11cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger/* 21cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger** License Applicability. Except to the extent portions of this file are 31cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger** made subject to an alternative license as permitted in the SGI Free 41cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger** Software License B, Version 1.1 (the "License"), the contents of this 51cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger** file are subject only to the provisions of the License. You may not use 61cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger** this file except in compliance with the License. You may obtain a copy 71cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger** of the License at Silicon Graphics, Inc., attn: Legal Services, 1600 81cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger** Amphitheatre Parkway, Mountain View, CA 94043-1351, or at: 91cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger** 101cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger** http://oss.sgi.com/projects/FreeB 111cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger** 121cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger** Note that, as provided in the License, the Software is distributed on an 131cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger** "AS IS" basis, with ALL EXPRESS AND IMPLIED WARRANTIES AND CONDITIONS 141cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger** DISCLAIMED, INCLUDING, WITHOUT LIMITATION, ANY IMPLIED WARRANTIES AND 151cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger** CONDITIONS OF MERCHANTABILITY, SATISFACTORY QUALITY, FITNESS FOR A 161cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger** PARTICULAR PURPOSE, AND NON-INFRINGEMENT. 171cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger** 181cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger** Original Code. The Original Code is: OpenGL Sample Implementation, 191cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger** Version 1.2.1, released January 26, 2000, developed by Silicon Graphics, 201cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger** Inc. The Original Code is Copyright (c) 1991-2000 Silicon Graphics, Inc. 211cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger** Copyright in any portions created by third parties is as indicated 221cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger** elsewhere herein. All Rights Reserved. 231cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger** 241cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger** Additional Notice Provisions: The application programming interfaces 251cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger** established by SGI in conjunction with the Original Code are The 261cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger** OpenGL(R) Graphics System: A Specification (Version 1.2.1), released 271cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger** April 1, 1999; The OpenGL(R) Graphics System Utility Library (Version 281cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger** 1.3), released November 4, 1998; and OpenGL(R) Graphics with the X 291cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger** Window System(R) (Version 1.3), released October 19, 1998. This software 301cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger** was created using the OpenGL(R) version 1.2.1 Sample Implementation 311cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger** published by SGI, but has not been independently verified as being 321cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger** compliant with the OpenGL(R) version 1.2.1 Specification. 331cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger** 341cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger*/ 351cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger/* 361cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger** Author: Eric Veach, July 1994. 371cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger** 381cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger** $Date$ $Revision$ 391cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger** $Header: //depot/main/gfx/lib/glu/libtess/sweep.c#5 $ 401cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger*/ 411cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 421cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger#include "gluos.h" 431cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger#include <assert.h> 441cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger#include <stddef.h> 451cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger#include <setjmp.h> /* longjmp */ 461cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger#include <limits.h> /* LONG_MAX */ 471cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 481cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger#include "mesh.h" 491cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger#include "geom.h" 501cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger#include "tess.h" 511cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger#include "dict.h" 521cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger#include "priorityq.h" 531cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger#include "memalloc.h" 541cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger#include "sweep.h" 551cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 561cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger#define TRUE 1 571cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger#define FALSE 0 581cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 591cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger#ifdef FOR_TRITE_TEST_PROGRAM 601cab2921ab279367f8206cdadc9259d12e603548Derek Sollenbergerextern void DebugEvent( GLUtesselator *tess ); 611cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger#else 621cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger#define DebugEvent( tess ) 631cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger#endif 641cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 651cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger/* 661cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * Invariants for the Edge Dictionary. 671cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * - each pair of adjacent edges e2=Succ(e1) satisfies EdgeLeq(e1,e2) 681cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * at any valid location of the sweep event 691cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * - if EdgeLeq(e2,e1) as well (at any valid sweep event), then e1 and e2 701cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * share a common endpoint 711cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * - for each e, e->Dst has been processed, but not e->Org 721cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * - each edge e satisfies VertLeq(e->Dst,event) && VertLeq(event,e->Org) 731cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * where "event" is the current sweep line event. 741cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * - no edge e has zero length 751cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * 761cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * Invariants for the Mesh (the processed portion). 771cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * - the portion of the mesh left of the sweep line is a planar graph, 781cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * ie. there is *some* way to embed it in the plane 791cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * - no processed edge has zero length 801cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * - no two processed vertices have identical coordinates 811cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * - each "inside" region is monotone, ie. can be broken into two chains 821cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * of monotonically increasing vertices according to VertLeq(v1,v2) 831cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * - a non-invariant: these chains may intersect (very slightly) 841cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * 851cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * Invariants for the Sweep. 861cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * - if none of the edges incident to the event vertex have an activeRegion 871cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * (ie. none of these edges are in the edge dictionary), then the vertex 881cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * has only right-going edges. 891cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * - if an edge is marked "fixUpperEdge" (it is a temporary edge introduced 901cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * by ConnectRightVertex), then it is the only right-going edge from 911cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * its associated vertex. (This says that these edges exist only 921cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * when it is necessary.) 931cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger */ 941cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 951cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger#define MAX(x,y) ((x) >= (y) ? (x) : (y)) 961cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger#define MIN(x,y) ((x) <= (y) ? (x) : (y)) 971cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 981cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger/* When we merge two edges into one, we need to compute the combined 991cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * winding of the new edge. 1001cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger */ 1011cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger#define AddWinding(eDst,eSrc) (eDst->winding += eSrc->winding, \ 1021cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger eDst->Sym->winding += eSrc->Sym->winding) 1031cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 1041cab2921ab279367f8206cdadc9259d12e603548Derek Sollenbergerstatic void SweepEvent( GLUtesselator *tess, GLUvertex *vEvent ); 1051cab2921ab279367f8206cdadc9259d12e603548Derek Sollenbergerstatic void WalkDirtyRegions( GLUtesselator *tess, ActiveRegion *regUp ); 1061cab2921ab279367f8206cdadc9259d12e603548Derek Sollenbergerstatic int CheckForRightSplice( GLUtesselator *tess, ActiveRegion *regUp ); 1071cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 1081cab2921ab279367f8206cdadc9259d12e603548Derek Sollenbergerstatic int EdgeLeq( GLUtesselator *tess, ActiveRegion *reg1, 1091cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger ActiveRegion *reg2 ) 1101cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger/* 1111cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * Both edges must be directed from right to left (this is the canonical 1121cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * direction for the upper edge of each region). 1131cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * 1141cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * The strategy is to evaluate a "t" value for each edge at the 1151cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * current sweep line position, given by tess->event. The calculations 1161cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * are designed to be very stable, but of course they are not perfect. 1171cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * 1181cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * Special case: if both edge destinations are at the sweep event, 1191cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * we sort the edges by slope (they would otherwise compare equally). 1201cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger */ 1211cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger{ 1221cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger GLUvertex *event = tess->event; 1231cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger GLUhalfEdge *e1, *e2; 1241cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger GLdouble t1, t2; 1251cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 1261cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger e1 = reg1->eUp; 1271cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger e2 = reg2->eUp; 1281cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 1291cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if( e1->Dst == event ) { 1301cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if( e2->Dst == event ) { 1311cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger /* Two edges right of the sweep line which meet at the sweep event. 1321cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * Sort them by slope. 1331cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger */ 1341cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if( VertLeq( e1->Org, e2->Org )) { 1351cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger return EdgeSign( e2->Dst, e1->Org, e2->Org ) <= 0; 1361cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger } 1371cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger return EdgeSign( e1->Dst, e2->Org, e1->Org ) >= 0; 1381cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger } 1391cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger return EdgeSign( e2->Dst, event, e2->Org ) <= 0; 1401cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger } 1411cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if( e2->Dst == event ) { 1421cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger return EdgeSign( e1->Dst, event, e1->Org ) >= 0; 1431cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger } 1441cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 1451cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger /* General case - compute signed distance *from* e1, e2 to event */ 1461cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger t1 = EdgeEval( e1->Dst, event, e1->Org ); 1471cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger t2 = EdgeEval( e2->Dst, event, e2->Org ); 1481cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger return (t1 >= t2); 1491cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger} 1501cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 1511cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 1521cab2921ab279367f8206cdadc9259d12e603548Derek Sollenbergerstatic void DeleteRegion( GLUtesselator *tess, ActiveRegion *reg ) 1531cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger{ 1541cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if( reg->fixUpperEdge ) { 1551cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger /* It was created with zero winding number, so it better be 1561cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * deleted with zero winding number (ie. it better not get merged 1571cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * with a real edge). 1581cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger */ 1591cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger assert( reg->eUp->winding == 0 ); 1601cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger } 1611cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger reg->eUp->activeRegion = NULL; 1621cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger dictDelete( tess->dict, reg->nodeUp ); /* __gl_dictListDelete */ 1631cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger memFree( reg ); 1641cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger} 1651cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 1661cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 1671cab2921ab279367f8206cdadc9259d12e603548Derek Sollenbergerstatic int FixUpperEdge( ActiveRegion *reg, GLUhalfEdge *newEdge ) 1681cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger/* 1691cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * Replace an upper edge which needs fixing (see ConnectRightVertex). 1701cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger */ 1711cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger{ 1721cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger assert( reg->fixUpperEdge ); 1731cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if ( !__gl_meshDelete( reg->eUp ) ) return 0; 1741cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger reg->fixUpperEdge = FALSE; 1751cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger reg->eUp = newEdge; 1761cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger newEdge->activeRegion = reg; 1771cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 1781cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger return 1; 1791cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger} 1801cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 1811cab2921ab279367f8206cdadc9259d12e603548Derek Sollenbergerstatic ActiveRegion *TopLeftRegion( ActiveRegion *reg ) 1821cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger{ 1831cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger GLUvertex *org = reg->eUp->Org; 1841cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger GLUhalfEdge *e; 1851cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 1861cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger /* Find the region above the uppermost edge with the same origin */ 1871cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger do { 1881cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger reg = RegionAbove( reg ); 1891cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger } while( reg->eUp->Org == org ); 1901cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 1911cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger /* If the edge above was a temporary edge introduced by ConnectRightVertex, 1921cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * now is the time to fix it. 1931cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger */ 1941cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if( reg->fixUpperEdge ) { 1951cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger e = __gl_meshConnect( RegionBelow(reg)->eUp->Sym, reg->eUp->Lnext ); 1961cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if (e == NULL) return NULL; 1971cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if ( !FixUpperEdge( reg, e ) ) return NULL; 1981cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger reg = RegionAbove( reg ); 1991cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger } 2001cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger return reg; 2011cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger} 2021cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 2031cab2921ab279367f8206cdadc9259d12e603548Derek Sollenbergerstatic ActiveRegion *TopRightRegion( ActiveRegion *reg ) 2041cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger{ 2051cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger GLUvertex *dst = reg->eUp->Dst; 2061cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 2071cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger /* Find the region above the uppermost edge with the same destination */ 2081cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger do { 2091cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger reg = RegionAbove( reg ); 2101cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger } while( reg->eUp->Dst == dst ); 2111cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger return reg; 2121cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger} 2131cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 2141cab2921ab279367f8206cdadc9259d12e603548Derek Sollenbergerstatic ActiveRegion *AddRegionBelow( GLUtesselator *tess, 2151cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger ActiveRegion *regAbove, 2161cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger GLUhalfEdge *eNewUp ) 2171cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger/* 2181cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * Add a new active region to the sweep line, *somewhere* below "regAbove" 2191cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * (according to where the new edge belongs in the sweep-line dictionary). 2201cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * The upper edge of the new region will be "eNewUp". 2211cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * Winding number and "inside" flag are not updated. 2221cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger */ 2231cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger{ 2241cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger ActiveRegion *regNew = (ActiveRegion *)memAlloc( sizeof( ActiveRegion )); 2251cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if (regNew == NULL) longjmp(tess->env,1); 2261cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 2271cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger regNew->eUp = eNewUp; 2281cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger /* __gl_dictListInsertBefore */ 2291cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger regNew->nodeUp = dictInsertBefore( tess->dict, regAbove->nodeUp, regNew ); 2301cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if (regNew->nodeUp == NULL) longjmp(tess->env,1); 2311cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger regNew->fixUpperEdge = FALSE; 2321cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger regNew->sentinel = FALSE; 2331cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger regNew->dirty = FALSE; 2341cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 2351cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger eNewUp->activeRegion = regNew; 2361cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger return regNew; 2371cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger} 2381cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 2391cab2921ab279367f8206cdadc9259d12e603548Derek Sollenbergerstatic GLboolean IsWindingInside( GLUtesselator *tess, int n ) 2401cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger{ 2411cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger switch( tess->windingRule ) { 2421cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger case GLU_TESS_WINDING_ODD: 2431cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger return (n & 1); 2441cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger case GLU_TESS_WINDING_NONZERO: 2451cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger return (n != 0); 2461cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger case GLU_TESS_WINDING_POSITIVE: 2471cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger return (n > 0); 2481cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger case GLU_TESS_WINDING_NEGATIVE: 2491cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger return (n < 0); 2501cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger case GLU_TESS_WINDING_ABS_GEQ_TWO: 2511cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger return (n >= 2) || (n <= -2); 2521cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger } 2531cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger /*LINTED*/ 2541cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger assert( FALSE ); 2551cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger /*NOTREACHED*/ 2561cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger return 0; 2571cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger} 2581cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 2591cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 2601cab2921ab279367f8206cdadc9259d12e603548Derek Sollenbergerstatic void ComputeWinding( GLUtesselator *tess, ActiveRegion *reg ) 2611cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger{ 2621cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger reg->windingNumber = RegionAbove(reg)->windingNumber + reg->eUp->winding; 2631cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger reg->inside = IsWindingInside( tess, reg->windingNumber ); 2641cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger} 2651cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 2661cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 2671cab2921ab279367f8206cdadc9259d12e603548Derek Sollenbergerstatic void FinishRegion( GLUtesselator *tess, ActiveRegion *reg ) 2681cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger/* 2691cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * Delete a region from the sweep line. This happens when the upper 2701cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * and lower chains of a region meet (at a vertex on the sweep line). 2711cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * The "inside" flag is copied to the appropriate mesh face (we could 2721cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * not do this before -- since the structure of the mesh is always 2731cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * changing, this face may not have even existed until now). 2741cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger */ 2751cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger{ 2761cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger GLUhalfEdge *e = reg->eUp; 2771cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger GLUface *f = e->Lface; 2781cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 2791cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger f->inside = reg->inside; 2801cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger f->anEdge = e; /* optimization for __gl_meshTessellateMonoRegion() */ 2811cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger DeleteRegion( tess, reg ); 2821cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger} 2831cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 2841cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 2851cab2921ab279367f8206cdadc9259d12e603548Derek Sollenbergerstatic GLUhalfEdge *FinishLeftRegions( GLUtesselator *tess, 2861cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger ActiveRegion *regFirst, ActiveRegion *regLast ) 2871cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger/* 2881cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * We are given a vertex with one or more left-going edges. All affected 2891cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * edges should be in the edge dictionary. Starting at regFirst->eUp, 2901cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * we walk down deleting all regions where both edges have the same 2911cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * origin vOrg. At the same time we copy the "inside" flag from the 2921cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * active region to the face, since at this point each face will belong 2931cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * to at most one region (this was not necessarily true until this point 2941cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * in the sweep). The walk stops at the region above regLast; if regLast 2951cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * is NULL we walk as far as possible. At the same time we relink the 2961cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * mesh if necessary, so that the ordering of edges around vOrg is the 2971cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * same as in the dictionary. 2981cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger */ 2991cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger{ 3001cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger ActiveRegion *reg, *regPrev; 3011cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger GLUhalfEdge *e, *ePrev; 3021cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 3031cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger regPrev = regFirst; 3041cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger ePrev = regFirst->eUp; 3051cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger while( regPrev != regLast ) { 3061cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger regPrev->fixUpperEdge = FALSE; /* placement was OK */ 3071cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger reg = RegionBelow( regPrev ); 3081cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger e = reg->eUp; 3091cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if( e->Org != ePrev->Org ) { 3101cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if( ! reg->fixUpperEdge ) { 3111cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger /* Remove the last left-going edge. Even though there are no further 3121cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * edges in the dictionary with this origin, there may be further 3131cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * such edges in the mesh (if we are adding left edges to a vertex 3141cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * that has already been processed). Thus it is important to call 3151cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * FinishRegion rather than just DeleteRegion. 3161cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger */ 3171cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger FinishRegion( tess, regPrev ); 3181cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger break; 3191cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger } 3201cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger /* If the edge below was a temporary edge introduced by 3211cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * ConnectRightVertex, now is the time to fix it. 3221cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger */ 3231cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger e = __gl_meshConnect( ePrev->Lprev, e->Sym ); 3241cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if (e == NULL) longjmp(tess->env,1); 3251cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if ( !FixUpperEdge( reg, e ) ) longjmp(tess->env,1); 3261cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger } 3271cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 3281cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger /* Relink edges so that ePrev->Onext == e */ 3291cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if( ePrev->Onext != e ) { 3301cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if ( !__gl_meshSplice( e->Oprev, e ) ) longjmp(tess->env,1); 3311cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if ( !__gl_meshSplice( ePrev, e ) ) longjmp(tess->env,1); 3321cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger } 3331cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger FinishRegion( tess, regPrev ); /* may change reg->eUp */ 3341cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger ePrev = reg->eUp; 3351cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger regPrev = reg; 3361cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger } 3371cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger return ePrev; 3381cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger} 3391cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 3401cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 3411cab2921ab279367f8206cdadc9259d12e603548Derek Sollenbergerstatic void AddRightEdges( GLUtesselator *tess, ActiveRegion *regUp, 3421cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger GLUhalfEdge *eFirst, GLUhalfEdge *eLast, GLUhalfEdge *eTopLeft, 3431cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger GLboolean cleanUp ) 3441cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger/* 3451cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * Purpose: insert right-going edges into the edge dictionary, and update 3461cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * winding numbers and mesh connectivity appropriately. All right-going 3471cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * edges share a common origin vOrg. Edges are inserted CCW starting at 3481cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * eFirst; the last edge inserted is eLast->Oprev. If vOrg has any 3491cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * left-going edges already processed, then eTopLeft must be the edge 3501cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * such that an imaginary upward vertical segment from vOrg would be 3511cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * contained between eTopLeft->Oprev and eTopLeft; otherwise eTopLeft 3521cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * should be NULL. 3531cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger */ 3541cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger{ 3551cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger ActiveRegion *reg, *regPrev; 3561cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger GLUhalfEdge *e, *ePrev; 3571cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger int firstTime = TRUE; 3581cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 3591cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger /* Insert the new right-going edges in the dictionary */ 3601cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger e = eFirst; 3611cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger do { 3621cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger assert( VertLeq( e->Org, e->Dst )); 3631cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger AddRegionBelow( tess, regUp, e->Sym ); 3641cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger e = e->Onext; 3651cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger } while ( e != eLast ); 3661cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 3671cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger /* Walk *all* right-going edges from e->Org, in the dictionary order, 3681cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * updating the winding numbers of each region, and re-linking the mesh 3691cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * edges to match the dictionary ordering (if necessary). 3701cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger */ 3711cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if( eTopLeft == NULL ) { 3721cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger eTopLeft = RegionBelow( regUp )->eUp->Rprev; 3731cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger } 3741cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger regPrev = regUp; 3751cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger ePrev = eTopLeft; 3761cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger for( ;; ) { 3771cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger reg = RegionBelow( regPrev ); 3781cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger e = reg->eUp->Sym; 3791cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if( e->Org != ePrev->Org ) break; 3801cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 3811cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if( e->Onext != ePrev ) { 3821cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger /* Unlink e from its current position, and relink below ePrev */ 3831cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if ( !__gl_meshSplice( e->Oprev, e ) ) longjmp(tess->env,1); 3841cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if ( !__gl_meshSplice( ePrev->Oprev, e ) ) longjmp(tess->env,1); 3851cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger } 3861cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger /* Compute the winding number and "inside" flag for the new regions */ 3871cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger reg->windingNumber = regPrev->windingNumber - e->winding; 3881cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger reg->inside = IsWindingInside( tess, reg->windingNumber ); 3891cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 3901cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger /* Check for two outgoing edges with same slope -- process these 3911cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * before any intersection tests (see example in __gl_computeInterior). 3921cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger */ 3931cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger regPrev->dirty = TRUE; 3941cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if( ! firstTime && CheckForRightSplice( tess, regPrev )) { 3951cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger AddWinding( e, ePrev ); 3961cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger DeleteRegion( tess, regPrev ); 3971cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if ( !__gl_meshDelete( ePrev ) ) longjmp(tess->env,1); 3981cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger } 3991cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger firstTime = FALSE; 4001cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger regPrev = reg; 4011cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger ePrev = e; 4021cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger } 4031cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger regPrev->dirty = TRUE; 4041cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger assert( regPrev->windingNumber - e->winding == reg->windingNumber ); 4051cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 4061cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if( cleanUp ) { 4071cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger /* Check for intersections between newly adjacent edges. */ 4081cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger WalkDirtyRegions( tess, regPrev ); 4091cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger } 4101cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger} 4111cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 4121cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 4131cab2921ab279367f8206cdadc9259d12e603548Derek Sollenbergerstatic void CallCombine( GLUtesselator *tess, GLUvertex *isect, 4141cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger void *data[4], GLfloat weights[4], int needed ) 4151cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger{ 4161cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger GLdouble coords[3]; 4171cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 4181cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger /* Copy coord data in case the callback changes it. */ 4191cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger coords[0] = isect->coords[0]; 4201cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger coords[1] = isect->coords[1]; 4211cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger coords[2] = isect->coords[2]; 4221cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 4231cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger isect->data = NULL; 4241cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger CALL_COMBINE_OR_COMBINE_DATA( coords, data, weights, &isect->data ); 4251cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if( isect->data == NULL ) { 4261cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if( ! needed ) { 4271cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger isect->data = data[0]; 4281cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger } else if( ! tess->fatalError ) { 4291cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger /* The only way fatal error is when two edges are found to intersect, 4301cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * but the user has not provided the callback necessary to handle 4311cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * generated intersection points. 4321cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger */ 4331cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger CALL_ERROR_OR_ERROR_DATA( GLU_TESS_NEED_COMBINE_CALLBACK ); 4341cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger tess->fatalError = TRUE; 4351cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger } 4361cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger } 4371cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger} 4381cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 4391cab2921ab279367f8206cdadc9259d12e603548Derek Sollenbergerstatic void SpliceMergeVertices( GLUtesselator *tess, GLUhalfEdge *e1, 4401cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger GLUhalfEdge *e2 ) 4411cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger/* 4421cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * Two vertices with idential coordinates are combined into one. 4431cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * e1->Org is kept, while e2->Org is discarded. 4441cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger */ 4451cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger{ 4461cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger void *data[4] = { NULL, NULL, NULL, NULL }; 4471cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger GLfloat weights[4] = { 0.5, 0.5, 0.0, 0.0 }; 4481cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 4491cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger data[0] = e1->Org->data; 4501cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger data[1] = e2->Org->data; 4511cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger CallCombine( tess, e1->Org, data, weights, FALSE ); 4521cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if ( !__gl_meshSplice( e1, e2 ) ) longjmp(tess->env,1); 4531cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger} 4541cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 4551cab2921ab279367f8206cdadc9259d12e603548Derek Sollenbergerstatic void VertexWeights( GLUvertex *isect, GLUvertex *org, GLUvertex *dst, 4561cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger GLfloat *weights ) 4571cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger/* 4581cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * Find some weights which describe how the intersection vertex is 4591cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * a linear combination of "org" and "dest". Each of the two edges 4601cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * which generated "isect" is allocated 50% of the weight; each edge 4611cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * splits the weight between its org and dst according to the 4621cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * relative distance to "isect". 4631cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger */ 4641cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger{ 4651cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger GLdouble t1 = VertL1dist( org, isect ); 4661cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger GLdouble t2 = VertL1dist( dst, isect ); 4671cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 4681cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger weights[0] = 0.5 * t2 / (t1 + t2); 4691cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger weights[1] = 0.5 * t1 / (t1 + t2); 4701cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger isect->coords[0] += weights[0]*org->coords[0] + weights[1]*dst->coords[0]; 4711cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger isect->coords[1] += weights[0]*org->coords[1] + weights[1]*dst->coords[1]; 4721cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger isect->coords[2] += weights[0]*org->coords[2] + weights[1]*dst->coords[2]; 4731cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger} 4741cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 4751cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 4761cab2921ab279367f8206cdadc9259d12e603548Derek Sollenbergerstatic void GetIntersectData( GLUtesselator *tess, GLUvertex *isect, 4771cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger GLUvertex *orgUp, GLUvertex *dstUp, 4781cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger GLUvertex *orgLo, GLUvertex *dstLo ) 4791cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger/* 4801cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * We've computed a new intersection point, now we need a "data" pointer 4811cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * from the user so that we can refer to this new vertex in the 4821cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * rendering callbacks. 4831cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger */ 4841cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger{ 4851cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger void *data[4]; 4861cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger GLfloat weights[4]; 4871cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 4881cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger data[0] = orgUp->data; 4891cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger data[1] = dstUp->data; 4901cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger data[2] = orgLo->data; 4911cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger data[3] = dstLo->data; 4921cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 4931cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger isect->coords[0] = isect->coords[1] = isect->coords[2] = 0; 4941cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger VertexWeights( isect, orgUp, dstUp, &weights[0] ); 4951cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger VertexWeights( isect, orgLo, dstLo, &weights[2] ); 4961cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 4971cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger CallCombine( tess, isect, data, weights, TRUE ); 4981cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger} 4991cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 5001cab2921ab279367f8206cdadc9259d12e603548Derek Sollenbergerstatic int CheckForRightSplice( GLUtesselator *tess, ActiveRegion *regUp ) 5011cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger/* 5021cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * Check the upper and lower edge of "regUp", to make sure that the 5031cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * eUp->Org is above eLo, or eLo->Org is below eUp (depending on which 5041cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * origin is leftmost). 5051cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * 5061cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * The main purpose is to splice right-going edges with the same 5071cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * dest vertex and nearly identical slopes (ie. we can't distinguish 5081cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * the slopes numerically). However the splicing can also help us 5091cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * to recover from numerical errors. For example, suppose at one 5101cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * point we checked eUp and eLo, and decided that eUp->Org is barely 5111cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * above eLo. Then later, we split eLo into two edges (eg. from 5121cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * a splice operation like this one). This can change the result of 5131cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * our test so that now eUp->Org is incident to eLo, or barely below it. 5141cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * We must correct this condition to maintain the dictionary invariants. 5151cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * 5161cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * One possibility is to check these edges for intersection again 5171cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * (ie. CheckForIntersect). This is what we do if possible. However 5181cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * CheckForIntersect requires that tess->event lies between eUp and eLo, 5191cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * so that it has something to fall back on when the intersection 5201cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * calculation gives us an unusable answer. So, for those cases where 5211cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * we can't check for intersection, this routine fixes the problem 5221cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * by just splicing the offending vertex into the other edge. 5231cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * This is a guaranteed solution, no matter how degenerate things get. 5241cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * Basically this is a combinatorial solution to a numerical problem. 5251cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger */ 5261cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger{ 5271cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger ActiveRegion *regLo = RegionBelow(regUp); 5281cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger GLUhalfEdge *eUp = regUp->eUp; 5291cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger GLUhalfEdge *eLo = regLo->eUp; 5301cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 5311cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if( VertLeq( eUp->Org, eLo->Org )) { 5321cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if( EdgeSign( eLo->Dst, eUp->Org, eLo->Org ) > 0 ) return FALSE; 5331cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 5341cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger /* eUp->Org appears to be below eLo */ 5351cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if( ! VertEq( eUp->Org, eLo->Org )) { 5361cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger /* Splice eUp->Org into eLo */ 5371cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if ( __gl_meshSplitEdge( eLo->Sym ) == NULL) longjmp(tess->env,1); 5381cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if ( !__gl_meshSplice( eUp, eLo->Oprev ) ) longjmp(tess->env,1); 5391cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger regUp->dirty = regLo->dirty = TRUE; 5401cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 5411cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger } else if( eUp->Org != eLo->Org ) { 5421cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger /* merge the two vertices, discarding eUp->Org */ 5431cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger pqDelete( tess->pq, eUp->Org->pqHandle ); /* __gl_pqSortDelete */ 5441cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger SpliceMergeVertices( tess, eLo->Oprev, eUp ); 5451cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger } 5461cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger } else { 5471cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if( EdgeSign( eUp->Dst, eLo->Org, eUp->Org ) < 0 ) return FALSE; 5481cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 5491cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger /* eLo->Org appears to be above eUp, so splice eLo->Org into eUp */ 5501cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger RegionAbove(regUp)->dirty = regUp->dirty = TRUE; 5511cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if (__gl_meshSplitEdge( eUp->Sym ) == NULL) longjmp(tess->env,1); 5521cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if ( !__gl_meshSplice( eLo->Oprev, eUp ) ) longjmp(tess->env,1); 5531cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger } 5541cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger return TRUE; 5551cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger} 5561cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 5571cab2921ab279367f8206cdadc9259d12e603548Derek Sollenbergerstatic int CheckForLeftSplice( GLUtesselator *tess, ActiveRegion *regUp ) 5581cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger/* 5591cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * Check the upper and lower edge of "regUp", to make sure that the 5601cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * eUp->Dst is above eLo, or eLo->Dst is below eUp (depending on which 5611cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * destination is rightmost). 5621cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * 5631cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * Theoretically, this should always be true. However, splitting an edge 5641cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * into two pieces can change the results of previous tests. For example, 5651cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * suppose at one point we checked eUp and eLo, and decided that eUp->Dst 5661cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * is barely above eLo. Then later, we split eLo into two edges (eg. from 5671cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * a splice operation like this one). This can change the result of 5681cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * the test so that now eUp->Dst is incident to eLo, or barely below it. 5691cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * We must correct this condition to maintain the dictionary invariants 5701cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * (otherwise new edges might get inserted in the wrong place in the 5711cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * dictionary, and bad stuff will happen). 5721cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * 5731cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * We fix the problem by just splicing the offending vertex into the 5741cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * other edge. 5751cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger */ 5761cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger{ 5771cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger ActiveRegion *regLo = RegionBelow(regUp); 5781cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger GLUhalfEdge *eUp = regUp->eUp; 5791cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger GLUhalfEdge *eLo = regLo->eUp; 5801cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger GLUhalfEdge *e; 5811cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 5821cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger assert( ! VertEq( eUp->Dst, eLo->Dst )); 5831cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 5841cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if( VertLeq( eUp->Dst, eLo->Dst )) { 5851cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if( EdgeSign( eUp->Dst, eLo->Dst, eUp->Org ) < 0 ) return FALSE; 5861cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 5871cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger /* eLo->Dst is above eUp, so splice eLo->Dst into eUp */ 5881cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger RegionAbove(regUp)->dirty = regUp->dirty = TRUE; 5891cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger e = __gl_meshSplitEdge( eUp ); 5901cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if (e == NULL) longjmp(tess->env,1); 5911cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if ( !__gl_meshSplice( eLo->Sym, e ) ) longjmp(tess->env,1); 5921cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger e->Lface->inside = regUp->inside; 5931cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger } else { 5941cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if( EdgeSign( eLo->Dst, eUp->Dst, eLo->Org ) > 0 ) return FALSE; 5951cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 5961cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger /* eUp->Dst is below eLo, so splice eUp->Dst into eLo */ 5971cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger regUp->dirty = regLo->dirty = TRUE; 5981cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger e = __gl_meshSplitEdge( eLo ); 5991cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if (e == NULL) longjmp(tess->env,1); 6001cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if ( !__gl_meshSplice( eUp->Lnext, eLo->Sym ) ) longjmp(tess->env,1); 6011cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger e->Rface->inside = regUp->inside; 6021cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger } 6031cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger return TRUE; 6041cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger} 6051cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 6061cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 6071cab2921ab279367f8206cdadc9259d12e603548Derek Sollenbergerstatic int CheckForIntersect( GLUtesselator *tess, ActiveRegion *regUp ) 6081cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger/* 6091cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * Check the upper and lower edges of the given region to see if 6101cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * they intersect. If so, create the intersection and add it 6111cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * to the data structures. 6121cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * 6131cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * Returns TRUE if adding the new intersection resulted in a recursive 6141cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * call to AddRightEdges(); in this case all "dirty" regions have been 6151cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * checked for intersections, and possibly regUp has been deleted. 6161cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger */ 6171cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger{ 6181cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger ActiveRegion *regLo = RegionBelow(regUp); 6191cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger GLUhalfEdge *eUp = regUp->eUp; 6201cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger GLUhalfEdge *eLo = regLo->eUp; 6211cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger GLUvertex *orgUp = eUp->Org; 6221cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger GLUvertex *orgLo = eLo->Org; 6231cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger GLUvertex *dstUp = eUp->Dst; 6241cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger GLUvertex *dstLo = eLo->Dst; 6251cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger GLdouble tMinUp, tMaxLo; 6261cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger GLUvertex isect, *orgMin; 6271cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger GLUhalfEdge *e; 6281cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 6291cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger assert( ! VertEq( dstLo, dstUp )); 6301cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger assert( EdgeSign( dstUp, tess->event, orgUp ) <= 0 ); 6311cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger assert( EdgeSign( dstLo, tess->event, orgLo ) >= 0 ); 6321cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger assert( orgUp != tess->event && orgLo != tess->event ); 6331cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger assert( ! regUp->fixUpperEdge && ! regLo->fixUpperEdge ); 6341cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 6351cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if( orgUp == orgLo ) return FALSE; /* right endpoints are the same */ 6361cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 6371cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger tMinUp = MIN( orgUp->t, dstUp->t ); 6381cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger tMaxLo = MAX( orgLo->t, dstLo->t ); 6391cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if( tMinUp > tMaxLo ) return FALSE; /* t ranges do not overlap */ 6401cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 6411cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if( VertLeq( orgUp, orgLo )) { 6421cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if( EdgeSign( dstLo, orgUp, orgLo ) > 0 ) return FALSE; 6431cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger } else { 6441cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if( EdgeSign( dstUp, orgLo, orgUp ) < 0 ) return FALSE; 6451cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger } 6461cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 6471cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger /* At this point the edges intersect, at least marginally */ 6481cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger DebugEvent( tess ); 6491cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 6501cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger __gl_edgeIntersect( dstUp, orgUp, dstLo, orgLo, &isect ); 6511cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger /* The following properties are guaranteed: */ 6521cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger assert( MIN( orgUp->t, dstUp->t ) <= isect.t ); 6531cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger assert( isect.t <= MAX( orgLo->t, dstLo->t )); 6541cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger assert( MIN( dstLo->s, dstUp->s ) <= isect.s ); 6551cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger assert( isect.s <= MAX( orgLo->s, orgUp->s )); 6561cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 6571cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if( VertLeq( &isect, tess->event )) { 6581cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger /* The intersection point lies slightly to the left of the sweep line, 6591cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * so move it until it''s slightly to the right of the sweep line. 6601cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * (If we had perfect numerical precision, this would never happen 6611cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * in the first place). The easiest and safest thing to do is 6621cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * replace the intersection by tess->event. 6631cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger */ 6641cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger isect.s = tess->event->s; 6651cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger isect.t = tess->event->t; 6661cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger } 6671cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger /* Similarly, if the computed intersection lies to the right of the 6681cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * rightmost origin (which should rarely happen), it can cause 6691cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * unbelievable inefficiency on sufficiently degenerate inputs. 6701cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * (If you have the test program, try running test54.d with the 6711cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * "X zoom" option turned on). 6721cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger */ 6731cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger orgMin = VertLeq( orgUp, orgLo ) ? orgUp : orgLo; 6741cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if( VertLeq( orgMin, &isect )) { 6751cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger isect.s = orgMin->s; 6761cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger isect.t = orgMin->t; 6771cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger } 6781cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 6791cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if( VertEq( &isect, orgUp ) || VertEq( &isect, orgLo )) { 6801cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger /* Easy case -- intersection at one of the right endpoints */ 6811cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger (void) CheckForRightSplice( tess, regUp ); 6821cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger return FALSE; 6831cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger } 6841cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 6851cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if( (! VertEq( dstUp, tess->event ) 6861cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger && EdgeSign( dstUp, tess->event, &isect ) >= 0) 6871cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger || (! VertEq( dstLo, tess->event ) 6881cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger && EdgeSign( dstLo, tess->event, &isect ) <= 0 )) 6891cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger { 6901cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger /* Very unusual -- the new upper or lower edge would pass on the 6911cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * wrong side of the sweep event, or through it. This can happen 6921cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * due to very small numerical errors in the intersection calculation. 6931cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger */ 6941cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if( dstLo == tess->event ) { 6951cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger /* Splice dstLo into eUp, and process the new region(s) */ 6961cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if (__gl_meshSplitEdge( eUp->Sym ) == NULL) longjmp(tess->env,1); 6971cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if ( !__gl_meshSplice( eLo->Sym, eUp ) ) longjmp(tess->env,1); 6981cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger regUp = TopLeftRegion( regUp ); 6991cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if (regUp == NULL) longjmp(tess->env,1); 7001cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger eUp = RegionBelow(regUp)->eUp; 7011cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger FinishLeftRegions( tess, RegionBelow(regUp), regLo ); 7021cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger AddRightEdges( tess, regUp, eUp->Oprev, eUp, eUp, TRUE ); 7031cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger return TRUE; 7041cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger } 7051cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if( dstUp == tess->event ) { 7061cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger /* Splice dstUp into eLo, and process the new region(s) */ 7071cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if (__gl_meshSplitEdge( eLo->Sym ) == NULL) longjmp(tess->env,1); 7081cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if ( !__gl_meshSplice( eUp->Lnext, eLo->Oprev ) ) longjmp(tess->env,1); 7091cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger regLo = regUp; 7101cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger regUp = TopRightRegion( regUp ); 7111cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger e = RegionBelow(regUp)->eUp->Rprev; 7121cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger regLo->eUp = eLo->Oprev; 7131cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger eLo = FinishLeftRegions( tess, regLo, NULL ); 7141cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger AddRightEdges( tess, regUp, eLo->Onext, eUp->Rprev, e, TRUE ); 7151cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger return TRUE; 7161cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger } 7171cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger /* Special case: called from ConnectRightVertex. If either 7181cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * edge passes on the wrong side of tess->event, split it 7191cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * (and wait for ConnectRightVertex to splice it appropriately). 7201cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger */ 7211cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if( EdgeSign( dstUp, tess->event, &isect ) >= 0 ) { 7221cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger RegionAbove(regUp)->dirty = regUp->dirty = TRUE; 7231cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if (__gl_meshSplitEdge( eUp->Sym ) == NULL) longjmp(tess->env,1); 7241cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger eUp->Org->s = tess->event->s; 7251cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger eUp->Org->t = tess->event->t; 7261cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger } 7271cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if( EdgeSign( dstLo, tess->event, &isect ) <= 0 ) { 7281cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger regUp->dirty = regLo->dirty = TRUE; 7291cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if (__gl_meshSplitEdge( eLo->Sym ) == NULL) longjmp(tess->env,1); 7301cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger eLo->Org->s = tess->event->s; 7311cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger eLo->Org->t = tess->event->t; 7321cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger } 7331cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger /* leave the rest for ConnectRightVertex */ 7341cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger return FALSE; 7351cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger } 7361cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 7371cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger /* General case -- split both edges, splice into new vertex. 7381cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * When we do the splice operation, the order of the arguments is 7391cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * arbitrary as far as correctness goes. However, when the operation 7401cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * creates a new face, the work done is proportional to the size of 7411cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * the new face. We expect the faces in the processed part of 7421cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * the mesh (ie. eUp->Lface) to be smaller than the faces in the 7431cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * unprocessed original contours (which will be eLo->Oprev->Lface). 7441cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger */ 7451cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if (__gl_meshSplitEdge( eUp->Sym ) == NULL) longjmp(tess->env,1); 7461cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if (__gl_meshSplitEdge( eLo->Sym ) == NULL) longjmp(tess->env,1); 7471cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if ( !__gl_meshSplice( eLo->Oprev, eUp ) ) longjmp(tess->env,1); 7481cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger eUp->Org->s = isect.s; 7491cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger eUp->Org->t = isect.t; 7501cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger eUp->Org->pqHandle = pqInsert( tess->pq, eUp->Org ); /* __gl_pqSortInsert */ 7511cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if (eUp->Org->pqHandle == LONG_MAX) { 7521cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger pqDeletePriorityQ(tess->pq); /* __gl_pqSortDeletePriorityQ */ 7531cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger tess->pq = NULL; 7541cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger longjmp(tess->env,1); 7551cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger } 7561cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger GetIntersectData( tess, eUp->Org, orgUp, dstUp, orgLo, dstLo ); 7571cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger RegionAbove(regUp)->dirty = regUp->dirty = regLo->dirty = TRUE; 7581cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger return FALSE; 7591cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger} 7601cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 7611cab2921ab279367f8206cdadc9259d12e603548Derek Sollenbergerstatic void WalkDirtyRegions( GLUtesselator *tess, ActiveRegion *regUp ) 7621cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger/* 7631cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * When the upper or lower edge of any region changes, the region is 7641cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * marked "dirty". This routine walks through all the dirty regions 7651cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * and makes sure that the dictionary invariants are satisfied 7661cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * (see the comments at the beginning of this file). Of course 7671cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * new dirty regions can be created as we make changes to restore 7681cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * the invariants. 7691cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger */ 7701cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger{ 7711cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger ActiveRegion *regLo = RegionBelow(regUp); 7721cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger GLUhalfEdge *eUp, *eLo; 7731cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 7741cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger for( ;; ) { 7751cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger /* Find the lowest dirty region (we walk from the bottom up). */ 7761cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger while( regLo->dirty ) { 7771cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger regUp = regLo; 7781cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger regLo = RegionBelow(regLo); 7791cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger } 7801cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if( ! regUp->dirty ) { 7811cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger regLo = regUp; 7821cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger regUp = RegionAbove( regUp ); 7831cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if( regUp == NULL || ! regUp->dirty ) { 7841cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger /* We've walked all the dirty regions */ 7851cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger return; 7861cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger } 7871cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger } 7881cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger regUp->dirty = FALSE; 7891cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger eUp = regUp->eUp; 7901cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger eLo = regLo->eUp; 7911cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 7921cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if( eUp->Dst != eLo->Dst ) { 7931cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger /* Check that the edge ordering is obeyed at the Dst vertices. */ 7941cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if( CheckForLeftSplice( tess, regUp )) { 7951cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 7961cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger /* If the upper or lower edge was marked fixUpperEdge, then 7971cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * we no longer need it (since these edges are needed only for 7981cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * vertices which otherwise have no right-going edges). 7991cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger */ 8001cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if( regLo->fixUpperEdge ) { 8011cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger DeleteRegion( tess, regLo ); 8021cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if ( !__gl_meshDelete( eLo ) ) longjmp(tess->env,1); 8031cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger regLo = RegionBelow( regUp ); 8041cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger eLo = regLo->eUp; 8051cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger } else if( regUp->fixUpperEdge ) { 8061cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger DeleteRegion( tess, regUp ); 8071cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if ( !__gl_meshDelete( eUp ) ) longjmp(tess->env,1); 8081cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger regUp = RegionAbove( regLo ); 8091cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger eUp = regUp->eUp; 8101cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger } 8111cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger } 8121cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger } 8131cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if( eUp->Org != eLo->Org ) { 8141cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if( eUp->Dst != eLo->Dst 8151cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger && ! regUp->fixUpperEdge && ! regLo->fixUpperEdge 8161cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger && (eUp->Dst == tess->event || eLo->Dst == tess->event) ) 8171cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger { 8181cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger /* When all else fails in CheckForIntersect(), it uses tess->event 8191cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * as the intersection location. To make this possible, it requires 8201cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * that tess->event lie between the upper and lower edges, and also 8211cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * that neither of these is marked fixUpperEdge (since in the worst 8221cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * case it might splice one of these edges into tess->event, and 8231cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * violate the invariant that fixable edges are the only right-going 8241cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * edge from their associated vertex). 8251cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger */ 8261cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if( CheckForIntersect( tess, regUp )) { 8271cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger /* WalkDirtyRegions() was called recursively; we're done */ 8281cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger return; 8291cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger } 8301cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger } else { 8311cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger /* Even though we can't use CheckForIntersect(), the Org vertices 8321cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * may violate the dictionary edge ordering. Check and correct this. 8331cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger */ 8341cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger (void) CheckForRightSplice( tess, regUp ); 8351cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger } 8361cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger } 8371cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if( eUp->Org == eLo->Org && eUp->Dst == eLo->Dst ) { 8381cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger /* A degenerate loop consisting of only two edges -- delete it. */ 8391cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger AddWinding( eLo, eUp ); 8401cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger DeleteRegion( tess, regUp ); 8411cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if ( !__gl_meshDelete( eUp ) ) longjmp(tess->env,1); 8421cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger regUp = RegionAbove( regLo ); 8431cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger } 8441cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger } 8451cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger} 8461cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 8471cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 8481cab2921ab279367f8206cdadc9259d12e603548Derek Sollenbergerstatic void ConnectRightVertex( GLUtesselator *tess, ActiveRegion *regUp, 8491cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger GLUhalfEdge *eBottomLeft ) 8501cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger/* 8511cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * Purpose: connect a "right" vertex vEvent (one where all edges go left) 8521cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * to the unprocessed portion of the mesh. Since there are no right-going 8531cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * edges, two regions (one above vEvent and one below) are being merged 8541cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * into one. "regUp" is the upper of these two regions. 8551cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * 8561cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * There are two reasons for doing this (adding a right-going edge): 8571cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * - if the two regions being merged are "inside", we must add an edge 8581cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * to keep them separated (the combined region would not be monotone). 8591cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * - in any case, we must leave some record of vEvent in the dictionary, 8601cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * so that we can merge vEvent with features that we have not seen yet. 8611cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * For example, maybe there is a vertical edge which passes just to 8621cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * the right of vEvent; we would like to splice vEvent into this edge. 8631cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * 8641cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * However, we don't want to connect vEvent to just any vertex. We don''t 8651cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * want the new edge to cross any other edges; otherwise we will create 8661cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * intersection vertices even when the input data had no self-intersections. 8671cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * (This is a bad thing; if the user's input data has no intersections, 8681cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * we don't want to generate any false intersections ourselves.) 8691cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * 8701cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * Our eventual goal is to connect vEvent to the leftmost unprocessed 8711cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * vertex of the combined region (the union of regUp and regLo). 8721cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * But because of unseen vertices with all right-going edges, and also 8731cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * new vertices which may be created by edge intersections, we don''t 8741cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * know where that leftmost unprocessed vertex is. In the meantime, we 8751cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * connect vEvent to the closest vertex of either chain, and mark the region 8761cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * as "fixUpperEdge". This flag says to delete and reconnect this edge 8771cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * to the next processed vertex on the boundary of the combined region. 8781cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * Quite possibly the vertex we connected to will turn out to be the 8791cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * closest one, in which case we won''t need to make any changes. 8801cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger */ 8811cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger{ 8821cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger GLUhalfEdge *eNew; 8831cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger GLUhalfEdge *eTopLeft = eBottomLeft->Onext; 8841cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger ActiveRegion *regLo = RegionBelow(regUp); 8851cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger GLUhalfEdge *eUp = regUp->eUp; 8861cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger GLUhalfEdge *eLo = regLo->eUp; 8871cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger int degenerate = FALSE; 8881cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 8891cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if( eUp->Dst != eLo->Dst ) { 8901cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger (void) CheckForIntersect( tess, regUp ); 8911cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger } 8921cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 8931cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger /* Possible new degeneracies: upper or lower edge of regUp may pass 8941cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * through vEvent, or may coincide with new intersection vertex 8951cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger */ 8961cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if( VertEq( eUp->Org, tess->event )) { 8971cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if ( !__gl_meshSplice( eTopLeft->Oprev, eUp ) ) longjmp(tess->env,1); 8981cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger regUp = TopLeftRegion( regUp ); 8991cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if (regUp == NULL) longjmp(tess->env,1); 9001cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger eTopLeft = RegionBelow( regUp )->eUp; 9011cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger FinishLeftRegions( tess, RegionBelow(regUp), regLo ); 9021cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger degenerate = TRUE; 9031cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger } 9041cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if( VertEq( eLo->Org, tess->event )) { 9051cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if ( !__gl_meshSplice( eBottomLeft, eLo->Oprev ) ) longjmp(tess->env,1); 9061cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger eBottomLeft = FinishLeftRegions( tess, regLo, NULL ); 9071cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger degenerate = TRUE; 9081cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger } 9091cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if( degenerate ) { 9101cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger AddRightEdges( tess, regUp, eBottomLeft->Onext, eTopLeft, eTopLeft, TRUE ); 9111cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger return; 9121cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger } 9131cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 9141cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger /* Non-degenerate situation -- need to add a temporary, fixable edge. 9151cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * Connect to the closer of eLo->Org, eUp->Org. 9161cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger */ 9171cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if( VertLeq( eLo->Org, eUp->Org )) { 9181cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger eNew = eLo->Oprev; 9191cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger } else { 9201cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger eNew = eUp; 9211cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger } 9221cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger eNew = __gl_meshConnect( eBottomLeft->Lprev, eNew ); 9231cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if (eNew == NULL) longjmp(tess->env,1); 9241cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 9251cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger /* Prevent cleanup, otherwise eNew might disappear before we've even 9261cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * had a chance to mark it as a temporary edge. 9271cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger */ 9281cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger AddRightEdges( tess, regUp, eNew, eNew->Onext, eNew->Onext, FALSE ); 9291cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger eNew->Sym->activeRegion->fixUpperEdge = TRUE; 9301cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger WalkDirtyRegions( tess, regUp ); 9311cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger} 9321cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 9331cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger/* Because vertices at exactly the same location are merged together 9341cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * before we process the sweep event, some degenerate cases can't occur. 9351cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * However if someone eventually makes the modifications required to 9361cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * merge features which are close together, the cases below marked 9371cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * TOLERANCE_NONZERO will be useful. They were debugged before the 9381cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * code to merge identical vertices in the main loop was added. 9391cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger */ 9401cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger#define TOLERANCE_NONZERO FALSE 9411cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 9421cab2921ab279367f8206cdadc9259d12e603548Derek Sollenbergerstatic void ConnectLeftDegenerate( GLUtesselator *tess, 9431cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger ActiveRegion *regUp, GLUvertex *vEvent ) 9441cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger/* 9451cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * The event vertex lies exacty on an already-processed edge or vertex. 9461cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * Adding the new vertex involves splicing it into the already-processed 9471cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * part of the mesh. 9481cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger */ 9491cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger{ 9501cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger GLUhalfEdge *e, *eTopLeft, *eTopRight, *eLast; 9511cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger ActiveRegion *reg; 9521cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 9531cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger e = regUp->eUp; 9541cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if( VertEq( e->Org, vEvent )) { 9551cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger /* e->Org is an unprocessed vertex - just combine them, and wait 9561cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * for e->Org to be pulled from the queue 9571cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger */ 9581cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger assert( TOLERANCE_NONZERO ); 9591cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger SpliceMergeVertices( tess, e, vEvent->anEdge ); 9601cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger return; 9611cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger } 9621cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 9631cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if( ! VertEq( e->Dst, vEvent )) { 9641cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger /* General case -- splice vEvent into edge e which passes through it */ 9651cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if (__gl_meshSplitEdge( e->Sym ) == NULL) longjmp(tess->env,1); 9661cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if( regUp->fixUpperEdge ) { 9671cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger /* This edge was fixable -- delete unused portion of original edge */ 9681cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if ( !__gl_meshDelete( e->Onext ) ) longjmp(tess->env,1); 9691cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger regUp->fixUpperEdge = FALSE; 9701cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger } 9711cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if ( !__gl_meshSplice( vEvent->anEdge, e ) ) longjmp(tess->env,1); 9721cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger SweepEvent( tess, vEvent ); /* recurse */ 9731cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger return; 9741cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger } 9751cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 9761cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger /* vEvent coincides with e->Dst, which has already been processed. 9771cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * Splice in the additional right-going edges. 9781cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger */ 9791cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger assert( TOLERANCE_NONZERO ); 9801cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger regUp = TopRightRegion( regUp ); 9811cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger reg = RegionBelow( regUp ); 9821cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger eTopRight = reg->eUp->Sym; 9831cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger eTopLeft = eLast = eTopRight->Onext; 9841cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if( reg->fixUpperEdge ) { 9851cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger /* Here e->Dst has only a single fixable edge going right. 9861cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * We can delete it since now we have some real right-going edges. 9871cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger */ 9881cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger assert( eTopLeft != eTopRight ); /* there are some left edges too */ 9891cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger DeleteRegion( tess, reg ); 9901cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if ( !__gl_meshDelete( eTopRight ) ) longjmp(tess->env,1); 9911cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger eTopRight = eTopLeft->Oprev; 9921cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger } 9931cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if ( !__gl_meshSplice( vEvent->anEdge, eTopRight ) ) longjmp(tess->env,1); 9941cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if( ! EdgeGoesLeft( eTopLeft )) { 9951cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger /* e->Dst had no left-going edges -- indicate this to AddRightEdges() */ 9961cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger eTopLeft = NULL; 9971cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger } 9981cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger AddRightEdges( tess, regUp, eTopRight->Onext, eLast, eTopLeft, TRUE ); 9991cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger} 10001cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 10011cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 10021cab2921ab279367f8206cdadc9259d12e603548Derek Sollenbergerstatic void ConnectLeftVertex( GLUtesselator *tess, GLUvertex *vEvent ) 10031cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger/* 10041cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * Purpose: connect a "left" vertex (one where both edges go right) 10051cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * to the processed portion of the mesh. Let R be the active region 10061cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * containing vEvent, and let U and L be the upper and lower edge 10071cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * chains of R. There are two possibilities: 10081cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * 10091cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * - the normal case: split R into two regions, by connecting vEvent to 10101cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * the rightmost vertex of U or L lying to the left of the sweep line 10111cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * 10121cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * - the degenerate case: if vEvent is close enough to U or L, we 10131cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * merge vEvent into that edge chain. The subcases are: 10141cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * - merging with the rightmost vertex of U or L 10151cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * - merging with the active edge of U or L 10161cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * - merging with an already-processed portion of U or L 10171cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger */ 10181cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger{ 10191cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger ActiveRegion *regUp, *regLo, *reg; 10201cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger GLUhalfEdge *eUp, *eLo, *eNew; 10211cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger ActiveRegion tmp; 10221cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 10231cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger /* assert( vEvent->anEdge->Onext->Onext == vEvent->anEdge ); */ 10241cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 10251cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger /* Get a pointer to the active region containing vEvent */ 10261cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger tmp.eUp = vEvent->anEdge->Sym; 10271cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger /* __GL_DICTLISTKEY */ /* __gl_dictListSearch */ 10281cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger regUp = (ActiveRegion *)dictKey( dictSearch( tess->dict, &tmp )); 10291cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger regLo = RegionBelow( regUp ); 10301cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger eUp = regUp->eUp; 10311cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger eLo = regLo->eUp; 10321cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 10331cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger /* Try merging with U or L first */ 10341cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if( EdgeSign( eUp->Dst, vEvent, eUp->Org ) == 0 ) { 10351cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger ConnectLeftDegenerate( tess, regUp, vEvent ); 10361cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger return; 10371cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger } 10381cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 10391cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger /* Connect vEvent to rightmost processed vertex of either chain. 10401cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * e->Dst is the vertex that we will connect to vEvent. 10411cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger */ 10421cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger reg = VertLeq( eLo->Dst, eUp->Dst ) ? regUp : regLo; 10431cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 10441cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if( regUp->inside || reg->fixUpperEdge) { 10451cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if( reg == regUp ) { 10461cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger eNew = __gl_meshConnect( vEvent->anEdge->Sym, eUp->Lnext ); 10471cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if (eNew == NULL) longjmp(tess->env,1); 10481cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger } else { 10491cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger GLUhalfEdge *tempHalfEdge= __gl_meshConnect( eLo->Dnext, vEvent->anEdge); 10501cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if (tempHalfEdge == NULL) longjmp(tess->env,1); 10511cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 10521cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger eNew = tempHalfEdge->Sym; 10531cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger } 10541cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if( reg->fixUpperEdge ) { 10551cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if ( !FixUpperEdge( reg, eNew ) ) longjmp(tess->env,1); 10561cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger } else { 10571cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger ComputeWinding( tess, AddRegionBelow( tess, regUp, eNew )); 10581cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger } 10591cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger SweepEvent( tess, vEvent ); 10601cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger } else { 10611cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger /* The new vertex is in a region which does not belong to the polygon. 10621cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * We don''t need to connect this vertex to the rest of the mesh. 10631cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger */ 10641cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger AddRightEdges( tess, regUp, vEvent->anEdge, vEvent->anEdge, NULL, TRUE ); 10651cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger } 10661cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger} 10671cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 10681cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 10691cab2921ab279367f8206cdadc9259d12e603548Derek Sollenbergerstatic void SweepEvent( GLUtesselator *tess, GLUvertex *vEvent ) 10701cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger/* 10711cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * Does everything necessary when the sweep line crosses a vertex. 10721cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * Updates the mesh and the edge dictionary. 10731cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger */ 10741cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger{ 10751cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger ActiveRegion *regUp, *reg; 10761cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger GLUhalfEdge *e, *eTopLeft, *eBottomLeft; 10771cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 10781cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger tess->event = vEvent; /* for access in EdgeLeq() */ 10791cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger DebugEvent( tess ); 10801cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 10811cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger /* Check if this vertex is the right endpoint of an edge that is 10821cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * already in the dictionary. In this case we don't need to waste 10831cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * time searching for the location to insert new edges. 10841cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger */ 10851cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger e = vEvent->anEdge; 10861cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger while( e->activeRegion == NULL ) { 10871cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger e = e->Onext; 10881cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if( e == vEvent->anEdge ) { 10891cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger /* All edges go right -- not incident to any processed edges */ 10901cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger ConnectLeftVertex( tess, vEvent ); 10911cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger return; 10921cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger } 10931cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger } 10941cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 10951cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger /* Processing consists of two phases: first we "finish" all the 10961cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * active regions where both the upper and lower edges terminate 10971cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * at vEvent (ie. vEvent is closing off these regions). 10981cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * We mark these faces "inside" or "outside" the polygon according 10991cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * to their winding number, and delete the edges from the dictionary. 11001cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * This takes care of all the left-going edges from vEvent. 11011cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger */ 11021cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger regUp = TopLeftRegion( e->activeRegion ); 11031cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if (regUp == NULL) longjmp(tess->env,1); 11041cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger reg = RegionBelow( regUp ); 11051cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger eTopLeft = reg->eUp; 11061cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger eBottomLeft = FinishLeftRegions( tess, reg, NULL ); 11071cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 11081cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger /* Next we process all the right-going edges from vEvent. This 11091cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * involves adding the edges to the dictionary, and creating the 11101cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * associated "active regions" which record information about the 11111cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * regions between adjacent dictionary edges. 11121cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger */ 11131cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if( eBottomLeft->Onext == eTopLeft ) { 11141cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger /* No right-going edges -- add a temporary "fixable" edge */ 11151cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger ConnectRightVertex( tess, regUp, eBottomLeft ); 11161cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger } else { 11171cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger AddRightEdges( tess, regUp, eBottomLeft->Onext, eTopLeft, eTopLeft, TRUE ); 11181cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger } 11191cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger} 11201cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 11211cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 11221cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger/* Make the sentinel coordinates big enough that they will never be 11231cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * merged with real input features. (Even with the largest possible 11241cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * input contour and the maximum tolerance of 1.0, no merging will be 11251cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * done with coordinates larger than 3 * GLU_TESS_MAX_COORD). 11261cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger */ 11271cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger#define SENTINEL_COORD (4 * GLU_TESS_MAX_COORD) 11281cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 11291cab2921ab279367f8206cdadc9259d12e603548Derek Sollenbergerstatic void AddSentinel( GLUtesselator *tess, GLdouble t ) 11301cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger/* 11311cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * We add two sentinel edges above and below all other edges, 11321cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * to avoid special cases at the top and bottom. 11331cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger */ 11341cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger{ 11351cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger GLUhalfEdge *e; 11361cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger ActiveRegion *reg = (ActiveRegion *)memAlloc( sizeof( ActiveRegion )); 11371cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if (reg == NULL) longjmp(tess->env,1); 11381cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 11391cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger e = __gl_meshMakeEdge( tess->mesh ); 11401cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if (e == NULL) longjmp(tess->env,1); 11411cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 11421cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger e->Org->s = SENTINEL_COORD; 11431cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger e->Org->t = t; 11441cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger e->Dst->s = -SENTINEL_COORD; 11451cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger e->Dst->t = t; 11461cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger tess->event = e->Dst; /* initialize it */ 11471cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 11481cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger reg->eUp = e; 11491cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger reg->windingNumber = 0; 11501cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger reg->inside = FALSE; 11511cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger reg->fixUpperEdge = FALSE; 11521cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger reg->sentinel = TRUE; 11531cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger reg->dirty = FALSE; 11541cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger reg->nodeUp = dictInsert( tess->dict, reg ); /* __gl_dictListInsertBefore */ 11551cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if (reg->nodeUp == NULL) longjmp(tess->env,1); 11561cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger} 11571cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 11581cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 11591cab2921ab279367f8206cdadc9259d12e603548Derek Sollenbergerstatic void InitEdgeDict( GLUtesselator *tess ) 11601cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger/* 11611cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * We maintain an ordering of edge intersections with the sweep line. 11621cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * This order is maintained in a dynamic dictionary. 11631cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger */ 11641cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger{ 11651cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger /* __gl_dictListNewDict */ 11661cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger tess->dict = dictNewDict( tess, (int (*)(void *, DictKey, DictKey)) EdgeLeq ); 11671cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if (tess->dict == NULL) longjmp(tess->env,1); 11681cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 11691cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger AddSentinel( tess, -SENTINEL_COORD ); 11701cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger AddSentinel( tess, SENTINEL_COORD ); 11711cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger} 11721cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 11731cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 11741cab2921ab279367f8206cdadc9259d12e603548Derek Sollenbergerstatic void DoneEdgeDict( GLUtesselator *tess ) 11751cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger{ 11761cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger ActiveRegion *reg; 11771cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger#ifndef NDEBUG 11781cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger int fixedEdges = 0; 11791cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger#endif 11801cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 11811cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger /* __GL_DICTLISTKEY */ /* __GL_DICTLISTMIN */ 11821cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger while( (reg = (ActiveRegion *)dictKey( dictMin( tess->dict ))) != NULL ) { 11831cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger /* 11841cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * At the end of all processing, the dictionary should contain 11851cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * only the two sentinel edges, plus at most one "fixable" edge 11861cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * created by ConnectRightVertex(). 11871cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger */ 11881cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if( ! reg->sentinel ) { 11891cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger assert( reg->fixUpperEdge ); 11901cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger assert( ++fixedEdges == 1 ); 11911cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger } 11921cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger assert( reg->windingNumber == 0 ); 11931cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger DeleteRegion( tess, reg ); 11941cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger/* __gl_meshDelete( reg->eUp );*/ 11951cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger } 11961cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger dictDeleteDict( tess->dict ); /* __gl_dictListDeleteDict */ 11971cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger} 11981cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 11991cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 12001cab2921ab279367f8206cdadc9259d12e603548Derek Sollenbergerstatic void RemoveDegenerateEdges( GLUtesselator *tess ) 12011cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger/* 12021cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * Remove zero-length edges, and contours with fewer than 3 vertices. 12031cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger */ 12041cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger{ 12051cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger GLUhalfEdge *e, *eNext, *eLnext; 12061cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger GLUhalfEdge *eHead = &tess->mesh->eHead; 12071cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 12081cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger /*LINTED*/ 12091cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger for( e = eHead->next; e != eHead; e = eNext ) { 12101cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger eNext = e->next; 12111cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger eLnext = e->Lnext; 12121cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 12131cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if( VertEq( e->Org, e->Dst ) && e->Lnext->Lnext != e ) { 12141cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger /* Zero-length edge, contour has at least 3 edges */ 12151cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 12161cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger SpliceMergeVertices( tess, eLnext, e ); /* deletes e->Org */ 12171cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if ( !__gl_meshDelete( e ) ) longjmp(tess->env,1); /* e is a self-loop */ 12181cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger e = eLnext; 12191cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger eLnext = e->Lnext; 12201cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger } 12211cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if( eLnext->Lnext == e ) { 12221cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger /* Degenerate contour (one or two edges) */ 12231cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 12241cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if( eLnext != e ) { 12251cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if( eLnext == eNext || eLnext == eNext->Sym ) { eNext = eNext->next; } 12261cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if ( !__gl_meshDelete( eLnext ) ) longjmp(tess->env,1); 12271cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger } 12281cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if( e == eNext || e == eNext->Sym ) { eNext = eNext->next; } 12291cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if ( !__gl_meshDelete( e ) ) longjmp(tess->env,1); 12301cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger } 12311cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger } 12321cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger} 12331cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 12341cab2921ab279367f8206cdadc9259d12e603548Derek Sollenbergerstatic int InitPriorityQ( GLUtesselator *tess ) 12351cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger/* 12361cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * Insert all vertices into the priority queue which determines the 12371cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * order in which vertices cross the sweep line. 12381cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger */ 12391cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger{ 12401cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger PriorityQ *pq; 12411cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger GLUvertex *v, *vHead; 12421cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 12431cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger /* __gl_pqSortNewPriorityQ */ 12441cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger pq = tess->pq = pqNewPriorityQ( (int (*)(PQkey, PQkey)) __gl_vertLeq ); 12451cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if (pq == NULL) return 0; 12461cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 12471cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger vHead = &tess->mesh->vHead; 12481cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger for( v = vHead->next; v != vHead; v = v->next ) { 12491cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger v->pqHandle = pqInsert( pq, v ); /* __gl_pqSortInsert */ 12501cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if (v->pqHandle == LONG_MAX) break; 12511cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger } 12521cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if (v != vHead || !pqInit( pq ) ) { /* __gl_pqSortInit */ 12531cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger pqDeletePriorityQ(tess->pq); /* __gl_pqSortDeletePriorityQ */ 12541cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger tess->pq = NULL; 12551cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger return 0; 12561cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger } 12571cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 12581cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger return 1; 12591cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger} 12601cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 12611cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 12621cab2921ab279367f8206cdadc9259d12e603548Derek Sollenbergerstatic void DonePriorityQ( GLUtesselator *tess ) 12631cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger{ 12641cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger pqDeletePriorityQ( tess->pq ); /* __gl_pqSortDeletePriorityQ */ 12651cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger} 12661cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 12671cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 12681cab2921ab279367f8206cdadc9259d12e603548Derek Sollenbergerstatic int RemoveDegenerateFaces( GLUmesh *mesh ) 12691cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger/* 12701cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * Delete any degenerate faces with only two edges. WalkDirtyRegions() 12711cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * will catch almost all of these, but it won't catch degenerate faces 12721cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * produced by splice operations on already-processed edges. 12731cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * The two places this can happen are in FinishLeftRegions(), when 12741cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * we splice in a "temporary" edge produced by ConnectRightVertex(), 12751cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * and in CheckForLeftSplice(), where we splice already-processed 12761cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * edges to ensure that our dictionary invariants are not violated 12771cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * by numerical errors. 12781cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * 12791cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * In both these cases it is *very* dangerous to delete the offending 12801cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * edge at the time, since one of the routines further up the stack 12811cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * will sometimes be keeping a pointer to that edge. 12821cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger */ 12831cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger{ 12841cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger GLUface *f, *fNext; 12851cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger GLUhalfEdge *e; 12861cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 12871cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger /*LINTED*/ 12881cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger for( f = mesh->fHead.next; f != &mesh->fHead; f = fNext ) { 12891cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger fNext = f->next; 12901cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger e = f->anEdge; 12911cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger assert( e->Lnext != e ); 12921cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 12931cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if( e->Lnext->Lnext == e ) { 12941cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger /* A face with only two edges */ 12951cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger AddWinding( e->Onext, e ); 12961cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if ( !__gl_meshDelete( e ) ) return 0; 12971cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger } 12981cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger } 12991cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger return 1; 13001cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger} 13011cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 13021cab2921ab279367f8206cdadc9259d12e603548Derek Sollenbergerint __gl_computeInterior( GLUtesselator *tess ) 13031cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger/* 13041cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * __gl_computeInterior( tess ) computes the planar arrangement specified 13051cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * by the given contours, and further subdivides this arrangement 13061cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * into regions. Each region is marked "inside" if it belongs 13071cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * to the polygon, according to the rule given by tess->windingRule. 13081cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * Each interior region is guaranteed be monotone. 13091cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger */ 13101cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger{ 13111cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger GLUvertex *v, *vNext; 13121cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 13131cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger tess->fatalError = FALSE; 13141cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 13151cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger /* Each vertex defines an event for our sweep line. Start by inserting 13161cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * all the vertices in a priority queue. Events are processed in 13171cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * lexicographic order, ie. 13181cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * 13191cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * e1 < e2 iff e1.x < e2.x || (e1.x == e2.x && e1.y < e2.y) 13201cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger */ 13211cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger RemoveDegenerateEdges( tess ); 13221cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if ( !InitPriorityQ( tess ) ) return 0; /* if error */ 13231cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger InitEdgeDict( tess ); 13241cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 13251cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger /* __gl_pqSortExtractMin */ 13261cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger while( (v = (GLUvertex *)pqExtractMin( tess->pq )) != NULL ) { 13271cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger for( ;; ) { 13281cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger vNext = (GLUvertex *)pqMinimum( tess->pq ); /* __gl_pqSortMinimum */ 13291cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if( vNext == NULL || ! VertEq( vNext, v )) break; 13301cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 13311cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger /* Merge together all vertices at exactly the same location. 13321cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * This is more efficient than processing them one at a time, 13331cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * simplifies the code (see ConnectLeftDegenerate), and is also 13341cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * important for correct handling of certain degenerate cases. 13351cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * For example, suppose there are two identical edges A and B 13361cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * that belong to different contours (so without this code they would 13371cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * be processed by separate sweep events). Suppose another edge C 13381cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * crosses A and B from above. When A is processed, we split it 13391cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * at its intersection point with C. However this also splits C, 13401cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * so when we insert B we may compute a slightly different 13411cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * intersection point. This might leave two edges with a small 13421cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * gap between them. This kind of error is especially obvious 13431cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * when using boundary extraction (GLU_TESS_BOUNDARY_ONLY). 13441cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger */ 13451cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger vNext = (GLUvertex *)pqExtractMin( tess->pq ); /* __gl_pqSortExtractMin*/ 13461cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger SpliceMergeVertices( tess, v->anEdge, vNext->anEdge ); 13471cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger } 13481cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger SweepEvent( tess, v ); 13491cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger } 13501cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 13511cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger /* Set tess->event for debugging purposes */ 13521cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger /* __GL_DICTLISTKEY */ /* __GL_DICTLISTMIN */ 13531cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger tess->event = ((ActiveRegion *) dictKey( dictMin( tess->dict )))->eUp->Org; 13541cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger DebugEvent( tess ); 13551cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger DoneEdgeDict( tess ); 13561cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger DonePriorityQ( tess ); 13571cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 13581cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if ( !RemoveDegenerateFaces( tess->mesh ) ) return 0; 13591cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger __gl_meshCheckMesh( tess->mesh ); 13601cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 13611cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger return 1; 13621cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger} 1363