DynamicAABBTree: about internal nodes.

[SemiSober]

Hi, i took a look at dyn4j implementation of dynamic AABB tree, the DynamicAABBTree class, i am confused by this piece of code :

Code: Select all

      while (n.parent != null) {
            // check if the current node the left child of its parent
            if (n == n.parent.left) {
               // it is, so check if the right node is non-null
               if (n.parent.right != null) {
                  // it isn't so the sibling node is the next node
                  n = n.parent.right;
                  nextNodeFound = true;
                  break;
               }
            }
            // if the current node isn't a left node or it is but its
            // sibling is null, go to the parent node
            n = n.parent;
         }


it seems that a node which has a child ( if (n == n.parent.left) ) might have not sibling(if (n.parent.right != null) ).
How it is possible in AABB Tree ?

// if the current node isn't a left node or it is but its
// sibling is null,

so far as i know, it is in conflict with the insertion strategy and AABB tree must be complete tree, each non-leaf node must have two child. can someone make it clear ?

thanks

[William]

So this is from the detectNonRecursive method. This method is doing an iterative stack-less traversal of the tree to find intersections. The benefit over using a stack or doing recursion is just the space savings. That said, take a look at the detect method for a much clearer (recursive) implementation of finding the intersections.

The code referred to above is used to backtrack to the next node to test once we've reached the left-most node of a branch. The next node to test will always be the first right node of a parent of the current node.

So for example:

An Example Binary Tree

download.png (2.34 KiB) Viewed 7521 times

Imagine we are on the node with value 1. When we run that code, we look at the parent node (value 2). It has a right node (value 4) which we then select and break out of the while loop. When we reach that code again, we'll be on the node with value 3. It's parent (value 4) doesn't have a right node, so we skip that node and keep walking up the tree to the node with value 2. On the next iteration, we find that the node with value 4 is not the left node of its parent (value 2), so the loop continues. The node with value 2 is the left node of its parent (value 5) and it has a right node (value 7) so that node is selected next.

Hopefully that's makes it a bit clearer on how its traversing the tree.

William

[zoom]

Great explanation, thanks.

[SemiSober]

thank you for reply, i exactly know what the function do, my question is here :
Why do you assume this situation(the image you have given, node 4 which has just one child) of tree ?

How can a AABB tree, which is a Complete Tree be constructed like this?

assume these objects:


the tree related to this situation would be like this :



if we would add one object, actually we do not insert One Node, but Two Node.
and the same operation for removing, remove two node when we want to remove an object from stage.

thanks

[William]

This is just the standard way to do an iterative stack-less traversal of a binary tree, balanced or not. Trees in general are never guaranteed to be balanced unless balancing code is present. Your picture is of a balanced binary tree.

That said, dyn4j's DynamicAABBTree is a balanced tree, however you still need this logic. For example, take your picture and remove node E. This is still a balanced tree, but the code in question must still be present to continue to node B.

Another example from here is node with value 19. We need to walk up the tree until we reach node with value 50 to continue.

Sample AVL Tree

251px-AVLtreef.svg.png (5.62 KiB) Viewed 7498 times

Adding and removing nodes is done by a, or a series of, rotations walking up the tree from the insertion or removal point to keep the tree balanced.

William

[SemiSober]

i am confused, can you present a picture of scene related to this tree :

[SemiSober]

i commented that line and traced the value of right child in different situation, the value was only 'false' in all situation.

Code: Select all

if (n == n.parent.left) {
               // it is, so check if the right node is non-null
               //if (n.parent.right != null) {
               //   System.out.println(n.parent.right == null);
                  // it isn't so the sibling node is the next node
               System.out.println(n.parent.right == null);
                  n = n.parent.right;
                  nextNodeFound = true;
                  break;
               //}
            }

[William]

Ok, I see what you are asking now.

Yes, due to the way the DynamicAABBTree is constructed, all leaf nodes are the AABBs of the objects in the scene. All other nodes are unions of their child nodes. The implication is that all nodes either have both or neither children.

As a result, the outlined code isn't really necessary.

William