monotriangulation.cc

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

	    {
	      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*/
}
    


/* the name here assumes that the polygon is Y-monotone, but 
 *this function also works for X-monotone polygons.
 * a monotne polygon consists of two extrem verteices: topVertex and botVertex, and
 *two monotone chains: inc_chain, and dec_chain. The edges of the increasing chain (inc_chain)
 *is ordered by following pointer: next, while  the edges of the decreasing chain (dec_chain)
 *is ordered by following pointer: prev
 * inc_index index the vertex which is the toppest of the inc_chain which we are handling currently.
 * dec_index index the vertex which is the toppest of the dec_chain which we are handling currently.
 */
void monoTriangulationRec(directedLine* inc_chain, Int inc_index, 
			  directedLine* dec_chain, Int dec_index, 
			  directedLine* topVertex, Int top_index,
			  directedLine* botVertex,
			  primStream* pStream)
{
  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*/
}

/***************************vertexArray begin here**********************************/
vertexArray::vertexArray(Real2* vertices, Int nVertices)
{
  Int i;
  size = index = nVertices;
  array = (Real**) malloc(sizeof(Real*) * nVertices);
  assert(array);
  for(i=0; i<nVertices; i++)
    {
      array[i] = vertices[i];
      array[i] = vertices[i];
    }
}

vertexArray::vertexArray(Int s)
{
  size = s;
  array = (Real**) malloc(sizeof(Real*) * s);
  assert(array);
  index = 0;
}

vertexArray::~vertexArray()
{
  free(array);
}

void vertexArray::appendVertex(Real* ptr)
{
  Int i;
  if(index >= size){
    Real** temp = (Real**) malloc(sizeof(Real*) * (2*size +1));
    assert(temp);
    for(i=0; i<index; i++)
      temp[i] = array[i];
    free(array);
    array = temp;
    size = 2*size+1;
  }
  array[index++] = ptr;
}

void vertexArray::print()
{
  printf("vertex Array:index=%i, size=%i\n", index, size);
  for(Int i=0; i<index; i++)
    {
      printf("(%f,%f) ", array[i][0], array[i][1]);
    }
  printf("\n");
}

/*find the first i such that array[i][1] >= v
 * and array[i+1][1] <v
 * if index == 0 (the array is empty, return -1.
 * if v is above all, return -1.
 * if v is below all, return index-1.
 */
Int vertexArray::findIndexAbove(Real v)
{
  Int i;
  if(index == 0) 
    return -1;
  else if(array[0][1] < v)
    return -1;
  else
    {
      for(i=1; i<index; i++)
	{
	  if(array[i][1] < v)
	    break;
	}
      return i-1;
    }
}

/*find the first i<=endIndex such that array[i][1] <= v
 * and array[i-1][1] > v
 *if sartIndex>endIndex, then return endIndex+1.
 *otherwise, startIndex<=endIndex, it is assumed that
 * 0<=startIndex<=endIndex<index.
 * if v is below all, return endIndex+1
 * if v is above all, return startIndex.
 */
Int vertexArray::findIndexBelowGen(Real v, Int startIndex, Int endIndex)
{
  Int i;
  if(startIndex > endIndex) 
    return endIndex+1;
  else if(array[endIndex][1] >  v)
    return endIndex+1;
  else //now array[endIndex][1] <= v
    {
      for(i=endIndex-1; i>=startIndex; i--)
	{
	  if(array[i][1] > v)
	    break;
	}
      return i+1;
    }
}

/*find the first i<=endIndex such that array[i-1][1] >= v
 * and array[i][1] < v
 *if sartIndex>endIndex, then return endIndex+1.
 *otherwise, startIndex<=endIndex, it is assumed that
 * 0<=startIndex<=endIndex<index.
 * if v is below or equal to all, return endIndex+1
 * if v is strictly above all, return startIndex.
 */
Int vertexArray::findIndexStrictBelowGen(Real v, Int startIndex, Int endIndex)
{
  Int i;
  if(startIndex > endIndex) 
    return endIndex+1;
  else if(array[endIndex][1] >=  v)
    return endIndex+1;
  else //now array[endIndex][1] < v
    {
      for(i=endIndex-1; i>=startIndex; i--)
	{
	  if(array[i][1] >= v)
	    break;
	}
      return i+1;
    }
}

/*find the first i>startIndex such that array[i-1][1] > v
 * and array[i][1] >=v
 *if sartIndex>endIndex, then return startIndex-1.
 *otherwise, startIndex<=endIndex, it is assumed that
 * 0<=startIndex<=endIndex<index.
 * if v is strictly above all, return startIndex-1
 * if v is strictly below all, return endIndex.
 */
Int vertexArray::findIndexFirstAboveEqualGen(Real v, Int startIndex, Int endIndex)
{

  Int i;
  if(startIndex > endIndex) 
    return startIndex-1;
  else if(array[startIndex][1] < v)
    return startIndex-1;
  else //now array[startIndex][1] >= v
    {

      for(i=startIndex; i<=endIndex; i++)
	{
	  if(array[i][1] <= v)
	    break;
	}
      if(i>endIndex) // v is strictly below all
	return endIndex;
      else if(array[i][1] == v)
	return i;
      else
	return i-1;
    }

}


/*find the first i>=startIndex such that array[i][1] >= v
 * and array[i+1][1] <v
 *if sartIndex>endIndex, then return startIndex-1.
 *otherwise, startIndex<=endIndex, it is assumed that
 * 0<=startIndex<=endIndex<index.
 * if v is above all, return startIndex-1
 * if v is below all, return endIndex.
 */
Int vertexArray::findIndexAboveGen(Real v, Int startIndex, Int endIndex)
{
  Int i;
  if(startIndex > endIndex) 
    return startIndex-1;
  else if(array[startIndex][1] < v)
    return startIndex-1;
  else //now array[startIndex][1] >= v
    {
      for(i=startIndex+1; i<=endIndex; i++)
	{
	  if(array[i][1] < v)
	    break;
	}
      return i-1;
    }
}

Int vertexArray::findDecreaseChainFromEnd(Int begin, Int end)
{
  Int i = end;
  Real prevU = array[i][0];
  Real thisU;
  for(i=end-1; i>=begin; i--){
    thisU = array[i][0];
    if(thisU < prevU)
      prevU = thisU;
    else
      break;
  }
  return i;
}

//if(V(start) == v, return start, other wise return the
//last i so that V(i)==v
Int vertexArray::skipEqualityFromStart(Real v, Int start, Int end)
{
  Int i;
  if(array[start][1] != v)
    return start;
  //now array[start][1] == v
  for(i=start+1; i<= end; i++)
    if(array[i][1] != v) 
      break;
  return i-1;
}
  

/***************************vertexArray end****************************************/



/***************************relfex chain stuff begin here*****************************/

reflexChain::reflexChain(Int size, Int is_increasing)
{
  queue = (Real2*) malloc(sizeof(Real2) * size);
  assert(queue);
  index_queue = 0;
  size_queue = size;
  isIncreasing = is_increasing;
}

reflexChain::~reflexChain()
{
  free(queue);
}

/*put (u,v) at the end of the queue
 *pay attention to space
 */
void reflexChain::insert(Real u, Real v)
{
  Int i;
  if(index_queue >= size_queue) {
    Real2 *temp = (Real2*) malloc(sizeof(Real2) * (2*size_queue+1));
    assert(temp);

    /*copy*/
    for(i=0; i<index_queue; i++){
      temp[i][0] = queue[i][0];
      temp[i][1] = queue[i][1];
    }
    
    free(queue);
    queue = temp;
    size_queue = 2*size_queue + 1;
  }

  queue[index_queue][0] = u;
  queue[index_queue][1] = v;
  index_queue ++;
}

void reflexChain::insert(Real v[2])
{
  insert(v[0], v[1]);
}

/*
static Real area(Real A[2], Real B[2], Real C[2])
{
  Real Bx, By, Cx, Cy;
  Bx = B[0] - A[0];
  By = B[1] - A[1];
  Cx = C[0] - A[0];
  Cy = C[1] - A[1];
  return Bx*Cy - Cx*By;
}
*/

/*the chain is reflex, and the vertex v is
 *on the other side of the chain, so that
 *we can outout the fan with v as the
 *the center
 */
void reflexChain::outputFan(Real v[2], primStream* pStream)
{
  Int i;
  pStream->begin();
  pStream->insert(v);
  if(isIncreasing) {
    for(i=0; i<index_queue; i++)
      pStream->insert(queue[i]);
  }
  else {
    for(i=index_queue-1; i>=0; i--)
      pStream->insert(queue[i]);    
  }
  pStream->end(PRIMITIVE_STREAM_FAN);
}

void reflexChain::processNewVertex(Real v[2], primStream* pStream)
{
  Int i,j,k;
  Int isReflex;
  /*if there are at most one vertex in the queue, then simply insert
   */
  if(index_queue <=1){
    insert(v);
    return;
  }
  
  /*there are at least two vertices in the queue*/
  j=index_queue-1;
  
  for(i=j; i>=1; i--) {
    if(isIncreasing) {
      isReflex = (area(queue[i-1], queue[i], v) <= 0.0);
    }
    else /*decreasing*/{
      isReflex = (area(v, queue[i], queue[i-1]) <= 0.0);	  
    }
    if(isReflex) {
      break;
    }
  }

  /*
   *if i<j then vertices: i+1--j are convex
   * output triangle fan: 
   *  v, and queue[i], i+1, ..., j
   */
  if(i<j) 
    {
      pStream->begin();
      pStream->insert(v);
      if(isIncreasing) {
	for(k=i; k<=j; k++)
	  pStream->insert(queue[k]);
      }
      else {
	for(k=j; k>=i; k--)
	  pStream->insert(queue[k]);
      }
      
      pStream->end(PRIMITIVE_STREAM_FAN);
    }

  /*delete vertices i+1--j from the queue*/
  index_queue = i+1;
  /*finally insert v at the end of the queue*/
  insert(v);

}

void reflexChain::print()
{
  Int i;
  printf("reflex chain: isIncreasing=%i\n", isIncreasing);
  for(i=0; i<index_queue; i++) {
    printf("(%f,%f) ", queue[i][0], queue[i][1]);
  }
  printf("\n");
}