Если у вас очень динамические данные, перемещающиеся в каждом кадре, и вам все еще нужно ускорить обнаружение столкновений, я на самом деле рекомендую использовать для этого фиксированную трехмерную сетку.Двумерный эквивалент:
Может также дублироваться как свободный список, чтобы разрешить удаление в постоянном времени, например, (используя nextиндекс в качестве индекса следующего элемента в той же ячейке сетки или следующего свободного элемента, который выскочит из свободного стека, если он был удален):
Другой пример:
Теперь в трех измерениях может показаться, что для этого требуется взрывная память.Однако хитрость заключается в том, чтобы каждая ячейка хранила 32-битный индекс в массиве и в основном служила бы списком индексов с одиночной связью.Это уменьшает размер каждой ячейки до 32 бит.Теперь, если вы храните сетку 100x100x100 (1 миллион ячеек), это займет менее 4 мегабайт.
Когда элементы перемещаются, вы можете просто удалить их из занимаемых ими ячеек, переместить их и вставить ихв новые клетки.Все, что вам нужно сделать для того, чтобы сделать это, это манипулировать некоторыми 32-битными индексами (нет выделения / освобождения памяти для передачи элементов из одного набора ячеек в другие).Это все постоянное время и не требует перебалансировки деревьев или расщепления октантов, которые становятся слишком многолюдными или чего-то в этом роде.
Вы также можете использовать иерархию сеток (это может звучать как октри, но по-другому).Под этим я подразумеваю, что у вас может быть одна грубая сетка для целых объектов сетки в вашей сцене.Тогда каждый объект сетки может хранить грубую сетку, скажем, 10x10x10 для каждой из своих частей.Затем каждая часть хранит точную сетку или октри для каждого из своих многоугольников.Это позволяет неорганическим сеткам, которые, скажем, являются жесткими с частями, которые просто вращаются, как робот, чтобы избежать необходимости обновлять точную сетку / октре многоугольников и просто обновлять свою собственную грубую сетку частей и грубую сетку мировых объектов, когдаон начинает вращать свои ноги и руки, например, только органические модели должны обновлять свои мелкие сетки, когда они деформируются костями, например,
Октябрь, который я бы сохранил для ваших полностью статических элементов / частей, которые никогда не должны бытьобновляется по кадрам, и я бы использовал хорошее октри, разреженное, возможно, с некоторой постобработкой для доступа к памяти для кеша.У вас есть немного больше времени для ускорения поиска в них и минимизации использования их памяти, если вы можете предположить, что октре никогда не нужно обновлять после его создания.