Some trouble with Box2D, recommendations requested

Sage
Posts: 1,199
Joined: 2004.10
Post: #1
Hey everybody,

I'm writing a 2d physics game, with completely destructible environment. It's kind of a 2d voxel system, where the user can 'cut' the world, and with some fanciness (marching cubes + shape optimization + triangulation -> rigid body destructible terrain ) I generate convex decompositions of the dynamically generated shapes and pass those to Box2D to act as rigid bodies.

Basically, it works Cool. But the trouble is, Box2D doesn't like some of the geometry that gets generated, mostly triangles which are long and thin. But Box2D doesn't have any option to 'test' if it will like a triangle, it either likes it, or it calls assert(false).

Which is really rude

Now, I was using Box2D's ConvexDecomposition utility lib for a while, but it skips any triangles Box2D doesn't like, leaving me with unacceptable holes in my geometry. And there's no good way to query what exactly Box2D doesn't like about the bad shape so as to be able to fix it.

I ditched Box2D's ConvexDecomposition functionality for an open-source triangulator which gives very high quality triangulations. However, some of these triangles are thin, and make Box2D barf.

I'm wondering if Chipmunk is more polite about long thin triangles? Or if, since it used double precision maths it can handle them?

Or perhaps there's some smarter way to do this I'm missing?

BTW, I'm in no way married to Box2D.
Quote this message in a reply
Apprentice
Posts: 19
Joined: 2010.03
Post: #2
caveat: I've never used Box2D.

I think you're going to find this problem with any collision/physics system. You should looks for a solution to the near-degenerate triangles.

Near-degenerates are hard to work with as you can travel through them too easily (for collision resolution) and they also render really badly (maximum fragment setup cost to pixels render ratio).

You could try removing the near-degenreat triangles and shrinking neighbours giving room for a new set of triangles to be inserted. You'll face the problem of T joints in your mesh (where edges meet edges rather than only vertices meeting) but this may be a acceptable.

Hope that helps a little
Quote this message in a reply
Moderator
Posts: 452
Joined: 2008.04
Post: #3
Recommendation Chipmunk! Obviously I'm biased though Wink

I suspect Scott will have some specific suggestions regarding how to handle convex geometry.

Howling Moon Software - CrayonBall for Mac and iPhone, Contract Game Dev Work
Quote this message in a reply
Apprentice
Posts: 12
Joined: 2009.08
Post: #4
Are you generating the triangles in a counter clockwise manner?
Quote this message in a reply
Member
Posts: 45
Joined: 2006.07
Post: #5
I've used this in the past for other projects:

http://www.cs.cmu.edu/~quake/triangle.html

It's pretty good at avoiding the long skinny ones.
Quote this message in a reply
Sage
Posts: 1,199
Joined: 2004.10
Post: #6
(Mar 7, 2011 07:59 AM)mattz Wrote:  I've used this in the past for other projects:

http://www.cs.cmu.edu/~quake/triangle.html

It's pretty good at avoiding the long skinny ones.

WOW. That looks absolutely perfect! Last night as I was doing dishes I was thinking that a delaunay triangulation ought to do the job, but then I got a little nervous about actually implementing such a beast.

Thanks so much,
Quote this message in a reply
Member
Posts: 45
Joined: 2006.07
Post: #7
Glad if it helps -- I was using it to generate physics meshes for marble mazes... it gave me output that looks like this (a very small test maze):

[Image: mmaze.png]

Was not super straightforward to figure out how to invoke the dang thing but once I figured it out, it worked ok. As I recall, I wanted blue triangles (board) to be nice and not too sliver-y, and red triangles (walls) didn't matter.
Quote this message in a reply
Sage
Posts: 1,482
Joined: 2002.09
Post: #8
Both Chipmunk and Box2D are going to struggle with small/thin shapes. The problem is that it's too easy for things to get stuck on the wrong side of them even during low speed collisions with other small/thin objects. This is especially bad when you have a shape that gets between the cracks of a decomposed concave shape. They also tend to be very expensive for the broadphase collision detection as they tend to fit very poorly in simplified bounding volumes which can lead to a lot of false positives that need to get filtered. Chipmunk won't prevent you from creating thin polygons, but you might find that they simply don't work acceptably well either.

You should also keep in mind that both libraries have a pretty high per-shape cost in the collision detection broadphase. If possible, it's better to decompose things into convex polygons with as many sides as possible instead of triangles. Box2D's broadphase isn't particularly fast, so this might cause problems sooner rather than later if you try to cram a lot of shapes into the simulation.

Have you considered building the world out of convex polygons to begin with? When slicing them you always end up with with another convex polygon. Though it would almost certainly force your world to have a very geometric feel.

Scott Lembcke - Howling Moon Software
Author of Chipmunk Physics - A fast and simple rigid body physics library in C.
Quote this message in a reply
Sage
Posts: 1,199
Joined: 2004.10
Post: #9
(Mar 7, 2011 10:24 AM)Skorche Wrote:  Both Chipmunk and Box2D are going to struggle with small/thin shapes. The problem is that it's too easy for things to get stuck on the wrong side of them even during low speed collisions with other small/thin objects. This is especially bad when you have a shape that gets between the cracks of a decomposed concave shape. They also tend to be very expensive for the broadphase collision detection as they tend to fit very poorly in simplified bounding volumes which can lead to a lot of false positives that need to get filtered. Chipmunk won't prevent you from creating thin polygons, but you might find that they simply don't work acceptably well either.

I certainly understand this, having been using ODE and Bullet for years now for 3D physics. That being said, my primary problem with Box2D was that it simply calls assert(false) whenever it's unhappy. I'd rather my game simply miss a collision now and then, than to mysteriously and randomly crash. And while I'm a pretty decent programmer, I don't consider myself qualified to make changes to the guts of somebody else's physics code... I've looked at the places where Box2D asserts false, and those basically look like trouble cases where there's no good option but to assert false. Sort of like painting oneself into a corner.

I'm a smart enough guy to know that anybody writing a physics engine is smarter than me Smile

Anyway, I'm scoping out your chipmunk API; it reminds me of ODE, and that's awesome. I love ODE's API.

Quote:Have you considered building the world out of convex polygons to begin with? When slicing them you always end up with with another convex polygon. Though it would almost certainly force your world to have a very geometric feel.

I have, but the trouble with this approach is that I'll have to write a level editor... whereas my current approach lets me design my levels in photoshop. My current voxel-based system has a number of peculiar advantages (which are very useful to my game dynamics), but I have seriously considered using glu tesselate's CSG functionality to do my cutting.
Quote this message in a reply
Sage
Posts: 1,482
Joined: 2002.09
Post: #10
We've taken a similar approach before: http://www.youtube.com/watch?v=LuOrC95K26E

The terrain isn't built out of solid polygons, only outlined out of segment shapes. If you wanted to allow chunks of terrain to become detached, you could take a slightly simplified route where detached concave shapes simply crumble into a number of simple convex ones. Throw up some dust particles to hide the shape change if they don't match exactly perhaps?

I've wanted to use my marching squares code to make a game with destructible terrain for a few years. Now I want to do detachable chunks of terrain too. Heh. I really need to enter some small contests so that I actually make something instead of just scope creeping projects that I'll probably never even start. Rolleyes

Scott Lembcke - Howling Moon Software
Author of Chipmunk Physics - A fast and simple rigid body physics library in C.
Quote this message in a reply
Sage
Posts: 1,199
Joined: 2004.10
Post: #11
I wanted to post a quick followup -- I ported my embryonic game from Box2D to Chipmunk, and used a constrained delaunay triangulation ( from poly2tri ), and it works beautifully. Per the discussion, I'm using line segments for static geometry, and switching to triangles for the cut-off pieces.

Anyway, it's working wonderfully. Thanks!
Quote this message in a reply
Sage
Posts: 1,482
Joined: 2002.09
Post: #12
Oh, protip: Give the line segments at least a small radius. Chipmunk (and Box2D for the same reason) allow objects to overlap slightly in order to keep collisions from appearing and disappearing every other frame and ruining the collision cache. In Chipmunk, this is controlled by the cp_collision_slop global, and defaults to 0.1 units. This means that objects can catch on the "cracks" between individual collision shapes occasionally causing it to jump or get caught. The radius for line segments was originally made as a solution to the problem. Giving them a radius of a pixel or two generally isn't visible to the player, but mostly fixes the crack problem as the line caps are nicely rounded off.

Glad Chipmunk is working well for you. Also video? Grin

Scott Lembcke - Howling Moon Software
Author of Chipmunk Physics - A fast and simple rigid body physics library in C.
Quote this message in a reply
Sage
Posts: 1,199
Joined: 2004.10
Post: #13
Actually, I'd already set a small radius. Will have to experiment to see what works best. And sadly, no video, since it's pretty boring.

But, here's a square that's been sliced several times.

[Image: Screen%20shot%202011-03-14%20at%2010.16.49%20PM.png]
Quote this message in a reply
Post Reply 

Possibly Related Threads...
Thread: Author Replies: Views: Last Post
  Box2D added to Cocos2D errors MDev 4 4,255 Dec 18, 2012 01:25 PM
Last Post: bgulanowski