Performance of positioning voxels in an octree/quadtree

Question

This is something I've been thinking about for the past couple hours. This is a mind exercise.

So I learned what octrees were today! Very interesting! I've been thinking through how to implement an octree that resolved to a voxel.

My biggest issue I can't wrap my head around right now, is referencing a position in the octree.

Disclaimer: First, I'm going to be using quadtrees in a 2D plane to visualize my problem. Second, I do not understand the correct jargon here, I'm going to assume any subdivision in an octree that is a parent is a "branch" and any subdivision that is only a child (in this case it resolves to a voxel) is a "leaf". Third, I'm going to number each space in a branch of a quadtree left-to-right top-to-bottom {1,2,3,4}

Let's say I have an quadtree that defines a 16x16 unit space. In location [16,16] I have a voxel stored.

4->4->4->4

Now say we add a voxel to position [4,4]. (Note, we start at zero)

1->4->1->1
4->4->4->4

Now let's say I want to check [16,8] to see if a voxel is stored. Using the previous method we would technically traverse these branches:

4->1->1->1

However 4->1 has not been allocated with any data so it is empty. (it does not subdivide because it is not in use).

My question becomes this, how could I quickly traverse the quadtree to find the voxel?

My first and easiest method would be travelling down the branches in the format I used above.

// Pseudo-code
Class Quadtree {
Quadtree Parent;
Quadtree c[4]; // children
};

Quadtree test1;
test1.c[4].c[4].c[4].c[4];
Quadtree test2;
test2.c[1].c[4].c[1].c[1];

The issue here is that voxelArray[16][16], voxelArray[4][4], or voxelArray[16][8] is much faster. Using a much larger quadtree (256x256) would increase the depth (from 4 to 8). Where nested arrays are still 2 memory operations. (Note, for the quadtree, in reality we would be using something of an accessor and checking to make sure the childs existed with conditional logic)

My second thought was to store the quadtrees as voxels themselves. For example, say we have an 2x2 array, empty it would look like

{0, 0, 0, 0}

At position [1,1] we would add a voxel and it would become

{0, 0, 0, 1}

If we were to store the quadtree it would look something like this

{1/*q*/, 0, 0, 0, 1}

Take this to a 4x4 and

{0/*q*/, 0, 0, 0, 
 0/*q*/, 0, 0, 0, 
 0/*q*/, 0, 0, 0, 
 1/*q*/, 0, 0, 1}

Although now you can access the data directly, you've lost the memory compactness of the quadtree and you still perform many logic operations. IMO this would only work well if you had big areas of 0s and small groupings of 1s.

By storing voxels in a quadtree/octree, you gain performance when looping through them all, but lose performance when directly accessing them.

Answer 1

You can compute a quadkey and then hash each voxel. The idea is to reduce the dimensional complexity. You can look for example for hamiltonian path or z curve or a hilbert curve. This path traverse the plane completely but it's technically still a curve.

Answer 2

This is more of an extended comment than an answer. It might be helpful to you though. Or it might not. Your example:

{0, 0, 0, 0}

does not illustrate an empty quadtree, it illustrates a quadtree in which all 4 quadrants have value 0 at the first (and only) level. This:

{}

illustrates an empty quadtree. This:

{0, 0, 0, {1,0,1,0}}

illustrates a quadtree in which 3 quadrants are all 0 and the fourth is a chess-board (albeit a small one). This:

{{1,{1,0,0,0},0,{1,1,1,{0,0,0,1}}}, 0, 0, {1,0,1,0}}

is beginning to get tricky but you get my drift by now.

In some languages (eg Lisp, Matlab, Mathematica) these illustrations can be directly implemented and manipulated. In many languages you'd implement a quadtree as a collection of pointers and/or values.