/* $Id: sampleCompTop.cpp,v 1.1 2000-02-09 08:48:35 jeroen Exp $ */
/*
** 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.0 (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: 2000-02-09 08:48:35 $ $Revision: 1.1 $
*/
/*
** $Header: /home/ktk/tmp/odin/2007/netlabs.cvs/odin32/src/opengl/glu/nurbs/nurbtess/sampleCompTop.cpp,v 1.1 2000-02-09 08:48:35 jeroen Exp $
*/

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

#ifdef __WIN32OS2__
#undef max
#define max(a,b) ((a>b)? a:b)
#endif

//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] - 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] + 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 = j;
         Real tempMin = 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 = fabs(inc_chain->getVertex(i)[0] - dec_chain->getVertex(l)[0]);
                 tempI = l;
               }
           }
         //inc_chain[i] and dec_chain[tempI] are connected.
         monoTriangulationRecGenOpt(dec_chain->getVertex(tempI),
                                    botVertex,
                                    inc_chain, i, inc_end,
                                    dec_chain, 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, 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 = 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 = 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);

}