Month: January 2017

Introductory Guide to AABB Tree Collision Detection

Those of you who read my Christmas break update will know I’ve taken a slight detour into low level graphics and games programming, writing a C++ voxel engine from the ground up for fun and a challenge. I’ve continued to tinker with it when I can and have since added support for voxel based sprites. In the screenshot below the aliens, player and bullet are all made up of voxels and move around the world space in a fashion vaguely reminiscent of the classic Space Invaders game:

2017_01_08_2

Though I realise it just looks like a flat textured mesh, and that a flat textured mesh would be many times more efficient than voxels for this, the ground is also made up voxels.

Of course as soon as you add sprites or anything that moves to a world you start to think about detecting collisions and doing this efficiently remains an interesting area of development with different approaches being more or less optimal for different conditions. It’s essentially a spatial organisation problem. As such although you might think “huh, collision detection, what use is that to me?” it’s not hard to see how similar indexing approaches can be useful in answering similar questions not involving games. Similarly although the A* algorithm, for example, is traditionally thought of as a gaming algorithm I’ve found myself using it in some very interesting none-gaming spaces.

In the case of collisions between sprites in my voxel engine I need to consider hundreds of objects made up of, in sum, millions of voxels spread across an indeterminate, but essentially very large and mostly sparse, three dimensional space. Pixel / voxel perfect detection between every one of those sprites is clearly going to be horrifically expensive and so typically collision detection is broken down into two phases:

  1. Broad range collisions – quickly draw up a shortlist of probable collisions.
  2. Narrow range collisions – use additional detail to filter the probably collisions resulting from the broad range pass into the actual pixel / voxel perfect collisions.

My first attempt at solving the broad range problem in my voxel engine is a common one and takes advantage of an efficient means of determining if two boxes (2d or 3d) intersect that relies on them being axis aligned – hence the axis aligned bounding box, or AABB. If that sounds complicated – don’t worry, it isn’t and I’ll explain it later.

There are many implementations of this available online and various blog posts and tutorials but I didn’t find anything that brought it all together and so what follows is a step by step guide to AABBs and how to sort them in a tree to quickly determine intersections. There is sample code provided in the form of the C++ implementation in my voxel engine and at the bottom of this post I explain how you can use this (just the AABB tree implementation) in your own code. However this post is more about the theory and once you understand that a simple implementation is fairly straightforward (though there are numerous optimisations, some of which are in my sample code some of which aren’t, that can complicate things).

For the purposes of keeping this guide simple I’m going to draw diagrams and talk about 2 dimensional boxes (rectangles) rather than 3 dimensional boxes however quite literally to add the 3rd dimension you just need to add in the 3rd dimension. Wherever x and y apply in the below add in z following the same pattern as for x and y. Hopefully that is clear in the sample code but if you have any questions you can always reach out on Twitter.

What are AABBs?

AABBs are simpler than they sound – they are essentially boxes who’s axes (so x,y for 2d and x,y,z for 3d) align / run in the same direction. The bounding part of the name is because when used for collision detection or as part of a tree they commonly contain, or bind, other boxes. The diagram below shows two simple and compatible AABBs:

simpleaabbs3

In contrast the two boxes shown in the diagram below are not AABBs as their axes do not align:

incompatibleaabbs3

A key characteristic of an AABB is that the space it occupies can be defined by 2 points irrespective of whether it is in a 2 or 3 dimensional space. In a 2 dimensional space the 2 points are (minx, miny) and (maxx, maxy).

This can be used to perform a very fast check as to whether or not two AABBs intersect. Consider the two AABBs in the diagram below:

intersectaabbs3

In this diagram we have two AABBs defined by a pair of points and the result of the following expression can determine whether or not they intersect:

maxx1 > minx2 && minx1 < maxx2 && maxy1 > miny1 && miny1 < maxy2

An important point to note about that expression is that it is made up of a series of ands which means that evaluation will stop as soon as one of the condition fails.

I’m fortunate working in a voxel engine in that objects in my game world are naturally axis aligned: voxels essentially being 3d pixels or tiny cubes. However what if your objects aren’t naturally aligned or are made up of shapes other than boxes? This is where the bounding part of the AABB comes in as you need to create a bounding box that encompasses the complex shape as shown in the diagram below:

boundingaabbs2

Obviously testing the AABBs for an intersection will not result in pixel perfect collision detection but remember the primary goal of using AABBs is in the broad range part of the process. Having quickly and cheaply determined that the two AABBs in the diagram above do not intersect we can save ourselves the computational expense of trying to figure out if two complex shapes intersect.

The AABB Tree

Using the above approach you can see how we can quickly and easily test for collisions between two objects in your world space however what if you have 100 objects? Or 1000? No matter how efficient the individual tests comparing 1000 AABBs against themselves is going to be an expensive operation and highly wasteful.

This is where the AABB tree comes in. It allows us to organise and index our AABBs to minimise the number of AABB intersection tests that need to be made by slicing the world up using, guess what, more AABBs.

If you’ve not come across them before trees are incredibly useful hierarchical data structures and there are many variants on the basic concept (if such things interest you an excellent, if quite formal, book on the subject is Introduction to Algorithms) and before continuing it’s worth gaining a basic knowledge of the structure and terminology from this Wikipedia article.

In the case of the AABB tree presented here the root, branch and leaves have some very specific properties:

Branch – Our branches always have exactly two children (known as left and right) and are assigned an AABB that is large enough to contain all of it’s descendants.
Leaf – Our leaves are associated with a game world object and through that have an AABB. A leaf’s AABB must fit entirely within it’s parents AABB and due to how our branches are defined that means it fits in every ancestors AABB.
Root – Our root may be a branch or a leaf

The best way to illustrate how this works is through a worked example.

Constructing an AABB Tree

Imagine we have an empty world, and so at this point our tree is empty, to which we are adding our first object. As our tree is currently empty we create a leaf node that corresponds to our new object and shares its AABB and assign that leaf to be the root:

treeaabb___1

Now we add a second object to our world, it doesn’t intersect with our first node, and something interesting happens to our tree:

treeaabb2

When we added the second object to our game world a number of things occurred:

  1. We created a branch node for our tree and assigned it an AABB that is large enough to contain both object (1) and object (2).
  2. We created a new leaf node for object (2) and attached it to our new branch node.
  3. We took our original leaf node for object (1) and attached it to our new branch node.
  4. We made the new branch node the root of the tree.

Ok. Let’s add another object to the game world and this time we’ll have it intersect with an existing object:

treeaabb3

Again when we added this object some interesting things happened to our tree:

  1. We created a new branch node (b) and assigned it an AABB that encompassed objects (1) and (3).
  2. We created a new leaf node for object (3) and assigned it to branch (b).
  3. We moved leaf node (1) to be a child of branch node (b) and attached this new branch node (b) branch node (a).
  4. This is subtle but important: we adjusted the AABB assigned to branch node (a) so that it accounts for the new leaf node. If we hadn’t done that the AABB assigned to branch node a would no longer have been big enough to contain the AABBs of its descendants.

Essentially every time we add a new game world object we manipulate the tree so that the rules for branch and root nodes that I described earlier still apply. This being the case we can describe a generic process for adding a new game world object into the tree:

  1. Create a leaf node for the object and assign it an AABB based on it’s associated object.
  2. Find the best existing node (leaf or branch) in the tree to make the new leaf a sibling of.
  3. Create a new branch node for the located node and the new leaf and assign it an AABB that contains both nodes (essentially combine the AABBs of the two located node and the new leaf).
  4. Attach the new leaf to the new branch node.
  5. Remove the existing node from the tree and attach it to the new branch node.
  6. Attach the new branch node as a child of the existing nodes previous parent node.
  7. Walk back up the tree adjusting the AABB of all of our ancestors to ensure they still contain the AABBs of all of their descendants.

Step 2 in the above does beg the question: how do you find the best leaf in the tree to make the new leaf a sibling of? Essentially this involves descending the tree and evaluating the likely cost of attaching to the left or right of each branch you move through. The better the decision you can make the more balanced the tree and the cheaper the subsequent queries.

A common heuristic used here is to assign a cost to the surface area of the left and right nodes having been adjusted for the addition of the new leaf’s AABB and descend in the direction of the cheapest node until you find yourself on a leaf.

Querying the AABB Tree

This is where all of our hard work pays off – it’s very simple and very fast. If we want to find all the possible collisions for a given AABB object all we need to do, starting at the root of the tree, is:

  1. Check to see if the current node intersects with the test objects AABB.
  2. If it does and if its a leaf node then this is a collision and so add it to the list of collisions.
  3. If it does and it’s a branch node then descend to the left and right and recursively repeat this process.

At the end of the above your list will contain all the possible collisions for your test object and we will have minimised the number of AABB intersection checks we had to perform as we will not have descended down any pathways (and therefore all the subsequent children) that could not intersect with the test AABB tree.

In implementation it’s best not to actually use a recursive approach as this can get expensive (and could fail) on large trees. Instead just maintain a stack / list of nodes that are to be further explored  as follows:

  1. Push the root node onto a stack (in C++ I use std::stack)
  2. While the stack is not empty:
    1. Pop from the stack
    2. Check and see if the node intersects with the test AABB object
    3. If it does then either:
      1. If it is a leaf node then this is a match for a collision. Add the leaf node (or its referenced object) to the list of collisions.
      2. If it is a branch node then push the children (the left and right nodes) on to the stack.

Understanding how to iterate over trees none-recursively can be very useful.

Updating the AABB Tree

In most (but not all) scenarios involving collision detection at least some of the objects in the world are moving. As the objects move that does require the tree to be updated and this is accomplished by removing the leaf that corresponds to the world object and reinserting it.

This can be an expensive operation and you can minimise the number of times you will need to do this if you express the movement of your world objects using a velocity vector and use this to “fatten” the AABB trees that you insert into the tree. For example take the object in the diagram below, it has a (x,y) velocity of (1,0) and has had it’s bounding AABB fattened accordingly:

velocityaabbs

How much you fatten the AABB trees is a trade off between update cost, predictability and broad range accuracy and you may need to experiment to get the best performance.

Finally as trees are updated it is possible for them to become unbalanced with some queries inappropriately requiring the traversal of many more nodes than others. One technique for resolving this is to rebalance the tree using rotations based on the height (depth from the bottom) of each node. Another is to balance the tree based around how evenly child nodes divide the parent nodes AABB. That’s slightly beyond the scope of a beginners guide and I’ve not yet implemented it myself in the sample code – however I may return to it at some point.

Sample Code

Finally their is sample code that goes along with this blog post and you can find it in my game engine. It’s pretty decoupled from the engine itself and you should be able to use it in your own code without too many problems. The key files are:

AABB.h – defines a structure for representing and manipulating an AABB
AABBTree.h – header file that defines the entry points to the tree class AABBTree and the AABBNode structure
AABBTree.cpp – implementation
IAABB.h – defines an interface that objects added to the tree must implement

To use the tree you will need to add those four files to your project and construct an instance of the AABBTree class – it’s constructor is very simple and takes an initial size (the number of tree nodes to reserve up front). Any object you want to add to the tree needs to implement the IAABB interface that simply needs to return the AABB structure when asked for. You can add, update and remove those objects with the insertObject, updateObject and removeObject methods respectively and you can query for collisions with the queryOverlaps method.

Useful Links

While researching AABB trees I found a number of useful links and these are below.

Game Physics: Broadphase Dynamic AABB Tree
AABB.cc
Box2D

In particular I found the code in the last two links very useful to read through and was able to base my own code on that, particularly the node allocation.

React Sample App

Having built a number of reasonably large apps using Angular (v1.x) I began to grow uncomfortable with some of its pain points and so started to look for alternatives. As a result I’ve spent a lot of time over the last 12 months with various JavaScript frameworks but in particular I found myself settling on React combined with Redux.

I find I’m an increasingly functional programmer and the idea of the user interface as a clean expression of state appeals to me massively. I’ve also found that when using React I feel like I’m using the JavaScript language itself, particularly ES6, rather than alternatives to what are becoming core language features.

However although the documentation is pretty good I found I started to struggle to find good patterns and practices when I moved away from simple ToDo type apps. As an experienced developer what I really wanted was some guidance illustrated by code in a working app.

To that end I recently build a sample app that illustrates solutions to typical problems you’ll encounter when moving beyond a ToDo app and have started working on a short book to go along with it. Initially I’d intended to do this as a series of blog posts but as I started to write them I realised the structure was not well suited to the blog format. My intention is still to push this out, at least largely, as open source probably under a creative commons license.

As a first step I’ve published an early version of the sample app onto GitHub and you can find it here. Constructive feedback would be very welcome and the best way to get in touch with me is on Twitter. I’ll have more details on the book as the content develops further.

segmentcomparison

A Simple Voxel Engine – Christmas 2016 Project

Happy New Year everyone – I hope everyone reading this had a great end of year break and has a fantastic 2017.

I suspect I’m not alone in that I like to spend a little time over the Christmas break working (in the fun sense of the word) on something a bit different from the day job. This year I took about 4 days out to work on a really simple voxel engine as both the look and constructible / destructible feel of voxels have always appealed to me, perhaps as a result of a childhood playing with Lego. Though bizarrely I’ve never played Minecraft.

The code for the engine along with a couple of demonstrations can, as ever, be found over on GitHub.

I didn’t want to feel like I was writing glue code and so rather than use an existing library I started with a blank C++ file, OpenGL, and an awful lot of ignorance. Now to be fair I do have a reasonable background in C, C++, graphics and systems programming – before this web thing came along I was working with embedded systems and 2d graphics engines using C, C++ and 68000 assembly – but that was back in 1994. I continued as a commercial C++ developer for 4 more years but then found myself working with C# and the first .Net beta via a brief foray with Delphi.

So I was rusty. Very rusty. However I had enthusiasm on my side and persevered until I had a couple of demo’s and some code that I wasn’t too embarrassed to share. The video below is me navigating a voxel “landscape” created using a black and white self portrait as a height map:

First step was some early research and I quickly discovered some really useful resources:

  • GLFW – a great library for abstracting away the underlying hardware and OS and getting you a window to draw in
  • Glad – OpenGL is a strange, strange, place and chances are you will need to use a “loader” to get access to the full API. This web service makes it really easy.
  • GLM – A header only mathematics library based on the OpenGL shader specification
  • Learn OpenGL – tutorial series
  • OpenGL Tutoral – another OpenGL tutorial series

Being conscious C++ had changed a fair bit since my youthful glory days I also skim read Accelerated C++ and Effective Modern C++. I’ll be returning to the latter and reading it in some more depth as I’m sure my code is still pretty stinky – but it works!

Day 1 – I Know Nothing

Armed with my new found expertise I set myself a goal of generating and rendering a landscape based on Perlin Noise but given I couldn’t yet draw a cube I thought I’d better bootstrap my way up. This first day was the toughest and involved a fair amount of staring at a blank screen, cursing, and feeling extremely thankful for the safety of managed environments. However at the end of the day I managed to get not only a single cube on the screen but a set of voxels arranged into a chunk rendering (a chunk is an organisational concept in a voxel engine – collections of voxels) and you can see that below:

2016_12_29_1

I didn’t yet have any lighting so to help me process what I was looking at I did a simple adjustment of the colours around each vertex.

The next step was to display several chunks together. My first effort at this went… badly. Only one chunk was ever displayed. After spending an hour looking for obscure OpenGL problems I realised I’d done something more basically dumb with C++ (we’ve all copied something we thought we were passing by reference right?), pounded my head into the desk a few times, corrected it and hurrah. 4×4 chunks!

2016_12_29_2

Flush with success wine may have been consumed.

Day 2 – Algorithms and Structures

Sitting at the desk with a slightly groggy head – which the wine had nothing to do with, nothing, not a damn thing – I started to ponder how to arrange and manage chunks.  The memory requirements for voxels can be huge. Imagine that each of your voxels takes 16 bytes to store it and that your landscape is a modest sized 1024 voxels wide, 32 voxels high, and 1024 voxels deep – that’s 536,870,912 bytes, better known as 512Mb, of storage needed before you even account for rendering geometry.

It’s clear you’re going to need someway of managing that and for practical usage compressing and/or virtualising it.

I came up with, and by came up with I mean I’d read somewhere and recalled it, the concept of a chunk manager (this came up somewhere in my research), chunk factories (this didn’t come up in my research but seems a logical extension) and a chunk optimiser (not yet implemented!).

The main decision here was how low to go – so to speak. The most optimal route likely involves getting the STL out of the way, pre-allocating memory and organising it in a very specific manner. However that also seemed the route most likely to feel like having your teeth pulled. In the end I decided to go with the path of least resistance and mostly used the std::vector class with pre-allocated sizes where known.

Nothing to see from my efforts yet except the cube still shows but using the new code. Which while not worth a screenshot was a result!

With that out the way I needed a perlin noise generator to implement as part of one of my new fangled chunk factories. I’ve written one before for a lava type effect at some point back when you had to find the algorithm in a book and figure out how to write it yourself. Having no wish to repeat that painful experience I quickly found a great post and gist on GitHub written in C# and converted it to C++.

I hit F5, Visual Studio whirred away for a few seconds, and to my utter amazement my good run of luck continued and I had an ugly but working voxel landscape.

2016_12_30_2

Good times. And good times when you’re on your Christmas break deserve wine.

Day 3 – This Is Far From Light Speed

Without any lighting it was hard to really get a sense of the terrain in the landscape that I could see but before I could do something about that I needed to address some performance issues. Rendering was fine – I was cruising at a vertical refresh locked 60 frames per second. When rendering started. Problem was that even on my 4.5GHz 6700K i7 it took about 90 seconds to generate the voxels and the initial geometry.

Normally I’d advocate measuring before going any further but the issue was self evidently (famous last words…. but not this time) in a fairly narrow section of code so step 1 was a code review which quickly highlighted a moment of stupidity from the previous day: I was calling the perlin noise function 16 times more than I needed to.

I could see from Visual Studio that memory allocation was also sub-optimal as it was occurring on an “as needed” basis but as previously noted I’m favouring clarity and simplicity over gnarly. However Visual Studio was also highlighting another issue – my CPU was only being used at around 15%. The code is single threaded and I’ve got 4 cores capable of supporting 8 threads.

Haha thinks me with my C# head on. This is eminently parallelisable (the clues being in the names “chunk” and perlin noise “function”) and C++ must have a decent task / parallel library by now. Oh yes. Futures. They’ll do it.

Oh boy. Oh boy oh boy. That hurt. Converting the code to use lambda’s and futures was straightforward but then the issues began – turns out there is not yet an equivalent for something like Task.WhenAll in the C++ standard library. I got there in the end after a bit of a deep dive into modern C++ threading concepts (I really didn’t want to use the OS primitives directly as I want to make this multi platform) and solved this with locks and condition_variables.

I’ve tested it on a variety of systems (with different performance characteristics and cores available) and it hasn’t crashed or done anything unpredictable on a variety of different systems but I’m sure there is something wrong with this code so if any C++ experts read this I’d love some pointers.

So now its quicker, about 6 or 7 seconds to generate a respectably sized landscape, but it looks the same and most of the day has gone.

Fortunately adding basic lighting proved much simpler. Simple voxels, cubes, are pretty simple to light as the normals are somewhat obvious and there is plenty of documented examples of using vertex normals inside vertex and fragment shaders to apply the appropriate colouring. A couple of hours later I had ambient, diffuse, and specular lighting up and running and could turn off my dodgy half shading.

2016_12_31_2

A great way to go into New Years Eve and definitely earning of a celebratory brandy. Slightly warmed and in an appropriate glass of course.

Day 4 – This Code Stinks

Old Man Randall (me) fell asleep long before midnight and so I woke up fresh and eager on New Years Day to do some more work. I’d had the brainwave a few days ago to use photographs as the source for landscape height maps using the brightness (whiteness in black and white photographs, calculated perceived brightness in colour photographs) of each pixel to build an appropriately high stack of voxels.

However before I could do anything else the code really needed some work. It had the distinctive whiff of a codebase in which many new things had been tried with little idea of what would work or not. Structure had become scrambled, inconsistencies were everywhere, and commented out attempts at different approaches abound. Not to mention I’d built everything into a single executable with no attempt to separate the engine from it’s usage.

A few hours later and although still not perfect I had something that was workable and set about implementing my voxel photographs starting with black and white. Being a supreme narcissist I selected a photograph of myself from my flickr library and busied myself trying to load it. This proved to be the hardest part – I’d forgotten how painful C++ and libraries without package managers can be (is there a package manager for C++?) with chains of dependencies.

In the end I realised that cimg could load bmp files without any dependencies and implemented a new chunk factory that used that to scan the pixels and create voxels based on their whiteness.

This worked a treat and I captured the video of me moving around the “landscape” that appears at the top of this post.

2017_01_01_1

A great way to finish off and in a burst of enthusiasm I quickly sent the link to my fans. Or fan. By which I mean my mum. No celebratory brandy sadly as structured cycling training has restarted but happiness abounds.

Conclusions and What Next?

A few things struck me throughout this short project that I think are worth collecting and reflecting on:

  • The modern Internet truly is a wonderful thing. The last time I was coding in C++ (about 1998) it wasn’t the Internet of today and things were so much harder. It’s an amazing resource.
  • The development community is amazing. There are so many people giving their time and expertise away for free in the form of blog posts, articles, and code that unless you’re doing something really on the bleeding edge there is someone, somewhere, who can help you.
  • Wow C++ has changed – for the better. It’s still complicated but there’s a lot more available out of the box to help you not make simple mistakes.
  • GPUs are incredible number crunching machines. I’m fortunate enough to have a pretty top notch GPU in my desktop (a 980Ti) but the sheer number of computations being performed to render, in 60 fps, some of the scenes I threw at this code is astounding. I knew in theory the capabilities of GPUs but didn’t “feel” it – I’m now interested where I can apply this power elsewhere.
  • Iterative approaches are great for tackling something you don’t know much about. I just kept setting myself mini-milestones and evolving the code, not being afraid to do something really badly at first. By setting small milestones you get a series of positive kicks that keeps you motivated through the hard times.
  • Coding, particularly when it involves learning, is fun. It really is. I still love it. I’ve been coding for around 34 years now, since I was 6 or 7, and it still gives me an enormous thrill. My passion for it at its core is undiminished.

As for this project and what I might do next. I’ve got a couple of simple projects in mind I’d like to use it with and a small shopping list of things I think will be interesting to implement:

  • Mac / *nix support
  • General optimisation. I’ve only done the really low hanging fruit so far and there is scope for improvement everywhere.
  • Voxel sprite support
  • Shadows
  • Skybox / fog support
  • Paging / virtualisation – with this in mind this is one of the main reasons that scenes are constructed using the chunk factory
  • Level of detail support
  • Simple physics

Whether or when I’ll get time to do this I’d rather not say, I have a big product launch on the horizon and a React book to write, but I’ve had so much fun that I’m likely to keep tinkering when I can.

 

Contact

  • If you're looking for help with C#, .NET, Azure, Architecture, or would simply value an independent opinion then please get in touch here or over on Twitter.

Recent Posts

Recent Tweets

Invalid or expired token.

Recent Comments

Archives

Categories

Meta

GiottoPress by Enrique Chavez