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

Question

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:

http://wiki.spinout182.com/w/Zelda_64:_Collision_Format http://zeldaspeedruns.com/oot/generalknowledge/zelda-64-engine

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.

Answer 1

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.

Answer 2

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.

Answer 3

The correct answer, based on the decompiled source code, is that a 16 x 16 spatial grid is used, dividing each level into 256 lists of surfaces that cross into the space and are candidates for collision depending on the space Mario occupies, which is a single point in space between his feet.

Object to object collisions use cylinder to cylinder collision checking with each object having only a defined cylinder height, cylinder radius and cylinder Y offset.

Object to surface collisions use point to rectangle collision detection. The single point is between Mario's feet, and it is logically checked 50 units from walls, 160 units from ceilings and 0 units to floors. Surface classification is based on Y projection of the normal vector only. To realize this, flat planes that make up walls are assumed to have width 50 during the collision testing, ceilings have depth 160, and so on. Per each game frame, up to 30 frames per second, four tests are performed at even intervals between Mario's initial position and his final position between the frame. This minimizes the chances of large velocities allowing him to break through walls when frames are dropped.