File indexing completed on 2024-03-24 15:17:35

0001 /*
0002 ** Author: Eric Veach, July 1994.
0003 **
0004 */
0005 
0006 #include "gluos.h"
0007 #include <stdlib.h>
0008 #include "geom.h"
0009 #include "mesh.h"
0010 #include "tessmono.h"
0011 #include <assert.h>
0012 
0013 #define AddWinding(eDst, eSrc) (eDst->winding += eSrc->winding, eDst->Sym->winding += eSrc->Sym->winding)
0014 
0015 /* __gl_meshTessellateMonoRegion( face ) tessellates a monotone region
0016  * (what else would it do??)  The region must consist of a single
0017  * loop of half-edges (see mesh.h) oriented CCW.  "Monotone" in this
0018  * case means that any vertical line intersects the interior of the
0019  * region in a single interval.  
0020  *
0021  * Tessellation consists of adding interior edges (actually pairs of
0022  * half-edges), to split the region into non-overlapping triangles.
0023  *
0024  * The basic idea is explained in Preparata and Shamos (which I don''t
0025  * have handy right now), although their implementation is more
0026  * complicated than this one.  The are two edge chains, an upper chain
0027  * and a lower chain.  We process all vertices from both chains in order,
0028  * from right to left.
0029  *
0030  * The algorithm ensures that the following invariant holds after each
0031  * vertex is processed: the untessellated region consists of two
0032  * chains, where one chain (say the upper) is a single edge, and
0033  * the other chain is concave.  The left vertex of the single edge
0034  * is always to the left of all vertices in the concave chain.
0035  *
0036  * Each step consists of adding the rightmost unprocessed vertex to one
0037  * of the two chains, and forming a fan of triangles from the rightmost
0038  * of two chain endpoints.  Determining whether we can add each triangle
0039  * to the fan is a simple orientation test.  By making the fan as large
0040  * as possible, we restore the invariant (check it yourself).
0041  */
0042 int __gl_meshTessellateMonoRegion(GLUface *face)
0043 {
0044     GLUhalfEdge *up, *lo;
0045 
0046     /* All edges are oriented CCW around the boundary of the region.
0047    * First, find the half-edge whose origin vertex is rightmost.
0048    * Since the sweep goes from left to right, face->anEdge should
0049    * be close to the edge we want.
0050    */
0051     up = face->anEdge;
0052     assert(up->Lnext != up && up->Lnext->Lnext != up);
0053 
0054     for (; VertLeq(up->Dst, up->Org); up = up->Lprev)
0055         ;
0056     for (; VertLeq(up->Org, up->Dst); up = up->Lnext)
0057         ;
0058     lo = up->Lprev;
0059 
0060     while (up->Lnext != lo)
0061     {
0062         if (VertLeq(up->Dst, lo->Org))
0063         {
0064             /* up->Dst is on the left.  It is safe to form triangles from lo->Org.
0065        * The EdgeGoesLeft test guarantees progress even when some triangles
0066        * are CW, given that the upper and lower chains are truly monotone.
0067        */
0068             while (lo->Lnext != up && (EdgeGoesLeft(lo->Lnext) || EdgeSign(lo->Org, lo->Dst, lo->Lnext->Dst) <= 0))
0069             {
0070                 GLUhalfEdge *tempHalfEdge = __gl_meshConnect(lo->Lnext, lo);
0071                 if (tempHalfEdge == NULL)
0072                     return 0;
0073                 lo = tempHalfEdge->Sym;
0074             }
0075             lo = lo->Lprev;
0076         }
0077         else
0078         {
0079             /* lo->Org is on the left.  We can make CCW triangles from up->Dst. */
0080             while (lo->Lnext != up && (EdgeGoesRight(up->Lprev) || EdgeSign(up->Dst, up->Org, up->Lprev->Org) >= 0))
0081             {
0082                 GLUhalfEdge *tempHalfEdge = __gl_meshConnect(up, up->Lprev);
0083                 if (tempHalfEdge == NULL)
0084                     return 0;
0085                 up = tempHalfEdge->Sym;
0086             }
0087             up = up->Lnext;
0088         }
0089     }
0090 
0091     /* Now lo->Org == up->Dst == the leftmost vertex.  The remaining region
0092    * can be tessellated in a fan from this leftmost vertex.
0093    */
0094     assert(lo->Lnext != up);
0095     while (lo->Lnext->Lnext != up)
0096     {
0097         GLUhalfEdge *tempHalfEdge = __gl_meshConnect(lo->Lnext, lo);
0098         if (tempHalfEdge == NULL)
0099             return 0;
0100         lo = tempHalfEdge->Sym;
0101     }
0102 
0103     return 1;
0104 }
0105 
0106 /* __gl_meshTessellateInterior( mesh ) tessellates each region of
0107  * the mesh which is marked "inside" the polygon.  Each such region
0108  * must be monotone.
0109  */
0110 int __gl_meshTessellateInterior(GLUmesh *mesh)
0111 {
0112     GLUface *f, *next;
0113 
0114     /*LINTED*/
0115     for (f = mesh->fHead.next; f != &mesh->fHead; f = next)
0116     {
0117         /* Make sure we don''t try to tessellate the new triangles. */
0118         next = f->next;
0119         if (f->inside)
0120         {
0121             if (!__gl_meshTessellateMonoRegion(f))
0122                 return 0;
0123         }
0124     }
0125 
0126     return 1;
0127 }
0128 
0129 /* __gl_meshDiscardExterior( mesh ) zaps (ie. sets to NULL) all faces
0130  * which are not marked "inside" the polygon.  Since further mesh operations
0131  * on NULL faces are not allowed, the main purpose is to clean up the
0132  * mesh so that exterior loops are not represented in the data structure.
0133  */
0134 void __gl_meshDiscardExterior(GLUmesh *mesh)
0135 {
0136     GLUface *f, *next;
0137 
0138     /*LINTED*/
0139     for (f = mesh->fHead.next; f != &mesh->fHead; f = next)
0140     {
0141         /* Since f will be destroyed, save its next pointer. */
0142         next = f->next;
0143         if (!f->inside)
0144         {
0145             __gl_meshZapFace(f);
0146         }
0147     }
0148 }
0149 
0150 #define MARKED_FOR_DELETION 0x7fffffff
0151 
0152 /* __gl_meshSetWindingNumber( mesh, value, keepOnlyBoundary ) resets the
0153  * winding numbers on all edges so that regions marked "inside" the
0154  * polygon have a winding number of "value", and regions outside
0155  * have a winding number of 0.
0156  *
0157  * If keepOnlyBoundary is TRUE, it also deletes all edges which do not
0158  * separate an interior region from an exterior one.
0159  */
0160 int __gl_meshSetWindingNumber(GLUmesh *mesh, int value, GLboolean keepOnlyBoundary)
0161 {
0162     GLUhalfEdge *e, *eNext;
0163 
0164     for (e = mesh->eHead.next; e != &mesh->eHead; e = eNext)
0165     {
0166         eNext = e->next;
0167         if (e->Rface->inside != e->Lface->inside)
0168         {
0169             /* This is a boundary edge (one side is interior, one is exterior). */
0170             e->winding = (e->Lface->inside) ? value : -value;
0171         }
0172         else
0173         {
0174             /* Both regions are interior, or both are exterior. */
0175             if (!keepOnlyBoundary)
0176             {
0177                 e->winding = 0;
0178             }
0179             else
0180             {
0181                 if (!__gl_meshDelete(e))
0182                     return 0;
0183             }
0184         }
0185     }
0186     return 1;
0187 }