There is still a flaw in that algo. It couldn’t survive this polygon :
customPoly=(
(0, -0.329999148100614548) ,
(1, -0.329999148100614548) ,
(-1, -.5) ,
(-1, -0.329999148100614548) ,
(-.7, -0.329999146237969398) ,
(-.5, -0.329999146237969398) ,
)
In that case, ri increases endlessly.
I tried to fix it by giving a tiny tolerance (-1.0e-15) rather than 0, but didn’t work :
float crossResult = CROSS(vert[v].pt, vert[rc[ri - 1]].pt,
vert[rc[ri]].pt);
if ( crossResult >= -1.0e-15 ) /* could be convex corner or straight */
{
printf("convec/straight, ri = %d, ",ri);
cout<<"cross = "<<crossResult<<", v = "<<v<<", endv = "<<endv<<endl;
if ( crossResult > 0) /* convex corner: cut it off */
_result.push_back(Triangle(this, rc[ri - 1], rc[ri], v));
/* else : perfectly straight, will be abandoned anyway */
ri--;
rc.pop_back();
nassertv(ri + 1 == (int)rc.size());
}
else /* concave, add v to the chain */
{
ri++;
printf("concave, ri = %d, ",ri);
cout<<"cross = "<<crossResult<<", v = "<<v<<", endv = "<<endv<<endl;
rc.push_back(v);
nassertv(ri + 1 == (int)rc.size());
vpos = mchain[vpos].next;
v = mchain[vpos].vnum;
}
log :
concave, ri = 2, cross = -1.86265e-009, v = 4, endv = 2
concave, ri = 2, cross = -0.119001, v = 5, endv = 2
empty, ri = 1
concave, ri = 2, cross = -1.86265e-009, v = 1, endv = 2
concave, ri = 3, cross = -1.86265e-009, v = 3, endv = 2
concave, ri = 2, cross = -3.72529e-009, v = 4, endv = 2
concave, ri = 2, cross = -1.86265e-009, v = 1, endv = 2
concave, ri = 3, cross = -1.86265e-009, v = 2, endv = 2
concave, ri = 3, cross = -1.86265e-009, v = 3, endv = 2
concave, ri = 2, cross = -1.86265e-009, v = 1, endv = 2
concave, ri = 2, cross = -3.72529e-009, v = 4, endv = 2
concave, ri = 2, cross = -0.289001, v = 5, endv = 2
empty, ri = 1
concave, ri = 2, cross = -1.86265e-009, v = 1, endv = 2
concave, ri = 3, cross = -1.86265e-009, v = 3, endv = 2
concave, ri = 2, cross = -3.72529e-009, v = 4, endv = 2
concave, ri = 2, cross = -1.86265e-009, v = 1, endv = 2
concave, ri = 3, cross = -1.86265e-009, v = 2, endv = 2
concave, ri = 3, cross = -1.86265e-009, v = 3, endv = 2
concave, ri = 2, cross = -1.86265e-009, v = 1, endv = 2
concave, ri = 2, cross = -3.72529e-009, v = 4, endv = 2
concave, ri = 2, cross = -0.289001, v = 5, endv = 2
empty, ri = 1
concave, ri = 2, cross = -1.86265e-009, v = 1, endv = 2
concave, ri = 3, cross = -1.86265e-009, v = 3, endv = 2
concave, ri = 2, cross = -3.72529e-009, v = 4, endv = 2
concave, ri = 2, cross = -1.86265e-009, v = 1, endv = 2
.
repeated endlessly
.
It couldn’t catch that case. Even the 1st one (cross = -1.86265e-009) was wrong, it should jump to convex/straight, but didn’t.
This didn’t work too :
double crossResult = CROSS(vert[v].pt, vert[rc[ri - 1]].pt,
vert[rc[ri]].pt);
if ( crossResult >=double(-1.0e-15) ) /* could be convex corner or straight */
THIS WORKS :
float crossResult = CROSS(vert[v].pt, vert[rc[ri - 1]].pt,
vert[rc[ri]].pt);
if ( (crossResult >= 0) ||
((crossResult<0) && (fabs(crossResult)>1.0e-15)) ) /* could be convex corner or straight */
I’m simply a newb in C++, I don’t know any better way.
log :
convec/straight, ri = 1, cross = -1.86265e-009, v = 4, endv = 2
empty, ri = 1
convec/straight, ri = 1, cross = 0.0510003, v = 5, endv = 2
empty, ri = 1
convec/straight, ri = 1, cross = 0.289001, v = 6, endv = 2
empty, ri = 1
convec/straight, ri = 1, cross = -1.86265e-009, v = 1, endv = 2
empty, ri = 1
convec/straight, ri = 1, cross = -0, v = 3, endv = 2
empty, ri = 1
convec/straight, ri = 1, cross = 0, v = 4, endv = 2
empty, ri = 1
convec/straight, ri = 1, cross = 1.86265e-009, v = 1, endv = 2
empty, ri = 1
But, unfortunately, by doing it this way, for sharp spikes, it wouldn’t work properly (I tried it with the spiky circle sample, 500-1000 vertices).
Any ideas ?
Thanks.