Fracturing Simulation by Sargis Grigorian

Table of contents
Introduction
Goals
Pre-fracturing models
Voronoi Fracturing
Delaunay Triangulation
Bowyer-Watson Algorithm
Result
Conclusion
Methods used
Sources

Introduction

This report will be a guide of the steps that I have taken to create my project, simulating fracturing. This topic caught my attention because it can be applied in a wide variety of games. Any game that has objects, which can be damaged, fracturing can be applied in different ways to make the game more interesting and visually appealing. In my report I will focus on 2 different types of fracturing using different methods. Throughout my project I will be using available product analysis to identify existing solutions and apply them to my project. Therefore I'll be talking about, and using the Voronoi diagram and the Delaunay triangulation. I have decided to give my simulation a low poly theme. Since this is the most performance efficient way to do it.

Goals

My goal is to create a simulation in Unity where objects can be fractured in different ways using different methods.

Pre-fracturing models

My first iteration and attempt at fracturing objects I did through pre-fracturing models in blender, which means I created a broken version of the mesh of an object and implement it in Unity. This broken version of the object would replace the unbroken version on collision or at any other moment I wish to activate it. The fragments are then affected by the physics at runtime in Unity, therefore crumbling down from the effects of gravity. Pre-fracturing was very easy to implement and is extremely efficient as there is not a great deal of calculations happening compared to different methods. This brings us to the first issue of pre-fracturing, the fracturing is always happening in the same constructed way, which limits visual realism.

Figure 1. Above are the pre-defined cracks for a cube that will determine how it will fracture. The cube is using the Voronoi diagram for the shattering.

The second issue with this technique is that if you're planning to use this for a big projects with plenty of objects, you will have to pre-fracture every object beforehand and then implement it into your game. This both time consuming and mind numbing work. In addition, regardless of where impact occurs on an object, the whole object will be fractured, and fragments may fall apart synchronously if there are no other constraints present. A window impacted by a projectile will fully break apart instead of the mass and density holding the rest of the window in place, which in return would look faulty to players. And finally, the last issue I see with this method is, that it will not work on AI generated objects. Now, I won't be using AI generated objects in my project, but I find it important to know all the possibilities and limitations of the methods I can use.

For pre-defined fracturing I've used the Voronoi diagram to divide the 3D meshes into fragments. This method can also be used for real time fracturing as well.

Voronoi Diagram

Short history lesson:
The Voronoi diagram was named after Georgy Voronoi who developed a method of spatial division based on the works of René Descartes in 1644, and later by mathematicians, as such, it is sometimes also known as Dirichlet Tessellation.

A 2D plane can be divided into a number of polygons using Voronoi's diagram, which is formed around generating points. The rule to follow is, exactly one generating point per cell. These cells' shapes depend on how far away from their own generating point they are relative to other cells. A cell's own generating point is always closer to a cell's interior than neighboring cells' generating points are.

Fig. 2 below shows the Voronoi diagram as a set of sites and points in the fundamental space of geometry. In this 2D plane, each site (P₁,P₂,P₃, etc) represents a polygon.

Each point in a polygon has equal distance or is closer to its own site than to any other point from other polygons. As you can see in Fig. 2b.

Each point in a face is equal distance or closer to its own site than to any other. This is highlighted in Fig. 2b. Each point in the area of polygon 'P5' is closer or has the same distance to its own cell. What determines the edges and cell shape is the distance calculations.

Figure 2. Visualization of the Voronoi Diagram [2]

Even though this figure shows the use of the Voronoi diagram on a 2D plane, it can be used on 3D objects as well to emulate our own object destruction. I have taken this method and applied it to real time fracturing within my Unity project.

I begin by generating the mesh fragments and store the fragments as children of the parent object. I've added an option for picking the number of fragments you'd like the object to split into. I'll loop through the fragment counts and subdivide the mesh into multiple fragments until the selected amount is reached. Then a random fracture plane is selected to start slicing the bottom and top to create new fragment.

var fragments = new Queue<FragmentData>();
        fragments.Enqueue(meshSource);

FragmentData sliceTop, sliceBottom;
        while (fragments.Count < settings.fragmentCount)
        { 
            Vector3 normal = new Vector3(
                   settings.xAxis ? Random.Range(0f, 10f) : 0f,
                   settings.yAxis ? Random.Range(0f, 10f) : 0f,
                   settings.zAxis ? Random.Range(0f, 10f) : 0f);
        }

For each new mesh a fragment is created as shown in Figure 3. A new game object is created to store the fragments. Each fragment will handle its own scaling, position and rotation.

this.root = new GameObject($"{this.name}Fragments");
this.root.transform.SetParent(this.transform.parent);

this.root.transform.rotation = this.transform.position;
this.root.transform.position = this.transform.rotation;
this.root.transform.scale = Vector3.one;

Once the calculations are done and the fragments are created, I get something like this.

Figure 3. Fractured cube with multiple generated fragments.
Figure 3.1. Fractured cube with multiple generated fragments spread around.

This script can be applied to simple objects and make them fracture on collision with the player, or any other tag you'd like to add. With the rigidbody on the object, the mass and drag can be adjusted to make the object feel heavier or lighter.

While this is already better than the pre-fracturing I made before, I noticed while prototyping that it doesn't solve the problem where the fracturing does not take in consideration where the initial impact was, and therefore always fractures from a random spot. This is acceptable for small objects with less fragments because it's less visible for the player, but becomes apparent when increasing the size of the object and fragment count. I aim to solve this while using a slightly different method.

Delaunay Triangulation

Short history lesson:
Named after the mathematician Boris Delone, Delaunay Triangulation is considered the dual graph of the Voronoi diagram; A Voronoi diagram can be extracted from a Delaunay Triangulation, and a Delaunay Triangulation can be extracted from a Voronoi Diagram

For my next iteration I will be using Delaunay triangulation, which works similarly, but has a few differences to distinguish itself from the Voronoi diagram. First of all, Delaunay triangulation always divides the planes into triangles. Other methods do not have this requirement and can return different shapes. Delaunay uses an angle-optimal solution known as min maxing, which maximizes the minimum interior angles of triangles for the best outcomes and is accomplished by edge flipping.[3] Which is needed to adhere to the rules of the triangles.

Figure 4.

By confirming no other vertices reside within the circumcircle of a specified triangle, you can determine the validity of the edges. Figure 4a shows that the circumcircle of the triangle what an invalid edge looks like, as the circumcircle of the triangle(p4, p6, p10) contains another vertex(p9), which makes (p6 - p10) invalid and sub-optimal in return. Next to it on figure 4b, it shows that the edge can be flipped to create a valid edge (p9 - p4) because the circumcircle of the triangle does not contain other vertices.

I made a list of vertices and triangles that make up the triangulation. I loop through the triangles and vertices until I can verify it's a Delaunay triangulation. I check it by doing check to see whether it's inside the circumcircle or not.

for (int i = 0; i < Triangles.Count; i+=3) {
     var vert0 = Vertices[Triangles[i]];
     var vert1 = Vertices[Triangles[i+1]];
     var vert2 = Vertices[Triangles[i+2]];

for (int j = 0; j < Vertices.Count; j++) {
     var x = Vertices[j];
     if (Calc.InsideCirc(x, vert0, vert1, vert2)) {
	return false;
     }
}}

This is important for us since we will be applying these rules to our project to optimize desirable fragments that we want. To do this correctly, we need the final piece, which is the Bowyer-watson algorithm.

Bowyer-Watson Algorithm

Finally I've used the Bowyer-Watson algorithm to calculate Delaunay triangulations. The procedure initially creates a large container triangle, breaking it into smaller triangles as iteratively added sites, to produce a Delaunay triangulation.

When a new point is added to the overall data structure, the incremental approach is used to construct new triangles. This makes it possible to add recently defined Delaunay triangles to the area around the new point, updating the previous Delaunay geometry. Which means we can use this to check where the impact is, for example throwing a rock through a window, and then create new fracturing based on that. As seen in Figure 5, fracturing starts at the place of impact rather than a random spot.

Figure 5.


As incremental techniques are necessary for constantly changing geometry, this process would be suitable for real-time fracturing because, unlike other methods, re-triangulation only impacts a limited region, eliminating the need to calculate triangulation over the whole structure.

The result

Figure 6. End result

I am satisfied with the end result. Throughout the project and the report I have slightly shifted the main goal of my research. It has shifted from Game Design and elements that make the simulation sensational, to a more realistic approach and accurate fracturing of for example glass.

The finishing product has sound effects added for breaking glass and concrete. I've changed my vehicle to a bulldozer instead of the racing car I was using previously. This made more sense to me knowing the environment of this simulation. And to help the player be able to destroy more and faster, I've added a rocket launcher at the top of the bulldozer which can shoot projectiles. The final result is a small sandbox where the player can toy around a bit with the bulldozer and the gun on top of it.

Conclusion

Different methods and algorithms can be used to achieve different success for fracturing objects in games. It fully depends on the scale of your game, the amount of realism you would want the players to experience and the performance you're willing to sacrifice. Unfortunately I didn't delve into performance much since having low-poly objects and applying the basics to have better performance prevented me from having much issues. I think in the future I'll try and use the Voronoi diagram in a different type of game for a different goal. Perhaps for map generation.

Research methods used:
Prototyping
Available product analysis
Document Analysis

Sources:

  1. Thomas, R. (2022, 13 mei). Real-time fracturing in video games. SpringerLink. https://link.springer.com/article/10.1007/s11042-022-13049-x?error=cookies_not_supported&code=70c7299b-6125-4596-9b98-1ed640e4124c
  2. Langetepe E, Zachmann G (2006) Geometric data structures for computer graphics AK peters/CRC Press
  3. Edge Flip Algorithm for Delaunay Triangulation. (z.d.). https://www.cise.ufl.edu/%7Eungor/delaunay/delaunay/node5.html
  4. Wiki Targeted (Games). (z.d.). Battlefield Wiki. https://battlefield.fandom.com/wiki/Destruction
  5. The Art of Destruction in “Rainbow Six: Siege”. (z.d.-b). [Video]. https://gdcvault.com/play/1023003/The-Art-of-Destruction-in
  6. UpGames. (2019, 21 april). Voronoi diagram tutorial in Unity3D(C#) [Video]. YouTube. https://www.youtube.com/watch?v=EDv69onIETk
  7. Wiki Targeted (Games). (z.d.-b). Rainbow Six Wiki. https://rainbowsix.fandom.com/wiki/Bullet_Penetration
  8. Github - PouletFrit - csDelaunay (n.d) Retrieved 12 October 2022. From https://github.com/PouletFrit/csDelaunay
  9. Github - Samson - Mano (n.d) Retrieved 5 November 2022. From https://github.com/Samson-Mano/Incremental_delaunay
  10. Wikiwand - Bowyer–Watson algorithm. (z.d.). Wikiwand. https://www.wikiwand.com/en/Bowyer%E2%80%93Watson_algorithm

Leave a Reply

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

Related Posts