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 * subdivider.cxx 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 "bezierarc.h" 46 #include "bin.h" 47 #include "renderhints.h" 48 #include "backend.h" 49 #include "mapdesc.h" 50 #include "quilt.h" 51 #include "patchlist.h" 52 #include "patch.h" 53 #include "nurbsconsts.h" 54 #include "trimvertpool.h" 55 #include "simplemath.h" 56 57 #include "polyUtil.h" //for function area() 58 59 //#define PARTITION_TEST 60 #ifdef PARTITION_TEST 61 #include "partitionY.h" 62 #include "monoTriangulation.h" 63 #include "dataTransform.h" 64 #include "monoChain.h" 65 66 #endif 67 68 69 #define OPTIMIZE_UNTRIMED_CASE 70 71 72 Bin* 73 Subdivider::makePatchBoundary( const REAL *from, const REAL *to ) 74 { 75 Bin* ret = new Bin(); 76 REAL smin = from[0]; 77 REAL smax = to[0]; 78 REAL tmin = from[1]; 79 REAL tmax = to[1]; 80 81 pjarc = 0; 82 83 Arc_ptr jarc = new(arcpool) Arc( arc_bottom, 0 ); 84 arctessellator.bezier( jarc, smin, smax, tmin, tmin ); 85 ret->addarc( jarc ); 86 pjarc = jarc->append( pjarc ); 87 88 jarc = new(arcpool) Arc( arc_right, 0 ); 89 arctessellator.bezier( jarc, smax, smax, tmin, tmax ); 90 ret->addarc( jarc ); 91 pjarc = jarc->append( pjarc ); 92 93 jarc = new(arcpool) Arc( arc_top, 0 ); 94 arctessellator.bezier( jarc, smax, smin, tmax, tmax ); 95 ret->addarc( jarc ); 96 pjarc = jarc->append( pjarc ); 97 98 jarc = new(arcpool) Arc( arc_left, 0 ); 99 arctessellator.bezier( jarc, smin, smin, tmax, tmin ); 100 ret->addarc( jarc ); 101 jarc->append( pjarc ); 102 103 assert( jarc->check() != 0 ); 104 return ret; 105 } 106 107 /*--------------------------------------------------------------------------- 108 * Subdivider - construct a subdivider 109 *--------------------------------------------------------------------------- 110 */ 111 112 Subdivider::Subdivider( Renderhints& r, Backend& b ) 113 : slicer( b ), 114 arctessellator( trimvertexpool, pwlarcpool ), 115 arcpool( sizeof( Arc), 1, "arcpool" ), 116 bezierarcpool( sizeof( BezierArc ), 1, "Bezarcpool" ), 117 pwlarcpool( sizeof( PwlArc ), 1, "Pwlarcpool" ), 118 renderhints( r ), 119 backend( b ) 120 { 121 } 122 123 void 124 Subdivider::setJumpbuffer( JumpBuffer *j ) 125 { 126 jumpbuffer = j; 127 } 128 129 /*--------------------------------------------------------------------------- 130 * clear - reset all state after possible error condition 131 *--------------------------------------------------------------------------- 132 */ 133 134 void 135 Subdivider::clear( void ) 136 { 137 trimvertexpool.clear(); 138 arcpool.clear(); 139 pwlarcpool.clear(); 140 bezierarcpool.clear(); 141 } 142 143 /*--------------------------------------------------------------------------- 144 * ~Subdivider - destroy a subdivider 145 *--------------------------------------------------------------------------- 146 */ 147 148 Subdivider::~Subdivider( void ) 149 { 150 } 151 152 /*--------------------------------------------------------------------------- 153 * addArc - add a bezier arc to a trim loop and to a bin 154 *--------------------------------------------------------------------------- 155 */ 156 void 157 Subdivider::addArc( REAL *cpts, Quilt *quilt, long _nuid ) 158 { 159 BezierArc *bezierArc = new(bezierarcpool) BezierArc; 160 Arc *jarc = new(arcpool) Arc( arc_none, _nuid ); 161 jarc->pwlArc = 0; 162 jarc->bezierArc = bezierArc; 163 bezierArc->order = quilt->qspec->order; 164 bezierArc->stride = quilt->qspec->stride; 165 bezierArc->mapdesc = quilt->mapdesc; 166 bezierArc->cpts = cpts; 167 initialbin.addarc( jarc ); 168 pjarc = jarc->append( pjarc ); 169 } 170 171 /*--------------------------------------------------------------------------- 172 * addArc - add a pwl arc to a trim loop and to a bin 173 *--------------------------------------------------------------------------- 174 */ 175 176 void 177 Subdivider::addArc( int npts, TrimVertex *pts, long _nuid ) 178 { 179 Arc *jarc = new(arcpool) Arc( arc_none, _nuid ); 180 jarc->pwlArc = new(pwlarcpool) PwlArc( npts, pts ); 181 initialbin.addarc( jarc ); 182 pjarc = jarc->append( pjarc ); 183 } 184 185 void 186 Subdivider::beginQuilts( void ) 187 { 188 qlist = 0; 189 } 190 191 void 192 Subdivider::addQuilt( Quilt *quilt ) 193 { 194 quilt->next = qlist; 195 qlist = quilt; 196 } 197 198 /*--------------------------------------------------------------------------- 199 * drawSurfaces - main entry point for surface tessellation 200 *--------------------------------------------------------------------------- 201 */ 202 203 void 204 Subdivider::drawSurfaces( long nuid ) 205 { 206 renderhints.init( ); 207 208 if (qlist == NULL) 209 { 210 //initialbin could be nonempty due to some errors 211 freejarcs(initialbin); 212 return; 213 } 214 215 for( Quilt *q = qlist; q; q = q->next ) { 216 if( q->isCulled( ) == CULL_TRIVIAL_REJECT ) { 217 freejarcs( initialbin ); 218 return; 219 } 220 } 221 222 223 REAL from[2], to[2]; 224 qlist->getRange( from, to, spbrkpts, tpbrkpts ); 225 #ifdef OPTIMIZE_UNTRIMED_CASE 226 //perform optimization only when the samplng method is 227 //DOMAIN_DISTANCE and the display methdo is either 228 //fill or outline_polygon. 229 int optimize = (is_domain_distance_sampling && (renderhints.display_method != N_OUTLINE_PATCH)); 230 #endif 231 232 if( ! initialbin.isnonempty() ) { 233 #ifdef OPTIMIZE_UNTRIMED_CASE 234 if(! optimize ) 235 { 236 237 makeBorderTrim( from, to ); 238 } 239 #else 240 makeBorderTrim( from, to ); 241 #endif 242 } else { 243 REAL rate[2]; 244 qlist->findRates( spbrkpts, tpbrkpts, rate ); 245 246 if( decompose( initialbin, min(rate[0], rate[1]) ) ) 247 mylongjmp( jumpbuffer, 31 ); 248 } 249 250 backend.bgnsurf( renderhints.wiretris, renderhints.wirequads, nuid ); 251 252 #ifdef PARTITION_TEST 253 if( initialbin.isnonempty() && spbrkpts.end-2 == spbrkpts.start && 254 tpbrkpts.end-2 == tpbrkpts.start) 255 { 256 for(int i=spbrkpts.start; i<spbrkpts.end-1; i++){ 257 for(int j=tpbrkpts.start; j<tpbrkpts.end-1; j++){ 258 Real pta[2], ptb[2]; 259 pta[0] = spbrkpts.pts[i]; 260 ptb[0] = spbrkpts.pts[i+1]; 261 pta[1] = tpbrkpts.pts[j]; 262 ptb[1] = tpbrkpts.pts[j+1]; 263 qlist->downloadAll(pta, ptb, backend); 264 265 directedLine *poly; 266 267 { 268 269 poly = bin_to_DLineLoops(initialbin); 270 271 poly=poly->deleteDegenerateLinesAllPolygons(); 272 273 sampledLine* retSampledLines; 274 //printf("before MC_partition\n"); 275 poly = MC_partitionY(poly, &retSampledLines); 276 //printf("after MC_partition\n"); 277 278 } 279 280 281 { 282 primStream pStream(5000,5000); 283 directedLine* temp; 284 285 for(temp=poly; temp != NULL; temp=temp->getNextPolygon()) 286 287 monoTriangulation(temp, &pStream); 288 289 slicer.evalStream(&pStream); 290 291 } 292 //need to clean up space 293 } 294 } 295 freejarcs( initialbin ); 296 backend.endsurf(); 297 return; 298 299 /* 300 printf("num_polygons=%i\n", poly->numPolygons()); 301 printf("num_edges=%i\n", poly->numEdgesAllPolygons()); 302 poly->writeAllPolygons("zloutputFile"); 303 return; 304 { 305 primStream pStream(20,20); 306 for(directedLine* tempD = poly; tempD != NULL; tempD = tempD->getNextPolygon()) 307 monoTriangulation(tempD, &pStream); 308 } 309 return; 310 */ 311 } 312 #endif //PARTITION_TEST 313 314 315 #ifdef OPTIMIZE_UNTRIMED_CASE 316 if( (!initialbin.isnonempty()) && optimize ) 317 { 318 int i,j; 319 int num_u_steps; 320 int num_v_steps; 321 for(i=spbrkpts.start; i<spbrkpts.end-1; i++){ 322 for(j=tpbrkpts.start; j<tpbrkpts.end-1; j++){ 323 Real pta[2], ptb[2]; 324 pta[0] = spbrkpts.pts[i]; 325 ptb[0] = spbrkpts.pts[i+1]; 326 pta[1] = tpbrkpts.pts[j]; 327 ptb[1] = tpbrkpts.pts[j+1]; 328 qlist->downloadAll(pta, ptb, backend); 329 330 num_u_steps = (int) (domain_distance_u_rate * (ptb[0]-pta[0])); 331 num_v_steps = (int) (domain_distance_v_rate * (ptb[1]-pta[1])); 332 333 if(num_u_steps <= 0) num_u_steps = 1; 334 if(num_v_steps <= 0) num_v_steps = 1; 335 336 backend.surfgrid(pta[0], ptb[0], num_u_steps, 337 ptb[1], pta[1], num_v_steps); 338 backend.surfmesh(0,0,num_u_steps,num_v_steps); 339 340 341 342 continue; 343 /* the following is left for reference purpose, don't delete 344 { 345 Bin* tempSource; 346 Patchlist patchlist(qlist, pta, ptb); 347 patchlist.getstepsize(); 348 349 tempSource=makePatchBoundary(pta, ptb); 350 351 tessellation(*tempSource, patchlist); 352 353 render(*tempSource); 354 delete tempSource; 355 } 356 */ 357 } 358 } 359 } 360 else 361 subdivideInS( initialbin ); 362 #else 363 364 subdivideInS( initialbin ); 365 #endif 366 367 backend.endsurf(); 368 369 } 370 371 void 372 Subdivider::subdivideInS( Bin& source ) 373 { 374 if( renderhints.display_method == N_OUTLINE_PARAM ) { 375 outline( source ); 376 freejarcs( source ); 377 } else { 378 setArcTypeBezier(); 379 setNonDegenerate(); 380 splitInS( source, spbrkpts.start, spbrkpts.end ); 381 } 382 } 383 384 385 /*--------------------------------------------------------------------------- 386 * splitInS - split a patch and a bin by an isoparametric line 387 *--------------------------------------------------------------------------- 388 */ 389 390 void 391 Subdivider::splitInS( Bin& source, int start, int end ) 392 { 393 if( source.isnonempty() ) { 394 if( start != end ) { 395 int i = start + (end - start) / 2; 396 Bin left, right; 397 split( source, left, right, 0, spbrkpts.pts[i] ); 398 splitInS( left, start, i ); 399 splitInS( right, i+1, end ); 400 } else { 401 if( start == spbrkpts.start || start == spbrkpts.end ) { 402 freejarcs( source ); 403 } else if( renderhints.display_method == N_OUTLINE_PARAM_S ) { 404 outline( source ); 405 freejarcs( source ); 406 } else { 407 setArcTypeBezier(); 408 setNonDegenerate(); 409 s_index = start; 410 splitInT( source, tpbrkpts.start, tpbrkpts.end ); 411 } 412 } 413 } 414 } 415 416 /*--------------------------------------------------------------------------- 417 * splitInT - split a patch and a bin by an isoparametric line 418 *--------------------------------------------------------------------------- 419 */ 420 421 void 422 Subdivider::splitInT( Bin& source, int start, int end ) 423 { 424 if( source.isnonempty() ) { 425 if( start != end ) { 426 int i = start + (end - start) / 2; 427 Bin left, right; 428 split( source, left, right, 1, tpbrkpts.pts[i] ); 429 splitInT( left, start, i ); 430 splitInT( right, i+1, end ); 431 } else { 432 if( start == tpbrkpts.start || start == tpbrkpts.end ) { 433 freejarcs( source ); 434 } else if( renderhints.display_method == N_OUTLINE_PARAM_ST ) { 435 outline( source ); 436 freejarcs( source ); 437 } else { 438 t_index = start; 439 setArcTypeBezier(); 440 setDegenerate(); 441 442 REAL pta[2], ptb[2]; 443 pta[0] = spbrkpts.pts[s_index-1]; 444 pta[1] = tpbrkpts.pts[t_index-1]; 445 446 ptb[0] = spbrkpts.pts[s_index]; 447 ptb[1] = tpbrkpts.pts[t_index]; 448 qlist->downloadAll( pta, ptb, backend ); 449 450 Patchlist patchlist( qlist, pta, ptb ); 451 /* 452 printf("-------samplingSplit-----\n"); 453 source.show("samplingSplit source"); 454 */ 455 samplingSplit( source, patchlist, renderhints.maxsubdivisions, 0 ); 456 setNonDegenerate(); 457 setArcTypeBezier(); 458 } 459 } 460 } 461 } 462 463 /*-------------------------------------------------------------------------- 464 * samplingSplit - recursively subdivide patch, cull check each subpatch 465 *-------------------------------------------------------------------------- 466 */ 467 468 void 469 Subdivider::samplingSplit( 470 Bin& source, 471 Patchlist& patchlist, 472 int subdivisions, 473 int param ) 474 { 475 if( ! source.isnonempty() ) return; 476 477 if( patchlist.cullCheck() == CULL_TRIVIAL_REJECT ) { 478 freejarcs( source ); 479 return; 480 } 481 482 patchlist.getstepsize(); 483 484 if( renderhints.display_method == N_OUTLINE_PATCH ) { 485 tessellation( source, patchlist ); 486 outline( source ); 487 freejarcs( source ); 488 return; 489 } 490 491 //patchlist.clamp(); 492 493 tessellation( source, patchlist ); 494 495 if( patchlist.needsSamplingSubdivision() && (subdivisions > 0) ) { 496 if( ! patchlist.needsSubdivision( 0 ) ) 497 param = 1; 498 else if( ! patchlist.needsSubdivision( 1 ) ) 499 param = 0; 500 else 501 param = 1 - param; 502 503 Bin left, right; 504 REAL mid = ( patchlist.pspec[param].range[0] + 505 patchlist.pspec[param].range[1] ) * 0.5; 506 split( source, left, right, param, mid ); 507 Patchlist subpatchlist( patchlist, param, mid ); 508 samplingSplit( left, subpatchlist, subdivisions-1, param ); 509 samplingSplit( right, patchlist, subdivisions-1, param ); 510 } else { 511 setArcTypePwl(); 512 setDegenerate(); 513 nonSamplingSplit( source, patchlist, subdivisions, param ); 514 setDegenerate(); 515 setArcTypeBezier(); 516 } 517 } 518 519 void 520 Subdivider::nonSamplingSplit( 521 Bin& source, 522 Patchlist& patchlist, 523 int subdivisions, 524 int param ) 525 { 526 if( patchlist.needsNonSamplingSubdivision() && (subdivisions > 0) ) { 527 param = 1 - param; 528 529 Bin left, right; 530 REAL mid = ( patchlist.pspec[param].range[0] + 531 patchlist.pspec[param].range[1] ) * 0.5; 532 split( source, left, right, param, mid ); 533 Patchlist subpatchlist( patchlist, param, mid ); 534 if( left.isnonempty() ) { 535 if( subpatchlist.cullCheck() == CULL_TRIVIAL_REJECT ) 536 freejarcs( left ); 537 else 538 nonSamplingSplit( left, subpatchlist, subdivisions-1, param ); 539 } 540 if( right.isnonempty() ) { 541 if( patchlist.cullCheck() == CULL_TRIVIAL_REJECT ) 542 freejarcs( right ); 543 else 544 nonSamplingSplit( right, patchlist, subdivisions-1, param ); 545 } 546 547 } else { 548 // make bbox calls 549 patchlist.bbox(); 550 backend.patch( patchlist.pspec[0].range[0], patchlist.pspec[0].range[1], 551 patchlist.pspec[1].range[0], patchlist.pspec[1].range[1] ); 552 553 if( renderhints.display_method == N_OUTLINE_SUBDIV ) { 554 outline( source ); 555 freejarcs( source ); 556 } else { 557 setArcTypePwl(); 558 setDegenerate(); 559 findIrregularS( source ); 560 monosplitInS( source, smbrkpts.start, smbrkpts.end ); 561 } 562 } 563 } 564 565 /*-------------------------------------------------------------------------- 566 * tessellation - set tessellation of interior and boundary of patch 567 *-------------------------------------------------------------------------- 568 */ 569 570 void 571 Subdivider::tessellation( Bin& bin, Patchlist &patchlist ) 572 { 573 // tessellate unsampled trim curves 574 tessellate( bin, patchlist.pspec[1].sidestep[1], patchlist.pspec[0].sidestep[1], 575 patchlist.pspec[1].sidestep[0], patchlist.pspec[0].sidestep[0] ); 576 577 // set interior sampling rates 578 slicer.setstriptessellation( patchlist.pspec[0].stepsize, patchlist.pspec[1].stepsize ); 579 580 //added by zl: set the order which will be used in slicer.c++ 581 slicer.set_ulinear( (patchlist.get_uorder() == 2)); 582 slicer.set_vlinear( (patchlist.get_vorder() == 2)); 583 584 // set boundary sampling rates 585 stepsizes[0] = patchlist.pspec[1].stepsize; 586 stepsizes[1] = patchlist.pspec[0].stepsize; 587 stepsizes[2] = patchlist.pspec[1].stepsize; 588 stepsizes[3] = patchlist.pspec[0].stepsize; 589 } 590 591 /*--------------------------------------------------------------------------- 592 * monosplitInS - split a patch and a bin by an isoparametric line 593 *--------------------------------------------------------------------------- 594 */ 595 596 void 597 Subdivider::monosplitInS( Bin& source, int start, int end ) 598 { 599 if( source.isnonempty() ) { 600 if( start != end ) { 601 int i = start + (end - start) / 2; 602 Bin left, right; 603 split( source, left, right, 0, smbrkpts.pts[i] ); 604 monosplitInS( left, start, i ); 605 monosplitInS( right, i+1, end ); 606 } else { 607 if( renderhints.display_method == N_OUTLINE_SUBDIV_S ) { 608 outline( source ); 609 freejarcs( source ); 610 } else { 611 setArcTypePwl(); 612 setDegenerate(); 613 findIrregularT( source ); 614 monosplitInT( source, tmbrkpts.start, tmbrkpts.end ); 615 } 616 } 617 } 618 } 619 620 /*--------------------------------------------------------------------------- 621 * monosplitInT - split a patch and a bin by an isoparametric line 622 *--------------------------------------------------------------------------- 623 */ 624 625 void 626 Subdivider::monosplitInT( Bin& source, int start, int end ) 627 { 628 if( source.isnonempty() ) { 629 if( start != end ) { 630 int i = start + (end - start) / 2; 631 Bin left, right; 632 split( source, left, right, 1, tmbrkpts.pts[i] ); 633 monosplitInT( left, start, i ); 634 monosplitInT( right, i+1, end ); 635 } else { 636 if( renderhints.display_method == N_OUTLINE_SUBDIV_ST ) { 637 outline( source ); 638 freejarcs( source ); 639 } else { 640 /* 641 printf("*******render\n"); 642 source.show("source\n"); 643 */ 644 render( source ); 645 freejarcs( source ); 646 } 647 } 648 } 649 } 650 651 652 /*---------------------------------------------------------------------------- 653 * findIrregularS - determine points of non-monotonicity is s direction 654 *---------------------------------------------------------------------------- 655 */ 656 657 void 658 Subdivider::findIrregularS( Bin& bin ) 659 { 660 assert( bin.firstarc()->check() != 0 ); 661 662 smbrkpts.grow( bin.numarcs() ); 663 664 for( Arc_ptr jarc=bin.firstarc(); jarc; jarc=bin.nextarc() ) { 665 REAL *a = jarc->prev->tail(); 666 REAL *b = jarc->tail(); 667 REAL *c = jarc->head(); 668 669 if( b[1] == a[1] && b[1] == c[1] ) continue; 670 671 //corrected code 672 if((b[1]<=a[1] && b[1] <= c[1]) || 673 (b[1]>=a[1] && b[1] >= c[1])) 674 { 675 //each arc (jarc, jarc->prev, jarc->next) is a 676 //monotone arc consisting of multiple line segements. 677 //it may happen that jarc->prev and jarc->next are the same, 678 //that is, jarc->prev and jarc form a closed loop. 679 //In such case, a and c will be the same. 680 if(a[0]==c[0] && a[1] == c[1]) 681 { 682 if(jarc->pwlArc->npts >2) 683 { 684 c = jarc->pwlArc->pts[jarc->pwlArc->npts-2].param; 685 } 686 else 687 { 688 assert(jarc->prev->pwlArc->npts>2); 689 a = jarc->prev->pwlArc->pts[jarc->prev->pwlArc->npts-2].param; 690 } 691 692 } 693 if(area(a,b,c) < 0) 694 { 695 smbrkpts.add(b[0]); 696 } 697 698 } 699 700 /* old code, 701 if( b[1] <= a[1] && b[1] <= c[1] ) { 702 if( ! ccwTurn_tr( jarc->prev, jarc ) ) 703 smbrkpts.add( b[0] ); 704 } else if( b[1] >= a[1] && b[1] >= c[1] ) { 705 if( ! ccwTurn_tl( jarc->prev, jarc ) ) 706 smbrkpts.add( b[0] ); 707 } 708 */ 709 710 } 711 712 smbrkpts.filter(); 713 } 714 715 /*---------------------------------------------------------------------------- 716 * findIrregularT - determine points of non-monotonicity in t direction 717 * where one arc is parallel to the s axis. 718 *---------------------------------------------------------------------------- 719 */ 720 721 void 722 Subdivider::findIrregularT( Bin& bin ) 723 { 724 assert( bin.firstarc()->check() != 0 ); 725 726 tmbrkpts.grow( bin.numarcs() ); 727 728 for( Arc_ptr jarc=bin.firstarc(); jarc; jarc=bin.nextarc() ) { 729 REAL *a = jarc->prev->tail(); 730 REAL *b = jarc->tail(); 731 REAL *c = jarc->head(); 732 733 if( b[0] == a[0] && b[0] == c[0] ) continue; 734 735 if( b[0] <= a[0] && b[0] <= c[0] ) { 736 if( a[1] != b[1] && b[1] != c[1] ) continue; 737 if( ! ccwTurn_sr( jarc->prev, jarc ) ) 738 tmbrkpts.add( b[1] ); 739 } else if ( b[0] >= a[0] && b[0] >= c[0] ) { 740 if( a[1] != b[1] && b[1] != c[1] ) continue; 741 if( ! ccwTurn_sl( jarc->prev, jarc ) ) 742 tmbrkpts.add( b[1] ); 743 } 744 } 745 tmbrkpts.filter( ); 746 } 747 748 /*----------------------------------------------------------------------------- 749 * makeBorderTrim - if no user input trimming data then create 750 * a trimming curve around the boundaries of the Quilt. The curve consists of 751 * four Jordan arcs, one for each side of the Quilt, connected, of course, 752 * head to tail. 753 *----------------------------------------------------------------------------- 754 */ 755 756 void 757 Subdivider::makeBorderTrim( const REAL *from, const REAL *to ) 758 { 759 REAL smin = from[0]; 760 REAL smax = to[0]; 761 REAL tmin = from[1]; 762 REAL tmax = to[1]; 763 764 pjarc = 0; 765 766 Arc_ptr jarc = new(arcpool) Arc( arc_bottom, 0 ); 767 arctessellator.bezier( jarc, smin, smax, tmin, tmin ); 768 initialbin.addarc( jarc ); 769 pjarc = jarc->append( pjarc ); 770 771 jarc = new(arcpool) Arc( arc_right, 0 ); 772 arctessellator.bezier( jarc, smax, smax, tmin, tmax ); 773 initialbin.addarc( jarc ); 774 pjarc = jarc->append( pjarc ); 775 776 jarc = new(arcpool) Arc( arc_top, 0 ); 777 arctessellator.bezier( jarc, smax, smin, tmax, tmax ); 778 initialbin.addarc( jarc ); 779 pjarc = jarc->append( pjarc ); 780 781 jarc = new(arcpool) Arc( arc_left, 0 ); 782 arctessellator.bezier( jarc, smin, smin, tmax, tmin ); 783 initialbin.addarc( jarc ); 784 jarc->append( pjarc ); 785 786 assert( jarc->check() != 0 ); 787 } 788 789 /*---------------------------------------------------------------------------- 790 * render - renders all monotone regions in a bin and frees the bin 791 *---------------------------------------------------------------------------- 792 */ 793 794 void 795 Subdivider::render( Bin& bin ) 796 { 797 bin.markall(); 798 799 #ifdef N_ISOLINE_S 800 slicer.setisolines( ( renderhints.display_method == N_ISOLINE_S ) ? 1 : 0 ); 801 #else 802 slicer.setisolines( 0 ); 803 #endif 804 805 for( Arc_ptr jarc=bin.firstarc(); jarc; jarc=bin.nextarc() ) { 806 if( jarc->ismarked() ) { 807 assert( jarc->check( ) != 0 ); 808 Arc_ptr jarchead = jarc; 809 do { 810 jarc->clearmark(); 811 jarc = jarc->next; 812 } while (jarc != jarchead); 813 slicer.slice( jarc ); 814 } 815 } 816 } 817 818 /*--------------------------------------------------------------------------- 819 * outline - render the trimmed patch by outlining the boundary 820 *--------------------------------------------------------------------------- 821 */ 822 823 void 824 Subdivider::outline( Bin& bin ) 825 { 826 bin.markall(); 827 for( Arc_ptr jarc=bin.firstarc(); jarc; jarc=bin.nextarc() ) { 828 if( jarc->ismarked() ) { 829 assert( jarc->check( ) != 0 ); 830 Arc_ptr jarchead = jarc; 831 do { 832 slicer.outline( jarc ); 833 jarc->clearmark(); 834 jarc = jarc->prev; 835 } while (jarc != jarchead); 836 } 837 } 838 } 839 840 /*--------------------------------------------------------------------------- 841 * freejarcs - free all arcs in a bin 842 *--------------------------------------------------------------------------- 843 */ 844 845 void 846 Subdivider::freejarcs( Bin& bin ) 847 { 848 bin.adopt(); /* XXX - should not be necessary */ 849 850 Arc_ptr jarc; 851 while( (jarc = bin.removearc()) != NULL ) { 852 if( jarc->pwlArc ) jarc->pwlArc->deleteMe( pwlarcpool ); jarc->pwlArc = 0; 853 if( jarc->bezierArc) jarc->bezierArc->deleteMe( bezierarcpool ); jarc->bezierArc = 0; 854 jarc->deleteMe( arcpool ); 855 } 856 } 857 858 /*---------------------------------------------------------------------------- 859 * tessellate - tessellate all Bezier arcs in a bin 860 * 1) only accepts linear Bezier arcs as input 861 * 2) the Bezier arcs are stored in the pwlArc structure 862 * 3) only vertical or horizontal lines work 863 * -- should 864 * 1) represent Bezier arcs in BezierArc structure 865 * (this requires a multitude of changes to the code) 866 * 2) accept high degree Bezier arcs (hard) 867 * 3) map the curve onto the surface to determine tessellation 868 * 4) work for curves of arbitrary geometry 869 *---------------------------------------------------------------------------- 870 */ 871 872 873 void 874 Subdivider::tessellate( Bin& bin, REAL rrate, REAL trate, REAL lrate, REAL brate ) 875 { 876 for( Arc_ptr jarc=bin.firstarc(); jarc; jarc=bin.nextarc() ) { 877 if( jarc->isbezier( ) ) { 878 assert( jarc->pwlArc->npts == 2 ); 879 TrimVertex *pts = jarc->pwlArc->pts; 880 REAL s1 = pts[0].param[0]; 881 REAL t1 = pts[0].param[1]; 882 REAL s2 = pts[1].param[0]; 883 REAL t2 = pts[1].param[1]; 884 885 jarc->pwlArc->deleteMe( pwlarcpool ); jarc->pwlArc = 0; 886 887 switch( jarc->getside() ) { 888 case arc_left: 889 assert( s1 == s2 ); 890 arctessellator.pwl_left( jarc, s1, t1, t2, lrate ); 891 break; 892 case arc_right: 893 assert( s1 == s2 ); 894 arctessellator.pwl_right( jarc, s1, t1, t2, rrate ); 895 break; 896 case arc_top: 897 assert( t1 == t2 ); 898 arctessellator.pwl_top( jarc, t1, s1, s2, trate ); 899 break; 900 case arc_bottom: 901 assert( t1 == t2 ); 902 arctessellator.pwl_bottom( jarc, t1, s1, s2, brate ); 903 break; 904 case arc_none: 905 (void) abort(); 906 break; 907 } 908 assert( ! jarc->isbezier() ); 909 assert( jarc->check() != 0 ); 910 } 911 } 912 } 913
Indexes created Thu Jul 23 00:25:05 UTC 2026