Interactive Explorer Project Description

Introduction - Overview of a Typical Connection - Classes Used - IXServer Details - IXClient Details - Algorithms of Interest - Remaining Tasks/Ideas - Conclusion
Introduction
The following excerpt from the demonstration page describes the desired experience:

You are represented by a point which has freedom of movement in a three-dimensional environment. The world as viewed from your current position and orientation is displayed along with buttons which can be used to navigate the environment. This view is updated as you - or other people and objects - move around in the virtual environment. As you explore, you will find two types of objects: those that are fixed in place and those that you can push by bumping into them. Try interacting with the environment around you!

The goal of this project is to create a three dimensional environment which can be Interactively Explored by multiple people simultaneously. Multiple users should be able to explore the environment with full freedom of movement and discuss what they see with each other. This conversation is made possible through the use of IRC-type messaging capabilities also provided by the applet. A client should be able to join at any time without having to know anyone's Internet address, worry about who else is present at the time, or obtain permission to join an active session.

A few of the key features:

• Clients have unrestricted movement (six degrees of freedom) in a true three-dimensional environment composed of points, lines, and solid polygons
• Multiple clients (their number being limited only by network traffic) can explore the same environment with no prior knowledge of each other's name, address, or other details
• Clients can interact with the environment by pushing certain objects around - with collision detection applied to themselves and the objects with which they interact
• Movement and changes made by one client are seen by all other clients in real-time - Clients can see each other (identified by name) according to their current position in the environment
• Clients can communicate with each other through the use of an IRC-type interface which maintains a log of the most recent communications

Introduction - Overview of a Typical Connection - Classes Used - IXServer Details - IXClient Details - Algorithms of Interest - Remaining Tasks/Ideas - Conclusion
Overview of a Typical Connection
Before anything else can happen, a machine needs to be set-up to run a web server and the Interactive Explorer server, IXClient. Once this machine is in place and has been provided with the necessary files (web pages and Java classes for IXServer and IXClient), a client can initiate a session as follows:

1. The client starts her browser and accesses the URL of the Interactive Explorer page.
2. Her browser requests the page from the server which sends the page and code for the client applet, IXClient.
3. The user's browser loads the applet and begins executing it.
4. As part of its initialization, the applet attempts to connect to the Interactive Explorer server on the server machine.
   • If the connection is unsuccessful, the applet enters single-user mode and allows the user to explore a default environment. The rest of this overview does not apply to this type of connection.
   • If the connection is successful, execution continues...
5. The server, on receiving a connection, spawns two threads for handling the new connection (a reader and a worker/writer).
6. The client, on making the connection, spawns a thread for receiving update messages from the server and requests an update.
7. The server, on receiving an update request, sends a complete description of the current state of the environment to all currently connected clients.
8. The client, on receiving the update, renders the view as seen from the user's current position and orientation.

The client is now connected and active. Any of the following can occur depending on the actions of the currently connected clients:

• The user changes her orientation
  1. No messages are sent since the view as seen by other clients has not changed.
  2. The user's view is re-rendered to reflect this change.
• The user tries to change her position (or changes her name)
  1. A request for permission to move is sent to the server.
  2. The server evaluates whether or not the move should be permitted:
     • If not, the server ignores the request. Because the applet never gets an update message, it does nothing - it is as though the move was never made.
     • If so, the move is made and all clients get an update message containing the current state of the environment - all views are re-rendered.
• Some other client changes his orientation
  1. The user is not made aware of this change (since it has no effect on her view of the environment).
• Some other client changes his position (or name)
  1. The user's applet receives an update message and re-renders its view.
• The user sends a text message
  1. The user's applet sends a text message to the server.
  2. The server reflects this message to all clients.
  3. The user's applet appends this message to its list of previous messages.
• Some other client sends a text message
  1. The user's applet receives an text message appends it to its list of previous messages.
• Nothing happens for a predetermined amount of time
  1. The server sends an update message to all connected clients (to detect broken connections).

When the client has finished using the applet, she closes her browser/loads another page/disconnects from the network, and the following events occur:

1. The user's applet terminates without sending any additional messages.
2. The server, on sending its next message, determines that the connection has been terminated.
3. The server frees all resources dedicated to maintaining information about the client.
4. The next update message from the server contains no reference to the previously existing client - it vanishes.

Introduction - Overview of a Typical Connection - Classes Used - IXServer Details - IXClient Details - Algorithms of Interest - Remaining Tasks/Ideas - Conclusion
Classes Used

Class Name	Purpose	Used by IXServer	Used by IXClient
ButtonConsole	Draws a bitmap of buttons and handles mouse input. Used for "Movement" and "Rotation" buttons.	No	Yes
CollisionDetection	Performs collision detection for a point moving through a set of triangles or a triangle moving through a set of points.	Yes	Yes
Environment	Contains a description of the current state of all objects (including clients) in an environment.	Yes	Yes
IndexedLine	Representation of a line with end-points stored as indices into a separate array of points.	Yes	Yes
IndexedObject	Representation of an object consisting of points, lines, and triangles with objects stored as indices into separate arrays of their respective type.	Yes	Yes
IndexedTriangle	Representation of a triangle with end-points stored as indices into a separate array of points.	Yes	Yes
IXClient	Main class for the client applet. Handles the user interface and the major functionality of the applet.	No	Yes
IXClientConnection	Separate Thread which handles client-side communication with the server.	No	Yes
IXClientInformation	Contains information about a client connection.	Yes	No
IXClientRenderer	Separate Thread which handles all aspects of rendering the client's current view of the environment (including coordinate transformations, clipping, and drawing calls).	No	Yes
IXClientScreen	Handles the z-buffered drawing of points, lines and polygons on a pixel-by-pixel basis.	No	Yes
IXServer	Main class for the server application. Handles establishing new connections and provides shared methods for safe environment modification.	Yes	No
IXServerConnection	Separate Thread which handles sending data to a client when necessary.	Yes	No
IXServerConnectionReader	Separate Thread which handles reading data from a client and responding to it.	Yes	No
IXServerTimer	Separate Thread which ensures that an event will occur every n seconds.	Yes	No
PerspectiveTransform	Matrix for computing the perspective transformation of a point, TPERSP.	No	Yes
Semaphore	Implementation of a binary semaphore for ensuring mutual exclusion and blocking.	No	Yes
ThreePoint	Representation of a point in three-dimensional space (with double variables) as well as point operations.	Yes	Yes
ThreeVector	Representation of a vector in three-dimensional space (with double variables) as well as vector operations.	Yes	Yes
TwoPoint	Representation of a point in screen space (with int variables).	No	Yes
ViewTransform	Matrix for computing the viewing transformation of a point, TVIEW.	No	Yes

Introduction - Overview of a Typical Connection - Classes Used - IXServer Details - IXClient Details - Algorithms of Interest - Remaining Tasks/Ideas - Conclusion
IXServer Details
Since IXServer is expected to be run for extended periods of time, care has been taken to make it as stable and reliable as possible. IXServer should be able to handle multiple clients connecting, disconnecting, and doing whatever they want in the environment, as well as lost connections and data. Because the security limitations of Java prevent clients from sending messages directly to each other, any information that is intended to reach all clients must be routed through the server. These requirements and others led to certain implementation decisions:

• Clients do not directly make changes - Clients have the potential to move in conflicting ways: one client could push an object while another client simultaneously moved to a place which happened to be inside the new location of the object. Independently, each of these moves is valid, but together they represent a problem. (Note that "simultaneous" can actually be a time span on the order of seconds due to the delay of message transmission on the network.) To avoid problems such as this, all movement is routed through the server in the form of a request for permission - with the realization that the request may not be granted. Because the client knows its request may be denied, no changes to internal data are made - and so there is nothing to undo in the event of a denial (because of this, the server denies requests by failing to respond to them). This avoids the problem of simultaneous actions and ensures that all movements will be evaluated based on the true state of the environment (rather than the older, out-of-date view of it that most clients are likely to have). In short, the problem of maintaining a single environment across all clients is solved by maintaining only one environment - a copy of which is sent to all clients as necessary.
• Clients do not send "termination" messages - Since there is no guarantee that a client's browser will properly execute any shut-down code (like the stop method), the server must not depend on getting such a message (the connection may be lost or the browser may lock for example). To accomplish this, the server monitors the state of its connections whenever it sends data to the clients. If any connection becomes broken, the server removes that client from its list of connected clients and terminates the two threads dedicated to handling communication with that client - thus freeing all resources dedicated to that client. To avoid the possibility of a broken connection persisting for a prolonged period of time, the server periodically sends out an update message to all clients it believes are connected - if any connections are invalid, it removes those clients.
• The server sends the entire environment in update messages - Because the underlying network transport protocol probably uses a fairly large packet size (~500-1500 bytes), sending a position update (three doubles) in a platform independent manner (see below for more details) would take three packets and waste a great deal of bandwidth. Since a reasonable encoding of the entire environment can fit into one packet, sending the entire environment every time incurs no extra network cost. Additionally, future implementations of the server could cache environment changes (sending ten changes in one message for example), therefore sending fewer update messages - requiring no modifications to the client. Finally, this avoids coherency problems that could result if a client missed an update message (packets may be dropped by the network). If messages were concerned only with the most recent change that occurred, such a client may never realize that its view of the environment was incorrect - the current implementation ensures that similar problems are corrected when the next update gets received.
• Update messages are Strings - Though Java provides a stream which can transmit primitive data types in a platform independent manner, sending even the simplest data types (like a ThreePoint - a three-dimensional point) would require three separate packets. By converting data types into Strings before sending them, this overhead can be reduced dramatically and the entire Environment can be made into one String. This technique takes advantage of the toString and valueOf methods available for all primitive data types as well as the StringTokenizer class (for Vectors). Strings can be sent efficiently in a platform-independent manner as UTF-8 strings (despite Java's use of Unicode, the characters used (\u0000-\u007f) require only one byte when converted to UTF-8) and can be easily read by a human during debugging. NOTE: If this limits future performance, a more efficient encoding can easily be substituted.

Introduction - Overview of a Typical Connection - Classes Used - IXServer Details - IXClient Details - Algorithms of Interest - Remaining Tasks/Ideas - Conclusion
IXClient Details
IXClient is intended to be run on the user's machine in the (Java-enabled) web browser of their choice. It should not be too demanding of the underlying hardware, and should be easy to use and understand. The obvious goal is that a wide variety of people will be able to quickly acclimate themselves with the applet and begin using it (instead of trying to figure out how to use it). The attempt to accommodate these and other criteria led to a number of implementation decisions:

• The applet uses custom graphics routines - Because the applet needs to draw everything into a z-buffered display, the routines of the Abstract Windowing Toolkit (java.awt.*) could not be used. Instead, custom routines had to be written which could draw points, lines, and filled triangles in a z-buffered manner (i.e. a request to draw a pixel would be granted only if the z-buffered value for that pixel was greater than the z value of the pixel to be drawn). Currently, the line and triangle routines use floating-point math (for its ease of initial implementation). These routines have been optimized for speed (the triangle drawing routine draws only horizontal lines, so the line routine has extremely fast code for drawing horizontal lines). However, a pure-integer technique throughout (like a three dimensional version of Bresenham's line algorithm) would almost certainly be faster (this is on the to-do list).
• Graphics output is double-buffered - Flicker and partially drawn images are confusing and distracting, so the applet double-buffers its graphics output. Double-buffering works by sending all graphics output to an off-screen image where it can't be seen by the viewer. When the off-screen image has been completed, it is swapped with the displayed image - and drawing begins on the new off-screen image. By doing this repeatedly, the user sees only completed images - so flicker and partially drawn images are not a concern. While double-buffering increases the resources needed by the applet (it requires another Image and the resources associated with it), the benefits are generally considered to outweigh the costs.
• The applet uses a separate Thread for rendering - Because the rendering process is somewhat time-consuming and the user may want to make additional input while the applet is rendering, a separate Thread is created for this purpose. This allows the user interface to be responsive even while the renderer is computing the next image. The use of multiple Threads led to related concurrency issues (the data may change while the renderer is using it) which were resolved through the use of a semaphore and by maintaining two versions of the data. An additional benefit of this approach is that the applet will not waste time rendering an image if there has already been another change to the data (i.e. if the user requests three position changes in quick succession, the renderer will ignore the first two and begin rendering the view corresponding to the current position).
• Triangles are the only polygons that may be defined - Because four-pointed polygons can occupy three dimensions and are not necessarily convex, determining if a point is part of such a polygon is more difficult than with three-pointed polygons which must be convex and planar. Additionally, clipping a general polygon against the viewing frustum is computationally intensive - a triangle can be successively clipped against the six planes more easily. Since the results of each clipping operation will be either a triangle or a four-pointed planar polygon (which can then be divided into two triangles), this implementation allows the applet to keep everything in the realm of triangles. Because of this, it is up to the environment's designer to decompose any polygons into their component triangles before they can be used.
• Collision detection works with points and triangles only - Because generalized collision detection is computationally intensive, the applet looks only at points and their interactions with triangles. Determining if a point will pass through a triangle is not extremely difficult, so this method can be used for both clients and the objects they push. For a certain subset of shapes, this technique is sufficient to prevent objects from penetrating each other. More general shapes may penetrate each other to some degree, but this will eventually be stopped when one of the vertices becomes involved. Again, this represents a tradeoff of generality for speed - but an environment's designer can choose objects to minimize (or eliminate) this problem.

Introduction - Overview of a Typical Connection - Classes Used - IXServer Details - IXClient Details - Algorithms of Interest - Remaining Tasks/Ideas - Conclusion
Algorithms of Interest

• The rendering pipeline - IXClient uses a variation of the general three dimensional rendering pipeline which proceeds as follows:
  1. Get new environment definition (in world space) as a result of some change to the environment
  2. Transform all points to view space and screen space using the standard 4×4 matrix multiplication technique
  3. Clip all lines against the viewing frustum (the algorithm clips the front and back planes in view space and the others in screen space)
  4. Iteratively clip all triangles against each plane of the viewing frustum
  5. Remove all points outside the viewing frustum
  6. Draw all points, lines, and triangles into an off-screen image
  7. Draw all text (such as that used for the names of other clients) - text is not z-buffered
  8. Swap the on- and off-screen images to display the results
  9. Reset the z-buffer and off-screen image to prepare for the next image
• Clipping a line against a plane - The end-points of the line are checked to see if they lie on the same side of the plane (the trivial accept/reject case). If not, the point of intersection of the line and the plane is found. The resulting clipped line is composed of this intersection point and the end-point lying on the inside of the plane.
• Clipping a triangle against a plane - This is done by clipping each of the three edges against the plane (after checking for the trivial accept/reject case of all three points lying on the same side of the plane). The result of the clipping operations will be either three or four unique points. If only three points result, the triangle defined by these points is added to the list of triangles. Otherwise, the lowest point (call it L) is found and the other three points are sorted according to the angle they make with the vertical line through L. Labeling these other points A, B, and C, two triangles can be defined: L-A-B and L-B-C. These two triangles form the necessary four-pointed polygon and are added to the list of triangles.
• Drawing a filled triangle - The triangle drawing routine begins by sorting the three vertices according to y-coordinate. Beginning at the top-most point, it traces its way down the two edges leading out from that point (stopping only on pixel coordinates). As it marches down the pixels of the edge lines, it draws a horizontal line between the two edges. At some point, one of the edges will end and the third vertex will be reached. At this point, the third edge replaces the completed edge, and progress continues until the bottom vertex is reached. As can be seen, this technique will result in a large number of horizontal lines being drawn - so this is handled by a special case in the line drawing routine and is done very quickly.
• Collision detection - The collision detection routine used by IXClient seems to check two cases: if a moving point will hit a triangle and if a moving triangle will hit a point. These are actually handled by the same method - the second case can be reduced to the first by moving the point in the opposite direction of motion and holding the triangle stationary. First, the routine checks to see if the start and end point lie on the same side of the plane defined by the triangle by using the dot product (this represents the trivial reject case). If not, the intersection of the line between the two points and the plane of the triangle is found. If this intersection lies inside the triangle, then the point would pass through the triangle - if not, no collision would occur. If a collision does occur, the triangle is asked whether or not it is part of an object (and therefore is pushable). If not, the movement is not permitted because the triangle is a fixed part of the environment. If the object is pushable, then the object is "test-pushed" - the applet acts as though it were pushed and determines if any other collisions occurred. If so, the attempt to push the object fails, otherwise, the object is moved to its new location.

Introduction - Overview of a Typical Connection - Classes Used - IXServer Details - IXClient Details - Algorithms of Interest - Remaining Tasks/Ideas - Conclusion
Remaining Tasks/Ideas

• Ensure that the applet works on different platforms - Though the applet is written in Java, it seems there are frequently problems across different platforms. While I test the applet using the two most popular browsers for the PC, other architectures occasionally have a problem with the applet. This is usually due to a timing problem, an implementation difference, or undefined behavior, but can be quickly fixed once the problem and its cause have been discovered.
• Use Bresenham's line algorithm - The three dimensional line (and triangle) drawing routines would benefit by using the faster integer math of a modified Bresenham's algorithm as opposed to the current floating-point method (this is discussed above).
• Allow multi-pointed polygons to be defined - These could be restricted to only planar, convex shapes, or could be allowed to be more general. To minimize later computation, these could be sent through a pre-computational step which would separate them into their respective triangles. In this manner, later performance would not suffer from the added functionality.
• Enable the interpretation of VRML files - By adding this capability, development of environments would be made much easier due to the use of existing tools for VRML development. Additionally, pre-existing VRML worlds could be used by Interactive Explorer with no effort being necessary to convert them to the current data format.
• Allow a self-modifying environment - By allowing events to occur without user intervention, behavior could be simulated by the environment. Most simply, periodic behavior could be modeled (such as a rotating object or opening/closing door) and users could observe and interact with this motion. This would allow simulation and exploration of many more classes of objects and could provide insight into exactly how different motions are related.
• Implement new features found in the JDK 1.1 - The next version of Java has a number of new features, many of which should translate directly into performance gains for the Interactive Explorer application. Of course, these features will require that clients use a browser that has been updated to JDK 1.1 (due in early '97). A few areas which could benefit:
  • The JAR specification should allow much faster download of the applet (since all .class and .gif files can be sent as one compressed file (extracted by the client))
  • Improvements in the AWT should translate into improved graphics performance
  • Bug-fixes in the socket implementation should yield fewer networking problems
  • Object serialization should make sending Environments more efficient
  • Remote Method Invocation may prove useful for streamlining the client/server interaction.

Introduction - Overview of a Typical Connection - Classes Used - IXServer Details - IXClient Details - Algorithms of Interest - Remaining Tasks/Ideas - Conclusion
Conclusion
Writing this applet has been an excellent learning experience. As can be seen by some of the issues covered above, the Interactive Explorer project makes use of a number of current technologies (such as client/server computing, the Java language, and 3D environments). While one can learn a considerable amount about something by reading about it, there's nothing like designing an implementation to ensure you really do understand. Overall, I am pleased with the way the project has gone. The current state of the application is far from perfect, but it accomplishes almost everything I initially envisioned. Performance, while not stellar, is very reasonable considering what is being attempted and how it is being accomplished. However, there are still a number of things that could be done, and so I look forward to continuing my work on this project.


The applet is available.
The source code is not currently available since this is a work in progress and therefore in a constant state of flux - there is a considerable amount of extra code in place (for profiling purposes among others) which makes understanding the code much more difficult.