3D Billboard Collision Detection

Hi, I’m doing a 2.5D game similar to “Assassin’s Creed Chronicles China”. I want my Environment to be 3D and my characters to be 2D sprites. So I’ve came across the Billboarding way of doing this, to put a texture/sprite onto a 3D plane, but my problem is how will I use my per-pixel collision on that plane now because it wont be just a Texture2D sprite but a 3D plane. Is there a way to get the perfect collision meaning all non-alpha/transparent pixels/vertices in this case will collide with other objects. Without using a Bounding Box way, but something similar to per-pixel collision.

Will very much appreciate it if someone can help, since this game is a year project for my final year and I’ve chosen MonoGame for my technology of choice. (https://www.youtube.com/user/GermanXNATutorials) has great tutorials but they are in German :sob: if anyone know any tutorials I could follow please help. Cool thanks.

My suggestions (Throbax TD works the same way, but is a RTS game) is that you first register the sprites to test for collisions on a grid. Choose the size reasonably. Read (or use) this to get an idea of what I’m talking about.
Now that you have a reasonably low number of collision-candidates you can do per-pixel collision testing.
Get the currently drawn texture from the billboard for the two sprites and their position and test for the collision.

Here is some example code from our game:

/// <summary>
///     Determines if there is overlap of the non-transparent pixels between two
///     sprites.
/// </summary>
/// <param name="transformA">World transform of the first sprite.</param>
/// <param name="widthA">Width of the first sprite's texture.</param>
/// <param name="heightA">Height of the first sprite's texture.</param>
/// <param name="dataA">Pixel color data of the first sprite.</param>
/// <param name="transformB">World transform of the second sprite.</param>
/// <param name="widthB">Width of the second sprite's texture.</param>
/// <param name="heightB">Height of the second sprite's texture.</param>
/// <param name="dataB">Pixel color data of the second sprite.</param>
/// <returns>
///     True if non-transparent pixels overlap; <c>false</c> otherwise
/// </returns>
public static bool IntersectPixels(Matrix transformA, int widthA, int heightA, bool[] dataA, Matrix transformB,
									int widthB, int heightB, bool[] dataB)
	if (dataB == null)
		return false;
	// Calculate a matrix which transforms from A's local space into
	// world space and then into B's local space.
	Matrix bInverted = Matrix.Invert(transformB);
	Matrix transformAtoB = transformA*bInverted;

	// When a point moves in A's local space, it moves in B's local space with a
	// fixed direction and distance proportional to the movement in A.
	// This algorithm steps through A one pixel at a time along A's X and Y axes
	// Calculate the analogous steps in B:
	Vector2 stepX = Vector2.TransformNormal(Vector2.UnitX, transformAtoB);
	Vector2 stepY = Vector2.TransformNormal(Vector2.UnitY, transformAtoB);

	// Calculate the top left corner of A in B's local space.
	// This variable will be reused to keep track of the start of each row.
	Vector2 yPosInB = Vector2.Transform(Vector2.Zero, transformAtoB);

	// For each row of pixels in A.
	for (int yA = 0; yA < heightA; yA++)
		// Start at the beginning of the row.
		Vector2 posInB = yPosInB;

		// For each pixel in this row.
		for (int xA = 0; xA < widthA; xA++)
			// Round to the nearest pixel.
			int xB = (int) Math.Round(posInB.X);
			int yB = (int) Math.Round(posInB.Y);

			// If the pixel lies within the bounds of B.
			if (0 <= xB && xB < widthB && 0 <= yB && yB < heightB)
				// Get the colors of the overlapping pixels.
				bool colorA = dataA[xA + yA*widthA];
				bool colorB = dataB[xB + yB*widthB];

				// If both pixels are not completely transparent,
				if (colorA && colorB)
					// then an intersection has been found.
					return true;

			// Move to the next pixel in the row.
			posInB += stepX;

		// Move to the next row.
		yPosInB += stepY;

	// No intersection found.
	return false;

And that’s how we call it:

Matrix transformA = Matrix.Identity;
transformA *= Matrix.CreateTranslation(-Origin.X, -Origin.Y, 0f);
transformA *= Matrix.CreateScale(new Vector3(Scale.X, Scale.Y, 1f));
if (DrawRotatedSprite)
	transformA *= Matrix.CreateRotationZ(RotationalCorrectionInRadian + Rotation);
transformA *= Matrix.CreateTranslation(Position.ToVector3());

Matrix transformB = Matrix.Identity;
transformB *= Matrix.CreateTranslation(-otherSprite.Origin.X, -otherSprite.Origin.Y, 0f);
transformB *= Matrix.CreateScale(new Vector3(otherSprite.Scale.X, otherSprite.Scale.Y, 1f));
if (DrawRotatedSprite)
	transformB *= Matrix.CreateRotationZ(otherSprite.RotationalCorrectionInRadian + otherSprite.Rotation);
transformB *= Matrix.CreateTranslation(otherSprite.Position.ToVector3());

if (Utils.IntersectPixels(transformA, spriteTexture.SpriteWidth, spriteTexture.SpriteHeight,
	GetCurrentSpriteCollisionData(spriteTexture), transformB, otherSpriteTexture.SpriteWidth,
	otherSpriteTexture.SpriteHeight, otherSprite.GetCurrentSpriteCollisionData(otherSpriteTexture)))
	return true;

The only problem could be the Color[] we pass to the method. This is something we pre-calculate in our content-processor. You would have to change it to a texture.
If you’re interested or need further help, I will refactor it and put it up on github or MonoGame.Extended (if it doesn’t already contain that).

Thanks a lot @throbax will have a look at it, hope it will help me. Cool :wink:

Oh. Sorry. Just realized the reason for that bool-array instead of a texture…
In order to get per-pixel collision-testing to work you ultimately have to compare the alpha-values of the pixels of the two sprites. So in order to get those values, you’d have to call getData() on both textures and that operation is notoriously slow because it essentially transfers data from the GPU (where the textures and rendertargets reside) to the CPU (where you’d like to do your comparison).
So we did that for every image in the atlas beforehand and stored the bool-array (true means A>0 and false A==0 or vice versa).
Maybe I should extract all that into a separate project…
Maybe you could help setting up a project on github? I will join in.

Oh… And before we both do anything stupid we will regret later on… @craftworkgames: Is that an integral part of MG.Extended already or a valid feature candidate?
Thx in advance.

I’m not sure about the MonoGame.Extended library, I never used it. Will try to make a sample program that contains maybe two textured billboards (characters) and a 3D cube, so we can test with that. I will let you know when I’ve done that. Thanks.

I’ve extracted some of the code and placed it in a public git repo. You can access it here:

Not tested (although it really should work; Didn’t change that much).
No NUnit tests.

Please edit it as you like and push to that repo.
Maybe we’ll get it clean so we can port it to MG.Extended at some point in time.

I can see this is working with a Texture2D all the way. What about the 3D plane (Billboard)?.. How are you guys rendering your sprites in your game? As just 2D sprite or unto a 3D plane? The biggest issue here is I can try to forget about rendering my sprite onto a plane, but use SpriteBatch to draw it as 2D but how will I do the collision between the 3D environment and the 2D sprites?

Also you mentioned I should only call the GetData method only once, what about animated sprites (Sprite Sheet)? Because at every frame it wont display the same image or do I read the entire sprite sheet once ignoring which current image is displayed?

Will try to look at the PerPixelCollision repo tomorrow, I’m kinda tired for today. Thanks a lot for your help.

Even if the world is 3d, your sprite is (i am making the assumption it cannot go foreground or background) always on the same plane. You can project the world orthographically to get 2d representation and use 2d algorithms to test collisions.

So you saying I can just use my 2D sprite (Texture2D) directly without using a 3D plane to draw my characters in the 3D world? If so then that will be cool, the only challenge will be the collision between 3D objects and 2D sprites. Cool… I will experiment and see the results. Just need to understand the matrices (world, view and projection) well so I can be able to apply them correctly. Thanks.

If you project all the 3D stuff the ortho way in a backbuffer and use this for collision test, i think it should work.
I have already tested this on xna 3 years ago and it worked fine. The only drawback is to draw the world 2 times : one 3D for the display, and ortho in the background. If you use MRTs you should be able to do it in one pass.

Okay cool… I will try that… what is MRTs?

Multiple Render Targets.

Hi guys, I’m still currently busy with Computer Graphics and Networks for now, since I have practicals and projects to complete. Will look at the game as soon as I have time because Graphics and Networks are semester modules whereas the Game Project module is a year module, so I need to work on the other modules first. Just letting you guys know just in case you wondering why I haven’t got back to you. Thanks.