GLU-1: Триангуляция многоугольников средствами GLU

Что такое GLU

Библиотека OpenGL Utility [html] [pdf] (сокращённо «GLU») является стандартным компонентом, поставляемым вместе с реализацией 3D API OpenGL. Как правило, доступна в составе ОС, поддерживающих OpenGL. Существуют открытые реализации (например, от SGI).

Библиотека включает ряд удобных функций для работы с текстурами, матрицами и геометрией. Последние включают в себя так называемый «тесселятор», выполняющий триангуляцию многоугольников, который можно использовать для отображения произвольных многоугольников в виде набора примитивов OpenGL, а также для булевских операций с полигональными множествами на плоскости.

Программа-пример

Проект MSVC2010 под названием GLUPoly на основе FreeGLUT содержит реализацию описанного ниже метода работы с GLU для отображения загружаемых из файлов многоугольников.

Управление. Стрелки перемещают камеру, +/- увеличивает/уменьшает изображение, home возвращает в начальную позицию, enter запрашивает с консоли имя файла на отображение. На старте автоматически открывается input.txt из текущей директории.

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

Многоугольники

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

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

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

Триангуляция

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

  • каждая точка из набора является вершиной хотя бы одного треугольника триангуляции;
  • любые два треугольника не имеют общих внутренних точек.

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

Пересечение отрезков

Для корректного выполнения триангуляции необходимо найти все точки пересечения контуров. Эту задачу можно решать по-разному, например, простым попарным перебором звеньев всех контуров, что даёт O(N^2) сложность (где N — количество всех звеньев). Современные библиотеки используют более эффективные алгоритмы, имеющие сложность O(N log N + K), где K — количество точек пересечения. Например, алгоритмы, основанные на принципе заметания плоскости прямой, возникшие как улучшенные аналоги O( (N + K) log N) алгоритма Бентли-Оттманна (сюда можно отнести алгоритм Чазелле-Эдельсбруннера [acm], основанный на трапецеидальном разбиении плоскости). Для разрешения вырожденных случаев (вроде пересечения в одной точке сразу нескольких контуров) могут применяться «возмущения» (perturbations; небольшие изменения) координат точек.

Метод витков

Метод витков определяет, какие из треугольников, полученных в процессе триангуляции, включить в вывод алгоритма. Для каждого треугольника определено «число витков» — сумма полных оборотов (оборот против часовой стрелки добавляет единицу, оборот по часовой стрелке вычитает единицу), которые сделает вокруг внутренности треугольника точка при обхождении всех контуров. Например, можно брать все треугольники, число витков которых не равно нулю или выбирать треугольники, число витков которых нечётно (таково было поведение GLU по умолчанию в версиях 1.0 и 1.1, реализация GLU 1.2 от Microsoft также по умолчанию использует это правило, во многих случаях оно позволяет не заботиться о правильности ориентации исходных контуров). Задавая разные критерии, можно выполнять булевские теоретико-множественные операции над многоугольниками (в замыкании).

Создание объекта тесселятора GLU

Для триангуляции многоугольника нужно создать объект GLUtesselator с помощью вызова функции gluNewTess. Когда объект станет не нужен, его следует удалить, передав функции gluDeleteTess. Можно триангулировать разные многоугольники в разных потоках исполнения, используя разные объекты GLUtesselator.

Настройка тесселятора

Тесселятор поддерживает три «свойства», которые можно установить функцией gluTessProperty.

  • GLU_TESS_WINDING_RULE — критерий выбора треугольников по числу витков, варианты значений:
    • GLU_TESS_WINDING_ODD нечётное число,
    • GLU_TESS_WINDING_NONZERO число витков не равно нулю,
    • GLU_TESS_WINDING_POSITIVE число витков положительно,
    • GLU_TESS_WINDING_NEGATIVE число витков отрицательно,
    • GLU_TESS_WINDING_ABS_GEQ_TWO модуль числа витков больше единицы.
  • GLU_TESS_BOUNDARY_ONLY — выбор режима: получать результат в виде наборов треугольников (GL_FALSE) или в виде контуров, описывающих выбранные в соответствии с критерием области (GL_TRUE).
  • GLU_TESS_TOLERANCE — допустимая относительная погрешность, в случае ненулевого значения GLU может удалять слишком близко друг от друга отстоящие точки в рамках указанной погрешности.

Получение результирующих примитивов

Для того, чтобы получить результирующие примитивы (будь то треугольники или ломаные), нужно зарегистрировать функции обратного вызова с помощью gluTessCallback:

  • GLU_TESS_BEGIN (_DATA) вызывается, когда начинается передача нового примитива, аналог glBegin;
  • GLU_TESS_VERTEX (_DATA) вызывается для передачи очередной вершины в виде указателя «vertexData», переданного в свою очередь тесселятору, аналог glVertexv;
  • GLU_TESS_END (_DATA) вызывается, когда примитив закончен, аналог glEnd;
  • GLU_TESS_COMBINE (_DATA) вызывается, когда необходимо породить новую вершину (найдена точка пересечения или удалены точки в соответствии с установленной допустимой погрешностью).

DATA-варианты позволяют передать колбеку дополнительный указатель «polygonData», и используются для привязки к конкретному объекту-получателю примитивов (что и сделано в примере).

Функция COMBINE нужна для того, чтобы дать пользователю возможность корректно «смешать» данные, прикреплённые к вершинам для порождения новых вершин (например, цвета и текстурные координаты) на основе четырёх исходных вершин. Минимальный пример этой функции дан в GLUPoly, более подробный пример здесь.

Процесс передачи контуров тесселятору

Для каждого отдельного многоугольника:
gluTessBeginPolygon (тесселятор, polygonData);

  для каждого контура:
  gluTessBeginContour (тесселятор);
    для каждой вершины контура:
    gluTessVertex (тесселятор, double координаты[3], vertexData);
  gluTessEndContour (тесселятор);
gluTessEndPolygon (тесселятор);

Третью координату вершины можно устанавливать в 0, триангуляция строится в проекции по направлению нормали, устанавливаемой функцией gluTessNormal. По умолчанию нормаль равна (0, 0, 1).

Структура программы-примера

Color.h содержит класс Color — представление RGBA цвета с float-компонентами («128-битный цвет»);

Vec2.h содержит класс Vec2 — двухкомпонентный вектор двойной точности;

Bbox2.h содержит класс Bbox2 — прямоугольник со сторонами параллельными осям координат, предназначенный для описания прямоугольных областей, занимаемых некими объектами, используется также для представления отображаемой области плоскости;

Poly.h + Poly.cpp определяют контур на основе стандартного vector;

Prim.h + Prim.cpp определяют класс-обёртку примитива OpenGL и класс Mesh2 (представляющий триангуляцию многоугольника), который обращается к GLU для триангуляции переданных контуров (см. шаблон конструктора, принимающий пару итераторов);

GLUPoly.cpp содержит собственно программу.

Реклама

Добавить комментарий

Заполните поля или щелкните по значку, чтобы оставить свой комментарий:

Логотип WordPress.com

Для комментария используется ваша учётная запись WordPress.com. Выход / Изменить )

Фотография Twitter

Для комментария используется ваша учётная запись Twitter. Выход / Изменить )

Фотография Facebook

Для комментария используется ваша учётная запись Facebook. Выход / Изменить )

Google+ photo

Для комментария используется ваша учётная запись Google+. Выход / Изменить )

Connecting to %s

%d такие блоггеры, как: