samplecomptop.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/sampleCompTop.cc,v 1.2 2001/11/29 16:16:55 kschultz Exp $
*/

#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include "zlassert.h"
#include "sampleCompTop.h"
#include "sampleCompRight.h"

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

//return : index_small, and index_large,
//from [small, large] is strictly U-monotne,
//from [large+1, end] is <u
//and vertex[large][0] is >= u
//if eveybody is <u, the large = start-1.
//otherwise both large and small are meaningful and we have start<=small<=large<=end
void findTopLeftSegment(vertexArray* leftChain,
                        Int leftStart,
                        Int leftEnd,
                        Real u,
                        Int& ret_index_small,
                        Int& ret_index_large
                        )
{
  Int i;
  assert(leftStart <= leftEnd);
  for(i=leftEnd; i>= leftStart; i--)
    {
      if(leftChain->getVertex(i)[0] >= u)
        break;
    }
  ret_index_large = i;
  if(ret_index_large >= leftStart)
    {
      for(i=ret_index_large; i>leftStart; i--)
        {
          if(leftChain->getVertex(i-1)[0] <= leftChain->getVertex(i)[0])
            break;
        }
      ret_index_small = i;
    }
}

void findTopRightSegment(vertexArray* rightChain,
                         Int rightStart,
                         Int rightEnd,
                         Real u,
                         Int& ret_index_small,
                         Int& ret_index_large)
{
  Int i;
  assert(rightStart<=rightEnd);
  for(i=rightEnd; i>=rightStart; i--)
    {
      if(rightChain->getVertex(i)[0] <= u)
        break;
    }
  ret_index_large = i;
  if(ret_index_large >= rightStart)
    {
      for(i=ret_index_large; i>rightStart;i--)
        {
          if(rightChain->getVertex(i-1)[0] >= rightChain->getVertex(i)[0])           
	    break;
        }
      ret_index_small = i;
    }
}


void sampleTopRightWithGridLinePost(Real* topVertex,
				   vertexArray* rightChain,
				   Int rightStart,
				   Int segIndexSmall,
				   Int segIndexLarge,
				   Int rightEnd,
				   gridWrap* grid,
				   Int gridV,
				   Int leftU,
				   Int rightU,
				   primStream* pStream)
{
  //the possible section which is to the right of rightU
  if(segIndexLarge < rightEnd)
    {
      Real *tempTop;
      if(segIndexLarge >= rightStart)
        tempTop = rightChain->getVertex(segIndexLarge);
      else
        tempTop = topVertex;
      Real tempBot[2];
      tempBot[0] = grid->get_u_value(rightU);
      tempBot[1] = grid->get_v_value(gridV);
monoTriangulationRecGenOpt(tempTop, tempBot,
			   NULL, 1,0,
			   rightChain, segIndexLarge+1, rightEnd,
			   pStream);
/*
      monoTriangulation2(tempTop, tempBot,
                         rightChain,
                         segIndexLarge+1,
                         rightEnd,
                         0, //a decrease  chian
                         pStream);
*/

    }
  
  //the possible section which is strictly Umonotone
  if(segIndexLarge >= rightStart)
    {
      stripOfFanRight(rightChain, segIndexLarge, segIndexSmall, grid, gridV, leftU, rightU, pStream, 0);
      Real tempBot[2];
      tempBot[0] = grid->get_u_value(leftU);
      tempBot[1] = grid->get_v_value(gridV);
      monoTriangulation2(topVertex, tempBot, rightChain, rightStart, segIndexSmall, 0, pStream);
    }
  else //the topVertex forms a fan with the grid points
    grid->outputFanWithPoint(gridV, leftU, rightU, topVertex, pStream);
}

void sampleTopRightWithGridLine(Real* topVertex,
                                vertexArray* rightChain,
                                Int rightStart,
                                Int rightEnd,
                                gridWrap* grid,
                                Int gridV,
                                Int leftU,
                                Int rightU,
                                primStream* pStream
                                )
{
  //if right chian is empty, then there is only one topVertex with one grid line
  if(rightEnd < rightStart){
    grid->outputFanWithPoint(gridV, leftU, rightU, topVertex, pStream);
    return;
  }

  Int segIndexSmall, segIndexLarge;
  findTopRightSegment(rightChain,
                      rightStart,
                      rightEnd,
                      grid->get_u_value(rightU),
                      segIndexSmall,
                      segIndexLarge
                      );
  sampleTopRightWithGridLinePost(topVertex, rightChain,
				 rightStart,
				 segIndexSmall,
				 segIndexLarge,
				 rightEnd,
				 grid,
				 gridV,
				 leftU,
				 rightU,
				 pStream);
}


void sampleTopLeftWithGridLinePost(Real* topVertex,
				   vertexArray* leftChain,
				   Int leftStart,
				   Int segIndexSmall,
				   Int segIndexLarge,
				   Int leftEnd,
				   gridWrap* grid,
				   Int gridV,
				   Int leftU,
				   Int rightU,
				   primStream* pStream)
{
  //the possible section which is to the left of leftU

  if(segIndexLarge < leftEnd)
    {
      Real *tempTop;
      if(segIndexLarge >= leftStart)
        tempTop = leftChain->getVertex(segIndexLarge);
      else
        tempTop = topVertex;
      Real tempBot[2];
      tempBot[0] = grid->get_u_value(leftU);
      tempBot[1] = grid->get_v_value(gridV);

      monoTriangulation2(tempTop, tempBot,
                         leftChain,
                         segIndexLarge+1,
                         leftEnd,
                         1, //a increase  chian
                         pStream);
    }

  //the possible section which is strictly Umonotone
  if(segIndexLarge >= leftStart)
    {
      //if there are grid points which are to the right of topV,
      //then we should use topVertex to form a fan with these points to
      //optimize the triangualtion
      int do_optimize=1;
      if(topVertex[0] >= grid->get_u_value(rightU))
	do_optimize = 0;
      else
	{
	  //we also have to make sure that topVertex are the right most vertex
          //on the chain.
	  int i;
	  for(i=leftStart; i<=segIndexSmall; i++)
	    if(leftChain->getVertex(i)[0] >= topVertex[0])
	      {
		do_optimize = 0;
		break;
	      }
	}

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

	  grid->outputFanWithPoint(gridV, midU, rightU, topVertex, pStream);
	  stripOfFanLeft(leftChain, segIndexLarge, segIndexSmall, grid, gridV, leftU, midU, pStream, 0);
	  Real tempBot[2];
	  tempBot[0] = grid->get_u_value(midU);
	  tempBot[1] = grid->get_v_value(gridV);
	  monoTriangulation2(topVertex, tempBot, leftChain, leftStart, segIndexSmall, 1, pStream);      
	}
      else //not optimize
	{

	  stripOfFanLeft(leftChain, segIndexLarge, segIndexSmall, grid, gridV, leftU, rightU, pStream, 0);
	  Real tempBot[2];
	  tempBot[0] = grid->get_u_value(rightU);
	  tempBot[1] = grid->get_v_value(gridV);
	  monoTriangulation2(topVertex, tempBot, leftChain, leftStart, segIndexSmall, 1, pStream);
	}
    }
  else //the topVertex forms a fan with the grid points
    grid->outputFanWithPoint(gridV, leftU, rightU, topVertex, pStream);  
}				   
				   

void sampleTopLeftWithGridLine(Real* topVertex,
                                vertexArray* leftChain,
                                Int leftStart,
                                Int leftEnd,
                                gridWrap* grid,
                                Int gridV,
                                Int leftU,
                                Int rightU,
                                primStream* pStream
                                )
{
  Int segIndexSmall, segIndexLarge;
  //if left chain is empty, then there is only one top vertex with one grid 
  //  line
  if(leftEnd < leftStart) {
    grid->outputFanWithPoint(gridV, leftU, rightU, topVertex, pStream);
    return;
  }
  findTopLeftSegment(leftChain,
                      leftStart,
                      leftEnd,
                      grid->get_u_value(leftU),
                      segIndexSmall,
                      segIndexLarge
                      );
  sampleTopLeftWithGridLinePost(topVertex,
				leftChain,
				leftStart,
				segIndexSmall,
				segIndexLarge,
				leftEnd,
				grid,
				gridV,
			        leftU,
				rightU,
				pStream);   
}
 
                
//return 1 if saprator exits, 0 otherwise
Int findTopSeparator(vertexArray* leftChain,
		     Int leftStartIndex,
		     Int leftEndIndex,
		     vertexArray* rightChain,
		     Int rightStartIndex,
		     Int rightEndIndex,
		     Int& ret_sep_left,
		     Int& ret_sep_right)
{
  
  Int oldLeftI, oldRightI, newLeftI, newRightI;
  Int i,j,k;
  Real leftMax /*= leftChain->getVertex(leftEndIndex)[0]*/;
  Real rightMin /*= rightChain->getVertex(rightEndIndex)[0]*/;
  if(leftChain->getVertex(leftEndIndex)[1] > rightChain->getVertex(rightEndIndex)[1]) //left higher
    {
      oldLeftI = leftEndIndex+1;
      oldRightI = rightEndIndex;