Archived

This topic is now archived and is closed to further replies.

Lithic

A new data structure... CLABT (move over ABT!)

Recommended Posts

Lithic    345
Continuous Leafless Adaptive Binary Tree, what i''m going to call the new idea i came up with today. The Adaptive Binary Tree that Yann uses has some very good features to it which make it an excellent choice of data structures. It also however has some room for improvement. To start with, the ABT is not all-inclusive. Many dynamic objects and particle effects which could overlap over the lines between leaf structures are not included in the tree for this very reason, unless the tree changes dynamically with every movement of an object (this is very bad for framerates). A good example of this is an elevator. An elevator moves up and down most likely crossing over the borders of several nodes, thus making the tree unable to put it in any one node. That over with, on to the CLABT: The CLABT is based on the ABT structure. Nodes are divided in a binary way based on the properties of that particular part of area. For more info there, go research about ABTs. There are no "leaves" in a CLABT. Every node is the same exact structure, capable of holding dynamic objects, particle effects, and any other structure used in the rendering of your level (if dynamic it MUST have a movement pattern, no creatures). When i say any node, i am including the Global root node (used in dividing the level), the two pieces it splits to, and every other node down to the ends of the tree. How do we decide where to put our objects (static and dynamic)? For a static object: The object is checked against the boundaries of the smallest level node in which it resides mostly in. If it crosses one of the nodes'' boundaries plus a defined overlap allowed for each boundary, then it will be checked to see how many nodes it at least partly resides in. If it is partly in only two nodes, the object is split into two along the boundary. Otherwise it is moved up a spot in the node heirarchy and tested the same way there. Once it finally passes the test, the ABT moves on to the next object and repeats. For a dynamic object: The object is bounded in a cube which encompasses it''s full possible range of motion in any direction. This cube is then tested against the node, if there is any overlap, it is tested against the next node up in the heirarchy. Some effects might even be global and be in the root heirarchy. Now that everything is divided into the nodes, the boundaries of the node are made to the minimum possible size which still encompasses everything stored within them. The nodes are then saved to a file on the hard disk, preserving their orientation in the tree and their contents. When used in the game the nodes are loaded dynamically. Any node out of the maximum view range of the player plus the amount they could move in one turn is loaded dynamically into RAM. If a node moves out of range it is deleted from RAM. This makes for no load times whatsoever in the game. The tree is traversed normally, checking for any content in each node level, testing against frustums, and rendering if in view. The entire game could be stored in one level file or multiple. If multiple to avoid obvious load times i would reccomend breaking the levels up by cut-scenes. This encompasses my new idea for a data structure, which I begun coding for my project. Give me some feedback as to what you think. --===LITHIC===-- --===WWW.Decimation.TK===--

Share this post


Link to post
Share on other sites
_DarkWIng_    602
This idea has been "invented" alot of times before(for different verions of KD-tree) and it never realy worked well. You might think about it a bit before you start implementing it. (search for posts about octrees/ABTs for info why is this bad)

You should never let your fears become the boundaries of your dreams.

Share this post


Link to post
Share on other sites
Hybrid    138
You mention moving objects up the tree before splitting, this is not so good, because it means you end up with more objects up the top of the tree than you want. Really you want all the objects at the bottom of the tree so that there is better localisation - which is better for culling and rendering less.

By the way, you also said the nodes are shrunk to encompass all the objects it stores. So there will be empty space within the tree - so how will a moving object be able to insert itself within the tree every time it moves, its possible that you''ll end up with dynamic objects higher up in the tree as well as they''ll cross boundaries of the node.

Share this post


Link to post
Share on other sites
Lithic    345
quote:
Original post by Hybrid
You mention moving objects up the tree before splitting, this is not so good, because it means you end up with more objects up the top of the tree than you want. Really you want all the objects at the bottom of the tree so that there is better localisation - which is better for culling and rendering less.


That is right, i do want more objects of the bottom of the tree for more precise culling, which is why triangle splitting is more effective than moving the triangles into a higher node. I think i''ll have it so that static objects can only be split, not go higher in the tree.

quote:
Original post by Hybrid
By the way, you also said the nodes are shrunk to encompass all the objects it stores. So there will be empty space within the tree - so how will a moving object be able to insert itself within the tree every time it moves, its possible that you''ll end up with dynamic objects higher up in the tree as well as they''ll cross boundaries of the node.



I don''t think you understood what i was saying. If a moving object is in a higher level of the tree, it does not have to reinsert itself, because the higher level is inclusive of its full range of motion. This would be a larger node to test against the frustum, but it would still speed up the game to do a couple extra tests and not draw several dynamic objects (elevators or trains would be several dynamic objects moving together; not drawing a single elevator could result in not drawing at LEAST 18 triangles for a poor-looking elevator). The node of the dynamic object would not change and there would be no reinsertion. The resizing a node to fit its content is done so that it will fail the frustum test more often to speed of framerate.

quote:
Original post by _DarkWIng_
This idea has been "invented" alot of times before(for different verions of KD-tree) and it never realy worked well. You might think about it a bit before you start implementing it. (search for posts about octrees/ABTs for info why is this bad)



Perhaps there were problems with similar trees, but i see no more problems with this tree than i would with any other ABT. Perhaps you could point out these problems.

--===LITHIC===--
--===WWW.Decimation.TK===--

Share this post


Link to post
Share on other sites
_DarkWIng_    602
As Hybrid told you moving objects up the tree is bad. You''ll end up with bunch of objects in root(and other non-leaf) node. Do you think cost of drawing otherwise culled object will outweight cost of their reinsertion into the tree?

You should never let your fears become the boundaries of your dreams.

Share this post


Link to post
Share on other sites
coelurus    259
Things are never reinserted, they are stored with the entire "range of motion" as Lithic explains, like the whole elevator shaft?

I''m not sure whether or not you would gain anything from this, but the tree will become pretty messy. I''m not sure how the elevator-test is done, but if the node is used for it, the elevator could be seen from far away. Still, we can''t be 100% until it has been tested

Only relying on the data structure is bad, you should have some more checks for things to render and I don''t only mean frustum culling. If you frustum cull the little elevator-object, it should work, but there has to be a better way than put it way up in the tree.

Share this post


Link to post
Share on other sites
Hybrid    138
Okay, I see what lithic means by keeping dynamic objects in the smallest node possible but one that encompasses the full range of the objects motion. So you might end up with some lower in the tree and some higher, depending on the range of motion.

But.... that imposes a sort of limitation to the system, since you have to know the dynamic objects possible motion first - e.g. an elevator going up and down. How would a TRUE dynamic object like a player or enemy running around the level fit in? Since you dont know all its possible motion, it would have to be stuck in the top/root node - and that means the root node will have a lot of objects controlled by the player and A.I., and any other 'unpredictable' dynamic objects.

I think really we have a case of an ABT here, but with dynamic objects sort of 'hacked' into it. I think the dynamic object (both predetermined and unpredictable motion ones) side of things needs to be thought through some more.

[edited by - Hybrid on September 4, 2003 8:15:50 AM]

Share this post


Link to post
Share on other sites
duhroach    225
From what it sounds like, you''re just crossing the ABT file structure with some concepts from Ulrich''s Loose Quadtree algorithm.

Essencially the concept is a good one; move larger object''s up in the tree to minimize divides. But as objects are moved up in the tree, their amount of visiblity increases. That is, a 200k mountain range that spans 5 leaf nodes, is moved into the main parent node, and is now being rendered every frame, regardless of what you''re looking at.

From what i can tell, it sounded like your goal was to design a pattern for which dynamic objects could be rendered in the tree effeciently? There''s tons of ways around this. I use a manager system that tracks the larger movement of objects in a scene, and re-inserts them into the ABT as they move from node to node. If an entity spans nodes, it is assigned to each one, with a "pre-render" flag set on it. Ie First-come, First-Render. This process is great, due to the fact that any object can move freely through the world, (without me having to know it''s path) and it''s automaticly added to the culling scheme.

All in all, I''d stick with static data being split as needed, while handling dynamic objects as an insertion factor. Binary Tree''s already have (close to) the lowest amount of checks for insertion / deletion, which means you''re not adding a ton of overhead just to re-insert an object when it moves between nodes.

~Main

==
Colt "MainRoach" McAnlis
Programmer
www.badheat.com/sinewave

Share this post


Link to post
Share on other sites
Yann L    1802
When you are inserting objects based on their possible movement range, you essentially get three main problems: first, as had been mentioned, you have to know the exact extends of the motion beforehand. That''s not always possible. Second, the inserted ''range-object'' will cover a huge volume of space, which is basically empty. Ie. the object itself will only occupy a small subspace, everything else is space reserved for possible movements. But the core definition of a good spatial tree (and that''s valid not only for an ABT, but for pretty much every Kd-tree variant) is to localize the object geometry as tight as possible. You bounding volume around the geometry should only be minimally larger than the geometry itself. In your case, you would have the exact opposite, which would greatly delocalize the tree. And third, since an ABT is a loose and sparse structure (other than eg. a classical octree), it doesn''t guarantee that every subvolume of space will be covered by a node or leaf. In fact, the opposite is true: most empty subvolumes won''t be covered by a node. That''s the actual trick which makes an ABT efficient in terms of culling and traversal. If you add your ''range-object'', you will create huge, empty nodes. That will make the tree very inefficient.

Now, the idea of inserting a dynamic object into the deepest possible node without overlapping is not new. The first spatial dynamic Kd-tree implementation used that principle. But unfortunately, for the reasons mentioned by other posters above, it is not efficient. Most objects will end up in top nodes, creating a very shallow tree. And not only object too large for a child node will end there, but also very small objects striding a node boundary. Imagine an ABT, starting with a large root node, recursively subdivided into two child nodes per level. Now, imagine you have a very small object to insert, that would perfectly fit into a deep leaf or node. Unfortunately, this object happens to touch the division plane used to subdivide the root node in the middle. The result of this being, that you generally won''t find a deeper node able to hold the object without growing it. The small object will end up in the root node.

When I developed the ABT structure, I tried a lot of different approaches to make it dynamic object friendly. Including the method you described. Unfortunately, it didn''t perform very well. I ended up using the method I described in one (or more) of the ABT threads: dynamic local tree updates. A node (including its parent branch) grows along with the object moving, until a delocalization threshold is reached. At this point, the delocalized branch is rebuilt on the fly, starting from the node that hit the threshold. While this method is certainly not perfect, it has proven to be quite efficient in practice (as long as you don''t have 50% of your level geometry moving at the same time).

I think your method would be better suited as an octree extension. A (non-loose) octree will always cover a region of space without creating holes. It won''t delocalize on the insertion of large empty objects either, since it allows the addition of a single object to multiple nodes.

Share this post


Link to post
Share on other sites
paulc    132
Haven''t exactly thought this through yet, but could you reverse the problem and have the object manage its own location in the data structure. For restricted/semi-dynamic objects like lifts, trains etc where their movement is restricted to a known area of space that can be represented as a bounding volume. At pre-process time the object can use this volume to identify the nodes in the spatial structure that it could occupy and store them local to itself. During the objects update, if it detects that it has left the node that is was occupying it could then identify which node it has moved into and re-insert itself into the structure as appropriate.

This might work, but then again could be hideous. Something to think on....

Share this post


Link to post
Share on other sites
Hybrid    138
paulc - but again, that would only cater for objects whose motion was was determined. It would not cater for completely dynamic objects that can be created or moved anywhere in the world.

Getting completely dynamic objects into the tree and moving them around efficiently is the key to creating a great spatial subdivision tree, I guess.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster   
Guest Anonymous Poster
quote:
Continuous Leafless Adaptive Binary Tree


All questions of utility and goodness/badness aside, the name doesn''t make sense.

Any tree with a finite number of nodes has leaves.

Share this post


Link to post
Share on other sites
Hybrid    138
One of the fundamental differences between the octree and the ABT, is that the ABT can have completely empty space which is not covered by any node.

Now octrees are very well suited to dynamic objects as they are regularly shaped and the nodes will be touching their neighbour nodes. This is extremely good for dynamic objects and collision detection, because when creating the octree nodes you can store pointers to their neighbours. This means you can fire a ray through the octree and simply go through it via each nodes neighbours - you don''t have to traverse the whole tree. This is good for dynamic objects as when any object moves out of a node and into another you can easily find the neighbouring nodes to move it into as the node has stored all the pointers to its neighbours when it was initially created.

Now because the ABT has empty space, irregular sized nodes (if the split plane moves and nodes are shrunk) then there is no clear-cut way of storing pointers to neighbours as nodes could have varying number of neighbours on the same edge due to the size of it and its ''neighbour'' nodes. The fact that it may not even have a neighbour due to empty space makes it even more tedious to use the neighbour technique of moving objects around the world.

We need a system that has the best of both worlds - the ABT''s adaptive nature for efficently storing geometry, its clever way of dealing with empty space, while having the neighbour possibility of octrees but without the possibility of having nodes with minimal geometry in (loose octrees can semi-solve that). Anyone upto the challenge?

Share this post


Link to post
Share on other sites
Lithic    345
It could easily be modified to work with an octree. Dynamics with AI would have to be global =/ but still it would work. It would be more effective to split all static objects. Also, to help with the structure, im going to put forth an idea:

An octree could split dynamically in much the same way as an ABT. It would be horribly slow in realtime, but if it was precalculated, it would work great. An octree is very similar to an ABT except there is a split on each plane instead of a split only on one plane. So basically you would have to calculate the split the same way as for an ABT but for all the planes. It would be somewhat slower, but if the tree was predetermined, it would work nicely. An octree's nodes can still shrink to fit the geometry, despite what seems to be popular opinion. All you'd have to do is set two boundaries, one for use with statics, and the other for unpredictable dynamics. The one for statics would shrink to encompass their geometry, and the other would be the octree's actual boundaries. Also... higher level nodes should still be able to hold things. The way an object would be put in a higher node would be if it were a dynamic large to the point where it would not be able to be fit into the lower heirarchy. EG: A particle effect Fire Hailstorm, A HUGE boss creature. This way, dynamics would be reinserted, and statics would stay in the same node, and a very minimal number of large-scale things would be in higher nodes. Any comments/questions, throw em out!

--===LITHIC===--
--===WWW.Decimation.TK===--

[edited by - Lithic on September 4, 2003 10:46:28 PM]

Share this post


Link to post
Share on other sites
coelurus    259
The problem with octrees is that for one box/cube (octree-node), the splits are generic throughout one plane. Yann showed a problem where octrees would split objects that an ABT could get around. If you make the planes arbitrary, you''d just get an ABT where 3 axes are bunched into one node.

If you keep the nodes'' boundaries as extents for dynamic objects, you can get a huge problem. Say you store an entire world in one octree and you got a huge megalo-boss in the middle of the world. This means, it will be inserted into the root node, since the very first subdivision will try to split it. Thus, the boss is determined "visible" over the entire world. That just wouldn''t be too great

Share this post


Link to post
Share on other sites
Hybrid    138
How about the following octree variation? It's slightly the same as lithic's last post, but is more open to dynamic objects

You have an octree but the splitting planes can be moved anywhere to better divide the world, like the ABT does with one plane, the octree does it in three. Yes calculating the split planes bearing in mind the 3 different partitions will take longer, but you end up with an octree that is more adapted to the geometry of the world. Each sub node can be slightly differently and therefore neighbouring nodes may be split differently themselves.

Now for dynamic objects, each node stores the pointers to its neighbours - all the neighbouring nodes at the same level in the tree. Now because nodes can be split arbitarily, then some nodes will have more than one neighbour on each edge, so you store the neighbour pointers as a list. Empty nodes would be flagged as empty and the tree created to it's lowest level along all branches.

At least this way you have the advantage of an octree that is better adapted to the world geometry, but also retains the neighbour links to move objects through the world and aid in collision detection.

objects pointers would have to be stored in all the nodes that the object is in (if it crosses a splitting plane), this would not be too ideal if the object is large and could cross multiple division planes, as it would have pointers to it from multiple nodes all of which would have to be updated as the object moves.

Hmm, there are a few little problems with it, but with a little work and thought perhaps it could be made better.

[edited by - Hybrid on September 5, 2003 6:34:10 AM]

Share this post


Link to post
Share on other sites
Lithic    345
quote:
Original post by Hybrid
Empty nodes would be flagged as empty and the tree created to it''s lowest level along all branches.
6:34:10 AM]



There is a better way to do this part I believe:

Back to my past theory, the information would be stored in the level data, but there would be TWO mins and max for bounding. One encloses all the static geometry only, fitting the scene, the other is the original bounding split. The splits of nodes are done dynamically to get an approximately even number of triangles in each node so there never would be an empty node. However, if there are no dynamics partly or fully in the node, The actual bounds of the nodes are not needed, and you can use the static bounds. Why would this give improvement? Take for instance a node that is larger because it has more spaced out triangles and cannot split further because there is only a few of them. If all of the triangles could fit into smaller bounds the there would be less chance of the node being in the player''s view. If the node isn''t drawn, thats less tris and quicker framerates and it would be just as easy and quick to implement.

--===LITHIC===--
--===WWW.Decimation.TK===--

Share this post


Link to post
Share on other sites
coelurus    259
Remember, that the more you keep to restrained structures, such as an octree, the more you split up geometry, compared to an ABT. Will you actually win on splitting geometry to allow easy insertion of dynamic objects, or is the AABB-adjusting in the ABT better, since you''ll get a lot less splits?
Only experiments can tell, so I think you should get working on your structure before saying much more here unless of course you got new good ideas

Share this post


Link to post
Share on other sites
Karl G    170
(Responding to a few posts up)

I think I''ve got the specs for a best-of-both-worlds tree--one with the ABT''s flexibility and the octree''s pointer-to-neighbour. I''ll work up some diagrams and see how it comes out...

Share this post


Link to post
Share on other sites
Hybrid    138
Karl - I look forward to hearing how things work out with that. The neighbour feature could be very tedious and annoying to implement in an ABT, because there could be any number of neighbours.

It''s good having a thread like this, where ideas for new trees and alterations of trees can be criticised constructively and postively.

Share this post


Link to post
Share on other sites
Karl G    170
Ok well here''s what I was thinking. I kinda hit a deadend after pondering how to implement it but this was my train of thought...


1. All nodes are a rectangular prism. (If I got this wrong then the rest of this post may as well be igored *gulp*)
2. Therefore, assuming that you can kill off the annoying effect of distant objects getting smaller, if you view the entire "world" of boxes from one side you''ll see where things overlap.
3. Being as certian portions overlap all the way down through the boxes, you create a list of rectangles for each dimension (x, y and z) that have boxes contained within them, down to the smallest one with even only 1 box overlapping.
4. Boxes cannot overlap
5. Starting with one side and ending with another (such as +X to -X, +Y to -Y and +Z to -Z) you arrange a list inside each rectangle, in depth order, of the boxes. Note that some rectangles will be overlapping others.
6. This is where I left off...

I hope you can see where I was going with that. Basically you could cast a ray down a "rectangle" and find what it intersects. There are a couple big problems with it that I now see but I hope I got some creative juices flowing Can''t say I didnt try hehe

Share this post


Link to post
Share on other sites
Yann L    1802
Karl, your idea is not that far fetched. The problem with loose structures, such as an ABT, is that there is no direct hierarchical relationship between spatially close nodes. Nodes can practically be in arbitrary positions, two hierarchically close branches don''t have to be spatially near. The opposite is also true: two spatially close nodes don''t have to be hierarchically related in any way. In fact, they could be at opposite sides of the tree !

So, you definitely need a separate structure representing purely spatial relationships, independent of the hierarchy itself. The concept Karl mentioned is basically a kind of PVS for ABT nodes, let''s called it a ''potential neighbour set''. Note the term ''potential'': since ABTs do not have guaranteed neighbours, such a structure could only hold an approximation. But that''s perhaps all you need. For every side of a node (+x, +y, +z, -x, -y, -z) keep a linked list of pointers to other nodes that are potentially close to the respective side of the node. When moving a dynamic object through the tree (growing nodes as needed), this structure would help tremendeously in determining new candidate insertion points for the object. Assuming the tree becomes too denormalized, then instead of rebuilding the whole denormalized branch, you could simply ''snap it back''. The dynamic object would then ''float'', ie. it would be unassigned. Using the potential neighbour sets of the old parent node, you would then perform a local restricted search through the set, trying to get the best fit node for reinsertion of the dynamic object.

Such an ABT extension would certainly work. But the main problems I see with that approach are memory consumption (the potential neighbour lists can quickly get overwhelming in terms of size) and search speed (in very deep branches with tons of spatially near nodes). And most important of all, keeping the structure up-to-date as the tree moves/deforms, at interactive rates, is going to be a major challenge.

Share this post


Link to post
Share on other sites
Karl G    170
"Quotes Yann L's Post"

^^ That's what I mean to say Now that I reread my post a few days after I think I stated it pretty strangely and I contradicted myself, but I'm glad someone was able to make sense of it!

The major problem as I see it is that the sets are only "potential" and cannot really be relied too heavily upon.

-------------------------- New Idea ---------------------------

Ok, new idea time. The purpose of this entire post was to be able to keep track of dynamic objects moving throughout the scene, right? So here's my thought.

Each object has it's own node (with possible subnodes if it is complex). As this object moves, it is migrated around the tree's other nodes... And now for some ascii art.

// Karl's Wonderful ASCII art!

|---------A|
| |-B| |
| |--| |--C|
| D | |
|------|---|


Each "node" represented by a box has a label in the top righthand corner. The largest one, A, contains B, C and the very small (object box) D. D represents our dynamic object. As D moves around, it can become incorporated into B or C when it moves inside, and therefore will migrate further down the hierarchy. When it leaves a space, it can migrate back up.

---------------------- Another Thought ---------------------
This was just a random thought I had when thinking about the problem of constructing neighbours. Why would it be so hard to cast a ray through the hierarchy? I mean, isn't that what you do when you check for culling procedures? Just check for which nodes are visible with no (or a very small) camera FOV in the desired location/direction.


Ok so those are my big thoughts for today. It's time for more homework...

*edit* misworded a sentence

[edited by - Karl G on September 9, 2003 9:55:10 PM]

Share this post


Link to post
Share on other sites