Co wynalazł Hilbert i Morton

Uwaga! Informacje na tej stronie mają ponad 5 lat. Nadal je udostępniam, ale prawdopodobnie nie odzwierciedlają one mojej aktualnej wiedzy ani przekonań.

Mon
12
Jan 2009

Tablicę jednowymiarową można posortować, żeby przyspieszyć jej przeszukiwanie. W programowaniu gier, do przestrzeni 2D i 3D używamy technik podziału przestrzeni (jak BSP, Octree, k-d tree), bo nie sposób uporządkować punktów czy obiektów w kolejności. Jednak czy napewno?

Otóż wynaleziono funkcje, które przeliczają pozycję punktu w przestrzeni (podzielonej wprawdzie na dyskretną siatkę) na pojedynczą liczbę taką, że dwa punkty leżące blisko siebie dostają często zbliżoną wartość. Te funkcje to numer komórki wzdłuż pewnej krzywej (Space-filling curve).

Przykładem może być Morton value:

Morton value
Źródło: Wikipedia

lub lepsza, ale bardziej kosztowna obliczeniowo Hilbert value:

Hilbert value
Źródło: Wikipedia

Comments | #math #algorithms #rendering Share

Comments

[Download] [Dropbox] [pub] [Mirror] [Privacy policy]
Copyright © 2004-2020