Introduccion
"¿Qué sucede si reemplazamos los números de coma flotante con números racionales y tratamos de representar la imagen?"
Me hice esta pregunta después de pensar en el tweet de un investigador y profesor de gráficos por computadora Morgan McGwire. Habló sobre cuánto se sorprenden los estudiantes de ciencias de la computación cuando descubren que para almacenar los números familiares de coma flotante en las computadoras modernas, deben hacerse compromisos. Y estos compromisos dificultan las tareas simples, por ejemplo, verificar si un punto pertenece a un triángulo. El problema, por supuesto, es que verificar que cuatro puntos estén en el mismo plano (coplanaridad) usando el determinante o algún tipo de multiplicación vectorial (pero de hecho esto es lo mismo) nunca dará un valor exactamente igual a cero, lo cual es necesario Estos son métodos matemáticos. Incluso si los cálculos reales de estar en el mismo plano fueran precisos, los mismos compromisos con una precisión de casi 1.0 darían la respuesta de que los cuatro puntos en sí mismos no son coplanares.
Esto dio origen a la idea en mí: si asumimos que todos los datos entrantes del renderizador (coordenadas de vértice, transformaciones 3D, etc.) se configuraron como números racionales, entonces crearían todas las operaciones, desde crear un rayo, atravesando la estructura de aceleración hasta la intersección ¿los rayos con triángulos son solo números racionales? Si ese fuera el caso, ¡podríamos llevar a cabo una prueba de coplanaridad exactamente! Quizás se pregunte por qué una escena 3D expresada en números racionales solo debería dar resultados en números racionales ...
Una escena simple, el trazado de ruta en el que se realiza mediante aritmética racional. Utiliza un sistema de números de punto flotante, no un número de punto flotante.En primer lugar, un número racional es un número que se puede expresar como la razón de dos enteros, por ejemplo 1/2 o 355/113. En segundo lugar, las "operaciones de renderizado normales", como las pruebas de cuadro delimitador, la verificación de la intersección de un rayo con un triángulo, la reflexión de un rayo, etc., se basan en productos vectoriales y escalares, así como en la división escalar (esto incluye transformación de coordenadas e inversión de matrices, cuaterniones, etc.), que a su vez se basan en cuatro operaciones básicas: suma, resta, multiplicación y división. Al sumar, restar, multiplicar y dividir números racionales, también se obtienen números racionales. El matemático diría que muchos números racionales forman un campo que está cerrado bajo cuatro operaciones aritméticas básicas. Para nosotros, esto significa que si nos adherimos a números exclusivamente racionales, podemos pasar de los datos de entrada de la escena 3D a una imagen completamente renderizada sin abandonar el mundo de los números racionales.
Las excepciones a la regla "las acciones sobre números racionales dan números racionales" son las raíces cuadradas y las funciones trigonométricas / trascendentales. En cuanto a lo último, siempre digo que si tuvo que realizar cálculos trigonométricos en los interiores geométricos de su renderizador, lo más probable es que esté haciendo algo mal (y le mostré
cómo solucionar los casos más estándar ) [
traducción en Habré]. En cuanto a las raíces cuadradas, con la excepción de las secciones cónicas (esferas, cilindros, etc.) y la realización de sombreado / DFOS / coloración, no es necesario normalizar los rayos y normalizar las superficies con la frecuencia habitual. Ciertamente no es necesario hacerlo para crear un rayo, su paso, intersección, reflejos, etc. Desafortunadamente, a menudo veo que los programadores normalizan los valores sin otra razón que "bueno, no lo sé, lo hago para poder jugar de manera segura". En la práctica, en la parte de la representación en la que se traza la geometría, rara vez es necesario normalizar los valores, así que tenía la esperanza de que pudieras rastrear toda la escena sin abandonar el mundo de los números racionales; esto es lo que llamaría "representación racional".
Para poner esto en práctica, necesito crear un sistema de números basado en números racionales que una computadora pueda usar. Luego, además, podría implementar los algoritmos habituales de trazado de ruta, calcular imágenes sin pérdida de precisión, realizar comprobaciones de coplanaridad que tengan respuestas precisas y hacer felices a todos los estudiantes que estudian gráficos por computadora.
Este artículo es una historia sobre dos noches de investigación sobre el realismo de tal idea. Hablaré sobre los muchos aspectos que aprendí, sobre lo que se me ocurrió y sobre algunas sorpresas que descubrí en el proceso. El artículo está escrito en un orden más o menos cronológico de mi trabajo. Además, fue escrito en mi estilo inusualmente informal y muy poco científico (del cual estoy orgulloso). La imagen que se muestra arriba es una especie de spoiler, pero lea el artículo hasta el final, porque hablaré sobre lo bueno y lo malo.
Preparación
Lo primero que hice fue implementar en
Shadertoy un trazador
mínimamente limitado para una escena
extremadamente simple que consta de un plano, una esfera, un paralelepípedo rectangular y un triángulo, los bloques de construcción de los renderizadores reales. Luego copié el código en un archivo C ++ y, después de hacer un par de cambios menores, lo compilé usando mi marco
piLibs . Entonces, para comparar, obtuve una imagen trazada en la CPU usando números regulares de acuerdo con el estándar IEEE754 con un punto flotante. También eliminé toda la normalización de rayos del código de seguimiento, porque, como se mencionó anteriormente, ninguno de ellos es realmente necesario. Permítame recordarle que se requiere una raíz cuadrada para la normalización, y los números racionales no se conservan cuando se usa (la raíz cuadrada de un número racional no es un número racional). Un poco más tarde veremos que todavía es posible aplicar raíces cuadradas, por supuesto, solo quería que el código fuera lo más matemáticamente posible para ver hasta dónde puedo llegar con la aritmética exacta de números racionales sin redondear.
El último paso preparatorio: tomé todas las clases vec3, mat4x4 y otras clases básicas de álgebra / matemáticas, y luego las cambié para que usaran racional en lugar de flotante. Dado que mi estructura racional sobrecarga todos los operadores estándar (suma, sub, mul, div, inversión de signos, comparaciones, etc.), el reemplazo se produjo sin problemas. Rápidamente implementé las operaciones habituales restantes (abs, signo, mod, fract, piso, sqrt, etc.), lo que teóricamente fue suficiente para obtener hermosas representaciones racionales.
Prueba 1 - La solución ingenua
Pero veamos cómo fue esta primera implementación. Al principio siempre intento lo más simple, y luego miro los resultados. Y la forma más sencilla de implementar valores racionales era usar dos enteros. Como sugiere el nombre de la sección, esta no será mi decisión final, pero para el primer intento fue una decisión razonable. Entonces, cada número
x debe representarse como el numerador
N y el denominador
D , formando el valor
N /
D. El valor
x se aproxima por el mejor par
N /
D posible (dentro de la profundidad de bits especificada), que está más cerca del valor
x verdadero. Decidí que ambos números deben ser positivos, y el signo del número debe almacenarse en un bit separado para simplificar el trabajo y deshacerse de las ambigüedades, aunque esto no es muy importante. En esta etapa, tanto los numeradores como los denominadores eran de tipo sin signo. Pero incluso al separar el signo,
N /
D tenía mucha redundancia: por ejemplo, 1/4 y 7/28 denotan el mismo número, pero tienen representaciones de bits completamente diferentes. Hablaremos de esto más adelante, pero por ahora, no centremos nuestra atención y veamos cómo se ven las cuatro operaciones aritméticas básicas en esta forma racional.
Primero, tenga en cuenta que restar
a -
b es simplemente la suma de
ay el valor opuesto a
b , es decir,
a + (
-b ), donde
-b se puede calcular simplemente cambiando el signo de
b . Del mismo modo, dividir
a /
b es lo mismo que multiplicar
ay el inverso de
b . O, en otras palabras,
a /
b =
a · (1 /
b ), donde (1 /
b ) se puede calcular simplemente cambiando los lugares del numerador
b n y el denominador
b d del número
b . Entonces, aquí está la primera propiedad interesante de la aritmética racional: la división y la multiplicación tienen los mismos costos, por lo tanto, a diferencia de la representación de coma flotante habitual, en la que las divisiones generalmente se evitan, retrasan u ocultan bajo los retrasos de las solicitudes de textura lenta, no hay necesidad de temer estas operaciones en aritmética racional .
Pasamos a la suma con la multiplicación: sabemos que los valores opuestos e inversos son trivialmente simples de calcular, por lo que obtenemos:
La preservación de los signos durante la multiplicación es trivial, es solo xor, porque dos valores positivos dan un resultado positivo, así como dos negativos. Guardar un signo para sumar es un proceso más complicado, y para una solución rápida lo implementé a través de tres ramas (la suma es trivial si los signos
a y
b coinciden, pero cuando no coinciden, entonces debe seleccionar un número más pequeño y restarlo del más grande; en el artículo no Describiré detalles tan pequeños con más detalle, pero solo tendré el código fuente en alguna parte).
También omitiré la implementación de fract () y floor (); Si decide intentar implementarlos usted mismo, verá su simplicidad y belleza. También se debe prestar atención a los operadores de comparación. Después de ocuparse de los signos y asumir que
ayb son positivos, obtenemos
Es importante señalar aquí que, incluso para la comparación, necesitamos un par de operaciones de multiplicación, que pueden conducir a la transición al siguiente tamaño de palabra y serán importantes un poco más bajas.
Finalmente, observamos las raíces cuadradas en una sección separada, sabiendo que en su mayor parte no las necesitamos (excepto la esfera de esta primera prueba).
Esto fue suficiente para ejecutar el primer render y rastrear la escena de prueba (plano + esfera + triángulo + caja rectangular) para ver qué sucedía. Generosamente utilicé números racionales de 65 bits para esta primera prueba, que en realidad representa una gran cantidad de datos (comparable al tipo de datos "doble"): 32 bits son tomados por el numerador, 32 bits son el denominador y otro bit es el signo. La primera es la imagen obtenida con este enfoque ingenuo, la segunda es la imagen hecha con números de punto flotante (referencia):
Números racionales "ingenuos" de 65 bitsReferencia de punto flotanteEl resultado fue bastante malo, la caja y el triángulo ni siquiera aparecían en el render, y la esfera y el plano del piso eran demasiado ruidosos. El problema, por supuesto, era que cada vez que mis números racionales realizaban cualquier operación aritmética básica en cualquiera de las etapas algorítmicas de representación, el numerador y el denominador se volvían cada vez más incontrolables, porque se usaba la multiplicación entera. Piense en lo siguiente: si las unidades de nuestro mundo inicial fueran metros, y vinculamos la geometría fuente (vértices y cámara) a una precisión milimétrica, entonces solo los datos fuente ocuparían un volumen de 16 bits para una escena bastante pequeña. Al mismo tiempo, con una resolución de pantalla HD estándar y un suavizado 4X, los números de dirección de haz racionales requerirían fácilmente 12 bits. Es decir, durante la primera interacción del haz y la geometría, la operación aritmética más simple que usa ambos conjuntos de datos de entrada convertiría el resultado en longitudes de 28 bits, lo suficientemente cerca del límite de 32 bits que establecí para mí en esta primera implementación. Y esto es incluso antes de que realicemos el primer producto vectorial o escalar. Para cuando el producto escalar esté completo, el renderizador necesitaría números racionales de cientos de bits de longitud para representar los números. Por supuesto, este es el peor de los casos, pero el caso promedio estaría cerca de esto. Teniendo en cuenta que asigné solo una capacidad de 32 bits para el numerador y el denominador, es fácil entender qué tan rápido los valores van más allá de los límites en esta prueba; no es sorprendente que, con la excepción del plano del piso y parte de la esfera, casi nada sea visible.
Prueba 2 - Reducción por el factor común más grande
Luego mejoré el sistema usando la propiedad que mencioné brevemente anteriormente: diferentes números racionales pueden significar la misma cantidad. Y, de hecho, 6/12 es el mismo valor que 1/2, pero utiliza muchos más bits que el anterior. Por lo tanto, la idea era la siguiente: si después de cada operación aritmética básica (o después de ella) extraería todos los divisores comunes del numerador y los denominadores, y llevaría la fracción a su forma más simple, entonces quizás pueda mantener todo bajo control y continuar las operaciones por más tiempo con aritmética exacta sin pérdida de precisión. ¿Quizás pueda hacer esto el tiempo suficiente para obtener imágenes limpias y renderizadas? Haré una pequeña digresión para mostrar otro ejemplo: 588/910 se puede simplificar a 42/65, porque 14 es un divisor de 588 y 910. Pero para almacenar 42/65, obviamente, se necesitan menos bits que 588/910. Encontrar el número más grande posible que divide simultáneamente los otros dos números se puede hacer usando el algoritmo del Gran Divisor Común (GCD), implementaciones efectivas que puedes encontrar en cualquier lugar (lo copié personalmente directamente de Wikipedia y lo aceleré un poco realizando el paso de escaneo bits utilizando operaciones internas x64). Entonces, armado con el algoritmo GCD, mi clase racional debería simplificar constantemente las fracciones generadas durante el proceso de renderizado. Esto podría hacerse de dos maneras:
El primero es convertir el resultado intermedio de los operadores de suma y multiplicación al siguiente tipo de datos de bits (en mi solución ingenua actual es uin64_t), buscar GCD en este tipo de datos más voluminoso y luego reducir el resultado a la longitud de bits original (32). La segunda forma es analizar cómo
a n ,
a d ,
b n y
b d se combinan entre sí en ambos operadores aritméticos y extraer divisores comunes de ellos antes de realizar la multiplicación. El segundo enfoque básicamente eliminó la necesidad de grandes longitudes de bits. Sabiendo que podría ser necesario usarlos de todos modos, decidí elegir el primer método, porque era más fácil de implementar y me permitía acelerar mi trabajo (la noche vuela muy rápido). Una vez hecho todo esto, veamos qué render puedo crear ahora:
Números racionales de 65 bits reducidos por GCDReferencia de punto flotanteMucho mejor! Hasta ahora, lejos de ser ideal, por supuesto, pero parece prometedor. Hice aparecer la caja y el triángulo, y la esfera ahora parece mucho más voluminosa. Sin embargo, apareció un artefacto divertido en la esquina superior derecha, y los números racionales para muchos píxeles aún van más allá de los límites, lo que conduce a muchos puntos en la imagen. Sin embargo, vale la pena señalar que para algunos (muchos) píxeles, ¡comencé a obtener resultados
precisos y perfectos! Es decir, el trazador encontró intersecciones matemáticamente precisas de puntos y distancias, que fue la causa principal de tratar de usar números racionales.
Antes de proceder al siguiente paso en el proceso de probar la aplicabilidad de los números racionales, quiero detenerme brevemente y compartir mis hallazgos con respecto a MCD y la reducción de números racionales.
El primer descubrimiento está relacionado con el volumen de bits de los números racionales. Aunque todavía no puedo reproducir imágenes hermosas y esto es más importante que preocuparme por optimizar los volúmenes de datos, y aunque esta implementación inicial todavía usaba una gran cantidad de bits (1 + 32 + 32), ya estaba pensando en el desperdicio mencionado anteriormente bits en forma de fracciones en exceso. En particular, después de agregar una etapa con un GCD, las combinaciones de bits como 2/4 ya no son aplicables, ya que se reducen automáticamente a 1/2 antes de escribir en cualquier registro o variable. Es decir, en cierto sentido, de las 2
64 combinaciones de bits que podrían ser un numerador y un denominador, muchas permanecieron sin usar. Y no puedes desperdiciar trozos así. ¿O es posible? ¿Cuánto espacio pierdo realmente? Hice una pequeña digresión para explorar este problema.
Digresión - En números primos mutuos
Las siguientes ilustraciones muestran el uso de bits para números racionales en 5/5 bits y 7/7 bits. Los ejes horizontal y vertical de los gráficos representan los valores del numerador y denominador de todos los números racionales posibles que tienen numeradores y denominadores de hasta 5 bits (31) y 7 bits (127). Los píxeles negros son combinaciones no utilizadas, y los píxeles blancos son fracciones utilizadas. Por ejemplo, toda la diagonal es negra, excepto el píxel 1/1, porque todas las fracciones de la forma n / n se reducen a 1/1.
Usando bits para 5/5 racional
Usando bits para 7/7 racionalSi cuenta los píxeles, como lo hice, entonces puede comprender rápidamente que la proporción de píxeles útiles con un aumento en el número de bits tiende a 60.8%. Una pequeña investigación en línea me mostró que esta relación resulta ser exactamente 6 / π
2 , porque también es la probabilidad de ser relativamente primo (no tener divisores comunes) para dos números aleatorios. Usted puede preguntar, ¿de dónde vino el pi? , « „“ » — , ,
- , 2, 1/ζ(2). , - .
, , 40% . , , … . , , , , , . - - -, , , . ,
.
, : , . , — (, , ), «» , , . , . , , , . . .
, — - , , . , 16/16- , , 16/16 ++ .
3 —
, . , .
, , , , , ( , — , . , , , ).
, , , - . , , . , , , ,
. .
, , , ( ). , :
65-, . 32/32 (65 ) 16/16 (33 ), ! , , . , . .
4 —
— - , 32 . , ( ).
, , . , — , . , , . , , . . , , «» . . 16/16, 32- 16/16, 5/27 13/19, .
. / . 1|5|26, :
1 :
5 : (B)
26 : ; — 26-B , — B ,
(B) . , 7/3
7/3 = 0 00010 000000000000000000000111 11,
0 , 2 ( 3), 2 , .
, IEEE754, : «1», . . «3» «1» «1»:
7/3 = 0 00001 0000000000000000000000111 1
, : , , 1 . , , 2
26 , . ! , «rational», , — , («int» «float») ! , «int» «rational». , .
, :
32- (1|5|26)32- --, ! - , , - . . , , , , . ( ), , .
( — ). ( ) , GPU :
https://www.shadertoy.com/view/Xd2fzR .
C++, . :
32- 32- , ! , . :
, , ; . , , . , . , , :
64
64- , 32- (1|5|26) . 64- ?
1|6|57 ( x64 ). 57 / .
( , ). ! , , , . , , «» . . , , 64 , . : - , , , ? , «» ? , .
() . . (
) ( ), . — , , . . .
: ,
x y , ,
() («» , ):
Después de buscar en Wikipedia, descubrí que esta ecuación en particular es la llamada "ecuación de Pell modificada". Hay algoritmos que encuentran los valores más pequeños de
x e
y para resolver esta ecuación. Desafortunadamente, mi atención cambió rápidamente a otras matemáticas diofantinas curiosas, y no procedí con la implementación de ninguno de estos algoritmos.
Reducción más efectiva
En los últimos minutos de la noche, pensé en explorar la idea de usar múltiples miembros que se combinen en operadores geométricos complejos, por ejemplo, en un producto vectorial. Digamos que el primer componente de un producto vectorial fue
bajo el supuesto de que sy = a / b, tz = c / d, ty = e / f, sz = g / h
Esto significa que ahora puedo intentar encontrar divisores comunes, por ejemplo, entre a y d, o e y h, y usarlos para la reducción preliminar.
Tenía otra idea: si en algún momento la velocidad de renderizado se convierte en un problema, puede deshabilitar por completo los pasos de búsqueda de GCD y aplicar solo la normalización. Una comprobación rápida mostró que, en este caso, los renderizados de imágenes siguen siendo aceptables y funcionan bien a una velocidad mucho mayor. Sin embargo, en este caso, por supuesto, obtenemos menos resultados aritméticamente precisos.
Como compromiso, puede negarse a implementar un procedimiento o un esquema GCD, y en su lugar usar algo matemáticamente simple, codificado en el código y efectivo, determinando la divisibilidad solo por 2, 3 y 5. Aunque de esta manera no encontraremos un número exhaustivo de divisores, por en la práctica, esto llevaría a encontrar una gran cantidad de abreviaturas. Piénselo: ¡la divisibilidad entre 2 ocurre tres veces más que la divisibilidad entre 7 y 20 veces más que la divisibilidad entre 41!
Conclusión
Después de este experimento, comencé a creer que es bastante posible que una representación de números se base en números racionales, similar a lo que yo llamo la "fracción de línea flotante". Una representación compatible con enteros y capaz de realizar muchas operaciones en aritmética exacta para muchas tareas (siempre que los datos de entrada se presenten de forma racional). La versión de 64 bits (1 | 6 | 57) tiene un gran potencial, aunque la versión de 32 bits (1 | 5 | 26) ya crea representaciones interesantes.
Si no fue un experimento durante dos noches, sino algo profesional creado en un estudio o empresa, en el futuro se podrían tomar los siguientes pasos:
* Obtenga un histograma de la cantidad de píxeles con precisión y no exactamente trazados (en otras palabras, la frecuencia de ejecución de normalización)
* Intente implementar una reducción codificada en los divisores 2, 3 y 5 y mida el porcentaje de píxeles exactos perdidos
* Muestra la diferencia de píxeles entre el renderizado en coma flotante y el renderizado en fracción flotante
* Encuentre formas ingeniosas de utilizar los valores no utilizados del formato de bits "fracciones de línea flotante", por ejemplo, para indicar Inf y NaN
* Implementar la detección de NaN, Inf, underflow, overflow.
En general, fue un estudio fascinante. En el proceso, descubrí algunas sorpresas, se me ocurrió una pequeña invención y aprendí mucho sobre la ecuación de Pell, raíces cuadradas, MCD, mecanismos internos x86_64, la función zeta de Riemann y algunos otros aspectos. Estoy muy contento con esto!