| Geant4 Cross Reference |
1 // see license file for original license. 1 // see license file for original license.
2 2
3 #ifndef tools_glutess_render 3 #ifndef tools_glutess_render
4 #define tools_glutess_render 4 #define tools_glutess_render
5 5
6 #include "mesh" 6 #include "mesh"
7 7
8 /* __gl_renderMesh( tess, mesh ) takes a mesh 8 /* __gl_renderMesh( tess, mesh ) takes a mesh and breaks it into triangle
9 * fans, strips, and separate triangles. A su 9 * fans, strips, and separate triangles. A substantial effort is made
10 * to use as few rendering primitives as possi 10 * to use as few rendering primitives as possible (ie. to make the fans
11 * and strips as large as possible). 11 * and strips as large as possible).
12 * 12 *
13 * The rendering output is provided as callbac 13 * The rendering output is provided as callbacks (see the api).
14 */ 14 */
15 //void __gl_renderMesh( GLUtesselator *tess, G 15 //void __gl_renderMesh( GLUtesselator *tess, GLUmesh *mesh );
16 //void __gl_renderBoundary( GLUtesselator *tes 16 //void __gl_renderBoundary( GLUtesselator *tess, GLUmesh *mesh );
17 17
18 //GLUboolean __gl_renderCache( GLUtesselator * 18 //GLUboolean __gl_renderCache( GLUtesselator *tess );
19 19
20 ////////////////////////////////////////////// 20 ////////////////////////////////////////////////////////
21 /// inlined C code : ///////////////////////// 21 /// inlined C code : ///////////////////////////////////
22 ////////////////////////////////////////////// 22 ////////////////////////////////////////////////////////
23 23
24 #include "_tess" 24 #include "_tess"
25 25
26 /* This structure remembers the information we 26 /* This structure remembers the information we need about a primitive
27 * to be able to render it later, once we have 27 * to be able to render it later, once we have determined which
28 * primitive is able to use the most triangles 28 * primitive is able to use the most triangles.
29 */ 29 */
30 struct FaceCount { 30 struct FaceCount {
31 long size; /* number of triangles used 31 long size; /* number of triangles used */
32 GLUhalfEdge *eStart; /* edge where this pri 32 GLUhalfEdge *eStart; /* edge where this primitive starts */
33 void (*render)(GLUtesselator *, GLUhalfEd 33 void (*render)(GLUtesselator *, GLUhalfEdge *, long);
34 /* routine to 34 /* routine to render this primitive */
35 }; 35 };
36 36
37 inline/*static*/ struct FaceCount static_Maxim 37 inline/*static*/ struct FaceCount static_MaximumFan( GLUhalfEdge *eOrig );
38 inline/*static*/ struct FaceCount static_Maxim 38 inline/*static*/ struct FaceCount static_MaximumStrip( GLUhalfEdge *eOrig );
39 39
40 inline/*static*/ void static_RenderFan( GLUtes 40 inline/*static*/ void static_RenderFan( GLUtesselator *tess, GLUhalfEdge *eStart, long size );
41 inline/*static*/ void static_RenderStrip( GLUt 41 inline/*static*/ void static_RenderStrip( GLUtesselator *tess, GLUhalfEdge *eStart, long size );
42 inline/*static*/ void static_RenderTriangle( G 42 inline/*static*/ void static_RenderTriangle( GLUtesselator *tess, GLUhalfEdge *eStart,
43 long size ); 43 long size );
44 44
45 inline/*static*/ void static_RenderMaximumFace 45 inline/*static*/ void static_RenderMaximumFaceGroup( GLUtesselator *tess, GLUface *fOrig );
46 inline/*static*/ void static_RenderLonelyTrian 46 inline/*static*/ void static_RenderLonelyTriangles( GLUtesselator *tess, GLUface *head );
47 47
48 48
49 49
50 /************************ Strips and Fans deco 50 /************************ Strips and Fans decomposition ******************/
51 51
52 /* __gl_renderMesh( tess, mesh ) takes a mesh 52 /* __gl_renderMesh( tess, mesh ) takes a mesh and breaks it into triangle
53 * fans, strips, and separate triangles. A su 53 * fans, strips, and separate triangles. A substantial effort is made
54 * to use as few rendering primitives as possi 54 * to use as few rendering primitives as possible (ie. to make the fans
55 * and strips as large as possible). 55 * and strips as large as possible).
56 * 56 *
57 * The rendering output is provided as callbac 57 * The rendering output is provided as callbacks (see the api).
58 */ 58 */
59 inline void __gl_renderMesh( GLUtesselator *te 59 inline void __gl_renderMesh( GLUtesselator *tess, GLUmesh *mesh )
60 { 60 {
61 GLUface *f; 61 GLUface *f;
62 62
63 /* Make a list of separate triangles so we c 63 /* Make a list of separate triangles so we can render them all at once */
64 tess->lonelyTriList = NULL; 64 tess->lonelyTriList = NULL;
65 65
66 for( f = mesh->fHead.next; f != &mesh->fHead 66 for( f = mesh->fHead.next; f != &mesh->fHead; f = f->next ) {
67 f->marked = TOOLS_GLU_FALSE; 67 f->marked = TOOLS_GLU_FALSE;
68 } 68 }
69 for( f = mesh->fHead.next; f != &mesh->fHead 69 for( f = mesh->fHead.next; f != &mesh->fHead; f = f->next ) {
70 70
71 /* We examine all faces in an arbitrary or 71 /* We examine all faces in an arbitrary order. Whenever we find
72 * an unprocessed face F, we output a grou 72 * an unprocessed face F, we output a group of faces including F
73 * whose size is maximum. 73 * whose size is maximum.
74 */ 74 */
75 if( f->inside && ! f->marked ) { 75 if( f->inside && ! f->marked ) {
76 static_RenderMaximumFaceGroup( tess, f ) 76 static_RenderMaximumFaceGroup( tess, f );
77 assert( f->marked ); 77 assert( f->marked );
78 } 78 }
79 } 79 }
80 if( tess->lonelyTriList != NULL ) { 80 if( tess->lonelyTriList != NULL ) {
81 static_RenderLonelyTriangles( tess, tess-> 81 static_RenderLonelyTriangles( tess, tess->lonelyTriList );
82 tess->lonelyTriList = NULL; 82 tess->lonelyTriList = NULL;
83 } 83 }
84 } 84 }
85 85
86 86
87 inline/*static*/ void static_RenderMaximumFace 87 inline/*static*/ void static_RenderMaximumFaceGroup( GLUtesselator *tess, GLUface *fOrig )
88 { 88 {
89 /* We want to find the largest triangle fan 89 /* We want to find the largest triangle fan or strip of unmarked faces
90 * which includes the given face fOrig. The 90 * which includes the given face fOrig. There are 3 possible fans
91 * passing through fOrig (one centered at ea 91 * passing through fOrig (one centered at each vertex), and 3 possible
92 * strips (one for each CCW permutation of t 92 * strips (one for each CCW permutation of the vertices). Our strategy
93 * is to try all of these, and take the prim 93 * is to try all of these, and take the primitive which uses the most
94 * triangles (a greedy approach). 94 * triangles (a greedy approach).
95 */ 95 */
96 GLUhalfEdge *e = fOrig->anEdge; 96 GLUhalfEdge *e = fOrig->anEdge;
97 struct FaceCount max, newFace; 97 struct FaceCount max, newFace;
98 98
99 max.size = 1; 99 max.size = 1;
100 max.eStart = e; 100 max.eStart = e;
101 max.render = &static_RenderTriangle; 101 max.render = &static_RenderTriangle;
102 102
103 if( ! tess->flagBoundary ) { 103 if( ! tess->flagBoundary ) {
104 newFace = static_MaximumFan( e ); if( newF 104 newFace = static_MaximumFan( e ); if( newFace.size > max.size ) { max = newFace; }
105 newFace = static_MaximumFan( e->Lnext ); i 105 newFace = static_MaximumFan( e->Lnext ); if( newFace.size > max.size ) { max = newFace; }
106 newFace = static_MaximumFan( e->Lprev ); i 106 newFace = static_MaximumFan( e->Lprev ); if( newFace.size > max.size ) { max = newFace; }
107 107
108 newFace = static_MaximumStrip( e ); if( ne 108 newFace = static_MaximumStrip( e ); if( newFace.size > max.size ) { max = newFace; }
109 newFace = static_MaximumStrip( e->Lnext ); 109 newFace = static_MaximumStrip( e->Lnext ); if( newFace.size > max.size ) { max = newFace; }
110 newFace = static_MaximumStrip( e->Lprev ); 110 newFace = static_MaximumStrip( e->Lprev ); if( newFace.size > max.size ) { max = newFace; }
111 } 111 }
112 (*(max.render))( tess, max.eStart, max.size 112 (*(max.render))( tess, max.eStart, max.size );
113 } 113 }
114 114
115 115
116 /* Macros which keep track of faces we have ma 116 /* Macros which keep track of faces we have marked temporarily, and allow
117 * us to backtrack when necessary. With trian 117 * us to backtrack when necessary. With triangle fans, this is not
118 * really necessary, since the only awkward ca 118 * really necessary, since the only awkward case is a loop of triangles
119 * around a single origin vertex. However wit 119 * around a single origin vertex. However with strips the situation is
120 * more complicated, and we need a general tra 120 * more complicated, and we need a general tracking method like the
121 * one here. 121 * one here.
122 */ 122 */
123 #define Marked(f) (! (f)->inside || (f)->marke 123 #define Marked(f) (! (f)->inside || (f)->marked)
124 124
125 #define AddToTrail(f,t) ((f)->trail = (t), (t) 125 #define AddToTrail(f,t) ((f)->trail = (t), (t) = (f), (f)->marked = TOOLS_GLU_TRUE)
126 126
127 //#define FreeTrail(t) if( 1 ) { while( (t) ! 127 //#define FreeTrail(t) if( 1 ) { while( (t) != NULL ) { (t)->marked = TOOLS_GLU_FALSE; t = (t)->trail; } } else
128 #define FreeTrail(t) do { while( (t) != NULL 128 #define FreeTrail(t) do { while( (t) != NULL ) { (t)->marked = TOOLS_GLU_FALSE; t = (t)->trail; } } while(false)
129 129
130 inline/*static*/ struct FaceCount static_Maxim 130 inline/*static*/ struct FaceCount static_MaximumFan( GLUhalfEdge *eOrig )
131 { 131 {
132 /* eOrig->Lface is the face we want to rende 132 /* eOrig->Lface is the face we want to render. We want to find the size
133 * of a maximal fan around eOrig->Org. To d 133 * of a maximal fan around eOrig->Org. To do this we just walk around
134 * the origin vertex as far as possible in b 134 * the origin vertex as far as possible in both directions.
135 */ 135 */
136 struct FaceCount newFace = { 0, NULL, &stati 136 struct FaceCount newFace = { 0, NULL, &static_RenderFan };
137 GLUface *trail = NULL; 137 GLUface *trail = NULL;
138 GLUhalfEdge *e; 138 GLUhalfEdge *e;
139 139
140 for( e = eOrig; ! Marked( e->Lface ); e = e- 140 for( e = eOrig; ! Marked( e->Lface ); e = e->Onext ) {
141 AddToTrail( e->Lface, trail ); 141 AddToTrail( e->Lface, trail );
142 ++newFace.size; 142 ++newFace.size;
143 } 143 }
144 for( e = eOrig; ! Marked( e->Rface ); e = e- 144 for( e = eOrig; ! Marked( e->Rface ); e = e->Oprev ) {
145 AddToTrail( e->Rface, trail ); 145 AddToTrail( e->Rface, trail );
146 ++newFace.size; 146 ++newFace.size;
147 } 147 }
148 newFace.eStart = e; 148 newFace.eStart = e;
149 /*LINTED*/ 149 /*LINTED*/
150 FreeTrail( trail ); 150 FreeTrail( trail );
151 return newFace; 151 return newFace;
152 } 152 }
153 153
154 154
155 #define IsEven(n) (((n) & 1) == 0) 155 #define IsEven(n) (((n) & 1) == 0)
156 156
157 inline/*static*/ struct FaceCount static_Maxim 157 inline/*static*/ struct FaceCount static_MaximumStrip( GLUhalfEdge *eOrig )
158 { 158 {
159 /* Here we are looking for a maximal strip t 159 /* Here we are looking for a maximal strip that contains the vertices
160 * eOrig->Org, eOrig->Dst, eOrig->Lnext->Dst 160 * eOrig->Org, eOrig->Dst, eOrig->Lnext->Dst (in that order or the
161 * reverse, such that all triangles are orie 161 * reverse, such that all triangles are oriented CCW).
162 * 162 *
163 * Again we walk forward and backward as far 163 * Again we walk forward and backward as far as possible. However for
164 * strips there is a twist: to get CCW orien 164 * strips there is a twist: to get CCW orientations, there must be
165 * an *even* number of triangles in the stri 165 * an *even* number of triangles in the strip on one side of eOrig.
166 * We walk the strip starting on a side with 166 * We walk the strip starting on a side with an even number of triangles;
167 * if both side have an odd number, we are f 167 * if both side have an odd number, we are forced to shorten one side.
168 */ 168 */
169 struct FaceCount newFace = { 0, NULL, &stati 169 struct FaceCount newFace = { 0, NULL, &static_RenderStrip };
170 long headSize = 0, tailSize = 0; 170 long headSize = 0, tailSize = 0;
171 GLUface *trail = NULL; 171 GLUface *trail = NULL;
172 GLUhalfEdge *e, *eTail, *eHead; 172 GLUhalfEdge *e, *eTail, *eHead;
173 173
174 for( e = eOrig; ! Marked( e->Lface ); ++tail 174 for( e = eOrig; ! Marked( e->Lface ); ++tailSize, e = e->Onext ) {
175 AddToTrail( e->Lface, trail ); 175 AddToTrail( e->Lface, trail );
176 ++tailSize; 176 ++tailSize;
177 e = e->Dprev; 177 e = e->Dprev;
178 if( Marked( e->Lface )) break; 178 if( Marked( e->Lface )) break;
179 AddToTrail( e->Lface, trail ); 179 AddToTrail( e->Lface, trail );
180 } 180 }
181 eTail = e; 181 eTail = e;
182 182
183 for( e = eOrig; ! Marked( e->Rface ); ++head 183 for( e = eOrig; ! Marked( e->Rface ); ++headSize, e = e->Dnext ) {
184 AddToTrail( e->Rface, trail ); 184 AddToTrail( e->Rface, trail );
185 ++headSize; 185 ++headSize;
186 e = e->Oprev; 186 e = e->Oprev;
187 if( Marked( e->Rface )) break; 187 if( Marked( e->Rface )) break;
188 AddToTrail( e->Rface, trail ); 188 AddToTrail( e->Rface, trail );
189 } 189 }
190 eHead = e; 190 eHead = e;
191 191
192 newFace.size = tailSize + headSize; 192 newFace.size = tailSize + headSize;
193 if( IsEven( tailSize )) { 193 if( IsEven( tailSize )) {
194 newFace.eStart = eTail->Sym; 194 newFace.eStart = eTail->Sym;
195 } else if( IsEven( headSize )) { 195 } else if( IsEven( headSize )) {
196 newFace.eStart = eHead; 196 newFace.eStart = eHead;
197 } else { 197 } else {
198 /* Both sides have odd length, we must sho 198 /* Both sides have odd length, we must shorten one of them. In fact,
199 * we must start from eHead to guarantee i 199 * we must start from eHead to guarantee inclusion of eOrig->Lface.
200 */ 200 */
201 --newFace.size; 201 --newFace.size;
202 newFace.eStart = eHead->Onext; 202 newFace.eStart = eHead->Onext;
203 } 203 }
204 /*LINTED*/ 204 /*LINTED*/
205 FreeTrail( trail ); 205 FreeTrail( trail );
206 return newFace; 206 return newFace;
207 } 207 }
208 208
209 209
210 inline/*static*/ void static_RenderTriangle( G 210 inline/*static*/ void static_RenderTriangle( GLUtesselator *tess, GLUhalfEdge *e, long size )
211 { 211 {
212 /* Just add the triangle to a triangle list, 212 /* Just add the triangle to a triangle list, so we can render all
213 * the separate triangles at once. 213 * the separate triangles at once.
214 */ 214 */
215 assert( size == 1 ); 215 assert( size == 1 );
216 AddToTrail( e->Lface, tess->lonelyTriList ); 216 AddToTrail( e->Lface, tess->lonelyTriList );
217 (void)size; 217 (void)size;
218 } 218 }
219 219
220 220
221 inline/*static*/ void static_RenderLonelyTrian 221 inline/*static*/ void static_RenderLonelyTriangles( GLUtesselator *tess, GLUface *f )
222 { 222 {
223 /* Now we render all the separate triangles 223 /* Now we render all the separate triangles which could not be
224 * grouped into a triangle fan or strip. 224 * grouped into a triangle fan or strip.
225 */ 225 */
226 GLUhalfEdge *e; 226 GLUhalfEdge *e;
227 int newState; 227 int newState;
228 int edgeState = -1; /* force edge state outp 228 int edgeState = -1; /* force edge state output for first vertex */
229 229
230 CALL_BEGIN_OR_BEGIN_DATA( GLU_TRIANGLES ); 230 CALL_BEGIN_OR_BEGIN_DATA( GLU_TRIANGLES );
231 231
232 for( ; f != NULL; f = f->trail ) { 232 for( ; f != NULL; f = f->trail ) {
233 /* Loop once for each edge (there will alw 233 /* Loop once for each edge (there will always be 3 edges) */
234 234
235 e = f->anEdge; 235 e = f->anEdge;
236 do { 236 do {
237 if( tess->flagBoundary ) { 237 if( tess->flagBoundary ) {
238 /* Set the "edge state" to TOOLS_GLU_TRUE ju 238 /* Set the "edge state" to TOOLS_GLU_TRUE just before we output the
239 * first vertex of each edge on the polygon 239 * first vertex of each edge on the polygon boundary.
240 */ 240 */
241 newState = ! e->Rface->inside; 241 newState = ! e->Rface->inside;
242 if( edgeState != newState ) { 242 if( edgeState != newState ) {
243 edgeState = newState; 243 edgeState = newState;
244 CALL_EDGE_FLAG_OR_EDGE_FLAG_DATA( ed 244 CALL_EDGE_FLAG_OR_EDGE_FLAG_DATA( edgeState );
245 } 245 }
246 } 246 }
247 CALL_VERTEX_OR_VERTEX_DATA( e->Org->data 247 CALL_VERTEX_OR_VERTEX_DATA( e->Org->data );
248 248
249 e = e->Lnext; 249 e = e->Lnext;
250 } while( e != f->anEdge ); 250 } while( e != f->anEdge );
251 } 251 }
252 CALL_END_OR_END_DATA(); 252 CALL_END_OR_END_DATA();
253 } 253 }
254 254
255 255
256 inline/*static*/ void static_RenderFan( GLUtes 256 inline/*static*/ void static_RenderFan( GLUtesselator *tess, GLUhalfEdge *e, long size )
257 { 257 {
258 /* Render as many CCW triangles as possible 258 /* Render as many CCW triangles as possible in a fan starting from
259 * edge "e". The fan *should* contain exact 259 * edge "e". The fan *should* contain exactly "size" triangles
260 * (otherwise we've goofed up somewhere). 260 * (otherwise we've goofed up somewhere).
261 */ 261 */
262 CALL_BEGIN_OR_BEGIN_DATA( GLU_TRIANGLE_FAN ) 262 CALL_BEGIN_OR_BEGIN_DATA( GLU_TRIANGLE_FAN );
263 CALL_VERTEX_OR_VERTEX_DATA( e->Org->data ); 263 CALL_VERTEX_OR_VERTEX_DATA( e->Org->data );
264 CALL_VERTEX_OR_VERTEX_DATA( e->Dst->data ); 264 CALL_VERTEX_OR_VERTEX_DATA( e->Dst->data );
265 265
266 while( ! Marked( e->Lface )) { 266 while( ! Marked( e->Lface )) {
267 e->Lface->marked = TOOLS_GLU_TRUE; 267 e->Lface->marked = TOOLS_GLU_TRUE;
268 --size; 268 --size;
269 e = e->Onext; 269 e = e->Onext;
270 CALL_VERTEX_OR_VERTEX_DATA( e->Dst->data ) 270 CALL_VERTEX_OR_VERTEX_DATA( e->Dst->data );
271 } 271 }
272 272
273 assert( size == 0 ); 273 assert( size == 0 );
274 CALL_END_OR_END_DATA(); 274 CALL_END_OR_END_DATA();
275 (void)size; <<
276 } 275 }
277 276
278 277
279 inline/*static*/ void static_RenderStrip( GLUt 278 inline/*static*/ void static_RenderStrip( GLUtesselator *tess, GLUhalfEdge *e, long size )
280 { 279 {
281 /* Render as many CCW triangles as possible 280 /* Render as many CCW triangles as possible in a strip starting from
282 * edge "e". The strip *should* contain exa 281 * edge "e". The strip *should* contain exactly "size" triangles
283 * (otherwise we've goofed up somewhere). 282 * (otherwise we've goofed up somewhere).
284 */ 283 */
285 CALL_BEGIN_OR_BEGIN_DATA( GLU_TRIANGLE_STRIP 284 CALL_BEGIN_OR_BEGIN_DATA( GLU_TRIANGLE_STRIP );
286 CALL_VERTEX_OR_VERTEX_DATA( e->Org->data ); 285 CALL_VERTEX_OR_VERTEX_DATA( e->Org->data );
287 CALL_VERTEX_OR_VERTEX_DATA( e->Dst->data ); 286 CALL_VERTEX_OR_VERTEX_DATA( e->Dst->data );
288 287
289 while( ! Marked( e->Lface )) { 288 while( ! Marked( e->Lface )) {
290 e->Lface->marked = TOOLS_GLU_TRUE; 289 e->Lface->marked = TOOLS_GLU_TRUE;
291 --size; 290 --size;
292 e = e->Dprev; 291 e = e->Dprev;
293 CALL_VERTEX_OR_VERTEX_DATA( e->Org->data ) 292 CALL_VERTEX_OR_VERTEX_DATA( e->Org->data );
294 if( Marked( e->Lface )) break; 293 if( Marked( e->Lface )) break;
295 294
296 e->Lface->marked = TOOLS_GLU_TRUE; 295 e->Lface->marked = TOOLS_GLU_TRUE;
297 --size; 296 --size;
298 e = e->Onext; 297 e = e->Onext;
299 CALL_VERTEX_OR_VERTEX_DATA( e->Dst->data ) 298 CALL_VERTEX_OR_VERTEX_DATA( e->Dst->data );
300 } 299 }
301 300
302 assert( size == 0 ); 301 assert( size == 0 );
303 CALL_END_OR_END_DATA(); 302 CALL_END_OR_END_DATA();
304 (void)size; <<
305 } 303 }
306 304
307 305
308 /************************ Boundary contour dec 306 /************************ Boundary contour decomposition ******************/
309 307
310 /* __gl_renderBoundary( tess, mesh ) takes a m 308 /* __gl_renderBoundary( tess, mesh ) takes a mesh, and outputs one
311 * contour for each face marked "inside". The 309 * contour for each face marked "inside". The rendering output is
312 * provided as callbacks (see the api). 310 * provided as callbacks (see the api).
313 */ 311 */
314 inline void __gl_renderBoundary( GLUtesselator 312 inline void __gl_renderBoundary( GLUtesselator *tess, GLUmesh *mesh )
315 { 313 {
316 GLUface *f; 314 GLUface *f;
317 GLUhalfEdge *e; 315 GLUhalfEdge *e;
318 316
319 for( f = mesh->fHead.next; f != &mesh->fHead 317 for( f = mesh->fHead.next; f != &mesh->fHead; f = f->next ) {
320 if( f->inside ) { 318 if( f->inside ) {
321 CALL_BEGIN_OR_BEGIN_DATA( GLU_LINE_LOOP 319 CALL_BEGIN_OR_BEGIN_DATA( GLU_LINE_LOOP );
322 e = f->anEdge; 320 e = f->anEdge;
323 do { 321 do {
324 CALL_VERTEX_OR_VERTEX_DATA( e->Org->da 322 CALL_VERTEX_OR_VERTEX_DATA( e->Org->data );
325 e = e->Lnext; 323 e = e->Lnext;
326 } while( e != f->anEdge ); 324 } while( e != f->anEdge );
327 CALL_END_OR_END_DATA(); 325 CALL_END_OR_END_DATA();
328 } 326 }
329 } 327 }
330 } 328 }
331 329
332 330
333 /************************ Quick-and-dirty deco 331 /************************ Quick-and-dirty decomposition ******************/
334 332
335 //#define SIGN_INCONSISTENT 2 333 //#define SIGN_INCONSISTENT 2
336 inline int SIGN_INCONSISTENT() { 334 inline int SIGN_INCONSISTENT() {
337 static const int s_value = 2; 335 static const int s_value = 2;
338 return s_value; 336 return s_value;
339 } 337 }
340 338
341 inline/*static*/ int static_ComputeNormal( GLU 339 inline/*static*/ int static_ComputeNormal( GLUtesselator *tess, GLUdouble norm[3], int check )
342 /* 340 /*
343 * If check==TOOLS_GLU_FALSE, we compute the p 341 * If check==TOOLS_GLU_FALSE, we compute the polygon normal and place it in norm[].
344 * If check==TOOLS_GLU_TRUE, we check that eac 342 * If check==TOOLS_GLU_TRUE, we check that each triangle in the fan from v0 has a
345 * consistent orientation with respect to norm 343 * consistent orientation with respect to norm[]. If triangles are
346 * consistently oriented CCW, return 1; if CW, 344 * consistently oriented CCW, return 1; if CW, return -1; if all triangles
347 * are degenerate return 0; otherwise (no cons 345 * are degenerate return 0; otherwise (no consistent orientation) return
348 * SIGN_INCONSISTENT. 346 * SIGN_INCONSISTENT.
349 */ 347 */
350 { 348 {
351 CachedVertex *v0 = tess->cache; 349 CachedVertex *v0 = tess->cache;
352 CachedVertex *vn = v0 + tess->cacheCount; 350 CachedVertex *vn = v0 + tess->cacheCount;
353 CachedVertex *vc; 351 CachedVertex *vc;
354 GLUdouble dot, xc, yc, zc, xp, yp, zp, n[3]; 352 GLUdouble dot, xc, yc, zc, xp, yp, zp, n[3];
355 int sign = 0; 353 int sign = 0;
356 354
357 /* Find the polygon normal. It is important 355 /* Find the polygon normal. It is important to get a reasonable
358 * normal even when the polygon is self-inte 356 * normal even when the polygon is self-intersecting (eg. a bowtie).
359 * Otherwise, the computed normal could be v 357 * Otherwise, the computed normal could be very tiny, but perpendicular
360 * to the true plane of the polygon due to n 358 * to the true plane of the polygon due to numerical noise. Then all
361 * the triangles would appear to be degenera 359 * the triangles would appear to be degenerate and we would incorrectly
362 * decompose the polygon as a fan (or simply 360 * decompose the polygon as a fan (or simply not render it at all).
363 * 361 *
364 * We use a sum-of-triangles normal algorith 362 * We use a sum-of-triangles normal algorithm rather than the more
365 * efficient sum-of-trapezoids method (used 363 * efficient sum-of-trapezoids method (used in CheckOrientation()
366 * in normal.c). This lets us explicitly re 364 * in normal.c). This lets us explicitly reverse the signed area
367 * of some triangles to get a reasonable nor 365 * of some triangles to get a reasonable normal in the self-intersecting
368 * case. 366 * case.
369 */ 367 */
370 if( ! check ) { 368 if( ! check ) {
371 norm[0] = norm[1] = norm[2] = 0.0; 369 norm[0] = norm[1] = norm[2] = 0.0;
372 } 370 }
373 371
374 vc = v0 + 1; 372 vc = v0 + 1;
375 xc = vc->coords[0] - v0->coords[0]; 373 xc = vc->coords[0] - v0->coords[0];
376 yc = vc->coords[1] - v0->coords[1]; 374 yc = vc->coords[1] - v0->coords[1];
377 zc = vc->coords[2] - v0->coords[2]; 375 zc = vc->coords[2] - v0->coords[2];
378 while( ++vc < vn ) { 376 while( ++vc < vn ) {
379 xp = xc; yp = yc; zp = zc; 377 xp = xc; yp = yc; zp = zc;
380 xc = vc->coords[0] - v0->coords[0]; 378 xc = vc->coords[0] - v0->coords[0];
381 yc = vc->coords[1] - v0->coords[1]; 379 yc = vc->coords[1] - v0->coords[1];
382 zc = vc->coords[2] - v0->coords[2]; 380 zc = vc->coords[2] - v0->coords[2];
383 381
384 /* Compute (vp - v0) cross (vc - v0) */ 382 /* Compute (vp - v0) cross (vc - v0) */
385 n[0] = yp*zc - zp*yc; 383 n[0] = yp*zc - zp*yc;
386 n[1] = zp*xc - xp*zc; 384 n[1] = zp*xc - xp*zc;
387 n[2] = xp*yc - yp*xc; 385 n[2] = xp*yc - yp*xc;
388 386
389 dot = n[0]*norm[0] + n[1]*norm[1] + n[2]*n 387 dot = n[0]*norm[0] + n[1]*norm[1] + n[2]*norm[2];
390 if( ! check ) { 388 if( ! check ) {
391 /* Reverse the contribution of back-faci 389 /* Reverse the contribution of back-facing triangles to get
392 * a reasonable normal for self-intersec 390 * a reasonable normal for self-intersecting polygons (see above)
393 */ 391 */
394 if( dot >= 0 ) { 392 if( dot >= 0 ) {
395 norm[0] += n[0]; norm[1] += n[1]; norm[2] += 393 norm[0] += n[0]; norm[1] += n[1]; norm[2] += n[2];
396 } else { 394 } else {
397 norm[0] -= n[0]; norm[1] -= n[1]; norm[2] -= 395 norm[0] -= n[0]; norm[1] -= n[1]; norm[2] -= n[2];
398 } 396 }
399 } else if( dot != 0 ) { 397 } else if( dot != 0 ) {
400 /* Check the new orientation for consist 398 /* Check the new orientation for consistency with previous triangles */
401 if( dot > 0 ) { 399 if( dot > 0 ) {
402 if( sign < 0 ) return SIGN_INCONSISTENT(); 400 if( sign < 0 ) return SIGN_INCONSISTENT();
403 sign = 1; 401 sign = 1;
404 } else { 402 } else {
405 if( sign > 0 ) return SIGN_INCONSISTENT(); 403 if( sign > 0 ) return SIGN_INCONSISTENT();
406 sign = -1; 404 sign = -1;
407 } 405 }
408 } 406 }
409 } 407 }
410 return sign; 408 return sign;
411 } 409 }
412 410
413 /* __gl_renderCache( tess ) takes a single con 411 /* __gl_renderCache( tess ) takes a single contour and tries to render it
414 * as a triangle fan. This handles convex pol 412 * as a triangle fan. This handles convex polygons, as well as some
415 * non-convex polygons if we get lucky. 413 * non-convex polygons if we get lucky.
416 * 414 *
417 * Returns TOOLS_GLU_TRUE if the polygon was s 415 * Returns TOOLS_GLU_TRUE if the polygon was successfully rendered. The rendering
418 * output is provided as callbacks (see the ap 416 * output is provided as callbacks (see the api).
419 */ 417 */
420 inline GLUboolean __gl_renderCache( GLUtessela 418 inline GLUboolean __gl_renderCache( GLUtesselator *tess )
421 { 419 {
422 CachedVertex *v0 = tess->cache; 420 CachedVertex *v0 = tess->cache;
423 CachedVertex *vn = v0 + tess->cacheCount; 421 CachedVertex *vn = v0 + tess->cacheCount;
424 CachedVertex *vc; 422 CachedVertex *vc;
425 GLUdouble norm[3]; 423 GLUdouble norm[3];
426 int sign; 424 int sign;
427 425
428 if( tess->cacheCount < 3 ) { 426 if( tess->cacheCount < 3 ) {
429 /* Degenerate contour -- no output */ 427 /* Degenerate contour -- no output */
430 return TOOLS_GLU_TRUE; 428 return TOOLS_GLU_TRUE;
431 } 429 }
432 430
433 norm[0] = tess->normal[0]; 431 norm[0] = tess->normal[0];
434 norm[1] = tess->normal[1]; 432 norm[1] = tess->normal[1];
435 norm[2] = tess->normal[2]; 433 norm[2] = tess->normal[2];
436 if( norm[0] == 0 && norm[1] == 0 && norm[2] 434 if( norm[0] == 0 && norm[1] == 0 && norm[2] == 0 ) {
437 static_ComputeNormal( tess, norm, TOOLS_GL 435 static_ComputeNormal( tess, norm, TOOLS_GLU_FALSE );
438 } 436 }
439 437
440 sign = static_ComputeNormal( tess, norm, TOO 438 sign = static_ComputeNormal( tess, norm, TOOLS_GLU_TRUE );
441 if( sign == SIGN_INCONSISTENT() ) { 439 if( sign == SIGN_INCONSISTENT() ) {
442 /* Fan triangles did not have a consistent 440 /* Fan triangles did not have a consistent orientation */
443 return TOOLS_GLU_FALSE; 441 return TOOLS_GLU_FALSE;
444 } 442 }
445 if( sign == 0 ) { 443 if( sign == 0 ) {
446 /* All triangles were degenerate */ 444 /* All triangles were degenerate */
447 return TOOLS_GLU_TRUE; 445 return TOOLS_GLU_TRUE;
448 } 446 }
449 447
450 /* Make sure we do the right thing for each 448 /* Make sure we do the right thing for each winding rule */
451 switch( tess->windingRule ) { 449 switch( tess->windingRule ) {
452 case GLU_TESS_WINDING_ODD: 450 case GLU_TESS_WINDING_ODD:
453 case GLU_TESS_WINDING_NONZERO: 451 case GLU_TESS_WINDING_NONZERO:
454 break; 452 break;
455 case GLU_TESS_WINDING_POSITIVE: 453 case GLU_TESS_WINDING_POSITIVE:
456 if( sign < 0 ) return TOOLS_GLU_TRUE; 454 if( sign < 0 ) return TOOLS_GLU_TRUE;
457 break; 455 break;
458 case GLU_TESS_WINDING_NEGATIVE: 456 case GLU_TESS_WINDING_NEGATIVE:
459 if( sign > 0 ) return TOOLS_GLU_TRUE; 457 if( sign > 0 ) return TOOLS_GLU_TRUE;
460 break; 458 break;
461 case GLU_TESS_WINDING_ABS_GEQ_TWO: 459 case GLU_TESS_WINDING_ABS_GEQ_TWO:
462 return TOOLS_GLU_TRUE; 460 return TOOLS_GLU_TRUE;
463 } 461 }
464 462
465 CALL_BEGIN_OR_BEGIN_DATA( tess->boundaryOnly 463 CALL_BEGIN_OR_BEGIN_DATA( tess->boundaryOnly ? GLU_LINE_LOOP
466 : (tess->cacheCount > 3) ? GLU_TRIANGL 464 : (tess->cacheCount > 3) ? GLU_TRIANGLE_FAN
467 : GLU_TRIANGLES ); 465 : GLU_TRIANGLES );
468 466
469 CALL_VERTEX_OR_VERTEX_DATA( v0->data ); 467 CALL_VERTEX_OR_VERTEX_DATA( v0->data );
470 if( sign > 0 ) { 468 if( sign > 0 ) {
471 for( vc = v0+1; vc < vn; ++vc ) { 469 for( vc = v0+1; vc < vn; ++vc ) {
472 CALL_VERTEX_OR_VERTEX_DATA( vc->data ); 470 CALL_VERTEX_OR_VERTEX_DATA( vc->data );
473 } 471 }
474 } else { 472 } else {
475 for( vc = vn-1; vc > v0; --vc ) { 473 for( vc = vn-1; vc > v0; --vc ) {
476 CALL_VERTEX_OR_VERTEX_DATA( vc->data ); 474 CALL_VERTEX_OR_VERTEX_DATA( vc->data );
477 } 475 }
478 } 476 }
479 CALL_END_OR_END_DATA(); 477 CALL_END_OR_END_DATA();
480 return TOOLS_GLU_TRUE; 478 return TOOLS_GLU_TRUE;
481 } 479 }
482 480
483 #endif 481 #endif