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/render.c#5 $ 401cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger*/ 411cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 421cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger#include "gluos.h" 431cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger#include <assert.h> 441cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger#include <stddef.h> 451cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger#include "mesh.h" 461cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger#include "tess.h" 471cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger#include "render.h" 481cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 491cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger#define TRUE 1 501cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger#define FALSE 0 511cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 521cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger/* This structure remembers the information we need about a primitive 531cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * to be able to render it later, once we have determined which 541cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * primitive is able to use the most triangles. 551cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger */ 561cab2921ab279367f8206cdadc9259d12e603548Derek Sollenbergerstruct FaceCount { 571cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger long size; /* number of triangles used */ 581cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger GLUhalfEdge *eStart; /* edge where this primitive starts */ 591cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger void (*render)(GLUtesselator *, GLUhalfEdge *, long); 601cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger /* routine to render this primitive */ 611cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger}; 621cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 631cab2921ab279367f8206cdadc9259d12e603548Derek Sollenbergerstatic struct FaceCount MaximumFan( GLUhalfEdge *eOrig ); 641cab2921ab279367f8206cdadc9259d12e603548Derek Sollenbergerstatic struct FaceCount MaximumStrip( GLUhalfEdge *eOrig ); 651cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 661cab2921ab279367f8206cdadc9259d12e603548Derek Sollenbergerstatic void RenderFan( GLUtesselator *tess, GLUhalfEdge *eStart, long size ); 671cab2921ab279367f8206cdadc9259d12e603548Derek Sollenbergerstatic void RenderStrip( GLUtesselator *tess, GLUhalfEdge *eStart, long size ); 681cab2921ab279367f8206cdadc9259d12e603548Derek Sollenbergerstatic void RenderTriangle( GLUtesselator *tess, GLUhalfEdge *eStart, 691cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger long size ); 701cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 711cab2921ab279367f8206cdadc9259d12e603548Derek Sollenbergerstatic void RenderMaximumFaceGroup( GLUtesselator *tess, GLUface *fOrig ); 721cab2921ab279367f8206cdadc9259d12e603548Derek Sollenbergerstatic void RenderLonelyTriangles( GLUtesselator *tess, GLUface *head ); 731cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 741cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 751cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 761cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger/************************ Strips and Fans decomposition ******************/ 771cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 781cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger/* __gl_renderMesh( tess, mesh ) takes a mesh and breaks it into triangle 791cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * fans, strips, and separate triangles. A substantial effort is made 801cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * to use as few rendering primitives as possible (ie. to make the fans 811cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * and strips as large as possible). 821cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * 831cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * The rendering output is provided as callbacks (see the api). 841cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger */ 851cab2921ab279367f8206cdadc9259d12e603548Derek Sollenbergervoid __gl_renderMesh( GLUtesselator *tess, GLUmesh *mesh ) 861cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger{ 871cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger GLUface *f; 881cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 891cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger /* Make a list of separate triangles so we can render them all at once */ 901cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger tess->lonelyTriList = NULL; 911cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 921cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger for( f = mesh->fHead.next; f != &mesh->fHead; f = f->next ) { 931cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger f->marked = FALSE; 941cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger } 951cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger for( f = mesh->fHead.next; f != &mesh->fHead; f = f->next ) { 961cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 971cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger /* We examine all faces in an arbitrary order. Whenever we find 981cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * an unprocessed face F, we output a group of faces including F 991cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * whose size is maximum. 1001cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger */ 1011cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if( f->inside && ! f->marked ) { 1021cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger RenderMaximumFaceGroup( tess, f ); 1031cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger assert( f->marked ); 1041cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger } 1051cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger } 1061cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if( tess->lonelyTriList != NULL ) { 1071cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger RenderLonelyTriangles( tess, tess->lonelyTriList ); 1081cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger tess->lonelyTriList = NULL; 1091cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger } 1101cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger} 1111cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 1121cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 1131cab2921ab279367f8206cdadc9259d12e603548Derek Sollenbergerstatic void RenderMaximumFaceGroup( GLUtesselator *tess, GLUface *fOrig ) 1141cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger{ 1151cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger /* We want to find the largest triangle fan or strip of unmarked faces 1161cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * which includes the given face fOrig. There are 3 possible fans 1171cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * passing through fOrig (one centered at each vertex), and 3 possible 1181cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * strips (one for each CCW permutation of the vertices). Our strategy 1191cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * is to try all of these, and take the primitive which uses the most 1201cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * triangles (a greedy approach). 1211cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger */ 1221cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger GLUhalfEdge *e = fOrig->anEdge; 1231cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger struct FaceCount max, newFace; 1241cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 1251cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger max.size = 1; 1261cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger max.eStart = e; 1271cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger max.render = &RenderTriangle; 1281cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 1291cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if( ! tess->flagBoundary ) { 1301cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger newFace = MaximumFan( e ); if( newFace.size > max.size ) { max = newFace; } 1311cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger newFace = MaximumFan( e->Lnext ); if( newFace.size > max.size ) { max = newFace; } 1321cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger newFace = MaximumFan( e->Lprev ); if( newFace.size > max.size ) { max = newFace; } 1331cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 1341cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger newFace = MaximumStrip( e ); if( newFace.size > max.size ) { max = newFace; } 1351cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger newFace = MaximumStrip( e->Lnext ); if( newFace.size > max.size ) { max = newFace; } 1361cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger newFace = MaximumStrip( e->Lprev ); if( newFace.size > max.size ) { max = newFace; } 1371cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger } 1381cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger (*(max.render))( tess, max.eStart, max.size ); 1391cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger} 1401cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 1411cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 1421cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger/* Macros which keep track of faces we have marked temporarily, and allow 1431cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * us to backtrack when necessary. With triangle fans, this is not 1441cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * really necessary, since the only awkward case is a loop of triangles 1451cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * around a single origin vertex. However with strips the situation is 1461cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * more complicated, and we need a general tracking method like the 1471cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * one here. 1481cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger */ 1491cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger#define Marked(f) (! (f)->inside || (f)->marked) 1501cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 1511cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger#define AddToTrail(f,t) ((f)->trail = (t), (t) = (f), (f)->marked = TRUE) 1521cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 1531cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger#define FreeTrail(t) do { \ 1541cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger while( (t) != NULL ) { \ 1551cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger (t)->marked = FALSE; t = (t)->trail; \ 1561cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger } \ 1571cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger } while(0) /* absorb trailing semicolon */ 1581cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 1591cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 1601cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 1611cab2921ab279367f8206cdadc9259d12e603548Derek Sollenbergerstatic struct FaceCount MaximumFan( GLUhalfEdge *eOrig ) 1621cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger{ 1631cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger /* eOrig->Lface is the face we want to render. We want to find the size 1641cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * of a maximal fan around eOrig->Org. To do this we just walk around 1651cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * the origin vertex as far as possible in both directions. 1661cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger */ 1671cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger struct FaceCount newFace = { 0, NULL, &RenderFan }; 1681cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger GLUface *trail = NULL; 1691cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger GLUhalfEdge *e; 1701cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 1711cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger for( e = eOrig; ! Marked( e->Lface ); e = e->Onext ) { 1721cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger AddToTrail( e->Lface, trail ); 1731cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger ++newFace.size; 1741cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger } 1751cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger for( e = eOrig; ! Marked( e->Rface ); e = e->Oprev ) { 1761cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger AddToTrail( e->Rface, trail ); 1771cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger ++newFace.size; 1781cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger } 1791cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger newFace.eStart = e; 1801cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger /*LINTED*/ 1811cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger FreeTrail( trail ); 1821cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger return newFace; 1831cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger} 1841cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 1851cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 1861cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger#define IsEven(n) (((n) & 1) == 0) 1871cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 1881cab2921ab279367f8206cdadc9259d12e603548Derek Sollenbergerstatic struct FaceCount MaximumStrip( GLUhalfEdge *eOrig ) 1891cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger{ 1901cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger /* Here we are looking for a maximal strip that contains the vertices 1911cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * eOrig->Org, eOrig->Dst, eOrig->Lnext->Dst (in that order or the 1921cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * reverse, such that all triangles are oriented CCW). 1931cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * 1941cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * Again we walk forward and backward as far as possible. However for 1951cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * strips there is a twist: to get CCW orientations, there must be 1961cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * an *even* number of triangles in the strip on one side of eOrig. 1971cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * We walk the strip starting on a side with an even number of triangles; 1981cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * if both side have an odd number, we are forced to shorten one side. 1991cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger */ 2001cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger struct FaceCount newFace = { 0, NULL, &RenderStrip }; 2011cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger long headSize = 0, tailSize = 0; 2021cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger GLUface *trail = NULL; 2031cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger GLUhalfEdge *e, *eTail, *eHead; 2041cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 2051cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger for( e = eOrig; ! Marked( e->Lface ); ++tailSize, e = e->Onext ) { 2061cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger AddToTrail( e->Lface, trail ); 2071cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger ++tailSize; 2081cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger e = e->Dprev; 2091cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if( Marked( e->Lface )) break; 2101cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger AddToTrail( e->Lface, trail ); 2111cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger } 2121cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger eTail = e; 2131cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 2141cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger for( e = eOrig; ! Marked( e->Rface ); ++headSize, e = e->Dnext ) { 2151cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger AddToTrail( e->Rface, trail ); 2161cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger ++headSize; 2171cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger e = e->Oprev; 2181cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if( Marked( e->Rface )) break; 2191cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger AddToTrail( e->Rface, trail ); 2201cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger } 2211cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger eHead = e; 2221cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 2231cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger newFace.size = tailSize + headSize; 2241cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if( IsEven( tailSize )) { 2251cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger newFace.eStart = eTail->Sym; 2261cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger } else if( IsEven( headSize )) { 2271cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger newFace.eStart = eHead; 2281cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger } else { 2291cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger /* Both sides have odd length, we must shorten one of them. In fact, 2301cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * we must start from eHead to guarantee inclusion of eOrig->Lface. 2311cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger */ 2321cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger --newFace.size; 2331cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger newFace.eStart = eHead->Onext; 2341cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger } 2351cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger /*LINTED*/ 2361cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger FreeTrail( trail ); 2371cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger return newFace; 2381cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger} 2391cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 2401cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 2411cab2921ab279367f8206cdadc9259d12e603548Derek Sollenbergerstatic void RenderTriangle( GLUtesselator *tess, GLUhalfEdge *e, long size ) 2421cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger{ 2431cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger /* Just add the triangle to a triangle list, so we can render all 2441cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * the separate triangles at once. 2451cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger */ 2461cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger assert( size == 1 ); 2471cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger AddToTrail( e->Lface, tess->lonelyTriList ); 2481cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger} 2491cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 2501cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 2511cab2921ab279367f8206cdadc9259d12e603548Derek Sollenbergerstatic void RenderLonelyTriangles( GLUtesselator *tess, GLUface *f ) 2521cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger{ 2531cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger /* Now we render all the separate triangles which could not be 2541cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * grouped into a triangle fan or strip. 2551cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger */ 2561cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger GLUhalfEdge *e; 2571cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger int newState; 2581cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger int edgeState = -1; /* force edge state output for first vertex */ 2591cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 2601cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger CALL_BEGIN_OR_BEGIN_DATA( GL_TRIANGLES ); 2611cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 2621cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger for( ; f != NULL; f = f->trail ) { 2631cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger /* Loop once for each edge (there will always be 3 edges) */ 2641cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 2651cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger e = f->anEdge; 2661cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger do { 2671cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if( tess->flagBoundary ) { 2681cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger /* Set the "edge state" to TRUE just before we output the 2691cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * first vertex of each edge on the polygon boundary. 2701cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger */ 2711cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger newState = ! e->Rface->inside; 2721cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if( edgeState != newState ) { 2731cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger edgeState = newState; 2741cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger CALL_EDGE_FLAG_OR_EDGE_FLAG_DATA( edgeState ); 2751cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger } 2761cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger } 2771cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger CALL_VERTEX_OR_VERTEX_DATA( e->Org->data ); 2781cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 2791cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger e = e->Lnext; 2801cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger } while( e != f->anEdge ); 2811cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger } 2821cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger CALL_END_OR_END_DATA(); 2831cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger} 2841cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 2851cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 2861cab2921ab279367f8206cdadc9259d12e603548Derek Sollenbergerstatic void RenderFan( GLUtesselator *tess, GLUhalfEdge *e, long size ) 2871cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger{ 2881cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger /* Render as many CCW triangles as possible in a fan starting from 2891cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * edge "e". The fan *should* contain exactly "size" triangles 2901cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * (otherwise we've goofed up somewhere). 2911cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger */ 2921cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger CALL_BEGIN_OR_BEGIN_DATA( GL_TRIANGLE_FAN ); 2931cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger CALL_VERTEX_OR_VERTEX_DATA( e->Org->data ); 2941cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger CALL_VERTEX_OR_VERTEX_DATA( e->Dst->data ); 2951cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 2961cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger while( ! Marked( e->Lface )) { 2971cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger e->Lface->marked = TRUE; 2981cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger --size; 2991cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger e = e->Onext; 3001cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger CALL_VERTEX_OR_VERTEX_DATA( e->Dst->data ); 3011cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger } 3021cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 3031cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger assert( size == 0 ); 3041cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger CALL_END_OR_END_DATA(); 3051cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger} 3061cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 3071cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 3081cab2921ab279367f8206cdadc9259d12e603548Derek Sollenbergerstatic void RenderStrip( GLUtesselator *tess, GLUhalfEdge *e, long size ) 3091cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger{ 3101cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger /* Render as many CCW triangles as possible in a strip starting from 3111cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * edge "e". The strip *should* contain exactly "size" triangles 3121cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * (otherwise we've goofed up somewhere). 3131cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger */ 3141cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger CALL_BEGIN_OR_BEGIN_DATA( GL_TRIANGLE_STRIP ); 3151cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger CALL_VERTEX_OR_VERTEX_DATA( e->Org->data ); 3161cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger CALL_VERTEX_OR_VERTEX_DATA( e->Dst->data ); 3171cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 3181cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger while( ! Marked( e->Lface )) { 3191cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger e->Lface->marked = TRUE; 3201cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger --size; 3211cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger e = e->Dprev; 3221cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger CALL_VERTEX_OR_VERTEX_DATA( e->Org->data ); 3231cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if( Marked( e->Lface )) break; 3241cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 3251cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger e->Lface->marked = TRUE; 3261cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger --size; 3271cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger e = e->Onext; 3281cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger CALL_VERTEX_OR_VERTEX_DATA( e->Dst->data ); 3291cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger } 3301cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 3311cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger assert( size == 0 ); 3321cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger CALL_END_OR_END_DATA(); 3331cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger} 3341cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 3351cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 3361cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger/************************ Boundary contour decomposition ******************/ 3371cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 3381cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger/* __gl_renderBoundary( tess, mesh ) takes a mesh, and outputs one 3391cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * contour for each face marked "inside". The rendering output is 3401cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * provided as callbacks (see the api). 3411cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger */ 3421cab2921ab279367f8206cdadc9259d12e603548Derek Sollenbergervoid __gl_renderBoundary( GLUtesselator *tess, GLUmesh *mesh ) 3431cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger{ 3441cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger GLUface *f; 3451cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger GLUhalfEdge *e; 3461cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 3471cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger for( f = mesh->fHead.next; f != &mesh->fHead; f = f->next ) { 3481cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if( f->inside ) { 3491cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger CALL_BEGIN_OR_BEGIN_DATA( GL_LINE_LOOP ); 3501cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger e = f->anEdge; 3511cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger do { 3521cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger CALL_VERTEX_OR_VERTEX_DATA( e->Org->data ); 3531cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger e = e->Lnext; 3541cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger } while( e != f->anEdge ); 3551cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger CALL_END_OR_END_DATA(); 3561cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger } 3571cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger } 3581cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger} 3591cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 3601cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 3611cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger/************************ Quick-and-dirty decomposition ******************/ 3621cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 3631cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger#define SIGN_INCONSISTENT 2 3641cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 3651cab2921ab279367f8206cdadc9259d12e603548Derek Sollenbergerstatic int ComputeNormal( GLUtesselator *tess, GLdouble norm[3], int check ) 3661cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger/* 3671cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * If check==FALSE, we compute the polygon normal and place it in norm[]. 3681cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * If check==TRUE, we check that each triangle in the fan from v0 has a 3691cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * consistent orientation with respect to norm[]. If triangles are 3701cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * consistently oriented CCW, return 1; if CW, return -1; if all triangles 3711cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * are degenerate return 0; otherwise (no consistent orientation) return 3721cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * SIGN_INCONSISTENT. 3731cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger */ 3741cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger{ 3751cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger CachedVertex *v0 = tess->cache; 3761cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger CachedVertex *vn = v0 + tess->cacheCount; 3771cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger CachedVertex *vc; 3781cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger GLdouble dot, xc, yc, zc, xp, yp, zp, n[3]; 3791cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger int sign = 0; 3801cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 3811cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger /* Find the polygon normal. It is important to get a reasonable 3821cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * normal even when the polygon is self-intersecting (eg. a bowtie). 3831cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * Otherwise, the computed normal could be very tiny, but perpendicular 3841cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * to the true plane of the polygon due to numerical noise. Then all 3851cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * the triangles would appear to be degenerate and we would incorrectly 3861cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * decompose the polygon as a fan (or simply not render it at all). 3871cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * 3881cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * We use a sum-of-triangles normal algorithm rather than the more 3891cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * efficient sum-of-trapezoids method (used in CheckOrientation() 3901cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * in normal.c). This lets us explicitly reverse the signed area 3911cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * of some triangles to get a reasonable normal in the self-intersecting 3921cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * case. 3931cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger */ 3941cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if( ! check ) { 3951cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger norm[0] = norm[1] = norm[2] = 0.0; 3961cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger } 3971cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 3981cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger vc = v0 + 1; 3991cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger xc = vc->coords[0] - v0->coords[0]; 4001cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger yc = vc->coords[1] - v0->coords[1]; 4011cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger zc = vc->coords[2] - v0->coords[2]; 4021cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger while( ++vc < vn ) { 4031cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger xp = xc; yp = yc; zp = zc; 4041cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger xc = vc->coords[0] - v0->coords[0]; 4051cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger yc = vc->coords[1] - v0->coords[1]; 4061cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger zc = vc->coords[2] - v0->coords[2]; 4071cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 4081cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger /* Compute (vp - v0) cross (vc - v0) */ 4091cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger n[0] = yp*zc - zp*yc; 4101cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger n[1] = zp*xc - xp*zc; 4111cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger n[2] = xp*yc - yp*xc; 4121cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 4131cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger dot = n[0]*norm[0] + n[1]*norm[1] + n[2]*norm[2]; 4141cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if( ! check ) { 4151cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger /* Reverse the contribution of back-facing triangles to get 4161cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * a reasonable normal for self-intersecting polygons (see above) 4171cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger */ 4181cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if( dot >= 0 ) { 4191cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger norm[0] += n[0]; norm[1] += n[1]; norm[2] += n[2]; 4201cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger } else { 4211cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger norm[0] -= n[0]; norm[1] -= n[1]; norm[2] -= n[2]; 4221cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger } 4231cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger } else if( dot != 0 ) { 4241cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger /* Check the new orientation for consistency with previous triangles */ 4251cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if( dot > 0 ) { 4261cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if( sign < 0 ) return SIGN_INCONSISTENT; 4271cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger sign = 1; 4281cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger } else { 4291cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if( sign > 0 ) return SIGN_INCONSISTENT; 4301cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger sign = -1; 4311cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger } 4321cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger } 4331cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger } 4341cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger return sign; 4351cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger} 4361cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 4371cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger/* __gl_renderCache( tess ) takes a single contour and tries to render it 4381cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * as a triangle fan. This handles convex polygons, as well as some 4391cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * non-convex polygons if we get lucky. 4401cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * 4411cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * Returns TRUE if the polygon was successfully rendered. The rendering 4421cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * output is provided as callbacks (see the api). 4431cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger */ 4441cab2921ab279367f8206cdadc9259d12e603548Derek SollenbergerGLboolean __gl_renderCache( GLUtesselator *tess ) 4451cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger{ 4461cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger CachedVertex *v0 = tess->cache; 4471cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger CachedVertex *vn = v0 + tess->cacheCount; 4481cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger CachedVertex *vc; 4491cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger GLdouble norm[3]; 4501cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger int sign; 4511cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 4521cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if( tess->cacheCount < 3 ) { 4531cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger /* Degenerate contour -- no output */ 4541cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger return TRUE; 4551cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger } 4561cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 4571cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger norm[0] = tess->normal[0]; 4581cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger norm[1] = tess->normal[1]; 4591cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger norm[2] = tess->normal[2]; 4601cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if( norm[0] == 0 && norm[1] == 0 && norm[2] == 0 ) { 4611cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger ComputeNormal( tess, norm, FALSE ); 4621cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger } 4631cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 4641cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger sign = ComputeNormal( tess, norm, TRUE ); 4651cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if( sign == SIGN_INCONSISTENT ) { 4661cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger /* Fan triangles did not have a consistent orientation */ 4671cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger return FALSE; 4681cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger } 4691cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if( sign == 0 ) { 4701cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger /* All triangles were degenerate */ 4711cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger return TRUE; 4721cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger } 4731cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 4741cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger /* Make sure we do the right thing for each winding rule */ 4751cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger switch( tess->windingRule ) { 4761cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger case GLU_TESS_WINDING_ODD: 4771cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger case GLU_TESS_WINDING_NONZERO: 4781cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger break; 4791cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger case GLU_TESS_WINDING_POSITIVE: 4801cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if( sign < 0 ) return TRUE; 4811cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger break; 4821cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger case GLU_TESS_WINDING_NEGATIVE: 4831cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if( sign > 0 ) return TRUE; 4841cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger break; 4851cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger case GLU_TESS_WINDING_ABS_GEQ_TWO: 4861cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger return TRUE; 4871cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger } 4881cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 4891cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger CALL_BEGIN_OR_BEGIN_DATA( tess->boundaryOnly ? GL_LINE_LOOP 4901cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger : (tess->cacheCount > 3) ? GL_TRIANGLE_FAN 4911cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger : GL_TRIANGLES ); 4921cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 4931cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger CALL_VERTEX_OR_VERTEX_DATA( v0->data ); 4941cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if( sign > 0 ) { 4951cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger for( vc = v0+1; vc < vn; ++vc ) { 4961cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger CALL_VERTEX_OR_VERTEX_DATA( vc->data ); 4971cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger } 4981cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger } else { 4991cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger for( vc = vn-1; vc > v0; --vc ) { 5001cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger CALL_VERTEX_OR_VERTEX_DATA( vc->data ); 5011cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger } 5021cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger } 5031cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger CALL_END_OR_END_DATA(); 5041cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger return TRUE; 5051cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger} 506