ReactOS  0.4.11-dev-465-g0e6bc23
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

void monoTriangulation ( directedLine monoPolygon,
primStream pStream 
)

Definition at line 626 of file monoTriangulation.cc.

Referenced by Subdivider::drawSurfaces().

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 }
void monoTriangulationRec(Real *topVertex, Real *botVertex, vertexArray *inc_chain, Int inc_current, vertexArray *dec_chain, Int dec_current, primStream *pStream)
Real * head()
directedLine * getPrev()
Definition: directedLine.h:73
Int compV2InY(Real A[2], Real B[2])
GLenum GLclampf GLint i
Definition: glfuncs.h:14
directedLine * getNext()
Definition: directedLine.h:74
Real * getVertex(Int i)
Int get_npoints()
Definition: directedLine.h:72
int Int
Definition: definitions.h:37
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.

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

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
Real ** getArray()
#define assert(x)
Definition: debug.h:53
GLenum GLclampf GLint i
Definition: glfuncs.h:14
void triangle(Real A[2], Real B[2], Real C[2])
smooth NULL
Definition: ftsmooth.c:416
float Real
Definition: definitions.h:36
void monoTriangulation2(Real *topVertex, Real *botVertex, vertexArray *inc_chain, Int inc_smallIndex, Int inc_largeIndex, Int is_increase_chain, primStream *pStream)
Real * getVertex(Int i)
int Int
Definition: definitions.h:37
void monoTriangulationFun ( directedLine monoPolygon,
Int(*)(Real *, Real *)  compFun,
primStream pStream 
)

Definition at line 577 of file monoTriangulation.cc.

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

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 }
Real * head()
void monoTriangulationRecFun(Real *topVertex, Real *botVertex, vertexArray *inc_chain, Int inc_current, vertexArray *dec_chain, Int dec_current, Int(*compFun)(Real *, Real *), primStream *pStream)
directedLine * getPrev()
Definition: directedLine.h:73
GLenum GLclampf GLint i
Definition: glfuncs.h:14
directedLine * getNext()
Definition: directedLine.h:74
Real * getVertex(Int i)
Int get_npoints()
Definition: directedLine.h:72
int Int
Definition: definitions.h:37
void monoTriangulationFunBackend ( Arc_ptr  loop,
Int(*)(Real *, Real *)  compFun,
Backend backend 
)

Definition at line 253 of file monoTriangulationBackend.cc.

Referenced by Slicer::slice_new().

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 }
VARIANT loop
void monoTriangulationRecFunBackend(Real *topVertex, Real *botVertex, vertexArray *inc_chain, Int inc_current, vertexArray *dec_chain, Int dec_current, Int(*compFun)(Real *, Real *), Backend *backend)
GLenum GLclampf GLint i
Definition: glfuncs.h:14
class Arc * Arc_ptr
Definition: arc.h:50
int Int
Definition: definitions.h:37
void monoTriangulationOpt ( directedLine poly,
primStream pStream 
)

Definition at line 55 of file monoTriangulation.cc.

Referenced by sampleLeftOneGridStep(), and sampleRightOneGridStep().

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 connectDiagonal_2slines(directedLine *v1, directedLine *v2, directedLine **ret_p1, directedLine **ret_p2, directedLine *list)
directedLine * polygonConvert(directedLine *polygon)
int other
Definition: msacm.c:1364
#define free
Definition: debug_ros.c:5
#define assert(x)
Definition: debug.h:53
void deleteSinglePolygonWithSline()
Int compV2InY(Real A[2], Real B[2])
void monoTriangulationFun(directedLine *monoPolygon, Int(*compFun)(Real *, Real *), primStream *pStream)
smooth NULL
Definition: ftsmooth.c:416
Int compV2InX(Real A[2], Real B[2])
void findInteriorCuspsX(directedLine *polygon, Int &ret_n_interior_cusps, directedLine **ret_interior_cusps)
Definition: partitionX.cc:121
#define malloc
Definition: debug_ros.c:4
directedLine * findDiagonal_singleCuspX(directedLine *cusp)
Definition: partitionX.cc:137
int Int
Definition: definitions.h:37
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.

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

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 }
void monoTriangulationRec(Real *topVertex, Real *botVertex, vertexArray *inc_chain, Int inc_current, vertexArray *dec_chain, Int dec_current, primStream *pStream)
Real ** getArray()
#define assert(x)
Definition: debug.h:53
Int compV2InY(Real A[2], Real B[2])
GLenum GLclampf GLint i
Definition: glfuncs.h:14
smooth NULL
Definition: ftsmooth.c:416
float Real
Definition: definitions.h:36
int Int
Definition: definitions.h:37
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 }
void monoTriangulationRec(Real *topVertex, Real *botVertex, vertexArray *inc_chain, Int inc_current, vertexArray *dec_chain, Int dec_current, primStream *pStream)
#define assert(x)
Definition: debug.h:53
directedLine * getPrev()
Definition: directedLine.h:73
Int compV2InY(Real A[2], Real B[2])
GLenum GLclampf GLint i
Definition: glfuncs.h:14
directedLine * getNext()
Definition: directedLine.h:74
Real * getVertex(Int i)
smooth NULL
Definition: ftsmooth.c:416
static stack_node_t temp
Definition: rpn.c:18
Int get_npoints()
Definition: directedLine.h:72
int Int
Definition: definitions.h:37
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.

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

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 }
Real ** getArray()
#define assert(x)
Definition: debug.h:53
Int compV2InY(Real A[2], Real B[2])
GLenum GLclampf GLint i
Definition: glfuncs.h:14
smooth NULL
Definition: ftsmooth.c:416
void monoTriangulationRec(Real *topVertex, Real *botVertex, vertexArray *inc_chain, Int inc_current, vertexArray *dec_chain, Int dec_current, Backend *backend)
float Real
Definition: definitions.h:36
int Int
Definition: definitions.h:37
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.

Referenced by monoTriangulationFun(), and monoTriangulationRecFun().

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 }
Real ** getArray()
void monoTriangulationRecFun(Real *topVertex, Real *botVertex, vertexArray *inc_chain, Int inc_current, vertexArray *dec_chain, Int dec_current, Int(*compFun)(Real *, Real *), primStream *pStream)
#define assert(x)
Definition: debug.h:53
GLenum GLclampf GLint i
Definition: glfuncs.h:14
smooth NULL
Definition: ftsmooth.c:416
float Real
Definition: definitions.h:36
int Int
Definition: definitions.h:37
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.

Referenced by monoTriangulationFunBackend(), and monoTriangulationRecFunBackend().

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 }
Real ** getArray()
#define assert(x)
Definition: debug.h:53
void monoTriangulationRecFunBackend(Real *topVertex, Real *botVertex, vertexArray *inc_chain, Int inc_current, vertexArray *dec_chain, Int dec_current, Int(*compFun)(Real *, Real *), Backend *backend)
GLenum GLclampf GLint i
Definition: glfuncs.h:14
smooth NULL
Definition: ftsmooth.c:416
float Real
Definition: definitions.h:36
int Int
Definition: definitions.h:37
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.

Referenced by monoTriangulationRecFunGen(), and monoTriangulationRecGenOpt().

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 }
Real ** getArray()
#define assert(x)
Definition: debug.h:53
GLenum GLclampf GLint i
Definition: glfuncs.h:14
smooth NULL
Definition: ftsmooth.c:416
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)
float Real
Definition: definitions.h:36
int Int
Definition: definitions.h:37
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.

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

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)
Real ** getArray()
Int compV2InY(Real A[2], Real B[2])
GLenum GLclampf GLint i
Definition: glfuncs.h:14
float Real
Definition: definitions.h:36
int Int
Definition: definitions.h:37
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.

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

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 
423  ret_p1->deleteSinglePolygonWithSline();
424  ret_p2->deleteSinglePolygonWithSline();
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
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
452  poly->deleteSinglePolygonWithSline();
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 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 connectDiagonal_2slines(directedLine *v1, directedLine *v2, directedLine **ret_p1, directedLine **ret_p2, directedLine *list)
directedLine * polygonConvert(directedLine *polygon)
directedLine * monoPolyPart(directedLine *polygon)
Definition: monoPolyPart.cc:80
int other
Definition: msacm.c:1364
#define free
Definition: debug_ros.c:5
#define assert(x)
Definition: debug.h:53
sampledLine * insert(sampledLine *nline)
Definition: sampledLine.cc:53
void deleteSinglePolygonWithSline()
static int chainConcave(vertexArray *dec_chain, Int dec_current, Int dec_end)
GLenum GLclampf GLint i
Definition: glfuncs.h:14
void monoTriangulationFun(directedLine *monoPolygon, Int(*compFun)(Real *, Real *), primStream *pStream)
smooth NULL
Definition: ftsmooth.c:416
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)
Int compV2InX(Real A[2], Real B[2])
void findInteriorCuspsX(directedLine *polygon, Int &ret_n_interior_cusps, directedLine **ret_interior_cusps)
Definition: partitionX.cc:121
const GLfloat area
Definition: s_aatritemp.h:104
Definition: _list.h:228
static stack_node_t temp
Definition: rpn.c:18
void deletePolygonListWithSline()
static int chainConvex(vertexArray *inc_chain, Int inc_current, Int inc_end)
#define malloc
Definition: debug_ros.c:4
directedLine * findDiagonal_singleCuspX(directedLine *cusp)
Definition: partitionX.cc:137
Real * getVertex(Int i)
int Int
Definition: definitions.h:37
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)
Real ** getArray()
void triangle(Real A[2], Real B[2], Real C[2])
Real * getVertex(Int i)
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.

Referenced by monoTriangulationRecOpt().

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 }
GLenum GLclampf GLint GLenum GLuint GLenum GLenum GLsizei GLenum const GLvoid GLfloat GLfloat GLfloat GLfloat GLclampd GLint 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 GLboolean GLboolean GLboolean GLint GLenum GLsizei const GLvoid GLenum GLint GLenum GLint GLint GLsizei GLint GLenum GLint GLint GLint GLint GLsizei GLenum GLsizei const GLuint GLboolean GLenum GLenum GLint GLsizei GLenum GLsizei GLenum const GLvoid GLboolean const GLboolean GLenum const GLdouble const GLfloat const GLdouble const GLfloat GLenum GLint GLint GLint GLint GLint GLint j
Definition: glfuncs.h:98
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 monoTriangulationRec(Real *topVertex, Real *botVertex, vertexArray *inc_chain, Int inc_current, vertexArray *dec_chain, Int dec_current, primStream *pStream)
GLenum GLclampf GLint i
Definition: glfuncs.h:14
void monoTriangulationRecOpt(Real *topVertex, Real *botVertex, vertexArray *left_chain, Int left_current, vertexArray *right_chain, Int right_current, primStream *pStream)
float Real
Definition: definitions.h:36
Real * getVertex(Int i)
int Int
Definition: definitions.h:37
void triangulateXYMonoTB ( Int  n_left,
Real **  leftVerts,
Int  n_right,
Real **  rightVerts,
primStream pStream 
)

Definition at line 181 of file monoTriangulation.cc.

Referenced by monoTriangulationRecGenTBOpt(), and triangulateConvexPolyVertical().

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 }
GLenum GLclampf GLint GLenum GLuint GLenum GLenum GLsizei GLenum const GLvoid GLfloat GLfloat GLfloat GLfloat GLclampd GLint 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 GLboolean GLboolean GLboolean GLint GLenum GLsizei const GLvoid GLenum GLint GLenum GLint GLint GLsizei GLint GLenum GLint GLint GLint GLint GLsizei GLenum GLsizei const GLuint GLboolean GLenum GLenum GLint GLsizei GLenum GLsizei GLenum const GLvoid GLboolean const GLboolean GLenum const GLdouble const GLfloat const GLdouble const GLfloat GLenum GLint GLint GLint GLint GLint GLint j
Definition: glfuncs.h:98
#define assert(x)
Definition: debug.h:53
void insert(Real u, Real v)
GLenum GLclampf GLint i
Definition: glfuncs.h:14
r l[0]
Definition: byte_order.h:167
float Real
Definition: definitions.h:36
void end(Int type)
int k
Definition: mpi.c:3369
int Int
Definition: definitions.h:37