samplecompright.cc

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

  assert(rightChain->getVertex(topRightIndex)[1] <= rightGridChain->get_v_value(rightGridChainStartIndex) &&
	 rightChain->getVertex(botRightIndex)[1] >= rightGridChain->get_v_value(rightGridChainEndIndex));

  //firstfind the first trim vertex which is strictly below the second top
  //grid line: index1. 
  Real secondGridChainV = rightGridChain->get_v_value(rightGridChainStartIndex+1);
  Int index1 = topRightIndex;
  while(rightChain->getVertex(index1)[1] >= secondGridChainV){
    index1++;
    if(index1 >  botRightIndex)
      break;
  }
  //now rightChain->getVertex(index1-1)[1] >= secondGridChainV and
  //rightChain->getVertex(index1)[1] < secondGridChainV and
  //we should include index1-1 to perform a gridStep
    index1--;

  //now we have rightChain->getVertex(index1)[1] >= secondGridChainV, and
  //rightChain->getVertex(index1+1)[1] < secondGridChainV
  sampleRightOneGridStep(rightChain, topRightIndex, index1, rightGridChain, rightGridChainStartIndex, pStream);

  //if rightChain->getVertex(index1)[1] ==secondGridChainV then we can 
  //recurvesively to the rest
  if(rightChain->getVertex(index1)[1] == secondGridChainV)
    {

      
      sampleRightStripRecF(rightChain, index1, botRightIndex, rightGridChain, rightGridChainStartIndex+1, rightGridChainEndIndex, pStream);
    }
  else if(index1 < botRightIndex)
    {
      //otherwise, we have rightChain->getVertex(index1)[1] > secondV
      //let the next trim vertex be nextTrimVertex, (which should be strictly
      //below the second grid line). Find the last grid line index2 which is STRICTLY ABOVE
      //nextTrimVertex.
      //sample one trm edge region.
      Real *uppervert, *lowervert;
      uppervert = rightChain->getVertex(index1);
      lowervert = rightChain->getVertex(index1+1); //okay since index1<botRightindex
      Int index2 = rightGridChainStartIndex+1;
      while(rightGridChain->get_v_value(index2) > lowervert[1])
	{
	  index2++;
	  if(index2 > rightGridChainEndIndex)
	    break;
	}
      index2--;
      
      sampleRightSingleTrimEdgeRegion(uppervert, lowervert, rightGridChain, rightGridChainStartIndex+1, index2, pStream);
      
      //recursion
      sampleRightStripRecF(rightChain, index1+1, botRightIndex, rightGridChain, index2, rightGridChainEndIndex, pStream);
    }
}

//the degenerate case of sampleRightOneGridStep
void sampleRightOneGridStepNoMiddle(vertexArray* rightChain,
				    Int beginRightIndex,
				    Int endRightIndex,
				    gridBoundaryChain* rightGridChain,
				    Int rightGridChainStartIndex,
				    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.
   */
  rightGridChain->rightEndFan(rightGridChainStartIndex+1, pStream);
  monoTriangulation2(rightGridChain->get_vertex(rightGridChainStartIndex),
		     rightGridChain->get_vertex(rightGridChainStartIndex+1),
		     rightChain,
		     beginRightIndex,
		     endRightIndex,
		     0, //decrease chain
		     pStream);
}

//sampling the right area in between two grid lines
//shape: _________|
void sampleRightOneGridStep(vertexArray* rightChain, 
			    Int beginRightIndex,
			    Int endRightIndex,
			    gridBoundaryChain* rightGridChain,
			    Int rightGridChainStartIndex,
			    primStream* pStream)
{
  if(checkMiddle(rightChain, beginRightIndex, endRightIndex,
		 rightGridChain->get_v_value(rightGridChainStartIndex),
		 rightGridChain->get_v_value(rightGridChainStartIndex+1))<0)
    {
      sampleRightOneGridStepNoMiddle(rightChain, beginRightIndex, endRightIndex, rightGridChain, rightGridChainStartIndex, pStream);
      return;
    }

  //copy into a polygn
  {
    directedLine* poly = NULL;
    sampledLine* sline;
    directedLine* dline;
    gridWrap* grid = rightGridChain->getGrid();
    float vert1[2];
    float vert2[2];
    Int i;
    
    Int innerInd = rightGridChain->getInnerIndex(rightGridChainStartIndex+1);
    Int upperInd = rightGridChain->getUlineIndex(rightGridChainStartIndex);
    Int lowerInd = rightGridChain->getUlineIndex(rightGridChainStartIndex+1);
    Real upperV = rightGridChain->get_v_value(rightGridChainStartIndex);
    Real lowerV = rightGridChain->get_v_value(rightGridChainStartIndex+1);
    
    //the upper gridline
    vert1[1]=vert2[1]=upperV;
    for(i=upperInd;
	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);
	if(poly == NULL)
	  poly = dline;
	else
	  poly->insert(dline);
      }
    
    //the vertical grid line segment
    vert1[0]=vert2[0] = grid->get_u_value(innerInd);
    vert1[1]=upperV;
    vert2[1]=lowerV;
    sline=new sampledLine(vert1, vert2);
    dline=new directedLine(INCREASING, sline);
    if(poly == NULL)
      poly = dline;
    else
      poly->insert(dline);
    
    //the lower grid line
    vert1[1]=vert2[1]=lowerV;
    for(i=innerInd; i<lowerInd; 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 edge connecting lower grid to right chain
    vert1[0]=grid->get_u_value(lowerInd);
    sline = new sampledLine(vert1, rightChain->getVertex(endRightIndex));
    dline = new directedLine(INCREASING, sline);
    poly->insert(dline);
    
    
    //the right Chain
    for(i=endRightIndex; i>beginRightIndex; i--)
      {
	sline = new sampledLine(rightChain->getVertex(i), rightChain->getVertex(i-1));
	dline = new directedLine(INCREASING, sline);
	poly->insert(dline);
      }

    //the edge connecting right chain with upper grid
    vert2[1]=upperV;
    vert2[0]=grid->get_u_value(upperInd);
    sline = new sampledLine(rightChain->getVertex(beginRightIndex), vert2);
    dline = new directedLine(INCREASING, sline);
    poly->insert(dline);    
    monoTriangulationOpt(poly, pStream);
    //clean up
    poly->deleteSinglePolygonWithSline();

    return;
  }
	   
  //this following code cannot be reached, but leave it for debuggig purpose.
  Int i;
  //find the maximal U-monotone chain of beginRightIndex, beginRightIndex+1,...
  i=beginRightIndex;
  Real prevU = rightChain->getVertex(i)[0];
  for(i=beginRightIndex+1; i<= endRightIndex; i++){
    Real thisU = rightChain->getVertex(i)[0];
    if(thisU < prevU)
      prevU = thisU;
    else
      break;
  }
  //from beginRightIndex to i-1 is strictly U-monotne
  //if(i-1==beginRightIndex and the vertex of rightchain is on the first 
  //gridline, then we should use 2 vertices  on the right chain. Of we only 
  //use one (begin), we would output degenrate triangles.
  if(i-1 == beginRightIndex && rightChain->getVertex(beginRightIndex)[1] == rightGridChain->get_v_value(rightGridChainStartIndex))
    i++;
  
  Int j = endRightIndex -1;
  if(rightGridChain->getInnerIndex(rightGridChainStartIndex+1) < rightGridChain->getUlineIndex(rightGridChainStartIndex+1))
    {
      j = rightChain->findDecreaseChainFromEnd(i-1/*beginRightIndex*/, endRightIndex);
      Int temp = endRightIndex;
      //now from j+1 to end is strictly U-monotone.
      //if j+1 is on the last grid line, then we wat to skip to the vertex   
      //whcih is strictly above the second grid line. This vertex must exist 
      //since there is a middle vertex
      if(j+1 == endRightIndex)
	{
	  while(rightChain->getVertex(j+1)[1] == rightGridChain->get_v_value(rightGridChainStartIndex+1))
	    j--;

	  monoTriangulation2(rightChain->getVertex(j+1),
			     rightGridChain->get_vertex(rightGridChainStartIndex+1),
			     rightChain,
			     j+2,
			     endRightIndex,
			     0, //a decrease chain
			     pStream);

	  temp = j+1;
	}

      stripOfFanRight(rightChain, temp, j+1, rightGridChain->getGrid(),
		      rightGridChain->getVlineIndex(rightGridChainStartIndex+1),
		      rightGridChain->getInnerIndex(rightGridChainStartIndex+1),
		      rightGridChain->getUlineIndex(rightGridChainStartIndex+1),
		      pStream,
		      0 //the grid line is below the trim line
		      );

    }


  stripOfFanRight(rightChain, i-1, beginRightIndex, rightGridChain->getGrid(),
		  rightGridChain->getVlineIndex(rightGridChainStartIndex),
		  rightGridChain->getInnerIndex(rightGridChainStartIndex+1),
		  rightGridChain->getUlineIndex(rightGridChainStartIndex),
		  pStream,
		  1 //the grid line is above the trm lines
		  );

  //monotone triangulate the remaining rightchain together with the
  //two vertices on the two grid v-lines
  Real vert[2][2];
  vert[0][0] = vert[1][0] = rightGridChain->getInner_u_value(rightGridChainStartIndex+1);
  vert[0][1] = rightGridChain->get_v_value(rightGridChainStartIndex);
  vert[1][1] = rightGridChain->get_v_value(rightGridChainStartIndex+1);

  monoTriangulation2(&vert[0][0], 
		     &vert[1][0],
		     rightChain,
		     i-1,
		     j+1,
		     0, ///a decreae chain
		     pStream);
}
		  
#endif    

void stripOfFanRight(vertexArray* rightChain, 
		    Int largeIndex,
		    Int smallIndex,
		    gridWrap* grid,
		    Int vlineIndex,
		    Int ulineSmallIndex,
		    Int ulineLargeIndex,
		    primStream* pStream,
		    Int gridLineUp /*1 if the grid line is above the trim lines*/
		     )
{
  assert(largeIndex >= smallIndex);

  Real grid_v_value;
  grid_v_value = grid->get_v_value(vlineIndex);

  Real2* trimVerts=(Real2*) malloc(sizeof(Real2)* (largeIndex-smallIndex+1));
  assert(trimVerts);


  Real2* gridVerts=(Real2*) malloc(sizeof(Real2)* (ulineLargeIndex-ulineSmallIndex+1));
  assert(gridVerts);

  Int k,i;
  if(! gridLineUp) /*trim line is above grid line, so trim vertices are going right when index increases*/
    for(k=0, i=smallIndex; i<=largeIndex; i++, k++)
      {
      trimVerts[k][0] = rightChain->getVertex(i)[0];
      trimVerts[k][1] = rightChain->getVertex(i)[1];
    }
  else
    for(k=0, i=largeIndex; i>=smallIndex; i--, k++)
      {
	trimVerts[k][0] = rightChain->getVertex(i)[0];
	trimVerts[k][1] = rightChain->getVertex(i)[1];
      }

  for(k=0, i=ulineSmallIndex; i<= ulineLargeIndex; i++, k++)
    {
      gridVerts[k][0] = grid->get_u_value(i);
      gridVerts[k][1] = grid_v_value;
    }

  if(gridLineUp)
    triangulateXYMono(
		      ulineLargeIndex-ulineSmallIndex+1, gridVerts,
		      largeIndex-smallIndex+1, trimVerts,
		      pStream);
  else
    triangulateXYMono(largeIndex-smallIndex+1, trimVerts,
		      ulineLargeIndex-ulineSmallIndex+1, gridVerts,
		      pStream);
  free(trimVerts);
  free(gridVerts);
}