[D3D11] glLineStipple emulieren

[Krishty]

Hi,

ein alter Renderer benutzt hier noch glLineStipple() um Strecken gestrichelt darzustellen. Die neue Version wird D3D benutzen, und dort muss ich ich das logischerweise emulieren. Ganz ohne Frage fällt die Wahl auf einen Geometry Shader, der die Strecken zu Quads extrahiert und eine Strichtextur draufpackt. Die Frage ist nur: Wie berechne ich die Texturkoordinaten?

So wie ich das sehe besteht zwischen allen Strecken, die in einem Rutsch gerendert werden, eine Datenabhängigkeit: Ich kann die Strichelung einer Strecke erst vorhersagen, wenn ich die Länge aller vorherigen Strecken, in Pixeln auf dem Bildschirm, kenne. Das bedeutet: Parallelisierung kann ich vergessen. Und nun? In jedem Frame auf der CPU projizieren, aus diesen Daten die Texturkoordinaten berechnen, die Vertices aktualisieren, und neu zur GPU hochladen? Da rollen sich mir die Fußnägel :(

[Spiele Programmierer]

Vielleicht im Compute Shader die bisherige Strichlänge als Vertexattribut berechnen?
Zumindest theoretisch sind ein Großteil der Notwenigen Additionen unabhänig und könnten parallel berechnet werden.
Erstmal die Abstände in Gruppen (parallel) zusemmnrechnen, die Gesamtsumme zum bis zum Start jeder Gruppe berechnen und schließlich wieder parallel in die Gruppen die einzelnen Abstände zusammenzählen.

Für bestimmte Arten von kleinen Linienmustern, kann man es vielleicht auch einfach tricksen.

[Krishty]

Stimmt. Ich schätze, dass nicht das Zusammenzählen selber der Flaschenhals sein wird, sondern das perspektivische Transformieren – und da dürfte der Compute Shader wunderbar schnell sein.

[mnemonix]

Ich kann die Strichelung einer Strecke erst vorhersagen, wenn ich die Länge aller vorherigen Strecken, in Pixeln auf dem Bildschirm, kenne.

Hm, klingt nach einer Präfixsumme (ist vielleicht auch das was Spiele Programmierer meint). Für eine Parallelisierung gibt es dazu ja genug Literatur.

[Krishty]

Das ist das Stichwort; danke!

[David_pb]

Hi,

im Grund lässt sich das auch einfach im Pixelshader lösen. Du könntest den Ansatz (siehe Links) verwenden den Wireframe zu rendern und das weiter modifizieren um den "Stipple-Effekt" zu simulieren:

https://forum.libcinder.org/topic/wiref ... ementation
http://developer.download.nvidia.com/SD ... eframe.pdf
http://web.archive.org/web/201306070046 ... index.html
http://codeflow.org/entries/2012/aug/02 ... ordinates/

[Krishty]

Danke, aber das ist nur die Lösung für den Teil des Problems, der sowieso einfach ist. Wenn du dir die Schnappschüsse dieser Implementierungen ansiehst, wirst du merken:

1. Lange Kanten sind länger gestrichelt als kurze
2. Die Strichelung fängt an jeder Kante neu an

2. ist das große Problem, denn wenn ich z.B. einen gestrichelten Kreis zeichnen möchte, besteht der aus vielen kleinen Strecken. Wenn jede Strecke ihre Strichelung von vorne beginnt, geht die Strichelung total unter. glLineStipple() „merkt“ sich darum, wo im Strichmuster die letzte Strecke aufgehört hat, und lässt die nächste Strecke dort weitermachen – und das auch noch im Screen Space, so dass man es nicht vorher in die Geometrie backen kann. Das ist der komplizierte Teil, für den ich die Präfixsumme brauche.

[Schrompf]

Ich würde wahrscheinlich einfach auf der CPU die Texturkoordinaten für alle Linien-Rechtecke ausrechnen. Wenn Du einen alten Renderer porten willst, geht der von so alter Hardware aus, dass Du auf heutiger Hardware noch nebenbei PI für jeden Vertex neuberechnen kannst und trotzdem lässig dessen Throughput schlägst. Aber ich vermute, dass kratzt Dir an der Ehre :-)

[Alexander Kornrumpf]

Danke, aber das ist nur die Lösung für den Teil des Problems, der sowieso einfach ist. Wenn du dir die Schnappschüsse dieser Implementierungen ansiehst, wirst du merken:

1. Lange Kanten sind länger gestrichelt als kurze
2. Die Strichelung fängt an jeder Kante neu an

2. ist das große Problem, denn wenn ich z.B. einen gestrichelten Kreis zeichnen möchte, besteht der aus vielen kleinen Strecken. Wenn jede Strecke ihre Strichelung von vorne beginnt, geht die Strichelung total unter. glLineStipple() „merkt“ sich darum, wo im Strichmuster die letzte Strecke aufgehört hat, und lässt die nächste Strecke dort weitermachen – und das auch noch im Screen Space, so dass man es nicht vorher in die Geometrie backen kann. Das ist der komplizierte Teil, für den ich die Präfixsumme brauche.

Das Grundproblem habe ich verstanden, nur zwei laterale Fragen:

- Sollte das Strichmuster nicht die Perspektive mitmachen, also Striche im Screenspace eben nicht gleichlang sein? Das wird doch sonst sehr irritierend wirken, oder? Beispiel: dein Kreis, bei schräger Betrachtung, ist von einer Ellipse in Draufsicht nur dadurch zu unterscheiden, dass die Striche am oberen und unteren Rand unterschiedlich lang sind. Es sei denn du hast ohnehin nur Draufsichten, dann stellt sich die Frage aber gar nicht weil es genügt, wenn die Striche ursprünglich gleich lang waren, da keine perspektivische Verzerrung stattfinden wird, oder?

- Ganz naiv verstehe ich nicht warum man überhaupt eine Textur braucht. Ist es nicht "besser", das Strichmuster on the fly im Shader zu generieren?

[Krishty]

Ich würde wahrscheinlich einfach auf der CPU die Texturkoordinaten für alle Linien-Rechtecke ausrechnen. Wenn Du einen alten Renderer porten willst, geht der von so alter Hardware aus, dass Du auf heutiger Hardware noch nebenbei PI für jeden Vertex neuberechnen kannst und trotzdem lässig dessen Throughput schlägst. Aber ich vermute, dass kratzt Dir an der Ehre :-)

Ja; mit D3D9 hätte ich es so gemacht weil die UP-Funktionen ja für genau diesen Zweck da sind (nur einmal Rendern und dann vergessen). Bei D3D11 kommt mir aber der Overhead der Buffer-Erzeugung gefühlt zu groß vor (1000 einmal-Buffer pro Frame ruckeln bei mir deutlich, und 1000 Strecken würde ich schon gern anzeigen können), und dann müsste ich wieder Logik implementieren um einen RingBuffer asynchron mit solchen einmal-Rendern-Jobs zu befüllen, und blabla das lutscht doch alles :(

- Sollte das Strichmuster nicht die Perspektive mitmachen, also Striche im Screenspace eben nicht gleichlang sein? Das wird doch sonst sehr irritierend wirken, oder? Beispiel: dein Kreis, bei schräger Betrachtung, ist von einer Ellipse in Draufsicht nur dadurch zu unterscheiden, dass die Striche am oberen und unteren Rand unterschiedlich lang sind.

Nein, sie sind garnicht zu unterscheiden. Das ist aber durchaus so gewollt, weil es sich um eine CAD-Anwendung handelt, und damit imitiert wird, wie ein menschlicher Zeichner seine Linien strichelt. Rotierte Ellipsen zu Kreisen (und umgekehrt) machen Menschen tatsächlich, und es hat mich früher regelmäßig in den Wahnsinn getrieben, aber so ist es eben.

Mein Favorit um eine Scheibe mit Radius r zu erzeugen: Man erzeugt zwei gegenüberliegende Ellipsebögen mit Radius r und r/2. Dann rotiert man sie 30°, dass sie zu einem geschlossenen Kreis projizieren. Nun verleiht man ihnen eine Liniendicke von r/2, so dass sie den Mittelpunkt treffen und eine gefüllte Scheibe ergeben. Wenn jemals jemand (ich!) etwas an dem Linienalgorithmus ändert, gehen Brandschutzmarkierungen in hunderten Zeichnungen kaputt. Yay!
Insbesondere die Entwickler von Plug-Ins, die auf Kopfdruck in deiner Zeichung die Elektrik reinmalen, sind lausige Programmierer und probieren mit ihrem Visual Basic einfach so lange herum, bis es irgendwie passt. Ändern kann man soawas jetzt nicht mehr; ich musste mich einfach damit abfinden.

- Ganz naiv verstehe ich nicht warum man überhaupt eine Textur braucht. Ist es nicht "besser", das Strichmuster on the fly im Shader zu generieren?

Das ist ein Detail, aber: Das Strichmuster ist natürlich einstellbar, etwa - -   - - oder — - — -. Hard-coding geht also nicht. Tatsächlich ist die Informationsmenge sehr gering, und glLineStipple nimmt einfach eine 16-Bit-Zahl, wo jedes Bit „jetzt Strich“ oder „jetzt kein Strich“ angibt. Eine 16-Bit-Shader-Konstante würde also reichen. Das haut aber nur hin, so lange die Linien auf dem Bildschirm exakt einen Pixel breit sind und du kein Anti-Aliasing haben willst. Bei breiteren Linien brauchst du lineare Interpolation, um ein Signed Distance Field aufzubauen. Und bevor ich dann im Shader die Bits linear interpoliere, kann ich einfacher direkt aus einer 16×1-Textur samplen.

3D-Kreise mit 2D-Strichelung glLineStipple-Version, so soll's aussehen

[Alexander Kornrumpf]

Nein, sie sind garnicht zu unterscheiden. Das ist aber durchaus so gewollt, weil es sich um eine CAD-Anwendung handelt, und damit imitiert wird, wie ein menschlicher Zeichner seine Linien strichelt.

Technische Zeichnungen die von Hand gemacht sind, nutzen nach meinem bescheidenen Wissen aber keine perspektivische Projektion. In Orthoprojektion stellt sich aber der Screenspace Teil des Problems nicht, da gleich lange Linien einfach gleich lang bleiben (?) egal in welchem Space. Ich hatte für dich gehofft, dass du das in deinem Use Case ausnutzen kannst.

[Krishty]

Ja, da könntest du recht haben. Ich muss mal in Erfahrung bringen, warum der derzeitige Renderer es auch perspektivisch macht. Wahrscheinlich, weil's das in OpenGL kostenlos gab.

[Alexander Kornrumpf]

Wahrscheinlich, weil's das in OpenGL kostenlos gab.

Wie furchtbar. Eigentlich dokumentiert der Thread hier ganz gut, dass sowas nie kostenlos ist.

[mOfl]

Ich hoffe, ihr verzeiht mir den Thread Resurrect, aber da ich vor Kurzem das gleiche Problem hatte, möchte ich gerne auch noch meinen Senf dazu geben. Vielleicht ist das Problem ohnehin schon gelöst.

Will man Stippling oder sonstige Effekte auf Linien, kann man das bequem mit einer 2d-Funktion (/-Textur) machen, wie bereits erwähnt. Dazu gibt es einiges an Literatur, stellvertretend dafür das hier. Damit die Striche langer Segmente nicht langgezogen werden, muss man die Texturkoordinaten im Screen Space berechnen und nicht perspektivisch korrekt interpolieren. In GLSL gibt es dafür das Keyword "noperspective", ich glaube, das gibt es in HLSL auch. Die Texturkoordinaten befüllst du dann im Geometry Shader mit Länge und Breite des aktuellen Segments, im Fragment Shader wertest du dann eine Funktion/Textur an diesen Koordinaten aus und repeatest bei Koordinaten außerhalb des Definitionsbereichs. Damit haben alle Striche innerhalb der Linie immer den gleichen Screen-Space-Abstand zu einander.

Der zweite, schwierigere Punkt ist, dass die Striche nicht an jedem Segment neu beginnen sollen, sondern kontinuierlich entlang der Linie verlaufen sollen. Wenn du nicht die Offsets aller Segmente auf der CPU berechnen willst/kannst, kannst du einen Segment Atlas verwenden, wie hier beschrieben. Das Paper ist leider schon etwas älter, die neuesten Hardwaremöglichkeiten bleiben deshalb darin unbeachtet. Aber du kannst das ja deinen Bedürfnissen entsprechend erweitern und die Sachen in einem Compute Shader statt im Framebuffer berechnen.