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