How to use a quad/oct tree for a block world

Question

I have been messing around with octrees and quadtrees for the past couple of days. I can build them, iterate them, and spit out information that I need. I also know they are very useful in collision detection, where you take the screen and subdivide it into smaller sections to be able to detect movements on the screen in specific sections rather than just going over the whole screen all the time. However, I can not fathom how an octree or quadtree could be used to generate a cube type world.

Here are some ideas that I have been thinking about:

1) You use the quad/oct tree to subdivide a set cube (10x10x10), and subdivide it until at-least one leaf is uniform; you then delete all other leafs that are not uniform, giving you variant sizes of the cube.

2) You subdivide a point in space (x,y,z) until you get a cube that has at-least one leaf that is all the same size, or reached a depth of the node, and use all those positions (x,y,z) as a position for the different type of blocks.

Can anyone explain the logic behind using an octree, or quadtree in building such a 3D environment? Is it based on x,y,z or is it based on a constant cube measurement? I am very unsure on how to proceed.

Answer 1

Octree's are really help you focus on keeping your cube world chunks divided into equal portions. The trick that they play is that as you keep feeding in cubes into the Octree branches you are automatically subdividing these into pieces that you can later extract on a proximity basis (ie Chunk01(128,0,0) Chunk02(256,0,0) etc..)

As you store the cubes into the octree you also define their "type" (material or some sort of enum that describes them). By doing this you also allow the Octree to group these cubes together if they become neighbours (ie grass, stone, sand etc). This then enables the octree algorithm to handle some of the intelligence for you in around how to collapse / condense these into 1x larger square/rectangle primitive enabling you to reduce your cube count.

At the end of the day you have two approaches to the cube world, the first is you want the end user to believe that you made the world 1x cube at a time but in reality you're actually merging your mesh/vertex count to give that illusion as a chunk of a surface is really just 1x big mesh and not 100's of cubes. It's only when the user interacts with the cube (ie remove/add) that you recalculate your mesh and bring the illusion of multiple cubes into reality ..but then you immediately swap it back out for a giant consolidated mesh.

Once you have got your octree running and you have your chunks consolidating down into single mesh forms (by feeding an array of vertex's into the GPU buffer) you then also have to do some additional work outside the octree around culling. There's a whole bunch of ways you can do this, volume culling (ray tracing) is typically what i've found most recommend but i think this could be done better though.

In my example here: https://vimeo.com/71330826 i basically approach it differently, in that given I know where the camera centre point is and I also track which direction the camera is facing i then basically use this as a proximity focused culling whereby if the chunk in question is behind the camera i destroy them reducing my GPU load as I go.

Also you'll note that each "Chunk" still has its face still visible on the outside, in that I cull the inside of each chunk from being created but given each Chunk is handling its own workload i still render the actual chunk "walls" beneath the camera... that I've later fixed by also keeping track of the Z depth of the user and the camera bounds

Answer 2

Quadtrees are 2D, so it really wouldn't make sense to use them to represent 3D space.

There are a variety of ways to use octrees. The implementation is certainly simpler if you use a fixed number of constant- and equal-size cubes. However, this is almost certainly not necessarily the most efficient implementation, and quad/octrees are all about efficiency.