Android collision detection of a 3d object based on a 2d projection

Question

I am writing a game for android. We have an orthographic view setup, but the characters (ships, projectiles, etc). The enemies / characters will be able to rotate about the x axis. The problem is that I want to do the collision detection as if it were in 2d using sprites, meaning that if i have a ship with a top down view of

---------
--------------
-----------------
--------------
---------

it might rotate to look like

-----
--------------
---

and i want to do all of the collisions based off of the appearance of a top down view. I was originally thinking of using glReadPixels, until I read that was unbelievably slow. Then I was thinking about using pre-rendered bitmaps, but that seems like a pain and not very great since some of our ships won't be 'normal' enough to just say "Have a bitmap for every 45 degrees of rotation about the X". Does anyone have any suggestions?

Answer 1

Posting an answer in case anyone comes searching for this topic.

Since this is on Android, I believe the assumption is that CPU is scarce, and so the collision algorithms need to be cheap. Based on that assumption, we will construct a system and then discuss optimizations:

1) [Offline] Simplify the 3D models into a collision mesh. This is a very typical procedure in any 3D game, and is done in the Content Creation Pipeline.

2) [Offline] Calculate a bounding sphere for every 3D collision mesh.

3) [Run-time] Project the 3D bounding sphere of each object to a 2D bounding circle.

4) [Run-time] Do cheap, simple circle-circle collision checks.

5) [Conditional Run-time] If a circle-circle collision occurs, project the full 3D collision meshes for both objects into 2D. This is trivial if you know your Linear Algebra.

6) [Conditional Run-time] Now do 2D triangle mesh intersection tests. If this returns True, you have a 2D collision.

Steps 1 and 2 are cheap, because you do them offline or at startup.

Step 3 is fairly cheap. For extra speed, only re-project a sphere if its projected size will change. This depends on your Projection matrix. In a top-down view, for example, this will only occur if the camera changes height, the objects change height, or the camera zooms in/out.

Step 4 is dirt cheap. Calculate the distance between the objects:

float total_radius = a.bounding_radius + b.bounding_radius;
if(DotProduct(a.2D_position - b.2D_position) < total_radius*total_radius)
    // Possible Intersection Detected!

Step 5 may be expensive, depending on your collision mesh complexity, matrix library speed, and the Android device. Luckily its hidden behind the circle-circle test. Step 5 can be optimized by caching the 3D projections. So, after you've projected a 3D model into 2D triangles, store that in the object's data. Only re-do that projection if the object has rotated, or moved closer/further to the camera. Also, don't forget back-face culling!

Step 6 is, again, expensive, but hidden behind the circle-circle test. At the cost of intersection quality, you can simplify the triangle-triangle intersection test to ignore triangle-within-triangle tests. This depends on your game, but I think most games would be fine without that test.

Both step 5 and step 6 can be optimized by sacrificing collision quality with respect to time. While the game may be rendering at 30 or 60fps, you can perform collision checks at 10fps, or at a rate adjustable based on current rendering performance.

Other optimizations depend entirely on your specific game. Collision meshes can be made quite simple, and thanks to back-face culling your final mesh-mesh collision check shouldn't be too complex. You can even do bounding circle-circle intersection tests on the triangles to cull them further (i.e., if a triangle isn't inside the other object's bounding circle, don't test it).

The FPS optimization suggested above can be taken half-way. You can re-project 2D meshes at 10FPS, but do the mesh-mesh intersections at a full 30fps.

Answer 2

I've since decided to go 2d, however, @ Tetrad and @Robert, there is something very wrong with that. The problem is that I want to do collisions based off of how it appeared to be in 2d. I would basically need to flatten all of my poly data so that it would lie on a single plane. In the simplest of terms, I needed to get rid of 1 dimension. If I have 2 ships that look like they collide, looking at them from above, I need to make sure they collide.

The overhead projection
      __________
______|_        |
|     | |       |
|     |_|_______|
|       |
|       |
---------

The same ships from a different perspective.
         _____________
_________ \           |
|        | |          |
|________| |          |
          /___________|

I want this to be a collision because it looks like it would be from a top down perspective. Bounding box collision detection would also not be sufficient in this case. The best I could come up with was rendering and using glReadPixels, but I heard that was unbearably slow.

Like I said, I've since decided to go 2d. I was only doing this in 3d so a friend who has a hard-on for OpenGL would work on this with me, but he bolted. Still, it's an interesting problem.

Thanks for your suggestions.

Answer 3

Well, you went with 2D eventually so this is purely theoretical at this point :) This is how I'd go about, as you put it, getting rid of one dimension :)

First, you need to project 3d mesh onto a 2d plane. I see two ways of doing that:

• if your projection is exactly aligned with either angle you just ignore that coordinate

• if it's not you can set up a projection matrix and use it to 'project to screen', ignoring the depth coordinate (this of course would work for the above case as well)

Then, you'd need to build a shape outline while going through all the faces. Working with faces allows you to have a concave outline by constructing a CSG sum of all projected triangles (this would be slow but then you'd be doing that on startu or it can even be preprocessed offline). If a convex outline would be OK then you need to build a convex hull. Last, optional step, would be to simplify the silhouette to make the collision detection faster.

Once you have your outline it's a simple matter of seeing if any of the edges intersect or one object is contained within the other.