Sprash

Mathias Plans

Build (old build) has to be hosted with a web server: python3 -m http.server for example.

Windows Build

GitHub

Description

This is a continuation of my previous project: https://courses.cs.ut.ee/2020/cg-pro/fall/Main/Project-Sprash

This semester I want to revamp my debris technology:

Asteroids are currently constructed with rhombic dodecahedrons, I wish to use Voronoi diagrams instead
The breaking hierarchy is very boring -- "snakes" are formed. I wish to use a clustering algorithm to make the breaking hierarchy more realistic and interesting
Currently, a mesh is generated for each state of an asteroid. I wish to create a data structure where there is only one mesh for each leaf. Union colliders and adding/removing Rigidbody have to be used.
Currently, only one type of asteroid is generated. I wish to add more.
Optionally I want to make asteroids look cooler.
Optionally I want to add more space debris.

Mesh generation according to Voronoi noise and the breaking hierarchy will be the most difficult parts of this project.

In the end there should be a link to the final build, repo and a 10-20 sec final result video.

Illustration

Here is an illustration on how the asteroids are generated

Firstly, we start with a voronoi diagram:

Then we pick a random location and a random radius, so we get a bounding area:

Every voronoi cell in that area will be in the new asteroid:

Then we do clustering. The important thing to note is that every non-leaf node will have exactly two kids:

We can also illustrate that tree with colored lines which separate the siblings:

Finally, when something collides with the asteroid, we can separate the siblings and make them their own independent asteroids:

Milestone 1 (05.10)

Familiarize with the project (2h)
Fix bugs (4h)
Design the algorithm with Voronoi noise (3h)

I fixed my bugs for the MängudeÖÖ Expo.

The initialization:

Create a collection of Voronoi cells. Turn them into separate meshes
Create a GameObject for each mesh. Add a collider to them.
Use a clustering algorithm to start pairing them, creating a hierarchy. Add a Rigidbody to the root.

In the game:

Create a few hundred asteroids and put them into a queue.
Spawn asteroids into the game by removing them from the queue.
If a collision is detected, the Rigidbody of the root is destroyed. A Rigidbody is added for each immediate child. If there are no children, increment a death counter.
When the death counter is equal to the number of Voronoi cells in the asteroid, reset the Asteroid and add it back to the queue.

This algorithm is much better than the one I am currently using. Firstly, it saves on a lot of memory, since I am not generating a mesh for each node in the graph. Instead, there are only meshes for the leaves! This also makes the loading times faster. Secondly, it is less confusing. What I currently have is a mess.

There might be some problems. The number of mesh colliders in the scene might cause lag. This is more of a problem for larger asteroids. The clustering might not be good enough, in which case a custom clustering algorithm has to be developed.

Currently, the asteroids look like this:

Milestone 2 (19.10)

Create meshes from Voronoi noise (7h)

I found a very nice Asset that generates 3D meshes of Voronoi diagrams: https://github.com/Scrawk/Hull-Delaunay-Voronoi

Each cell in the diagram has its own mesh, so this is perfect for me!

Here is a diagram of ~200 cells:

Now I need to create a subset of this.

The first attempt produced this:

Clearly this is not what I want. I foolishly limited all the generation numbers into the radius and didn't take the subset, as I should be.

What I need is to filter the cells after they have been generated. The problem is that the center is not attached to the cells. This was fixed by adding an attribute to VoronoiRegion class which returns an arithmetic mean of the vertices. The more correct method would be to return the center of mass, but this is more difficult.

Then I created a filter function, which returns true if the filter can be passed. It's just the parametric function for the sphere. Here is an example of a subset of the diagram with 10000 cells!

Loading 10k cells takes quite a long time, however. So I have to use less, at least for testing. I also made each axis configurable, so it is not a perfect sphere. All the parameters are configurable in the inspector:

Here is the generated asteroid with the shown parameters:

As can be seen, the asteroids look quite pointy. This can be fixed by changing the distribution of initial points. The other solution would be to not use flat shading and fix normals, etc... I will look into it when I get to the beautification phase of the project.

TODO: The initial diagram could be reused as well. Then just take subsets with different centers. This approach should save on generation times greatly.

Milestone 3 (02.11)

Use a clustering algorithm on the Voronoi cells (4h)
First attempt at the tree node type (3h)

Before the clustering could happen, I had to remove the rendering logic (it used OpenGL) and convert the VoronoiMesh class into non-GameObject. Then I had to create a new GameObject AsteroidCreator, which has all the settings in the inspector and produces a hierarchy of Meshes.

The clustering algorithm itself is similar to complete-linkage clustering. I did some things differently, because I do not need precision, but speed. The algorithm can be found here.

The result is demonstrated by deactivating parts of the hierachy:

The collider thing was quite simple. I only needed to add the colliders to leaves, which are inherited by the parents:

Then I tried to add a rigidbody to the equation. Adding it to the root was easy enough. Transitioning it to children is not so straight forward. Since it is a physics simulation, deleting rigidbodies straight away can not be done. Also, the asteroids collide with eachother as well, making things even more chaotic:

One reason for this chaos might be that the clusters are "hooked" together:

I think the solution would be to create a pool of GameObjects with rigidbodies in them. Then when I need to assign a rigidbody to a root, I make the root a child of that gameobject. This way I do not have to create rigidbodies all the time.

Milestone 4 (16.11)

Fix the collision chaos (5h)
Add the new asteroids into the game (2h)

The first thing I did was change the clustering algorithm. Now I am just using the centroids of clusters. However, this seems to create uneven halves. It should be good enough for now. The other idea was to use Random Projection trees, but then I won't have two kids per node anymore, and some splits might have a situation where two halves are not even physically attached. Luckly, tweaking the clustering algorithm is quite simple, so I will keep on experimenting.

The chaos was fixed by writing lots of missing code. I added a controller for each asteroid that handles its resources and activation logic. Then I also created a prefab for the rigidbody objects. At first, the collisions weren't detected, but physics worked alright. I discovered that OnCollisionEnter function has to be in the same GameObject as the rigidbody! Here is the initial result:

At least there are no errors!

The problem is that as soon as I create the children, they collide with each other, and "cancle" each other out, so to speak. Also, notice how the collision isn't detected until the cube is well inside the asteroid? This is a bug, and I have no clue why it happens. It might also be one of the reasons that everything disintegrates at once. I have to look into this after I have fixed the canceling issue.

Previously I handled this problem with a 'grace' period, where the asteroid is immune for certain amount of time after it's creation. I used 4 frames for the period last time. It makes things better, but one collision still produces many splinters. Increasing the period seems to work. Here I used 10 frames:

Still, sometimes it produces 3 sub-asteroids. Also, I should perhaps time the grace period in real time, not with frames (TODO).

Now I have to fix the strange not-colliding-until-in-the-middle-of-the-asteroid bug. While testing different scenarios, I discovered that entering the collider doesn't trigger the collision, but entering, and then trying to exit does! Perhaps, changing the position of the box in editor doesn't simulate the physics?

With that in mind, I tried to "force" the Unity to simulate physics even when I move objects in the editor. I had a hunch that adding a rigidbody to the cube would do the trick:

This is magnificent. Now I need to add some infrastructure so that I can add them to the game. Mainly, there should be some sort of handler that creates few tens or hundreds of asteroids and holds them in the pool. Then stich the debris spawner with the new handler, and finally add logic for despawning (<- maybe should do it with a trigger? YES! TODO).

Unity is strange. When I change the coordinates of a parent, the children will also move, but in the opposite direction. This means that the parent moves, but the children stay in place (in world space). Basically, Unity does hidden transformations to children, that, if you are not experienced with Unity, will produce very strange bugs. After dealing with this for hours, I got the new asteroids into the game finally:

The collisions look natural, and the asteroids move when the satellites move. But in the end, a super-explosion can be seen. They happen quite frequently, and I have no clue why. It might be some ping-pong situation, where the bouncing and explosion force form a positive feedback loop. Regardless, this has to be investigated and fixed.

Milestone 5 (30.11)

Change rigidbody mass depending on the asteroid (1h)
Investigate and fix the super-explosions (5h)
Add illustrations for the algorithm (2h)

I added custom masses for each stage of the asteroid, although it doesn't seem to do much. Currently, I am using the number of leaves in the sub-asteroid as the mass.

For removing super-explosions, I did two things. Firstly, I changed the grace period so it actually uses time instead of the number of frames. I set it to 100ms currently. Secondly, I changed the Physic Material of the asteroids. I reduced the bounciness from 1 to 0.8 and set the bounce combine to average. With these changes, the number of super-explosions was reduced greatly. But they still happen sometimes.

I noticed that due to a large number of leaves (up to 100), the scene looks like a nuclear chain reaction. Big asteroids get destroyed fast and there are lots of small asteroids haphazardly flying about. This can be mitigated somewhat by increasing the grace period, but then it becomes noticeable. One of the solutions that I came up with is to use the physical equations to calculate the force of the collision, and then use that to determine whether I have to split the asteroid or not. I can also have a health system.

The illustrations for the algorithm are in the project description.

Milestone 6 (14.12)

Implement health system with physics equations (4h)
Make the surface of the asteroid look better (3h)

The health system was implemented quite easily. Unity's Collision class has a field called impulse, which is related to the total force of the collision. To get the force, I just had to divide the impulse vector by the fixed time delta. Then I took the magnitude of the force vector and got the total force. A typical collision is about 15k force units. So I set the health around that area. I also made the health scale with a square root of the size of the asteroid. In that way, smaller asteroids are less volatile. Here is an illustration of how calm the game is now:

I also tried to make the asteroids look cooler, but I quickly realized that 3h is not enough for the full task. But I did create a procedural texture for the asteroids. I used many layers of fractal noise:

The reason this task is so difficult is that I need to distinguish between surface vertices and internal vertices. For that, I have to investigate how the library that I am using works. I estimate that it would cost around 2 milestones worth of work to start messing with surface vertices and their normals. I guess this has to do.

Computer Graphics Project 2021/22 fall