PDA

View Full Version : Octree vs. scene tree



starman
08-12-2003, 08:17 AM
I'm expanding my Jupiter simulation to be a complete solar system simulation. Since the number of bodies (and thus triangles) is increasing, I'd like to employ some sort of frustum culling - an octree.

However, the hierarchical tree I use to store and render the sun/planet/moons is somewhat orthogonal to the spatial organization of the octree. My render code traverses the solar system tree -- which starts at the sun -- and then pushes/pops the modelview matrix as it places the planets and moons. It all works nicely, but if the camera is located at Pluto I don't want to be drawing Mercury.

My first idea is to first cull with an octree and mark each body as "visible" or not. Then, when I traverse the solar system tree, I'll merely check if the body is visible before trying to draw it.

This seems like an awkward solution. Would a BSP-tree be better? Or is there some other structure that will allow me to maintain the hierarchical integrity of the sun/planets/moons as well as cull the frustum?

starman
08-12-2003, 11:36 AM
Actually, when I think about it, perhaps a brute force method might not be a terrible approach as a first pass. Sun, nine planets, a handful of moons is still less than 50 objects. I could test each one of them against the view frustum prior to drawing and skip the octree. Of course, if I use a realistic number of asteroids that approach goes out the window...

Orzech
08-12-2003, 12:27 PM
Hi starman!


Originally posted by starman:
I could test each one of them against the view frustum prior to drawing and skip the octree. Of course, if I use a realistic number of asteroids that approach goes out the window...

IMHO the frustrum culling would be fairly enough. It depends, of course, on how complicated your objects are. You surely don't want to render a whole planet which conatains thousands of triangles if only one of them is visible, do you? http://www.opengl.org/discussion_boards/ubb/wink.gif
I would go for frustrum culling since it's an easy solution and then I would try to add some LOD alogorithm to speed up your application.

Orzech

starman
08-12-2003, 03:44 PM
I'm using gluSphere to draw the planets and moons, so I really don't have access to the tesselated triangles.

Now I'm reading about scene graphs. I've come across a couple different approaches: one stores geometry at every node, the other only at leaf nodes. The intermediate nodes would contain texture, lighting, transformation, and bounding volume info.

Perhaps that's a good place to start - with a simple scene graph.

JanHH
08-12-2003, 06:13 PM
I am a little astonished about so much effort for just some planets, really not very much 3d objects.. I have made the experience that if you use a tree structure for culling, to gain performance, there have to be really many many objects.. you can easily test several thousand objects witout getting really worse performance than with a tree on current hardware, I would put every planet into a display list, it should really be running fast witout any tests at all.

Orzech
08-13-2003, 03:38 AM
... and if you are using gluSphere you can easily approximate level of detail by just checking distance to a camera and drawing spheres with particular number of divisions.

starman
08-13-2003, 03:49 AM
JanHH - That's good to hear. I'm falling into the trap I've warned others about - premature optimization! I still need to organize my scene better, but I'll leave out the frustum culling until I notice performance problems.

Orzech - Good idea about level of detail.

dbugger
08-13-2003, 10:40 PM
I think you should do some brute culling. Check every planets bounding SPHERE against the frustum, that should be very fast. Don't bother with more advanced scene-trees yet. Just a note: if your FOV == 90 degrees, 1 unit into the screen == 1 unit left.

starman
08-14-2003, 02:28 AM
Well, a tree is the logical data structure to organize my scene anyway: sun at the root, planets are children of sun, moons are children of planets. The world transform of the moon is the concatenation of its matrix to its ancestors: [S][P][M]. It won't be too hard to add textures and lighting to that tree.