General Octree question: What do you actually store?

Question

Ok, So I'm experimenting with various terrain generation methods, primarily in Unity, but i'll admit to not use all its features because I started learning about Game Dev in XNA YEARS ago. So, I made a blocky setup like minecraft several times, and made it ineractive. Kool Beans... I did it in chunks, not an Octree method. I've also had a broken version of Marching cubes, but it really wasn't broken, it made the look I was going for at the time.

So I've never really worked with Octrees, and I started reaseaching Dual Contouring and Surface Nets, and a lot of em talk about Octrees. I get the idea logically, but I kinda don't understand some basic "Mechanics" of Octrees, and finding "basic" answers to some of these topics is rough.

So, sticking really to just Octrees, what kind of data to really store in em? I mean, I get I literally could break up a 3D array of strings, but I'm asking about best practices and practicality. I've been using an array of bools generated by another object, really because I'm really trying to make something that does more "computing" than "hashing", and I was thinking bools would be the smallest type to store if I'm going to "blow it up" with other techniques.

So, when I first create this bad boy, and give it a 3D array of data, Do I really go through a method of recusivly testing each value before I "break" the "Master Node" into "Children nodes"? Or Do I start by testing each value in pairs, building Up to larger children nodes?

Any other pointers would be appreciated.

Answer 1

Octrees store data, indexed by a 3 dimensional position. That data could be a reference to an object, reference, bool, or whatever you need.

Inserting items into an Octree is typically done from top down. You have a maximum number of items per cube, once that maximum is reached, the cube is split into 8 (hence the oct prefix in Octree). When splitting, the items from the parent cube is distributed into the 8 new children (octants). If you know you're going to have a large number of items inserted right off the bat, you can pre-allocate the Octree with an initial depth of nodes. Pre-allocating can speed things up when inserting items, since there's a performance hit when splitting a parent and reinserting its items.

However, balancing node max item count and depth is something you'll have to test out for your needs. The balancing is between adding new items and finding existing items. If you don't have a lot of depth, adding new items is rather fast. However, that means you'll have more items in each node and that means searching through all those items when trying to find items closest to a specific position.

Best thing you can do is to implement an octree and play around with it. Hook up some performance indicators so you know what effect your changes are making. Get a good idea of how you're going to use it. In reality, using an octree for a minecraft-esq voxel game is overkill. Since cube voxel positions are exactly predictable, it would be much faster to implement a chunk-based index to a specific cube, instead of using an octree to locate the cube.