ReactOS 0.4.15-dev-7834-g00c4b3d
monoTriangulation.h File Reference
#include "primitiveStream.h"
#include "directedLine.h"
#include "arc.h"
Include dependency graph for monoTriangulation.h:
This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes

class  reflexChain
 
class  vertexArray
 

Functions

void monoTriangulation (directedLine *monoPolygon, primStream *pStream)
 
void monoTriangulationRec (Real *topVertex, Real *botVertex, vertexArray *inc_chain, Int inc_current, vertexArray *dec_chain, Int dec_current, primStream *pStream)
 
void monoTriangulationRec (directedLine *inc_chain, Int inc_index, directedLine *dec_chain, Int dec_index, directedLine *topVertex, Int top_index, directedLine *botVertex, primStream *pStream)
 
void monoTriangulation2 (Real *topVertex, Real *botVertex, vertexArray *inc_chain, Int inc_smallIndex, Int inc_largeIndex, Int is_increase_chain, primStream *pStream)
 
void monoTriangulationRecGen (Real *topVertex, Real *botVertex, vertexArray *inc_chain, Int inc_current, Int inc_end, vertexArray *dec_chain, Int dec_current, Int dec_end, primStream *pStream)
 
void monoTriangulationRecGenOpt (Real *topVertex, Real *botVertex, vertexArray *inc_chain, Int inc_current, Int inc_end, vertexArray *dec_chain, Int dec_current, Int dec_end, primStream *pStream)
 
void triangulateXYMonoTB (Int n_left, Real **leftVerts, Int n_right, Real **rightVerts, primStream *pStream)
 
void monoTriangulationRecGenTBOpt (Real *topVertex, Real *botVertex, vertexArray *inc_chain, Int inc_current, Int inc_end, vertexArray *dec_chain, Int dec_current, Int dec_end, primStream *pStream)
 
void monoTriangulationRecOpt (Real *topVertex, Real *botVertex, vertexArray *left_chain, Int left_current, vertexArray *right_chain, Int right_current, primStream *pStream)
 
void monoTriangulationRecFunGen (Real *topVertex, Real *botVertex, vertexArray *inc_chain, Int inc_current, Int inc_end, vertexArray *dec_chain, Int dec_current, Int dec_end, Int(*compFun)(Real *, Real *), primStream *pStream)
 
void monoTriangulationRecFun (Real *topVertex, Real *botVertex, vertexArray *inc_chain, Int inc_current, vertexArray *dec_chain, Int dec_current, Int(*compFun)(Real *, Real *), primStream *pStream)
 
void monoTriangulationFun (directedLine *monoPolygon, Int(*compFun)(Real *, Real *), primStream *pStream)
 
void monoTriangulationRec (Real *topVertex, Real *botVertex, vertexArray *inc_chain, Int inc_current, vertexArray *dec_chain, Int dec_current, Backend *backend)
 
void monoTriangulationFunBackend (Arc_ptr loop, Int(*compFun)(Real *, Real *), Backend *backend)
 
void monoTriangulationRecFunBackend (Real *topVertex, Real *botVertex, vertexArray *inc_chain, Int inc_current, vertexArray *dec_chain, Int dec_current, Int(*compFun)(Real *, Real *), Backend *backend)
 
void monoTriangulationOpt (directedLine *poly, primStream *pStream)
 

Function Documentation

◆ monoTriangulation()

void monoTriangulation ( directedLine monoPolygon,
primStream pStream 
)

Definition at line 626 of file monoTriangulation.cc.

627{
628 Int i;
629 /*find the top vertex, bottom vertex, inccreasing chain, and decreasing chain,
630 *then call monoTriangulationRec
631 */
632 directedLine* tempV;
633 directedLine* topV;
634 directedLine* botV;
635 topV = botV = monoPolygon;
636 for(tempV = monoPolygon->getNext(); tempV != monoPolygon; tempV = tempV->getNext())
637 {
638 if(compV2InY(topV->head(), tempV->head())<0) {
639 topV = tempV;
640 }
641 if(compV2InY(botV->head(), tempV->head())>0) {
642 botV = tempV;
643 }
644 }
645 /*creat increase and decrease chains*/
646 vertexArray inc_chain(20); /*this is a dynamic array*/
647 for(i=1; i<=topV->get_npoints()-2; i++) { /*the first vertex is the top vertex which doesn't belong to inc_chain*/
648 inc_chain.appendVertex(topV->getVertex(i));
649 }
650 for(tempV = topV->getNext(); tempV != botV; tempV = tempV->getNext())
651 {
652 for(i=0; i<=tempV->get_npoints()-2; i++){
653 inc_chain.appendVertex(tempV->getVertex(i));
654 }
655 }
656
657 vertexArray dec_chain(20);
658 for(tempV = topV->getPrev(); tempV != botV; tempV = tempV->getPrev())
659 {
660 for(i=tempV->get_npoints()-2; i>=0; i--){
661 dec_chain.appendVertex(tempV->getVertex(i));
662 }
663 }
664 for(i=botV->get_npoints()-2; i>=1; i--){
665 dec_chain.appendVertex(tempV->getVertex(i));
666 }
667
668 monoTriangulationRec(topV->head(), botV->head(), &inc_chain, 0, &dec_chain, 0, pStream);
669
670}
Int get_npoints()
Definition: directedLine.h:72
directedLine * getPrev()
Definition: directedLine.h:73
Real * getVertex(Int i)
directedLine * getNext()
Definition: directedLine.h:74
Real * head()
int Int
Definition: definitions.h:37
Int compV2InY(Real A[2], Real B[2])
GLsizei GLenum const GLvoid GLsizei GLenum GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLint GLint GLint GLshort GLshort GLshort GLubyte GLubyte GLubyte GLuint GLuint GLuint GLushort GLushort GLushort GLbyte GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLfloat GLint GLint GLint GLint GLshort GLshort GLshort GLshort GLubyte GLubyte GLubyte GLubyte GLuint GLuint GLuint GLuint GLushort GLushort GLushort GLushort GLboolean const GLdouble const GLfloat const GLint const GLshort const GLbyte const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLdouble const GLfloat const GLfloat const GLint const GLint const GLshort const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort GLenum GLenum GLenum GLfloat GLenum GLint GLenum GLenum GLenum GLfloat GLenum GLenum GLint GLenum GLfloat GLenum GLint GLint GLushort GLenum GLenum GLfloat GLenum GLenum GLint GLfloat const GLubyte GLenum GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLint GLint GLsizei GLsizei GLint GLenum GLenum const GLvoid GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLenum const GLdouble GLenum GLenum const GLfloat GLenum GLenum const GLint GLsizei GLuint GLfloat GLuint GLbitfield GLfloat GLint GLuint GLboolean GLenum GLfloat GLenum GLbitfield GLenum GLfloat GLfloat GLint GLint const GLfloat GLenum GLfloat GLfloat GLint GLint GLfloat GLfloat GLint GLint const GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat const GLdouble const GLfloat const GLdouble const GLfloat GLint i
Definition: glfuncs.h:248
void monoTriangulationRec(Real *topVertex, Real *botVertex, vertexArray *inc_chain, Int inc_current, vertexArray *dec_chain, Int dec_current, primStream *pStream)

Referenced by Subdivider::drawSurfaces().

◆ monoTriangulation2()

void monoTriangulation2 ( Real topVertex,
Real botVertex,
vertexArray inc_chain,
Int  inc_smallIndex,
Int  inc_largeIndex,
Int  is_increase_chain,
primStream pStream 
)

Definition at line 678 of file monoTriangulation.cc.

683{
684 assert( inc_chain != NULL);
685 Real** inc_array ;
686
687 if(inc_smallIndex > inc_largeIndex)
688 return; //no triangles
689 if(inc_smallIndex == inc_largeIndex)
690 {
691 if(is_increase_chain)
692 pStream->triangle(inc_chain->getVertex(inc_smallIndex), botVertex, topVertex);
693 else
694 pStream->triangle(inc_chain->getVertex(inc_smallIndex), topVertex, botVertex);
695 return;
696 }
697 Int i;
698
699 if(is_increase_chain && botVertex[1] == inc_chain->getVertex(inc_largeIndex)[1])
700 {
701 pStream->triangle(botVertex, inc_chain->getVertex(inc_largeIndex-1),
702 inc_chain->getVertex(inc_largeIndex));
703 monoTriangulation2(topVertex, botVertex, inc_chain, inc_smallIndex,
704 inc_largeIndex-1,
705 is_increase_chain,
706 pStream);
707 return;
708 }
709 else if( (!is_increase_chain) && topVertex[1] == inc_chain->getVertex(inc_smallIndex)[1])
710 {
711 pStream->triangle(topVertex, inc_chain->getVertex(inc_smallIndex+1),
712 inc_chain->getVertex(inc_smallIndex));
713 monoTriangulation2(topVertex, botVertex, inc_chain, inc_smallIndex+1,
714 inc_largeIndex, is_increase_chain, pStream);
715 return ;
716 }
717
718 inc_array = inc_chain->getArray();
719
720 reflexChain rChain(20,is_increase_chain); /*1 means the chain is increasing*/
721
722 rChain.processNewVertex(topVertex, pStream);
723
724 for(i=inc_smallIndex; i<=inc_largeIndex; i++){
725 rChain.processNewVertex(inc_array[i], pStream);
726 }
727 rChain.processNewVertex(botVertex, pStream);
728
729}
return
Definition: dirsup.c:529
void triangle(Real A[2], Real B[2], Real C[2])
Real ** getArray()
Real * getVertex(Int i)
float Real
Definition: definitions.h:36
#define NULL
Definition: types.h:112
#define assert(x)
Definition: debug.h:53
void monoTriangulation2(Real *topVertex, Real *botVertex, vertexArray *inc_chain, Int inc_smallIndex, Int inc_largeIndex, Int is_increase_chain, primStream *pStream)

Referenced by monoTriangulation2(), sampleBotLeftWithGridLinePost(), sampleBotRightWithGridLinePost(), sampleCompBot(), sampleCompTop(), sampleLeftOneGridStep(), sampleLeftOneGridStepNoMiddle(), sampleLeftSingleTrimEdgeRegion(), sampleRightOneGridStep(), sampleRightOneGridStepNoMiddle(), sampleRightSingleTrimEdgeRegion(), sampleTopLeftWithGridLinePost(), and sampleTopRightWithGridLinePost().

◆ monoTriangulationFun()

void monoTriangulationFun ( directedLine monoPolygon,
Int(*)(Real *, Real *)  compFun,
primStream pStream 
)

Definition at line 577 of file monoTriangulation.cc.

578{
579 Int i;
580 /*find the top vertex, bottom vertex, inccreasing chain, and decreasing chain,
581 *then call monoTriangulationRec
582 */
583 directedLine* tempV;
584 directedLine* topV;
585 directedLine* botV;
586 topV = botV = monoPolygon;
587 for(tempV = monoPolygon->getNext(); tempV != monoPolygon; tempV = tempV->getNext())
588 {
589 if(compFun(topV->head(), tempV->head())<0) {
590 topV = tempV;
591 }
592 if(compFun(botV->head(), tempV->head())>0) {
593 botV = tempV;
594 }
595 }
596
597 /*creat increase and decrease chains*/
598 vertexArray inc_chain(20); /*this is a dynamic array*/
599 for(i=1; i<=topV->get_npoints()-2; i++) { /*the first vertex is the top vertex which doesn't belong to inc_chain*/
600 inc_chain.appendVertex(topV->getVertex(i));
601 }
602 for(tempV = topV->getNext(); tempV != botV; tempV = tempV->getNext())
603 {
604 for(i=0; i<=tempV->get_npoints()-2; i++){
605 inc_chain.appendVertex(tempV->getVertex(i));
606 }
607 }
608
609 vertexArray dec_chain(20);
610 for(tempV = topV->getPrev(); tempV != botV; tempV = tempV->getPrev())
611 {
612 for(i=tempV->get_npoints()-2; i>=0; i--){
613 dec_chain.appendVertex(tempV->getVertex(i));
614 }
615 }
616 for(i=botV->get_npoints()-2; i>=1; i--){
617 dec_chain.appendVertex(tempV->getVertex(i));
618 }
619
620 if (!(0 == inc_chain.getNumElements() && 0 == dec_chain.getNumElements())) {
621 monoTriangulationRecFun(topV->head(), botV->head(), &inc_chain, 0,
622 &dec_chain, 0, compFun, pStream);
623 }
624}
void monoTriangulationRecFun(Real *topVertex, Real *botVertex, vertexArray *inc_chain, Int inc_current, vertexArray *dec_chain, Int dec_current, Int(*compFun)(Real *, Real *), primStream *pStream)

Referenced by monoTriangulationOpt(), monoTriangulationRecGenOpt(), and sampleMonoPoly().

◆ monoTriangulationFunBackend()

void monoTriangulationFunBackend ( Arc_ptr  loop,
Int(*)(Real *, Real *)  compFun,
Backend backend 
)

Definition at line 253 of file monoTriangulationBackend.cc.

254{
255 Int i;
256 /*find the top vertex, bottom vertex, inccreasing chain, and decreasing chain,
257 *then call monoTriangulationRec
258 */
259 Arc_ptr tempV;
260 Arc_ptr topV;
261 Arc_ptr botV;
262 topV = botV = loop;
263 for(tempV = loop->next; tempV != loop; tempV = tempV->next)
264 {
265 if(compFun(topV->tail(), tempV->tail())<0) {
266 topV = tempV;
267 }
268 if(compFun(botV->tail(), tempV->tail())>0) {
269 botV = tempV;
270 }
271 }
272
273 /*creat increase and decrease chains*/
274 vertexArray inc_chain(20); /*this is a dynamic array*/
275 for(i=1; i<=topV->pwlArc->npts-2; i++) { /*the first vertex is the top vertex which doesn't belong to inc_chain*/
276 inc_chain.appendVertex(topV->pwlArc->pts[i].param);
277 }
278 for(tempV = topV->next; tempV != botV; tempV = tempV->next)
279 {
280 for(i=0; i<=tempV->pwlArc->npts-2; i++){
281 inc_chain.appendVertex(tempV->pwlArc->pts[i].param);
282 }
283 }
284
285 vertexArray dec_chain(20);
286 for(tempV = topV->prev; tempV != botV; tempV = tempV->prev)
287 {
288 for(i=tempV->pwlArc->npts-2; i>=0; i--){
289 dec_chain.appendVertex(tempV->pwlArc->pts[i].param);
290 }
291 }
292 for(i=botV->pwlArc->npts-2; i>=1; i--){
293 dec_chain.appendVertex(tempV->pwlArc->pts[i].param);
294 }
295
296 monoTriangulationRecFunBackend(topV->tail(), botV->tail(), &inc_chain, 0, &dec_chain, 0, compFun, backend);
297
298}
class Arc * Arc_ptr
Definition: arc.h:50
void monoTriangulationRecFunBackend(Real *topVertex, Real *botVertex, vertexArray *inc_chain, Int inc_current, vertexArray *dec_chain, Int dec_current, Int(*compFun)(Real *, Real *), Backend *backend)

Referenced by Slicer::slice_new().

◆ monoTriangulationOpt()

void monoTriangulationOpt ( directedLine poly,
primStream pStream 
)

Definition at line 55 of file monoTriangulation.cc.

56{
57 Int n_cusps;
58 Int n_edges = poly->numEdges();
59 directedLine** cusps = (directedLine**) malloc(sizeof(directedLine*)*n_edges);
60 assert(cusps);
61 findInteriorCuspsX(poly, n_cusps, cusps);
62 if(n_cusps ==0) //u monotine
63 {
64 monoTriangulationFun(poly, compV2InX, pStream);
65 }
66 else if(n_cusps == 1) // one interior cusp
67 {
68 directedLine* new_polygon = polygonConvert(cusps[0]);
70 //<other> should NOT be null unless there are self-intersecting
71 //trim curves. In that case, we don't want to core dump, instead,
72 //we triangulate anyway, and print out error message.
73 if(other == NULL)
74 {
75 monoTriangulationFun(poly, compV2InX, pStream);
76 }
77 else
78 {
79 directedLine* ret_p1;
80 directedLine* ret_p2;
81
82 new_polygon->connectDiagonal_2slines(new_polygon, other,
83 &ret_p1,
84 &ret_p2,
85 new_polygon);
86
87 monoTriangulationFun(ret_p1, compV2InX, pStream);
88 monoTriangulationFun(ret_p2, compV2InX, pStream);
89
92 }
93 }
94 else
95 {
96 //we need a general partitionX funtion (supposed to be in partitionX.C,
97 //not implemented yet. XXX
98 monoTriangulationFun(poly, compV2InY, pStream);
99 }
100
101 free(cusps);
102}
void deleteSinglePolygonWithSline()
void connectDiagonal_2slines(directedLine *v1, directedLine *v2, directedLine **ret_p1, directedLine **ret_p2, directedLine *list)
#define free
Definition: debug_ros.c:5
#define malloc
Definition: debug_ros.c:4
Int compV2InX(Real A[2], Real B[2])
directedLine * polygonConvert(directedLine *polygon)
void monoTriangulationFun(directedLine *monoPolygon, Int(*compFun)(Real *, Real *), primStream *pStream)
int other
Definition: msacm.c:1376
void findInteriorCuspsX(directedLine *polygon, Int &ret_n_interior_cusps, directedLine **ret_interior_cusps)
Definition: partitionX.cc:121
directedLine * findDiagonal_singleCuspX(directedLine *cusp)
Definition: partitionX.cc:137

Referenced by sampleLeftOneGridStep(), and sampleRightOneGridStep().

◆ monoTriangulationRec() [1/3]

void monoTriangulationRec ( directedLine inc_chain,
Int  inc_index,
directedLine dec_chain,
Int  dec_index,
directedLine topVertex,
Int  top_index,
directedLine botVertex,
primStream pStream 
)

Definition at line 1033 of file monoTriangulation.cc.

1038{
1039 Int i;
1040 directedLine *temp, *oldtemp = NULL;
1041 Int tempIndex, oldtempIndex = 0;
1042
1043 assert(inc_chain != NULL && dec_chain != NULL);
1044
1045 if(inc_chain == botVertex) {
1046 reflexChain rChain(20, 0);
1047 rChain.processNewVertex(topVertex->getVertex(top_index), pStream);
1048 for(i=dec_index; i< dec_chain->get_npoints(); i++){
1049 rChain.processNewVertex(dec_chain->getVertex(i), pStream);
1050 }
1051 for(temp = dec_chain->getPrev(); temp != botVertex; temp = temp->getPrev())
1052 {
1053 for(i=0; i<temp->get_npoints(); i++){
1054 rChain.processNewVertex(temp->getVertex(i), pStream);
1055 }
1056 }
1057 }
1058 else if(dec_chain==botVertex) {
1059 reflexChain rChain(20, 1);
1060 rChain.processNewVertex(topVertex->getVertex(top_index), pStream);
1061 for(i=inc_index; i< inc_chain->get_npoints(); i++){
1062 rChain.processNewVertex(inc_chain->getVertex(i), pStream);
1063 }
1064 for(temp = inc_chain->getPrev(); temp != botVertex; temp = temp->getNext())
1065 {
1066 for(i=0; i<temp->get_npoints(); i++){
1067 rChain.processNewVertex(temp->getVertex(i), pStream);
1068 }
1069 }
1070 }
1071 else /*neither reached the bottom*/{
1072 if(compV2InY(inc_chain->getVertex(inc_index), dec_chain->getVertex(dec_index)) <=0) {
1073 reflexChain rChain(20, 0);
1074 rChain.processNewVertex(topVertex -> getVertex(top_index), pStream);
1075 temp = dec_chain;
1076 tempIndex = dec_index;
1077 while( compV2InY(inc_chain->getVertex(inc_index), temp->getVertex(tempIndex))<=0) {
1078 oldtemp = temp;
1079 oldtempIndex = tempIndex;
1080 rChain.processNewVertex(temp->getVertex(tempIndex), pStream);
1081
1082 if(tempIndex == temp->get_npoints()-1){
1083 tempIndex = 0;
1084 temp = temp->getPrev();
1085 }
1086 else{
1087 tempIndex++;
1088 }
1089 }
1090 rChain.outputFan(inc_chain->getVertex(inc_index), pStream);
1091 monoTriangulationRec(inc_chain, inc_index, temp, tempIndex, oldtemp, oldtempIndex, botVertex, pStream);
1092 }
1093 else /* >0*/ {
1094 reflexChain rChain(20, 1);
1095 rChain.processNewVertex(topVertex -> getVertex(top_index), pStream);
1096 temp = inc_chain;
1097 tempIndex = inc_index;
1098 while( compV2InY(temp->getVertex(tempIndex), dec_chain->getVertex(dec_index))>0){
1099 oldtemp = temp;
1100 oldtempIndex = tempIndex;
1101 rChain.processNewVertex(temp->getVertex(tempIndex), pStream);
1102
1103 if(tempIndex == temp->get_npoints()-1){
1104 tempIndex = 0;
1105 temp = temp->getNext();
1106 }
1107 else{
1108 tempIndex++;
1109 }
1110 }
1111 rChain.outputFan(dec_chain->getVertex(dec_index), pStream);
1112 monoTriangulationRec(temp, tempIndex, dec_chain, dec_index, oldtemp, oldtempIndex, botVertex, pStream);
1113 }
1114 } /*end case neither reached the bottom*/
1115}
static calc_node_t temp
Definition: rpn_ieee.c:38

◆ monoTriangulationRec() [2/3]

void monoTriangulationRec ( Real topVertex,
Real botVertex,
vertexArray inc_chain,
Int  inc_current,
vertexArray dec_chain,
Int  dec_current,
Backend backend 
)

Definition at line 159 of file monoTriangulationBackend.cc.

163{
164 assert( inc_chain != NULL && dec_chain != NULL);
165 assert( ! (inc_current>=inc_chain->getNumElements() &&
166 dec_current>=dec_chain->getNumElements()));
167 Int inc_nVertices;
168 Int dec_nVertices;
169 Real** inc_array ;
170 Real** dec_array ;
171 Int i;
172 assert( ! ( (inc_chain==NULL) && (dec_chain==NULL)));
173
174 if(inc_current>=inc_chain->getNumElements()) /*no more vertices on inc_chain*/
175 {
176
177 dec_array = dec_chain->getArray();
178 dec_nVertices = dec_chain->getNumElements();
179 reflexChain rChain(20,0);
180 /*put the top vertex into the reflex chain*/
181 rChain.processNewVertex(topVertex, backend);
182 /*process all the vertices on the dec_chain*/
183 for(i=dec_current; i<dec_nVertices; i++){
184 rChain.processNewVertex(dec_array[i], backend);
185 }
186 /*process the bottom vertex*/
187 rChain.processNewVertex(botVertex, backend);
188
189 }
190 else if(dec_current>= dec_chain->getNumElements()) /*no more vertices on dec_chain*/
191 {
192 inc_array = inc_chain->getArray();
193 inc_nVertices= inc_chain->getNumElements();
194 reflexChain rChain(20,1);
195 /*put the top vertex into the reflex chain*/
196 rChain.processNewVertex(topVertex, backend);
197 /*process all the vertices on the inc_chain*/
198 for(i=inc_current; i<inc_nVertices; i++){
199 rChain.processNewVertex(inc_array[i], backend);
200 }
201 /*process the bottom vertex*/
202 rChain.processNewVertex(botVertex, backend);
203 }
204 else /*neither chain is empty*/
205 {
206 inc_array = inc_chain -> getArray();
207 dec_array = dec_chain -> getArray();
208 inc_nVertices= inc_chain->getNumElements();
209 dec_nVertices= dec_chain->getNumElements();
210 /*if top of inc_chain is 'lower' than top of dec_chain, process all the
211 *vertices on the dec_chain which are higher than top of inc_chain
212 */
213 if(compV2InY(inc_array[inc_current], dec_array[dec_current]) <= 0)
214 {
215
216 reflexChain rChain(20, 0);
217 rChain.processNewVertex(topVertex, backend);
218 for(i=dec_current; i<dec_nVertices; i++)
219 {
220 if(compV2InY(inc_array[inc_current], dec_array[i]) <= 0)
221 rChain.processNewVertex(dec_array[i], backend);
222 else
223 break;
224 }
225 rChain.outputFan(inc_array[inc_current], backend);
226 monoTriangulationRec(dec_array[i-1], botVertex,
227 inc_chain, inc_current,
228 dec_chain, i,
229 backend);
230 }
231 else /*compV2InY(inc_array[inc_current], dec_array[dec_current]) > 0*/
232 {
233
234 reflexChain rChain(20, 1);
235 rChain.processNewVertex(topVertex, backend);
236 for(i=inc_current; i<inc_nVertices; i++)
237 {
238 if(compV2InY(inc_array[i], dec_array[dec_current]) >0)
239 rChain.processNewVertex(inc_array[i], backend);
240 else
241 break;
242 }
243 rChain.outputFan(dec_array[dec_current], backend);
244 monoTriangulationRec(inc_array[i-1], botVertex,
245 inc_chain, i,
246 dec_chain, dec_current,
247 backend);
248 }
249 }/*end case neither is empty*/
250}
void monoTriangulationRec(Real *topVertex, Real *botVertex, vertexArray *inc_chain, Int inc_current, vertexArray *dec_chain, Int dec_current, Backend *backend)

Referenced by monoTriangulationLoop(), monoTriangulationRec(), and sampleMonoPolyRec().

◆ monoTriangulationRec() [3/3]

void monoTriangulationRec ( Real topVertex,
Real botVertex,
vertexArray inc_chain,
Int  inc_current,
vertexArray dec_chain,
Int  dec_current,
primStream pStream 
)

Definition at line 929 of file monoTriangulation.cc.

933{
934 assert( inc_chain != NULL && dec_chain != NULL);
935 assert( ! (inc_current>=inc_chain->getNumElements() &&
936 dec_current>=dec_chain->getNumElements()));
937 Int inc_nVertices;
938 Int dec_nVertices;
939 Real** inc_array ;
940 Real** dec_array ;
941 Int i;
942 assert( ! ( (inc_chain==NULL) && (dec_chain==NULL)));
943
944 if(inc_current>=inc_chain->getNumElements()) /*no more vertices on inc_chain*/
945 {
946
947 dec_array = dec_chain->getArray();
948 dec_nVertices = dec_chain->getNumElements();
949 reflexChain rChain(20,0);
950 /*put the top vertex into the reflex chain*/
951 rChain.processNewVertex(topVertex, pStream);
952 /*process all the vertices on the dec_chain*/
953 for(i=dec_current; i<dec_nVertices; i++){
954 rChain.processNewVertex(dec_array[i], pStream);
955 }
956 /*process the bottom vertex*/
957 rChain.processNewVertex(botVertex, pStream);
958
959 }
960 else if(dec_current>= dec_chain->getNumElements()) /*no more vertices on dec_chain*/
961 {
962 inc_array = inc_chain->getArray();
963 inc_nVertices= inc_chain->getNumElements();
964 reflexChain rChain(20,1);
965 /*put the top vertex into the reflex chain*/
966 rChain.processNewVertex(topVertex, pStream);
967 /*process all the vertices on the inc_chain*/
968 for(i=inc_current; i<inc_nVertices; i++){
969 rChain.processNewVertex(inc_array[i], pStream);
970 }
971 /*process the bottom vertex*/
972 rChain.processNewVertex(botVertex, pStream);
973 }
974 else /*neither chain is empty*/
975 {
976 inc_array = inc_chain -> getArray();
977 dec_array = dec_chain -> getArray();
978 inc_nVertices= inc_chain->getNumElements();
979 dec_nVertices= dec_chain->getNumElements();
980 /*if top of inc_chain is 'lower' than top of dec_chain, process all the
981 *vertices on the dec_chain which are higher than top of inc_chain
982 */
983 if(compV2InY(inc_array[inc_current], dec_array[dec_current]) <= 0)
984 {
985
986 reflexChain rChain(20, 0);
987 rChain.processNewVertex(topVertex, pStream);
988 for(i=dec_current; i<dec_nVertices; i++)
989 {
990 if(compV2InY(inc_array[inc_current], dec_array[i]) <= 0)
991 rChain.processNewVertex(dec_array[i], pStream);
992 else
993 break;
994 }
995 rChain.outputFan(inc_array[inc_current], pStream);
996 monoTriangulationRec(dec_array[i-1], botVertex,
997 inc_chain, inc_current,
998 dec_chain, i,
999 pStream);
1000 }
1001 else /*compV2InY(inc_array[inc_current], dec_array[dec_current]) > 0*/
1002 {
1003
1004 reflexChain rChain(20, 1);
1005 rChain.processNewVertex(topVertex, pStream);
1006 for(i=inc_current; i<inc_nVertices; i++)
1007 {
1008 if(compV2InY(inc_array[i], dec_array[dec_current]) >0)
1009 rChain.processNewVertex(inc_array[i], pStream);
1010 else
1011 break;
1012 }
1013 rChain.outputFan(dec_array[dec_current], pStream);
1014 monoTriangulationRec(inc_array[i-1], botVertex,
1015 inc_chain, i,
1016 dec_chain, dec_current,
1017 pStream);
1018 }
1019 }/*end case neither is empty*/
1020}

Referenced by monoTriangulation(), monoTriangulationRec(), and monoTriangulationRecOpt().

◆ monoTriangulationRecFun()

void monoTriangulationRecFun ( Real topVertex,
Real botVertex,
vertexArray inc_chain,
Int  inc_current,
vertexArray dec_chain,
Int  dec_current,
Int(*)(Real *, Real *)  compFun,
primStream pStream 
)

Definition at line 832 of file monoTriangulation.cc.

837{
838 assert( inc_chain != NULL && dec_chain != NULL);
839 assert( ! (inc_current>=inc_chain->getNumElements() &&
840 dec_current>=dec_chain->getNumElements()));
841 Int inc_nVertices;
842 Int dec_nVertices;
843 Real** inc_array ;
844 Real** dec_array ;
845 Int i;
846 assert( ! ( (inc_chain==NULL) && (dec_chain==NULL)));
847
848 if(inc_current>=inc_chain->getNumElements()) /*no more vertices on inc_chain*/
849 {
850
851 dec_array = dec_chain->getArray();
852 dec_nVertices = dec_chain->getNumElements();
853 reflexChain rChain(20,0);
854 /*put the top vertex into the reflex chain*/
855 rChain.processNewVertex(topVertex, pStream);
856 /*process all the vertices on the dec_chain*/
857 for(i=dec_current; i<dec_nVertices; i++){
858 rChain.processNewVertex(dec_array[i], pStream);
859 }
860 /*process the bottom vertex*/
861 rChain.processNewVertex(botVertex, pStream);
862
863 }
864 else if(dec_current>= dec_chain->getNumElements()) /*no more vertices on dec_chain*/
865 {
866 inc_array = inc_chain->getArray();
867 inc_nVertices= inc_chain->getNumElements();
868 reflexChain rChain(20,1);
869 /*put the top vertex into the reflex chain*/
870 rChain.processNewVertex(topVertex, pStream);
871 /*process all the vertices on the inc_chain*/
872 for(i=inc_current; i<inc_nVertices; i++){
873 rChain.processNewVertex(inc_array[i], pStream);
874 }
875 /*process the bottom vertex*/
876 rChain.processNewVertex(botVertex, pStream);
877 }
878 else /*neither chain is empty*/
879 {
880 inc_array = inc_chain -> getArray();
881 dec_array = dec_chain -> getArray();
882 inc_nVertices= inc_chain->getNumElements();
883 dec_nVertices= dec_chain->getNumElements();
884 /*if top of inc_chain is 'lower' than top of dec_chain, process all the
885 *vertices on the dec_chain which are higher than top of inc_chain
886 */
887 if(compFun(inc_array[inc_current], dec_array[dec_current]) <= 0)
888 {
889
890 reflexChain rChain(20, 0);
891 rChain.processNewVertex(topVertex, pStream);
892 for(i=dec_current; i<dec_nVertices; i++)
893 {
894 if(compFun(inc_array[inc_current], dec_array[i]) <= 0)
895 rChain.processNewVertex(dec_array[i], pStream);
896 else
897 break;
898 }
899 rChain.outputFan(inc_array[inc_current], pStream);
900 monoTriangulationRecFun(dec_array[i-1], botVertex,
901 inc_chain, inc_current,
902 dec_chain, i,
903 compFun,
904 pStream);
905 }
906 else /*compFun(inc_array[inc_current], dec_array[dec_current]) > 0*/
907 {
908
909 reflexChain rChain(20, 1);
910 rChain.processNewVertex(topVertex, pStream);
911 for(i=inc_current; i<inc_nVertices; i++)
912 {
913 if(compFun(inc_array[i], dec_array[dec_current]) >0)
914 rChain.processNewVertex(inc_array[i], pStream);
915 else
916 break;
917 }
918 rChain.outputFan(dec_array[dec_current], pStream);
919 monoTriangulationRecFun(inc_array[i-1], botVertex,
920 inc_chain, i,
921 dec_chain, dec_current,
922 compFun,
923 pStream);
924 }
925 }/*end case neither is empty*/
926}

Referenced by monoTriangulationFun(), and monoTriangulationRecFun().

◆ monoTriangulationRecFunBackend()

void monoTriangulationRecFunBackend ( Real topVertex,
Real botVertex,
vertexArray inc_chain,
Int  inc_current,
vertexArray dec_chain,
Int  dec_current,
Int(*)(Real *, Real *)  compFun,
Backend backend 
)

Definition at line 303 of file monoTriangulationBackend.cc.

308{
309 assert( inc_chain != NULL && dec_chain != NULL);
310 assert( ! (inc_current>=inc_chain->getNumElements() &&
311 dec_current>=dec_chain->getNumElements()));
312 Int inc_nVertices;
313 Int dec_nVertices;
314 Real** inc_array ;
315 Real** dec_array ;
316 Int i;
317 assert( ! ( (inc_chain==NULL) && (dec_chain==NULL)));
318
319 if(inc_current>=inc_chain->getNumElements()) /*no more vertices on inc_chain*/
320 {
321
322 dec_array = dec_chain->getArray();
323 dec_nVertices = dec_chain->getNumElements();
324 reflexChain rChain(20,0);
325 /*put the top vertex into the reflex chain*/
326 rChain.processNewVertex(topVertex, backend);
327 /*process all the vertices on the dec_chain*/
328 for(i=dec_current; i<dec_nVertices; i++){
329 rChain.processNewVertex(dec_array[i], backend);
330 }
331 /*process the bottom vertex*/
332 rChain.processNewVertex(botVertex, backend);
333
334 }
335 else if(dec_current>= dec_chain->getNumElements()) /*no more vertices on dec_chain*/
336 {
337 inc_array = inc_chain->getArray();
338 inc_nVertices= inc_chain->getNumElements();
339 reflexChain rChain(20,1);
340 /*put the top vertex into the reflex chain*/
341 rChain.processNewVertex(topVertex, backend);
342 /*process all the vertices on the inc_chain*/
343 for(i=inc_current; i<inc_nVertices; i++){
344 rChain.processNewVertex(inc_array[i], backend);
345 }
346 /*process the bottom vertex*/
347 rChain.processNewVertex(botVertex, backend);
348 }
349 else /*neither chain is empty*/
350 {
351 inc_array = inc_chain -> getArray();
352 dec_array = dec_chain -> getArray();
353 inc_nVertices= inc_chain->getNumElements();
354 dec_nVertices= dec_chain->getNumElements();
355 /*if top of inc_chain is 'lower' than top of dec_chain, process all the
356 *vertices on the dec_chain which are higher than top of inc_chain
357 */
358 if(compFun(inc_array[inc_current], dec_array[dec_current]) <= 0)
359 {
360
361 reflexChain rChain(20, 0);
362 rChain.processNewVertex(topVertex, backend);
363 for(i=dec_current; i<dec_nVertices; i++)
364 {
365 if(compFun(inc_array[inc_current], dec_array[i]) <= 0)
366 rChain.processNewVertex(dec_array[i], backend);
367 else
368 break;
369 }
370 rChain.outputFan(inc_array[inc_current], backend);
371 monoTriangulationRecFunBackend(dec_array[i-1], botVertex,
372 inc_chain, inc_current,
373 dec_chain, i,
374 compFun,
375 backend);
376 }
377 else /*compFun(inc_array[inc_current], dec_array[dec_current]) > 0*/
378 {
379
380 reflexChain rChain(20, 1);
381 rChain.processNewVertex(topVertex, backend);
382 for(i=inc_current; i<inc_nVertices; i++)
383 {
384 if(compFun(inc_array[i], dec_array[dec_current]) >0)
385 rChain.processNewVertex(inc_array[i], backend);
386 else
387 break;
388 }
389 rChain.outputFan(dec_array[dec_current], backend);
390 monoTriangulationRecFunBackend(inc_array[i-1], botVertex,
391 inc_chain, i,
392 dec_chain, dec_current,
393 compFun,
394 backend);
395 }
396 }/*end case neither is empty*/
397}

Referenced by monoTriangulationFunBackend(), and monoTriangulationRecFunBackend().

◆ monoTriangulationRecFunGen()

void monoTriangulationRecFunGen ( Real topVertex,
Real botVertex,
vertexArray inc_chain,
Int  inc_current,
Int  inc_end,
vertexArray dec_chain,
Int  dec_current,
Int  dec_end,
Int(*)(Real *, Real *)  compFun,
primStream pStream 
)

Definition at line 734 of file monoTriangulation.cc.

739{
740 assert( inc_chain != NULL && dec_chain != NULL);
741 assert( ! (inc_current> inc_end &&
742 dec_current> dec_end));
743 /*
744 Int inc_nVertices;
745 Int dec_nVertices;
746 */
747 Real** inc_array ;
748 Real** dec_array ;
749 Int i;
750 assert( ! ( (inc_chain==NULL) && (dec_chain==NULL)));
751
752 if(inc_current> inc_end) /*no more vertices on inc_chain*/
753 {
754
755 dec_array = dec_chain->getArray();
756 reflexChain rChain(20,0);
757 /*put the top vertex into the reflex chain*/
758 rChain.processNewVertex(topVertex, pStream);
759 /*process all the vertices on the dec_chain*/
760 for(i=dec_current; i<=dec_end; i++){
761 rChain.processNewVertex(dec_array[i], pStream);
762 }
763 /*process the bottom vertex*/
764 rChain.processNewVertex(botVertex, pStream);
765
766 }
767 else if(dec_current> dec_end) /*no more vertices on dec_chain*/
768 {
769 inc_array = inc_chain->getArray();
770 reflexChain rChain(20,1);
771 /*put the top vertex into the reflex chain*/
772 rChain.processNewVertex(topVertex, pStream);
773 /*process all the vertices on the inc_chain*/
774 for(i=inc_current; i<=inc_end; i++){
775 rChain.processNewVertex(inc_array[i], pStream);
776 }
777 /*process the bottom vertex*/
778 rChain.processNewVertex(botVertex, pStream);
779 }
780 else /*neither chain is empty*/
781 {
782 inc_array = inc_chain -> getArray();
783 dec_array = dec_chain -> getArray();
784
785 /*if top of inc_chain is 'lower' than top of dec_chain, process all the
786 *vertices on the dec_chain which are higher than top of inc_chain
787 */
788 if(compFun(inc_array[inc_current], dec_array[dec_current]) <= 0)
789 {
790
791 reflexChain rChain(20, 0);
792 rChain.processNewVertex(topVertex, pStream);
793 for(i=dec_current; i<=dec_end; i++)
794 {
795 if(compFun(inc_array[inc_current], dec_array[i]) <= 0)
796 rChain.processNewVertex(dec_array[i], pStream);
797 else
798 break;
799 }
800 rChain.outputFan(inc_array[inc_current], pStream);
801 monoTriangulationRecFunGen(dec_array[i-1], botVertex,
802 inc_chain, inc_current, inc_end,
803 dec_chain, i, dec_end,
804 compFun,
805 pStream);
806 }
807 else /*compFun(inc_array[inc_current], dec_array[dec_current]) > 0*/
808 {
809
810 reflexChain rChain(20, 1);
811 rChain.processNewVertex(topVertex, pStream);
812 for(i=inc_current; i<=inc_end; i++)
813 {
814 if(compFun(inc_array[i], dec_array[dec_current]) >0)
815 rChain.processNewVertex(inc_array[i], pStream);
816 else
817 break;
818 }
819 rChain.outputFan(dec_array[dec_current], pStream);
820 monoTriangulationRecFunGen(inc_array[i-1], botVertex,
821 inc_chain, i,inc_end,
822 dec_chain, dec_current,dec_end,
823 compFun,
824 pStream);
825 }
826 }/*end case neither is empty*/
827}
void monoTriangulationRecFunGen(Real *topVertex, Real *botVertex, vertexArray *inc_chain, Int inc_current, Int inc_end, vertexArray *dec_chain, Int dec_current, Int dec_end, Int(*compFun)(Real *, Real *), primStream *pStream)

Referenced by monoTriangulationRecFunGen(), and monoTriangulationRecGenOpt().

◆ monoTriangulationRecGen()

void monoTriangulationRecGen ( Real topVertex,
Real botVertex,
vertexArray inc_chain,
Int  inc_current,
Int  inc_end,
vertexArray dec_chain,
Int  dec_current,
Int  dec_end,
primStream pStream 
)

Definition at line 492 of file monoTriangulation.cc.

496{
497 Real** inc_array ;
498 Real** dec_array ;
499 Int i;
500
501 if(inc_current > inc_end && dec_current>dec_end)
502 return;
503 else if(inc_current>inc_end) /*no more vertices on inc_chain*/
504 {
505 dec_array = dec_chain->getArray();
506 reflexChain rChain(100,0);
507 /*put the top vertex into the reflex chain*/
508 rChain.processNewVertex(topVertex, pStream);
509 /*process all the vertices on the dec_chain*/
510 for(i=dec_current; i<=dec_end; i++){
511 rChain.processNewVertex(dec_array[i], pStream);
512 }
513 /*process the bottom vertex*/
514 rChain.processNewVertex(botVertex, pStream);
515 }
516 else if(dec_current> dec_end) /*no more vertices on dec_chain*/
517 {
518 inc_array = inc_chain->getArray();
519
520 reflexChain rChain(100,1);
521 /*put the top vertex into the reflex chain*/
522 rChain.processNewVertex(topVertex, pStream);
523 /*process all the vertices on the inc_chain*/
524 for(i=inc_current; i<=inc_end; i++){
525 rChain.processNewVertex(inc_array[i], pStream);
526 }
527 /*process the bottom vertex*/
528 rChain.processNewVertex(botVertex, pStream);
529 }
530 else /*neither chain is empty*/
531 {
532 inc_array = inc_chain -> getArray();
533 dec_array = dec_chain -> getArray();
534
535 /*if top of inc_chain is 'lower' than top of dec_chain, process all the
536 *vertices on the dec_chain which are higher than top of inc_chain
537 */
538 if(compV2InY(inc_array[inc_current], dec_array[dec_current]) <= 0)
539 {
540
541 reflexChain rChain(100, 0);
542 rChain.processNewVertex(topVertex, pStream);
543 for(i=dec_current; i<=dec_end; i++)
544 {
545 if(compV2InY(inc_array[inc_current], dec_array[i]) <= 0)
546 rChain.processNewVertex(dec_array[i], pStream);
547 else
548 break;
549 }
550 rChain.outputFan(inc_array[inc_current], pStream);
551 monoTriangulationRecGen(dec_array[i-1], botVertex,
552 inc_chain, inc_current, inc_end,
553 dec_chain, i, dec_end,
554 pStream);
555 }
556 else /*compV2InY(inc_array[inc_current], dec_array[dec_current]) > 0*/
557 {
558
559 reflexChain rChain(100, 1);
560 rChain.processNewVertex(topVertex, pStream);
561 for(i=inc_current; i<=inc_end; i++)
562 {
563 if(compV2InY(inc_array[i], dec_array[dec_current]) >0)
564 rChain.processNewVertex(inc_array[i], pStream);
565 else
566 break;
567 }
568 rChain.outputFan(dec_array[dec_current], pStream);
569 monoTriangulationRecGen(inc_array[i-1], botVertex,
570 inc_chain, i, inc_end,
571 dec_chain, dec_current,dec_end,
572 pStream);
573 }
574 }/*end case neither is empty*/
575}
void monoTriangulationRecGen(Real *topVertex, Real *botVertex, vertexArray *inc_chain, Int inc_current, Int inc_end, vertexArray *dec_chain, Int dec_current, Int dec_end, primStream *pStream)

Referenced by monoTriangulationRecGen(), monoTriangulationRecGenOpt(), monoTriangulationRecOpt(), sampleCompBot(), sampleCompTop(), sampleLeftSingleTrimEdgeRegionGen(), and sampleRightSingleTrimEdgeRegionGen().

◆ monoTriangulationRecGenOpt()

void monoTriangulationRecGenOpt ( Real topVertex,
Real botVertex,
vertexArray inc_chain,
Int  inc_current,
Int  inc_end,
vertexArray dec_chain,
Int  dec_current,
Int  dec_end,
primStream pStream 
)

Definition at line 332 of file monoTriangulation.cc.

336{
337 Int i;
338 //copy this to a polygon: directedLine Lioop
339 sampledLine* sline;
340 directedLine* dline;
341 directedLine* poly;
342
343 if(inc_current <= inc_end) //at least one vertex in inc_chain
344 {
345 sline = new sampledLine(topVertex, inc_chain->getVertex(inc_current));
346 poly = new directedLine(INCREASING, sline);
347 for(i=inc_current; i<=inc_end-1; i++)
348 {
349 sline = new sampledLine(inc_chain->getVertex(i), inc_chain->getVertex(i+1));
350 dline = new directedLine(INCREASING, sline);
351 poly->insert(dline);
352 }
353 sline = new sampledLine(inc_chain->getVertex(inc_end), botVertex);
354 dline = new directedLine(INCREASING, sline);
355 poly->insert(dline);
356 }
357 else //inc_chian is empty
358 {
359 sline = new sampledLine(topVertex, botVertex);
360 dline = new directedLine(INCREASING, sline);
361 poly = dline;
362 }
363
364 assert(poly != NULL);
365
366 if(dec_current <= dec_end) //at least on vertex in dec_Chain
367 {
368 sline = new sampledLine(botVertex, dec_chain->getVertex(dec_end));
369 dline = new directedLine(INCREASING, sline);
370 poly->insert(dline);
371 for(i=dec_end; i>dec_current; i--)
372 {
373 sline = new sampledLine(dec_chain->getVertex(i), dec_chain->getVertex(i-1));
374 dline = new directedLine(INCREASING, sline);
375 poly->insert(dline);
376 }
377 sline = new sampledLine(dec_chain->getVertex(dec_current), topVertex);
378 dline = new directedLine(INCREASING, sline);
379 poly->insert(dline);
380 }
381 else //dec_chain is empty
382 {
383 sline = new sampledLine(botVertex, topVertex);
384 dline = new directedLine(INCREASING, sline);
385 poly->insert(dline);
386 }
387
388 {
389 Int n_cusps;
390 Int n_edges = poly->numEdges();
391 directedLine** cusps = (directedLine**) malloc(sizeof(directedLine*)*n_edges);
392 assert(cusps);
393 findInteriorCuspsX(poly, n_cusps, cusps);
394
395 if(n_cusps ==0) //u monotine
396 {
397 monoTriangulationFun(poly, compV2InX, pStream);
398 }
399 else if(n_cusps == 1) // one interior cusp
400 {
401 directedLine* new_polygon = polygonConvert(cusps[0]);
403 //<other> should NOT be null unless there are self-intersecting
404 //trim curves. In that case, we don't want to core dump, instead,
405 //we triangulate anyway, and print out error message.
406 if(other == NULL)
407 {
408 monoTriangulationFun(poly, compV2InX, pStream);
409 }
410 else
411 {
412 directedLine* ret_p1;
413 directedLine* ret_p2;
414
415 new_polygon->connectDiagonal_2slines(new_polygon, other,
416 &ret_p1,
417 &ret_p2,
418 new_polygon);
419
420 monoTriangulationFun(ret_p1, compV2InX, pStream);
421 monoTriangulationFun(ret_p2, compV2InX, pStream);
422
425 }
426 }
427 else
428 {
429 //we need a general partitionX funtion (supposed to be in partitionX.C,
430 //not implemented yet. XXX
431 //monoTriangulationFun(poly, compV2InY, pStream);
432
433 directedLine* new_polygon = polygonConvert(poly);
434 directedLine* list = monoPolyPart(new_polygon);
435 for(directedLine* temp = list; temp != NULL; temp = temp->getNextPolygon())
436 {
438 }
439 //clean up
440 list->deletePolygonListWithSline();
441
442 }
443
444 free(cusps);
445 /*
446 if(numInteriorCuspsX(poly) == 0) //is u monotone
447 monoTriangulationFun(poly, compV2InX, pStream);
448 else //it is not u motone
449 monoTriangulationFun(poly, compV2InY, pStream);
450 */
451 //clean up space
453 return;
454 }
455
456 //apparently the following code is not reachable,
457 //it is for test purpose
458 if(inc_current > inc_end || dec_current>dec_end)
459 {
460 monoTriangulationRecGen(topVertex, botVertex, inc_chain, inc_current, inc_end,
461 dec_chain, dec_current, dec_end,
462 pStream);
463 return;
464 }
465
466
467 if(
468 area(dec_chain->getVertex(dec_current),
469 topVertex,
470 inc_chain->getVertex(inc_current)) >=0
471 && chainConvex(inc_chain, inc_current, inc_end)
472 && chainConcave(dec_chain, dec_current, dec_end)
473 && area(inc_chain->getVertex(inc_end), botVertex, dec_chain->getVertex(dec_end)) >=0
474 )
475 {
476 monoTriangulationRecFunGen(topVertex, botVertex,
477 inc_chain, inc_current, inc_end,
478 dec_chain, dec_current, dec_end,
479 compV2InX, pStream);
480 }
481 else
482 {
483 monoTriangulationRecGen(topVertex, botVertex, inc_chain, inc_current, inc_end,
484 dec_chain, dec_current, dec_end,
485 pStream);
486 }
487}
void insert(directedLine *nl)
Definition: list.h:37
@ INCREASING
Definition: directedLine.h:39
directedLine * monoPolyPart(directedLine *polygon)
Definition: monoPolyPart.cc:80
static int chainConcave(vertexArray *dec_chain, Int dec_current, Int dec_end)
static int chainConvex(vertexArray *inc_chain, Int inc_current, Int inc_end)
static Real area(Real A[2], Real B[2], Real C[2])
Definition: polyDBG.cc:50

Referenced by sampleCompBotSimple(), sampleCompTopSimpleOpt(), sampleMonoPolyRec(), and sampleTopRightWithGridLinePost().

◆ monoTriangulationRecGenTBOpt()

void monoTriangulationRecGenTBOpt ( Real topVertex,
Real botVertex,
vertexArray inc_chain,
Int  inc_current,
Int  inc_end,
vertexArray dec_chain,
Int  dec_current,
Int  dec_end,
primStream pStream 
)

Definition at line 162 of file monoTriangulation.cc.

166{
167 pStream->triangle(topVertex, inc_chain->getVertex(inc_current), dec_chain->getVertex(dec_current));
168
169/*printf("**(%f,%f)\n", inc_chain->getArray()[0][0],inc_chain->getArray()[0][1]);*/
170 triangulateXYMonoTB(inc_end-inc_current+1, inc_chain->getArray()+inc_current, dec_end-dec_current+1, dec_chain->getArray()+dec_current, pStream);
171
172 pStream->triangle(botVertex, dec_chain->getVertex(dec_end), inc_chain->getVertex(inc_end));
173}
void triangulateXYMonoTB(Int n_left, Real **leftVerts, Int n_right, Real **rightVerts, primStream *pStream)

◆ monoTriangulationRecOpt()

void monoTriangulationRecOpt ( Real topVertex,
Real botVertex,
vertexArray left_chain,
Int  left_current,
vertexArray right_chain,
Int  right_current,
primStream pStream 
)

Definition at line 104 of file monoTriangulation.cc.

108{
109 Int i,j;
110 Int n_left = left_chain->getNumElements();
111 Int n_right = right_chain->getNumElements();
112 if(left_current>= n_left-1 ||
113 right_current>= n_right-1)
114 {
115 monoTriangulationRec(topVertex, botVertex, left_chain, left_current,
116 right_chain, right_current, pStream);
117 return;
118 }
119 //now both left and right have at least two vertices each.
120 Real left_v = left_chain->getVertex(left_current)[1];
121 Real right_v = right_chain->getVertex(right_current)[1];
122
123 if(left_v <= right_v) //first left vertex is below right
124 {
125 //find the last vertex of right which is above or equal to left
126 for(j=right_current; j<=n_right-1; j++)
127 {
128 if(right_chain->getVertex(j)[1] < left_v)
129 break;
130 }
131 monoTriangulationRecGen(topVertex, left_chain->getVertex(left_current),
132 left_chain, left_current, left_current,
133 right_chain, right_current, j-1,
134 pStream);
135 monoTriangulationRecOpt(right_chain->getVertex(j-1),
136 botVertex,
137 left_chain, left_current,
138 right_chain, j,
139 pStream);
140 }
141 else //first right vertex is strictly below left
142 {
143 //find the last vertex of left which is strictly above right
144 for(i=left_current; i<=n_left-1; i++)
145 {
146 if(left_chain->getVertex(i)[1] <= right_v)
147 break;
148 }
149 monoTriangulationRecGen(topVertex, right_chain->getVertex(right_current),
150 left_chain, left_current, i-1,
151 right_chain, right_current, right_current,
152 pStream);
153 monoTriangulationRecOpt(left_chain->getVertex(i-1),
154 botVertex,
155 left_chain, i,
156 right_chain, right_current,
157 pStream);
158 }
159}
GLsizei GLenum const GLvoid GLsizei GLenum GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLint GLint GLint GLshort GLshort GLshort GLubyte GLubyte GLubyte GLuint GLuint GLuint GLushort GLushort GLushort GLbyte GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLfloat GLint GLint GLint GLint GLshort GLshort GLshort GLshort GLubyte GLubyte GLubyte GLubyte GLuint GLuint GLuint GLuint GLushort GLushort GLushort GLushort GLboolean const GLdouble const GLfloat const GLint const GLshort const GLbyte const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLdouble const GLfloat const GLfloat const GLint const GLint const GLshort const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort GLenum GLenum GLenum GLfloat GLenum GLint GLenum GLenum GLenum GLfloat GLenum GLenum GLint GLenum GLfloat GLenum GLint GLint GLushort GLenum GLenum GLfloat GLenum GLenum GLint GLfloat const GLubyte GLenum GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLint GLint GLsizei GLsizei GLint GLenum GLenum const GLvoid GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLenum const GLdouble GLenum GLenum const GLfloat GLenum GLenum const GLint GLsizei GLuint GLfloat GLuint GLbitfield GLfloat GLint GLuint GLboolean GLenum GLfloat GLenum GLbitfield GLenum GLfloat GLfloat GLint GLint const GLfloat GLenum GLfloat GLfloat GLint GLint GLfloat GLfloat GLint GLint const GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat const GLdouble const GLfloat const GLdouble const GLfloat GLint GLint GLint j
Definition: glfuncs.h:250
void monoTriangulationRecOpt(Real *topVertex, Real *botVertex, vertexArray *left_chain, Int left_current, vertexArray *right_chain, Int right_current, primStream *pStream)

Referenced by monoTriangulationRecOpt().

◆ triangulateXYMonoTB()

void triangulateXYMonoTB ( Int  n_left,
Real **  leftVerts,
Int  n_right,
Real **  rightVerts,
primStream pStream 
)

Definition at line 181 of file monoTriangulation.cc.

184{
185
186
187 Int i,j,k,l;
188 Real* topMostV;
189
190 assert(n_left>=1 && n_right>=1);
191 if(leftVerts[0][1] >= rightVerts[0][1])
192 {
193 i=1;
194 j=0;
195 topMostV = leftVerts[0];
196 }
197 else
198 {
199 i=0;
200 j=1;
201 topMostV = rightVerts[0];
202 }
203
204 while(1)
205 {
206 if(i >= n_left) /*case1: no more in left*/
207 {
208
209 if(j<n_right-1) /*at least two vertices in right*/
210 {
211 pStream->begin();
212 pStream->insert(topMostV);
213 for(k=n_right-1; k>=j; k--)
214 pStream->insert(rightVerts[j]);
215
216 pStream->end(PRIMITIVE_STREAM_FAN);
217
218 }
219
220 break;
221 }
222 else if(j>= n_right) /*case2: no more in right*/
223 {
224
225 if(i<n_left-1) /*at least two vertices in left*/
226 {
227 pStream->begin();
228 pStream->insert(topMostV);
229
230 for(k=i; k<n_left; k++)
231 pStream->insert(leftVerts[k]);
232
233 pStream->end(PRIMITIVE_STREAM_FAN);
234 }
235
236 break;
237 }
238 else /* case3: neither is empty, plus the topMostV, there is at least one triangle to output*/
239 {
240
241 if(leftVerts[i][1] >= rightVerts[j][1])
242 {
243 pStream->begin();
244 pStream->insert(rightVerts[j]); /*the origin of this fan*/
245
246 pStream->insert(topMostV);
247
248 /*find the last k>=i such that
249 *leftverts[k][1] >= rightverts[j][1]
250 */
251 k=i;
252 while(k<n_left)
253 {
254 if(leftVerts[k][1] < rightVerts[j][1])
255 break;
256 k++;
257 }
258 k--;
259 for(l=i; l<=k; l++)
260 {
261 pStream->insert(leftVerts[l]);
262 }
263
264 pStream->end(PRIMITIVE_STREAM_FAN);
265 //update i for next loop
266 i = k+1;
267 topMostV = leftVerts[k];
268
269 }
270 else /*leftVerts[i][1] < rightVerts[j][1]*/
271 {
272 pStream->begin();
273 pStream->insert(leftVerts[i]);/*the origion of this fan*/
274
275 /*find the last k>=j such that
276 *rightverts[k][1] > leftverts[i][1]*/
277 k=j;
278 while(k< n_right)
279 {
280 if(rightVerts[k][1] <= leftVerts[i][1])
281 break;
282 k++;
283 }
284 k--;
285
286 for(l=k; l>= j; l--)
287 pStream->insert(rightVerts[l]);
288
289 pStream->insert(topMostV);
290 pStream->end(PRIMITIVE_STREAM_FAN);
291 j=k+1;
292 topMostV = rightVerts[j-1];
293 }
294 }
295 }
296}
r l[0]
Definition: byte_order.h:168
void insert(Real u, Real v)
void end(Int type)
int k
Definition: mpi.c:3369
@ PRIMITIVE_STREAM_FAN

Referenced by monoTriangulationRecGenTBOpt(), and triangulateConvexPolyVertical().