Please use this identifier to cite or link to this item: http://doi.org/10.25358/openscience-5191
Authors: Werth, Kai
Title: Packing a trunk : a physically based approach with full motional freedom
Online publication date: 7-Oct-2020
Year of first publication: 2013
Language: english
Abstract: Geometric packing problems may be formulated mathematically as constrained optimization problems. But finding a good solution is a challenging task. The more complicated the geometry of the container or the objects to be packed, the more complex the non-penetration constraints become. In this work we propose the use of a physics engine that simulates a system of colliding rigid bodies. It is a tool to resolve interpenetration conflicts and to optimize configurations locally. We develop an efficient and easy-to-implement physics engine that is specialized for collision detection and contact handling. In succession of the development of this engine a number of novel algorithms for distance calculation and intersection volume were designed and imple- mented, which are presented in this work. They are highly specialized to pro- vide fast responses for cuboids and triangles as input geometry whereas the concepts they are based on can easily be extended to other convex shapes. Especially noteworthy in this context is our ε-distance algorithm - a novel application that is not only very robust and fast but also compact in its im- plementation. Several state-of-the-art third party implementations are being presented and we show that our implementations beat them in runtime and robustness. The packing algorithm that lies on top of the physics engine is a Monte Carlo based approach implemented for packing cuboids into a container described by a triangle soup. We give an implementation for the SAE J1100 variant of the trunk packing problem. We compare this implementation to several established approaches and we show that it gives better results in faster time than these existing implementations.
Geometrische Packprobleme lassen sich mathematisch formulieren als Opti- mierungsprobleme mit Nebenbedingungen. Jedoch das Finden einer guten Lösung ist eine große Herausforderung. Je komplizierter die Geometrie des Containers oder der zu packenden Objekte ist, umso komplexer werden die Zwangsbedingungen für Überschneidungsfreiheit. In dieser Arbeit schlagen wir die Verwendung einer Physics-Engine vor, die ein System von kollidierenden Starrkörpern simuliert. Dieses Werkzeug löst Überschneidungen auf und optimiert eine Konfiguration lokal. Wir entwickeln eine effiziente und leicht nachzubauende Physics-Engine welche spezialisiert ist auf Kollisionserkennung und Kollisionsbehandlung. Infolge der Entwicklung dieser Engine wurden eine Reihe neuartiger Algo- rithmen zur Berechnung von euklidischem Abstand und Schnittvolumen ent- worfen und implementiert, welche in dieser Arbeit präsentiert werden. Sie sind hochspezialisiert um schnelle Antwortzeiten für Quader und Dreiecke zu liefern, wobei sich die verwendeten Konzepts ohne Weiteres auch für andere konvexe Objekte erweitern lassen. Erwähnenswert in diesem Kontext ist unser ε-Abstandsalgorithmus, ein neuartiges Werkzeug, welches sowohl sehr robust arbeitet als auch kompakt zu implementieren ist. Wir präsentieren einige anerkannte Drittimplementierungen und zeigen auf, daß unsere Imple- mentierungen diese schlagen in Laufzeit und Robustheit. Der Packalgorithmus welcher auf der Physics-Engine aufsetzt, ist ein Monte Carlo-basierter Ansatz für Quader in einem Container, der durch Dreiecke beschrieben ist. Wir beschreiben eine Implementierung für die SAE-J1100 Variante des Kofferraumpackproblems. Wir vergleichen diese Implementierung mit einer Reihe bereits bestehender Ansätze und zeigen auf, daß sie bessere Resultate in kürzerer Zeit liefert als diese existierenden Ansätze.
DDC: 004 Informatik
004 Data processing
Department: FB 08 Physik, Mathematik u. Informatik
ROR: https://ror.org/023b0x485
DOI: http://doi.org/10.25358/openscience-5191
URN: urn:nbn:de:hebis:77-33488
Version: Original work
Publication type: Dissertation
License: In Copyright
Information on rights of use: https://rightsstatements.org/vocab/InC/1.0/
Extent: 87 S.
Publisher: Johannes Gutenberg-Universität
Publisher place: Mainz
Issue date: 2013
Appears in collections:JGU-Publikationen

Files in This Item:
  File Description SizeFormat
Thumbnail
werth_kai-packing_a_trun-20201014105145058.pdf3.97 MBAdobe PDFView/Open