Комментарии 7
а по поводу VP-Tree не думали? В теории, для точек на плоскости оно должно неплохо искать соседей. Только его перестраивать сложновато, насколько я помню.
в статье про разные алгоритмы речь идет про пересечение прямоугольников. В случае же с точками вам бы:
а) больше подошло r-tree
б) было бы достаточно вообще детектора коллизий на основе очереди с приоритетами и расчетом новой коллизии при наступлении каждого из событий
а) больше подошло r-tree
б) было бы достаточно вообще детектора коллизий на основе очереди с приоритетами и расчетом новой коллизии при наступлении каждого из событий
ага. перевод…
На практике везде используется динамическое AABB-дерево.
Изначально строится дерево, содержащее подскэйленные + увеличенные по направлению движения (прогнозирование) баунды. Когда баунд тела выходит за пределы текущего баунда, тогда уже вставляют элемент по новой. При этом дерево полностью не перестраивают. На этом моменте еще можно провести множество оптимизаций, связанных с поиском новых столкновений и актуализацией старых.
Также разделяют деревья для статических и динамических элементов, у которых может быть различной стратегия обновления.
Ну и разделение деревьев положительно сказывается на запросах к сцене (raycast, overlap, sweep и т.д.)
Изначально строится дерево, содержащее подскэйленные + увеличенные по направлению движения (прогнозирование) баунды. Когда баунд тела выходит за пределы текущего баунда, тогда уже вставляют элемент по новой. При этом дерево полностью не перестраивают. На этом моменте еще можно провести множество оптимизаций, связанных с поиском новых столкновений и актуализацией старых.
Также разделяют деревья для статических и динамических элементов, у которых может быть различной стратегия обновления.
Ну и разделение деревьев положительно сказывается на запросах к сцене (raycast, overlap, sweep и т.д.)
Судя по комментариям, то нужна статья с обзором всех популярных существующих пространственных индексов, где бы описывались все сильные и слабые стороны каждого.
Нужна! А ещё к каждому кейс использования. Перестраивать дерево на каждый кадр или как-то хитро его модифицировать, если объектов много и они часто перемещаются? У себя в проекте топдаун-игры, я тупо нарезал уровень на регулярные квадраты и каждый кадр вписываю туда все попадающие объекты. Дёшево и сердито. Но не даёт покоя мысль, что есть какие-то способы и волков накормить и овец сохранить.
Нормальный метод. В молекулярной динамике используется уже много десятилетий, называется
en.wikipedia.org/wiki/Cell_lists
Есть и альтернативы, конечно.
en.wikipedia.org/wiki/Cell_lists
Есть и альтернативы, конечно.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Деревья квадрантов и распознавание коллизий