Como ya puedes entender de mis artículos anteriores, me gusta usar el desarrollo de juegos como una excusa para demostrar matemáticas complejas para las cuales, de lo contrario, la mayoría de las personas no tendrían ningún uso. ¡Y este artículo no es una excepción! Quiero mostrar una técnica muy interesante, correspondiente a puntos que me interesan:
- el proceso es lo suficientemente claro
- es mucho más rápido que la técnica habitual que realiza la misma tarea
- utiliza una propiedad muy inusual de representar números de punto flotante en formato de punto flotante, lo que implica que ...
- No funciona en el análisis clásico . Para que este algoritmo funcione en teoría, ¡debes ingresar al maravilloso mundo de las matemáticas no clásicas! Y si esto no despertó su curiosidad, entonces no sé qué más hacer.
Este artículo es bastante largo y teórico, porque requiere un estudio profundo de las explicaciones, así que tómate tu tiempo y vuelve a leer las partes que creías que no eran tan obvias la primera vez.
Un poco sobre el contexto (GPU)
Uno de los aspectos importantes a los que debe prestar atención en el desarrollo de juegos, y en un sentido más amplio, en cualquier área con el uso activo de gráficos, es el ancho de banda de la GPU. El procesador central y la GPU son dispositivos físicos separados, y necesitan sincronización para intercambiar datos. Si ya ha realizado el procesamiento en paralelo, entonces sabe que cuando dos dispositivos necesitan sincronizarse, esto significa perder una cantidad significativa de tiempo. La interacción de la CPU-GPU a este respecto no es diferente, por lo que nos esforzamos por minimizar la transferencia de datos, tanto en el número de operaciones como en la cantidad de datos transferidos.
La minimización de la cantidad de operaciones de transferencia de datos generalmente se realiza mediante almacenamiento en búfer: nos esforzamos por ajustar todos los datos en el menor número posible de matrices, y luego transferimos todo de una vez para que ya no tengamos que preocuparnos por ellos. Minimizar la cantidad de datos en las operaciones de transferencia es un tema completamente diferente, y las soluciones a este problema son casi siempre individuales. Como un ejemplo extremo de esto, puede ver
cómo el motor de renderizado de Destiny se adapta a la posición, las normales de superficie, las banderas de material y los parámetros BSDF anisotrópicos completos de 96 bits, es decir. tres números de coma flotante (p. 62 en adelante). Sin embargo, se pueden lograr buenos resultados mediante métodos generales, a los que luego se agregan soluciones individuales para la optimización.
Hoy discutiremos la
compresión sin pérdida de vectores individuales en 3D . Esta oración contiene varias palabras clave:
- Vectores 3D únicos : vectores 3D que tienen una longitud de 1
- Compresión sin pérdidas : reduzca el tamaño de las descripciones de vectores 3D únicos sin pérdida de precisión. Esto es lo opuesto a la compresión con pérdida.
- Separado : la codificación y decodificación de vectores se realiza sin información sobre sus vecinos. Si la situación fuera lo contrario, entonces podría ser algo así como la compresión por lotes , en la que no se comprimen vectores individuales, sino sus matrices
Antes de continuar, debo mencionar el excelente artículo
"Una encuesta de representaciones eficientes para vectores de unidades independientes " de Cigolle, Donow, Evangelakos, Mara, McGuire y Meyer, del cual me inspiré para mi publicación. Debo decir de
inmediato que el
algoritmo del que hablaré es menos eficiente que el algoritmo oct presentado en el artículo . Si desea la máxima eficiencia, lea el artículo y use
oct . El propósito de mi publicación es mostrar la belleza del uso de matemáticas muy inusuales, al tiempo que crea, como veremos más adelante, un algoritmo muy conveniente.
Topología directamente en tu videojuego
En el caso de la esfera de la unidad, solo θ y φ son importantes, porque ρ es siempre 1 y, por lo tanto, redundante.El punto de partida del algoritmo es la observación de que los vectores unitarios 3D son equivalentes a los puntos en una esfera. Como probablemente sepa, una esfera es una superficie bidimensional, es decir, para la identificación única de puntos en una esfera, solo se requieren dos coordenadas. Un ejemplo muy común de esto son las coordenadas esféricas, en las cuales un punto en la esfera está definido por dos ángulos, θ y φ.
Curiosamente, una propiedad bastante desagradable es que aunque la esfera y el cuadrado relleno (un posible espacio para coordenadas 2D) son objetos 2D, realmente no hay correspondencia entre ellos. Esto significa que no hay forma de unir un punto único en la esfera a cada punto único del cuadrado (al menos de manera continua); se dice que
no son homeomórficos (en otras palabras, uno tiene un límite y el otro no). Un resultado desagradable de esto es que algunas coordenadas 2D se pierden en el sentido de que diferentes coordenadas corresponden a puntos idénticos en la esfera (por ejemplo, en el caso de coordenadas esféricas, cuando φ es 0, el punto correspondiente será el polo norte, independientemente de la coordenada θ). En términos de compresión, perdemos patrones de bits valiosos con los que podríamos describir los puntos de una esfera.
Si desea más matemática y quiere demostrar que el cuadrado y la esfera no son homeomórficos, puede usar el hecho de que la esfera, en contraste con el cuadrado, no es contraíble, y la contractibilidad es una propiedad topológica; El teorema de Borsuk-Ulam también se puede usar como prueba. También me dijeron que los grupos de homotopía pueden ayudar con la prueba, pero esto ya está fuera de mi área de especialización.
Sin embargo, este problema surge no solo con las coordenadas esféricas; cualquier representación continua en 2D de los puntos de la esfera sufrirá de ella. Sin embargo, recuerde esto para el futuro.
Las coordenadas esféricas también tienen otras malas propiedades:
- Tienen una distribución pobre sobre la esfera. Si se generan coordenadas esféricas aleatorias y se vuelven a convertir en puntos 3D, forman grupos alrededor de los polos y se enrarecerán bastante cerca del ecuador. Esto se debe al hecho de que los vectores 3D cerca del ecuador serán menos distinguibles con precisión.
Distribución en una esfera de 10.000 coordenadas esféricas uniformemente distribuidas. - Su embalaje y desembalaje son costosos. Para el empaque (3D → 2D), se requiere una operación acos y una atan2 , que son funciones trigonométricas inversas bastante costosas, y para desempaquetar (2D → 3D) se requieren dos operaciones cos y dos operaciones sin , que también están lejos de ser económicas.
Consulte el artículo anterior para conocer otras comparaciones de coordenadas esféricas y otros métodos de compresión.
La tarea de preservar patrones de bits ... y velocidad
El método que consideraremos tiene una gran ventaja: su cálculo es mucho más rápido, más del doble que el punto de referencia ingenuo no optimizado (probado en el empaquetado y desempaquetado de 10 millones de vectores aleatorios en C ++ en Visual Studio 19 en Intel Core i5 7th gen). Además, el método no tiene una singularidad, es decir, cada punto empaquetado corresponde a un único punto desempaquetado, en contraste con las coordenadas esféricas mencionadas anteriormente.
Como se mencionó anteriormente, no hay homeomorfismo entre la esfera de la unidad y el cuadrado de la unidad, es decir, no podemos unir adecuadamente cada punto único en el cuadrado a otro punto único en la esfera. Pero consideremos las siguientes construcciones: hasta ahora solo nos interesará el hemisferio norte, en el que hay puntos con una coordenada Z positiva o cero.
"Aplanamos" el hemisferio norte en el disco, descartando la coordenada Z de cada punto (o asignándole un valor de 0).Encontramos una manera de conectar cada punto en el hemisferio norte a cada punto en un solo disco. Algunos puntos notables:
- el polo norte cae en (0, 0).
- cada punto en el límite del hemisferio permanece igual. Más específicamente, el hemisferio y el disco tienen el mismo límite. Esto es lógico, porque los puntos en el límite del hemisferio tienen Z = 0, es decir, descartando la coordenada Z, no cambiamos nada.
Compresión de disco: una tarea simple y compleja
La siguiente construcción requiere una pequeña introducción. Por si acaso, diré que los números complejos son una extensión del espacio de los números reales (números ordinarios como 0, 1, 129,43, pi, 335/117, raíz cuadrada 2, etc.), que usa un número especial que llamé
imaginario unidad Los números complejos tienen la forma
a + ib , donde
a y
b son algunos números reales (respectivamente, las partes real e imaginaria), y
tengo la propiedad
i ² = -1. Esto nos permite unir números complejos con puntos en un plano 2D. Si tomamos para
z un número complejo de la forma
z = a + ib , entonces podemos representar
z como un punto con coordenadas (
a ,
b ) en el plano. Las funciones de extracción de la "parte real" y la "parte imaginaria" del número complejo
z se denotan por
Re (z) e
Im (z) .
El número complejo z y sus valores.Además de las partes reales e imaginarias del número complejo, también se puede tener en cuenta la longitud y el ángulo formado por él con el eje X. Esto se denomina
representación polar . La longitud polar y el ángulo polar son la norma
| z | y argumento
Arg (z) . Una propiedad conveniente de ambas representaciones es que la
adición de números complejos se realiza sumando las partes reales e imaginarias , y la
multiplicación de números complejos se realiza multiplicando las normas y sumando los argumentos .
Aquí nos interesan dos operaciones: cuadrar y obtener la raíz cuadrada de un número complejo. La cuadratura de un número complejo es exactamente la misma que para los números reales: simplemente lo multiplicamos por nosotros mismos, esencialmente
cuadrando la norma y duplicando el argumento . Tenga en cuenta que si la norma de un número complejo es menor que 1, cuando lo cuadre, su longitud será menor que uno; Por lo tanto, si tomamos cada número complejo en el disco que tiene una parte real positiva y los ponemos todos en un cuadrado, entonces esencialmente obtendremos el disco completo.
A la izquierda hay varios números complejos en la mitad del disco con la parte real positiva (coordenada X). A la derecha está el resultado de cuadrar todos estos puntos. ¡La mitad del disco ahora llena todo el disco!Un truco está asociado con "duplicar un argumento": depende del lado del eje X en el que se encuentra el punto. La regla se muestra a continuación.
Un número complejo con una parte imaginaria positiva (coordenada Y) gira hacia la izquierda, y un número complejo con una parte imaginaria negativa (coordenada Y) gira hacia la derecha.Como en el caso de los números reales, la raíz cuadrada es el inverso de la cuadratura: para un número complejo dado
z , las raíces cuadradas (dos de ellas) son los números
c , de modo que
c² = z . Como en el caso de los números reales, si
c es la raíz cuadrada de
z , entonces
-c también lo es. El de los números
c y
-c , cuyo argumento es igual a la mitad del argumento
z , se llama el valor principal de la raíz cuadrada (esto es similar a tomar la raíz cuadrada positiva de un número real en lugar de la raíz cuadrada negativa).
Si comprende que cuando un número complejo es al cuadrado, su norma es al cuadrado y su argumento se duplica, entonces puede adivinar fácilmente que el valor principal de la raíz cuadrada toma la raíz cuadrada de la norma y reduce a la mitad el argumento (siguiendo la regla que se muestra arriba, pero con las flechas al revés) . Como en el caso de la cuadratura, cuando se saca la raíz cuadrada de un número complejo con una norma menor que 1, la norma permanece menor que 1; por lo tanto, "comprime" el disco de la unidad en sus números reales medio positivos.
A la izquierda hay varios puntos en un solo disco. El lado derecho muestra el resultado de sacar la raíz cuadrada de todos estos puntos. ¡Todo el disco ahora cabe en la mitad de sí mismo!Esta es la base del algoritmo: de hecho, comprimimos todo el disco de la unidad en la mitad con la parte real positiva. Como recordarán, recientemente hemos aplanado la mitad superior de una esfera en un solo disco; Ahora vale la pena ver qué haremos con él.
Poniendo todo junto
Resumamos lo que acabamos de hacer: aplanamos la mitad de la esfera en una unidad de disco, descartando la coordenada Z de todos sus puntos, y exprimimos la unidad de disco en su propia mitad con la parte real positiva usando el complejo valor de la raíz cuadrada principal. De hecho, ¡aplanamos la mitad de la esfera en la mitad del disco! Ahora con algunos cambios, podemos hacer lo mismo para comprimir la mitad restante de la esfera en la mitad restante del disco.
La mitad inferior de la esfera (todos los puntos de la esfera con una coordenada Z negativa) también se aplanan en un disco unitario al soltar repetidamente las coordenadas Z. Sin embargo, para todos los números complejos
z en el disco, tomamos el valor opuesto a la raíz cuadrada principal de
z (es decir, tomamos
-c en lugar de
c ) Como el valor principal de la raíz cuadrada siempre tiene una parte real positiva, el valor opuesto siempre tendrá una parte real negativa; de hecho, aplanamos la mitad restante de la esfera en la mitad restante del disco, ¡y la etapa de compresión ahora está completa!
Paso de compresión completa. Tenga en cuenta que los hemisferios norte y sur (azul y naranja) se aplanan en dos copias de un solo disco y luego se comprimen en dos mitades de un solo disco.El algoritmo de compresión es el siguiente:
function packUnitVector(unit) disk = new Complex(unit.x, unit.y) packed = principalSquareRoot(disk) return unit.z < 0 ? -packed : packed
Y así, en solo tres líneas de pseudocódigo, aplicamos toda la teoría que examinamos para crear un algoritmo efectivo. Si su entorno no tiene una fórmula para el valor principal de la raíz cuadrada, puede encontrarla
en Wikipedia (se debe prestar especial atención a elegir el signo de la parte imaginaria). Aquí está la implementación de referencia de C ++ que uso en mi código:
Regresa
Afrontamos la compresión, ahora procedemos a descomprimir.
El desempaquetado consiste en el orden inverso de todos los pasos de compresión:
- expandimos las mitades positivas y negativas de las partes materiales de un solo disco en dos discos completos
- unir cada disco completo con su hemisferio correspondiente
En resumen, comenzamos con el valor empaquetado de
p , lo elevamos al cuadrado para volver al punto en el disco obtenido de uno de los hemisferios, y luego usamos el signo
Re (p) para averiguar de qué hemisferio se toma el punto en el disco. Usando la ecuación
x² + y² + z² = 1 , que define los puntos en la esfera de la unidad, podemos recrear la coordenada Z faltante del punto empaquetado.
Cabe señalar que calcular el cuadrado del valor empaquetado siempre nos dará el punto correcto del disco, independientemente de su hemisferio inicial (superior o inferior), porque
z² = (-z) ² .
El algoritmo de descompresión es el siguiente:
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
Y entonces obtuvimos un algoritmo que crea de manera muy eficiente una representación 2D de vectores 3D únicos, que, a diferencia de las coordenadas esféricas, no pierde ningún patrón de bits y no tiene singularidad. Si no tiene en cuenta un par de trucos de optimización para acelerar los cálculos, esta es una versión casi lista para usar del algoritmo.
... o no? Si observabas atentamente, te diste cuenta de que algo anda mal aquí. ¿Dije que la esfera y el cuadrado de la unidad no son homeomórficos, y sin embargo, de alguna manera fue capaz de unir un punto único en el disco a cada punto único en la esfera? Además, no hemos mencionado ninguna matemática no clásica, entonces, ¿qué está pasando?
De hecho, nuestro algoritmo tiene un serio inconveniente: funciona para todos los puntos en toda la esfera, excepto para los puntos en el hemisferio norte con Y = 0 y X <= 0, que, al empacar y desempacar, se comparan erróneamente con el punto correspondiente en el hemisferio norte.
La razón de esto es que cuando se descartan sus coordenadas Z, el número complejo correspondiente es un número real negativo, no tiene una parte imaginaria. Cuando tomamos el valor principal de la raíz cuadrada de un número real negativo, a su vez obtenemos un número complejo completamente imaginario que no tiene la parte real (esto es similar al hecho de que el valor principal de la raíz cuadrada de -1 es igual a
i ). Luego tratamos de mantener el signo de la coordenada Z en lo que es esencialmente cero.
Tira de problemas Los puntos con Y = 0 y X <= 0 se agrupan en una línea de números puramente imaginarios con partes reales indefinibles.Veamos qué sucede cuando empacamos dos de esos puntos (no olvide que x <= 0).
El | Punto norte | Punto sur
unidad | (x, 0, z) | (x, 0, -z)
disco | x + 0i | x + 0i
embalado | 0 + √ (-x) i | -0 - √ (-x) i
Dado que la parte imaginaria de la proyección en el disco de ambos puntos es igual a cero, no podemos almacenar el signo de la coordenada Z en el signo de la parte real del valor principal de la raíz cuadrada, porque en sí mismo es igual a cero. Simplemente podemos detenernos en esto, aceptando el hecho de que el algoritmo no funciona para estos puntos, o podemos seguir adelante.
Olvida lo que aprendimos
En todas las áreas y ramas de las matemáticas que conozco, se supone que 0 = -0. Esto se deduce de la definición de
-a , que es lo opuesto a
a , indicando que
"-a es el único número que da 0 cuando se suma con a" . Dado que 0 también es un elemento cero con respecto a la suma (
0 + a = a + 0 = a ), lo único que necesita agregar a 0 para obtener 0 es 0 en sí mismo.
Sin embargo, en el desarrollo de software, todo es diferente. En la mayoría de las representaciones de números de coma flotante, junto con el exponente y la mantisa, se utiliza un bit extra para almacenar el personaje. Esto significa que cuando el exponente y la mantisa son 0, el bit de signo se puede usar para distinguir entre ceros positivos y negativos. En la mayoría de los lenguajes de programación (si no todos), estos dos ceros se tratan como un solo cero (solo intente
0 == -0 ), pero hay una diferencia, y esto se puede ver si intenta enviar “-0” y “0 al terminal "- así es como se deducirán.
Esto es extremadamente importante para nosotros: ¡el valor de cero puede usarse para almacenar información sobre el signo! De hecho, se almacena correctamente de todos modos; en nuestro caso, el problema es que no se lee correctamente. Si miramos la penúltima línea en el algoritmo de desempaquetado, veremos lo siguiente:
packed.real() < 0 ? -1 : 1
Esta operación lee el signo de la parte real del valor empaquetado para determinar a qué hemisferio pertenece el punto: norte o sur. Sin embargo, en el caso de
empaquetado.real () es 0 o -0, el operador de comparación ignora el carácter y el operador ternario siempre devuelve 1. La forma correcta de leer el carácter es una solicitud
real del estado del bit de signo, por ejemplo, usando
std :: signbit de C ++ o
np .signbit de Numpy a Python: la función depende del idioma. Recuerde que el bit de signo es 1 cuando el número es negativo y 0 cuando el número es positivo.
Por lo tanto, obtenemos una función corregida y cien por cien funcional:
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
Eso es todo! Ahora el algoritmo está completo. Las matemáticas no clásicas se manifiestan en el hecho de que usamos el hecho de que 0 difiere de -0, lo cual es falso para todas las áreas de matemáticas que conozco. Sin embargo, hay una manera de hacer lógica esta extrañeza en un sentido teórico, matemáticamente riguroso.
Espacios que no cumplen con las reglas: una línea recta con dos puntos de origen
Para comprender mejor lo siguiente, debe conocer los conceptos de clases de equivalencia y vecindarios. Esto es opcional, pero será más claro.
Podemos asegurar la consistencia de esta rareza con un "signo cero", comenzando con un espacio topológico interesante: una línea recta con dos puntos de origen.
Una línea recta con dos puntos de origen es un eje numérico real ordinario, que de alguna manera creció un 0 extra por sí mismo.Se obtiene una línea recta con dos puntos de origen cuando tomamos dos ejes numéricos reales y pegamos cada número con su opuesto, excepto 0. Formalmente, una línea recta con dos puntos de origen es un espacio cociente R² con una relación de equivalencia que identifica dos números si son iguales
y no son 0. El resultado es una línea recta de números reales con dos ceros diferentes equidistantes de cualquier punto, pero al mismo tiempo diferentes entre sí. Formalmente, dos vecindarios de cada uno de los ceros siempre tienen una intersección no vacía.
Podemos expandir esto e intentar definir el objeto "similar a un disco" que se utilizó en este artículo. Anteriormente, mantuvimos por la fuerza el signo de la coordenada Z del punto en la parte real de la raíz cuadrada principal de su proyección en el disco complejo, incluso si esta parte real es 0. Esto significa que no usamos números complejos, sino otro concepto similar a ellos: un número complejo, la parte imaginaria de la cual es un número real, y la parte real de la cual es un punto en una línea con dos puntos de origen, por lo que podemos distinguir la parte real igual a +0 y -0. De hecho, ¡usamos
números complejos con dos puntos de origen!Y, de hecho, no encontramos una biyección (mapeo uno a uno) entre una esfera y una unidad de disco, pero encontramos una biyección entre una esfera y una unidad de disco con dos puntos de origen. No verifiqué si esta biyección es un homeomorfismo (un homeomorfismo es una biyección continua en ambas direcciones), pero tal vez algún día lo haga.
Un poco de topología al final
En conclusión, quiero enfatizar que aunque el plano complejo que utilizamos con dos puntos de origen no se sigue de la misma construcción que la línea recta con dos coordenadas, de hecho es el equivalente de otro plano complejo con dos puntos de origen coordinado, construido de manera similar a una línea recta con Dos origen.
En el caso de una línea recta con dos puntos de origen, pegamos dos copias del eje del número real en todos los lugares excepto 0. Podemos hacer lo mismo con dos copias del plano complejo pegando cada par de números complejos iguales que no sean 0, y de manera similar se vuelven complejos Un avión con dos puntos de origen. Esta construcción difiere de la construcción de un nuevo plano complejo a partir de una línea recta con dos puntos de origen y un eje numérico real ordinario: el primero es un espacio factorial y el segundo es un producto de espacios. Sin embargo, la única diferencia entre los dos espacios resultantes es la forma de
escribir diferentes ceros en cada espacio: en el primero se cuentan como (
0 + 0i) a y (
0 + 0i) b (dos ceros tomados de dos espacios diferentes no pegados), y en este último se leen como
(0a + 0i) y
(0b + 0i) . De hecho, ambos espacios son homeomórficos, por lo que puede usar uno de manera segura donde se requiere el otro.
Conclusión
Espero que hayas disfrutado esta excursión al mundo de las matemáticas extrañas y oscuras. Insisto nuevamente en el hecho de que, estrictamente hablando, este algoritmo se comporta peor que el algoritmo
oct del artículo que mencioné al principio. Aunque es cercano o incluso más rápido en tiempo de ejecución, su distribución de puntos en la esfera está lejos de ser tan buena. Escribí este artículo para mostrar cómo las matemáticas aparentemente extrañas, como las tonterías abstractas, pueden tener aplicaciones muy interesantes en el mundo real; Por otra parte, encuentro este sinsentido abstracto encantador. Espero que hayas aprendido algo útil del artículo, ¡gracias por leer!