Java-Gaming.org Java4K winners: [ by our judges | by the community ]         
Featured games (67)
games approved by the League of Dukes
Games in Showcase (∞)
games submitted by our members



News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: [1]
  Print  
  Polygon triangulation  (Read 2498 times)
0 Members and 1 Guest are viewing this topic.
Offline Bonbon-Chan

Sr. Member
**

Posts: 417
Medals: 14



« on: 2009-09-28 10:54:12 »

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  Angry)
- 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  Tongue
ps2 : I hear about an GLU Tesselator in LWJGL 2.2

Offline kevglass
« League of Dukes »

JGO Kernel
*****

Posts: 5214
Medals: 49


Mentally unstable, best avoided.


« Reply #1 on: 2009-09-28 10:58:54 »

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

Offline Bonbon-Chan

Sr. Member
**

Posts: 417
Medals: 14



« Reply #2 on: 2009-09-30 04:55:58 »

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

I manage to get better result  Tongue. The trick is to transform polygon in several polygons that triangulator can deal with  Grin
It need lots of tests and calculations  Undecided 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! Go get 'em!
Offline broumbroum

Sr. Member
**

Posts: 384



« Reply #3 on: 2009-10-08 08:11:05 »

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

::::... :..... :::::: ;;;:::™ b23:production 2006 GNU/GPL @ http://b23prodtm.webhop.info
on sf.net: /projects/sf3jswing
Java (1.6u10 plz) Web Start pool
dev' VODcast[/ur
Offline Bonbon-Chan

Sr. Member
**

Posts: 417
Medals: 14



« Reply #4 on: 2009-10-09 03:32:43 »

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  Grin

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);
    }
Offline CommanderKeith

JGO Wizard
****

Posts: 1455
Medals: 9



« Reply #5 on: 2009-11-19 08:19:40 »

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.

Offline kevglass
« League of Dukes »

JGO Kernel
*****

Posts: 5214
Medals: 49


Mentally unstable, best avoided.


« Reply #6 on: 2009-11-19 08:41:13 »

GLUTesselator is software.

Kev

Offline CommanderKeith

JGO Wizard
****

Posts: 1455
Medals: 9



« Reply #7 on: 2009-11-19 08:48:18 »

I didn't know that, thanks Smiley

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.


Pages: [1]
  Print  
 
 
Jump to:  

Powered by MySQL Powered by PHP Powered by SMF 1.1.16 | SMF © 2011, Simple Machines Valid XHTML 1.0! Valid CSS!
Page created in 0.128 seconds with 21 queries.