diff options
Diffstat (limited to 'mesalib/src/glu/sgi/libnurbs/nurbtess/directedLine.cc')
| -rw-r--r-- | mesalib/src/glu/sgi/libnurbs/nurbtess/directedLine.cc | 860 |
1 files changed, 0 insertions, 860 deletions
diff --git a/mesalib/src/glu/sgi/libnurbs/nurbtess/directedLine.cc b/mesalib/src/glu/sgi/libnurbs/nurbtess/directedLine.cc deleted file mode 100644 index d942db728..000000000 --- a/mesalib/src/glu/sgi/libnurbs/nurbtess/directedLine.cc +++ /dev/null @@ -1,860 +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 "glimports.h" -#include "zlassert.h" - -#include "quicksort.h" -#include "directedLine.h" -#include "polyDBG.h" - -#ifdef __WATCOMC__ -#pragma warning 726 10 -#endif - -//we must return the newLine -directedLine* directedLine::deleteChain(directedLine* begin, directedLine* end) -{ - if(begin->head()[0] == end->tail()[0] && - begin->head()[1] == end->tail()[1] - ) - { - directedLine *ret = begin->prev; - begin->prev->next = end->next; - end->next->prev = begin->prev; - delete begin->sline; - delete end->sline; - delete begin; - delete end; - - return ret; - } - - directedLine* newLine; - sampledLine* sline = new sampledLine(begin->head(), end->tail()); - newLine = new directedLine(INCREASING, sline); - directedLine *p = begin->prev; - directedLine *n = end->next; - p->next = newLine; - n->prev = newLine; - newLine->prev = p; - newLine->next = n; - - delete begin->sline; - delete end->sline; - delete begin; - delete end; - return newLine; -} - - -void directedLine::deleteSingleLine(directedLine* dline) -{ - //make sure that dline->prev->tail is the same as - //dline->next->head. This is for numerical erros. - //for example, if we delete a line which is almost degeneate - //within (epsilon), then we want to make that the polygon after deletion - //is still a valid polygon - - dline->next->head()[0] = dline->prev->tail()[0]; - dline->next->head()[1] = dline->prev->tail()[1]; - - dline->prev->next = dline->next; - dline->next->prev = dline->prev; - - delete dline; - -} - -static Int myequal(Real a[2], Real b[2]) -{ - /* - if(a[0]==b[0] && a[1] == b[1]) - return 1; - else - return 0; - */ - - - if(fabs(a[0]-b[0]) < 0.00001 && - fabs(a[1]-b[1]) < 0.00001) - return 1; - else - return 0; - -} - -directedLine* directedLine::deleteDegenerateLines() -{ - //if there is only one edge or two edges, don't do anything - if(this->next == this) - return this; - if(this->next == this->prev) - return this; - - //find a nondegenerate line - directedLine* temp; - directedLine* first = NULL; - if(! myequal(head(), tail())) - /* - if(head()[0] != tail()[0] || - head()[1] != tail()[1]) - */ - first = this; - else - { - for(temp = this->next; temp != this; temp = temp->next) - { - /* - if(temp->head()[0] != temp->tail()[0] || - temp->head()[1] != temp->tail()[1]) - */ - if(! myequal(temp->head(), temp->tail())) - { - first = temp; - break; - } - - } - } - - //if there are no non-degenerate lines, then we simply return NULL. - if(first == NULL) - { - deleteSinglePolygonWithSline(); - return NULL; - } - - directedLine* tempNext = NULL; - for(temp =first->next; temp != first; temp = tempNext) - { - tempNext = temp->getNext(); -/* - if(temp->head()[0] == temp->tail()[0] && - temp->head()[1] == temp->tail()[1]) -*/ - - if(myequal(temp->head(), temp->tail())) - deleteSingleLine(temp); - } - return first; -} - -directedLine* directedLine::deleteDegenerateLinesAllPolygons() -{ - directedLine* temp; - directedLine *tempNext = NULL; - directedLine* ret= NULL; - directedLine* retEnd = NULL; - for(temp=this; temp != NULL; temp = tempNext) - { - tempNext = temp->nextPolygon; - temp->nextPolygon = NULL; - if(ret == NULL) - { - ret = retEnd = temp->deleteDegenerateLines(); - - } - else - { - directedLine *newPolygon = temp->deleteDegenerateLines(); - if(newPolygon != NULL) - { - retEnd->nextPolygon = temp->deleteDegenerateLines(); - retEnd = retEnd->nextPolygon; - } - } - } - return ret; -} - -directedLine* directedLine::cutIntersectionAllPoly(int &cutOccur) -{ - directedLine* temp; - directedLine *tempNext = NULL; - directedLine* ret= NULL; - directedLine* retEnd = NULL; - cutOccur = 0; - for(temp=this; temp != NULL; temp = tempNext) - { - int eachCutOccur=0; - tempNext = temp->nextPolygon; - temp->nextPolygon = NULL; - if(ret == NULL) - { - - ret = retEnd = DBG_cutIntersectionPoly(temp, eachCutOccur); - if(eachCutOccur) - cutOccur = 1; - } - else - { - - retEnd->nextPolygon = DBG_cutIntersectionPoly(temp, eachCutOccur); - retEnd = retEnd->nextPolygon; - if(eachCutOccur) - cutOccur = 1; - } - } - return ret; -} - - -void directedLine::deleteSinglePolygonWithSline() -{ - directedLine *temp, *tempNext; - prev->next = NULL; - for(temp=this; temp != NULL; temp = tempNext) - { - tempNext = temp->next; - delete temp->sline; - delete temp; - } -} - -void directedLine::deletePolygonListWithSline() -{ - directedLine *temp, *tempNext; - for(temp=this; temp != NULL; temp=tempNext) - { - tempNext = temp->nextPolygon; - temp->deleteSinglePolygonWithSline(); - } -} - -void directedLine::deleteSinglePolygon() -{ - directedLine *temp, *tempNext; - prev->next = NULL; - for(temp=this; temp != NULL; temp = tempNext) - { - tempNext = temp->next; - delete temp; - } -} - -void directedLine::deletePolygonList() -{ - directedLine *temp, *tempNext; - for(temp=this; temp != NULL; temp=tempNext) - { - tempNext = temp->nextPolygon; - temp->deleteSinglePolygon(); - } -} - - -/*a loop by itself*/ -directedLine::directedLine(short dir, sampledLine* sl) -{ - direction = dir; - sline = sl; - next = this; - prev = this; - nextPolygon = NULL; -// prevPolygon = NULL; - rootBit = 0;/*important to initilzae to 0 meaning not root yet*/ - - rootLink = NULL; - -} - -void directedLine::init(short dir, sampledLine* sl) -{ - direction = dir; - sline = sl; -} - -directedLine::directedLine() -{ - next = this; - prev = this; - nextPolygon = NULL; - rootBit = 0;/*important to initilzae to 0 meaning not root yet*/ - rootLink = NULL; - direction = INCREASING; - sline = NULL; -} - -directedLine::~directedLine() -{ -} - -Real* directedLine::head() -{ - - return (direction==INCREASING)? (sline->get_points())[0] : (sline->get_points())[sline->get_npoints()-1]; -} - -/*inline*/ Real* directedLine::getVertex(Int i) -{ - return (direction==INCREASING)? (sline->get_points())[i] : (sline->get_points())[sline->get_npoints() - 1 -i]; -} - -Real* directedLine::tail() -{ - return (direction==DECREASING)? (sline->get_points())[0] : (sline->get_points())[sline->get_npoints()-1]; -} - - /*insert a new line between prev and this*/ -void directedLine::insert(directedLine* nl) -{ - nl->next = this; - nl->prev = prev; - prev->next = nl; - prev = nl; - nl->rootLink = this; /*assuming that 'this' is the root!!!*/ -} - -Int directedLine::numEdges() -{ - Int ret=0; - directedLine* temp; - if(next == this) return 1; - - ret = 1; - for(temp = next; temp != this; temp = temp->next) - ret++; - return ret; -} - -Int directedLine::numEdgesAllPolygons() -{ - Int ret=0; - directedLine* temp; - for(temp=this; temp!= NULL; temp=temp->nextPolygon) - { - ret += temp->numEdges(); - } - return ret; -} - -/*return 1 if the double linked list forms a polygon. - */ -short directedLine::isPolygon() -{ - directedLine* temp; - - /*a polygon contains at least 3 edges*/ - if(numEdges() <=2) return 0; - - /*check this edge*/ - if(! isConnected()) return 0; - - /*check all other edges*/ - for(temp=next; temp != this; temp = temp->next){ - if(!isConnected()) return 0; - } - return 1; -} - -/*check if the head of this edge is connected to - *the tail of the prev - */ -short directedLine::isConnected() -{ - if( (head()[0] == prev->tail()[0]) && (head()[1] == prev->tail()[1])) - return 1; - else - return 0; -} - -Int compV2InY(Real A[2], Real B[2]) -{ - if(A[1] < B[1]) return -1; - if(A[1] == B[1] && A[0] < B[0]) return -1; - if(A[1] == B[1] && A[0] == B[0]) return 0; - return 1; -} - -Int compV2InX(Real A[2], Real B[2]) -{ - if(A[0] < B[0]) return -1; - if(A[0] == B[0] && A[1] < B[1]) return -1; - if(A[0] == B[0] && A[1] == B[1]) return 0; - return 1; -} - -/*compare two vertices NOT lines! - *A vertex is the head of a directed line. - *(x_1, y_1) <= (x_2, y_2) if - *either y_1 < y_2 - *or y_1 == y_2 && x_1 < x_2. - *return -1 if this->head() <= nl->head(), - *return 1 otherwise - */ -Int directedLine::compInY(directedLine* nl) -{ - if(head()[1] < nl->head()[1]) return -1; - if(head()[1] == nl->head()[1] && head()[0] < nl->head()[0]) return -1; - return 1; -} - -/*compare two vertices NOT lines! - *A vertex is the head of a directed line. - *(x_1, y_1) <= (x_2, y_2) if - *either x_1 < x_2 - *or x_1 == x_2 && y_1 < y_2. - *return -1 if this->head() <= nl->head(), - *return 1 otherwise - */ -Int directedLine::compInX(directedLine* nl) -{ - if(head()[0] < nl->head()[0]) return -1; - if(head()[0] == nl->head()[0] && head()[1] < nl->head()[1]) return -1; - return 1; -} - -/*used by sort precedures - */ -static Int compInY2(directedLine* v1, directedLine* v2) -{ - return v1->compInY(v2); -} -#ifdef NOT_USED -static Int compInX(directedLine* v1, directedLine* v2) -{ - return v1->compInX(v2); -} -#endif - -/*sort all the vertices NOT the lines! - *a vertex is the head of a directed line - */ -directedLine** directedLine::sortAllPolygons() -{ - Int total_num_edges = 0; - directedLine** array = toArrayAllPolygons(total_num_edges); - quicksort( (void**)array, 0, total_num_edges-1, (Int (*)(void *, void *)) compInY2); - - return array; -} - -void directedLine::printSingle() -{ - if(direction == INCREASING) - printf("direction is INCREASING\n"); - else - printf("direction is DECREASING\n"); - printf("head=%f,%f)\n", head()[0], head()[1]); - sline->print(); -} - -/*print one polygon*/ -void directedLine::printList() -{ - directedLine* temp; - printSingle(); - for(temp = next; temp!=this; temp=temp->next) - temp->printSingle(); -} - -/*print all the polygons*/ -void directedLine::printAllPolygons() -{ - directedLine *temp; - for(temp = this; temp!=NULL; temp = temp->nextPolygon) - { - printf("polygon:\n"); - temp->printList(); - } -} - -/*insert this polygon into the head of the old polygon List*/ -directedLine* directedLine::insertPolygon(directedLine* oldList) -{ - /*this polygon is a root*/ - setRootBit(); - if(oldList == NULL) return this; - nextPolygon = oldList; -/* oldList->prevPolygon = this;*/ - return this; -} - -/*cutoff means delete. but we don't deallocate any space, - *so we use cutoff instead of delete - */ -directedLine* directedLine::cutoffPolygon(directedLine *p) -{ - directedLine* temp; - directedLine* prev_polygon = NULL; - if(p == NULL) return this; - - for(temp=this; temp != p; temp = temp->nextPolygon) - { - if(temp == NULL) - { - fprintf(stderr, "in cutoffPolygon, not found\n"); - exit(1); - } - prev_polygon = temp; - } - -/* prev_polygon = p->prevPolygon;*/ - - p->resetRootBit(); - if(prev_polygon == NULL) /*this is the one to cutoff*/ - return nextPolygon; - else { - prev_polygon->nextPolygon = p->nextPolygon; - return this; - } -} - -Int directedLine::numPolygons() -{ - if(nextPolygon == NULL) return 1; - else return 1+nextPolygon->numPolygons(); -} - - -/*let array[index ...] denote - *all the edges in this polygon - *return the next available index of array. - */ -Int directedLine::toArraySinglePolygon(directedLine** array, Int index) -{ - directedLine *temp; - array[index++] = this; - for(temp = next; temp != this; temp = temp->next) - { - array[index++] = temp; - } - return index; -} - -/*the space is allocated. The caller is responsible for - *deallocate the space. - *total_num_edges is set to be the total number of edges of all polygons - */ -directedLine** directedLine::toArrayAllPolygons(Int& total_num_edges) -{ - total_num_edges=numEdgesAllPolygons(); - directedLine** ret = (directedLine**) malloc(sizeof(directedLine*) * total_num_edges); - assert(ret); - - directedLine *temp; - Int index = 0; - for(temp=this; temp != NULL; temp=temp->nextPolygon) { - index = temp->toArraySinglePolygon(ret, index); - } - return ret; -} - -/*assume the polygon is a simple polygon, return - *the area enclosed by it. - *if thee order is counterclock wise, the area is positive. - */ -Real directedLine::polyArea() -{ - directedLine* temp; - Real ret=0.0; - Real x1,y1,x2,y2; - x1 = this->head()[0]; - y1 = this->head()[1]; - x2 = this->next->head()[0]; - y2 = this->next->head()[1]; - ret = -(x2*y1-x1*y2); - for(temp=this->next; temp!=this; temp = temp->next) - { - x1 = temp->head()[0]; - y1 = temp->head()[1]; - x2 = temp->next->head()[0]; - y2 = temp->next->head()[1]; - ret += -( x2*y1-x1*y2); - } - return Real(0.5)*ret; -} - -/*******************split or combine polygons begin********************/ -/*conect a diagonal of a single simple polygon or two simple polygons. - *If the two vertices v1 (head) and v2 (head) are in the same simple polygon, - *then we actually split the simple polygon into two polygons. - *If instead two vertices velong to two difference polygons, - *then we combine the two polygons into one polygon. - *It is upto the caller to decide whether this is a split or a - *combination. - * - *Case Split: - *split a single simple polygon into two simple polygons by - *connecting a diagonal (two vertices). - *v1, v2: the two vertices are the head() of the two directedLines. - * this routine generates one new sampledLine which is returned in - *generatedLine, - *and it generates two directedLines returned in ret_p1 and ret_p2. - *ret_p1 and ret_p2 are used as the entry to the two new polygons. - *Notice the caller should not deallocate the space of v2 and v2 after - *calling this function, since all of the edges are connected to - *ret_p1 or ret_p2. - * - *combine: - *combine two simpolygons into one by connecting one diagonal. - *the returned polygon is returned in ret_p1. - */ -/*ARGSUSED*/ -void directedLine::connectDiagonal(directedLine* v1, directedLine* v2, - directedLine** ret_p1, - directedLine** ret_p2, - sampledLine** generatedLine, - directedLine* polygonList ) -{ - sampledLine *nsline = new sampledLine(2); - - - - nsline->setPoint(0, v1->head()); - nsline->setPoint(1, v2->head()); - - - - /*the increasing line is from v1 head to v2 head*/ - directedLine* newLineInc = new directedLine(INCREASING, nsline); - - - - directedLine* newLineDec = new directedLine(DECREASING, nsline); - - - directedLine* v1Prev = v1->prev; - directedLine* v2Prev = v2->prev; - - v1 ->prev = newLineDec; - v2Prev ->next = newLineDec; - newLineDec->next = v1; - newLineDec->prev = v2Prev; - - v2 ->prev = newLineInc; - v1Prev ->next = newLineInc; - newLineInc->next = v2; - newLineInc->prev = v1Prev; - - *ret_p1 = newLineDec; - *ret_p2 = newLineInc; - *generatedLine = nsline; -} - -//see the function connectDiangle -/*ARGSUSED*/ -void directedLine::connectDiagonal_2slines(directedLine* v1, directedLine* v2, - directedLine** ret_p1, - directedLine** ret_p2, - directedLine* polygonList ) -{ - sampledLine *nsline = new sampledLine(2); - sampledLine *nsline2 = new sampledLine(2); - - nsline->setPoint(0, v1->head()); - nsline->setPoint(1, v2->head()); - nsline2->setPoint(0, v1->head()); - nsline2->setPoint(1, v2->head()); - - /*the increasing line is from v1 head to v2 head*/ - directedLine* newLineInc = new directedLine(INCREASING, nsline); - - directedLine* newLineDec = new directedLine(DECREASING, nsline2); - - directedLine* v1Prev = v1->prev; - directedLine* v2Prev = v2->prev; - - v1 ->prev = newLineDec; - v2Prev ->next = newLineDec; - newLineDec->next = v1; - newLineDec->prev = v2Prev; - - v2 ->prev = newLineInc; - v1Prev ->next = newLineInc; - newLineInc->next = v2; - newLineInc->prev = v1Prev; - - *ret_p1 = newLineDec; - *ret_p2 = newLineInc; - -} - -Int directedLine::samePolygon(directedLine* v1, directedLine* v2) -{ - if(v1 == v2) return 1; - directedLine *temp; - for(temp = v1->next; temp != v1; temp = temp->next) - { - if(temp == v2) return 1; - } - return 0; -} - -directedLine* directedLine::findRoot() -{ - if(rootBit) return this; - directedLine* temp; - for(temp = next; temp != this; temp = temp->next) - if(temp -> rootBit ) return temp; - return NULL; /*should not happen*/ -} - -directedLine* directedLine::rootLinkFindRoot() -{ - directedLine* tempRoot; - directedLine* tempLink; - tempRoot = this; - tempLink = rootLink; - while(tempLink != NULL){ - tempRoot = tempLink; - tempLink = tempRoot->rootLink; - } - return tempRoot; -} - -/*******************split or combine polygons end********************/ - -/*****************IO stuff begin*******************/ - -/*format: - *#polygons - * #vertices - * vertices - * #vertices - * vertices - *... - */ -void directedLine::writeAllPolygons(char* filename) -{ - FILE* fp = fopen(filename, "w"); - assert(fp); - Int nPolygons = numPolygons(); - directedLine *root; - fprintf(fp, "%i\n", nPolygons); - for(root = this; root != NULL; root = root->nextPolygon) - { - directedLine *temp; - Int npoints=0; - npoints = root->get_npoints()-1; - for(temp = root->next; temp != root; temp=temp->next) - npoints += temp->get_npoints()-1; - fprintf(fp, "%i\n", npoints/*root->numEdges()*/); - - - for(Int i=0; i<root->get_npoints()-1; i++){ - fprintf(fp, "%f ", root->getVertex(i)[0]); - fprintf(fp, "%f ", root->getVertex(i)[1]); - } - - for(temp=root->next; temp != root; temp = temp->next) - { - for(Int i=0; i<temp->get_npoints()-1; i++){ - - fprintf(fp, "%f ", temp->getVertex(i)[0]); - fprintf(fp, "%f ", temp->getVertex(i)[1]); - } - fprintf(fp,"\n"); - } - fprintf(fp, "\n"); - } - fclose(fp); -} - -directedLine* readAllPolygons(char* filename) -{ - Int i,j; - FILE* fp = fopen(filename, "r"); - Int nPolygons; - int result; - - assert(fp); - result = fscanf(fp, "%i", &nPolygons); - assert(result != EOF); - directedLine *ret = NULL; - - for(i=0; i<nPolygons; i++) - { - Int nEdges; - result = fscanf(fp, "%i", &nEdges); - assert(result != EOF); - Real vert[2][2] = { { 0 } }; - Real VV[2][2]; - /*the first two vertices*/ - result = fscanf(fp, "%f", &(vert[0][0])); - assert(result != EOF); - result = fscanf(fp, "%f", &(vert[0][1])); - assert(result != EOF); - result = fscanf(fp, "%f", &(vert[1][0])); - assert(result != EOF); - result = fscanf(fp, "%f", &(vert[1][1])); - assert(result != EOF); - VV[1][0] = vert[0][0]; - VV[1][1] = vert[0][1]; - sampledLine *sLine = new sampledLine(2, vert); - directedLine *thisPoly = new directedLine(INCREASING, sLine); -thisPoly->rootLinkSet(NULL); - - directedLine *dLine; - for(j=2; j<nEdges; j++) - { - vert[0][0]=vert[1][0]; - vert[0][1]=vert[1][1]; - result = fscanf(fp, "%f", &(vert[1][0])); - assert(result != EOF); - result = fscanf(fp, "%f", &(vert[1][1])); - assert(result != EOF); - sLine = new sampledLine(2,vert); - dLine = new directedLine(INCREASING, sLine); -dLine->rootLinkSet(thisPoly); - thisPoly->insert(dLine); - } - - VV[0][0]=vert[1][0]; - VV[0][1]=vert[1][1]; - sLine = new sampledLine(2,VV); - dLine = new directedLine(INCREASING, sLine); -dLine->rootLinkSet(thisPoly); - thisPoly->insert(dLine); - - ret = thisPoly->insertPolygon(ret); - } - fclose(fp); - return ret; -} - - - - - - - - |