Vertex Smoothing

[blackfin]

Hallo Experten,

ja, ich weiss, das was jetzt kommt, ist nicht wirklich eine Delphi-Frage, sondern eine allgemein mathematische.
Da ich aber damals im Geometrieunterricht lieber darüber nachgedacht habe, wie ich an Sylvester aus einer RedBull-Dose einen Vulkan baue oder den Stadtbrunnen einfärbe, anstatt dem netten Herren vorne zuzhören,schaue ich nun mit meinem Problem so dumm aus der Wäsche wie ein Schwälblein wenn es blitzt.
Es geht nämlich um:

Vertex Smoothting in einem Terrain.
Das klingt nun erst einmal überkanditelt, ist es auch, aber das tut ja nichts zur Sache, dass ich es nicht hinbekomme, egal wie cool es klingt...:)

Das Problem ist eigentlich recht simpel:

Ich habe ein Grid mit lauter Vertices, alle haben eine bestimmte Höhe, alles zusammen bildet eine Landschaft.
Nun kann es sein, dass vieler Übergänge zwischen den Terrains zu "stufig" und zu hart sind.
Ich würde das ganze gerne weicher haben, also "smoothen" (sowas wie dieser unsägliche "TurboSmooth" im 3dsMax)
Nun habe ich allerdings keine grosse Ahnung, mit welchem Algorithmus man ein Terrain "weicher" machen kann.

Irgendwie muss ich die einzelnen Steigungen zwischen den Vertices wohl berechnen und anpassen...aber wie genau...?

P.S.:
Wenn die Fragestellung Mist ist, dann bratet mir gleich eins über! Ich versuche dann, das Ganze nochmal etwas besser zu beschreiben.... :cyclops:


Edit:
Ich habe mal einen Screenshot angehängt, um das Problem zu verdeutlichen.
Der "Berg" auf dem Bild ist viel zu eckig. Nun möchte ich einen Algorithmus drüber laufen lassen, der die einzelnen Höhen etwas natürlicher und weicher macht.
Mir gehts jetzt auch nicht um "gebt mir den Code, ich bin zu faul dafür", sondern um allgemeine Ansätze, wie man so etwas bewerkstelligt.

[Hubi89]

Heyho blackfin,

da gibt es mehrere Möglichkeiten. Ich weiß jetzt nicht, wie tief du in der Materie steckst und kann deinem Bild dazu auch wenig entnehmen, aber um die ganze Sache "weicher" zu machen könntest du folgendes probieren:

- Falls du es nicht schon tust, kannst du mal Lichtberechnungen mit interpolierten Normalen probieren (Stichwort phong). Dies ändert natürlich an der Geometrie selber nichts, aber lässt die ganze Sache schon viel "weicher" wirken(http://en.wikipedia.org/wiki/File:Ph...ing-sample.jpg).
- Du könntest versuchen anstatt nur jeweils einen Wert pro Pixel aus der Heightmap zu lesen eine Art "sub-sampling" durchzuführen, indem du ein "enzelnes Pixel" weiter unterteilst und die Werte durch bilineare Filterung bestimmst.
- Es gibt auch Algorithmen, die Meshes nach bestimmten Vorschriften verfeinern, dazu könntest du als Startpunkt mal http://en.wikipedia.org/wiki/Catmull...vision_surface nehmen und dich informieren was es da alles gibt.
- Stichwort Geometry-Shader und Tesselation? Sollten das die neuen Dx11 Grakas nicht von Haus aus können? Kenn mich da aber leider gar nicht aus, vllt hat da jemand anders mehr Ahnung.

Hoffe, ich konnte dir weiterhelfen.

Gruß
Hubi

[Medium]

Und die Lösung, die dir vermutlich vorschwebte, nennt sich Filterung, und ist von einem Blur-Filter wie bei Bitmaps kaum zu unterscheiden ;). Zu Blur-Filtern finden sich wohl einige Quellen in der DP (Blur, Smooth(ing), Weichzeichnen/-er, Gauss (Filter) - alles passende Suchbegriffe), und diese wendest du dann statt auf Pixel eines Bitmaps, auf die Y-Koordinaten deiner Vertices an.

Edit: Aber aufpassen! Wenn dein Mesh von oben gesehen nicht ein regelmäßiges Gitter ist, musst du X und Z mit beachten für die Faktoren, wodurch ein paar schöne Optimierungen durch LUTs weg fallen.

Das wäre, besonders wenn man einen Gauss-Filter nimmt, der übliche Weg um ein Mesh zu "smoothen", ohne etwas am Shading zu machen, und wobei die Topologie völlig unangetastet bleibt (vorausgesetzt, man betrachtet die Länge der Verbindungen in einem Netz nicht der Topologie zugehörig :stupid: )

Hubis Vorschläge sind nicht falsch, aber
1) Setzt hier an der falschen Stelle an, da über diesen Ansatz, wie er schrieb, die Geometrie unangetastet bleibt, und du hast definitiv ein Problem in der Geometrie. Weitet man die Idee aber aus, so lässt sich das o.g. Filtering dank Adjacency-Infos tatsächlich im Shader machen, allerdings nur im Geometry-Shader. (Und mit viel Trickserei sogar noch im Vertex-Shader, aber auch nur unter OGL, und auch nur wenn im VS Texture-Reads zugelassen sind - was nicht gerade so der Standard ist. Oooooder wenn man Unmengen an TexCoords dazu dichtet, die die Adjacency-Infos tragen - auch bitter :))

2) Fällt unter Tesselation

3) Dito

4) Tesselation! :D Von "Haus aus" können sie das nicht wirklich, man muss den Shader schon noch selber bauen, wo man dann u.a. 2) und 3) implementieren könnte. (Zumindest ist mir nichts der Art bekannt, ich bin aber bei den aller neusten Chips auch nicht mehr ganz so up to date.) Aber den Geometry-Shader (und somit Adjacency-Infos frei Haus) gibt's erst seit DX10. Allerdings bringt glaube ich der eine oder andere Treiber so eine Option für generische Tesselation mit. Die kann einem dann aber auch gewaltig in die Suppe spucken kann ich mir vorstellen, da man ja so gar keine Kontrolle drüber hätte.


Lange Rede, kurzer Pin: Was du im Hinterkopf hast, ist fast sicher einfaches Filtering. Und das muss bei statischen Meshes zum Glück nur ein Mal gemacht werden, d.h. es tut sogar eine langsame (lesbare) implementierung =)

Oh, es gibt noch eine Variante die teilweise angewendet wird, eine iterative: Diffusion. Wenn ich nicht völlig irre, nähert Gauss-Filterung aber Diffusion an, und das iterative Verfahren ist nur nötig, wenn man Grenzen innerhalb des Feldes hat, über die nicht hinaus diffundiert werden darf, bzw. Materialen unterschiedlicher "Leitfähigkeit" dabei sind (bei dir z.B. Sand und Stein in einem Mesh, und du willst Erosion "faken"). (Ja, diese Erosion wäre nicht wirklich realistisch, aber zu einem gewissen Grad sehr ähnlich - nur falls da einer gleich mit kommt ;))

[Hubi89]

Filtering hab ich ja ganz vergessen^^
So einfach kanns sein...

[blackfin]

Hui.....

erstmal Danke für die Antworten! :hello:

An sowas ähnliches wie nen Gauss-Filter hatte ich schon gedacht, dann werde ich die Idee wohl mal aufgreifen und rumbasteln :)

Geometrie-Shader will ich allerdings nicht einsetzen, da mir die Technik noch zu "neu" ist und die Leute, die das "Viech" dann benutzen sollen, teilweise eine solche Grafikkarte noch gar nicht besitzen. Es ist mir schon fast zuviel, SM3 einzusetzen, aber da komm ich nicht drumrum :)

Die Idee mit dem Phong-Shading und dem Normal mapping halte eigentlich für ziemlich gut, aber wie ja medium bereits gesagt hat, geht es mir erstmal nur um die Geometrie an sich. Verschönern und faken kann man das dann immer noch :) Ansätze sind dafür auch schon vorhanden.

Subdivision Surfaces kann ich allerdings nicht anwenden, da ich damit das Terrain weiter unterteilen müsste und das will ich nicht :)
Generell ist das sicher eine gute Idee, aber wenn dann nur im Nahbereich oder für Non-Realtime-Rendering. (meine Meinung :)

Naja, lange rede kurzer Sinn..ich werd dann erstmal den alten Gauss bemühen und schauen, ob er nicht allzu "grantig" wird, wenn ich den Algorithmus verwurschtel :angel2:
Über Erosions-Emulation will ich erstmal gar nicht nachdenken, das übersteigt meine Fähigkeiten dann doch etwas *hust* :gruebel:

Edit:

Ich schreibe definitiv zuviele Smilies....

[blackfin]

Update:

Der Tipp mit dem (aktuell jetzt nicht wirklich Gaussian, weil zu langsam) Blur hat wunderbar funktioniert :D
Jetzt weiss ich glaub ich, wie Blizzard bei WoW seine Terrains erstellt hat :mrgreen:

Den Erfolg will ich euch natürlich auch nicht vorenthalten: Aktuell ein (untexturiertes) Bild Vorher <-> Nachher.

Überseht mal einfach den Vertex-Fehler in der Mitte, da ist noch ein böses Z-Fighting im Gange, aber da hab ich ja auch schon was dagegen....

[Mithrandir]

Cool... :)

Darf man fragen, wofür du das brauchst?

[Medium]

Das macht was her! Und es schaut, auch in der Texturierung, wirklich recht WoWig aus :D

Die meisten Terrain-Generatoren dürften es auch sehr ähnlich machen: Irgend eine Noise-Funktion (klassisch Perlin Noise) als Heightmap, weichzeichnen und Vertices draus züchten. Schaut immer wieder schmuck aus :)

[blackfin]

Zitat:

Darf man fragen, wofür du das brauchst?

Naja..."brauchen" ist hier eigentlich niht der richtige Begriff.

Ich bastel mir gerade einen kleinen World-/Terrain-Editor mit OpenGL zusammen.
Es gilt für mich in erster Linie, dabei etwas zu lernen.
Wie macht man so etwas, wie ist die Art und Weise, an so etwas heranzugehen.
Ich habe dabei selbst keine so grossen Hoffnungen, dass das Ganze wirklich sowas wie eine Engine wird, weil die Arbeit an so etwas wirklich uferlos ist, aber wenn ich Zeit und Muße habe, bastel ich einfach gerne daran herum :)

Inspiriert hat mich dazu, muss ich zugeben wie viele, World of Warcraft.
Jetzt liegt es mir wirklich fern, so etwas in der Art "nachzuprogrammieren" (haha, dazu bräuchte es wohl 100 Leute und 10 Jahre Zeit...),
aber ich möchte einfach mal wissen, wie so etwas generell aufgebaut ist, und natürlich...ob so etwas mit Delphi überhaupt möglich ist.
Und das scheint es ja zu sein :) Zumindest, was die Grafik-Engine davon angeht.

Zitat:

Das macht was her

Danke *froi* :) Aber der Held des Moments bist ja eher du selbst, denn du hast mich auf die richtige Idee mit dem alten Gauss gebracht :D


Edit:

Anbei noch ein Screenshot von der zugehörigen "Spiel-Engine" (*hust* naja..also....der Begriff ist eigentlich mächtig überzogen, mehr als rumlaufen kann man da nicht..und bis es mehr wird, werden wohl noch Jahre vergehen..*g*)

[Medium]

:shock: Alter Lachs, das sieht wirklich 1a aus! Und von wegen Idee... die war ja nicht mal neu, und die Umsetzung hat sicherlich mehr Schmalz erfordert als einfach mal "Gauss" zu stammeln ;). Das sieht echt schon nach riiichtig viel Arbeit drin aus, mein Respekt ist dir sicher! (Bin bei Spaß-/Lernprojekten selten so ausdauernd. Wenn "proof of concept", dann fertig :stupid: )

[blackfin]

Uhhh...das ist ja nun fast beschämend :oops: Danke! *s*
Naja, viel Arbeit steckt schon drin, das stimmt...aber alles ist noch mehr als weit davon entfernt, irgendwie zu etwas zu taugen *g*

[Mithrandir]

Ich will eine Demo! :firejump:

[blackfin]

Zitat:

Ich will eine Demo!

Hehe, die will ich selbst auch :) Aber bis dahin wird noch ein wenig (viel) Wasser die Donau runterlaufen...

[blackfin]

Ich nutz diesen Thread jetzt einfach ab jetzt, um mal ein paar Updates reinzuschreiben :)

Mein Shadow-Raycaster und der Pseudo-Fog funktionieren nun auch langsam aber sicher, hier ein aktueller Screenshot aus der "Engine" <-- *hust*



Ich glaube aber, dass ich wohl bald wieder hier eine Frage stellen muss....dazu muss ich aber noch überlegen, wie ich die Frage am geschicktesten Stelle, ohne dass ich mich selbst in eine Sackgasse manövriere....

Aber, Medium, mach dich schonmal bereit :mrgreen:

[Mithrandir]

Cool. :shock:

[blackfin]

Und wieder ein paar Screen-Updates :)
Langsam wird es was...

[Mithrandir]

*sabber*

Wie war das jetzt eigentlich mit der Demo?... :stupid:

[blackfin]

Zitat:

Wie war das jetzt eigentlich mit der Demo?

Jaaa, ich weiss :oops::oops: Die bin ich noch schuldig...
Mal sehen, wenn ich es schaffe, das ganze relativ schnell in eine Demo zu packen, bekommste die auch :)

[Mithrandir]

:firejump:

[turboPASCAL]

Ich hätt auch gern eine Demo bittö...

[blackfin]

Wenn ich eine mache, stelle ich die hier rein!
Wird aber noch n bißchen dauern...*s*
Und erwartet keine Wunder, so toll ist das Ding nämlich gar nicht :D