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

Revision 11829, 16.6 kB (checked in by robert, 4 years ago)

Introduced osg namespace to new local GLU functions

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
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) */
84typedef 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
92GLUtesselator * GLAPIENTRY
93osg::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
141static 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
155static 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
193void GLAPIENTRY
194osg::gluDeleteTess( GLUtesselator *tess )
195{
196  RequireState( tess, T_DORMANT );
197  memFree( tess );
198}
199
200
201void GLAPIENTRY
202osg::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 */
240void GLAPIENTRY
241osg::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
268void GLAPIENTRY
269osg::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
276void GLAPIENTRY
277osg::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
346static 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
385static 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
397static 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
415void GLAPIENTRY
416osg::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
462void GLAPIENTRY
463osg::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
476void GLAPIENTRY
477osg::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
493void GLAPIENTRY
494osg::gluTessEndContour( GLUtesselator *tess )
495{
496  RequireState( tess, T_IN_CONTOUR );
497  tess->state = T_IN_POLYGON;
498}
499
500void GLAPIENTRY
501osg::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}
Note: See TracBrowser for help on using the browser.