Conservative visibility preprocessing for walkthroughs of complex urban scenes

ABSTRACT

Visibility preprocessing is a useful method to reduce the complexity of scenes to be processed in real-time, and so enhances the overall rendering performance for interactive visualization of virtual environments. In this paper, we propose an efficient visibility preprocessing method. The proposed method is able to handle more general environments, like urban environments, and remove invisible polygons jointly blocked by multiple occluders. The proposed method requires O(nm) time and O(n+m) space. By selecting a suitable value for m. user can select a suitable level of trade-off between the preprocessing time and the quality of the computational result. In the proposed method, we assume that navigatable areas in virtual environments are partitioned into rectangular parallelepiped cells or sub-worlds. To preprocess the visibility of each polygon for a given partitioned cell, we should determine at least the area-to-area visibility. That is inherently a four-dimensional problem. In the proposed method, we efficiently express four-dimensional visibility information on two-dimensional spaces and keep it within a ternary tree. which is conceptually similar to a BSP(Binary Space Partitioning) tree, by exploiting the characteristics of conservative visibility.

REFERENCES

• 1: Ned Greene , Michael Kass , Gavin Miller, Hierarchical Z-buffer visibility, Proceedings of the 20th annual conference on Computer graphics and interactive techniques, p.231-238, September 1993 [doi>10.1145/166117.166147]
• 2: Ned Greene, Hierarchical polygon tiling with coverage masks, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.65-74, August 1996 [doi>10.1145/237170.237207]
• 3: T. Hudson , D. Manocha , J. Cohen , M. Lin , K. Hoff , H. Zhang, Accelerated occlusion culling using shadow frusta, Proceedings of the thirteenth annual symposium on Computational geometry, p.1-10, June 04-06, 1997, Nice, France [doi>10.1145/262839.262847]
• 4: Hansong Zhang , Dinesh Manocha , Tom Hudson , Kenneth E. Hoff, III, Visibility culling using hierarchical occlusion maps, Proceedings of the 24th annual conference on Computer graphics and interactive techniques, p.77-88, August 1997 [doi>10.1145/258734.258781]
• 5: Satyan Coorg , Seth Teller, Real-time occlusion culling for models with large occluders, Proceedings of the 1997 symposium on Interactive 3D graphics, p.83-ff., April 27-30, 1997, Providence, Rhode Island, United States [doi>10.1145/253284.253312]
• 6: T. Funkhouser, S. Teller and D. Khorramabadi, The UC Berkeley System for Interactive Visualization of Large Architectural Models, Presence, 5(1), 1995.
• 7: Harry Plantinga , Charles R. Dyer, Visibility, occlusion, and the aspect graph, International Journal of Computer Vision, v.5 n.2, p.137-160, Nov. 1990 [doi>10.1007/BF00054919]
• 8: Ziv Gigus , John Canny , Raimund Seidel, Efficiently Computing and Representing Aspect Graphs of Polyhedral Objects, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.13 n.6, p.542-551, June 1991 [doi>10.1109/34.87341]
• 9: Frédo Durand , George Drettakis , Claude Puech, The visibility skeleton: a powerful and efficient multi-purpose global visibility tool, Proceedings of the 24th annual conference on Computer graphics and interactive techniques, p.89-100, August 1997 [doi>10.1145/258734.258785]
• 10: K.H. Yoo, D.S. Kim, S.Y.Shin and K.Y.Chwa, Linear-Time Algorithms for Finding the Shadow Volumes from a Convex Area Light Source, Algorithmica, 20:227-241, 1998.
• 11: Alvin Theophilus Campbell, III, Modeling global diffuse illumination for image synthesis, University of Texas at Austin, Austin, TX, 1992
• 12: Norman Chin , Steven Feiner, Fast object-precision shadow generation for area light sources using BSP trees, Proceedings of the 1992 symposium on Interactive 3D graphics, p.21-30, June 1992, Cambridge, Massachusetts, United States [doi>10.1145/147156.147159]
• 13: Seth J. Teller, Computing the antipenumbra of an area light source, Proceedings of the 19th annual conference on Computer graphics and interactive techniques, p.139-148, July 1992
• 14: George Drettakis , Eugene Fiume, A fast shadow algorithm for area light sources using backprojection, Proceedings of the 21st annual conference on Computer graphics and interactive techniques, p.223-230, July 1994 [doi>10.1145/192161.192207]
• 15: A. James Stewart , Sherif Ghali, Fast computation of shadow boundaries using spatial coherence and backprojections, Proceedings of the 21st annual conference on Computer graphics and interactive techniques, p.231-238, July 1994 [doi>10.1145/192161.192210]
• 16: Seth Jared Teller, Visibility computations in densely occluded polyhedral environments, University of California at Berkeley, Berkeley, CA, 1992
• 17: D.S. Kim, Visibility Layers and their Applications to Rendering, Ph.D. thesis, Computer Science Department, Korea Advanced Institute of Science and Technology, 1997.
• 18: R. Yagel and W. Ray, Visibility Computation for Efficient Walkthrough of Complex Environments, Presence, 5(1): 45- 60, MIT Press, 1996.
• 19: D. Cohen-Or, G. Fibich, D. Halperin and E. Zadicario, Conservafve Visibility and Strong Occlusion for Viewspace Partitioning of Densely Occluded Scenes, In Eurographics '98 Conjerence Proceedings, 1998.
• 20: A.M. Waxman and K.Y. Wohn, Image Flow Theory: A frame work for 3-D Inference from Time-varying Imagery, Advances in Computer Vision Vol 1. Christopher Brown (Ed.), pages 165-224, Lawrence Erlbaum Assoc., 1988.
• 21: R.C. Bolles, H.H. Baker, and D.H. Marimont, Epipolar-Plane Image Analysis: An Approach to Determining Structures from Motion, Inter. J. Computer Vision, 1:7-55, 1987.
• 22: Nina Amenta, Bounded boxes, Hausdorff distance, and a new proof of an interesting Helly-type theorem, Proceedings of the tenth annual symposium on Computational geometry, p.340-347, June 06-08, 1994, Stony Brook, New York, United States [doi>10.1145/177424.178064]
• 23: Gernot Schaufler , Julie Dorsey , Xavier Decoret , François X. Sillion, Conservative volumetric visibility with occluder fusion, Proceedings of the 27th annual conference on Computer graphics and interactive techniques, p.229-238, July 2000 [doi>10.1145/344779.344886]
• 24: Frédo Durand , George Drettakis , Joëlle Thollot , Claude Puech, Conservative visibility preprocessing using extended projections, Proceedings of the 27th annual conference on Computer graphics and interactive techniques, p.239-248, July 2000 [doi>10.1145/344779.344891]
• 25: Peter Wonka , Michael Wimmer , Dieter Schmalstieg, Visibility Preprocessing with Occluder Fusion for Urban Walkthroughs, Proceedings of the Eurographics Workshop on Rendering Techniques 2000, p.71-82, June 26-28, 2000

INDEX TERMS

Keywords:
Conservative Visibility, Occlusion Culling, Visibility Determination, Visibility Preprocessing