# How do collision meshes work in games like Zelda on the N64?

I was recently reading about the technology of Ocarina of Time/Majoras Mask and discovered that world collision is done using a single triangle mesh (vertices, normals, etc) for an entire area. There are also no signs of preprocessed spatial partitioning methods in that data structure.

What algorithms exist for performing character collision on a similar arbitrary triangle mesh fast enough to run on a platform like the N64?

Quake is a contemporary game with a similar feature that came to mind. I understand Quake brush collision works by subdividing an AABB with planes. If a point is in the AABB and behind all the planes there is a collision. However, this method only works using a bunch of individual convex objects to make up a collision scene.

Zelda data structure details Here:

EDIT - I don't need to know the real method used by the real game, Zelda is an example. I am looking for a method of achieving a similar effect under similar hardware constraints.

• This question appears to be off-topic because it is about how a particular game works, which we don't allow. Aug 2, 2013 at 19:45
• @NicolBolas I am mainly using this as an example, I don't care particularly about the real method used, I wan't to know how this style collision is done on constrained hardware. Thats why I asked "what techniques could be used for this" Aug 2, 2013 at 20:15
• @NicolBolas from your link the answers say that questions about parts of technology are better and "How can I achieve a similar effect as in Game X" are good. Aug 2, 2013 at 20:16
• Maybe you should edit the question to the specifics of your situation, instead of how it might have been done by an old game. The answer will be far more relevant to you. Aug 2, 2013 at 21:21
• I have the feeling no one is going to answer this. It's basically Japanese spaghetti code magic. I do too want to know how this is done. Aug 2, 2013 at 23:51

EDIT:

This project decompiled Mario 64 and contains the source for collision.

Taking tigoru's advice. I instead searched for how the technique is done in Mario 64. (Zelda's engine is a direct derivative).

I found that this document was mentioned in Mario 64 discussions several times.

I read through the paper and it describes an algorithm that would solve this problem. It works in a similar way to sweeping ellipses in quake, but is built around triangle soup, rather than brush/plane soup.

The algorithm presented in this paper handles collision detection against arbitrary meshes stored as a so-called polygon soup. When a collision is detected the algorithm will slide the moving entity along the obstacles as it is typically seen in 3d computer games. The moving entity is approximated with an ellipsoid which gives a fairly tight fit for most humanoid or animal shapes.

The algorithm also solves a lot of performance problems:

Personally I haven’t had any performance problems with it and one also has to remember that there are two “early out” points in the function which actually kicks in quite often. Here are some statistics: I walked around a few minutes in an ERA test map which consisted of both a terrain (build from a heightmap) and polygon meshes such as houses, stairs etc. In total 1.1 million triangles were sent to the function over the whole test period and of those approximately 40% were detected to be backfacing and thus skipped1. Of the remaining 700.000 triangles 65% were able to exit early from the function after just a few cheap tests to calculate the time values t0 and t1. Of those triangles that didn’t exit early most had to perform the sweep test but a few could skip the sweep because a collision against the inside of the triangle were detected. All in all only about 20% of the triangles being sent to the function had to actually be checked for collision against the inside or edge of the triangle and thus payed the full price for the rather long function.

• Correct me if i'm wrong : the document explain a efficient way to detect collision between an ellipsoid and a triangle (and response). but does it use any kind of spatial data structure to accelerate the process (or are almost all triangles checked, eg : only backfacing are filtered) ? Aug 14, 2013 at 8:59
• @tigrou not a single triangles, an arbitrary triangle mesh (bouncing etc). You are correct though, it does not describe a data structure to optimize the process. However, the algorithm can quickly eliminate irrelevant triangles. The zelda collision mesh had no sign of an optimized structure, unless it was somehow divided at runtime. Aug 14, 2013 at 15:55

I'd be surprised if they don't pre-process that list of polygons on load into a spatial data structure. It could be as simple as a uniform 2D grid over the world, or something more complicated like a k-d tree.

That would allow you to rapidly find a short list of the polygons which are close to a point of interest, and you can then test each one to see if you're colliding.

Any modern physics engine should easily handle a static mesh of collision polygons efficiently by using some form of spatial subdivision. For example check out the btBvhTriangleMeshShape that bullet has.

• It would seem strange in that case not to pre process it... Would collision be something like a ray triangle check once a possible set was identified?' Aug 3, 2013 at 3:59
• Probably a sphere-triangle check, where the character is represented as a sphere. You can quickly reject triangles based on the sphere-plane distance that way.