Octree question?

When building the tree just 'clip' the polygon to the bounding box of the current octree node.

Basically, you have your polysoup. When created a new node you are gonna check all polygons in your soup and clip them to make sure you have all the polygons in that node. If the count is above a certain threshold then create 8 new nodes recursively.

This will make sure you always have all polygon parts in the correct octree node.

- Freaky

[edited by - Freaky on April 18, 2004 3:49:02 PM]

Just put it in a higher node - go up a level until it fits into it. In the worst case it will only fit into the root node, which means the object is visible from everywhere.

I might not be helpful here, but, klanjtib, what happens when you put a millimeter-size 10,000-polygon utah teapot at the very center of the map? It surely won''t be visible from everywhere (it''s so small it''s easy to miss) but will be drawn all the time.

Thats when you use a structure called a ''loose octree''. Basically if the initial area of each leaf was K, you multiply it by a factor M, where m>1 (eg M=1.5). Now, theres going to be some overlap between leaf nodes. In order to resolve the situation where an object is in between 2 leaf nodes, you hold a position P which represents the center of each node - and you do a comparison test to see which center its closest to.

For a better explanation:

Ulrich''s own explanation on loose octrees

You don''t want to split a polygon by more than one plane. What you should do is use recursion...

Say you add a polygon in the root node, and the node has 8 children nodes... And your polygons happens to fit in 4 of those 8 children nodes. Well, the polygon would be split by multiple planes, but its not a problem. You have 3 split planes in an octree node. If one of these plane intersects the polygon, then the polygon needs to be split in 2 by that plane. When you split the polygon, you get two new polygons.

Say your polygon gets split by the XY plane first, then once you have those 2 polygons, you add them again to the root node. Those new polygons should not be split by the XY plane, because each of them lies on a different side of the XY plane. However, those 2 polygons might be split by the XZ plane! The same function that has split the first polygon in 2 will detect that the 2 new polygons need to be split again, and those polygons will be added to the octree again, until they can no longer be split by that node, and they will be managed by the children node, which may also need to split those polygons, depending on their size.

---

Looking for a serious game project?
www.xgameproject.com