ReactOS 0.4.15-dev-6052-g2626c72
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 */
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 );
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 assert( size == 1 );
244 AddToTrail( e->Lface, tess->lonelyTriList );
245}
246
247
249{
250 /* Now we render all the separate triangles which could not be
251 * grouped into a triangle fan or strip.
252 */
253 GLUhalfEdge *e;
254 int newState;
255 int edgeState = -1; /* force edge state output for first vertex */
256
258
259 for( ; f != NULL; f = f->trail ) {
260 /* Loop once for each edge (there will always be 3 edges) */
261
262 e = f->anEdge;
263 do {
264 if( tess->flagBoundary ) {
265 /* Set the "edge state" to TRUE just before we output the
266 * first vertex of each edge on the polygon boundary.
267 */
268 newState = ! e->Rface->inside;
269 if( edgeState != newState ) {
270 edgeState = newState;
272 }
273 }
274 CALL_VERTEX_OR_VERTEX_DATA( e->Org->data );
275
276 e = e->Lnext;
277 } while( e != f->anEdge );
278 }
280}
281
282
283static void RenderFan( GLUtesselator *tess, GLUhalfEdge *e, long size )
284{
285 /* Render as many CCW triangles as possible in a fan starting from
286 * edge "e". The fan *should* contain exactly "size" triangles
287 * (otherwise we've goofed up somewhere).
288 */
290 CALL_VERTEX_OR_VERTEX_DATA( e->Org->data );
291 CALL_VERTEX_OR_VERTEX_DATA( e->Dst->data );
292
293 while( ! Marked( e->Lface )) {
294 e->Lface->marked = TRUE;
295 --size;
296 e = e->Onext;
297 CALL_VERTEX_OR_VERTEX_DATA( e->Dst->data );
298 }
299
300 assert( size == 0 );
302}
303
304
305static void RenderStrip( GLUtesselator *tess, GLUhalfEdge *e, long size )
306{
307 /* Render as many CCW triangles as possible in a strip starting from
308 * edge "e". The strip *should* contain exactly "size" triangles
309 * (otherwise we've goofed up somewhere).
310 */
312 CALL_VERTEX_OR_VERTEX_DATA( e->Org->data );
313 CALL_VERTEX_OR_VERTEX_DATA( e->Dst->data );
314
315 while( ! Marked( e->Lface )) {
316 e->Lface->marked = TRUE;
317 --size;
318 e = e->Dprev;
319 CALL_VERTEX_OR_VERTEX_DATA( e->Org->data );
320 if( Marked( e->Lface )) break;
321
322 e->Lface->marked = TRUE;
323 --size;
324 e = e->Onext;
325 CALL_VERTEX_OR_VERTEX_DATA( e->Dst->data );
326 }
327
328 assert( size == 0 );
330}
331
332
333/************************ Boundary contour decomposition ******************/
334
335/* __gl_renderBoundary( tess, mesh ) takes a mesh, and outputs one
336 * contour for each face marked "inside". The rendering output is
337 * provided as callbacks (see the api).
338 */
340{
341 GLUface *f;
342 GLUhalfEdge *e;
343
344 for( f = mesh->fHead.next; f != &mesh->fHead; f = f->next ) {
345 if( f->inside ) {
347 e = f->anEdge;
348 do {
349 CALL_VERTEX_OR_VERTEX_DATA( e->Org->data );
350 e = e->Lnext;
351 } while( e != f->anEdge );
353 }
354 }
355}
356
357
358/************************ Quick-and-dirty decomposition ******************/
359
360#define SIGN_INCONSISTENT 2
361
362static int ComputeNormal( GLUtesselator *tess, GLdouble norm[3], int check )
363/*
364 * If check==FALSE, we compute the polygon normal and place it in norm[].
365 * If check==TRUE, we check that each triangle in the fan from v0 has a
366 * consistent orientation with respect to norm[]. If triangles are
367 * consistently oriented CCW, return 1; if CW, return -1; if all triangles
368 * are degenerate return 0; otherwise (no consistent orientation) return
369 * SIGN_INCONSISTENT.
370 */
371{
372 CachedVertex *v0 = tess->cache;
373 CachedVertex *vn = v0 + tess->cacheCount;
374 CachedVertex *vc;
375 GLdouble dot, xc, yc, zc, xp, yp, zp, n[3];
376 int sign = 0;
377
378 /* Find the polygon normal. It is important to get a reasonable
379 * normal even when the polygon is self-intersecting (eg. a bowtie).
380 * Otherwise, the computed normal could be very tiny, but perpendicular
381 * to the true plane of the polygon due to numerical noise. Then all
382 * the triangles would appear to be degenerate and we would incorrectly
383 * decompose the polygon as a fan (or simply not render it at all).
384 *
385 * We use a sum-of-triangles normal algorithm rather than the more
386 * efficient sum-of-trapezoids method (used in CheckOrientation()
387 * in normal.c). This lets us explicitly reverse the signed area
388 * of some triangles to get a reasonable normal in the self-intersecting
389 * case.
390 */
391 if( ! check ) {
392 norm[0] = norm[1] = norm[2] = 0.0;
393 }
394
395 vc = v0 + 1;
396 xc = vc->coords[0] - v0->coords[0];
397 yc = vc->coords[1] - v0->coords[1];
398 zc = vc->coords[2] - v0->coords[2];
399 while( ++vc < vn ) {
400 xp = xc; yp = yc; zp = zc;
401 xc = vc->coords[0] - v0->coords[0];
402 yc = vc->coords[1] - v0->coords[1];
403 zc = vc->coords[2] - v0->coords[2];
404
405 /* Compute (vp - v0) cross (vc - v0) */
406 n[0] = yp*zc - zp*yc;
407 n[1] = zp*xc - xp*zc;
408 n[2] = xp*yc - yp*xc;
409
410 dot = n[0]*norm[0] + n[1]*norm[1] + n[2]*norm[2];
411 if( ! check ) {
412 /* Reverse the contribution of back-facing triangles to get
413 * a reasonable normal for self-intersecting polygons (see above)
414 */
415 if( dot >= 0 ) {
416 norm[0] += n[0]; norm[1] += n[1]; norm[2] += n[2];
417 } else {
418 norm[0] -= n[0]; norm[1] -= n[1]; norm[2] -= n[2];
419 }
420 } else if( dot != 0 ) {
421 /* Check the new orientation for consistency with previous triangles */
422 if( dot > 0 ) {
423 if( sign < 0 ) return SIGN_INCONSISTENT;
424 sign = 1;
425 } else {
426 if( sign > 0 ) return SIGN_INCONSISTENT;
427 sign = -1;
428 }
429 }
430 }
431 return sign;
432}
433
434/* __gl_renderCache( tess ) takes a single contour and tries to render it
435 * as a triangle fan. This handles convex polygons, as well as some
436 * non-convex polygons if we get lucky.
437 *
438 * Returns TRUE if the polygon was successfully rendered. The rendering
439 * output is provided as callbacks (see the api).
440 */
442{
443 CachedVertex *v0 = tess->cache;
444 CachedVertex *vn = v0 + tess->cacheCount;
445 CachedVertex *vc;
446 GLdouble norm[3];
447 int sign;
448
449 if( tess->cacheCount < 3 ) {
450 /* Degenerate contour -- no output */
451 return TRUE;
452 }
453
454 norm[0] = tess->normal[0];
455 norm[1] = tess->normal[1];
456 norm[2] = tess->normal[2];
457 if( norm[0] == 0 && norm[1] == 0 && norm[2] == 0 ) {
458 ComputeNormal( tess, norm, FALSE );
459 }
460
461 sign = ComputeNormal( tess, norm, TRUE );
462 if( sign == SIGN_INCONSISTENT ) {
463 /* Fan triangles did not have a consistent orientation */
464 return FALSE;
465 }
466 if( sign == 0 ) {
467 /* All triangles were degenerate */
468 return TRUE;
469 }
470
471 /* Make sure we do the right thing for each winding rule */
472 switch( tess->windingRule ) {
475 break;
477 if( sign < 0 ) return TRUE;
478 break;
480 if( sign > 0 ) return TRUE;
481 break;
483 return TRUE;
484 }
485
487 : (tess->cacheCount > 3) ? GL_TRIANGLE_FAN
488 : GL_TRIANGLES );
489
491 if( sign > 0 ) {
492 for( vc = v0+1; vc < vn; ++vc ) {
494 }
495 } else {
496 for( vc = vn-1; vc > v0; --vc ) {
498 }
499 }
501 return TRUE;
502}
_Tp _STLP_CALL norm(const complex< _Tp > &__z)
Definition: _complex.h:741
struct outqueuenode * head
Definition: adnsresfilter.c:66
#define NULL
Definition: types.h:112
#define TRUE
Definition: types.h:120
#define FALSE
Definition: types.h:117
#define GLU_TESS_WINDING_NONZERO
Definition: glu.h:261
#define GLU_TESS_WINDING_POSITIVE
Definition: glu.h:262
#define GLU_TESS_WINDING_NEGATIVE
Definition: glu.h:263
#define GLU_TESS_WINDING_ODD
Definition: glu.h:260
#define GLU_TESS_WINDING_ABS_GEQ_TWO
Definition: glu.h:264
static struct FaceCount MaximumFan(GLUhalfEdge *eOrig)
Definition: render.c:158
static void RenderStrip(GLUtesselator *tess, GLUhalfEdge *eStart, long size)
Definition: render.c:305
#define SIGN_INCONSISTENT
Definition: render.c:360
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:441
static void RenderLonelyTriangles(GLUtesselator *tess, GLUface *head)
Definition: render.c:248
static void RenderTriangle(GLUtesselator *tess, GLUhalfEdge *eStart, long size)
Definition: render.c:238
#define IsEven(n)
Definition: render.c:183
void __gl_renderMesh(GLUtesselator *tess, GLUmesh *mesh)
Definition: render.c:82
void __gl_renderBoundary(GLUtesselator *tess, GLUmesh *mesh)
Definition: render.c:339
static void RenderFan(GLUtesselator *tess, GLUhalfEdge *eStart, long size)
Definition: render.c:283
#define AddToTrail(f, t)
Definition: render.c:148
static int ComputeNormal(GLUtesselator *tess, GLdouble norm[3], int check)
Definition: render.c:362
#define Marked(f)
Definition: render.c:146
#define assert(x)
Definition: debug.h:53
#define check(expected, result)
Definition: dplayx.c:32
#define GL_TRIANGLE_FAN
Definition: gl.h:196
double GLdouble
Definition: gl.h:163
#define GL_TRIANGLES
Definition: gl.h:194
#define GL_LINE_LOOP
Definition: gl.h:192
#define GL_TRIANGLE_STRIP
Definition: gl.h:195
unsigned char GLboolean
Definition: gl.h:151
GLsizeiptr size
Definition: glext.h:5919
GLdouble n
Definition: glext.h:7729
GLfloat f
Definition: glext.h:7540
GLfloat v0
Definition: glext.h:6061
GLsizei GLenum const GLvoid GLsizei GLenum GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLint GLint GLint GLshort GLshort GLshort GLubyte GLubyte GLubyte GLuint GLuint GLuint GLushort GLushort GLushort GLbyte GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLfloat GLint GLint GLint GLint GLshort GLshort GLshort GLshort GLubyte GLubyte GLubyte GLubyte GLuint GLuint GLuint GLuint GLushort GLushort GLushort GLushort GLboolean const GLdouble const GLfloat const GLint const GLshort const GLbyte const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLdouble const GLfloat const GLfloat const GLint const GLint const GLshort const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort GLenum GLenum GLenum GLfloat GLenum GLint GLenum GLenum GLenum GLfloat GLenum GLenum GLint GLenum GLfloat GLenum GLint GLint GLushort GLenum GLenum GLfloat GLenum GLenum GLint GLfloat const GLubyte GLenum GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLint GLint GLsizei GLsizei GLint GLenum GLenum const GLvoid GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLenum const GLdouble GLenum GLenum const GLfloat GLenum GLenum const GLint GLsizei GLuint GLfloat GLuint GLbitfield GLfloat GLint GLuint GLboolean GLenum GLfloat GLenum GLbitfield GLenum GLfloat GLfloat GLint GLint const GLfloat GLenum GLfloat GLfloat GLint GLint GLfloat GLfloat GLint GLint const GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat GLint vn
Definition: glfuncs.h:238
#define e
Definition: ke_i.h:82
#define f
Definition: ke_i.h:83
#define sign(x)
Definition: mapdesc.cc:613
#define long
Definition: qsort.c:33
void * data
Definition: tess.h:56
GLdouble coords[3]
Definition: tess.h:55
long size
Definition: render.c:54
void(* render)(GLUtesselator *, GLUhalfEdge *, long)
Definition: render.c:56
GLUhalfEdge * eStart
Definition: render.c:55
Definition: mesh.h:126
GLUhalfEdge * anEdge
Definition: mesh.h:129
GLUhalfEdge * Onext
Definition: mesh.h:141
GLUhalfEdge * Sym
Definition: mesh.h:140
Definition: mesh.h:163
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
Definition: mesh.c:198
#define max(a, b)
Definition: svc.c:63
#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