A new data structure... CLABT (move over ABT!)
Author
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===--
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.
You should never let your fears become the boundaries of your dreams.
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.
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.
Author
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===--
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.
You should never let your fears become the boundaries of your dreams.
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.
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.
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]
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]
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
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
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.
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.
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....
This might work, but then again could be hideous. Something to think on....
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
