/* ** 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 #include #include #ifndef max #define max(a,b) ((a>b)? a:b) #endif #ifndef min #define min(a,b) ((a>b)? b:a) #endif #include #include "glimports.h" #include "zlassert.h" #include "sampleMonoPoly.h" #include "sampleComp.h" #include "polyDBG.h" #include "partitionX.h" #define ZERO 0.00001 //#define MYDEBUG //#define SHORTEN_GRID_LINE //see work/newtess/internal/test/problems /*split a polygon so that each vertex correcpond to one edge *the head of the first edge of the returned plygon must be the head of the first *edge of the origianl polygon. This is crucial for the code in sampleMonoPoly function */ directedLine* polygonConvert(directedLine* polygon) { int i; directedLine* ret; sampledLine* sline; sline = new sampledLine(2); sline->setPoint(0, polygon->getVertex(0)); sline->setPoint(1, polygon->getVertex(1)); ret=new directedLine(INCREASING, sline); for(i=1; i<= polygon->get_npoints()-2; i++) { sline = new sampledLine(2); sline->setPoint(0, polygon->getVertex(i)); sline->setPoint(1, polygon->getVertex(i+1)); ret->insert(new directedLine(INCREASING, sline)); } for(directedLine *temp = polygon->getNext(); temp != polygon; temp = temp->getNext()) { for(i=0; i<= temp->get_npoints()-2; i++) { sline = new sampledLine(2); sline->setPoint(0, temp->getVertex(i)); sline->setPoint(1, temp->getVertex(i+1)); ret->insert(new directedLine(INCREASING, sline)); } } return ret; } void triangulateConvexPolyVertical(directedLine* topV, directedLine* botV, primStream *pStream) { Int i,j; Int n_leftVerts; Int n_rightVerts; Real** leftVerts; Real** rightVerts; directedLine* tempV; n_leftVerts = 0; for(tempV = topV; tempV != botV; tempV = tempV->getNext()) { n_leftVerts += tempV->get_npoints(); } n_rightVerts=0; for(tempV = botV; tempV != topV; tempV = tempV->getNext()) { n_rightVerts += tempV->get_npoints(); } Real2* temp_leftVerts = (Real2 *) malloc(sizeof(Real2) * n_leftVerts); assert(temp_leftVerts); Real2* temp_rightVerts = (Real2 *) malloc(sizeof(Real2) * n_rightVerts); assert(temp_rightVerts); leftVerts = (Real**) malloc(sizeof(Real2*) * n_leftVerts); assert(leftVerts); rightVerts = (Real**) malloc(sizeof(Real2*) * n_rightVerts); assert(rightVerts); for(i=0; igetNext()) { for(j=1; jget_npoints(); j++) { leftVerts[i][0] = tempV->getVertex(j)[0]; leftVerts[i][1] = tempV->getVertex(j)[1]; i++; } } n_leftVerts = i; i=0; for(tempV = topV->getPrev(); tempV != botV->getPrev(); tempV = tempV->getPrev()) { for(j=tempV->get_npoints()-1; j>=1; j--) { rightVerts[i][0] = tempV->getVertex(j)[0]; rightVerts[i][1] = tempV->getVertex(j)[1]; i++; } } n_rightVerts = i; triangulateXYMonoTB(n_leftVerts, leftVerts, n_rightVerts, rightVerts, pStream); free(leftVerts); free(rightVerts); free(temp_leftVerts); free(temp_rightVerts); } void triangulateConvexPolyHoriz(directedLine* leftV, directedLine* rightV, primStream *pStream) { Int i,j; Int n_lowerVerts; Int n_upperVerts; Real2 *lowerVerts; Real2 *upperVerts; directedLine* tempV; n_lowerVerts=0; for(tempV = leftV; tempV != rightV; tempV = tempV->getNext()) { n_lowerVerts += tempV->get_npoints(); } n_upperVerts=0; for(tempV = rightV; tempV != leftV; tempV = tempV->getNext()) { n_upperVerts += tempV->get_npoints(); } lowerVerts = (Real2 *) malloc(sizeof(Real2) * n_lowerVerts); assert(n_lowerVerts); upperVerts = (Real2 *) malloc(sizeof(Real2) * n_upperVerts); assert(n_upperVerts); i=0; for(tempV = leftV; tempV != rightV; tempV = tempV->getNext()) { for(j=0; jget_npoints(); j++) { lowerVerts[i][0] = tempV->getVertex(j)[0]; lowerVerts[i][1] = tempV->getVertex(j)[1]; i++; } } i=0; for(tempV = leftV->getPrev(); tempV != rightV->getPrev(); tempV = tempV->getPrev()) { for(j=tempV->get_npoints()-1; j>=0; j--) { upperVerts[i][0] = tempV->getVertex(j)[0]; upperVerts[i][1] = tempV->getVertex(j)[1]; i++; } } triangulateXYMono(n_upperVerts, upperVerts, n_lowerVerts, lowerVerts, pStream); free(lowerVerts); free(upperVerts); } void triangulateConvexPoly(directedLine* polygon, Int ulinear, Int vlinear, primStream* pStream) { /*find left, right, top , bot */ directedLine* tempV; directedLine* topV; directedLine* botV; directedLine* leftV; directedLine* rightV; topV = botV = polygon; for(tempV = polygon->getNext(); tempV != polygon; tempV = tempV->getNext()) { if(compV2InY(topV->head(), tempV->head())<0) { topV = tempV; } if(compV2InY(botV->head(), tempV->head())>0) { botV = tempV; } } //find leftV for(tempV = topV; tempV != botV; tempV = tempV->getNext()) { if(tempV->tail()[0] >= tempV->head()[0]) break; } leftV = tempV; //find rightV for(tempV = botV; tempV != topV; tempV = tempV->getNext()) { if(tempV->tail()[0] <= tempV->head()[0]) break; } rightV = tempV; if(vlinear) { triangulateConvexPolyHoriz( leftV, rightV, pStream); } else if(ulinear) { triangulateConvexPolyVertical(topV, botV, pStream); } else { if(DBG_is_U_direction(polygon)) { triangulateConvexPolyHoriz( leftV, rightV, pStream); } else triangulateConvexPolyVertical(topV, botV, pStream); } } /*for debug purpose*/ void drawCorners( Real* topV, Real* botV, vertexArray* leftChain, vertexArray* rightChain, gridBoundaryChain* leftGridChain, gridBoundaryChain* rightGridChain, Int gridIndex1, Int gridIndex2, Int leftCornerWhere, Int leftCornerIndex, Int rightCornerWhere, Int rightCornerIndex, Int bot_leftCornerWhere, Int bot_leftCornerIndex, Int bot_rightCornerWhere, Int bot_rightCornerIndex) { Real* leftCornerV; Real* rightCornerV; Real* bot_leftCornerV; Real* bot_rightCornerV; if(leftCornerWhere == 1) leftCornerV = topV; else if(leftCornerWhere == 0) leftCornerV = leftChain->getVertex(leftCornerIndex); else leftCornerV = rightChain->getVertex(leftCornerIndex); if(rightCornerWhere == 1) rightCornerV = topV; else if(rightCornerWhere == 0) rightCornerV = leftChain->getVertex(rightCornerIndex); else rightCornerV = rightChain->getVertex(rightCornerIndex); if(bot_leftCornerWhere == 1) bot_leftCornerV = botV; else if(bot_leftCornerWhere == 0) bot_leftCornerV = leftChain->getVertex(bot_leftCornerIndex); else bot_leftCornerV = rightChain->getVertex(bot_leftCornerIndex); if(bot_rightCornerWhere == 1) bot_rightCornerV = botV; else if(bot_rightCornerWhere == 0) bot_rightCornerV = leftChain->getVertex(bot_rightCornerIndex); else bot_rightCornerV = rightChain->getVertex(bot_rightCornerIndex); Real topGridV = leftGridChain->get_v_value(gridIndex1); Real topGridU1 = leftGridChain->get_u_value(gridIndex1); Real topGridU2 = rightGridChain->get_u_value(gridIndex1); Real botGridV = leftGridChain->get_v_value(gridIndex2); Real botGridU1 = leftGridChain->get_u_value(gridIndex2); Real botGridU2 = rightGridChain->get_u_value(gridIndex2); glBegin(GL_LINE_STRIP); glVertex2fv(leftCornerV); glVertex2f(topGridU1, topGridV); glEnd(); glBegin(GL_LINE_STRIP); glVertex2fv(rightCornerV); glVertex2f(topGridU2, topGridV); glEnd(); glBegin(GL_LINE_STRIP); glVertex2fv(bot_leftCornerV); glVertex2f(botGridU1, botGridV); glEnd(); glBegin(GL_LINE_STRIP); glVertex2fv(bot_rightCornerV); glVertex2f(botGridU2, botGridV); glEnd(); } void toVertexArrays(directedLine* topV, directedLine* botV, vertexArray& leftChain, vertexArray& rightChain) { Int i; directedLine* tempV; for(i=1; i<=topV->get_npoints()-2; i++) { /*the first vertex is the top vertex which doesn't belong to inc_chain*/ leftChain.appendVertex(topV->getVertex(i)); } for(tempV = topV->getNext(); tempV != botV; tempV = tempV->getNext()) { for(i=0; i<=tempV->get_npoints()-2; i++){ leftChain.appendVertex(tempV->getVertex(i)); } } for(tempV = topV->getPrev(); tempV != botV; tempV = tempV->getPrev()) { for(i=tempV->get_npoints()-2; i>=0; i--){ rightChain.appendVertex(tempV->getVertex(i)); } } for(i=botV->get_npoints()-2; i>=1; i--){ rightChain.appendVertex(tempV->getVertex(i)); } } void findTopAndBot(directedLine* polygon, directedLine*& topV, directedLine*& botV) { assert(polygon); directedLine* tempV; topV = botV = polygon; for(tempV = polygon->getNext(); tempV != polygon; tempV = tempV->getNext()) { if(compV2InY(topV->head(), tempV->head())<0) { topV = tempV; } if(compV2InY(botV->head(), tempV->head())>0) { botV = tempV; } } } void findGridChains(directedLine* topV, directedLine* botV, gridWrap* grid, gridBoundaryChain*& leftGridChain, gridBoundaryChain*& rightGridChain) { /*find the first(top) and the last (bottom) grid line which intersect the *this polygon */ Int firstGridIndex; /*the index in the grid*/ Int lastGridIndex; firstGridIndex = (Int) ((topV->head()[1] - grid->get_v_min()) / (grid->get_v_max() - grid->get_v_min()) * (grid->get_n_vlines()-1)); if(botV->head()[1] < grid->get_v_min()) lastGridIndex = 0; else lastGridIndex = (Int) ((botV->head()[1] - grid->get_v_min()) / (grid->get_v_max() - grid->get_v_min()) * (grid->get_n_vlines()-1)) + 1; /*find the interval inside the polygon for each gridline*/ Int *leftGridIndices = (Int*) malloc(sizeof(Int) * (firstGridIndex - lastGridIndex +1)); assert(leftGridIndices); Int *rightGridIndices = (Int*) malloc(sizeof(Int) * (firstGridIndex - lastGridIndex +1)); assert(rightGridIndices); Int *leftGridInnerIndices = (Int*) malloc(sizeof(Int) * (firstGridIndex - lastGridIndex +1)); assert(leftGridInnerIndices); Int *rightGridInnerIndices = (Int*) malloc(sizeof(Int) * (firstGridIndex - lastGridIndex +1)); assert(rightGridInnerIndices); findLeftGridIndices(topV, firstGridIndex, lastGridIndex, grid, leftGridIndices, leftGridInnerIndices); findRightGridIndices(topV, firstGridIndex, lastGridIndex, grid, rightGridIndices, rightGridInnerIndices); leftGridChain = new gridBoundaryChain(grid, firstGridIndex, firstGridIndex-lastGridIndex+1, leftGridIndices, leftGridInnerIndices); rightGridChain = new gridBoundaryChain(grid, firstGridIndex, firstGridIndex-lastGridIndex+1, rightGridIndices, rightGridInnerIndices); free(leftGridIndices); free(rightGridIndices); free(leftGridInnerIndices); free(rightGridInnerIndices); } void findDownCorners(Real *botVertex, vertexArray *leftChain, Int leftChainStartIndex, Int leftChainEndIndex, vertexArray *rightChain, Int rightChainStartIndex, Int rightChainEndIndex, Real v, Real uleft, Real uright, Int& ret_leftCornerWhere, /*0: left chain, 1: topvertex, 2: rightchain*/ Int& ret_leftCornerIndex, /*useful when ret_leftCornerWhere == 0 or 2*/ Int& ret_rightCornerWhere, /*0: left chain, 1: topvertex, 2: rightchain*/ Int& ret_rightCornerIndex /*useful when ret_leftCornerWhere == 0 or 2*/ ) { #ifdef MYDEBUG printf("*************enter find donw corner\n"); printf("finddownCorner: v=%f, uleft=%f, uright=%f\n", v, uleft, uright); printf("(%i,%i,%i,%i)\n", leftChainStartIndex, leftChainEndIndex,rightChainStartIndex, rightChainEndIndex); printf("left chain is\n"); leftChain->print(); printf("right chain is\n"); rightChain->print(); #endif assert(v > botVertex[1]); Real leftGridPoint[2]; leftGridPoint[0] = uleft; leftGridPoint[1] = v; Real rightGridPoint[2]; rightGridPoint[0] = uright; rightGridPoint[1] = v; Int i; Int index1, index2; index1 = leftChain->findIndexBelowGen(v, leftChainStartIndex, leftChainEndIndex); index2 = rightChain->findIndexBelowGen(v, rightChainStartIndex, rightChainEndIndex); if(index2 <= rightChainEndIndex) //index2 was found above index2 = rightChain->skipEqualityFromStart(v, index2, rightChainEndIndex); if(index1>leftChainEndIndex && index2 > rightChainEndIndex) /*no point below v on left chain or right chain*/ { /*the botVertex is the only vertex below v*/ ret_leftCornerWhere = 1; ret_rightCornerWhere = 1; } else if(index1>leftChainEndIndex ) /*index2 <= rightChainEndIndex*/ { ret_rightCornerWhere = 2; /*on right chain*/ ret_rightCornerIndex = index2; Real tempMin = rightChain->getVertex(index2)[0]; Int tempI = index2; for(i=index2+1; i<= rightChainEndIndex; i++) if(rightChain->getVertex(i)[0] < tempMin) { tempI = i; tempMin = rightChain->getVertex(i)[0]; } //we consider whether we can use botVertex as left corner. First check //if (leftGirdPoint, botVertex) interesects right chian or not. if(DBG_intersectChain(rightChain, rightChainStartIndex,rightChainEndIndex, leftGridPoint, botVertex)) { ret_leftCornerWhere = 2;//right ret_leftCornerIndex = index2; //should use tempI??? } else if(botVertex[0] < tempMin) ret_leftCornerWhere = 1; //bot else { ret_leftCornerWhere = 2; //right ret_leftCornerIndex = tempI; } } else if(index2> rightChainEndIndex) /*index1<=leftChainEndIndex*/ { ret_leftCornerWhere = 0; /*left chain*/ ret_leftCornerIndex = index1; /*find the vertex on the left chain with the maximum u, *either this vertex or the botvertex can be used as the right corner */ Int tempI; //skip those points which are equal to v. (avoid degeneratcy) for(tempI = index1; tempI <= leftChainEndIndex; tempI++) if(leftChain->getVertex(tempI)[1] < v) break; if(tempI > leftChainEndIndex) ret_rightCornerWhere = 1; else { Real tempMax = leftChain->getVertex(tempI)[0]; for(i=tempI; i<= leftChainEndIndex; i++) if(leftChain->getVertex(i)[0] > tempMax) { tempI = i; tempMax = leftChain->getVertex(i)[0]; } //we consider whether we can use botVertex as a corner. So first we check //whether (rightGridPoint, botVertex) interescts the left chain or not. if(DBG_intersectChain(leftChain, leftChainStartIndex,leftChainEndIndex, rightGridPoint, botVertex)) { ret_rightCornerWhere = 0; ret_rightCornerIndex = index1; //should use tempI??? } else if(botVertex[0] > tempMax) { ret_rightCornerWhere = 1; } else { ret_rightCornerWhere = 0; ret_rightCornerIndex = tempI; } } } else /*index1<=leftChainEndIndex and index2 <=rightChainEndIndex*/ { if(leftChain->getVertex(index1)[1] >= rightChain->getVertex(index2)[1]) /*left point above right point*/ { ret_leftCornerWhere = 0; /*on left chain*/ ret_leftCornerIndex = index1; Real tempMax; Int tempI; tempI = index1; tempMax = leftChain->getVertex(index1)[0]; /*find the maximum u for all the points on the left above the right point index2*/ for(i=index1+1; i<= leftChainEndIndex; i++) { if(leftChain->getVertex(i)[1] < rightChain->getVertex(index2)[1]) break; if(leftChain->getVertex(i)[0]>tempMax) { tempI = i; tempMax = leftChain->getVertex(i)[0]; } } //we consider if we can use rightChain(index2) as right corner //we check if (rightChain(index2), rightGidPoint) intersecs left chain or not. if(DBG_intersectChain(leftChain, leftChainStartIndex,leftChainEndIndex, rightGridPoint, rightChain->getVertex(index2))) { ret_rightCornerWhere = 0; ret_rightCornerIndex = index1; //should use tempI??? } else if(tempMax >= rightChain->getVertex(index2)[0] || tempMax >= uright ) { ret_rightCornerWhere = 0; /*on left Chain*/ ret_rightCornerIndex = tempI; } else { ret_rightCornerWhere = 2; /*on right chain*/ ret_rightCornerIndex = index2; } } else /*left below right*/ { ret_rightCornerWhere = 2; /*on the right*/ ret_rightCornerIndex = index2; Real tempMin; Int tempI; tempI = index2; tempMin = rightChain->getVertex(index2)[0]; /*find the minimum u for all the points on the right above the left poitn index1*/ for(i=index2+1; i<= rightChainEndIndex; i++) { if( rightChain->getVertex(i)[1] < leftChain->getVertex(index1)[1]) break; if(rightChain->getVertex(i)[0] < tempMin) { tempI = i; tempMin = rightChain->getVertex(i)[0]; } } //we consider if we can use leftchain(index1) as left corner. //we check if (leftChain(index1) intersects right chian or not if(DBG_intersectChain(rightChain, rightChainStartIndex, rightChainEndIndex, leftGridPoint, leftChain->getVertex(index1))) { ret_leftCornerWhere = 2; ret_leftCornerIndex = index2; //should use tempI??? } else if(tempMin <= leftChain->getVertex(index1)[0] || tempMin <= uleft) { ret_leftCornerWhere = 2; /* on right chain*/ ret_leftCornerIndex = tempI; } else { ret_leftCornerWhere = 0; /*on left chain*/ ret_leftCornerIndex = index1; } } } } void findUpCorners(Real *topVertex, vertexArray *leftChain, Int leftChainStartIndex, Int leftChainEndIndex, vertexArray *rightChain, Int rightChainStartIndex, Int rightChainEndIndex, Real v, Real uleft, Real uright, Int& ret_leftCornerWhere, /*0: left chain, 1: topvertex, 2: rightchain*/ Int& ret_leftCornerIndex, /*useful when ret_leftCornerWhere == 0 or 2*/ Int& ret_rightCornerWhere, /*0: left chain, 1: topvertex, 2: rightchain*/ Int& ret_rightCornerIndex /*useful when ret_leftCornerWhere == 0 or 2*/ ) { #ifdef MYDEBUG printf("***********enter findUpCorners\n"); #endif assert(v < topVertex[1]); Real leftGridPoint[2]; leftGridPoint[0] = uleft; leftGridPoint[1] = v; Real rightGridPoint[2]; rightGridPoint[0] = uright; rightGridPoint[1] = v; Int i; Int index1, index2; index1 = leftChain->findIndexFirstAboveEqualGen(v, leftChainStartIndex, leftChainEndIndex); index2 = rightChain->findIndexFirstAboveEqualGen(v, rightChainStartIndex, rightChainEndIndex); if(index2>= leftChainStartIndex) //index2 was found above index2 = rightChain->skipEqualityFromStart(v, index2, rightChainEndIndex); if(index1= rightChainStartIndex*/ { ret_rightCornerWhere = 2; /*on right chain*/ ret_rightCornerIndex = index2; //find the minimum u on right top, either that, or top, or right[index2] is the left corner Real tempMin = rightChain->getVertex(index2)[0]; Int tempI = index2; for(i=index2-1; i>=rightChainStartIndex; i--) if(rightChain->getVertex(i)[0] < tempMin) { tempMin = rightChain->getVertex(i)[0]; tempI = i; } //chech whether (leftGridPoint, top) intersects rightchai, //if yes, use right corner as left corner //if not, use top or right[tempI] as left corner if(DBG_intersectChain(rightChain, rightChainStartIndex, rightChainEndIndex, leftGridPoint, topVertex)) { ret_leftCornerWhere = 2; //rightChain ret_leftCornerIndex = index2; } else if(topVertex[0] < tempMin) ret_leftCornerWhere = 1; /*topvertex*/ else { ret_leftCornerWhere = 2; //right chain ret_leftCornerIndex = tempI; } } else if(index2< rightChainStartIndex) /*index1>=leftChainStartIndex*/ { ret_leftCornerWhere = 0; /*left chain*/ ret_leftCornerIndex = index1; //find the maximum u on the left top section. either that or topvertex, or left[index1] is the right corner Real tempMax = leftChain->getVertex(index1)[0]; Int tempI = index1; for(i=index1-1; i>=leftChainStartIndex; i--){ if(leftChain->getVertex(i)[0] > tempMax) { tempMax = leftChain->getVertex(i)[0]; tempI = i; } } //check whether (rightGridPoint, top) intersects leftChain or not //if yes, we use leftCorner as the right corner //if not, we use either top or left[tempI] as the right corner if(DBG_intersectChain(leftChain, leftChainStartIndex,leftChainEndIndex, rightGridPoint, topVertex)) { ret_rightCornerWhere = 0; //left chan ret_rightCornerIndex = index1; } else if(topVertex[0] > tempMax) ret_rightCornerWhere = 1;//topVertex else { ret_rightCornerWhere = 0;//left chain ret_rightCornerIndex = tempI; } } else /*index1>=leftChainStartIndex and index2 >=rightChainStartIndex*/ { if(leftChain->getVertex(index1)[1] <= rightChain->getVertex(index2)[1]) /*left point below right point*/ { ret_leftCornerWhere = 0; /*on left chain*/ ret_leftCornerIndex = index1; Real tempMax; Int tempI; tempI = index1; tempMax = leftChain->getVertex(index1)[0]; /*find the maximum u for all the points on the left below the right point index2*/ for(i=index1-1; i>= leftChainStartIndex; i--) { if(leftChain->getVertex(i)[1] > rightChain->getVertex(index2)[1]) break; if(leftChain->getVertex(i)[0]>tempMax) { tempI = i; tempMax = leftChain->getVertex(i)[0]; } } //chek whether (rightChain(index2), rightGridPoint) intersects leftchian or not if(DBG_intersectChain(leftChain, leftChainStartIndex, leftChainEndIndex, rightGridPoint, rightChain->getVertex(index2))) { ret_rightCornerWhere = 0; ret_rightCornerIndex = index1; } else if(tempMax >= rightChain->getVertex(index2)[0] || tempMax >= uright) { ret_rightCornerWhere = 0; /*on left Chain*/ ret_rightCornerIndex = tempI; } else { ret_rightCornerWhere = 2; /*on right chain*/ ret_rightCornerIndex = index2; } } else /*left above right*/ { ret_rightCornerWhere = 2; /*on the right*/ ret_rightCornerIndex = index2; Real tempMin; Int tempI; tempI = index2; tempMin = rightChain->getVertex(index2)[0]; /*find the minimum u for all the points on the right below the left poitn index1*/ for(i=index2-1; i>= rightChainStartIndex; i--) { if( rightChain->getVertex(i)[1] > leftChain->getVertex(index1)[1]) break; if(rightChain->getVertex(i)[0] < tempMin) { tempI = i; tempMin = rightChain->getVertex(i)[0]; } } //check whether (leftGRidPoint,left(index1)) interesect right chain if(DBG_intersectChain(rightChain, rightChainStartIndex, rightChainEndIndex, leftGridPoint, leftChain->getVertex(index1))) { ret_leftCornerWhere = 2; //right ret_leftCornerIndex = index2; } else if(tempMin <= leftChain->getVertex(index1)[0] || tempMin <= uleft) { ret_leftCornerWhere = 2; /* on right chain*/ ret_leftCornerIndex = tempI; } else { ret_leftCornerWhere = 0; /*on left chain*/ ret_leftCornerIndex = index1; } } } #ifdef MYDEBUG printf("***********leave findUpCorners\n"); #endif } //return 1 if neck exists, 0 othewise Int findNeckF(vertexArray *leftChain, Int botLeftIndex, vertexArray *rightChain, Int botRightIndex, gridBoundaryChain* leftGridChain, gridBoundaryChain* rightGridChain, Int gridStartIndex, Int& neckLeft, Int& neckRight) { /* printf("enter findNeckF, botleft, botright=%i,%i,gstartindex=%i\n",botLeftIndex,botRightIndex,gridStartIndex); printf("leftChain is\n"); leftChain->print(); printf("rightChain is\n"); rightChain->print(); */ Int lowerGridIndex; //the grid below leftChain and rightChian vertices Int i; Int n_vlines = leftGridChain->get_nVlines(); Real v; if(botLeftIndex >= leftChain->getNumElements() || botRightIndex >= rightChain->getNumElements()) return 0; //no neck exists v=min(leftChain->getVertex(botLeftIndex)[1], rightChain->getVertex(botRightIndex)[1]); for(i=gridStartIndex; iget_v_value(i) <= v && leftGridChain->getUlineIndex(i)<= rightGridChain->getUlineIndex(i)) break; lowerGridIndex = i; if(lowerGridIndex == n_vlines) //the two trm vertex are higher than all gridlines return 0; else { Int botLeft2, botRight2; /* printf("leftGridChain->get_v_)value=%f\n",leftGridChain->get_v_value(lowerGridIndex), botLeftIndex); printf("leftChain->get_vertex(0)=(%f,%f)\n", leftChain->getVertex(0)[0],leftChain->getVertex(0)[1]); printf("leftChain->get_vertex(1)=(%f,%f)\n", leftChain->getVertex(1)[0],leftChain->getVertex(1)[1]); printf("leftChain->get_vertex(2)=(%f,%f)\n", leftChain->getVertex(2)[0],leftChain->getVertex(2)[1]); */ botLeft2 = leftChain->findIndexFirstAboveEqualGen(leftGridChain->get_v_value(lowerGridIndex), botLeftIndex, leftChain->getNumElements()-1) -1 ; /* printf("botLeft2=%i\n", botLeft2); printf("leftChain->getNumElements=%i\n", leftChain->getNumElements()); */ botRight2 = rightChain->findIndexFirstAboveEqualGen(leftGridChain->get_v_value(lowerGridIndex), botRightIndex, rightChain->getNumElements()-1) -1; if(botRight2 < botRightIndex) botRight2=botRightIndex; if(botLeft2 < botLeftIndex) botLeft2 = botLeftIndex; assert(botLeft2 >= botLeftIndex); assert(botRight2 >= botRightIndex); //find nectLeft so that it is th erightmost vertex on letChain Int tempI = botLeftIndex; Real temp = leftChain->getVertex(tempI)[0]; for(i=botLeftIndex+1; i<= botLeft2; i++) if(leftChain->getVertex(i)[0] > temp) { temp = leftChain->getVertex(i)[0]; tempI = i; } neckLeft = tempI; tempI = botRightIndex; temp = rightChain->getVertex(tempI)[0]; for(i=botRightIndex+1; i<= botRight2; i++) if(rightChain->getVertex(i)[0] < temp) { temp = rightChain->getVertex(i)[0]; tempI = i; } neckRight = tempI; return 1; } } /*find i>=botLeftIndex,j>=botRightIndex so that *(leftChain[i], rightChain[j]) is a neck. */ void findNeck(vertexArray *leftChain, Int botLeftIndex, vertexArray *rightChain, Int botRightIndex, Int& leftLastIndex, /*left point of the neck*/ Int& rightLastIndex /*right point of the neck*/ ) { assert(botLeftIndex < leftChain->getNumElements() && botRightIndex < rightChain->getNumElements()); /*now the neck exists for sure*/ if(leftChain->getVertex(botLeftIndex)[1] <= rightChain->getVertex(botRightIndex)[1]) //left below right { leftLastIndex = botLeftIndex; /*find i so that rightChain[i][1] >= leftchainbotverte[1], and i+1< */ rightLastIndex=rightChain->findIndexAboveGen(leftChain->getVertex(botLeftIndex)[1], botRightIndex+1, rightChain->getNumElements()-1); } else //left above right { rightLastIndex = botRightIndex; leftLastIndex = leftChain->findIndexAboveGen(rightChain->getVertex(botRightIndex)[1], botLeftIndex+1, leftChain->getNumElements()-1); } } void findLeftGridIndices(directedLine* topEdge, Int firstGridIndex, Int lastGridIndex, gridWrap* grid, Int* ret_indices, Int* ret_innerIndices) { Int i,k,isHoriz = 0; Int n_ulines = grid->get_n_ulines(); Real uMin = grid->get_u_min(); Real uMax = grid->get_u_max(); /* Real vMin = grid->get_v_min(); Real vMax = grid->get_v_max(); */ Real slop = 0.0, uinterc; #ifdef SHORTEN_GRID_LINE //uintercBuf stores all the interction u value for each grid line //notice that lastGridIndex<= firstGridIndex Real *uintercBuf = (Real *) malloc (sizeof(Real) * (firstGridIndex-lastGridIndex+1)); assert(uintercBuf); #endif /*initialization to make vtail bigger than grid->...*/ directedLine* dLine = topEdge; Real vtail = grid->get_v_value(firstGridIndex) + 1.0; Real tempMaxU = grid->get_u_min(); /*for each grid line*/ for(k=0, i=firstGridIndex; i>=lastGridIndex; i--, k++) { Real grid_v_value = grid->get_v_value(i); /*check whether this grid line is below the current trim edge.*/ if(vtail > grid_v_value) { /*since the grid line is below the trim edge, we *find the trim edge which will contain the trim line */ while( (vtail=dLine->tail()[1]) > grid_v_value){ tempMaxU = max(tempMaxU, dLine->tail()[0]); dLine = dLine -> getNext(); } if( fabs(dLine->head()[1] - vtail) < ZERO) isHoriz = 1; else { isHoriz = 0; slop = (dLine->head()[0] - dLine->tail()[0]) / (dLine->head()[1]-vtail); } } if(isHoriz) { uinterc = max(dLine->head()[0], dLine->tail()[0]); } else { uinterc = slop * (grid_v_value - vtail) + dLine->tail()[0]; } tempMaxU = max(tempMaxU, uinterc); if(uinterc < uMin && uinterc >= uMin - ZERO) uinterc = uMin; if(uinterc > uMax && uinterc <= uMax + ZERO) uinterc = uMax; #ifdef SHORTEN_GRID_LINE uintercBuf[k] = uinterc; #endif assert(uinterc >= uMin && uinterc <= uMax); if(uinterc == uMax) ret_indices[k] = n_ulines-1; else ret_indices[k] = (Int)(((uinterc-uMin)/(uMax - uMin)) * (n_ulines-1)) + 1; if(ret_indices[k] >= n_ulines) ret_indices[k] = n_ulines-1; ret_innerIndices[k] = (Int)(((tempMaxU-uMin)/(uMax - uMin)) * (n_ulines-1)) + 1; /*reinitialize tempMaxU for next grdiLine*/ tempMaxU = uinterc; } #ifdef SHORTEN_GRID_LINE //for each grid line, compare the left grid point with the //intersection point. If the two points are too close, then //we should move the grid point one grid to the right //and accordingly we should update the inner index. for(k=0, i=firstGridIndex; i>=lastGridIndex; i--, k++) { //check gridLine i //check ret_indices[k] Real a = grid->get_u_value(ret_indices[k]-1); Real b = grid->get_u_value(ret_indices[k]); assert(uintercBuf[k] >= a && uintercBuf < b); if( (b-uintercBuf[k]) <= 0.2 * (b-a)) //interc is very close to b { ret_indices[k]++; } //check ret_innerIndices[k] if(k>0) { if(ret_innerIndices[k] < ret_indices[k-1]) ret_innerIndices[k] = ret_indices[k-1]; if(ret_innerIndices[k] < ret_indices[k]) ret_innerIndices[k] = ret_indices[k]; } } //clean up free(uintercBuf); #endif } void findRightGridIndices(directedLine* topEdge, Int firstGridIndex, Int lastGridIndex, gridWrap* grid, Int* ret_indices, Int* ret_innerIndices) { Int i,k; Int n_ulines = grid->get_n_ulines(); Real uMin = grid->get_u_min(); Real uMax = grid->get_u_max(); /* Real vMin = grid->get_v_min(); Real vMax = grid->get_v_max(); */ Real slop = 0.0, uinterc; #ifdef SHORTEN_GRID_LINE //uintercBuf stores all the interction u value for each grid line //notice that firstGridIndex >= lastGridIndex Real *uintercBuf = (Real *) malloc (sizeof(Real) * (firstGridIndex-lastGridIndex+1)); assert(uintercBuf); #endif /*initialization to make vhead bigger than grid->v_value...*/ directedLine* dLine = topEdge->getPrev(); Real vhead = dLine->tail()[1]; Real tempMinU = grid->get_u_max(); /*for each grid line*/ for(k=0, i=firstGridIndex; i>=lastGridIndex; i--, k++) { Real grid_v_value = grid->get_v_value(i); /*check whether this grid line is below the current trim edge.*/ if(vhead >= grid_v_value) { /*since the grid line is below the tail of the trim edge, we *find the trim edge which will contain the trim line */ while( (vhead=dLine->head()[1]) > grid_v_value){ tempMinU = min(tempMinU, dLine->head()[0]); dLine = dLine -> getPrev(); } /*skip the equality in the case of degenerat case: horizontal */ while(dLine->head()[1] == grid_v_value) dLine = dLine->getPrev(); assert( dLine->tail()[1] != dLine->head()[1]); slop = (dLine->tail()[0] - dLine->head()[0]) / (dLine->tail()[1]-dLine->head()[1]); /* if(dLine->tail()[1] == vhead) isHoriz = 1; else { isHoriz = 0; slop = (dLine->tail()[0] - dLine->head()[0]) / (dLine->tail()[1]-vhead); } */ } uinterc = slop * (grid_v_value - dLine->head()[1]) + dLine->head()[0]; //in case unterc is outside of the grid due to floating point if(uinterc < uMin) uinterc = uMin; else if(uinterc > uMax) uinterc = uMax; #ifdef SHORTEN_GRID_LINE uintercBuf[k] = uinterc; #endif tempMinU = min(tempMinU, uinterc); assert(uinterc >= uMin && uinterc <= uMax); if(uinterc == uMin) ret_indices[k] = 0; else ret_indices[k] = (int)ceil((((uinterc-uMin)/(uMax - uMin)) * (n_ulines-1))) -1; /* if(ret_indices[k] >= grid->get_n_ulines()) { printf("ERROR3\n"); exit(0); } if(ret_indices[k] < 0) { printf("ERROR4\n"); exit(0); } */ ret_innerIndices[k] = (int)ceil ((((tempMinU-uMin)/(uMax - uMin)) * (n_ulines-1))) -1; tempMinU = uinterc; } #ifdef SHORTEN_GRID_LINE //for each grid line, compare the left grid point with the //intersection point. If the two points are too close, then //we should move the grid point one grid to the right //and accordingly we should update the inner index. for(k=0, i=firstGridIndex; i>=lastGridIndex; i--, k++) { //check gridLine i //check ret_indices[k] Real a = grid->get_u_value(ret_indices[k]); Real b = grid->get_u_value(ret_indices[k]+1); assert(uintercBuf[k] > a && uintercBuf <= b); if( (uintercBuf[k]-a) <= 0.2 * (b-a)) //interc is very close to a { ret_indices[k]--; } //check ret_innerIndices[k] if(k>0) { if(ret_innerIndices[k] > ret_indices[k-1]) ret_innerIndices[k] = ret_indices[k-1]; if(ret_innerIndices[k] > ret_indices[k]) ret_innerIndices[k] = ret_indices[k]; } } //clean up free(uintercBuf); #endif } void sampleMonoPoly(directedLine* polygon, gridWrap* grid, Int ulinear, Int vlinear, primStream* pStream, rectBlockArray* rbArray) { /* { grid->print(); polygon->writeAllPolygons("zloutputFile"); exit(0); } */ if(grid->get_n_ulines() == 2 || grid->get_n_vlines() == 2) { if(ulinear && grid->get_n_ulines() == 2) { monoTriangulationFun(polygon, compV2InY, pStream); return; } else if(DBG_isConvex(polygon) && polygon->numEdges() >=4) { triangulateConvexPoly(polygon, ulinear, vlinear, pStream); return; } else if(vlinear || DBG_is_U_direction(polygon)) { Int n_cusps;//num interior cusps Int n_edges = polygon->numEdges(); directedLine** cusps = (directedLine**) malloc(sizeof(directedLine*) * n_edges); assert(cusps); findInteriorCuspsX(polygon, n_cusps, cusps); if(n_cusps == 0) //u_monotone { monoTriangulationFun(polygon, compV2InX, pStream); free(cusps); return; } else if(n_cusps == 1) //one interior cusp { directedLine* new_polygon = polygonConvert(cusps[0]); directedLine* other = findDiagonal_singleCuspX( new_polygon); // 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(polygon, compV2InX, pStream); free(cusps); return; } 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(); free(cusps); return; } free(cusps); } } /*find the top and bottom of the polygon. It is supposed to be *a V-monotone polygon */ directedLine* tempV; directedLine* topV; directedLine* botV; topV = botV = polygon; for(tempV = polygon->getNext(); tempV != polygon; tempV = tempV->getNext()) { if(compV2InY(topV->head(), tempV->head())<0) { topV = tempV; } if(compV2InY(botV->head(), tempV->head())>0) { botV = tempV; } } /*find the first(top) and the last (bottom) grid line which intersect the *this polygon */ Int firstGridIndex; /*the index in the grid*/ Int lastGridIndex; firstGridIndex = (Int) ((topV->head()[1] - grid->get_v_min()) / (grid->get_v_max() - grid->get_v_min()) * (grid->get_n_vlines()-1)); lastGridIndex = (Int) ((botV->head()[1] - grid->get_v_min()) / (grid->get_v_max() - grid->get_v_min()) * (grid->get_n_vlines()-1)) + 1; /*find the interval inside the polygon for each gridline*/ Int *leftGridIndices = (Int*) malloc(sizeof(Int) * (firstGridIndex - lastGridIndex +1)); assert(leftGridIndices); Int *rightGridIndices = (Int*) malloc(sizeof(Int) * (firstGridIndex - lastGridIndex +1)); assert(rightGridIndices); Int *leftGridInnerIndices = (Int*) malloc(sizeof(Int) * (firstGridIndex - lastGridIndex +1)); assert(leftGridInnerIndices); Int *rightGridInnerIndices = (Int*) malloc(sizeof(Int) * (firstGridIndex - lastGridIndex +1)); assert(rightGridInnerIndices); findLeftGridIndices(topV, firstGridIndex, lastGridIndex, grid, leftGridIndices, leftGridInnerIndices); findRightGridIndices(topV, firstGridIndex, lastGridIndex, grid, rightGridIndices, rightGridInnerIndices); gridBoundaryChain leftGridChain(grid, firstGridIndex, firstGridIndex-lastGridIndex+1, leftGridIndices, leftGridInnerIndices); gridBoundaryChain rightGridChain(grid, firstGridIndex, firstGridIndex-lastGridIndex+1, rightGridIndices, rightGridInnerIndices); // leftGridChain.draw(); // leftGridChain.drawInner(); // rightGridChain.draw(); // rightGridChain.drawInner(); /*(1) determine the grid boundaries (left and right). *(2) process polygon into two monotone chaines: use vertexArray *(3) call sampleMonoPolyRec */ /*copy the two chains into vertexArray datastructure*/ Int i; vertexArray leftChain(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*/ leftChain.appendVertex(topV->getVertex(i)); } for(tempV = topV->getNext(); tempV != botV; tempV = tempV->getNext()) { for(i=0; i<=tempV->get_npoints()-2; i++){ leftChain.appendVertex(tempV->getVertex(i)); } } vertexArray rightChain(20); for(tempV = topV->getPrev(); tempV != botV; tempV = tempV->getPrev()) { for(i=tempV->get_npoints()-2; i>=0; i--){ rightChain.appendVertex(tempV->getVertex(i)); } } for(i=botV->get_npoints()-2; i>=1; i--){ rightChain.appendVertex(tempV->getVertex(i)); } sampleMonoPolyRec(topV->head(), botV->head(), &leftChain, 0, &rightChain, 0, &leftGridChain, &rightGridChain, 0, pStream, rbArray); /*cleanup space*/ free(leftGridIndices); free(rightGridIndices); free(leftGridInnerIndices); free(rightGridInnerIndices); } void sampleMonoPolyRec( Real* topVertex, Real* botVertex, vertexArray* leftChain, Int leftStartIndex, vertexArray* rightChain, Int rightStartIndex, gridBoundaryChain* leftGridChain, gridBoundaryChain* rightGridChain, Int gridStartIndex, primStream* pStream, rectBlockArray* rbArray) { /*find the first connected component, and the four corners. */ Int index1, index2; /*the first and last grid line of the first connected component*/ if(topVertex[1] <= botVertex[1]) return; /*find i so that the grid line is below the top vertex*/ Int i=gridStartIndex; while (i < leftGridChain->get_nVlines()) { if(leftGridChain->get_v_value(i) < topVertex[1]) break; i++; } /*find the first connected component starting with i*/ /*find index1 so that left_uline_index <= right_uline_index, that is, this *grid line contains at least one inner grid point */ index1=i; int num_skipped_grid_lines=0; while(index1 < leftGridChain->get_nVlines()) { if(leftGridChain->getUlineIndex(index1) <= rightGridChain->getUlineIndex(index1)) break; num_skipped_grid_lines++; index1++; } if(index1 >= leftGridChain->get_nVlines()) /*no grid line exists which has inner point*/ { /*stop recursion, ...*/ /*monotone triangulate it...*/ // printf("no grid line exists\n"); /* monoTriangulationRecOpt(topVertex, botVertex, leftChain, leftStartIndex, rightChain, rightStartIndex, pStream); */ if(num_skipped_grid_lines <2) { monoTriangulationRecGenOpt(topVertex, botVertex, leftChain, leftStartIndex, leftChain->getNumElements()-1, rightChain, rightStartIndex, rightChain->getNumElements()-1, pStream); } else { //the optimum way to triangulate is top-down since this polygon //is narrow-long. monoTriangulationRec(topVertex, botVertex, leftChain, leftStartIndex, rightChain, rightStartIndex, pStream); } /* monoTriangulationRec(topVertex, botVertex, leftChain, leftStartIndex, rightChain, rightStartIndex, pStream); */ /* monoTriangulationRecGenTBOpt(topVertex, botVertex, leftChain, leftStartIndex, leftChain->getNumElements()-1, rightChain, rightStartIndex, rightChain->getNumElements()-1, pStream);*/ } else { /*find index2 so that left_inner_index <= right_inner_index holds until index2*/ index2=index1+1; if(index2 < leftGridChain->get_nVlines()) while(leftGridChain->getInnerIndex(index2) <= rightGridChain->getInnerIndex(index2)) { index2++; if(index2 >= leftGridChain->get_nVlines()) break; } index2--; /*the neck*/ Int neckLeftIndex; Int neckRightIndex; /*the four corners*/ Int up_leftCornerWhere; Int up_leftCornerIndex; Int up_rightCornerWhere; Int up_rightCornerIndex; Int down_leftCornerWhere; Int down_leftCornerIndex; Int down_rightCornerWhere; Int down_rightCornerIndex; Real* tempBotVertex; /*the bottom vertex for this component*/ Real* nextTopVertex=NULL; /*for the recursion*/ Int nextLeftStartIndex=0; Int nextRightStartIndex=0; /*find the points below the grid line index2 on both chains*/ Int botLeftIndex = leftChain->findIndexStrictBelowGen( leftGridChain->get_v_value(index2), leftStartIndex, leftChain->getNumElements()-1); Int botRightIndex = rightChain->findIndexStrictBelowGen( rightGridChain->get_v_value(index2), rightStartIndex, rightChain->getNumElements()-1); /*if either botLeftIndex>= numelements, * or botRightIndex >= numelemnet, *then there is no neck exists. the bottom vertex is botVertex, */ if(! findNeckF(leftChain, botLeftIndex, rightChain, botRightIndex, leftGridChain, rightGridChain, index2, neckLeftIndex, neckRightIndex)) /* if(botLeftIndex == leftChain->getNumElements() || botRightIndex == rightChain->getNumElements()) */ { #ifdef MYDEBUG printf("neck NOT exists, botRightIndex=%i\n", botRightIndex); #endif tempBotVertex = botVertex; nextTopVertex = botVertex; botLeftIndex = leftChain->getNumElements()-1; botRightIndex = rightChain->getNumElements()-1; } else /*neck exists*/ { #ifdef MYDEBUG printf("neck exists\n"); #endif /* findNeck(leftChain, botLeftIndex, rightChain, botRightIndex, neckLeftIndex, neckRightIndex); */ #ifdef MYDEBUG printf("neck is found, neckLeftIndex=%i, neckRightIndex=%i\n", neckLeftIndex, neckRightIndex); glBegin(GL_LINES); glVertex2fv(leftChain->getVertex(neckLeftIndex)); glVertex2fv(rightChain->getVertex(neckRightIndex)); glEnd(); #endif if(leftChain->getVertex(neckLeftIndex)[1] <= rightChain->getVertex(neckRightIndex)[1]) { tempBotVertex = leftChain->getVertex(neckLeftIndex); botLeftIndex = neckLeftIndex-1; botRightIndex = neckRightIndex; nextTopVertex = rightChain->getVertex(neckRightIndex); nextLeftStartIndex = neckLeftIndex; nextRightStartIndex = neckRightIndex+1; } else { tempBotVertex = rightChain->getVertex(neckRightIndex); botLeftIndex = neckLeftIndex; botRightIndex = neckRightIndex-1; nextTopVertex = leftChain->getVertex(neckLeftIndex); nextLeftStartIndex = neckLeftIndex+1; nextRightStartIndex = neckRightIndex; } } findUpCorners(topVertex, leftChain, leftStartIndex, botLeftIndex, rightChain, rightStartIndex, botRightIndex, leftGridChain->get_v_value(index1), leftGridChain->get_u_value(index1), rightGridChain->get_u_value(index1), up_leftCornerWhere, up_leftCornerIndex, up_rightCornerWhere, up_rightCornerIndex); findDownCorners(tempBotVertex, leftChain, leftStartIndex, botLeftIndex, rightChain, rightStartIndex, botRightIndex, leftGridChain->get_v_value(index2), leftGridChain->get_u_value(index2), rightGridChain->get_u_value(index2), down_leftCornerWhere, down_leftCornerIndex, down_rightCornerWhere, down_rightCornerIndex); #ifdef MYDEBUG printf("find corners done, down_leftwhere=%i, down_righwhere=%i,\n",down_leftCornerWhere, down_rightCornerWhere ); printf("find corners done, up_leftwhere=%i, up_righwhere=%i,\n",up_leftCornerWhere, up_rightCornerWhere ); printf("find corners done, up_leftindex=%i, up_righindex=%i,\n",up_leftCornerIndex, up_rightCornerIndex ); printf("find corners done, down_leftindex=%i, down_righindex=%i,\n",down_leftCornerIndex, down_rightCornerIndex ); #endif /* drawCorners(topVertex, tempBotVertex, leftChain, rightChain, leftGridChain, rightGridChain, index1, index2, up_leftCornerWhere, up_leftCornerIndex, up_rightCornerWhere, up_rightCornerIndex, down_leftCornerWhere, down_leftCornerIndex, down_rightCornerWhere, down_rightCornerIndex); */ sampleConnectedComp(topVertex, tempBotVertex, leftChain, leftStartIndex, botLeftIndex, rightChain, rightStartIndex, botRightIndex, leftGridChain, rightGridChain, index1, index2, up_leftCornerWhere, up_leftCornerIndex, up_rightCornerWhere, up_rightCornerIndex, down_leftCornerWhere, down_leftCornerIndex, down_rightCornerWhere, down_rightCornerIndex, pStream, rbArray ); /*recursion*/ sampleMonoPolyRec( nextTopVertex, botVertex, leftChain, nextLeftStartIndex, rightChain, nextRightStartIndex, leftGridChain, rightGridChain, index2+1, pStream, rbArray); } } void sampleLeftStrip(vertexArray* leftChain, Int topLeftIndex, Int botLeftIndex, gridBoundaryChain* leftGridChain, Int leftGridChainStartIndex, Int leftGridChainEndIndex, primStream* pStream ) { assert(leftChain->getVertex(topLeftIndex)[1] > leftGridChain->get_v_value(leftGridChainStartIndex)); assert(leftChain->getVertex(topLeftIndex+1)[1] <= leftGridChain->get_v_value(leftGridChainStartIndex)); assert(leftChain->getVertex(botLeftIndex)[1] <= leftGridChain->get_v_value(leftGridChainEndIndex)); assert(leftChain->getVertex(botLeftIndex-1)[1] > leftGridChain->get_v_value(leftGridChainEndIndex)); /* *(1)find the last grid line which doesn'; pass below * this first edge, sample this region: one trim edge and * possily multiple grid lines. */ Real *upperVert, *lowerVert; /*the end points of the first trim edge*/ upperVert = leftChain->getVertex(topLeftIndex); lowerVert = leftChain->getVertex(topLeftIndex+1); Int index = leftGridChainStartIndex; while(leftGridChain->get_v_value(index) >= lowerVert[1]){ index++; if(index > leftGridChainEndIndex) break; } index--; sampleLeftSingleTrimEdgeRegion(upperVert, lowerVert, leftGridChain, leftGridChainStartIndex, index, pStream); sampleLeftStripRec(leftChain, topLeftIndex+1, botLeftIndex, leftGridChain, index, leftGridChainEndIndex, pStream); } void sampleLeftStripRec(vertexArray* leftChain, Int topLeftIndex, Int botLeftIndex, gridBoundaryChain* leftGridChain, Int leftGridChainStartIndex, Int leftGridChainEndIndex, primStream* pStream ) { /*now top left trim vertex is below the top grid line. */ /*stop condition: if topLeftIndex >= botLeftIndex, then stop. */ if(topLeftIndex >= botLeftIndex) return; /*find the last trim vertex which is above the second top grid line: * index1. *and sampleLeftOneGridStep(leftchain, topLeftIndex, index1, leftGridChain, * leftGridChainStartIndex). * index1 could be equal to topLeftIndex. */ Real secondGridChainV = leftGridChain->get_v_value(leftGridChainStartIndex+1); assert(leftGridChainStartIndex < leftGridChainEndIndex); Int index1 = topLeftIndex; while(leftChain->getVertex(index1)[1] > secondGridChainV) index1++; index1--; sampleLeftOneGridStep(leftChain, topLeftIndex, index1, leftGridChain, leftGridChainStartIndex, pStream); /* * Let the next trim vertex be nextTrimVertIndex (which should be * below the second grid line). * Find the last grid line index2 which is above nextTrimVert. * sampleLeftSingleTrimEdgeRegion(uppervert[2], lowervert[2], * leftGridChain, leftGridChainStartIndex+1, index2). */ Real *uppervert, *lowervert; uppervert = leftChain->getVertex(index1); lowervert = leftChain->getVertex(index1+1); Int index2 = leftGridChainStartIndex+1; while(leftGridChain->get_v_value(index2) >= lowervert[1]) { index2++; if(index2 > leftGridChainEndIndex) break; } index2--; sampleLeftSingleTrimEdgeRegion(uppervert, lowervert, leftGridChain, leftGridChainStartIndex+1, index2, pStream); /* sampleLeftStripRec(leftChain, nextTrimVertIndex, botLeftIndex, leftGridChain, index2, leftGridChainEndIndex ) * */ sampleLeftStripRec(leftChain, index1+1, botLeftIndex, leftGridChain, index2, leftGridChainEndIndex, pStream); } /***************begin RecF***********************/ /* the gridlines from leftGridChainStartIndex to * leftGridChainEndIndex are assumed to form a * connected component. * the trim vertex of topLeftIndex is assumed to * be below the first gridline, and the tim vertex * of botLeftIndex is assumed to be above the last * grid line. * If botLeftIndex < topLeftIndex, then no connected componeent exists, and this funcion returns without * outputing any triangles. * Otherwise botLeftIndex >= topLeftIndex, there is at least one triangle to output. */ void sampleLeftStripRecF(vertexArray* leftChain, Int topLeftIndex, Int botLeftIndex, gridBoundaryChain* leftGridChain, Int leftGridChainStartIndex, Int leftGridChainEndIndex, primStream* pStream ) { /*now top left trim vertex is below the top grid line. */ /*stop condition: if topLeftIndex > botLeftIndex, then stop. */ if(topLeftIndex > botLeftIndex) return; /*if there is only one grid Line, return.*/ if(leftGridChainStartIndex>=leftGridChainEndIndex) return; assert(leftChain->getVertex(topLeftIndex)[1] <= leftGridChain->get_v_value(leftGridChainStartIndex) && leftChain->getVertex(botLeftIndex)[1] >= leftGridChain->get_v_value(leftGridChainEndIndex)); /*firs find the first trim vertex which is below or equal to the second top grid line: * index1. */ Real secondGridChainV = leftGridChain->get_v_value(leftGridChainStartIndex+1); Int index1 = topLeftIndex; while(leftChain->getVertex(index1)[1] > secondGridChainV){ index1++; if(index1>botLeftIndex) break; } /*now leftChain->getVertex(index-1)[1] > secondGridChainV and * leftChain->getVertex(index)[1] <= secondGridChainV *If equality holds, then we should include the vertex index1, otherwise we include only index1-1, to *perform sampleOneGridStep. */ if(index1>botLeftIndex) index1--; else if(leftChain->getVertex(index1)[1] < secondGridChainV) index1--; /*now we have leftChain->getVertex(index1)[1] >= secondGridChainV, and * leftChain->getVertex(index1+1)[1] <= secondGridChainV */ sampleLeftOneGridStep(leftChain, topLeftIndex, index1, leftGridChain, leftGridChainStartIndex, pStream); /*if leftChain->getVertex(index1)[1] == secondGridChainV, then we can recursively do the rest. */ if(leftChain->getVertex(index1)[1] == secondGridChainV) { sampleLeftStripRecF(leftChain, index1, botLeftIndex,leftGridChain, leftGridChainStartIndex+1, leftGridChainEndIndex, pStream); } else if(index1 < botLeftIndex) { /* Otherwise, we have leftChain->getVertex(index1)[1] > secondGridChainV, * let the next trim vertex be nextTrimVertIndex (which should be strictly * below the second grid line). * Find the last grid line index2 which is above nextTrimVert. * sampleLeftSingleTrimEdgeRegion(uppervert[2], lowervert[2], * leftGridChain, leftGridChainStartIndex+1, index2). */ Real *uppervert, *lowervert; uppervert = leftChain->getVertex(index1); lowervert = leftChain->getVertex(index1+1); //okay since index1get_v_value(index2) >= lowervert[1]) { index2++; if(index2 > leftGridChainEndIndex) break; } index2--; sampleLeftSingleTrimEdgeRegion(uppervert, lowervert, leftGridChain, leftGridChainStartIndex+1, index2, pStream); /*recursion*/ sampleLeftStripRecF(leftChain, index1+1, botLeftIndex, leftGridChain, index2, leftGridChainEndIndex, pStream); } } /***************End RecF***********************/ /*sample the left area in between one trim edge and multiple grid lines. * all the grid lines should be in between the two end poins of the *trim edge. */ void sampleLeftSingleTrimEdgeRegion(Real upperVert[2], Real lowerVert[2], gridBoundaryChain* gridChain, Int beginIndex, Int endIndex, primStream* pStream) { Int i,j,k; vertexArray vArray(endIndex-beginIndex+1); vArray.appendVertex(gridChain->get_vertex(beginIndex)); for(k=1, i=beginIndex+1; i<=endIndex; i++, k++) { vArray.appendVertex(gridChain->get_vertex(i)); /*output the fan of the grid points of the (i)th and (i-1)th grid line. */ if(gridChain->getUlineIndex(i) < gridChain->getUlineIndex(i-1)) { pStream->begin(); pStream->insert(gridChain->get_vertex(i-1)); for(j=gridChain->getUlineIndex(i); j<= gridChain->getUlineIndex(i-1); j++) pStream->insert(gridChain->getGrid()->get_u_value(j), gridChain->get_v_value(i)); pStream->end(PRIMITIVE_STREAM_FAN); } else if(gridChain->getUlineIndex(i) > gridChain->getUlineIndex(i-1)) { pStream->begin(); pStream->insert(gridChain->get_vertex(i)); for(j=gridChain->getUlineIndex(i); j>= gridChain->getUlineIndex(i-1); j--) pStream->insert(gridChain->getGrid()->get_u_value(j), gridChain->get_v_value(i-1)); pStream->end(PRIMITIVE_STREAM_FAN); } /*otherwisem, the two are equal, so there is no fan to outout*/ } monoTriangulation2(upperVert, lowerVert, &vArray, 0, endIndex-beginIndex, 0, /*decreasing chain*/ pStream); } /*return i, such that from begin to i-1 the chain is strictly u-monotone. */ Int findIncreaseChainFromBegin(vertexArray* chain, Int begin ,Int end) { Int i=begin; Real prevU = chain->getVertex(i)[0]; Real thisU; for(i=begin+1; i<=end; i++){ thisU = chain->getVertex(i)[0]; if(prevU < thisU){ prevU = thisU; } else break; } return i; } /*check whether there is a vertex whose v value is strictly *inbetween vup vbelow *if no middle exists return -1, else return the idnex. */ Int checkMiddle(vertexArray* chain, Int begin, Int end, Real vup, Real vbelow) { Int i; for(i=begin; i<=end; i++) { if(chain->getVertex(i)[1] < vup && chain->getVertex(i)[1]>vbelow) return i; } return -1; } /*the degenerat case of sampleLeftOneGridStep*/ void sampleLeftOneGridStepNoMiddle(vertexArray* leftChain, Int beginLeftIndex, Int endLeftIndex, gridBoundaryChain* leftGridChain, Int leftGridChainStartIndex, primStream* pStream) { /*since there is no middle, there is at most one point which is on the *second grid line, there could be multiple points on the first (top) *grid line. */ leftGridChain->leftEndFan(leftGridChainStartIndex+1, pStream); monoTriangulation2(leftGridChain->get_vertex(leftGridChainStartIndex), leftGridChain->get_vertex(leftGridChainStartIndex+1), leftChain, beginLeftIndex, endLeftIndex, 1, //is increase chain. pStream); } /*sampling the left area in between two grid lines. */ void sampleLeftOneGridStep(vertexArray* leftChain, Int beginLeftIndex, Int endLeftIndex, gridBoundaryChain* leftGridChain, Int leftGridChainStartIndex, primStream* pStream ) { if(checkMiddle(leftChain, beginLeftIndex, endLeftIndex, leftGridChain->get_v_value(leftGridChainStartIndex), leftGridChain->get_v_value(leftGridChainStartIndex+1))<0) { sampleLeftOneGridStepNoMiddle(leftChain, beginLeftIndex, endLeftIndex, leftGridChain, leftGridChainStartIndex, pStream); return; } //copy into a polygon { directedLine* poly = NULL; sampledLine* sline; directedLine* dline; gridWrap* grid = leftGridChain->getGrid(); Real vert1[2]; Real vert2[2]; Int i; Int innerInd = leftGridChain->getInnerIndex(leftGridChainStartIndex+1); Int upperInd = leftGridChain->getUlineIndex(leftGridChainStartIndex); Int lowerInd = leftGridChain->getUlineIndex(leftGridChainStartIndex+1); Real upperV = leftGridChain->get_v_value(leftGridChainStartIndex); Real lowerV = leftGridChain->get_v_value(leftGridChainStartIndex+1); //the upper gridline vert1[1] = vert2[1] = upperV; for(i=innerInd; i>upperInd; i--) { vert1[0]=grid->get_u_value(i); vert2[0]=grid->get_u_value(i-1); sline = new sampledLine(vert1, vert2); dline = new directedLine(INCREASING, sline); if(poly == NULL) poly = dline; else poly->insert(dline); } //the edge connecting upper grid with left chain vert1[0] = grid->get_u_value(upperInd); vert1[1] = upperV; sline = new sampledLine(vert1, leftChain->getVertex(beginLeftIndex)); dline = new directedLine(INCREASING, sline); if(poly == NULL) poly = dline; else poly->insert(dline); //the left chain for(i=beginLeftIndex; igetVertex(i), leftChain->getVertex(i+1)); dline = new directedLine(INCREASING, sline); poly->insert(dline); } //the edge connecting left chain with lower gridline vert2[0] = grid->get_u_value(lowerInd); vert2[1] = lowerV; sline = new sampledLine(leftChain->getVertex(endLeftIndex), vert2); dline = new directedLine(INCREASING, sline); poly->insert(dline); //the lower grid line vert1[1] = vert2[1] = lowerV; for(i=lowerInd; iget_u_value(i); vert2[0] = grid->get_u_value(i+1); sline = new sampledLine(vert1, vert2); dline = new directedLine(INCREASING, sline); poly->insert(dline); } //the vertical grid line segement vert1[0]=vert2[0] = grid->get_u_value(innerInd); vert2[1]=upperV; vert1[1]=lowerV; sline=new sampledLine(vert1, vert2); dline=new directedLine(INCREASING, sline); poly->insert(dline); monoTriangulationOpt(poly, pStream); //cleanup poly->deleteSinglePolygonWithSline(); return; } Int i; if(1/*leftGridChain->getUlineIndex(leftGridChainStartIndex) >= leftGridChain->getUlineIndex(leftGridChainStartIndex+1)*/ ) /*the second grid line is beyond the first one to the left*/ { /*find the maximal U-monotone chain * of endLeftIndex, endLeftIndex-1, ..., */ i=endLeftIndex; Real prevU = leftChain->getVertex(i)[0]; for(i=endLeftIndex-1; i>=beginLeftIndex; i--){ Real thisU = leftChain->getVertex(i)[0]; if( prevU < thisU){ prevU = thisU; } else break; } /*from endLeftIndex to i+1 is strictly U- monotone */ /*if i+1==endLeftIndex and the vertex and leftchain is on the second gridline, then *we should use 2 vertices on the leftchain. If we only use one (endLeftIndex), then we *we would output degenerate triangles */ if(i+1 == endLeftIndex && leftChain->getVertex(endLeftIndex)[1] == leftGridChain->get_v_value(1+leftGridChainStartIndex)) i--; Int j = beginLeftIndex/*endLeftIndex*/+1; if(leftGridChain->getInnerIndex(leftGridChainStartIndex+1) > leftGridChain->getUlineIndex(leftGridChainStartIndex)) { j = findIncreaseChainFromBegin(leftChain, beginLeftIndex, i+1/*endLeftIndex*/); Int temp = beginLeftIndex; /*now from begin to j-1 is strictly u-monotone*/ /*if j-1 is on the first grid line, then we want to skip to the vertex which is strictly *below the grid line. This vertexmust exist since there is a 'corner turn' inbetween the two grid lines */ if(j-1 == beginLeftIndex) { while(leftChain->getVertex(j-1)[1] == leftGridChain->get_v_value(leftGridChainStartIndex)) j++; Real vert[2]; vert[0] = leftGridChain->get_u_value(leftGridChainStartIndex); vert[1] = leftGridChain->get_v_value(leftGridChainStartIndex); monoTriangulation2( vert/*leftChain->getVertex(beginLeftIndex)*/, leftChain->getVertex(j-1), leftChain, beginLeftIndex, j-2, 1, pStream //increase chain ); temp = j-1; } stripOfFanLeft(leftChain, j-1, temp/*beginLeftIndex*/, leftGridChain->getGrid(), leftGridChain->getVlineIndex(leftGridChainStartIndex), leftGridChain->getUlineIndex(leftGridChainStartIndex), leftGridChain->getInnerIndex(leftGridChainStartIndex+1), pStream, 1 /*the grid line is above the trim line*/ ); } stripOfFanLeft(leftChain, endLeftIndex, i+1, leftGridChain->getGrid(), leftGridChain->getVlineIndex(leftGridChainStartIndex+1), leftGridChain->getUlineIndex(leftGridChainStartIndex+1), leftGridChain->getInnerIndex(leftGridChainStartIndex+1), pStream, 0 /*the grid line is below the trim lines*/ ); /*monotone triangulate the remaining left chain togther with the *two vertices on the two grid v-lines. */ Real vert[2][2]; vert[0][0]=vert[1][0] = leftGridChain->getInner_u_value(leftGridChainStartIndex+1); vert[0][1] = leftGridChain->get_v_value(leftGridChainStartIndex); vert[1][1] = leftGridChain->get_v_value(leftGridChainStartIndex+1); // vertexArray right(vert, 2); monoTriangulation2( &vert[0][0], /*top vertex */ &vert[1][0], /*bottom vertex*/ leftChain, /*beginLeftIndex*/j-1, i+1, 1, /*an increasing chain*/ pStream); } else /*the second one is shorter than the first one to the left*/ { /*find the maximal U-monotone chain of beginLeftIndex, beginLeftIndex+1,..., */ i=beginLeftIndex; Real prevU = leftChain->getVertex(i)[0]; for(i=beginLeftIndex+1; i<=endLeftIndex; i++){ Real thisU = leftChain->getVertex(i)[0]; if(prevU < thisU){ prevU = thisU; } else break; } /*from beginLeftIndex to i-1 is strictly U-monotone*/ stripOfFanLeft(leftChain, i-1, beginLeftIndex, leftGridChain->getGrid(), leftGridChain->getVlineIndex(leftGridChainStartIndex), leftGridChain->getUlineIndex(leftGridChainStartIndex), leftGridChain->getUlineIndex(leftGridChainStartIndex+1), pStream, 1 /*the grid line is above the trim lines*/ ); /*monotone triangulate the remaining left chain together with the *two vertices on the two grid v-lines. */ Real vert[2][2]; vert[0][0]=vert[1][0] = leftGridChain->get_u_value(leftGridChainStartIndex+1); vert[0][1] = leftGridChain->get_v_value(leftGridChainStartIndex); vert[1][1] = leftGridChain->get_v_value(leftGridChainStartIndex+1); vertexArray right(vert, 2); monoTriangulation2( &vert[0][0], //top vertex &vert[1][0], //bottom vertex leftChain, i-1, endLeftIndex, 1, /*an increase chain*/ pStream); } } /*n_upper>=1 *n_lower>=1 */ void triangulateXYMono(Int n_upper, Real upperVerts[][2], Int n_lower, Real lowerVerts[][2], primStream* pStream) { Int i,j,k,l; Real* leftMostV; assert(n_upper>=1 && n_lower>=1); if(upperVerts[0][0] <= lowerVerts[0][0]) { i=1; j=0; leftMostV = upperVerts[0]; } else { i=0; j=1; leftMostV = lowerVerts[0]; } while(1) { if(i >= n_upper) /*case1: no more in upper*/ { if(jbegin(); pStream->insert(leftMostV); while(jinsert(lowerVerts[j]); j++; } pStream->end(PRIMITIVE_STREAM_FAN); } break; } else if(j>= n_lower) /*case2: no more in lower*/ { if(ibegin(); pStream->insert(leftMostV); for(k=n_upper-1; k>=i; k--) pStream->insert(upperVerts[k]); pStream->end(PRIMITIVE_STREAM_FAN); } break; } else /* case3: neither is empty, plus the leftMostV, there is at least one triangle to output*/ { if(upperVerts[i][0] <= lowerVerts[j][0]) { pStream->begin(); pStream->insert(lowerVerts[j]); /*the origin of this fan*/ /*find the last k>=i such that *upperverts[k][0] <= lowerverts[j][0] */ k=i; while(k lowerVerts[j][0]) break; k++; } k--; for(l=k; l>=i; l--)/*the reverse is for two-face lighting*/ { pStream->insert(upperVerts[l]); } pStream->insert(leftMostV); pStream->end(PRIMITIVE_STREAM_FAN); //update i for next loop i = k+1; leftMostV = upperVerts[k]; } else /*upperVerts[i][0] > lowerVerts[j][0]*/ { pStream->begin(); pStream->insert(upperVerts[i]);/*the origion of this fan*/ pStream->insert(leftMostV); /*find the last k>=j such that *lowerverts[k][0] < upperverts[i][0]*/ k=j; while(k< n_lower) { if(lowerVerts[k][0] >= upperVerts[i][0]) break; pStream->insert(lowerVerts[k]); k++; } pStream->end(PRIMITIVE_STREAM_FAN); j=k; leftMostV = lowerVerts[j-1]; } } } } void stripOfFanLeft(vertexArray* leftChain, Int largeIndex, Int smallIndex, gridWrap* grid, Int vlineIndex, Int ulineSmallIndex, Int ulineLargeIndex, primStream* pStream, Int gridLineUp /*1 if the grid line is above the trim lines*/ ) { assert(largeIndex >= smallIndex); Real grid_v_value; grid_v_value = grid->get_v_value(vlineIndex); Real2* trimVerts=(Real2*) malloc(sizeof(Real2)* (largeIndex-smallIndex+1)); assert(trimVerts); Real2* gridVerts=(Real2*) malloc(sizeof(Real2)* (ulineLargeIndex-ulineSmallIndex+1)); assert(gridVerts); Int k,i; if(gridLineUp) /*trim line is below grid line, so trim vertices are going right when index increases*/ for(k=0, i=smallIndex; i<=largeIndex; i++, k++) { trimVerts[k][0] = leftChain->getVertex(i)[0]; trimVerts[k][1] = leftChain->getVertex(i)[1]; } else for(k=0, i=largeIndex; i>=smallIndex; i--, k++) { trimVerts[k][0] = leftChain->getVertex(i)[0]; trimVerts[k][1] = leftChain->getVertex(i)[1]; } for(k=0, i=ulineSmallIndex; i<= ulineLargeIndex; i++, k++) { gridVerts[k][0] = grid->get_u_value(i); gridVerts[k][1] = grid_v_value; } if(gridLineUp) triangulateXYMono( ulineLargeIndex-ulineSmallIndex+1, gridVerts, largeIndex-smallIndex+1, trimVerts, pStream); else triangulateXYMono(largeIndex-smallIndex+1, trimVerts, ulineLargeIndex-ulineSmallIndex+1, gridVerts, pStream); free(trimVerts); free(gridVerts); }