d168374c98a12ed4a86af0f757a9e993d0cad1a3
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.
34 ** $Date: 2006/03/29 18:46:46 $ $Revision: 1.5 $
37 ** $Header: /home/krh/git/sync/mesa-cvs-repo/Mesa/src/glu/sgi/libnurbs/nurbtess/monoTriangulation.cc,v 1.5 2006/03/29 18:46:46 brianp Exp $
43 #include "glimports.h"
46 #include "monoTriangulation.h"
47 #include "polyUtil.h" /*for area*/
48 #include "partitionX.h"
49 #include "monoPolyPart.h"
53 extern directedLine
* polygonConvert(directedLine
* polygon
);
57 void monoTriangulationOpt(directedLine
* poly
, primStream
* pStream
)
60 Int n_edges
= poly
->numEdges();
61 directedLine
** cusps
= (directedLine
**) malloc(sizeof(directedLine
*)*n_edges
);
63 findInteriorCuspsX(poly
, n_cusps
, cusps
);
64 if(n_cusps
==0) //u monotine
66 monoTriangulationFun(poly
, compV2InX
, pStream
);
68 else if(n_cusps
== 1) // one interior cusp
70 directedLine
* new_polygon
= polygonConvert(cusps
[0]);
71 directedLine
* other
= findDiagonal_singleCuspX(new_polygon
);
72 //<other> should NOT be null unless there are self-intersecting
73 //trim curves. In that case, we don't want to core dump, instead,
74 //we triangulate anyway, and print out error message.
77 monoTriangulationFun(poly
, compV2InX
, pStream
);
84 new_polygon
->connectDiagonal_2slines(new_polygon
, other
,
89 monoTriangulationFun(ret_p1
, compV2InX
, pStream
);
90 monoTriangulationFun(ret_p2
, compV2InX
, pStream
);
92 ret_p1
->deleteSinglePolygonWithSline();
93 ret_p2
->deleteSinglePolygonWithSline();
98 //we need a general partitionX funtion (supposed to be in partitionX.C,
99 //not implemented yet. XXX
100 monoTriangulationFun(poly
, compV2InY
, pStream
);
106 void monoTriangulationRecOpt(Real
* topVertex
, Real
* botVertex
,
107 vertexArray
* left_chain
, Int left_current
,
108 vertexArray
* right_chain
, Int right_current
,
112 Int n_left
= left_chain
->getNumElements();
113 Int n_right
= right_chain
->getNumElements();
114 if(left_current
>= n_left
-1 ||
115 right_current
>= n_right
-1)
117 monoTriangulationRec(topVertex
, botVertex
, left_chain
, left_current
,
118 right_chain
, right_current
, pStream
);
121 //now both left and right have at least two vertices each.
122 Real left_v
= left_chain
->getVertex(left_current
)[1];
123 Real right_v
= right_chain
->getVertex(right_current
)[1];
125 if(left_v
<= right_v
) //first left vertex is below right
127 //find the last vertex of right which is above or equal to left
128 for(j
=right_current
; j
<=n_right
-1; j
++)
130 if(right_chain
->getVertex(j
)[1] < left_v
)
133 monoTriangulationRecGen(topVertex
, left_chain
->getVertex(left_current
),
134 left_chain
, left_current
, left_current
,
135 right_chain
, right_current
, j
-1,
137 monoTriangulationRecOpt(right_chain
->getVertex(j
-1),
139 left_chain
, left_current
,
143 else //first right vertex is strictly below left
145 //find the last vertex of left which is strictly above right
146 for(i
=left_current
; i
<=n_left
-1; i
++)
148 if(left_chain
->getVertex(i
)[1] <= right_v
)
151 monoTriangulationRecGen(topVertex
, right_chain
->getVertex(right_current
),
152 left_chain
, left_current
, i
-1,
153 right_chain
, right_current
, right_current
,
155 monoTriangulationRecOpt(left_chain
->getVertex(i
-1),
158 right_chain
, right_current
,
164 void monoTriangulationRecGenTBOpt(Real
* topVertex
, Real
* botVertex
,
165 vertexArray
* inc_chain
, Int inc_current
, Int inc_end
,
166 vertexArray
* dec_chain
, Int dec_current
, Int dec_end
,
169 pStream
->triangle(topVertex
, inc_chain
->getVertex(inc_current
), dec_chain
->getVertex(dec_current
));
171 /*printf("**(%f,%f)\n", inc_chain->getArray()[0][0],inc_chain->getArray()[0][1]);*/
172 triangulateXYMonoTB(inc_end
-inc_current
+1, inc_chain
->getArray()+inc_current
, dec_end
-dec_current
+1, dec_chain
->getArray()+dec_current
, pStream
);
174 pStream
->triangle(botVertex
, dec_chain
->getVertex(dec_end
), inc_chain
->getVertex(inc_end
));
180 *the strip is going top to bottom. compared to the funtion
181 * triangulateXYmono()
183 void triangulateXYMonoTB(Int n_left
, Real
** leftVerts
,
184 Int n_right
, Real
** rightVerts
,
192 assert(n_left
>=1 && n_right
>=1);
193 if(leftVerts
[0][1] >= rightVerts
[0][1])
197 topMostV
= leftVerts
[0];
203 topMostV
= rightVerts
[0];
208 if(i
>= n_left
) /*case1: no more in left*/
211 if(j
<n_right
-1) /*at least two vertices in right*/
214 pStream
->insert(topMostV
);
215 for(k
=n_right
-1; k
>=j
; k
--)
216 pStream
->insert(rightVerts
[j
]);
218 pStream
->end(PRIMITIVE_STREAM_FAN
);
224 else if(j
>= n_right
) /*case2: no more in right*/
227 if(i
<n_left
-1) /*at least two vertices in left*/
230 pStream
->insert(topMostV
);
232 for(k
=i
; k
<n_left
; k
++)
233 pStream
->insert(leftVerts
[k
]);
235 pStream
->end(PRIMITIVE_STREAM_FAN
);
240 else /* case3: neither is empty, plus the topMostV, there is at least one triangle to output*/
243 if(leftVerts
[i
][1] >= rightVerts
[j
][1])
246 pStream
->insert(rightVerts
[j
]); /*the origin of this fan*/
248 pStream
->insert(topMostV
);
250 /*find the last k>=i such that
251 *leftverts[k][1] >= rightverts[j][1]
256 if(leftVerts
[k
][1] < rightVerts
[j
][1])
263 pStream
->insert(leftVerts
[l
]);
266 pStream
->end(PRIMITIVE_STREAM_FAN
);
267 //update i for next loop
269 topMostV
= leftVerts
[k
];
272 else /*leftVerts[i][1] < rightVerts[j][1]*/
275 pStream
->insert(leftVerts
[i
]);/*the origion of this fan*/
277 /*find the last k>=j such that
278 *rightverts[k][1] > leftverts[i][1]*/
282 if(rightVerts
[k
][1] <= leftVerts
[i
][1])
289 pStream
->insert(rightVerts
[l
]);
291 pStream
->insert(topMostV
);
292 pStream
->end(PRIMITIVE_STREAM_FAN
);
294 topMostV
= rightVerts
[j
-1];
300 static int chainConvex(vertexArray
* inc_chain
, Int inc_current
, Int inc_end
)
303 //if there are no more than 2 vertices, return 1
304 if(inc_current
>= inc_end
-1) return 1;
305 for(i
=inc_current
; i
<= inc_end
-2; i
++)
307 if(area(inc_chain
->getVertex(i
), inc_chain
->getVertex(i
+1), inc_chain
->getVertex(i
+2)) <0)
313 static int chainConcave(vertexArray
* dec_chain
, Int dec_current
, Int dec_end
)
316 //if there are no more than 2 vertices, return 1
317 if(dec_current
>= dec_end
-1) return 1;
318 for(i
=dec_current
; i
<=dec_end
-2; i
++)
320 if(area(dec_chain
->getVertex(i
), dec_chain
->getVertex(i
+1), dec_chain
->getVertex(i
+2)) >0)
326 void monoTriangulationRecGenInU(Real
* topVertex
, Real
* botVertex
,
327 vertexArray
* inc_chain
, Int inc_current
, Int inc_end
,
328 vertexArray
* dec_chain
, Int dec_current
, Int dec_end
,
334 void monoTriangulationRecGenOpt(Real
* topVertex
, Real
* botVertex
,
335 vertexArray
* inc_chain
, Int inc_current
, Int inc_end
,
336 vertexArray
* dec_chain
, Int dec_current
, Int dec_end
,
340 //copy this to a polygon: directedLine Lioop
345 if(inc_current
<= inc_end
) //at least one vertex in inc_chain
347 sline
= new sampledLine(topVertex
, inc_chain
->getVertex(inc_current
));
348 poly
= new directedLine(INCREASING
, sline
);
349 for(i
=inc_current
; i
<=inc_end
-1; i
++)
351 sline
= new sampledLine(inc_chain
->getVertex(i
), inc_chain
->getVertex(i
+1));
352 dline
= new directedLine(INCREASING
, sline
);
355 sline
= new sampledLine(inc_chain
->getVertex(inc_end
), botVertex
);
356 dline
= new directedLine(INCREASING
, sline
);
359 else //inc_chian is empty
361 sline
= new sampledLine(topVertex
, botVertex
);
362 dline
= new directedLine(INCREASING
, sline
);
366 assert(poly
!= NULL
);
368 if(dec_current
<= dec_end
) //at least on vertex in dec_Chain
370 sline
= new sampledLine(botVertex
, dec_chain
->getVertex(dec_end
));
371 dline
= new directedLine(INCREASING
, sline
);
373 for(i
=dec_end
; i
>dec_current
; i
--)
375 sline
= new sampledLine(dec_chain
->getVertex(i
), dec_chain
->getVertex(i
-1));
376 dline
= new directedLine(INCREASING
, sline
);
379 sline
= new sampledLine(dec_chain
->getVertex(dec_current
), topVertex
);
380 dline
= new directedLine(INCREASING
, sline
);
383 else //dec_chain is empty
385 sline
= new sampledLine(botVertex
, topVertex
);
386 dline
= new directedLine(INCREASING
, sline
);
392 Int n_edges
= poly
->numEdges();
393 directedLine
** cusps
= (directedLine
**) malloc(sizeof(directedLine
*)*n_edges
);
395 findInteriorCuspsX(poly
, n_cusps
, cusps
);
397 if(n_cusps
==0) //u monotine
399 monoTriangulationFun(poly
, compV2InX
, pStream
);
401 else if(n_cusps
== 1) // one interior cusp
403 directedLine
* new_polygon
= polygonConvert(cusps
[0]);
404 directedLine
* other
= findDiagonal_singleCuspX(new_polygon
);
405 //<other> should NOT be null unless there are self-intersecting
406 //trim curves. In that case, we don't want to core dump, instead,
407 //we triangulate anyway, and print out error message.
410 monoTriangulationFun(poly
, compV2InX
, pStream
);
414 directedLine
* ret_p1
;
415 directedLine
* ret_p2
;
417 new_polygon
->connectDiagonal_2slines(new_polygon
, other
,
422 monoTriangulationFun(ret_p1
, compV2InX
, pStream
);
423 monoTriangulationFun(ret_p2
, compV2InX
, pStream
);
425 ret_p1
->deleteSinglePolygonWithSline();
426 ret_p2
->deleteSinglePolygonWithSline();
431 //we need a general partitionX funtion (supposed to be in partitionX.C,
432 //not implemented yet. XXX
433 //monoTriangulationFun(poly, compV2InY, pStream);
435 directedLine
* new_polygon
= polygonConvert(poly
);
436 directedLine
* list
= monoPolyPart(new_polygon
);
437 for(directedLine
* temp
= list
; temp
!= NULL
; temp
= temp
->getNextPolygon())
439 monoTriangulationFun(temp
, compV2InX
, pStream
);
442 list
->deletePolygonListWithSline();
448 if(numInteriorCuspsX(poly) == 0) //is u monotone
449 monoTriangulationFun(poly, compV2InX, pStream);
450 else //it is not u motone
451 monoTriangulationFun(poly, compV2InY, pStream);
454 poly
->deleteSinglePolygonWithSline();
458 //apparently the following code is not reachable,
459 //it is for test purpose
460 if(inc_current
> inc_end
|| dec_current
>dec_end
)
462 monoTriangulationRecGen(topVertex
, botVertex
, inc_chain
, inc_current
, inc_end
,
463 dec_chain
, dec_current
, dec_end
,
470 area(dec_chain
->getVertex(dec_current
),
472 inc_chain
->getVertex(inc_current
)) >=0
473 && chainConvex(inc_chain
, inc_current
, inc_end
)
474 && chainConcave(dec_chain
, dec_current
, dec_end
)
475 && area(inc_chain
->getVertex(inc_end
), botVertex
, dec_chain
->getVertex(dec_end
)) >=0
478 monoTriangulationRecFunGen(topVertex
, botVertex
,
479 inc_chain
, inc_current
, inc_end
,
480 dec_chain
, dec_current
, dec_end
,
485 monoTriangulationRecGen(topVertex
, botVertex
, inc_chain
, inc_current
, inc_end
,
486 dec_chain
, dec_current
, dec_end
,
491 /*if inc_current>inc_end, then inc_chain has no points to be considered
494 void monoTriangulationRecGen(Real
* topVertex
, Real
* botVertex
,
495 vertexArray
* inc_chain
, Int inc_current
, Int inc_end
,
496 vertexArray
* dec_chain
, Int dec_current
, Int dec_end
,
503 if(inc_current
> inc_end
&& dec_current
>dec_end
)
505 else if(inc_current
>inc_end
) /*no more vertices on inc_chain*/
507 dec_array
= dec_chain
->getArray();
508 reflexChain
rChain(100,0);
509 /*put the top vertex into the reflex chain*/
510 rChain
.processNewVertex(topVertex
, pStream
);
511 /*process all the vertices on the dec_chain*/
512 for(i
=dec_current
; i
<=dec_end
; i
++){
513 rChain
.processNewVertex(dec_array
[i
], pStream
);
515 /*process the bottom vertex*/
516 rChain
.processNewVertex(botVertex
, pStream
);
518 else if(dec_current
> dec_end
) /*no more vertices on dec_chain*/
520 inc_array
= inc_chain
->getArray();
522 reflexChain
rChain(100,1);
523 /*put the top vertex into the reflex chain*/
524 rChain
.processNewVertex(topVertex
, pStream
);
525 /*process all the vertices on the inc_chain*/
526 for(i
=inc_current
; i
<=inc_end
; i
++){
527 rChain
.processNewVertex(inc_array
[i
], pStream
);
529 /*process the bottom vertex*/
530 rChain
.processNewVertex(botVertex
, pStream
);
532 else /*neither chain is empty*/
534 inc_array
= inc_chain
-> getArray();
535 dec_array
= dec_chain
-> getArray();
537 /*if top of inc_chain is 'lower' than top of dec_chain, process all the
538 *vertices on the dec_chain which are higher than top of inc_chain
540 if(compV2InY(inc_array
[inc_current
], dec_array
[dec_current
]) <= 0)
543 reflexChain
rChain(100, 0);
544 rChain
.processNewVertex(topVertex
, pStream
);
545 for(i
=dec_current
; i
<=dec_end
; i
++)
547 if(compV2InY(inc_array
[inc_current
], dec_array
[i
]) <= 0)
548 rChain
.processNewVertex(dec_array
[i
], pStream
);
552 rChain
.outputFan(inc_array
[inc_current
], pStream
);
553 monoTriangulationRecGen(dec_array
[i
-1], botVertex
,
554 inc_chain
, inc_current
, inc_end
,
555 dec_chain
, i
, dec_end
,
558 else /*compV2InY(inc_array[inc_current], dec_array[dec_current]) > 0*/
561 reflexChain
rChain(100, 1);
562 rChain
.processNewVertex(topVertex
, pStream
);
563 for(i
=inc_current
; i
<=inc_end
; i
++)
565 if(compV2InY(inc_array
[i
], dec_array
[dec_current
]) >0)
566 rChain
.processNewVertex(inc_array
[i
], pStream
);
570 rChain
.outputFan(dec_array
[dec_current
], pStream
);
571 monoTriangulationRecGen(inc_array
[i
-1], botVertex
,
572 inc_chain
, i
, inc_end
,
573 dec_chain
, dec_current
,dec_end
,
576 }/*end case neither is empty*/
579 void monoTriangulationFun(directedLine
* monoPolygon
, Int (*compFun
)(Real
*, Real
*), primStream
* pStream
)
582 /*find the top vertex, bottom vertex, inccreasing chain, and decreasing chain,
583 *then call monoTriangulationRec
588 topV
= botV
= monoPolygon
;
589 for(tempV
= monoPolygon
->getNext(); tempV
!= monoPolygon
; tempV
= tempV
->getNext())
591 if(compFun(topV
->head(), tempV
->head())<0) {
594 if(compFun(botV
->head(), tempV
->head())>0) {
599 /*creat increase and decrease chains*/
600 vertexArray
inc_chain(20); /*this is a dynamic array*/
601 for(i
=1; i
<=topV
->get_npoints()-2; i
++) { /*the first vertex is the top vertex which doesn't belong to inc_chain*/
602 inc_chain
.appendVertex(topV
->getVertex(i
));
604 for(tempV
= topV
->getNext(); tempV
!= botV
; tempV
= tempV
->getNext())
606 for(i
=0; i
<=tempV
->get_npoints()-2; i
++){
607 inc_chain
.appendVertex(tempV
->getVertex(i
));
611 vertexArray
dec_chain(20);
612 for(tempV
= topV
->getPrev(); tempV
!= botV
; tempV
= tempV
->getPrev())
614 for(i
=tempV
->get_npoints()-2; i
>=0; i
--){
615 dec_chain
.appendVertex(tempV
->getVertex(i
));
618 for(i
=botV
->get_npoints()-2; i
>=1; i
--){
619 dec_chain
.appendVertex(tempV
->getVertex(i
));
622 if (!(0 == inc_chain
.getNumElements() && 0 == dec_chain
.getNumElements())) {
623 monoTriangulationRecFun(topV
->head(), botV
->head(), &inc_chain
, 0,
624 &dec_chain
, 0, compFun
, pStream
);
628 void monoTriangulation(directedLine
* monoPolygon
, primStream
* pStream
)
631 /*find the top vertex, bottom vertex, inccreasing chain, and decreasing chain,
632 *then call monoTriangulationRec
637 topV
= botV
= monoPolygon
;
638 for(tempV
= monoPolygon
->getNext(); tempV
!= monoPolygon
; tempV
= tempV
->getNext())
640 if(compV2InY(topV
->head(), tempV
->head())<0) {
643 if(compV2InY(botV
->head(), tempV
->head())>0) {
647 /*creat increase and decrease chains*/
648 vertexArray
inc_chain(20); /*this is a dynamic array*/
649 for(i
=1; i
<=topV
->get_npoints()-2; i
++) { /*the first vertex is the top vertex which doesn't belong to inc_chain*/
650 inc_chain
.appendVertex(topV
->getVertex(i
));
652 for(tempV
= topV
->getNext(); tempV
!= botV
; tempV
= tempV
->getNext())
654 for(i
=0; i
<=tempV
->get_npoints()-2; i
++){
655 inc_chain
.appendVertex(tempV
->getVertex(i
));
659 vertexArray
dec_chain(20);
660 for(tempV
= topV
->getPrev(); tempV
!= botV
; tempV
= tempV
->getPrev())
662 for(i
=tempV
->get_npoints()-2; i
>=0; i
--){
663 dec_chain
.appendVertex(tempV
->getVertex(i
));
666 for(i
=botV
->get_npoints()-2; i
>=1; i
--){
667 dec_chain
.appendVertex(tempV
->getVertex(i
));
670 monoTriangulationRec(topV
->head(), botV
->head(), &inc_chain
, 0, &dec_chain
, 0, pStream
);
674 /*the chain could be increasing or decreasing, although we use the
676 *the argument is_increase_chain indicates whether this chain
677 *is increasing (left chain in V-monotone case) or decreaing (right chain
678 *in V-monotone case).
680 void monoTriangulation2(Real
* topVertex
, Real
* botVertex
,
681 vertexArray
* inc_chain
, Int inc_smallIndex
,
683 Int is_increase_chain
,
686 assert( inc_chain
!= NULL
);
689 if(inc_smallIndex
> inc_largeIndex
)
690 return; //no triangles
691 if(inc_smallIndex
== inc_largeIndex
)
693 if(is_increase_chain
)
694 pStream
->triangle(inc_chain
->getVertex(inc_smallIndex
), botVertex
, topVertex
);
696 pStream
->triangle(inc_chain
->getVertex(inc_smallIndex
), topVertex
, botVertex
);
701 if(is_increase_chain
&& botVertex
[1] == inc_chain
->getVertex(inc_largeIndex
)[1])
703 pStream
->triangle(botVertex
, inc_chain
->getVertex(inc_largeIndex
-1),
704 inc_chain
->getVertex(inc_largeIndex
));
705 monoTriangulation2(topVertex
, botVertex
, inc_chain
, inc_smallIndex
,
711 else if( (!is_increase_chain
) && topVertex
[1] == inc_chain
->getVertex(inc_smallIndex
)[1])
713 pStream
->triangle(topVertex
, inc_chain
->getVertex(inc_smallIndex
+1),
714 inc_chain
->getVertex(inc_smallIndex
));
715 monoTriangulation2(topVertex
, botVertex
, inc_chain
, inc_smallIndex
+1,
716 inc_largeIndex
, is_increase_chain
, pStream
);
720 inc_array
= inc_chain
->getArray();
722 reflexChain
rChain(20,is_increase_chain
); /*1 means the chain is increasing*/
724 rChain
.processNewVertex(topVertex
, pStream
);
726 for(i
=inc_smallIndex
; i
<=inc_largeIndex
; i
++){
727 rChain
.processNewVertex(inc_array
[i
], pStream
);
729 rChain
.processNewVertex(botVertex
, pStream
);
733 /*if compFun == compV2InY, top to bottom: V-monotone
734 *if compFun == compV2InX, right to left: U-monotone
736 void monoTriangulationRecFunGen(Real
* topVertex
, Real
* botVertex
,
737 vertexArray
* inc_chain
, Int inc_current
, Int inc_end
,
738 vertexArray
* dec_chain
, Int dec_current
, Int dec_end
,
739 Int (*compFun
)(Real
*, Real
*),
742 assert( inc_chain
!= NULL
&& dec_chain
!= NULL
);
743 assert( ! (inc_current
> inc_end
&&
744 dec_current
> dec_end
));
752 assert( ! ( (inc_chain
==NULL
) && (dec_chain
==NULL
)));
754 if(inc_current
> inc_end
) /*no more vertices on inc_chain*/
757 dec_array
= dec_chain
->getArray();
758 reflexChain
rChain(20,0);
759 /*put the top vertex into the reflex chain*/
760 rChain
.processNewVertex(topVertex
, pStream
);
761 /*process all the vertices on the dec_chain*/
762 for(i
=dec_current
; i
<=dec_end
; i
++){
763 rChain
.processNewVertex(dec_array
[i
], pStream
);
765 /*process the bottom vertex*/
766 rChain
.processNewVertex(botVertex
, pStream
);
769 else if(dec_current
> dec_end
) /*no more vertices on dec_chain*/
771 inc_array
= inc_chain
->getArray();
772 reflexChain
rChain(20,1);
773 /*put the top vertex into the reflex chain*/
774 rChain
.processNewVertex(topVertex
, pStream
);
775 /*process all the vertices on the inc_chain*/
776 for(i
=inc_current
; i
<=inc_end
; i
++){
777 rChain
.processNewVertex(inc_array
[i
], pStream
);
779 /*process the bottom vertex*/
780 rChain
.processNewVertex(botVertex
, pStream
);
782 else /*neither chain is empty*/
784 inc_array
= inc_chain
-> getArray();
785 dec_array
= dec_chain
-> getArray();
787 /*if top of inc_chain is 'lower' than top of dec_chain, process all the
788 *vertices on the dec_chain which are higher than top of inc_chain
790 if(compFun(inc_array
[inc_current
], dec_array
[dec_current
]) <= 0)
793 reflexChain
rChain(20, 0);
794 rChain
.processNewVertex(topVertex
, pStream
);
795 for(i
=dec_current
; i
<=dec_end
; i
++)
797 if(compFun(inc_array
[inc_current
], dec_array
[i
]) <= 0)
798 rChain
.processNewVertex(dec_array
[i
], pStream
);
802 rChain
.outputFan(inc_array
[inc_current
], pStream
);
803 monoTriangulationRecFunGen(dec_array
[i
-1], botVertex
,
804 inc_chain
, inc_current
, inc_end
,
805 dec_chain
, i
, dec_end
,
809 else /*compFun(inc_array[inc_current], dec_array[dec_current]) > 0*/
812 reflexChain
rChain(20, 1);
813 rChain
.processNewVertex(topVertex
, pStream
);
814 for(i
=inc_current
; i
<=inc_end
; i
++)
816 if(compFun(inc_array
[i
], dec_array
[dec_current
]) >0)
817 rChain
.processNewVertex(inc_array
[i
], pStream
);
821 rChain
.outputFan(dec_array
[dec_current
], pStream
);
822 monoTriangulationRecFunGen(inc_array
[i
-1], botVertex
,
823 inc_chain
, i
,inc_end
,
824 dec_chain
, dec_current
,dec_end
,
828 }/*end case neither is empty*/
831 /*if compFun == compV2InY, top to bottom: V-monotone
832 *if compFun == compV2InX, right to left: U-monotone
834 void monoTriangulationRecFun(Real
* topVertex
, Real
* botVertex
,
835 vertexArray
* inc_chain
, Int inc_current
,
836 vertexArray
* dec_chain
, Int dec_current
,
837 Int (*compFun
)(Real
*, Real
*),
840 assert( inc_chain
!= NULL
&& dec_chain
!= NULL
);
841 assert( ! (inc_current
>=inc_chain
->getNumElements() &&
842 dec_current
>=dec_chain
->getNumElements()));
848 assert( ! ( (inc_chain
==NULL
) && (dec_chain
==NULL
)));
850 if(inc_current
>=inc_chain
->getNumElements()) /*no more vertices on inc_chain*/
853 dec_array
= dec_chain
->getArray();
854 dec_nVertices
= dec_chain
->getNumElements();
855 reflexChain
rChain(20,0);
856 /*put the top vertex into the reflex chain*/
857 rChain
.processNewVertex(topVertex
, pStream
);
858 /*process all the vertices on the dec_chain*/
859 for(i
=dec_current
; i
<dec_nVertices
; i
++){
860 rChain
.processNewVertex(dec_array
[i
], pStream
);
862 /*process the bottom vertex*/
863 rChain
.processNewVertex(botVertex
, pStream
);
866 else if(dec_current
>= dec_chain
->getNumElements()) /*no more vertices on dec_chain*/
868 inc_array
= inc_chain
->getArray();
869 inc_nVertices
= inc_chain
->getNumElements();
870 reflexChain
rChain(20,1);
871 /*put the top vertex into the reflex chain*/
872 rChain
.processNewVertex(topVertex
, pStream
);
873 /*process all the vertices on the inc_chain*/
874 for(i
=inc_current
; i
<inc_nVertices
; i
++){
875 rChain
.processNewVertex(inc_array
[i
], pStream
);
877 /*process the bottom vertex*/
878 rChain
.processNewVertex(botVertex
, pStream
);
880 else /*neither chain is empty*/
882 inc_array
= inc_chain
-> getArray();
883 dec_array
= dec_chain
-> getArray();
884 inc_nVertices
= inc_chain
->getNumElements();
885 dec_nVertices
= dec_chain
->getNumElements();
886 /*if top of inc_chain is 'lower' than top of dec_chain, process all the
887 *vertices on the dec_chain which are higher than top of inc_chain
889 if(compFun(inc_array
[inc_current
], dec_array
[dec_current
]) <= 0)
892 reflexChain
rChain(20, 0);
893 rChain
.processNewVertex(topVertex
, pStream
);
894 for(i
=dec_current
; i
<dec_nVertices
; i
++)
896 if(compFun(inc_array
[inc_current
], dec_array
[i
]) <= 0)
897 rChain
.processNewVertex(dec_array
[i
], pStream
);
901 rChain
.outputFan(inc_array
[inc_current
], pStream
);
902 monoTriangulationRecFun(dec_array
[i
-1], botVertex
,
903 inc_chain
, inc_current
,
908 else /*compFun(inc_array[inc_current], dec_array[dec_current]) > 0*/
911 reflexChain
rChain(20, 1);
912 rChain
.processNewVertex(topVertex
, pStream
);
913 for(i
=inc_current
; i
<inc_nVertices
; i
++)
915 if(compFun(inc_array
[i
], dec_array
[dec_current
]) >0)
916 rChain
.processNewVertex(inc_array
[i
], pStream
);
920 rChain
.outputFan(dec_array
[dec_current
], pStream
);
921 monoTriangulationRecFun(inc_array
[i
-1], botVertex
,
923 dec_chain
, dec_current
,
927 }/*end case neither is empty*/
931 void monoTriangulationRec(Real
* topVertex
, Real
* botVertex
,
932 vertexArray
* inc_chain
, Int inc_current
,
933 vertexArray
* dec_chain
, Int dec_current
,
936 assert( inc_chain
!= NULL
&& dec_chain
!= NULL
);
937 assert( ! (inc_current
>=inc_chain
->getNumElements() &&
938 dec_current
>=dec_chain
->getNumElements()));
944 assert( ! ( (inc_chain
==NULL
) && (dec_chain
==NULL
)));
946 if(inc_current
>=inc_chain
->getNumElements()) /*no more vertices on inc_chain*/
949 dec_array
= dec_chain
->getArray();
950 dec_nVertices
= dec_chain
->getNumElements();
951 reflexChain
rChain(20,0);
952 /*put the top vertex into the reflex chain*/
953 rChain
.processNewVertex(topVertex
, pStream
);
954 /*process all the vertices on the dec_chain*/
955 for(i
=dec_current
; i
<dec_nVertices
; i
++){
956 rChain
.processNewVertex(dec_array
[i
], pStream
);
958 /*process the bottom vertex*/
959 rChain
.processNewVertex(botVertex
, pStream
);
962 else if(dec_current
>= dec_chain
->getNumElements()) /*no more vertices on dec_chain*/
964 inc_array
= inc_chain
->getArray();
965 inc_nVertices
= inc_chain
->getNumElements();
966 reflexChain
rChain(20,1);
967 /*put the top vertex into the reflex chain*/
968 rChain
.processNewVertex(topVertex
, pStream
);
969 /*process all the vertices on the inc_chain*/
970 for(i
=inc_current
; i
<inc_nVertices
; i
++){
971 rChain
.processNewVertex(inc_array
[i
], pStream
);
973 /*process the bottom vertex*/
974 rChain
.processNewVertex(botVertex
, pStream
);
976 else /*neither chain is empty*/
978 inc_array
= inc_chain
-> getArray();
979 dec_array
= dec_chain
-> getArray();
980 inc_nVertices
= inc_chain
->getNumElements();
981 dec_nVertices
= dec_chain
->getNumElements();
982 /*if top of inc_chain is 'lower' than top of dec_chain, process all the
983 *vertices on the dec_chain which are higher than top of inc_chain
985 if(compV2InY(inc_array
[inc_current
], dec_array
[dec_current
]) <= 0)
988 reflexChain
rChain(20, 0);
989 rChain
.processNewVertex(topVertex
, pStream
);
990 for(i
=dec_current
; i
<dec_nVertices
; i
++)
992 if(compV2InY(inc_array
[inc_current
], dec_array
[i
]) <= 0)
993 rChain
.processNewVertex(dec_array
[i
], pStream
);
997 rChain
.outputFan(inc_array
[inc_current
], pStream
);
998 monoTriangulationRec(dec_array
[i
-1], botVertex
,
999 inc_chain
, inc_current
,
1003 else /*compV2InY(inc_array[inc_current], dec_array[dec_current]) > 0*/
1006 reflexChain
rChain(20, 1);
1007 rChain
.processNewVertex(topVertex
, pStream
);
1008 for(i
=inc_current
; i
<inc_nVertices
; i
++)
1010 if(compV2InY(inc_array
[i
], dec_array
[dec_current
]) >0)
1011 rChain
.processNewVertex(inc_array
[i
], pStream
);
1015 rChain
.outputFan(dec_array
[dec_current
], pStream
);
1016 monoTriangulationRec(inc_array
[i
-1], botVertex
,
1018 dec_chain
, dec_current
,
1021 }/*end case neither is empty*/
1026 /* the name here assumes that the polygon is Y-monotone, but
1027 *this function also works for X-monotone polygons.
1028 * a monotne polygon consists of two extrem verteices: topVertex and botVertex, and
1029 *two monotone chains: inc_chain, and dec_chain. The edges of the increasing chain (inc_chain)
1030 *is ordered by following pointer: next, while the edges of the decreasing chain (dec_chain)
1031 *is ordered by following pointer: prev
1032 * inc_index index the vertex which is the toppest of the inc_chain which we are handling currently.
1033 * dec_index index the vertex which is the toppest of the dec_chain which we are handling currently.
1035 void monoTriangulationRec(directedLine
* inc_chain
, Int inc_index
,
1036 directedLine
* dec_chain
, Int dec_index
,
1037 directedLine
* topVertex
, Int top_index
,
1038 directedLine
* botVertex
,
1039 primStream
* pStream
)
1042 directedLine
*temp
, *oldtemp
= NULL
;
1043 Int tempIndex
, oldtempIndex
= 0;
1045 assert(inc_chain
!= NULL
&& dec_chain
!= NULL
);
1047 if(inc_chain
== botVertex
) {
1048 reflexChain
rChain(20, 0);
1049 rChain
.processNewVertex(topVertex
->getVertex(top_index
), pStream
);
1050 for(i
=dec_index
; i
< dec_chain
->get_npoints(); i
++){
1051 rChain
.processNewVertex(dec_chain
->getVertex(i
), pStream
);
1053 for(temp
= dec_chain
->getPrev(); temp
!= botVertex
; temp
= temp
->getPrev())
1055 for(i
=0; i
<temp
->get_npoints(); i
++){
1056 rChain
.processNewVertex(temp
->getVertex(i
), pStream
);
1060 else if(dec_chain
==botVertex
) {
1061 reflexChain
rChain(20, 1);
1062 rChain
.processNewVertex(topVertex
->getVertex(top_index
), pStream
);
1063 for(i
=inc_index
; i
< inc_chain
->get_npoints(); i
++){
1064 rChain
.processNewVertex(inc_chain
->getVertex(i
), pStream
);
1066 for(temp
= inc_chain
->getPrev(); temp
!= botVertex
; temp
= temp
->getNext())
1068 for(i
=0; i
<temp
->get_npoints(); i
++){
1069 rChain
.processNewVertex(temp
->getVertex(i
), pStream
);
1073 else /*neither reached the bottom*/{
1074 if(compV2InY(inc_chain
->getVertex(inc_index
), dec_chain
->getVertex(dec_index
)) <=0) {
1075 reflexChain
rChain(20, 0);
1076 rChain
.processNewVertex(topVertex
-> getVertex(top_index
), pStream
);
1078 tempIndex
= dec_index
;
1079 while( compV2InY(inc_chain
->getVertex(inc_index
), temp
->getVertex(tempIndex
))<=0) {
1081 oldtempIndex
= tempIndex
;
1082 rChain
.processNewVertex(temp
->getVertex(tempIndex
), pStream
);
1084 if(tempIndex
== temp
->get_npoints()-1){
1086 temp
= temp
->getPrev();
1092 rChain
.outputFan(inc_chain
->getVertex(inc_index
), pStream
);
1093 monoTriangulationRec(inc_chain
, inc_index
, temp
, tempIndex
, oldtemp
, oldtempIndex
, botVertex
, pStream
);
1096 reflexChain
rChain(20, 1);
1097 rChain
.processNewVertex(topVertex
-> getVertex(top_index
), pStream
);
1099 tempIndex
= inc_index
;
1100 while( compV2InY(temp
->getVertex(tempIndex
), dec_chain
->getVertex(dec_index
))>0){
1102 oldtempIndex
= tempIndex
;
1103 rChain
.processNewVertex(temp
->getVertex(tempIndex
), pStream
);
1105 if(tempIndex
== temp
->get_npoints()-1){
1107 temp
= temp
->getNext();
1113 rChain
.outputFan(dec_chain
->getVertex(dec_index
), pStream
);
1114 monoTriangulationRec(temp
, tempIndex
, dec_chain
, dec_index
, oldtemp
, oldtempIndex
, botVertex
, pStream
);
1116 } /*end case neither reached the bottom*/
1119 /***************************vertexArray begin here**********************************/
1120 vertexArray::vertexArray(Real2
* vertices
, Int nVertices
)
1123 size
= index
= nVertices
;
1124 array
= (Real
**) malloc(sizeof(Real
*) * nVertices
);
1126 for(i
=0; i
<nVertices
; i
++)
1128 array
[i
] = vertices
[i
];
1129 array
[i
] = vertices
[i
];
1133 vertexArray::vertexArray(Int s
)
1136 array
= (Real
**) malloc(sizeof(Real
*) * s
);
1141 vertexArray::~vertexArray()
1146 void vertexArray::appendVertex(Real
* ptr
)
1150 Real
** temp
= (Real
**) malloc(sizeof(Real
*) * (2*size
+1));
1152 for(i
=0; i
<index
; i
++)
1158 array
[index
++] = ptr
;
1161 void vertexArray::print()
1163 printf("vertex Array:index=%i, size=%i\n", index
, size
);
1164 for(Int i
=0; i
<index
; i
++)
1166 printf("(%f,%f) ", array
[i
][0], array
[i
][1]);
1171 /*find the first i such that array[i][1] >= v
1172 * and array[i+1][1] <v
1173 * if index == 0 (the array is empty, return -1.
1174 * if v is above all, return -1.
1175 * if v is below all, return index-1.
1177 Int
vertexArray::findIndexAbove(Real v
)
1182 else if(array
[0][1] < v
)
1186 for(i
=1; i
<index
; i
++)
1195 /*find the first i<=endIndex such that array[i][1] <= v
1196 * and array[i-1][1] > v
1197 *if sartIndex>endIndex, then return endIndex+1.
1198 *otherwise, startIndex<=endIndex, it is assumed that
1199 * 0<=startIndex<=endIndex<index.
1200 * if v is below all, return endIndex+1
1201 * if v is above all, return startIndex.
1203 Int
vertexArray::findIndexBelowGen(Real v
, Int startIndex
, Int endIndex
)
1206 if(startIndex
> endIndex
)
1208 else if(array
[endIndex
][1] > v
)
1210 else //now array[endIndex][1] <= v
1212 for(i
=endIndex
-1; i
>=startIndex
; i
--)
1221 /*find the first i<=endIndex such that array[i-1][1] >= v
1222 * and array[i][1] < v
1223 *if sartIndex>endIndex, then return endIndex+1.
1224 *otherwise, startIndex<=endIndex, it is assumed that
1225 * 0<=startIndex<=endIndex<index.
1226 * if v is below or equal to all, return endIndex+1
1227 * if v is strictly above all, return startIndex.
1229 Int
vertexArray::findIndexStrictBelowGen(Real v
, Int startIndex
, Int endIndex
)
1232 if(startIndex
> endIndex
)
1234 else if(array
[endIndex
][1] >= v
)
1236 else //now array[endIndex][1] < v
1238 for(i
=endIndex
-1; i
>=startIndex
; i
--)
1240 if(array
[i
][1] >= v
)
1247 /*find the first i>startIndex such that array[i-1][1] > v
1248 * and array[i][1] >=v
1249 *if sartIndex>endIndex, then return startIndex-1.
1250 *otherwise, startIndex<=endIndex, it is assumed that
1251 * 0<=startIndex<=endIndex<index.
1252 * if v is strictly above all, return startIndex-1
1253 * if v is strictly below all, return endIndex.
1255 Int
vertexArray::findIndexFirstAboveEqualGen(Real v
, Int startIndex
, Int endIndex
)
1259 if(startIndex
> endIndex
)
1260 return startIndex
-1;
1261 else if(array
[startIndex
][1] < v
)
1262 return startIndex
-1;
1263 else //now array[startIndex][1] >= v
1266 for(i
=startIndex
; i
<=endIndex
; i
++)
1268 if(array
[i
][1] <= v
)
1271 if(i
>endIndex
) // v is strictly below all
1273 else if(array
[i
][1] == v
)
1282 /*find the first i>=startIndex such that array[i][1] >= v
1283 * and array[i+1][1] <v
1284 *if sartIndex>endIndex, then return startIndex-1.
1285 *otherwise, startIndex<=endIndex, it is assumed that
1286 * 0<=startIndex<=endIndex<index.
1287 * if v is above all, return startIndex-1
1288 * if v is below all, return endIndex.
1290 Int
vertexArray::findIndexAboveGen(Real v
, Int startIndex
, Int endIndex
)
1293 if(startIndex
> endIndex
)
1294 return startIndex
-1;
1295 else if(array
[startIndex
][1] < v
)
1296 return startIndex
-1;
1297 else //now array[startIndex][1] >= v
1299 for(i
=startIndex
+1; i
<=endIndex
; i
++)
1308 Int
vertexArray::findDecreaseChainFromEnd(Int begin
, Int end
)
1311 Real prevU
= array
[i
][0];
1313 for(i
=end
-1; i
>=begin
; i
--){
1314 thisU
= array
[i
][0];
1323 //if(V(start) == v, return start, other wise return the
1324 //last i so that V(i)==v
1325 Int
vertexArray::skipEqualityFromStart(Real v
, Int start
, Int end
)
1328 if(array
[start
][1] != v
)
1330 //now array[start][1] == v
1331 for(i
=start
+1; i
<= end
; i
++)
1332 if(array
[i
][1] != v
)
1338 /***************************vertexArray end****************************************/
1342 /***************************relfex chain stuff begin here*****************************/
1344 reflexChain::reflexChain(Int size
, Int is_increasing
)
1346 queue
= (Real2
*) malloc(sizeof(Real2
) * size
);
1350 isIncreasing
= is_increasing
;
1353 reflexChain::~reflexChain()
1358 /*put (u,v) at the end of the queue
1359 *pay attention to space
1361 void reflexChain::insert(Real u
, Real v
)
1364 if(index_queue
>= size_queue
) {
1365 Real2
*temp
= (Real2
*) malloc(sizeof(Real2
) * (2*size_queue
+1));
1369 for(i
=0; i
<index_queue
; i
++){
1370 temp
[i
][0] = queue
[i
][0];
1371 temp
[i
][1] = queue
[i
][1];
1376 size_queue
= 2*size_queue
+ 1;
1379 queue
[index_queue
][0] = u
;
1380 queue
[index_queue
][1] = v
;
1384 void reflexChain::insert(Real v
[2])
1390 static Real area(Real A[2], Real B[2], Real C[2])
1392 Real Bx, By, Cx, Cy;
1397 return Bx*Cy - Cx*By;
1401 /*the chain is reflex, and the vertex v is
1402 *on the other side of the chain, so that
1403 *we can outout the fan with v as the
1406 void reflexChain::outputFan(Real v
[2], primStream
* pStream
)
1412 for(i
=0; i
<index_queue
; i
++)
1413 pStream
->insert(queue
[i
]);
1416 for(i
=index_queue
-1; i
>=0; i
--)
1417 pStream
->insert(queue
[i
]);
1419 pStream
->end(PRIMITIVE_STREAM_FAN
);
1422 void reflexChain::processNewVertex(Real v
[2], primStream
* pStream
)
1426 /*if there are at most one vertex in the queue, then simply insert
1428 if(index_queue
<=1){
1433 /*there are at least two vertices in the queue*/
1436 for(i
=j
; i
>=1; i
--) {
1438 isReflex
= (area(queue
[i
-1], queue
[i
], v
) <= 0.0);
1440 else /*decreasing*/{
1441 isReflex
= (area(v
, queue
[i
], queue
[i
-1]) <= 0.0);
1449 *if i<j then vertices: i+1--j are convex
1450 * output triangle fan:
1451 * v, and queue[i], i+1, ..., j
1459 pStream
->insert(queue
[k
]);
1463 pStream
->insert(queue
[k
]);
1466 pStream
->end(PRIMITIVE_STREAM_FAN
);
1469 /*delete vertices i+1--j from the queue*/
1471 /*finally insert v at the end of the queue*/
1476 void reflexChain::print()
1479 printf("reflex chain: isIncreasing=%i\n", isIncreasing
);
1480 for(i
=0; i
<index_queue
; i
++) {
1481 printf("(%f,%f) ", queue
[i
][0], queue
[i
][1]);