next »

[Glaiel-Gamer]

What's the best way to collide a rigid body with a bitmap landscape?

The rigid body is a convex polygon with points stored in clockwise order, I got them colliding with each other pretty well (there's one issue with resolving when they are spinning fast but I'm working on it), but I need them to collide with a bitmap landscape now.


- I can't parse the bitmap into a set of convex polygons because it is constantly changing and doing that every frame would be processor-intensive

- I could parse the original bitmap into a set of convex polygons, but then for collision I'd have to test with the AND combination of that and a set of circles and I can't feasibly see how to test for AND combinations of polygons

- I could iterate points along the edge of each polygon and test each point with the bitmap, which would get me a set of points inside the bitmap and from there I could find a way to calculate the collision normal and then iterate it out of the bitmap... but that's a lot of work too.


Any suggestions?

[J.G. Martins]

This is interesting to me too

Does the background bitmap change in predictable ways? As in, only when something explodes and the terrain is deformed? If this is the case, and changes won't be occuring every single frame, it might be feasible to have a start set of convex polygons to which you can test collisions against. Every time you deform terrain, it should involve a reduced number of polygons and you should just create a new subset of convex polygons that conform to the new terrain.


Regarding colliding collisions between segments and bitmaps: your bitmap probably has direct access to any pixel, so maybe something along this approach:
1) Figure list of counter clockwise points on the polygon such that consecutive points are never more than X "pixels" apart
2) Figure out where those points are on the bitmap, and see if any area around that point has a collision pixel
3) In case there is, go in deeper. Maybe deduce some lines and points from the bitmap around the possible collision area, and collide with that.



I'd still go for the first approach if the terrain isn't continually changing, or if the changes are really small and affect small areas of the total map.

These are just thoughts from the top of my head, as I've never implemented any of this and don't know what common practise is, if there is a common practise for this collision type

[Glaiel-Gamer]

No it's not deformable terrain, it's something different but I really don't want to give away the mechanic right now (i'll be releasing the flash version this week though, these rigid stuff is for the next one).

And yes, it changes every frame.

[Michelle Disraeli]

Parsing the bitmap into a convex polygon would help. Line-line collision testing is almost certainly going to be less intensive than bitmap scanning. The important thing here is simply to use this to reduce the workload - you simply need the generated polygon(s) to be guaranteed to fully enclose all collidable pixels. Depending upon how you are running the simulation, there are a number of techniques which could be used to do this (for example, a simple collision grid).

After this, I don't think there is any escaping iterating through the underlying pixels themselves. If you don't want to make an exact polygon representation, I can't really see any alternative. However, there are some tricks you can use for speed.

Firstly, ensure that all the colliding areas are continuous. If you must have separated regions, make these further apart than the size of the colliding bodies, such that you need only consider the pixels along the edges when checking the bitmap for collision. Similarly, objects should move at a slow enough speed such that they don't pass right through a section of the collidable bitmap before the next collision check.

The bitmap itself should ideally be literally a bitmap, allowing simple sequential bitwise operations to check for collision.

Your main issue when checking the bitmap is going to be memory access. When checking along a scanline, this is not an issue, but rather the problems occur when you move vertically. Try to keep the entirety of an area that will all be checked at once in a single page of memory (approximately 4K). Either use smaller maps, or a tile based system. If you use a tile based solution, you should ideally only require a worst-case check against four tiles - the tiles should be bigger than the colliding object. When using a tile system, you can mark entire tiles as either "passable", "blocked" or "checkme". A polygonal scheme on top of this would allow further definition to the checkme, avoiding a potentially costly scan through the bitmap itself. Alternatives for this include a number of predefined collision patterns for tiles, rather than a terrain collision polygon.

[J.G. Martins]

Love the tile solution. Precomputing FTW

Unfortunately, terrain changes every frame. Do you expect a lot of collisions? This should probably define whether it will be worth computing the type of tile (collide, nocollide, checkme, as Michelle pointed out) every single frame or whether you're better off just checking small parts here and there.

Also, if anyone wants to know why it is better to scan horizontally than vertically, feel free to ask. It can make a huge difference in some cases

[Alex May]

You could rasterise the convex shape (this would work for concaves too) and then & it with the landscape bitmap.

Ask Data on the Cortex Command forum, or PM him on here to see how he did it in CC.

[Glaiel-Gamer]

You could rasterise the convex shape (this would work for concaves too) and then & it with the landscape bitmap.

Ask Data on the Cortex Command forum, or PM him on here to see how he did it in CC.

I've done that one before
http://lab.glaielgames.com/superflag.htm

But that doesn't help in finding the collision normal or the collision point (unless its a circle)

[bateleur]

But that doesn't help in finding the collision normal or the collision point (unless its a circle)

Finding the point isn't too bad. What you have is a set of potential collision points. If your interations are small enough (and you should always use small iterations for physics work) these will be very close together, so you can find a single motion vector for the moving body near those points which to a good degree of approximation applies to all the points in the set. Pick the one furthest back along that vector.

Collision normal is a huge can of worms. I'd recommend cheating, since I've never found a decent way to do this well. One possible cheat is to keep a separate bitmap with nominal normals stored as pixels and then update it (approximately) whenever you deform the terrain.

[Alex May]

Or don't use rigid bodies and instead simulate them using springs...

[Glaiel-Gamer]

Collision normal is a huge can of worms. I'd recommend cheating, since I've never found a decent way to do this well. One possible cheat is to keep a separate bitmap with nominal normals stored as pixels and then update it (approximately) whenever you deform the terrain.

Ya the point on the poly seems easier to find than how far in the bitmap it is.

Actually one way I found to estimate a collision normal is to test points on the perimeter of the circle then average the colliding ones together and that the vector from that point to the center of the circle... I can't really easily find out how far into the shape it is though.

And approximating it with springs, I still have the same collision detection problem. I might actually go the approximate it with springs route, cause true rigids seem pretty unstable so far (they mess up a little when they are rotating fast)

[Alex May]

But you've already solved the collision detection problem as you have demonstrated yourself (and anyway if you're using the spring ends you don't even have to rasterise the object, just do a lookup on the bitmap for the spring end locations). You keep the ends of the springs (and the edges too if you like) outside the collision and you're good to go.

[Glaiel-Gamer]

But you've already solved the collision detection problem as you have demonstrated yourself (and anyway if you're using the spring ends you don't even have to rasterise the object, just do a lookup on the bitmap for the spring end locations). You keep the ends of the springs (and the edges too if you like) outside the collision and you're good to go.

Spring ends wouldn't give me a colliding point if the bitmap is colliding a side on a vertex.

Also, detection isn't the problem, it's resolution and finding the point of the collision (since once I have the point I can estimate a normal), and I have no idea how to estimate the point.

I guess I could try projecting onto the velocity vector, but then I'd end up never being able to find the collision point if the point is on the bitmap and not on the shape (on an edge of a shape)

[Alex May]

I don't think you need the normal if you're using springs. It's a bunch of points connected by springs, right? So you move the object and one of the points can't move. You still move all the other points, but then you iteratively restore all the springs afterwards, they try to get back to their desired lengths.

[Glaiel-Gamer]

I don't think you need the normal if you're using springs. It's a bunch of points connected by springs, right? So you move the object and one of the points can't move. You still move all the other points, but then you iteratively restore all the springs afterwards, they try to get back to their desired lengths.

You need to know the normal to know which direction to move it, and in what direction to change the velocity of the particle

Again doesn't really help if its hitting an edge not a point, cause then you have to go and apply forces somewhere anyway.

[Alex May]

You need to know the normal to know which direction to move it, and in what direction to change the velocity of the particle

Again doesn't really help if its hitting an edge not a point, cause then you have to go and apply forces somewhere anyway.

Yeah, I guess you'd need the normal to change the particle velocity. In that case you could do a simple heuristic on the local bitmap to find an approximate angle. Take a 5x5 area and measure the slope like that.

Part of me still believes you wouldn't necessarily need the normal as the springs might cause the necessary reaction in the colliding particle.

[bateleur]

Part of me still believes you wouldn't necessarily need the normal as the springs might cause the necessary reaction in the colliding particle.

The typical evil case for normals is when two parallel rectangles intersect at their corners. The correct collision reaction varies enormously depending on which face actually collided, which you cannot in general work out without inspecting velocities, rotations and timings for both.

With a mesh of springs it would be easy to get the right answer for the initial collision, but then secondary collisions (by which I mean one frame later) could be quite horribly wrong. The reason being because you'd need such fine-grained time slices and so many springs to get the right answer that it would be impractical.

Still, springs could be a very good approximation for certain kinds of objects. In particular, if you have low coefficients of restitution anyway and/or reasonably low movements speeds the resulting collisions might seem quite natural. (The key question being how fast the compression wave from a collision propagates through the mesh - too slowly and it will look like Gish!)

Nightmare case for springs would probably be a long, thing beam landing across the point of a pyramid!

[BorisTheBrave]

No ones mentioned quadtrees yet! This is a great way of storing bitmaps so you can make localized changes without recalculating anything.
Here's a picture of what I mean:
http://www.box2d.org/forum/viewtopic.php?f=4&t=1829
In this case, he's chosen to stop the tesallation at a certain point and then produced triangles to fill in the last bit, presumably based on the 10x10 pixels in each small square. But you are free to deal with that last bit in other ways too, such as discussed above. The important thing is quadtree part, which allows you to efficiently modify parts of the bitmap easily, and also fill in large areas very quickly. And query vs polygons efficiently. And do flood fills. Etc.

[J.G. Martins]

Thank you for that, Boris