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