Gamasutra: The Art & Business of Making Gamesspacer
View All     RSS
July 25, 2014
arrowPress Releases
July 25, 2014
PR Newswire
View All
View All     Submit Event





If you enjoy reading this site, you might also want to check out these UBM Tech sites:


 
Cracking destruction
by Dennis Gustafsson on 05/13/14 09:26:00 am   Featured Blogs

The following blog post, unless otherwise noted, was written by a member of Gamasutra’s community.
The thoughts and opinions expressed are those of the writer and not Gamasutra or its parent company.

 

Smash Hit is a game built entirely around destruction. We knew from the beginning that destruction had to be fully procedural and also 100% reliable. Prefabricated pieces broken the same way every time simply wouldn't be enough for the type of game we wanted to make. The clean art style and consistent materials made breakage easier, since everything that breaks is made out of the same, solid glass material.

Procedural breakage

Physically based breakage is hard. Really hard. I remember NovodeX had some kind of FEM approximation for breakage in the early days of PhysX, but it never worked well and didn't look very convincing. I think for most game scenarios it is also completely overkill, especially for brittle fracture, like glass. I designed the breakage in Smash Hit around one rough simplification – objects always break where they get hit. This is not true in the real world, where tension builds up in the material, and objects tend to break at their weakest spot, but hey, we're not really after accurate breakage here. What we want is breakage that feels right, and looks cool.

In Smash Hit, when a breakable object gets hit, and the exerted impulse is above a certain threshold, I carve out a small volume around the point of impact and break that up into several smaller pieces that become new dynamic objects.

It sounds simple, but looks quite convincing. However, there are a few obstacles to overcome in the implementation:

  • Carving out a piece from a generic object in a robust way
  • Slicing that volume
  • Check for topology changes in the original object. Carving out a piece may cause it to fall apart.

Plane splitting 

Carving out a volume from a generic mesh in a robust way is a really complex geometric problem. Furthermore, since every object in Smash Hit is physically simulated we want the resulting objects to be well-behaved in a physics-friendly format. From a physics point of view, I represent all objects as compounds of convex shapes, so the resulting broken object must also be a collection of convex shapes. Luckily there is one safe way to split up a convex object into two new objects that are also guaranteed to be convex – slicing it with a plane.

So to carve out a piece from the original object, I slice all the convex shapes with five bounding planes, slightly randomized around the point of impact. It will increase the total number of convex shapes used in the original object, but that is inevitable due to the fact we are making the object more concave. It takes a bit of bookkeeping to get the splitting code right, but as long as the plane splitting is robust, so will the overall breakage algorithm.

The carved out piece can be split up into smaller pieces using the same plane-splitting, so all we need is a really fast, reliable plane-splitting method for convex objects.

Breakage in six steps

Robust splitting

The classic problem with plane-splitting is not handling degenerate cases. Say for instance one of the faces coincide with the splitting plane, so that only one edge crosses the plane due to floating point precision. That can easily result in degenerate geometry, non-closed polyhedra or even broken data structures and hard crashes. To avoid that, I start by determining a side for each vertex (above or below the plane) and then base all edge-splitting on that information, hence only split an edge if the corresponding two vertices are on opposite sides of the plane. The split point for each edge is capped to be a certain distance away from both vertices, so that the resulting two shapes are always closed, well-defined and all edges are above a certain length.

I tried quite a few data structures for doing the plane-splitting before finding one that works well in practice. The biggest hurdle was that I needed a way to track vertices through multiple splits in order to keep vertex normals consistent. It might not be visible at a first glance, but vertex normals are used extensively to make nice gradients in the glass rendering and create a certain softness to the material. Recomputing those normals after splitting an object would create a deviation in the material that is very visible to the player. In the end, the half-edge data structure turned out perfect for the job, offering both high performance and very small memory footprint. I even use 16 bit integers instead of pointers to keep the size down.

Tracking topology

After carving out a hole in the object, it needs to be checked for topology changes. Depending on the shape, it might have been split into two or more separate objects. Finding connected components in a series of  inter-connected nodes is classic graph theory. What makes out a connection in this case is wether two shapes are touching face to face. The most elegant way to do this would be to track split faces between shapes and remember the connections, but it takes a lot of bookkeeping. I'm using a more pragmatic approach, where the distance between shapes are measured geometrically. I have written before about the GJK algorithm and how immensely useful it is for all kinds of geometric operations. In this case, we only want to know if two object are within a certain distance of each other. This can be done as a simple overlap test in configuration space, which is extremely fast.

The algorithm for finding connected components goes like this:

Assign each object a unique id
For each object A
  For each object B
    If id[A] and id[B] are different and they are touching
      Replace all id[A] and id[B] with min(id[A], id[B])
  Next
Next

After we're done all shapes with the same id represent the same rigid body. This is obviously not a very fast general algorithm due to cubic complexity, but since the number of shapes in a rigid body is usually within a few dozen it works well in practice. The nice thing about it is the complete lack of state, which simplifies further breakage.

Simulation pipeline

A final word on breakage is the importance of getting the simulation pipeline right. With an off-the-shelf physics engine, contact impulses are typically analyzed after the simulation step to determine if something breaks. This give the impression of unbreakable objects colliding and then artificially split up afterwards. The key to natural looking breakage is to limit the contact forces of a breakable object during the simulation and break them up while preserving some of the motion. There are tricks to mix in some of the pre-break velocity on broken pieces, but I went all in and actually do multiple solves during breakage, so a simulation step typically involves running the following steps:

  1. General collision detection
  2. Run solver with capped impulses on breakable objects
  3. Check if some contacts reached the cap and in that case break objects
  4. Collision detection for new objects
  5. Run the solver again on affected contacts with capped impulses
  6. Repeat from 3
  7. Integrate

This means that objects are created and broken several times during a simulation step before proceeding to integration. I have capped the number of solves per simulation step to three in order to limit performance impact.

This is the first game where I'm giving my low level physics engine a proper work-out. It has been in development on and off for almost four years so it's great to finally see it in action. Good destruction ties very deeply into the simulation pipeline, so it's not ideal to plaster it on top of an existing physics engine.


Related Jobs

Cloud Imperium Games
Cloud Imperium Games — Austin, Texas, United States
[07.25.14]

DevOps Engineer
Cloud Imperium Games
Cloud Imperium Games — Austin, Texas, United States
[07.25.14]

Animation Programmer
Cloud Imperium Games
Cloud Imperium Games — Austin, Texas, United States
[07.25.14]

Server/Backend Programmer
Cloud Imperium Games
Cloud Imperium Games — Austin, Texas, United States
[07.25.14]

Lead Online Engineer






Comments


Ian Morrison
profile image
The destruction physics look gorgeous, not to mention satisfying. Is there a bubble wrap level? Because it looks like it's tapping into the same gleefully destructive joy.

I'm impressed by how well it appears to be running, given that this is a mobile title. Did you have to do a lot of extra optimization to get the physics to play so smoothly?

Dennis Gustafsson
profile image
Thanks Ian! Yes, there was quite a bit of optimizations to the physics, especially making good use of multple cores. It is mostly data-parallel, in order to minimize interaction lag.

Sauli Kiviranta
profile image
Fully agree with Ian. This just triggers some magical nerve and even looking at the things get broken is cool :)

Juan Felipe Belon Perez
profile image
For a long time I was thinking about what was the technique over here when you break a plane with the ball in your game, I thought it was some physx thing but now I understand the theory.
Thanks!

Wes Jurica
profile image
Just downloaded this game. On my first play I made it to the level 2 save point then quickly died. I bought the premium upgrade so I could continue from save points. Then I started from level 2 with only 10 balls and died after 1 hit! Then died again and again and again. Instead of beautiful glass, I was thinking about smashing my phone.

I didn't realize that the save point takes into account how many balls you had when you went through it. That nice, even 10 made me think that was the starting amount. After I figured that out, I went back through and played level 1 again and made it through with 5x the balls left.

Anywho, great game! I hope your team is getting very wealthy with this simple, well-implemented, beautiful game. Congrats!


none
 
Comment: