| /* |
| ** 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. |
| ** |
| ** $Date: 2012/03/29 17:22:17 $ $Revision: 1.1.1.1 $ |
| */ |
| /* |
| ** $Header: /cvs/bao-parsec/pkgs/libs/mesa/src/src/glu/sgi/libnurbs/nurbtess/monoTriangulation.cc,v 1.1.1.1 2012/03/29 17:22:17 uid42307 Exp $ |
| */ |
| |
| #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"); |
| } |