• Advertisement
Sign in to follow this  

Pixel-collision-detection (2d-objects) and using d3dxsprite-rotation

This topic is 4850 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I'm working on a 2d arcade game using D3D (vc++, DirectX9, Summer2004-SDK) and now I'm at a point where I need to improve my bounding-box collision detection to a pixel-perfect collision detection. I've already read about creating bitmasks of sprites and comparing them, but I'm afraid it won't work with the way how I handle the sprites, especially when it comes to rotation or scaling. I'm using D3DXSprites and there's a way to let d3d rotate it, but as D3D handles it, I have no chance to read the pixels somewhere before they get blitted on the buffer. Well, I think there's none, maybe there's one. My idea is, in case a bounding-box collision matches (I will expand the bounding box to compensate the rotation) I will "blit" the first sprite including roation/scaling to another buffer(1bit color-resolution) and create a bitmask right out of it, the same with the second sprite, and then comparing the bits to each other. /* I also thought about rotating all the objects before the game starts, but there could be alot of huge objects and I don't want to waste memory on 360degree rotation bitmasks for like 100+ sprites. */ Is my idea a way to go or am I lurking in the wrong direction and there's a better way? If it's they way to go, my next problem is how to achieve this goal. How do I set up another gfx-buffer for that? I think, using "CreateDevice" for another buffer won't work that way. Then, if I have a buffer, what about the sprite textures, would I have to create another Texture(which means every object has to be created twice) with a pointer to another gfx-buffer? To say the least, I'm lost on this topic :) Any ideas? Michael

Share this post


Link to post
Share on other sites
Advertisement
It sounds like your digging a hole for yourself. Is it really necessary to test against pixels, particularly for rotated sprites? In 99 percent of all cases you can get away with bounding boxes. The other 1 percent you can use circles, ellipses, or polygons. You almost never need to collide pixels, particularly on moving sprites. What is the basis of your assumption, if I may ask?

Share this post


Link to post
Share on other sites
Quote:
Original post by Tom
It sounds like your digging a hole for yourself. Is it really necessary to test against pixels, particularly for rotated sprites? In 99 percent of all cases you can get away with bounding boxes. The other 1 percent you can use circles, ellipses, or polygons. You almost never need to collide pixels, particularly on moving sprites. What is the basis of your assumption, if I may ask?


For instance: One sprite is huge (something like a rotating shield) where parts of it can be "bombed" out by enemies or the player which leaves random shaped holes somewhere(can be big).

Share this post


Link to post
Share on other sites
Quote:
Original post by MFox
For instance: One sprite is huge (something like a rotating shield) where parts of it can be "bombed" out by enemies or the player which leaves random shaped holes somewhere(can be big).


Rather than 1 large bounding box, can you not make the large sprite a number of boxes? One box for each sub-component?

Pixel-perfect collision with rotation and scaling is a huge pain in the ass so you should avoid it unless you're really sure you need it.

Share this post


Link to post
Share on other sites
Quote:
Original post by DrunkenHyena
Rather than 1 large bounding box, can you not make the large sprite a number of boxes? One box for each sub-component?

Pixel-perfect collision with rotation and scaling is a huge pain in the ass so you should avoid it unless you're really sure you need it.


Hm, this could be another way to try, but there's also another shield where the holes could be small and long, and the rocket could go through. This would have to be really small objects then if I split the huge object up But I could split it up anyway to a number of objects to lower the collision-calculating time. Thanks for that thought :)


Actually I'd still like to know how to technically approach the pixel-perfect-collision the way I asked in my initial post. It would be cool if anyone could help me out with this.

Share this post


Link to post
Share on other sites
Other than the bitmasking approach, about the only thing I could suggest is actually invert the process of using bounding geometry.

If your game is anything like Worms, where the player can blow out circular holes in the environment, try doing this:

1) When an explosion occurs (Part of the terrain is cut out), create a bounding sphere (Sorry, circle) that matches the size of the part of the terrain that was cut out.

2) When the bounding-box test passes, test your sprite against all of the bounding circles applied to that object.

3) If your sprite is outside all of the circles (No circle bounding test passes), then you sprite is colliding with the terrain.

It's basically reversing the role of bounding geometry by only applying an action if all of the tests fail. Basically you're just setting the 'empty' areas that you know it's safe to pass through.

Of course you'll have to rotate the points from which your circles originate when you rotate your mesh, but you should be able to find some info about that on the 'net somewhere, or use some of the D3DXMatrix functions. In the end you'll probably find this method will be a lot faster than constantly doing pixel tests.

Also, just in case, if your environment destruction is more complex than just circles being cut out, you could use a simplified BSP instead of a distance check, although that's substantially more complex.

Share this post


Link to post
Share on other sites
Quote:
Original post by MFox
Hm, this could be another way to try, but there's also another shield where the holes could be small and long, and the rocket could go through. This would have to be really small objects then if I split the huge object up But I could split it up anyway to a number of objects to lower the collision-calculating time. Thanks for that thought :)

I'd probably put a bounding box around the entire sprite. This box can be used to quickly reject collisions that are far away. Then if a collision is detected with the box you can check the sub-components. You could go as far as a Quadtree, but that would probably be overkill.

Quote:

Actually I'd still like to know how to technically approach the pixel-perfect-collision the way I asked in my initial post. It would be cool if anyone could help me out with this.


First you would probably want to use bounding circles. Since circles aren't affected by rotation (and scaling a circle is trivial) you can still do you high-level collision very quickly.

Then if the bounding circles do detect a collision, you do the pixel-perfect check. To do that you essentially do something like:

For each pixel in object A, apply scaling/rotation/etc to find it's position in world/screen space. Then back-transform that point using object B's rotation/scaling. That point is now easily compared against object B's position.

This is basically the same problem as picking objects with a mouse, but instead of a single point (mouse click) you need to test every single pixel of Object A against Object B (obviously quitting early if a collision is detected).

Share this post


Link to post
Share on other sites
Thanks guys for your thoughts.

The idea about bounding boxes didn't come into my mind first, it's a good idea for handling collision checks. I will implement that.

Now coming back to the pixelcollision-thing, Let's say I have to do it the way I initially wanted, doesn't matter how slow it is(I might need this also for other tasks besides collision-checking, that's why I'm so interested in how to approach it:) )

There I have the following issue:

I rotate or scale the Sprite, using D3DXMatrixTransformation2D/SetTransform. Then the sprite is "blitted" on the backbuffer.

How to create out of this the bitmask? I don't think I have access to the scaled/rotated object before it's on the backbuffer.

Do I setup another D3D-Device(in case it's working that easy). But then I would have to generate all the Textures again for that device, no?

Or are there other ways to access this?

Share this post


Link to post
Share on other sites
One approach that you could try, would be to keep track of all of the border pixels of your sprites. Then, you only have to check each of the border pixels on each sprite to see if any of them overlap in position. Naturally, this only works if things move either at most 1 pixel per collision detection frame or if you break up the movement into 1 pixel chunks and test each one. (which usually isn't too slow if things aren't flying around at really fast speeds)
You can speed this up by classifying the pixels into say top, right, left, bottom pixels (or combinations thereof). Then an object moving up would only have to check its top pixels versus an object moving down (or remaining stationary). You can write a simple program to classify the pixels for you, eg, any pixel that isn't transparent that has all transparent pixels above it would be a top pixel. Similarly, all pixels that have only transparent pixels to the left would be a left pixel. A pixel would have to be able to be classified as both a left and top pixel if its a corner.
Taking this even further, you might notice (depending on the freedom of movement) that certain objects always collide with certain pixels. To see what I mean, take 2 of your sprites and place them into something like paint. Then drag one of the sprites towards the other, and you'll notice that only certain pixels will ever cause a collision first. You could still write a program to do this for you, but you quickly lose flexibility with this method.
To handle rotating these sprites, you could then manually apply the rotation to your border pixel arrays (either via trig or matrix multiplication).
Naturally, you'd still use your standard bounding box/spheres (depending on the shape of the object) to speed things up at a high level. Splitting up large sprites into many smaller ones is also recommended, simplifies the collision detection, sometimes improves rendering speed, can improve memory utilization by not storing as many transparent pixels for large odd-shaped objects (imagine a giant U-shaped spaceship or something), and you can do nifty things like blowing up large objects into their component sprites sending them spinning across the screen.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement