2 * SGI FREE SOFTWARE LICENSE B (Version 2.0, Sept. 18, 2008)
3 * Copyright (C) 1991-2000 Silicon Graphics, Inc. All Rights Reserved.
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:
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.
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
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.
31 ** Author: Eric Veach, July 1994.
42 #define AddWinding(eDst,eSrc) (eDst->winding += eSrc->winding, \
43 eDst->Sym->winding += eSrc->Sym->winding)
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.
51 * Tessellation consists of adding interior edges (actually pairs of
52 * half-edges), to split the region into non-overlapping triangles.
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,
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.
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).
72 int __gl_meshTessellateMonoRegion( GLUface
*face
)
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.
82 assert( up
->Lnext
!= up
&& up
->Lnext
->Lnext
!= up
);
84 for( ; VertLeq( up
->Dst
, up
->Org
); up
= up
->Lprev
)
86 for( ; VertLeq( up
->Org
, up
->Dst
); up
= up
->Lnext
)
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.
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
;
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
;
115 /* Now lo->Org == up->Dst == the leftmost vertex. The remaining region
116 * can be tessellated in a fan from this leftmost vertex.
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
;
129 /* __gl_meshTessellateInterior( mesh ) tessellates each region of
130 * the mesh which is marked "inside" the polygon. Each such region
133 int __gl_meshTessellateInterior( GLUmesh
*mesh
)
138 for( f
= mesh
->fHead
.next
; f
!= &mesh
->fHead
; f
= next
) {
139 /* Make sure we don''t try to tessellate the new triangles. */
142 if ( !__gl_meshTessellateMonoRegion( f
) ) return 0;
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.
155 void __gl_meshDiscardExterior( GLUmesh
*mesh
)
160 for( f
= mesh
->fHead
.next
; f
!= &mesh
->fHead
; f
= next
) {
161 /* Since f will be destroyed, save its next pointer. */
164 __gl_meshZapFace( f
);
169 #define MARKED_FOR_DELETION 0x7fffffff
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.
176 * If keepOnlyBoundary is TRUE, it also deletes all edges which do not
177 * separate an interior region from an exterior one.
179 int __gl_meshSetWindingNumber( GLUmesh
*mesh
, int value
,
180 GLboolean keepOnlyBoundary
)
182 GLUhalfEdge
*e
, *eNext
;
184 for( e
= mesh
->eHead
.next
; e
!= &mesh
->eHead
; e
= eNext
) {
186 if( e
->Rface
->inside
!= e
->Lface
->inside
) {
188 /* This is a boundary edge (one side is interior, one is exterior). */
189 e
->winding
= (e
->Lface
->inside
) ? value
: -value
;
192 /* Both regions are interior, or both are exterior. */
193 if( ! keepOnlyBoundary
) {
196 if ( !__gl_meshDelete( e
) ) return 0;