Was ist der Unterschied zwischen verschiedenen raumfüllenden Kurven?

Raumfüllende Kurven sind in vielen Grafikanwendungen wichtig, da sie dazu beitragen, räumliche Lokalität freizulegen. Wir hören oft von verschiedenen Algorithmen, die Z-Kurven, Morton-Codes, Hilbert-Kurven usw. verwenden. Was sind die Unterschiede zwischen einigen dieser verschiedenen Kurven und wie wirken sie sich auf verschiedene Anwendungen aus?

Der Unterschied besteht darin, wie gut ein Mapping die Lokalität bewahrt und wie einfach es ist, die Schlüssel zu codieren / decodieren. In der Arbeit "Lineare Clusterbildung von Objekten mit mehreren Attributen" von HV Jagadish heißt es: "Durch algebraische Analyse und durch Computersimulation haben wir gezeigt, dass die Hilbert-Zuordnung unter den meisten Umständen so gut oder besser als die besten in vorgeschlagenen alternativen Zuordnungen ist die Literatur". Auf der anderen Seite ist die Verwendung von z-order etwas einfacher. Vergleichen Sie beispielsweise die verschiedenen Methoden, die in Bit Twiddling Hacks für z-order und Wikipedia für Hilbert-order aufgeführt sind.

Was die Anwendungen angeht, denke ich, dass der Hauptvorteil bei der Verwendung von Raumfüllungskurven darin besteht, dass sie Punkte aus einem höherdimensionalen Raum auf einen Raum mit einer niedrigeren Dimension abbilden. Sie ermöglichen beispielsweise die Fensterabfrage nach Punkten mithilfe des traditionellen B-Tree-Datenbankindex. Andererseits besteht der Nachteil darin, dass man die Grenzen der Eingabe im Voraus kennen muss, da es schwierig ist, die Größe der Abbildung später zu ändern.

PS: "Z-Kurve" entspricht "Morton-Code".

PPS: Zusätzliche Zuordnungen umfassen Peano-Kurven und für Anwendungen siehe auch Geohash .

Diese raumfüllenden Kurven ermöglichen es, die Lokalität in mehreren Dimensionen beizubehalten, wenn Sie linear entlang der Kurve "gehen".

Wie ich gesehen habe, wird Z-Order (auch als Morton-Code bekannt) am häufigsten verwendet, da der Rechenaufwand konstant (und günstig) ist, um auf einen beliebigen Punkt der Kurve direkt zuzugreifen. (Und einfach in Hardware mit 0-Zyklus-Einbußen zu implementieren, da dies dem "nur Schalten" von Adressleitungen entspricht).

Ein konkretes Beispiel für eine Z-Order-Kurve ist das Textur-Swizzling: Dies erhöht im Grunde die Cache-Trefferrate für Textur-Lesevorgänge auf GPUs. (Siehe Bilder im Artikel über Z-Curve https://en.wikipedia.org/wiki/Z-order_curve )

Wenn die Textur einfach linear gespeichert wird, erhalten Sie den maximalen Cachetreffer, wenn Sie nur die Textur als 2D-Bild rendern. Wenn Sie sie jedoch auf dem Bildschirm um 90 Grad drehen, geraten Sie in den schlimmsten Fall (Cache-Fehler für jedes gelesene Textur). .

Infolgedessen ist es besser, ein wenig abzuwägen und Ihr Best-Case-Szenario zu senken und für die meisten Muster bessere Cache-Treffer zu erzielen.

Wie ich gesehen habe, erfordern andere Kurven möglicherweise einen rekursiven Schritt für ihre Berechnung und verursachen höhere Kosten als die Z-Kurve mit einem minimalen Gewinn an Lokalitätskohärenz. Ich habe also noch nichts über die Kurve gehört, die für einen praktischen Zweck verwendet wird, außer als Forschungsgegenstand in Mathematik oder kreativen / lustigen Renderings.