SURVEY ON VISIBILITY AND DATA DISTRIBUTION IN DISTRIBUTED VIRTUAL ENVIRONMENTS

Year 2015, Volume: 11 Issue: 3, 43 - 75, 21.01.2016

Yekta Kılıç Gürkan Koldaş Şafak Çevikbaş

Abstract

The importance of data distribution increases in Multi-User Distributed Virtual Environments (DVEs) in parallel to both the complexity of virtual scenes and the number of clients. Main challenges are to load the relevant part of the scene, estimate and render visible primitives by keeping the frame rate fluent, since each user sees different part of the shared scene. In order to achieve the frame rate goal, data distribution should be well managed and optimization approaches based on network and visibility should be applied according to the requirements of each DVE. This is substantially handled by considering the area of interest for each user and estimating visible primitives as early as possible. This paper surveys the research on visibility culling, data management based on area of interest in DVEs and consequently summarizes thirteen implementations in the literature.

Keywords

distributed virtual environments, data distribution management, visibility culling, area of interest

References

• Michael Capps and Seth Teller, "Communication visibility in shared virtual worlds," in Enabling Technologies: Infrastructure for Collaborative Enterprises, 1997. Proceeding, Sixth IEEE Workshops on. IEEE, 1997. [2]
• Richard M. Fujimoto, "Parallel and distributed simulation," in Proceedings of the 31st conference on Winter simulation: Simulation-a bridge to the future-Volume 1., 1999. [3]
• Katherine L. Morse and Jeffrey S. Steinman, "Data distribution management in the HLA: Multidimensional regions and physically correct filtering," in Proceedings of the 1997 Spring Simulation Interoperability Workshop, 1997. [4]
• Daniel Cohen-Or, Yiorgos L. Chrysanthou, Cláudio T. Silva, and Fredo Durand, "A survey of visibility for walkthrough applications," in Visualization and Computer Graphics, IEEE Transactions on 9.3 (2003): 412-431. [5]
• Azzedine Boukerche, Nathan J. McGraw, and R. B. Araujo, "A novel
• synchronization in large-scale distributed virtual environments," in Virtual
• Measurement Systems, 2005. VECIMS 2005. Proceedings of the 2005 IEEE International Conference on. IEEE, 2005. to
• support Environments, Human-Computer Interfaces and [6]
• Jiri Bittner and Peter Wonka, "Visibility in computer graphics," in Environment and Planning B: Planning and Design 30 (2003): 729- 755. [7]
• Jean-Sébastien Boulanger, Jörg Kienzle, and Clark Verbrugge, "Comparing interest management algorithms for massively multiplayer games," in Proceedings of 5th ACM SIGCOMM workshop on Network and system support for games, 2006. [8]
• Chris Carter, Abdennour El Rhalibi, and Madjid Merabti, “A survey of AoIM, distribution and communication in peer-to-peer online games,” in Computer Communications and Networks (ICCCN), 2012 21st International Conference on. IEEE, 2012. [9]
• Elvis S Liu, and Georgios K. Theodoropoulos. "Interest management for distributed virtual environments: A survey," in ACM Computing Surveys (CSUR)46.4 (2014): 51.
• Bingqing Shen, Jingzhi Guo, and Peng Chen. "A survey of P2P virtual world infrastructure,," in e-Business Engineering (ICEBE), 2012 IEEE Ninth International Conference on. IEEE, 2012.
• John S. Gilmore and Herman A. Engelbrecht. "A survey of state persistency in peer-to-peer massively multiplayer online games," Parallel and Distributed Systems, IEEE Transactions on 23.5, 2012, pp. 818-834.
• Eliya Büyükkaya, Maha Abdallah, and Gwendal Simon. "A survey of peer-to-peer overlay approaches for networked virtual environments," Peer-to-peer networking and applications 8.2, 2013, pp. 276-300.
• Edwin Catmull, “A subdivision algorithm for computer display of curved surfaces,”, Ph.D. dissertation, University of Utah, Salt Lake City, Utah, 1974.
• James T. Klosowski and Cláudio T. Silva, "The prioritized-layered projection algorithm for visible set estimation," in Visualization and Computer Graphics, IEEE Transactions on 6.2 (2000): 108-123.
• Gürkan Koldaş, “Efficient visibility estimation for distributed virtual urban environments,” Ph.D. dissertation, Middle East Technical University, Ankara, 2008.
• Frame rate, Wikipedia, [online] 2015, https://en.wikipedia.org/wiki/ Frame_rate (Accessed: 06 October 2015).
• Hansong Zhang, “Effective occlusion culling for the interactive display of arbitrary models,” Ph.D. dissertation, The University of North Carolina, Chapel Hill, 1998.
• Seth J. Teller and Carlo H. Séquin, "Visibility preprocessing for interactive walkthroughs," Computer Graphics. Vol. 25. No. 4., 1991.
• Ned Greene and Michael Kass, "Error-bounded antialiased rendering of complex environments," in Proceedings of the 21st annual conference on Computer graphics and interactive techniques, 1994.
• Satyan Coorg and Seth Teller, "Temporally coherent conservative visibility," in Proceedings of the twelfth annual symposium on Computational geometry, 1999.
• Satyan Coorg and Seth Teller, "Real-time occlusion culling for models with large occluders," in Proceedings of the 1997 symposium on Interactive 3D graphics, 1997.
• T. Hudson, D. Manocha, J. Cohen, M. Lin, K. Hoff, and H. Zhang, “Accelerated occlusion culling using shadow frusta,” in Proceedings of the thirteenth annual symposium on Computational geometry, 1997, pp. 1-10.
• Ned Greene, Michael Kass, and Gavin Miller, "Hierarchical Z-buffer visibility," in Proceedings of the 20th annual conference on Computer graphics and interactive techniques, 1993.
• Fausto Bernardini, James T. Klosowski, and Jihad El‐Sana, "Directional discretized occluders for accelerated occlusion culling," in Computer Graphics Forum. Vol. 19. No. 3. Blackwell Publishers Ltd, 2000.
• Jiří Bittner, Vlastimil Havran, and Pavel Slavik, "Hierarchical visibility culling with occlusion trees," in Computer Graphics International, 1998. Proceedings. IEEE, 1998.
• Frédo Durand, George Drettakis, Joelle Thollot, and Claude Puech, "Conservative visibility preprocessing using extended projections," in Proceedings of the 27th annual conference on Computer graphics and interactive techniques, 2000, pp. 239-248.
• Mojtaba Hosseini, Steve Pettifer, and Nicolas D. Georganas, "Visibility-based interest management in collaborative virtual environments," in Proceedings of the 4th international conference on Collaborative virtual environments, 2002.
• Huy T. Vo et al., "iRun: Interactive rendering of large unstructured grids," in Eurographics Symposium on Parallel Graphics and Visualization, 2007.
• Gerd Hesina and Dieter Schmalstieg, "A network architecture for remote rendering." dis-rt. IEEE, 1998.
• James F. Kurose and Keith W. Ross, “Computer networking a top- down approach,” Fifth Edition, Pearson Education, 2010, ch. 2, pp. 112-116.
• Katherine L. Morse, “Interest management in large-scale distributed simulations,” in Information and Computer Science, University of California, Irvine, 1996.
• Shun-Yun Hu, "Spatial publish subscribe," Proc. of IEEE Virtual Reality (IEEE VR) workshop, Massively Multiuser Virtual Environment (MMVE’09), 2009.
• Graham Morgan, Fengyun Lu, and Kier Store, "Interest management middleware for networked games," in Proceedings of the 2005 symposium on Interactive 3D graphics and games, 2005.
• Thomas A. Funkhouser, "RING: a client-server system for multi- user virtual environments," in Proceedings of the 1995 symposium on Interactive 3D graphics, 1995.
• Daniel Cohen-Or and Eyal Zadicario, "Visibility streaming for network-based walkthroughs," in Graphics Interface. Vol. 98. No. 1, Yohai Makbily, Craig Gotsman, and Reuven Bar-Yehuda, "Geometric algorithms for message filtering in decentralized virtual environments," in Proceedings of the 1999 symposium on Interactive 3D graphics, 1999.
• Fábio O. Moreira, Joao L.D. Comba, and Carla M.D.S. Freitas, "Smart visible sets for networked virtual environments," Computer Graphics and Image Processing, 2002. Proceedings. XV Brazilian Symposium on. IEEE, 2002.
• Jean-Eudes Marvie, Julien Perret, and Kadi Bouatouch, "Remote interactive walkthrough of city models." in Pacific Conference on Computer Graphics and Applications, 2003.
• Jimmy Chim, Rynson W.H. Lau, Hong Va Leong, and Antonio Si, “CyberWalk:
• environment,” Multimedia, IEEE Transactions on,5(4), 2003, pp. 503-515. distributed virtual
• walkthrough Wagner T. Correa, James T. Klosowski, and Claudio T. Silva, "Visibility-based prefetching for interactive out-of-core rendering," in Proceedings of the 2003 IEEE Symposium on Parallel and Large- Data Visualization and Graphics, IEEE Computer Society, 2003.
• Anthony Steed and Cameron Angus, "Frontier sets: A partitioning scheme to enable scalable virtual environments," in Proceedings of EUROGRAPHICS 2004, Short Presentations and Interactive Demos, 2004, pp: 13-17.
• Anthony Steed and Cameron Angus, "Supporting scalable peer to peer virtual environments using frontier sets," in Virtual Reality, 2005. Proceedings. VR 2005. IEEE. IEEE, 2005.
• Dihong Tian and Ghassan AlRegib, "PODS: partially ordered delivery for 3D scenes in resource-constrained environments," in Acoustics, Speech and Signal Processing, 2006. ICASSP 2006 Proceedings. 2006 IEEE International Conference on. Vol. 5. IEEE, Beomjoo Seo and Roger Zimmermann, "Edge indexing in a grid for highly dynamic virtual environments," in Proceedings of the 14th annual ACM international conference on Multimedia, 2006.
• Beomjoo Seo and Roger Zimmermann, "Quantitative analysis of visibility determinations for networked virtual environments," Journal of Visual Communication and Image Representation 23.5, 2012, pp. 705-718.
• Shun-Yun Hu, Ting-Hao Huang, Shao-Chen Chang, Wei-Lun Sung, Jehn-Ruey Jiang, and Bing-Yu Chen, “Flod: A framework for peer- to-peer 3D streaming,” in The 27th Conference on Computer Communications. IEEE, 2008.
• Revanth N. R. and P. J. Narayanan, "Distributed massive model rendering," Proceedings of the Eighth Indian Conference on Computer Vision, Graphics and Image Processing, 2012.
• Carlos Eduardo B. Bezerra, Fábio R. Cecin, and Cláudio FR Geyer, "A3: A novel interest management algorithm for distributed simulations of mmogs," in Distributed Simulation and Real-Time Applications, 2008. DS-RT 2008. 12th IEEE/ACM International Symposium on. IEEE, 2008.
• Kari Vatjus-Anttila, Timo Koskela, Seamus Hickey, and Jarkko Vatjus-Antilla, "Occlusion based message dissemination method in networked virtual environments," in Next Generation Mobile Apps, Services and Technologies (NGMAST), 2013 Seventh International Conference on. IEEE, 2013.