¿Cuál es la diferencia entre varias curvas de relleno de espacio?

Las curvas de relleno de espacio son importantes en muchas aplicaciones gráficas porque ayudan a exponer la localidad espacial. A menudo escuchamos acerca de diferentes algoritmos que utilizan curvas Z, códigos Morton, curvas Hilbert, etc. ¿Cuáles son las diferencias entre algunas de estas curvas diferentes y cómo se aplican a diversas aplicaciones?

La diferencia es qué tan bien una asignación conserva la localidad y lo fácil que es codificar / decodificar las claves. El documento "Agrupación lineal de objetos con múltiples atributos" de HV Jagadish dice: "Mediante el análisis algebraico y la simulación por computadora, demostramos que, en la mayoría de las circunstancias, el mapeo de Hilbert funcionó tan bien o mejor que el mejor de los mapeos alternativos sugeridos en la literatura". Por otro lado, el orden z es un poco más simple de usar, por ejemplo, compare los diversos métodos enumerados en Bit Twiddling Hacks para el orden z y Wikipedia para el orden Hilbert.

En cuanto a las aplicaciones, creo que la principal ventaja en el uso de curvas de relleno de espacio es que mapean puntos desde el espacio dimensional superior al espacio de dimensión inferior. Por ejemplo, hacen posible la consulta de ventana para puntos usando el índice tradicional de base de datos del árbol B. Una vez más, por otro lado, la desventaja es que uno necesita conocer los límites de la entrada de antemano ya que es difícil "redimensionar" el mapeo más adelante.

PD: "curva Z" es lo mismo que "código Morton".

PPS: las asignaciones adicionales incluyen la curva de Peano y para aplicaciones, consulte también Geohash .

Esas curvas de relleno de espacio permiten mantener la localidad en múltiples dimensiones cuando "camina" linealmente a lo largo de la curva.

Por lo que he visto, Z-Order (también conocido como código de Morton) es el más empleado debido a su costo computacional que es constante (y barato) para acceder a cualquier punto de la curva directamente. (Y fácil de implementar en hardware con penalización de 0 ciclos, ya que corresponde a "simplemente cambiar" los cables de dirección).

Un ejemplo concreto de la curva de orden Z es la textura de la textura: básicamente está aumentando la tasa de aciertos de caché para la lectura de textura en las GPU. (Ver imágenes en el artículo sobre la curva Z https://en.wikipedia.org/wiki/Z-order_curve )

Si la textura simplemente se almacena linealmente, obtienes el máximo impacto de caché si renderizas solo la textura como imagen 2D, pero si la giras 90 grados en la pantalla, entras en el peor de los casos (pérdida de caché para cada lectura de textura) .

Como resultado, es mejor intercambiar un poco y reducir su mejor escenario y tener un mejor impacto de caché para la mayoría de los patrones.

Como nota personal, por lo que he visto, otras curvas pueden requerir un paso recursivo para su cálculo y resultar en un costo mayor que la curva Z con una ganancia mínima en términos de coherencia de localidad. Por lo tanto, no he oído hablar de esas curvas utilizadas con un propósito práctico, excepto como un tema de investigación en representación matemática o creativa / divertida.