monotriangulation.cc

Mesa is an open-source implementation of the OpenGL specification - a system for rendering interacti

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

#include <stdlib.h>
#include <stdio.h>
#include "gluos.h"
#include "glimports.h"
#include "zlassert.h"

#include "monoTriangulation.h"
#include "polyUtil.h" /*for area*/
#include "partitionX.h"
#include "monoPolyPart.h"



extern  directedLine*  polygonConvert(directedLine* polygon);

/*poly is NOT deleted
 */
void monoTriangulationOpt(directedLine* poly, primStream* pStream)
{
  Int n_cusps;
  Int n_edges = poly->numEdges();
  directedLine** cusps = (directedLine**) malloc(sizeof(directedLine*)*n_edges);
  assert(cusps);
  findInteriorCuspsX(poly, n_cusps, cusps);
  if(n_cusps ==0) //u monotine
    {
      monoTriangulationFun(poly, compV2InX, pStream);
    }
  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(poly, compV2InX, pStream);
	}
      else
	{
	  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();	  
	}
    }
  else
    {
      //we need a general partitionX funtion (supposed to be in partitionX.C,
      //not implemented yet. XXX
      monoTriangulationFun(poly, compV2InY, pStream);    
    }
  
  free(cusps);
}

void monoTriangulationRecOpt(Real* topVertex, Real* botVertex, 
			     vertexArray* left_chain, Int left_current,
			     vertexArray* right_chain, Int right_current,
			     primStream* pStream)
{
  Int i,j;
  Int n_left = left_chain->getNumElements();
  Int n_right = right_chain->getNumElements();
  if(left_current>= n_left-1 ||
     right_current>= n_right-1)
    {
      monoTriangulationRec(topVertex, botVertex, left_chain, left_current,
			   right_chain, right_current, pStream);
      return;
    }
  //now both left and right  have at least two vertices each.
  Real left_v = left_chain->getVertex(left_current)[1];
  Real right_v = right_chain->getVertex(right_current)[1];
 
  if(left_v <= right_v) //first left vertex is below right
    {
      //find the last vertex of right which is above or equal to left
      for(j=right_current; j<=n_right-1; j++)
	{
	  if(right_chain->getVertex(j)[1] < left_v)
	    break;
	}
      monoTriangulationRecGen(topVertex, left_chain->getVertex(left_current),
			      left_chain, left_current, left_current,
			      right_chain, right_current, j-1,
			      pStream);
      monoTriangulationRecOpt(right_chain->getVertex(j-1),
			      botVertex,
			      left_chain, left_current,
			      right_chain, j,
			      pStream);
    }
  else //first right vertex is strictly below left
    {
      //find the last vertex of left which is strictly above right
      for(i=left_current; i<=n_left-1; i++)
	{
	  if(left_chain->getVertex(i)[1] <= right_v)
	    break;
	}
      monoTriangulationRecGen(topVertex, right_chain->getVertex(right_current),
			      left_chain, left_current, i-1,
			      right_chain, right_current, right_current,
			      pStream);
      monoTriangulationRecOpt(left_chain->getVertex(i-1),
			      botVertex,
			      left_chain, i,
			      right_chain, right_current,
			      pStream);
    }
}


void monoTriangulationRecGenTBOpt(Real* topVertex, Real* botVertex, 
			  vertexArray* inc_chain, Int inc_current, Int inc_end,
			  vertexArray* dec_chain, Int dec_current, Int dec_end,
			  primStream* pStream)
{
  pStream->triangle(topVertex, inc_chain->getVertex(inc_current), dec_chain->getVertex(dec_current));
  
/*printf("**(%f,%f)\n", inc_chain->getArray()[0][0],inc_chain->getArray()[0][1]);*/
  triangulateXYMonoTB(inc_end-inc_current+1, inc_chain->getArray()+inc_current,  dec_end-dec_current+1,  dec_chain->getArray()+dec_current, pStream);

  pStream->triangle(botVertex, dec_chain->getVertex(dec_end), inc_chain->getVertex(inc_end));
}
  

/*n_left>=1
 *n_right>=1
 *the strip is going top to bottom. compared to the funtion
 * triangulateXYmono()
 */
void triangulateXYMonoTB(Int n_left, Real** leftVerts,
		       Int n_right, Real** rightVerts,
		       primStream* pStream)
{


  Int i,j,k,l;
  Real* topMostV;

  assert(n_left>=1 && n_right>=1);
  if(leftVerts[0][1] >= rightVerts[0][1])
    {
      i=1;
      j=0;
      topMostV = leftVerts[0];
    }
  else
    {
      i=0;
      j=1;
      topMostV = rightVerts[0];
    }
  
  while(1)
    {
      if(i >= n_left) /*case1: no more in left*/
	{

	  if(j<n_right-1) /*at least two vertices in right*/
	    {
	      pStream->begin();
	      pStream->insert(topMostV);
	      for(k=n_right-1; k>=j; k--)		
		pStream->insert(rightVerts[j]);

	      pStream->end(PRIMITIVE_STREAM_FAN);
	      
	    }

	  break;	
	}
      else if(j>= n_right) /*case2: no more in right*/
	{

	  if(i<n_left-1) /*at least two vertices in left*/
	    {
	      pStream->begin();
	      pStream->insert(topMostV);

	      for(k=i; k<n_left; k++)
		pStream->insert(leftVerts[k]);

	      pStream->end(PRIMITIVE_STREAM_FAN);	      
	    }

	  break;
	}
      else /* case3: neither is empty, plus the topMostV, there is at least one triangle to output*/
	{

	  if(leftVerts[i][1] >=  rightVerts[j][1])
	    {
	      pStream->begin();
	      pStream->insert(rightVerts[j]); /*the origin of this fan*/

	      pStream->insert(topMostV);

	      /*find the last k>=i such that 
	       *leftverts[k][1] >= rightverts[j][1]
	       */
	      k=i;
	      while(k<n_left)
		{
		  if(leftVerts[k][1] < rightVerts[j][1])
		    break;
		  k++;
		}
	      k--;
	      for(l=i; l<=k; l++)
		{
		  pStream->insert(leftVerts[l]);
		}

	      pStream->end(PRIMITIVE_STREAM_FAN);
	      //update i for next loop
	      i = k+1;
	      topMostV = leftVerts[k];

	    }
	  else /*leftVerts[i][1] < rightVerts[j][1]*/
	    {
	      pStream->begin();
	      pStream->insert(leftVerts[i]);/*the origion of this fan*/

	      /*find the last k>=j such that
	       *rightverts[k][1] > leftverts[i][1]*/
	      k=j;
	      while(k< n_right)
		{
		  if(rightVerts[k][1] <= leftVerts[i][1])
		    break;
		  k++;
		}
	      k--;

	      for(l=k; l>= j; l--)
		pStream->insert(rightVerts[l]);

	      pStream->insert(topMostV);
	      pStream->end(PRIMITIVE_STREAM_FAN);
	      j=k+1;
	      topMostV = rightVerts[j-1];
	    }	  
	}
    }
}

static int chainConvex(vertexArray* inc_chain, Int inc_current, Int inc_end)
{
  Int i;
  //if there are no more than 2 vertices, return 1
  if(inc_current >= inc_end-1) return 1;
  for(i=inc_current; i<= inc_end-2; i++)
    {
      if(area(inc_chain->getVertex(i), inc_chain->getVertex(i+1), inc_chain->getVertex(i+2)) <0)
	return 0;
    }
  return 1;
}

static int chainConcave(vertexArray* dec_chain, Int dec_current, Int dec_end)
{
  Int i;
  //if there are no more than 2 vertices, return 1
  if(dec_current >= dec_end -1) return 1;
  for(i=dec_current; i<=dec_end-2; i++)
    {
      if(area(dec_chain->getVertex(i), dec_chain->getVertex(i+1), dec_chain->getVertex(i+2)) >0)
	return 0;
    }
  return 1;
}
 
void monoTriangulationRecGenInU(Real* topVertex, Real* botVertex,
				vertexArray* inc_chain, Int inc_current, Int inc_end,
				vertexArray* dec_chain, Int dec_current, Int dec_end,
				primStream* pStream)
{
  
}

void  monoTriangulationRecGenOpt(Real* topVertex, Real* botVertex,
				 vertexArray* inc_chain, Int inc_current, Int inc_end,
				 vertexArray* dec_chain, Int dec_current, Int dec_end,
				 primStream* pStream)
{
  Int i;
  //copy this to a polygon: directedLine Lioop
  sampledLine* sline;
  directedLine* dline;
  directedLine* poly;

  if(inc_current <= inc_end) //at least one vertex in inc_chain
    {      
      sline = new sampledLine(topVertex, inc_chain->getVertex(inc_current));
      poly = new directedLine(INCREASING, sline);
      for(i=inc_current; i<=inc_end-1; i++)
	{
	  sline = new sampledLine(inc_chain->getVertex(i), inc_chain->getVertex(i+1));
	  dline = new directedLine(INCREASING, sline);
	  poly->insert(dline);
	}
      sline = new sampledLine(inc_chain->getVertex(inc_end), botVertex);
      dline = new directedLine(INCREASING, sline);
      poly->insert(dline);
    }
  else //inc_chian is empty
    {
      sline = new sampledLine(topVertex, botVertex);
      dline = new directedLine(INCREASING, sline);
      poly = dline;
    }
  
  assert(poly != NULL);

  if(dec_current <= dec_end) //at least on vertex in dec_Chain
    {
      sline = new sampledLine(botVertex, dec_chain->getVertex(dec_end));
      dline = new directedLine(INCREASING, sline);
      poly->insert(dline);
      for(i=dec_end; i>dec_current; i--)
	{
	  sline = new sampledLine(dec_chain->getVertex(i), dec_chain->getVertex(i-1));
	  dline = new directedLine(INCREASING, sline);
	  poly->insert(dline);
	}
      sline = new sampledLine(dec_chain->getVertex(dec_current), topVertex);
      dline = new directedLine(INCREASING, sline);
      poly->insert(dline);      
    }
  else //dec_chain  is empty
    {
      sline = new sampledLine(botVertex, topVertex);
      dline = new directedLine(INCREASING, sline);
      poly->insert(dline);
    }

  {
    Int n_cusps;
    Int n_edges = poly->numEdges();
    directedLine** cusps = (directedLine**) malloc(sizeof(directedLine*)*n_edges);
    assert(cusps);
    findInteriorCuspsX(poly, n_cusps, cusps);

    if(n_cusps ==0) //u monotine
      {
	monoTriangulationFun(poly, compV2InX, pStream);
      }
    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(poly, compV2InX, pStream);
	    }
	  else
	    {
	      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();	  
	    }
      }
    else
      {
	//we need a general partitionX funtion (supposed to be in partitionX.C,
	//not implemented yet. XXX
	//monoTriangulationFun(poly, compV2InY, pStream);    
	
	directedLine* new_polygon = polygonConvert(poly);
	directedLine* list = monoPolyPart(new_polygon);
	for(directedLine* temp = list; temp != NULL; temp = temp->getNextPolygon())
	  { 
	    monoTriangulationFun(temp, compV2InX, pStream);
	  }
	//clean up
	list->deletePolygonListWithSline();
        
      }

    free(cusps);
    /*
      if(numInteriorCuspsX(poly) == 0) //is u monotone
	monoTriangulationFun(poly, compV2InX, pStream);
      else //it is not u motone
	monoTriangulationFun(poly, compV2InY, pStream);    
	*/
    //clean up space
    poly->deleteSinglePolygonWithSline();
    return;
  }
      
  //apparently the following code is not reachable, 
  //it is for test purpose
  if(inc_current > inc_end || dec_current>dec_end)
    {
    monoTriangulationRecGen(topVertex, botVertex, inc_chain, inc_current, inc_end,
			    dec_chain, dec_current, dec_end,
			    pStream);    
    return;
  }
  

  if(
     area(dec_chain->getVertex(dec_current),
	  topVertex,
	  inc_chain->getVertex(inc_current)) >=0
     && chainConvex(inc_chain, inc_current, inc_end)
     && chainConcave(dec_chain, dec_current, dec_end)
     && area(inc_chain->getVertex(inc_end), botVertex, dec_chain->getVertex(dec_end)) >=0
     )
    {
      monoTriangulationRecFunGen(topVertex, botVertex, 
				 inc_chain, inc_current, inc_end,
				 dec_chain, dec_current, dec_end, 
				 compV2InX, pStream);
    }
  else
    {
      monoTriangulationRecGen(topVertex, botVertex, inc_chain, inc_current, inc_end,
			      dec_chain, dec_current, dec_end,
			      pStream);
    }
}

/*if inc_current>inc_end, then inc_chain has no points to be considered
 *same for dec_chain
 */
void monoTriangulationRecGen(Real* topVertex, Real* botVertex, 
			  vertexArray* inc_chain, Int inc_current, Int inc_end,