ReactOS  0.4.13-dev-249-gcba1a2f
monoTriangulationBackend.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 */
37 
38 #include "monoTriangulation.h"
39 #include "polyUtil.h"
40 #include "backend.h"
41 //#include "arc.h"
42 
44 {
45  Int i;
46  /*
47  TrimVertex trimVert;
48  */
49  backend->bgntfan();
50 
51  /*
52  trimVert.param[0]=v[0];
53  trimVert.param[1]=v[1];
54  backend->tmeshvert(&trimVert);
55  */
56  backend->tmeshvert(v[0], v[1]);
57 
58  if(isIncreasing) {
59  for(i=0; i<index_queue; i++)
60  {
61  /*
62  trimVert.param[0]=queue[i][0];
63  trimVert.param[1]=queue[i][1];
64  backend->tmeshvert(&trimVert);
65  */
66  backend->tmeshvert(queue[i][0], queue[i][1]);
67  }
68  }
69  else {
70  for(i=index_queue-1; i>=0; i--)
71  {
72  /*
73  trimVert.param[0]=queue[i][0];
74  trimVert.param[1]=queue[i][1];
75  backend->tmeshvert(&trimVert);
76  */
77  backend->tmeshvert(queue[i][0], queue[i][1]);
78  }
79  }
80  backend->endtfan();
81 }
82 
84 {
85  Int i,j,k;
86  Int isReflex;
87  /*TrimVertex trimVert;*/
88  /*if there are at most one vertex in the queue, then simply insert
89  */
90  if(index_queue <=1){
91  insert(v);
92  return;
93  }
94 
95  /*there are at least two vertices in the queue*/
96  j=index_queue-1;
97 
98  for(i=j; i>=1; i--) {
99  if(isIncreasing) {
100  isReflex = (area(queue[i-1], queue[i], v) <= 0.0);
101  }
102  else /*decreasing*/{
103  isReflex = (area(v, queue[i], queue[i-1]) <= 0.0);
104  }
105  if(isReflex) {
106  break;
107  }
108  }
109 
110  /*
111  *if i<j then vertices: i+1--j are convex
112  * output triangle fan:
113  * v, and queue[i], i+1, ..., j
114  */
115  if(i<j)
116  {
117  backend->bgntfan();
118  /*
119  trimVert.param[0]=v[0];
120  trimVert.param[1]=v[1];
121  backend->tmeshvert(& trimVert);
122  */
123  backend->tmeshvert(v[0], v[1]);
124 
125  if(isIncreasing) {
126  for(k=i; k<=j; k++)
127  {
128  /*
129  trimVert.param[0]=queue[k][0];
130  trimVert.param[1]=queue[k][1];
131  backend->tmeshvert(& trimVert);
132  */
133  backend->tmeshvert(queue[k][0], queue[k][1]);
134  }
135  }
136  else {
137  for(k=j; k>=i; k--)
138  {
139  /*
140  trimVert.param[0]=queue[k][0];
141  trimVert.param[1]=queue[k][1];
142  backend->tmeshvert(& trimVert);
143  */
144  backend->tmeshvert(queue[k][0], queue[k][1]);
145  }
146  }
147 
148  backend->endtfan();
149  }
150 
151  /*delete vertices i+1--j from the queue*/
152  index_queue = i+1;
153  /*finally insert v at the end of the queue*/
154  insert(v);
155 
156 }
157 
158 
159 void monoTriangulationRec(Real* topVertex, Real* botVertex,
160  vertexArray* inc_chain, Int inc_current,
161  vertexArray* dec_chain, Int dec_current,
162  Backend* backend)
163 {
164  assert( inc_chain != NULL && dec_chain != NULL);
165  assert( ! (inc_current>=inc_chain->getNumElements() &&
166  dec_current>=dec_chain->getNumElements()));
167  Int inc_nVertices;
168  Int dec_nVertices;
169  Real** inc_array ;
170  Real** dec_array ;
171  Int i;
172  assert( ! ( (inc_chain==NULL) && (dec_chain==NULL)));
173 
174  if(inc_current>=inc_chain->getNumElements()) /*no more vertices on inc_chain*/
175  {
176 
177  dec_array = dec_chain->getArray();
178  dec_nVertices = dec_chain->getNumElements();
179  reflexChain rChain(20,0);
180  /*put the top vertex into the reflex chain*/
181  rChain.processNewVertex(topVertex, backend);
182  /*process all the vertices on the dec_chain*/
183  for(i=dec_current; i<dec_nVertices; i++){
184  rChain.processNewVertex(dec_array[i], backend);
185  }
186  /*process the bottom vertex*/
187  rChain.processNewVertex(botVertex, backend);
188 
189  }
190  else if(dec_current>= dec_chain->getNumElements()) /*no more vertices on dec_chain*/
191  {
192  inc_array = inc_chain->getArray();
193  inc_nVertices= inc_chain->getNumElements();
194  reflexChain rChain(20,1);
195  /*put the top vertex into the reflex chain*/
196  rChain.processNewVertex(topVertex, backend);
197  /*process all the vertices on the inc_chain*/
198  for(i=inc_current; i<inc_nVertices; i++){
199  rChain.processNewVertex(inc_array[i], backend);
200  }
201  /*process the bottom vertex*/
202  rChain.processNewVertex(botVertex, backend);
203  }
204  else /*neither chain is empty*/
205  {
206  inc_array = inc_chain -> getArray();
207  dec_array = dec_chain -> getArray();
208  inc_nVertices= inc_chain->getNumElements();
209  dec_nVertices= dec_chain->getNumElements();
210  /*if top of inc_chain is 'lower' than top of dec_chain, process all the
211  *vertices on the dec_chain which are higher than top of inc_chain
212  */
213  if(compV2InY(inc_array[inc_current], dec_array[dec_current]) <= 0)
214  {
215 
216  reflexChain rChain(20, 0);
217  rChain.processNewVertex(topVertex, backend);
218  for(i=dec_current; i<dec_nVertices; i++)
219  {
220  if(compV2InY(inc_array[inc_current], dec_array[i]) <= 0)
221  rChain.processNewVertex(dec_array[i], backend);
222  else
223  break;
224  }
225  rChain.outputFan(inc_array[inc_current], backend);
226  monoTriangulationRec(dec_array[i-1], botVertex,
227  inc_chain, inc_current,
228  dec_chain, i,
229  backend);
230  }
231  else /*compV2InY(inc_array[inc_current], dec_array[dec_current]) > 0*/
232  {
233 
234  reflexChain rChain(20, 1);
235  rChain.processNewVertex(topVertex, backend);
236  for(i=inc_current; i<inc_nVertices; i++)
237  {
238  if(compV2InY(inc_array[i], dec_array[dec_current]) >0)
239  rChain.processNewVertex(inc_array[i], backend);
240  else
241  break;
242  }
243  rChain.outputFan(dec_array[dec_current], backend);
244  monoTriangulationRec(inc_array[i-1], botVertex,
245  inc_chain, i,
246  dec_chain, dec_current,
247  backend);
248  }
249  }/*end case neither is empty*/
250 }
251 
252 
253 void monoTriangulationFunBackend(Arc_ptr loop, Int (*compFun)(Real*, Real*), Backend* backend)
254 {
255  Int i;
256  /*find the top vertex, bottom vertex, inccreasing chain, and decreasing chain,
257  *then call monoTriangulationRec
258  */
259  Arc_ptr tempV;
260  Arc_ptr topV;
261  Arc_ptr botV;
262  topV = botV = loop;
263  for(tempV = loop->next; tempV != loop; tempV = tempV->next)
264  {
265  if(compFun(topV->tail(), tempV->tail())<0) {
266  topV = tempV;
267  }
268  if(compFun(botV->tail(), tempV->tail())>0) {
269  botV = tempV;
270  }
271  }
272 
273  /*creat increase and decrease chains*/
274  vertexArray inc_chain(20); /*this is a dynamic array*/
275  for(i=1; i<=topV->pwlArc->npts-2; i++) { /*the first vertex is the top vertex which doesn't belong to inc_chain*/
276  inc_chain.appendVertex(topV->pwlArc->pts[i].param);
277  }
278  for(tempV = topV->next; tempV != botV; tempV = tempV->next)
279  {
280  for(i=0; i<=tempV->pwlArc->npts-2; i++){
281  inc_chain.appendVertex(tempV->pwlArc->pts[i].param);
282  }
283  }
284 
285  vertexArray dec_chain(20);
286  for(tempV = topV->prev; tempV != botV; tempV = tempV->prev)
287  {
288  for(i=tempV->pwlArc->npts-2; i>=0; i--){
289  dec_chain.appendVertex(tempV->pwlArc->pts[i].param);
290  }
291  }
292  for(i=botV->pwlArc->npts-2; i>=1; i--){
293  dec_chain.appendVertex(tempV->pwlArc->pts[i].param);
294  }
295 
296  monoTriangulationRecFunBackend(topV->tail(), botV->tail(), &inc_chain, 0, &dec_chain, 0, compFun, backend);
297 
298 }
299 
300 /*if compFun == compV2InY, top to bottom: V-monotone
301  *if compFun == compV2InX, right to left: U-monotone
302  */
303 void monoTriangulationRecFunBackend(Real* topVertex, Real* botVertex,
304  vertexArray* inc_chain, Int inc_current,
305  vertexArray* dec_chain, Int dec_current,
306  Int (*compFun)(Real*, Real*),
307  Backend* backend)
308 {
309  assert( inc_chain != NULL && dec_chain != NULL);
310  assert( ! (inc_current>=inc_chain->getNumElements() &&
311  dec_current>=dec_chain->getNumElements()));
312  Int inc_nVertices;
313  Int dec_nVertices;
314  Real** inc_array ;
315  Real** dec_array ;
316  Int i;
317  assert( ! ( (inc_chain==NULL) && (dec_chain==NULL)));
318 
319  if(inc_current>=inc_chain->getNumElements()) /*no more vertices on inc_chain*/
320  {
321 
322  dec_array = dec_chain->getArray();
323  dec_nVertices = dec_chain->getNumElements();
324  reflexChain rChain(20,0);
325  /*put the top vertex into the reflex chain*/
326  rChain.processNewVertex(topVertex, backend);
327  /*process all the vertices on the dec_chain*/
328  for(i=dec_current; i<dec_nVertices; i++){
329  rChain.processNewVertex(dec_array[i], backend);
330  }
331  /*process the bottom vertex*/
332  rChain.processNewVertex(botVertex, backend);
333 
334  }
335  else if(dec_current>= dec_chain->getNumElements()) /*no more vertices on dec_chain*/
336  {
337  inc_array = inc_chain->getArray();
338  inc_nVertices= inc_chain->getNumElements();
339  reflexChain rChain(20,1);
340  /*put the top vertex into the reflex chain*/
341  rChain.processNewVertex(topVertex, backend);
342  /*process all the vertices on the inc_chain*/
343  for(i=inc_current; i<inc_nVertices; i++){
344  rChain.processNewVertex(inc_array[i], backend);
345  }
346  /*process the bottom vertex*/
347  rChain.processNewVertex(botVertex, backend);
348  }
349  else /*neither chain is empty*/
350  {
351  inc_array = inc_chain -> getArray();
352  dec_array = dec_chain -> getArray();
353  inc_nVertices= inc_chain->getNumElements();
354  dec_nVertices= dec_chain->getNumElements();
355  /*if top of inc_chain is 'lower' than top of dec_chain, process all the
356  *vertices on the dec_chain which are higher than top of inc_chain
357  */
358  if(compFun(inc_array[inc_current], dec_array[dec_current]) <= 0)
359  {
360 
361  reflexChain rChain(20, 0);
362  rChain.processNewVertex(topVertex, backend);
363  for(i=dec_current; i<dec_nVertices; i++)
364  {
365  if(compFun(inc_array[inc_current], dec_array[i]) <= 0)
366  rChain.processNewVertex(dec_array[i], backend);
367  else
368  break;
369  }
370  rChain.outputFan(inc_array[inc_current], backend);
371  monoTriangulationRecFunBackend(dec_array[i-1], botVertex,
372  inc_chain, inc_current,
373  dec_chain, i,
374  compFun,
375  backend);
376  }
377  else /*compFun(inc_array[inc_current], dec_array[dec_current]) > 0*/
378  {
379 
380  reflexChain rChain(20, 1);
381  rChain.processNewVertex(topVertex, backend);
382  for(i=inc_current; i<inc_nVertices; i++)
383  {
384  if(compFun(inc_array[i], dec_array[dec_current]) >0)
385  rChain.processNewVertex(inc_array[i], backend);
386  else
387  break;
388  }
389  rChain.outputFan(dec_array[dec_current], backend);
390  monoTriangulationRecFunBackend(inc_array[i-1], botVertex,
391  inc_chain, i,
392  dec_chain, dec_current,
393  compFun,
394  backend);
395  }
396  }/*end case neither is empty*/
397 }
void bgntfan()
Definition: backend.cc:185
Int isReflex(directedLine *v)
Definition: partitionY.cc:122
Real ** getArray()
void processNewVertex(Real v[2], primStream *pStream)
void appendVertex(Real *ptr)
#define assert(x)
Definition: debug.h:53
void monoTriangulationRecFunBackend(Real *topVertex, Real *botVertex, vertexArray *inc_chain, Int inc_current, vertexArray *dec_chain, Int dec_current, Int(*compFun)(Real *, Real *), Backend *backend)
void tmeshvert(GridTrimVertex *)
Definition: backend.cc:269
Int compV2InY(Real A[2], Real B[2])
GLsizei GLenum const GLvoid GLsizei GLenum GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLint GLint GLint GLshort GLshort GLshort GLubyte GLubyte GLubyte GLuint GLuint GLuint GLushort GLushort GLushort GLbyte GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLfloat GLint GLint GLint GLint GLshort GLshort GLshort GLshort GLubyte GLubyte GLubyte GLubyte GLuint GLuint GLuint GLuint GLushort GLushort GLushort GLushort GLboolean const GLdouble const GLfloat const GLint const GLshort const GLbyte const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLdouble const GLfloat const GLfloat const GLint const GLint const GLshort const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort GLenum GLenum GLenum GLfloat GLenum GLint GLenum GLenum GLenum GLfloat GLenum GLenum GLint GLenum GLfloat GLenum GLint GLint GLushort GLenum GLenum GLfloat GLenum GLenum GLint GLfloat const GLubyte GLenum GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLint GLint GLsizei GLsizei GLint GLenum GLenum const GLvoid GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLenum const GLdouble GLenum GLenum const GLfloat GLenum GLenum const GLint GLsizei GLuint GLfloat GLuint GLbitfield GLfloat GLint GLuint GLboolean GLenum GLfloat GLenum GLbitfield GLenum GLfloat GLfloat GLint GLint const GLfloat GLenum GLfloat GLfloat GLint GLint GLfloat GLfloat GLint GLint const GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat const GLdouble const GLfloat const GLdouble const GLfloat GLint i
Definition: glfuncs.h:248
void endtfan()
Definition: backend.cc:197
void insert(Real u, Real v)
Definition: _queue.h:59
smooth NULL
Definition: ftsmooth.c:416
void monoTriangulationRec(Real *topVertex, Real *botVertex, vertexArray *inc_chain, Int inc_current, vertexArray *dec_chain, Int dec_current, Backend *backend)
void outputFan(Real v[2], primStream *pStream)
GLsizei GLenum const GLvoid GLsizei GLenum GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLint GLint GLint GLshort GLshort GLshort GLubyte GLubyte GLubyte GLuint GLuint GLuint GLushort GLushort GLushort GLbyte GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLfloat GLint GLint GLint GLint GLshort GLshort GLshort GLshort GLubyte GLubyte GLubyte GLubyte GLuint GLuint GLuint GLuint GLushort GLushort GLushort GLushort GLboolean const GLdouble const GLfloat const GLint const GLshort const GLbyte const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLdouble const GLfloat const GLfloat const GLint const GLint const GLshort const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort GLenum GLenum GLenum GLfloat GLenum GLint GLenum GLenum GLenum GLfloat GLenum GLenum GLint GLenum GLfloat GLenum GLint GLint GLushort GLenum GLenum GLfloat GLenum GLenum GLint GLfloat const GLubyte GLenum GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLint GLint GLsizei GLsizei GLint GLenum GLenum const GLvoid GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLenum const GLdouble GLenum GLenum const GLfloat GLenum GLenum const GLint GLsizei GLuint GLfloat GLuint GLbitfield GLfloat GLint GLuint GLboolean GLenum GLfloat GLenum GLbitfield GLenum GLfloat GLfloat GLint GLint const GLfloat GLenum GLfloat GLfloat GLint GLint GLfloat GLfloat GLint GLint const GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat const GLdouble const GLfloat const GLdouble const GLfloat GLint GLint GLint j
Definition: glfuncs.h:250
void monoTriangulationFunBackend(Arc_ptr loop, Int(*compFun)(Real *, Real *), Backend *backend)
class Arc * Arc_ptr
Definition: arc.h:50
const GLdouble * v
Definition: gl.h:2040
static Real area(Real A[2], Real B[2], Real C[2])
Definition: polyDBG.cc:50
float Real
Definition: definitions.h:36
int k
Definition: mpi.c:3369
int Int
Definition: definitions.h:37