File indexing completed on 2024-04-21 14:46:25

 /*
 ** Author: Eric Veach, July 1994.
 **
 */
 
 #include "gluos.h"
 #include <assert.h>
 #include <stddef.h>
 #include "mesh.h"
 #include "tess.h"
 #include "render.h"
 
 #ifndef TRUE
 #define TRUE 1
 #endif
 #ifndef FALSE
 #define FALSE 0
 #endif
 
 /* This structure remembers the information we need about a primitive
  * to be able to render it later, once we have determined which
  * primitive is able to use the most triangles.
  */
 struct FaceCount
 {
     long size;           /* number of triangles used */
     GLUhalfEdge *eStart; /* edge where this primitive starts */
     void (*render)(GLUtesselator *, GLUhalfEdge *, long);
     /* routine to render this primitive */
 };
 
 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);
 
 /************************ Strips and Fans decomposition ******************/
 
 /* __gl_renderMesh( tess, mesh ) takes a mesh and breaks it into triangle
  * fans, strips, and separate triangles.  A substantial effort is made
  * to use as few rendering primitives as possible (ie. to make the fans
  * and strips as large as possible).
  *
  * The rendering output is provided as callbacks (see the api).
  */
 void __gl_renderMesh(GLUtesselator *tess, GLUmesh *mesh)
 {
     GLUface *f;
 
     /* Make a list of separate triangles so we can render them all at once */
     tess->lonelyTriList = NULL;
 
     for (f = mesh->fHead.next; f != &mesh->fHead; f = f->next)
     {
         f->marked = FALSE;
     }
     for (f = mesh->fHead.next; f != &mesh->fHead; f = f->next)
     {
         /* We examine all faces in an arbitrary order.  Whenever we find
      * an unprocessed face F, we output a group of faces including F
      * whose size is maximum.
      */
         if (f->inside && !f->marked)
         {
             RenderMaximumFaceGroup(tess, f);
             assert(f->marked);
         }
     }
     if (tess->lonelyTriList != NULL)
     {
         RenderLonelyTriangles(tess, tess->lonelyTriList);
         tess->lonelyTriList = NULL;
     }
 }
 
 static void RenderMaximumFaceGroup(GLUtesselator *tess, GLUface *fOrig)
 {
     /* We want to find the largest triangle fan or strip of unmarked faces
    * which includes the given face fOrig.  There are 3 possible fans
    * passing through fOrig (one centered at each vertex), and 3 possible
    * strips (one for each CCW permutation of the vertices).  Our strategy
    * is to try all of these, and take the primitive which uses the most
    * triangles (a greedy approach).
    */
     GLUhalfEdge *e = fOrig->anEdge;
     struct FaceCount max, newFace;
 
     max.size   = 1;
     max.eStart = e;
     max.render = &RenderTriangle;
 
     if (!tess->flagBoundary)
     {
         newFace = MaximumFan(e);
         if (newFace.size > max.size)
         {
             max = newFace;
         }
         newFace = MaximumFan(e->Lnext);
         if (newFace.size > max.size)
         {
             max = newFace;
         }
         newFace = MaximumFan(e->Lprev);
         if (newFace.size > max.size)
         {
             max = newFace;
         }
 
         newFace = MaximumStrip(e);
         if (newFace.size > max.size)
         {
             max = newFace;
         }
         newFace = MaximumStrip(e->Lnext);
         if (newFace.size > max.size)
         {
             max = newFace;
         }
         newFace = MaximumStrip(e->Lprev);
         if (newFace.size > max.size)
         {
             max = newFace;
         }
     }
     (*(max.render))(tess, max.eStart, max.size);
 }
 
 /* Macros which keep track of faces we have marked temporarily, and allow
  * us to backtrack when necessary.  With triangle fans, this is not
  * really necessary, since the only awkward case is a loop of triangles
  * around a single origin vertex.  However with strips the situation is
  * more complicated, and we need a general tracking method like the
  * one here.
  */
 #define Marked(f) (!(f)->inside || (f)->marked)
 
 #define AddToTrail(f, t) ((f)->trail = (t), (t) = (f), (f)->marked = TRUE)
 
 #define FreeTrail(t)                  \
     do                                \
     {                                 \
         while ((t) != NULL)           \
         {                             \
             (t)->marked = FALSE;      \
             t           = (t)->trail; \
         }                             \
     } while (0) /* absorb trailing semicolon */
 
 static struct FaceCount MaximumFan(GLUhalfEdge *eOrig)
 {
     /* eOrig->Lface is the face we want to render.  We want to find the size
    * of a maximal fan around eOrig->Org.  To do this we just walk around
    * the origin vertex as far as possible in both directions.
    */
     struct FaceCount newFace = { 0, NULL, &RenderFan };
     GLUface *trail           = NULL;
     GLUhalfEdge *e;
 
     for (e = eOrig; !Marked(e->Lface); e = e->Onext)
     {
         AddToTrail(e->Lface, trail);
         ++newFace.size;
     }
     for (e = eOrig; !Marked(e->Rface); e = e->Oprev)
     {
         AddToTrail(e->Rface, trail);
         ++newFace.size;
     }
     newFace.eStart = e;
     /*LINTED*/
     FreeTrail(trail);
     return newFace;
 }
 
 #define IsEven(n) (((n)&1) == 0)
 
 static struct FaceCount MaximumStrip(GLUhalfEdge *eOrig)
 {
     /* Here we are looking for a maximal strip that contains the vertices
    * eOrig->Org, eOrig->Dst, eOrig->Lnext->Dst (in that order or the
    * reverse, such that all triangles are oriented CCW).
    *
    * Again we walk forward and backward as far as possible.  However for
    * strips there is a twist: to get CCW orientations, there must be
    * an *even* number of triangles in the strip on one side of eOrig.
    * We walk the strip starting on a side with an even number of triangles;
    * if both side have an odd number, we are forced to shorten one side.
    */
     struct FaceCount newFace = { 0, NULL, &RenderStrip };
     long headSize = 0, tailSize = 0;
     GLUface *trail = NULL;
     GLUhalfEdge *e, *eTail, *eHead;
 
     for (e = eOrig; !Marked(e->Lface); ++tailSize, e = e->Onext)
     {
         AddToTrail(e->Lface, trail);
         ++tailSize;
         e = e->Dprev;
         if (Marked(e->Lface))
             break;
         AddToTrail(e->Lface, trail);
     }
     eTail = e;
 
     for (e = eOrig; !Marked(e->Rface); ++headSize, e = e->Dnext)
     {
         AddToTrail(e->Rface, trail);
         ++headSize;
         e = e->Oprev;
         if (Marked(e->Rface))
             break;
         AddToTrail(e->Rface, trail);
     }
     eHead = e;
 
     newFace.size = tailSize + headSize;
     if (IsEven(tailSize))
     {
         newFace.eStart = eTail->Sym;
     }
     else if (IsEven(headSize))
     {
         newFace.eStart = eHead;
     }
     else
     {
         /* Both sides have odd length, we must shorten one of them.  In fact,
      * we must start from eHead to guarantee inclusion of eOrig->Lface.
      */
         --newFace.size;
         newFace.eStart = eHead->Onext;
     }
     /*LINTED*/
     FreeTrail(trail);
     return newFace;
 }
 
 static void RenderTriangle(GLUtesselator *tess, GLUhalfEdge *e, long size)
 {
     /* Just add the triangle to a triangle list, so we can render all
    * the separate triangles at once.
    */
     assert(size == 1);
     AddToTrail(e->Lface, tess->lonelyTriList);
 }
 
 static void RenderLonelyTriangles(GLUtesselator *tess, GLUface *f)
 {
     /* Now we render all the separate triangles which could not be
    * grouped into a triangle fan or strip.
    */
     GLUhalfEdge *e;
     int newState;
     int edgeState = -1; /* force edge state output for first vertex */
 
     CALL_BEGIN_OR_BEGIN_DATA(GL_TRIANGLES);
 
     for (; f != NULL; f = f->trail)
     {
         /* Loop once for each edge (there will always be 3 edges) */
 
         e = f->anEdge;
         do
         {
             if (tess->flagBoundary)
             {
                 /* Set the "edge state" to TRUE just before we output the
      * first vertex of each edge on the polygon boundary.
      */
                 newState = !e->Rface->inside;
                 if (edgeState != newState)
                 {
                     edgeState = newState;
                     CALL_EDGE_FLAG_OR_EDGE_FLAG_DATA(edgeState);
                 }
             }
             CALL_VERTEX_OR_VERTEX_DATA(e->Org->data);
 
             e = e->Lnext;
         } while (e != f->anEdge);
     }
     CALL_END_OR_END_DATA();
 }
 
 static void RenderFan(GLUtesselator *tess, GLUhalfEdge *e, long size)
 {
     /* Render as many CCW triangles as possible in a fan starting from
    * edge "e".  The fan *should* contain exactly "size" triangles
    * (otherwise we've goofed up somewhere).
    */
     CALL_BEGIN_OR_BEGIN_DATA(GL_TRIANGLE_FAN);
     CALL_VERTEX_OR_VERTEX_DATA(e->Org->data);
     CALL_VERTEX_OR_VERTEX_DATA(e->Dst->data);
 
     while (!Marked(e->Lface))
     {
         e->Lface->marked = TRUE;
         --size;
         e = e->Onext;
         CALL_VERTEX_OR_VERTEX_DATA(e->Dst->data);
     }
 
     assert(size == 0);
     CALL_END_OR_END_DATA();
 }
 
 static void RenderStrip(GLUtesselator *tess, GLUhalfEdge *e, long size)
 {
     /* Render as many CCW triangles as possible in a strip starting from
    * edge "e".  The strip *should* contain exactly "size" triangles
    * (otherwise we've goofed up somewhere).
    */
     CALL_BEGIN_OR_BEGIN_DATA(GL_TRIANGLE_STRIP);
     CALL_VERTEX_OR_VERTEX_DATA(e->Org->data);
     CALL_VERTEX_OR_VERTEX_DATA(e->Dst->data);
 
     while (!Marked(e->Lface))
     {
         e->Lface->marked = TRUE;
         --size;
         e = e->Dprev;
         CALL_VERTEX_OR_VERTEX_DATA(e->Org->data);
         if (Marked(e->Lface))
             break;
 
         e->Lface->marked = TRUE;
         --size;
         e = e->Onext;
         CALL_VERTEX_OR_VERTEX_DATA(e->Dst->data);
     }
 
     assert(size == 0);
     CALL_END_OR_END_DATA();
 }
 
 /************************ Boundary contour decomposition ******************/
 
 /* __gl_renderBoundary( tess, mesh ) takes a mesh, and outputs one
  * contour for each face marked "inside".  The rendering output is
  * provided as callbacks (see the api).
  */
 void __gl_renderBoundary(GLUtesselator *tess, GLUmesh *mesh)
 {
     GLUface *f;
     GLUhalfEdge *e;
 
     for (f = mesh->fHead.next; f != &mesh->fHead; f = f->next)
     {
         if (f->inside)
         {
             CALL_BEGIN_OR_BEGIN_DATA(GL_LINE_LOOP);
             e = f->anEdge;
             do
             {
                 CALL_VERTEX_OR_VERTEX_DATA(e->Org->data);
                 e = e->Lnext;
             } while (e != f->anEdge);
             CALL_END_OR_END_DATA();
         }
     }
 }
 
 /************************ Quick-and-dirty decomposition ******************/
 
 #define SIGN_INCONSISTENT 2
 
 static int ComputeNormal(GLUtesselator *tess, GLdouble norm[3], int check)
 /*
  * If check==FALSE, we compute the polygon normal and place it in norm[].
  * If check==TRUE, we check that each triangle in the fan from v0 has a
  * consistent orientation with respect to norm[].  If triangles are
  * consistently oriented CCW, return 1; if CW, return -1; if all triangles
  * are degenerate return 0; otherwise (no consistent orientation) return
  * SIGN_INCONSISTENT.
  */
 {
     CachedVertex *v0 = tess->cache;
     CachedVertex *vn = v0 + tess->cacheCount;
     CachedVertex *vc;
     GLdouble dot, xc, yc, zc, xp, yp, zp, n[3];
     int sign = 0;
 
     /* Find the polygon normal.  It is important to get a reasonable
    * normal even when the polygon is self-intersecting (eg. a bowtie).
    * Otherwise, the computed normal could be very tiny, but perpendicular
    * to the true plane of the polygon due to numerical noise.  Then all
    * the triangles would appear to be degenerate and we would incorrectly
    * decompose the polygon as a fan (or simply not render it at all).
    *
    * We use a sum-of-triangles normal algorithm rather than the more
    * efficient sum-of-trapezoids method (used in CheckOrientation()
    * in normal.c).  This lets us explicitly reverse the signed area
    * of some triangles to get a reasonable normal in the self-intersecting
    * case.
    */
     if (!check)
     {
         norm[0] = norm[1] = norm[2] = 0.0;
     }
 
     vc = v0 + 1;
     xc = vc->coords[0] - v0->coords[0];
     yc = vc->coords[1] - v0->coords[1];
     zc = vc->coords[2] - v0->coords[2];
     while (++vc < vn)
     {
         xp = xc;
         yp = yc;
         zp = zc;
         xc = vc->coords[0] - v0->coords[0];
         yc = vc->coords[1] - v0->coords[1];
         zc = vc->coords[2] - v0->coords[2];
 
         /* Compute (vp - v0) cross (vc - v0) */
         n[0] = yp * zc - zp * yc;
         n[1] = zp * xc - xp * zc;
         n[2] = xp * yc - yp * xc;
 
         dot = n[0] * norm[0] + n[1] * norm[1] + n[2] * norm[2];
         if (!check)
         {
             /* Reverse the contribution of back-facing triangles to get
        * a reasonable normal for self-intersecting polygons (see above)
        */
             if (dot >= 0)
             {
                 norm[0] += n[0];
                 norm[1] += n[1];
                 norm[2] += n[2];
             }
             else
             {
                 norm[0] -= n[0];
                 norm[1] -= n[1];
                 norm[2] -= n[2];
             }
         }
         else if (dot != 0)
         {
             /* Check the new orientation for consistency with previous triangles */
             if (dot > 0)
             {
                 if (sign < 0)
                     return SIGN_INCONSISTENT;
                 sign = 1;
             }
             else
             {
                 if (sign > 0)
                     return SIGN_INCONSISTENT;
                 sign = -1;
             }
         }
     }
     return sign;
 }
 
 /* __gl_renderCache( tess ) takes a single contour and tries to render it
  * as a triangle fan.  This handles convex polygons, as well as some
  * non-convex polygons if we get lucky.
  *
  * Returns TRUE if the polygon was successfully rendered.  The rendering
  * output is provided as callbacks (see the api).
  */
 GLboolean __gl_renderCache(GLUtesselator *tess)
 {
     CachedVertex *v0 = tess->cache;
     CachedVertex *vn = v0 + tess->cacheCount;
     CachedVertex *vc;
     GLdouble norm[3];
     int sign;
 
     if (tess->cacheCount < 3)
     {
         /* Degenerate contour -- no output */
         return TRUE;
     }
 
     norm[0] = tess->normal[0];
     norm[1] = tess->normal[1];
     norm[2] = tess->normal[2];
     if (norm[0] == 0 && norm[1] == 0 && norm[2] == 0)
     {
         ComputeNormal(tess, norm, FALSE);
     }
 
     sign = ComputeNormal(tess, norm, TRUE);
     if (sign == SIGN_INCONSISTENT)
     {
         /* Fan triangles did not have a consistent orientation */
         return FALSE;
     }
     if (sign == 0)
     {
         /* All triangles were degenerate */
         return TRUE;
     }
 
     /* Make sure we do the right thing for each winding rule */
     switch (tess->windingRule)
     {
         case GLU_TESS_WINDING_ODD:
         case GLU_TESS_WINDING_NONZERO:
             break;
         case GLU_TESS_WINDING_POSITIVE:
             if (sign < 0)
                 return TRUE;
             break;
         case GLU_TESS_WINDING_NEGATIVE:
             if (sign > 0)
                 return TRUE;
             break;
         case GLU_TESS_WINDING_ABS_GEQ_TWO:
             return TRUE;
     }
 
     CALL_BEGIN_OR_BEGIN_DATA(tess->boundaryOnly ? GL_LINE_LOOP :
                                                   (tess->cacheCount > 3) ? GL_TRIANGLE_FAN : GL_TRIANGLES);
 
     CALL_VERTEX_OR_VERTEX_DATA(v0->data);
     if (sign > 0)
     {
         for (vc = v0 + 1; vc < vn; ++vc)
         {
             CALL_VERTEX_OR_VERTEX_DATA(vc->data);
         }
     }
     else
     {
         for (vc = vn - 1; vc > v0; --vc)
         {
             CALL_VERTEX_OR_VERTEX_DATA(vc->data);
         }
     }
     CALL_END_OR_END_DATA();
     return TRUE;
 }