Laser Cutting — Tech secrets of a top charts game!
Our game Laser Cutting has been downloaded more than 8 million times.
To celebrate this milestone, and because we saw that the Unity developers community would like to know more about how we achieved real-time mesh cutting (cf this reddit post), we wanted to write and share a more in-depth tech guide on how the game works.
In Laser Cutting, you are able to freely use a laser to carve in real-time into a 3D surface. When you create an “island” (i.e., cut a complete loop, or from one end of the surface area to another), it needs to be removed from the surface and fall off. When the player is done, they are presented with a screen that computes their accuracy.
We have just described three different problems that will be tackled in this article:
- How to carve into a mesh
- How to detect islands and make them fall off
- How to give the player an accuracy score
Let’s dive in together!
Problem Solving #1 — Carving into a mesh
Starting with a simple grid
How is this achieved? The answer is procedural meshes. The difference between a traditional mesh and a procedural mesh is that the former is usually designed into a 3D modeling software, while the latter is created entirely from code. How do we create a mesh with programming lines, you might ask? To understand this concept, you will have to remember one thing: a mesh is just a bunch of vertices (positions), joined together to form triangles (vertex indices).
This is a very simple procedurally generated 20x20 grid of squares, each square being 2 triangles. There are 21x21 different positions — (0;0) (0;1) (0;2) etc. up to (20; 20) — joined together to form 400 squares, thus 800 triangles. Think of it as a grid of pixels: the more squares you have, the finer the resolution. This process in 3D modeling is called tesselation. A naïve way of carving into this mesh is to simply remove triangles.
Marching squares and marching cubes algorithms are based on this concept of having a grid to fiddle with. Marching squares is executed in 2D space, while marching cubes is executed in 3D space. However, a very simple mistake can be made here: while the rendering of the surface has a 3D depth, this doesn’t mean we need marching cubes! Let’s say we are working on a 2D grid forming a surface on the (X,Y) axes: when we carve at a point, we carve a circle all along the Z axis, consequently carving a cylinder shape. We can then simply work with a 2D grid and add vertices further on the Z axis to create this depth effect
Marching cubes is only useful if we want to carve spherical shapes into a volume, which is not what we are trying to achieve here (a great example of what marching cubes can achieve is Sebastian Lague’s Coding Adventure).
Above is the same 2D grid we have seen earlier, with vertices added further on the Z axis to create the depth of our volume.
Marching Squares
Under the hood of marching squares, is a floating point value assigned to each vertex in the grid telling how much “matter” there is around this vertex. You can choose your own conventions regarding this value. For this example, let’s say this value is how much “ground” there is around this vertex. As long as the ground value is > 1, there will be ground. The goal of marching squares is then to find the isoline with value 1 that will delimit surfaces with value > 1 and with value < 1.
For example, this is what an island looks like.
You can also see the effect of this floating point value on the final mesh, removing triangles or moving vertices depending on the surrounding values of each grid pixel… but we are getting ahead of ourselves; this is the final result. There are already tons of great marching square tutorials out there, so I won’t go into very precise details. Let’s just dive straight into the major steps to get there.
Step 1 — Identifying broad cases
Each square in the grid has 4 corners. Assign each corner a “case value” from {1,2,4,8}. If a corner has a value superior or equal to the isoline threshold (1 in our example), the corner is considered “active” (black in the following example), otherwise it is considered “inactive” (white in the following example).
To compute the case value of a square, sum the case values of each active corner. There are 16 different case possibilities then — you will get the following results (gray being “no ground” and orange “ground”):
For each of these cases, add triangles to your mesh corresponding to the orange surface.
There are multiple ways to triangulate each shape, but here are some examples in case you are struggling!
Step 2 — Carving the surface
The problem we are trying to solve is: how do we carve a disk of radius R at coordinates (x, y) into this surface?
The first, simple version, is to get all the vertices of the grid which are at distance < R from point (x, y) and set their value to 0.
You will end up with something rather blocky, one of the reasons being that the operation is quite binary: either you’re inside the disk and your value is zero, or you’re not and you keep your old value.
A much smoother way is to set the value of each vertex linearly depending on their distance from point (x, y). This will gradually set the value of each vertex, giving much more space for interpolation, which happens to be our next step.
Step 3 — Interpolation
The blocky look of our surfaces is kind of breaking the illusion that we are carving a disk. We could of course increase the resolution of our grid to a point where pixels are so small that the effect will fade… but this would bring your hardware to its knees! Remember that the mesh has to be rebuilt every time it is modified.
If you only use the binary statement “Vertex Value > 1” versus “Vertex Value ≤ 1”, you get all 16 shape variations, each showcased above as the 16 cases.
However, if you only use this statement to determine if a vertex is active or inactive and under which of the 16 cases the shape falls, you can then use the full range of the floating point value. Each of the 16 cases mentioned above has an infinity of variations depending on each vertex value:
Result
And voilà! Time to carve!
Problem Solving #2 — Fall away!
Connected Component Labeling
We now want to have some parts of the surface fall off. Most of this is achieved using an algorithm called Connected Component Labeling. The Wikipedia article explains it very well: the basic idea is to identify islands into a grid, depending on their value. Which value? The value that we computed above! The exact same value that was used to compute the shape can be used to determine on which island each vertex is sitting.
In this example, Label 0 will be set on each pixel that has a value < 1. This is our “sea level”. Each pixel that has a value ≥ 1 is sitting on an island.
We ended up using the two-pass algorithm as it gave better performance overall.
Make islands fall off
Now that you have labeling operational, the idea is simple: when the player carves, each carved pixel has a label of 0 while the rest of the level has a label of 1. The instant a second label appears, an island has been created, and one of the two islands has to fall off. Which one? For now, let’s just say “the smallest one”, but that will not work for the game. We’ll keep this issue for part #3!
We ended up with a quite brutal but efficient solution to actually make the island fall off: set the value of every pixel that is part of the island that will fall off to 0 in the main grid, and create a second smaller marching squares grid which has a value of 0 everywhere except on the pixels of the falling island (these will get their original value instead). Add a rigid body to the falling island, and there you go: your island goes away!
Problem Solving #3 — Scoring
And now onto our final problem for today: scoring. How do we know how accurate the player was? To understand that, let’s analyse how levels are designed.
Anatomy of a level
On the left is how the level looks like in game, while on the right is the actual sprite that has been designed for the game. Each R/G/B color channel is important for different reasons.
- The green channel will be used for dotted-line rendering. Each material in the game (wood, stone, gold…) has a different color for the dotted line, and the green channel of the level sprite will be colored using that material’s color.
- The blue channel was added later on in the game development process and is used for control snapping. We discovered that players felt the game was too hard at times. Thus, they have the option to toggle snapping on and off, allowing them to follow curves more precisely.
- And last but not least, the red channel is the one used for scoring! Imagine that the level sprite is actually mapped on top of our 2D grid, giving each vertex in our grid a red channel value to play with. The following rules are then applied regarding this value:
- Vertices that have a red value of 1 (fully red) are where the player will increase their score. These vertices need to be there at the end of the level: the player will be rewarded with a score point for each of these vertices during score computation. This gives us two things: the maximum score that is achievable on this level (perfect shape), and the base score for the player.
- If a fully red vertex is missing, a penalty is subtracted from the player base score for each missing vertex.
- A vertex that has a red value of 0 needs to be removed by the player. If not, same process: score penalty for the player.
- A vertex that has a red value of 0.5 (close to the border) has no effect on the score. This is done to give a little leeway to the scoring mechanics.
We now have a score for the player, and the maximum score achievable, giving us a percentage of accuracy.
Coming back to falling islands
Remember how we did not know which island should fall off in problem #2? Well, this is where we solve this issue. When a complete cut is made by the player, and two islands appear, compute the score on each of these two islands. The island with the smallest score is the one that should fall off.
Here is an example, showcasing the overlay of the level sprite on top of the actual in-game level. If the player cuts along the black border, two islands are created: A and B.
The score of B is much higher than the score of A, since B contains a lot of scoring vertices. The result is clear: A falls off!
Conclusion
At Dual Cat, we love to have technical challenges to overcome in each of our games. It keeps everyone motivated and eager to learn.
There’s a bunch of other things that could be said about the game that I haven’t mentioned here, especially how these algorithms were optimized to make sure they ran on as many devices as possible, but maybe that’s a subject for another article.
In the meantime, thanks for reading, and don’t hesitate to comment if you have any questions or feedback.
Laser Cutting by Dual Cat is available in all countries on both iOS and Android
