The pfPortals Visibility Library


Table of Contents

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: The following API functions give the user of the pfPortals library control over how the various callbacks behave:

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.

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.

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).


© 1995 Copyright by the University of North Carolina and David Luebke.