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

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

На сегодняшний день создано большое количество программ, позволяющих создавать и редактировать трёхмерные сцены и объекты. Среди наиболее популярных можно назвать такие как 3D studio Max, которая позволяет трёхмерные компьютерные ролики. Область её применения в основном реклама, мультипликация и оформление телевизионных передач. Другой не менее популярный пакет программ это Auto-CAD. Он применяется в основном инженерами и проектировщиками для создания чертежей и пространственных моделей. Кроме этих существует множество других специализированных программных пакетов охватывающих практически все стороны человеческой жизни.

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

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

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

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

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

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

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

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

или н

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

где x₁, y₁ и x_2, y₂ - концы разлагаемого отрезка и y_i - начальное значение для очередного шага вдоль отрезка. Фактически уравнение (2.1.) представляет собой рекуррентное соотношение для последовательных значений y вдоль нужного отрезка. Этот метод, используемый для разложения в растр отрезков, называется цифровым дифференциальным анализатором (ЦДА). В простом ЦДА либо , либо (большее из приращений) выбирается в качестве единицы растра. Ниже приводится простой алгоритм, работающий во всех квадрантах:

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

предполагается, что концы отрезка (x₁,y₁) и (x₂,y₂) не совпадают

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

Примечание: во многих реализациях функция Integer означает взятие целой части, т.е. Integer( 8.5) = 9, а не 8. В алгоритме используется именно такая функция.

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

if abs (x₂ x₁₎ abs (y₂ y₁₎ then

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

Брезенхему. Для начала заметим, что необходимо сгенерировать только одну восьмую часть окружности. Остальные её части могут быть получены последовательными отражениями. Если сгенерирован первый октант (от 0 до 45 против часовой стрелки), то второй октант можно получить зеркальным отражением относительно прямой у = x, что дает в совокупности первый квадрант. Первый квадрант отражается относительно прямой x = 0 для получения соответствующей части окружности во втором квадранте. Верхняя полуокружность отражается относительно прямой у = 0 для завершения построения. На рис.2.3. приведены двумерные матрицы соответствующих преобразований.

Для вывода алгоритма рассмотрим первую четверть окружности с центром в начале координат. Заметим, что если работа алгоритма начинается в точке x = 0, у = R, то при генерации окружности по часовой стрелке в первом квадранте у является монотонно убывающей функцией аргумента x. Аналогично, если исходной точкой является y = 0, x = R, то при генерации окружности против часовой стрелки x будет монотонно убывающей функцией аргумента у. В нашем случае выбирается генерация по часовой стрелке с началом в точке x = 0, у = R. Предполагается, что центр окружности и начальная точка находятся точно в точках растра. Для любой заданной точки на окружности при генерации по часовой стрелке существует только три возможности выбрать следующий пиксел, наилучшим образом приближающий окружность: горизонтально вправо, по диагонали вниз и вправо, вертикально вниз. Эти направления обозначены соответственно m_H, m_D, m_V. Алгоритм выбирает пиксел, для которого минимален квадрат расстояния между одним из этих пикселов и окружностью, т. е. минимум из

m_H = | (x_i + 1)² + (y_i)² - R² |

m_H = | (x_i + 1)² + (y_i 1)² - R² |

m_H = | (x_i)² + (y_i 1)² - R² |

Вычисления можно упростить, если заметить, что в окрестности точки (x_i, y_i) возможны только пять типов пересечений окружности и сетки растра. Разность между квадратами расстояний от центра окружности до диагонального пиксела (x_i + 1, y_i 1) и от центра до точки на окружности R² равна

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

При < 0 диагональная точка (x_i + 1, y_i 1) находится внутри реальной окружности, т. е. это случаи 1 или 2 на рис.2.6. Ясно, что в этой ситуации следует выбрать либо пиксел (x_i + 1, y_i) т. е. m_H, либо пиксел (x_i + 1, y_i 1), т. е. m_D. Для этого сначала рассмотрим случай 1 и проверим разность квадратов расстояний от окружности до пикселов в горизонтальном и диагональном направлениях:

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

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

при < 0 выбираем m_H (x_i + 1, у_i)

при > 0 выбираем m_D (x_i + 1, у_i - 1)

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

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

так как диагональный пиксел (x_i + 1, у_i - 1) всегда лежит внутри окружности, а горизонтальный (x_i + 1, у_i) - вне ее. Таким образом, можно вычислить по формуле

Дополнение до полного квадрата члена (y_i)² с помощью добавления и вычитания - 2у_i + 1 дает

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

= 2(_i + y_i) - 1

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

Рассмотрим случай 2 на рис.2.6 и заметим, что здесь должен быть выбран горизонтальный пиксел (x_i + 1, у_i), так как у является монотонно убывающей функцией. Проверка компонент показывает, что

поскольку в случае 2 горизонтальный (x_i + 1, у_i) и диагональный (x_i + 1, у_i - 1) пикселы лежат внутри окружности. Следовательно, < 0, и при использовании того же самого критерия, что и в случае 1, выбирается пиксел (x_i + 1, у_i).

Если _i > 0, то диагональная точка (x_i + 1, у_i - 1) находится вне окружности, т. е. это случаи З и 4 на рис.2.6. В данной ситуации ясно, что должен быть выбран либо пиксел (x_i + 1, у_i - 1), т. е. m_D, либо (x_i, у_i - 1), т. е. m_V. Аналогично разбору предыдущего случая критерий выбора можно получить, рассматривая сначала случай З и проверяя разность между квадратами расстояний от окружности до диагонального m_D и вертикального m_V пикселов, т. е.

При ^\ < 0 расстояние от окружности до вертикального пиксела (x_i, у_i - 1) больше и следует выбрать диагональный шаг m_D, к пикселу (x_i + 1, у_i - 1). Напротив, в случае ^\ > 0 расстояние от окружности до диагонального пиксела больше и следует выбрать вертикальное движение к пикселу (x_i, у_i - 1). Таким образом,

при 0 выбираем m_D в (x_i + 1, у_i - 1)

при < 0 выбираем m_V в (x_i, у_i - 1)

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

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

поскольку для случая З диагональный пиксел (x_i + 1, у_i - 1) находится вне окружности, тогда как вертикальный пиксел (x_i, у_i - 1) лежит внутри ее. Это позволяет записать ^\ в виде

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

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

Теперь, рассматривая случай 4, снова заметим, что следует выбрать вертикальный пиксел (x_i, у_i - 1), так как y является монотонно убывающей функцией при возрастании x. проверка компонент ^\ для случая 4 показывает, что

поскольку оба пиксела находятся вне окружности. Следовательно, ^\ > 0 и при использовании критерия, разработанного для случая 3, происходит верный выбор m_V.

Осталось проверить только случай 5 на рис.2.7, который встречается, когда диагональный пиксел (x_i + 1, у_i - 1) лежит на окружности, т. е. _i = 0. Проверка компонент показывает, что

Следовательно, > 0 и выбирается диагональный пиксел (x_i + 1, у_i - 1). Аналогичным образом оцениваем компоненты ^\:

и < 0, что является условием выбора правильного диагонального шага к (х_i + 1, у_i - 1). Таким образом, случай _i = 0 подчиняется тому же критерию, что и случай _i < 0 или _i > 0.

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

_i < 0

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

> 0 выбираем пиксел (х_i + 1, у_i - 1) m_D

_i > 0

^\ 0 выбираем пиксел (х_i + 1, у_i - 1) m_D

^\ > 0 выбираем пиксел (х_i , у_i - 1) m_V

_i = 0 выбираем пиксел (х_i + 1, у_i - 1) m_D

Легко разработать простые рекуррентные соотношения дня реализации пошагового алгоритма. Сначала рассмотрим горизонтальный шаг m_H к пикселу (х_i + 1, у_i). Обозначим это новое положение пиксела как (i + 1). Тогда координаты нового пиксела и значение _i равны

Аналогично координаты нового пиксела и значения _i для шага m_D к пикселу (х_i + 1, у_i - 1) таковы:

То же самое для шага m_V к (х_i, у_i - 1)

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

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

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

x_i = 0

y_i = R

_i = 2(1 - R)

Предел = 0

Plot (x_i, y_i)

if y_i Предел 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_i + 2y_i - 1

if 0 then 10

if > 0 then 20

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

= 2_i + 2x_i - 1

if 0 then 20

if > 0 then 30

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

шаг m_H

x_i = x_i +1

_i = _i +2x_i + 1

goto 1

шаг m_D

x_i = x_i +1

y_i = y_i - 1

_i = _i +2x_i - 2y_i + 2

goto 1

шаг m_V

30y_i = y_i - 1

_i = _i - 2x_i + 1

goto 1

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

Рис. 3.1 - Необходимость удаления невидимых линий

Необходимость удаления невидимых линий, ребер, поверхностей или объемов проиллюстрирована рис. 3.1. На рис. 3.1, а приведен типичный каркасный чертеж куба. Его можно интерпретировать двояко: как вид куба сверху, слева или снизу, справа. Удаление тех линий или поверхностей, которые невидимы с соответствующей точки зрения, позволяют избавиться от неоднозначности. Результаты показаны на рис. 3.1, b и c.

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

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

Объем вычислений для любого алгоритма, работающего в объектном пространстве, и сравнивающего каждый объект сцены со всеми остальными объектами этой сцены, растет теоретически как квадрат числа объектов (n²⁾. Аналогично, объем вычислений любого алгоритма, работающего в пространстве изображения и сравнивающего каждый объект сцены с позициями всех пикселов в системе координат экрана, растет теоретически, как nN. Здесь n обозначает количество объектов (тел, плоскостей или ребер) в сцене, а N - число пикселов. Теоретически трудоемкость алгоритмов, работаюoих в объектном пространстве, меньше трудоемкости алгоритмов, работающих в пространстве изображения, при n < N. Поскольку N обычно равно (512)², то теоретически большинство алгоритмов следует реализовывать в объектном пространстве. Однако на практике это не так. Дело в том, что алгоритмы, работающие в пространстве изображения, более эффективны потому, что для них легче воспользоваться преимуществом когерентности при растровой реализации.

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

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

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

F (x, у, z) = 0

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

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

На рис. 3.2 приведен пример, где указанные параллельные плоскости определяются постоянными значениями z. Функция F (x, у, z) = 0 сводится к последовательности кривых, лежащих в каждой из этих параллельных плоскостей, например к последовательности

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

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

Рис. 3.2

Итак, поверхность теперь складывается из последовательности кривых, лежащих в каждой из этих плоскостей, как показано на рис. 3.3. Здесь предполагается, что полученные кривые являются однозначными функциями независимых переменных. Если спроецировать полученные кривые на плоскость z = 0, то сразу становится ясна идея алгоритма удаления невидимых участков исходной поверхности. Алгоритм сначала упорядочивает плоскости z = const по возрастанию расстояния до них от точки наблюдения. Затем для каждой плоскости, начиная с ближайшей к точке наблюдения, строится кривая, лежащая на ней. Алгоритм удаления невидимой линии заключается в следующем:

Рис. 3.3

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

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

Алгоритм работает очень хорошо до тех пор, пока какая-нибудь очередная кривая не окажется ниже самой первой из кривых. Как показано на рис. 3.4,а. Подобные кривые, естественно, видимы и представляют собой нижнюю сторону исходной поверхности. Однако алгоритм будет считать их невидимыми. Нижняя сторона поверхности делается видимой, если модифицировать этот алгоритм, включив в него нижний горизонт, который опускается вниз по ходу работы алгоритма. Это реализуется при помощи второго массива, длина которого равна числу различимых точек по оси x в пространстве изображения. Этот массив содержит наименьшие значения y для каждого значения x. Алгоритм теперь становится таким:

Рис. 3.4

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

Рис. 3.5

В изложенном алгоритме предполагается, что значение функции, т. е. y, известно для каждого значения x в пространстве изображения. Однако если для каждого значения x нельзя указать (вычислить) соответствующее ему значение у, то невозможно поддерживать массивы верхнего и нижнего плавающих горизонтов. В таком случае используется линейная интерполяция значений у между известными значениями для того, чтобы заполнить массивы верхнего и нижнего плавающих горизонтов, как показано на рис. 3.5. Если видимость кривой меняется, то метод с такой простой интерполяцией не даст корректного результата. Этот эффект проиллюстрирован рис. 3.6, а. Предполагая, что операция по заполнению массивов проводится после проверки видимости, получаем, что при переходе текущей кривой от видимого к невидимому состоянию (сегмент АВ на рис. 3.6,а), точка (x_n+k, y_n+k) объявляется невидимой. Тогда участок кривой между точками (x_n, y_n) и (x_n+k, y_n+k) не изображается и операция по заполнению массивов не производится. Образуется зазор между текущей и предыдущей кривыми. Если на участке текущей кривой происходит переход от невидимого состояния к видимому (сегмент CD на рис. 3.6,а), то точка (x_m+k, y_m+k) объявляется видимой, а участок кривой между точками (x_m, y_m) и (x_m+k, y_m+k) изображается и операция по заполнению массивов проводится. Поэтому изображается и невидимый кусок сегмента CD. Кроме того, массивы плавающих горизонтов не будут содержать точных значений у. А это может повлечь за собой дополнительные нежелательные эффекты для последующих кривы. Следовательно, необходимо решать задачу о поиске точек пересечения сегментов текущей и предшествующей кривых.

Рис. 3.6

Существует несколько методов получения точек пересечения кривых. На растровых дисплеях значение координаты x можно увеличивать на 1, начиная с x_n или x_m (рис. 3.6,а). Значение у, соответствующее текущему значению координаты х в пространстве изображения, получается путем добавления к значению у, соответствующему предыдущему значению координаты x, вертикального приращения y вдоль заданной кривой. Затем определяется видимость новой точки с координатами (x + 1, y + y₎. Если эта точка видима, то активируется связанный с ней пиксел. Если невидима, то пиксел не активируется, а x увеличивается на 1. Этот процесс продолжается до тех пор, пока не встретится x_n+k или x_m+k. Пересечения для растровых дисплеев определяются изложенным методом с достаточной точностью. Близкий и даже более элегантный метод определения пересечений основан на двоичном поиске.

Точное значение точки пересечения двух прямолинейных отрезков, которые интерполируют текущую и предшествующую кривые, между точками (x_n, y_n) и (x_n+k, y_n+k) (рис. 3.6) задается формулами:

где

а индексы c и p соответствуют текущей и предшествующей кривым. Полученный результат показан на рис. 3.6,b. Теперь алгоритм излагается более формально.