2D Mask Collision

[knxrb]

Hi guys, I'm trying to find a way to do pixel perfect sprite collisions using VB.Net 2005 and just so you all know I can't use DirectX for this app.

I've heard sprite masks mentioned for collisions and I was wondering how I could do this and if it would give me pixel perfect collisions?

The sprites are all random, they are all different sizes and I can't use rectangles or circles for bounding boxes as it won't give me pixel perfect collisions that way

Thanks in advance, knxrb

[SJWhiteley]

Well, how I used to do it was a two-step (or three step) process:

Get the bounds of your sprites in a rectangle. Perform a hit-test between the bounds rectangle. If they don't intersect then not additional testing necessary.

Optionally, break down each sprite into smaller bound rectangles (this is precomputed at sprite generation). Check an intersect between these smaller rectangles and the intersect region. If there are no hits then go about our business.

Get the intersections and perform pixel/boolean hit testing on the sprite masks in that region (again the sprite masks are precomputed).

Performing the intermediate test can speed things up, especially if you have 'full hit' flags for each sub-rectangle: this means if there's an intersect with this rectangle then it's a hit with no pixel level check required.

This can all be done with simple arrays, if-thens and loops. If you are mathematically inclined then you can use vector and array transformations...

...however, this is with old, VB and API calls to C DLLs. There may be some fancy smancy .NET stuff which could help (barring your DirectX limitation of course).

[knxrb]

So you mean:
1. Check for a collision with the bounding box rectangle.
2. If there is a collision then split image and check each bit for a collision.

How do I check if there is a collision between a bit of a picture and another sprite's bit of a picture?

knxrb

[SJWhiteley]

How do I check if there is a collision between a bit of a picture and another sprite's bit of a picture?

Loop through the rectangle areas which overlap on the masks.

Since the masks are basically 2D arrays of boolean values, if both mask bits are true then you have a collision.

It's a brute force method, but if you are smart with your sprite design it can be very quick (i.e. the planning phase determines how well your code performs).

Based on your drawing (a circle for your sprite) you wouldn't split the circle into quadrants: you'd probably have a single square which covers the center (any intersect on this rectangle is a collision); 4 rectangles which cover the remaining portions of the circle. The 'corners' do not have any rectangles in them, as any 'overlap' here would be a miss, regardless.

So, for a circle, you'd store 6 rectangles: the full bounds rectangle (black), the center rectangle (E) and the 4 border rectangles (a,b,c,d).

[Jenner]

Granted, a routine like this would work, but it could potentially be pretty slow. There's no mechanism outside of DirectX that does fast sprite intersection. XNA has a really good and simple implementation for determining sprite intersection, but that too uses DirectX to do it.

[knxrb]

Ok cool, but how would I know if the sprites collide because even your rectangles have massive gaps around the sprite.

[SJWhiteley]

Ok cool, but how would I know if the sprites collide because even your rectangles have massive gaps around the sprite.

Do you mean the corners? Of course: there's no point in checking these areas because the sprite doesn't cover that area (considering our circular sprite). So even if you have a rectangular sprite, for example, that is 'in' that area, there is no collision.

The left/right/top/bottom rectangles will require you to 'scan' each pixel in the overlapping region. That is, find the intersecting region and loop through the pixels in that region. If a pixel in one sprite is set and the pixel in the other sprite is set then you have a collision.

Note that it does require math, but not particularly complex.

[knxrb]

Oh I get it, so I see if a black pixel from one mask and a black pixel from the other mask are in the same spot, got you