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 } 202