| 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
9 * fans, strips, and separate triangles. A su
10 * to use as few rendering primitives as possi
11 * and strips as large as possible).
12 *
13 * The rendering output is provided as callbac
14 */
15 //void __gl_renderMesh( GLUtesselator *tess, G
16 //void __gl_renderBoundary( GLUtesselator *tes
17
18 //GLUboolean __gl_renderCache( GLUtesselator *
19
20 //////////////////////////////////////////////
21 /// inlined C code : /////////////////////////
22 //////////////////////////////////////////////
23
24 #include "_tess"
25
26 /* This structure remembers the information we
27 * to be able to render it later, once we have
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 pri
33 void (*render)(GLUtesselator *, GLUhalfEd
34 /* routine to
35 };
36
37 inline/*static*/ struct FaceCount static_Maxim
38 inline/*static*/ struct FaceCount static_Maxim
39
40 inline/*static*/ void static_RenderFan( GLUtes
41 inline/*static*/ void static_RenderStrip( GLUt
42 inline/*static*/ void static_RenderTriangle( G
43 long size );
44
45 inline/*static*/ void static_RenderMaximumFace
46 inline/*static*/ void static_RenderLonelyTrian
47
48
49
50 /************************ Strips and Fans deco
51
52 /* __gl_renderMesh( tess, mesh ) takes a mesh
53 * fans, strips, and separate triangles. A su
54 * to use as few rendering primitives as possi
55 * and strips as large as possible).
56 *
57 * The rendering output is provided as callbac
58 */
59 inline void __gl_renderMesh( GLUtesselator *te
60 {
61 GLUface *f;
62
63 /* Make a list of separate triangles so we c
64 tess->lonelyTriList = NULL;
65
66 for( f = mesh->fHead.next; f != &mesh->fHead
67 f->marked = TOOLS_GLU_FALSE;
68 }
69 for( f = mesh->fHead.next; f != &mesh->fHead
70
71 /* We examine all faces in an arbitrary or
72 * an unprocessed face F, we output a grou
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->
82 tess->lonelyTriList = NULL;
83 }
84 }
85
86
87 inline/*static*/ void static_RenderMaximumFace
88 {
89 /* We want to find the largest triangle fan
90 * which includes the given face fOrig. The
91 * passing through fOrig (one centered at ea
92 * strips (one for each CCW permutation of t
93 * is to try all of these, and take the prim
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( newF
105 newFace = static_MaximumFan( e->Lnext ); i
106 newFace = static_MaximumFan( e->Lprev ); i
107
108 newFace = static_MaximumStrip( e ); if( ne
109 newFace = static_MaximumStrip( e->Lnext );
110 newFace = static_MaximumStrip( e->Lprev );
111 }
112 (*(max.render))( tess, max.eStart, max.size
113 }
114
115
116 /* Macros which keep track of faces we have ma
117 * us to backtrack when necessary. With trian
118 * really necessary, since the only awkward ca
119 * around a single origin vertex. However wit
120 * more complicated, and we need a general tra
121 * one here.
122 */
123 #define Marked(f) (! (f)->inside || (f)->marke
124
125 #define AddToTrail(f,t) ((f)->trail = (t), (t)
126
127 //#define FreeTrail(t) if( 1 ) { while( (t) !
128 #define FreeTrail(t) do { while( (t) != NULL
129
130 inline/*static*/ struct FaceCount static_Maxim
131 {
132 /* eOrig->Lface is the face we want to rende
133 * of a maximal fan around eOrig->Org. To d
134 * the origin vertex as far as possible in b
135 */
136 struct FaceCount newFace = { 0, NULL, &stati
137 GLUface *trail = NULL;
138 GLUhalfEdge *e;
139
140 for( e = eOrig; ! Marked( e->Lface ); e = e-
141 AddToTrail( e->Lface, trail );
142 ++newFace.size;
143 }
144 for( e = eOrig; ! Marked( e->Rface ); e = e-
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_Maxim
158 {
159 /* Here we are looking for a maximal strip t
160 * eOrig->Org, eOrig->Dst, eOrig->Lnext->Dst
161 * reverse, such that all triangles are orie
162 *
163 * Again we walk forward and backward as far
164 * strips there is a twist: to get CCW orien
165 * an *even* number of triangles in the stri
166 * We walk the strip starting on a side with
167 * if both side have an odd number, we are f
168 */
169 struct FaceCount newFace = { 0, NULL, &stati
170 long headSize = 0, tailSize = 0;
171 GLUface *trail = NULL;
172 GLUhalfEdge *e, *eTail, *eHead;
173
174 for( e = eOrig; ! Marked( e->Lface ); ++tail
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 ); ++head
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 sho
199 * we must start from eHead to guarantee i
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( G
211 {
212 /* Just add the triangle to a triangle list,
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_RenderLonelyTrian
222 {
223 /* Now we render all the separate triangles
224 * grouped into a triangle fan or strip.
225 */
226 GLUhalfEdge *e;
227 int newState;
228 int edgeState = -1; /* force edge state outp
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 alw
234
235 e = f->anEdge;
236 do {
237 if( tess->flagBoundary ) {
238 /* Set the "edge state" to TOOLS_GLU_TRUE ju
239 * first vertex of each edge on the polygon
240 */
241 newState = ! e->Rface->inside;
242 if( edgeState != newState ) {
243 edgeState = newState;
244 CALL_EDGE_FLAG_OR_EDGE_FLAG_DATA( ed
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( GLUtes
257 {
258 /* Render as many CCW triangles as possible
259 * edge "e". The fan *should* contain exact
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( GLUt
280 {
281 /* Render as many CCW triangles as possible
282 * edge "e". The strip *should* contain exa
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 dec
309
310 /* __gl_renderBoundary( tess, mesh ) takes a m
311 * contour for each face marked "inside". The
312 * provided as callbacks (see the api).
313 */
314 inline void __gl_renderBoundary( GLUtesselator
315 {
316 GLUface *f;
317 GLUhalfEdge *e;
318
319 for( f = mesh->fHead.next; f != &mesh->fHead
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->da
325 e = e->Lnext;
326 } while( e != f->anEdge );
327 CALL_END_OR_END_DATA();
328 }
329 }
330 }
331
332
333 /************************ Quick-and-dirty deco
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( GLU
342 /*
343 * If check==TOOLS_GLU_FALSE, we compute the p
344 * If check==TOOLS_GLU_TRUE, we check that eac
345 * consistent orientation with respect to norm
346 * consistently oriented CCW, return 1; if CW,
347 * are degenerate return 0; otherwise (no cons
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
358 * normal even when the polygon is self-inte
359 * Otherwise, the computed normal could be v
360 * to the true plane of the polygon due to n
361 * the triangles would appear to be degenera
362 * decompose the polygon as a fan (or simply
363 *
364 * We use a sum-of-triangles normal algorith
365 * efficient sum-of-trapezoids method (used
366 * in normal.c). This lets us explicitly re
367 * of some triangles to get a reasonable nor
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]*n
390 if( ! check ) {
391 /* Reverse the contribution of back-faci
392 * a reasonable normal for self-intersec
393 */
394 if( dot >= 0 ) {
395 norm[0] += n[0]; norm[1] += n[1]; norm[2] +=
396 } else {
397 norm[0] -= n[0]; norm[1] -= n[1]; norm[2] -=
398 }
399 } else if( dot != 0 ) {
400 /* Check the new orientation for consist
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 con
414 * as a triangle fan. This handles convex pol
415 * non-convex polygons if we get lucky.
416 *
417 * Returns TOOLS_GLU_TRUE if the polygon was s
418 * output is provided as callbacks (see the ap
419 */
420 inline GLUboolean __gl_renderCache( GLUtessela
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]
437 static_ComputeNormal( tess, norm, TOOLS_GL
438 }
439
440 sign = static_ComputeNormal( tess, norm, TOO
441 if( sign == SIGN_INCONSISTENT() ) {
442 /* Fan triangles did not have a consistent
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
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
466 : (tess->cacheCount > 3) ? GLU_TRIANGL
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