Packing a trunk : a physically based approach with full motional freedom

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.

Modellierung von Porenraumgeometrien und Transport in korngestützten porösen Medien

Poröse Medien spielen in der Hydrosphäre eine wesentliche Rolle bei der Strömung und beim Transport von Stoffen. In diesem Raum finden komplexe Prozesse statt: Advektion, Kon-vektion, Diffusion, hydromechanische Dispersion, Sorption, Komplexierung, Ionenaustausch und Abbau. Die strömungsmechanischen- und die Transportverhältnisse in porösen Medien werden direkt durch die Geometrie des Porenraumes selbst und durch die Eigenschaften der transportierten (oder strömenden) Medien bestimmt. In der Praxis wird eine Vielzahl von empirischen Modellen verwendet, die die Eigenschaften des porösen Mediums in repräsentativen Elementarvolumen wiedergeben. Die Ermittlung der in empirischen Modellen verwendeten Materialparameter erfolgt über Labor- oder Feldbestimmungsmethoden. Im Rahmen dieser Arbeit wurde das Computer-modell PoreFlow entwickelt, welches die hydraulischen Eigenschaften eines korngestützten porösen Mediums aus der mikroskopischen Modellierung des Fluidflusses und Transportes ableitet. Das poröse Modellmedium wird durch ein dreidimensionales Kugelpackungsmodell, zusam-mengesetzt aus einer beliebigen Kornverteilung, dargestellt. Im Modellporenraum wird die Strömung eines Fluids basierend auf einer stationären Lösung der Navier-Stokes-Gleichung simuliert. Die Ergebnisse der Modellsimulationen an verschiedenen Modellmedien werden mit den Ergebnissen von Säulenversuchen verglichen. Es zeigt sich eine deutliche Abhängigkeit der Strömungs- und Transportparameter von der Porenraumgeometrie sowohl in den Modell-simulationen als auch in den Säulenexperimenten.

Dynamic distance analysis : new geometric data structures and algorithms for the real-time calculation of tolerance violating regions in the digital mockup process

In vielen Industriezweigen, zum Beispiel in der Automobilindustrie, werden Digitale Versuchsmodelle (Digital MockUps) eingesetzt, um die Konstruktion und die Funktion eines Produkts am virtuellen Prototypen zu überprüfen. Ein Anwendungsfall ist dabei die Überprüfung von Sicherheitsabständen einzelner Bauteile, die sogenannte Abstandsanalyse. Ingenieure ermitteln dabei für bestimmte Bauteile, ob diese in ihrer Ruhelage sowie während einer Bewegung einen vorgegeben Sicherheitsabstand zu den umgebenden Bauteilen einhalten. Unterschreiten Bauteile den Sicherheitsabstand, so muss deren Form oder Lage verändert werden. Dazu ist es wichtig, die Bereiche der Bauteile, welche den Sicherhabstand verletzen, genau zu kennen. rnrnIn dieser Arbeit präsentieren wir eine Lösung zur Echtzeitberechnung aller den Sicherheitsabstand unterschreitenden Bereiche zwischen zwei geometrischen Objekten. Die Objekte sind dabei jeweils als Menge von Primitiven (z.B. Dreiecken) gegeben. Für jeden Zeitpunkt, in dem eine Transformation auf eines der Objekte angewendet wird, berechnen wir die Menge aller den Sicherheitsabstand unterschreitenden Primitive und bezeichnen diese als die Menge aller toleranzverletzenden Primitive. Wir präsentieren in dieser Arbeit eine ganzheitliche Lösung, welche sich in die folgenden drei großen Themengebiete unterteilen lässt.rnrnIm ersten Teil dieser Arbeit untersuchen wir Algorithmen, die für zwei Dreiecke überprüfen, ob diese toleranzverletzend sind. Hierfür präsentieren wir verschiedene Ansätze für Dreiecks-Dreiecks Toleranztests und zeigen, dass spezielle Toleranztests deutlich performanter sind als bisher verwendete Abstandsberechnungen. Im Fokus unserer Arbeit steht dabei die Entwicklung eines neuartigen Toleranztests, welcher im Dualraum arbeitet. In all unseren Benchmarks zur Berechnung aller toleranzverletzenden Primitive beweist sich unser Ansatz im dualen Raum immer als der Performanteste.rnrnDer zweite Teil dieser Arbeit befasst sich mit Datenstrukturen und Algorithmen zur Echtzeitberechnung aller toleranzverletzenden Primitive zwischen zwei geometrischen Objekten. Wir entwickeln eine kombinierte Datenstruktur, die sich aus einer flachen hierarchischen Datenstruktur und mehreren Uniform Grids zusammensetzt. Um effiziente Laufzeiten zu gewährleisten ist es vor allem wichtig, den geforderten Sicherheitsabstand sinnvoll im Design der Datenstrukturen und der Anfragealgorithmen zu beachten. Wir präsentieren hierzu Lösungen, die die Menge der zu testenden Paare von Primitiven schnell bestimmen. Darüber hinaus entwickeln wir Strategien, wie Primitive als toleranzverletzend erkannt werden können, ohne einen aufwändigen Primitiv-Primitiv Toleranztest zu berechnen. In unseren Benchmarks zeigen wir, dass wir mit unseren Lösungen in der Lage sind, in Echtzeit alle toleranzverletzenden Primitive zwischen zwei komplexen geometrischen Objekten, bestehend aus jeweils vielen hunderttausend Primitiven, zu berechnen. rnrnIm dritten Teil präsentieren wir eine neuartige, speicheroptimierte Datenstruktur zur Verwaltung der Zellinhalte der zuvor verwendeten Uniform Grids. Wir bezeichnen diese Datenstruktur als Shrubs. Bisherige Ansätze zur Speicheroptimierung von Uniform Grids beziehen sich vor allem auf Hashing Methoden. Diese reduzieren aber nicht den Speicherverbrauch der Zellinhalte. In unserem Anwendungsfall haben benachbarte Zellen oft ähnliche Inhalte. Unser Ansatz ist in der Lage, den Speicherbedarf der Zellinhalte eines Uniform Grids, basierend auf den redundanten Zellinhalten, verlustlos auf ein fünftel der bisherigen Größe zu komprimieren und zur Laufzeit zu dekomprimieren.rnrnAbschießend zeigen wir, wie unsere Lösung zur Berechnung aller toleranzverletzenden Primitive Anwendung in der Praxis finden kann. Neben der reinen Abstandsanalyse zeigen wir Anwendungen für verschiedene Problemstellungen der Pfadplanung.

Use of computer algebra in the calculation of Feynman diagrams

The increasing precision of current and future experiments in high-energy physics requires a likewise increase in the accuracy of the calculation of theoretical predictions, in order to find evidence for possible deviations of the generally accepted Standard Model of elementary particles and interactions. Calculating the experimentally measurable cross sections of scattering and decay processes to a higher accuracy directly translates into including higher order radiative corrections in the calculation. The large number of particles and interactions in the full Standard Model results in an exponentially growing number of Feynman diagrams contributing to any given process in higher orders. Additionally, the appearance of multiple independent mass scales makes even the calculation of single diagrams non-trivial. For over two decades now, the only way to cope with these issues has been to rely on the assistance of computers. The aim of the xloops project is to provide the necessary tools to automate the calculation procedures as far as possible, including the generation of the contributing diagrams and the evaluation of the resulting Feynman integrals. The latter is based on the techniques developed in Mainz for solving one- and two-loop diagrams in a general and systematic way using parallel/orthogonal space methods. These techniques involve a considerable amount of symbolic computations. During the development of xloops it was found that conventional computer algebra systems were not a suitable implementation environment. For this reason, a new system called GiNaC has been created, which allows the development of large-scale symbolic applications in an object-oriented fashion within the C++ programming language. This system, which is now also in use for other projects besides xloops, is the main focus of this thesis. The implementation of GiNaC as a C++ library sets it apart from other algebraic systems. Our results prove that a highly efficient symbolic manipulator can be designed in an object-oriented way, and that having a very fine granularity of objects is also feasible. The xloops-related parts of this work consist of a new implementation, based on GiNaC, of functions for calculating one-loop Feynman integrals that already existed in the original xloops program, as well as the addition of supplementary modules belonging to the interface between the library of integral functions and the diagram generator.

On the geometry of the spin-statistics connection in quantum mechanics

The Spin-Statistics theorem states that the statistics of a system of identical particles is determined by their spin: Particles of integer spin are Bosons (i.e. obey Bose-Einstein statistics), whereas particles of half-integer spin are Fermions (i.e. obey Fermi-Dirac statistics). Since the original proof by Fierz and Pauli, it has been known that the connection between Spin and Statistics follows from the general principles of relativistic Quantum Field Theory. In spite of this, there are different approaches to Spin-Statistics and it is not clear whether the theorem holds under assumptions that are different, and even less restrictive, than the usual ones (e.g. Lorentz-covariance). Additionally, in Quantum Mechanics there is a deep relation between indistinguishabilty and the geometry of the configuration space. This is clearly illustrated by Gibbs' paradox. Therefore, for many years efforts have been made in order to find a geometric proof of the connection between Spin and Statistics. Recently, various proposals have been put forward, in which an attempt is made to derive the Spin-Statistics connection from assumptions different from the ones used in the relativistic, quantum field theoretic proofs. Among these, there is the one due to Berry and Robbins (BR), based on the postulation of a certain single-valuedness condition, that has caused a renewed interest in the problem. In the present thesis, we consider the problem of indistinguishability in Quantum Mechanics from a geometric-algebraic point of view. An approach is developed to study configuration spaces Q having a finite fundamental group, that allows us to describe different geometric structures of Q in terms of spaces of functions on the universal cover of Q. In particular, it is shown that the space of complex continuous functions over the universal cover of Q admits a decomposition into C(Q)-submodules, labelled by the irreducible representations of the fundamental group of Q, that can be interpreted as the spaces of sections of certain flat vector bundles over Q. With this technique, various results pertaining to the problem of quantum indistinguishability are reproduced in a clear and systematic way. Our method is also used in order to give a global formulation of the BR construction. As a result of this analysis, it is found that the single-valuedness condition of BR is inconsistent. Additionally, a proposal aiming at establishing the Fermi-Bose alternative, within our approach, is made.

Individual plasmonic nanogaps : controlled assembly and detailed investigation

Diese Arbeit befasst sich mit den optischen Resonanzen metallischer Nanopartikel im Abstand weniger Nanometer von einer metallischen Grenzfläche. Die elektromagnetische Wechselwirkung dieser „Kugel-vor-Fläche“ Geometrie ruft interessante optische Phänomene hervor. Sie erzeugt eine spezielle elektromagnetische Eigenmode, auch Spaltmode genannt, die im Wesentlichen auf den Nanospalt zwi-schen Kugel und Oberfläche lokalisiert ist. In der quasistatischen Näherung hängt die Resonanzposition nur vom Material, der Umgebung, dem Film-Kugel Abstand und dem Kugelradius selbst ab. Theoretische Berechnungen sagen für diese Region unter Resonanzbedingungen eine große Verstärkung des elektro-magnetischen Feldes voraus. rnUm die optischen Eigenschaften dieser Systeme zu untersuchen, wurde ein effizienter plasmonenver-mittelnder Dunkelfeldmodus für die konfokale Rastermikroskopie durch dünne Metallfilme entwickelt, der die Verstärkung durch Oberflächenplasmonen sowohl im Anregungs- als auch Emissionsprozess ausnutzt. Dadurch sind hochwertige Dunkelfeldaufnahmen durch die Metallfilme der Kugel-vor-Fläche Systeme garantiert, und die Spektroskopie einzelner Resonatoren wird erleichtert. Die optischen Untersuchungen werden durch eine Kombination von Rasterkraft- und Rasterelektronenmikroskopie vervollständigt, so dass die Form und Größe der untersuchten Resonatoren in allen drei Dimensionen bestimmt und mit den optischen Resonanzen korreliert werden können. Die Leistungsfähigkeit des neu entwickelten Modus wird für ein Referenzsystem aus Polystyrol-Kugeln auf einem Goldfilm demonstriert. Hierbei zeigen Partikel gleicher Größe auch die erwartete identische Resonanz.rnFür ein aus Gold bestehendes Kugel-vor-Fläche System, bei dem der Spalt durch eine selbstorganisierte Monolage von 2-Aminoethanthiol erzeugt wird, werden die Resonanzen von Goldpartikeln, die durch Reduktion mit Chlorgoldsäure erzeugt wurden, mit denen von idealen Goldkugeln verglichen. Diese ent-stehen aus den herkömmlichen Goldpartikeln durch zusätzliche Bestrahlung mit einem Pikosekunden Nd:Yag Laser. Bei den unbestrahlten Partikeln mit ihrer Unzahl an verschiedenen Formen zeigen nur ein Drittel der untersuchten Resonatoren ein Verhalten, das von der Theorie vorhergesagt wird, ohne das dies mit ihrer Form oder Größe korrelieren würde. Im Fall der bestrahlten Goldkugeln tritt eine spürbare Verbesserung ein, bei dem alle Resonatoren mit den theoretischen Rechnungen übereinstimmen. Eine Änderung der Oberflächenrauheit des Films zeigt hingegen keinen Einfluß auf die Resonanzen. Obwohl durch die Kombination von Goldkugeln und sehr glatten Metallfilmen eine sehr definierte Probengeometrie geschaffen wurde, sind die experimentell bestimmten Linienbreiten der Resonanzen immer noch wesentlich größer als die berechneten. Die Streuung der Daten, selbst für diese Proben, deutet auf weitere Faktoren hin, die die Spaltmoden beeinflußen, wie z.B. die genaue Form des Spalts. rnDie mit den Nanospalten verbundenen hohen Feldverstärkungen werden untersucht, indem ein mit Farbstoff beladenes Polyphenylen-Dendrimer in den Spalt eines aus Silber bestehenden Kugel-vor-Fläche Systems gebracht wird. Das Dendrimer in der Schale besteht lediglich aus Phenyl-Phenyl Bindungen und garantiert durch die damit einhergende Starrheit des Moleküls eine überragende Formstabiliät, ohne gleichzeitig optisch aktiv zu sein. Die 16 Dithiolan Endgruppen sorgen gleichzeitig für die notwendige Affinität zum Silber. Dadurch kann der im Inneren befindliche Farbstoff mit einer Präzision von wenigen Nanometern im Spalt zwischen den Metallstrukturen platziert werden. Der gewählte Perylen Farbstoff zeichnet sich wiederum durch hohe Photostabilität und Fluoreszenz-Quantenausbeute aus. Für alle untersuchten Partikel wird ein starkes Fluoreszenzsignal gefunden, das mindestens 1000-mal stärker ist, als das des mit Farbstoff überzogenen Metallfilms. Das Profil des Fluoreszenz-Anregungsspektrums variiert zwischen den Partikeln und zeigt im Vergleich zum freien Farbstoff eine zusätzliche Emission bei höheren Frequenzen, was in der Literatur als „hot luminescence“ bezeichnet wird. Bei der Untersuchung des Streuverhaltens der Resonatoren können wieder zwei unterschiedliche Arten von Resonatoren un-terschieden werden. Es gibt zunächst die Fälle, die bis auf die beschriebene Linienverbreiterung mit einer idealen Kugel-vor-Fläche Geometrie übereinstimmen und dann andere, die davon stark abweichen. Die Veränderungen der Fluoreszenz-Anregungsspektren für den gebundenen Farbstoffs weisen auf physikalische Mechanismen hin, die bei diesen kleinen Metall/Farbstoff Abständen eine Rolle spielen und die über eine einfache wellenlängenabhängige Verstärkung hinausgehen.