|
|
Comments and Discussions
|
|
 |
|
hello viewres
please give your suggestions. im having a dfx object and i want to cut the object in slicing means im having 10/10 mm squere object. i want it to cut it in 10 parts so each part is containing 10 mm width and 1 mm height. and i also need it's vertex values in opengl.
so please send me the suggestions.
any suggestion most welcome
hi
|
|
|
|
|
I found this routine sometimes produces incorrect tesselation. When certain points in the polygon winding are colinear, it can skip over them and produce triangles outside of the original polygon.
My fix simply classifies points on the edge of the test triangle as 'inside' instead of 'outside'. This appears to be a stable and beneficial fix so far.
Example Input:
poly normal (0.000f,-0.500f,0.866f)
poly points
(0.700f,6.500f,4.071f) // 0
(0.700f,5.500f,3.494f) // 1 This point gets mis-classified with 2,8,9 triangle
(-1.700f,5.500f,3.494f) // 2
(-1.700f,6.500f,4.071f) // 3
(-2.500f,6.500f,4.071f) // 4
(-7.300f,1.700f,1.300f) // 5
(11.300f,1.700f,1.300f) // 6
(7.500f,5.500f,3.494f) // 7
(4.300f,5.500f,3.494f) // 8
(4.300f,6.500f,4.071f) // 9
Old Code in function IsPointInside():
pmq2.Vector(m_e1,ntmp); if( (B0=m_N.Dot(ntmp)) <= 0.0 ) return false;
m_e0.Vector(pmq2,ntmp); if( (B1=m_N.Dot(ntmp)) <= 0.0 ) return false;
return ( (m_A-B0-B1) > 0.0 ? true : false );
New Code:
pmq2.Vector(m_e1,ntmp); if( (B0=m_N.Dot(ntmp)) < 0.0 ) return false;
m_e0.Vector(pmq2,ntmp); if( (B1=m_N.Dot(ntmp)) < 0.0 ) return false;
return ( (m_A-B0-B1) < 0.0 ? false : true);
Helpful explaination of internal variables:
//...........^.....
//.........I/......
//.N......./.......
//.^...e0./........
//.|...../__-->p...
//.|...K.\.........
//........\...A....
//......e1.\.......
//..........\......
//...........v.....
//..........J......
//(I replaced spaces with dots as they were not preserved in post?)
//
// I,J,K (points of current test triangle, indices or indirect indices)
// e0,e1 (edges from IK, JK)
// A (Area of current triangle, is actually area*2)
// N (Normal of current triangle, not unit length)
//
// p Test point if in current triangle.
//
Edit....
Further testing shows that neither the old or new code correctly and consistently handles coincident and colinear points. (Eg. An example of a coincident point, is a Figure '8' polygons that does not actually cross over, just converges in the middle.)
Example Input:
// Eg. Coincident point, figure 8 style
poly normal (0.000f,-0.500f,0.866f)
poly points
(1.700f,6.300f,2.801f)
(4.300f,3.700f,1.300f)
(5.700f,3.700f,1.300f)
(7.000f,5.000f,2.051f)
(8.300f,3.700f,1.300f)
(9.300f,3.700f,1.300f)
(8.000f,5.000f,2.051f)
(7.000f,5.000f,2.051f)
(1.700f,10.300f,5.111f)
This should help more with coincident points:
Old code in IsAnyPointInside():
if( ( ip < i || ip > k ) &&
IsPointInside(points[m_nIndex[ip]],points[ik]) )
{
return true;
}
New code:
if( ip < i || ip > k )
{
// NOTE: This is Vector3 exact equality test
if( points[m_nIndex[ip]].Equal(points[m_nIndex[i]])
|| points[m_nIndex[ip]].Equal(points[m_nIndex[j]])
|| points[m_nIndex[ip]].Equal(points[m_nIndex[k]])
)
{
continue; // Identical points are not inside, they do not hurt turns
}
if( IsPointInside(points[m_nIndex[ip]],points[ik]) )
{
return true;
}
}
If topus's suggested change is valid, it should read
//
// j is alligned from i to k ?
//
if( ((-FLT_EPSILON) < m_A && m_A < FLT_EPSILON) || // Area OR Poor Normal
((-FLT_EPSILON) < m_N[0] && m_N[0] < FLT_EPSILON &&
(-FLT_EPSILON) < m_N[1] && m_N[1] < FLT_EPSILON &&
(-FLT_EPSILON) < m_N[2] && m_N[2] < FLT_EPSILON ))
return degenerate;
// NOTE: This code is more efficient on PC with eg. 'fabsf(m_A) <= FLT_EPSILON' to reduce float compares.
Also note that you can help the algorithm by removing 'junk' before processing. Eg. project 3D points onto plane (of which normal is used). Remove degeneracies like coincident and colinear points. Snapping and merging points may help, but could lead to bad-snaps that cause self intersections.
Edit:
I have found another case which I believe shows a flaw in the algorithm. As 'ears' are clipped off the polygon, the remaining polygon can become self intersecting and fail 'point in poly' test, to produce triangles outside the original shape.
Example input:
poly normal(0,0,1)
(10.52881622f,-1.25890017f,0.00000000f)
(10.52881241f,0.24110639f,0.00000000f)
(-1.47119045f,0.24110317f,0.00000000f)
(-1.47119141f,-1.25889719f,0.00000000f)
(4.52881575f,-1.25890088f,0.00000000f)
(4.52881479f,-3.25889254f,0.00000000f)
(6.08583260f,-3.25889111f,0.00000000f)
(6.08583069f,-1.25889945f,0.00000000f)
The fix:
in function Triangulate()
in 'case convex :'
in else, after 'RemoveVertex'
// Advance to preserve poly integrity
i = j;
j = k;
k++;
This allows the point AFTER the removed triangle point to be the start of the next test triangle. This helps with near colinear points that fan out from an otherwise stationary start point.
Edit:
There are still issues with the code. The bottom line is that the original algorithm does not handle simple non-covex polys with colinear, but non intersecting segments. The overall algorithm does not handle polygons that intersect in anyway, including at single points, though it often produces a correct or near correct result.
Please comment on this.
|
|
|
|
|
In my crossplatform c++ framework ( www.amanith.org ) i've implemented a fast sweepline tesselator that can handle non simple polygons with holes , and some common degenerations.
For every questions abuot this, email me at: mfabbri@amanith.org
|
|
|
|
|
Change the line:
for( register int i=0 , j=1 ; j < nPoints ; i++ , j++ ){
to:
for( register int i=0 , j=1 ; i < nPoints ; i++ , j++, j=j%nPoints ){
and normal of the polygon will be calculated correctly.
Torsten
|
|
|
|
|
Thanks for the code.
Martin
|
|
|
|
|
Thank you very much for this example!
It's the simple and best tesselation
algorithm I found over the internet!
I found a special case that pop-up an
index range error (very hard to find!!!  )
in the Triangulate function.
The "k" index missed 2 hits because it
starts at k=2... So I did a little patch!
New loop:
for( int i=0 , j=1 , k=2 ; k < nVertex+3 ; )
New indexes:
int ib = i % nVertex;
int jb = j % nVertex;
int kb = k % nVertex;
Here is the modified function:
// BEGIN
int nTriangle= 0;
int nVertex = nCount;
//
AllocIndex(nCount);
//
bool bNoErrors = true;
//
while( nVertex > 3 && bNoErrors )
{
//
// tri to remove one vertex...
//
bNoErrors = false;
//
for( int i=0 , j=1 , k=2 ; k < nVertex+3 ; )
{
if( nVertex == 0 )
break;
int ib = i % nVertex;
int jb = j % nVertex;
int kb = k % nVertex;
//
switch( TriangleArea(points,
m_nIndex[ib],
m_nIndex[jb],
m_nIndex[kb],
normal) )
{
//
// ok. flush face && remove vertex j
//
case convex :
//
// Testing containement
//
if( IsAnyPointInside(points,ib,jb,kb,nVertex) ){
//
// go ahead..
//
i = j;
j = k;
k++;
}
else
{
nTriangle++;
AddFace(points,m_nIndex[ib],m_nIndex[jb],m_nIndex[kb]);
//
// remove vertex j
//
nVertex = RemoveVertex(jb, nVertex);
bNoErrors= true;
}
break;
case concave :
//
// go ahead..
//
i = j;
j = k;
k++;
break;
case degenerate :
//
// remove vertex j
//
nVertex = RemoveVertex(jb, nVertex);
bNoErrors= true;
break;
}
}
}
return nTriangle;
// END
TruePyroman
|
|
|
|
|
Hi ,
Ok Delauney rules in good tesselation. But in the case of non-convex poly you have to use the constrained form of the algorithm (DCT). You can achieve good tesselation without get rid of your algorithm :
as a post - process phase you can "mimimize" the edge size of convex quads. It's like use the turn edge tools in 3ds max. In this way, long triangles are converted in more equilaterals ones.
If i got time i'll try and send it to you.
|
|
|
|
|
I would suggest using a delauney triangulation - it will cut down the number of thin strips, and produce a much better tesselation.
Here's a link..
or do a search on google.
|
|
|
|
|
Pepito Sbazzeguti... "Gratta il Pepito, viene fuori il Peppone!"
Certo che avresti potuto essere più originale con lo pseudonimo.
Samantha Fox
|
|
|
|
|
I have a suggestion for you: Write up that article properly!
That is, why don't you put some explanation of the problem itself, the solution utilized by your code, the potential use of the code and some code examples of how to use it in another application etc. ?
|
|
|
|
|
Or is it a code "Ad-Lib"?  (the childrens fill in the blank language game, not the old sound card company)
____ ____ ________ ____ ________ ____ ________ ____ ________ ____ ________ ____ ________ ____ ________ ____ ________ ____ ________ ____ ________ ____ ________ ____ ________ ____ ________ ____ ________ ____ ________ ____ ________ ____ ________ ____ ________ ____ ________ ____ ________ ____ ________ ____ ________ ____ ________ ____ ________ ____ ________ ____ ________ ____ ________ ____ ________ ____ ________ ____ ________ ____ ________ ____ ________ ____ ________ ____ ________ ____ ________ ____ ________ ____ ________ ____ ________ ____ ________ ____ ________ ____ ____
|
|
|
|
|
Why would you do something like this? What practical application does this have?
|
|
|
|
|
|
|
 General  News  Suggestion  Question  Bug  Answer  Joke  Rant  Admin
|
Tesselation of mono connected non convex polygon
| Type | Article |
| Licence | CPOL |
| First Posted | 6 Feb 2002 |
| Views | 149,618 |
| Downloads | 1,112 |
| Bookmarked | 20 times |
|
|
Submit an article or tip
Post your Blog
