source: trunk/src/opengl/glu/nurbs/internals/monoTriangulationBackend.cpp

Last change on this file was 2689, checked in by jeroen, 26 years ago

* empty log message *
File size: 12.0 KB
Line 
1/* $Id: monoTriangulationBackend.cpp,v 1.1 2000-02-09 08:50:25 jeroen Exp $ */
2/*
3** License Applicability. Except to the extent portions of this file are
4** made subject to an alternative license as permitted in the SGI Free
5** Software License B, Version 1.0 (the "License"), the contents of this
6** file are subject only to the provisions of the License. You may not use
7** this file except in compliance with the License. You may obtain a copy
8** of the License at Silicon Graphics, Inc., attn: Legal Services, 1600
9** Amphitheatre Parkway, Mountain View, CA 94043-1351, or at:
10**
11** http://oss.sgi.com/projects/FreeB
12**
13** Note that, as provided in the License, the Software is distributed on an
14** "AS IS" basis, with ALL EXPRESS AND IMPLIED WARRANTIES AND CONDITIONS
15** DISCLAIMED, INCLUDING, WITHOUT LIMITATION, ANY IMPLIED WARRANTIES AND
16** CONDITIONS OF MERCHANTABILITY, SATISFACTORY QUALITY, FITNESS FOR A
17** PARTICULAR PURPOSE, AND NON-INFRINGEMENT.
18**
19** Original Code. The Original Code is: OpenGL Sample Implementation,
20** Version 1.2.1, released January 26, 2000, developed by Silicon Graphics,
21** Inc. The Original Code is Copyright (c) 1991-2000 Silicon Graphics, Inc.
22** Copyright in any portions created by third parties is as indicated
23** elsewhere herein. All Rights Reserved.
24**
25** Additional Notice Provisions: The application programming interfaces
26** established by SGI in conjunction with the Original Code are The
27** OpenGL(R) Graphics System: A Specification (Version 1.2.1), released
28** April 1, 1999; The OpenGL(R) Graphics System Utility Library (Version
29** 1.3), released November 4, 1998; and OpenGL(R) Graphics with the X
30** Window System(R) (Version 1.3), released October 19, 1998. This software
31** was created using the OpenGL(R) version 1.2.1 Sample Implementation
32** published by SGI, but has not been independently verified as being
33** compliant with the OpenGL(R) version 1.2.1 Specification.
34**
35** $Date: 2000-02-09 08:50:25 $ $Revision: 1.1 $
36*/
37/*
38** $Header: /home/ktk/tmp/odin/2007/netlabs.cvs/odin32/src/opengl/glu/nurbs/internals/monoTriangulationBackend.cpp,v 1.1 2000-02-09 08:50:25 jeroen Exp $
39*/
40
41#include "monoTriangulation.h"
42#include "polyUtil.h"
43#include "backend.h"
44#include "arc.h"
45
46void reflexChain::outputFan(Real v[2], Backend* backend)
47{
48 Int i;
49 TrimVertex trimVert;
50 backend->bgntfan();
51
52 /*
53 trimVert.param[0]=v[0];
54 trimVert.param[1]=v[1];
55 backend->tmeshvert(&trimVert);
56 */
57 backend->tmeshvert(v[0], v[1]);
58
59 if(isIncreasing) {
60 for(i=0; i<index_queue; i++)
61 {
62 /*
63 trimVert.param[0]=queue[i][0];
64 trimVert.param[1]=queue[i][1];
65 backend->tmeshvert(&trimVert);
66 */
67 backend->tmeshvert(queue[i][0], queue[i][1]);
68 }
69 }
70 else {
71 for(i=index_queue-1; i>=0; i--)
72 {
73 /*
74 trimVert.param[0]=queue[i][0];
75 trimVert.param[1]=queue[i][1];
76 backend->tmeshvert(&trimVert);
77 */
78 backend->tmeshvert(queue[i][0], queue[i][1]);
79 }
80 }
81 backend->endtfan();
82}
83
84void reflexChain::processNewVertex(Real v[2], Backend* backend)
85{
86 Int i,j,k;
87 Int isReflex;
88 TrimVertex trimVert;
89 /*if there are at most one vertex in the queue, then simply insert
90 */
91 if(index_queue <=1){
92 insert(v);
93 return;
94 }
95
96 /*there are at least two vertices in the queue*/
97 j=index_queue-1;
98
99 for(i=j; i>=1; i--) {
100 if(isIncreasing) {
101 isReflex = (area(queue[i-1], queue[i], v) <= 0.0);
102 }
103 else /*decreasing*/{
104 isReflex = (area(v, queue[i], queue[i-1]) <= 0.0);
105 }
106 if(isReflex) {
107 break;
108 }
109 }
110
111 /*
112 *if i<j then vertices: i+1--j are convex
113 * output triangle fan:
114 * v, and queue[i], i+1, ..., j
115 */
116 if(i<j)
117 {
118 backend->bgntfan();
119 /*
120 trimVert.param[0]=v[0];
121 trimVert.param[1]=v[1];
122 backend->tmeshvert(& trimVert);
123 */
124 backend->tmeshvert(v[0], v[1]);
125
126 if(isIncreasing) {
127 for(k=i; k<=j; k++)
128 {
129 /*
130 trimVert.param[0]=queue[k][0];
131 trimVert.param[1]=queue[k][1];
132 backend->tmeshvert(& trimVert);
133 */
134 backend->tmeshvert(queue[k][0], queue[k][1]);
135 }
136 }
137 else {
138 for(k=j; k>=i; k--)
139 {
140 /*
141 trimVert.param[0]=queue[k][0];
142 trimVert.param[1]=queue[k][1];
143 backend->tmeshvert(& trimVert);
144 */
145 backend->tmeshvert(queue[k][0], queue[k][1]);
146 }
147 }
148
149 backend->endtfan();
150 }
151
152 /*delete vertices i+1--j from the queue*/
153 index_queue = i+1;
154 /*finally insert v at the end of the queue*/
155 insert(v);
156
157}
158
159
160void monoTriangulationRec(Real* topVertex, Real* botVertex,
161 vertexArray* inc_chain, Int inc_current,
162 vertexArray* dec_chain, Int dec_current,
163 Backend* backend)
164{
165 assert( inc_chain != NULL && dec_chain != NULL);
166 assert( ! (inc_current>=inc_chain->getNumElements() &&
167 dec_current>=dec_chain->getNumElements()));
168 Int inc_nVertices;
169 Int dec_nVertices;
170 Real** inc_array ;
171 Real** dec_array ;
172 Int i;
173 assert( ! ( (inc_chain==NULL) && (dec_chain==NULL)));
174
175 if(inc_current>=inc_chain->getNumElements()) /*no more vertices on inc_chain*/
176 {
177
178 dec_array = dec_chain->getArray();
179 dec_nVertices = dec_chain->getNumElements();
180 reflexChain rChain(20,0);
181 /*put the top vertex into the reflex chain*/
182 rChain.processNewVertex(topVertex, backend);
183 /*process all the vertices on the dec_chain*/
184 for(i=dec_current; i<dec_nVertices; i++){
185 rChain.processNewVertex(dec_array[i], backend);
186 }
187 /*process the bottom vertex*/
188 rChain.processNewVertex(botVertex, backend);
189
190 }
191 else if(dec_current>= dec_chain->getNumElements()) /*no more vertices on dec_chain*/
192 {
193 inc_array = inc_chain->getArray();
194 inc_nVertices= inc_chain->getNumElements();
195 reflexChain rChain(20,1);
196 /*put the top vertex into the reflex chain*/
197 rChain.processNewVertex(topVertex, backend);
198 /*process all the vertices on the inc_chain*/
199 for(i=inc_current; i<inc_nVertices; i++){
200 rChain.processNewVertex(inc_array[i], backend);
201 }
202 /*process the bottom vertex*/
203 rChain.processNewVertex(botVertex, backend);
204 }
205 else /*neither chain is empty*/
206 {
207 inc_array = inc_chain -> getArray();
208 dec_array = dec_chain -> getArray();
209 inc_nVertices= inc_chain->getNumElements();
210 dec_nVertices= dec_chain->getNumElements();
211 /*if top of inc_chain is 'lower' than top of dec_chain, process all the
212 *vertices on the dec_chain which are higher than top of inc_chain
213 */
214 if(compV2InY(inc_array[inc_current], dec_array[dec_current]) <= 0)
215 {
216
217 reflexChain rChain(20, 0);
218 rChain.processNewVertex(topVertex, backend);
219 for(i=dec_current; i<dec_nVertices; i++)
220 {
221 if(compV2InY(inc_array[inc_current], dec_array[i]) <= 0)
222 rChain.processNewVertex(dec_array[i], backend);
223 else
224 break;
225 }
226 rChain.outputFan(inc_array[inc_current], backend);
227 monoTriangulationRec(dec_array[i-1], botVertex,
228 inc_chain, inc_current,
229 dec_chain, i,
230 backend);
231 }
232 else /*compV2InY(inc_array[inc_current], dec_array[dec_current]) > 0*/
233 {
234
235 reflexChain rChain(20, 1);
236 rChain.processNewVertex(topVertex, backend);
237 for(i=inc_current; i<inc_nVertices; i++)
238 {
239 if(compV2InY(inc_array[i], dec_array[dec_current]) >0)
240 rChain.processNewVertex(inc_array[i], backend);
241 else
242 break;
243 }
244 rChain.outputFan(dec_array[dec_current], backend);
245 monoTriangulationRec(inc_array[i-1], botVertex,
246 inc_chain, i,
247 dec_chain, dec_current,
248 backend);
249 }
250 }/*end case neither is empty*/
251}
252
253
254void monoTriangulationFunBackend(Arc_ptr loop, Int (*compFun)(Real*, Real*), Backend* backend)
255{
256 Int i;
257 /*find the top vertex, bottom vertex, inccreasing chain, and decreasing chain,
258 *then call monoTriangulationRec
259 */
260 Arc_ptr tempV;
261 Arc_ptr topV;
262 Arc_ptr botV;
263 topV = botV = loop;
264 for(tempV = loop->next; tempV != loop; tempV = tempV->next)
265 {
266 if(compFun(topV->tail(), tempV->tail())<0) {
267 topV = tempV;
268 }
269 if(compFun(botV->tail(), tempV->tail())>0) {
270 botV = tempV;
271 }
272 }
273
274 /*creat increase and decrease chains*/
275 vertexArray inc_chain(20); /*this is a dynamic array*/
276 for(i=1; i<=topV->pwlArc->npts-2; i++) { /*the first vertex is the top vertex which doesn't belong to inc_chain*/
277 inc_chain.appendVertex(topV->pwlArc->pts[i].param);
278 }
279 for(tempV = topV->next; tempV != botV; tempV = tempV->next)
280 {
281 for(i=0; i<=tempV->pwlArc->npts-2; i++){
282 inc_chain.appendVertex(tempV->pwlArc->pts[i].param);
283 }
284 }
285
286 vertexArray dec_chain(20);
287 for(tempV = topV->prev; tempV != botV; tempV = tempV->prev)
288 {
289 for(i=tempV->pwlArc->npts-2; i>=0; i--){
290 dec_chain.appendVertex(tempV->pwlArc->pts[i].param);
291 }
292 }
293 for(i=botV->pwlArc->npts-2; i>=1; i--){
294 dec_chain.appendVertex(tempV->pwlArc->pts[i].param);
295 }
296
297 monoTriangulationRecFunBackend(topV->tail(), botV->tail(), &inc_chain, 0, &dec_chain, 0, compFun, backend);
298
299}
300
301/*if compFun == compV2InY, top to bottom: V-monotone
302 *if compFun == compV2InX, right to left: U-monotone
303 */
304void monoTriangulationRecFunBackend(Real* topVertex, Real* botVertex,
305 vertexArray* inc_chain, Int inc_current,
306 vertexArray* dec_chain, Int dec_current,
307 Int (*compFun)(Real*, Real*),
308 Backend* backend)
309{
310 assert( inc_chain != NULL && dec_chain != NULL);
311 assert( ! (inc_current>=inc_chain->getNumElements() &&
312 dec_current>=dec_chain->getNumElements()));
313 Int inc_nVertices;
314 Int dec_nVertices;
315 Real** inc_array ;
316 Real** dec_array ;
317 Int i;
318 assert( ! ( (inc_chain==NULL) && (dec_chain==NULL)));
319
320 if(inc_current>=inc_chain->getNumElements()) /*no more vertices on inc_chain*/
321 {
322
323 dec_array = dec_chain->getArray();
324 dec_nVertices = dec_chain->getNumElements();
325 reflexChain rChain(20,0);
326 /*put the top vertex into the reflex chain*/
327 rChain.processNewVertex(topVertex, backend);
328 /*process all the vertices on the dec_chain*/
329 for(i=dec_current; i<dec_nVertices; i++){
330 rChain.processNewVertex(dec_array[i], backend);
331 }
332 /*process the bottom vertex*/
333 rChain.processNewVertex(botVertex, backend);
334
335 }
336 else if(dec_current>= dec_chain->getNumElements()) /*no more vertices on dec_chain*/
337 {
338 inc_array = inc_chain->getArray();
339 inc_nVertices= inc_chain->getNumElements();
340 reflexChain rChain(20,1);
341 /*put the top vertex into the reflex chain*/
342 rChain.processNewVertex(topVertex, backend);
343 /*process all the vertices on the inc_chain*/
344 for(i=inc_current; i<inc_nVertices; i++){
345 rChain.processNewVertex(inc_array[i], backend);
346 }
347 /*process the bottom vertex*/
348 rChain.processNewVertex(botVertex, backend);
349 }
350 else /*neither chain is empty*/
351 {
352 inc_array = inc_chain -> getArray();
353 dec_array = dec_chain -> getArray();
354 inc_nVertices= inc_chain->getNumElements();
355 dec_nVertices= dec_chain->getNumElements();
356 /*if top of inc_chain is 'lower' than top of dec_chain, process all the
357 *vertices on the dec_chain which are higher than top of inc_chain
358 */
359 if(compFun(inc_array[inc_current], dec_array[dec_current]) <= 0)
360 {
361
362 reflexChain rChain(20, 0);
363 rChain.processNewVertex(topVertex, backend);
364 for(i=dec_current; i<dec_nVertices; i++)
365 {
366 if(compFun(inc_array[inc_current], dec_array[i]) <= 0)
367 rChain.processNewVertex(dec_array[i], backend);
368 else
369 break;
370 }
371 rChain.outputFan(inc_array[inc_current], backend);
372 monoTriangulationRecFunBackend(dec_array[i-1], botVertex,
373 inc_chain, inc_current,
374 dec_chain, i,
375 compFun,
376 backend);
377 }
378 else /*compFun(inc_array[inc_current], dec_array[dec_current]) > 0*/
379 {
380
381 reflexChain rChain(20, 1);
382 rChain.processNewVertex(topVertex, backend);
383 for(i=inc_current; i<inc_nVertices; i++)
384 {
385 if(compFun(inc_array[i], dec_array[dec_current]) >0)
386 rChain.processNewVertex(inc_array[i], backend);
387 else
388 break;
389 }
390 rChain.outputFan(dec_array[dec_current], backend);
391 monoTriangulationRecFunBackend(inc_array[i-1], botVertex,
392 inc_chain, i,
393 dec_chain, dec_current,
394 compFun,
395 backend);
396 }
397 }/*end case neither is empty*/
398}
Note: See TracBrowser for help on using the repository browser.