GLU/tessmono.c

   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 <stdlib.h>
  37 #include "geom.h"
  38 #include "mesh.h"
  39 #include "tessmono.h"
  40 #include <assert.h>
  41
  42 #define AddWinding(eDst,eSrc)   (eDst->winding += eSrc->winding, \
  43                                  eDst->Sym->winding += eSrc->Sym->winding)
  44
  45 /* __gl_meshTessellateMonoRegion( face ) tessellates a monotone region
  46  * (what else would it do??)  The region must consist of a single
  47  * loop of half-edges (see mesh.h) oriented CCW.  "Monotone" in this
  48  * case means that any vertical line intersects the interior of the
  49  * region in a single interval.
  50  *
  51  * Tessellation consists of adding interior edges (actually pairs of
  52  * half-edges), to split the region into non-overlapping triangles.
  53  *
  54  * The basic idea is explained in Preparata and Shamos (which I don''t
  55  * have handy right now), although their implementation is more
  56  * complicated than this one.  The are two edge chains, an upper chain
  57  * and a lower chain.  We process all vertices from both chains in order,
  58  * from right to left.
  59  *
  60  * The algorithm ensures that the following invariant holds after each
  61  * vertex is processed: the untessellated region consists of two
  62  * chains, where one chain (say the upper) is a single edge, and
  63  * the other chain is concave.  The left vertex of the single edge
  64  * is always to the left of all vertices in the concave chain.
  65  *
  66  * Each step consists of adding the rightmost unprocessed vertex to one
  67  * of the two chains, and forming a fan of triangles from the rightmost
  68  * of two chain endpoints.  Determining whether we can add each triangle
  69  * to the fan is a simple orientation test.  By making the fan as large
  70  * as possible, we restore the invariant (check it yourself).
  71  */
  72 int __gl_meshTessellateMonoRegion( GLUface *face )
  73 {
  74   GLUhalfEdge *up, *lo;
  75
  76   /* All edges are oriented CCW around the boundary of the region.
  77    * First, find the half-edge whose origin vertex is rightmost.
  78    * Since the sweep goes from left to right, face->anEdge should
  79    * be close to the edge we want.
  80    */
  81   up = face->anEdge;
  82   assert( up->Lnext != up && up->Lnext->Lnext != up );
  83
  84   for( ; VertLeq( up->Dst, up->Org ); up = up->Lprev )
  85     ;
  86   for( ; VertLeq( up->Org, up->Dst ); up = up->Lnext )
  87     ;
  88   lo = up->Lprev;
  89
  90   while( up->Lnext != lo ) {
  91     if( VertLeq( up->Dst, lo->Org )) {
  92       /* up->Dst is on the left.  It is safe to form triangles from lo->Org.
  93        * The EdgeGoesLeft test guarantees progress even when some triangles
  94        * are CW, given that the upper and lower chains are truly monotone.
  95        */
  96       while( lo->Lnext != up && (EdgeGoesLeft( lo->Lnext )
  97              || EdgeSign( lo->Org, lo->Dst, lo->Lnext->Dst ) <= 0 )) {
  98         GLUhalfEdge *tempHalfEdge= __gl_meshConnect( lo->Lnext, lo );
  99         if (tempHalfEdge == NULL) return 0;
 100         lo = tempHalfEdge->Sym;
 101       }
 102       lo = lo->Lprev;
 103     } else {
 104       /* lo->Org is on the left.  We can make CCW triangles from up->Dst. */
 105       while( lo->Lnext != up && (EdgeGoesRight( up->Lprev )
 106              || EdgeSign( up->Dst, up->Org, up->Lprev->Org ) >= 0 )) {
 107         GLUhalfEdge *tempHalfEdge= __gl_meshConnect( up, up->Lprev );
 108         if (tempHalfEdge == NULL) return 0;
 109         up = tempHalfEdge->Sym;
 110       }
 111       up = up->Lnext;
 112     }
 113   }
 114
 115   /* Now lo->Org == up->Dst == the leftmost vertex.  The remaining region
 116    * can be tessellated in a fan from this leftmost vertex.
 117    */
 118   assert( lo->Lnext != up );
 119   while( lo->Lnext->Lnext != up ) {
 120     GLUhalfEdge *tempHalfEdge= __gl_meshConnect( lo->Lnext, lo );
 121     if (tempHalfEdge == NULL) return 0;
 122     lo = tempHalfEdge->Sym;
 123   }
 124
 125   return 1;
 126 }
 127
 128
 129 /* __gl_meshTessellateInterior( mesh ) tessellates each region of
 130  * the mesh which is marked "inside" the polygon.  Each such region
 131  * must be monotone.
 132  */
 133 int __gl_meshTessellateInterior( GLUmesh *mesh )
 134 {
 135   GLUface *f, *next;
 136
 137   /*LINTED*/
 138   for( f = mesh->fHead.next; f != &mesh->fHead; f = next ) {
 139     /* Make sure we don''t try to tessellate the new triangles. */
 140     next = f->next;
 141     if( f->inside ) {
 142       if ( !__gl_meshTessellateMonoRegion( f ) ) return 0;
 143     }
 144   }
 145
 146   return 1;
 147 }
 148
 149
 150 /* __gl_meshDiscardExterior( mesh ) zaps (ie. sets to NULL) all faces
 151  * which are not marked "inside" the polygon.  Since further mesh operations
 152  * on NULL faces are not allowed, the main purpose is to clean up the
 153  * mesh so that exterior loops are not represented in the data structure.
 154  */
 155 void __gl_meshDiscardExterior( GLUmesh *mesh )
 156 {
 157   GLUface *f, *next;
 158
 159   /*LINTED*/
 160   for( f = mesh->fHead.next; f != &mesh->fHead; f = next ) {
 161     /* Since f will be destroyed, save its next pointer. */
 162     next = f->next;
 163     if( ! f->inside ) {
 164       __gl_meshZapFace( f );
 165     }
 166   }
 167 }
 168
 169 #define MARKED_FOR_DELETION     0x7fffffff
 170
 171 /* __gl_meshSetWindingNumber( mesh, value, keepOnlyBoundary ) resets the
 172  * winding numbers on all edges so that regions marked "inside" the
 173  * polygon have a winding number of "value", and regions outside
 174  * have a winding number of 0.
 175  *
 176  * If keepOnlyBoundary is TRUE, it also deletes all edges which do not
 177  * separate an interior region from an exterior one.
 178  */
 179 int __gl_meshSetWindingNumber( GLUmesh *mesh, int value,
 180                                 GLboolean keepOnlyBoundary )
 181 {
 182   GLUhalfEdge *e, *eNext;
 183
 184   for( e = mesh->eHead.next; e != &mesh->eHead; e = eNext ) {
 185     eNext = e->next;
 186     if( e->Rface->inside != e->Lface->inside ) {
 187
 188       /* This is a boundary edge (one side is interior, one is exterior). */
 189       e->winding = (e->Lface->inside) ? value : -value;
 190     } else {
 191
 192       /* Both regions are interior, or both are exterior. */
 193       if( ! keepOnlyBoundary ) {
 194         e->winding = 0;
 195       } else {
 196         if ( !__gl_meshDelete( e ) ) return 0;
 197       }
 198     }
 199   }
 200   return 1;
 201 }