Category Archives: Graphics

2Dv3D

2Dv3D это GUI приложение, основная часть которого была написана мной в 2006 (затем оно обновлялось несколько раз), предназначенное для визуализации наборов (например, изменяющиеся во времени области плоскости) плоских множеств («слоёв»), заданных многоугольниками («контурами»). Для триангуляции многоугольников используется GLU. К слову, разработчикам, использующим OpenGL в FreePascal / Lazarus или Delphi, может быть полезен dglOpenGL.

Итак, я решил выложить 2Dv3D здесь. Приложение довольно специфическое, но может оказаться кому-нибудь полезным. Исходный код не выкладываю, ибо он страшен есть :). Файл readme.txt (как и manual) устарели, сначала читать readme_first.txt. Кроме того, в файле openfile.txt даётся описание опций диалога загрузки файлов. Некотрые окна (главная панель, отчёт) имеют меню, вызываемое правым кликом.

В папке samples (отсутствует в архиве 2Dv3D-0.48j-no-samples.7z) приведены три примера (промежуточные результаты работы программ построения решений в дифференциальных играх): screw.txt и pipe.txt имеют формат с «многосвязными слоями» (на самом деле односвязны), bridge.txt — с односвязными. Файлы pipe.txt и bridge.txt являются элементами «одной сцены» (трубка достижимости, огибающая мост).

2Dv3D-0.48j.7z (MD5: ce21e49106802cd298ac6dafac0a942b)
2Dv3D-0.48j-no-samples.7z (MD5: 06b69a832f3aaf4163f0935776403858)

Дальнейшее развитие этого приложения и исправление в нём ошибок не планируется.

Реклама

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

AV-2: AstarVis

Введение

На основе кода BY-1 и в качестве продолжения идей AV-1 был разработан визуализатор алгоритма A*. Архив содержит проект Visual C++ 2010 со всем исходным кодом и библиотекой FreeGLUT, готовый к использованию «как есть». В архив также включены откомпилированный exe и html-документация, сгенерированная системой Doxygen/Graphviz по комментариям в исходном коде.

Управление

  • ESC выход;
  • SPACE/ENTER новый ландшафт;
  • стрелки/WASDXZ управление камерой;
  • 0123456789 выбор множителя эвристики (соответственно от 0 до 9) с перерасчётом А*-пути, если нужно;
  • G показывать рёбра графа;
  • P показывать пути, полученные алгоритмами Дейкстры и А*.

Цвета

Про структуру графа, отражающего ландшафт, рассказано в следующем разделе «Ландшафт».

Предварительная заливка ландшафта вычисляется функцией Scene::prepareColors и состоит из синей и красной компонент. Красная компонента возрастает по мере приближения к целевой вершине, оставаясь при этом всегда меньше единицы. Синяя компонента возрастает по мере приближения к начальной вершине (эти вершины находятся в противоположных углах).

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

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

Рёбра графа изображаются отрезками жёлто-оранжевого цвета. Путь, построенный алгоритмом Дейкстры, изображается линией жёлто-зелёного цвета, А*-путь — линией светло-синего цвета.

Ландшафт

Ландшафт генерируется как карта высот сложением псевдослучайных чисел, «холмов» и «кратеров» (вычисляемых как сдвинутая и повёрнутая обратная квадратичная форма координат узла, точнее см. код классов Hill и Ring в HeightMap.h).

Карта высот представляет собой набор отсчётов (двумерный массив чисел), заданных в узлах прямоугольной сетки (лежащей в плоскости 0xy), используемыми как высоты (координаты по оси 0z) некоторого ландшафта в этих узлах. Карту высот представляет класс HeightMap.

Карта высот может быть изображена как набор полосок треугольников. Каждая четвёрка соседних узлов (ограничивающих ячейку сетки в плоскости 0xy) задаёт два треугольника. При этом дублируются вершины всех рядов кроме двух крайних. Нормали к этим треугольникам можно вычислить, например, используя векторное произведение разностей пар их вершин. Полоски треугольников строит и отображает класс Terrain.

Чтобы рассчитывать пути на ландшафте, нужно отождествить элементы графа с некоторыми элементами ландшафта. В простейшем случае можно считать вершинами графа вершины треугольников, а рёбрами графа — рёбра треугольников, проецирующиеся на 0xy в отрезки, параллельные осям 0x и 0y.

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

Связывание визуализации с алгоритмом А*

Класс TerrainGraph может быть использован непосредственно как вектор списков смежности благодаря перегруженному оператору [ ]. Веса рёбер и оценка расстояний (эвристика) рассчитываются с помощью функции-члена estimatePrice. Функторы-адапторы WeightsForGraph и HeuristicForGraph представляют граф соответственно в виде матрицы весов рёбер и эвристики для алгоритма А*.

Визуализатор использует три типа событий:

  1. OpenedEvent для события размещения вершины в очереди с приоритетом (открытое множество).
  2. ClosedEvent для события извлечения вершины из очереди.
  3. PathEvent для пометки очередной вершины в пути, построенном алгоритмом А*.

События последнего типа генерируются в последнем цикле в функции Scene::makeApath. События первых двух типов генерируются и помещаются в очередь объектом класса AstarDemo, передаваемом функции astar в качестве последнего параметра (класс AstarDemo выступает в роли модели параметра шаблона DemoPolicy).

UPDATE. 2013.01.25. Более новый вариант расположен здесь (в составе AV Orchid).

AV-1: SortVis

скриншот / визуализатор сортировок

Введение

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

В качестве основы визуализатора взят код из BY-0.

Исходный код: codepad. Архив откомпилированный exe + freeglut.dll можно скачать по ссылке (для запуска exe должны быть установлены библиотеки Microsoft Visual C++ 2010 redistributable).

Принцип работы

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

Итак, рассматриваем только те алгоритмы, которым достаточно сравнивать (оператор < ) и присваивать (оператор = ) объекты сортируемой последовательности. Чтобы «записать» последовательность вызова указанных операторов вместо чисел сортируются объекты специального класса — «зонда» Probe, который содержит как числовое значение, так и указатель на очередь событий, куда перегруженные operator< и operator= складывают соответствующие события. Такой подход позволяет визуализировать подходящий алгоритм (например, std::sort), не внося в него изменений.

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

Детали реализации

Прямоугольник (class Rect) является визуализацией числа, задаётся двумя углами (левый нижний с координатами (x0, y0) и правый верхний с координатами (x1, y1)) и цветом.

Массив прямоугольников (class RectArray), также «столбец», является визуализацией сортируемого массива. Имеет две функции-члена, отвечающих за визуализацию событий:

void assign ( unsigned index, float value );

соответствует присваиванию элементу массива с индексом index значения value,  прямоугольник с этим индексом изменит длину и будет помечен красным цветом;

void compare ( unsigned i1, unsigned i2 );

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

Событие (struct IEvent) — абстрактный базовый класс, наследники которого должны определять метод void apply(RectArray&), вызов которого с передачей соответствующего массива прямоугольников и будет приводить к применению события и его последующей визуализации.

Очередь событий (class EventQueue) — основной структурный элемент, хранит как собственно очередь событий с временными метками их наступления (в секундах), так и указатель на соответствующий массив прямоугольников, а также его координаты на плоскости. Таким образом, очередь отвечает как за сохранение событий (функция push), за применение событий, произошедших к заданному моменту времени (функция next), так и за отрисовку связанного с ней массива прямоугольников (функция paint).

Зонд (class Probe) — сортируемый объект, генерирующий события с помощью перегруженных операторов. Событиям сравнения и присваивания нужны индексы элементов, поэтому зонд кроме собственно числового значения хранит и свой индекс. Кроме того, так как очередь событий требует «глобальную» временную метку, было решено перенести ответственность за вычисление времени наступления события на специальный класс TimeMapper, который получает объект IEvent, вычисляет время и уже сам отправляет событие в очередь. Поэтому зонд хранит указатель на объект TimeMapper, который является общим для всех элементов сортируемого массива.

Сцена (class Scene) — главный класс, соединяющий все куски визуализатора воедино. Хранит набор очередей событий и соответствующих массивов прямоугольников. Функция makeNew сбрасывает очереди, создаёт и сортирует новые массивы, заполняя очереди событиями. Функция paint отрисовывает все столбцы ( «всю сцену» ). Функция next передаёт время функциям next всех очередей, возвращает true, если хотя бы одно событие было извлечено из очередей (что используется как условие обновления буфера кадра в обработчике frameMove).

Таймер (class Timer) написан для удобного управления скоростью визуализации. Хранит «реальное» время, возвращаемое std::clock(), и «виртуальное» время визуализации в «секундах», с учётом скорости течения времени (поле factor).

UPDATE. 2013.01.23. Более новый вариант расположен здесь (в составе AV Orchid).

BY-1

скриншот

Введение

Результатом BY-0 стала простенькая программа-симулятор движения твёрдых сфер на плоскости. Очевидная следующая задача — сделать движение в трёхмерном пространстве. Сделаем это в два шага (1а и 1б).

Шаг 1а

Цель — реализовать движение в 3D. Будем сравнивать старый и новый варианты.

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

glTranslated(p.x, p.y, p.z);

вместо

glTranslated(p.x, p.y, 0.0);

в Ball::paint() позиционирует шар в трёхмерном пространстве.

Вместо действия одной центральной силы притяжения будем рассчитывать взаимное притяжение шаров друг к другу по формуле закона всемирного тяготения (естественно, значение константы G у нас своё). Сила, действующая на пару шаров вычисляется функцией gravity(Ball&, Ball&).

Кроме того, на шары будет действовать сила «вязкого» трения (не зависящая, впрочем, от взаимно-относительного положения тел) равная -Fr^2 v, где F — коэффициент трения, r — радиус шара, v — скорость шара. Сила трения вычисляется функцией friction(Ball&). Размеры окна в процессе вычисления сил нам более не нужны, поэтому переменные width и height убраны.

Рисование в 3D требует применения техник отсечения невидимых поверхностей. Стандартной техникой, работающей на попиксельном уровне и реализованной аппаратно в GPU, является тест глубины с применением буфера глубины (также называемого z-буфером). В OpenGL тест глубины включается с помощью команды (см. main())

glEnable(GL_DEPTH_TEST);

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

glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT);

Кроме того, для повышения реалистичности картинки неплохо было бы включить освещение. Простейший вариант, доступный в OpenGL 1.0 состоит в использовании повершинного расчёта освещённости с закрашиванием треугольников линейной интерполяцией цветов, полученных на вершинах (затенение Гуро). Для его включения с использованием одного источника света достаточно трёх вызовов

  glEnable(GL_NORMALIZE);
  glEnable(GL_LIGHTING);
  glEnable(GL_LIGHT0);

Параметры источника света LIGHT0 задаются по умолчанию. Это направленный (бесконечно удалённый, заданный направлением лучей) источник белого цвета. Для изменения его параметров можно использовать функции glLight*. При расчёте освещения полагается, что нормали имеют единичную длину. Однако, например, при масштабировании объекта (мы задаём радиус шара), происходит масштабирование и нормалей в том числе, что изменяет их длину. Вызов glEnable(GL_NORMALIZE) предлагает OpenGL позаботиться об этом: включает автоматическую нормализацию нормалей.

Обработчик события изменения сторон окна теперь выставляет (пока всё ещё ортогональную) проекцию примерно фиксированного размера, отображая вдоль наибольшего измерения (ширины или высоты окна) координаты сцены от -500 до 500 (вдоль оси 0x или оси 0y, соответственно).

Что до прочих мелочей, то изменилась «политика выхода» из программы: вместо «жёсткого» exit(0) вызываем glutExit(). Кроме того, чтобы распределить вычислительную нагрузку на все доступные в системе аппаратно поддерживаемые потоки ЦП внутри функции frameMove() используется директива OpenMP:

# pragma omp parallel for

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

Шаг 1б

Следующая цель — управляемая проекция с имитацией перспективы, попросту говоря, «камера». Будем сравнивать вариант, полученный на шаге 1а, и окончательный вариант BY-1.

Камера (класс SphericalCoords) у нас будет довольно простая: основанная на сферических координатах. Положение её в пространстве задаётся двумя углами phi (долгота) и theta (широта), а также расстоянием до начала координат r. Пользователь может поворачивать камеру вокруг начала координат влево (A) и вправо (D) на угол dphi, вверх (Z) и вниз (X) на угол dtheta или придвигать (W) и отодвигать (S) её от начала координат домножением-делением r на заданный коэффициент rf.

Кроме клавиш, генерирующих при нажатии ASCII-код, можно использовать «специальные клавиши» (управление курсором, функциональные). Для этого требуется определить специальный обработчик (в нашей программе он назван specialKeyPressed) и подключить его к GLUT вызовом glutSpecialFunc. Теперь камерой можно управлять клавишами-стрелками.

Матрица проекции строится как произведение двух матриц.

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

gluPerspective(75, double(w) / double(h), 16.0, 4096.0);

который выставляет угол зрения по вертикали в 75 градусов, соотношение сторон (коэффициент, на который нужно домножить угол зрения по вертикали, чтобы получить угол зрения по горизонтали), расстояние до ближней отсекающей плоскости — 16 единиц (всё, что ближе к камере — не рисуется), расстояние до дальней отсекающей плоскости — 4096 единиц (всё, что дальше от камеры — не рисуется. Таким образом задаются размеры объёма отсечения, но не его положение и ориентация в пространстве. Изменяя угол зрения можно добиться эффекта оптического зума.

2. Матрицы камеры, задающей положение и ориентацию видимой области в пространстве. Эта матрица вычисляется в функции SphericalCoords::apply() при помощи функции gluLookAt, которая позволяет задать координаты положения камеры, координаты точки, на которую направлена (смотрит) камера и направление «вверх» (с помощью выбора которого можно вращать камеру вокруг оси зрения). Как нетрудно догадаться, фактически эта функция вычисляет матрицу поворота и сдвига.

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

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

glEnable(GL_BLEND);

Формула смешивания задаётся с помощью функции glBlendFunc:

glBlendFunc(GL_SRC_ALPHA, GL_ONE_MINUS_SRC_ALPHA);

Первый параметр определяет, на что будет домножен цвет «источника» (нового пикселя), в данном случае — на собственное значение альфа-канала. Второй параметр определяет, на что будет домножен цвет «назначения» (пикселя в буфере кадра), в данном случае — на (1 — a), где a — значение альфа-канала нового пикселя. Цвет результирующего пикселя получается как сумма этих двух произведений. Например, вызов

glBlendFunc(GL_ONE, GL_ONE);

приведёт к простому сложению цветов пикселей.

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

glEnable(GL_CULL_FACE);

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

BY-0

Введение

Когда-то давно я написал небольшой примерчик использования библиотеки GLUT, в котором демонстрировалось физически корректное столкновение двух твёрдых шариков. В феврале 2010г он был размещён на моей странице на codepad.org. Теперь же я решил сделать из него что-то более интересное и использовать в качестве учебного пособия.

Шарики

Изначально код рассчитан на N шариков. При этом почему-то было сделано так, что столкновения обрабатываются только между первыми двумя. Впрочем, это несложно исправить.

Вначале генерируется случайная «целевая» точка столкновения внутри окна (функция new_circles). N шариков со случайными массами и радиусами расставляются в случайных позициях со скоростями, направленными в точку столкновения, по величине равными четверти расстояния от центра шарика до точки столкновения. Таким образом, шарики должны столкнуться примерно через 4 секунды.

За рисование (рендеринг) отвечает функция repaint. Собственно же движения и столкновения шариков рассчитываются в функции frame_move. Время на момент расчёта последнего кадра хранится в глобальной переменной t. В случае, если на момент вызова frame_move() прошло больше 0 микросекунд, происходит изменение положения шариков соответственно их скоростям и прошедшему времени. Если центры шариков 0 и 1 находятся друг от друга не дальше суммы радиусов этих шариков, то регистрируется столкновение и скорости шариков меняются соответственно. Код под комментарием «improve distance» производит «разведение» шариков, чтобы они перестали касаться. Работа этого кода может приводить к «туннелированию» шариков, если результирующие скорости оказались близки к параллельным.

Функция handle_key реализует реакцию на нажатие пользователем клавиш, когда активно окно, где происходит рисование шариков (под MS Visual Studio данный файл следует компилировать как консольное приложение, соответственно будет два окна: консоль и окно с графикой, правда, чтобы его скомпилировать и успешно запустить, нужно раздобыть библиотеку GLUT в составе glut.h, glut32.lib и glut32.dll). Нажатие на enter или пробел создаёт новый набор шариков, нажатие на escape (код 27 в ASCII) или q приводит к выходу из программы.

Функция main производит инициализацию GLUT, состояния контекста OpenGL, создаёт аппроксимацию сферы (единичного радиуса, 12 вершин на «круг» по долготе, 4 таких круга по широте), регистрирует (передаёт библиотеке указатели на эти функции) функции-обработчики событий (callbacks; под комментарием «register callbacks» ). Вызов glutMainLoop() запускает цикл-обработчик событий, из которого, собственно, и вызываются зарегистрированные нами функции.

Окна

Зачем нам нужен GLUT? Что до OpenGL, то это низкоуровневый графический API, обращающийся непосредственно к драйверу GPU. В его «компетенции» не входит создание окон GUI или, тем более, организация взаимодействия с пользователем (реакция на события клавиатуры и мыши). Всё это, а также инициализация виртуального устройства OpenGL (создание контекста OpenGL) реализуется операционной системой. Если же хочется обеспечить независимость от ОС и/или простоту кода (что важно для маленьких приложений), имеет смысл воспользоваться сторонними библиотеками-обёртками, предоставляющими указанный функционал. Например, библиотекой GLUT.

Библиотека GLUT имеет давно устоявшийся (в настоящее время не развивается), достаточно простой в использовании (самый простой?) интерфейс на языке C (можно использовать в программах на разных языках программирования). Конечно, есть другие библиотеки, с помощью которых можно сделать то же самое и что-нибудь ещё, как маленькие и простые (например, SFML), так и огромные, предоставляющие широкий функционал для создания серьёзных GUI приложений (например, Qt).

Новый вариант

Итак, старый вариант был переправлен.

Для сравнения старого и нового вариантов удобно использовать какой-нибудь вариант утилиты diff (у Microsoft есть своя реализация — WinDiff, которая может присутствовать в составе Visual Studio/Windows SDK; мне же больше нравится WinMerge).

В качестве реализации GLUT было решено взять более современную (чем оригинальная) open-source библиотеку freeglut (тем более, что есть сборка под Visual C++). Вместо микросекундного времени boost::date_time, будем использовать обычный миллисекундный std::clock.

Макрос GLUTCALLBACK нам теперь без надобности (был на случай особого соглашения вызова для функций-обработчиков, например, __stdcall).

Посмотрим Ball::paint vs circle::paint. Стек матриц не используется, поэтому перед установкой матрицы для шара, просто заменяем текущую матрицу на единичную. Далее, было:

glScaled(r, r, r);
glTranslated(p.x / r, p.y / r, 0.0);

стало

glTranslated(p.x, p.y, 0.0);
glScaled(r, r, r);

Указанные функции домножают текущую матрицу на матрицу соответствующего преобразования слева. Поэтому (новый вариант), сначала промасштабируем единичную сферу, сделав из неё сферу радиуса r, потом переместим её из начала координат в позицию (p.x, p.y), а не наоборот, как было в старом варианте (поэтому там деление на r).

Появилась новая функция Ball::move, которая осуществляет расчёт сдвига шара в соответствии с заданным ускорением a. Ускорение считается постоянным в течении указанного промежутка времени time_step. Метод первого порядка, его точность низкая, но вполне соответствует обычной «игровой физике». Итак, сначала нужно записать в a сумму ускорений, порождаемых силами, действующими на шар, потом вызвать move.

Сила здесь будет одна — похожее на гравитацию (прямо пропорциональное массе шара и константе G, обратно пропорциональное квадрату расстояния) притяжение к центру экрана. Вычислением ускорения, порождаемого этой силой, занимается функция applyCentralForce.

Функция frame_move переименована в frameMove и теперь рассчитывает столкновения для всех пар шариков. Кроме того, вместо того, чтобы «разводить» шарики, «зашедшие» внутрь друг друга, фиксация столкновения производится только в случае сближения центров шариков. Шарики могут оказаться внутри друг друга (что особенно заметно из-за того, что при случайном выборе позиции факт «попадания» внутрь не проверяется), зато нет «туннелирования».

Добавлен обработчик события изменения размеров окна рендеринга reshape, именно там устанавливается матрица проекции, которая в старом варианте просто не использовалась. Текущие размеры окна хранятся в глобальных переменных width и height.

С фактом наличия глобальных переменных пока решено смириться.