Qual é o maior nível "relativo" que posso obter usando o float?

13

Assim como foi demonstrado em jogos como o Dungeon Siege e o KSP, um nível grande o suficiente começará a ter falhas por causa de como o ponto flutuante funciona. Você não pode adicionar 1e-20 a 1e20 sem perder a precisão.

Se optar por limitar o tamanho do meu nível, como calculo a velocidade mínima em que meu objeto pode se mover até que comece a ficar instável?

jokoon
fonte

Respostas:

26

Um flutuador de 32 bits possui uma mantissa de 23 bits .

Isso significa que cada número é representado como 1.xxx xxx xxx xxx xxx xxx xxx xx vezes uma potência de 2, em que cada x é um dígito binário, 0 ou 1. (Com exceção de números desnormalizados extremamente pequenos menores que 2126 - eles começam com 0. em vez de 1., mas eu os ignorarei pelo que segue)

Portanto, no intervalo de 2Eu e 2(i+1) , você pode representar qualquer número com uma precisão de ±2(Eu-24)

Como exemplo, para Eu=0 0 , o menor número nesse intervalo é (20 0)1=1 . O próximo número menor é (20 0)(1+2-23) . Se você deseja representar 1+2-24 , terá que arredondar para cima ou para baixo, para um erro de 2-24 ambos os sentidos.

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

Portanto, se suas unidades forem metros, você perderá a precisão milimétrica em torno da banda 16 484 - 32 768 (cerca de 16 a 33 km da origem).

Geralmente, acredita-se que você pode solucionar isso usando uma unidade base diferente, mas isso não é verdade, pois é uma precisão relativa que importa.

  • Se usarmos centímetros como unidade, perderemos a precisão milimétrica na faixa de 1 048 576-2 097 152 (a 10-21 km da origem)

  • Se usarmos hectares como unidade, perderemos a precisão em milímetros na faixa 128-256 (13 a 26 km da origem)

... portanto, alterar a unidade em quatro ordens de magnitude ainda acaba com uma perda de precisão milimétrica em algum lugar na faixa de dezenas de quilômetros. Tudo o que estamos mudando é exatamente onde a banda atinge (devido à incompatibilidade entre a numeração da base 10 e a base 2), não estendendo drasticamente nossa área tocável.

Exatamente quanta imprecisão seu jogo pode tolerar dependerá de detalhes de sua jogabilidade, simulação física, tamanho da entidade / distâncias de desenho, resolução de renderização etc. etc., portanto, é difícil definir um limite exato. Pode ser que sua renderização pareça boa a 50 km da origem, mas suas balas estão se teletransportando pelas paredes ou um script de jogabilidade sensível dá errado. Ou você pode achar que o jogo funciona bem, mas tudo tem uma vibração quase imperceptível devido a imprecisões na transformação da câmera.

Se você conhece o nível de precisão necessário (digamos, um intervalo de 0,01 unidades é mapeado para cerca de 1 px à sua distância típica de visualização / interação e qualquer deslocamento menor é invisível), você pode usar a tabela acima para descobrir onde está perdendo precisão e recue algumas ordens de grandeza por segurança em caso de operações com perdas.

Mas se você estiver pensando em grandes distâncias, talvez seja melhor evitar tudo isso atualizando seu mundo à medida que o jogador se move. Você escolhe uma região conservadora pequena em forma de quadrado ou cubo em torno da origem. Sempre que o jogador se mover para fora desta região, traduza-o e tudo no mundo, retornando pela metade da largura dessa região, mantendo o jogador dentro. Como tudo se move em conjunto, seu player não verá nenhuma alteração. As imprecisões ainda podem acontecer em partes distantes do mundo, mas geralmente são muito menos visíveis do que acontecendo sob seus pés, e você sempre terá alta precisão disponível perto do player.

DMGregory
fonte
1
Recentes é definitivamente o caminho a seguir!
Floris 24/05
2
Que tal usar coordenadas de ponto fixo? Talvez com números inteiros de 64 bits, se necessário?
API-Beast
a pergunta é: quão grande pode ser essa região centralizada? se, por exemplo, no meu jogo, eu quero fotografar a uma grande distância com um zoom forte, preciso absolutamente usar o dobro ou o flutuador é suficiente? não é melhor para os mais recentes, de acordo com um quad tree ou algum algoritmo de blocos?
jokoon
Isso dependerá da estabilidade numérica dos algoritmos empregados pelos seus sistemas de renderização e física - portanto, para uma determinada base de código / mecanismo, a única maneira de saber com certeza é tentar uma cena de teste. Podemos usar a tabela para estimar a precisão máxima (por exemplo, uma câmera a 16 km de um objeto tende a ver pelo menos erros do tamanho de milímetros, portanto o zoom deve ser grande o suficiente para manter aqueles menores que um pixel - se o zoom precisar para ser mais rigoroso com o seu jogo, dobra ou pode ser necessária uma matemática inteligente), mas uma cadeia de operações com perdas pode ter problemas bem antes desse limite hipotético.
DMGregory
Ainda estou me perguntando o que significa para o mundo mais recente de uma API gráfica. Se eu tiver um grande pedaço de geometria instanciada (ou não instanciada), ainda é seguro fazê-lo? Acho que significa traduzir TODAS as transformações, mas se eu fizer isso várias vezes, não há risco de perda de precisão de ponto flutuante?
Jokoon # 6/18
3

É difícil responder, pois depende da escala de sua física: qual é a velocidade mínima aceitável de movimento que NÃO precisa ser arredondada para zero?

Se você precisa de um mundo grande e de uma física consistente, é melhor usar uma classe de pontos fixos.

Por exemplo, disparar uma bola de canhão de qualquer lugar do mundo dará o mesmo resultado e um ponto fixo de 64 bits (32,32) fornece uma enorme quantidade de precisão e mais do que qualquer coisa perceptível na maioria dos jogos. Se sua unidade está a 1 metro, você ainda está a 232 picômetros de precisão a 2147483 km da origem.

Você ainda pode fazer a física local em pontos flutuantes na célula local para economizar no trabalho de programação e usar um mecanismo de física pronto para uso. Ainda será razoavelmente consistente para todos os fins práticos.

Como fase ampla de bônus, o AABB tende a ser mais rápido em ponto fixo devido à latência da FPU. Também é mais rápido converter um ponto fixo em um índice octree (ou quadtree), pois é possível fazer um mascaramento de bits simples.

Essas operações não se beneficiam tanto das instruções do SIMD e do pipelining que normalmente ocultariam a latência da FPU.

Você pode converter as posições em ponto flutuante APÓS subtrair a posição da câmera em ponto fixo para renderizar tudo, evitando problemas de ponto flutuante em um mundo grande e ainda usando um renderizador comum usando pontos flutuantes.

Stephane Hockenhull
fonte
-3

Você pode evitá-lo completamente por multiplicação.
Em vez de trabalhar com flutuadores, apenas multiplique-os por 10 ^ (x), armazene-os e, quando necessário, multiplique novamente por 10 ^ (- x).
A partir disso, depende do tipo de int que você deseja usar.

Anon
fonte
2
Isso não evita o problema. Um formato de ponto fixo ainda possui precisão e alcance finitos - quanto maior o alcance, menor a precisão (com base em onde você coloca esse ponto decimal fixo) -, portanto, a decisão de "quão grande eu posso fazer um nível sem erros de arredondamento visíveis" ainda se aplica.
DMGregory
3
Além disso, a base 10 não é muito prática. Os números de ponto fixo funcionam muito melhor quando você divide o número inteiro em termos de bits (considere 26.6 não assinado - o componente fracionário é o menor de 6 bits ( 1,0 / 64,0 * x & 63) e a parte integral é simplesmente x >> 6) . Isso é muito mais simples de implementar do que elevar algo a uma potência de dez.
Andon M. Coleman