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 */

36 #include <stdlib.h>

40 #include <assert.h>

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.

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 {

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 */

85 ;

87 ;

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 */

101 }

104 /* lo->Org is on the left. We can make CCW triangles from up->Dst. */

110 }

112 }

113 }

115 /* Now lo->Org == up->Dst == the leftmost vertex. The remaining region

116 * can be tessellated in a fan from this leftmost vertex.

117 */

123 }

126 }

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 {

137 /*LINTED*/

139 /* Make sure we don''t try to tessellate the new triangles. */

143 }

144 }

147 }

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 {

159 /*LINTED*/

161 /* Since f will be destroyed, save its next pointer. */

165 }

166 }

167 }

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.

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 {

188 /* This is a boundary edge (one side is interior, one is exterior). */

192 /* Both regions are interior, or both are exterior. */

197 }

198 }

199 }

201 }