I dont want to have to calculate static data in my octree on the fly, so id like to save the pre-calculated tree to disk. I assume this is possible, as saving of a bsp tree is possible/required. Is there anyone that has done something of this sort that can give me ideas? thanks
What’s an octree? If you mean that you are maintaining a tree-like data structure that connects objects to each other in a hierarchical way, then you mean that you want to add streaming capabilities to your data structure. If so, let me know 
.
You can save it to disk recursively, in pretty much the same way you would otherwise traverse it.
You start with the root. You save all the data you need for that node (bounding box, list of polygons, …). Then you write some information that indicates which of the eight possible children are effectively present. I use a byte-sized bitfield for this. Then you recursively do the same for all the node’s children.
To load the octree back from the file, you do the opposite. First you read the node information (bounding box, list of polygons, …). Then you read the bitfield to see which children are defined. For each defined child, you create a new node under the current one and recursively repeat the process.
- Tom
Originally posted by Tom Nuydens:
You can save it to disk recursively, in pretty much the same way you would otherwise traverse it.
Yes, XLNT!, Example Follows:
class MyTree
{
public:
MyTree();
const MyTree* child() const;
const MyTree* sibling() const;
bool enabled() const;
bool disabled() const;
MyTree* child();
MyTree* sibling();
MyTree* lastChild();
MyTree* lastSibling();
virtual void action() {}
virtual void saveData() { // Your code here }
// Etc …
private:
MyTree* m_Sibling;
MyTree* m_Child;
// Etc …
};
void ActionTree(MyTree* baseNode)
{
if (baseNode->enabled())
{
baseNode->action();
}
if (baseNode->sibling())
{
ActionTree(baseNode->sibling());
}
if (baseNode->child())
{
ActionTree(baseNode->child());
}
}
void SaveTree(MyTree* baseNode)
{
if (baseNode->enabled())
{
baseNode->saveData();
}
if (baseNode->sibling())
{
SaveTree(baseNode->sibling());
}
if (baseNode->child())
{
SaveTree(baseNode->child());
}
}
I don’t know if I can help you or not. That’s because I program with Delphi and most of the guys here seem to program with C++, however, if you want, I can send you my set of classes (written in Delphi), that defines a flexible object-oriented framework, with very powerful streaming capabilities. I’m building my 3D objects above this framework. It’s not complete yet, but it may give you some ideas.
Originally posted by Tom Nuydens:
You can save it to disk recursively, in pretty much the same way you would otherwise traverse it.
Tom is totally right, although I would like to point something out when using recursivity: using this technique can easily blow your stack (I do it every day !). So it is a good practice to check your code against various cases to ensure that you will never do that…
If you are using VC++, you can alter the stack size in the projects settings…
Regards.
Eric
You are right Eric, however instead of increasing the stack you can minimize the stack requierments of your program. For example, in the code above (posted by pleopard). instead of saving/loading the siblings’ data recursively, you can maintain a pointer in the saveTree and actionTree functions to iterate all childs. That’s done by keeping in mind that the parent node is responsible of its “all” childs but not responsible of its next sibling.
As long as you have a doubly linked list,
you don’t need recursion at all. You just
put the root on the list, and enter the
loop:
while (list not empty)
unlink first item
save it
put children of item on list
If you put the children at the end, you get
breadth-first traversal, which is my personal
favourite. If you put the children at the
head of the list, you get depth-first.
(as a design point, “save” might take the
list as an argument, and put the children on
it inside the object, if “children” is private
data)
Excellent point softland. However, I don’t use that method because I am not concerned with blowing my stack . I use the recursive technique because it allows me to decouple the functionality of the needed operations (saveTree, actionTreee) from the class definition. Doing such greatly enhances the maintainability of my code. I can quickly and easily add new functions without changing the classes of the elements (MyTree) upon which the functions operate.
See “Design Patterns”, Gamma et al, “Visitor” pattern, p331.
I totally agree with you Pleopard, and I didn’t mean that you have to get rid of recursive methods. I’m developing some components and classes with Delphi, and I do maintain a tree like the one you mentioned, and I’m using recursive methods to obtain flexibility, however, I meant that you have to compromise, i.e mix between iteration and recursion. Every parent node should “iterate” it’s child nodes, and if it happens that one of the child nodes has childs, it iterates through them. See, recursive here, works in the the depth of the tree but not in the same level (not between siblings). This way, I get a maintainable code and low stack requierments. Plus, exessive use of recursion may make your code slower.