Pixel Perfect collision with rotation support?

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

Recommended Posts

Anyone know how to make a pixel perfect collision function that supports rotation of the sprites?

This is for a 2d game.

I have a feeling this is a performance killer.

Share on other sites

You want to use some kind of divide and conquer algorithm, like an quadtree for maximum efficiency, first checking the top level nodes which encompass the whole sprites, then somehow go lower and lower eliminating nodes (and thus all the pixels covered by them) until you find the pixels that are colliding.

Rotation can be added by just testing for collision between 2 rotated boxes.

If this sounds complex or if your sprites are not that complex, i would suggest making a simple polygon thats approximately the shape of the sprite and using that for collision.

It will probably be faster and give you smoother collisions (pixels are kind of... rough)

Another option would be to make a bunch of spheres to represent the collideable parts of the sprite. Sphere-Sphere collisions are very simple so it would be easy to implement (for small objects at least, straight edges not so much)

What kinds of objects and collisions do you have/need?

Share on other sites
I searched for a solution to the same problem a few months ago. I found a fantastic work from microsoft.
It is the fastest pixel perfect collision idea i have found, and support whatever affine transformation(but you need a transformation matrix)

http://xbox.create.msdn.com/en-US/education/catalog/tutorial/collision_2d_perpixel_transformed

The standard idea to support rotations is to work in the local space of the sprite A and bring the sprite B in local A space.

Then, microsoft suggests to transform the X and Y versor of A local space to B's one, and then just add the transformed versors to the B's local transofrmation currently checked coordinate, in order to make 2 additions instead of a matrix multiplication

The archive in the link contains a better explaination, but i hope you can get a grasp of what i meant.

Here's my implementation. It works really nice even on mobile hardware. Obviously you can't abuse pixel perfect collision
https://github.com/MakersF/AndEngineCollisionsExtension/blob/master/src/com/makersf/andengine/extension/collisions/pixelperfect/PixelPerfectCollisionChecker.java

As waterlimon stated, use pixel perfect collision only if it is the only one that make sense (you have sprites that should have holes and you must check against point that can potentially be smaller that that holes. Or something extremely unregular)

Share on other sites

Thank you Makers_F!

I found some interesting things in that link.

Making your code compatible with Slick2D would be a lot easier than translating microsofts code(which uses lots of overloaded operators).

Can you help me with that?

Share on other sites

For the past few days I have been trying to translate the C# method Makers_F linked above.

The method if now fully translated but its not working. The collision detection is wrong and random.

Here is the code:

	//A GameObject stores the entity's width, height, rotation(degrees), color data and position
static boolean pixelPerfectRotation(GameObject obj1, GameObject obj2)
{
//obj1 and obj2 is just rotated, no translate, nothing else!

//Create two transforms that rotates around their center point.
Transform tA = Transform.createRotateTransform((float) Math.toRadians(obj1.rotation), obj1.currX + obj1.width / 2, obj1.currY + obj1.height / 2);
Transform tB = Transform.createRotateTransform((float) Math.toRadians(obj2.rotation), obj2.currX + obj2.width / 2, obj2.currY + obj2.height / 2);
Transform AToB = Utilities.multiply(tA, Utilities.invert(tB));

Vector2f stepX = Utilities.transformNormal(new Vector2f(1, 0), AToB);
Vector2f stepY = Utilities.transformNormal(new Vector2f(0, 1), AToB);

Vector2f yPosInB = AToB.transform(new Vector2f(0, 0));

for (int yA = 0; yA < obj1.height; yA++)
{
Vector2f posInB = new Vector2f(yPosInB);

for (int xA = 0; xA < obj1.width; xA++)
{
int xB = Math.round(posInB.x);
int yB = Math.round(posInB.y);

if (0 <= xB && xB < obj2.width && 0 <= yB && yB < obj2.height)
{
if (obj1.data[xA][yA] != 0 && obj2.data[xB][yB] != 0)
return true;
}
posInB.x += stepX.x;
posInB.y += stepX.y;
}
yPosInB.x += stepY.x;
yPosInB.y += stepY.y;
}
return false;
}


	//Class Utilities
public static Transform invert(Transform t)
{
float[] matrix = t.getMatrixPosition();
float a  = matrix[0];
float b  = matrix[1];
float c  = matrix[3];
float d  = matrix[4];
float tx = matrix[6];
float ty = matrix[7];
final float value = a*d-b*c;

float[] inverted = {
d/value,
-b/value,
0,
-c/value,
a/value,
0,
(c*ty-d*tx)/value,
-(a*ty-b*tx)/value,
1
};

Transform trans = new Transform();
float[] matrix2 = trans.getMatrixPosition();
matrix2[0] = inverted[0];
matrix2[1] = inverted[1];
matrix2[2] = inverted[2];
matrix2[3] = inverted[3];
matrix2[4] = inverted[4];
matrix2[5] = inverted[5];
matrix2[6] = inverted[6];
matrix2[7] = inverted[7];
matrix2[8] = inverted[8];

return trans;
}

public static Transform multiply(Transform t1, Transform t2)
{
float[] m1 = t1.getMatrixPosition();
float[] m2 = t2.getMatrixPosition();

float t11 = m1[0]*m2[0] + m1[1]*m2[3] + m1[2]*m2[6];
float t12 = m1[0]*m2[1] + m1[1]*m2[4] + m1[2]*m2[7];
float t13 = m1[0]*m2[2] + m1[1]*m2[5] + m1[2]*m2[8];

float t21 = m1[3]*m2[0] + m1[4]*m2[3] + m1[5]*m2[6];
float t22 = m1[3]*m2[1] + m1[4]*m2[4] + m1[5]*m2[7];
float t23 = m1[3]*m2[2] + m1[4]*m2[5] + m1[5]*m2[8];

float t31 = m1[6]*m2[0] + m1[7]*m2[3] + m1[8]*m2[6];
float t32 = m1[6]*m2[1] + m1[7]*m2[4] + m1[8]*m2[7];
float t33 = m1[6]*m2[2] + m1[7]*m2[5] + m1[8]*m2[8];

Transform trans = new Transform();
float[] matrix = trans.getMatrixPosition();
matrix[0] = t11;
matrix[1] = t12;
matrix[2] = t13;
matrix[3] = t21;
matrix[4] = t22;
matrix[5] = t23;
matrix[6] = t31;
matrix[7] = t32;
matrix[8] = t33;

return trans;
}

public static Vector2f transformNormal(Vector2f src, Transform transform)
{
float[] matrix = transform.getMatrixPosition();

return new Vector2f(src.x * matrix[0] + src.y * matrix[3],
src.x * matrix[1] + src.y * matrix[4]);

//		Vector2f vec1 = transform.transform(src);
//		Vector2f vec2 = transform.transform(new Vector2f(0,0));
//
//		return new Vector2f(vec1.x - vec2.x, vec1.y - vec2.y);
}


The Transform class is from Slick2D's library.

A thing that confuses me about the original code by Microsoft is that they are never taking the two entities position into account, they are never used in the method.

Edited by P0jahn

Share on other sites
The position is taken into account by the transformation. The transformation matrix contains the translation, rotation, skew and scale. This means that if you multiply {0,0} (the left bottom corner of your sprite) for the matrix of this sprite, it will give the coordinates of the point in the world coordinate system which touches the left bottom corner of your sprite. This is valid for every point of the sprite

Share on other sites

Isint 0,0 usually the top-left corner of an image?

Share on other sites
It doesn't matter. It depends on the coordinate system. It can even be the centre. Try to understand the concepts, not the single example! Replace "left bottom" with "top-left", "center", "a point a hundred times the dimension of the sprite away from the sprite" and it will still be corrected! The transformation translate a whatever point in the local coordinate system to the world coordinate system