Gibt es eine effiziente \ einfache Art und Weise eine konkave Polygon in Direct3d zu ziehen

StackOverflow https://stackoverflow.com/questions/91202

  •  01-07-2019
  •  | 
  •  

Frage

Ich versuche, ein Polygon mit c # und directx zu ziehen

Alles, was ich bekomme, ist eine geordnete Liste von Punkten aus einer Datei, und ich brauche das flache Polygon in einer 3D-Welt zu ziehen.

I können die Punkte laden und eine konvexe Form unter Verwendung eines trianglefan und drawuserprimitives ziehen.

Dies führt offensichtlich zu falschen Ergebnissen, wenn das Polygon sehr konkav ist (was es sein kann).

Ich kann nicht vorstellen, ich die einzige Person bin, mit diesem Problem auseinander zu setzen (tho ich ein gfx / directx Neophyt bin - mein Hintergrund in gui \ windows Anwendungsentwicklung ist).

Kann mir jemand auf einen einfachen Punkt Ressource \ tutorial \ Algorithmus zu folgen, die mir helfen können?

War es hilfreich?

Lösung

Direct3D kann nur ziehen Dreiecken (na ja, kann es Linien und Punkte zeichnen, wie gut, aber das ist neben dem Punkt). Also, wenn Sie irgendeine Form zeichnen mögen, die komplexer als ein Dreieck ist, müssen Sie eine Reihe von zeichnen Dreiecken, die gleich diese Form zu berühren.

In Ihrem Fall ist es eine konkave Polygon Triangulation Problem. Bei einer Reihe von Eckpunkten, man kann sie halten wie es ist, man muss nur den „Index-Puffer“ berechnen (in einfachstenem Fall drei Indizes pro Dreieck, das sagen, welche Eckpunkte, die das Dreieck verwendet). Ziehen Sie dann, dass, indem sie in Vertex / Index-Puffer oder mit DrawUserPrimitives.

Einige Algorithmen für die Triangulation einfach (konvex oder konkav, aber ohne Selbstüberschneidungen oder Löcher) Polygone sind unter VTerrain Website .

Ich habe Ratcliffs Code in der Vergangenheit; sehr einfach und funktioniert gut. VTerrain hat einen toten Link zu ihr; Der Code kann hier . Es ist C ++, aber die Portierung das sollte über C # einfach sein.

Oh, und nicht Dreieck Fans verwenden. Sie sind von sehr begrenztem Nutzen, ineffizient und werden bald verschwinden (z Direct3D 10 unterstützt sie nicht mehr). Verwenden Sie einfach Dreieck-Listen.

Andere Tipps

Triangulation ist er offensichtliche Antwort, aber es ist schwer, eine solide Triangulator zu schreiben. Es sei denn, Sie 2 Monate Zeit verlieren es nicht einmal versuchen.

Es gibt ein paar Codes, die Ihnen helfen können:

Die GPC-Bibliothek. Sehr einfach zu bedienen, aber Sie können nicht wie es ist Lizenz:

http://www.cs.man. ac.uk/~toby/alan/software/gpc.html

Es gibt auch Dreieck:

http://www.cs.cmu.edu/~quake/triangle .html

Und FIST:

http: //www.cosy.sbg. ac.at/~held/projects/triang/triang.html

Eine andere (und meine bevorzugte) Möglichkeit wäre, die GLU Tesselator zu verwenden. Sie können ganz gut die GLU-Bibliothek aus DirectX-Programme laden und nutzen. Sie stellen keine OpenGL-Kontext brauchen, es zu benutzen und es ist vorinstalliert auf allen Windows-Rechnern. Wenn Sie beziehen möchten, können Sie die Triangulation Code aus der SGI-Referenzimplementierung abheben. Ich habe das einmal und es hat mir nur ein paar Stunden.

Bisher für die Triangulation. Es gibt eine andere Art und Weise als auch. Sie Schablone Tricks verwenden

Der allgemeine Algorithmus lautet wie folgt:

  1. Disable farb- und Tiefe schreibt. Aktivieren Schablone schreibt und Setup Ihre Stencilbuffer, dass es den aktuellen Schablonenwert invertiert wird. Ein bisschen Schablone ist ausreichend. Oh - Ihr Stencilbuffer sollte auch gelöscht werden

    2. .

  2. Wählen Sie einen beliebigen Punkt auf dem Bildschirm. Alle tun wird. Rufen Sie diesen Punkt Ihr Anker.

  3. Für jede Kante des Polygons ein Dreieck aus den beiden Eckpunkten bauen, die den Rand und Ihren Anker bauen. Zeichnen Sie, dass Dreieck.

  4. Wenn Sie alle diese Dreiecke gezeichnet haben, schalten Sie Schablone schreiben, schalten Sie Schablonentest und Farb Schreib- und einen Vollbild-Quad in der Farbe der Wahl ziehen. Dies füllt nur die Pixel in Ihrem konvexen Polygons.

Es ist eine gute Idee, den Anker in die Mitte des Polygons zu platzieren und nur ein Rechteck so groß wie die Grenzkasten Ihres Polygon zu zeichnen. Das spart ein bisschen Füllrate.

Btw - die Schablonentechnik arbeitet für selbstschneidende Polygone als auch

.

Hoffe, es hilft,   Nils

Wenn Sie sind in der Lage den Stencil Buffer zu verwenden, sollte es nicht schwer sein, zu tun. Hier ist ein allgemeiner Algorithmus: 

Clear the stencil buffer to 1.
Pick an arbitrary vertex v0, probably somewhere near the polygon to reduce floating-point errors.
For each vertex v[i] of the polygon in clockwise order:
    let s be the segment v[i]->v[i+1] (where i+1 will wrap to 0 when the last vertex is reached)
    if v0 is to the "right" of s:
        draw a triangle defined by s, v[i], v[i+1] that adds 1 to the stencil buffer
    else
        draw a triangle defined by s, v[i], v[i+1] that subtracts 1 from the stencil buffer
end for
fill the screen with the desired color/texture, testing for stencil buffer values >= 2.

Mit dem "Recht s" Ich meine, aus der Perspektive von jemandem auf v steht [i] und gegenüber v [i + 1]. Dies kann durch die Verwendung eines Kreuzproduktes getestet werden:

Kreuz (v0 - v [i], v [i + 1] - v [i])> 0

Ich habe gerade dies für ein Projekt zu tun hatte. Der einfachste Algorithmus gefunden wird „Ear Clipping“ genannt. Ein großes Papier darauf ist hier: TriangulationByEarClipping.pdf

Ich habe mir etwa 250 Zeilen C ++ Code und 4 Stunden, um die Brute-Force-Version zu implementieren. Andere Algorithmen haben eine bessere Leistung, aber das war einfach zu implementieren und zu verstehen.

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top