Topologie und umfassende Analyse für einen ahnungslosen Spieleentwickler: Komprimieren einzelner 3D-Vektoren

Wie Sie bereits aus meinen vorherigen Artikeln wissen, möchte ich die Spieleentwicklung als Ausrede verwenden, um komplexe Mathematik zu demonstrieren, für die die meisten Menschen sonst keinen Nutzen hätten. Und dieser Artikel ist keine Ausnahme! Ich möchte eine sehr coole Technik zeigen, die den für mich interessanten Punkten entspricht:

• Der Prozess ist klar genug
• es ist viel schneller als die übliche Technik, die die gleiche Aufgabe ausführt
• Es verwendet eine sehr ungewöhnliche Eigenschaft, Gleitkommazahlen im Gleitkommaformat darzustellen, was impliziert, dass ...
• es funktioniert nicht in der klassischen Analyse . Damit dieser Algorithmus theoretisch funktioniert, müssen Sie in die wunderbare Welt der nicht-klassischen Mathematik eintauchen! Und wenn dies Ihre Neugier nicht geweckt hat, weiß ich nicht, was ich sonst tun soll.

Dieser Artikel ist ziemlich lang und theoretisch, da er ein gründliches Studium der Erklärungen erfordert. Nehmen Sie sich also Zeit und lesen Sie die Teile noch einmal durch, von denen Sie dachten, dass sie beim ersten Mal nicht so offensichtlich waren.

Ein bisschen über den Kontext (GPU)

Einer der wichtigen Aspekte, auf die Sie bei der Entwicklung von Spielen und im weiteren Sinne - in jedem Bereich mit aktivem Grafikeinsatz - achten sollten, ist die Bandbreite der GPU. Der Zentralprozessor und die GPU sind separate physische Geräte und müssen synchronisiert werden, um Daten auszutauschen. Wenn Sie bereits eine Parallelverarbeitung durchgeführt haben, bedeutet dies einen erheblichen Zeitverlust, wenn zwei Geräte synchronisiert werden müssen. Das Zusammenspiel von CPU und GPU ist in dieser Hinsicht nicht anders. Daher bemühen wir uns, die Datenübertragung sowohl hinsichtlich der Anzahl der Vorgänge als auch der übertragenen Datenmenge so gering wie möglich zu halten.

Die Minimierung der Anzahl der Datenübertragungsvorgänge erfolgt normalerweise durch Puffern: Wir bemühen uns, alle Daten in die kleinstmögliche Anzahl von Arrays zu packen und dann alles auf einmal zu übertragen, damit wir uns nicht mehr darum kümmern müssen. Die Minimierung der Datenmenge bei Übertragungsvorgängen ist ein völlig anderes Thema, und die Lösungen für dieses Problem sind fast immer individuell. Als extremes Beispiel hierfür können Sie sehen, wie die Destiny-Rendering-Engine die Position, Oberflächennormalen, Material-Flags und 96-Bit-BSDF-Parameter mit vollständiger Anisotropie anpasst, d. H. drei Gleitkommazahlen (ab S. 62). Gute Ergebnisse lassen sich jedoch mit allgemeinen Methoden erzielen, denen dann individuelle Optimierungslösungen hinzugefügt werden.

Heute werden wir die verlustfreie Komprimierung einzelner 3D-Vektoren diskutieren. Dieser Satz enthält mehrere Schlüsselwörter:

• Einzelne 3D-Vektoren : 3D-Vektoren mit einer Länge von 1
• verlustfreie Komprimierung : Verkleinern Sie die Beschreibungen einzelner 3D-Vektoren ohne Genauigkeitsverlust. Dies ist das Gegenteil von verlustbehafteter Komprimierung.
• Separat : Die Vektorcodierung und -decodierung wird ohne Informationen über die Nachbarn durchgeführt. Wenn die Situation umgekehrt wäre, könnte es sich um eine Art Stapelkomprimierung handeln , bei der nicht einzelne Vektoren komprimiert werden, sondern deren Arrays

Bevor ich fortfahre, muss ich den hervorragenden Artikel „Eine Übersicht über effiziente Darstellungen für unabhängige Einheitsvektoren “ von Cigolle, Donow, Evangelakos, Mara, McGuire und Meyer erwähnen, von dem ich mich für meinen Beitrag inspirieren ließ. Ich muss sofort sagen , dass der Algorithmus, über den ich sprechen werde, weniger effizient ist als der im Artikel vorgestellte Okt.- Algorithmus . Wenn Sie maximale Effizienz wünschen, lesen Sie den Artikel und verwenden Sie oct . Der Zweck meines Beitrags ist es, die Schönheit der Verwendung sehr ungewöhnlicher Mathematik zu demonstrieren und gleichzeitig, wie wir später sehen werden, einen sehr praktischen Algorithmus zu erstellen.

Topologie direkt in Ihrem Videospiel

Im Fall der Einheitskugel sind nur θ und φ wichtig, da ρ immer 1 ist und daher redundant ist.

Ausgangspunkt des Algorithmus ist die Beobachtung, dass Einheits-3D-Vektoren Punkten auf einer Kugel entsprechen. Wie Sie wahrscheinlich wissen, ist eine Kugel eine zweidimensionale Oberfläche, dh für die eindeutige Identifizierung von Punkten auf einer Kugel sind nur zwei Koordinaten erforderlich. Ein sehr verbreitetes Beispiel hierfür sind Kugelkoordinaten, bei denen ein Punkt auf der Kugel durch zwei Winkel θ und φ definiert ist.

Interessanterweise ist eine ziemlich unangenehme Eigenschaft, dass obwohl die Kugel und das gefüllte Quadrat (ein möglicher Raum für 2D-Koordinaten) 2D-Objekte sind, es tatsächlich keine Korrespondenz zwischen ihnen gibt. Dies bedeutet, dass es keine Möglichkeit gibt, jedem einzelnen Punkt des Quadrats einen eindeutigen Punkt auf der Kugel zuzuordnen (zumindest in kontinuierlicher Weise). Man sagt, dass sie nicht homöomorph sind (mit anderen Worten, einer hat eine Grenze und der andere nicht). Ein unangenehmes Ergebnis davon ist, dass einige 2D-Koordinaten in dem Sinne verloren gehen, dass verschiedene Koordinaten identischen Punkten auf der Kugel entsprechen (im Fall von sphärischen Koordinaten, wenn φ 0 ist, ist der entsprechende Punkt unabhängig von der Koordinate θ der Nordpol). Bei der Komprimierung verlieren wir wertvolle Bitmuster, mit denen wir die Punkte einer Kugel beschreiben können!

Wenn Sie mehr Mathematik wollen und beweisen möchten, dass das Quadrat und die Kugel nicht homöomorph sind, können Sie die Tatsache nutzen, dass die Kugel im Gegensatz zum Quadrat nicht kontrahierbar ist und die Kontrahierbarkeit eine topologische Eigenschaft ist. Der Borsuk-Ulam-Satz kann auch als Beweis verwendet werden. Sie sagten mir auch, dass Homotopie-Gruppen beim Beweis helfen können, aber dies liegt bereits außerhalb meines Fachgebiets.

Dieses Problem tritt jedoch nicht nur bei sphärischen Koordinaten auf; Darunter leidet jede kontinuierliche 2D-Darstellung der Punkte der Kugel. Denken Sie jedoch für die Zukunft daran.

Sphärische Koordinaten haben auch andere schlechte Eigenschaften:

• Sie haben eine schlechte Verteilung über die Kugel. Wenn zufällige sphärische Koordinaten generiert und zurück in 3D-Punkte konvertiert werden, bilden sie Cluster um die Pole und sind in der Nähe des Äquators ziemlich dünn. Dies ist auf die Tatsache zurückzuführen, dass 3D-Vektoren in der Nähe des Äquators weniger genau unterscheidbar sind.
  
  
  
  
  Verteilung auf einer Kugel von 10.000 gleichmäßig verteilten Kugelkoordinaten
• Ihre Verpackung und ihr Auspacken sind kostspielig. Für das Packen (3D → 2D) werden eine Operation acos und eine atan2 benötigt, was ziemlich kostspielige inverse trigonometrische Funktionen sind, und für das Auspacken (2D → 3D) werden zwei Operationen cos und zwei Operationen sin benötigt , die ebenfalls bei weitem nicht wirtschaftlich sind.

Lesen Sie den obigen Artikel, um mehr über andere Vergleiche von Kugelkoordinaten und andere Komprimierungsmethoden zu erfahren.

Die Aufgabe, Bitmuster zu erhalten ... und die Geschwindigkeit

Die Methode, die wir betrachten werden, hat einen großen Vorteil - ihre Berechnung ist viel schneller, mehr als doppelt so schnell wie die des nicht optimierten naiven Benchmarks (getestet beim Packen und Entpacken von 10 Millionen zufälligen Vektoren in C ++ in Visual Studio 19 auf Intel Core i5 7. Generation). Darüber hinaus weist das Verfahren keine Singularität auf, das heißt, jeder gepackte Punkt entspricht im Gegensatz zu den oben erwähnten sphärischen Koordinaten einem einzelnen ungepackten Punkt.

Wie bereits erwähnt, gibt es keinen Homöomorphismus zwischen der Einheitskugel und dem Einheitsquadrat. Das heißt, wir können nicht jeden einzelnen Punkt auf dem Quadrat ordnungsgemäß an einen anderen einzelnen Punkt auf der Kugel anhängen. Aber lassen Sie uns die folgenden Konstruktionen betrachten - bisher wird uns nur die nördliche Hemisphäre beschäftigen, in der es Punkte mit einer positiven oder Nullkoordinate Z gibt.


Wir haben die nördliche Hemisphäre in die Scheibe „abgeflacht“ und dabei die Z-Koordinate jedes Punktes verworfen (oder ihm den Wert 0 zugewiesen).

Wir haben einen Weg gefunden, um jeden Punkt auf der Nordhalbkugel mit jedem Punkt auf einer einzelnen Scheibe zu verbinden. Einige bemerkenswerte Punkte:

• der Nordpol fällt in (0, 0).
• Jeder Punkt auf der Halbkugelgrenze bleibt derselbe. Insbesondere haben die Halbkugel und die Scheibe die gleiche Grenze. Dies ist logisch, da die Punkte auf der Halbkugelgrenze Z = 0 haben, dh, wenn wir die Z-Koordinate verwerfen, ändern wir nichts.

Plattenkomprimierung: eine einfache komplexe Aufgabe

Die folgende Konstruktion erfordert eine kleine Einführung. Nur für den Fall, ich sage, dass komplexe Zahlen eine Erweiterung des Raums von reellen Zahlen sind (gewöhnliche Zahlen wie 0, 1, 129,43, pi, 335/117, Quadratwurzel 2 usw.), die eine spezielle Zahl verwenden, die ich imaginär nenne Einheit . Komplexe Zahlen haben die Form a + ib , wobei a und b einige reelle Zahlen (der Real- bzw. der Imaginärteil) sind und i die Eigenschaft i² = -1 hat. Dies ermöglicht es uns, komplexe Zahlen mit Punkten auf einer 2D-Ebene abzugleichen. Nehmen wir für z eine komplexe Zahl der Form z = a + ib , so können wir z als Punkt mit Koordinaten ( a , b ) auf der Ebene darstellen. Die Extraktionsfunktionen des "Realteils" und des "Imaginärteils" der komplexen Zahl z werden mit Re (z) und Im (z) bezeichnet .


Die komplexe Zahl z und ihre Werte.

Neben den Real- und Imaginärteilen der komplexen Zahl können auch die Länge und der Winkel berücksichtigt werden, die sie mit der X-Achse bilden, was als polare Darstellung bezeichnet wird . Die Polarlänge und der Polarwinkel sind die Norm | z | und Argument Arg (z) . Eine bequeme Eigenschaft beider Darstellungen ist, dass die Addition komplexer Zahlen durch Addition des Real- und Imaginärteils und die Multiplikation komplexer Zahlen durch Multiplikation der Normen und Addition der Argumente erfolgt .

Hier interessieren uns zwei Operationen: Quadrieren und Ermitteln der Quadratwurzel einer komplexen Zahl. Das Quadrieren einer komplexen Zahl entspricht genau den reellen Zahlen: Multiplizieren Sie sie einfach mit sich selbst, indem Sie die Norm im Wesentlichen quadrieren und das Argument verdoppeln . Beachten Sie, dass wenn die Norm einer komplexen Zahl kleiner als 1 ist, ihre Länge beim Quadrieren kleiner als 1 bleibt. Wenn wir also jede komplexe Zahl auf der Platte nehmen, die einen positiven Realteil hat, und sie alle in ein Quadrat setzen, erhalten wir im Wesentlichen die gesamte Platte.


Auf der linken Seite befinden sich mehrere komplexe Zahlen in der Hälfte der Scheibe mit dem positiven Realteil (X-Koordinate). Rechts ist das Ergebnis der Quadratur all dieser Punkte. Die Hälfte der Festplatte füllt jetzt die gesamte Festplatte!

Ein Trick ist mit dem „Verdoppeln eines Arguments“ verbunden: Er hängt von der Seite der X-Achse ab, auf der der Punkt liegt. Die Regel ist unten gezeigt.


Eine komplexe Zahl mit einem positiven Imaginärteil (Y-Koordinate) dreht sich nach links und eine komplexe Zahl mit einem negativen Imaginärteil (Y-Koordinate) dreht sich nach rechts.

Wie bei reellen Zahlen ist die Quadratwurzel die Umkehrung der Quadratur: Für eine gegebene komplexe Zahl z sind die Quadratwurzeln (zwei von ihnen) die Zahlen c , so dass c² = z ist . Wie im Fall von reellen Zahlen ist auch -c die Quadratwurzel von z , wenn c die Quadratwurzel von z ist . Die der Zahlen c und -c , deren Argument gleich der Hälfte des Arguments z ist , wird als Hauptwert der Quadratwurzel bezeichnet (dies ist vergleichbar mit der positiven Quadratwurzel einer reellen Zahl anstelle der negativen Quadratwurzel).

Wenn Sie verstehen, dass wenn eine komplexe Zahl quadriert wird, ihre Norm quadriert wird und sich ihr Argument verdoppelt, können Sie leicht erraten, dass der Hauptwert der Quadratwurzel die Quadratwurzel aus der Norm entnimmt und das Argument halbiert (gemäß der oben gezeigten Regel, wobei die Pfeile jedoch auf den Kopf gestellt sind). . Wie beim Quadrieren bleibt die Norm kleiner als 1, wenn die Quadratwurzel einer komplexen Zahl mit einer Norm von weniger als 1 gezogen wird. Daher wird die Einheitsplatte in ihre halbpositiven reellen Zahlen "komprimiert".


Links befinden sich mehrere Punkte auf einer einzelnen Platte. Die rechte Seite zeigt das Ergebnis der Quadratwurzelung aller dieser Punkte. Die ganze Scheibe passt jetzt in die Hälfte von sich!

Dies ist die Grundlage des Algorithmus: Tatsächlich komprimieren wir die gesamte Einheitsscheibe mit dem positiven Realteil zur Hälfte. Wie Sie sich erinnern, haben wir kürzlich die obere Hälfte einer Kugel zu einer einzigen Scheibe abgeflacht. Nun lohnt es sich zu sehen, was wir damit machen werden.

Alles zusammen

Lassen Sie uns zusammenfassen, was wir gerade getan haben: Wir haben die Hälfte der Kugel zu einer Einheitsscheibe abgeflacht, die Z-Koordinate aller ihrer Punkte verworfen und die Einheitsscheibe mit dem positiven Realteil unter Verwendung des komplexen Quadratwurzel-Hauptwerts in ihre eigene Hälfte gequetscht. Tatsächlich haben wir die halbe Kugel auf die halbe Scheibe abgeflacht! Jetzt können wir mit ein paar Änderungen dasselbe tun, um die verbleibende Hälfte der Kugel in die verbleibende Hälfte der Scheibe zu komprimieren.

Die untere Hälfte der Kugel (alle Punkte der Kugel mit einer negativen Z-Koordinate) wird ebenfalls durch wiederholtes Ablegen der Z-Koordinaten zu einer Einheitsscheibe abgeflacht. Für alle komplexen Zahlen z in der Scheibe nehmen wir jedoch den Wert entgegengesetzt zur Hauptquadratwurzel von z (d. H. Wir nehmen -c anstelle von c) ) Da der Hauptwert der Quadratwurzel immer einen positiven Realteil hat, hat der entgegengesetzte Wert immer einen negativen Realteil; Tatsächlich haben wir die verbleibende Hälfte der Kugel in die verbleibende Hälfte der Scheibe abgeflacht, und die Komprimierungsstufe ist nun abgeschlossen!


Voller Komprimierungsschritt. Beachten Sie, dass die nördliche und die südliche Hemisphäre (blau und orange) zu zwei Kopien einer einzelnen Platte abgeflacht und dann zu zwei Hälften einer einzelnen Platte komprimiert werden.

Der Komprimierungsalgorithmus lautet wie folgt:

function packUnitVector(unit) disk = new Complex(unit.x, unit.y) packed = principalSquareRoot(disk) return unit.z < 0 ? -packed : packed 

Und so haben wir in nur drei Zeilen Pseudocode die gesamte Theorie angewendet, die wir untersucht haben, um einen effektiven Algorithmus zu erstellen. Wenn Ihre Umgebung keine Formel für den Hauptwert der Quadratwurzel hat, finden Sie diese auf Wikipedia (besondere Aufmerksamkeit sollte der Auswahl des Vorzeichens des Imaginärteils gewidmet werden). Hier ist die Referenz-C ++ - Implementierung, die ich in meinem Code verwende:

 // Principal complex square root of 'x + iy' float2 csqrt(float x, float y) { float r = sqrt(x * x + y * y); return float2(sqrt((r + x) / 2), (y < 0 ? -1 : 1) * sqrt((r - x) / 2)); } 

Komm zurück

Wir haben die Komprimierung gemeistert und fahren nun mit dem Auspacken fort.

Das Auspacken erfolgt in umgekehrter Reihenfolge aller Komprimierungsschritte:

• Wir erweitern sowohl die positive als auch die negative Hälfte der materiellen Teile einer einzelnen Scheibe in zwei volle Scheiben
• Ordnen Sie jeder vollen Scheibe die entsprechende Halbkugel zu

Kurz gesagt, wir beginnen mit dem gepackten Wert von p , quadrieren ihn, um zu dem Punkt auf der Scheibe zurückzukehren, der von einer der Hemisphären erhalten wurde, und verwenden dann das Zeichen Re (p) , um herauszufinden, von welcher Hemisphäre der Punkt auf der Scheibe stammt. Mit der Gleichung x² + y² + z² = 1 , die die Punkte auf der Einheitskugel definiert, können wir die fehlende Z-Koordinate des gepackten Punktes nachbilden .

Es ist zu beachten, dass die Berechnung des Quadrats des gepackten Werts immer den richtigen Punkt der Scheibe ergibt, unabhängig von ihrer anfänglichen Halbkugel (obere oder untere), da z² = (-z) ² .

Der Dekomprimierungsalgorithmus lautet wie folgt:

 function unpackUnitVector(packed): disk = packed * packed unit = new Vec3() unit.x = disk.real() unit.y = disk.imag() unit.z = sqrt(1 - unit.x * unit.x - unit.y * unit.y) * (packed.real() < 0 ? -1 : 1) return unit 

Und so haben wir einen Algorithmus erhalten, der sehr effizient eine 2D-Darstellung einzelner 3D-Vektoren erstellt, die im Gegensatz zu sphärischen Koordinaten keine Bitmuster verliert und keine Singularität aufweist. Wenn Sie einige Optimierungstricks nicht berücksichtigen, um die Berechnungen zu beschleunigen, ist dies eine fast fertige Version des Algorithmus.

… oder nicht? Wenn Sie genau hinschauten, bemerkten Sie, dass hier etwas nicht stimmt. Ich sagte, dass die Kugel und das Einheitsquadrat nicht homöomorph sind und dennoch irgendwie einen eindeutigen Punkt auf der Scheibe an jeden eindeutigen Punkt auf der Kugel binden konnten? Darüber hinaus haben wir keine nicht-klassische Mathematik erwähnt. Was passiert also?

Tatsächlich hat unser Algorithmus einen schwerwiegenden Nachteil: Er funktioniert für jeden Punkt in der gesamten Kugel, mit Ausnahme von Punkten auf der Nordhalbkugel mit Y = 0 und X <= 0, die beim Packen und Entpacken fälschlicherweise mit dem entsprechenden Punkt auf der Nordhalbkugel verglichen werden.

Der Grund dafür ist, dass, wenn ihre Koordinaten Z verworfen werden, die entsprechende komplexe Zahl eine negative reelle Zahl ist und keinen Imaginärteil hat. Wenn wir den Hauptwert der Quadratwurzel einer negativen reellen Zahl nehmen, erhalten wir wiederum eine vollständig imaginäre komplexe Zahl, die keinen reellen Teil hat (dies ähnelt der Tatsache, dass der Hauptwert der Quadratwurzel von -1 gleich i ist ). Dann versuchen wir, das Vorzeichen der Z-Koordinate im Wesentlichen auf Null zu halten.


Problemstreifen. Punkte mit Y = 0 und X <= 0 werden in eine Reihe rein imaginärer Zahlen mit undefinierbaren Realteilen gepackt.

Mal sehen, was passiert, wenn wir zwei solche Punkte packen (nicht vergessen, dass x <= 0 ist).

  |  Nordpunkt |  South Point
  Einheit |  (x, 0, z) |  (x, 0, -z)
  Datenträger |  x + 0i |  x + 0i
 verpackt |  0 + √ (-x) i |  -0 - √ (-x) i 

Da der Imaginärteil der Projektion beider Punkte auf die Scheibe gleich Null ist, können wir das Vorzeichen der Z-Koordinate nicht im Vorzeichen des Realteils des Hauptwerts der Quadratwurzel speichern, da es selbst gleich Null ist. Wir können einfach darüber nachdenken und akzeptieren, dass der Algorithmus für diese Punkte nicht funktioniert - oder wir können weitermachen.

Vergiss was wir gelernt haben

In allen mir bekannten Bereichen und Zweigen der Mathematik wird angenommen, dass 0 = -0 ist. Dies folgt aus der Definition von -a , die das Gegenteil von a ist und besagt, dass "-a die einzige Zahl ist, die 0 ergibt, wenn sie mit a summiert wird" . Da 0 auch in Bezug auf Addition ein Nullelement ist ( 0 + a = a + 0 = a ), müssen Sie nur 0 zu 0 hinzufügen, um 0 zu erhalten, und zwar 0 selbst.

In der Softwareentwicklung ist jedoch alles anders. In den meisten Darstellungen von Gleitkommazahlen wird zusammen mit dem Exponenten und der Mantisse ein zusätzliches Bit zum Speichern des Zeichens verwendet. Das heißt, wenn der Exponent und die Mantisse 0 sind, kann das Vorzeichenbit verwendet werden, um zwischen positiven und negativen Nullen zu unterscheiden. In den meisten Programmiersprachen (wenn nicht allen) werden beide Nullen als eine einzige Null behandelt (versuchen Sie es einfach mit 0 == -0 ), aber es gibt einen Unterschied. Dies kann festgestellt werden, wenn Sie versuchen, „-0“ und „0“ an das Terminal auszugeben "- so werden sie abgeleitet.

Dies ist sehr wichtig für uns: Der Wert Null kann tatsächlich zum Speichern von Informationen über das Zeichen verwendet werden! Tatsächlich wird es trotzdem korrekt gespeichert. in unserem Fall ist das Problem, dass es nicht richtig gelesen wird. Wenn wir uns die vorletzte Zeile im Entpack-Algorithmus ansehen, werden wir Folgendes sehen:

 packed.real() < 0 ? -1 : 1 

Diese Operation liest das Vorzeichen des Realteils des gepackten Werts, um zu bestimmen, zu welcher Hemisphäre der Punkt gehört - Norden oder Süden. Wenn packet.real () jedoch 0 oder -0 ist, wird das Zeichen vom Vergleichsoperator ignoriert und der ternäre Operator gibt immer 1 zurück. Die richtige Art, das Zeichen zu lesen, ist eine echte Anfrage nach dem Status des Vorzeichenbits, z. B. mit std :: signbit von C ++ oder np .signbit von Numpy nach Python - die Funktion ist sprachabhängig. Denken Sie daran, dass das Vorzeichenbit 1 ist, wenn die Zahl negativ ist, und 0, wenn die Zahl positiv ist.

So erhalten wir eine korrigierte und hundertprozentig funktionierende Funktion:

 function unpackUnitVector(packed): disk = packed * packed unit = new Vec3() unit.x = disk.real() unit.y = disk.imag() unit.z = sqrt(1 - unit.x * unit.x - unit.y * unit.y) * (signbit(packed.real()) ? -1 : 1) return unit 

Das ist alles! Damit ist der Algorithmus abgeschlossen. Nicht-klassische Mathematik äußert sich in der Tatsache, dass wir die Tatsache verwenden, dass 0 von -0 abweicht, was für alle Bereiche der Mathematik, die ich kenne, falsch ist. Es gibt jedoch eine Möglichkeit, diese Fremdartigkeit in einem theoretischen, mathematisch strengen Sinn logisch zu machen.

Räume, die sich nicht an die Regeln halten: eine gerade Linie mit zwei Ursprungspunkten

Um das Folgende besser zu verstehen, sollten Sie die Konzepte von Äquivalenzklassen und Nachbarschaften kennen. Dies ist optional, wird aber klarer.

Wir können die Konsistenz dieser Kuriosität mit einem "Vorzeichen Null" sicherstellen, beginnend mit einem interessanten topologischen Raum: einer geraden Linie mit zwei Ursprungspunkten.


Eine gerade Linie mit zwei Ursprungspunkten ist eine gewöhnliche reale numerische Achse, die für sich selbst irgendwie um eine zusätzliche 0 gewachsen ist.

Eine gerade Linie mit zwei Ursprungspunkten ergibt sich, wenn wir zwei reelle numerische Achsen nehmen und jede Zahl mit Ausnahme von 0 mit dem Gegenteil verbinden. Formal ist eine gerade Linie mit zwei Ursprungspunkten ein Quotientenraum R² mit einer Äquivalenzbeziehung, die zwei Zahlen identifiziert, wenn sie gleich und sind sind nicht 0. Das Ergebnis ist eine gerade Linie von reellen Zahlen mit zwei unterschiedlichen Nullen, die von jedem Punkt gleich weit entfernt sind, sich aber gleichzeitig voneinander unterscheiden. Formal haben zwei beliebige Nachbarschaften jeder der Nullen immer einen nicht leeren Schnittpunkt.

Wir können dies erweitern und versuchen, das in diesem Artikel verwendete "disk-like" -Objekt zu definieren. Früher haben wir das Vorzeichen der Z-Koordinate des Punktes im Realteil der Hauptquadratwurzel seiner Projektion auf die komplexe Scheibe gewaltsam beibehalten, auch wenn dieser Realteil 0 ist. Dies bedeutet, dass wir keine komplexen Zahlen verwendet haben, sondern ein ähnliches Konzept: eine komplexe Zahl, Der Imaginärteil ist eine reelle Zahl, und der Realteil ist ein Punkt auf einer Linie mit zwei Ursprungspunkten, sodass wir den Realteil gleich +0 und -0 unterscheiden können. Tatsächlich verwenden wir komplexe Zahlen mit zwei Ursprungspunkten!

Tatsächlich fanden wir keine Bijektion (Eins-zu-Eins-Zuordnung) zwischen der Kugel und der Einheitsscheibe, sondern eine Bijektion zwischen der Kugel und der Einheitsscheibe mit zwei Ursprungspunkten. Ich habe nicht geprüft, ob diese Bijektion ein Homöomorphismus ist (ein Homöomorphismus ist eine in beide Richtungen fortlaufende Bijektion), aber vielleicht werde ich es eines Tages tun.

Ein bisschen Topologie am Ende

Abschließend möchte ich betonen, dass die komplexe Ebene, die wir mit zwei Ursprungspunkten verwendet haben, zwar nicht aus derselben Konstruktion wie die gerade Linie mit zwei Ursprungspunkten folgt, dass sie jedoch einer anderen komplexen Ebene mit zwei Ursprungspunkten entspricht, die ähnlich konstruiert ist wie eine gerade Linie mit zwei herkunft.

Im Fall einer geraden Linie mit zwei Ursprungspunkten haben wir an allen Stellen außer 0 zwei Kopien der reellen numerischen Achse geklebt. Wir können dasselbe mit zwei Kopien der komplexen Ebene tun, indem wir jedes Paar gleicher komplexer Zahlen, die nicht 0 sind, zusammenkleben und auf ähnliche Weise komplex werden eine Ebene mit zwei Ursprungspunkten. Diese Konstruktion unterscheidet sich von der Konstruktion einer neuen komplexen Ebene aus einer geraden Linie mit zwei Ursprungspunkten und einer gewöhnlichen reellen numerischen Achse: Die erstere ist ein Faktorraum, und die letztere ist ein Produkt von Räumen. Der einzige Unterschied zwischen den beiden resultierenden Räumen besteht jedoch darin, wie in jedem Raum unterschiedliche Nullen geschrieben werden: Im ersten Fall werden sie als ( 0 + 0i) a und ( 0 + 0i) b gezählt (zwei Nullen aus zwei nicht zusammengeklebten Räumen). und in letzterem werden sie als (0a + 0i) und (0b + 0i ) gelesen. Tatsächlich sind beide Räume homöomorph, sodass Sie einen sicher dort verwenden können, wo der andere benötigt wird.

Fazit

Ich hoffe, Sie haben diesen Ausflug in die Welt der bizarren und obskuren Mathematik genossen. Ich betone noch einmal die Tatsache, dass sich dieser Algorithmus streng genommen schlechter verhält als der Oct- Algorithmus aus dem eingangs erwähnten Artikel. Obwohl es in der Ausführungszeit kurz oder sogar schneller ist, ist seine Punkteverteilung auf der Kugel bei weitem nicht so gut. Ich habe damals diesen Artikel geschrieben, um zu zeigen, wie eine scheinbar fremde Mathematik, ähnlich wie abstrakter Unsinn, tatsächlich eine sehr interessante Anwendung in der realen Welt haben kann. außerdem finde ich diesen abstrakten Quatsch entzückend. Ich hoffe, Sie haben aus dem Artikel etwas Nützliches gelernt, danke fürs Lesen!