Chapter 4 - Spatial Culling Prototype
To explore how the communication control techniques discussed in the
previous chapter could be best integrated into the GreenSpace system, a
prototype communication control system was developed. Ideally, this would have
been built directly on top of the actual GreenSpace infrastructure; unfortunately,
the GreenSpace system, being developed in parallel to this thesis research, was
not yet stable enough to be used as a platform, so a simple prototype of the
GreenSpace system was required as a test-bed for the communication control
Since the GreenSpace demonstration system used in November was
optimized for the demonstration application and peripherals, it was not flexible
enough to be used for this research. Instead, a simple prototype of the upcoming
GreenSpace system was constructed and the communication control system was
developed on top of it.
In the previous Multi-User Systems chapter we observed the only scalable
network solutions appeared to be multicast communication or multiple
communicating servers. Since multiple servers increase latency as messages are
passed from server to server, multicast appears the most promising. Several of
the existing systems described were already in the process of converting to a
We also observed the importance of a platform and display independence.
Open Inventor was presented as evidence of a toolkit that can help to provide
Nearly all of the systems that addressed limiting the communication
between entities (including MUDs, CyberTerm, DOOM, LucasFilm's Habitat,
NPSNET, DIVE, MASSIVE, and RING) employed a spatial model for
communication reduction. Entities in the simulation which were far away or not
visible, were disregarded. This general approach will be called "spatial culling."
The communication control prototype and underlying prototype of the
GreenSpace infrastructure are not intended to provide a useful multi-user virtual
environment application. This is intended to be an exploratory [Tren91], or throw-
away, prototype rather than an evolutionary one. The system is being developed
in order to explore the integration of some key ideas discovered in the previous
chapter. If these ideas prove to be fruitful, then they should be designed directly
into the developing GreenSpace infrastructure.
The prototype was intended to mimic the upcoming GreenSpace system
wherever feasible and to provide enough functionality to experiment with spatial
culling of interpersonal communication. The prototype should logically be thought
of as two separate components: application and communication control. The
application relates to parts of the prototype which emulate the actual GreenSpace
infrastructure (such as I/O), as well as the application models and interface. The
communication control component of the prototype is the focus of this research.
4.2.1 Application Prototype
In order to effectively explore communication control, the application
component needed to provide enough functionality to enable many users to
simutaneously inhabit the same virtual environments, to navigate through those
environments, and to communicate with other users in them. More specifically, the
application component was to include the networking support, object models, and
navigational interface (including graphical rendering and user input).
In order to generally show support for collaborative design, virtual space
teleconferencing, situational training, and entertainment applications, the user
representations were designed to be humanoid, while the environments were to
be architectural. Accordingly, the navigational interface was designed to facilitate
`walking' through the environment, much as a user would walk through a physical
4.2.2 Communication Control
Communication can take place within many media (visual, auditory, haptic,
etc). As it was important to explore how different media can be controlled
differently, at least two communication media had to be supported. This prototype
focused on visual and auditory communication modalities.
In general terms, we will be taking advantage of people's natural
expectations of physical spaces in the design of the virtual space communication
control system. As in NPSNET, we break the world into small regions that the
inhabitants move between. We will spatially cull away data from virtually distant
users by associating multicast channels with each region and employing the same
spatial culling technique used by NPSNET.
When multiple users share an environmental locality, as do people
standing in the same physical room, they should be able to see and hear each
other, just as they would be able to in a MUD room.
When the area that the users are sharing is very large, then we will not
automatically expect to be able to hear and see each other. In this case, the
communication control system should appropriately cull out the data from distant
For this prototype we will create a hybrid of the spatial partioning approach
used in MUDs, LucasFilm's Habitat, and NPSNET with a simplified version of the
COMIC spatial model used by DIVE and MASSIVE. Rather than consider all of
the features of the spatial model, we will focus on an audio aura. In the COMIC
model this could be accomplished by making the nimbus and focus equal in size
and shape to the aura, for the audio medium. Adapters will also be disregarded in
this prototype, though they are obviously an important extension. This simplified
model will make it easier to see the effect of this spatial model.
Ideally, the application should spatially partition the environment into rooms
and areas for communication, rather than expecting this from the communication
control system. The communication control system cannot know enough about
the specific application or the environment model to sensibly extract logical
communication areas from the model. As there is no real application associated
with this prototype, the communication control system can simply slice the world
into an arbitrary number of symmetrical communication regions.
Once the design was chosen, many implementation decisions were left to
be made. As the prototype was to be exploratory, rather than evolutionary, many
features were hard-coded into the system that would otherwise have been left
more general. This helped to speed the implementation process. Before the
communication control system could be constructed, the application prototype
had to be built.
4.3.1 Application Prototype
The application prototype was constructed in a series of stages, each one
building on the next. The first step was to create a user interface to a single-user
In order to make the prototype as accessible to as many users as possible,
the specialized high-end hardware required to achieve an immersive system was
avoided. A 3D toolkit, Open Inventor, was chosen to assist in the construction of
this interface. The user interface began as a simple series of modifications to the
Open Inventor Walk Viewer [Wern94], which provides for the navigation through a
virtual environment using a mouse. Since Open Inventor is written in C++, the rest
of the prototype was developed in C++ as well.
The Open Inventor file format is roughly a superset of an emerging
standard called the Virtual Reality Modelling Language (VRML) [Pesc94]. The
VRML file format is quickly gaining wide support as a 3D object description format
for use on the World Wide Web (WWW). As there are so many VRML models
available on the WWW and Open Inventor can handle most VRML files with little
modification, VRML models were sought as the environment and participant
models for this prototype.
Initially, models of DOOM levels that had been converted to VRML were
tested, but the models were too complex and had too many textures to achieve
acceptable frame rates on low-end SGIs. Eventually, a simplified version of a
demonstration VRML file from SGI called The Palladium was used [Ferr95]. This
VRML file was hand edited down to a reasonable number of polygons to achieve
fast frame rates on low-end machines. The model chosen for the participants was
extracted from another SGI VRML file called Stonehenge [Ferr95]. This VRML file
was also hand edited to remove a set of polygons representing the user's
shadow, to color the face of the participant grey for viewpoint identification, and to
place hooks for coloring and moving the body of the participant from the
application. Figure 4.1 shows the resulting models as seen from the walk viewer
In order to allow the use of machines which did not include audio support,
the decision was made to simulate the audio streams with text messages. Within
the prototype itself these messages would still be treated as audio, but would be
displayed as text. A set of familiar song lyrics were compiled to be used as
simulated communication streams, including the words to songs such as "Its a
Small World", "Gilligan's Island", and "The Brady Bunch." Simply by hitting a
single key on the keyboard, users were able to toggle on or off a preselected
simulated audio stream.
Figure 4.1: Environment and Participant Model
Once the single user application was functional and the position of the user
was extractable as the user moved through the environment, the next step of
Jens Dauner developed a set of C++ classes to provide multicast network
support, in parallel with the development of the application prototype. As soon as
the multicast network package provided the ability to connect to a single multicast
channel, the prototype was modified to become a two-user virtual environment
system in which both users were connected to the same multicast channel to
share their positional data.
The final step for the application prototype was the generalization to a large
number of users. To ease implementation, an arbitrary limit of 100 users was
4.3.2 Communication Control
Until this phase of the prototype development, the prototype had been
operating very similarily to a broadcast network mode. Each of the users in the
environment was sending positional or audio data to all other users in the
environment, each of which was rendering what it received.
The first step was to break the world into an arbitrary number of
symmetrical cells. To ease implementation, these cells were chosen to be square
and to line up exactly with the edges of the world. The world was arbitrarily divided
into a 10 by 10 grid of communication cells. Each cell was assigned a multicast
channel of the form 225.13.X.Z, where X and Z corresponded to the location of
that cell within the grid. This allowed each client to compute, rather than look-up,
the multicast address associated with the cell the user was currently in based on
the user's current position. Once the clients were able to listen to and send to the
multicast channel associated with their current position, this phase of the
prototype development was complete.
Next we expanded the range of the user's perception to include the
multicast channels associated with all of the cells adjacent to the cell they were
currently in. As the user moved through the environment, the client was
responsible for observing when cell boundaries were crossed, disconnecting from
the channels no longer within range, and connecting to the newly in range
channels. Figure 4.2 shows the boundaries of the current communication cell, as
well as outside boundaries of the adjacent eight cells, from within the
Since we received no positional data from users outside of our range of
perception, as we were simply not listening to the same multicast channel they
were broadcasting their position to, we had to do something with the
representation of those users' bodies which were outside of our range. Therefore,
a group update channel was created that each user sent to when they moved
from one cell to another and periodically sent if they remained in the same cell for
a long time. Knowing what cell a user was in allowed us to place a representation
of that user in approximately their current position. This should allow us to see the
approximate position of far away users, then the correct position of that user as
we approach them.
Figure 4.2: Overhead View showing Communication Boxes
Finally, the audio aura was put into place. When a user was within range of
your perception (either in the same cell as you or one of the eight adjacent cells),
the distance between you and the other user was computed. If the other user was
further than the width of a communication cell, then their verbal communication
was ignored. This simulates an audio aura which is smaller than the visual aura.
When the user is between half the width of a cell and a full width of a cell away,
audio drop-off is simulated by replacing the actual audio text message with the
UserX is saying something, but is too far away to hear."
In Figure 4.3 the user is shown standing near the upper left hand corner of
the center communication cell. The light grey squares indicate which cells the
user is currently subscribed to, while the dark grey circle shows the user's audio
aura. The user guide in Appendix A describes the operation of the prototype in
Figure 4.3: Communication Model Diagram
In addition the the spatial culling model which this prototype demonstrates,
the prototype included a broadcast mode option which disabled all of the spatial
culling features and caused the client to simply send and listen to a single
multicast channel. This allowed users to try both the broadcast and spatial culling
modes for comparison.
Conducting controlled experiments in cooperative systems is nearly
impossible [Shne92], compared to single-user systems, due to the multiplicity of
users. Nonetheless, informal experiments were conducted with members of the
GreenSpace group and later with a much larger, less controlled group.
Most of the early tests were conducted by getting one or two volunteers to
enter the environment at the same time as the author. Feedback would be
collected by staying in touch with the users over the phone or connected via an
MBONE audio session.
After the prototype had stabilized, an online set of instructions and
evaluation form (shown in the appendices) were constructed and general request
for volunteers was made to the members of the HITLab and Department of
Computer Science and Engineering. Each user was given a unique identification
("userid") so that they could be tracked while using the system.
A total of 26 userids were assigned, corresponding to users most of whom
tried the prototype at least once. Unfortunately, only 6 of those people took the
time to fill out the online form. The rest of the feedback was accumulated through
informal discussions with people about their experiences with the prototype.
With small numbers of users, the benefit of the spatial culling mode over
the broadcast style mode was not apparent. However, as the number of users in
the system grew beyond 5 or 10, the broadcast environment quickly became
overloaded and confusing in comparison to the spatial culling version.
Without a real application being supported by the system, people often
simply flocked together through what Pavel Curtis calls "social gravity" [Curt92].
All of the users in one place negated the effects of spatial culling.
When users did become overwhelmed by the amount of simulated speech
flooding their screen in the spatial culling mode, they did tend to move away from
the noise. This does help support the claim that this is an intuitive approach to
filter interpersonal communication.
A few of the users found the placement of far away users in approximate
positions to be confusing, either because they were not far enough away
(indicating that the communication cells were two small for the application) or
because the representation of the other users was otherwise unchanged.
Perhaps changing their shape or color when only placed approximately would
solve this problem.
Some users noticed that it was easier to locate other chatting users in the
spatial culling mode than with the broadcast mode. They would simply navigate
around the environment until they began to hear the user, then make a closer
scan of the immediate area to find them. This would not be possible in the
Many users were frustrated by the lack of real communication. While this
may have been a short coming of the prototype, this was seen as a good sign that
people were engaged enough with the interface to actually want to try to start up
real conversations within it. This, of course, was beyond the scope of this
exploratory prototype and will be left for the real GreenSpace system to provide.