Category Archives: GLU

GLU-1: FusedFunctor

Введение

Дальнейшее развитие программы-демонстратора триангуляции средствами GLU.

В качестве эксперимента была опробована методика, названная здесь «fused functors» («слияние функторов»). Это эксперимент, а не пример распространённой или рекомендуемой практики. Суть методики в объединении нескольких действий, выполняемых над одними и теми же элементами массива (первоначально вершинами контура) и/или их последовательными парами (первоначально отрезками, составляющими контур). Можно продолжить на n-ки произвольной длины (например, все последовательные тройки вершин позволяют обработать углы контура). Код здесь: GLUPoly-1.2.7z. Объединение нескольких действий задумано с тем, чтобы выполнять их не за несколько проходов, а за один.

FusedFunctor

Итак, функтор, допускающий «слияние», строго говоря не является функтором в терминах C++, так как не переопределяет operator(). Класс, который можно назвать «FusedFunctor» должен предоставлять следующее.

  • Вложенные типы argument_type (тип обрабатываемых элементов массива) и result_type (результат обработки, возвращаемый в конце, может быть void, например, если begin/fuse складывают элементы в контейнер или выводят в поток).
  • Функции начала процесса void begin (argument_type) и void begin (argument_type, size_t n), в качестве первого параметра принимающие первый обрабатываемый элемент, в качестве n может передаваться общее количество элементов, если оно известно заранее (да, элементы могут поступать произвольным образом, а не выбираться из массива).
  • Функция обработки следующего элемента void fuse (argument_type), вызывается для всех элементов кроме первого в порядке их поступления.
  • Функция завершения процесса result_type end(), возвращающая конечный результат (если result_type не void).

Функционал разбит на три заголовочных файла. На диаграмме ниже показано их содержимое.

Стрелочкой «A ← b» показаны случаи, когда функция b возвращает объект класса A. Назначение этих функций в увеличении удобства использования классов (аналогично std::pairstd::make_pair, чтобы не выписывать явно параметры шаблонов, если они выводимы).

FusedFunctor.h

Функция applyFused применяет fused functor к диапазону, заданному парой итераторов. Если итераторы относятся к категории RandomAccessIterator, то используется вариант begin с указанием количества элементов.

Два fused functor’а можно объединить, используя combineFused. При этом результат второго функтора игнорируется. Данная функция используется в конструкторе Mesh2.

Остальное содержимое файла имеет вспомогательное назначение. Функции fuseVoidBy1, fuseBy1 и fuseBy2 позволяют «конвертировать» обычный функтор в fused functor (соответственно FusedVoidBy1, FusedBy1 и FusedBy2). Первая из них полагает, что функтор не возвращает результата (результат игнорируется). By1-варианты обрабатывают по одной вершине. By2-варианты обрабатывают все последовательные пары, в конце пару (последний элемент, первый элемент). Не-void варианты используют функтор «аккумулятор» для объединения результатов вызовов исходного функтора. По умолчанию используется InPlaceAdd, вызывающий operator+=.

Шаблоны ResultOf и ArgumentOf используются для вычисления типа (через вложенный тип type, такие шаблоны ещё называют метафункциями) результата функтора (для классов по умолчанию используется вложенный тип result_type) и типа аргумента (для классов используется вложенный тип argument_type). ArgumentOf работает и для бинарных функций (но не для функторов-наследников std::binary_function), однако, при необходимости можно либо явно задать тип аргумента в шаблоне, либо определить частную специализацию шаблона ArgumentOf, возвращающую нужный тип. Аналогично можно поступить и с ResultOf, впрочем, этот шаблон несколько «сильнее» засчёт того, что опирается на boost::result_of (который, в свою очередь, использует возможности C++11, если они доступны).

Вспомогательную роль играют boost::type_traits (common_type) и boost::call_traits (для вывода типа параметра из типа аргумента, для пользовательских классов по умолчанию выводится константная ссылка).

FusedForContour.h

В этот заголовочный файл включены средства, предназначенные для использования с объектами Contour, основанные на FusedFunctor.h. FusedPerimeter и FusedArea являются fused functor, и вычисляют соответственно периметр и площадь многоугольника. Они используются в Contour::perimeter() и Contour::area(). FusedContourPushBack заполняет объект контура вершинами.

FusedFunctorTuple.h

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

Функции functorsTuple/functorsTupleVoid можно использовать для объединения нескольких обычных функторов в один функтор, возвращающий n-ку («tuple», «кортеж») результатов (не-Void-вариант). Для конвертирования n-ки fused functor’ов в один fused functor предназначены fuseTuple/fuseVoidTuple (Void-вариант игнорирует результаты). Далее их опять же можно объединить с помощью combineFused (цель которой, собственно, не в объединении пары функторов, а в объединении того, что возвращает результат и того, что не возвращает).

Используется реализация n-ки из boost::fusion.

GLU-1: SSE2 реализация Vec2

Введение

Старый вариант GLUPoly переименован в GLUPoly-1.0.7z. Ниже описаны отличия GLUPoly-1.1.7z.

Написана реализация Vec2 поверх SSE2, использующая интринсики (помещена в Vec2sse2.h). Старый Vec2.h переименован в Vec2std.h. Новый Vec2.h включает Vec2sse2.h, если компилируется MSVC под x64 или с параметром /arch:SSE2 (или /arch:AVX), иначе включает Vec2std.h.

Некоторые изменения были внесены в Bbox2.h (ускорение построения Bbox2 по набору Vec2).

Проблема 1

Для эффективного использования SSE следует выравнивать данные по 16-байтной границе, поэтому значения типа __m128d (пара 64-битных чисел с плавающей точкой, упакованная в 128-битное значение) выравниваются по 16-байт. Это свойство автоматически передаётся всем структурам/классам, включающим в себя __m128d.

Однако стандартные средства выделения памяти не гарантируют выравнивания нестандартных размеров (т.е., например, new int[100] будет выровнен по 4-байтной границе для 4-байтного int, а вот new __m128d[100] по 16-байтной границе уже может быть и не выровнен).

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

Недостаток такого решения — невозможность использования с контейнерами, использующими rebind::other аллокатора (например, std::list).

Принятое решение основано на двух дополнительных классах, размещённых в новом файле AlignedAllocator.h.

AlignedNewDeleteImpl<Align> реализует набор operator new/operator delete, выравнивающих по Align байт (Align == 16 для __m128d и, соответственно, SSE2-версии Vec2). Класс, которому нужно обеспечить выравнивание своих объектов, может наследовать от AlignedNewDeleteImpl. С другой стороны, AlignedNewDeleteImpl является обёрткой системно-зависимых функций выделения памяти (только отсюда они вызываются напрямую).

Замечание. Vec2 для простоты использует public-наследование. С точки зрения принципов использования наследования следует использовать private-наследование, однако оказалось, что using AlignedNewDeleteImpl::operator new и т.д. в public-секции не работает. Пока мне не ясно, с чем это связано. Конечно, можно это обойти, написав явную переадресацию вызовов.

AlignedAllocator<T, Align> реализует STL-совместимый аллокатор, для выделения объектов T средствами AlignedNewDeleteImpl. Его можно использовать непосредственно (Align по умолчанию устанавливается равным __alignof T) в качестве параметра шаблона STL-контейнера. «Правильный» аллокатор решает проблему rebind::other.

Кроме того, для удобства можно определить std::allocator для своего класса, чтобы каждый раз не приходилось указывать аллокатор (т.к. стандартный аллокатор всё равно не подходит, и его использование может оказаться латентной ошибкой), что и сделано для Vec2 путём наследования std::allocator<Vec2> от AlignedAllocator<Vec2>.

Проблема 2

Компилятор может «отказаться» передавать объекты с выравниванием поверх стандартных встроенных типов в функции как копии. Например, void foo (const __m128d&); компилируется, а void foo (__m128d); — нет.

К сожалению, в std::vector нашлась такая функция, а именно — resize (size_type, T), принимающая заполняющее значение как копию. Можно по-разному пытаться обойти эту проблему. В данном случае я выбрал решение «в лоб»: написать свою реализацию динамического массива Vec2: Contour (Contour.h и Contour.cpp). Данная реализация также использует SSE2 (для копирования /заполнения диапазонов), если был включен Vec2sse2.h.

UPDATE 08/12. В стандартной библиотеке C++11 эта функция изменена и теперь принимает ссылку. Таким образом, можно использовать std::vector из современных дистрибутивов STL (например, в составе Visual Studio 2012).

Тестирование

Solution теперь содержит два проекта: исходный GLUPoly и вспомогательный Tests (содержит только один файл test.cpp). Цель второго проекта — аккумуляция unit-тестов, проверяющих код из GLUPoly. На данный момент тестами покрыты Vec2, Bbox2 и Contour. Тесты построены на библиотеке Boost.Test.

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

Ещё

Добавлены FusedFunctor.h и FusedFunctorTuple.h, но о них я намерен написать в следующий раз (планируется внести некоторые изменения).

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 содержит собственно программу.