Как объединить многогранники?

Question

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

Также после этого я буду реализовывать метод вычитания и пересечения.

Я помогаю этой библиотеке с открытым исходным кодом. Исходный код: https://bitbucket.org/Clearspan/geometry-class-library/src/34a2ab5031879d051abb855a828368e397b4f5b6/GeometryClassLibrary/Solids/Polyhedron.cs?at=master

Answer 1

Существует достаточно обширная литература по этому вопросу. Посмотрите, например , оптимальный алгоритм для пересечения трехмерных выпуклых многогранников.

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

Вместо того, чтобы рассматривать грани как точки и линии, будет проще рассматривать их как плоскости. Вы можете легко найти пересечение плоскостей.

Вы спрашиваете, есть ли простой алгоритм. Ответ, вероятно, нет. Есть алгоритмы, но есть много краевых случаев, которые нужно учитывать: что, если два многогранника встречаются в одной точке? Есть также проблемы эффективности. Наивный подход будет пересекать каждое лицо с каждым другим лицом. Составляем алгоритм O(n^2). Это будет плохо масштабироваться, если многогранники имеют сотни или тысячи граней, что довольно часто встречается при моделировании.

Answer 2

Это известная проблема исследования в компьютерной графике для нахождения булевых операций над полигональными сетками. Вы можете взглянуть на некоторые связанные документы по адресу:

http://arxiv.org/pdf/1308.4434.pdf

http://www.tandfonline.com/doi/abs/10.3722/cadaps.2010.405-415?journalCode=tcad20.

(Вы можете найти более старые работы, взглянув на цитируемые статьи)

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