File indexing completed on 2024-03-24 15:17:34
0001 /* 0002 ** Author: Eric Veach, July 1994. 0003 ** 0004 */ 0005 0006 #include "gluos.h" 0007 #include <stddef.h> 0008 #include <assert.h> 0009 #include <setjmp.h> 0010 #include "memalloc.h" 0011 #include "tess.h" 0012 #include "mesh.h" 0013 #include "normal.h" 0014 #include "sweep.h" 0015 #include "tessmono.h" 0016 #include "render.h" 0017 0018 #define GLU_TESS_DEFAULT_TOLERANCE 0.0 0019 #define GLU_TESS_MESH 100112 /* void (*)(GLUmesh *mesh) */ 0020 0021 #ifndef TRUE 0022 #define TRUE 1 0023 #endif 0024 #ifndef FALSE 0025 #define FALSE 0 0026 #endif 0027 0028 /*ARGSUSED*/ static void GLAPIENTRY noBegin(GLenum type) 0029 { 0030 } 0031 /*ARGSUSED*/ static void GLAPIENTRY noEdgeFlag(GLboolean boundaryEdge) 0032 { 0033 } 0034 /*ARGSUSED*/ static void GLAPIENTRY noVertex(void *data) 0035 { 0036 } 0037 /*ARGSUSED*/ static void GLAPIENTRY noEnd(void) 0038 { 0039 } 0040 /*ARGSUSED*/ static void GLAPIENTRY noError(GLenum errnum) 0041 { 0042 } 0043 /*ARGSUSED*/ static void GLAPIENTRY noCombine(GLdouble coords[3], void *data[4], GLfloat weight[4], void **dataOut) 0044 { 0045 } 0046 /*ARGSUSED*/ static void GLAPIENTRY noMesh(GLUmesh *mesh) 0047 { 0048 } 0049 0050 /*ARGSUSED*/ void GLAPIENTRY __gl_noBeginData(GLenum type, void *polygonData) 0051 { 0052 } 0053 /*ARGSUSED*/ void GLAPIENTRY __gl_noEdgeFlagData(GLboolean boundaryEdge, void *polygonData) 0054 { 0055 } 0056 /*ARGSUSED*/ void GLAPIENTRY __gl_noVertexData(void *data, void *polygonData) 0057 { 0058 } 0059 /*ARGSUSED*/ void GLAPIENTRY __gl_noEndData(void *polygonData) 0060 { 0061 } 0062 /*ARGSUSED*/ void GLAPIENTRY __gl_noErrorData(GLenum errnum, void *polygonData) 0063 { 0064 } 0065 /*ARGSUSED*/ void GLAPIENTRY __gl_noCombineData(GLdouble coords[3], void *data[4], GLfloat weight[4], void **outData, 0066 void *polygonData) 0067 { 0068 } 0069 0070 /* Half-edges are allocated in pairs (see mesh.c) */ 0071 typedef struct 0072 { 0073 GLUhalfEdge e, eSym; 0074 } EdgePair; 0075 0076 #undef MAX 0077 #define MAX(a, b) ((a) > (b) ? (a) : (b)) 0078 #define MAX_FAST_ALLOC (MAX(sizeof(EdgePair), MAX(sizeof(GLUvertex), sizeof(GLUface)))) 0079 0080 GLUtesselator *GLAPIENTRY gluNewTess(void) 0081 { 0082 GLUtesselator *tess; 0083 0084 /* Only initialize fields which can be changed by the api. Other fields 0085 * are initialized where they are used. 0086 */ 0087 0088 if (memInit(MAX_FAST_ALLOC) == 0) 0089 { 0090 return 0; /* out of memory */ 0091 } 0092 tess = (GLUtesselator *)memAlloc(sizeof(GLUtesselator)); 0093 if (tess == NULL) 0094 { 0095 return 0; /* out of memory */ 0096 } 0097 0098 tess->state = T_DORMANT; 0099 0100 tess->normal[0] = 0; 0101 tess->normal[1] = 0; 0102 tess->normal[2] = 0; 0103 0104 tess->relTolerance = GLU_TESS_DEFAULT_TOLERANCE; 0105 tess->windingRule = GLU_TESS_WINDING_ODD; 0106 tess->flagBoundary = FALSE; 0107 tess->boundaryOnly = FALSE; 0108 0109 tess->callBegin = &noBegin; 0110 tess->callEdgeFlag = &noEdgeFlag; 0111 tess->callVertex = &noVertex; 0112 tess->callEnd = &noEnd; 0113 0114 tess->callError = &noError; 0115 tess->callCombine = &noCombine; 0116 tess->callMesh = &noMesh; 0117 0118 tess->callBeginData = &__gl_noBeginData; 0119 tess->callEdgeFlagData = &__gl_noEdgeFlagData; 0120 tess->callVertexData = &__gl_noVertexData; 0121 tess->callEndData = &__gl_noEndData; 0122 tess->callErrorData = &__gl_noErrorData; 0123 tess->callCombineData = &__gl_noCombineData; 0124 0125 tess->polygonData = NULL; 0126 0127 return tess; 0128 } 0129 0130 static void MakeDormant(GLUtesselator *tess) 0131 { 0132 /* Return the tessellator to its original dormant state. */ 0133 0134 if (tess->mesh != NULL) 0135 { 0136 __gl_meshDeleteMesh(tess->mesh); 0137 } 0138 tess->state = T_DORMANT; 0139 tess->lastEdge = NULL; 0140 tess->mesh = NULL; 0141 } 0142 0143 #define RequireState(tess, s) \ 0144 if (tess->state != s) \ 0145 GotoState(tess, s) 0146 0147 static void GotoState(GLUtesselator *tess, enum TessState newState) 0148 { 0149 while (tess->state != newState) 0150 { 0151 /* We change the current state one level at a time, to get to 0152 * the desired state. 0153 */ 0154 if (tess->state < newState) 0155 { 0156 switch (tess->state) 0157 { 0158 case T_DORMANT: 0159 CALL_ERROR_OR_ERROR_DATA(GLU_TESS_MISSING_BEGIN_POLYGON); 0160 gluTessBeginPolygon(tess, NULL); 0161 break; 0162 case T_IN_POLYGON: 0163 CALL_ERROR_OR_ERROR_DATA(GLU_TESS_MISSING_BEGIN_CONTOUR); 0164 gluTessBeginContour(tess); 0165 break; 0166 default:; 0167 } 0168 } 0169 else 0170 { 0171 switch (tess->state) 0172 { 0173 case T_IN_CONTOUR: 0174 CALL_ERROR_OR_ERROR_DATA(GLU_TESS_MISSING_END_CONTOUR); 0175 gluTessEndContour(tess); 0176 break; 0177 case T_IN_POLYGON: 0178 CALL_ERROR_OR_ERROR_DATA(GLU_TESS_MISSING_END_POLYGON); 0179 /* gluTessEndPolygon( tess ) is too much work! */ 0180 MakeDormant(tess); 0181 break; 0182 default:; 0183 } 0184 } 0185 } 0186 } 0187 0188 void GLAPIENTRY gluDeleteTess(GLUtesselator *tess) 0189 { 0190 RequireState(tess, T_DORMANT); 0191 memFree(tess); 0192 } 0193 0194 void GLAPIENTRY gluTessProperty(GLUtesselator *tess, GLenum which, GLdouble value) 0195 { 0196 GLenum windingRule; 0197 0198 switch (which) 0199 { 0200 case GLU_TESS_TOLERANCE: 0201 if (value < 0.0 || value > 1.0) 0202 break; 0203 tess->relTolerance = value; 0204 return; 0205 0206 case GLU_TESS_WINDING_RULE: 0207 windingRule = (GLenum)value; 0208 if (windingRule != value) 0209 break; /* not an integer */ 0210 0211 switch (windingRule) 0212 { 0213 case GLU_TESS_WINDING_ODD: 0214 case GLU_TESS_WINDING_NONZERO: 0215 case GLU_TESS_WINDING_POSITIVE: 0216 case GLU_TESS_WINDING_NEGATIVE: 0217 case GLU_TESS_WINDING_ABS_GEQ_TWO: 0218 tess->windingRule = windingRule; 0219 return; 0220 default: 0221 break; 0222 } 0223 0224 case GLU_TESS_BOUNDARY_ONLY: 0225 tess->boundaryOnly = (value != 0); 0226 return; 0227 0228 default: 0229 CALL_ERROR_OR_ERROR_DATA(GLU_INVALID_ENUM); 0230 return; 0231 } 0232 CALL_ERROR_OR_ERROR_DATA(GLU_INVALID_VALUE); 0233 } 0234 0235 /* Returns tessellator property */ 0236 void GLAPIENTRY gluGetTessProperty(GLUtesselator *tess, GLenum which, GLdouble *value) 0237 { 0238 switch (which) 0239 { 0240 case GLU_TESS_TOLERANCE: 0241 /* tolerance should be in range [0..1] */ 0242 assert(0.0 <= tess->relTolerance && tess->relTolerance <= 1.0); 0243 *value = tess->relTolerance; 0244 break; 0245 case GLU_TESS_WINDING_RULE: 0246 assert(tess->windingRule == GLU_TESS_WINDING_ODD || tess->windingRule == GLU_TESS_WINDING_NONZERO || 0247 tess->windingRule == GLU_TESS_WINDING_POSITIVE || tess->windingRule == GLU_TESS_WINDING_NEGATIVE || 0248 tess->windingRule == GLU_TESS_WINDING_ABS_GEQ_TWO); 0249 *value = tess->windingRule; 0250 break; 0251 case GLU_TESS_BOUNDARY_ONLY: 0252 assert(tess->boundaryOnly == TRUE || tess->boundaryOnly == FALSE); 0253 *value = tess->boundaryOnly; 0254 break; 0255 default: 0256 *value = 0.0; 0257 CALL_ERROR_OR_ERROR_DATA(GLU_INVALID_ENUM); 0258 break; 0259 } 0260 } /* gluGetTessProperty() */ 0261 0262 void GLAPIENTRY gluTessNormal(GLUtesselator *tess, GLdouble x, GLdouble y, GLdouble z) 0263 { 0264 tess->normal[0] = x; 0265 tess->normal[1] = y; 0266 tess->normal[2] = z; 0267 } 0268 0269 void GLAPIENTRY gluTessCallback(GLUtesselator *tess, GLenum which, _GLUfuncptr fn) 0270 { 0271 switch (which) 0272 { 0273 case GLU_TESS_BEGIN: 0274 tess->callBegin = (fn == NULL) ? &noBegin : (void(GLAPIENTRY *)(GLenum))fn; 0275 return; 0276 case GLU_TESS_BEGIN_DATA: 0277 tess->callBeginData = (fn == NULL) ? &__gl_noBeginData : (void(GLAPIENTRY *)(GLenum, void *))fn; 0278 return; 0279 case GLU_TESS_EDGE_FLAG: 0280 tess->callEdgeFlag = (fn == NULL) ? &noEdgeFlag : (void(GLAPIENTRY *)(GLboolean))fn; 0281 /* If the client wants boundary edges to be flagged, 0282 * we render everything as separate triangles (no strips or fans). 0283 */ 0284 tess->flagBoundary = (fn != NULL); 0285 return; 0286 case GLU_TESS_EDGE_FLAG_DATA: 0287 tess->callEdgeFlagData = (fn == NULL) ? &__gl_noEdgeFlagData : (void(GLAPIENTRY *)(GLboolean, void *))fn; 0288 /* If the client wants boundary edges to be flagged, 0289 * we render everything as separate triangles (no strips or fans). 0290 */ 0291 tess->flagBoundary = (fn != NULL); 0292 return; 0293 case GLU_TESS_VERTEX: 0294 tess->callVertex = (fn == NULL) ? &noVertex : (void(GLAPIENTRY *)(void *))fn; 0295 return; 0296 case GLU_TESS_VERTEX_DATA: 0297 tess->callVertexData = (fn == NULL) ? &__gl_noVertexData : (void(GLAPIENTRY *)(void *, void *))fn; 0298 return; 0299 case GLU_TESS_END: 0300 tess->callEnd = (fn == NULL) ? &noEnd : (void(GLAPIENTRY *)(void))fn; 0301 return; 0302 case GLU_TESS_END_DATA: 0303 tess->callEndData = (fn == NULL) ? &__gl_noEndData : (void(GLAPIENTRY *)(void *))fn; 0304 return; 0305 case GLU_TESS_ERROR: 0306 tess->callError = (fn == NULL) ? &noError : (void(GLAPIENTRY *)(GLenum))fn; 0307 return; 0308 case GLU_TESS_ERROR_DATA: 0309 tess->callErrorData = (fn == NULL) ? &__gl_noErrorData : (void(GLAPIENTRY *)(GLenum, void *))fn; 0310 return; 0311 case GLU_TESS_COMBINE: 0312 tess->callCombine = 0313 (fn == NULL) ? &noCombine : (void(GLAPIENTRY *)(GLdouble[3], void * [4], GLfloat[4], void **)) fn; 0314 return; 0315 case GLU_TESS_COMBINE_DATA: 0316 tess->callCombineData = (fn == NULL) ? 0317 &__gl_noCombineData : 0318 (void(GLAPIENTRY *)(GLdouble[3], void * [4], GLfloat[4], void **, void *)) fn; 0319 return; 0320 case GLU_TESS_MESH: 0321 tess->callMesh = (fn == NULL) ? &noMesh : (void(GLAPIENTRY *)(GLUmesh *))fn; 0322 return; 0323 default: 0324 CALL_ERROR_OR_ERROR_DATA(GLU_INVALID_ENUM); 0325 return; 0326 } 0327 } 0328 0329 static int AddVertex(GLUtesselator *tess, GLdouble coords[3], void *data) 0330 { 0331 GLUhalfEdge *e; 0332 0333 e = tess->lastEdge; 0334 if (e == NULL) 0335 { 0336 /* Make a self-loop (one vertex, one edge). */ 0337 0338 e = __gl_meshMakeEdge(tess->mesh); 0339 if (e == NULL) 0340 return 0; 0341 if (!__gl_meshSplice(e, e->Sym)) 0342 return 0; 0343 } 0344 else 0345 { 0346 /* Create a new vertex and edge which immediately follow e 0347 * in the ordering around the left face. 0348 */ 0349 if (__gl_meshSplitEdge(e) == NULL) 0350 return 0; 0351 e = e->Lnext; 0352 } 0353 0354 /* The new vertex is now e->Org. */ 0355 e->Org->data = data; 0356 e->Org->coords[0] = coords[0]; 0357 e->Org->coords[1] = coords[1]; 0358 e->Org->coords[2] = coords[2]; 0359 0360 /* The winding of an edge says how the winding number changes as we 0361 * cross from the edge''s right face to its left face. We add the 0362 * vertices in such an order that a CCW contour will add +1 to 0363 * the winding number of the region inside the contour. 0364 */ 0365 e->winding = 1; 0366 e->Sym->winding = -1; 0367 0368 tess->lastEdge = e; 0369 0370 return 1; 0371 } 0372 0373 static void CacheVertex(GLUtesselator *tess, GLdouble coords[3], void *data) 0374 { 0375 CachedVertex *v = &tess->cache[tess->cacheCount]; 0376 0377 v->data = data; 0378 v->coords[0] = coords[0]; 0379 v->coords[1] = coords[1]; 0380 v->coords[2] = coords[2]; 0381 ++tess->cacheCount; 0382 } 0383 0384 static int EmptyCache(GLUtesselator *tess) 0385 { 0386 CachedVertex *v = tess->cache; 0387 CachedVertex *vLast; 0388 0389 tess->mesh = __gl_meshNewMesh(); 0390 if (tess->mesh == NULL) 0391 return 0; 0392 0393 for (vLast = v + tess->cacheCount; v < vLast; ++v) 0394 { 0395 if (!AddVertex(tess, v->coords, v->data)) 0396 return 0; 0397 } 0398 tess->cacheCount = 0; 0399 tess->emptyCache = FALSE; 0400 0401 return 1; 0402 } 0403 0404 void GLAPIENTRY gluTessVertex(GLUtesselator *tess, GLdouble coords[3], void *data) 0405 { 0406 int i, tooLarge = FALSE; 0407 GLdouble x, clamped[3]; 0408 0409 RequireState(tess, T_IN_CONTOUR); 0410 0411 if (tess->emptyCache) 0412 { 0413 if (!EmptyCache(tess)) 0414 { 0415 CALL_ERROR_OR_ERROR_DATA(GLU_OUT_OF_MEMORY); 0416 return; 0417 } 0418 tess->lastEdge = NULL; 0419 } 0420 for (i = 0; i < 3; ++i) 0421 { 0422 x = coords[i]; 0423 if (x < -GLU_TESS_MAX_COORD) 0424 { 0425 x = -GLU_TESS_MAX_COORD; 0426 tooLarge = TRUE; 0427 } 0428 if (x > GLU_TESS_MAX_COORD) 0429 { 0430 x = GLU_TESS_MAX_COORD; 0431 tooLarge = TRUE; 0432 } 0433 clamped[i] = x; 0434 } 0435 if (tooLarge) 0436 { 0437 CALL_ERROR_OR_ERROR_DATA(GLU_TESS_COORD_TOO_LARGE); 0438 } 0439 0440 if (tess->mesh == NULL) 0441 { 0442 if (tess->cacheCount < TESS_MAX_CACHE) 0443 { 0444 CacheVertex(tess, clamped, data); 0445 return; 0446 } 0447 if (!EmptyCache(tess)) 0448 { 0449 CALL_ERROR_OR_ERROR_DATA(GLU_OUT_OF_MEMORY); 0450 return; 0451 } 0452 } 0453 if (!AddVertex(tess, clamped, data)) 0454 { 0455 CALL_ERROR_OR_ERROR_DATA(GLU_OUT_OF_MEMORY); 0456 } 0457 } 0458 0459 void GLAPIENTRY gluTessBeginPolygon(GLUtesselator *tess, void *data) 0460 { 0461 RequireState(tess, T_DORMANT); 0462 0463 tess->state = T_IN_POLYGON; 0464 tess->cacheCount = 0; 0465 tess->emptyCache = FALSE; 0466 tess->mesh = NULL; 0467 0468 tess->polygonData = data; 0469 } 0470 0471 void GLAPIENTRY gluTessBeginContour(GLUtesselator *tess) 0472 { 0473 RequireState(tess, T_IN_POLYGON); 0474 0475 tess->state = T_IN_CONTOUR; 0476 tess->lastEdge = NULL; 0477 if (tess->cacheCount > 0) 0478 { 0479 /* Just set a flag so we don't get confused by empty contours 0480 * -- these can be generated accidentally with the obsolete 0481 * NextContour() interface. 0482 */ 0483 tess->emptyCache = TRUE; 0484 } 0485 } 0486 0487 void GLAPIENTRY gluTessEndContour(GLUtesselator *tess) 0488 { 0489 RequireState(tess, T_IN_CONTOUR); 0490 tess->state = T_IN_POLYGON; 0491 } 0492 0493 void GLAPIENTRY gluTessEndPolygon(GLUtesselator *tess) 0494 { 0495 GLUmesh *mesh; 0496 0497 if (setjmp(tess->env) != 0) 0498 { 0499 /* come back here if out of memory */ 0500 CALL_ERROR_OR_ERROR_DATA(GLU_OUT_OF_MEMORY); 0501 return; 0502 } 0503 0504 RequireState(tess, T_IN_POLYGON); 0505 tess->state = T_DORMANT; 0506 0507 if (tess->mesh == NULL) 0508 { 0509 if (!tess->flagBoundary && tess->callMesh == &noMesh) 0510 { 0511 /* Try some special code to make the easy cases go quickly 0512 * (eg. convex polygons). This code does NOT handle multiple contours, 0513 * intersections, edge flags, and of course it does not generate 0514 * an explicit mesh either. 0515 */ 0516 if (__gl_renderCache(tess)) 0517 { 0518 tess->polygonData = NULL; 0519 return; 0520 } 0521 } 0522 if (!EmptyCache(tess)) 0523 longjmp(tess->env, 1); /* could've used a label*/ 0524 } 0525 0526 /* Determine the polygon normal and project vertices onto the plane 0527 * of the polygon. 0528 */ 0529 __gl_projectPolygon(tess); 0530 0531 /* __gl_computeInterior( tess ) computes the planar arrangement specified 0532 * by the given contours, and further subdivides this arrangement 0533 * into regions. Each region is marked "inside" if it belongs 0534 * to the polygon, according to the rule given by tess->windingRule. 0535 * Each interior region is guaranteed be monotone. 0536 */ 0537 if (!__gl_computeInterior(tess)) 0538 { 0539 longjmp(tess->env, 1); /* could've used a label */ 0540 } 0541 0542 mesh = tess->mesh; 0543 if (!tess->fatalError) 0544 { 0545 int rc = 1; 0546 0547 /* If the user wants only the boundary contours, we throw away all edges 0548 * except those which separate the interior from the exterior. 0549 * Otherwise we tessellate all the regions marked "inside". 0550 */ 0551 if (tess->boundaryOnly) 0552 { 0553 rc = __gl_meshSetWindingNumber(mesh, 1, TRUE); 0554 } 0555 else 0556 { 0557 rc = __gl_meshTessellateInterior(mesh); 0558 } 0559 if (rc == 0) 0560 longjmp(tess->env, 1); /* could've used a label */ 0561 0562 __gl_meshCheckMesh(mesh); 0563 0564 if (tess->callBegin != &noBegin || tess->callEnd != &noEnd || tess->callVertex != &noVertex || 0565 tess->callEdgeFlag != &noEdgeFlag || tess->callBeginData != &__gl_noBeginData || 0566 tess->callEndData != &__gl_noEndData || tess->callVertexData != &__gl_noVertexData || 0567 tess->callEdgeFlagData != &__gl_noEdgeFlagData) 0568 { 0569 if (tess->boundaryOnly) 0570 { 0571 __gl_renderBoundary(tess, mesh); /* output boundary contours */ 0572 } 0573 else 0574 { 0575 __gl_renderMesh(tess, mesh); /* output strips and fans */ 0576 } 0577 } 0578 if (tess->callMesh != &noMesh) 0579 { 0580 /* Throw away the exterior faces, so that all faces are interior. 0581 * This way the user doesn't have to check the "inside" flag, 0582 * and we don't need to even reveal its existence. It also leaves 0583 * the freedom for an implementation to not generate the exterior 0584 * faces in the first place. 0585 */ 0586 __gl_meshDiscardExterior(mesh); 0587 (*tess->callMesh)(mesh); /* user wants the mesh itself */ 0588 tess->mesh = NULL; 0589 tess->polygonData = NULL; 0590 return; 0591 } 0592 } 0593 __gl_meshDeleteMesh(mesh); 0594 tess->polygonData = NULL; 0595 tess->mesh = NULL; 0596 } 0597 0598 /*XXXblythe unused function*/ 0599 #if 0 0600 void GLAPIENTRY 0601 gluDeleteMesh( GLUmesh *mesh ) 0602 { 0603 __gl_meshDeleteMesh( mesh ); 0604 } 0605 #endif 0606 0607 /*******************************************************/ 0608 0609 /* Obsolete calls -- for backward compatibility */ 0610 0611 void GLAPIENTRY gluBeginPolygon(GLUtesselator *tess) 0612 { 0613 gluTessBeginPolygon(tess, NULL); 0614 gluTessBeginContour(tess); 0615 } 0616 0617 /*ARGSUSED*/ 0618 void GLAPIENTRY gluNextContour(GLUtesselator *tess, GLenum type) 0619 { 0620 gluTessEndContour(tess); 0621 gluTessBeginContour(tess); 0622 } 0623 0624 void GLAPIENTRY gluEndPolygon(GLUtesselator *tess) 0625 { 0626 gluTessEndContour(tess); 0627 gluTessEndPolygon(tess); 0628 }