9
\$\begingroup\$

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.

\$\endgroup\$
9
  • 2
    \$\begingroup\$ This question appears to be off-topic because it is about how a particular game works, which we don't allow. \$\endgroup\$ Aug 2 '13 at 19:45
  • 4
    \$\begingroup\$ @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" \$\endgroup\$ Aug 2 '13 at 20:15
  • 2
    \$\begingroup\$ @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. \$\endgroup\$ Aug 2 '13 at 20:16
  • 2
    \$\begingroup\$ 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. \$\endgroup\$
    – House
    Aug 2 '13 at 21:21
  • 3
    \$\begingroup\$ 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. \$\endgroup\$
    – Sidar
    Aug 2 '13 at 23:51
5
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\begingroup\$ 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) ? \$\endgroup\$
    – tigrou
    Aug 14 '13 at 8:59
  • \$\begingroup\$ @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. \$\endgroup\$ Aug 14 '13 at 15:55
3
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\begingroup\$ 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?' \$\endgroup\$ Aug 3 '13 at 3:59
  • \$\begingroup\$ 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. \$\endgroup\$
    – Adam
    Aug 3 '13 at 18:19
1
\$\begingroup\$

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.

\$\endgroup\$
1
  • \$\begingroup\$ Thanks for bringing this back. Do you have a reference to the code or an article which this is based on? Or is the link I referenced? \$\endgroup\$ May 3 '21 at 15:23

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .