DynamicAABBTree: about internal nodes.

Any posts related to how dyn4j works, the math involved, class structure and hierarchy, etc.
SemiSober
Posts: 11
Joined: Wed Apr 23, 2014 1:20 am

DynamicAABBTree: about internal nodes.

Postby SemiSober » Tue Sep 23, 2014 1:54 pm

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
Site Admin
Posts: 345
Joined: Sat Feb 06, 2010 10:23 pm

Re: DynamicAABBTree: about internal nodes.

Postby William » Tue Sep 23, 2014 8:19 pm

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:
download.png
An Example Binary Tree
download.png (2.34 KiB) Viewed 4814 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
Posts: 141
Joined: Sun Mar 17, 2013 3:57 pm
Location: Stockholm, Sweden
Contact:

Re: DynamicAABBTree: about internal nodes.

Postby zoom » Wed Sep 24, 2014 2:43 am

Great explanation, thanks.

SemiSober
Posts: 11
Joined: Wed Apr 23, 2014 1:20 am

Re: DynamicAABBTree: about internal nodes.

Postby SemiSober » Wed Sep 24, 2014 6:56 am

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:
Image

the tree related to this situation would be like this :
Image


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
Attachments
tttree.png
tttree.png (9.02 KiB) Viewed 4797 times

William
Site Admin
Posts: 345
Joined: Sat Feb 06, 2010 10:23 pm

Re: DynamicAABBTree: about internal nodes.

Postby William » Wed Sep 24, 2014 8:00 am

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.
251px-AVLtreef.svg.png
Sample AVL Tree
251px-AVLtreef.svg.png (5.62 KiB) Viewed 4791 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
Posts: 11
Joined: Wed Apr 23, 2014 1:20 am

Re: DynamicAABBTree: about internal nodes.

Postby SemiSober » Wed Sep 24, 2014 10:36 am

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

SemiSober
Posts: 11
Joined: Wed Apr 23, 2014 1:20 am

Re: DynamicAABBTree: about internal nodes.

Postby SemiSober » Thu Sep 25, 2014 9:46 am

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
Site Admin
Posts: 345
Joined: Sat Feb 06, 2010 10:23 pm

Re: DynamicAABBTree: about internal nodes.

Postby William » Fri Sep 26, 2014 10:49 am

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


Return to “Behind The Scenes”

Who is online

Users browsing this forum: No registered users and 1 guest