samplecomptop.cc

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

			     leftGridChain->getVlineIndex(gridIndex1),
			     leftGridChain->getUlineIndex(gridIndex1),
			     rightGridChain->getUlineIndex(gridIndex1),
			     pStream, 0);


	      monoTriangulationRecGen(topVertex, rightGridChain->get_vertex(gridIndex1),
				      leftChain, leftStartIndex, segLeftSmall,
				      rightChain, rightStartIndex, up_rightCornerIndex,
				      pStream);	    
	    }//end left in right out
	  else if(rightChain->getVertex(sep_right)[0] <= rightGridChain->get_u_value(gridIndex1))
	    {
	      Int segRightSmall, segRightLarge;
	      findTopRightSegment(rightChain,
				 sep_right,
				 up_rightCornerIndex,
				 rightGridChain->get_u_value(gridIndex1),
				 segRightSmall,
				 segRightLarge);
	      assert(segRightLarge>=sep_right);
	      monoTriangulation2(rightChain->getVertex(segRightLarge),
				 rightGridChain->get_vertex(gridIndex1),
				 rightChain,
				 segRightLarge+1,
				 up_rightCornerIndex,
				 0, //a decrease chain
				 pStream);
	      stripOfFanRight(rightChain, segRightLarge, segRightSmall,
			      rightGridChain->getGrid(),
			      rightGridChain->getVlineIndex(gridIndex1),
			      leftGridChain->getUlineIndex(gridIndex1),
			      rightGridChain->getUlineIndex(gridIndex1),
			      pStream, 0);


	      monoTriangulationRecGen(topVertex, leftGridChain->get_vertex(gridIndex1),
				      leftChain, leftStartIndex, up_leftCornerIndex,
				      rightChain, rightStartIndex,segRightSmall,
				      pStream);

	    }//end left out rigth in
	  else //left out , right out
	    {

	      sampleCompTopSimple(topVertex,
				  leftChain,
				  leftStartIndex,
				  rightChain,
				  rightStartIndex,
				  leftGridChain,
				  rightGridChain,
				  gridIndex1,
				  up_leftCornerWhere,
				  up_leftCornerIndex,
				  up_rightCornerWhere,
				  up_rightCornerIndex,
				  pStream);	      	      
	    }//end leftout, right out
	}//end if separator exixts.
      else //no separator
	{

	  sampleCompTopSimple(topVertex,
			    leftChain,
			      leftStartIndex,
			      rightChain,
			      rightStartIndex,
			      leftGridChain,
			      rightGridChain,
			      gridIndex1,
			    up_leftCornerWhere,
			      up_leftCornerIndex,
			      up_rightCornerWhere,
			      up_rightCornerIndex,
			    pStream);
	}
#endif
    }//end if 0,2
}//end if the function

		   
static void sampleCompTopSimpleOpt(gridWrap* grid,
				   Int gridV,
				   Real* topVertex, Real* botVertex,
				   vertexArray* inc_chain, Int inc_current, Int inc_end,
				   vertexArray* dec_chain, Int dec_current, Int dec_end,
				   primStream* pStream)
{
  if(gridV <= 0 || dec_end<dec_current || inc_end <inc_current)
    {
      monoTriangulationRecGenOpt(topVertex, botVertex,
				 inc_chain, inc_current, inc_end,
				 dec_chain, dec_current, dec_end,
				 pStream);
      return;
    }
  if(grid->get_v_value(gridV+1) >= topVertex[1])
    {
      monoTriangulationRecGenOpt(topVertex, botVertex,
				 inc_chain, inc_current, inc_end,
				 dec_chain, dec_current, dec_end,
				 pStream);
      return;
    }      
 Int i,j,k;
  Real currentV = grid->get_v_value(gridV+1);
  if(inc_chain->getVertex(inc_end)[1] <= currentV &&
     dec_chain->getVertex(dec_end)[1] < currentV)
    {
      //find i bottom up so that inc_chain[i]<= curentV and inc_chain[i-1] > currentV, 
      //find j botom up so that dec_chain[j] < currentV and dec_chain[j-1] >= currentV
      for(i=inc_end; i >= inc_current; i--) 
	{
	  if(inc_chain->getVertex(i)[1] > currentV)
	    break;
	}
      i++;
      for(j=dec_end; j >= dec_current; j--)
	{
	  if(dec_chain->getVertex(j)[1] >= currentV)
	    break;
	}
      j++;
     if(inc_chain->getVertex(i)[1] <= dec_chain->getVertex(j)[1])
       {
	 //find the k so that dec_chain[k][1] < inc_chain[i][1]
	 for(k=j; k<=dec_end; k++)
	   {
	     if(dec_chain->getVertex(k)[1] < inc_chain->getVertex(i)[1])
	       break;
	   }
         //we know that dec_chain[j][1] >= inc_chian[i][1]
	 //we know that dec_chain[k-1][1]>=inc_chain[i][1]
         //we know that dec_chian[k][1] < inc_chain[i][1]
         //find l in [j, k-1] so that dec_chain[l][0] 0 is closest to
         // inc_chain[i]
         int l;
         Real tempI = Real(j);
         Real tempMin = (Real)fabs(inc_chain->getVertex(i)[0] - dec_chain->getVertex(j)[0]);
         for(l=j+1; l<= k-1; l++)
	   {
	     if(fabs(inc_chain->getVertex(i)[0] - dec_chain->getVertex(l)[0])
		<= tempMin)
	       {
		 tempMin = (Real)fabs(inc_chain->getVertex(i)[0] - dec_chain->getVertex(l)[0]);
		 tempI = (Real)l;
	       }
	   }
	 //inc_chain[i] and dec_chain[tempI] are connected.
	 monoTriangulationRecGenOpt(dec_chain->getVertex((int)tempI),
				    botVertex,
				    inc_chain, i, inc_end,
				    dec_chain, (int)(tempI+1), dec_end,
				    pStream);
	 //recursively do the rest
	 sampleCompTopSimpleOpt(grid,
				gridV+1,
				topVertex, inc_chain->getVertex(i),
				inc_chain, inc_current, i-1,
				dec_chain, dec_current, (int)tempI,
				pStream);
       }
      else
	{
	  //find the k so that inc_chain[k][1] <= dec_chain[j][1]
	  for(k=i; k<=inc_end; k++)
	    {
	      if(inc_chain->getVertex(k)[1] <= dec_chain->getVertex(j)[1])
		break;
	    }
	  //we know that inc_chain[i] > dec_chain[j]
	  //we know that inc_chain[k-1][1] > dec_chain[j][1]
	  //we know that inc_chain[k][1] <= dec_chain[j][1]
	  //so we find l between [i,k-1] so that 
	  //inc_chain[l][0] is the closet to dec_chain[j][0]
	  int tempI = i;
	  int l;
	  Real tempMin = (Real)fabs(inc_chain->getVertex(i)[0] - dec_chain->getVertex(j)[0]);
	  for(l=i+1; l<=k-1; l++)
	    {
	      if(fabs(inc_chain->getVertex(l)[0] - dec_chain->getVertex(j)[0]) <= tempMin)
		{
		  tempMin = (Real)fabs(inc_chain->getVertex(l)[0] - dec_chain->getVertex(j)[0]);
		  tempI = l;
		}
	    }				 	      

	  //inc_chain[tempI] and dec_chain[j] are connected

	  monoTriangulationRecGenOpt(inc_chain->getVertex(tempI),
				     botVertex,
				     inc_chain, tempI+1, inc_end,
				     dec_chain, j, dec_end,
				     pStream);

	  //recurvesily do the rest
	  sampleCompTopSimpleOpt(grid, gridV+1,
				 topVertex, dec_chain->getVertex(j),
				 inc_chain, inc_current, tempI,
				 dec_chain, dec_current, j-1,
				 pStream);
	}	    				   	       
    }
  else //go to the next higher gridV
    {
      sampleCompTopSimpleOpt(grid,
			     gridV+1,
			     topVertex, botVertex,
			     inc_chain, inc_current, inc_end,
			     dec_chain, dec_current, dec_end,
			     pStream);
    }
}
			  
void sampleCompTopSimple(Real* topVertex,
                   vertexArray* leftChain,
                   Int leftStartIndex,
                   vertexArray* rightChain,
                   Int rightStartIndex,
                   gridBoundaryChain* leftGridChain,
                   gridBoundaryChain* rightGridChain,
                   Int gridIndex1,
                   Int up_leftCornerWhere,
                   Int up_leftCornerIndex,
                   Int up_rightCornerWhere,
                   Int up_rightCornerIndex,
                   primStream* pStream)
{
  //the plan is to use monotriangulation algortihm.
  Int i,k;
  Real* ActualTop;
  Real* ActualBot;
  Int ActualLeftStart, ActualLeftEnd;
  Int ActualRightStart, ActualRightEnd;
  
  //creat an array to store the points on the grid line
  gridWrap* grid = leftGridChain->getGrid();
  Int gridV = leftGridChain->getVlineIndex(gridIndex1);
  Int gridLeftU = leftGridChain->getUlineIndex(gridIndex1);
  Int gridRightU = rightGridChain->getUlineIndex(gridIndex1);

  Real2* gridPoints = (Real2*) malloc(sizeof(Real2) * (gridRightU - gridLeftU +1));
  assert(gridPoints);
  
  for(k=0, i=gridRightU; i>= gridLeftU; i--, k++)
    {
      gridPoints[k][0] = grid->get_u_value(i);
      gridPoints[k][1] = grid->get_v_value(gridV);
    }

  if(up_leftCornerWhere != 2)
    ActualRightStart = rightStartIndex;
  else
    ActualRightStart = up_leftCornerIndex+1; //up_leftCornerIndex will be the ActualTop
  
  if(up_rightCornerWhere != 2) //right corner is not on right chain
    ActualRightEnd = rightStartIndex-1; //meaning that there is no actual rigth section
  else
    ActualRightEnd = up_rightCornerIndex;
  
  vertexArray ActualRightChain(max(0, ActualRightEnd-ActualRightStart+1) + gridRightU-gridLeftU+1);

  for(i=ActualRightStart; i<= ActualRightEnd; i++)
    ActualRightChain.appendVertex(rightChain->getVertex(i));
  for(i=0; i<gridRightU-gridLeftU+1; i++)
    ActualRightChain.appendVertex(gridPoints[i]);    

  //determine ActualLeftEnd
  if(up_leftCornerWhere != 0)
    ActualLeftEnd = leftStartIndex-1;
  else
    ActualLeftEnd = up_leftCornerIndex;
  
  if(up_rightCornerWhere != 0)
    ActualLeftStart = leftStartIndex;
  else
    ActualLeftStart = up_rightCornerIndex+1; //up_rightCornerIndex will be the actual top
  
  if(up_leftCornerWhere == 0) 
    {
      if(up_rightCornerWhere == 0)
	ActualTop = leftChain->getVertex(up_rightCornerIndex);
      else
	ActualTop = topVertex;
    }
  else if(up_leftCornerWhere == 1) 
    ActualTop = topVertex;
  else  //up_leftCornerWhere == 2
    ActualTop = rightChain->getVertex(up_leftCornerIndex);
  
  ActualBot = gridPoints[gridRightU - gridLeftU];
  



  if(leftChain->getVertex(ActualLeftEnd)[1] == ActualBot[1])
    {
/*
    monoTriangulationRecGenOpt(ActualTop, leftChain->getVertex(ActualLeftEnd),
			    leftChain,
			    ActualLeftStart, ActualLeftEnd-1,
			    &ActualRightChain,
			    0,
			    ActualRightChain.getNumElements()-1,
			    pStream);
*/
   
    sampleCompTopSimpleOpt(grid, gridV,
			   ActualTop, leftChain->getVertex(ActualLeftEnd),
			    leftChain,
			    ActualLeftStart, ActualLeftEnd-1,
			    &ActualRightChain,
			    0,
			    ActualRightChain.getNumElements()-1,
			    pStream);
    
  }
  else
    {
/*
    monoTriangulationRecGenOpt(ActualTop, ActualBot, leftChain,
			  ActualLeftStart, ActualLeftEnd,
			  &ActualRightChain,
			  0, ActualRightChain.getNumElements()-2, //the last is the bot.
			  pStream);
*/
   	  
    sampleCompTopSimpleOpt(grid, gridV,
			   ActualTop, ActualBot, leftChain,
			  ActualLeftStart, ActualLeftEnd,
			  &ActualRightChain,
			  0, ActualRightChain.getNumElements()-2, //the last is the bot.
			  pStream);

   
  }

  free(gridPoints);
      
}