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

#include "gluos.h"
#include <stdlib.h>
#include <stdio.h>
#include <GL/gl.h>

#include "glimports.h"
#include "zlassert.h"

#include "monoChain.h"
#include "quicksort.h"
#include "searchTree.h"
#include "polyUtil.h"

#ifndef max
#define max(a,b) ((a>b)? a:b)
#endif
#ifndef min
#define min(a,b) ((a>b)? b:a)
#endif

extern Int isCusp(directedLine *v);
extern Int deleteRepeatDiagonals(Int num_diagonals, directedLine** diagonal_vertices, directedLine** new_vertices);

//for debug purpose only
#if 0 // UNUSED
static void drawDiagonals(Int num_diagonals, directedLine** diagonal_vertices)
{
  Int i;
  for(i=0; i<num_diagonals; i++)
    {
      glBegin(GL_LINE);
      glVertex2fv(diagonal_vertices[2*i]->head());
      glVertex2fv(diagonal_vertices[2*i+1]->head());
      glEnd();
    }
}
#endif

/*given (x_1, y_1) and (x_2, y_2), and y
 *return x such that (x,y) is on the line
 */
inline Real intersectHoriz(Real x1, Real y1, Real x2, Real y2, Real y)
{
  return ((y2==y1)? (x1+x2)*0.5 : x1 + ((y-y1)/(y2-y1)) * (x2-x1));
}

//compare the heads of the two chains
static int compChainHeadInY(monoChain* mc1, monoChain* mc2)
{
  return compV2InY(mc1->getHead()->head(), mc2->getHead()->head());
}

monoChain::monoChain(directedLine* cHead, directedLine* cTail)
{
  chainHead = cHead;
  chainTail = cTail;
  next = this;
  prev = this;
  
  nextPolygon = NULL;

  //compute bounding box
  directedLine* temp;
  minX = maxX = chainTail->head()[0];
  minY = maxY = chainTail->head()[1];

  for(temp=chainHead; temp!=cTail; temp = temp->getNext())
    {
      if(temp->head()[0] < minX)
	minX = temp->head()[0];
      if(temp->head()[0] > maxX)
	maxX = temp->head()[0];

      if(temp->head()[1] < minY)
	minY = temp->head()[1];
      if(temp->head()[1] > maxY)
	maxY = temp->head()[1];
    }

  //check whether the chain is increasing or decreasing
  if(chainHead->compInY(chainTail) <0)
    isIncrease = 1;
  else
    isIncrease = 0;
  
  //initilize currrent, this is used for accelerating search
  if(isIncrease)
    current = chainHead;
  else
    current = chainTail;

  isKey = 0;
}

//insert a new line between prev and this
void monoChain::insert(monoChain* nc)
{
  nc->next = this;
  nc->prev = prev;
  prev->next = nc;
  prev = nc;
}

void monoChain::deleteLoop()
{
  monoChain *temp, *tempNext;
  prev->next = NULL;
  for(temp=this; temp != NULL; temp = tempNext)
    {
      tempNext = temp->next;
      delete temp;
    }
}

void monoChain::deleteLoopList()
{
  monoChain *temp, *tempNext;
  for(temp=this; temp != NULL; temp = tempNext)
    {
      tempNext = temp->nextPolygon;
      temp->deleteLoop();
    }
}

Int monoChain::toArraySingleLoop(monoChain** array, Int index)
{
  monoChain *temp;
  array[index++] = this;
  for(temp = next; temp != this; temp = temp->next)
    {
      array[index++] = temp;
    }
  return index;
}

monoChain** monoChain::toArrayAllLoops(Int& num_chains)
{
  num_chains = numChainsAllLoops();
  monoChain **ret =  (monoChain**) malloc(sizeof(monoChain*) * num_chains);
  assert(ret);
  monoChain *temp;
  Int index = 0;
  for(temp = this; temp != NULL; temp=temp->nextPolygon){
    index = temp->toArraySingleLoop(ret, index);
  }
  return ret;
}

Int monoChain::numChainsSingleLoop()
{
  Int ret=0;
  monoChain* temp;
  if(next == this) return 1;
  ret = 1;
  for(temp=next; temp != this; temp = temp->next)
    ret++;
  return ret;
}

Int monoChain::numChainsAllLoops()
{
  Int ret=0;
  monoChain *temp;
  for(temp =this; temp != NULL; temp = temp->nextPolygon)
    ret += temp->numChainsSingleLoop();
  return ret;
}

//update 'current'
Real monoChain::chainIntersectHoriz(Real y)
{
  directedLine* temp;
  if(isIncrease)
    {
      for(temp= current; temp != chainTail; temp = temp->getNext())
	{
	  if(temp->head()[1] > y)
	    break;
	}
      current = temp->getPrev();
    }
  else 
    {
      for(temp = current; temp != chainHead; temp = temp->getPrev())
	{
	  if(temp->head()[1] > y)
	    break;
	}
      current = temp->getNext();
    }
  return intersectHoriz(current->head()[0], current->head()[1], current->tail()[0], current->tail()[1], y);
}

monoChain* directedLineLoopToMonoChainLoop(directedLine* loop)
{
  directedLine *temp;
  monoChain *ret=NULL;

  //find the first cusp
  directedLine *prevCusp=NULL;
  directedLine *firstCusp;

  if(isCusp(loop))
    prevCusp = loop;
  else
    {
      for(temp = loop->getNext(); temp != loop; temp = temp->getNext())
	if(isCusp(temp))
	  break;
      prevCusp = temp;
    }
  firstCusp = prevCusp;
//printf("first cusp is (%f,%f), (%f,%f), (%f,%f)\n", prevCusp->getPrev()->head()[0], prevCusp->getPrev()->head()[1], prevCusp->head()[0], prevCusp->head()[1], prevCusp->tail()[0], prevCusp->tail()[1]);

  for(temp = prevCusp->getNext(); temp != loop; temp = temp->getNext())
    {
      if(isCusp(temp))
	{
//printf("the cusp is (%f,%f), (%f,%f), (%f,%f)\n", temp->getPrev()->head()[0], temp->getPrev()->head()[1], temp->head()[0], temp->head()[1], temp->tail()[0], temp->tail()[1]);
	  if(ret == NULL)
	    {
	      ret = new monoChain(prevCusp, temp);
	    }
	  else
	    ret->insert(new monoChain(prevCusp, temp));
	  prevCusp = temp;	  
	}
    }
  ret->insert(new monoChain(prevCusp, firstCusp));

  return ret;
}

monoChain* directedLineLoopListToMonoChainLoopList(directedLine* list)
{
  directedLine* temp;
  monoChain* mc;
  monoChain* mcEnd;
  mc = directedLineLoopToMonoChainLoop(list);
  mcEnd = mc;  
  for(temp = list->getNextPolygon(); temp != NULL; temp = temp->getNextPolygon())
    {
      monoChain *newLoop = directedLineLoopToMonoChainLoop(temp);
      mcEnd->setNextPolygon(newLoop);
      mcEnd = newLoop;
    }
  return mc;
}

/*compare two edges of a polygon.
 *edge A < edge B if there is a horizontal line so that the intersection
 *with A is to the left of the intersection with B.
 *This function is used in sweepY for the dynamic search tree insertion to
 *order the edges.
 * Implementation: (x_1,y_1) and (x_2, y_2)
 */
static Int compEdges(directedLine *e1, directedLine *e2)
{
  Real* head1 = e1->head();
  Real* tail1 = e1->tail();
  Real* head2 = e2->head();
  Real* tail2 = e2->tail();
/*
  Real h10 = head1[0];
  Real h11 = head1[1];
  Real t10 = tail1[0];
  Real t11 = tail1[1];
  Real h20 = head2[0];
  Real h21 = head2[1];
  Real t20 = tail2[0];
  Real t21 = tail2[1];
*/
  Real e1_Ymax, e1_Ymin, e2_Ymax, e2_Ymin;
/*
  if(h11>t11) {
    e1_Ymax= h11;
    e1_Ymin= t11;
  }
  else{
    e1_Ymax = t11;
    e1_Ymin = h11;
  }

  if(h21>t21) {
    e2_Ymax= h21;
    e2_Ymin= t21;
  }
  else{
    e2_Ymax = t21;
    e2_Ymin = h21;
  }
*/
 
  if(head1[1]>tail1[1]) {
    e1_Ymax= head1[1];
    e1_Ymin= tail1[1];
  }
  else{
    e1_Ymax = tail1[1];
    e1_Ymin = head1[1];
  }

  if(head2[1]>tail2[1]) {
    e2_Ymax= head2[1];
    e2_Ymin= tail2[1];
  }
  else{
    e2_Ymax = tail2[1];
    e2_Ymin = head2[1];
  }

  
  /*Real e1_Ymax = max(head1[1], tail1[1]);*/ /*max(e1->head()[1], e1->tail()[1]);*/
  /*Real e1_Ymin = min(head1[1], tail1[1]);*/ /*min(e1->head()[1], e1->tail()[1]);*/
  /*Real e2_Ymax = max(head2[1], tail2[1]);*/ /*max(e2->head()[1], e2->tail()[1]);*/
  /*Real e2_Ymin = min(head2[1], tail2[1]);*/ /*min(e2->head()[1], e2->tail()[1]);*/

  Real Ymax = min(e1_Ymax, e2_Ymax);
  Real Ymin = max(e1_Ymin, e2_Ymin);
    
  Real y = 0.5*(Ymax + Ymin);

/*  Real x1 = intersectHoriz(e1->head()[0], e1->head()[1], e1->tail()[0], e1->tail()[1], y);
  Real x2 = intersectHoriz(e2->head()[0], e2->head()[1], e2->tail()[0], e2->tail()[1], y);
*/
/*
  Real x1 = intersectHoriz(h10, h11, t10, t11, y);
  Real x2 = intersectHoriz(h20, h21, t20, t21, y);
*/
  Real x1 = intersectHoriz(head1[0], head1[1], tail1[0], tail1[1], y);
  Real x2 = intersectHoriz(head2[0], head2[1], tail2[0], tail2[1], y);

  if(x1<= x2) return -1;
  else return 1;
}

Int  compChains(monoChain* mc1, monoChain* mc2)
{
  Real y;
  assert(mc1->isKey || mc2->isKey);
  if(mc1->isKey)
    y = mc1->keyY;
  else
    y = mc2->keyY;
  directedLine *d1 = mc1->find(y);
  directedLine *d2 = mc2->find(y);
  mc2->find(y);
//  Real x1 = mc1->chainIntersectHoriz(y);
//  Real x2 = mc2->chainIntersectHoriz(y);
  return   compEdges(d1, d2);
}

//this function modifies current for efficiency
directedLine* monoChain::find(Real y)
{
  directedLine *ret;
  directedLine *temp;
  assert(current->head()[1] <= y);
  if(isIncrease)
    {
      assert(chainTail->head()[1] >=y);
      for(temp=current; temp!=chainTail; temp = temp->getNext())
	{
	  if(temp->head()[1] > y)
	    break;
	}
      current = temp->getPrev();
      ret = current;
    }
  else
    {
      for(temp=current; temp != chainHead; temp = temp->getPrev())
	{
	  if(temp->head()[1] > y)
	    break;
	}
      current = temp->getNext();
      ret = temp;
    }
  return ret;  
}

void monoChain::printOneChain()
{
  directedLine* temp;
  for(temp = chainHead; temp != chainTail; temp = temp->getNext())
    {
      printf("(%f,%f) ", temp->head()[0], temp->head()[1]);
    }
  printf("(%f,%f) \n", chainTail->head()[0], chainTail->head()[1]);  
}

void monoChain::printChainLoop()
{
  monoChain* temp;
  this->printOneChain();
  for(temp = next; temp != this; temp = temp->next)
    {
      temp->printOneChain();
    }
  printf("\n");
}

void monoChain::printAllLoops()
{
  monoChain* temp;
  for(temp=this; temp != NULL; temp = temp->nextPolygon)
    temp->printChainLoop();
}

//return 1 if error occures
Int MC_sweepY(Int nVertices, monoChain** sortedVertices, sweepRange** ret_ranges)
{
  Int i;
  Real keyY;
  Int errOccur=0;
//printf("enter MC_sweepY\n");
//printf("nVertices=%i\n", nVertices);
  /*for each vertex in the sorted list, update the binary search tree.
   *and store the range information for each vertex.
   */
  treeNode* searchTree = NULL;
//printf("nVertices=%i\n", nVertices);
  for(i=0; i<nVertices; i++)
    {
      monoChain* vert = sortedVertices[i];
      keyY = vert->getHead()->head()[1]; //the sweep line
      directedLine *dline = vert->getHead();
      directedLine *dlinePrev = dline->getPrev();
      if(isBelow(dline, dline) && isBelow(dline, dlinePrev))