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