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:
10 ** http://oss.sgi.com/projects/FreeB
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.
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.
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.
36 ** Author: Eric Veach, July 1994.
38 ** $Date$ $Revision: 1.1 $
39 ** $Header: /cygdrive/c/RCVS/CVS/ReactOS/reactos/lib/glu32/libtess/tessmono.c,v 1.1 2004/02/02 16:39:15 navaraf Exp $
49 #define AddWinding(eDst,eSrc) (eDst->winding += eSrc->winding, \
50 eDst->Sym->winding += eSrc->Sym->winding)
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.
58 * Tessellation consists of adding interior edges (actually pairs of
59 * half-edges), to split the region into non-overlapping triangles.
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,
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.
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).
79 int __gl_meshTessellateMonoRegion( GLUface
*face
)
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.
89 assert( up
->Lnext
!= up
&& up
->Lnext
->Lnext
!= up
);
91 for( ; VertLeq( up
->Dst
, up
->Org
); up
= up
->Lprev
)
93 for( ; VertLeq( up
->Org
, up
->Dst
); up
= up
->Lnext
)
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.
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
;
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
;
122 /* Now lo->Org == up->Dst == the leftmost vertex. The remaining region
123 * can be tessellated in a fan from this leftmost vertex.
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
;
136 /* __gl_meshTessellateInterior( mesh ) tessellates each region of
137 * the mesh which is marked "inside" the polygon. Each such region
140 int __gl_meshTessellateInterior( GLUmesh
*mesh
)
145 for( f
= mesh
->fHead
.next
; f
!= &mesh
->fHead
; f
= next
) {
146 /* Make sure we don''t try to tessellate the new triangles. */
149 if ( !__gl_meshTessellateMonoRegion( f
) ) return 0;
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.
162 void __gl_meshDiscardExterior( GLUmesh
*mesh
)
167 for( f
= mesh
->fHead
.next
; f
!= &mesh
->fHead
; f
= next
) {
168 /* Since f will be destroyed, save its next pointer. */
171 __gl_meshZapFace( f
);
176 #define MARKED_FOR_DELETION 0x7fffffff
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.
183 * If keepOnlyBoundary is TRUE, it also deletes all edges which do not
184 * separate an interior region from an exterior one.
186 int __gl_meshSetWindingNumber( GLUmesh
*mesh
, int value
,
187 GLboolean keepOnlyBoundary
)
189 GLUhalfEdge
*e
, *eNext
;
191 for( e
= mesh
->eHead
.next
; e
!= &mesh
->eHead
; e
= eNext
) {
193 if( e
->Rface
->inside
!= e
->Lface
->inside
) {
195 /* This is a boundary edge (one side is interior, one is exterior). */
196 e
->winding
= (e
->Lface
->inside
) ? value
: -value
;
199 /* Both regions are interior, or both are exterior. */
200 if( ! keepOnlyBoundary
) {
203 if ( !__gl_meshDelete( e
) ) return 0;