Рассмотрены основные ошибки при построении CSG-моделей алгоритмом, работающим с полигональными объектами, а также предложены методы их решения.

Ключевые слова: компьютерная графика, пересечение многогранников, трёхмерная геометрия, Constructive Solid Geometry.

Введение.

Данная статья является дополнением к статье “Булевы операции на трёхмерных моделях в компьютерной графике” [1]. При реализации CSG-моделей алгоритмом, работающим с полигональными объектами [2], часто не учитываются частные случаи, которые создают ряд определённых сложностей при разработке программ, используемых для визуализации данных моделей.

Решение данной проблемы является важным для людей, работающих с компьютерной графикой, в частности, в области трёхмерного моделирования.

Алгоритмы построения CSG-моделей.

Существуют следующие алгоритмы построения CSG-моделей: работающие в пространстве изображения и работающие в пространстве объекта. Вторые являются более гибкими, к ним принадлежат алгоритмы, работающие с полигональными моделями, представляющие для нас интерес.

Алгоритм, работающий с полигональными объектами, обычно разбивают на три основных этапа [1]:

1. нахождение линии пересечения двух заданных полигональных примитивов;
2. разбиение каждого треугольника, которыми образован данный примитив, на группы треугольников, таким образом, чтобы каждый из отрезков являлся стороной двух смежных треугольников;
3. решение задачи пространственной локализации треугольника одного примитива, относительно другого.

Ошибки впервом этапе.

Для поиска пересечения двух примитивов (рассматриваем треугольники) в пространстве удобно использовать алгоритм [3], однако, данный алгоритм не учитывает случаи, когда два примитива лежат в одной плоскости, притом, не параллельной ни одной из плоскостей проекции. Определить принадлежность двух треугольников одной плоскости достаточно просто при реализации алгоритма [3]: если расстояния и (рис. 1).

Рис. 1. Геометрическое представление алгоритма [3]

Решение. Если же два треугольника лежат в одной плоскости, то задача разбиения треугольников по линии пересечения будет решаться совершенно иначе. Два треугольника лежат в одной плоскости (рис. 2), тогда разбиение данных двух примитивов будет следующим (рис. 3).

Рис. 2. Пересечение двух треугольников в одной плоскости

Рис. 3. Разбиение двух пересекающихся треугольников в одной плоскости на непересекающиеся примитивы

Ошибки во третьем этапе.

Самым удобным с точки зрения реализации и скорости выполнения является метод бросания лучей (ray-casting) [4]. Проблем с выбором точки испускания луча не возникает, однако возникает проблема с подсчётом количества пересечений выпущенного луча с примитивами второго объекта.

Рассмотрим основные случаи, которые могут возникнуть:

1) луч пересёк примитив, не через его сторону или же вершину;

2) луч пересёк примитив через его сторону;

3) луч пересёк примитив через его вершину.

Если в первом случае проблем не возникает, то два других случая заставляют задуматься, ведь, так как второй объект является замкнутым примитивом, то стороны всех его примитивов, а соответственно и вершин, соприкасаются как минимум с тремя другими. Именно поэтому возникает сложность в учёте истинного количества пересечений луча и примитивов другого объекта.

Решение в данном случае достаточно тривиальное: каждую вершину и сторону считать отдельным объектом и при пересечении учитывать только один раз.

Литература:

1. Смелкова Е. А., Таразанов А. М., Меркулов Д. В., Иксарица Н. И., Погорелов Д. А., Булевы операции на трёхмерных моделях в компьютерной графике, Аллея Науки, Т. 1, № 1 (17), с. 860–864, 2018.
2. R. Banerjee and J. Rossignac, Topologically exact evaluation of polyhedra defined in CSG with loose primitives, to appear in Computers Graphics Forum, Vol. 15, No. 4, pp. 205–217, 1996
3. R. Banerjee and J. Rossignac, Topologically exact evaluation of polyhedra defined in CSG with loose primitives, to appear in Computers Graphics Forum, Vol. 15, No. 4, pp. 205–217, 1996
4. ZAJÍČEK, Petr Acceleration of Ray-Casting for CSG scenes. Master thesis, MFF UK, 2012.