src/glu/sgi/libnurbs/internals/subdivider.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  * subdivider.cxx
  37  *
  38  * $Date: 2003/10/15 21:11:13 $ $Revision: 1.2 $
  39  * $Header: /home/krh/git/sync/mesa-cvs-repo/Mesa/src/glu/sgi/libnurbs/internals/subdivider.cc,v 1.2 2003/10/15 21:11:13 brianp Exp $
  40  */
  41
  42 #include "glimports.h"
  43 #include "myassert.h"
  44 #include "mystdio.h"
  45 #include "subdivider.h"
  46 #include "arc.h"
  47 #include "bezierarc.h"
  48 #include "bin.h"
  49 #include "renderhints.h"
  50 #include "backend.h"
  51 #include "mapdesc.h"
  52 #include "quilt.h"
  53 #include "patchlist.h"
  54 #include "patch.h"
  55 #include "nurbsconsts.h"
  56 #include "trimvertpool.h"
  57 #include "simplemath.h"
  58
  59 #include "polyUtil.h" //for function area()
  60
  61 //#define  PARTITION_TEST
  62 #ifdef PARTITION_TEST
  63 #include "partitionY.h"
  64 #include "monoTriangulation.h"
  65 #include "dataTransform.h"
  66 #include "monoChain.h"
  67
  68 #endif
  69
  70
  71 #define OPTIMIZE_UNTRIMED_CASE
  72
  73
  74 Bin*
  75 Subdivider::makePatchBoundary( const REAL *from, const REAL *to )
  76 {
  77     Bin* ret = new Bin();
  78     REAL smin = from[0];
  79     REAL smax = to[0];
  80     REAL tmin = from[1];
  81     REAL tmax = to[1];
  82
  83     pjarc = 0;
  84
  85     Arc_ptr jarc = new(arcpool) Arc( arc_bottom, 0 );
  86     arctessellator.bezier( jarc, smin, smax, tmin, tmin );
  87     ret->addarc( jarc  );
  88     pjarc = jarc->append( pjarc );
  89
  90     jarc = new(arcpool) Arc( arc_right, 0 );
  91     arctessellator.bezier( jarc, smax, smax, tmin, tmax );
  92     ret->addarc( jarc  );
  93     pjarc = jarc->append( pjarc );
  94
  95     jarc = new(arcpool) Arc( arc_top, 0 );
  96     arctessellator.bezier( jarc, smax, smin, tmax, tmax );
  97     ret->addarc( jarc  );
  98     pjarc = jarc->append( pjarc );
  99
 100     jarc = new(arcpool) Arc( arc_left, 0 );
 101     arctessellator.bezier( jarc, smin, smin, tmax, tmin );
 102     ret->addarc( jarc  );
 103     jarc->append( pjarc );
 104
 105     assert( jarc->check() != 0 );
 106     return ret;
 107 }
 108
 109 /*---------------------------------------------------------------------------
 110  * Subdivider - construct a subdivider
 111  *---------------------------------------------------------------------------
 112  */
 113
 114 Subdivider::Subdivider( Renderhints& r, Backend& b )
 115         : slicer( b ),
 116           arctessellator( trimvertexpool, pwlarcpool ),
 117           arcpool( sizeof( Arc), 1, "arcpool" ),
 118           bezierarcpool( sizeof( BezierArc ), 1, "Bezarcpool" ),
 119           pwlarcpool( sizeof( PwlArc ), 1, "Pwlarcpool" ),
 120           renderhints( r ),
 121           backend( b )
 122 {
 123 }
 124
 125 void
 126 Subdivider::setJumpbuffer( JumpBuffer *j )
 127 {
 128     jumpbuffer = j;
 129 }
 130
 131 /*---------------------------------------------------------------------------
 132  * clear - reset all state after possible error condition
 133  *---------------------------------------------------------------------------
 134  */
 135
 136 void
 137 Subdivider::clear( void )
 138 {
 139     trimvertexpool.clear();
 140     arcpool.clear();
 141     pwlarcpool.clear();
 142     bezierarcpool.clear();
 143 }
 144
 145 /*---------------------------------------------------------------------------
 146  * ~Subdivider - destroy a subdivider
 147  *---------------------------------------------------------------------------
 148  */
 149
 150 Subdivider::~Subdivider( void )
 151 {
 152 }
 153
 154 /*---------------------------------------------------------------------------
 155  * addArc - add a bezier arc to a trim loop and to a bin
 156  *---------------------------------------------------------------------------
 157  */
 158 void
 159 Subdivider::addArc( REAL *cpts, Quilt *quilt, long _nuid )
 160 {
 161     BezierArc *bezierArc = new(bezierarcpool) BezierArc;
 162     Arc *jarc           = new(arcpool) Arc( arc_none, _nuid );
 163     jarc->pwlArc        = 0;
 164     jarc->bezierArc     = bezierArc;
 165     bezierArc->order    = quilt->qspec->order;
 166     bezierArc->stride   = quilt->qspec->stride;
 167     bezierArc->mapdesc  = quilt->mapdesc;
 168     bezierArc->cpts     = cpts;
 169     initialbin.addarc( jarc );
 170     pjarc               = jarc->append( pjarc );
 171 }
 172
 173 /*---------------------------------------------------------------------------
 174  * addArc - add a pwl arc to a trim loop and to a bin
 175  *---------------------------------------------------------------------------
 176  */
 177
 178 void
 179 Subdivider::addArc( int npts, TrimVertex *pts, long _nuid )
 180 {
 181     Arc *jarc           = new(arcpool) Arc( arc_none, _nuid );
 182     jarc->pwlArc        = new(pwlarcpool) PwlArc( npts, pts );
 183     initialbin.addarc( jarc  );
 184     pjarc               = jarc->append( pjarc );
 185 }
 186
 187 void
 188 Subdivider::beginQuilts( void )
 189 {
 190     qlist = 0;
 191 }
 192
 193 void
 194 Subdivider::addQuilt( Quilt *quilt )
 195 {
 196     quilt->next = qlist;
 197     qlist = quilt;
 198 }
 199
 200 /*---------------------------------------------------------------------------
 201  * drawSurfaces - main entry point for surface tessellation
 202  *---------------------------------------------------------------------------
 203  */
 204
 205 void
 206 Subdivider::drawSurfaces( long nuid )
 207 {
 208     renderhints.init( );
 209
 210     if (qlist == NULL)
 211       {
 212         //initialbin could be nonempty due to some errors
 213         freejarcs(initialbin);
 214         return;
 215       }
 216
 217     for( Quilt *q = qlist; q; q = q->next ) {
 218         if( q->isCulled( ) == CULL_TRIVIAL_REJECT ) {
 219             freejarcs( initialbin );
 220             return;
 221         }
 222     }
 223
 224
 225     REAL from[2], to[2];
 226     qlist->getRange( from, to, spbrkpts, tpbrkpts );
 227 #ifdef OPTIMIZE_UNTRIMED_CASE
 228     //perform optimization only when the samplng method is
 229     //DOMAIN_DISTANCE and the display methdo is either
 230     //fill or outline_polygon.
 231     int optimize = (is_domain_distance_sampling && (renderhints.display_method != N_OUTLINE_PATCH));
 232 #endif
 233
 234     if( ! initialbin.isnonempty() ) {
 235 #ifdef OPTIMIZE_UNTRIMED_CASE
 236         if(! optimize )
 237           {
 238
 239           makeBorderTrim( from, to );
 240           }
 241 #else
 242         makeBorderTrim( from, to );
 243 #endif
 244     } else {
 245         REAL rate[2];
 246         qlist->findRates( spbrkpts, tpbrkpts, rate );
 247
 248         if( decompose( initialbin, min(rate[0], rate[1]) ) )
 249             mylongjmp( jumpbuffer, 31 );
 250     }
 251
 252     backend.bgnsurf( renderhints.wiretris, renderhints.wirequads, nuid );
 253
 254 #ifdef PARTITION_TEST
 255  if(    initialbin.isnonempty() && spbrkpts.end-2 == spbrkpts.start &&
 256         tpbrkpts.end-2 == tpbrkpts.start)
 257 {
 258     for(int i=spbrkpts.start; i<spbrkpts.end-1; i++){
 259       for(int j=tpbrkpts.start; j<tpbrkpts.end-1; j++){
 260         Real pta[2], ptb[2];
 261         pta[0] = spbrkpts.pts[i];
 262         ptb[0] = spbrkpts.pts[i+1];
 263         pta[1] = tpbrkpts.pts[j];
 264         ptb[1] = tpbrkpts.pts[j+1];
 265         qlist->downloadAll(pta, ptb, backend);
 266
 267         directedLine *poly;
 268
 269           {
 270
 271             poly = bin_to_DLineLoops(initialbin);
 272
 273             poly=poly->deleteDegenerateLinesAllPolygons();
 274
 275     sampledLine* retSampledLines;
 276 //printf("before MC_partition\n");
 277             poly = MC_partitionY(poly, &retSampledLines);
 278 //printf("after MC_partition\n");
 279
 280           }
 281
 282
 283         {
 284           primStream pStream(5000,5000);
 285           directedLine* temp;
 286
 287           for(temp=poly; temp != NULL; temp=temp->getNextPolygon())
 288
 289             monoTriangulation(temp, &pStream);
 290
 291           slicer.evalStream(&pStream);
 292
 293         }
 294         //need to clean up space
 295       }
 296     }
 297     freejarcs( initialbin );
 298     backend.endsurf();
 299     return;
 300
 301     /*
 302     printf("num_polygons=%i\n", poly->numPolygons());
 303     printf("num_edges=%i\n", poly->numEdgesAllPolygons());
 304     poly->writeAllPolygons("zloutputFile");
 305     return;
 306     {
 307       primStream pStream(20,20);
 308       for(directedLine* tempD = poly; tempD != NULL; tempD = tempD->getNextPolygon())
 309         monoTriangulation(tempD, &pStream);
 310     }
 311     return;
 312     */
 313 }
 314 #endif //PARTITION_TEST
 315
 316
 317 #ifdef OPTIMIZE_UNTRIMED_CASE
 318     if( (!initialbin.isnonempty())  && optimize )
 319       {
 320         int i,j;
 321         int num_u_steps;
 322         int num_v_steps;
 323         for(i=spbrkpts.start; i<spbrkpts.end-1; i++){
 324           for(j=tpbrkpts.start; j<tpbrkpts.end-1; j++){
 325             Real pta[2], ptb[2];
 326             pta[0] = spbrkpts.pts[i];
 327             ptb[0] = spbrkpts.pts[i+1];
 328             pta[1] = tpbrkpts.pts[j];
 329             ptb[1] = tpbrkpts.pts[j+1];
 330             qlist->downloadAll(pta, ptb, backend);
 331
 332             num_u_steps = (int) (domain_distance_u_rate * (ptb[0]-pta[0]));
 333             num_v_steps = (int) (domain_distance_v_rate * (ptb[1]-pta[1]));
 334
 335             if(num_u_steps <= 0) num_u_steps = 1;
 336             if(num_v_steps <= 0) num_v_steps = 1;
 337
 338             backend.surfgrid(pta[0], ptb[0], num_u_steps,
 339                              ptb[1], pta[1], num_v_steps);
 340             backend.surfmesh(0,0,num_u_steps,num_v_steps);
 341
 342
 343
 344             continue;
 345             /* the following is left for reference purpose, don't delete
 346             {
 347             Bin* tempSource;
 348               Patchlist patchlist(qlist, pta, ptb);
 349               patchlist.getstepsize();
 350
 351               tempSource=makePatchBoundary(pta, ptb);
 352
 353               tessellation(*tempSource, patchlist);
 354
 355               render(*tempSource);
 356               delete tempSource;
 357             }
 358             */
 359           }
 360         }
 361       }
 362     else
 363       subdivideInS( initialbin );
 364 #else
 365
 366     subdivideInS( initialbin );
 367 #endif
 368
 369     backend.endsurf();
 370
 371 }
 372
 373 void
 374 Subdivider::subdivideInS( Bin& source )
 375 {
 376     if( renderhints.display_method == N_OUTLINE_PARAM ) {
 377         outline( source );
 378         freejarcs( source );
 379     } else {
 380         setArcTypeBezier();
 381         setNonDegenerate();
 382         splitInS( source, spbrkpts.start, spbrkpts.end );
 383     }
 384 }
 385
 386
 387 /*---------------------------------------------------------------------------
 388  * splitInS - split a patch and a bin by an isoparametric line
 389  *---------------------------------------------------------------------------
 390  */
 391
 392 void
 393 Subdivider::splitInS( Bin& source, int start, int end )
 394 {
 395     if( source.isnonempty() ) {
 396         if( start != end ) {
 397             int i = start + (end - start) / 2;
 398             Bin left, right;
 399             split( source, left, right, 0, spbrkpts.pts[i] );
 400             splitInS( left, start, i );
 401             splitInS( right, i+1, end );
 402         } else {
 403             if( start == spbrkpts.start || start == spbrkpts.end ) {
 404                 freejarcs( source );
 405             } else if( renderhints.display_method == N_OUTLINE_PARAM_S ) {
 406                 outline( source );
 407                 freejarcs( source );
 408             } else {
 409                 setArcTypeBezier();
 410                 setNonDegenerate();
 411                 s_index = start;
 412                 splitInT( source, tpbrkpts.start, tpbrkpts.end );
 413             }
 414         }
 415     }
 416 }
 417
 418 /*---------------------------------------------------------------------------
 419  * splitInT - split a patch and a bin by an isoparametric line
 420  *---------------------------------------------------------------------------
 421  */
 422
 423 void
 424 Subdivider::splitInT( Bin& source, int start, int end )
 425 {
 426     if( source.isnonempty() ) {
 427         if( start != end ) {
 428             int i = start + (end - start) / 2;
 429             Bin left, right;
 430             split( source, left, right, 1, tpbrkpts.pts[i] );
 431             splitInT( left, start, i );
 432             splitInT( right, i+1, end );
 433         } else {
 434             if( start == tpbrkpts.start || start == tpbrkpts.end ) {
 435                 freejarcs( source );
 436             } else if( renderhints.display_method == N_OUTLINE_PARAM_ST ) {
 437                 outline( source );
 438                 freejarcs( source );
 439             } else {
 440                 t_index = start;
 441                 setArcTypeBezier();
 442                 setDegenerate();
 443
 444                 REAL pta[2], ptb[2];
 445                 pta[0] = spbrkpts.pts[s_index-1];
 446                 pta[1] = tpbrkpts.pts[t_index-1];
 447
 448                 ptb[0] = spbrkpts.pts[s_index];
 449                 ptb[1] = tpbrkpts.pts[t_index];
 450                 qlist->downloadAll( pta, ptb, backend );
 451
 452                 Patchlist patchlist( qlist, pta, ptb );
 453 /*
 454 printf("-------samplingSplit-----\n");
 455 source.show("samplingSplit source");
 456 */
 457                 samplingSplit( source, patchlist, renderhints.maxsubdivisions, 0 );
 458                 setNonDegenerate();
 459                 setArcTypeBezier();
 460             }
 461         }
 462     }
 463 }
 464
 465 /*--------------------------------------------------------------------------
 466  * samplingSplit - recursively subdivide patch, cull check each subpatch
 467  *--------------------------------------------------------------------------
 468  */
 469
 470 void
 471 Subdivider::samplingSplit(
 472     Bin& source,
 473     Patchlist& patchlist,
 474     int subdivisions,
 475     int param )
 476 {
 477     if( ! source.isnonempty() ) return;
 478
 479     if( patchlist.cullCheck() == CULL_TRIVIAL_REJECT ) {
 480         freejarcs( source );
 481         return;
 482     }
 483
 484     patchlist.getstepsize();
 485
 486     if( renderhints.display_method == N_OUTLINE_PATCH ) {
 487         tessellation( source, patchlist );
 488         outline( source );
 489         freejarcs( source );
 490         return;
 491     }
 492
 493     //patchlist.clamp();
 494
 495     tessellation( source, patchlist );
 496
 497     if( patchlist.needsSamplingSubdivision() && (subdivisions > 0) ) {
 498         if( ! patchlist.needsSubdivision( 0 ) )
 499             param = 1;
 500         else if( ! patchlist.needsSubdivision( 1 ) )
 501             param = 0;
 502         else
 503             param = 1 - param;
 504
 505         Bin left, right;
 506         REAL mid = ( patchlist.pspec[param].range[0] +
 507                      patchlist.pspec[param].range[1] ) * 0.5;
 508         split( source, left, right, param, mid );
 509         Patchlist subpatchlist( patchlist, param, mid );
 510         samplingSplit( left, subpatchlist, subdivisions-1, param );
 511         samplingSplit( right, patchlist, subdivisions-1, param );
 512     } else {
 513         setArcTypePwl();
 514         setDegenerate();
 515         nonSamplingSplit( source, patchlist, subdivisions, param );
 516         setDegenerate();
 517         setArcTypeBezier();
 518     }
 519 }
 520
 521 void
 522 Subdivider::nonSamplingSplit(
 523     Bin& source,
 524     Patchlist& patchlist,
 525     int subdivisions,
 526     int param )
 527 {
 528     if( patchlist.needsNonSamplingSubdivision() && (subdivisions > 0) ) {
 529         param = 1 - param;
 530
 531         Bin left, right;
 532         REAL mid = ( patchlist.pspec[param].range[0] +
 533                      patchlist.pspec[param].range[1] ) * 0.5;
 534         split( source, left, right, param, mid );
 535         Patchlist subpatchlist( patchlist, param, mid );
 536         if( left.isnonempty() )
 537             if( subpatchlist.cullCheck() == CULL_TRIVIAL_REJECT )
 538                 freejarcs( left );
 539             else
 540                 nonSamplingSplit( left, subpatchlist, subdivisions-1, param );
 541         if( right.isnonempty() )
 542             if( patchlist.cullCheck() == CULL_TRIVIAL_REJECT )
 543                 freejarcs( right );
 544             else
 545                 nonSamplingSplit( right, patchlist, subdivisions-1, param );
 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 }