TY - JOUR AU - Castenow, Jannik AU - Fischer, Matthias AU - Harbig, Jonas AU - Jung, Daniel AU - Meyer auf der Heide, Friedhelm ID - 16299 JF - Theoretical Computer Science SN - 0304-3975 TI - Gathering Anonymous, Oblivious Robots on a Grid VL - 815 ER - TY - JOUR AU - Brandt, Sascha AU - Jähn, Claudius AU - Fischer, Matthias AU - Meyer auf der Heide, Friedhelm ID - 16337 IS - 7 JF - Computer Graphics Forum SN - 0167-7055 TI - Visibility‐Aware Progressive Farthest Point Sampling on the GPU VL - 38 ER - TY - GEN AB - 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. AU - Brandt, Sascha AU - Jähn, Claudius AU - Fischer, Matthias AU - Meyer auf der Heide, Friedhelm ID - 16341 T2 - arXiv:1904.08225 TI - Rendering of Complex Heterogenous Scenes using Progressive Blue Surfels ER - TY - CONF AB - 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. AU - Brandt, Sascha AU - Jähn, Claudius AU - Fischer, Matthias AU - Gerges, Maria AU - Berssenbrügge, Jan ID - 27403 T2 - Proceedings of the ASME 2017 International Design Engineering Technical Conferences & Computers and Information in Engineering Conference, Band 1 TI - Automatic Derivation of Geometric Properties of Components from 3D Polygon Models VL - 1 ER - TY - GEN AB - 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. AU - Fischer, Matthias AU - Jung, Daniel AU - Meyer auf der Heide, Friedhelm ID - 17811 T2 - arXiv:1702.03400 TI - Gathering Anonymous, Oblivious Robots on a Grid ER - TY - CONF AB - 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. AU - Brandt, Sascha AU - Fischer, Matthias AU - Gerges, Maria AU - Jähn, Claudius AU - Berssenbrügge, Jan ID - 16338 SN - 9780791858110 T2 - Volume 1: 37th Computers and Information in Engineering Conference TI - Automatic Derivation of Geometric Properties of Components From 3D Polygon Models VL - 1 ER - TY - CONF AB - 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. AU - Brandt, Sascha AU - Fischer, Matthias ID - 16339 T2 - Wissenschaftsforum Intelligente Technische Systeme (WInTeSys) 2017 TI - Automatische Ableitung der Transportwege von Transportsystemen aus dem 3D-Polygonmodell VL - 369 ER - TY - CONF AU - Fischer, Matthias AU - Jung, Daniel AU - Meyer auf der Heide, Friedhelm ED - Fernández Anta, Antonio ED - Jurdzinski, Tomasz ED - Mosteiro, Miguel A. ED - Zhang, Yanyong ID - 16347 T2 - Algorithms for Sensor Systems - 13th International Symposium on Algorithms and Experiments for Wireless Sensor Networks, {ALGOSENSORS} TI - Gathering Anonymous, Oblivious Robots on a Grid VL - 10718 ER - TY - GEN AB - 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)$. AU - Cord-Landwehr, Andreas AU - Fischer, Matthias AU - Jung, Daniel AU - Meyer auf der Heide, Friedhelm ID - 16450 T2 - arXiv:1602.03303 TI - Asymptotically Optimal Gathering on a Grid ER - TY - CONF AB - 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. AU - Fischer, Matthias AU - Jähn, Claudius AU - Meyer auf der Heide, Friedhelm AU - Petring, Ralf ED - Kliemann, Lasse ED - Sanders, Peter ID - 16351 T2 - Algorithm Engineering TI - Algorithm Engineering Aspects of Real-Time Rendering Algorithms VL - 9220 ER - TY - CONF AB - 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). AU - Cord-Landwehr, Andreas AU - Fischer, Matthias AU - Jung, Daniel AU - Meyer auf der Heide, Friedhelm ID - 16359 T2 - Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA) TI - Asymptotically Optimal Gathering on a Grid ER - TY - CONF AB - 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. AU - Abshoff, Sebastian AU - Cord-Landwehr, Andreas AU - Fischer, Matthias AU - Jung, Daniel AU - Meyer auf der Heide, Friedhelm ID - 16360 T2 - Proceedings of the 30th International Parallel and Distributed Processing Symposium (IPDPS) TI - Gathering a Closed Chain of Robots on a Grid ER - TY - CONF AU - Berssenbrügge, Jan AU - Wiederkehr, Olga AU - Jähn, Claudius AU - Fischer, Matthias ID - 28318 T2 - 12. Paderborner Workshop Augmented & Virtual Reality in der Produktentstehung, Band 342 TI - Anbindung des Virtuellen Prototypen an die Partialmodelle intelligenter technischer Systeme ER - TY - CONF AU - Jähn, Claudius AU - Fischer, Matthias AU - Gerges, Maria AU - Berssenbrügge, Jan ID - 28322 T2 - 12. Paderborner Workshop Augmented & Virtual Reality in der Produktentstehung, Band 342 TI - Automatische Ableitung geometrischer Eigenschaften von Bauteilen aus dem 3-D-Polygonmodell ER - TY - CONF AU - Berssenbrügge, Jan AU - Wiederkehr, Olga AU - Jähn, Claudius AU - Fischer, Matthias ID - 17425 T2 - 12. Paderborner Workshop Augmented & Virtual Reality in der Produktentstehung TI - Anbindung des Virtuellen Prototypen an die Partialmodelle intelligenter technischer Systeme VL - 343 ER - TY - CONF AU - Jähn, Claudius AU - Fischer, Matthias AU - Gerges, Maria AU - Berssenbrügge, Jan ID - 17427 T2 - 12. Paderborner Workshop Augmented & Virtual Reality in der Produktentstehung TI - Automatische Ableitung geometrischer Eigenschaften von Bauteilen aus dem 3-D-Polygonmodell VL - 342 ER - TY - CONF AU - Berssenbrügge, Jan AU - Wiederkehr, Olga AU - Jähn, Claudius AU - Fischer, Matthias ID - 23070 T2 - 12. Paderborner Workshop Augmented & Virtual Reality in der Produktentstehung TI - Anbindung des Virtuellen Prototypen an die Partialmodelle intelligenter technischer Systeme VL - 342 ER - TY - GEN AB - 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. AU - Abshoff, Sebastian AU - Cord-Landwehr, Andreas AU - Fischer, Matthias AU - Jung, Daniel AU - Meyer auf der Heide, Friedhelm ID - 16449 T2 - arXiv:1510.05454 TI - Gathering a Closed Chain of Robots on a Grid ER - TY - CONF AB - 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. AU - Petring, Ralf AU - Eikel, Benjamin AU - Jähn, Claudius AU - Fischer, Matthias AU - Meyer auf der Heide, Friedhelm ID - 17439 T2 - 11. Paderborner Workshop Augmented & Virtual Reality in der Produktentstehung TI - Darstellung heterogener 3-D-Szenen in Echtzeit VL - 311 ER - TY - CONF AB - 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. AU - Eikel, Benjamin AU - Jähn, Claudius AU - Fischer, Matthias AU - Meyer auf der Heide, Friedhelm ID - 16393 IS - 4 SN - 0167-7055 T2 - Computer Graphics Forum TI - Spherical Visibility Sampling VL - 32 ER -