Ear Clipping Triangulation Algorithm

[Nicolas Gramlich]

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

Read more soon...

Best Regards,
Nicolas

[ichi]

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!

[damucz]

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

[Nicolas Gramlich]

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:

Stacked Tetris Blocks.

tetristower.png (34.12 KiB) Viewed 3550 times

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

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

Best Regards,
Nicolas

[K2DaC]

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



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

[blandonfrank]

Great news!
looking forward to testing the sample.

[andcoder]

Hi there, please update! Any sample available yet?

[Nicolas Gramlich]

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 ]

Syntax: [ Download ] [ Show ]

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.032 seconds, using GeSHi 1.0.8.4

Hope this helps

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

Best Regards,
Nicolas

[K2DaC]

it works great.


now i have to update all Blocks, "draw" new Sprites, change the control & Rotation ... i think i'll start from 0 again

[brewhaha]

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.