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.

Entwicklung und Test eines Röntgeninterferometers auf der Basis von Übergangsstrahlung

In der vorliegenden Arbeit werden Entwicklung und Test einesneuartigen Interferometers mit zwei örtlich separierten,phasenkorrelierten Röntgenquellen zur Messung des Realteilsdes komplexen Brechungsindex von dünnen, freitragendenFolien beschrieben. Die Röntgenquellen sind zwei Folien, indenen relativistische Elektronen der Energie 855 MeVÜbergangsstrahlung erzeugen. Das am Mainzer Mikrotron MAMIrealisierte Interferometer besteht aus einer Berylliumfolieeiner Dicke von 10 Mikrometer und einer Nickel-Probefolieeiner Dicke von 2.1 Mikrometer. Die räumlichenInterferenzstrukturen werden als Funktion desFolienabstandes in einer ortsauflösenden pn-CCD nach derFourier-Analyse des Strahlungsimpulses mittels einesSilizium-Einkristallspektrometers gemessen. Die Phase derIntensitätsoszillationen enthält Informationen über dieDispersion, die die in der strahlaufwärtigen Folie erzeugteWelle in der strahlabwärtigen Probefolie erfährt. AlsFallstudie wurde die Dispersion von Nickel im Bereich um dieK-Absorptionskane bei 8333 eV, sowie bei Photonenenergien um9930 eV gemessen. Bei beiden Energien wurden deutlicheInterferenzstrukturen nachgewiesen, wobei die Kohärenz wegenWinkelmischungen mit steigendem Folienabstand bzw.Beobachtungswinkel abnimmt. Es wurden Anpassungen vonSimulationsrechnungen an die Messdaten durchgeführt, die diekohärenzvermindernden Effekte berücksichtigen. Aus diesenAnpassungen konnte bei beiden untersuchten Energien dieDispersion der Nickelprobe mit einer relativen Genauigkeitvon kleiner gleich 1.5 % in guter Übereinstimmung mit derLiteratur bestimmt werden.

Test of Lorentz symmetry with a 3 He,129 Xe clock-comparison experiment

In case of violation of CPT- and Lorentz Symmetry, the minimal Standard Model Extension (SME) of Kostelecky and coworkers predicts sidereal modulations of atomic transition frequencies as the Earth rotates relative to a Lorentz-violating background field. One method to search for these modulations is the so-called clock-comparison experiment, where the frequencies of co-located clocks are compared as they rotate with respect to the fixed stars. In this work an experiment is presented where polarized 3He and 129Xe gas samples in a glass cell serve as clocks, whose nuclear spin precession frequencies are detected with the help of highly sensitive SQUID sensors inside a magnetically shielded room. The unique feature of this experiment is the fact that the spins are precessing freely, with transverse relaxation times of up to 4.4 h for 129Xe and 14.1 h for 3He. To be sensitive to Lorentz-violating effects, the influence of external magnetic fields is canceled via the weighted difference of the 3He and 129Xe frequencies or phases. The Lorentz-violating SME parameters for the neutron are determined out of a fit on the phase difference data of 7 spin precession measurements of 12 to 16 hours length. The result of the fit gives an upper limit for the equatorial component of the neutron parameter b_n of 3.7×10^(−32) GeV at the 95% confidence level. This value is not limited by the signal-to-noise ratio, but by the strong correlations between the fit parameters. To reduce the correlations and therewith improve the sensitivity of future experiments, it will be necessary to change the time structure of the weighted phase difference, which can be realized by increasing the 129Xe relaxation time.

Test der Speziellen Relativitätstheorie mittels Laserspektroskopie an relativistischen 7 Li +-Ionen am ESR

Die Invarianz physikalischer Gesetze unter Lorentztransformationen ist eines der fundamentalen Postulate der modernen Physik und alle Theorien der grundlegenden Wechselwirkungen sind in kovarianter Form formuliert. Obwohl die Spezielle Relativitätstheorie (SRT) in einer Vielzahl von Experimenten mit hoher Genauigkeit überprüft und bestätigt wurde, sind aufgrund der weitreichenden Bedeutung dieses Postulats weitere verbesserte Tests von grundsätzlichem Interesse. Darüber hinaus weisen moderne Ansätze zur Vereinheitlichung der Gravitation mit den anderen Wechselwirkungen auf eine mögliche Verletzung der Lorentzinvarianz hin. In diesem Zusammenhang spielen Ives-Stilwell Experimente zum Test der Zeitdilatation in der SRT eine bedeutende Rolle. Dabei wird die hochauflösende Laserspektroskopie eingesetzt, um die Gültigkeit der relativistischen Dopplerformel – und damit des Zeitdilatationsfaktors γ – an relativistischen Teilchenstrahlen zu untersuchen. Im Rahmen dieser Arbeit wurde ein Ives-Stilwell Experiment an 7Li+-Ionen, die bei einer Geschwindigkeit von 34 % der Lichtgeschwindigkeit im Experimentierspeicherring (ESR) des GSI Helmholtzzentrums für Schwerionenforschung gespeichert waren, durchgeführt. Unter Verwendung des 1s2s3S1→ 1s2p3P2-Übergangs wurde sowohl Λ-Spektroskopie als auch Sättigungsspektroskopie betrieben. Durch die computergestützte Analyse des Fluoreszenznachweises und unter Verwendung optimierter Kantenfilter für den Nachweis konnte das Signal zu Rauschverhältnis entscheidend verbessert und unter Einsatz eines zusätzlichen Pumplasers erstmals ein Sättigungssignal beobachtet werden. Die Frequenzstabilität der beiden verwendeten Lasersysteme wurde mit Hilfe eines Frequenzkamms spezifiziert, um eine möglichst hohe Genauigkeit zu erreichen. Die aus den Strahlzeiten gewonnen Daten wurden im Rahmen der Robertson-Mansouri-Sexl-Testtheorie (RMS) und der Standard Model Extension (SME) interpretiert und entsprechende Obergrenzen für die relevanten Testparameter der jeweiligen Theorie bestimmt. Die Obergrenze für den Testparameter α der RMS-Theorie konnte gegenüber den früheren Messungen bei 6,4 % der Lichtgeschwindigkeit am Testspeicherring (TSR) des Max-Planck-Instituts für Kernphysik in Heidelberg um einen Faktor 4 verbessert werden.

High precision swept volume approximation with conservative error bounds

In technical design processes in the automotive industry, digital prototypes rapidly gain importance, because they allow for a detection of design errors in early development stages. The technical design process includes the computation of swept volumes for maintainability analysis and clearance checks. The swept volume is very useful, for example, to identify problem areas where a safety distance might not be kept. With the explicit construction of the swept volume an engineer gets evidence on how the shape of components that come too close have to be modified.rnIn this thesis a concept for the approximation of the outer boundary of a swept volume is developed. For safety reasons, it is essential that the approximation is conservative, i.e., that the swept volume is completely enclosed by the approximation. On the other hand, one wishes to approximate the swept volume as precisely as possible. In this work, we will show, that the one-sided Hausdorff distance is the adequate measure for the error of the approximation, when the intended usage is clearance checks, continuous collision detection and maintainability analysis in CAD. We present two implementations that apply the concept and generate a manifold triangle mesh that approximates the outer boundary of a swept volume. Both algorithms are two-phased: a sweeping phase which generates a conservative voxelization of the swept volume, and the actual mesh generation which is based on restricted Delaunay refinement. This approach ensures a high precision of the approximation while respecting conservativeness.rnThe benchmarks for our test are amongst others real world scenarios that come from the automotive industry.rnFurther, we introduce a method to relate parts of an already computed swept volume boundary to those triangles of the generator, that come closest during the sweep. We use this to verify as well as to colorize meshes resulting from our implementations.

Efficient parallel proximity queries and an application to highly complex motion planning problems with many narrow passages

In vielen Bereichen der industriellen Fertigung, wie zum Beispiel in der Automobilindustrie, wer- den digitale Versuchsmodelle (sog. digital mock-ups) eingesetzt, um die Entwicklung komplexer Maschinen m ̈oglichst gut durch Computersysteme unterstu ̈tzen zu k ̈onnen. Hierbei spielen Be- wegungsplanungsalgorithmen eine wichtige Rolle, um zu gew ̈ahrleisten, dass diese digitalen Pro- totypen auch kollisionsfrei zusammengesetzt werden k ̈onnen. In den letzten Jahrzehnten haben sich hier sampling-basierte Verfahren besonders bew ̈ahrt. Diese erzeugen eine große Anzahl von zuf ̈alligen Lagen fu ̈r das ein-/auszubauende Objekt und verwenden einen Kollisionserken- nungsmechanismus, um die einzelnen Lagen auf Gu ̈ltigkeit zu u ̈berpru ̈fen. Daher spielt die Kollisionserkennung eine wesentliche Rolle beim Design effizienter Bewegungsplanungsalgorith- men. Eine Schwierigkeit fu ̈r diese Klasse von Planern stellen sogenannte “narrow passages” dar, schmale Passagen also, die immer dort auftreten, wo die Bewegungsfreiheit der zu planenden Objekte stark eingeschr ̈ankt ist. An solchen Stellen kann es schwierig sein, eine ausreichende Anzahl von kollisionsfreien Samples zu finden. Es ist dann m ̈oglicherweise n ̈otig, ausgeklu ̈geltere Techniken einzusetzen, um eine gute Performance der Algorithmen zu erreichen.rnDie vorliegende Arbeit gliedert sich in zwei Teile: Im ersten Teil untersuchen wir parallele Kollisionserkennungsalgorithmen. Da wir auf eine Anwendung bei sampling-basierten Bewe- gungsplanern abzielen, w ̈ahlen wir hier eine Problemstellung, bei der wir stets die selben zwei Objekte, aber in einer großen Anzahl von unterschiedlichen Lagen auf Kollision testen. Wir im- plementieren und vergleichen verschiedene Verfahren, die auf Hu ̈llk ̈operhierarchien (BVHs) und hierarchische Grids als Beschleunigungsstrukturen zuru ̈ckgreifen. Alle beschriebenen Verfahren wurden auf mehreren CPU-Kernen parallelisiert. Daru ̈ber hinaus vergleichen wir verschiedene CUDA Kernels zur Durchfu ̈hrung BVH-basierter Kollisionstests auf der GPU. Neben einer un- terschiedlichen Verteilung der Arbeit auf die parallelen GPU Threads untersuchen wir hier die Auswirkung verschiedener Speicherzugriffsmuster auf die Performance der resultierenden Algo- rithmen. Weiter stellen wir eine Reihe von approximativen Kollisionstests vor, die auf den beschriebenen Verfahren basieren. Wenn eine geringere Genauigkeit der Tests tolerierbar ist, kann so eine weitere Verbesserung der Performance erzielt werden.rnIm zweiten Teil der Arbeit beschreiben wir einen von uns entworfenen parallelen, sampling- basierten Bewegungsplaner zur Behandlung hochkomplexer Probleme mit mehreren “narrow passages”. Das Verfahren arbeitet in zwei Phasen. Die grundlegende Idee ist hierbei, in der er- sten Planungsphase konzeptionell kleinere Fehler zuzulassen, um die Planungseffizienz zu erh ̈ohen und den resultierenden Pfad dann in einer zweiten Phase zu reparieren. Der hierzu in Phase I eingesetzte Planer basiert auf sogenannten Expansive Space Trees. Zus ̈atzlich haben wir den Planer mit einer Freidru ̈ckoperation ausgestattet, die es erlaubt, kleinere Kollisionen aufzul ̈osen und so die Effizienz in Bereichen mit eingeschr ̈ankter Bewegungsfreiheit zu erh ̈ohen. Optional erlaubt unsere Implementierung den Einsatz von approximativen Kollisionstests. Dies setzt die Genauigkeit der ersten Planungsphase weiter herab, fu ̈hrt aber auch zu einer weiteren Perfor- mancesteigerung. Die aus Phase I resultierenden Bewegungspfade sind dann unter Umst ̈anden nicht komplett kollisionsfrei. Um diese Pfade zu reparieren, haben wir einen neuartigen Pla- nungsalgorithmus entworfen, der lokal beschr ̈ankt auf eine kleine Umgebung um den bestehenden Pfad einen neuen, kollisionsfreien Bewegungspfad plant.rnWir haben den beschriebenen Algorithmus mit einer Klasse von neuen, schwierigen Metall- Puzzlen getestet, die zum Teil mehrere “narrow passages” aufweisen. Unseres Wissens nach ist eine Sammlung vergleichbar komplexer Benchmarks nicht ̈offentlich zug ̈anglich und wir fan- den auch keine Beschreibung von vergleichbar komplexen Benchmarks in der Motion-Planning Literatur.