Was ist der größte relative Level, den ich mit float machen kann?

13

Genau wie es bei Spielen wie Dungeon Belagerung und KSP demonstriert wurde, wird ein Level, das groß genug ist, aufgrund der Funktionsweise von Gleitkommazahlen Störungen aufweisen. Sie können 1e-20 nicht zu 1e20 addieren, ohne an Genauigkeit zu verlieren.

Wie berechne ich die Mindestgeschwindigkeit, mit der sich mein Objekt bewegen kann, bis es unruhig wird, wenn ich die Größe meines Levels einschränke?

jokoon
quelle

Antworten:

26

Ein 32-Bit-Float hat eine 23-Bit-Mantisse .

Das bedeutet, dass jede Zahl als 1.xxx xxx xxx xxx xxx xxx xxx xx mal eine Zweierpotenz dargestellt wird, wobei jedes x eine binäre Ziffer ist, entweder 0 oder 1. (Mit Ausnahme von extrem kleinen denormalisierten Zahlen unter 2126 - Sie beginnen mit 0 anstatt mit 1, aber ich werde sie für das Folgende ignorieren.)

Im Bereich von und 2 ( i + 1 ) können Sie also eine beliebige Zahl mit einer Genauigkeit von ± 2 ( i - 24 ) darstellen.2ich2(ich+1)±2(ich-24)

Beispielsweise ist für i = 0 die kleinste Zahl in diesem Bereich (2 ^ 0) * 1 = 1. Die nächstkleinere Zahl ist (2 ^ 0) * (1 + 2 ^ -23). Wenn Sie 1 + 2 ^ -24 darstellen möchten, müssen Sie auf- oder abrunden, für einen Fehler von 2 ^ -24 in beide Richtungen.

In this range:                You get accuracy within:
-----------------------------------------------
         0.25   -     0.5    2^-26 = 1.490 116 119 384 77 E-08
         0.5    -     1      2^-25 = 2.980 232 238 769 53 E-08
         1     -      2      2^-24 = 5.960 464 477 539 06 E-08
         2     -      4      2^-23 = 1.192 092 895 507 81 E-07
         4     -      8      2^-22 = 2.384 185 791 015 62 E-07
         8     -     16      2^-21 = 4.768 371 582 031 25 E-07
        16     -     32      2^-20 = 9.536 743 164 062 5  E-07
        32     -     64      2^-19 = 1.907 348 632 812 5  E-06
        64     -    128      2^-18 = 0.000 003 814 697 265 625
       128    -     256      2^-17 = 0.000 007 629 394 531 25
       256    -     512      2^-16 = 0.000 015 258 789 062 5
       512    -   1 024      2^-15 = 0.000 030 517 578 125
     1 024    -   2 048      2^-14 = 0.000 061 035 156 25
     2 048    -   4 096      2^-13 = 0.000 122 070 312 5
     4 096    -   8 192      2^-12 = 0.000 244 140 625
     8 192   -   16 384      2^-11 = 0.000 488 281 25
    16 384   -   32 768      2^-10 = 0.000 976 562 5
    32 768   -   65 536      2^-9  = 0.001 953 125
    65 536   -  131 072      2^-8  = 0.003 906 25
   131 072   -  262 144      2^-7  = 0.007 812 5
   262 144   -  524 288      2^-6  = 0.015 625
   524 288 -  1 048 576      2^-5  = 0.031 25
 1 048 576 -  2 097 152      2^-4  = 0.062 5
 2 097 152 -  4 194 304      2^-3  = 0.125
 4 194 304 -  8 388 608      2^-2  = 0.25
 8 388 608 - 16 777 216      2^-1  = 0.5
16 777 216 - 33 554 432      2^0   = 1

Wenn Ihre Einheiten also Meter sind, verlieren Sie die Millimetergenauigkeit um das 16 484 - 32 768-Band (ca. 16-33 km vom Ursprung entfernt).

Es wird allgemein angenommen, dass Sie dies umgehen können, indem Sie eine andere Basiseinheit verwenden. Dies ist jedoch nicht der Fall, da es auf die relative Präzision ankommt.

  • Wenn wir als Maßeinheit Zentimeter verwenden, verlieren wir Millimetergenauigkeit im Band 1 048 576-2 097 152 (10-21 km vom Ursprung entfernt).

  • Wenn wir Hektometer als Einheit verwenden, verlieren wir die Millimetergenauigkeit im Bereich 128-256 (13-26 km vom Ursprung entfernt).

... so dass das Ändern der Einheit um vier Größenordnungen immer noch zu einem Verlust an Millimetergenauigkeit im Bereich von einigen zehn Kilometern führt. Alles, was wir verschieben, ist, wo genau in der Band, die es trifft (aufgrund der Nichtübereinstimmung zwischen der Nummerierung der Basis 10 und der der Basis 2), unser spielbares Gebiet nicht drastisch erweitert.

Wie viel Ungenauigkeit Ihr Spiel tolerieren kann, hängt von Details Ihres Gameplays, der Physiksimulation, der Größe des Objekts / der Zeichenentfernung, der Renderauflösung usw. ab. Es ist daher schwierig, einen genauen Grenzwert festzulegen. Es mag sein, dass Ihr Rendering 50 km vom Ursprung entfernt gut aussieht, aber Ihre Kugeln werden durch Wände teleportiert oder ein sensibles Gameplay-Skript geht durcheinander. Sie werden vielleicht feststellen, dass das Spiel gut läuft, aber alles hat eine kaum wahrnehmbare Schwingung aufgrund von Ungenauigkeiten in der Kameratransformation.

Wenn Sie die Genauigkeit kennen, die Sie benötigen (z. B. entspricht eine Spanne von 0,01 Einheiten bei einem typischen Betrachtungs- / Interaktionsabstand etwa 1 px, und ein kleinerer Versatz ist nicht sichtbar), können Sie anhand der obigen Tabelle herausfinden, wo Sie diesen verlieren Genauigkeit, und treten Sie ein paar Zehnerpotenzen zurück, um die Sicherheit bei verlustbehafteten Operationen zu gewährleisten.

Aber wenn Sie über große Entfernungen nachdenken, ist es möglicherweise besser, all dies zu umgehen, indem Sie Ihre Welt neu zentrieren, während sich der Spieler bewegt. Sie wählen einen konservativ kleinen quadratischen oder würfelförmigen Bereich um den Ursprung. Wenn sich der Spieler außerhalb dieser Region bewegt, übersetze sie und alles auf der Welt um die Hälfte der Breite dieser Region und lasse den Spieler drinnen. Da sich alles zusammen bewegt, sieht Ihr Spieler keine Veränderung. Ungenauigkeiten können immer noch in fernen Teilen der Welt vorkommen, sind dort jedoch in der Regel viel weniger auffällig als direkt unter Ihren Füßen, und Sie haben garantiert immer eine hohe Präzision in der Nähe des Players.

DMGregory
quelle
1
Recentering ist definitiv der richtige Weg!
Floris
2
Was ist mit Fixpunktkoordinaten? Möglicherweise mit 64-Bit-Ganzzahlen, falls erforderlich?
API-Beast
Die Frage ist, wie groß diese zentrierte Region sein kann. Wenn ich zum Beispiel in meinem Spiel mit einem starken Zoom aus großer Entfernung schießen möchte, muss ich unbedingt double verwenden oder ist float genug? Ist es nicht besser, nach einem Quad-Baum oder einem Kachel-Algorithmus neu zu zentrieren?
jokoon
Dies hängt von der numerischen Stabilität der von Ihren Rendering- und Physiksystemen verwendeten Algorithmen ab. Für eine bestimmte Codebasis / Engine ist die einzige Möglichkeit, dies mit Sicherheit zu wissen, eine Testszene. Wir können die Tabelle verwenden, um die maximale Genauigkeit zu schätzen (z. B. eine Kamera, die 16 km von einem Objekt entfernt ist, neigt dazu, Fehler mit einer Größe von mindestens Millimetern zu erkennen. Daher sollte Ihr Zoom so weit sein, dass er kleiner als ein Pixel ist - wenn der Zoom dies erfordert Um für Ihr Spiel enger zu werden, müssen Sie möglicherweise das Doppelte oder eine clevere Methode anwenden. Eine Reihe von verlustbehafteten Operationen kann jedoch Probleme verursachen, die weit vor dieser hypothetischen Grenze liegen.
DMGregory
Ich frage mich immer noch, was es bedeutet, die Welt für eine grafische API neu zu zentrieren. Wenn ich einen großen Teil einer instanziierten (oder nicht instanziierten) Geometrie habe, ist es trotzdem sicher, dies zu tun? Ich denke, es bedeutet, ALLE Transformationen zu übersetzen, aber wenn ich das mehrmals mache, besteht dann nicht das Risiko eines Gleitkomma-Präzisionsverlusts?
jokoon
3

Es ist schwer zu beantworten, da es von der Größe Ihrer Physik abhängt: Was ist die akzeptable Mindestbewegungsgeschwindigkeit, die NICHT auf Null gerundet werden darf?

Wenn Sie eine große Welt und konsistente Physik benötigen, ist es besser, eine Festkommaklasse zu verwenden.

Wenn Sie beispielsweise eine Kanonenkugel von überall auf der Welt abschießen, erhalten Sie das gleiche Ergebnis, und ein 64-Bit-Fixpunkt (32,32) bietet Ihnen ein hohes Maß an Präzision und mehr als alles, was in den meisten Spielen wahrnehmbar ist. Wenn Ihr Gerät 1 Meter misst, sind Sie immer noch mit einer Genauigkeit von 232 Pikometern 2147483 km vom Ursprung entfernt.

Sie können die lokale Physik weiterhin in Gleitkommazellen innerhalb der lokalen Zelle ausführen, um Programmierarbeit zu sparen und eine handelsübliche Physik-Engine zu verwenden. Es wird für alle praktischen Zwecke noch einigermaßen konsistent sein.

Als Bonus tendieren breite Phase und AABB aufgrund der FPU-Latenzzeit dazu, im Fixpunkt schneller zu sein. Es ist auch schneller, einen festen Punkt in einen Octree- (oder Quadtree-) Index umzuwandeln, da Sie eine einfache Bitmaskierung durchführen können.

Diese Vorgänge profitieren weniger von SIMD-Befehlen und Pipelining, die normalerweise die FPU-Latenz verbergen würden.

Sie können die Positionen in Gleitkommazahlen umwandeln, NACHDEM Sie die Position der Kamera in Festkommazahlen subtrahieren, um alles zu rendern. Auf diese Weise vermeiden Sie Gleitkommazahlen in einer großen Welt und verwenden weiterhin einen regulären Renderer mit Gleitkommazahlen.

Stephane Hockenhull
quelle
-2

Sie können dies durch Multiplikation ganz vermeiden.
Anstatt mit Floats zu arbeiten, multiplizieren Sie sie einfach mit 10 ^ (x), speichern Sie sie und multiplizieren Sie sie bei Bedarf erneut mit 10 ^ (- x).
Davon hängt es ab, welche Art von Int Sie verwenden möchten.

Anon
quelle
1
Dies vermeidet das Problem nicht. Ein Festkomma-Format hat immer noch eine endliche Genauigkeit und Reichweite - je größer die Reichweite, desto geringer die Genauigkeit (basierend darauf, wo Sie diesen festen Dezimalpunkt setzen) - also die Entscheidung, "wie groß ich eine Ebene ohne sichtbare Rundungsfehler machen kann". gilt immer noch.
DMGregory
3
Darüber hinaus ist Base-10 nicht sehr praktisch. Festkommazahlen funktionieren viel besser, wenn Sie die ganze Zahl in Bits aufteilen (betrachten Sie vorzeichenlose 26.6 - die Bruchkomponente sind die unteren 6-Bits ( 1.0 / 64.0 * x & 63) und der integrale Teil ist einfach x >> 6). . Das ist viel einfacher umzusetzen, als etwas auf eine Zehnerpotenz zu erhöhen.
Andon M. Coleman