samplemonopoly.cc

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

  directedLine* botV;
  topV = botV = polygon;

  for(tempV = polygon->getNext(); tempV != polygon; tempV = tempV->getNext())
    {
      if(compV2InY(topV->head(), tempV->head())<0) {

	topV = tempV;
      }
      if(compV2InY(botV->head(), tempV->head())>0) {

	botV = tempV;
      }
    }
  
  /*find the first(top) and the last (bottom) grid line which intersect the
   *this polygon
   */
  Int firstGridIndex; /*the index in the grid*/
  Int lastGridIndex;
  firstGridIndex = (Int) ((topV->head()[1] - grid->get_v_min()) / (grid->get_v_max() - grid->get_v_min()) * (grid->get_n_vlines()-1));
  lastGridIndex  = (Int) ((botV->head()[1] - grid->get_v_min()) / (grid->get_v_max() - grid->get_v_min()) * (grid->get_n_vlines()-1)) + 1;


  /*find the interval inside  the polygon for each gridline*/
  Int *leftGridIndices = (Int*) malloc(sizeof(Int) * (firstGridIndex - lastGridIndex +1));
  assert(leftGridIndices);
  Int *rightGridIndices = (Int*) malloc(sizeof(Int) * (firstGridIndex - lastGridIndex +1));
  assert(rightGridIndices);
  Int *leftGridInnerIndices = (Int*) malloc(sizeof(Int) * (firstGridIndex - lastGridIndex +1));
  assert(leftGridInnerIndices);
  Int *rightGridInnerIndices = (Int*) malloc(sizeof(Int) * (firstGridIndex - lastGridIndex +1));
  assert(rightGridInnerIndices);

  findLeftGridIndices(topV, firstGridIndex, lastGridIndex, grid,  leftGridIndices, leftGridInnerIndices);

  findRightGridIndices(topV, firstGridIndex, lastGridIndex, grid,  rightGridIndices, rightGridInnerIndices);

  gridBoundaryChain leftGridChain(grid, firstGridIndex, firstGridIndex-lastGridIndex+1, leftGridIndices, leftGridInnerIndices);

  gridBoundaryChain rightGridChain(grid, firstGridIndex, firstGridIndex-lastGridIndex+1, rightGridIndices, rightGridInnerIndices);



//  leftGridChain.draw();
//  leftGridChain.drawInner();
//  rightGridChain.draw();
//  rightGridChain.drawInner();
  /*(1) determine the grid boundaries (left and right).
   *(2) process polygon  into two monotone chaines: use vertexArray
   *(3) call sampleMonoPolyRec
   */

  /*copy the two chains into vertexArray datastructure*/
  Int i;
  vertexArray leftChain(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*/
    leftChain.appendVertex(topV->getVertex(i));
  }
  for(tempV = topV->getNext(); tempV != botV; tempV = tempV->getNext())
    {
      for(i=0; i<=tempV->get_npoints()-2; i++){
	leftChain.appendVertex(tempV->getVertex(i));
      }
    }
  
  vertexArray rightChain(20);
  for(tempV = topV->getPrev(); tempV != botV; tempV = tempV->getPrev())
    {
      for(i=tempV->get_npoints()-2; i>=0; i--){
	rightChain.appendVertex(tempV->getVertex(i));
      }
    }
  for(i=botV->get_npoints()-2; i>=1; i--){ 
    rightChain.appendVertex(tempV->getVertex(i));
  }

  sampleMonoPolyRec(topV->head(),
		    botV->head(),
		    &leftChain,
		    0,
		    &rightChain,
		    0,
		    &leftGridChain,
		    &rightGridChain,
		    0,
		    pStream,
		    rbArray);


  /*cleanup space*/
  free(leftGridIndices);
  free(rightGridIndices);
  free(leftGridInnerIndices);
  free(rightGridInnerIndices);
}

void sampleMonoPolyRec(
		       Real* topVertex,
		       Real* botVertex,
		       vertexArray* leftChain, 
		       Int leftStartIndex,
		       vertexArray* rightChain,
		       Int rightStartIndex,
		       gridBoundaryChain* leftGridChain, 
		       gridBoundaryChain* rightGridChain, 
		       Int gridStartIndex,
		       primStream* pStream,
		       rectBlockArray* rbArray)
{

  /*find the first connected component, and the four corners.
   */
  Int index1, index2; /*the first and last grid line of the first connected component*/

  if(topVertex[1] <= botVertex[1])
    return;
    
  /*find i so that the grid line is below the top vertex*/
  Int i=gridStartIndex;
  while (i < leftGridChain->get_nVlines())
    {
      if(leftGridChain->get_v_value(i) < topVertex[1])
	break;
      i++;
    }

  /*find the first connected component starting with i*/
  /*find index1 so that left_uline_index <= right_uline_index, that is, this
   *grid line contains at least one inner grid point
   */
  index1=i;
  int num_skipped_grid_lines=0;
  while(index1 < leftGridChain->get_nVlines())
    {
      if(leftGridChain->getUlineIndex(index1) <= rightGridChain->getUlineIndex(index1))
	break;
      num_skipped_grid_lines++;
      index1++;
    }



  if(index1 >= leftGridChain->get_nVlines()) /*no grid line exists which has inner point*/
    {
      /*stop recursion, ...*/
      /*monotone triangulate it...*/
//      printf("no grid line exists\n");      
/*
      monoTriangulationRecOpt(topVertex, botVertex, leftChain, leftStartIndex,
			   rightChain, rightStartIndex, pStream);
*/

if(num_skipped_grid_lines <2)
  {
    monoTriangulationRecGenOpt(topVertex, botVertex, leftChain, leftStartIndex,
			       leftChain->getNumElements()-1,
			       rightChain, rightStartIndex, 
			       rightChain->getNumElements()-1,
			       pStream);
  }
else
  {
    //the optimum way to triangulate is top-down since this polygon
    //is narrow-long.
    monoTriangulationRec(topVertex, botVertex, leftChain, leftStartIndex,
			 rightChain, rightStartIndex, pStream);
  }

/*
      monoTriangulationRec(topVertex, botVertex, leftChain, leftStartIndex,
			   rightChain, rightStartIndex, pStream);
*/

/*      monoTriangulationRecGenTBOpt(topVertex, botVertex, 
				   leftChain, leftStartIndex, leftChain->getNumElements()-1,
				   rightChain, rightStartIndex, rightChain->getNumElements()-1, 
				   pStream);*/
      


    }
  else
    {

      /*find index2 so that left_inner_index <= right_inner_index holds until index2*/
      index2=index1+1;
      if(index2 < leftGridChain->get_nVlines())
	while(leftGridChain->getInnerIndex(index2) <= rightGridChain->getInnerIndex(index2))
	  {
	    index2++;
	    if(index2 >= leftGridChain->get_nVlines())
	      break;
	  }
      
      index2--;
      

      
      /*the neck*/
      Int neckLeftIndex;
      Int neckRightIndex;

      /*the four corners*/
      Int up_leftCornerWhere;
      Int up_leftCornerIndex;
      Int up_rightCornerWhere;
      Int up_rightCornerIndex;
      Int down_leftCornerWhere;
      Int down_leftCornerIndex;
      Int down_rightCornerWhere;
      Int down_rightCornerIndex;

      Real* tempBotVertex; /*the bottom vertex for this component*/
      Real* nextTopVertex=NULL; /*for the recursion*/
      Int nextLeftStartIndex=0;
      Int nextRightStartIndex=0;

      /*find the points below the grid line index2 on both chains*/
      Int botLeftIndex = leftChain->findIndexStrictBelowGen(
						      leftGridChain->get_v_value(index2),
						      leftStartIndex,
						      leftChain->getNumElements()-1);
      Int botRightIndex = rightChain->findIndexStrictBelowGen(
							rightGridChain->get_v_value(index2),
							rightStartIndex,
							rightChain->getNumElements()-1);
      /*if either botLeftIndex>= numelements,
       *        or botRightIndex >= numelemnet,
       *then there is no neck exists. the bottom vertex is botVertex, 
       */
      if(! findNeckF(leftChain, botLeftIndex, rightChain, botRightIndex,
		   leftGridChain, rightGridChain, index2, neckLeftIndex, neckRightIndex))
	 /*
      if(botLeftIndex == leftChain->getNumElements() ||
	 botRightIndex == rightChain->getNumElements())
	 */
	{
#ifdef MYDEBUG
	  printf("neck NOT exists, botRightIndex=%i\n", botRightIndex);
#endif

	  tempBotVertex =  botVertex;
	  nextTopVertex = botVertex;
	  botLeftIndex = leftChain->getNumElements()-1;
	  botRightIndex = rightChain->getNumElements()-1;
	}
      else /*neck exists*/
	{
#ifdef MYDEBUG
	  printf("neck exists\n");
#endif

          /*
	  findNeck(leftChain, botLeftIndex,
		   rightChain, botRightIndex,
		   neckLeftIndex,
		   neckRightIndex);
		   */
#ifdef MYDEBUG
printf("neck is found, neckLeftIndex=%i, neckRightIndex=%i\n", neckLeftIndex, neckRightIndex);
glBegin(GL_LINES);
glVertex2fv(leftChain->getVertex(neckLeftIndex));
glVertex2fv(rightChain->getVertex(neckRightIndex));
glEnd();
#endif

	  if(leftChain->getVertex(neckLeftIndex)[1] <= rightChain->getVertex(neckRightIndex)[1])
	    {
	      tempBotVertex = leftChain->getVertex(neckLeftIndex);
	      botLeftIndex = neckLeftIndex-1;
	      botRightIndex = neckRightIndex;
	      nextTopVertex = rightChain->getVertex(neckRightIndex);
	      nextLeftStartIndex = neckLeftIndex;
	      nextRightStartIndex = neckRightIndex+1;
	    }
	  else
	    {
	      tempBotVertex = rightChain->getVertex(neckRightIndex);
	      botLeftIndex = neckLeftIndex;
	      botRightIndex = neckRightIndex-1;		  
	      nextTopVertex = leftChain->getVertex(neckLeftIndex);
	      nextLeftStartIndex = neckLeftIndex+1;
	      nextRightStartIndex = neckRightIndex;
	    }
	}

      findUpCorners(topVertex,
		    leftChain,
		    leftStartIndex, botLeftIndex,
		    rightChain,
		    rightStartIndex, botRightIndex,
		    leftGridChain->get_v_value(index1),
		    leftGridChain->get_u_value(index1),
		    rightGridChain->get_u_value(index1),
		    up_leftCornerWhere,
		    up_leftCornerIndex,
		    up_rightCornerWhere,
		    up_rightCornerIndex);

      findDownCorners(tempBotVertex,
		      leftChain,
		      leftStartIndex, botLeftIndex,
		      rightChain,
		      rightStartIndex, botRightIndex,
		      leftGridChain->get_v_value(index2),
		      leftGridChain->get_u_value(index2),
		      rightGridChain->get_u_value(index2),
		      down_leftCornerWhere,
		      down_leftCornerIndex,
		      down_rightCornerWhere,
		      down_rightCornerIndex);	      
#ifdef MYDEBUG
      printf("find corners done, down_leftwhere=%i, down_righwhere=%i,\n",down_leftCornerWhere, down_rightCornerWhere );
      printf("find corners done, up_leftwhere=%i, up_righwhere=%i,\n",up_leftCornerWhere, up_rightCornerWhere );
      printf("find corners done, up_leftindex=%i, up_righindex=%i,\n",up_leftCornerIndex, up_rightCornerIndex );
      printf("find corners done, down_leftindex=%i, down_righindex=%i,\n",down_leftCornerIndex, down_rightCornerIndex );
#endif

/*
      drawCorners(topVertex,
		  tempBotVertex,
		  leftChain,
		  rightChain,
		  leftGridChain,
		  rightGridChain,
		  index1,
		  index2,
		  up_leftCornerWhere,
		  up_leftCornerIndex,
		  up_rightCornerWhere,
		  up_rightCornerIndex,
		  down_leftCornerWhere,
		  down_leftCornerIndex,
		  down_rightCornerWhere,
		  down_rightCornerIndex);
*/


      sampleConnectedComp(topVertex, tempBotVertex,
			  leftChain, 
			  leftStartIndex, botLeftIndex,
			  rightChain,
			  rightStartIndex, botRightIndex,
			  leftGridChain,
			  rightGridChain,
			  index1, index2,
			  up_leftCornerWhere,
			  up_leftCornerIndex,
			  up_rightCornerWhere,
			  up_rightCornerIndex,
			  down_leftCornerWhere,
			  down_leftCornerIndex,
			  down_rightCornerWhere,
			  down_rightCornerIndex,
			  pStream,
			  rbArray
			  );

      /*recursion*/

      sampleMonoPolyRec(
			nextTopVertex,
			botVertex,
			leftChain, 
			nextLeftStartIndex,
			rightChain,
			nextRightStartIndex,
			leftGridChain, 
			rightGridChain, 
			index2+1,
			pStream, rbArray);
			

    }

}

void sampleLeftStrip(vertexArray* leftChain,
		     Int topLeftIndex,
		     Int botLeftIndex,
		     gridBoundaryChain* leftGridChain,
		     Int leftGridChainStartIndex,
		     Int leftGridChainEndIndex,
		     primStream* pStream
		     )
{
  assert(leftChain->getVertex(topLeftIndex)[1] > leftGridChain->get_v_value(leftGridChainStartIndex));
  assert(leftChain->getVertex(topLeftIndex+1)[1] <= leftGridChain->get_v_value(leftGridChainStartIndex));
  assert(leftChain->getVertex(botLeftIndex)[1] <= leftGridChain->get_v_value(leftGridChainEndIndex));
  assert(leftChain->getVertex(botLeftIndex-1)[1] > leftGridChain->get_v_value(leftGridChainEndIndex));

  /*
   *(1)find the last grid line which doesn'; pass below
   * this first edge, sample this region: one trim edge and 
   * possily multiple grid lines.
   */
  Real *upperVert, *lowerVert; /*the end points of the first trim edge*/
  upperVert = leftChain->getVertex(topLeftIndex);
  lowerVert = leftChain->getVertex(topLeftIndex+1);
  
  Int index = leftGridChainStartIndex;
  while(leftGridChain->get_v_value(index) >= lowerVert[1]){
    index++;
    if(index > leftGridChainEndIndex) 
      break;
  }
  index--;
  
  sampleLeftSingleTrimEdgeRegion(upperVert, lowerVert,
				 leftGridChain,
				 leftGridChainStartIndex,
				 index,
				 pStream);
  sampleLeftStripRec(leftChain, topLeftIndex+1, botLeftIndex,
		     leftGridChain, index, leftGridChainEndIndex,
		     pStream);

}

void sampleLeftStripRec(vertexArray* leftChain,
		     Int topLeftIndex,
		     Int botLeftIndex,
		     gridBoundaryChain* leftGridChain,
		     Int leftGridChainStartIndex,
		     Int leftGridChainEndIndex,
			primStream* pStream
		     )
{
  /*now top left trim vertex is below the top grid line.
   */
  /*stop condition: if topLeftIndex >= botLeftIndex, then stop.
   */
  if(topLeftIndex >= botLeftIndex) 
    return;