© Георгиевский Анатолий, 27.01.2008 - 09.02.2008

OpenGL. Построение плоских и объемных фигур заданных контурами

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

Надписи в OpenGL

Шрифты в OpenGL не представлены никак. С выводом текстов придется повозится. Есть два основных направления, как представлять тексты в OpenGL: в виде полигонов или в виде растровых изображений. Каждый из этих двух способов имеет свои плюсы и свои минусы. Изображение растровое выглядит лучше если размер шрифта не слишком велик. Если буквы, цифры и всё что в шрифтах встречается (глифы) крупные, то тогда в плане качества и быстродействия выигрывает способ представления в виде полигонов. Можно сформулировать два критерия когда использовать растровые изображения, когда полигоны.

Если количество вершин необходимых для представления глифа (символа в терминологии шрифтов) превышает количество точек растрового изображения глифа. Например, если глиф имеет высоту 32 линии, а представление того же глифа полигонами задается 40 вершинами, то по объему загружаемой информации может выигрывать векторное представление шрифта. Однако надо учитывать второй критерий применимости векторных изображений. Минимальное растояние между вершинами должно превышать 1 пиксель иначе качество представления глифа в виде растрового изображения будет заведомо выше.

Шрифты и глифы

Надписи состоят из отдельных глифов (символов). Глифы беруться из шрифтов в фотрмате OpenType или TrueType. Шрифты содержат представление глифа в виде множества контуров, а также правила расчета расстояния между глифами. Каждый глиф в шрифте представлен набором контуров в векторном виде: вершинами и правилами их соединяения. Соединение вершин производится прямыми линиями или кривыми Безье. Кривые Безье задаются по трем или четырем вершинам.

Растровое представление

Если вам в прикладном ПО понадобилось сгенерировать растровую надпись, то рекомендуется воспользоваться библиотекой FreeType2, на базе которой строится вся типография Linux. Однако, FreeType2 предоставляет только базовый набор функций для работы с отдельными глифами. Следует обратить внимание на библиотеку Pango, которая представляет собой более высокий уровень и предоставляет средства для компоновки глифов в слова и средства форматирования абзацев. Средства FreeType2+Pango входят в состав библиотек GTK+.

Векторное представление

Прежде всего необходимо распознать формат TrueType и загрузить глифы. С этой задачей хорошо справится библиотека FreeType2. Дальше, надо получить представление глифа в виде контуров и перевести контуры в полигоны.

#include <ft2build.h>  
#include FT_FREETYPE_H
#include FT_GLYPH_H

...

FT_Library library; 
FT_Face face; 

FT_Init_FreeType( &library ); 

FT_New_Face( library, font_name, 0, face );

FT_Load_Glyph( face, glyph_index, FT_LOAD_DEFAULT | FT_LOAD_NO_SCALE);
face->glyph->outlines.

Последоавтельность действий дана упрощенно, по каждой функции рекомендуется почитать документацию к FreeType2.

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

В следующем примере промежуточные точки контура расчитывались кривыми Безье.

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

glEnable(GL_LINE_SMOOTH);
glHint( GL_LINE_SMOOTH_HINT, GL_DONT_CARE);

"Хинты" указывают библиотеке (или драйверу) насколько эта возможность мне нужна, готов ли я пожертвовать быстродействием.

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

glLineWidth(2.5);

Триангуляция полигонов (тесселяция)

Следующая проблема сводится не столько к пониманию, как рисовать объемные шрифты, скорее как работать с контурами трехмерных объектов и как из конуров получать поверхности. Решение сводится к разбивке контура на множество простых фигур. Разбивка на примитивы (треугольники) называется попросту триангуляцией. Средство для триангуляции полигонов (теселяции) представлено в библиотеке GLU. "Теселяция" происходит от иностранного слова "тессель" обозначающего кусочки мозаики. Мозаика может состоять из привычных для OpenGL примитивов: GL_TRIANGLE_FAN, GL_TRIANGLES, GL_QUADS. Треугольников, прямоугольников и треугольников расположенных веером (GL_TRIANGLE_FAN) вокруг центральной точки. На рисунке ниже продемонстрирован характер разбиения контура на треугольники. Некоторые элементы мозаики отобразились неадекватно. Те части полигона, которые представляются в форме веера (GL_TRIANGLE_FAN), как например точка в конце надписи, отображаются без радиальных линий.

Триангуляция выполняется над набором контуров. Открытые или залитые контуры задаются направлением обхода контура по или против часовой стрелки (CCW/CW). По ходу дела, алгоритм триангуляции может самостоятельно определять какие контуры являются внутренними, какие внешними обводами. Режим автоматическтого выделения вложенности контуров задается параметром GLU_TESS_WINDING_ODD.

gluTessProperty( tobj, GLU_TESS_WINDING_RULE, GLU_TESS_WINDING_ODD);

Ниже представлен результат работы тесселятора.

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

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

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

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

Вытягивание контура мы производим по оси Z (в общем случае можно под любым углом к плоскости). Каждому отрезку линии контура мы достраиваем полигон прямоугольной формы. Полигоны добавляются в режиме GL_QUAD_STRIP - вершины задаются в виде ленточки.

glBegin( GL_QUAD_STRIP);
for (... по всем точкам контура...){
   glVertex3f(x,y,z); glVertex3f(x,y,z-dz);
}
glEnd();

На рисунке ниже представлен результат построения контура в виде ленточки. Цвет был задан полупрозрачным, поэтому ленточка просвечивает. Ленточка получилась одноцветной, без полутонов и теней, потому что освещение не просчитывалось.

glDisable(GL_LIGHTING);

Поверх ленточки был нанесен контур сглаженной линией.

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

glBegin( GL_QUADS);
for (... по всем отрезкам контура...){
   glNormal2f(-dy, dx);
   glVertex3f(x[i],y[i],z[i]); glVertex3f(x[i],y[i],z[i]-dz);
   glVertex3f(x[i+1],y[i+1],z[i+1]-dx); glVertex3f(x[i+1],y[i+1],z[i+1]);
}
glEnd();

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

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

Базовые операции производимые с контурами объектов

Тут мы сделаем вид, что работаем с множествами: множеставми отрезков, вершин и полигонов. Берем букву "А" или лучше "О". У этой буквы есть внешний и есть внутренний контур. В общем случае контур ориентирован произвольным образом, по или против часовой стрелке. Превая задача, необходимо определить какой контур является внешним, какой внутренним. Контуры должны быть сориентированы против часовой стрелки (ССW) при обходе внешнего контура или по часовой стрелке (CW) при обходе внутреннего контура. Основная операция - смена направления обхода контура.

Обработка контуров

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

void APIENTRY my_tess_combine(GLdouble coords[3], 
                              void* vertex_data[4],
                              GLfloat weight[4], void** dataOut)
{
   myVertex* vertex = vertex_new(coords);
   *dataOut=vertex;
}

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

gluTessCallback( tobj, GLU_TESS_COMBINE,   (_GLUfuncptr)my_tess_combine);

Можно сохранить результат обработки контуров, если переопределить функцию описания вершины в функцию сохранения вершины в новый контур. Так функция my_tess_vertex создает объект типа "вершина контура" и добавляет в ноый контур.

void APIENTRY my_tess_vertex(GLdouble coords[3], 
                              void* contour_data)
{
	myContour* contour = contour_data;
	myVertex* vertex = vertex_new(coords);
	contour_append(contour_data, vertex);
}

Добавляем обработчик вершин в описание тесселятора.

gluTessCallback( tobj, GLU_TESS_VERTEX_DATA,   (_GLUfuncptr)my_tess_vertex);

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

gluTessProperty( tobj,GLU_TESS_BOUNDARY_ONLY, 1);
gluTessProperty( tobj, GLU_TESS_WINDING_RULE, GLU_TESS_WINDING_ODD);

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

Добавление контуров

gluTessProperty( tobj, GLU_TESS_WINDING_RULE, GLU_TESS_WINDING_POSITIVE);

Вычитанние контуров

gluTessProperty( tobj, GLU_TESS_WINDING_RULE, GLU_TESS_WINDING_POSITIVE);

Использован тот же самый режим, только мы предварительно сменили направление обхода контура.

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

gluTessProperty( tobj, GLU_TESS_WINDING_RULE, GLU_TESS_WINDING_ABS_GEQ_TWO);

Растровые изобаржения

Растровые шри.... Растровое изрбражение надписи.

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

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

Искусство выкладывания мозаики из цветных пикселей называется пиксель-арт.

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

Интеграл считается по замкнутому контуру ограниченному одним пикселем, через который проходит контур. Если контур проходит несколько раз через данный пиксель, то интеграл считается несколько раз и суммируется по модулю 1. При использовании такого метода количество операций умножения и деления, на самом деле, около 10 на каждый фрагмент контура попадающего внутрь пикселя.

На рисунке (выше) графически представлены правла подсчета площади при пересечении пикселя и контура, на третьем фрагменте - сумма двух проходов по модулю 1. Для вещественных чисел операции суммирования по модулю будет соответствовать результат выражения.

	S = S - floor(S);

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

glPixelZoom(1.0,1.0);
glRasterPos2f (X, Y);
glPixelStorei(GL_UNPACK_ALIGNMENT, 4);
glDrawPixels (bitmap->width, bitmap->height,
  GL_RGBA, GL_UNSIGNED_INT_8_8_8_8,
  bitmap->buffer);

Для вывода текстовых фрагментов может оказаться более удобным режим GL_LUMINANCE или GL_LUMINANCE_ALPHA, чтобы накладывать надпись на фоновое изображение. Функция glPixelZoom() позволяет масштабировать растровое изображение. Функция glRasterPos2f() задает расположение изображения. Подробнее по параметрам функций следует обратиться к спецификации.

На изображении мелкая надпись выведена функцией glDrawPixels().

Штриховка и фрезерование поверхностей заданных контурами

Наклонная шриховка может быть выполнена, если контур повернуть или шрихи повернуть. Если поворачивать напрвление штрихов, то в каждой точке контура надо считать расстояние от точки до наклонной линии. Если контур повернуть, то считать надо поворот каждой точки контура. В одном случае умножение матрицы на вектор, в другам случае умножение транспонированной (обратной) матрицы на вектор. Количество операций вообще-то одинаковое. Предлагается ввести операцию поворота контура и не усложнять алгоритм штриховки. Обратное преобразование - дело техники. При выводе надо указать поворот координат (обратное преобразование), при помощи функции glRotatef(-angle, 0,0,1).

Отступ

Следующая задача - генерация огибающего контура с отступом на радиус инструмента. Каждая точка огибающего контура должена располагаться на расстоянии R от исходного. Первым делом мы построили контур состоящий из отрезков сдвинутых на расстояние R относительно исходного контура в направлении перпендикулярном исходному контуру (по нормали).

Для расчета относительных координат точки M смещенной на растояние R от прямой заданной векотором (dx,dy) использовалось выражение

x = \frac{-dy\cdot{R}}{\sqrt{dx^2 + dy^2}}
y = \frac{dx\cdot{R}}{\sqrt{dx^2 + dy^2}}

Количество точек (вершин) при этом удвоилось и появились разрывы.

Изображение построено с учетом выпуклости-вогнутости контура. Разрывы показаны только для выпуклых фрагментов контуров.

На рис. показано правило определения выгнутости-вогнутости (кривизны) контура. Перегиб определяется по трем точкам. Можно сказать, что нас интересует измнение направления вектора или знак второй производной. Для численного определения перегиба в точке (x1,y1) предлагается использовать расстояние от точки до прямой, заданной вектором. Для упрощения формулы мы построили отрезки и вектора в относительных координатах.

Расстояние от точки (x1,y1) до прямой Ax+By+C = 0 описывается выражением

d = \frac{Ax+By+C}{\sqrt{A^2 + B^2}}

Нас интересует только знак выражения, поэтому выражение под корнем можно не считать.

d1 ~ –(y1 – y0)·(x2 – x0) + (x1 – x0)·(y2 – y0)

С тем же успехом можно посчитать площадь контура образованного тремя соседними точками.

Если кривая выпуклая - всё просто, разрыв можно заменить дугой окружности. А если кривая вогнутая, могут быть разные варианты пересечения отрезков...

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

Расчет точки пересечения отрезков M(x,y)...

t = \frac{d_1}{d_1 - d_2}
x = (1–tx1 + t·x2
y = (1–ty1 + t·y2

Здесь величины d1 и d2 противоположного занака.

Cсылки

  • OpenGL - индустриальный стандарт трехмерной графики
  • Спецификация OpenGL. Не самая свежая, но рекомендуемая для начального ознакомления.
  • Спецификация библиотеки GLU (GL Utility)
  • библиотека FreeType2 - загрузка шрифтов TrueType
  • Кривые Безье, очень наглядно

    (27 января 2008 г. - 9 февраля 2008 г.)

  •