Pixel Perfect Collision Detection and locking bitmaps

Pixel Perfect Collision Detection and locking bitmaps

Edgar Reynaldo

Major Reynaldo

May 2007

Hi peeps.

I'm working on my collision detection in my game Skyline, and it's currently taking 50ms per collision check in fullscreen. I have to read from two bitmaps, one is a collision buffer for the lasers, and the other is a collision buffer for the city. Locked in native format and READ_ONLY is still too slow for me.

If allegro is preserving textures, and there is a memory copy lurking out there somewhere, can't I just read from that? It would be blazing fast. Because I can't afford to download 1920x1080x2x60 pixels off the gpu every second.

I can use an unordered_set for the collision buffer for the city, and I can use distance based hit detection for the lasers, but I need a way to draw into the collision buffer for the city to 'erase' the city where it has been destroyed.

What are my options?

Advice?

Eagle and Allegro 5 binaries | Older Allegro 4 and 5 binaries | Allegro 5 compile guide
King Piccolo will make it so Then I could just flip it with some sweet, sweet matrix math. In either case, I’ll ride this wagon until the wheels fall off. Thanks to those that keep it running

Audric

Member #907

January 2001

I'm not 100% sure, but a shader may be a way to get the collision information without having to move all the data to RAM to examine it.

Or use a 1bpp mask that stays in RAM, that you keep up to date in parallel with the bitmap. It's only 253Kb for a full screen. Downside is that there is no user-friendly API for "drawing a disc" in an array of bits.

relpatseht

Member #5,034

September 2004

You want to use GPU occlusion queries, probably.

Be cautious though. You can't just fire off the queries then have the CPU wait for them to return. That would take a long time. You need to do other things while the GPU is working, then pick up the results when available.

Edgar Reynaldo

Major Reynaldo

May 2007

I solved it by making my own collision mask and drawing software circle fills into it. Simple vector<bool> 2D array of pixels that are alpha non-zero in the original image.

I didn't feel like doing a bunch of bit shifting and masking so I just used bool instead of bits.

The real pain is downloading anything off the gpu. You can't reliably DL more than around 1024X768 off the gpu each frame without incurring performance penalties. It just takes too long.

But really, with a shader, couldn't I just set my shader and then 'draw' my missile positions into a shader that did nothing but check the target texture for alpha value?

Chris Katko

Member #1,881

January 2002

relpatseht said:

^^^^^^^^^^^^^^^THIS.

If you want speed, or to use the GPU (and why else to use it?), you don't use async events. You use data-oriented design. Think of everything as streams of data, and transformations on those streams. Everything MUST operate on CHUNKS of data at a time, not a single data point.

99% of the time, this improves your code too because it prevents you from coupling things that shouldn't be coupled. Like, updating object state... inside of a draw() call.

But basically, you make an array of structs containing whatever you want to work on (object positions, for example) send them all to the GPU, then have it do the work on a large batch of them (while you then do something else with the CPU), and then when the results are ready, you deal with those results on the CPU side.

-----sig:
“Programs should be written for people to read, and only incidentally for machines to execute.” - Structure and Interpretation of Computer Programs
"Political Correctness is fascism disguised as manners" --George Carlin

Edgar Reynaldo

Major Reynaldo

May 2007

So far I've gotten a lot of different answers. PBOs, glReadPixels (fail), Occulsion queries, etc.

If I put my missile positions in a 1D texture, and use a shader to draw that texture invisibly onto my collision mask, can't I set a few variables inside the shader, and then read them back?

relpatseht

Member #5,034

September 2004

You can, but it's foolish. Occlusion queries are designed for this exact task.

[edit]
To clarify, occlusion queries have the GPU tell you what overlaps, rather than reading back the entire buffer from the GPU then scanning it pixel by pixel to determine what overlapped on the CPU (ala glRedaPixels circa 1990 and PBOs circa 2000).

Edgar Reynaldo

Major Reynaldo

May 2007

Well at this point it's rather academic, since I have it all working smashing well now in the latest version. Full speed in full screen, lasers blaring missiles blowing up everywhere and it all works fine.

Cookies 8-)

One thing I don't understand is all this asynchronous junk. How am I supposed to do collisions when my physics on the gpu is 3 frames behind by the time it arrives? Why would I do it this way? I mean I could do the explosions vs. missiles test by mask, but it already works by radius. I could do the lasers on a collision buffer like I was doing before, but it was super slow overall. The only thing left is the city mask, which would be nice to do on the gpu, but works now that my software circle fill works.