Где я могу хранить фигуры в октете?

Немного информации о проектных решениях до сих пор... Я разработал octree-структуру, которая может хранить точки. Я решил ограничить рекурсию "поколений" на основе определенного базового количества вокселей. Ребенок-узлы создаются только при добавлении точек в этот node. Это не динамическое графическое приложение - этот октет и объекты в нем статичны, поэтому предварительная обработка для повышения производительности не вызывает беспокойства.

Теперь я хотел бы добавить "фигуры" в свою октету - в частности, поверхностную сетку, состоящую из треугольников. Вершины этих треугольников не соответствуют точкам, хранящимся в окте. Как хранить эти фигуры в октете? Я вижу два варианта...

Серые узлы "пусты" в том, что у них нет фигур. В альтернативе 1 формы сохраняются в каждом node, который они пересекают, т.е. node 1a содержит формы 1 и 4c и 4d share2. В альтернативе 2 формы сохраняются только в наименьшем node, который они пересекают, т.е. node 1a содержит shape1 и node 4 содержит shape2.

Большинство сообщений на октетах, которые я видел, предполагают Alt1, но они никогда не объясняют, почему. Alt2 имеет больше смысла для меня и создаст дополнительную работу для тех форм, которые находятся на границах node. Почему Alt1 предпочтительнее?

Изменить: Чтобы уточнить, мой язык реализации - С++, поэтому я бы предпочел примеры реализации на этом языке, но вопрос не зависит от языка. Извините, если это неправильное использование тегов.

Edit2: Несмотря на то, что он не имеет прямого отношения к вопросу о хранении формы, эта ссылка содержит хорошее обсуждение обходного пути, которое стоит за вопросом, Я думал, что это может помочь любому, кто заинтересован в работе над этим вопросом.

Ответ 1

ALT1 правильный. Учитывая, что вы хотите ограничить максимальное количество объектов (треугольников) в node, вам нужно будет разделить узлы, которые будут содержать много треугольников. Это неизбежно приводит к наличию единого треугольника в нескольких узлах, если вы не хотите подразделять треугольники так, чтобы они идеально соответствовали точкам октауза (что зависит от вашего приложения, я бы вообще не рекомендовал этого и, например, для raytracing, это, как правило, не выполняется).

Как контрпример, представьте себе ALT2, содержащую подробную модель сэнтфордского кролика, стоящего на большом треугольнике. Большой треугольник предотвратит разбиение корня node на подносы, и, таким образом, ваш октет будет таким же хорошим, как если бы у вас не было octree.

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

Ответ 2

Это больше относится к quadtrees, с которыми я больше знаком, но это 2D-эквивалент октета; поэтому он может быть применим.

Общие подходы к вставке: каждый внутренний node квадранта имеет емкость, которая является максимальным числом "объектов", которые может иметь квадрант квадранта. Если вы достигнете емкости, вы разделите ее, а затем вставьте все "объекты" в соответствующий дочерний квадрант. У вас также будет точка, в которой вы подразделяете и один или несколько ваших "объектов" оседлают несколько дочерних квадрантов; будьте осторожны в этом случае при вставке/запросе. Как правило, емкость node выбирается либо для более быстрой вставки, либо для запроса.

Итак, учитывая это, я не вижу ничего плохого в изображении ALT2, которое вы представляете. Но мое предположение о том, почему вы всегда видите изображение ALT1, - это подход по умолчанию, когда вставка в незанятую ячейку должна быть разделена, а затем вставлена.