samplecompbot.cc

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

/*
** License Applicability. Except to the extent portions of this file are
** made subject to an alternative license as permitted in the SGI Free
** Software License B, Version 1.1 (the "License"), the contents of this
** file are subject only to the provisions of the License. You may not use
** this file except in compliance with the License. You may obtain a copy
** of the License at Silicon Graphics, Inc., attn: Legal Services, 1600
** Amphitheatre Parkway, Mountain View, CA 94043-1351, or at:
** 
** http://oss.sgi.com/projects/FreeB
** 
** Note that, as provided in the License, the Software is distributed on an
** "AS IS" basis, with ALL EXPRESS AND IMPLIED WARRANTIES AND CONDITIONS
** DISCLAIMED, INCLUDING, WITHOUT LIMITATION, ANY IMPLIED WARRANTIES AND
** CONDITIONS OF MERCHANTABILITY, SATISFACTORY QUALITY, FITNESS FOR A
** PARTICULAR PURPOSE, AND NON-INFRINGEMENT.
** 
** Original Code. The Original Code is: OpenGL Sample Implementation,
** Version 1.2.1, released January 26, 2000, developed by Silicon Graphics,
** Inc. The Original Code is Copyright (c) 1991-2000 Silicon Graphics, Inc.
** Copyright in any portions created by third parties is as indicated
** elsewhere herein. All Rights Reserved.
** 
** Additional Notice Provisions: The application programming interfaces
** established by SGI in conjunction with the Original Code are The
** OpenGL(R) Graphics System: A Specification (Version 1.2.1), released
** April 1, 1999; The OpenGL(R) Graphics System Utility Library (Version
** 1.3), released November 4, 1998; and OpenGL(R) Graphics with the X
** Window System(R) (Version 1.3), released October 19, 1998. This software
** was created using the OpenGL(R) version 1.2.1 Sample Implementation
** published by SGI, but has not been independently verified as being
** compliant with the OpenGL(R) version 1.2.1 Specification.
**
** $Date: 2001/11/29 16:16:55 $ $Revision: 1.2 $
*/
/*
** $Header: /home/krh/git/sync/mesa-cvs-repo/Mesa/src/glu/sgi/libnurbs/nurbtess/sampleCompBot.cc,v 1.2 2001/11/29 16:16:55 kschultz Exp $
*/

#include <stdlib.h>
#include <stdio.h>
#include "zlassert.h"
#include "sampleCompBot.h"
#include "sampleCompRight.h"

#define max(a,b) ((a>b)? a:b)

//return: index_mono, index_pass
//from [pass, mono] is strictly U-monotone
//from [corner, pass] is <u
// vertex[pass][0] >= u
//if everybost is <u, then pass = end+1.
//otherwise both mono and pass are meanng full and we have corner<=pass<=mono<=end
void findBotLeftSegment(vertexArray* leftChain, 
			Int leftEnd,
			Int leftCorner,
			Real u,
			Int& ret_index_mono,
			Int& ret_index_pass)
{
  Int i;

  assert(leftCorner <= leftEnd);
  for(i=leftCorner; i<= leftEnd; i++)
    if(leftChain->getVertex(i)[0] >= u)
      break;
  ret_index_pass = i;
  if(ret_index_pass <= leftEnd)
    {
      for(i=ret_index_pass; i< leftEnd; i++)
	{
	  if(leftChain->getVertex(i+1)[0] <= leftChain->getVertex(i)[0])
	    break;
	}
      ret_index_mono = i;
    }

}

void findBotRightSegment(vertexArray* rightChain, 
			 Int rightEnd,
			 Int rightCorner,
			 Real u,
			 Int& ret_index_mono,
			 Int& ret_index_pass)
{
  Int i;
  assert(rightCorner <= rightEnd);
  for(i=rightCorner; i<= rightEnd; i++)
    if(rightChain->getVertex(i)[0] <= u)
      break;



  ret_index_pass = i;

  if(ret_index_pass <= rightEnd)
    {
      for(i=ret_index_pass; i< rightEnd; i++)
	{
	  if(rightChain->getVertex(i+1)[0] >= rightChain->getVertex(i)[0])
	    break;
	}
      ret_index_mono = i;
    }
}


void sampleBotRightWithGridLinePost(Real* botVertex,
				    vertexArray* rightChain,
				    Int rightEnd,
				    Int segIndexMono,
				    Int segIndexPass,
				    Int rightCorner,
				    gridWrap* grid,
				    Int gridV,
				    Int leftU,
				    Int rightU,
				    primStream* pStream)
{
  //the possible section which is to the right of rightU
  if(segIndexPass > rightCorner) //from corner to pass-1 is > u.
    {
      Real *tempBot;
      if(segIndexPass <= rightEnd) //there is a point to the left of u
	tempBot = rightChain->getVertex(segIndexPass);
      else   //nothing is to the left of u.
	tempBot = botVertex; 
      Real tempTop[2];
      tempTop[0] = grid->get_u_value(rightU);
      tempTop[1] = grid->get_v_value(gridV);
      
      monoTriangulation2(tempTop, tempBot,
			 rightChain,
			 rightCorner,
			 segIndexPass-1,
			 0, // a decrease chain
			 pStream);
    }

  //the possible section which is strictly Umonotone
  if(segIndexPass <= rightEnd) //segIndex pass and mono exist
    {
      //if there are grid points which are to the left of botVertex
      //then we should use botVertex to form a fan with these points to
      //optimize the triangulation
      int do_optimize = 1;
      if(botVertex[0] <= grid->get_u_value(leftU))
	do_optimize = 0;
      else
	{
	  //we also have to make sure that botVertex is the left most vertex on the chain
	  int i;
	  for(i=segIndexMono; i<=rightEnd; i++)
	    if(rightChain->getVertex(i)[0] <= botVertex[0])
	      {
		do_optimize = 0;
		break;
	      }
	}

      if(do_optimize)
	{
	  //find midU so that grid->get_u_value(midU) <= botVertex[0]
	  //and               grid->get_u_value(midU) >  botVertex[0]
	  int midU = leftU;
	  while(grid->get_u_value(midU) <= botVertex[0])
	    {
	      midU++;
	      if(midU > rightU)
		break;
	    }
	  midU--;

	  grid->outputFanWithPoint(gridV, leftU, midU, botVertex, pStream);
	  stripOfFanRight(rightChain, segIndexMono, segIndexPass, grid, gridV, midU, rightU, pStream, 1);	  
	  Real tempTop[2];
	  tempTop[0] = grid->get_u_value(midU);
	  tempTop[1] = grid->get_v_value(gridV);
	  monoTriangulation2(tempTop, botVertex, rightChain, segIndexMono, rightEnd, 0, pStream);
	}
      else //not optimize
	{
	  stripOfFanRight(rightChain, segIndexMono, segIndexPass, grid, gridV, leftU, rightU, pStream, 1);
	  Real tempTop[2];
	  tempTop[0] = grid->get_u_value(leftU);
	  tempTop[1] = grid->get_v_value(gridV);
	  monoTriangulation2(tempTop, botVertex, rightChain, segIndexMono, rightEnd, 0, pStream);
	}
    }
  else //the botVertex forms a fan witht eh grid points
    grid->outputFanWithPoint(gridV, leftU, rightU, botVertex, pStream);
}
      
void sampleBotRightWithGridLine(Real* botVertex, 
				vertexArray* rightChain,
				Int rightEnd,
				Int rightCorner,
				gridWrap* grid,
				Int gridV,
				Int leftU,
				Int rightU,
				primStream* pStream)
{
  //if right chaain is empty, then there is only one bot vertex with
  //one grid line
  if(rightEnd<rightCorner){
    grid->outputFanWithPoint(gridV, leftU, rightU, botVertex, pStream);
    return;
  }

  Int segIndexMono, segIndexPass;
  findBotRightSegment(rightChain,
		      rightEnd,
		      rightCorner,
		      grid->get_u_value(rightU),
		      segIndexMono,
		      segIndexPass);

  sampleBotRightWithGridLinePost(botVertex, 
				 rightChain,
				 rightEnd,
				 segIndexMono,
				 segIndexPass,
				 rightCorner,
				 grid,
				 gridV,
				 leftU,
				 rightU,
				 pStream);
}
  
 
void sampleBotLeftWithGridLinePost(Real* botVertex,
				   vertexArray* leftChain,
				   Int leftEnd,
				   Int segIndexMono,
				   Int segIndexPass,
				   Int leftCorner,
				   gridWrap* grid,
				   Int gridV,
				   Int leftU, 
				   Int rightU,
				   primStream* pStream)
{

  //the possible section which is to the left of leftU
  if(segIndexPass > leftCorner) //at least leftCorner is to the left of leftU
    {
      Real *tempBot; 
      if(segIndexPass <= leftEnd) //from corner to pass-1 is <u
	tempBot = leftChain->getVertex(segIndexPass);
      else //nothing is to the rigth of u
	tempBot = botVertex;
      Real tempTop[2];
      tempTop[0] = grid->get_u_value(leftU);
      tempTop[1] = grid->get_v_value(gridV);
      monoTriangulation2(tempTop, tempBot, leftChain, leftCorner, segIndexPass-1,
			 1, //a increase chain,
			 pStream);
    }
  //the possible section which is strictly Umonotone
  if(segIndexPass <= leftEnd) //segIndexpass and mono exist
    {
      stripOfFanLeft(leftChain, segIndexMono, segIndexPass, grid, gridV, leftU, rightU, pStream, 1);
      Real tempTop[2];
      tempTop[0] = grid->get_u_value(rightU);
      tempTop[1] = grid->get_v_value(gridV);

      monoTriangulation2(tempTop, botVertex, leftChain, segIndexMono, leftEnd, 
			 1,  //increase chain
			 pStream);
    }
  else //the botVertex forms a fan with the grid points
    {
      grid->outputFanWithPoint(gridV, leftU, rightU, botVertex, pStream);
    }

}

void sampleBotLeftWithGridLine(Real* botVertex,
			       vertexArray* leftChain,
			       Int leftEnd,
			       Int leftCorner,
			       gridWrap* grid,
			       Int gridV,
			       Int leftU,
			       Int rightU,
			       primStream* pStream)
{

  //if leftChain is empty, then there is only one botVertex with one grid line
  if(leftEnd< leftCorner){
    grid->outputFanWithPoint(gridV, leftU, rightU, botVertex, pStream);
    return;
  }

  Int segIndexPass, segIndexMono;
  findBotLeftSegment(leftChain, leftEnd, leftCorner, grid->get_u_value(leftU), segIndexMono, segIndexPass);

  sampleBotLeftWithGridLinePost(botVertex,
			    leftChain,
			    leftEnd,
			    segIndexMono,
			    segIndexPass,
			    leftCorner,
			    grid,
			    gridV,
			    leftU, rightU, pStream);
}

//return 1 if separator exists, 0 otherwise
Int findBotSeparator(vertexArray* leftChain,
		     Int leftEnd,
		     Int leftCorner,
		     vertexArray* rightChain,
		     Int rightEnd,
		     Int rightCorner,
		     Int& ret_sep_left,
		     Int& ret_sep_right)
{
  Int oldLeftI, oldRightI, newLeftI, newRightI;
  Int i,j,k;
  Real leftMax /*= leftChain->getVertex(leftCorner)[0]*/;
  Real rightMin /*= rightChain->getVertex(rightCorner)[0]*/;
  if(leftChain->getVertex(leftCorner)[1] < rightChain->getVertex(rightCorner)[1])//leftlower
    {
      oldLeftI = leftCorner-1;
      oldRightI = rightCorner;
      leftMax = leftChain->getVertex(leftCorner)[0] - Real(1.0) ; //initilize to be left of leftCorner
      rightMin = rightChain->getVertex(rightCorner)[0]; 
    }
  else //rightlower
    {
      oldLeftI = leftCorner;
      oldRightI = rightCorner-1;
      leftMax = leftChain->getVertex(leftCorner)[0];
      rightMin = rightChain->getVertex(rightCorner)[0] + Real(1.0);
    }

  //i: the current working leftChain Index
  //j: the curent working right chian index
  //if(left(i) is lower than right(j), then the two chains above right(j) are separated.
  //else the two chains below left(i) are separated.
  i = leftCorner;
  j = rightCorner;
  while(1)
    {
      newLeftI = oldLeftI;
      newRightI = oldRightI;
      if(i> leftEnd) //left chain is doen , go through remaining right chain
	{
	  for(k=j+1; k<= rightEnd; 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, above right(k+1) is separated: oldLeftI, oldRightI
	    }
	  break; //the while loop
	}
      else if(j > rightEnd) //right Chain is doen
	{
	  for(k=i+1; k<= leftEnd; 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, above left(k+1) is separated: oldLeftI, oldRightI
	    }
	  break; //the while loop
	}
      else if(leftChain->getVertex(i)[1] < rightChain->getVertex(j)[1]) //left lower
	{

	  if(leftChain->getVertex(i)[0] > leftMax) //update leftMax amd newLeftI
	    {
	      leftMax = leftChain->getVertex(i)[0];
	      newLeftI = i;
	    }
	  for(k=j+1; k<= rightEnd; k++) //update rightMin and newRightI;
	    {
	      if(rightChain->getVertex(k)[1] < leftChain->getVertex(i)[1]) //right gets lower
		break;
	      if(rightChain->getVertex(k)[0] < rightMin)
		{
		  rightMin = rightChain->getVertex(k)[0];
		  newRightI = k;
		}
	    }
	  j = k; //next working j, since j will he lower than i in next loop
	  if(leftMax >= rightMin) //there is a conflict
	    break;
	  else //still no conflict
	    {
	      oldLeftI = newLeftI;
	      oldRightI = newRightI;

	    }
	}
      else //right lower
	{
	  if(rightChain->getVertex(j)[0] < rightMin)
	    {
	      rightMin = rightChain->getVertex(j)[0];
	      newRightI = j;
	    }
	  for(k=i+1; k<= leftEnd; k++)
	    {
	      if(leftChain->getVertex(k)[1] < rightChain->getVertex(j)[1])