src/glu/sgi/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  */
  39
  40 #include "glimports.h"
  41 #include "mystdio.h"
  42 #include "myassert.h"
  43 #include "subdivider.h"
  44 #include "types.h"
  45 #include "arc.h"
  46 #include "trimvertex.h"
  47 #include "simplemath.h"
  48
  49 inline int
  50 Subdivider::bbox( TrimVertex *a, TrimVertex *b, TrimVertex *c, int p )
  51 {
  52     return bbox( a->param[p], b->param[p], c->param[p],
  53                  a->param[1-p], b->param[1-p], c->param[1-p] );
  54 }
  55
  56 int
  57 Subdivider::ccwTurn_sr( Arc_ptr j1, Arc_ptr j2 ) // dir = 1
  58 {
  59     register TrimVertex *v1     = &j1->pwlArc->pts[j1->pwlArc->npts-1];
  60     register TrimVertex *v1last = &j1->pwlArc->pts[0];
  61     register TrimVertex *v2     = &j2->pwlArc->pts[0];
  62     register TrimVertex *v2last = &j2->pwlArc->pts[j2->pwlArc->npts-1];
  63     register TrimVertex *v1next = v1-1;
  64     register TrimVertex *v2next = v2+1;
  65     int sgn;
  66
  67     assert( v1 != v1last );
  68     assert( v2 != v2last );
  69
  70 #ifndef NDEBUG
  71     _glu_dprintf( "arc_ccw_turn, p = %d\n", 0 );
  72 #endif
  73
  74     // the arcs lie on the line (0 == v1->param[0])
  75     if( v1->param[0] == v1next->param[0] && v2->param[0] == v2next->param[0] )
  76         return 0;
  77
  78     if( v2next->param[0] < v2->param[0] || v1next->param[0] < v1->param[0] )
  79         ::mylongjmp( jumpbuffer, 28 );
  80
  81     if( v1->param[1] < v2->param[1] )
  82         return 0;
  83     else if( v1->param[1] > v2->param[1] )
  84         return 1;
  85
  86     while( 1 ) {
  87         if( v1next->param[0] < v2next->param[0] ) {
  88 #ifndef NDEBUG
  89             _glu_dprintf( "case a\n" );
  90 #endif
  91             assert( v1->param[0] <= v1next->param[0] );
  92             assert( v2->param[0] <= v1next->param[0] );
  93             switch( bbox( v2, v2next, v1next, 1 ) ) {
  94                 case -1:
  95                     return 0;
  96                 case 0:
  97                    sgn = ccw( v1next, v2, v2next );
  98                    if( sgn != -1 ) {
  99                         return sgn;
 100                    } else {
 101 #ifdef DEBUG
 102                         _glu_dprintf( "decr\n" );
 103 #endif
 104                         v1 = v1next--;
 105                         if( v1 == v1last ) {
 106 #ifdef DEBUG
 107                             _glu_dprintf( "no good results\n" );
 108 #endif
 109                             return 0; // ill-conditioned, guess answer
 110                         }
 111                     }
 112                     break;
 113                 case 1:
 114                     return 1;
 115             }
 116         } else if( v1next->param[0] > v2next->param[0] ) {
 117 #ifndef NDEBUG
 118             _glu_dprintf( "case b\n" );
 119 #endif
 120             assert( v1->param[0] <= v2next->param[0] );
 121             assert( v2->param[0] <= v2next->param[0] );
 122             switch( bbox( v1, v1next, v2next, 1 ) ) {
 123                 case -1:
 124                     return 1;
 125                 case 0:
 126                    sgn = ccw( v1next, v1, v2next );
 127                    if( sgn != -1 ) {
 128                         return sgn;
 129                    } else {
 130 #ifdef DEBUG
 131                         _glu_dprintf( "incr\n" );
 132 #endif
 133                         v2 = v2next++;
 134                         if( v2 == v2last ) {
 135 #ifdef DEBUG
 136                             _glu_dprintf( "no good results\n" );
 137 #endif
 138                             return 0; // ill-conditioned, guess answer
 139                         }
 140                     }
 141                     break;
 142                 case 1:
 143                     return 0;
 144             }
 145         } else {
 146 #ifndef NDEBUG
 147             _glu_dprintf( "case ab\n" );
 148 #endif
 149             if( v1next->param[1] < v2next->param[1] )
 150                 return 0;
 151             else if( v1next->param[1] > v2next->param[1] )
 152                 return 1;
 153             else {
 154 #ifdef DEBUG
 155                 _glu_dprintf( "incr\n" );
 156 #endif
 157                 v2 = v2next++;
 158                 if( v2 == v2last ) {
 159 #ifdef DEBUG
 160                     _glu_dprintf( "no good results\n" );
 161 #endif
 162                     return 0; // ill-conditioned, guess answer
 163                 }
 164             }
 165         }
 166     }
 167 }
 168
 169 int
 170 Subdivider::ccwTurn_sl( Arc_ptr j1, Arc_ptr j2 ) // dir = 0
 171 {
 172     register TrimVertex *v1     = &j1->pwlArc->pts[j1->pwlArc->npts-1];
 173     register TrimVertex *v1last = &j1->pwlArc->pts[0];
 174     register TrimVertex *v2     = &j2->pwlArc->pts[0];
 175     register TrimVertex *v2last = &j2->pwlArc->pts[j2->pwlArc->npts-1];
 176     register TrimVertex *v1next = v1-1;
 177     register TrimVertex *v2next = v2+1;
 178     int sgn;
 179
 180     assert( v1 != v1last );
 181     assert( v2 != v2last );
 182
 183 #ifndef NDEBUG
 184     _glu_dprintf( "arc_ccw_turn, p = %d\n", 0 );
 185 #endif
 186
 187     // the arcs lie on the line (0 == v1->param[0])
 188     if( v1->param[0] == v1next->param[0] && v2->param[0] == v2next->param[0] )
 189         return 0;
 190
 191     if( v2next->param[0] > v2->param[0] || v1next->param[0] > v1->param[0] )
 192         ::mylongjmp( jumpbuffer, 28 );
 193
 194     if( v1->param[1] < v2->param[1] )
 195         return 1;
 196     else if( v1->param[1] > v2->param[1] )
 197         return 0;
 198
 199     while( 1 ) {
 200         if( v1next->param[0] > v2next->param[0] ) {
 201 #ifndef NDEBUG
 202             _glu_dprintf( "case c\n" );
 203 #endif
 204             assert( v1->param[0] >= v1next->param[0] );
 205             assert( v2->param[0] >= v1next->param[0] );
 206             switch( bbox( v2next, v2, v1next, 1 ) ) {
 207                 case -1:
 208                     return 1;
 209                 case 0:
 210                     sgn = ccw( v1next, v2, v2next );
 211                     if( sgn != -1 )
 212                         return sgn;
 213                     else {
 214                         v1 = v1next--;
 215 #ifdef DEBUG
 216                         _glu_dprintf( "decr\n" );
 217 #endif
 218                         if( v1 == v1last ) {
 219 #ifdef DEBUG
 220                             _glu_dprintf( "no good results\n" );
 221 #endif
 222                             return 0; // ill-conditioned, guess answer
 223                         }
 224                     }
 225                     break;
 226                 case 1:
 227                     return 0;
 228             }
 229         } else if( v1next->param[0] < v2next->param[0] ) {
 230 #ifndef NDEBUG
 231             _glu_dprintf( "case d\n" );
 232 #endif
 233             assert( v1->param[0] >= v2next->param[0] );
 234             assert( v2->param[0] >= v2next->param[0] );
 235             switch( bbox( v1next, v1, v2next, 1 ) ) {
 236                 case -1:
 237                     return 0;
 238                 case 0:
 239                     sgn = ccw( v1next, v1, v2next );
 240                     if( sgn != -1 )
 241                         return sgn;
 242                     else {
 243                         v2 = v2next++;
 244 #ifdef DEBUG
 245                         _glu_dprintf( "incr\n" );
 246 #endif
 247                         if( v2 == v2last ) {
 248 #ifdef DEBUG
 249                             _glu_dprintf( "no good results\n" );
 250 #endif
 251                             return 0; // ill-conditioned, guess answer
 252                         }
 253                     }
 254                     break;
 255                 case 1:
 256                     return 1;
 257             }
 258         } else {
 259 #ifdef DEBUG
 260             _glu_dprintf( "case cd\n" );
 261 #endif
 262             if( v1next->param[1] < v2next->param[1] )
 263                 return 1;
 264             else if( v1next->param[1] > v2next->param[1] )
 265                 return 0;
 266             else {
 267                 v2 = v2next++;
 268 #ifdef DEBUG
 269                 _glu_dprintf( "incr\n" );
 270 #endif
 271                 if( v2 == v2last ) {
 272 #ifdef DEBUG
 273                     _glu_dprintf( "no good results\n" );
 274 #endif
 275                     return 0; // ill-conditioned, guess answer
 276                 }
 277             }
 278         }
 279     }
 280 }
 281
 282 int
 283 Subdivider::ccwTurn_tr( Arc_ptr j1, Arc_ptr j2 ) // dir = 1
 284 {
 285     register TrimVertex *v1     = &j1->pwlArc->pts[j1->pwlArc->npts-1];
 286     register TrimVertex *v1last = &j1->pwlArc->pts[0];
 287     register TrimVertex *v2     = &j2->pwlArc->pts[0];
 288     register TrimVertex *v2last = &j2->pwlArc->pts[j2->pwlArc->npts-1];
 289     register TrimVertex *v1next = v1-1;
 290     register TrimVertex *v2next = v2+1;
 291     int sgn;
 292
 293     assert( v1 != v1last );
 294     assert( v2 != v2last );
 295
 296 #ifndef NDEBUG
 297     _glu_dprintf( "arc_ccw_turn, p = %d\n", 1 );
 298 #endif
 299
 300     // the arcs lie on the line (1 == v1->param[1])
 301     if( v1->param[1] == v1next->param[1] && v2->param[1] == v2next->param[1] )
 302         return 0;
 303
 304     if( v2next->param[1] < v2->param[1] || v1next->param[1] < v1->param[1] )
 305         ::mylongjmp( jumpbuffer, 28 );
 306
 307     if( v1->param[0] < v2->param[0] )
 308         return 1;
 309     else if( v1->param[0] > v2->param[0] )
 310         return 0;
 311
 312     while( 1 ) {
 313         if( v1next->param[1] < v2next->param[1] ) {
 314 #ifndef NDEBUG
 315             _glu_dprintf( "case a\n" );
 316 #endif
 317             assert( v1->param[1] <= v1next->param[1] );
 318             assert( v2->param[1] <= v1next->param[1] );
 319             switch( bbox( v2, v2next, v1next, 0 ) ) {
 320                 case -1:
 321                     return 1;
 322                 case 0:
 323                    sgn = ccw( v1next, v2, v2next );
 324                    if( sgn != -1 ) {
 325                         return sgn;
 326                    } else {
 327 #ifdef DEBUG
 328                         _glu_dprintf( "decr\n" );
 329 #endif
 330                         v1 = v1next--;
 331                         if( v1 == v1last ) {
 332 #ifdef DEBUG
 333                             _glu_dprintf( "no good results\n" );
 334 #endif
 335                             return 0; // ill-conditioned, guess answer
 336                         }
 337                     }
 338                     break;
 339                 case 1:
 340                     return 0;
 341             }
 342         } else if( v1next->param[1] > v2next->param[1] ) {
 343 #ifndef NDEBUG
 344             _glu_dprintf( "case b\n" );
 345 #endif
 346             assert( v1->param[1] <= v2next->param[1] );
 347             assert( v2->param[1] <= v2next->param[1] );
 348             switch( bbox( v1, v1next, v2next, 0 ) ) {
 349                 case -1:
 350                     return 0;
 351                 case 0:
 352                    sgn = ccw( v1next, v1, v2next );
 353                    if( sgn != -1 ) {
 354                         return sgn;
 355                    } else {
 356 #ifdef DEBUG
 357                         _glu_dprintf( "incr\n" );
 358 #endif
 359                         v2 = v2next++;
 360                         if( v2 == v2last ) {
 361 #ifdef DEBUG
 362                             _glu_dprintf( "no good results\n" );
 363 #endif
 364                             return 0; // ill-conditioned, guess answer
 365                         }
 366                     }
 367                     break;
 368                 case 1:
 369                     return 1;
 370             }
 371         } else {
 372 #ifdef DEBUG
 373             _glu_dprintf( "case ab\n" );
 374 #endif
 375             if( v1next->param[0] < v2next->param[0] )
 376                 return 1;
 377             else if( v1next->param[0] > v2next->param[0] )
 378                 return 0;
 379             else {
 380 #ifdef DEBUG
 381                 _glu_dprintf( "incr\n" );
 382 #endif
 383                 v2 = v2next++;
 384                 if( v2 == v2last ) {
 385 #ifdef DEBUG
 386                     _glu_dprintf( "no good results\n" );
 387 #endif
 388                     return 0; // ill-conditioned, guess answer
 389                 }
 390             }
 391         }
 392     }
 393 }
 394
 395 int
 396 Subdivider::ccwTurn_tl( Arc_ptr j1, Arc_ptr j2 )
 397 {
 398     register TrimVertex *v1     = &j1->pwlArc->pts[j1->pwlArc->npts-1];
 399     register TrimVertex *v1last = &j1->pwlArc->pts[0];
 400     register TrimVertex *v2     = &j2->pwlArc->pts[0];
 401     register TrimVertex *v2last = &j2->pwlArc->pts[j2->pwlArc->npts-1];
 402     register TrimVertex *v1next = v1-1;
 403     register TrimVertex *v2next = v2+1;
 404     int sgn;
 405
 406     assert( v1 != v1last );
 407     assert( v2 != v2last );
 408
 409 #ifndef NDEBUG
 410     _glu_dprintf( "arc_ccw_turn, p = %d\n", 1 );
 411 #endif
 412
 413     // the arcs lie on the line (1 == v1->param[1])
 414     if( v1->param[1] == v1next->param[1] && v2->param[1] == v2next->param[1] )
 415         return 0;
 416
 417     if( v2next->param[1] > v2->param[1] || v1next->param[1] > v1->param[1] )
 418         ::mylongjmp( jumpbuffer, 28 );
 419
 420     if( v1->param[0] < v2->param[0] )
 421         return 0;
 422     else if( v1->param[0] > v2->param[0] )
 423         return 1;
 424
 425     while( 1 ) {
 426         if( v1next->param[1] > v2next->param[1] ) {
 427 #ifndef NDEBUG
 428             _glu_dprintf( "case c\n" );
 429 #endif
 430             assert( v1->param[1] >= v1next->param[1] );
 431             assert( v2->param[1] >= v1next->param[1] );
 432             switch( bbox( v2next, v2, v1next, 0 ) ) {
 433                 case -1:
 434                     return 0;
 435                 case 0:
 436                     sgn = ccw( v1next, v2, v2next );
 437                     if( sgn != -1 )
 438                         return sgn;
 439                     else {
 440                         v1 = v1next--;
 441 #ifdef DEBUG
 442                         _glu_dprintf( "decr\n" );
 443 #endif
 444                         if( v1 == v1last ) {
 445 #ifdef DEBUG
 446                             _glu_dprintf( "no good results\n" );
 447 #endif
 448                             return 0; // ill-conditioned, guess answer
 449                         }
 450                     }
 451                     break;
 452                 case 1:
 453                     return 1;
 454             }
 455         } else if( v1next->param[1] < v2next->param[1] ) {
 456 #ifndef NDEBUG
 457             _glu_dprintf( "case d\n" );
 458             assert( v1->param[1] >= v2next->param[1] );
 459             assert( v2->param[1] >= v2next->param[1] );
 460 #endif
 461             switch( bbox( v1next, v1, v2next, 0 ) ) {
 462                 case -1:
 463                     return 1;
 464                 case 0:
 465                     sgn = ccw( v1next, v1, v2next );
 466                     if( sgn != -1 )
 467                         return sgn;
 468                     else {
 469                         v2 = v2next++;
 470 #ifdef DEBUG
 471                         _glu_dprintf( "incr\n" );
 472 #endif
 473                         if( v2 == v2last ) {
 474 #ifdef DEBUG
 475                             _glu_dprintf( "no good results\n" );
 476 #endif
 477                             return 0; // ill-conditioned, guess answer
 478                         }
 479                     }
 480                     break;
 481                 case 1:
 482                     return 0;
 483             }
 484         } else {
 485 #ifdef DEBUG
 486             _glu_dprintf( "case cd\n" );
 487 #endif
 488             if( v1next->param[0] < v2next->param[0] )
 489                 return 0;
 490             else if( v1next->param[0] > v2next->param[0] )
 491                 return 1;
 492             else {
 493                 v2 = v2next++;
 494 #ifdef DEBUG
 495                 _glu_dprintf( "incr\n" );
 496 #endif
 497                 if( v2 == v2last ) {
 498 #ifdef DEBUG
 499                     _glu_dprintf( "no good results\n" );
 500 #endif
 501                     return 0; // ill-conditioned, guess answer
 502                 }
 503             }
 504         }
 505     }
 506 }
 507
 508
 509 #ifndef NDEBUG
 510 int
 511 Subdivider::bbox( register REAL sa, register REAL sb, register REAL sc,
 512       register REAL ta, register REAL tb, register REAL tc )
 513 #else
 514 int
 515 Subdivider::bbox( register REAL sa, register REAL sb, register REAL sc,
 516       register REAL   , register REAL   , register REAL    )
 517 #endif
 518 {
 519 #ifndef NDEBUG
 520     assert( tc >= ta );
 521     assert( tc <= tb );
 522 #endif
 523
 524     if( sa < sb ) {
 525         if( sc <= sa ) {
 526             return -1;
 527         } else if( sb <= sc ) {
 528             return 1;
 529         } else {
 530             return 0;
 531         }
 532     } else if( sa > sb ) {
 533         if( sc >= sa ) {
 534             return 1;
 535         } else if( sb >= sc ) {
 536             return -1;
 537         } else {
 538             return 0;
 539         }
 540     } else {
 541         if( sc > sa ) {
 542             return 1;
 543         } else if( sb > sc ) {
 544             return -1;
 545         } else {
 546             return 0;
 547         }
 548     }
 549 }
 550
 551 /*----------------------------------------------------------------------------
 552  * ccw - determine how three points are oriented by computing their
 553  *       determinant.
 554  *       Return 1 if the vertices are ccw oriented,
 555  *              0 if they are cw oriented, or
 556  *              -1 if the computation is ill-conditioned.
 557  *----------------------------------------------------------------------------
 558  */
 559 int
 560 Subdivider::ccw( TrimVertex *a, TrimVertex *b, TrimVertex *c )
 561 {
 562     REAL d = det3( a, b, c );
 563     if( glu_abs(d) < 0.0001 ) return -1;
 564     return (d < 0.0) ? 0 : 1;
 565 }