Archived

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

ProgramMax

A few octree questions

Recommended Posts

Okay, I have been working on my octree-based engine for a while and I am running into many questions. I am hoping some people can help me out. 1.) How many polys should each node hold for optimal usage? 2.) What about octree nodes not being perfect squares? 3.) Has anyone thought up a good way to hide what is visible through an octree, but hidden (such as a vally behind a hill)? 4.) Is there a good way to premake LOD? Further details on the questions: 1.) How many polys should each node hold for optimal usage? My friend and I sat down and thought this one through. It wouldn''t be a static number, but be dynamic. Let me explain why: Say we have some normal landscape with a small, but highly detailed rock. If that rock isn''t in the view then it gets cut off early and doesn''t matter. However if the rock is in view, you could have like 50 octree nodes just for that detailed rock, however the rock is so small that even though it is detailed, it is almost always either entirly visible or entirly not visible. In this case the extra octree nodes would give more proccessing and memory usage than what would benefit. I mention this because this could help other people optimize their engines, and I am having trouble implementing it. I have found out that I should test how dense the polygons are in the area to test how many polys each node should hold, but I don''t know how to go about doing that. If someone could help me that would be great. 2.) What about octree nodes not being perfect squares? Okay, no terrain is going to be perfectly balanced, and so sense my octrees are using perfect cubes, the tree won''t be balanced. It would look more like: * /\ /\ /\ /\/\ Instead of a balanced tree that might look like: * /\ /\/\ /\/\/\ If I were to sort the octrees so that rather than using perfect cubes, it split down the middle having an equal amount of polys on both sides. Then the tree would be more balanced. The problem is then each node holds 2 extra width variables and after a while that will build up. Is it worth the extra space? I don''t really see it speeding up at all... 3.) Has anyone thought up a good way to hide what is visible through an octree, but hidden (such as a vally behind a hill)? I like the idea of having rolling hills and caves. However if I am in a cave, the octree structor would return to me what is visible, and the rest of the world that would be visible if the cave was see through. This is great if I am using alpha values, but I am not. I know that my world will be opaque and so I want to find a way to cull what should be, and hopefully have it build in with octrees well. 4.) Is there a good way to premake LOD? Obviously having premade LOD will be quite nice. My idea is to have every node hold triangle data. The leafs will hold the actual data, and every other node will hold a LOD generated by it''s 8 children. That way you can premake the LOD and things won''t take much more memory. It works with the octree structure well. Here is my problem though. Say I have this tall hill I am standing next to. I am looking along it''s side (not strait at it) and am in a valley next to it. The close hill might look like: _ / \ and when I generate a LOD it might look like: /\ So then my problem would be when I put the LOD hill next to the real hill, there would be gaps and it wouldn''t line up. I then figured I could just force the LOD to use the same edge points as the real version. But doing that wouldn''t save a whole lot when using LODs would it? It would force a still high amount of polys. If anyone has some ideas, I would REALLY appreciate it. Thanks a million everyone!!

Share this post


Link to post
Share on other sites
Here's my thoughts:

1) I really can't comment on this first one since I prefer to store objects in oc-trees than polygons, but here goes: I would set a hard limit on polygon count and the depth of the tree. If when you reach the maximum tree depth you still have a bunch of polies left over, just dump them all in that last node. As long as you set the minimum node size (~1/treedepth) large enough, your rock subdivision problem should work itself out.

2) I would recommend keeping your nodes perfect cubes, that way you can reasonably use bounding spheres later on to do collision tests rapidly. Probably makes testing which node to drop into easier as well.

3) If your whole octree is static, you might consider using some sort of PVS to store which nodes are visible from a specific node. Perhaps, in each node, store some bounding planes that, based upon the viewer location, restrict whether or not a child node gets drawn. Not sure if this is feasible because I havent tried it, but y'all can think it through for me

4) You might want to do something similar to quad tree terrain to generate LOD for your oc-tree, but this pretty much restricts your terrain to lying along one axis (typically the X-Z plane). If you were hoping to do spherical terrain (like a planet) I think you'll have to store the terrain as a separate entity or invent something . Also, in any event I would recommend using the same vertices as the original terrain, that way you can index into the same vertex buffer.

-Matt

Edited by - tirisfal on November 11, 2001 9:33:22 AM

Share this post


Link to post
Share on other sites
1.) How many polys should each node hold for optimal usage?
2.) What about octree nodes not being perfect squares?
3.) Has anyone thought up a good way to hide what is visible through an octree, but hidden (such as a vally behind a hill)?
4.) Is there a good way to premake LOD?

1.) Your answer is quite interesting. It seems to work well, because it handles the case without causing other problems. But then I have to find when the octree is getting twards it''s last nodes or the tree is getting too large. How would I know when to stop it or what the optimal size of the tree would be?

2.) Ahh yes, forgot about that completely. Sphere testing is much quicker and for that reason alone it would be better to keep them perfect cubes. So question 2 is completely answered.

3.) Okay, so each node would hold a PVS structure telling which nodes will and will not be visible from this node. But with all that overhead, would it be worth the work? It might end up just rendering the dead polys would be less time consuming than building the PVS and using it. What do you think?

4.) I am not familiar with how a quadtree does it''s LOD, so perhaps you can enlighten me. I know my case will mostly be that of quadtree or similar, and so it wouldn''t be much of a wrong-doing to try to incorporate that. You suggest using the same indecies...but that would not be LOD. Did you mean same indecies around the edges? That way it would fit perfectly but would require a certain amount of polys and there for would not allow much LODing to take place. I am confused as to your answer to this one.

Thanks a ton for your help!

Share this post


Link to post
Share on other sites