логические операции над сетками

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

Примеры изображений: http://www.rhino3d.com/4/help/Commands/Booleans.htm

Я думаю об этом как Конструктивно-Сплошная Геометрия (CSG). Надеюсь, вы можете найти помощь здесь.

http://www.alsprogrammingresource.com/csg.html

http://createuniverses.blogspot.com/2009/09/qtcsg-constructive-solid-geometry.html

http://www.nigels.com/research/

Также поиск Google для Конструктивной Твердой Геометрии как начало.

НТН

Я думаю, что мы можем разобраться, если мы просто подумаем об этом.

Очевидно, вы захотите создать грани (треугольники), где две геометрии пересекаются. Тогда у вас останется три сетки: только что пересеченное вами пересечение, геометрия 1 и геометрия 2.

Затем просто удалите то, что вам не нужно!

• BooleanDifference: удалить изолированную деталь и геометрию 2.
• BooleanIntersection: удалить геометрию 1 и 2, оставив изолированную часть
• BooleanUnion: объединить геометрии 1 и 2 и удалить изолированную деталь (убедитесь, что геометрии 1 и 2 объединены в твердую геометрию)
• BooleanSplit: отделить геометрию 1, геометрию 2 и продублировать изолированную часть (прикрепить одну к геометрии 1, а другую к геометрии 2)

Я думаю, что это покрывает, а? Трудная часть, очевидно, будет создавать грани пересечения. Для этого, переберите каждую грань одного и проверьте, является ли эта грань частью другой; если он полностью внутри, то скопируйте грань как часть сетки пересечения. Если он частично внутри, то вам нужно разбить треугольник вдоль линии пересечения; Я думаю, что DirectX и OpenGL будут иметь вспомогательные функции для этого, или это просто какая-то трехмерная математика (векторы). Я узнал подобные вещи в Calculus 3 (или это было 2?), Но если у вас нет подсказки, возможно, спросите на math.stackexchange.com . И тогда, конечно, если лицо снаружи, ничего не делать. После перебора всех граней обеих сеток у вас останется сетка пересечения.

Если вы имеете дело с полигональными моделями, вам, возможно, придется иметь дело с немногообразной геометрией, что означает, что вопрос о том, что находится "внутри", а что "снаружи", не определен. Сложно выполнить логическую операцию, если вы не знаете, есть ли у вас 0 или 1.

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

Стоит отметить, что большинство ваших операций могут быть представлены отрицанием и объединением, где отрицание некоторой геометрии - это просто геометрия с перевернутыми нормалями. Так что, если вы можете получить правильное объединение, тогда другие операции должны просто следовать:

• пересечение (A, B): =! объединение (! A,! B)
• вычесть (A и B): =! union (! A, B)

У Сандера есть несколько неплохих постов в блоге, в которых обсуждаются реализации CSG: http://sandervanrossen.blogspot.com/search/label/CSG

Это довольно сложная тема, по крайней мере, если вы хотите сделать это надежно (с плавающей точкой вызывает некоторые серьезные трудности).

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

http://homes.cs.washington.edu/~gilbo/repofiles/booleans2009.pdf

http://openflipper.org/uploads/media/campen_2010_eg_02.pdf