Quelle est la différence entre les différentes courbes de remplissage d'espace?

Les courbes de remplissage d'espace sont importantes dans de nombreuses applications graphiques car elles permettent d'exposer la localité spatiale. Nous entendons souvent parler de différents algorithmes utilisant des courbes Z, des codes Morton, des courbes Hilbert, etc. Quelles sont les différences entre certaines de ces différentes courbes et comment s'appliquent-elles à diverses applications?

La différence est à quel point un mappage préserve la localité et à quel point il est facile de coder / décoder les clés. L'article "Linear Clustering of Objects with Multiple Attributes" de HV Jagadish dit: "Grâce à l'analyse algébrique et à la simulation par ordinateur, nous avons montré que dans la plupart des cas, la cartographie de Hilbert fonctionnait aussi bien ou mieux que la meilleure des cartographies alternatives suggérées dans la littérature". D'un autre côté, l'ordre z est un peu plus simple à utiliser, par exemple comparer les différentes méthodes répertoriées dans Bit Twiddling Hacks pour l'ordre z et Wikipedia pour l'ordre Hilbert.

En ce qui concerne les applications, je pense que le principal avantage de l'utilisation des courbes de remplissage d'espace est qu'elles mappent les points de l'espace de dimension supérieure à l'espace de dimension inférieure. Par exemple, ils permettent de rechercher des points par fenêtre à l'aide d'un index de base de données B-tree traditionnel. Encore une fois, d'un autre côté, l'inconvénient est qu'il faut connaître les limites de l'entrée à l'avance car il est difficile de «redimensionner» le mappage plus tard.

PS: "Z-curve" est le même que "Morton code".

PPS: les mappages supplémentaires incluent la courbe de Peano et pour les applications, voir également Geohash .

Ces courbes de remplissage d'espace permettent de conserver la localité dans plusieurs dimensions lorsque vous "marchez" linéairement le long de la courbe.

D'après ce que j'ai vu, Z-Order (également connu sous le nom de code Morton) est le plus utilisé en raison de son coût de calcul qui est constant (et bon marché) pour accéder directement à n'importe quel point de la courbe. (Et facile à implémenter dans le matériel avec une pénalité de 0 cycle, car cela correspond à des fils d'adresse "simplement commutés").

Un exemple concret de courbe Z-Order est le swizzling de texture: qui augmente fondamentalement le taux de succès du cache pour la texture lue sur les GPU. (Voir les images dans l'article sur Z-Curve https://en.wikipedia.org/wiki/Z-order_curve )

Si la texture est simplement stockée linéairement, vous obtenez le maximum de cache si vous restituez uniquement la texture en tant qu'image 2D, mais si vous la faites pivoter de 90 degrés à l'écran, vous entrez dans le pire des cas (cache manquant pour chaque texture lue) .

En conséquence, il est préférable de faire un peu de compromis et d'abaisser votre meilleur scénario et d'avoir un meilleur accès au cache pour la plupart des modèles.

À titre personnel, d'après ce que j'ai vu, d'autres courbes peuvent nécessiter une étape récursive pour leur calcul et entraîner un coût plus élevé que la courbe Z avec un gain minimal en termes de cohérence de localité. Donc, je n'ai pas entendu parler de ces courbes utilisées à des fins pratiques, sauf en tant que sujet de recherche en rendu mathématique ou créatif / amusant.