diff options
Diffstat (limited to 'mesalib/src/glu/sgi/libnurbs/nurbtess/sampleCompTop.cc')
| -rw-r--r-- | mesalib/src/glu/sgi/libnurbs/nurbtess/sampleCompTop.cc | 1030 |
1 files changed, 0 insertions, 1030 deletions
diff --git a/mesalib/src/glu/sgi/libnurbs/nurbtess/sampleCompTop.cc b/mesalib/src/glu/sgi/libnurbs/nurbtess/sampleCompTop.cc deleted file mode 100644 index 951e937c4..000000000 --- a/mesalib/src/glu/sgi/libnurbs/nurbtess/sampleCompTop.cc +++ /dev/null @@ -1,1030 +0,0 @@ -/* -** License Applicability. Except to the extent portions of this file are -** made subject to an alternative license as permitted in the SGI Free -** Software License B, Version 1.1 (the "License"), the contents of this -** file are subject only to the provisions of the License. You may not use -** this file except in compliance with the License. You may obtain a copy -** of the License at Silicon Graphics, Inc., attn: Legal Services, 1600 -** Amphitheatre Parkway, Mountain View, CA 94043-1351, or at: -** -** http://oss.sgi.com/projects/FreeB -** -** Note that, as provided in the License, the Software is distributed on an -** "AS IS" basis, with ALL EXPRESS AND IMPLIED WARRANTIES AND CONDITIONS -** DISCLAIMED, INCLUDING, WITHOUT LIMITATION, ANY IMPLIED WARRANTIES AND -** CONDITIONS OF MERCHANTABILITY, SATISFACTORY QUALITY, FITNESS FOR A -** PARTICULAR PURPOSE, AND NON-INFRINGEMENT. -** -** Original Code. The Original Code is: OpenGL Sample Implementation, -** Version 1.2.1, released January 26, 2000, developed by Silicon Graphics, -** Inc. The Original Code is Copyright (c) 1991-2000 Silicon Graphics, Inc. -** Copyright in any portions created by third parties is as indicated -** elsewhere herein. All Rights Reserved. -** -** Additional Notice Provisions: The application programming interfaces -** established by SGI in conjunction with the Original Code are The -** OpenGL(R) Graphics System: A Specification (Version 1.2.1), released -** April 1, 1999; The OpenGL(R) Graphics System Utility Library (Version -** 1.3), released November 4, 1998; and OpenGL(R) Graphics with the X -** Window System(R) (Version 1.3), released October 19, 1998. This software -** was created using the OpenGL(R) version 1.2.1 Sample Implementation -** published by SGI, but has not been independently verified as being -** compliant with the OpenGL(R) version 1.2.1 Specification. -** -*/ -/* -*/ - -#include <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 = 0, 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 = 0, 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); - -} - |