Algorithms and analyses: pre-reckoning algorithm for distributed virtual environments

ABSTRACT

This paper proposes a pre-reckoning algorithm for distributed virtual environments. First, an overview of dead reckoning techniques used in distributed virtual environments is provided. The benefits and drawbacks of implementing dead reckoning within specific types of distributed virtual environments are discussed. An alternative to traditional dead reckoning techniques used in DIS-compliant distributed virtual environments is proposed. The alternative, referred to as "pre-reckoning," seeks to significantly reduce prediction error with a minimal increase in the number of entity state update packets issued. The performance of the pre-reckoning algorithm is compared to one of the DIS standard algorithms for location prediction. The test cases are based upon a game-based environment where the movements of participants are influenced by physical boundaries.

REFERENCES

• 1: Wentong Cai , Francis B. S. Lee , L. Chen, An auto-adaptive dead reckoning algorithm for distributed interactive simulation, Proceedings of the thirteenth workshop on Parallel and distributed simulation, p.82-89, May 01-04, 1999, Atlanta, Georgia, United States
• 2: Capin, T., J. Esmerado, and D. Thalmann. 1999. A Dead Reckoning Technique for Streaming Virtual Human Animation. IEEE Transactions on Circuits and Systems for Video Technology 9: 411--414.
• 3: Addison Chan , Rynson W. H. Lau , Beatrice Ng, A hybrid motion prediction method for caching and prefetching in distributed virtual environments, Proceedings of the ACM symposium on Virtual reality software and technology, November 15-17, 2001, Baniff, Alberta, Canada [doi>10.1145/505008.505035]
• 4: Brook Conner , Loring Holden, Providing a low latency user experience in a high latency application, Proceedings of the 1997 symposium on Interactive 3D graphics, p.45-ff., April 27-30, 1997, Providence, Rhode Island, United States [doi>10.1145/253284.253305]
• 5: Hugh W. Holbrook , Sandeep K. Singhal , David R. Cheriton, Log-based receiver-reliable multicast for distributed interactive simulation, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.328-341, August 28-September 01, 1995, Cambridge, Massachusetts, United States
• 6: IEEE. 1995. IEEE Standard for Distributed Interactive Simulation - Application Protocols, Annex B: Dead Reckoning Definitions and Algorithms, IEEE Std 1278.1-1995. New York: IEEE Press.
• 7: Michael Knight , Tom Clancy , Richard Dal Porto, Tom Clancy's Rainbow Six: Prima's Official Strategy Guide, Prima Communications, Inc., Rocklin, CA, 1998
• 8: Michael R. Macedonia , Donald P. Brutzman , Michael J. Zyda , David R. Pratt , Paul T. Barham , John Falby , John Locke, NPSNET: a multi-player 3D virtual environment over the Internet, Proceedings of the 1995 symposium on Interactive 3D graphics, p.93-ff., April 09-12, 1995, Monterey, California, United States [doi>10.1145/199404.199419]
• 9: Sandeep K. Singhal , David R. Cheriton, Using a Position History-Based Protocol for Distributed Object Visualization, Stanford University, Stanford, CA, 1994
• 10: Sandeep Singhal , Michael Zyda, Networked virtual environments: design and implementation, ACM Press/Addison-Wesley Publishing Co., New York, NY, 1999
• 11: Ouri Wolfson , Liqin Jiang , A. Prasad Sistla , Sam Chamberlain , Naphtali Rishe , Minglin Deng, Databases for Tracking Mobile Units in Real Time, Proceeding of the 7th International Conference on Database Theory, p.169-186, January 10-12, 1999