samplecomptop.cc

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

      leftMax =  leftChain->getVertex(leftEndIndex)[0] - Real(1.0); //initilza to left of leftU
      rightMin = rightChain->getVertex(rightEndIndex)[0];
    }
  else
    {
      oldLeftI = leftEndIndex;
      oldRightI = rightEndIndex+1;
      leftMax =  leftChain->getVertex(leftEndIndex)[0]; 
      rightMin = rightChain->getVertex(rightEndIndex)[0] + Real(1.0);      
    }
  
  //i: the current working leftChain index, 
  //j: the current working rightChain index,
  //if left(i) is higher than right(j), then the two chains beloew right(j) are separated.
  //else the two chains below left(i) are separeated.
  i=leftEndIndex; 
  j=rightEndIndex;
  while(1)
    {
      newLeftI = oldLeftI;
      newRightI = oldRightI;

      if(i<leftStartIndex) //left chain is done, go through remining right chain.
	{
	  for(k=j-1; k>= rightStartIndex; k--)
	    {
	      if(rightChain->getVertex(k)[0] > leftMax) //no conflict
		{
		  //update oldRightI if necessary
		  if(rightChain->getVertex(k)[0] < rightMin)
		    {
		      rightMin = rightChain->getVertex(k)[0];
		      oldRightI = k;
		    }
		}
	      else  //there is a conflict
		break; //the for-loop. below right(k-1) is seperated: oldLeftI, oldRightI.
	    }
	  break; //the while loop
	}
      else if(j<rightStartIndex) //rightChain is done
	{
	  for(k=i-1; k>= leftStartIndex; k--)
	    {
	      if(leftChain->getVertex(k)[0] < rightMin) //no conflict
		{
		  //update oldLeftI if necessary
		  if(leftChain->getVertex(k)[0] > leftMax)
		    {
		      leftMax = leftChain->getVertex(k)[0];
		      oldLeftI = k;
		    }
		}
	      else //there is a conflict
		break; //the for loop
	    }
	  break; //the while loop
	}
      else if(leftChain->getVertex(i)[1] > rightChain->getVertex(j)[1]) //left hgiher
	{
	  if(leftChain->getVertex(i)[0] > leftMax) //update leftMax and newLeftI.
	    {
	      leftMax = leftChain->getVertex(i)[0];	     
	      newLeftI = i;
	    }
	  for(k=j-1; k>= rightStartIndex; k--) //update rightMin and newRightI.
	    {
	      if(rightChain->getVertex(k)[1] > leftChain->getVertex(i)[1])
		break;
	      if(rightChain->getVertex(k)[0] < rightMin)
		{
		  rightMin = rightChain->getVertex(k)[0];
		  newRightI = k;
		}
	    }
	  j = k; //next working j, since j will be higher than i in next loop
	  if(leftMax >= rightMin) //there is a conflict
	    break;
	  else //still no conflict
	    {
	      oldLeftI = newLeftI;
	      oldRightI = newRightI;
	    }
	}
      else //right higher
	{
	  if(rightChain->getVertex(j)[0] < rightMin)
	    {
	      rightMin = rightChain->getVertex(j)[0];
	      newRightI = j;
	    }
	  for(k=i-1; k>= leftStartIndex; k--)
	    {
	      if(leftChain->getVertex(k)[1] > rightChain->getVertex(j)[1])
		break;
	      if(leftChain->getVertex(k)[0] > leftMax)
		{
		  leftMax = leftChain->getVertex(k)[0];
		  newLeftI = k;
		}
	    }
	  i = k; //next working i, since i will be higher than j next loop
	  
	  if(leftMax >= rightMin) //there is a conflict
	    break;
	  else //still no conflict
	    {
	      oldLeftI = newLeftI;
	      oldRightI = newRightI;
	    }
	}
    }//end of while loop
  //now oldLeftI and oldRightI are the desired separeator index, notice that there are not necessarily valid
  if(oldLeftI > leftEndIndex || oldRightI > rightEndIndex)
    return 0;
  else
    {
      ret_sep_left = oldLeftI;
      ret_sep_right = oldRightI;
      return 1;
    }
}

        
void sampleCompTop(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)
{
  if(up_leftCornerWhere == 1 && up_rightCornerWhere == 1) //the top is topVertex with possible grid points
    {
      leftGridChain->getGrid()->outputFanWithPoint(leftGridChain->getVlineIndex(gridIndex1),
						   leftGridChain->getUlineIndex(gridIndex1),
						   rightGridChain->getUlineIndex(gridIndex1),
						   topVertex,
						   pStream);
      return;
    }

  else if(up_leftCornerWhere != 0)
    {
      Real* tempTop;
      Int tempRightStart;
      if(up_leftCornerWhere == 1){
	tempRightStart = rightStartIndex;
	tempTop = topVertex;
      }
      else
	{
	  tempRightStart = up_leftCornerIndex+1;
	  tempTop = rightChain->getVertex(up_leftCornerIndex);
	}
      sampleTopRightWithGridLine(tempTop, rightChain, tempRightStart, up_rightCornerIndex,
				 rightGridChain->getGrid(),
				 leftGridChain->getVlineIndex(gridIndex1),
				 leftGridChain->getUlineIndex(gridIndex1),
				 rightGridChain->getUlineIndex(gridIndex1),
				 pStream);
    }
  else if(up_rightCornerWhere != 2)
    {
      Real* tempTop;
      Int tempLeftStart;
      if(up_rightCornerWhere == 1)
	{
	  tempLeftStart = leftStartIndex;
	  tempTop = topVertex;
	}
      else //0
	{
	  tempLeftStart = up_rightCornerIndex+1;
	  tempTop = leftChain->getVertex(up_rightCornerIndex);
	}
/*
      sampleTopLeftWithGridLine(tempTop, leftChain, tempLeftStart, up_leftCornerIndex,
				leftGridChain->getGrid(),
				 leftGridChain->getVlineIndex(gridIndex1),
				 leftGridChain->getUlineIndex(gridIndex1),
				 rightGridChain->getUlineIndex(gridIndex1),
				 pStream);
*/
      sampleCompTopSimple(topVertex,
			  leftChain,
			  leftStartIndex,
			  rightChain,
			  rightStartIndex,
			  leftGridChain,
			  rightGridChain,
			  gridIndex1,
			  up_leftCornerWhere,
			  up_leftCornerIndex,
			  up_rightCornerWhere,
			  up_rightCornerIndex,
			  pStream);	      	      
    }
  else //up_leftCornerWhere == 0, up_rightCornerWhere == 2.
    {
      sampleCompTopSimple(topVertex,
			  leftChain,
			  leftStartIndex,
			  rightChain,
			  rightStartIndex,
			  leftGridChain,
			  rightGridChain,
			  gridIndex1,
			  up_leftCornerWhere,
			  up_leftCornerIndex,
			  up_rightCornerWhere,
			  up_rightCornerIndex,
			  pStream);	      	      
      return;
#ifdef NOT_REACHABLE //code is not reachable, for test purpose only
      //the following code is trying to do some optimization, but not quite working, also see sampleCompBot.C:
      Int sep_left, sep_right;
      if(findTopSeparator(leftChain,
			  leftStartIndex,
			  up_leftCornerIndex,
			  rightChain,
			  rightStartIndex,
			  up_rightCornerIndex,
			  sep_left,
			  sep_right)
	 ) //separator exists
	{

	  if( leftChain->getVertex(sep_left)[0] >= leftGridChain->get_u_value(gridIndex1) &&
	     rightChain->getVertex(sep_right)[0] <= rightGridChain->get_u_value(gridIndex1))
	    {
	      Int gridSep;
	      Int segLeftSmall, segLeftLarge, segRightSmall, segRightLarge;
	      Int valid=1; //whether the gridStep is valid or not.
	      findTopLeftSegment(leftChain,
				 sep_left,
				 up_leftCornerIndex,
				 leftGridChain->get_u_value(gridIndex1),
				 segLeftSmall,
				 segLeftLarge);
	      findTopRightSegment(rightChain,
				 sep_right,
				 up_rightCornerIndex,
				 rightGridChain->get_u_value(gridIndex1),
				 segRightSmall,
				 segRightLarge);
	      if(leftChain->getVertex(segLeftSmall)[1] >= rightChain->getVertex(segRightSmall)[1])
		{
		  gridSep = rightGridChain->getUlineIndex(gridIndex1);
		  while(leftGridChain->getGrid()->get_u_value(gridSep) > leftChain->getVertex(segLeftSmall)[0])
		    gridSep--;
		  if(segLeftSmall<segLeftLarge)
		    if(leftGridChain->getGrid()->get_u_value(gridSep) < leftChain->getVertex(segLeftSmall+1)[0])
		      {
			valid = 0;
		      }
		}
	      else
		{
		  gridSep = leftGridChain->getUlineIndex(gridIndex1);
		  while(leftGridChain->getGrid()->get_u_value(gridSep) < rightChain->getVertex(segRightSmall)[0])
		    gridSep++;
		  if(segRightSmall<segRightLarge)
		    if(leftGridChain->getGrid()->get_u_value(gridSep) > rightChain->getVertex(segRightSmall+1)[0])
		      {
			valid = 0;
		      }
		}		
		  
	      if(! valid)
		{
		  sampleCompTopSimple(topVertex,
				      leftChain,
				      leftStartIndex,
				      rightChain,
				      rightStartIndex,
				      leftGridChain,
				      rightGridChain,
				      gridIndex1,
				      up_leftCornerWhere,
				      up_leftCornerIndex,
				      up_rightCornerWhere,
				      up_rightCornerIndex,
				      pStream);	      	      
		}
	      else
		{
		  sampleTopLeftWithGridLinePost(leftChain->getVertex(segLeftSmall),
						leftChain,
						segLeftSmall+1,
						segLeftSmall+1,
						segLeftLarge,
						up_leftCornerIndex,
						leftGridChain->getGrid(),
						leftGridChain->getVlineIndex(gridIndex1),
						leftGridChain->getUlineIndex(gridIndex1),
						gridSep,
						pStream);
		  sampleTopRightWithGridLinePost(rightChain->getVertex(segRightSmall),
						 rightChain,
						 segRightSmall+1,
						 segRightSmall+1,
						 segRightLarge,
						 up_rightCornerIndex,
						 leftGridChain->getGrid(),
						 leftGridChain->getVlineIndex(gridIndex1),
						 gridSep,
						 rightGridChain->getUlineIndex(gridIndex1),
						 pStream);
		  Real tempBot[2];
		  tempBot[0] = leftGridChain->getGrid()->get_u_value(gridSep);
		  tempBot[1] = leftGridChain->get_v_value(gridIndex1);
		  monoTriangulationRecGen(topVertex, tempBot,
					  leftChain, leftStartIndex, segLeftSmall,
					  rightChain, rightStartIndex, segRightSmall,
					  pStream);
		}
	    }//end if both sides have vetices inside the gridboundary points
	  else if(leftChain->getVertex(sep_left)[0] >= leftGridChain->get_u_value(gridIndex1)) //left is in, right is nout
	    {

	      Int segLeftSmall, segLeftLarge;
	      findTopLeftSegment(leftChain,
				 sep_left,
				 up_leftCornerIndex,
				 leftGridChain->get_u_value(gridIndex1),
				 segLeftSmall,
				 segLeftLarge);	      
	      assert(segLeftLarge >= sep_left); 
              monoTriangulation2(leftChain->getVertex(segLeftLarge),
				 leftGridChain->get_vertex(gridIndex1),
				 leftChain,
				 segLeftLarge+1,
				 up_leftCornerIndex,
				 1, //a increase chain,
				 pStream);

	      stripOfFanLeft(leftChain, segLeftLarge, segLeftSmall, 
			     leftGridChain->getGrid(),