OBB tree problem
Author
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
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.
Author
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]
[edited by - bah on May 25, 2004 7:13:27 PM]
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:
This can be thought of as _correct_, except that it doesn''t ever finish.
(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.
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?
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
