ReactOS 0.4.15-dev-8093-g3285f69
render.c File Reference
#include "gluos.h"
#include <assert.h>
#include "tess.h"
Include dependency graph for render.c:

Go to the source code of this file.

Classes

struct  FaceCount
 

Macros

#define TRUE   1
 
#define FALSE   0
 
#define Marked(f)   (! (f)->inside || (f)->marked)
 
#define AddToTrail(f, t)   ((f)->trail = (t), (t) = (f), (f)->marked = TRUE)
 
#define FreeTrail(t)
 
#define IsEven(n)   (((n) & 1) == 0)
 
#define SIGN_INCONSISTENT   2
 

Functions

static struct FaceCount MaximumFan (GLUhalfEdge *eOrig)
 
static struct FaceCount MaximumStrip (GLUhalfEdge *eOrig)
 
static void RenderFan (GLUtesselator *tess, GLUhalfEdge *eStart, long size)
 
static void RenderStrip (GLUtesselator *tess, GLUhalfEdge *eStart, long size)
 
static void RenderTriangle (GLUtesselator *tess, GLUhalfEdge *eStart, long size)
 
static void RenderMaximumFaceGroup (GLUtesselator *tess, GLUface *fOrig)
 
static void RenderLonelyTriangles (GLUtesselator *tess, GLUface *head)
 
void __gl_renderMesh (GLUtesselator *tess, GLUmesh *mesh)
 
void __gl_renderBoundary (GLUtesselator *tess, GLUmesh *mesh)
 
static int ComputeNormal (GLUtesselator *tess, GLdouble norm[3], int check)
 
GLboolean __gl_renderCache (GLUtesselator *tess)
 

Macro Definition Documentation

◆ AddToTrail

#define AddToTrail (   f,
  t 
)    ((f)->trail = (t), (t) = (f), (f)->marked = TRUE)

Definition at line 148 of file render.c.

◆ FALSE

#define FALSE   0

Definition at line 46 of file render.c.

◆ FreeTrail

#define FreeTrail (   t)
Value:
do { \
while( (t) != NULL ) { \
(t)->marked = FALSE; t = (t)->trail; \
} \
} while(0) /* absorb trailing semicolon */
#define NULL
Definition: types.h:112
#define FALSE
Definition: types.h:117
GLdouble GLdouble t
Definition: gl.h:2047

Definition at line 150 of file render.c.

◆ IsEven

#define IsEven (   n)    (((n) & 1) == 0)

Definition at line 183 of file render.c.

◆ Marked

#define Marked (   f)    (! (f)->inside || (f)->marked)

Definition at line 146 of file render.c.

◆ SIGN_INCONSISTENT

#define SIGN_INCONSISTENT   2

Definition at line 360 of file render.c.

◆ TRUE

#define TRUE   1

Definition at line 43 of file render.c.

Function Documentation

◆ __gl_renderBoundary()

void __gl_renderBoundary ( GLUtesselator tess,
GLUmesh mesh 
)

Definition at line 339 of file render.c.

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}
#define GL_LINE_LOOP
Definition: gl.h:192
GLfloat f
Definition: glext.h:7540
#define e
Definition: ke_i.h:82
#define f
Definition: ke_i.h:83
Definition: mesh.h:126
Definition: mesh.c:198
#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

Referenced by gluTessEndPolygon().

◆ __gl_renderCache()

GLboolean __gl_renderCache ( GLUtesselator tess)

Definition at line 441 of file render.c.

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
#define TRUE
Definition: types.h:120
#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
#define SIGN_INCONSISTENT
Definition: render.c:360
static int ComputeNormal(GLUtesselator *tess, GLdouble norm[3], int check)
Definition: render.c:362
#define GL_TRIANGLE_FAN
Definition: gl.h:196
double GLdouble
Definition: gl.h:163
#define GL_TRIANGLES
Definition: gl.h:194
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 sign(x)
Definition: mapdesc.cc:613
void * data
Definition: tess.h:56
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
CachedVertex cache[TESS_MAX_CACHE]
Definition: tess.h:108

Referenced by gluTessEndPolygon().

◆ __gl_renderMesh()

void __gl_renderMesh ( GLUtesselator tess,
GLUmesh mesh 
)

Definition at line 82 of file render.c.

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}
static void RenderMaximumFaceGroup(GLUtesselator *tess, GLUface *fOrig)
Definition: render.c:110
static void RenderLonelyTriangles(GLUtesselator *tess, GLUface *head)
Definition: render.c:248
#define assert(x)
Definition: debug.h:53
GLUface * lonelyTriList
Definition: tess.h:94

Referenced by gluTessEndPolygon().

◆ ComputeNormal()

static int ComputeNormal ( GLUtesselator tess,
GLdouble  norm[3],
int  check 
)
static

Definition at line 362 of file render.c.

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}
#define check(expected, result)
Definition: dplayx.c:32
GLdouble n
Definition: glext.h:7729
GLdouble coords[3]
Definition: tess.h:55

Referenced by __gl_renderCache().

◆ MaximumFan()

static struct FaceCount MaximumFan ( GLUhalfEdge eOrig)
static

Definition at line 158 of file render.c.

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}
#define FreeTrail(t)
Definition: render.c:150
static void RenderFan(GLUtesselator *tess, GLUhalfEdge *eStart, long size)
Definition: render.c:283
#define AddToTrail(f, t)
Definition: render.c:148
#define Marked(f)
Definition: render.c:146
long size
Definition: render.c:54
GLUhalfEdge * eStart
Definition: render.c:55

Referenced by RenderMaximumFaceGroup().

◆ MaximumStrip()

static struct FaceCount MaximumStrip ( GLUhalfEdge eOrig)
static

Definition at line 185 of file render.c.

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}
static void RenderStrip(GLUtesselator *tess, GLUhalfEdge *eStart, long size)
Definition: render.c:305
#define IsEven(n)
Definition: render.c:183
GLUhalfEdge * Onext
Definition: mesh.h:141
GLUhalfEdge * Sym
Definition: mesh.h:140

Referenced by RenderMaximumFaceGroup().

◆ RenderFan()

static void RenderFan ( GLUtesselator tess,
GLUhalfEdge eStart,
long  size 
)
static

Definition at line 283 of file render.c.

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}
GLsizeiptr size
Definition: glext.h:5919

Referenced by MaximumFan().

◆ RenderLonelyTriangles()

static void RenderLonelyTriangles ( GLUtesselator tess,
GLUface head 
)
static

Definition at line 248 of file render.c.

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}
GLboolean flagBoundary
Definition: tess.h:92
#define CALL_EDGE_FLAG_OR_EDGE_FLAG_DATA(a)
Definition: tess.h:145

Referenced by __gl_renderMesh().

◆ RenderMaximumFaceGroup()

static void RenderMaximumFaceGroup ( GLUtesselator tess,
GLUface fOrig 
)
static

Definition at line 110 of file render.c.

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}
static struct FaceCount MaximumFan(GLUhalfEdge *eOrig)
Definition: render.c:158
static struct FaceCount MaximumStrip(GLUhalfEdge *eOrig)
Definition: render.c:185
static void RenderTriangle(GLUtesselator *tess, GLUhalfEdge *eStart, long size)
Definition: render.c:238
GLUhalfEdge * anEdge
Definition: mesh.h:129
#define max(a, b)
Definition: svc.c:63

Referenced by __gl_renderMesh().

◆ RenderStrip()

static void RenderStrip ( GLUtesselator tess,
GLUhalfEdge eStart,
long  size 
)
static

Definition at line 305 of file render.c.

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}
#define GL_TRIANGLE_STRIP
Definition: gl.h:195

Referenced by MaximumStrip().

◆ RenderTriangle()

static void RenderTriangle ( GLUtesselator tess,
GLUhalfEdge eStart,
long  size 
)
static

Definition at line 238 of file render.c.

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}

Referenced by RenderMaximumFaceGroup().