Здравствуйте, notepad, Вы писали:

N>Да-да, именно octree. Ты правильно описал, где эта структура данных применяется очень эффективно. Я тоже слабо представляю как балансировать/сортировать такое дерево. Зачем? Скорость поиска и обработки элементов сильно возрастает.
Хм. Похоже кто-то из нас не понимает что такое Octree и как его готовить.
Я себе его представляю так:
Берем пространство допустим куб со стороной километер и делим его на 8 кубов со стороной 500 метров и так далие пока не достигнем куба приемлимого размера. Теперь берем все объекты из пространства и в зависимости от их координат и размеров (если объект попадает в несколько кубов сразу) заносим ссылки на объекты в соответствующие кубы (наименьшего размера). Теперь для того чтобы проверить столкновения надо только пройтись по спискам в кубах.
А теперь внимание вопросы: Где тут динамическое дерево? Что тут можно отсортировать? И что тут балансировать?
И вопрос на засыпку: Как вобще можно отсортировать дерево? Балансировка дерева это я понимаю, а что такое сортировка дерева?