Kolizje 3D

Witam, mam następujący problem. Piszę silnik gry 3D, ogółem wszystko idzie gładko jednak kolizje w moim świecie 3D nie są zbyt idealne. Samo napisanie kolizji nie było trudne jednak przy sprawdzaniu kolizji na mapie, która posiada nawet do 1000000 obiektów (na razie wprowadziłem ograniczenie ale ten milion niedługo mi nie wystarczy) gra po prostu masakrycznie wolno działa. Nie jest też tak, że sprawdzam kolizje z tymi milionami obiektów, sprawdzam odległość każdego z nich od gracza i jeśli nie przekracza powiedzmy 4 to wylicza kolizje i pozwala wykonać ruch w daną stronę bądź nie. Niestety obliczanie odległości z milionem obiektów trwa zbyt długo (nawet na moim, dość szybkim komputerze), czy macie pomysły jak to efektywnie zrobić? Kolizje nie muszą być super zaawansowane (kolizje z pochylniami itd. odpadają), mój świat gry jest kwadratowy - dosłownie, jak w tej znanej grze Minecraft, może nawet jeszcze bardziej kwadratowy... :) Proszę o nakierowanie na coś co może mi się przydać, czytałem źródła kilku gier (np. Quake'a 3), ale jakoś nie za bardzo mogę załapać jak to działa (bo kolizje tam są bardzo rozbudowane). Nie polecajcie mi też gotowych silników kolizji (już mi w jednym miejscu tak polecili), ja chcę to sam napisać, a podane przykłady takich silników kolizji też były "zbyt rozbudowane", proszę wyłącznie o pomoc.

Bo bez sensu sprawdzasz kolizję ze wszystkimi obiektami, lepiej jakbyś reprezentował wszystkie obiekty w jakiejś ciekawszej strukturze http://en.wikipedia.org/wiki/Octree
Jeśli chcesz rozwiązać problem najprościej jak się da i wydajnie to podziel sobie świat na małe trójwymiarowe kafelki (co i tak już masz pewnie zrobione) i w każdym kafelku trzymaj informację jakie obiekty kolidują z tym kafelkiem (czy tam sześcianikiem), podczas ruchu sprawdzaj kolizje tylko z obiektami które kolidują z siąsiadującymi kafelkami gracza i jeśli podczas ruchu gracz zmieni kolidujące z nim kafelki to wyrzuć go z poprzednich kafelków i dodaj do nowych informację o tym, że z nimi koliduje.

Czyli proponujesz stworzenie czegoś w stylu "regionów" na które pocięta jest cała mapa i sprawdzać tylko w nich kolizje? Niegłupie, spróbuje to zrobić, myślę że ten pomysł może dobrze wypalić, spróbuję i thx za wskazówkę.