Каков правильный подход для нарезки 3D-сетки? Сетка - это все закрытые поверхности, а срезы должны быть двоичными изображениями того, что внутри сетки. Так, например, сетка, представляющая изображение сферы и среза, представляет собой заполненные круги.
Я ищу библиотеку программного обеспечения или алгоритм, который я могу интегрировать в свой текущий проект на С++.
Моя библиотека игр с открытым исходным кодом содержит реализацию сетки. Он работает с Irrlicht api, но может быть переписан для использования другого API с небольшими усилиями. Вы можете использовать код в соответствии с условиями лицензии BSD или учиться у него реализовать свое собственное.
См. MeshTools:: splitMeshZ в этом файле для реализации срединной сетки.
Если вы просто хотите знать алгоритм, вот описание высокого уровня того, что я сделал:
Первоначально я думал о том, чтобы использовать ограничивающий прямоугольник по оси, чтобы указать, где вырезать сетку. Это было проблематично, потому что оно вводило множество особых случаев. Например, край, который пересекает угол поля, может быть разбит на три части, а не на два.
Используя плоскость, чтобы вырезать сетку только в левую сетку, а правая сетка уменьшает количество особых случаев, потому что ребро находится либо с одной стороны плоскости, либо с другой, или пересекает плоскость и так рубится в ровно две части.
Любая желаемая конфигурация разрезов может быть выполнена просто путем однократного разрезания, взятия одной из полученных сеток и резки ее снова в другом месте и т.д. В частности, в случае, который вы описываете в этом разделе, круг может быть вырезан из сферы, вырезая одну половину сферы, слегка сдвигая плоскость и отрезая другую половину, оставляя только тонкую полосу. (Вы не можете разрезать сетку до буквально никакой глубины с кодом, который я написал, но вы могли бы сократить сетку до того, что вы установили порог равенства с плавающей запятой. Я думаю, что я произвольно выбрал в моем коде 0,001).
Используя подобную логику, любой желаемый угол плоскости резки может быть достигнут с использованием фиксированной плоскости; вам просто нужно преобразовать сетку, чтобы повернуть ее относительно фиксированной плоскости резки, а затем преобразовать результат назад. (Для моей игры мне нужны только разрезы, перпендикулярные плоскости XY, поэтому для простоты я разрешаю только значение Z среза и предполагаю, что разрез находится в этом положении Z.)
ОК, теперь, когда мы упростили проблему, алгоритм не так уж плох:
Исходное условие: у вас есть плоскость резания. У вас есть набор исходных треугольников. У вас есть два набора множеств полигонов (а не треугольники, квадраты могут быть сгенерированы путем разрезания треугольника). Два набора назначений называются Left и Right.
Процесс: Итерация над тремя точками треугольника. Подсчитайте количество точек, которые меньше плоскости резки. Я назову их меньше, чем плоскость резания слева, и те, которые больше, чем плоскость резания вправо. Есть только несколько случаев:
Две точки - Left, одна точка - Right. Если вы держите край треугольника и разрезаете его по двум другим краям, вы остаетесь на трапеции. Поместите квадрат в левый набор, состоящий из двух точек в вашей руке, плюс две точки, которые пересекают разрез. Поместите треугольник в нужное множество (зеркальное изображение выше).
Закончив, поверните квадрики в треугольники, добавив ссылку через самую короткую часть.
Что это. Это основной алгоритм. Фактический код обрабатывает еще несколько случаев, например, если край точно равен разрезу, что, если треугольник находится точно на краю, не добавляйте вырожденные многоугольники (например, точку без тела) и т.д.
Разное. проблемы (все они связаны с кодом):
Не слишком усложняйте математику для LERP'а, где край пересекает плоскость резания. Он не нуждается в полной линейной интерполяции, на самом деле это просто Highschool Algebra II: выше по прогону, раз соотношение
Предпочтительно кэшировать созданные (LERP) точки, чтобы треугольники, которые разделяли вершины в неразрезанной сетке, будут совместно использовать соответствующие новые вершины в разрезанной сетке.
Если вы собираетесь сохранить общий доступ к вершинам и используете буферы с треугольными индексами, вы, к сожалению, еще не знаете индекс, когда сначала создаете фигуры, которые будут помещены в левые и правые наборы. Я использую класс под названием "ВозможныйVertex" для представления индекса будущего треугольника.
Если вы собираетесь отображать сетку, имеет значение порядок обмотки. Тщательная мысль о том, как вы его кодируете, может гарантировать, что полученные полигоны используют тот же порядок намотки, что и треугольники, из которых они были получены. Это становится особенно сложным при триангуляции квадроциклов. Я не могу запомнить детали, но все это связано с связанным кодом.
Для моей игры я хотел создать плоскую ленту, соединяющую две срезанные сетки. Поэтому splitMeshZ приводит к 3 сеткам, а не только к двум. Вы можете использовать среднюю сетку или просто игнорировать ее.
Я изложил алгоритм вычисления пересечений плоскостных томов в этом ответе. Реализация на Java предоставляется.
Проект в разрезе 3D-сетки (с исходным кодом на С++):
http://www.dainf.ct.utfpr.edu.br/~rminetto/projects/slicing/
Я предполагаю, что вы говорите о треугольных сетках?
Какой "правильный" подход сильно зависит от специфики вашего прецедента.
Подход OpenGL, предложенный Джерри, может сработать для вас.
Другим подходом было бы явное вычисление разрезов. Вы могли бы с этим CGAL. Более конкретно, с его 3D-ядром. Он имеет function, который может вычислять пересечения между всеми типами примитивов, включая плоскость и треугольник. С помощью этой функции вы можете точно вычислить контур пересечения и отобразить его в изображении. - Таким образом, вы не будете зависеть от OpenGL, а от CGAL.
Это будет быстрее (для себя, а не время работы), если вы его реализуете самостоятельно: это простые шаги, которые вам нужно выполнить:
1-Извлеките все треугольники сетки
2 - для каждого треугольника
2-1- проверить, находится ли какая-либо из треугольных точек на плоскости среза,
2-2- если нет, то для каждого из трех его краев найдите пересечение с вашей плоскостью среза (если оно есть). Вы должны либо иметь 2 из них, пересекающихся с плоскостью, либо ни один.
2-2-1 Если 2 ребра пересекаются с плоскостью, вы добавляете линию между этими двумя точками на плоскости.