summaryrefslogtreecommitdiffstats
path: root/src/glu/sgi/libnurbs/nurbtess/sampleCompTop.cc
diff options
context:
space:
mode:
Diffstat (limited to 'src/glu/sgi/libnurbs/nurbtess/sampleCompTop.cc')
-rw-r--r--src/glu/sgi/libnurbs/nurbtess/sampleCompTop.cc1032
1 files changed, 1032 insertions, 0 deletions
diff --git a/src/glu/sgi/libnurbs/nurbtess/sampleCompTop.cc b/src/glu/sgi/libnurbs/nurbtess/sampleCompTop.cc
new file mode 100644
index 00000000000..76a36e06e2d
--- /dev/null
+++ b/src/glu/sgi/libnurbs/nurbtess/sampleCompTop.cc
@@ -0,0 +1,1032 @@
+/*
+** 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: 2001/03/17 00:25:41 $ $Revision: 1.1 $
+*/
+/*
+** $Header: /home/krh/git/sync/mesa-cvs-repo/Mesa/src/glu/sgi/libnurbs/nurbtess/sampleCompTop.cc,v 1.1 2001/03/17 00:25:41 brianp 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] - 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] + 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 = j;
+ Real tempMin = 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 = fabs(inc_chain->getVertex(i)[0] - dec_chain->getVertex(l)[0]);
+ tempI = l;
+ }
+ }
+ //inc_chain[i] and dec_chain[tempI] are connected.
+ monoTriangulationRecGenOpt(dec_chain->getVertex(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 = 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 = 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);
+
+}
+
generated by cgit v1.2.3 (git 2.39.1) at 2024-12-22 05:50:47 +0000