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