W dniu 07.05.2011 07:40, kenobi pisze:
> ale bedzie tu mulic jak cholera
Bo to jest algorytm do niczego.


> jakie sztuczki optymalizacyjne? mi przychodza dwie do glowy - wstepny
> podzial na sektory, oznaczanie w kazdej klatce bitflagami tych
> objektow ktore sie poruszyly i sprawdzanie tylko ich
Sortujesz wektor obiektów po x,y,z. Przeglądasz liniowo ten wektor
sprawdzając czy dwie współrzędne środków różnią się o mniej niż promień
(czyli robisz test na kolizję 2 sześcianów. Jeżeli tak to robisz
dokładny test liczeniem pierwiastków. Całość masz w
O(n*(log(n)+1))=O(n*logN).

W momencie gdy całość trzymasz już posortowane w ten sposób w jakimś
drzewie koszt jeszcze może spaść bo zmieniasz układ (w O(log(n)) tylko
gdy doszło do zmiany w porządku sortowania danego obiektu.

Jak masz dane w octtree to też można optymalizować.

--
Pozdrawiam
Michoo