Remove libGLU

It's been moved to its own repository, found at
	http://cgit.freedesktop.org/mesa/glu/

Acked-by: Kenneth Graunke <[email protected]>

1 files changed, 0 insertions, 2427 deletions

diff --git a/src/glu/sgi/libnurbs/nurbtess/sampleMonoPoly.cc b/src/glu/sgi/libnurbs/nurbtess/sampleMonoPoly.cc
deleted file mode 100644
index 051f2410834..00000000000
--- a/src/glu/sgi/libnurbs/nurbtess/sampleMonoPoly.cc
+++ /dev/null
@@ -1,2427 +0,0 @@
-/*
-** 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.
-**
-*/
-/*
-*/
-
-#include "gluos.h"
-#include <stdlib.h>
-#include <stdio.h>
-#include <math.h>
-
-#ifndef max
-#define max(a,b) ((a>b)? a:b)
-#endif
-#ifndef min
-#define min(a,b) ((a>b)? b:a)
-#endif
-
-#include <GL/gl.h>
-
-#include "glimports.h"
-#include "zlassert.h"
-#include "sampleMonoPoly.h"
-#include "sampleComp.h"
-#include "polyDBG.h"
-#include "partitionX.h"
-
-
-#define ZERO 0.00001
-
-//#define  MYDEBUG
-
-//#define SHORTEN_GRID_LINE
-//see work/newtess/internal/test/problems
-
-
-/*split a polygon so that each vertex correcpond to one edge
- *the head of the first edge of the returned plygon must be the head of the first
- *edge of the origianl polygon. This is crucial for the code in sampleMonoPoly function
- */
- directedLine*  polygonConvert(directedLine* polygon)
-{
-  int i;
-  directedLine* ret;
-  sampledLine* sline;
-  sline = new sampledLine(2);
-  sline->setPoint(0, polygon->getVertex(0));
-  sline->setPoint(1, polygon->getVertex(1));
-  ret=new directedLine(INCREASING, sline);
-  for(i=1; i<= polygon->get_npoints()-2; i++)
-    {
-      sline = new sampledLine(2);
-      sline->setPoint(0, polygon->getVertex(i));
-      sline->setPoint(1, polygon->getVertex(i+1));
-      ret->insert(new directedLine(INCREASING, sline));
-    }
-
-  for(directedLine *temp = polygon->getNext(); temp != polygon; temp = temp->getNext())
-    {
-      for(i=0; i<= temp->get_npoints()-2; i++)
-	{
-	  sline = new sampledLine(2);
-	  sline->setPoint(0, temp->getVertex(i));
-	  sline->setPoint(1, temp->getVertex(i+1));
-	  ret->insert(new directedLine(INCREASING, sline));
-	}
-    }
-  return ret;
-}
-
-void triangulateConvexPolyVertical(directedLine* topV, directedLine* botV, primStream *pStream)
-{
-  Int i,j;
-  Int n_leftVerts;
-  Int n_rightVerts;
-  Real** leftVerts;
-  Real** rightVerts;
-  directedLine* tempV;
-  n_leftVerts = 0;
-  for(tempV = topV; tempV != botV; tempV = tempV->getNext())
-    {
-      n_leftVerts += tempV->get_npoints();
-    }
-  n_rightVerts=0;
-  for(tempV = botV; tempV != topV; tempV = tempV->getNext())
-    {
-      n_rightVerts += tempV->get_npoints();
-    }
-
-  Real2* temp_leftVerts = (Real2 *) malloc(sizeof(Real2) * n_leftVerts);
-  assert(temp_leftVerts);
-  Real2* temp_rightVerts = (Real2 *) malloc(sizeof(Real2) * n_rightVerts);
-  assert(temp_rightVerts);
-
-  leftVerts = (Real**) malloc(sizeof(Real2*) * n_leftVerts);
-  assert(leftVerts);
-  rightVerts = (Real**) malloc(sizeof(Real2*) * n_rightVerts);
-  assert(rightVerts);
-  for(i=0; i<n_leftVerts; i++)
-    leftVerts[i] = temp_leftVerts[i];
-  for(i=0; i<n_rightVerts; i++)
-    rightVerts[i] = temp_rightVerts[i];
-
-  i=0;
-  for(tempV = topV; tempV != botV; tempV = tempV->getNext())
-    {
-      for(j=1; j<tempV->get_npoints(); j++)
-	{
-	  leftVerts[i][0] = tempV->getVertex(j)[0];
-	  leftVerts[i][1] = tempV->getVertex(j)[1];
-	  i++;
-	}
-    }
-  n_leftVerts = i;
-  i=0;
-  for(tempV = topV->getPrev(); tempV != botV->getPrev(); tempV = tempV->getPrev())
-    {
-      for(j=tempV->get_npoints()-1; j>=1; j--)
-	{
-	  rightVerts[i][0] = tempV->getVertex(j)[0];
-	  rightVerts[i][1] = tempV->getVertex(j)[1];
-	  i++;
-	}
-    }
-  n_rightVerts = i;
-  triangulateXYMonoTB(n_leftVerts, leftVerts, n_rightVerts, rightVerts, pStream);
-  free(leftVerts);
-  free(rightVerts);
-  free(temp_leftVerts);
-  free(temp_rightVerts);
-}  
-
-void triangulateConvexPolyHoriz(directedLine* leftV, directedLine* rightV, primStream *pStream)
-{
-  Int i,j;
-  Int n_lowerVerts;
-  Int n_upperVerts;
-  Real2 *lowerVerts;
-  Real2 *upperVerts;
-  directedLine* tempV;
-  n_lowerVerts=0;
-  for(tempV = leftV; tempV != rightV; tempV = tempV->getNext())
-    {
-      n_lowerVerts += tempV->get_npoints();
-    }
-  n_upperVerts=0;
-  for(tempV = rightV; tempV != leftV; tempV = tempV->getNext())
-    {
-      n_upperVerts += tempV->get_npoints();
-    }
-  lowerVerts = (Real2 *) malloc(sizeof(Real2) * n_lowerVerts);
-  assert(n_lowerVerts);
-  upperVerts = (Real2 *) malloc(sizeof(Real2) * n_upperVerts);
-  assert(n_upperVerts);
-  i=0;
-  for(tempV = leftV; tempV != rightV; tempV = tempV->getNext())
-    {
-      for(j=0; j<tempV->get_npoints(); j++)
-	{
-	  lowerVerts[i][0] = tempV->getVertex(j)[0];
-	  lowerVerts[i][1] = tempV->getVertex(j)[1];
-	  i++;
-	}
-    }
-  i=0;
-  for(tempV = leftV->getPrev(); tempV != rightV->getPrev(); tempV = tempV->getPrev())
-    {
-      for(j=tempV->get_npoints()-1; j>=0; j--)
-	{
-	  upperVerts[i][0] = tempV->getVertex(j)[0];
-	  upperVerts[i][1] = tempV->getVertex(j)[1];
-	  i++;
-	}
-    }
-  triangulateXYMono(n_upperVerts, upperVerts, n_lowerVerts, lowerVerts, pStream);
-  free(lowerVerts);
-  free(upperVerts);
-}  
-void triangulateConvexPoly(directedLine* polygon, Int ulinear, Int vlinear, primStream* pStream)
-{
-  /*find left, right, top , bot
-    */
-  directedLine* tempV;
-  directedLine* topV;
-  directedLine* botV;
-  directedLine* leftV;
-  directedLine* rightV;
-  topV = botV = polygon;
-
-  for(tempV = polygon->getNext(); tempV != polygon; tempV = tempV->getNext())
-    {
-      if(compV2InY(topV->head(), tempV->head())<0) {
-
-	topV = tempV;
-      }
-      if(compV2InY(botV->head(), tempV->head())>0) {
-
-	botV = tempV;
-      }
-    }
-  //find leftV
-  for(tempV = topV; tempV != botV; tempV = tempV->getNext())
-    {
-      if(tempV->tail()[0] >= tempV->head()[0])
-	break;
-    }
-  leftV = tempV;
-  //find rightV
-  for(tempV = botV; tempV != topV; tempV = tempV->getNext())
-    {
-      if(tempV->tail()[0] <= tempV->head()[0])
-	break;
-    }
-  rightV = tempV;
-  if(vlinear)
-    {
-      triangulateConvexPolyHoriz( leftV, rightV, pStream);
-    }
-  else if(ulinear)
-    {
-      triangulateConvexPolyVertical(topV, botV, pStream);
-    }
-  else
-    {
-      if(DBG_is_U_direction(polygon))
-	{
-	  triangulateConvexPolyHoriz( leftV, rightV, pStream);
-	}
-      else
-	triangulateConvexPolyVertical(topV, botV, pStream);
-    }
-}	      
-
-/*for debug purpose*/
-void drawCorners(
-		 Real* topV, Real* botV,		 
-		 vertexArray* leftChain,
-		 vertexArray* rightChain,
-		 gridBoundaryChain* leftGridChain,
-		 gridBoundaryChain* rightGridChain,
-		 Int gridIndex1,
-		 Int gridIndex2,
-		 Int leftCornerWhere,
-		 Int leftCornerIndex,
-		 Int rightCornerWhere,
-		 Int rightCornerIndex,
-		 Int bot_leftCornerWhere,
-		 Int bot_leftCornerIndex,
-		 Int bot_rightCornerWhere,
-		 Int bot_rightCornerIndex)
-{
-  Real* leftCornerV;
-  Real* rightCornerV;
-  Real* bot_leftCornerV;
-  Real* bot_rightCornerV;
-
-  if(leftCornerWhere == 1)
-    leftCornerV = topV;
-  else if(leftCornerWhere == 0)
-    leftCornerV = leftChain->getVertex(leftCornerIndex);
-  else
-    leftCornerV = rightChain->getVertex(leftCornerIndex);
-
-  if(rightCornerWhere == 1)
-    rightCornerV = topV;
-  else if(rightCornerWhere == 0)
-    rightCornerV = leftChain->getVertex(rightCornerIndex);
-  else
-    rightCornerV = rightChain->getVertex(rightCornerIndex);
-
-  if(bot_leftCornerWhere == 1)
-    bot_leftCornerV = botV;
-  else if(bot_leftCornerWhere == 0)
-    bot_leftCornerV = leftChain->getVertex(bot_leftCornerIndex);
-  else
-    bot_leftCornerV = rightChain->getVertex(bot_leftCornerIndex);
-
-  if(bot_rightCornerWhere == 1)
-    bot_rightCornerV = botV;
-  else if(bot_rightCornerWhere == 0)
-    bot_rightCornerV = leftChain->getVertex(bot_rightCornerIndex);
-  else
-    bot_rightCornerV = rightChain->getVertex(bot_rightCornerIndex);
-
-  Real topGridV = leftGridChain->get_v_value(gridIndex1);
-  Real topGridU1 = leftGridChain->get_u_value(gridIndex1);
-  Real topGridU2 = rightGridChain->get_u_value(gridIndex1);
-  Real botGridV = leftGridChain->get_v_value(gridIndex2);
-  Real botGridU1 = leftGridChain->get_u_value(gridIndex2);
-  Real botGridU2 = rightGridChain->get_u_value(gridIndex2);
-  
-  glBegin(GL_LINE_STRIP);
-  glVertex2fv(leftCornerV);
-  glVertex2f(topGridU1, topGridV);
-  glEnd();
-
-  glBegin(GL_LINE_STRIP);
-  glVertex2fv(rightCornerV);
-  glVertex2f(topGridU2, topGridV);
-  glEnd();
-
-  glBegin(GL_LINE_STRIP);
-  glVertex2fv(bot_leftCornerV);
-  glVertex2f(botGridU1, botGridV);
-  glEnd();
-
-  glBegin(GL_LINE_STRIP);
-  glVertex2fv(bot_rightCornerV);
-  glVertex2f(botGridU2, botGridV);
-  glEnd();
-
-
-}
-		 
-void toVertexArrays(directedLine* topV, directedLine* botV, vertexArray& leftChain, vertexArray& rightChain)
-{  
-  Int i;
-  directedLine* tempV;
-  for(i=1; i<=topV->get_npoints()-2; i++) { /*the first vertex is the top vertex which doesn't belong to inc_chain*/
-    leftChain.appendVertex(topV->getVertex(i));
-  }
-  for(tempV = topV->getNext(); tempV != botV; tempV = tempV->getNext())
-    {
-      for(i=0; i<=tempV->get_npoints()-2; i++){
-	leftChain.appendVertex(tempV->getVertex(i));
-      }
-    }  
-
-  for(tempV = topV->getPrev(); tempV != botV; tempV = tempV->getPrev())
-    {
-      for(i=tempV->get_npoints()-2; i>=0; i--){
-	rightChain.appendVertex(tempV->getVertex(i));
-      }
-    }
-  for(i=botV->get_npoints()-2; i>=1; i--){ 
-    rightChain.appendVertex(tempV->getVertex(i));
-  }
-}
-
-
-void findTopAndBot(directedLine* polygon, directedLine*& topV, directedLine*& botV)
-{
-  assert(polygon);
-  directedLine* tempV;
-  topV = botV = polygon;
-   for(tempV = polygon->getNext(); tempV != polygon; tempV = tempV->getNext())
-    {
-      if(compV2InY(topV->head(), tempV->head())<0) {
-	topV = tempV;
-      }
-      if(compV2InY(botV->head(), tempV->head())>0) {
-	botV = tempV;
-      }
-    }
-}
-   
-void findGridChains(directedLine* topV, directedLine* botV, 
-		    gridWrap* grid,
-		    gridBoundaryChain*& leftGridChain,
-		    gridBoundaryChain*& rightGridChain)
-{
-  /*find the first(top) and the last (bottom) grid line which intersect the
-   *this polygon
-   */
-  Int firstGridIndex; /*the index in the grid*/
-  Int lastGridIndex;
-
-  firstGridIndex = (Int) ((topV->head()[1] - grid->get_v_min()) / (grid->get_v_max() - grid->get_v_min()) * (grid->get_n_vlines()-1));
-
-  if(botV->head()[1] < grid->get_v_min())
-    lastGridIndex = 0;
-  else
-    lastGridIndex  = (Int) ((botV->head()[1] - grid->get_v_min()) / (grid->get_v_max() - grid->get_v_min()) * (grid->get_n_vlines()-1)) + 1;
-
-  /*find the interval inside  the polygon for each gridline*/
-  Int *leftGridIndices = (Int*) malloc(sizeof(Int) * (firstGridIndex - lastGridIndex +1));
-  assert(leftGridIndices);
-  Int *rightGridIndices = (Int*) malloc(sizeof(Int) * (firstGridIndex - lastGridIndex +1));
-  assert(rightGridIndices);
-  Int *leftGridInnerIndices = (Int*) malloc(sizeof(Int) * (firstGridIndex - lastGridIndex +1));
-  assert(leftGridInnerIndices);
-  Int *rightGridInnerIndices = (Int*) malloc(sizeof(Int) * (firstGridIndex - lastGridIndex +1));
-  assert(rightGridInnerIndices);
-
-  findLeftGridIndices(topV, firstGridIndex, lastGridIndex, grid,  leftGridIndices, leftGridInnerIndices);
-
-  findRightGridIndices(topV, firstGridIndex, lastGridIndex, grid,  rightGridIndices, rightGridInnerIndices);
-
-  leftGridChain =  new gridBoundaryChain(grid, firstGridIndex, firstGridIndex-lastGridIndex+1, leftGridIndices, leftGridInnerIndices);
-
-  rightGridChain = new gridBoundaryChain(grid, firstGridIndex, firstGridIndex-lastGridIndex+1, rightGridIndices, rightGridInnerIndices);
-
-  free(leftGridIndices);
-  free(rightGridIndices);
-  free(leftGridInnerIndices);
-  free(rightGridInnerIndices);
-}
-
-void findDownCorners(Real *botVertex, 
-		   vertexArray *leftChain, Int leftChainStartIndex, Int leftChainEndIndex,
-		   vertexArray *rightChain, Int rightChainStartIndex, Int rightChainEndIndex,
-		   Real v,
-		   Real uleft,
-		   Real uright,
-		   Int& ret_leftCornerWhere, /*0: left chain, 1: topvertex, 2: rightchain*/
-		   Int& ret_leftCornerIndex, /*useful when ret_leftCornerWhere == 0 or 2*/
-		   Int& ret_rightCornerWhere, /*0: left chain, 1: topvertex, 2: rightchain*/
-		   Int& ret_rightCornerIndex /*useful when ret_leftCornerWhere == 0 or 2*/
-		   )
-{
-#ifdef MYDEBUG
-printf("*************enter find donw corner\n");
-printf("finddownCorner: v=%f, uleft=%f, uright=%f\n", v, uleft, uright);
-printf("(%i,%i,%i,%i)\n", leftChainStartIndex, leftChainEndIndex,rightChainStartIndex, rightChainEndIndex); 
-printf("left chain is\n");
-leftChain->print();
-printf("right chain is\n");
-rightChain->print();
-#endif
-
-  assert(v > botVertex[1]);
-  Real leftGridPoint[2];
-  leftGridPoint[0] = uleft;
-  leftGridPoint[1] = v;
-  Real rightGridPoint[2];
-  rightGridPoint[0] = uright;
-  rightGridPoint[1] = v;
-
-  Int i;
-  Int index1, index2;
-
-  index1 = leftChain->findIndexBelowGen(v, leftChainStartIndex, leftChainEndIndex);
-  index2 = rightChain->findIndexBelowGen(v, rightChainStartIndex, rightChainEndIndex);
-
-  if(index2 <= rightChainEndIndex) //index2 was found above
-    index2 = rightChain->skipEqualityFromStart(v, index2, rightChainEndIndex);
-
-  if(index1>leftChainEndIndex && index2 > rightChainEndIndex) /*no point below v on left chain or right chain*/
-    {
-
-      /*the botVertex is the only vertex below v*/
-      ret_leftCornerWhere = 1;
-      ret_rightCornerWhere = 1;
-    }
-  else if(index1>leftChainEndIndex ) /*index2 <= rightChainEndIndex*/
-    {
-
-      ret_rightCornerWhere = 2; /*on right chain*/
-      ret_rightCornerIndex = index2;
-
-
-      Real tempMin = rightChain->getVertex(index2)[0];
-      Int tempI = index2;
-      for(i=index2+1; i<= rightChainEndIndex; i++)
-	if(rightChain->getVertex(i)[0] < tempMin)
-	  {
-	    tempI = i;
-	    tempMin = rightChain->getVertex(i)[0];
-	  }
-
-
-      //we consider whether we can use botVertex as left corner. First check 
-      //if (leftGirdPoint, botVertex) interesects right chian or not.
-     if(DBG_intersectChain(rightChain, rightChainStartIndex,rightChainEndIndex,
-				    leftGridPoint, botVertex))
-       {
-	 ret_leftCornerWhere = 2;//right
-	 ret_leftCornerIndex = index2; //should use tempI???
-       }
-     else if(botVertex[0] < tempMin)
-       ret_leftCornerWhere = 1; //bot
-     else
-       {
-	 ret_leftCornerWhere = 2; //right
-	 ret_leftCornerIndex = tempI;
-       }
-    }
-  else if(index2> rightChainEndIndex) /*index1<=leftChainEndIndex*/
-    {
-      ret_leftCornerWhere = 0; /*left chain*/
-      ret_leftCornerIndex = index1;
-      
-      /*find the vertex on the left chain with the maximum u,
-       *either this vertex or the botvertex can be used as the right corner
-       */
-
-      Int tempI;
-      //skip those points which are equal to v. (avoid degeneratcy)
-      for(tempI = index1; tempI <= leftChainEndIndex; tempI++)
-	if(leftChain->getVertex(tempI)[1] < v) 
-	  break;
-      if(tempI > leftChainEndIndex)
-	ret_rightCornerWhere = 1;
-      else
-	{
-	  Real tempMax = leftChain->getVertex(tempI)[0];
-	  for(i=tempI; i<= leftChainEndIndex; i++)
-	    if(leftChain->getVertex(i)[0] > tempMax)
-	      {
-		tempI = i;
-		tempMax = leftChain->getVertex(i)[0];
-	      }
-
-
-
-	  //we consider whether we can use botVertex as a corner. So first we check 
-	  //whether (rightGridPoint, botVertex) interescts the left chain or not.
-	  if(DBG_intersectChain(leftChain, leftChainStartIndex,leftChainEndIndex,
-				    rightGridPoint, botVertex))
-	    {
-	      ret_rightCornerWhere = 0;
-	      ret_rightCornerIndex = index1; //should use tempI???
-	    }
-	  else if(botVertex[0] > tempMax)
-	    {
-		      
-              ret_rightCornerWhere = 1;
-	    }
-	  else
-	    {
-	      ret_rightCornerWhere = 0;
-	      ret_rightCornerIndex = tempI;
-	    }
-	}
-      
-    }
-  else /*index1<=leftChainEndIndex and index2 <=rightChainEndIndex*/
-    {
-      if(leftChain->getVertex(index1)[1] >= rightChain->getVertex(index2)[1]) /*left point above right point*/
-	{
-	  ret_leftCornerWhere = 0; /*on left chain*/
-	  ret_leftCornerIndex = index1;
-
-	  Real tempMax;
-	  Int tempI;
-
-	  tempI = index1;
-	  tempMax = leftChain->getVertex(index1)[0];
-
-	  /*find the maximum u for all the points on the left above the right point index2*/
-	  for(i=index1+1; i<= leftChainEndIndex; i++)
-	    {
-	      if(leftChain->getVertex(i)[1] < rightChain->getVertex(index2)[1])
-		break;
-
-	      if(leftChain->getVertex(i)[0]>tempMax)
-		{
-		  tempI = i;
-		  tempMax = leftChain->getVertex(i)[0];
-		}
-	    }
-	  //we consider if we can use rightChain(index2) as right corner
-	  //we check if (rightChain(index2), rightGidPoint) intersecs left chain or not.
-	  if(DBG_intersectChain(leftChain, leftChainStartIndex,leftChainEndIndex, rightGridPoint, rightChain->getVertex(index2)))
-	    {
-	      ret_rightCornerWhere = 0;
-	      ret_rightCornerIndex = index1; //should use tempI???
-	    }
-	  else if(tempMax >= rightChain->getVertex(index2)[0] ||
-	     tempMax >= uright
-	     )
-	    {
-
-	      ret_rightCornerWhere = 0; /*on left Chain*/
-	      ret_rightCornerIndex = tempI;
-	    }
-	  else
-	    {
-	      ret_rightCornerWhere = 2; /*on right chain*/
-	      ret_rightCornerIndex = index2;
-	    }
-	}
-      else /*left below right*/
-	{
-	  ret_rightCornerWhere = 2; /*on the right*/
-	  ret_rightCornerIndex = index2;
-	  
-	  Real tempMin;
-	  Int tempI;
-	  
-	  tempI = index2;
-	  tempMin = rightChain->getVertex(index2)[0];
-	  
-	  /*find the minimum u for all the points on the right above the left poitn index1*/
-	  for(i=index2+1; i<= rightChainEndIndex; i++)
-	    {
-	      if( rightChain->getVertex(i)[1] < leftChain->getVertex(index1)[1])
-		break;
-	      if(rightChain->getVertex(i)[0] < tempMin)
-		{
-		  tempI = i;
-		  tempMin = rightChain->getVertex(i)[0];
-		}
-	    }
-
-	  //we consider if we can use leftchain(index1) as left corner. 
-	  //we check if (leftChain(index1) intersects right chian or not
-	  if(DBG_intersectChain(rightChain, rightChainStartIndex, rightChainEndIndex, leftGridPoint, leftChain->getVertex(index1)))
-	    {
-	      ret_leftCornerWhere = 2;
-	      ret_leftCornerIndex = index2; //should use tempI???
-	      }
-	  else if(tempMin <= leftChain->getVertex(index1)[0] ||
-	     tempMin <= uleft)				
-	    {
-	      ret_leftCornerWhere = 2; /* on right chain*/
-	      ret_leftCornerIndex = tempI;
-	    }
-	  else
-	    {
-	      ret_leftCornerWhere = 0; /*on left chain*/
-	      ret_leftCornerIndex = index1;
-	    }
-	}
-    }
-
-}
-
-
-void findUpCorners(Real *topVertex, 
-		   vertexArray *leftChain, Int leftChainStartIndex, Int leftChainEndIndex,
-		   vertexArray *rightChain, Int rightChainStartIndex, Int rightChainEndIndex,
-		   Real v,
-		   Real uleft,
-		   Real uright,
-		   Int& ret_leftCornerWhere, /*0: left chain, 1: topvertex, 2: rightchain*/
-		   Int& ret_leftCornerIndex, /*useful when ret_leftCornerWhere == 0 or 2*/
-		   Int& ret_rightCornerWhere, /*0: left chain, 1: topvertex, 2: rightchain*/
-		   Int& ret_rightCornerIndex /*useful when ret_leftCornerWhere == 0 or 2*/
-		   )
-{
-#ifdef MYDEBUG
-printf("***********enter findUpCorners\n");
-#endif
-
-  assert(v < topVertex[1]);
-  Real leftGridPoint[2];
-  leftGridPoint[0] = uleft;
-  leftGridPoint[1] = v;
-  Real rightGridPoint[2];
-  rightGridPoint[0] = uright;
-  rightGridPoint[1] = v;
-
-  Int i;
-  Int index1, index2;
-
-  index1 = leftChain->findIndexFirstAboveEqualGen(v, leftChainStartIndex, leftChainEndIndex);
-
-
-  index2 = rightChain->findIndexFirstAboveEqualGen(v, rightChainStartIndex, rightChainEndIndex);
-
-  if(index2>= leftChainStartIndex)  //index2 was found above  
-    index2 = rightChain->skipEqualityFromStart(v, index2, rightChainEndIndex);
-
-  if(index1<leftChainStartIndex && index2 <rightChainStartIndex) /*no point above v on left chain or right chain*/
-    {
-      /*the topVertex is the only vertex above v*/
-      ret_leftCornerWhere = 1;
-      ret_rightCornerWhere = 1;
-    }
-  else if(index1<leftChainStartIndex ) /*index2 >= rightChainStartIndex*/
-    {
-      ret_rightCornerWhere = 2; /*on right chain*/
-      ret_rightCornerIndex = index2;
-
-      //find the minimum u on right top, either that, or top, or right[index2] is the left corner
-      Real tempMin = rightChain->getVertex(index2)[0];
-      Int tempI = index2;
-      for(i=index2-1; i>=rightChainStartIndex; i--)
-	if(rightChain->getVertex(i)[0] < tempMin)
-	  {
-	    tempMin = rightChain->getVertex(i)[0];
-	    tempI = i;
-	  }
-      //chech whether (leftGridPoint, top) intersects rightchai,
-      //if yes, use right corner as left corner
-      //if not, use top or right[tempI] as left corner
-      if(DBG_intersectChain(rightChain, rightChainStartIndex, rightChainEndIndex,
-			leftGridPoint, topVertex))
-	{
-	  ret_leftCornerWhere = 2; //rightChain
-	  ret_leftCornerIndex = index2; 
-	}
-      else if(topVertex[0] < tempMin)
-	ret_leftCornerWhere = 1; /*topvertex*/
-      else
-	{
-	  ret_leftCornerWhere = 2; //right chain
-	  ret_leftCornerIndex = tempI;
-	}
-	      
-    }
-  else if(index2< rightChainStartIndex) /*index1>=leftChainStartIndex*/
-    {
-      ret_leftCornerWhere = 0; /*left chain*/
-      ret_leftCornerIndex = index1;
-       
-      //find the maximum u on the left top section. either that or topvertex, or left[index1]  is the right corner
-      Real tempMax = leftChain->getVertex(index1)[0];
-      Int tempI = index1;
-
-      for(i=index1-1; i>=leftChainStartIndex; i--){
-
-	if(leftChain->getVertex(i)[0] > tempMax)
-	  {
-
-	    tempMax = leftChain->getVertex(i)[0];
-	    tempI = i;
-	  }
-      }
-      //check whether (rightGridPoint, top) intersects leftChain or not
-      //if yes, we use leftCorner as the right corner
-      //if not, we use either top or left[tempI] as the right corner
-      if(DBG_intersectChain(leftChain, leftChainStartIndex,leftChainEndIndex,
-			    rightGridPoint, topVertex))
-	 {
-	   ret_rightCornerWhere = 0; //left chan
-	   ret_rightCornerIndex = index1;
-	 }
-      else if(topVertex[0] > tempMax)
-	ret_rightCornerWhere = 1;//topVertex
-      else
-	{
-	  ret_rightCornerWhere = 0;//left chain
-	  ret_rightCornerIndex = tempI;
-	}
-    }
-  else /*index1>=leftChainStartIndex and index2 >=rightChainStartIndex*/
-    {
-      if(leftChain->getVertex(index1)[1] <= rightChain->getVertex(index2)[1]) /*left point below right point*/
-	{
-	  ret_leftCornerWhere = 0; /*on left chain*/
-	  ret_leftCornerIndex = index1;
-
-	  Real tempMax;
-	  Int tempI;
-
-	  tempI = index1;
-	  tempMax = leftChain->getVertex(index1)[0];
-
-	  /*find the maximum u for all the points on the left below the right point index2*/
-	  for(i=index1-1; i>= leftChainStartIndex; i--)
-	    {
-	      if(leftChain->getVertex(i)[1] > rightChain->getVertex(index2)[1])
-		break;
-
-	      if(leftChain->getVertex(i)[0]>tempMax)
-		{
-		  tempI = i;
-		  tempMax = leftChain->getVertex(i)[0];
-		}
-	    }
-	  //chek whether (rightChain(index2), rightGridPoint) intersects leftchian or not
-	  if(DBG_intersectChain(leftChain, leftChainStartIndex, leftChainEndIndex, rightGridPoint, rightChain->getVertex(index2)))
-	     {
-	       ret_rightCornerWhere = 0;
-	       ret_rightCornerIndex = index1;
-	     }
-	  else if(tempMax >= rightChain->getVertex(index2)[0] ||
-	     tempMax >= uright)
-	    {
-	      ret_rightCornerWhere = 0; /*on left Chain*/
-	      ret_rightCornerIndex = tempI;
-	    }
-	  else
-	    {
-	      ret_rightCornerWhere = 2; /*on right chain*/
-	      ret_rightCornerIndex = index2;
-	    }
-	}
-      else /*left above right*/
-	{
-	  ret_rightCornerWhere = 2; /*on the right*/
-	  ret_rightCornerIndex = index2;
-	  
-	  Real tempMin;
-	  Int tempI;
-	  
-	  tempI = index2;
-	  tempMin = rightChain->getVertex(index2)[0];
-	  
-	  /*find the minimum u for all the points on the right below the left poitn index1*/
-	  for(i=index2-1; i>= rightChainStartIndex; i--)
-	    {
-	      if( rightChain->getVertex(i)[1] > leftChain->getVertex(index1)[1])
-		break;
-	      if(rightChain->getVertex(i)[0] < tempMin)
-		{
-		  tempI = i;
-		  tempMin = rightChain->getVertex(i)[0];
-		}
-	    }
-          //check whether (leftGRidPoint,left(index1)) interesect right chain 
-	  if(DBG_intersectChain(rightChain, rightChainStartIndex, rightChainEndIndex,
-				leftGridPoint, leftChain->getVertex(index1)))
-	    {
-	      ret_leftCornerWhere = 2; //right
-	      ret_leftCornerIndex = index2;
-	    }
-	  else if(tempMin <= leftChain->getVertex(index1)[0] ||
-	     tempMin <= uleft)
-	    {
-	      ret_leftCornerWhere = 2; /* on right chain*/
-	      ret_leftCornerIndex = tempI;
-	    }
-	  else
-	    {
-	      ret_leftCornerWhere = 0; /*on left chain*/
-	      ret_leftCornerIndex = index1;
-	    }
-	}
-    }
-#ifdef MYDEBUG
-printf("***********leave findUpCorners\n");
-#endif
-}
-
-//return 1 if neck exists, 0 othewise
-Int findNeckF(vertexArray *leftChain, Int botLeftIndex,
-	      vertexArray *rightChain, Int botRightIndex,
-	      gridBoundaryChain* leftGridChain,
-	      gridBoundaryChain* rightGridChain,
-	      Int gridStartIndex,
-	      Int& neckLeft, 
-	      Int& neckRight)
-{
-/*
-printf("enter findNeckF, botleft, botright=%i,%i,gstartindex=%i\n",botLeftIndex,botRightIndex,gridStartIndex);
-printf("leftChain is\n");
-leftChain->print();
-printf("rightChain is\n");
-rightChain->print();
-*/
-
-  Int lowerGridIndex; //the grid below leftChain and rightChian vertices
-  Int i;
-  Int n_vlines = leftGridChain->get_nVlines();
-  Real v;
-  if(botLeftIndex >= leftChain->getNumElements() ||
-     botRightIndex >= rightChain->getNumElements())
-    return 0; //no neck exists
-     
-  v=min(leftChain->getVertex(botLeftIndex)[1], rightChain->getVertex(botRightIndex)[1]);  
-
- 
-
-
-  for(i=gridStartIndex; i<n_vlines; i++)
-    if(leftGridChain->get_v_value(i) <= v && 
-       leftGridChain->getUlineIndex(i)<= rightGridChain->getUlineIndex(i))
-      break;
-  
-  lowerGridIndex = i;
-
-  if(lowerGridIndex == n_vlines) //the two trm vertex are higher than all gridlines
-    return 0;
-  else 
-    {
-      Int botLeft2, botRight2;
-/*
-printf("leftGridChain->get_v_)value=%f\n",leftGridChain->get_v_value(lowerGridIndex), botLeftIndex); 
-printf("leftChain->get_vertex(0)=(%f,%f)\n", leftChain->getVertex(0)[0],leftChain->getVertex(0)[1]);
-printf("leftChain->get_vertex(1)=(%f,%f)\n", leftChain->getVertex(1)[0],leftChain->getVertex(1)[1]);
-printf("leftChain->get_vertex(2)=(%f,%f)\n", leftChain->getVertex(2)[0],leftChain->getVertex(2)[1]);
-*/
-      botLeft2 = leftChain->findIndexFirstAboveEqualGen(leftGridChain->get_v_value(lowerGridIndex), botLeftIndex, leftChain->getNumElements()-1) -1 ;
-
-/*
-printf("botLeft2=%i\n", botLeft2);
-printf("leftChain->getNumElements=%i\n", leftChain->getNumElements());
-*/
-
-      botRight2 = rightChain->findIndexFirstAboveEqualGen(leftGridChain->get_v_value(lowerGridIndex), botRightIndex, rightChain->getNumElements()-1) -1;
-      if(botRight2 < botRightIndex) botRight2=botRightIndex;
-
-      if(botLeft2 < botLeftIndex) botLeft2 = botLeftIndex;
-
-      assert(botLeft2 >= botLeftIndex);
-      assert(botRight2 >= botRightIndex);
-      //find nectLeft so that it is th erightmost vertex on letChain
-
-      Int tempI = botLeftIndex;
-      Real temp = leftChain->getVertex(tempI)[0];
-      for(i=botLeftIndex+1; i<= botLeft2; i++)
-	if(leftChain->getVertex(i)[0] > temp)
-	  {
-	    temp = leftChain->getVertex(i)[0];
-	    tempI = i;
-	  }
-      neckLeft = tempI;
-
-      tempI = botRightIndex;
-      temp = rightChain->getVertex(tempI)[0];
-      for(i=botRightIndex+1; i<= botRight2; i++)
-	if(rightChain->getVertex(i)[0] < temp)
-	  {
-	    temp = rightChain->getVertex(i)[0];
-	    tempI = i;
-	  }
-      neckRight = tempI;
-      return 1;
-    }
-}
-							
-  
-	          
-/*find i>=botLeftIndex,j>=botRightIndex so that
- *(leftChain[i], rightChain[j]) is a neck.
- */
-void findNeck(vertexArray *leftChain, Int botLeftIndex, 
-	      vertexArray *rightChain, Int botRightIndex, 
-	      Int& leftLastIndex, /*left point of the neck*/
-	      Int& rightLastIndex /*right point of the neck*/
-	      )
-{
-  assert(botLeftIndex < leftChain->getNumElements() &&
-     botRightIndex < rightChain->getNumElements());
-     
-  /*now the neck exists for sure*/
-
-  if(leftChain->getVertex(botLeftIndex)[1] <= rightChain->getVertex(botRightIndex)[1]) //left below right
-    {
-
-      leftLastIndex = botLeftIndex;
-      
-      /*find i so that rightChain[i][1] >= leftchainbotverte[1], and i+1<
-       */
-      rightLastIndex=rightChain->findIndexAboveGen(leftChain->getVertex(botLeftIndex)[1], botRightIndex+1, rightChain->getNumElements()-1);    
-    }
-  else  //left above right
-    {
-
-      rightLastIndex = botRightIndex;
-     
-      leftLastIndex = leftChain->findIndexAboveGen(rightChain->getVertex(botRightIndex)[1], 
-						  botLeftIndex+1,
-						  leftChain->getNumElements()-1);
-    }
-}
-      
-      
-
-void findLeftGridIndices(directedLine* topEdge, Int firstGridIndex, Int lastGridIndex, gridWrap* grid,  Int* ret_indices, Int* ret_innerIndices)
-{
-
-  Int i,k,isHoriz = 0;
-  Int n_ulines = grid->get_n_ulines();
-  Real uMin = grid->get_u_min();
-  Real uMax = grid->get_u_max();
-  /*
-  Real vMin = grid->get_v_min();
-  Real vMax = grid->get_v_max();
-  */
-  Real slop = 0.0, uinterc;
-
-#ifdef SHORTEN_GRID_LINE
-  //uintercBuf stores all the interction u value for each grid line
-  //notice that lastGridIndex<= firstGridIndex
-  Real *uintercBuf = (Real *) malloc (sizeof(Real) * (firstGridIndex-lastGridIndex+1));
-  assert(uintercBuf);
-#endif
-
-  /*initialization to make vtail bigger than grid->...*/
-  directedLine* dLine = topEdge;
-  Real vtail = grid->get_v_value(firstGridIndex) + 1.0; 
-  Real tempMaxU = grid->get_u_min();
-
-
-  /*for each grid line*/
-  for(k=0, i=firstGridIndex; i>=lastGridIndex; i--, k++)
-    {
-
-      Real grid_v_value = grid->get_v_value(i);
-
-      /*check whether this grid line is below the current trim edge.*/
-      if(vtail > grid_v_value)
-	{
-	  /*since the grid line is below the trim edge, we 
-	   *find the trim edge which will contain the trim line
-	   */
-	  while( (vtail=dLine->tail()[1]) > grid_v_value){
-
-	    tempMaxU = max(tempMaxU, dLine->tail()[0]);
-	    dLine = dLine -> getNext();
-	  }
-
-	  if( fabs(dLine->head()[1] - vtail) < ZERO)
-	    isHoriz = 1;
-	  else
-	    {
-	      isHoriz = 0;
-	      slop = (dLine->head()[0] - dLine->tail()[0]) / (dLine->head()[1]-vtail);
-	    }
-	}
-
-      if(isHoriz)
-	{
-	  uinterc = max(dLine->head()[0], dLine->tail()[0]);
-	}
-      else
-	{
-	  uinterc = slop * (grid_v_value - vtail) + dLine->tail()[0];
-	}
-      
-      tempMaxU = max(tempMaxU, uinterc);
-
-      if(uinterc < uMin && uinterc >= uMin - ZERO)
-	uinterc = uMin;
-      if(uinterc > uMax && uinterc <= uMax + ZERO)
-	uinterc = uMax;
-
-#ifdef SHORTEN_GRID_LINE
-      uintercBuf[k] = uinterc;
-#endif
-
-      assert(uinterc >= uMin && uinterc <= uMax);
-       if(uinterc == uMax)
-         ret_indices[k] = n_ulines-1;
-       else
-	 ret_indices[k] = (Int)(((uinterc-uMin)/(uMax - uMin)) * (n_ulines-1)) + 1;
-      if(ret_indices[k] >= n_ulines)
-	ret_indices[k] = n_ulines-1;
-
-
-      ret_innerIndices[k] = (Int)(((tempMaxU-uMin)/(uMax - uMin)) * (n_ulines-1)) + 1;
-
-      /*reinitialize tempMaxU for next grdiLine*/
-      tempMaxU = uinterc;
-    }
-#ifdef SHORTEN_GRID_LINE
-  //for each grid line, compare the left grid point with the 
-  //intersection point. If the two points are too close, then
-  //we should move the grid point one grid to the right
-  //and accordingly we should update the inner index.
-  for(k=0, i=firstGridIndex; i>=lastGridIndex; i--, k++)
-    {
-      //check gridLine i
-      //check ret_indices[k]
-      Real a = grid->get_u_value(ret_indices[k]-1);
-      Real b = grid->get_u_value(ret_indices[k]);
-      assert(uintercBuf[k] >= a && uintercBuf < b);
-      if( (b-uintercBuf[k]) <= 0.2 * (b-a)) //interc is very close to b
-	{
-	  ret_indices[k]++;
-	}
-
-      //check ret_innerIndices[k]
-      if(k>0)
-	{
-	  if(ret_innerIndices[k] < ret_indices[k-1])
-	    ret_innerIndices[k] = ret_indices[k-1];
-	  if(ret_innerIndices[k] < ret_indices[k])
-	    ret_innerIndices[k] = ret_indices[k];
-	}
-    }
-  //clean up
-  free(uintercBuf);
-#endif
-}
-
-void findRightGridIndices(directedLine* topEdge, Int firstGridIndex, Int lastGridIndex, gridWrap* grid,  Int* ret_indices, Int* ret_innerIndices)
-{
-
-  Int i,k;
-  Int n_ulines = grid->get_n_ulines();
-  Real uMin = grid->get_u_min();
-  Real uMax = grid->get_u_max();
-  /*
-  Real vMin = grid->get_v_min();
-  Real vMax = grid->get_v_max();
-  */
-  Real slop = 0.0, uinterc;
-
-#ifdef SHORTEN_GRID_LINE
-  //uintercBuf stores all the interction u value for each grid line
-  //notice that firstGridIndex >= lastGridIndex
-  Real *uintercBuf = (Real *) malloc (sizeof(Real) * (firstGridIndex-lastGridIndex+1));
-  assert(uintercBuf);
-#endif
-
-  /*initialization to make vhead bigger than grid->v_value...*/
-  directedLine* dLine = topEdge->getPrev();
-  Real vhead = dLine->tail()[1];
-  Real tempMinU = grid->get_u_max();
-
-  /*for each grid line*/
-  for(k=0, i=firstGridIndex; i>=lastGridIndex; i--, k++)
-    {
-
-      Real grid_v_value = grid->get_v_value(i);
-
-
-      /*check whether this grid line is below the current trim edge.*/
-      if(vhead >= grid_v_value)
-	{
-	  /*since the grid line is below the tail of the trim edge, we 
-	   *find the trim edge which will contain the trim line
-	   */
-	  while( (vhead=dLine->head()[1]) > grid_v_value){
-	    tempMinU = min(tempMinU, dLine->head()[0]);
-	    dLine = dLine -> getPrev();
-	  }
-
-	  /*skip the equality in the case of degenerat case: horizontal */
-	  while(dLine->head()[1] == grid_v_value)
-	    dLine = dLine->getPrev();
-	    
-	  assert( dLine->tail()[1] != dLine->head()[1]);
-	  slop = (dLine->tail()[0] - dLine->head()[0]) / (dLine->tail()[1]-dLine->head()[1]);
-	  /*
-	   if(dLine->tail()[1] == vhead)
-	     isHoriz = 1;
-	     else
-	    {
-	      isHoriz = 0;
-	      slop = (dLine->tail()[0] - dLine->head()[0]) / (dLine->tail()[1]-vhead);
-	    }
-	    */
-	}
-	uinterc = slop * (grid_v_value - dLine->head()[1]) + dLine->head()[0];
-
-      //in case unterc is outside of the grid due to floating point
-      if(uinterc < uMin)
-	uinterc = uMin;
-      else if(uinterc > uMax)
-	uinterc = uMax;
-
-#ifdef SHORTEN_GRID_LINE
-      uintercBuf[k] = uinterc;
-#endif      
-
-      tempMinU = min(tempMinU, uinterc);
-
-      assert(uinterc >= uMin && uinterc <= uMax);      
-
-      if(uinterc == uMin)
-	ret_indices[k] = 0;
-      else
-	ret_indices[k] = (int)ceil((((uinterc-uMin)/(uMax - uMin)) * (n_ulines-1))) -1;
-/*
-if(ret_indices[k] >= grid->get_n_ulines())
-  {
-  printf("ERROR3\n");
-  exit(0);
-}
-if(ret_indices[k] < 0)    
-  {
-  printf("ERROR4\n");
-  exit(0);
-}
-*/
-      ret_innerIndices[k] = (int)ceil ((((tempMinU-uMin)/(uMax - uMin)) * (n_ulines-1))) -1;
-
-      tempMinU = uinterc;
-    }
-#ifdef SHORTEN_GRID_LINE
-  //for each grid line, compare the left grid point with the 
-  //intersection point. If the two points are too close, then
-  //we should move the grid point one grid to the right
-  //and accordingly we should update the inner index.
-  for(k=0, i=firstGridIndex; i>=lastGridIndex; i--, k++)
-    {
-      //check gridLine i
-      //check ret_indices[k]
-      Real a = grid->get_u_value(ret_indices[k]);
-      Real b = grid->get_u_value(ret_indices[k]+1);
-      assert(uintercBuf[k] > a && uintercBuf <= b);
-      if( (uintercBuf[k]-a) <= 0.2 * (b-a)) //interc is very close to a
-	{
-	  ret_indices[k]--;
-	}
-
-      //check ret_innerIndices[k]
-      if(k>0)
-	{
-	  if(ret_innerIndices[k] > ret_indices[k-1])
-	    ret_innerIndices[k] = ret_indices[k-1];
-	  if(ret_innerIndices[k] > ret_indices[k])
-	    ret_innerIndices[k] = ret_indices[k];
-	}
-    }
-  //clean up
-  free(uintercBuf);
-#endif
-}
-
-
-void sampleMonoPoly(directedLine* polygon, gridWrap* grid, Int ulinear, Int vlinear, primStream* pStream, rectBlockArray* rbArray)
-{
-/*
-{
-grid->print();
-polygon->writeAllPolygons("zloutputFile");
-exit(0);
-}
-*/
-
-if(grid->get_n_ulines() == 2 ||
-   grid->get_n_vlines() == 2)
-{ 
-  if(ulinear && grid->get_n_ulines() == 2)
-    {
-      monoTriangulationFun(polygon, compV2InY, pStream);   
-      return;
-    }
-  else if(DBG_isConvex(polygon) && polygon->numEdges() >=4)
-     {
-       triangulateConvexPoly(polygon, ulinear, vlinear, pStream);
-       return;
-     }
-  else if(vlinear || DBG_is_U_direction(polygon))
-    {
-      Int n_cusps;//num interior cusps
-      Int n_edges = polygon->numEdges();
-      directedLine** cusps = (directedLine**) malloc(sizeof(directedLine*) * n_edges);
-      assert(cusps);
-      findInteriorCuspsX(polygon, n_cusps, cusps);
-
-      if(n_cusps == 0) //u_monotone
-	{
-
-	  monoTriangulationFun(polygon, compV2InX, pStream);
-
-          free(cusps);
-          return;          
-	}
-      else if(n_cusps == 1) //one interior cusp
-	{
-
-	  directedLine* new_polygon = polygonConvert(cusps[0]);
-
-	  directedLine* other = findDiagonal_singleCuspX( new_polygon);
-
-
-
-	  //<other> should NOT be null unless there are self-intersecting
-          //trim curves. In that case, we don't want to core dump, instead,
-          //we triangulate anyway, and print out error message.
-	  if(other == NULL)
-	    {
-	      monoTriangulationFun(polygon, compV2InX, pStream);
-	      free(cusps);
-	      return;
-	    }
-
-	  directedLine* ret_p1;
-	  directedLine* ret_p2;
-
-	  new_polygon->connectDiagonal_2slines(new_polygon, other, 
-					   &ret_p1,
-					   &ret_p2,
-					   new_polygon);
-
-	  monoTriangulationFun(ret_p1, compV2InX, pStream);
-	  monoTriangulationFun(ret_p2, compV2InX, pStream);
-
-	  ret_p1->deleteSinglePolygonWithSline();	      
-	  ret_p2->deleteSinglePolygonWithSline();	  
-
-          free(cusps);
-          return;
-         }
-     free(cusps);
-     }
-}
-
-  /*find the top and bottom of the polygon. It is supposed to be
-   *a V-monotone polygon
-   */
-
-  directedLine* tempV;
-  directedLine* topV;
-  directedLine* botV;
-  topV = botV = polygon;
-
-  for(tempV = polygon->getNext(); tempV != polygon; tempV = tempV->getNext())
-    {
-      if(compV2InY(topV->head(), tempV->head())<0) {
-
-	topV = tempV;
-      }
-      if(compV2InY(botV->head(), tempV->head())>0) {
-
-	botV = tempV;
-      }
-    }
-  
-  /*find the first(top) and the last (bottom) grid line which intersect the
-   *this polygon
-   */
-  Int firstGridIndex; /*the index in the grid*/
-  Int lastGridIndex;
-  firstGridIndex = (Int) ((topV->head()[1] - grid->get_v_min()) / (grid->get_v_max() - grid->get_v_min()) * (grid->get_n_vlines()-1));
-  lastGridIndex  = (Int) ((botV->head()[1] - grid->get_v_min()) / (grid->get_v_max() - grid->get_v_min()) * (grid->get_n_vlines()-1)) + 1;
-
-
-  /*find the interval inside  the polygon for each gridline*/
-  Int *leftGridIndices = (Int*) malloc(sizeof(Int) * (firstGridIndex - lastGridIndex +1));
-  assert(leftGridIndices);
-  Int *rightGridIndices = (Int*) malloc(sizeof(Int) * (firstGridIndex - lastGridIndex +1));
-  assert(rightGridIndices);
-  Int *leftGridInnerIndices = (Int*) malloc(sizeof(Int) * (firstGridIndex - lastGridIndex +1));
-  assert(leftGridInnerIndices);
-  Int *rightGridInnerIndices = (Int*) malloc(sizeof(Int) * (firstGridIndex - lastGridIndex +1));
-  assert(rightGridInnerIndices);
-
-  findLeftGridIndices(topV, firstGridIndex, lastGridIndex, grid,  leftGridIndices, leftGridInnerIndices);
-
-  findRightGridIndices(topV, firstGridIndex, lastGridIndex, grid,  rightGridIndices, rightGridInnerIndices);
-
-  gridBoundaryChain leftGridChain(grid, firstGridIndex, firstGridIndex-lastGridIndex+1, leftGridIndices, leftGridInnerIndices);
-
-  gridBoundaryChain rightGridChain(grid, firstGridIndex, firstGridIndex-lastGridIndex+1, rightGridIndices, rightGridInnerIndices);
-
-
-
-//  leftGridChain.draw();
-//  leftGridChain.drawInner();
-//  rightGridChain.draw();
-//  rightGridChain.drawInner();
-  /*(1) determine the grid boundaries (left and right).
-   *(2) process polygon  into two monotone chaines: use vertexArray
-   *(3) call sampleMonoPolyRec
-   */
-
-  /*copy the two chains into vertexArray datastructure*/
-  Int i;
-  vertexArray leftChain(20); /*this is a dynamic array*/
-  for(i=1; i<=topV->get_npoints()-2; i++) { /*the first vertex is the top vertex which doesn't belong to inc_chain*/
-    leftChain.appendVertex(topV->getVertex(i));
-  }
-  for(tempV = topV->getNext(); tempV != botV; tempV = tempV->getNext())
-    {
-      for(i=0; i<=tempV->get_npoints()-2; i++){
-	leftChain.appendVertex(tempV->getVertex(i));
-      }
-    }
-  
-  vertexArray rightChain(20);
-  for(tempV = topV->getPrev(); tempV != botV; tempV = tempV->getPrev())
-    {
-      for(i=tempV->get_npoints()-2; i>=0; i--){
-	rightChain.appendVertex(tempV->getVertex(i));
-      }
-    }
-  for(i=botV->get_npoints()-2; i>=1; i--){ 
-    rightChain.appendVertex(tempV->getVertex(i));
-  }
-
-  sampleMonoPolyRec(topV->head(),
-		    botV->head(),
-		    &leftChain,
-		    0,
-		    &rightChain,
-		    0,
-		    &leftGridChain,
-		    &rightGridChain,
-		    0,
-		    pStream,
-		    rbArray);
-
-
-  /*cleanup space*/
-  free(leftGridIndices);
-  free(rightGridIndices);
-  free(leftGridInnerIndices);
-  free(rightGridInnerIndices);
-}
-
-void sampleMonoPolyRec(
-		       Real* topVertex,
-		       Real* botVertex,
-		       vertexArray* leftChain, 
-		       Int leftStartIndex,
-		       vertexArray* rightChain,
-		       Int rightStartIndex,
-		       gridBoundaryChain* leftGridChain, 
-		       gridBoundaryChain* rightGridChain, 
-		       Int gridStartIndex,
-		       primStream* pStream,
-		       rectBlockArray* rbArray)
-{
-
-  /*find the first connected component, and the four corners.
-   */
-  Int index1, index2; /*the first and last grid line of the first connected component*/
-
-  if(topVertex[1] <= botVertex[1])
-    return;
-    
-  /*find i so that the grid line is below the top vertex*/
-  Int i=gridStartIndex;
-  while (i < leftGridChain->get_nVlines())
-    {
-      if(leftGridChain->get_v_value(i) < topVertex[1])
-	break;
-      i++;
-    }
-
-  /*find the first connected component starting with i*/
-  /*find index1 so that left_uline_index <= right_uline_index, that is, this
-   *grid line contains at least one inner grid point
-   */
-  index1=i;
-  int num_skipped_grid_lines=0;
-  while(index1 < leftGridChain->get_nVlines())
-    {
-      if(leftGridChain->getUlineIndex(index1) <= rightGridChain->getUlineIndex(index1))
-	break;
-      num_skipped_grid_lines++;
-      index1++;
-    }
-
-
-
-  if(index1 >= leftGridChain->get_nVlines()) /*no grid line exists which has inner point*/
-    {
-      /*stop recursion, ...*/
-      /*monotone triangulate it...*/
-//      printf("no grid line exists\n");      
-/*
-      monoTriangulationRecOpt(topVertex, botVertex, leftChain, leftStartIndex,
-			   rightChain, rightStartIndex, pStream);
-*/
-
-if(num_skipped_grid_lines <2)
-  {
-    monoTriangulationRecGenOpt(topVertex, botVertex, leftChain, leftStartIndex,
-			       leftChain->getNumElements()-1,
-			       rightChain, rightStartIndex, 
-			       rightChain->getNumElements()-1,
-			       pStream);
-  }
-else
-  {
-    //the optimum way to triangulate is top-down since this polygon
-    //is narrow-long.
-    monoTriangulationRec(topVertex, botVertex, leftChain, leftStartIndex,
-			 rightChain, rightStartIndex, pStream);
-  }
-
-/*
-      monoTriangulationRec(topVertex, botVertex, leftChain, leftStartIndex,
-			   rightChain, rightStartIndex, pStream);
-*/
-
-/*      monoTriangulationRecGenTBOpt(topVertex, botVertex, 
-				   leftChain, leftStartIndex, leftChain->getNumElements()-1,
-				   rightChain, rightStartIndex, rightChain->getNumElements()-1, 
-				   pStream);*/
-      
-
-
-    }
-  else
-    {
-
-      /*find index2 so that left_inner_index <= right_inner_index holds until index2*/
-      index2=index1+1;
-      if(index2 < leftGridChain->get_nVlines())
-	while(leftGridChain->getInnerIndex(index2) <= rightGridChain->getInnerIndex(index2))
-	  {
-	    index2++;
-	    if(index2 >= leftGridChain->get_nVlines())
-	      break;
-	  }
-      
-      index2--;
-      
-
-      
-      /*the neck*/
-      Int neckLeftIndex;
-      Int neckRightIndex;
-
-      /*the four corners*/
-      Int up_leftCornerWhere;
-      Int up_leftCornerIndex;
-      Int up_rightCornerWhere;
-      Int up_rightCornerIndex;
-      Int down_leftCornerWhere;
-      Int down_leftCornerIndex;
-      Int down_rightCornerWhere;
-      Int down_rightCornerIndex;
-
-      Real* tempBotVertex; /*the bottom vertex for this component*/
-      Real* nextTopVertex=NULL; /*for the recursion*/
-      Int nextLeftStartIndex=0;
-      Int nextRightStartIndex=0;
-
-      /*find the points below the grid line index2 on both chains*/
-      Int botLeftIndex = leftChain->findIndexStrictBelowGen(
-						      leftGridChain->get_v_value(index2),
-						      leftStartIndex,
-						      leftChain->getNumElements()-1);
-      Int botRightIndex = rightChain->findIndexStrictBelowGen(
-							rightGridChain->get_v_value(index2),
-							rightStartIndex,
-							rightChain->getNumElements()-1);
-      /*if either botLeftIndex>= numelements,
-       *        or botRightIndex >= numelemnet,
-       *then there is no neck exists. the bottom vertex is botVertex, 
-       */
-      if(! findNeckF(leftChain, botLeftIndex, rightChain, botRightIndex,
-		   leftGridChain, rightGridChain, index2, neckLeftIndex, neckRightIndex))
-	 /*
-      if(botLeftIndex == leftChain->getNumElements() ||
-	 botRightIndex == rightChain->getNumElements())
-	 */
-	{
-#ifdef MYDEBUG
-	  printf("neck NOT exists, botRightIndex=%i\n", botRightIndex);
-#endif
-
-	  tempBotVertex =  botVertex;
-	  nextTopVertex = botVertex;
-	  botLeftIndex = leftChain->getNumElements()-1;
-	  botRightIndex = rightChain->getNumElements()-1;
-	}
-      else /*neck exists*/
-	{
-#ifdef MYDEBUG
-	  printf("neck exists\n");
-#endif
-
-          /*
-	  findNeck(leftChain, botLeftIndex,
-		   rightChain, botRightIndex,
-		   neckLeftIndex,
-		   neckRightIndex);
-		   */
-#ifdef MYDEBUG
-printf("neck is found, neckLeftIndex=%i, neckRightIndex=%i\n", neckLeftIndex, neckRightIndex);
-glBegin(GL_LINES);
-glVertex2fv(leftChain->getVertex(neckLeftIndex));
-glVertex2fv(rightChain->getVertex(neckRightIndex));
-glEnd();
-#endif
-
-	  if(leftChain->getVertex(neckLeftIndex)[1] <= rightChain->getVertex(neckRightIndex)[1])
-	    {
-	      tempBotVertex = leftChain->getVertex(neckLeftIndex);
-	      botLeftIndex = neckLeftIndex-1;
-	      botRightIndex = neckRightIndex;
-	      nextTopVertex = rightChain->getVertex(neckRightIndex);
-	      nextLeftStartIndex = neckLeftIndex;
-	      nextRightStartIndex = neckRightIndex+1;
-	    }
-	  else
-	    {
-	      tempBotVertex = rightChain->getVertex(neckRightIndex);
-	      botLeftIndex = neckLeftIndex;
-	      botRightIndex = neckRightIndex-1;		  
-	      nextTopVertex = leftChain->getVertex(neckLeftIndex);
-	      nextLeftStartIndex = neckLeftIndex+1;
-	      nextRightStartIndex = neckRightIndex;
-	    }
-	}
-
-      findUpCorners(topVertex,
-		    leftChain,
-		    leftStartIndex, botLeftIndex,
-		    rightChain,
-		    rightStartIndex, botRightIndex,
-		    leftGridChain->get_v_value(index1),
-		    leftGridChain->get_u_value(index1),
-		    rightGridChain->get_u_value(index1),
-		    up_leftCornerWhere,
-		    up_leftCornerIndex,
-		    up_rightCornerWhere,
-		    up_rightCornerIndex);
-
-      findDownCorners(tempBotVertex,
-		      leftChain,
-		      leftStartIndex, botLeftIndex,
-		      rightChain,
-		      rightStartIndex, botRightIndex,
-		      leftGridChain->get_v_value(index2),
-		      leftGridChain->get_u_value(index2),
-		      rightGridChain->get_u_value(index2),
-		      down_leftCornerWhere,
-		      down_leftCornerIndex,
-		      down_rightCornerWhere,
-		      down_rightCornerIndex);	      
-#ifdef MYDEBUG
-      printf("find corners done, down_leftwhere=%i, down_righwhere=%i,\n",down_leftCornerWhere, down_rightCornerWhere );
-      printf("find corners done, up_leftwhere=%i, up_righwhere=%i,\n",up_leftCornerWhere, up_rightCornerWhere );
-      printf("find corners done, up_leftindex=%i, up_righindex=%i,\n",up_leftCornerIndex, up_rightCornerIndex );
-      printf("find corners done, down_leftindex=%i, down_righindex=%i,\n",down_leftCornerIndex, down_rightCornerIndex );
-#endif
-
-/*
-      drawCorners(topVertex,
-		  tempBotVertex,
-		  leftChain,
-		  rightChain,
-		  leftGridChain,
-		  rightGridChain,
-		  index1,
-		  index2,
-		  up_leftCornerWhere,
-		  up_leftCornerIndex,
-		  up_rightCornerWhere,
-		  up_rightCornerIndex,
-		  down_leftCornerWhere,
-		  down_leftCornerIndex,
-		  down_rightCornerWhere,
-		  down_rightCornerIndex);
-*/
-
-
-      sampleConnectedComp(topVertex, tempBotVertex,
-			  leftChain, 
-			  leftStartIndex, botLeftIndex,
-			  rightChain,
-			  rightStartIndex, botRightIndex,
-			  leftGridChain,
-			  rightGridChain,
-			  index1, index2,
-			  up_leftCornerWhere,
-			  up_leftCornerIndex,
-			  up_rightCornerWhere,
-			  up_rightCornerIndex,
-			  down_leftCornerWhere,
-			  down_leftCornerIndex,
-			  down_rightCornerWhere,
-			  down_rightCornerIndex,
-			  pStream,
-			  rbArray
-			  );
-
-      /*recursion*/
-
-      sampleMonoPolyRec(
-			nextTopVertex,
-			botVertex,
-			leftChain, 
-			nextLeftStartIndex,
-			rightChain,
-			nextRightStartIndex,
-			leftGridChain, 
-			rightGridChain, 
-			index2+1,
-			pStream, rbArray);
-			
-
-    }
-
-}
-
-void sampleLeftStrip(vertexArray* leftChain,
-		     Int topLeftIndex,
-		     Int botLeftIndex,
-		     gridBoundaryChain* leftGridChain,
-		     Int leftGridChainStartIndex,
-		     Int leftGridChainEndIndex,
-		     primStream* pStream
-		     )
-{
-  assert(leftChain->getVertex(topLeftIndex)[1] > leftGridChain->get_v_value(leftGridChainStartIndex));
-  assert(leftChain->getVertex(topLeftIndex+1)[1] <= leftGridChain->get_v_value(leftGridChainStartIndex));
-  assert(leftChain->getVertex(botLeftIndex)[1] <= leftGridChain->get_v_value(leftGridChainEndIndex));
-  assert(leftChain->getVertex(botLeftIndex-1)[1] > leftGridChain->get_v_value(leftGridChainEndIndex));
-
-  /*
-   *(1)find the last grid line which doesn'; pass below
-   * this first edge, sample this region: one trim edge and 
-   * possily multiple grid lines.
-   */
-  Real *upperVert, *lowerVert; /*the end points of the first trim edge*/
-  upperVert = leftChain->getVertex(topLeftIndex);
-  lowerVert = leftChain->getVertex(topLeftIndex+1);
-  
-  Int index = leftGridChainStartIndex;
-  while(leftGridChain->get_v_value(index) >= lowerVert[1]){
-    index++;
-    if(index > leftGridChainEndIndex) 
-      break;
-  }
-  index--;
-  
-  sampleLeftSingleTrimEdgeRegion(upperVert, lowerVert,
-				 leftGridChain,
-				 leftGridChainStartIndex,
-				 index,
-				 pStream);
-  sampleLeftStripRec(leftChain, topLeftIndex+1, botLeftIndex,
-		     leftGridChain, index, leftGridChainEndIndex,
-		     pStream);
-
-}
-
-void sampleLeftStripRec(vertexArray* leftChain,
-		     Int topLeftIndex,
-		     Int botLeftIndex,
-		     gridBoundaryChain* leftGridChain,
-		     Int leftGridChainStartIndex,
-		     Int leftGridChainEndIndex,
-			primStream* pStream
-		     )
-{
-  /*now top left trim vertex is below the top grid line.
-   */
-  /*stop condition: if topLeftIndex >= botLeftIndex, then stop.
-   */
-  if(topLeftIndex >= botLeftIndex) 
-    return;
-
-  /*find the last trim vertex which is above the second top grid line:
-   * index1.
-   *and sampleLeftOneGridStep(leftchain, topLeftIndex, index1, leftGridChain,
-   * leftGridChainStartIndex).
-   * index1 could be equal to topLeftIndex.
-   */
-  Real secondGridChainV = leftGridChain->get_v_value(leftGridChainStartIndex+1);
-  assert(leftGridChainStartIndex < leftGridChainEndIndex);
-  Int index1 = topLeftIndex;
-  while(leftChain->getVertex(index1)[1] > secondGridChainV)
-    index1++;
-  index1--;
-  
-  sampleLeftOneGridStep(leftChain, topLeftIndex, index1, leftGridChain, leftGridChainStartIndex, pStream);
-
-
-  /* 
-   * Let the next trim vertex be nextTrimVertIndex (which should be  
-   *  below the second grid line).
-   * Find the last grid line index2 which is above nextTrimVert.
-   * sampleLeftSingleTrimEdgeRegion(uppervert[2], lowervert[2], 
-   *                      leftGridChain, leftGridChainStartIndex+1, index2).
-   */
-  Real *uppervert, *lowervert;
-  uppervert = leftChain->getVertex(index1);
-  lowervert = leftChain->getVertex(index1+1);
-  Int index2 = leftGridChainStartIndex+1;
-
-  while(leftGridChain->get_v_value(index2) >= lowervert[1])
-    {
-      index2++;
-      if(index2 > leftGridChainEndIndex)
-	break;
-    }
-  index2--;
-  sampleLeftSingleTrimEdgeRegion(uppervert, lowervert, leftGridChain, leftGridChainStartIndex+1, index2,  pStream);
-
-   /* sampleLeftStripRec(leftChain, 
-                        nextTrimVertIndex,
-                        botLeftIndex,
-                        leftGridChain,
-			index2,
-                        leftGridChainEndIndex
-			)
-   *
-   */
-  sampleLeftStripRec(leftChain, index1+1, botLeftIndex, leftGridChain, index2, leftGridChainEndIndex, pStream);
-  
-}
-
-
-/***************begin RecF***********************/
-/* the gridlines from leftGridChainStartIndex to 
- * leftGridChainEndIndex are assumed to form a
- * connected component.
- * the trim vertex of topLeftIndex is assumed to
- * be below the first gridline, and the tim vertex
- * of botLeftIndex is assumed to be above the last
- * grid line.
- * If botLeftIndex < topLeftIndex, then no connected componeent exists, and this funcion returns without
- * outputing any triangles.
- * Otherwise botLeftIndex >= topLeftIndex, there is at least one triangle to output.
- */
-void sampleLeftStripRecF(vertexArray* leftChain,
-		     Int topLeftIndex,
-		     Int botLeftIndex,
-		     gridBoundaryChain* leftGridChain,
-		     Int leftGridChainStartIndex,
-		     Int leftGridChainEndIndex,
-			primStream* pStream
-		     )
-{
-  /*now top left trim vertex is below the top grid line.
-   */
-  /*stop condition: if topLeftIndex > botLeftIndex, then stop.
-   */
-  if(topLeftIndex > botLeftIndex) 
-    return;
-
-  /*if there is only one grid Line, return.*/
-
-  if(leftGridChainStartIndex>=leftGridChainEndIndex)
-    return;
-
-
-  assert(leftChain->getVertex(topLeftIndex)[1] <= leftGridChain->get_v_value(leftGridChainStartIndex) &&
-	 leftChain->getVertex(botLeftIndex)[1] >= leftGridChain->get_v_value(leftGridChainEndIndex));
-
-  /*firs find the first trim vertex which is below or equal to the second top grid line:
-   * index1.
-   */
-  Real secondGridChainV = leftGridChain->get_v_value(leftGridChainStartIndex+1);
-
-
-  Int index1 = topLeftIndex;
-
-  while(leftChain->getVertex(index1)[1] > secondGridChainV){
-    index1++;
-    if(index1>botLeftIndex)
-      break;
-  }
-
-  /*now leftChain->getVertex(index-1)[1] > secondGridChainV and
-   *    leftChain->getVertex(index)[1] <= secondGridChainV
-   *If equality holds, then we should include the vertex index1, otherwise we include only index1-1, to
-   *perform sampleOneGridStep.
-   */
-  if(index1>botLeftIndex) 
-    index1--;
-  else if(leftChain->getVertex(index1)[1] < secondGridChainV)
-    index1--;
-
-  /*now we have leftChain->getVertex(index1)[1] >= secondGridChainV, and 
-   *  leftChain->getVertex(index1+1)[1] <= secondGridChainV
-   */
-
-
-  sampleLeftOneGridStep(leftChain, topLeftIndex, index1, leftGridChain, leftGridChainStartIndex, pStream);
-
-
-  /*if leftChain->getVertex(index1)[1] == secondGridChainV, then we can recursively do the rest.
-   */
-  if(leftChain->getVertex(index1)[1] == secondGridChainV)
-    {
-
-      sampleLeftStripRecF(leftChain, index1, botLeftIndex,leftGridChain, leftGridChainStartIndex+1, leftGridChainEndIndex, pStream);
-    }
-  else if(index1 < botLeftIndex)
-    {
-
-      /* Otherwise, we have leftChain->getVertex(index1)[1] > secondGridChainV,
-       * let the next trim vertex be nextTrimVertIndex (which should be  strictly
-       *  below the second grid line).
-       * Find the last grid line index2 which is above nextTrimVert.
-       * sampleLeftSingleTrimEdgeRegion(uppervert[2], lowervert[2], 
-       *                      leftGridChain, leftGridChainStartIndex+1, index2).
-       */
-      Real *uppervert, *lowervert;
-      uppervert = leftChain->getVertex(index1);
-      lowervert = leftChain->getVertex(index1+1); //okay since index1<botLeftIndex
-      Int index2 = leftGridChainStartIndex+1;
-
-      
-      while(leftGridChain->get_v_value(index2) >= lowervert[1])
-	{
-	  index2++;
-	  if(index2 > leftGridChainEndIndex)
-	    break;
-	}
-      index2--;
-
-      
-      sampleLeftSingleTrimEdgeRegion(uppervert, lowervert, leftGridChain, leftGridChainStartIndex+1, index2,  pStream);
-      
-      /*recursion*/
-
-      sampleLeftStripRecF(leftChain, index1+1, botLeftIndex, leftGridChain, index2, leftGridChainEndIndex, pStream);
-    }
-  
-}
-
-/***************End RecF***********************/
-
-/*sample the left area in between one trim edge and multiple grid lines.
- * all the grid lines should be in between the two end poins of the
- *trim edge.
- */
-void sampleLeftSingleTrimEdgeRegion(Real upperVert[2], Real lowerVert[2],
-				    gridBoundaryChain* gridChain,
-				    Int beginIndex,
-				    Int endIndex,
-				    primStream* pStream)
-{
-  Int i,j,k;
-
-  vertexArray vArray(endIndex-beginIndex+1);  
-  vArray.appendVertex(gridChain->get_vertex(beginIndex));
-
-  for(k=1, i=beginIndex+1; i<=endIndex; i++, k++)
-    {
-      vArray.appendVertex(gridChain->get_vertex(i));
-
-      /*output the fan of the grid points of the (i)th and (i-1)th grid line.
-       */
-      if(gridChain->getUlineIndex(i) < gridChain->getUlineIndex(i-1))
-	{
-	  pStream->begin();	  
-	  pStream->insert(gridChain->get_vertex(i-1));
-	  for(j=gridChain->getUlineIndex(i); j<= gridChain->getUlineIndex(i-1); j++)
-	    pStream->insert(gridChain->getGrid()->get_u_value(j), gridChain->get_v_value(i));
-	  pStream->end(PRIMITIVE_STREAM_FAN);
-	}
-      else if(gridChain->getUlineIndex(i) > gridChain->getUlineIndex(i-1))
-	{
-	  pStream->begin();
-	  pStream->insert(gridChain->get_vertex(i));
-	  for(j=gridChain->getUlineIndex(i); j>= gridChain->getUlineIndex(i-1); j--)
-	    pStream->insert(gridChain->getGrid()->get_u_value(j), gridChain->get_v_value(i-1));
-	  pStream->end(PRIMITIVE_STREAM_FAN);
-	}
-      /*otherwisem, the two are equal, so there is no fan to outout*/	  
-    }
-  
-  monoTriangulation2(upperVert, lowerVert, &vArray, 0, endIndex-beginIndex, 
-		     0, /*decreasing chain*/
-		     pStream);
-}
-  
-/*return i, such that from begin to i-1 the chain is strictly u-monotone. 
- */				 
-Int findIncreaseChainFromBegin(vertexArray* chain, Int begin ,Int end)
-{
-  Int i=begin;
-  Real prevU = chain->getVertex(i)[0];
-  Real thisU;
-  for(i=begin+1; i<=end; i++){
-    thisU = chain->getVertex(i)[0];
-
-    if(prevU < thisU){
-      prevU = thisU;
-    }
-    else
-      break;
-  }
-  return i;
-}
-  
-/*check whether there is a vertex whose v value is strictly 
- *inbetween vup vbelow
- *if no middle exists return -1, else return the idnex.
- */
-Int checkMiddle(vertexArray* chain, Int begin, Int end, 
-		Real vup, Real vbelow)
-{
-  Int i;
-  for(i=begin; i<=end; i++)
-    {
-      if(chain->getVertex(i)[1] < vup && chain->getVertex(i)[1]>vbelow)
-	return i;
-    }
-  return -1;
-}
-  
-/*the degenerat case of sampleLeftOneGridStep*/
-void sampleLeftOneGridStepNoMiddle(vertexArray* leftChain,
-				   Int beginLeftIndex,
-				   Int endLeftIndex,
-				   gridBoundaryChain* leftGridChain,
-				   Int leftGridChainStartIndex,
-				   primStream* pStream)
-{
-  /*since there is no middle, there is at most one point which is on the 
-   *second grid line, there could be multiple points on the first (top)
-   *grid line.
-   */
-
-  leftGridChain->leftEndFan(leftGridChainStartIndex+1, pStream);
-
-  monoTriangulation2(leftGridChain->get_vertex(leftGridChainStartIndex),
-		     leftGridChain->get_vertex(leftGridChainStartIndex+1),
-		     leftChain,
-		     beginLeftIndex,
-		     endLeftIndex,
-		     1, //is increase chain.
-		     pStream);
-}
-
-
-
-/*sampling the left area in between two grid lines.
- */
-void sampleLeftOneGridStep(vertexArray* leftChain,
-		  Int beginLeftIndex,
-		  Int endLeftIndex,
-		  gridBoundaryChain* leftGridChain,
-		  Int leftGridChainStartIndex,
-		  primStream* pStream
-		  )
-{
-  if(checkMiddle(leftChain, beginLeftIndex, endLeftIndex, 
-		 leftGridChain->get_v_value(leftGridChainStartIndex),
-		 leftGridChain->get_v_value(leftGridChainStartIndex+1))<0)
-    
-    {
-      
-      sampleLeftOneGridStepNoMiddle(leftChain, beginLeftIndex, endLeftIndex, leftGridChain, leftGridChainStartIndex, pStream);
-      return;
-    }
-  
-  //copy into a polygon
-  {
-    directedLine* poly = NULL;
-    sampledLine* sline;
-    directedLine* dline;
-    gridWrap* grid = leftGridChain->getGrid();
-    Real vert1[2];
-    Real vert2[2];
-    Int i;
-    
-    Int innerInd = leftGridChain->getInnerIndex(leftGridChainStartIndex+1);
-    Int upperInd = leftGridChain->getUlineIndex(leftGridChainStartIndex);
-    Int lowerInd = leftGridChain->getUlineIndex(leftGridChainStartIndex+1);
-    Real upperV = leftGridChain->get_v_value(leftGridChainStartIndex);
-    Real lowerV = leftGridChain->get_v_value(leftGridChainStartIndex+1);
-
-    //the upper gridline
-    vert1[1] = vert2[1] = upperV;
-    for(i=innerInd;	i>upperInd;	i--)
-      {
-	vert1[0]=grid->get_u_value(i);
-	vert2[0]=grid->get_u_value(i-1);
-	sline = new sampledLine(vert1, vert2);
-	dline = new directedLine(INCREASING, sline);
-	if(poly == NULL)
-	  poly = dline;
-	else
-	  poly->insert(dline);
-      }
-
-    //the edge connecting upper grid with left chain
-    vert1[0] = grid->get_u_value(upperInd);
-    vert1[1] = upperV;
-    sline = new sampledLine(vert1, leftChain->getVertex(beginLeftIndex));
-    dline = new directedLine(INCREASING, sline);
-    if(poly == NULL)
-      poly = dline;
-    else
-      poly->insert(dline);    
- 
-    //the left chain
-    for(i=beginLeftIndex; i<endLeftIndex; i++)
-      {
-	sline = new sampledLine(leftChain->getVertex(i), leftChain->getVertex(i+1));
-	dline = new directedLine(INCREASING, sline);
-	poly->insert(dline);
-      }
-
-    //the edge connecting left chain with lower gridline
-    vert2[0] = grid->get_u_value(lowerInd);
-    vert2[1] = lowerV;
-    sline = new sampledLine(leftChain->getVertex(endLeftIndex), vert2);
-    dline = new directedLine(INCREASING, sline);
-    poly->insert(dline);
-
-    //the lower grid line
-    vert1[1] = vert2[1] = lowerV;
-    for(i=lowerInd; i<innerInd; i++)
-      {
-	vert1[0] = grid->get_u_value(i);
-	vert2[0] = grid->get_u_value(i+1);
-	sline = new sampledLine(vert1, vert2);
-	dline = new directedLine(INCREASING, sline);
-	poly->insert(dline);       
-      }
-
-    //the vertical grid line segement
-    vert1[0]=vert2[0] = grid->get_u_value(innerInd);
-    vert2[1]=upperV;
-    vert1[1]=lowerV;
-    sline=new sampledLine(vert1, vert2);
-    dline=new directedLine(INCREASING, sline);
-    poly->insert(dline);
-    monoTriangulationOpt(poly, pStream);
-    //cleanup
-    poly->deleteSinglePolygonWithSline();
-    return;
-  }
- 
-
-
- 
-
-  Int i;
-  if(1/*leftGridChain->getUlineIndex(leftGridChainStartIndex) >= 
-     leftGridChain->getUlineIndex(leftGridChainStartIndex+1)*/
-     ) /*the second grid line is beyond the first one to the left*/
-    {
-      /*find the maximal U-monotone chain 
-       * of endLeftIndex, endLeftIndex-1, ..., 
-       */
-      i=endLeftIndex;
-      Real prevU = leftChain->getVertex(i)[0];
-      for(i=endLeftIndex-1; i>=beginLeftIndex; i--){
-	Real thisU = leftChain->getVertex(i)[0];
-	if( prevU < thisU){
-	  prevU = thisU;
-	}
-	else 
-	  break;
-      }
-      /*from endLeftIndex to i+1 is strictly U- monotone */
-      /*if i+1==endLeftIndex and the vertex and leftchain is on the second gridline, then
-       *we should use 2 vertices on the leftchain. If we only use one (endLeftIndex), then we
-       *we would output degenerate triangles
-       */
-      if(i+1 == endLeftIndex && leftChain->getVertex(endLeftIndex)[1] == leftGridChain->get_v_value(1+leftGridChainStartIndex))
-	i--;
-
-      Int j = beginLeftIndex/*endLeftIndex*/+1;
-
-
-      if(leftGridChain->getInnerIndex(leftGridChainStartIndex+1) > leftGridChain->getUlineIndex(leftGridChainStartIndex))
-	{
-	  j = findIncreaseChainFromBegin(leftChain, beginLeftIndex, i+1/*endLeftIndex*/);
-
-	  Int temp = beginLeftIndex;
-	  /*now from begin to j-1 is strictly u-monotone*/
-	  /*if j-1 is on the first grid line, then we want to skip to the vertex which is strictly
-	   *below the grid line. This vertexmust exist since there is a 'corner turn' inbetween the two grid lines
-	   */
-	  if(j-1 == beginLeftIndex)
-	    {
-	      while(leftChain->getVertex(j-1)[1] == leftGridChain->get_v_value(leftGridChainStartIndex))
-		j++;	        
-
-	      Real vert[2];
-	      vert[0] = leftGridChain->get_u_value(leftGridChainStartIndex);
-	      vert[1] = leftGridChain->get_v_value(leftGridChainStartIndex);
-
-	      monoTriangulation2(
-				 vert/*leftChain->getVertex(beginLeftIndex)*/,
-				 leftChain->getVertex(j-1),
-				 leftChain,
-				 beginLeftIndex,
-				 j-2,
-				 1,
-				 pStream //increase chain
-				 );
-				 
-	      temp = j-1;
-	    }
-				 
-	  stripOfFanLeft(leftChain, j-1, temp/*beginLeftIndex*/, leftGridChain->getGrid(),
-			 leftGridChain->getVlineIndex(leftGridChainStartIndex),
-			 leftGridChain->getUlineIndex(leftGridChainStartIndex),
-			 leftGridChain->getInnerIndex(leftGridChainStartIndex+1),
-			 pStream,
-			 1 /*the grid line is above the trim line*/
-			 );
-	}
-      
-      stripOfFanLeft(leftChain, endLeftIndex, i+1, leftGridChain->getGrid(), 
-		     leftGridChain->getVlineIndex(leftGridChainStartIndex+1),
-		     leftGridChain->getUlineIndex(leftGridChainStartIndex+1),
-		     leftGridChain->getInnerIndex(leftGridChainStartIndex+1),
-		     pStream,
-		     0 /*the grid line is below the trim lines*/
-		     );
-      
-      /*monotone triangulate the remaining left chain togther with the
-       *two vertices on the two grid v-lines.
-       */
-      Real vert[2][2];
-      vert[0][0]=vert[1][0] = leftGridChain->getInner_u_value(leftGridChainStartIndex+1);
-      vert[0][1] = leftGridChain->get_v_value(leftGridChainStartIndex);      
-      vert[1][1] = leftGridChain->get_v_value(leftGridChainStartIndex+1);
-
-//      vertexArray right(vert, 2);
-
-      monoTriangulation2(
-			 &vert[0][0], /*top vertex */
-			 &vert[1][0], /*bottom vertex*/
-			 leftChain, 
-			 /*beginLeftIndex*/j-1,
-			 i+1,
-			 1, /*an increasing chain*/
-			 pStream);
-    }
-  else /*the second one is shorter than the first one to the left*/
-    {
-      /*find the maximal U-monotone chain of beginLeftIndex, beginLeftIndex+1,...,
-       */
-      i=beginLeftIndex;
-      Real prevU = leftChain->getVertex(i)[0];
-      for(i=beginLeftIndex+1; i<=endLeftIndex; i++){
-	Real thisU = leftChain->getVertex(i)[0];
-
-	if(prevU < thisU){
-	  prevU = thisU;
-	}
-	else
-	  break;
-      }
-      /*from beginLeftIndex to i-1 is strictly U-monotone*/
-
-
-      stripOfFanLeft(leftChain, i-1, beginLeftIndex, leftGridChain->getGrid(),
-			 leftGridChain->getVlineIndex(leftGridChainStartIndex),
-			 leftGridChain->getUlineIndex(leftGridChainStartIndex),
-			 leftGridChain->getUlineIndex(leftGridChainStartIndex+1),
-			 pStream,
-		         1 /*the grid line is above the trim lines*/
-			 );
-      /*monotone triangulate the remaining left chain together with the 
-       *two vertices on the two grid v-lines.
-       */
-      Real vert[2][2];
-      vert[0][0]=vert[1][0] = leftGridChain->get_u_value(leftGridChainStartIndex+1);
-      vert[0][1] = leftGridChain->get_v_value(leftGridChainStartIndex);      
-      vert[1][1] = leftGridChain->get_v_value(leftGridChainStartIndex+1);
-
-      vertexArray right(vert, 2);
-
-      monoTriangulation2(
-			 &vert[0][0], //top vertex 
-			 &vert[1][0], //bottom vertex
-			 leftChain, 
-			 i-1,
-			 endLeftIndex,
-			 1, /*an increase chain*/
-			 pStream);
-
-    }
-}
-  
-/*n_upper>=1
- *n_lower>=1
- */
-void triangulateXYMono(Int n_upper, Real upperVerts[][2],
-		       Int n_lower, Real lowerVerts[][2],
-		       primStream* pStream)
-{
-  Int i,j,k,l;
-  Real* leftMostV;
-
-  assert(n_upper>=1 && n_lower>=1);
-  if(upperVerts[0][0] <= lowerVerts[0][0])
-    {
-      i=1;
-      j=0;
-      leftMostV = upperVerts[0];
-    }
-  else
-    {
-      i=0;
-      j=1;
-      leftMostV = lowerVerts[0];
-    }
-  
-  while(1)
-    {
-      if(i >= n_upper) /*case1: no more in upper*/
-	{
-
-	  if(j<n_lower-1) /*at least two vertices in lower*/
-	    {
-	      pStream->begin();
-	      pStream->insert(leftMostV);
-	      while(j<n_lower){
-		pStream->insert(lowerVerts[j]);
-		j++;
-	      }
-	      pStream->end(PRIMITIVE_STREAM_FAN);
-	    }
-
-	  break;	
-	}
-      else if(j>= n_lower) /*case2: no more in lower*/
-	{
-
-	  if(i<n_upper-1) /*at least two vertices in upper*/
-	    {
-	      pStream->begin();
-	      pStream->insert(leftMostV);
-
-	      for(k=n_upper-1; k>=i; k--)
-		pStream->insert(upperVerts[k]);
-
-	      pStream->end(PRIMITIVE_STREAM_FAN);
-	    }
-
-	  break;
-	}
-      else /* case3: neither is empty, plus the leftMostV, there is at least one triangle to output*/
-	{
-
-	  if(upperVerts[i][0] <= lowerVerts[j][0])
-	    {
-	      pStream->begin();
-	      pStream->insert(lowerVerts[j]); /*the origin of this fan*/
-
-	      /*find the last k>=i such that 
-	       *upperverts[k][0] <= lowerverts[j][0]
-	       */
-	      k=i;
-	      while(k<n_upper)
-		{
-		  if(upperVerts[k][0] > lowerVerts[j][0])
-		    break;
-		  k++;
-		}
-	      k--;
-	      for(l=k; l>=i; l--)/*the reverse is for two-face lighting*/
-		{
-		  pStream->insert(upperVerts[l]);
-		}
-	      pStream->insert(leftMostV);
-
-	      pStream->end(PRIMITIVE_STREAM_FAN);
-	      //update i for next loop
-	      i = k+1;
-	      leftMostV = upperVerts[k];
-
-	    }
-	  else /*upperVerts[i][0] > lowerVerts[j][0]*/
-	    {
-	      pStream->begin();
-	      pStream->insert(upperVerts[i]);/*the origion of this fan*/
-	      pStream->insert(leftMostV);
-	      /*find the last k>=j such that
-	       *lowerverts[k][0] < upperverts[i][0]*/
-	      k=j;
-	      while(k< n_lower)
-		{
-		  if(lowerVerts[k][0] >= upperVerts[i][0])
-		    break;
-		  pStream->insert(lowerVerts[k]);
-		  k++;
-		}
-	      pStream->end(PRIMITIVE_STREAM_FAN);
-	      j=k;
-	      leftMostV = lowerVerts[j-1];
-	    }	  
-	}
-    }
-}
-		       
-
-void stripOfFanLeft(vertexArray* leftChain, 
-		    Int largeIndex,
-		    Int smallIndex,
-		    gridWrap* grid,
-		    Int vlineIndex,
-		    Int ulineSmallIndex,
-		    Int ulineLargeIndex,
-		    primStream* pStream,
-		    Int gridLineUp /*1 if the grid line is above the trim lines*/
-		     )
-{
-  assert(largeIndex >= smallIndex);
-
-  Real grid_v_value;
-  grid_v_value = grid->get_v_value(vlineIndex);
-
-  Real2* trimVerts=(Real2*) malloc(sizeof(Real2)* (largeIndex-smallIndex+1));
-  assert(trimVerts);
-
-
-  Real2* gridVerts=(Real2*) malloc(sizeof(Real2)* (ulineLargeIndex-ulineSmallIndex+1));
-  assert(gridVerts);
-
-  Int k,i;
-  if(gridLineUp) /*trim line is below grid line, so trim vertices are going right when index increases*/
-    for(k=0, i=smallIndex; i<=largeIndex; i++, k++)
-      {
-      trimVerts[k][0] = leftChain->getVertex(i)[0];
-      trimVerts[k][1] = leftChain->getVertex(i)[1];
-    }
-  else
-    for(k=0, i=largeIndex; i>=smallIndex; i--, k++)
-      {
-	trimVerts[k][0] = leftChain->getVertex(i)[0];
-	trimVerts[k][1] = leftChain->getVertex(i)[1];
-      }
-
-  for(k=0, i=ulineSmallIndex; i<= ulineLargeIndex; i++, k++)
-    {
-      gridVerts[k][0] = grid->get_u_value(i);
-      gridVerts[k][1] = grid_v_value;
-    }
-
-  if(gridLineUp)
-    triangulateXYMono(
-		      ulineLargeIndex-ulineSmallIndex+1, gridVerts,
-		      largeIndex-smallIndex+1, trimVerts,
-		      pStream);
-  else
-    triangulateXYMono(largeIndex-smallIndex+1, trimVerts,
-		      ulineLargeIndex-ulineSmallIndex+1, gridVerts,
-		      pStream);
-  free(trimVerts);
-  free(gridVerts);
-}
-
-  
-
-
-