Я хочу использовать октодерево в качестве представления сцены OGL, и у меня там есть движущийся объект. Я также хотел бы использовать это октодерево для ускорения обнаружения столкновений. Есть ли какой-нибудь хороший алгоритм, который дает вам путь в октодереве (все ячейки/узлы такого пути), через который мог бы пройти движущийся объект?
Предположим, у меня есть один движущийся объект, скорость которого мне известна (т.е. две позиции, начало движения и окончания движения в одном кадре).
Моя идея состоит в том, чтобы просто пройтись по всему дереву и выполнить обнаружение столкновений ячейки, содержащей движущийся объект, и остальных ячеек. Это дало бы мне их все, но разве это не перебор? Спасибо!
Octree — на какие клетки влияет движущийся объект?
Ответы (1)
Если у вас есть начальная и конечная позиции вашего движущегося объекта, то у вас есть луч, определяющий движение вашего объекта. Узел в вашем октодереве — это прямоугольный параллелепипед, представляющий собой довольно простой многогранник. Вы можете думать о тестах на столкновение/пересечение как о тестах на пересечение луча и прямоугольного параллелепипеда.
Ознакомьтесь с алгоритмами пересечения объект-объект на этой странице:
http://www.realtimerendering.com/intersections.html#II247
Эта страница указывает на код на Github для пересечения луча и многогранника:
https://github.com/erich666/GraphicsGems/blob/master/gemsii/RayCPhdron.c
Чтобы начать с простого примера, предположим, что ваш объект — это просто точка, движущаяся по этому лучу движения. Затем вы можете найти путь объекта, используя пересечение луча и кубоида. Если узел октодерева не содержит луч, то нет смысла углубляться в дочерние узлы этого узла. (Поиск по всему октодереву сверху вниз в первую очередь противоречит цели создания октодерева.) Даже если ваши объекты представляют собой сложную вещь с множеством вершин, написание кода для простого пересечения луча/кубоида для одной движущейся точки будет поучительно.
В книге по вычислительной геометрии Geometric Tools for Computer Graphics, написанной Шнайдером и Эберли, есть хорошая трактовка пересечения линий в многогранниках, включая страницу с простым для понимания псевдокодом. Если вы собираетесь потратить много времени на кодирование трехмерной геометрии, вам понадобится копия этой книги на вашей полке. У Эберли также есть ряд полезных PDF-файлов на его веб-сайте:
https://www.geometrictools.com/
Если вы создадите свое октодерево таким образом, чтобы каждый узел имел указатель на своих непосредственных соседей, это может немного ускорить поиск. Однако я бы не советовал внедрять с самого начала — сначала создайте что-то простое, а не решайте несколько задач реализации одновременно.
Чтобы взять немного более сложный пример, если у вас есть треугольник из 3 вершин, ориентированный так, что нормаль к поверхности треугольника параллельна направлению движения, то проверка пересечения треугольника с кубовидными узлами вашего октодерева будет простой; проверить пересечение луча-кубоида для лучей, начинающихся в каждой вершине и параллельных направлению движения.
Оттуда ваш подход может варьироваться в зависимости от сложности вашего движущегося объекта и ваших потребностей в обнаружении «столкновений». Например, вы можете разрешить считать столкновением не только пересечение, но и очень близкое пересечение одного объекта с другим. Я не знаю, что у вас за приложение, насколько сложным может быть ваш объект, является ли объект приблизительно выпуклым и т. д., но вы могли бы рассмотреть возможность тестирования столкновения с выпуклой оболочкой объекта или, возможно, со сферой/кубом, который охватывает все точки объекта.
person
Rethunk
schedule
22.02.2016
У меня есть книга Эберли «Дизайн 3D-игрового движка, 2-е издание», и она отлично читается и является справочной. Он использует его библиотеку WildMagic 4.0, которая сейчас устарела, поскольку у него есть совершенно новая библиотека, но это все еще отличная книга для обучения. Я хотел бы когда-нибудь приобрести некоторые из его других книг. У меня также есть еще одна замечательная книга Яна Миллингтона — Game Physics Engine Development. Первый больше связан с рендерингом графики, созданием и управлением иерархией сцен, а второй имеет дело с различными типами физики. Серия NVidia GPU Gems — еще один хороший набор книг.
- person Francis Cugler; 22.02.2016
Спасибо большое. Я учту это!
- person Hitokage; 22.02.2016
