Decompose into triangles

Posts regarding potential bugs, enhancement requests, and general feedback on use of dyn4j
zoom
Posts: 143
Joined: Sun Mar 17, 2013 3:57 pm
Location: Stockholm, Sweden
Contact:

Decompose into triangles

Postby zoom » Fri Dec 27, 2013 4:10 pm

I need to triangulate a non-convex polygon (without holes) so I can render it in OpenGL. I was looking at the decomposer implementations and saw that they have an intermediate step of triangles that are then simplified to Convexes. Would it be possible to have another interface, say DecomposeToTriangles, that for example SweepLine could implement that would return the list of triangles?
I'm hoping that the triangles are in CC-winding.

zoom
Posts: 143
Joined: Sun Mar 17, 2013 3:57 pm
Location: Stockholm, Sweden
Contact:

Re: Decompose into triangles

Postby zoom » Sun Dec 29, 2013 10:00 am

What I'm doing now is taking the Convexes, cast them to polygons, create a GL_TRIANGLE_FAN out of each convex and render them. Even though it is a bit roundabout; going from triangles to convexes to triangle fans I can say that for my use case (between 1-150 convexes) the bottleneck is still rendering. So even though sweep line shows up in the profiler it is pretty darn quick :-)

William
Site Admin
Posts: 351
Joined: Sat Feb 06, 2010 10:23 pm

Re: Decompose into triangles

Postby William » Mon Dec 30, 2013 8:13 am

Yeah, both EarClipping and SweepLine triangulate the simple polygon first, then a post processing step called hertelMehlhorn merges triangles into convexes (to reduce the number of convexes). These two could easily support a triangulate() method, but Bayazit would not. I could add another interface called Trangulator and have EarClipping and SweepLine implement it if you think that would be of use. Just let me know.

William

zoom
Posts: 143
Joined: Sun Mar 17, 2013 3:57 pm
Location: Stockholm, Sweden
Contact:

Re: Decompose into triangles

Postby zoom » Mon Dec 30, 2013 9:34 am

Yeah a triangle-soup would be perfect for rendering. Even more so if the triangles have the same (counter clockwise) winding. Or a method to test the winding (idk maybe just a cross product).
Too bad neither SVN nor google code support pull requests, I can make a patch file if it helps but I think you already know what I want :-)

zoom
Posts: 143
Joined: Sun Mar 17, 2013 3:57 pm
Location: Stockholm, Sweden
Contact:

Re: Decompose into triangles

Postby zoom » Sat Jan 11, 2014 5:03 am

I just gave the Triangulator a first spin, it is just perfect! It made my code so much simpler :-)

By chance it also happened to shave off enough CPU cycles in my test case that now I have to wait for OpenGL instead of waiting for the decomposer. But for the record, the decomposer was really fast already, this was just a funny coincidence.


Return to “Bugs, Enhancements, Feedback”

Who is online

Users browsing this forum: No registered users and 1 guest