11. Математические и алгоритмические основы компьютерной графики

Математические основы компьютерной графики. Основные алгоритмы машинной графики и их классификация. 3D-стандарты и графические библиотеки. Графические библиотеки DirectDraw и OpenGL.

Классификация алгоритмов. Алгоритмы машинной графики можно разделить на 2 уровня: нижний и верхний. Группа алгоритмов нижнего уровня предназначена для реализации графических примитивов (линий, окружностей, заполнений и т.д.). Эти алгоритмы или подобные им воспроизведены в графических библиотеках языков высокого уровня; или реализованы аппаратно в графических процессоров рабочих станций. Среди алгоритмов нижнего уровня можно выделить группы: 1) простейшие в смысле используемых математических методов и отличающиеся простотой реализации. Такие алгоритмы не являются наилучшими по объему выполняемых вычислений или требуемым ресурсам памяти; 2) сложные математические предпосылки используются и отличаются большей эффективностью; 3) могут без больших затруднений быть реализованы аппаратно (допускается распараллеливаемые, рекурсивные, реализуемые в простейших командах). Сюда входят и алгоритмы из первых двух групп; 4) алгоритм со специальным назначением (устранение лестничного эффекта). К алгоритмам верхнего уровня относятся алгоритмы удаления невидимых линий и поверхностей. Задача удаления невидимых линий и поверхностей остается центральной в компьютерной графике. От эффективности алгоритмов, позволяющих решить эту задачу, зависят качество и скорость построения 3-мерного изображения. К задаче удаления невидимых линий и поверхностей примыкает задача построения (закрашивания) полутоновых реалистичных изображений, т.е. учета явлений, связанных с количеством и характером источников света, учета свойств поверхностей тела (прозрачность, преломление, отражение света). Но вывод объектов в алгоритмах верхнего уровня обеспечивается примитивами, реализующими алгоритмы нижнего уровня. Поэтому нельзя игнорировать проблему выбора и разработки эффективных алгоритмов нижнего уровня. Для разных областей применения машинной графики на первый план могут выдвигаться разные свойства алгоритмов. Для научной графики большое значение имеет универсальность алгоритма, а быстродействие может отходить на второй план. Для систем моделирования, воспроизводящих движущиеся объекты, быстродействие становится главным критерием, т.к. требуется генерировать изображение практически в реально масштабируемом времени. Особенности растровой графики связаны с тем, что обычные изображения, с которыми сталкивается человек в своей деятельности, реализованы на плоскости, состоящей из бесконечного набора точек. А экран растрового дисплея представляется матрицей дискретных элементов, имеющих конкретные физические размеры. Поэтому нельзя провести точную линию из одной точки в другую, а можно выполнить лишь аппроксимацию этой линии с отображением ее на дискретной матрице. Эта решетка представляется квадратной сеткой с шагом 1, а отображение любого объекта на такую решетку – разложение его в растр или растровое представление. Алгоритм Брезенхема был разработан в 1965г. для цифровых графопостроителей, а затем стал использоваться для растровых дисплеев. Идея алгоритма заключается в том, что одна координата изменяется на 1, а другая не изменяется или изменяется на 1 в зависимости от расположения соответствующей точки от ближайшего узла координатной сетки. Расстояние от точки отрезка до ближайшего узла по соответствующей ортогональной координате – ошибка. Алгоритм организован так, что для вычисления второй координаты требуется лишь определить знак этой ошибки. Достоинства алгоритма: 1) выполняет оптимальную аппроксимацию отрезка, используя при этом целочисленную арифметику и минимальное количество операций сложения и вычитания; 2) алгоритм используется во всех октантах плоскости (для всех октантов линия рассматривается как набор сегментов двух типов: расположенных диагонально и расположенных вертикально или горизонтально). Заполнение сплошных областей может быть выполнено двумя способами: сканированием строк и затравочным заполнением. Метод сканирования строк решает задачи определенного порядка сканирования принадлежности точки внутренней области многоугольника или контура. При затравочном заполнении предполагается наличие некоторой точки, принадлежащей внутренней области (затравочная точка), для которой определяют ее соседние точки и включают ее в список других затравочных точек. Список этих точек анализируется с точки зрения необходимости их закрашивания. Области могут задаваться внутренне определенным и гранично определенным способом. Внутренне определенная область состоит из точек лишь одного цвета или интенсивности. Пиксели, внешние по отношению к внутренне определенной области, имеют отличные от них цвет или интенсивность. Гранично определенная область имеет контур, состоящий из пикселей с выделенным значением цвета или интенсивностью. Внутренние пиксели области отличаются от них по цвету или интенсивности, а внешние могут с ними совпадать. Удаление невидимых линий и поверхностей. Сложность данной задачи привела к появлению большого числа различных способов ее решения, различных алгоритмов, но наилучшего способа не существует. Главным недостатком всех этих алгоритмов является значительный объем вычислений, необходимый для определения удаляемых линий и поверхностей. В начале реализации любого алгоритма удаления невидимых линий и поверхностей для повышения эффективности его работы обычно проводится сортировка координат объектов синтезируемой сцены. Основная идея сортировки: чем дальше расположен объект от точки визирования, тем больше вероятность того, что он будет полностью или частично экранироваться одним из объектов, более близких к точке наблюдения. Алгоритмы удаления невидимых линий и поверхностей классифицируются по способу выбора систем координат или пространства, в которых они работают: 1) алгоритмы, работающие в объектном пространстве и имеющие дело с физической системой координат (мировые координаты), в которых они описаны; 2) алгоритмы, работающие в пространстве изображения и имеющие дело с системой координат того устройства, на котором эти объекты синтезируются. Существует большое число смешанных методов, объединяющих оба подхода. Алгоритмы первого класса используются тогда, когда требуется высокая точность изображения объектов. Синтезируемые при этом изображения можно свободно увеличивать или уменьшать во много раз, сдвигать или поворачивать. Точность в вычислении алгоритмов второго класса ограничивается разрешающей способностью экрана. Результаты, полученные в пространстве изображения, а затем увеличенные или уменьшенные во много раз, не будут соответствовать исходной сцене. Отсечение нелицевых граней. Рассмотрим задачу удаления невидимых линий для многогранника. Заметим, что если вектор нормали грани составляет с вектором, задающим направление наблюдения, тупой угол, то эта грань заведомо не может быть видна. Тупой ли угол или нет, определяется знаком скалярного произведения векторов. Когда сцена представляет собой один выпуклый многогранник, удаление нелицевых граней полностью решает проблему удаления невидимых линий (в общем случае позволяет значительно сократить количество рассматриваемых граней). Алгоритм Робертса – самый первый алгоритм, предназначенный для удаления невидимых линий. Сначала отбрасываются все ребра, обе определяющие грани которых являются нелицевыми. Дале производится проверка оставшихся ребер со всеми гранями многогранника на закрывание. Возможны случаи: 1) грань не закрывает ребро; 2) грань полностью закрывает ребро; 3) грань частично закрывает ребро (ребро разбивается при этом на несколько частей, из которых видимыми являются не более двух). Алгоритм Аппеля основан на понятии количественной невидимости точки как количества лицевых граней, ее закрывающих. Точка видима лишь тогда, когда ее количественная невидимость равна 0. Метод Z-буфера является одним из самых простых алгоритмов удаления невидимых линий и поверхностей. Это метод буфера глубины. Сопоставим каждому пикселю (x, y) картинной плоскости его расстояние вдоль направления проектирования z. Для вывода на картинную плоскость произвольной грани она переводится в свое растровое представление, и для каждого пикселя этой грани находится его глубина. Если эта глубина меньше значения глубины, хранимой в Z-буфере, то этот пиксель рисуется, и его глубина заносится в Z-буфер. Алгоритм упорядочения заключается в таком упорядочении граней, чтобы при их выводе в этом порядке получилось корректное изображение. Для этого необходимо, чтобы дальние грани выводились раньше, чем более близкие (используются методы сортировки по глубине и двоичное разбиение пространства). Метод построчного сканирования. Все изображения на картинной плоскости можно представить как ряд горизонтальных (вертикальных) линий пикселей. Рассмотрим сечение сцены плоскостью, проходящей через такую линию пикселей и центр проектирования. Пересечением этой плоскости с объектами сцены будет множество непересекающихся (за исключением концов) отрезков, которые необходимо спроектировать. Задача удаления невидимых линий для такого набора отрезков решается просто. Принципы построения полутоновых изображений. Световая энергия, падающая на поверхность от источника света, может быть поглощена, отражена или пропущена. Количество энергии зависит от длины световой волны. При этом цвет поверхности объекта определяется поглощенными длинами волн. Способы закрашивания: 1) гранение требует сравнительно небольших ресурсов ПК, т.к. предполагает лишь заполнение каждого из многоугольников одним цветом или оттенком. Этот способ примитивен, и закрашенные объекты выглядят нереалистично; 2) линейное (пропорциональное) закрашивание предполагает изменение освещенности в пределах каждого многоугольника. Благодаря этому изображения более реалистичны. Здесь яркость и цветовая насыщенность элементов каждого многоугольника плавно меняются в интервале между значениями, вычисленными для его вершин; 3) способ Гуро – яркость и цветовая насыщенность каждого многоугольника плавно меняется не только от угла к углу, но и вдоль его ребер. Осуществляется в 4 этапа: вычисление нормалей к поверхности; определение нормалей в вершинах путем усреднения нормалей по граням, которым принадлежит данная вершина; вычисление интенсивности в вершинах; закрашивание многоугольника путем линейной интерполяции значений интенсивности вдоль ребер и между ребрами. Недостаток: эффект полосы Маха – на ребрах смежных многоугольников возникает полоса разрыва непрерывности; 4) способ Фонга решает проблему полосы Маха, т.к. предполагает плавное изменение яркости и насыщенности не только вдоль ребер каждого многоугольника, но и по самой поверхности. При этом даже зеркальные блики на поверхностях выглядят правдоподобно; 5) способ трассировки лучей позволяет учесть такие эффекты, как отражение и преломление, наложение текстур. Выпустим из каждого источника света пучок лучей во все стороны и мысленно проследим (оттрассируем) дальнейшее распространение каждого из них до тех пор, пока он не попадет в глаз наблюдателя, либо не покинет сцену. При попадании луча на границу объекта выпускаем из точки попадания отраженные и преломленные лучи и отслеживаем их и все порожденные ими лучи. Это и есть процесс прямой трассировки лучей. При этом можно получить изображение сцены, но это требует огромных вычислительных затрат. Причем в полученное изображение вклад вносит лишь небольшая часть трассировочных лучей. Чтобы избежать этого, необходимо отслеживать лишь те лучи, которые попадают в глаз наблюдателя; 6) способ обратной трассировки лучей. Проследим путь луча, выходящего из глаз наблюдателя и проходящего через соответствующую точку экрана. Цвет соответствующей точки экрана будет определяться долей световой энергии, попадающей в эту точку и покидающей ее в направлении глаза. Для этого из нее выпускаются лучи в тех направлениях, из которых может придти энергия. Это может привести к определению точек пересечения соответствующих лучей с объектами сцены, выпусканию новых лучей и т.д. Существуют разные способы моделирования текстуры: проективные и процедурные (сплошные). В первом случае образец текстуры проецируется на поверхность параллельным переносом, либо цилиндрическим или сферическим проектированием. Недостатки: большой объем памяти для хранения образцов текстур, небольшая гибкость и трудность текстурирования объектов сложной формы. Второй путь не требует больших затрат памяти и работает с объектами любой формы. Но т.к. подобранная функция может зависеть от большого числа переменных, то основным недостатком является ее сложность. Для удаления погрешностей метода трассировки лучей (метод aliasing, выраженный в лестничном эффекте и пропадании точек) используется распределенная трассировка, добавляющая высокочастотный шум по методу Монте-Карло. Недостаток метода трассировки лучей: с изменением положения наблюдателя необходимо пересчитывать всю сцену. 3D-стандарты и графические библиотеки. Единого, всеобъемлющего 3D-стандарта пока не существует ни на аппаратном, ни на программном уровне. В гонке за стандартизацию принимает участие огромное количество компаний (Apple, Microsoft, Intel, AMD и т.д.). Производитель акселераторов должен добиться не только отличных аппаратных характеристик (скорости визуализации, поддержки различных 3D-функций), но и полной совместимости своего издания с основными графическими библиотеками (посредством качественных драйверов). Графические 3D библиотеки (интерфейсы программных приложений (API – Application Programming Interface)) предназначены для того, чтобы, задав некоторые общие методы обработки графики программным обеспечением, облегчить и ускорить процесс созданий приложений, которые используют 3-мерную графику: объемные объекты, свет, перспективу, деформации и т.д. Многие графические библиотеки Direct3D ориентированы на комбинированную работу как с 3D акселератором, так и с центральным процессором. Если акселератор в системе не найден или не поддерживает данную функцию, то библиотека «переложит» всю работу на центральный процессор, и 3-мерный эффект все равно будет достигнут (возможно это займет время). Из наиболее популярных графических библиотек выделяют Direct3D, OpenGL (3Dfx – фирма), Glide API, QuickTime3D (Apple). Пока лишь три API 3-мерной графики получили широкое распространение на ПК: Direct3D, Glide API, OpenGL. Все они имеют плюсы и минусы, но до сих пор каждая библиотека находится в своей нише. Direct3D и Glide API – общепризнанные интерфейсы для 3-мерных игр, OpenGL – для профессиональных программ 3-мерного моделирования и автоматизированного проектирования. В последнее время, благодаря своей мощи, простоте и доступности для изучения, в играх чаще используется OpenGL. Direct3D. Эту библиотеку, входящую в набор библиотек Microsoft DirectX, можно назвать стандартом в игровой индустрии. Как и любая другая графическая библиотека такого класса Direct3D представляет собой своеобразную прослойку между акселератором и приложением. Набор DirectX поставляется с ОС Windows, а также отдельно с видеоадаптерами и дистрибутивами приложений многих производителей аппаратного и ПО. Большинство игр используют Direct3D, но, по мнению экспертов, данная библиотека неудобна и не представляет таких богатых возможностей как OpenGL. Библиотеки Direct3D многие разработчики считают малоперспективными, что обусловлено сложностями, возникающими при программировании на этом API и низкой производительностью. В результате Direct3D приобрела репутацию широко распространённой, но довольно слабой графической библиотеки. «+»: тотальная совместимость со всеми графическими акселераторами и большим количеством 3-мерных игр. Кроме того, эта библиотека практически не требует настройки. OpenGL – очень мощная в техническом отношении, легкая в применении, хорошо отлаженная и проверенная графическая библиотека. Большое количество приложений (в основном профессиональные пакеты для создания трехмерной графики) написаны с использованием OpenGL. В отличие от Direct3D OpenGL является межплатформенным стандартом, что существенно облегчает перенос программ, использующих такой API, на другие платформы, в том числе на PC и др. OpenGL разрабатывалась в компании Silicon Graphics. Преимущества OpenGL: 1) Стабильность. Данный API является стандартом уже много лет. Различные дополнения тщательно контролировались и заранее анонсировались, чтобы разработчики могли учитывать изменения, соблюдая все требования совместимости «снизу вверх» и чтобы даже ранние OpenGL приложения не устарели. 2) Переносимость. OpenGL приложения гарантированно дают одинаковые визуальные результаты на OpenGL совместимом оборудовании независимо от ОС и графической оболочки. 3) Масштабируемость. OpenGL приложения выполняются на различных системах от PC до суперкомпьютеров. Поэтому приложения можно легко переносить на любую платформу. 4) Удобство использования. OpenGL хорошо структурирована и понятна программисту. Информация об аппаратном обеспечении содержится в драйверах, что освобождает разработчиков от необходимости выяснять специфические особенности оборудования. Кроме того, можно использовать множество уже разработанных и отлаженных OpenGL подпрограмм. В настоящее время тенденция к поддержке OpenGL на платформе PC наметилась четко. Эта графическая библиотека приобретает всё большую популярность среди производителей игрового ПО и создателей акселераторов трехмерной графики. Glide API – широко распространенная и разработанная компанией 3Dfx. Поддерживается на аппаратном уровне лишь компанией 3Dfx. Но благодаря популярности наборов VooDoo применяется в играх. По своим функциональным способностям похожа на OpenGL. Glide API не предоставляет широких возможностей межплатформенного переноса приложений. Она специально предназначена для использования в играх. Позволяет создавать реалистичные эффекты при достаточно высоком быстродействии. QuickTime. Этот пакет содержит кодеки, поддерживающие потоковое видео для Интернета, имеет функцию виртуальной реальности и поддерживает более 150 видеоэффектов. В пакет QuickTime версии 3 вошел QuickDraw3D, который позволено встраивать в 3-мерную графику, просматривать ее и управлять ею в режиме реального времени.