Procedural Mesh Slicing

Jasper van den Barg

26-10-2020

Foreword

After the 3D meshes bootcamp I was really amazed by the possibility to generate my own meshes inside Unity and I was wondering if I could also alter existing meshes as well. I was really interested to see if I would be able to make a game object shatter on impact or explode into multiple pieces.

This object destruction had to be procedural so it would be different every time depending on the situation. This meant I couldn’t just take an object, make a copy of it, divide it into multiple pieces using 3d software, and replacing the original object with the broken object each time it had to be destroyed. This would mean the object would break exactly the same way each time. To make the object destruction procedural I somehow had to calculate new pieces that would shatter the object.

Having no idea where to start the easiest thing to do for me was to simply slice an object in half. This is the first thing I started with. After finding out the mesh slicer I created could only slice convex meshes I put a little research into slicing concave meshes and I came to the conclusion this would be very challenging. Thus I decided to keep focusing on slicing concave meshes and changed the subject of the research from procedural object shattering to procedural mesh slicing.

Contents

  1. Preface
  2. Understanding meshes
  3. Mesh slicing setup
  4. Convex meshes
  5. Concave meshes
  6. Results
  7. Future references

1. Preface

This paper explains how to slice meshes in Unity during runtime. There are two different type of meshes discussed in this paper, these include convex and concave meshes. The paper explains how to slice both of these different meshes. The mesh slicer is able to provide clean meshes at the cost of frame time or ‘uncorrected’ meshes at the cost of vertex count.

The project was built in Unity2020.1.2f1. Meshes can be sliced in both scene and play mode with the Knife prefab provided. To slice an object it must be placed on a separate layer ‘Sliceable’ and this layer must also be selected on the Knife prefab.

The mesh slicer is able to slice simple convex meshes, simple concave meshes, concave meshes with holes, concave meshes consisting out of multiple parts, and meshes such as planes/quads. The mesh slicer is not able to slice boned meshes.

2. Understanding meshes

Image 1

Meshes contain vertex data (positions, normals, texCoords etc.) and “face” data, with faces most often being triangles. On the right a game object can be seen in shaded wireframe mode. This allows you to see the vertices and triangles, as well as the light hitting the object (normals) and the color/texture of the object (uv) (Unity, 2020).

Conceptually, all vertex data is stored in separate arrays of the same size. For example, if you have a mesh of 100 Vertices, and you want to have a position, normal and a texture coordinate for each vertex, than the mesh should have vertices, normals, uv arrays, each being 100 in size. Data for i-th vertex is at index “i” in each array (Unity, 2020).

The mesh face data, i.e. the triangles it is made of, is simply three vertex indices for each triangle. For example, if the mesh has 10 triangles, then the triangles array should be 30 numbers, with each number indicating which vertex to use. The first three elements in the triangles array are the indices for the vertices that make up that triangle; the next three elements make up another triangle and so on (Unity, 2020).

When it comes to mesh shapes there are essentially two different kinds of shapes: convex and concave.
A convex mesh is a mesh where all vertices have an interior angle less than 180 degrees and a concave mesh is a mesh which has at least one interior angle greater than 180 degrees. The interior angle is the angle between a vertex and its adjacent vertices directed to the inside of the mesh/polygon.

Image 2

3. Mesh slicing setup

To slice any meshes I have decided to use an empty game object on which the slicer script will be located. This empty game object will be referred to as a ‘Knife’, because knifes cut things. The knife shoots out multiple rays at an angle to detect any sliceable objects in its path. The knife contains a few variables which can be adjusted such as ray length, cast angle and the amount of rays to be cast. These rays pick up any object that is inside the ‘Sliceable’ layer, multiple objects can be picked up at the same time.

Image 3

If an object is detected to be sliced there are a few steps we need to take to go from object1 -> slice1,slice2:

  1. Get the mesh data from the object (vertices, normals, triangles, uv).
  2. Create a Plane in the direction the Knife is angled and goes through the point the mesh was hit at.
  3. Iterate over all the triangles of the original mesh and check on which side of the plane the vertices of that triangle are located.
    1. If all vertices are located on the positive side of the plane: add the triangle data to slice1.
    2. If all vertices are located on the negative side of the plane: add the triangle data to slice2.
    3. If one or two vertices are located on the positive side of the plane: calculate new vertex data and add triangles to slice1 and slice2 according to the location of the vertices inside the triangle.
  4. Triangulate the polygon that consists out of the newly calculated vertices.
  5. Build two new game objects out of the new mesh data we calculated.

Because steps 1, 2, 3 and 5 are the same for convex and concave meshes these will be explained here as well as step 4 for convex meshes but step 4 for concave meshes will be explained in the next chapter.

4. Convex meshes

Because steps 1, 2, 3 and 5 are the same for convex and concave meshes these will be explained here aswell as step 4 for convex meshes, step 4 for concave meshes will be explained in the next chapter.

4.1. Getting the mesh data and creating a plane

Whenever we tell our Knife to cut, it shoots out a bunch of rays and returns an array with all sliceable objects that were hit. From each hit object we collect the mesh data (vertices, normals, uv, triangles) and store this in a SlicedMesh object that we call “unslicedMesh”. For this unslicedMesh we create a plane with the normal of our slicing direction that goes through the point where the mesh was hit. A plane is a Unity structure that represents a plane in 3D space. With the structure comes a bunch of handy features we will use later on. When we create this new plane we need to take into account that the rotation of the plane and the hit location of the mesh are in world space, but the location of the vertices in the mesh are in local space. Because of this we need to make sure we also create our plane in the local space of the mesh we hit.

4.2. Slicing the mesh

When we use the plane to slice the mesh we need to make two new meshes, one new mesh for the part that is located on the positive side of the plane and one new mesh for the part that is located on the negative side of the plane. We can do this by iterating over all the triangles in our unslicedMesh and check on which side of the plane each vertex is located. To do this we use the function plane.GetSide(vertex). This function returns true if the vertex is located on the positive side of the plane and false for the negative side. We save this bool for each vertex so we can calculate how many vertices are located on each side of the plane. If there are three vertices on the positive side of the plane we need to add the entire triangle plus the corresponding data to the positive slice, if zero vertices are located on the positive side of the plane we need to add the entire triangle plus the corresponding data to the negative slice, else we need to calculate new data and add the new triangle(s) to the correct side. (DitzelGames, 2019)

In case one of the vertices is located on a different side than the other two vertices we cut a triangle and need to calculate new data for our cutting points. To do this we first need to know which vertex is located on which side of the plane. For this we can use the information from our plane.GetSide check we did earlier to get our new indexing.

With this indexing we can get the data of the triangle we cut with our plane and use this data to calculate our new data (new vertices, normals and uvs).

//determines which vertex in the triangle is solely located on one side of the plane
int singleIndex = sideB == sideC ? 0 : sideA == sideC ? 1 : 2;
int indexB = t + ((singleIndex + 1% 3), indexC = t + ((singleIndex + 2% 3);
singleIndex += t;
 
//calculate which vertices/normals/uv should be used to calculate intersection points
Vector3 singleVertex = original.vertices[originalTriangles[singleIndex]],
        vertexB = original.vertices[originalTriangles[indexB]],                 //right vertex
        vertexC = original.vertices[originalTriangles[indexC]];                 //left vertex
Vector3 singleNormal = original.normals[originalTriangles[singleIndex]],
        normalB = original.normals[originalTriangles[indexB]],
        normalC = original.normals[originalTriangles[indexC]];
Vector2 singleUv = original.uv[originalTriangles[singleIndex]],
        uvB = original.uv[originalTriangles[indexB]],
        uvC = original.uv[originalTriangles[indexC]];
 
//calculate new vertices/normals/uv where edge intersects plane
float lerpB, lerpC;
Vector3 newVertexB = PointOnPlane(plane, singleVertex, vertexB, out lerpB),     //new right vertex
        newVertexC = PointOnPlane(plane, singleVertex, vertexC, out lerpC);     //new left vertex
Vector3 newNormalB = Vector3.Lerp(singleNormal, normalB, lerpB),                //lerp to get the point between the old vertices where the new vertex is located
        newNormalC = Vector3.Lerp(singleNormal, normalC, lerpC);
Vector2 newUvB = Vector2.Lerp(singleUv, uvB, lerpB),
        newUvC = Vector2.Lerp(singleUv, uvC, lerpC);

To calculate the location for our new vertices we use the PointOnPlane() function. This function takes in a plane, two vector3 and returns a vector3 and a float. The new vertex is calculated by raycasting form the singleVertex to Vertex(B/C) throught the plane. This returns a distance from the singleVertex to our plane and we simply add this distance to our singleVertex to get the position for the new vertex. The function also returns a lerp which it uses to calculate the new normals and uvs.

private Vector3 PointOnPlane(Plane _plane, Vector3 v1, Vector3 v2, out float lerp)
{
    Vector3 direction = (v2 - v1);
    Ray ray = new Ray(v1, direction.normalized);
    float distance;
    _plane.Raycast(ray, out distance);
    Vector3 v3 = v1 + (direction.normalized * distance);
    lerp = distance / direction.magnitude;
    return v3;
}
Image 4

With this new data we can build our new triangles. Let’s say we cut the triangle as demonstrated in the image 4. We cut triangle ABC with our plane which results in a cut where A is located on the positive side of the plane and B and C are located on the negative side of the plane. Since there is one vertex located on the positive side of the plane we need to make one new triangle AnewBnewC. There are two vertices located on the negative side of the plane so we need to make two new triangles BCnewB and newBCnewC. We add these new triangles to our new slice.

4.3. Triangulating the slicing plane polygon

Because unsliced mesh is convex the polygon that results from the slicing plane (or new vertices) is also a convex polygon (and the new slices are also convex). Convex polygons are fairly easy to triangulate. We can simply do this by taking one of our new vertices and build new triangles between this vertex and all the other new vertices. The resulting cut can be seen in image 5.

Image 5

4.4. Creating a new game object

Image 6

Before we create a new game object from our new mesh data we need to correct a problem we created. Whenever we add a new triangle we give each triangle individual vertex data. This results in a lot more data than we need for our new game object. Let’s say we cut the quad in image 6. For the positive side we need to add the following new triangles to the slice: ABE, BDE and BCD. If we add these triangles together we get the following Amount of vertex data A3BC2D2E, while we only need vertex data ABCDE. Because of this we need to correct vertex and triangle data of our slice before we build the mesh and make it a game object. We do this by building a new list with data, iterating over the old data and checking if our old data is already inside our new data.

To build a new game object of our new slice we need to:

  • Create a new game object with the transform of the unslicedMesh
  • Create a new mesh with the data of our slice.
  • Add a mesh filter to the game object and add the mesh to this mesh filter.
  • Add a mesh renderer with the material of the original game object.
  • Add a mesh collider.
  • Add a rigid body.
  • Set the layer of the game object to sliceable.

5. Concave meshes

Image 7

When slicing a concave mesh we need to take a different approach on triangulating the polygon resulting from our mesh. for this we need to take into account three different type of cuts that can result from our slice: a simple concave polygon, a concave polygon with a hole in it, separate polygons or any combination of these three.

5.1. Creating a polygon

The first thing we need to do is build a polygon(s) from our slice, the only problem is that we don’t know in which order our triangles are sliced, so when we draw a line from one vertex to the next it won’t give the correct polygon that resulted from our slice. To fix this problem we need to find out which vertices are connected to each other. To do this we use an Edge, an Edge is a line/edge of our polygon. This Edge has a start and end vertex. Whenever we slice a triangle we get two new vertices and with these new vertices we can create a new Edge and because we know in what direction the new triangles are build we also know what the start and end vertices of this edge are. With this information we can connect all edges in the following way: Edge1.endPosition == Edge2.startPosition -> Edge2.endPosition == Edge3.startPosition. If all edges are connected in the new list, but there are still edges in the old list a new new list is made.

From these list of connected Edges we can make a list of Polygons. For this we use the PolygonMetaData class, this class basically contains the same data as the Edge class except it only has the data of the start vertex of the edge and as an addition it also has the 2D position of this vertex. This 2D position is needed to check which polygons are holes and which polygons are not, it will also be used for different calculations in the triangulation algorithm. To get this 2D position we project our 3D position onto the plane we used to cut the mesh (Bunny83, 2018).

5.2. Holes and outlines

Image 8

Let’s say we end up with three polygons (p1, p2 and p3) when we slice our mesh we can end up with four different combinations of theses polygons. If none of the polygons is located inside of each other each polygon is an outline, if p1 is located inside of p2 p1 is a hole and p2 is the outline of that hole, if p1 is located inside p2 and p3 is also located inside p2 p2 is the outline of p1 and p2, but if p1 is located inside of p2 and p3 is also located in p1 but p1 is also located inside p3 then p2 is the outline of p3 but p1 is a separate outline. See image 8 for reference.

To find out which polygons are holes and which polygons are outlines we give each polygon an ID and a ParentID. First all holes are marked as outlines. Second we iterate over all outlines and check if ParentID of outline(i) equals ParentID outline(j), since this is the first iteration all polygons still have the same ParentID. If ParentID(i) equals ParentID(j) we check if one of the vertices of outline(i) lies within the entire polygon of outline(j). If the vertex lies within the outline the ParentID of outline(i) is set to the ID of outline(j) and outline(i) is marked as a hole. We use these same steps for all the polygons that are marked as holes, except whenever a hole(i) is located inside hole(j) the ParentID of hole(i) stays the same as it was before. These steps are repeated until there are no new outlines and holes discovered.

Image 9

To find out if polygon(i) is located inside polygon(j) we can take any given Point of polygon(i) and match it against the edges in polygon(j). This kan be done by casting a ray from Point to the right and counting how many edges of polygon(j) it intersects with. If and edge inside polygon(j) has a startposition.x or an endposition.x greater than Point.x that edge is a candidate to be intersected by the ray -> if this edge has a startposition.y greater than Point.y and an endposition.y less than Point.y or the other way around the edge remains a candidate to be intersected. For this candidate edge we need to calculate the x position at the point on the edge where y=Point.y. If this x position is greater than Point.x the ray cast from Point will intersect this line. If we count the amount of intersections the ray makes with polygon(j) we can find out if Point is inside polygon(j). If count is even Point is located outside of polygon(j), if count is uneven Point is located inside polygon(j) (meowNET, 2013).

public bool IsPointInPolygon(Vector2 point)
{
    bool inside = false;
 
    int polygonLenght = vertices2D.Count;
    for (int i = 0; i < vertices2D.Count; i++)
    {
        int j = (i + 1% polygonLenght;
        //if point.y lies between both y values of the edge it may intersect
        if ((vertices2D[i].< point.&& vertices2D[j].>= point.y) || (vertices2D[i].>= point.&& vertices2D[j].< point.y))
        {
            //get the direction vector to calculate the x position of the edge at the height of the point
            Vector2 direction = vertices2D[j] - vertices2D[i];
            Vector2 newPoint = point - vertices2D[i];
            float factor = (newPoint./ direction.y);
            if (newPoint.< direction.* factor && direction.!= 0)
                inside = !inside;
        }
    }
    return inside;
}

5.3. Triangulating algorithm

Triangulating a polygon is the action of filling a simple polygon with triangles. A simple polygon is a polygon consisting of ordered edges, where, if you traverse the edges the interior of the polygon is always on one side. So if the edges of a polygon are traversed counter clockwise the interior of the polygon is always on the left side of the edge. This means that edge can only intersect at the point of a vertex.

The triangulation method used in this paper is the ‘Ear Clipping’ method (Eberly, 2015). This method takes O(n^2) time, but with some clever thinking this can be done a bit more efficiently. There are faster algorithms out there which can triangulate polygons in o(nlogn) time, but these are harder to implement and might not deal with all the criteria our polygons meet, such as having holes inside of them. The Ear Clipping method was chosen because it is easier to implement and also deals with holes inside our polygon. This method allows to create an algorithm that can triangulate polygons with multiple holes in them. To use this algorithm in our mesh slicer we need six lists containing information about the vertices in our polygon:

  • List<Vector3> vertices3D: the 3D location of the vertices inside the polygon.
  • List<Vector2> vertices2D: the same list of vertices but their position project in 2D onto the slicing plane.
  • List<int> vertices: index of each vertex in the vertices2D/3D list.
  • List<int> reflexVertices: index of each reflex vertex in the vertices2D/3D list.
  • List<int> convecVertices: index of each convex vertex in the vertices2D/3D list.
  • List<int> earVertices: index of each ear vertex in the vertices2D/3D list.

The rules of this algorithm state the following:

  • The list of vertices must be ordered from one edge to the next.
  • If the polygon contains holes inside it the order of the vertexList of the holes must be the opposite direction of the vertexList of the outline. So if the outline vertices are ordered clockwise the vertices in the holes must be ordered counter clockwise.
  • A reflex vertex is a vertex whose interior angle between its two adjacent vertices is greater than 180 degrees.
  • A convex vertex is a vertex whose interior angle between its two adjacent vertices is less than 180 degrees.
  • An ear vertex is a vertex whose triangle formed between itself and its two adjacent vertices lies completely inside of the polygon. This means none of the vertices inside the polygon except for the vertices that make up the triangle itself are contained within this triangle. To make this a bit more efficient we only need to check the reflex vertices for containment since these are the only vertices that have a possibility to be contained within the triangle.

To find out if a vertex is convex or reflex create a plane using the Plane.Set3Points function to create a plane going through the vertex, the adjacent vertex before in the list and Vertex3.back. We then check if the adjacent vertex after the vertex in the list lies on the positive side of the plane or not. If that vertex lies on the positive side of the plane the vertex is convex.

public bool IsConvexVertex(Vector2 vL, Vector2 vM, Vector2 vR)
{
    if ((vM - vL).normalized == (vR - vM).normalized) return true;
    Plane plane = new Plane(vL, vM, Vector3.back);
    return plane.GetSide(vR);
}

To find out if a convex vertex is also an ear vertex we need to check for all reflex vertices if they are located inside the triangle that is made from the convex vertex and its adjacent vertices. This can be done by calculating the vectors going from point A in the triangle to point B and C. If both these vectors are positive and the sum of these vectors is equal or less than one, the point is located inside the triangle (Lague, 2017).

private bool IsEar(Vector2 vL, Vector2 vM, Vector2 vR)
{
    for (int i = 0; i < reflexVertices.Count; i++)
    {
        Vector2 P = vertices2D[reflexVertices[i]];
 
        if (P == vL || P == vR) continue;
 
        double s1 = vR.- vM.y;
        double s2 = vR.- vM.x;
        double s3 = vL.- vM.y;
        double s4 = P.- vM.y;
 
        double w1 = (vM.* s1 + s4 * s2 - P.* s1) / (s3 * s2 - (vL.- vM.x) * s1);
        double w2 = (s4 - w1 * s3) / s1;
        if (w1 >= 0 && w2 >= 0 && (w1 + w2) <= 1return false;
        else continue;
    }
    return true;
}

To start the triangulation we take the first earVertex from our list and draw a triangle between its adjacent vertices and remove the earVertex from the earVertices and vertices list. If an adjacent vertex was a convex it remains convex and we need to check if it becomes an ear or remains an ear. If an adjacent vertex was reflex we need to check if it becomes convex and if so if it becomes and ear. If an adjacent vertex becomes an ear we add it to the front of our earVertices list. Repeat these steps until the entire polygon is triangulated.

Let’s triangulate the following polygon. The polygon consisting of vertices {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} has reflexVertices {2, 5, 7, 8}, convexVertices {0, 1,3, 4, 6, 9} and earVertices {3, 4, 6, 9}.

Image 10

Let’s clip the first earVertex and draw a triangle between its adject vertices so we get triangle {2, 3, 4}. We remove this vertex form our lists so we end up with vertices {1, 2, 4, 5, 6, 7, 8, 9} reflexVertices {2, 5, 7, 8} convexVertices {0, 1, 4, 6, 9} and earVertices {4, 6, 9}. Now we need to check for the adjacent vertices if they have changed from their original state, vertex 2 was reflex and still is, vertex 4 was an ear and still is so the lists remain the same as above.

Image 11

Now let’s clip our next ear {4} and draw the triangle {2, 4, 5}. After removing the earVertex from the lists and updating the adjacent vertices we end up with vertices {0, 1, 2, 5, 6, 7, 8, 9}, reflexVertices {2, 7, 8}, convexVertices {0, 1, 5, 6, 9} and earVertices {5, 6, 9}.

Image 12

After taking the first ear {5} and clipping it we and up with vertices {0, 1, 2, 6, 7, 8, 9}, reflexVertices {7, 8}, convexVertices {0, 1, 2, 6, 9} and earVertices {6, 9}

Image 13

Let’s keep doing this for the remaining earVertices.

Image 14
Image 16
Image 17
Image 18

At last we end up with vertices {1, 7, 8} which are all convex and all ears. Connecting these last points in the right order gives us the triangulated polygon in image 19.

Image 19

In case our polygon has one or multiple holes inside of it we first need to attach this hole to the outer polygon by creating an edge inside of the polygon thus “closing” the polygon at that edge. To do this we need to look for the vertex inside the hole with the greatest x value and connect this to one of the vertices of the outer polygon. To connect this vertex to a vertex of the outer polygon we need to check for an edge that intersects with the ray cast from the hole vertex to the right and take the vertex in this edge with the greatest x value.

Image 20

In image 21 you can see how the new edge created inside the polygon connects the outer polygon with the hole. We insert the vertices of the hole into the list of vertices of the outline after the connecting vertex 11 starting at vertex 16 going counter clockwise until we reach vertex 16 again and go back to vertex 11. Note that vertex 16 and 11 are marked in the image as 18 and 19 and therefore must be added again at the end of the inserted vertices.

Image 21

Whenever we connect one of these vertices a check must be done to see if the connecting vertices are visible to each other. In image 22 a case can be seen where the edge P to intersection I is visible to the ray cast from vertex M to I, but the vertex P is not visible to M when casting a ray from M to P directly. Because of this possibility each edge from a reflex vertex (where x is greater than M.x) to its adjacent vertices must be checked for intersection (setchi, 2019). If an intersection occurs connect M to the vertex in that edge with the greatest x value, in this case vertex A. This holds the same for a polygon with multiple holes, where you need to connect the vertex in the holes with the greatest x value first. After doing this the hole becomes part of the outer polygon and another hole may even be attached to it.

Image 22

5.4. Slicing a concave polygon

To triangulate a concave polygon steps one, two and three of slicing a convex polygon are repeated. For each triangle we now slice (in step three) we also create an edge going from right to left (facing the polygon) and add this to a polygonCreator for each slice. After all the triangles have been checked the polygon creator connects these edges, turns them into polygons and checks which polygons are outlines and which ones are holes. The winding direction of the polygons that are holes is already opposite of the winding directing of the outlines since the triangles facing the inside of a mesh are already drawn in a different direction as those on the outside which results in our edges going in that direction as well.
Next the triangulator prepares this “raw” polygon data to be triangulated by the Ear Clipping algorithm. The triangulator created a ‘FinishedPolygon’ by triangulating each outline with its corresponding holes using the Ear Clipping algorithm and adding this data to the FinishedPolygon data. Keeping in mind that our mesh already has a certain amount of vertices inside it, the size of this list is added as an offset to the triangles. After all the polygons are triangulated and the data is added to the FinishedPolygon, the FinishedPolygon added to the SlicedMesh as a new sub mesh. Because the polygon is now a sub mesh a slicing material can now be added to the sliced part of the mesh. The new game object is built by performing step five.

Image 23

6. Results

The mesh slicer described in this paper is able to slice convex and concave meshes using the Ear Clipping algorithm. These meshes include simple convex meshes, simple concave meshes, concave meshes with holes in them, concave meshes consisting of multiple parts, and meshes such as planes/quads. The mesh slicer is not able to slice boned meshes. When only slicing convex meshes it is recommended to set the Knife to convex mode because it performs a bit better than concave mode. Below is the average time difference between convex and concave mode when slicing different objects:

  • Unity Cube ( 24 vertices ): 21,1 – 15,5 = 5,6ms
  • Unity Sphere (515 vertices): 52 – 43,2 = 8,8ms
  • Unity Capsule (550 vertices): 54,1 – 47,4 = 6,4ms

When slicing the following two objects the average slicing time results in the following:

  • Hollow cylinder (128 vertices): 47,2ms
  • Wobble object (as seen in image 23) (2235 vertices): 642,8ms

After debugging different steps in the process it turns out that correcting the data in step five can take up a large amount of time depending on the amount of vertices inside the original object. When turning of the data correction the algorithm is able to slice the wobble object in 51ms, but the positive slice ends up with 8972 vertices instead of 1965 and the negative slice ends up with 4820 vertices instead of 1273.

Unfortunately there are instances where the mesh slicer is unable to slice and object correctly. If one the vertices of a mesh lies exactly on the slicing plane the plane is unable to tell on which side of the plane the vertex is located because it is located on the plane itself. In this case the slicer won’t be able to slice the object using the concave algorithm but it is able to slice the object using the convex algorithm. If the mesh data from the original object is incorrect the mesh slicer won’t be able to correctly slice the mesh. Cases like these are meshes where edges are intersecting other edges.

7. Future references

If I were to continue this project in the future I would try to find a way to keep the vertex count in the new slices low while also maintaining a fast slicing time. Another way to keep the vertex count and frame time low would be to slice the object on a different thread and show a slicing animation/effect while the new slices are being calculated.

I also would like to put more time into the concave mesh slicer to fix the issue where the Ear Clipping algorithm can’t triangulate a slice whenever this slice goes directly through a vertex.

Finally I would add the feature to create multiple game objects depending on the slice we calculated. In image 24 a slice can be seen consisting out of three unconnected parts. Currently these parts are treated as the same game object, but in the future I would like to add the ability to make a separate game object for each of these parts. This could possibly be done by keeping a list of connected triangles when slicing the mesh and creating a separate game object for each collection of triangles. Unfortunately this was not feasible in the scope of this project.

Image 24

Sources

  • Bunny83. (2018, June 27). converting-a-3d-polygon-into-a-2d-polygon. Retrieved October 05, 2020, from answers.unity: https://answers.unity.com/questions/1522620/converting-a-3d-polygon-into-a-2d-polygon.html
  • DitzelGames. (2019, August 20). Procedural Destroy in Unity – Lazy Tutorial. Retrieved September 25, 2020, from Youtube: https://youtu.be/VwGiwDLQ40A
  • Eberly, D. (2015, August 16). TriangulationByEarClipping. Retrieved October 05, 2020, from geometrictools: https://www.geometrictools.com/Documentation/TriangulationByEarClipping.pdf
  • Lague, S. (2017, June 14). Gamedev Maths: point in triangle. Retrieved October 19, 2020, from youtube: https://youtu.be/HYAgJN3x4GA
  • meowNET. (2013, February 21). c-sharp-point-in-polygon. Retrieved October 14, 2020, from stackoverflow: https://stackoverflow.com/questions/4243042/c-sharp-point-in-polygon
  • setchi. (2019, October 31). Unity-LineSegmentsIntersection. Retrieved October 20, 2020, from github: https://github.com/setchi/Unity-LineSegmentsIntersection
  • Unity. (2020, October 20). Mesh. Retrieved October 23, 2020, from docs.unity3d: https://docs.unity3d.com/ScriptReference/Mesh.html

Project

  • Project: https://drive.google.com/file/d/1DI2thjtAmiX-DzV0dEb77vBVBShxzdMC/view?usp=sharing
  • Code: https://github.com/jaspervandenbarg/ProceduralMeshSlicing.git

Leave a Reply

Your email address will not be published. Required fields are marked *

Related Posts