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