ReactOS 0.4.15-dev-7842-g558ab78
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;
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
159void 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
253void 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 */
303void 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 tmeshvert(GridTrimVertex *)
Definition: backend.cc:269
void bgntfan()
Definition: backend.cc:185
void endtfan()
Definition: backend.cc:197
Definition: _queue.h:67
void outputFan(Real v[2], primStream *pStream)
void processNewVertex(Real v[2], primStream *pStream)
Real ** getArray()
void appendVertex(Real *ptr)
int Int
Definition: definitions.h:37
float Real
Definition: definitions.h:36
Int compV2InY(Real A[2], Real B[2])
#define NULL
Definition: types.h:112
class Arc * Arc_ptr
Definition: arc.h:50
#define assert(x)
Definition: debug.h:53
const GLdouble * v
Definition: gl.h:2040
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
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)
void monoTriangulationRec(Real *topVertex, Real *botVertex, vertexArray *inc_chain, Int inc_current, vertexArray *dec_chain, Int dec_current, Backend *backend)
void monoTriangulationRecFunBackend(Real *topVertex, Real *botVertex, vertexArray *inc_chain, Int inc_current, vertexArray *dec_chain, Int dec_current, Int(*compFun)(Real *, Real *), Backend *backend)
int k
Definition: mpi.c:3369
Int isReflex(directedLine *v)
Definition: partitionY.cc:122
static Real area(Real A[2], Real B[2], Real C[2])
Definition: polyDBG.cc:50
static int insert
Definition: xmllint.c:138