partitiony.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: 2001/11/29 16:16:55 $ $Revision: 1.2 $
*/
/*
** $Header: /home/krh/git/sync/mesa-cvs-repo/Mesa/src/glu/sgi/libnurbs/nurbtess/partitionY.cc,v 1.2 2001/11/29 16:16:55 kschultz Exp $
*/

#include <stdlib.h>
#include <stdio.h>
#include <time.h>

#include "zlassert.h"
#include "partitionY.h"
#include "searchTree.h"
#include "quicksort.h"
#include "polyUtil.h"


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


/*retrurn 
 *-1: if A < B (Ya<Yb) || (Ya==Yb)
 * 0: if A == B
 * 1: if A>B
 */
static Int compVertInY(Real A[2], Real B[2])
{
  if( (A[1] < B[1]) || (A[1]==B[1] && A[0]<B[0])) 
    return -1;
  else if
    ( A[1] == B[1] && A[0] == B[0]) return 0;
  else
    return 1;
}

/*v is a vertex: the head of en edge,
 *e is an edge,
 *return 1 if e is below v: assume v1 and v2 are the two endpoints of e:
 * v1<= v, v2<=v.
 */
Int isBelow(directedLine *v, directedLine *e)
{
  Real* vert = v->head();
  if(   compVertInY(e->head(), vert) != 1 
     && compVertInY(e->tail(), vert) != 1
     )
    return 1;
  else
    return 0;
}

/*v is a vertex: the head of en edge,
 *e is an edge,
 *return 1 if e is below v: assume v1 and v2 are the two endpoints of e:
 * v1>= v, v2>=v.
 */
Int isAbove(directedLine *v, directedLine *e)
{
  Real* vert = v->head();
  if(   compVertInY(e->head(), vert) != -1 
     && compVertInY(e->tail(), vert) != -1
     )
    return 1;
  else
    return 0;
}

Int isCusp(directedLine *v)
{
  Real *A=v->getPrev()->head();
  Real *B=v->head();
  Real *C=v->tail();
  if(A[1] < B[1] && B[1] < C[1])
    return 0;
  else if(A[1] > B[1] && B[1] > C[1])
    return 0;
  else if(A[1] < B[1] && C[1] < B[1])
    return 1;
  else if(A[1] > B[1] && C[1] > B[1])
    return 1;

  if(isAbove(v, v) && isAbove(v, v->getPrev()) ||
     isBelow(v, v) && isBelow(v, v->getPrev()))
    return 1;
  else
    return 0;
}

/*crossproduct is strictly less than 0*/
Int isReflex(directedLine *v)
{
  Real* A = v->getPrev()->head();
  Real* B = v->head();
  Real* C = v->tail();
  Real Bx,By, Cx, Cy;
  Bx = B[0] - A[0];
  By = B[1] - A[1];
  Cx = C[0] - A[0];
  Cy = C[1] - A[1];

  if(Bx*Cy - Cx*By < 0) return 1;
  else return 0;
}

 /*return 
 *0: not-cusp
 *1: interior cusp
 *2: exterior cusp
 */
Int cuspType(directedLine *v)
{
  if(! isCusp(v)) return 0;
  else if(isReflex(v)) return 1;
  else
    return 2;
}

sweepRange* sweepRangeMake(directedLine* left, Int leftType,
			   directedLine* right, Int rightType)
{
  sweepRange* ret = (sweepRange*)malloc(sizeof(sweepRange));
  assert(ret);
  ret->left = left;
  ret->leftType = leftType;
  ret->right = right;
  ret->rightType = rightType;
  return ret;
}

void sweepRangeDelete(sweepRange* range)
{
  free(range);
}

Int sweepRangeEqual(sweepRange* src1, sweepRange* src2)
{
  Int leftEqual;
  Int rightEqual;
  
  
  /*The case when both are vertices should not happen*/
  assert(! (src1->leftType == 0 && src2->leftType == 0));    
  if(src1->leftType == 0 && src2->leftType == 1){
    if(src1->left == src2->left ||
       src1->left->getPrev() == src2->left
       )
      leftEqual = 1;
    else
      leftEqual = 0;
  }
  else if(src1->leftType == 1 && src2->leftType == 1){
    if(src1->left == src2->left)
      leftEqual = 1;
    else
      leftEqual = 0;
  }
  else /*src1->leftType == 1 && src2->leftType == 0*/{
    if(src1->left == src2->left ||
       src1->left == src2->left->getPrev()
       )
      leftEqual = 1;
    else 
      leftEqual = 0;
  }

  /*the same thing for right*/
  /*The case when both are vertices should not happen*/
  assert(! (src1->rightType == 0 && src2->rightType == 0));    
  if(src1->rightType == 0 && src2->rightType == 1){
    if(src1->right == src2->right ||
       src1->right->getPrev() == src2->right
       )
      rightEqual = 1;
    else
      rightEqual = 0;
  }
  else if(src1->rightType == 1 && src2->rightType == 1){
    if(src1->right == src2->right)
      rightEqual = 1;
    else
      rightEqual = 0;
  }
  else /*src1->rightType == 1 && src2->rightType == 0*/{
    if(src1->right == src2->right ||
       src1->right == src2->right->getPrev()
       )
      rightEqual = 1;
    else 
      rightEqual = 0;
  }
  
  return (leftEqual == 1 || rightEqual == 1);
}

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

/*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 = Real(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;
}
  
/*used by sort precedures
 */
static Int compInY(directedLine* v1, directedLine* v2)
{
  return v1->compInY(v2);
}

void findDiagonals(Int total_num_edges, directedLine** sortedVertices, sweepRange** ranges, Int& num_diagonals, directedLine** diagonal_vertices)
{
  Int i,j,k;

  k=0;

  for(i=0; i<total_num_edges; i++)
    {
      directedLine* vert =sortedVertices[i];
      directedLine* thisEdge = vert;
      directedLine* prevEdge = vert->getPrev();
/*
printf("find i=%i\n", i);            
printf("the vertex is\n");
vert->printSingle();
*/
      if(isBelow(vert, thisEdge) && isBelow(vert, prevEdge) && compEdges(prevEdge, thisEdge)<0)
	{
	  /*this is an upward interior cusp*/
	  diagonal_vertices[k++] = vert;

	  for(j=i+1; j<total_num_edges; j++)
	    if(sweepRangeEqual(ranges[i], ranges[j]))
	      {
		diagonal_vertices[k++] = sortedVertices[j];
		break;
	      }
	  assert(j<total_num_edges);


	}
      else if(isAbove(vert, thisEdge) && isAbove(vert, prevEdge) && compEdges(prevEdge, thisEdge)>0)
	{
	  /*this is an downward interior cusp*/
	  diagonal_vertices[k++] = vert;
	  for(j=i-1; j>=0; j--)
	    if(sweepRangeEqual(ranges[i], ranges[j]))
	      {
		diagonal_vertices[k++] = sortedVertices[j];
		break;
	      }
/*	  printf("j=%i\n", j);*/
	  assert(j>=0);



	}
    }
  num_diagonals = k/2;
}

/*get rid of repeated diagonlas so that each diagonal appears only once in the array
 */
Int deleteRepeatDiagonals(Int num_diagonals, directedLine** diagonal_vertices, directedLine** new_vertices)
{
  Int i,k;
  Int j,l;
  Int index;
  index=0;
  for(i=0,k=0; i<num_diagonals; i++, k+=2)
    {
      Int isRepeated=0;
      /*check the diagonla (diagonal_vertice[k], diagonal_vertices[k+1])
       *is repeated or not
       */
      for(j=0,l=0; j<index; j++, l+=2)
	{
	  if(
	     (diagonal_vertices[k] == new_vertices[l] && 
	      diagonal_vertices[k+1] == new_vertices[l+1]
	      )
	     ||
	     (
	      diagonal_vertices[k] == new_vertices[l+1] && 
	      diagonal_vertices[k+1] == new_vertices[l]
	      )
	     )
	    {
	      isRepeated=1;
	      break;
	    }
	}
      if(! isRepeated)
	{
	  new_vertices[index+index] = diagonal_vertices[k];
	  new_vertices[index+index+1] = diagonal_vertices[k+1];