#### Archived

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

# OBB tree problem

This topic is 5022 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Hi, I have a group of objects stored in a tree (with an arbitrary number of children per node) and I am trying to write a function that calculates every node''s oriented bounding box so that it encloses that node''s polygonal mesh as well as those of its offspring. I just need to calculate the minima and maxima of every child and compare them with that of the parent but I just can''t get my head around (probably because of the recursive nature of the algorithm, even though I''ve done it before with other tree functions). Any help would be greatly appreciated

##### Share on other sites
quote:

I just need to calculate the minima and maxima of every child and compare them with that of the parent

Yep, that''s about it. Make a recursive call to each child asking it to calculate it''s bounds. Then calculate the nodes own bounds, and find the minimum of the minimums and the maximum of the maximums. The recursion will work because the nodes at the ''bottom'' of the tree don''t have any children, hence the recursion doesn''t go on for ever.

##### Share on other sites
Yes, the algorithm is fairly simple but I''m having trouble coding the function.

##### Share on other sites
Have you written an auxiliary function that returns the bounds of a single polygonal mesh?

##### Share on other sites
Yes, I have. I have trouble visualising how the function would work. If I was dealing with a linked list (single,double,cyclic,etc) I would have done it in a jiffy.

[edited by - bah on May 25, 2004 7:13:27 PM]

##### Share on other sites
Write a function to calculate the bounds of a subtree with a given top node. It can do it like this:

(1) Calls the auxiliary function to calculate it''s own meshes bounds; lets call those bounds B.

(2) Calls *itself* on each of it''s children. For each call, it will get the bounds of that whole subtree - combine each into B.

(3) Finally, return B.

The trick to recursion is to decide exactly what your function will do, and promise that you will make it do that. Then, write the function assuming that a recursive call will indeed meet that promise, even though you haven''t finished writing it yet.

The only danger is that you don''t recurse forever, which in this case cannot happen because of the finite size of the tree. Here is an example which recurses forever:

int answer_to_life_the_universe_and_everything()// This function will calculate the answer to life the universe and everything.{  // The function ''answer_to_life_the_universe_and_everything'' should give us our answer!  return answer_to_life_the_universe_and_everything()}

This can be thought of as _correct_, except that it doesn''t ever finish.

##### Share on other sites
That''s more or less what i''ve said in my first post but thanks for trying though.

##### Share on other sites
What''s still troubling you then? It is a specific part of the code you don''t know how to implement, or do you just want to be more confident about why it will work?