diff options
Diffstat (limited to 'mesalib/src/glu/sgi/libnurbs/nurbtess/monoTriangulation.cc')
| -rw-r--r-- | mesalib/src/glu/sgi/libnurbs/nurbtess/monoTriangulation.cc | 1482 |
1 files changed, 1482 insertions, 0 deletions
diff --git a/mesalib/src/glu/sgi/libnurbs/nurbtess/monoTriangulation.cc b/mesalib/src/glu/sgi/libnurbs/nurbtess/monoTriangulation.cc new file mode 100644 index 000000000..8e8d49dda --- /dev/null +++ b/mesalib/src/glu/sgi/libnurbs/nurbtess/monoTriangulation.cc @@ -0,0 +1,1482 @@ +/* +** 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 "gluos.h" +#include "glimports.h" +#include "zlassert.h" + +#include "monoTriangulation.h" +#include "polyUtil.h" /*for area*/ +#include "partitionX.h" +#include "monoPolyPart.h" + + + +extern directedLine* polygonConvert(directedLine* polygon); + +/*poly is NOT deleted + */ +void monoTriangulationOpt(directedLine* poly, primStream* pStream) +{ + Int n_cusps; + Int n_edges = poly->numEdges(); + directedLine** cusps = (directedLine**) malloc(sizeof(directedLine*)*n_edges); + assert(cusps); + findInteriorCuspsX(poly, n_cusps, cusps); + if(n_cusps ==0) //u monotine + { + monoTriangulationFun(poly, compV2InX, pStream); + } + else if(n_cusps == 1) // one interior cusp + { + directedLine* new_polygon = polygonConvert(cusps[0]); + directedLine* other = findDiagonal_singleCuspX(new_polygon); + //<other> should NOT be null unless there are self-intersecting + //trim curves. In that case, we don't want to core dump, instead, + //we triangulate anyway, and print out error message. + if(other == NULL) + { + monoTriangulationFun(poly, compV2InX, pStream); + } + else + { + directedLine* ret_p1; + directedLine* ret_p2; + + new_polygon->connectDiagonal_2slines(new_polygon, other, + &ret_p1, + &ret_p2, + new_polygon); + + monoTriangulationFun(ret_p1, compV2InX, pStream); + monoTriangulationFun(ret_p2, compV2InX, pStream); + + ret_p1->deleteSinglePolygonWithSline(); + ret_p2->deleteSinglePolygonWithSline(); + } + } + else + { + //we need a general partitionX funtion (supposed to be in partitionX.C, + //not implemented yet. XXX + monoTriangulationFun(poly, compV2InY, pStream); + } + + free(cusps); +} + +void monoTriangulationRecOpt(Real* topVertex, Real* botVertex, + vertexArray* left_chain, Int left_current, + vertexArray* right_chain, Int right_current, + primStream* pStream) +{ + Int i,j; + Int n_left = left_chain->getNumElements(); + Int n_right = right_chain->getNumElements(); + if(left_current>= n_left-1 || + right_current>= n_right-1) + { + monoTriangulationRec(topVertex, botVertex, left_chain, left_current, + right_chain, right_current, pStream); + return; + } + //now both left and right have at least two vertices each. + Real left_v = left_chain->getVertex(left_current)[1]; + Real right_v = right_chain->getVertex(right_current)[1]; + + if(left_v <= right_v) //first left vertex is below right + { + //find the last vertex of right which is above or equal to left + for(j=right_current; j<=n_right-1; j++) + { + if(right_chain->getVertex(j)[1] < left_v) + break; + } + monoTriangulationRecGen(topVertex, left_chain->getVertex(left_current), + left_chain, left_current, left_current, + right_chain, right_current, j-1, + pStream); + monoTriangulationRecOpt(right_chain->getVertex(j-1), + botVertex, + left_chain, left_current, + right_chain, j, + pStream); + } + else //first right vertex is strictly below left + { + //find the last vertex of left which is strictly above right + for(i=left_current; i<=n_left-1; i++) + { + if(left_chain->getVertex(i)[1] <= right_v) + break; + } + monoTriangulationRecGen(topVertex, right_chain->getVertex(right_current), + left_chain, left_current, i-1, + right_chain, right_current, right_current, + pStream); + monoTriangulationRecOpt(left_chain->getVertex(i-1), + botVertex, + left_chain, i, + right_chain, right_current, + pStream); + } +} + + +void monoTriangulationRecGenTBOpt(Real* topVertex, Real* botVertex, + vertexArray* inc_chain, Int inc_current, Int inc_end, + vertexArray* dec_chain, Int dec_current, Int dec_end, + primStream* pStream) +{ + pStream->triangle(topVertex, inc_chain->getVertex(inc_current), dec_chain->getVertex(dec_current)); + +/*printf("**(%f,%f)\n", inc_chain->getArray()[0][0],inc_chain->getArray()[0][1]);*/ + triangulateXYMonoTB(inc_end-inc_current+1, inc_chain->getArray()+inc_current, dec_end-dec_current+1, dec_chain->getArray()+dec_current, pStream); + + pStream->triangle(botVertex, dec_chain->getVertex(dec_end), inc_chain->getVertex(inc_end)); +} + + +/*n_left>=1 + *n_right>=1 + *the strip is going top to bottom. compared to the funtion + * triangulateXYmono() + */ +void triangulateXYMonoTB(Int n_left, Real** leftVerts, + Int n_right, Real** rightVerts, + primStream* pStream) +{ + + + Int i,j,k,l; + Real* topMostV; + + assert(n_left>=1 && n_right>=1); + if(leftVerts[0][1] >= rightVerts[0][1]) + { + i=1; + j=0; + topMostV = leftVerts[0]; + } + else + { + i=0; + j=1; + topMostV = rightVerts[0]; + } + + while(1) + { + if(i >= n_left) /*case1: no more in left*/ + { + + if(j<n_right-1) /*at least two vertices in right*/ + { + pStream->begin(); + pStream->insert(topMostV); + for(k=n_right-1; k>=j; k--) + pStream->insert(rightVerts[j]); + + pStream->end(PRIMITIVE_STREAM_FAN); + + } + + break; + } + else if(j>= n_right) /*case2: no more in right*/ + { + + if(i<n_left-1) /*at least two vertices in left*/ + { + pStream->begin(); + pStream->insert(topMostV); + + for(k=i; k<n_left; k++) + pStream->insert(leftVerts[k]); + + pStream->end(PRIMITIVE_STREAM_FAN); + } + + break; + } + else /* case3: neither is empty, plus the topMostV, there is at least one triangle to output*/ + { + + if(leftVerts[i][1] >= rightVerts[j][1]) + { + pStream->begin(); + pStream->insert(rightVerts[j]); /*the origin of this fan*/ + + pStream->insert(topMostV); + + /*find the last k>=i such that + *leftverts[k][1] >= rightverts[j][1] + */ + k=i; + while(k<n_left) + { + if(leftVerts[k][1] < rightVerts[j][1]) + break; + k++; + } + k--; + for(l=i; l<=k; l++) + { + pStream->insert(leftVerts[l]); + } + + pStream->end(PRIMITIVE_STREAM_FAN); + //update i for next loop + i = k+1; + topMostV = leftVerts[k]; + + } + else /*leftVerts[i][1] < rightVerts[j][1]*/ + { + pStream->begin(); + pStream->insert(leftVerts[i]);/*the origion of this fan*/ + + /*find the last k>=j such that + *rightverts[k][1] > leftverts[i][1]*/ + k=j; + while(k< n_right) + { + if(rightVerts[k][1] <= leftVerts[i][1]) + break; + k++; + } + k--; + + for(l=k; l>= j; l--) + pStream->insert(rightVerts[l]); + + pStream->insert(topMostV); + pStream->end(PRIMITIVE_STREAM_FAN); + j=k+1; + topMostV = rightVerts[j-1]; + } + } + } +} + +static int chainConvex(vertexArray* inc_chain, Int inc_current, Int inc_end) +{ + Int i; + //if there are no more than 2 vertices, return 1 + if(inc_current >= inc_end-1) return 1; + for(i=inc_current; i<= inc_end-2; i++) + { + if(area(inc_chain->getVertex(i), inc_chain->getVertex(i+1), inc_chain->getVertex(i+2)) <0) + return 0; + } + return 1; +} + +static int chainConcave(vertexArray* dec_chain, Int dec_current, Int dec_end) +{ + Int i; + //if there are no more than 2 vertices, return 1 + if(dec_current >= dec_end -1) return 1; + for(i=dec_current; i<=dec_end-2; i++) + { + if(area(dec_chain->getVertex(i), dec_chain->getVertex(i+1), dec_chain->getVertex(i+2)) >0) + return 0; + } + return 1; +} + +void monoTriangulationRecGenInU(Real* topVertex, Real* botVertex, + vertexArray* inc_chain, Int inc_current, Int inc_end, + vertexArray* dec_chain, Int dec_current, Int dec_end, + primStream* pStream) +{ + +} + +void monoTriangulationRecGenOpt(Real* topVertex, Real* botVertex, + vertexArray* inc_chain, Int inc_current, Int inc_end, + vertexArray* dec_chain, Int dec_current, Int dec_end, + primStream* pStream) +{ + Int i; + //copy this to a polygon: directedLine Lioop + sampledLine* sline; + directedLine* dline; + directedLine* poly; + + if(inc_current <= inc_end) //at least one vertex in inc_chain + { + sline = new sampledLine(topVertex, inc_chain->getVertex(inc_current)); + poly = new directedLine(INCREASING, sline); + for(i=inc_current; i<=inc_end-1; i++) + { + sline = new sampledLine(inc_chain->getVertex(i), inc_chain->getVertex(i+1)); + dline = new directedLine(INCREASING, sline); + poly->insert(dline); + } + sline = new sampledLine(inc_chain->getVertex(inc_end), botVertex); + dline = new directedLine(INCREASING, sline); + poly->insert(dline); + } + else //inc_chian is empty + { + sline = new sampledLine(topVertex, botVertex); + dline = new directedLine(INCREASING, sline); + poly = dline; + } + + assert(poly != NULL); + + if(dec_current <= dec_end) //at least on vertex in dec_Chain + { + sline = new sampledLine(botVertex, dec_chain->getVertex(dec_end)); + dline = new directedLine(INCREASING, sline); + poly->insert(dline); + for(i=dec_end; i>dec_current; i--) + { + sline = new sampledLine(dec_chain->getVertex(i), dec_chain->getVertex(i-1)); + dline = new directedLine(INCREASING, sline); + poly->insert(dline); + } + sline = new sampledLine(dec_chain->getVertex(dec_current), topVertex); + dline = new directedLine(INCREASING, sline); + poly->insert(dline); + } + else //dec_chain is empty + { + sline = new sampledLine(botVertex, topVertex); + dline = new directedLine(INCREASING, sline); + poly->insert(dline); + } + + { + Int n_cusps; + Int n_edges = poly->numEdges(); + directedLine** cusps = (directedLine**) malloc(sizeof(directedLine*)*n_edges); + assert(cusps); + findInteriorCuspsX(poly, n_cusps, cusps); + + if(n_cusps ==0) //u monotine + { + monoTriangulationFun(poly, compV2InX, pStream); + } + else if(n_cusps == 1) // one interior cusp + { + directedLine* new_polygon = polygonConvert(cusps[0]); + directedLine* other = findDiagonal_singleCuspX(new_polygon); + //<other> should NOT be null unless there are self-intersecting + //trim curves. In that case, we don't want to core dump, instead, + //we triangulate anyway, and print out error message. + if(other == NULL) + { + monoTriangulationFun(poly, compV2InX, pStream); + } + else + { + directedLine* ret_p1; + directedLine* ret_p2; + + new_polygon->connectDiagonal_2slines(new_polygon, other, + &ret_p1, + &ret_p2, + new_polygon); + + monoTriangulationFun(ret_p1, compV2InX, pStream); + monoTriangulationFun(ret_p2, compV2InX, pStream); + + ret_p1->deleteSinglePolygonWithSline(); + ret_p2->deleteSinglePolygonWithSline(); + } + } + else + { + //we need a general partitionX funtion (supposed to be in partitionX.C, + //not implemented yet. XXX + //monoTriangulationFun(poly, compV2InY, pStream); + + directedLine* new_polygon = polygonConvert(poly); + directedLine* list = monoPolyPart(new_polygon); + for(directedLine* temp = list; temp != NULL; temp = temp->getNextPolygon()) + { + monoTriangulationFun(temp, compV2InX, pStream); + } + //clean up + list->deletePolygonListWithSline(); + + } + + free(cusps); + /* + if(numInteriorCuspsX(poly) == 0) //is u monotone + monoTriangulationFun(poly, compV2InX, pStream); + else //it is not u motone + monoTriangulationFun(poly, compV2InY, pStream); + */ + //clean up space + poly->deleteSinglePolygonWithSline(); + return; + } + + //apparently the following code is not reachable, + //it is for test purpose + if(inc_current > inc_end || dec_current>dec_end) + { + monoTriangulationRecGen(topVertex, botVertex, inc_chain, inc_current, inc_end, + dec_chain, dec_current, dec_end, + pStream); + return; + } + + + if( + area(dec_chain->getVertex(dec_current), + topVertex, + inc_chain->getVertex(inc_current)) >=0 + && chainConvex(inc_chain, inc_current, inc_end) + && chainConcave(dec_chain, dec_current, dec_end) + && area(inc_chain->getVertex(inc_end), botVertex, dec_chain->getVertex(dec_end)) >=0 + ) + { + monoTriangulationRecFunGen(topVertex, botVertex, + inc_chain, inc_current, inc_end, + dec_chain, dec_current, dec_end, + compV2InX, pStream); + } + else + { + monoTriangulationRecGen(topVertex, botVertex, inc_chain, inc_current, inc_end, + dec_chain, dec_current, dec_end, + pStream); + } +} + +/*if inc_current>inc_end, then inc_chain has no points to be considered + *same for dec_chain + */ +void monoTriangulationRecGen(Real* topVertex, Real* botVertex, + vertexArray* inc_chain, Int inc_current, Int inc_end, + vertexArray* dec_chain, Int dec_current, Int dec_end, + primStream* pStream) +{ + Real** inc_array ; + Real** dec_array ; + Int i; + + if(inc_current > inc_end && dec_current>dec_end) + return; + else if(inc_current>inc_end) /*no more vertices on inc_chain*/ + { + dec_array = dec_chain->getArray(); + reflexChain rChain(100,0); + /*put the top vertex into the reflex chain*/ + rChain.processNewVertex(topVertex, pStream); + /*process all the vertices on the dec_chain*/ + for(i=dec_current; i<=dec_end; i++){ + rChain.processNewVertex(dec_array[i], pStream); + } + /*process the bottom vertex*/ + rChain.processNewVertex(botVertex, pStream); + } + else if(dec_current> dec_end) /*no more vertices on dec_chain*/ + { + inc_array = inc_chain->getArray(); + + reflexChain rChain(100,1); + /*put the top vertex into the reflex chain*/ + rChain.processNewVertex(topVertex, pStream); + /*process all the vertices on the inc_chain*/ + for(i=inc_current; i<=inc_end; i++){ + rChain.processNewVertex(inc_array[i], pStream); + } + /*process the bottom vertex*/ + rChain.processNewVertex(botVertex, pStream); + } + else /*neither chain is empty*/ + { + inc_array = inc_chain -> getArray(); + dec_array = dec_chain -> getArray(); + + /*if top of inc_chain is 'lower' than top of dec_chain, process all the + *vertices on the dec_chain which are higher than top of inc_chain + */ + if(compV2InY(inc_array[inc_current], dec_array[dec_current]) <= 0) + { + + reflexChain rChain(100, 0); + rChain.processNewVertex(topVertex, pStream); + for(i=dec_current; i<=dec_end; i++) + { + if(compV2InY(inc_array[inc_current], dec_array[i]) <= 0) + rChain.processNewVertex(dec_array[i], pStream); + else + break; + } + rChain.outputFan(inc_array[inc_current], pStream); + monoTriangulationRecGen(dec_array[i-1], botVertex, + inc_chain, inc_current, inc_end, + dec_chain, i, dec_end, + pStream); + } + else /*compV2InY(inc_array[inc_current], dec_array[dec_current]) > 0*/ + { + + reflexChain rChain(100, 1); + rChain.processNewVertex(topVertex, pStream); + for(i=inc_current; i<=inc_end; i++) + { + if(compV2InY(inc_array[i], dec_array[dec_current]) >0) + rChain.processNewVertex(inc_array[i], pStream); + else + break; + } + rChain.outputFan(dec_array[dec_current], pStream); + monoTriangulationRecGen(inc_array[i-1], botVertex, + inc_chain, i, inc_end, + dec_chain, dec_current,dec_end, + pStream); + } + }/*end case neither is empty*/ +} + +void monoTriangulationFun(directedLine* monoPolygon, Int (*compFun)(Real*, Real*), primStream* pStream) +{ + Int i; + /*find the top vertex, bottom vertex, inccreasing chain, and decreasing chain, + *then call monoTriangulationRec + */ + directedLine* tempV; + directedLine* topV; + directedLine* botV; + topV = botV = monoPolygon; + for(tempV = monoPolygon->getNext(); tempV != monoPolygon; tempV = tempV->getNext()) + { + if(compFun(topV->head(), tempV->head())<0) { + topV = tempV; + } + if(compFun(botV->head(), tempV->head())>0) { + botV = tempV; + } + } + + /*creat increase and decrease chains*/ + vertexArray inc_chain(20); /*this is a dynamic array*/ + for(i=1; i<=topV->get_npoints()-2; i++) { /*the first vertex is the top vertex which doesn't belong to inc_chain*/ + inc_chain.appendVertex(topV->getVertex(i)); + } + for(tempV = topV->getNext(); tempV != botV; tempV = tempV->getNext()) + { + for(i=0; i<=tempV->get_npoints()-2; i++){ + inc_chain.appendVertex(tempV->getVertex(i)); + } + } + + vertexArray dec_chain(20); + for(tempV = topV->getPrev(); tempV != botV; tempV = tempV->getPrev()) + { + for(i=tempV->get_npoints()-2; i>=0; i--){ + dec_chain.appendVertex(tempV->getVertex(i)); + } + } + for(i=botV->get_npoints()-2; i>=1; i--){ + dec_chain.appendVertex(tempV->getVertex(i)); + } + + if (!(0 == inc_chain.getNumElements() && 0 == dec_chain.getNumElements())) { + monoTriangulationRecFun(topV->head(), botV->head(), &inc_chain, 0, + &dec_chain, 0, compFun, pStream); + } +} + +void monoTriangulation(directedLine* monoPolygon, primStream* pStream) +{ + Int i; + /*find the top vertex, bottom vertex, inccreasing chain, and decreasing chain, + *then call monoTriangulationRec + */ + directedLine* tempV; + directedLine* topV; + directedLine* botV; + topV = botV = monoPolygon; + for(tempV = monoPolygon->getNext(); tempV != monoPolygon; tempV = tempV->getNext()) + { + if(compV2InY(topV->head(), tempV->head())<0) { + topV = tempV; + } + if(compV2InY(botV->head(), tempV->head())>0) { + botV = tempV; + } + } + /*creat increase and decrease chains*/ + vertexArray inc_chain(20); /*this is a dynamic array*/ + for(i=1; i<=topV->get_npoints()-2; i++) { /*the first vertex is the top vertex which doesn't belong to inc_chain*/ + inc_chain.appendVertex(topV->getVertex(i)); + } + for(tempV = topV->getNext(); tempV != botV; tempV = tempV->getNext()) + { + for(i=0; i<=tempV->get_npoints()-2; i++){ + inc_chain.appendVertex(tempV->getVertex(i)); + } + } + + vertexArray dec_chain(20); + for(tempV = topV->getPrev(); tempV != botV; tempV = tempV->getPrev()) + { + for(i=tempV->get_npoints()-2; i>=0; i--){ + dec_chain.appendVertex(tempV->getVertex(i)); + } + } + for(i=botV->get_npoints()-2; i>=1; i--){ + dec_chain.appendVertex(tempV->getVertex(i)); + } + + monoTriangulationRec(topV->head(), botV->head(), &inc_chain, 0, &dec_chain, 0, pStream); + +} + +/*the chain could be increasing or decreasing, although we use the + * name inc_chain. + *the argument is_increase_chain indicates whether this chain + *is increasing (left chain in V-monotone case) or decreaing (right chain + *in V-monotone case). + */ +void monoTriangulation2(Real* topVertex, Real* botVertex, + vertexArray* inc_chain, Int inc_smallIndex, + Int inc_largeIndex, + Int is_increase_chain, + primStream* pStream) +{ + assert( inc_chain != NULL); + Real** inc_array ; + + if(inc_smallIndex > inc_largeIndex) + return; //no triangles + if(inc_smallIndex == inc_largeIndex) + { + if(is_increase_chain) + pStream->triangle(inc_chain->getVertex(inc_smallIndex), botVertex, topVertex); + else + pStream->triangle(inc_chain->getVertex(inc_smallIndex), topVertex, botVertex); + return; + } + Int i; + + if(is_increase_chain && botVertex[1] == inc_chain->getVertex(inc_largeIndex)[1]) + { + pStream->triangle(botVertex, inc_chain->getVertex(inc_largeIndex-1), + inc_chain->getVertex(inc_largeIndex)); + monoTriangulation2(topVertex, botVertex, inc_chain, inc_smallIndex, + inc_largeIndex-1, + is_increase_chain, + pStream); + return; + } + else if( (!is_increase_chain) && topVertex[1] == inc_chain->getVertex(inc_smallIndex)[1]) + { + pStream->triangle(topVertex, inc_chain->getVertex(inc_smallIndex+1), + inc_chain->getVertex(inc_smallIndex)); + monoTriangulation2(topVertex, botVertex, inc_chain, inc_smallIndex+1, + inc_largeIndex, is_increase_chain, pStream); + return ; + } + + inc_array = inc_chain->getArray(); + + reflexChain rChain(20,is_increase_chain); /*1 means the chain is increasing*/ + + rChain.processNewVertex(topVertex, pStream); + + for(i=inc_smallIndex; i<=inc_largeIndex; i++){ + rChain.processNewVertex(inc_array[i], pStream); + } + rChain.processNewVertex(botVertex, pStream); + +} + +/*if compFun == compV2InY, top to bottom: V-monotone + *if compFun == compV2InX, right to left: U-monotone + */ +void monoTriangulationRecFunGen(Real* topVertex, Real* botVertex, + vertexArray* inc_chain, Int inc_current, Int inc_end, + vertexArray* dec_chain, Int dec_current, Int dec_end, + Int (*compFun)(Real*, Real*), + primStream* pStream) +{ + assert( inc_chain != NULL && dec_chain != NULL); + assert( ! (inc_current> inc_end && + dec_current> dec_end)); + /* + Int inc_nVertices; + Int dec_nVertices; + */ + Real** inc_array ; + Real** dec_array ; + Int i; + assert( ! ( (inc_chain==NULL) && (dec_chain==NULL))); + + if(inc_current> inc_end) /*no more vertices on inc_chain*/ + { + + dec_array = dec_chain->getArray(); + reflexChain rChain(20,0); + /*put the top vertex into the reflex chain*/ + rChain.processNewVertex(topVertex, pStream); + /*process all the vertices on the dec_chain*/ + for(i=dec_current; i<=dec_end; i++){ + rChain.processNewVertex(dec_array[i], pStream); + } + /*process the bottom vertex*/ + rChain.processNewVertex(botVertex, pStream); + + } + else if(dec_current> dec_end) /*no more vertices on dec_chain*/ + { + inc_array = inc_chain->getArray(); + reflexChain rChain(20,1); + /*put the top vertex into the reflex chain*/ + rChain.processNewVertex(topVertex, pStream); + /*process all the vertices on the inc_chain*/ + for(i=inc_current; i<=inc_end; i++){ + rChain.processNewVertex(inc_array[i], pStream); + } + /*process the bottom vertex*/ + rChain.processNewVertex(botVertex, pStream); + } + else /*neither chain is empty*/ + { + inc_array = inc_chain -> getArray(); + dec_array = dec_chain -> getArray(); + + /*if top of inc_chain is 'lower' than top of dec_chain, process all the + *vertices on the dec_chain which are higher than top of inc_chain + */ + if(compFun(inc_array[inc_current], dec_array[dec_current]) <= 0) + { + + reflexChain rChain(20, 0); + rChain.processNewVertex(topVertex, pStream); + for(i=dec_current; i<=dec_end; i++) + { + if(compFun(inc_array[inc_current], dec_array[i]) <= 0) + rChain.processNewVertex(dec_array[i], pStream); + else + break; + } + rChain.outputFan(inc_array[inc_current], pStream); + monoTriangulationRecFunGen(dec_array[i-1], botVertex, + inc_chain, inc_current, inc_end, + dec_chain, i, dec_end, + compFun, + pStream); + } + else /*compFun(inc_array[inc_current], dec_array[dec_current]) > 0*/ + { + + reflexChain rChain(20, 1); + rChain.processNewVertex(topVertex, pStream); + for(i=inc_current; i<=inc_end; i++) + { + if(compFun(inc_array[i], dec_array[dec_current]) >0) + rChain.processNewVertex(inc_array[i], pStream); + else + break; + } + rChain.outputFan(dec_array[dec_current], pStream); + monoTriangulationRecFunGen(inc_array[i-1], botVertex, + inc_chain, i,inc_end, + dec_chain, dec_current,dec_end, + compFun, + pStream); + } + }/*end case neither is empty*/ +} + +/*if compFun == compV2InY, top to bottom: V-monotone + *if compFun == compV2InX, right to left: U-monotone + */ +void monoTriangulationRecFun(Real* topVertex, Real* botVertex, + vertexArray* inc_chain, Int inc_current, + vertexArray* dec_chain, Int dec_current, + Int (*compFun)(Real*, Real*), + primStream* pStream) +{ + assert( inc_chain != NULL && dec_chain != NULL); + assert( ! (inc_current>=inc_chain->getNumElements() && + dec_current>=dec_chain->getNumElements())); + Int inc_nVertices; + Int dec_nVertices; + Real** inc_array ; + Real** dec_array ; + Int i; + assert( ! ( (inc_chain==NULL) && (dec_chain==NULL))); + + if(inc_current>=inc_chain->getNumElements()) /*no more vertices on inc_chain*/ + { + + dec_array = dec_chain->getArray(); + dec_nVertices = dec_chain->getNumElements(); + reflexChain rChain(20,0); + /*put the top vertex into the reflex chain*/ + rChain.processNewVertex(topVertex, pStream); + /*process all the vertices on the dec_chain*/ + for(i=dec_current; i<dec_nVertices; i++){ + rChain.processNewVertex(dec_array[i], pStream); + } + /*process the bottom vertex*/ + rChain.processNewVertex(botVertex, pStream); + + } + else if(dec_current>= dec_chain->getNumElements()) /*no more vertices on dec_chain*/ + { + inc_array = inc_chain->getArray(); + inc_nVertices= inc_chain->getNumElements(); + reflexChain rChain(20,1); + /*put the top vertex into the reflex chain*/ + rChain.processNewVertex(topVertex, pStream); + /*process all the vertices on the inc_chain*/ + for(i=inc_current; i<inc_nVertices; i++){ + rChain.processNewVertex(inc_array[i], pStream); + } + /*process the bottom vertex*/ + rChain.processNewVertex(botVertex, pStream); + } + else /*neither chain is empty*/ + { + inc_array = inc_chain -> getArray(); + dec_array = dec_chain -> getArray(); + inc_nVertices= inc_chain->getNumElements(); + dec_nVertices= dec_chain->getNumElements(); + /*if top of inc_chain is 'lower' than top of dec_chain, process all the + *vertices on the dec_chain which are higher than top of inc_chain + */ + if(compFun(inc_array[inc_current], dec_array[dec_current]) <= 0) + { + + reflexChain rChain(20, 0); + rChain.processNewVertex(topVertex, pStream); + for(i=dec_current; i<dec_nVertices; i++) + { + if(compFun(inc_array[inc_current], dec_array[i]) <= 0) + rChain.processNewVertex(dec_array[i], pStream); + else + break; + } + rChain.outputFan(inc_array[inc_current], pStream); + monoTriangulationRecFun(dec_array[i-1], botVertex, + inc_chain, inc_current, + dec_chain, i, + compFun, + pStream); + } + else /*compFun(inc_array[inc_current], dec_array[dec_current]) > 0*/ + { + + reflexChain rChain(20, 1); + rChain.processNewVertex(topVertex, pStream); + for(i=inc_current; i<inc_nVertices; i++) + { + if(compFun(inc_array[i], dec_array[dec_current]) >0) + rChain.processNewVertex(inc_array[i], pStream); + else + break; + } + rChain.outputFan(dec_array[dec_current], pStream); + monoTriangulationRecFun(inc_array[i-1], botVertex, + inc_chain, i, + dec_chain, dec_current, + compFun, + pStream); + } + }/*end case neither is empty*/ +} + + +void monoTriangulationRec(Real* topVertex, Real* botVertex, + vertexArray* inc_chain, Int inc_current, + vertexArray* dec_chain, Int dec_current, + primStream* pStream) +{ + assert( inc_chain != NULL && dec_chain != NULL); + assert( ! (inc_current>=inc_chain->getNumElements() && + dec_current>=dec_chain->getNumElements())); + Int inc_nVertices; + Int dec_nVertices; + Real** inc_array ; + Real** dec_array ; + Int i; + assert( ! ( (inc_chain==NULL) && (dec_chain==NULL))); + + if(inc_current>=inc_chain->getNumElements()) /*no more vertices on inc_chain*/ + { + + dec_array = dec_chain->getArray(); + dec_nVertices = dec_chain->getNumElements(); + reflexChain rChain(20,0); + /*put the top vertex into the reflex chain*/ + rChain.processNewVertex(topVertex, pStream); + /*process all the vertices on the dec_chain*/ + for(i=dec_current; i<dec_nVertices; i++){ + rChain.processNewVertex(dec_array[i], pStream); + } + /*process the bottom vertex*/ + rChain.processNewVertex(botVertex, pStream); + + } + else if(dec_current>= dec_chain->getNumElements()) /*no more vertices on dec_chain*/ + { + inc_array = inc_chain->getArray(); + inc_nVertices= inc_chain->getNumElements(); + reflexChain rChain(20,1); + /*put the top vertex into the reflex chain*/ + rChain.processNewVertex(topVertex, pStream); + /*process all the vertices on the inc_chain*/ + for(i=inc_current; i<inc_nVertices; i++){ + rChain.processNewVertex(inc_array[i], pStream); + } + /*process the bottom vertex*/ + rChain.processNewVertex(botVertex, pStream); + } + else /*neither chain is empty*/ + { + inc_array = inc_chain -> getArray(); + dec_array = dec_chain -> getArray(); + inc_nVertices= inc_chain->getNumElements(); + dec_nVertices= dec_chain->getNumElements(); + /*if top of inc_chain is 'lower' than top of dec_chain, process all the + *vertices on the dec_chain which are higher than top of inc_chain + */ + if(compV2InY(inc_array[inc_current], dec_array[dec_current]) <= 0) + { + + reflexChain rChain(20, 0); + rChain.processNewVertex(topVertex, pStream); + for(i=dec_current; i<dec_nVertices; i++) + { + if(compV2InY(inc_array[inc_current], dec_array[i]) <= 0) + rChain.processNewVertex(dec_array[i], pStream); + else + break; + } + rChain.outputFan(inc_array[inc_current], pStream); + monoTriangulationRec(dec_array[i-1], botVertex, + inc_chain, inc_current, + dec_chain, i, + pStream); + } + else /*compV2InY(inc_array[inc_current], dec_array[dec_current]) > 0*/ + { + + reflexChain rChain(20, 1); + rChain.processNewVertex(topVertex, pStream); + for(i=inc_current; i<inc_nVertices; i++) + { + if(compV2InY(inc_array[i], dec_array[dec_current]) >0) + rChain.processNewVertex(inc_array[i], pStream); + else + break; + } + rChain.outputFan(dec_array[dec_current], pStream); + monoTriangulationRec(inc_array[i-1], botVertex, + inc_chain, i, + dec_chain, dec_current, + pStream); + } + }/*end case neither is empty*/ +} + + + +/* the name here assumes that the polygon is Y-monotone, but + *this function also works for X-monotone polygons. + * a monotne polygon consists of two extrem verteices: topVertex and botVertex, and + *two monotone chains: inc_chain, and dec_chain. The edges of the increasing chain (inc_chain) + *is ordered by following pointer: next, while the edges of the decreasing chain (dec_chain) + *is ordered by following pointer: prev + * inc_index index the vertex which is the toppest of the inc_chain which we are handling currently. + * dec_index index the vertex which is the toppest of the dec_chain which we are handling currently. + */ +void monoTriangulationRec(directedLine* inc_chain, Int inc_index, + directedLine* dec_chain, Int dec_index, + directedLine* topVertex, Int top_index, + directedLine* botVertex, + primStream* pStream) +{ + Int i; + directedLine *temp, *oldtemp = NULL; + Int tempIndex, oldtempIndex = 0; + + assert(inc_chain != NULL && dec_chain != NULL); + + if(inc_chain == botVertex) { + reflexChain rChain(20, 0); + rChain.processNewVertex(topVertex->getVertex(top_index), pStream); + for(i=dec_index; i< dec_chain->get_npoints(); i++){ + rChain.processNewVertex(dec_chain->getVertex(i), pStream); + } + for(temp = dec_chain->getPrev(); temp != botVertex; temp = temp->getPrev()) + { + for(i=0; i<temp->get_npoints(); i++){ + rChain.processNewVertex(temp->getVertex(i), pStream); + } + } + } + else if(dec_chain==botVertex) { + reflexChain rChain(20, 1); + rChain.processNewVertex(topVertex->getVertex(top_index), pStream); + for(i=inc_index; i< inc_chain->get_npoints(); i++){ + rChain.processNewVertex(inc_chain->getVertex(i), pStream); + } + for(temp = inc_chain->getPrev(); temp != botVertex; temp = temp->getNext()) + { + for(i=0; i<temp->get_npoints(); i++){ + rChain.processNewVertex(temp->getVertex(i), pStream); + } + } + } + else /*neither reached the bottom*/{ + if(compV2InY(inc_chain->getVertex(inc_index), dec_chain->getVertex(dec_index)) <=0) { + reflexChain rChain(20, 0); + rChain.processNewVertex(topVertex -> getVertex(top_index), pStream); + temp = dec_chain; + tempIndex = dec_index; + while( compV2InY(inc_chain->getVertex(inc_index), temp->getVertex(tempIndex))<=0) { + oldtemp = temp; + oldtempIndex = tempIndex; + rChain.processNewVertex(temp->getVertex(tempIndex), pStream); + + if(tempIndex == temp->get_npoints()-1){ + tempIndex = 0; + temp = temp->getPrev(); + } + else{ + tempIndex++; + } + } + rChain.outputFan(inc_chain->getVertex(inc_index), pStream); + monoTriangulationRec(inc_chain, inc_index, temp, tempIndex, oldtemp, oldtempIndex, botVertex, pStream); + } + else /* >0*/ { + reflexChain rChain(20, 1); + rChain.processNewVertex(topVertex -> getVertex(top_index), pStream); + temp = inc_chain; + tempIndex = inc_index; + while( compV2InY(temp->getVertex(tempIndex), dec_chain->getVertex(dec_index))>0){ + oldtemp = temp; + oldtempIndex = tempIndex; + rChain.processNewVertex(temp->getVertex(tempIndex), pStream); + + if(tempIndex == temp->get_npoints()-1){ + tempIndex = 0; + temp = temp->getNext(); + } + else{ + tempIndex++; + } + } + rChain.outputFan(dec_chain->getVertex(dec_index), pStream); + monoTriangulationRec(temp, tempIndex, dec_chain, dec_index, oldtemp, oldtempIndex, botVertex, pStream); + } + } /*end case neither reached the bottom*/ +} + +/***************************vertexArray begin here**********************************/ +vertexArray::vertexArray(Real2* vertices, Int nVertices) +{ + Int i; + size = index = nVertices; + array = (Real**) malloc(sizeof(Real*) * nVertices); + assert(array); + for(i=0; i<nVertices; i++) + { + array[i] = vertices[i]; + array[i] = vertices[i]; + } +} + +vertexArray::vertexArray(Int s) +{ + size = s; + array = (Real**) malloc(sizeof(Real*) * s); + assert(array); + index = 0; +} + +vertexArray::~vertexArray() +{ + free(array); +} + +void vertexArray::appendVertex(Real* ptr) +{ + Int i; + if(index >= size){ + Real** temp = (Real**) malloc(sizeof(Real*) * (2*size +1)); + assert(temp); + for(i=0; i<index; i++) + temp[i] = array[i]; + free(array); + array = temp; + size = 2*size+1; + } + array[index++] = ptr; +} + +void vertexArray::print() +{ + printf("vertex Array:index=%i, size=%i\n", index, size); + for(Int i=0; i<index; i++) + { + printf("(%f,%f) ", array[i][0], array[i][1]); + } + printf("\n"); +} + +/*find the first i such that array[i][1] >= v + * and array[i+1][1] <v + * if index == 0 (the array is empty, return -1. + * if v is above all, return -1. + * if v is below all, return index-1. + */ +Int vertexArray::findIndexAbove(Real v) +{ + Int i; + if(index == 0) + return -1; + else if(array[0][1] < v) + return -1; + else + { + for(i=1; i<index; i++) + { + if(array[i][1] < v) + break; + } + return i-1; + } +} + +/*find the first i<=endIndex such that array[i][1] <= v + * and array[i-1][1] > v + *if sartIndex>endIndex, then return endIndex+1. + *otherwise, startIndex<=endIndex, it is assumed that + * 0<=startIndex<=endIndex<index. + * if v is below all, return endIndex+1 + * if v is above all, return startIndex. + */ +Int vertexArray::findIndexBelowGen(Real v, Int startIndex, Int endIndex) +{ + Int i; + if(startIndex > endIndex) + return endIndex+1; + else if(array[endIndex][1] > v) + return endIndex+1; + else //now array[endIndex][1] <= v + { + for(i=endIndex-1; i>=startIndex; i--) + { + if(array[i][1] > v) + break; + } + return i+1; + } +} + +/*find the first i<=endIndex such that array[i-1][1] >= v + * and array[i][1] < v + *if sartIndex>endIndex, then return endIndex+1. + *otherwise, startIndex<=endIndex, it is assumed that + * 0<=startIndex<=endIndex<index. + * if v is below or equal to all, return endIndex+1 + * if v is strictly above all, return startIndex. + */ +Int vertexArray::findIndexStrictBelowGen(Real v, Int startIndex, Int endIndex) +{ + Int i; + if(startIndex > endIndex) + return endIndex+1; + else if(array[endIndex][1] >= v) + return endIndex+1; + else //now array[endIndex][1] < v + { + for(i=endIndex-1; i>=startIndex; i--) + { + if(array[i][1] >= v) + break; + } + return i+1; + } +} + +/*find the first i>startIndex such that array[i-1][1] > v + * and array[i][1] >=v + *if sartIndex>endIndex, then return startIndex-1. + *otherwise, startIndex<=endIndex, it is assumed that + * 0<=startIndex<=endIndex<index. + * if v is strictly above all, return startIndex-1 + * if v is strictly below all, return endIndex. + */ +Int vertexArray::findIndexFirstAboveEqualGen(Real v, Int startIndex, Int endIndex) +{ + + Int i; + if(startIndex > endIndex) + return startIndex-1; + else if(array[startIndex][1] < v) + return startIndex-1; + else //now array[startIndex][1] >= v + { + + for(i=startIndex; i<=endIndex; i++) + { + if(array[i][1] <= v) + break; + } + if(i>endIndex) // v is strictly below all + return endIndex; + else if(array[i][1] == v) + return i; + else + return i-1; + } + +} + + +/*find the first i>=startIndex such that array[i][1] >= v + * and array[i+1][1] <v + *if sartIndex>endIndex, then return startIndex-1. + *otherwise, startIndex<=endIndex, it is assumed that + * 0<=startIndex<=endIndex<index. + * if v is above all, return startIndex-1 + * if v is below all, return endIndex. + */ +Int vertexArray::findIndexAboveGen(Real v, Int startIndex, Int endIndex) +{ + Int i; + if(startIndex > endIndex) + return startIndex-1; + else if(array[startIndex][1] < v) + return startIndex-1; + else //now array[startIndex][1] >= v + { + for(i=startIndex+1; i<=endIndex; i++) + { + if(array[i][1] < v) + break; + } + return i-1; + } +} + +Int vertexArray::findDecreaseChainFromEnd(Int begin, Int end) +{ + Int i = end; + Real prevU = array[i][0]; + Real thisU; + for(i=end-1; i>=begin; i--){ + thisU = array[i][0]; + if(thisU < prevU) + prevU = thisU; + else + break; + } + return i; +} + +//if(V(start) == v, return start, other wise return the +//last i so that V(i)==v +Int vertexArray::skipEqualityFromStart(Real v, Int start, Int end) +{ + Int i; + if(array[start][1] != v) + return start; + //now array[start][1] == v + for(i=start+1; i<= end; i++) + if(array[i][1] != v) + break; + return i-1; +} + + +/***************************vertexArray end****************************************/ + + + +/***************************relfex chain stuff begin here*****************************/ + +reflexChain::reflexChain(Int size, Int is_increasing) +{ + queue = (Real2*) malloc(sizeof(Real2) * size); + assert(queue); + index_queue = 0; + size_queue = size; + isIncreasing = is_increasing; +} + +reflexChain::~reflexChain() +{ + free(queue); +} + +/*put (u,v) at the end of the queue + *pay attention to space + */ +void reflexChain::insert(Real u, Real v) +{ + Int i; + if(index_queue >= size_queue) { + Real2 *temp = (Real2*) malloc(sizeof(Real2) * (2*size_queue+1)); + assert(temp); + + /*copy*/ + for(i=0; i<index_queue; i++){ + temp[i][0] = queue[i][0]; + temp[i][1] = queue[i][1]; + } + + free(queue); + queue = temp; + size_queue = 2*size_queue + 1; + } + + queue[index_queue][0] = u; + queue[index_queue][1] = v; + index_queue ++; +} + +void reflexChain::insert(Real v[2]) +{ + insert(v[0], v[1]); +} + +/* +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; +} +*/ + +/*the chain is reflex, and the vertex v is + *on the other side of the chain, so that + *we can outout the fan with v as the + *the center + */ +void reflexChain::outputFan(Real v[2], primStream* pStream) +{ + Int i; + pStream->begin(); + pStream->insert(v); + if(isIncreasing) { + for(i=0; i<index_queue; i++) + pStream->insert(queue[i]); + } + else { + for(i=index_queue-1; i>=0; i--) + pStream->insert(queue[i]); + } + pStream->end(PRIMITIVE_STREAM_FAN); +} + +void reflexChain::processNewVertex(Real v[2], primStream* pStream) +{ + Int i,j,k; + Int isReflex; + /*if there are at most one vertex in the queue, then simply insert + */ + if(index_queue <=1){ + insert(v); + return; + } + + /*there are at least two vertices in the queue*/ + j=index_queue-1; + + for(i=j; i>=1; i--) { + if(isIncreasing) { + isReflex = (area(queue[i-1], queue[i], v) <= 0.0); + } + else /*decreasing*/{ + isReflex = (area(v, queue[i], queue[i-1]) <= 0.0); + } + if(isReflex) { + break; + } + } + + /* + *if i<j then vertices: i+1--j are convex + * output triangle fan: + * v, and queue[i], i+1, ..., j + */ + if(i<j) + { + pStream->begin(); + pStream->insert(v); + if(isIncreasing) { + for(k=i; k<=j; k++) + pStream->insert(queue[k]); + } + else { + for(k=j; k>=i; k--) + pStream->insert(queue[k]); + } + + pStream->end(PRIMITIVE_STREAM_FAN); + } + + /*delete vertices i+1--j from the queue*/ + index_queue = i+1; + /*finally insert v at the end of the queue*/ + insert(v); + +} + +void reflexChain::print() +{ + Int i; + printf("reflex chain: isIncreasing=%i\n", isIncreasing); + for(i=0; i<index_queue; i++) { + printf("(%f,%f) ", queue[i][0], queue[i][1]); + } + printf("\n"); +} |