Sie haben Javascript deaktiviert!
Sie haben versucht eine Funktion zu nutzen, die nur mit Javascript möglich ist. Um sämtliche Funktionalitäten unserer Internetseite zu nutzen, aktivieren Sie bitte Javascript in Ihrem Browser.

#### Dr. Matthias Fischer

Kontakt
Publikationen

Wissenschaftlicher Mitarbeiter

Telefon:
+49 5251 60-6466
Fax:
+49 5251 60-6482
Büro:
F1.223
Web:
Besucher:
Fürstenallee 11

Liste im Research Information System öffnen

## 2020

Gathering Anonymous, Oblivious Robots on a Grid

J. Castenow, M. Fischer, J. Harbig, D. Jung, F. Meyer auf der Heide, Theoretical Computer Science (2020), 815, pp. 289-309

## 2019

Visibility‐Aware Progressive Farthest Point Sampling on the GPU

S. Brandt, C. Jähn, M. Fischer, F. Meyer auf der Heide, Computer Graphics Forum (2019), 38(7), pp. 413-424

Rendering of Complex Heterogenous Scenes using Progressive Blue Surfels

S. Brandt, C. Jähn, M. Fischer, F. Meyer auf der Heide, in: arXiv:1904.08225, 2019

We present a technique for rendering highly complex 3D scenes in real-time by generating uniformly distributed points on the scene's visible surfaces. The technique is applicable to a wide range of scene types, like scenes directly based on complex and detailed CAD data consisting of billions of polygons (in contrast to scenes handcrafted solely for visualization). This allows to visualize such scenes smoothly even in VR on a HMD with good image quality, while maintaining the necessary frame-rates. In contrast to other point based rendering methods, we place points in an approximated blue noise distribution only on visible surfaces and store them in a highly GPU efficient data structure, allowing to progressively refine the number of rendered points to maximize the image quality for a given target frame rate. Our evaluation shows that scenes consisting of a high amount of polygons can be rendered with interactive frame rates with good visual quality on standard hardware.

## 2017

Automatic Derivation of Geometric Properties of Components from 3D Polygon Models

S. Brandt, C. Jähn, M. Fischer, M. Gerges, J. Berssenbrügge, in: Proceedings of the ASME 2017 International Design Engineering Technical Conferences & Computers and Information in Engineering Conference, Band 1, ASME, 2017, pp. 91:1-91:10

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.

Gathering Anonymous, Oblivious Robots on a Grid

M. Fischer, D. Jung, F. Meyer auf der Heide, in: arXiv:1702.03400, 2017

We consider a swarm of $n$ autonomous mobile robots, distributed on a 2-dimensional grid. A basic task for such a swarm is the gathering process: All robots have to gather at one (not predefined) place. A common local model for extremely simple robots is the following: The robots do not have a common compass, only have a constant viewing radius, are autonomous and indistinguishable, can move at most a constant distance in each step, cannot communicate, are oblivious and do not have flags or states. The only gathering algorithm under this robot model, with known runtime bounds, needs $\mathcal{O}(n^2)$ rounds and works in the Euclidean plane. The underlying time model for the algorithm is the fully synchronous $\mathcal{FSYNC}$ model. On the other side, in the case of the 2-dimensional grid, the only known gathering algorithms for the same time and a similar local model additionally require a constant memory, states and "flags" to communicate these states to neighbors in viewing range. They gather in time $\mathcal{O}(n)$. In this paper we contribute the (to the best of our knowledge) first gathering algorithm on the grid that works under the same simple local model as the above mentioned Euclidean plane strategy, i.e., without memory (oblivious), "flags" and states. We prove its correctness and an $\mathcal{O}(n^2)$ time bound in the fully synchronous $\mathcal{FSYNC}$ time model. This time bound matches the time bound of the best known algorithm for the Euclidean plane mentioned above. We say gathering is done if all robots are located within a $2\times 2$ square, because in $\mathcal{FSYNC}$ such configurations cannot be solved.

Automatic Derivation of Geometric Properties of Components From 3D Polygon Models

S. Brandt, M. Fischer, M. Gerges, C. Jähn, J. Berssenbrügge, in: Volume 1: 37th Computers and Information in Engineering Conference, 2017, pp. 91:1-91:10

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.

Automatische Ableitung der Transportwege von Transportsystemen aus dem 3D-Polygonmodell

S. Brandt, M. Fischer, in: Wissenschaftsforum Intelligente Technische Systeme (WInTeSys) 2017, Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn, 2017, pp. 415-427

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.

Gathering Anonymous, Oblivious Robots on a Grid

M. Fischer, D. Jung, F. Meyer auf der Heide, in: Algorithms for Sensor Systems - 13th International Symposium on Algorithms and Experiments for Wireless Sensor Networks, {ALGOSENSORS}, Springer, 2017, pp. 168-181

## 2016

Asymptotically Optimal Gathering on a Grid

A.. Cord-Landwehr, M. Fischer, D. Jung, F. Meyer auf der Heide, in: arXiv:1602.03303, 2016

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 $\mathcal{O}(n)$ in the fully synchronous $\mathcal{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 $2\times 2$-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 $L_1$-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 \emph{merged} to be only one robot. The locality constraint is the significant challenging issue here, since robot movements 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 connectivity. In our model, robots can obtain a special state, which marks such a robot to be performing specific connectivity preserving movements in order to allow later merge operations of the swarm. Compared to the grid, for gathering in the Euclidean plane for the same robot and time model the best known upper bound is $\mathcal{O}(n^2)$.

Algorithm Engineering Aspects of Real-Time Rendering Algorithms

M. Fischer, C. Jähn, F. Meyer auf der Heide, R. Petring, in: Algorithm Engineering, Springer, 2016, pp. 226-244

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.

Asymptotically Optimal Gathering on a Grid

A. Cord-Landwehr, M. Fischer, D. Jung, F. Meyer auf der Heide, in: Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), ACM, 2016, pp. 301-312

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

Gathering a Closed Chain of Robots on a Grid

S. Abshoff, A. Cord-Landwehr, M. Fischer, D. Jung, F. Meyer auf der Heide, in: Proceedings of the 30th International Parallel and Distributed Processing Symposium (IPDPS), IEEE, 2016, pp. 689-699

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.

## 2015

Anbindung des Virtuellen Prototypen an die Partialmodelle intelligenter technischer Systeme

J. Berssenbrügge, O. Wiederkehr, C. Jähn, M. Fischer, in: 12. Paderborner Workshop Augmented & Virtual Reality in der Produktentstehung, Band 342 , Verlagsschriftenreihe des Heinz Nixdorf Instituts, 2015, pp. 65-78

Automatische Ableitung geometrischer Eigenschaften von Bauteilen aus dem 3-D-Polygonmodell

C. Jähn, M. Fischer, M. Gerges, J. Berssenbrügge, in: 12. Paderborner Workshop Augmented & Virtual Reality in der Produktentstehung, Band 342, Verlagsschriftenreihe des Heinz Nixdorf Instituts, 2015, pp. 107-120

Anbindung des Virtuellen Prototypen an die Partialmodelle intelligenter technischer Systeme

J.. Berssenbrügge, O. Wiederkehr, C. Jähn, M. Fischer, in: 12. Paderborner Workshop Augmented & Virtual Reality in der Produktentstehung, Verlagsschriftenreihe des Heinz Nixdorf Instituts, 2015, pp. 65-78

Automatische Ableitung geometrischer Eigenschaften von Bauteilen aus dem 3-D-Polygonmodell

C. Jähn, M. Fischer, M. Gerges, J. Berssenbrügge, in: 12. Paderborner Workshop Augmented & Virtual Reality in der Produktentstehung, Verlagsschriftenreihe des Heinz Nixdorf Instituts, 2015, pp. 107-120

Anbindung des Virtuellen Prototypen an die Partialmodelle intelligenter technischer Systeme

J. Berssenbrügge, O. Wiederkehr, C. Jähn, M. Fischer, in: 12. Paderborner Workshop Augmented & Virtual Reality in der Produktentstehung, Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn, 2015, pp. 65-78

Gathering a Closed Chain of Robots on a Grid

S. Abshoff, A.. Cord-Landwehr, M. Fischer, D. Jung, F. Meyer auf der Heide, in: arXiv:1510.05454, 2015

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\times 2$ subgrid. Our model is completely local (no global control, no global coordinates, no compass, no global communication or vision, \ldots). Each robot can only see its next constant number of left and right neighbors on the chain. This fixed constant is called the \emph{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 $\mathcal{FSYNC}$ model. For this problem, we present a gathering algorithm which needs linear time. This result generalizes the result from \cite{hopper}, where an open chain with specified distinguishable (and fixed) endpoints is considered.

## 2013

Darstellung heterogener 3-D-Szenen in Echtzeit

R. Petring, B. Eikel, C. Jähn, M. Fischer, F. Meyer auf der Heide, in: 11. Paderborner Workshop Augmented & Virtual Reality in der Produktentstehung, 2013, pp. 49--60

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.

Spherical Visibility Sampling

B. Eikel, C. Jähn, M. Fischer, F. Meyer auf der Heide, in: Computer Graphics Forum, 2013, pp. 49-58

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.

Evaluation of Rendering Algorithms Using Position-Dependent Scene Properties

C. Jähn, B. Eikel, M. Fischer, R. Petring, F. Meyer auf der Heide, in: Advances in Visual Computing, 2013

In order to evaluate the efficiency of algorithms for real-time 3D rendering, different properties like rendering time, occluded triangles, or image quality, need to be investigated. Since these properties depend on the position of the camera, usually some camera path is chosen, along which the measurements are performed. As those measurements cover only a small part of the scene, this approach hardly allows drawing conclusions regarding the algorithm's properties at arbitrary positions in the scene. The presented method allows the systematic and position-independent evaluation of rendering algorithms. It uses an adaptive sampling approach to approximate the distribution of a property (like rendering time) for all positions in the scene. This approximation can be visualized to produce an intuitive impression of the algorithm's behavior or be statistically analyzed for objectively rating and comparing algorithms. We demonstrate our method by evaluating performance aspects of a known occlusion culling algorithm.

Real-Time 3D Rendering of Heterogeneous Scenes

R. Petring, B. Eikel, C. Jähn, M. Fischer, F. Meyer auf der Heide, in: Advances in Visual Computing, 2013

Many virtual 3D scenes, especially those that are large, are not structured evenly. For such heterogeneous data, there is no single algorithm that is able to render every scene type at each position fast and with the same high image quality. For a small set of scenes, this situation can be improved if different rendering algorithms are manually assigned to particular parts of the scene by an experienced user. We introduce the Multi-Algorithm-Rendering method. It automatically deploys different rendering algorithms simultaneously for a broad range of scene types. The method divides the scene into subregions and measures the behavior of different algorithms for each region in a preprocessing step. During runtime, this data is utilized to compute an estimate for the quality and running time of the available rendering algorithms from the observer's point of view. By solving an optimizing problem, the image quality can be optimized by an assignment of algorithms to regions while keeping the frame rate almost constant.

## 2012

Asynchronous Occlusion Culling on Heterogeneous PC Clusters for Distributed 3D Scenes

T. Suess, C. Koch, C. Jähn, M. Fischer, F. Meyer auf der Heide, in: Advances in Visual Computing, 2012, pp. 502-512

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.

## 2011

Approximative occlusion culling using the hull tree

T. Suess, C. Koch, C. Jähn, M. Fischer, in: Proceedings of the Graphics Interface 2011 Conference, May 25-27, St. John's, Newfoundland, Canada, Canadian Human-Computer Communications Society, 2011, pp. 79--86

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.

Simulation aided, knowledge based routing for AGVs in a distribution warehouse

A. Klaas, C. Laroque, W. Dangelmaier, M. Fischer, in: Proceedings of the 2011 Winter Simulation Conference (WSC), 2011

Ein paralleles Out-of-Core Renderingsystem für Standard-Rechnernetze

T. Suess, C. Jähn, M. Fischer, F. Meyer auf der Heide, C. Koch, in: Augmented & Virtual Reality in der Produktentstehung, Verlagsschriftenreihe des Heinz Nixdorf Instituts, 2011, pp. 185--197

An Easy Extendable Modeling Framework for Discrete Event Simulation Models and their Visualization

H. Renken, C. Laroque, M. Fischer, in: Proceedings of The 25th European Simulation and Modelling Conference - ESM2011, 2011

Parallel Out-of-Core Occlusion Culling

T. Suess, C. Koch, C. Jähn, M. Fischer, F. Meyer auf der Heide, 2011

We present a parallel rendering system for PC-Clusters to visualize large 3D scenes. One single visualization node, equipped with a high-end graphics adapter, is supported by a group of backend nodes with weak graphics performance. The objects of the scene are distributed among these backend nodes, they serve two purposes: First, they provide an out-of-core memory system for the visualization node. Second, they assist the visualization node's rendering by performing visibility calculations and only sending visible objects to the visualization node. In order to obtain fast rendering with our system, we have to distribute the objects among the backend nodes in a way that does not only guarantee an even distribution of the objects, but also an even distribution of the visibility calculations and the amount of data send to the visualization node. We identify necessary properties of the distribution and argue that a random distribution is a good candidate. Further, in order to reduce the number of objects sent to the visualization node per frame, we employ an approximate hierarchical occlusion culling in each backend node. For this, they are equipped, in addition to the objects assigned to them, with simplified versions of the other objects of the 3D scene. The visualization node is equipped with 512 MiB video memory and supported by 15 backend nodes. This system is able to render a approx. 350 million polygons (approx. 8.5 GiB) large aircraft model between 20 - 30 fps and thus allows a walkthrough in real-time.

Collisionless Gathering of Robots with an Extent

A. Cord-Landwehr, B. Degener, M. Fischer, M. Hüllmann, B. Kempkes, A. Klaas, P. Kling, S. Kurras, M. Märtens, F. Meyer auf der Heide, C. Raupach, K. Swierkot, D. Warner, C. Weddemann, D. Wonisch, in: 37th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2011), Springer, 2011, pp. 178-189

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.

A New Approach for Analyzing Convergence Algorithms for Mobile Robots

A. Cord-Landwehr, B. Degener, M. Fischer, M. Hüllmann, B. Kempkes, A. Klaas, P. Kling, S. Kurras, M. Märtens, F. Meyer auf der Heide, C. Raupach, K. Swierkot, D. Warner, C. Weddemann, D. Wonisch, in: Automata, Languages and Programming, 2011

Given a set of n mobile robots in the d-dimensional Euclidean space, the goal is to let them converge to a single not predefined point. The challenge is that the robots are limited in their capabilities. Robots can, upon activation, compute the positions of all other robots using an individual affine coordinate system. The robots are indistinguishable, oblivious and may have different affine coordinate systems. A very general discrete time model assumes that robots are activated in arbitrary order. Further, the computation of a new target point may happen much earlier than the movement, so that the movement is based on outdated information about other robot's positions. Time is measured as the number of rounds, where a round ends as soon as each robot has moved at least once. In [Cohen, Peleg: Convergence properties of gravitational algorithms in asynchronous robot systems], the Center of Gravity is considered as target function, convergence was proven, and the number of rounds needed for halving the diameter of the convex hull of the robot's positions was shown to be O(n^2) and Omega(n). We present an easy-to-check property of target functions that guarantee convergence and yields upper time bounds. This property intuitively says that when a robot computes a new target point, this point is significantly within the current axes aligned minimal box containing all robots. This property holds, e.g., for the above-mentioned target function, and improves the above O(n^2) to an asymptotically optimal O(n) upper bound. Our technique also yields a constant time bound for a target function that requires all robots having identical coordinate axes.

An Easy Extendable Modeling Framework for Discrete Event Simulation Models and their Visualization

H. Renken, C. Laroque, M. Fischer, in: Proceedings of The 25th European Simulation and Modelling Conference - ESM2011, 2011

Simulation Aided, Knowledge Based Routing for AGVs in a Distribution Warehouse

A.. Klaas, C.. Laroque, M. Fischer, W. Dangelmaier, in: Proceedings of the 2011 Winter Simulation Conference, 2011

## 2010

Automated 3D-motion planning for ramps and stairs in intra-logistics material flow simulations

M. Fischer, H. Renken, C. Laroque, G. Schaumann, W. Dangelmaier, in: Proceedings of the 2010 Winter Simulation Conference, 2010

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.

Asynchronous Parallel Reliefboard Computation for Scene Object Approximation

M. Fischer, C. Jähn, T. Suess, in: Eurographics Symposium on Parallel Graphics and Visualization (EGPGV), The Eurographics Association, 2010, pp. 43-51

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.

T. Suess, T. Wiesemann, M. Fischer, in: 2010 IEEE Fifth International Conference on Networking, Architecture, and Storage, 2010, pp. 448 - 456

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.

Gewichtetes c-Collision-Protokoll zur Balancierung eines parallelen Out-of-Core-Renderingsystems

T. Suess, T. Wiesemann, M. Fischer, in: Augmented & Virtual Reality in der Produktentstehung, 2010, pp. 39-52

Typischerweise sind die Knoten eines PC-Clusters nicht mit leistungsfähigen Grafikkarten ausgestattet. Dennoch bieten Cluster-Betreiber einige wenige Rechenknoten an, die mit Highend-Grafikkarten ausgestattet sind, um beispielsweise eine PowerWall zu betreiben. Wenn zwischen diesen unterschiedlichen Knotentypen ein schnelles Netzwerk existiert, kann die Bilderzeugung durch die Knoten mit schwacher Grafikkarte beschleunigt werden. Dabei können die unterschiedlichen Knotentypen unterschiedliche Aufgabe bearbeiten. In einem solchen heterogenen System, müssen die unterschiedlichen entstehenden Lasten auf andere Weise verteilt werden, als in einem System, bei dem alle Knoten gleich ausgestattet sind. Wir präsentieren in dieser Arbeit Lastbalancierungsmechanismen, die in einem parallelen Out-of-Core-Renderingsystem für heterogene PC-Cluster eingesetzt werden.

Preprocessed Global Visibility for Real-Time Rendering on Low-End Hardware

B. Eikel, C. Jähn, M. Fischer, in: Advances in Visual Computing, 2010

We present an approach for real-time rendering of complex 3D scenes consisting of millions of polygons on limited graphics hardware. In a preprocessing step, powerful hardware is used to gain fine granular global visibility information of a scene using an adaptive sampling algorithm. Additively the visual influence of each object on the eventual rendered image is estimated. This influence is used to select the most important objects to display in our approximative culling algorithm. After the visibility data is compressed to meet the storage capabilities of small devices, we achieve an interactive walkthrough of the Power Plant scene on a standard netbook with an integrated graphics chipset.

## 2009

Concepts for Model Verification and Validation during Simulation Runtime

C. Laroque, M. Fischer, W. Dangelmaier, in: European Simulation and Modelling Conference (ESM 2009), EUROSIS-ETI, 2009

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.

Ein System zur aggregierten Visualisierung verteilter Materialflusssimulationen

T. Suess, M. Fischer, D. Huber, C.. Laroque, W. Dangelmaier, in: Augmented & Virtual Reality in der Produktentstehung, Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn, 2009, pp. 111--126

Planar Visibility Counting

M. Fischer, M. Hilbig, C. Jähn, F. Meyer auf der Heide, M. Ziegler, in: Proc. 25th European Workshop on Computational Geometry, 2009, pp. 203-206

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.

## 2008

A System for Aggregated Visualization of Multiple Parallel Discrete Event Simulations

T. Suess, D. Huber, M. Fischer, C. Laroque, W. Dangelmaier, in: IEEE International Symposium on Parallel and Distributed Processing with Applications, 2008

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.

Aggregated 3D-visualization of a distributed simulation experiment of a queuing system

W. Dangelmaier, M. Fischer, D. Huber, C. Laroque, T. Suess, in: 2008 Winter Simulation Conference, 2008, pp. 2012-2020

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.

Dynamic Control of Animation Schemes for the Efficient 3D-Visualization of Material Flow Simulations

C. Laroque, M. Fischer, W. Dangelmaier, B. Eikel, in: Industrial Simulation Conference (ISC 2008), EUROSIS-ETI, 2008, pp. 306-310

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.

Regelung von Animationen in Simulationen von hochdynamischen Fabrikszenen

C. Laroque, M. Fischer, B. Eikel, in: Augmented & Virtual Reality in der Produktentstehung, Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn, 2008, pp. 193--206

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.

Planar Visibility Counting

M. Fischer, M. Hilbig, C. Jähn, F. Meyer auf der Heide, M. Ziegler, in: arXiv:0810.0052, 2008

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.

## 2007

Interactive Refinement of a Material Flow Simulation Model by Comparing Multiple Simulation Runs in one 3D Environment

M. Fischer, C.. Laroque, D.. Huber, J.. Krokowski, B.. Mueck, M.. Kortenjan, M. Aufenanger, W. Dangelmaier, in: European Simulation and Modelling Conference (ESM 2007), 2007, pp. 499--505

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.

Ein ganzheitlicher Ansatz zur immersiven 3D-Materialflusssimulation innerhalb der Digitalen Fabrik

W. Dangelmaier, C.. Laroque, M. Fischer, in: Augmented & Virtual Reality in der Produktentstehung, Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn, 2007, pp. 95-110

Smart Teams: Simulating Large Robotic Swarms in Vast Environments

S. Arens, A. Buss, H. Deck, M. Dynia, M. Fischer, H. Hagedorn, P. Isaak, J. Kutylowski, F. Meyer auf der Heide, V. Nesterow, A. Ogiermann, B. Stobbe, T. Storm, H. Wachsmuth, in: Proceedings of the 4th International Symposium on Autonomous Minirobots for Research and Edutainment, Heinz Nixdorf Institut, University of Paderborn, 2007, pp. 215-222

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.

## 2006

d³FACT insight goes parallel - Aggregation of multiple simulations

W.. Dangelmaier, D.. Huber, C.. Laroque, M. Aufenanger, M. Fischer, J. Krokowski, M. Kortenjan, in: Simulation and Visualization 2006 (SimViS), SCS European Publishing House, 2006, pp. 79-88

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.

## 2005

Design, Analysis, and Evaluation of Data Structure for Distributed Virtual Environments

M. Fischer, Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn, 2005

Design, analysis, and evaluation of a data structure for distributed virtual environments

M. Fischer, Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn, 2005

Virtual and augmented reality support for discrete manufacturing system simulation

W. Dangelmaier, M. Fischer, J. Gausemeier, M. Grafe, C. Matysczok, B. Mueck, Computers in Industry (2005), pp. 371-383

Nowadays companies operate in a difficult environment: the dynamics of innovations increase and product life cycles become shorter. Furthermore products and the corresponding manufacturing processes get more and more complex. Therefore, companies need new methods for the planning of manufacturing systems. One promising approach in this context is digital factory/virtual productionthe modeling and analysis of computer models of the planned factory with the objective to reduce time and costs. For the modeling and analysis various simulation methods and programs have been developed. They are a highly valuable support for planning and visualizing the manufacturing system. But there is one major disadvantage: only experienced and long trained experts are able to operate with these programs. The graphical user interface is very complex and not intuitive to use. This results in an extensive and error-prone modeling of complex simulation models and a time-consuming interpretation of the simulation results. To overcome these weak points, intuitive and understandable manmachine interfaces like augmented and virtual reality can be used. This paper describes the architecture of a system which uses the technologies of augmented and virtual reality to support the planning process of complex manufacturing systems. The proposed system assists the user in modeling, the validation of the simulation model, and the subsequent optimization of the production system. A general application of the VR- and AR-technologies and of the simulation is realized by the development of appropriate linking and integration mechanisms. For the visualization of the arising 3D-data within the VR- and AR-environments, a dedicated 3D-rendering library is used.

Multi-User Support and Motion Planning of Humans and Humans Driven Vehicles in Interactive 3D Material Flow Simulations

M. Fischer, B. Mueck, K. Mahajan, M. Kortenjan, C. Laroque, W. Dangelmaier, in: Proceedings of the Winter Simulation Conference, 2005

Methods to lead the user to significant processes in a 3D material flow simulation

W. Dangelmaier, B. Mueck, M. Fischer, K. Mahajan, C. Laroque, in: Simulation in wider Europe - 19th European Conference on Modelling and Simulation ECMS 2005, 2005, pp. 267-270

## 2004

Guidance of Users in Interactive 3D-Visualisations of Material Flow Simulations

B. Mueck, W. Dangelmaier, C.. Laroque, M. Fischer, M. Kortenjan, in: Simulation and Visualisation 2004, SCS European Publishing House, 2004, pp. 73-83

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.

The Randomized Sample Tree: A Data Structure for Interactive Walk-Throughs in Externally Stored Virtual Environments

J. Klein, J. Krokowski, M. Fischer, M. Wand, R. Wanka, F. Meyer auf der Heide, Presence: Teleoperators and Virtual Environments (2004), pp. 617-637

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. The sampling process is done in the preprocessing. There, the polygons are randomly distributed in our hierarchical data structure, the randomized sample tree. This tree only uses space that is linear in the number of polygons. In order to produce an approximate 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.

## 2003

Components for the Active Support of the Analysis of Material Flow Simulations in a Virtual Environment

B. Mueck, W. Dangelmaier, M. Fischer, in: 15th European Simulation Symposium (ESS 2003), SCS - Europe, 2003, pp. 367-371

Virtual and Augmented Reality Support for Discrete Manufacturing System Simulation

M. Fischer, M. Grafe, C. Matysczok, B. Mueck, M. Schoo, in: Human Aspects in Production Management - Proceedings of the IFIP WG 5.7 Working Conference on Human Aspects in Production Management, Shaker Verlag, 2003, pp. 170-177

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.

Komponenten zur aktiven Unterstützung der Analyse von Materialflusssimulationen in virtuellen Umgebungen

W. Dangelmaier, W. Franke, B. Mueck, M. Fischer, in: 2. Paderborner Workshop Augmented & Virtual Reality in der Produktentstehung, 2003, pp. 141-151

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.

Planung von komplexen Fertigungssystemen durch Einsatz einer VR/AR-unterstützten Simulation

M. Fischer, M. Grafe, C. Matysczok, M. Schoo, B. Mueck, in: 2. Paderborner Workshop Augmented & Virtual Reality in der Produktentstehung, Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn, 2003, pp. 153-166

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.

## 2002

Bi-directional Coupling of Simulation Tools with a Walkthrough-System

B. Mueck, W. Dangelmaier, M. Fischer, W. Klemisch, in: Simulation und Visualisierung, SCS European Publishing House, 2002, pp. 71-84

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.

The randomized sample tree: a data structure for interactive walkthroughs in externally stored virtual environments

J. Klein, J. Krokowski, M. Fischer, M. Wand, R. Wanka, F. Meyer auf der Heide, in: Proceedings of the ACM symposium on Virtual reality software and technology - VRST '02, 2002

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.

## 2001

Occlusion Culling for Virtual Environments based on the 3D-Sectorgraph

J. Klein, M. Fischer, in: Proc. of 3. GI-Informatiktage 2001, 2001, pp. 275 - 278

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.

The randomized z-buffer algorithm

M. Wand, M. Fischer, I. Peter, F. Meyer auf der Heide, W. Straßer, in: Proceedings of the 28th annual conference on Computer graphics and interactive techniques - SIGGRAPH '01, 2001

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.

## 2000

Randomized Point Sampling for Output-Sensitive Rendering of Complex Dynamic Scenes

M. Wand, M. Fischer, F. Meyer auf der Heide, 2000

We present a new output-sensitive rendering algorithm, the randomized z-buffer algorithm. It renders an image of a three dimensional scene of triangular primitives by reconstruction from a random sample of surface points which are chosen with a probability proportional to the projected area of the objects. The approach is independent of mesh connectivity and topology. It leads to a rendering time that grows only logarithmically with the numbers of triangles in the scene and to linear memory consumption, thus allowing walkthroughs of scenes of extreme complexity. We consider different methods for image reconstruction which aim at correctness, rendering speed and image quality and we develop an efficient data structure for sample extraction in output-sensitive time which allows for efficient dynamic updates of the scene. Experiments confirm that scenes consisting of some hundred billion triangles can be rendered within seconds with an image quality comparable to a conventional z-buffer rendering; in special cases, realtime performance can be achieved.

## 1999

Partitioned neighborhood spanners of minimal outdegree

M. Fischer, T. Lukovszki, M. Ziegler, in: Proceedings of the 11th Canadian Conference on Computational Geometry, 1999

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.

## 1998

Geometric Searching in Walkthrough Animations with Weak Spanners in Real Time

M. Fischer, T. Lukovszki, M. Ziegler, in: Algorithms — ESA’ 98, 1998

We study algorithmic aspects in the management of geometric scenes in interactive walkthrough animations. We consider arbitrarily large scenes consisting of unit size balls. For a smooth navigation in the scene we have to fulfill hard real time requirements. Therefore, we need algorithms whose running time is independent of the total number of objects in the scene and that use as small space as possible. In this work we focus on one of the basic operations in our walkthrough system: reporting the objects around the visitor within a certain distance. Previously a randomized data structure was presented that supports reporting the balls around the visitor in an output sensitive time and allows insertion and deletion of objects nearly as fast as searching. These results were achieved by exploiting the fact that the visitor moves ''slowly'' through the scene. A serious disadvantage of the aforementioned data structure is a big space overhead and the use of randomization. Our first result is a construction of weak spanners that leads to an improvement of the space requirement of the previously known data structures. Then we develop a deterministic data structure for the searching problem in which insertion of objects are allowed. Our incremental data structure supports O(1+k) reporting time, where k is a certain quantity close to the number of reported objects. The insertion time is similar to the reporting time and the space is linear to the total number of objects.

A Network Based Approach for Realtime Walkthrough of Massive Models

M. Fischer, T. Lukovszki, M.. Ziegler, in: Algorithm Engineering, 2nd International Workshop, {WAE '98}, Max-Planck-Institut für Informatik, 1998, pp. 133--142

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.

Multimediale Entdeckungsreisen unserer Welt mit dem Internet

M. Ziegler, M. Fischer, T. Lukovszki, 1998

Preis für den Beitrag "Multimediale Entdeckungsreisen unserer Welt mit dem Internet"

## 1997

Dynamic data structures for realtime management of large geometric scenes

M. Fischer, F. Meyer auf der Heide, W. Strothmann, in: 5th Annual European Symposium on Algorithms (ESA '97), Springer, 1997, pp. 1157 - 170

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.

## 1996

A Realistic Cost Model for the Communication Time in Parallel Programs

M. Fischer, J. Rethmann, A. Wachsmann, in: 3rd Workshop on Abstract Machine Models for Parallel and Distributed Computing (AMW '96), IOS Press, 1996, pp. 13–27

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.

A Realistic Cost Model for the Communication Time in Parallel Programs on Parallel Computers Using a Service Hardware

M. Fischer, J. Rethmann, A. Wachsmann, 1996

In this report, we develop a cost model for the communication time on parallel computers consisting of processors and a service network, i.e., a network performing services like broadcast, synchronization, and global variables. Because we do not have a parallel computer at our disposal that is equipped with a service network, we emulate the service network on a reconfigurable 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 (the number of messages sent out by one processor), and number of processors accessing global variables. We show that these parameters influence the communication time in a high degree and capture important parameters like network contention. We implement a Bitonic Sort, Sample Sort, Matrix Multiplication, and Connected Components algorithm, 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 programer to determine the parameter values for our model and that our new cost model precisely predicts the communication time of parallel algorithms. We explore the interaction of hot spots and asynchrony and show that the influence of hot spots to the communication time is not as high as one would expect from theoretical considerations in a synchronous model. Therefore, we do not apprehend the hot spot in our cost model. 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.

Liste im Research Information System öffnen

Die Universität der Informationsgesellschaft