Видное место в системах геометрического моделирования занимает конструирование кривых и поверхностей. При этом чаще всего возникает задача восполнения данных: имеется некоторое количество точек, через которые следует провести кривую. Это ни что иное, как классическая задача интерполяции. Многим из тех, кто сталкивается с научными и инженерными расчётами часто приходится оперировать наборами значений, полученных экспериментальным путём или методом случайной выборки. Как правило, на основании этих наборов требуется построить функцию, на которую могли бы с высокой точностью попадать другие получаемые значения. Такая задача называется аппроксимацией кривой. Интерполяцией называют такую разновидность аппроксимации, при которой кривая построенной функции проходит точно через имеющиеся точки данных. Задача сглаживания кривой возникает, когда данные, используемые для ее восстановления, определены в результате измерений или эмпирически с некоторой погрешностью либо представляют кривую, описываемую функцией, недостаточно гладкой (например, не дифференцируемой или дифференцируемой всего несколько раз). Существует также близкая к интерполяции задача, которая заключается в аппроксимации какой-либо сложной функции другой, более простой функцией. Если некоторая функция слишком сложна для производительных вычислений, можно попытаться вычислить её значение в нескольких точках, а по ним построить, то есть интерполировать, более простую функцию. Разумеется, использование упрощенной функции не позволяет получить такие же точные результаты, какие давала бы первоначальная функция. Но в некоторых классах задач достигнутый выигрыш в простоте и скорости вычислений может перевесить получаемую погрешность в результатах. Существует совершенно другая разновидность математической интерполяции, известную под названием «интерполяция операторов». К классическим работам по интерполяции операторов относятся теорема Рисса-Торина (Riesz-Thorin theorem) и теорема Марцинкевича (Marcinkiewicz theorem), являющиеся основой для множества других работ, но данный вид интерполяции не рассматривается в этой работе.

1. СОСТАВНЫЕ КРИВЫЕ И СПЛАЙНЫ

Определение интерполяции

Рассмотрим систему несовпадающих точек x_i (iÎ0,1,…,N) из некоторой области D. Пусть значения функции f известны только в этих точках:

y_i=f(x_i), i=1,…,N

Задача интерполяции состоит в поиске такой функции F из заданного класса функций, что

F(x_i)= y_i, i=1,…,N

Точки x_i называют узлами интерполяции, а их совокупность — интерполяционной сеткой.

Пары (x_i,y_i) называют точками данных или базовыми точками.

Разность между «соседними» значениями

D x_i= x_i -x_i_-1

- шагом интерполяционной сетки. Он может быть как переменным так и постоянным.

Функцию F(x) - интерполирующей функцией или интерполянтом.

Точки данных (из приведённой таблицы), в декартовой системе координат.

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

Классический метод ее решения состоит в построении интерполяционного многочлена Лагранжа.

Линейная интерполяция

Лине́йная интерполя́ция — интерполяция алгебраическим двучленом

P₁(x) = ax + b функции f, заданной в двух точках x_i_-1 и x_i отрезка.

Геометрически это означает замену графика функции f прямой, проходящей через точки (x_i_-1,f(x_i_-1)) и (x_i,f(x_i)).

Уравнение такой прямой имеет вид:

отсюда для xÎ[x_i_-1,x_i]

Это и есть формула линейной интерполяции, при этом

f(x)=P₁(x)+R₁(x)

где R₁(x) — погрешность формулы:

Справедлива оценка

Линейная интерполяция применяется для уплотнения таблиц. Формула линейной интерполяции является частным случаем интерполяционной формулы Лагранжа и интерполяционной формулы Ньютона.

Многочлен Лагранжа

Интерполяционный многочлен Лагранжа (рис 1.1) определенного равенством

(1.1)

где

. (1.2)

Рис.1.1 График многочлена Лагранжа

Из определения L_i(x) следует, что

L_i(x_j) =, i, j ,

где - дельта-символ Кронекера:

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

Этот недостаток можно устранить, если склеивать не многочлены Лагранжа, а многочлены Эрмита.

Кусочно-кубические многочлены Эрмита

Пусть в узлах сетки : а = x₀< x₁<...< x_N = b даны значения некоторой функции f (x) и ее производной f^/(x):

f_i = f (x_i), , i = 0,1,...,N.

Требуется построить кусочно-кубический полином Эрмита p_н(х), удовлетворяющий условиям:

1) на каждом промежутке (i = 1,2,...,N)

p_н(х) = a_io+ a_i₁ (х -х_i_-1) + a_i₂ (х -х_i_-1)² + a_i₃ (х -х_i_-1)³ ; (1.3)

2) Р_н (х_i) = f_i, (х_i) =, i = 0,1,...,N.

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

Учитывая условия интерполяции, для вычисления коэффициентов (= 0,1,2,3) для каждого i имеем систему уравнений, определяемую равенствами:

p_н (х_i_-1) = f_i_-1, p_н (х_i) = f_i,

(х_i_-1) = , (х_i) = .

Если ввести обозначения h_i = x_i - x_i_-1, то на участке [x_i_-1, x_i] получим систему уравнений для определения :

a_i0 = f_i-1;

a_i0 + a_i1 h_i + a_i2 h_i² + a_i3h_i³= f_i;

a_i1= ;

a_i1 + 2a_i2 h_i + 3a_i3h_i²= .

Отсюда находим неизвестные коэффициенты:

a_i₀ = f_i_-1;

a_i₁= ;

a_i₂ = ; (1.4)

a_i₃= .

Введем обозначение u = (x - x_i_-1) / h_i. Подставляя (1.4) в (1.3) и собирая члены при f_i_-1, f_i, и , получим

Р_н (х) =. (1.5)

,где

(u) = 1- 3u² + 2u³;

(u) = 3u² - 2u³;

(u) = u - 2u² + u³; (1.6)

(u) = -u² + u³

есть функции Эрмита третьей степени. Их графики изображены на рис.1.2. График полинома Эрмита представлен на рисунке 1.3.

Рис. 1.2 Функции сопряжения многочлена Эрмита

Рис.1.3 График кусочно-кубического многочлена Эрмита

Иногда эти функции называют функциями сопряжения. Как видно из (1.5), с помощью первых двух функций сопрягаются значения f_i_-1 и f_i, а посредством двух других - производные и , в результате чего получается «сглаженное» объединение Р_н (х) на участке [x_i_-1, x_i].

Возникает вопрос: что делать, если производные в узлах сетки неизвестны? Наиболее простым выходом из этой ситуации является определение первых производных по разделенным разностям вида:

, i = 1,2,...,N-1

(1.7)

где

, .

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

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

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

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

Кусочно-кубические функции Эрмита (другой пример сплайнов) - это кубические сплайны дефекта 2, т.е. сплайны с непрерывной первой производной. Сплайны с непрерывной второй производной будем называть сплайнами дефекта 1. Сплайн, на всем отрезке [а, b] совпадающий с кубическим полиномом, назовем сплайном дефекта 0.

Термин «сплайн» произошел от английского слова spline. В переводе это «рейка» - приспособление, которое применяют чертежники для проведения гладких кривых через заданные точки.

Возьмем гибкую стальную рейку (линейку), поставим ее на ребро и поместим между опорами, которые расположены в заданных точках (рис.1.4).

Рис.1.4 Кубическая сплайн-функция

Согласно закону Бернулли-Эйлера, линеаризованное дифференциальное уравнение изогнутой оси линейки имеет вид:

(1.8)

где М (х) - изгибающий момент изменяющийся линейно от одной точки опоры к другой,

- вторая производная прогиба рейки,

E – модуль Юнга,

I – момент инерции.

Для малых отклонений рейки y'<<1 вторая производная прогиба рейки будет равна

где R(x) – радиус кривизны.

Из формулы 1.8 можно выразить

Так как опоры гибкой рейки действуют как простые подпорки, тогда изгибающие моменты между опорами изменяются линейно. Подставляя M(x)=Ax+B в уравнение Бернулли-Эйлера получим

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

S(x)= A₁x³+ B₁x²+ C₁x+ D₁

Таким образом, профиль линейки описывается кубическим сплайном дефекта 1 или просто кубическим сплайном. Для определенности задачи на концах должны быть заданы краевые условия, в частности, при отсутствии внешних нагрузок на линейку (х₀) = (х_N) = 0.

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

Во-первых, это функции наименьшей степени, имеющие непрерывные вторые производные.

Во-вторых, алгоритмы построения кубических сплайнов очень просты и эффективно реализуются на ЭВМ, причем влияние ошибок округления при вычислениях оказывается незначительным.

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

, (1.9)

где равенство имеет место только для f (x) =(x).

Пусть (х_i) = f_i. Введем обозначение (x_i) = m_i, i = 0,1,...,N.

Тогда на каждом интервале[x_i_-1, x_i] согласно (1.5)

. (1.10)

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

Поскольку

, (1.11)

находим отсюда односторонние пределы вторых производных:

(1.12)

Из требования непрерывности второй производной в точках х_i (i = 1,2,...,N-1) (х_i+ 0) =(х_i - 0) находим

. (1.13)

Здесь .

Чтобы определить величины m₀, m_i,..., m_N, надо задать два дополнительных условия (так называемые «краевые» условия).

Из всего многообразия краевых условий будем рассматривать только два типа (заданы первые или вторые производные):

1. (а) =(а), (b) =(b)

2. (а) =(а), (b) =(b).

Тогда получим систему для определения m_i:

(1.14)

В (1.14) для условий типа 1:

а для условий типа 2 согласно (1.12):

Матрица системы (1.14) в этих случаях является матрицей с диагональным преобладанием. Такие матрицы невырождены, потому система имеет решение, и притом единственное.

1.5.1 Решение системы линейных уравнений методом прогонки

Во всех рассматриваемых случаях для нахождения величин у_i необходимо решать трехдиагональную систему линейных алгебраических уравнений типа:

(1.15)

Такие системы эффективно решаются методом прогонки. Решение будем искать в виде

y_i = v_i y_i₊₁ + u_i , i = 0,1,2,...,N. (1.16)

Используя выражение для из y_i_-1 (1.16)

y_i_-1 = v_i_-1 y_i + u_i_-1 ,

исключим это неизвестное из i-го уравнения системы (1.15):

c_i y_i-1 + a_i y_i + b_iy_i+1= .

Получим

(a_i + c_i v_i-1) y_i+ b_iy_i+1= - c_i u_i-1. (1.17)

Сравнивая (1.17) с (1.16), выводим рекуррентные формулы для прогоночных коэффициентов v_i, u_i (прямая прогонка):

; (1.18)

, i = 0,1,2,...,N.

Подставив в полученные формулы коэффициенты из системы уравнений 1.14 получим формулы для определения прогоночных коэффициентов

Очевидно, что y_N = u_N. Все остальные неизвестные находятся по формулам (1.16) (обратная прогонка).

m_i = v_i m_i₊₁ + u_i ,

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

Кривы́е Безье́ были разработаны в 60-х годах XX века независимо друг от друга Пьером Безье (Bézier) из автомобилестроительной компании «Рено» и Полем де Кастелье (de Casteljau) из компании «Ситроен», где применялись для проектирования кузовов автомобилей.

Несмотря на то, что открытие де Кастелье было сделано несколько ранее Безье (1959), его исследования не публиковались и скрывались компанией как производственная тайна до конца 1960-х.

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

Кривая Безье — параметрическая кривая, задаваемая выражением

$\mathbf{B}(t)=\sum^n_{i=0} \mathbf{P}_i \mathbf{b}_{i,n}(t),\quad 0<t<1$

где P_i— функция компонент векторов опорных вершин, а b_i_,_n(t) - базисные функции кривой Безье, называемые также полиномами Бернштейна.

$\mathbf{b}_{i,n}(t)={n \choose i} t^i(1-t)^{n-i}$

${n \choose i}=\frac{n!}{i!(n-i)!}$ ,

где n — степень полинома, i — порядковый номер опорной вершины

Виды кривых Безье:

1.6.1 Линейные кривые Безье

При n = 1 кривая представдяет собой отрезок прямой линии, опорные точки P₀ и P₁ определяют его начало и конец. Кривая задаётся уравнением:

$\mathbf{B}(t)=(1-t)\mathbf{P}_0 + t\mathbf{P}_1 \quad t \in [0,1]$ .

Построение линейной кривой Безье

Параметр t в функции, описывающей линейный случай кривой Безье, определяет где именно на расстоянии от P₀ до P₁ находится B(t). Например, при t = 0,25 значение функции B(t) соответствует четверти расстояния между точками P₀ и P₁. Параметр t изменяется от 0 до 1, а B(t) описывает отрезок прямой между точками P₀ до P₁.

1.6.2 Квадратные кривые Безье

Квадратная кривая Безье (n = 2) задаётся 3-я опорными точками: P₀, P₁ и P₂.

$\mathbf{B}(t) = (1 - t)^{2}\mathbf{P}_0 + 2t(1 - t)\mathbf{P}_1 + t^{2}\mathbf{P}_2, \quad t \in [0,1]$ .

Для построения квадратных кривых безье требуется выделение двух промежуточных точек Q₀ и Q₁ из условия чтобы параметр t изменялся от 0 до 1:

Точка Q₀ изменяется от P₀ до P₁ и описывает линейную кривую Безье.

Точка Q₁ изменяется от P₁ до P₂ и также описывает линейную кривую Безье.

Точка B₀ изменяется от Q₀ до Q₁ и описывает квадратную кривую Безье.

Квадратные кривые Безье в составе сплайнов используются для описания формы символов в шрифтах TrueType и в SWF файлах.

1.6.3 Кубические кривые Безье

В параметрической форме кубическая кривая Безье (n = 3) описывается следующим уравнением:

$\mathbf{B}(t) = (1-t)^3\mathbf{P}_0 + 3t(1-t)^2\mathbf{P}_1 + 3t^2(1-t)\mathbf{P}_2 + t^3\mathbf{P}_3, \quad t \in [0,1]$ .

Четыре опорные точки P₀, P₁, P₂ и P₃, заданные в 2-х или 3-мерном пространстве определяют форму кривой.

Линия берёт начало из точки P₀ направляясь к P₁ и заканчивается в точке P₃ подходя к ней со стороны P₂. То есть кривая не проходит через точки P₁ и P₂, они используются для указания её направления. Длина отрезка между P₀ и P₁ определяет, как скоро кривая повернёт к P₃.

В матричной форме кубическая кривая Безье записывается следующим образом:

$\mathbf{B}(t) = \begin{bmatrix}t^3&t^2& t& 1\end{bmatrix}\mathbf{M}_B \begin{bmatrix}\mathbf{P}_0\\\mathbf{P}_1\\\mathbf{P}_2\\\mathbf{P}_3\end{bmatrix}$ ,

где $\mathbf{M}_B$ называется базисной матрицей Безье:

$\mathbf{M}_B = \begin{bmatrix}-1&3&-3&1\\3&-6&3&0\\-3&3&0&0\\1&0&0&0\end{bmatrix}$

В современных графических системах, таких как PostScript, Metafont и GIMP для представления криволинейных форм используются сплайны Безье, составленные из кубических кривых.

Для кубической кривой это промежуточные точки Q₀, Q₁ и Q₂, описывающие линейные кривые, а также точки R₀ и R₁, которые описывают квадратные кривые:

Построение кубической кривой Безье четвёртой степени это будут точки точки Q₀, Q₁, Q₂ и Q₃, описывающие линейные кривые, R₀, R₁ и R₂, которые описывают квадратные кривые, а также точки S₀ и S₁, описывающие кубические кривые Безье:

Построение кривой Безье 4-й степени

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

1.7 B-сплайны

В вычислительной математике B-сплайном называют сплайн-функцию, имеющую наименьший носитель для заданной степени, порядка гладкости и части области определения. Фундаментальная теорема устанавливает, что любая сплайн-функция для заданной степени, гладкости и области определения может быть представлена как линейная комбинация B-сплайнов той же степени и гладкости на той же области определения. Термин B-сплайн был введён И. Шёнбергом и является сокращением от словосочетания «базисный сплайн». B-сплайны могут быть вычислены с помощью алгоритма де Бора, обладающего устойчивостью. В системах автоматизированного проектирования и компьютерной графике термин B-сплайн часто описывает сплайн-кривую, которая задана сплайн-функциями, выраженными линейными комбинациями B-сплайнов.

B-сплайны в сравнении с многочленами Бернштейна обладают следующими дополнительными преимуществами:

1. Аппроксимация B-сплайнами обеспечивает более точное приближение ломаной, чем аппроксимация многочленами Бернштейна.

2. При аппроксимации методом Безье на значения координат каждой точки кривой оказывают влияние все вершины ломаной Безье. Это затрудняет корректирование отдельных участков кривой. В то же время аппроксимация B-сплайнами обладает желательной локальностью. Этим способом можно производить локальные изменения кривой без полного пересчета.

3. Единственным путем увеличения (уменьшения) порядка кривой Безье является увеличение (уменьшение) числа вершин и соответствующей ломаной Безье. В методе B-сплайнов эти два параметра независимы и, следовательно, могут быть выбраны произвольно.

Кривая, построенная на основе B-сплайн-базиса, описывается следующим образом:

где - радиус-вектор точек на кривой,

- вершины аппроксимируемой ломаной (всего вершин n+1),

Nik(t) - весовая функция i-й нормализованной B-сплайн базисной кривой порядка k (т. е. степени k-1), задаваемая рекуррентными соотношениями:

где x_i – элементы узлового вектора, а t – параметр, изменяющийся в диапазоне от 0 до tmax=(n – k+2).

Рис.5.9. Изображение нескольких B-сплайн-кривых различного порядка.

Узловой вектор, длина которого (n+k+1), вводится для учета собственной кривизны B-сплайн-кривых и представляет собой неубывающую последовательность целых чисел - параметрических узлов. Узловой вектор определяется числом точек в аппроксимируемой ломаной, порядком кривой, а также наличием сложных (кратных) узлов.

B-сплайн-кривая является полиномом степени (k–1) на каждом интервале (x_i, x_i+1) и что все ее производные до (k–2)-го порядка включительно непрерывны вдоль всей кривой. То есть эта кривая представляет собой сплайн-функцию порядка k (степени k–1).

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

Рис.5.10. B-сплайн-кривые со сдвоенной вершиной.

В этой вершине в кривой третьего порядка образуется излом

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

1.8 Описание кривых в параметрическом виде

В общем случае в задачах машинного проектирования кривые не могут быть записаны в виде уравнения y = f (x) c использованием обычных однозначных функций. Первая причина этого в том, что формы объектов в технике не должны зависеть от системы координат. Кроме того, кривые инженерных объектов могут иметь вертикальные касательные, что тесно связано с многозначностью функций. Правда, кривая, заданная в неявном виде F (x, y) = 0, свободна от этого недостатка. Но для такой функции при вычислении текущих координат точек приходится каждый раз решать в общем случае нелинейное уравнение F (x, y) = 0 от одного неизвестного х или у.

Поэтому в машинном проектировании ведущую роль играет параметрическое представление участков кривых. Например, кривая на плоскости представляется не функцией вида y = f (x) или F (x, y) = 0, а парой функций x = x (s) и y = y (s) от параметра s (рис 1.5 a,б). Вид самой функции представлен на рисунке 1.5.

a)	б)
c)
Рис. 1.5 Плоская параметрическая сплайн-функция

В общем случае точка на пространственной кривой задается вектор-функцией вида

r = r (s) = x (s) i + y (s) j + z (s) k, (1.19)

где i, j и k - единичные орты декартовой системы координат.

В дальнейшем под функцией r = r (s) будем подразумевать радиус-вектор точки на пространственной кривой , либо одну из следующих функций: x = x (s), y = y (s) или z = z (s) (рис 1.6 а,б,с).

a)	б)	с)

Рис. 1.6 Пространственная (3D) параметрическая сплайн-функция

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

Очевидно, что параметр s лучше всего выразить через длину дуги, однако на практике мы не можем установить длину дуги, пока не вычислим кривую, а чтобы это сделать, нужно знать длину дуги. Наиболее естественен альтернативный подход - использовать накопленную (суммарную) длину хорд, т.е. взяв s₀ = 0, определить

s_i = s_i-1 + | r_i - r_i-1 |, i = 1,2,...,N, (1.20)

где | r_i - r_i_-1 | =.

Можно начать с кривой, параметризованной таким способом, и затем, используя итерационный процесс, получить кривую, параметризованную по длине дуги. Поскольку разница между такими кривыми невелика, ограничиваются параметризацией по суммарной длине хорд. Для этого строят три сплайна, зависящие от s и проходящие через точки (x_i, s_i), (y_i, s_i), (z_i, s_i) соответственно.

Для определения коэффициентов параметрического сплайна необходимо решать три системы методом прогонки. Они различаются только правыми частями. Нетрудно видеть, что в формулах (1.18) величины v_i и a_i + c_i v_i_-1не зависят от правых частей этих систем. Поэтому, если вычислить их и запомнить, для решения каждой из трех систем потребуется меньше арифметических операций.

Суммарная длина хорд - это приближение к длине дуги, поэтому можно считать, что | m_i | = || 1. В таком случае в любом узле кривой можно вычислить производные, если задать дополнительную точку r_g, лежащую на касательной к кривой:

. (1.21)

Из типа 2 краевых условий ограничимся случаем = 0 на краях интервала. Точки, в которых заранее будут задаваться первые производные (или равные нулю вторые производные, если первые производные неизвестны), назовем характерными.

Прогонку для решения систем уравнений будем осуществлять по участкам от одной характерной точки до другой. Таким образом, появляется возможность аппроксимировать кривую, состоящую из (N + 1) точек с (К + 1) характерными точками, где . Очевидно, что первая и последняя точки всегда должны быть характерными. Минимальное количество участков для прогонки - 1, максимальное - N.

Для параметрического кубического сплайна по аналогии с (1.10) можно записать уравнение кривой на участке [s_i_-1, s_i]:

, (1.22)

где h_i = s_i - s_i_-1, u = (s - s_i_-1) / h_i, а m_i- неизвестные векторы, которые определяются из решения трех систем.

Пусть m_i-1 = m_i = , h_i = | r_i - r_i-1 |. (1.23)

Тогда из (1.22) следует, что

- прямая линия.

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

1.9 Практическое использование кубических параметрических сплайнов

1.8.1. Выбор шага интерполяции

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

L² =,

и шаг по параметру

L = 2. (1.24)

Здесь - максимальное отклонение кривой от хорды (рис.1.7);

. (1.25)

1.8.2. Разбиение графической информации

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

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

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

Рис. 1.8 Разбиение графической информации

Найдем координаты точек пересечения кривой с краями листа, а также параметры этих точек. Включим в полученную таблицу начальную и конечную точки кривой. В рассматриваемом примере (рис.1.8)

P₀, P₁, P₂, P₃, P₄, P₅, P₆, P₇, P₈, P_k. (1.26)

Упорядочим точки по возрастанию параметра:

P₀, P₆, P₁, P₂, P₄, P₅, P₃, P₈, P₇, P_k. (1.27)

Выбросим из полученной таблицы одинаковые точки (случай прохождения кривой через угол листа):

P₀, P₆, P₁, P₂, P₄, P₅, P₃, P₇, P_k. (1.28)

После этого можно получить таблицу границ для черчения кривой. Черчение начинается с первого участка, если начальная точка лежит на поле листа; если не лежит, - то со второго.

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

[P₆, P₁], [P₂, P₄], [P₅, P₃], [P₇, P_k]. (1.29)

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

Ax + By + Cz + D = 0,

то все сводится (при использовании кубических параметрических сплайнов) к решению кубического уравнения относительно параметра s:

F (s) = Ax (s) + By (s) + Cz (s) + D = 0. (1.30)

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

Если корни уравнения (1.30) отделены, часто пользуются методом хорд. Если известно хорошее начальное приближение, можно применить метод Ньютона.

1.8.3 Машинные методы построения аксонометрических изображений.

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

Многогранники можно описать двумя способами:

1. Списком ребер, где каждое ребро - прямая, определяемая двумя своими точками .

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

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

Представление технических объектов в ЭВМ должно отвечать следующим требованиям:

1. Компактность и однозначность описания.

2. Легкость построения изображения произвольного многогранника на экране дисплея.

3. Удобство преобразования, деформирования, присоединения объекта к другим объектам.

4. Удобство математического описания для решения метрических и позиционных задач на поверхности.

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

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

Дадим кратко необходимые сведения об однородных координатах.

Точка в пространстве (т.е. в трехмерной системе) с действительными координатами C,U,Z будет в однородных координатах отражаться четырехкомпонентным вектором-строкой [C,U,Z1], где 1 - однородный член, либо как некоторое кратное этого вектора, например [wx wy wz w] , где w - произвольное число.

Точку в однородных координатах можно обозначить строчными буквами [x y z w] , это та же самая точка, поскольку ее координаты C,U,Z всегда можно найти, разделив их на однородный член w, т. е.

C = x / w , U = y / w , Z = z / w.

Таким образом, действительные координаты точки C, U, Z получаются делением компонент вектора-строки на его четвертый компонент.

Пример 1. Уравнение прямой Ax + By = C в матричной форме запишется [ x y ] = C или [x y 1 ]= 0 . Без учета знака С запишем: [ x y w ]= 0 . Назовем [ x y 1 ] - матрицей координат точек и - матрицей координат линий.

Пример 2. Уравнение двух прямых x + y = 1 и 3x - 5y = 0 можно записать в следующем виде:

[ x y ] = [ 10 ] или [x y 1 ] = [ 0 0 ] .

Получим матрицу 3х2 , которую трудно обращать. Проведем преобразование , не нарушающее это равенство , тогда

[ x y w ] = [ x y w ].

Для новой квадратной матрицы легко найти обратную матрицу.

Однородные координаты и матричная запись позволяют сделать уравнения более симметричными и облегчают решение многих задач на ЭВМ.

Пример 3. Параболу x = y²можно представить в параметрическом виде уравнением x = u² . где y = u . Любую точку на этой параболе можно представить в матричной форме уравнением:

[ x y 1 ] = [ u² u 1]= [ u² u 1].

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

1.8.4 Матричное преобразование системы координат

Приведем формулы линейных преобразований:

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

x` = a₁x + b₁y + c₁z + d₁ , x` = a₁x + b₁y + d₁ ,

y` = a₂x + b₂y + c₂z + d₂ , y` = a₂x + b₂y + d₂ ,

z` = a₃x + b₃y + c₃z + d₃ .

Для реализации на ЭВМ удобнее представить их в матричном виде. Матричная форма записи преобразований позволяет представлять последовательность различных преобразований в виде единого преобразования ( совмещение преобразований ) .

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

Рассмотрим одновременно двумерные и трехмерные преобразования, позволяющие легко вычислить координаты новой точки ( x`, y`, z` ) по координатам ( x , y , z ) исходной точки:

[ x` y` z` 1 ] = [ x y z 1 ] ; [ x` y` 1 ] = [ x y 1 ].

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

Частные виды преобразований:

1. Перемещение. Преобразование перемещения ( сдвига ) исходной точки ( x , y , z ) в новое положение ( x`, y`, z` ) выражается в следующей форме:

[ x` y` z` 1 ] = [ x y z 1 ] ; [ x` y` 1 ] = [ x y 1 ] ,

где , , - величины перемещения в направлениях x , y и z соответственно .

2. Вращение. Поворот точки ( x , y ) в двумерном преобразовании на угол j по часовой стрелке относительно начала координат определяется по формуле :

[ x` y` 1 ] = [ x y 1 ].

Вращение в комбинации с перемещением можно использовать для вращения точек плоской фигуры вокруг любой точки. Например , точка ( x , y ) поворачивается на угол j по часовой стрелке относительно какой-либо точки М ( x_М , y_М) .

Уравнение преобразования вращения применяется только для поворота точек относительно начала координат, поэтому вначале необходимо сдвинуть точку ( x , y ) так, чтобы точка М ( x_М , y_М) стала началом координат

[ x` y` 1 ] = [ x y 1 ],

затем произвести поворот точки (x`,y`) на угол j:

[ x`` y`` 1 ] = [ x` y` 1 ] .

Возвратим начало системы координат в исходное положение, т.е. произведем обратный сдвиг:

[ x``` y``` 1 ] = [ x`` y`` 1 ] .

Для конкретных значений x_М , y_М и j можно эту последовательность преобразований представить как одно преобразование (совмещенное). При совмещении не должен нарушаться порядок выполнения преобразований :

[ x`` y`` 1 ] = [ x y 1 ] .

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

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

Вращение вокруг координатной оси X, проходящей через точку (0,0,0), выражается матрицей:

[ x` y` z` 1 ] = [ x y z 1 ] .

Здесь угол поворота j берется по часовой стрелке вокруг начала координат , если смотреть в направлении начала координат из точки, расположенной на положительной полуоси X .

Вращение вокруг координатной оси Y выражается матрицей:

[ x` y` z` 1 ] = [ x y z 1 ] .

Вращение вокруг координатной оси Z, проходящей через начало координат, выражается матрицей:

[ x` y` z` 1 ] = [ x y z 1 ].

Вращение вокруг произвольной оси описывается комбинацией простейших преобразований и выполняется в пять этапов:

1) перенос объекта в новую координатную систему с началом координат в любой точке (x,y,z) на прямой оси вращения (матрица Т);

2) совмещение единичного вектора оси X (0,0,1) с вектором направляющих косинусов (a,b,c) оси вращения путем поворота координатной системы вокруг осей X и Y (матрицы R и Q);

3) поворот новой координатной системы на угол j вокруг оси X (матрица F);

4) выполнение преобразования, обратного произведенному на втором этапе (матрицы R^-1 и Q^-1);

5) выполнение преобразования, обратного произведенному на первом этапе (матрица Т^-1) .

На 4-м и 5-м этапах происходит возвращение объекта в исходную систему координат.

Таким образом, полное преобразование можно записать как

Т R Q F R^-1 Q^-1 Т^-1.

3. Масштабирование. Применяется для увеличения или уменьшения изображения фигуры относительно ее начального размера .

Увеличение или уменьшение фигуры производится относительно начала системы координат по формуле

[ x` y` z` 1 ] = [ x y z 1 ].

Если S_x , S_y , S_z – коэффициенты масштабирования не равны между собой, то это приводит к искажению изображения за счет неодинакового изменения размеров фигуры по направлениям координатных осей.

Отрицательные значения величин S_x , S_y , S_z дают зеркальное отображение фигуры .

1.9 Сглаживающая сплайн-функция

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

Рис. 1.9 Аппроксимация заданных точек

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

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

. (1.31)

Здесь R_i > 0 - некоторые весовые множители, определяющие относительный вес, согласовывающий сглаживание и аппроксимацию; S(х) - дважды непрерывно дифференцируемые функции.

Так как кубический сплайн минимизирует (см. 1.9), то естественно искать решение в классе кубических сплайнов.

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

S” (а) =S” (b) = 0 (1.32)

Так как требовать совпадения значений сплайна и интерполяционной функции в узлах сетки теперь нельзя, получим другое условие, которое будет вытекать из того, что функционал (1.31) минимизируется кубическим сплайном S(х). Для задачи сглаживания более удобно другое представление сплайна, в котором вместо m_i присутствуют вторые производные M_i = . Запишем условие линейности второй производной от кубического сплайна S (х) на участке [x_i_-1, x_i]:

. (1.33)

Здесь h_i = x_i - x_i_-1, M_i - коэффициенты сплайна. Граничными условиями будут M₀ = M_N = 0.

Если рассмотреть выражение Ф. (u - S), где u (x) - любая функция из заданного класса, а S(х) - сглаживающий сплайн, то после некоторых преобразований (интеграл берется по частям и используются граничные условия (1.32)) получим:

Ф (u - S) = Ф (u ) - Ф (S) - 2 с,

где . (1.34)

Если потребовать, чтобы с = 0, то

Ф (u - S) = Ф (u ) - Ф (S) 0 (1.35)

(Ф (u - S) - положительно определенный функционал). Отсюда следует, что Ф (S) Ф (u), т.е. тогда кубический сплайн будет минимизировать рассматриваемый функционал. Из (1.33) можно определить . После простых преобразований условие с = 0 запишется следующим образом:

S (x_i) = y_i - R_i L_i , i = 0,1,...,N, (1.36)

где - (1.37)

скачок третьей производной в i - м узле.

Для единообразия записи здесь введено: M_-1 = M_N₊₁ = 0, h₀ h_N₊₁ 0. Формула (1.36) заменяет условие s(x_i) = y_i интерполяционной задачи.

Для определения коэффициентов M_i (i = 1,2,...,N-1) потребуем, чтобы функция S(х) и ее первая производная (х) были непрерывны в узлах сетки, т.е.

S(x_i - 0) = S(x_i + 0), s’(x_i - 0) = s’(x_i + 0). (1.38)

Дважды интегрируя (1.33) и учитывая (1.36) и (1.38), получим для определения неизвестных коэффициентов систему N - 1 линейных алгебраических уравнений:

c_i-2 M_i-2 + b_i-1 M_i-1 + a_i M_i + b_i M_i+1 + c_i M_i+2 = F_i; (1.39)

a₁ = c₀ = b₀ = 0; b_N-1 = c_N-1 = c_N-2 = 0;

;

i = 1,2,...,N-1

; (1.40)

i = 1,2,...,N-2

; i = 1,2,...,N-3; .

Если весовые множители (R₀, R₁,..., R_N) известны, то после решения пятидиагональной системы (1.39) методом прогонки (когда R_i малы) или методом немонотонной прогонки (при больших значениях R_i) и определения коэффициентов M_i значения сглаживающей функции в узлах находятся из соотношения (1.36).

При R_i = 0 получаем из (1.39) систему уравнений для определения коэффициентов интерполяционного кубического сплайна. Отсюда следует, что чем точнее значение y_i в узлах сетки, тем меньше должны быть величины весовых множителей R_i. Если при сглаживании возникает необходимость закрепить точку с номером k, то для этого надо потребовать, чтобы R_k = 0.

При сглаживании обычно известны ошибки в определении значений y_i, т.е. задаются неравенства

|(x_i) - y_i| (i = 0,1,...,N). (1.41)

Для полного решения задачи сглаживания было предложено строить интерполяционный процесс для определения R_i. Обозначив

E_i =(x_i) - y_i_, (1.42)

из (1.36) и (1.41) получим

. (1.43)

В соответствии с (1.43) построим интерполяционный процесс для определения R_i, используя следующую формулу:

, (1.44)

где j - номер итерации.

Для получения начального приближения естественно положить R_i⁽⁰⁾ = 0 и построить кубический сплайн, проходящий через заданные точки. Ясно, что если L_i⁽^j⁾ = 0, то R_i⁽^j⁺¹⁾ = 0.

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

R_i⁽^j⁺¹⁾ = R_i⁽^j⁾ = R_i⁽^j⁾ . (1.45)

Отсюда видно, что если при j-й итерации для i-й точки неравенство (1.41) не выполнено ( |E_i⁽^j⁾| > ), то R_i⁽^j⁺¹⁾ < R_i⁽^j⁾ , т.е. следующая (j + 1)-я итерация уменьшает весовой множитель R_i. Это способствует уменьшению Е_i. С другой стороны, если на j-й итерации |E_i⁽^j⁾| < и L_i⁽^j⁾ 0, то множитель R_i на следующей итерации увеличивается, что способствует более полному использованию «коридора» (1.41) в целях обеспечения большей гладкости сплайна.

Итерационный процесс должен продолжаться до тех пор, пока значения сплайна (x_i) в узлах сетки не окажутся в «коридоре».

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

= A_i | L_i |. (1.46)

В случае предполагаемых грубых ошибок

A_i = . (1.47)

грубые ошибки не попадаются, то

A_i = . (1.48)

При сглаживании кривых строится параметрический сглаживающий сплайн r (s) = x (s) i + y (s) j + z (s) k как совокупность трех сглаживающих сплайнов. Параметризацию будем брать по суммарной длине хорд. Отметим, что в ходе сглаживания изменяется расстояние между точками и поэтому на каждой итерации необходимо осуществлять пересчет параметров . Пример сглаживания некоторой неоднозначной кривой приведен на рис.1.10

Рис. 1.10 Сглаживание кривой

2. СОСТАВНЫЕ ПОВЕРХНОСТИ

2.1. Общие замечания

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

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

Уравнение поверхности в параметрическом виде в дифференциальной геометрии записывается как

r = r (u, v), (2.1)

где r (u, v) - радиус-вектор точки на поверхности. Это уравнение (2.1) соответствует трем скалярным уравнениям

x = x (u, v);

у = y (u, v); (2.2)

z = z (u, v).

Здесь u и v - параметры, которые изменяются в некотором диапазоне.

2.2 Билинейная интерполяция

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

Рассмотрим одну порцию поверхности представленную точки Q₁₁(x₁,y₁), Q₁₂(x₁,y₂), Q₂₁(x₂,y₁) и Q₂₂(x₂,y₂). Необходимо определить координаты точки P(x,y). Первым шагом интерполируется (линейно) значение вспомогательных точек R₁ и R₂ вдоль оси абсцисс, где

R₁ = (x,y₁)

R₂ = (x,y₂)

$f(R_1) \approx \frac{x_2-x}{x_2-x_1} f(Q_{11}) + \frac{x-x_1}{x_2-x_1} f(Q_{21})$

$f(R_2) \approx \frac{x_2-x}{x_2-x_1} f(Q_{12}) + \frac{x-x_1}{x_2-x_1} f(Q_{22})$

Теперь проводится линейная интерполяция между вспомогательными точками R₁ и R₂.

$f(P) \approx \frac{y_2-y}{y_2-y_1} f(R_1) + \frac{y-y_1}{y_2-y_1} f(R_2).$

Это и есть приблизительное значение функции в точке P, т.е. f(x, y).

$\begin{align} f(x,y) &\approx \frac{f(Q_{11})}{(x_2-x_1)(y_2-y_1)} (x_2-x)(y_2-y) \\ & + \frac{f(Q_{21})}{(x_2-x_1)(y_2-y_1)} (x-x_1)(y_2-y) \\ & + \frac{f(Q_{12})}{(x_2-x_1)(y_2-y_1)} (x_2-x)(y-y_1) \\ & + \frac{f(Q_{22})}{(x_2-x_1)(y_2-y_1)} (x-x_1)(y-y_1). \end{align}$

В случае, когда известные точки находятся на вершинах единичного квадрата, т.е. имеют координаты Q₁₁(0, 0), Q₁₂(0, 1), Q₂₁(1, 0), и Q₂₂ (1, 1), т.е. по сторонам порции параллельным осям вводим параметры u и v, которые

u = (x - x₁) / h_x, где h_x=x₂-x₁

v = (y - y₁) / h_y, где h_y=y₂-y₁

Формулу билинейной интерполяции представляется в таком виде

P(u,v)=Q₁₁(1-u)(1-v)+ Q₁₂u(1-v)+Q₂₁(1-u)v+Q₂₂uv

Или же с помощью умножения векторов с матрицей:

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

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

Билинейная интерполяция применяется для изменения размеров цифровых изображений (обычно увеличение), при закрашивании трехмерных объектов и поверхностей - метод Гуро.

2.3. Поверхности Кунса, определенные тензорным произведением

Допустим, что u и v изменяются в пределах от 0 до 1 вдоль соответствующих границ порции (рис.2.1).

Тогда r (u, v), 0<u, v<1 представляет внутренность порции поверхности; r (u, 0), r (1, v), r (u, 1) и r (0, v) представляют четыре известные граничные кривые. Тем самым задача определения порции поверхности сводится к нахождению функции r (u, v), которая при u = 0, u = 1, v = 0 и v = 1 представляет нужную граничную кривую.

Следуя Кунсу, рассмотрим сначала более простую задачу построения порции поверхности, если заданы только две ее границы: r (u, 0) и r (1, v). Применяя интерполяцию Эрмита (1.22) (только в рассматриваемом случае параметрическая длина равна 1, т.е. h = 1) в u -направлении, получим поверхность:

r₁ (u, v) = (u) r (0, v) + (u) r (1, v) +

+ (u) r_u (0, v) + (u) r_u (1, v), (2.3)

которая интерполирует две граничные кривые r (0, v) и r (1, v) имеет заданные наклоны r_u (0, v) и r_u (1, v) поперек границ.

Точно также можно построить еще одну поверхность, которая будет интерполировать две кривые r (u, 0) и r (u, 1) в v -на правлении:

r₂ (u, v) = (v) r (u, 0) + (v) r (u, 1) +

+ (v) r_v (u, 0) + (v) r_v (u, 1). (2.4)

Легко проверить, что сумма r₁ + r₂ не дает требуемой поверхности. Чтобы ее построить, необходимо вычесть дополнительное слагаемое, получаемое с помощью того же метода интерполяции в обоих направлениях при использовании только информации об угловых точках, т.е.

r (u, v) = r₁ (u, v) + r₂ (u, v) - r₃ (u, v).

Вспомним, что граничные кривые описываются кубическими параметрическими сплайнами с параметрической длиной, равной единице:

r (i, v) = (v) r (i, 0) + (v) r (i, 1) +

+ (v) r_v (i, 0) + (v) r_v (i, 1); (2.5)

r (u, j) = (u) r (0, j) + (u) r (1, j) +

+ (u) r_u (0, j) + (u) r_u (1, j);

i, j = 0,1.

Поперечные градиенты r_u (0, v), r_u (1, v), r_v (u, 0) и r_v (u, 1) определим по аналогии с (2.5):

r_u (i, v) = (v) r_u (i, 0) + (v) r_u (i, 1) +

+ (v) r_uv (i, 0) + (v) r_uv (i, 1);

r_v (u, j) = (u) r_v (0, j) + (u) r_v (1, j) + (2.6)

+ (u) r_uv (0, j) + (u) r_uv (1, j).

После подстановки этих выражений (2.5) и (2.6) в (2.3) и (2.4) оказывается, что все три члена r₁, r₂ и r₃ равны между собой. В результате

r (u, v) = F (u) Q F^T(v), (2.7)

где F (u) = [(u), (u), (u), (u)] - матрица-строка;

F^T (v) = [(v), (v), (v), (v)]^T - матрица-столбец; (2.8)

Т - символ транспонирования;

Q = (2.9)

Заметим, что порция поверхности (2.7) полностью определена через векторы r, r_u, r_v и r_uv в ее четырех углах. Порция поверхности этого типа определяется тензорным (или декартовым) произведением. Понятие «тензорное произведение» связано с тем обстоятельством, что матрица (2.9) зависит не от скаляров, а от векторов, и поэтому представляет собой тензор.

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

Действительно, r_u (u, v) = F_u (u) Q^T F (v). Отсюда r_u (i, v) = (v) r_u (i, 0) + (v) r_u (i, 1) + (v) r_uv (i, 0) + (v) r_uv (i, 1); r_u (i, 0) и r_u (i, 1) непрерывны на каркасе (это коэффициенты кубического параметрического сплайна). Если при этом сделать непрерывными r_uv в углах порции, то составная поверхность будет непрерывна до первой производной.

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

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

2.4. Поверхности на непрямоугольном каркасе

Рассмотрим произвольный каркас поверхности, образованный пересечением s - кривых с t - кривыми. Пусть s_ij, t_ij (i,j = 0,1) значения параметров в узлах конкретной порции (рис.2.2). Обозначим параметрические длины соответствующих граничных кривых через s₀, s₁, t₀ и t₁, т.е. s_i = s_i₁ - s_i₀, t_j = t₁_j - t₀_j.

Граничные кривые порции r (0, v), r (1, v), r (u, 0) и r (u, 1) тогда запишутся следующим образом:

r (i, v) = r (i, 0)(v) + r (i, 1) (v) + [r_t (i, 0)(v) + r_t (i, 1)(v)] t_i;

r (u, j) = r (0, j)(u) + r (1, j) (u) + [r_s (0, j)(u) + r_s (1, j)(u)] s_j.

(2.10)

Построить поверхность Кунса можно только для прямоугольной (или квадратной сетки). Поэтому необходимо определить преобразование

(2.11)

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

Если преобразование уже определено, то

r_u (u, v) = r_s (u, v) s_u (u, v) + r_t (u, v) t_u (u, v);

r_v (u, v) = r_s (u, v) s_v (u, v) + r_t (u, v) t_v (u, v). (2.12)

Отсюда для узлов порции получим

r_u (i, j) = r_s (i, j) s_u (i, j) + r_t (i, j) t_u (i, j);

r_v (i, j) = r_s (i, j) s_v (i, j) + r_t (i, j) t_v (i, j). (2.13)

Но из (2.10) следует, что

r_u (i, j) = r_s (i, j) s_j;

r_v (i, j) = r_t (i, j) t_j . (2.14)

Сопоставляя (2.13) и (2.14), имеем

s_u (i, j) = s_j , s_v (i, j) = 0, (2.15)

t_u (i, j) = 0, t_v (i, j) = t_i . (2.16)

Найдем для примера, преобразование s = s (u, v). В узлах порции эта функция определена: s₀₀, s₁₀, s₀₁, s₁₁. Первые производные задаются соотношениями (2.15). Так как s_u (i, j)0 , а s_v(i, j) = 0, то необходимо потребовать, чтобы s_uv(i, j) = 0. В таком случае преобразование s = s (u, v) согласно (2.7) запишется как

s (u, v) = F (u) F^T(v). (2.17)

После простейших преобразований получим

s (u, v) = [1 - u,u] . (2.18)

Аналогично можно определить, что

t (u, v) = [(u), (u)] . (2.19)

Из (2.18) и (2.19) найдем

s_u (v) = s₀ (v) + s₁(v) ; (2.20)

t_v (u) = t₀ (u) + t₁(u). (2.21)

Формулы (2.20) и (2.21) определяют закон изменения параметрических длин. Параметрическая длина в направлении s меняется от s₀ (на границе v = 0) до s₁ (на границе v = 1) по закону, определенному (2.20). Аналогично для параметрической длины в направлении t (2.21).

Следуя Кунсу, построим поверхность r₁ (u, v) , интерполирующую две граничные кривые r (0, v) и r (1, v) и имеющую заданные наклоны r_s (0, v) и r_s (1, v) поперек границ порции.

Так как r_u (i, v) = r_s (i, v) s_u (v) (из (2.9) t_u (i, v) = 0), то

r₁ (u, v) = r (0, v)(u) + r (1, v)(u) +

+ [r_s (0, v)(u) + r_s(1, v)(u)] s_u(v). (2.22)

Аналогично построим поверхность r₂ (u, v), интерполирующую граничные кривые r (u, 0) и r (u, 1) с соответствующими наклонами r_t (u, 0) и r_t (u, 1) поперек границ порции:

r₂ (u, v) = r (u, 0)(v) + r (u, 1)(v) +

+ [r_t (u, 0)(v) + r_t(u, 1)(v)] t_v(u). (2.23)

Как и прежде,

r (u, v) = r₁ (u, v) + r₂ (u, v) - r₃ (u, v). (2.24)

Здесь r₃ (u, v) получено с помощью того же метода интерполяции (2.19) в обоих направлениях при использовании информации об угловых точках.

Определим поперечные границы r_s (i, v) и r_t(u, j):

r_s (i, v) = r_s (i, 0)(v) + r_s (i, 1) (v) +

+ [r_st (i, 0)(v) + r_st (i, 1)(v)] t_i; (2.25)

r_t (u, j) = r_t (0, j)(u) + r_t(1, j) (u) +

+ [r_st (0, j)(u) + r_st (1, j)(u)] s_j. (2.26)

После соответствующих преобразований получим выражение для r (u, v):

r (u, v) = F (u) Q (u, v) F^T(v), (2.27)

где F (u) и F^T(v) были определены в (2.8), а

Q (u, v) = . (2.28)

Здесь введено обозначение

l_ij = s_u (v) t_i + s_j t_v (u) - s_j t_i, i,j = 0,1; (2.29)

s_u (v) и t_v (u) определяются по формулам (2.20) и (2.21).

Сравним полученное уравнение порции поверхности на непрямоугольной области (2.27) с порцией поверхности Кунса, определенного тензорным произведением (2.7).

Разница состоит в том, что появились множители перед первыми и перекрестными производными. В них учитывается непрямоугольность области. Матрица Q теперь зависит от параметров u и v. При s₀ = s₁ = 1 и t₀ = t₁ = 1 эти множители тождественно равны единице, и, как частный случай, получается поверхность тензорного произведения, определяемая на единичном квадрате. Таким образом, уравнение (2.27) является обобщением описания такой поверхности на произвольный четырехугольник.

Можно проверить, что обеспечивается непрерывность производных r_s и r_t поперек границ порции, что важно, когда переходят к описанию составной поверхности. Рассмотрим, для примера, поведение r_s (i, v).

Из (2.12) следует, что

r_u (u, v) = r_s (u, v) s_u (v) + r_t (u, v) t_u (u, v).

При u = i (i = 0,1)

r_u (i, v) = r_s (i, v) s_u (v), (2.30)

так как t_u (i, v) = 0 (из (2.19)).

Из (2.27) получим

r_u (u, v) = F_u (u) Q (u, v) F^T(v) + F (u) Q_u (u, v) F^T(v).

Тогда при u = i

r_u (i, v) = F_u (i) Q (i, v) F^T(v), (2.31)

так как Q_u (i, v) = 0 (это следует из (2.28)).

Сравнивая (2.30) и (2.31), получим

r_s (i, v) s_u(v) = [r_s (i, 0)(v) + r_s (i, 1) (v) +

+ r_st (i, 0) t_i(v) + r_st (i, 1)t_i(v)] s_u (v)

или

r_s (i, v) = r_s (i, 0)(v) + r_s (i, 1) (v) +

+ [r_st (i, 0)(v) + r_st (i, 1)(v)] t_i.

Итак, производная r_s(i, v) поперек границ u = i (i = 0,1) зависит лишь от значений r_s (i, 0) и r_s (i, 1) в углах этих границ (t_i - общая граница двух соседних порций). Следовательно, если r_s (i, 0), r_s (i, 1), r_st (i, 0) и r_st (i, 1) одинаковы на границах двух порций, то составная поверхность будет иметь непрерывный градиент поперек этих границ.

2.5. Определение коэффициентов поверхности

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

r, s, r_s, t, r_t, r_st,

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

Для обозначения набора точек r₀₀, r₁₀,..., r_NK используем символ r_ij (i = 0,1,...,N). Здесь (N + 1) - число кривых второго семейства каркаса; j = 0,1,...,K, где (K + 1) - число кривых первого семейства каркаса (рис.2.3).

Процесс определения коэффициентов поверхности по массиву точек будет состоять в следующем.

1) Вычисляются сплайновые кривые в s- направлении через (К + 1) наборов точек r_i₀, r_i₁,..., r_ik, i = 0,1,...,N. Каждая кривая требует дополнительных условий в характерных точках (либо задания наклонов r_s, либо, если наклоны неизвестны, r_ss = 0).

2) Вычисляются сплайновые кривые, проходящие в t - направлении через (N + 1) наборов точек r₀_j, r₁_j,..., r_Nj, (j = 0,1,...,K). При этом используются заданные значения r_t в характерных точках (или r_tt = 0, если наклоны неизвестны).

В результате на шагах 1) и 2) получаем сетку аппроксимированных кривых, т.е. во всех узлах каркаса r, s, r_s, t, r_t могут рассматриваться как известные.

3) В s - направлении вычисляются (К + 1) сплайнов, соответствующих наборам векторов градиентов r_t_,_i₀; r_t_,_i₁;...; r_t_,_ik(i = 0,1,...,N). Для этих вычислений необходимы значения r_s_t в характерных точках, а поскольку такие значения получить нельзя, предполагается, что в характерных точках равна нулю более старшая производная по s, а именно r_sts = 0. Коэффициенты таких сплайновых кривых и есть неизвестные производные r_st в узлах каркаса.

Теперь известны все элементы всех Q-тензоров, поэтому формула (2.15) может быть использована для построения каждой порции составной поверхности.

3. УДАЛЕНИЕ НЕВИДИМЫХ ЛИНИЙ И ПОВЕРХНОСТЕЙ

3.1 Общие замечания

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

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

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

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

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

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

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

3.2 Построение графика функции двух переменных

Рассмотрим сначала задачу построения графика функции двух переменных z = f (x, y) в виде сетки координатных линий x = const и y = const.

Будем рассматривать параллельное проектирование, при котором проекцией вертикальной линии на картинной плоскости (экране) является вертикальная линия. Легко убедиться в том, что в этом случае точка p (x, y, z) переходит в точку ((p, e₁), (p, e₂)) на картинной плоскости, где

e₁ = (cos , sin , 0),

e₂ = (sin sin , -cos sin , cos ),

а направление проектирования имеет вид

e₃ = (sin cos , -cos cos , -sin ),

где , .

Рассмотрим сначала построение графика функции в виде набора линий, соответствующих постоянным значениям y, считая, что углы и подобраны таким образом, что при y₁<y₂ плоскость у = у₁ расположена ближе к картинной плоскости, чем плоскость у = у₂.

Заметим, что каждая линия семейства z = f (x, y_i) лежит в своей плоскости y = y_i , причем все эти плоскости параллельны и, следовательно, не могут пересекаться. Из этого следует, что при y_j>y_i линия z = f (x, y_j) не может закрывать линию z = f (x, y_i).

3.3 Удаление невидимых линий

3.3.1 Метод плавающего горизонта

Алгоритм построения графика функции z = f (x, y) когда линии рисуются в порядке удаления (возрастания у) и при рисовании очередной линии рисуется только та ее часть, которая не закрывается ранее нарисованными линиями такой алгоритм называется методом плавающего горизонта.

Для определения частей линии z = f (x, y_k), которые не закрывают ранее нарисованные линии, вводятся так называемые линии горизонта, или контурные линии.

Пусть проекцией линии z = f (x, y_k) на картинную плоскость является линия Y = Y_k(X), где (X, Y) - координаты на картинной плоскости, причем Y соответствует вертикальной координате. Контурные линии Y^k_max(X) и Y^k_min(X) определяются следующими соотношениями:

Y^k_max(X) =Y_i(X),

Y^k_min(X) =Y_i(X).

На экране рисуются только те части линии Y = Y_k(X), которые находятся выше линии Y^k_max(X) или ниже линии Y^k_min(X) (рис 3.1) .

Одной из наиболее простых и эффективных реализаций данного метода является растровая реализация, при которой в области задания исходной функции вводится сетка

(x_i, y_j), i = 1,...,n₁, j = 1,...,n₂

и каждая из линий Y = Y_k(X) представляется в виде ломаной. Для рисования сегментов этой ломаной используется модифицированный алгоритм Брезенхейма, который перед выводом очередного пиксела сравнивает его ординату с верхней и нижней контурными линиями, представляющими собой в этом случае массивы значений ординат. Случай отрезков с угловым коэффициентом большим 1 требует специальной обработки (для того, чтобы не появлялись выпадающие пикселы).

Рассмотрим теперь задачу построения полутонового изображения графика функции z = f (x, y).

Как и ранее, введем сетку

(x_i, y_j), i = 1,...,n₁, j = 1,...,n₂

и затем приблизим график функции набором треугольных граней с вершинами в точках (x_i, y_j, f(x_i, y_j)).

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

Для определения порядка, в котором должны выводится грани, воспользуемся тем, что треугольники, лежащие в полосе

(x, y), ,

не могут закрывать треугольники из полосы

(x, y), .

Рис 3.1 Удаление невидимых линий методом плавающего горизонта

a=(x-p)²+(y-p)²

Z(x,y)=0.2sin(x)cos(y)-1.5cos(7a/4)e^-a

3.3.2 Алгоритм Робертса

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

Опишем этот алгоритм.

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

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

· грань не закрывает ребро;

· грань полностью закрывает ребро (и оно тогда удаляется из списка рассматриваемых ребер);

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

Если общее количество граней равно n, то временные затраты для данного алгоритма составляют О (n²).

Можно заметно сократить количество проверок, если воспользоваться разбиением картинной плоскости.

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

Несмотря на то, что этот вариант алгоритма требует определенных затрат для построения разбиения и соответствующих списков, при удачном выборе разбиения он имеет порядок О (n).

3.3.3 Алгоритм Аппеля

Введем понятие так называемой количественной невидимости точки как количества лицевых граней, ее закрывающих.

Точка является видимой только в том случае, когда ее количественная невидимость равна нулю.

Рассмотрим, как меняется количественная невидимость вдоль ребра.

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

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

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

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

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

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

Так как для реальных объектов количество ребер, входящих в контурную линию, намного меньше общего числа ребер, то алгоритм Аппеля является более эффективным, чем алгоритм Робертса.

Замечание

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

3.4 Удаление невидимых граней

3.4.1 Отсечение нелицевых граней

Рассмотрим многогранник, для каждой грани которого задан единичный вектор внешней нормали. Несложно заметить, что если вектор нормали грани n составляет с вектором l, задающим направление проектирования, тупой угол, то эта грань заведомо не может быть видна. Такие грани называются нелицевыми. В случае, когда соответствующий угол является острым, грань называется лицевой.

В случае параллельного проектирования условия на угол можно записать в виде

(n, 1) 0,

поскольку направление проектирования l от грани не зависит.

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

l = с -р.

Для определения того, является заданная грань лицевой или нет, достаточно взять произвольную точку р этой грани и проверить выполнение условия

(n, 1) 0.

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

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

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

3.42 Метод z- буфера

Одним из самых простых алгоритмов удаления невидимых граней и поверхностей является метод z- буфера (буфера глубины). В силу крайней простоты этого метода часто встречаются его аппаратные реализации.

Сопоставим каждому пикселу (х, у) картинной плоскости, кроме цвета, хранящегося в видеопамяти, его расстояние до картинной плоскости вдоль направления проектирования z (х, у) (его глубину).

Изначально массив глубин инициализируется +.

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

Замечание

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

3.4.3 Алгоритмы упорядочения

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

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

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

3.4.4 Метод сортировки по глубине

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

Этот метод великолепно работает для ряда сцен, включая, например, построение изображения нескольких непересекающихся достаточно простых тел.

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

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

Перед выводом грани Р следует убедиться, что никакая другая грань Q, проекция которой на ось Oz пересекается с проекцией грани Р, не может закрываться гранью Р. И если это условие выполнено, то грань Р должна быть выведена раньше. Предлагаются следующие 5 тестов в порядке возрастания сложности проверки:

1. Пересекаются ли проекции этих граней на ось Ох?

2. Пересекаются ли их проекции на ось Оy?

3. Находится ли грань Р по другую сторону от плоскости, проходящей через грань Q, чем начало координат (наблюдатель)?

4. Находится ли грань Q по ту же сторону от плоскости, проходящей через грань Р, что и начало координат (наблюдатель)?

5. Пересекаются ли проекции этих граней на картинную плоскость?

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

3^|. Находится ли грань Q по другую сторону от плоскости, проходящей через грань Р, чем начало координат?

4^|. Находится ли грань Р по ту же сторону от плоскости, проходящей через грань Q, что и начало координат?

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

3.4.5 Метод двоичного разбиения пространства

Существует другой, крайне элегантный способ упорядочивания граней.

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

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

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

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

В результате мы приходим к дереву разбиения пространства (Binary Space Partitioning), узлами которого являются грани.

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

· получить как можно более сбалансированное дерево;

· минимизировать количество разбиений.

К сожалению, эти критерии, как правило, являются взаимоисключающими, поэтому выбирается некоторый компромиссный вариант.

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

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

3.4.6 Метод построчного сканирования

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

Подобные алгоритмы с успехом используются для создания компьютерных игр типа Wolfenstein 3d.

Рассмотрим, каким путем возможно применение этого метода для создания игры типа Wolfenstein 3d.

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

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

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

3.4.7 Алгоритм Варнака

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

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

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

4. ЗАКРАШИВАНИЕ

4.1 Закрашивание диффузионных и зеркальных поверхностей

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

Подпись:

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

Подпись:

а)	б)	В)
Рис 4.2

Свойство отраженного света зависят от формы и направления источника света, а также от ориентации освещаемой поверхности и ее свойств. Свет, отраженный от объекта, может быть диффузным и зеркальным: диффузно отраженный свет рассеивается равномерно по всем направлениям (Ламбертовая поверхность см. рисунок 4.2 а)), зеркальное отражение происходит от внешней поверхности объекта (рис. 4.2 б). На рисунке 4.2 в показана поверхность, имеющая как диффузную, так и зеркальную характеристики. Примеры поверхностей, имеющие диффузную и зеркальную характеристики представлены на рисунках 4.3 и 4.4 соответственно.

Рис. 4.3 Зеркальная поверхность

Рис. 4.4 Диффузионная поверхность (Ламбертовая)

Рис 4.5

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

I = I_i k_dcos , (4.1)

где I - интенсивность отраженного света;

I_i - интенсивность точечного источника ();

k_d - коэффициент диффузного отражения (постоянная величина, );

- угол между направлением на источник света и (внешней) нормалью к поверхности, (рис 4.5).

Пусть дана точка M (рис. 4.5) на поверхности объекта и необходимо определить интенсивность диффузионного отраженного света из этой точки. Положение точки М относительно начала системы координат задана вектором (m_x,m_y,m_z) и известен вектор нормали к поверхности объекта в точке M обозначим через (n_x,n_y,n_z),где n_x,n_y,n_z – составляющие этого вектора по осям, а вектор, направленный на источник света обозначим через (s_x,s_y,s_z). Положение источника света относительно начала системы координат задан вектором (s_xi,s_yi,s_zi) тогда вектор направленный на источник света из заданной точки M определяется по формуле

Косинус угла между векторами и определяется по формуле

(4.2)

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

I = I_a k_a+I_i k_dcos , , (4.3)

где I_a - интенсивность рассеянного света;

k_a - (постоянный) коэффициент диффузного отражения рассеянного света, .

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

I_z = I_i k_zcos^p, (4.4)

где I_z - интенсивность зеркально отраженного света

k_z - экспериментальная постоянная (коэффициент зеркального отражения );

- угол между отраженным лучом и вектором наблюдения (направление на камеру) ;

р - степень, аппроксимирующая пространственное распределение света (величина, влияющая на размер блика на поверхности объекта ).

Составляющие вектора отраженного луча (r_x,r_y,r_z) при зеркальном отражении определяются с помощью следующих формул

Положение точки наблюдения (камеры) K относительно начала системы координат задана вектором (k_xi,k_yi,k_zi) вектор наблюдения (направление на камеру) из заданной точки M будет определен по формуле

Косинус угла между векторами и определяется по формуле

Объединяя последние две формулы (4.3) и (4.4), получаем модель освещения (функцию закраски), используемую для расчета интенсивности (или тона) точек поверхности объекта (или пикселов изображения):

I = I_a k_a+ I_i(k_d cos + k_scos^p). (4.5)

Замечание

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

В случае, когда точечных источников света несколько, то значение интенсивности отраженного света в некоторой точке определяется как сумма значений интенсивности отраженного света от каждого источника света. Если освещаемая поверхность в рассматриваемой точке гладкая (имеет касательную плоскость), то вектор внешней нормали вычисляется непосредственно. Пусть закрашиваемая поверхность задана неявном виде F(x,y,z)=0. Если дана явная функция, то эту функцию всегда можно представить в неявном виде путем переноса в левую часть уравнения определяемое значение. Для определения вектора нормали n(n_x,n_y,n_z) в некоторой точке N(x_N,y_N,z_N) необходимо определить частные производные F_x, F_y, F_z, по переменным x,y,z и в полученные уравнения подставить координаты точки, для которой определяется нормаль.

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

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

A_ix + B_i y + C_i z + D_i = 0, i = 1,...,m.

Можно считать, что нормальные векторы этих плоскостей

(A_i, B_i, C_i), i = 1,...,m,

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

(А, В, С) =(A_i, B_i, C_i).

Замечание

Для определения направления приближенной нормали в точке, лежащей на ребре многогранной поверхности, достаточно сложить векторы внешних нормалей, примыкающих к этому ребру граней рассматриваемой поверхности. Можно поступить и по-иному. А именно, аппроксимировать переменный вектор нормали вдоль ребра многогранной поверхности при помощи уже найденных векторов внешних нормалей в вершинах, прилегающих к рассматриваемому ребру.

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

V₁V₂V₁V₃, V₁V₃V₁V₄, V₁V₄V₁V₂.

Замечание

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

Для отыскания направления вектора отражения напомним, что единичные векторы - падающего света l, нормали к поверхности n и отражения r лежат в одной плоскости, причем угол падения равен углу отражения.

Рассмотрим модель освещения с одним точечным источником и предположим, что свет падает вдоль оси Z. Тогда координаты единичного вектора отражения

r = (r_x, r_y, r_z)

определяются по формулам

r_x = 2n_x n_z,

r_y = 2n_y n_z,

r_z = 2n²_z - 1,

где n = (n_x, n_y, n_z) - единичный вектор нормали к поверхности.

Если же свет от источника падает не по оси аппликат, то проще всего поступить так: выбрать новую координатную систему так, чтобы ее начало совпадало с рассматриваемой точкой, касательная плоскость к поверхности была плоскостью ху, а нормаль к поверхности в этой точке шла вдоль оси Z. В этой новой системе координат векторы r и l будут связаны соотношениями

r_x = -l_x, r_y = -l_y, r_z = l_z.

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

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

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

Опишем два известных метода построения сглаженных изображений.

4.2 Закраска методом Гуро

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

Пусть дана выпуклая четырехугольная грань. Предположим, что интенсивности в ее вершинах V₁, V₂, V₃ и V₄ известны и равны соответственно I_V₁, I_V₂, I_V₃ и I_V₄.

Пусть W - произвольная точка грани. Для определения интенсивности (освещенности) в этой точке проведем через нее горизонтальную прямую. Обозначим через U и V точки пересечения проведенной прямой с границей грани.

Будем считать, что интенсивность на отрезке UV изменяется линейно, то есть

I_W = (1 - t)I_U + t I_V,

где t =, .

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

Тогда интенсивность в точках U и V вычисляется по формулам

I_U = (1 - u)I_V4 + u I_V1,

I_V = (1 - v)I_V1 + v I_V2,

где u =, , v =, .

Метод Гуро обеспечивает непрерывное изменение интенсивности при переходе от одной грани к другой без разрывов и скачков.

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

Таким образом, процесс рисования грани слагается из следующих шагов:

1) проектирование вершин грани на экран;

2) отыскание интенсивностей в вершинах по формуле (4.3);

3) определение координат концов очередного отрезка и значений интенсивности в их линейной интерполяции;

4) рисование отрезка с линейным изменением интенсивности между его концами.

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

n =,

где a₁,...,a_k - произвольные весовые коэффициенты.

2. Дефекты изображения, возникающие при закраске Гуро, частично объясняются тем, что этот метод не обеспечивает гладкости изменения интенсивности.

4.3 Закраска методом Фонга

Как и описанный выше метод закраски Гуро, закраска Фонга при расчете интенсивности также опирается на интерполирование. Однако, в отличие от метода Гуро, здесь интерполируется не значение интенсивности по уже известным ее значениям в опорных точках, а значение вектора внешней нормали, которое затем используется для вычисления интенсивности пиксела. Поэтому закраска Фонга требует заметно большего объема вычислений. Правда, при этом изображение получается более близким к реалистичному (в частности, при закраске Фонга зеркальные блики выглядят довольно правдоподобно).

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

Для определения вектора «нормали» n_W в точке W проводим через эту точку горизонтальную прямую и, используя значения векторов «нормалей» n_U и n_V в точках ее пересечения U и V с ребрами грани, получаем

n_W =,

где t =,

а векторы внешних нормалей в точках U и V находятся, в свою очередь (также линейной интерполяцией), по векторам нормалей в концевых точках соответствующих ребер рассматриваемой многоугольной грани:

n_U = (1 - u) n_V4 + u n_V1,

n_V = (1 - v) n_V1 + v n_V2,

где u =, v =.

Нормирование вектора n_W необходимо в следствие того, что в формулах (1) - (5) используется единичный вектор нормали.

5. OpenGL

5.1 Введение

OpenGL (Open Graphics Library — открытая графическая библиотека) — спецификация, определяющая независимый от языка программирования кросс-платформенный программный интерфейс для написания приложений, использующих двумерную и трёхмерную компьютерную графику. Включает более 250-ти функций для рисования сложных трёхмерных сцен из простых примитивов. Используется при создании видео-игр, САПР, виртуальной реальности, визуализации в научных исследованиях. На платформе Windows конкурирует с DirectX.

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

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

Silicon Graphics Incorporated (SGI) специализировалась на создании высокотехнологического графического оборудования и программных средств. Являясь в то время лидером в трёхмерной графике, SGI видела проблемы и барьеры в росте рынка. Поэтому было принято решение стандартизировать метод доступа к графической аппаратуре на уровне программного интерфейса. Таким образом появился программный интерфейс OpenGL, который стандартизирует доступ к графической аппаратуре, путем смещения ответственности за создание аппаратного драйвера на производителя графического устройства. Это позволило разработчикам программного обеспечения использовать более высокий уровень абстракции от графического оборудования, что значительно ускорило создание новых программных продуктов и снизило на них затраты.

В 1992 году компания SGI возглавила OpenGL ARB — группу компаний по разработке спецификации OpenGL. OpenGL эволюционировал из 3D-интерфейса SGI — IRIS GL. Одним из ограничений IRIS GL было то, что он позволял использовать только возможности, поддерживаемые оборудованием; если возможность не была реализована аппаратно, приложение не могло её использовать. OpenGL преодолевает эту проблему за счёт программной реализации возможностей, не предоставляемых аппаратно, что позволяет приложениям использовать этот интерфейс на относительно маломощных системах…

Когда в 1995 году была выпущена библиотека Direct3D, Microsoft, SGI и Hewlett-Packard начали проект под названием Fahrenheit, который предусматривал создание более универсального программного интерфейса на основе Direct3D и OpenGL.

По сравнению с DirectX, главной проблемой OpenGL является Консорциум, в который входит большое количество компаний с различными интересами, что приводит к длительному периоду принятия новой версии спецификации. OpenGL версии 2.0 была представлена 3Dlabs в ответ на беспокойства относительно медленного развития и нечеткого направления OpenGL. 3Dlabs предложила ряд существенных дополнений к стандарту, наиболее значимым из которого было добавление к ядру OpenGL шейдерного языка GLSL (OpenGL Shading Language). Это позволяет программисту заменить фиксированный конвейер OpenGL небольшими программами на специальном языке для создания различных эффектов, таких как bump mapping, normal mapping, paralax mapping, HDR и т.д..

5.1.1 Спецификация

На базовом уровне, OpenGL — это просто спецификация, то есть документ, описывающий набор функций и их точное поведение. Производители оборудования на основе этой спецификации создают реализации — библиотеки функций, соответствующих набору функций спецификации. Реализация использует возможности оборудования там, где это возможно. Если аппаратура не позволяет реализовать какую-либо возможность, она должна быть эмулирована программно. Производители должны пройти специфические тесты (conformance tests — тесты на соответствие) прежде чем реализация будет классифицирована как OpenGL реализация. Таким образом, разработчикам программного обеспечения достаточно научиться использовать функции, описанные в спецификации, оставив эффективную реализацию последних разработчикам аппаратного обеспечения.

Эффективные реализации OpenGL существуют для Windows, Unix-платформ, PlayStation 3 и Mac OS. Эти реализации обычно предоставляются изготовителями видеоадаптеров и активно используют возможности последних. Существуют также чисто программные реализации спецификации OpenGL, одной из которых является библиотека Mesa. Из лицензионных соображений Mesa является «неофициальной» реализацией OpenGL, хотя полностью с ней совместима на уровне кода.

Спецификация OpenGL пересматривается Консорциумом ARB (Architecture Review Board), который был сформирован в 1992 году. Консорциум состоит из компаний, заинтересованных в создании широко распространённого и доступного API. Согласно официальному сайту OpenGL, членами ARB с решающим голосом на ноябрь 2004 года являются производители профессиональных графических аппаратных средств SGI, 3Dlabs, Matrox и Evans & Sutherland (военные приложения), производители потребительских графических аппаратных средств ATI и NVIDIA, производитель процессоров Intel, и изготовители компьютеров и компьютерного оборудования IBM, Apple, Dell, Hewlett-Packard и Sun Microsystems, а также один из лидеров компьютерной игровой индустрии id Software. Microsoft, один из основоположников Консорциума, покинула его в марте 2003 года. Помимо постоянных членов, каждый год приглашается большое количество других компаний, становящихся частью OpenGL ARB в течение одного года. Такое большое число компаний, вовлеченных в разнообразный круг интересов, позволило OpenGL стать прикладным интерфейсом широкого назначения с большим количеством возможностей.

Курт Экелей (Kurt Akeley) и Марк Сегал (Mark Segal) являются авторами оригинальной спецификации OpenGL. Крис Фрэзиер (Chris Frazier) редактировал версию 1.1. Йон Лич (Jon Leech) редактировал версии с 1.2 по настоящую версию 2.0.

5.1.2 Архитектура

OpenGL ориентируется на следующие две задачи:

· Скрыть сложности адаптации различных 3D-ускорителей предоставляя разработчику единый API.

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

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

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

5.1.3 Расширения

Стандарт OpenGL, с появлением новых технологий, позволяет отдельным производителям добавлять в библиотеку функциональность через механизм расширений. Расширения распространяются с помощью двух составляющих: заголовочный файл, в котором находятся прототипы новых функций и констант, а также драйвер устройства, поставляемого разработчиком. Каждый производитель имеет аббревиатуру, которая используется при именовании его новых функций и констант. Например, компания NVIDIA имеет аббревиатуру NV, которая используется при именовании ее новых функций, как, например, glCombinerParameterfvNV(), а также констант, GL_NORMAL_MAP_NV. Может случиться так, что определённое расширение могут реализовать несколько производителей. В этом случае используется аббревиатура EXT, например, glDeleteRenderbuffersEXT. В случае же, когда расширение одобряется Консорциумом ARB, оно приобретает аббревиатуру ARB и становится стандартным расширением. Обычно, расширения, одобренные Консорциумом ARB, включаются в одну из последующих спецификаций OpenGL.

5.1.4 Дополнительные библиотеки

Существует ряд библиотек, созданных поверх или в дополнение к OpenGL. Например, библиотека GLU, являющаяся практически стандартным дополнением OpenGL и всегда её сопровождающая, построена поверх последней, то есть использует её функции для реализации своих возможностей. Другие библиотеки, как, например, GLUT и SDL, созданы для реализации возможностей, недоступных в OpenGL. К таким возможностям относятся создание интерфейса пользователя (окна, кнопки, меню и др.), настройка контекста рисования (область рисования, использующаяся OpenGL), обработка сообщений от устройств ввода/вывода (клавиатура, мышь и др.), а также работа с файлами. Обычно, каждый оконный менеджер имеет собственную библиотеку-расширение для реализации вышеописанных возможностей, например, WGL в Windows или GLX в X Window System, однако библиотеки GLUT и SDL являются кросс-платформенными, что облегчает перенос написанных приложений на другие платформы.

Библиотеки, как GLEW («The OpenGL Extension Wrangler Library») и GLEE («The OpenGL Easy Extension library») созданы для облегчения работы с расширениями и различными версиями OpenGL. Это особенно актуально для программистов в Windows, так как, заголовочные и библиотечные файлы, поставляемые с Visual Studio, находятся на уровне версии OpenGL 1.1.

OpenGL имеет только набор геометрических примитивов (точки, линии, многоугольники) из которых создаются все трёхмерные объекты. Порой подобный уровень детализации не всегда удобен при создании сцен. Поэтому поверх OpenGL были созданы более высокоуровневые библиотеки, такие как Open Inventor и VTK. Данные библиотеки позволяют оперировать более сложными трёхмерными объектами, что облегчает и ускоряет создание трёхмерной сцены.

5.1.5 Независимость от языка программирования

Для подтверждения независимости от языка программирования были разработаны различные варианты привязки (binding) функций OpenGL или полностью перенесены на другие языки. Одним из примеров может служить библиотека Java 3D, которая может использовать аппаратное ускорение OpenGL. Прямая привязка функций реализована в Lightweight Java Game Library[2], которая имеет прямую привязку OpenGL для Java. Sun также выпустила версию Java OpenGL (JOGL), которая предоставляет прямую привязку к Си-функциям OpenGL, в отличие от Java 3D, которая не имеет столь низкоуровневой поддержки. Официальный сайт OpenGL имеет ссылки на привязки для языков Java, Фортран 90, Perl, Pike, Python, Ada, Visual Basic и Pascal. Имеются также варианты привязки OpenGL для языков C++ и C#.

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

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

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

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

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

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

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

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

5.2.1 Архитектура и особенности синтаксиса

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

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

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

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

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

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

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

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

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

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

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

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

Command_name имя команды

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

[b s i f d ub us ui ]тип аргумента:

b означает тип GLbyte (аналог char в С\С++),

f тип GLfloat (аналог float),

i– тип GLint(аналог int)

s - GLshort короткое целое

d - GLdouble дробное с двойной точностью

ub - GLubyte беззнаковый байт

us - GLushort беззнаковое короткое целое

ui - GLuint беззнаковое целое

v - массив из n параметров указанного типа.

Полный список типов и их описание можно посмотреть в файле gl.h

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

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

glBegin(GL_LINES);

glVertex2f(0,2);

glVertex2f(10,6);

glEnd;

glColor3d(1,0,0);

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

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

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

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

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

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

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

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

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

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

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

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

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_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 цвета --//

glutInitDisplayMode(GLUT_RGBA | GLUT_DOUBLE | GLUT_DEPTH);

//-- Регистрация вызываемых функций --//

glutDisplayFunc(MyDisplay);

glutIdleFunc(MyIdle);

//-- Запуск механизма обработки событий --//

glutMainLoop();

};

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

5.2.3 Вершины и примитивы

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

void glVertex[2 3 4][s i f d](type coords)

void glVertex[2 3 4][s i f d]v(type *coords)

Координаты точки задаются максимум четырьмя значениями: x, y, z, w, при этом можно указывать два (x,y) или три (x,y,z) значения, а для остальных переменных в этих случаях используются значения по умолчанию: z=0, w=1. Как уже было сказано выше, число в названии команды соответствует числу явно задаваемых значений, а последующий символ – их типу.

Координатные оси расположены так, что точка (0,0) находится в левом нижнем углу экрана, ось x направлена влево, ось y- вверх, а ось z- из экрана. Это расположение осей мировой системы координат, в которой задаются координаты вершин объекта, другие системы координат будут рассмотрены ниже.

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

void glBegin(GLenum mode)

void glEnd(void)

Параметр mode определяет тип примитива, который задается внутри и может принимать следующие значения:

GL_POINTS каждая вершина задает координаты некоторой точки.
GL_LINES каждая отдельная пара вершин определяет отрезок; если задано нечетное число вершин, то последняя вершина игнорируется.
GL_LINE_STRIP каждая следующая вершина задает отрезок вместе с предыдущей.
GL_LINE_LOOP отличие от предыдущего примитива только в том, что последний отрезок определяется последней и первой вершиной, образуя замкнутую ломаную.
GL_POLYGON последовательно задаются вершины выпуклого многоугольника
GL_TRIANGLES каждая отдельная тройка вершин определяет треугольник; если задано не кратное трем число вершин, то последние вершины игнорируются.
GL_TRIANGLE_STRIP каждая следующая вершина задает треугольник вместе с двумя предыдущими.
GL_TRIANGLE_FAN треугольники задаются первой и каждой следующей парой вершин (пары не пересекаются).
GL_QUADS каждая отдельная четверка вершин определяет четырехугольник; если задано не кратное четырем число вершин, то последние вершины игнорируются.
GL_QUAD_STRIP четырехугольник с номером n определяется вершинами с номерами 2n-1, 2n, 2n+2, 2n+1.

Для задания текущего цвета вершины используются команды

void glColor[3 4][b s i f](GLtype components)

void glColor[3 4][b s i f]v(GLtype components)

Первые три параметра задают R, G, B компоненты цвета, а последний параметр определяет alpha-компоненту, которая задает уровень прозрачности объекта. Если в названии команды указан тип ‘f’ (float), то значения всех параметров должны принадлежать отрезку [0,1], при этом по умолчанию значение alpha-компоненты устанавливается равным 1.0, что соответствует полной непрозрачности. Если указан тип ‘ub’ (unsigned byte), то значения должны лежать в отрезке [0,255].

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

Для управления режимом интерполяции цветов используется команда void glShadeModel(GLenummode) вызов которой с параметром GL_SMOOTH включает интерполяцию (установка по умолчанию), а с GL_FLAT отключает.

Например, чтобы нарисовать треугольник с разными цветами в вершинах, достаточно написать:

GLfloat BlueCol[3]={0,0,1};

glBegin(GL_TRIANGLE);

glColor3f(1.0, 0.0, 0.0); //красный

glVertex3f(0.0, 0.0, 0.0);

glColor3ub(0,255,0); //зеленый

glVertex3f(1.0, 0.0, 0.0);

glColor3fv(BlueCol); //синий

glVertex3f(1.0, 1.0, 0.0);

glEnd();

Для задания цвета фона используется команда void glClearColor(GLclampf red, GLclampf green, GLclampf blue, GLclampf alpha). Значения должны находиться в отрезке [0,1] и по умолчанию равны нулю. После этого вызов команды void glClear(GLbitfield mask) с параметром GL_COLOR_BUFFER_BIT устанавливает цвет фона во все буфера, доступные для записи цвета (иногда удобно использовать несколько буферов цвета).

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

void glNormal3[b s i f d](type coords)

void glNormal3[b s i f d]v(type coords)

Задаваемый вектор может не иметь единичной длины, но он будет нормироваться автоматически в режиме нормализации, который включается вызовом команды glEnable(GL_NORMALIZE).Команды

void glEnable(GLenum mode)

void glDisable(GLenum mode)

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

Вообще, внутри командных скобок glBegin() и glEnd() можно производить вызов лишь нескольких команд, в которые входят glVertex..(), glColor..()glNormal..(), glRect..(), glMaterial..() и glTexCoord..().

Последние две команды будут рассматриваться ниже, а с помощью команды void glRect[s i f d]( GLtype x1, GLtype y1, GLtype x2, GLtype y2 ), void glRect[s i f d]v( GLtype *v1, GLtype *v2 ) можно нарисовать прямоугольник в плоскости z=0 с координатами противоположных углов (x1,y1) и (x2,y2), либо набор прямоугольников с координатами углов в массивах v1 и v2.

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

Однако сначала надо определить понятие лицевых и обратных граней.

Под гранью понимается одна из сторон многоугольника, и по умолчанию лицевой считается та сторона, вершины которой обходятся против часовой стрелки. Направление обхода вершин лицевых сторон можно изменить вызовом команды void glFrontFace(GLenum mode) со значением параметра mode равным GL_CW, а отменить- с GL_CCW.

Чтобы изменить метод отображения многоугольника используется команда void glPolygonMode(GLenum face, Glenum mode)

Параметр mode определяет, как будут отображаться многоугольники, а параметр face устанавливает тип многоугольников, к которым будет применяться эта команда и может принимать следующие значения:

GL_FRONT для лицевых граней

GL_BACK для обратных граней

GL_FRONT_AND_BACK для всех граней

Параметр mode может быть равен:

GL_POINT при таком режиме будут отображаться только вершины многоугольников.

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

GL_FILL при таком режиме многоугольники будут закрашиваться текущим цветом с учетом освещения и этот режим установлен по умолчанию.

Кроме того, можно указывать, какой тип граней отображать на экране. Для этого сначала надо установить соответствующий режим вызовом команды glEnable(GL_CULL_FACE), а затем выбрать тип отображаемых граней с помощью команды void glСullFace(GLenum mode)

Вызов с параметром GL_FRONT приводит к удалению из изображения всех лицевых граней, а с параметром GL_BACK- обратных (установка по умолчанию).

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

Например, чтобы нарисовать сферу или цилиндр, надо сначала создать объект специального типа GLUquadricObj с помощью команды

GLUquadricObj* gluNewQuadric(void)

а затем вызвать соответствующую команду:

void gluSphere(GLUquadricObj * qobj, GLdouble radius, GLint slices, GLint stacks)

void gluCylinder(GLUquadricObj * qobj, GLdouble baseRadius, GLdouble topRadius, GLdouble height, GLint slices, GLint stacks)

где параметр slices задает число разбиений вокруг оси z, а stacks – вдоль оси z.

Более подробную информацию об этих и других командах построения примитивов можно найти приложении.

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

5.2.4 Массивы вершин

Если вершин много, то чтобы не вызывать для каждой команду glVertex..(), удобно объединять вершины в массивы, используя команду

void glVertexPointer( GLint size, GLenum type, GLsizei stride, void *ptr ) которая определяет способ хранения и координаты вершин. При этом size определяет число координат вершины (может быть равен 2, 3, 4), type определяет тип данных (может быть равен GL_SHORT, GL_INT, GL_FLOAT, GL_DOUBLE). Иногда удобно хранить в одном массиве другие атрибуты вершины, и тогда параметр stride задает смещение от координат одной вершины до координат следующей; если stride равен нулю, это значит, что координаты расположены последовательно. В параметре ptr указывается адрес, где находятся данные.

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

void NormalPointer(GLenum type, GLsizei stride, void*pointer)

void ColorPointer(GLintsize, GLenum type, GLsizei stride, void *pointer)

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

void glEnableClientState(GLenum array)

с параметрами GL_VERTEX_ARRAY, GL_NORMAL_ARRAY, GL_COLOR_ARRAY соответственно. После окончания работы с массивом желательно вызвать команду

void glDisableClientState(GLenum array)

с соответствующим значением параметра array.

Для отображения содержимого массивов используется команда

void glArrayElement(GLint index)

которая передает OpenGL атрибуты вершины, используя элементы массива с номером index. Это аналогично последовательному применению команд вида glColor..(…), glNormal..(…), glVertex..(…) c соответствующими параметрами. Однако вместо нее обычно вызывается команда

void glDrawArrays(GLenum mode, GLint first, GLsizei count)

рисующая count примитивов, определяемых параметром mode, используя элементы из массивов с индексами от first до first+count-1. Это эквивалентно вызову команды glArrayElement() с соответствующими индексами.

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

Для этого надо вызвать команду

void glDrawArrays(GLenum mode, GLsizei count, GLenum type, void *indices)

где indices– это массив номеров вершин, которые надо использовать для построения примитивов, type определяет тип элементов этого массива: GL_UNSIGNED_BYTE, GL_UNSIGNED_SHORT, GL_UNSIGNED_INT, а count задает их количество.

5.2.5 Списки изображений

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

void glNewList(GLuint list, GLenum mode)

void glEndList()

Для различения списков используются целые положительные числа, задаваемые при создании списка значением параметра list, а параметр mode определяет режим обработки команд, входящих в список:

GL_COMPILE команды записываются в список без выполнения

GL_COMPILE_AND_EXECUTE команды сначала выполняются, а затем записываются в список

После того, как список создан, его можно вызвать командой

void glCallList(GLuint list)

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

void glCallLists(GLsizei n, GLenum type, const GLvoid *lists)

вызывающей n списков с идентификаторами из массива lists, тип элементов которого указывается в параметре type. Это могут быть типы GL_BYTE, GL_UNSIGNED_BYTE, GL_SHORT, GL_INT, GL_UNSIGNED_INT >и некоторые другие. Для удаления списков используется команда

void glDeleteLists(GLint list, GLsizei range)

которая удаляет списки с идентификаторами ID из диапазона list <=ID<= list+range-1.

5.2.6 Преобразования координат и проекции

В OpenGL используются как основные три системы координат: левосторонняя, правосторонняя и оконная. Первые две системы являются трехмерными и отличаются друг от друга направлением оси z: в правосторонней она направлена на наблюдателя, а в левосторонней – в глубь экрана. Расположение осей x и y аналогично описанному выше. Левосторонняя система используется для задания значений параметрам команды gluPerspective(), glOrtho(), которые будут рассмотрены ниже, а правосторонняя или мировая система координат во всех остальных случаях. Отображение трехмерной информации происходит в двумерную оконную систему координат.

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

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

void glMatrixMode(GLenum mode)

вызов которой со значением параметра mode равным GL_MODELVIEW, GL_PROJECTION, GL_TEXTURE включает режим работы с видовой, проекций и матрицей текстуры соответственно. Для вызова команд, задающих матрицы того или иного типа необходимо сначала установить соответствующий режим.

Для определения элементов матрицы текущего типа вызывается команда

void glLoadMatrix[f d](GLtype *m)

где m указывает на массив из 16 элементов типа float или double в соответствии с названием команды, при этом сначала в нем должен быть записан первый столбец матрицы, затем второй, третий и четвертый.

Команда

void glLoadIdentity(void)

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

void glPushMatrix(void)

void glPopMatrix(void)

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

Для умножения текущей матрицы слева на другую матрицу используется команда

void glMultMatrix[f d](GLtype *m)

где m должен задавать матрицу размером 4x4 в виде массива с описанным расположением данных. Однако обычно для изменения матрицы того или иного типа удобно использовать специальные команды, которые по значениям своих параметров создают нужную матрицу и перемножают ее с текущей. Чтобы сделать текущей созданную матрицу, надо перед вызовом этой команды вызвать glLoadIdentity().

5.2.6.1 Видовое преобразование

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

(x’, y’, z’, 1)T =M * (x, y, z, 1)T

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

void glTranslate[f d](GLtype x, GLtype y, GLtype z)

void glRotate[f d](GLtype angle, GLtype x, GLtype y, GLtype z)

void glScale[f d](GLtype x, GLtype y, GLtype z)

glTranlsate..() производит перенос объекта, прибавляя к координатам его вершин значения своих параметров.

glRotate..() производит поворот объекта против часовой стрелки на угол angle (измеряется в градусах) вокруг вектора ( x,y,z ).

glScale..() производит масштабирование объекта (сжатие или растяжение), домножая соответствующие координаты его вершин на значения своих параметров.

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

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

void gluLookAt(GLdouble eyex, GLdouble eyey, GLdouble eyez, GLdouble centerx, GLdouble centery, GLdouble centerz, GLdouble upx, GLdouble upy, GLdouble upz)

где точка ( eyex,eyey,eyez ) определяет точку наблюдения, ( centerx, centery, centerz )задает центр сцены, который будет проектироваться в центр области вывода, а вектор ( upx,upy,upz ) задает положительное направление оси у, определяя поворот камеры. Если, например, камеру не надо поворачивать, то задается значение (0,1,0), а со значением (0,-1,0) сцена будет перевернута.

Фактически, эта команда совершает перенос и поворот объектов сцены, но в таком виде задавать параметры бывает удобнее.

5.2.6.2 Проекции

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

void glOrtho(GLdouble left, GLdouble right, GLdouble bottom, GLdouble top, GLdouble near, GLdouble far)

void gluOrtho2D(GLdouble left, GLdouble right, GLdouble bottom, GLdouble top)

Первая команда создает матрицу проекции в усеченный объем видимости (параллелограмм видимости) в левосторонней системе координат. Параметры команды задают точки (left, bottom, -near) и (right, top, -near), которые отвечают левому нижнему и правому верхнему углам окна вывода. Параметры near и far задают расстояние до ближней и дальней плоскостей отсечения по дальности от точки (0,0,0) и могут быть отрицательными.

Во второй команде, в отличие от первой, значения near и far устанавливаются равными –1 и 1 соответственно.

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

void gluPerspective(GLdouble angley, GLdouble aspect, GLdouble znear, GLdouble zfar)

которая задает усеченный конус видимости в левосторонней системе координат. Параметр angley определяет угол видимости в градусах по оси у и должен находиться в диапазоне от 0 до 180. Угол видимости вдоль оси x задается параметром aspect, который обычно задается как отношение сторон области вывода. Параметры zfar и znear задают расстояние от наблюдателя до плоскостей отсечения по глубине и должны быть положительными. Чем больше отношение zfar/znear, тем хуже в буфере глубины будут различаться расположенные рядом поверхности, так как по умолчанию в него будет записываться ‘сжатая’ глубина в диапазоне от 0 до 1 (см. следующий пункт).

5.2.6.3 Область вывода

После применения матрицы проекций на вход следующего преобразования подаются так называемые усеченные (clip) координаты, для которых значения всех компонент (xc, yc, zc, wc)T находятся в отрезке [-1,1]. После этого находятся нормализованные координаты вершин по формуле:

(xn, yn, zn)T=(xc/wc, yc/wc, zc/wc)T

Область вывода представляет из себя прямоугольник в оконной системе координат, размеры которого задаются командой:

void glViewPort(GLint x, GLint y, GLint width, GLint height)

Значения всех параметров задаются в пикселах и определяют ширину и высоту области вывода с координатами левого нижнего угла ( x,y ) в оконной системе координат. Размеры оконной системы координат определяются текущими размерами окна приложения, точка (0,0)находится в левом нижнем углу окна.

Используя параметры команды glViewPort(), вычисляются оконные координаты центра области вывода (ox, oy) по формулам ox=x+width/2, oy=y+height/2.

Пусть px=width, py=height, тогда можно найти оконные координаты каждой вершины:

(xw, yw, zw)T = ( (px/2) xn+ ox , (py/2) yn+ oy , [(f-n)/2] zn+(n+f)/2 )T

При этом целые положительные величины n и f задают минимальную и максимальную глубину точки в окне и по умолчанию равны 0 и 1 соответственно. Глубина каждой точки записывается в специальный буфер глубины (z-буфер), который используется для удаления невидимых линий и поверхностей. Установить значения n и f можно вызовом функции

void glDepthRange(GLclampd n, GLclampd f)

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

5.2.7 Материалы и освещение

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

5.2.7.1 Свойства материала

Для задания параметров текущего материала используются команды

void glMaterial[i f](GLenum face, GLenum pname, GLtype param)

void glMaterial[i f]v(GLenum face, GLenum pname, GLtype *params)

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

GL_AMBIENT параметр params должен содержать четыре целых или вещественных значения цветов RGBA, которые определяют рассеянный цвет материала (цвет материала в тени).

Значение по умолчанию: (0.2, 0.2, 0.2, 1.0).

GL_DIFFUSE параметр params должен содержать четыре целых или вещественных значения цветов RGBA, которые определяют цвет диффузного отражения материала.

Значение по умолчанию:(0.8, 0.8, 0.8, 1.0).

GL_SPECULAR параметр params должен содержать четыре целых или вещественных значения цветов RGBA, которые определяют цвет зеркального отражения материала.

Значение по умолчанию: (0.0, 0.0, 0.0, 1.0).

GL_SHININESS параметр params должен содержать одно целое или вещественное значение в диапазоне от 0 до 128, которое определяет степень зеркального отражения материала.

Значение по умолчанию: 0.

GL_EMISSION параметр params должен содержать четыре целых или вещественных значения цветов RGBA, которые определяют интенсивность излучаемого света материала.

Значение по умолчанию: (0.0, 0.0, 0.0, 1.0).

GL_AMBIENT_AND_DIFFUSE эквивалентно двум вызовам команды glMaterial..() со значением pname GL_AMBIENT и GL_DIFFUSE и одинаковыми значениями params.

Из этого следует, что вызов команды glMaterial[i f]() возможен только для установки степени зеркального отражения материала. В большинстве моделей учитывается диффузный и зеркальный отраженный свет; первый определяет естественный цвет объекта, а второй – размер и форму бликов на его поверхности.

Параметр face определяет тип граней, для которых задается этот материал и может принимать значения GL_FRONT, GL_BACK или GL_FRONT_AND_BACK.

Если в сцене материалы объектов различаются лишь одним параметром, рекомендуется сначала установить нужный режим, вызвав glEnable() c параметром GL_COLOR_MATERIAL, а затем использовать команду

void glColorMaterial(GLenum face, GLenum pname)

где параметр face имеет аналогичный смысл, а параметр pname может принимать все перечисленные значения. После этого, значения выбранного с помощью pname свойства материала для конкретного объекта (или вершины) устанавливается вызовом команды glColor..(), что позволяет избежать вызовов более ресурсоемкой команды glMaterial..() и повышает эффективность программы.

5.2.7.2 Источники света

Добавить в сцену источник света можно с помощью команд

void glLight[i f](GLenum light, GLenum pname, GLfloat param)

void glLight[i f](GLenum light, GLenum pname, GLfloat *params)

Параметр light однозначно определяет источник,и выбирается из набора специальных символических имен вида GL_LIGHTi, где i должно лежать в диапазоне от 0 до GL_MAX_LIGHT, которое не превосходит восьми.

Оставшиеся два параметра имеют аналогичный смысл, что и в команде glMaterial..(). Рассмотрим их назначение (вначале описываются параметры для первой команды, затем для второй):

GL_SPOT_EXPONENT параметр param должен содержать целое или вещественное число от 0 до 128, задающее распределение интенсивности света. Этот параметр описывает уровень сфокусированности источника света.

Значение по умолчанию: 0 (рассеянный свет).

GL_SPOT_CUTOFF параметр param должен содержать целое или вещественное число между 0 и 90 или равное 180, которое определяет максимальный угол разброса света. Значение этого параметра есть половина угла в вершине конусовидного светового потока, создаваемого источником.

Значение по умолчанию: 180 (рассеянный свет).

GL_AMBIENT параметр params должен содержать четыре целых или вещественных значения цветов RGBA, которые определяют цвет фонового освещения.

Значение по умолчанию: (0.0, 0.0, 0.0, 1.0).

GL_DIFFUSE параметр params должен содержать четыре целых или вещественных значения цветов RGBA, которые определяют цвет диффузного освещения.

Значение по умолчанию: (1.0, 1.0, 1.0, 1.0)для LIGHT0 и (0.0, 0.0, 0.0, 1.0) для остальных.

GL_SPECULAR параметр params должен содержать четыре целых или вещественных значения цветов RGBA, которые определяют цвет зеркального отражения.

Значение по умолчанию: (1.0, 1.0, 1.0, 1.0)для LIGHT0 и (0.0, 0.0, 0.0, 1.0) для остальных.

GL_POSITION параметр params должен содержать четыре целых или вещественных, которые определяют положение источника света. Если значение компоненты w равно 0.0, то источник считается бесконечно удаленным и при расчете освещенности учитывается только направление на точку (x,y,z), в противном случае считается, что источник расположен в точке (x,y,z,w).

Значение по умолчанию: (0.0, 0.0, 1.0, 0.0).

GL_SPOT_DIRECTION параметр params должен содержать четыре целых или вещественных числа, которые определяют направление света.

Значение по умолчанию: (0.0, 0.0, -1.0, 1.0).

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

Для использования освещения сначала надо установить соответствующий режим вызовом команды glEnable (GL_LIGHTNING), а затем включить нужный источник командой glEnable(GL_LIGHTn).

5.2.7.3 Модель освещения

В OpenGL используется модель освещения Фонга, в соответствии с которой цвет точки определяется несколькими факторами: свойствами материала и текстуры, величиной нормали в этой точке, а также положением источника света и наблюдателя. Для корректного расчета освещенности в точке надо использовать единичные нормали, однако команды типа glScale..(), могут изменять длину нормалей. Чтобы это учитывать, используется уже упоминавшийся режим нормализации нормалей, который включается вызовом команды glEnable(GL_NORMALIZE).

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

void glLightModel[i f](GLenum pname, GLenum param)

void glLightModel[i f]v(GLenum pname, const GLtype *params)

Аргумент pname определяет, какой параметр модели освещения будет настраиваться и может принимать следующие значения:

GL_LIGHT_MODEL_LOCAL_VIEWER параметр param должен быть булевским и задает положение наблюдателя. Если он равен FALSE, то направление обзора считается параллельным оси –z, вне зависимости от положения в видовыx координатах. Если же он равен TRUE, то наблюдатель находится в начале видовой системы координат. Это может улучшить качество освещения, но усложняет его расчет.

Значение по умолчанию: FALSE.

GL_LIGHT_MODEL_TWO_SIDE параметр param должен быть булевским и управляет режимом расчета освещенности как для лицевых, так и для обратных граней. Если он равен FALSE, то освещенность рассчитывается только для лицевых граней. Если же он равен TRUE, расчет проводится и для обратных граней. Значение по умолчанию: FALSE .

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

Значение по умолчанию:(0.2, 0.2, 0.2,1.0).

5.2.8 Текстуры

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

выбрать изображение и преобразовать его к нужному формату

загрузить изображение в память

определить, как текстура будет наноситься на объект и как она будет с ним взаимодействовать.

Рассмотрим каждый из этих этапов.

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

Принятый в OpenGL формат хранения изображений отличается от стандартного формата Windows DIB только тем, что компоненты (R,G,B) для каждой точки хранятся в прямом порядке, а не в обратном и выравнивание задается программистом. Считывание графических данных из файла и их преобразование можно проводить и вручную, однако удобней воспользоваться функцией, входящей в состав библиотеки GLAUX (для ее использования надо дополнительно подключить glaux.lib), которая сама проводит необходимые операции. Это функция

AUX_RGBImageRec* auxDIBImageLoad(string file)

где file– название файла с расширением *.bmp или *.dib. В качестве результата функция возвращает указатель на область памяти, где хранятся преобразованные данные.

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

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

void gluScaleImage(GLenum format, GLint widthin, GL heightin, GLenum typein, const void *datain, GLint widthout, GLint heightout, GLenum typeout, void *dataout)

В качестве значения параметра format обычно используется значение GL_RGB или GL_RGBA, определяющее формат хранения информации. Параметры widthin, heightin, widhtout, heightout определяют размеры входного и выходного изображений, а с помощью typein и typeout задается тип элементов массивов, расположенных по адресам datain и dataout. Как и обычно, то может быть тип

GL_UNSIGNED_BYTE, GL_SHORT, GL_INT и так далее. Результат своей работы функция заносит в область памяти, на которую указывает параметр dataout.

Во-вторых, надо предусмотреть случай, когда объект по размерам значительно меньше наносимой на него текстуры. Чем меньше объект, тем меньше должна быть наносимая на него текстура и поэтому вводится понятие уровней детализации текстуры. Каждый уровень детализации задает некоторое изображение, которое является как правило уменьшенной в два раза копией оригинала. Такой подход позволяет улучшить качество нанесения текстуры на объект. Например, для изображения размером 2mx2n можно построить max(m,n)+1 уменьшенных изображений, соответствующих различным уровням детализации.

Эти два этапа создания образа текстуры в памяти можно провести с помощью команды

void gluBuild2DMipmaps(GLenum target, GLint components, GLint width, GLint height, GLenum format, GLenum type, const void *data)

где параметр target должен быть равен GL_TEXTURE_2D, components определяет количество цветовых компонент текстуры, которые будут использоваться при ее наложении и может принимать значения от 1 до 4 (1-только красный,2-красный и alpha, 3-красный, синий, зеленый, 4-все компоненты).

Параметры width, height, data определяют размеры и расположение текстуры соответственно, а format и type имеют аналогичный смысл, что и в команде gluScaleImage().

В OpenGL допускается использование одномерных текстур, то есть размера 1xN, однако это всегда надо указывать, используя в качестве значения target константу GL_TEXTURE_1D. Существует одномерный аналог рассматриваемой команды- gluBuild1DMipmaps(), который отличается от двумерного отсутствием параметра height.

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

void glGenTextures(GLsizei n, GLuint*textures)

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

void glBindTexture(GLenum target, GLuint texture)

где target может принимать значения GL_TEXTURE_1D или GL_TEXTURE_2D, а параметр texture должен быть равен идентификатору той текстуры, к которой будут относиться последующие команды. Для того, чтобы в процессе рисования сделать текущей текстуру с некоторым идентификатором, достаточно опять вызвать команду glBindTexture() c соответствующим значением target и texture. Таким образом, команда glBindTexture() включает режим создания текстуры с идентификатором texture, если такая текстура еще не создана, либо режим ее использования, то есть делает эту текстуру текущей.

5.2.8.2 Методы наложения текстуры

При наложении текстуры, как уже упоминалось, надо учитывать случай, когда размеры текстуры отличаются от размеров объекта, на который она накладывается. При этом возможно как растяжение, так и сжатие изображения, и то, как будут проводиться эти преобразования может серьезно повлиять на качество построенного изображения. Для определения положения точки на текстуре используется параметрическая система координат (s,t), причем значения s и t находятся в отрезке [0,1]. Для изменения различных параметров текстуры применяются команды:

void glTexParameter[i f](GLenum target, GLenum pname, GLenum param)

void glTexParameter[i f]v(GLenum target, GLenum pname, GLenum *params)

При этом target имеет аналогичный смысл, что и раньше, pname определяет, какое свойство будем менять,а с помощью param или params устанавливается новое значение. Возможные значения pname:

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

Значение по умолчанию: GL_LINEAR.

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

Значение по умолчанию: GL_LINEAR.

GL_TEXTURE_WRAP_S параметр param устанавливает значение координаты s, если оно не входит в отрезок [0,1]. При значении GL_REPEAT целая часть s отбрасывается, и в результате изображение размножается по поверхности. При значении GL_CLAMP используются краевые значения: 0 или 1, что удобно использовать, если на объект накладывается один образ.

Значение по умолчанию: GL_REPEAT.

GL_TEXTURE_WRAP_T аналогично предыдущему значению, только для координаты t.

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

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

void glTexEnv[i f](GLenum target, GLenum pname, GLtype param)

void glTexEnv[i f]v(GLenum target, GLenum pname, GLtype *params)

Параметр target должен быть равен GL_TEXTURE_ENV, а в качестве pname рассмотрим только одно значение GL_TEXTURE_ENV_MODE, которое наиболее часто применяется. Параметр если param может быть равен:

GL_MODULATE конечный цвет находится как произведение цвета точки на поверхности и цвета соответствующей ей точки на текстуре.

GL_REPLACE в качестве конечного цвета используется цвет точки на текстуре.

GL_BLEND конечный цвет находится как сумма цвета точки на поверхности и цвета соответствующей ей точки на текстуре с учетом их яркости.

5.2.8.3 Координаты текстуры

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

Первый метод реализуется с помощью команд

void glTexCoord[1 2 3 4][s i f d](type coord)

void glTexCoord[1 2 3 4][s i f d]v(type *coord)

Чаще всего используется команды вида glTexCoord2..(type s, type t), задающие текущие координаты текстуры. Вообще, понятие текущих координат текстуры аналогично понятиям текущего цвета и текущей нормали, и является атрибутом вершины. Однако даже для куба нахождение соответствующих координат текстуры является довольно трудоемким занятием, поэтому в библиотеке GLU помимо команд, проводящих построение таких примитивов, как сфера, цилиндр и диск, предусмотрено также наложение на них текстур. Для этого достаточно вызвать команду

void gluQuadricTexture(GLUquadricObj*quadObject, GLboolean textureCoords)

с параметром textureCoords равным GL_TRUE, и тогда текущая текстура будет автоматически накладываться на примитив.

Второй метод реализуется с помощью команд

void glTexGen[i f d](GLenum coord, GLenum pname, GLtype param)

void glTexGen[i f d]v(GLenum coord, GLenum pname, const GLtype *params)

Параметр coord определяет для какой координаты задается формула и может принимать значение GL_S, GL_T; pname определяет тип формулы и может быть равен GL_TEXTURE_GEN_MODE, GL_OBJECT_PLANE, GL_EYE_PLANE. С помощью params задаются необходимые параметры, а param может быть равен GL_OBJECT_LINEAR, GL_EYE_LINEAR, GL_SPHERE_MAP. Рассмотрение всех возможных комбинаций значений аргументов этой команды заняло бы слишком много места, поэтому в качестве примера рассмотрим, как можно задать зеркальную текстуру. При таком наложении текстуры изображение будет как бы отражаться от поверхности объекта, вызывая интересный оптический эффект. Для этого сначала надо создать два целочисленных массива коэффициентов s_coeffs и t_coeffs со значениями (1,0,0,1) и (0,1,0,1) соответственно, а затем вызвать команды:

glEnable(GL_TEXTURE_GEN_S);
glTexGeni(GL_S, GL_TEXTURE_GEN_MODE, GL_EYE_LINEAR);

glTexGendv(GL_S, GL_EYE_PLANE, s_coeffs);

и такие же команды для координаты t с соответствующими изменениями.

БИБЛИОГРАФИЧЕСКИЙ СПИСОК

1. Алберг Дж., Нильсон Э., Уолш Дж. Теория сплайнов и ее применения. –М.: Мир, 1972.

2. Вершинин В.В., Завьялов Ю.С., Павлов Н.Н. Экстремальные свойства сплайнов и задач сглаживания. -Новосибирск: Наука, 1988.

3. Гильберт Д., Кон-Фоссен С. Наглядная геометрия. Пер. с нем. - М.: Наука, 1981. -344 с.

4. Гребенников А.И., Метод сплайнов и решение некорректных задач теории приближений. -М: Мир, 1983.

5. Жермен-Лакур П., Жорж П.Л., Пистер Ф., Безье П. Математика и САПР. В 2-х кн. Кн.2 Пер. с франц. -М: Мир, 1988. - 264 с.

6. Завьялов Ю.С., Квасов Б.И., Мирошниченко В.Л., Методы сплайн-функций. -М: Наука, 1980.

7. Завьялов Ю.С., Леус В.А., Скороспелов В.А., Сплайны в инженерной геометрии. -М: Машиностроение, 1985.

8. Иванов В.П., Батраков А.С. Трехмерная компьютерная графика. - М.: Радио и связь, 1995 - 224 с.

9. Игнатов М.И., Певный А.Б. Натуральные сплайны многих переменных. -Ленинград: Наука, 1991.

10.Носач В.В. Решение задач аппроксимации с помощью персональных компьютеров. - М. МИКАП, 1994. - 382 с.

11.Роджерс Д., Адамс Дж. Математические основы машинной графики. Пер. с англ.-М.:Мир,2001.-604с.

12.Сидоренко С.М., Соловьев Л.П., Пронюшкина Т.Г., Сидоренко Е.Г. Вычислительная геометрия. -М.: Луч, 1995. -205 с.

13.Фокс А., Пратт М. Вычислительная геометрия. Применение в проектировании и на производстве. -М: Мир, 1982. - 304 с.

14.Фоли Дж., вэн Дэм А. Основы интерактивной машинной графики: В 2-х нигах. -М: Мир, 1985. - 368 с.

Улан-Удэ, 2009

Рис.1.3 График кусочно-кубического многочлена Эрмита

Рис.1.4 Кубическая сплайн-функция

1.6.3 Кубические кривые Безье

1.8.1. Выбор шага интерполяции

Рис. 1.8 Разбиение графической информации

Рис. 1.9 Аппроксимация заданных точек

Рис 3.1 Удаление невидимых линий методом плавающего горизонта

Z(x,y)=0.2*sin(x)*cos(y)-1.5*cos(7a/4)*e-a

3.42 Метод z- буфера

Рис 4.2

Рис 4.5

5. OpenGL

5.1.2 Архитектура

5.1.3 Расширения

5.1.4 Дополнительные библиотеки

5.1.5 Независимость от языка программирования

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

Z(x,y)=0.2sin(x)cos(y)-1.5cos(7a/4)e^-a