reactos/dll/win32/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         }
 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 }