reactos/dll/glu32/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  */
  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         if( right.isnonempty() )
 540             if( patchlist.cullCheck() == CULL_TRIVIAL_REJECT )
 541                 freejarcs( right );
 542             else
 543                 nonSamplingSplit( right, patchlist, subdivisions-1, param );
 544
 545     } else {
 546         // make bbox calls
 547         patchlist.bbox();
 548         backend.patch( patchlist.pspec[0].range[0], patchlist.pspec[0].range[1],
 549                        patchlist.pspec[1].range[0], patchlist.pspec[1].range[1] );
 550
 551         if( renderhints.display_method == N_OUTLINE_SUBDIV ) {
 552             outline( source );
 553             freejarcs( source );
 554         } else {
 555             setArcTypePwl();
 556             setDegenerate();
 557             findIrregularS( source );
 558             monosplitInS( source, smbrkpts.start, smbrkpts.end );
 559         }
 560     }
 561 }
 562
 563 /*--------------------------------------------------------------------------
 564  * tessellation - set tessellation of interior and boundary of patch
 565  *--------------------------------------------------------------------------
 566  */
 567
 568 void
 569 Subdivider::tessellation( Bin& bin, Patchlist &patchlist )
 570 {
 571     // tessellate unsampled trim curves
 572     tessellate( bin, patchlist.pspec[1].sidestep[1], patchlist.pspec[0].sidestep[1],
 573          patchlist.pspec[1].sidestep[0], patchlist.pspec[0].sidestep[0] );
 574
 575     // set interior sampling rates
 576     slicer.setstriptessellation( patchlist.pspec[0].stepsize, patchlist.pspec[1].stepsize );
 577
 578     //added by zl: set the order which will be used in slicer.c++
 579     slicer.set_ulinear( (patchlist.get_uorder() == 2));
 580     slicer.set_vlinear( (patchlist.get_vorder() == 2));
 581
 582     // set boundary sampling rates
 583     stepsizes[0] = patchlist.pspec[1].stepsize;
 584     stepsizes[1] = patchlist.pspec[0].stepsize;
 585     stepsizes[2] = patchlist.pspec[1].stepsize;
 586     stepsizes[3] = patchlist.pspec[0].stepsize;
 587 }
 588
 589 /*---------------------------------------------------------------------------
 590  * monosplitInS - split a patch and a bin by an isoparametric line
 591  *---------------------------------------------------------------------------
 592  */
 593
 594 void
 595 Subdivider::monosplitInS( Bin& source, int start, int end )
 596 {
 597     if( source.isnonempty() ) {
 598         if( start != end ) {
 599             int i = start + (end - start) / 2;
 600             Bin left, right;
 601             split( source, left, right, 0, smbrkpts.pts[i] );
 602             monosplitInS( left, start, i );
 603             monosplitInS( right, i+1, end );
 604         } else {
 605             if( renderhints.display_method == N_OUTLINE_SUBDIV_S ) {
 606                 outline( source );
 607                 freejarcs( source );
 608             } else {
 609                 setArcTypePwl();
 610                 setDegenerate();
 611                 findIrregularT( source );
 612                 monosplitInT( source, tmbrkpts.start, tmbrkpts.end );
 613             }
 614         }
 615     }
 616 }
 617
 618 /*---------------------------------------------------------------------------
 619  * monosplitInT - split a patch and a bin by an isoparametric line
 620  *---------------------------------------------------------------------------
 621  */
 622
 623 void
 624 Subdivider::monosplitInT( Bin& source, int start, int end )
 625 {
 626     if( source.isnonempty() ) {
 627         if( start != end ) {
 628             int i = start + (end - start) / 2;
 629             Bin left, right;
 630             split( source, left, right, 1, tmbrkpts.pts[i] );
 631             monosplitInT( left, start, i );
 632             monosplitInT( right, i+1, end );
 633         } else {
 634             if( renderhints.display_method == N_OUTLINE_SUBDIV_ST ) {
 635                 outline( source );
 636                 freejarcs( source );
 637             } else {
 638 /*
 639 printf("*******render\n");
 640 source.show("source\n");
 641 */
 642                 render( source );
 643                 freejarcs( source );
 644             }
 645         }
 646     }
 647 }
 648
 649
 650 /*----------------------------------------------------------------------------
 651  * findIrregularS - determine points of non-monotonicity is s direction
 652  *----------------------------------------------------------------------------
 653  */
 654
 655 void
 656 Subdivider::findIrregularS( Bin& bin )
 657 {
 658     assert( bin.firstarc()->check() != 0 );
 659
 660     smbrkpts.grow( bin.numarcs() );
 661
 662     for( Arc_ptr jarc=bin.firstarc(); jarc; jarc=bin.nextarc() ) {
 663         REAL *a = jarc->prev->tail();
 664         REAL *b = jarc->tail();
 665         REAL *c = jarc->head();
 666
 667         if( b[1] == a[1] && b[1] == c[1] ) continue;
 668
 669         //corrected code
 670         if((b[1]<=a[1] && b[1] <= c[1]) ||
 671            (b[1]>=a[1] && b[1] >= c[1]))
 672           {
 673             //each arc (jarc, jarc->prev, jarc->next) is a
 674             //monotone arc consisting of multiple line segements.
 675             //it may happen that jarc->prev and jarc->next are the same,
 676             //that is, jarc->prev and jarc form a closed loop.
 677             //In such case, a and c will be the same.
 678             if(a[0]==c[0] && a[1] == c[1])
 679               {
 680                 if(jarc->pwlArc->npts >2)
 681                   {
 682                     c = jarc->pwlArc->pts[jarc->pwlArc->npts-2].param;
 683                   }
 684                 else
 685                   {
 686                     assert(jarc->prev->pwlArc->npts>2);
 687                     a = jarc->prev->pwlArc->pts[jarc->prev->pwlArc->npts-2].param;
 688                   }
 689
 690               }
 691             if(area(a,b,c) < 0)
 692               {
 693                 smbrkpts.add(b[0]);
 694               }
 695
 696           }
 697
 698         /* old code,
 699         if( b[1] <= a[1] && b[1] <= c[1] ) {
 700             if( ! ccwTurn_tr( jarc->prev, jarc ) )
 701                 smbrkpts.add( b[0] );
 702         } else if( b[1] >= a[1] && b[1] >= c[1] ) {
 703             if( ! ccwTurn_tl( jarc->prev, jarc ) )
 704                 smbrkpts.add( b[0] );
 705         }
 706         */
 707
 708     }
 709
 710     smbrkpts.filter();
 711 }
 712
 713 /*----------------------------------------------------------------------------
 714  * findIrregularT - determine points of non-monotonicity in t direction
 715  *                   where one arc is parallel to the s axis.
 716  *----------------------------------------------------------------------------
 717  */
 718
 719 void
 720 Subdivider::findIrregularT( Bin& bin )
 721 {
 722     assert( bin.firstarc()->check() != 0 );
 723
 724     tmbrkpts.grow( bin.numarcs() );
 725
 726     for( Arc_ptr jarc=bin.firstarc(); jarc; jarc=bin.nextarc() ) {
 727         REAL *a = jarc->prev->tail();
 728         REAL *b = jarc->tail();
 729         REAL *c = jarc->head();
 730
 731         if( b[0] == a[0] && b[0] == c[0] ) continue;
 732
 733         if( b[0] <= a[0] && b[0] <= c[0] ) {
 734             if( a[1] != b[1] && b[1] != c[1] ) continue;
 735             if( ! ccwTurn_sr( jarc->prev, jarc ) )
 736                 tmbrkpts.add( b[1] );
 737         } else if ( b[0] >= a[0] && b[0] >= c[0] ) {
 738             if( a[1] != b[1] && b[1] != c[1] ) continue;
 739             if( ! ccwTurn_sl( jarc->prev, jarc ) )
 740                 tmbrkpts.add( b[1] );
 741         }
 742     }
 743     tmbrkpts.filter( );
 744 }
 745
 746 /*-----------------------------------------------------------------------------
 747  * makeBorderTrim - if no user input trimming data then create
 748  * a trimming curve around the boundaries of the Quilt.  The curve consists of
 749  * four Jordan arcs, one for each side of the Quilt, connected, of course,
 750  * head to tail.
 751  *-----------------------------------------------------------------------------
 752  */
 753
 754 void
 755 Subdivider::makeBorderTrim( const REAL *from, const REAL *to )
 756 {
 757     REAL smin = from[0];
 758     REAL smax = to[0];
 759     REAL tmin = from[1];
 760     REAL tmax = to[1];
 761
 762     pjarc = 0;
 763
 764     Arc_ptr jarc = new(arcpool) Arc( arc_bottom, 0 );
 765     arctessellator.bezier( jarc, smin, smax, tmin, tmin );
 766     initialbin.addarc( jarc  );
 767     pjarc = jarc->append( pjarc );
 768
 769     jarc = new(arcpool) Arc( arc_right, 0 );
 770     arctessellator.bezier( jarc, smax, smax, tmin, tmax );
 771     initialbin.addarc( jarc  );
 772     pjarc = jarc->append( pjarc );
 773
 774     jarc = new(arcpool) Arc( arc_top, 0 );
 775     arctessellator.bezier( jarc, smax, smin, tmax, tmax );
 776     initialbin.addarc( jarc  );
 777     pjarc = jarc->append( pjarc );
 778
 779     jarc = new(arcpool) Arc( arc_left, 0 );
 780     arctessellator.bezier( jarc, smin, smin, tmax, tmin );
 781     initialbin.addarc( jarc  );
 782     jarc->append( pjarc );
 783
 784     assert( jarc->check() != 0 );
 785 }
 786
 787 /*----------------------------------------------------------------------------
 788  * render - renders all monotone regions in a bin and frees the bin
 789  *----------------------------------------------------------------------------
 790  */
 791
 792 void
 793 Subdivider::render( Bin& bin )
 794 {
 795     bin.markall();
 796
 797 #ifdef N_ISOLINE_S
 798     slicer.setisolines( ( renderhints.display_method == N_ISOLINE_S ) ? 1 : 0 );
 799 #else
 800     slicer.setisolines( 0 );
 801 #endif
 802
 803     for( Arc_ptr jarc=bin.firstarc(); jarc; jarc=bin.nextarc() ) {
 804         if( jarc->ismarked() ) {
 805             assert( jarc->check( ) != 0 );
 806             Arc_ptr jarchead = jarc;
 807             do {
 808                 jarc->clearmark();
 809                 jarc = jarc->next;
 810             } while (jarc != jarchead);
 811             slicer.slice( jarc );
 812         }
 813     }
 814 }
 815
 816 /*---------------------------------------------------------------------------
 817  * outline - render the trimmed patch by outlining the boundary
 818  *---------------------------------------------------------------------------
 819  */
 820
 821 void
 822 Subdivider::outline( Bin& bin )
 823 {
 824     bin.markall();
 825     for( Arc_ptr jarc=bin.firstarc(); jarc; jarc=bin.nextarc() ) {
 826         if( jarc->ismarked() ) {
 827             assert( jarc->check( ) != 0 );
 828             Arc_ptr jarchead = jarc;
 829             do {
 830                 slicer.outline( jarc );
 831                 jarc->clearmark();
 832                 jarc = jarc->prev;
 833             } while (jarc != jarchead);
 834         }
 835     }
 836 }
 837
 838 /*---------------------------------------------------------------------------
 839  * freejarcs - free all arcs in a bin
 840  *---------------------------------------------------------------------------
 841  */
 842
 843 void
 844 Subdivider::freejarcs( Bin& bin )
 845 {
 846     bin.adopt();        /* XXX - should not be necessary */
 847
 848     Arc_ptr jarc;
 849     while( (jarc = bin.removearc()) != NULL ) {
 850         if( jarc->pwlArc ) jarc->pwlArc->deleteMe( pwlarcpool ); jarc->pwlArc = 0;
 851         if( jarc->bezierArc) jarc->bezierArc->deleteMe( bezierarcpool ); jarc->bezierArc = 0;
 852         jarc->deleteMe( arcpool );
 853     }
 854 }
 855
 856 /*----------------------------------------------------------------------------
 857  * tessellate - tessellate all Bezier arcs in a bin
 858  *                 1) only accepts linear Bezier arcs as input
 859  *                 2) the Bezier arcs are stored in the pwlArc structure
 860  *                 3) only vertical or horizontal lines work
 861  *              -- should
 862  *                 1) represent Bezier arcs in BezierArc structure
 863  *                    (this requires a multitude of changes to the code)
 864  *                 2) accept high degree Bezier arcs (hard)
 865  *                 3) map the curve onto the surface to determine tessellation
 866  *                 4) work for curves of arbitrary geometry
 867  *----------------------------------------------------------------------------
 868  */
 869
 870
 871 void
 872 Subdivider::tessellate( Bin& bin, REAL rrate, REAL trate, REAL lrate, REAL brate )
 873 {
 874     for( Arc_ptr jarc=bin.firstarc(); jarc; jarc=bin.nextarc() ) {
 875         if( jarc->isbezier( ) ) {
 876             assert( jarc->pwlArc->npts == 2 );
 877             TrimVertex  *pts = jarc->pwlArc->pts;
 878             REAL s1 = pts[0].param[0];
 879             REAL t1 = pts[0].param[1];
 880             REAL s2 = pts[1].param[0];
 881             REAL t2 = pts[1].param[1];
 882
 883             jarc->pwlArc->deleteMe( pwlarcpool ); jarc->pwlArc = 0;
 884
 885             switch( jarc->getside() ) {
 886                 case arc_left:
 887                     assert( s1 == s2 );
 888                     arctessellator.pwl_left( jarc, s1, t1, t2, lrate );
 889                     break;
 890                 case arc_right:
 891                     assert( s1 == s2 );
 892                     arctessellator.pwl_right( jarc, s1, t1, t2, rrate );
 893                     break;
 894                 case arc_top:
 895                     assert( t1 == t2 );
 896                     arctessellator.pwl_top( jarc, t1, s1, s2, trate );
 897                     break;
 898                 case arc_bottom:
 899                     assert( t1 == t2 );
 900                     arctessellator.pwl_bottom( jarc, t1, s1, s2, brate );
 901                     break;
 902                 case arc_none:
 903                     (void) abort();
 904                     break;
 905             }
 906             assert( ! jarc->isbezier() );
 907             assert( jarc->check() != 0 );
 908         }
 909     }
 910 }