diff options
Diffstat (limited to 'mesalib/src/glu/sgi/libnurbs/nurbtess/monoChain.cc')
| -rw-r--r-- | mesalib/src/glu/sgi/libnurbs/nurbtess/monoChain.cc | 936 |
1 files changed, 0 insertions, 936 deletions
diff --git a/mesalib/src/glu/sgi/libnurbs/nurbtess/monoChain.cc b/mesalib/src/glu/sgi/libnurbs/nurbtess/monoChain.cc deleted file mode 100644 index cb28129ad..000000000 --- a/mesalib/src/glu/sgi/libnurbs/nurbtess/monoChain.cc +++ /dev/null @@ -1,936 +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 "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; - keyY = 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; - } - } - assert(ret); - 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)) - { -//printf("case 1\n"); - //this<v and prev < v - //delete both edges - vert->isKey = 1; - vert->keyY = keyY; - treeNode* thisNode = TreeNodeFind(searchTree, vert, (Int (*) (void *, void *))compChains); - vert->isKey = 0; - - vert->getPrev()->isKey = 1; - vert->getPrev()->keyY = keyY; - treeNode* prevNode = TreeNodeFind(searchTree, vert->getPrev(), (Int (*) (void *, void *))compChains); - vert->getPrev()->isKey = 0; - - if(cuspType(dline) == 1)//interior cusp - { - - treeNode* leftEdge = TreeNodePredecessor(prevNode); - treeNode* rightEdge = TreeNodeSuccessor(thisNode); - if(leftEdge == NULL || rightEdge == NULL) - { - errOccur = 1; - goto JUMP_HERE; - } - - directedLine* leftEdgeDline = ((monoChain* ) leftEdge->key)->find(keyY); - - - - directedLine* rightEdgeDline = ((monoChain* ) rightEdge->key)->find(keyY); - - ret_ranges[i] = sweepRangeMake(leftEdgeDline, 1, rightEdgeDline, 1); - } - else /*exterior cusp*/ - { - ret_ranges[i] = sweepRangeMake( dline, 1, dlinePrev, 1); - } - - searchTree = TreeNodeDeleteSingleNode(searchTree, thisNode); - searchTree = TreeNodeDeleteSingleNode(searchTree, prevNode); - - } - else if(isAbove(dline, dline) && isAbove(dline, dlinePrev)) - { -//printf("case 2\n"); - //insert both edges - treeNode* thisNode = TreeNodeMake(vert); - treeNode* prevNode = TreeNodeMake(vert->getPrev()); - - vert->isKey = 1; - vert->keyY = keyY; - searchTree = TreeNodeInsert(searchTree, thisNode, (Int (*) (void *, void *))compChains); - vert->isKey = 0; - - vert->getPrev()->isKey = 1; - vert->getPrev()->keyY = keyY; - searchTree = TreeNodeInsert(searchTree, prevNode, (Int (*) (void *, void *))compChains); - vert->getPrev()->isKey = 0; - - if(cuspType(dline) == 1) //interior cusp - { -//printf("cuspType is 1\n"); - treeNode* leftEdge = TreeNodePredecessor(thisNode); - treeNode* rightEdge = TreeNodeSuccessor(prevNode); - if(leftEdge == NULL || rightEdge == NULL) - { - errOccur = 1; - goto JUMP_HERE; - } -//printf("leftEdge is %i, rightEdge is %i\n", leftEdge, rightEdge); - directedLine* leftEdgeDline = ((monoChain*) leftEdge->key)->find(keyY); - directedLine* rightEdgeDline = ((monoChain*) rightEdge->key)->find(keyY); - ret_ranges[i] = sweepRangeMake( leftEdgeDline, 1, rightEdgeDline, 1); - } - else //exterior cusp - { -//printf("cuspType is not 1\n"); - ret_ranges[i] = sweepRangeMake(dlinePrev, 1, dline, 1); - } - } - else - { -//printf("%i,%i\n", isAbove(dline, dline), isAbove(dline, dlinePrev)); - errOccur = 1; - goto JUMP_HERE; - - fprintf(stderr, "error in MC_sweepY\n"); - exit(1); - } - } - - JUMP_HERE: - //finally clean up space: delete the search tree - TreeNodeDeleteWholeTree(searchTree); - return errOccur; -} - -void MC_findDiagonals(Int total_num_edges, monoChain** sortedVertices, - sweepRange** ranges, Int& num_diagonals, - directedLine** diagonal_vertices) -{ - Int i,j,k; - k=0; - //reset 'current' of all the monoChains - for(i=0; i<total_num_edges; i++) - sortedVertices[i]->resetCurrent(); - - for(i=0; i<total_num_edges; i++) - { - directedLine* vert = sortedVertices[i]->getHead(); - directedLine* thisEdge = vert; - directedLine* prevEdge = vert->getPrev(); - if(isBelow(vert, thisEdge) && isBelow(vert, prevEdge) && compEdges(prevEdge, thisEdge)<0) - { - //this is an upward interior cusp - diagonal_vertices[k++] = vert; - - directedLine* leftEdge = ranges[i]->left; - directedLine* rightEdge = ranges[i]->right; - - directedLine* leftVert = leftEdge; - directedLine* rightVert = rightEdge->getNext(); - assert(leftVert->head()[1] >= vert->head()[1]); - assert(rightVert->head()[1] >= vert->head()[1]); - directedLine* minVert = (leftVert->head()[1] <= rightVert->head()[1])?leftVert:rightVert; - Int found = 0; - for(j=i+1; j<total_num_edges; j++) - { - if(sortedVertices[j]->getHead()->head()[1] > minVert->head()[1]) - break; - - if(sweepRangeEqual(ranges[i], ranges[j])) - { - found = 1; - break; - } - } - - if(found) - diagonal_vertices[k++] = sortedVertices[j]->getHead(); - else - diagonal_vertices[k++] = minVert; - } - else if(isAbove(vert, thisEdge) && isAbove(vert, prevEdge) && compEdges(prevEdge, thisEdge)>0) - { - //downward interior cusp - diagonal_vertices[k++] = vert; - directedLine* leftEdge = ranges[i]->left; - directedLine* rightEdge = ranges[i]->right; - directedLine* leftVert = leftEdge->getNext(); - directedLine* rightVert = rightEdge; - assert(leftVert->head()[1] <= vert->head()[1]); - assert(rightVert->head()[1] <= vert->head()[1]); - directedLine* maxVert = (leftVert->head()[1] > rightVert->head()[1])? leftVert:rightVert; - Int found=0; - for(j=i-1; j>=0; j--) - { - if(sortedVertices[j]->getHead()->head()[1] < maxVert->head()[1]) - break; - if(sweepRangeEqual(ranges[i], ranges[j])) - { - found = 1; - break; - } - } - if(found) - diagonal_vertices[k++] = sortedVertices[j]->getHead(); - else - diagonal_vertices[k++] = maxVert; - } - } - num_diagonals = k/2; -} - - - - -directedLine* MC_partitionY(directedLine *polygons, sampledLine **retSampledLines) -{ -//printf("enter mc_partitionY\n"); - Int total_num_chains = 0; - monoChain* loopList = directedLineLoopListToMonoChainLoopList(polygons); - monoChain** array = loopList->toArrayAllLoops(total_num_chains); - - if(total_num_chains<=2) //there is just one single monotone polygon - { - loopList->deleteLoopList(); - free(array); - *retSampledLines = NULL; - return polygons; - } - -//loopList->printAllLoops(); -//printf("total_num_chains=%i\n", total_num_chains); - quicksort( (void**)array, 0, total_num_chains-1, (Int (*)(void*, void*))compChainHeadInY); -//printf("after quicksort\n"); - - sweepRange** ranges = (sweepRange**)malloc(sizeof(sweepRange*) * (total_num_chains)); - assert(ranges); - - if(MC_sweepY(total_num_chains, array, ranges)) - { - loopList->deleteLoopList(); - free(array); - *retSampledLines = NULL; - return NULL; - } -//printf("after MC_sweepY\n"); - - - Int num_diagonals; - /*number diagonals is < total_num_edges*total_num_edges*/ - directedLine** diagonal_vertices = (directedLine**) malloc(sizeof(directedLine*) * total_num_chains*2/*total_num_edges*/); - assert(diagonal_vertices); - -//printf("before call MC_findDiagonales\n"); - - MC_findDiagonals(total_num_chains, array, ranges, num_diagonals, diagonal_vertices); -//printf("after call MC_findDia, num_diagnla=%i\n", num_diagonals); - - directedLine* ret_polygons = polygons; - sampledLine* newSampledLines = NULL; - Int i,k; - - num_diagonals=deleteRepeatDiagonals(num_diagonals, diagonal_vertices, diagonal_vertices); - - - -//drawDiagonals(num_diagonals, diagonal_vertices); -//printf("diagoanls are \n"); -//for(i=0; i<num_diagonals; i++) -// { -// printf("(%f,%f)\n", diagonal_vertices[2*i]->head()[0], diagonal_vertices[2*i]->head()[1]); -// printf("**(%f,%f)\n", diagonal_vertices[2*i+1]->head()[0], diagonal_vertices[2*i+1]->head()[1]); -// } - - Int *removedDiagonals=(Int*)malloc(sizeof(Int) * num_diagonals); - for(i=0; i<num_diagonals; i++) - removedDiagonals[i] = 0; -// printf("first pass\n"); - - - for(i=0,k=0; i<num_diagonals; i++,k+=2) - { - - - directedLine* v1=diagonal_vertices[k]; - directedLine* v2=diagonal_vertices[k+1]; - directedLine* ret_p1; - directedLine* ret_p2; - - /*we ahve to determine whether v1 and v2 belong to the same polygon before - *their structure are modified by connectDiagonal(). - */ -/* - directedLine *root1 = v1->findRoot(); - directedLine *root2 = v2->findRoot(); - assert(root1); - assert(root2); -*/ - -directedLine* root1 = v1->rootLinkFindRoot(); -directedLine* root2 = v2->rootLinkFindRoot(); - - if(root1 != root2) - { - - removedDiagonals[i] = 1; - sampledLine* generatedLine; - - - - v1->connectDiagonal(v1,v2, &ret_p1, &ret_p2, &generatedLine, ret_polygons); - - - - newSampledLines = generatedLine->insert(newSampledLines); -/* - ret_polygons = ret_polygons->cutoffPolygon(root1); - - ret_polygons = ret_polygons->cutoffPolygon(root2); - ret_polygons = ret_p1->insertPolygon(ret_polygons); -root1->rootLinkSet(ret_p1); -root2->rootLinkSet(ret_p1); -ret_p1->rootLinkSet(NULL); -ret_p2->rootLinkSet(ret_p1); -*/ - ret_polygons = ret_polygons->cutoffPolygon(root2); - - - -root2->rootLinkSet(root1); -ret_p1->rootLinkSet(root1); -ret_p2->rootLinkSet(root1); - - /*now that we have connected the diagonal v1 and v2, - *we have to check those unprocessed diagonals which - *have v1 or v2 as an end point. Notice that the head of v1 - *has the same coodinates as the head of v2->prev, and the head of - *v2 has the same coordinate as the head of v1->prev. - *Suppose these is a diagonal (v1, x). If (v1,x) is still a valid - *diagonal, then x should be on the left hand side of the directed line: *v1->prev->head -- v1->head -- v1->tail. Otherwise, (v1,x) should be - *replaced by (v2->prev, x), that is, x is on the left of - * v2->prev->prev->head, v2->prev->head, v2->prev->tail. - */ - Int ii, kk; - for(ii=0, kk=0; ii<num_diagonals; ii++, kk+=2) - if( removedDiagonals[ii]==0) - { - directedLine* d1=diagonal_vertices[kk]; - directedLine* d2=diagonal_vertices[kk+1]; - /*check d1, and replace diagonal_vertices[kk] if necessary*/ - if(d1 == v1) { - /*check if d2 is to left of v1->prev->head:v1->head:v1->tail*/ - if(! pointLeft2Lines(v1->getPrev()->head(), - v1->head(), v1->tail(), d2->head())) - { -/* - assert(pointLeft2Lines(v2->getPrev()->getPrev()->head(), - v2->getPrev()->head(), - v2->getPrev()->tail(), d2->head())); -*/ - diagonal_vertices[kk] = v2->getPrev(); - } - } - if(d1 == v2) { - /*check if d2 is to left of v2->prev->head:v2->head:v2->tail*/ - if(! pointLeft2Lines(v2->getPrev()->head(), - v2->head(), v2->tail(), d2->head())) - { -/* - assert(pointLeft2Lines(v1->getPrev()->getPrev()->head(), - v1->getPrev()->head(), - v1->getPrev()->tail(), d2->head())); -*/ - diagonal_vertices[kk] = v1->getPrev(); - } - } - /*check d2 and replace diagonal_vertices[k+1] if necessary*/ - if(d2 == v1) { - /*check if d1 is to left of v1->prev->head:v1->head:v1->tail*/ - if(! pointLeft2Lines(v1->getPrev()->head(), - v1->head(), v1->tail(), d1->head())) - { -/* assert(pointLeft2Lines(v2->getPrev()->getPrev()->head(), - v2->getPrev()->head(), - v2->getPrev()->tail(), d1->head())); -*/ - diagonal_vertices[kk+1] = v2->getPrev(); - } - } - if(d2 == v2) { - /*check if d1 is to left of v2->prev->head:v2->head:v2->tail*/ - if(! pointLeft2Lines(v2->getPrev()->head(), - v2->head(), v2->tail(), d1->head())) - { -/* assert(pointLeft2Lines(v1->getPrev()->getPrev()->head(), - v1->getPrev()->head(), - v1->getPrev()->tail(), d1->head())); -*/ - diagonal_vertices[kk+1] = v1->getPrev(); - } - } - } -}/*end if (root1 not equal to root 2)*/ -} - - /*second pass, now all diagoals should belong to the same polygon*/ -//printf("second pass: \n"); - -// for(i=0; i<num_diagonals; i++) -// printf("%i ", removedDiagonals[i]); - - - for(i=0,k=0; i<num_diagonals; i++, k += 2) - if(removedDiagonals[i] == 0) - { - - - directedLine* v1=diagonal_vertices[k]; - directedLine* v2=diagonal_vertices[k+1]; - - - - directedLine* ret_p1; - directedLine* ret_p2; - - /*we ahve to determine whether v1 and v2 belong to the same polygon before - *their structure are modified by connectDiagonal(). - */ - directedLine *root1 = v1->findRoot(); -/* - directedLine *root2 = v2->findRoot(); - - - - assert(root1); - assert(root2); - assert(root1 == root2); - */ - sampledLine* generatedLine; - - - - v1->connectDiagonal(v1,v2, &ret_p1, &ret_p2, &generatedLine, ret_polygons); - newSampledLines = generatedLine->insert(newSampledLines); - - ret_polygons = ret_polygons->cutoffPolygon(root1); - - ret_polygons = ret_p1->insertPolygon(ret_polygons); - - ret_polygons = ret_p2->insertPolygon(ret_polygons); - - - - for(Int j=i+1; j<num_diagonals; j++) - { - if(removedDiagonals[j] ==0) - { - - directedLine* temp1=diagonal_vertices[2*j]; - directedLine* temp2=diagonal_vertices[2*j+1]; - if(temp1==v1 || temp1==v2 || temp2==v1 || temp2==v2) - if(! temp1->samePolygon(temp1, temp2)) - { - /*if temp1 and temp2 are in different polygons, - *then one of them must be v1 or v2. - */ - - - - assert(temp1==v1 || temp1 == v2 || temp2==v1 || temp2 ==v2); - if(temp1==v1) - { - diagonal_vertices[2*j] = v2->getPrev(); - } - if(temp2==v1) - { - diagonal_vertices[2*j+1] = v2->getPrev(); - } - if(temp1==v2) - { - diagonal_vertices[2*j] = v1->getPrev(); - } - if(temp2==v2) - { - diagonal_vertices[2*j+1] = v1->getPrev(); - } - } - } - } - - } - - - //clean up - loopList->deleteLoopList(); - free(array); - free(ranges); - free(diagonal_vertices); - free(removedDiagonals); - - *retSampledLines = newSampledLines; - return ret_polygons; -} - - |