Tuesday, May 13, 2014

Cracking destruction

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.

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 earlier on this blog written 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])

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.


  1. Hi Dennis! I'm delighted to see such a well made game become extremely successful. Well-deserved!

    You write that you use 16 bit integers to save memory. I read elsewhere that 16 and 8 bit variables take a performance hit on a 32 bit ARM processor because the data is padded before use. Then some third source said this isn't so. Now I'm confused.

    Do you know what the deal is?

    1. Interesting! I haven't heard of that before, so I don't know if that's the case. I generally see a performance boost when data size is minimized due to better cache utilization, but I haven't clocked this case specifically.

  2. Thanks a lot for the info and excellent to see the game doing so well too.

  3. Very awe-inspiring Dennis! I could never really put my finger on what made the engine feel so darn good, but when you mentioned the perservation of movement upon impact, it just made sense! Can you recommend any further reading that has helped you during the years?

    1. Not sure what to recommend.. but the bullet physics forum is awesome. That's probably the most relevant discussions and topics on game physics to be found anywhere. bulletphysics.com

  4. Will you add the gameplay mode and levels from the gameplay teaser and screenshots?

    1. Hi Elliott, that's a very sharp eye! No, I don't think those will be added. We tried out a lot of different game modes and score models, and they all had various problems (separate blog post on that coming up), so I don't think we will go back and add them, not saying there won't be new game modes in the future though.

  5. Hi Dennis, thanks for sharing! Your physics loop makes a lot of sense. I'm curious if you had any trouble with visual overlap due to running the position update at the end of the step. This might be something only a physics programmer notices. :)

    1. Thanks Erin, I'm sure there is some overlap at times, but it's hard to see as the camera is constantly moving.

  6. Good to know about the destruction in gaming. I think even that's an art one should possess and it would be possible only to people who have innovative thoughts in gaming. To get these innovative ideas one should have done their game development courses which are readily available in many game development institutes.

  7. Just a quick question how was the general performance of bullet physics in the game did it need any special optimizations. What are the average sub-steps used in the game ?

  8. Tracking features are the most amazing feature which discusses in this article.Valet parking Luton

  9. I have understood everything except the code part. Please elaborate that. meet and greet luton

  10. Is it important to go deeper into the objects for avoiding such kind of breaks?
    meet and greet parking gatwick

  11. Robust Splitting is a crucial part of it all. It is also ingenious though.
    Heathrow Parking
    Meet and Greet Heathrow

  12. No doubt it is an excellent game...