intersect.cc revision f220fa62
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 * intersect.c++ 37 * 38 */ 39 40#include "glimports.h" 41#include "myassert.h" 42#include "mystdio.h" 43#include "subdivider.h" 44#include "arc.h" 45#include "bin.h" 46#include "backend.h" 47#include "trimvertpool.h" 48 49/*#define NOTDEF*/ 50 51enum i_result { INTERSECT_VERTEX, INTERSECT_EDGE }; 52 53/* local functions */ 54#ifndef NDEBUG // for asserts only 55static int arc_classify( Arc_ptr, int, REAL ); 56#endif 57static enum i_result pwlarc_intersect( PwlArc *, int, REAL, int, int[3] ); 58 59 60void 61Subdivider::partition( Bin & bin, Bin & left, Bin & intersections, 62 Bin & right, Bin & unknown, int param, REAL value ) 63{ 64 Bin headonleft, headonright, tailonleft, tailonright; 65 66 for( Arc_ptr jarc = bin.removearc(); jarc; jarc = bin.removearc() ) { 67 68 REAL tdiff = jarc->tail()[param] - value; 69 REAL hdiff = jarc->head()[param] - value; 70 71 if( tdiff > 0.0 ) { 72 if( hdiff > 0.0 ) { 73 right.addarc( jarc ); 74 } else if( hdiff == 0.0 ) { 75 tailonright.addarc( jarc ); 76 } else { 77 Arc_ptr jtemp; 78 switch( arc_split(jarc, param, value, 0) ) { 79 case 2: 80 tailonright.addarc( jarc ); 81 headonleft.addarc( jarc->next ); 82 break; 83 case 31: 84 assert( jarc->head()[param] > value ); 85 right.addarc( jarc ); 86 tailonright.addarc( jtemp = jarc->next ); 87 headonleft.addarc( jtemp->next ); 88 break; 89 case 32: 90 assert( jarc->head()[param] <= value ); 91 tailonright .addarc( jarc ); 92 headonleft.addarc( jtemp = jarc->next ); 93 left.addarc( jtemp->next ); 94 break; 95 case 4: 96 right.addarc( jarc ); 97 tailonright.addarc( jtemp = jarc->next ); 98 headonleft.addarc( jtemp = jtemp->next ); 99 left.addarc( jtemp->next ); 100 } 101 } 102 } else if( tdiff == 0.0 ) { 103 if( hdiff > 0.0 ) { 104 headonright.addarc( jarc ); 105 } else if( hdiff == 0.0 ) { 106 unknown.addarc( jarc ); 107 } else { 108 headonleft.addarc( jarc ); 109 } 110 } else { 111 if( hdiff > 0.0 ) { 112 Arc_ptr jtemp; 113 switch( arc_split(jarc, param, value, 1) ) { 114 case 2: 115 tailonleft.addarc( jarc ); 116 headonright.addarc( jarc->next ); 117 break; 118 case 31: 119 assert( jarc->head()[param] < value ); 120 left.addarc( jarc ); 121 tailonleft.addarc( jtemp = jarc->next ); 122 headonright.addarc( jtemp->next ); 123 break; 124 case 32: 125 assert( jarc->head()[param] >= value ); 126 tailonleft.addarc( jarc ); 127 headonright.addarc( jtemp = jarc->next ); 128 right.addarc( jtemp->next ); 129 break; 130 case 4: 131 left.addarc( jarc ); 132 tailonleft.addarc( jtemp = jarc->next ); 133 headonright.addarc( jtemp = jtemp->next ); 134 right.addarc( jtemp->next ); 135 } 136 } else if( hdiff == 0.0 ) { 137 tailonleft.addarc( jarc ); 138 } else { 139 left.addarc( jarc ); 140 } 141 } 142 } 143 if( param == 0 ) { 144 classify_headonleft_s( headonleft, intersections, left, value ); 145 classify_tailonleft_s( tailonleft, intersections, left, value ); 146 classify_headonright_s( headonright, intersections, right, value ); 147 classify_tailonright_s( tailonright, intersections, right, value ); 148 } else { 149 classify_headonleft_t( headonleft, intersections, left, value ); 150 classify_tailonleft_t( tailonleft, intersections, left, value ); 151 classify_headonright_t( headonright, intersections, right, value ); 152 classify_tailonright_t( tailonright, intersections, right, value ); 153 } 154} 155 156inline static void 157vert_interp( TrimVertex *n, TrimVertex *l, TrimVertex *r, int p, REAL val ) 158{ 159 assert( val > l->param[p]); 160 assert( val < r->param[p]); 161 162 n->nuid = l->nuid; 163 164 n->param[p] = val; 165 if( l->param[1-p] != r->param[1-p] ) { 166 REAL ratio = (val - l->param[p]) / (r->param[p] - l->param[p]); 167 n->param[1-p] = l->param[1-p] + 168 ratio * (r->param[1-p] - l->param[1-p]); 169 } else { 170 n->param[1-p] = l->param[1-p]; 171 } 172} 173 174int 175Subdivider::arc_split( Arc_ptr jarc, int param, REAL value, int dir ) 176{ 177 int maxvertex = jarc->pwlArc->npts; 178 Arc_ptr jarc1; 179 TrimVertex* v = jarc->pwlArc->pts; 180 181 int loc[3]; 182 switch( pwlarc_intersect( jarc->pwlArc, param, value, dir, loc ) ) { 183 184 // When the parameter value lands on a vertex, life is sweet 185 case INTERSECT_VERTEX: { 186 jarc1 = new(arcpool) Arc( jarc, new( pwlarcpool) PwlArc( maxvertex-loc[1], &v[loc[1]] ) ); 187 jarc->pwlArc->npts = loc[1] + 1; 188 jarc1->next = jarc->next; 189 jarc1->next->prev = jarc1; 190 jarc->next = jarc1; 191 jarc1->prev = jarc; 192 assert(jarc->check() != 0); 193 return 2; 194 } 195 196 // When the parameter value intersects an edge, we have to 197 // interpolate a new vertex. There are special cases 198 // if the new vertex is adjacent to one or both of the 199 // endpoints of the arc. 200 case INTERSECT_EDGE: { 201 int i, j; 202 if( dir == 0 ) { 203 i = loc[0]; 204 j = loc[2]; 205 } else { 206 i = loc[2]; 207 j = loc[0]; 208 } 209 210#ifndef NOTDEF 211 // The split is between vertices at index j and i, in that 212 // order (j < i) 213 214 // JEB: This code is my idea of how to do the split without 215 // increasing the number of links. I'm doing this so that 216 // the is_rect routine can recognize rectangles created by 217 // subdivision. In exchange for simplifying the curve list, 218 // however, it costs in allocated space and vertex copies. 219 220 TrimVertex *newjunk = trimvertexpool.get(maxvertex -i+1 /*-j*/); 221 int k; 222 for(k=0; k<maxvertex-i; k++) 223 { 224 newjunk[k+1] = v[i+k]; 225 newjunk[k+1].nuid = jarc->nuid; 226 } 227 228 TrimVertex *vcopy = trimvertexpool.get(maxvertex); 229 for(k=0; k<maxvertex; k++) 230 { 231 vcopy[k].param[0] = v[k].param[0]; 232 vcopy[k].param[1] = v[k].param[1]; 233 } 234 jarc->pwlArc->pts=vcopy; 235 236 v[i].nuid = jarc->nuid; 237 v[j].nuid = jarc->nuid; 238 vert_interp( &newjunk[0], &v[loc[0]], &v[loc[2]], param, value ); 239 240 if( showingDegenerate() ) 241 backend.triangle( &v[i], &newjunk[0], &v[j] ); 242 243 vcopy[j+1].param[0]=newjunk[0].param[0]; 244 vcopy[j+1].param[1]=newjunk[0].param[1]; 245 246 247 jarc1 = new(arcpool) Arc( jarc, 248 new(pwlarcpool) PwlArc(maxvertex-i+1 , newjunk ) ); 249 250 jarc->pwlArc->npts = j+2; 251 jarc1->next = jarc->next; 252 jarc1->next->prev = jarc1; 253 jarc->next = jarc1; 254 jarc1->prev = jarc; 255 assert(jarc->check() != 0); 256 257 return 2; 258#endif //not NOTDEF 259 // JEB: This is the original version: 260#ifdef NOTDEF 261 Arc_ptr jarc2, jarc3; 262 263 TrimVertex *newjunk = trimvertexpool.get(3); 264 v[i].nuid = jarc->nuid; 265 v[j].nuid = jarc->nuid; 266 newjunk[0] = v[j]; 267 newjunk[2] = v[i]; 268 vert_interp( &newjunk[1], &v[loc[0]], &v[loc[2]], param, value ); 269 270 if( showingDegenerate() ) 271 backend.triangle( &newjunk[2], &newjunk[1], &newjunk[0] ); 272 273 // New vertex adjacent to both endpoints 274 if (maxvertex == 2) { 275 jarc1 = new(arcpool) Arc( jarc, new(pwlarcpool) PwlArc( 2, newjunk+1 ) ); 276 jarc->pwlArc->npts = 2; 277 jarc->pwlArc->pts = newjunk; 278 jarc1->next = jarc->next; 279 jarc1->next->prev = jarc1; 280 jarc->next = jarc1; 281 jarc1->prev = jarc; 282 assert(jarc->check() != 0); 283 284 return 2; 285 286 // New vertex adjacent to ending point of arc 287 } else if (maxvertex - j == 2) { 288 jarc1 = new(arcpool) Arc( jarc, new(pwlarcpool) PwlArc( 2, newjunk ) ); 289 jarc2 = new(arcpool) Arc( jarc, new(pwlarcpool) PwlArc( 2, newjunk+1 ) ); 290 jarc->pwlArc->npts = maxvertex-1; 291 jarc2->next = jarc->next; 292 jarc2->next->prev = jarc2; 293 jarc->next = jarc1; 294 jarc1->prev = jarc; 295 jarc1->next = jarc2; 296 jarc2->prev = jarc1; 297 assert(jarc->check() != 0); 298 return 31; 299 300 // New vertex adjacent to starting point of arc 301 } else if (i == 1) { 302 jarc1 = new(arcpool) Arc( jarc, new(pwlarcpool) PwlArc( 2, newjunk+1 ) ); 303 jarc2 = new(arcpool) Arc( jarc, 304 new(pwlarcpool) PwlArc( maxvertex-1, &jarc->pwlArc->pts[1] ) ); 305 jarc->pwlArc->npts = 2; 306 jarc->pwlArc->pts = newjunk; 307 jarc2->next = jarc->next; 308 jarc2->next->prev = jarc2; 309 jarc->next = jarc1; 310 jarc1->prev = jarc; 311 jarc1->next = jarc2; 312 jarc2->prev = jarc1; 313 assert(jarc->check() != 0); 314 return 32; 315 316 // It's somewhere in the middle 317 } else { 318 jarc1 = new(arcpool) Arc( jarc, new(pwlarcpool) PwlArc( 2, newjunk ) ); 319 jarc2 = new(arcpool) Arc( jarc, new(pwlarcpool) PwlArc( 2, newjunk+1 ) ); 320 jarc3 = new(arcpool) Arc( jarc, new(pwlarcpool) PwlArc( maxvertex-i, v+i ) ); 321 jarc->pwlArc->npts = j + 1; 322 jarc3->next = jarc->next; 323 jarc3->next->prev = jarc3; 324 jarc->next = jarc1; 325 jarc1->prev = jarc; 326 jarc1->next = jarc2; 327 jarc2->prev = jarc1; 328 jarc2->next = jarc3; 329 jarc3->prev = jarc2; 330 assert(jarc->check() != 0); 331 return 4; 332 } 333#endif // NOTDEF 334 } 335 default: 336 return -1; //picked -1 since it's not used 337 } 338} 339 340/*---------------------------------------------------------------------------- 341 * pwlarc_intersect - find intersection of pwlArc and isoparametric line 342 *---------------------------------------------------------------------------- 343 */ 344 345static enum i_result 346pwlarc_intersect( 347 PwlArc *pwlArc, 348 int param, 349 REAL value, 350 int dir, 351 int loc[3] ) 352{ 353 assert( pwlArc->npts > 0 ); 354 355 if( dir ) { 356 TrimVertex *v = pwlArc->pts; 357 int imin = 0; 358 int imax = pwlArc->npts - 1; 359 assert( value > v[imin].param[param] ); 360 assert( value < v[imax].param[param] ); 361 while( (imax - imin) > 1 ) { 362 int imid = (imax + imin)/2; 363 if( v[imid].param[param] > value ) 364 imax = imid; 365 else if( v[imid].param[param] < value ) 366 imin = imid; 367 else { 368 loc[1] = imid; 369 return INTERSECT_VERTEX; 370 } 371 } 372 loc[0] = imin; 373 loc[2] = imax; 374 return INTERSECT_EDGE; 375 } else { 376 TrimVertex *v = pwlArc->pts; 377 int imax = 0; 378 int imin = pwlArc->npts - 1; 379 assert( value > v[imin].param[param] ); 380 assert( value < v[imax].param[param] ); 381 while( (imin - imax) > 1 ) { 382 int imid = (imax + imin)/2; 383 if( v[imid].param[param] > value ) 384 imax = imid; 385 else if( v[imid].param[param] < value ) 386 imin = imid; 387 else { 388 loc[1] = imid; 389 return INTERSECT_VERTEX; 390 } 391 } 392 loc[0] = imin; 393 loc[2] = imax; 394 return INTERSECT_EDGE; 395 } 396} 397 398/*---------------------------------------------------------------------------- 399 * arc_classify - determine which side of a line a jarc lies 400 *---------------------------------------------------------------------------- 401 */ 402 403#ifndef NDEBUG // for asserts only 404static int 405arc_classify( Arc_ptr jarc, int param, REAL value ) 406{ 407 REAL tdiff, hdiff; 408 if( param == 0 ) { 409 tdiff = jarc->tail()[0] - value; 410 hdiff = jarc->head()[0] - value; 411 } else { 412 tdiff = jarc->tail()[1] - value; 413 hdiff = jarc->head()[1] - value; 414 } 415 416 if( tdiff > 0.0 ) { 417 if( hdiff > 0.0 ) { 418 return 0x11; 419 } else if( hdiff == 0.0 ) { 420 return 0x12; 421 } else { 422 return 0x10; 423 } 424 } else if( tdiff == 0.0 ) { 425 if( hdiff > 0.0 ) { 426 return 0x21; 427 } else if( hdiff == 0.0 ) { 428 return 0x22; 429 } else { 430 return 0x20; 431 } 432 } else { 433 if( hdiff > 0.0 ) { 434 return 0x01; 435 } else if( hdiff == 0.0 ) { 436 return 0x02; 437 } else { 438 return 0; 439 } 440 } 441} 442#endif 443 444void 445Subdivider::classify_tailonleft_s( Bin& bin, Bin& in, Bin& out, REAL val ) 446{ 447 /* tail at left, head on line */ 448 Arc_ptr j; 449 450 while( (j = bin.removearc()) != NULL ) { 451 assert( arc_classify( j, 0, val ) == 0x02 ); 452 j->clearitail(); 453 454 REAL diff = j->next->head()[0] - val; 455 if( diff > 0.0 ) { 456 in.addarc( j ); 457 } else if( diff < 0.0 ) { 458 if( ccwTurn_sl( j, j->next ) ) 459 out.addarc( j ); 460 else 461 in.addarc( j ); 462 } else { 463 if( j->next->tail()[1] > j->next->head()[1] ) 464 in.addarc(j); 465 else 466 out.addarc(j); 467 } 468 } 469} 470 471void 472Subdivider::classify_tailonleft_t( Bin& bin, Bin& in, Bin& out, REAL val ) 473{ 474 /* tail at left, head on line */ 475 Arc_ptr j; 476 477 while( (j = bin.removearc()) != NULL ) { 478 assert( arc_classify( j, 1, val ) == 0x02 ); 479 j->clearitail(); 480 481 REAL diff = j->next->head()[1] - val; 482 if( diff > 0.0 ) { 483 in.addarc( j ); 484 } else if( diff < 0.0 ) { 485 if( ccwTurn_tl( j, j->next ) ) 486 out.addarc( j ); 487 else 488 in.addarc( j ); 489 } else { 490 if (j->next->tail()[0] > j->next->head()[0] ) 491 out.addarc( j ); 492 else 493 in.addarc( j ); 494 } 495 } 496} 497 498void 499Subdivider::classify_headonleft_s( Bin& bin, Bin& in, Bin& out, REAL val ) 500{ 501 /* tail on line, head at left */ 502 Arc_ptr j; 503 504 while( (j = bin.removearc()) != NULL ) { 505 assert( arc_classify( j, 0, val ) == 0x20 ); 506 507 j->setitail(); 508 509 REAL diff = j->prev->tail()[0] - val; 510 if( diff > 0.0 ) { 511 out.addarc( j ); 512 } else if( diff < 0.0 ) { 513 if( ccwTurn_sl( j->prev, j ) ) 514 out.addarc( j ); 515 else 516 in.addarc( j ); 517 } else { 518 if( j->prev->tail()[1] > j->prev->head()[1] ) 519 in.addarc( j ); 520 else 521 out.addarc( j ); 522 } 523 } 524} 525 526void 527Subdivider::classify_headonleft_t( Bin& bin, Bin& in, Bin& out, REAL val ) 528{ 529 /* tail on line, head at left */ 530 Arc_ptr j; 531 532 while( (j = bin.removearc()) != NULL ) { 533 assert( arc_classify( j, 1, val ) == 0x20 ); 534 j->setitail(); 535 536 REAL diff = j->prev->tail()[1] - val; 537 if( diff > 0.0 ) { 538 out.addarc( j ); 539 } else if( diff < 0.0 ) { 540 if( ccwTurn_tl( j->prev, j ) ) 541 out.addarc( j ); 542 else 543 in.addarc( j ); 544 } else { 545 if( j->prev->tail()[0] > j->prev->head()[0] ) 546 out.addarc( j ); 547 else 548 in.addarc( j ); 549 } 550 } 551} 552 553 554void 555Subdivider::classify_tailonright_s( Bin& bin, Bin& in, Bin& out, REAL val ) 556{ 557 /* tail at right, head on line */ 558 Arc_ptr j; 559 560 while( (j = bin.removearc()) != NULL ) { 561 assert( arc_classify( j, 0, val ) == 0x12); 562 563 j->clearitail(); 564 565 REAL diff = j->next->head()[0] - val; 566 if( diff > 0.0 ) { 567 if( ccwTurn_sr( j, j->next ) ) 568 out.addarc( j ); 569 else 570 in.addarc( j ); 571 } else if( diff < 0.0 ) { 572 in.addarc( j ); 573 } else { 574 if( j->next->tail()[1] > j->next->head()[1] ) 575 out.addarc( j ); 576 else 577 in.addarc( j ); 578 } 579 } 580} 581 582void 583Subdivider::classify_tailonright_t( Bin& bin, Bin& in, Bin& out, REAL val ) 584{ 585 /* tail at right, head on line */ 586 Arc_ptr j; 587 588 while( (j = bin.removearc()) != NULL ) { 589 assert( arc_classify( j, 1, val ) == 0x12); 590 591 j->clearitail(); 592 593 REAL diff = j->next->head()[1] - val; 594 if( diff > 0.0 ) { 595 if( ccwTurn_tr( j, j->next ) ) 596 out.addarc( j ); 597 else 598 in.addarc( j ); 599 } else if( diff < 0.0 ) { 600 in.addarc( j ); 601 } else { 602 if( j->next->tail()[0] > j->next->head()[0] ) 603 in.addarc( j ); 604 else 605 out.addarc( j ); 606 } 607 } 608} 609 610void 611Subdivider::classify_headonright_s( Bin& bin, Bin& in, Bin& out, REAL val ) 612{ 613 /* tail on line, head at right */ 614 Arc_ptr j; 615 616 while( (j = bin.removearc()) != NULL ) { 617 assert( arc_classify( j, 0, val ) == 0x21 ); 618 619 j->setitail(); 620 621 REAL diff = j->prev->tail()[0] - val; 622 if( diff > 0.0 ) { 623 if( ccwTurn_sr( j->prev, j ) ) 624 out.addarc( j ); 625 else 626 in.addarc( j ); 627 } else if( diff < 0.0 ) { 628 out.addarc( j ); 629 } else { 630 if( j->prev->tail()[1] > j->prev->head()[1] ) 631 out.addarc( j ); 632 else 633 in.addarc( j ); 634 } 635 } 636} 637 638void 639Subdivider::classify_headonright_t( Bin& bin, Bin& in, Bin& out, REAL val ) 640{ 641 /* tail on line, head at right */ 642 Arc_ptr j; 643 644 while( (j = bin.removearc()) != NULL ) { 645 assert( arc_classify( j, 1, val ) == 0x21 ); 646 647 j->setitail(); 648 649 REAL diff = j->prev->tail()[1] - val; 650 if( diff > 0.0 ) { 651 if( ccwTurn_tr( j->prev, j ) ) 652 out.addarc( j ); 653 else 654 in.addarc( j ); 655 } else if( diff < 0.0 ) { 656 out.addarc( j ); 657 } else { 658 if( j->prev->tail()[0] > j->prev->head()[0] ) 659 in.addarc( j ); 660 else 661 out.addarc( j ); 662 } 663 } 664} 665 666