[Previous Chapter][Table of Contents][Next Chapter]

Chapter 4 - Spatial Culling Prototype

4.1 Overview

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 system.

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.

4.1.1 Lessons

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 multicasting approach.

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 both.

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."

4.1.2 Scope

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.

4.2 Design

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 space.

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 users.

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.

4.3 Implementation

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 virtual environment.

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 user interface.

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)

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 development began.

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 enforced.

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 environment.

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)

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 string "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 more detail.

(Figure 4.3)

Figure 4.3: Communication Model Diagram

4.4 Evaluation

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.

4.4.1 Approach

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.

4.4.2 Results

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 broadcast version.

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.