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

#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include "zlassert.h"
#include "polyDBG.h"

#ifdef __WATCOMC__
#pragma warning 14  10
#pragma warning 391 10
#pragma warning 726 10
#endif

static Real area(Real A[2], Real B[2], Real C[2])
{
  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];
  return Bx*Cy - Cx*By;
}

Int DBG_isConvex(directedLine *poly)
{
  directedLine* temp;
  if(area(poly->head(), poly->tail(), poly->getNext()->tail()) < 0.00000)
    return 0;
  for(temp = poly->getNext(); temp != poly; temp = temp->getNext())
    {
      if(area(temp->head(), temp->tail(), temp->getNext()->tail()) < 0.00000)
	return 0;
    }
  return 1;
}

Int DBG_is_U_monotone(directedLine* poly)
{
  Int n_changes = 0;
  Int prev_sign;
  Int cur_sign;
   directedLine* temp;
  cur_sign = compV2InX(poly->tail(), poly->head());

  n_changes = (compV2InX(poly->getPrev()->tail(), poly->getPrev()->head())
	       != cur_sign);

  for(temp = poly->getNext(); temp != poly; temp = temp->getNext())
    {
      prev_sign = cur_sign;
      cur_sign = compV2InX(temp->tail(), temp->head());

      if(cur_sign != prev_sign)
	n_changes++;
    }

  if(n_changes ==2) return 1;
  else return 0;
}

/*if u-monotone, and there is a long horizontal edge*/
Int DBG_is_U_direction(directedLine* poly)
{
/*
  if(! DBG_is_U_monotone(poly))
    return 0;
*/
  Int V_count = 0;
  Int U_count = 0;
  directedLine* temp;
  if( fabs(poly->head()[0] - poly->tail()[0]) <= fabs(poly->head()[1]-poly->tail()[1]))
    V_count += poly->get_npoints();
  else
    U_count += poly->get_npoints();
  /*
  else if(poly->head()[1] == poly->tail()[1])
    U_count += poly->get_npoints();
    */
  for(temp = poly->getNext(); temp != poly; temp = temp->getNext())
    {
      if( fabs(temp->head()[0] - temp->tail()[0]) <= fabs(temp->head()[1]-temp->tail()[1]))
	V_count += temp->get_npoints();
      else
	U_count += temp->get_npoints();
      /*
      if(temp->head()[0] == temp->tail()[0])
	V_count += temp->get_npoints();
      else if(temp->head()[1] == temp->tail()[1])
	U_count += temp->get_npoints();
	*/
    }

  if(U_count > V_count) return 1;
  else return 0;
}

/*given two line segments, determine whether
 *they intersect each other or not.
 *return 1 if they do,
 *return 0 otherwise
 */
Int DBG_edgesIntersect(directedLine* l1, directedLine* l2)
{
  if(l1->getNext() == l2)
    {
      if(area(l1->head(), l1->tail(), l2->tail()) == 0) //colinear
	{
	  if( (l1->tail()[0] - l1->head()[0])*(l2->tail()[0]-l2->head()[0]) +
	     (l1->tail()[1] - l1->head()[1])*(l2->tail()[1]-l2->head()[1]) >=0)
	    return 0; //not intersect
	  else
	    return 1;
	}
      //else we use the normal code
    }
  else if(l1->getPrev() == l2)
    {
      if(area(l2->head(), l2->tail(), l1->tail()) == 0) //colinear
	{
	  if( (l2->tail()[0] - l2->head()[0])*(l1->tail()[0]-l1->head()[0]) +
	     (l2->tail()[1] - l2->head()[1])*(l1->tail()[1]-l1->head()[1]) >=0)
	    return 0; //not intersect
	  else
	    return 1;
	}
      //else we use the normal code
    }
  else //the two edges are not connected
    {
      if((l1->head()[0] == l2->head()[0] &&
	 l1->head()[1] == l2->head()[1]) ||
	 (l1->tail()[0] == l2->tail()[0] &&
	 l1->tail()[1] == l2->tail()[1]))
	return 1;

    }


  if(
     (
      area(l1->head(), l1->tail(), l2->head())
      *
      area(l1->head(), l1->tail(), l2->tail())
      < 0
      )
     &&
     (
      area(l2->head(), l2->tail(), l1->head())
      *area(l2->head(), l2->tail(), l1->tail())
      < 0
      )
     )
    return 1;
  else
    return 0;
}

/*whether AB and CD intersect
 *return 1 if they do
 *retur 0 otheriwse
 */
Int DBG_edgesIntersectGen(Real A[2], Real B[2], Real C[2], Real D[2])
{
  if(
     (
      area(A, B, C) * area(A,B,D) <0
      )
     &&
     (
      area(C,D,A) * area(C,D,B) < 0
      )
     )
    return 1;
  else
    return 0;
}

/*determien whether    (A,B) interesect chain[start] to [end]
 */
Int DBG_intersectChain(vertexArray* chain, Int start, Int end, Real A[2], Real B[2])
{
  Int i;
  for(i=start; i<=end-2; i++)
    if(DBG_edgesIntersectGen(chain->getVertex(i), chain->getVertex(i+1), A, B))
      return 1;

  return 0;
}

/*determine whether a polygon intersect itself or not
 *return 1 is it does,
 *	 0 otherwise
 */
Int DBG_polygonSelfIntersect(directedLine* poly)
{
  directedLine* temp1;
  directedLine* temp2;
  temp1=poly;
  for(temp2=temp1->getNext(); temp2 != temp1; temp2=temp2->getNext())
    {
      if(DBG_edgesIntersect(temp1, temp2))
	{
	  return 1;
	}

    }

  for(temp1=poly->getNext(); temp1 != poly; temp1 = temp1->getNext())
    for(temp2=temp1->getNext(); temp2 != temp1; temp2=temp2->getNext())
      {
	if(DBG_edgesIntersect(temp1, temp2))
	  {
	    return 1;
	  }
      }
  return 0;
}

/*check whether a line segment intersects a  polygon
 */
Int DBG_edgeIntersectPoly(directedLine* edge, directedLine* poly)
{
  directedLine* temp;
  if(DBG_edgesIntersect(edge, poly))
    return 1;
  for(temp=poly->getNext(); temp != poly; temp=temp->getNext())
    if(DBG_edgesIntersect(edge, temp))
      return 1;
  return 0;
}

/*check whether two polygons intersect
 */
Int DBG_polygonsIntersect(directedLine* p1, directedLine* p2)
{
  directedLine* temp;
  if(DBG_edgeIntersectPoly(p1, p2))
    return 1;
  for(temp=p1->getNext(); temp!= p1; temp = temp->getNext())
    if(DBG_edgeIntersectPoly(temp, p2))
      return 1;
  return 0;
}

/*check whether there are polygons intersecting each other in
 *a list of polygons
 */
Int DBG_polygonListIntersect(directedLine* pList)
{
  directedLine *temp;
  for(temp=pList; temp != NULL; temp = temp->getNextPolygon())
    if(DBG_polygonSelfIntersect(temp))
      return 1;
  directedLine* temp2;
  for(temp=pList; temp!=NULL; temp=temp->getNextPolygon())
    {
      for(temp2=temp->getNextPolygon(); temp2 != NULL; temp2=temp2->getNextPolygon())
	if(DBG_polygonsIntersect(temp, temp2))
	  return 1;
    }

  return 0;
}


Int DBG_isCounterclockwise(directedLine* poly)
{
  return (poly->polyArea() > 0);
}

/*ray: v0 with direction (dx,dy).
 *edge: v1-v2.
 * the extra point v10[2] is given for the information at
 *v1. Basically this edge is connectd to edge
 * v10-v1. If v1 is on the ray,
 * then we need v10  to determine whether this ray intersects
 * the edge or not (that is, return 1 or return 0).
 * If v1 is on the ray, then if v2 and v10 are on the same side of the ray,
 * we return 0, otherwise return 1.
 *For v2, if v2 is on the ray, we always return 0.
 *Notice that v1 and v2 are not symmetric. So the edge is directed!!!
 * The purpose for this convention is such that: a point is inside a polygon
 * if and only if it intersets with odd number of edges.
 */
Int DBG_rayIntersectEdge(Real v0[2], Real dx, Real dy, Real v10[2], Real v1[2], Real v2[2])
{
/*
if( (v1[1] >= v0[1] && v2[1]<= v0[1] )
  ||(v2[1] >= v0[1] && v1[1]<= v0[1] )
   )
  printf("rayIntersectEdge, *********\n");
*/

  Real denom = (v2[0]-v1[0])*(-dy) - (v2[1]-v1[1]) * (-dx);
  Real nomRay = (v2[0]-v1[0]) * (v0[1] - v1[1]) - (v2[1]-v1[1])*(v0[0]-v1[0]);
  Real nomEdge = (v0[0]-v1[0]) * (-dy) - (v0[1]-v1[1])*(-dx);


  /*if the ray is parallel to the edge, return 0: not intersect*/
  if(denom == 0.0)
    return 0;

  /*if v0 is on the edge, return 0: not intersect*/
  if(nomRay == 0.0)
    return 0;

  /*if v1 is on the positive ray, and the neighbor of v1 crosses the ray
   *return 1: intersect
   */
  if(nomEdge == 0)
    { /*v1 is on the positive or negative ray*/

/*
      printf("v1 is on the ray\n");
*/

      if(dx*(v1[0]-v0[0])>=0 && dy*(v1[1]-v0[1])>=0) /*v1 on positive ray*/
	{
	  if(area(v0, v1, v10) * area(v0, v1, v2) >0)
	    return 0;
	  else
	    return 1;
	}
      else /*v1 on negative ray*/
	return 0;
    }

  /*if v2 is on the ray, always return 0: not intersect*/
  if(nomEdge == denom) {
/*    printf("v2 is on the ray\n");*/
    return 0;
  }