Опорный конспект лекций по дисциплине Вычислительная геометрия и компьютерная графика (стр. 6 )

y = f(x)

Пример - уравнение прямой, y = mх + b. При этом одному значению х соотвествует только одно значение y, поэтому замкнутые или многозначные кривые, например окружность, явно представить нельзя. Неявное представление

f(x, y) = 0

позволяет обойти это ограничение.

9.3Параметрические кривые

В параметрическом виде каждая координата точки кривой представлена как функция одного параметра. Значение параметра задает координатный вектор точки на кривой. Для двумерной кривой с параметром t координаты точки равны:

x = x(t)
y = y(t)

Тогда векторное представление точки на кривой:

P(t) = [x(t) y(t)]

Чтобы получить непараметрическую форму, нужно исключить t из двух уравнений и вывести одно в терминах x и y.

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

P'(t) = [x'(t) y'(t)]

Наклон кривой равен

dydx=y'(t)x'(t)

Отметим, что при х'(t) = 0 наклон бесконечен. Параметрическое представление не вызывает в этом случае вычислительных трудностей, достаточно приравнять нулю одну компоненту касательного вектора.

Так как точка на параметрической кривой определяется только значением параметра, эта форма не зависит от выбора системы координат. Конечные точки и длина кривой определяются диапазоном изменения параметра. Часто бывает удобно нормализовать параметр на интересующем отрезке кривой к 0 <= t <= 1. Осенезависимость параметрической кривой позволяет с легкостью проводить с ней аффинные преобразования.

Самое простое параметрическое представление у прямой. Для двух векторов положения P1 и Р2 параметрический вид отрезка прямой между ними такой:

P(t) = P1 + (P2 - P1)t 0 <= t <= 1

Так как Р(t) это вектор, у каждой его составляющей есть параметрическое представление х(t) и y(t) между P1 и P2:

x(t) = x1 + (x2 - x1)t
y(t) = y1 + (y2 - y1)t
0 <= t <= 1

На рис. 3.1. сравниваются непараметрическое и параметрическое представление окружности в первом квадранте. Непараметрический вид

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

Стандартная параметрическая форма единичной окружности:

x = cosθ
y = sinθ
0 <= θ <= 2π

где параметр θ - геометрический угол, отмеряемый против часовой стрелки от положительной полуоси х. На рис. 3.1,b изображена дуга, построенная по равным приращениям параметра в пределах 0 <= θ <= π/2. При этом точки располагаются на одинаковом расстоянии вдоль окружности, и окружность выглядит гораздо лучше. Недостаток такого представления - сложность вычисления тригонометрических функций.

Параметрическом представление кривой не единственно, например,

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

9.4Общие уравнения конических сечений

Общий вид неявного уравнения второй степени

ах2 + 2bхy + сy2 + 2dx + 2еy + f = 0

порождает различные двумерные кривые, называемые коническими сечениями. На рис. 3.2 изображены три вида конических сечений - парабола, гипербола и эллипс. Окружность - это частный случай эллипса. Определяя коэффициенты a, b, c, d, e и f, можно получить разные конические сечения. Если сечение задано относительно локальной системы координат и проходит через ее начало, то f = 0. Для того чтобы провести кривую через данные точки, используются граничные условия.

Пусть с = 1, тогда сегмент кривой между двумя точками определяется пятью независимыми условиями, из которых вычисляются оставшиеся коэффициенты a, b, d, e и f. Например, можно указать положение крайних точек, наклон кривой в них и промежуточную точку на кривой.

Если b = 0, c = 1, то аналитическое представление кривой получается с помощью только четырех дополнительных условий, например положения концевых точек и наклона кривой в них. Кривая при а = 1, b = 0 и с = 1 еще проще

х2 + y2 + 2dx + 2еy + f = 0

Тремя условиями для вычисления d, е и f могут быть две концевые точки и наклон кривой в одной из них или же две концевые точки и третья точка на кривой.

При а = b = с = 0 получается прямая линия. Ее уравнение

dx + еy + f = 0

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

Итак, уравнение представляет параболу при b2 - 4ac = 0 и центральное сечение при b2 - 4ac <> 0. Если сечение центрально и b2 - 4ac < 0, уратвнение представляет эллипс, а если b2 - 4ac > 0 - гиперболу.

Таблица 3.1. Конические сечения

9.5Пространственные кривые

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

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

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

Трехмерные кривые можно представить параметрически или непараметрически. Явное непараметрическое представление имеет вид

x = x
y = f(x)
z = g(x)

Неявное непараметрическое представление кривой как пересечения двух поверхностей задается уравнениями:

f(x, y,z) = 0
g(x, y,z) = 0

Общий параметрический вид пространственной кривой можно записать в виде:

x = x(t)
y = y(t)
z = z(t)

где параметр t изменяется в определенных пределах t1 <= t <= t2. В приведенном выше явном непараметрическом представлении х можно рассматривать как параметр, х = t. Тогда эта же кривая имеет параметрическую форму

x = t
y = f(t)
z = g(t)

9.6Кубические сплайны

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

Уравнение одного параметрического сегмента сплайна таково:

P(t) = 4 Σ i = 1Bi t i-1 t1 <= t <= t2

где t1 и t2 - значения параметров в начале и конце сегмента. Р(t) - вектор к любой точке сегмента. Р(t) = [х(t) y(t) z(t)] - это векторно-значная функция, где три составляющие Р(t) - декартовы координаты вектора.

Коэффициенты Bi можно получить с помощью четырех специальных граничных условий для сплайнового сегмента (подставляя координаты двух концевых точек и приравнивая значения производных в них). Если решить полученную систему уравнений, то для концевых точек P1 и P2 можно записать:

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

9.7Параболическая интерполяция

Кубические сплайны - это мощное и удобное средство, но и они небезупречны: необходимо учитывать влияние направления и величины касательных векторов, указывать все точки кривой до ее изображения, невозможна локальная коррекция кривой. Расчет кубического сплайна требует обращения большой матрицы, зависящей от всех элементов сплайна; т. е. изменение любого сегмента затрагивает все остальные сегменты. Воздействие уменьшается при удалении от точки возмущения, но полностью принебречь им нельзя. Параболическая интерполяция разрешает большинство этих проблем за счет того, что она только непрерывна, т. е. в точках соединения согментов сохраняется непрерывность лишь первой производной, причем параболическая интерполяция не требует больших расчетов.

Параболическая интерполяция была разработана Оверхаузером. Оверхаузер строил кривую интерполяции, исходя из геометрических соображений. Идея состоит в линейной интерполяции (приравнивание производных) пересекающихся частей двух парабол. Параболы заданы четырьмя последовательными точками: первая - тремя первыми точками, вторая - тремя последними. Пересечение лежит между второй и третьей точками. Несмотря на то, что параболы - плоские кривые, их линейная интерполяция - кубическая пространственная кривая, как показано на рис. 4.2.

9.8Кривые Безье

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

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

Кривая Безье задается многоугольником, как показано на рис. 4.3. Так как базис Безье является бернштейновским, сразу же известны некоторые совйства кривых Безье. Например:

 Функции базиса вещественны.

 Степень многочлена, определяющего участок кривой, на единицу меньше количества точек соответствующего многоугольника.

 Основа формы кривой повторяет очертания многоугольника.

 Первая и последняя точки кривой совпадают с соответствующими точками определяющего многоугольника.

 Векторы касательных в концах кривой по направлению совпадают с первой и последней сторонами многоугольника.

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

 Кривая обладает свойством уменьшения вариации. Это означает, что кривая пересекает любую прямую линию не чаще, чем определяющий многоугольник.

 Кривая инвариантна относительно аффинных преобразований.

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

Тема 10 Современные графические системы. Библиотека OpenGL.

OpenGL является на данный момент одним из самых популярных программных интерфейсов (API) для разработки приложений в области двумерной и трехмерной графики. Стандарт OpenGL был разработан и утвержден в 1992 году ведущими фирмами в области разработки программного обеспечения, а его основой стала библиотека IRIS GL, разработанная Silicon Graphics.

На данный момент реализация OpenGL включает в себя несколько библиотек (описание базовых функций OpenGL, GLU, GLUT, GLAUX и другие), назначение которых будет описано ниже.

Что такое OpenGL?

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

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

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

OpenGL является прослойкой между аппаратурой и пользовательским уровнем. Это дает возможность использовать единый интерфейс для разных платформ, при этом получая оптимальную производительность с использованием аппаратной поддержки.

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

Характерными особенностями OpenGL, которые обеспечили распространение и развитие этого графического стандарта, являются:

Стабильность

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

Надежность и переносимость

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

Легкость применения

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

10.1Основные возможности

q Набор базовых примитивов: точки, линии, многоугольники и т. п.

q Видовые и координатные преобразования

q Удаление невидимых линий и поверхностей (z-буфер)

q Использование сплайнов для построения линий и поверхностей

q Наложение текстуры и применение освещения

q Добавление специальных эффектов: тумана, изменение прозрачности, смешивание цветов (blending), устранение ступенчатости (anti-aliasing).

Как уже было сказано, существует реализация OpenGL для разных платформ, для чего было удобно разделить базовые функции графической системы и функции для отображения графической информации и взаимодействия с пользователем. Были созданы библиотеки для отображения информации с помощью оконной подсистемы для операционных систем Windows и Unix (WGL и GLX соответственно), а также библиотеки GLAUX и GLUT, которые используются для создания так называемых консольных приложений.

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

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

10.2Основы OpenGL

С точки зрения архитектуры графическая система OpenGL является конвейером, состоящим из нескольких этапов обработки данных:

q Аппроксимация кривых и поверхностей

q Обработка вершин и сборка примитивов

q Растеризация и обработка фрагментов

q Операции над пикселями

q Подготовка текстуры

q Передача данных в буфер кадра

GL обрабатывает и выводит так называемые примитивы (primitive) с учетом некоторого числа выбранных режимов. Каждый примитив – это точка, отрезок, многоугольник и т. д. Каждый режим может быть изменен независимо от других. Определение примитивов, выбор режимов и другие операции описывается с помощью команд в форме вызовов процедур.

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

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

10.3Синтаксис команд

Для обеспечения интуитивно понятных названий в OpenGL полное имя команды имеет вид:

type glCommand_name[][b s i f d ub us ui][v] (type1 arg1,…,typeN argN)

Таким образом, имя состоит из нескольких частей:

gl это имя библиотеки, в которой описана эта функция: для базовых функций OpenGL, функций из библиотек GLU, GLUT, GLAUX это gl, glu, glut, aux соответственно.

Command_name имя команды

[] число аргументов команды

[b s i f d ub us ui] тип аргумента: символ b означает тип GLbyte (аналог char в С\С++), символ f – тип GLfloat (аналог float), символ i – тип GLint (аналог int) и так далее. Полный список типов и их описание можно посмотреть в файле gl. h

[v] наличие этого символа показывает, что в качестве параметров функции используется указатель на массив значений

Символы в квадратных скобках в некоторых названиях не используются. Например, команда glVertex2i() описана как базовая в библиотеке OpenGL, и использует в качестве параметров два целых числа, а команда glColor3fv() использует в качестве параметра указатель на массив из трех вещественных чисел.

10.4Структура консольного приложения

Будем рассматривать построение консольного приложения при помощи библиотеки GLUT или GL Utility Toolkit, получившей в последнее время широкое распространение. Эта библиотека обеспечивает единый интерфейс для работы с окнами вне зависимости от платформы, поэтому описываемая ниже структура приложения остается неизменной для операционных систем Windows, Linux и многих других.

Функции GLUT могут быть классифицированы на несколько групп по своему назначению:

q Инициализация

q Начало обработки событий

q Управление окнами

q Управление меню

q Регистрация вызываемых (callback) функций

q Управление индексированной палитрой цветов

q Отображение шрифтов

q Отображение дополнительных геометрических фигур (тор, конус и др.)

Инициализация проводится с помощью функции

glutInit (int *argcp, char **argv)

Переменная argcp есть указатель на стандартную переменную argc описываемую в функции main(), а argv – указатель на параметры, передаваемые программе при запуске, который описывается там же. Эта функция проводит необходимые начальные действия для построения окна приложения, и только несколько функций GLUT могут быть вызваны до нее. К ним относятся:

glutInitWindowPosition (int x, int y)

glutInitWindowSize (int width, int height)

glutInitDisplayMode (unsigned int mode)

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

GLUT_RGBA Режим RGBA. Используется по умолчанию, если не указаны явно режимы GLUT_RGBA или GLUT_INDEX.

GLUT_RGB То же, что и GLUT_RGBA.

GLUT_INDEX Режим индексированных цветов (использование палитры). Отменяет GLUT_RGBA.

GLUT_SINGLE Окно с одиночным буфером. Используется по умолчанию.

GLUT_DOUBLE Окно с двойным буфером. Отменяет GLUT_SINGLE.

GLUT_STENCIL Окно с трафаретным буфером.

GLUT_ACCUM Окно с буфером накопления.

GLUT_DEPTH Окно с буфером глубины.

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

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

Работа с трафаретным буфером и буфером накопления описана в разделе Спецэффекты.

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

void glutDisplayFunc (void (*func) (void))

void glutReshapeFunc (void (*func) (int width, int height))

void glutMouseFunc (void (*func) (int button, int state, int x, int y))

void glutIdleFunc (void (*func) (void))

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

void glutPostRedisplay (void)

Через glutReshapeFunc() устанавливается функция обработки изменения размеров окна пользователем, которой передаются новые размеры.

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

Контроль всех событий происходит внутри бесконечного цикла в функции

void glutMainLoop (void)

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

#include <GL/glut.h>

void MyIdle(void)

{

/*Код, который меняет переменные, определяющие следующий кадр */

…

};

void MyDisplay(void)

{

/* Код OpenGL, который отображает кадр */

…

/* После рисования переставляем буфера */

glutSwapBuffers();

};

void main(int argcp, char **argv)

{

/* Инициализация GLUT */

glutInit(&argcp, argv);

glutInitWindowSize(640, 480);

glutInitWindowPosition(0, 0);

/* Открытие окна */

glutCreateWindow("My OpenGL Application");

/* Выбор режима: двойной буфер и RGBA цвета */