Berechnung einer Normalen mit Freiheitsgraden

[Schrompf]

Moin,

ich bastle trotz absehbarem Tod meiner Selbständigkeit immernoch am Voxelprojekt. Da habe ich jetzt ein Problem mit der Beleuchtung. Ich berechne pro Voxel eine Normale anhand der 3^3 bzw. 5^3 umgebenden Voxel. Dabei kommt es immer wieder vor, dass ein Voxel absolut symmetrisch von Nachbarvoxeln umgeben ist, so dass die momentane Normalenberechnung den Nullvektor ergibt. Was ich also eigentlich suche, ist eine erweiterte Normalenberechnung, die irgendwie die Freiheitsgrade zur aktuellen Umgebungssituation ermittelt und irgendwie in die Normale mitkodiert.

Folgende Szenarien sind möglich:

a) der Voxel ist Teil einer ein-voxel-dicken Schicht. Die Normale für diesen Fall ist eigentlich durch die Ebene definiert, kann aber zwei Richtungen sein. Also quasi schlichte doppelseitige Beleuchtung.

b) der Voxel ist Teil einer ein-voxel-dicken Strecke. Die Normale ist also nur als Senkrechte auf dieser Strecke festgelegt, kann aber frei um diese Achse rotiert werden.

c) der Voxel ist freistehend. Die Normale ist völlig frei.

Von diesen drei Szenarien ist eigentlich nur a) wirklich lösenswürdig. Egal, wie dick man die Wände eines Hauses macht, schon in wenigen hundert Metern Distanz sind die Wände durch's LOD nur noch einen Voxel dick. b) kommt auch gelegentlich vor, ist aber selten genug, um auf Nice-To-Have herabgestuft zu werden. c) Ist nahezu ausgeschlossen nach meinem bisherigen Kenntnisstand.

Mein Gedanke war jetzt, dass ich zusätzlich zur Normale noch irgendwie kodiere, welche Freiheitsgrade diese Normale hat, und dann bei der Beleuchtung die Normale relativ zum Betrachter innerhalb dieser Freiheitsgrade anzupassen. Bei Fall a) der doppelseitigen Beleuchtung wäre das die schlichte Auswahl der Richtung, die zum Betrachter hinzeigt. Bei Fall b) wird's schon spannender - entweder ich beleuchte dann den Voxel beim Rendern pro Fragment, oder ich bestimme mir eine Normale, die innerhalb der zulässigen Ebene zum Betrachter hin rotiert ist.

Meine Fragen sind also:

1) welche mathematischen Tricks und Ideen gibt es, die Normalen und Freiheitsgrade zu berechnen?

und 2) wie kodiere ich die dann? Ich werde wahrscheinlich nicht mehr mit nur 3 Komponenten pro Voxel auskommen, aber das ist eh unvermeidlich.

----------
Ich habe die selbe Frage auch im SPPRO.de gestellt, zu finden unter https://www.spieleprogrammierer.de/15-2 ... itsgraden/

[Alexander Kornrumpf]

Kannst du vielleicht kurz schildern oder verlinken, was du im Moment machst?

[Alexander Kornrumpf]

Was ich mir jetzt in 10 Minuten zusammengegooglet habe, ist dass du wahrscheinlich den Gradienten bestimmst, weil man das so macht (tm) und im degenerierten Fall mitteln sich der Gradient zur einen und der zur anderen Seite wahrscheinlich zu 0 während du im normalen Fall immer nur nach "außen" überhaupt einen Gradienten hast weil deine Objekte solide sind. Soweit richtig?

[B.G.Michi]

ohne mich groß reinzudenken zu 2): du brauchst einen Vektor (die Normale) und 2 Bit um die 4 Fälle zu unterscheiden:
--- Oberfläche (Normalfall)
--- Schicht, speichere eine Richtung und negiere bei Beleuchtung gegebenenfalls
--- Strecke, speichere die Richtung der Strecke und verwende bei der Beleuchtung eine Normale senkrecht darauf
--- Freistehend, Vektor ist irrelevant (z.B. = 0) und verwende bei der Beleuchtung eine beliebige Normale

Ob du die 2 Bit nun in die Komponenten der Normalen kodierst (z.B. in das LSB) oder eine neue Komponente aufmachst ist deine Wahl ;)
Welche Normale du bei der Beleuchtung verwendest musst du dann irgendwie aus Position des Betrachters, des Voxels/evtl. Pixels und Lichts berechnen. Aber das dürfte stark davon abhängenwie die Beleuchtung bei dir genau funktioniert

Edit zu 1): ich glaube du kannst, die Fälle 2-4, also wenn die Normalenberechnung 0 ergeben hat, durch die Anzahl der gefüllten Voxel im 3^3 Quader unterschieden:
--- Freistehend: 1 (nur das betrachtete Voxel)
--- Strecke: 3
--- Schicht: sonst
Dann kannst du die Berechnung in den 3 Fällen einzeln behandeln.

[xq]

Ich schließe mich meinem Vorredner an: Klingt durchaus sinnvoll, nur zum Edit: Wenn ich einen Voxel zwischen zwei Flächen habe:

Code: Alles auswählen

X X
XXX
X X

ist der Voxel ja eine strecke, die anzahl der nachbarn ist ja aber hier 18, man sollte als bei der generierung auch auf sowas achten.

[Schrompf]

Moin, und Danke schonmal!

im Einzelnen:

Was ich mir jetzt in 10 Minuten zusammengegooglet habe, ist dass du wahrscheinlich den Gradienten bestimmst, weil man das so macht (tm) und im degenerierten Fall mitteln sich der Gradient zur einen und der zur anderen Seite wahrscheinlich zu 0 während du im normalen Fall immer nur nach "außen" überhaupt einen Gradienten hast weil deine Objekte solide sind. Soweit richtig?

Genau das. Im Endeffekt zähle ich Nachbarvoxel durch und summiere eine davon wegzeigende Normale auf, so dass bei einem Randvoxel halt eine summierte Normale entsteht, die vom Rand wegzeigt. Bei symmetrischen Nachbarvoxel-Szenarien summiert sich die Normale aber zu 0 auf. Und für diesen Fall brauche ich eine Alternative, da der leider recht häufig auftritt.

du brauchst einen Vektor (die Normale) und 2 Bit um die 4 Fälle zu unterscheiden:
--- Oberfläche (Normalfall)
--- Schicht, speichere eine Richtung und negiere bei Beleuchtung gegebenenfalls
--- Strecke, speichere die Richtung der Strecke und verwende bei der Beleuchtung eine Normale senkrecht darauf
--- Freistehend, Vektor ist irrelevant (z.B. = 0) und verwende bei der Beleuchtung eine beliebige Normale

Eine klassische Fallunterscheidung. Hmja. Die zwei Bonusbits kriege ich noch unter. Die Zählweise ist mir aber etwas zu wackelig, weil Strecken ja auch außerhalb der drei Hauptachsen vorkommen können und dann das klassische Aliasing alle möglichen Voxelszenarien entstehen lassen könnte.

Mir dämmert gerade, dass ich das Problem evtl. schonmal gelöst habe. Für die Physikkörper-Anpassung an frei geformte Meshes habe ich bei den Splitterwelten mal eine Hauptachsen-Transformation berechnet. Dabei ermittelt man für eine Punktewolke die dominierenden Achsen, die zwar orthogonal zueinander sind, aber je nach "Signifikanz" unterschiedlich lang sind. Das Ding müsste also auch diagonale Strecken und Ebenen zuverlässig erkennen und die dritte Hauptachse dann als Null ausspucken.

Hm. Wenn ich das Ding auf eine Bresenham-Strecke loslasse, wird es aber zufällig zwischendurch mal Ebenen anstatt der Strecke erkennen. Ach mann, alles kacke. Aber immernoch besser als die jetzige Lösungen, bei der Wände in 50m Abstand durch das LOD plötzlich schwarz im Licht werden.

[Alexander Kornrumpf]

Moin, und Danke schonmal!

Genau das. Im Endeffekt zähle ich Nachbarvoxel durch und summiere eine davon wegzeigende Normale auf, so dass bei einem Randvoxel halt eine summierte Normale entsteht, die vom Rand wegzeigt. Bei symmetrischen Nachbarvoxel-Szenarien summiert sich die Normale aber zu 0 auf. Und für diesen Fall brauche ich eine Alternative, da der leider recht häufig auftritt.


Eine klassische Fallunterscheidung. Hmja. Die zwei Bonusbits kriege ich noch unter. Die Zählweise ist mir aber etwas zu wackelig, weil Strecken ja auch außerhalb der drei Hauptachsen vorkommen können und dann das klassische Aliasing alle möglichen Voxelszenarien entstehen lassen könnte.

Mir dämmert gerade, dass ich das Problem evtl. schonmal gelöst habe. Für die Physikkörper-Anpassung an frei geformte Meshes habe ich bei den Splitterwelten mal eine Hauptachsen-Transformation berechnet. Dabei ermittelt man für eine Punktewolke die dominierenden Achsen, die zwar orthogonal zueinander sind, aber je nach "Signifikanz" unterschiedlich lang sind. Das Ding müsste also auch diagonale Strecken und Ebenen zuverlässig erkennen und die dritte Hauptachse dann als Null ausspucken.

Hm. Wenn ich das Ding auf eine Bresenham-Strecke loslasse, wird es aber zufällig zwischendurch mal Ebenen anstatt der Strecke erkennen. Ach mann, alles kacke. Aber immernoch besser als die jetzige Lösungen, bei der Wände in 50m Abstand durch das LOD plötzlich schwarz im Licht werden.

Wie man n Fälle in log_2(n) Bits speichert scheint mir der triviale Teil zu sein. Der schwierige Teil scheint mir, wie dein Bresenham Bsp auch besagt, zu sein, wie man (effizient) erkennt in welchem Fall man sich befindet. Oder irre ich mich?

[Schrompf]

Wie man n Fälle in log_2(n) Bits speichert scheint mir der triviale Teil zu sein. Der schwierige Teil scheint mir, wie dein Bresenham Bsp auch besagt, zu sein, wie man (effizient) erkennt in welchem Fall man sich befindet. Oder irre ich mich?

Jupp, so ist es.

[Edit] Die Hauptachsen-Trafo könnte das erkennen. Die würde ein "ordentliches" Voxelklümpchen mit deutlicher Schieflage drei Hauptachsen ausspucken, für eine Ebene egal welcher Lage nur zwei Hauptachsen und eine dritte mit Länge nahe 0, und für eine Linie würde sie nur eine dominante Achse ausspucken, die anderen wären nahe Null. Nur macht es mir halt Sorgen, dass in so einem Mikrokosmos aus gerade mal 5x5x5 Voxeln jeder Voxel neben der Hauptachse einen signifikanten Einfluss hat, eine Strecke also in allen außen den einfachsten Fällen doch noch eine signifikante zweite Hauptachse ergäbe.

Aber nuja, das Problem betrifft dann ja nur Strecken. Der größte offensichtliche Problemfall ist aktuell die Beleuchtung von Ebenen, daher wäre das schonmal ein Fortschritt. Es wäre aber spannend, eine Lösung zu finden, die astronomisch schnell und stabil wäre.

[Alexander Kornrumpf]

Vielleicht hilft das:

Ich mach es mal in 2D. Du hast dieses Bild:

\($\begin{pmatrix}0 & 0 & 0 \\ 1 & 1 & 1 \\ 0 & 0 & 0\end{pmatrix}$\)

Jetzt willst du durch Faltung mit \($\begin{pmatrix}1\\0\\-1\end{pmatrix}$\) naiv den Gradienten für die gesetzten Pixel bestimmen [1,2] und stellst enttäuscht fest, dass der Gradient für die gesetzten Pixel immer 0 ist. Aber das ist natürlich nur die halbe Wahrheit denn für die erste und letzte Zeile des Bildes (nehmen wir einfach an, es ginge in alle Richtungen mit Nullen weiter) ist der Gradient eben nicht 0 und das Gradientenbild als ganzes wird so aussehen, wie man es naiv erwartet.

Und genau das passiert dir gerade in 3D. Wahrscheinlich wird es helfen, hilfsweise die Gradienten der nicht gesetzten Nachbarvoxel hinzuzuziehen.

P. S. Es ist dabei egal, in welcher Richtung die Kante verläuft. Darum geht es ja gerade, dass du das eigentlich gar nicht bestimmen musst.

[1]man kann auch Sobel nehmen, tut nichts zur Sache.
[2]man kann auch den Gradienten in die andere Richtung bestimmen, aber der ist trivial und gewollt 0

[Schrompf]

Du schlägst vor, dass ich die Gradienten auch für die Nachbarpixel bestimme und dann diese Gradienten zur Konfliktlösung heranziehe? Aber das würde doch genau gar nichts ändern? Damit erweitere ich effektiv nur den Suchbereich auf 5x5x5. Und das benutze ich intern eh schon, und es versagt natürlich genauso bei hinreichend freistehenden Ebenen wie z.B. bei jeder Mauer.

[Alexander Kornrumpf]

Huh? Das Gradientenbild in y Richtung in meinem Beispiel ist (Zero Padding an den Rändern unterstellend)

\($\begin{pmatrix}1 & 1& 1\\0&0&0\\-1&-1&-1\end{pmatrix}$\)

Du berücksichstigst aber nur die mittlere Zeile. Inwiefern würde es "nichts ändern" bei Betrachtung von der einen Seite die Zeile darüber und bei Betrachtung von der anderen Seite die Zeile darunter zu berücksichtigen? Das würde doch genau zum gewünschten Ergebnis führen nämlich immer dem Gradienten, der von der Wand weg zeigt.

Oder verstehe ich dein Problem doch falsch?

[Alexander Kornrumpf]

Für diagonale Wände:

\($ I = \begin{pmatrix} 1 & 0 & 0\\ 0& 1 & 0 \\ 0 & 0 & 1\end{pmatrix}$\)

\($ G_x = G_y = \begin{pmatrix} 0 & 1 & 0\\ -1& 0 & 1 \\ 0 & -1 & 0\end{pmatrix}$\)

die von 0 verschiedenen Gradienten zeigen in die jeweils richtige Richtung, d. h. \($\begin{pmatrix}1\\1\end{pmatrix}$\) bzw. \($\begin{pmatrix}-1\\-1\end{pmatrix}$\). Ist das nicht das was du wolltest?

[Schrompf]

Ich glaube, Du verstehst das Problem wirklich falsch. Ich habe jetzt keine Ahnung, was Du mit den weiteren Matrizen eigentlich sagen willst, aber wir bleiben mal beim orginalen Beispiel:

Code: Alles auswählen

0 0 0 0 0
0 0 0 0 0
1 1 1 1 1
0 0 0 0 0 
0 0 0 0 0

Ich habe das Beispiel so verstanden, dass das eine Ein-Voxel-dicke Wand ist mit nix drüber und nix drunter. Also ein gängiger Problemfall. Habe ich mal freistil auf 5x5 erweitert. Angenommen ich würde tatsächlich nur die unmittelbare 1-Voxel-Umgebung heranziehen, würde die Faltungsmatrix in etwa so aussehen.

Code: Alles auswählen

 0 - 0
 + 0 -
 0 + 0

Das angewendet auf den inneren 3x3-Bereich, auch auf die leeren Voxel, ergäbe folgendes:

Code: Alles auswählen

0 0 0 0 0
+ + + + +
0 0 0 0 0
- - - - -
0 0 0 0 0

Und wenn ich das jetzt einfach mal in die Gradientenberechnung einfließen lasse, kriege ich natürlich einen Gradienten für die Mittelvoxel raus. Nur dass der nicht neu ist, sondern sich strikt aus der Faltungsmatrix ergibt. Und er ist natürlich nutzlos, weil wir ja schon im ersten Beitrag so weit waren, dass eine einzige Normale auf dieser Wand keine korrekte Beleuchtung ergibt. Ich bräuchte an dieser Stelle zwei Normalen, oder halt ein DoubleSided-Flag. Und damit sind wir dann in der Auflistung der Sonderfälle, wie von anderen Postern vorher schon geschrieben wurde.

[Alexander Kornrumpf]

Und wenn ich das jetzt einfach mal in die Gradientenberechnung einfließen lasse, kriege ich natürlich einen Gradienten für die Mittelvoxel raus. Nur dass der nicht neu ist, sondern sich strikt aus der Faltungsmatrix ergibt.

Ich verstehe das tatsächlich nicht. Im Ausgangsposting hattest du doch noch beklagt, dass der resultierende Vektor der Nullvektor ist. Dieses Problem ist aber anscheinend hausgemacht?! Und dass der Gradient sich aus der Faltung ergibt ist ja der Grund die Faltung überhaupt zu machen. Inwiefern ist das ein Problem?

Und er ist natürlich nutzlos, weil wir ja schon im ersten Beitrag so weit waren, dass eine einzige Normale auf dieser Wand keine korrekte Beleuchtung ergibt. Ich bräuchte an dieser Stelle zwei Normalen, oder halt ein DoubleSided-Flag.

Und du bekommst zwei Normalen. Also das was du brauchst. Soweit ich das jetzt überblicke komplett generisch und ohne jede Fallunterscheidung.

Und damit sind wir dann in der Auflistung der Sonderfälle, wie von anderen Postern vorher schon geschrieben wurde.

Inwiefern?

[Schrompf]

Ich glaube, ich verstehe langsam, welches Problem Du eigentlich lösen willst.

Und wenn ich das jetzt einfach mal in die Gradientenberechnung einfließen lasse, kriege ich natürlich einen Gradienten für die Mittelvoxel raus. Nur dass der nicht neu ist, sondern sich strikt aus der Faltungsmatrix ergibt.

Ich verstehe das tatsächlich nicht. Im Ausgangsposting hattest du doch noch beklagt, dass der resultierende Vektor der Nullvektor ist. Dieses Problem ist aber anscheinend hausgemacht?! Und dass der Gradient sich aus der Faltung ergibt ist ja der Grund die Faltung überhaupt zu machen. Inwiefern ist das ein Problem?

Ja, das Problem ist "hausgemacht", weil die Normalenbestimmung auf die bisherige Art zu einfach ist und bei solchen symmetrischen Fällen kollabiert. Das steht im ersten Beitrag und ist der Grund, warum wir diese Diskussion überhaupt führen.

Deine Methode ergibt jetzt eine zweite Normale, die da einen sinnvollen Vektor ergibt, wo die erste noch 0 ist. Auch sehr gut, interessanter Gedanke. Leider ist diese Normale in 50% der Fälle falsch, weil eine Wand für eine korrekte Beleuchtung nunmal zwei Oberflächen braucht und nicht nur eine. Und das sind nicht die zwei, die wir gerade ausgerechnet haben, sondern die eine und die negierte Version der einen. Im Falle einer Ebene können wir das hier aber ableiten und über ein paar Bits in die Normale kodieren.

Und dann wäre da noch der Fall einer Strecke. Dafür brächte es dann anstatt der zwei Normalen eine beliebige Menge Normalen in einer Ebene senkrecht zum Streckenverlauf. Hier scheitert dann auch Dein Ansatz - der findet zwar eine irgendwie geartete Normale, die aber mit den tatsächlichen Erfordernissen der Beleuchtung nix mehr zu tun hat.

Da allerdings kommt mir eine Idee. Wenn man jetzt den dritten Spezialfall eines einzelnen freistehenden Voxels betrachtet, sieht man, dass die Normale für den Voxel eh schon vorher feststeht, weil man das Ergebnis ja quasi direkt in die Matrix schreibt. Kann man sich dann nicht einfach den zweiten Pass ersparen und gleich am Anfang die präsenten Nachbarvoxel irgendwie anders einrechnen? So ne Art gerichtete Vermutung oder im Gegenteil eine Unmöglichkeit eines Teils des Normalenraumes, die man irgendwie so parametrisiert bekommt, dass sie aufsummiert immernoch Sinn ergibt.

[Alexander Kornrumpf]

Deine Methode ergibt jetzt eine zweite Normale, die da einen sinnvollen Vektor ergibt, wo die erste noch 0 ist. Auch sehr gut, interessanter Gedanke. Leider ist diese Normale in 50% der Fälle falsch, weil eine Wand für eine korrekte Beleuchtung nunmal zwei Oberflächen braucht und nicht nur eine. Und das sind nicht die zwei, die wir gerade ausgerechnet haben, sondern die eine und die negierte Version der einen.

Ich verstehe das Problem immer noch nicht. In den Fällen, die wir gerade ausgerechnet haben sind die Normalen zu beiden Seiten der Wand jeweils die negierten Versionen voneinander.

Im Falle einer Ebene können wir das hier aber ableiten und über ein paar Bits in die Normale kodieren.

Ja, das verstehe ich schon. Die Frage ist was letztlich effizienter ist. Eine Version die erst erkennen muss dass es sich um eine Ebene handelt und von da aus Bitfrickelt, oder eine generische, die mehr Normalen berechnet und speichert.

Und dann wäre da noch der Fall einer Strecke. Dafür brächte es dann anstatt der zwei Normalen eine beliebige Menge Normalen in einer Ebene senkrecht zum Streckenverlauf. Hier scheitert dann auch Dein Ansatz - der findet zwar eine irgendwie geartete Normale, die aber mit den tatsächlichen Erfordernissen der Beleuchtung nix mehr zu tun hat.

Ähm, mein Ansatz war purely 2d. Die Erweiterung auf 3D steht noch aus. Ich finde das in 3D schwer zu visualisieren aber ich sehe nicht warum es in 3D nicht gehen sollte.

[Alexander Kornrumpf]

Ich hab mir den Spaß gemacht, das grad mal tu implementieren. Das erste Bild ist einfach eine Wand. Das zweite Bild ist das Ergebnis wenn man Pixel, die einen von Null verschiedenen Gradienten haben und auf der oberen linken Seite der Wand liegen, aus der oberen linken Ecke beleuchtet. Im Prinzip kommt da schon das raus was ich erwarten würde. Was halt nur passiert, ist dass die erleuchteten Pixel im Vergleich zur Wand verschoben sind. Aber das kann man ja lösen.

Ich bin ziemlich sicher dass das in 3d genauso funktioniert, nur ist das ätzender zu implementieren, deswegen habe ich es nicht gemacht.

test.png (411 Bytes) 4311 mal betrachtet

out.png (612 Bytes) 4311 mal betrachtet

[Alexander Kornrumpf]

Und nochmal von unten rechts beleuchtet, damit man sieht, dass die Normalen auf beiden Seiten passen:

out.png (547 Bytes) 4305 mal betrachtet