sampleCompTop.cc

Go to the documentation of this file.

/*
** 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: 2006-03-12 00:07:02 +0000 (Sun, 12 Mar 2006) $ $Revision: 1.1 $
*/
/*
** $Header: /cygdrive/c/RCVS/CVS/ReactOS/reactos/lib/glu32/libnurbs/nurbtess/sampleCompTop.cc,v 1.1 2004/02/02 16:39:14 navaraf 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;
      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(),
                 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);
      
}