My Dissertation:
Virtual Reality in Assembly Simulation -
Collision Detection, Simulation Algorithms, and Interaction Techniques

You can download the PDF version (2 MB).
It is optimized for on-screen viewing (color plots, hyperlinks, lores images).

You can also download the Postscript version (6.7 MB).
It is optimized for printing (b/w plots, hires images).
If you have a color printer, you might also want to print the color tables (4.2 MB).

And you can even download a PDF version (2.3 MB) that is identical to the printed book (it still has the hyperlinks, of course).
This might be helpful if you want to cite individual pages.
It is formatted for A5, so it is probably not well suited if you want to print it yourself on A4/letter format.

Summary
See below.

Zusammenfassung
Siehe unten.

Abstract
This thesis presents frameworks, algorithms, and techniques in order to make the application of virtual reality for virtual prototyping feasible. Virtual assembly simulation is focused on in particular.

The contributions are in the following areas: high-level specification of virtual environments, efficient interaction metaphors and frameworks, real-time collision detection and response, physically-based simulation, tracking, and virtual prototyping application development.

A framework for authoring virtual environments is proposed. The main premise for the proposed framework is that it should be easy for non-computer scientists to author virtual environments. Therefore, the concept of actions, events, inputs, and objects is introduced. These entities can be combined to virtual environments by the event-based approach.

Collision detection is one of the enabling technologies for all kinds of physically-based simulation and for virtual prototyping. This book proposes a collision detection pipeline as a framework for collision detection modules. Subsequently, several algorithms for all stages of the collision detection pipeline are developed and evaluated.

Interaction in virtual environments comprises many different aspects: device handling, processing input data, navigation, interaction paradigms, and physically-based object behavior. For all of them, techniques, frameworks, or algorithms are presented in this book, with a particular emphasis on their application to virtual prototyping.

Finally, virtual prototyping is discussed in general, while the virtual assembly simulation application is described in more detail.

All frameworks and algorithms have been implemented in Fraunhofer-IGD's VR system Virtual Design II, now available from VRCom.

Keywords
VR system design, authoring of virtual environments, event-action framework, VR plugins, alternative scene graphs, semantic scene graphs, incremental collision detection, convex collision detection, hierarchical collision detection, collision detection pipeline, immersive interation, tracking correction, tracking filtering, natural grasping, sliding, VR applications in industry, virtual prototyping.

Schlagworte
Design von VR-Systemen, Erstellung von virtuellen Umgebungen, Event-Action Framework, VR Plugins, alternative Szenengraphen, semantische Szenengraphen, inkrementelle Kollisionserkennung, konvexe Kollisionserkennung, hierarchische Kollisionserkennung, Kollisionspipeline, immersive Interaktion, Tracking-Korrektur, Tracking-Filterung, natürliches Greifen, Gleiten, VR-Applikationen in der Industrie, virtuelle Prototypen.

Location
Darmstadt University of Technology.
Submission: May 29, 2000.
Defense: July 10, 2000.

In case of problems
In case of problems, please don't hesitate to contact me.
(For instance, if your host is not registered by the world-wide Domain Name Service (DNS), then you will not be able to ftp ...)

Summary

In 1995, only a few VR systems were commercially available and a few more in the academic domain. None of these was mature at the time, nor had any of them been deployed in the field for everyday work. Some commercial and most academic systems were not so much a self-contained VR system, but rather a set of libraries which application programmers could build upon.

In particular, VR was not ready for use for industry application. Problems persisted in the following areas (among others): electro-magnetic tracking, high-level specification of virtual environments, efficient interaction metaphors and frameworks, and real-time collision detection and response.

This thesis has made contributions to all of these areas. Almost all of the algorithms, applications, and frameworks presented in this thesis have been integrated into the VR system Virtual Design II, which has been developed by the department I am with, and which is now commercially available through the spin-off VRCom.

Framework for authoring virtual environments

Creating virtual environments involves two steps: first, it has to be described, then it must be simulated. The former is known as authoring, while the latter basically means that the description is executed by a VR system.

After a discussion of frameworks for computer-human interaction in related areas (see Section 2.1), such as user-interface management systems, Smalltalk, and programming languages, Section 2.2 proposes a framework for authoring virtual environments. This framework is the basis of our VR system Virtual Design II.

The main premise for the proposed framework is that it should be easy for non-computer scientists (like architects or mechanical engineers) to author virtual environments. This excluded full-fledged programming languages or state machines. Therefore, this thesis introduces the concept of actions events, inputs, and objects (AEIO). These entities can be combined to virtual environments by an event-based approach; the behavior-based approach was deemed inappropriate for application to virtual prototyping.

In each class of entities, a set of entities has been identified such that a significant part of an application can be implemented using these. Each set has been chosen such that its expressive power is maximized while its number of entities is minimized.

Application-specific capabilities can be plugged in at run-time, thereby augmenting the set of actions and inputs. In order to facilitate short turn-around times during development of a plug-in, the following development cycle is supported: the system can delete all actions and/or inputs instantiated from a plug-in; the programmer changes the implementation of the plug-in; the system re-loads that plug-in and re-instantiates all former instances.

Based on the AEIO framework, a scripting language has been designed such that its concepts can be easily grasped by non-programmers. It is orthogonal in the sense that any input can trigger any action. In addition, a many-to-many mapping between inputs and actions can be established; actions can be combined to more complex actions; similarly, inputs can be combined by logical operators. Simple constructs allow the VE author to combine actions or inputs into more complex features. The above mentioned events are basically filters which can detect transitions in inputs (or other events).

Besides the conventional scene graph several alternative object graphs can be maintained. Due to the dynamic nature of a VR scene graph, references in that graph are symbolic, allowing for dynamic changes "behind the scene". Alternative scene graphs are also used to map semantic attributes not present in the conventional scene graph.

Three layers of creating virtual environments can be identified (see Section 2.4.2). The scene graph is on the lower level, while the AEIO framework is on the middle level. On the top level are specialized authoring tools for specific application domains (such as assembly simulation), which are better described as configuration tools. On that level, the author merely specifies "roles" of objects, such as "tool". Using high-level authoring tools, creation of VEs (in that specific application domain) is a matter of minutes.

Collision detection

Collision detection is one of the enabling "technologies" for all kinds of physically-based simulation in VR and other applications. The algorithms presented in this section assume a polygonal object representation.

After a brief discussion of the requirements of collision detection algorithms (see Section 3.1), one of the basic operations of collision detection is analyzed (see Section 3.2). The comparison of several algorithms yielded a simple rule for choosing the optimal algorithm. A collision detection algorithm wishing to maximize performance should implement at least two algorithms for that basic operation and choose either of them on a case-to-case basis according to this rule.

Based on that, I developed an algorithm for checking any type of object, even deforming ones (see Section 3.3). The basic idea is a pipeline of bounding box checks in carefully chosen coordinate frames combined with sorting of bounding boxes. By sorting, one can find quickly a range of polygons within a certain region. The sorted list of polygons can be updated quickly between successive frames, because usually deformation between frames is small. This algorithm can check two spheres with 10,000 polygons each within about 4.5 milliseconds on average and two door locks with 12,000 polygons each within about 15 milliseconds.

Convex objects present themselves for incremental collision detection. Based on the concept of linear separability and simulated annealing, I developed a very fast algorithm which depends linearly on polygon count and rotational velocity with very small hidden constants (see Section 3.4.3). The algorithm gains additional efficiency by hill-climbing on the convex hull and by maintaining the separating plane in two different coordinate frames simultaneously. Collision detection time is of the order of microseconds when objects do not intersect. A comparison with the renowned Lin-Canny algorithm showed that the algorithm presented in this thesis is about 2 times faster. In addition, it seems to be more robust numerically.

Actually, the current implementation of this algorithm is a probabilistic Monte-Carlo algorithm. Although convex objects are not encountered in our scenarios and applications, such algorithms can still be valuable earlier in the collision detection pipeline.

Said Lin-Canny algorithm is based on a closest-feature criterion and makes use of Voronoi regions. I have given a much simpler criterion which does not need Voronoi regions (see Section 3.4.4). So, objects could even deform, provided they stay convex. This algorithm has been implemented on Cosmo/Optimizer. However, it is, as of this writing, not clear yet how it compares to the original one.

Another class are hierarchical algorithms, which are well-suited for non-deformable objects with large polygon counts. In this class, three algorithms have been presented.

The first one is based on clipping and bisecting non-axis-aligned boxes (I have called the associated data structure a box-tree). The algorithm takes advantage of the special geometry of boxes and certain assertions about the arrangement of boxes within a box-tree. In addition, recursion makes use of all the calculations done on the previous level.

The second algorithm uses a data structure very similar to the first one. It efficiently encloses non-aligned boxes by axis-aligned ones (see Section 3.5.6). Again, recursion makes complete use of the calculations on the previous level. This algorithm is much faster than the first one.

A "good" bounding volume hierarchy is crucial for efficient hierarchical collision detection (see Section 3.5.7). Yet, the construction of such a hierarchy should be fast enough so that it can be done at load time. The algorithm for constructing box-trees developed in this thesis is, under certain assumptions, in O(n) time, which has been supported by experiments. By evaluating many different criteria guiding the construction process, the optimal criterion (in the sense of fast collision detection) among them was determined (see Section 3.5.7).

The third algorithm for hierarchical collision detection makes use of discrete oriented polytopes (DOPs) (see Section 3.5.8). For this type of bounding volume, I have found an elegant way to enclose non-axis-aligned DOPs by axis-aligned ones which is in O(k) while the previously proposed method is in O(k2) (k being the number of orientations). The optimal number of orientations (in the sense of fast collision detection) seems to be 24; it has been determined by extensive experiments (see Section 3.5.9). This algorithm can check a pair of door locks, 50,000 polygons each, within 4 milliseconds; two car bodies, each 60,000 polygons, can be checked within 1/2 millisecond.

The collision detection algorithm based on DOP-trees can be generalized to allow different numbers of orientations and even different sets of orientations. As for the box-tree, an efficient algorithm for constructing DOP-trees was developed. It works with any number of orientations.

The box-tree and the DOP-tree algorithms were compared with implementations of two other hierarchical algorithms, namely Rapid and Quick_CD (see Section 3.5.10). Experiments have shown that the DOP-tree algorithm is about as fast as Rapid (in certain cases slower while faster in other), which is, to my knowledge, the fastest hierarchical algorithm to date.

Because incremental algorithms perform so well for convex objects, incremental hierarchical collision detection is discussed. An algorithm based on DOP-trees has been implemented (see Section 3.5.11), and its performance is evaluated in detail.

In the class of flexible objects two algorithms were implemented (see Sections 3.7.1 and 3.7.2). The first one is a hierarchical algorithm, based on the assumption that deformation is small between successive frames. During traversal, the algorithm takes the maximum "drift" of polygons into account. The second one is based on maintaining a sorted list of polygons. Overlapping polygon bounding boxes are found by three sweeps, each along one axis. Unfortunately, both of them perform worse than the bounding box pipeline algorithm in all practical cases (see Section 3.3).

So far, all collision detection algorithms dealt with the polygon level. If a virtual environment consists of many moving objects, then the n2-problem is encountered at the object level, too.

At the object level (see Section 3.8), octrees (Section 3.8.4) and grids (Section 3.8.5) were discussed. Both have been implemented such that only those cells are being visited which actually need to be updated. According to experiments involving various complexities, grids are better suited for highly dynamic environments (see Section 3.8.6), which is in contrast to more static applications, such as ray-tracing. My experiments suggest that for more than 30-40 objects both a grid and the separating planes algorithm should be used for neighbor-finding, because grids are in O(n), while convex hulls are tight bounding volumes. For environments with less than 30 objects, the separating planes algorithm should be used. However, these numbers seem to depend also on the number of polygons, to a some extent.

Finally, I have proposed and implemented a collision detection pipeline (see Section 3.9). This pipeline consists of several stages, each of which can be considered a certain type of filter. The pipeline has been integrated as a module in the VR-System Virtual Design II.

Collision detection lends itself well to parallelization. The collision detection module features concurrency, coarse-grain, and fine-grain parallelization (see Section 3.10). Experiments demonstrate the efficiency of the implementation.

Interaction

Interaction in virtual environments comprises many different aspects: device handling, processing input data, navigation, interaction paradigms, and physically-based object behavior.

Navigation is the most basic interaction in virtual environments. A general framework has been proposed allowing for a broad range of navigation paradigms and input devices (see Section 4.4). Other basic tasks include menus (Section 4.5.1), which are needed to organize the multitude of functions, posture recognition (Section 4.2.1), which is needed to invoke frequently used functions, and utterance recognition (Section 4.2.2). All of these have been integrated in the VR system.

Electro-magnetic tracking poses at least two problems: noise and distortion. In real-world sites, electro-magnetic noise is produced by all kinds of electrical devices, and distortion is caused by ferro-magnetic material in floors, ceiling, speakers, etc. Both noise and distortion can render a VR system useless, especially for virtual assembly simulation, because they would compromise precise positioning. In addition, distortion can lead to artifacts when the environment is rendered on a cave or powerwall.

The problem of noise is addressed by a filtering pipeline, designed to meet the special requirements of VR (see Section 4.3.1). Tracker distortion is greatly reduced by an algorithm developed in Section 4.3.2 . Extensive tests verify its quality and performance. The algorithm has been integrated in several device servers of Virtual Design II.

Another basic interaction task is grasping. In fact, with virtual assembly simulation the user's hand is the most important tool. Traditionally, grasping has been implemented rather unnatural through posture recognition. One of the reasons is that there is (as of yet) no force feedback to the user's real hand. I have developed an algorithm for natural grasping, which presses the virtual hand's fingers to an object and grasps it based on the analysis of the contact (see Section 4.5.3).

When trying to assemble an object, it should not penetrate other parts. Instead it should behave similar to objects in the real world and somehow "slide" along the surface. This kind of behavior has been implemented by a physically-based algorithm presented in Section 4.5.4 . It does not try to be physically correct, but to be as fast as possible while still providing intuitive and plausible behavior. Experiments have shown that my algorithm needs about 300 microseconds per contact point (not counting collision detection time).

Applications

The frameworks, concepts, and algorithms described above have been implemented as several modules within our VR system Virtual Design II. The system has been used for many applications. A lot of them were and are being developed for customers from automotive industries (virtual prototyping). Other application domains include edutainment, cultural heritage, and immersive scientific visualization.

In this thesis, virtual prototyping is being defined as the application of virtual reality instead of physical mock-ups. This definition is stronger than the one prevailing throughout manufacturing industries. Their weaker definition usually means the application of software in general instead of physical mock-ups.

Virtual assembly simulation is one of the applications I have developed on top of our VR system. In Chapter 5 , virtual prototyping is discussed in general, while the virtual assembly simulation application is described in Section 5.2 in more detail. It is now being introduced in the product process of a large automobile manufacturer.

Future directions

I believe that virtual assembly simulation is one of the most challenging applications of virtual reality. Although it has matured in that it can be used in the product process, there are still a lot of things to be improved. ( In the article "What's Real about Virtual Reality?" in the November/December '99 issue of IEEE CG&A, Fred Brooks remarked ironically: "VR that used to almost work now barely works".)

Probably the most important missing feature is force-feedback. Especially in virtual assembly and maintenance simulations, acoustic and visual feedback turned out to be not sufficient to meet the demands of the users. Mechanics "see" with their hands, particularly in narrow and complex environments or when they cannot see their hands and/or tools. Therefore, force feedback would add significantly to the degree of immersion and usability, and it would give a natural and expected cue how to resolve collisions. Furthermore, it would prevent a deviation of the (real) hand and the virtual one.

While this poses non-trivial problems by itself, it also poses additional problems in areas dealt with in this thesis, namely collision detection and interaction techniques. A haptic device for virtual assembly simulation must be integrated into the system so that the user will be able to use it intuitively (like a familiar tool) and safely. Requirements on collision detection are very demanding: under all circumstances, query times must be less than 2~milliseconds for checking at least one object against all the environment.

Another important feature is the simulation of flexible parts. I feel that considerable research is still required in order to be able to interact with hoses, wires, bundles, plastic tanks, etc., in real time.

Collision detection. Since collision detection is an enabling technology not only for virtual assembly simulation, I am positive that this area will be scientifically active for many years to come. My timing experiments with the sliding simulation have shown that collision detection is still by a factor of about 10 more time consuming than the simulation algorithm itself. There are algorithms and object representations allowing faster collision detection queries than the algorithms presented in this thesis. However, they have other drawbacks, such as limited accuracy. So, there is still a need for much faster algorithms checking a pair of objects in close proximity.

In particular, three main directions will get greater attention: collision detection of flexible parts, incremental collision detection for polygon soups, and application-specific algorithms, such as collision detection for force-feedback. Algorithm developers will need to keep in mind cache coherency and memory access patterns. Otherwise, in my experience, an algorithm superior in theory might lose in practice.

To my knowledge, it still remains an open problem if there is a global characterization for the quality (in the sense of fast collision detection) of bounding volume hierarchies which can be computed using only the geometry of the tree itself and without prior construction of the tree. If there is such a global characterization, the next question would be, whether it can be "localized", so that it involves only a bounding volume and its father and child bounding volumes. Such a local characterization would lead to an optimal BV tree construction algorithm.

Interaction. In the area of interaction techniques, natural manipulation of objects still needs considerable research. In particular, the three types of precision grasps of objects by the user's virtual hand in a robust and stable manner is, to my knowledge, unsolved as of this writing. Challenging examples include some common and (seemingly) simple operations: juggling two balls in one hand, turning a screw between index finger and thumb, or wiggling a pencil between index finger and middle finger.

Virtual reality in general always needs some form of tracking. As of yet, the user is almost always tethered by some device, either the head-mounted display, an electro-magnetic sensor, or the data glove. However, virtual reality eventually must become "untethered". While the technology is available already to solve this problem, it is either not commercially available or too expensive.

Future directions for virtual prototyping. The result of a user survey, performed with the application described in Section 5.2, indicates that the use of VR for virtual prototyping will play an important role in the near future in automotive (and probably other manufacturing) industries. In particular, the response of the surveyed users has been very encouraging and optimistic that VR does have the potential to reduce the number of physical mock-ups and improve overall product quality, especially in those steps of the business process chain where humans play an important role.

VR is the best tool (today) to obtain quick answers in an intuitive way in the concept phase of the business process of a product, because in that phase data change often and are available only in a "rough" and preliminary preparation. However, a formal cost/benefit analysis at this time has, to my knowledge, not yet been performed, which might be due to the fact that virtual prototyping has been integrated in the daily productive work environment only for a very limited period and only in very few development processes.

However, VR will not become a wide-spread tool in manufacturing industries before it is seamlessly and completely integrated into the existing CA and IT infrastructure. ( For instance, in order to create a complete VE for immersive assembly simulation 70% of the time is needed to find and prepare the CAD data and only 30% for authoring the VE. ) This is not only a question of conversion and preparation tools: a lot of the data needed for a complete digital mock-up are just not there yet, such as process information, semantical (non-geometric) properties, visual properties of material, etc. This can be solved only in a shift in the design process: design guidelines have to be established with virtual prototyping in mind. All automotive and aerospace companies have realized that and are working on implementing solutions. However, this does not only involve technical aspects of the design process but also a tremendous shift in corporate culture.

Zusammenfassung

Obwohl virtuelle Realität (VR) schon seit etlichen Jahren im akademischen Bereich erforscht wird, so gab es zu Beginn der vorliegenden Arbeit de facto noch keine Anwendungen im produktiven Einsatz. Die Ursache waren Probleme in verschiedenen Bereichen:
  1. Die Beschreibung von virtuellen Umgebungen mit komplexem Objekt-Verhalten und komplexen Interaktionsabläufen war sehr rudimentär und zeitaufwendig.

    In der vorliegenden Dissertation wird ein Konzept entworfen, das es erlaubt, virtuelle Umgebungen mit Hilfe einer einfachen Beschreibungssprache zu spezifizieren, die auch von Nicht-Programmierern leicht erlernt werden kann.

  2. Physikalisch-basierte Simulation von Objektverhalten war zwar teilweise schon gelöst, jedoch bereitete Echtzeit immer noch ein Problem. Der Grund war (und ist), daß das eigentlich Zeitaufwendige nicht die Simulation an sich ist, sondern die Kollisionserkennung.

    In dieser Arbeit werden Algorithmen für eine schnelle Kollisionserkennung vorgestellt.

  3. Bei der Einbaumontagesimulation mit VR werden Bauteile in engen Bauräumen bewegt. Einerseits sollen Bauteile sich nicht gegenseitig durchdringen, andererseits fehlt (auch in der nahen Zukunft) die Möglichkeit, die Hand des Benutzers derart einzuschränken, daß keine Durchdringungen stattfinden.

    Die hier vorgestellte Simulation implementiert ein Objektverhalten, das es dem Benutzer erlaubt, Bauteile auf kollisionsfreien Pfaden zu führen.

  4. Interaktion zwischen der virtuellen Hand und virtuellen Objekten war nicht natürlich. Insbesondere das Greifen von Objekten (eine der häufigsten Arbeitsschritte bei virtueller Einbaumontagesimulation) basierte auf reiner Gestenerkennung.

    Hier wurde ein Algorithmus entwickelt, basierend auf obigen Kollisionserkennungsverfahren, der das natürliche Greifen ohne Gestenerkennung beliebiger Bauteile erlaubt.

  5. Das Tracking von Kopf- und Handpositionen geschieht (auch heute noch) häufig durch elektromagnetisch arbeitende Systeme. Diese haben in realen Arbeitsumfeldern einen signifikanten Fehler (typischerweise n x 10 cm).

    In dieser Arbeit wird ein Algorithmus vorgestellt, der sowohl Positions- als auch Orientierungsfehler korrigieren kann.

  6. Noch vor wenigen Jahren gab es keine Anwendung von VR für virtuelle Einbaumontagesimulation im produktiven Einsatz.

    In Kooperation mit Industriepartnern ist eine Applikation für diesen Bereich entstanden, die es dem Anwender erlaubt, in wenigen Minuten eine VR-Sitzung zusammenzustellen und zu starten.

Alle in dieser Arbeit vorgestellten Algorithmen und Konzepte wurden in dem am Fraunhofer-Institut für Computergraphik entwickelten VR-System Virtual Design II implementiert, welches jetzt von dem Spin-Off VRCom vertrieben wird.

Beschreibung und Simulation von virtuellen Umgebungen

Um eine virtuelle Umgebung zu simulieren, muß sie zuerst beschrieben werden. Die meisten früher verfügbaren VR-Systeme verfolgten den Toolbox-Ansatz, was bedeutete, daß eine VR-Anwendung im wesentlichen programmiert wurde.

Vor der Entwicklung meines Frameworks zur Beschreibung von virtuellen Umgebungen werden verschiedene verwandte Gebiete diskutiert, in denen Computer-Benutzer-Interaktionen behandelt werden. User-Interface-Management-Systeme (normalerweise für klassische 2D-Desktop-Interfaces entwickelt) haben teilweise eine ähnliche Problemstellung wie in VR. Der Fokus liegt dort häufig eher auf der internen Architektur als auf der Beschreibung an sich. Transition networks sind im wesentlichen endliche Automaten; diese wurden in verschiedene Richtungen erweitert, z.B. auf rekursive Netzwerke (die dann deterministischen Stack-Automaten entsprechen). Zur Beschreibung von Dialogen wurden Event-Sprachen vorgeschlagen, die im wesentlichen allgemeine Programmiersprachen, erweitert um gewisse UI-Beschreibungselemente, sind. Schließlich wurden Interaktionsbäume vorgeschlagen, welche einen eher graphischen Ansatz zur Beschreibung der UI-Dialoge verfolgen.

Die oben erwähnten Konzepte zur Beschreibung von User-Interfaces schienen nicht geeignet, virtuelle Umgebungen zu beschreiben. Einige stellen eher eine Architektur vor, andere sind nicht geeignet für Nicht-Programmierer, wieder andere schienen zu stark auf die Führung eines Benutzers durch Dialoge fokussiert zu sein.

Ziel des hier vorgestellten Frameworks war es, eine Beschreibungssprache zu finden, die von Nicht-Programmierern (z.B. Architektur- oder Maschinenbaustudenten) leicht erlernt werden kann. Das Konzept sollte auch von diesen Anwendern sofort erfaßt werden können, d.h., daß Konzepte wie endliche Automaten, oder vollwertige Programmiersprachen, ausschieden.

Die Grundelemente, mit denen man es in virtuellen Welten zu tun hat, sind (graphische) Objekte, Aktionen (normalerweise auf diesen Objekten) und Ereignisse. Hinzu kommen relativ einfache Filter für Ereignisse. Es gibt im wesentlichen zwei Arten, wie diese Grundelemente verknüpft werden können: den Ereignis-basierten und den Verhalten-basierten. Letzterer geht von einer gewissen Autonomie der Objekte aus und eignet sich eher für den Unterhaltungsbereich. Da die Zielanwendungen unseres VR-Systems mehr im industriellen Bereich liegen, habe ich den Ereignis-basierten Ansatz verfolgt.

Basierend auf diesen Grundelementen wurde eine Beschreibungssprache entwickelt, die dem Benutzer erlaubt, ein Skript einer virtuellen Umgebung zu erstellen. Die Prämisse dabei war, daß Aktionen und Ereignisse orthogonal zueinander sein sollen, d.h., daß jedes Ereignis mit jeder Aktion verknüpft werden kann. Weiterhin können viele Ereignisse dieselbe Aktion auslösen, und ein Ereignis kann viele Aktionen auslösen. Ereignisse können durch logische Operationen verknüpft werden. Mehrere Aktionen können zu Sequenzen zusammengestellt werden oder parallel ausgeführt werden.

Die oben erwähnten Filter werden benötigt, um Übergänge von Ereignissen zu erkennen und daraus neue Ereignisse zu generieren, und um Zustände von Ereignissen festzuhalten. Sie können Ereignissen "nachgeschaltet" werden.

Für jede Klasse von Grundelementen wurde eine Menge von "Bausteinen" identifiziert, aus denen sich der größte Teil aller VR-Anwendungen beschreiben läßt. Dabei wurde versucht, die Ausdruckskraft in jeder Klasse zu maximieren und gleichzeitig die Anzahl der Elemente klein zu halten, ohne diese jedoch auf einer zu niederen Ebene anzusiedeln.

Ereignisse entstehen durch physikalische Eingaben, virtuelle Eingaben, geometrische Bedingungen, oder zeitliche Ereignisse. Aktionen bewirken u.a. Navigation, Veränderung geometrischer Attribute, Greifen (oder allgemein das Herstellen von Invarianten), verschiedene Arten von Animationen geometrischer Attribute, Selektion oder physikalische Ausgaben.

Da normalerweise eine Applikation nicht vollständig durch oben genannte "Bausteine" erstellt werden kann, besteht die Möglichkeit, zur Laufzeit applikationsspezifische Plugins zu laden. Diese haben Zugriff zu allen internen Daten des VR-Systems, und können ihrerseits ihre Funktionalität über eine standardisierte Schnittstelle anbieten. Dadurch können sie wie vordefinierte Aktionen in der Beschreibung der virtuelle Umgebung angesprochen werden und können ihrerseits Ereignisse erzeugen, die wie vordefinierte Ereignisse über die Beschreibung an andere Aktionen weitergeleitet werden können. Folgender Zyklus wird unterstützt, um die Entwicklung eines solchen Plugins zu beschleunigen: das System löscht alle Input-/Action-Instanzen eines Plugins; der Entwickler ändert das Plugin; das System lädt das Plugin neu und re-instantiiert alle vorherigen Instanzen.

Aufgrund der dynamischen Natur einer virtuelle Umgebung können Objekte entstehen oder gelöscht werden. Darum ist es notwendig, Objektreferenzen symbolisch zu halten. Gleichzeitig soll jede Aktion auf einer beliebigen Menge von Objekten (sofern sinnvoll) wirken können. Dies führt konsequenterweise zum Konzept der alternativen dynamischen Szenengraphen.

Die Objekte des Renderer-Szenengraphen enthalten nur graphische Attribute. Das VR-System benötigt jedoch darüber hinaus semantische Attribute. Diese werden jedoch nicht als zusätzliche Attribute der graphischen Objekte implementiert, da dies aus Gründen einer sauberen Implementierung des Gesamtsystems nicht ratsam ist.

Das vorgestellte Konzept wurde von mir als Basis des am Fraunhofer-Institut für graphische Datenverarbeitung entwickelten VR-Systems Virtual Design II implementiert. Eine Erweiterung zum Multi-User-System wurde vorgestellt.

Das bisher vorgestellte Framework bildet die mittlere Schicht eines 3-schichtigen Konzeptes: die darunter liegende besteht aus dem Szenengraphen, die darüber liegende ist eine weitere applikationsspezifische Abstraktion. Auf dieser Ebene spezifiziert der Benutzer nur noch einige semantische Attribute und "Rollen", welche dann umgesetzt werden in die oben vorgestellte Beschreibungssprache. Auf dieser Ebene ist es sinnvoller, von "Konfiguration" denn von Beschreibung zu sprechen. Für die weiter unten beschriebene Einbaumontage-Applikation wurde ein graphisches Konfigurationswerkzeug erstellt. Damit ist die Erstellung von Szenarien für die Einbaumontagesimulation (vorausgesetzt, die Geometrie ist vorhanden) eine Sache von Minuten.

Kollisionserkennung

Kollisionserkennung ist die Basis für fast alle physikalisch-basierte Simulationen, für Kraftrückkopplung und für Kollisionsanalysen bei der Einbaumontagesimulation. Die Anforderungen an die Kollisionserkennung sind, im Kontext VR, sehr hoch: sie muß sehr schnell sein, so daß die Echtzeitfähigkeit des VR-Systems nie gefährdet wird; für Kraftrückkopplung wird eine Kollisionserkennungsrate von mindestens 500 Hz benötigt; sie sollte auch deformierbare Objekte handhaben können; sie sollte ein Paar beteiligter Polygone liefern können; sie sollte möglichst die exakte Kollisionszeit liefern; und schließlich sollten die Hilfsdatenstrukturen möglichst klein sein und zur Startzeit mit erträglichem Zeitaufwand aufgebaut werden können. Diese Anforderungen sind so hoch, daß sie noch heute nicht vollständig erfüllt werden können.

Die in dieser Arbeit vorgestellten Algorithmen setzen eine polygonale Objektrepräsentation voraus. Dies ist dieselbe Repräsentation wie sie auch vom Renderer verwendet wird.

Eine der grundlegenden Operationen aller Kollisionserkennungsalgorithmen ist der Schnitt zweier Polygone. Aus der Literatur sind verschiedene Verfahren bekannt. Zwei davon wurden von verglichen, um das optimale Verfahren zu bestimmen. Es hat sich gezeigt, daß abhängig von der Eckenzahl der beiden Polygone das eine oder das andere Verfahren schneller ist.

Der als erstes betrachtet Kollisionserkennungsalgorithmus kann beliebige Objekte testen, auch deformierbare. Er besteht aus einer Pipeline von verfeinernden Bounding-Box-Tests, die immer im jeweils günstigsten Koordinatensystem durchgeführt werden. Gleichzeitig wird das Prinzip der "lazy evaluation" angewendet. Ein Großteil aller Bounding-Box-Tests kann zum einen schnell ausgeschlossen werden durch Vorab-Sortieren der Polygone beider Objekte. Dadurch ist es möglich, schnell den "Bereich" von Polygonen zu finden, die für eine Überlappung in Frage kommen. Zum anderen wird für alle Polygone eine obere Schranke ihrer Ausdehnung bestimmt, welche im weiteren Verlauf als Abbruchkriterium herangezogen werden kann. Mit diesem Algorithmus kann man zwei Kugeln mit je 10,000 Polygonen im Mittel in ca. 4.5 Millisekunden testen, und zwei Schlösser mit je 12,000 Polygonen in ca. 15 Millisekunden.

Es hat sich gezeigt, daß die Klasse der konvexen Objekte besonders schnelle Algorithmen ermöglicht, weil man bei diesen temporale Kohärenz ausnutzen kann. In dieser Arbeit wird ein solcher inkrementeller Algorithmus für diese Klasse vorgestellt. Er basiert auf der Eigenschaft der linearen Separierbarkeit von konvexen Objekten. Die Bestimmung einer separierenden Ebene geschieht ähnlich wie bei Perzeptrons (inklusive simuliertem Ausglühen), allerdings mit der zusätzlichen Optimierung des steilsten Abstiegs. Der Algorithmus wird schließlich zu einem inkrementellen gemacht, indem eine einmal gefunden separierende Ebene gespeichert wird. Da es sich um konvexe Objekte handelt, kann die Überprüfung, ob eine Ebene separierend ist, im günstigsten Fall abgeschlossen werden, nachdem alle Nachbarecken betrachtet worden sind.

Dieser Algorithmus ist in seiner aktuellen Implementierung eigentlich ein probabilistischer Monte-Carlo-Algorithmus. Findet er keine separierende Ebene, so besteht eine geringe Wahrscheinlichkeit, daß die Objekte dennoch nicht überlappen. Allerdings kommen in unseren Anwendungen konvexe Objekte an sich nicht vor. Vielmehr dienen konvexe Algorithmen zur Überprüfung der konvexen Hüllen der eigentlichen Objekte.

Ausführliche Tests wurden durchgeführt, um die beteiligten Parameter zu optimieren. Anschließend wurde der Algorithmus mit dem bis dahin besten bekannten Algorithmus für konvexe Objekte verglichen. Es zeigte sich, daß der hier vorgestellte Algorithmus für den Fall der Nicht-Kollision in allen Situationen um den Faktor 2 schneller ist. Außerdem scheint die Referenz-Implementierung I_collide des Konkurrenzalgorithmus in manchen Situationen numerische Instabilitäten aufzuweisen, wohingegen der hier vorgestellte Algorithmus keine Probleme zeigte.

Für den eben erwähnten Konkurrenzalgorithmus wird in der vorliegenden Arbeit ein vereinfachter Algorithmus vorgeschlagen. Der Vorteil besteht darin, daß keine Voronoi-Diagramme nötig sind. Somit entfallen relativ lange Berechnungen von zusätzlichen Datenstrukturen, die normalerweise zur Ladezeit gemacht werden müssen, und der damit verbundene Speicheraufwand. Außerdem besteht im Prinzip die Möglichkeit, daß die Objekte sich verformen, vorausgesetzt, sie bleiben konvex.

Für starre Objekte eignen sich besonders hierarchische Kollisionserkennungsalgorithmen. Diese erstellen für die Menge der Polygone einen Baum von Bounding-Volumen. Jedes Bounding-Volumen schließt dabei die ihm zugeordneten Polygone ein. Man kann Bounding-Volumen-Hierarchien auch als eine sukzessive Verfeinerung der Darstellung eines Objektes betrachten.

In dieser Klasse werden drei Algorithmen vorgestellt. Zwei davon basieren auf Bounding-Boxes als Hüllvolumen (daher heißt diese Hierarchie auch Box-Tree), der dritte auf einer Verallgemeinerung (DOP-Tree). Diese sollen im folgenden skizziert werden.

Die Traversierung von Bounding-Volumen-Hierarchien läuft fast immer nach demselben Schema ab. Die Grundoperation dabei ist ein Überlappungstest zweier Bounding-Volumen (Knoten) der beiden Bäume. Der erste Algorithmus basiert auf der Idee des Clippings und nutzt dabei die spezielle Geometrie von Bounding-Boxes und gewisse Eigenschaften der Anordnung Boxes innerhalb der Hierarchie aus. Diese spezielle Anordnung innerhalb der Hierarchie erlaubt es auch, alle Berechnungen eines Zyklus' bei der Rekursion auf die nächsttiefere Ebene wiederzuverwenden.

Der zweite Algorithmus verwendet fast dieselbe Datenstruktur wie der erste. Durch einen wesentlich effizienteren Überlappungstest ist er jedoch um etliche Faktoren schneller als der erste. Dies wird erreicht durch eine schnelle Methode, eine nicht-achsenparallel Bounding-Box in einer achsen-parallelen einzuschließen. Auch hier werden wieder alle Berechnungsergebnisse einer Stufe auf der nächsten wiederverwendet.

Ein hierarchischer Kollisionserkennungsalgorithmus kann nur so "gut" sein wie die Hierarchie zu den Objekten. Deswegen ist es wichtig, den Aufbau solcher Hierarchien zu optimieren. Trotzdem soll dieser Aufbau schnell genug sein, so daß er zur Ladezeit eines Objektes durchgeführt werden kann. Die vorliegende Arbeit definiert einige Kriterien, die als Heuristiken für den Aufbau dienen können. Ein top-down Algorithmus zum Aufbau von Box-Trees wird vorgestellt. Seine Komplexität liegt, unter bestimmten Annahmen, in O(n). In der Praxis wurde dies durch Experimente bestätigt. Um die von diesem Algorithmus erzeugten Hierarchien zu optimieren, wurde eine Reihe von Heuristiken an Hand der damit erzielbaren Kollisionszeiten getestet und der beste darunter bestimmt.

Beim Aufbau einer Bounding-Volumen-Hierarchie ist die geometrische Robustheit von hoher Bedeutung. (Geometrische Unrobustheit tritt besonders bei synthetischen Objekten stark zutage.) Bei dem hier implementierten Algorithmus wird geometrische Robustheit durch epsilon-Schranken mit absolut zufriedenstellendem Ergebnis erzielt.

Der dritte hierarchische Algorithmus basiert auf der Verallgemeinerung von Bounding-Boxes, den sog. diskret orientierten Polytopen (DOP). Sie haben den Vorteil, daß man im Prinzip die konvexe Hülle eines Objektes damit beliebig genau annähern kann, und dennoch der Überlappungstest so einfach wie der von Bounding-Boxes ist (bis auf einen Faktor). Hier wird eine elegante Berechnung angegeben, mit Hilfe derer ein nicht-achsenparalleler DOP (was laut Definition eigentlich kein DOP ist) durch einen achsenparallelen eingeschlossen werden kann. Diese Berechnung benötigt O(k) Zeit (k = Anzahl der Orientierungen); das in der Literatur angegebene Verfahren benötigt O(k^2), oder unverhältnismäßig viel Speicheraufwand. Stellt man DOPs durch einen k-dimensionalen Vektor dar, so kann man einen schiefen DOP mittels einer affinen Transformation durch einen achsenparallelen DOP einschließen. Diese affine Transformation hängt von der Orientierung des nicht-achsenparalleler DOPs ab. Da aber alle DOPs eines DOP-Trees gleich orientiert sind, muß man diese affine Transformation nur ein Mal bestimmen.

Der DOP-Tree-Algorithmus hat im wesentlichen einen Parameter, nämlich die Anzahl der Orientierungen. Durch ausführliche Tests wurde des Optimum bei k=24 Orientierungen bestimmt. Auch für diesen Algorithmus wurde ein Verfahren angegeben, mit dem ein guter DOP-Tree konstruiert werden kann. Er wird durch eine Heuristik geleitet, die auf einer Schätzung des Volumens der DOP-Kandidaten beruht.

Dieser dritte Algorithmus ist schneller als die zwei auf Box-Trees basierenden. Ein Vergleich mit einem der schnellsten in der Literatur vorgestellten Algorithmus, in der Rapid-Implementierung, zeigte, daß der DOP-Tree-Algorithmus ungefähr gleich schnell wie Rapid ist: in manchen Fällen ist er signifikant schneller, in manchen langsamer, in manchen gibt es keinen signifikanten Unterschied. Damit kann z.B. ein Schloß von 50,000 Polygonen (pro Objekt) in 1 Millisekunde, und eine Autokarosserie von 60,000 Polygonen in unter 1/2 Millisekunde getestet werden.

Der DOP-Tree-Algorithmus wurde unter der Annahme implementiert, daß die Anzahl und Ausrichtung der Orientierungen für alle Hierarchien gleich ist. Diese Einschränkung ist nicht notwendig: sowohl die Traversierung als auch der Aufbau der Hierarchien funktionieren genauso im allgemeinen Fall. (Allerdings ist der praktische Gewinn für die Kollisionserkennung fraglich.)

Da inkrementelle Algorithmen für konvexe Objekte hervorragende Beschleunigungen gegenüber nicht-inkrementellen aufweisen, erschien es konsequent, auch für die allgemeinere Klasse der starren Objekte nach einer inkrementellen Variante zu suchen. In dieser Arbeit wird ein solcher inkrementeller Algorithmus beschrieben. Er arbeitet auf einer beliebigen Bounding-Volumen-Hierarchie. Anstatt jedoch immer von den Wurzeln auszugehen, startet dieser von unten oder der Mitte und arbeitet sich dann weiter nach unten oder oben vor. Der Preis ist eine zusätzliche Datenstruktur pro Objektpaar (der sog. Link-Tree).

Flexible Objekte stellen für die Kollisionserkennung ein besonderes Problem dar, da die meisten Datenstrukturen bei Deformation ungültig werden. Für diese Klasse von Objekten wurden in dieser Arbeit zwei Algorithmen vorgestellt. Der erste basiert auf einer Bounding-Volumen-Hierarchie und der Annahme, daß die Deformation zwischen zwei Frames normalerweise relativ klein ist. Der Algorithmus bezieht bei der Traversierung der Hierarchien die maximale "Drift" der Polygone eines Objektes mit ein und versucht, die Hierarchie so selten wie möglich zu aktualisieren.

Der zweite Algorithmus für flexible Objekte betrachtet ein Objekt als eine lose Menge von (Polygon-) Bounding-Boxes. Er geht von der Annahme aus, daß diese Boxes sich nicht zu weit zwischen zwei Frames bewegen. Der Algorithmus sortiert die Menge der Boxes in jeder Koordinatenachse. Von einem Frame zum nächsten sollte der Aufwand für das Sortieren relativ gering sein. Sich überlappende (rote und blaue) Boxes werden anschließend durch drei "Sweeps" über je eine Achse gefunden. Leider haben Benchmarks zwischen diesen Algorithmen und dem Bounding-Box-Pipeline-Algorithmus gezeigt, daß letzterer in allen praktisch relevanten Fällen schneller zu sein scheint.

Die bisher betrachteten Algorithmen behandeln das Problem der Kollisionserkennung zwischen einem Paar von Objekten. Hat man eine virtuelle Umgebung bestehend aus einer großen Anzahl von sich bewegenden Objekten, so bekommt man auch auf der Objekt-Ebene das n2-Problem. Um dieses Problem zu lösen werden zwei Space-Indexing-Strukturen, das Gitter und der Octree, untersucht. Sowohl das Gitter als auch der Octree wurden "inkrementell" implementiert, d.h., daß nur diejenigen Zellen besucht werden, die tatsächlich modifiziert werden müssen. Ein Vergleich zeigt zwischen Gitter und Octree zeigt, daß das Gitter für dynamische Szenen wesentlich effizienter ist. Dies ist ein Unterschied zu der eher statischen Anwendung beim Ray-Tracing, wo Octrees effizienter als Gitter sind.

Es ist klar, daß ein Gitter einen Aufwand von O(n) hat, wohingegen eine Nachbarbestimmung anhand eines Überlappungstestes der konvexen Hüllen für n Objekte einen Aufwand von O(n2) hat. Dafür haben letztere den Vorteil, daß sie, im Gegensatz zum Gitter, relativ selten eine unnötige exakte Kollisionserkennung anstoßen. Ausführliche Experimente mit verschiedenen Objektanzahlen haben gezeigt, daß unterhalb einer gewissen Objektanzahl das Gitter langsamer als der Separating-Planes-Algorithmus ist. Diese Schranke liegt bei ca. 30 Objekten, hängt aber auch etwas von der Anzahl der Polygone ab. Deswegen wird in dieser Arbeit ein Kombination vorgeschlagen, wobei das Gitter und der Separating-Planes-Algorithmus zwei aufeinander folgende Stufen in der Kollisionspipeline sind. Diese Kombination wird oberhalb der erwähnten Schranke verwendet, wohingegen unterhalb dieser Schranke nur der Separating-Planes-Algorithmus verwendet wird.

Abschließend wird eine Kollisionspipeline vorgestellt, die alle bisher gewonnen Erkenntnisse und Algorithmen in einem kohärenten System vereint. Diese Pipeline wurde implementiert und ist in das VR-System Virtual Design II integriert.

Dieses Kollisionsmodul wurde sowohl grobkörnig als auch feinkörnig parallelisiert. Experimente zeigen, daß die Parallelisierung eine gute Effizienz aufweist. Gleichzeitig kann das Kollisionsmodul nebenläufig zur main loop des VR-Systems laufen. Die Nebenläufigkeit ist zur Aufrechterhaltung einer konstanten Frame-Rate wichtig.

Interaktion

In diesem Kapitel werden verschiedene Aspekte der Interaktion in und mit virtuellen Umgebungen betrachtet.

Nach der Vorstellung eines Frameworks zur verteilten Anbindung von VR-Geräten werden einige Algorithmen zur Verarbeitung der von VR-Geräten kommenden Meßwerte vorgestellt.

Dazu gehört die statische benutzerunabhängige Gestenerkennung. Hier wurden verschiedene Ansätze implementiert. Als robustester hat sich derjenige erwiesen, der einen 20-dimensionalen Vektor in ein diskretes {-1,0,1}20-Volumen klassifiziert. Zusammen mit einer on-line Kalibrierung des Dataglove ergibt dies eine, unserer Erfahrung nach, sehr robuste, benutzerunabhängige Gestenerkennung.

Die von Spracherkennnungsprogrammen gelieferten Wörter müssen analysiert werden, um die gewünschte Aktion auslösen zu können. Es hat sich gezeigt, daß es flexibler ist, die "Satzerkennung" erst auf der Seite des VR-Systems zu machen und die Spracherkennung selbst im "word spotting" Modus zu betreiben. Zu diesem Zweck wird hier eine einfache Grammatik vorgestellt, die Füllwörter zuläßt und Parameter unterstützt. Ein weiterer Vorteil dieser Vorgehensweise ist, daß die zu erkennenden Sätze vom Autor der virtuellen Umgebung in derselben Beschreibung spezifizieren werden können, in der auch der Rest dieser Umgebung spezifiziert wird. In diesem Kontext werden einige Richtlinien wiedergegeben, die sich als sinnvoll bei der Benutzung von Spracheingabe in VR-Applikationen erwiesen haben.

Tracking des Kopfes und der Hände ist einer der wichtigsten Eingabekanäle (dem Benutzer normalerweise nicht bewußte). Allerdings haben die meistens verwendeten elektro-magnetischen Systeme zwei gravierende Probleme: die Meßwerte sind verrauscht, und sie sind verzerrt. Jedes dieser beiden Probleme kann ein VR-System praktisch unbrauchbar machen.

Zur Filterung wurde ein Verfahren vorgestellt, das die speziellen Bedingungen eines elektro-magnetischen Tracking-Systems berücksichtigt. Um Verzögerungen in der Daten-Pipeline auszugleichen arbeitet dieses Verfahren prädiktiv und unterscheidet zwei Bewegungsmodi. Diese müssen innerhalb weniger Samples erkannt werden, da die elektro-magnetischen Systeme oft mit relativ niedriger Sampling-Frequenz arbeiten. Die hier vorgeschlagene Filter-Pipeline kann sowohl Translationen als auch Orientierungen filtern.

Um das Problem der Verzerrung der Meßwerte zu lösen wurde ein Korrekturverfahren basierend auf radialen Basisfunktionen vorgestellt. Dieses Verfahren eignet sich sowohl zur Korrektur von Translation als auch Orientierung. Es arbeitet sehr schnell, so daß keine zusätzlichen Verzögerungen entstehen. Experimente mit realen gemessenen Daten zeigen eine Verbesserung von 40 cm auf ca. 4 cm; Experimente mit synthetisch erzeugten Daten zeigen eine Verbesserung von 60 cm auf ca. 2 cm.

In diesem Zusammenhang wurden die beiden häufigsten elektro-magnetischen Systeme auf ihre Verzerrung hin untersucht. Messungen haben gezeigt, daß, entgegen den Herstellerangaben, auch das gepulste Gleichstromsystem erhebliche Verzerrungen aufweist.

Eine weitere grundlegende Interaktion in virtuellen Umgebungen ist die Navigation. Für diese wurde ein allgemeines Konzept, das flying carpet Modell, vorgestellt, mit dem alle praxisrelevanten Navigationsmetaphern abgedeckt werden können. Dies schließt ein Modell des Kopfes mit ein, da die Verarbeitung des Kopftrackings dadurch etwas komplexer wird, daß der Kopfsensor nicht in unmittelbarer Nähe der Augen angebracht ist.

Weitere grundlegende Interaktionen sind Menüs und Selektion. Verschiedene Metaphern werden für deren Implementierung vorgestellt und diskutiert.

Eines der wichtigsten Werkzeuge bei der Einbaumontagesimulation sind die Hände. Insbesondere das Greifen von Bauteilen oder Werkzeugen ist eine sehr häufig vorkommende Interaktion. Bislang wurde das Greifen noch sehr "abstrakt" durchgeführt. In dieser Arbeit wird ein Verfahren vorgestellt, um eine Art des Greifens, das sog. "power grasp", natürlich und intuitiv ausführen zu können. Dazu wird die virtuelle Hand des Benutzers um das Bauteil "geschmiegt" und eine Kontaktanalyse durchgeführt.

In der Einbaumontagesimulation müssen oft Montagepfade von Bauteilen aufgezeichnet werden, die kollisionsfrei sein müssen. Da es (noch) keine Möglichkeit gibt, die reale Hand des Benutzers daran zu hindern, eine Kollision herbeizuführen, muß diese auf anderem Wege erreicht werden. Dazu wird statt dem starren Greifen eine Gummibandmetapher eingeführt und mittels einer physikalisch-basierten Simulation das Bauteil auf einem kollisionsfreien Pfad bewegt. Im Falle einer Kollision versucht das Bauteil, auf der Oberfläche zu "gleiten". Die hierfür entwickelten Algorithmen werden in ähnlicher Form auch für eine Kraftrückkopplung benötigt werden.

Die Bewegung des Bauteils wird weiterhin durch die Hand gesteuert. Solange keine Kollision entsteht, folgt das Bauteil der Hand. Im Falle einer Kollision bestimmt der Algorithmus mittels Intervallhalbierung eine Näherung der exakten Kontaktstelle und -position. Der so gefundene Kontakt wird analysiert, um die Kontaktnormalen und die Kontaktsituation (1-, 2-, 3- oder Mehr-Punkt-Kontakt) zu bestimmen. Anhand dieser Analyse werden neue Geschwindigkeiten bestimmt und auf das Objekt aufgebracht. Verschiedene Abbruchkriterien sorgen für den Abbruch der Simulation, wenn das Bauteil der Hand weit genug gefolgt ist, oder wenn es sich nicht mehr bewegen läßt.

Applikationen

Die in dieser Arbeit entwickelten Konzepte und Algorithmen wurden in dem am IGD entwickelten VR-System Virtual Design II integriert. Mit diesem System wurden eine ganze Reihe von Applikationen entwickelt, viele im Bereich Virtual Prototyping, einige im Bereich Edutainment, Cultural Heritage, Shows, und immersive scientific visualization. Einige davon werden in der vorliegenden Arbeit beschrieben.

Virtual Prototyping wird in dieser Arbeit definiert als die Anwendung von Virtual Reality beim Prototypisieren anstelle von physikalischen Mock-Ups. Diese Definition ist enger als die häufig in der Industrie verwendete, wo Virtual Prototyping generell als die Anwendung von Software anstelle von physikalischen Prototypen verstanden wird.

Die Einbaumontagesimulation ist eine vergleichsweise komplexe Applikation. Die hierfür entwickelten Funktionalitäten werden in dieser Arbeit näher vorgestellt. Diese reichen von Funktionalitäten zur Analyse der Geometrie (Clipping, variable Benutzergröße, Stammdateninformationen, und verschiedene Abstandsmeßfunktionen), über einfache inverse Kinematiken, visuelles, audielles und taktiles Feedback bei Kollision, bis zur Dokumentation (Montagepfade, visuelle und textuelle Anmerkungen, Snapshots, HTML).

Gabriel Zachmann
Last modified: Sat Sep 10 15:55:01 MDT 2005