Horde3D

We are currently thinking about ways to optimize the scene management. Profiling has shown that the update of the render queue is by far the most expensive function for Chicago. So here is the plan of attack:

Currently we have the scene graph structure which is used for hierarchical transformation and also culling, accelerated by an AABB tree. The new idea is to split that scene graph in two components: a scene tree which is solely responsible for the node transformations and a spatial graph which does the culling. There is not much difference for the user, the spatial graph is completely transparent: When a scene tree node is updated, it is automatically rearranged in the spatial graph. The spatial graph finally generates the render queue. The spatial graph can be something like an octree or portal system. But as default implementation I would opt for something very simple but useful called multibound (see http://geck.bethsoft.com/index.php/Occlusion_Culling). Basically a multibound is just an AABB which is placed manually by a designer at appropriate locations, e.g. a room. All objects which are in the multibound are culled in one go. The multibounds could also be used in combination with hardware occlusion culling which makes them much more effective.

This system would give a better separation of concerns (transformation hierarchy and culling based on spatial proximity/locality). Multibounds would be represented as scene nodes, so they could also be transformed, for example when the whole world is shifted. That also means that no additional API is necessary and adding support in the Horde editor is rather easy. The current AABB tree would be removed which makes the scene tree updates cheaper and amortizes hopefully the additional costs of the spatial graph processing. I think that system would give to users a lot more chances to optimize performance of complex scenes.

Any thougts on that?

A spatial graph supporting cycles could be very useful (and powerful).
This would allow games with extremely large indoor areas to be rendered easily.

e.g.
* The spatial graph root has 1 child node called "RoomA"
* "RoomA" has 2 children: "RoomB" and "RoomC"
* "RoomB" has 2 children: "RoomC" and "RoomA"
* "RoomC" has 2 children: "RoomA" and "RoomB"

The code for stopping infinite loops is pretty simple. The renderer can increment a counter once per 'Render' call. When a spatial node is visited, this ID is recorded. If the recorded ID is equal to the current ID, then this node has already been visited this frame:


[EDIT] Thinking some more about a spatial-graph, it might be useful for the user to tell Horde (or for Horde to figure out internally) which multi-bound/spatial-node the camera is currently inside of.

For example, in this example level there are 8 rooms in a circle pattern, each room is connected to 2 other rooms.

If Horde knows that the camera is inside of room "B" then the scene traversal is more efficient than if we always started at some particular "root node" (N.B. in my picture there is no root node - all nodes are equal in the spatial graph).

Starting from "B" (in my picture), the graph traversal would look like:

DarkAngel, thanks for your feedback, it is very appreciated.

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.

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? 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 graphI 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.

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.

Thanks a lot for your detailed explanation, it made your ideas much clearer to me. I will do some deeper thinking about the whole topic when I have a bit more time again.

We have integrated a very basic spatial graph now. It is just a flat list and does not yet support MultiBounds or sectors with connectivity information but it already helps to make the culling (render queue generation) considerably faster.