Wie kann ich Punkte in Bereichen mit höherer Krümmung konzentrieren?

Wie kann ich Punkte auf einer impliziten Oberfläche verteilen, um sie in Bereichen mit höherer Krümmung dichter zu konzentrieren?

Ich habe überlegt, Punkte zufällig hinzuzufügen und Punkte abzulehnen, die aufgrund der Krümmung nicht erforderlich sind, aber ich würde gerne wissen, ob es einen besseren Ansatz gibt, um eine gleichmäßigere Verteilung über Bereiche mit ähnlicher Krümmung zu erzielen und gleichzeitig die in hoher Höhe erforderliche höhere Dichte zu erzielen Krümmungsbereiche.

Ich möchte diese Punkte speziell für eine Triangulation der Oberfläche verwenden und möchte nicht mehr Dreiecke erstellen, als ich für relativ flache Teile benötige.

Dies wird auf Formen mit einer bekannten Ableitung angewendet, damit die Krümmung an einem bestimmten Punkt berechnet werden kann.

Dies muss kein Echtzeitansatz sein.

Die Idee, die ich anwenden möchte, wäre die folgende: Ich mache das Beispiel für die Kurve, aber es sollte für die Anwendung für die Oberfläche einfach sein.

Nehmen wir an, wir haben eine Kurve gleichmäßig parametrisiert ist. Angenommen, der Parameter der Kurve ist s . Ihr Ziel ist es, einen Punkt abzutasten, der dem Wert von s entspricht, so dass die Krümmung hoch ist.$\gamma$$s$$s$

Wenn Sie die Größe der Krümmung , ist dies auch eine Funktion von s . Also, wenn Sie die Funktion | normalisieren c | erhalten Sie eine Wahrscheinlichkeitsverteilung. Wenn Sie das Integral einer solchen Verteilung erhalten, erhalten Sie die kumulative Verteilung. Nennen wir diese kumulative Funktion C ( s ) .$c$$s$$|c|$$C(s)$

Das Stichprobenproblem aus einer Verteilung, die durch die kumulative Funktion gegeben ist, ist allgemein bekannt. Wenn Sie also einen Satz von Werten abgetastet haben , wird dieser Wert mit den interessierenden Punkten in Beziehung gesetzt.$s_0,s_1,\dots,s_n$

Die Anwendung dieser Methode auf den Fall der Oberfläche sollte gerade sein, da Sie im Grunde eine zweidimensionale kumulative Verteilungsfunktion haben, das Stichprobenproblem jedoch genau das gleiche ist.

Um nur einige Details zu nennen, handelt es sich im Grunde genommen um eine Stichprobe aus einer Verteilung, da die kumulative Funktion zwei Schritte umfasst:

1. Nehmen Sie einen zufälligen Wert im Intervall , sagen wir $[0,1]$$k$

2. Löse die Gleichung .$C(s) = k$

Dieser Ansatz ist genau, natürlich teuer, aber wenn Sie einen solchen Ansatz mögen, können Sie an der Optimierung arbeiten.

Ein guter Ausgangspunkt ist das in SIGGRAPH 1994 veröffentlichte klassische Papier Verwenden von Partikeln zur Probenahme und Kontrolle impliziter Oberflächen .

Eine einfache Partikelsimulation, die in der Arbeit Sampling impliziter Objekte mit physikalisch basierten Partikelsystemen ( Computers & Graphics , 1996) für Kurven beschrieben wurde, funktioniert auch für Oberflächen. Beispiele finden Sie unter Dynamische Textur für implizite Oberflächen .

Ein neueres Beispiel finden Sie unter Form- und Tondarstellung für implizite Oberflächen ( Computers & Graphics , 2011).

Der folgende naive Ansatz wird wahrscheinlich nicht so gut verteilte Punkte liefern wie die von Lhf angegebenen , aber es sollte viel einfacher zu implementieren und rechnerisch schneller sein:

Für zwei Punkte $x$ und $y$ Lassen $d(x,y)$ bezeichnen die durchschnittliche Entfernung, die Sie Punkte mit der durchschnittlichen Krümmung von möchten $x$ und $y$ zB eine Konstante multipliziert mit der Umkehrung der durchschnittlichen Krümmung von zu haben $x$ und $y$.

Bauen Sie nun Ihre Punktesammlung auf $A$ nacheinander:

1. Wählen Sie einen zufälligen Punkt $x$ und fügen Sie zwei Punkte hinzu, sodass alle drei Punkte ein gleichseitiges Dreieck mit Kantenlänge bilden $d(x,x)$.

2. Addiere alle Punkte zu $A$ und markieren Sie sie als benachbart.

3. Führen Sie die folgenden Schritte wiederholt aus, bis keine Nachbarschaften mehr vorhanden sind $A$ nicht mehr:

   1. Wählen Sie zwei benachbarte Punkte aus $x$ und $y$ von $A$. Markieren Sie sie als nicht benachbart.
   2. Consider a point $z$ that has a distance of $d(x,y)$ from both these points. Of the two possible such points select the one pointing outwards of $A$ (this needs some work, but should be straightforward).

   3. Check whether $z$ is closer than $d(x,y)$ to any point from $A$ that is still adjacent to another point.

      • if yes, discard it.
      • if no, mark $x$ and $z$ as well as $y$ and $z$ as adjacent and add $z$ to $A$.

At the end, $A$ should be a collection of points matching your criteria. You sort-of just created a triangulation but it may be pathological and thus you should probably triangulate the points afresh.