samplemonopoly.cc

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

  Real v;
  if(botLeftIndex >= leftChain->getNumElements() ||
     botRightIndex >= rightChain->getNumElements())
    return 0; //no neck exists
     
  v=min(leftChain->getVertex(botLeftIndex)[1], rightChain->getVertex(botRightIndex)[1]);  

 


  for(i=gridStartIndex; i<n_vlines; i++)
    if(leftGridChain->get_v_value(i) <= v && 
       leftGridChain->getUlineIndex(i)<= rightGridChain->getUlineIndex(i))
      break;
  
  lowerGridIndex = i;

  if(lowerGridIndex == n_vlines) //the two trm vertex are higher than all gridlines
    return 0;
  else 
    {
      Int botLeft2, botRight2;
/*
printf("leftGridChain->get_v_)value=%f\n",leftGridChain->get_v_value(lowerGridIndex), botLeftIndex); 
printf("leftChain->get_vertex(0)=(%f,%f)\n", leftChain->getVertex(0)[0],leftChain->getVertex(0)[1]);
printf("leftChain->get_vertex(1)=(%f,%f)\n", leftChain->getVertex(1)[0],leftChain->getVertex(1)[1]);
printf("leftChain->get_vertex(2)=(%f,%f)\n", leftChain->getVertex(2)[0],leftChain->getVertex(2)[1]);
*/
      botLeft2 = leftChain->findIndexFirstAboveEqualGen(leftGridChain->get_v_value(lowerGridIndex), botLeftIndex, leftChain->getNumElements()-1) -1 ;

/*
printf("botLeft2=%i\n", botLeft2);
printf("leftChain->getNumElements=%i\n", leftChain->getNumElements());
*/

      botRight2 = rightChain->findIndexFirstAboveEqualGen(leftGridChain->get_v_value(lowerGridIndex), botRightIndex, rightChain->getNumElements()-1) -1;
      if(botRight2 < botRightIndex) botRight2=botRightIndex;

      if(botLeft2 < botLeftIndex) botLeft2 = botLeftIndex;

      assert(botLeft2 >= botLeftIndex);
      assert(botRight2 >= botRightIndex);
      //find nectLeft so that it is th erightmost vertex on letChain

      Int tempI = botLeftIndex;
      Real temp = leftChain->getVertex(tempI)[0];
      for(i=botLeftIndex+1; i<= botLeft2; i++)
	if(leftChain->getVertex(i)[0] > temp)
	  {
	    temp = leftChain->getVertex(i)[0];
	    tempI = i;
	  }
      neckLeft = tempI;

      tempI = botRightIndex;
      temp = rightChain->getVertex(tempI)[0];
      for(i=botRightIndex+1; i<= botRight2; i++)
	if(rightChain->getVertex(i)[0] < temp)
	  {
	    temp = rightChain->getVertex(i)[0];
	    tempI = i;
	  }
      neckRight = tempI;
      return 1;
    }
}
							
  
	          
/*find i>=botLeftIndex,j>=botRightIndex so that
 *(leftChain[i], rightChain[j]) is a neck.
 */
void findNeck(vertexArray *leftChain, Int botLeftIndex, 
	      vertexArray *rightChain, Int botRightIndex, 
	      Int& leftLastIndex, /*left point of the neck*/
	      Int& rightLastIndex /*right point of the neck*/
	      )
{
  assert(botLeftIndex < leftChain->getNumElements() &&
     botRightIndex < rightChain->getNumElements());
     
  /*now the neck exists for sure*/

  if(leftChain->getVertex(botLeftIndex)[1] <= rightChain->getVertex(botRightIndex)[1]) //left below right
    {

      leftLastIndex = botLeftIndex;
      
      /*find i so that rightChain[i][1] >= leftchainbotverte[1], and i+1<
       */
      rightLastIndex=rightChain->findIndexAboveGen(leftChain->getVertex(botLeftIndex)[1], botRightIndex+1, rightChain->getNumElements()-1);    
    }
  else  //left above right
    {

      rightLastIndex = botRightIndex;
     
      leftLastIndex = leftChain->findIndexAboveGen(rightChain->getVertex(botRightIndex)[1], 
						  botLeftIndex+1,
						  leftChain->getNumElements()-1);
    }
}
      
      

void findLeftGridIndices(directedLine* topEdge, Int firstGridIndex, Int lastGridIndex, gridWrap* grid,  Int* ret_indices, Int* ret_innerIndices)
{

  Int i,k,isHoriz = 0;
  Int n_ulines = grid->get_n_ulines();
  Real uMin = grid->get_u_min();
  Real uMax = grid->get_u_max();
  /*
  Real vMin = grid->get_v_min();
  Real vMax = grid->get_v_max();
  */
  Real slop = 0.0, uinterc;

#ifdef SHORTEN_GRID_LINE
  //uintercBuf stores all the interction u value for each grid line
  //notice that lastGridIndex<= firstGridIndex
  Real *uintercBuf = (Real *) malloc (sizeof(Real) * (firstGridIndex-lastGridIndex+1));
  assert(uintercBuf);
#endif

  /*initialization to make vtail bigger than grid->...*/
  directedLine* dLine = topEdge;
  Real vtail = grid->get_v_value(firstGridIndex) + 1.0; 
  Real tempMaxU = grid->get_u_min();


  /*for each grid line*/
  for(k=0, i=firstGridIndex; i>=lastGridIndex; i--, k++)
    {

      Real grid_v_value = grid->get_v_value(i);

      /*check whether this grid line is below the current trim edge.*/
      if(vtail > grid_v_value)
	{
	  /*since the grid line is below the trim edge, we 
	   *find the trim edge which will contain the trim line
	   */
	  while( (vtail=dLine->tail()[1]) > grid_v_value){

	    tempMaxU = max(tempMaxU, dLine->tail()[0]);
	    dLine = dLine -> getNext();
	  }

	  if( fabs(dLine->head()[1] - vtail) < ZERO)
	    isHoriz = 1;
	  else
	    {
	      isHoriz = 0;
	      slop = (dLine->head()[0] - dLine->tail()[0]) / (dLine->head()[1]-vtail);
	    }
	}

      if(isHoriz)
	{
	  uinterc = max(dLine->head()[0], dLine->tail()[0]);
	}
      else
	{
	  uinterc = slop * (grid_v_value - vtail) + dLine->tail()[0];
	}
      
      tempMaxU = max(tempMaxU, uinterc);

      if(uinterc < uMin && uinterc >= uMin - ZERO)
	uinterc = uMin;
      if(uinterc > uMax && uinterc <= uMax + ZERO)
	uinterc = uMax;

#ifdef SHORTEN_GRID_LINE
      uintercBuf[k] = uinterc;
#endif

      assert(uinterc >= uMin && uinterc <= uMax);
       if(uinterc == uMax)
         ret_indices[k] = n_ulines-1;
       else
	 ret_indices[k] = (Int)(((uinterc-uMin)/(uMax - uMin)) * (n_ulines-1)) + 1;
      if(ret_indices[k] >= n_ulines)
	ret_indices[k] = n_ulines-1;


      ret_innerIndices[k] = (Int)(((tempMaxU-uMin)/(uMax - uMin)) * (n_ulines-1)) + 1;

      /*reinitialize tempMaxU for next grdiLine*/
      tempMaxU = uinterc;
    }
#ifdef SHORTEN_GRID_LINE
  //for each grid line, compare the left grid point with the 
  //intersection point. If the two points are too close, then
  //we should move the grid point one grid to the right
  //and accordingly we should update the inner index.
  for(k=0, i=firstGridIndex; i>=lastGridIndex; i--, k++)
    {
      //check gridLine i
      //check ret_indices[k]
      Real a = grid->get_u_value(ret_indices[k]-1);
      Real b = grid->get_u_value(ret_indices[k]);
      assert(uintercBuf[k] >= a && uintercBuf < b);
      if( (b-uintercBuf[k]) <= 0.2 * (b-a)) //interc is very close to b
	{
	  ret_indices[k]++;
	}

      //check ret_innerIndices[k]
      if(k>0)
	{
	  if(ret_innerIndices[k] < ret_indices[k-1])
	    ret_innerIndices[k] = ret_indices[k-1];
	  if(ret_innerIndices[k] < ret_indices[k])
	    ret_innerIndices[k] = ret_indices[k];
	}
    }
  //clean up
  free(uintercBuf);
#endif
}

void findRightGridIndices(directedLine* topEdge, Int firstGridIndex, Int lastGridIndex, gridWrap* grid,  Int* ret_indices, Int* ret_innerIndices)
{

  Int i,k;
  Int n_ulines = grid->get_n_ulines();
  Real uMin = grid->get_u_min();
  Real uMax = grid->get_u_max();
  /*
  Real vMin = grid->get_v_min();
  Real vMax = grid->get_v_max();
  */
  Real slop = 0.0, uinterc;

#ifdef SHORTEN_GRID_LINE
  //uintercBuf stores all the interction u value for each grid line
  //notice that firstGridIndex >= lastGridIndex
  Real *uintercBuf = (Real *) malloc (sizeof(Real) * (firstGridIndex-lastGridIndex+1));
  assert(uintercBuf);
#endif

  /*initialization to make vhead bigger than grid->v_value...*/
  directedLine* dLine = topEdge->getPrev();
  Real vhead = dLine->tail()[1];
  Real tempMinU = grid->get_u_max();

  /*for each grid line*/
  for(k=0, i=firstGridIndex; i>=lastGridIndex; i--, k++)
    {

      Real grid_v_value = grid->get_v_value(i);


      /*check whether this grid line is below the current trim edge.*/
      if(vhead >= grid_v_value)
	{
	  /*since the grid line is below the tail of the trim edge, we 
	   *find the trim edge which will contain the trim line
	   */
	  while( (vhead=dLine->head()[1]) > grid_v_value){
	    tempMinU = min(tempMinU, dLine->head()[0]);
	    dLine = dLine -> getPrev();
	  }

	  /*skip the equality in the case of degenerat case: horizontal */
	  while(dLine->head()[1] == grid_v_value)
	    dLine = dLine->getPrev();
	    
	  assert( dLine->tail()[1] != dLine->head()[1]);
	  slop = (dLine->tail()[0] - dLine->head()[0]) / (dLine->tail()[1]-dLine->head()[1]);
	  /*
	   if(dLine->tail()[1] == vhead)
	     isHoriz = 1;
	     else
	    {
	      isHoriz = 0;
	      slop = (dLine->tail()[0] - dLine->head()[0]) / (dLine->tail()[1]-vhead);
	    }
	    */
	}
	uinterc = slop * (grid_v_value - dLine->head()[1]) + dLine->head()[0];

      //in case unterc is outside of the grid due to floating point
      if(uinterc < uMin)
	uinterc = uMin;
      else if(uinterc > uMax)
	uinterc = uMax;

#ifdef SHORTEN_GRID_LINE
      uintercBuf[k] = uinterc;
#endif      

      tempMinU = min(tempMinU, uinterc);

      assert(uinterc >= uMin && uinterc <= uMax);      

      if(uinterc == uMin)
	ret_indices[k] = 0;
      else
	ret_indices[k] = (int)ceil((((uinterc-uMin)/(uMax - uMin)) * (n_ulines-1))) -1;
/*
if(ret_indices[k] >= grid->get_n_ulines())
  {
  printf("ERROR3\n");
  exit(0);
}
if(ret_indices[k] < 0)    
  {
  printf("ERROR4\n");
  exit(0);
}
*/
      ret_innerIndices[k] = (int)ceil ((((tempMinU-uMin)/(uMax - uMin)) * (n_ulines-1))) -1;

      tempMinU = uinterc;
    }
#ifdef SHORTEN_GRID_LINE
  //for each grid line, compare the left grid point with the 
  //intersection point. If the two points are too close, then
  //we should move the grid point one grid to the right
  //and accordingly we should update the inner index.
  for(k=0, i=firstGridIndex; i>=lastGridIndex; i--, k++)
    {
      //check gridLine i
      //check ret_indices[k]
      Real a = grid->get_u_value(ret_indices[k]);
      Real b = grid->get_u_value(ret_indices[k]+1);
      assert(uintercBuf[k] > a && uintercBuf <= b);
      if( (uintercBuf[k]-a) <= 0.2 * (b-a)) //interc is very close to a
	{
	  ret_indices[k]--;
	}

      //check ret_innerIndices[k]
      if(k>0)
	{
	  if(ret_innerIndices[k] > ret_indices[k-1])
	    ret_innerIndices[k] = ret_indices[k-1];
	  if(ret_innerIndices[k] > ret_indices[k])
	    ret_innerIndices[k] = ret_indices[k];
	}
    }
  //clean up
  free(uintercBuf);
#endif
}


void sampleMonoPoly(directedLine* polygon, gridWrap* grid, Int ulinear, Int vlinear, primStream* pStream, rectBlockArray* rbArray)
{
/*
{
grid->print();
polygon->writeAllPolygons("zloutputFile");
exit(0);
}
*/

if(grid->get_n_ulines() == 2 ||
   grid->get_n_vlines() == 2)
{ 
  if(ulinear && grid->get_n_ulines() == 2)
    {
      monoTriangulationFun(polygon, compV2InY, pStream);   
      return;
    }
  else if(DBG_isConvex(polygon) && polygon->numEdges() >=4)
     {
       triangulateConvexPoly(polygon, ulinear, vlinear, pStream);
       return;
     }
  else if(vlinear || DBG_is_U_direction(polygon))
    {
      Int n_cusps;//num interior cusps
      Int n_edges = polygon->numEdges();
      directedLine** cusps = (directedLine**) malloc(sizeof(directedLine*) * n_edges);
      assert(cusps);
      findInteriorCuspsX(polygon, n_cusps, cusps);

      if(n_cusps == 0) //u_monotone
	{

	  monoTriangulationFun(polygon, compV2InX, pStream);

          free(cusps);
          return;          
	}
      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(polygon, compV2InX, pStream);
	      free(cusps);
	      return;
	    }

	  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();	  

          free(cusps);
          return;
         }
     free(cusps);
     }
}

  /*find the top and bottom of the polygon. It is supposed to be
   *a V-monotone polygon
   */

  directedLine* tempV;
  directedLine* topV;