Базовые алгоритмы в компьютерной графике.
Алгоритм вывода прямой линии.
Поскольку экран LCD-дисплея можно рассматривать как матрицу дискретных элементов (пикселей), каждый из которых может быть подсвечен, нельзя непосредственно провести отрезок из одной точки в другую. Процесс определения пикселей, наилучшим образом аппроксимирующих заданный отрезок, называется разложением в растр. В сочетании с процессом построчной визуализации изображения он известен как преобразование растровой развертки. Для горизонтальных, вертикальных и наклоненных под углом 45°. отрезков выбор растровых элементов очевиден. При любой другой ориентации выбрать нужные пиксели труднее, что и показано на рис.1.
Рис.1. Разложение в растр отрезков прямых.
Общие требования к алгоритмам вычерчивания отрезков следующие: Отрезки должны выглядеть прямыми, начинаться и заканчиваться в заданных точках, яркость вдоль отрезка должна быть постоянной и не зависеть от длины и наклона, рисовать нужно быстро.
Постоянная вдоль всего отрезка яркость достигается лишь при проведении горизонтальных, вертикальных и наклоненных под углом 45° прямых. Для всех других ориентаций разложение в растр приведет к неравномерности яркости, как это показано на рис. 1.
В большинстве алгоритмов вычерчивания отрезков для упрощения вычислений используется пошаговый алгоритм. Приведем пример подобного алгоритма:
Простой пошаговый алгоритм
позиция = начало
шаг = приращение
1. if позиция - конец < точность then 4
if позици > конец then 2
if позиция < конец then 3
2. позиция = позиция - шаг
go to 1
3. позиция = позиция + шаг
go to 1
4. finish
Алгоритм Брезенхема.
Хотя алгоритм Брезенхема был первоначально разработан для цифровых графопостроителей, однако он в равной степени подходит для LCD-монитора. Алгоритм выбирает оптимальные растровые координаты для представления отрезка. В процессе работы одна из координат - либо x, либо y (в зависимости от углового коэффициента) - изменяется на единицу. Изменение другой координаты (на 0 или 1) зависит от расстояния между действительным положением отрезка и ближайшими координатами сетки. Такое расстояние мы назовем ошибкой.
Алгоритм построен так, что требуется проверить лишь знак этой ошибки. На рис.2 это иллюстрируется для отрезка в первом октанте, т.е. для отрезка с угловым коэффициентом, лежащим в диапазоне от 0 до 1. Из рисунка можно заметить, что если угловой коэффициент отрезка из точки (0,0) больше, чем 1/2, то пересечение с прямой x = 1 будет расположено ближе к прямой y = 1, чем к прямой y = 0. Следовательно, точка растра (1,1) лучше аппроксимирует ход отрезка, чем точка (1,0). Если угловой коэффициент меньше 1/2, то верно обратное. для углового коэффициента, равного 1/2, нет какого либо предпочтительного выбора. В данном случае алгоритм выбирает точку (1,1).
Рис. 2. Основная идея алгоритма Брезенхема.
Не все отрезки проходят через точки растра. Подобная ситуация иллюстрируется рис.3, где отрезок с тангенсом угла наклона 3/8 сначала походит через точку растра (0,0) и последовательно пересекает три пикселя. Также иллюстрируется вычисление ошибки при представлении отрезка дискретными пикселями.
Рис.3. График ошибки в алгоритме Брезенхема.
Так как желательно проверять только знак ошибки, то она первоначально устанавливается равной -1/2. Таким образом, если угловой коэффициент отрезка больше или равен 1/2, то величина ошибки в следующей точке растра с координатами (1,0) может быть вычислена как
e = e + m
где m - угловой коэффициент. В нашем случае при начальном значении ошибки -1/2
e = 1/2 + 3/8 = -1/8
Так как е отрицательно, отрезок пройдет ниже середины пикселя. Следовательно, пиксел на том же самом горизонтальном уровне лучше аппроксимирует положение отрезка, поэтому у не увеличивается. Аналогично вычисляем ошибку
e = -1/8 + 3/8 = 1/4
в следующей точке растра (2,0). Теперь е положительно, значит отрезок пройдет выше средней точки. Растровый элемент (2,1) со следующей по величине координатой у лучше аппроксимирует положение отрезка. Следовательно у увеличивается на 1. Прежде чем рассматривать следующий пиксель, необходимо откорректировать ошибку вычитанием из нее 1. Имеем
e = 1/4 - 1 = -3/4
Заметим, что пересечение вертикальной прямой x = 2 с заданным отрезком лежит на 1/4 ниже прямой у = 1. Если же перенести отрезок 1/2 вниз, мы получим как раз величину -3/4. Продолжение вычислений для следующего пикселя дает
e = -3/4 + 3/8 = -3/8
Так как е отрицательно, то у не увеличивается. Из всего сказанного следует, что ошибка - это интервал, отсекаемый по оси у рассматриваемым отрезком в каждом растровом элементе (относительно -1/2).
Приведем алгоритм Брезенхема для первого октанта, т.е. для случая 0 =< 
y =< x.
Алгоритм Брезенхема разложения в растр отрезка для первого октанта
предполагается, что концы отрезка (x1,y1) и (x2,y2) не совпадают
Integer - функция преобразования в целое
x, y, x, y - целые
е - вещественное
инициализация переменных
x = x1
y = y1
x = x2 - x1
y = y2 - y1
Инициализация с поправкой на половину пикселя
е = y/x - 1/2
начало основного цикла
for i = 1 to x
plot (x,y)
while ( e => 0 )
y = y + 1
e = e - 1
end while
x = x + 1
e = e + y/x
next i
finish
Блок-схема алгоритма приводится на рис.4.
Рис.4. Блок-схема алгоритма Брезенхема.
Пример алгоритма Брезенхема.
Рассмотрим отрезок проведенный из точки (0,0) в точку (5,5). Разложение отрезка в растр по алгоритму Брезенхема приводит к такому результату:
начальные установки
x = 0
y = 0
x = 5
y = 5
е = 1 - 1/2 = 1/2
результаты работы пошагового цикла
Результат показан на рис.5 и совпадает с ожидаемым. Заметим, что точка растра с координатами (5,5) не активирована. Эту точку можно активировать путем изменения цикла for-next на 0 to x. Активацию точки (0,0) можно устранить, если поставить оператор Plot непосредственно перед строкой next i.
Рис. 5. Результат работы алгоритма Брезенхема в первом октанте.
Общий алгоритм Брезенхема.
Чтобы реализация алгоритма Брезенхема была полной необходимо обрабатывать отрезки во всех октантах. Модификацию легко сделатть, учитывая в алгоритме номер квадранта, в котором лежит отрезок и его угловой коэффициепт. Когда абсолютная величина углового коэффициента больше 1, у постоянно изменяется на единицу, а критерий ошибки Брезенхема используется для принятия решения об изменении величины x. Выбор постоянно изменяющейся (на +1 или -1) кооординаты зависит от квадранта (рис.6.). Общий алгоритм может быть оформлен в следующем виде:
Обобщенный целочисленный алгоритм Брезенхема квадрантов
предполагается, что концы отрезка (x1,y1) и (x2,y2) не совпадают
все переменные считаются целыми
Sign - функция, возвращающая -1, 0, 1 для отрицательного, нулевого и положительного аргумента соответственно
инициализация переменных
x = x1
y = y1
x = abs(x2 - x1)
y = abs(y2 - y1)
s1 = Sign(x2 - x1)
s2 = Sign(y2 - y1)
обмен значений x и y в зависимости от углового коэффициента наклона отрезка
if y < x then
Врем = x
x = y
y = Врем
Обмен = 1
else
Обмен = 0
end if
инициализация е с поправкой на половину пикселя
е = 2*y - x
основной цикл
for i = 1 to x
Plot(x,y)
while(е =>0)
if Обмен = 1 then
x = x + s1
else
y = y + s2
end if
е = е - 2*x
end while
if Обмен = 1 then
y = y + s2
else
x = x + s1
end if
е = е + 2*y
next i
finish
Рис.6. Разбор случаев для обобщенного алгоритма Брезенхема.
Пример. Обобщенный алгоритм Брезенхема.
Для иллюсрации рассмотрим отрезок из точки (0,0) в точку (-8, -4).
начальные установки
x = 0
y = 0
x = 8
y = 4
s1 = -1
s2 = -1
Обмен = 0
е = 0
результаты работы пошагового цикла
Рис.7. Результат работы обобщенного алгоритма Брезенхема в третьем квадранте.
На рис. 7 продемонстрирован результат. Сравнение с рис. 5 показывает, что результаты работы двух алгоритмов отличаются.
В следующем разделе рассматривается алгоритм Брезенхема для генерации окружности.
Алгоритм Брезенхема для генерации окружности.
В растр нужно разлагать не только линейные, но и другие, более сложные функции. Разложению конических сечений, т. е. окружностей, эллипсов, парабол, гипербол, было посвящено значительное число работ . Наибольшее внимание, разумеется, уделено окружности. Один из наиболее эффективных и простых для понимания алгоритмов генерации окружности принадлежит Брезенхему . Для начала заметим, что необходимо сгенерировать только одну восьмую часть окружности. Остальные ее части могут быть получены последовательными отражениями, как это показано на рис. 8. Если сгенерирован первый октант (от 0 до 45° против часовой стрелки), то второй октант можно получить зеркальным отражением относительно прямой у = х, что дает в совокупности первый квадрант. Первый квадрант отражается относительно прямой х = 0 для получения соответствующей части окружности во втором квадранте. Верхняя полуокружность отражается относительно прямой у = 0 для завершения построения. На рис. 8 приведены двумерные матрицы соответствующих преобразований.
Рис. 8. Генерация полной окружности из дуги в первом октанте.
Для вывода алгоритма рассмотрим первую четверть окружности с центром в начале координат. Заметим, что если работа алгоритма начинается в точке х = 0, у = R, то при генерации окружности по часовой стрелке в первом квадранте у является монотонно убывающей функцией аргументам (рис. 9). Аналогично, если исходной точкой является у = 0, х = R, то при генерации окружности против часовой стрелки х будет монотонно убывающей функцией аргумента у. В нашем случае выбирается генерация по часовой стрелке с началом в точке х = 0, у = R. Предполагается, что центр окружности и начальная точка находятся точно в точках растра.
Для любой заданной точки на окружности при генерации по часовой стрелке существует только три возможности выбрать следующий пиксел, наилучшим образом приближающий окружность: горизонтально вправо, по диагонали вниз и вправо, вертикально вниз. На рис. 10 эти направления обозначены соответственно mH, mD, mV. Алгоритм выбирает пиксел, для которого минимален квадрат расстояния между одним из этих пикселей и окружностью, т. е. минимум из
mH = |(xi + 1)2 + (yi)2 -R2|
mD = |(xi + 1)2 + (yi -1)2 -R2|
mV = |(xi )2 + (yi -1)2 -R2|
Вычисления можно упростить, если заметить, что в окрестности точки (xi,yi,) возможны только пять типов пересечений окружности и сетки растра, приведенных на рис. 11.
Рис. 11. Пересечение окружности и сетки растра.
Разность между квадратами расстояний от центра окружности до диагонального пикселя (xi, + 1, уi - 1) и от центра до точки на окружности R2 равна
di = (xi + 1)2 + (yi -1)2 -R2
Как и в алгоритме Брезенхема для отрезка, для выбора соответствующего пикселя желательно использовать только знак ошибки, а не ее величину.
При di < 0 диагональная точка (xi, + 1, уi - 1) находится внутри реальной окружности, т. е. это случаи 1 или 2 на рис. 11. Ясно, что в этой ситуации следует выбрать либо пиксел (xi, + 1, уi), т. е. mH, либо пиксел (xi, + 1, уi - 1), т. е. mD. Для этого сначала рассмотрим случай 1 и проверим разность квадратов расстояний от окружности до пикселей в горизонтальном и диагональном направлениях:
d = |(xi + 1)2 + (yi )2 -R2| - |(xi + 1)2 + (yi -1)2 -R2|
При d < 0 расстояние от окружности до диагонального пикселя больше, чем до горизонтального. Напротив, если d > 0, расстояние до горизонтального пикселя больше. Таким образом,
при d <= 0 выбираем mH в (xi, + 1, уi - 1)
при d > 0 выбираем mD в (xi, + 1, уi - 1)
При e = 0, когда расстояние от окружности до обоих пикселей одинаковы, выбираем горизонтальный шаг.
Количество вычислений, необходимых для оценки величины e, можно сократить, если заметить, что в случае 1
(xi + 1)2 + (yi )2 -R2 >= 0
(xi + 1)2 + (yi -1)2 -R2 < 0
так как диагональный пиксел (xi, + 1, уi - 1) всегда лежит внутри окружности, а горизонтальный (xi, + 1, уi ) - вне ее. Таким образом, e можно вычислить по формуле
d = (xi + 1)2 + (yi )2 -R2 + (xi + 1)2 + (yi -1)2 -R2
Дополнение до полного квадрата члена (yi )2 с помощью добавления и вычитания - 2yi + 1 дает
d = 2[(xi + 1)2 + (yi -1)2 -R2] + 2yi - 1
В квадратных скобках стоит по определению ei и его подстановка
d = 2( ei + yi ) - 1
существенно упрощает выражение.
Рассмотрим случай 2 на рис. 11 и заметим, что здесь должен быть выбран горизонтальный пиксел (xi, + 1, уi), так как у является монотонно убывающей функцией. Проверка компонент e показывает, что
(xi + 1)2 + (yi )2 -R2 < 0
(xi + 1)2 + (yi -1)2 -R2 < 0
поскольку в случае 2 горизонтальный (xi, + 1, уi) и диагональный (xi, + 1, уi -1) пиксели лежат внутри окружности. Следовательно, d < 0, и при использовании того же самого критерия, что и в случае 1, выбирается пиксел (xi, + 1, уi).
Если ei > 0, то диагональная точка (xi, + 1, уi -1) находится вне окружности, т. е. это случаи 3 и 4 на рис. 11. В данной ситуации ясно, что должен быть выбран либо пиксел (xi, + 1, уi -1), либо (xi, , уi -1). Аналогично разбору предыдущего случая критерий выбора можно получить, рассматривая сначала случай 3 и проверяя разность между квадратами расстояний от окружности до диагонального mD и вертикального mV пикселей,
т. е. d' = |(xi + 1)2 + (yi -1)2 -R2| - |(xi)2 + (yi -1)2 -R2 |
При d' < 0 расстояние от окружности до вертикального пикселя (xi, , уi -1) больше и следует выбрать диагональный шаг к пикселу (xi, + 1, уi -1). Напротив, в случае d' > 0 расстояние от окружности до диагонального пикселя больше и следует выбрать вертикальное движение к пикселу (xi, , уi -1). Таким образом,
при d' <= 0 выбираем mD в (xi +1, , уi -1)
при d' > 0 выбираем mV в (xi, , уi -1)
Здесь в случае d' = 0, т. е. когда расстояния равны, выбран диагональный шаг.
Проверка компонент e' показывает, что
(xi )2 + (yi -1)2 -R2 >= 0
(xi + 1)2 + (yi -1)2 -R2 < 0
поскольку для случая 3 диагональный пиксел (xi +1, уi -1) находится вне окружности, тогда как вертикальный пиксел (xi, , уi -1) лежит внутри ее. Это позволяет записать e' в виде
d' = (xi +1)2 + (yi -1)2 -R2 + (xi )2 + (yi -1)2 -R2
Дополнение до полного квадрата члена (xi)2 с помощью добавления и вычитания 2xi + 1 дает
d' = 2[(xi +1)2 + (yi -1)2 -R2] - 2xi - 1
Использование определения di приводит выражение к виду
d' = 2( ei - xi )- 1
Теперь, рассматривая случай 4, снова заметим, что следует выбрать вертикальный пиксел (xi, уi -1), так как у является монотонно убывающей функцией при возрастании х.
Проверка компонент d' для случая 4 показывает, что
(xi +1)2 + (yi -1)2 -R2 > 0
(xi )2 + (yi -1)2 -R2 > 0
поскольку оба пикселя находятся вне окружности. Следовательно, e' > 0 и при использовании критерия, разработанного для случая 3, происходит верный выбор mV.
Осталось проверить только случай 5 на рис. 11, который встречается, когда диагональный пиксел (xi, , уi -1) лежит на окружности, т. е. di = 0. Проверка компонент e показывает, что
(xi +1)2 + (yi)2 -R2 > 0
(xi +1)2 + (yi -1)2 -R2 = 0
Следовательно, d > 0 и выбирается диагональный пиксел (xi +1 , уi -1) . Аналогичным образом оцениваем компоненты d' :
(xi +1)2 + (yi -1)2 -R2 = 0
(xi +1)2 + (yi -1)2 -R2 < 0
и d' < 0, что является условием выбора правильного диагонального шага к (xi +1 , уi -1) . Таким образом, случай di = 0 подчиняется тому же критерию, что и случай di < 0 или di > 0. Подведем итог полученных результатов:
di < 0
d <= 0 выбираем пиксел (xi +1 , уi ) - mH
d > 0 выбираем пиксел (xi +1 , уi -1) - mD
di > 0
d' <= 0 выбираем пиксел (xi +1 , уi -1) - mD
d' > 0 выбираем пиксел (xi , уi -1)- mV
di = 0 выбираем пиксел (xi +1 , уi -1) - mD
Легко разработать простые рекуррентные соотношения для реализации пошагового алгоритма. Сначала рассмотрим горизонтальный шаг mH к пикселу (xi + 1, уi). Обозначим это новое положение пикселя как (i + 1). Тогда координаты нового пикселя и значение ei равны
xi+1 = xi +1
yi+1 = yi
di+1 = (xi+1 +1)2 + (yi+1 -1)2 -R2 ddi + 2xi+1+ 1
Аналогично координаты нового пикселя и значение di для шага mD к пикселу (xi + 1, уi -1) таковы:
xi+1 = xi +1
yi+1 = yi -1
di+1 = di + 2xi+1 - 2yi+1 +2
То же самое для шага mV к (xi, уi -1)
xi+1 = xi
yi+1 = yi -1
di+1 = di - 2yi+1 +1
Реализация алгоритма Брезенхема на псевдокоде для окружности приводится ниже.
Пошаговый алгоритм Брезенхема для генерации окружности в первом квадранте
все переменные - целые
инициализация переменных
xi = 0
yi = R
Di = 2(1 - R)
Предел = 0
1 Plot (xi, yi)
if yi <= Предел then 4
Выделение случая 1 или 2, 4 или 5, или 3
if Di < 0 then 2
if D > 0 then 3
if Di= 0 then 20
определение случая 1 или 2
2 d = 2di + 2уi - 1
if d <= 0 then 10
if d > 0 then 20
определение случая 4 или 5
3 d = 2Di + 2хi - 1
if d <= 0 then 20
if d > 0 then 30
выполнение шагов
шаг к mH
10 хi = хi + 1
Di = Di+ 2хi + 1
gо to 1
шаг mD
20 хi = хi + 1
yi = yi + 1
Di = Di+ 2хi - 2уi+ 2
gо to 1
4 finish
Переменная предела устанавливается в нуль для окончания работы алгоритма на горизонтальной оси, в результате генерируется окружность в первом квадранте. Если необходим лишь один из октантов, то второй октант можно получить с помощью установки Предел = Integer (R/sqrt(2)), а первый - с помощью отражения второго октанта относительно прямой у = х (рис. 8). Блок-схема алгоритма приводится на рис. 12.
Рис. 12. Блок-схема пошагового алгоритма Брезенхема для генерации окружности в первом квадранте.
Кривая Безье и ее геометрический алгоритм.
Кривые Безье были разработаны в 60 – х годах XX века независимо друг от друга Пьером Безье (Bezier) из автомобилестроительной компании «Рено» и Полем де Кастелье (de Casteljau) из компании «Ситроен», где применялись для проектирования кузовов автомобилей.
Несмотря на то, что открытие де Кастелье было сделано несколько ранее Безье (1959), его исследования не публиковались и скрывались компанией как производственная тайна до конца 1960 – х.
Впервые кривые были представлены широкой публике в 1962 году французским инженером Пьером Безье, который, разработав их независимо от де Кастелье, использовал их для компьютерного проектирования автомобильных кузовов. Кривые были названы именем Безье, а именем де Кастелье назван разработанный им рекурсивный способ определения кривых (алгоритм де Кастелье).
Впоследствии это открытие стало одним из важнейших инструментов систем автоматизированного проектирования и программ компьютерной графики.
Кривая Безье – параметрическая кривая, задаваемая выражением
, 0 < t <1
где 
– функция компонент векторов опорных вершин, а 
– базисные функции кривой Безье, называемые также полиномами Бернштейна.
где n – степень полинома, i – порядковый номер опорной вершины.
Виды кривых Безье
Линейные кривые
При n = 1 кривая представляет собой отрезок прямой линии, опорные точки P0 и P1 определяют его начало и конец.
Кривая задаётся уравнением:
Квадратичные кривые
(n = 2) задаётся 3 – мя опорными точками: P0, P1 и P2.
,
Квадратичные кривые Безье в составе сплайнов используются для описания формы символов в шрифтах TrueType и в SWF файлах.
Кубические кривые
(n = 3) описывается следующим уравнением:
Четыре опорные точки P0, P1, P2 и P3, заданные в 2 – х или 3 – мерном пространстве определяют форму кривой.
Линия берёт начало из точки P0 направляясь к P1 и заканчивается в точке P3 подходя к ней со стороны P2. То есть кривая не проходит через точки P1 и P2, они используются для указания её направления. Длина отрезка между P0 и P1 определяет, как скоро кривая повернёт к P3.
В матричной форме кубическая кривая Безье записывается следующим образом:
,
где 
называется базисной матрицей Безье:
В современных графических системах, таких как PostScript, Metafont и GIMP для представления криволинейных форм используются сплайны Безье, составленные из кубических кривых.
Применение в компьютерной графике
Благодаря простоте задания и манипуляции, кривые Безье нашли широкое применение в компьютерной графике для моделирования гладких линий. Кривая целиком лежит в выпуклой оболочке своих опорных точек. Это свойство кривых Безье с одной стороны значительно облегчает задачу нахождения точек пересечения кривых (если не пересекаются выпуклые оболочки, то не пересекаются и сами кривые), а с другой стороны позволяет визуализировать кривую с помощью её опорных точек. Кроме того, аффинные преобразования кривой (перенос, масштабирование, вращение) также могут быть осуществлены путём применения соответствующих трансформаций к опорным точкам.
Наибольшее значение имеют кривые Безье второй и третьей степеней (квадратичные и кубические). Кривые высших степеней при обработке требуют большего объёма вычислений и для практических целей используются реже. Для построения сложных по форме линий отдельные кривые Безье могут быть последовательно соединены друг с другом в сплайн Безье. Для того, чтобы обеспечить гладкость линии в месте соединения двух кривых, смежные опорные точки обеих кривых должны лежать на одной линии. В программах векторной графики наподобие Adobe Illustrator или Inkscape подобные фрагменты известны под названием «путей» (path).
Геометрический алгоритм для кривой Безье
Этот алгоритм позволяет вычислить координаты (х, у) точки кривой Безье по значению параметра t.
1. Каждая сторона контура многоугольника, проходящего по точкам – ориентирам, делится пропорционально значению t.
2. Точки деления соединяются отрезками прямых и образуют новый многоугольник. Количество узлов нового контура на единицу меньше, чем количество узлов предыдущего контура.
3. Стороны нового контура снова делятся пропорционально значению t. И так далее. Это продолжается до тех пор, пока не будет получена единственная точка деления. Эта точка и будет точкой кривой Безье.
Приведем запись геометрического алгоритма на языке С + + :
for ( i = 0; i < = m; i + + )
R[i] = P[i]; / / формируем вспомогательный массив R[]
for ( j = m; i > 0; i – – )
for ( i = 0; i < j; i + + )
R[i] = R[i] + t * (R[i + 1] – R[i]);
Результат работы алгоритма – координаты одной точки кривой Безье записываются в R[0].
Модели описания поверхностей. Аналитическая модель.
Аналитической моделью называется описание поверхности математическими формулами:
z = f(x,y) – описание с помощью функции,
F(x,y,z) = 0 – описание с помощью неявного уравнения.
Зачастую используется параметрическая форма описания поверхности:
где s и t – параметры, которые изменяются в определенном диапазоне, а функции Fx, Fy и Fz определяют форму поверхности.
Преимущество параметрической формы заключается в легкости описания поверхностей, которые отвечают неоднозначным функциям, и замкнутых поверхностей.
Параметрическое описание можно задать таким образом, что формула не будет существенно изменяться (усложняться) при поворотах поверхности, и ее масштабировании.
В качестве примера рассмотрим аналитическое описание поверхности шара.
x = R sin s cos t, y = R sin s sin t, z = R cos s – в параметрической форме.
Аналитическая модель наиболее пригодна для многих операций анализа поверхностей.
Достоинства модели (с позиций КГ):
- легкость расчета координат каждой точки поверхности, нормали;
- небольшой объем данных для описания достаточно сложных форм.
Недостатки:
- сложность формул описания с использованием функций, которые медленно вычисляются на компьютере, снижают скорость выполнения операций отображения;
- невозможность в большинстве случаев применить данную форму описания непосредственно для изображения поверхности – поверхность отображается как многогранник, координаты вершин и граней которого рассчитываются в процессе отображения, что уменьшает скорость сравнительно с полигональной моделью описания.
Модель поверхности «равномерная сетка».
Эта модель описывает координаты отдельных точек поверхности следующим способом. Каждому узлу сетки с индексами (i, j) приписывается значение высоты zij. Индексам (i, j) отвечают определенные значения координат (x, y). Расстояние между узлами одинаковое – dx по оси x, dy по оси y. Фактически такая модель – это двумерный массив, растр, матрица, каждый элемент которой сохраняет значение высоты.
Не каждая поверхность может быть представлена этой моделью. Если в каждом узле (i, j) записывается только одно значение высоты, то это означает, что поверхность описывается однозначной функцией z = f (x, y). Иначе говоря, это такая поверхность, которую каждая вертикаль пересекает только один раз. Не могут моделироваться также вертикальные грани. Необходимо заметить, что сетка может быть задана не только в декартовых координатах. Например, для того чтобы описать поверхность шара однозначной функцией, можно использовать полярные координаты. С помощью равномерной сетки часто описывают рельеф земной поверхности.
Положительные черты равномерной сетки:
- простота описания поверхностей;
- возможность быстро узнать высоту любой точки поверхности простой интерполяцией.
Недостатки равномерной сетки:
- поверхности, которые соответствуют неоднозначной функции высоты в узлах сетки, не могут быть смоделированы;
- для описания сложных поверхностей необходимо большое количество узлов, которое может быть ограничено объемом памяти компьютера.
Модель поверхности «неравномерная сетка».
Неравномерной сеткой называется модель описания поверхности в виде множества отдельных точек {(x0, y0, z0), (x1, y1, z1), …,(xn – 1, yn – 1, zn – 1)}, принадлежащих поверхности. Эти точки могут быть получены, например, в результате измерений поверхности какого – нибудь объекта с помощью определенного оборудования. Такую модель можно считать обобщением для некоторых рассмотренных выше моделей. Например, векторная полигональная модель и равномерная сетка могут считаться разновидностями неравномерной сетки.
Рассмотрим модель поверхности в виде множества точечных значений, логически никак не связанных между собой. Неравномерность задания опорных точек усложняет определение координат для других точек поверхности, которые не совпадают с опорными точками. Требуются специальные методы пространственной интерполяции.
Пусть задача заключается в вычислении значения координаты z по известным координатам (x, y). Для этого необходимо найти несколько самых близких точек, а затем вычислить искомое значение z, исходя из взаимного расположения этих точек в проекции (x, y). Для равномерной сетки эта задача решается достаточно просто – поиска фактически нет, сразу рассчитываются индексы самых близких опорных точек.
Вторая задача заключается в отображении (визуализации) поверхности. Эту задачу можно решать несколькими способами. Один из наиболее распространенных – триангуляция.
Процесс триангуляции может быть представлен следующим образом:
- находим первые три самые близкие друг к другу точки – получаем одну плоскую треугольную грань;
- находим точку, ближайшую к этой грани, и образовываем смежную грань, и т.д., пока не останется ни одной отдельной точки.
УЧЕНЬЕ - СВЕТ, А НЕУЧЕНЬЕ - ЧУТЬ СВЕТ И НА РАБОТУ!
