Geant4 Cross Reference |
1 // see license file for original license. 1 // see license file for original license. 2 2 3 #ifndef tools_glutess_render 3 #ifndef tools_glutess_render 4 #define tools_glutess_render 4 #define tools_glutess_render 5 5 6 #include "mesh" 6 #include "mesh" 7 7 8 /* __gl_renderMesh( tess, mesh ) takes a mesh 8 /* __gl_renderMesh( tess, mesh ) takes a mesh and breaks it into triangle 9 * fans, strips, and separate triangles. A su 9 * fans, strips, and separate triangles. A substantial effort is made 10 * to use as few rendering primitives as possi 10 * to use as few rendering primitives as possible (ie. to make the fans 11 * and strips as large as possible). 11 * and strips as large as possible). 12 * 12 * 13 * The rendering output is provided as callbac 13 * The rendering output is provided as callbacks (see the api). 14 */ 14 */ 15 //void __gl_renderMesh( GLUtesselator *tess, G 15 //void __gl_renderMesh( GLUtesselator *tess, GLUmesh *mesh ); 16 //void __gl_renderBoundary( GLUtesselator *tes 16 //void __gl_renderBoundary( GLUtesselator *tess, GLUmesh *mesh ); 17 17 18 //GLUboolean __gl_renderCache( GLUtesselator * 18 //GLUboolean __gl_renderCache( GLUtesselator *tess ); 19 19 20 ////////////////////////////////////////////// 20 //////////////////////////////////////////////////////// 21 /// inlined C code : ///////////////////////// 21 /// inlined C code : /////////////////////////////////// 22 ////////////////////////////////////////////// 22 //////////////////////////////////////////////////////// 23 23 24 #include "_tess" 24 #include "_tess" 25 25 26 /* This structure remembers the information we 26 /* This structure remembers the information we need about a primitive 27 * to be able to render it later, once we have 27 * to be able to render it later, once we have determined which 28 * primitive is able to use the most triangles 28 * primitive is able to use the most triangles. 29 */ 29 */ 30 struct FaceCount { 30 struct FaceCount { 31 long size; /* number of triangles used 31 long size; /* number of triangles used */ 32 GLUhalfEdge *eStart; /* edge where this pri 32 GLUhalfEdge *eStart; /* edge where this primitive starts */ 33 void (*render)(GLUtesselator *, GLUhalfEd 33 void (*render)(GLUtesselator *, GLUhalfEdge *, long); 34 /* routine to 34 /* routine to render this primitive */ 35 }; 35 }; 36 36 37 inline/*static*/ struct FaceCount static_Maxim 37 inline/*static*/ struct FaceCount static_MaximumFan( GLUhalfEdge *eOrig ); 38 inline/*static*/ struct FaceCount static_Maxim 38 inline/*static*/ struct FaceCount static_MaximumStrip( GLUhalfEdge *eOrig ); 39 39 40 inline/*static*/ void static_RenderFan( GLUtes 40 inline/*static*/ void static_RenderFan( GLUtesselator *tess, GLUhalfEdge *eStart, long size ); 41 inline/*static*/ void static_RenderStrip( GLUt 41 inline/*static*/ void static_RenderStrip( GLUtesselator *tess, GLUhalfEdge *eStart, long size ); 42 inline/*static*/ void static_RenderTriangle( G 42 inline/*static*/ void static_RenderTriangle( GLUtesselator *tess, GLUhalfEdge *eStart, 43 long size ); 43 long size ); 44 44 45 inline/*static*/ void static_RenderMaximumFace 45 inline/*static*/ void static_RenderMaximumFaceGroup( GLUtesselator *tess, GLUface *fOrig ); 46 inline/*static*/ void static_RenderLonelyTrian 46 inline/*static*/ void static_RenderLonelyTriangles( GLUtesselator *tess, GLUface *head ); 47 47 48 48 49 49 50 /************************ Strips and Fans deco 50 /************************ Strips and Fans decomposition ******************/ 51 51 52 /* __gl_renderMesh( tess, mesh ) takes a mesh 52 /* __gl_renderMesh( tess, mesh ) takes a mesh and breaks it into triangle 53 * fans, strips, and separate triangles. A su 53 * fans, strips, and separate triangles. A substantial effort is made 54 * to use as few rendering primitives as possi 54 * to use as few rendering primitives as possible (ie. to make the fans 55 * and strips as large as possible). 55 * and strips as large as possible). 56 * 56 * 57 * The rendering output is provided as callbac 57 * The rendering output is provided as callbacks (see the api). 58 */ 58 */ 59 inline void __gl_renderMesh( GLUtesselator *te 59 inline void __gl_renderMesh( GLUtesselator *tess, GLUmesh *mesh ) 60 { 60 { 61 GLUface *f; 61 GLUface *f; 62 62 63 /* Make a list of separate triangles so we c 63 /* Make a list of separate triangles so we can render them all at once */ 64 tess->lonelyTriList = NULL; 64 tess->lonelyTriList = NULL; 65 65 66 for( f = mesh->fHead.next; f != &mesh->fHead 66 for( f = mesh->fHead.next; f != &mesh->fHead; f = f->next ) { 67 f->marked = TOOLS_GLU_FALSE; 67 f->marked = TOOLS_GLU_FALSE; 68 } 68 } 69 for( f = mesh->fHead.next; f != &mesh->fHead 69 for( f = mesh->fHead.next; f != &mesh->fHead; f = f->next ) { 70 70 71 /* We examine all faces in an arbitrary or 71 /* We examine all faces in an arbitrary order. Whenever we find 72 * an unprocessed face F, we output a grou 72 * an unprocessed face F, we output a group of faces including F 73 * whose size is maximum. 73 * whose size is maximum. 74 */ 74 */ 75 if( f->inside && ! f->marked ) { 75 if( f->inside && ! f->marked ) { 76 static_RenderMaximumFaceGroup( tess, f ) 76 static_RenderMaximumFaceGroup( tess, f ); 77 assert( f->marked ); 77 assert( f->marked ); 78 } 78 } 79 } 79 } 80 if( tess->lonelyTriList != NULL ) { 80 if( tess->lonelyTriList != NULL ) { 81 static_RenderLonelyTriangles( tess, tess-> 81 static_RenderLonelyTriangles( tess, tess->lonelyTriList ); 82 tess->lonelyTriList = NULL; 82 tess->lonelyTriList = NULL; 83 } 83 } 84 } 84 } 85 85 86 86 87 inline/*static*/ void static_RenderMaximumFace 87 inline/*static*/ void static_RenderMaximumFaceGroup( GLUtesselator *tess, GLUface *fOrig ) 88 { 88 { 89 /* We want to find the largest triangle fan 89 /* We want to find the largest triangle fan or strip of unmarked faces 90 * which includes the given face fOrig. The 90 * which includes the given face fOrig. There are 3 possible fans 91 * passing through fOrig (one centered at ea 91 * passing through fOrig (one centered at each vertex), and 3 possible 92 * strips (one for each CCW permutation of t 92 * strips (one for each CCW permutation of the vertices). Our strategy 93 * is to try all of these, and take the prim 93 * is to try all of these, and take the primitive which uses the most 94 * triangles (a greedy approach). 94 * triangles (a greedy approach). 95 */ 95 */ 96 GLUhalfEdge *e = fOrig->anEdge; 96 GLUhalfEdge *e = fOrig->anEdge; 97 struct FaceCount max, newFace; 97 struct FaceCount max, newFace; 98 98 99 max.size = 1; 99 max.size = 1; 100 max.eStart = e; 100 max.eStart = e; 101 max.render = &static_RenderTriangle; 101 max.render = &static_RenderTriangle; 102 102 103 if( ! tess->flagBoundary ) { 103 if( ! tess->flagBoundary ) { 104 newFace = static_MaximumFan( e ); if( newF 104 newFace = static_MaximumFan( e ); if( newFace.size > max.size ) { max = newFace; } 105 newFace = static_MaximumFan( e->Lnext ); i 105 newFace = static_MaximumFan( e->Lnext ); if( newFace.size > max.size ) { max = newFace; } 106 newFace = static_MaximumFan( e->Lprev ); i 106 newFace = static_MaximumFan( e->Lprev ); if( newFace.size > max.size ) { max = newFace; } 107 107 108 newFace = static_MaximumStrip( e ); if( ne 108 newFace = static_MaximumStrip( e ); if( newFace.size > max.size ) { max = newFace; } 109 newFace = static_MaximumStrip( e->Lnext ); 109 newFace = static_MaximumStrip( e->Lnext ); if( newFace.size > max.size ) { max = newFace; } 110 newFace = static_MaximumStrip( e->Lprev ); 110 newFace = static_MaximumStrip( e->Lprev ); if( newFace.size > max.size ) { max = newFace; } 111 } 111 } 112 (*(max.render))( tess, max.eStart, max.size 112 (*(max.render))( tess, max.eStart, max.size ); 113 } 113 } 114 114 115 115 116 /* Macros which keep track of faces we have ma 116 /* Macros which keep track of faces we have marked temporarily, and allow 117 * us to backtrack when necessary. With trian 117 * us to backtrack when necessary. With triangle fans, this is not 118 * really necessary, since the only awkward ca 118 * really necessary, since the only awkward case is a loop of triangles 119 * around a single origin vertex. However wit 119 * around a single origin vertex. However with strips the situation is 120 * more complicated, and we need a general tra 120 * more complicated, and we need a general tracking method like the 121 * one here. 121 * one here. 122 */ 122 */ 123 #define Marked(f) (! (f)->inside || (f)->marke 123 #define Marked(f) (! (f)->inside || (f)->marked) 124 124 125 #define AddToTrail(f,t) ((f)->trail = (t), (t) 125 #define AddToTrail(f,t) ((f)->trail = (t), (t) = (f), (f)->marked = TOOLS_GLU_TRUE) 126 126 127 //#define FreeTrail(t) if( 1 ) { while( (t) ! 127 //#define FreeTrail(t) if( 1 ) { while( (t) != NULL ) { (t)->marked = TOOLS_GLU_FALSE; t = (t)->trail; } } else 128 #define FreeTrail(t) do { while( (t) != NULL 128 #define FreeTrail(t) do { while( (t) != NULL ) { (t)->marked = TOOLS_GLU_FALSE; t = (t)->trail; } } while(false) 129 129 130 inline/*static*/ struct FaceCount static_Maxim 130 inline/*static*/ struct FaceCount static_MaximumFan( GLUhalfEdge *eOrig ) 131 { 131 { 132 /* eOrig->Lface is the face we want to rende 132 /* eOrig->Lface is the face we want to render. We want to find the size 133 * of a maximal fan around eOrig->Org. To d 133 * of a maximal fan around eOrig->Org. To do this we just walk around 134 * the origin vertex as far as possible in b 134 * the origin vertex as far as possible in both directions. 135 */ 135 */ 136 struct FaceCount newFace = { 0, NULL, &stati 136 struct FaceCount newFace = { 0, NULL, &static_RenderFan }; 137 GLUface *trail = NULL; 137 GLUface *trail = NULL; 138 GLUhalfEdge *e; 138 GLUhalfEdge *e; 139 139 140 for( e = eOrig; ! Marked( e->Lface ); e = e- 140 for( e = eOrig; ! Marked( e->Lface ); e = e->Onext ) { 141 AddToTrail( e->Lface, trail ); 141 AddToTrail( e->Lface, trail ); 142 ++newFace.size; 142 ++newFace.size; 143 } 143 } 144 for( e = eOrig; ! Marked( e->Rface ); e = e- 144 for( e = eOrig; ! Marked( e->Rface ); e = e->Oprev ) { 145 AddToTrail( e->Rface, trail ); 145 AddToTrail( e->Rface, trail ); 146 ++newFace.size; 146 ++newFace.size; 147 } 147 } 148 newFace.eStart = e; 148 newFace.eStart = e; 149 /*LINTED*/ 149 /*LINTED*/ 150 FreeTrail( trail ); 150 FreeTrail( trail ); 151 return newFace; 151 return newFace; 152 } 152 } 153 153 154 154 155 #define IsEven(n) (((n) & 1) == 0) 155 #define IsEven(n) (((n) & 1) == 0) 156 156 157 inline/*static*/ struct FaceCount static_Maxim 157 inline/*static*/ struct FaceCount static_MaximumStrip( GLUhalfEdge *eOrig ) 158 { 158 { 159 /* Here we are looking for a maximal strip t 159 /* Here we are looking for a maximal strip that contains the vertices 160 * eOrig->Org, eOrig->Dst, eOrig->Lnext->Dst 160 * eOrig->Org, eOrig->Dst, eOrig->Lnext->Dst (in that order or the 161 * reverse, such that all triangles are orie 161 * reverse, such that all triangles are oriented CCW). 162 * 162 * 163 * Again we walk forward and backward as far 163 * Again we walk forward and backward as far as possible. However for 164 * strips there is a twist: to get CCW orien 164 * strips there is a twist: to get CCW orientations, there must be 165 * an *even* number of triangles in the stri 165 * an *even* number of triangles in the strip on one side of eOrig. 166 * We walk the strip starting on a side with 166 * We walk the strip starting on a side with an even number of triangles; 167 * if both side have an odd number, we are f 167 * if both side have an odd number, we are forced to shorten one side. 168 */ 168 */ 169 struct FaceCount newFace = { 0, NULL, &stati 169 struct FaceCount newFace = { 0, NULL, &static_RenderStrip }; 170 long headSize = 0, tailSize = 0; 170 long headSize = 0, tailSize = 0; 171 GLUface *trail = NULL; 171 GLUface *trail = NULL; 172 GLUhalfEdge *e, *eTail, *eHead; 172 GLUhalfEdge *e, *eTail, *eHead; 173 173 174 for( e = eOrig; ! Marked( e->Lface ); ++tail 174 for( e = eOrig; ! Marked( e->Lface ); ++tailSize, e = e->Onext ) { 175 AddToTrail( e->Lface, trail ); 175 AddToTrail( e->Lface, trail ); 176 ++tailSize; 176 ++tailSize; 177 e = e->Dprev; 177 e = e->Dprev; 178 if( Marked( e->Lface )) break; 178 if( Marked( e->Lface )) break; 179 AddToTrail( e->Lface, trail ); 179 AddToTrail( e->Lface, trail ); 180 } 180 } 181 eTail = e; 181 eTail = e; 182 182 183 for( e = eOrig; ! Marked( e->Rface ); ++head 183 for( e = eOrig; ! Marked( e->Rface ); ++headSize, e = e->Dnext ) { 184 AddToTrail( e->Rface, trail ); 184 AddToTrail( e->Rface, trail ); 185 ++headSize; 185 ++headSize; 186 e = e->Oprev; 186 e = e->Oprev; 187 if( Marked( e->Rface )) break; 187 if( Marked( e->Rface )) break; 188 AddToTrail( e->Rface, trail ); 188 AddToTrail( e->Rface, trail ); 189 } 189 } 190 eHead = e; 190 eHead = e; 191 191 192 newFace.size = tailSize + headSize; 192 newFace.size = tailSize + headSize; 193 if( IsEven( tailSize )) { 193 if( IsEven( tailSize )) { 194 newFace.eStart = eTail->Sym; 194 newFace.eStart = eTail->Sym; 195 } else if( IsEven( headSize )) { 195 } else if( IsEven( headSize )) { 196 newFace.eStart = eHead; 196 newFace.eStart = eHead; 197 } else { 197 } else { 198 /* Both sides have odd length, we must sho 198 /* Both sides have odd length, we must shorten one of them. In fact, 199 * we must start from eHead to guarantee i 199 * we must start from eHead to guarantee inclusion of eOrig->Lface. 200 */ 200 */ 201 --newFace.size; 201 --newFace.size; 202 newFace.eStart = eHead->Onext; 202 newFace.eStart = eHead->Onext; 203 } 203 } 204 /*LINTED*/ 204 /*LINTED*/ 205 FreeTrail( trail ); 205 FreeTrail( trail ); 206 return newFace; 206 return newFace; 207 } 207 } 208 208 209 209 210 inline/*static*/ void static_RenderTriangle( G 210 inline/*static*/ void static_RenderTriangle( GLUtesselator *tess, GLUhalfEdge *e, long size ) 211 { 211 { 212 /* Just add the triangle to a triangle list, 212 /* Just add the triangle to a triangle list, so we can render all 213 * the separate triangles at once. 213 * the separate triangles at once. 214 */ 214 */ 215 assert( size == 1 ); 215 assert( size == 1 ); 216 AddToTrail( e->Lface, tess->lonelyTriList ); 216 AddToTrail( e->Lface, tess->lonelyTriList ); 217 (void)size; 217 (void)size; 218 } 218 } 219 219 220 220 221 inline/*static*/ void static_RenderLonelyTrian 221 inline/*static*/ void static_RenderLonelyTriangles( GLUtesselator *tess, GLUface *f ) 222 { 222 { 223 /* Now we render all the separate triangles 223 /* Now we render all the separate triangles which could not be 224 * grouped into a triangle fan or strip. 224 * grouped into a triangle fan or strip. 225 */ 225 */ 226 GLUhalfEdge *e; 226 GLUhalfEdge *e; 227 int newState; 227 int newState; 228 int edgeState = -1; /* force edge state outp 228 int edgeState = -1; /* force edge state output for first vertex */ 229 229 230 CALL_BEGIN_OR_BEGIN_DATA( GLU_TRIANGLES ); 230 CALL_BEGIN_OR_BEGIN_DATA( GLU_TRIANGLES ); 231 231 232 for( ; f != NULL; f = f->trail ) { 232 for( ; f != NULL; f = f->trail ) { 233 /* Loop once for each edge (there will alw 233 /* Loop once for each edge (there will always be 3 edges) */ 234 234 235 e = f->anEdge; 235 e = f->anEdge; 236 do { 236 do { 237 if( tess->flagBoundary ) { 237 if( tess->flagBoundary ) { 238 /* Set the "edge state" to TOOLS_GLU_TRUE ju 238 /* Set the "edge state" to TOOLS_GLU_TRUE just before we output the 239 * first vertex of each edge on the polygon 239 * first vertex of each edge on the polygon boundary. 240 */ 240 */ 241 newState = ! e->Rface->inside; 241 newState = ! e->Rface->inside; 242 if( edgeState != newState ) { 242 if( edgeState != newState ) { 243 edgeState = newState; 243 edgeState = newState; 244 CALL_EDGE_FLAG_OR_EDGE_FLAG_DATA( ed 244 CALL_EDGE_FLAG_OR_EDGE_FLAG_DATA( edgeState ); 245 } 245 } 246 } 246 } 247 CALL_VERTEX_OR_VERTEX_DATA( e->Org->data 247 CALL_VERTEX_OR_VERTEX_DATA( e->Org->data ); 248 248 249 e = e->Lnext; 249 e = e->Lnext; 250 } while( e != f->anEdge ); 250 } while( e != f->anEdge ); 251 } 251 } 252 CALL_END_OR_END_DATA(); 252 CALL_END_OR_END_DATA(); 253 } 253 } 254 254 255 255 256 inline/*static*/ void static_RenderFan( GLUtes 256 inline/*static*/ void static_RenderFan( GLUtesselator *tess, GLUhalfEdge *e, long size ) 257 { 257 { 258 /* Render as many CCW triangles as possible 258 /* Render as many CCW triangles as possible in a fan starting from 259 * edge "e". The fan *should* contain exact 259 * edge "e". The fan *should* contain exactly "size" triangles 260 * (otherwise we've goofed up somewhere). 260 * (otherwise we've goofed up somewhere). 261 */ 261 */ 262 CALL_BEGIN_OR_BEGIN_DATA( GLU_TRIANGLE_FAN ) 262 CALL_BEGIN_OR_BEGIN_DATA( GLU_TRIANGLE_FAN ); 263 CALL_VERTEX_OR_VERTEX_DATA( e->Org->data ); 263 CALL_VERTEX_OR_VERTEX_DATA( e->Org->data ); 264 CALL_VERTEX_OR_VERTEX_DATA( e->Dst->data ); 264 CALL_VERTEX_OR_VERTEX_DATA( e->Dst->data ); 265 265 266 while( ! Marked( e->Lface )) { 266 while( ! Marked( e->Lface )) { 267 e->Lface->marked = TOOLS_GLU_TRUE; 267 e->Lface->marked = TOOLS_GLU_TRUE; 268 --size; 268 --size; 269 e = e->Onext; 269 e = e->Onext; 270 CALL_VERTEX_OR_VERTEX_DATA( e->Dst->data ) 270 CALL_VERTEX_OR_VERTEX_DATA( e->Dst->data ); 271 } 271 } 272 272 273 assert( size == 0 ); 273 assert( size == 0 ); 274 CALL_END_OR_END_DATA(); 274 CALL_END_OR_END_DATA(); 275 (void)size; << 276 } 275 } 277 276 278 277 279 inline/*static*/ void static_RenderStrip( GLUt 278 inline/*static*/ void static_RenderStrip( GLUtesselator *tess, GLUhalfEdge *e, long size ) 280 { 279 { 281 /* Render as many CCW triangles as possible 280 /* Render as many CCW triangles as possible in a strip starting from 282 * edge "e". The strip *should* contain exa 281 * edge "e". The strip *should* contain exactly "size" triangles 283 * (otherwise we've goofed up somewhere). 282 * (otherwise we've goofed up somewhere). 284 */ 283 */ 285 CALL_BEGIN_OR_BEGIN_DATA( GLU_TRIANGLE_STRIP 284 CALL_BEGIN_OR_BEGIN_DATA( GLU_TRIANGLE_STRIP ); 286 CALL_VERTEX_OR_VERTEX_DATA( e->Org->data ); 285 CALL_VERTEX_OR_VERTEX_DATA( e->Org->data ); 287 CALL_VERTEX_OR_VERTEX_DATA( e->Dst->data ); 286 CALL_VERTEX_OR_VERTEX_DATA( e->Dst->data ); 288 287 289 while( ! Marked( e->Lface )) { 288 while( ! Marked( e->Lface )) { 290 e->Lface->marked = TOOLS_GLU_TRUE; 289 e->Lface->marked = TOOLS_GLU_TRUE; 291 --size; 290 --size; 292 e = e->Dprev; 291 e = e->Dprev; 293 CALL_VERTEX_OR_VERTEX_DATA( e->Org->data ) 292 CALL_VERTEX_OR_VERTEX_DATA( e->Org->data ); 294 if( Marked( e->Lface )) break; 293 if( Marked( e->Lface )) break; 295 294 296 e->Lface->marked = TOOLS_GLU_TRUE; 295 e->Lface->marked = TOOLS_GLU_TRUE; 297 --size; 296 --size; 298 e = e->Onext; 297 e = e->Onext; 299 CALL_VERTEX_OR_VERTEX_DATA( e->Dst->data ) 298 CALL_VERTEX_OR_VERTEX_DATA( e->Dst->data ); 300 } 299 } 301 300 302 assert( size == 0 ); 301 assert( size == 0 ); 303 CALL_END_OR_END_DATA(); 302 CALL_END_OR_END_DATA(); 304 (void)size; << 305 } 303 } 306 304 307 305 308 /************************ Boundary contour dec 306 /************************ Boundary contour decomposition ******************/ 309 307 310 /* __gl_renderBoundary( tess, mesh ) takes a m 308 /* __gl_renderBoundary( tess, mesh ) takes a mesh, and outputs one 311 * contour for each face marked "inside". The 309 * contour for each face marked "inside". The rendering output is 312 * provided as callbacks (see the api). 310 * provided as callbacks (see the api). 313 */ 311 */ 314 inline void __gl_renderBoundary( GLUtesselator 312 inline void __gl_renderBoundary( GLUtesselator *tess, GLUmesh *mesh ) 315 { 313 { 316 GLUface *f; 314 GLUface *f; 317 GLUhalfEdge *e; 315 GLUhalfEdge *e; 318 316 319 for( f = mesh->fHead.next; f != &mesh->fHead 317 for( f = mesh->fHead.next; f != &mesh->fHead; f = f->next ) { 320 if( f->inside ) { 318 if( f->inside ) { 321 CALL_BEGIN_OR_BEGIN_DATA( GLU_LINE_LOOP 319 CALL_BEGIN_OR_BEGIN_DATA( GLU_LINE_LOOP ); 322 e = f->anEdge; 320 e = f->anEdge; 323 do { 321 do { 324 CALL_VERTEX_OR_VERTEX_DATA( e->Org->da 322 CALL_VERTEX_OR_VERTEX_DATA( e->Org->data ); 325 e = e->Lnext; 323 e = e->Lnext; 326 } while( e != f->anEdge ); 324 } while( e != f->anEdge ); 327 CALL_END_OR_END_DATA(); 325 CALL_END_OR_END_DATA(); 328 } 326 } 329 } 327 } 330 } 328 } 331 329 332 330 333 /************************ Quick-and-dirty deco 331 /************************ Quick-and-dirty decomposition ******************/ 334 332 335 //#define SIGN_INCONSISTENT 2 333 //#define SIGN_INCONSISTENT 2 336 inline int SIGN_INCONSISTENT() { 334 inline int SIGN_INCONSISTENT() { 337 static const int s_value = 2; 335 static const int s_value = 2; 338 return s_value; 336 return s_value; 339 } 337 } 340 338 341 inline/*static*/ int static_ComputeNormal( GLU 339 inline/*static*/ int static_ComputeNormal( GLUtesselator *tess, GLUdouble norm[3], int check ) 342 /* 340 /* 343 * If check==TOOLS_GLU_FALSE, we compute the p 341 * If check==TOOLS_GLU_FALSE, we compute the polygon normal and place it in norm[]. 344 * If check==TOOLS_GLU_TRUE, we check that eac 342 * If check==TOOLS_GLU_TRUE, we check that each triangle in the fan from v0 has a 345 * consistent orientation with respect to norm 343 * consistent orientation with respect to norm[]. If triangles are 346 * consistently oriented CCW, return 1; if CW, 344 * consistently oriented CCW, return 1; if CW, return -1; if all triangles 347 * are degenerate return 0; otherwise (no cons 345 * are degenerate return 0; otherwise (no consistent orientation) return 348 * SIGN_INCONSISTENT. 346 * SIGN_INCONSISTENT. 349 */ 347 */ 350 { 348 { 351 CachedVertex *v0 = tess->cache; 349 CachedVertex *v0 = tess->cache; 352 CachedVertex *vn = v0 + tess->cacheCount; 350 CachedVertex *vn = v0 + tess->cacheCount; 353 CachedVertex *vc; 351 CachedVertex *vc; 354 GLUdouble dot, xc, yc, zc, xp, yp, zp, n[3]; 352 GLUdouble dot, xc, yc, zc, xp, yp, zp, n[3]; 355 int sign = 0; 353 int sign = 0; 356 354 357 /* Find the polygon normal. It is important 355 /* Find the polygon normal. It is important to get a reasonable 358 * normal even when the polygon is self-inte 356 * normal even when the polygon is self-intersecting (eg. a bowtie). 359 * Otherwise, the computed normal could be v 357 * Otherwise, the computed normal could be very tiny, but perpendicular 360 * to the true plane of the polygon due to n 358 * to the true plane of the polygon due to numerical noise. Then all 361 * the triangles would appear to be degenera 359 * the triangles would appear to be degenerate and we would incorrectly 362 * decompose the polygon as a fan (or simply 360 * decompose the polygon as a fan (or simply not render it at all). 363 * 361 * 364 * We use a sum-of-triangles normal algorith 362 * We use a sum-of-triangles normal algorithm rather than the more 365 * efficient sum-of-trapezoids method (used 363 * efficient sum-of-trapezoids method (used in CheckOrientation() 366 * in normal.c). This lets us explicitly re 364 * in normal.c). This lets us explicitly reverse the signed area 367 * of some triangles to get a reasonable nor 365 * of some triangles to get a reasonable normal in the self-intersecting 368 * case. 366 * case. 369 */ 367 */ 370 if( ! check ) { 368 if( ! check ) { 371 norm[0] = norm[1] = norm[2] = 0.0; 369 norm[0] = norm[1] = norm[2] = 0.0; 372 } 370 } 373 371 374 vc = v0 + 1; 372 vc = v0 + 1; 375 xc = vc->coords[0] - v0->coords[0]; 373 xc = vc->coords[0] - v0->coords[0]; 376 yc = vc->coords[1] - v0->coords[1]; 374 yc = vc->coords[1] - v0->coords[1]; 377 zc = vc->coords[2] - v0->coords[2]; 375 zc = vc->coords[2] - v0->coords[2]; 378 while( ++vc < vn ) { 376 while( ++vc < vn ) { 379 xp = xc; yp = yc; zp = zc; 377 xp = xc; yp = yc; zp = zc; 380 xc = vc->coords[0] - v0->coords[0]; 378 xc = vc->coords[0] - v0->coords[0]; 381 yc = vc->coords[1] - v0->coords[1]; 379 yc = vc->coords[1] - v0->coords[1]; 382 zc = vc->coords[2] - v0->coords[2]; 380 zc = vc->coords[2] - v0->coords[2]; 383 381 384 /* Compute (vp - v0) cross (vc - v0) */ 382 /* Compute (vp - v0) cross (vc - v0) */ 385 n[0] = yp*zc - zp*yc; 383 n[0] = yp*zc - zp*yc; 386 n[1] = zp*xc - xp*zc; 384 n[1] = zp*xc - xp*zc; 387 n[2] = xp*yc - yp*xc; 385 n[2] = xp*yc - yp*xc; 388 386 389 dot = n[0]*norm[0] + n[1]*norm[1] + n[2]*n 387 dot = n[0]*norm[0] + n[1]*norm[1] + n[2]*norm[2]; 390 if( ! check ) { 388 if( ! check ) { 391 /* Reverse the contribution of back-faci 389 /* Reverse the contribution of back-facing triangles to get 392 * a reasonable normal for self-intersec 390 * a reasonable normal for self-intersecting polygons (see above) 393 */ 391 */ 394 if( dot >= 0 ) { 392 if( dot >= 0 ) { 395 norm[0] += n[0]; norm[1] += n[1]; norm[2] += 393 norm[0] += n[0]; norm[1] += n[1]; norm[2] += n[2]; 396 } else { 394 } else { 397 norm[0] -= n[0]; norm[1] -= n[1]; norm[2] -= 395 norm[0] -= n[0]; norm[1] -= n[1]; norm[2] -= n[2]; 398 } 396 } 399 } else if( dot != 0 ) { 397 } else if( dot != 0 ) { 400 /* Check the new orientation for consist 398 /* Check the new orientation for consistency with previous triangles */ 401 if( dot > 0 ) { 399 if( dot > 0 ) { 402 if( sign < 0 ) return SIGN_INCONSISTENT(); 400 if( sign < 0 ) return SIGN_INCONSISTENT(); 403 sign = 1; 401 sign = 1; 404 } else { 402 } else { 405 if( sign > 0 ) return SIGN_INCONSISTENT(); 403 if( sign > 0 ) return SIGN_INCONSISTENT(); 406 sign = -1; 404 sign = -1; 407 } 405 } 408 } 406 } 409 } 407 } 410 return sign; 408 return sign; 411 } 409 } 412 410 413 /* __gl_renderCache( tess ) takes a single con 411 /* __gl_renderCache( tess ) takes a single contour and tries to render it 414 * as a triangle fan. This handles convex pol 412 * as a triangle fan. This handles convex polygons, as well as some 415 * non-convex polygons if we get lucky. 413 * non-convex polygons if we get lucky. 416 * 414 * 417 * Returns TOOLS_GLU_TRUE if the polygon was s 415 * Returns TOOLS_GLU_TRUE if the polygon was successfully rendered. The rendering 418 * output is provided as callbacks (see the ap 416 * output is provided as callbacks (see the api). 419 */ 417 */ 420 inline GLUboolean __gl_renderCache( GLUtessela 418 inline GLUboolean __gl_renderCache( GLUtesselator *tess ) 421 { 419 { 422 CachedVertex *v0 = tess->cache; 420 CachedVertex *v0 = tess->cache; 423 CachedVertex *vn = v0 + tess->cacheCount; 421 CachedVertex *vn = v0 + tess->cacheCount; 424 CachedVertex *vc; 422 CachedVertex *vc; 425 GLUdouble norm[3]; 423 GLUdouble norm[3]; 426 int sign; 424 int sign; 427 425 428 if( tess->cacheCount < 3 ) { 426 if( tess->cacheCount < 3 ) { 429 /* Degenerate contour -- no output */ 427 /* Degenerate contour -- no output */ 430 return TOOLS_GLU_TRUE; 428 return TOOLS_GLU_TRUE; 431 } 429 } 432 430 433 norm[0] = tess->normal[0]; 431 norm[0] = tess->normal[0]; 434 norm[1] = tess->normal[1]; 432 norm[1] = tess->normal[1]; 435 norm[2] = tess->normal[2]; 433 norm[2] = tess->normal[2]; 436 if( norm[0] == 0 && norm[1] == 0 && norm[2] 434 if( norm[0] == 0 && norm[1] == 0 && norm[2] == 0 ) { 437 static_ComputeNormal( tess, norm, TOOLS_GL 435 static_ComputeNormal( tess, norm, TOOLS_GLU_FALSE ); 438 } 436 } 439 437 440 sign = static_ComputeNormal( tess, norm, TOO 438 sign = static_ComputeNormal( tess, norm, TOOLS_GLU_TRUE ); 441 if( sign == SIGN_INCONSISTENT() ) { 439 if( sign == SIGN_INCONSISTENT() ) { 442 /* Fan triangles did not have a consistent 440 /* Fan triangles did not have a consistent orientation */ 443 return TOOLS_GLU_FALSE; 441 return TOOLS_GLU_FALSE; 444 } 442 } 445 if( sign == 0 ) { 443 if( sign == 0 ) { 446 /* All triangles were degenerate */ 444 /* All triangles were degenerate */ 447 return TOOLS_GLU_TRUE; 445 return TOOLS_GLU_TRUE; 448 } 446 } 449 447 450 /* Make sure we do the right thing for each 448 /* Make sure we do the right thing for each winding rule */ 451 switch( tess->windingRule ) { 449 switch( tess->windingRule ) { 452 case GLU_TESS_WINDING_ODD: 450 case GLU_TESS_WINDING_ODD: 453 case GLU_TESS_WINDING_NONZERO: 451 case GLU_TESS_WINDING_NONZERO: 454 break; 452 break; 455 case GLU_TESS_WINDING_POSITIVE: 453 case GLU_TESS_WINDING_POSITIVE: 456 if( sign < 0 ) return TOOLS_GLU_TRUE; 454 if( sign < 0 ) return TOOLS_GLU_TRUE; 457 break; 455 break; 458 case GLU_TESS_WINDING_NEGATIVE: 456 case GLU_TESS_WINDING_NEGATIVE: 459 if( sign > 0 ) return TOOLS_GLU_TRUE; 457 if( sign > 0 ) return TOOLS_GLU_TRUE; 460 break; 458 break; 461 case GLU_TESS_WINDING_ABS_GEQ_TWO: 459 case GLU_TESS_WINDING_ABS_GEQ_TWO: 462 return TOOLS_GLU_TRUE; 460 return TOOLS_GLU_TRUE; 463 } 461 } 464 462 465 CALL_BEGIN_OR_BEGIN_DATA( tess->boundaryOnly 463 CALL_BEGIN_OR_BEGIN_DATA( tess->boundaryOnly ? GLU_LINE_LOOP 466 : (tess->cacheCount > 3) ? GLU_TRIANGL 464 : (tess->cacheCount > 3) ? GLU_TRIANGLE_FAN 467 : GLU_TRIANGLES ); 465 : GLU_TRIANGLES ); 468 466 469 CALL_VERTEX_OR_VERTEX_DATA( v0->data ); 467 CALL_VERTEX_OR_VERTEX_DATA( v0->data ); 470 if( sign > 0 ) { 468 if( sign > 0 ) { 471 for( vc = v0+1; vc < vn; ++vc ) { 469 for( vc = v0+1; vc < vn; ++vc ) { 472 CALL_VERTEX_OR_VERTEX_DATA( vc->data ); 470 CALL_VERTEX_OR_VERTEX_DATA( vc->data ); 473 } 471 } 474 } else { 472 } else { 475 for( vc = vn-1; vc > v0; --vc ) { 473 for( vc = vn-1; vc > v0; --vc ) { 476 CALL_VERTEX_OR_VERTEX_DATA( vc->data ); 474 CALL_VERTEX_OR_VERTEX_DATA( vc->data ); 477 } 475 } 478 } 476 } 479 CALL_END_OR_END_DATA(); 477 CALL_END_OR_END_DATA(); 480 return TOOLS_GLU_TRUE; 478 return TOOLS_GLU_TRUE; 481 } 479 } 482 480 483 #endif 481 #endif