aboutsummaryrefslogtreecommitdiff
path: root/mesalib/src/glu/sgi/libnurbs/nurbtess/polyDBG.cc
diff options
context:
space:
mode:
Diffstat (limited to 'mesalib/src/glu/sgi/libnurbs/nurbtess/polyDBG.cc')
-rw-r--r--mesalib/src/glu/sgi/libnurbs/nurbtess/polyDBG.cc734
1 files changed, 0 insertions, 734 deletions
diff --git a/mesalib/src/glu/sgi/libnurbs/nurbtess/polyDBG.cc b/mesalib/src/glu/sgi/libnurbs/nurbtess/polyDBG.cc
deleted file mode 100644
index 4d04df73f..000000000
--- a/mesalib/src/glu/sgi/libnurbs/nurbtess/polyDBG.cc
+++ /dev/null
@@ -1,734 +0,0 @@
-/*
-** 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;
- }
-
- /*finally */
- if(denom*nomRay>0 && denom*nomEdge>0 && nomEdge/denom <=1.0)
- return 1;
- return 0;
-}
-
-
-/*return the number of intersections*/
-Int DBG_rayIntersectPoly(Real v0[2], Real dx, Real dy, directedLine* poly)
-{
- directedLine* temp;
- Int count=0;
- if(DBG_rayIntersectEdge(v0, dx, dy, poly->getPrev()->head(), poly->head(), poly->tail()))
- count++;
-
- for(temp=poly->getNext(); temp != poly; temp = temp->getNext())
- if(DBG_rayIntersectEdge(v0, dx, dy, temp->getPrev()->head(), temp->head(), temp->tail()))
- count++;
-/*printf("ray intersect poly: count=%i\n", count);*/
- return count;
-}
-
-Int DBG_pointInsidePoly(Real v[2], directedLine* poly)
-{
-/*
-printf("enter pointInsidePoly , v=(%f,%f)\n", v[0], v[1]);
-printf("the polygon is\n");
-poly->printList();
-*/
- /*for debug purpose*/
- assert( (DBG_rayIntersectPoly(v,1,0,poly) % 2 )
- == (DBG_rayIntersectPoly(v,1,Real(0.1234), poly) % 2 )
- );
- if(DBG_rayIntersectPoly(v, 1, 0, poly) % 2 == 1)
- return 1;
- else
- return 0;
-}
-
-/*return the number of polygons which contain thie polygon
- * as a subset
- */
-Int DBG_enclosingPolygons(directedLine* poly, directedLine* list)
-{
- directedLine* temp;
- Int count=0;
-/*
-printf("%i\n", DBG_pointInsidePoly(poly->head(),
- list->getNextPolygon()
- ->getNextPolygon()
- ->getNextPolygon()
- ->getNextPolygon()
-));
-*/
-
- for(temp = list; temp != NULL; temp = temp->getNextPolygon())
- {
- if(poly != temp)
- if(DBG_pointInsidePoly(poly->head(), temp))
- count++;
-/* printf("count=%i\n", count);*/
- }
- return count;
-}
-
-void DBG_reverse(directedLine* poly)
-{
- if(poly->getDirection() == INCREASING)
- poly->putDirection(DECREASING);
- else
- poly->putDirection(INCREASING);
-
- directedLine* oldNext = poly->getNext();
- poly->putNext(poly->getPrev());
- poly->putPrev(oldNext);
-
- directedLine* temp;
- for(temp=oldNext; temp!=poly; temp = oldNext)
- {
- if(temp->getDirection() == INCREASING)
- temp->putDirection(DECREASING);
- else
- temp->putDirection(INCREASING);
-
- oldNext = temp->getNext();
- temp->putNext(temp->getPrev());
- temp->putPrev(oldNext);
- }
- printf("reverse done\n");
-}
-
-Int DBG_checkConnectivity(directedLine *polygon)
-{
- if(polygon == NULL) return 1;
- directedLine* temp;
- if(polygon->head()[0] != polygon->getPrev()->tail()[0] ||
- polygon->head()[1] != polygon->getPrev()->tail()[1])
- return 0;
- for(temp=polygon->getNext(); temp != polygon; temp=temp->getNext())
- {
- if(temp->head()[0] != temp->getPrev()->tail()[0] ||
- temp->head()[1] != temp->getPrev()->tail()[1])
- return 0;
- }
- return 1;
-}
-
-/*print out error message.
- *If it cannot modify the polygon list to make it satify the
- *requirements, return 1.
- *otherwise modify the polygon list, and return 0
- */
-Int DBG_check(directedLine *polyList)
-{
- directedLine* temp;
- if(polyList == NULL) return 0;
-
- /*if there are intersections, print out error message
- */
- if(DBG_polygonListIntersect(polyList))
- {
- fprintf(stderr, "DBG_check: there are self intersections, don't know to modify the polygons\n");
- return 1;
- }
-
- /*check the connectivity of each polygon*/
- for(temp = polyList; temp!= NULL; temp = temp ->getNextPolygon())
- {
- if(! DBG_checkConnectivity(temp))
- {
- fprintf(stderr, "DBG_check, polygon not connected\n");
- return 1;
- }
- }
-
- /*check the orientation of each polygon*/
- for(temp = polyList; temp!= NULL; temp = temp ->getNextPolygon())
- {
-
-
- Int correctDir;
-
- if( DBG_enclosingPolygons(temp, polyList) % 2 == 0)
- correctDir = 1; /*counterclockwise*/
- else
- correctDir = 0; /*clockwise*/
-
- Int actualDir = DBG_isCounterclockwise(temp);
-
- if(correctDir != actualDir)
- {
- fprintf(stderr, "DBG_check: polygon with incorrect orientations. reversed\n");
-
- DBG_reverse(temp);
- }
-
- }
- return 0;
-}
-
-/**************handle self intersections*****************/
-//determine whether e interects [begin, end] or not
-static directedLine* DBG_edgeIntersectChainD(directedLine *e,
- directedLine *begin, directedLine *end)
-{
- directedLine *temp;
- for(temp=begin; temp != end; temp = temp->getNext())
- {
- if(DBG_edgesIntersect(e, temp))
- return temp;
- }
- if(DBG_edgesIntersect(e, end))
- return end;
- return NULL;
-}
-
-//given a polygon, cut the edges off and finally obtain a
-//a polygon without intersections. The cut-off edges are
-//dealloated. The new polygon is returned.
-directedLine* DBG_cutIntersectionPoly(directedLine *polygon, int& cutOccur)
-{
- directedLine *begin, *end, *next;
- begin = polygon;
- end = polygon;
- cutOccur = 0;
- while( (next = end->getNext()) != begin)
- {
- directedLine *interc = NULL;
- if( (interc = DBG_edgeIntersectChainD(next, begin, end)))
- {
- int fixed = 0;
- if(DBG_edgesIntersect(next, interc->getNext()))
- {
- //trying to fix it
- Real buf[2];
- int i;
- Int n=5;
- buf[0] = interc->tail()[0];
- buf[1] = interc->tail()[1];
-
- for(i=1; i<n; i++)
- {
- Real r = ((Real)i) / ((Real) n);
- Real u = (1-r) * interc->head()[0] + r * interc->tail()[0];
- Real v = (1-r) * interc->head()[1] + r * interc->tail()[1];
- interc->tail()[0] = interc->getNext()->head()[0] = u;
- interc->tail()[1] = interc->getNext()->head()[1] = v;
- if( (! DBG_edgesIntersect(next, interc)) &&
- (! DBG_edgesIntersect(next, interc->getNext())))
- break; //we fixed it
- }
- if(i==n) // we didn't fix it
- {
- fixed = 0;
- //back to original
- interc->tail()[0] = interc->getNext()->head()[0] = buf[0];
- interc->tail()[1] = interc->getNext()->head()[1] = buf[1];
- }
- else
- {
- fixed = 1;
- }
- }
- if(fixed == 0)
- {
- cutOccur = 1;
- begin->deleteSingleLine(next);
-
- if(begin != end)
- {
- if(DBG_polygonSelfIntersect(begin))
- {
- directedLine* newEnd = end->getPrev();
- begin->deleteSingleLine(end);
- end = newEnd;
- }
- }
- }
- else
- {
- end = end->getNext();
- }
- }
- else
- {
- end = end->getNext();
- }
- }
- return begin;
-}
-
-//given a polygon, cut the edges off and finally obtain a
-//a polygon without intersections. The cut-off edges are
-//dealloated. The new polygon is returned.
-#if 0 // UNUSED
-static directedLine* DBG_cutIntersectionPoly_notwork(directedLine *polygon)
-{
- directedLine *crt;//current polygon
- directedLine *begin;
- directedLine *end;
- directedLine *temp;
- crt = polygon;
- int find=0;
- while(1)
- {
-//printf("loop\n");
- //if there are less than 3 edges, we should stop
- if(crt->getPrev()->getPrev() == crt)
- return NULL;
-
- if(DBG_edgesIntersect(crt, crt->getNext()) ||
- (crt->head()[0] == crt->getNext()->tail()[0] &&
- crt->head()[1] == crt->getNext()->tail()[1])
- )
- {
- find = 1;
- crt=crt->deleteChain(crt, crt->getNext());
- }
- else
- {
- //now we know crt and crt->getNext do not intersect
- begin = crt;
- end = crt->getNext();
-//printf("begin=(%f,%f)\n", begin->head()[0], begin->head()[1]);
-//printf("end=(%f,%f)\n", end->head()[0], end->head()[1]);
- for(temp=end->getNext(); temp!=begin; temp= temp->getNext())
- {
-//printf("temp=(%f,%f)\n", temp->head()[0], temp->head()[1]);
- directedLine *intersect = DBG_edgeIntersectChainD(temp, begin, end);
- if(intersect != NULL)
- {
- crt = crt->deleteChain(intersect, temp);
- find=1;
- break; //the for loop
- }
- else
- {
- end = temp;
- }
- }
- }
- if(find == 0)
- return crt;
- else
- find = 0; //go to next loop
-}
-}
-#endif
-
-directedLine* DBG_cutIntersectionAllPoly(directedLine* list)
-{
- directedLine* temp;
- directedLine* tempNext=NULL;
- directedLine* ret = NULL;
- int cutOccur=0;
- for(temp=list; temp != NULL; temp = tempNext)
- {
- directedLine *left;
- tempNext = temp->getNextPolygon();
-
- left = DBG_cutIntersectionPoly(temp, cutOccur);
- if(left != NULL)
- ret=left->insertPolygon(ret);
- }
- return ret;
-}
-
-sampledLine* DBG_collectSampledLinesAllPoly(directedLine *polygonList)
-{
- directedLine *temp;
- sampledLine* tempHead = NULL;
- sampledLine* tempTail = NULL;
- sampledLine* cHead = NULL;
- sampledLine* cTail = NULL;
-
- if(polygonList == NULL)
- return NULL;
-
- DBG_collectSampledLinesPoly(polygonList, cHead, cTail);
-
- assert(cHead);
- assert(cTail);
- for(temp = polygonList->getNextPolygon(); temp != NULL; temp = temp->getNextPolygon())
- {
- DBG_collectSampledLinesPoly(temp, tempHead, tempTail);
- cTail->insert(tempHead);
- cTail = tempTail;
- }
- return cHead;
-}
-
-void DBG_collectSampledLinesPoly(directedLine *polygon, sampledLine*& retHead, sampledLine*& retTail)
-{
- directedLine *temp;
- retHead = NULL;
- retTail = NULL;
- if(polygon == NULL)
- return;
-
- retHead = retTail = polygon->getSampledLine();
- for(temp = polygon->getNext(); temp != polygon; temp=temp->getNext())
- {
- retHead = temp->getSampledLine()->insert(retHead);
- }
-}
generated by cgit v1.2.3 (git 2.25.1) at 2024-07-01 13:35:10 +0000