Einführung
"Was passiert, wenn wir die Gleitkommazahlen durch rationale Zahlen ersetzen und versuchen, das Bild zu rendern?"
Ich stellte mir diese Frage, nachdem ich über den Tweet eines Forschers und Computergrafiklehrers Morgan McGwire nachgedacht hatte. Er sprach darüber, wie sehr Informatikstudenten überrascht sind, als sie zum ersten Mal herausfinden, dass Kompromisse eingegangen werden müssen, um die bekannten Gleitkommazahlen in modernen Computern zu speichern. Und diese Kompromisse erschweren einfache Aufgaben, zum Beispiel die Überprüfung, ob ein Punkt zu einem Dreieck gehört. Das Problem ist natürlich, dass die Überprüfung, ob vier Punkte in derselben Ebene liegen (Koplanarität), unter Verwendung der Determinante oder einer Art Vektormultiplikation (aber tatsächlich ist dies dasselbe) niemals einen Wert ergibt, der genau gleich Null ist, was erforderlich ist Dies sind mathematische Methoden. Selbst wenn die tatsächlichen Berechnungen, auf derselben Ebene zu sein, genau wären, würden dieselben Kompromisse mit einer Genauigkeit von fast 1,0 die Antwort geben, dass die vier Punkte selbst nicht koplanar sind.
Dies brachte mich auf die Idee - wenn wir annehmen, dass alle eingehenden Renderer-Daten (Scheitelpunktkoordinaten, 3D-Transformationen usw.) als rationale Zahlen festgelegt wurden, würden sie alle Operationen erstellen, von der Erzeugung eines Strahls über die Beschleunigungsstruktur bis zur Kreuzung Strahlen mit Dreiecken sind nur rationale Zahlen? Wenn das der Fall wäre, könnten wir genau einen Koplanaritätstest durchführen! Sie fragen sich vielleicht, warum eine in rationalen Zahlen ausgedrückte 3D-Szene nur zu rationalen Zahlen führen sollte ...
Eine einfache Szene, deren Pfadverfolgung durch rationale Arithmetik durchgeführt wird. Es wird ein Gleitkommazahlensystem verwendet, keine Gleitkommazahl.Erstens ist eine rationale Zahl eine Zahl, die als Verhältnis zweier ganzer Zahlen ausgedrückt werden kann, beispielsweise 1/2 oder 355/113. Zweitens basieren „normale Rendering-Operationen“, wie z. B. Bounding-Box-Tests, Überprüfen des Schnittpunkts eines Strahls mit einem Dreieck, Reflexion eines Strahls usw., auf Vektor- und Skalarprodukten sowie auf Skalarunterteilungen (einschließlich) Koordinatentransformation und Matrixinversion, Quaternionen usw.), die wiederum auf vier Grundoperationen basieren: Addition, Subtraktion, Multiplikation und Division. Beim Addieren, Subtrahieren, Multiplizieren und Dividieren rationaler Zahlen werden auch rationale Zahlen erhalten. Der Mathematiker würde sagen, dass viele rationale Zahlen ein Feld bilden, das unter vier grundlegenden arithmetischen Operationen geschlossen wird. Für uns bedeutet dies, dass wir, wenn wir uns ausschließlich an rationale Zahlen halten, tatsächlich von den Eingabedaten der 3D-Szene zu einem vollständig gerenderten Bild übergehen können, ohne die Welt der rationalen Zahlen zu verlassen.
Ausnahmen von der Regel „Aktionen auf rationale Zahlen ergeben rationale Zahlen“ sind Quadratwurzeln und trigonometrische / transzendentale Funktionen. Was letzteres betrifft, sage ich immer, wenn Sie trigonometrische Berechnungen in den geometrischen Innenräumen Ihres Renderers durchführen mussten, dann machen Sie höchstwahrscheinlich etwas falsch (und ich habe gezeigt,
wie man die meisten Standardfälle behebt ) [
Übersetzung auf Habré]. Bei Quadratwurzeln ist es mit Ausnahme von konischen Abschnitten (Kugeln, Zylinder usw.) und der Durchführung von Schattierungen / DFOS / Färbungen nicht erforderlich, die Strahlen und die Normalen zu den Oberflächen so oft wie gewöhnlich zu normalisieren. Es muss sicherlich nicht getan werden, um einen Strahl, seinen Durchgang, Schnittpunkt, Reflexionen usw. zu erzeugen. Leider sehe ich sehr oft, dass Programmierer Werte aus keinem anderen Grund normalisieren als "Nun, ich weiß nicht, ich mache es, damit ich auf Nummer sicher gehen kann." In der Praxis ist es in dem Teil des Renderings, in dem die Geometrie verfolgt wird, sehr selten erforderlich, die Werte zu normalisieren. Daher hatte ich die Hoffnung, dass es möglich ist, die gesamte Szene zu verfolgen, ohne die Welt der rationalen Zahlen zu verlassen - dies würde ich als "rationales Rendering" bezeichnen.
Um dies in die Praxis umzusetzen, muss ich ein Zahlensystem erstellen, das auf rationalen Zahlen basiert, die ein Computer verwenden könnte. Darüber hinaus könnte ich die üblichen Pfadverfolgungsalgorithmen implementieren, Bilder ohne Genauigkeitsverlust berechnen, Koplanaritätsprüfungen mit genauen Antworten durchführen und alle Schüler, die Computergrafiken studieren, glücklich machen.
Dieser Artikel handelt von zwei Nächten der Erforschung des Realismus einer solchen Idee. Ich werde über die vielen Aspekte sprechen, die ich gelernt habe, über das, was ich mir ausgedacht habe, und über einige Überraschungen, die ich dabei entdeckt habe. Der Artikel ist in mehr oder weniger chronologischer Reihenfolge meiner Arbeit verfasst. Außerdem wurde es in meinem ungewöhnlich informellen und sehr unwissenschaftlichen Stil geschrieben (auf den ich stolz bin). Das oben gezeigte Bild ist eine Art Spoiler, aber lesen Sie den Artikel bis zum Ende, weil ich über das Gute und das Schlechte sprechen werde.
Vorbereitung
Das erste, was ich tat, war, in
Shadertoy einen minimal begrenzten Tracer für eine
extrem einfache Szene zu implementieren, die aus einer Ebene, einer Kugel, einem rechteckigen Parallelepiped und einem Dreieck besteht - den Bausteinen realer Renderer. Dann habe ich den Code in eine C ++ - Datei kopiert und nach einigen geringfügigen Änderungen mit meinem
piLibs- Framework kompiliert. Zum Vergleich habe ich ein verfolgtes Bild mit regulären Zahlen gemäß dem IEEE754-Standard mit Gleitkomma auf die CPU gerendert. Ich habe auch die gesamte Strahlennormalisierung aus dem Trace-Code entfernt, da, wie oben erwähnt, keine davon tatsächlich benötigt wird. Ich möchte Sie daran erinnern, dass für die Normalisierung eine Quadratwurzel erforderlich ist und rationale Zahlen bei ihrer Verwendung nicht erhalten bleiben (die Quadratwurzel einer rationalen Zahl ist keine rationale Zahl). Wenig später werden wir sehen, dass das Anwenden von Quadratwurzeln natürlich immer noch möglich ist. Ich wollte nur den Code so mathematisch sauber wie möglich machen, um zu sehen, wie weit ich mit der exakten Arithmetik rationaler Zahlen ohne Rundung gehen kann.
Der letzte vorbereitende Schritt - Ich nahm alle vec3-, mat4x4- und anderen grundlegenden Algebra- / Mathematikklassen und änderte sie dann so, dass sie rational statt float verwendeten. Da meine rationale Struktur alle Standardoperatoren (add, sub, mul, div, Vorzeichenumkehr, Vergleiche usw.) überlastet, erfolgte der Austausch ohne Probleme. Ich implementierte schnell die verbleibenden üblichen Operationen (abs, sign, mod, frakt, floor, sqrt usw.), was theoretisch ausreichte, um schöne rationale Renderings zu erhalten.
Test 1 - Die naive Lösung
Aber mal sehen, wie diese erste Implementierung war. Zuerst versuche ich immer das Einfachste und dann schaue ich mir die Ergebnisse an. Der einfachste Weg, rationale Werte zu implementieren, bestand darin, zwei ganze Zahlen zu verwenden. Wie der Name des Abschnitts andeutet, wird dies nicht meine endgültige Entscheidung sein, aber für den ersten Versuch war es eine vernünftige Entscheidung. Daher sollte jede Zahl
x als Zähler
N und Nenner
D dargestellt werden und den Wert
N /
D bilden. Der
x- Wert wird durch das bestmögliche
N /
D- Paar (innerhalb der angegebenen Bittiefe) angenähert, das dem wahren
x- Wert am nächsten kommt. Ich entschied, dass beide Zahlen positiv sein müssen und das Vorzeichen der Zahl in einem separaten Bit gespeichert werden sollte, um die Arbeit zu vereinfachen und Unklarheiten zu beseitigen, obwohl dies nicht sehr wichtig ist. Zu diesem Zeitpunkt waren sowohl Zähler als auch Nenner vom Typ ohne Vorzeichen. Aber selbst beim Trennen des Vorzeichens hatte
N /
D viel Redundanz: Zum Beispiel bezeichnen 1/4 und 7/28 dieselbe Zahl, haben aber völlig unterschiedliche Bitdarstellungen. Wir werden später darauf eingehen, aber jetzt wollen wir unsere Aufmerksamkeit nicht konzentrieren und sehen, wie die vier grundlegenden arithmetischen Operationen in dieser rationalen Form aussehen.
Zunächst ist zu beachten, dass das Subtrahieren von
a -
b einfach die Addition von
a und dem Wert gegenüber
b ist , d. H.
A + (
-b ), wobei
-b durch einfaches Ändern des Vorzeichens von
b berechnet werden kann. In ähnlicher Weise ist das Teilen von
a /
b dasselbe wie das Multiplizieren von
a und der Umkehrung von
b . Oder mit anderen Worten,
a /
b =
a · (1 /
b ), wobei (1 /
b ) berechnet werden kann, indem einfach die Stellen des Zählers
b n und des Nenners
b d der Zahl
b geändert werden . Hier ist also die erste interessante Eigenschaft der rationalen Arithmetik: Division und Multiplikation haben die gleichen Kosten. Daher besteht im Gegensatz zum üblichen Gleitkomma-Rendering, bei dem Divisionen normalerweise vermieden, verzögert oder unter den Verzögerungen langsamer Texturanforderungen verborgen werden, keine Notwendigkeit, sich vor diesen Operationen in der rationalen Arithmetik zu fürchten .
Wir wenden uns der Addition mit Multiplikation zu: Wir wissen, dass die entgegengesetzten und inversen Werte trivial einfach zu berechnen sind, also erhalten wir:
Die Vorzeichenerhaltung während der Multiplikation ist trivial, sie ist nur xor, da zwei positive Werte ein positives Ergebnis ergeben, sowie zwei negative. Das Speichern eines Zeichens zum Hinzufügen ist ein komplizierterer Vorgang, und für eine schnelle Lösung habe ich es in drei Zweigen implementiert (das Hinzufügen ist trivial, wenn die Zeichen
a und
b übereinstimmen, aber wenn sie nicht übereinstimmen, müssen Sie eine kleinere Zahl auswählen und von der größeren abziehen - in dem Artikel, den ich nicht habe Ich werde solche kleinen Details genauer beschreiben, aber den Quellcode einfach irgendwo auslegen.
Ich werde auch die Implementierung von Fract () und Floor () überspringen. Wenn Sie versuchen, sie selbst zu implementieren, werden Sie ihre Einfachheit und Schönheit erkennen. Auch die Vergleichsoperatoren sollten berücksichtigt werden. Nachdem wir uns um die Zeichen gekümmert haben und angenommen haben, dass
a und
b positiv sind, bekommen wir
Hierbei ist zu beachten, dass wir auch zum Vergleich einige Multiplikationsoperationen benötigen, die zum Übergang zur nächsten Wortgröße führen können und etwas niedriger wichtig sind.
Schließlich betrachten wir die Quadratwurzeln in einem separaten Abschnitt und wissen, dass wir sie größtenteils nicht benötigen (mit Ausnahme der Kugel aus diesem ersten Test).
Dies war genug, um das erste Rendering auszuführen und die Testszene (Ebene + Kugel + Dreieck + rechteckiges Feld) zu verfolgen, um zu sehen, was daraus wurde. Ich habe für diesen ersten Test großzügig rationale 65-Bit-Zahlen verwendet, die tatsächlich eine große Datenmenge darstellen (vergleichbar mit dem "doppelten" Datentyp): 32 Bit werden vom Zähler übernommen, 32 Bit sind der Nenner und ein weiteres Bit ist das Vorzeichen. Das erste ist das Bild, das mit diesem naiven Ansatz erhalten wurde, das zweite ist das Bild, das unter Verwendung von Gleitkommazahlen (Referenz) erstellt wurde:
"Naive" rationale 65-Bit-ZahlenGleitkomma-ReferenzDas Ergebnis war ziemlich schlecht, die Box und das Dreieck erschienen nicht einmal auf dem Putz, und die Kugel und die Ebene des Bodens waren zu laut. Das Problem war natürlich, dass jedes Mal, wenn meine rationalen Zahlen eine grundlegende arithmetische Operation in einer der algorithmischen Stufen des Renderns ausführten, der Zähler und der Nenner immer unkontrollierter wurden, weil eine ganzzahlige Multiplikation verwendet wurde. Stellen Sie sich Folgendes vor: Wenn die Einheiten unserer ursprünglichen Welt Meter wären und wir die Quellgeometrie (Eckpunkte und Kamera) millimetergenau verknüpfen würden, würden nur die Quelldaten für eine relativ kleine Szene ein 16-Bit-Volumen belegen. Gleichzeitig würden bei einer Standard-HD-Bildschirmauflösung und einer 4-fachen Glättung rationale Strahlrichtungszahlen leicht 12 Bit erfordern. Das heißt, während der ersten Interaktion von Strahl und Geometrie würde die einfachste arithmetische Operation unter Verwendung beider Eingabedatensätze das Ergebnis in 28-Bit-Längen umwandeln - nahe genug an der 32-Bit-Grenze, die ich mir in dieser ersten Implementierung gesetzt habe. Und das noch bevor wir das allererste Vektor- oder Skalarprodukt durchgeführt haben. Bis das Skalarprodukt vollständig ist, würde der Renderer rationale Zahlen benötigen, die Hunderte von Bits lang sind, um Zahlen darzustellen. Dies ist natürlich der schlimmste Fall, aber der durchschnittliche Fall würde nahe daran liegen. Wenn man bedenkt, dass ich nur eine 32-Bit-Kapazität für den Zähler und den Nenner zugewiesen habe, ist es leicht zu verstehen, wie schnell die Werte in diesem Test die Grenzen überschreiten - es ist nicht überraschend, dass mit Ausnahme der Bodenebene und eines Teils der Kugel fast nichts sichtbar ist.
Test 2 - Reduktion um den größten gemeinsamen Faktor
Dann habe ich das System verbessert, indem ich die oben kurz erwähnte Eigenschaft verwendet habe - verschiedene rationale Zahlen können den gleichen Betrag bedeuten. Tatsächlich ist 6/12 der gleiche Wert wie 1/2, verwendet jedoch viel mehr Bits als das letzte. Daher lautete die Idee wie folgt: Wenn ich nach jeder grundlegenden arithmetischen Operation (oder danach) alle gemeinsamen Teiler aus dem Zähler und den Nennern extrahieren und den Bruch in seine einfachste Form bringen würde, könnte ich vielleicht alles unter Kontrolle halten und die Operationen länger fortsetzen mit exakter Arithmetik ohne Genauigkeitsverlust. Vielleicht können Sie dies lange genug tun, um saubere, gerenderte Bilder zu erhalten? Ich werde einen kleinen Exkurs machen, um ein anderes Beispiel zu zeigen: 588/910 kann auf 42/65 vereinfacht werden, da 14 ein Teiler von 588 und 910 ist. Aber um 42/65 zu speichern, werden offensichtlich weniger Bits benötigt als 588/910. Das Finden der größtmöglichen Zahl, die gleichzeitig die beiden anderen Zahlen teilt, kann mit dem Great Common Divisor (GCD) -Algorithmus erfolgen, dessen effektive Implementierungen Sie überall finden können (ich habe sie persönlich direkt aus Wikipedia kopiert und durch Ausführen des Scanschritts etwas beschleunigt Bits mit internen x64-Operationen). Ausgerüstet mit dem GCD-Algorithmus sollte meine rationale Klasse die während des Rendervorgangs erzeugten Brüche ständig vereinfachen. Dies kann auf zwei Arten geschehen:
Das erste besteht darin, das Zwischenergebnis der Additions- und Multiplikationsoperatoren in den nächsten Typ von Bitdaten umzuwandeln (in meiner aktuellen naiven Lösung ist es uin64_t), nach GCD in diesem umfangreicheren Datentyp zu suchen und das Ergebnis dann auf die ursprüngliche Bitlänge zu reduzieren (32). Der zweite Weg besteht darin, zu analysieren, wie
a n ,
a d ,
b n und
b d in beiden arithmetischen Operatoren miteinander kombiniert werden, und gemeinsame Teiler daraus zu extrahieren, bevor die Multiplikation durchgeführt wird. Der zweite Ansatz beseitigte im Wesentlichen die Notwendigkeit großer Bitlängen. Da ich wusste, dass es ohnehin notwendig sein könnte, sie zu verwenden, entschied ich mich für die erste Methode, da sie einfacher zu implementieren war und es mir ermöglichte, meine Arbeit zu beschleunigen (der Abend vergeht sehr schnell). Nachdem wir das alles getan haben, wollen wir sehen, welchen Render ich jetzt erstellen kann:
Rationale 65-Bit-Zahlen durch GCD reduziertGleitkomma-ReferenzViel besser! Bisher weit davon entfernt, natürlich ideal, aber es sieht vielversprechend aus. Ich habe die Box und das Dreieck erscheinen lassen, und die Kugel scheint jetzt viel voluminöser zu sein. In der oberen rechten Ecke erschien jedoch ein lustiges Artefakt, und rationale Zahlen für viele Pixel gehen immer noch über die Grenzen hinaus, was zu vielen Punkten im Bild führt. Es ist jedoch erwähnenswert, dass ich für einige (viele) Pixel anfing,
genaue und perfekte Ergebnisse zu erzielen! Das heißt, der Tracer fand mathematisch genaue Schnittpunkte von Punkten und Entfernungen, was die Hauptursache für den Versuch war, rationale Zahlen zu verwenden.
Bevor ich zum nächsten Schritt im Prozess des Nachweises der Anwendbarkeit rationaler Zahlen übergehe, möchte ich kurz auf meine Erkenntnisse zur GCD und zur Reduzierung rationaler Zahlen eingehen.
Die erste Entdeckung bezieht sich auf das Bitvolumen rationaler Zahlen. Obwohl ich immer noch keine schönen Bilder rendern kann und dies wichtiger ist als die Sorge um die Optimierung des Datenvolumens, und obwohl diese frühe Implementierung immer noch eine große Anzahl von Bits (1 + 32 + 32) verwendete, habe ich bereits über die zuvor erwähnte Verschwendung nachgedacht Bits in Form von überschüssigen Brüchen. Insbesondere nach dem Hinzufügen einer Stufe mit einer GCD sind Bitkombinationen wie 2/4 nicht mehr anwendbar, da sie vor dem Schreiben in ein Register oder eine Variable automatisch auf 1/2 reduziert werden. Das heißt, von allen 2
64 Kombinationen von Bits, die ein Zähler und ein Nenner sein könnten, blieben in gewissem Sinne viele unbenutzt. Und so etwas kann man nicht verschwenden. Oder ist es möglich? Wie viel Platz verliere ich tatsächlich? Ich habe einen kleinen Exkurs gemacht, um dieses Problem zu untersuchen.
Exkurs - Auf gegenseitig Primzahlen
Die folgenden Abbildungen zeigen die Verwendung von Bits für rationale Zahlen in 5/5 Bit und 7/7 Bit. Die horizontalen und vertikalen Achsen der Graphen repräsentieren die Werte des Zählers und Nenners aller möglichen rationalen Zahlen mit Zählern und Nennern bis zu 5 Bits (31) und 7 Bits (127). Schwarze Pixel sind nicht verwendete Kombinationen, und weiße Pixel sind verwendete Brüche. Beispielsweise ist die gesamte Diagonale bis auf das 1/1 Pixel schwarz, da alle Brüche der Form n / n auf 1/1 reduziert werden.
Verwenden von Bits für 5/5 rational
Verwenden von Bits für 7/7 rationalWenn Sie die Pixel wie ich zählen, können Sie schnell verstehen, dass der Anteil nützlicher Pixel mit einer Erhöhung der Anzahl der Bits tendenziell 60,8% beträgt. Eine kleine Online-Recherche hat mir gezeigt, dass dieses Verhältnis genau 6 / π
2 beträgt, da es auch die Wahrscheinlichkeit ist, für zwei Zufallszahlen relativ prim (ohne gemeinsame Teiler) zu sein. Sie fragen sich vielleicht, woher der Pi kommt?
Es stellt sich heraus, dass „sechs mal pi im Quadrat“ ein Wert ist, der gleich Eins geteilt durch die Riemannsche Zetafunktion ist, die am Punkt 2, 1 / ζ (2) berechnet wird. Dies sollte uns nicht sehr überraschen, da die Riemannsche Zeta-Funktion häufig bei Problemen mit Primzahlen und gegenseitig Primzahlen auftaucht., , 40% . , , … . , , , , , . - - -, , , . ,
.
Kehren wir zur Analyse dessen zurück, was wir erhalten haben: Ich kann Bilder mit Verzerrungen rendern, aber sehr stark von der Verteilung der Primzahlen in den Berechnungen abhängen. Es hängt von diesen Primzahlen ab, ob der GCD-Algorithmus den Ausdruck vereinfachen kann - sobald eine Primzahl oder ein Vielfaches davon in eine der Renderer-Zahlen (Vektoren, Skalare, Matrizen) fällt, "verschmutzt" er alle darauf folgenden Zahlen in weiteren arithmetischen Manipulationen. und bleibt für immer in ihnen. Daher ist garantiert, dass allmählich alles zu wachsen beginnt, es ist nur eine Frage der Zeit. Neben der Tatsache, dass dies unvermeidlich ist, ist dies auch notwendig, da es sich um gegenseitig einfache Teiler handelt, die Informationen über den Wert einer Zahl enthalten. Gleichzeitig brechen große Primzahlen alles sehr schnell. Es gibt also einen Konflikt.Das Letzte, was es zu beachten gilt, ist, dass ich immer noch doppelt so viele Bits wie die Standard-Gleitkommazahl verwendet habe, sodass es hier bisher keine wirklichen Vorteile gibt. Natürlich habe ich versucht, rationale 16/16-Bit-Zahlen zu verwenden, was ein ehrlicherer Vergleich mit den tatsächlichen Anforderungen für die Gleitkomma-Arithmetik wäre, aber mit einer Genauigkeit von 16/16 hat das System, das ich mit Zähler + Nenner + GCD geschrieben habe, vollständig unleserliche Bilder erstellt.Test 3 - Normalisierung rationaler Zahlen
, . , .
, , , , , ( , — , . , , , ).
Wie dem auch sei, ich habe mich entschlossen zu prüfen, was mit den Renderings passieren würde, wenn ich Zähler und Nenner irgendwie vor Überlaufen schützen würde. Am einfachsten wäre es, sowohl den Zähler als auch den Nenner bei Bedarf um eine ausreichende Anzahl von Bits nach rechts zu verschieben, bis sie wieder in dem ihnen zugewiesenen Bitraum erscheinen. Tatsächlich bedeutet dies eine ganzzahlige Division sowohl des Zählers als auch des Nenners durch einen Wert, was bedeutet, dass der Wert der Zahl ungefähr unverändert bleibt . Und hier bin ich vom ursprünglichen Ziel des Experiments abgewichen.In meiner ersten Implementierung habe ich mir die Anzahl der für Zähler und Nenner benötigten Bits angesehen, das Maximum für beide genommen und beide um diese Anzahl von Bits verschoben (auf die nächste Ganzzahl gerundet). Als dies in den Additions- und Multiplikationsoperatoren implementiert wurde, sah alles ziemlich akzeptabel aus:Rationale 65-Bit-Zahlen, reduziert durch GCD und NormalisierungGleitkomma-StandardDa alles ziemlich gut aussah, habe ich zu diesem Zeitpunkt das Problem einer großen Anzahl von Bits gelöst, die in der aktuellen Implementierung verwendet wurden. Ich habe versucht, 16/16 (33 Bit) anstelle von 32/32 (65 Bit) zu verwenden, und die Bilder erwiesen sich als überraschend gut! Ich habe immer noch gesehen, dass es an einigen Rändern der Kugel kleine Löcher gibt, und in der Figur der Textur des Dreiecks gibt es kleine Lücken. Dies ist jedoch nicht schlecht für Größen, die nahe genug an Gleitkommazahlen liegen. Es gab mir Energie, neue Ideen zu lernen.Test 4 - Floating Slash
Zu diesem Zeitpunkt habe ich mich entschlossen, mich abzulenken und nicht mehr nach Ausreden zu suchen. Wenn ich etwas Interessantes für das Rendern in rationalen Zahlen finden möchte, sollten sie 32 Bit und nicht mehr belegen. Es ist besser, eine gute Idee zu finden oder anzuhalten und dort zu enden (dies war zu Beginn des zweiten Versuchsabends).Zuerst dachte ich, dass es sich lohnt, an den Ideen von GCD und Normalisierung festzuhalten, aber es war klüger, sich der Speicherung und Verwendung von Bits zu nähern. Das erste, was mir einfiel, war, dass Zähler und Nenner zwar groß werden können, dies aber oft nicht geschieht. Zumindest geschieht dies nicht gleichzeitig. Wenn der Zähler klein ist, können Sie den Nenner daher groß sein lassen und umgekehrt. Nicht verwendete Bits eines von zwei ganzzahligen Werten können verwendet werden, um größere Werte darzustellen. Dann wurde mir klar, dass eine Gleitkommazahl in ähnlicher Weise im Wesentlichen ein Festkommaformat ist, bei dem der „Festpunkt“ variabel gemacht wird. Ich kann meine rationalen Zahlen nehmen und auch das Bitlayout der Bruchbruchvariablen variabel machen. Das heißt, es ist nicht schwer, den Bruch auf 16/16 zu setzen, aber zuzulassen, dass dieselbe 32-Bit-Variable manchmal 16/16 ist.und manchmal 5/27 oder 13/19, je nach Bedarf.Das Auschecken hat sich gelohnt. Auf jeden Fall können einige Zeilen Code zum Ein- und Auspacken in internen Setzern und Gettern schnell geschrieben werden. Das logischste Schema für mich schien 1 | 5 | 26 zu sein, das heißt:1 Bit:
5-Bit- Vorzeichen : Bruchzeilenposition (B)
26-Bit: kombinierte Zähler- und Nennerdaten; der Zähler ist das obere 26-B-Bit, der Nenner ist das untere B-Bit,
wobei der Bruchbalken (B) die Größe des Nenners bestimmt. Zum Beispiel wird die Nummer 7/3 als geschrieben7/3 = 0 00010 000000000000000000000111 11,
Wenn das Vorzeichen 0 einen positiven Wert bedeutet, bezeichnet die Zeile des Bruchs 2 den Nenner (Nummer 3), für dessen Darstellung 2 Bits erforderlich sind, und der Rest der Bits geht an den Zähler.Den Lesern, die mit dem IEEE754-Standard gearbeitet haben, ist diese Beobachtung möglicherweise bekannt: Die binäre Darstellung des Nenners beginnt immer mit „1“, da die Bruchzeilenzahl sie immer auf die kürzeste Darstellung abschneidet. Das heißt, das erste Bit des Nenners ist optional. In diesem Fall kann die Zahl "3" nur durch den Binärwert "1" und den Wert der Bruchlinie "1" dargestellt werden:7/3 = 0 00001 0000000000000000000000111 1
Dieser Trick hat mir nicht nur ein wertvolles Stück gespart, sondern auch einen hervorragenden Nebeneffekt: Wenn der Wert des Bruchteils Null ist, bedeutet dies natürlich gleichzeitig, dass der Nenner 1 ist und kein Speicherplatz zum Speichern benötigt wird. Dies bedeutet, dass sich meine rationale Darstellung von Zahlen plötzlich als vollständig kompatibel mit der üblichen ganzzahligen Darstellung und Arithmetik herausstellte, bis die Werte der Zahlen über 2 26 steigendas heißt zu einer ausreichend großen Schwelle. Was für eine wundervolle Überraschung! Das heißt, theoretisch kann ich genau den gleichen Datentyp "rational" verwenden, um Standard-Rendering- und Shading-Operationen auszuführen, aber auch alle Logik und Aufgaben des Befehlsflusses im Pfad-Tracer ausführen - ich muss nicht mehr zwei Datentypen verwenden, wie es passiert in den meisten Renderern ("int" und "float") und führen Sie Konvertierungen in die eine und die andere Richtung durch! Die Zeit lief mir jedoch davon, so dass ich nicht alle Schleifenindizes von „int“ auf „rational“ änderte. Der Abend neigte sich dem Ende zu und ich musste noch viele Dinge überprüfen, um die Qualität der Renderings zu verbessern.Nachdem ich die Implementierung erstellt hatte, konnte ich sie überprüfen:32-Bit- Bruchzahlen (1 | 5 | 26)32- --, ! - , , - . . , , , , . ( ), , .
Zu diesem Zeitpunkt war ich bereit, einen ernsthafteren Test durchzuführen (aber immer noch experimentell - das System ist noch lange nicht betriebsbereit). Ich habe einen Pfad-Tracer mit einem minimalen Satz von Funktionen implementiert (nicht unbedingt physikalisch genau oder sogar unter Berücksichtigung der Physik) und eine Szene mit mehreren rechteckigen Parallelepipeds und zwei Lichtquellen erstellt, deren Referenzimplementierung auf der GPU hier zu finden ist: https://www.shadertoy.com/view/Xd2fzR .Ich habe die Szene erneut in das C ++ - Framework konvertiert, einige unnötige Strahlennormalisierungen entfernt und das Rendern ausgeführt. Folgendes habe ich bekommen:32-Bit- Bruchzahlen32- , ! , . :
, , ; . , , . , . , , :
64
Die Idee der exakten Arithmetik kann weder in naiven rationalen 64-Bit-Zahlen noch in rationalen 32-Bit-Zahlen (1 | 5 | 26) mit einem Gleitlinienbruch verwirklicht werden. Und funktionieren 64-Bit-Gleitkommazahlen eines Bruchs?Ich implementierte schnell die rationalen Zahlen 1 | 6 | 57 (obwohl ich neue interne x64-Mechanismen zum Verschieben von Bits lernen musste). Diese 57 Bit Zähler / Nenner ermöglichten die Verfolgung eines viel größeren Entfernungsintervalls. Ich habe es tatsächlich geschafft, eine Szene mit mehreren Dreiecken genau zu verfolgenArithmetik (nicht die oben erwähnte Szene mit rechteckigen Parallelepipeds und globaler Beleuchtung, sondern nur ein paar Dreiecke vor der Kamera). Und der Erfolg erwartete mich! Der Koplanaritätstest, den ich implementiert habe, um die Richtigkeit zu überprüfen, erforderte jedoch mehrere Skalar- und Vektorproduktoperationen, wodurch sich die Zahlen zu normalisieren begannen. Obwohl ich wusste, dass der Render genau war, konnte ich ihn daher nicht experimentell „beweisen“. Was für eine Ironie. Im Allgemeinen bedeutet dies, dass 64 Bit für mehrere Dreiecke ausreichten, komplexere Szenen jedoch immer noch auseinanderfallen. Dies ließ mich jedoch über eine andere Frage nachdenken: Gibt es einen Algorithmus, mit dem die Koplanarität getestet werden kann, der nicht auf absoluten Werten, sondern auf modularer Arithmetik basiert? Ich denkeIn der modularen Arithmetik sollten rationale Zahlen nicht in ihrer Größe „explodieren“. Ich hatte keine Zeit, dies alles zu untersuchen, und ich bin kein Experte für Zahlentheorie.Quadratwurzeln
Am letzten (zweiten) Forschungsabend habe ich mich entschlossen, kurz auf dieses Thema einzugehen und neue Informationen zu studieren. Ich wollte die bestmögliche Quadratwurzelfunktion für rationale Zahlen implementieren. Meine derzeitige naive Entscheidung ( schlecht ) hat die ganzzahlige Quadratwurzel des Zählers (mit entsprechender Rundung) genommen und dann dasselbe mit dem Nenner gemacht. Da die Quadratwurzel eines Bruchs ein Bruchteil der Quadratwurzeln von Zähler und Nenner ist, liefert dieser Ansatz im Allgemeinen anständige Ergebnisse, die sich nicht zu sehr von der besten Antwort unterscheiden. Aber er gibt sicherlich nicht die beste rationale Annäherung an die Quadratwurzel einer rationalen Zahl zurück. Er führt zwei statt einer Annäherung durch.Ich habe folgendes versucht: Am Ende suchen wir hier nach zwei ganzen Zahlen x y , ,
() («» , ):
Nachdem ich Wikipedia durchsucht hatte, stellte ich fest, dass diese spezielle Gleichung die sogenannte "Modified Pell's Gleichung" ist. Es gibt Algorithmen, die die kleinsten
x- und
y- Werte finden, um diese Gleichung zu lösen. Leider verlagerte sich meine Aufmerksamkeit schnell auf andere merkwürdige diophantinische Mathematik, und ich fuhr mit der Implementierung eines dieser Algorithmen nicht fort.
Effektivere Reduzierung
In den letzten Minuten des Abends dachte ich darüber nach, die Idee zu untersuchen, mehrere Elemente zu verwenden, die in komplexen geometrischen Operatoren kombiniert werden, beispielsweise in einem Vektorprodukt. Angenommen, die erste Komponente eines Vektorprodukts war
unter der Annahme, dass sy = a / b, tz = c / d, ty = e / f, sz = g / h
Dies bedeutete, dass ich jetzt versuchen kann, gemeinsame Teiler zu finden, zum Beispiel zwischen a und d oder e und h, und sie für die vorläufige Reduktion zu verwenden.
Ich hatte eine andere Idee: Wenn irgendwann die Rendergeschwindigkeit zum Problem wird, können Sie die Schritte zum Suchen nach GCD vollständig deaktivieren und nur die Normalisierung anwenden. Eine schnelle Überprüfung ergab, dass in diesem Fall die Bildrender immer noch akzeptabel sind und mit einer viel höheren Geschwindigkeit gut funktionieren. In diesem Fall erhalten wir natürlich weniger arithmetisch genaue Ergebnisse.
Als Kompromiss können Sie die Implementierung des Verfahrens oder des GCD-Schemas ablehnen und stattdessen etwas mathematisch Einfaches verwenden, das im Code fest codiert und effektiv ist und die Teilbarkeit durch nur 2, 3 und 5 bestimmt. Obwohl wir keine erschöpfende Anzahl von Teilern finden, durch In der Praxis würde dies dazu führen, dass eine große Anzahl von Abkürzungen gefunden wird. Denken Sie darüber nach - die Teilbarkeit durch 2 tritt dreimal häufiger auf als die Teilbarkeit durch 7 und 20 Mal häufiger als die Teilbarkeit durch 41!
Fazit
Nach diesem Experiment begann ich zu glauben, dass es durchaus möglich ist, dass eine Darstellung von Zahlen auf rationalen Zahlen basiert, ähnlich dem, was ich als "Gleitlinienbruch" bezeichne. Eine Darstellung, die mit ganzen Zahlen kompatibel ist und viele Operationen in exakter Arithmetik für viele Aufgaben ausführen kann (vorausgesetzt, die Eingabedaten werden in einer rationalen Form dargestellt). Die 64-Bit-Version (1 | 6 | 57) hat großes Potenzial, obwohl die 32-Bit-Version (1 | 5 | 26) bereits interessante Renderings erstellt.
Wenn es kein Experiment für zwei Abende war, sondern etwas Professionelles, das in einem Studio oder einer Firma erstellt wurde, könnten in Zukunft die folgenden Schritte unternommen werden:
* Erhalten Sie ein Histogramm der Anzahl der genau und nicht genau verfolgten Pixel (mit anderen Worten, der Häufigkeit der Normalisierungsausführung).
* Versuchen Sie, eine hartcodierte Reduzierung der Teiler 2, 3 und 5 zu implementieren und den Prozentsatz der verlorenen exakten Pixel zu messen
* Zeigen Sie den Pixelunterschied zwischen Gleitkomma-Rendering und Bruch-Gleitkomma-Rendering an
* Finden Sie ausgeklügelte Möglichkeiten, die nicht verwendeten Werte des Bitformats "Floating Line Fractions" zu verwenden, um beispielsweise Inf und NaN zu bezeichnen
* Implementieren Sie die Erkennung von NaN, Inf, Unterlauf, Überlauf.
Alles in allem war es eine faszinierende Studie. Dabei entdeckte ich einige Überraschungen, entwickelte eine kleine Erfindung und lernte viel über die Pell-Gleichung, Quadratwurzeln, GCD, interne x86_64-Mechanismen, die Riemann-Zeta-Funktion und einige andere Aspekte. Ich bin sehr zufrieden damit!