Реализация Octree для треугольной сетки и частиц
В настоящее время я работаю в эффективном механизме расчета для моделирования частиц как в CPU, так и в GPU. В последнее время я работал в октриах, и мне удалось написать рабочую версию октри для частиц в космосе, а также эффективно обрабатывать их столкновения. Теперь мне нужно вставить треугольную сетку (объект STL) в мое дерево, чтобы я мог также обрабатывать столкновения между частицами и треугольниками объекта. Я запутался, как мне эффективно вставить треугольники в мою уже созданную октаву? Пожалуйста, предложите методы для достижения этой цели. Если это поможет, я работаю с C ++. Уже спасибо
Решение
Вставка треугольников в существующий Octree не должна сильно отличаться от создания нового Octree и вставки его в него. Единственное, что здесь важно, — это убедиться, что ваш существующий Octree покрывает трехмерное пространство, которое гарантированно включает в себя все треугольники.
Кроме этого, что касается самой вставки, я бы порекомендовал реализовать двухэтапную вставку, где на первом шаге вы используете быстрый тест, чтобы увидеть, может ли треугольник содержаться в определенном кубе, и на втором этапе (в случае, если первое прошло) вы действительно делаете правильный расчет, чтобы увидеть это.
Одним из таких быстрых тестов является получение ограничивающего прямоугольника треугольника (от минимального x, y, z всех точек до максимального x, y, z всех точек) и сравнение этого прямоугольника с одним из октре (если обе координаты прямоугольника на одной и той же оси не находятся в пределах диапазона, определенного блоком октодеревьев, и находятся на одной стороне (как снизу, так и выше), то это определенно снаружи).
Очевидно, что как только вы обнаружили пересечение между треугольником и прямоугольником Octree, вы должны повторить этот тест для всех его дочерних блоков.
Есть также другие места в алгоритме, чтобы сделать это более эффективным (например, сортировка прямоугольников и треугольников по x, y, z и затем проверка, которая учитывает только релевантные блоки), но это зависит от уровня, на котором вы хотите оптимизировать ,
Другие решения
Если ваши частицы имеют одинаковый размер, а ваши треугольники — нет, это обычно требует совершенно другой структуры данных. С частицами одинакового размера вы можете просто рассматривать их как точки и просто хранить одну частицу в одном листовом узле дерева как одну точку в пространстве (не имеет значения, имеет ли он большой радиус / размер, пока все частицы одинакового размера, поскольку ваши поисковые запросы, при условии, что они расширены по размеру частицы, всегда будут поднимать свои центральные точки).
Для треугольников они могут сильно различаться по размеру и могут пересекаться кратно восьми дочерним октантам. В результате вы можете сделать несколько вещей, о которых я знаю:
- Просто вставьте указатель / индекс в треугольник в нескольких листьях с некоторой избыточностью или просто продублируйте все данные треугольника во всех листьях (это может быть взрывоопасно при использовании памяти, если вы не будете осторожны с этим с точки зрения настройки параметров для дерево против контента, но это может сделать поиск более удобным для кеша).
- Разделите треугольник так, чтобы, если он пересекает два или более октанта, он становился двумя или более разделенными треугольниками. Это, как правило, немного дороже для сборок / обновлений, но может быть быстрым для запросов, если вы храните данные треугольника непосредственно в листьях удобным для кеш способом.
- Используйте свободное представление, как свободный октри. В этом случае при вставке вы рассматриваете треугольник только как одну точку. Однако вы расширяете AABB всех узлов октодерева, которые вы пересекаете во время вставки, чтобы охватить треугольник.
# 1 имеет тенденцию быть приемлемым для динамического контента, если вы минимизируете использование памяти и обработку, вовлеченную в построение дерева, и устанавливаете некоторые разумные ограничения, такие как максимальная глубина для октодерева, чтобы оно не хотело делиться бесконечно.
# 2 имеет тенденцию быть достаточно хорошим для статического контента и хорошо подходит для быстрого поиска, так как это может привести к более мелкому и лучше сбалансированному дереву, чем # 1, потому что у вас нет перекрывающихся данных, хранящихся в листьях, которые будут как правило, хотят, чтобы они разделились больше, чем в идеале. Если ваши данные статичны, то вам может потребоваться сохранить только одну копию в самом дереве непосредственно, и это дерево может свободно изменять эти данные так, как они хотят, чтобы обеспечить самый быстрый поиск.
# 3 имеет тенденцию быть очень хорошим для динамического контента, поскольку он хорошо уравновешивает накладные расходы между созданием / обновлением дерева и его поиском. Тем не менее, свободная октрида сильно ухудшает производительность поисковых запросов, потому что то, что раньше было простой проверкой относительно центральной точки, чтобы определить, какой октант (ы) для обхода, теперь требует проверки AABB всех 8 октантов, чтобы определить, каких детей пройти во время поиска. Однако это значительно снижает накладные расходы на построение и обновление дерева, делая его хорошо сбалансированным для динамического контента, где, скажем, сетка деформирует каждый отдельный кадр в интерактивном контексте реального времени.
Он помогает с этими типами вопросов точно определять ваши потребности, например, статичны ли ваши сетки или нет, нужны ли вам быстрые обновления / сборки / поиски или баланс (обычно вы не можете сделать все эти три вещи очень быстрыми: сделать один супер быстро обычно означает сделать другой медленнее).
Raytracers, например, часто используют повторы, которые очень хорошо подходят для чрезвычайно статичного контента, поскольку они часто могут позволить себе потратить некоторое дополнительное время на построение структуры, поскольку впоследствии они могут выполнить миллиарды тестов пересечения лучей / треугольников. Для raytracer не обязательно иметь дело с сотнями миллисекунд, чтобы построить / обновить свой пространственный индекс, поскольку может потребоваться много секунд, а иногда даже минут или часов, чтобы визуализировать всю сцену с производственным качеством. 100 мс по стандартам офлайн-рендеринга — это крошечное время, по стандартам реального времени — невероятное количество времени. С другой стороны, самые быстрые времена поиска настолько важны для raytracer, что свободные октреы, как правило, будут ужасным выбором, и большинству raytracers часто захочется глубоко скопировать данные, необходимые для выполнения тестов на пересечение в листья, чтобы они не не требуют случайных образцов доступа к памяти для доступа к данным, хранящимся в листьях.
Однако физическому движку, занимающемуся обнаружением столкновений многих вещей, движущихся в контексте реального времени, требуется совсем другое представление, подходящее для динамического контента. И игровые движки, которые имеют дело с широким спектром статического и динамического контента в полностью интерактивных контекстах реального времени, могут использовать несколько структур данных: каждая из них приспособлена для типа контента, который они хранят.
Если ваши частицы действительно имеют одинаковый размер, то я рекомендую использовать другую структуру данных (например, другой тип дерева октя) для хранения треугольных сеток. Тот же случай, если ваши частицы очень динамичны, а ваши сетки довольно статичны. В этом случае, если вы ищете, чтобы увидеть, сталкивается ли частица с сеткой или частицей, вы можете сначала проверить октодерево, хранящее сетки, оптимизированные для треугольников. Если вы не нашли пересекающийся треугольник, то ищите другое октодерево, подходящее для хранения динамических частиц одинакового размера, чтобы проверить столкновения между частицами. Вы все еще можете абстрагировать это до такой степени, что это будет выглядеть как единая структура данных, но в идеале вы должны использовать две разные реализации для этого.
Для сеток, которые преобразуются, также может быть полезно сохранить два октре: внешнее окто для целых сеток только для грубых тестов на пересечение с их AABB, например, Затем, если грубый тест на пересечение пройден, ищите октрево, сохраненное для каждой сетки, чтобы определить, какие треугольники пересекаются. Это позволяет избежать обновления треугольников хранения октодерева при преобразовании сеток (например, при их вращении).