monoTriangulation.cc File Reference

#include "monoTriangulation.h"
#include "polyUtil.h"
#include "partitionX.h"
#include "monoPolyPart.h"

Include dependency graph for monoTriangulation.cc:

Go to the source code of this file.

Functions
directedLine *	polygonConvert (directedLine *polygon)
void	monoTriangulationOpt (directedLine *poly, primStream *pStream)
void	monoTriangulationRecOpt (Real *topVertex, Real *botVertex, vertexArray *left_chain, Int left_current, vertexArray *right_chain, Int right_current, 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	triangulateXYMonoTB (Int n_left, Real **leftVerts, Int n_right, Real **rightVerts, primStream *pStream)
static int	chainConvex (vertexArray *inc_chain, Int inc_current, Int inc_end)
static int	chainConcave (vertexArray *dec_chain, Int dec_current, Int dec_end)
void	monoTriangulationRecGenInU (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	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	monoTriangulationFun (directedLine *monoPolygon, Int(*compFun)(Real *, Real *), primStream *pStream)
void	monoTriangulation (directedLine *monoPolygon, primStream *pStream)
void	monoTriangulation2 (Real *topVertex, Real *botVertex, vertexArray *inc_chain, Int inc_smallIndex, Int inc_largeIndex, Int is_increase_chain, 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	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)

Function Documentation

chainConcave()

static int chainConcave ( vertexArray *  dec_chain, Int  dec_current, Int  dec_end  )

static

Definition at line 311 of file monoTriangulation.cc.

{
  Int i;
  //if there are no more than 2 vertices, return 1
  if(dec_current >= dec_end -1) return 1;
  for(i=dec_current; i<=dec_end-2; i++)
    {
      if(area(dec_chain->getVertex(i), dec_chain->getVertex(i+1), dec_chain->getVertex(i+2)) >0)
    return 0;
    }
  return 1;
}

Referenced by monoTriangulationRecGenOpt().

chainConvex()

static int chainConvex ( vertexArray *  inc_chain, Int  inc_current, Int  inc_end  )

static

Definition at line 298 of file monoTriangulation.cc.

{
  Int i;
  //if there are no more than 2 vertices, return 1
  if(inc_current >= inc_end-1) return 1;
  for(i=inc_current; i<= inc_end-2; i++)
    {
      if(area(inc_chain->getVertex(i), inc_chain->getVertex(i+1), inc_chain->getVertex(i+2)) <0)
    return 0;
    }
  return 1;
}

Referenced by monoTriangulationRecGenOpt().

monoTriangulation()

void monoTriangulation	(	directedLine *	monoPolygon,
		primStream *	pStream
	)

Definition at line 626 of file monoTriangulation.cc.

{
  Int i;
  /*find the top vertex, bottom vertex, inccreasing chain, and decreasing chain,
   *then call monoTriangulationRec
   */
  directedLine* tempV;
  directedLine* topV;
  directedLine* botV;
  topV = botV = monoPolygon;
  for(tempV = monoPolygon->getNext(); tempV != monoPolygon; tempV = tempV->getNext())
    {
      if(compV2InY(topV->head(), tempV->head())<0) {
    topV = tempV;
      }
      if(compV2InY(botV->head(), tempV->head())>0) {
    botV = tempV;
      }
    }
  /*creat increase and decrease chains*/
  vertexArray inc_chain(20); /*this is a dynamic array*/
  for(i=1; i<=topV->get_npoints()-2; i++) { /*the first vertex is the top vertex which doesn't belong to inc_chain*/
    inc_chain.appendVertex(topV->getVertex(i));
  }
  for(tempV = topV->getNext(); tempV != botV; tempV = tempV->getNext())
    {
      for(i=0; i<=tempV->get_npoints()-2; i++){
    inc_chain.appendVertex(tempV->getVertex(i));
      }
    }
  
  vertexArray dec_chain(20);
  for(tempV = topV->getPrev(); tempV != botV; tempV = tempV->getPrev())
    {
      for(i=tempV->get_npoints()-2; i>=0; i--){
    dec_chain.appendVertex(tempV->getVertex(i));
      }
    }
  for(i=botV->get_npoints()-2; i>=1; i--){ 
    dec_chain.appendVertex(tempV->getVertex(i));
  }
  
  monoTriangulationRec(topV->head(), botV->head(), &inc_chain, 0, &dec_chain, 0, 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.

{
  assert( inc_chain != NULL);
  Real** inc_array ;
 
  if(inc_smallIndex > inc_largeIndex)
    return; //no triangles 
  if(inc_smallIndex == inc_largeIndex)
    {
      if(is_increase_chain)
    pStream->triangle(inc_chain->getVertex(inc_smallIndex), botVertex, topVertex);
      else
    pStream->triangle(inc_chain->getVertex(inc_smallIndex), topVertex, botVertex);  
      return;
    }
  Int i;
 
  if(is_increase_chain && botVertex[1] == inc_chain->getVertex(inc_largeIndex)[1])
    {
      pStream->triangle(botVertex, inc_chain->getVertex(inc_largeIndex-1),
            inc_chain->getVertex(inc_largeIndex));
      monoTriangulation2(topVertex, botVertex, inc_chain, inc_smallIndex,
             inc_largeIndex-1,
             is_increase_chain,
             pStream);
      return;
    }
  else if( (!is_increase_chain) && topVertex[1] == inc_chain->getVertex(inc_smallIndex)[1])
    {
      pStream->triangle(topVertex, inc_chain->getVertex(inc_smallIndex+1),
            inc_chain->getVertex(inc_smallIndex));
      monoTriangulation2(topVertex, botVertex, inc_chain, inc_smallIndex+1,
             inc_largeIndex, is_increase_chain, pStream);
      return ;
    }                  
 
  inc_array = inc_chain->getArray();
 
  reflexChain rChain(20,is_increase_chain); /*1 means the chain is increasing*/
 
  rChain.processNewVertex(topVertex, pStream);
 
  for(i=inc_smallIndex; i<=inc_largeIndex; i++){
    rChain.processNewVertex(inc_array[i], pStream);
  }
  rChain.processNewVertex(botVertex, 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.

{
  Int i;
  /*find the top vertex, bottom vertex, inccreasing chain, and decreasing chain,
   *then call monoTriangulationRec
   */
  directedLine* tempV;
  directedLine* topV;
  directedLine* botV;
  topV = botV = monoPolygon;
  for(tempV = monoPolygon->getNext(); tempV != monoPolygon; tempV = tempV->getNext())
    {
      if(compFun(topV->head(), tempV->head())<0) {
    topV = tempV;
      }
      if(compFun(botV->head(), tempV->head())>0) {
    botV = tempV;
      }
    }
 
  /*creat increase and decrease chains*/
  vertexArray inc_chain(20); /*this is a dynamic array*/
  for(i=1; i<=topV->get_npoints()-2; i++) { /*the first vertex is the top vertex which doesn't belong to inc_chain*/
    inc_chain.appendVertex(topV->getVertex(i));
  }
  for(tempV = topV->getNext(); tempV != botV; tempV = tempV->getNext())
    {
      for(i=0; i<=tempV->get_npoints()-2; i++){
    inc_chain.appendVertex(tempV->getVertex(i));
      }
    }
  
  vertexArray dec_chain(20);
  for(tempV = topV->getPrev(); tempV != botV; tempV = tempV->getPrev())
    {
      for(i=tempV->get_npoints()-2; i>=0; i--){
    dec_chain.appendVertex(tempV->getVertex(i));
      }
    }
  for(i=botV->get_npoints()-2; i>=1; i--){ 
    dec_chain.appendVertex(tempV->getVertex(i));
  }
  
  if (!(0 == inc_chain.getNumElements() && 0 == dec_chain.getNumElements())) {
     monoTriangulationRecFun(topV->head(), botV->head(), &inc_chain, 0,
                             &dec_chain, 0, compFun, pStream);
  }
}  

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

monoTriangulationOpt()

void monoTriangulationOpt	(	directedLine *	poly,
		primStream *	pStream
	)

Definition at line 55 of file monoTriangulation.cc.

{
  Int n_cusps;
  Int n_edges = poly->numEdges();
  directedLine** cusps = (directedLine**) malloc(sizeof(directedLine*)*n_edges);
  assert(cusps);
  findInteriorCuspsX(poly, n_cusps, cusps);
  if(n_cusps ==0) //u monotine
    {
      monoTriangulationFun(poly, compV2InX, pStream);
    }
  else if(n_cusps == 1) // one interior cusp
    {
      directedLine* new_polygon = polygonConvert(cusps[0]);
      directedLine* other = findDiagonal_singleCuspX(new_polygon);
      //<other> should NOT be null unless there are self-intersecting
      //trim curves. In that case, we don't want to core dump, instead,
      //we triangulate anyway, and print out error message.
      if(other == NULL)
    {
      monoTriangulationFun(poly, compV2InX, pStream);
    }
      else
    {
      directedLine* ret_p1;
      directedLine* ret_p2;
      
      new_polygon->connectDiagonal_2slines(new_polygon, other, 
                           &ret_p1,
                           &ret_p2,
                           new_polygon);
      
      monoTriangulationFun(ret_p1, compV2InX, pStream);
      monoTriangulationFun(ret_p2, compV2InX, pStream);
      
      ret_p1->deleteSinglePolygonWithSline();         
      ret_p2->deleteSinglePolygonWithSline();     
    }
    }
  else
    {
      //we need a general partitionX funtion (supposed to be in partitionX.C,
      //not implemented yet. XXX
      monoTriangulationFun(poly, compV2InY, pStream);    
    }
  
  free(cusps);
}

Referenced by sampleLeftOneGridStep(), and sampleRightOneGridStep().

monoTriangulationRec() [1/2]

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.

{
  Int i;
  directedLine *temp, *oldtemp = NULL;
  Int tempIndex, oldtempIndex = 0;
  
  assert(inc_chain != NULL && dec_chain != NULL);
  
  if(inc_chain == botVertex) {
    reflexChain rChain(20, 0);
    rChain.processNewVertex(topVertex->getVertex(top_index), pStream);
    for(i=dec_index; i< dec_chain->get_npoints(); i++){
      rChain.processNewVertex(dec_chain->getVertex(i), pStream);
    }
    for(temp = dec_chain->getPrev(); temp != botVertex; temp = temp->getPrev())
      {
    for(i=0; i<temp->get_npoints(); i++){
      rChain.processNewVertex(temp->getVertex(i), pStream);
    }
      }
  }
  else if(dec_chain==botVertex) {
    reflexChain rChain(20, 1);
    rChain.processNewVertex(topVertex->getVertex(top_index), pStream);
    for(i=inc_index; i< inc_chain->get_npoints(); i++){
      rChain.processNewVertex(inc_chain->getVertex(i), pStream);
    }
    for(temp = inc_chain->getPrev(); temp != botVertex; temp = temp->getNext())
      {
    for(i=0; i<temp->get_npoints(); i++){
      rChain.processNewVertex(temp->getVertex(i), pStream);
    }
      }
  }
  else /*neither reached the bottom*/{
    if(compV2InY(inc_chain->getVertex(inc_index), dec_chain->getVertex(dec_index)) <=0) {
      reflexChain rChain(20, 0);
      rChain.processNewVertex(topVertex -> getVertex(top_index), pStream);
      temp = dec_chain;
      tempIndex = dec_index;
      while( compV2InY(inc_chain->getVertex(inc_index), temp->getVertex(tempIndex))<=0) {
    oldtemp = temp;
    oldtempIndex = tempIndex;
    rChain.processNewVertex(temp->getVertex(tempIndex), pStream);
    
    if(tempIndex == temp->get_npoints()-1){
      tempIndex = 0;
      temp = temp->getPrev();
    }
    else{
      tempIndex++;
    }
      }
      rChain.outputFan(inc_chain->getVertex(inc_index), pStream);
      monoTriangulationRec(inc_chain, inc_index, temp, tempIndex, oldtemp, oldtempIndex, botVertex, pStream);
    }
    else /* >0*/ {
      reflexChain rChain(20, 1);
      rChain.processNewVertex(topVertex -> getVertex(top_index), pStream);
      temp = inc_chain;
      tempIndex = inc_index;
      while( compV2InY(temp->getVertex(tempIndex), dec_chain->getVertex(dec_index))>0){
    oldtemp = temp;
    oldtempIndex = tempIndex;
    rChain.processNewVertex(temp->getVertex(tempIndex), pStream);
    
    if(tempIndex == temp->get_npoints()-1){
      tempIndex = 0;
      temp = temp->getNext();
    }
    else{
      tempIndex++;
    }
      }
      rChain.outputFan(dec_chain->getVertex(dec_index), pStream);
      monoTriangulationRec(temp, tempIndex, dec_chain, dec_index, oldtemp, oldtempIndex, botVertex, pStream); 
    }
  } /*end case neither reached the bottom*/
}

monoTriangulationRec() [2/2]

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.

{
  assert( inc_chain != NULL && dec_chain != NULL);
  assert( ! (inc_current>=inc_chain->getNumElements() &&
         dec_current>=dec_chain->getNumElements()));
  Int inc_nVertices;
  Int dec_nVertices;
  Real** inc_array ;
  Real** dec_array ;
  Int i;
  assert( ! ( (inc_chain==NULL) && (dec_chain==NULL)));
 
  if(inc_current>=inc_chain->getNumElements()) /*no more vertices on inc_chain*/
    {
 
      dec_array = dec_chain->getArray();
      dec_nVertices = dec_chain->getNumElements();      
      reflexChain rChain(20,0);
      /*put the top vertex into the reflex chain*/
      rChain.processNewVertex(topVertex, pStream);
      /*process all the vertices on the dec_chain*/
      for(i=dec_current; i<dec_nVertices; i++){
    rChain.processNewVertex(dec_array[i], pStream);
      }
      /*process the bottom vertex*/
      rChain.processNewVertex(botVertex, pStream);
 
    }
  else if(dec_current>= dec_chain->getNumElements()) /*no more vertices on dec_chain*/
    {
      inc_array = inc_chain->getArray();
      inc_nVertices= inc_chain->getNumElements();
      reflexChain rChain(20,1);
      /*put the top vertex into the reflex chain*/
      rChain.processNewVertex(topVertex, pStream);
      /*process all the vertices on the inc_chain*/
      for(i=inc_current; i<inc_nVertices; i++){
    rChain.processNewVertex(inc_array[i], pStream);
      }
      /*process the bottom vertex*/
      rChain.processNewVertex(botVertex, pStream);
    }
  else /*neither chain is empty*/
    {
      inc_array = inc_chain -> getArray();
      dec_array = dec_chain -> getArray();
      inc_nVertices= inc_chain->getNumElements();
      dec_nVertices= dec_chain->getNumElements();
      /*if top of inc_chain is 'lower' than top of dec_chain, process all the 
       *vertices on the dec_chain which are higher than top of inc_chain
       */
      if(compV2InY(inc_array[inc_current], dec_array[dec_current]) <= 0)
    {
 
      reflexChain rChain(20, 0);
      rChain.processNewVertex(topVertex, pStream);
      for(i=dec_current; i<dec_nVertices; i++)
        {
          if(compV2InY(inc_array[inc_current], dec_array[i]) <= 0)
        rChain.processNewVertex(dec_array[i], pStream);
          else 
        break;
        }
      rChain.outputFan(inc_array[inc_current], pStream);
      monoTriangulationRec(dec_array[i-1], botVertex, 
                   inc_chain, inc_current,
                   dec_chain, i,
                   pStream);
    }
      else /*compV2InY(inc_array[inc_current], dec_array[dec_current]) > 0*/
    {
 
      reflexChain rChain(20, 1);
      rChain.processNewVertex(topVertex, pStream);
      for(i=inc_current; i<inc_nVertices; i++)
        {
          if(compV2InY(inc_array[i], dec_array[dec_current]) >0)        
        rChain.processNewVertex(inc_array[i], pStream);       
          else
        break;
        }
      rChain.outputFan(dec_array[dec_current], pStream);
      monoTriangulationRec(inc_array[i-1], botVertex, 
                   inc_chain, i,
                   dec_chain, dec_current,
                   pStream);
    }
    }/*end case neither is empty*/
}

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.

{
  assert( inc_chain != NULL && dec_chain != NULL);
  assert( ! (inc_current>=inc_chain->getNumElements() &&
         dec_current>=dec_chain->getNumElements()));
  Int inc_nVertices;
  Int dec_nVertices;
  Real** inc_array ;
  Real** dec_array ;
  Int i;
  assert( ! ( (inc_chain==NULL) && (dec_chain==NULL)));
 
  if(inc_current>=inc_chain->getNumElements()) /*no more vertices on inc_chain*/
    {
 
      dec_array = dec_chain->getArray();
      dec_nVertices = dec_chain->getNumElements();      
      reflexChain rChain(20,0);
      /*put the top vertex into the reflex chain*/
      rChain.processNewVertex(topVertex, pStream);
      /*process all the vertices on the dec_chain*/
      for(i=dec_current; i<dec_nVertices; i++){
    rChain.processNewVertex(dec_array[i], pStream);
      }
      /*process the bottom vertex*/
      rChain.processNewVertex(botVertex, pStream);
 
    }
  else if(dec_current>= dec_chain->getNumElements()) /*no more vertices on dec_chain*/
    {
      inc_array = inc_chain->getArray();
      inc_nVertices= inc_chain->getNumElements();
      reflexChain rChain(20,1);
      /*put the top vertex into the reflex chain*/
      rChain.processNewVertex(topVertex, pStream);
      /*process all the vertices on the inc_chain*/
      for(i=inc_current; i<inc_nVertices; i++){
    rChain.processNewVertex(inc_array[i], pStream);
      }
      /*process the bottom vertex*/
      rChain.processNewVertex(botVertex, pStream);
    }
  else /*neither chain is empty*/
    {
      inc_array = inc_chain -> getArray();
      dec_array = dec_chain -> getArray();
      inc_nVertices= inc_chain->getNumElements();
      dec_nVertices= dec_chain->getNumElements();
      /*if top of inc_chain is 'lower' than top of dec_chain, process all the 
       *vertices on the dec_chain which are higher than top of inc_chain
       */
      if(compFun(inc_array[inc_current], dec_array[dec_current]) <= 0)
    {
 
      reflexChain rChain(20, 0);
      rChain.processNewVertex(topVertex, pStream);
      for(i=dec_current; i<dec_nVertices; i++)
        {
          if(compFun(inc_array[inc_current], dec_array[i]) <= 0)
        rChain.processNewVertex(dec_array[i], pStream);
          else 
        break;
        }
      rChain.outputFan(inc_array[inc_current], pStream);
      monoTriangulationRecFun(dec_array[i-1], botVertex, 
                   inc_chain, inc_current,
                   dec_chain, i,
                   compFun,
                   pStream);
    }
      else /*compFun(inc_array[inc_current], dec_array[dec_current]) > 0*/
    {
 
      reflexChain rChain(20, 1);
      rChain.processNewVertex(topVertex, pStream);
      for(i=inc_current; i<inc_nVertices; i++)
        {
          if(compFun(inc_array[i], dec_array[dec_current]) >0)      
        rChain.processNewVertex(inc_array[i], pStream);       
          else
        break;
        }
      rChain.outputFan(dec_array[dec_current], pStream);
      monoTriangulationRecFun(inc_array[i-1], botVertex, 
                   inc_chain, i,
                   dec_chain, dec_current,
                   compFun,
                   pStream);
    }
    }/*end case neither is empty*/
}

Referenced by monoTriangulationFun(), and monoTriangulationRecFun().

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.

{
  assert( inc_chain != NULL && dec_chain != NULL);
  assert( ! (inc_current> inc_end &&
         dec_current> dec_end));
  /*
  Int inc_nVertices;
  Int dec_nVertices;
  */
  Real** inc_array ;
  Real** dec_array ;
  Int i;
  assert( ! ( (inc_chain==NULL) && (dec_chain==NULL)));
 
  if(inc_current> inc_end) /*no more vertices on inc_chain*/
    {
 
      dec_array = dec_chain->getArray();
      reflexChain rChain(20,0);
      /*put the top vertex into the reflex chain*/
      rChain.processNewVertex(topVertex, pStream);
      /*process all the vertices on the dec_chain*/
      for(i=dec_current; i<=dec_end; i++){
    rChain.processNewVertex(dec_array[i], pStream);
      }
      /*process the bottom vertex*/
      rChain.processNewVertex(botVertex, pStream);
 
    }
  else if(dec_current> dec_end) /*no more vertices on dec_chain*/
    {
      inc_array = inc_chain->getArray();
      reflexChain rChain(20,1);
      /*put the top vertex into the reflex chain*/
      rChain.processNewVertex(topVertex, pStream);
      /*process all the vertices on the inc_chain*/
      for(i=inc_current; i<=inc_end; i++){
    rChain.processNewVertex(inc_array[i], pStream);
      }
      /*process the bottom vertex*/
      rChain.processNewVertex(botVertex, pStream);
    }
  else /*neither chain is empty*/
    {
      inc_array = inc_chain -> getArray();
      dec_array = dec_chain -> getArray();
 
      /*if top of inc_chain is 'lower' than top of dec_chain, process all the 
       *vertices on the dec_chain which are higher than top of inc_chain
       */
      if(compFun(inc_array[inc_current], dec_array[dec_current]) <= 0)
    {
 
      reflexChain rChain(20, 0);
      rChain.processNewVertex(topVertex, pStream);
      for(i=dec_current; i<=dec_end; i++)
        {
          if(compFun(inc_array[inc_current], dec_array[i]) <= 0)
        rChain.processNewVertex(dec_array[i], pStream);
          else 
        break;
        }
      rChain.outputFan(inc_array[inc_current], pStream);
      monoTriangulationRecFunGen(dec_array[i-1], botVertex, 
                   inc_chain, inc_current, inc_end,
                   dec_chain, i, dec_end,
                   compFun,
                   pStream);
    }
      else /*compFun(inc_array[inc_current], dec_array[dec_current]) > 0*/
    {
 
      reflexChain rChain(20, 1);
      rChain.processNewVertex(topVertex, pStream);
      for(i=inc_current; i<=inc_end; i++)
        {
          if(compFun(inc_array[i], dec_array[dec_current]) >0)      
        rChain.processNewVertex(inc_array[i], pStream);       
          else
        break;
        }
      rChain.outputFan(dec_array[dec_current], pStream);
      monoTriangulationRecFunGen(inc_array[i-1], botVertex, 
                   inc_chain, i,inc_end,
                   dec_chain, dec_current,dec_end,
                   compFun,
                   pStream);
    }
    }/*end case neither is empty*/
}

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.

{
  Real** inc_array ;
  Real** dec_array ;
  Int i;
 
  if(inc_current > inc_end && dec_current>dec_end)
    return;
  else if(inc_current>inc_end) /*no more vertices on inc_chain*/
    {
      dec_array = dec_chain->getArray();
      reflexChain rChain(100,0);
      /*put the top vertex into the reflex chain*/
      rChain.processNewVertex(topVertex, pStream);
      /*process all the vertices on the dec_chain*/
      for(i=dec_current; i<=dec_end; i++){
    rChain.processNewVertex(dec_array[i], pStream);
      }
      /*process the bottom vertex*/
      rChain.processNewVertex(botVertex, pStream);
    }
  else if(dec_current> dec_end) /*no more vertices on dec_chain*/
    {
      inc_array = inc_chain->getArray();
 
      reflexChain rChain(100,1);
      /*put the top vertex into the reflex chain*/
      rChain.processNewVertex(topVertex, pStream);
      /*process all the vertices on the inc_chain*/
      for(i=inc_current; i<=inc_end; i++){
    rChain.processNewVertex(inc_array[i], pStream);
      }
      /*process the bottom vertex*/
      rChain.processNewVertex(botVertex, pStream);
    }
  else /*neither chain is empty*/
    {
      inc_array = inc_chain -> getArray();
      dec_array = dec_chain -> getArray();
 
      /*if top of inc_chain is 'lower' than top of dec_chain, process all the 
       *vertices on the dec_chain which are higher than top of inc_chain
       */
      if(compV2InY(inc_array[inc_current], dec_array[dec_current]) <= 0)
    {
 
      reflexChain rChain(100, 0);
      rChain.processNewVertex(topVertex, pStream);
      for(i=dec_current; i<=dec_end; i++)
        {
          if(compV2InY(inc_array[inc_current], dec_array[i]) <= 0)
        rChain.processNewVertex(dec_array[i], pStream);
          else 
        break;
        }
      rChain.outputFan(inc_array[inc_current], pStream);
      monoTriangulationRecGen(dec_array[i-1], botVertex, 
                   inc_chain, inc_current, inc_end,
                   dec_chain, i, dec_end,
                   pStream);
    }
      else /*compV2InY(inc_array[inc_current], dec_array[dec_current]) > 0*/
    {
 
      reflexChain rChain(100, 1);
      rChain.processNewVertex(topVertex, pStream);
      for(i=inc_current; i<=inc_end; i++)
        {
          if(compV2InY(inc_array[i], dec_array[dec_current]) >0)        
        rChain.processNewVertex(inc_array[i], pStream);       
          else
        break;
        }
      rChain.outputFan(dec_array[dec_current], pStream);
      monoTriangulationRecGen(inc_array[i-1], botVertex, 
                   inc_chain, i, inc_end,
                   dec_chain, dec_current,dec_end,
                   pStream);
    }
    }/*end case neither is empty*/
}

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

monoTriangulationRecGenInU()

void monoTriangulationRecGenInU	(	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 324 of file monoTriangulation.cc.

{
  
}

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.

{
  Int i;
  //copy this to a polygon: directedLine Lioop
  sampledLine* sline;
  directedLine* dline;
  directedLine* poly;
 
  if(inc_current <= inc_end) //at least one vertex in inc_chain
    {      
      sline = new sampledLine(topVertex, inc_chain->getVertex(inc_current));
      poly = new directedLine(INCREASING, sline);
      for(i=inc_current; i<=inc_end-1; i++)
    {
      sline = new sampledLine(inc_chain->getVertex(i), inc_chain->getVertex(i+1));
      dline = new directedLine(INCREASING, sline);
      poly->insert(dline);
    }
      sline = new sampledLine(inc_chain->getVertex(inc_end), botVertex);
      dline = new directedLine(INCREASING, sline);
      poly->insert(dline);
    }
  else //inc_chian is empty
    {
      sline = new sampledLine(topVertex, botVertex);
      dline = new directedLine(INCREASING, sline);
      poly = dline;
    }
  
  assert(poly != NULL);
 
  if(dec_current <= dec_end) //at least on vertex in dec_Chain
    {
      sline = new sampledLine(botVertex, dec_chain->getVertex(dec_end));
      dline = new directedLine(INCREASING, sline);
      poly->insert(dline);
      for(i=dec_end; i>dec_current; i--)
    {
      sline = new sampledLine(dec_chain->getVertex(i), dec_chain->getVertex(i-1));
      dline = new directedLine(INCREASING, sline);
      poly->insert(dline);
    }
      sline = new sampledLine(dec_chain->getVertex(dec_current), topVertex);
      dline = new directedLine(INCREASING, sline);
      poly->insert(dline);      
    }
  else //dec_chain  is empty
    {
      sline = new sampledLine(botVertex, topVertex);
      dline = new directedLine(INCREASING, sline);
      poly->insert(dline);
    }
 
  {
    Int n_cusps;
    Int n_edges = poly->numEdges();
    directedLine** cusps = (directedLine**) malloc(sizeof(directedLine*)*n_edges);
    assert(cusps);
    findInteriorCuspsX(poly, n_cusps, cusps);
 
    if(n_cusps ==0) //u monotine
      {
    monoTriangulationFun(poly, compV2InX, pStream);
      }
    else if(n_cusps == 1) // one interior cusp
      {
    directedLine* new_polygon = polygonConvert(cusps[0]);
    directedLine* other = findDiagonal_singleCuspX(new_polygon);
      //<other> should NOT be null unless there are self-intersecting
          //trim curves. In that case, we don't want to core dump, instead,
          //we triangulate anyway, and print out error message.
      if(other == NULL)
        {
          monoTriangulationFun(poly, compV2InX, pStream);
        }
      else
        {
          directedLine* ret_p1;
          directedLine* ret_p2;
          
          new_polygon->connectDiagonal_2slines(new_polygon, other, 
                           &ret_p1,
                           &ret_p2,
                           new_polygon);
          
          monoTriangulationFun(ret_p1, compV2InX, pStream);
          monoTriangulationFun(ret_p2, compV2InX, pStream);
 
          ret_p1->deleteSinglePolygonWithSline();         
          ret_p2->deleteSinglePolygonWithSline();     
        }
      }
    else
      {
    //we need a general partitionX funtion (supposed to be in partitionX.C,
    //not implemented yet. XXX
    //monoTriangulationFun(poly, compV2InY, pStream);    
    
    directedLine* new_polygon = polygonConvert(poly);
    directedLine* list = monoPolyPart(new_polygon);
    for(directedLine* temp = list; temp != NULL; temp = temp->getNextPolygon())
      { 
        monoTriangulationFun(temp, compV2InX, pStream);
      }
    //clean up
    list->deletePolygonListWithSline();
        
      }
 
    free(cusps);
    /*
      if(numInteriorCuspsX(poly) == 0) //is u monotone
    monoTriangulationFun(poly, compV2InX, pStream);
      else //it is not u motone
    monoTriangulationFun(poly, compV2InY, pStream);    
    */
    //clean up space
    poly->deleteSinglePolygonWithSline();
    return;
  }
      
  //apparently the following code is not reachable, 
  //it is for test purpose
  if(inc_current > inc_end || dec_current>dec_end)
    {
    monoTriangulationRecGen(topVertex, botVertex, inc_chain, inc_current, inc_end,
                dec_chain, dec_current, dec_end,
                pStream);    
    return;
  }
  
 
  if(
     area(dec_chain->getVertex(dec_current),
      topVertex,
      inc_chain->getVertex(inc_current)) >=0
     && chainConvex(inc_chain, inc_current, inc_end)
     && chainConcave(dec_chain, dec_current, dec_end)
     && area(inc_chain->getVertex(inc_end), botVertex, dec_chain->getVertex(dec_end)) >=0
     )
    {
      monoTriangulationRecFunGen(topVertex, botVertex, 
                 inc_chain, inc_current, inc_end,
                 dec_chain, dec_current, dec_end, 
                 compV2InX, pStream);
    }
  else
    {
      monoTriangulationRecGen(topVertex, botVertex, inc_chain, inc_current, inc_end,
                  dec_chain, dec_current, dec_end,
                  pStream);
    }
}

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.

{
  pStream->triangle(topVertex, inc_chain->getVertex(inc_current), dec_chain->getVertex(dec_current));
  
/*printf("**(%f,%f)\n", inc_chain->getArray()[0][0],inc_chain->getArray()[0][1]);*/
  triangulateXYMonoTB(inc_end-inc_current+1, inc_chain->getArray()+inc_current,  dec_end-dec_current+1,  dec_chain->getArray()+dec_current, pStream);
 
  pStream->triangle(botVertex, dec_chain->getVertex(dec_end), inc_chain->getVertex(inc_end));
}

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.

{
  Int i,j;
  Int n_left = left_chain->getNumElements();
  Int n_right = right_chain->getNumElements();
  if(left_current>= n_left-1 ||
     right_current>= n_right-1)
    {
      monoTriangulationRec(topVertex, botVertex, left_chain, left_current,
               right_chain, right_current, pStream);
      return;
    }
  //now both left and right  have at least two vertices each.
  Real left_v = left_chain->getVertex(left_current)[1];
  Real right_v = right_chain->getVertex(right_current)[1];
 
  if(left_v <= right_v) //first left vertex is below right
    {
      //find the last vertex of right which is above or equal to left
      for(j=right_current; j<=n_right-1; j++)
    {
      if(right_chain->getVertex(j)[1] < left_v)
        break;
    }
      monoTriangulationRecGen(topVertex, left_chain->getVertex(left_current),
                  left_chain, left_current, left_current,
                  right_chain, right_current, j-1,
                  pStream);
      monoTriangulationRecOpt(right_chain->getVertex(j-1),
                  botVertex,
                  left_chain, left_current,
                  right_chain, j,
                  pStream);
    }
  else //first right vertex is strictly below left
    {
      //find the last vertex of left which is strictly above right
      for(i=left_current; i<=n_left-1; i++)
    {
      if(left_chain->getVertex(i)[1] <= right_v)
        break;
    }
      monoTriangulationRecGen(topVertex, right_chain->getVertex(right_current),
                  left_chain, left_current, i-1,
                  right_chain, right_current, right_current,
                  pStream);
      monoTriangulationRecOpt(left_chain->getVertex(i-1),
                  botVertex,
                  left_chain, i,
                  right_chain, right_current,
                  pStream);
    }
}

Referenced by monoTriangulationRecOpt().

polygonConvert()

directedLine * polygonConvert

(

directedLine *

polygon

)

Definition at line 72 of file sampleMonoPoly.cc.

{
  int i;
  directedLine* ret;
  sampledLine* sline;
  sline = new sampledLine(2);
  sline->setPoint(0, polygon->getVertex(0));
  sline->setPoint(1, polygon->getVertex(1));
  ret=new directedLine(INCREASING, sline);
  for(i=1; i<= polygon->get_npoints()-2; i++)
    {
      sline = new sampledLine(2);
      sline->setPoint(0, polygon->getVertex(i));
      sline->setPoint(1, polygon->getVertex(i+1));
      ret->insert(new directedLine(INCREASING, sline));
    }
 
  for(directedLine *temp = polygon->getNext(); temp != polygon; temp = temp->getNext())
    {
      for(i=0; i<= temp->get_npoints()-2; i++)
    {
      sline = new sampledLine(2);
      sline->setPoint(0, temp->getVertex(i));
      sline->setPoint(1, temp->getVertex(i+1));
      ret->insert(new directedLine(INCREASING, sline));
    }
    }
  return ret;
}

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

triangulateXYMonoTB()

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

Definition at line 181 of file monoTriangulation.cc.

{
 
 
  Int i,j,k,l;
  Real* topMostV;
 
  assert(n_left>=1 && n_right>=1);
  if(leftVerts[0][1] >= rightVerts[0][1])
    {
      i=1;
      j=0;
      topMostV = leftVerts[0];
    }
  else
    {
      i=0;
      j=1;
      topMostV = rightVerts[0];
    }
  
  while(1)
    {
      if(i >= n_left) /*case1: no more in left*/
    {
 
      if(j<n_right-1) /*at least two vertices in right*/
        {
          pStream->begin();
          pStream->insert(topMostV);
          for(k=n_right-1; k>=j; k--)       
        pStream->insert(rightVerts[j]);
 
          pStream->end(PRIMITIVE_STREAM_FAN);
          
        }
 
      break;    
    }
      else if(j>= n_right) /*case2: no more in right*/
    {
 
      if(i<n_left-1) /*at least two vertices in left*/
        {
          pStream->begin();
          pStream->insert(topMostV);
 
          for(k=i; k<n_left; k++)
        pStream->insert(leftVerts[k]);
 
          pStream->end(PRIMITIVE_STREAM_FAN);         
        }
 
      break;
    }
      else /* case3: neither is empty, plus the topMostV, there is at least one triangle to output*/
    {
 
      if(leftVerts[i][1] >=  rightVerts[j][1])
        {
          pStream->begin();
          pStream->insert(rightVerts[j]); /*the origin of this fan*/
 
          pStream->insert(topMostV);
 
          /*find the last k>=i such that 
           *leftverts[k][1] >= rightverts[j][1]
           */
          k=i;
          while(k<n_left)
        {
          if(leftVerts[k][1] < rightVerts[j][1])
            break;
          k++;
        }
          k--;
          for(l=i; l<=k; l++)
        {
          pStream->insert(leftVerts[l]);
        }
 
          pStream->end(PRIMITIVE_STREAM_FAN);
          //update i for next loop
          i = k+1;
          topMostV = leftVerts[k];
 
        }
      else /*leftVerts[i][1] < rightVerts[j][1]*/
        {
          pStream->begin();
          pStream->insert(leftVerts[i]);/*the origion of this fan*/
 
          /*find the last k>=j such that
           *rightverts[k][1] > leftverts[i][1]*/
          k=j;
          while(k< n_right)
        {
          if(rightVerts[k][1] <= leftVerts[i][1])
            break;
          k++;
        }
          k--;
 
          for(l=k; l>= j; l--)
        pStream->insert(rightVerts[l]);
 
          pStream->insert(topMostV);
          pStream->end(PRIMITIVE_STREAM_FAN);
          j=k+1;
          topMostV = rightVerts[j-1];
        }     
    }
    }
}

Referenced by monoTriangulationRecGenTBOpt(), and triangulateConvexPolyVertical().