Tesselation of Mono Connected Non Convex Polygon

Download source files - 41.23 KB

Sample Image - PolyTry.jpg

Introduction

A simple alternative to OpenGL polygon tesselation callback. You can focus on file triangle.h that contain the class to evaluate convexity of polygon and tesselate the polygon. No extra points are inserted. You can work only with planar polygon also in 3D.

Every suggestion in order to speed up the class and create better tesselation ('better' triangles) is appreciated.

History

6^th February, 2002: Initial post

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

About the Author

Peppino Sbargzeguti

United States

Member

No Biography provided

Article Top

Poor

Excellent

Add a reason or comment to your vote: x
Votes of 3 or less require a comment

Comments and Discussions

You must Sign In to use this message board.

Search this forum
	Profile popups Spacing Noise Layout Per page

Found an index range error in code

TruePyroman

23 Feb '03 - 14:38

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!!! OMG | :OMG:

)
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

Re: Found an index range error in code

topus

10 Apr '03 - 2:46

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 sub-alligned) 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