| 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 ) tesse
7 * (what else would it do??) The region must
8 * loop of half-edges (see mesh.h) oriented CC
9 * case means that any vertical line intersect
10 * region in a single interval.
11 *
12 * Tessellation consists of adding interior ed
13 * half-edges), to split the region into non-o
14 *
15 * __gl_meshTessellateInterior( mesh ) tessell
16 * the mesh which is marked "inside" the polyg
17 * must be monotone.
18 *
19 * __gl_meshDiscardExterior( mesh ) zaps (ie.
20 * which are not marked "inside" the polygon.
21 * on NULL faces are not allowed, the main pur
22 * mesh so that exterior loops are not represe
23 *
24 * __gl_meshSetWindingNumber( mesh, value, kee
25 * winding numbers on all edges so that region
26 * polygon have a winding number of "value", a
27 * have a winding number of 0.
28 *
29 * If keepOnlyBoundary is TOOLS_GLU_TRUE, it a
30 * separate an interior region from an exterio
31 */
32
33 //int __gl_meshTessellateMonoRegion( GLUface *
34 //int __gl_meshTessellateInterior( GLUmesh *me
35 //void __gl_meshDiscardExterior( GLUmesh *mesh
36 //int __gl_meshSetWindingNumber( GLUmesh *mesh
37 // GLUboolean keepOnlyBoundary );
38
39 //////////////////////////////////////////////
40 /// inlined C code : /////////////////////////
41 //////////////////////////////////////////////
42 #include "geom"
43 #include "mesh"
44
45 /* __gl_meshTessellateMonoRegion( face ) tesse
46 * (what else would it do??) The region must
47 * loop of half-edges (see mesh.h) oriented CC
48 * case means that any vertical line intersect
49 * region in a single interval.
50 *
51 * Tessellation consists of adding interior ed
52 * half-edges), to split the region into non-o
53 *
54 * The basic idea is explained in Preparata an
55 * have handy right now), although their imple
56 * complicated than this one. The are two edg
57 * and a lower chain. We process all vertices
58 * from right to left.
59 *
60 * The algorithm ensures that the following in
61 * vertex is processed: the untessellated regi
62 * chains, where one chain (say the upper) is
63 * the other chain is concave. The left verte
64 * is always to the left of all vertices in th
65 *
66 * Each step consists of adding the rightmost
67 * of the two chains, and forming a fan of tri
68 * of two chain endpoints. Determining whethe
69 * to the fan is a simple orientation test. B
70 * as possible, we restore the invariant (chec
71 */
72 inline int __gl_meshTessellateMonoRegion( GLUf
73 {
74 GLUhalfEdge *up, *lo;
75
76 /* All edges are oriented CCW around the bou
77 * First, find the half-edge whose origin ve
78 * Since the sweep goes from left to right,
79 * be close to the edge we want.
80 */
81 up = face->anEdge;
82 assert( up->Lnext != up && up->Lnext->Lnext
83
84 for( ; VertLeq( up->Dst, up->Org ); up = up-
85 ;
86 for( ; VertLeq( up->Org, up->Dst ); up = up-
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 t
93 * The EdgeGoesLeft test guarantees prog
94 * are CW, given that the upper and lowe
95 */
96 while( lo->Lnext != up && (EdgeGoesLeft(
97 || EdgeSign( lo->Org, lo->Dst, lo->Lnex
98 GLUhalfEdge *tempHalfEdge= __gl_meshConnect(
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
105 while( lo->Lnext != up && (EdgeGoesRight
106 || EdgeSign( up->Dst, up->Org, up->Lpre
107 GLUhalfEdge *tempHalfEdge= __gl_meshConnect(
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 ve
116 * can be tessellated in a fan from this lef
117 */
118 assert( lo->Lnext != up );
119 while( lo->Lnext->Lnext != up ) {
120 GLUhalfEdge *tempHalfEdge= __gl_meshConnec
121 if (tempHalfEdge == NULL) return 0;
122 lo = tempHalfEdge->Sym;
123 }
124
125 return 1;
126 }
127
128
129 /* __gl_meshTessellateInterior( mesh ) tessell
130 * the mesh which is marked "inside" the polyg
131 * must be monotone.
132 */
133 inline int __gl_meshTessellateInterior( GLUmes
134 {
135 GLUface *f, *next;
136
137 /*LINTED*/
138 for( f = mesh->fHead.next; f != &mesh->fHead
139 /* Make sure we don''t try to tessellate t
140 next = f->next;
141 if( f->inside ) {
142 if ( !__gl_meshTessellateMonoRegion( f )
143 }
144 }
145
146 return 1;
147 }
148
149
150 /* __gl_meshDiscardExterior( mesh ) zaps (ie.
151 * which are not marked "inside" the polygon.
152 * on NULL faces are not allowed, the main pur
153 * mesh so that exterior loops are not represe
154 */
155 inline void __gl_meshDiscardExterior( GLUmesh
156 {
157 GLUface *f, *next;
158
159 /*LINTED*/
160 for( f = mesh->fHead.next; f != &mesh->fHead
161 /* Since f will be destroyed, save its nex
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, kee
172 * winding numbers on all edges so that region
173 * polygon have a winding number of "value", a
174 * have a winding number of 0.
175 *
176 * If keepOnlyBoundary is TOOLS_GLU_TRUE, it a
177 * separate an interior region from an exterio
178 */
179 inline int __gl_meshSetWindingNumber( GLUmesh
180 GLUboolean keepOnlyBoundary )
181 {
182 GLUhalfEdge *e, *eNext;
183
184 for( e = mesh->eHead.next; e != &mesh->eHead
185 eNext = e->next;
186 if( e->Rface->inside != e->Lface->inside )
187
188 /* This is a boundary edge (one side is
189 e->winding = (e->Lface->inside) ? value
190 } else {
191
192 /* Both regions are interior, or both ar
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