Хранение треугольников с общим ребром в Octree

Я пытаюсь загрузить файл сетки STL и сохранить его треугольники в структурах данных октодерева для некоторого научного анализа (не для игр).

пример двух треугольников с общим краем

как показано на изображении, треугольник 1 хранится в узлах октодерева NE, SE, SW и NW, а треугольник 2 хранится в узлах октодерева NW и SW. (2d представление, но та же история в 3d).

Было бы бессмысленно разделять узлы на СЗ и ЮЗ, поскольку два треугольника имеют общую красную сторону. и эта проблема становится более сложной, если у меня есть более двух треугольников, охватывающих несколько ячеек.

Итак, как правильно хранить треугольники в октодереве?

ps- я не хочу обрезать треугольники.


c++ structure octree
person Arash    schedule 07.04.2017    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Я использовал два наиболее распространенных подхода:

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

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

person Michal Butterweck    schedule 06.06.2018