«В.М. Гасов, А.М. Цыганенко ТРЕХМЕРНАЯ ГРАФИКА В МЕДИАИНДУСТРИИ Учебник Допущено УМО по образованию в области полиграфии и книжного дела для студентов высших учебных заведений, обучающихся по специальностям: 230102.65 – ...»

Министерство образования и науки Российской Федерации

Московский государственный университет печати

В.М. Гасов, А.М. Цыганенко

ТРЕХМЕРНАЯ ГРАФИКА

В МЕДИАИНДУСТРИИ

Учебник

Допущено УМО по образованию в области полиграфии

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

обучающихся по специальностям:

230102.65 – Автоматизирование системы обработки информации и управления;

230200.65 – Информационные системы;

074100.65 – Информационные системы в медиаиндустрии Москва 2010 УДК 004.92 ББК 32.973-044.4 Г22 Рецензенты:

Д.И. Попов, доктор технических наук, заведующий кафедрой информатики МГУП;

В.М. Постников, кандидат технических наук, доцент МГТУ им. Н.Э. Баумана Гасов В.М.

Г22 Трехмерная графика в медиаиндустрии : учебник / В.М. Гасов, А.М. Цыганенко; Мос. гос. ун-т печати. – М. :

МГУП, 2010. – 524 с ISBN 978-5-8122-1075- В книге рассматриваются вопросы представления и обработки трехмерной графики. Освещаются различные аспекты создания, и возможностей современных анимационных структур, включенных в состав электронных изданий. Рассмотрено современное языковое и программное обеспечение средств создания и просмотра элементов трехмерной графики электронных изданий. Анализируются современные технологии создания анимационных мультимедийных компонентов электронных изданий. Представляется алгоритмическая и программная поддержка процессов обработки трехмерной графики.

УДК 004. ББК 32.973-044. © Гасов В.М., Цыганенко А.М., ISBN 978-5-8122-1075- © Московский государственный университет печати,

ВВЕДЕНИЕ

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

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

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

Глава

ВИДЫ ТРЕХМЕРНОЙ ГРАФИКИ

И СПОСОБЫ ЕЕ ОПИСАНИЯ

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

• Полигональная графика.

• Аналитическая графика.

• Фрактальная графика.

• Сплайновая графика.

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

Обычно набор точек задается в том порядке, в каком они расположены относительно внешней нормали полигона, так как в этом случае более просто решается задача удаления невидимых граней без дополнительных затрат при последующей обработке. Точка же задается традиционным способом с помощью трех координатами – x, y, z. Таким образом, трехмерный объект, состоящий из полигонов, задается как массив данных или как некоторая структура.

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

Например:

шар радиуса r с центром в точке (x0, y0, z0):

Эллипсоид с радиусами a, b, c и с центром в точке (x0, y0, z0):

Гиперболоиды с радиусами a, b, c и с центром в точке (x0, y0, z0):

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

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

Фрактальная графика. Алгоритмы фрактальной графики позволяют создавать необычайно красивые и фантастические трехмерные изображения. Ключевое понятие любого фрактала – самоподобие. Объект называют самоподобным, когда увеличенные части объекта походят на сам объект и друг на друга. Примером самоподобных объектов является береговая линия или скалистый участок местности. Зазубренный край сломанного горного камня имеет очертания, подобные очертаниям горного хребта на горизонте. Благодаря этому, возможно использование фракталов для генерирования поверхности местности, которая походит на саму себя, независимо от масштаба, в котором она отображена.

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

Присваивая определенный цвет каждому значению высоты, можно отождествить отображение высоты с цветным изображением. В этом случае обработка данных начинается с большого пустого двухмерного массива точек. Размерность должна быть (2m + 1) (2m + 1), где m – натуральное число. Значения в углах устанавливаются на одинаковое значение высоты.

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

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

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

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

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

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

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

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

• лежит в выпуклой оболочке порождающих ее точек;

• является гладкой поверхностью;

• упираясь в точки Vоо, Vоз, Vзо, Vзз, касается исходящих из них отрезков контрольного графа заданного набора.

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

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

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

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

Основным недостатком полигональных моделей является то, что при незначительном числе полигонов у фигур с плавными гранями наблюдается «угловатость». Эта угловатость усиливается, если фигура деформируется. При сильных деформациях, которые нередко используются при имитации движения «естественных» объектов, например животных, искажения могут стать неприемлемыми.

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

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

Сторона, или ребро многоугольника (стороны многоугольников образуют ребра каркасной модели полигональной фигуры) определяется двумя вершинами, следующими друг за другом. Кроме того, считается, что последняя вершина многоугольника соединена с первой, что дает замыкание контура полигона. Ребро рассматривается как отрезок прямой линии, соединяющий две указанные вершины. Чаще всего в полигональной модели ребра служат для соединения между собой двух граней.

Ребро, принадлежащее только одной грани, считается граничным. Граничные ребра могут использоваться для соединения («сшивки») между собой полигональных поверхностей (моделей), подготовленных в отдельности.

Грани. Область, ограниченная последовательными ребрами, рассматривается как грань. Любой полигональный объект в результате рассматривается как набор граней. Если этот набор замкнут (не имеет граничных ребер), то модель можно рассматривать как тело. В полигональной модели можно проводить любые операции с каждой отдельной гранью или полигоном. Если рассматривать грань только как набор ребер, то изменение порядка вершин на противоположный не влияет на форму грани.

Однако при этом изменяется еще одна важная характеристика грани – направление, в котором она ориентирована. То есть каждая грань имеет «лицевую» и «изнаночную» стороны. Для замкнутого тела лицевые стороны граней смотрят наружу, а изнаночные – внутрь, так, что они не должны быть видны. Положение лицевой стороны грани определяется вектором, который называют нормалью. Обычно нормаль — это вектор, исходящий из центра грани в направлении лицевой стороны перпендикулярно к поверхности. Нормаль полигона играет определяющую роль в процессе дальнейшей обработки полигональной модели.

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

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

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

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

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

Отдельные связанные полигональные фигуры называют оболочками. Фигура может состоять из нескольких оболочек. При этом каждое ребро может принадлежать только одной оболочке.

Удалив ряд граней, одну фигуру можно разделить на две оболочки, которые в этом случае остаются частями одной полигональной фигуры. Их можно разделить, так, что каждая из них превратится в отдельную фигуру. Некоторые команды программ обработки данных применяются не к фигурам, а именно к отдельным оболочкам.

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

Сказать то же самое о четырехугольнике или многоугольнике нельзя. Даже четырехугольник, который первоначально был плоским, может изогнуться в процессе деформации объекта и превратиться в криволинейную поверхность. Использование же кривых поверхностей полигонов (неплоских четырехугольников и т. д.) зачастую неприемлемо. Такой четырехугольник необходимо либо заранее разделить на две треугольные грани, либо принять специальные меры, исключающие появление неплоских полигонов.

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

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

Двусторонняя топология. Все полигональные фигуры должны иметь двустороннюю топологию. Это означает, например, что «жучок», который ползает по «лицевой» поверхности фигуры, может посетить любую ее точку, но не может попасть на «изнаночную» поверхность, пока не переползет через граничное ребро. Соответственно, то же самое относится и к «изнаночной» поверхности.

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

Другая некорректность состоит в наличии «висячих» вершин и ребер. К этой категории относятся как ребра и вершины, вообще не принадлежащие какой-либо грани, так и такие, которые не вписываются в нормальную структуру граней. Например, ситуация, когда ребро одной грани является составным, то есть к нему примыкают два или более ребер другой грани, недопустима.

Некорректность здесь состоит в том, что вершине соответствует внутренняя точка ребра. Фактически программа не может привязать вершину к ребру, так что связность фигуры нарушается.

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

• Три или более граней имеют общее ребро. Как уже отмечалось, граничное ребро должно принадлежать ровно одной грани, а все прочие ребра должны принадлежать ровно двум граням. Если одно ребро принадлежит большему числу граней, последовательно определить «лицевую» и «изнаночную» поверхности не представляется возможным.

• Имеется изолированная общая вершина. То есть две грани имеют общую вершину, не имея прямой связи общими ребрами через грани, также связанные с этой вершиной. Это, например, возможно, если ребра грани, примыкающие к общей вершине, граничные. Аналогичный эффект возникает, если две отдельные оболочки (например два куба) имеют только одну общую вершину.

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

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

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

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

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

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

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

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

Так, при использовании полигонов на границе силуэта объекта с внешней средой проявляется многоугольная структура объекта (граница приобретает форму ломаной линии), которая может сохраняться и в случае уменьшения размеров полигонов. В силу психологических свойств зрения, такой эффект оказывает неблагоприятное воздействие на процесс восприятия синтезированной сцены.

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

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

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

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

При выполнении операций анимации трехмерных поверхностей и синтеза объектов из полигонов может происходить изменение плоскостной структуры полигонов (кроме треугольных полигонов). В результате появляются криволинейные поверхности.

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

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

Трехмерная аналитическая графика уходит своими корнями в векторную двухмерную графику, которая больше известна как «машинная графика». В машинной графике трехмерные объекты представляются в виде трех проекций, позволяющих задавать размеры каждого элемента или детали сложных изделий, и общего вида изделия, представленного, как правило, в изометрической проекции. В связи с особой актуальностью машинной графики, для нее, в первую очередь, были разработаны международные стандарты, в частности, GKS (ядро графической системы). Эти стандарты определили рекомендуемые способы визуального представления соответствующих видов или проекций трехмерных изделий с помощью различных геометрических примитивов вывода изображения на экран «графической станции». Первоначально для описания плоских векторных изображений в качестве примитивов использовались такие геометрические элементы, как вектора, ломаные линии, дуги окружностей и эллипсов, символьная информация и более сложные двухмерные геометрические элементы. Для каждого из таких элементов был введен соответствующий набор атрибутов. Например, для линии (вектора) были использованы такие атрибуты, как координаты начала и конца линии, тип линии, ее толщина, цвет и т. д.

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

1) параболоиды с центром в точке (x0, y0, z0):

2) объекты цилиндрического вида:

На рис. 1.2 приведен пример криволинейной поверхности, описываемой соотношением вида:

y = (1/5) sin (x) cos (z) - (3/2) cos (7a/4) exp (- a), Рис. 1.2. Пример криволинейной поверхности В связи с повышением сложности визуализируемых объектов трехмерной графики, набор примитивов постоянно увеличивается.

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

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

объект, сегмент, сцена и сценарий.

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

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

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

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

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

И, наконец, в анимационной графике (и в видео) последовательность визуализируемых сцен характеризуется понятием «Сценарий», который предусматривает последовательность визуализации сцен.

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

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

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

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

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

В частности, было предложено для представления трехмерных объектов из примитивов использовать три операции алгебры логики: дизъюнкция (объединение), коньюнкция (пересечение) и отрицание, выступающее аналогом вычитания.

Обычно для описания примитивов используются аналитически определяемые поверхности, которые разделяют трехмерное пространство на два полупространства: внутреннее, или положительное, и внешнее, или отрицательное.

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

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

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

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

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

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

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

В результате полученная каркасная модель будет содержать как видимые, так и невидимые элементы объекта.

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

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

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

Таким образом, методы и алгоритмы, применяемые в процессе создания реалистичных изображений, весьма разнообразны. Но все их объединяет аналитический подход к описанию трехмерных объектов и построению алгоритмического и программного обеспечения.

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

При создании трехмерных объектов широко реализуются методы построения плоских и пространственных кривых. Кривые строятся, в основном, следующими способами:

• применением различных методов интерполяции по точкам;

• вычислением конических сечений;

• расчетом пересечения поверхностей;

• выполнением преобразования некоторой кривой;

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

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

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

В качестве уравнений кривых обычно используются соотношения, базирующиеся на функциях времени: x(t), y(t) и z(t), где параметр t можно считать изменяющимся в диапазоне от 0 до 1. Кроме того, кривые, которые необходимо представлять, могут быть неплоскими и незамкнутыми, и, зачастую, контуры объектов могут иметь вертикальные касательные.

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

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

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

В связи с широкими масштабами использования сплайнов для аппроксимации кривых и криволинейных поверхностей, был введен специальный термин: сплайновая графика.

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

Сплайны состоят из вершин (vertices) и сегментов (segments).

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

Каждая вершина сплайна имеет касательные векторы (tangents), снабженные на концах управляющими точками, или маркерами (handels). Маркеры касательных векторов управляют кривизной сегментов сплайна при входе в вершину, которой принадлежат касательные векторы, и выходе из нее. В зависимости от свойств касательных векторов различают следующие типы вершин: Угловая (Corner), Сглаженная (Smooth), Безье (Bezier) и Безье угловая (Bezier Corner).

Угловая – это вершина, примыкающие к которой сегменты не имеют кривизны.

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

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

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

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

С помощью вершин Безье-угловая можно осуществлять полный контроль над сегментами сплайна в этой точке.

Сегодня наиболее распространенными сплайнами являются следующие.

B-сплайны. По заданному набору точек V0, V1, V2, V3 элементарная кубическая B-сплайновая кривая определяется при помощи векторного параметрического уравнения вида Составная кубическая B-сплайновая кривая, задаваемая параметрическим уравнением r = r (t), 0 t (m – 2) и определяемая набором точек V0, V1,..., Vm–1, Vm, где (m 3), представляет собой объединение (m – 2) элементарных кубических B-сплайновых кривых, каждая из которых описывается уравнениями вида Построенная по данному уравнению кривая обладает важным свойством: изменение координат одной вершины в массиве или добавление новой вершины к уже имеющимся не приводит к полному изменению всей кривой, и, следовательно, не требует выполнения большого количества вычислений.

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

Рациональные кубические B-сплайны. По заданному набору V0, V1, V2, V3 рациональная кубическая B-сплайновая кривая определяется уравнением следующего вида:

Величины wi, называются весами (или параметрами формы), и представляют собой неотрицательные числа, сумма которых положительна.

В случае, если все веса равны между собой, то приведенное выше уравнение описывает элементарную кубическую B-сплайновую кривую.

Бета-сплайны. Применение составных бета-сплайновых кривых основывается на их свойстве геометрической непрерывности. Если требуется составить кривую из двух сплайновых кривых, то необходимо в точке сопряжения сплайновых кривых обеспечить совпадения их единичных касательных векторов и векторов кривизны.

Уравнение элементарной бета-сплайновой кривой, порожденной набором точек Vi-1, Vi, Vi+1, Vi+2 в матричной форме имеет вид:

Матрица M называется базисной матрицей бета-сплайновой кривой.

Численные параметры b1 и b2 называются параметрами формы бета-сплайновой кривой (параметр скоса и параметр напряжения, соответственно). Изменение значений параметров b1 и b влечет за собой изменение формы результирующей кривой (без изменения координат опорных точек).

При b1 = 1, b2 = 0 получается кубическая B-сплайновая кривая.

Наряду с рассмотренными выше сплайнами в современной компьютерной графике достаточно широко используются кривые Безье и Эрмита.

На основе рациональных кубических B-сплайнов была создана технология NURBS (Неоднородный рациональный Бисплайн), использующая сочетание разнообразных видов интерполяционных кривых. При использовании этой технологии программа сама определяет, какой тип сплайна применить в конкретной ситуации.

Для построения кривой задаются опорные точки, через которые проходит кривая, и задающие вершины, которые не лежат на кривой, а задают ее направление, выгибая кривую в свою сторону. Каждой задающей вершине присваивается «вес», показывающий, насколько сильно должна выгибаться кривая. В общем случае NURBS-поверхности представляют собой сетки, состоящие из кривых, причем каждая «ячейка» ограничивается не более, чем четырьмя кривыми. Точки пересечения кривых называются узлами.

Рис. 1.3. Пример b-сплайна (слева) и NURBS-кривой (справа) На основе сплайновых кривых создаются поперечные сечения форм создаваемых трехмерных объектов, по которым строятся соответствующие криволинейные поверхности, характеризующие внешний вид проектируемого объекта. Для придания ему реалистичности в дальнейшем используются процедуры проецирования, удаления невидимых линий и граней, производится закраска или текстурирование, рассчитываются освещенность и затенение элементов объекта и осуществляется визуализация конечного результата.

Ниже на рис. 1.4 приведены примеры общего вида сферической поверхности, созданной средствами полигональной графики и NURBS-технологий.

Рис. 1.4. Примеры полигональной (слева) и NURBS-моделей (справа) Технология NURBS считается универсальной, поскольку она позволяет строить не только модели искусственных и технических объектов, но и натуральных модели природных объектов.

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

Сегодня сплайновая графика используется во многих графических пакетах: Power Animator (фирмы Alias/Wavefront), 3D Studio MAX, Maya, Softimage3D, SolidThinking, Rhinoceros Catia, Pro/Engeneer, Solid Works, Softim ageXSI, SideFX, Houdini, Rhinoceros и др.

Очень широкое применение в большинстве растровых, векторных и трехмерных графических программных пакетах нашли инструменты для работы с кривыми или, как их иногда называют, с путями. Объясняется это тем, что во всех программных продуктах кривые (пути) создаются и редактируются по одиному принципу, так как в их основе лежит одно понятие – кривые Безье.

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

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

Произвольная ломаная линия может задаваться некоторым количеством опорных (контрольными) точек P0, P1 и P2, положение которых определено в трехмерном пространстве. По этим точкам строится дуга, которая пройдет через точки P0, P2 и будет лежать внутри треугольника P0 P1 P2. P1 будет контрольной точкой, которая служит «регулирующей» или «влияющей». Метод разбиения делит ломаную линию на два сегмента, каждый из которых определяется тремя контрольными точками. Используя эту процедуру, можно рекурсивно создавать сегменты ломаной, которая в конечном итоге будет аппроксимирована отрезками. Главная сложность рассмотренной процедуры заключается в вычислении промежуточных точек, лежащих на отрезках между контрольными точками.

Процедуру разбиения ломаной на два сегмента можно представить следующим образом:

P1(1) – середина отрезка P0 P1;

P2(1) – середина отрезка P1 P2;

P2(2) – середина отрезка P1(1) P2(1).

Определив P2(2) как точку, лежащую на дуге, мы получим два множества контрольных точек ({P0, P1(1), P2(2)} и {P2(2), P2(1), P2}), которые называют первым и вторым контрольными подмножествами соответственно (рис. 1.5).

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

Рис. 1.5. Определение точки, лежащей на кривой Повторим выполнение этой процедуры. Для этого контрольные точки {P0, P1(1), P2(2)} назовем точками P0, P1, P2 соответственно и применим вышеизложенную процедуру разбиения. Положим, что:

P1(1) – середина отрезка P0P1;

P2(1) – середина отрезка P1P2;

P2(2) – середина отрезка P1(1)P2(1).

Теперь P2(2) будет точкой, лежащей на дуге. Таким образом, как и в предыдущем разбиении, мы получим точку, через которую будет проходить дуга и два новых контрольных подмножества (рис. 1.6).

Рис. 1.6. Нахождение второй точки, лежащей на кривой Что касается точек P2(2), P2(1), P2, полученных при первом разбиении, то, назвав их P0, P1, P2 соответственно, можно снова применить процедуру разбиения и получить третью точку, лежащую на кривой.

Таким образом, после преобразований мы получим вспомогательную ломаную и три точки. Дуга, проведенная через эти точки, будет выглядеть так, как показано на рис. 1.7.

Рис. 1.7. Дуга, построенная методом разбиения Таким образом, на каждом шаге формируется точка на ломаной и два новых подмножества контрольных точек. Рассмотренный способ позволяет разделить (разбить) ломаную линию на части, каждая из которых обрабатывается отдельно.

Квадратичные кривые Безье Такую кривую можно рассмотреть как аппроксимацию разбиения и отсечения, где основной операцией является генерация средней точки на ломаной линии. Искомая кривая будет строиться по точкам, вычисленным с использованием некоторого параметра t – число от 0 до 1, (в данном примере t = 0,75).

Вычислим точку P1(1) на отрезке P0 P1 по следующей формуле:

Вычислим точку P2(1) на отрезке P1 P2 по формуле Наконец вычислим точку P2(2) на отрезке P1(1) P2(1)) по формуле Обозначим P(t) = P2(2).

Эта процедура похожа на метод разбиения и отсечения. Каждый раз при вычислении новой точки контрольные точки разбиваются на два подмножества, каждое из которых может быть использовано для генерации новой ломаной. Этот метод полностью идентичен методу разбиения и отсечения при t = 1/2.

Можно рассмотреть эту процедуру с точки зрения использования параметров. Каждая из точек P1(1), P2(1) и P2(2) зависит от параметра t, и P2(2) принимает значение, соответствующее значению параметра t. Таким образом, P(t) является функциональным представлением кривой Безье.

Алгебраически это записывается в виде соотношения Подставив эти два выражения, получим:

P(t) = P2(2)(t) = (1 – t)P1(1)(t) + tP2(1)(t) = Это квадратичный полином (или линейная комбинация квадратичных полиномов), следовательно, это параболическая кривая. Таким образом, квадратичная кривая Безье является неразложимой параболической кривой.

Квадратичная кривая Безье обладает следующими свойствами:

• P(0) = P0 и P(1) = P2, кривая проходит через контрольные точки P0 и P2;

• кривая P(t) является непрерывной и все ее производные так же непрерывны (как следует из свойств полиномов);

• продифференцируем P(t) по t и получим:

Таким образом, Так как производная – это тангенс угла наклона, то можно сделать вывод, что наклон кривой при t = 0 такой же, как и у вектора 2(P1 – P0), а наклон кривой при t = 1 такой же, как и у вектора 2(P2 – P1).

Функции (1 – t)2, 2 t(1 – t) и t2, которые соединяют точки P0, P1, P2 являются полиномами Бернштейна 2-й степени. Сами функции и их сумма неотрицательны:

Кривая лежит внутри треугольника P0 P1 P2.

P(t) является аффинной комбинацией точек P0, P1 и P2. Таким образом, P(t) будет лежать в выпуклой области контрольных точек.

В процессе вычисления P(t) контрольные точки разбиваются на два подмножества {P0, P1(1)(t), P2(2)(t)}, и {P2(2)(t), P2(1)(t), P2}, каждое из которых может быть использовано для определения другой кривой, как описано выше. Все точки, полученные методом разбиения и отсечения, лежат на этой кривой.

Понятно, что P(1/2) это первая точка, вычисленная методом разбиения и отсечения. Покажем, что P(1/4) именно та точка, которая получена методом разбиения и отсечения на контрольном множестве Q0 = P0, Q2 = P1(1)(1/2) и Q2 = P2(2)(1/2), которые были сгенерированы на первом шаге применения метода разбиения и отсечения.

Назовем эту точку Q и получим:

Подставим Qi:

Если будем вычислять P(t) при t = 1/2, получим:

Итак, P(1/4) является точкой, полученной по алгоритму разбиения и отсечения. Такие же вычисления производятся и для других точек. Каждая точка, сгенерированная методом разбиения и отсечения, соответствует дуге в отношении k/2n при любых k и n.

Таким образом, можно использовать два способа генерации точек на кривой. Первый – геометрический, при котором поиск точек производится путем выбора из последовательности точек на отрезке. Второй – аналитический, в нем кривая выражается функционально.

Геометрический метод построения Задав точки P0, P1, P2, мы можем построить кривую следующим образом:

Аналитическая форма записи Задав точки P0, P1, P2 мы можем построить кривую P(t) в соответствии с соотношением Кубические кривые Безье Кубические кривые Безье получили наиболее широкое распространение в графических пакетах. Способ построения этих кривых мало отличается от построения квадратичных кривых и основан на применении метода разбиения и отсечения.

Обычно задаются четыре контрольные точки P0, P1, P2, P3 для генерации P(t), как и в случае квадратичной кривой Безье:

Обозначим P3(3)(t) как P(t).

В целом процесс построения такой же, как и квадратичной кривой Безье: добавился лишь один уровень (рис. 1.8). Процедура, как и в квадратичном случае, вырабатывает точки на кривой и разбивает кривую на 2 новых подмножества, каждое из которых состоит из четырех точек.

Упрощая написанную выше конструкцию, получим:

= t [t P3(1)(t) + (1 – t)P2(1)(t)] + (1 – t) [t P2(1)(t) + (1 – t)P1(1)(t)] = Как и в случае квадратичной кривой, существует два метода генерации точек на кривой.

Геометрический метод Задав точки P0, P1, P2, P3, мы можем сгенерировать точку P(t) на кривой Безье.

Аналитический метод использует соотношение:

Задав контрольные точки P0, P1, P2, P3, определяем кривую Безье:

где B0,3(t) = (1 – t), B1,3(t) = 3 t (1 – t)2, B2,3(t) = 3 t2 (1 – t), B3,3(t) = t3 – полиномы Бернштейна третьей степени.

Кривые Безье произвольной степени Кривые Безье произвольной степени – это обобщенное представление квадратичных и кубических кривых Безье.

Задав множество контрольных точек {P0, P1, …, Pn}, мы можем определить кривую Безье n-й степени следующими способами.

Аналитическое определение:

Геометрическое определение:

Использование кривых Безье В компьютерной графике кривые Безье являются не только основой векторной графики, но и способом описания шрифтов, способом описания выделения и т. д. Самая главная функция кривых Безье, определившая их широкую известность, является возможность создания контуров геометрических фигур с достаточно высокой точностью. Действительно, создать правильные с точки зрения геометрии фигуры при помощи инструментов рисования даже современных графических пакетов довольно сложно. Для этого необходимо обладать определенными художественными способностями, навыками работы с графическими пакетами и иметь в наличии соответствующие аппаратные средства: профессиональные манипуляторы и планшеты. Эти условия противоречат основной концепции создания практически любой графической программы:

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

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

Кроме того, фигуры, созданные при помощи кривых Безье, можно трансформировать и масштабировать без искажений т. е.

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

До использования формул Безье контуры трехмерных компьютерных персонажей производились ломаными линиями, поверхности были гранеными, а движение – прерывистым, скачкообразным, неестественным. Если же взять четыре кривых в пространстве (16 управляющих точек), можно определить поверхность Безье, обладающую теми же полезными свойствами, что и кривая. Этим объясняется широкое использование кривых Безье в трехмерной графике. Кроме того, кривая Безье – наиболее общий и интуитивно понятный способ управления движением. Параметрам кривой можно поставить в соответствие параметры движения компьютерного персонажа, и движение будет происходить по заданным нами правилам. Этим, в частности объясняется столь широкое применение кривых Безье в двух- и трехмерной анимации.

Фракталы, как форма описания объектов двух- и трехмерной графики, становятся все более популярными не только для описания всевозможных узоров, оригинальных орнаментов, элементов трехмерных сцен и других элементов оформления, но и описания виртуальных миров. Для получения разнообразных фрактальных структур была предложена система IFS (Iterated Functions System – Система итерируемых функций), которая представляет собой систему функций из некоторого фиксированного класса функций, отображающих одно многомерное множество на другое.

Наиболее простая реализация системы IFS базируется на аффинных преобразованиях плоскости:

Для построения IFS применяют кроме аффинных и другие классы простых геометрических преобразований, которые задаются небольшим числом параметров. Например, проективные:

или квадратичные:

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

В качестве примера использования системы IFS для построения фрактальных структур, можно рассмотреть изображение «дракона Хартера – Хейтуэя» и «кривую Коха».

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

Построим IFS для двухмерного случая изображение, так называемого, «дракона Хартера – Хейтуэя». Для этого расположим первое поколение этого фрактала на сетке координат растрового дисплея с разрешением, например, 640 x 350 пикселов (рис.1.9).

Рис.1.9. Заготовка для построения IFS «дракона Хартера – Хейтуэя»

На представленном рис. 1.10 точки получившейся ломаной обозначены через A, B и C. По правилам построения у этого фрактала имеются две части, подобные целому. Это ломаные линии ADB и BEC. Зная координаты концов этих отрезков, можно вычислить коэффициенты двух аффинных преобразований, переводящих ломаную линию ABC в ломаные ADB и BEC:

Задавшись начальной стартовой точкой (например, X = 0; Y = 0), после десятой итерации на экране получим изображение фрактальной структуры (см. рис. 1.10), которая представляет собой «дракон Хартера – Хейтуэя».

Рис. 1.10. «Дракон Хартера – Хейтуэя», постpоенный с помощью системы IFS на экране с разрешением 640 x 350 пикс.

Его кодом (сжатым описанием) является набор коэффициентов двух аффинных преобразований.

Аналогично можно построить систему IFS для «кривой Коха».

Эта кривая имеет четыре части, подобные целой кривой. Для нахождения IFS вновь разместим первое поколение этого фрактала на растровом экране (сетке координат дисплея) с тем же разрешением 640 350 пикселов (рис. 1.11).

Рис. 1.11. Заготовка для построения системы IFS «кpивой Кох»

Для ее построения используется набор аффинных преобразований, состоящий из четырех преобразований:

В результате после десятой итерации можно получить изображение, представленное на рис. 1.12.

Рис. 1.12. «Кpивая Кох», постpоенная на экране с разрешением 640 350 пикс.

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

Три первых шага в построении этого фрактала представлены на рис. 1.13, а изображение самого фрактала – на рис. 1.14.

Рис. 1.13. Постpоение фрактала «Салфетка Сеpпинского»

Число треугольников все меньшего и меньшего масштаба в нем может быть бесконечно. Число черных треугольников в этом построении растет как 3n, где n — номер шага, а длина их стороны уменьшается как 2–n. Поэтому фрактальная размерность равна Можно показать, что площадь белых пятен равна площади исходного треугольника.

Рис. 1.14. Фрактал «Салфетка Сеpпинского»

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

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

Простейшим случайным фракталом является траектория частицы, совершающей броуновское движение (рис. 1.15).

Рис. 1.15. Траектория движения броуновской частицы И хотя сама траектория имеет очень сложный извилистый характер, определить ее фрактальную размерность оказывается достаточно просто. Действительно, если частица переместилась на расстояние R, то среднее число «шагов», которое она сделала определиться соотношением где l — характерная длина одного шага. Поэтому Это значит, что характерный размер диффузионной траектории на заданной площади пропорционален величине этой площади. То есть изображение траекторий движения частицы на плоскости является достаточно «густым». Следует отметить, что для двухмерного броуновского движения вероятность возвращения в любую, сколь угодно малую окрестность произвольно выбранной точки, равна 1.

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

(ее фрактальная размерность по-прежнему равна 2 и не заполняет всего предоставленного ей объема. В этом случае вероятность возврата оказывается меньше единицы.

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

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

В результате образуется некоторая пористая структура, изображенная для двухмерного случая на рис. 1.16. Большие поры внутри «экранируются» отростками достаточно большой длины.

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

В двухмерном случае фрактальная размерность такого кластера оказывается близка к значению 1,7.

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

Метод «Систем Итерируемых Функций» (Iterated Functions System – IFS) был реализован в различных программных средах, наиболее известных из которых, по мнению авторов, является программа Fractal Explorer. Ее рабочее окно представлено на рис. 1.17.

Рис. 1.17. Диалоговое окно работы с фракталами В списковом окне Inplemented представлен перечень фракталов, начиная с фрактальных кривых, двухмерных фракталов и заканчивая трехмерными фракталами, один из которых приведен на рис. 1.18.

Рис. 1.18. Пример изображения трехмерного фрактала Под списком фракталов размещена строка с формульным описанием выбранного фрактала. Фактически это поле ввода, в котором можно видоизменить или модернизировать формулу фрактала.

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

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

Для работы с цветом служит диалоговое окно, представленное на рис. 1.19.

Рис. 1.19. Диалоговое окно работы с цветом (Color control) В качестве примера изменения палитры изображения, на рис. 1.20 приведено изображение трехмерного фрактала.

Рис. 1.20. Изображение трехмерного фрактала На рис. 1.21 представлен фрактал рис. 1.18, изображение которого повернуто на некоторый угол в пространстве.

и угла расположения изображения фрактала рис. 1. Рис. 1.22. Влияние фильтрации на изображение фрактала На рис. 1.22 приведены примеры применения к фракталам функций фильтрации. Доступные фильтры диалогового окна рис. 1.17 представлены в виде свернутого списка, фрагмент которого представлен на рис. 1.23.

Рис. 1.23. Списковое окно Filter properties Таким образом, на наш взгляд, фрактальная графика обладает огромными возможностями в формировании разнообразных изображений, причем некоторые из них визуально подобны элементам окружающего мира. Фракталы хорошо и многогранно описывают всевозможные узоры, орнаменты и другие элементы оформления. Но большинство – описывают виртуальные миры, чем и объясняются широкие масштабы применения фракталов в сценах виртуальной реальности.

Система IFS может быть использована для сжатия графической информации при описании разнообразных изображений (например, фотографий), на основе выявления локального самоподобия. В случае фракталов наблюдается глобальное самоподобие.

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

ОБЩЕЕ ПРЕДСТАВЛЕНИЕ

О МОДЕЛИРОВАНИИ ТРЕХМЕРНОЙ

КОМПЬЮТЕРНОЙ ГРАФИКИ

Г оворя о моделировании трехмерной графики, имеют в виду следующие два аспекта: описание трехмерных сцен и их визуальное представление. В трехмерной графике работают с геометрическими примитивами, сегментами, объектами и сценами (кадрами), каждый из которых имеет три пространственных измерения: ширину, высоту и глубину. И именно в этих координатах описывается любой трехмерный объект или сцена. В анимационной трехмерной графике последовательность визуализации сцен определяется сценарием, т. е. появляется еще один параметр – время.

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

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

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

2.1. Трехмерное пространство Трехмерное пространство – это расширение двухмерного пространства или плоскости (X, Y) за счет введения третьей координаты (Z).

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

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

Трехмерная система координат определяется тремя осями координат: горизонтальной, вертикальной и координатой глубины, обычно называемых, соответственно осями X, Y и Z.

Объектами могут быть здания, деревья, машины, животные или любой предмет реального или виртуального мира. Координаты трехмерного пространства определяют положение в пространстве вершин или узловых точек геометрических примитивов вывода, из которых составлен объект. Соединив вершины объекта линиями, можно получить каркасную модель, называемую так из-за того, что на экране визуализируются все грани (видимые и невидимые) поверхности трехмерного тела. На рис. 2.1 приведен пример каркасной модели куба. Проведя процедуру удаления невидимых граней можно получить в результате каркасную модель трехмерного объекта, включающую лишь видимые грани или области (составляющие поверхность объекта), которые могут быть заполнены цветом, текстурами и освещаться лучами одного или нескольких источников света.

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

Визуализация – это процесс графического отображения сложных процессов (в данном случае построения) на экране компьютера в виде графических примитивов вывода соответствующего объекта. Визуализировать можно абсолютно разные процессы:

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

Компьютер оперирует не самими трехмерными объектами, а их математическими описаниями. Трехмерное приложение оперирует объектами, описанными в некоторой глобальной (мировой) системе координат (Global или World Coordinate System).

Чаще всего здесь используется ортогональная, или же декартова система координат, в которой положение каждой точки задается ее расстоянием от начала координат по трем взаимно перпендикулярным осям X, Y и Z.

При визуализации объектов трехмерной графики и сцен на экранах мониторов или плоттеров плоскость визуализации представляется плоскостью координат X и Y, а координата Z, определяющая глубину псевдотрехмерного изображения, перпендикулярна экрану и направлена в «глубь» экрана (от наблюдателя).

Фактически координата Z характеризует удаление элемента трехмерной сцены от наблюдателя или от плоскости визуализации. Эта координата имеет решающее значение при решении задачи удаления невидимых элементов, граней или объектов.

Так, объекты переднего плана могут полностью или частично загораживать объекты сцены, размещенные на большем удалении (глубине) от наблюдателя.

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

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

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

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

В приведенном выше примере (см. рис. 2.2), в качестве отсекателя может использоваться параллелограмм, для которого задаются две боковых, задняя и передняя, и две верхних грани.

В СКН математическое представление координат оказывается значительно проще, а, следовательно, проще и математические расчеты. Например, можно выбрать такую СКН, при которой Z-координата вершины сразу определяет глубину вершины в сцене (расстояние до камеры) и может без преобразований записываться в Z-буфер видеокарты. Если бы для этих целей использовалась мировая система координат, то для расчета глубины вершины, скорее всего, пришлось бы использовать все три мировые координаты X, Y, Z и рассчитывать расстояния относительно наблюдателя (видового окна или камеры).

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

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

Рис. 2.3. Использование координат в виде широты и долготы В этих координатах определяются как сами объекты, так и их взаимное расположение.

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

Существующие стереоскопические системы отображения создают эффект присутствия наблюдателя в среде изображаемых объектов. Однако и в них, тем или иным способом, для каждого глаза формируется свое двухмерное изображение, так что эту иллюзию приходится создавать дважды с двух точек наблюдения (зрения), несколько смещенных друг относительно друга.

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

Наибольший интерес для трехмерной графики представляют режимы, в которых цветом каждого пиксела непосредственно управляют двоичные коды разрядностью в 15–16 бит (High Color) или 24 бита (True Color), размещенные в соответствующих ячейках видеопамяти. Режимы с индексным определением цвета (8 бит ячейки видеопамяти выбирают цвет в соответствии с программированием палитр) для реалистичного изображения трехмерных объектов считаются недостаточными, однако они до сего времени используются в трехмерной графике Web.

Наряду с мировой системой координат используются относительные координаты (0–1) и физические координаты конкретных средств визуализации изображений. Однако они применяются в программных приложениях и для конечного пользователя, как правило, не ощутимы.

Так, работая с 3D Studio MAX пользователь имеет дело с воображаемым трехмерным пространством. В этом программном пакете трехмерное пространство – это куб в неком «кибернетическом пространстве», создаваемый в памяти компьютера. Кибернетическое пространство отличается от реального физического мира тем, что создается и существует только в памяти компьютера благодаря действию специального программного обеспечения.

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

2.2. Методы построения моделей В настоящее время существует множество программ трехмерного моделирования, каждая из которых предлагает свои комбинации инструментов и, соответственно, свои функциональные возможности. Из наиболее популярных сегодня методов моделирования можно назвать полигональное и сплайновое, хотя существует еще множество других, таких как моделирование с помощью метабол, SDS-моделирование и т. д. Наиболее популярные программы (3D Studio MAX, Maya, Lightwave) поддерживают сразу несколько таких методов, и выбор их зависит от конкретной задачи, а также от личных вкусов и предпочтений пользователя.

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

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

Так, программный комплекс 3D Studio MAX позволяет моделировать замкнутые пространства («помещения») и их содержимое с использованием разнообразных базовых примитивов, сегментов или объектов, таких как кубы, сферы, цилиндры и конусы, а также с использованием инструментов, необходимых для реализации разнообразных методов создания более сложных объектов.

После того как модели всех объектов созданы и размещены в составе сцены, можно выбрать из библиотеки соответствующего пакета трехмерной графики любые готовые материалы, такие как пластик, дерево, камень и т. д. и применить свойства этих материалов к объектам сцены. Очень часто программные пакеты предусматривают возможность создания и собственных материалов, с помощью специальных программных модулей редакторов материалов, например, Material Editor 3D Studio MAX.

После присвоения граням объектов свойств материалов или осуществив закраску, создаются виртуальные съемочные камеры, через объективы которых будет наблюдаться трехмерная сцена, и производиться съемка наполняющих ее объектов. За счет настройки параметров виртуальных камер можно получить широкоугольную панораму сцены или укрупнить план съемки, чтобы сосредоточить свое внимание на отдельных мелких деталях. Например, программный пакет 3D Studio MAX (как и другие пакеты трехмерной графики) поддерживает модели камер с набором параметров, свойственных существующим фото- или видеокамерам, с помощью которых можно наблюдать сцену именно в том виде, который требуется по замыслу сценария.

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

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

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

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

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

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

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

В основном используются три типа 3D-моделей:

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

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

Элементы моделей. При формировании 3D-модели используются:

• двухмерные элементы (точки, прямые, отрезки прямых, окружности и их дуги, различные плоские кривые и контуры);

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

• объемные элементы (параллелепипеды, призмы, пирамиды, конусы, произвольные многогранники и т. п.).

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

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

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

Как известно, растровые изображения представляются в виде битовых массивов. Такие массивы сохраняются во многих файловых форматах, например PNG, GIF, JPEG и TIFF. Файлы могут быть открыты на любом компьютере, который имеет соответствующие программы для просмотра и редактирования графики.

Растровые изображения плохо масштабируются.

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

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

Для построения моделей трехмерной графики применяются два основных способа формирования геометрических элементов моделей: построение по заданным отношениям (ограничениям) и построение с использованием преобразований.

Построение с использованием отношений. Построение с использованием отношений заключается в том, что задаются:

• элементы, подлежащие построению;

• список отношений и элементов, к которым применены отношения.

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

Известно два способа реализации построения по отношениям – общий и частный. При общем способе реализацию построения по заданным отношениям можно представить в виде двухшаговой процедуры:

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

• решается построенная система уравнений.

Очевидное достоинство такого способа – простота расширения системы. Для введения нового отношения достаточно ввести соответствующие новые уравнения.

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

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

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

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

Построение с использованием преобразований. Построение нового объекта с использованием преобразований заключается в следующем:

• задается преобразуемый объект;

• задается преобразование (это может быть обычное аффинное преобразование, определяемое матрицей, или некоторое деформирующее преобразование, например, замена одного отрезка контура ломаной);

• осуществляется выполнение преобразований.

Типы моделей. Как уже отмечалось, можно выделить два основных типа представлений 3D-моделей:

• граничное, когда в модели хранятся границы объекта, например, вершины, ребра, грани;

• в виде дерева построения, когда хранятся базовые примитивы (призма, пирамида, цилиндр, конус и т. п.), из которых формируется объект, и применяемые при этом операции; в узле дерева сохраняется операция формирования, а ветви представляют примитивы вывода.

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

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

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

В общем случае сложно отдать предпочтение одной их рассмотренных моделей, поскольку каждая из них имеет свои достоинства и недостатки. Так, например, считается, что граничная модель удобна для выполнения операций визуализации трехмерных сцен (удаление невидимых частей, закраска и т. п.).

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

модификацию объекта изменением тех или иных отдельных параметров, вплоть до исключения каких-либо ее составных частей, но неудобна для визуализации, так как требует повторной обработки информации об объекте по дереву построения. Поэтому необходимы средства взаимного преобразования моделей (рис. 2.4).

Кинематическая модель Рис. 2.4. Преобразования моделей представления Для представления поверхностей объектов используются две основных разновидности способов:

• представление в виде набора вершин, ребер и плоских многоугольников (полигональных сеток);

• представление с использованием параметрических бикубических площадок (кусков).

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

Полигональные сетки. Как отмечалось выше, полигональная сетка представляет собой набор вершин, ребер и граней в виде плоских многоугольников. Вершины соединяются ребрами. Многоугольники можно рассматривать как последовательность вершин или ребер. Для такого подхода к представлению объектов можно предложить различные способы внутреннего представления полигональных сеток, например, представленные на рис. 2.5 и 2.6.

(Pi – многоугольники, Vj – вершины, Ek – ребра) Рис. 2.6. Представление полигональной сетки Представленная на рис. 2.5 модель компактна для одного многоугольника, но избыточна для набора граней, так как не существует общего описания общих вершин и ребер.

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

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

Особенности аппаратного 3D-моделирования.

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