monoPolyPart.cc revision f220fa62 
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 */
56static 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 */
68static 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 */
80directedLine* 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