Tech Research: Mesh Splitting (Patreon)

I haven't made a tech research post in a long time. I thought i'd make one on the tech for the cooking update, cutting fruits. These posts can get pretty technical but I hope you like reading it.

Quick demonstration:

The mission is to find all the points on the cutting plane that slices the mesh into 2 parts, the right and left parts. Then, we create the 2 meshes and fill in the interiors with another mesh for the filling. However, this is easier said than done and there are a plethora of strategies one can go about solving this.

First, we have to talk about the domain that we will work with, aka, the type of geometry that we will cut. This is because mesh splitting can get super intense depending on the type of geometry. I'll go over why later but for now we are looking at cutting fruit:

The average shape of a fruit is a sphere (thankfully), and usually has no holes inside (thank GOD). Therefore we can set our parameters to work with convex meshes only. The why will be explained further down.

The second thing we will do is to iterate through every triangle of the mesh and test it for intersection with the slicing plane:

The yellow is where the plane knife passes through and the red triangles are the ones marked for intersection. Finding which triangles to test for intersection is easy, simply check if the 3 points of the triangle are on the same side of the plane. Example:

The 3 points of triangle C are on the same side of the plane and as we can see it doesn't intersect with the plane, so we can ignore it. But triangle A has 1 triangle on one side of the plane and 2 points on the other side, meaning it is intersecting. So now that we know that it is intersecting with the cutting plane, we find the 2 points where it is being intersected. Thankfully Unity comes with some plane functions to find these points. We are interested in axb and cxb of the triangle:

The first big problem for mesh splitting is building a graph of edges that represents the cross section of the mesh we are splitting. In other words, as the yellow line slices the geometry, points like axb and cxb are building a ring around the mesh. This should be a nice long array of ordered points. The problem with meshes is that we will never traverse the geometry in order because mesh triangles are randomized like so:

This means that the array of points around the mesh will be built in pieces and we need to connect them. What I did to solve this was create a dictionary that maps a 3D location to a node class. This allowed me to look up where an intersection point lived based on a 3d location. Therefore I could connect points like axb and cxb based on neighbor locations:

After we've traversed through all triangles and found the ring around the mesh where we  split into 2 parts, we can create the 2 resulting mesh halves:

Now comes the filling, triangulation. We have built our array of points from the dictionary that goes along the mesh. These points look like this from above:

Now I can talk about the importance of convex vs concave vs holes dilemma. Convex shapes (those that are just round and don't have indents), have a very easy O(n) algorithm for triangulation, meaning I can build it very fast with a single for loop by just traversing every point like a fan:

If the array of points were concave, it would be far more complicated to make an efficient algorithm and the fan triangulation wouldn't work:

There are alternative algorithms such as ear clipping (O(n^2)) and even more complex algorithm's like Seidel's (O(nlogn)), but we don't need to worry about them since we are working with nice convex fruits. That's why it's important to analyze your domain before working on algorithms. Less burden and faster results.

So my first results were the following:

One problem with this type of topology is that adding more cuts to it made meshes with tons of triangles:

This is problematic because it made every subsequent cutting take longer than the last one. This is not ideal for VR performance. A quarter cut melon made the following mesh:

263 triangles. I tasked myself with a way to simplify the meshes. We can't do much about simplifying the base sphere mesh that we start out with (without getting to involved anyways), but we can change how we are filling in the interior parts of the fruits which is the bottleneck and source of the crazy topology. Therefore I moved from a fan triangulation to a zig zag pattern.

And now when I add more cuts, it produces better results. Still not pretty but far better:

This lowered the triangle count result to the following:

Down to 213 tris. Still very heavy because again, every triangle needs to be traversed if I were to cut this piece into another smaller piece. However, I noticed that there were points of the filling that weren't needed. I could ignore points that lied on the same line:

This was as best as I could clean up the filling and it brought down the final mesh benchmark down to the following:

166 triangles. Far better than what we start out with 263 triangles. I'm not too worried about performance since cutting functions are ran once every few seconds (or whatever speed the user will use the knife).

This was where I finished my algorithm. I hope to start implementing it soon after I finish a few other stuff with the canyon. It will be part of v0.7 and hopefully part of the v0.7c beta. I don't know when that beta will come out but maybe in 2-3 weeks.

That's how we cut fruit with C#.