Cube/Sauerbraten internal representation, OCTree vs AABBTree

by Sugoi-Baka on 08/16/2004 12:47, 2 messages, last message: 08/17/2004 19:35, 2161 views, last view: 05/04/2024 19:12

On the about page (http://wouter.fov120.com/sauerbraten/), it is stated that "the world consists of an octree..."
Is the world really represented with an octree or does it use the binary variety of axis aligned bounding box tree?

From my experience (which given, isn't so deep, surely lower than Aardappel), that a binary tree representation is usually better than a real "octree" representations due to certain aspects.
1. A binary tree is much easier to mentain.
2. Considering an object needs to split a node, splitting a node in two is simpler than splitting into 8. Same in case nodes need to be joined.
3. Ray tracing in binary trees is easier, just need to check if the ends of the rays are on either side of the splitting plane, like a BSP.
4. In case a collision test is in a small area, the number of subnodes needed to check is smaller. However, if it encloses many nodes, the number of tree nodes needed to check is higher.
5. It seems like except for #4, every issue that exists in a AABTree also exists in a normal Octree (like the question when to join/split or how to traverse) so the solutions found for an Octree should also work for an AABTree (upper/lower bounds for object counts, timestamps to reduce collision test with same object etc)

Just as Aardappel stated in the coding guidelines, "keep it simple". Axis Aligned Binary Trees are simpler than Octrees.

I might completely out of my league here and maybe what I wrote is outdated already, but if it can help making this very cute project even better, then my work here is done.

   Board Index   

#1: not really

by Aardappel on 08/16/2004 21:12

an AABB tree is mostly used for irregular geometry. What is different in Sauerbraten is that the world geometry IS defined by the octree (not merely contained in it).

To your points, octrees are really simpler than AABB's, because the octree's geometry is entirely on power of 2 boundaries. In fact, the octree's coordinates are not even stored anywhere in memory (except when sent to the GPU), they are computed on the fly. This makes all algorithms a LOT simpler compared to dealing with arbitrary boxes as in AABBs. Also, an octree in terms of splits is equivalent to an AABB, just that you have 3 splits at once on each level of the tree.

Look at some of the code involved in sauerbraten, it is simpler than an AABB could ever be.

And of course sauerbraten could never be made with AABBs in the first place, because the whole engine is structured around space subdivision rather than encapsulation.

reply to this message

#2: Re: not really

by Sugoi-Baka on 08/17/2004 19:35, refers to #1

Interesting indeed.
Actually I have thought of the fact the world is defined by the tree, and about that I agree. What I meant, in short, is instead of using a split to 8 each time, just split in 2 each time, and keep everything very similar to how it is currently.

Hope this makes it clearer.

reply to this message

   Board Index