home n64
introduction
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.
world collision system overview
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:
- asset creation
- in blender, create the 3d model for the environment that the player will walk around in.
- 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)
- compile time (pc)
- 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.
- 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.
- run time (n64)
- 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.
- the result of loadCollTriangles() is a vector of triangles in memory, reconstructed from the .bin file.
- 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.
- finally, the collision function, resolveWallCollision(), is called every frame.
save_triangles.cpp -> loadCollTriangles()
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 $< $@
resolveWallCollision()
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:
- 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
- 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):
- check if the sphere represented by the player's position + movement direction (playerPos+movementDir) intersects the current triangle. if it does:
- if the triangle's angle is less than maxSlopeAngle, set grounded = true (the player is touching a triangle he can walk on)
- 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)
- loop through the list of normals we collected:
- 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)
- 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:
- calculate the current normal vector multiplied by the previously calculated dot product and subtract the result from the aggregate collection vector
- after all correction vectors are aggregated, return the original movementDir + the aggregated corrections
sphere/triangle collision