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