src/parsec/disk-image/parsec/parsec-benchmark/pkgs/libs/mesa/src/src/glu/sgi/libnurbs/internals/monoTriangulationBackend.cc - public/gem5-resources - Git at Google

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

 #include "monoTriangulation.h"
 #include "polyUtil.h"
 #include "backend.h"
 #include "arc.h"

 void reflexChain::outputFan(Real v[2], Backend* backend)
 {
   Int i;
   /*
   TrimVertex trimVert;
   */
   backend->bgntfan();

   /*
   trimVert.param[0]=v[0];
   trimVert.param[1]=v[1];
   backend->tmeshvert(&trimVert);
   */
   backend->tmeshvert(v[0], v[1]);

   if(isIncreasing) {
     for(i=0; i<index_queue; i++)
       {
 	/*
 	trimVert.param[0]=queue[i][0];
 	trimVert.param[1]=queue[i][1];
 	backend->tmeshvert(&trimVert);
 	*/
 	backend->tmeshvert(queue[i][0], queue[i][1]);
       }
   }
   else {
     for(i=index_queue-1; i>=0; i--)
       {
 	/*
 	trimVert.param[0]=queue[i][0];
 	trimVert.param[1]=queue[i][1];
 	backend->tmeshvert(&trimVert);
 	*/
 	backend->tmeshvert(queue[i][0], queue[i][1]);
       }
   }
   backend->endtfan();
 }

 void reflexChain::processNewVertex(Real v[2], Backend* backend)
 {
   Int i,j,k;
   Int isReflex;
   /*TrimVertex trimVert;*/
   /*if there are at most one vertex in the queue, then simply insert
    */
   if(index_queue <=1){
     insert(v);
     return;
   }

   /*there are at least two vertices in the queue*/
   j=index_queue-1;

   for(i=j; i>=1; i--) {
     if(isIncreasing) {
       isReflex = (area(queue[i-1], queue[i], v) <= 0.0);
     }
     else /*decreasing*/{
       isReflex = (area(v, queue[i], queue[i-1]) <= 0.0);
     }
     if(isReflex) {
       break;
     }
   }

   /*
    *if i<j then vertices: i+1--j are convex
    * output triangle fan:
    *  v, and queue[i], i+1, ..., j
    */
   if(i<j)
     {
       backend->bgntfan();
       /*
       trimVert.param[0]=v[0];
       trimVert.param[1]=v[1];
       backend->tmeshvert(& trimVert);
       */
       backend->tmeshvert(v[0], v[1]);

       if(isIncreasing) {
 	for(k=i; k<=j; k++)
 	  {
 	    /*
 	    trimVert.param[0]=queue[k][0];
 	    trimVert.param[1]=queue[k][1];
 	    backend->tmeshvert(& trimVert);
 	    */
 	    backend->tmeshvert(queue[k][0], queue[k][1]);
 	  }
       }
       else {
 	for(k=j; k>=i; k--)
 	  {
 	    /*
 	    trimVert.param[0]=queue[k][0];
 	    trimVert.param[1]=queue[k][1];
 	    backend->tmeshvert(& trimVert);
 	    */
 	    backend->tmeshvert(queue[k][0], queue[k][1]);
 	  }
       }

       backend->endtfan();
     }

   /*delete vertices i+1--j from the queue*/
   index_queue = i+1;
   /*finally insert v at the end of the queue*/
   insert(v);

 }


 void monoTriangulationRec(Real* topVertex, Real* botVertex,
 			  vertexArray* inc_chain, Int inc_current,
 			  vertexArray* dec_chain, Int dec_current,
 			  Backend* backend)
 {
   assert( inc_chain != NULL && dec_chain != NULL);
   assert( ! (inc_current>=inc_chain->getNumElements() &&
 	     dec_current>=dec_chain->getNumElements()));
   Int inc_nVertices;
   Int dec_nVertices;
   Real** inc_array ;
   Real** dec_array ;
   Int i;
   assert( ! ( (inc_chain==NULL) && (dec_chain==NULL)));

   if(inc_current>=inc_chain->getNumElements()) /*no more vertices on inc_chain*/
     {

       dec_array = dec_chain->getArray();
       dec_nVertices = dec_chain->getNumElements();
       reflexChain rChain(20,0);
       /*put the top vertex into the reflex chain*/
       rChain.processNewVertex(topVertex, backend);
       /*process all the vertices on the dec_chain*/
       for(i=dec_current; i<dec_nVertices; i++){
 	rChain.processNewVertex(dec_array[i], backend);
       }
       /*process the bottom vertex*/
       rChain.processNewVertex(botVertex, backend);

     }
   else if(dec_current>= dec_chain->getNumElements()) /*no more vertices on dec_chain*/
     {
       inc_array = inc_chain->getArray();
       inc_nVertices= inc_chain->getNumElements();
       reflexChain rChain(20,1);
       /*put the top vertex into the reflex chain*/
       rChain.processNewVertex(topVertex, backend);
       /*process all the vertices on the inc_chain*/
       for(i=inc_current; i<inc_nVertices; i++){
 	rChain.processNewVertex(inc_array[i], backend);
       }
       /*process the bottom vertex*/
       rChain.processNewVertex(botVertex, backend);
     }
   else /*neither chain is empty*/
     {
       inc_array = inc_chain -> getArray();
       dec_array = dec_chain -> getArray();
       inc_nVertices= inc_chain->getNumElements();
       dec_nVertices= dec_chain->getNumElements();
       /*if top of inc_chain is 'lower' than top of dec_chain, process all the
        *vertices on the dec_chain which are higher than top of inc_chain
        */
       if(compV2InY(inc_array[inc_current], dec_array[dec_current]) <= 0)
 	{

 	  reflexChain rChain(20, 0);
 	  rChain.processNewVertex(topVertex, backend);
 	  for(i=dec_current; i<dec_nVertices; i++)
 	    {
 	      if(compV2InY(inc_array[inc_current], dec_array[i]) <= 0)
 		rChain.processNewVertex(dec_array[i], backend);
 	      else
 		break;
 	    }
 	  rChain.outputFan(inc_array[inc_current], backend);
 	  monoTriangulationRec(dec_array[i-1], botVertex,
 			       inc_chain, inc_current,
 			       dec_chain, i,
 			       backend);
 	}
       else /*compV2InY(inc_array[inc_current], dec_array[dec_current]) > 0*/
 	{

 	  reflexChain rChain(20, 1);
 	  rChain.processNewVertex(topVertex, backend);
 	  for(i=inc_current; i<inc_nVertices; i++)
 	    {
 	      if(compV2InY(inc_array[i], dec_array[dec_current]) >0)
 		rChain.processNewVertex(inc_array[i], backend);
 	      else
 		break;
 	    }
 	  rChain.outputFan(dec_array[dec_current], backend);
 	  monoTriangulationRec(inc_array[i-1], botVertex,
 			       inc_chain, i,
 			       dec_chain, dec_current,
 			       backend);
 	}
     }/*end case neither is empty*/
 }


 void monoTriangulationFunBackend(Arc_ptr loop, Int (*compFun)(Real*, Real*), Backend* backend)
 {
   Int i;
   /*find the top vertex, bottom vertex, inccreasing chain, and decreasing chain,
    *then call monoTriangulationRec
    */
   Arc_ptr tempV;
   Arc_ptr topV;
   Arc_ptr botV;
   topV = botV = loop;
   for(tempV = loop->next; tempV != loop; tempV = tempV->next)
     {
       if(compFun(topV->tail(), tempV->tail())<0) {
 	topV = tempV;
       }
       if(compFun(botV->tail(), tempV->tail())>0) {
 	botV = tempV;
       }
     }

   /*creat increase and decrease chains*/
   vertexArray inc_chain(20); /*this is a dynamic array*/
   for(i=1; i<=topV->pwlArc->npts-2; i++) { /*the first vertex is the top vertex which doesn't belong to inc_chain*/
     inc_chain.appendVertex(topV->pwlArc->pts[i].param);
   }
   for(tempV = topV->next; tempV != botV; tempV = tempV->next)
     {
       for(i=0; i<=tempV->pwlArc->npts-2; i++){
 	inc_chain.appendVertex(tempV->pwlArc->pts[i].param);
       }
     }

   vertexArray dec_chain(20);
   for(tempV = topV->prev; tempV != botV; tempV = tempV->prev)
     {
       for(i=tempV->pwlArc->npts-2; i>=0; i--){
 	dec_chain.appendVertex(tempV->pwlArc->pts[i].param);
       }
     }
   for(i=botV->pwlArc->npts-2; i>=1; i--){
     dec_chain.appendVertex(tempV->pwlArc->pts[i].param);
   }

   monoTriangulationRecFunBackend(topV->tail(), botV->tail(), &inc_chain, 0, &dec_chain, 0, compFun, backend);

 }

 /*if compFun == compV2InY, top to bottom: V-monotone
  *if compFun == compV2InX, right to left: U-monotone
  */
 void monoTriangulationRecFunBackend(Real* topVertex, Real* botVertex,
 			  vertexArray* inc_chain, Int inc_current,
 			  vertexArray* dec_chain, Int dec_current,
 			  Int  (*compFun)(Real*, Real*),
 			  Backend* backend)
 {
   assert( inc_chain != NULL && dec_chain != NULL);
   assert( ! (inc_current>=inc_chain->getNumElements() &&
 	     dec_current>=dec_chain->getNumElements()));
   Int inc_nVertices;
   Int dec_nVertices;
   Real** inc_array ;
   Real** dec_array ;
   Int i;
   assert( ! ( (inc_chain==NULL) && (dec_chain==NULL)));

   if(inc_current>=inc_chain->getNumElements()) /*no more vertices on inc_chain*/
     {

       dec_array = dec_chain->getArray();
       dec_nVertices = dec_chain->getNumElements();
       reflexChain rChain(20,0);
       /*put the top vertex into the reflex chain*/
       rChain.processNewVertex(topVertex, backend);
       /*process all the vertices on the dec_chain*/
       for(i=dec_current; i<dec_nVertices; i++){
 	rChain.processNewVertex(dec_array[i], backend);
       }
       /*process the bottom vertex*/
       rChain.processNewVertex(botVertex, backend);

     }
   else if(dec_current>= dec_chain->getNumElements()) /*no more vertices on dec_chain*/
     {
       inc_array = inc_chain->getArray();
       inc_nVertices= inc_chain->getNumElements();
       reflexChain rChain(20,1);
       /*put the top vertex into the reflex chain*/
       rChain.processNewVertex(topVertex, backend);
       /*process all the vertices on the inc_chain*/
       for(i=inc_current; i<inc_nVertices; i++){
 	rChain.processNewVertex(inc_array[i], backend);
       }
       /*process the bottom vertex*/
       rChain.processNewVertex(botVertex, backend);
     }
   else /*neither chain is empty*/
     {
       inc_array = inc_chain -> getArray();
       dec_array = dec_chain -> getArray();
       inc_nVertices= inc_chain->getNumElements();
       dec_nVertices= dec_chain->getNumElements();
       /*if top of inc_chain is 'lower' than top of dec_chain, process all the
        *vertices on the dec_chain which are higher than top of inc_chain
        */
       if(compFun(inc_array[inc_current], dec_array[dec_current]) <= 0)
 	{

 	  reflexChain rChain(20, 0);
 	  rChain.processNewVertex(topVertex, backend);
 	  for(i=dec_current; i<dec_nVertices; i++)
 	    {
 	      if(compFun(inc_array[inc_current], dec_array[i]) <= 0)
 		rChain.processNewVertex(dec_array[i], backend);
 	      else
 		break;
 	    }
 	  rChain.outputFan(inc_array[inc_current], backend);
 	  monoTriangulationRecFunBackend(dec_array[i-1], botVertex,
 			       inc_chain, inc_current,
 			       dec_chain, i,
 			       compFun,
 			       backend);
 	}
       else /*compFun(inc_array[inc_current], dec_array[dec_current]) > 0*/
 	{

 	  reflexChain rChain(20, 1);
 	  rChain.processNewVertex(topVertex, backend);
 	  for(i=inc_current; i<inc_nVertices; i++)
 	    {
 	      if(compFun(inc_array[i], dec_array[dec_current]) >0)
 		rChain.processNewVertex(inc_array[i], backend);
 	      else
 		break;
 	    }
 	  rChain.outputFan(dec_array[dec_current], backend);
 	  monoTriangulationRecFunBackend(inc_array[i-1], botVertex,
 			       inc_chain, i,
 			       dec_chain, dec_current,
 			       compFun,
 			       backend);
 	}
     }/*end case neither is empty*/
 }
	/*
	** License Applicability. Except to the extent portions of this file are
	** made subject to an alternative license as permitted in the SGI Free
	** Software License B, Version 1.1 (the "License"), the contents of this
	** file are subject only to the provisions of the License. You may not use
	** this file except in compliance with the License. You may obtain a copy
	** of the License at Silicon Graphics, Inc., attn: Legal Services, 1600
	** Amphitheatre Parkway, Mountain View, CA 94043-1351, or at:
	**
	** http://oss.sgi.com/projects/FreeB
	**
	** Note that, as provided in the License, the Software is distributed on an
	** "AS IS" basis, with ALL EXPRESS AND IMPLIED WARRANTIES AND CONDITIONS
	** DISCLAIMED, INCLUDING, WITHOUT LIMITATION, ANY IMPLIED WARRANTIES AND
	** CONDITIONS OF MERCHANTABILITY, SATISFACTORY QUALITY, FITNESS FOR A
	** PARTICULAR PURPOSE, AND NON-INFRINGEMENT.
	**
	** Original Code. The Original Code is: OpenGL Sample Implementation,
	** Version 1.2.1, released January 26, 2000, developed by Silicon Graphics,
	** Inc. The Original Code is Copyright (c) 1991-2000 Silicon Graphics, Inc.
	** Copyright in any portions created by third parties is as indicated
	** elsewhere herein. All Rights Reserved.
	**
	** Additional Notice Provisions: The application programming interfaces
	** established by SGI in conjunction with the Original Code are The
	** OpenGL(R) Graphics System: A Specification (Version 1.2.1), released
	** April 1, 1999; The OpenGL(R) Graphics System Utility Library (Version
	** 1.3), released November 4, 1998; and OpenGL(R) Graphics with the X
	** Window System(R) (Version 1.3), released October 19, 1998. This software
	** was created using the OpenGL(R) version 1.2.1 Sample Implementation
	** published by SGI, but has not been independently verified as being
	** compliant with the OpenGL(R) version 1.2.1 Specification.
	**
	** $Date: 2012/03/29 17:22:18 $ $Revision: 1.1.1.1 $
	*/
	/*
	** $Header: /cvs/bao-parsec/pkgs/libs/mesa/src/src/glu/sgi/libnurbs/internals/monoTriangulationBackend.cc,v 1.1.1.1 2012/03/29 17:22:18 uid42307 Exp $
	*/

	#include "monoTriangulation.h"
	#include "polyUtil.h"
	#include "backend.h"
	#include "arc.h"

	void reflexChain::outputFan(Real v[2], Backend* backend)
	{
	Int i;
	/*
	TrimVertex trimVert;
	*/
	backend->bgntfan();

	/*
	trimVert.param[0]=v[0];
	trimVert.param[1]=v[1];
	backend->tmeshvert(&trimVert);
	*/
	backend->tmeshvert(v[0], v[1]);

	if(isIncreasing) {
	for(i=0; i<index_queue; i++)
	{
	/*
	trimVert.param[0]=queue[i][0];
	trimVert.param[1]=queue[i][1];
	backend->tmeshvert(&trimVert);
	*/
	backend->tmeshvert(queue[i][0], queue[i][1]);
	}
	}
	else {
	for(i=index_queue-1; i>=0; i--)
	{
	/*
	trimVert.param[0]=queue[i][0];
	trimVert.param[1]=queue[i][1];
	backend->tmeshvert(&trimVert);
	*/
	backend->tmeshvert(queue[i][0], queue[i][1]);
	}
	}
	backend->endtfan();
	}

	void reflexChain::processNewVertex(Real v[2], Backend* backend)
	{
	Int i,j,k;
	Int isReflex;
	/TrimVertex trimVert;/
	/*if there are at most one vertex in the queue, then simply insert
	*/
	if(index_queue <=1){
	insert(v);
	return;
	}

	/there are at least two vertices in the queue/
	j=index_queue-1;

	for(i=j; i>=1; i--) {
	if(isIncreasing) {
	isReflex = (area(queue[i-1], queue[i], v) <= 0.0);
	}
	else /decreasing/{
	isReflex = (area(v, queue[i], queue[i-1]) <= 0.0);
	}
	if(isReflex) {
	break;
	}
	}

	/*
	*if i<j then vertices: i+1--j are convex
	* output triangle fan:
	* v, and queue[i], i+1, ..., j
	*/
	if(i<j)
	{
	backend->bgntfan();
	/*
	trimVert.param[0]=v[0];
	trimVert.param[1]=v[1];
	backend->tmeshvert(& trimVert);
	*/
	backend->tmeshvert(v[0], v[1]);

	if(isIncreasing) {
	for(k=i; k<=j; k++)
	{
	/*
	trimVert.param[0]=queue[k][0];
	trimVert.param[1]=queue[k][1];
	backend->tmeshvert(& trimVert);
	*/
	backend->tmeshvert(queue[k][0], queue[k][1]);
	}
	}
	else {
	for(k=j; k>=i; k--)
	{
	/*
	trimVert.param[0]=queue[k][0];
	trimVert.param[1]=queue[k][1];
	backend->tmeshvert(& trimVert);
	*/
	backend->tmeshvert(queue[k][0], queue[k][1]);
	}
	}

	backend->endtfan();
	}

	/delete vertices i+1--j from the queue/
	index_queue = i+1;
	/finally insert v at the end of the queue/
	insert(v);

	}


	void monoTriangulationRec(Real* topVertex, Real* botVertex,
	vertexArray* inc_chain, Int inc_current,
	vertexArray* dec_chain, Int dec_current,
	Backend* backend)
	{
	assert( inc_chain != NULL && dec_chain != NULL);
	assert( ! (inc_current>=inc_chain->getNumElements() &&
	dec_current>=dec_chain->getNumElements()));
	Int inc_nVertices;
	Int dec_nVertices;
	Real** inc_array ;
	Real** dec_array ;
	Int i;
	assert( ! ( (inc_chain==NULL) && (dec_chain==NULL)));

	if(inc_current>=inc_chain->getNumElements()) /no more vertices on inc_chain/
	{

	dec_array = dec_chain->getArray();
	dec_nVertices = dec_chain->getNumElements();
	reflexChain rChain(20,0);
	/put the top vertex into the reflex chain/
	rChain.processNewVertex(topVertex, backend);
	/process all the vertices on the dec_chain/
	for(i=dec_current; i<dec_nVertices; i++){
	rChain.processNewVertex(dec_array[i], backend);
	}
	/process the bottom vertex/
	rChain.processNewVertex(botVertex, backend);

	}
	else if(dec_current>= dec_chain->getNumElements()) /no more vertices on dec_chain/
	{
	inc_array = inc_chain->getArray();
	inc_nVertices= inc_chain->getNumElements();
	reflexChain rChain(20,1);
	/put the top vertex into the reflex chain/
	rChain.processNewVertex(topVertex, backend);
	/process all the vertices on the inc_chain/
	for(i=inc_current; i<inc_nVertices; i++){
	rChain.processNewVertex(inc_array[i], backend);
	}
	/process the bottom vertex/
	rChain.processNewVertex(botVertex, backend);
	}
	else /neither chain is empty/
	{
	inc_array = inc_chain -> getArray();
	dec_array = dec_chain -> getArray();
	inc_nVertices= inc_chain->getNumElements();
	dec_nVertices= dec_chain->getNumElements();
	/*if top of inc_chain is 'lower' than top of dec_chain, process all the
	*vertices on the dec_chain which are higher than top of inc_chain
	*/
	if(compV2InY(inc_array[inc_current], dec_array[dec_current]) <= 0)
	{

	reflexChain rChain(20, 0);
	rChain.processNewVertex(topVertex, backend);
	for(i=dec_current; i<dec_nVertices; i++)
	{
	if(compV2InY(inc_array[inc_current], dec_array[i]) <= 0)
	rChain.processNewVertex(dec_array[i], backend);
	else
	break;
	}
	rChain.outputFan(inc_array[inc_current], backend);
	monoTriangulationRec(dec_array[i-1], botVertex,
	inc_chain, inc_current,
	dec_chain, i,
	backend);
	}
	else /compV2InY(inc_array[inc_current], dec_array[dec_current]) > 0/
	{

	reflexChain rChain(20, 1);
	rChain.processNewVertex(topVertex, backend);
	for(i=inc_current; i<inc_nVertices; i++)
	{
	if(compV2InY(inc_array[i], dec_array[dec_current]) >0)
	rChain.processNewVertex(inc_array[i], backend);
	else
	break;
	}
	rChain.outputFan(dec_array[dec_current], backend);
	monoTriangulationRec(inc_array[i-1], botVertex,
	inc_chain, i,
	dec_chain, dec_current,
	backend);
	}
	}/end case neither is empty/
	}


	void monoTriangulationFunBackend(Arc_ptr loop, Int (compFun)(Real, Real), Backend backend)
	{
	Int i;
	/*find the top vertex, bottom vertex, inccreasing chain, and decreasing chain,
	*then call monoTriangulationRec
	*/
	Arc_ptr tempV;
	Arc_ptr topV;
	Arc_ptr botV;
	topV = botV = loop;
	for(tempV = loop->next; tempV != loop; tempV = tempV->next)
	{
	if(compFun(topV->tail(), tempV->tail())<0) {
	topV = tempV;
	}
	if(compFun(botV->tail(), tempV->tail())>0) {
	botV = tempV;
	}
	}

	/creat increase and decrease chains/
	vertexArray inc_chain(20); /this is a dynamic array/
	for(i=1; i<=topV->pwlArc->npts-2; i++) { /the first vertex is the top vertex which doesn't belong to inc_chain/
	inc_chain.appendVertex(topV->pwlArc->pts[i].param);
	}
	for(tempV = topV->next; tempV != botV; tempV = tempV->next)
	{
	for(i=0; i<=tempV->pwlArc->npts-2; i++){
	inc_chain.appendVertex(tempV->pwlArc->pts[i].param);
	}
	}

	vertexArray dec_chain(20);
	for(tempV = topV->prev; tempV != botV; tempV = tempV->prev)
	{
	for(i=tempV->pwlArc->npts-2; i>=0; i--){
	dec_chain.appendVertex(tempV->pwlArc->pts[i].param);
	}
	}
	for(i=botV->pwlArc->npts-2; i>=1; i--){
	dec_chain.appendVertex(tempV->pwlArc->pts[i].param);
	}

	monoTriangulationRecFunBackend(topV->tail(), botV->tail(), &inc_chain, 0, &dec_chain, 0, compFun, backend);

	}

	/*if compFun == compV2InY, top to bottom: V-monotone
	*if compFun == compV2InX, right to left: U-monotone
	*/
	void monoTriangulationRecFunBackend(Real* topVertex, Real* botVertex,
	vertexArray* inc_chain, Int inc_current,
	vertexArray* dec_chain, Int dec_current,
	Int (compFun)(Real, Real*),
	Backend* backend)
	{
	assert( inc_chain != NULL && dec_chain != NULL);
	assert( ! (inc_current>=inc_chain->getNumElements() &&
	dec_current>=dec_chain->getNumElements()));
	Int inc_nVertices;
	Int dec_nVertices;
	Real** inc_array ;
	Real** dec_array ;
	Int i;
	assert( ! ( (inc_chain==NULL) && (dec_chain==NULL)));

	if(inc_current>=inc_chain->getNumElements()) /no more vertices on inc_chain/
	{

	dec_array = dec_chain->getArray();
	dec_nVertices = dec_chain->getNumElements();
	reflexChain rChain(20,0);
	/put the top vertex into the reflex chain/
	rChain.processNewVertex(topVertex, backend);
	/process all the vertices on the dec_chain/
	for(i=dec_current; i<dec_nVertices; i++){
	rChain.processNewVertex(dec_array[i], backend);
	}
	/process the bottom vertex/
	rChain.processNewVertex(botVertex, backend);

	}
	else if(dec_current>= dec_chain->getNumElements()) /no more vertices on dec_chain/
	{
	inc_array = inc_chain->getArray();
	inc_nVertices= inc_chain->getNumElements();
	reflexChain rChain(20,1);
	/put the top vertex into the reflex chain/
	rChain.processNewVertex(topVertex, backend);
	/process all the vertices on the inc_chain/
	for(i=inc_current; i<inc_nVertices; i++){
	rChain.processNewVertex(inc_array[i], backend);
	}
	/process the bottom vertex/
	rChain.processNewVertex(botVertex, backend);
	}
	else /neither chain is empty/
	{
	inc_array = inc_chain -> getArray();
	dec_array = dec_chain -> getArray();
	inc_nVertices= inc_chain->getNumElements();
	dec_nVertices= dec_chain->getNumElements();
	/*if top of inc_chain is 'lower' than top of dec_chain, process all the
	*vertices on the dec_chain which are higher than top of inc_chain
	*/
	if(compFun(inc_array[inc_current], dec_array[dec_current]) <= 0)
	{

	reflexChain rChain(20, 0);
	rChain.processNewVertex(topVertex, backend);
	for(i=dec_current; i<dec_nVertices; i++)
	{
	if(compFun(inc_array[inc_current], dec_array[i]) <= 0)
	rChain.processNewVertex(dec_array[i], backend);
	else
	break;
	}
	rChain.outputFan(inc_array[inc_current], backend);
	monoTriangulationRecFunBackend(dec_array[i-1], botVertex,
	inc_chain, inc_current,
	dec_chain, i,
	compFun,
	backend);
	}
	else /compFun(inc_array[inc_current], dec_array[dec_current]) > 0/
	{

	reflexChain rChain(20, 1);
	rChain.processNewVertex(topVertex, backend);
	for(i=inc_current; i<inc_nVertices; i++)
	{
	if(compFun(inc_array[i], dec_array[dec_current]) >0)
	rChain.processNewVertex(inc_array[i], backend);
	else
	break;
	}
	rChain.outputFan(dec_array[dec_current], backend);
	monoTriangulationRecFunBackend(inc_array[i-1], botVertex,
	inc_chain, i,
	dec_chain, dec_current,
	compFun,
	backend);
	}
	}/end case neither is empty/
	}