ReactOS  0.4.12-dev-685-gf36cbf7
tessmono.c
Go to the documentation of this file.
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  */
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  */
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  */
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  */
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 }
Definition: mesh.h:163
GLUhalfEdge * Lnext
Definition: mesh.h:142
#define EdgeGoesRight(e)
Definition: geom.h:66
GLUvertex * Org
Definition: mesh.h:143
#define assert(x)
Definition: debug.h:53
GLUface * next
Definition: mesh.h:127
void __gl_meshZapFace(GLUface *fZap)
Definition: mesh.c:555
int __gl_meshDelete(GLUhalfEdge *eDel)
Definition: mesh.c:384
void __gl_meshDiscardExterior(GLUmesh *mesh)
Definition: tessmono.c:155
Definition: mesh.h:126
#define up(mutex)
Definition: glue.h:30
GLUhalfEdge * __gl_meshConnect(GLUhalfEdge *eOrg, GLUhalfEdge *eDst)
Definition: mesh.c:508
#define e
Definition: ke_i.h:82
unsigned char GLboolean
Definition: gl.h:151
GLUface fHead
Definition: mesh.h:165
smooth NULL
Definition: ftsmooth.c:416
GLUhalfEdge eHead
Definition: mesh.h:166
int __gl_meshTessellateInterior(GLUmesh *mesh)
Definition: tessmono.c:133
GLfloat f
Definition: glext.h:7540
#define EdgeGoesLeft(e)
Definition: geom.h:65
GLUhalfEdge * Sym
Definition: mesh.h:140
#define EdgeSign(u, v, w)
Definition: geom.h:55
GLUhalfEdge * next
Definition: mesh.h:139
static unsigned __int64 next
Definition: rand_nt.c:6
#define f
Definition: ke_i.h:83
#define VertLeq(u, v)
Definition: geom.h:50
int __gl_meshSetWindingNumber(GLUmesh *mesh, int value, GLboolean keepOnlyBoundary)
Definition: tessmono.c:179
struct define * next
Definition: wpp.c:35
GLenum GLuint GLint GLenum face
Definition: glext.h:7025
int __gl_meshTessellateMonoRegion(GLUface *face)
Definition: tessmono.c:72