General From-Region Visibility Computation for Large Models
We present an efficient hardware-accelerated algorithm
for region based visibility computation of large polygonal
models. The algorithm works for general, out-of-core 3D scenes.
It conservatively bounds shadow-volumes and reduces the general
shadow containment problem to hardware occlusion queries.
As a result, we are able to take advantage of occluder
fusion. We also present a 2.5D variant that is able to bound the
frusta more tightly.
Empirical results show that our algorithm
overestimates the real visibility only by a factor of 2-5 and
takes less than a second per cell for large 3D scenes.
Efficient Perspective-Accurate Silhouette Computation
Silhouettes are perceptually and geometrically salient
features of geometric models. Hence a number of graphics and visualization
applications need to find them to aid further processing.
The efficient computation of silhouettes, especially in the context of
perspective projection, is known to be difficult.
This paper presents a novel efficient and practical algorithm to compute
silhouettes from a sequence of viewpoints under perspective projection.
Parallel projection forms a special case of this algorithm. Our
approach is based on the point-plane duality in three dimensions, that allows the
efficient computation of the changes in the silhouette of a polygonal model
between consecutive frames.
We also present several applications of our technique to a
variety of problems from computer graphics to medical visualization. We
also provide experimental data that prove the efficiency of our approach.
Download link coming shortly
Hierarchical Back-Face Computation
We present a sub-linear algorithm to compute the set of
back-facing polygons in a polyhedral model. The algorithm
partitions the model into hierarchical clusters based
on the orientations and positions of the polygons.
As a pre-processing step, the algorithm constructs
spatial decompositions with respect to each cluster.
For a sequence of back-face computations, the algorithm exploits the
coherence in view-point movement to efficiently determine if
it is in front of or behind a cluster. Due to coherence, the algorithm's
performance is linear in the number of clusters on average.
We have applied this algorithm to speed up the rendering of polyhedral
On average, we are able to cull almost half the polygons. The algorithm
accounts for 5-10% of the total CPU time per frame on an SGI Indigo2
frame rate is improved by 40-75% as compared to the standard back-face
culling implemented in hardware.
compressed postscript version now.
Hierarchical Visibility Culling for Spline Models
We present hierarchical algorithms for visibility culling of spline models.
This includes back-patch culling, a generalization of back-face culling for
polygons to splines. These algorithms are extended to trimmed surfaces as
well. We propose different spatial approximations for enclosing the normals
of a spline surface and compare them for efficiency and effectiveness on
different graphics systems. We extend the culling algorithms using
hierarchical techniques to collection of surface patches and combine them
with view-frustum culling to formulate a ONE (Object-Normal Exclusion)-tree
for a given model. The algorithm traverses the ONE-tree at run time and
culls away portions of the model not visible from the current viewpoint.
These algorithms have been implemented and applied to a number of large
models. In practice, we are able to speed-up the overall spline rendering
algorithms by about 20-30% based on back-patch culling only and by more than
50% using ONE-trees.
compressed postscript version now.