ReactOS  0.4.12-dev-90-g2e2e63e
monoPolyPart.cc
Go to the documentation of this file.
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  */
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  */
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  */
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 
#define C(name, bit)
Definition: cpu.h:208
void connectDiagonal_2slines(directedLine *v1, directedLine *v2, directedLine **ret_p1, directedLine **ret_p2, directedLine *list)
static Int is_u_maximal(directedLine *v)
Definition: monoPolyPart.cc:56
Real * head()
struct outqueuenode * head
Definition: adnsresfilter.c:66
directedLine * monoPolyPart(directedLine *polygon)
Definition: monoPolyPart.cc:80
#define B(row, col)
Definition: m_matrix.c:146
directedLine * getPrev()
Definition: directedLine.h:73
Int compV2InY(Real A[2], Real B[2])
directedLine * insertPolygon(directedLine *newpolygon)
directedLine * getNext()
Definition: directedLine.h:74
static Int is_u_minimal(directedLine *v)
Definition: monoPolyPart.cc:68
smooth NULL
Definition: ftsmooth.c:416
Int compV2InX(Real A[2], Real B[2])
#define A(row, col)
Definition: m_matrix.c:145
int ret
static const WCHAR E[]
Definition: oid.c:1090
#define G(x, y, z)
Definition: md5.c:52
#define D(name, bit)
const GLdouble * v
Definition: gl.h:2040
#define H
#define F(x, y, z)
Definition: md5.c:51
int Int
Definition: definitions.h:37