VRML 97 currently lacks tools for enabling visibility managment for indoor environments.
An ideal browser implementation could analyze the scene graph and apply occlusion culling algorithms during rendering, but this seems currently not feasible given the dynamic nature of a VRML scene graph.
A well known occlusision culling technique are Cell & Portals.
The idea in short: given a set of rooms (Cells) connected by windows and doors
(Portals), for a given room if a window is not visible, the room viewed through
the window is not visible either. That means cellsnot currently visible need
not to be rendered nor checked for collision and selection.
Details
As a compact description the reader is refered to the paper: Faster 3D Game Graphics by Not Drawing What Is Not Seen Kenneth E. Hoff III. ACM Crossroads, 1997.
Node definitions :
Cell {
exposedField SFVec3f bboxSize -1 -1 -1
exposedField SFVec3f bboxCenter 0 0 0
exposedField MFNode children []
eventIn MFNode addChildren
eventIn MFNode removeChildren
exposedField MFNode portals
exposedField SFInt32 content 0
}
Portal {
exposedField SFBool enabled TRUE
exposedField SFBool ccw TRUE
exposedField SFNode coord NULL
exposedField SFNode cell NULL
}
CellGroup[ {
exposedField SFVec3f bboxSize -1 -1 -1
exposedField SFVec3f bboxCenter 0 0 0
exposedField SFInt32 range -50
exposedField MFNode cells []
exposedField MFNode children []
eventIn MFNode addChildren
eventIn MFNode removeChildren
eventOut MFNode activeCells
}
BspTree {
exposedField SFRotation plane 0 0 1 0
exposedField SFNode front NULL
exposedField SFNode overlap NULL
exposedField SFNode back NULL
}
A Cell Portal graph is routed by a CellGroup node. The list of cells is listed
in the cells field of the CellGroup.
The Portal helper node defines the "window" geometry and points to
the Cell seen.
CellGroup
Cellgroup is a grouping node similarily to Group.
The cells field specifies the list of cells composing the CellGroup. The nodes must be Cell nodes.
The children field may specify a list of children nodes consisting out of a BspTree Tree with Cell nodes as leaves. Nodes contained in the children field are not rendered in a linear way, they are used to find the initial starting cell, the cell containing the current viewpoint.
The activeCells eventOut is set to the list of currently visible cells. activeCells[0] is the starting cell, which contains the viewer.
The range field allows to limit the cell recursion depth. The Cell tree is recursivley traversed up to the level abs(range). If range is negative the browser can automatically lower the range depending on system performance.
bboxSize bboxCenter addChildren removeChildren children have the same semantic as in the Group node.
Cell
Cell is a grouping node similarily to Group. The children field contain the geometry of the room.
The portals field specifies the list of Portals for the Cell
bboxSize bboxCenter addChildren removeChildren children have the same semantic as in the Group node.
The content field is for application use. A possible use is to define content types like water, closed space, normal space having different meaning of the application. (e.g. User can not walk into a Cell containing water.)
Portal
Portal specifies the portal's geometry aCell is a grouping node similarily to Group. The children field contain the geometry of the room.
The field enabled controls portal processing. If enabled is TRUE processing the Portal is active and will be check for visibility, if enabled is FALSE the Portal is not active, the portal is treated unvisible.
The field coord specifies a Coordinate node containing the 3D Polygon of the Portal.
The ccw field specifies the handedness of the polygon, see IndexedFaceSet ccw field for explanation.
The field cell points to a Cell node, its the cell which is seen throug the Portal.
BspTree
BspTree node is helper node structuring scene graphs in disjoint sets separated by a 3D plane.
The field plane specifies the plane.
Example:
Implementation notes:
C++/Javascript Pseudo Code:
// context variables
viewpoint; // the viewpoint position (eye) in local coordinates
viewFrustrum; // current view frustrum, initially set of 5 planes: sides and far plane
clipVolume; // temp culling frustrum for Cell
mode; // current traversal mode for BspTree / Cell
function CellGroup::traverse()
{
clipVolume = viewFrustrum; // initially what can be seen must be inside the current view frustrum
activeCells.length = 0;
// mark all cells as not visible
for (i=0;i<cells.length;i++)
cells[i].clipVolume=emptyVolume;
// find the cell containing the viewpoint, ideally there is only 1
// and check/add all cells connected through portals
findActiveCells(children);
push viewFrustrum;
// render each active cell, but use the cell's (smaller) frustrum
// for object and portal culling
for (i=0;i<activeCells.length;i++) {
setViewFrustrum(activeCells[i].clipVolume);
activeCells[i]->traverse();
}
pop viewFrustrum;
}
function findActiveCells(children)
{
// like normal traverse with special action for BspTree & Cell node
mode = findActiveCellsTraverse;
traverse(children);
mode = normalTraverse;
}
function Cell::traverse()
{
if (mode == findActiveCellsTraverse) {
// once reaching here, cell is complete or partly visilbe
// we add it to the list of active cells of the parent CellGroup
addToActiveCells(this);
// record / update the cell's clipVolume
this.clipVolume = union(this.clipVolum,clipVolume);
for (i=0;i<portals.length;i++)
portals[i]->traverse();
return stop_traversal;
} else
traverse(children);
}
function Portal::traverse()
{
var resultPoly;
if (!enabled) return; // portal is not enabled, so can't view into cell
if (!cell) return; // portal does not point to a cell, so nothing visible
// if Portal polygon is backfacing, cell can't be seen
if (isBackfacing(viewpoint,PlaneOf(coord,ccw)) return;
// if Portal polygon totally clipped by current clipVolume, cell can't be seen
if (!ClipPolyAgainstFrustrum(coord,clipVolume,resultPoly)) return;
push clipVolume
// create new smaller frustrum through edges of result poly, viewpoint and zfar plane
clipVolume = buildClipVolumeForPoly(resultPoly);
cell->traverse();
pop clipVolume;
}
function BspTree::traverse()
{
if (mode == findActiveCellsTraverse) {
status=PointPlaneStatus(viewpoint,plane);
if (status == INSIDE) traverse(front)
else if (status == OUTSIDE) traverse(back)
else traverse(overlap)
} else // generic mode
status=ViewfrustrumPlaneStatus(viewfrustrum,plane);
// optionally check viewfrustrum against againts plane & cull children
if (status == INSIDE) {
traverse(overlap)
traverse(front)
} else
if (status == OUTSIDE) {
traverse(back)
traverse(overlap)
} else{
traverse(back)
traverse(overlap)
traverse(front)
}
}
}
traverse(MFNode v)
{
for (i=0;i<v.length;i++)
v[i]->traverse();
}
traverse(SFNode v)
{
if (v) v->traverse();
}
function PointPlaneStatus(p,plane)
{
f = p.x * plane[0] + p.y * plane[1] + p.z * plane[2] + plane[3];
if (f<0) return INSIDE;
if (f>0) return OUTSIDE;
return OVERLAP;
}
The Cell->Portal->Cell structure introduces an arbitrary cyclic graph of nodes. Should Portal use an SFInt32 instead of SFNode to reference the target cell by number in the parent Cell group ?
If the CellGroup node is going to be deleted from browser memory the browser can set all portals fields of the Cell nodes refered by he cell field to NULL, in order to break any cyclic node references.
If the same cells is viewed through several portals instead of computing cell.clipVolume = union(cell.clipVolume); cell.clipVolume can be set to the initial (viewFrustrum) clipVolume. Also the content author could avoid some cases "several portals" to the same cell, by defining a larger portal polygon covering several geometric windows.
The BspTree node definitions should better be :
BspTree {
exposedField SFVec3f normal 0 0 1
exposedField SFFloat distance 0
exposedField SFNode front NULL
exposedField SFNode back NULL
}
Portal Node: In addition to Cell the nodes Switch Group LOD are allowed in the cell field if they contain Cell nodes.
A nice feature would be to predefine some Cell content types, e.g. content = -1, the Browser does not allow to navigate into this area, content = -2, the space is water, navigationSpeed is set to half speed.
A specific problem is the authoring of the Cell Portal structures. Games like Quake have tools for subdividing the game level in bsp tree sorted convex subspaces and building the visibility structure. In other approaches authors need to indicate the different cell's and flag portal poygons.
8*8 script generated in-door grid scene : roomsobj_portal.wrl
16*16 script generated out-door scene (with visibilityLimit) : roomsobj_portal_outside.wrl
The culling rate can be observed using the F7 key, one number represents the number of primitives (IndexedFaceSet's) displayed after all culling. (ViewFrustrum, Cell & Portal culling.)
Output from from roomsobj_portal with tracking of the user : roomsobj_portal_out.wrl
using the activeCells eventOut from CellGroup.
The name of the cell the user is inside and the number of totall rendered cells
is printed to the console.
For comparison scenes using only BspTree but not Cells & Portals :
8*8 script generated in-door scene : rooms_bsp.wrl
12*12 script generated in-door scene with fog: rooms_bsp_1212.wrl
References:
This is the scene graph for set of 2*2 rooms connected with doors:
CellGroup {
cells [
DEF C0_0 Cell {
children [
]
portals [
DEF PC1_0 Portal {
coord Coordinate {point [70 14.5 28,70 14.5 42,70 0 42,70 0 28]}
cell DEF C1_0 Cell {
children [
]
portals [
DEF PC1_1 Portal {
coord Coordinate {point [112 14.5 70,98 14.5 70,98 0 70,112 0 70]}
cell DEF C1_1 Cell {
children [
]
portals [
DEF PC1_0_1 Portal {
coord Coordinate {point [98 14.5 70,112 14.5 70,112 0 70,98 0 70]}
cell USE C1_0
},
DEF PC0_1 Portal {
coord Coordinate {point [70 14.5 112,70 14.5 98,70 0 98,70 0 112]}
cell DEF C0_1 Cell {
children [
]
portals [
DEF PC0_0 Portal {
coord Coordinate {point [28 14.5 70,42 14.5 70,42 0 70,28 0 70]}
cell USE C0_0
},
DEF PC1_1_1 Portal {
coord Coordinate {point [70 14.5 98,70 14.5 112,70 0 112,70 0 98]}
cell USE C1_1
},
]
}
}
]
}
},
DEF PC0_0_1 Portal {
coord Coordinate {point [70 14.5 42,70 14.5 28,70 0 28,70 0 42]}
cell USE C0_0
}
]
}
},
DEF PC0_1_1 Portal {
coord Coordinate {point [42 14.5 70,28 14.5 70,28 0 70,42 0 70]}
cell USE C0_1
}
]
},
USE C0_1,
USE C1_0,
USE C1_1
]
children BspTree {
plane 1 0 0 -70
front BspTree {
plane 0 0 1 -70
front USE C0_0
back USE C0_1
}
back BspTree {
plane 0 0 1 -70
front USE C1_0
back USE C1_1
}
}
}