Indeed :)

Curious, did you use any other information or was this a wild guess?

As a side note, if anyone wants to go into more depth, Samet's "Foundations of Multidimansional and Metric Data Structures" (http://www.amazon.com/Foundations-Multidimensional-Structure...) is an extensive survey of a lot of spatial data structures.

The article sensationally positions this as some incredible breakthrough that the "old guard" of gaming is trying to suppress. More likely, the code works, but has limitations -- the same limitations that led old guard luminaries like Carmack to defer the idea for another few years.

As others have pointed out, voxel-based games have been around for a long time; a recent example is the whimsical "3D Dot Game Hero" for PS3, in which they use the low-res nature of the voxel world as a fun design element.

Voxel-based approaches have huge advantages ("infinite" detail, background details that are deformable at the pixel level, simpler simulation of particle-based phenomena like flowing water, etc.) but they'll only win once computing power reaches an important crossover point. That point is where rendering an organic world a voxel at a time looks better than rendering zillions of polygons to approximate an organic world. Furthermore, much of the effort that's gone into visually simulating real-world phenomena (read the last 30 years of Siggraph conference proceedings) will mostly have to be reapplied to voxel rendering. Simply put: lighting, caustics, organic elements like human faces and hair, etc. will have to be "figured out all over again" for the new era of voxel engines. It will therefore likely take a while for voxel approaches to produce results that look as good, even once the crossover point of level of detail is reached.

I don't mean to take anything away from the hard and impressive coding work this team has done, but if they had more academic background, they'd know that much of what they've "pioneered" has been studied in tremendous detail for two decades. Hanan Samet's treatise on the subject tells you absolutely everything you need to know, and more: (http://www.amazon.com/Foundations-Multidimensional-Structure...) and even goes into detail about the application of these spatial data structures to other areas like machine learning. Ultimately, Samet's book is all about the "curse of dimensionality" and how (and how much) data structures can help address it.

In the late 90s at Naughty Dog, I used Samet's ideas (octrees in particular) for collision detection in the Crash Bandicoot games. In those games, the world was visually rendered with polygons, but physically modeled -- for collision detection purposes, at least -- with an octree. The nice thing about octrees is that they are very simple to work with and self-calibrate their resolution dynamically, making them very space-efficient. Intuitively, a big region of empty air tends to be represented by a handful of huge cubes, while the individual fronds of a fern get coated with dozens or hundreds of tiny cubes, because there's more surface detail to account for in the latter example.

I think the crossover point I mentioned earlier will come when GPUs become general-purpose enough to allow massively parallel voxel rendering implementations. That's what surprised me most about this article: they crow that it's a CPU-only technology... why? GPUs excel at tasks involving vast amounts of relatively simple parallel computation.

Prior to the crossover point, we'll see a bunch of cool games that use voxel rendering primarily for gameplay reasons. These games will look chunky compared to their polygonal peers, but will offer unique experiences. Minecraft is a good example. (I'm assuming it's voxel-based, but don't really know.)

If the kind of query you are interested in running is a "K Nearest Neighbor Query" (that is for a give point give me the K nearest objects) you should also consider looking at metric trees. To have a metric tree you must have a metric function which takes two objects and returns a distance between them. The distance must satisfy:

   1. d(x, y) ≥ 0 (non-negativity)
   2. d(x, y) = 0 if and only if x = y (identity of indiscernibles)
   3. d(x, y) = d(y, x) (symmetry)
   4. d(x, z) ≤ d(x, y) + d(y, z) (triangle inequality).

Metric trees can be highly useful for data which is either highly dimensional (ie having greater than 3 or 4 dimensions) or non dimensional (like strings for instance DNA sequences).

The M-Tree is probably the most generally useful metric tree: http://en.wikipedia.org/wiki/M-tree

If you data is static or only updated very infrequently you should use an MVP tree. It is probably the best static structure, closely followed by Sergey Brin's GNAT structure.

MVP Tree: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.43.7... GNAT: http://infolab.stanford.edu/~sergey/near.html

Finally for some data (like strings) it can be very expensive to calculate the distance function. Therefore, there is another set of structures which relax the triangle inequality and are "near metric" trees. These can be useful for pruning your search space.

For more info on metric data structures see: http://www.amazon.com/Foundations-Multidimensional-Metric-Da...

If you want an overview, the bible right now is Samet's Foundations of Multidimensional and Metric Data Structures:

http://www.amazon.com/Foundations-Multidimensional-Structure...