Octree - какие клетки влияет на движущийся объект?

Question

Я хочу использовать октет как представление сцены OGL, и у меня есть движущийся объект. Я также хотел бы использовать этот октет для ускорения обнаружения столкновений. Есть ли какой-либо хороший алгоритм, который дает вам путь в octree (все ячейки/узлы такого пути), в который будет проникать движущийся объект?

Предположим, у меня есть один движущийся объект, где я знаю скорость (так что две позиции, начало движения и конец движения в одном кадре).

Моя идея - просто пройти через все дерево и выполнить обнаружение столкновения ячейки, содержащей движущийся объект и остальные ячейки. Это даст мне все, но разве это не перебор? Спасибо!

Answer 1

Если у вас есть начальное и конечное положения вашего движущегося объекта, у вас есть луч, определяющий движение вашего объекта. Узел в вашем октете является кубоидом, который является довольно простым многогранником. Вы можете подумать о тестах на столкновение/пересечение в качестве луче-кубоидных тестов пересечения.

Заканчивать алгоритмы Объектно-объект пересечения на этой странице:

http://www.realtimerendering.com/intersections.html#II247

этой странице точек в код на Github для лучей многогранника пересечения:

https://github.com/erich666/GraphicsGems/blob/master/gemsii/RayCPhdron.c

Чтобы начать с простой пример, предположим, что ваш объект является просто точкой, движущейся вдоль этого луча движения. Затем вы можете найти путь к объекту, используя пересечение луча-кубоида. Если узел октета не содержит луч, тогда нет смысла искать глубже в дочерние узлы этого узла. (Поиск по всему октету сверху вниз поражает цель создания октета в первую очередь.) Даже если ваши объекты сложны с множеством вершин, написание кода для простого пересечения луча/кубоида для одной точки в движении будет поучительным.

Вычислительная геометрия книга Геометрические инструменты для компьютерной графики Шнайдером и Eberly имеет хорошую обработку линии-в-многогранника пересечения, в том числе страницы псевдокод, который легко понять. Если вы собираетесь потратить много времени на кодирование 3D-геометрии, вам понадобится копия этой книги на полке. Eberly также имеет ряд полезных PDF-файлов на своем сайте:

https://www.geometrictools.com/

Если вы создаете октодерева таким образом, что каждый узел имеет указатель на его ближайших соседей, то это может ускорить поиск немного. Однако я бы не предлагал внедрить с самого начала - сначала создайте что-то простое, а не сразу займемся несколькими задачами реализации.

Чтобы сделать несколько более сложный пример, если у вас есть треугольник из трех вершин, ориентированный так, чтобы нормальная поверхность треугольника была параллельна направлению движения, тогда тесты пересечения треугольника с кубическими узлами вашего окта были бы прямой; тестовое луче-кубовидное пересечение для лучей, начиная с каждой вершины и параллельно направлению движения.

Оттуда ваш подход может варьироваться в зависимости от сложности вашего движущегося объекта и ваших потребностей в обнаружении «столкновения». Например, вы можете разрешить не только пересечение, которое можно рассматривать как столкновение, но и очень близкий проход одного объекта к другому. Я не знаю, каково ваше приложение, насколько сложным может быть ваш объект, является ли объект примерно выпуклым и т. Д., Но вы можете рассмотреть возможность проверки столкновения с выпуклой оболочкой объекта или, возможно, с помощью сферы/куба, которая охватывает все точки в объекте.