Трехмерная компьютерная графика

Кемеровский Государственный Университет

кафедра математического анализа

Курсовая работа по теме:

Трёхмерная компьютерная графика

Выполнил: студент М-963

Печёркин Ю. К.

Руководитель: Ким В. Б.

Кемерово 1999

Введение

Машинная графика в настоящее время уже вполне сформировалась как наука.

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

изображений - от простых чертежей до реалистичных образов естественных

объектов. Машинная графика используется почти во всех научных и инженерных

дисциплинах для наглядности восприятия и передачи информации. Знание её

основ в наше время необходимо любому ученому или инженеру. Машинная графика

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

Применение во время деловых совещаний демонстрационных слайдов,

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

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

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

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

прибегают к услугам машинной графики и компьютерной мультипликации.

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

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

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

создавать и редактировать трёхмерные сцены и объекты. Среди наиболее

популярных можно назвать такие как 3D studio Max, которая позволяет

трёхмерные компьютерные ролики. Область её применения в основном реклама,

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

популярный пакет программ это Auto-CAD. Он применяется в основном

инженерами и проектировщиками для создания чертежей и пространственных

моделей. Кроме этих существует множество других специализированных

программных пакетов охватывающих практически все стороны человеческой

жизни.

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

вычислительными средствами, те, что основаны на пространственно-образном

мышлении человека, занимают особое место. Современные программно-

оперативные средства компьютерной графики представляют собой весьма

эффективный инструмент поддержки такого мышления при выполнении работ самых

разных видов. С другой стороны именно пространственно-образное мышление

является неформальной творческой основой для расширения изобразительных

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

обогащающее сотрудничество всё более совершенной техники и человека со всем

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

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

привлекательной оказывается компьютерная визуализация, особенно

визуализация динамическая, которую следует рассматривать как важнейший

инструмент для обучения наукам.

1. Введение в машинную графику

Современная машинная графика - это тщательно разработанная дисциплина.

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

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

методы растрового сканирования, отсечение, удаление линий и поверхностей,

цвет, закраска, текстура и эффекты прозрачности. Сейчас наибольший интерес

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

Машинная графика - сложная и разнообразная дисциплина. Для изучения её,

прежде всего, необходимо разбить на обозримые части. Прежде всего

необходимо рассмотреть методы и алгоритмы растровой графики. Это достаточно

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

рассматриваются алгоритмы рисования отрезков и окружностей на экране

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

устранения ступенчатости или лестничного эффекта. Отдельно следует

рассмотреть методы отсечения изображения, т.е. отбора той информации,

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

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

линий и поверхностей. Это одна из наиболее сложных составляющих

визуализации трёхмерных объектов. Способы достижения эффектов прозрачности,

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

частей трёхмерных объектов и, тем не менее, некоторые из них тесно связаны

с этой проблемой. Например, построение теней. Не смотря на это, в

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

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

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

в различных средах, тени, фактура объекта. Так же рассматриваются различные

источники света, их спектральные характеристики и форма. Сюда же относятся

цветовые эффекты, сглаживание поверхностей и многое другое.

Как видно из выше сказанного компьютерная графика это достаточно

объемная дисциплина, поэтому я остановлюсь лишь на некоторых её наиболее

интересных аспектах.

2. Растровая графика

Любое изображение, в том числе и трёхмерное, состоит из графических

примитивов. Поэтому, прежде всего, необходимо знать специальные методы

генерации изображения, вычерчивание прямых и кривых линий, закраски

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

некоторые из этих методов.

1. Алгоритмы вычерчивания отрезков

Поскольку экран дисплея можно рассматривать как матрицу дискретных

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

непосредственно провести отрезок из одной точки в другую. Процесс

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

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

наклоненных под углом 45( отрезков выбор растровых элементов очевиден. При

любой другой ориентации выбрать нужные пикселы труднее.

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

из них.

2. Цифровой дифференциальный анализатор

Один из методов разложения отрезка в растр состоит в решении

дифференциального уравнения, описывающего этот процесс. Для прямой линии

имеем:

[pic] или [pic]н

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

[pic]

где x1, y1 и x2, y2 – концы разлагаемого отрезка и yi – начальное значение

для очередного шага вдоль отрезка. Фактически уравнение (2.1.) представляет

собой рекуррентное соотношение для последовательных значений y вдоль

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

называется цифровым дифференциальным анализатором (ЦДА). В простом ЦДА либо

[pic], либо [pic] (большее из приращений) выбирается в качестве единицы

растра. Ниже приводится простой алгоритм, работающий во всех квадрантах:

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

анализатора (ЦДА)

предполагается, что концы отрезка (x1,y1) и (x2,y2) не совпадают

Integer – функция преобразования вещественного числа в целое.

Примечание: во многих реализациях функция Integer означает взятие целой

части, т.е. Integer(( 8.5) = ( 9, а не ( 8. В алгоритме используется именно

такая функция.

Sign ( функция, возвращающая ( 1, 0, 1 для отрицательного нулевого и

положительного аргумента соответственно.

if abs ( x2 ( x1 ) ( abs ( y2 ( y1 ) then

Длина = abs ( x2 ( x1 )

else

Длина = abs ( y2 ( y1 )

end if

полагаем большее из приращений (x или (y равным единице растра

(x = ( x2 ( x1 ) / Длина

(y = ( y2 ( y1 ) / Длина

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

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

квадрантов

x = x1 + 0.5 * Sign ( (x )

y = y1 + 0.5 * Sign ( (y )

начало основного цикла

i =1

while ( i ( Длина )

Plot ( Integer ( x ), Integer ( y ) )

x = x + (x

y = y + (y

i = i + 1

end while

finish

С помощью этого алгоритма получают прямые, вполне удовлетворительного

вида, но у него есть ряд недостатков. Во-первых, плохая точность в концевых

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

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

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

3. Алгоритм Брезенхема

Алгоритм Брезенхема выбирает оптимальные растровые координаты для

представления отрезка. В процессе работы одна из координат - либо x, либо у

(в зависимости от углового коэффициента) - изменяется на единицу. Изменение

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

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

Такое расстояние называется ошибкой.

Алгоритм построен так, что требуется проверять лишь знак этой ошибки.

На рис.2.1 это иллюстрируется для отрезка в первом

Ѕ ( (y ( 1 (ошибка ( 0)

0 ( (y/(x < Ѕ (ошибка <0)

Инициировать ошибку в – Ѕ

ошибка = ошибка + (y/(x

октанте, т. е. для отрезка с угловым коэффициентом, лежащим в диапазоне от

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

отрезка из точки (0,0) больше чем 1/2, то его пересечение с прямой x = 1

будет расположено ближе к прямой у = 1, чем к прямой у = 0. Следовательно,

точка растра (1,1) лучше аппроксимирует ход отрезка, чем точка (1,0). Если

угловой коэффициент меньше 1/2, то верно обратное. Для углового

коэффициента равного 1/2 нет какого-либо предпочтительного выбора. В данном

случае алгоритм выбирает точку (1,1).

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

только целочисленную арифметику и исключить деление. Т.к. важен лишь знак

ошибки, то приняв

[pic]

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

Чтобы реализация алгоритма была полной необходимо обрабатывать отрезки во

всех октантах. Когда абсолютная величина углового коэффициента больше 1, y

постоянно изменяется на единицу, а критерий ошибки Брезенхема используется

для принятия решения об изменении величены x. Выбор постоянно изменяющейся

(на +1 или –1) координаты зависит от квадранта (рис. 2.2).

Алгоритм Брезенхема может быть оформлен в следующем виде.

Обобщённый целочисленный алгоритм Брезенхема квадрантов

предполагается, что концы отрезка (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

инициализация [pic] с поправкой на половину пиксела

[pic] = 2 * (y ( (x

основной цикл

for i = 1 to (x

Plot ( x ,y )

While ( [pic] ( 0 )

If Обмен = 1 then

x = x + s1

else

y = y + s2

end if

[pic] = [pic] ( 2 * (x

end while

if Обмен = 1 then

y = y + s2

else

x = x + s1

end if

[pic] = [pic] + 2 * (y

next i

finish

Этот алгоритм удовлетворяет самым строгим требованиям. Он имеет

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

микропрограммном уровне.

4. Алгоритм Брезенхема для генерации окружностей

В растр нужно разлагать не только линейные, но и другие, более сложные

функции. Разложению конических сечений, т. е. окружностей, эллипсов,

парабол, гипербол посвящено значительное число работ. Наибольшее внимание,

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

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

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

восьмую часть окружности. Остальные её части могут быть получены

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

сгенерирован первый октант (от 0( до 45( против часовой стрелки), то второй

октант можно получить зеркальным отражением относительно прямой у = x, что

дает в совокупности первый квадрант. Первый квадрант отражается

относительно прямой x = 0 для получения соответствующей части окружности во

втором квадранте. Верхняя полуокружность отражается относительно прямой у =

0 для завершения построения. На рис.2.3. приведены двумерные матрицы

соответствующих преобразований.

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

начале координат. Заметим, что если работа алгоритма начинается в точке x =

0, у = R, то при генерации окружности по часовой стрелке в первом квадранте

у является монотонно убывающей функцией аргумента x (рис. 2.4). Аналогично,

если исходной точкой является y = 0, x = R, то при генерации окружности

против часовой стрелки x будет монотонно убывающей функцией аргумента у. В

нашем случае выбирается генерация по часовой стрелке с началом в точке x =

0, у = R. Предполагается, что центр окружности и начальная точка находятся

точно в точках растра.

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

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

образом приближающий окружность: горизонтально вправо, по диагонали вниз и

вправо, вертикально вниз. На рис.2.5 эти направления обозначены

соответственно mH, mD, mV. Алгоритм выбирает пиксел, для

которого минимален квадрат расстояния между одним из этих пикселов и

окружностью, т. е. минимум из

mH = | ( xi + 1 )2 + ( yi )2 – R2 |

mH = | ( xi + 1 )2 + ( yi ( 1 )2 – R2 |

mH = | ( xi )2 + ( yi ( 1 )2 – R2 |

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

xi, yi ) возможны только пять типов пересечений окружности и сетки растра,

приведенных на рис.2.6.

Разность между квадратами расстояний от центра окружности до

диагонального пиксела ( xi + 1, yi ( 1 ) и от центра до точки на окружности

R2 равна

[pic]

Как и в алгоритме Брезенхема для отрезка, для выбора соответствующего

пиксела желательно использовать только знак ошибки, а не её величину.

При ( < 0 диагональная точка ( xi + 1, yi ( 1 ) находится внутри

реальной окружности, т. е. это случаи 1 или 2 на рис.2.6. Ясно, что в этой

ситуации следует выбрать либо пиксел ( xi + 1, yi ) т. е. mH, либо пиксел (

xi + 1, yi ( 1 ), т. е. mD. Для этого сначала рассмотрим случай 1 и

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

горизонтальном и диагональном направлениях:

[pic]

При ( < 0 расстояние от окружности до диагонального пиксела

(mD) больше, чем до горизонтального (mH). Напротив, если ( > 0, расстояние

до горизонтального пиксела (mH) больше. Таким образом,

при ( < 0 выбираем mH ( xi + 1, уi )

при ( > 0 выбираем mD ( xi + 1, уi – 1 )

При ( = 0, когда расстояния от окружности до обоих пикселов одинаковы,

выбираем горизонтальный шаг.

Количество вычислений, необходимых для оценки величины (, можно

сократить, если заметить, что в случае 1

[pic]

так как диагональный пиксел ( xi + 1, уi – 1 ) всегда лежит внутри

окружности, а горизонтальный ( xi + 1, уi ) - вне ее. Таким образом, (

можно вычислить по формуле

[pic]

Дополнение до полного квадрата члена ( yi )2 с помощью добавления и

вычитания - 2уi + 1 дает

[pic]

В квадратных скобках стоит по определению (i, и его подстановка

( = 2((i + yi) – 1

существенно упрощает выражение.

Рассмотрим случай 2 на рис.2.6 и заметим, что здесь должен быть выбран

горизонтальный пиксел ( xi + 1, уi ), так как у является монотонно

убывающей функцией. Проверка компонент ( показывает, что

[pic]

поскольку в случае 2 горизонтальный ( xi + 1, уi ) и диагональный ( xi + 1,

уi – 1 ) пикселы лежат внутри окружности. Следовательно, ( < 0, и при

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

( xi + 1, уi ).

Если (i > 0, то диагональная точка ( xi + 1, уi – 1 ) находится вне

окружности, т. е. это случаи З и 4 на рис.2.6. В данной ситуации ясно, что

должен быть выбран либо пиксел ( xi + 1, уi – 1 ), т. е. mD, либо ( xi, уi

– 1 ), т. е. mV. Аналогично разбору предыдущего случая критерий выбора

можно получить, рассматривая сначала случай З и проверяя разность между

квадратами расстояний от окружности до диагонального mD и вертикального mV

пикселов, т. е.

[pic]

При (\ < 0 расстояние от окружности до вертикального пиксела ( xi, уi –

1 ) больше и следует выбрать диагональный шаг mD, к пикселу ( xi + 1, уi –

1 ). Напротив, в случае (\ > 0 расстояние от окружности до диагонального

пиксела больше и следует выбрать вертикальное движение к пикселу ( xi, уi –

1 ). Таким образом,

при ( ( 0 выбираем mD в ( xi + 1, уi – 1 )

при ( < 0 выбираем mV в ( xi, уi – 1 )

Здесь в случае ( = 0, т. е. когда расстояния равны, выбран диагональный

шаг.

Проверка компонент (\ показывает, что

[pic]

поскольку для случая З диагональный пиксел ( xi + 1, уi – 1 ) находится вне

окружности, тогда как вертикальный пиксел ( xi, уi – 1 ) лежит внутри ее.

Это позволяет записать (\ в виде

[pic]

Дополнение до полного квадрата члена ( xi )2 с помощью добавления и

вычитания 2xi + 1 дает

[pic]

Использование определения (i приводит выражение к виду

[pic]

Теперь, рассматривая случай 4, снова заметим, что следует выбрать

вертикальный пиксел ( xi, уi – 1 ), так как y является монотонно убывающей

функцией при возрастании x. проверка компонент (\ для случая 4 показывает,

что

[pic]

поскольку оба пиксела находятся вне окружности. Следовательно, (\ > 0 и при

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

выбор mV.

Осталось проверить только случай 5 на рис.2.7, который встречается,

когда диагональный пиксел ( xi + 1, уi – 1 ) лежит на окружности, т. е. (i

= 0. Проверка компонент ( показывает, что

[pic]

Следовательно, ( > 0 и выбирается диагональный пиксел ( xi + 1, уi – 1 ).

Аналогичным образом оцениваем компоненты (\:

[pic]

и ( < 0, что является условием выбора правильного диагонального шага к ( хi

+ 1, уi – 1 ). Таким образом, случай (i = 0 подчиняется тому же критерию,

что и случай (i < 0 или (i > 0.

Подведем итог полученных результатов:

(i < 0

( ( 0 выбираем пиксел ( хi + 1, уi ) ( mH

( > 0 выбираем пиксел ( хi + 1, уi – 1 ) ( mD

(i > 0

(\ ( 0 выбираем пиксел ( хi + 1, уi – 1 ) ( mD

(\ > 0 выбираем пиксел ( хi , уi – 1 ) ( mV

(i = 0 выбираем пиксел ( хi + 1, уi – 1 ) ( mD

Легко разработать простые рекуррентные соотношения дня реализации

пошагового алгоритма. Сначала рассмотрим горизонтальный шаг mH к пикселу (

хi + 1, уi ). Обозначим это новое положение пиксела как ( i + 1 ). Тогда

координаты нового пиксела и значение (i равны

[pic]

Аналогично координаты нового пиксела и значения (i для шага mD к пикселу (

хi + 1, уi – 1 ) таковы:

[pic]

То же самое для шага mV к ( хi, уi – 1 )

[pic]

Реализация алгоритма Брезенхема для окружности приводиться ниже.

Пошаговый алгоритм Брезенхема для генерации окружности в первом квадранте

все переменные целые

xi = 0

yi = R

(i = 2(1 – R)

Предел = 0

1. Plot ( xi, yi )

if yi ( Предел then 4

выделение случая 1 или 2, 4 или 5, или 3

if (i < 0 then 2

if (i > 0 then 3

if (i = 0 then 20

определение случая 1 или 2

2. ( = 2(i + 2yi – 1

if ( ( 0 then 10

if ( > 0 then 20

определение случая 4 или 5

3. ( = 2(i + 2xi – 1

if ( ( 0 then 20

if ( > 0 then 30

выполнение шагов

шаг mH

10. xi = xi +1

(i = (i +2xi + 1

goto 1

шаг mD

20. xi = xi +1

yi = yi – 1

(i = (i +2xi – 2yi + 2

goto 1

шаг mV

30 yi = yi – 1

(i = (i – 2xi + 1

goto 1

4 finish

5. Растровая развёртка сплошных областей

До сих пор речь шла о представлении на растровом графическом устройстве

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

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

сплошных областей из простых описаний ребер или вершин будем называть

растровой разверткой сплошных областей, заполнением многоугольников или

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

которые обычно делятся на две широкие категории: растровая развертка и

затравочное заполнение.

В методах растровой развертки пытаются определить в порядке

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

алгоритмы обычно иду от «верха» многоугольника или контура к «низу».

В методах затравочного заполнения предполагается, что известна

некоторая точка (затравка) внутри замкнутого контура. В алгоритмах ищут

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

точка расположена не внутри, значит, обнаружена граница контура. Если же

точка оказалась внутри контура, то она становится новой затравочной точкой

и поиск продолжается рекурсивно.

6. Растровая развёртка многоугольников

Можно разработать эффективный метод растровой развёртки

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

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

Это свойство называется пространственной когерентностью.

Характеристики пикселов на данной строке изменяются только там, где

ребро многоугольника пересекает строку. Эти пересечения делят сканирующую

строку на области.

Для простого многоугольника на рис. 2.7 строка 2 пересекает

многоугольник при x = 1 и x = 8.

Получаем три области:

x < 1 вне многоугольника

1 ( x ( 8 внутри многоугольника

x > 8 вне многоугольника

Строка 4 делится на пять областей:

x < 1 вне многоугольника

1 ( x ( 4 внутри многоугольника

4 < x < б вне многоугольника

б ( x ( 8 внутри многоугольника

x > 8 вне многоугольника

Совсем необязательно, чтобы точки пересечения для строки 4 сразу

определялись в фиксированном порядке (слева направо). Например, если

многоугольник задаётся списком вершин P1, P2, P3, P4, а список рёбер (

последовательными парами вершин P1P2, P2P3, P3P4, P4P5, P5P1, то для строки

4 будут найдены следующие точки пересечения с рёбрами многоугольника: 8, 6,

4, 1. Эти точки надо отсортировать в возрастающем порядке по x, т. е.

получить 1,4, 6, 8.

При определении интенсивности, цвета и оттенка пикселов на сканирующей

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

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

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

крайних (от начала строки до первой точки пересечения и от последней точки

пересечения до конца строки) используется фоновая интенсивность или цвет.

Точное определение тех пикселов, которые должны активироваться,

требует некоторой осторожности. Рассмотрим простой прямоугольник,

изображенный на рис. 2.8. Прямоугольник имеет координаты (1,1), (5,1),

(5,4), (1,4). Сканирующие строки с 1 по 4 имеют пересечения с ребрами

многоугольника при x = 1 и 5. Пиксел адресуется координатами своего левого

нижнего угла, значит, для каждой из этих сканирующих строк будут

активированы пикселы с x-координатами 1, 2, 3, 4 и 5. На рис. 2.8 показан

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

равна 20, в то время как настоящая площадь прямоугольника равна 12.

Модификация системы координат сканирующей строки и теста активации

устраняет эту проблему, как это показано на рис. 2.8,b. Считается, что

сканирующие строки проходят через центр строк пикселов, т. е. через

середину интервала, как это показано на рис. 2.8,b. Тест активации

модифицируется следующим образом: проверяется, лежит ли внутри интервала

центр пиксела, расположенного справа от пересечения. Однако пикселы все еще

адресуются координатами левого нижнего угла. Как показано на рис.2.8,b,

результат данного метода корректен.

Горизонтальные ребра не могут пересекать сканирующую строку и, таким

образом, игнорируются. Это совсем не означает, что их нет на рисунке. Эти

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

Дополнительная трудность возникает при пересечении сканирующей строки и

многоугольника точно по вершине, как это показано на рис. 2.9. При

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

получаем, что строка у = 3.5 пересечет многоугольник в 2, 2 и 8, т. е.

получится нечетное количество пересечений. Следовательно, разбиение

пикселов на пары даст неверный результат, т. е. пикселы (0,3), (1,3) и от

(3,3) до (7,3) будут фоновыми, а пикселы (2,3), (8,3), (9,3) окрасятся в

цвет многоугольника. Если учитывать только одну точку пересечения с

вершиной. Тогда для строки у = 3.5 получим правильный результат. Однако

результат применения метода к строке у = 1.5, имеющей два пересечения в

(5,1), показывает, что метод неверен. Для этой строки именно разбиение на

пары даст верный результат, т. е. окрашен будет только пиксел (5,1). Если

же учитывать в вершине только одно пересечение, то пикселы от (0,1) до

(4,1) будут фоновыми, а пикселы от (5,1) до (9,1) будут окрашены в цвет

многоугольника.

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

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

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

максимум или минимум многоугольника в рассматриваемой вершине можно с

помощью проверки концевых точек двух ребер. Если у обоих рёбер у больше,

чем у вершины, значит, вершина является точкой локального минимума. Если

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

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

минимума, ни точкой локального максимума. На рис.2.10 точка Р1 - локальный

минимум, Р3 - локальный максимум, а Р2, Р4 - ни то ни другое.

Следовательно, в точках Р1 и Р3 учитываются два пересечения со сканирующими

строками, а в Р2 и Р4 - одно.

7. Алгоритм с упорядоченным списком рёбер

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

алгоритмы растровой развертки сплошных областей, называемые алгоритмами с

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

эффективности сортировки. Приведём очень простой алгоритм.

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

Подготовить данные:

Используя сканирующие строки, проведенные через середины отрезков, т.

е. через у + Ѕ определить для каждого ребра многоугольника наивысшую

сканирующую строку, пересекаемую ребром.

Занести ребро многоугольника в у- группу, соответствующую этой

сканирующей строке.

Сохранить в связном списке значения: начальное значение координат x

точек пересечения, (y - число сканирующих строк, пересекаемых ребром

многоугольника, и ~ (x – шаг приращения по x при переходе от одной

сканирующей строки к другой.

Преобразовать эти данные в растровую форму:

Для каждой сканирующей строки проверить соответствующую у- группу на

наличие новых ребер. Новые ребра добавить в список активных рёбер.

Отсортировать координаты x точек пересечения из САР в порядке

возрастания; т. е. х1 предшествует x2, если х1 < х2

Выделить пары точек пересечений из отсортированного по

x списка. Активировать на сканирующей строке y пикселы для целых

значений x, таких, что x1 ( x + Ѕ ( x2. Для каждого ребра из САР

уменьшить (у на 1. Если (у < 0, то исключить данное ребро из САР.

Вычислить новое значение координат x точек пересечения xнов = xстар +

(x

Перейти к следующей сканирующей строке

В алгоритме предполагается, что все данные предварительно преобразованы

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

8. Алгоритм заполнения по рёбрам

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

Первый шаг состоит в обрисовке контура, в результате чего на каждой

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

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

точно алгоритм можно сформулировать в следующем виде:

Алгоритм со списком ребер и флагом

Обрисовка контура:

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

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

левый пиксел, центр которого лежит справа от пересечения;

т.е.

x + 1/2 > xпересечения

Заполнение:

Для каждой сканирующей строки, пересекающей многоугольник

Внутри = FALSE

for x = 0 (левая граница) to x = xmax, (правая граница)

if пиксел в точке x имеет граничное значение

then инвертировать значение переменной Внутри

if Внутри = TRUE then

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

else

присвоить пикселу в x значение цвета фона

end if

next x

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

что затраты на ввод/вывод значительно меньше, чем в алгоритме со списком

рёбер, в результате чего, при его аппаратной реализации, он работает на

один-два порядка быстрее чем алгоритм с упорядоченным списком рёбер.

9. Алгоритмы заполнения с затравкой

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

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

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

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

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

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

- определенным, то все пикселы, принадлежащие внутренней части, имеют один

и тот же цвет или интенсивность, а все пикселы, внешние по отношению к

области, имеют другой цвет. Это продемонстрировано на рис. 2.10. Если

область относится к гранично-определенным, то все пикселы на границе

области имеют выделенное значение или цвет, как это показано на рис. 2.11.

Алгоритмы, заполняющие внутренне - определенные области, называются

внутренне - заполняющими, а алгоритмы для гранично-определённых областей –

гранично-заполняющими. Далее будут обсуждаться гранично-заполняющие

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

получить аналогичным образом.

Внутренне- или гранично-определённые области могут быть 4- или 8-

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

помощью комбинаций движений только в 4-х направлениях: налево, направо,

вверх, вниз. Для 8-и связной области добавляются ещё и диагональные

направления. Алгоритм заполнения 8-связной области заполнит и 4-связную, но

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

цветами две отдельные 4-связные области, использование 8-связного алгоритма

даст не верный результат. Далее речь пойдёт об алгоритмах для 4-связных

областей, однако их легко адаптировать и для 8-связных.

10. Построчный алгоритм заполнения с затравкой

Используя стек, можно разработать алгоритм заполнения гранично-

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

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

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

довольно большим. Зачастую в нём содержится дублирующаяся информация. В

построчном алгоритме заполнения с затравкой стек минимизируется за счёт

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

сканирующей строке. Непрерывный интервал - это группа примыкающих друг к

другу пикселов (ограниченная уже заполненными или граничными пикселами). Мы

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

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

Данный алгоритм применим гранично-определённым 4-связным областям,

которые могут быть как выпуклыми, так и не выпуклыми, а также могут

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

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

работу алгоритма можно разбить на четыре этапа.

Построчный алгоритм заполнения с затравкой

Затравочный пиксел на интервале извлекается из стека, содержащего

затравочные пикселы.

Интервал с затравочным пикселом заполняется влево и вправо от

затравки вдоль сканирующей строки до тех пор пока не будет найдена

граница.

В переменной Xлев и Xправ запоминаются крайний левый и крайний правый

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

В диапазоне Xлев ( x ( Xправ проверяются строки расположенные

непосредственно над в под текущей строкой. Определяется, есть ли на

них еще не заполненные пикселы. Если такие пикселы есть (т. е. не все

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

крайний правый пиксел в каждом интервале отмечается как затравочный и

помещается в стек.

При инициализации алгоритма в стек помешается единственный затравочный

пиксел, работа завершается при опустошении стека. Ниже приводится более

подробное описание алгоритма на псевдокоде.

Построчный алгоритм заполнения с затравкой

Затравка ( x, y ) выдаёт затравочный пиксел

Pop - процедура, которая извлекает пиксел из стека

Push - процедура, которая помещает пиксел в стек

инициируем стек

Push Затравка ( x, y )

While ( стек не пуст )

Извлекаем пиксел из стека и присваиваем ему новое значение Pop

Пиксел ( x, y )

Пиксел ( x, y ) = Нов_значение

сохраняем x- координату затравочного пиксела

Врем_х = x

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

x = x +1

while Пиксел ( x, y ) ( Гран_значение

Пиксел ( x, y ) = Нов_значение

x = x +1

end while

сохраняем крайний справа пиксел

Xправ = x (1

восстанавливаем x- координату затравки

x = Врем_х

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

x = x (1

while Пиксел ( x, y ) ( Гран_значение

Пиксел ( x, y ) = Нов_значение

x = x (1

end while

сохраняем крайний слева пиксел

Xлев = x +1

восстанавливаем x- координату затравки

x = Врем_х

проверим, что строка выше не является ни границей многоугольника, ни

уже полностью заполненной; если это не так, то найти затравку, начиная

с левого края подинтервала сканирующей строки

x = Xлев

y = y +1

while x ( Xправ

ищем затравку на строке выше

Флаг = 0

while ( Пиксел ( x, y ) ( Гран_значение and

Пиксел ( x, y ) ( Нов_значение and x < Xправ )

if Флаг = 0 then Флаг = 1

x = x + 1

end while

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

if Флаг =1 then

if ( x = Xправ and Пиксел ( x, y ) ( Гран_значение

and Пиксел ( x, y ) ( Нов_значение ) then

Push Пиксел ( x, y )

else

Push Пиксел ( x ( 1, y )

end if

Флаг = 0

end if

продолжим проверку, если интервал был прерван

Xвход = x

while (( Пиксел ( x, y ) = Гран_значение or

Пиксел ( x, y ) = Нов_значение ) and x < Xправ)

x = x + 1

end while

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

if x = Xвход then x = x + 1

end while

проверим, что строка ниже не является ни границей многоугольника, ни

уже полностью заполненной

Эта часть алгоритма совершенно аналогична проверке для строки

выше, за исключением, того что вместо y = y + 1 надо подставить

y = y ( 1

end while

finish

3. Удаление невидимых линий и поверхностей

Задача удаления невидимых линий и поверхностей является одной из

наиболее сложных в машинной графике. Алгоритмы удаления невидимых линий и

поверхностей служат для определения линий ребер, поверхностей или объемов,

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

пространства.

Необходимость удаления невидимых линий, ребер, поверхностей или объемов

проиллюстрирована рис.3.1. На рис.4.1, а приведен типичный каркасный чертеж

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

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

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

Результаты показаны на рис.4.1, b и c.

Сложность задачи удаления невидимых линий и поверхностей привела к

появлению большого числа, различных способов ее решения. Многие из них

ориентированы на специализированные приложения. Наилучшего решения общей

задачи удаления невидимых линий и поверхностей не существует. Для

моделирования процессов в реальном времени, например, для авиа тренажеров,

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

видео генерации (30 кадр/с). Для машинной мультипликации требуются

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

которых представлены тени, прозрачность и фактура, учитывающие эффекты

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

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

даже часов. Строго говоря, учет эффектов прозрачности, фактуры, отражения и

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

Естественнее считать их частью процесса визуализации изображения. Процесс

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

сцены в реалистической манере. Однако многие из этих эффектов встроены в

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

Существует тесная взаимосвязь между скоростью работы алгоритма и

детальностью его результата. Ни один из алгоритмов не может достигнуть

хороших оценок для этих двух показателей одновременно. По мере создания все

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

Реальные задачи, однако, всегда будут требовать учета еще большего

количества деталей.

Алгоритмы удаления невидимых линий или поверхностей можно

классифицировать по способу выбора системы координат или пространства, в

котором они работают. Алгоритмы, работающие в объектном пространстве, имеют

дело с физической системой координат, в которой описаны эти объекты. При

этом получаются весьма точные результаты, ограниченные, вообще говоря, лишь

точностью вычислений. Полученные изображения можно свободно увеличивать во

много раз. Алгоритмы, работающие в объектном пространстве, особенно полезны

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

работающие в пространстве изображения, имеют дело с системой координат того

экрана, на котором объекты визуализируются. При этом точность вычислений

ограничена разрешающей способностью экрана. Результаты, полученные в

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

соответствовать исходной сцене. Алгоритмы, формирующие список приоритетов

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

Объем вычислений для любого алгоритма, работающего в объектном

пространстве, и сравнивающего каждый объект сцены со всеми остальными

объектами этой сцены, растет теоретически как квадрат числа объектов ( n2

). Аналогично, объем вычислений любого алгоритма, работающего в

пространстве изображения и сравнивающего каждый объект сцены с позициями

всех пикселов в системе координат экрана, растет теоретически, как nN.

Здесь n обозначает количество объектов (тел, плоскостей или ребер) в сцене,

а N - число пикселов. Теоретически трудоемкость алгоритмов, работаюoих в

объектном пространстве, меньше трудоемкости алгоритмов, работающих в

пространстве изображения, при n < N. Поскольку N обычно равно ( 512 )2, то

теоретически большинство алгоритмов следует реализовывать в объектном

пространстве. Однако на практике это не так. Дело в том, что алгоритмы,

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

легче воспользоваться преимуществом когерентности при растровой реализации.

Далее дается изложение некоторых алгоритмов, работающих как в объектном

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

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

невидимых линий и поверхностей.

1. Алгоритм плавающего горизонта

Алгоритм плавающего горизонта чаще всего используется для удаления

невидимых линий трехмерного представления функций, описывающих поверхность

в виде

F ( x, у, z ) = 0

Подобные функции возникают во многих приложениях в математике, технике,

естественных науках и других дисциплинах.

Существует много алгоритмов, использующих этот подход. Поскольку в

приложениях в основном нас интересует описание поверхности, этот алгоритм

обычно работает в пространстве изображения. Главная идея данного метода

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

исходной поверхности последовательностью параллельных секущих плоскостей,

имеющих постоянные значения координат x, y или z.

На рис. 3.2 приведен пример, где указанные параллельные плоскости

определяются постоянными значениями z. Функция F ( x, у, z ) = 0 сводится к

последовательности кривых, лежащих в каждой из этих параллельных

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

y = f ( x, z ) или y = g ( y, z )

где z постоянно на каждой из заданных параллельных плоскостей.

Итак, поверхность теперь складывается из последовательности кривых,

лежащих в каждой из этих плоскостей, как показано на рис. 3.3. Здесь

предполагается, что полученные кривые являются однозначными функциями

независимых переменных. Если спроецировать полученные кривые на плоскость z

= 0, то сразу становится ясна идея алгоритма удаления невидимых участков

исходной поверхности. Алгоритм сначала упорядочивает плоскости

z = const по возрастанию расстояния до них от точки наблюдения. Затем для

каждой плоскости, начиная с ближайшей к точке наблюдения, строится кривая,

лежащая на ней. Алгоритм удаления невидимой линии заключается в следующем:

Если на текущей плоскости при некотором заданном значении x

соответствующее значение y на кривой больше значения y для всех

предыдущих кривых при этом значении x, то текущая кривая видима в

этой точке; в противном случае она невидима.

Реализация данного алгоритма достаточно проста. Для хранения максимальных

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

числу различимых точек (разрешению) по оси x в пространстве изображения.

Значения, хранящиеся в этом массиве, представляют собой текущие значения

«горизонта». Поэтому по мере рисования каждой очередной кривой этот

горизонт «всплывает». Фактически этот алгоритм удаления невидимых линий

работает каждый раз с одной линией.

Алгоритм работает очень хорошо до тех пор, пока какая-нибудь очередная

кривая не окажется ниже самой первой из кривых. Как показано на рис.3.4,а.

Подобные кривые, естественно, видимы и представляют собой нижнюю сторону

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

сторона поверхности делается видимой, если модифицировать этот алгоритм,

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

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

числу различимых точек по оси x в пространстве изображения. Этот массив

содержит наименьшие значения y для каждого значения x. Алгоритм теперь

становится таким:

Если на текущей плоскости при некотором заданном значении x

соответствующее значение y на кривой больше максимума или меньше

минимума по y для всех предыдущих кривых при этом x, то текущая

кривая видима. В противном случае она невидима.

Полученный результат показан на рис. 3.4, b.

В изложенном алгоритме предполагается, что значение функции, т. е. y,

известно для каждого значения x в пространстве изображения. Однако если

для каждого значения x нельзя указать (вычислить) соответствующее ему

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

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

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

нижнего плавающих горизонтов, как показано на рис. 3.5. Если видимость

кривой меняется, то метод с такой простой интерполяцией не даст корректного

результата. Этот эффект проиллюстрирован рис. 3.6,а. Предполагая, что

операция по заполнению массивов проводится после проверки видимости,

получаем, что при переходе текущей кривой от видимого к невидимому

состоянию (сегмент АВ на рис. 3.6,а), точка (xn+k, yn+k ) объявляется

невидимой. Тогда участок кривой между точками (xn, yn) и (xn+k, yn+k ) не

изображается и операция по заполнению массивов не производится. Образуется

зазор между текущей и предыдущей кривыми Если на участке текущей кривой

происходит переход от невидимого состояния к видимому (сегмент CD на рис.

3.6,а), то точка (xm+k, ym+k ) объявляется видимой, а участок кривой между

точками (xm, ym) и (xm+k, ym+k ) изображается и операция по заполнению

массивов проводится. Поэтому изображается и невидимый кусок сегмента CD.

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

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

последующих кривы. Следовательно,

необходимо решать задачу о поиске точек пересечения сегментов текущей и

предшествующей кривых.

Существует несколько методов получения точек пересечения кривых. На

растровых дисплеях значение координаты x можно увеличивать на 1, начиная с

xn или xm (рис. 3.6,а). Значение у, соответствующее текущему значению

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

значению у, соответствующему предыдущему значению координаты x,

вертикального приращения (y вдоль заданной кривой. Затем определяется

видимость новой точки с координатами (x + 1, y + (y ). Если эта точка

видима, то активируется связанный с ней пиксел. Если невидима, то пиксел не

активируется, а x увеличивается на 1. Этот процесс продолжается до тех пор,

пока не встретится xn+k или xm+k. Пересечения для растровых дисплеев

определяются изложенным методом с достаточной точностью. Близкий и даже

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

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

интерполируют текущую и предшествующую кривые, между точками (xn, yn) и

(xn+k, yn+k ) (рис. 3.6) задается формулами:

[pic]

где

[pic]

а индексы c и p соответствуют текущей и предшествующей кривым. Полученный

результат показан на рис. 3.6,b. Теперь алгоритм излагается более

формально.

Если на текущей плоскости при некотором заданном значении x

соответствующее значение y на кривой больше максимума или меньше

минимума по y для всех предыдущих кривых при этом x, то текущая

кривая видима. В противном случае она невидима.

Если на участке от предыдущего (xn) до текущего (xn+k) значения x

видимость кривой изменяется, то вычисляется точка пересечения (xi).

Если на участке от xn до xn+k сегмент кривой полностью видим, то он

изображается целиком; если он стал невидимым, то изображается

фрагмент от xn до xi; если же он стал видимым, то изображается

фрагмент от xi до xn+k.

Заполнить массивы верхнего и нижнего плавающих горизонтов.

Изложенный алгоритм приводит к некоторым дефектам, когда кривая,

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

появляется слева или справа из-под множества кривых, лежащих в плоскостях,

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

на рис. 3.7, где уже обработанные плоскости n - 1 и n расположены ближе к

точке наблюдения. На рисунке показано, что получается при обработке

плоскости n + 1. После обработки кривых n - 1 и n верхний горизонт для

значений x = 0 и 1 равен начальному значению у; для значений x от 2 до 17

он равен ординатам кривой n; а для значений 18, 19, 20 - ординатам кривой n

- 1. Нижний горизонт для значений x = 0 и 1 равен начальному значению у;

для значений x = 2, 3, 4 – ординатам кривой n; а для значений x от 5 до 20

- ординатам кривой n - 1. При обработке текущей кривой (n + 1) алгоритм

объявляет ее видимой при x = 4. Это показано сплошной линией на рис. 3.7.

Аналогичный эффект возникает и справа при x = 18. Такой эффект приводит к

появлению зазубренных боковых ребер. Проблема с зазубренностью боковых

ребер решается включением в массивы верхнего и нижнего горизонтов ординат,

соответствующих штриховым линиям на рис. 3.7. Это можно выполнить

эффективно, создав ложные боковые ребра. Приведем алгоритм, реализующий эту

идею для обеих ребер.

Обработка левого бокового ребра:

Если Pn является первой точкой на первой кривой, то запомним Pn в

качестве Pn(1 и закончим заполнение. В противном случае создадим

ребро, соединяющее Pn и Pn(1.

Занесем в массивы верхнего и нижнего горизонтов ординаты этого

ребра и запомним Pn в качестве Pn(1.

Обработка правого бокового ребра:

Если Pn является последней точкой на первой кривой, то запомним Pn в

качестве Pn(1 и закончим заполнение. В противном случае создадим

ребро, соединяющее Pn и Pn(1.

Занесем в массивы верхнего и нижнего горизонтов ординаты этого

ребра и запомним Pn в качестве Pn(1.

Теперь полный алгоритм выглядит так:

Для каждой плоскости z = const.

Обработать левое боковое ребро.

Для каждой точки, лежащей на кривой из текущей плоскости:

Если при некотором заданном значении x соответствующее значение у

на кривой больше максимума или меньше минимума по у для всех

предыдущих кривых при этом x, то кривая видима (в этой точке). В

противном случае она невидима.

Если на сегменте от предыдущего (xn) до текущего (xn+k) значения x

видимость кривой изменяется, то вычисляется пересечение (xi).

Если на участке от xn до (xn+k) сегмент кривой полностью видим, то

он изображается целиком; если он cтал невидимым, то изображается

его кусок от xn до xi; если же он стал видимым, то изображается его

кусок от xi до xn+k.

Заполнить массивы верхнего и нижнего плавающих горизонтов.

Обработать правое боковое ребро.

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

алгоритм может дать некорректные результаты. Во избежании этого если

встречаются узкие участки, то функцию следует вычислять в большем числе

точек.

На рис. 3.8 показан типичный результат работы алгоритма плавающего

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

Алгоритм плавающего горизонта

Гэкран – разрешение экрана в горизонтальном направлении

Вэкран – разрешение экрана в вертикальном направлении

Верх – массив, содержащий координаты верхнего горизонта

Низ – массив, содержащий координаты нижнего горизонта

Y – текущее значение функции y = f ( x, z ) при z = const

Тфлаг – флаг видимости для текущей точки

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

0 = невидима

1 = видима и выше верхнего горизонта

-1 = видима и ниже нижнего горизонта

Draw – графическая команда, которая чертит видимую линию между точками,

заданными их координатами.

Xmin, Xmax – минимальная и максимальная абсциссы функции

Xшаг – шаг приращения вдоль оси x

Zmin, Zmax – минимальная и максимальная аппликата функции

Zшаг – шаг между плоскостями z = const

Dimension Верх (Гэкран), Низ (Гэкран)

инициализация переменных

Xлевое = (1; Yлевое = (1; Xправое = (1; Yправое = (1

инициализация массивов горизонтов

Верх = 0

Низ = Вэкран

Вычисление функции на каждой плоскости z = const, начиная с ближайшей к

наблюдателю плоскости Zmax

for z = Zmax to Zmin step ( Zшаг

инициализация предыдущих значений по x и y: Xпред и Yпред

Xпред = Xmin

Yпред = f (Xmin, z)

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

Xпред, Yпред, z в данной точке

обработка левого бокового ребра

call Обрребра (Xпред, Yпред, Xлев, Yлев; Верх, Низ)

call Видимость (Xпред, Yпред, Верх, Низ; Пфлаг)

для каждой точки на кривой, лежащей в плоскости z = const

for x = Xmin to Xmax step Xшаг

y = f (x, z)

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

данной точке

проверка видимости текущей точки и заполнение соответствующего

массива горизонта

call Видимость (x, y, Верх, Низ; Тфлаг)

if Тфлаг = Пфлаг then

if (Тфлаг = 1) or (Тфлаг = (1) then

Draw (Xпред, Yпред, x, y)

call Горизонт (Xпред, Yпред, x, y; Верх, Низ)

end if

если видимость изменилась, то вычисляется пересечение и заполняется

массив горизонта

else

if Тфлаг = 0 then

if Пфлаг = 1 then

call Пересечение (Xпред, Yпред, x, y, Верх; Xi, Yi)

else

call Пересечение (Xпред, Yпред, x, y, Низ; Xi, Yi)

end if

Draw (Xпред, Yпред, Xi, Yi)

сall Горизонт (Xпред, Yпред, Xi, Yi, Верх, Низ)

else

if Тфлаг = 1 then

if Пфлаг = 0 then

call Пересечение (Xпред, Yпред, x, y, Верх; Xi, Yi)

Draw (Xi, Yi, x, y)

сall Горизонт (Xi, Yi, x, y; Верх, Низ)

else

call Пересечение (Xпред, Yпред, x, y, Низ; Xi, Yi)

Draw (Xпред, Yпред, Xi, Yi)

call Горизонт (Xпред, Yпред, Xi, Yi; Верх, Низ)

call Пересечение (Xпред, Yпред, x, y, Верх; Xi, Yi)

Draw (Xi, Yi, x, y)

call Горизонт (Xi, Yi, x, y; Верх, Низ)

end if

else

if Пфлаг = 0 then

call Пересечение (Xпред, Yпред, x, y, Верх; Xi, Yi)

Draw (Xi, Yi, x, y)

call Горизонт (Xi, Yi, x, y; Верх, Низ)

else

call Пересечение (Xпред, Yпред, x, y, Верх; Xi, Yi)

Draw (Xпред, Yпред, Xi, Yi)

call Горизонт (Xпред, Yпред, Xi, Yi; Верх, Низ)

call Пересечение (Xпред, Yпред, x, y, Низ; Xi, Yi)

Draw (Xi, Yi, x, y)

call Горизонт (Xi, Yi, x, y; Верх, Низ)

end if

end if

end if

end if

вновь инициализировать Пфлаг, Xпред, Yпред

Пфлаг = Тфлаг

Xпред = x

Yпред = y

next x

обработка правого концевого ребра

call Обрребра (x, y, Xправ, Yправ; Верх, Низ)

next z

finish

подпрограмма обработки бокового ребра

Subroutine Обрребра (x, y, Xребра, Yребра; Верх, Низ)

если Xребра = (1, то встречена первая кривая и ребро не создаётся

if Xребра = (1 then 1

call Горизонт (Xребра, Yребра, x, y; Верх, Низ)

1 Xребра = x

Yребра = y

return

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

Subroutine Видимость (x, y, Верх, Низ; Тфлаг)

видимость точки определяется по отношению к верхнему и нижнему

плавающим горизонтам. Если точка лежит на самом горизонте, то она

считается видимой.

Тфлаг = 0, если точка невидима

= 1, если она видима и выше верхнего горизонта

= (1, если она видима и ниже нижнего горизонта

x считается целой

if (y < Верх (x)) and (y > Низ (x)) then Тфлаг = 0

if y ( Верх (x) then Тфлаг = 1

if y ( Низ (x) then Тфлаг = (1

return

подпрограмма заполнения массивов плавающих горизонтов

Subroutine Горизонт (X1, Y1, X2, Y2; Верх, Низ)

Эта программа использует линейную интерполяцию для заполнения массивов

горизонтов между X1 и X2

Max (a, b) – определяет большее из a и b

Min (a, b) – определяет меньшее из a и b

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

if (X2 ( X1) = 0 then

Верх (X2) = Max (Верх (X2), Y2)

Низ (X2) = Min (Низ (X2), Y2)

else

Наклон = (Y2 ( Y1)/(X2 ( X1)

for x = X1 to X2 step 1

y = Наклон * (x ( X1) + Y1

Верх (x) = Max (Верх (x), y)

Низ (x) = Min (Низ (x), y)

next x

end if

return

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

Subroutine Пересечение (X1, Y1, X2, Y2, Массив; Xi, Yi)

Эта процедура вычисляет пересечение двух отрезков прямых

Массив содержит информацию о соответствующем горизонте

Sign – функция принимающая значения (1, 0, 1, если знак её аргумента

<0, =0, >0 соответственно

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

if (X2 – X1) = 0 then

Xi = X2

Yi = Массив (X2)

else

вычисление пересечения

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

пересечение считается обнаруженным, когда изменяется знак разности

значений y

Наклон = (Y2 – Y1)/(X2 – X1)

Ysign = Sign (Y1 + Наклон ( Массив (X1 + 1))

Csign = Ysign

Yi = Y1 + Наклон

Xi = X1 + 1

while Csign = Ysign

Yi = Y1 + Наклон

Xi = X1 + 1

Csign = Sign (Yi - Массив (Xi))

end while

выбирается ближайшее целое число

if |Yi ( Наклон ( Массив (X1 – 1)| ( |Yi ( Наклон ( Массив (X1)| then

Yi = Y1 – Наклон

Xi = X1 – 1

end if

end if

return

В приведенных выше алгоритме и примере функция у = f (x, z)

рассматривалась только при z = const. Часто бывает удобно вычерчивать

кривые, полагая постоянными как z, так и x. При этом возникает эффект

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

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

плоскостями z = const и x = const. Однако это не так. Верный результат

получается при обработке тех кривых из числа лежащих в плоскостях z = const

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

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

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

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

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

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

и нижнего плавающих горизонтов. Если используется перекрестная штриховка,

то не надо формировать левое и правое боковые ребра.

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

Алгоритм Робертса представляет собой первое известное решение задачи об

удалении невидимых линий . Это математически элегантный метод, работающий в

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

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

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

того, какая его часть или части, если таковые есть, экранируются этими

телами. Поэтому вычислительная трудоемкость алгоритма Робертса растет

теоретически как квадрат числа объектов. Именно этот факт привёл к снижению

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

этом алгоритме, просты, мощны и точны. Кроме того, этот алгоритм можно

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

поздние реализации алгоритма, использующие предварительную приоритетную

сортировку вдоль оси z и простые габаритные или минимаксные тесты,

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

В алгоритме Робертса требуется, чтобы все изображаемые тела или объекты

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

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

представляться набором пересекающихся плоскостей. Уравнение произвольной

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

ах + by + cz + d = 0 (3.1)

В матричной форме это выглядит так:

[pic]

или

[pic]

где [pic] представляет собой плоскость. Поэтому любое выпуклое твердое тело

можно выразить матрицей тела, состоящей из коэффициентов уравнений

плоскостей, т. е.

[pic]

где каждый столбец содержит коэффициенты одной плоскости.

Напомним, что любая точка пространства представима в однородных

координатах вектором

[pic]

Более того, если точка [S] лежит на плоскости, то [S]*[P]T = 0.

Если же [S] не лежит на плоскости, то знак этого скалярного произведения

показывает, по какую сторону от плоскости расположена точка. В алгоритме

Робертса предполагается, что точки, лежащие внутри тела, дают положительное

скалярное произведение.

Хотя уравнение плоскости (3.1) содержит четыре неизвестных

коэффициента, его можно нормировать так, чтобы d = 1 следовательно, трех

неколлинеарных точек достаточно для определения этих коэффициентов.

Подстановка координат трех неколлинеарных точек (x1, y1, z1), (x2, y2, z2),

(x2, y2, z2) в нормированное уравнение (3.1) дает:

ax1 + by1 + cz1 = (1

ax2 + by2 + cz2 = (1

ax3 + by3 + cz3 = (1

В матричной форме это выглядит так:

[pic]

или

[pic] (3.2)

Решение этого уравнения дает значения коэффициентов уравнения