Polygon triangulation

[Bonbon-Chan]

Hi there,

for some reason, I want to do a "realtime" SVG renderer. For now, I manage to :
- load the file (even the arcs, what a noughty thing  )
- construct polygons for filling and stroking
- a basic polygon triangulation

It work pretty well (and quicker than expected for an none optimized test). But my polygon are not "simple" ones and some rendering are wrong. I use the "Ears" algorithm right now (and this problem is quite difficult).

There's a quick&dirty test. It compares my triangulation with the Java2D shape drawing.

Any idea about the problem.

ps1 : I just gone an idea while writing this post 
ps2 : I hear about an GLU Tesselator in LWJGL 2.2

[kevglass]

There's a series of different triangulators in Slick you could rip off. They all comply to the Triangulator interface so it should be easy to compare them. AFAIK none copy with holes tho.

Kev

[Bonbon-Chan]

I take a look to them and they all use more or less the same algorithm : "Ears algorithm" 

I manage to get better result  . The trick is to transform polygon in several polygons that triangulator can deal with 
It need lots of tests and calculations  and it's not perfect.

I will have to do lot's of optimization but it seems to be fast enough for now.

Games published by our own members! Check 'em out!

[broumbroum]

It may be properly known as "Polygon Tesselation". Java 2D Shapes have PathIterator's that handles "Winding Rules" which is part of this chapter of OpenGL : http://glprogramming.com/red/chapter11.html

[Bonbon-Chan]

It may be properly known as "Polygon Tesselation". Java 2D Shapes have PathIterator's that handles "Winding Rules" which is part of this chapter of OpenGL : http://glprogramming.com/red/chapter11.html

Thanks, but I allready know it 

1   2   3   4   5   6   7   8   9   10   11   12   13   14   15   16   17   18   19   20   21   22   23   24   25   26   27   28   29   30   31   32   33   34   35   36   37   38   39   40   41   42   43   44   45   46   47   48   49   50   51   52   53   54   55   56   57   58   59   60

public void create(Shape shape)   {     double doubles[] = new double[6];     Point2D.Double pt = null;     Point2D.Double lastPoint = null;     Point2D.Double lastMove = null;     clear();     PathIterator it = shape.getPathIterator(null, 0.25);     //PathIterator it = shape.getPathIterator(null);     while(!it.isDone())     {       int type = it.currentSegment(doubles);       switch(type)       {         case PathIterator.SEG_LINETO :           pt = new Point2D.Double(doubles[0],doubles[1]);           if (pt.distance(lastPoint)>0.0001)           {             addPoint( pt );             lastPoint = pt;           }         break;         case PathIterator.SEG_MOVETO :           pt = new Point2D.Double(doubles[0],doubles[1]);           if (lastMove != null)           {             if (current.get(current.size()-1).distance(lastMove)<0.0001)             {               current.remove(current.size()-1);             }           }           newPolygone();           addPoint( pt );           lastPoint = pt;           lastMove = pt;         break;         case PathIterator.SEG_CLOSE :         break;         default :       }       it.next();     }     if (lastMove != null)     {       if (current.get(current.size()-1).distance(lastMove)<0.0001)       {         current.remove(current.size()-1);       }     }   }

But there is something even greater in Java 2D, it can generate a shape form an outline style and a filling shape :

1   2   3   4   5   6   7   8   9   10   11   12   13   14   15   16   17   18   19   20

createPath(p);     if (style.fill != null)     {       GL11.glColor3f((float)style.fill.getRed()/255.0f,                      (float)style.fill.getGreen()/255.0f,                      (float)style.fill.getBlue()/255.0f);             drawGlShape(path);     }     if(style.stroke != null)     {       GL11.glColor3f((float)style.stroke.getRed()/255.0f,                      (float)style.stroke.getGreen()/255.0f,                      (float)style.stroke.getBlue()/255.0f);             Shape outLinePath = style.getBasicStroke().createStrokedShape(path);       drawGlShape(outLinePath);     }

[CommanderKeith]

Hi Bonbon-Chan,

Did you ever give LWJGL's new GLUTesselator a go? I'm wondering whether it's faster than tesselating in software. I suppose for your very complex polygons the openGL card's algorithm  might not be stable enough and you want control over how it is tesselated.

[kevglass]

GLUTesselator is software.

Kev

[CommanderKeith]

I didn't know that, thanks

And cheers for letting us use your slick tessellation code. It's great how many polygon tesselation routines are in there. Also the GeomUtils class is pretty cool with its constructive area geometry.