12.Роджерс Д., Адаме Дж. Математические основы машинной графики.
-М.:Мир, 1980.-240с. 13.Роджерс Д. Алгоритмические основы машинной графики.-М.:Мир,
1989.-512с. И.Уокер Б.С., Гурд Дж., Дроник Е.А. Интерактивная машинная
графика.-М. :Машиностроение, 1980.-168с. 15.Фоли Дж., вэн Дэм А. Основы интерактивной машинной графики.
-М.:Мир,1985.-Т.1:375 с.,Т.2:368 с. 16.Фролов А.Г., Фролов Г.В. Программирование видеоадаптеров
CGA, EGA и VGA. - М.: Диалог - МИФИ, 1992.-28S с.
17. Хирн Д., Бейкер М. Микрокомпьютерная графика.-М.:Мир, 1987.
-352с.
18. ШикинЕ.В., Боресков А.В., Зайцев А.А. Начала компьютерной
графики.-М.: Диалог-МИФИ, 1993.-138 с.
19. Эгрон Ж. Синтез изображений. Базовые алгоритмы.-М.:Радио и
связь, 1993.-216с.
20. Эйнджел И. Практическое введение в машинную графи-
ку.-М.:Радио и связь, 1984.-135 с.
21. Эндерле Г., Кэнси К., Пфафф Г. Программные средства машинной
графики. Международный стандарт GKS. - М.:Радио и связь,
1988.-479 с.
6. АЛГОРИТМЫ МАШИННОЙ ГРАФИКИ, ИСПОЛЬЗУЕМЫЕ ПРИ ВЫПОЛНЕНИИ
Алгоритмы машинной графики можно разделить на два уровня: нижний и верхний. Группа алгоритмов нижнего уровня иредназначе-
-22-
на для реализации графических примитивов. Они достаточно подробно изучаются во время лекционных занятий и реализуются студентами на практических занятиях. Эти алгоритмы или подобные им воспроизведены в графических библиотеках языков высокого уровня, реализованы аппаратно в графических процессорах и графических рабочих станциях.
Однако для конкретных случаев можно написать программу, существенно более эффективную по времени. Среди алгоритмов нижнего уровня можно выделить группу простейших в смысле используемых математических методов и отличающихся простотой реализации.
Как правило, такие алгоритмы не являются наилучшими по объему выполняемых вычислений или требуемым ресурсам памяти. Поэтому можно выделить вторую группу алгоритмов, использующих более сложные математические предпосылки и отличающихся большей эффективностью.
К третьей группе следует отнести алгоритмы, которые могут быть без больших затруднений реализованы аппаратно (допускающие распараллеливание, рекурсивные, реализуемые в простейших командах). В эту группу могут попасть и алгоритмы, представленные в первых двух группах.
Наконец, к четвертой группе можно отнести алгоритмы со специальными эффектами, например, с устранением лестничного эффекта.
К алгоритмам верхнего уровня относятся в первую очередь алгоритмы удаления невидимых линий и поверхностей. Задача удаления невидимых линий и поверхностей продолжает оставаться центральной в машинной графике. От эффективности алгоритмов,
позволяющих решить эту задачу, зависят качество и скорость построения трехмерного изображения.
Однако при этом не следует забывать, что вывод объектов обеспечивается примитивами, реализующими алгоритмы нижнего уровня, поэтому нельзя игнорировать проблему выбора и разработки эффективных алгоритмов нижнего уровня.
Для разных областей применения машинной графики на первый план могут выдвигаться разные свойства алгоритмов. Для научной графики большое значение имеет универсальность алгоритма, быстродействие может отходить на второй план. Для систем моделирования, воспроизводящих движущиеся объекты, быстродействие становится главным критерием, поскольку требуется генерировать изображение практически в реальном масштабе времени.
В данном пособии рассматривается ряд алгоритмов верхнего уровня, рассчитанных на работу с примитивами, позволяющих получить хорошие результаты при небольших затратах памяти и процессорного времени.
К задаче удаления невидимых линий и поверхностей примыкает задача построения реалистических изображений, т.е. учета явлений, связанных с количеством и характером источников света, учета свойств поверхности тела (прозрачность, преломление, отражение света).
В пособии рассматриваются алгоритмы двух последних групп, поскольку усилия студентов во время выполнения курсовой работы сосредоточиваются именно на реализации и использовании данных алгоритмов.
Сложность задачи удаления невидимых линий и поверхностей привела к появлению большого числа различных способов ее реше-
-24-
ния, различных алгоритмов, но наилучшего решения поставленной задачи не существует. Главным недостатком всех алгоритмов является значительный объем вычислений, необходимых для определения удаляемых линий и поверхностей.
Вначале реализации любого алгоритма удаления невидимых линий и поверхностей для повышения эффективности его работы обычно проводится сортировка координат объектов синтезируемой сцены. Основная идея сортировки заключается в том, что, чем дальше расположен объект от точки визирования, тем больше вероятность того, что он будет полностью или частично экранироваться одним из объектов, более близких к точке наблюдения.
Алгоритмы удаления невидимых линий и поверхностей классифицируются по способу выбора систем координат или пространства, в котором они работают. Первый класс - это алгоритмы, работающие в объектном пространстве, имеющие дело с физической системой координат (мировые координаты), в которой они описаны. Второй класс алгоритмов работает в пространстве изображения и имеет дело с системой координат того устройства, на котором эти объекты синтезируются. Алгоритмы первого класса используются в тех случаях, когда требуется высокая точность изображения объектов. Синтезируемые в этом случае изображения можно свободно увеличивать (уменьшать) во много раз, сдвигать или поворачивать. Точность вычислений алгоритмов второго класса ограничивается разрешающей способностью экрана. Результаты, полученные в пространстве изображения, а затем увеличенные (уменьшенные) во много раз, не будут соответствовать исходной сцене.
Различны и объемы вычислений для различного рода алгоритмов. Так объем вычислений для алгоритмов, работающих в объектом
пространстве, и сравнивающих каждый объект сцены со всеми остальными объектами этой сцены, растет теоретически как квадрат числа объектов. Аналогично, объем вычислений алгоритмов, работающих в пространстве изображений и сравнивающих каждый объект с позициями пикселов в экранной системе координат, растет теоретически, как произведение числа объектов на число пикселов экрана.
На практике, сравнительный анализ существующих алгоритмов удаления невидимых линий крайне затруднителен. В различных случаях при работе с различными моделями синтезируемого пространства эффективны различные алгоритмы. Даже при работе с одной и той же моделью оказывается, что в зависимости от точки наблюдения следует использовать различные алгоритмы.
6.1. АЛГОРИТМ РОБЕРТСА
Алгоритм Робертса представляет собой первый из известных алгоритмов удаления невидимых линий. Этот математически элегантный метод работает в объектном пространстве. Модификации алгоритма, использующие предварительную пространственную сортировку вдоль оси z и простые габаритные или минимаксные тесты, позволяют добиться почти линейной зависимости роста объема вычислений от роста числа объектов.
Роберте решил проблему удаления невидимых линий для объектов, составленных из 1 Овьшуклых многогранников. Любой замкнутый объект с плоскими гранями можно представить в виде набора выпуклых многогранников ( рис. ), то есть в виде наборов плоскостей, образующих грани данных многогранников. Поскольку объем вычислений в алгоритмах удаления невидимых линий и поверхностей
растет с увеличением числа многоугольников, для описания поверхностей объектов желательно использовать многоугольники с более чем тремя сторонами.
Таким образом, для реализации алгоритма необходимо вначале
представить объекты визуализации в виде наборов многогранников,
каждый из которых задан уравнениями плоскостей своих граней.
Каждая плоскость многогранника описывается уравнением:
aX + bY + cZ+d = 0, (6.1)
где X,Y и Z - мировые координаты.
В матричной форме это уравнение запишется в виде: [XYZ1][P] = 0,где
р 2= о
L -
Любой выпуклый объект можно описать матрицей объекта, состоящей из коэффицентов уравнений плоскостей:
| |al | a2 ... | an |
| = i ь | Л Ь2 | ... bnj, |
| |cl | c2 ... | cn| |
| |dl | d2 ... | , dn| |
| L- | — |
где каждый столбец содержит коэффициенты одной плоскости.
Известно, что любая точка на плоскости однозначно определя-
ется двумя координатами; точка в пространстве в однородных коор-
динатах описывается вектором [S] = [X Y Z 1]. Известно также, если точка лежит на плоскости, то скалярное произведение [S][P] равно 0; если же точка не лежит на плоскости, то знак этого скалярного произведения показывает, по какую сторону от плоскости расположена точка. В алгоритме Робертса предполагается, что точки, лежащие внутри тела дают положительное скалярное произведение.
Сформировать матрицу объекта, состоящую из коэффициентов уравнений плоскостей можно несколькими методами. Один из них использует общеизвестный из аналитической геометрии принцип, что плоскость можно определить по трем неколлинеарным точкам ( хотя уравнение плоскости содержит четыре неизвестных коэффициента, его можно нормировать так, чтобы d = 1 ). Другой метод используется, если известен вектор нормали к плоскости , то есть :
где 2 i,j,k 0 - единичные векторы осей X, Y, Z соответственно. Уравнение плоскости описывается формулой (6.1). Коэффицеш^ вычисляется с помощью произвольной точки на плоскости. Например, если эта точка с координатами (xl, yl, zl), то d = - (axl + byl + czl).
Метод, предложенный Мартином Ньюэлом, позволяет найти как точное решение для уравнений плоскостей многоугольников, так и «наилучшее» приближение для неплоских многоугольников. Этот метод эквивалентен определению нормали в каждой вершине многоугольника с помощью векторного произведения прилежащих ребер и усреднения результатов. Коэффициенты плоскости вычисляются из следующей стстемы уравнений: