Qual é a diferença entre várias curvas de preenchimento de espaço?

As curvas de preenchimento de espaço são importantes em muitas aplicações gráficas, pois ajudam a expor a localização espacial. Frequentemente ouvimos sobre diferentes algoritmos usando curvas Z, códigos de Morton, curvas de Hilbert, etc. Quais são as diferenças entre algumas dessas curvas diferentes e como elas se aplicam a várias aplicações?

A diferença é quão bem um mapeamento preserva a localidade e como é fácil codificar / decodificar as chaves. O artigo "Agrupamento linear de objetos com múltiplos atributos", de HV Jagadish, diz: "Através da análise algébrica e da simulação em computador, mostramos que, na maioria das circunstâncias, o mapeamento de Hilbert teve um desempenho tão bom quanto o melhor dos mapeamentos alternativos sugeridos em a literatura". Por outro lado, a ordem z é um pouco mais simples de usar, por exemplo, compare os vários métodos listados em Bit Twiddling Hacks para ordem z e Wikipedia para ordem Hilbert.

Quanto às aplicações, acho que a principal vantagem do uso de curvas de preenchimento de espaço é que elas mapeiam pontos do espaço dimensional mais alto para o espaço de menor dimensão. Por exemplo, eles possibilitam a janela de consulta de pontos usando o índice tradicional do banco de dados em árvore B. Novamente, por outro lado, a desvantagem é que é preciso conhecer os limites da entrada com antecedência, pois é difícil "redimensionar" o mapeamento posteriormente.

PS: "Curva Z" é o mesmo que "Código Morton".

PPS: mapeamentos adicionais incluem curva Peano e, para aplicativos, consulte também Geohash .

Essas curvas de preenchimento de espaço permitem manter a localidade em várias dimensões quando você "caminha" linearmente ao longo da curva.

Pelo que vi, o Z-Order (também conhecido como código de Morton) é o mais empregado por causa de seu custo computacional, que é constante (e barato) para acessar diretamente qualquer ponto da curva. (E fácil de implementar em hardware com penalidade de 0 ciclo, pois corresponde a "apenas trocar" os fios de endereço).

Um exemplo concreto da curva Z-Order é o swizzling de textura: o que basicamente aumenta a taxa de acertos do cache para a leitura de textura nas GPUs. (Veja imagens no artigo sobre a Z-Curve https://en.wikipedia.org/wiki/Z-order_curve )

Se a textura é simplesmente armazenada linearmente, você obtém o máximo de acertos do cache se renderizar apenas a textura como imagem 2D, mas se você girá-la 90 graus na tela, entrará no pior cenário possível (falta de cache para cada textura lida) .

Como resultado, é melhor trocar um pouco e diminuir o seu cenário de melhor caso e ter melhor acerto de cache para a maioria dos padrões.

Como uma observação pessoal, pelo que vi, outras curvas podem exigir etapas recursivas para o cálculo e resultar em um custo maior do que a curva Z, com um ganho mínimo em termos de coerência da localidade. Portanto, não ouvi falar sobre aquelas curvas usadas com propósitos práticos, exceto como objeto de pesquisa em renderização matemática ou criativa / engraçada.