The Problem:
Handling and navigation through large worlds is currently not well supported in VRML 2.0 Browser. Browsers could implement view culling using bounding box information stored in Group nodes, but still a large amount of invisible geometry need to be passed to the rendering subsystem.
One Solution:
A common solution used in games is to subdivide the world into smaller parts, where the browser can quickly decide to draw or not to draw a part. One method is the Binary-Space Partitioning Tree (BSP-Tree). The world is partitioned by an infinite plane into the parts in front and in back of plane. The remaining parts are itself recursively split until the part is a single object.
In a True BSP-Tree, which can be rendered with out the help of a z-buffer, each object is a single polygon which might get split if it crosses the plane of its parent tree node, a node stores also the list of polygon exactly on the plane.
In an hybrid approach objects need not to be decomposed so far or can be combined with dynamic, moving parts which are not part of the BSP-Tree hierarchy. Here z-buffering is enabled, to ensure correct visibility.
GLView introduces the BspTree node :
EXTERNPROTO BspTree [
exposedField SFRotation plane # the plane equation
exposedField SFNode front
exposedField SFNode overlap
exposedField SFNode back
] "urn:inet:glview.com:node:BspTree"
plane encodes the splitting plane of this node in standard form :
plane[0] *x + plane[1] *y + plane[2] *z + plane[3] == 0
front is the scene graph totally in the front (or in touch) with the plane
back is the scene graph totally in the back (or in touch) with the plane
overlap is the scene graph on the plane (True BSP Mode) or which has parts on both sides of the plane (hybrid BSP mode)
This format allows full VRML 2.0 composeability, each Scene-Graph routed by the SFNode fields can contain an arbitrary scene graph. Common sub-graph cases includes again a BspTree or terminals like Shape nodes, NULL, Transform Groups or Anchors, Groups with TouchSensors or VisibilitySensors.
As an alternative to the "misuse" of an SFRotation to store a plane, a new field type SFPlane could be introduced.
It could be possible to write an implementation of this Node using a Proto and a script node, in the simple case all three subgraphs are stored in a single group, and in the advanced case a ProximitySensor together with a Switch and a Script decides on what part of the tree is shown.
The following samples are constructed with the TileGrid VRML EAI Applet :
Grid size 32 * 32 = 1024 simple objects
Grid size 64*64 = 4096 (Warning: some VRML browser may have problems with "large" worlds)
In the current GLView implementation BspTree´s should not be contained in Transform Groups.
The optimization only works out, if the viewpoint is inside the world, and if the visibilityLimit in the worlds NavigationInfo is specified as small as possible.
To enable "True" BSP-Rendering similar to game engines, toggle the "x" key in GLView. This will disable the standard z-buffer algorithm, and could further increase the frame rate. For optimal results the tree should be a True-BspTree, that means all Geometry is properly sorted into the tree, terminal nodes are planar objects or convex, solid objects, all object intersections has been resolved.
The GLView default is the hybrid mode, where z-buffering is used to compute visible pixels and the BSP-Tree helps culling. In hybrid mode, it is not necessary to decompose objects up to the last polygon.
The VRML VisibilitySensor optimized in GLView in conjunction with BspTree's and should be used for enabling/disabling complex animations. I.E. when ever an the sub-graph becomes visible, start the animation, enable the timers, whenever the sub-graph becomes invisible, stop the time sensors or even cull geometry via the VRML EAI to recover memory.
Other techniques which can be combined are :
use of LevelOfDetail (LOD nodes) to remove detail of objects far away from the viewer,
ProximitySensors to enable/disable scene graphs depending on viewer position
Using the EAI an application could implement dynamic tree modification,
by storing moving objects into their proper tree locations, or
by loading/unloading scene sub-graphs depending on viewer location
and movement.
For some type of scene there is a natural subdivision scheme, like quad-tree, oct-tree for Landscapes, connected rooms, buildings etc.
A quad-tree approach can be found in the TileGrid EAI sample.
Other examples could be the streets, tunnels or similar shapes, which could be subdivided along their spine curve.
The GLView standalone version has a BSP-Tree builder and Scene-graph optimizer.
First a suitable scene-graph for optimization or BspTree construction has to be found.
The scene tree optimizer expands all Transforms, Groups, Inlines. Geometry is converted to IndexedFaceSet nodes. The resultant Transform Matrix and any TextureTransform is applied to Geometry. DEF / USES are expanded.
A lookup process shares Material, ImageTexture and Appearance Nodes.
For BSP-Tree Purposes Anchors are applied to all resulting geometry individually and there is the option of decomposing IndexedFaceSets into single polygon IndexedFaceSets ("Planar Shape").
In the standard , simple case the result is a long list of Shape nodes containing IndexedFaceSet's.
The Optimizer may currently not work correctly on graphs with ROUTES into Transforms or containing unsupported nodes like Billboard, LOD. Such cases may need some manual cleanup before or after the optimizer runs.
As a second step the BspTree builder takes this list and build a BspTree node hierarchy out of it.
There are several approaches how to build the tree, GLView offers the following choices:
Subdivision strategy:
use first planar object : search for the first planar Shape, other wise use "split along largest dimension"
use largest planar object : search for the largest planar Shape
split along largest dimension : take the bounding box of all nodes and split along the axis with the largest size
For the hybrid approach the option maxBspLevel allow to stop this tree building process after a certain subdivision level has been achieved.
Depending on the number of final nodes, this process can take
some time. So please be patient, especially if you subdivide objects
into single faces.
Step by Step Instruction for Optimizer and BSP-Tree Builder:
Using the optimizer without BspTree building may also speed up
the rendering of the scene, because the group hierarchy is beeing
flattened, Materials/Textures are shared, transforms are applied.
The optimizer currently can't apply Transforms to non Shape nodes
: i.e. if "ignore routes" not checked,
DEF t0 Transform { children [
DEF t1 Transform { ## t1 has a route
}
Shape {
geometry IFS
}
]}
will be transformed to
Group { children [
DEF T1 Transform { }
## should be Transform { t0 children DEF T1 Transform {}}
Shape {
geometry IFS_t0_applied
}
]}