Perfekt genaues Rasterizen

[Schrompf]

Moin!

Ich glaube, ich habe mein Problem schon selbst gelöst, aber ich frag trotzdem mal:

Wie rasterized man ein Dreieck exakt? Also so richtig exakt, so dass an einer Kante mit dem Nachbardreieck nie, nie, NIE ein Pixel doppelt beschrieben oder im Gegenteil von beiden Seiten verfehlt wird? Die GPUs dieser Welt machen das ja die ganze Zeit.

Mein bisheriger Ansatz ist: baryzentrische Koords ausrechnen, und dann prüfen auf s >= 0, t >= 0, s+t < 1. Aber ich brauch ja was, was für identische Eingaben deterministische Ergebnisse liefert. So dass ich an einer Kante zwischen zwei Dreiecken immer exakt bestimmen kann, ob ein Pixel jetzt noch ins Dreieck gehört oder nicht. Und wenn nicht, muss er dann stattdessen zuverlässig zum Nachbardreieck gehören.

Und daher darf ich nicht baryzentrisch arbeiten: die zwei Dreiecke an einer gemeinsamen Kante haben jeweils einen dritten Eckpunkt, der das Gesamtergebnis an so einer Kante dann nicht mehr deterministisch werden lässt.

Meine aktuelle Idee ist jetzt also, nur die beiden Eckpunkte einer Kante zu nehmen und mit dem Skalarprodukt der Senkrechte dazu die Pixel zu prüfen. Dann müsste ich Distanz d < 0 und auf der anderen Seite d >= 0 testen können und müsste immer exakt zu deterministischen Ergebnissen kommen. Wenn's nicht zum Einen gehört, muss es zum Anderen gehören.

An Ecken wird es dann wohl komplizierter. Oder doch nicht? Hat jemand Erfahrungen? Ihr seid doch alles alte Nerds, ihr habt doch garantiert schonmal nen Software Rasterizer geschrieben, oder? :-)

[Krishty]

Wie rasterized man ein Dreieck exakt? Also so richtig exakt, so dass an einer Kante mit dem Nachbardreieck nie, nie, NIE ein Pixel doppelt beschrieben oder im Gegenteil von beiden Seiten verfehlt wird? Die GPUs dieser Welt machen das ja die ganze Zeit.

Dass GPUs Pixel benachbarter Dreiecke doppelt schreiben ist mir neu. Zumindest die Direct3D Rasterization Rules verneinen das eindeutig: https://learn.microsoft.com/en-us/windo ... tage-rules

Edit: Oder meinst du, dass die GPUs die ganze Zeit rasterisieren, ohne Pixel doppelt zu schreiben? Dann hast du natürlich recht.

Da ist dann auch eine mögliche Lösung, nämlich dass in mehrdeutigen Fällen die obere/linke Kante Vorrang hat.

[kimkulling]

Richtig exakt aus meiner Sicht:
- Rasterizing der Kanten für alle Dreiecke mit Bresenham ermitteln.

Aufgrund der Entscheidungs-Heuristik sollte es da keine Missverständnisse geben, sofern ich mich nicht komplett irre.

VG Kimmi

[Jonathan]

Hat jemand Erfahrungen? Ihr seid doch alles alte Nerds, ihr habt doch garantiert schonmal nen Software Rasterizer geschrieben, oder? :-)

Hehe, ja, sollte man denken, aber leider nein. Aber ich kann mich noch daran erinnern, damals in Computergrafik I diesen Standardrasterisierungsalgorithmus gelernt zu haben, nur um dann 2 Jahre später von nem Kollegen gesagt zu bekommen, dass der jetzt wieder total out ist und Grafikkarten seit Jahren was neues / effizienteres machen. Leider weiß ich da keine Namen, was diesen Post ein klein wenig sinnlos macht, sorry^^

(Aber FunFact: Wir hatten neulich Linien-Rasterisierung diskutiert und ein Kollege hat da mal näher rein geschaut und scheinbar ist das für höhere Dimensionen (3, 4, 5, etc.) gar nicht so leicht sehr effizient eine Linie mit gewisser dicke zu voxelisieren. Vielleicht aber auch eher deshalb, weil das fast niemand braucht, und Brute-Force auch nicht so teuer und nicht so schwierig ist.)

[kimkulling]

Bresenham ist meines Kenntnistandes nach der Weg, den die meisten GPU-Driver immer noch benutzen. Im 3D-Metall-Druck wird er übrigens auch immer noch genutzt, um Druck-Prioritäten für Flächen in der aktuelleb Slice zu bestimmen.

Ich habe einmal etwas von Algorithmen gelesen. Es gibt Dinosaurier und es gibt Haie. Bresemńham scheint ein Hai zu sein!

VG Kim

[Schrompf]

Bresenham ist es wohl nicht, weil: MultiSampling. Dafür gibt's ja elaborierte Muster, wie die Samples innerhalb eines Pixels verteilt werden, und manchmal kann man sie sogar konfigurieren. Das bedeutet für mich, dass die GPU irgendwie Positionen auf Innerhalb/Außerhalb prüft.

[Schrompf]

Edit: Oder meinst du, dass die GPUs die ganze Zeit rasterisieren, ohne Pixel doppelt zu schreiben? Dann hast du natürlich recht.

Da ist dann auch eine mögliche Lösung, nämlich dass in mehrdeutigen Fällen die obere/linke Kante Vorrang hat.

Das verstehe ich nicht. Ja, ich meinte, dass die GPUs sauber lückenfrei rasterisieren. Aber wie soll ich oben/links einen Vorrang geben?

Ah. Oh. Mir dämmert's: wenn ich mittels der Senkrechte einer Kante prüfe, ob diesseits oder jenseits, dann kann ich für die eine Hälfte der Richtungen ein >= 0 benutzen und für die andere Hälfte der Richtungen nur ein > 0. Das probier ich mal aus.

[Krishty]

Das verstehe ich nicht. Ja, ich meinte, dass die GPUs sauber lückenfrei rasterisieren. Aber wie soll ich oben/links einen Vorrang geben?

Any pixel center which falls inside a triangle is drawn; a pixel is assumed to be inside if it passes the top-left rule. The top-left rule is that a pixel center is defined to lie inside of a triangle if it lies on the top edge or the left edge of a triangle.

Where:

• A top edge, is an edge that is exactly horizontal and is above the other edges.
• A left edge, is an edge that is not exactly horizontal and is on the left side of the triangle. A triangle can have one or two left edges.
• The top-left rule ensures that adjacent triangles are drawn once.

This illustration shows examples …

(emphasis mine)

[Krishty]

Andere Lösungen gibt es natürlich auch. So kannst du einen Test nach Jordan machen, der durch die Winding Number ein eindeutiges Ergebnis für aneinander grenzende Polygon gibt. Wenn man Polygon zu Dreieck vereinfacht, wird der Code auch recht simpel.

An improved algorithm to calculate the winding number was developed by Dan Sunday in 2001.[7] It does not use angles in calculations, nor any trigonometry, and functions exactly the same as the ray casting algorithms described above. Sunday's algorithm works by considering an infinite horizontal ray cast from the point being checked. Whenever that ray crosses an edge of the polygon, Juan Pineda's edge crossing algorithm (1988)[8] is used to determine how the crossing will affect the winding number. As Sunday describes it, if the edge crosses the ray going "upwards", the winding number is incremented; if it crosses the ray "downwards", the number is decremented. Sunday's algorithm gives the correct answer for nonsimple polygons, whereas the boundary crossing algorithm fails in this case.

Emphasis mine; beachte, dass das nur eine andere Ausführung der Top-Left-Regel von Direct3D ist. Ich nutze diesen Algorithmus mit Festpunktarithmetik für “welche Nationalität hat der Luftraum hier” in meinem Flugsimulator und er scheint in der Tat keine Überlappung zu haben.

Welche Implementierung die GPUs benutzen, weiß ich nicht. Du hast recht, dass die baryzentrischen Koordinaten problematisch sind, aber GPUs müssen sie für die lineare Interpolation der Vertex-Attribute einsetzen. Ob die dann einen Bresenham zusätzlich machen oder eine Lösung für die baryzentrischen Probleme gefunden haben, weiß ich nicht.

[Schrompf]

Danke für die Erklärungen! Mit der TopLeft-Regel kann ich was anfangen.

Hab mal schnell einen Software-Rasterizer auf Basis baryzentrischer Koordinaten geschrieben, und der ist echt überraschend genau. Im Bild sind 6 Dreiecke, die richtig schiefe Koordinaten haben und außerdem über Zeit skaliert, gedreht, verschoben werden. Und dem hab ich ein bissl zugeguckt und nicht ein einziges Mal eine Lücke oder einen doppelt geschrieben Pixel gesehen.

Prinzipiell ist dieser Ansatz trotzdem unperfekt. Im Discord habe ich https://kristoffer-dyrkorn.github.io/tr ... asterizer/ bekommen, aber noch nicht vollständig durchgelesen. Ich schau mal. So wie's jetzt baryzentrisch aussieht, reicht mir das eigentlich erstmal, aber ich fühle mich verpflichtet, eine "echte" Lösung zu finden, die mich auch in Zukunft nicht überraschen wird.

[Schrompf]

Hab den Artikel jetzt zu Ende gelesen und der ist echt gut! Ist zwar JavaScript, aber erklärt echt freundlich das Problem mit Fließkomma-Zahlen, was sie eigentlich sind und wie sie sich verhalten. Und schlägt als Lösung für mein Problem der Ungenauen Zuordnung an Dreiecks-Rändern genau das vor, was auch der C++-Discord vorgeschlagen hat: Festkomma-Zahlen.

[kimkulling]

Danke fürs Teilen, der Artikel ist in der Tat sehr lesenswert.

[Schrompf]

Es rastert! Absolut lückenlos! Dazu nötig waren
a) Umbau von baryzentrisch auf Abstandstest aller drei Kanten
(Der Artikel oben nennt es Determinante, aber wenn man bissl schielt, sieht man, dass es ganz banal das Punktprodukt mit der Kantensenkrechte ist.)
b) Zartes Offset auf die Kantenabstände je nach TopLeft-Regel - siehe oben.
(Der Artikel packt das Offset auf jeden Abstandstest, ich pack das Offset einmalig am Anfang auf die Abstand-Startwerte.)
c) Umbau auf Festkomma. Ich hab nen banalen int32 mit 8Bit Nachkomma genommen.

Mein Testrender (der graue Blob oben im Bild) ist jetzt absolut lückenfreu und überlappungsfrei - letzteres habe ich jetzt nachleuchtend gemacht, so dass ich zumindest das zuverlässig bemerken würde.

Jetzt wende ich das mal auf meine Surface-Rendereien an - die schwarzen Streifen und komischen Kanten auf allen Oberflächen kommen nämlich daher, dass mein bisheriger SoftwareRasterizer immer mal wieder Pixelreihen ausließ oder doppelt beschrieb. Das müsste jetzt vorbei sein! Endlich einheitsgraue glatte Oberflächen :-D

[Krishty]

c) Umbau auf Festkomma. Ich hab nen banalen int32 mit 8Bit Nachkomma genommen.

Fun fact: Z fighting entsteht nicht nur durch Ungenauigkeit in Z, sondern auch durch Ungenauigkeit in X/Y. Ein Nvidia-Paper hatte mal analysiert, was den größeren Einfluss hat, und bei 32-bit-Tiefenpuffer war es IIRC X/Y.

Also geh mit der Genauigkeit ruhig so weit hoch wie du kannst.

[Schrompf]

Da sagste was. Für schräge Kanten brauchst Du ja ein paar Bits Subpixel-Genauigkeit. Und da ist leider ne Multiplikation drin. Wenn man im 32bit-Integer bleiben will, hat man also nur 16Bit insgesamt zur Verfügung. Sogar nur 15, wegen Vorzeichen. Wenn ich Rendertargets bis 4096 bespielen will, hab ich also noch drei tapfere Nachkomma-Bits übrig :-(

Vielleicht doch alles auf 64bit-Integer. Da haben wir genug Headroom, um bis zum Rand des beobachtbaren Universums zu rasterizen. Und ich hab neulich entdeckt, dass das AVX256-Multiply 4x 32bit Integer mit 4x 32bit-Integer mit vollen 4x 64bit Ergebnis multiplizieren kann. Wär also kein so heftiger Einschnitt.