[Solved] Pixel-based collision detection in D3D?
Author
Alright then, let me kindly set the stage up for ye:
I'm current writing a 2D game of sorts which requires some rather accurate collision detection. I mean, we can't have grenades bouncing off incorrectly or players walking face-first into invisible walls, now can we? [smile]
Okay, okay, I'll skip the vagueities. The problem of getting accurate collision detection has been plagueing me since the game's development began. I have game objects that are rendered as simple 2D quads that require pixel-perfect collision detection. I had this going just fine at first; it's just a matter of locking the surface, getting access to that glorious pixel data, and checking for transparent/non pixels wherever the player is trying to move.
Then I went and added game object rotation. This means that all of the objects -- crates, toilets, couches, and the like -- can no longer use this method of collision detection, since the given pixel data of the bitmap is only relevant when Rotation = 0.
The only solution I can think of is approximating objects using polygonal hulls that represent each object. These easily lend themselves to rotation and fairly simplistic collision, but there's the burden of needing to (a) implement the darn thing, and (b) integrating somesort of hull editor into my current editors and manually constructing the polygonal-hulls for every one of my gosh-darned 100+ objects. [sad]
I'd be very much appreciative of any suggestions that could be made on the topic. Thanks in advance! [smile]
[Edited by - HopeDagger on May 23, 2006 9:35:45 AM]
Would it not be reasonably easy to generate polygonal hulls automatically from the sprite textures, either off-line or at load time time.
Just analyse the pixels of the texture and calculate the hull (either based on their alpha or the pixel color). The hulls themselves could either a arbritary polygonal ones or just a regular box (Axis aligned or not) or a ellipse.
Just analyse the pixels of the texture and calculate the hull (either based on their alpha or the pixel color). The hulls themselves could either a arbritary polygonal ones or just a regular box (Axis aligned or not) or a ellipse.
One option could be to do a z-buffer like idea. Have a surface that is the size of the screen and render objects' alpha value on to that (you wouldn't want to render the floors onto it but, you would the walls.) Then, you would just check the alpha value for a specific area.
HTH!
HTH!
Hulls are absolutely the way to go. They handle rotation properly as you say, but they also increase performance - you can use multiple resolution versions of the hull and test on the lowres ones first. Another benefit is the possibility of checking between timesteps (moving line-line collision test).
I haven't implemented the autogeneration code myself yet, but one that creates the high-res polygon should be fairly easy.
What's trickier is a resolution reducer algo that is guaranteed to not cut into the area defined by the higher-res polygon, so if you find any resources for that, please post it!
I haven't implemented the autogeneration code myself yet, but one that creates the high-res polygon should be fairly easy.
What's trickier is a resolution reducer algo that is guaranteed to not cut into the area defined by the higher-res polygon, so if you find any resources for that, please post it!
Quote:Original post by HopeDagger
The only solution I can think of is approximating objects using polygonal hulls that represent each object. These easily lend themselves to rotation and fairly simplistic collision, but there's the burden of needing to (a) implement the darn thing, and (b) integrating somesort of hull editor into my current editors and manually constructing the polygonal-hulls for every one of my gosh-darned 100+ objects. [sad][smile]
I think by far the easier way is to employ a z-buffer, and check drawn pixels, that would be O(m+n) and if you need speed scale them down before. You also can do it employing hardware accelerated z-buffer and occlusion queries if using Dx9.
The z-buffer solution seems like a nice trick, but one drawback is that you have to render *before* you know if they hit or not; another is you won't catch hits inbetween frames (when movement is larger than maximum overlap).
Using polygons, you can also benefit from 3D physics libraries and get lots of funtionality for free.
Using polygons, you can also benefit from 3D physics libraries and get lots of funtionality for free.
Author
Thanks for the reples, everyone. Greatly appreciated. Ratings have been boosted as appropriate. (Sans P16, who is already maxxed :P)
I've decided that I'm going to take a go at the Z-Buffer idea of rendering the collision-image to a surface and checking for a collision through that. Naturally I have no idea of how to do this, but I'll start up a new thread rather than taking this one out of scope.
Thanks again!
I've decided that I'm going to take a go at the Z-Buffer idea of rendering the collision-image to a surface and checking for a collision through that. Naturally I have no idea of how to do this, but I'll start up a new thread rather than taking this one out of scope.
Thanks again!
Maybe you can do a mix of both methods. Having a precomputed convex hull from the non-transparent sprite pixels (easy, treat them as a 2d point set), and in case of hull collision, then perform a per-pixel z-buffer based check. You can manage them as geometry and have pixel precision collision detection.
Ruben.
Ruben.
Hi,
If it's just a matter of rotations, can't you use an inverse rotation to use your previous method ?
Imagine a sprite which is rotated of X. You want to check if a pixel (on screen) is transparent or not. You know that the sprite has a rotation of X, so you simply rotate the point you want to check by -X (around the sprite's rotation center) and you've got the coordinates of your points in the sprites. You can then lock it, check the transparency, and that's done.
You just have a few maths operations to add to your current method to handle rotations.
(don't know if i'm being clear, and maybe I misunderstood the question ^^)
If it's just a matter of rotations, can't you use an inverse rotation to use your previous method ?
Imagine a sprite which is rotated of X. You want to check if a pixel (on screen) is transparent or not. You know that the sprite has a rotation of X, so you simply rotate the point you want to check by -X (around the sprite's rotation center) and you've got the coordinates of your points in the sprites. You can then lock it, check the transparency, and that's done.
You just have a few maths operations to add to your current method to handle rotations.
(don't know if i'm being clear, and maybe I misunderstood the question ^^)
Author
@Paic: Brilliant idea -- I feel guilty now for having not thought of such a thing. Doh. [smile]
I just implemented this, and it works perfectly; just like my old code, but now supporting 'dem pesky rotations. Huzzah.
Thanks again, Paic!
I just implemented this, and it works perfectly; just like my old code, but now supporting 'dem pesky rotations. Huzzah.
Thanks again, Paic!
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
