Prozedurale Oberflächen, How-Not-To

Für Fragen zu Grafik APIs wie DirectX und OpenGL sowie Shaderprogrammierung.
Benutzeravatar
Schrompf
Moderator
Beiträge: 4838
Registriert: 25.02.2009, 23:44
Benutzertext: Lernt nur selten dazu
Echter Name: Thomas Ziegenhagen
Wohnort: Dresden
Kontaktdaten:

Prozedurale Oberflächen, How-Not-To

Beitrag von Schrompf »

Moin,

inspiriert vom Aktuelle-Fortschritte-Thread sammle ich mal lose all die Sachen, die mir zum Thema "Oberflächen prozedural generieren" einfallen. Als erstes das runde Unterteilen bzw. die Subdivision: ich habe einiges ausprobiert und wieder verworfen und bin am Ende bei dieser Methode gelandet:

p1, p2, p3 - Eckpunkte des Dreiecks
nf - Flächennormale
n1, n2, n3 - Normalen der Eckpunkte
p - der aktuell betrachtete Punkt auf dem Dreieck.
dp - Offset des Punktes, damit die resultierende Fläche "rund" ist

Die Formel, die ich jetzt einsetze, sieht so aus:

Code: Alles auswählen

float k1 = dot( n1, p - p1), k2 = ...;
vec3 n = normalize( n1 + s * (n2 - n1) + t * (n3 - n1));
float k = k1 + s * (k2 - k1) + t * (k3 - k1);
p += -0.701f * k * n;
Die 0.701 sind eigentlich 1/sqrt(2), das hab ich anhand irgendeines Beispiels ausgerechnet. Aber als ich das mal visualisar, stall ich bald fest, dass entweder die Gewichtung nicht linear oder das Prinzip komplett falsch ist. So sieht das in meinem kleinen 2D-Software-Renderer aus:
rundunterteilung_falsch.gif
oder als Image auf meinem Server
Bild

Das eine muss man anklicken, um es bewegt zu sehen, das andere ist bei den meisten Leuten unsichtbar, weil https-Seite auf http-Content verweist. Grmpf. Bei Gelegenheit kümmere ich mich mal darum.

Ich formel das jetzt mal durch und guck, ob es vielleicht nur ne Quadrierung oder so braucht oder ob sowas hässliches wie arctan() rauskommt
Früher mal Dreamworlds. Früher mal Open Asset Import Library. Heutzutage nur noch so rumwursteln.
Benutzeravatar
Krishty
Establishment
Beiträge: 8229
Registriert: 26.02.2009, 11:18
Benutzertext: state is the enemy
Kontaktdaten:

Re: Prozedurale Oberflächen, How-Not-To

Beitrag von Krishty »

Schrompf hat geschrieben: 05.04.2021, 19:24Das eine muss man anklicken, um es bewegt zu sehen, das andere ist bei den meisten Leuten unsichtbar, weil https-Seite auf http-Content verweist. Grmpf. Bei Gelegenheit kümmere ich mich mal darum.
AFAIk hat Chromanoid sich schon gekümmert; dein Bild wird via senky auf zfx.info dupliziert und animiert bei mir auch direkt :)
[/ot]
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Benutzeravatar
Jonathan
Establishment
Beiträge: 2352
Registriert: 04.08.2004, 20:06
Kontaktdaten:

Re: Prozedurale Oberflächen, How-Not-To

Beitrag von Jonathan »

Hm, was genau sieht man und woran machst du fest, ob das gut ist oder nicht?

Ich schätze mal links/rechts das sind irgendwelche Oberflächennormalen und die mittleren Pfeile geben an, wohin sich ein Punkt verschiebt? Aber werden die äußeren Pfeile nicht durch die nächsten Linien definiert? D.h. du müsstest eigentlich einen 3-teiligen Linienzug interpolieren?

Der Text liest sich, als sei das Ergebnis kaputt, aber es sieht für mich zumindest erstmal rund und nicht offensichtlich kaputt aus und da mir nicht ganz klar ist, was genau du versuchst zu erreichen, ist mir auch nicht klar, wie man beurteilt ob das Ergebnis gut oder schlecht ist.

Aber generell: Ist sowas nicht ein gelöstes Problem? Ich meine, würde man sich nicht einfach das Catmull-Clark Paper raussuchen, das auch Blender nachimplementiert? Geht es dir um die kreative Bastelei, oder hast du besondere Anforderungen?
Lieber dumm fragen, als dumm bleiben!
https://jonathank.de/games/
Benutzeravatar
Schrompf
Moderator
Beiträge: 4838
Registriert: 25.02.2009, 23:44
Benutzertext: Lernt nur selten dazu
Echter Name: Thomas Ziegenhagen
Wohnort: Dresden
Kontaktdaten:

Re: Prozedurale Oberflächen, How-Not-To

Beitrag von Schrompf »

Nuja, so ist es in meinem Dungeon jetzt implementiert, und für die meisten Fälle geht das schon, aber für mich ist es falsch.

a) Die roten Pfeile links und rechts sind die Vertexnormalen. Die weiße Linie ist die gekrümmte Fläche. Im Idealfall ist diese resultierende Fläche direkt an den Punkten genau so geneigt, wie es die Normale vorschreibt, und dazwischen kontinuierlich. Das heißt zum Beispiel, wenn die linke Normale nach außen geneigt ist, ist die weiße Linie direkt darunter senkrecht dazu, geht dann nach rechts nach einem Hügel zu einer Asymptote über, die x-parallel unter der rechten Normale endet.

Catmull-Clark muss ich mal googeln. Ich bin notorisch miserabel darin, Paper nachzuvollziehen. Die Leute geben sich immer furchtbar viel Mühe, die eigentlichen Wirkprinzipien hinter zwei metrischen Tonnen Theorie-Gefasel zu verstecken - ich dringe da selten durch. Aber vielleicht gibt's dazu ja was, was auch Normalsterbliche verstehen.
Früher mal Dreamworlds. Früher mal Open Asset Import Library. Heutzutage nur noch so rumwursteln.
Benutzeravatar
Jonathan
Establishment
Beiträge: 2352
Registriert: 04.08.2004, 20:06
Kontaktdaten:

Re: Prozedurale Oberflächen, How-Not-To

Beitrag von Jonathan »

Ah ja, dann ist es tatsächlich falsch, weil die Normale ja ziemlich deutlich nicht mehr senkrecht ist.

Zur Lektüre: Es müsste da eigentlich auf jeden Fall etwas geben, was sehr anwendungsorientiert ist. Wir hatten früher in den Computergraphik Einführungsvorlesungen ein wenig darüber gesprochen. In Richtung Splines gibt es da ja auch ganz viel und gerade sowas wie der https://de.wikipedia.org/wiki/De-Casteljau-Algorithmus ist eigentlich sehr anschaulich.

Eine Frage wäre natürlich auch, wie wichtig Geschwindigkeit ist. Soll das in Echtzeit (und im Shader) ablaufen, oder als Vorberechnungsschritt? Im letzteren Fall dürfte Geschwindigkeit ja fast egal sein, selbst wenn man es sehr naiv und 10x langsamer als die Referenz implementiert wäre es dann ja immer noch sehr schnell.

Ich hab mal schnell "Catmull-Clark for dummies" gesucht und gleich folgenden Link gefunden:

http://www.rorydriscoll.com/2008/08/01/ ... he-basics/

Habs jetzt nicht ganz gelesen, aber es scheint mir sehr anschaulich erklärt zu sein, wie man für jede Iteration die neuen Vertexe berechnet. Vermutlich ist das schwierigste eine effiziente Darstellung des Trianglemeshes um schnell an die benötigten Nachbarn zu kommen. Vielleicht will man sowas wie die Winged-Edge Darstellung dafür verwenden:

https://en.wikipedia.org/wiki/Winged_edge


[Edit] Am besten zuallererst nochmal in Blender oder so anschauen, was Catmull-Clark macht und ob es das ist, was du willst. Im Prinzip hast du diskrete Iterationsschritte, die jeweils die Anzahl der Eckpunkte ver-x-fachen, du hast also nicht unbedingt super viel Kontrolle über die Auflösung und so. Außerdem funktioniert es z.B. mit Quads besser als mit (potentiell sehr deformierten) Triangles. Das sieht man gut, wenn man in Blender mal entsprechend hässliches Meshes bastelt. [/edit]
Lieber dumm fragen, als dumm bleiben!
https://jonathank.de/games/
Alexander Kornrumpf
Moderator
Beiträge: 2106
Registriert: 25.02.2009, 13:37

Re: Prozedurale Oberflächen, How-Not-To

Beitrag von Alexander Kornrumpf »

Schrompf hat geschrieben: 05.04.2021, 20:48 Die roten Pfeile links und rechts sind die Vertexnormalen. Die weiße Linie ist die gekrümmte Fläche. Im Idealfall ist diese resultierende Fläche direkt an den Punkten genau so geneigt, wie es die Normale vorschreibt, und dazwischen kontinuierlich. Das heißt zum Beispiel, wenn die linke Normale nach außen geneigt ist, ist die weiße Linie direkt darunter senkrecht dazu, geht dann nach rechts nach einem Hügel zu einer Asymptote über, die x-parallel unter der rechten Normale endet.
Was zeigt die Visualisierung? Wenn das die Normalen sind, die du ausgerechnet hast, ist das Problem ja eher nicht dass die Kurve nicht zu den normalen passt, sondern, dass diese Normalen nicht stimmen können, weil sie zwischendurch mal nach Rechts zeigen müssen um den gewünschten Verlauf hinzubekommen.

Es sieht auf dem Bild so aus als würdest du die Richtung der Normalen zwischen den beiden Enden linear interpolieren und es ist ja offensichtlich (?) dass das nicht funktionieren kann.

Die Formel verstehe ich leider nicht bzw. ich kann sie nicht mit der Erklärung der Symbole dadrüber in Einklang bringen.
Benutzeravatar
Schrompf
Moderator
Beiträge: 4838
Registriert: 25.02.2009, 23:44
Benutzertext: Lernt nur selten dazu
Echter Name: Thomas Ziegenhagen
Wohnort: Dresden
Kontaktdaten:

Re: Prozedurale Oberflächen, How-Not-To

Beitrag von Schrompf »

Vielen Dank erstmal für die ganzen Anregungen. Das Material dazu werde ich mir morgen anschauen. Ich habe jetzt ausgehend von der Halbkreisformel y = sqrt(1 - x²) eine Formel gebastelt, die bei symmetrisch ausgelenkten Vertexnormalen exakt den dazugehörigen Halbkreis reproduziert. Sieht dann so aus:

Bild

Die Formel ist allerdings kompliziert und wird durch mangelnde Beschriftung nicht besser. Links und rechts die Vertizes mit der jeweiligen Normale, dazwischen die gerundete Kante, jetzt korrekt auf beiden Seiten mit exakt der Steigung, die die Normale vorgibt. Die Formel enthält jetzt ne Fallunterscheidung gegen 0 und mehrere Wurzeln - das ist ausnehmend fäkalisch, und rein optisch gibt's zumindest für die Fallunterscheidung auch keinen erkennbaren Grund. Schau ich mir bei Gelegenheit nochmal mit frischem Kopf an.
Früher mal Dreamworlds. Früher mal Open Asset Import Library. Heutzutage nur noch so rumwursteln.
Alexander Kornrumpf
Moderator
Beiträge: 2106
Registriert: 25.02.2009, 13:37

Re: Prozedurale Oberflächen, How-Not-To

Beitrag von Alexander Kornrumpf »

Ich habe das mal spaßeshalber analytisch für den einfachsten möglichen 2d Fall durchgerechnet.

Wir sind uns wahrscheinlich einig, dass ein Polynom mindestens kubisch sein muss, um den gewünschten Verlauf zu haben. Also:

f(x) ax^3 + bx^2 + cx + d

Sagen wir der Einfachkeit halber die beiden Enden sind an 0 und 1 und die Funktion ist dort jeweils 0, gibt uns:

d = 0 und a+b+c=0

Sagen wir auch der Einfachkeit halber die Ableitung ist am Anfang 1 (45° Tangente) und am Ende (wie in deinem Beispiel) 0, gibt uns:

c = 1 und 3a+2b+1 =0

Zweite Ableitung muss das Vorzeichen wechseln (daher mindestens kubisch) ich glaube man braucht das später nicht mehr, aber gibt uns der Vollständigkeit halber:

b < 0 und 6a+2b > 0

Mit ein bisschen rumrechnen (oder Scharfes hinschauen):

a = 1; b= -2; c=1; d=0;

Plot sieht im Abschnitt 0 bis 1 richtig aus:

https://www.wolframalpha.com/input/?i=f ... 2x%5E2%2Bx

Weiß nicht ob das hilft. Ist halt der einfachste Fall, den ich mir überlegen konnte.
joeydee
Establishment
Beiträge: 1039
Registriert: 23.04.2003, 15:29
Kontaktdaten:

Re: Prozedurale Oberflächen, How-Not-To

Beitrag von joeydee »

Ich würde da kubische Bezier-Interpolation nehmen (inwiefern sich das mit schon genannten Lösungen oder Catmull oder anderen deckt wollte ich jetzt nicht recherchieren). Ist im Prinzip simpel. Auseinandergenommen betrachtet nur eine Reihe Vektor-Lerps.
Evtl. hast du das sogar schonmal betrachtet und verworfen, weil du dir dachtest, deine Kurve soll ja durch die Mesh-Punkte gehen, und bei Bezier geht sie an Stützpunkten vorbei. Ne, geht aber:
- Du hast v0 und v1 und die Normalen n0, n1 dieser Punkte.
- Du konstruierst einen virtuellen Punkt a0 auf der Oberflächentangente bei v0 in Richtung v1 (a0=v0+vec(n0.y, -n0.x)*f0)
- Dasselbe für v1 in Richtung v0 (a1=v1+vec(-n1.y,n1.x)*f1)
- f0/f1 bestimmt die Krümmungseigenschaft an den Meshpunkten, es gibt ja nicht nur ein Lösung. Das könnte also durchaus ein Vertex-Parameter sein um den lokalen Look zu kontrollieren. Ansonsten bin ich meist bei ca. 1/3 der Strecke v0-v1 für die Tangentenlängen.
Interpolation im Detail (t von 0-1):
- zuerst die Strecken v0-a0-a1-v1 interpolieren:
a=lerp(v0,a0,t);
b=lerp(a0,a1,t);
c=lerp(a1,v1,t);
- dann die Strecken a-b-c interpolieren:
d=lerp(a,b,t);
e=lerp(b,c,t);
- dann d-e interpolieren:
final=lerp(d,e,t);
ferdsch.
Kann man in eine Formel zusammenfassen, darf jeder selbst frickeln, mach ich jetzt nicht mehr. Stattdessen gibts noch Screens.
Grün: Normalen (hellgrün sind die Versatz-Wege), Blau: Tangenten mit gegebener Länge (Endpunkte sind a0 bzw. a1)
Screen2: das passiert, wenn eine Tangente länger wird. Alle Bedingungen erfüllt, aber andere Kurve.
Screen 3&4: Ändern der linken Normalen.
bezier01.jpg
bezier02.jpg
bezier03.jpg
bezier04.jpg
joeydee
Establishment
Beiträge: 1039
Registriert: 23.04.2003, 15:29
Kontaktdaten:

Re: Prozedurale Oberflächen, How-Not-To

Beitrag von joeydee »

Hier noch ergänzend der Code, wenn man alle lerps einsetzt und Klammern auflöst:

Code: Alles auswählen

        
        
        //Tangentenpunkte für v0, n0 und v1, n1
            float d = (v1 - v0).Length;
            Vector4 ta0 = new Vector4(n0.Y, -n0.X, 0, 0);
            Vector4 ta1 = new Vector4(-n1.Y, n1.X, 0, 0);
            Vector4 a0 = v0 + ta0 * d * 0.3f;
            Vector4 a1 = v1 + ta1 * d * 0.3f;

        //cubic bezier interpolation
        Vector4 qlerp(Vector4 v0, Vector4 a0, Vector4 a1, Vector4 v1, float t)
        {
            float s = 1 - t;
            float f0 = s * s * s;
            float f1 = 3 * s * s * t;
            float f2 = 3 * s * t * t;
            float f3 = t * t * t;
            return v0 * f0 + a0 * f1 + a1 * f2 + v1 * f3;
        }

pps:
Benutzeravatar
Jonathan
Establishment
Beiträge: 2352
Registriert: 04.08.2004, 20:06
Kontaktdaten:

Re: Prozedurale Oberflächen, How-Not-To

Beitrag von Jonathan »

Alexander Kornrumpf hat geschrieben: 05.04.2021, 22:55 Ich habe das mal spaßeshalber analytisch für den einfachsten möglichen 2d Fall durchgerechnet.

Wir sind uns wahrscheinlich einig, dass ein Polynom mindestens kubisch sein muss, um den gewünschten Verlauf zu haben. Also:

f(x) ax^3 + bx^2 + cx + d

Sagen wir der Einfachkeit halber die beiden Enden sind an 0 und 1 und die Funktion ist dort jeweils 0, gibt uns:

d = 0 und a+b+c=0

Sagen wir auch der Einfachkeit halber die Ableitung ist am Anfang 1 (45° Tangente) und am Ende (wie in deinem Beispiel) 0, gibt uns:

c = 1 und 3a+2b+1 =0

Zweite Ableitung muss das Vorzeichen wechseln (daher mindestens kubisch) ich glaube man braucht das später nicht mehr, aber gibt uns der Vollständigkeit halber:

b < 0 und 6a+2b > 0

Mit ein bisschen rumrechnen (oder Scharfes hinschauen):

a = 1; b= -2; c=1; d=0;

Plot sieht im Abschnitt 0 bis 1 richtig aus:

https://www.wolframalpha.com/input/?i=f ... 2x%5E2%2Bx

Weiß nicht ob das hilft. Ist halt der einfachste Fall, den ich mir überlegen konnte.
Ich würde das so motivieren: Wir kennen 2 Punkte (links und rechts) und zwei Ableitungen (durch die Normalen links und rechts) und suchen jetzt eine Funktion, die hinreichend nett ist und diese 4 Kriterien erfüllt. -> 4 Bedingungen -> 4 Freiheitsgrade -> Polynom dritten Grades.

Aber das Problem ist, dass Polynome Funktionen sind und keine Kurven. Eine ganz wichtige Eigenschaft bei so Interpolationen ist, dass die invariant unter affinen Transformatione (gemeint sind: Verschiebungen, Skalierung, Drehung, Scherung) sein sollten. Ein Polynom kann man aber nicht 90 Grad drehen und es explodiert schon viel früher.


Was Splines (da gibt es ja diverse Sorten von) im Wesentlich machen ist, dass man eine Menge an Kontrollpunkten hat und die Splines definieren dir die Gewichte für Interpolation zwischen diesen Punkten (z.B. über Polynome, ->Bernsteinpolynome). Dadurch funktionieren affine Transformationen automatisch, da sie sich ja nur auf die Kontrollpunkte auswirken und nicht auf die Gewichte.
Lieber dumm fragen, als dumm bleiben!
https://jonathank.de/games/
Benutzeravatar
Zudomon
Establishment
Beiträge: 2253
Registriert: 25.03.2009, 07:20
Kontaktdaten:

Re: Prozedurale Oberflächen, How-Not-To

Beitrag von Zudomon »

Wird mal Zeit, der Theorie hier ein Gesicht zu geben 😂
Hier also Catmull-Clark und kubische Bezier im Vergleich.

Ich bin aber schnell zu quadratische Bezierkurven übergegangen, weil 9 zu 16 Kontrollpunkte schon eine Ersparnis war und das Ergebnis fast genauso aussah. Bin mir auch nicht mehr ganz sicher, ob das im Screenshot schon Quadratische sind.

Catmull-Clark:

viewtopic.php?p=15519#p15519
20110121_2.jpg
Kubische Bezier:

viewtopic.php?p=22300#p22300
20110823b.jpg
Benutzeravatar
Jonathan
Establishment
Beiträge: 2352
Registriert: 04.08.2004, 20:06
Kontaktdaten:

Re: Prozedurale Oberflächen, How-Not-To

Beitrag von Jonathan »

joeydee hat geschrieben: 06.04.2021, 08:35
Die Animation ist super, da sieht man eigentlich direkt alles.

Das Problem an Bezierkurven ist nur (wie man dort sieht), dass sie nicht durch die äußeren Kontrollpunkte laufen. Für Splines berechnet man daher aus den Punkten durch die die Kurve laufen soll die Kontrollpunkte (P0-P3) im ersten Schritt und Interpoliert diese dann wie gezeigt im zweiten Schritt.


Aber generell erzeugt dir all das natürlich sehr glatte Oberflächen. Vermutlich will man ja eher sowas wie Sand oder Rinde oder Steine erzeugen. Ich habe damit keine Erfahrung aber ich glaube man könnte vielleicht einfach prozedural eine 2D Heightmap generieren und diese dann z.B. auf eine solche glatte Interpolation der Punkte anwenden. Spätestens dann dürfte es aber nicht mehr Echtzeit sein, weil es für solche Heightmaps wohl nur in Ausnahmefällen hübsche analytische Darstellungen gibt und man vermutlich eher in einem mehrstufigen Prozess (als Kombination unterschiedlicher Operatoren) tatsächlich die Textur generiert.
Lieber dumm fragen, als dumm bleiben!
https://jonathank.de/games/
Alexander Kornrumpf
Moderator
Beiträge: 2106
Registriert: 25.02.2009, 13:37

Re: Prozedurale Oberflächen, How-Not-To

Beitrag von Alexander Kornrumpf »

Jonathan hat geschrieben: 06.04.2021, 09:26 Ich würde das so motivieren: Wir kennen 2 Punkte (links und rechts) und zwei Ableitungen (durch die Normalen links und rechts) und suchen jetzt eine Funktion, die hinreichend nett ist und diese 4 Kriterien erfüllt. -> 4 Bedingungen -> 4 Freiheitsgrade -> Polynom dritten Grades.

Aber das Problem ist, dass Polynome Funktionen sind und keine Kurven. Eine ganz wichtige Eigenschaft bei so Interpolationen ist, dass die invariant unter affinen Transformatione (gemeint sind: Verschiebungen, Skalierung, Drehung, Scherung) sein sollten. Ein Polynom kann man aber nicht 90 Grad drehen und es explodiert schon viel früher.


Was Splines (da gibt es ja diverse Sorten von) im Wesentlich machen ist, dass man eine Menge an Kontrollpunkten hat und die Splines definieren dir die Gewichte für Interpolation zwischen diesen Punkten (z.B. über Polynome, ->Bernsteinpolynome). Dadurch funktionieren affine Transformationen automatisch, da sie sich ja nur auf die Kontrollpunkte auswirken und nicht auf die Gewichte.
Ja, danke. Ich habe noch nie was mit Bezier-Kurven oder Splines selbst programmiert, ergab sich irgendwie nicht. Für mein persönliches ästhetisches Empfinden sehen Bezier-Kurven "immer" falsch aus, aber darum geht es ja hier nicht.

Mein Eindruck war, dass Schrompf aus irgendeinem Grund nicht Bezier implementiert sondern versucht sich das ganze selbst aus first principles herzuleiten und ich wollte mich vor allem selbst testen, ob ich den ersten Schritt einer solchen Überlegung "noch" hinbekommen. Mir ist schon klar, dass ich da nur Oberstufenmathematik gebastelt habe und das, wie du ja auch weiter oben schreibst, ein gelöstes Problem ohne weitere Geheimnisse ist. Mir hilft selber rechnen trotzdem manchmal beim Verstehen.
Alexander Kornrumpf
Moderator
Beiträge: 2106
Registriert: 25.02.2009, 13:37

Re: Prozedurale Oberflächen, How-Not-To

Beitrag von Alexander Kornrumpf »

Zudomon hat geschrieben: 06.04.2021, 09:36 Wird mal Zeit, der Theorie hier ein Gesicht zu geben 😂
Vielleicht sollten wir erst nochmal klären, was eigentlich das Problem ist, das Schrompf versucht zu lösen. Ich hatte es so verstanden, dass er beliebige Punkte und Normalen vorgeben will und der Algorithmus soll dann die Landschaft approximieren, die dadurch bestimmt wird.

Einen Würfel rund aussehen zu lassen erscheint mir wie ein wesentlich einfacheres Problem. Und wir du selbst schreibst ist es ja auch fast egal, wie man das technisch macht, weil es für das Gehirn sowieso immer einigermaßen gleich aussieht.
joeydee
Establishment
Beiträge: 1039
Registriert: 23.04.2003, 15:29
Kontaktdaten:

Re: Prozedurale Oberflächen, How-Not-To

Beitrag von joeydee »

Jonathan hat geschrieben: 06.04.2021, 09:39 Das Problem an Bezierkurven ist nur (wie man dort sieht), dass sie nicht durch die äußeren Kontrollpunkte laufen.
Müssen sie ja auch nicht. Nur P0 und P3 sind Bestandteile des Meshes(!). P1 und P2 ergeben sich durch die Normale an P0 und P3. Daher haben sie bei mir auch ganz andere Namen.
Weit verbreiteter Irrtum ist "die Kurve läuft ja gar nicht durch meine Meshpunkte, also unbrauchbar". Hatte ich ja extra deswegen erwähnt.

Alexander Kornrumpf hat geschrieben: 06.04.2021, 10:03 Vielleicht sollten wir erst nochmal klären, was eigentlich das Problem ist, das Schrompf versucht zu lösen.
So wie ich verstehe:
Einer zu unterteilenden Meshoberfläche kontinuierlich verlaufende "Normalen" (sind sie ja dann nicht mehr) zuweisen, anhand derer Richtungen er problemlos einen prozeduralen (oder Heightmap-) Offset draufsetzen kann, ohne dass sich das an Ecken in Wohlgefallen auflöst.
Dabei soll die neue 0-Oberfläche a) durch die ursprünglichen Meshpunkte gehen und b) die dort ursprüngliche interpolierte Normale haben.
Um dem Problem näherzukommen, hat er das auf 2D und 2 Punkte mit 2 verschiedenen Normalen heruntergebrochen.
Benutzeravatar
Zudomon
Establishment
Beiträge: 2253
Registriert: 25.03.2009, 07:20
Kontaktdaten:

Re: Prozedurale Oberflächen, How-Not-To

Beitrag von Zudomon »

Alexander Kornrumpf hat geschrieben: 06.04.2021, 10:03 Vielleicht sollten wir erst nochmal klären, was eigentlich das Problem ist, das Schrompf versucht zu lösen.
Dachte, es wäre ganz hilfreich, mal die hier vorgeschlagenen Verfahren (also Catmull und Bezier) direkt zu veranschaulichen, da ich zufälligerweise genau diese damals implementiert hatte. Joeydee hat ja auch schon beschrieben, wie man die Bezierkurven mit den Kontrollpunkten anwenden kann.

Außerdem hat Schrompf schon im Showroom gesagt, was er damit vor hat:
Schrompf hat geschrieben: 03.04.2021, 11:53 Basismesh ist eine klassische DungeonMaster-artige TileMap aus 2m-Würfeln [...] hey Meshes nur aus rechteckigen zueinander senkrechten Flächen wären doch ein super Testballon für meine Oberflächengenerierungs-Lib.
Als ich damals seine Idee hier präsentiert habe, hat mich Schrompf sogar für den reißerischen Titel gelobt ❤
viewtopic.php?p=47180#p47180
Benutzeravatar
Schrompf
Moderator
Beiträge: 4838
Registriert: 25.02.2009, 23:44
Benutzertext: Lernt nur selten dazu
Echter Name: Thomas Ziegenhagen
Wohnort: Dresden
Kontaktdaten:

Re: Prozedurale Oberflächen, How-Not-To

Beitrag von Schrompf »

Wow, ihr geht ja ab. Vielen vielen Dank nochmal.

Was will ich eigentlich tun: einen groben Mesh rund unterteilen/subdividen/tesselieren, damit ich eine kontinuierliche bruchfreie Arbeitsbasis habe, auf der ich Details auftragen kann. Der letzte Teil kommt später.

Das hier ist die 2D-Vereinfachung des eigentlichen 3D-Problems, nämlich ein Dreieck anhand der drei Eck-Normalen rund zu unterteilen. Und ich hoffe, dass ich die Formeln, die hier zusammengetragen wurden, dann mit ein bisschen Augen-Zusammenkneifen in den 3D-Raum übertragen kann.

Warum keine Bezier-Patches: ich hab mich an den Namen erinnert, es bei Google eingegeben und bin in den CS-Kursen diverser amerikanischer Unis rausgekommen, die mich heillos überfordert haben. Und da ich schon immer lieber Zeug im Kopf umhergeschoben habe, bis es passt, anstatt die Theorie dahinter zu verstehen, habe ich an der Stelle die Bezier-Patches wieder aufgegeben.

Performance: das hier ist Vorverarbeitung. Solange das Ergebnis im Release-Build nach ein paar Sekunden verfügbar ist, ist das ok. Und es hat sich jetzt bereits herausgestellt, dass es völlig wurscht ist, wieviel Rechenschritte ich pro Vertex mache, weil die Berechnung der Texturen hinterher alles in den Schatten stellt.
Früher mal Dreamworlds. Früher mal Open Asset Import Library. Heutzutage nur noch so rumwursteln.
Alexander Kornrumpf
Moderator
Beiträge: 2106
Registriert: 25.02.2009, 13:37

Re: Prozedurale Oberflächen, How-Not-To

Beitrag von Alexander Kornrumpf »

joeydee hat geschrieben: 06.04.2021, 10:55 Müssen sie ja auch nicht. Nur P0 und P3 sind Bestandteile des Meshes(!). P1 und P2 ergeben sich durch die Normale an P0 und P3. Daher haben sie bei mir auch ganz andere Namen.
Weit verbreiteter Irrtum ist "die Kurve läuft ja gar nicht durch meine Meshpunkte, also unbrauchbar". Hatte ich ja extra deswegen erwähnt.
Für bestimmte Werte von "ergeben sich" :) Wenn ich es richtig verstehe bekommst du dadurch zwei zusätzliche Freiheitsgrade nämlich wie weit du die Stützpunkte entlang der Tangente [Edit: war "Normale"] nach außen ziehst.
Alexander Kornrumpf
Moderator
Beiträge: 2106
Registriert: 25.02.2009, 13:37

Re: Prozedurale Oberflächen, How-Not-To

Beitrag von Alexander Kornrumpf »

Zudomon hat geschrieben: 06.04.2021, 11:16 Dachte, es wäre ganz hilfreich, mal die hier vorgeschlagenen Verfahren (also Catmull und Bezier) direkt zu veranschaulichen, da ich zufälligerweise genau diese damals implementiert hatte.
Wäre es bestimmt. Meiner Anschauung war leider durch deine Screenshots nicht geholfen, aber das ist ja Geschmackssache.
Ich könnte auf Basis deiner Screenshots jetzt keine Entscheidung treffen, welche Technik Schrompf verwenden "sollte". Kannst du?
Als ich damals seine Idee hier präsentiert habe, hat mich Schrompf sogar für den reißerischen Titel gelobt ❤
Einer von uns beiden muss seinen Sarkasmusdetektor neu kalibrieren.
Benutzeravatar
Zudomon
Establishment
Beiträge: 2253
Registriert: 25.03.2009, 07:20
Kontaktdaten:

Re: Prozedurale Oberflächen, How-Not-To

Beitrag von Zudomon »

Alexander Kornrumpf hat geschrieben: 06.04.2021, 12:21
joeydee hat geschrieben: 06.04.2021, 10:55 Müssen sie ja auch nicht. Nur P0 und P3 sind Bestandteile des Meshes(!). P1 und P2 ergeben sich durch die Normale an P0 und P3. Daher haben sie bei mir auch ganz andere Namen.
Weit verbreiteter Irrtum ist "die Kurve läuft ja gar nicht durch meine Meshpunkte, also unbrauchbar". Hatte ich ja extra deswegen erwähnt.
Für bestimmte Werte von "ergeben sich" :) Wenn ich es richtig verstehe bekommst du dadurch zwei zusätzliche Freiheitsgrade nämlich wie weit du die Stützpunkte entlang der Normale nach außen ziehst.
Nein, die Stützpunkte P1 und P2 werden nicht entlang der Normale nach außen gezogen. Sie sitzen zwischen P0 und P3. P0 zu P1 steht senkrecht zur Normale, gibt also die Tangente zum Punkt P0 wieder. P3 zu P2 entsprechend, nur dass dieser Vektor negiert ist.
Der Freiheitsgrad ist theoretisch aber in der Tat vorhanden, letztendlich ist es aber am besten, wenn man die Länge P0-P1 und P2-P3 fest bestimmt... nämlich auf 33% und 66% der Strecke zwischen P0 und P3.
Allerdings sollte man da vielleicht noch beachten, dass man diese Werte noch mittelt, wenn auch noch andere Linien (später dann Flächen) anschließen. Wichtig ist, dass die Ableitungen erhalten bleiben. Angenommen man baut jetzt mehrere Strecken hintereinander P0 P1 P2 P3 und Q0 Q1 Q2 Q3, wo dann P3 und Q0 den selben Punkt referenzieren, dann sollte eben P3 zu P2 genauso lang gewählt werden wie Q0 zu Q1.
Zuletzt geändert von Zudomon am 06.04.2021, 12:46, insgesamt 1-mal geändert.
Benutzeravatar
Zudomon
Establishment
Beiträge: 2253
Registriert: 25.03.2009, 07:20
Kontaktdaten:

Re: Prozedurale Oberflächen, How-Not-To

Beitrag von Zudomon »

Alexander Kornrumpf hat geschrieben: 06.04.2021, 12:25
Zudomon hat geschrieben: 06.04.2021, 11:16 Dachte, es wäre ganz hilfreich, mal die hier vorgeschlagenen Verfahren (also Catmull und Bezier) direkt zu veranschaulichen, da ich zufälligerweise genau diese damals implementiert hatte.
Wäre es bestimmt. Meiner Anschauung war leider durch deine Screenshots nicht geholfen, aber das ist ja Geschmackssache.
Ich könnte auf Basis deiner Screenshots jetzt keine Entscheidung treffen, welche Technik Schrompf verwenden "sollte". Kannst du?
Kommt letztendlich darauf an, was er am Ende dann tatsächlich erreichen will. Er hat ja kurz nach meinem Post auch selbst nochmal genauer definiert, was er möchte. Bin ich jetzt allerdings nicht so 100% draus schlau geworden.
Wenn es sich um Würfelflächen handelt, wie ich angenommen hatte, naja, da hab ich dann für Bezier entschieden, weil man da jede Fläche Aufgrund der Kontrollpunkte beliebig verfeinern kann ohne Nachbarschaften zu berücksichtigen. Bei Catmull Clark war doch pro Iteration ein Subdivide und dann ein Smooth Schritt nötig. Das verwende ich für normale Geometrie immer noch.
Allerdings spiele ich bei meiner nächsten StoneQuest Engine mit dem Gedanken eventuell wieder auf das normale Subdivide für die Voxelwelt zurück zu greifen. Bin mir da selbst noch extrem unschlüssig.
Alexander Kornrumpf
Moderator
Beiträge: 2106
Registriert: 25.02.2009, 13:37

Re: Prozedurale Oberflächen, How-Not-To

Beitrag von Alexander Kornrumpf »

Zudomon hat geschrieben: 06.04.2021, 12:33 Nein, die Stützpunkte P1 und P2 werden nicht entlang der Normale nach außen gezogen.
Du hast komplett recht, ich habe Tangente im Bild gesehen, Tangente gedacht und Normale geschrieben. In 2d sind Tangente und Normale ja eindeutig bis auf Vorzeichenkonvention durch einander bestimmt insofern denke ich man kann verstehen, was ich meinte. Ich denke es ist eine Frage des jeweiligen Hintergrundes ob man es intuitiver findet in Begriffen von Tangenten oder Normalen zu denken, mathematisch ist es wegen obiger Eigenschaft dasselbe.

Das was 3d Grafiker "Normale" nennen ist ja oft (meistens?) auch gar keine Normale im mathematischen Sinne, z. B. war es früher üblich die Normalen der angrenzenden Dreiecke an den Eckpunkten zu mitteln und das Ergebnis "Normale" zu nennen. Weiß nicht wie sich der State of the Art da weiter entwickelt hat.
letztendlich ist es aber am besten, wenn man die Länge P0-P1 und P2-P3 fest bestimmt... nämlich auf 33% und 66% der Strecke zwischen P0 und P3.
"am besten" mit Bezug worauf?
Benutzeravatar
Zudomon
Establishment
Beiträge: 2253
Registriert: 25.03.2009, 07:20
Kontaktdaten:

Re: Prozedurale Oberflächen, How-Not-To

Beitrag von Zudomon »

Alexander Kornrumpf hat geschrieben: 06.04.2021, 12:45 [...] ich habe Tangente im Bild gesehen, Tangente gedacht und Normale geschrieben.
Ah okay, das erklärt es natürlich 😀

Aber was du schreibst, dass die 3D Grafiker da nochmal eine andere Definition haben war mir nicht bekannt... darauf wollte ich mich auch nicht beziehen.
Wobei eine gemittelte Normale würde ich auch Normale nennen... das wird ja für Gouraud Shading verwendet. Allerdings würde ich das dann Vertexnormale nennen, die entsprechend von den Dreiecksnormalen abweicht. Im eigentlichen ist das ja immer noch die Senkrechte, zumindest wenn die angrenzenden Dreiecke nicht zu sehr Kanten/Ecken bilden.
Alexander Kornrumpf hat geschrieben: 06.04.2021, 12:45
letztendlich ist es aber am besten, wenn man die Länge P0-P1 und P2-P3 fest bestimmt... nämlich auf 33% und 66% der Strecke zwischen P0 und P3.
"am besten" mit Bezug worauf?
In Bezug auf die Stetigkeit. Ich kann das auch nicht mathematisch fundiert darlegen. Bin da ja auch eher wie Schrompf, "schieben bis es passt" (hat meine Mathelehrerin immer gesagt).
Aber nicht falsch verstehen, die 33% und 66% waren nur auf die Länge bezogen. Die Richtung der Vektoren MUSS der Tangente entsprechen.
joeydee
Establishment
Beiträge: 1039
Registriert: 23.04.2003, 15:29
Kontaktdaten:

Re: Prozedurale Oberflächen, How-Not-To

Beitrag von joeydee »

Alexander, man bekommt keine "zusätzlichen" Freiheitsgrade. Die Problemstellung per se hat diese Freiheitsgrade, ich kann eine ganze Kurvenschar durch die beiden Punkte malen, die die Normalenbedingung erfüllen. Welchen Wert ich als Standard benutze, und worauf er sich bezieht, steht da.
Alexander Kornrumpf
Moderator
Beiträge: 2106
Registriert: 25.02.2009, 13:37

Re: Prozedurale Oberflächen, How-Not-To

Beitrag von Alexander Kornrumpf »

joeydee hat geschrieben: 06.04.2021, 13:39 Alexander, man bekommt keine "zusätzlichen" Freiheitsgrade. Die Problemstellung per se hat diese Freiheitsgrade, ich kann eine ganze Kurvenschar durch die beiden Punkte malen, die die Normalenbedingung erfüllen. Welchen Wert ich als Standard benutze, und worauf er sich bezieht, steht da.
Ich will nicht zu sehr in Spitzfindigkeiten verfallen. Wir sind uns ja total einig, dass man diese Parameter gegeben die beiden Punkte und die beiden Tangentenrichtungen im Prinzip frei wählen kann, und das ist ja die Hauptsache.
Benutzeravatar
Schrompf
Moderator
Beiträge: 4838
Registriert: 25.02.2009, 23:44
Benutzertext: Lernt nur selten dazu
Echter Name: Thomas Ziegenhagen
Wohnort: Dresden
Kontaktdaten:

Re: Prozedurale Oberflächen, How-Not-To

Beitrag von Schrompf »

screenshot0029.png
Warum nimmst Du nicht einfach Bezier-Dreiecke, haben sie gesagt. Das ist doch auserfunden, haben sie gesagt.
Früher mal Dreamworlds. Früher mal Open Asset Import Library. Heutzutage nur noch so rumwursteln.
Benutzeravatar
Schrompf
Moderator
Beiträge: 4838
Registriert: 25.02.2009, 23:44
Benutzertext: Lernt nur selten dazu
Echter Name: Thomas Ziegenhagen
Wohnort: Dresden
Kontaktdaten:

Re: Prozedurale Oberflächen, How-Not-To

Beitrag von Schrompf »

Hab einfach die Gewichtung vergessen. Die ausformulierte Bezier-Dreieck-Funktion hat Faktoren vor einigen der Stützpunkte. Dann noch einen Copy&Paste-Fehler gefixt und ist es Bezier-Rund. Man sieht jetzt aber auch ganz hübsch, dass senkrecht aufeinander stehende Grobklötze evtl. eine schlechte Ausgangsbasis für Subdivision sind. Egal, geht schon.

vorher:
Bild

nachher: [edit] Vorzeichenfehler ausgerechnet im mittleren Stützpunkt, jetzt ist es wirklich final.
Bild
Früher mal Dreamworlds. Früher mal Open Asset Import Library. Heutzutage nur noch so rumwursteln.
Benutzeravatar
Schrompf
Moderator
Beiträge: 4838
Registriert: 25.02.2009, 23:44
Benutzertext: Lernt nur selten dazu
Echter Name: Thomas Ziegenhagen
Wohnort: Dresden
Kontaktdaten:

Re: Prozedurale Oberflächen, How-Not-To

Beitrag von Schrompf »

So, jetzt zum nächsten Thema. Ich packe jetzt ein Noise drauf, sowohl als Auslenkung entlang der gerundeten Normale als auch rein virtuell in die NormalMap. Und da sieht man echt unschöne Muster.
screenshot0030.png
Ich *glaube*, das liegt an meiner extrem sparsamen Implementation von SimplexNoise. Ich habe nämlich exakt 2³ Zufallswerte, aus denen ich trilinear sample. Das ergibt zwar schönes Optimierungspotential in der Berechnung, aber ich glaube, daher stammen auch diese wirklich gut sichtbaren Streifen. Mit ein bisschen Augen-Zusammenkneifen kann man die einzelnen Oktaven auseinanderhalten.

Ich hoffe mal, es ist nur das, und probiere jetzt 8³ oder 16³
Früher mal Dreamworlds. Früher mal Open Asset Import Library. Heutzutage nur noch so rumwursteln.
Alexander Kornrumpf
Moderator
Beiträge: 2106
Registriert: 25.02.2009, 13:37

Re: Prozedurale Oberflächen, How-Not-To

Beitrag von Alexander Kornrumpf »

Die nun deutlich sichtbare Diagonale im ehemals zylindrischen Teil ist gewollt?
Antworten