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?

  • \$\begingroup\$ How would you do it for normal sprites? Have you considered offscreen rendering of "collision map" every frame? \$\endgroup\$ – Notabene Mar 27 '11 at 22:08
  • 1
    \$\begingroup\$ If you just did the collision in 3D this would be trivial, but I'm assuming you don't have a framework that's set up for that. \$\endgroup\$ – Tetrad Mar 28 '11 at 0:55
  • \$\begingroup\$ What Tetrad said, just do it the 3D way, there is nothing wrong with that. \$\endgroup\$ – Robert Massaioli Mar 28 '11 at 3:57

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.

  • \$\begingroup\$ That's indeed the only way I was able to figure for our game Synchrom. Everything is done with Three.js And indeed as exposed steps 5-6 are expensive with quite complexe meshes : / (around 10ms). So definitelly go for simplified models \$\endgroup\$ – StackHola Aug 5 '15 at 8:01

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.

  • \$\begingroup\$ Why was this posted as an answer? It doesn't answer the question... it should be an edit of the question. \$\endgroup\$ – bummzack Jul 6 '11 at 6:53
  • \$\begingroup\$ @bummzack The user is unregistered, and due to circumstances he has two separate accounts. So he is unable to edit his answer. \$\endgroup\$ – Jesse Dorsey Jul 7 '11 at 18:18

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy