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.

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)

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?

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.

Anyway, can someone please help me debug it?

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

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

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