Jaka jest różnica między różnymi krzywymi wypełniającymi przestrzeń?

Krzywe wypełniające przestrzeń są ważne w wielu aplikacjach graficznych, ponieważ pomagają uwidocznić lokalizację przestrzenną. Często słyszymy o różnych algorytmach wykorzystujących krzywe Z, kody Mortona, krzywe Hilberta itp. Jakie są różnice między niektórymi z tych różnych krzywych i jak odnoszą się one do różnych aplikacji?

Różnica polega na tym, jak dobrze mapowanie zachowuje lokalizację i jak łatwo jest kodować / dekodować klucze. W artykule „Liniowe grupowanie obiektów o wielu atrybutach” HV Jagadish mówi: „Poprzez analizę algebraiczną i symulację komputerową pokazaliśmy, że w większości przypadków mapowanie Hilberta przebiegało tak dobrze lub lepiej niż najlepsze z alternatywnych mapowań sugerowanych w literatura ”. Z drugiej strony, kolejność Z jest nieco prostsza w użyciu, na przykład porównaj różne metody wymienione w Bitach Twiddling Hacks dla kolejności Z i Wikipedii dla kolejności Hilberta.

Jeśli chodzi o aplikacje, myślę, że główną zaletą stosowania krzywych wypełniania przestrzeni jest to, że odwzorowują one punkty z przestrzeni o większym wymiarze na przestrzeń o niższym wymiarze. Umożliwiają one na przykład zapytanie okna o punkty przy użyciu tradycyjnego indeksu bazy danych B-drzewa. Z drugiej strony, wadą jest to, że trzeba wcześniej znać granice danych wejściowych, ponieważ później trudno jest „zmienić rozmiar” mapowania.

PS: „Krzywa Z” jest taka sama jak „Kod Mortona”.

PPS: Dodatkowe mapowania obejmują krzywą Peano, a dla aplikacji zobacz także Geohash .

Te krzywe wypełniania przestrzeni pozwalają zachować lokalizację w wielu wymiarach, gdy „chodzisz” liniowo wzdłuż krzywej.

Z tego, co widziałem, Z-Order (znany również jako kod Mortona) jest najbardziej wykorzystywany ze względu na jego koszt obliczeniowy, który jest stały (i tani), aby uzyskać bezpośredni dostęp do dowolnego punktu krzywej. (I łatwe do wdrożenia sprzętowego z karą zerową, ponieważ odpowiada to „tylko przełączaniu” przewodów adresowych).

Konkretnym przykładem krzywej Z-Order jest zamiatanie tekstur: zasadniczo zwiększa współczynnik trafień w pamięć podręczną dla odczytanych tekstur na GPU. (Zobacz zdjęcia w artykule o Z-Curve https://en.wikipedia.org/wiki/Z-order_curve )

Jeśli tekstura jest po prostu przechowywana liniowo, otrzymasz maksymalne trafienie w pamięć podręczną, jeśli renderujesz samą teksturę jako obraz 2D, ale jeśli obrócisz ją o 90 stopni na ekranie, przejdziesz do najgorszego scenariusza (brak pamięci podręcznej przy każdym odczytaniu tekstury) .

W rezultacie lepiej jest nieco odrzucić i obniżyć scenariusz najlepszego przypadku i uzyskać lepsze trafienie w pamięć podręczną dla większości wzorców.

Jako osobistą notatkę, z tego, co widziałem, inne krzywe mogą wymagać rekurencyjnego kroku do ich obliczenia i skutkować wyższym kosztem niż Krzywa Z przy minimalnym wzroście spójności lokalizacji. Nie słyszałem więc o tych krzywych wykorzystywanych w praktycznym celu, z wyjątkiem badań jako matematyki lub kreatywnego / śmiesznego renderowania.