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.
34 ** $Date: 2001/03/17 00:25:41 $ $Revision: 1.1 $
39 *To partition a v-monotone polygon into some uv-monotone polygons.
40 *The algorithm is different from the general monotone partition algorithm.
41 *while the general monotone partition algorithm works for this special case,
42 *but it is more expensive (O(nlogn)). The algorithm implemented here takes
43 *advantage of the fact that the input is a v-monotone polygon and it is
44 *conceptually simpler and computationally cheaper (a linear time algorithm).
45 *The algorithm is described in Zicheng Liu's paper
46 * "Quality-Oriented Linear Time Tessellation".
51 #include "directedLine.h"
52 #include "monoPolyPart.h"
54 /*a vertex is u_maximal if both of its two neightbors are to the left of this
57 static Int
is_u_maximal(directedLine
* v
)
59 if (compV2InX(v
->getPrev()->head(), v
->head()) == -1 &&
60 compV2InX(v
->getNext()->head(), v
->head()) == -1)
66 /*a vertex is u_minimal if both of its two neightbors are to the right of this
69 static Int
is_u_minimal(directedLine
* v
)
71 if (compV2InX(v
->getPrev()->head(), v
->head()) == 1 &&
72 compV2InX(v
->getNext()->head(), v
->head()) == 1)
78 /*poly: a v-monotone polygon
79 *return: a linked list of uv-monotone polygons.
81 directedLine
* monoPolyPart(directedLine
* polygon
)
83 //handle special cases:
86 if(polygon
->getPrev() == polygon
)
88 if(polygon
->getPrev() == polygon
->getNext())
90 if(polygon
->getPrev()->getPrev() == polygon
->getNext())
93 //find the top and bottom vertexes
94 directedLine
*tempV
, *topV
, *botV
;
95 topV
= botV
= polygon
;
96 for(tempV
= polygon
->getNext(); tempV
!= polygon
; tempV
= tempV
->getNext())
98 if(compV2InY(topV
->head(), tempV
->head())<0) {
101 if(compV2InY(botV
->head(), tempV
->head())>0) {
107 directedLine
*A
, *B
, *C
, *D
, *G
, *H
;
108 //find A:the first u_maximal vertex on the left chain
109 //and C: the left most vertex between top and A
112 for(tempV
=topV
->getNext(); tempV
!= botV
; tempV
= tempV
->getNext())
114 if(tempV
->head()[0] < C
->head()[0])
117 if(is_u_maximal(tempV
))
126 if(A
->head()[0] < C
->head()[0])
130 //find B: the first u_minimal vertex on the right chain
131 //and D: the right most vertex between top and B
134 for(tempV
=topV
->getPrev(); tempV
!= botV
; tempV
= tempV
->getPrev())
136 if(tempV
->head()[0] > D
->head()[0])
138 if(is_u_minimal(tempV
))
147 if(B
->head()[0] > D
->head()[0])
152 if(C
->head()[0] >= D
->head()[0])
155 //find G on the left chain that is right above B
156 for(tempV
=topV
; compV2InY(tempV
->head(), B
->head()) == 1; tempV
=tempV
->getNext());
157 G
= tempV
->getPrev();
158 //find H on the right chain that is right above A
159 for(tempV
=topV
; compV2InY(tempV
->head(), A
->head()) == 1; tempV
= tempV
->getPrev());
160 H
= tempV
->getNext();
163 directedLine
* ret
= NULL
;
164 directedLine
* currentPolygon
= polygon
;
167 //if both B and D are equal to botV, then this polygon is already
169 if(A
== botV
&& B
== botV
)
171 ret
= currentPolygon
->insertPolygon(ret
);
174 else //not u-monotone
176 directedLine
*ret_p1
, *ret_p2
;
177 if(compV2InY(A
->head(),B
->head()) == 1) //A is above B
179 directedLine
* E
= NULL
;
180 for(tempV
= C
; tempV
!= D
; tempV
= tempV
->getPrev())
182 if(tempV
->head()[0] >= A
->head()[0])
191 if(E
->head()[0]> H
->head()[0])
193 //connect AE and output polygon ECA
194 polygon
->connectDiagonal_2slines(A
, E
,
198 ret
= ret_p2
->insertPolygon(ret
);
199 currentPolygon
= ret_p1
;
205 if(G
->head()[1] >= A
->head()[1])
207 //update A to be the next u-maxiaml vertex on left chain
208 //and C the leftmost vertex between the old A and the new A
210 for(tempV
= A
->getNext(); tempV
!= botV
; tempV
= tempV
->getNext())
213 if(tempV
->head()[0] < C
->head()[0])
215 if(is_u_maximal(tempV
))
225 if(botV
->head()[0] < C
->head()[0])
234 for(tempV
= H
; compV2InY(tempV
->head(), A
->head()) == 1; tempV
= tempV
->getPrev());
235 H
= tempV
->getNext();
242 directedLine
* F
= NULL
;
243 for(tempV
= D
; tempV
!= C
; tempV
= tempV
->getNext())
245 if(tempV
->head()[0] <= B
->head()[0])
253 if(F
->head()[0] < G
->head()[0])
257 polygon
->connectDiagonal_2slines(F
, B
,
261 ret
= ret_p2
->insertPolygon(ret
);
262 currentPolygon
= ret_p1
;
264 if(H
->head()[1] >= B
->head()[1])
267 //update B to be the next u-minimal vertex on right chain
268 //and D the rightmost vertex between the old B and the new B
270 for(tempV
= B
->getPrev(); tempV
!= botV
; tempV
= tempV
->getPrev())
272 if(tempV
->head()[0] > D
->head()[0])
274 if(is_u_minimal(tempV
))
283 if(botV
->head()[0] > D
->head()[0])
291 for(tempV
= G
; compV2InY(tempV
->head(), B
->head()) == 1; tempV
= tempV
->getNext());
292 G
= tempV
->getPrev();
294 } //end of A is below B
295 } //end not u-monotone