| /* |
| ** 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/sampleCompTop.cc,v 1.1.1.1 2012/03/29 17:22:17 uid42307 Exp $ |
| */ |
| |
| #include <stdlib.h> |
| #include <stdio.h> |
| #include <math.h> |
| #include "zlassert.h" |
| #include "sampleCompTop.h" |
| #include "sampleCompRight.h" |
| |
| #define max(a,b) ((a>b)? a:b) |
| |
| //return : index_small, and index_large, |
| //from [small, large] is strictly U-monotne, |
| //from [large+1, end] is <u |
| //and vertex[large][0] is >= u |
| //if eveybody is <u, the large = start-1. |
| //otherwise both large and small are meaningful and we have start<=small<=large<=end |
| void findTopLeftSegment(vertexArray* leftChain, |
| Int leftStart, |
| Int leftEnd, |
| Real u, |
| Int& ret_index_small, |
| Int& ret_index_large |
| ) |
| { |
| Int i; |
| assert(leftStart <= leftEnd); |
| for(i=leftEnd; i>= leftStart; i--) |
| { |
| if(leftChain->getVertex(i)[0] >= u) |
| break; |
| } |
| ret_index_large = i; |
| if(ret_index_large >= leftStart) |
| { |
| for(i=ret_index_large; i>leftStart; i--) |
| { |
| if(leftChain->getVertex(i-1)[0] <= leftChain->getVertex(i)[0]) |
| break; |
| } |
| ret_index_small = i; |
| } |
| } |
| |
| void findTopRightSegment(vertexArray* rightChain, |
| Int rightStart, |
| Int rightEnd, |
| Real u, |
| Int& ret_index_small, |
| Int& ret_index_large) |
| { |
| Int i; |
| assert(rightStart<=rightEnd); |
| for(i=rightEnd; i>=rightStart; i--) |
| { |
| if(rightChain->getVertex(i)[0] <= u) |
| break; |
| } |
| ret_index_large = i; |
| if(ret_index_large >= rightStart) |
| { |
| for(i=ret_index_large; i>rightStart;i--) |
| { |
| if(rightChain->getVertex(i-1)[0] >= rightChain->getVertex(i)[0]) |
| break; |
| } |
| ret_index_small = i; |
| } |
| } |
| |
| |
| void sampleTopRightWithGridLinePost(Real* topVertex, |
| vertexArray* rightChain, |
| Int rightStart, |
| Int segIndexSmall, |
| Int segIndexLarge, |
| Int rightEnd, |
| gridWrap* grid, |
| Int gridV, |
| Int leftU, |
| Int rightU, |
| primStream* pStream) |
| { |
| //the possible section which is to the right of rightU |
| if(segIndexLarge < rightEnd) |
| { |
| Real *tempTop; |
| if(segIndexLarge >= rightStart) |
| tempTop = rightChain->getVertex(segIndexLarge); |
| else |
| tempTop = topVertex; |
| Real tempBot[2]; |
| tempBot[0] = grid->get_u_value(rightU); |
| tempBot[1] = grid->get_v_value(gridV); |
| monoTriangulationRecGenOpt(tempTop, tempBot, |
| NULL, 1,0, |
| rightChain, segIndexLarge+1, rightEnd, |
| pStream); |
| /* |
| monoTriangulation2(tempTop, tempBot, |
| rightChain, |
| segIndexLarge+1, |
| rightEnd, |
| 0, //a decrease chian |
| pStream); |
| */ |
| |
| } |
| |
| //the possible section which is strictly Umonotone |
| if(segIndexLarge >= rightStart) |
| { |
| stripOfFanRight(rightChain, segIndexLarge, segIndexSmall, grid, gridV, leftU, rightU, pStream, 0); |
| Real tempBot[2]; |
| tempBot[0] = grid->get_u_value(leftU); |
| tempBot[1] = grid->get_v_value(gridV); |
| monoTriangulation2(topVertex, tempBot, rightChain, rightStart, segIndexSmall, 0, pStream); |
| } |
| else //the topVertex forms a fan with the grid points |
| grid->outputFanWithPoint(gridV, leftU, rightU, topVertex, pStream); |
| } |
| |
| void sampleTopRightWithGridLine(Real* topVertex, |
| vertexArray* rightChain, |
| Int rightStart, |
| Int rightEnd, |
| gridWrap* grid, |
| Int gridV, |
| Int leftU, |
| Int rightU, |
| primStream* pStream |
| ) |
| { |
| //if right chian is empty, then there is only one topVertex with one grid line |
| if(rightEnd < rightStart){ |
| grid->outputFanWithPoint(gridV, leftU, rightU, topVertex, pStream); |
| return; |
| } |
| |
| Int segIndexSmall, segIndexLarge; |
| findTopRightSegment(rightChain, |
| rightStart, |
| rightEnd, |
| grid->get_u_value(rightU), |
| segIndexSmall, |
| segIndexLarge |
| ); |
| sampleTopRightWithGridLinePost(topVertex, rightChain, |
| rightStart, |
| segIndexSmall, |
| segIndexLarge, |
| rightEnd, |
| grid, |
| gridV, |
| leftU, |
| rightU, |
| pStream); |
| } |
| |
| |
| void sampleTopLeftWithGridLinePost(Real* topVertex, |
| vertexArray* leftChain, |
| Int leftStart, |
| Int segIndexSmall, |
| Int segIndexLarge, |
| Int leftEnd, |
| gridWrap* grid, |
| Int gridV, |
| Int leftU, |
| Int rightU, |
| primStream* pStream) |
| { |
| //the possible section which is to the left of leftU |
| |
| if(segIndexLarge < leftEnd) |
| { |
| Real *tempTop; |
| if(segIndexLarge >= leftStart) |
| tempTop = leftChain->getVertex(segIndexLarge); |
| else |
| tempTop = topVertex; |
| Real tempBot[2]; |
| tempBot[0] = grid->get_u_value(leftU); |
| tempBot[1] = grid->get_v_value(gridV); |
| |
| monoTriangulation2(tempTop, tempBot, |
| leftChain, |
| segIndexLarge+1, |
| leftEnd, |
| 1, //a increase chian |
| pStream); |
| } |
| |
| //the possible section which is strictly Umonotone |
| if(segIndexLarge >= leftStart) |
| { |
| //if there are grid points which are to the right of topV, |
| //then we should use topVertex to form a fan with these points to |
| //optimize the triangualtion |
| int do_optimize=1; |
| if(topVertex[0] >= grid->get_u_value(rightU)) |
| do_optimize = 0; |
| else |
| { |
| //we also have to make sure that topVertex are the right most vertex |
| //on the chain. |
| int i; |
| for(i=leftStart; i<=segIndexSmall; i++) |
| if(leftChain->getVertex(i)[0] >= topVertex[0]) |
| { |
| do_optimize = 0; |
| break; |
| } |
| } |
| |
| if(do_optimize) |
| { |
| //find midU so that grid->get_u_value(midU) >= topVertex[0] |
| //and grid->get_u_value(midU-1) < topVertex[0] |
| int midU=rightU; |
| while(grid->get_u_value(midU) >= topVertex[0]) |
| { |
| midU--; |
| if(midU < leftU) |
| break; |
| } |
| midU++; |
| |
| grid->outputFanWithPoint(gridV, midU, rightU, topVertex, pStream); |
| stripOfFanLeft(leftChain, segIndexLarge, segIndexSmall, grid, gridV, leftU, midU, pStream, 0); |
| Real tempBot[2]; |
| tempBot[0] = grid->get_u_value(midU); |
| tempBot[1] = grid->get_v_value(gridV); |
| monoTriangulation2(topVertex, tempBot, leftChain, leftStart, segIndexSmall, 1, pStream); |
| } |
| else //not optimize |
| { |
| |
| stripOfFanLeft(leftChain, segIndexLarge, segIndexSmall, grid, gridV, leftU, rightU, pStream, 0); |
| Real tempBot[2]; |
| tempBot[0] = grid->get_u_value(rightU); |
| tempBot[1] = grid->get_v_value(gridV); |
| monoTriangulation2(topVertex, tempBot, leftChain, leftStart, segIndexSmall, 1, pStream); |
| } |
| } |
| else //the topVertex forms a fan with the grid points |
| grid->outputFanWithPoint(gridV, leftU, rightU, topVertex, pStream); |
| } |
| |
| |
| void sampleTopLeftWithGridLine(Real* topVertex, |
| vertexArray* leftChain, |
| Int leftStart, |
| Int leftEnd, |
| gridWrap* grid, |
| Int gridV, |
| Int leftU, |
| Int rightU, |
| primStream* pStream |
| ) |
| { |
| Int segIndexSmall, segIndexLarge; |
| //if left chain is empty, then there is only one top vertex with one grid |
| // line |
| if(leftEnd < leftStart) { |
| grid->outputFanWithPoint(gridV, leftU, rightU, topVertex, pStream); |
| return; |
| } |
| findTopLeftSegment(leftChain, |
| leftStart, |
| leftEnd, |
| grid->get_u_value(leftU), |
| segIndexSmall, |
| segIndexLarge |
| ); |
| sampleTopLeftWithGridLinePost(topVertex, |
| leftChain, |
| leftStart, |
| segIndexSmall, |
| segIndexLarge, |
| leftEnd, |
| grid, |
| gridV, |
| leftU, |
| rightU, |
| pStream); |
| } |
| |
| |
| //return 1 if saprator exits, 0 otherwise |
| Int findTopSeparator(vertexArray* leftChain, |
| Int leftStartIndex, |
| Int leftEndIndex, |
| vertexArray* rightChain, |
| Int rightStartIndex, |
| Int rightEndIndex, |
| Int& ret_sep_left, |
| Int& ret_sep_right) |
| { |
| |
| Int oldLeftI, oldRightI, newLeftI, newRightI; |
| Int i,j,k; |
| Real leftMax /*= leftChain->getVertex(leftEndIndex)[0]*/; |
| Real rightMin /*= rightChain->getVertex(rightEndIndex)[0]*/; |
| if(leftChain->getVertex(leftEndIndex)[1] > rightChain->getVertex(rightEndIndex)[1]) //left higher |
| { |
| oldLeftI = leftEndIndex+1; |
| oldRightI = rightEndIndex; |
| leftMax = leftChain->getVertex(leftEndIndex)[0] - Real(1.0); //initilza to left of leftU |
| rightMin = rightChain->getVertex(rightEndIndex)[0]; |
| } |
| else |
| { |
| oldLeftI = leftEndIndex; |
| oldRightI = rightEndIndex+1; |
| leftMax = leftChain->getVertex(leftEndIndex)[0]; |
| rightMin = rightChain->getVertex(rightEndIndex)[0] + Real(1.0); |
| } |
| |
| //i: the current working leftChain index, |
| //j: the current working rightChain index, |
| //if left(i) is higher than right(j), then the two chains beloew right(j) are separated. |
| //else the two chains below left(i) are separeated. |
| i=leftEndIndex; |
| j=rightEndIndex; |
| while(1) |
| { |
| newLeftI = oldLeftI; |
| newRightI = oldRightI; |
| |
| if(i<leftStartIndex) //left chain is done, go through remining right chain. |
| { |
| for(k=j-1; k>= rightStartIndex; k--) |
| { |
| if(rightChain->getVertex(k)[0] > leftMax) //no conflict |
| { |
| //update oldRightI if necessary |
| if(rightChain->getVertex(k)[0] < rightMin) |
| { |
| rightMin = rightChain->getVertex(k)[0]; |
| oldRightI = k; |
| } |
| } |
| else //there is a conflict |
| break; //the for-loop. below right(k-1) is seperated: oldLeftI, oldRightI. |
| } |
| break; //the while loop |
| } |
| else if(j<rightStartIndex) //rightChain is done |
| { |
| for(k=i-1; k>= leftStartIndex; k--) |
| { |
| if(leftChain->getVertex(k)[0] < rightMin) //no conflict |
| { |
| //update oldLeftI if necessary |
| if(leftChain->getVertex(k)[0] > leftMax) |
| { |
| leftMax = leftChain->getVertex(k)[0]; |
| oldLeftI = k; |
| } |
| } |
| else //there is a conflict |
| break; //the for loop |
| } |
| break; //the while loop |
| } |
| else if(leftChain->getVertex(i)[1] > rightChain->getVertex(j)[1]) //left hgiher |
| { |
| if(leftChain->getVertex(i)[0] > leftMax) //update leftMax and newLeftI. |
| { |
| leftMax = leftChain->getVertex(i)[0]; |
| newLeftI = i; |
| } |
| for(k=j-1; k>= rightStartIndex; k--) //update rightMin and newRightI. |
| { |
| if(rightChain->getVertex(k)[1] > leftChain->getVertex(i)[1]) |
| break; |
| if(rightChain->getVertex(k)[0] < rightMin) |
| { |
| rightMin = rightChain->getVertex(k)[0]; |
| newRightI = k; |
| } |
| } |
| j = k; //next working j, since j will be higher than i in next loop |
| if(leftMax >= rightMin) //there is a conflict |
| break; |
| else //still no conflict |
| { |
| oldLeftI = newLeftI; |
| oldRightI = newRightI; |
| } |
| } |
| else //right higher |
| { |
| if(rightChain->getVertex(j)[0] < rightMin) |
| { |
| rightMin = rightChain->getVertex(j)[0]; |
| newRightI = j; |
| } |
| for(k=i-1; k>= leftStartIndex; k--) |
| { |
| if(leftChain->getVertex(k)[1] > rightChain->getVertex(j)[1]) |
| break; |
| if(leftChain->getVertex(k)[0] > leftMax) |
| { |
| leftMax = leftChain->getVertex(k)[0]; |
| newLeftI = k; |
| } |
| } |
| i = k; //next working i, since i will be higher than j next loop |
| |
| if(leftMax >= rightMin) //there is a conflict |
| break; |
| else //still no conflict |
| { |
| oldLeftI = newLeftI; |
| oldRightI = newRightI; |
| } |
| } |
| }//end of while loop |
| //now oldLeftI and oldRightI are the desired separeator index, notice that there are not necessarily valid |
| if(oldLeftI > leftEndIndex || oldRightI > rightEndIndex) |
| return 0; |
| else |
| { |
| ret_sep_left = oldLeftI; |
| ret_sep_right = oldRightI; |
| return 1; |
| } |
| } |
| |
| |
| void sampleCompTop(Real* topVertex, |
| vertexArray* leftChain, |
| Int leftStartIndex, |
| vertexArray* rightChain, |
| Int rightStartIndex, |
| gridBoundaryChain* leftGridChain, |
| gridBoundaryChain* rightGridChain, |
| Int gridIndex1, |
| Int up_leftCornerWhere, |
| Int up_leftCornerIndex, |
| Int up_rightCornerWhere, |
| Int up_rightCornerIndex, |
| primStream* pStream) |
| { |
| if(up_leftCornerWhere == 1 && up_rightCornerWhere == 1) //the top is topVertex with possible grid points |
| { |
| leftGridChain->getGrid()->outputFanWithPoint(leftGridChain->getVlineIndex(gridIndex1), |
| leftGridChain->getUlineIndex(gridIndex1), |
| rightGridChain->getUlineIndex(gridIndex1), |
| topVertex, |
| pStream); |
| return; |
| } |
| |
| else if(up_leftCornerWhere != 0) |
| { |
| Real* tempTop; |
| Int tempRightStart; |
| if(up_leftCornerWhere == 1){ |
| tempRightStart = rightStartIndex; |
| tempTop = topVertex; |
| } |
| else |
| { |
| tempRightStart = up_leftCornerIndex+1; |
| tempTop = rightChain->getVertex(up_leftCornerIndex); |
| } |
| sampleTopRightWithGridLine(tempTop, rightChain, tempRightStart, up_rightCornerIndex, |
| rightGridChain->getGrid(), |
| leftGridChain->getVlineIndex(gridIndex1), |
| leftGridChain->getUlineIndex(gridIndex1), |
| rightGridChain->getUlineIndex(gridIndex1), |
| pStream); |
| } |
| else if(up_rightCornerWhere != 2) |
| { |
| Real* tempTop; |
| Int tempLeftStart; |
| if(up_rightCornerWhere == 1) |
| { |
| tempLeftStart = leftStartIndex; |
| tempTop = topVertex; |
| } |
| else //0 |
| { |
| tempLeftStart = up_rightCornerIndex+1; |
| tempTop = leftChain->getVertex(up_rightCornerIndex); |
| } |
| /* |
| sampleTopLeftWithGridLine(tempTop, leftChain, tempLeftStart, up_leftCornerIndex, |
| leftGridChain->getGrid(), |
| leftGridChain->getVlineIndex(gridIndex1), |
| leftGridChain->getUlineIndex(gridIndex1), |
| rightGridChain->getUlineIndex(gridIndex1), |
| pStream); |
| */ |
| sampleCompTopSimple(topVertex, |
| leftChain, |
| leftStartIndex, |
| rightChain, |
| rightStartIndex, |
| leftGridChain, |
| rightGridChain, |
| gridIndex1, |
| up_leftCornerWhere, |
| up_leftCornerIndex, |
| up_rightCornerWhere, |
| up_rightCornerIndex, |
| pStream); |
| } |
| else //up_leftCornerWhere == 0, up_rightCornerWhere == 2. |
| { |
| sampleCompTopSimple(topVertex, |
| leftChain, |
| leftStartIndex, |
| rightChain, |
| rightStartIndex, |
| leftGridChain, |
| rightGridChain, |
| gridIndex1, |
| up_leftCornerWhere, |
| up_leftCornerIndex, |
| up_rightCornerWhere, |
| up_rightCornerIndex, |
| pStream); |
| return; |
| #ifdef NOT_REACHABLE //code is not reachable, for test purpose only |
| //the following code is trying to do some optimization, but not quite working, also see sampleCompBot.C: |
| Int sep_left, sep_right; |
| if(findTopSeparator(leftChain, |
| leftStartIndex, |
| up_leftCornerIndex, |
| rightChain, |
| rightStartIndex, |
| up_rightCornerIndex, |
| sep_left, |
| sep_right) |
| ) //separator exists |
| { |
| |
| if( leftChain->getVertex(sep_left)[0] >= leftGridChain->get_u_value(gridIndex1) && |
| rightChain->getVertex(sep_right)[0] <= rightGridChain->get_u_value(gridIndex1)) |
| { |
| Int gridSep; |
| Int segLeftSmall, segLeftLarge, segRightSmall, segRightLarge; |
| Int valid=1; //whether the gridStep is valid or not. |
| findTopLeftSegment(leftChain, |
| sep_left, |
| up_leftCornerIndex, |
| leftGridChain->get_u_value(gridIndex1), |
| segLeftSmall, |
| segLeftLarge); |
| findTopRightSegment(rightChain, |
| sep_right, |
| up_rightCornerIndex, |
| rightGridChain->get_u_value(gridIndex1), |
| segRightSmall, |
| segRightLarge); |
| if(leftChain->getVertex(segLeftSmall)[1] >= rightChain->getVertex(segRightSmall)[1]) |
| { |
| gridSep = rightGridChain->getUlineIndex(gridIndex1); |
| while(leftGridChain->getGrid()->get_u_value(gridSep) > leftChain->getVertex(segLeftSmall)[0]) |
| gridSep--; |
| if(segLeftSmall<segLeftLarge) |
| if(leftGridChain->getGrid()->get_u_value(gridSep) < leftChain->getVertex(segLeftSmall+1)[0]) |
| { |
| valid = 0; |
| } |
| } |
| else |
| { |
| gridSep = leftGridChain->getUlineIndex(gridIndex1); |
| while(leftGridChain->getGrid()->get_u_value(gridSep) < rightChain->getVertex(segRightSmall)[0]) |
| gridSep++; |
| if(segRightSmall<segRightLarge) |
| if(leftGridChain->getGrid()->get_u_value(gridSep) > rightChain->getVertex(segRightSmall+1)[0]) |
| { |
| valid = 0; |
| } |
| } |
| |
| if(! valid) |
| { |
| sampleCompTopSimple(topVertex, |
| leftChain, |
| leftStartIndex, |
| rightChain, |
| rightStartIndex, |
| leftGridChain, |
| rightGridChain, |
| gridIndex1, |
| up_leftCornerWhere, |
| up_leftCornerIndex, |
| up_rightCornerWhere, |
| up_rightCornerIndex, |
| pStream); |
| } |
| else |
| { |
| sampleTopLeftWithGridLinePost(leftChain->getVertex(segLeftSmall), |
| leftChain, |
| segLeftSmall+1, |
| segLeftSmall+1, |
| segLeftLarge, |
| up_leftCornerIndex, |
| leftGridChain->getGrid(), |
| leftGridChain->getVlineIndex(gridIndex1), |
| leftGridChain->getUlineIndex(gridIndex1), |
| gridSep, |
| pStream); |
| sampleTopRightWithGridLinePost(rightChain->getVertex(segRightSmall), |
| rightChain, |
| segRightSmall+1, |
| segRightSmall+1, |
| segRightLarge, |
| up_rightCornerIndex, |
| leftGridChain->getGrid(), |
| leftGridChain->getVlineIndex(gridIndex1), |
| gridSep, |
| rightGridChain->getUlineIndex(gridIndex1), |
| pStream); |
| Real tempBot[2]; |
| tempBot[0] = leftGridChain->getGrid()->get_u_value(gridSep); |
| tempBot[1] = leftGridChain->get_v_value(gridIndex1); |
| monoTriangulationRecGen(topVertex, tempBot, |
| leftChain, leftStartIndex, segLeftSmall, |
| rightChain, rightStartIndex, segRightSmall, |
| pStream); |
| } |
| }//end if both sides have vetices inside the gridboundary points |
| else if(leftChain->getVertex(sep_left)[0] >= leftGridChain->get_u_value(gridIndex1)) //left is in, right is nout |
| { |
| |
| Int segLeftSmall, segLeftLarge; |
| findTopLeftSegment(leftChain, |
| sep_left, |
| up_leftCornerIndex, |
| leftGridChain->get_u_value(gridIndex1), |
| segLeftSmall, |
| segLeftLarge); |
| assert(segLeftLarge >= sep_left); |
| monoTriangulation2(leftChain->getVertex(segLeftLarge), |
| leftGridChain->get_vertex(gridIndex1), |
| leftChain, |
| segLeftLarge+1, |
| up_leftCornerIndex, |
| 1, //a increase chain, |
| pStream); |
| |
| stripOfFanLeft(leftChain, segLeftLarge, segLeftSmall, |
| leftGridChain->getGrid(), |
| leftGridChain->getVlineIndex(gridIndex1), |
| leftGridChain->getUlineIndex(gridIndex1), |
| rightGridChain->getUlineIndex(gridIndex1), |
| pStream, 0); |
| |
| |
| monoTriangulationRecGen(topVertex, rightGridChain->get_vertex(gridIndex1), |
| leftChain, leftStartIndex, segLeftSmall, |
| rightChain, rightStartIndex, up_rightCornerIndex, |
| pStream); |
| }//end left in right out |
| else if(rightChain->getVertex(sep_right)[0] <= rightGridChain->get_u_value(gridIndex1)) |
| { |
| Int segRightSmall, segRightLarge; |
| findTopRightSegment(rightChain, |
| sep_right, |
| up_rightCornerIndex, |
| rightGridChain->get_u_value(gridIndex1), |
| segRightSmall, |
| segRightLarge); |
| assert(segRightLarge>=sep_right); |
| monoTriangulation2(rightChain->getVertex(segRightLarge), |
| rightGridChain->get_vertex(gridIndex1), |
| rightChain, |
| segRightLarge+1, |
| up_rightCornerIndex, |
| 0, //a decrease chain |
| pStream); |
| stripOfFanRight(rightChain, segRightLarge, segRightSmall, |
| rightGridChain->getGrid(), |
| rightGridChain->getVlineIndex(gridIndex1), |
| leftGridChain->getUlineIndex(gridIndex1), |
| rightGridChain->getUlineIndex(gridIndex1), |
| pStream, 0); |
| |
| |
| monoTriangulationRecGen(topVertex, leftGridChain->get_vertex(gridIndex1), |
| leftChain, leftStartIndex, up_leftCornerIndex, |
| rightChain, rightStartIndex,segRightSmall, |
| pStream); |
| |
| }//end left out rigth in |
| else //left out , right out |
| { |
| |
| sampleCompTopSimple(topVertex, |
| leftChain, |
| leftStartIndex, |
| rightChain, |
| rightStartIndex, |
| leftGridChain, |
| rightGridChain, |
| gridIndex1, |
| up_leftCornerWhere, |
| up_leftCornerIndex, |
| up_rightCornerWhere, |
| up_rightCornerIndex, |
| pStream); |
| }//end leftout, right out |
| }//end if separator exixts. |
| else //no separator |
| { |
| |
| sampleCompTopSimple(topVertex, |
| leftChain, |
| leftStartIndex, |
| rightChain, |
| rightStartIndex, |
| leftGridChain, |
| rightGridChain, |
| gridIndex1, |
| up_leftCornerWhere, |
| up_leftCornerIndex, |
| up_rightCornerWhere, |
| up_rightCornerIndex, |
| pStream); |
| } |
| #endif |
| }//end if 0,2 |
| }//end if the function |
| |
| |
| static void sampleCompTopSimpleOpt(gridWrap* grid, |
| Int gridV, |
| Real* topVertex, Real* botVertex, |
| vertexArray* inc_chain, Int inc_current, Int inc_end, |
| vertexArray* dec_chain, Int dec_current, Int dec_end, |
| primStream* pStream) |
| { |
| if(gridV <= 0 || dec_end<dec_current || inc_end <inc_current) |
| { |
| monoTriangulationRecGenOpt(topVertex, botVertex, |
| inc_chain, inc_current, inc_end, |
| dec_chain, dec_current, dec_end, |
| pStream); |
| return; |
| } |
| if(grid->get_v_value(gridV+1) >= topVertex[1]) |
| { |
| monoTriangulationRecGenOpt(topVertex, botVertex, |
| inc_chain, inc_current, inc_end, |
| dec_chain, dec_current, dec_end, |
| pStream); |
| return; |
| } |
| Int i,j,k; |
| Real currentV = grid->get_v_value(gridV+1); |
| if(inc_chain->getVertex(inc_end)[1] <= currentV && |
| dec_chain->getVertex(dec_end)[1] < currentV) |
| { |
| //find i bottom up so that inc_chain[i]<= curentV and inc_chain[i-1] > currentV, |
| //find j botom up so that dec_chain[j] < currentV and dec_chain[j-1] >= currentV |
| for(i=inc_end; i >= inc_current; i--) |
| { |
| if(inc_chain->getVertex(i)[1] > currentV) |
| break; |
| } |
| i++; |
| for(j=dec_end; j >= dec_current; j--) |
| { |
| if(dec_chain->getVertex(j)[1] >= currentV) |
| break; |
| } |
| j++; |
| if(inc_chain->getVertex(i)[1] <= dec_chain->getVertex(j)[1]) |
| { |
| //find the k so that dec_chain[k][1] < inc_chain[i][1] |
| for(k=j; k<=dec_end; k++) |
| { |
| if(dec_chain->getVertex(k)[1] < inc_chain->getVertex(i)[1]) |
| break; |
| } |
| //we know that dec_chain[j][1] >= inc_chian[i][1] |
| //we know that dec_chain[k-1][1]>=inc_chain[i][1] |
| //we know that dec_chian[k][1] < inc_chain[i][1] |
| //find l in [j, k-1] so that dec_chain[l][0] 0 is closest to |
| // inc_chain[i] |
| int l; |
| Real tempI = Real(j); |
| Real tempMin = (Real)fabs(inc_chain->getVertex(i)[0] - dec_chain->getVertex(j)[0]); |
| for(l=j+1; l<= k-1; l++) |
| { |
| if(fabs(inc_chain->getVertex(i)[0] - dec_chain->getVertex(l)[0]) |
| <= tempMin) |
| { |
| tempMin = (Real)fabs(inc_chain->getVertex(i)[0] - dec_chain->getVertex(l)[0]); |
| tempI = (Real)l; |
| } |
| } |
| //inc_chain[i] and dec_chain[tempI] are connected. |
| monoTriangulationRecGenOpt(dec_chain->getVertex((int)tempI), |
| botVertex, |
| inc_chain, i, inc_end, |
| dec_chain, (int)(tempI+1), dec_end, |
| pStream); |
| //recursively do the rest |
| sampleCompTopSimpleOpt(grid, |
| gridV+1, |
| topVertex, inc_chain->getVertex(i), |
| inc_chain, inc_current, i-1, |
| dec_chain, dec_current, (int)tempI, |
| pStream); |
| } |
| else |
| { |
| //find the k so that inc_chain[k][1] <= dec_chain[j][1] |
| for(k=i; k<=inc_end; k++) |
| { |
| if(inc_chain->getVertex(k)[1] <= dec_chain->getVertex(j)[1]) |
| break; |
| } |
| //we know that inc_chain[i] > dec_chain[j] |
| //we know that inc_chain[k-1][1] > dec_chain[j][1] |
| //we know that inc_chain[k][1] <= dec_chain[j][1] |
| //so we find l between [i,k-1] so that |
| //inc_chain[l][0] is the closet to dec_chain[j][0] |
| int tempI = i; |
| int l; |
| Real tempMin = (Real)fabs(inc_chain->getVertex(i)[0] - dec_chain->getVertex(j)[0]); |
| for(l=i+1; l<=k-1; l++) |
| { |
| if(fabs(inc_chain->getVertex(l)[0] - dec_chain->getVertex(j)[0]) <= tempMin) |
| { |
| tempMin = (Real)fabs(inc_chain->getVertex(l)[0] - dec_chain->getVertex(j)[0]); |
| tempI = l; |
| } |
| } |
| |
| //inc_chain[tempI] and dec_chain[j] are connected |
| |
| monoTriangulationRecGenOpt(inc_chain->getVertex(tempI), |
| botVertex, |
| inc_chain, tempI+1, inc_end, |
| dec_chain, j, dec_end, |
| pStream); |
| |
| //recurvesily do the rest |
| sampleCompTopSimpleOpt(grid, gridV+1, |
| topVertex, dec_chain->getVertex(j), |
| inc_chain, inc_current, tempI, |
| dec_chain, dec_current, j-1, |
| pStream); |
| } |
| } |
| else //go to the next higher gridV |
| { |
| sampleCompTopSimpleOpt(grid, |
| gridV+1, |
| topVertex, botVertex, |
| inc_chain, inc_current, inc_end, |
| dec_chain, dec_current, dec_end, |
| pStream); |
| } |
| } |
| |
| void sampleCompTopSimple(Real* topVertex, |
| vertexArray* leftChain, |
| Int leftStartIndex, |
| vertexArray* rightChain, |
| Int rightStartIndex, |
| gridBoundaryChain* leftGridChain, |
| gridBoundaryChain* rightGridChain, |
| Int gridIndex1, |
| Int up_leftCornerWhere, |
| Int up_leftCornerIndex, |
| Int up_rightCornerWhere, |
| Int up_rightCornerIndex, |
| primStream* pStream) |
| { |
| //the plan is to use monotriangulation algortihm. |
| Int i,k; |
| Real* ActualTop; |
| Real* ActualBot; |
| Int ActualLeftStart, ActualLeftEnd; |
| Int ActualRightStart, ActualRightEnd; |
| |
| //creat an array to store the points on the grid line |
| gridWrap* grid = leftGridChain->getGrid(); |
| Int gridV = leftGridChain->getVlineIndex(gridIndex1); |
| Int gridLeftU = leftGridChain->getUlineIndex(gridIndex1); |
| Int gridRightU = rightGridChain->getUlineIndex(gridIndex1); |
| |
| Real2* gridPoints = (Real2*) malloc(sizeof(Real2) * (gridRightU - gridLeftU +1)); |
| assert(gridPoints); |
| |
| for(k=0, i=gridRightU; i>= gridLeftU; i--, k++) |
| { |
| gridPoints[k][0] = grid->get_u_value(i); |
| gridPoints[k][1] = grid->get_v_value(gridV); |
| } |
| |
| if(up_leftCornerWhere != 2) |
| ActualRightStart = rightStartIndex; |
| else |
| ActualRightStart = up_leftCornerIndex+1; //up_leftCornerIndex will be the ActualTop |
| |
| if(up_rightCornerWhere != 2) //right corner is not on right chain |
| ActualRightEnd = rightStartIndex-1; //meaning that there is no actual rigth section |
| else |
| ActualRightEnd = up_rightCornerIndex; |
| |
| vertexArray ActualRightChain(max(0, ActualRightEnd-ActualRightStart+1) + gridRightU-gridLeftU+1); |
| |
| for(i=ActualRightStart; i<= ActualRightEnd; i++) |
| ActualRightChain.appendVertex(rightChain->getVertex(i)); |
| for(i=0; i<gridRightU-gridLeftU+1; i++) |
| ActualRightChain.appendVertex(gridPoints[i]); |
| |
| //determine ActualLeftEnd |
| if(up_leftCornerWhere != 0) |
| ActualLeftEnd = leftStartIndex-1; |
| else |
| ActualLeftEnd = up_leftCornerIndex; |
| |
| if(up_rightCornerWhere != 0) |
| ActualLeftStart = leftStartIndex; |
| else |
| ActualLeftStart = up_rightCornerIndex+1; //up_rightCornerIndex will be the actual top |
| |
| if(up_leftCornerWhere == 0) |
| { |
| if(up_rightCornerWhere == 0) |
| ActualTop = leftChain->getVertex(up_rightCornerIndex); |
| else |
| ActualTop = topVertex; |
| } |
| else if(up_leftCornerWhere == 1) |
| ActualTop = topVertex; |
| else //up_leftCornerWhere == 2 |
| ActualTop = rightChain->getVertex(up_leftCornerIndex); |
| |
| ActualBot = gridPoints[gridRightU - gridLeftU]; |
| |
| |
| |
| |
| if(leftChain->getVertex(ActualLeftEnd)[1] == ActualBot[1]) |
| { |
| /* |
| monoTriangulationRecGenOpt(ActualTop, leftChain->getVertex(ActualLeftEnd), |
| leftChain, |
| ActualLeftStart, ActualLeftEnd-1, |
| &ActualRightChain, |
| 0, |
| ActualRightChain.getNumElements()-1, |
| pStream); |
| */ |
| |
| sampleCompTopSimpleOpt(grid, gridV, |
| ActualTop, leftChain->getVertex(ActualLeftEnd), |
| leftChain, |
| ActualLeftStart, ActualLeftEnd-1, |
| &ActualRightChain, |
| 0, |
| ActualRightChain.getNumElements()-1, |
| pStream); |
| |
| } |
| else |
| { |
| /* |
| monoTriangulationRecGenOpt(ActualTop, ActualBot, leftChain, |
| ActualLeftStart, ActualLeftEnd, |
| &ActualRightChain, |
| 0, ActualRightChain.getNumElements()-2, //the last is the bot. |
| pStream); |
| */ |
| |
| sampleCompTopSimpleOpt(grid, gridV, |
| ActualTop, ActualBot, leftChain, |
| ActualLeftStart, ActualLeftEnd, |
| &ActualRightChain, |
| 0, ActualRightChain.getNumElements()-2, //the last is the bot. |
| pStream); |
| |
| |
| } |
| |
| free(gridPoints); |
| |
| } |
| |
