«A DISSERTATION SUBMITTED TO THE DEPARTMENT OF COMPUTER SCIENCE AND THE COMMITTEE ON GRADUATE STUDIES OF STANFORD UNIVERSITY IN PARTIAL FULFILLMENT OF ...»
EFFECTIVE REMOTE MODELING IN LARGE-SCALE DISTRIBUTED
SIMULATION AND VISUALIZATION ENVIRONMENTS
SUBMITTED TO THE DEPARTMENT OF COMPUTER SCIENCE
AND THE COMMITTEE ON GRADUATE STUDIES
OF STANFORD UNIVERSITY
IN PARTIAL FULFILLMENT OF THE REQUIREMENTS
FOR THE DEGREE OF
DOCTOR OF PHILOSOPHYSandeep Kishan Singhal August 1996 c Copyright 1997 by Sandeep Kishan Singhal All Rights Reserved ii I certify that I have read this dissertation and that in my opinion it is fully adequate, in scope and in quality, as a dissertation for the degree of Doctor of Philosophy.
David R. Cheriton (Principal Adviser) I certify that I have read this dissertation and that in my opinion it is fully adequate, in scope and in quality, as a dissertation for the degree of Doctor of Philosophy.
Patrick M. Hanrahan I certify that I have read this dissertation and that in my opinion it is fully adequate, in scope and in quality, as a dissertation for the degree of Doctor of Philosophy.
Approved for the University Committee on Graduate Studies:
iii Abstract The best Qualiﬁcation of a Prophet is to have a good Memory.
– George Savile A Distributed Interactive Simulation application provides a group of users with the illusion of a single, coherent virtual world, even though the users may be physically located at different machines connected by a network. These applications demand that each user sees a consistent virtual world view, that users are able to interact closely with one another and with other simulation entities in the virtual world, and that maximum realism is provided by hiding the distributed nature of the application from users.
Faster processors, more powerful graphics hardware, and higher-capacity networks are support- ing the development of distributed simulation applications containing more simulation entities and more detailed models of entity appearance and behavior. Consequently, these networked virtual environments are seeing increased use for multiplayer video games, military and industrial train- ing, and collaborative engineering (e.g. collaborative design and distributed simulation of complex engineering models). Large distributed interactive simulation applications are growing to include well over 100,000 dynamic entities. Achieving the size and detail required by future simulations is constrained by limits in network bandwidth, network latency, and host processing power.
This thesis describes network protocols and algorithms to support remote modeling, allowing a host to model and render remote entities in large-scale distributed simulations. These techniques require fewer network resources and simultaneously support a broader range of entity types than previous approaches. The thesis begins by describing the Position History-Based Dead Reckoning (PHBDR) protocol, a simple, efﬁcient protocol which provides smooth, accurate remote position modeling and minimizes dependencies on network performance and entity representation. We use
Axis Point Protocol: Models remote entity orientation by tracking the position of points in the entity’s local coordinate system. This protocol is designed to extract information from a broad range of entity representations.
Multiple-Detail Channels: A protocol architecture for remotely modeling complex entities— those having non-rigid structure or articulated parts—at different levels of detail depending on locally available computational and network resources. This technique allows each host to allocate its local network and computational resources toward entities that are of primary local interest.
Projection Aggregation Entities: A protocol for dynamically bundling information from a group of remote entities based on their type and location. This protocol is used for remotely modeling distant or uninteresting entities at a low level of detail.
In presenting these techniques, this thesis shows that a simple, efﬁcient protocol can provide smooth, accurate remote position modeling and that it can be applied recursively to support entity orientation, structure, and aggregation at multiple levels of detail; these protocols offer performance and costs that are competitive with more complex and application-speciﬁc approaches, while providing simpler analyses of behavior by exploiting this recursive structure. In support of this claim,
this thesis shows that:
PHBDR is a simple, efﬁcient protocol that provides smooth and accurate remote modeling for a broad range of entities and explicitly recognizes network latency.
PHBDR is still smooth and accurate when used to model entity orientation, entity structure at multiple levels of detail, and entity aggregations.
The recursive protocol structuring provides better network performance and reduced software complexity when compared with the application-speciﬁc approaches deployed in previous systems.
I have discovered that the process of writing a Doctoral thesis is much like a barn raising common in pioneer communities during the nineteenth century. In a barn raising, relatives, friends, neighbors, and even complete strangers would gather to help a family erect a new barn. The barn’s completion was met with a community-wide celebration. That tradition reveals how the ﬁrst pioneers, while being adventurous, recognized the need to exchange knowledge and experience with each other by developing and maintaining a strong sense of community. Probably the biggest lesson I have learned in graduate school is the importance of such collaboration among modern-day research pioneers. Dozens of people have offered suggestions and insight, information, and encouragement that contributed to this thesis and the research it describes. Indeed, for my own little thesis barn raising, I am indebted to relatives, friends, neighbors, and complete strangers.
I thank my advisor, Professor David Cheriton, for his advice and support in performing this research. He has a unique intuition for what will and will not work, and his on-the-spot suggestions often saved me hours of fruitless programming. David always demanded that my research yield high-impact results and “not embarrass the grandkids.” He has taught me that real engineering is a series of design tradeoffs. Finally, he has provided an invigorating research environment in which people are expected to question any and all ideas put before them.
Professor Patrick Hanrahan and Consulting Professor Craig Partridge read this thesis critically, and it beneﬁted greatly from their comments. Professors Marc Levoy and Gio Wiederhold also pointed me toward several related references, while Anthony Tomasic ﬁrst observed the relationship between real-time aggregation and data warehousing applications.
I have become notorious for walking down the hallways and bothering everyone with my latest vi research problems. My work beneﬁted greatly from discussions with numerous members of my research group, particularly Ken Duda, Michael Greenwald, Hugh Holbrook, and Matt Zelesko.
I especially thank Hugh who, along with Eric Halpern, implemented most of the PARADISE distributed simulation system on which many of my protocols were deployed. Luis Gravano, David Hoffman, and Hugh McGuire were always willing to drop everything, listen to my ideas, and offer valuable suggestions, even though my research was wholly unrelated to their own.
Numerous other people took time out of their busy schedules to provide information about their (often unpublished) work: Judith Dahmann (The MITRE Corporation), John Hines and Adam Whitlock (Naval Research and Development (NRaD)), Marty Johnson (Science Applications International Corporation (SAIC)), Yoshifumi Kitamura (ATR Communication Systems Research Laboratories), Duncan Miller and Dan Van Hook (MIT Lincoln Laboratories), Nobutatsu Nakamura (NEC Information Technology Research Laboratories), Kenny Sato (Sumitomo Electric Industries Limited), Dan Schab (Naval Air Warfare Center–Training Systems Division (NTSC)) who also provided the F-16 ﬂight traces used in Chapter 4, Greg Troxel (BBN), and Michael Zyda (Naval Postgraduate School (NPS)). Randy Garrett (Institute for Defense Analysis (IDA)/DARPA) ﬁrst offered me the opportunity to become involved with the STOW program and learn about cuttingedge military simulation technology; he and Stuart Milner (also of DARPA) ensured the availability of any information I needed and could always direct me to people capable of answering my questions. This thesis has truly beneﬁted from an understanding of real application demands that I gained courtesy of these individuals.
The Stanford U.S.–Japan Technology Management Center translated several technical papers from Japanese to support my research. I thank Richard Dasher, Tom Cunningham, and Gary Brown for making this valuable service available to me. Tadashi Nakatani graciously translated additional materials from Japanese for me.
This research was funded by a graduate fellowship from the Fannie and John Hertz Foundation, by DARPA grant DABT63–91–K–0001, and by an equipment grant from IBM.
Graduate school involves more than writing a thesis, for it is also a time of intellectual curiosity.
Besides discussing a wealth of research-related matters with my ofﬁcemates, Jonathan Stone and Stuart Cheshire, I shared discussions ranging from the efﬁcacy of three-phase transaction commitment to the viability of airline deregulation in Europe. I have learned so much from interacting with these two individuals, and I only hope that they found our interactions equally rewarding.
For those times in the past year when I was frustrated, depressed, disillusioned, lonely, or upset, Risa, Brooke, Karen, and Derek always listened to my problems with a sympathetic ear. Your moral vii support allowed me to keep things in perspective. You are a wonderful group of people, and I wish each of you the very best.
Finally, my debt to my parents, Ram and Sushma, is one that I can never describe fully, let alone begin to repay. Your faith in me has always exceeded my own. I continually strive to match your own dedication, integrity, and strength. Thank you for not ever asking me what a Ph.D student does all day.
My biggest regret is that my younger sister, Nidhi, could not live to see the completion of this thesis. At the time of her death, I had not even graduated from high school, and a Ph.D was the last thing on my mind. However, I can imagine no other person who would have relished its completion more than I do. It is therefore in her memory that I dedicate this volume.
STANFORD, CALIFORNIA30 AUGUST 1996
Introduction A Distributed Interactive Simulation application, as illustrated in Figure 1.1, provides a group of users with the illusion of a single, coherent virtual world, even though the computations run on heterogeneous systems that may be dispersed over a physically large geographic area (e.g. around the real world). The virtual world consists of a set of entities, objects that participate in some way in the simulation. Simulation entities may include, for example, human-controlled and computercontrolled vehicles; a terrain (and associated features such as rocks, trees, and buildings), and even logical objects such as the current weather state or an object group. In this interactive environment, each host presents its local user with a realistic viewport onto the virtual world. For example, the rendered scene depicts all of the virtual world entities that would normally be visible to that user.
As a result, the user is unaware of which users are controlling the various entities, which computers are performing detailed computational modeling of the various entities, and where those humans and computers are physically located. Besides supporting geographic separation of the users, the distributed nature of these applications supports fault-tolerant simulation environments and allows the creation of large systems at relatively low cost compared to large, centralized architectures.
Faster processors, more powerful graphics hardware, and higher-capacity networks are supporting the development of distributed simulation applications containing more simulation entities and more detailed models of entity appearance and behavior. Consequently, these networked virtual environments are seeing increased use for multiplayer video games, military and industrial training, and collaborative engineering (e.g. collaborative design and distributed simulation of complex engineering models). These applications demand that each user sees a consistent virtual world view, that users are able to interact closely with one another and with other entities in the virtual world, and maximum realism is provided by hiding the distributed nature of the application from users.
Figure 1.1: Distributed Interactive Simulation Application Presents a User with a Coherent Virtual World To allow a local user to move about the virtual world and interact with remote participants, the host must accurately display the position, orientation, and structure of all virtual world entities visible to that user.
For each entity, each host maintains an entity model—some state information along with a function that takes the state information as input and can generate the entity’s current position, orientation, and structure on each frame. We designate one host’s model as the “source” (also known as the “local” or “true”) model representing the most accurate current state of the entity.
Because the state of an entity model is updated in response to user input, the source model typically resides at the host whose local user is directly controlling the entity 1 to minimize the delay between
Figure 1.2: Simulation Nodes Exchange Information About Locally Modeled Entities user actions and source model updates.