Основы Constructive Solid Geometry (CSG) и ее реализация в OpenGL

Одним из широко распространенных инструментов в моделировании (конструировании) сложных объектов является Constructive Solid Geometry, а именно построение новых объектов путем операций объединения, пересечение и вычитания более простых объектов (при этом эти объекты считаются сплошными, а не только границей).

Рис 1. Пример использование CSG.

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

Рис 2. Представление CSG-объекта в виде дерева.

Крайне легко и красиво CSG реализуется в трассировке лучей - для этого необходимо лишь изменить процедуру нахождения пересечения луча с объектом, чтобы она возвращала отсортированный список ВСЕХ пересечений луча с данным объектом.

Тогда, если у нас есть два объекта А и В и есть некоторая операция * (в качестве нее может выступать любая из следующих операций - объединение, пересечение и вычитание), тогда для получения пересечения заданного луча R с A*B достаточно найти пересечение луча с каждым из объектов А и В (которые будут представлять собой упорядоченные списки отрезков) и применить операцию * к ним.

Т.е. все сводится просто к реализации основных операций над упорядоченными списками отрезков на прямой - довольно легко решаемой одномерной задаче. Для метода трассировки лучей CSG работает всегда, причем довольно эффективно.

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

Однако во многих случаях полигональное представление результата и не требуется - достаточно лишь построить результирующий объект средствами OpenGL.

В этом случае можно все операции проводить в пространстве картинной плоскости (image space) и довольно быстро получать требуемый результат.

Далее мы рассмотрим простейшие способы реализации основных операций CSG средствами OpenGL для выпуклых объектов

Операция объединения двух объектов

Для построения результата объединения двух объектов А и В достаточно просто вывести их средствами OpenGL в произвольном порядке с включенным тестом глубины (используя режимы GL_LESS или GL_LEQUAL).

Построение части объекта А, содержащейся внутри выпуклого объекта В

Пусть у нас есть два выпуклых объекта - А и В - и мы хотим средствами OpenGL построить изображение той части объекта А, которая содержится внутри объекта В.

В силу выпуклости объекта В нам достаточно только проверить фрагменты лицевых граней объекта А на попадание между лицевыми и нелицевыми гранями объекта В.

Рис 3. Часть границы объекта А, лежащая внутри объекта В.

Одним из способов построение заключается в том, что сначала все лицевые грани объекта А выводятся в буфер глубины (буфер цвета выключается).

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

Рис 4. Результат вывод лицевых граней объекта В.

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

Рис 5. Результат вывода нелицевых граней объекта В.

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

Рис 6.

Таким образом, по окончанию данной процедуры у нас в буфере трафарета ненулевыми значениями будут помечены все фрагменты А, содержащиеся внутри B.

Осталось только вывести соответствующие значения цвета - для этого разрешается запись в буфер цвета и повторно выводится объект А с отсечением по буферу трафарета (отсекаются нулевые значения в буфере трафарета).

Для вывода лицевых/нелицевых граней удобно воспользоваться функция glCullFace, позволяющей автоматически отбрасывать грани заданного типа.

Ниже приводится исходный код на С++ функции, осуществляющей построение части объекта А, лежащей внутри объекта B. Обратите внимание, что в данном случае нам достаточно выпуклости только у объекта B.

Построение пересечения двух выпуклых объектов

Задача построения пересечения двух объектов А и В фактически заключается в построении частей лицевых граней объекта А, содержащихся в В, и частей лицевых граней объекта В, содержащихся в А.

Таким образом данную задачу можно свести к двухкратному применению уже рассмотренной нами функции drawFirstInSecond за одним исключением.

Дело в том, что после первого вызова (построение части А содержащейся в В) в буфере глубины останутся значения глубины, соответствующие лицевым граням объекта А. И если не принять дополнительных мер, то вызов drawFirstInSecond ( B, A ) отработает не верно.

Поэтому после вызова drawFirstInSecond ( A, B ) необходимо в "принудительном порядке" прописать в буфер глубины значения глубины для лицевых граней объекта B. Для этого достаточно просто отключить тест трафарета, тест глубины установить в GL_ALWAYS и вывести лицевые грани объекта B.

Для этого можно ввести отдельную функцию fixDepth, приводимую ниже.

В результате мы приходим к следующей процедуре построения пересечения двух выпуклых объектов:

Построение разности двух выпуклых объектов

Если у нас есть два выпуклых объекта А и В, то как можно легко заметить, разность В-A будет состоять из двух типов фрагментов - фрагментов лицевых граней объекта В, не лежащих в А, и фрагментов нелицевых граней объекта А, лежащих в В.

Рис. 7. Разность двух объектов А и В.

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

Ниже приводится исходный код измененной функции drawFirstInSecond.

В результате мы приходим к следующему коду, для построения разности двух выпуклых объектов.

Алгоритм SCS

Одним из удобных алгоритмов построения CSG-объектов является SCS-алгоритм. Он работает только с выпуклыми примитивами и использует так называемую нормализованную форму для CSG-выражения - итоговый объект представляется как объединение нескольких частичных объектов, каждый из которых получается путем пересечения и/или вычитания примитивов.

Можно показать, что любое CSG-выражение может быть приведено в нормализованную форму.

Поскольку для объединения частичных объектов можно просто воспользоваться стандартным z-буфером, то фактически задача сводится к нахождению частичных объектов.

Процесс нахождения частичного объекта сводится к следующим шагам:

1. Найти лицевую поверхность всех пересекаемых примитивов. Она удовлетворяет следующим условиям - она лежит дальше всех лицевых поверхностей, но ближе всех нелицевых поверхностей.

Данный шаг легко реализуется при помощи буфера трафарета, как рассматривалось ранее.

2. Вычесть из полученного объекта все вычитаемые примитивы. Для этого отдельно выводятся лицевые грани вычитаемого примитива, а затем его нелицевые грани. Для тех пикселов, в которых лицевые грани оказались ближе, а нелицевые - дальше, происходит замена значений в буфере глубины на значения глубины нелицевых граней.

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

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

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

Это связано с том, что для данного метода порядок в котором вычитаются примитивы имеет значение. Т.е. если мы из примитива X вычитаем примитивы A и B, то результаты операций X-А-В и X-В-А могут отличаться.

Для борьбы с этим с нашем примере достаточно просто два раза выесть один из объектов - до и после другого (X-А-В-А). Тогда поскольку в получившееся выражение войдет как случай, когда мы сперва вычитаем первый объект, а потом второй, так и случай, когда сначала вычитается второй объект, а потом - первый.

На следующих двух рисунках приведены неправильное (рис. 8) и правильное (рис. 9) построение разности.

Рис 8. Изображение, получаемое по формуле X-А-В

Рис 9. Изображение, полученное по формуле X-А-В-A

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

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

Библиотека OpenCSG

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

Библиотека OpenCSG использует несколько разных алгоритмов (включая и SCS) и позволяет строить изображения сложных CSG-объектов средствами OpenGL в реальном времени.

На сайте библиотеки www.opencsg.org можно скачать как саму библиотеку, так и ряд примеров и необходимую документацию.

Исходный код (с примерами для двух объектов и примеров вычитания по SCS-алгоритму) можно скачать здесь.

Откомпилированную версию для M$ Windoze можно скачать здесь.

Откомпилированную версию для Linux можно скачать здесь.

Откомпилированную версию для Mac OS X можно скачать здесь.

В работе над статьей был использован пример с www.opengl.org.