root/OpenSceneGraph/trunk/src/osg/glu/libtess/tess.cpp @ 11818

Revision 11818, 17.2 kB (checked in by robert, 4 years ago)

Removed usage gluos.h and redundent gluint.h

Line 
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) */
83typedef 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
91GLUtesselator * GLAPIENTRY
92gluNewTess( 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
140static 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
154static 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
192void GLAPIENTRY
193gluDeleteTess( GLUtesselator *tess )
194{
195  RequireState( tess, T_DORMANT );
196  memFree( tess );
197}
198
199
200void GLAPIENTRY
201gluTessProperty( 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 */
239void GLAPIENTRY
240gluGetTessProperty( 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
267void GLAPIENTRY
268gluTessNormal( 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
275void GLAPIENTRY
276gluTessCallback( 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
345static 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
384static 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
396static 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
414void GLAPIENTRY
415gluTessVertex( 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
461void GLAPIENTRY
462gluTessBeginPolygon( 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
475void GLAPIENTRY
476gluTessBeginContour( 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
492void GLAPIENTRY
493gluTessEndContour( GLUtesselator *tess )
494{
495  RequireState( tess, T_IN_CONTOUR );
496  tess->state = T_IN_POLYGON;
497}
498
499void GLAPIENTRY
500gluTessEndPolygon( 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
597void GLAPIENTRY
598gluDeleteMesh( GLUmesh *mesh )
599{
600  __gl_meshDeleteMesh( mesh );
601}
602#endif
603
604
605
606/*******************************************************/
607
608/* Obsolete calls -- for backward compatibility */
609
610void GLAPIENTRY
611gluBeginPolygon( GLUtesselator *tess )
612{
613  gluTessBeginPolygon( tess, NULL );
614  gluTessBeginContour( tess );
615}
616
617
618/*ARGSUSED*/
619void GLAPIENTRY
620gluNextContour( GLUtesselator *tess, GLenum type )
621{
622  gluTessEndContour( tess );
623  gluTessBeginContour( tess );
624}
625
626
627void GLAPIENTRY
628gluEndPolygon( GLUtesselator *tess )
629{
630  gluTessEndContour( tess );
631  gluTessEndPolygon( tess );
632}
Note: See TracBrowser for help on using the browser.