ColMesh - 3D Collisions Made Easy!
License
The ColMesh system is licensed under a CreativeCommons Attribution 4.0 International License.
This means you are free to use it in both personal and commercial projects, free of charge.
Appropriate credit is required.
What is a ColMesh?
A ColMesh is a collection of 3D primitives and triangle meshes against which you can cast rays and do collision checks. It is basically an easy-to-use 3D collision system for GMS 2.3.
What does it do?
It will push your player out of level geometry.
It handles slope calculations for you so that your player doesn’t slide down slopes.
It lets you move platforms around and gives you everything you need to make sure your player moves the same way.
It lets you cast rays so that your player can shoot bullets or laser beams, and by casting a ray from the player’s previous coordinate to the new coordinate before doing collision checking, you can make sure the player never falls through level geometry.
How does it do it?
It’s all GML, so it should work on any platform. Any object that should check for collisions against level geometry must be represented by either a sphere or a capsule.
The level can be subdivided into smaller regions so that your player only has to check for collisions with nearby primitives.
For the actual collisions it uses this thing, you might have heard of it, it's called math.
But why would I make a 3D game in GameMaker?
That’s entirely up to you. There are better tools out there, with branch standard 3D physics dlls and the like.
Only use GM for 3D games if you really wanna use GM for 3D games
And why did you make this tool?
Because I really wanna use GM for 3D games.
What you see here is a ColMesh that has been placed inside itself, causing a recursive effect. Notice how collisions even works properly against the smaller ColMeshes
Okay!
With that out of the way, let’s get into how you can actually use this tool.
Download it from here:
Join Discord channel
Executable demo
Marketplace link
The zip contains an executable demo that has been compiled with the YYC. Since all the calculations are done CPU-side, the collision system sees a massive boost when compiling with YYC compared to VM.
Getting started
No initialization necessary, just import the ColMesh scripts, and it’s ready to be used.
Create a new ColMesh like this:
This creates an empty ColMesh. Now populate it with some geometry! There are a bunch of primitives that can be used.
For now, let’s just add a single triangle mesh by giving it the path to an OBJ file:
Now it is already possible to perform collision checks and cast rays against this ColMesh, but if it contains a lot of geometry, that will be very slow.
It’s a better idea to subdivide it into smaller regions first! In order to subdivide a model, you need to supply the desired region size. A region
will always be an axis-aligned bounding cube, and regionSize is the side length of this cube. The smaller the region size, the less geometry will be in
each region, but the more regions and more memory usage there will be. Finding the balance between efficiency and memory usage is its own art!
But in short, subdivide your model like this, and then you’re ready to collide with it:
Colliding with the ColMesh
Now, let’s go into the player’s step event. Avoiding a ColMesh can be done in varying levels of complexity. I’m first gonna show you the straightforward way of doing it:
So what happens here? Let’s break it down a bit, and look at the first 8 arguments: x, y, z, xup, yup, zup, radius, height. These describe a capsule.
Setting it to 0 will make the player slide on all surfaces. Setting it to 90 degrees will break your collisions, divide by zero, and possibly end the universe.
When checking for collisions, the potential collision points are normally sorted so that the collision with the greatest displacement is performed first. This is not the case if fast is set to true,
then it will just push the capsule out on a first-come-first-serve basis. This is useful for stuff like pushing the camera out of level geometry, or for enemies and environment objects.
The function returns an array of the following format:
[x, y, z, nx, ny, nz, collision (true or false)]
The first three indices contain the position of the bottom of the capsule, after it has been displaced out of the colmesh.
The next three indices contain the normal of the slope beneath the player. This can be used for example to figure out if the player should be allowed to jump. If the slope is too steep, maybe you shouldn’t let the player jump all the way to the top of the hill?
The last index is either true or false. If it’s true, there was a collision, and the capsule should be displaced.
Now your player is avoiding the levelColmesh! Of course, you still need to make your player move when you press your input buttons etc, but that’s up to you.
How to add primitives
At the moment, these are the supported primitives that can be put into a ColMesh, in addition to triangle meshes:
addShape returns the handle of the new shape. You can read from it, but the shape’s parameters should not be changed once it has been created.
If you want your primitives to move, you should add what’s called a dynamic. What’s that? Well, just keep reading…
Dynamic shapes
If you want your objects to move, you should add them as “dynamics”. A dynamic is a container for a primitive, or even a whole ColMesh, that can be moved around inside the ColMesh.
Adding new dynamics to a ColMesh is a pretty similar process to adding regular primitives:
Notice how the cube itself is added to local coordinates (0, 0, 0), and then its world-space position is stored in a matrix called M. This will center the cube at (x, y, z),
and if you apply any rotations, it will rotate around its own center. If you had done it the other way, adding the cube to (x, y, z) and setting the matrix coordinates to (0, 0, 0),
the pivot point of the cube will be at the world-space (0, 0, 0), which in most cases will not make sense.
Here’s how you can make it move. This little piece of code will make the cube rotate around the worldspace Y axis:
Now the cube is rotating, but the player will not rotate with it just yet. We need a way to figure out how the cube the player is standing on has moved, rotated, or been scaled since the previous step.
And for that, we have this useful function:
This will transform the player’s coordinates in the same manner that the cube it’s standing on was transformed from the previous step, making the player move and rotate with the cube.
Now, what follows is a bit of a technical explanation, so if you don’t feel ready for that just yet, feel free to skip it:
Casting rays
You can cast rays at the ColMesh using ColMesh.castRay(x1, y1, z1, x2, y2, z2). It will return the first point of intersection as an array of the following format:
[x, y, z, nx, ny, nz, intersectedShape]
It returns false if there was no intersection.
The returned array is pretty similar to what you get when displacing a capsule out of the ColMesh.
xyz is the point of intersection
nx, ny, nz is the normal at the point of intersection
The last index contains the shape struct that was hit.
You’ll often want to cast a ray from the player’s previous position to its current position, just to make sure it never passes through level geometry. Like this:
This piece of code assumes that the player is spherical. It doesn’t entirely make sense for a capsule though… We may need a smarter solution for a capsule.
We can use the speed vector of the player to figure out the best point along the capsule for which to perform a ray cast. If the player is moving downwards, it makes the most sense to cast from its feet. If it’s moving upwards, we’ll most likely want to prevent its head from going through the ceiling. As such, we can slide the origin of the ray along the capsule like this:
A ray cast should usually be followed by displacing the capsule properly out of the level geometry with ColMesh.displaceCapsule.
Trigger objects
So far we've only covered solid objects.
But a 3D world also contains non-solid objects, for example collectible objects like coins and powerups, and trigger objects like doors and portals.
You can add this kind of trigger objects as follows:
Notice how you have two optional arguments here. These allow you to control what should happen when the player collides with the shape, or when it is hit by a ray.
GMS 2.3 allows you to pass functions by reference. That means that you can create custom functions that should be executed instead of the regular collision response.
Demo 1 showcases how you can add collectible coins to a 3D level. The coins will send their collision shape a function that will increment global.coins by 1, play a sound, delete the coin object and remove the shape from the ColMesh.
The code for this looks like this:
There has also been added a new optional argument to colmesh.displaceCapsule, that allows you to turn on or off collision functions. When turned off, the custom collision functions are not executed.
This is useful for objects that should only collide with the world and not trigger game objects.
Non-solid objects are NOT saved when using colmesh.save or colmesh.writeToBuffer.
Saving and loading
You’ll typically want to precompute your ColMeshes. Generating and subdividing a ColMesh can be a slow process, so luckily you can easily save and load them to and from buffers.
If you don’t want to include the precomputed ColMeshes, you could generate them the first time they’re needed, and then cache them in local files like this:
If your game should be able to run in HTML, you can’t use the ColMesh.save and load functions. Instead, you should save and load a buffer asynchronously, and use ColMesh.writeToBuffer and ColMesh.readFromBuffer.
Planned features
These are some shapes that are planned:
Thank you!
Feedback is always appreciated.
Snidr
License
The ColMesh system is licensed under a CreativeCommons Attribution 4.0 International License.
This means you are free to use it in both personal and commercial projects, free of charge.
Appropriate credit is required.
What is a ColMesh?
A ColMesh is a collection of 3D primitives and triangle meshes against which you can cast rays and do collision checks. It is basically an easy-to-use 3D collision system for GMS 2.3.
What does it do?
It will push your player out of level geometry.
It handles slope calculations for you so that your player doesn’t slide down slopes.
It lets you move platforms around and gives you everything you need to make sure your player moves the same way.
It lets you cast rays so that your player can shoot bullets or laser beams, and by casting a ray from the player’s previous coordinate to the new coordinate before doing collision checking, you can make sure the player never falls through level geometry.
How does it do it?
It’s all GML, so it should work on any platform. Any object that should check for collisions against level geometry must be represented by either a sphere or a capsule.
The level can be subdivided into smaller regions so that your player only has to check for collisions with nearby primitives.
For the actual collisions it uses this thing, you might have heard of it, it's called math.
But why would I make a 3D game in GameMaker?
That’s entirely up to you. There are better tools out there, with branch standard 3D physics dlls and the like.
Only use GM for 3D games if you really wanna use GM for 3D games
And why did you make this tool?
Because I really wanna use GM for 3D games.
What you see here is a ColMesh that has been placed inside itself, causing a recursive effect. Notice how collisions even works properly against the smaller ColMeshes
Okay!
With that out of the way, let’s get into how you can actually use this tool.
Download it from here:
Join Discord channel
Executable demo
Marketplace link
The zip contains an executable demo that has been compiled with the YYC. Since all the calculations are done CPU-side, the collision system sees a massive boost when compiling with YYC compared to VM.
Getting started
No initialization necessary, just import the ColMesh scripts, and it’s ready to be used.
Create a new ColMesh like this:
Code:
levelColmesh = new colmesh();For now, let’s just add a single triangle mesh by giving it the path to an OBJ file:
Code:
levelColmesh.addMesh(“ColMesh Demo/Demo1Level.obj”);It’s a better idea to subdivide it into smaller regions first! In order to subdivide a model, you need to supply the desired region size. A region
will always be an axis-aligned bounding cube, and regionSize is the side length of this cube. The smaller the region size, the less geometry will be in
each region, but the more regions and more memory usage there will be. Finding the balance between efficiency and memory usage is its own art!
But in short, subdivide your model like this, and then you’re ready to collide with it:
Code:
var regionSize = 120; //120 is a magic number I chose that fit well for my player size and level complexity. It may have to be different for your game!
levelColmesh.subdivide(regionSize);Colliding with the ColMesh
Now, let’s go into the player’s step event. Avoiding a ColMesh can be done in varying levels of complexity. I’m first gonna show you the straightforward way of doing it:
Code:
var slopeAngle = 40; //The threshhold where if the slope is steeper, the player will start to slide
var fast = false; //You’ll usually want to turn off the “fast” collision checking for important objects like the player
col = levelColmesh.displaceCapsule(x, y, z, xup, yup, zup, radius, height, slopeAngle, fast);
if (col[6]) //If we’re touching ground
{
x = col[0];
y = col[1];
z = col[2];
}- xyz are the cordinates of the bottom of the capsule.
- xup, yup, zup are the up-vector of the player, this can usually be set to [0, 0, 1].
- Radius is the radius of the capsule, and height is the length of the capsule along the up-direction. Setting height to 0 will remove any calculations needed for capsule and just perform collisions for a sphere instead, which is a bit faster.
- SlopeAngle is useful for preventing the player from sliding around on even the smallest slopes.
Setting it to 0 will make the player slide on all surfaces. Setting it to 90 degrees will break your collisions, divide by zero, and possibly end the universe.
When checking for collisions, the potential collision points are normally sorted so that the collision with the greatest displacement is performed first. This is not the case if fast is set to true,
then it will just push the capsule out on a first-come-first-serve basis. This is useful for stuff like pushing the camera out of level geometry, or for enemies and environment objects.
The function returns an array of the following format:
[x, y, z, nx, ny, nz, collision (true or false)]
The first three indices contain the position of the bottom of the capsule, after it has been displaced out of the colmesh.
The next three indices contain the normal of the slope beneath the player. This can be used for example to figure out if the player should be allowed to jump. If the slope is too steep, maybe you shouldn’t let the player jump all the way to the top of the hill?
The last index is either true or false. If it’s true, there was a collision, and the capsule should be displaced.
Now your player is avoiding the levelColmesh! Of course, you still need to make your player move when you press your input buttons etc, but that’s up to you.
How to add primitives
At the moment, these are the supported primitives that can be put into a ColMesh, in addition to triangle meshes:
- Sphere
- Axis-aligned cube
- Block (can have any orientation and non-uniform scaling, but not shear)
- Capsule
- Cylinder
- Torus
- Disk
Code:
levelColmesh.addShape(new colmesh_sphere(x, y, z, radius));
levelColmesh.addShape(new colmesh_cube(x, y, z, sideLength));
levelColmesh.addShape(new colmesh_block(colmesh_matrix_build(x, y, z, 0, 0, 0, xSize / 2, ySize / 2, zSize / 2))); //The cube will be twice as big as the given scale
levelColmesh.addShape(new colmesh_capsule(x, y, z, xup, yup, xup, radius, height));
levelColmesh.addShape(new colmesh_cylinder(x, y, z, xup, yup, xup, radius, height));
levelColmesh.addShape(new colmesh_torus(x, y, z, xup, yup, xup, majorRadius, minorRadius));
levelColmesh.addShape(new colmesh_disk(x, y, z, xup, yup, xup, majorRadius, minorRadius));If you want your primitives to move, you should add what’s called a dynamic. What’s that? Well, just keep reading…
Dynamic shapes
If you want your objects to move, you should add them as “dynamics”. A dynamic is a container for a primitive, or even a whole ColMesh, that can be moved around inside the ColMesh.
Adding new dynamics to a ColMesh is a pretty similar process to adding regular primitives:
Code:
M = colmesh_matrix_build(x, y, z, 0, 0, 0, 1, 1, 1);
dynamic = levelColmesh.addDynamic(new colmesh_cube(0, 0, 0, size), M);and if you apply any rotations, it will rotate around its own center. If you had done it the other way, adding the cube to (x, y, z) and setting the matrix coordinates to (0, 0, 0),
the pivot point of the cube will be at the world-space (0, 0, 0), which in most cases will not make sense.
Here’s how you can make it move. This little piece of code will make the cube rotate around the worldspace Y axis:
Code:
M = colmesh_matrix_build(x, y, z, 0, current_time / 50, 0, 1, 1, 1);
shape.setMatrix(M, true);And for that, we have this useful function:
Code:
var D = levelColmesh.getDeltaMatrix();
if (is_array(D))
{
var P = matrix_transform_vertex(D, x, y, z);
x = P[0];
y = P[1];
z = P[2];
}Now, what follows is a bit of a technical explanation, so if you don’t feel ready for that just yet, feel free to skip it:
Okay, excellent, glad you’re interested in the technical details as well! Finding a general solution to this was a bit tricky, but I believe this is as close as I’m gonna get.
When the player (or any other object, for that matter) uses levelColmesh.displaceCapsule to collide with a ColMesh, it “secretly” creates a ds_queue in a local variable of the calling object. They are of course stored in the ColMesh as well, and will be destroyed when the ColMesh is cleared.
If the shape that causes the greatest displacement is a moving object, its current world matrix is added to this queue. It also adds the inverse of the previous world matrix. Multiplying these two matrices together will result in the delta matrix. However, there are some more complications.
The player needs to be transformed *before* colliding with the ColMesh, otherwise the transformation may cause it to end up inside the ColMesh. But we don’t get the delta matrix until *after* the collision has been done. If we multiply the two matrices together here and now, and then use the result next step, that delta matrix will already be outdated, and the player would appear to be “lagging behind” the moving object. This is why it’s so useful to save the matrices as they are – since the matrices are stored in the ds_queue by reference, they will also automatically be updated the next step once the moving object has used shape.setMatrix!
Okay, that kinda makes sense, but why use a ds_queue?
This solves another problem: A dynamic can contain a whole different ColMesh. And that ColMesh can also contain moving objects, or even more ColMeshes. A ColMesh may even contain itself, causing a recursive call (capped at 8 recursions by default, but you can change this manually). The transformations of each dynamic must stack on top of each other, starting at the bottom. As such, the queue could contain any number of matrices that all need to be multiplied together to find the final world-space delta matrix.
So that’s how moving objects work!
When the player (or any other object, for that matter) uses levelColmesh.displaceCapsule to collide with a ColMesh, it “secretly” creates a ds_queue in a local variable of the calling object. They are of course stored in the ColMesh as well, and will be destroyed when the ColMesh is cleared.
If the shape that causes the greatest displacement is a moving object, its current world matrix is added to this queue. It also adds the inverse of the previous world matrix. Multiplying these two matrices together will result in the delta matrix. However, there are some more complications.
The player needs to be transformed *before* colliding with the ColMesh, otherwise the transformation may cause it to end up inside the ColMesh. But we don’t get the delta matrix until *after* the collision has been done. If we multiply the two matrices together here and now, and then use the result next step, that delta matrix will already be outdated, and the player would appear to be “lagging behind” the moving object. This is why it’s so useful to save the matrices as they are – since the matrices are stored in the ds_queue by reference, they will also automatically be updated the next step once the moving object has used shape.setMatrix!
Okay, that kinda makes sense, but why use a ds_queue?
This solves another problem: A dynamic can contain a whole different ColMesh. And that ColMesh can also contain moving objects, or even more ColMeshes. A ColMesh may even contain itself, causing a recursive call (capped at 8 recursions by default, but you can change this manually). The transformations of each dynamic must stack on top of each other, starting at the bottom. As such, the queue could contain any number of matrices that all need to be multiplied together to find the final world-space delta matrix.
So that’s how moving objects work!
Casting rays
You can cast rays at the ColMesh using ColMesh.castRay(x1, y1, z1, x2, y2, z2). It will return the first point of intersection as an array of the following format:
[x, y, z, nx, ny, nz, intersectedShape]
It returns false if there was no intersection.
The returned array is pretty similar to what you get when displacing a capsule out of the ColMesh.
xyz is the point of intersection
nx, ny, nz is the normal at the point of intersection
The last index contains the shape struct that was hit.
You’ll often want to cast a ray from the player’s previous position to its current position, just to make sure it never passes through level geometry. Like this:
Code:
//Cast a short-range ray from the previous position to the current position to avoid going through geometry
ray = levelColmesh.castRay(prevX, prevY, prevZ, x, y, z);
if (is_array(ray))
{
x = ray[0] - (x - prevX) * .1; //Subtract the original vector multiplied by some small number so that the player ends up just outside of the intersection
y = ray[1] - (y - prevY) * .1;
z = ray[2] - (z - prevZ) * .1;
}We can use the speed vector of the player to figure out the best point along the capsule for which to perform a ray cast. If the player is moving downwards, it makes the most sense to cast from its feet. If it’s moving upwards, we’ll most likely want to prevent its head from going through the ceiling. As such, we can slide the origin of the ray along the capsule like this:
Code:
var d = height * (.5 + .5 * sign(xup * (x - prevX) + yup * (y - prevY) + zup * (z - prevZ)));
var dx = xup * d;
var dy = yup * d;
var dz = zup * d;
ray = levelColmesh.castRay(prevX + dx, prevY + dy, prevZ + dz, x + dx, y + dy, z + dz);
if (is_array(ray))
{
x = ray[0] - dx - (x - prevX) * .1;
y = ray[1] - dy - (y - prevY) * .1;
z = ray[2] - dz - (z - prevZ) * .1;
}Trigger objects
So far we've only covered solid objects.
But a 3D world also contains non-solid objects, for example collectible objects like coins and powerups, and trigger objects like doors and portals.
You can add this kind of trigger objects as follows:
Code:
shape = levelColmesh.addTrigger(shape, colFunc*, rayFunc*);GMS 2.3 allows you to pass functions by reference. That means that you can create custom functions that should be executed instead of the regular collision response.
Demo 1 showcases how you can add collectible coins to a 3D level. The coins will send their collision shape a function that will increment global.coins by 1, play a sound, delete the coin object and remove the shape from the ColMesh.
The code for this looks like this:
Code:
//Create a collision function for the coin, telling it to destroy itself and remove its shape from the level ColMesh
colFunc = function()
{
global.coins ++; //Increment the global variable "coins"
instance_destroy(); //This will destroy the current instance of oCoin
levelColmesh.removeShape(shape); //"shape" is oCoin's shape variable. Remove it from the ColMesh
audio_play_sound(sndCoin, 0, false); //Play coin pickup sound
}
//Create a spherical collision shape for the coin
shape = new colmesh_sphere(x, y, z, radius)
//Add the coin to the ColMesh as a trigger
//The collision function will be executed if the player collides with the coin, using colmesh.displaceCapsule.
levelColmesh.addTrigger(shape, colFunc);This is useful for objects that should only collide with the world and not trigger game objects.
Non-solid objects are NOT saved when using colmesh.save or colmesh.writeToBuffer.
Saving and loading
You’ll typically want to precompute your ColMeshes. Generating and subdividing a ColMesh can be a slow process, so luckily you can easily save and load them to and from buffers.
If you don’t want to include the precomputed ColMeshes, you could generate them the first time they’re needed, and then cache them in local files like this:
Code:
levelColmesh = new colmesh();
if !(levelColmesh.load("ColMeshCache.cm"))
{
//If a cache does not exist, generate a colmesh from an OBJ file, subdivide it, and save a cache
levelColmesh.addMesh("Level.obj");
levelColmesh.subdivide(130);
levelColmesh.save("ColMeshCache.cm");
}Planned features
These are some shapes that are planned:
- Halfpipe/partial hollow cylinder
- Bowl/partial hollow sphere
- Planar heightmap
- Spherical heightmap
- Other kinds of heightmaps?
- Subtractive shapes, so that you can “cut away” parts of primitives.
- Physics simulations
- Combining ColMesh and SMF to create ragdolls
Thank you!
Feedback is always appreciated.
Snidr
Last edited:
