Triangulation of Concave Polgygons in C/C++

Official forum for the Chipmunk2D Physics Library.
Post Reply
sketch
Posts: 3
Joined: Mon Aug 12, 2013 9:03 am
Contact:

Triangulation of Concave Polgygons in C/C++

Post by sketch »

Hi,

I would first like to say good job with Chipmunk! It's super easy to use, supports all interesting joint types, and is quite fast. I have tried both Box2d and PhysX but they pale in comparison to Chipmunk for what I need in 2D. It's a nice engine!

Right now I'm at a point where I need to triangulate a concave polygon with no holes. The polygon is constructed from an ordered set of points along the hull (in CW or CCW order).

Chipmunk Pro has Autogeometry features, and I managed to find examples of its use in Objective-C (http://chipmunk-physics.net/forum/viewtopic.php?t=813), but I cannot seem to find the documentation on how to use this feature directly from C/C++.

Can anyone point me in the right direction where I can read more on this?

Another solution I found was CGAL (http://www.cgal.org) but the library is huge and I only need one small feature from it so I would like to avoid using it.

Thank you,
Rados
LegoCylon
Posts: 29
Joined: Wed May 09, 2012 12:06 am
Contact:

Re: Triangulation of Concave Polgygons in C/C++

Post by LegoCylon »

It sounds like you may already have the set of vertices. If so you can just create a body with segment shapes between each vertex with a little bit of beveling and enable segment-to-segment collision.

If you do not have the points, I use OpenCV to do edge detection in my level editor. It is also a large library but I only include OpenCV_core and OpenCV_imgproc. cv::findContours returns a set of contours with vertices. You can think of each contour as a separate polygon. Once I have the vertices I follow the same procedure as above using segment shapes. It's pretty quick to update but I have not tried using it in real time in my game so I don't know how well it performs in that context on a mobile device.
sketch
Posts: 3
Joined: Mon Aug 12, 2013 9:03 am
Contact:

Re: Triangulation of Concave Polgygons in C/C++

Post by sketch »

Thank you for the reply! I'm sort of trying to see if Chuimunk has some triangulation functions exposed. I should have been a bit more clear!

I have objects which are collections of bodies, shapes, and constraints, and through some wizardry I return the object's concave hull. Now I would like to triangulate the computed hull and feed it to OpenGL.

I am looking for some helper functions which will help me with the triangulation. I think Chipmunk has such functions, but I cannot find the documentation about it. Does Chipmunk provide this at all?

Cheers,
R
User avatar
slembcke
Site Admin
Posts: 4166
Joined: Tue Aug 14, 2007 7:13 pm
Contact:

Re: Triangulation of Concave Polgygons in C/C++

Post by slembcke »

So triangulation works, but is non-ideal for a couple reasons since triangulation is usually rendering oriented. It tends to generate a lot of shapes and often very pointy shapes. Joining triangles together into convex hulls helps, but it's a step that's often not taken. Since a lot of existing code is graphics oriented, triangles are the preferred output format. That's something to keep in mind.

What Chipmunk Pro provides is ACD (approximate convex decomposition). It has two main benefits. It takes a threshold, so you can choose between an exact (and possibly wasteful) decomposition and a simplified one. The second benefit is that it tends to avoid making skinny or sharp polygons because of the way it splits things up.
Image

The Chipmunk Pro decomposition function is pretty straightforward. You give it a polyline and a minimum concavity threshold and it returns a set of convex polygons. This unit test should make things clearer:

Code: Select all

	{
		cpVect verts[] = {{0,0}, {1,2}, {2,0}, {1,1}};
		cpVect expected1[] = {{0,0}, {1,2}, {1,1}};
		cpVect expected2[] = {{1,2}, {2,0}, {1,1}};
		
		cpPolyline line = MakeLoopedPolyline(4, verts);
		cpPolylineSet *set = cpPolylineConvexDecomposition_BETA(line, 0.0);
		
		GHAssertEquals(set->count, 2, nil);
		AssertPolyline(self, set->lines[0], 3, expected1);
		AssertPolyline(self, set->lines[1], 3, expected2);
	}
The function is tagged as "beta" because it only works with simple (non-self intersecting) polygons as input. Just detecting a non-simple polygon is as computationally expensive as decomposing a simple one. I haven't decided what the best way to handle that in a realtime setting is. Given good input it will give you good output though, and it will do it quite quickly. ;)
Can't sleep... Chipmunks will eat me...
Check out our latest projects! -> http://howlingmoonsoftware.com/wordpress/
sketch
Posts: 3
Joined: Mon Aug 12, 2013 9:03 am
Contact:

Re: Triangulation of Concave Polgygons in C/C++

Post by sketch »

Thank you for your quick reply! That is precisely what I'm looking for :)

Is the functionality not available in the Pro Trial? I downloaded the pro trial to test it, But I cannot locate the Polyline classes.

EDIT:

Ah I did not see that the Pro download is for the iOS Pro trial. But it is great that Chipmunk has the ACD feature. It is definitely a handy one. It will save me quite a bit of trouble down the road.

Thank you again for the information and your fast reply.

Cheers,
R
Post Reply

Who is online

Users browsing this forum: Heise IT-Markt [Crawler] and 9 guests