#include <stdlib.h>
#include <stdio.h>
#include "zlassert.h"
#include "sampleCompBot.h"
#include "sampleCompRight.h"
#define max(a,b) ((a>b)? a:b)
void findBotLeftSegment(vertexArray* leftChain,
Int leftEnd,
Int leftCorner,
Real u,
Int& ret_index_mono,
Int& ret_index_pass)
{
Int i;
assert(leftCorner <= leftEnd);
for(i=leftCorner; i<= leftEnd; i++)
if(leftChain->getVertex(i)[0] >= u)
break;
ret_index_pass = i;
if(ret_index_pass <= leftEnd)
{
for(i=ret_index_pass; i< leftEnd; i++)
{
if(leftChain->getVertex(i+1)[0] <= leftChain->getVertex(i)[0])
break;
}
ret_index_mono = i;
}
}
void findBotRightSegment(vertexArray* rightChain,
Int rightEnd,
Int rightCorner,
Real u,
Int& ret_index_mono,
Int& ret_index_pass)
{
Int i;
assert(rightCorner <= rightEnd);
for(i=rightCorner; i<= rightEnd; i++)
if(rightChain->getVertex(i)[0] <= u)
break;
ret_index_pass = i;
if(ret_index_pass <= rightEnd)
{
for(i=ret_index_pass; i< rightEnd; i++)
{
if(rightChain->getVertex(i+1)[0] >= rightChain->getVertex(i)[0])
break;
}
ret_index_mono = i;
}
}
void sampleBotRightWithGridLinePost(Real* botVertex,
vertexArray* rightChain,
Int rightEnd,
Int segIndexMono,
Int segIndexPass,
Int rightCorner,
gridWrap* grid,
Int gridV,
Int leftU,
Int rightU,
primStream* pStream)
{
if(segIndexPass > rightCorner) {
Real *tempBot;
if(segIndexPass <= rightEnd) tempBot = rightChain->getVertex(segIndexPass);
else tempBot = botVertex;
Real tempTop[2];
tempTop[0] = grid->get_u_value(rightU);
tempTop[1] = grid->get_v_value(gridV);
monoTriangulation2(tempTop, tempBot,
rightChain,
rightCorner,
segIndexPass-1,
0, pStream);
}
if(segIndexPass <= rightEnd) {
int do_optimize = 1;
if(botVertex[0] <= grid->get_u_value(leftU))
do_optimize = 0;
else
{
int i;
for(i=segIndexMono; i<=rightEnd; i++)
if(rightChain->getVertex(i)[0] <= botVertex[0])
{
do_optimize = 0;
break;
}
}
if(do_optimize)
{
int midU = leftU;
while(grid->get_u_value(midU) <= botVertex[0])
{
midU++;
if(midU > rightU)
break;
}
midU--;
grid->outputFanWithPoint(gridV, leftU, midU, botVertex, pStream);
stripOfFanRight(rightChain, segIndexMono, segIndexPass, grid, gridV, midU, rightU, pStream, 1);
Real tempTop[2];
tempTop[0] = grid->get_u_value(midU);
tempTop[1] = grid->get_v_value(gridV);
monoTriangulation2(tempTop, botVertex, rightChain, segIndexMono, rightEnd, 0, pStream);
}
else {
stripOfFanRight(rightChain, segIndexMono, segIndexPass, grid, gridV, leftU, rightU, pStream, 1);
Real tempTop[2];
tempTop[0] = grid->get_u_value(leftU);
tempTop[1] = grid->get_v_value(gridV);
monoTriangulation2(tempTop, botVertex, rightChain, segIndexMono, rightEnd, 0, pStream);
}
}
else grid->outputFanWithPoint(gridV, leftU, rightU, botVertex, pStream);
}
void sampleBotRightWithGridLine(Real* botVertex,
vertexArray* rightChain,
Int rightEnd,
Int rightCorner,
gridWrap* grid,
Int gridV,
Int leftU,
Int rightU,
primStream* pStream)
{
if(rightEnd<rightCorner){
grid->outputFanWithPoint(gridV, leftU, rightU, botVertex, pStream);
return;
}
Int segIndexMono, segIndexPass;
findBotRightSegment(rightChain,
rightEnd,
rightCorner,
grid->get_u_value(rightU),
segIndexMono,
segIndexPass);
sampleBotRightWithGridLinePost(botVertex,
rightChain,
rightEnd,
segIndexMono,
segIndexPass,
rightCorner,
grid,
gridV,
leftU,
rightU,
pStream);
}
void sampleBotLeftWithGridLinePost(Real* botVertex,
vertexArray* leftChain,
Int leftEnd,
Int segIndexMono,
Int segIndexPass,
Int leftCorner,
gridWrap* grid,
Int gridV,
Int leftU,
Int rightU,
primStream* pStream)
{
if(segIndexPass > leftCorner) {
Real *tempBot;
if(segIndexPass <= leftEnd) tempBot = leftChain->getVertex(segIndexPass);
else tempBot = botVertex;
Real tempTop[2];
tempTop[0] = grid->get_u_value(leftU);
tempTop[1] = grid->get_v_value(gridV);
monoTriangulation2(tempTop, tempBot, leftChain, leftCorner, segIndexPass-1,
1, pStream);
}
if(segIndexPass <= leftEnd) {
stripOfFanLeft(leftChain, segIndexMono, segIndexPass, grid, gridV, leftU, rightU, pStream, 1);
Real tempTop[2];
tempTop[0] = grid->get_u_value(rightU);
tempTop[1] = grid->get_v_value(gridV);
monoTriangulation2(tempTop, botVertex, leftChain, segIndexMono, leftEnd,
1, pStream);
}
else {
grid->outputFanWithPoint(gridV, leftU, rightU, botVertex, pStream);
}
}
void sampleBotLeftWithGridLine(Real* botVertex,
vertexArray* leftChain,
Int leftEnd,
Int leftCorner,
gridWrap* grid,
Int gridV,
Int leftU,
Int rightU,
primStream* pStream)
{
if(leftEnd< leftCorner){
grid->outputFanWithPoint(gridV, leftU, rightU, botVertex, pStream);
return;
}
Int segIndexPass, segIndexMono;
findBotLeftSegment(leftChain, leftEnd, leftCorner, grid->get_u_value(leftU), segIndexMono, segIndexPass);
sampleBotLeftWithGridLinePost(botVertex,
leftChain,
leftEnd,
segIndexMono,
segIndexPass,
leftCorner,
grid,
gridV,
leftU, rightU, pStream);
}
Int findBotSeparator(vertexArray* leftChain,
Int leftEnd,
Int leftCorner,
vertexArray* rightChain,
Int rightEnd,
Int rightCorner,
Int& ret_sep_left,
Int& ret_sep_right)
{
Int oldLeftI, oldRightI, newLeftI, newRightI;
Int i,j,k;
Real leftMax ;
Real rightMin ;
if(leftChain->getVertex(leftCorner)[1] < rightChain->getVertex(rightCorner)[1]) {
oldLeftI = leftCorner-1;
oldRightI = rightCorner;
leftMax = leftChain->getVertex(leftCorner)[0] - Real(1.0) ; rightMin = rightChain->getVertex(rightCorner)[0];
}
else {
oldLeftI = leftCorner;
oldRightI = rightCorner-1;
leftMax = leftChain->getVertex(leftCorner)[0];
rightMin = rightChain->getVertex(rightCorner)[0] + Real(1.0);
}
i = leftCorner;
j = rightCorner;
while(1)
{
newLeftI = oldLeftI;
newRightI = oldRightI;
if(i> leftEnd) {
for(k=j+1; k<= rightEnd; k++)
{
if(rightChain->getVertex(k)[0] > leftMax) {
if(rightChain->getVertex(k)[0] < rightMin)
{
rightMin = rightChain->getVertex(k)[0];
oldRightI = k;
}
}
else break; }
break; }
else if(j > rightEnd) {
for(k=i+1; k<= leftEnd; k++)
{
if(leftChain->getVertex(k)[0] < rightMin) {
if(leftChain->getVertex(k)[0] > leftMax)
{
leftMax = leftChain->getVertex(k)[0];
oldLeftI = k;
}
}
else break; }
break; }
else if(leftChain->getVertex(i)[1] < rightChain->getVertex(j)[1]) {
if(leftChain->getVertex(i)[0] > leftMax) {
leftMax = leftChain->getVertex(i)[0];
newLeftI = i;
}
for(k=j+1; k<= rightEnd; k++) {
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; if(leftMax >= rightMin) break;
else {
oldLeftI = newLeftI;
oldRightI = newRightI;
}
}
else {
if(rightChain->getVertex(j)[0] < rightMin)
{
rightMin = rightChain->getVertex(j)[0];
newRightI = j;
}
for(k=i+1; k<= leftEnd; 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; if(leftMax >= rightMin) break;
else {
oldLeftI = newLeftI;
oldRightI = newRightI;
}
}
} if(oldLeftI < leftCorner || oldRightI < rightCorner)
return 0; else
{
ret_sep_left = oldLeftI;
ret_sep_right = oldRightI;
return 1;
}
}
void sampleCompBot(Real* botVertex,
vertexArray* leftChain,
Int leftEnd,
vertexArray* rightChain,
Int rightEnd,
gridBoundaryChain* leftGridChain,
gridBoundaryChain* rightGridChain,
Int gridIndex,
Int down_leftCornerWhere,
Int down_leftCornerIndex,
Int down_rightCornerWhere,
Int down_rightCornerIndex,
primStream* pStream)
{
if(down_leftCornerWhere == 1 && down_rightCornerWhere == 1) {
leftGridChain->getGrid()->outputFanWithPoint(leftGridChain->getVlineIndex(gridIndex),
leftGridChain->getUlineIndex(gridIndex),
rightGridChain->getUlineIndex(gridIndex),
botVertex,
pStream);
return;
}
else if(down_leftCornerWhere != 0)
{
Real* tempBot;
Int tempRightEnd;
if(down_leftCornerWhere == 1){
tempRightEnd = rightEnd;
tempBot = botVertex;
}
else
{
tempRightEnd = down_leftCornerIndex-1;
tempBot = rightChain->getVertex(down_leftCornerIndex);
}
sampleBotRightWithGridLine(tempBot,
rightChain,
tempRightEnd,
down_rightCornerIndex,
rightGridChain->getGrid(),
leftGridChain->getVlineIndex(gridIndex),
leftGridChain->getUlineIndex(gridIndex),
rightGridChain->getUlineIndex(gridIndex),
pStream);
}
else if(down_rightCornerWhere != 2)
{
Real* tempBot;
Int tempLeftEnd;
if(down_rightCornerWhere == 1){
tempLeftEnd = leftEnd;
tempBot = botVertex;
}
else {
tempLeftEnd = down_rightCornerIndex-1;
tempBot = leftChain->getVertex(down_rightCornerIndex);
}
sampleBotLeftWithGridLine(tempBot, leftChain, tempLeftEnd, down_leftCornerIndex,
leftGridChain->getGrid(),
leftGridChain->getVlineIndex(gridIndex),
leftGridChain->getUlineIndex(gridIndex),
rightGridChain->getUlineIndex(gridIndex),
pStream);
}
else {
sampleCompBotSimple(botVertex,
leftChain,
leftEnd,
rightChain,
rightEnd,
leftGridChain,
rightGridChain,
gridIndex,
down_leftCornerWhere,
down_leftCornerIndex,
down_rightCornerWhere,
down_rightCornerIndex,
pStream);
return;
#ifdef NOT_REACHABLE
Int sep_left, sep_right;
if(findBotSeparator(leftChain, leftEnd, down_leftCornerIndex,
rightChain, rightEnd, down_rightCornerIndex,
sep_left, sep_right)
) {
if(leftChain->getVertex(sep_left)[0] >= leftGridChain->get_u_value(gridIndex) &&
rightChain->getVertex(sep_right)[0] <= rightGridChain->get_u_value(gridIndex))
{
Int gridSep;
Int segLeftMono, segLeftPass, segRightMono, segRightPass;
findBotLeftSegment(leftChain,
sep_left,
down_leftCornerIndex,
leftGridChain->get_u_value(gridIndex),
segLeftMono,
segLeftPass);
findBotRightSegment(rightChain,
sep_right,
down_rightCornerIndex,
rightGridChain->get_u_value(gridIndex),
segRightMono,
segRightPass);
if(leftChain->getVertex(segLeftMono)[1] <= rightChain->getVertex(segRightMono)[1])
{
gridSep = rightGridChain->getUlineIndex(gridIndex);
while(leftGridChain->getGrid()->get_u_value(gridSep) > leftChain->getVertex(segLeftMono)[0])
gridSep--;
}
else
{
gridSep = leftGridChain->getUlineIndex(gridIndex);
while(leftGridChain->getGrid()->get_u_value(gridSep) < rightChain->getVertex(segRightMono)[0])
gridSep++;
}
sampleBotLeftWithGridLinePost(leftChain->getVertex(segLeftMono),
leftChain,
segLeftMono-1,
segLeftMono-1,
segLeftPass,
down_leftCornerIndex,
leftGridChain->getGrid(),
leftGridChain->getVlineIndex(gridIndex),
leftGridChain->getUlineIndex(gridIndex),
gridSep,
pStream);
sampleBotRightWithGridLinePost(rightChain->getVertex(segRightMono),
rightChain,
segRightMono-1,
segRightMono-1,
segRightPass,
down_rightCornerIndex,
rightGridChain->getGrid(),
rightGridChain->getVlineIndex(gridIndex),
gridSep,
rightGridChain->getUlineIndex(gridIndex),
pStream);
Real tempTop[2];
tempTop[0] = leftGridChain->getGrid()->get_u_value(gridSep);
tempTop[1] = leftGridChain->get_v_value(gridIndex);
monoTriangulationRecGen(tempTop, botVertex,
leftChain, segLeftMono, leftEnd,
rightChain, segRightMono, rightEnd,
pStream);
} else if(leftChain->getVertex(sep_left)[0] >= leftGridChain->get_u_value(gridIndex))
{
Int segLeftMono, segLeftPass;
findBotLeftSegment(leftChain,
sep_left,
down_leftCornerIndex,
leftGridChain->get_u_value(gridIndex),
segLeftMono,
segLeftPass);
assert(segLeftPass <= sep_left); monoTriangulation2(leftGridChain->get_vertex(gridIndex),
leftChain->getVertex(segLeftPass),
leftChain,
down_leftCornerIndex,
segLeftPass-1,
1, pStream);
stripOfFanLeft(leftChain, segLeftMono, segLeftPass,
leftGridChain->getGrid(),
leftGridChain->getVlineIndex(gridIndex),
leftGridChain->getUlineIndex(gridIndex),
rightGridChain->getUlineIndex(gridIndex),
pStream,1 );
monoTriangulationRecGen(rightGridChain->get_vertex(gridIndex),
botVertex,
leftChain, segLeftMono, leftEnd,
rightChain, down_rightCornerIndex, rightEnd,
pStream);
} else if(rightChain->getVertex(sep_right)[0] <= rightGridChain->get_u_value(gridIndex)) {
Int segRightMono, segRightPass;
findBotRightSegment(rightChain, sep_right, down_rightCornerIndex,
rightGridChain->get_u_value(gridIndex),
segRightMono,
segRightPass);
assert(segRightPass <= sep_right); monoTriangulation2(rightGridChain->get_vertex(gridIndex),
rightChain->getVertex(segRightPass),
rightChain,
down_rightCornerIndex,
segRightPass-1,
0, pStream);
stripOfFanRight(rightChain, segRightMono, segRightPass,
rightGridChain->getGrid(),
rightGridChain->getVlineIndex(gridIndex),
leftGridChain->getUlineIndex(gridIndex),
rightGridChain->getUlineIndex(gridIndex),
pStream, 1);
monoTriangulationRecGen(leftGridChain->get_vertex(gridIndex),
botVertex,
leftChain, down_leftCornerIndex, leftEnd,
rightChain, segRightMono, rightEnd,
pStream);
} else {
sampleCompBotSimple(botVertex,
leftChain,
leftEnd,
rightChain,
rightEnd,
leftGridChain,
rightGridChain,
gridIndex,
down_leftCornerWhere,
down_leftCornerIndex,
down_rightCornerWhere,
down_rightCornerIndex,
pStream);
} } else {
sampleCompBotSimple(botVertex,
leftChain,
leftEnd,
rightChain,
rightEnd,
leftGridChain,
rightGridChain,
gridIndex,
down_leftCornerWhere,
down_leftCornerIndex,
down_rightCornerWhere,
down_rightCornerIndex,
pStream);
}
#endif
}}
void sampleCompBotSimple(Real* botVertex,
vertexArray* leftChain,
Int leftEnd,
vertexArray* rightChain,
Int rightEnd,
gridBoundaryChain* leftGridChain,
gridBoundaryChain* rightGridChain,
Int gridIndex,
Int down_leftCornerWhere,
Int down_leftCornerIndex,
Int down_rightCornerWhere,
Int down_rightCornerIndex,
primStream* pStream)
{
Int i,k;
Real* ActualTop;
Real* ActualBot;
Int ActualLeftStart, ActualLeftEnd;
Int ActualRightStart, ActualRightEnd;
gridWrap* grid = leftGridChain->getGrid();
Int gridV = leftGridChain->getVlineIndex(gridIndex);
Int gridLeftU = leftGridChain->getUlineIndex(gridIndex);
Int gridRightU = rightGridChain->getUlineIndex(gridIndex);
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(down_rightCornerWhere != 0) ActualLeftEnd = leftEnd;
else
ActualLeftEnd = down_rightCornerIndex-1;
if(down_leftCornerWhere != 0) ActualLeftStart = leftEnd+1; else
ActualLeftStart = down_leftCornerIndex;
vertexArray ActualLeftChain(max(0, ActualLeftEnd - ActualLeftStart +1) + gridRightU - gridLeftU +1);
for(i=0; i<gridRightU - gridLeftU +1 ; i++)
ActualLeftChain.appendVertex(gridPoints[i]);
for(i=ActualLeftStart; i<= ActualLeftEnd; i++)
ActualLeftChain.appendVertex(leftChain->getVertex(i));
if(down_rightCornerWhere != 2) ActualRightStart = rightEnd +1; else
ActualRightStart = down_rightCornerIndex;
if(down_leftCornerWhere != 2) {
ActualRightEnd = rightEnd;
}
else {
ActualRightEnd = down_leftCornerIndex-1;
}
if(down_rightCornerWhere == 2)
{
if(down_leftCornerWhere == 2)
ActualBot = rightChain->getVertex(down_leftCornerIndex);
else
ActualBot = botVertex;
}
else if(down_rightCornerWhere == 1) ActualBot = botVertex;
else ActualBot = leftChain->getVertex(down_rightCornerIndex);
ActualTop = gridPoints[0];
if(rightChain->getVertex(ActualRightStart)[1] == ActualTop[1])
monoTriangulationRecGenOpt(rightChain->getVertex(ActualRightStart),
ActualBot,
&ActualLeftChain,
0,
ActualLeftChain.getNumElements()-1,
rightChain,
ActualRightStart+1,
ActualRightEnd,
pStream);
else
monoTriangulationRecGenOpt(ActualTop, ActualBot,
&ActualLeftChain,
1, ActualLeftChain.getNumElements()-1,
rightChain,
ActualRightStart,
ActualRightEnd,
pStream);
free(gridPoints);
}