samplemonopoly.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: 2005/10/28 13:09:23 $ $Revision: 1.5 $
*/
/*
** $Header: /home/krh/git/sync/mesa-cvs-repo/Mesa/src/glu/sgi/libnurbs/nurbtess/sampleMonoPoly.cc,v 1.5 2005/10/28 13:09:23 brianp Exp $
*/

#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,