Glass shattering

By Thomas Otte
30-3-2021

Foreword

The goal of my project was to create a script that based on a collision should shatter the mesh. To achieve this, I wanted to use a Voronoi diagram, to create realistic looking shards. In this article, I will take you through my journey to achieving this goal, along with the challenges I encountered and the result this produced.

The reason I wanted to do this, is because I wanted to make a modular script, that could be applied to anything and it would work on it. Besides I thought this might be a fun challenge to take on.

Table of Contents

  1. Preface
  2. Goal and scope
  3. Meshes
  4. The Voronoi diagram
  5. Delaunay triangulation
  6. Geometrical approach
  7. Creating a new shard
  8. Optimisation
  9. Results
  10. Future reference
  11. Sources

1. Preface

The goal of this project was to have the shattering effect work on any mesh, however, I was unable to achieve this. So far, this script is only applicable to 2D meshes. The new mesh it creates will only have faces when the old mesh had a face there. It currently doesn’t work with convex meshes, this will be discussed later in this article.

The shattering effect I’m talking about is when you for example drop a glass object. This object will then shattering into smaller glass shards. Later in this article the term ‘shard’ will be used, this ‘shard’ is a separate class in the code and will be formed into a new game object. Similar to the glass shard, this is a piece of the original object.

This project was made in Unity2019.2.5f1, and the shattering of a mesh will happen on collision and when the set impact velocity is reached.

Chapter one will explain more about meshes and how they work within unity. In the next chapters, we will discuss the Voronoi diagram and how I wanted to use this. After that, this article will discuss an entirely different approach and why this approach was used over the Voronoi method. Then the process of creating shards will be discussed. Then finishing up the technical part, some optimisations will be discussed. Finally, the results will be shown.

2. Goal and scope

The original goal of this project was to create a script, that would be able to create a shatter effect on any mesh. This mesh needed to be subdivided into separate game objects, so they would be able to use the unity physics engine. Also, this mesh should have smaller shards near the centre of the impact, than further away from the impact position. Additionally, for the remedial, I wanted to make sure the final shattered object should look like the object from before. And for the remedial, it should be applicable on the unity plane object.

The final product after the remedial, the script can be applied on the plane object that unity provides as a primitive. It will shatter with shards smaller when closer to the impact position and it has no tear in the end. This uses the algorithm described in chapter 6, geometrical approach. The Voronoi approach remained unused for this version.

3. Meshes

A mesh is a representation of a 3D object. A mesh consists of vertices and triangles. Alongside that, additional information like a texture or normals can be applied and changes to appear different on screen. To use a texture, uv-coördinates are used to describe what part of a texture should be on a specific part of the mesh. In unity, all this data is added as arrays to a mesh object.

Vertices and triangles form the geometric shape of the mesh. The triangles dictate which vertices form a face together. Each triangle has 3 vertices, which are connected via three edges, together, these edges form the face of a triangle. The order of the vertices in the triangle matter, the face is only shown in the direction where the vertices are in clockwise order.

Figure 1: Vertices form a triangle, connected via edges, determined by the triangle (Toble, Maierhofer, 2006)

For this project, it is also important to understand the difference between a convex and concave shape. A concave shape is a shape where there are points within the shape, that cannot be reached from another point without going outside of the shape (figure 2). A convex shape does not have any combination of points that cannot be connected with a straight line, without going outside the shape.
The difference also goes for meshes, it is important to understand this difference because a concave mesh is more difficult to handle. On a convex mesh, you can triangulate everything, but for a concave mesh, you need to not triangulate certain triangles. These triangles need to be excluded, this can form a problem when triangulating.

Figure 2: Concave shape (left) and convex shape (right) (Smart Penguins – GameDev, 2020)

4. Voronoi diagram

Important notice, anything described in this chapter is not used in the final product and is only here for future reference and to show work that has been done!

A Voronoi diagram is a distribution of space. In a Voronoi diagram, there are some points on a plane, these points are also called seeds. The space in a Voronoi diagram is divided into cells, each of these cells consists of the points that are the closest to the seed of this cell as can been seen in figure 3.

Each colour in this figure is a different Voronoi cell, and each black dot is a seed. We will use this diagram, to create individual shards, where one shard would be one cell of the Voronoi diagram. I used this to create shards with inconsistencies in their shape, making it feel more like natural shattering.

Figure 3: Voronoi diagram (Stadnik, 2020)

Since in the mesh, we do not have a set collection of points, we need to calculate where the intersection points and edges are between cells. This is where Delaunay triangulation comes into play, the centre of each circle with the edge of the circle on a triangle in Delaunay triangulation corresponds to an intersection point between Voronoi cells. This will be explained in the next chapter.

5. Delaunay triangulation

Important notice, anything described in this chapter (5, 5.1, 5.2 and 5.3) is not used in the final product and is only here for future reference and to show work that has been done!

Delaunay triangulation is a way of creating triangles between points so that no point is within the circumcircle of a triangle. This is needed to determine where the intersection points of the Voronoi diagram are. The circumcircle is the circle formed with all the points of the triangle being the same distance from the centre of the circle.

Figure 4: Delaunay triangulation

In the above figure, 10 random points are generated and connected using Delaunay triangulation. These points are generated on the mesh of the object, in this case, a 2D plane. To do this, a random triangle in the mesh is selected, then a random point in this triangle is taken and temporarily added to a list object. A random point is chosen using a function in a static class, which takes the vertices of the triangle. The formula for selecting a random point in a triangle is:


Where r1 and r2 are randomly generated numbers and vertex1, vertex2 and vertex3 are the vertices of a triangle. (Millikan, 2011)

5.1 Bruteforce delaunay

I created a bruteforce algorithm to implement delaunay triangluation. Instead of storing the triangles it creates, we immediately store the centre of the circumcircle to the shards that will be created. These are the intersection points of the Voronoi diagram and will be required later, the triangles themselves are not needed right now.

// Set properties for this potential intersection
Vector3 center = ShatterHelper.CircleCenter(
    s1.cellPoint, s2.cellPoint, s3.cellPoint
);
float distance = Vector3.Distance(center, s1.cellPoint);
 
// Check if this point is already evaluated
if (addedVertices.Contains(ShatterHelper.RoundVector3(center)))
    continue;
 
// Check if this intersection is valid
bool isValid = true;
foreach (Shard s4 in shards)
{
    if (distance > Vector3.Distance(center, s4.cellPoint))
    {
        isValid = false;
        break;
    }
}
// Add the intersection point to the shard

The above code snippet is encapsulated in 3 for each-loops, which evaluates every unique combination of three vertices. These vertices would form a triangle if it is valid. For this, we calculate the circle centre, where the vertices are on the edge of the circle.
Then, we check if any point is within this circle. If this is the case, the triangle is invalid and we proceed further. Otherwise, the circle centre is an intersection point on the Voronoi diagram. If any vertex is evaluated again, we skip that one.
After this, we know where the intersection points of the Voronoi diagram are, and to what shard they belong.

The first time, I chose to use this algorithm, since it was the easiest to implement. Other algorithms, like the ones covered in 5.2 and 5.3, require a so-called flip algorithm. The flip algorithm checks if a triangle can be optimized by checking if the centre edge of a set of 4 vertices can be drawn between two other vertices. Doing this might require (though this is very rare) changing all other triangles, since optimizing the triangle may allow another triangle to be optimized. However, I chose not to use a voronoi based method, since this was unreliable.

5.2 Divide & Conquer

An example of an algorithm to calculate the triangles is the ‘divide & conquer algorithm. This algorithm divides the points into subsections of approximately 3 points. These points are triangulated and then get combined into larger subsections, all of those points are then triangulated within the combined sections, and a flip algorithm is used, to check if there are more efficient triangles. This is repeated until every section is combined and everything is triangulated.

Figure 5: Divide and Conquer algorithm (Cvejić, 2016)

5.3 Bowyer-Watson

Another algorithm is the Bowyer-Watson algorithm, also known as the point-by-point insertion algorithm. In this algorithm, all points are encapsulated in a ‘super triangle’. Points are added one at a time and get connected to the points where it does not intersect with an edge of a triangle. If the new points are added to a triangle with one edge of the super triangle, then the edge that the new edge would intersect with is removed. In the end, the super triangle is removed and the edges connected to them. (Madali, 2020)

Figure 6: Bowyer-Watson algorithm

I have experimented a bit with this algorithm, but my approach was wrong. I focussed on a triangle-based approach, but it would be way more effective using an edge-based approach. This has to do with the flip algorithm, when using triangles, you have to check all triangles if they share an edge and if they do, need to be flipped. When using edges, you can simply check which edges are shared by a triangle and flip accordingly. Therefore my experiment failed and was very inefficient.

6. Geometrical approach

A different approach to shattering a mesh is to use geometry. Using this, you can create more reliable shards, but these shards are more alike. This takes away from the effect of glass shattering, but with some randomness, this can still look pretty good. To do this, we divide some points around the centre of the impact of the collision. Then we extend those to the edges of the object and if needed, also put some vertices on those lines, to further divide the mesh. You can see this happen in the code snippet below.

for (int i = 0; i < radials; i++)
{
    for (int j = 0; j < circles; j++)
    {
        float dirX = Mathf.Cos(Mathf.PI * (i * 2) / radials) + Random.Range(-randomness, randomness);
        float dirZ = Mathf.Sin(Mathf.PI * (i * 2) / radials) + Random.Range(-randomness, randomness);
 
        Vector3 v = new Vector3(dirX, 0, dirZ);
 
        // The scale is there to make sure the last vertex is on the edge of the object
        float scale;
        if (Mathf.Abs(v.x) > Mathf.Abs(v.z))
        {
           scale = (bounds.extents.x / (Mathf.Abs(v.x))) * ((float)(j + 1) / circles) - Random.Range(0, randomness * (1 - (float)(j + 1) / circles));
        }
        else
        {
           scale = (bounds.extents.z / (Mathf.Abs(v.z))) * ((float)(j + 1) / circles) - Random.Range(0, randomness * (1 - (float)(j + 1) / circles));
        }
        v *= scale;
 
        // Make the impact position the center
        v -= impactPosition * ((float)(j + 1) / circles);
        v += impactPosition;
 
        newVertices[i * circles + j] = v;
    }
}

We also add some randomness to the positions, so it looks less generated. An advantage of this approach is also that all vertices are ordered counter-clockwise, which helps to create shards later on.

Then we separately create shards that connect to the edges of the object, we know we only have to connect the corner pieces, since the rest is already covered, so we just look for the closest vertex on the outer ring that is not colinear with the corner vertex. If the points are colinear, that means they form a straight line, so it won’t form a triangle. This creates a pattern that looks like this:

Figure 7: Where vertices would be created using this method

7. Creating new shards

To create a shard of the shattered object is very easy. All needed vertices are already assigned to separate shards. All we need to do is create a copy of the current object so that all materials and shaders remain in its shards. Then we need to triangulate the shards, since all vertices are ordered, we don’t need a complex algorithm to do this.

private List<int> Triangulate(Vector3[] orderedVretices)
{
    List<int> triangles = new List<int>();
 
    for (int i = 1; i < orderedVretices.Length - 1; i++)
    {
        triangles.Add(0);
        triangles.Add(i);
        triangles.Add(i + 1);
    }
 
    return triangles;
}

All that needs to be done is to connect the original vertex, to the following two, when there are more vertices, connect those the same way. With ordered vertices in a convex mesh, this will reliably triangulate it.

Now, we have the vertices and triangles defined for each shard, from this we create a copy of the parent object. We do remove the script to shatter the mesh, otherwise, all shards would shatter, again and again, this is very bad for performance. The mesh of the copy is replaced with the new vertices and triangles.

Once everything is done, we can destroy the original object, since all of its shards are created.

8. Optimisation

Important notice, anything described in this chapter (8, 8.1 and 8.2) is not used in the final product and is only here for future reference and to show work that has been done!

There are a few optimisations I did, to improve the script. In this chapter, I will discuss these optimisations, why they save time and what issues they created.

8.1 Convex hull

A convex hull is the most bare-bones representation of a convex mesh. In the image, all the black dots would be vertices. The blue line represents a convex hull, all the points in the centre are not necessary to represent the mesh.

Figure 8: rubberband analogy of a convex hull (Sommer, 2016)

In the case of the plane object in Unity, which is 11 * 11 = 121 vertices, can be reduced to 42 vertices. This saves a lot of comparisons. The Voronoi algorithm I used was O(n^4), which is very inefficient, and would take approximately 200 million comparisons to use. Using the convex hull, this can be reduced to about 3 million.

8.2 Removing vertices

Voronoi diagrams generate intersections very far from the original mesh, therefore the vertices generated at these intersections need to be removed. Originally, I used a raycast to detect if a vertex was outside the original mesh. However, this wasn’t reliable and relatively slow. To change this, I just check if a point is in the original mesh, by checking if it is in a triangle of the convex hull.

public static bool IsInTriangle(Vector3 pt, Vector3 v1, Vector3 v2, Vector3 v3)
{
    v1 -= pt;
    v2 -= pt;
    v3 -= pt;

    Vector3 u = Vector3.Cross(v2, v3);
    Vector3 v = Vector3.Cross(v3, v1);
    Vector3 w = Vector3.Cross(v1, v2);
 
        if (Vector3.Dot(u, v) < 0 || Vector3.Dot(u, w) < 0)
    {
        return false;
    }

    return true;
}

This algorithm checks if a point is in a triangle. If it is not, then it will be removed from the new shattered game object. This is 0.2 seconds faster than the raycast algorithm when 10 shards are created.

9. Results

The result of this work is a script that can divide a 2D, convex mesh into shards on collision. This happens in 0.01 seconds.

This result complies with the criteria set for the remedial of this project. Shards created are smaller near the impact position, no tears exist anymore, compared to the previous result and there are no new points that are outside of the mesh.

In this GIF, you can see that the mesh gets subdivided with shards near the centre of the impact smaller. In this case, the impact is simulated to be a little to the right. Though it doesn’t seem like it in the image, there is some randomness in the shape of the shards.

I am very happy with these results and see them as a definite improvement from the first version.

Figure 9: Glass shattering result

10. Future reference

Something that can improve this script in my opinion is more randomness, it still looks very much generated, which I think is undesirable. The reason this randomness cannot be increased yet is that there will be a large chance that shards will start to overlap, this would look even worse. This can be improved by changing the formula, so randomness can occur in a larger area and can be dependent on the size of the shards desired.

Another improvement that could be made, though this would be very hard, is to include extra vertices in the shards so that not every shape would be a rectangle like object. This would also include pentagons, for example, creating more variation and a more exciting shattering effect. A challenge with this is that vertices are generated in order, and adding extra vertices would disturb this order.

Another final improvement can be created by allowing this to work on other objects. This would be possible for flat objects, as long as it is possible to calcualte the distance to an edge. 3D objects would also be possible with this technique, you can take a vertical slice of the object and create vertices on both sides of the vertical slice. This would then only need to be triangulated, but I see this as a very possible and realistic improvement.

11. Sources

Batya Studios. (2020, 9 oktober). Procedural glass shattering. Unity Asset Store. https://assetstore.unity.com/packages/tools/particles-effects/procedural-glass-shattering-123802

Dušan Cvejić. (2016, 17 april). Delaunay triangulation divide and conquer algorithm [Video]. YouTube. https://www.youtube.com/watch?v=FUkmgjB3tSg

Madali, N. (2020, 8 september). Delaunay Triangulation. Towards Data Science. https://towardsdatascience.com/delaunay-triangulation-228a86d1ddad

Martigan. (2015, 18 June). Show that four points are coplanar [Forumpost]. Mathematics Stack Exchange. https://math.stackexchange.com/questions/1330357/show-that-four-points-are-coplanar/1330360

Maur, P. (2002, January). Delaunay triangulation in 3D. https://www.kiv.zcu.cz/site/documents/verejne/vyzkum/publikace/technicke-zpravy/2002/tr-2002-02.pdf

Millikan, R. [Roos Millikan]. (2011, 24 January). Uniform random point in triangle in 3D [Forumpost]. Mathematics Stack Exchange. https://math.stackexchange.com/questions/18686/uniform-random-point-in-triangle-in-3d

Smart Penguins – GameDev. (2020, 21 March). Understanding Physics: Collision Shapes, Mesh vs Hull, Concave vs Convex – for Unity and Buildbox [Video]. YouTube. https://www.youtube.com/watch?v=_uE90sarrrc

Snibbe, S. S. (1992, March). Introduction to Voronoi Diagrams. http://cs.brown.edu/courses/cs252/misc/resources/lectures/pdf/notes09.pdf

Sommer, P. (2020, 19 juni). A gentle introduction to the convex hull problem. Medium. https://medium.com/@pascal.sommer.ch/a-gentle-introduction-to-the-convex-hull-problem-62dfcabee90c

Tobler, R. F., & Maierhofer, S. (2006, January). A Mesh Data Structure for Rendering and Subdivision. http://wscg.zcu.cz/wscg2006/Papers_2006/Short/E17-full.pdf

Unity technologies. (2021, 22 March). Mesh. Unity. https://docs.unity3d.com/ScriptReference/Mesh.html

Utilities. (2020). [Collection of C# scripts for various utilities]. Bunny83. https://github.com/Bunny83/Utilities

Tags: ,

Related Posts