Synchronize with trunk's revision r57629.
[reactos.git] / dll / opengl / glu32 / src / libtess / tess.c
1 /*
2 * SGI FREE SOFTWARE LICENSE B (Version 2.0, Sept. 18, 2008)
3 * Copyright (C) 1991-2000 Silicon Graphics, Inc. All Rights Reserved.
4 *
5 * Permission is hereby granted, free of charge, to any person obtaining a
6 * copy of this software and associated documentation files (the "Software"),
7 * to deal in the Software without restriction, including without limitation
8 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
9 * and/or sell copies of the Software, and to permit persons to whom the
10 * Software is furnished to do so, subject to the following conditions:
11 *
12 * The above copyright notice including the dates of first publication and
13 * either this permission notice or a reference to
14 * http://oss.sgi.com/projects/FreeB/
15 * shall be included in all copies or substantial portions of the Software.
16 *
17 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
18 * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
19 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
20 * SILICON GRAPHICS, INC. BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
21 * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF
22 * OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
23 * SOFTWARE.
24 *
25 * Except as contained in this notice, the name of Silicon Graphics, Inc.
26 * shall not be used in advertising or otherwise to promote the sale, use or
27 * other dealings in this Software without prior written authorization from
28 * Silicon Graphics, Inc.
29 */
30 /*
31 ** Author: Eric Veach, July 1994.
32 **
33 */
34
35 #include "gluos.h"
36 #include <stddef.h>
37 #include <assert.h>
38 #include <setjmp.h>
39 #include "memalloc.h"
40 #include "tess.h"
41 #include "mesh.h"
42 #include "normal.h"
43 #include "sweep.h"
44 #include "tessmono.h"
45 #include "render.h"
46
47 #define GLU_TESS_DEFAULT_TOLERANCE 0.0
48 #define GLU_TESS_MESH 100112 /* void (*)(GLUmesh *mesh) */
49
50 #ifndef TRUE
51 #define TRUE 1
52 #endif
53 #ifndef FALSE
54 #define FALSE 0
55 #endif
56
57 /*ARGSUSED*/ static void GLAPIENTRY noBegin( GLenum type ) {}
58 /*ARGSUSED*/ static void GLAPIENTRY noEdgeFlag( GLboolean boundaryEdge ) {}
59 /*ARGSUSED*/ static void GLAPIENTRY noVertex( void *data ) {}
60 /*ARGSUSED*/ static void GLAPIENTRY noEnd( void ) {}
61 /*ARGSUSED*/ static void GLAPIENTRY noError( GLenum errnum ) {}
62 /*ARGSUSED*/ static void GLAPIENTRY noCombine( GLdouble coords[3], void *data[4],
63 GLfloat weight[4], void **dataOut ) {}
64 /*ARGSUSED*/ static void GLAPIENTRY noMesh( GLUmesh *mesh ) {}
65
66
67 /*ARGSUSED*/ void GLAPIENTRY __gl_noBeginData( GLenum type,
68 void *polygonData ) {}
69 /*ARGSUSED*/ void GLAPIENTRY __gl_noEdgeFlagData( GLboolean boundaryEdge,
70 void *polygonData ) {}
71 /*ARGSUSED*/ void GLAPIENTRY __gl_noVertexData( void *data,
72 void *polygonData ) {}
73 /*ARGSUSED*/ void GLAPIENTRY __gl_noEndData( void *polygonData ) {}
74 /*ARGSUSED*/ void GLAPIENTRY __gl_noErrorData( GLenum errnum,
75 void *polygonData ) {}
76 /*ARGSUSED*/ void GLAPIENTRY __gl_noCombineData( GLdouble coords[3],
77 void *data[4],
78 GLfloat weight[4],
79 void **outData,
80 void *polygonData ) {}
81
82 /* Half-edges are allocated in pairs (see mesh.c) */
83 typedef struct { GLUhalfEdge e, eSym; } EdgePair;
84
85 #undef MAX
86 #define MAX(a,b) ((a) > (b) ? (a) : (b))
87 #define MAX_FAST_ALLOC (MAX(sizeof(EdgePair), \
88 MAX(sizeof(GLUvertex),sizeof(GLUface))))
89
90
91 GLUtesselator * GLAPIENTRY
92 gluNewTess( void )
93 {
94 GLUtesselator *tess;
95
96 /* Only initialize fields which can be changed by the api. Other fields
97 * are initialized where they are used.
98 */
99
100 if (memInit( MAX_FAST_ALLOC ) == 0) {
101 return 0; /* out of memory */
102 }
103 tess = (GLUtesselator *)memAlloc( sizeof( GLUtesselator ));
104 if (tess == NULL) {
105 return 0; /* out of memory */
106 }
107
108 tess->state = T_DORMANT;
109
110 tess->normal[0] = 0;
111 tess->normal[1] = 0;
112 tess->normal[2] = 0;
113
114 tess->relTolerance = GLU_TESS_DEFAULT_TOLERANCE;
115 tess->windingRule = GLU_TESS_WINDING_ODD;
116 tess->flagBoundary = FALSE;
117 tess->boundaryOnly = FALSE;
118
119 tess->callBegin = &noBegin;
120 tess->callEdgeFlag = &noEdgeFlag;
121 tess->callVertex = &noVertex;
122 tess->callEnd = &noEnd;
123
124 tess->callError = &noError;
125 tess->callCombine = &noCombine;
126 tess->callMesh = &noMesh;
127
128 tess->callBeginData= &__gl_noBeginData;
129 tess->callEdgeFlagData= &__gl_noEdgeFlagData;
130 tess->callVertexData= &__gl_noVertexData;
131 tess->callEndData= &__gl_noEndData;
132 tess->callErrorData= &__gl_noErrorData;
133 tess->callCombineData= &__gl_noCombineData;
134
135 tess->polygonData= NULL;
136
137 return tess;
138 }
139
140 static void MakeDormant( GLUtesselator *tess )
141 {
142 /* Return the tessellator to its original dormant state. */
143
144 if( tess->mesh != NULL ) {
145 __gl_meshDeleteMesh( tess->mesh );
146 }
147 tess->state = T_DORMANT;
148 tess->lastEdge = NULL;
149 tess->mesh = NULL;
150 }
151
152 #define RequireState( tess, s ) if( tess->state != s ) GotoState(tess,s)
153
154 static void GotoState( GLUtesselator *tess, enum TessState newState )
155 {
156 while( tess->state != newState ) {
157 /* We change the current state one level at a time, to get to
158 * the desired state.
159 */
160 if( tess->state < newState ) {
161 switch( tess->state ) {
162 case T_DORMANT:
163 CALL_ERROR_OR_ERROR_DATA( GLU_TESS_MISSING_BEGIN_POLYGON );
164 gluTessBeginPolygon( tess, NULL );
165 break;
166 case T_IN_POLYGON:
167 CALL_ERROR_OR_ERROR_DATA( GLU_TESS_MISSING_BEGIN_CONTOUR );
168 gluTessBeginContour( tess );
169 break;
170 default:
171 ;
172 }
173 } else {
174 switch( tess->state ) {
175 case T_IN_CONTOUR:
176 CALL_ERROR_OR_ERROR_DATA( GLU_TESS_MISSING_END_CONTOUR );
177 gluTessEndContour( tess );
178 break;
179 case T_IN_POLYGON:
180 CALL_ERROR_OR_ERROR_DATA( GLU_TESS_MISSING_END_POLYGON );
181 /* gluTessEndPolygon( tess ) is too much work! */
182 MakeDormant( tess );
183 break;
184 default:
185 ;
186 }
187 }
188 }
189 }
190
191
192 void GLAPIENTRY
193 gluDeleteTess( GLUtesselator *tess )
194 {
195 RequireState( tess, T_DORMANT );
196 memFree( tess );
197 }
198
199
200 void GLAPIENTRY
201 gluTessProperty( GLUtesselator *tess, GLenum which, GLdouble value )
202 {
203 GLenum windingRule;
204
205 switch( which ) {
206 case GLU_TESS_TOLERANCE:
207 if( value < 0.0 || value > 1.0 ) break;
208 tess->relTolerance = value;
209 return;
210
211 case GLU_TESS_WINDING_RULE:
212 windingRule = (GLenum) value;
213 if( windingRule != value ) break; /* not an integer */
214
215 switch( windingRule ) {
216 case GLU_TESS_WINDING_ODD:
217 case GLU_TESS_WINDING_NONZERO:
218 case GLU_TESS_WINDING_POSITIVE:
219 case GLU_TESS_WINDING_NEGATIVE:
220 case GLU_TESS_WINDING_ABS_GEQ_TWO:
221 tess->windingRule = windingRule;
222 return;
223 default:
224 break;
225 }
226
227 case GLU_TESS_BOUNDARY_ONLY:
228 tess->boundaryOnly = (value != 0);
229 return;
230
231 default:
232 CALL_ERROR_OR_ERROR_DATA( GLU_INVALID_ENUM );
233 return;
234 }
235 CALL_ERROR_OR_ERROR_DATA( GLU_INVALID_VALUE );
236 }
237
238 /* Returns tessellator property */
239 void GLAPIENTRY
240 gluGetTessProperty( GLUtesselator *tess, GLenum which, GLdouble *value )
241 {
242 switch (which) {
243 case GLU_TESS_TOLERANCE:
244 /* tolerance should be in range [0..1] */
245 assert(0.0 <= tess->relTolerance && tess->relTolerance <= 1.0);
246 *value= tess->relTolerance;
247 break;
248 case GLU_TESS_WINDING_RULE:
249 assert(tess->windingRule == GLU_TESS_WINDING_ODD ||
250 tess->windingRule == GLU_TESS_WINDING_NONZERO ||
251 tess->windingRule == GLU_TESS_WINDING_POSITIVE ||
252 tess->windingRule == GLU_TESS_WINDING_NEGATIVE ||
253 tess->windingRule == GLU_TESS_WINDING_ABS_GEQ_TWO);
254 *value= tess->windingRule;
255 break;
256 case GLU_TESS_BOUNDARY_ONLY:
257 assert(tess->boundaryOnly == TRUE || tess->boundaryOnly == FALSE);
258 *value= tess->boundaryOnly;
259 break;
260 default:
261 *value= 0.0;
262 CALL_ERROR_OR_ERROR_DATA( GLU_INVALID_ENUM );
263 break;
264 }
265 } /* gluGetTessProperty() */
266
267 void GLAPIENTRY
268 gluTessNormal( GLUtesselator *tess, GLdouble x, GLdouble y, GLdouble z )
269 {
270 tess->normal[0] = x;
271 tess->normal[1] = y;
272 tess->normal[2] = z;
273 }
274
275 void GLAPIENTRY
276 gluTessCallback( GLUtesselator *tess, GLenum which, _GLUfuncptr fn)
277 {
278 switch( which ) {
279 case GLU_TESS_BEGIN:
280 tess->callBegin = (fn == NULL) ? &noBegin : (void (GLAPIENTRY *)(GLenum)) fn;
281 return;
282 case GLU_TESS_BEGIN_DATA:
283 tess->callBeginData = (fn == NULL) ?
284 &__gl_noBeginData : (void (GLAPIENTRY *)(GLenum, void *)) fn;
285 return;
286 case GLU_TESS_EDGE_FLAG:
287 tess->callEdgeFlag = (fn == NULL) ? &noEdgeFlag :
288 (void (GLAPIENTRY *)(GLboolean)) fn;
289 /* If the client wants boundary edges to be flagged,
290 * we render everything as separate triangles (no strips or fans).
291 */
292 tess->flagBoundary = (fn != NULL);
293 return;
294 case GLU_TESS_EDGE_FLAG_DATA:
295 tess->callEdgeFlagData= (fn == NULL) ?
296 &__gl_noEdgeFlagData : (void (GLAPIENTRY *)(GLboolean, void *)) fn;
297 /* If the client wants boundary edges to be flagged,
298 * we render everything as separate triangles (no strips or fans).
299 */
300 tess->flagBoundary = (fn != NULL);
301 return;
302 case GLU_TESS_VERTEX:
303 tess->callVertex = (fn == NULL) ? &noVertex :
304 (void (GLAPIENTRY *)(void *)) fn;
305 return;
306 case GLU_TESS_VERTEX_DATA:
307 tess->callVertexData = (fn == NULL) ?
308 &__gl_noVertexData : (void (GLAPIENTRY *)(void *, void *)) fn;
309 return;
310 case GLU_TESS_END:
311 tess->callEnd = (fn == NULL) ? &noEnd : (void (GLAPIENTRY *)(void)) fn;
312 return;
313 case GLU_TESS_END_DATA:
314 tess->callEndData = (fn == NULL) ? &__gl_noEndData :
315 (void (GLAPIENTRY *)(void *)) fn;
316 return;
317 case GLU_TESS_ERROR:
318 tess->callError = (fn == NULL) ? &noError : (void (GLAPIENTRY *)(GLenum)) fn;
319 return;
320 case GLU_TESS_ERROR_DATA:
321 tess->callErrorData = (fn == NULL) ?
322 &__gl_noErrorData : (void (GLAPIENTRY *)(GLenum, void *)) fn;
323 return;
324 case GLU_TESS_COMBINE:
325 tess->callCombine = (fn == NULL) ? &noCombine :
326 (void (GLAPIENTRY *)(GLdouble [3],void *[4], GLfloat [4], void ** )) fn;
327 return;
328 case GLU_TESS_COMBINE_DATA:
329 tess->callCombineData = (fn == NULL) ? &__gl_noCombineData :
330 (void (GLAPIENTRY *)(GLdouble [3],
331 void *[4],
332 GLfloat [4],
333 void **,
334 void *)) fn;
335 return;
336 case GLU_TESS_MESH:
337 tess->callMesh = (fn == NULL) ? &noMesh : (void (GLAPIENTRY *)(GLUmesh *)) fn;
338 return;
339 default:
340 CALL_ERROR_OR_ERROR_DATA( GLU_INVALID_ENUM );
341 return;
342 }
343 }
344
345 static int AddVertex( GLUtesselator *tess, GLdouble coords[3], void *data )
346 {
347 GLUhalfEdge *e;
348
349 e = tess->lastEdge;
350 if( e == NULL ) {
351 /* Make a self-loop (one vertex, one edge). */
352
353 e = __gl_meshMakeEdge( tess->mesh );
354 if (e == NULL) return 0;
355 if ( !__gl_meshSplice( e, e->Sym ) ) return 0;
356 } else {
357 /* Create a new vertex and edge which immediately follow e
358 * in the ordering around the left face.
359 */
360 if (__gl_meshSplitEdge( e ) == NULL) return 0;
361 e = e->Lnext;
362 }
363
364 /* The new vertex is now e->Org. */
365 e->Org->data = data;
366 e->Org->coords[0] = coords[0];
367 e->Org->coords[1] = coords[1];
368 e->Org->coords[2] = coords[2];
369
370 /* The winding of an edge says how the winding number changes as we
371 * cross from the edge''s right face to its left face. We add the
372 * vertices in such an order that a CCW contour will add +1 to
373 * the winding number of the region inside the contour.
374 */
375 e->winding = 1;
376 e->Sym->winding = -1;
377
378 tess->lastEdge = e;
379
380 return 1;
381 }
382
383
384 static void CacheVertex( GLUtesselator *tess, GLdouble coords[3], void *data )
385 {
386 CachedVertex *v = &tess->cache[tess->cacheCount];
387
388 v->data = data;
389 v->coords[0] = coords[0];
390 v->coords[1] = coords[1];
391 v->coords[2] = coords[2];
392 ++tess->cacheCount;
393 }
394
395
396 static int EmptyCache( GLUtesselator *tess )
397 {
398 CachedVertex *v = tess->cache;
399 CachedVertex *vLast;
400
401 tess->mesh = __gl_meshNewMesh();
402 if (tess->mesh == NULL) return 0;
403
404 for( vLast = v + tess->cacheCount; v < vLast; ++v ) {
405 if ( !AddVertex( tess, v->coords, v->data ) ) return 0;
406 }
407 tess->cacheCount = 0;
408 tess->emptyCache = FALSE;
409
410 return 1;
411 }
412
413
414 void GLAPIENTRY
415 gluTessVertex( GLUtesselator *tess, GLdouble coords[3], void *data )
416 {
417 int i, tooLarge = FALSE;
418 GLdouble x, clamped[3];
419
420 RequireState( tess, T_IN_CONTOUR );
421
422 if( tess->emptyCache ) {
423 if ( !EmptyCache( tess ) ) {
424 CALL_ERROR_OR_ERROR_DATA( GLU_OUT_OF_MEMORY );
425 return;
426 }
427 tess->lastEdge = NULL;
428 }
429 for( i = 0; i < 3; ++i ) {
430 x = coords[i];
431 if( x < - GLU_TESS_MAX_COORD ) {
432 x = - GLU_TESS_MAX_COORD;
433 tooLarge = TRUE;
434 }
435 if( x > GLU_TESS_MAX_COORD ) {
436 x = GLU_TESS_MAX_COORD;
437 tooLarge = TRUE;
438 }
439 clamped[i] = x;
440 }
441 if( tooLarge ) {
442 CALL_ERROR_OR_ERROR_DATA( GLU_TESS_COORD_TOO_LARGE );
443 }
444
445 if( tess->mesh == NULL ) {
446 if( tess->cacheCount < TESS_MAX_CACHE ) {
447 CacheVertex( tess, clamped, data );
448 return;
449 }
450 if ( !EmptyCache( tess ) ) {
451 CALL_ERROR_OR_ERROR_DATA( GLU_OUT_OF_MEMORY );
452 return;
453 }
454 }
455 if ( !AddVertex( tess, clamped, data ) ) {
456 CALL_ERROR_OR_ERROR_DATA( GLU_OUT_OF_MEMORY );
457 }
458 }
459
460
461 void GLAPIENTRY
462 gluTessBeginPolygon( GLUtesselator *tess, void *data )
463 {
464 RequireState( tess, T_DORMANT );
465
466 tess->state = T_IN_POLYGON;
467 tess->cacheCount = 0;
468 tess->emptyCache = FALSE;
469 tess->mesh = NULL;
470
471 tess->polygonData= data;
472 }
473
474
475 void GLAPIENTRY
476 gluTessBeginContour( GLUtesselator *tess )
477 {
478 RequireState( tess, T_IN_POLYGON );
479
480 tess->state = T_IN_CONTOUR;
481 tess->lastEdge = NULL;
482 if( tess->cacheCount > 0 ) {
483 /* Just set a flag so we don't get confused by empty contours
484 * -- these can be generated accidentally with the obsolete
485 * NextContour() interface.
486 */
487 tess->emptyCache = TRUE;
488 }
489 }
490
491
492 void GLAPIENTRY
493 gluTessEndContour( GLUtesselator *tess )
494 {
495 RequireState( tess, T_IN_CONTOUR );
496 tess->state = T_IN_POLYGON;
497 }
498
499 void GLAPIENTRY
500 gluTessEndPolygon( GLUtesselator *tess )
501 {
502 GLUmesh *mesh;
503
504 if (setjmp(tess->env) != 0) {
505 /* come back here if out of memory */
506 CALL_ERROR_OR_ERROR_DATA( GLU_OUT_OF_MEMORY );
507 return;
508 }
509
510 RequireState( tess, T_IN_POLYGON );
511 tess->state = T_DORMANT;
512
513 if( tess->mesh == NULL ) {
514 if( ! tess->flagBoundary && tess->callMesh == &noMesh ) {
515
516 /* Try some special code to make the easy cases go quickly
517 * (eg. convex polygons). This code does NOT handle multiple contours,
518 * intersections, edge flags, and of course it does not generate
519 * an explicit mesh either.
520 */
521 if( __gl_renderCache( tess )) {
522 tess->polygonData= NULL;
523 return;
524 }
525 }
526 if ( !EmptyCache( tess ) ) longjmp(tess->env,1); /* could've used a label*/
527 }
528
529 /* Determine the polygon normal and project vertices onto the plane
530 * of the polygon.
531 */
532 __gl_projectPolygon( tess );
533
534 /* __gl_computeInterior( tess ) computes the planar arrangement specified
535 * by the given contours, and further subdivides this arrangement
536 * into regions. Each region is marked "inside" if it belongs
537 * to the polygon, according to the rule given by tess->windingRule.
538 * Each interior region is guaranteed be monotone.
539 */
540 if ( !__gl_computeInterior( tess ) ) {
541 longjmp(tess->env,1); /* could've used a label */
542 }
543
544 mesh = tess->mesh;
545 if( ! tess->fatalError ) {
546 int rc = 1;
547
548 /* If the user wants only the boundary contours, we throw away all edges
549 * except those which separate the interior from the exterior.
550 * Otherwise we tessellate all the regions marked "inside".
551 */
552 if( tess->boundaryOnly ) {
553 rc = __gl_meshSetWindingNumber( mesh, 1, TRUE );
554 } else {
555 rc = __gl_meshTessellateInterior( mesh );
556 }
557 if (rc == 0) longjmp(tess->env,1); /* could've used a label */
558
559 __gl_meshCheckMesh( mesh );
560
561 if( tess->callBegin != &noBegin || tess->callEnd != &noEnd
562 || tess->callVertex != &noVertex || tess->callEdgeFlag != &noEdgeFlag
563 || tess->callBeginData != &__gl_noBeginData
564 || tess->callEndData != &__gl_noEndData
565 || tess->callVertexData != &__gl_noVertexData
566 || tess->callEdgeFlagData != &__gl_noEdgeFlagData )
567 {
568 if( tess->boundaryOnly ) {
569 __gl_renderBoundary( tess, mesh ); /* output boundary contours */
570 } else {
571 __gl_renderMesh( tess, mesh ); /* output strips and fans */
572 }
573 }
574 if( tess->callMesh != &noMesh ) {
575
576 /* Throw away the exterior faces, so that all faces are interior.
577 * This way the user doesn't have to check the "inside" flag,
578 * and we don't need to even reveal its existence. It also leaves
579 * the freedom for an implementation to not generate the exterior
580 * faces in the first place.
581 */
582 __gl_meshDiscardExterior( mesh );
583 (*tess->callMesh)( mesh ); /* user wants the mesh itself */
584 tess->mesh = NULL;
585 tess->polygonData= NULL;
586 return;
587 }
588 }
589 __gl_meshDeleteMesh( mesh );
590 tess->polygonData= NULL;
591 tess->mesh = NULL;
592 }
593
594
595 /*XXXblythe unused function*/
596 #if 0
597 void GLAPIENTRY
598 gluDeleteMesh( GLUmesh *mesh )
599 {
600 __gl_meshDeleteMesh( mesh );
601 }
602 #endif
603
604
605
606 /*******************************************************/
607
608 /* Obsolete calls -- for backward compatibility */
609
610 void GLAPIENTRY
611 gluBeginPolygon( GLUtesselator *tess )
612 {
613 gluTessBeginPolygon( tess, NULL );
614 gluTessBeginContour( tess );
615 }
616
617
618 /*ARGSUSED*/
619 void GLAPIENTRY
620 gluNextContour( GLUtesselator *tess, GLenum type )
621 {
622 gluTessEndContour( tess );
623 gluTessBeginContour( tess );
624 }
625
626
627 void GLAPIENTRY
628 gluEndPolygon( GLUtesselator *tess )
629 {
630 gluTessEndContour( tess );
631 gluTessEndPolygon( tess );
632 }