Topologia e análise abrangente para um desenvolvedor de jogos desavisado: compactando vetores 3D únicos

Como você já pode entender nos meus artigos anteriores, gosto de usar o desenvolvimento de jogos como uma desculpa para demonstrar matemática complexa para a qual a maioria das pessoas não teria utilidade. E este artigo não é exceção! Quero mostrar uma técnica muito bacana, correspondente a pontos interessantes para mim:

• o processo é claro o suficiente
• é muito mais rápido que a técnica usual que executa a mesma tarefa
• ele usa uma propriedade muito incomum de representar números de ponto flutuante no formato de ponto flutuante, o que implica que ...
• não funciona na análise clássica . Para que esse algoritmo funcione na teoria, você precisa entrar no maravilhoso mundo da matemática não clássica! E se isso não despertou sua curiosidade, não sei mais o que fazer.

Este artigo é bastante longo e teórico, porque requer um estudo aprofundado das explicações; portanto, reserve um tempo e releia as partes que lhe pareciam não tão óbvias na primeira vez.

Um pouco sobre o contexto (GPU)

Um dos aspectos importantes que você deve prestar atenção no desenvolvimento de jogos e, em um sentido mais amplo - em qualquer área com o uso ativo de gráficos - é a largura de banda da GPU. O processador central e a GPU são dispositivos físicos separados e precisam de sincronização para trocar dados. Se você já fez o processamento paralelo, sabe que quando dois dispositivos precisam ser sincronizados, isso significa perder uma quantidade significativa de tempo. A interação da CPU-GPU nesse sentido não é diferente, por isso nos esforçamos para minimizar a transferência de dados, tanto no número de operações quanto na quantidade de dados transferidos.

A minimização do número de operações de transferência de dados geralmente é realizada usando o buffer: nós nos esforçamos para ajustar todos os dados no menor número possível de matrizes e depois transferimos tudo de uma só vez para que não precisemos mais nos preocupar com eles. Minimizar a quantidade de dados nas operações de transferência é um tópico completamente diferente, e as soluções para esse problema são quase sempre individuais. Como um exemplo extremo disso, você pode ver como o mecanismo de renderização Destiny consegue se ajustar à posição, normais da superfície, sinalizadores de material e parâmetros BSDF anisotrópicos completos de 96 bits, ou seja, três números de ponto flutuante (p. 62 em diante). No entanto, bons resultados podem ser alcançados por métodos gerais, aos quais são adicionadas soluções individuais para otimização.

Hoje discutiremos a compactação sem perdas de vetores 3D individuais individuais . Esta frase contém várias palavras-chave:

• Vetores 3D únicos : vetores 3D com um comprimento de 1
• compactação sem perdas : reduza o tamanho das descrições de vetores 3D únicos sem perda de precisão. É o oposto da compactação com perdas.
• Separado : a codificação e decodificação de vetores é realizada sem informações sobre seus vizinhos. Se a situação fosse oposta, poderia ser algo como compactação em lote , na qual não vetores individuais são compactados, mas suas matrizes

Antes de prosseguir, devo mencionar o excelente artigo “Uma Pesquisa de Representações Eficientes para Vetores de Unidades Independentes ”, de Cigolle, Donow, Evangelakos, Mara, McGuire e Meyer, da qual me inspirei para o meu cargo. Devo dizer imediatamente que o algoritmo sobre o qual falarei é menos eficiente que o algoritmo de outubro apresentado no artigo . Se você deseja a máxima eficiência, leia o artigo e use o oct . O objetivo do meu post é mostrar a beleza de usar matemática muito incomum, enquanto cria, como veremos mais adiante, um algoritmo muito conveniente.

Topologia diretamente no seu videogame

No caso da esfera unitária, apenas θ e φ são importantes, porque ρ é sempre 1 e, portanto, redundante.

O ponto de partida do algoritmo é a observação de que os vetores unitários 3D são equivalentes aos pontos em uma esfera. Como você provavelmente sabe, uma esfera é uma superfície bidimensional, ou seja, para a identificação exclusiva de pontos em uma esfera, são necessárias apenas duas coordenadas. Um exemplo muito comum disso são as coordenadas esféricas, nas quais um ponto na esfera é definido por dois ângulos, θ e φ.

Curiosamente, uma propriedade bastante desagradável é que, embora a esfera e o quadrado preenchido (um espaço possível para coordenadas 2D) sejam objetos 2D, realmente não há correspondência entre eles. Isso significa que não há como anexar um ponto único na esfera a cada ponto único do quadrado (pelo menos de maneira contínua); eles são considerados não-homeomórficos (em outras palavras, um tem um limite e o outro não). Um resultado desagradável disso é que algumas coordenadas 2D são perdidas no sentido de que coordenadas diferentes correspondem a pontos idênticos na esfera (por exemplo, no caso de coordenadas esféricas, quando φ é 0, o ponto correspondente será o polo norte, independentemente da coordenada θ). Em termos de compactação, perdemos padrões de bits valiosos com os quais poderíamos descrever os pontos de uma esfera!

Se você deseja mais matemática e deseja provar que o quadrado e a esfera não são homeomórficos, pode usar o fato de que a esfera, em contraste com o quadrado, não é contratável e a contratabilidade é uma propriedade topológica; O teorema de Borsuk-Ulam também pode ser usado como prova. Eles também me disseram que os grupos de homotopia podem ajudar com a prova, mas isso já está fora da minha área de especialização.

No entanto, esse problema surge não apenas com coordenadas esféricas; qualquer representação 2D contínua dos pontos da esfera sofrerá com isso. No entanto, lembre-se disso para o futuro.

As coordenadas esféricas também têm outras propriedades ruins:

• Eles têm uma má distribuição sobre a esfera. Se coordenadas esféricas aleatórias forem geradas e convertidas de volta para pontos 3D, elas formarão aglomerados em torno dos pólos e serão rarefeitas perto do equador. Isso se deve ao fato de que os vetores 3D próximos ao equador serão menos precisamente distinguíveis.
  
  
  
  
  Distribuição em uma esfera de 10.000 coordenadas esféricas uniformemente distribuídas
• Sua embalagem e desembalagem são caras. Para empacotar (3D → 2D), são necessárias uma operação acos e uma atan2 , que são funções trigonométricas inversas bastante caras, e para descompactar (2D → 3D) são necessárias duas operações cos e duas operações sin , que também estão longe de serem econômicas.

Confira o artigo acima para aprender sobre outras comparações de coordenadas esféricas e outros métodos de compressão.

A tarefa de preservar padrões de bits ... e velocidade

O método que consideraremos tem uma grande vantagem - seu cálculo é muito mais rápido, mais do que o dobro do valor de referência ingênuo não otimizado (testado na embalagem e na descompactação de 10 milhões de vetores aleatórios em C ++ no Visual Studio 19 no Intel Core i5 7a geração). Além disso, o método não possui singularidade, ou seja, cada ponto empacotado corresponde a um único ponto não empacotado, em contraste com as coordenadas esféricas mencionadas acima.

Como mencionado anteriormente, não há homeomorfismo entre a esfera unitária e o quadrado unitário, ou seja, não podemos amarrar adequadamente cada ponto único do quadrado a outro ponto único da esfera. Mas vamos considerar as seguintes construções - até agora, apenas o hemisfério norte, em que há pontos com uma coordenada Z positiva ou zero, nos interessará.


Nós “achatamos” o hemisfério norte no disco, descartando a coordenada Z de cada ponto (ou atribuindo a ele um valor 0).

Encontramos uma maneira de anexar todos os pontos do hemisfério norte a todos os pontos em um único disco. Alguns pontos dignos de nota:

• o polo norte cai em (0, 0).
• cada ponto no limite do hemisfério permanece o mesmo. Mais especificamente, o hemisfério e o disco têm o mesmo limite. Isso é lógico, porque os pontos no limite do hemisfério têm Z = 0, ou seja, descartando a coordenada Z, não mudamos nada.

Compactação de disco: uma tarefa complexa simples

A construção a seguir requer uma pequena introdução. Apenas no caso, direi que números complexos são uma extensão do espaço de números reais (números comuns como 0, 1, 129,43, pi, 335/117, raiz quadrada 2 e assim por diante), que usa um número especial chamado imaginário unidade . Números complexos têm a forma a + ib , onde a e b são alguns números reais (respectivamente, as partes real e imaginária), e i tem a propriedade i ² = -1. Isso nos permite combinar números complexos com pontos em um plano 2D. Se tomarmos para z um número complexo da forma z = a + ib , poderemos representar z como um ponto com coordenadas ( a , b ) no plano. As funções de extração da “parte real” e da “parte imaginária” do número complexo z são denotadas por Re (z) e Im (z) .


O número complexo z e seus valores.

Além das partes reais e imaginárias do número complexo, também é possível considerar o comprimento e o ângulo formado por ele com o eixo X. Isso é chamado de representação polar . O comprimento polar e o ângulo polar são a norma | z | e argumento Arg (z) . Uma propriedade conveniente de ambas as representações é que a adição de números complexos é feita adicionando as partes reais e imaginárias , e a multiplicação de números complexos é feita multiplicando as normas e adicionando os argumentos .

Aqui estamos interessados ​​em duas operações: quadratura e obtenção da raiz quadrada de um número complexo. Esquadrar um número complexo é exatamente o mesmo que para números reais: simplesmente o multiplicamos por nós mesmos, essencialmente esquadrando a norma e dobrando o argumento . Observe que, se a norma de um número complexo for menor que 1, ao quadrá-lo, seu comprimento permanecerá menor que um; Assim, se pegarmos cada número complexo no disco que possui uma parte real positiva e os colocarmos em um quadrado, obteremos essencialmente o disco inteiro.


À esquerda, existem vários números complexos na metade do disco com a parte real positiva (coordenada X). À direita está o resultado da quadratura de todos esses pontos. Metade do disco agora preenche todo o disco!

Um truque está associado à “duplicação de um argumento”: depende do lado do eixo X no qual o ponto se encontra. A regra é mostrada abaixo.


Um número complexo com uma parte imaginária positiva (coordenada Y) gira para a esquerda e um número complexo com uma parte imaginária negativa (coordenada Y) gira para a direita.

Como no caso de números reais, a raiz quadrada é o inverso do quadrado: para um determinado número complexo z , as raízes quadradas (duas delas) são os números c , de modo que c² = z . Como no caso de números reais, se c é a raiz quadrada de z , então -c também é. O dos números c e -c , cujo argumento é igual à metade do argumento z , é chamado o valor principal da raiz quadrada (é semelhante a obter a raiz quadrada positiva de um número real em vez da raiz quadrada negativa).

Se você entender que, quando um número complexo é elevado ao quadrado, sua norma é elevada ao quadrado e seu argumento é dobrado, é fácil adivinhar que o valor principal da raiz quadrada retira a raiz quadrada da norma e reduz pela metade o argumento (seguindo a regra mostrada acima, mas com as setas viradas ao contrário) . Como no caso da quadratura, ao obter a raiz quadrada de um número complexo com uma norma menor que 1, a norma permanece menor que 1; portanto, "comprime" o disco da unidade em seus números reais semi positivos.


À esquerda, existem vários pontos em um único disco. O lado direito mostra o resultado de obter a raiz quadrada de todos esses pontos. O disco inteiro agora cabe na metade de si!

Esta é a base do algoritmo: na verdade, compactamos todo o disco da unidade em metade e meia com a parte real positiva. Como você se lembra, recentemente achatamos a metade superior de uma esfera em um único disco; Agora vale a pena ver o que faremos com isso.

Juntando tudo

Vamos resumir o que acabamos de fazer: achatamos metade da esfera em um disco unitário, descartando a coordenada Z de todos os seus pontos e comprimimos o disco unitário em sua própria metade com a parte real positiva usando o valor da raiz quadrada principal complexa. De fato, achatamos metade da esfera em metade do disco! Agora, com algumas alterações, podemos fazer o mesmo para comprimir a metade restante da esfera na metade restante do disco.

Da mesma forma, a metade inferior da esfera (todos os pontos da esfera com uma coordenada Z negativa) é achatada em um disco unitário, eliminando repetidamente as coordenadas Z. No entanto, para todos os números complexos z no disco, assumimos o valor oposto à raiz quadrada principal de z (ou seja, pegamos -c em vez de c ) Como o valor principal da raiz quadrada sempre tem uma parte real positiva, o valor oposto sempre terá uma parte real negativa; de fato, achatamos a metade restante da esfera na metade restante do disco e o estágio de compactação agora está completo!


Etapa de compactação completa. Observe que os hemisférios norte e sul (azul e laranja) são achatados em duas cópias de um único disco e, em seguida, compactados em duas metades de um único disco.

O algoritmo de compactação é o seguinte:

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

E assim, em apenas três linhas de pseudocódigo, aplicamos toda a teoria que examinamos para criar um algoritmo eficaz. Se o seu ambiente não possui uma fórmula para o valor principal da raiz quadrada, ela pode ser encontrada na Wikipedia (atenção especial deve ser dada à escolha do sinal da parte imaginária). Aqui está a implementação de C ++ de referência que eu uso no meu código:

 // 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)); } 

Volta

Lidamos com a compactação, agora procedemos à descompactação.

A descompactação consiste na ordem inversa de todas as etapas de compactação:

• expandimos as metades positiva e negativa das partes materiais de um único disco em dois discos completos
• combine cada disco completo com seu hemisfério correspondente

Em resumo, começamos com o valor compactado de p , esquadrá-lo para retornar ao ponto no disco obtido de um dos hemisférios e, em seguida, usamos o sinal Re (p) para descobrir de qual hemisfério o ponto no disco é retirado. Usando a equação x² + y² + z² = 1 , que define os pontos na esfera unitária, podemos recriar a coordenada Z ausente do ponto empacotado.

Note-se que o cálculo do quadrado do valor compactado sempre nos dará o ponto correto do disco, independentemente do seu hemisfério inicial (superior ou inferior), porque z² = (-z) ² .

O algoritmo de descompressão é o seguinte:

 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 

E, portanto, obtivemos um algoritmo que cria com eficiência uma representação 2D de vetores 3D únicos, que, diferentemente das coordenadas esféricas, não perde nenhum padrão de bits e não possui singularidade. Se você não levar em consideração alguns truques de otimização para acelerar os cálculos, esta é uma versão quase pronta do algoritmo.

... ou não? Se você assistiu com atenção, notou que algo está errado aqui. Eu disse que a esfera e o quadrado unitário não são homeomórficos e, de alguma forma, conseguiram vincular um ponto único do disco a cada ponto único da esfera? Além disso, não mencionamos nenhuma matemática não clássica, então o que está acontecendo?

De fato, nosso algoritmo tem uma séria desvantagem: ele funciona para todos os pontos da esfera inteira, exceto para os pontos no hemisfério norte com Y = 0 e X <= 0, que, ao empacotar e descompactar, são erroneamente comparados com o ponto correspondente no hemisfério norte.

A razão para isso é que, quando suas coordenadas Z são descartadas, o número complexo correspondente é um número real negativo, não possui uma parte imaginária. Quando assumimos o valor principal da raiz quadrada de um número real negativo, obtemos um número complexo completamente imaginário que não possui uma parte real (isso é semelhante ao fato de que o valor principal da raiz quadrada de -1 é igual a i ). Em seguida, tentamos manter o sinal da coordenada Z no que é essencialmente zero.


Faixa de problema. Pontos com Y = 0 e X <= 0 são agrupados em uma linha de números puramente imaginários com partes reais indefiníveis.

Vamos ver o que acontece quando empacotamos dois desses pontos (não esqueça que x <= 0).

  |  Ponto norte |  Ponto sul
  unidade  (x, 0, z) |  (x, 0, -z)
  disco  x + 0i  x + 0i
 embalado |  0 + √ (-x) i |  -0 - √ (-x) i 

Como a parte imaginária da projeção no disco de ambos os pontos é igual a zero, não podemos armazenar o sinal da coordenada Z no sinal da parte real do valor principal da raiz quadrada, porque ela própria é igual a zero. Podemos simplesmente insistir nisso, aceitando o fato de que o algoritmo não funciona para esses pontos - ou podemos seguir em frente.

Esqueça o que aprendemos

Em todas as áreas e ramos da matemática que conheço, assume-se que 0 = -0. Isso decorre da definição de -a , que é o oposto de a , afirmando que "-a é o único número que dá 0 quando somada com a" . Como 0 também é um elemento zero em relação à adição ( 0 + a = a + 0 = a ), a única coisa que você precisa adicionar a 0 para obter 0 é o próprio 0.

No entanto, no desenvolvimento de software, tudo é diferente. Na maioria das representações de números de ponto flutuante, junto com o expoente e a mantissa, um bit extra é usado para armazenar o caractere. Isso significa que quando o expoente e a mantissa são 0, o bit de sinal pode ser usado para distinguir entre zeros positivos e negativos. Na maioria das linguagens de programação (se não todas), esses dois zeros são tratados como um único zero (tente fazer 0 == -0 ), mas há uma diferença, e isso pode ser visto se você tentar enviar “-0” e “0 para o terminal "- é assim que eles serão deduzidos.

Isso é extremamente importante para nós: o valor zero pode realmente ser usado para armazenar informações sobre o sinal! De fato, ele é armazenado corretamente de qualquer maneira; no nosso caso, o problema é que não é lido corretamente. Se observarmos a penúltima linha no algoritmo de descompactação, veremos o seguinte:

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

Esta operação lê o sinal da parte real do valor compactado para determinar a qual hemisfério o ponto pertence - norte ou sul. Entretanto, no caso em que embal.real () é 0 ou -0, o caractere é ignorado pelo operador de comparação e o operador ternário sempre retorna 1. A maneira correta de ler o caracter é uma solicitação real para o status do bit de sinal, por exemplo, usando std :: signbit de C ++ ou np .signbit de Numpy para Python - a função depende da linguagem. Lembre-se de que o bit do sinal é 1 quando o número é negativo e 0 quando o número é positivo.

Assim, obtemos uma função de trabalho corrigida e cem por cento:

 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 

Isso é tudo! Agora o algoritmo está completo. A matemática não clássica se manifesta no fato de que usamos 0 que difere de -0, o que é falso para todas as áreas da matemática que eu conheço. No entanto, existe uma maneira de tornar essa estranheza lógica em um sentido teórico, matematicamente rigoroso.

Espaços que não cumprem as regras: uma linha reta com dois pontos de origem

Para entender melhor o seguinte, você deve conhecer os conceitos de classes de equivalência e vizinhanças. Isso é opcional, mas será mais claro.

Podemos garantir a consistência dessa singularidade com um "sinal zero", começando com um espaço topológico interessante: uma linha reta com dois pontos de origem.


Uma linha reta com dois pontos de origem é um eixo numérico real comum, que de alguma forma aumentou 0 para si.

Uma linha reta com dois pontos de origem é obtida quando pegamos dois eixos numéricos reais e colamos cada número com o seu oposto, com exceção de 0. Formalmente, uma linha reta com dois pontos de origem é um espaço quociente R² com uma relação de equivalência identificando dois números se eles são iguais e não são 0. O resultado é uma linha reta de números reais com dois zeros diferentes eqüidistantes de qualquer ponto, mas ao mesmo tempo diferentes um do outro. Formalmente, quaisquer dois bairros de cada um dos zeros sempre têm um cruzamento não vazio.

Podemos expandir isso e tentar definir o objeto "tipo disco" usado neste artigo. Anteriormente, mantivemos à força o sinal da coordenada Z do ponto na parte real da raiz quadrada principal de sua projeção no disco complexo, mesmo que essa parte real seja 0. Isso significa que não usamos números complexos, mas outro conceito semelhante a eles: um número complexo, cuja parte imaginária é um número real e a parte real é um ponto em uma linha com dois pontos de origem, para que possamos distinguir a parte real igual a +0 e -0. De fato, usamos números complexos com dois pontos de origem!

De fato, não encontramos uma bijeção (mapeamento um a um) entre a esfera e o disco unitário, mas encontramos uma bijeção entre a esfera e o disco unitário com dois pontos de origem. Não testei se essa bijeção é um homeomorfismo (um homeomorfismo é uma bijeção contínua em ambas as direções), mas talvez um dia eu o faça.

Um pouco de topologia no final

Concluindo, quero enfatizar que, embora o plano complexo que usamos com dois pontos de origem não siga a mesma construção da linha reta com duas origens, na verdade, é o equivalente a outro plano complexo com dois pontos de origem construído de maneira semelhante a uma linha reta com duas origens.

No caso de uma linha reta com dois pontos de origem, colamos duas cópias do eixo numérico real em todos os lugares, exceto 0. Podemos fazer o mesmo com duas cópias do plano complexo colando juntos cada par de números complexos iguais que não são 0 e, da mesma forma, ficamos complexos um plano com dois pontos de origem. Essa construção difere da construção de um novo plano complexo a partir de uma linha reta com dois pontos de origem e um eixo numérico real comum: o primeiro é um espaço fatorial e o segundo é um produto de espaços. No entanto, a única diferença entre os dois espaços resultantes é a maneira de escrever zeros diferentes em cada espaço: no primeiro, eles são contados como ( 0 + 0i) ae ( 0 + 0i) b (dois zeros tirados de dois espaços diferentes não colados), e no último eles são lidos como (0a + 0i) e (0b + 0i) . De fato, os dois espaços são homeomórficos, portanto você pode usar com segurança um onde o outro for necessário.

Conclusão

Espero que você tenha gostado dessa excursão ao mundo da matemática bizarra e obscura. Enfatizo novamente o fato de que, estritamente falando, esse algoritmo se comporta pior do que o algoritmo de outubro do artigo que mencionei no início. Embora seja próximo ou até mais rápido no tempo de execução, sua distribuição de pontos na esfera está longe de ser tão boa. Escrevi este artigo para mostrar como a matemática aparentemente alienígena, semelhante ao absurdo abstrato, pode realmente ter uma aplicação muito interessante no mundo real; além disso, acho essa absurda abstrata deliciosa. Espero que você tenha aprendido algo útil com o artigo, obrigado pela leitura!