Under Evolution.


General From-Region Visibility Computation for Large Models
Jatin Chhugani     Budirijanto Purnomo     Shankar Krishnan     Subodh Kumar    

Abstract

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
Mihai Pop    Gill Barequet   Wenjing Huang   Subodh Kumar  

Abstract

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
Subodh Kumar     Dinesh Manocha     William Garrett     Ming Lin    

Abstract

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 models. 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 Extreme. The overall frame rate is improved by 40-75% as compared to the standard back-face culling implemented in hardware.

Get a compressed postscript version now.


Hierarchical Visibility Culling for Spline Models
Subodh Kumar     Dinesh Manocha    

Abstract

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.

Get a compressed postscript version now.