aboutsummaryrefslogtreecommitdiff
path: root/mesalib/src/glu/sgi/libnurbs/internals/subdivider.cc
diff options
context:
space:
mode:
authormarha <marha@users.sourceforge.net>2009-10-08 13:15:52 +0000
committermarha <marha@users.sourceforge.net>2009-10-08 13:15:52 +0000
commita0c4815433ccd57322f4f7703ca35e9ccfa59250 (patch)
treef5213802ec12adb86ec3136001c1c29fe5343700 /mesalib/src/glu/sgi/libnurbs/internals/subdivider.cc
parentc73dc01b6de45612b24dc2dd34fba24d81ebf46c (diff)
downloadvcxsrv-a0c4815433ccd57322f4f7703ca35e9ccfa59250.tar.gz
vcxsrv-a0c4815433ccd57322f4f7703ca35e9ccfa59250.tar.bz2
vcxsrv-a0c4815433ccd57322f4f7703ca35e9ccfa59250.zip
Added MesaLib-7.6
Diffstat (limited to 'mesalib/src/glu/sgi/libnurbs/internals/subdivider.cc')
-rw-r--r--mesalib/src/glu/sgi/libnurbs/internals/subdivider.cc910
1 files changed, 910 insertions, 0 deletions
diff --git a/mesalib/src/glu/sgi/libnurbs/internals/subdivider.cc b/mesalib/src/glu/sgi/libnurbs/internals/subdivider.cc
new file mode 100644
index 000000000..cc0b51470
--- /dev/null
+++ b/mesalib/src/glu/sgi/libnurbs/internals/subdivider.cc
@@ -0,0 +1,910 @@
+/*
+** License Applicability. Except to the extent portions of this file are
+** made subject to an alternative license as permitted in the SGI Free
+** Software License B, Version 1.1 (the "License"), the contents of this
+** file are subject only to the provisions of the License. You may not use
+** this file except in compliance with the License. You may obtain a copy
+** of the License at Silicon Graphics, Inc., attn: Legal Services, 1600
+** Amphitheatre Parkway, Mountain View, CA 94043-1351, or at:
+**
+** http://oss.sgi.com/projects/FreeB
+**
+** Note that, as provided in the License, the Software is distributed on an
+** "AS IS" basis, with ALL EXPRESS AND IMPLIED WARRANTIES AND CONDITIONS
+** DISCLAIMED, INCLUDING, WITHOUT LIMITATION, ANY IMPLIED WARRANTIES AND
+** CONDITIONS OF MERCHANTABILITY, SATISFACTORY QUALITY, FITNESS FOR A
+** PARTICULAR PURPOSE, AND NON-INFRINGEMENT.
+**
+** Original Code. The Original Code is: OpenGL Sample Implementation,
+** Version 1.2.1, released January 26, 2000, developed by Silicon Graphics,
+** Inc. The Original Code is Copyright (c) 1991-2000 Silicon Graphics, Inc.
+** Copyright in any portions created by third parties is as indicated
+** elsewhere herein. All Rights Reserved.
+**
+** Additional Notice Provisions: The application programming interfaces
+** established by SGI in conjunction with the Original Code are The
+** OpenGL(R) Graphics System: A Specification (Version 1.2.1), released
+** April 1, 1999; The OpenGL(R) Graphics System Utility Library (Version
+** 1.3), released November 4, 1998; and OpenGL(R) Graphics with the X
+** Window System(R) (Version 1.3), released October 19, 1998. This software
+** was created using the OpenGL(R) version 1.2.1 Sample Implementation
+** published by SGI, but has not been independently verified as being
+** compliant with the OpenGL(R) version 1.2.1 Specification.
+*/
+
+/*
+ * subdivider.cxx
+ *
+ */
+
+#include "glimports.h"
+#include "myassert.h"
+#include "mystdio.h"
+#include "subdivider.h"
+#include "arc.h"
+#include "bezierarc.h"
+#include "bin.h"
+#include "renderhints.h"
+#include "backend.h"
+#include "mapdesc.h"
+#include "quilt.h"
+#include "patchlist.h"
+#include "patch.h"
+#include "nurbsconsts.h"
+#include "trimvertpool.h"
+#include "simplemath.h"
+
+#include "polyUtil.h" //for function area()
+
+//#define PARTITION_TEST
+#ifdef PARTITION_TEST
+#include "partitionY.h"
+#include "monoTriangulation.h"
+#include "dataTransform.h"
+#include "monoChain.h"
+
+#endif
+
+
+#define OPTIMIZE_UNTRIMED_CASE
+
+
+Bin*
+Subdivider::makePatchBoundary( const REAL *from, const REAL *to )
+{
+ Bin* ret = new Bin();
+ REAL smin = from[0];
+ REAL smax = to[0];
+ REAL tmin = from[1];
+ REAL tmax = to[1];
+
+ pjarc = 0;
+
+ Arc_ptr jarc = new(arcpool) Arc( arc_bottom, 0 );
+ arctessellator.bezier( jarc, smin, smax, tmin, tmin );
+ ret->addarc( jarc );
+ pjarc = jarc->append( pjarc );
+
+ jarc = new(arcpool) Arc( arc_right, 0 );
+ arctessellator.bezier( jarc, smax, smax, tmin, tmax );
+ ret->addarc( jarc );
+ pjarc = jarc->append( pjarc );
+
+ jarc = new(arcpool) Arc( arc_top, 0 );
+ arctessellator.bezier( jarc, smax, smin, tmax, tmax );
+ ret->addarc( jarc );
+ pjarc = jarc->append( pjarc );
+
+ jarc = new(arcpool) Arc( arc_left, 0 );
+ arctessellator.bezier( jarc, smin, smin, tmax, tmin );
+ ret->addarc( jarc );
+ jarc->append( pjarc );
+
+ assert( jarc->check() != 0 );
+ return ret;
+}
+
+/*---------------------------------------------------------------------------
+ * Subdivider - construct a subdivider
+ *---------------------------------------------------------------------------
+ */
+
+Subdivider::Subdivider( Renderhints& r, Backend& b )
+ : slicer( b ),
+ arctessellator( trimvertexpool, pwlarcpool ),
+ arcpool( sizeof( Arc), 1, "arcpool" ),
+ bezierarcpool( sizeof( BezierArc ), 1, "Bezarcpool" ),
+ pwlarcpool( sizeof( PwlArc ), 1, "Pwlarcpool" ),
+ renderhints( r ),
+ backend( b )
+{
+}
+
+void
+Subdivider::setJumpbuffer( JumpBuffer *j )
+{
+ jumpbuffer = j;
+}
+
+/*---------------------------------------------------------------------------
+ * clear - reset all state after possible error condition
+ *---------------------------------------------------------------------------
+ */
+
+void
+Subdivider::clear( void )
+{
+ trimvertexpool.clear();
+ arcpool.clear();
+ pwlarcpool.clear();
+ bezierarcpool.clear();
+}
+
+/*---------------------------------------------------------------------------
+ * ~Subdivider - destroy a subdivider
+ *---------------------------------------------------------------------------
+ */
+
+Subdivider::~Subdivider( void )
+{
+}
+
+/*---------------------------------------------------------------------------
+ * addArc - add a bezier arc to a trim loop and to a bin
+ *---------------------------------------------------------------------------
+ */
+void
+Subdivider::addArc( REAL *cpts, Quilt *quilt, long _nuid )
+{
+ BezierArc *bezierArc = new(bezierarcpool) BezierArc;
+ Arc *jarc = new(arcpool) Arc( arc_none, _nuid );
+ jarc->pwlArc = 0;
+ jarc->bezierArc = bezierArc;
+ bezierArc->order = quilt->qspec->order;
+ bezierArc->stride = quilt->qspec->stride;
+ bezierArc->mapdesc = quilt->mapdesc;
+ bezierArc->cpts = cpts;
+ initialbin.addarc( jarc );
+ pjarc = jarc->append( pjarc );
+}
+
+/*---------------------------------------------------------------------------
+ * addArc - add a pwl arc to a trim loop and to a bin
+ *---------------------------------------------------------------------------
+ */
+
+void
+Subdivider::addArc( int npts, TrimVertex *pts, long _nuid )
+{
+ Arc *jarc = new(arcpool) Arc( arc_none, _nuid );
+ jarc->pwlArc = new(pwlarcpool) PwlArc( npts, pts );
+ initialbin.addarc( jarc );
+ pjarc = jarc->append( pjarc );
+}
+
+void
+Subdivider::beginQuilts( void )
+{
+ qlist = 0;
+}
+
+void
+Subdivider::addQuilt( Quilt *quilt )
+{
+ quilt->next = qlist;
+ qlist = quilt;
+}
+
+/*---------------------------------------------------------------------------
+ * drawSurfaces - main entry point for surface tessellation
+ *---------------------------------------------------------------------------
+ */
+
+void
+Subdivider::drawSurfaces( long nuid )
+{
+ renderhints.init( );
+
+ if (qlist == NULL)
+ {
+ //initialbin could be nonempty due to some errors
+ freejarcs(initialbin);
+ return;
+ }
+
+ for( Quilt *q = qlist; q; q = q->next ) {
+ if( q->isCulled( ) == CULL_TRIVIAL_REJECT ) {
+ freejarcs( initialbin );
+ return;
+ }
+ }
+
+
+ REAL from[2], to[2];
+ qlist->getRange( from, to, spbrkpts, tpbrkpts );
+#ifdef OPTIMIZE_UNTRIMED_CASE
+ //perform optimization only when the samplng method is
+ //DOMAIN_DISTANCE and the display methdo is either
+ //fill or outline_polygon.
+ int optimize = (is_domain_distance_sampling && (renderhints.display_method != N_OUTLINE_PATCH));
+#endif
+
+ if( ! initialbin.isnonempty() ) {
+#ifdef OPTIMIZE_UNTRIMED_CASE
+ if(! optimize )
+ {
+
+ makeBorderTrim( from, to );
+ }
+#else
+ makeBorderTrim( from, to );
+#endif
+ } else {
+ REAL rate[2];
+ qlist->findRates( spbrkpts, tpbrkpts, rate );
+
+ if( decompose( initialbin, min(rate[0], rate[1]) ) )
+ mylongjmp( jumpbuffer, 31 );
+ }
+
+ backend.bgnsurf( renderhints.wiretris, renderhints.wirequads, nuid );
+
+#ifdef PARTITION_TEST
+ if( initialbin.isnonempty() && spbrkpts.end-2 == spbrkpts.start &&
+ tpbrkpts.end-2 == tpbrkpts.start)
+{
+ for(int i=spbrkpts.start; i<spbrkpts.end-1; i++){
+ for(int j=tpbrkpts.start; j<tpbrkpts.end-1; j++){
+ Real pta[2], ptb[2];
+ pta[0] = spbrkpts.pts[i];
+ ptb[0] = spbrkpts.pts[i+1];
+ pta[1] = tpbrkpts.pts[j];
+ ptb[1] = tpbrkpts.pts[j+1];
+ qlist->downloadAll(pta, ptb, backend);
+
+ directedLine *poly;
+
+ {
+
+ poly = bin_to_DLineLoops(initialbin);
+
+ poly=poly->deleteDegenerateLinesAllPolygons();
+
+ sampledLine* retSampledLines;
+//printf("before MC_partition\n");
+ poly = MC_partitionY(poly, &retSampledLines);
+//printf("after MC_partition\n");
+
+ }
+
+
+ {
+ primStream pStream(5000,5000);
+ directedLine* temp;
+
+ for(temp=poly; temp != NULL; temp=temp->getNextPolygon())
+
+ monoTriangulation(temp, &pStream);
+
+ slicer.evalStream(&pStream);
+
+ }
+ //need to clean up space
+ }
+ }
+ freejarcs( initialbin );
+ backend.endsurf();
+ return;
+
+ /*
+ printf("num_polygons=%i\n", poly->numPolygons());
+ printf("num_edges=%i\n", poly->numEdgesAllPolygons());
+ poly->writeAllPolygons("zloutputFile");
+ return;
+ {
+ primStream pStream(20,20);
+ for(directedLine* tempD = poly; tempD != NULL; tempD = tempD->getNextPolygon())
+ monoTriangulation(tempD, &pStream);
+ }
+ return;
+ */
+}
+#endif //PARTITION_TEST
+
+
+#ifdef OPTIMIZE_UNTRIMED_CASE
+ if( (!initialbin.isnonempty()) && optimize )
+ {
+ int i,j;
+ int num_u_steps;
+ int num_v_steps;
+ for(i=spbrkpts.start; i<spbrkpts.end-1; i++){
+ for(j=tpbrkpts.start; j<tpbrkpts.end-1; j++){
+ Real pta[2], ptb[2];
+ pta[0] = spbrkpts.pts[i];
+ ptb[0] = spbrkpts.pts[i+1];
+ pta[1] = tpbrkpts.pts[j];
+ ptb[1] = tpbrkpts.pts[j+1];
+ qlist->downloadAll(pta, ptb, backend);
+
+ num_u_steps = (int) (domain_distance_u_rate * (ptb[0]-pta[0]));
+ num_v_steps = (int) (domain_distance_v_rate * (ptb[1]-pta[1]));
+
+ if(num_u_steps <= 0) num_u_steps = 1;
+ if(num_v_steps <= 0) num_v_steps = 1;
+
+ backend.surfgrid(pta[0], ptb[0], num_u_steps,
+ ptb[1], pta[1], num_v_steps);
+ backend.surfmesh(0,0,num_u_steps,num_v_steps);
+
+
+
+ continue;
+ /* the following is left for reference purpose, don't delete
+ {
+ Bin* tempSource;
+ Patchlist patchlist(qlist, pta, ptb);
+ patchlist.getstepsize();
+
+ tempSource=makePatchBoundary(pta, ptb);
+
+ tessellation(*tempSource, patchlist);
+
+ render(*tempSource);
+ delete tempSource;
+ }
+ */
+ }
+ }
+ }
+ else
+ subdivideInS( initialbin );
+#else
+
+ subdivideInS( initialbin );
+#endif
+
+ backend.endsurf();
+
+}
+
+void
+Subdivider::subdivideInS( Bin& source )
+{
+ if( renderhints.display_method == N_OUTLINE_PARAM ) {
+ outline( source );
+ freejarcs( source );
+ } else {
+ setArcTypeBezier();
+ setNonDegenerate();
+ splitInS( source, spbrkpts.start, spbrkpts.end );
+ }
+}
+
+
+/*---------------------------------------------------------------------------
+ * splitInS - split a patch and a bin by an isoparametric line
+ *---------------------------------------------------------------------------
+ */
+
+void
+Subdivider::splitInS( Bin& source, int start, int end )
+{
+ if( source.isnonempty() ) {
+ if( start != end ) {
+ int i = start + (end - start) / 2;
+ Bin left, right;
+ split( source, left, right, 0, spbrkpts.pts[i] );
+ splitInS( left, start, i );
+ splitInS( right, i+1, end );
+ } else {
+ if( start == spbrkpts.start || start == spbrkpts.end ) {
+ freejarcs( source );
+ } else if( renderhints.display_method == N_OUTLINE_PARAM_S ) {
+ outline( source );
+ freejarcs( source );
+ } else {
+ setArcTypeBezier();
+ setNonDegenerate();
+ s_index = start;
+ splitInT( source, tpbrkpts.start, tpbrkpts.end );
+ }
+ }
+ }
+}
+
+/*---------------------------------------------------------------------------
+ * splitInT - split a patch and a bin by an isoparametric line
+ *---------------------------------------------------------------------------
+ */
+
+void
+Subdivider::splitInT( Bin& source, int start, int end )
+{
+ if( source.isnonempty() ) {
+ if( start != end ) {
+ int i = start + (end - start) / 2;
+ Bin left, right;
+ split( source, left, right, 1, tpbrkpts.pts[i] );
+ splitInT( left, start, i );
+ splitInT( right, i+1, end );
+ } else {
+ if( start == tpbrkpts.start || start == tpbrkpts.end ) {
+ freejarcs( source );
+ } else if( renderhints.display_method == N_OUTLINE_PARAM_ST ) {
+ outline( source );
+ freejarcs( source );
+ } else {
+ t_index = start;
+ setArcTypeBezier();
+ setDegenerate();
+
+ REAL pta[2], ptb[2];
+ pta[0] = spbrkpts.pts[s_index-1];
+ pta[1] = tpbrkpts.pts[t_index-1];
+
+ ptb[0] = spbrkpts.pts[s_index];
+ ptb[1] = tpbrkpts.pts[t_index];
+ qlist->downloadAll( pta, ptb, backend );
+
+ Patchlist patchlist( qlist, pta, ptb );
+/*
+printf("-------samplingSplit-----\n");
+source.show("samplingSplit source");
+*/
+ samplingSplit( source, patchlist, renderhints.maxsubdivisions, 0 );
+ setNonDegenerate();
+ setArcTypeBezier();
+ }
+ }
+ }
+}
+
+/*--------------------------------------------------------------------------
+ * samplingSplit - recursively subdivide patch, cull check each subpatch
+ *--------------------------------------------------------------------------
+ */
+
+void
+Subdivider::samplingSplit(
+ Bin& source,
+ Patchlist& patchlist,
+ int subdivisions,
+ int param )
+{
+ if( ! source.isnonempty() ) return;
+
+ if( patchlist.cullCheck() == CULL_TRIVIAL_REJECT ) {
+ freejarcs( source );
+ return;
+ }
+
+ patchlist.getstepsize();
+
+ if( renderhints.display_method == N_OUTLINE_PATCH ) {
+ tessellation( source, patchlist );
+ outline( source );
+ freejarcs( source );
+ return;
+ }
+
+ //patchlist.clamp();
+
+ tessellation( source, patchlist );
+
+ if( patchlist.needsSamplingSubdivision() && (subdivisions > 0) ) {
+ if( ! patchlist.needsSubdivision( 0 ) )
+ param = 1;
+ else if( ! patchlist.needsSubdivision( 1 ) )
+ param = 0;
+ else
+ param = 1 - param;
+
+ Bin left, right;
+ REAL mid = ( patchlist.pspec[param].range[0] +
+ patchlist.pspec[param].range[1] ) * 0.5;
+ split( source, left, right, param, mid );
+ Patchlist subpatchlist( patchlist, param, mid );
+ samplingSplit( left, subpatchlist, subdivisions-1, param );
+ samplingSplit( right, patchlist, subdivisions-1, param );
+ } else {
+ setArcTypePwl();
+ setDegenerate();
+ nonSamplingSplit( source, patchlist, subdivisions, param );
+ setDegenerate();
+ setArcTypeBezier();
+ }
+}
+
+void
+Subdivider::nonSamplingSplit(
+ Bin& source,
+ Patchlist& patchlist,
+ int subdivisions,
+ int param )
+{
+ if( patchlist.needsNonSamplingSubdivision() && (subdivisions > 0) ) {
+ param = 1 - param;
+
+ Bin left, right;
+ REAL mid = ( patchlist.pspec[param].range[0] +
+ patchlist.pspec[param].range[1] ) * 0.5;
+ split( source, left, right, param, mid );
+ Patchlist subpatchlist( patchlist, param, mid );
+ if( left.isnonempty() )
+ if( subpatchlist.cullCheck() == CULL_TRIVIAL_REJECT )
+ freejarcs( left );
+ else
+ nonSamplingSplit( left, subpatchlist, subdivisions-1, param );
+ if( right.isnonempty() )
+ if( patchlist.cullCheck() == CULL_TRIVIAL_REJECT )
+ freejarcs( right );
+ else
+ nonSamplingSplit( right, patchlist, subdivisions-1, param );
+
+ } else {
+ // make bbox calls
+ patchlist.bbox();
+ backend.patch( patchlist.pspec[0].range[0], patchlist.pspec[0].range[1],
+ patchlist.pspec[1].range[0], patchlist.pspec[1].range[1] );
+
+ if( renderhints.display_method == N_OUTLINE_SUBDIV ) {
+ outline( source );
+ freejarcs( source );
+ } else {
+ setArcTypePwl();
+ setDegenerate();
+ findIrregularS( source );
+ monosplitInS( source, smbrkpts.start, smbrkpts.end );
+ }
+ }
+}
+
+/*--------------------------------------------------------------------------
+ * tessellation - set tessellation of interior and boundary of patch
+ *--------------------------------------------------------------------------
+ */
+
+void
+Subdivider::tessellation( Bin& bin, Patchlist &patchlist )
+{
+ // tessellate unsampled trim curves
+ tessellate( bin, patchlist.pspec[1].sidestep[1], patchlist.pspec[0].sidestep[1],
+ patchlist.pspec[1].sidestep[0], patchlist.pspec[0].sidestep[0] );
+
+ // set interior sampling rates
+ slicer.setstriptessellation( patchlist.pspec[0].stepsize, patchlist.pspec[1].stepsize );
+
+ //added by zl: set the order which will be used in slicer.c++
+ slicer.set_ulinear( (patchlist.get_uorder() == 2));
+ slicer.set_vlinear( (patchlist.get_vorder() == 2));
+
+ // set boundary sampling rates
+ stepsizes[0] = patchlist.pspec[1].stepsize;
+ stepsizes[1] = patchlist.pspec[0].stepsize;
+ stepsizes[2] = patchlist.pspec[1].stepsize;
+ stepsizes[3] = patchlist.pspec[0].stepsize;
+}
+
+/*---------------------------------------------------------------------------
+ * monosplitInS - split a patch and a bin by an isoparametric line
+ *---------------------------------------------------------------------------
+ */
+
+void
+Subdivider::monosplitInS( Bin& source, int start, int end )
+{
+ if( source.isnonempty() ) {
+ if( start != end ) {
+ int i = start + (end - start) / 2;
+ Bin left, right;
+ split( source, left, right, 0, smbrkpts.pts[i] );
+ monosplitInS( left, start, i );
+ monosplitInS( right, i+1, end );
+ } else {
+ if( renderhints.display_method == N_OUTLINE_SUBDIV_S ) {
+ outline( source );
+ freejarcs( source );
+ } else {
+ setArcTypePwl();
+ setDegenerate();
+ findIrregularT( source );
+ monosplitInT( source, tmbrkpts.start, tmbrkpts.end );
+ }
+ }
+ }
+}
+
+/*---------------------------------------------------------------------------
+ * monosplitInT - split a patch and a bin by an isoparametric line
+ *---------------------------------------------------------------------------
+ */
+
+void
+Subdivider::monosplitInT( Bin& source, int start, int end )
+{
+ if( source.isnonempty() ) {
+ if( start != end ) {
+ int i = start + (end - start) / 2;
+ Bin left, right;
+ split( source, left, right, 1, tmbrkpts.pts[i] );
+ monosplitInT( left, start, i );
+ monosplitInT( right, i+1, end );
+ } else {
+ if( renderhints.display_method == N_OUTLINE_SUBDIV_ST ) {
+ outline( source );
+ freejarcs( source );
+ } else {
+/*
+printf("*******render\n");
+source.show("source\n");
+*/
+ render( source );
+ freejarcs( source );
+ }
+ }
+ }
+}
+
+
+/*----------------------------------------------------------------------------
+ * findIrregularS - determine points of non-monotonicity is s direction
+ *----------------------------------------------------------------------------
+ */
+
+void
+Subdivider::findIrregularS( Bin& bin )
+{
+ assert( bin.firstarc()->check() != 0 );
+
+ smbrkpts.grow( bin.numarcs() );
+
+ for( Arc_ptr jarc=bin.firstarc(); jarc; jarc=bin.nextarc() ) {
+ REAL *a = jarc->prev->tail();
+ REAL *b = jarc->tail();
+ REAL *c = jarc->head();
+
+ if( b[1] == a[1] && b[1] == c[1] ) continue;
+
+ //corrected code
+ if((b[1]<=a[1] && b[1] <= c[1]) ||
+ (b[1]>=a[1] && b[1] >= c[1]))
+ {
+ //each arc (jarc, jarc->prev, jarc->next) is a
+ //monotone arc consisting of multiple line segements.
+ //it may happen that jarc->prev and jarc->next are the same,
+ //that is, jarc->prev and jarc form a closed loop.
+ //In such case, a and c will be the same.
+ if(a[0]==c[0] && a[1] == c[1])
+ {
+ if(jarc->pwlArc->npts >2)
+ {
+ c = jarc->pwlArc->pts[jarc->pwlArc->npts-2].param;
+ }
+ else
+ {
+ assert(jarc->prev->pwlArc->npts>2);
+ a = jarc->prev->pwlArc->pts[jarc->prev->pwlArc->npts-2].param;
+ }
+
+ }
+ if(area(a,b,c) < 0)
+ {
+ smbrkpts.add(b[0]);
+ }
+
+ }
+
+ /* old code,
+ if( b[1] <= a[1] && b[1] <= c[1] ) {
+ if( ! ccwTurn_tr( jarc->prev, jarc ) )
+ smbrkpts.add( b[0] );
+ } else if( b[1] >= a[1] && b[1] >= c[1] ) {
+ if( ! ccwTurn_tl( jarc->prev, jarc ) )
+ smbrkpts.add( b[0] );
+ }
+ */
+
+ }
+
+ smbrkpts.filter();
+}
+
+/*----------------------------------------------------------------------------
+ * findIrregularT - determine points of non-monotonicity in t direction
+ * where one arc is parallel to the s axis.
+ *----------------------------------------------------------------------------
+ */
+
+void
+Subdivider::findIrregularT( Bin& bin )
+{
+ assert( bin.firstarc()->check() != 0 );
+
+ tmbrkpts.grow( bin.numarcs() );
+
+ for( Arc_ptr jarc=bin.firstarc(); jarc; jarc=bin.nextarc() ) {
+ REAL *a = jarc->prev->tail();
+ REAL *b = jarc->tail();
+ REAL *c = jarc->head();
+
+ if( b[0] == a[0] && b[0] == c[0] ) continue;
+
+ if( b[0] <= a[0] && b[0] <= c[0] ) {
+ if( a[1] != b[1] && b[1] != c[1] ) continue;
+ if( ! ccwTurn_sr( jarc->prev, jarc ) )
+ tmbrkpts.add( b[1] );
+ } else if ( b[0] >= a[0] && b[0] >= c[0] ) {
+ if( a[1] != b[1] && b[1] != c[1] ) continue;
+ if( ! ccwTurn_sl( jarc->prev, jarc ) )
+ tmbrkpts.add( b[1] );
+ }
+ }
+ tmbrkpts.filter( );
+}
+
+/*-----------------------------------------------------------------------------
+ * makeBorderTrim - if no user input trimming data then create
+ * a trimming curve around the boundaries of the Quilt. The curve consists of
+ * four Jordan arcs, one for each side of the Quilt, connected, of course,
+ * head to tail.
+ *-----------------------------------------------------------------------------
+ */
+
+void
+Subdivider::makeBorderTrim( const REAL *from, const REAL *to )
+{
+ REAL smin = from[0];
+ REAL smax = to[0];
+ REAL tmin = from[1];
+ REAL tmax = to[1];
+
+ pjarc = 0;
+
+ Arc_ptr jarc = new(arcpool) Arc( arc_bottom, 0 );
+ arctessellator.bezier( jarc, smin, smax, tmin, tmin );
+ initialbin.addarc( jarc );
+ pjarc = jarc->append( pjarc );
+
+ jarc = new(arcpool) Arc( arc_right, 0 );
+ arctessellator.bezier( jarc, smax, smax, tmin, tmax );
+ initialbin.addarc( jarc );
+ pjarc = jarc->append( pjarc );
+
+ jarc = new(arcpool) Arc( arc_top, 0 );
+ arctessellator.bezier( jarc, smax, smin, tmax, tmax );
+ initialbin.addarc( jarc );
+ pjarc = jarc->append( pjarc );
+
+ jarc = new(arcpool) Arc( arc_left, 0 );
+ arctessellator.bezier( jarc, smin, smin, tmax, tmin );
+ initialbin.addarc( jarc );
+ jarc->append( pjarc );
+
+ assert( jarc->check() != 0 );
+}
+
+/*----------------------------------------------------------------------------
+ * render - renders all monotone regions in a bin and frees the bin
+ *----------------------------------------------------------------------------
+ */
+
+void
+Subdivider::render( Bin& bin )
+{
+ bin.markall();
+
+#ifdef N_ISOLINE_S
+ slicer.setisolines( ( renderhints.display_method == N_ISOLINE_S ) ? 1 : 0 );
+#else
+ slicer.setisolines( 0 );
+#endif
+
+ for( Arc_ptr jarc=bin.firstarc(); jarc; jarc=bin.nextarc() ) {
+ if( jarc->ismarked() ) {
+ assert( jarc->check( ) != 0 );
+ Arc_ptr jarchead = jarc;
+ do {
+ jarc->clearmark();
+ jarc = jarc->next;
+ } while (jarc != jarchead);
+ slicer.slice( jarc );
+ }
+ }
+}
+
+/*---------------------------------------------------------------------------
+ * outline - render the trimmed patch by outlining the boundary
+ *---------------------------------------------------------------------------
+ */
+
+void
+Subdivider::outline( Bin& bin )
+{
+ bin.markall();
+ for( Arc_ptr jarc=bin.firstarc(); jarc; jarc=bin.nextarc() ) {
+ if( jarc->ismarked() ) {
+ assert( jarc->check( ) != 0 );
+ Arc_ptr jarchead = jarc;
+ do {
+ slicer.outline( jarc );
+ jarc->clearmark();
+ jarc = jarc->prev;
+ } while (jarc != jarchead);
+ }
+ }
+}
+
+/*---------------------------------------------------------------------------
+ * freejarcs - free all arcs in a bin
+ *---------------------------------------------------------------------------
+ */
+
+void
+Subdivider::freejarcs( Bin& bin )
+{
+ bin.adopt(); /* XXX - should not be necessary */
+
+ Arc_ptr jarc;
+ while( (jarc = bin.removearc()) != NULL ) {
+ if( jarc->pwlArc ) jarc->pwlArc->deleteMe( pwlarcpool ); jarc->pwlArc = 0;
+ if( jarc->bezierArc) jarc->bezierArc->deleteMe( bezierarcpool ); jarc->bezierArc = 0;
+ jarc->deleteMe( arcpool );
+ }
+}
+
+/*----------------------------------------------------------------------------
+ * tessellate - tessellate all Bezier arcs in a bin
+ * 1) only accepts linear Bezier arcs as input
+ * 2) the Bezier arcs are stored in the pwlArc structure
+ * 3) only vertical or horizontal lines work
+ * -- should
+ * 1) represent Bezier arcs in BezierArc structure
+ * (this requires a multitude of changes to the code)
+ * 2) accept high degree Bezier arcs (hard)
+ * 3) map the curve onto the surface to determine tessellation
+ * 4) work for curves of arbitrary geometry
+ *----------------------------------------------------------------------------
+ */
+
+
+void
+Subdivider::tessellate( Bin& bin, REAL rrate, REAL trate, REAL lrate, REAL brate )
+{
+ for( Arc_ptr jarc=bin.firstarc(); jarc; jarc=bin.nextarc() ) {
+ if( jarc->isbezier( ) ) {
+ assert( jarc->pwlArc->npts == 2 );
+ TrimVertex *pts = jarc->pwlArc->pts;
+ REAL s1 = pts[0].param[0];
+ REAL t1 = pts[0].param[1];
+ REAL s2 = pts[1].param[0];
+ REAL t2 = pts[1].param[1];
+
+ jarc->pwlArc->deleteMe( pwlarcpool ); jarc->pwlArc = 0;
+
+ switch( jarc->getside() ) {
+ case arc_left:
+ assert( s1 == s2 );
+ arctessellator.pwl_left( jarc, s1, t1, t2, lrate );
+ break;
+ case arc_right:
+ assert( s1 == s2 );
+ arctessellator.pwl_right( jarc, s1, t1, t2, rrate );
+ break;
+ case arc_top:
+ assert( t1 == t2 );
+ arctessellator.pwl_top( jarc, t1, s1, s2, trate );
+ break;
+ case arc_bottom:
+ assert( t1 == t2 );
+ arctessellator.pwl_bottom( jarc, t1, s1, s2, brate );
+ break;
+ case arc_none:
+ (void) abort();
+ break;
+ }
+ assert( ! jarc->isbezier() );
+ assert( jarc->check() != 0 );
+ }
+ }
+}