source: trunk/src/opengl/glu/tess/tess.c

Last change on this file was 3079, checked in by jeroen, 26 years ago

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