Generieren von Dreiecken aus einem quadratischen Raster

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:

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

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 .

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,

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.

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

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.