To detect errors or find potential for improvement during the CAD-supported development of a complex technical system like modern industrial machines, the system's virtual prototype can be examined in virtual reality (VR) in the context of virtual design reviews. Besides exploring the static shape of the examined system, observing the machines' mechanics (e.g., motor-driven mechanisms) and transport routes for the material transport (e.g., via conveyor belts or chains, or rail-based transport systems) can play an equally important role in such a review. In practice it is often the case, that the relevant information about transport routes, or kinematic properties is either not consequently modeled in the CAD data or is lost during conversion processes. To significantly reduce the manual effort and costs for creating animations of the machines complex behavior with such limited input data for a design review, we present a set of algorithms to automatically determine geometrical properties of machine parts based only on their triangulated surfaces. The algorithms allow to detect the course of transport systems, the orientation of objects in 3d space, rotation axes of cylindrical objects and holes, the number of tooth of gears, as well as the tooth spacing of toothed racks. We implemented the algorithms in the VR system PADrend and applied them to animate virtual prototypes of real machines.

To detect errors or find potential for improvement during the CAD-supported development of a complex technical system like modern industrial machines, the system’s virtual prototype can be examined in virtual reality (VR) in the context of virtual design reviews. Besides exploring the static shape of the examined system, observing the machines’ mechanics (e.g., motor-driven mechanisms) and transport routes for the material transport (e.g., via conveyor belts or chains, or rail-based transport systems) can play an equally important role in such a review. In practice it is often the case, that the relevant information about transport routes, or kinematic properties is either not consequently modeled in the CAD data or is lost during conversion processes. To significantly reduce the manual effort and costs for creating animations of the machines complex behavior with such limited input data for a design review, we present a set of algorithms to automatically determine geometrical properties of machine parts based only on their triangulated surfaces. The algorithms allow to detect the course of transport systems, the orientation of objects in 3d space, rotation axes of cylindrical objects and holes, the number of tooth of gears, as well as the tooth spacing of toothed racks. We implemented the algorithms in the VR system PADrend and applied them to animate virtual prototypes of real machines.

In der CAD-unterstützten Entwicklung von technischen Systemen (Maschinen, Anlagen etc.) werden virtuelle Prototypen im Rahmen eines virtuellen Design-Reviews mit Hilfe eines VR-Systems gesamtheitlich betrachtet, um frühzeitig Fehler und Verbesserungsbedarf zu erkennen. Ein wichtiger Untersuchungsgegenstand ist dabei die Analyse von Transportwegen für den Materialtransport mittels Fließbändern, Förderketten oder schienenbasierten Transportsystemen. Diese Transportwege werden im VR-System animiert. Problematisch dabei ist, dass derartige Transportsysteme im zugrundeliegenden CAD-Modell in der Praxis oft nicht modelliert und nur exemplarisch angedeutet werden, da diese für die Konstruktion nicht relevant sind (z.B. der Fördergurt eines Förderbandes, oder die Kette einer Förderkette), oder die Informationen über den Verlauf bei der Konvertierung der Daten in das VR-System verloren gehen. Bei der Animation dieser Transportsysteme in einem VR-System muss der Transportweg also aufwändig, manuell nachgearbeitet werden. Das Ziel dieser Arbeit ist die Reduzierung des notwendigen manuellen Nachbearbeitungsaufwandes für das Design-Review durch eine automatische Berechnung der Animationspfade entlang eines Transportsystems. Es wird ein Algorithmus vorgestellt, der es ermöglicht mit nur geringem zeitlichem Benutzeraufwand den Animationspfad aus den reinen polygonalen dreidimensionalen Daten eines Transportsystems automatisch zu rekonstruieren.

Defining, measuring, and comparing the quality and efficiency of rendering algorithms in computer graphics is a demanding challenge: quality measures are often application specific and efficiency is strongly influenced by properties of the rendered scene and the used hardware. We survey the currently employed evaluation methods for AQ1 the development process of rendering algorithms. Then, we present our PADrend framework, which supports systematic and flexible development, evaluation, adaptation, and comparison of rendering algorithms, and provides a comfortable and easy-to-use platform for developers of rendering algorithms. The system includes a new evaluation method to improve the objectivity of experimental evaluations of rendering algorithms.

In this paper, we solve the local gathering problem of a swarm of n indistinguishable, point-shaped robots on a two dimensional grid in asymptotically optimal time O(n) in the fully synchronous FSYNC time model. Given an arbitrarily distributed (yet connected) swarm of robots, the gathering problem on the grid is to locate all robots within a 2x2- sized area that is not known beforehand. Two robots are connected if they are vertical or horizontal neighbors on the grid. The locality constraint means that no global control, no compass, no global communication and only local vision is available; hence, a robot can only see its grid neighbors up to a constant L1-distance, which also limits its movements. A robot can move to one of its eight neighboring grid cells and if two or more robots move to the same location they are merged to be only one robot. The locality constraint is the significant challenging issue here, since robot move- ments must not harm the (only globally checkable) swarm connectivity. For solving the gathering problem, we provide a synchronous algorithm { executed by every robot { which ensures that robots merge without breaking the swarm con- nectivity. In our model, robots can obtain a special state, which marks such a robot to be performing specific connec- tivity preserving movements in order to allow later merge operations of the swarm. Compared to the grid, for gath- ering in the Euclidean plane for the same robot and time model the best known upper bound is O(n^2).

We consider the following variant of the two dimensional gathering problem for swarms of robots: Given a swarm of n indistinguishable, point shaped robots on a two dimensional grid. Initially, the robots form a closed chain on the grid and must keep this connectivity during the whole process of their gathering. Connectivity means, that neighboring robots of the chain need to be positioned at the same or neighboring points of the grid. In our model, gathering means to keep shortening the chain until the robots are located inside a 2*2 subgrid. Our model is completely local (no global control, no global coordinates, no compass, no global communication or vision, ...). Each robot can only see its next constant number of left and right neighbors on the chain. This fixed constant is called the viewing path length. All its operations and detections are restricted to this constant number of robots. Other robots, even if located at neighboring or the same grid point cannot be detected. Only based on the relative positions of its detectable chain neighbors, a robot can decide to obtain a certain state. Based on this state and their local knowledge, the robots do local modifications to the chain by moving to neighboring grid points without breaking the chain. These modifications are performed without the knowledge whether they lead to a global progress or not. We assume the fully synchronous FSYNC model. For this problem, we present a gathering algorithm which needs linear time. This result generalizes a result, where an open chain with specified distinguishable (and fixed) endpoints is considered.

Viele virtuelle 3-D-Szenen im industriellen Bereich sind nicht gleichmäßig strukturiert, z.B. weil sie eine stark unterschiedliche Dichteverteilung der Polygone aufweisen. Für solch heterogene Daten existiert kein Algorithmus, der die Gesamtheit der Daten sowohl schnell als auch mit guter Qualität darstellen kann. Die Auswahl der richtigen Algorithmen für einzelne Szenenteile durch einen Experten ist zeitintensiv und in vielen Visualisierungssystemen nicht umzusetzen. Um dieses Problem zu lösen, setzt das hier vorgestellte Multi-Algorithmen-Rendering verschiedene Renderingalgorithmen gleichzeitig ein, um eine virtuelle 3-D-Szene darzustellen. Das Verfahren unterteilt die Szene dafür in einem Vorverarbeitungsschritt automatisch in geeignete Teilregionen und bestimmt deren Eigenschaften. Diese Daten werden zur Laufzeit dazu genutzt, um ständig für den aktuellen Standpunkt des Betrachters eine Abschätzung der Qualität und Laufzeit der zur Auswahl stehenden Renderingalgorithmen zu berechnen. Durch die Lösung eines Optimierungsproblems kann so bei vorgegebener Bildrate durch die passende Zuordnung der Algorithmen zu den Regionen die Bildqualität optimiert werden – bei automatischer Anpassung an die Leistungsfähigkeit der eingesetzten Hardware. In einer experimentellen Evaluierung vergleichen wir die Laufzeit und Bildqualität des Verfahrens mit denen verbreiteter Standardrenderingverfahren.

Many 3D scenes (e.g. generated from CAD data) are composed of a multitude of objects that are nested in each other. A showroom, for instance, may contain multiple cars and every car has a gearbox with many gearwheels located inside. Because the objects occlude each other, only few are visible from outside. We present a new technique, Spherical Visibility Sampling (SVS), for real-time 3D rendering of such -- possibly highly complex -- scenes. SVS exploits the occlusion and annotates hierarchically structured objects with directional visibility information in a preprocessing step. For different directions, the directional visibility encodes which objects of a scene's region are visible from the outside of the regions' enclosing bounding sphere. Since there is no need to store a separate view space subdivision as in most techniques based on preprocessed visibility, a small memory footprint is achieved. Using the directional visibility information for an interactive walkthrough, the potentially visible objects can be retrieved very efficiently without the need for further visibility tests. Our evaluation shows that using SVS allows to preprocess complex 3D scenes fast and to visualize them in real time (e.g. a Power Plant model and five animated Boeing 777 models with billions of triangles). Because SVS does not require hardware support for occlusion culling during rendering, it is even applicable for rendering large scenes on mobile devices.

We present a parallel rendering system for heterogeneous PC clusters to visualize massive models. One single, powerful visualization node is supported by a group of backend nodes with weak graphics performance. While the visualization node renders the visible objects, the backend nodes asynchronously perform visibility tests and supply the front end with visible scene objects. The visualization node stores only currently visible objects in its memory, while the scene is distributed among the backend nodes’ memory without redundancy. To efficiently compute the occlusion tests in spite of that each backend node stores only a fraction of the original geometry, we complete the scene by adding highly simplified versions of the objects stored on other nodes. We test our system with 15 backend nodes. It is able to render a ≈ 350,M polygons (≈ 8.5,GiB) large aircraft model with 20, to 30,fps and thus allows a walk-through in real-time.

Occlusion culling is a common approach to accelerate real-time rendering of polygonal 3D-scenes by reducing the rendering load. Especially for large scenes, it is necessary to remove occluded objects to achieve a frame rate that provides an interactive environment. In order to benefit from the culling properly, often hierarchical data structures are used. These data structures typically create a spatial subdivision of a given scene into axis-aligned bounding boxes. These boxes can be tested quickly, but they are not very precise. By using these boxes, the included objects are detected as visible, even if other objects occlude them (false-positives). To get perfect results, the models’ original geometry included in the box has to be tested, but this would require too much computational power. To overcome this problem, original objects’ approximations could be used, but typical methods for mesh simplification cannot be applied, because they do not create an outer hull for a given object. We present a model simplification algorithm, which generates simple outer hulls, consisting of only few more triangles than a box, while preserving an object’s shape better than a corresponding bounding box. This approach is then extended to a hierarchical data structure, the so-called hull tree, that can be generated for a given scene to improve the visibility tests. Next, we present an approximative rendering algorithm, which combines the features of the hull tree with the use of inner hulls for efficient occlusion detection and global state-sorting of the visible objects.

Gathering n mobile robots in one single point in the Euclidean plane is a widely studied problem from the area of robot formation problems. Classically, the robots are assumed to have no physical extent, and they are able to share a position with other robots. We drop these assumptions and investigate a similar problem for robots with (a spherical) extent: the goal is to gather the robots as close together as possible. More exactly, we want the robots to form a sphere with minimum radius around a predefined point. We propose an algorithm for this problem which synchronously moves the robots towards the center of the sphere unless they block each other. In this case, if possible, the robots spin around the center of the sphere. We analyze this algorithm experimentally in the plane. If R is the distance of the farthest robot to the center of the sphere, the simulations indicate a runtime which is linear in n and R. Additionally, we prove a theoretic upper bound for the runtime of O(nR) for a discrete version of the problem. Simulations also suggest a runtime of O(n + R) for the discrete version.

Commercial software of material flow simulations has the ability to layout the simulated models. Arranged equipment, such as conveyors or machines, includes the need to model and determine motion paths for moving objects like forklifts or automatically guided vehicles, so that the simulation framework is able to navigate all vehicles across those motion paths. After analyzing first scenarios, the user often carries out layout changes in the simulation model, e.g. moving, adding or deleting equipment. However, those changes cause time consuming, additional modeling of the motion paths for the user. Our motion planning algorithm reduces these changes by automatically determining the motion paths for moving objects, depending on an actual model layout without colliding with other objects. The algorithm works on the basis of the virtual scene’s 3D-data used for the simulation model’s visualization. We demonstrate the technique with a multi-floor building example.

We present a parallel algorithm for the rendering of complex three-dimensional scenes. The algorithm runs across heterogeneous architectures of PC-clusters consisting of a visualization-node, equipped with a powerful graphics adapter, and cluster nodes requiring weaker graphics capabilities only. The visualization-node renders a mixture of scene objects and simplified meshes (Reliefboards). The cluster nodes assist the visualization-node by asynchronous computing of Reliefboards, which are used to replace and render distant parts of the scene. Our algorithm is capable of gaining significant speedups if the cluster's nodes provide weak graphics adapters only. We trade the number of cluster nodes off the scene objects' image quality.

Many professional cluster systems consist of nodes with different hardware configurations. Such heterogeneous environments require different load-balancing techniques than homogenous environments. The c-load-collision-protocol is able to achieve good results for data-management purposes. Using this protocol, we propose a way for load-balancing in interactive rendering environments. For this work, we implemented a parallel rendering system and took different picking strategies into account to compare the results. The advantage of our approach compared to other approaches is that we group the available nodes of a cluster into two different categories, based on the hardware abilities. Some nodes are used solely for rendering, while others serve as secondary storage and to assist the former ones by performing auxiliary calculations.

Modern companies are nowadays confronted with an increasing demand of multiple products, where they need to perform more flexible every day. Cost-intensive decisions are to be confirmed in short times, in order to minimize risks and secure efficient production programs as well as material flows. Tools for this digital planning via simulation methods are one well established possibility to receive decision support. Nevertheless, the creation of the necessary simulation models is a complicated and error-prone process, where complexity of modeling, validation and verification depends on the used tool and its functionalities. This paper presents implemented concepts for an innovative user support in his tasks of verification and validation of simulation models during the execution of a simulation run. Time-intensive procedures like stopping simulation, parameterization and restarting within the problem analysis are simplified. So the user is able to focus on the real problem solving task.

For a fixed virtual scene (=collection of simplices) S and given observer position p, how many elements of S are weakly visible (i.e. not fully occluded by others) from p? The present work explores the trade-off between query time and preprocessing space for these quantities in 2D: exactly, in the approximate deterministic, and in the probabilistic sense. We deduce the EXISTENCE of an O(m^2/n^2) space data structure for S that, given p and time O(log n), allows to approximate the ratio of occluded segments up to arbitrary constant absolute error; here m denotes the size of the Visibility Graph--which may be quadratic, but typically is just linear in the size n of the scene S. On the other hand, we present a data structure CONSTRUCTIBLE in O(n*log(n)+m^2*polylog(n)/k) preprocessing time and space with similar approximation properties and query time O(k*polylog n), where k<n is an arbitrary parameter. We describe an implementation of this approach and demonstrate the practical benefit of the parameter k to trade memory for query time in an empirical evaluation on three classes of benchmark scenes.

In this paper we present a system for the simultaneous visualization of several parallel executed simulation replications. By aggregating the scenes of multiple similar simulations into one single scene it is possible to make a visual statistical analysis of a set of discrete event simulations as well as to easily compare different system parameterizations. The aim of our system is to enhance the model analysis, verification and validation process in terms of speed and ease. The parallel execution of several simulations of complex models and the visualization of these cannot be done on one computer, thus a parallel approach is necessary. Our system uses a thin-client and multiple processors on a PC-cluster. The rendering and the simulation execution are done on processors of the cluster. The client is used only for the visualization of the images transmitted by the cluster and for user interaction.

The paper describes an approach for an aggregated animation of a simulation experiment in an interactive 3D environment, visualizing multiple, distributed simulation runs. Although the general approach of a 3-dimensional visualization of material flow simulation helps to understand the dynamic behavior of a system better as well as faster, it remains unclear, how typical the animated simulation represents the model, if there is a stochastic influence for even some parameters. By the integrated visualization of multiple distributed simulation runs, this uncertainty can be solved, which will be shown in this paper for a typical simulation study of a queuing system.

This paper describes a method for the animation of a large number of objects within a dynamic 3D visualization of a material flow simulation model. It uses key-frame based animation. The number of animated objects may grow constantly in complex simulation models, which might lead to an amount of animations that is too big to be computed in real-time. By the use of a dynamic adjustment, the presented algorithm prefers important animations. Less relevant animations are updated rarely, whereby the selection itself is taken by multiple indicators, e.g. the visible size of the animated object on the screen, in order to keep a good optical impression. Dependent on the computing power of the computer, the algorithm controls the animations in such a way, that the fluid visualization of a large number of objects is still possible. Though the algorithm is to be used within a material flow simulator, it is moreover implemented in a specific animation editor, which allows the design and control of animation schemes. It supports the use of grouping to allow the creation of hierarchical structures for complex animations in a fast and easy manner. The evaluation of the algorithm is proven by a test scene, consisting of tens of thousands animated objects.

Dieser Artikel beschreibt eine Methode zur Animation einer großen Anzahl von Objekten zur dynamischen 3D-Visualisierung eines Simulationsmodells mittels der Materialflusssimulation auf Basis von Schlüsselbildern. Die Anzahl zu animierender Objekte ist in komplexen Modellen zu groß, um alle Animationen flüssig darzustellen. Dynamisch abgestuft wählt das entwickelte Verfahren gezielt wichtige Animationen aus, weniger relevante Animationen werden entsprechend seltener animiert. Die Selektion der Animationen erfolgt nach der projizierten Größe der Objekte auf das Ausgabegerät, um einen guten optischen Eindruck beizubehalten. Angepasst an die Leistungsfähigkeit des Rechners wird das Verfahren so geregelt, dass die Visualisierung einer hohen Anzahl von Objekten in Echtzeit möglich bleibt. Das Verfahren ist in einem Editor prototypisch implementiert, mit dem Schlüsselbilder für Objekte erzeugt werden können. Das Gruppieren von Objekten wird erlaubt, so dass eine Hierarchie von Bewegungspfaden definierbar ist. Die Evaluierung der Methode wird mittels Testszenen durchgeführt, die aus mehreren zehntausend animierten Objekten bestehen.

The validation of material flow models as well as the selection of promising strategies for the generation of a successful experiment plan is a time-consuming process. A new approach is presented, which supports the simulation expert in his working process by giving him the opportunity to modify the simulated simulation run and afterwards compare the effects of his modification with the original setting, online and in one user interface, implemented by switching the visualizations between the simulation runs or opening up to 5 parallel 3D windows. The method developed therefore clones existing simulation runs online and allows the navigation within these existing simulation runs. The method has been implemented and is validated by a test model, which describes in detail the new working process of a modeler. New research questions are derived from this work, which will define following working steps.

We consider the problem of exploring an unknown environment using a swarm of autonomous robots with collective behavior emerging from their local rules. Each robot has only a very restricted view on the environment which makes cooperation difficult. We introduce a software system which is capable of simulating a large number of such robots (e.g. 1000) on highly complex terrains with millions of obstacles. Its main purpose is to easily integrate and evaluate any kind of algorithm for controlling the robot behavior. The simulation may be observed in real-time via a visualization that displays both the individual and the collective progress of the robots. We present the system design, its main features and underlying concepts.

In this paper the ideas of a new research project are presented. The material flow simu- lator d3FACT insight shall manage multiple parallel and time synchronous simulations to grand the power of real-time visualization in combination with statistical analysis. This research is issued to overcome the conflict of simulation run repetition for a good statistical basis and real-time immersive visualization. A side effect will be the reduc- tion of time needed for simulation experiments. The planned simulation tool has the feature of triggered cloning, i.e., the user can decide during runtime to clone a set of simulations after changing parameters to preserve the original system. The simulations will be aggregated by visualization and statistics. The rendering is planned to overlay several simulations using effects like inking and transparency. Simulation data will be aggregated with statistical functions and diagrams.

The visualisation of manufacturing-processes assists the user in understanding and analysis. Typically he can move free and unguided in a virtual environment which visualizes the entire process. Thus knowledge and conclusions are to some extend acquired on a random base. This article describes the development of a tool, which enables the user to interactively improve significant production processes in the simulation. He moves in a virtual 3D-environment (walkthrough system) and is able to acquire automatically calculated indications for significant processes. At the same time the simulation considers significant objects in a more detailed way. If the viewer is interested in a significant process, he is automatically guided to the relevant location where he can examine the critical situation by modification of the simulation model.

Unternehmen operieren zunehmend in einem schwierigen Umfeld: Die Innovationsdynamik nimmt zu; die Produktlebenszyklen werden kürzer; gleichzeitig werden die Produkte komplexer; der harte Wettbewerb zwingt die Unternehmen, auf Marktveränderungen zu reagieren. Aus dieser Entwicklung resultieren hohe Anforderungen an die Gestaltung der Fertigungsprozesse. Im Wesentlichen kommt es darauf an, die Fertigungsprozesse möglichst rasch an die neuen Gegebenheiten anzupassen, bzw. neue Fertigungsprozesse so zu planen, dass sie auf Anhieb die erforderlichen Resultate bringen. Ein wichtiges Mittel hierfür der Einsatz von Materialflusssimulationen. Hierzu ist zunächst die Erstellung eines Simulationsmodells notwendig. Dafür wird in einem ersten Schritt das zu betrachtende System analysiert und ein rechnerinternes Modell erzeugt. Dieses beinhaltet die Modellierung von Funktionen, Prozessen, Verhaltensweisen oder Regeln, die im Modell die tatsächlichen Wirkzusammenhänge im Unternehmen widerspiegeln sollen. Die so modellierten Aspekte sind untereinander so vernetzt, dass alle Funktionen des Modells ein Ganzes ergeben. Für viele Fragenstellungen werden umfangreiche Modelle mit einem komplexen Verhalten benötigt. Andererseits steigt mit zunehmender Größe und Komplexität des Simulationsmodells auch der Modellierungsaufwand, die Fehleranfälligkeit, die Laufzeit und der Interpretationsaufwand bei der Ergebnisauswertung. Fehler bei der Modellbildung führen bei der Simulation zu Fehlinterpretationen und falschen Ergebnissen. Einen wesentlichen Anteil daran hat die Gestaltung der Benutzungsschnittstelle: Das übliche, wenig intuitive WIMP-Interface (Windows, Icons, Mouse, Pointer) erfordert sehr gut geschulte Benutzer, sodass die Erzeugung der meist komplexen Simulationsmodelle mit großen Zeitaufwand verbunden ist. Die Präsentation der Simulationsergebnisse erfolgt in Form von Wertetabellen und zweidimensionalen, abstrakten Darstellungen des Fertigungssystems. Für die Simulationsexperten erscheint dies ausreichend, für ein aus verschiedenen Bereichen und Disziplinen zusammengesetztes Planungsteam ist das aber nicht akzeptabel. So können Fehlinterpretationen aufgrund der unklaren Darstellungen auftreten. Durch eine durchgängige Unterstützung von der Modellierung über die Ausführung bis zur Analyse von Simulationen durch Augmented-Reality und Virtual-Reality werden viele dieser Probleme überwunden aber viele neue Probleme entstehen. Marktgängige Simulatoren unterstützen zwar z.T. schon Virtual Reality; eine durchgängige Simulationsunterstützung wird aber in der Virtuellen Umgebung nicht geboten. Argumented Reality-Komponenten sind bisher nicht bekannt. In diesem Artikel werden nach einer Analyse der benötigten Technologien die Nutzenpotentiale insb. durch den Einsatz von AR ausgelotet.

Simulation und Visualisierung sind anerkannte Mittel zum Verstehen und Analysieren von Fertigungsprozessen. In Visualisierungen von Fertigungsprozessen können Betrachter frei und ungeleitet umherwandern. Erkenntnisse werden so aber eher zufällig erworben. Dieser Artikel skizziert ein System und Methoden, die den Betrachter unterstützen auf auffällige/signifikante Prozesse/ Punkte in Materialflusssimulationen aufmerksam zu werden und diese zu entschärfen. Es wird der Entwurf eines Werkzeugs beschrieben, dass den Betrachter einer Simulation die Möglichkeit bietet, signifikante Produktionsprozesse interaktiv zu verbessern. Der Benutzer wird sich in einer virtuellen 3D-Umgebung (Walkthrough-System) bewegen können und automatisch ermittelte Indizien für signifikante Abläufe erhalten. Zugleich soll die Simulation signifikante Objekte genauer simulieren. Bekundet der Benutzer Interesse an einem signifikanten Prozess, wird er automatisch zu dem jeweiligen Ort geführt werden und dort durch Eingriffe in die Simulation die kritische Situation experimentell untersuchen können. Da der kritische Moment in der Vergangenheit liegt und somit vom Betrachter schon verpasst ist, wird es dem Betrachter möglich sein, die Simulation auf einen Zeitpunkt vor dem Eintreten zurück zu setzen. Die virtuelle Szene (3D-Grafik-Modelle) einer typischen dynamischen Simulationsumgebung ist in der Regel zu komplex, um sie in Echtzeit in einem Walkthrough-System zu visualisieren und darzustellen. Typischerweise werden Approximationsverfahren eingesetzt, um die Komplexität zu reduzieren und ein flüssiges Navigieren des Betrachters zu erlauben. Durch spezifische Simulations-Anforderungen ist bekannt, an welchen Objekten des Simulationsmodells Probleme auftreten; sie sind für den Betrachter wichtig. Die zugehörigen virtuellen 3D-Repräsentanten, können von den Approximationsalgorithmen mit einer besonders hohen Darstellungsqualität dargestellt werden und die übrigen Teile der virtuellen Szene entsprechend vernachlässigt werden. Solche Approximationsalgorithmen und Datenstrukturen nutzen die spezifischen Eigenschaften virtueller Simulationsumgebungen aus, um eine hohe Darstellungsqualität und Darstellungsperformance zu erreichen.

In der heutigen Zeit operieren Unternehmen zunehmend in einem schwierigen Umfeld: Die Innovationsdynamik nimmt zu und die Produktlebenszyklen werden kürzer. Daraus resultieren hohe Anforderungen an die Planung von Fertigungssysteme. Um diesen Prozess zu unterstützen, sollen die Technologien Augmented Reality und Virtual Reality in einem integrierten System genutzt werden. Dieses System unterstützt den Anwender bei der Modellbildung, der Validierung des Simulationsmodells sowie der folgenden Optimierung des Fertigungssystems. Durch die Entwicklung geeigneter Kopplungs- bzw. Integrationsmechanismen wird eine durchgängige Nutzung der Technologien AR, VR und Simulation realisiert. Die Visualisierung der anfallenden 3D-Daten innerhalb der VR- und ARUmgebungen erfolgt mittels einer 3D-Renderinglibrary, die es durch den Einsatz von neuen entwickelten Verfahren ermöglicht, die verwendeten 3D-Modelle weitgehend automatisiert aus unternehmensinternen 3D-CAD-Modellen zu generieren.

Visualising is a method used to help experiencing and understanding causal cohesions in simulation processes. For this purpose, tools for visualising are already implemented in prevalent simulation systems. The user creates his simulation model and generates a 3-dimensional (2,5-dimensional) visualising by means of the simulation system. This helps examining the process which makes it easier for the viewer to “understand” it. Simulation tools usually only provide the opportunity for a unidirectional visualising. In a 3-dimensional surrounding the viewer can not implement an interaction with the simulation while the system is running. Though an interaction during the simulation run enables the user to gain a better understanding of causal cohesions. Solutions via HLA are sophisticated and therefore rather suited for extensive projects. We present a distributed system consisting of a commercial manufacturing simulation tool, a coupling module and a walkthrough system. The distributed system in conjunctions with the coupling module guarantees generality and a wide field of applications of the walkthrough system. Further it guarantees flexibility and selection of the specialized graphics hardware for the walkthrough system. A further contribution of this paper is the solution of the time synchronisation problem caused by simulation tool and walkthrough system.

We present a new data structure for rendering highly complex virtual environments of arbitrary topology. The special feature of our approach is that it allows an interactive navigation in very large scenes (30 GB/400 million polygons in our benchmark scenes) that cannot be stored in main memory, but only on a local or remote hard disk. Furthermore, it allows interactive rendering of substantially more complex scenes by instantiating objects. For the computation of an approximate image of the scene, a sampling technique is used. In the preprocessing, a so-called sample tree is built whose nodes contain randomly selected polygons from the scene. This tree only uses space that is linear in the number of polygons. In order to produce an image of the scene, the tree is traversed and polygons stored in the visited nodes are rendered. During the interactive walkthrough, parts of the sample tree are loaded from local or remote hard disk. We implemented our algorithm in a prototypical walkthrough system. Analysis and experiments show that the quality of our images is comparable to images computed by the conventional z-buffer algorithm regardless of the scene topology.

We present a new approximate occlusion-culling algorithm that in contrast to other algorithms, manages the objects of the scene in a 3D-sectorgraph. For generating a frame, as far as possible only the visible objects are rendered that can be found quickly by an edge of the graph. The algorithm allows a real-time navigation with over 20 frames per second in complex scenes consisting of over 10 millions of polygons. Moreover, approximation errors are very low.

We present a new output-sensitive rendering algorithm, the randomized z-buffer algorithm. It renders an image of an arbitrary three-dimensional scene consisting of triangular primitives by reconstruction from a dynamically chosen set of random surface sample points. This approach is independent of mesh connectivity and topology. The resulting rendering time grows only logarithmically with the numbers of triangles in the scene. We were able to render walkthroughs of scenes of up to 10^14 triangles at interactive frame rates. Automatic identification of low detail scene components ensures that the rendering speed of the randomized z-buffer cannot drop below that of conventional z-buffer rendering. Experimental and analytical evidence is given that the image quality is comparable to that of common approaches like z-buffer rendering. The precomputed data structures employed by the randomized z-buffer allow for interactive dynamic updates of the scene. Their memory requirements grow only linearly with the number of triangles and allow for a scene graph based instantiation scheme to further reduce memory consumption.

A geometric spanner with vertex set P in Rd is a sparse approximation of the complete Euclidean graph determined by P. We introduce the notion of partitioned neighborhood graphs (PNGs), unifying and generalizing most constructions of spanners treated in literature. Two important parameters characterizing their properties are the outdegree k in N and the stretch factor f>1 describing the “quality” of approximation. PNGs have been throughly investigated with respect to small values of f. We present in this work results about small values of k. The aim of minimizing k rather than f arises from two observations: * k determines the amount of space required for storing PNGs. * Many algorithms employing a (previously constructed) spanner have running times depending on its outdegree. Our results include, for fixed dimensions d as well as asymptotically, upper and lower bounds on this optimal value of k. The upper bounds are shown constructively and yield efficient algorithms for actually computing the corresponding PNGs even in degenerate cases.

New dynamic search data structures developed recently guarantee constant execution time per search and update, i.e., they fulfil the real-time requirements necessary for interactive walkthrough in large geometric scenes. Yet, superiority or even applicability of these new methods in practice was still an open question. Their prototypical implementation presented in this work uses common libraries on standard stations and thus represents a first strut to bridge this gap. Indeed our experimental results give an indication on the actual performance of these theoretical ideas on real machines and possible bottlenecks in future developments. By special algorithmic enhancements, we can even avoid the otherwise essential preprocessing step.

We present a data structure problem which describes the requirements of a simple variant of fully dynamic walk-through animation: We assume the scene to consist of unit size balls in R2 or higher dimensions. The scene may be arbitrarily large and has to be stored in secondary memory (discs) with relatively slow access. We allow a visitor to walk in the scene, and a modeler to update the scene by insertions and deletions of balls. We focus on the realtime requirement of animation systems: For some t (specified by the computation power of (the rendering hardware of) the graphic workstation) the data structure has to guarantee that the balls within distance t of the current visitor's position are presented to the rendering hardware, 20 times per second. Insertions and deletions should also be available to the visitor with small delay, independent of the size of the scene. We present a data structure that fulfills the above task in realtime. Its runtime is output-sensitive, i.e. linear in a quantity close to the output size of the query. We further present (preliminary) experimental results indicating that our structure is efficient in practice.

In this paper we develop a model for communication time on parallel computers consisting of processors and a service network, i.e., a network performing services like broadcast, synchronization, and global variables. The implementation of the service network is done on a free configurable Transputer network. Our cost model describes the communication time of accesses to global variables and consists of a multi-linear function. The cost model includes the parameters packet size, send hot spot, and the number of processors accessing global variables. These parameters influence the communication time in a high degree and capture important parameters like contention. We implement a Bitonic Sort and a Connected Components algorithm (among others) and we show that our model is able to predict the communication time within a 10% error if indirect service networks are used. The applications show that it is easy for a programmer to determine the parameter values for our model and that our new cost model precisely predicts the communication time of parallel algorithms. Furthermore, we minimize the communication time of accesses to global variables by finding a balance between the number of messages in the network and their size. Our model predicts the optimal values for these parameters which we validate by experiments. A modified implementation of our routing which determines on-line the optimal parameter values for an access to a global variable achieves good speed ups.