samplemonopoly.cc

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

  /*find the last trim vertex which is above the second top grid line:
   * index1.
   *and sampleLeftOneGridStep(leftchain, topLeftIndex, index1, leftGridChain,
   * leftGridChainStartIndex).
   * index1 could be equal to topLeftIndex.
   */
  Real secondGridChainV = leftGridChain->get_v_value(leftGridChainStartIndex+1);
  assert(leftGridChainStartIndex < leftGridChainEndIndex);
  Int index1 = topLeftIndex;
  while(leftChain->getVertex(index1)[1] > secondGridChainV)
    index1++;
  index1--;
  
  sampleLeftOneGridStep(leftChain, topLeftIndex, index1, leftGridChain, leftGridChainStartIndex, pStream);


  /* 
   * Let the next trim vertex be nextTrimVertIndex (which should be  
   *  below the second grid line).
   * Find the last grid line index2 which is above nextTrimVert.
   * sampleLeftSingleTrimEdgeRegion(uppervert[2], lowervert[2], 
   *                      leftGridChain, leftGridChainStartIndex+1, index2).
   */
  Real *uppervert, *lowervert;
  uppervert = leftChain->getVertex(index1);
  lowervert = leftChain->getVertex(index1+1);
  Int index2 = leftGridChainStartIndex+1;

  while(leftGridChain->get_v_value(index2) >= lowervert[1])
    {
      index2++;
      if(index2 > leftGridChainEndIndex)
	break;
    }
  index2--;
  sampleLeftSingleTrimEdgeRegion(uppervert, lowervert, leftGridChain, leftGridChainStartIndex+1, index2,  pStream);

   /* sampleLeftStripRec(leftChain, 
                        nextTrimVertIndex,
                        botLeftIndex,
                        leftGridChain,
			index2,
                        leftGridChainEndIndex
			)
   *
   */
  sampleLeftStripRec(leftChain, index1+1, botLeftIndex, leftGridChain, index2, leftGridChainEndIndex, pStream);
  
}


/***************begin RecF***********************/
/* the gridlines from leftGridChainStartIndex to 
 * leftGridChainEndIndex are assumed to form a
 * connected component.
 * the trim vertex of topLeftIndex is assumed to
 * be below the first gridline, and the tim vertex
 * of botLeftIndex is assumed to be above the last
 * grid line.
 * If botLeftIndex < topLeftIndex, then no connected componeent exists, and this funcion returns without
 * outputing any triangles.
 * Otherwise botLeftIndex >= topLeftIndex, there is at least one triangle to output.
 */
void sampleLeftStripRecF(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;

  /*if there is only one grid Line, return.*/

  if(leftGridChainStartIndex>=leftGridChainEndIndex)
    return;


  assert(leftChain->getVertex(topLeftIndex)[1] <= leftGridChain->get_v_value(leftGridChainStartIndex) &&
	 leftChain->getVertex(botLeftIndex)[1] >= leftGridChain->get_v_value(leftGridChainEndIndex));

  /*firs find the first trim vertex which is below or equal to the second top grid line:
   * index1.
   */
  Real secondGridChainV = leftGridChain->get_v_value(leftGridChainStartIndex+1);


  Int index1 = topLeftIndex;

  while(leftChain->getVertex(index1)[1] > secondGridChainV){
    index1++;
    if(index1>botLeftIndex)
      break;
  }

  /*now leftChain->getVertex(index-1)[1] > secondGridChainV and
   *    leftChain->getVertex(index)[1] <= secondGridChainV
   *If equality holds, then we should include the vertex index1, otherwise we include only index1-1, to
   *perform sampleOneGridStep.
   */
  if(index1>botLeftIndex) 
    index1--;
  else if(leftChain->getVertex(index1)[1] < secondGridChainV)
    index1--;

  /*now we have leftChain->getVertex(index1)[1] >= secondGridChainV, and 
   *  leftChain->getVertex(index1+1)[1] <= secondGridChainV
   */


  sampleLeftOneGridStep(leftChain, topLeftIndex, index1, leftGridChain, leftGridChainStartIndex, pStream);


  /*if leftChain->getVertex(index1)[1] == secondGridChainV, then we can recursively do the rest.
   */
  if(leftChain->getVertex(index1)[1] == secondGridChainV)
    {

      sampleLeftStripRecF(leftChain, index1, botLeftIndex,leftGridChain, leftGridChainStartIndex+1, leftGridChainEndIndex, pStream);
    }
  else if(index1 < botLeftIndex)
    {

      /* Otherwise, we have leftChain->getVertex(index1)[1] > secondGridChainV,
       * let the next trim vertex be nextTrimVertIndex (which should be  strictly
       *  below the second grid line).
       * Find the last grid line index2 which is above nextTrimVert.
       * sampleLeftSingleTrimEdgeRegion(uppervert[2], lowervert[2], 
       *                      leftGridChain, leftGridChainStartIndex+1, index2).
       */
      Real *uppervert, *lowervert;
      uppervert = leftChain->getVertex(index1);
      lowervert = leftChain->getVertex(index1+1); //okay since index1<botLeftIndex
      Int index2 = leftGridChainStartIndex+1;

      
      while(leftGridChain->get_v_value(index2) >= lowervert[1])
	{
	  index2++;
	  if(index2 > leftGridChainEndIndex)
	    break;
	}
      index2--;

      
      sampleLeftSingleTrimEdgeRegion(uppervert, lowervert, leftGridChain, leftGridChainStartIndex+1, index2,  pStream);
      
      /*recursion*/

      sampleLeftStripRecF(leftChain, index1+1, botLeftIndex, leftGridChain, index2, leftGridChainEndIndex, pStream);
    }
  
}

/***************End RecF***********************/

/*sample the left area in between one trim edge and multiple grid lines.
 * all the grid lines should be in between the two end poins of the
 *trim edge.
 */
void sampleLeftSingleTrimEdgeRegion(Real upperVert[2], Real lowerVert[2],
				    gridBoundaryChain* gridChain,
				    Int beginIndex,
				    Int endIndex,
				    primStream* pStream)
{
  Int i,j,k;

  vertexArray vArray(endIndex-beginIndex+1);  
  vArray.appendVertex(gridChain->get_vertex(beginIndex));

  for(k=1, i=beginIndex+1; i<=endIndex; i++, k++)
    {
      vArray.appendVertex(gridChain->get_vertex(i));

      /*output the fan of the grid points of the (i)th and (i-1)th grid line.
       */
      if(gridChain->getUlineIndex(i) < gridChain->getUlineIndex(i-1))
	{
	  pStream->begin();	  
	  pStream->insert(gridChain->get_vertex(i-1));
	  for(j=gridChain->getUlineIndex(i); j<= gridChain->getUlineIndex(i-1); j++)
	    pStream->insert(gridChain->getGrid()->get_u_value(j), gridChain->get_v_value(i));
	  pStream->end(PRIMITIVE_STREAM_FAN);
	}
      else if(gridChain->getUlineIndex(i) > gridChain->getUlineIndex(i-1))
	{
	  pStream->begin();
	  pStream->insert(gridChain->get_vertex(i));
	  for(j=gridChain->getUlineIndex(i); j>= gridChain->getUlineIndex(i-1); j--)
	    pStream->insert(gridChain->getGrid()->get_u_value(j), gridChain->get_v_value(i-1));
	  pStream->end(PRIMITIVE_STREAM_FAN);
	}
      /*otherwisem, the two are equal, so there is no fan to outout*/	  
    }
  
  monoTriangulation2(upperVert, lowerVert, &vArray, 0, endIndex-beginIndex, 
		     0, /*decreasing chain*/
		     pStream);
}
  
/*return i, such that from begin to i-1 the chain is strictly u-monotone. 
 */				 
Int findIncreaseChainFromBegin(vertexArray* chain, Int begin ,Int end)
{
  Int i=begin;
  Real prevU = chain->getVertex(i)[0];
  Real thisU;
  for(i=begin+1; i<=end; i++){
    thisU = chain->getVertex(i)[0];

    if(prevU < thisU){
      prevU = thisU;
    }
    else
      break;
  }
  return i;
}
  
/*check whether there is a vertex whose v value is strictly 
 *inbetween vup vbelow
 *if no middle exists return -1, else return the idnex.
 */
Int checkMiddle(vertexArray* chain, Int begin, Int end, 
		Real vup, Real vbelow)
{
  Int i;
  for(i=begin; i<=end; i++)
    {
      if(chain->getVertex(i)[1] < vup && chain->getVertex(i)[1]>vbelow)
	return i;
    }
  return -1;
}
  
/*the degenerat case of sampleLeftOneGridStep*/
void sampleLeftOneGridStepNoMiddle(vertexArray* leftChain,
				   Int beginLeftIndex,
				   Int endLeftIndex,
				   gridBoundaryChain* leftGridChain,
				   Int leftGridChainStartIndex,
				   primStream* pStream)
{
  /*since there is no middle, there is at most one point which is on the 
   *second grid line, there could be multiple points on the first (top)
   *grid line.
   */

  leftGridChain->leftEndFan(leftGridChainStartIndex+1, pStream);

  monoTriangulation2(leftGridChain->get_vertex(leftGridChainStartIndex),
		     leftGridChain->get_vertex(leftGridChainStartIndex+1),
		     leftChain,
		     beginLeftIndex,
		     endLeftIndex,
		     1, //is increase chain.
		     pStream);
}



/*sampling the left area in between two grid lines.
 */
void sampleLeftOneGridStep(vertexArray* leftChain,
		  Int beginLeftIndex,
		  Int endLeftIndex,
		  gridBoundaryChain* leftGridChain,
		  Int leftGridChainStartIndex,
		  primStream* pStream
		  )
{
  if(checkMiddle(leftChain, beginLeftIndex, endLeftIndex, 
		 leftGridChain->get_v_value(leftGridChainStartIndex),
		 leftGridChain->get_v_value(leftGridChainStartIndex+1))<0)
    
    {
      
      sampleLeftOneGridStepNoMiddle(leftChain, beginLeftIndex, endLeftIndex, leftGridChain, leftGridChainStartIndex, pStream);
      return;
    }
  
  //copy into a polygon
  {
    directedLine* poly = NULL;
    sampledLine* sline;
    directedLine* dline;
    gridWrap* grid = leftGridChain->getGrid();
    Real vert1[2];
    Real vert2[2];
    Int i;
    
    Int innerInd = leftGridChain->getInnerIndex(leftGridChainStartIndex+1);
    Int upperInd = leftGridChain->getUlineIndex(leftGridChainStartIndex);
    Int lowerInd = leftGridChain->getUlineIndex(leftGridChainStartIndex+1);
    Real upperV = leftGridChain->get_v_value(leftGridChainStartIndex);
    Real lowerV = leftGridChain->get_v_value(leftGridChainStartIndex+1);

    //the upper gridline
    vert1[1] = vert2[1] = upperV;
    for(i=innerInd;	i>upperInd;	i--)
      {
	vert1[0]=grid->get_u_value(i);
	vert2[0]=grid->get_u_value(i-1);
	sline = new sampledLine(vert1, vert2);
	dline = new directedLine(INCREASING, sline);
	if(poly == NULL)
	  poly = dline;
	else
	  poly->insert(dline);
      }

    //the edge connecting upper grid with left chain
    vert1[0] = grid->get_u_value(upperInd);
    vert1[1] = upperV;
    sline = new sampledLine(vert1, leftChain->getVertex(beginLeftIndex));
    dline = new directedLine(INCREASING, sline);
    if(poly == NULL)
      poly = dline;
    else
      poly->insert(dline);    
 
    //the left chain
    for(i=beginLeftIndex; i<endLeftIndex; i++)
      {
	sline = new sampledLine(leftChain->getVertex(i), leftChain->getVertex(i+1));
	dline = new directedLine(INCREASING, sline);
	poly->insert(dline);
      }

    //the edge connecting left chain with lower gridline
    vert2[0] = grid->get_u_value(lowerInd);
    vert2[1] = lowerV;
    sline = new sampledLine(leftChain->getVertex(endLeftIndex), vert2);
    dline = new directedLine(INCREASING, sline);
    poly->insert(dline);

    //the lower grid line
    vert1[1] = vert2[1] = lowerV;
    for(i=lowerInd; i<innerInd; i++)
      {
	vert1[0] = grid->get_u_value(i);
	vert2[0] = grid->get_u_value(i+1);
	sline = new sampledLine(vert1, vert2);
	dline = new directedLine(INCREASING, sline);
	poly->insert(dline);       
      }

    //the vertical grid line segement
    vert1[0]=vert2[0] = grid->get_u_value(innerInd);
    vert2[1]=upperV;
    vert1[1]=lowerV;
    sline=new sampledLine(vert1, vert2);
    dline=new directedLine(INCREASING, sline);
    poly->insert(dline);
    monoTriangulationOpt(poly, pStream);
    //cleanup
    poly->deleteSinglePolygonWithSline();
    return;
  }
 


 

  Int i;
  if(1/*leftGridChain->getUlineIndex(leftGridChainStartIndex) >= 
     leftGridChain->getUlineIndex(leftGridChainStartIndex+1)*/
     ) /*the second grid line is beyond the first one to the left*/
    {
      /*find the maximal U-monotone chain 
       * of endLeftIndex, endLeftIndex-1, ..., 
       */
      i=endLeftIndex;
      Real prevU = leftChain->getVertex(i)[0];
      for(i=endLeftIndex-1; i>=beginLeftIndex; i--){
	Real thisU = leftChain->getVertex(i)[0];
	if( prevU < thisU){
	  prevU = thisU;
	}
	else 
	  break;
      }
      /*from endLeftIndex to i+1 is strictly U- monotone */
      /*if i+1==endLeftIndex and the vertex and leftchain is on the second gridline, then
       *we should use 2 vertices on the leftchain. If we only use one (endLeftIndex), then we
       *we would output degenerate triangles
       */
      if(i+1 == endLeftIndex && leftChain->getVertex(endLeftIndex)[1] == leftGridChain->get_v_value(1+leftGridChainStartIndex))
	i--;

      Int j = beginLeftIndex/*endLeftIndex*/+1;


      if(leftGridChain->getInnerIndex(leftGridChainStartIndex+1) > leftGridChain->getUlineIndex(leftGridChainStartIndex))
	{
	  j = findIncreaseChainFromBegin(leftChain, beginLeftIndex, i+1/*endLeftIndex*/);

	  Int temp = beginLeftIndex;
	  /*now from begin to j-1 is strictly u-monotone*/
	  /*if j-1 is on the first grid line, then we want to skip to the vertex which is strictly
	   *below the grid line. This vertexmust exist since there is a 'corner turn' inbetween the two grid lines
	   */
	  if(j-1 == beginLeftIndex)
	    {
	      while(leftChain->getVertex(j-1)[1] == leftGridChain->get_v_value(leftGridChainStartIndex))
		j++;	        

	      Real vert[2];
	      vert[0] = leftGridChain->get_u_value(leftGridChainStartIndex);
	      vert[1] = leftGridChain->get_v_value(leftGridChainStartIndex);

	      monoTriangulation2(
				 vert/*leftChain->getVertex(beginLeftIndex)*/,
				 leftChain->getVertex(j-1),
				 leftChain,
				 beginLeftIndex,
				 j-2,
				 1,
				 pStream //increase chain
				 );
				 
	      temp = j-1;
	    }
				 
	  stripOfFanLeft(leftChain, j-1, temp