Конструктивная сетка стереометрии
Если я создаю форму с помощью конструктивных методов стереометрии, как я могу создать каркасную сетку для рендеринга? Я знаю, что алгоритмы для того, чтобы непосредственно представить формы CSG, но я хочу преобразовать его в каркасную сетку только однажды так, чтобы я мог представлять его "обычно"
Добавить немного больше детали. Учитывая описание формы, такой как "Куб здесь, пересечение со сферой здесь, вычитают цилиндр здесь", я хочу быть в состоянии вычислить сетку полигона.
5 ответов
Здесь есть некоторые ссылки Google Scholar, которые могут быть полезны.
Из того, что я могу сказать об абстракциях, основная идея заключается в генерации облака точек на основе объемных данных, доступных в модели CSG, а затем использовании более распространенных алгоритмов для генерации сетки граней в 3D, чтобы соответствовать этому облаку точек.
Правка: Делая некоторые дальнейшие исследования, этот вид операции называется "преобразованием из CSG в B-Rep (граничное представление)". Исследования этой строки привели к полезному PDF:
http://www.scielo.br/pdf/jbsmse/v29n4/a01v29n4.pdf
И, для дополнительной информации, ключевой алгоритм называется "Marching Cubes Algorithm". По сути, модель CSG используется для создания объемной модели объекта с вокселями, а затем алгоритм Marching Cubes используется для создания трехмерной сетки из данных вокселей
.Можно попробовать триангулировать (тетраэдрировать) каждый примитив, затем выполнить булевые операции над тетраэдрической сеткой, что "проще", так как вам нужно только беспокоиться о тетраэдрических операциях. Затем вы можете выполнить извлечение границы, чтобы получить B-реп. Так как вы знаете формы ваших примитивов аналитически, вы можете построить пользовательские тетраэдрические операции ваших примитивов в соответствии с вашими потребностями, вместо того, чтобы полагаться на библиотеку генерации сетки.
Например, предположим, что ваш объект представляет собой объединение куба и цилиндра, и предположим, что вы имеете тетраэдрические операции обоих объектов. Для того, чтобы вычислить граничное представление результирующего объекта, вы сначала пометите все граничные грани тетраэдры каждого примитивного объекта. Затем выполняется операция объединения: если две тетраэдры разобщены, то ничего делать не надо; обе тетраэдры должны существовать в результирующем многограннике. Если они пересекаются, то есть ряд случаев (возможно, порядка дюжины или около того), которые необходимо обработать. В каждом из этих случаев объем двух тетраэдров должен быть перетриангулирован с учетом ограничений по поверхности. Это облегчается тем, что вам нужно беспокоиться только о тетраэдре, в отличие от более сложных форм. В процессе работы необходимо поддерживать граничные фасетные метки таким образом, чтобы в конечной коллекции тетраэдр можно было извлечь граничные фасетные метки и сформировать треугольную сетку поверхности
.Существуют два основных подхода. Если у вас есть набор полигональных форм, то для каждой из них можно создать дерево BSP, а затем объединить деревья BSP. Из Википедии,
1990 Нейлор, Аманатиды и Тибо. предоставить алгоритм слияния двух bsp-деревья для формирования новой bsp-деревья из два оригинальных дерева. Это обеспечивает многие преимущества, в том числе: сочетание движущиеся объекты в лице BSP деревья со статической обстановкой (также представленный деревом BSP), очень эффективные операции CSG на многогранниках, точное обнаружение столкновений в O(log n * журнал n), и правильный заказ прозрачных поверхностей, содержащихся в двух взаимопроникающие объекты (был используется для рентгеновского эффекта зрения).
Статья находится здесь Слияние деревьев BSP дает операции полиэдрического множества .
Альтернативно каждая форма может быть представлена как функция над пространством (например, подписанное расстояние до поверхности). До тех пор, пока поверхность определяется как где функция равна нулю, функции затем могут быть объединены с помощью (MIN == пересечение), (MAX == объединение) и (NEGATION = нет) операторов, имитирующих операции множества. Результирующая поверхность затем может быть извлечена как позиции, где комбинированная функция равна нулю, используя такую технику, как "Марширующие кубы". Также могут быть использованы лучшие методы извлечения поверхности, такие как Dual Marching Cubes или Dual Contouring. Это, конечно, приведёт к дискретному приближению истинной поверхности CSG. Я предлагаю использовать Dual Contouring , потому что он способен восстанавливать острые черты, такие как углы кубов .
Кажется, эти библиотеки делают то, что вы хотите:
www.solidgraphics.com/SolidKit / carve-csg.com/ { {1}} gts.sourceforge.net/
См. также "Constructive Solid Geometry for Triangulated Polyhedra" (1990) Philip M. Hubbard doi:10.1.1.34.9374