The point of the multibounds is that they don't have portal/connectiviy information. They are just a hint (set by a human) for the engine that it is reasonable to treat the objects in the designated area (the multibound) as a single entity for culling. For example, this can make sense for a room which has many smaller objects (e.g. chairs, tables) to speed up the culling, especially if that multibound is occluded by the walls around the room.
Perhaps my idea should actually be a 3rd graph then?
Graph #1 = Scene transformations tree
Graph #2 = AABB / culling tree
Graph #3 = Connectivity / traversal graph
I don't quite get your point of the room cycles. How does the system profit when each room includes any other room? For me the spatial graph is a logical real-world representation of the spatial relation, so the huger room could include the smaller room (which makes a tree) but not the other way round.
I don't think this idea would help much in simple scenes like the chicago sample, so I'll use a city as an example scene:
First we have the traditional spatial tree (AABB tree/quad tree/etc...), where each node has one parent and can have many children.
The root node contains many city blocks, each block contains many buildings, each building contains many floors, each floor contains many rooms.
This tree is good for frustum-culling purposes, as entire blocks, buildings, or floors can be culled at once.
However, this tree is not ideal for scene traversal as we always have to begin at the root node, and we don't have any information on which nodes are visible from other nodes.
For example, in the above image the camera can only see two rooms, however the renderer must:
*Start at the root node
*Cull every city block, except the one the camera is in
*Cull every building, except the one the camera is in
*Cull every floor, except the one the camera is in
*Cull every room, except the two the camera can see
We can improve scene traversal by supplementing the first tree with a non-directional graph
, which describes connectivity.
Using a connectivity graph, the scene traversal can begin in the camera's current room, instead of starting at the root.
In the above example image, the camera is inside room "A", which connects to "B", "C" and the outside "o" (this would be the city-block node which contains the building).
*First "A" is rendered.
* "B", "C" and "o" are checked next. "C" and "o" are culled.
* "B" is rendered. All of the rooms connecting to "B" have already been processed, so rendering is complete.
Another example using city scene: the hierarchical-AABB layout (black arrows) and the connectivity data (green arrows) could look like this:
(click the map for larger version).
When rendering a node, a recursive function is called through both black and green arrows (but nodes must be counted like in my first post so they are not rendered twice
If the user has not supplied a connectivity graph, then rendering can still begin from the root (as it does now), and will work because there are still black arrows, but no green arrows.
Concerning the second part of your answer, do I understand correctly that for the culling algorithm you describe, you need connectivity information between the spatial nodes? So you describe basically a portal system?
It is similar to a portal system.
In my original picture, you could call the pink lines that join each room together "portals" --- If you calculated the AABBs of the portals, you could do occlusion tests on the portal AABBs instead of on the AABB of the room behind the "portal"
Actually, this would probably be a required feature - When entering connectivity data, you could optionally specify an AABB to be used for culling purposes (whether the "portal" is hidden or not). If no AABB is specified for a connection, then the multibound that the connection points to would be used for culling purposes.
In most cases, connections wouldn't require an explicit AABB of their own.
However, if a "child room" has a connection to a "parent room" (e.g. Room 1 on Floor 3 has a window which connects back up the tree to Block 2
), the the parents AABB test would always
pass... So instead, the "portal" would be required to have an AABB of it's own.