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:

Źródło: Wikipedia

lub lepsza, ale bardziej kosztowna obliczeniowo Hilbert value:

Źródło: Wikipedia

Comments | #math #algorithms #rendering Share

Comments