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

Немного предыстории дизайнерских решений... Я разработал структуру октодерева, которая может хранить точки. Я решил ограничить рекурсию «поколений» на основе определенного базового размера вокселя. Дочерние узлы создаются только тогда, когда к этому узлу добавляются точки. Это не динамическое графическое приложение — это октодерево и объекты в нем статичны, поэтому предварительная обработка для повышения производительности не вызывает беспокойства.

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

Альтернативный вариант 1: хранить треугольники в каждом концевом узле, который он пересекает. Альтернативный вариант 2: хранить треугольники в наименьшем узле, который может содержать каждую вершину. .

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

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

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

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

Обновление: Четыре года спустя Alt2 оказался проще в реализации, но очень медленным, потому что большие треугольники, хранящиеся на более высоких уровнях октодерева, проверялись при каждом обходе октодерева — в моем случае это означало от сотен до тысяч ненужных тесты. В итоге я пересмотрел свой код, чтобы использовать вариант R*-Tree, который был легко реализовать и значительно быстрее.


c++ data-structures spatial-index octree
person Phlucious    schedule 29.04.2014    source источник
comment
+1 Я нахожу этот вопрос интересным и хорошо представленным (и совершенно не знаю ответа, просто говорю заранее). Правильно ли предположить, что тег C++ является вашим предпочтением жизнеспособным предложениям схемы адресации, которые будут представлены? Если это так, вы можете уточнить это в вопросе, хотя я предполагаю, что кто-то может найти ответ на Форте, и вы, вероятно, с легкостью его проанализируете. Как написано, это будет хорошо независимо от языкового тега.   -  person WhozCraig    schedule 29.04.2014
comment
Причина для Alt1 - это подразумеваемая точность. Тесты октодерева aabb выполняются быстрее, чем тесты треугольника. Таким образом, более мелкозернистое октодерево с несколькими регистрациями одной и той же сетки позволит выполнять более быстрые запросы. Как в log n по сравнению с n, с точки зрения сложности. Но с другой стороны, он более требователен к памяти, чем alt2. Кроме того, для нестатической геометрии обновления стоят дороже, чем в alt2. В целом выбор того, какое подразделение вы выберете, зависит от типа сцены, с которой вы имеете дело. Количество объектов и изменчивость играют равную роль (и память).   -  person meandbug    schedule 29.04.2014
comment
@WhozCraig: флаг C++ был включен только потому, что это мой язык реализации, и любой пример кода будет лучше всего понят на этом языке. Вы правы, что сам вопрос не зависит от языка.   -  person Phlucious    schedule 29.04.2014
comment
@meandbug: Спасибо за информацию. Поскольку моя среда статична (точнее, данные LiDAR облака точек), обновления сцены не являются ограничением дизайна, но приятно знать, что это соображение влияет на широко распространенное предпочтение alt1. Большинство статей Octree, которые я видел, связаны с играми.   -  person Phlucious    schedule 29.04.2014
comment
@ Phlucious, почему бы тогда не пойти на K-D-Tree? Это кажется более оптимальным для такого приложения. en.wikipedia.org/wiki/K-d_tree   -  person meandbug    schedule 30.04.2014
comment
@meandbug: Хороший вопрос. Моя первоначальная задача требовала некоторых вычислений на основе вокселей, для которых требовалась регулярная сетка, поэтому я наложил на нее октодерево, чтобы ускорить алгоритмы поиска и трассировки лучей. Мне также просто понравилась простота октодерева.   -  person Phlucious    schedule 30.04.2014
comment
Вы упомянули, что a R*-Tree variant ... was easy to implement and substantially faster. Меня интересует использование памяти. Как R*-Tree по сравнению с Octree в отношении использования памяти? Спасибо =)   -  person user3405291    schedule 22.06.2020
comment
@user3405291 user3405291 Я реализовал разреженное октодерево, создавая экземпляры узлов только тогда, когда они были необходимы, поэтому я не заметил значительных изменений в использовании памяти между ними. Мои данные также статичны, поэтому я могу пространственно оптимизировать R*-дерево так, как это не удалось бы сделать в динамической среде. Я не могу говорить об общем случае.   -  person Phlucious    schedule 23.06.2020

Ответы (3)


arrow_upward
5
arrow_downward

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

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

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

person the swine    schedule 28.05.2014
comment
Спасибо за интересный ответ. В вашем сценарии все листовые узлы находятся на одном уровне глубины? Если это так, то мне кажется, что алгоритм трассировки лучей все равно захочет пройти каждый уровень, чтобы пропустить пустые высокоуровневые узлы (и их потомки) в дереве. Если нет, то разве вам не пришлось бы проходить каждый уровень, независимо от этого? - person Phlucious; 28.05.2014
comment
@Phlucious они могут быть на разных уровнях, иначе октодерево превратилось бы в обычную сетку, и можно было бы использовать растеризацию 3DDDA для обхода узлов. Что касается посещения вышестоящих узлов, то это не совсем так, вы всегда знаете, с какой стороны узла выходит луч, и вы можете подготовить указатели, ведущие к соседнему узлу, разделяющему данную сторону (инициализировать указатели один раз, использовать много раз). Затем структура октодерева используется только для поиска начала луча, а затем весь обход представляет собой простой переход к соседнему. - person the swine; 28.05.2014
comment
Имеет смысл. При хранении листовых узлов на нескольких уровнях, как именно вы определяете листовые узлы, пересекаемые фигурой, когда вершины находятся на расстоянии нескольких узлов друг от друга (например, в вашем примере с кроликом на большом треугольнике)? Я не понимаю, как большой узел будет хранить указатель на своего западного соседа, когда есть два меньших западных узла. - person Phlucious; 29.05.2014
comment
@Phlucious Пересечение узла и треугольника легко сделать с помощью теоремы о разделяющей оси (SAT). Для узлов, выровненных по оси, это легко реализовать и довольно быстро. Что касается западного указателя, то он либо хранит указатель на западный узел на том же уровне, и после перехода туда находится следующий листовой узел, либо, альтернативно, он хранит растровое изображение указателей, сопоставленных с его стенкой, и в зависимости от того, какой пиксель луч стреляет, обход продолжается. - person the swine; 29.05.2014

arrow_upward
1
arrow_downward

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

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

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

person Justin    schedule 29.04.2014

arrow_upward
0
arrow_downward

У меня есть простая реализация октодерева С++. Реализация подразделяет узел на восемь дочерних элементов, как если бы в этом конкретном узле присутствовало более одной точки. Теперь я хочу использовать то же октодерево для данных поверхностной сетки. Я имею в виду, что хочу хранить полную информацию о геометрии в структуре данных октодерева. В дополнение к этому у меня есть информация о треугольнике, которую я извлек из файла .stl.

Мой вопрос почти аналогичен тому, что задал Phlucious несколько лет назад, но я не понял всего обсуждения его вопроса.

person Aravindh SK    schedule 28.05.2020