CODEWITHSUNDEEP
c++algorithmmemorytreeoctree
tomriddle_1234
tomriddle_1234

Reputation: 3213

What's the most storage efficient Octree structure for reconstruction?

I've coded a full octree implementation without too much optimization for 3D reconstruction, however, the tree structure contains too many pointers, and cannot support more than 256^3 voxels.

Theoretically, for a non-tree structure if I used a vector<bool> which uses ~1 bit per voxel, this would be more acceptable because the non-tree structure could support 2k^3 with 8GB memory.

However an optimized octree structure should be able do equal to or better than this, since:

  1. It shouldn't have to store every voxel, since condensation can allow compression of nearby, same-value voxels.

  2. It shouldn't use too many pointers, since pointers themselves uses a fair amount of bytes already.

  3. The octree must have a fairly low node/voxel ratio.

For a full octree the node number could be calculated as (s^3 -1) / 7. The s is the volume resolution, which is a power of 2. For example if s = 4, I'd need 1 + 8 = 9 nodes in the octree to represent a 4x4x4 grid of voxels.

Does anyone know of an octree implementation in C++ that meets these specifications?

Upvotes: 2

Views: 4838

Answers (1)

Thelvyn
Thelvyn

Reputation: 264

I think octrees are the way to go but children nodes should be built only if needed (at least one voxel is set). Moreover, compression should be used. Often adjacent voxels have same values and thus RLE compression seems to works well. This is explained in this thesis http://www.terathon.com/voxels/

Upvotes: 3

Related Questions