|
Published Articles >> Table of Contents >> Abstract
November 2004 (Vol. 16, No. 11)
pp. 1357-1369
The Hierarchical Degree-of-Visibility Tree
Lidan Shou
Zhiyong Huang, IEEE
Kian-Lee Tan, IEEE Computer Society
Full Article Text:
   
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/TKDE.2004.78
Send link to a friend
| Abstract |
|
In this paper, we present a novel structure called the Hierarchical Degree-of-Visibility Tree (HDoV-tree) for visibility query processing in visualization systems. The HDoV-tree builds on and extends the R-tree such that 1) the search space is pruned based on the degree of visibility of objects and 2) internal nodes store level-of-details (LoDs) that represent a collection of objects in a coarser form. We propose two tree traversal algorithms that balance performance and visual fidelity, explore three storage structures for the HDoV-tree, and develop novel caching techniques for disk-based HDoV-tree. We implemented the HDoV-tree in a prototype walkthrough system called VISUAL. Our experimental study shows that VISUAL can lead to high frame rates without compromising visual fidelity.
|
 References
|
[1] P.K. Agarwal, S. Har-Peled, and Y. Wang, Occlusion Culling for Fast Walkthrough in Urban Areas Proc. Eurographics 2001 (short presentation), Sept. 2001.
[2] D. Aliaga, J. Cohen, A. Wilson, E. Baker, H. Zhang, C. Erikson, K. Hoff, and T. Hudson, MMR: An Interactive Massive Model Rendering System Using Geometric and Image-Based Acceleration Proc. ACM Symp. Interactive 3D Graphics, pp. 199-206, 1999.
[3] J. Bittner, V. Havran, and P. Slavik, Hierarchical Visibility Culling with Occlusion Trees Proc. Computer Graphics Int'l '98, pp. 207-219, June 1998.
[4] T.A. Funkhouser, C.H. Sequin, and S.J. Teller, Management of Large Amounts of Data in Interactive Building Walkthroughs Proc ACM SIGGRAPH Symp. Interactive 3D Graphics, pp. 11-20, Mar. 1992.
[5] A. Guttman, R-Trees: A Dynamic Index Structure for Spatial Searching Proc. 1984 ACM SIGMOD Int'l Conf. Management of Data, pp. 47-57, 1984.
[6] M. Kofler, M. Gervautz, and M. Gruber, R-Trees for Organizing and Visualizing 3D GIS Databases J. Visualization and Computer Animation, vol. 11, pp. 129-143, 2000.
[7] V. Koltun, Y. Chrysanthou, and D. Cohen-Or, Hardware Assisted Culling Using a Dual Ray Space Proc. Eurographics Rendering Workshop, pp. 204-213, 2001.
[8] C. Saona-Vázquez, I. Navazo, and P. Brunet, The Visibility Octree: A Data Structure for 3D Navigation Computers&Graphics, vol. 23, pp. 635-643, 1999.
[9] L. Shou, C. Chionh, Y. Ruan, Z. Huang, and K.L. Tan, Walking through a Very Large Virtual Environment in Real-Time Proc. 27th Int'l Conf. Very Large Data Bases, pp. 401-410, 2001.
[10] L. Shou, Z. Huang, and K.L. Tan, Hdov-Tree: The Structure, the Storage, the Speed Proc. 19th Int'l Conf. Data Eng., 2003.
[11] L. Shou, Querying Large Virtual Models for Interactive Walkthrough PhD thesis, Nat'l Univ. Singapore, 2002.
[12] S.J. Teller and C.H. Sequin, Visibility Preprocessing for Interactive Walkthroughs Computer Graphics (Proc. SIGGRAPH '91), vol. 25, no. 4, pp. 61-69, 1991.
|
 Additional Information
|
Index Terms- Degree of visibility, HDoV-tree, level-of-details, performance and visual fidelity, virtual environment.
Citation:
Lidan Shou, Zhiyong Huang, Kian-Lee Tan,
"The Hierarchical Degree-of-Visibility Tree,"
IEEE Transactions on Knowledge and Data Engineering,
vol. 16,
no. 11,
pp. 1357-1369,
Nov.,
2004
|
|
RSS Feed