1/*
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:
9**
10** http://oss.sgi.com/projects/FreeB
11**
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.
17**
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.
23**
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.
33**
34*/
35/*
36** Author: Eric Veach, July 1994.
37**
38** $Date$ $Revision$
39** $Header: //depot/main/gfx/lib/glu/libtess/tessmono.c#5 $
40*/
41
42#include "gluos.h"
43#include <stdlib.h>
44#include "geom.h"
45#include "mesh.h"
46#include "tessmono.h"
47#include <assert.h>
48
49#define AddWinding(eDst,eSrc)	(eDst->winding += eSrc->winding, \
50				 eDst->Sym->winding += eSrc->Sym->winding)
51
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.
57 *
58 * Tessellation consists of adding interior edges (actually pairs of
59 * half-edges), to split the region into non-overlapping triangles.
60 *
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,
65 * from right to left.
66 *
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.
72 *
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).
78 */
79int __gl_meshTessellateMonoRegion( GLUface *face )
80{
81  GLUhalfEdge *up, *lo;
82
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.
87   */
88  up = face->anEdge;
89  assert( up->Lnext != up && up->Lnext->Lnext != up );
90
91  for( ; VertLeq( up->Dst, up->Org ); up = up->Lprev )
92    ;
93  for( ; VertLeq( up->Org, up->Dst ); up = up->Lnext )
94    ;
95  lo = up->Lprev;
96
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.
102       */
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;
108      }
109      lo = lo->Lprev;
110    } else {
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;
117      }
118      up = up->Lnext;
119    }
120  }
121
122  /* Now lo->Org == up->Dst == the leftmost vertex.  The remaining region
123   * can be tessellated in a fan from this leftmost vertex.
124   */
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;
130  }
131
132  return 1;
133}
134
135
136/* __gl_meshTessellateInterior( mesh ) tessellates each region of
137 * the mesh which is marked "inside" the polygon.  Each such region
138 * must be monotone.
139 */
140int __gl_meshTessellateInterior( GLUmesh *mesh )
141{
142  GLUface *f, *next;
143
144  /*LINTED*/
145  for( f = mesh->fHead.next; f != &mesh->fHead; f = next ) {
146    /* Make sure we don''t try to tessellate the new triangles. */
147    next = f->next;
148    if( f->inside ) {
149      if ( !__gl_meshTessellateMonoRegion( f ) ) return 0;
150    }
151  }
152
153  return 1;
154}
155
156
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.
161 */
162void __gl_meshDiscardExterior( GLUmesh *mesh )
163{
164  GLUface *f, *next;
165
166  /*LINTED*/
167  for( f = mesh->fHead.next; f != &mesh->fHead; f = next ) {
168    /* Since f will be destroyed, save its next pointer. */
169    next = f->next;
170    if( ! f->inside ) {
171      __gl_meshZapFace( f );
172    }
173  }
174}
175
176#define MARKED_FOR_DELETION	0x7fffffff
177
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.
182 *
183 * If keepOnlyBoundary is TRUE, it also deletes all edges which do not
184 * separate an interior region from an exterior one.
185 */
186int __gl_meshSetWindingNumber( GLUmesh *mesh, int value,
187			        GLboolean keepOnlyBoundary )
188{
189  GLUhalfEdge *e, *eNext;
190
191  for( e = mesh->eHead.next; e != &mesh->eHead; e = eNext ) {
192    eNext = e->next;
193    if( e->Rface->inside != e->Lface->inside ) {
194
195      /* This is a boundary edge (one side is interior, one is exterior). */
196      e->winding = (e->Lface->inside) ? value : -value;
197    } else {
198
199      /* Both regions are interior, or both are exterior. */
200      if( ! keepOnlyBoundary ) {
201	e->winding = 0;
202      } else {
203	if ( !__gl_meshDelete( e ) ) return 0;
204      }
205    }
206  }
207  return 1;
208}
209