Die meisten zweidimensionalen quasi-zufälligen Methoden sind für die Einheitsquadratabtastung ausgelegt. Dreiecke sind jedoch auch in der Computergrafik sehr wichtig. Daher habe ich eine einfache direkte Konstruktionsmethode beschrieben, um eine Folge von Punkten eines Dreiecks beliebiger Form gleichmäßig abzudecken.


Figure 1. Eine neue direkte Methode zur Konstruktion einer offenen (unendlichen) quasi-zufälligen Sequenz mit geringer Divergenz in einem Dreieck beliebiger Form und Größe. Die Abbildung zeigt die Verteilung der Punkte in fünfzehn zufälligen Dreiecken für die ersten 150 Punkte.

Kurzer Rückblick

Sequenzen mit geringer Diskrepanz, die ein Quadrat gleichmäßig abtasten / füllen, werden seit fast hundert Jahren aktiv untersucht. Die meisten dieser quasi zufälligen Sequenzen können durch einfaches Strecken zu Rechtecken erweitert werden, ohne die Diskrepanz wesentlich zu beschädigen.

In diesem Beitrag werden wir jedoch eine interessante und wichtige Erweiterung von Sequenzen mit geringer Divergenz in ein beliebiges Dreieck betrachten.

Soweit ich verstehen konnte, wurde der Konstruktion von Mengen von Punkten und Sequenzen, die gleichmäßig in einem Dreieck verteilt sind, sehr wenig Aufmerksamkeit geschenkt. Die bemerkenswerten Werke der letzten Jahre von Basu [2014] , Pillands [2005] und Brandolini [2013] sind die wichtigsten, wenn nicht die einzigen Artikel zu diesem Thema.

Diese Autoren betrachten dieses Problem normalerweise aus einem sehr theoretischen und analytischen Blickwinkel und lösen es fast immer für ein einzelnes reguläres Dreieck. Im Gegensatz dazu ist mein Beitrag hauptsächlich für die Entwicklung praktischer Techniken beim Rendern von Grafiken gedacht.

Der Beitrag beschreibt eine einfache Methode der direkten Konstruktion, die weder Akzeptanz / Ausschluss noch Verwerfen oder Rekursion erfordert. und vor allem kann es auf Dreiecke beliebiger Größe und Form angewendet werden.

Der Beitrag besteht aus vier Abschnitten:

1. Quadratische Zufallssequenzen
2. Überlagern Sie ein Einheitsquadrat mit einem Dreieck.
3. Verzerrungsreduzierung
4. Weitere Verallgemeinerungen

1. Quasi zufällige Folge von Punkten

Sie könnten denken, dass es einfach ist, 100 Punkte in einem Quadrat zu platzieren, damit der Mindestabstand zwischen benachbarten Punkten so groß wie möglich bleibt. Aber was ist, wenn Sie 13 Punkte platzieren müssen? 47? Was ist mit 2019 Punkten ?!

Es stellt sich heraus, dass Punktfolgen mit geringer Divergenz einen systematischen Weg zur Lösung dieses Problems darstellen. Es gibt viele quasi zufällige Sequenzen mit geringer Divergenz, von einer einfachen Holton-Sequenz zu einer komplexeren Sable-Sequenz. Jede dieser Sequenzen hat ihre eigenen Vor- und Nachteile. Beispielsweise erweisen sich Holton-Sequenzen als nützlicher, wenn Objekte in einem Bereich platziert werden, da sie über gut optimierte lokale Entfernungsmetriken wie die nächsten Nachbarn verfügen. Die Sable-Sequenz neigt dazu, mehr "überfüllt" zu bilden, aber die globale Verteilung der Punkte ist sehr gleichmäßig, so dass sie ausgezeichnete Quadratureigenschaften aufweist.

Es gibt eine andere Sequenz, die ich gerne verwende, mit ausgezeichneten lokalen und globalen Eigenschaften. Dies ist die Reihenfolge $$$R_2$ausführlich beschrieben in meinem vorherigen Beitrag "Unerwartete Effizienz von quasi-zufälligen Sequenzen" .

Kurz gesagt, wir definieren eine unendliche zweidimensionale Sequenz $$$R_2$so dass

$$

$$\ pmb {t} _n = \ left \ {n \ pmb {\ alpha} \ right \} \ quad n = 1,2,3, ... \ pmb {t} _n = \ left \ {n \ pmb {\ alpha} \ right \} \ quad n = 1,2,3, ...$$

$$

$$\ textrm {where} \ quad \ pmb {\ alpha} = \ left (\ frac {1} {g}, \ frac {1} {g ^ 2} \ right),$$

$$

$$\ textrm {und} \; g \ simeq 1.32471795572 \ tag {1}$$

Lesen Sie mehr über diese besondere Bedeutung. $$$g$, die oft als "plastische Konstante" bezeichnet wird, kann auf Wikipedia oder Mathworld gelesen werden.

Als Ergebnis zeigt 2 einen Vergleich verschiedener Sequenzen mit einer geringen Divergenz (und einer einfachen einheitlichen Zufallsstichprobe zum Vergleich). Wie Sie sehen können, zeigt diese Zufallsstichprobe die Ansammlung von Punkten. Darüber hinaus enthält es Bereiche, die überhaupt keine Punkte enthalten („weißes Rauschen“), während eine quasi zufällige Folge mit geringer Divergenz eine Methode ist, um eine (unendliche) Folge von Punkten deterministisch zu konstruieren, so dass die platzierten Punkte zu jedem Zeitpunkt gleichmäßig verteilt sind Raum.


Abbildung 2. Darstellung der ersten 150 Mitglieder verschiedener quasi zufälliger Sequenzen mit geringer Divergenz. Beachten Sie, dass sie alle gleichmäßig verteilte Punkte im Raum erzeugen als eine einfache gleichmäßige Zufallsverteilung (unten links).

2. Das Auferlegen eines Einheitsquadrats auf ein Dreieck

Es gibt drei bekannte Methoden, um eine einheitliche Zufallsstichprobe aus einem Dreieck sicherzustellen:

1. Parallelogrammmethode
2. Kramers Methode und
3. inverse Wahrscheinlichkeitsverteilungsmethode.

Abbildung 3. Parallelogrammmethode

Die Parallelogrammmethode ist wie folgt.

Für Dreieck $$$\ pmb {ABC}$Betrachten Sie ein Parallelogramm $$$\ pmb {ABCA ’}$.

Für einen Punkt eines Einheitsquadrats $$$(r_1, r_2)$setze einen solchen Punkt $$$\ pmb {P}$das $$$\ pmb {P} = r_1 \ pmb {AC} + r_2 \ pmb {AB}$.

Dieser Punkt befindet sich immer innerhalb des Parallelogramms. Wenn es jedoch in einem zusätzlichen Dreieck angezeigt wird $$$\ pmb {ABC ’}$dann müssen wir es zurück zum Dreieck drehen $$$\ pmb {ABC}$.

Das heißt, wenn $$$r_1 + r_2 <1$dann $$$\ pmb {P} = r_1 \ pmb {AC} + r_2 \ pmb {AB}$aber wenn $$$r_1 + r_2> 1$dann $$$\ pmb {P} = (1-r_1) \ pmb {AC} + (1-r_2) \ pmb {AB}$.

Es ist jedoch sehr wichtig zu verstehen, dass, obwohl diese Verfahren eine gleichmäßige Abtastung aus dem Dreieck liefern, dies nicht bedeutet, dass eine solche Transformation die gleichmäßige räumliche Anordnung (d. H. Geringe Divergenz) unserer quasi zufälligen Punktverteilungen beibehält.

Beispielsweise kann bei der Parallelogrammmethode die Reflexion häufig dazu führen, dass ein Punkt sehr nahe an einem anderen vorhandenen Punkt liegt. Offensichtlich zerstört dies die Struktur mit geringer Divergenz und erscheint als Verzerrung / Streifen.

In ähnlicher Weise wendet das inverse Wahrscheinlichkeitsverteilungsverfahren eine nichtlineare Verzerrung auf Punkte an. In Holton- und Sable-Sequenzen bedeutet dies, dass sich zwei Punkte sehr oft sehr nahe beieinander befinden.

Abbildung 4 zeigt, wie gut die geringe Diskrepanz in jeder der verschiedenen quasi-zufälligen Sequenzen erhalten bleibt, wenn eine Region mithilfe der Parallelogrammmethode von einem Einheitsquadrat in ein Dreieck transformiert wird.


Figure 4. Vergleich der Transformation verschiedener quasi-zufälliger Sequenzen in einem Dreieck. Oben ist die Holton-Sequenz, in der Mitte die Sable-Sequenz, unten die Sequenz $$$R_2$. Es ist ersichtlich, dass in der Holton-Sequenz eine signifikante Überfüllung der Punkte und in der Sobol-Sequenz eine signifikante Bandenbildung auftritt. Im Vergleich zu ihnen nacheinander $$$R_2$Die Punkte sind sehr gleichmäßig verteilt und es gibt fast keine erkennbaren Überfüllungen oder Streifen.

Von den drei verschiedenen Triangulationsmethoden und vielen verschiedenen quasi-zufälligen Sequenzen wurde die Parallelogrammmethode auf die Sequenzmethode angewendet $$$R_2$ist die einzige Kombination, die ständig Ergebnisse erzielt, die im Hinblick auf die Aufrechterhaltung einer geringen Varianz ohne Verzerrung akzeptabel sind.

Die hervorragenden Ergebnisse dieser Kombination können in Abbildung 5 genauer untersucht werden.


Abbildung 5. Sie können sehen, dass die konvertierte Sequenz $$$R_2$bietet eine sehr einfache, aber effektive Möglichkeit, viele davon gleichmäßig zu verteilen $$$N$Punkte im Dreieck. Es funktioniert mit spitzwinkligen und stumpfwinkligen Dreiecken. (Farbe zeigt die Anordnung an).

3. Andere Aspekte

Verzerrung

Das Parallelogrammverfahren erfordert die Auswahl von zwei Seiten des Dreiecks als Basisvektoren.

Wenn Scheitelpunkte in zufälliger Reihenfolge markiert sind, ähneln die Punktmuster normalerweise den in Abbildung 6 gezeigten.


Abbildung 6. Muster von Punkten, die durch zufällige Auswahl der Scheitelpunktreihenfolge erhalten wurden. Beachten Sie, dass in den meisten Fällen Verzerrungen deutlich erkennbar sind.

Es stellt sich jedoch heraus, dass bei sorgfältiger Auswahl der Reihenfolge der Eckpunkte Verzerrungen erheblich reduziert werden können. Vor allem, wenn Sie das Dreieck so beschriften $$$A$ist der größte Winkel (d. h. die größte Seite ist dagegen), dann die Seiten $$$\ pmb {AB}$und $$$\ pmb {AC}$werden als zwei Seiten eines Parallelogramms verwendet.

Wenn wir diese Reihenfolge einhalten, erhalten wir die oben in den Abbildungen 1, 4 und 5 gezeigten Punktmuster.

Selbst bei einer bestimmten Reihenfolge von Eckpunkten sind in einigen Fällen jedoch immer noch Verzerrungseffekte erkennbar. Sie fallen am deutlichsten auf, wenn einer der Winkel in den Dreiecken sehr klein ist. Bei stumpfen Dreiecken, wenn der kleinste Winkel weniger als 30 Grad beträgt, ist eine gewisse Verzerrung erkennbar, und bei spitzwinkligen Dreiecken, wenn der kleinste Winkel weniger als 20 Grad beträgt, wird eine Verzerrung sichtbar. (Wenn die abgetasteten Dreiecke Teil des Delaunay-Netzes sind, können solche Verzerrungsprobleme minimal sein, da die Delaunay-Triangulation speziell darauf ausgelegt ist, die Anzahl der Dreiecke mit kleinen Winkeln zu minimieren.)

Andere Formen

Leider kann die Parallelogrammtechnik nicht für andere Formen verwendet werden, da sie Dreiecksymmetrie verwendet. Für einige Figuren können mit der inversen Wahrscheinlichkeitsverteilungsmethode gute Ergebnisse erzielt werden. Das Folgende ist ein Beispiel für die Reihenfolge $$$R_2R_2$Mit einer geringen Divergenz können Sie in einen Bereich konvertieren, der von einer Gaußschen Kurve begrenzt wird, während Sie einen gleichmäßigen Abstand zwischen den Punkten beibehalten.