Add your own alternative version
Stats
172.1K views 1.4K downloads 21 bookmarked
Posted
6 Feb 2002

Comments and Discussions



You had implemented it?
My god! Your code is too similiar to SGI/libtess.
Such functions as "sweepevent", "TessellateMonotoneRegion" ..., are almost the same to SGI/libtess.
I suggest you add " Thanks to SGI/libtess " in the header.
Hey, kavenger,
you should not always call "AddContourPoint",
If you had research the struct of Mesh carefully,you can add all your vertex once together. This can make you function 100% faster.
============================
Gods know that I really love you from the bottom of my heart,but I forget to tell you that...





Hey Liu,
I have read all libtess sources/docs, and got inspired during the writing of my tessellator, as weel as for another good paper, that explain the sweepline algorithm in details ( http://www.cs.ucsb.edu/~suri/cs235/Triangulation.pdf ).So, yes, i'll follow your suggestion adding the greetings to SGI.
My decision to rewite a tesselator instead of using the libtess ones is due to the fact that i had a try to be more robust and support more degeneration cases, without to introduce overheads of any kind.
Anyway, now, i'm oriented in a direction to use OpenGL drawing tecniques that don't need of the tesselation step, beacuse this step is too expensive, and it needs a too high robustness level.
Just for curiosity,
Are you using Amanith? Do u use the tessellation for drawing purposes or for something other?
( my mail is: mfabbri ]at[ amanith ]dot[ 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





It could be better for performance issue to exclude the case of last j from the for loop, in order not to compute the modulo each time.
I would do :
normal[0]=normal[1]=normal[2]=0.0f;
for( register int i=0 , j=1 ; j < nPoints ; i++ , j++ ){
normal[0]+= ( points[i][1]  points[j][1] ) * ( points[i][2] + points[j][2] ) ;
normal[1]+= ( points[i][2]  points[j][2] ) * ( points[i][0] + points[j][0] ) ;
normal[2]+= ( points[i][0]  points[j][0] ) * ( points[i][1] + points[j][1] ) ;
}
// last case :
normal[0]+= ( points[i][1]  points[0][1] ) * ( points[i][2] + points[0][2] ) ;
normal[1]+= ( points[i][2]  points[0][2] ) * ( points[i][0] + points[0][0] ) ;
normal[2]+= ( points[i][0]  points[0][0] ) * ( points[i][1] + points[0][1] ) ;

It would also be a good idea to delete Vector3F array in CPolyTryView::OnDraw(CDC* pDC) after call to triangulate() to avoid memory leaks !





Area computation is bugged :
you should add in CPolyTriView::OnDraw()
existing :
//
for( int i=0 ; i < m_nPoints ; i++ ){
points[i][0] = m_points[i].x;
points[i][1] = m_points[i].y;
if( i ) Area+= ( m_points[i].x * m_points[i1].y  m_points[i1].x * m_points[i].y) * 0.5f;
}
//
// added after for loop :
Area += ( m_points[0].x * m_points[i1].y  m_points[i1].x * m_points[0].y) * 0.5f;
Also, if area computation is only used for normal deduction, you can avoid *0.5f as it will not change area sign.





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 popup 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





Another litle improvement:
Use previus code and change the line
while( nVertex > 3 && bNoErrors )
with the line
while( nVertex >= 3 && bNoErrors )
Also to solve the problem with degenerate points (alligned or suballigned) replace the test in function Triangle Area (that work fine for planar 2D polygon's)
//
// j is alligned from i to k ?
//
if( (FLT_EPSILON) < m_A && m_A < FLT_EPSILON )
return degenerate;
with:
//
// j is alligned from i to k ?
//
if( (FLT_EPSILON) < m_A && m_A < FLT_EPSILON &&
(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;
Last (but not least) if some consecutive triangles as the same origin vertex you can optimizing opengl drawing code collecting the common side (from two consecutive triangles) and using triangle fan (example triangle vertex 0,1,2 && 0,2,3 etc.. can be collected in a triangle fan 0,1,2,3 etc..)
Thanks very much for this very speedy code





Hi ,
Ok Delauney rules in good tesselation. But in the case of nonconvex 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.





A more little explanation about my article. In order to tesselate the polygon i use this tecnique:
First compute the normal of polygon (i use the newell method see Graphic Gems..)
For each sequence of three vertex ( i, j, k ) in the polygon compute the vector area (alias normal of triangle).
If the normal go in the opposite direction of polygon normal the triangle is 'concave' and go ahead.
If the area il 0.0 the point j is alligned from i to k and eliminated from the list of vertex.
If the normal of triangle is in the same direction of polygon normal the triangle is convex. In the last case check if any other point is inside the triangle (the IsPointInside function). This function test if the point is on solid angle ik ^ jk. if this is true compute distance of intersection k>point to line ij and test distance. If all is good emit triangle, remove vertex j from list and go to the next triplet....
The reason for wich i posted this article is that i don't find this tecnique in any book or article and ave a doubt about the mathematical basic of my algoritm In other words is true that it work in any case ? (my experience ask yes but is very far from a theorem...)
The Delauney algortim work fine but is 'computational' more expensive than my algortim (using my Delauney implementation) for this reason i try this way. At the end my apologize for my poor english but my sincerly idea is to contribute to codeproject and suggest a way to resolv a problem that i found. Thanks pepito.







General News Suggestion Question Bug Answer Joke Praise Rant Admin Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

