The pfPortals Visibility Library

Copyright
Introduction
Cells, Portals, Locators, and Items
Organizing the Scene Graph
Building the Scene Graph
Callbacks
Data
API
Acknowledgements
References

Copyright

The pfPortals library is a public domain software package and may be freely used, modified, and distributed, provided certain conditions are met. The following copyright appears in the source code and applies to this documentation as well:


/***************************************************************************\

  Copyright 1995 The University of North Carolina at Chapel Hill.
  All Rights Reserved.

  Permission to use, copy, modify and distribute this software and its
  documentation without fee, and without a written agreement, is
  hereby granted, provided that the above copyright notice and the
  complete text of this comment appear in all copies, and provided that
  the University of North Carolina and the original authors are
  credited in any publications arising from the use of this software.

  IN NO EVENT SHALL THE UNIVERSITY OF NORTH CAROLINA AT CHAPEL HILL 
  OR THE AUTHOR OF THIS SOFTWARE BE LIABLE TO ANY PARTY FOR DIRECT,
  INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES, INCLUDING
  LOST PROFITS, ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS
  DOCUMENTATION, EVEN IF THE UNIVERSITY OF NORTH CAROLINA AND/OR THE
  AUTHOR OF THIS SOFTWARE HAVE BEEN ADVISED OF THE POSSIBILITY OF 
  SUCH DAMAGES.

  The author of the pfPortals1.2 software library may be contacted at:

  US Mail:             David Patrick Luebke
                       Department of Computer Science
                       Sitterson Hall, CB #3175
                       University of N. Carolina
                       Chapel Hill, NC 27599-3175

  Phone:               (919)962-1825

  EMail:               luebke@cs.unc.edu

\*****************************************************************************/

Introduction

PfPortals is a public domain software library by David Luebke which performs portal-based culling in IRIS Performer© applications. The library consists of a number of callbacks which are attached to nodes in the Performer scene graph, an interface for building the scene graph and attaching the callbacks appropriately, and an interface for controlling the behavior of the callbacks. The pfPortals library was developed at the University of North Carolina during the Spring semester of 1995.

The portal-based culling approach attempts to improve rendering performance for large models by culling away portions of the model which are completely occluded. It works best in scenarios such as architectural walkthroughs, where most of the model is typically hidden from the viewer by walls, floors and ceilings. Portal-based culling subdivides the model into cells and portals. A cell is a polyhedral volume of space; a portal is a transparent 2D region upon a cell boundary that connects adjacent cells. Cells can only "see" other cells through the portals. In an architectural model, the cell boundaries should follow the walls and partitions, so that cells roughly correspond to the rooms of the building. The portals likewise correspond to the doors and windows through which neighboring rooms can view each other.

The pfPortals library implements the portal-based culling scheme described in Portals and Mirrors: Simple, Fast Evaluation of Potentially Visible Sets, by David Luebke and Chris Georges, in the Proceedings of the 1995 Symposium on Interactive 3-D Graphics (April 1995; ACM Press). Briefly, this algorithm determines what cell contains the viewer, and what portals of that cell are visible to the viewer. Next the code recursively determines what portals of adjacent cells are visible through the portals already determined to be visible. This approach accumulates a list of visible cells without considering portions of the model far removed from the visible set.

Cells, Portals, Locators, and Items

Cells in the pfPortals library consist of pfGroups with certain callbacks attached (described below). Portals have no explicit representation in the Performer scene graph; rather, information is stored with each cell about every portal that leaves the cell. The Locator is a pfGroup which contains all of the cells in the model. Callbacks attached to the Locator node determine which cell contains the viewer and perform the actual visibility determination. Items are detailed objects within each cell which should be culled to the screen region visible through portal sequences (the cull box). Again, items in pfPortals consist of pfGroups containing the geometry of the item, with callbacks attached.

Organizing the scene graph

The ideal representation of a model in the portal-based culling scheme is the cell adjacency graph, in which nodes of the graph represent cells and arcs represent portals connecting cells. The visibility calculations performed by the pfPortals callbacks amount to a depth-first traversal of this cell adjacency graph. Unfortunately the Performer scene graph is not well suited for representing a cell adjacency graph. This is primarily because the cell adjacency graph contains cycles, which the Performer scene graph (really a hierarchy) cannot elegantly represent. In future versions of Performer this restriction may be removed, but in Performer 1.2 it is necessary to enforce a particular scene graph organization for the pfPortals callbacks to work properly. The pfPortals API includes functions to help build such a scene graph easily.

Near the root of the tree should be a pfGroup which contains all of the cells in the scene. This node is called the Locator and has certain callbacks attached to it (described below). The Locator node is created and initialized with the pfCreateLocator() function. Each cell in the scene is a pfGroup with attached callbacks. The pfAddCell() function will create a cell, add it to the Locator, attach the appropriate callbacks, and return the pfGroup pointer to you. Every node representing geometry within a cell must then be added as a child or descendent of that pfGroup. For large cells containing many detailed objects, it is still a good idea to arrange the objects hierarchically within the cell to take full advantage of view-frustum culling. Once a cell has been created with pfAddCell(), portals may be added at any time with the pfAddPortal() function.

Building the Scene Graph

Application Programmer's Interface

The following API functions allow the user to build the adjacency graph of cells and portals:

pfGroup *pfCreateLocator(void)
This function creates the special pfGroup called the Locator. The Locator will contain all cells added to the model, and should be placed near the root of the scene graph. PfCreateLocator() sets the appropriate data structures and callbacks and returns a pointer to the Locator pfGroup.
pfGroup *pfAddCell(char *name)
This function creates a pfGroup with the specified name, allocating and initializing the appropriate structures. The cell is then added as a child of the Locator, attaches the cell callbacks (described below, and returns a pointer to the cell. If a cell with the specified name has already been added, pfAddCell() does nothing and returns a pointer to that cell.
void pfAddPortal(pfGroup *source, char *dest, int numverts, pfVec3 *verts)
This function adds a portal from the first cell (specified as a pointer to a pfGroup) to the second cell (specified by name). If the named cell does not exist pfAddCell() is called to create it. The vertices of the portal must be specified in world coordinates.

The following API functions give the user of the pfPortals library control over how the various callbacks behave:

void pfInitPortals(void)
This function initializes the library and should be called before any other pfPortals call.
void pfEnablePortals(void)
This function enables portal-based culling.
void pfDisablePortals(void)
This function disables portal-based culling. All cells are considered visible. Note that standard view-frustum culling may still cull out some invisible portions of the model.
int pfQueryPortals(void)
This function returns 1 if portals are currently enabled and 0 otherwise.
void pfEnablePortalBounds(void)
This function turns on portal boundaries, highlighting the bounds viewing frustum in red and the cull boxes for each portal in green. This can be a useful debugging tool.
void pfDisablePortalBounds(void)
This function turns off portal boundaries.
int pfQueryPortalBounds(void)
This function returns 1 if portal boundaries are currently enabled and 0 otherwise.
void pfEnableSmallFrustum(void)
This function enables culling to a simulated small viewing frustum in the center 60% of the screen. Along with pfEnablePortalBounds, this can be a useful debugging tool and an excellent illustration of the underlying algorithm.
void pfDisableSmallFrustum(void)
This function disables culling to the simulated small viewing frustum.
int pfQuerySmallScreen(void)
This function returns 1 if the simulated small viewing frustum is enabled and 0 otherwise.
void pfSetLocateFunction(pfLocateFunctionType *myfunc)
This function allows the user of the pfPortals library to hook in a custom function which determines the cell containing the viewer. The pfPortals library currently uses a rudimentary function for this purpose which assumes axis-aligned, rectangular cells. A much better approach would be to perform collision detection between the viewpoint, walls, and portals of the current cell, and only to allow the user to pass through portals. The pfSetLocatorFunction hook allows the programmer to specify this or another sophisticated Locator function. The function passed to pfSetLocatorFunction should return a pointer to the pfGroup for the cell containing the viewer. The arguments passed to the function will be the current pfTraverser (of which the Locator will be the current node) and the pfLocatorData structure attached to the Locator.
pfLocateFunctionType pfQueryLocateFunction(void)
This function will return a pointer to the function set with pfSetLocatorFunction, of NULL if no function has been specified (in which case the built-in function will be used).

Callbacks

The pfCreateLocator(), pfAddCell(), and pfAddPortal() functions attach the following functions to nodes in the Performer scene graph as CULL and DRAW callbacks. Under normal circumstances you should not have to deal with these functions at all; they are attached and called automatically by the pfPortals library and the Performer scene traversal.

pfEnterCellCull: This should be attached as a CULL pre-callback to the pfGroup representing a cell.
pfExitCellCull: This should be attached as a DRAW post-callback to the pfGroup representing a cell.
pfEnterLocatorCull: This should be attached as a CULL pre-callback to the pfGroup representing the Locator.
pfEnterLocatorDraw: This should be attached as a DRAW pre-callback to the pfGroup representing the Locator.
pfExitLocatorDraw: This should be attached as a DRAW post-callback to the pfGroup representing the Locator.

Data

The pfPortals library fills out the following data structures and in some cases attaches them to nodes in the Performer scene graph. This information is provided primarily for those who want to extend pfPortals; under normal circumstances the pfPortals user should not have to deal with these structures at all.

pfPortalData: Every portal in the model is represented by two pfPortalData structures, one for each direction. Note that which direction the portal faces is determined by the ordering of the vertices. The 'normal' field is for internal use and need not be specified by the user. The texture-related fields will be used by a future release of the library and are not currently used.
- attached_cell - The cell on the 'other side' of the portal.
- numverts - The number of vertices that make up the portal. Must be less than PFPORTAL_MAX_VERTS, defined in pfPortals.h.
- verts - The actual array of vertices.
- normal - For internal use.
- numtextures - For internal use, not currently used.
- textures - For internal use, not currently used.
- texflag - For internal use, not currently used.
pfCellData: Each cell in the model is represented by a pfCellData structure, which will be attached to the appropriate pfGroup for the CULL and DRAW traversals via pfAddCell().
- numportals - The number of portals for this cell.
- portals - The actual array of portals.
- index - for internal use.
- numcullboxes - For internal use.
- cullboxes - For internal use.
pfItemData: Each item within a cell is represented by a pfItemData structure, which should be attached to the appropriate pfGroup for the CULL traversal via pfNodeTravData().
- parent_cell - The cell which contains this item.
- bbox - The axial bounding box of this item.
LocatorData: This data structure represents the Locator and will be attached via pfCreateLocator().
- numcells - The number of cells in the model.
- cells - The actual array of pfCellData pointers for the cells.
- bboxes - An array of the axial bounding boxes for each cell. This is only used by the built-in Locator function for determining which cell the user is in and need not be specified if the user provides a custom locator function via pfSetLocateFunction().

Acknowledgements

The author would like to extend his sincere thanks to Dr. Fred Brooks, Chris Georges, Mike Goslin, Brad Grantham, Michael Jones, and everybody else at UNC and SGI who helped create, test, and support the pfPortals library. Initial work on the pfPortals algorithms and software was supported by ARPA Contract DABT63-93-C-C048.

References

A great deal of excellent work has been done on portal-based visibility schemes. The pfPortals library is intellectually indebted to all of the following authors and papers:

[1] Jones, C.B. A New Approach to the `Hidden Line' Problem. The Computer Journal, vol. 14 no. 3 (August 1971), 232..

[2] Airey, John. Increasing Update Rates in the Building Walkthrough System with Automatic Model-Space Subdivision and Potentially Visible Set Calculations. Ph.D. thesis, UNC-CH CS Department TR #90-027 (July 1990).

[3] Teller, Seth. Visibility Computation in Densely Occluded Polyhedral Environments. Ph.D. thesis, UC Berkeley CS Department, TR #92/708 (1992).