The objective is to make a Boss that is destructible like one would carve/destroy a block of marble, possibly with a state machine that allows it to behave differently depending on how much and what parts of the boss are destroyed. When the boss is hit with an attack it carves out a part of the boss at the location where it was hit, using mesh slicing, eventually completely destroying the boss.
Week 1: Splitting meshes in two parts
The first challenge is to the mesh slicing code to be able to deform a mesh and turn it into multiple objects, to start out I did some research on programs and packages there are to achieve this. I found the repository EzySlice which I will be using as a reference.
Splitting up triangles
To start out we are going to slice a mesh into two parts along a plane, to achieve this we iterate over the triangles and for each vertex we check whether on what side of the plane it is located, the triangles that are fully on one side of the plane get moved to the respective arrays.
For the triangles that get sliced by the plane we need to find the intersection points and use these points to divide the triangle up into three new triangles that can be placed on either side of the plane.
To find the intersection between a line and a plane we can use the following equation:
After implementing this in code we get the following result:
Generating new UVs
In order to ensure compatibility with textures, the newly created vertices must be assigned UV coordinates. To achieve this, we can use a calculation that is based on the percentage difference in distance between: the two original vertices, and the vertex generated for the new triangle. Using this percentage, we can interpolate the UV coordinates in between the two original vertices. This interpolation ensures that the textures align correctly with the newly generated geometry.
Filling in the center
Next up we need to generate two new faces to fill in the holes after being sliced, to do this we can take the average position of the newly generated vertices and draw triangles between these vertices to create a flat surface along the slice.
Week 2: Slicing shapes out of a mesh
This would suffice if the goal was to split an object in two, but if we were to implement this into a bossfight it would be over very quickly, so instead of cutting a mesh in two we need to take a chunk out of the mesh.
Combining planes
The fastest way to create shapes we can use to cut would be to use a combination of planes to create a rudimentary version of a mesh. This will also allow us to reuse the code for the plane intersections
If we take a sword as our weapon of choice we can take a wedge out of the mesh. This wedge can de defined by two planes that are slightly angled. The vertices that need to be removed are between the point of impact and the intersection point of the planes, above the lower plane, and below the upper plane.
One option to achieve this is to make two consecutive cuts with planes and reattach two of the resulting parts, this would allow us to use the plane mesh slicing.
However a more efficient way to do this is to slice with both planes at the same time. For this we will need a little more logic.
The planes cut the space into four sections. If the planes are facing toward each other we can use the plane.GetSide(Vector3 point) function build in to detect in which of the section the vertex is located, if it is on the positive side of both planes it is inside the wedge, otherwise it is in one of the other sections.
The current code splits the mesh into two parts, the wedge and the rest of the mesh, however it is also possible for the wedge to cut the mesh into more than two parts. To account for this we need to know if the parts of the original mesh above and below the wedge are still connected.
By checking if there are vertices in the section opposite of the wedge we know whether the wegde cut through the mesh completely or only partially. The vertices that are in the section opposite of the wedge are on the negative side of both of the planes.
Week 3: Mesh Collisions
Constructive Solid Geometry
One method to simplify the mesh collisions would be to use Constructive Solid Geometry (CSG) it uses the addition and subtraction of primitive shapes to create new geometry.
CSG is mostly used as a prototyping tool for level design because using it at runtime is very performance heavy but if we use primitve shaped the performance will be better than using any regular mesh.
CSG uses convex shapes or combinations of convex shapes because it is a lot simpler and less performance heavy than using concave shapes.
Checking if a vertex is inside another mesh
One of the algorithm we need is to check whether a vertex is inside of another mesh, we can do this in two ways, the first assumes that the mesh we are checking against is convex, we use the plane.GetSide() function for every triangle in the mesh and if it is on the negative side for all of them the point is inside.
If we want to add support for concave shapes we need a more complex algorithm this video from Inside Code explains how it works if you cas an infinitly long ray in a random direction and the ray has an odd number of intersections it is inside the mesh, for the raycasting algorithm we are going to use the ray triangle intersection algoritm from the next paragraph.
Triangle-triangle intersection
Simple planes are sufficient for weapons like swords and axes but if you want to deform the mesh in more complex ways for example when stone is hit with a hammer, it would be a lot of work to do with just planes.
The ideal way to do this would be to create a “brush” mesh and use triangle intersection to create a mesh collision algorithm. We do have to keep in mind that this will have a larger impact on performance especially if we use brushes with a lot of triangles.
To achieve this we need a performant algorithm for triangle-triangle intersection. We are going to use the Möller en Trumbore (2005) Ray Triangle intersection algorithm. In Baldwin and Weber (2016) it is stated that their algoritm is 6% faster that Möller Trumbore but Möller Trumbore had the source code in their paper and i was able to find a comprehensive video by enigma tutorials explaing the paper and the code.
It works by calculating the barycentric coordinates of the intersection, if one of the coordinates is above 1 or below 0 it falls outside of the triangle.
If we first find the vertex in the triangle that is alone either inside or outside the brush we can send two rays from this vertex to the other two vertices to find where the intersections lie;
With this code however i had the problem that the rays would also intersect with the back side if the brush enabling culling would not work because the rays originate from both inside and outside the brush.
To prevent this I added an extra check that makes sure the intersection point lies between the origin and end point of the ray.
Week 4: Intersection Cases
The triangles that make up two meshes can intersect in a lot of different ways, and most of these ways need their own seperate logic to add new triangles here are a few examples:
Here are some examples of the implementations
I had a lot of trouble at first finding all of the different types of intersections because it was very hard to see where exactly all off the vertices are and how they connect with triangles, to solve this I spawn small spheres at the positions of the vertices and draw where the edges of a triangle collide. This helps identify bugs and solutions.
Filling up the inside
Next we need to fill up the empty hole left behind by the intersection, to do this we are going to move find the vertices of the brush that are inside the target and add them to the target mesh;
This is mostly the same as we did with cutting out the brush from the mesh but we need to make sure the triangle are in reverse order so they are facing outward.
Performance
The current algorithm works well with simple shapes but if we use more complex shapes with a lot of triangles it is very slow. On a PC with a Intel I7-12700k and a NVIDIA RTX 3070 it takes 27 ms to perform an intersection between a sphere and a cube and 668 ms between two spheres, if we want to apply this in real time that has to be improved to at most ~50 with the two spheres so the operation can be hidden with special effects.
After adding a timer and saving the times after each step we can confirm which steps need to be optimized the most.
The “Init” step is where the data gets assigned to the proper structures, this also includes checking each vertex whether it is inside the opposite mesh. This is the second highest contributor.
The “Intersects” step is where all of the intersection calculations are done.
The intersections themselves are already calculated with a highly optimized function so to improve performance we need to reduce the amount of intersections checked. We are going to do this by only calculating the intersections for triangles that are likely to intersect instead of all of them.
Hierarchical Hash Grids
First I tried implementing Hash Grids to solve the performance issues. This solution uses a grid of same size cells that each contain a list of triangles that intersect with the cell, this allows you to add a triangle to the grid and only check the triangles in the cells that contain the triangle. In terms of performance it worked perfectly reducing the time the intersections take by ten times.
In my implementation I make two grids, one for the triangles in the target mesh and one for the triangles in the brush mesh, then for each triangle in one mesh i check against the grid with the triangles for the other mesh.
To add a triangle to the cells that contain it we get the minimun and maximum values for the points in the triangle and use those to create a bounding box, every cell in that bounding box is assigned the triangle. It is important to set the right cellSize, a cellSize too large and you will not have much performance benefits and with a cellSize that is too small you will take up more memory and some intersections will be missed because the triangles are too large in comparison to the cells. For me a cellSize dependant on the scale of the mesh worked well.
To store the cells and triangles within the HashGrid class we use a Dictionary, when you use a custom class in a dictionary you can lose a lot of performance to checking the keys against each other and generating the hash codes, to limit this performance loss we can implement our own GetHashCode() and Equals() methods.
Hash grids can also be used to improve the performance when checking whether a vertex is inside the other mesh. The only thing we have to change is to add a new function that checks a ray against the cells in the grid instead of a triangle. the ray we draw to check each vertex starts at a vertex and points directly right, so we only have to check the cell the vertex is in and all of the cells in a line to the right.
After implementing all of this I was still unable to reach the target of 50 ms for two spheres, however the total time has been cut down to 150 ms, this should be possible to hide by putting the slice method in a coroutine and adding some effects over it.
Week 5
Detatching newly cut meshes
After cutting into a mesh there is a chance the mesh gets cut in half completely, when this happens we want the original mesh to be split into two parts, to achieve this in a very performant way we can use the logic for slicing along a plane we made earlier to cut the mesh in half.
To determine whether the mesh is cut in half we can use the same method as when determining if a vertex is inside of a mesh, if the frontmost vertices from the brush hit and even number of faces when raycasting along the direction of the cut it is outside and so the mesh has been cut in half, we then make a plane split the two parts of the mesh and place them in seperate objects.
Adding a different texture on the inside
At the moment the inside of the cut has the uv coordinates of the mesh that was used to cut and the texture of the original mesh. In practice this look really odd, to fix this we are going to add the inside of the cut as a new submesh so we can change the texture of the inside to whatever we want. One thing we need to be carefull off is to add the new vertices generated by the intersections to both the original mesh and the submesh and keep track of them in seperate arrays so we can give them seperate uvs.
More Performance
Last week I greatly increased the performance of the operation by adding hash grids however the performance still isn’t ideal as it still takes ~150 ms to subtract two spheres, to further increase the performance we can add CPU multithreading, for the intersections and side calculations we use a lot of loops to go through every vertex and triangle but the program would run a lot faster if we could do multiple calculations at the same time. Using this method I was able to achieve ~50 ms on the previously mentioned specs.
Conclusion
In the end I was able to create a mesh slicing system that can cut the negative of one mesh out of another much like the subtract operation used in CSG. I wasn’t able to achieve the complete performance benchmark but the performance was good enough to be able to hide the operation with special effects.
The biggest challenge I faced in the creating of the mesh slicing system was the fact that there were very few substantial sources I could use to guide me through the creation. There were a few superficial explanations of the concept, for example the GDC presentation on CSG but no actual examples or sudo code.
I did not have enough time to implement this system into a bossfight which was the initial goal so I would like to complete this in the future.
Sources
- Möller, T., & Trumbore, B. (2005). Fast, minimum storage ray/triangle intersection. ACM Digital Library. https://doi.org/10.1145/1198555.1198746
- Doug Baldwin and Michael Weber, Fast Ray-Triangle Intersections by Coordinate Transformation, Journal of Computer Graphics Techniques (JCGT), vol. 5, no. 3, 39-49, 2016 Available online http://jcgt.org/published/0005/03/03/
- GDC Constructive Solid Geometry https://www.youtube.com/watch?v=Iqmg4gblreo&list=PL1xkonPEvEiEtNtjgmAPWc8Gtc6tt4lNY
- Enigma tutorials Möller Trumbore explained https://www.youtube.com/watch?v=fK1RPmF_zjQ
- Inside Code Is a point inside of a polygon? https://www.youtube.com/watch?v=RSXM9bgqxJM
- Hierarchical Hash Grids https://www.youtube.com/watch?v=sx4IIQL0x7c
