oleaut32: Remove unnecessary consts.
[wine.git] / dlls / glu32 / render.c
blob16026a8f9d8a66e33126003c2afdf5f218b9595e
1 /*
2 * SGI FREE SOFTWARE LICENSE B (Version 2.0, Sept. 18, 2008)
3 * Copyright (C) 1991-2000 Silicon Graphics, Inc. All Rights Reserved.
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:
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.
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.
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.
31 ** Author: Eric Veach, July 1994.
35 #include <stdarg.h>
36 #include <assert.h>
38 #include "windef.h"
39 #include "winbase.h"
41 #include "mesh.h"
42 #include "tess.h"
44 /* This structure remembers the information we need about a primitive
45 * to be able to render it later, once we have determined which
46 * primitive is able to use the most triangles.
48 struct FaceCount {
49 long size; /* number of triangles used */
50 GLUhalfEdge *eStart; /* edge where this primitive starts */
51 void (*render)(GLUtesselator *, GLUhalfEdge *, long);
52 /* routine to render this primitive */
55 static struct FaceCount MaximumFan( GLUhalfEdge *eOrig );
56 static struct FaceCount MaximumStrip( GLUhalfEdge *eOrig );
58 static void RenderFan( GLUtesselator *tess, GLUhalfEdge *eStart, long size );
59 static void RenderStrip( GLUtesselator *tess, GLUhalfEdge *eStart, long size );
60 static void RenderTriangle( GLUtesselator *tess, GLUhalfEdge *eStart,
61 long size );
63 static void RenderMaximumFaceGroup( GLUtesselator *tess, GLUface *fOrig );
64 static void RenderLonelyTriangles( GLUtesselator *tess, GLUface *head );
68 /************************ Strips and Fans decomposition ******************/
70 /* __gl_renderMesh( tess, mesh ) takes a mesh and breaks it into triangle
71 * fans, strips, and separate triangles. A substantial effort is made
72 * to use as few rendering primitives as possible (ie. to make the fans
73 * and strips as large as possible).
75 * The rendering output is provided as callbacks (see the api).
77 void __gl_renderMesh( GLUtesselator *tess, GLUmesh *mesh )
79 GLUface *f;
81 /* Make a list of separate triangles so we can render them all at once */
82 tess->lonelyTriList = NULL;
84 for( f = mesh->fHead.next; f != &mesh->fHead; f = f->next ) {
85 f->marked = FALSE;
87 for( f = mesh->fHead.next; f != &mesh->fHead; f = f->next ) {
89 /* We examine all faces in an arbitrary order. Whenever we find
90 * an unprocessed face F, we output a group of faces including F
91 * whose size is maximum.
93 if( f->inside && ! f->marked ) {
94 RenderMaximumFaceGroup( tess, f );
95 assert( f->marked );
98 if( tess->lonelyTriList != NULL ) {
99 RenderLonelyTriangles( tess, tess->lonelyTriList );
100 tess->lonelyTriList = NULL;
105 static void RenderMaximumFaceGroup( GLUtesselator *tess, GLUface *fOrig )
107 /* We want to find the largest triangle fan or strip of unmarked faces
108 * which includes the given face fOrig. There are 3 possible fans
109 * passing through fOrig (one centered at each vertex), and 3 possible
110 * strips (one for each CCW permutation of the vertices). Our strategy
111 * is to try all of these, and take the primitive which uses the most
112 * triangles (a greedy approach).
114 GLUhalfEdge *e = fOrig->anEdge;
115 struct FaceCount max, newFace;
117 max.size = 1;
118 max.eStart = e;
119 max.render = &RenderTriangle;
121 if( ! tess->flagBoundary ) {
122 newFace = MaximumFan( e ); if( newFace.size > max.size ) { max = newFace; }
123 newFace = MaximumFan( e->Lnext ); if( newFace.size > max.size ) { max = newFace; }
124 newFace = MaximumFan( e->Lprev ); if( newFace.size > max.size ) { max = newFace; }
126 newFace = MaximumStrip( e ); if( newFace.size > max.size ) { max = newFace; }
127 newFace = MaximumStrip( e->Lnext ); if( newFace.size > max.size ) { max = newFace; }
128 newFace = MaximumStrip( e->Lprev ); if( newFace.size > max.size ) { max = newFace; }
130 (*(max.render))( tess, max.eStart, max.size );
134 /* Macros which keep track of faces we have marked temporarily, and allow
135 * us to backtrack when necessary. With triangle fans, this is not
136 * really necessary, since the only awkward case is a loop of triangles
137 * around a single origin vertex. However with strips the situation is
138 * more complicated, and we need a general tracking method like the
139 * one here.
141 #define Marked(f) (! (f)->inside || (f)->marked)
143 #define AddToTrail(f,t) ((f)->trail = (t), (t) = (f), (f)->marked = TRUE)
145 #define FreeTrail(t) do { \
146 while( (t) != NULL ) { \
147 (t)->marked = FALSE; t = (t)->trail; \
149 } while(0) /* absorb trailing semicolon */
153 static struct FaceCount MaximumFan( GLUhalfEdge *eOrig )
155 /* eOrig->Lface is the face we want to render. We want to find the size
156 * of a maximal fan around eOrig->Org. To do this we just walk around
157 * the origin vertex as far as possible in both directions.
159 struct FaceCount newFace = { 0, NULL, &RenderFan };
160 GLUface *trail = NULL;
161 GLUhalfEdge *e;
163 for( e = eOrig; ! Marked( e->Lface ); e = e->Onext ) {
164 AddToTrail( e->Lface, trail );
165 ++newFace.size;
167 for( e = eOrig; ! Marked( e->Rface ); e = e->Oprev ) {
168 AddToTrail( e->Rface, trail );
169 ++newFace.size;
171 newFace.eStart = e;
172 /*LINTED*/
173 FreeTrail( trail );
174 return newFace;
178 #define IsEven(n) (((n) & 1) == 0)
180 static struct FaceCount MaximumStrip( GLUhalfEdge *eOrig )
182 /* Here we are looking for a maximal strip that contains the vertices
183 * eOrig->Org, eOrig->Dst, eOrig->Lnext->Dst (in that order or the
184 * reverse, such that all triangles are oriented CCW).
186 * Again we walk forward and backward as far as possible. However for
187 * strips there is a twist: to get CCW orientations, there must be
188 * an *even* number of triangles in the strip on one side of eOrig.
189 * We walk the strip starting on a side with an even number of triangles;
190 * if both side have an odd number, we are forced to shorten one side.
192 struct FaceCount newFace = { 0, NULL, &RenderStrip };
193 long headSize = 0, tailSize = 0;
194 GLUface *trail = NULL;
195 GLUhalfEdge *e, *eTail, *eHead;
197 for( e = eOrig; ! Marked( e->Lface ); ++tailSize, e = e->Onext ) {
198 AddToTrail( e->Lface, trail );
199 ++tailSize;
200 e = e->Dprev;
201 if( Marked( e->Lface )) break;
202 AddToTrail( e->Lface, trail );
204 eTail = e;
206 for( e = eOrig; ! Marked( e->Rface ); ++headSize, e = e->Dnext ) {
207 AddToTrail( e->Rface, trail );
208 ++headSize;
209 e = e->Oprev;
210 if( Marked( e->Rface )) break;
211 AddToTrail( e->Rface, trail );
213 eHead = e;
215 newFace.size = tailSize + headSize;
216 if( IsEven( tailSize )) {
217 newFace.eStart = eTail->Sym;
218 } else if( IsEven( headSize )) {
219 newFace.eStart = eHead;
220 } else {
221 /* Both sides have odd length, we must shorten one of them. In fact,
222 * we must start from eHead to guarantee inclusion of eOrig->Lface.
224 --newFace.size;
225 newFace.eStart = eHead->Onext;
227 /*LINTED*/
228 FreeTrail( trail );
229 return newFace;
233 static void RenderTriangle( GLUtesselator *tess, GLUhalfEdge *e, long size )
235 /* Just add the triangle to a triangle list, so we can render all
236 * the separate triangles at once.
238 assert( size == 1 );
239 AddToTrail( e->Lface, tess->lonelyTriList );
243 static void RenderLonelyTriangles( GLUtesselator *tess, GLUface *f )
245 /* Now we render all the separate triangles which could not be
246 * grouped into a triangle fan or strip.
248 GLUhalfEdge *e;
249 int newState;
250 int edgeState = -1; /* force edge state output for first vertex */
252 CALL_BEGIN_OR_BEGIN_DATA( GL_TRIANGLES );
254 for( ; f != NULL; f = f->trail ) {
255 /* Loop once for each edge (there will always be 3 edges) */
257 e = f->anEdge;
258 do {
259 if( tess->flagBoundary ) {
260 /* Set the "edge state" to TRUE just before we output the
261 * first vertex of each edge on the polygon boundary.
263 newState = ! e->Rface->inside;
264 if( edgeState != newState ) {
265 edgeState = newState;
266 CALL_EDGE_FLAG_OR_EDGE_FLAG_DATA( edgeState );
269 CALL_VERTEX_OR_VERTEX_DATA( e->Org->data );
271 e = e->Lnext;
272 } while( e != f->anEdge );
274 CALL_END_OR_END_DATA();
278 static void RenderFan( GLUtesselator *tess, GLUhalfEdge *e, long size )
280 /* Render as many CCW triangles as possible in a fan starting from
281 * edge "e". The fan *should* contain exactly "size" triangles
282 * (otherwise we've goofed up somewhere).
284 CALL_BEGIN_OR_BEGIN_DATA( GL_TRIANGLE_FAN );
285 CALL_VERTEX_OR_VERTEX_DATA( e->Org->data );
286 CALL_VERTEX_OR_VERTEX_DATA( e->Dst->data );
288 while( ! Marked( e->Lface )) {
289 e->Lface->marked = TRUE;
290 --size;
291 e = e->Onext;
292 CALL_VERTEX_OR_VERTEX_DATA( e->Dst->data );
295 assert( size == 0 );
296 CALL_END_OR_END_DATA();
300 static void RenderStrip( GLUtesselator *tess, GLUhalfEdge *e, long size )
302 /* Render as many CCW triangles as possible in a strip starting from
303 * edge "e". The strip *should* contain exactly "size" triangles
304 * (otherwise we've goofed up somewhere).
306 CALL_BEGIN_OR_BEGIN_DATA( GL_TRIANGLE_STRIP );
307 CALL_VERTEX_OR_VERTEX_DATA( e->Org->data );
308 CALL_VERTEX_OR_VERTEX_DATA( e->Dst->data );
310 while( ! Marked( e->Lface )) {
311 e->Lface->marked = TRUE;
312 --size;
313 e = e->Dprev;
314 CALL_VERTEX_OR_VERTEX_DATA( e->Org->data );
315 if( Marked( e->Lface )) break;
317 e->Lface->marked = TRUE;
318 --size;
319 e = e->Onext;
320 CALL_VERTEX_OR_VERTEX_DATA( e->Dst->data );
323 assert( size == 0 );
324 CALL_END_OR_END_DATA();
328 /************************ Boundary contour decomposition ******************/
330 /* __gl_renderBoundary( tess, mesh ) takes a mesh, and outputs one
331 * contour for each face marked "inside". The rendering output is
332 * provided as callbacks (see the api).
334 void __gl_renderBoundary( GLUtesselator *tess, GLUmesh *mesh )
336 GLUface *f;
337 GLUhalfEdge *e;
339 for( f = mesh->fHead.next; f != &mesh->fHead; f = f->next ) {
340 if( f->inside ) {
341 CALL_BEGIN_OR_BEGIN_DATA( GL_LINE_LOOP );
342 e = f->anEdge;
343 do {
344 CALL_VERTEX_OR_VERTEX_DATA( e->Org->data );
345 e = e->Lnext;
346 } while( e != f->anEdge );
347 CALL_END_OR_END_DATA();
353 /************************ Quick-and-dirty decomposition ******************/
355 #define SIGN_INCONSISTENT 2
357 static int ComputeNormal( GLUtesselator *tess, GLdouble norm[3], int check )
359 * If check==FALSE, we compute the polygon normal and place it in norm[].
360 * If check==TRUE, we check that each triangle in the fan from v0 has a
361 * consistent orientation with respect to norm[]. If triangles are
362 * consistently oriented CCW, return 1; if CW, return -1; if all triangles
363 * are degenerate return 0; otherwise (no consistent orientation) return
364 * SIGN_INCONSISTENT.
367 CachedVertex *v0 = tess->cache;
368 CachedVertex *vn = v0 + tess->cacheCount;
369 CachedVertex *vc;
370 GLdouble dot, xc, yc, zc, xp, yp, zp, n[3];
371 int sign = 0;
373 /* Find the polygon normal. It is important to get a reasonable
374 * normal even when the polygon is self-intersecting (eg. a bowtie).
375 * Otherwise, the computed normal could be very tiny, but perpendicular
376 * to the true plane of the polygon due to numerical noise. Then all
377 * the triangles would appear to be degenerate and we would incorrectly
378 * decompose the polygon as a fan (or simply not render it at all).
380 * We use a sum-of-triangles normal algorithm rather than the more
381 * efficient sum-of-trapezoids method (used in CheckOrientation()
382 * in normal.c). This lets us explicitly reverse the signed area
383 * of some triangles to get a reasonable normal in the self-intersecting
384 * case.
386 if( ! check ) {
387 norm[0] = norm[1] = norm[2] = 0.0;
390 vc = v0 + 1;
391 xc = vc->coords[0] - v0->coords[0];
392 yc = vc->coords[1] - v0->coords[1];
393 zc = vc->coords[2] - v0->coords[2];
394 while( ++vc < vn ) {
395 xp = xc; yp = yc; zp = zc;
396 xc = vc->coords[0] - v0->coords[0];
397 yc = vc->coords[1] - v0->coords[1];
398 zc = vc->coords[2] - v0->coords[2];
400 /* Compute (vp - v0) cross (vc - v0) */
401 n[0] = yp*zc - zp*yc;
402 n[1] = zp*xc - xp*zc;
403 n[2] = xp*yc - yp*xc;
405 dot = n[0]*norm[0] + n[1]*norm[1] + n[2]*norm[2];
406 if( ! check ) {
407 /* Reverse the contribution of back-facing triangles to get
408 * a reasonable normal for self-intersecting polygons (see above)
410 if( dot >= 0 ) {
411 norm[0] += n[0]; norm[1] += n[1]; norm[2] += n[2];
412 } else {
413 norm[0] -= n[0]; norm[1] -= n[1]; norm[2] -= n[2];
415 } else if( dot != 0 ) {
416 /* Check the new orientation for consistency with previous triangles */
417 if( dot > 0 ) {
418 if( sign < 0 ) return SIGN_INCONSISTENT;
419 sign = 1;
420 } else {
421 if( sign > 0 ) return SIGN_INCONSISTENT;
422 sign = -1;
426 return sign;
429 /* __gl_renderCache( tess ) takes a single contour and tries to render it
430 * as a triangle fan. This handles convex polygons, as well as some
431 * non-convex polygons if we get lucky.
433 * Returns TRUE if the polygon was successfully rendered. The rendering
434 * output is provided as callbacks (see the api).
436 GLboolean __gl_renderCache( GLUtesselator *tess )
438 CachedVertex *v0 = tess->cache;
439 CachedVertex *vn = v0 + tess->cacheCount;
440 CachedVertex *vc;
441 GLdouble norm[3];
442 int sign;
444 if( tess->cacheCount < 3 ) {
445 /* Degenerate contour -- no output */
446 return TRUE;
449 norm[0] = tess->normal[0];
450 norm[1] = tess->normal[1];
451 norm[2] = tess->normal[2];
452 if( norm[0] == 0 && norm[1] == 0 && norm[2] == 0 ) {
453 ComputeNormal( tess, norm, FALSE );
456 sign = ComputeNormal( tess, norm, TRUE );
457 if( sign == SIGN_INCONSISTENT ) {
458 /* Fan triangles did not have a consistent orientation */
459 return FALSE;
461 if( sign == 0 ) {
462 /* All triangles were degenerate */
463 return TRUE;
466 /* Make sure we do the right thing for each winding rule */
467 switch( tess->windingRule ) {
468 case GLU_TESS_WINDING_ODD:
469 case GLU_TESS_WINDING_NONZERO:
470 break;
471 case GLU_TESS_WINDING_POSITIVE:
472 if( sign < 0 ) return TRUE;
473 break;
474 case GLU_TESS_WINDING_NEGATIVE:
475 if( sign > 0 ) return TRUE;
476 break;
477 case GLU_TESS_WINDING_ABS_GEQ_TWO:
478 return TRUE;
481 CALL_BEGIN_OR_BEGIN_DATA( tess->boundaryOnly ? GL_LINE_LOOP
482 : (tess->cacheCount > 3) ? GL_TRIANGLE_FAN
483 : GL_TRIANGLES );
485 CALL_VERTEX_OR_VERTEX_DATA( v0->data );
486 if( sign > 0 ) {
487 for( vc = v0+1; vc < vn; ++vc ) {
488 CALL_VERTEX_OR_VERTEX_DATA( vc->data );
490 } else {
491 for( vc = vn-1; vc > v0; --vc ) {
492 CALL_VERTEX_OR_VERTEX_DATA( vc->data );
495 CALL_END_OR_END_DATA();
496 return TRUE;