Generieren von Dreiecken aus einem quadratischen Raster

7

Ich habe ein quadratisches 2D-Raster mit Werten, die Geländehöhen darstellen, und ich möchte aus diesem Raster Dreiecke generieren, um eine 3D-Ansicht des Geländes zu erstellen. Mein erster Gedanke war, jedes Quadrat diagonal in zwei Dreiecke zu teilen, aber die geteilte Diagonale ist deutlich zu sehen, besonders von oben:

Dreiviertelansicht Draufsicht

Gibt es eine empfohlene Möglichkeit, Dreiecke zu generieren, um diesen Effekt zu entfernen / zu reduzieren?

vivi
quelle
Wie haben Sie aus Neugier das Gelände gefärbt? Haben Sie einen Shader geschrieben, der Farben basierend auf der Höhe zuweist? (Ich bin immer noch ein Anfänger im modernen OpenGL).
Wardd
@wardd Ich setze einfach die Farbe des Scheitelpunkts auf einen Wert, der von der Höhe abhängt, und OpenGL führt beim Zeichnen der Dreiecke eine lineare Interpolation durch (eigentlich verwende ich OpenGL ES 1.1, also keine Shader für mich :))
vivi

Antworten:

3

Ihr Terrain erinnert mich an das Übungsbeispiel (Höheninterpolation), das im Kapitel Delaunay-Triangulationen (PDF) von Computational Geometry: Algorithms and Applications verwendet wird . Obwohl sie aus einer Höhenkarte ein unregelmäßiges Dreiecksnetz erzeugen, gilt der Teil an unzulässigen Kanten möglicherweise immer noch für Ihr reguläres Dreiecksnetz.

Die Idee ist, dass es zwei Möglichkeiten gibt, die Kante für jeweils vier benachbarte Gitterscheitelpunkte umzudrehen (ich werde diese später als Quad bezeichnen ). Sie definieren eine Kante als illegal, wenn wir den kleinsten Winkel lokal vergrößern können, indem wir diese Kante umdrehen . Das Kapitel führt dann zur Verwendung einer Delaunay-Triangulation, um ein unzulässiges kantenfreies Netz zu erhalten. Da Sie jedoch ein reguläres Gitter haben, können Sie ausreichen, indem Sie alle Quads durchlaufen und die Teilungskante anhand der Länge wie folgt festlegen:

def get_triangles(quads):
    # quad layout:
    # 0--1
    # |  |
    # 3--2 
    for quad in quads:
        if quad[0] - quad[2] < quad[1] - quad[3]:
            # NW-SE edge is shortest
            yield triangle(quad[0],quad[2],quad[3]) # lower-left triangle
            yield triangle(quad[1],quad[2],quad[0]) # upper-right triangle
        else:
            # NE-SW edge is shortest
            yield triangle(quad[1],quad[2],quad[3]) # lower-right triangle
            yield triangle(quad[0],quad[1],quad[3]) # upper-left triangle

Die Wahl der kürzesten Spaltkante sollte zu einem natürlicheren Gelände mit relativ geringem Arbeitsaufwand führen.

Bonus: Mit viel mehr Arbeit können Sie noch besser arbeiten, indem Sie die globalen Merkmale Ihrer Höhenkarte wie Gipfel, Grate, Täler und Entwässerungswege berücksichtigen. Eine Einführung finden Sie in Abschnitt 3.2 und 3.5 dieses Artikels: Digitale Höhenmodelle: Übersicht und ausgewählte TIN-Algorithmen .

Eric
quelle
1
Ich habe es gerade versucht, es ist merklich besser, besonders in den Flussbetten: imgur
vivi
5

Es wird für Sie nicht gut aussehen, wenn Sie das Netz nicht feiner tessellieren (verwenden Sie mehr Dreiecke, verwenden Sie ein größeres Gitter und lassen Sie die Höhenänderungen viel langsamer werden).

Ihre Normalen sind ein bisschen aus. Um geglättete Normalen an einem Scheitelpunkt zu finden, müssen Sie an jedem Scheitelpunkt mehrere Kreuzprodukte nehmen , die gefundenen Normalen summieren und diese Normalen dann normalisieren.

Zum Beispiel,

Geben Sie hier die Bildbeschreibung ein

Hier würden Sie die Vektoren finden a, b, c, d, und die normalen in der Mitte Scheitel wäre:

n1 = a x b
n2 = b x c
n3 = c x d
n4 = d x a

finalNormal = (n1 + n2 + n3 + n4).normalize()

Sie könnten auch die anderen 4 (diagonalen) Vektoren verwenden, aber das ist wirklich übertrieben. Wenn Sie 4 Vektoren verwenden, sieht es fast so aus, als würden Sie 8 Vektoren verwenden.

Bobobobo
quelle
Ich denke, mit einer glatten Schattierung wird das Netz selbst bei der in den Bildern angezeigten Tesselation ziemlich gut ausfallen.
Kevintodisco
OK, ich fange an zu verstehen. Es ist sinnvoll zu berücksichtigen, dass die Normalen eine Eigenschaft der Geländescheitelpunkte und nicht der Dreiecke sind, wie ich dachte. Vielleicht sollte ich meinen Geländegenerator auch die Normalen produzieren lassen. Ich denke, ich bin auch verwirrt über die Tatsache, dass Scheitelpunktnormalen mit glatter Schattierung verwendet werden müssen und mit flacher Schattierung seltsam aussehen. Nach deinem Rat (siehe hier (imgur) ) ist es definitiv viel besser. Ich denke, die lineare Interpolation schneidet es einfach nicht für das Gelände, und die einzige Lösung besteht darin, überhaupt mehr Geländedatenpunkte zu berechnen.
Vivi
Sie sind gleichwertig. Hier finde ich die Normalen genauso effektiv wie die Durchschnittsnormalen der 4 Quads, die den Scheitelpunkt umgeben. Wenn Sie die 8-Vektor-Lösung verwenden, erhalten Sie effektiv die durchschnittliche Normalen der 8 Dreiecke, die den Scheitelpunkt umgeben.
Bobobobo
2

Ich kann mir ein paar Ansätze vorstellen, hier ein paar in der Reihenfolge der erforderlichen Arbeit (aber wahrscheinlich mehr Qualität)

Erstens: alternative Kantenrichtung; Dies sollte einfach zu implementieren sein

.---.---.---.    .---.---.---.
| / | / | / |    | / | \ | / |
'---'---'---' -> '---'---'---'
| / | / | / |    | \ | / | \ |
'---'---'---'    '---'---'---'

Zweitens: Wählen Sie die Kantenrichtung basierend auf der Kantenlänge. Überprüfen Sie, ob / oder \ kürzer ist, und wählen Sie das aus - oder das längere. Testen Sie und sehen Sie, was besser aussieht. Das Schlechte an diesem Ansatz ist, dass er etwas mehr Arbeit erfordert.

Drittens: Implementieren Sie einen Algorithmus zum "Drehen von Kanten". Für jede Kante finden Sie zwei Dreiecke (auf beiden Seiten der Kante), die ein Viereck bilden. Die Kante, die das Quad teilt, kann "gedreht" werden, um zwei verschiedene Dreiecke zu bilden. Beachten Sie, dass die "drehbaren" Kanten die ursprünglichen horizontalen und vertikalen Kanten enthalten. Führen Sie mehrere Durchgänge über die Geometrie aus, um die Kantenlängen zu minimieren.

Viertens: Verwerfen Sie zunächst Quadrate, und während Ihre Quelldaten möglicherweise noch quadratisch sind, probieren Sie sie einfach für die Höhenwerte aus, die auf einem Stichprobenalgorithmus basieren. Punktabtastung ist in Ordnung, wenn Sie Ihre Quelldaten zuerst ganz nach oben skalieren.

Nach dem Verwerfen von Quadraten werden die Dinge interessanter. Welche Art von Netz soll verwendet werden? Sechsecke? Unterteilte Polygone basierend auf dem Rauschen innerhalb der Polygone (flache Bereiche verwenden also weniger Polys als holprige)? Zufällige Daten?

Vielleicht möchten Sie auch den Klassiker "Texturierung & Modellierung, prozeduraler Ansatz" ( http://www.amazon.com/Texturing-Modeling-Third-Edition-Procedural/dp/1558608486 ) aufgreifen

Jari Komppa
quelle
Ich verwende aus Gründen des Gameplays ein quadratisches Netz, aber tatsächlich ist mein Algorithmus zur Geländegenerierung eine Funktion R ^ 2 -> R. Vielleicht habe ich den Anfängerfehler gemacht, zu denken: "Ich möchte A erreichen, aber ich denke, B ist ein guter Weg." um A zu machen, werde ich fragen, wie man B macht, anstatt zu fragen, wie man A macht ".
Vivi
0

Basierend auf dem von Ihnen bereitgestellten Bild würde ich sagen, dass Sie auf dem richtigen Weg sind, und der nächste Schritt besteht darin, eine gleichmäßige Schattierung des Netzes zu ermöglichen. Derzeit sehen Sie harte Kanten in der Beleuchtung benachbarter Dreiecke, da jedes Dreieck flach schattiert ist. Die Normalen von nur einem der Scheitelpunkte werden für Beleuchtungsberechnungen verwendet, anstatt die Normalen aller drei Scheitelpunkte über die Fläche des Dreiecks zu interpolieren (oder die Beleuchtung an jedem Scheitelpunkt zu interpolieren, je nachdem, ob Sie pro verwenden Pixel- bzw. Scheitelpunktbeleuchtung).

In älteren OpenGL-Implementierungen wird das Aktivieren einer glatten ( Gourard- ) Schattierung mit der folgenden Zeile durchgeführt:

glShadeModel(GL_SMOOTH);

Beachten Sie jedoch, dass dies jetzt zugunsten der programmierbaren Pipeline veraltet ist. Fürchte dich jedoch nicht, da es immer noch funktioniert, wenn du mit einer älteren OpenGL-Bibliothek arbeitest (und es möglicherweise auch in der neuesten Version unterstützt wird; jemand kann mich korrigieren, wenn ich mich irre). Um eine kurze Tangente zu spielen, wird manchmal das Erlernen von OpenGL über den veralteten Sofortmodus bevorzugt, da es etwas einfacher ist als die programmierbare Pipeline.

Wie auch immer, die glatte Schattierung hängt auch davon ab, ob die Normalen Ihrer Scheitelpunkte bei der Untersuchung Ihres Bildes richtig eingestellt sind, was anscheinend bereits geschieht. Wenn sie aus irgendeinem Grund nicht ganz korrekt sind, würde ich diese Antwort gerne aktualisieren, um eine Anleitung zur Berechnung zu geben.

Hoffe das hilft :)

Update: Um die Normalen für die richtige Beleuchtung zu berechnen, können Sie die folgende Regel verwenden: die normal für einen Scheitelpunkt ist gleich dem Durchschnitt der Gesichtsnormalen der Dreiecke ist ein Teil. Die Flächennormale eines Dreiecks wird berechnet, indem das Kreuzprodukt zweier seiner Kanten genommen wird. Also, für eine der Ecken Ihres Netzes:

A-----B
|   .`|
| .`  |
C`----D

Sie können die Gesichtsnormalen von berechnen ABC durch Nehmen BA x BCund die Gesichtsnormalen von BCDbis durch NehmenBC x BD . Wenn Sie die beiden resultierenden Vektoren zusammen mitteln und das Ergebnis normalisieren, erhalten Sie die Normalität für B. Für Eckpunkte in der Mitte des Netzes berechnen und mitteln Sie die Flächennormalen von acht Dreiecken. Beachten Sie, dass dies die Methode ist, die Bobobobo in seiner Antwort angegeben hat. Ich hoffe, dass diese Zusammenfassung eine gute Ergänzung dazu darstellt.

Für diese Art der Berechnung lohnt es sich wirklich, Ihr Netz in einer Half-Edge-Datenstruktur zu speichern . Dies erleichtert das Durchqueren der Dreiecke erheblich und ermöglicht es Ihnen, die Unterteilung und Dezimierung des Netzes zu implementieren, falls Sie es später benötigen.

Kevintodisco
quelle
Die glatte Schattierung ist aktiviert, aber ich habe die Scheitelpunkte für jedes Dreieck dupliziert und ihre Normalen auf die Normalen des Dreiecks gesetzt. Ich sehe nicht sofort, was die Normalität eines einzelnen Scheitelpunkts wäre. Ist es der Durchschnitt der Normalen der benachbarten Dreiecke? Zählt ein Dreieck mit einem Weitwinkel mehr als ein Engwinkel? Was ist mit den Kanten? Entschuldigung, wenn meine Fragen etwas chaotisch sind, lerne ich im Laufe der Zeit :)
Vivi
@vivi Ich habe meine Antwort aktualisiert, um zu erklären, wie die Normalen berechnet werden können, und auch einige andere nützliche Tipps gegeben.
Kevintodisco