7
\$\begingroup\$

So I'm making an artillery type game, sort of similar to Worms with all the usual stuff like destructible terrain etc... and while I could use per-pixel collision that doesn't give me collision normals or anything like that. Converting it all to a mesh would also mean I could use an existing physics library, which would be better than anything I can make by myself.

I've seen people mention doing this by using Marching Squares to get contours in the bitmap, but I can't find anything which mentions how to turn these into a mesh (Unless it refers to a 3D mesh with contour lines defining different heights, which is NOT what I want). At the moment I can get a basic Marching Squares contour which looks something like this (Where the grid-like lines in the background would be the Marching Squares 'cells'):

Marching Squares result

That needs to be interpolated to get a smoother, more accurate result but that's the general idea. I had a couple ideas for how to turn this into a mesh, but many of them wouldn't work in certain cases, and the one which I thought would work perfectly has turned out to be very slow and I've not even finished it yet! Ideally I'd like whatever I end up using to be fast enough to do every frame for cases such as rapidly-firing weapons, or digging tools.

I'm thinking there must be some kind of existing algorithm/technique for turning something like this into a mesh, but I can't seem to find anything. I've looked at some things like Delaunay Triangulation, but as far as I can tell that won't correctly handle concave shapes like the above example, and also wouldn't account for holes within the terrain.

I'll go through the technique I came up with for comparison and I guess I'll see if anyone has a better idea. First of all interpolate the Marching Squares contour lines, creating vertices from the line ends, and getting vertices where lines cross cell edges (Important). Then, for each cell containing vertices create polygons by using 2 vertices, and a cell corner as the 3rd vertex (Probably the closest corner).

enter image description here

Do this for each cell and I think you should have a mesh which accurately represents the original bitmap (Though there will only be polygons at the edges of the bitmap, and large filled in areas in between will be empty). The only problem with this is that it involves lopping through every pixel once for the initial Marching Squares, then looping through every cell (image height + 1 x image width + 1) at least twice, which ends up being really slow for any decently sized image...

Improve this question
\$\endgroup\$
6
  • 1
    \$\begingroup\$ "that doesn't give me collision normals or anything like that." Says who? You can check the nearby pixels and generate a collision normal just fine. In fact, you can use marching cubes on-demand to do exactly this. No need for a mesh; you just need a normal, right? \$\endgroup\$
    – Nicol Bolas
    May 6, 2012 at 21:42
  • \$\begingroup\$ Oh yeah, I have already done something similar actually, but it's not great. I mean it works fairly well, but definitely not perfectly. Using Marching Squares on a small area around the collision point would probably be a slightly better solution than my previous one, but I can still see problems with it. For example too small a sample area will produce an inaccurate normal because you miss detail, whereas too large an area means you'd probably have to average the angle of the edges you get (which again could be inaccurate). \$\endgroup\$
    – Megadanxzero
    May 6, 2012 at 22:41
  • \$\begingroup\$ And of course that's ignoring the fact that I'd then still have to make my own physics, which probably wouldn't end up being very good, instead of just using an existing robust physics engine. I don't know of any physics engines that let you override the collision detection with your own per-pixel stuff and then just give it a collision normal to react to. Could be that something like that exists though. \$\endgroup\$
    – Megadanxzero
    May 6, 2012 at 22:44
  • \$\begingroup\$ How accurate of a normal do you need? You're making a Scorched Earth/Worms-style game. I think your players will forgive you if the bounce isn't perfect. I mean, do you think that the old DOS Scorched Earth was building highly accurate meshes and so forth? Do you think that even modern Worms games go through a great deal of effort to compute this stuff? \$\endgroup\$
    – Nicol Bolas
    May 6, 2012 at 22:44
  • 1
    \$\begingroup\$ The "physics" part of a physics system (especially in 2D) is the easiest part. It's the "collision" part that's hard. \$\endgroup\$
    – Nicol Bolas
    May 6, 2012 at 22:45

1 Answer 1

Reset to default
2
\$\begingroup\$

I haven't worked with 2D physics engines before, I'm not sure exactly how the collision mesh is supposed to look.

If it's simply a set of 2D triangles, then you should look into triangulation methods. For example, constrained Delauney triangulation.

Delaunay triangulations maximize the minimum angle of all the angles of the triangles in the triangulation; they tend to avoid skinny triangles.

Which is a good thing when it comes to rendering these triangles at least, and may or may not be good for collision detection as well.

A constrained Delauny triangulation incorporates fixed edges, which would be your detected edges. This library may provide what you need

Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ Aha, I hadn't heard of Constrained Delaunay Triangulation, that seems like it could be exactly what I need, I'll definitely have to look into it. Thanks! \$\endgroup\$
    – Megadanxzero
    May 8, 2012 at 10:42

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .