The Problem:
The handling of 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 needs 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 divided by an infinite plane into the parts in front and behind the plane. The remaining parts are itself recursively split until the part is a single object.
In a True BSP-Tree, which can be rendered without the help of a z-buffer, each object is a single polygon. A polygon 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 a hybrid approach objects need not to be decomposed so far or can be combined with dynamic, moving parts that 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 case 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 what part of the tree is shown.
The following samples have been constructed with the TileGrid VRML EAI Applet.
A square grid has been recursively subdived into an BspTree, each grid tile leaf contains some geometry.
16 * 16 Rooms, some containing an animated object
Grid size 16 * 16 = 256 simple objects
Grid size 32 * 32 = 1024 simple objects
Grid size 64*64 = 4096 (Warning: some VRML browsers may have serious problems with this large worlds)
More complex geometry BspTree version
The Bsp Structure of these examples is equivalent to a quad tree.
The room example demonstrates, that it is possible to use animated
objects in this hybrid BspTree approach. Each leaf position is
a convex subspace, an animated object at a certain BspTree Level,
should not move out of the boundary of the subspace defined by
its parents planes.
Extending VRML 2.0 with native implemented EXTERNPROTO'S is described in the VRML 2.0 spec. Any compliant VRML 2.0 browser can display the world, if the world author includes the EXTERNPROTO definitition and a fallback implementation of the native node. The above samples are using the following EXTERNPROTO statement :
EXTERNPROTO BspTree[
exposedField SFRotation plane
field SFNode front
field SFNode overlap
field SFNode back
]
["urn:inet:glview.com:node:BspTree","nodes.wrl#BspTree"]
With the implementation in nodes.wrl
PROTO BspTree [
exposedField SFRotation plane 0 0 1 0
field SFNode front NULL
field SFNode overlap NULL
field SFNode back NULL
]
{
DEF G Group {}
Script {
directOutput TRUE
field SFNode group USE G
field SFNode a IS front
field SFNode b IS overlap
field SFNode c IS back
url "vrmlscript:
function initialize() {
group.set_children = new MFNode(a,b,c);
}"
}}
This works for example in Intervista's WorldView browser.
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 intersection 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 is optimized in GLView in conjunction with BspTree's and should be used for enabling/disabling complex animations. I.E. whenever a the sub-graph becomes visible, an animation can be started by enabling the TimeSensors/Scripts, whenever the sub-graph becomes invisible, the TimeSensors are disabled.
Other techniques that 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 ScriptNode or 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 are 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 builds a BspTree node hierarchy out of it.
There are several approaches how to build the tree, GLView offers currently 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 the current set of nodes and split the set 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 being
flattened, Materials/Textures are shared, transforms are applied.
The current GLView BspTree proposal helps not in all cases, so far we could walk in a large outside landscape. Then we want to enter buildings with may have very complex geometry inside.
It is assumed for now that the complex things in the rooms inside
can't be viewed from outside. (the windows and Door's are opaque.)
GLView introduces two more nodes to aid Occlusion culling:
EXTERNPROTO Occlusion[
exposedField SFVec3f bboxSize
exposedField SFVec3f bboxCenter
exposedField SFBool enabled
exposedField SFNode proxy
exposedField MFNode children
eventIn MFNode addChildren
eventIn MFNode removeChildren
eventOut SFBool isActive
eventOut SFTime enterTime
eventOut SFTime exitTime
]
["urn:inet:glview.com:node:Occlusion" ]
Occlusion is a group node with an additional proxy geometry triggering an inside/outside processing.
Children would contain the inside view of the room, proxy would contain the bounding shape for the room, i.e. a Box {} node.
During traversal the current viewpoint is compared with all geometry nodes in the proxy subgraph.
If the viewpoint is outside all geometry nodes, children will be not visited for display. If the viewpoint is inside the proxy the children will be visited.
Whenever children become visible or invisible isActive, enterTime and exitTime events are generated similar to the ProximitySensor.
Occlusion's behaviour can be switched to the normal Group behaviour
by setting enabled to FALSE. This is designed for cases where
temporarily the room becomes visible from the outside, for example
if a door or window has been opened, to look inside the room.
EXTERNPROTO Inclusion[
exposedField SFVec3f bboxSize
exposedField SFVec3f bboxCenter
exposedField SFBool enabled
exposedField SFNode proxy
exposedField MFNode children
eventIn MFNode addChildren
eventIn MFNode removeChildren
eventOut SFBool isActive
eventOut SFTime enterTime
eventOut SFTime exitTime
]
["urn:inet:glview.com:node:Inclusion"]
Inclusion is somehow the inverse to Occlusion, children are only traversed if the viewpoint is in one of the proxy objects or if proxy is NULL. In combination with BspTree's if an Inclusion node becomes active, the node signals the BSP-Tree logic to stop processing.
The idea is, once you are inside a room, you cannot see anything
else.
Simple cases where the proxy is a Box can be realized in standard VRML 2.0 using a ProximitySensor and a Script as demonstrated on the VRML sample's page.
The current implementation allows the following nodes inside the
proxy scene graph: Group Transform, Box, Sphere, Cylinder, IndexedFaceSet
(must be convex)
Readers are invited to discuss these ideas and to formulate a proposal for future VRML standards. Please send mail to hg@berlin.snafu.de.