| 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