reactos/lib/glu32/libnurbs/internals/ccw.cc

   1 /*
   2 ** License Applicability. Except to the extent portions of this file are
   3 ** made subject to an alternative license as permitted in the SGI Free
   4 ** Software License B, Version 1.1 (the "License"), the contents of this
   5 ** file are subject only to the provisions of the License. You may not use
   6 ** this file except in compliance with the License. You may obtain a copy
   7 ** of the License at Silicon Graphics, Inc., attn: Legal Services, 1600
   8 ** Amphitheatre Parkway, Mountain View, CA 94043-1351, or at:
   9 **
  10 ** http://oss.sgi.com/projects/FreeB
  11 **
  12 ** Note that, as provided in the License, the Software is distributed on an
  13 ** "AS IS" basis, with ALL EXPRESS AND IMPLIED WARRANTIES AND CONDITIONS
  14 ** DISCLAIMED, INCLUDING, WITHOUT LIMITATION, ANY IMPLIED WARRANTIES AND
  15 ** CONDITIONS OF MERCHANTABILITY, SATISFACTORY QUALITY, FITNESS FOR A
  16 ** PARTICULAR PURPOSE, AND NON-INFRINGEMENT.
  17 **
  18 ** Original Code. The Original Code is: OpenGL Sample Implementation,
  19 ** Version 1.2.1, released January 26, 2000, developed by Silicon Graphics,
  20 ** Inc. The Original Code is Copyright (c) 1991-2000 Silicon Graphics, Inc.
  21 ** Copyright in any portions created by third parties is as indicated
  22 ** elsewhere herein. All Rights Reserved.
  23 **
  24 ** Additional Notice Provisions: The application programming interfaces
  25 ** established by SGI in conjunction with the Original Code are The
  26 ** OpenGL(R) Graphics System: A Specification (Version 1.2.1), released
  27 ** April 1, 1999; The OpenGL(R) Graphics System Utility Library (Version
  28 ** 1.3), released November 4, 1998; and OpenGL(R) Graphics with the X
  29 ** Window System(R) (Version 1.3), released October 19, 1998. This software
  30 ** was created using the OpenGL(R) version 1.2.1 Sample Implementation
  31 ** published by SGI, but has not been independently verified as being
  32 ** compliant with the OpenGL(R) version 1.2.1 Specification.
  33 */
  34
  35 /*
  36  * ccw.c++
  37  *
  38  * $Date$ $Revision: 1.1 $
  39  * $Header: /cygdrive/c/RCVS/CVS/ReactOS/reactos/lib/glu32/libnurbs/internals/ccw.cc,v 1.1 2004/02/02 16:39:11 navaraf Exp $
  40  */
  41
  42 #include "glimports.h"
  43 #include "mystdio.h"
  44 #include "myassert.h"
  45 #include "subdivider.h"
  46 #include "types.h"
  47 #include "arc.h"
  48 #include "trimvertex.h"
  49 #include "simplemath.h"
  50
  51 inline int
  52 Subdivider::bbox( TrimVertex *a, TrimVertex *b, TrimVertex *c, int p )
  53 {
  54     return bbox( a->param[p], b->param[p], c->param[p],
  55                  a->param[1-p], b->param[1-p], c->param[1-p] );
  56 }
  57
  58 int
  59 Subdivider::ccwTurn_sr( Arc_ptr j1, Arc_ptr j2 ) // dir = 1
  60 {
  61     register TrimVertex *v1     = &j1->pwlArc->pts[j1->pwlArc->npts-1];
  62     register TrimVertex *v1last = &j1->pwlArc->pts[0];
  63     register TrimVertex *v2     = &j2->pwlArc->pts[0];
  64     register TrimVertex *v2last = &j2->pwlArc->pts[j2->pwlArc->npts-1];
  65     register TrimVertex *v1next = v1-1;
  66     register TrimVertex *v2next = v2+1;
  67     int sgn;
  68
  69     assert( v1 != v1last );
  70     assert( v2 != v2last );
  71
  72 #ifndef NDEBUG
  73     dprintf( "arc_ccw_turn, p = %d\n", 0 );
  74 #endif
  75
  76     // the arcs lie on the line (0 == v1->param[0])
  77     if( v1->param[0] == v1next->param[0] && v2->param[0] == v2next->param[0] )
  78         return 0;
  79
  80     if( v2next->param[0] < v2->param[0] || v1next->param[0] < v1->param[0] )
  81         ::mylongjmp( jumpbuffer, 28 );
  82
  83     if( v1->param[1] < v2->param[1] )
  84         return 0;
  85     else if( v1->param[1] > v2->param[1] )
  86         return 1;
  87
  88     while( 1 ) {
  89         if( v1next->param[0] < v2next->param[0] ) {
  90 #ifndef NDEBUG
  91             dprintf( "case a\n" );
  92 #endif
  93             assert( v1->param[0] <= v1next->param[0] );
  94             assert( v2->param[0] <= v1next->param[0] );
  95             switch( bbox( v2, v2next, v1next, 1 ) ) {
  96                 case -1:
  97                     return 0;
  98                 case 0:
  99                    sgn = ccw( v1next, v2, v2next );
 100                    if( sgn != -1 ) {
 101                         return sgn;
 102                    } else {
 103 #ifdef DEBUG
 104                         dprintf( "decr\n" );
 105 #endif
 106                         v1 = v1next--;
 107                         if( v1 == v1last ) {
 108 #ifdef DEBUG
 109                             dprintf( "no good results\n" );
 110 #endif
 111                             return 0; // ill-conditioned, guess answer
 112                         }
 113                     }
 114                     break;
 115                 case 1:
 116                     return 1;
 117             }
 118         } else if( v1next->param[0] > v2next->param[0] ) {
 119 #ifndef NDEBUG
 120             dprintf( "case b\n" );
 121 #endif
 122             assert( v1->param[0] <= v2next->param[0] );
 123             assert( v2->param[0] <= v2next->param[0] );
 124             switch( bbox( v1, v1next, v2next, 1 ) ) {
 125                 case -1:
 126                     return 1;
 127                 case 0:
 128                    sgn = ccw( v1next, v1, v2next );
 129                    if( sgn != -1 ) {
 130                         return sgn;
 131                    } else {
 132 #ifdef DEBUG
 133                         dprintf( "incr\n" );
 134 #endif
 135                         v2 = v2next++;
 136                         if( v2 == v2last ) {
 137 #ifdef DEBUG
 138                             dprintf( "no good results\n" );
 139 #endif
 140                             return 0; // ill-conditioned, guess answer
 141                         }
 142                     }
 143                     break;
 144                 case 1:
 145                     return 0;
 146             }
 147         } else {
 148 #ifndef NDEBUG
 149             dprintf( "case ab\n" );
 150 #endif
 151             if( v1next->param[1] < v2next->param[1] )
 152                 return 0;
 153             else if( v1next->param[1] > v2next->param[1] )
 154                 return 1;
 155             else {
 156 #ifdef DEBUG
 157                 dprintf( "incr\n" );
 158 #endif
 159                 v2 = v2next++;
 160                 if( v2 == v2last ) {
 161 #ifdef DEBUG
 162                     dprintf( "no good results\n" );
 163 #endif
 164                     return 0; // ill-conditioned, guess answer
 165                 }
 166             }
 167         }
 168     }
 169 }
 170
 171 int
 172 Subdivider::ccwTurn_sl( Arc_ptr j1, Arc_ptr j2 ) // dir = 0
 173 {
 174     register TrimVertex *v1     = &j1->pwlArc->pts[j1->pwlArc->npts-1];
 175     register TrimVertex *v1last = &j1->pwlArc->pts[0];
 176     register TrimVertex *v2     = &j2->pwlArc->pts[0];
 177     register TrimVertex *v2last = &j2->pwlArc->pts[j2->pwlArc->npts-1];
 178     register TrimVertex *v1next = v1-1;
 179     register TrimVertex *v2next = v2+1;
 180     int sgn;
 181
 182     assert( v1 != v1last );
 183     assert( v2 != v2last );
 184
 185 #ifndef NDEBUG
 186     dprintf( "arc_ccw_turn, p = %d\n", 0 );
 187 #endif
 188
 189     // the arcs lie on the line (0 == v1->param[0])
 190     if( v1->param[0] == v1next->param[0] && v2->param[0] == v2next->param[0] )
 191         return 0;
 192
 193     if( v2next->param[0] > v2->param[0] || v1next->param[0] > v1->param[0] )
 194         ::mylongjmp( jumpbuffer, 28 );
 195
 196     if( v1->param[1] < v2->param[1] )
 197         return 1;
 198     else if( v1->param[1] > v2->param[1] )
 199         return 0;
 200
 201     while( 1 ) {
 202         if( v1next->param[0] > v2next->param[0] ) {
 203 #ifndef NDEBUG
 204             dprintf( "case c\n" );
 205 #endif
 206             assert( v1->param[0] >= v1next->param[0] );
 207             assert( v2->param[0] >= v1next->param[0] );
 208             switch( bbox( v2next, v2, v1next, 1 ) ) {
 209                 case -1:
 210                     return 1;
 211                 case 0:
 212                     sgn = ccw( v1next, v2, v2next );
 213                     if( sgn != -1 )
 214                         return sgn;
 215                     else {
 216                         v1 = v1next--;
 217 #ifdef DEBUG
 218                         dprintf( "decr\n" );
 219 #endif
 220                         if( v1 == v1last ) {
 221 #ifdef DEBUG
 222                             dprintf( "no good results\n" );
 223 #endif
 224                             return 0; // ill-conditioned, guess answer
 225                         }
 226                     }
 227                     break;
 228                 case 1:
 229                     return 0;
 230             }
 231         } else if( v1next->param[0] < v2next->param[0] ) {
 232 #ifndef NDEBUG
 233             dprintf( "case d\n" );
 234 #endif
 235             assert( v1->param[0] >= v2next->param[0] );
 236             assert( v2->param[0] >= v2next->param[0] );
 237             switch( bbox( v1next, v1, v2next, 1 ) ) {
 238                 case -1:
 239                     return 0;
 240                 case 0:
 241                     sgn = ccw( v1next, v1, v2next );
 242                     if( sgn != -1 )
 243                         return sgn;
 244                     else {
 245                         v2 = v2next++;
 246 #ifdef DEBUG
 247                         dprintf( "incr\n" );
 248 #endif
 249                         if( v2 == v2last ) {
 250 #ifdef DEBUG
 251                             dprintf( "no good results\n" );
 252 #endif
 253                             return 0; // ill-conditioned, guess answer
 254                         }
 255                     }
 256                     break;
 257                 case 1:
 258                     return 1;
 259             }
 260         } else {
 261 #ifdef DEBUG
 262             dprintf( "case cd\n" );
 263 #endif
 264             if( v1next->param[1] < v2next->param[1] )
 265                 return 1;
 266             else if( v1next->param[1] > v2next->param[1] )
 267                 return 0;
 268             else {
 269                 v2 = v2next++;
 270 #ifdef DEBUG
 271                 dprintf( "incr\n" );
 272 #endif
 273                 if( v2 == v2last ) {
 274 #ifdef DEBUG
 275                     dprintf( "no good results\n" );
 276 #endif
 277                     return 0; // ill-conditioned, guess answer
 278                 }
 279             }
 280         }
 281     }
 282 }
 283
 284 int
 285 Subdivider::ccwTurn_tr( Arc_ptr j1, Arc_ptr j2 ) // dir = 1
 286 {
 287     register TrimVertex *v1     = &j1->pwlArc->pts[j1->pwlArc->npts-1];
 288     register TrimVertex *v1last = &j1->pwlArc->pts[0];
 289     register TrimVertex *v2     = &j2->pwlArc->pts[0];
 290     register TrimVertex *v2last = &j2->pwlArc->pts[j2->pwlArc->npts-1];
 291     register TrimVertex *v1next = v1-1;
 292     register TrimVertex *v2next = v2+1;
 293     int sgn;
 294
 295     assert( v1 != v1last );
 296     assert( v2 != v2last );
 297
 298 #ifndef NDEBUG
 299     dprintf( "arc_ccw_turn, p = %d\n", 1 );
 300 #endif
 301
 302     // the arcs lie on the line (1 == v1->param[1])
 303     if( v1->param[1] == v1next->param[1] && v2->param[1] == v2next->param[1] )
 304         return 0;
 305
 306     if( v2next->param[1] < v2->param[1] || v1next->param[1] < v1->param[1] )
 307         ::mylongjmp( jumpbuffer, 28 );
 308
 309     if( v1->param[0] < v2->param[0] )
 310         return 1;
 311     else if( v1->param[0] > v2->param[0] )
 312         return 0;
 313
 314     while( 1 ) {
 315         if( v1next->param[1] < v2next->param[1] ) {
 316 #ifndef NDEBUG
 317             dprintf( "case a\n" );
 318 #endif
 319             assert( v1->param[1] <= v1next->param[1] );
 320             assert( v2->param[1] <= v1next->param[1] );
 321             switch( bbox( v2, v2next, v1next, 0 ) ) {
 322                 case -1:
 323                     return 1;
 324                 case 0:
 325                    sgn = ccw( v1next, v2, v2next );
 326                    if( sgn != -1 ) {
 327                         return sgn;
 328                    } else {
 329 #ifdef DEBUG
 330                         dprintf( "decr\n" );
 331 #endif
 332                         v1 = v1next--;
 333                         if( v1 == v1last ) {
 334 #ifdef DEBUG
 335                             dprintf( "no good results\n" );
 336 #endif
 337                             return 0; // ill-conditioned, guess answer
 338                         }
 339                     }
 340                     break;
 341                 case 1:
 342                     return 0;
 343             }
 344         } else if( v1next->param[1] > v2next->param[1] ) {
 345 #ifndef NDEBUG
 346             dprintf( "case b\n" );
 347 #endif
 348             assert( v1->param[1] <= v2next->param[1] );
 349             assert( v2->param[1] <= v2next->param[1] );
 350             switch( bbox( v1, v1next, v2next, 0 ) ) {
 351                 case -1:
 352                     return 0;
 353                 case 0:
 354                    sgn = ccw( v1next, v1, v2next );
 355                    if( sgn != -1 ) {
 356                         return sgn;
 357                    } else {
 358 #ifdef DEBUG
 359                         dprintf( "incr\n" );
 360 #endif
 361                         v2 = v2next++;
 362                         if( v2 == v2last ) {
 363 #ifdef DEBUG
 364                             dprintf( "no good results\n" );
 365 #endif
 366                             return 0; // ill-conditioned, guess answer
 367                         }
 368                     }
 369                     break;
 370                 case 1:
 371                     return 1;
 372             }
 373         } else {
 374 #ifdef DEBUG
 375             dprintf( "case ab\n" );
 376 #endif
 377             if( v1next->param[0] < v2next->param[0] )
 378                 return 1;
 379             else if( v1next->param[0] > v2next->param[0] )
 380                 return 0;
 381             else {
 382 #ifdef DEBUG
 383                 dprintf( "incr\n" );
 384 #endif
 385                 v2 = v2next++;
 386                 if( v2 == v2last ) {
 387 #ifdef DEBUG
 388                     dprintf( "no good results\n" );
 389 #endif
 390                     return 0; // ill-conditioned, guess answer
 391                 }
 392             }
 393         }
 394     }
 395 }
 396
 397 int
 398 Subdivider::ccwTurn_tl( Arc_ptr j1, Arc_ptr j2 )
 399 {
 400     register TrimVertex *v1     = &j1->pwlArc->pts[j1->pwlArc->npts-1];
 401     register TrimVertex *v1last = &j1->pwlArc->pts[0];
 402     register TrimVertex *v2     = &j2->pwlArc->pts[0];
 403     register TrimVertex *v2last = &j2->pwlArc->pts[j2->pwlArc->npts-1];
 404     register TrimVertex *v1next = v1-1;
 405     register TrimVertex *v2next = v2+1;
 406     int sgn;
 407
 408     assert( v1 != v1last );
 409     assert( v2 != v2last );
 410
 411 #ifndef NDEBUG
 412     dprintf( "arc_ccw_turn, p = %d\n", 1 );
 413 #endif
 414
 415     // the arcs lie on the line (1 == v1->param[1])
 416     if( v1->param[1] == v1next->param[1] && v2->param[1] == v2next->param[1] )
 417         return 0;
 418
 419     if( v2next->param[1] > v2->param[1] || v1next->param[1] > v1->param[1] )
 420         ::mylongjmp( jumpbuffer, 28 );
 421
 422     if( v1->param[0] < v2->param[0] )
 423         return 0;
 424     else if( v1->param[0] > v2->param[0] )
 425         return 1;
 426
 427     while( 1 ) {
 428         if( v1next->param[1] > v2next->param[1] ) {
 429 #ifndef NDEBUG
 430             dprintf( "case c\n" );
 431 #endif
 432             assert( v1->param[1] >= v1next->param[1] );
 433             assert( v2->param[1] >= v1next->param[1] );
 434             switch( bbox( v2next, v2, v1next, 0 ) ) {
 435                 case -1:
 436                     return 0;
 437                 case 0:
 438                     sgn = ccw( v1next, v2, v2next );
 439                     if( sgn != -1 )
 440                         return sgn;
 441                     else {
 442                         v1 = v1next--;
 443 #ifdef DEBUG
 444                         dprintf( "decr\n" );
 445 #endif
 446                         if( v1 == v1last ) {
 447 #ifdef DEBUG
 448                             dprintf( "no good results\n" );
 449 #endif
 450                             return 0; // ill-conditioned, guess answer
 451                         }
 452                     }
 453                     break;
 454                 case 1:
 455                     return 1;
 456             }
 457         } else if( v1next->param[1] < v2next->param[1] ) {
 458 #ifndef NDEBUG
 459             dprintf( "case d\n" );
 460             assert( v1->param[1] >= v2next->param[1] );
 461             assert( v2->param[1] >= v2next->param[1] );
 462 #endif
 463             switch( bbox( v1next, v1, v2next, 0 ) ) {
 464                 case -1:
 465                     return 1;
 466                 case 0:
 467                     sgn = ccw( v1next, v1, v2next );
 468                     if( sgn != -1 )
 469                         return sgn;
 470                     else {
 471                         v2 = v2next++;
 472 #ifdef DEBUG
 473                         dprintf( "incr\n" );
 474 #endif
 475                         if( v2 == v2last ) {
 476 #ifdef DEBUG
 477                             dprintf( "no good results\n" );
 478 #endif
 479                             return 0; // ill-conditioned, guess answer
 480                         }
 481                     }
 482                     break;
 483                 case 1:
 484                     return 0;
 485             }
 486         } else {
 487 #ifdef DEBUG
 488             dprintf( "case cd\n" );
 489 #endif
 490             if( v1next->param[0] < v2next->param[0] )
 491                 return 0;
 492             else if( v1next->param[0] > v2next->param[0] )
 493                 return 1;
 494             else {
 495                 v2 = v2next++;
 496 #ifdef DEBUG
 497                 dprintf( "incr\n" );
 498 #endif
 499                 if( v2 == v2last ) {
 500 #ifdef DEBUG
 501                     dprintf( "no good results\n" );
 502 #endif
 503                     return 0; // ill-conditioned, guess answer
 504                 }
 505             }
 506         }
 507     }
 508 }
 509
 510
 511 #ifndef NDEBUG
 512 int
 513 Subdivider::bbox( register REAL sa, register REAL sb, register REAL sc,
 514       register REAL ta, register REAL tb, register REAL tc )
 515 #else
 516 int
 517 Subdivider::bbox( register REAL sa, register REAL sb, register REAL sc,
 518       register REAL   , register REAL   , register REAL    )
 519 #endif
 520 {
 521 #ifndef NDEBUG
 522     assert( tc >= ta );
 523     assert( tc <= tb );
 524 #endif
 525
 526     if( sa < sb ) {
 527         if( sc <= sa ) {
 528             return -1;
 529         } else if( sb <= sc ) {
 530             return 1;
 531         } else {
 532             return 0;
 533         }
 534     } else if( sa > sb ) {
 535         if( sc >= sa ) {
 536             return 1;
 537         } else if( sb >= sc ) {
 538             return -1;
 539         } else {
 540             return 0;
 541         }
 542     } else {
 543         if( sc > sa ) {
 544             return 1;
 545         } else if( sb > sc ) {
 546             return -1;
 547         } else {
 548             return 0;
 549         }
 550     }
 551 }
 552
 553 /*----------------------------------------------------------------------------
 554  * ccw - determine how three points are oriented by computing their
 555  *       determinant.
 556  *       Return 1 if the vertices are ccw oriented,
 557  *              0 if they are cw oriented, or
 558  *              -1 if the computation is ill-conditioned.
 559  *----------------------------------------------------------------------------
 560  */
 561 int
 562 Subdivider::ccw( TrimVertex *a, TrimVertex *b, TrimVertex *c )
 563 {
 564     REAL d = det3( a, b, c );
 565     if( glu_abs(d) < 0.0001 ) return -1;
 566     return (d < 0.0) ? 0 : 1;
 567 }