Einfache Landschaft - Algorithmus

Badestrand

Hi!

Ich bastele gerade an der Darstellung einer Landschaft in OpenGL herum. Dabei hat mein Testfeld eine Größe von 20x20 Feldern, jedes davon hat einen Farbwert und eine Höhen-Koordinate. Der Farbwert ist erstmal egal, das klappt ganz gut. Aber die Höhendarstellung würde ich gerne anders machen: Zur Zeit mache ich's so, dass ich jedes Feld in 5 Punkte (Ecken plus Mitte) unterteile, jeder Punkt hat eine Normale und seine Koordinaten (x/y/z).
Die z-Koordinaten der Ecken eines Feldes werden aus dem Durchschnitt der 4 herumliegenden Felder berechnet. Da immer zwei Eckpunkte plus Mittelpunkt ein Dreieck bilden (eins der 4 Faces), berechne ich die Normalen der Eckpunkte aus dem Durchschnitt der 4 Normalen der Faces. Die Mittelpunkts-Normale wird aus dem Durchschnitt der vier umgebenden Eck-Normalen gebildet.
Schön und gut, das Ganze sieht so aus: Nr 1 und Nr 2.

Ich hätte es eigentlich gern, wenn die Hügelketten nicht so im Zick-Zack wären und es gibt ein paar Einbuchtungen die mir nicht gefallen, weiß zufällig jemand einen guten Algorithmus um solche Sachen hübsch darzustellen? Achso, und mein Ziel-Feld hat ~40k Felder und auch größere und mehr Höhenunterschiede (hier nur Höhe 0 oder 1).

Mit bestem Dank,
Badestrand

__Stefan__

Wieso machst du das Gitter nicht so?

v--v
| /|
|/ |
v--v

CStoll

Von welchen dieser Punkte hast du denn die Höhenwerte vorgegeben? Die Feld-Mittelpunkte oder die Ecken?

(btw, vielleicht sieht die Darstellung besser aus, wenn du auch noch die Kanten-Mittelpunkte einbeziehst)

hellihjb

die geschichte mit dem zusaetzlichen eckpunkt in der mitte taugt generell wenig.
ausgehend von der darstellung von __Stefan__ hast du zwischen 4 eckpunkten 5 kanten. durch einen zusaetzlichen eckpunkt teilst du die mittlere kante in zwei kuerzere, alle anderen kanten bleiben aber erhalten - dafuer hast du aber doppelt so viele polygone.
erhoehe also lieber die gesamtaufloesung des rasters.
dann trianguliere deine vierecke entlang der kleinsten differenz zwischen zwei eckpunkten:

v--v    v--v
| /| => |\ |
|/ |    | \|
v--v    v--v

Badestrand

Hm, ich glaube ich hab mich ein wenig unverständlich ausgedrückt Also, ich hab ein Gitter vorgegeben mit x*y Feldern, jedes Feld hat dabei auch eine Höhenangabe, mehr nicht. Jedes Feld unterteile ich in 4 Polygone, dazu nehme die x/y-Koordinate des Feldes als Mittelpunkt (in der Zeichnung das 'x'), die Eckpunkte sind einfach +-0.5 vom Mittelpunkt entfernt (und sind ja nicht vorgegeben, die führe ich also ein).

v-------v-------v-------v
| \   / | \   / | \   / |
|   x   |   x   |   x   |
| /   \ | /   \ | /   \ |
v-------v-------v-------v
| \   / | \   / | \   / |
|   x   |   x   |   x   |
| /   \ | /   \ | /   \ |
v-------v-------v-------v

Stefan schrieb:

Wieso machst du das Gitter nicht so?
v--v
| /|
|/ |
v--v

Im Moment hab ich's ja höher aufgelöst, da würde ich ungerne weiter heruntergehen. Oder wie meinst du das mit der Zeichnung?

CStoll schrieb:

Von welchen dieser Punkte hast du denn die Höhenwerte vorgegeben? Die Feld-Mittelpunkte oder die Ecken?

Vom Mittelpunkt, bzw einfach vom Feld als solchen. Ich hab da prinzipiell keine Vorgaben, sondern lade aus einer Datenbank die Datensätze, jeder Datensatz enthält eine x- und y-Koordinate und hat ein Höhenattribut, was ich anhand der Kartenauflösung (kartographiertes Teilgebiet von Indonesion) auf eine z-Koordinate umrechne.

hellihjb schrieb:

die geschichte mit dem zusaetzlichen eckpunkt in der mitte taugt generell wenig.
ausgehend von der darstellung von __Stefan__ hast du zwischen 4 eckpunkten 5 kanten. durch einen zusaetzlichen eckpunkt teilst du die mittlere kante in zwei kuerzere, alle anderen kanten bleiben aber erhalten - dafuer hast du aber doppelt so viele polygone.
erhoehe also lieber die gesamtaufloesung des rasters.

Hm ja, ich hab ja eigentlich nicht die Eckpunkte, sondern die Mittelpunkte! Und vieeeel weiter auflösen als jetzt kann ich das auch nicht, sonst kommen ältere PCs nicht mehr hinterher.

crashterpiece

quadratische interpolation wäre auch möglich, verringert den knickeffekt

hellihjb

nochmal kurz zu erklaerung:
in deinem beispiel hast du ein raster aus 20x20 punkten plus deren mittelpunkte -
macht 19x19x4=1444 triangles.
laesst du die mittelpunkte weg und nimmst stattdessen (zum beispiel) ein raster von 28x28 eckpunkten, haettest du 27x27x2=1458 triangles (also circa die gleiche polygonmenge) und effektiv mehr "aufloesung" weil die kanten zwischen zwei eckpunkten kuerzer sind.

rapso

hellihjb schrieb:

trianguliere deine vierecke entlang der kleinsten differenz zwischen zwei eckpunkten

das duerfte das resultat im verhaeltnis zum aufwand am meisten steigern.

Badestrand

@hellihjb: Cool, das hab ich verstanden! Nur, ich weiß nicht, wie ich mein Raster von 20x20 auf (z.B.) 28x28 bringen soll. Oder einfach irgendwie hochskalieren? Die Eingangsdaten sind leider fix, die kann ich nicht verändern

rapso schrieb:

hellihjb schrieb:

trianguliere deine vierecke entlang der kleinsten differenz zwischen zwei eckpunkten

das duerfte das resultat im verhaeltnis zum aufwand am meisten steigern.

Hört sich ja gut an Unter "triangulieren" hab ich nur das gefunden, kommt das hin und kann ich dann auch noch jedem Dreieck, was auf einem Feld liegt, eine bestimmte Farbe zuweisen? Und so ganz versteh ich die Technik auch nicht (ist für mich der erste Ausflug in die 3D-Welt), gibt es da konkrete Algorithmen oder Erklärungs-Anleitungen zu?

Ansonsten schonmal vielen Dank an alle!

rapso

damit meint er nur, dass du statt im fest vorgegebenem muster, also z.b.

v0--v1
|  / |
| /  |
v2--v3

auch erwegen sollst

v0--v1
| \  |
|  \ |
v2--v3

zu verwenden.
je nachdem ob zwischen v1-v2 oder v0-v3 der abstand/unterschied kleiner ist.

Badestrand

Achso, super Dann brauch ich ja auch nur 2 statt 4 Dreiecken pro Feld, vielleicht skalier ich dann meine Felder auf das Doppelte hoch, weil ich ja auch die Umgebungs-z-Werte mit einberechne. Naja, ich probier mal ein wenig herum, muchas muchas gracias!