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

Question

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

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

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

Answer 1

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

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

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

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

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

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

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

https://www.geometrictools.com/

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

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

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