Culling an Object Hierarchy to a Frustum Hierarchy

Introduction

Visibility culling of a scene is central to any interactive graphics application. The idea is to limit the geometry sent down the rendering pipeline to only the geometry with a fair chance of finally becoming visible. It is important for the culling stage to be fast for it to be effective; otherwise the performance gain achieved will be overshadowed. Hierarchical scene structures are commonly used to speed up the process. Hierarchical culling of bounding boxes to a view frustum is fast and sufficient in most applications. However, when there are multiple view frustums (as in a tiled display wall), visibility culling time becomes substantial and cannot be hidden by pipelining it with other stages of rendering.

Here, we address the problem of culling an object hierarchy to a hierarchically organized set of frustums, such as those found in tiled displays and shadow volume computation. We present an adaptive algorithm to unfold the Object Hierarchy (OH) or Frustum hierarchy (FH) at every stage in the culling procedure. Our algorithm computes from-point visibility and is conservative. The precomputation required is minimal, allowing our approach to be applied for dynamic scenes as well.

Design & Features

Features of the Adaptive OH and FH culling Algo ::fh2

  • Faster running time than existing solutions based etirely on either OH or FH
  • Use of Heirarchies potentially eliminates half objects and frustums in each step
  • Sublinear running time, adapts according to viewpoint and "goodness" of the scene.
  • Simple PCA based preprocessing required to compute Oriented Bounding boxes
  • Can work with OBB's, AABB's or Bounding Spheres
  • Scales sublineraly to to both object and frustum count, suitable for very large number of objects and large tiled displays
  • Dynamic objects can be used as only cheap OBB/AABB computation is needed every frame
  • Easily extendable to a generalized arrangement of view frustums

We first find all the objects in the Primary view frustum and then call the Adaptive algorithm for every object present inside the Primary view frustum. The Adaptive algoritm is recursive in nature. The basic steps involved are::

Algorithm Adaptive Culling. Inputs: Object Node and Frustum Nodealgo

  • If the Frustum node is a leaf node, mark the Object node visible to this frustum and return.
  • [L,C,R] = Classify the children of the Object Node according to their orientation with respect to the Frusum node's bisection plane.
  • Send All objects in set C to both sub-frustums of the Frustum Node using this algorithm again
  • Send All objects in set L to the left sub-frustum using this algorithm again
  • Send All objects in set R to the right sub-frusrum using this algorithm again

The time complexity of the algorithm is roughly of O (min (N*logM, M*logN)) where N = Number of objects and M = Number of view frustums.

Related Publication

  • Nirnimesh, Pawan Harish and P. J. Narayanan - Garuda: A Scalable, Tiled Display Wall Using Commodity PCs Proc. of IEEE Transactions on Visualization and Computer Graphics(TVCG), Vol.13, no.~5, pp.864-877, 2007. [PDF]

  • Nirnimesh, Pawan Harish and P. J. Narayanan - Culling an Object Hierarchy to a Frustum Hierarchy, 5th Indian Conference on Computer Vision, Graphics and Image Processing, Madurai, India, LNCL 4338 pp.252-263,2006. [PDF]

Associated People