Loose Octrees

As wished by one of my fellow readers, here's an article about loose octrees. A loose octree is an adaptive spatial subdivision approach, which is very easy to implement and gives pretty good performance.

Basics

Usually, an octree subdivides the scene recursively into increasingly smaller cells. Let's take a look at this in 2D:

octree

As you can see, it subdivides where the geometry is. Note that in a normal octree, the object which is slightly larger than a cell would either:

  • end up in the parent cell
  • be put into the two cells it overlaps

This is not really a problem, but it can be easily worked around by relaxing the bounds slightly. This is already the main idea behind the loose octrees: You relax the bounds to be twice the size of the object. Then, you only sort in by the centre of the bounding box, so one object always ends up in a single cell.

Here you can see a single cell of the octree, with its corresponding loose bound.

The loose bound is exactly twice as large as the cell itself. This gives us an important property: If we have an object which is no larger then the cell itself, and its centre is inside the cell, we can guarantee that the object is inside the loose bounds. Sorting in means that we just need to check the size, and the centre, instead of checking for overlap as we would have to do with general octrees. The only difficulty that arises is querying this tree, as we have to check against the relaxed bounds now.

Here you see two cells (red and yellow) with their loose bounds.

For the query point, we have to check both cells, as the point lies inside the relaxed bounds of both cells. That's it basically.

Implementation notes

Some implementation notes:

  • You can store the whole tree in an array, instead of storing 8 pointers per node. Just store an offset into the array, and per node you store only:

    • Object list
    • Bounds
    • Offset
    • Pointer to the array structure (can be derived from the offset, if you can guarantee that the array starts right after your control structure)

    This gives you a very tight storage structure.

  • Checking for the object size: If your octree is a perfect cube, you can just check the length of the diagonal. In other cases, I'm currently using a dot product of the object diagonal onto the cell diagonal, and comparing this¬† seems to work great so far for non-cube-shaped octrees. For non-cube-shaped octrees, just compute the half-sized bounding box and check whether the object fits. If it is axis aligned, this is very easy.

  • You need to bound the scene before starting. That's no big deal, as you can easily prune the top levels, as long as a node has exactly one child, you can use that child as the new root.

References

I didn't invent this on my own, but rather based it on "Spatial partitioning with 'Loose Octrees'" by Tatcher Ulrich, which you can find on his web site: http://www.tulrich.com/geekstuff/partitioning.html. I'm pretty sure this is the original source of this idea.

Boost 1.37 has been released

Boost 1.37 has been released, as part of their new 3-month release cycle. So grab it while its hot. For build instructions on x64 windows, you can take a look at an older blog post. Only changes I've seen so far is Boost.Jam building works even with parentheses in my PATH, and running tools\jam\build_dist.bat does quite a bit more than it did previously (it builds Quickbook.exe). The binary can be found in toolsjamstageboost-jam-3.1.16-1-ntx86. The rest seems to work just fine.

Visual Studio 2010 preview released

Today Microsoft released a preview of the Visual Studio 2010 with partial C++0x support. This should be also based on their new, Phoenix based compiler, and brings the most important features like auto, rvalues and lambdas. There is a post about some of the new features at the Visual C++ blog. Moreover, it seems to get some parallel helper library, similar to the thread building blocks, both for managed and for native code. Looking forward to this as well.

Great time to be a C++ developer right now :)

The quest for the right UI toolkit

Graphical user interfaces are not really a new invention, and still, I don't see that any vendor has come up with a really good toolkit for creating GUIs. What's taking them so long, and where are we actually heading with the current user interface development?

State of the nation

Currently, there are two major kinds of approaches: One are declarative user interfaces, the other is what I call procedural interfaces. Procedural interfaces is what Qt, GTK, FLTK, wxWidgets, WinForms and quite a few other toolkits give you. On startup, some code like "create a button, add to layout" is executed. For creation, you usually use some designer tool which creates this procedural code and hides them from the developer, as it tends to be extremely ugly.

The nice thing about fully procedural interfaces is that they are easy to create on-the-fly. The not-so-funny part is that the UI creation code is often interwoven with the application logic (event handlers, anyone?). On the desktop, these kind of toolkits are very popular, as they don't require much resources during creation and easily support custom widgets (the "direct rendering" mode is usually quite sophisticated).

The other kind of toolkits use are more or less declarative approach. The most successful UI toolkit out there -- HTML (just think about how many web sites we have!) -- is fully declarative, unless you start using JavaScript, which adds some procedural creation as well. The advantage is that the UI itself is totally decoupled from the logic. The only desktop solution that uses this approach is -- as far as I know -- WPF. This is actually quite a shame, because I consider the declarative approach much more suitable for UI development; after all, the interface is usually static. Moreover, by having the code separated totally from the UI, you can easily move around UI elements without having to update the code. A good example is a context menu: In WPF, you can describe it with a small XAML snippet and load it, giving the UI designer a chance to rearrange the items. In other languages, you would create it at runtime, forcing the designer to rearrange it directly in your code.

Of course, this only covers the cases where you can live with the user-created widgets. For custom widgets, there is basically no real choice besides having a fully procedural painting engine. For this, Qt's QPainter is actually very nice example: It is a really clean, low-level drawing interface. I'm not so sure that a more scene-graph oriented approach is really suited for the low-level drawing, especially performance wise -- think about creating a plot with line segments vs. drawing the line directly.

Wish-list

For the future, I wish that the various vendors can agree on some standard -- similar to HTML -- for declarative UI development. The display-engine for it can be different for each platform (I have no problem with widgets looking differently, as long as the layout engine can cope with it). For low-level drawing, some kind of minimal draw toolkit should be provided (similar to QPainter) with a specified minimum set of operations.

The major problem will be the programming language for all of this; something like JavaScript (with C interop) should do the trick though. Until then, I think I'll try to use WPF for most of my future projects on Windows, as I'm really pleased with the results so far. I didn't write custom widgets with it though, this might very well change my opinion on the subject :)