isosurface in hohen Dimensionen Tracking

Question

wie isosurface auf einem höherdimensionalen Raum verfolgen effizient

Answer 1

Sie haben eine skalare Kostenfunktion in N Dimensionen,

f ( y , y , .., y ) ε r,   y ε r

sondern nur in einem regelmäßigen rechteckigen Raster abgetastet,

y _k = Ψ _k + ψ _k x _k ,   Konstanten Ψ _k ε r und ψ _k ε r und Gitterkoordinaten x _k ε n

und das Problem ist die Isofläche (n) zu lokalisieren i,

f ( y , y 1, .., y _N) = C _i

der direkte Weg über jede Zelle nur Schleife wäre in der Gitter, und überprüfen Sie, ob die aktuelle Isofläche die aktuelle Zelle schneidet, und wenn ja, beschreiben Sie den Teil der Isofläche innerhalb der aktuellen Zelle. (Marching Cubes ist ein Ansatz, um zu beschreiben, wie die Isofläche jede Rasterzelle schneidet.)

Die Einschränkung hier ist, eine Nachbarschaftssuche statt jede einzelne Zelle zu untersuchen.

OP hatte eine previous question speziell für den 3D-Fall, auf die ich posted ein Link zu Beispielcode, grid.h und grid.c (bei Pastebin.com, weil sie zu lang waren inline enthalten).

Diese Implementierung unterscheidet sich vollständig von der Slicing-Methode von OP. Meine ist ein direkter, einfacher Weg über die Rasterzellen, die die aktuelle Isofläche schneiden.Er speichert die Rasterproben im Cache und verwendet eine separate Karte (eine char pro Rasterzelle), um zu verfolgen, welche Gitterzellen zwischengespeichert, gelaufen und/oder zu einem Stapel geschoben wurden, um später durchlaufen zu werden. Dieser Ansatz kann leicht auf mehr als drei Dimensionen erweitert werden. Obwohl der Code für genau drei Dimensionen geschrieben wurde, ist der Ansatz selbst nicht spezifisch für drei Dimensionen. Sie müssen lediglich die Datenstrukturen anpassen, um jede (sinnvolle) Anzahl von Dimensionen zu berücksichtigen.

Der Isoflächengang selbst ist trivial. Sie beginnen mit einer Rasterzelle, die die Isofläche schneidet, und untersuchen dann alle nächsten Nachbarzellen, um zu sehen, ob die Isofläche diese auch schneidet. In der Praxis verwenden Sie einen Stapel von Gitterzellenpositionen, um untersucht zu werden, und eine Karte von Gitterzellenflags, um zu vermeiden, bereits untersuchte Gitterzellen erneut zu untersuchen. Da die Anzahl der Gitterpunktabtastungen pro Gitterzelle 2 N ist, ist mein Beispielcode nicht optimal: Viele nahe gelegene Gitterpunkte werden ausgewertet, um zu sehen, ob die benachbarten Gitterzellen die Isofläche schneiden. (Anstatt nur die Gitterpunkte zu untersuchen, die die Isofläche begrenzen, werden Gitterpunkte untersucht, die zu Gitterzellen gehören, die die Isofläche umgeben.) Diese zusätzliche Arbeit wächst exponentiell, wenn sie zunimmt.

Ein besserer Ansatz wäre jede der möglichen 2 N zu betrachten ( N -1) -faces getrennt, untersuchten Zellen zu vermeiden, die Iso-Oberfläche überhaupt nicht schneiden.

In einem N -dimensionalen regelmäßigen Rechteckraster ist jede Zelle ein N -dimensionalen Quader, durch die 2 definiert ^N Gitterpunkte an den Scheitelpunkten (Ecken). Die N -cuboid Zellen haben N ( N -1) zweidimensionale Flächen, und 2 N ( N-1) -dimensionalen Gesichter.

Um jede ( N -1) -Fläche zu untersuchen, müssen Sie die Kostenfunktion auf die 2 ^{N -1} Gitterpunkte untersuchen definieren, dass ( N -1) -Fläche. Wenn die Kostenfunktion an diesen Punkten den Isoflächenwert überspannt, schneidet die Isofläche die ( -1) -Oberfläche, und die Isofläche schneidet auch die nächste Gitterzelle in dieser Richtung.

Es gibt zwei ( -1) -Flächen senkrecht zu jeder Achse. Wenn die Isofläche die ( -1) -Oberfläche näher an der negativen Unendlichkeit schneidet, dann schneidet die Isofläche die nächste Gitterzelle entlang dieser Achse in Richtung der negativen Unendlichkeit. Wenn die Isofläche die ( -1) ähnliche Fläche näher an der positiven Unendlichkeit schneidet, schneidet sie auch die nächste Gitterzelle entlang dieser Achse in Richtung der positiven Unendlichkeit. Somit sind die ( -1 -1) -Flächen perfekt für die Entscheidung, welche Nachbarzellen untersucht werden sollen oder nicht. Dies ist der Fall, weil die ( -1 -1) -Fläche genau die Menge der Gitterpunkte ist, die die beiden Zellen teilen.

Ich bin sehr zögerlich, Beispiel-C-Code zu geben, weil der Beispielcode des gleichen Ansatzes für den 3D-Fall bisher niemandem geholfen zu haben scheint.Ich fürchte, eine längere Erklärung mit 2- und 3-dimensionalen Beispielbildern zur Veranschaulichung wäre erforderlich, um den Ansatz in leicht verständlichen Begriffen zu beschreiben; und ohne ein festes Verständnis der Logik würde jeder Beispielcode einfach wie ein Kauderwelsch aussehen.

Answer 2

Sie sind besser mit einer Bibliothek für 2-Dimension können Sie den Conrec-Algorithmus von Prof. Paul Bourke versuchen. Es ist einem Marschwürfel ähnlich.