#include "gluos.h"
#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#ifndef max
#define max(a,b) ((a>b)? a:b)
#endif
#ifndef min
#define min(a,b) ((a>b)? b:a)
#endif
#include <GL/gl.h>
#include "glimports.h"
#include "zlassert.h"
#include "sampleMonoPoly.h"
#include "sampleComp.h"
#include "polyDBG.h"
#include "partitionX.h"
#define ZERO 0.00001
directedLine* polygonConvert(directedLine* polygon)
{
int i;
directedLine* ret;
sampledLine* sline;
sline = new sampledLine(2);
sline->setPoint(0, polygon->getVertex(0));
sline->setPoint(1, polygon->getVertex(1));
ret=new directedLine(INCREASING, sline);
for(i=1; i<= polygon->get_npoints()-2; i++)
{
sline = new sampledLine(2);
sline->setPoint(0, polygon->getVertex(i));
sline->setPoint(1, polygon->getVertex(i+1));
ret->insert(new directedLine(INCREASING, sline));
}
for(directedLine *temp = polygon->getNext(); temp != polygon; temp = temp->getNext())
{
for(i=0; i<= temp->get_npoints()-2; i++)
{
sline = new sampledLine(2);
sline->setPoint(0, temp->getVertex(i));
sline->setPoint(1, temp->getVertex(i+1));
ret->insert(new directedLine(INCREASING, sline));
}
}
return ret;
}
void triangulateConvexPolyVertical(directedLine* topV, directedLine* botV, primStream *pStream)
{
Int i,j;
Int n_leftVerts;
Int n_rightVerts;
Real** leftVerts;
Real** rightVerts;
directedLine* tempV;
n_leftVerts = 0;
for(tempV = topV; tempV != botV; tempV = tempV->getNext())
{
n_leftVerts += tempV->get_npoints();
}
n_rightVerts=0;
for(tempV = botV; tempV != topV; tempV = tempV->getNext())
{
n_rightVerts += tempV->get_npoints();
}
Real2* temp_leftVerts = (Real2 *) malloc(sizeof(Real2) * n_leftVerts);
assert(temp_leftVerts);
Real2* temp_rightVerts = (Real2 *) malloc(sizeof(Real2) * n_rightVerts);
assert(temp_rightVerts);
leftVerts = (Real**) malloc(sizeof(Real2*) * n_leftVerts);
assert(leftVerts);
rightVerts = (Real**) malloc(sizeof(Real2*) * n_rightVerts);
assert(rightVerts);
for(i=0; i<n_leftVerts; i++)
leftVerts[i] = temp_leftVerts[i];
for(i=0; i<n_rightVerts; i++)
rightVerts[i] = temp_rightVerts[i];
i=0;
for(tempV = topV; tempV != botV; tempV = tempV->getNext())
{
for(j=1; j<tempV->get_npoints(); j++)
{
leftVerts[i][0] = tempV->getVertex(j)[0];
leftVerts[i][1] = tempV->getVertex(j)[1];
i++;
}
}
n_leftVerts = i;
i=0;
for(tempV = topV->getPrev(); tempV != botV->getPrev(); tempV = tempV->getPrev())
{
for(j=tempV->get_npoints()-1; j>=1; j--)
{
rightVerts[i][0] = tempV->getVertex(j)[0];
rightVerts[i][1] = tempV->getVertex(j)[1];
i++;
}
}
n_rightVerts = i;
triangulateXYMonoTB(n_leftVerts, leftVerts, n_rightVerts, rightVerts, pStream);
free(leftVerts);
free(rightVerts);
free(temp_leftVerts);
free(temp_rightVerts);
}
void triangulateConvexPolyHoriz(directedLine* leftV, directedLine* rightV, primStream *pStream)
{
Int i,j;
Int n_lowerVerts;
Int n_upperVerts;
Real2 *lowerVerts;
Real2 *upperVerts;
directedLine* tempV;
n_lowerVerts=0;
for(tempV = leftV; tempV != rightV; tempV = tempV->getNext())
{
n_lowerVerts += tempV->get_npoints();
}
n_upperVerts=0;
for(tempV = rightV; tempV != leftV; tempV = tempV->getNext())
{
n_upperVerts += tempV->get_npoints();
}
lowerVerts = (Real2 *) malloc(sizeof(Real2) * n_lowerVerts);
assert(n_lowerVerts);
upperVerts = (Real2 *) malloc(sizeof(Real2) * n_upperVerts);
assert(n_upperVerts);
i=0;
for(tempV = leftV; tempV != rightV; tempV = tempV->getNext())
{
for(j=0; j<tempV->get_npoints(); j++)
{
lowerVerts[i][0] = tempV->getVertex(j)[0];
lowerVerts[i][1] = tempV->getVertex(j)[1];
i++;
}
}
i=0;
for(tempV = leftV->getPrev(); tempV != rightV->getPrev(); tempV = tempV->getPrev())
{
for(j=tempV->get_npoints()-1; j>=0; j--)
{
upperVerts[i][0] = tempV->getVertex(j)[0];
upperVerts[i][1] = tempV->getVertex(j)[1];
i++;
}
}
triangulateXYMono(n_upperVerts, upperVerts, n_lowerVerts, lowerVerts, pStream);
free(lowerVerts);
free(upperVerts);
}
void triangulateConvexPoly(directedLine* polygon, Int ulinear, Int vlinear, primStream* pStream)
{
directedLine* tempV;
directedLine* topV;
directedLine* botV;
directedLine* leftV;
directedLine* rightV;
topV = botV = polygon;
for(tempV = polygon->getNext(); tempV != polygon; tempV = tempV->getNext())
{
if(compV2InY(topV->head(), tempV->head())<0) {
topV = tempV;
}
if(compV2InY(botV->head(), tempV->head())>0) {
botV = tempV;
}
}
for(tempV = topV; tempV != botV; tempV = tempV->getNext())
{
if(tempV->tail()[0] >= tempV->head()[0])
break;
}
leftV = tempV;
for(tempV = botV; tempV != topV; tempV = tempV->getNext())
{
if(tempV->tail()[0] <= tempV->head()[0])
break;
}
rightV = tempV;
if(vlinear)
{
triangulateConvexPolyHoriz( leftV, rightV, pStream);
}
else if(ulinear)
{
triangulateConvexPolyVertical(topV, botV, pStream);
}
else
{
if(DBG_is_U_direction(polygon))
{
triangulateConvexPolyHoriz( leftV, rightV, pStream);
}
else
triangulateConvexPolyVertical(topV, botV, pStream);
}
}
void drawCorners(
Real* topV, Real* botV,
vertexArray* leftChain,
vertexArray* rightChain,
gridBoundaryChain* leftGridChain,
gridBoundaryChain* rightGridChain,
Int gridIndex1,
Int gridIndex2,
Int leftCornerWhere,
Int leftCornerIndex,
Int rightCornerWhere,
Int rightCornerIndex,
Int bot_leftCornerWhere,
Int bot_leftCornerIndex,
Int bot_rightCornerWhere,
Int bot_rightCornerIndex)
{
Real* leftCornerV;
Real* rightCornerV;
Real* bot_leftCornerV;
Real* bot_rightCornerV;
if(leftCornerWhere == 1)
leftCornerV = topV;
else if(leftCornerWhere == 0)
leftCornerV = leftChain->getVertex(leftCornerIndex);
else
leftCornerV = rightChain->getVertex(leftCornerIndex);
if(rightCornerWhere == 1)
rightCornerV = topV;
else if(rightCornerWhere == 0)
rightCornerV = leftChain->getVertex(rightCornerIndex);
else
rightCornerV = rightChain->getVertex(rightCornerIndex);
if(bot_leftCornerWhere == 1)
bot_leftCornerV = botV;
else if(bot_leftCornerWhere == 0)
bot_leftCornerV = leftChain->getVertex(bot_leftCornerIndex);
else
bot_leftCornerV = rightChain->getVertex(bot_leftCornerIndex);
if(bot_rightCornerWhere == 1)
bot_rightCornerV = botV;
else if(bot_rightCornerWhere == 0)
bot_rightCornerV = leftChain->getVertex(bot_rightCornerIndex);
else
bot_rightCornerV = rightChain->getVertex(bot_rightCornerIndex);
Real topGridV = leftGridChain->get_v_value(gridIndex1);
Real topGridU1 = leftGridChain->get_u_value(gridIndex1);
Real topGridU2 = rightGridChain->get_u_value(gridIndex1);
Real botGridV = leftGridChain->get_v_value(gridIndex2);
Real botGridU1 = leftGridChain->get_u_value(gridIndex2);
Real botGridU2 = rightGridChain->get_u_value(gridIndex2);
glBegin(GL_LINE_STRIP);
glVertex2fv(leftCornerV);
glVertex2f(topGridU1, topGridV);
glEnd();
glBegin(GL_LINE_STRIP);
glVertex2fv(rightCornerV);
glVertex2f(topGridU2, topGridV);
glEnd();
glBegin(GL_LINE_STRIP);
glVertex2fv(bot_leftCornerV);
glVertex2f(botGridU1, botGridV);
glEnd();
glBegin(GL_LINE_STRIP);
glVertex2fv(bot_rightCornerV);
glVertex2f(botGridU2, botGridV);
glEnd();
}
void toVertexArrays(directedLine* topV, directedLine* botV, vertexArray& leftChain, vertexArray& rightChain)
{
Int i;
directedLine* tempV;
for(i=1; i<=topV->get_npoints()-2; i++) {
leftChain.appendVertex(topV->getVertex(i));
}
for(tempV = topV->getNext(); tempV != botV; tempV = tempV->getNext())
{
for(i=0; i<=tempV->get_npoints()-2; i++){
leftChain.appendVertex(tempV->getVertex(i));
}
}
for(tempV = topV->getPrev(); tempV != botV; tempV = tempV->getPrev())
{
for(i=tempV->get_npoints()-2; i>=0; i--){
rightChain.appendVertex(tempV->getVertex(i));
}
}
for(i=botV->get_npoints()-2; i>=1; i--){
rightChain.appendVertex(tempV->getVertex(i));
}
}
void findTopAndBot(directedLine* polygon, directedLine*& topV, directedLine*& botV)
{
assert(polygon);
directedLine* tempV;
topV = botV = polygon;
for(tempV = polygon->getNext(); tempV != polygon; tempV = tempV->getNext())
{
if(compV2InY(topV->head(), tempV->head())<0) {
topV = tempV;
}
if(compV2InY(botV->head(), tempV->head())>0) {
botV = tempV;
}
}
}
void findGridChains(directedLine* topV, directedLine* botV,
gridWrap* grid,
gridBoundaryChain*& leftGridChain,
gridBoundaryChain*& rightGridChain)
{
Int firstGridIndex;
Int lastGridIndex;
firstGridIndex = (Int) ((topV->head()[1] - grid->get_v_min()) / (grid->get_v_max() - grid->get_v_min()) * (grid->get_n_vlines()-1));
if(botV->head()[1] < grid->get_v_min())
lastGridIndex = 0;
else
lastGridIndex = (Int) ((botV->head()[1] - grid->get_v_min()) / (grid->get_v_max() - grid->get_v_min()) * (grid->get_n_vlines()-1)) + 1;
Int *leftGridIndices = (Int*) malloc(sizeof(Int) * (firstGridIndex - lastGridIndex +1));
assert(leftGridIndices);
Int *rightGridIndices = (Int*) malloc(sizeof(Int) * (firstGridIndex - lastGridIndex +1));
assert(rightGridIndices);
Int *leftGridInnerIndices = (Int*) malloc(sizeof(Int) * (firstGridIndex - lastGridIndex +1));
assert(leftGridInnerIndices);
Int *rightGridInnerIndices = (Int*) malloc(sizeof(Int) * (firstGridIndex - lastGridIndex +1));
assert(rightGridInnerIndices);
findLeftGridIndices(topV, firstGridIndex, lastGridIndex, grid, leftGridIndices, leftGridInnerIndices);
findRightGridIndices(topV, firstGridIndex, lastGridIndex, grid, rightGridIndices, rightGridInnerIndices);
leftGridChain = new gridBoundaryChain(grid, firstGridIndex, firstGridIndex-lastGridIndex+1, leftGridIndices, leftGridInnerIndices);
rightGridChain = new gridBoundaryChain(grid, firstGridIndex, firstGridIndex-lastGridIndex+1, rightGridIndices, rightGridInnerIndices);
free(leftGridIndices);
free(rightGridIndices);
free(leftGridInnerIndices);
free(rightGridInnerIndices);
}
void findDownCorners(Real *botVertex,
vertexArray *leftChain, Int leftChainStartIndex, Int leftChainEndIndex,
vertexArray *rightChain, Int rightChainStartIndex, Int rightChainEndIndex,
Real v,
Real uleft,
Real uright,
Int& ret_leftCornerWhere,
Int& ret_leftCornerIndex,
Int& ret_rightCornerWhere,
Int& ret_rightCornerIndex
)
{
#ifdef MYDEBUG
printf("*************enter find donw corner\n");
printf("finddownCorner: v=%f, uleft=%f, uright=%f\n", v, uleft, uright);
printf("(%i,%i,%i,%i)\n", leftChainStartIndex, leftChainEndIndex,rightChainStartIndex, rightChainEndIndex);
printf("left chain is\n");
leftChain->print();
printf("right chain is\n");
rightChain->print();
#endif
assert(v > botVertex[1]);
Real leftGridPoint[2];
leftGridPoint[0] = uleft;
leftGridPoint[1] = v;
Real rightGridPoint[2];
rightGridPoint[0] = uright;
rightGridPoint[1] = v;
Int i;
Int index1, index2;
index1 = leftChain->findIndexBelowGen(v, leftChainStartIndex, leftChainEndIndex);
index2 = rightChain->findIndexBelowGen(v, rightChainStartIndex, rightChainEndIndex);
if(index2 <= rightChainEndIndex) index2 = rightChain->skipEqualityFromStart(v, index2, rightChainEndIndex);
if(index1>leftChainEndIndex && index2 > rightChainEndIndex)
{
ret_leftCornerWhere = 1;
ret_rightCornerWhere = 1;
}
else if(index1>leftChainEndIndex )
{
ret_rightCornerWhere = 2;
ret_rightCornerIndex = index2;
Real tempMin = rightChain->getVertex(index2)[0];
Int tempI = index2;
for(i=index2+1; i<= rightChainEndIndex; i++)
if(rightChain->getVertex(i)[0] < tempMin)
{
tempI = i;
tempMin = rightChain->getVertex(i)[0];
}
if(DBG_intersectChain(rightChain, rightChainStartIndex,rightChainEndIndex,
leftGridPoint, botVertex))
{
ret_leftCornerWhere = 2; ret_leftCornerIndex = index2; }
else if(botVertex[0] < tempMin)
ret_leftCornerWhere = 1; else
{
ret_leftCornerWhere = 2; ret_leftCornerIndex = tempI;
}
}
else if(index2> rightChainEndIndex)
{
ret_leftCornerWhere = 0;
ret_leftCornerIndex = index1;
Int tempI;
for(tempI = index1; tempI <= leftChainEndIndex; tempI++)
if(leftChain->getVertex(tempI)[1] < v)
break;
if(tempI > leftChainEndIndex)
ret_rightCornerWhere = 1;
else
{
Real tempMax = leftChain->getVertex(tempI)[0];
for(i=tempI; i<= leftChainEndIndex; i++)
if(leftChain->getVertex(i)[0] > tempMax)
{
tempI = i;
tempMax = leftChain->getVertex(i)[0];
}
if(DBG_intersectChain(leftChain, leftChainStartIndex,leftChainEndIndex,
rightGridPoint, botVertex))
{
ret_rightCornerWhere = 0;
ret_rightCornerIndex = index1; }
else if(botVertex[0] > tempMax)
{
ret_rightCornerWhere = 1;
}
else
{
ret_rightCornerWhere = 0;
ret_rightCornerIndex = tempI;
}
}
}
else
{
if(leftChain->getVertex(index1)[1] >= rightChain->getVertex(index2)[1])
{
ret_leftCornerWhere = 0;
ret_leftCornerIndex = index1;
Real tempMax;
Int tempI;
tempI = index1;
tempMax = leftChain->getVertex(index1)[0];
for(i=index1+1; i<= leftChainEndIndex; i++)
{
if(leftChain->getVertex(i)[1] < rightChain->getVertex(index2)[1])
break;
if(leftChain->getVertex(i)[0]>tempMax)
{
tempI = i;
tempMax = leftChain->getVertex(i)[0];
}
}
if(DBG_intersectChain(leftChain, leftChainStartIndex,leftChainEndIndex, rightGridPoint, rightChain->getVertex(index2)))
{
ret_rightCornerWhere = 0;
ret_rightCornerIndex = index1; }
else if(tempMax >= rightChain->getVertex(index2)[0] ||
tempMax >= uright
)
{
ret_rightCornerWhere = 0;
ret_rightCornerIndex = tempI;
}
else
{
ret_rightCornerWhere = 2;
ret_rightCornerIndex = index2;
}
}
else
{
ret_rightCornerWhere = 2;
ret_rightCornerIndex = index2;
Real tempMin;
Int tempI;
tempI = index2;
tempMin = rightChain->getVertex(index2)[0];
for(i=index2+1; i<= rightChainEndIndex; i++)
{
if( rightChain->getVertex(i)[1] < leftChain->getVertex(index1)[1])
break;
if(rightChain->getVertex(i)[0] < tempMin)
{
tempI = i;
tempMin = rightChain->getVertex(i)[0];
}
}
if(DBG_intersectChain(rightChain, rightChainStartIndex, rightChainEndIndex, leftGridPoint, leftChain->getVertex(index1)))
{
ret_leftCornerWhere = 2;
ret_leftCornerIndex = index2; }
else if(tempMin <= leftChain->getVertex(index1)[0] ||
tempMin <= uleft)
{
ret_leftCornerWhere = 2;
ret_leftCornerIndex = tempI;
}
else
{
ret_leftCornerWhere = 0;
ret_leftCornerIndex = index1;
}
}
}
}
void findUpCorners(Real *topVertex,
vertexArray *leftChain, Int leftChainStartIndex, Int leftChainEndIndex,
vertexArray *rightChain, Int rightChainStartIndex, Int rightChainEndIndex,
Real v,
Real uleft,
Real uright,
Int& ret_leftCornerWhere,
Int& ret_leftCornerIndex,
Int& ret_rightCornerWhere,
Int& ret_rightCornerIndex
)
{
#ifdef MYDEBUG
printf("***********enter findUpCorners\n");
#endif
assert(v < topVertex[1]);
Real leftGridPoint[2];
leftGridPoint[0] = uleft;
leftGridPoint[1] = v;
Real rightGridPoint[2];
rightGridPoint[0] = uright;
rightGridPoint[1] = v;
Int i;
Int index1, index2;
index1 = leftChain->findIndexFirstAboveEqualGen(v, leftChainStartIndex, leftChainEndIndex);
index2 = rightChain->findIndexFirstAboveEqualGen(v, rightChainStartIndex, rightChainEndIndex);
if(index2>= leftChainStartIndex) index2 = rightChain->skipEqualityFromStart(v, index2, rightChainEndIndex);
if(index1<leftChainStartIndex && index2 <rightChainStartIndex)
{
ret_leftCornerWhere = 1;
ret_rightCornerWhere = 1;
}
else if(index1<leftChainStartIndex )
{
ret_rightCornerWhere = 2;
ret_rightCornerIndex = index2;
Real tempMin = rightChain->getVertex(index2)[0];
Int tempI = index2;
for(i=index2-1; i>=rightChainStartIndex; i--)
if(rightChain->getVertex(i)[0] < tempMin)
{
tempMin = rightChain->getVertex(i)[0];
tempI = i;
}
if(DBG_intersectChain(rightChain, rightChainStartIndex, rightChainEndIndex,
leftGridPoint, topVertex))
{
ret_leftCornerWhere = 2; ret_leftCornerIndex = index2;
}
else if(topVertex[0] < tempMin)
ret_leftCornerWhere = 1;
else
{
ret_leftCornerWhere = 2; ret_leftCornerIndex = tempI;
}
}
else if(index2< rightChainStartIndex)
{
ret_leftCornerWhere = 0;
ret_leftCornerIndex = index1;
Real tempMax = leftChain->getVertex(index1)[0];
Int tempI = index1;
for(i=index1-1; i>=leftChainStartIndex; i--){
if(leftChain->getVertex(i)[0] > tempMax)
{
tempMax = leftChain->getVertex(i)[0];
tempI = i;
}
}
if(DBG_intersectChain(leftChain, leftChainStartIndex,leftChainEndIndex,
rightGridPoint, topVertex))
{
ret_rightCornerWhere = 0; ret_rightCornerIndex = index1;
}
else if(topVertex[0] > tempMax)
ret_rightCornerWhere = 1; else
{
ret_rightCornerWhere = 0; ret_rightCornerIndex = tempI;
}
}
else
{
if(leftChain->getVertex(index1)[1] <= rightChain->getVertex(index2)[1])
{
ret_leftCornerWhere = 0;
ret_leftCornerIndex = index1;
Real tempMax;
Int tempI;
tempI = index1;
tempMax = leftChain->getVertex(index1)[0];
for(i=index1-1; i>= leftChainStartIndex; i--)
{
if(leftChain->getVertex(i)[1] > rightChain->getVertex(index2)[1])
break;
if(leftChain->getVertex(i)[0]>tempMax)
{
tempI = i;
tempMax = leftChain->getVertex(i)[0];
}
}
if(DBG_intersectChain(leftChain, leftChainStartIndex, leftChainEndIndex, rightGridPoint, rightChain->getVertex(index2)))
{
ret_rightCornerWhere = 0;
ret_rightCornerIndex = index1;
}
else if(tempMax >= rightChain->getVertex(index2)[0] ||
tempMax >= uright)
{
ret_rightCornerWhere = 0;
ret_rightCornerIndex = tempI;
}
else
{
ret_rightCornerWhere = 2;
ret_rightCornerIndex = index2;
}
}
else
{
ret_rightCornerWhere = 2;
ret_rightCornerIndex = index2;
Real tempMin;
Int tempI;
tempI = index2;
tempMin = rightChain->getVertex(index2)[0];
for(i=index2-1; i>= rightChainStartIndex; i--)
{
if( rightChain->getVertex(i)[1] > leftChain->getVertex(index1)[1])
break;
if(rightChain->getVertex(i)[0] < tempMin)
{
tempI = i;
tempMin = rightChain->getVertex(i)[0];
}
}
if(DBG_intersectChain(rightChain, rightChainStartIndex, rightChainEndIndex,
leftGridPoint, leftChain->getVertex(index1)))
{
ret_leftCornerWhere = 2; ret_leftCornerIndex = index2;
}
else if(tempMin <= leftChain->getVertex(index1)[0] ||
tempMin <= uleft)
{
ret_leftCornerWhere = 2;
ret_leftCornerIndex = tempI;
}
else
{
ret_leftCornerWhere = 0;
ret_leftCornerIndex = index1;
}
}
}
#ifdef MYDEBUG
printf("***********leave findUpCorners\n");
#endif
}
Int findNeckF(vertexArray *leftChain, Int botLeftIndex,
vertexArray *rightChain, Int botRightIndex,
gridBoundaryChain* leftGridChain,
gridBoundaryChain* rightGridChain,
Int gridStartIndex,
Int& neckLeft,
Int& neckRight)
{
Int lowerGridIndex; Int i;
Int n_vlines = leftGridChain->get_nVlines();
Real v;
if(botLeftIndex >= leftChain->getNumElements() ||
botRightIndex >= rightChain->getNumElements())
return 0;
v=min(leftChain->getVertex(botLeftIndex)[1], rightChain->getVertex(botRightIndex)[1]);
for(i=gridStartIndex; i<n_vlines; i++)
if(leftGridChain->get_v_value(i) <= v &&
leftGridChain->getUlineIndex(i)<= rightGridChain->getUlineIndex(i))
break;
lowerGridIndex = i;
if(lowerGridIndex == n_vlines) return 0;
else
{
Int botLeft2, botRight2;
botLeft2 = leftChain->findIndexFirstAboveEqualGen(leftGridChain->get_v_value(lowerGridIndex), botLeftIndex, leftChain->getNumElements()-1) -1 ;
botRight2 = rightChain->findIndexFirstAboveEqualGen(leftGridChain->get_v_value(lowerGridIndex), botRightIndex, rightChain->getNumElements()-1) -1;
if(botRight2 < botRightIndex) botRight2=botRightIndex;
if(botLeft2 < botLeftIndex) botLeft2 = botLeftIndex;
assert(botLeft2 >= botLeftIndex);
assert(botRight2 >= botRightIndex);
Int tempI = botLeftIndex;
Real temp = leftChain->getVertex(tempI)[0];
for(i=botLeftIndex+1; i<= botLeft2; i++)
if(leftChain->getVertex(i)[0] > temp)
{
temp = leftChain->getVertex(i)[0];
tempI = i;
}
neckLeft = tempI;
tempI = botRightIndex;
temp = rightChain->getVertex(tempI)[0];
for(i=botRightIndex+1; i<= botRight2; i++)
if(rightChain->getVertex(i)[0] < temp)
{
temp = rightChain->getVertex(i)[0];
tempI = i;
}
neckRight = tempI;
return 1;
}
}
void findNeck(vertexArray *leftChain, Int botLeftIndex,
vertexArray *rightChain, Int botRightIndex,
Int& leftLastIndex,
Int& rightLastIndex
)
{
assert(botLeftIndex < leftChain->getNumElements() &&
botRightIndex < rightChain->getNumElements());
if(leftChain->getVertex(botLeftIndex)[1] <= rightChain->getVertex(botRightIndex)[1]) {
leftLastIndex = botLeftIndex;
rightLastIndex=rightChain->findIndexAboveGen(leftChain->getVertex(botLeftIndex)[1], botRightIndex+1, rightChain->getNumElements()-1);
}
else {
rightLastIndex = botRightIndex;
leftLastIndex = leftChain->findIndexAboveGen(rightChain->getVertex(botRightIndex)[1],
botLeftIndex+1,
leftChain->getNumElements()-1);
}
}
void findLeftGridIndices(directedLine* topEdge, Int firstGridIndex, Int lastGridIndex, gridWrap* grid, Int* ret_indices, Int* ret_innerIndices)
{
Int i,k,isHoriz = 0;
Int n_ulines = grid->get_n_ulines();
Real uMin = grid->get_u_min();
Real uMax = grid->get_u_max();
Real slop = 0.0, uinterc;
#ifdef SHORTEN_GRID_LINE
Real *uintercBuf = (Real *) malloc (sizeof(Real) * (firstGridIndex-lastGridIndex+1));
assert(uintercBuf);
#endif
directedLine* dLine = topEdge;
Real vtail = grid->get_v_value(firstGridIndex) + 1.0;
Real tempMaxU = grid->get_u_min();
for(k=0, i=firstGridIndex; i>=lastGridIndex; i--, k++)
{
Real grid_v_value = grid->get_v_value(i);
if(vtail > grid_v_value)
{
while( (vtail=dLine->tail()[1]) > grid_v_value){
tempMaxU = max(tempMaxU, dLine->tail()[0]);
dLine = dLine -> getNext();
}
if( fabs(dLine->head()[1] - vtail) < ZERO)
isHoriz = 1;
else
{
isHoriz = 0;
slop = (dLine->head()[0] - dLine->tail()[0]) / (dLine->head()[1]-vtail);
}
}
if(isHoriz)
{
uinterc = max(dLine->head()[0], dLine->tail()[0]);
}
else
{
uinterc = slop * (grid_v_value - vtail) + dLine->tail()[0];
}
tempMaxU = max(tempMaxU, uinterc);
if(uinterc < uMin && uinterc >= uMin - ZERO)
uinterc = uMin;
if(uinterc > uMax && uinterc <= uMax + ZERO)
uinterc = uMax;
#ifdef SHORTEN_GRID_LINE
uintercBuf[k] = uinterc;
#endif
assert(uinterc >= uMin && uinterc <= uMax);
if(uinterc == uMax)
ret_indices[k] = n_ulines-1;
else
ret_indices[k] = (Int)(((uinterc-uMin)/(uMax - uMin)) * (n_ulines-1)) + 1;
if(ret_indices[k] >= n_ulines)
ret_indices[k] = n_ulines-1;
ret_innerIndices[k] = (Int)(((tempMaxU-uMin)/(uMax - uMin)) * (n_ulines-1)) + 1;
tempMaxU = uinterc;
}
#ifdef SHORTEN_GRID_LINE
for(k=0, i=firstGridIndex; i>=lastGridIndex; i--, k++)
{
Real a = grid->get_u_value(ret_indices[k]-1);
Real b = grid->get_u_value(ret_indices[k]);
assert(uintercBuf[k] >= a && uintercBuf < b);
if( (b-uintercBuf[k]) <= 0.2 * (b-a)) {
ret_indices[k]++;
}
if(k>0)
{
if(ret_innerIndices[k] < ret_indices[k-1])
ret_innerIndices[k] = ret_indices[k-1];
if(ret_innerIndices[k] < ret_indices[k])
ret_innerIndices[k] = ret_indices[k];
}
}
free(uintercBuf);
#endif
}
void findRightGridIndices(directedLine* topEdge, Int firstGridIndex, Int lastGridIndex, gridWrap* grid, Int* ret_indices, Int* ret_innerIndices)
{
Int i,k;
Int n_ulines = grid->get_n_ulines();
Real uMin = grid->get_u_min();
Real uMax = grid->get_u_max();
Real slop = 0.0, uinterc;
#ifdef SHORTEN_GRID_LINE
Real *uintercBuf = (Real *) malloc (sizeof(Real) * (firstGridIndex-lastGridIndex+1));
assert(uintercBuf);
#endif
directedLine* dLine = topEdge->getPrev();
Real vhead = dLine->tail()[1];
Real tempMinU = grid->get_u_max();
for(k=0, i=firstGridIndex; i>=lastGridIndex; i--, k++)
{
Real grid_v_value = grid->get_v_value(i);
if(vhead >= grid_v_value)
{
while( (vhead=dLine->head()[1]) > grid_v_value){
tempMinU = min(tempMinU, dLine->head()[0]);
dLine = dLine -> getPrev();
}
while(dLine->head()[1] == grid_v_value)
dLine = dLine->getPrev();
assert( dLine->tail()[1] != dLine->head()[1]);
slop = (dLine->tail()[0] - dLine->head()[0]) / (dLine->tail()[1]-dLine->head()[1]);
}
uinterc = slop * (grid_v_value - dLine->head()[1]) + dLine->head()[0];
if(uinterc < uMin)
uinterc = uMin;
else if(uinterc > uMax)
uinterc = uMax;
#ifdef SHORTEN_GRID_LINE
uintercBuf[k] = uinterc;
#endif
tempMinU = min(tempMinU, uinterc);
assert(uinterc >= uMin && uinterc <= uMax);
if(uinterc == uMin)
ret_indices[k] = 0;
else
ret_indices[k] = (int)ceil((((uinterc-uMin)/(uMax - uMin)) * (n_ulines-1))) -1;
ret_innerIndices[k] = (int)ceil ((((tempMinU-uMin)/(uMax - uMin)) * (n_ulines-1))) -1;
tempMinU = uinterc;
}
#ifdef SHORTEN_GRID_LINE
for(k=0, i=firstGridIndex; i>=lastGridIndex; i--, k++)
{
Real a = grid->get_u_value(ret_indices[k]);
Real b = grid->get_u_value(ret_indices[k]+1);
assert(uintercBuf[k] > a && uintercBuf <= b);
if( (uintercBuf[k]-a) <= 0.2 * (b-a)) {
ret_indices[k]--;
}
if(k>0)
{
if(ret_innerIndices[k] > ret_indices[k-1])
ret_innerIndices[k] = ret_indices[k-1];
if(ret_innerIndices[k] > ret_indices[k])
ret_innerIndices[k] = ret_indices[k];
}
}
free(uintercBuf);
#endif
}
void sampleMonoPoly(directedLine* polygon, gridWrap* grid, Int ulinear, Int vlinear, primStream* pStream, rectBlockArray* rbArray)
{
if(grid->get_n_ulines() == 2 ||
grid->get_n_vlines() == 2)
{
if(ulinear && grid->get_n_ulines() == 2)
{
monoTriangulationFun(polygon, compV2InY, pStream);
return;
}
else if(DBG_isConvex(polygon) && polygon->numEdges() >=4)
{
triangulateConvexPoly(polygon, ulinear, vlinear, pStream);
return;
}
else if(vlinear || DBG_is_U_direction(polygon))
{
Int n_cusps; Int n_edges = polygon->numEdges();
directedLine** cusps = (directedLine**) malloc(sizeof(directedLine*) * n_edges);
assert(cusps);
findInteriorCuspsX(polygon, n_cusps, cusps);
if(n_cusps == 0) {
monoTriangulationFun(polygon, compV2InX, pStream);
free(cusps);
return;
}
else if(n_cusps == 1) {
directedLine* new_polygon = polygonConvert(cusps[0]);
directedLine* other = findDiagonal_singleCuspX( new_polygon);
if(other == NULL)
{
monoTriangulationFun(polygon, compV2InX, pStream);
free(cusps);
return;
}
directedLine* ret_p1;
directedLine* ret_p2;
new_polygon->connectDiagonal_2slines(new_polygon, other,
&ret_p1,
&ret_p2,
new_polygon);
monoTriangulationFun(ret_p1, compV2InX, pStream);
monoTriangulationFun(ret_p2, compV2InX, pStream);
ret_p1->deleteSinglePolygonWithSline();
ret_p2->deleteSinglePolygonWithSline();
free(cusps);
return;
}
free(cusps);
}
}
directedLine* tempV;
directedLine* topV;
directedLine* botV;
topV = botV = polygon;
for(tempV = polygon->getNext(); tempV != polygon; tempV = tempV->getNext())
{
if(compV2InY(topV->head(), tempV->head())<0) {
topV = tempV;
}
if(compV2InY(botV->head(), tempV->head())>0) {
botV = tempV;
}
}
Int firstGridIndex;
Int lastGridIndex;
firstGridIndex = (Int) ((topV->head()[1] - grid->get_v_min()) / (grid->get_v_max() - grid->get_v_min()) * (grid->get_n_vlines()-1));
lastGridIndex = (Int) ((botV->head()[1] - grid->get_v_min()) / (grid->get_v_max() - grid->get_v_min()) * (grid->get_n_vlines()-1)) + 1;
Int *leftGridIndices = (Int*) malloc(sizeof(Int) * (firstGridIndex - lastGridIndex +1));
assert(leftGridIndices);
Int *rightGridIndices = (Int*) malloc(sizeof(Int) * (firstGridIndex - lastGridIndex +1));
assert(rightGridIndices);
Int *leftGridInnerIndices = (Int*) malloc(sizeof(Int) * (firstGridIndex - lastGridIndex +1));
assert(leftGridInnerIndices);
Int *rightGridInnerIndices = (Int*) malloc(sizeof(Int) * (firstGridIndex - lastGridIndex +1));
assert(rightGridInnerIndices);
findLeftGridIndices(topV, firstGridIndex, lastGridIndex, grid, leftGridIndices, leftGridInnerIndices);
findRightGridIndices(topV, firstGridIndex, lastGridIndex, grid, rightGridIndices, rightGridInnerIndices);
gridBoundaryChain leftGridChain(grid, firstGridIndex, firstGridIndex-lastGridIndex+1, leftGridIndices, leftGridInnerIndices);
gridBoundaryChain rightGridChain(grid, firstGridIndex, firstGridIndex-lastGridIndex+1, rightGridIndices, rightGridInnerIndices);
Int i;
vertexArray leftChain(20);
for(i=1; i<=topV->get_npoints()-2; i++) {
leftChain.appendVertex(topV->getVertex(i));
}
for(tempV = topV->getNext(); tempV != botV; tempV = tempV->getNext())
{
for(i=0; i<=tempV->get_npoints()-2; i++){
leftChain.appendVertex(tempV->getVertex(i));
}
}
vertexArray rightChain(20);
for(tempV = topV->getPrev(); tempV != botV; tempV = tempV->getPrev())
{
for(i=tempV->get_npoints()-2; i>=0; i--){
rightChain.appendVertex(tempV->getVertex(i));
}
}
for(i=botV->get_npoints()-2; i>=1; i--){
rightChain.appendVertex(tempV->getVertex(i));
}
sampleMonoPolyRec(topV->head(),
botV->head(),
&leftChain,
0,
&rightChain,
0,
&leftGridChain,
&rightGridChain,
0,
pStream,
rbArray);
free(leftGridIndices);
free(rightGridIndices);
free(leftGridInnerIndices);
free(rightGridInnerIndices);
}
void sampleMonoPolyRec(
Real* topVertex,
Real* botVertex,
vertexArray* leftChain,
Int leftStartIndex,
vertexArray* rightChain,
Int rightStartIndex,
gridBoundaryChain* leftGridChain,
gridBoundaryChain* rightGridChain,
Int gridStartIndex,
primStream* pStream,
rectBlockArray* rbArray)
{
Int index1, index2;
if(topVertex[1] <= botVertex[1])
return;
Int i=gridStartIndex;
while (i < leftGridChain->get_nVlines())
{
if(leftGridChain->get_v_value(i) < topVertex[1])
break;
i++;
}
index1=i;
int num_skipped_grid_lines=0;
while(index1 < leftGridChain->get_nVlines())
{
if(leftGridChain->getUlineIndex(index1) <= rightGridChain->getUlineIndex(index1))
break;
num_skipped_grid_lines++;
index1++;
}
if(index1 >= leftGridChain->get_nVlines())
{
if(num_skipped_grid_lines <2)
{
monoTriangulationRecGenOpt(topVertex, botVertex, leftChain, leftStartIndex,
leftChain->getNumElements()-1,
rightChain, rightStartIndex,
rightChain->getNumElements()-1,
pStream);
}
else
{
monoTriangulationRec(topVertex, botVertex, leftChain, leftStartIndex,
rightChain, rightStartIndex, pStream);
}
}
else
{
index2=index1+1;
if(index2 < leftGridChain->get_nVlines())
while(leftGridChain->getInnerIndex(index2) <= rightGridChain->getInnerIndex(index2))
{
index2++;
if(index2 >= leftGridChain->get_nVlines())
break;
}
index2--;
Int neckLeftIndex;
Int neckRightIndex;
Int up_leftCornerWhere;
Int up_leftCornerIndex;
Int up_rightCornerWhere;
Int up_rightCornerIndex;
Int down_leftCornerWhere;
Int down_leftCornerIndex;
Int down_rightCornerWhere;
Int down_rightCornerIndex;
Real* tempBotVertex;
Real* nextTopVertex=NULL;
Int nextLeftStartIndex=0;
Int nextRightStartIndex=0;
Int botLeftIndex = leftChain->findIndexStrictBelowGen(
leftGridChain->get_v_value(index2),
leftStartIndex,
leftChain->getNumElements()-1);
Int botRightIndex = rightChain->findIndexStrictBelowGen(
rightGridChain->get_v_value(index2),
rightStartIndex,
rightChain->getNumElements()-1);
if(! findNeckF(leftChain, botLeftIndex, rightChain, botRightIndex,
leftGridChain, rightGridChain, index2, neckLeftIndex, neckRightIndex))
{
#ifdef MYDEBUG
printf("neck NOT exists, botRightIndex=%i\n", botRightIndex);
#endif
tempBotVertex = botVertex;
nextTopVertex = botVertex;
botLeftIndex = leftChain->getNumElements()-1;
botRightIndex = rightChain->getNumElements()-1;
}
else
{
#ifdef MYDEBUG
printf("neck exists\n");
#endif
#ifdef MYDEBUG
printf("neck is found, neckLeftIndex=%i, neckRightIndex=%i\n", neckLeftIndex, neckRightIndex);
glBegin(GL_LINES);
glVertex2fv(leftChain->getVertex(neckLeftIndex));
glVertex2fv(rightChain->getVertex(neckRightIndex));
glEnd();
#endif
if(leftChain->getVertex(neckLeftIndex)[1] <= rightChain->getVertex(neckRightIndex)[1])
{
tempBotVertex = leftChain->getVertex(neckLeftIndex);
botLeftIndex = neckLeftIndex-1;
botRightIndex = neckRightIndex;
nextTopVertex = rightChain->getVertex(neckRightIndex);
nextLeftStartIndex = neckLeftIndex;
nextRightStartIndex = neckRightIndex+1;
}
else
{
tempBotVertex = rightChain->getVertex(neckRightIndex);
botLeftIndex = neckLeftIndex;
botRightIndex = neckRightIndex-1;
nextTopVertex = leftChain->getVertex(neckLeftIndex);
nextLeftStartIndex = neckLeftIndex+1;
nextRightStartIndex = neckRightIndex;
}
}
findUpCorners(topVertex,
leftChain,
leftStartIndex, botLeftIndex,
rightChain,
rightStartIndex, botRightIndex,
leftGridChain->get_v_value(index1),
leftGridChain->get_u_value(index1),
rightGridChain->get_u_value(index1),
up_leftCornerWhere,
up_leftCornerIndex,
up_rightCornerWhere,
up_rightCornerIndex);
findDownCorners(tempBotVertex,
leftChain,
leftStartIndex, botLeftIndex,
rightChain,
rightStartIndex, botRightIndex,
leftGridChain->get_v_value(index2),
leftGridChain->get_u_value(index2),
rightGridChain->get_u_value(index2),
down_leftCornerWhere,
down_leftCornerIndex,
down_rightCornerWhere,
down_rightCornerIndex);
#ifdef MYDEBUG
printf("find corners done, down_leftwhere=%i, down_righwhere=%i,\n",down_leftCornerWhere, down_rightCornerWhere );
printf("find corners done, up_leftwhere=%i, up_righwhere=%i,\n",up_leftCornerWhere, up_rightCornerWhere );
printf("find corners done, up_leftindex=%i, up_righindex=%i,\n",up_leftCornerIndex, up_rightCornerIndex );
printf("find corners done, down_leftindex=%i, down_righindex=%i,\n",down_leftCornerIndex, down_rightCornerIndex );
#endif
sampleConnectedComp(topVertex, tempBotVertex,
leftChain,
leftStartIndex, botLeftIndex,
rightChain,
rightStartIndex, botRightIndex,
leftGridChain,
rightGridChain,
index1, index2,
up_leftCornerWhere,
up_leftCornerIndex,
up_rightCornerWhere,
up_rightCornerIndex,
down_leftCornerWhere,
down_leftCornerIndex,
down_rightCornerWhere,
down_rightCornerIndex,
pStream,
rbArray
);
sampleMonoPolyRec(
nextTopVertex,
botVertex,
leftChain,
nextLeftStartIndex,
rightChain,
nextRightStartIndex,
leftGridChain,
rightGridChain,
index2+1,
pStream, rbArray);
}
}
void sampleLeftStrip(vertexArray* leftChain,
Int topLeftIndex,
Int botLeftIndex,
gridBoundaryChain* leftGridChain,
Int leftGridChainStartIndex,
Int leftGridChainEndIndex,
primStream* pStream
)
{
assert(leftChain->getVertex(topLeftIndex)[1] > leftGridChain->get_v_value(leftGridChainStartIndex));
assert(leftChain->getVertex(topLeftIndex+1)[1] <= leftGridChain->get_v_value(leftGridChainStartIndex));
assert(leftChain->getVertex(botLeftIndex)[1] <= leftGridChain->get_v_value(leftGridChainEndIndex));
assert(leftChain->getVertex(botLeftIndex-1)[1] > leftGridChain->get_v_value(leftGridChainEndIndex));
Real *upperVert, *lowerVert;
upperVert = leftChain->getVertex(topLeftIndex);
lowerVert = leftChain->getVertex(topLeftIndex+1);
Int index = leftGridChainStartIndex;
while(leftGridChain->get_v_value(index) >= lowerVert[1]){
index++;
if(index > leftGridChainEndIndex)
break;
}
index--;
sampleLeftSingleTrimEdgeRegion(upperVert, lowerVert,
leftGridChain,
leftGridChainStartIndex,
index,
pStream);
sampleLeftStripRec(leftChain, topLeftIndex+1, botLeftIndex,
leftGridChain, index, leftGridChainEndIndex,
pStream);
}
void sampleLeftStripRec(vertexArray* leftChain,
Int topLeftIndex,
Int botLeftIndex,
gridBoundaryChain* leftGridChain,
Int leftGridChainStartIndex,
Int leftGridChainEndIndex,
primStream* pStream
)
{
if(topLeftIndex >= botLeftIndex)
return;
Real secondGridChainV = leftGridChain->get_v_value(leftGridChainStartIndex+1);
assert(leftGridChainStartIndex < leftGridChainEndIndex);
Int index1 = topLeftIndex;
while(leftChain->getVertex(index1)[1] > secondGridChainV)
index1++;
index1--;
sampleLeftOneGridStep(leftChain, topLeftIndex, index1, leftGridChain, leftGridChainStartIndex, pStream);
Real *uppervert, *lowervert;
uppervert = leftChain->getVertex(index1);
lowervert = leftChain->getVertex(index1+1);
Int index2 = leftGridChainStartIndex+1;
while(leftGridChain->get_v_value(index2) >= lowervert[1])
{
index2++;
if(index2 > leftGridChainEndIndex)
break;
}
index2--;
sampleLeftSingleTrimEdgeRegion(uppervert, lowervert, leftGridChain, leftGridChainStartIndex+1, index2, pStream);
sampleLeftStripRec(leftChain, index1+1, botLeftIndex, leftGridChain, index2, leftGridChainEndIndex, pStream);
}
void sampleLeftStripRecF(vertexArray* leftChain,
Int topLeftIndex,
Int botLeftIndex,
gridBoundaryChain* leftGridChain,
Int leftGridChainStartIndex,
Int leftGridChainEndIndex,
primStream* pStream
)
{
if(topLeftIndex > botLeftIndex)
return;
if(leftGridChainStartIndex>=leftGridChainEndIndex)
return;
assert(leftChain->getVertex(topLeftIndex)[1] <= leftGridChain->get_v_value(leftGridChainStartIndex) &&
leftChain->getVertex(botLeftIndex)[1] >= leftGridChain->get_v_value(leftGridChainEndIndex));
Real secondGridChainV = leftGridChain->get_v_value(leftGridChainStartIndex+1);
Int index1 = topLeftIndex;
while(leftChain->getVertex(index1)[1] > secondGridChainV){
index1++;
if(index1>botLeftIndex)
break;
}
if(index1>botLeftIndex)
index1--;
else if(leftChain->getVertex(index1)[1] < secondGridChainV)
index1--;
sampleLeftOneGridStep(leftChain, topLeftIndex, index1, leftGridChain, leftGridChainStartIndex, pStream);
if(leftChain->getVertex(index1)[1] == secondGridChainV)
{
sampleLeftStripRecF(leftChain, index1, botLeftIndex,leftGridChain, leftGridChainStartIndex+1, leftGridChainEndIndex, pStream);
}
else if(index1 < botLeftIndex)
{
Real *uppervert, *lowervert;
uppervert = leftChain->getVertex(index1);
lowervert = leftChain->getVertex(index1+1); Int index2 = leftGridChainStartIndex+1;
while(leftGridChain->get_v_value(index2) >= lowervert[1])
{
index2++;
if(index2 > leftGridChainEndIndex)
break;
}
index2--;
sampleLeftSingleTrimEdgeRegion(uppervert, lowervert, leftGridChain, leftGridChainStartIndex+1, index2, pStream);
sampleLeftStripRecF(leftChain, index1+1, botLeftIndex, leftGridChain, index2, leftGridChainEndIndex, pStream);
}
}
void sampleLeftSingleTrimEdgeRegion(Real upperVert[2], Real lowerVert[2],
gridBoundaryChain* gridChain,
Int beginIndex,
Int endIndex,
primStream* pStream)
{
Int i,j,k;
vertexArray vArray(endIndex-beginIndex+1);
vArray.appendVertex(gridChain->get_vertex(beginIndex));
for(k=1, i=beginIndex+1; i<=endIndex; i++, k++)
{
vArray.appendVertex(gridChain->get_vertex(i));
if(gridChain->getUlineIndex(i) < gridChain->getUlineIndex(i-1))
{
pStream->begin();
pStream->insert(gridChain->get_vertex(i-1));
for(j=gridChain->getUlineIndex(i); j<= gridChain->getUlineIndex(i-1); j++)
pStream->insert(gridChain->getGrid()->get_u_value(j), gridChain->get_v_value(i));
pStream->end(PRIMITIVE_STREAM_FAN);
}
else if(gridChain->getUlineIndex(i) > gridChain->getUlineIndex(i-1))
{
pStream->begin();
pStream->insert(gridChain->get_vertex(i));
for(j=gridChain->getUlineIndex(i); j>= gridChain->getUlineIndex(i-1); j--)
pStream->insert(gridChain->getGrid()->get_u_value(j), gridChain->get_v_value(i-1));
pStream->end(PRIMITIVE_STREAM_FAN);
}
}
monoTriangulation2(upperVert, lowerVert, &vArray, 0, endIndex-beginIndex,
0,
pStream);
}
Int findIncreaseChainFromBegin(vertexArray* chain, Int begin ,Int end)
{
Int i=begin;
Real prevU = chain->getVertex(i)[0];
Real thisU;
for(i=begin+1; i<=end; i++){
thisU = chain->getVertex(i)[0];
if(prevU < thisU){
prevU = thisU;
}
else
break;
}
return i;
}
Int checkMiddle(vertexArray* chain, Int begin, Int end,
Real vup, Real vbelow)
{
Int i;
for(i=begin; i<=end; i++)
{
if(chain->getVertex(i)[1] < vup && chain->getVertex(i)[1]>vbelow)
return i;
}
return -1;
}
void sampleLeftOneGridStepNoMiddle(vertexArray* leftChain,
Int beginLeftIndex,
Int endLeftIndex,
gridBoundaryChain* leftGridChain,
Int leftGridChainStartIndex,
primStream* pStream)
{
leftGridChain->leftEndFan(leftGridChainStartIndex+1, pStream);
monoTriangulation2(leftGridChain->get_vertex(leftGridChainStartIndex),
leftGridChain->get_vertex(leftGridChainStartIndex+1),
leftChain,
beginLeftIndex,
endLeftIndex,
1, pStream);
}
void sampleLeftOneGridStep(vertexArray* leftChain,
Int beginLeftIndex,
Int endLeftIndex,
gridBoundaryChain* leftGridChain,
Int leftGridChainStartIndex,
primStream* pStream
)
{
if(checkMiddle(leftChain, beginLeftIndex, endLeftIndex,
leftGridChain->get_v_value(leftGridChainStartIndex),
leftGridChain->get_v_value(leftGridChainStartIndex+1))<0)
{
sampleLeftOneGridStepNoMiddle(leftChain, beginLeftIndex, endLeftIndex, leftGridChain, leftGridChainStartIndex, pStream);
return;
}
{
directedLine* poly = NULL;
sampledLine* sline;
directedLine* dline;
gridWrap* grid = leftGridChain->getGrid();
Real vert1[2];
Real vert2[2];
Int i;
Int innerInd = leftGridChain->getInnerIndex(leftGridChainStartIndex+1);
Int upperInd = leftGridChain->getUlineIndex(leftGridChainStartIndex);
Int lowerInd = leftGridChain->getUlineIndex(leftGridChainStartIndex+1);
Real upperV = leftGridChain->get_v_value(leftGridChainStartIndex);
Real lowerV = leftGridChain->get_v_value(leftGridChainStartIndex+1);
vert1[1] = vert2[1] = upperV;
for(i=innerInd; i>upperInd; i--)
{
vert1[0]=grid->get_u_value(i);
vert2[0]=grid->get_u_value(i-1);
sline = new sampledLine(vert1, vert2);
dline = new directedLine(INCREASING, sline);
if(poly == NULL)
poly = dline;
else
poly->insert(dline);
}
vert1[0] = grid->get_u_value(upperInd);
vert1[1] = upperV;
sline = new sampledLine(vert1, leftChain->getVertex(beginLeftIndex));
dline = new directedLine(INCREASING, sline);
if(poly == NULL)
poly = dline;
else
poly->insert(dline);
for(i=beginLeftIndex; i<endLeftIndex; i++)
{
sline = new sampledLine(leftChain->getVertex(i), leftChain->getVertex(i+1));
dline = new directedLine(INCREASING, sline);
poly->insert(dline);
}
vert2[0] = grid->get_u_value(lowerInd);
vert2[1] = lowerV;
sline = new sampledLine(leftChain->getVertex(endLeftIndex), vert2);
dline = new directedLine(INCREASING, sline);
poly->insert(dline);
vert1[1] = vert2[1] = lowerV;
for(i=lowerInd; i<innerInd; i++)
{
vert1[0] = grid->get_u_value(i);
vert2[0] = grid->get_u_value(i+1);
sline = new sampledLine(vert1, vert2);
dline = new directedLine(INCREASING, sline);
poly->insert(dline);
}
vert1[0]=vert2[0] = grid->get_u_value(innerInd);
vert2[1]=upperV;
vert1[1]=lowerV;
sline=new sampledLine(vert1, vert2);
dline=new directedLine(INCREASING, sline);
poly->insert(dline);
monoTriangulationOpt(poly, pStream);
poly->deleteSinglePolygonWithSline();
return;
}
Int i;
if(1
)
{
i=endLeftIndex;
Real prevU = leftChain->getVertex(i)[0];
for(i=endLeftIndex-1; i>=beginLeftIndex; i--){
Real thisU = leftChain->getVertex(i)[0];
if( prevU < thisU){
prevU = thisU;
}
else
break;
}
if(i+1 == endLeftIndex && leftChain->getVertex(endLeftIndex)[1] == leftGridChain->get_v_value(1+leftGridChainStartIndex))
i--;
Int j = beginLeftIndex+1;
if(leftGridChain->getInnerIndex(leftGridChainStartIndex+1) > leftGridChain->getUlineIndex(leftGridChainStartIndex))
{
j = findIncreaseChainFromBegin(leftChain, beginLeftIndex, i+1);
Int temp = beginLeftIndex;
if(j-1 == beginLeftIndex)
{
while(leftChain->getVertex(j-1)[1] == leftGridChain->get_v_value(leftGridChainStartIndex))
j++;
Real vert[2];
vert[0] = leftGridChain->get_u_value(leftGridChainStartIndex);
vert[1] = leftGridChain->get_v_value(leftGridChainStartIndex);
monoTriangulation2(
vert,
leftChain->getVertex(j-1),
leftChain,
beginLeftIndex,
j-2,
1,
pStream );
temp = j-1;
}
stripOfFanLeft(leftChain, j-1, temp, leftGridChain->getGrid(),
leftGridChain->getVlineIndex(leftGridChainStartIndex),
leftGridChain->getUlineIndex(leftGridChainStartIndex),
leftGridChain->getInnerIndex(leftGridChainStartIndex+1),
pStream,
1
);
}
stripOfFanLeft(leftChain, endLeftIndex, i+1, leftGridChain->getGrid(),
leftGridChain->getVlineIndex(leftGridChainStartIndex+1),
leftGridChain->getUlineIndex(leftGridChainStartIndex+1),
leftGridChain->getInnerIndex(leftGridChainStartIndex+1),
pStream,
0
);
Real vert[2][2];
vert[0][0]=vert[1][0] = leftGridChain->getInner_u_value(leftGridChainStartIndex+1);
vert[0][1] = leftGridChain->get_v_value(leftGridChainStartIndex);
vert[1][1] = leftGridChain->get_v_value(leftGridChainStartIndex+1);
monoTriangulation2(
&vert[0][0],
&vert[1][0],
leftChain,
j-1,
i+1,
1,
pStream);
}
else
{
i=beginLeftIndex;
Real prevU = leftChain->getVertex(i)[0];
for(i=beginLeftIndex+1; i<=endLeftIndex; i++){
Real thisU = leftChain->getVertex(i)[0];
if(prevU < thisU){
prevU = thisU;
}
else
break;
}
stripOfFanLeft(leftChain, i-1, beginLeftIndex, leftGridChain->getGrid(),
leftGridChain->getVlineIndex(leftGridChainStartIndex),
leftGridChain->getUlineIndex(leftGridChainStartIndex),
leftGridChain->getUlineIndex(leftGridChainStartIndex+1),
pStream,
1
);
Real vert[2][2];
vert[0][0]=vert[1][0] = leftGridChain->get_u_value(leftGridChainStartIndex+1);
vert[0][1] = leftGridChain->get_v_value(leftGridChainStartIndex);
vert[1][1] = leftGridChain->get_v_value(leftGridChainStartIndex+1);
vertexArray right(vert, 2);
monoTriangulation2(
&vert[0][0], &vert[1][0], leftChain,
i-1,
endLeftIndex,
1,
pStream);
}
}
void triangulateXYMono(Int n_upper, Real upperVerts[][2],
Int n_lower, Real lowerVerts[][2],
primStream* pStream)
{
Int i,j,k,l;
Real* leftMostV;
assert(n_upper>=1 && n_lower>=1);
if(upperVerts[0][0] <= lowerVerts[0][0])
{
i=1;
j=0;
leftMostV = upperVerts[0];
}
else
{
i=0;
j=1;
leftMostV = lowerVerts[0];
}
while(1)
{
if(i >= n_upper)
{
if(j<n_lower-1)
{
pStream->begin();
pStream->insert(leftMostV);
while(j<n_lower){
pStream->insert(lowerVerts[j]);
j++;
}
pStream->end(PRIMITIVE_STREAM_FAN);
}
break;
}
else if(j>= n_lower)
{
if(i<n_upper-1)
{
pStream->begin();
pStream->insert(leftMostV);
for(k=n_upper-1; k>=i; k--)
pStream->insert(upperVerts[k]);
pStream->end(PRIMITIVE_STREAM_FAN);
}
break;
}
else
{
if(upperVerts[i][0] <= lowerVerts[j][0])
{
pStream->begin();
pStream->insert(lowerVerts[j]);
k=i;
while(k<n_upper)
{
if(upperVerts[k][0] > lowerVerts[j][0])
break;
k++;
}
k--;
for(l=k; l>=i; l--)
{
pStream->insert(upperVerts[l]);
}
pStream->insert(leftMostV);
pStream->end(PRIMITIVE_STREAM_FAN);
i = k+1;
leftMostV = upperVerts[k];
}
else
{
pStream->begin();
pStream->insert(upperVerts[i]);
pStream->insert(leftMostV);
k=j;
while(k< n_lower)
{
if(lowerVerts[k][0] >= upperVerts[i][0])
break;
pStream->insert(lowerVerts[k]);
k++;
}
pStream->end(PRIMITIVE_STREAM_FAN);
j=k;
leftMostV = lowerVerts[j-1];
}
}
}
}
void stripOfFanLeft(vertexArray* leftChain,
Int largeIndex,
Int smallIndex,
gridWrap* grid,
Int vlineIndex,
Int ulineSmallIndex,
Int ulineLargeIndex,
primStream* pStream,
Int gridLineUp
)
{
assert(largeIndex >= smallIndex);
Real grid_v_value;
grid_v_value = grid->get_v_value(vlineIndex);
Real2* trimVerts=(Real2*) malloc(sizeof(Real2)* (largeIndex-smallIndex+1));
assert(trimVerts);
Real2* gridVerts=(Real2*) malloc(sizeof(Real2)* (ulineLargeIndex-ulineSmallIndex+1));
assert(gridVerts);
Int k,i;
if(gridLineUp)
for(k=0, i=smallIndex; i<=largeIndex; i++, k++)
{
trimVerts[k][0] = leftChain->getVertex(i)[0];
trimVerts[k][1] = leftChain->getVertex(i)[1];
}
else
for(k=0, i=largeIndex; i>=smallIndex; i--, k++)
{
trimVerts[k][0] = leftChain->getVertex(i)[0];
trimVerts[k][1] = leftChain->getVertex(i)[1];
}
for(k=0, i=ulineSmallIndex; i<= ulineLargeIndex; i++, k++)
{
gridVerts[k][0] = grid->get_u_value(i);
gridVerts[k][1] = grid_v_value;
}
if(gridLineUp)
triangulateXYMono(
ulineLargeIndex-ulineSmallIndex+1, gridVerts,
largeIndex-smallIndex+1, trimVerts,
pStream);
else
triangulateXYMono(largeIndex-smallIndex+1, trimVerts,
ulineLargeIndex-ulineSmallIndex+1, gridVerts,
pStream);
free(trimVerts);
free(gridVerts);
}