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:
10 ** http://oss.sgi.com/projects/FreeB
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.
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.
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.
38 #include "monoTriangulation.h"
43 void reflexChain::outputFan(Real v
[2], Backend
* backend
)
52 trimVert.param[0]=v[0];
53 trimVert.param[1]=v[1];
54 backend->tmeshvert(&trimVert);
56 backend
->tmeshvert(v
[0], v
[1]);
59 for(i
=0; i
<index_queue
; i
++)
62 trimVert.param[0]=queue[i][0];
63 trimVert.param[1]=queue[i][1];
64 backend->tmeshvert(&trimVert);
66 backend
->tmeshvert(queue
[i
][0], queue
[i
][1]);
70 for(i
=index_queue
-1; i
>=0; i
--)
73 trimVert.param[0]=queue[i][0];
74 trimVert.param[1]=queue[i][1];
75 backend->tmeshvert(&trimVert);
77 backend
->tmeshvert(queue
[i
][0], queue
[i
][1]);
83 void reflexChain::processNewVertex(Real v
[2], Backend
* backend
)
87 /*TrimVertex trimVert;*/
88 /*if there are at most one vertex in the queue, then simply insert
95 /*there are at least two vertices in the queue*/
100 isReflex
= (area(queue
[i
-1], queue
[i
], v
) <= 0.0);
103 isReflex
= (area(v
, queue
[i
], queue
[i
-1]) <= 0.0);
111 *if i<j then vertices: i+1--j are convex
112 * output triangle fan:
113 * v, and queue[i], i+1, ..., j
119 trimVert.param[0]=v[0];
120 trimVert.param[1]=v[1];
121 backend->tmeshvert(& trimVert);
123 backend
->tmeshvert(v
[0], v
[1]);
129 trimVert.param[0]=queue[k][0];
130 trimVert.param[1]=queue[k][1];
131 backend->tmeshvert(& trimVert);
133 backend
->tmeshvert(queue
[k
][0], queue
[k
][1]);
140 trimVert.param[0]=queue[k][0];
141 trimVert.param[1]=queue[k][1];
142 backend->tmeshvert(& trimVert);
144 backend
->tmeshvert(queue
[k
][0], queue
[k
][1]);
151 /*delete vertices i+1--j from the queue*/
153 /*finally insert v at the end of the queue*/
159 void monoTriangulationRec(Real
* topVertex
, Real
* botVertex
,
160 vertexArray
* inc_chain
, Int inc_current
,
161 vertexArray
* dec_chain
, Int dec_current
,
164 assert( inc_chain
!= NULL
&& dec_chain
!= NULL
);
165 assert( ! (inc_current
>=inc_chain
->getNumElements() &&
166 dec_current
>=dec_chain
->getNumElements()));
172 assert( ! ( (inc_chain
==NULL
) && (dec_chain
==NULL
)));
174 if(inc_current
>=inc_chain
->getNumElements()) /*no more vertices on inc_chain*/
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
);
186 /*process the bottom vertex*/
187 rChain
.processNewVertex(botVertex
, backend
);
190 else if(dec_current
>= dec_chain
->getNumElements()) /*no more vertices on dec_chain*/
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
);
201 /*process the bottom vertex*/
202 rChain
.processNewVertex(botVertex
, backend
);
204 else /*neither chain is empty*/
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
213 if(compV2InY(inc_array
[inc_current
], dec_array
[dec_current
]) <= 0)
216 reflexChain
rChain(20, 0);
217 rChain
.processNewVertex(topVertex
, backend
);
218 for(i
=dec_current
; i
<dec_nVertices
; i
++)
220 if(compV2InY(inc_array
[inc_current
], dec_array
[i
]) <= 0)
221 rChain
.processNewVertex(dec_array
[i
], backend
);
225 rChain
.outputFan(inc_array
[inc_current
], backend
);
226 monoTriangulationRec(dec_array
[i
-1], botVertex
,
227 inc_chain
, inc_current
,
231 else /*compV2InY(inc_array[inc_current], dec_array[dec_current]) > 0*/
234 reflexChain
rChain(20, 1);
235 rChain
.processNewVertex(topVertex
, backend
);
236 for(i
=inc_current
; i
<inc_nVertices
; i
++)
238 if(compV2InY(inc_array
[i
], dec_array
[dec_current
]) >0)
239 rChain
.processNewVertex(inc_array
[i
], backend
);
243 rChain
.outputFan(dec_array
[dec_current
], backend
);
244 monoTriangulationRec(inc_array
[i
-1], botVertex
,
246 dec_chain
, dec_current
,
249 }/*end case neither is empty*/
253 void monoTriangulationFunBackend(Arc_ptr loop
, Int (*compFun
)(Real
*, Real
*), Backend
* backend
)
256 /*find the top vertex, bottom vertex, inccreasing chain, and decreasing chain,
257 *then call monoTriangulationRec
263 for(tempV
= loop
->next
; tempV
!= loop
; tempV
= tempV
->next
)
265 if(compFun(topV
->tail(), tempV
->tail())<0) {
268 if(compFun(botV
->tail(), tempV
->tail())>0) {
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
);
278 for(tempV
= topV
->next
; tempV
!= botV
; tempV
= tempV
->next
)
280 for(i
=0; i
<=tempV
->pwlArc
->npts
-2; i
++){
281 inc_chain
.appendVertex(tempV
->pwlArc
->pts
[i
].param
);
285 vertexArray
dec_chain(20);
286 for(tempV
= topV
->prev
; tempV
!= botV
; tempV
= tempV
->prev
)
288 for(i
=tempV
->pwlArc
->npts
-2; i
>=0; i
--){
289 dec_chain
.appendVertex(tempV
->pwlArc
->pts
[i
].param
);
292 for(i
=botV
->pwlArc
->npts
-2; i
>=1; i
--){
293 dec_chain
.appendVertex(tempV
->pwlArc
->pts
[i
].param
);
296 monoTriangulationRecFunBackend(topV
->tail(), botV
->tail(), &inc_chain
, 0, &dec_chain
, 0, compFun
, backend
);
300 /*if compFun == compV2InY, top to bottom: V-monotone
301 *if compFun == compV2InX, right to left: U-monotone
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
*),
309 assert( inc_chain
!= NULL
&& dec_chain
!= NULL
);
310 assert( ! (inc_current
>=inc_chain
->getNumElements() &&
311 dec_current
>=dec_chain
->getNumElements()));
317 assert( ! ( (inc_chain
==NULL
) && (dec_chain
==NULL
)));
319 if(inc_current
>=inc_chain
->getNumElements()) /*no more vertices on inc_chain*/
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
);
331 /*process the bottom vertex*/
332 rChain
.processNewVertex(botVertex
, backend
);
335 else if(dec_current
>= dec_chain
->getNumElements()) /*no more vertices on dec_chain*/
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
);
346 /*process the bottom vertex*/
347 rChain
.processNewVertex(botVertex
, backend
);
349 else /*neither chain is empty*/
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
358 if(compFun(inc_array
[inc_current
], dec_array
[dec_current
]) <= 0)
361 reflexChain
rChain(20, 0);
362 rChain
.processNewVertex(topVertex
, backend
);
363 for(i
=dec_current
; i
<dec_nVertices
; i
++)
365 if(compFun(inc_array
[inc_current
], dec_array
[i
]) <= 0)
366 rChain
.processNewVertex(dec_array
[i
], backend
);
370 rChain
.outputFan(inc_array
[inc_current
], backend
);
371 monoTriangulationRecFunBackend(dec_array
[i
-1], botVertex
,
372 inc_chain
, inc_current
,
377 else /*compFun(inc_array[inc_current], dec_array[dec_current]) > 0*/
380 reflexChain
rChain(20, 1);
381 rChain
.processNewVertex(topVertex
, backend
);
382 for(i
=inc_current
; i
<inc_nVertices
; i
++)
384 if(compFun(inc_array
[i
], dec_array
[dec_current
]) >0)
385 rChain
.processNewVertex(inc_array
[i
], backend
);
389 rChain
.outputFan(dec_array
[dec_current
], backend
);
390 monoTriangulationRecFunBackend(inc_array
[i
-1], botVertex
,
392 dec_chain
, dec_current
,
396 }/*end case neither is empty*/