Geant4 Cross Reference |
1 // see license file for original license. 2 3 #ifndef tools_glutess_tessmono 4 #define tools_glutess_tessmono 5 6 /* __gl_meshTessellateMonoRegion( face ) tessellates a monotone region 7 * (what else would it do??) The region must consist of a single 8 * loop of half-edges (see mesh.h) oriented CCW. "Monotone" in this 9 * case means that any vertical line intersects the interior of the 10 * region in a single interval. 11 * 12 * Tessellation consists of adding interior edges (actually pairs of 13 * half-edges), to split the region into non-overlapping triangles. 14 * 15 * __gl_meshTessellateInterior( mesh ) tessellates each region of 16 * the mesh which is marked "inside" the polygon. Each such region 17 * must be monotone. 18 * 19 * __gl_meshDiscardExterior( mesh ) zaps (ie. sets to NULL) all faces 20 * which are not marked "inside" the polygon. Since further mesh operations 21 * on NULL faces are not allowed, the main purpose is to clean up the 22 * mesh so that exterior loops are not represented in the data structure. 23 * 24 * __gl_meshSetWindingNumber( mesh, value, keepOnlyBoundary ) resets the 25 * winding numbers on all edges so that regions marked "inside" the 26 * polygon have a winding number of "value", and regions outside 27 * have a winding number of 0. 28 * 29 * If keepOnlyBoundary is TOOLS_GLU_TRUE, it also deletes all edges which do not 30 * separate an interior region from an exterior one. 31 */ 32 33 //int __gl_meshTessellateMonoRegion( GLUface *face ); 34 //int __gl_meshTessellateInterior( GLUmesh *mesh ); 35 //void __gl_meshDiscardExterior( GLUmesh *mesh ); 36 //int __gl_meshSetWindingNumber( GLUmesh *mesh, int value, 37 // GLUboolean keepOnlyBoundary ); 38 39 //////////////////////////////////////////////////////// 40 /// inlined C code : /////////////////////////////////// 41 //////////////////////////////////////////////////////// 42 #include "geom" 43 #include "mesh" 44 45 /* __gl_meshTessellateMonoRegion( face ) tessellates a monotone region 46 * (what else would it do??) The region must consist of a single 47 * loop of half-edges (see mesh.h) oriented CCW. "Monotone" in this 48 * case means that any vertical line intersects the interior of the 49 * region in a single interval. 50 * 51 * Tessellation consists of adding interior edges (actually pairs of 52 * half-edges), to split the region into non-overlapping triangles. 53 * 54 * The basic idea is explained in Preparata and Shamos (which I don''t 55 * have handy right now), although their implementation is more 56 * complicated than this one. The are two edge chains, an upper chain 57 * and a lower chain. We process all vertices from both chains in order, 58 * from right to left. 59 * 60 * The algorithm ensures that the following invariant holds after each 61 * vertex is processed: the untessellated region consists of two 62 * chains, where one chain (say the upper) is a single edge, and 63 * the other chain is concave. The left vertex of the single edge 64 * is always to the left of all vertices in the concave chain. 65 * 66 * Each step consists of adding the rightmost unprocessed vertex to one 67 * of the two chains, and forming a fan of triangles from the rightmost 68 * of two chain endpoints. Determining whether we can add each triangle 69 * to the fan is a simple orientation test. By making the fan as large 70 * as possible, we restore the invariant (check it yourself). 71 */ 72 inline int __gl_meshTessellateMonoRegion( GLUface *face ) 73 { 74 GLUhalfEdge *up, *lo; 75 76 /* All edges are oriented CCW around the boundary of the region. 77 * First, find the half-edge whose origin vertex is rightmost. 78 * Since the sweep goes from left to right, face->anEdge should 79 * be close to the edge we want. 80 */ 81 up = face->anEdge; 82 assert( up->Lnext != up && up->Lnext->Lnext != up ); 83 84 for( ; VertLeq( up->Dst, up->Org ); up = up->Lprev ) 85 ; 86 for( ; VertLeq( up->Org, up->Dst ); up = up->Lnext ) 87 ; 88 lo = up->Lprev; 89 90 while( up->Lnext != lo ) { 91 if( VertLeq( up->Dst, lo->Org )) { 92 /* up->Dst is on the left. It is safe to form triangles from lo->Org. 93 * The EdgeGoesLeft test guarantees progress even when some triangles 94 * are CW, given that the upper and lower chains are truly monotone. 95 */ 96 while( lo->Lnext != up && (EdgeGoesLeft( lo->Lnext ) 97 || EdgeSign( lo->Org, lo->Dst, lo->Lnext->Dst ) <= 0 )) { 98 GLUhalfEdge *tempHalfEdge= __gl_meshConnect( lo->Lnext, lo ); 99 if (tempHalfEdge == NULL) return 0; 100 lo = tempHalfEdge->Sym; 101 } 102 lo = lo->Lprev; 103 } else { 104 /* lo->Org is on the left. We can make CCW triangles from up->Dst. */ 105 while( lo->Lnext != up && (EdgeGoesRight( up->Lprev ) 106 || EdgeSign( up->Dst, up->Org, up->Lprev->Org ) >= 0 )) { 107 GLUhalfEdge *tempHalfEdge= __gl_meshConnect( up, up->Lprev ); 108 if (tempHalfEdge == NULL) return 0; 109 up = tempHalfEdge->Sym; 110 } 111 up = up->Lnext; 112 } 113 } 114 115 /* Now lo->Org == up->Dst == the leftmost vertex. The remaining region 116 * can be tessellated in a fan from this leftmost vertex. 117 */ 118 assert( lo->Lnext != up ); 119 while( lo->Lnext->Lnext != up ) { 120 GLUhalfEdge *tempHalfEdge= __gl_meshConnect( lo->Lnext, lo ); 121 if (tempHalfEdge == NULL) return 0; 122 lo = tempHalfEdge->Sym; 123 } 124 125 return 1; 126 } 127 128 129 /* __gl_meshTessellateInterior( mesh ) tessellates each region of 130 * the mesh which is marked "inside" the polygon. Each such region 131 * must be monotone. 132 */ 133 inline int __gl_meshTessellateInterior( GLUmesh *mesh ) 134 { 135 GLUface *f, *next; 136 137 /*LINTED*/ 138 for( f = mesh->fHead.next; f != &mesh->fHead; f = next ) { 139 /* Make sure we don''t try to tessellate the new triangles. */ 140 next = f->next; 141 if( f->inside ) { 142 if ( !__gl_meshTessellateMonoRegion( f ) ) return 0; 143 } 144 } 145 146 return 1; 147 } 148 149 150 /* __gl_meshDiscardExterior( mesh ) zaps (ie. sets to NULL) all faces 151 * which are not marked "inside" the polygon. Since further mesh operations 152 * on NULL faces are not allowed, the main purpose is to clean up the 153 * mesh so that exterior loops are not represented in the data structure. 154 */ 155 inline void __gl_meshDiscardExterior( GLUmesh *mesh ) 156 { 157 GLUface *f, *next; 158 159 /*LINTED*/ 160 for( f = mesh->fHead.next; f != &mesh->fHead; f = next ) { 161 /* Since f will be destroyed, save its next pointer. */ 162 next = f->next; 163 if( ! f->inside ) { 164 __gl_meshZapFace( f ); 165 } 166 } 167 } 168 169 //#define MARKED_FOR_DELETION 0x7fffffff 170 171 /* __gl_meshSetWindingNumber( mesh, value, keepOnlyBoundary ) resets the 172 * winding numbers on all edges so that regions marked "inside" the 173 * polygon have a winding number of "value", and regions outside 174 * have a winding number of 0. 175 * 176 * If keepOnlyBoundary is TOOLS_GLU_TRUE, it also deletes all edges which do not 177 * separate an interior region from an exterior one. 178 */ 179 inline int __gl_meshSetWindingNumber( GLUmesh *mesh, int value, 180 GLUboolean keepOnlyBoundary ) 181 { 182 GLUhalfEdge *e, *eNext; 183 184 for( e = mesh->eHead.next; e != &mesh->eHead; e = eNext ) { 185 eNext = e->next; 186 if( e->Rface->inside != e->Lface->inside ) { 187 188 /* This is a boundary edge (one side is interior, one is exterior). */ 189 e->winding = (e->Lface->inside) ? value : -value; 190 } else { 191 192 /* Both regions are interior, or both are exterior. */ 193 if( ! keepOnlyBoundary ) { 194 e->winding = 0; 195 } else { 196 if ( !__gl_meshDelete( e ) ) return 0; 197 } 198 } 199 } 200 return 1; 201 } 202 203 #endif