Geometric and Graphics Support

A critical subsystem in all synthetic environment systems is the geometric engine, or the software module responsible for creating a realistic view of the simulated world, and for allowing the user to interact with it. In a typical scenario, a system requires the display of several objects, that move and must behave realistically. A user wanders in the environment, constantly changing his or her point of view. Other users (or actors) may be sharing the same environment, and a suitable representation of them could be required. The users interact with objects in the environment, for example touching their surface to pick and query an object, grabbing and moving them, or simply colliding with a wall of a room. Simulation of even the simplest form of dynamic and interaction requires collision detection and contact analysis. Fast display of complex environments requires efficient visibility computation. Querying and interacting with objects requires rapid point location and local shape control. In short, the geometric engine of a general-purpose synthetic environment system should provide efficient data structures and algorithms for:

• Shape representation
• Dynamic object insertion and deletion
• Object animation (motion, non-rigid transformation)
• Object location and closest point queries
• Collision detection and contact analysis
• Visibility ordering and culling
• View-volume clipping
• Multi-resolution representation
• Real-time high-quality rendering
• Other operations required by specific applications (e.g., set operation and interactive shape control for collaborative design)

We are exploring the use of data structures suitable to support the operations listed above in a complex, constantly changing environment. Several types of data structures that partially satisfy these needs have been proposed in the past. However, they have mainly been used in Computer Aided Design (CAD) systems or other special-purpose applications, and not as an infrastructure for a complex, dynamic and general-purpose environment. Often, CAD systems use boundary representations (Breps) to describe the geometry of the object being modeled. Breps are well suited to the implementation of the most common modeling operations. However, when this representation is to be used in a general-purpose synthetic environment, it has to be supplemented with additional structures such as octrees or bounding volumes hierarchies to achieve the required efficiency.