Boundary handling and neighbor search in iterative incompressible SPH

Abstract: Die physikalisch basierte Simulation von Fluiden stellt in den Computerwissenschaften eine anspruchsvolle Aufgabe dar. Um diese Aufgabe zu bewältigen, wird oftmals die partikelbasierte Interpolationsmethode Smoothed Particle Hydrodynamics (SPH) verwendet. Obwohl die Anwendungsgebiete solcher numerischen Simulationen in den letzten Jahren stetig zugenommen haben, bleibt eine erhebliche Anzahl von Problemen weiterhin zu lösen.

Für Simulationen inkompressibler Fluide stellt der Volumenerhalt eine besondere Herausforderung dar, um ein realistisches Verhalten zu erzielen. Neueren Verfahren liegt in diesem Zusammenhang ein implizites Schema zugrunde, wobei auf iterative Weise eine Druck-Poisson-Gleichung (PPE) gelöst wird. Aufgrund verschiedener Vorteile im Vergleich zu expliziten Schemata, wie beispielsweise Robustheit, größere Zeitschritte und Benutzerfreundlichkeit, gelten iterative Verfahren heutzutage als Stand der Technik zum Einhalten der Inkompressibilitätsbedingung.

Effizienten und stabilen Implementierungen solch iterativer Verfahren liegen ausgefeilte Methoden zur Grenzflächenbehandlung und Nachbarsuche zugrunde. Obwohl einige der interessantesten Verhaltensweisen von Fluiden an Grenzflächen entstehen, haben numerische Methoden große Schwierigkeiten physikalisch korrekte Ergebnisse zu erzielen. Im Falle von SPH ist das Fehlen von Partikeln an diesen Grenzflächen besonders problematisch. Dennoch verwenden neuere iterative Löser hierzu noch immer Methoden, die ursprünglich für nicht-iterative Löser entwickelt wurden. Zudem haben iterative Löser spezielle Anforderungen an die Performanz. Da insbesondere in modernen Computerarchitekturen höhere Prozessor-Taktraten Verbesserungen der Speicherbandbreite übertroffen haben, sind iterative Löser nun ebenfalls durch Speicherperformanz limitiert. Davon ist vor allem die Nachbarsuche betroffen. All dies motiviert die Untersuchung neuer Algorithmen und Datenstrukturen, welche die besonderen Eigenschaften und Anforderungen iterativer Löser berücksichtigen.

Diese Arbeit leistet vier Beiträge, um den Stand der Technik der Grenzflächenbehandlung und Nachbarsuche voranzubringen. Der Schwerpunkt liegt dabei auf iterativen inkompressiblen SPH-Lösern. In einem ersten Beitrag wird eine neuartige Grenzflächenbehandlung vorgestellt. Neu daran ist, dass die PPE um individuelle Druckwerte von Grenzpartikel erweitert wird. Neben einer Reduktion von Druckschwankungen hat dies den Vorteil, dass die Konvergenz verbessert wird und größere Zeitschritte verwendet werden können. Ein zweiter Beitrag vereinfacht die erweiterte PPE-Formulierung unter Beibehaltung ihrer Vorteile. Hierzu werden mittels Moving Least Squares (MLS) Druckwerte von Fluid- zu Grenzpartikeln lokal extrapoliert. Ein dritter Beitrag beschäftigt sich mit Verbesserungen für ebene Grenzflächen. Dazu wird die Oberfläche der tatsächlichen Grenzfläche mittels MLS rekonstruiert. Dies löst Probleme früherer Verfahren aufgrund von Abweichungen bei der Berechnung von Normalenvektoren und Entfernungen. Weitere Vorteile sind ein verringertes Durchsickern von Fluidpartikeln an den Grenzflächen sowie eine verringerte künstliche Reibung. Ein vierter Beitrag ist ein neuartiges Komprimierungsschema für die Nachbarsuche. Es nutzt spezielle Eigenschaften der Partikelsortierung, was zu erheblichen Speichereinsparungen führt. Es ist Teil einer neuartigen Datenstruktur, die raumfüllende Kurven verwendet, um die räumliche Lokalität und die zeitliche Kohärenz zu verbessern. Dies resultiert in höheren Cache-Trefferquoten sowie in einem geringeren Speicherverkehr.

Trotz der hohen Anforderungen iterativer PPE-Löser an die Recheneffizienz und den Speicherbedarf, weisen alle vier geleisteten Beiträge großes Potenzial zur Verbesserung der Simulationsgenauigkeit, -robustheit und -effizienz auf. Anspruchsvolle Simulationen mit komplexen sowie sich schnell bewegenden Grenzflächengeometrien und Milliarden von Partikeln werden auf gängiger Computerhardware effizient verarbeitet. Dies wäre mit früheren Methoden nicht möglich gewesen
Abstract: The physically based simulation of fluids is a challenging task in the field of computational science. In Lagrangian simulations, Smoothed Particle Hydrodynamics (SPH) is a popular method to accomplish this task. Although the number of applications for such simulations has increased steadily in recent years, a substantial number of issues still remains to be addressed.

For simulations of incompressible fluids, volume preservation is one of the key aspects to achieve realistic behavior. For this purpose, recent methods use implicit schemes that iteratively solve a Pressure Poisson Equation (PPE). Due to various benefits compared to explicit schemes, such as robustness, larger time steps and ease of use, iterative solvers are nowadays considered as state-of-the-art to achieve incompressibility.

Efficient and stable implementations of such iterative solvers base on the interplay of sophisticated solutions for boundary handling and neighbor search. Although some of the most interesting fluid behaviors originate at the interface to boundaries, numerical methods encounter great difficulty in achieving physically correct results. In the context of SPH, the particle deficiency at interfaces is particularly problematic. Nevertheless, recent iterative solvers still use boundary handling methods that were originally developed for non-iterative solvers. Furthermore, as increased clock speeds in modern computer architectures have outpaced improvements in memory bandwidth, iterative solvers are now also limited by memory performance, which particularly affects the neighbor search. All in all, this motivates to investigate new algorithms and data structures that take into account the special characteristics of iterative solvers.

This thesis makes four contributions to advance the state-of-the-art in boundary handling and neighbor search with a particular focus on recent iterative incompressible SPH solvers. In a first contribution, a novel boundary handling is derived that overcomes previous issues by incorporating pressure values of boundary particles into the PPE. This reduces pressure oscillations, improves solver convergence and allows to use larger time steps. A second contribution simplifies the extended PPE formulation while preserving its benefits. For this purpose, Moving Least Squares (MLS) is employed to locally extrapolate pressure values from fluid to boundary particles. A third contribution concentrates on improvements for planar boundaries. Thereby, the surface of the true boundary is reconstructed with MLS. This resolves issues of previous methods due to deviations in computed normal vectors and due to erroneous oscillations in distance computations. Further benefits include a reduced particle leakage and a reduced artificial boundary friction. A fourth contribution is a novel compression scheme that uses an optimized structure leveraging unique characteristics of the particle ordering, yielding significant memory savings. It is part of a novel data structure that employs space filling curves to improve spatial locality and temporal coherence. This results in higher cache-hit rates and lower memory traffic for the neighbor search.

Despite the high demands in terms of computational efficiency and memory requirements of iterative PPE-based solvers, all four contributions show great potential to positively affect simulation accuracy, robustness and efficiency. Challenging large-scale simulations with fast-moving complex boundary geometries and billions of particles are efficiently processed on common computer hardware. This would have been infeasible with previous methods

Angaben zum Objekt

• Standort: Deutsche Nationalbibliothek Frankfurt am Main
• Umfang: Online-Ressource
• Sprache: Englisch
• Anmerkungen: Universität Freiburg, Dissertation, 2020

Klassifikation und Themen

• Schlagwort: Hydrodynamics ; Smoothed Particle Hydrodynamics ; Numerische Strömungssimulation ; Animation

Beteiligte, Orts- und Zeitangaben

• Ereignis: Veröffentlichung
• (wo): Freiburg
• (wer): Universität
• (wann): 2020
• Urheber: Band, Stefan
• Beteiligte Personen und Organisationen: Teschner, Matthias ; Albert-Ludwigs-Universität Freiburg. Fakultät für Angewandte Wissenschaften

Weitere Informationen

• DOI: 10.6094/UNIFR/166559
• URN: urn:nbn:de:bsz:25-freidok-1665593
• Rechteinformation: Der Zugriff auf das Objekt ist unbeschränkt möglich.
• Letzte Aktualisierung: 14.08.2025, 10:52 MESZ