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: 2001/03/17 00:25:41 $ $Revision: 1.1 $
37 ** $Header: /home/krh/git/sync/mesa-cvs-repo/Mesa/src/glu/sgi/libnurbs/nurbtess/monoTriangulation.cc,v 1.1 2001/03/17 00:25:41 brianp Exp $
42 #include "glimports.h"
45 #include "monoTriangulation.h"
46 #include "polyUtil.h" /*for area*/
47 #include "partitionX.h"
48 #include "monoPolyPart.h"
52 extern directedLine
* polygonConvert(directedLine
* polygon
);
56 void monoTriangulationOpt(directedLine
* poly
, primStream
* pStream
)
59 Int n_edges
= poly
->numEdges();
60 directedLine
** cusps
= (directedLine
**) malloc(sizeof(directedLine
*)*n_edges
);
62 findInteriorCuspsX(poly
, n_cusps
, cusps
);
63 if(n_cusps
==0) //u monotine
65 monoTriangulationFun(poly
, compV2InX
, pStream
);
67 else if(n_cusps
== 1) // one interior cusp
69 directedLine
* new_polygon
= polygonConvert(cusps
[0]);
70 directedLine
* other
= findDiagonal_singleCuspX(new_polygon
);
71 //<other> should NOT be null unless there are self-intersecting
72 //trim curves. In that case, we don't want to core dump, instead,
73 //we triangulate anyway, and print out error message.
76 monoTriangulationFun(poly
, compV2InX
, pStream
);
83 new_polygon
->connectDiagonal_2slines(new_polygon
, other
,
88 monoTriangulationFun(ret_p1
, compV2InX
, pStream
);
89 monoTriangulationFun(ret_p2
, compV2InX
, pStream
);
91 ret_p1
->deleteSinglePolygonWithSline();
92 ret_p2
->deleteSinglePolygonWithSline();
97 //we need a general partitionX funtion (supposed to be in partitionX.C,
98 //not implemented yet. XXX
99 monoTriangulationFun(poly
, compV2InY
, pStream
);
105 void monoTriangulationRecOpt(Real
* topVertex
, Real
* botVertex
,
106 vertexArray
* left_chain
, Int left_current
,
107 vertexArray
* right_chain
, Int right_current
,
111 Int n_left
= left_chain
->getNumElements();
112 Int n_right
= right_chain
->getNumElements();
113 if(left_current
>= n_left
-1 ||
114 right_current
>= n_right
-1)
116 monoTriangulationRec(topVertex
, botVertex
, left_chain
, left_current
,
117 right_chain
, right_current
, pStream
);
120 //now both left and right have at least two vertices each.
121 Real left_v
= left_chain
->getVertex(left_current
)[1];
122 Real right_v
= right_chain
->getVertex(right_current
)[1];
124 if(left_v
<= right_v
) //first left vertex is below right
126 //find the last vertex of right which is above or equal to left
127 for(j
=right_current
; j
<=n_right
-1; j
++)
129 if(right_chain
->getVertex(j
)[1] < left_v
)
132 monoTriangulationRecGen(topVertex
, left_chain
->getVertex(left_current
),
133 left_chain
, left_current
, left_current
,
134 right_chain
, right_current
, j
-1,
136 monoTriangulationRecOpt(right_chain
->getVertex(j
-1),
138 left_chain
, left_current
,
142 else //first right vertex is strictly below left
144 //find the last vertex of left which is strictly above right
145 for(i
=left_current
; i
<=n_left
-1; i
++)
147 if(left_chain
->getVertex(i
)[1] <= right_v
)
150 monoTriangulationRecGen(topVertex
, right_chain
->getVertex(right_current
),
151 left_chain
, left_current
, i
-1,
152 right_chain
, right_current
, right_current
,
154 monoTriangulationRecOpt(left_chain
->getVertex(i
-1),
157 right_chain
, right_current
,
163 void monoTriangulationRecGenTBOpt(Real
* topVertex
, Real
* botVertex
,
164 vertexArray
* inc_chain
, Int inc_current
, Int inc_end
,
165 vertexArray
* dec_chain
, Int dec_current
, Int dec_end
,
168 pStream
->triangle(topVertex
, inc_chain
->getVertex(inc_current
), dec_chain
->getVertex(dec_current
));
170 /*printf("**(%f,%f)\n", inc_chain->getArray()[0][0],inc_chain->getArray()[0][1]);*/
171 triangulateXYMonoTB(inc_end
-inc_current
+1, inc_chain
->getArray()+inc_current
, dec_end
-dec_current
+1, dec_chain
->getArray()+dec_current
, pStream
);
173 pStream
->triangle(botVertex
, dec_chain
->getVertex(dec_end
), inc_chain
->getVertex(inc_end
));
179 *the strip is going top to bottom. compared to the funtion
180 * triangulateXYmono()
182 void triangulateXYMonoTB(Int n_left
, Real
** leftVerts
,
183 Int n_right
, Real
** rightVerts
,
191 assert(n_left
>=1 && n_right
>=1);
192 if(leftVerts
[0][1] >= rightVerts
[0][1])
196 topMostV
= leftVerts
[0];
202 topMostV
= rightVerts
[0];
207 if(i
>= n_left
) /*case1: no more in left*/
210 if(j
<n_right
-1) /*at least two vertices in right*/
213 pStream
->insert(topMostV
);
214 for(k
=n_right
-1; k
>=j
; k
--)
215 pStream
->insert(rightVerts
[j
]);
217 pStream
->end(PRIMITIVE_STREAM_FAN
);
223 else if(j
>= n_right
) /*case2: no more in right*/
226 if(i
<n_left
-1) /*at least two vertices in left*/
229 pStream
->insert(topMostV
);
231 for(k
=i
; k
<n_left
; k
++)
232 pStream
->insert(leftVerts
[k
]);
234 pStream
->end(PRIMITIVE_STREAM_FAN
);
239 else /* case3: neither is empty, plus the topMostV, there is at least one triangle to output*/
242 if(leftVerts
[i
][1] >= rightVerts
[j
][1])
245 pStream
->insert(rightVerts
[j
]); /*the origin of this fan*/
247 pStream
->insert(topMostV
);
249 /*find the last k>=i such that
250 *leftverts[k][1] >= rightverts[j][1]
255 if(leftVerts
[k
][1] < rightVerts
[j
][1])
262 pStream
->insert(leftVerts
[l
]);
265 pStream
->end(PRIMITIVE_STREAM_FAN
);
266 //update i for next loop
268 topMostV
= leftVerts
[k
];
271 else /*leftVerts[i][1] < rightVerts[j][1]*/
274 pStream
->insert(leftVerts
[i
]);/*the origion of this fan*/
276 /*find the last k>=j such that
277 *rightverts[k][1] > leftverts[i][1]*/
281 if(rightVerts
[k
][1] <= leftVerts
[i
][1])
288 pStream
->insert(rightVerts
[l
]);
290 pStream
->insert(topMostV
);
291 pStream
->end(PRIMITIVE_STREAM_FAN
);
293 topMostV
= rightVerts
[j
-1];
299 static int chainConvex(vertexArray
* inc_chain
, Int inc_current
, Int inc_end
)
302 //if there are no more than 2 vertices, return 1
303 if(inc_current
>= inc_end
-1) return 1;
304 for(i
=inc_current
; i
<= inc_end
-2; i
++)
306 if(area(inc_chain
->getVertex(i
), inc_chain
->getVertex(i
+1), inc_chain
->getVertex(i
+2)) <0)
312 static int chainConcave(vertexArray
* dec_chain
, Int dec_current
, Int dec_end
)
315 //if there are no more than 2 vertices, return 1
316 if(dec_current
>= dec_end
-1) return 1;
317 for(i
=dec_current
; i
<=dec_end
-2; i
++)
319 if(area(dec_chain
->getVertex(i
), dec_chain
->getVertex(i
+1), dec_chain
->getVertex(i
+2)) >0)
325 void monoTriangulationRecGenInU(Real
* topVertex
, Real
* botVertex
,
326 vertexArray
* inc_chain
, Int inc_current
, Int inc_end
,
327 vertexArray
* dec_chain
, Int dec_current
, Int dec_end
,
333 void monoTriangulationRecGenOpt(Real
* topVertex
, Real
* botVertex
,
334 vertexArray
* inc_chain
, Int inc_current
, Int inc_end
,
335 vertexArray
* dec_chain
, Int dec_current
, Int dec_end
,
339 //copy this to a polygon: directedLine Lioop
344 if(inc_current
<= inc_end
) //at least one vertex in inc_chain
346 sline
= new sampledLine(topVertex
, inc_chain
->getVertex(inc_current
));
347 poly
= new directedLine(INCREASING
, sline
);
348 for(i
=inc_current
; i
<=inc_end
-1; i
++)
350 sline
= new sampledLine(inc_chain
->getVertex(i
), inc_chain
->getVertex(i
+1));
351 dline
= new directedLine(INCREASING
, sline
);
354 sline
= new sampledLine(inc_chain
->getVertex(inc_end
), botVertex
);
355 dline
= new directedLine(INCREASING
, sline
);
358 else //inc_chian is empty
360 sline
= new sampledLine(topVertex
, botVertex
);
361 dline
= new directedLine(INCREASING
, sline
);
365 assert(poly
!= NULL
);
367 if(dec_current
<= dec_end
) //at least on vertex in dec_Chain
369 sline
= new sampledLine(botVertex
, dec_chain
->getVertex(dec_end
));
370 dline
= new directedLine(INCREASING
, sline
);
372 for(i
=dec_end
; i
>dec_current
; i
--)
374 sline
= new sampledLine(dec_chain
->getVertex(i
), dec_chain
->getVertex(i
-1));
375 dline
= new directedLine(INCREASING
, sline
);
378 sline
= new sampledLine(dec_chain
->getVertex(dec_current
), topVertex
);
379 dline
= new directedLine(INCREASING
, sline
);
382 else //dec_chain is empty
384 sline
= new sampledLine(botVertex
, topVertex
);
385 dline
= new directedLine(INCREASING
, sline
);
391 Int n_edges
= poly
->numEdges();
392 directedLine
** cusps
= (directedLine
**) malloc(sizeof(directedLine
*)*n_edges
);
394 findInteriorCuspsX(poly
, n_cusps
, cusps
);
396 if(n_cusps
==0) //u monotine
398 monoTriangulationFun(poly
, compV2InX
, pStream
);
400 else if(n_cusps
== 1) // one interior cusp
402 directedLine
* new_polygon
= polygonConvert(cusps
[0]);
403 directedLine
* other
= findDiagonal_singleCuspX(new_polygon
);
404 //<other> should NOT be null unless there are self-intersecting
405 //trim curves. In that case, we don't want to core dump, instead,
406 //we triangulate anyway, and print out error message.
409 monoTriangulationFun(poly
, compV2InX
, pStream
);
413 directedLine
* ret_p1
;
414 directedLine
* ret_p2
;
416 new_polygon
->connectDiagonal_2slines(new_polygon
, other
,
421 monoTriangulationFun(ret_p1
, compV2InX
, pStream
);
422 monoTriangulationFun(ret_p2
, compV2InX
, pStream
);
424 ret_p1
->deleteSinglePolygonWithSline();
425 ret_p2
->deleteSinglePolygonWithSline();
430 //we need a general partitionX funtion (supposed to be in partitionX.C,
431 //not implemented yet. XXX
432 //monoTriangulationFun(poly, compV2InY, pStream);
434 directedLine
* new_polygon
= polygonConvert(poly
);
435 directedLine
* list
= monoPolyPart(new_polygon
);
436 for(directedLine
* temp
= list
; temp
!= NULL
; temp
= temp
->getNextPolygon())
438 monoTriangulationFun(temp
, compV2InX
, pStream
);
441 list
->deletePolygonListWithSline();
447 if(numInteriorCuspsX(poly) == 0) //is u monotone
448 monoTriangulationFun(poly, compV2InX, pStream);
449 else //it is not u motone
450 monoTriangulationFun(poly, compV2InY, pStream);
453 poly
->deleteSinglePolygonWithSline();
457 //apparently the following code is not reachable,
458 //it is for test purpose
459 if(inc_current
> inc_end
|| dec_current
>dec_end
)
461 monoTriangulationRecGen(topVertex
, botVertex
, inc_chain
, inc_current
, inc_end
,
462 dec_chain
, dec_current
, dec_end
,
469 area(dec_chain
->getVertex(dec_current
),
471 inc_chain
->getVertex(inc_current
)) >=0
472 && chainConvex(inc_chain
, inc_current
, inc_end
)
473 && chainConcave(dec_chain
, dec_current
, dec_end
)
474 && area(inc_chain
->getVertex(inc_end
), botVertex
, dec_chain
->getVertex(dec_end
)) >=0
477 monoTriangulationRecFunGen(topVertex
, botVertex
,
478 inc_chain
, inc_current
, inc_end
,
479 dec_chain
, dec_current
, dec_end
,
484 monoTriangulationRecGen(topVertex
, botVertex
, inc_chain
, inc_current
, inc_end
,
485 dec_chain
, dec_current
, dec_end
,
490 /*if inc_current>inc_end, then inc_chain has no points to be considered
493 void monoTriangulationRecGen(Real
* topVertex
, Real
* botVertex
,
494 vertexArray
* inc_chain
, Int inc_current
, Int inc_end
,
495 vertexArray
* dec_chain
, Int dec_current
, Int dec_end
,
502 if(inc_current
> inc_end
&& dec_current
>dec_end
)
504 else if(inc_current
>inc_end
) /*no more vertices on inc_chain*/
506 dec_array
= dec_chain
->getArray();
507 reflexChain
rChain(100,0);
508 /*put the top vertex into the reflex chain*/
509 rChain
.processNewVertex(topVertex
, pStream
);
510 /*process all the vertices on the dec_chain*/
511 for(i
=dec_current
; i
<=dec_end
; i
++){
512 rChain
.processNewVertex(dec_array
[i
], pStream
);
514 /*process the bottom vertex*/
515 rChain
.processNewVertex(botVertex
, pStream
);
517 else if(dec_current
> dec_end
) /*no more vertices on dec_chain*/
519 inc_array
= inc_chain
->getArray();
521 reflexChain
rChain(100,1);
522 /*put the top vertex into the reflex chain*/
523 rChain
.processNewVertex(topVertex
, pStream
);
524 /*process all the vertices on the inc_chain*/
525 for(i
=inc_current
; i
<=inc_end
; i
++){
526 rChain
.processNewVertex(inc_array
[i
], pStream
);
528 /*process the bottom vertex*/
529 rChain
.processNewVertex(botVertex
, pStream
);
531 else /*neither chain is empty*/
533 inc_array
= inc_chain
-> getArray();
534 dec_array
= dec_chain
-> getArray();
536 /*if top of inc_chain is 'lower' than top of dec_chain, process all the
537 *vertices on the dec_chain which are higher than top of inc_chain
539 if(compV2InY(inc_array
[inc_current
], dec_array
[dec_current
]) <= 0)
542 reflexChain
rChain(100, 0);
543 rChain
.processNewVertex(topVertex
, pStream
);
544 for(i
=dec_current
; i
<=dec_end
; i
++)
546 if(compV2InY(inc_array
[inc_current
], dec_array
[i
]) <= 0)
547 rChain
.processNewVertex(dec_array
[i
], pStream
);
551 rChain
.outputFan(inc_array
[inc_current
], pStream
);
552 monoTriangulationRecGen(dec_array
[i
-1], botVertex
,
553 inc_chain
, inc_current
, inc_end
,
554 dec_chain
, i
, dec_end
,
557 else /*compV2InY(inc_array[inc_current], dec_array[dec_current]) > 0*/
560 reflexChain
rChain(100, 1);
561 rChain
.processNewVertex(topVertex
, pStream
);
562 for(i
=inc_current
; i
<=inc_end
; i
++)
564 if(compV2InY(inc_array
[i
], dec_array
[dec_current
]) >0)
565 rChain
.processNewVertex(inc_array
[i
], pStream
);
569 rChain
.outputFan(dec_array
[dec_current
], pStream
);
570 monoTriangulationRecGen(inc_array
[i
-1], botVertex
,
571 inc_chain
, i
, inc_end
,
572 dec_chain
, dec_current
,dec_end
,
575 }/*end case neither is empty*/
578 void monoTriangulationFun(directedLine
* monoPolygon
, Int (*compFun
)(Real
*, Real
*), primStream
* pStream
)
581 /*find the top vertex, bottom vertex, inccreasing chain, and decreasing chain,
582 *then call monoTriangulationRec
587 topV
= botV
= monoPolygon
;
588 for(tempV
= monoPolygon
->getNext(); tempV
!= monoPolygon
; tempV
= tempV
->getNext())
590 if(compFun(topV
->head(), tempV
->head())<0) {
593 if(compFun(botV
->head(), tempV
->head())>0) {
598 /*creat increase and decrease chains*/
599 vertexArray
inc_chain(20); /*this is a dynamic array*/
600 for(i
=1; i
<=topV
->get_npoints()-2; i
++) { /*the first vertex is the top vertex which doesn't belong to inc_chain*/
601 inc_chain
.appendVertex(topV
->getVertex(i
));
603 for(tempV
= topV
->getNext(); tempV
!= botV
; tempV
= tempV
->getNext())
605 for(i
=0; i
<=tempV
->get_npoints()-2; i
++){
606 inc_chain
.appendVertex(tempV
->getVertex(i
));
610 vertexArray
dec_chain(20);
611 for(tempV
= topV
->getPrev(); tempV
!= botV
; tempV
= tempV
->getPrev())
613 for(i
=tempV
->get_npoints()-2; i
>=0; i
--){
614 dec_chain
.appendVertex(tempV
->getVertex(i
));
617 for(i
=botV
->get_npoints()-2; i
>=1; i
--){
618 dec_chain
.appendVertex(tempV
->getVertex(i
));
621 monoTriangulationRecFun(topV
->head(), botV
->head(), &inc_chain
, 0, &dec_chain
, 0, compFun
, pStream
);
625 void monoTriangulation(directedLine
* monoPolygon
, primStream
* pStream
)
628 /*find the top vertex, bottom vertex, inccreasing chain, and decreasing chain,
629 *then call monoTriangulationRec
634 topV
= botV
= monoPolygon
;
635 for(tempV
= monoPolygon
->getNext(); tempV
!= monoPolygon
; tempV
= tempV
->getNext())
637 if(compV2InY(topV
->head(), tempV
->head())<0) {
640 if(compV2InY(botV
->head(), tempV
->head())>0) {
644 /*creat increase and decrease chains*/
645 vertexArray
inc_chain(20); /*this is a dynamic array*/
646 for(i
=1; i
<=topV
->get_npoints()-2; i
++) { /*the first vertex is the top vertex which doesn't belong to inc_chain*/
647 inc_chain
.appendVertex(topV
->getVertex(i
));
649 for(tempV
= topV
->getNext(); tempV
!= botV
; tempV
= tempV
->getNext())
651 for(i
=0; i
<=tempV
->get_npoints()-2; i
++){
652 inc_chain
.appendVertex(tempV
->getVertex(i
));
656 vertexArray
dec_chain(20);
657 for(tempV
= topV
->getPrev(); tempV
!= botV
; tempV
= tempV
->getPrev())
659 for(i
=tempV
->get_npoints()-2; i
>=0; i
--){
660 dec_chain
.appendVertex(tempV
->getVertex(i
));
663 for(i
=botV
->get_npoints()-2; i
>=1; i
--){
664 dec_chain
.appendVertex(tempV
->getVertex(i
));
667 monoTriangulationRec(topV
->head(), botV
->head(), &inc_chain
, 0, &dec_chain
, 0, pStream
);
671 /*the chain could be increasing or decreasing, although we use the
673 *the argument is_increase_chain indicates whether this chain
674 *is increasing (left chain in V-monotone case) or decreaing (right chain
675 *in V-monotone case).
677 void monoTriangulation2(Real
* topVertex
, Real
* botVertex
,
678 vertexArray
* inc_chain
, Int inc_smallIndex
,
680 Int is_increase_chain
,
683 assert( inc_chain
!= NULL
);
686 if(inc_smallIndex
> inc_largeIndex
)
687 return; //no triangles
688 if(inc_smallIndex
== inc_largeIndex
)
690 if(is_increase_chain
)
691 pStream
->triangle(inc_chain
->getVertex(inc_smallIndex
), botVertex
, topVertex
);
693 pStream
->triangle(inc_chain
->getVertex(inc_smallIndex
), topVertex
, botVertex
);
698 if(is_increase_chain
&& botVertex
[1] == inc_chain
->getVertex(inc_largeIndex
)[1])
700 pStream
->triangle(botVertex
, inc_chain
->getVertex(inc_largeIndex
-1),
701 inc_chain
->getVertex(inc_largeIndex
));
702 monoTriangulation2(topVertex
, botVertex
, inc_chain
, inc_smallIndex
,
708 else if( (!is_increase_chain
) && topVertex
[1] == inc_chain
->getVertex(inc_smallIndex
)[1])
710 pStream
->triangle(topVertex
, inc_chain
->getVertex(inc_smallIndex
+1),
711 inc_chain
->getVertex(inc_smallIndex
));
712 monoTriangulation2(topVertex
, botVertex
, inc_chain
, inc_smallIndex
+1,
713 inc_largeIndex
, is_increase_chain
, pStream
);
717 inc_array
= inc_chain
->getArray();
719 reflexChain
rChain(20,is_increase_chain
); /*1 means the chain is increasing*/
721 rChain
.processNewVertex(topVertex
, pStream
);
723 for(i
=inc_smallIndex
; i
<=inc_largeIndex
; i
++){
724 rChain
.processNewVertex(inc_array
[i
], pStream
);
726 rChain
.processNewVertex(botVertex
, pStream
);
730 /*if compFun == compV2InY, top to bottom: V-monotone
731 *if compFun == compV2InX, right to left: U-monotone
733 void monoTriangulationRecFunGen(Real
* topVertex
, Real
* botVertex
,
734 vertexArray
* inc_chain
, Int inc_current
, Int inc_end
,
735 vertexArray
* dec_chain
, Int dec_current
, Int dec_end
,
736 Int (*compFun
)(Real
*, Real
*),
739 assert( inc_chain
!= NULL
&& dec_chain
!= NULL
);
740 assert( ! (inc_current
> inc_end
&&
741 dec_current
> dec_end
));
747 assert( ! ( (inc_chain
==NULL
) && (dec_chain
==NULL
)));
749 if(inc_current
> inc_end
) /*no more vertices on inc_chain*/
752 dec_array
= dec_chain
->getArray();
753 reflexChain
rChain(20,0);
754 /*put the top vertex into the reflex chain*/
755 rChain
.processNewVertex(topVertex
, pStream
);
756 /*process all the vertices on the dec_chain*/
757 for(i
=dec_current
; i
<=dec_end
; i
++){
758 rChain
.processNewVertex(dec_array
[i
], pStream
);
760 /*process the bottom vertex*/
761 rChain
.processNewVertex(botVertex
, pStream
);
764 else if(dec_current
> dec_end
) /*no more vertices on dec_chain*/
766 inc_array
= inc_chain
->getArray();
767 reflexChain
rChain(20,1);
768 /*put the top vertex into the reflex chain*/
769 rChain
.processNewVertex(topVertex
, pStream
);
770 /*process all the vertices on the inc_chain*/
771 for(i
=inc_current
; i
<=inc_end
; i
++){
772 rChain
.processNewVertex(inc_array
[i
], pStream
);
774 /*process the bottom vertex*/
775 rChain
.processNewVertex(botVertex
, pStream
);
777 else /*neither chain is empty*/
779 inc_array
= inc_chain
-> getArray();
780 dec_array
= dec_chain
-> getArray();
782 /*if top of inc_chain is 'lower' than top of dec_chain, process all the
783 *vertices on the dec_chain which are higher than top of inc_chain
785 if(compFun(inc_array
[inc_current
], dec_array
[dec_current
]) <= 0)
788 reflexChain
rChain(20, 0);
789 rChain
.processNewVertex(topVertex
, pStream
);
790 for(i
=dec_current
; i
<=dec_end
; i
++)
792 if(compFun(inc_array
[inc_current
], dec_array
[i
]) <= 0)
793 rChain
.processNewVertex(dec_array
[i
], pStream
);
797 rChain
.outputFan(inc_array
[inc_current
], pStream
);
798 monoTriangulationRecFunGen(dec_array
[i
-1], botVertex
,
799 inc_chain
, inc_current
, inc_end
,
800 dec_chain
, i
, dec_end
,
804 else /*compFun(inc_array[inc_current], dec_array[dec_current]) > 0*/
807 reflexChain
rChain(20, 1);
808 rChain
.processNewVertex(topVertex
, pStream
);
809 for(i
=inc_current
; i
<=inc_end
; i
++)
811 if(compFun(inc_array
[i
], dec_array
[dec_current
]) >0)
812 rChain
.processNewVertex(inc_array
[i
], pStream
);
816 rChain
.outputFan(dec_array
[dec_current
], pStream
);
817 monoTriangulationRecFunGen(inc_array
[i
-1], botVertex
,
818 inc_chain
, i
,inc_end
,
819 dec_chain
, dec_current
,dec_end
,
823 }/*end case neither is empty*/
826 /*if compFun == compV2InY, top to bottom: V-monotone
827 *if compFun == compV2InX, right to left: U-monotone
829 void monoTriangulationRecFun(Real
* topVertex
, Real
* botVertex
,
830 vertexArray
* inc_chain
, Int inc_current
,
831 vertexArray
* dec_chain
, Int dec_current
,
832 Int (*compFun
)(Real
*, Real
*),
835 assert( inc_chain
!= NULL
&& dec_chain
!= NULL
);
836 assert( ! (inc_current
>=inc_chain
->getNumElements() &&
837 dec_current
>=dec_chain
->getNumElements()));
843 assert( ! ( (inc_chain
==NULL
) && (dec_chain
==NULL
)));
845 if(inc_current
>=inc_chain
->getNumElements()) /*no more vertices on inc_chain*/
848 dec_array
= dec_chain
->getArray();
849 dec_nVertices
= dec_chain
->getNumElements();
850 reflexChain
rChain(20,0);
851 /*put the top vertex into the reflex chain*/
852 rChain
.processNewVertex(topVertex
, pStream
);
853 /*process all the vertices on the dec_chain*/
854 for(i
=dec_current
; i
<dec_nVertices
; i
++){
855 rChain
.processNewVertex(dec_array
[i
], pStream
);
857 /*process the bottom vertex*/
858 rChain
.processNewVertex(botVertex
, pStream
);
861 else if(dec_current
>= dec_chain
->getNumElements()) /*no more vertices on dec_chain*/
863 inc_array
= inc_chain
->getArray();
864 inc_nVertices
= inc_chain
->getNumElements();
865 reflexChain
rChain(20,1);
866 /*put the top vertex into the reflex chain*/
867 rChain
.processNewVertex(topVertex
, pStream
);
868 /*process all the vertices on the inc_chain*/
869 for(i
=inc_current
; i
<inc_nVertices
; i
++){
870 rChain
.processNewVertex(inc_array
[i
], pStream
);
872 /*process the bottom vertex*/
873 rChain
.processNewVertex(botVertex
, pStream
);
875 else /*neither chain is empty*/
877 inc_array
= inc_chain
-> getArray();
878 dec_array
= dec_chain
-> getArray();
879 inc_nVertices
= inc_chain
->getNumElements();
880 dec_nVertices
= dec_chain
->getNumElements();
881 /*if top of inc_chain is 'lower' than top of dec_chain, process all the
882 *vertices on the dec_chain which are higher than top of inc_chain
884 if(compFun(inc_array
[inc_current
], dec_array
[dec_current
]) <= 0)
887 reflexChain
rChain(20, 0);
888 rChain
.processNewVertex(topVertex
, pStream
);
889 for(i
=dec_current
; i
<dec_nVertices
; i
++)
891 if(compFun(inc_array
[inc_current
], dec_array
[i
]) <= 0)
892 rChain
.processNewVertex(dec_array
[i
], pStream
);
896 rChain
.outputFan(inc_array
[inc_current
], pStream
);
897 monoTriangulationRecFun(dec_array
[i
-1], botVertex
,
898 inc_chain
, inc_current
,
903 else /*compFun(inc_array[inc_current], dec_array[dec_current]) > 0*/
906 reflexChain
rChain(20, 1);
907 rChain
.processNewVertex(topVertex
, pStream
);
908 for(i
=inc_current
; i
<inc_nVertices
; i
++)
910 if(compFun(inc_array
[i
], dec_array
[dec_current
]) >0)
911 rChain
.processNewVertex(inc_array
[i
], pStream
);
915 rChain
.outputFan(dec_array
[dec_current
], pStream
);
916 monoTriangulationRecFun(inc_array
[i
-1], botVertex
,
918 dec_chain
, dec_current
,
922 }/*end case neither is empty*/
926 void monoTriangulationRec(Real
* topVertex
, Real
* botVertex
,
927 vertexArray
* inc_chain
, Int inc_current
,
928 vertexArray
* dec_chain
, Int dec_current
,
931 assert( inc_chain
!= NULL
&& dec_chain
!= NULL
);
932 assert( ! (inc_current
>=inc_chain
->getNumElements() &&
933 dec_current
>=dec_chain
->getNumElements()));
939 assert( ! ( (inc_chain
==NULL
) && (dec_chain
==NULL
)));
941 if(inc_current
>=inc_chain
->getNumElements()) /*no more vertices on inc_chain*/
944 dec_array
= dec_chain
->getArray();
945 dec_nVertices
= dec_chain
->getNumElements();
946 reflexChain
rChain(20,0);
947 /*put the top vertex into the reflex chain*/
948 rChain
.processNewVertex(topVertex
, pStream
);
949 /*process all the vertices on the dec_chain*/
950 for(i
=dec_current
; i
<dec_nVertices
; i
++){
951 rChain
.processNewVertex(dec_array
[i
], pStream
);
953 /*process the bottom vertex*/
954 rChain
.processNewVertex(botVertex
, pStream
);
957 else if(dec_current
>= dec_chain
->getNumElements()) /*no more vertices on dec_chain*/
959 inc_array
= inc_chain
->getArray();
960 inc_nVertices
= inc_chain
->getNumElements();
961 reflexChain
rChain(20,1);
962 /*put the top vertex into the reflex chain*/
963 rChain
.processNewVertex(topVertex
, pStream
);
964 /*process all the vertices on the inc_chain*/
965 for(i
=inc_current
; i
<inc_nVertices
; i
++){
966 rChain
.processNewVertex(inc_array
[i
], pStream
);
968 /*process the bottom vertex*/
969 rChain
.processNewVertex(botVertex
, pStream
);
971 else /*neither chain is empty*/
973 inc_array
= inc_chain
-> getArray();
974 dec_array
= dec_chain
-> getArray();
975 inc_nVertices
= inc_chain
->getNumElements();
976 dec_nVertices
= dec_chain
->getNumElements();
977 /*if top of inc_chain is 'lower' than top of dec_chain, process all the
978 *vertices on the dec_chain which are higher than top of inc_chain
980 if(compV2InY(inc_array
[inc_current
], dec_array
[dec_current
]) <= 0)
983 reflexChain
rChain(20, 0);
984 rChain
.processNewVertex(topVertex
, pStream
);
985 for(i
=dec_current
; i
<dec_nVertices
; i
++)
987 if(compV2InY(inc_array
[inc_current
], dec_array
[i
]) <= 0)
988 rChain
.processNewVertex(dec_array
[i
], pStream
);
992 rChain
.outputFan(inc_array
[inc_current
], pStream
);
993 monoTriangulationRec(dec_array
[i
-1], botVertex
,
994 inc_chain
, inc_current
,
998 else /*compV2InY(inc_array[inc_current], dec_array[dec_current]) > 0*/
1001 reflexChain
rChain(20, 1);
1002 rChain
.processNewVertex(topVertex
, pStream
);
1003 for(i
=inc_current
; i
<inc_nVertices
; i
++)
1005 if(compV2InY(inc_array
[i
], dec_array
[dec_current
]) >0)
1006 rChain
.processNewVertex(inc_array
[i
], pStream
);
1010 rChain
.outputFan(dec_array
[dec_current
], pStream
);
1011 monoTriangulationRec(inc_array
[i
-1], botVertex
,
1013 dec_chain
, dec_current
,
1016 }/*end case neither is empty*/
1021 /* the name here assumes that the polygon is Y-monotone, but
1022 *this function also works for X-monotone polygons.
1023 * a monotne polygon consists of two extrem verteices: topVertex and botVertex, and
1024 *two monotone chains: inc_chain, and dec_chain. The edges of the increasing chain (inc_chain)
1025 *is ordered by following pointer: next, while the edges of the decreasing chain (dec_chain)
1026 *is ordered by following pointer: prev
1027 * inc_index index the vertex which is the toppest of the inc_chain which we are handling currently.
1028 * dec_index index the vertex which is the toppest of the dec_chain which we are handling currently.
1030 void monoTriangulationRec(directedLine
* inc_chain
, Int inc_index
,
1031 directedLine
* dec_chain
, Int dec_index
,
1032 directedLine
* topVertex
, Int top_index
,
1033 directedLine
* botVertex
,
1034 primStream
* pStream
)
1037 directedLine
*temp
, *oldtemp
;
1038 Int tempIndex
, oldtempIndex
;
1040 assert(inc_chain
!= NULL
&& dec_chain
!= NULL
);
1042 if(inc_chain
== botVertex
) {
1043 reflexChain
rChain(20, 0);
1044 rChain
.processNewVertex(topVertex
->getVertex(top_index
), pStream
);
1045 for(i
=dec_index
; i
< dec_chain
->get_npoints(); i
++){
1046 rChain
.processNewVertex(dec_chain
->getVertex(i
), pStream
);
1048 for(temp
= dec_chain
->getPrev(); temp
!= botVertex
; temp
= temp
->getPrev())
1050 for(i
=0; i
<temp
->get_npoints(); i
++){
1051 rChain
.processNewVertex(temp
->getVertex(i
), pStream
);
1055 else if(dec_chain
==botVertex
) {
1056 reflexChain
rChain(20, 1);
1057 rChain
.processNewVertex(topVertex
->getVertex(top_index
), pStream
);
1058 for(i
=inc_index
; i
< inc_chain
->get_npoints(); i
++){
1059 rChain
.processNewVertex(inc_chain
->getVertex(i
), pStream
);
1061 for(temp
= inc_chain
->getPrev(); temp
!= botVertex
; temp
= temp
->getNext())
1063 for(i
=0; i
<temp
->get_npoints(); i
++){
1064 rChain
.processNewVertex(temp
->getVertex(i
), pStream
);
1068 else /*neither reached the bottom*/{
1069 if(compV2InY(inc_chain
->getVertex(inc_index
), dec_chain
->getVertex(dec_index
)) <=0) {
1070 reflexChain
rChain(20, 0);
1071 rChain
.processNewVertex(topVertex
-> getVertex(top_index
), pStream
);
1073 tempIndex
= dec_index
;
1074 while( compV2InY(inc_chain
->getVertex(inc_index
), temp
->getVertex(tempIndex
))<=0) {
1076 oldtempIndex
= tempIndex
;
1077 rChain
.processNewVertex(temp
->getVertex(tempIndex
), pStream
);
1079 if(tempIndex
== temp
->get_npoints()-1){
1081 temp
= temp
->getPrev();
1087 rChain
.outputFan(inc_chain
->getVertex(inc_index
), pStream
);
1088 monoTriangulationRec(inc_chain
, inc_index
, temp
, tempIndex
, oldtemp
, oldtempIndex
, botVertex
, pStream
);
1091 reflexChain
rChain(20, 1);
1092 rChain
.processNewVertex(topVertex
-> getVertex(top_index
), pStream
);
1094 tempIndex
= inc_index
;
1095 while( compV2InY(temp
->getVertex(tempIndex
), dec_chain
->getVertex(dec_index
))>0){
1097 oldtempIndex
= tempIndex
;
1098 rChain
.processNewVertex(temp
->getVertex(tempIndex
), pStream
);
1100 if(tempIndex
== temp
->get_npoints()-1){
1102 temp
= temp
->getNext();
1108 rChain
.outputFan(dec_chain
->getVertex(dec_index
), pStream
);
1109 monoTriangulationRec(temp
, tempIndex
, dec_chain
, dec_index
, oldtemp
, oldtempIndex
, botVertex
, pStream
);
1111 } /*end case neither reached the bottom*/
1114 /***************************vertexArray begin here**********************************/
1115 vertexArray::vertexArray(Real2
* vertices
, Int nVertices
)
1118 size
= index
= nVertices
;
1119 array
= (Real
**) malloc(sizeof(Real
*) * nVertices
);
1121 for(i
=0; i
<nVertices
; i
++)
1123 array
[i
] = vertices
[i
];
1124 array
[i
] = vertices
[i
];
1128 vertexArray::vertexArray(Int s
)
1131 array
= (Real
**) malloc(sizeof(Real
*) * s
);
1136 vertexArray::~vertexArray()
1141 void vertexArray::appendVertex(Real
* ptr
)
1145 Real
** temp
= (Real
**) malloc(sizeof(Real
*) * (2*size
+1));
1147 for(i
=0; i
<index
; i
++)
1153 array
[index
++] = ptr
;
1156 void vertexArray::print()
1158 printf("vertex Array:index=%i, size=%i\n", index
, size
);
1159 for(Int i
=0; i
<index
; i
++)
1161 printf("(%f,%f) ", array
[i
][0], array
[i
][1]);
1166 /*find the first i such that array[i][1] >= v
1167 * and array[i+1][1] <v
1168 * if index == 0 (the array is empty, return -1.
1169 * if v is above all, return -1.
1170 * if v is below all, return index-1.
1172 Int
vertexArray::findIndexAbove(Real v
)
1177 else if(array
[0][1] < v
)
1181 for(i
=1; i
<index
; i
++)
1190 /*find the first i<=endIndex such that array[i][1] <= v
1191 * and array[i-1][1] > v
1192 *if sartIndex>endIndex, then return endIndex+1.
1193 *otherwise, startIndex<=endIndex, it is assumed that
1194 * 0<=startIndex<=endIndex<index.
1195 * if v is below all, return endIndex+1
1196 * if v is above all, return startIndex.
1198 Int
vertexArray::findIndexBelowGen(Real v
, Int startIndex
, Int endIndex
)
1201 if(startIndex
> endIndex
)
1203 else if(array
[endIndex
][1] > v
)
1205 else //now array[endIndex][1] <= v
1207 for(i
=endIndex
-1; i
>=startIndex
; i
--)
1216 /*find the first i<=endIndex such that array[i-1][1] >= v
1217 * and array[i][1] < v
1218 *if sartIndex>endIndex, then return endIndex+1.
1219 *otherwise, startIndex<=endIndex, it is assumed that
1220 * 0<=startIndex<=endIndex<index.
1221 * if v is below or equal to all, return endIndex+1
1222 * if v is strictly above all, return startIndex.
1224 Int
vertexArray::findIndexStrictBelowGen(Real v
, Int startIndex
, Int endIndex
)
1227 if(startIndex
> endIndex
)
1229 else if(array
[endIndex
][1] >= v
)
1231 else //now array[endIndex][1] < v
1233 for(i
=endIndex
-1; i
>=startIndex
; i
--)
1235 if(array
[i
][1] >= v
)
1242 /*find the first i>startIndex such that array[i-1][1] > v
1243 * and array[i][1] >=v
1244 *if sartIndex>endIndex, then return startIndex-1.
1245 *otherwise, startIndex<=endIndex, it is assumed that
1246 * 0<=startIndex<=endIndex<index.
1247 * if v is strictly above all, return startIndex-1
1248 * if v is strictly below all, return endIndex.
1250 Int
vertexArray::findIndexFirstAboveEqualGen(Real v
, Int startIndex
, Int endIndex
)
1254 if(startIndex
> endIndex
)
1255 return startIndex
-1;
1256 else if(array
[startIndex
][1] < v
)
1257 return startIndex
-1;
1258 else //now array[startIndex][1] >= v
1261 for(i
=startIndex
; i
<=endIndex
; i
++)
1263 if(array
[i
][1] <= v
)
1266 if(i
>endIndex
) // v is strictly below all
1268 else if(array
[i
][1] == v
)
1277 /*find the first i>=startIndex such that array[i][1] >= v
1278 * and array[i+1][1] <v
1279 *if sartIndex>endIndex, then return startIndex-1.
1280 *otherwise, startIndex<=endIndex, it is assumed that
1281 * 0<=startIndex<=endIndex<index.
1282 * if v is above all, return startIndex-1
1283 * if v is below all, return endIndex.
1285 Int
vertexArray::findIndexAboveGen(Real v
, Int startIndex
, Int endIndex
)
1288 if(startIndex
> endIndex
)
1289 return startIndex
-1;
1290 else if(array
[startIndex
][1] < v
)
1291 return startIndex
-1;
1292 else //now array[startIndex][1] >= v
1294 for(i
=startIndex
+1; i
<=endIndex
; i
++)
1303 Int
vertexArray::findDecreaseChainFromEnd(Int begin
, Int end
)
1306 Real prevU
= array
[i
][0];
1308 for(i
=end
-1; i
>=begin
; i
--){
1309 thisU
= array
[i
][0];
1318 //if(V(start) == v, return start, other wise return the
1319 //last i so that V(i)==v
1320 Int
vertexArray::skipEqualityFromStart(Real v
, Int start
, Int end
)
1323 if(array
[start
][1] != v
)
1325 //now array[start][1] == v
1326 for(i
=start
+1; i
<= end
; i
++)
1327 if(array
[i
][1] != v
)
1333 /***************************vertexArray end****************************************/
1337 /***************************relfex chain stuff begin here*****************************/
1339 reflexChain::reflexChain(Int size
, Int is_increasing
)
1341 queue
= (Real2
*) malloc(sizeof(Real2
) * size
);
1345 isIncreasing
= is_increasing
;
1348 reflexChain::~reflexChain()
1353 /*put (u,v) at the end of the queue
1354 *pay attention to space
1356 void reflexChain::insert(Real u
, Real v
)
1359 if(index_queue
>= size_queue
) {
1360 Real2
*temp
= (Real2
*) malloc(sizeof(Real2
) * (2*size_queue
+1));
1364 for(i
=0; i
<index_queue
; i
++){
1365 temp
[i
][0] = queue
[i
][0];
1366 temp
[i
][1] = queue
[i
][1];
1371 size_queue
= 2*size_queue
+ 1;
1374 queue
[index_queue
][0] = u
;
1375 queue
[index_queue
][1] = v
;
1379 void reflexChain::insert(Real v
[2])
1385 static Real area(Real A[2], Real B[2], Real C[2])
1387 Real Bx, By, Cx, Cy;
1392 return Bx*Cy - Cx*By;
1396 /*the chain is reflex, and the vertex v is
1397 *on the other side of the chain, so that
1398 *we can outout the fan with v as the
1401 void reflexChain::outputFan(Real v
[2], primStream
* pStream
)
1407 for(i
=0; i
<index_queue
; i
++)
1408 pStream
->insert(queue
[i
]);
1411 for(i
=index_queue
-1; i
>=0; i
--)
1412 pStream
->insert(queue
[i
]);
1414 pStream
->end(PRIMITIVE_STREAM_FAN
);
1417 void reflexChain::processNewVertex(Real v
[2], primStream
* pStream
)
1421 /*if there are at most one vertex in the queue, then simply insert
1423 if(index_queue
<=1){
1428 /*there are at least two vertices in the queue*/
1431 for(i
=j
; i
>=1; i
--) {
1433 isReflex
= (area(queue
[i
-1], queue
[i
], v
) <= 0.0);
1435 else /*decreasing*/{
1436 isReflex
= (area(v
, queue
[i
], queue
[i
-1]) <= 0.0);
1444 *if i<j then vertices: i+1--j are convex
1445 * output triangle fan:
1446 * v, and queue[i], i+1, ..., j
1454 pStream
->insert(queue
[k
]);
1458 pStream
->insert(queue
[k
]);
1461 pStream
->end(PRIMITIVE_STREAM_FAN
);
1464 /*delete vertices i+1--j from the queue*/
1466 /*finally insert v at the end of the queue*/
1471 void reflexChain::print()
1474 printf("reflex chain: isIncreasing=%i\n", isIncreasing
);
1475 for(i
=0; i
<index_queue
; i
++) {
1476 printf("(%f,%f) ", queue
[i
][0], queue
[i
][1]);