Zeichnen einer Iso-Linie eines impliziten 2D-Skalarfelds

Question

Ich habe ein implizites Skalarfeld, das in 2D definiert ist. Für jeden Punkt in 2D kann ich einen exakten Skalarwert berechnen, aber es ist eine etwas komplexe Berechnung.
Ich möchte eine Iso-Linie dieser Oberfläche zeichnen, sagen wir die Linie des '0' Wertes. Die Funktion selbst ist fortlaufend, aber die Iso-Zeile "0" kann mehrere fortlaufende Instanzen haben, und es ist nicht garantiert, dass sie alle verbunden sind.
Das Berechnen des Werts für jedes Pixel ist keine Option, da dies zu viel Zeit in Anspruch nehmen würde - in der Größenordnung von ein paar Sekunden und das muss so realtime wie möglich sein.

Was ich gerade benutze, ist eine rekursive Raumaufteilung, die man sich als eine Art Viererbaum vorstellen kann. Ich nehme eine anfängliche, sehr grobe Abtastung des Raums, und wenn ich ein Quadrat finde, das einen Übergang von positiven zu negativen Werten enthält, teile ich es rekursiv in 4 kleinere Quadrate und überprüfe es erneut, wobei ich auf der Pixelebene stoppe. Der Positiv-Negativ-Übergang wird durch Abtasten eines Quadrats in seinen 4 Ecken detektiert. Das funktioniert ziemlich gut, außer wenn es nicht funktioniert. Die Iso-Linien, die gezeichnet werden, werden manchmal abgeschnitten, weil die Übergangserfassung für Übergänge fehlschlägt, die in einem kleinen Bereich einer Kante auftreten und die eine Ecke eines Quadrats nicht kreuzen.

Gibt es eine bessere Möglichkeit, Iso-Line-Zeichnen in diesen Einstellungen zu tun?

Answer 1

Ich hatte viel Erfolg mit den hier beschriebenen Algorithmen http://web.archive.org/web/20140718130446/http://members.bellatlantic.net/~vze2vrva/thesis.html , die adaptive Konturierung (ähnlich zu dem, was Sie beschreiben), und auch einige andere Probleme mit Kontur Plotten im Allgemeinen.

Es gibt keine allgemeine Möglichkeit, alle Konturen einer Funktion zu finden, ohne auf jedes Pixel zu schauen. Es könnte eine sehr kleine geschlossene Kontur geben, wo eine Region nur ungefähr die Größe eines Pixels hat, wo die Funktion positiv ist, in einem Bereich, in dem die Funktion im Allgemeinen negativ ist. Wenn Sie nicht so fein proben, dass Sie eine Probe in die positive Region platzieren, gibt es keine allgemeine Möglichkeit zu wissen, dass sie da ist.

Wenn Ihre Funktion glatt genug ist, können Sie möglicherweise raten, wo solche kleinen geschlossenen Konturen liegen, weil der Modul der Funktion in einer sie umgebenden Region klein wird. Die Probenahme könnte dann nur in diesen Regionen verfeinert werden.