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