Ear Clipping Triangulation Algorithm

  ... information about changes and new features of AndEngine,

Ear Clipping Triangulation Algorithm

Postby Nicolas Gramlich » Wed Sep 15, 2010 12:06 pm

Hello Community,

these days I'm finishing(/fixing) an EarClipping algorithm. That algorithm is able to triangulate any 'polygon' (List<Vector2> in our case) to a set of triangles. Sounds useless :?: Oh no :P

Read more soon... :)

Best Regards,
Nicolas
Nicolas Gramlich
Site Admin
 
Posts: 1734
Joined: Mon Jun 07, 2010 6:20 pm
Location: Schriesheim, Germany

Re: Ear Clipping Triangulation Algorithm

Postby ichi » Wed Sep 15, 2010 2:05 pm

Awesome!

I've been reading a lot about this lately, thinking I would find some easy open source code to use for triangulation but with no great success... I really need this for static ground shapes in my level editor, so this is great news! :)
ichi
 
Posts: 62
Joined: Mon Sep 06, 2010 1:47 pm

Re: Ear Clipping Triangulation Algorithm

Postby damucz » Wed Sep 15, 2010 2:33 pm

ichi wrote:Awesome!

I've been reading a lot about this lately, thinking I would find some easy open source code to use for triangulation but with no great success... I really need this for static ground shapes in my level editor, so this is great news! :)


As a standalone part of another engine?
http://www.apistudios.com/hosted/marzec ... lator.html

There is also very effective and fast non-java solution.
http://www.compgeom.com/~piyush/scripts/triangle/

And other sources again in Java... (which I didn't try personally)
http://www.cs.cornell.edu/home/chew/Delaunay.html
http://www.cs.bgu.ac.il/~benmoshe/DT/De ... 20Java.htm
http://www.csie.ntu.edu.tw/~b5506061/vo ... ronoi.html
http://goanna.cs.rmit.edu.au/~gl/resear ... aunay.html
http://www.koders.com/java/fid47630D7A3 ... px?s=graph

Nothing against Nicolas. It's definitely good to have the (math) tools directly in engine.

Dan
damucz
 
Posts: 2
Joined: Mon Jul 26, 2010 11:02 am

Re: Ear Clipping Triangulation Algorithm

Postby Nicolas Gramlich » Wed Sep 15, 2010 6:01 pm

Hi,

the original source is from:
http://cgm.cs.mcgill.ca/~godfried/teach ... ithm2.html
Main Source-file: http://cgm.cs.mcgill.ca/~godfried/teach ... arCut.java

Afaik Mario Zechner (badlogicgames.com) then adapted it to work with List<Vector2> instead of arrays.
Another really good explanation of the algorihm can be found here: http://www.geometrictools.com/Documenta ... ipping.pdf

The algorithm worked very well, as long as you didn't have collinear edges like you can find them in strictly geometrical (not hand-drawn) shapes like these tetris blocks:
tetristower.png
Stacked Tetris Blocks.
tetristower.png (34.12 KiB) Viewed 4111 times

So i (most likely) fixed that problem :) . The above screenshot was taken from AndEngine :D

I'll push the source today or tomorrow, sou you can give it a try too :)

Best Regards,
Nicolas
Nicolas Gramlich
Site Admin
 
Posts: 1734
Joined: Mon Jun 07, 2010 6:20 pm
Location: Schriesheim, Germany

Re: Ear Clipping Triangulation Algorithm

Postby K2DaC » Wed Sep 15, 2010 8:46 pm

great ! Perfect timing, will check it out the next days. here's my storry / screen:

Image

First attemp : Create Concave Bodys with PhysicsExample - wasted hours
Second attemp : Create each block with Joints, so every Block was made of 4 Bodys, 4 Faces, 3 WeldJoints.
Big Performance Problems on Device with 50++ Blocks (50 Blocks = 200 Bodys, 200 Faces, 150 Joints, ...)
Third attemp : Code review + Blocks are made of 1 or 2 Bodys, and 0 or 1 Joint.

Game ist still under heavy construction and for education purposes only
Done :
autoParallaxBackground with Clowds :=)
2-Way OnScreenController

ToDo :
- 4th attemp with Blocks :)
- Rotation still does not Really work
- a lot ...
K2DaC
 
Posts: 16
Joined: Sat Sep 11, 2010 6:40 am
Location: Berlin, Germany

Re: Ear Clipping Triangulation Algorithm

Postby blandonfrank » Wed Sep 15, 2010 11:43 pm

Great news!
looking forward to testing the sample.
blandonfrank
 
Posts: 298
Joined: Fri Jul 23, 2010 9:46 pm

Re: Ear Clipping Triangulation Algorithm

Postby andcoder » Thu Sep 16, 2010 8:05 pm

Hi there, please update! Any sample available yet?
andcoder
 
Posts: 13
Joined: Thu Aug 05, 2010 7:11 pm

Re: Ear Clipping Triangulation Algorithm

Postby Nicolas Gramlich » Thu Sep 16, 2010 11:37 pm

Hi,

Changeset: http://code.google.com/p/andenginephysi ... 88fbc18c2d

Actual class: http://code.google.com/p/andenginephysi ... lator.java

Pretty useful once a Vector2[] has been triangulated: PhysicsFactory.createTrianglulatedBody(...)

Summing up, the usage looks somewhat similar to this:

Syntax: [ Download ] [ Hide ]
Using java Syntax Highlighting
  1. final List<Vector2> vertices = new ArrayList<Vector2>(); // Add some vertices here!
  2. final ITriangulationAlgoritm triangulationAlgoritm = new EarClippingTriangulator();
  3. final List<Vector2> triangles = triangulationAlgoritm.computeTriangles(vertices);
  4.                        
  5. final Body body = PhysicsFactory.createTrianglulatedBody(pPhysicsWorld, pShape, triangles, pBodyType, pFixtureDef);
Parsed in 0.031 seconds, using GeSHi 1.0.8.4


Hope this helps :)

Bugs might be included :P and the API might change slightly in future releases :)

Best Regards,
Nicolas
Nicolas Gramlich
Site Admin
 
Posts: 1734
Joined: Mon Jun 07, 2010 6:20 pm
Location: Schriesheim, Germany

Re: Ear Clipping Triangulation Algorithm

Postby K2DaC » Fri Sep 17, 2010 10:38 am

it works great.
Image

now i have to update all Blocks, "draw" new Sprites, change the control & Rotation ... i think i'll start from 0 again :)
K2DaC
 
Posts: 16
Joined: Sat Sep 11, 2010 6:40 am
Location: Berlin, Germany

Re: Ear Clipping Triangulation Algorithm

Postby brewhaha » Sat Sep 18, 2010 12:58 am

Hey guys,
As a warning you might want to check out this article about tetris clones: http://androidandme.com/2010/06/news/google-can-giveth-apps-and-google-can-taketh-apps-away/

Not sure what the current state of this is, but it is perhaps worth looking into.
brewhaha
 
Posts: 60
Joined: Mon Jul 12, 2010 1:06 pm

Next

Return to Updates

Who is online

Users browsing this forum: No registered users and 2 guests