Scene Graphs and Lights

It is commonly accepted that the single hierarchy of a scene graph is not suited to model all the different groupings, assignments, orderings, … that are needed. While carrying the torch is a kind of parenting, the lighting is a kind of volume affiliation. These are totally different things.

A solution to this problem is to use structures as needed: In this case install a spatial structure to quickly find neighbored entities, e.g. an octree. Attach the torch by parenting to a skeleton (or simple anchor). Use the resolved position of the torch to query the spatial structure for nearby entities. Then don't use the N nearest lights but the N lights with most effect on the entity due to brightness and distance.

So, should I use both a scene graph and a spatial structure? Should the scene graph chain spatial transformations while the spatial structure should provide spatial queries and culling?

I think I'm confusing things a bit, but I thought they would serve (almost) the same purpose. Is there some article on this matter?

A transformation hierarchy and a culling system are two very different problems, which both have very different optimal data representations.
It used to be very common to try an solve every problem using a single graph data structure, but it's a very flawed approach and is not popular any more.

http://home.comcast.net/~tom_forsyth/blog.wiki.html#%5B%5BScene%20Graphs%20-%20just%20say%20no%5D%5D

I second what Hodgman said.

I'll also add, that we have a BVH (Bounding Volume Hierarchy) for lights. Their bounding volumes represent area that light affects (e.g. for point light we have a sphere, for spot light it is a cone, and similarly for area lights (as we do support them in our tech)).

Now, first we can quickly tell whether we have to compute with given light (e.g. whether it affects any pixel in given view frustum), second we can quickly tell which lights affect each given object.

The objects we need to test are taken from another BVH, that contains scene objects (we actually split objects in static and dynamic ones - because for static objects you don't need to rebuild the hierarchy, for dynamics you need to either rebuild, or sometimes just refit).

So basically we're working with multiple "scene graphs" in our tech (BVH is actually an implementation that can be used as scene graph). To explain a little bit about BVH (unless you know what it's all about) - check http://en.wikipedia.org/wiki/Bounding_volume_hierarchy

Technically you could also use some spatial hierarchy for this - KD-trees or Octrees for example.

I second what Hodgman said.

I'll also add, that we have a BVH (Bounding Volume Hierarchy) for lights. Their bounding volumes represent area that light affects (e.g. for point light we have a sphere, for spot light it is a cone, and similarly for area lights (as we do support them in our tech)).

Now, first we can quickly tell whether we have to compute with given light (e.g. whether it affects any pixel in given view frustum), second we can quickly tell which lights affect each given object.

The objects we need to test are taken from another BVH, that contains scene objects (we actually split objects in static and dynamic ones - because for static objects you don't need to rebuild the hierarchy, for dynamics you need to either rebuild, or sometimes just refit).

So basically we're working with multiple "scene graphs" in our tech (BVH is actually an implementation that can be used as scene graph). To explain a little bit about BVH (unless you know what it's all about) - check http://en.wikipedia.org/wiki/Bounding_volume_hierarchy

Technically you could also use some spatial hierarchy for this - KD-trees or Octrees for example.

Just like to add a +1 here as your solution sounds almost identical to what we do at my company, though we use an oct-tree instead of a BVH.

I made this just for you: Scene Graphs

L. Spiro

Cant ask for much more then for someone to write you an article for an answer :)

Good job, i know it cleared things up for me anyway! - Thanks

Thank you very much for all the answers. Thank you L.Spiro for the article. I'll be reading your posts ;)

I have definitely been reading some outdated stuff. I'll dig into this now.