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