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 *monoPolyPart.C
37 *
38 *To partition a v-monotone polygon into some uv-monotone polygons.
39 *The algorithm is different from the general monotone partition algorithm.
40 *while the general monotone partition algorithm works for this special case,
41 *but it is more expensive (O(nlogn)). The algorithm implemented here takes
42 *advantage of the fact that the input is a v-monotone polygon and it is
43 *conceptually simpler and computationally cheaper (a linear time algorithm).
44 *The algorithm is described in Zicheng Liu's paper
45 * "Quality-Oriented Linear Time Tessellation".
46 */
47
48 #include <stdlib.h>
49 //#include <stdio.h>
50 #include "directedLine.h"
51 //#include "monoPolyPart.h"
52
53 /*a vertex is u_maximal if both of its two neightbors are to the left of this
54 *vertex
55 */
is_u_maximal(directedLine * v)56 static Int is_u_maximal(directedLine* v)
57 {
58 if (compV2InX(v->getPrev()->head(), v->head()) == -1 &&
59 compV2InX(v->getNext()->head(), v->head()) == -1)
60 return 1;
61 else
62 return 0;
63 }
64
65 /*a vertex is u_minimal if both of its two neightbors are to the right of this
66 *vertex
67 */
is_u_minimal(directedLine * v)68 static Int is_u_minimal(directedLine* v)
69 {
70 if (compV2InX(v->getPrev()->head(), v->head()) == 1 &&
71 compV2InX(v->getNext()->head(), v->head()) == 1)
72 return 1;
73 else
74 return 0;
75 }
76
77 /*poly: a v-monotone polygon
78 *return: a linked list of uv-monotone polygons.
79 */
monoPolyPart(directedLine * polygon)80 directedLine* monoPolyPart(directedLine* polygon)
81 {
82 //handle special cases:
83 if(polygon == NULL)
84 return NULL;
85 if(polygon->getPrev() == polygon)
86 return polygon;
87 if(polygon->getPrev() == polygon->getNext())
88 return polygon;
89 if(polygon->getPrev()->getPrev() == polygon->getNext())
90 return polygon;
91
92 //find the top and bottom vertexes
93 directedLine *tempV, *topV, *botV;
94 topV = botV = polygon;
95 for(tempV = polygon->getNext(); tempV != polygon; tempV = tempV->getNext())
96 {
97 if(compV2InY(topV->head(), tempV->head())<0) {
98 topV = tempV;
99 }
100 if(compV2InY(botV->head(), tempV->head())>0) {
101 botV = tempV;
102 }
103 }
104
105 //initilization
106 directedLine *A, *B, *C, *D, *G, *H;
107 //find A:the first u_maximal vertex on the left chain
108 //and C: the left most vertex between top and A
109 A = NULL;
110 C = topV;
111 for(tempV=topV->getNext(); tempV != botV; tempV = tempV->getNext())
112 {
113 if(tempV->head()[0] < C->head()[0])
114 C = tempV;
115
116 if(is_u_maximal(tempV))
117 {
118 A = tempV;
119 break;
120 }
121 }
122 if(A == NULL)
123 {
124 A = botV;
125 if(A->head()[0] < C->head()[0])
126 C = A;
127 }
128
129 //find B: the first u_minimal vertex on the right chain
130 //and D: the right most vertex between top and B
131 B = NULL;
132 D = topV;
133 for(tempV=topV->getPrev(); tempV != botV; tempV = tempV->getPrev())
134 {
135 if(tempV->head()[0] > D->head()[0])
136 D = tempV;
137 if(is_u_minimal(tempV))
138 {
139 B = tempV;
140 break;
141 }
142 }
143 if(B == NULL)
144 {
145 B = botV;
146 if(B->head()[0] > D->head()[0])
147 D = B;
148 }
149
150 //error checking XXX
151 if(C->head()[0] >= D->head()[0])
152 return polygon;
153
154 //find G on the left chain that is right above B
155 for(tempV=topV; compV2InY(tempV->head(), B->head()) == 1; tempV=tempV->getNext());
156 G = tempV->getPrev();
157 //find H on the right chain that is right above A
158 for(tempV=topV; compV2InY(tempV->head(), A->head()) == 1; tempV = tempV->getPrev());
159 H = tempV->getNext();
160
161 //Main Loop
162 directedLine* ret = NULL;
163 directedLine* currentPolygon = polygon;
164 while(1)
165 {
166 //if both B and D are equal to botV, then this polygon is already
167 //u-monotone
168 if(A == botV && B == botV)
169 {
170 ret = currentPolygon->insertPolygon(ret);
171 return ret;
172 }
173 else //not u-monotone
174 {
175 directedLine *ret_p1, *ret_p2;
176 if(compV2InY(A->head(),B->head()) == 1) //A is above B
177 {
178 directedLine* E = NULL;
179 for(tempV = C; tempV != D; tempV = tempV->getPrev())
180 {
181 if(tempV->head()[0] >= A->head()[0])
182 {
183 E = tempV;
184 break;
185 }
186 }
187
188 if(E == NULL)
189 E = D;
190 if(E->head()[0]> H->head()[0])
191 E = H;
192 //connect AE and output polygon ECA
193 polygon->connectDiagonal_2slines(A, E,
194 &ret_p1,
195 &ret_p2,
196 NULL);
197 ret = ret_p2->insertPolygon(ret);
198 currentPolygon = ret_p1;
199
200 if(E == D)
201 D = ret_p1;
202 if(E == H)
203 H = ret_p1;
204 if(G->head()[1] >= A->head()[1])
205 G = A;
206 //update A to be the next u-maxiaml vertex on left chain
207 //and C the leftmost vertex between the old A and the new A
208 C = A;
209 for(tempV = A->getNext(); tempV != botV; tempV = tempV->getNext())
210 {
211
212 if(tempV->head()[0] < C->head()[0])
213 C = tempV;
214 if(is_u_maximal(tempV))
215 {
216 A = tempV;
217 break;
218 }
219 }
220
221 if(tempV == botV)
222 {
223 A = botV;
224 if(botV->head()[0] < C->head()[0])
225 C = botV;
226 }
227 //update H
228
229 if(A == botV)
230 H = botV;
231 else
232 {
233 for(tempV = H; compV2InY(tempV->head(), A->head()) == 1; tempV = tempV->getPrev());
234 H = tempV->getNext();
235 }
236
237 }
238 else //A is below B
239 {
240
241 directedLine* F = NULL;
242 for(tempV = D; tempV != C; tempV = tempV->getNext())
243 {
244 if(tempV->head()[0] <= B->head()[0])
245 {
246 F = tempV;
247 break;
248 }
249 }
250 if(F == NULL)
251 F = C;
252 if(F->head()[0] < G->head()[0])
253 F = G;
254
255 //connect FB
256 polygon->connectDiagonal_2slines(F, B,
257 &ret_p1,
258 &ret_p2,
259 NULL);
260 ret = ret_p2->insertPolygon(ret);
261 currentPolygon = ret_p1;
262 B = ret_p1;
263 if(H ->head()[1] >= B->head()[1])
264 H = ret_p1;
265
266 //update B to be the next u-minimal vertex on right chain
267 //and D the rightmost vertex between the old B and the new B
268 D = B;
269 for(tempV = B->getPrev(); tempV != botV; tempV = tempV->getPrev())
270 {
271 if(tempV->head()[0] > D->head()[0])
272 D = tempV;
273 if(is_u_minimal(tempV))
274 {
275 B = tempV;
276 break;
277 }
278 }
279 if(tempV == botV)
280 {
281 B = botV;
282 if(botV->head()[0] > D->head()[0])
283 D = botV;
284 }
285 //update G
286 if(B == botV)
287 G = botV;
288 else
289 {
290 for(tempV = G; compV2InY(tempV->head(), B->head()) == 1; tempV = tempV->getNext());
291 G = tempV->getPrev();
292 }
293 } //end of A is below B
294 } //end not u-monotone
295 } //end of main loop
296 }
297
298
299
300