Warning, /include/Geant4/tools/glutess/tessmono is written in an unsupported language. File is not indexed.
0001 // see license file for original license.
0002
0003 #ifndef tools_glutess_tessmono
0004 #define tools_glutess_tessmono
0005
0006 /* __gl_meshTessellateMonoRegion( face ) tessellates a monotone region
0007 * (what else would it do??) The region must consist of a single
0008 * loop of half-edges (see mesh.h) oriented CCW. "Monotone" in this
0009 * case means that any vertical line intersects the interior of the
0010 * region in a single interval.
0011 *
0012 * Tessellation consists of adding interior edges (actually pairs of
0013 * half-edges), to split the region into non-overlapping triangles.
0014 *
0015 * __gl_meshTessellateInterior( mesh ) tessellates each region of
0016 * the mesh which is marked "inside" the polygon. Each such region
0017 * must be monotone.
0018 *
0019 * __gl_meshDiscardExterior( mesh ) zaps (ie. sets to NULL) all faces
0020 * which are not marked "inside" the polygon. Since further mesh operations
0021 * on NULL faces are not allowed, the main purpose is to clean up the
0022 * mesh so that exterior loops are not represented in the data structure.
0023 *
0024 * __gl_meshSetWindingNumber( mesh, value, keepOnlyBoundary ) resets the
0025 * winding numbers on all edges so that regions marked "inside" the
0026 * polygon have a winding number of "value", and regions outside
0027 * have a winding number of 0.
0028 *
0029 * If keepOnlyBoundary is TOOLS_GLU_TRUE, it also deletes all edges which do not
0030 * separate an interior region from an exterior one.
0031 */
0032
0033 //int __gl_meshTessellateMonoRegion( GLUface *face );
0034 //int __gl_meshTessellateInterior( GLUmesh *mesh );
0035 //void __gl_meshDiscardExterior( GLUmesh *mesh );
0036 //int __gl_meshSetWindingNumber( GLUmesh *mesh, int value,
0037 // GLUboolean keepOnlyBoundary );
0038
0039 ////////////////////////////////////////////////////////
0040 /// inlined C code : ///////////////////////////////////
0041 ////////////////////////////////////////////////////////
0042 #include "geom"
0043 #include "mesh"
0044
0045 /* __gl_meshTessellateMonoRegion( face ) tessellates a monotone region
0046 * (what else would it do??) The region must consist of a single
0047 * loop of half-edges (see mesh.h) oriented CCW. "Monotone" in this
0048 * case means that any vertical line intersects the interior of the
0049 * region in a single interval.
0050 *
0051 * Tessellation consists of adding interior edges (actually pairs of
0052 * half-edges), to split the region into non-overlapping triangles.
0053 *
0054 * The basic idea is explained in Preparata and Shamos (which I don''t
0055 * have handy right now), although their implementation is more
0056 * complicated than this one. The are two edge chains, an upper chain
0057 * and a lower chain. We process all vertices from both chains in order,
0058 * from right to left.
0059 *
0060 * The algorithm ensures that the following invariant holds after each
0061 * vertex is processed: the untessellated region consists of two
0062 * chains, where one chain (say the upper) is a single edge, and
0063 * the other chain is concave. The left vertex of the single edge
0064 * is always to the left of all vertices in the concave chain.
0065 *
0066 * Each step consists of adding the rightmost unprocessed vertex to one
0067 * of the two chains, and forming a fan of triangles from the rightmost
0068 * of two chain endpoints. Determining whether we can add each triangle
0069 * to the fan is a simple orientation test. By making the fan as large
0070 * as possible, we restore the invariant (check it yourself).
0071 */
0072 inline int __gl_meshTessellateMonoRegion( GLUface *face )
0073 {
0074 GLUhalfEdge *up, *lo;
0075
0076 /* All edges are oriented CCW around the boundary of the region.
0077 * First, find the half-edge whose origin vertex is rightmost.
0078 * Since the sweep goes from left to right, face->anEdge should
0079 * be close to the edge we want.
0080 */
0081 up = face->anEdge;
0082 assert( up->Lnext != up && up->Lnext->Lnext != up );
0083
0084 for( ; VertLeq( up->Dst, up->Org ); up = up->Lprev )
0085 ;
0086 for( ; VertLeq( up->Org, up->Dst ); up = up->Lnext )
0087 ;
0088 lo = up->Lprev;
0089
0090 while( up->Lnext != lo ) {
0091 if( VertLeq( up->Dst, lo->Org )) {
0092 /* up->Dst is on the left. It is safe to form triangles from lo->Org.
0093 * The EdgeGoesLeft test guarantees progress even when some triangles
0094 * are CW, given that the upper and lower chains are truly monotone.
0095 */
0096 while( lo->Lnext != up && (EdgeGoesLeft( lo->Lnext )
0097 || EdgeSign( lo->Org, lo->Dst, lo->Lnext->Dst ) <= 0 )) {
0098 GLUhalfEdge *tempHalfEdge= __gl_meshConnect( lo->Lnext, lo );
0099 if (tempHalfEdge == NULL) return 0;
0100 lo = tempHalfEdge->Sym;
0101 }
0102 lo = lo->Lprev;
0103 } else {
0104 /* lo->Org is on the left. We can make CCW triangles from up->Dst. */
0105 while( lo->Lnext != up && (EdgeGoesRight( up->Lprev )
0106 || EdgeSign( up->Dst, up->Org, up->Lprev->Org ) >= 0 )) {
0107 GLUhalfEdge *tempHalfEdge= __gl_meshConnect( up, up->Lprev );
0108 if (tempHalfEdge == NULL) return 0;
0109 up = tempHalfEdge->Sym;
0110 }
0111 up = up->Lnext;
0112 }
0113 }
0114
0115 /* Now lo->Org == up->Dst == the leftmost vertex. The remaining region
0116 * can be tessellated in a fan from this leftmost vertex.
0117 */
0118 assert( lo->Lnext != up );
0119 while( lo->Lnext->Lnext != up ) {
0120 GLUhalfEdge *tempHalfEdge= __gl_meshConnect( lo->Lnext, lo );
0121 if (tempHalfEdge == NULL) return 0;
0122 lo = tempHalfEdge->Sym;
0123 }
0124
0125 return 1;
0126 }
0127
0128
0129 /* __gl_meshTessellateInterior( mesh ) tessellates each region of
0130 * the mesh which is marked "inside" the polygon. Each such region
0131 * must be monotone.
0132 */
0133 inline int __gl_meshTessellateInterior( GLUmesh *mesh )
0134 {
0135 GLUface *f, *next;
0136
0137 /*LINTED*/
0138 for( f = mesh->fHead.next; f != &mesh->fHead; f = next ) {
0139 /* Make sure we don''t try to tessellate the new triangles. */
0140 next = f->next;
0141 if( f->inside ) {
0142 if ( !__gl_meshTessellateMonoRegion( f ) ) return 0;
0143 }
0144 }
0145
0146 return 1;
0147 }
0148
0149
0150 /* __gl_meshDiscardExterior( mesh ) zaps (ie. sets to NULL) all faces
0151 * which are not marked "inside" the polygon. Since further mesh operations
0152 * on NULL faces are not allowed, the main purpose is to clean up the
0153 * mesh so that exterior loops are not represented in the data structure.
0154 */
0155 inline void __gl_meshDiscardExterior( GLUmesh *mesh )
0156 {
0157 GLUface *f, *next;
0158
0159 /*LINTED*/
0160 for( f = mesh->fHead.next; f != &mesh->fHead; f = next ) {
0161 /* Since f will be destroyed, save its next pointer. */
0162 next = f->next;
0163 if( ! f->inside ) {
0164 __gl_meshZapFace( f );
0165 }
0166 }
0167 }
0168
0169 //#define MARKED_FOR_DELETION 0x7fffffff
0170
0171 /* __gl_meshSetWindingNumber( mesh, value, keepOnlyBoundary ) resets the
0172 * winding numbers on all edges so that regions marked "inside" the
0173 * polygon have a winding number of "value", and regions outside
0174 * have a winding number of 0.
0175 *
0176 * If keepOnlyBoundary is TOOLS_GLU_TRUE, it also deletes all edges which do not
0177 * separate an interior region from an exterior one.
0178 */
0179 inline int __gl_meshSetWindingNumber( GLUmesh *mesh, int value,
0180 GLUboolean keepOnlyBoundary )
0181 {
0182 GLUhalfEdge *e, *eNext;
0183
0184 for( e = mesh->eHead.next; e != &mesh->eHead; e = eNext ) {
0185 eNext = e->next;
0186 if( e->Rface->inside != e->Lface->inside ) {
0187
0188 /* This is a boundary edge (one side is interior, one is exterior). */
0189 e->winding = (e->Lface->inside) ? value : -value;
0190 } else {
0191
0192 /* Both regions are interior, or both are exterior. */
0193 if( ! keepOnlyBoundary ) {
0194 e->winding = 0;
0195 } else {
0196 if ( !__gl_meshDelete( e ) ) return 0;
0197 }
0198 }
0199 }
0200 return 1;
0201 }
0202
0203 #endif
