slicer.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.
*/

/*
 * slicer.c++
 *
 * $Date: 2005/10/28 13:09:23 $ $Revision: 1.5 $
 * $Header: /home/krh/git/sync/mesa-cvs-repo/Mesa/src/glu/sgi/libnurbs/internals/slicer.cc,v 1.5 2005/10/28 13:09:23 brianp Exp $
 */

#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include "glimports.h"
#include "mystdio.h"
#include "myassert.h"
#include "bufpool.h"
#include "slicer.h"
#include "backend.h"
#include "arc.h"
#include "gridtrimvertex.h"
#include "simplemath.h"
#include "trimvertex.h"
#include "varray.h"

#include "polyUtil.h" //for area()

//static int count=0;

/*USE_OPTTT is initiated in trimvertex.h*/

#ifdef USE_OPTTT
	#include <GL/gl.h>
#endif

//#define USE_READ_FLAG //whether to use new or old tesselator
                          //if defined, it reads "flagFile", 
                          // if the number is 1, then use new tess
                          // otherwise, use the old tess.
                         //if not defined, then use new tess.
#ifdef USE_READ_FLAG
static Int read_flag(char* name);
Int newtess_flag = read_flag("flagFile");
#endif

//#define COUNT_TRIANGLES
#ifdef COUNT_TRIANGLES
Int num_triangles = 0;
Int num_quads = 0;
#endif

#define max(a,b) ((a>b)? a:b)
#define ZERO 0.00001 /*determing whether a loop is a rectngle or not*/
#define equalRect(a,b) ((glu_abs(a-b) <= ZERO)? 1:0) //only used in tessellating a rectangle

#if 0 // UNUSED
static Int is_Convex(Arc_ptr loop)
{
  if(area(loop->tail(), loop->head(), loop->next->head()) <0 )
    return 0;
  for(Arc_ptr jarc = loop->next; jarc != loop; jarc = jarc->next)
    {
      if(area(jarc->tail(), jarc->head(), jarc->next->head()) < 0)
	return 0;
    }
  return 1;
}
#endif

/******triangulate a monotone polygon**************/
#include "monoTriangulation.h"
#if 0 // UNUSED
static int is_U_monotone(Arc_ptr loop)
{
  int n_changes=0;
  int prev_sign;
  int cur_sign;
  Arc_ptr temp;

  cur_sign = compV2InX(loop->head(), loop->tail());

  n_changes  = (compV2InX(loop->prev->head(), loop->prev->tail())
		!= cur_sign);

  for(temp=loop->next; temp != loop; temp = temp->next)
    {
      prev_sign = cur_sign;
      cur_sign = compV2InX(temp->head(), temp->tail());
      if(cur_sign != prev_sign)
       {
#ifdef DEBUG
	 printf("***change signe\n");
#endif
	 n_changes++;
       }
    }
  if(n_changes == 2) return 1;
  else
    return 0;
}
#endif

inline int compInY(REAL a[2], REAL b[2])
{
  if(a[1] < b[1])
    return -1;
  else if (a[1] > b[1])
    return 1;
  else if(a[0] > b[0])
    return 1;
  else return -1;
}

void monoTriangulationLoop(Arc_ptr loop, Backend& backend, primStream* pStream)
{
  int i;
  //find the top, bottom, increasing and decreasing chain
  //then call monoTrianulation
  Arc_ptr jarc, temp;
  Arc_ptr top;
  Arc_ptr bot;
  top = bot = loop;
  if(compInY(loop->tail(), loop->prev->tail()) < 0)
    {
      //first find bot
      for(temp = loop->next; temp != loop; temp = temp->next)
	{
	  if(compInY(temp->tail(), temp->prev->tail()) > 0)
	    break;
	}
      bot = temp->prev;
      //then find top
      for(temp=loop->prev; temp != loop; temp = temp->prev)
	{
	  if(compInY(temp->tail(), temp->prev->tail()) > 0)
	    break;
	}
      top = temp;
    }
  else //loop > loop->prev
    {
      for(temp=loop->next; temp != loop; temp = temp->next)
	{
	  if(compInY(temp->tail(), temp->prev->tail()) < 0)
	    break;
	}
      top = temp->prev;
      for(temp=loop->prev; temp != loop; temp = temp->prev)
	{
	  if(compInY(temp->tail(), temp->prev->tail()) < 0)
	    break;
	}
      bot = temp;
    }
  //creat increase and decrease chains
  vertexArray inc_chain(50); //this is a dynamci array
  for(i=1; i<=top->pwlArc->npts-2; i++) 
    {
      //the first vertex is the top which doesn't below to inc_chain
      inc_chain.appendVertex(top->pwlArc->pts[i].param);
    }
  for(jarc=top->next; jarc != bot; jarc = jarc->next)
    {
      for(i=0; i<=jarc->pwlArc->npts-2; i++)
	{
	  inc_chain.appendVertex(jarc->pwlArc->pts[i].param);
	}
      
    }
  vertexArray dec_chain(50);
  for(jarc = top->prev; jarc != bot; jarc = jarc->prev)
    {
      for(i=jarc->pwlArc->npts-2; i>=0; i--)
	{
	  dec_chain.appendVertex(jarc->pwlArc->pts[i].param);
	}
    }
  for(i=bot->pwlArc->npts-2; i>=1; i--)
    {
      dec_chain.appendVertex(jarc->pwlArc->pts[i].param);
    }	  

  monoTriangulationRec(top->tail(), bot->tail(), &inc_chain, 0,
		       &dec_chain, 0, &backend);

}

/********tesselate a rectanlge (OPTIMIZATION**************/
static void triangulateRectGen(Arc_ptr loop, int n_ulines, int n_vlines, Backend& backend);

static Int is_rect(Arc_ptr loop)
{
  Int nlines =1;
  for(Arc_ptr jarc = loop->next; jarc != loop; jarc = jarc->next)
    {
      nlines++;
      if(nlines == 5)
	break;
    }
  if(nlines != 4)
    return 0;


/*
printf("here1\n");
printf("loop->tail=(%f,%f)\n", loop->tail()[0], loop->tail()[1]);
printf("loop->head=(%f,%f)\n", loop->head()[0], loop->head()[1]);
printf("loop->next->tail=(%f,%f)\n", loop->next->tail()[0], loop->next->tail()[1]);
printf("loop->next->head=(%f,%f)\n", loop->next->head()[0], loop->next->head()[1]);
if(fglu_abs(loop->tail()[0] - loop->head()[0])<0.000001)
	printf("equal 1\n");
if(loop->next->tail()[1] == loop->next->head()[1])
	printf("equal 2\n");
*/

  if( (glu_abs(loop->tail()[0] - loop->head()[0])<=ZERO) && 
      (glu_abs(loop->next->tail()[1] - loop->next->head()[1])<=ZERO) &&
      (glu_abs(loop->prev->tail()[1] - loop->prev->head()[1])<=ZERO) &&
      (glu_abs(loop->prev->prev->tail()[0] - loop->prev->prev->head()[0])<=ZERO)
     )
    return 1;
  else if
    ( (glu_abs(loop->tail()[1] - loop->head()[1]) <= ZERO) && 
      (glu_abs(loop->next->tail()[0] - loop->next->head()[0]) <= ZERO) &&
      (glu_abs(loop->prev->tail()[0] - loop->prev->head()[0]) <= ZERO) &&
      (glu_abs(loop->prev->prev->tail()[1] - loop->prev->prev->head()[1]) <= ZERO)
     )
      return 1;
  else
    return 0;
}


//a line with the same u for opt
#ifdef USE_OPTTT
static void evalLineNOGE_BU(TrimVertex *verts, int n, Backend& backend)
{
  int i;
  backend.preEvaluateBU(verts[0].param[0]);
  for(i=0; i<n; i++)
    backend.tmeshvertNOGE_BU(&verts[i]);
}
#endif

//a line with the same v for opt
#ifdef USE_OPTTT
static void evalLineNOGE_BV(TrimVertex *verts, int n, Backend& backend)
{
  int i;
  backend.preEvaluateBV(verts[0].param[1]);

  for(i=0; i<n; i++)
    backend.tmeshvertNOGE_BV(&verts[i]);
}
#endif

#ifdef USE_OPTTT
static void evalLineNOGE(TrimVertex *verts, int n, Backend& backend)
{

  if(verts[0].param[0] == verts[n-1].param[0]) //all u;s are equal
    evalLineNOGE_BU(verts, n, backend);
  else if(verts[0].param[1] == verts[n-1].param[1]) //all v's are equal
    evalLineNOGE_BV(verts, n, backend);
  else
    {
      int i;
      for(i=0; i<n; i++)
	backend.tmeshvertNOGE(&verts[i]);
    }
}
#endif

inline void  OPT_OUTVERT(TrimVertex& vv, Backend& backend) 
{

#ifdef USE_OPTTT
  glNormal3fv(vv.cache_normal);                         
  glVertex3fv(vv.cache_point);
#else

  backend.tmeshvert(&vv);

#endif

}

static void triangulateRectAux(PwlArc* top, PwlArc* bot, PwlArc* left, PwlArc* right, Backend& backend);

static void triangulateRect(Arc_ptr loop, Backend& backend, int TB_or_LR, int ulinear, int vlinear)
{
  //we know the loop is a rectangle, but not sure which is top
  Arc_ptr top, bot, left, right;
  if(loop->tail()[1] == loop->head()[1])
    {
      if(loop->tail()[1] > loop->prev->prev->tail()[1])
	{

	top = loop;
	}
      else{

	top = loop->prev->prev;
	}
    }
  else 
    {
      if(loop->tail()[0] > loop->prev->prev->tail()[0])
	{
	  //loop is the right arc

	  top = loop->next;
	}
      else
	{

	  top = loop->prev;
	}
    }
  left = top->next;
  bot  = left->next;
  right= bot->next;

  //if u, v are both nonlinear, then if the
  //boundary is tessellated dense, we also
  //sample the inside to get a better tesslletant.
  if( (!ulinear) && (!vlinear))
    {
      int nu = top->pwlArc->npts;
      if(nu < bot->pwlArc->npts)
	nu = bot->pwlArc->npts;
      int nv = left->pwlArc->npts;
      if(nv < right->pwlArc->npts)
	nv = right->pwlArc->npts;
/*
      if(nu > 2 && nv > 2)
	{
	  triangulateRectGen(top, nu-2,  nv-2, backend);
	  return;
	}
*/
    }

  if(TB_or_LR == 1)
    triangulateRectAux(top->pwlArc, bot->pwlArc, left->pwlArc, right->pwlArc, backend);
  else if(TB_or_LR == -1)
    triangulateRectAux(left->pwlArc, right->pwlArc, bot->pwlArc, top->pwlArc, backend);    
  else
    {
      Int maxPointsTB = top->pwlArc->npts + bot->pwlArc->npts;
      Int maxPointsLR = left->pwlArc->npts + right->pwlArc->npts;
      
      if(maxPointsTB < maxPointsLR)
	triangulateRectAux(left->pwlArc, right->pwlArc, bot->pwlArc, top->pwlArc, backend);    
      else
	triangulateRectAux(top->pwlArc, bot->pwlArc, left->pwlArc, right->pwlArc, backend);
    }
}

static void triangulateRectAux(PwlArc* top, PwlArc* bot, PwlArc* left, PwlArc* right, Backend& backend)
{ //if(maxPointsTB >= maxPointsLR)
    {

      Int d, topd_left, topd_right, botd_left, botd_right, i,j;
      d = left->npts /2;

#ifdef USE_OPTTT
      evalLineNOGE(top->pts, top->npts, backend);
      evalLineNOGE(bot->pts, bot->npts, backend);
      evalLineNOGE(left->pts, left->npts, backend);
      evalLineNOGE(right->pts, right->npts, backend);
#endif

      if(top->npts == 2) {
	backend.bgntfan();
	OPT_OUTVERT(top->pts[0], backend);//the root
	for(i=0; i<left->npts; i++){
	  OPT_OUTVERT(left->pts[i], backend);
	}
	for(i=1; i<= bot->npts-2; i++){
	  OPT_OUTVERT(bot->pts[i], backend);
	}
	backend.endtfan();
	
	backend.bgntfan();
	OPT_OUTVERT(bot->pts[bot->npts-2], backend);
	for(i=0; i<right->npts; i++){
	  OPT_OUTVERT(right->pts[i], backend);
	}
	backend.endtfan();
      }
      else if(bot->npts == 2) {
	backend.bgntfan();
	OPT_OUTVERT(bot->pts[0], backend);//the root
	for(i=0; i<right->npts; i++){
	  OPT_OUTVERT(right->pts[i], backend);
	}
	for(i=1; i<= top->npts-2; i++){
	  OPT_OUTVERT(top->pts[i], backend);
	}
	backend.endtfan();
	
	backend.bgntfan();
	OPT_OUTVERT(top->pts[top->npts-2], backend);