Если я построю форму с использованием методов конструктивной сплошной геометрии, как я могу построить сетку каркаса для рендеринга? Я знаю алгоритмы прямого визуализации форм CSG, но я хочу преобразовать их в сетку wireframe только один раз, чтобы я мог отображать его "нормально"
Чтобы добавить немного больше деталей. Учитывая описание формы, такой как "Куб здесь, пересечение с сферой здесь, вычитаем цилиндр здесь" Я хочу иметь возможность вычислить многоугольную сетку.
Существует два основных подхода. Если у вас есть множество многоугольных фигур, можно создать дерево BSP для каждой фигуры, тогда деревья BSP могут быть объединены. Из Википедии,
1990 Naylor, Amanatides и Thibault предоставить алгоритм для слияния двух bsp деревья, чтобы сформировать новое дерево bsp из два оригинальных дерева. Это обеспечивает многие преимущества, включая: объединение движущиеся объекты, представленные BSP деревья со статической средой (также представленное деревом BSP), очень эффективные операции CSG на многогранниках, точное обнаружение коллизий в O (log n * log n) и правильное упорядочение прозрачных поверхностей, содержащихся в двух взаимопроникающие объекты ( используется для эффекта рентгеновского зрения).
Статья найдена здесь Слияние деревьев BSP дает многогранные заданные операции.
В качестве альтернативы, каждая форма может быть представлена как функция над пространством (например, расстояние до знака до поверхности). Пока поверхность определяется как функция, равная нулю, функции затем могут быть объединены с использованием (MIN ==) пересечения), (MAX == union) и (NEGATION = not) операторов для имитации заданных операций. Полученная поверхность затем может быть извлечена в виде позиций, где объединенная функция равна нулю, используя технику, подобную Marching Cubes. Также могут быть использованы лучшие методы экстракции поверхности, такие как Dual Marching Cubes или Dual Contouring. Это, конечно же, приведет к дискретному приближению истинной поверхности CSG. Я предлагаю использовать Dual Contouring, поскольку он способен восстанавливать острые объекты, такие как углы кубов.
Кажется, что эти библиотеки делают то, что вы хотите:
www.solidgraphics.com/SolidKit/ carve-csg.com/ gts.sourceforge.net/
См. также "Конструктивная сплошная геометрия для триангулированных многогранников" (1990) Филипп М. Хаббард doi: 10.1.1.34.9374
Здесь есть некоторые ссылки Google Scholar, которые могут быть полезны.
Из того, что я могу сказать о рефератах, основная идея состоит в том, чтобы создать облако точек из объемных данных, доступных в модели CSG, а затем использовать некоторые более распространенные алгоритмы для создания сетки граней в 3D, чтобы соответствовать этой точке облако.
Изменить: Выполняя некоторые дальнейшие исследования, этот вид операции называется "преобразование из CSG в B-Rep (граничное представление)". Поиски этой строки приводят к полезному PDF:
http://www.scielo.br/pdf/jbsmse/v29n4/a01v29n4.pdf
И для дополнительной информации ключевой алгоритм называется "" Маршевый алгоритм кубов "". По существу, модель CSG используется для создания объемной модели объекта с вокселями, а затем алгоритм Marching Cubes используется для создания 3D-сетки из данных воксела.
Вы можете попытаться triangulate (tetrahedralize) каждого примитива, а затем выполнить булевы операции на тетраэдрической сетке, что является "более простым", так как вам нужно только беспокоиться о работе тетраэдра-тетраэдра. Затем вы можете выполнить граничное извлечение, чтобы получить B-rep. Поскольку вы анализируете формы своих примитивов аналитически, вы можете создавать собственные тетраэдризации ваших примитивов в соответствии с вашими потребностями, а не полагаться на библиотеку генерации сетки.
Например, предположим, что ваш объект был объединением куба и цилиндра, и предположим, что у вас есть тетраэдризация обоих объектов. Чтобы вычислить граничное представление результирующего объекта, вы сначала назовите все граничные грани тетраэдров каждого примитивного объекта. Затем вы выполняете операцию объединения: если два тетраэдра не пересекаются, то ничего не нужно делать; оба тетраэдра должны существовать в полученном многограннике. Если они пересекаются, то существует ряд случаев (вероятно, порядка десятка или около того), которые нужно обрабатывать. В каждом из этих случаев объем двух тетраэдров должен быть повторно триангулирован таким образом, который учитывает поверхностные ограничения. Это несколько облегчается тем, что вам нужно только беспокоиться о тетраэдрах, а не о более сложных формах. Графические метки граней должны поддерживаться в процессе, так что в конечном наборе тетраэдров граничные грани могут быть извлечены, чтобы сформировать треугольную сетку поверхности.
Мне повезло с BRL-CAD-приложением MGED, где я могу построить выпуклый многогранник путем пересечения плоскостей с использованием CSG, а затем извлечь граничное представление, используя команду командной строки g-stl. Проверьте http://brlcad.org/ Malcolm
Если вы можете преобразовать введенные примитивы в полиэдральные сетки, тогда вы можете использовать логические подпрограммы libigl С++. Следующее вычисляет объединение сетки (VA, FA) и другой сетки (VB, FB):
igl::mesh_boolean(VA,FA,VB,FB,"union",VC,FC);
где VA является # ВА матрицей вершинных позиций, а FA является матрицей индексов треугольника #FA по 3 в VA и т.д. Техника, используемая в libigl, отличается от тех, которые упомянуты в ответе Джо. Все пары треугольников пересекаются друг с другом (с использованием пространственного ускорения), а затем полученные субтреугольники классифицируются как принадлежащие к выходной поверхности или нет.