this document explains the system i developed for handling collision detection between the player and the 3d mesh representing the game environment. without such a system, the player would not interact with the environment and would walk through walls, or, if gravity is implemented, would fall through floors. early in development i used an AABB system similar to the one in example 5 (splitscreen) in HailToDodongo's tiny3d library. this system works well for small, simple environments consisting of rectangular obstacles aligned with the coordinate system, and is fairly simple and straightforward to set up. but for more complicated environments with diagonal surfaces, a more robust system is needed. additionally, in a project with many different complex environments the player could navigate between, i needed a system which would be able to automatically extract collision data from the environment mesh so that no manual intervention would be required every time i add a new area to the game.

this diagram shows all of the components of the collision system starting from creating the model in blender to calling the collision resolution function while the game is running. the flow of the system is tightly correlated with the system for displaying the environment (since the collision must happen where the visual boundaries are), so on the right side of the diagram i have included the components of the tiny3d system for rendering the environment.

here is a high level description of each step in the world collision system:

1. asset creation
   1. in blender, create the 3d model for the environment that the player will walk around in.
   2. export the model as a .glb file. (this is the same file used for the tiny3d system, indicated by the branching arrow in the diagram)
2. compile time (pc)
   1. save_triangles is a script i wrote to extract the coordinates of all the triangles in the .glb file. it is called by the makefile when compiling the n64 rom.
   2. the result of save_triangles is a .bin file containing a vector of all the triangles and their coordinates. it is loaded into the filesystem for the rom.
3. run time (n64)
   1. while the game is running, any time a new environment is loaded, the loadCollTriangles() function is called. this reads from the .bin file corresponding to the current environment.
   2. the result of loadCollTriangles() is a vector of triangles in memory, reconstructed from the .bin file.
   3. the coordinates of the triangles must be scaled and transformed the same way as the coordinates of the triangles in the rendered T3DModel. otherwise, the collision boundaries will not be aligned with the visually rendered environment.
   4. finally, the collision function, resolveWallCollision(), is called every frame.

save_triangles is a standalone script i wrote to extract triangle information (3d coordinates of vertices grouped by triangles) from a .glb file exported from blender. it uses the tinygltf library.

it can be run from the command line with the following syntax:

save_triangles <path/to/input.glb> <path/to/output.bin>

i modified the makefile for my game to automatically execute save_triangles if a new .glb file is added to the game assets or an existing one has been updated:

filesystem/%.bin: assets/models/%.glb
@mkdir -p $(dir $@)
@echo " [COLL] $@"
tools/save_triangles/save_triangles $< $@

another feature of this script is that it will ignore triangles if the name of the material applied to them starts with "noColl_". this makes it easy to mark structures in the environment model that i don't want the player to collide with.

there were a couple unforeseen obstacles i encountered while getting this to work. the first is that the endianness (or byte order) of the n64 is opposite to the one of my computer. to account for this, i had to make the script swap the byte order of the data before writing it to the binary file.

the other obstacle was that i didn't know the coordinates of the visual models get scaled up by 64 to reduce floating point errors. eventually i figured this out and incorporated the same scaling to the collision triangles.

my resolveWallCollision() function returns a 3d vector indicating how the player should be moved to correct any collisions for the current frame. i chose to use a sphere to represent the collision box for the player since my game doesn't involve any complex physics with the character model. the inputs are as follows:

• playerPos: a vector representing the player's current position
• playerRadius: the radius of the sphere representing the player's collision box
• triangles: the std::vector of triangles previously loaded with loadCollTriangles()
• maxSlopeAngle: a float representing the angle delineating a wall vs. walkable ground (i.e., if the triangle being evaluated has an angle relative to horizontal greater than maxSlopeAngle, the player will collide with it as if it were a wall. if the angle is less than maxSlopeAngle, the player will walk on it)
• movementDir: a vector representing the direction the player is trying to move in this frame based on controller input
• grounded: a pointer to a boolean keeping track of whether the player is in contact with a walkable triangle

here are the steps in my algorithm:

1. initialize the following:
   • a vector = {0,0,0} to represent how the player should be moved to resolve all collisions
   • an empty list of vectors to keep track of normal vectors of surfaces the player is colliding with


2. loop through all of the triangles in the environment and do the following (note: eventually i will implement a BVH to avoid searching through every single triangle):
   1. check if the sphere represented by the player's position + movement direction (playerPos+movementDir) intersects the current triangle. if it does:
      1. if the triangle's angle is less than maxSlopeAngle, set grounded = true (the player is touching a triangle he can walk on)
      2. add the current triangle's normal vector to a list of vectors if it's not similar to any vector already in the list (we are collecting normal vectors of all surfaces the player is colliding with, but a surface can have multiple triangles and we only want one normal vector per surface)


3. loop through the list of normals we collected:
   1. calculate the dot product of movementDir and the current normal vector (we want to see if the player is colliding with the front or the back of the surface)
   2. if the dot product is < 0, the player is colliding with the front of the surface (if this check is not done, the player may get stuck on outer corners) and we want to calculate the correction vector:
      1. calculate the current normal vector multiplied by the previously calculated dot product and subtract the result from the aggregate collection vector


4. after all correction vectors are aggregated, return the original movementDir + the aggregated corrections

step 2a in the explanation of resolveWallCollision() mentions checking if the player sphere collides with a triangle. here i will lay out the steps to do that:

1. find the point on the triangle which is closest to the sphere. if the distance between that point and the center of the sphere is less than the sphere's radius, the sphere is colliding with the triangle.
   
   1. to get the closest point on the triangle:
      1. calculate the normal vector of the triangle by normalizing the cross product of the vectors of two of the triangle's sides
      2. project the position of the sphere onto the triangle with the following formula: spherePosition - triangleNormal * (dot(triangleNormal, spherePosition) - dot(triangleNormal, triangle.v0))
      3. if the projected point is inside the triangle, return it
         1. to determine if the point is in the triangle, create 3 triangles based on the triangle's vertices (v0, v1, v2) and the point (P) calculated in the previous step
         2. calculate the areas of the triangles (a0, a1, a2) and divide each by the area of the original triangle (A)
         3. the point is in the triangle if all of the following are true:
            • a0/A < 1
            • a1/A < 1
            • a2/A < 1
            • (a0+a1+a2)/A = 1
      4. if the projected vector is not inside the triangle, find the closest point between the sphere and the triangle's edges.