# What are the time-efficiency characteristics of these voxel data structures?

Real-time, high-resolution voxel raycasters tend to use one of the following optimising data structures in order to achieve interactive frame rates. What are the pros and cons to these, and what other approaches are you aware of?

• Octrees
• KD-Trees
• Uniform 2D grid with run-length encodings for 3rd dimension (as used in Voxlap)

I am primarily concerned with their impacts on time efficiency rather than space efficiency, but feel free to respond on both aspects. This includes not only raycast time, but also reconstruction time following CSG ops.

I am interested specifically in real-time performance on the CPU, so please don't suggest that I skip the above in favour of GPU-centric volume rendering approaches which may not require these optimisations; those aren't of interest to me at this time.

-
Isn't an Octree a 3-dimensional KD-tree (K = 3)? – stephelton Jan 13 '12 at 4:38
@stephelton An octree is what it's name suggests, a tree with exactly 8 nodes at any given level. It represents a subdivision of 3D space caused by exact bisection of the given (usually cubic) space along planes perpendicular to each of the x, y, and z axes, leading to 8 children. A KD-tree is a tree which (in any number of dimensions) is split into just 2 subdivisions at any given level, via a single plane along an arbitrary axis and at an abitrary position t along that axis, within the volume described. Check wikipedia for diagrams. – Arcane Engineer Jan 13 '12 at 14:00
thanks for clearing that up. – stephelton Jan 13 '12 at 19:46

The octree vs. kd-tree debate seems ancient; as I recall I've seen both sides argued well. I can't speak about KD-trees with much experience, so I can only provide half the answer. That said, I know many optimizations that can be made to the Octree data structure, these could help you in your research, and are probably relevant:

Parametric Traversal (An Efficient Parametric Algorithm for Octree Traversal by J Revelles): I hear that similar optimizations exist for kd-trees, not sure how well they work. But for octrees the method described in this paper is fast even on the CPU, and I happen to know it's trivial to rewrite as optimized SIMD code. So be on the lookout for a similar thing. On that note,

SSE/NEON/Altivec: When looking into implementing both raycast and simple top-down traversal methods, see how well they vectorize. I wouldn't rely on the compiler for this, since it's such a specific and critical problem domain with so many nuances; in fact, I tend to lean towards writing at least my top-down routine in inline assembly for good measure. Beware of dodgy code-gen around intrinsics; spitting out "movups" everywhere is not unheard of.

Cache Coherence: KD-tree nodes are points with two subnodes each. Octree nodes have 8 or more; the result is that, while KD-Trees as implemented naively are easier, octrees are trivial to rewrite for better cache coherence. A cursory glance at google reveals some variety of methods described or advocated for cache-aware KD-tree optimization, only a few being pointer-less. With octrees, the way to go seems to be to store an integer offset in each node and use it to index a "node pool", which stores each group of 8 children in their own block. This, I've found, is fastest by at least an order of magnitude, and I don't see an equivalent boost coming from blocks of 2 subnodes. But you're welcome to try :D.

Since you're doing volume rendering, you may also want to check out Jon Olick's SIGGRAPH 2008 presentation on SVOs, from the "Beyond Programmable Shading" talk. Just find the link on his youtube demonstration. Aside from describing a structure similar to what I've outlined, it has a nifty optimization in it called "depth advance". The idea is to start the raycast close to the z-buffer of the previous frame, taking advantage of temporal coherence. Again, I don't know if this is possible with KD-trees, particularly since they don't subdivide along the z-axis and parametric traversal is likely harder, but you're welcome to try :D.

I don't mean to advocate one method or another, just pointing out that the basic algorithm is only as good as its implementation, and there are a lot of subtleties at play here.

-
Agreed re the subtleties. Not a bad point about KD tree vs octree cache-coherence, although it's a bit of over-simplification of the problem, since it all depends on how you allocate your memory. Laine and Karras's SVO paper uses a custom allocator for this reason, and very smartly uses a 16-bit short pointer to reduce the cost of octree nodes while maintaining all the benefits of octrees. – Arcane Engineer Jan 13 '12 at 13:47
Thanks for that! Using a custom allocator as well, but I've been using an integer offset (something like: (parent-child)/sizeof(node)); I've looked into using a short, but just couldn't find any good reference on the feasibility of that for larger trees; my structs are very big anyway (32 bytes aligned, since I'm using them for >9-channel brickmaps with some extra data per node for faster voxelization) so it likely wouldn't matter. I guess while we're on the subject, it might help us if the OP mentioned what size grid he was using, and what sort of data per voxel ;). – vpostman Jan 13 '12 at 19:39
Upvoted for the useful info, must have slipped my mind before :D. – vpostman Jan 13 '12 at 19:48
• Octrees
• KD-Trees

Both provide ~around log time complexity to hit the wall yet, well implemented octree traversal apparently gives a little edge; however, KD traversal is simpler to implement.

in favour of GPU-centric volume rendering approaches

I would love to test such GPU VR; in fact, for higher quality interactive rendering & bigger data-sets the best volumetric ray tracer running on dual x5670 outperforms any GPU setup I've tested so far.

-