A new BSP tree framework incorporating dynamic LoD models

ABSTRACT

In this paper we present a new BSP (Binary Space Partitioning (BSP) tree. BSP trees are one of the most successful space partitioning techniques, since they allow both object modeling and classification in one single structure. In this paper, we present a new framework designed for a multi-resolution modeling system that incorporates the BSP tree structure and dynamic levels of detail models. It has the advantages of both BSP and multi-resolution representations. The tree construction and traversal routines for the multi-resolution BSP tree are discussed in detail. Images and timing for our implementation are provided.

REFERENCES

• 1: Daniel Aliaga , Jonathan Cohen , Andrew Wilson , Hansong Zhang , Carl Erikson , Kenneth Hoff , Thomas Hudson , Wolfgang Stuerzlinger , Eric Baker , Rui Bastos , Mary Whitton , Fred Brooks , Dinesh Manocha, A Framework for the Real-Time Walkthrough of Massive Models, University of North Carolina at Chapel Hill, Chapel Hill, NC, 1998
• 2: E. Puppo, R. Scopigro. Simplification, LoD and Multiresolution --Principle and Applications. EUROGRAPHICS'97, Tutorial Notes(ISSN1017-4656), Eurographics Association, 1997
• 3: Zhigeng Pan, Xiaohu Ma, and Jiaoying Shi, An Overview of Techniques for creating Models at Multiple LoD, Journal of Image and Graphics, 3(9),pp754-759,1998
• 4: William J. Schroeder , Jonathan A. Zarge , William E. Lorensen, Decimation of triangle meshes, ACM SIGGRAPH Computer Graphics, v.26 n.2, p.65-70, July 1992
• 5: P. Cignoni, C. Montani, C. Rocchini. Preserving Attributes Values on simplified Meshes by Resampling Detail Textures. The Visual Computer, 15, pp519-539,1999
• 6: Jonathan Cohen , Amitabh Varshney , Dinesh Manocha , Greg Turk , Hans Weber , Pankaj Agarwal , Frederick Brooks , William Wright, Simplification envelopes, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.119-128, August 1996 [doi>10.1145/237170.237220]
• 7: Hugues Hoppe, Progressive meshes, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.99-108, August 1996 [doi>10.1145/237170.237216]
• 8: Michael Garland , Paul S. Heckbert, Surface simplification using quadric error metrics, Proceedings of the 24th annual conference on Computer graphics and interactive techniques, p.209-216, August 1997 [doi>10.1145/258734.258849]
• 9: Jonathan Cohen , Marc Olano , Dinesh Manocha, Appearance-preserving simplification, Proceedings of the 25th annual conference on Computer graphics and interactive techniques, p.115-122, July 1998 [doi>10.1145/280814.280832]
• 10: Hugues Hoppe, View-dependent refinement of progressive meshes, Proceedings of the 24th annual conference on Computer graphics and interactive techniques, p.189-198, August 1997 [doi>10.1145/258734.258843]
• 11: David Luebke , Carl Erikson, View-dependent simplification of arbitrary polygonal environments, Proceedings of the 24th annual conference on Computer graphics and interactive techniques, p.199-208, August 1997 [doi>10.1145/258734.258847]
• 12: Julie C. Xia , Amitabh Varshney, Dynamic view-dependent simplification for polygonal models, Proceedings of the 7th conference on Visualization '96, p.327-ff., October 28-29, 1996, San Francisco, California, United States
• 13: Rynson W. H. Lau , Danny S. P. To , Mark Green, Adaptive Multi-Resolution Modeling Technique Based on Viewing and Animation Parameters, Proceedings of the 1997 Virtual Reality Annual International Symposium (VRAIS '97), p.20, March 01-05, 1997
• 14: Thomas A. Funkhouser , Carlo H. Séquin, Adaptive display algorithm for interactive frame rates during visualization of complex virtual environments, Proceedings of the 20th annual conference on Computer graphics and interactive techniques, p.247-254, September 1993 [doi>10.1145/166117.166149]
• 15: William C. Thibault , Bruce F. Naylor, Set operations on polyhedra using binary space partitioning trees, ACM SIGGRAPH Computer Graphics, v.21 n.4, p.153-162, July 1987
• 16: M. S. Paterson , F. F. Yao, Binary partitions with applications to hidden surface removal and solid modelling, Proceedings of the fifth annual symposium on Computational geometry, p.23-32, June 05-07, 1989, Saarbruchen, West Germany [doi>10.1145/73833.73836]
• 17: A. T. Campbell, III , Donald S. Fussell, Adaptive mesh generation for global diffuse illumination, ACM SIGGRAPH Computer Graphics, v.24 n.4, p.155-164, Aug. 1990
• 18: Y.Chyscmthou, and M.Slater, Computing Dynamic Changes to BSP Trees, Computer Graphics Forum(Eurographics'92 Proceedings),pp321-332,1992
• 19: E.Torres, Optimization of the BSP lbr the Visualization of Dynamic Scenes, Eurographic'90 Proceedings:507- 518,1990
• 20: Yiorgos Chrysanthou , Mel Slater, Shadow volume BSP trees for computation of shadows in dynamic scenes, Proceedings of the 1995 symposium on Interactive 3D graphics, p.45-50, April 09-12, 1995, Monterey, California, United States [doi>10.1145/199404.199412]
• 21: J. Huerta , M. Chover , R. Quiros , R. Vivo , J. Ribelles, Binary space partitioning trees: a multiresolution approach, Proceedings of the IEEE Conference on Information Visualisation, p.148, August 27-28, 1997
• 22: Charles Wiley , A. T. Campbell, III , Stephen Szygenda , Donald Fussell , Fred Hudson, Multiresolution BSP trees applied to terrain, transparency, and general objects, Proceedings of the conference on Graphics interface '97, p.88-96, May 1997, Kelowna, British Columbia, Canada
• 23: RCignoni, C.Montani, C.Rocchini, R.Scopogno, Resolution Modeling. Technical Report C97-02, CNUCE-C.N.R., Pisa, Italy, 1997
• 24: Zhiliang Tao, Zhigeng Pan, and Jiaoying Shi, A Hierarchical Dynamic Simplification Method for Complex Environments, Journal of Image and Graphics,3(12), pp1032-1035, 1998

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.3 Picture/Image Generation

General Terms:
Algorithms, Experimentation

Keywords:
BSP trees, Multi-resolution modeling, mesh simplification, real-time rendering