monotriangulation.cc

Mesa is an open-source implementation of the OpenGL specification - a system for rendering interacti

			  vertexArray* dec_chain, Int dec_current, Int dec_end,
			  primStream* pStream)
{
  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*/
}

void monoTriangulationFun(directedLine* monoPolygon, Int (*compFun)(Real*, Real*), primStream* pStream)
{
  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);
  }
}  

void monoTriangulation(directedLine* monoPolygon, primStream* pStream)
{
  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);

}

/*the chain could be increasing or decreasing, although we use the
 * name inc_chain.
 *the argument  is_increase_chain indicates whether this chain
 *is increasing (left chain in V-monotone case) or decreaing (right chain
 *in V-monotone case).
 */
void monoTriangulation2(Real* topVertex, Real* botVertex, 
			vertexArray* inc_chain, Int inc_smallIndex,
			Int inc_largeIndex,
			Int is_increase_chain,
			primStream* pStream)
{
  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);

}
 
/*if compFun == compV2InY, top to bottom: V-monotone
 *if compFun == compV2InX, right to left: U-monotone
 */
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)
{
  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*/
}
   
/*if compFun == compV2InY, top to bottom: V-monotone
 *if compFun == compV2InX, right to left: U-monotone
 */
void monoTriangulationRecFun(Real* topVertex, Real* botVertex, 
			  vertexArray* inc_chain, Int inc_current,
			  vertexArray* dec_chain, Int dec_current,
			  Int  (*compFun)(Real*, Real*),
			  primStream* pStream)
{
  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*/
}


void monoTriangulationRec(Real* topVertex, Real* botVertex, 
			  vertexArray* inc_chain, Int inc_current,
			  vertexArray* dec_chain, Int dec_current,
			  primStream* pStream)
{
  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++)