Partikelverfolgung und Octrees

Quadtrees (und octrees in 3D) definieren mittels rekursiver Zerlegung eines Raumes eine hierarchische Datenstruktur. Ein quadtree (bzw. ein octree) ist ein Baum, in dem jeder innere Knoten vier (acht) Söhne besitzt. Jeder Knoten korrespondiert mit einem Quadrat (Würfel).
Hat ein Knoten v eines quadtrees Söhne, dann sind die den Söhnen zugeordneten Quadrate die Quadranten des zu v gehörenden Quadrats. In den Knoten können dabei nicht nur Punkte sondern auch Linien und Flächen gespeichert werden (PM octrees,
Samet)

Der Engpaß bei der Berechnung der Partikelbewegung in den beiden "Filmen" ist das Aufspüren von Stößen. Ein naiver Algorithmus, der jedes mögliche Partikelpaar auf einen Zusammenstoß testet, führt zu einem Aufwand der Größenordnung O(n²). Werden die Partikel in einem octree gespeichert, so läßt sich ein Nahfeld zu einem Teilchen bestimmen (Aufwand O(log(n)). Insgesamt ergibt sich ein O(n log(n))-Algorithmus.

 

Partikelverfolgung und zugehöriger dynamischer octree als gif-Film (ca 140 KB)

Partikelverfolgung als Film (ca 0.5 MB)

 


Up  Home

Dr. F. Liebau
2002-06-25