1. Introdução
"O que acontece se substituirmos os números de ponto flutuante por números racionais e tentarmos renderizar a imagem?"
Eu me fiz essa pergunta depois de pensar no tweet de um pesquisador e professor de computação gráfica Morgan McGwire. Ele falou sobre o quanto os estudantes de ciência da computação ficam surpresos quando descobrem que, para armazenar os números familiares de ponto flutuante nos computadores modernos, é necessário fazer compromissos. E esses compromissos dificultam tarefas simples, por exemplo, verificar se um ponto pertence a um triângulo. O problema, é claro, é que verificar se quatro pontos estão no mesmo plano (coplanaridade) usando o determinante ou algum tipo de multiplicação de vetor (mas, de fato, é a mesma coisa) nunca dará um valor exatamente igual a zero, o que é necessário estes são métodos matemáticos. Mesmo que os cálculos reais de estar no mesmo plano fossem precisos, os mesmos compromissos com uma precisão de quase 1,0 dariam a resposta de que os quatro pontos em si não são coplanares.
Isso deu origem à ideia em mim - se assumirmos que todos os dados do renderizador recebido (coordenadas de vértices, transformações em 3D etc.) foram definidos como números racionais, eles criariam todas as operações, desde a criação de um raio, passando pela estrutura aceleradora até a interseção raios com triângulos são apenas números racionais? Se fosse esse o caso, poderíamos realizar um teste de coplanaridade exatamente! Você pode estar se perguntando por que uma cena 3D expressa em números racionais deve dar apenas resultados em números racionais ...
Uma cena simples, cujo traçado é realizado pela aritmética racional. Ele usa um sistema numérico de ponto flutuante, não um número de ponto flutuante.Primeiro, um número racional é um número que pode ser expresso como a razão de dois números inteiros, por exemplo 1/2 ou 355/113. Em segundo lugar, "operações normais de renderização", como testes em caixas delimitadoras, verificação da interseção de um raio com um triângulo, reflexão de um raio etc., baseiam-se em produtos vetoriais e escalares, bem como na divisão escalar (isso inclui transformação coordenada e inversão matricial, quaterniões, etc.), que por sua vez se baseiam em quatro operações básicas: adição, subtração, multiplicação e divisão. Ao adicionar, subtrair, multiplicar e dividir números racionais, também são obtidos números racionais. O matemático diria que muitos números racionais formam um campo fechado em quatro operações aritméticas básicas. Para nós, isso significa que, se aderirmos a números exclusivamente racionais, poderemos realmente ir dos dados de entrada da cena 3D para uma imagem totalmente renderizada sem sair do mundo dos números racionais.
Exceções à regra "ações em números racionais dão números racionais" são raízes quadradas e funções trigonométricas / transcendentais. Quanto ao último, eu sempre digo que se você tivesse que realizar cálculos trigonométricos nos interiores geométricos do seu renderizador, provavelmente estava fazendo algo errado (e eu mostrei
como corrigir os casos mais comuns ) [
tradução em Habré]. Quanto às raízes quadradas, com exceção das seções cônicas (esferas, cilindros, etc.) e a realização de sombreamento / DFOS / coloração, não é necessário normalizar os raios e normal para as superfícies com a frequência habitual. Certamente não precisa ser feito para criar um raio, sua passagem, interseção, reflexões etc. Infelizmente, muitas vezes vejo que os programadores normalizam valores por nenhuma outra razão além de "bem, eu não sei, faço isso para poder jogar com segurança". Na prática, na parte da renderização onde a geometria é rastreada, raramente é necessário normalizar os valores, então eu tinha a esperança de que você pudesse rastrear toda a cena sem sair do mundo dos números racionais - isso é o que eu chamaria de "renderização racional".
Para colocar isso em prática, preciso criar um sistema numérico baseado em números racionais que um computador possa usar. Além disso, eu poderia implementar os algoritmos comuns de rastreamento de caminho, calcular imagens sem perda de precisão, executar verificações de coplanaridade com respostas precisas e deixar todos os alunos que estudam computação gráfica felizes.
Este artigo é uma história sobre duas noites de pesquisa sobre o realismo dessa ideia. Vou falar sobre os muitos aspectos que aprendi, sobre o que descobri e sobre algumas surpresas que descobri no processo. O artigo está escrito em uma ordem mais ou menos cronológica do meu trabalho. Além disso, foi escrito em meu estilo incomumente informal e pouco científico (do qual me orgulho). A imagem mostrada acima é uma espécie de spoiler, mas leia o artigo até o fim, porque vou falar sobre o bem e o mal.
Preparação
A primeira coisa que fiz foi implementar em
Shadertoy um rastreador minimamente limitado para uma cena
extremamente simples que consistia em um avião, uma esfera, um paralelepípedo retangular e um triângulo - os blocos de construção de renderizadores reais. Depois copiei o código em um arquivo C ++ e, depois de fazer algumas pequenas alterações, compilei-o usando minha estrutura
piLibs . Portanto, para comparação, obtive uma imagem rastreada renderizada na CPU usando números regulares de acordo com o padrão IEEE754 com um ponto flutuante. Também removi toda a normalização de raios do código de rastreamento, porque, como mencionado acima, nenhum deles é realmente necessário. Deixe-me lembrá-lo de que uma raiz quadrada é necessária para a normalização, e os números racionais não são preservados quando usados (a raiz quadrada de um número racional não é um número racional). Um pouco mais tarde, veremos que a aplicação de raízes quadradas, é claro, ainda é possível, eu só queria tornar o código o mais matematicamente limpo possível para ver até onde posso ir com a aritmética exata dos números racionais sem arredondamentos.
A etapa preparatória final - tomei todas as aulas de vec3, mat4x4 e outras aulas básicas de álgebra / matemática e as alterei para que usassem racional em vez de float. Como minha estrutura racional sobrecarrega todos os operadores padrão (adição, sub, mul, div, inversão de sinal, comparações etc.), a substituição ocorreu sem problemas. Eu rapidamente implementei as operações usuais restantes (abs, sinal, mod, fratura, piso, sqrt etc.), o que teoricamente era suficiente para obter renderizações racionais bonitas.
Teste 1 - A Solução Ingênua
Mas vamos ver como foi essa primeira implementação. No começo, sempre tento o mais simples e depois olho para os resultados. E a maneira mais simples de implementar valores racionais era usar dois números inteiros. Como o nome da seção sugere, essa não será minha decisão final, mas, na primeira tentativa, foi uma decisão razoável. Portanto, cada número
x deve ser representado como o numerador
N e o denominador
D , formando o valor
N /
D. O valor
x é aproximado pelo melhor par
N /
D possível (dentro da profundidade de bits especificada), mais próximo do valor
x verdadeiro. Decidi que ambos os números devem ser positivos, e o sinal do número deve ser armazenado em um bit separado, a fim de simplificar o trabalho e livrar-se de ambiguidades, embora isso não seja muito importante. Nesse estágio, numeradores e denominadores eram do tipo não assinado. Mas, mesmo ao separar o sinal,
N /
D tinha muita redundância: por exemplo, 1/4 e 7/28 denotam o mesmo número, mas têm representações de bits completamente diferentes. Falaremos sobre isso mais tarde, mas, por enquanto, não vamos concentrar nossa atenção e ver como as quatro operações aritméticas básicas se parecem nessa forma racional.
Primeiro, observe que subtrair
a -
b é simplesmente a adição de
a e o valor oposto a
b , ou seja,
a + (
-b ), onde
-b pode ser calculado simplesmente substituindo o sinal de
b . Da mesma forma, dividir
a /
b é o mesmo que multiplicar ae o inverso de
b . Ou, em outras palavras,
a /
b =
a · (1 /
b ), em que (1 /
b ) pode ser calculado simplesmente mudando os locais do numerador
b n e do denominador
b d do número
b . Portanto, aqui está a primeira propriedade interessante da aritmética racional - divisão e multiplicação têm os mesmos custos, portanto, diferentemente da renderização de ponto flutuante usual, na qual as divisões geralmente são evitadas, atrasadas ou ocultas sob os atrasos das solicitações de textura lenta, não há necessidade de ter medo dessas operações na aritmética racional .
Passamos à adição com multiplicação: sabemos que os valores opostos e inversos são trivialmente simples de calcular, então obtemos:
A preservação do sinal durante a multiplicação é trivial, é apenas xor, porque dois valores positivos dão um resultado positivo e dois negativos. Salvar um sinal para adição é um processo mais complicado, e para uma solução rápida eu o implementei através de três ramos (a adição é trivial se os sinais
a e
b coincidem, mas quando eles não coincidem, é necessário selecionar um número menor e subtraí-lo do maior - no artigo eu não Descreverei esses pequenos detalhes com mais detalhes, mas apenas coloque o código-fonte em algum lugar).
Também vou pular a implementação de fract () e floor (); se você decidir implementá-las, verá sua simplicidade e beleza. Também deve ser dada atenção aos operadores de comparação. Tendo cuidado dos sinais e assumindo que
aeb são positivos, obtemos
É importante notar aqui que, mesmo para comparação, precisamos de algumas operações de multiplicação, o que pode levar à transição para o tamanho da próxima palavra e será importante um pouco menor.
Por fim, examinamos as raízes quadradas em uma seção separada, sabendo que na maioria das vezes não precisamos delas (exceto a esfera deste primeiro teste).
Isso foi suficiente para executar a primeira renderização e rastrear a cena de teste (plano + esfera + triângulo + caixa retangular) para ver o que aconteceu. Usei generosamente números racionais de 65 bits para este primeiro teste, que na verdade representa uma grande quantidade de dados (comparável ao tipo de dados "duplo"): 32 bits são obtidos pelo numerador, 32 bits são o denominador e outro bit é o sinal. A primeira é a imagem obtida com essa abordagem ingênua, a segunda é a imagem criada usando números de ponto flutuante (referência):
Números racionais de 65 bits "ingênuos"Referência de ponto flutuanteO resultado foi muito ruim, a caixa e o triângulo nem apareceram na renderização, e a esfera e o plano do piso eram muito barulhentos. O problema, é claro, era que toda vez que meus números racionais realizavam qualquer operação aritmética básica em qualquer um dos estágios algorítmicos da renderização, o numerador e o denominador ficavam cada vez mais incontroláveis, porque a multiplicação inteira era usada. Pense no seguinte: se as unidades do nosso mundo inicial fossem metros e anexássemos a geometria da fonte (vértices e câmera) à precisão milimétrica, apenas os dados da fonte ocupariam um volume de 16 bits para uma cena bastante pequena. Ao mesmo tempo, com resolução de tela HD padrão e suavização de 4x, números de direção racional do feixe exigiriam facilmente 12 bits. Ou seja, durante a primeira interação do feixe e da geometria, a operação aritmética mais simples usando os dois conjuntos de dados de entrada transformaria o resultado em comprimentos de 28 bits - perto o suficiente do limite de 32 bits que eu estabeleci para mim nesta primeira implementação. E isso foi antes mesmo de executarmos o primeiro produto vetorial ou escalar. Quando o produto escalar estiver completo, o renderizador precisará de números racionais com centenas de bits para representar números. Obviamente, esse é o pior caso, mas o caso médio estaria próximo disso. Considerando que aloquei apenas uma capacidade de 32 bits para o numerador e o denominador, é fácil entender a rapidez com que os valores ultrapassam os limites deste teste - não é de surpreender que, com exceção da planta baixa e parte da esfera, quase nada seja visível.
Teste 2 - Redução pelo maior fator comum
Depois, aprimorei o sistema usando a propriedade que mencionei brevemente acima - diferentes números racionais podem significar a mesma quantidade. De fato, 6/12 é o mesmo valor que 1/2, mas usa muito mais bits que o anterior. Portanto, a idéia era a seguinte: se após cada operação aritmética básica (ou depois dela) eu extraísse todos os divisores comuns do numerador e dos denominadores e traga a fração para sua forma mais simples, talvez seja possível manter tudo sob controle e continuar as operações por mais tempo com aritmética exata sem perda de precisão. Talvez você possa fazer isso o suficiente para obter imagens limpas e renderizadas? Vou fazer uma pequena digressão para mostrar outro exemplo: 588/910 pode ser simplificado para 42/65, porque 14 é um divisor de 588 e 910. Mas para armazenar 42/65, obviamente, são necessários menos bits que 588/910. Encontrar o maior número possível que divide simultaneamente os outros dois números pode ser feito usando o algoritmo Great Common Divisor (GCD), cujas implementações eficazes você pode encontrar em qualquer lugar (copiei-o pessoalmente diretamente da Wikipedia e o acelerei um pouco, executando a etapa de verificação) bits usando operações internas x64). Assim, armada com o algoritmo GCD, minha classe racional deve simplificar constantemente as frações geradas durante o processo de renderização. Isso pode ser feito de duas maneiras:
O primeiro é converter o resultado intermediário dos operadores de adição e multiplicação para o próximo tipo de dados de bit (na minha solução ingênua atual é uin64_t), procurar o GCD nesse tipo de dados mais volumoso e reduzir o resultado ao tamanho do bit original (32). A segunda maneira é analisar como
a n ,
a d ,
b n e
b d são combinados entre si nos dois operadores aritméticos e extrair deles divisores comuns antes de realizar a multiplicação. A segunda abordagem basicamente eliminou a necessidade de comprimentos de bits grandes. Sabendo que seria necessário usá-los de qualquer maneira, decidi escolher o primeiro método, porque era mais fácil de implementar e me permitiu acelerar meu trabalho (a noite voa muito rapidamente). Tendo feito tudo isso, vamos ver qual renderização posso criar agora:
Números racionais de 65 bits reduzidos por GCDReferência de ponto flutuanteMuito melhor! Até agora, longe do ideal, é claro, mas parece promissor. Fiz a caixa e o triângulo aparecerem, e a esfera agora parece muito mais volumosa. No entanto, um artefato engraçado apareceu no canto superior direito, e números racionais para muitos pixels ainda vão além dos limites, o que leva a muitos pontos na imagem. No entanto, vale ressaltar que, para alguns (muitos) pixels, comecei a obter resultados
precisos e perfeitos! Ou seja, o rastreador encontrou interseções matematicamente precisas de pontos e distâncias, que foram a causa principal da tentativa de usar números racionais.
Antes de prosseguir para a próxima etapa do processo de comprovação da aplicabilidade dos números racionais, quero parar brevemente e compartilhar minhas descobertas sobre o GCD e a redução dos números racionais.
A primeira descoberta está relacionada ao volume de bits de números racionais. Embora ainda não consiga render belas imagens, isso é mais importante do que me preocupar com a otimização de volumes de dados e, embora essa implementação inicial ainda usasse um grande número de bits (1 + 32 + 32), eu já estava pensando no desperdício mencionado anteriormente bits na forma de frações em excesso. Em particular, após adicionar um estágio com um GCD, combinações de bits como 2/4 não são mais aplicáveis, porque são automaticamente reduzidas a 1/2 antes de serem gravadas em qualquer registro ou variável. Isto é, de certo modo, de todas as 2
64 combinações de bits que poderiam ser um numerador e um denominador, muitas permaneceram sem uso. E você não pode desperdiçar pedaços assim. Ou é possível? Quanto espaço eu realmente perco? Fiz uma pequena digressão para explorar esta questão.
Digressão - em números mutuamente primos
As ilustrações abaixo mostram o uso de bits para números racionais em 5/5 bits e 7/7 bits. Os eixos horizontal e vertical dos gráficos representam os valores do numerador e denominador de todos os números racionais possíveis, com numeradores e denominadores de até 5 bits (31) e 7 bits (127). Pixels pretos são combinações não utilizadas e pixels brancos são frações usadas. Por exemplo, a diagonal inteira é preta, exceto o 1/1 pixel, porque todas as frações do formato n / n são reduzidas para 1/1.
Usando bits para 5/5 racional
Usando bits para 7/7 racionalSe você contar os pixels, como eu fiz, poderá entender rapidamente que a proporção de pixels úteis com um aumento no número de bits tende a 60,8%. Uma pequena pesquisa on-line mostrou-me que essa razão é exatamente 6 / π
2 , porque também é a probabilidade de ser relativamente primo (sem divisores comuns) para dois números aleatórios. Você pode perguntar, de onde veio o pi?
Acontece que “seis por pi ao quadrado” é um valor igual à unidade dividido pela função zie de Riemann calculada no ponto 2, 1 / ζ (2). Isso não deveria nos surpreender muito, porque a função Riemann zeta geralmente aparece em problemas envolvendo números primos e mutuamente primos.Seja como for, na minha visão racional, desperdicei cerca de 40% das combinações de bits. E, embora este pareça um número grande, eu decidi olhar para ele como se fosse realmente um pouco menos ... graças ao qual eu não poderia estar muito chateado. Com isso em mente, decidi seguir em frente, usando outras abordagens completamente diferentes, em vez de tentar otimizar esse único problema localmente. No entanto, aprendi brevemente sobre as árvores Stern-Brokaw e Calkin-Wilf, o que poderia me permitir usar totalmente todos os bits disponíveis, mas o intervalo de valores obtidos com a ajuda deles é muito pequeno, então abandonei rapidamente essa ideia e segui em frente. Acho que neste momento devo expressar minha gratidão à Wikipedia como uma fonte constante de meu conhecimento.Voltemos à análise do que obtivemos: posso renderizar imagens com distorções, mas muito dependemos da distribuição dos números primos nos cálculos. Depende desses números primos se o algoritmo GCD pode simplificar a expressão - assim que qualquer número primo ou um múltiplo dele cair em qualquer um dos números de renderizador (vetores, escalares, matrizes), ele polui todos os números que o seguem em outras manipulações aritméticas, e permanece neles para sempre. Portanto, gradualmente tudo é garantido para começar a crescer, é apenas uma questão de tempo. Além do fato de que isso é inevitável, também é necessário, porque são divisores mutuamente simples que carregam informações sobre o valor de um número. Mas, ao mesmo tempo, números primos grandes quebram tudo muito rapidamente. Portanto, há um conflito.A última coisa que vale a pena notar é que eu ainda usei o dobro de bits do número de ponto flutuante padrão, então não há vantagens reais até agora. Obviamente, tentei usar números racionais de 16/16 bits, o que seria uma comparação mais honesta com os verdadeiros requisitos da aritmética de ponto flutuante, mas com uma precisão de 16/16, o sistema que escrevi com o numerador + denominador + GCD criou imagens completamente ilegíveis.Teste 3 - Normalização de Números Racionais
, . , .
, , , , , ( , — , . , , , ).
Seja como for, decidi verificar o que aconteceria com os processamentos se de alguma forma protegesse o numerador e o denominador de transbordar. A maneira mais fácil seria deslocar o numerador e o denominador, se necessário, por um número suficiente de bits para a direita, até que apareçam novamente no espaço de bits alocado. De fato, isso significa uma divisão inteira do numerador e do denominador por um valor, o que significa que o valor do número permanece aproximadamente inalterado. E aqui eu me desviei do objetivo original do experimento.Na minha primeira implementação, observei o número de bits necessários para o numerador e o denominador, peguei o máximo para ambos e mudei ambos por esse número de bits (arredondando para o número inteiro mais próximo). Quando isso foi implementado nos operadores de adição e multiplicação, tudo começou a parecer bastante aceitável:Números racionais de 65 bits reduzidos por GCD e normalizaçãoPadrão de ponto flutuanteComo tudo parecia muito bom, nessa fase, resolvi o problema de uma grande quantidade de bits usados na implementação atual. Tentei usar 16/16 (33 bits) em vez de 32/32 (65 bits), e as imagens foram surpreendentemente boas! Eu ainda vi que em algumas bordas da esfera existem pequenos buracos, e na figura da textura do triângulo existem pequenas lacunas. Mas isso não é ruim para quantidades próximas o suficiente de números de ponto flutuante. Isso me deu energia para aprender novas idéias.Teste 4 - Barra flutuante
Nesse estágio, decidi me distrair e parar de procurar desculpas - se eu quiser encontrar algo interessante para renderizar em números racionais, eles devem ocupar 32 bits e não mais. É melhor encontrar uma boa idéia ou parar e terminar aí (isso foi no início da segunda noite de experimentos).No começo, pensei que valia a pena aderir às idéias de GCD e normalização, mas era mais sensato abordar o armazenamento e o uso de bits. A primeira coisa que me ocorreu foi que, embora o numerador e o denominador possam aumentar, isso geralmente não acontece. Ou, pelo menos, isso não acontece simultaneamente. Portanto, quando o numerador é pequeno, você pode deixar o denominador ser grande e vice-versa. Os bits não utilizados de um dos dois valores inteiros podem ser usados para representar valores maiores. Então percebi que, da mesma forma, um número de ponto flutuante é essencialmente um formato de ponto fixo, onde o ponto "fixo" é feito variável. Eu posso pegar meus números racionais e também tornar o layout de bits da fração de fração variável. Ou seja, não é difícil definir a fração como 16/16, mas permitir que a mesma variável de 32 bits às vezes seja 16/16,e às vezes 5/27 ou 13/19, conforme necessário.Valeu a pena conferir. De qualquer forma, algumas linhas de código de embalagem / descompactação em setters e getters internos podem ser escritas rapidamente. O esquema mais lógico para mim parecia 1 | 5 | 26, ou seja:1 bit: sinal de
5 bits: posição da linha de fração (B)
26 bits: dados combinados de numerador e denominador; o numerador é o bit 26-B superior, o denominador é o bit B inferior,
onde a barra de frações (B) determina o tamanho do denominador. Por exemplo, o número 7/3 será escrito como7/3 = 0 00010 0000000000000000000001111 11,
onde o sinal 0 significa um valor positivo, a linha da fração 2 indica o denominador (número 3), que requer 2 bits para representar, e o restante dos bits vai para o numerador.Os leitores que trabalharam com o padrão IEEE754 podem achar familiar essa observação: a representação binária do denominador sempre começa com "1", porque o número da linha de fração sempre o trunca para a representação mais curta. Ou seja, o primeiro bit do denominador é opcional. Nesse caso, o número "3" pode ser representado apenas pelo valor binário "1" e pelo valor da linha de fração "1":7/3 = 0 00001 00000000000000000000000000111 1
Esse truque não só me salvou um pouco precioso, mas também tem um excelente efeito colateral: quando o valor da barra de uma fração é zero, isso naturalmente significa ao mesmo tempo que o denominador é 1 e que não é necessário espaço para armazená-lo. Isso significa que, de repente, minha representação racional de números se tornou completamente compatível com a representação inteira e aritmética usuais, até que os valores dos números subissem acima de 2 26, ou seja, para um limite suficientemente grande. Que surpresa maravilhosa! Ou seja, teoricamente, eu posso usar exatamente o mesmo tipo de dados, "racional", para executar operações de renderização e sombreamento padrão, mas também executar toda a lógica e tarefas do fluxo de comando no rastreador de caminho - não preciso mais usar dois tipos de dados, como acontece na maioria dos renderizadores ("int" e "float") e faça conversões em uma direção e outra! No entanto, o tempo estava se esgotando para mim, então não alterei todos os índices de loop de "int" para "racional". A noite estava chegando ao fim e eu ainda tinha que verificar muitas coisas para melhorar a qualidade das renderizações.Depois de criar a implementação, pude verificar:Números racionais fracionários de 32 bits (1 | 5 | 26)Referência de ponto flutuante de 32 bits Ohhhh, nada mal! Ainda tenho artefatos na esfera, que por enquanto vou culpar por minha má implementação da raiz quadrada, mas a caixa e o triângulo ficaram realmente limpos. O número de pixels de imagem resolvidos com precisão também aumentou. Penso que, devido ao fato de que antes do estouro no denominador ou numerador, mais números têm tempo para aparecer, aumentei a probabilidade de o GCD encontrar divisores comuns e realizar uma redução. Ou seja, a linha flutuante da fração não apenas aumentou o intervalo dos números representados e adiou o momento de normalização (com perda de precisão) causada pelo estouro, mas também deu o próximo passo na melhoria da qualidade, aumentando a probabilidade de reduções.Nesta fase, eu estava pronto para realizar um teste mais sério (mas ainda experimental - o sistema ainda está longe de estar pronto para operação). Eu implementei um rastreador de caminho com um conjunto mínimo de funções (não necessariamente fisicamente precisas ou mesmo levando em conta a física) e criei uma cena com vários paralelepípedos retangulares e duas fontes de luz, cuja implementação de referência na GPU está aqui: https://www.shadertoy.com/view/Xd2fzR .Novamente converti a cena para a estrutura C ++, novamente removi algumas normalizações de raios desnecessárias e executei a renderização. Aqui está o que eu tenho:Números racionais fracionários de 32 bitsPadrão de ponto flutuante de 32 bitsUau, isso é realmente bom! Embora vazamentos de luz sejam claramente visíveis nos cantos onde as bordas do piso e do teto estão conectadas. Veja-os na aproximação:
Talvez eles sejam causados por um problema na minha implementação da interseção de um raio e uma caixa retangular, que só é expressa em números racionais; Eu não ficaria surpreso. Ou talvez eu tenha me deparado com os limites dos quais números racionais são capazes. Seja como for, estou bastante satisfeito. Além disso, tenho outras alterações e experimentos que queria testar pelo curto período de tempo restante:Algumas outras experiências
Aritmética precisa em 64 bits
A idéia de aritmética exata não pode ser realizada em números racionais ingênuos de 64 bits ou em números racionais de 32 bits (1 | 5 | 26) com uma fração de linha flutuante. E os números de ponto flutuante de 64 bits de uma fração funcionam?Implementei rapidamente os números racionais 1 | 6 | 57 (embora eu tivesse que aprender novos mecanismos internos x64 para troca de bits). Esses 57 bits de numerador / denominador permitiram traçar um intervalo de distância muito maior. Na verdade, eu consegui traçar uma cena com vários triângulos com toda a precisãoaritmética (não a cena acima mencionada com paralelepípedos retangulares e iluminação global, mas apenas alguns triângulos na frente da câmera). E o sucesso me esperava! No entanto, o teste de coplanaridade, que eu implementei para verificar a exatidão, exigiu várias operações de produtos escalares e vetoriais, o que fez com que os números começassem a se normalizar. Portanto, embora eu soubesse que a renderização era precisa, não poderia "prová-la" experimentalmente. Que ironia. Em geral, isso significa que 64 bits foram suficientes para vários triângulos, mas cenas mais complexas ainda serão desfeitas. No entanto, isso me fez pensar em outra pergunta: existe algum algoritmo que pode ser usado para testar a coplanaridade, baseado não em valores absolutos, mas na aritmética modular? Eu achona aritmética modular, os números racionais não devem "explodir" em tamanho? Não tive tempo de investigar tudo isso e não sou especialista em teoria dos números.Raízes quadradas
Na última (segunda) noite de pesquisa, decidi abordar brevemente esse tópico e estudar novas informações. Eu queria implementar a melhor função de raiz quadrada possível para números racionais. Minha decisão ingênua atual ( incorreta ) pegou a raiz quadrada inteira do numerador (com arredondamento correspondente) e depois fez o mesmo com o denominador. Como a raiz quadrada de uma fração é uma fração das raízes quadradas do numerador e denominador, em geral, essa abordagem retorna resultados decentes, não muito diferentes da melhor resposta. Mas ele certamente não retorna a melhor aproximação racional da raiz quadrada de um número racional. Ele realiza duas em vez de uma aproximação.Eu tentei o seguinte: no final, aqui estamos procurando por dois inteiros x y , ,
() («» , ):
Depois de pesquisar na Wikipedia, descobri que essa equação específica é a chamada "equação de Pell modificada". Existem algoritmos que encontram os menores valores de
x e
y para resolver esta equação. Infelizmente, minha atenção mudou rapidamente para outras curiosas matemáticas diofantinas, e eu não continuei com a implementação de nenhum desses algoritmos.
Redução mais efetiva
Nos últimos minutos da noite, pensei em explorar a idéia de usar vários membros que se combinam em operadores geométricos complexos, por exemplo, em um produto vetorial. Digamos que o primeiro componente de um produto vetorial foi
sob a suposição de que sy = a / b, tz = c / d, ty = e / f, sz = g / h
Isso significava que agora eu posso tentar encontrar divisores comuns, por exemplo, entre a e d ou e e h, e usá-los para redução preliminar.
Tive outra ideia: se, em algum momento, a velocidade de renderização se tornar um problema, você poderá desativar completamente as etapas de pesquisa do GCD e aplicar apenas a normalização. Uma verificação rápida mostrou que, nesse caso, a imagem renderizada ainda permanece aceitável e funciona bem a uma velocidade muito maior. No entanto, nesse caso, é claro, obtemos menos resultados aritmeticamente precisos.
Como compromisso, você pode se recusar a implementar o procedimento ou o esquema GCD e usar algo matematicamente simples, codificado no código e eficaz, determinando a divisibilidade em apenas 2, 3 e 5. Embora não encontremos um número exaustivo de divisores, na prática, isso levaria a encontrar um grande número de abreviações. Pense nisso - divisibilidade por 2 ocorre três vezes mais que divisibilidade por 7 e 20 vezes mais que divisibilidade por 41!
Conclusão
Após esse experimento, comecei a acreditar que é bem possível que uma representação de números seja baseada em números racionais, semelhante ao que eu chamo de "fração de linha flutuante". Uma representação compatível com números inteiros e capaz de executar muitas operações na aritmética exata para muitas tarefas (desde que os dados de entrada sejam apresentados de forma racional). A versão de 64 bits (1 | 6 | 57) tem um grande potencial, embora a versão de 32 bits (1 | 5 | 26) já crie renderizações interessantes.
Se não fosse um experimento por duas noites, mas algo profissional criado em um estúdio ou empresa, no futuro, as seguintes etapas poderão ser tomadas:
* Obtenha um histograma do número de pixels precisos e não exatamente rastreados (em outras palavras, a frequência de execução da normalização)
* Tente implementar uma redução codificada nos divisores 2, 3 e 5 e meça a porcentagem de pixels exatos perdidos
* Mostre a diferença de pixel entre a renderização do ponto flutuante e a renderização do ponto flutuante da fração
* Encontre maneiras engenhosas de usar os valores não utilizados do formato de bit "frações de linha flutuante", por exemplo, para indicar Inf e NaN
* Implementar a detecção de NaN, Inf, underflow, overflow.
Em suma, foi um estudo fascinante. No processo, descobri algumas surpresas, criei uma pequena invenção e aprendi muito sobre a equação de Pell, raízes quadradas, GCD, mecanismos internos x86_64, a função zie de Riemann e outros aspectos. Estou muito satisfeito com isso!