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 }