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