## Deformable Terrain

23 01 2011

The first step in our new title, a 2D deformable terrain solution. We decided to split our work into two areas to try different approaches, either a quad-tree or polygon based system. My responsibility was to create a quad-tree based system that could be easily altered. The main benefit of this would be combining our spatial partitioning and terrain into one object, whilst the quad-tree approach would naturally lead to a simple terrain. The terrain is recursively divided into quads, and can always use the largest tree nodes possible. On the other hand, the polygon approach would integrate nicely with several physics engines we looked at, and so both seemed a fairly viable approach to begin with.

Although both approaches were built and tested, it seemed that the quad-tree gave much more consistent and stable results. The polygon operations either resulted in visually suitable terrain, but with vertex counts far too high for collision calculations or vice versa. It was decided to continue working towards the quad-tree system.

For the first prototype, the quad-tree system came together fairly quickly, and resulted in a robust solution that accepted circular brushes to paint across the terrain. The following images show how a simplified quad (triangles shown in red) adapts and subdivides to form the edges of a hole in the terrain around the brush (shown in green). A simple operation here, but something fraught with errors in our polygonal solution.

The basic principle is fairly simple and works by recursively splitting and disabling quads within the circular brush area as the following pseudocode shows:

```RemoveQuadsAroundPoint( quad, position, radius )
{

if ( quad fully within circle )

else if ( partial intersection )
for each child
}```

Re-enabling quads is almost the same, but is a little trickier as after looking at the children, we have to check if they are all enabled, and so can simplify to the parent quad only:

```AddQuadsAroundPoint( quad, position, radius )
{

if ( partial intersection )
for each child

if ( any intersection )
}```

Once the basic system was done, we threw various test cases at it and managed to get some fairly complex terrain pretty quickly, all with very little external input. The following shows a quickly “drawn”, cavernous terrain and shows how the system easily adapts and always uses the best tree nodes available.

And this final video shows the deformation in action: