Apa perbedaan antara berbagai kurva pengisian ruang?

Kurva yang mengisi ruang penting dalam banyak aplikasi grafis karena mereka membantu mengekspos lokalitas spasial. Kita sering mendengar tentang algoritma yang berbeda menggunakan kurva Z, kode Morton, kurva Hilbert, dll. Apa perbedaan antara beberapa kurva berbeda ini dan bagaimana mereka berlaku untuk berbagai aplikasi?

Perbedaannya adalah seberapa baik pemetaan mempertahankan lokalitas dan betapa mudahnya untuk menyandikan / mendekode kunci. Makalah "Linear Clustering of Objects dengan Multiple Attributes" oleh HV Jagadish mengatakan: "Melalui analisis aljabar, dan melalui simulasi komputer, kami menunjukkan bahwa dalam sebagian besar keadaan, pemetaan Hilbert dilakukan dengan baik atau lebih baik daripada yang terbaik dari pemetaan alternatif yang disarankan dalam literatur". Di sisi lain, z-order sedikit lebih mudah digunakan, misalnya membandingkan berbagai metode yang tercantum dalam Bit Twiddling Hacks untuk z-order dan Wikipedia untuk Hilbert-order.

Adapun aplikasi, saya pikir keuntungan utama dalam menggunakan kurva pengisian ruang adalah bahwa mereka memetakan titik dari ruang dimensi yang lebih tinggi ke ruang dimensi yang lebih rendah. Sebagai contoh, mereka memungkinkan untuk mencari kueri untuk poin menggunakan indeks database B-tree tradisional. Sekali lagi, di sisi lain, kerugiannya adalah seseorang harus mengetahui batasan input sebelumnya karena sulit untuk "mengubah ukuran" pemetaan nanti.

PS: "Z-curve" sama dengan "Morton code".

PPS: Pemetaan tambahan termasuk kurva Peano dan untuk aplikasi lihat juga Geohash .

Kurva yang mengisi ruang tersebut memungkinkan untuk menjaga lokalitas dalam berbagai dimensi saat Anda "berjalan" secara linear di sepanjang kurva.

Dari apa yang saya lihat, Z-Order (juga dikenal sebagai kode Morton) adalah yang paling banyak digunakan karena biaya komputasinya yang konstan (dan murah) untuk mengakses setiap titik kurva secara langsung. (Dan mudah diimplementasikan dalam perangkat keras dengan penalti 0 cycle, karena sesuai dengan "address switching" kabel alamat).

Contoh konkret kurva Z-Order adalah tekstur swizzling: yang pada dasarnya meningkatkan tingkat cache-hit untuk membaca tekstur pada GPU. (Lihat gambar dalam artikel tentang Z-Curve https://en.wikipedia.org/wiki/Z-order_curve )

Jika tekstur disimpan secara linier, Anda mendapatkan hit cache maksimum jika Anda membuat hanya tekstur sebagai gambar 2D, tetapi jika Anda memutarnya dengan 90 derajat di layar, Anda masuk ke skenario terburuk (cache miss untuk setiap membaca tekstur) .

Akibatnya, lebih baik menukar sedikit dan menurunkan skenario kasus terbaik Anda dan memiliki hit cache yang lebih baik untuk sebagian besar pola.

Sebagai catatan pribadi, dari apa yang saya lihat, kurva lain mungkin memerlukan langkah rekursif untuk perhitungan mereka dan menghasilkan biaya yang lebih besar daripada Z-Curve dengan keuntungan minimal dalam hal koherensi lokalitas. Jadi, saya belum pernah mendengar tentang kurva yang digunakan dengan tujuan praktis, kecuali sebagai subjek penelitian dalam rendering matematika atau kreatif / lucu.