]> git.jsancho.org Git - lugaru.git/blob - Dependencies/GLU/render.c
Drop commented-out remains of MinMaxDistance
[lugaru.git] / Dependencies / GLU / 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  */
49 struct 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
56 static struct FaceCount MaximumFan( GLUhalfEdge *eOrig );
57 static struct FaceCount MaximumStrip( GLUhalfEdge *eOrig );
58
59 static void RenderFan( GLUtesselator *tess, GLUhalfEdge *eStart, long size );
60 static void RenderStrip( GLUtesselator *tess, GLUhalfEdge *eStart, long size );
61 static void RenderTriangle( GLUtesselator *tess, GLUhalfEdge *eStart,
62                             long size );
63
64 static void RenderMaximumFaceGroup( GLUtesselator *tess, GLUface *fOrig );
65 static 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  */
78 void __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
106 static 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
154 static 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
181 static 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
234 static 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
244 static 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
279 static 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
301 static 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  */
335 void __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
358 static 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  */
437 GLboolean __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 }