1
\$\begingroup\$

I started with a very simple graphics engine a few weeks ago and I have finished a simple scene-graph and I am now at a point where I need to create a bounding volume hierarchy.

I never really thought about it that much and now I am stuck. Basically my current goal is to achieve view frustum culling and I know how to do this but I have no idea of how to generate a bounding volume hierarchy.

The problem that I have is that I don't know how to create bounding boxes spatially.

My scene-graph allows me to group objects together and at the moment I am doing this

[object_group1,object_group2,....object_groupN]

And now I just check if the object_group is inside my view frustum, but this is only a naive solution.

Which algorithm/data structure would you recommend for an outdoor scene?

\$\endgroup\$
1
\$\begingroup\$

First, of all I smell that you are going to use your scene graph for frustum culling and other operations not meant to be a scene graph operations. Please Don't.

Using scene graph for things other than propagating data like transformations and some other properties, is counter intuitive. If frustum culling needs info derived from the scene graph Doesn't mean the scene graph should be used to make frustum culling. And that's might big reason why you are stuck.

Regarding your outdoor scene, it's hard to select one spatial partitioning that will fit (rule:-) them all.. If your engine contains a lot of terrains then you might use an Octree data structure, especially if there are a lot of static objects. Bounding Volume Hierarchy can be used with more dynamic scenes. And you probably will end up using multiple spatial partitioning techniques.

My advice is to implement basic frustum culling testing the whole scene without BVH or Octrees, this will be your starting point. Don't overwhelm yourself ( because I did that I ended up less productive). After successfully implementing frustum culling you can optimize more using other techniques, which highly depend on the scene.

And again Please Don't use your scene graph for things it was not meant to be.

\$\endgroup\$
  • \$\begingroup\$ I don't really have a scene-graph, I really only create a tree for transformations, then I convert the tree to some object with the calculated model matrix. So what you are basically saying is that I should use two different data structures? One for all static objects and one for the dynamic ones? And I also thought that an Octree is an BVH, or am I confused? \$\endgroup\$ – Maik Klein Jan 20 '14 at 7:36
  • \$\begingroup\$ Also do you know of any must read blogs/books for graphics programmers? I find it really hard to find information. \$\endgroup\$ – Maik Klein Jan 20 '14 at 7:45
  • \$\begingroup\$ Octree and BVH are different. What am saying is that you need to start writing frustum culling without optimization data structure, just loop through the scene and set which object is visible and which is not. And then pass these data to the renderer. The transformation hierarchy is your scene graph in your case. \$\endgroup\$ – concept3d Jan 20 '14 at 7:46
  • \$\begingroup\$ after writing basic frustum culling your spatial data structure will vary based on the application. So you will probably end up with multiple. \$\endgroup\$ – concept3d Jan 20 '14 at 7:49
  • \$\begingroup\$ Check real time rendering 3ed, mathematics for 3d computer graphics 3d edition, real time collision detection, and game engine architecture. \$\endgroup\$ – concept3d Jan 20 '14 at 7:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.