Sign in to follow this  
HopeDagger

[Solved] Pixel-based collision detection in D3D?

Recommended Posts

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]

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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!

Share this post


Link to post
Share on other sites
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!

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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!

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
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.

Share this post


Link to post
Share on other sites
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 ^^)

Share this post


Link to post
Share on other sites
@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!

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this