Введение в компьютерную графику

Лекция 1 Введение в компьютерную графику Основные направления компьютерной графики Самая важная функция компьютера – обработка информации. Особо можно выделить обработку информации, связанную с изображениями. Она разделяется на три основные направления: визуализация, обработка и распознавание изображений. Визуализация – создание изображения на основе описания (модели) некоторого объекта: Существует большое количество методов и алгоритмов визуализации, которые различаются между собой в зависимости от того, что и как должно быть отображено: график функции, диаграмма, схема, карта или имитация трехмерной реальности – изображения сцен в компьютерных развлечениях, художественных фильмах, тренажерах, в системах архитектурного проектирования. Важными и связанными между собой факторами здесь являются: скорость изменения кадров, насыщенность сцены объектами, качество изображения, учет особенностей графического устройства. Обработка изображений – это преобразование изображений, т.е. входными данными является изображение и результат – тоже изображение: Примерами обработки изображений могут служить повышение контраста, четкости, коррекция цветов, редукция цветов, сглаживание, уменьшение шумов и т.д. В качестве материала обработки могут быть космические снимки, отсканированные изображения, радиолокационные, инфракрасные изображения и т.п. Задачей обработки изображений может быть как улучшение в зависимости от определенного критерия (реставрация, восстановление), так и специальное преобразование, кардинально изменяющее изображение. В последнем случае обработка изображений может быть промежуточным этапом для дальнейшего распознавания изображения. Например, перед распознаванием часто необходимо выделять контуры, создавать бинарное изображение, разделять исходное изображение по цветам. Методы обработки изображения могут существенно различаться в зависимости от того, каким путем оно получено: синтезировано системой КГ, получено в результате оцифровки черно-белой или цветной фотографии. Основной задачей распознавания изображений является получение описания изображенных объектов. Методы и алгоритмы распознавания разрабатывались, прежде всего, для обеспечения зрения роботов и для систем специального назначения. Но в последнее время компьютерные системы распознавания изображений все чаще появляются в повседневной практике, например, офисные системы распознавания текстов или программы векторизации. Цель распознавания может формулироваться по-разному: выделение отдельных элементов (например, букв текста на изображении документа или условных знаков на изображении карты), классификация изображения в целом (например, проверка, изображен ли определенный объект, или установление персоны по отпечаткам пальцев). Методы классификации и выделения отдельных элементов могут быть взаимосвязаны. С одной стороны, классификация может быть выполнена на основе структурного анализа отдельных элементов объекта, с другой – для выделения отдельных элементов изображения можно использовать методы классификации. Задача распознавания является обратной по отношению к визуализации: Сферы применения компьютерной графики: ● САПР (системы автоматизированного проектирования); ● деловая графика (графическое представление данных); ● визуализация процессов и явлений в научных исследованиях (компьютерное графическое моделирование); ● медицина (компьютерная томография, УЗИ и т.д.); ● геодезия и картография (ГИС); ● полиграфия (схемы, плакаты, иллюстрации); ● сфера массовой информации (графика в Интернете, иллюстрации, фото); ● кинематография (спецэффекты, компьютерная мультипликация); ● быт (компьютерные игры, графические редакторы, фотоальбомы). Столь широкое распространение компьютерная графика получила с появлением интерактивных графических систем. Понятие "интерактивная компьютерная графика" (ИКГ) предполагает способность компьютерной системы создавать графику и вести диалог с человеком. В системе ИКГ пользователь воспринимает на дисплее изображение, представляющее некоторый сложный объект, и может вносить изменения в описание (модель) объекта. Такими изменениями могут быть ввод и редактирование отдельных элементов, задание числовых значений для любых параметров, различные операции по вводу информации на основе восприятия изображений человеком. В настоящее время почти любую программу можно считать системой интерактивной компьютерной графики. Исторически первыми интерактивными системами считаются системы автоматизированного проектирования (САПР), которые появились в 60-х годах XX века. Они используются во многих областях: машиностроение, электроника, проектирование самолетов и автомобилей, при разработке микроэлектронных интегральных схем, в архитектуре. Все более популярными становятся геоинформационные системы (ГИС). Они используют методы и алгоритмы многих наук и информационных технологий: последние достижения технологий баз данных, в них заложены многие алгоритмы и методы математики, физики, геодезии, топологии, картографии, навигации и, конечно же, компьютерной графики. Системы типа ГИС зачастую требуют значительных мощностей компьютера как для работы с базами данных, так и для визуализации объектов. Типичными для любой ГИС являются следующие операции: ввод и редактирование объектов с учетом их расположения на поверхности Земли; формирование разнообразных цифровых моделей и хранение их в базах данных; анализ множества объектов, расположенных на некоторой территории, с учетом пространственных, топологических отношений. Важным этапом развития систем КГ являются системы виртуальной реальности (virtual reality). Наращивание мощностей компьютера, повышение реалистичности трехмерной графики, совершенствование способов диалога с человеком позволяют создавать иллюзию вхождения человека в виртуальное пространство, которое может быть моделью существующего или выдуманного пространства. Системы класса виртуальной реальности для диалога с компьютером обычно используют такие устройства, как шлем-дисплей, сенсоры на теле человека. Широко используется КГ в кинематографии. Одним из первых примеров был фильм "Звездные войны", созданный с помощью суперкомпьютера Cray. До недавнего времени технологии компьютерной графики использовались для спецэффектов, создания изображений экзотических чудовищ, имитации стихийных бедствий и других элементов, которые являлись лишь фоном для игры живых актеров. В 2001 г. вышел на экраны полнометражный кинофильм "Финальная фантазия", в котором все, включая изображения людей, синтезировано компьютером – живые актеры только озвучили роли за кадром. Важное место занимает компьютерная графика в Интернете. В этих целях совершенствуются методы передачи визуальной информации, разрабатываются новые графические форматы. В современных компьютерных играх значительную роль играют анимация, реалистичность изображений, совершенство способов ввода-вывода информации. Следует отметить, что во многих игровых программах используются идеи и методы, разработанные для профессиональных компьютерных систем, таких как тренажеры для летчиков. Деловая графика Понятие деловой графики включает методы и средства графической интерпретации научной и деловой информации: таблицы, схемы, диаграммы, иллюстрации, чертежи. Среди программных средств КГ особое место занимают средства деловой графики. Они предназначены для создания иллюстраций при подготовке отчетной документации, статистических сводок и других иллюстративных материалов. Программные средства деловой графики включаются в состав текстовых и табличных процессоров. В среде MS Office имеются встроенные инструменты для создания деловой графики: графический редактор Paint, средство MS Graph, диаграммы MS Excel . Остановимся подробнее на типах и приемах создания диаграмм, поскольку диаграммы являются мощным средством визуализации данных. Типы и виды диаграмм. Назначение. В пакете Excel имеются следующие основные типы диаграмм. 1. Гистограмма. Отображает значения различных категорий. Виды: • обычная гистограмма; • объемный вариант обычной гистограммы; • трехмерная гистограмма. Показывает раскладку значений по категориям и рядам данных; • гистограмма с накоплением. Отображает вклад каждой категории в общую сумму; • объемный вариант гистограммы с накоплением; • гистограмма, нормированная на 100%. Отражает долю каждой категории в общей сумме; • объемный вариант нормированной гистограммы. 2. Линейчатая диаграмма. По использованию является аналогом гистограммы. Виды те же. 3. График. Отображает развитие процесса во времени или по категориям. Виды: • обычный; • график с маркерами – график, на котором помечены точки данных; • объемный вариант графика; • график с накоплением. Хорошо отображает изменение общей суммы по времени или по категориям; • график с накоплением с маркерами; • нормированный график. Отображает изменение вклада каждого значения во времени или по категориям; • нормированный график с маркерами. 4. Круговая диаграмма. Отображает один ряд данных. Виды: • обычная круговая диаграмма. Отображает вклад каждого значения (в %) в общую сумму; • разрезанная круговая диаграмма. Отображает вклад каждого значения в общую сумму, выделяя отдельные элементы; • объемный вариант обычной круговой диаграммы; • объемный вариант разрезанной круговой диаграммы; • вторичная круговая диаграмма – круговая диаграмма с частью значений, вынесенных во вторую диаграмму (для облегчения работы с маленькими секторами в основной диаграмме их можно объединить в один элемент, а затем разбить в отдельную диаграмму рядом с основной); • вторичная гистограмма – круговая диаграмма с частью значений, вынесенных в гистограмму. 5. Кольцевая диаграмма. Отображает несколько рядов данных, причем каждое кольцо соответствует одному ряду данных и показывает вклад каждого значения в общую сумму ряда. Виды те же, что и у круговой диаграммы. 6. Точечная диаграмма. Или показывает отношения между численными значениями в нескольких рядах данных, или отображает две группы чисел как один ряд координат X и Y. Эта диаграмма показывает неравные промежутки, или кластеры, данных и обычно используется для отображения результатов научных исследований. Виды: • точечная диаграмма со значениями, соединенными сглаживающими линиями (с маркерами или без них); • точечная диаграмма со значениями, соединенными отрезками (с маркерами или без них). 7. Пузырьковая диаграмма. Отображает на плоскости наборы из трех значений. Подобна точечной диаграмме, но третья величина отображается размером пузырька. 8. С областями. Хорошо отображает изменение значений ряда с течением времени. Виды: • обычная; • диаграмма с областями с накоплением. Отображает как изменение общей суммы, так и изменение вклада отдельных значений; • нормированная диаграмма с областями. Отображает изменение вклада значений с изменением времени. 9. Лепестковая диаграмма. Является аналогом графика в полярной системе координат, отображает распределение значений относительно начала координат. В лепестковой диаграмме каждой категории соответствует своя ось координат. Линиями соединяются значения, относящиеся к одному ряду. Виды: • обычная; • лепестковая диаграмма с маркерами; • заполненная лепестковая диаграмма. Отличается от обычной тем, что области, относящиеся к каждому ряду, закрашены разными цветами. 10. Биржевая диаграмма. Виды: • обычная. Отображает наборы данных из трех значений (например, самый высокий курс, самый низкий курс, курс закрытия); • биржевая диаграмма для наборов из четырех значений (курс открытия, курс закрытия, самый высокий курс, самый низкий курс); • биржевая диаграмма для наборов из четырех значений (курс закрытия, самый высокий курс, самый низкий курс, объем). Для объема используется дополнительная ось, параллельная оси Y; • биржевая диаграмма для наборов из пяти значений (курс открытия, курс закрытия, самый высокий курс, самый низкий курс, объем). 11. Поверхность. Отображает изменение значений по двум измерениям в виде поверхности. Такую диаграмму целесообразно использовать для поиска наилучшего сочетания в двух наборах данных. Виды: • обычная – области, относящиеся к одному диапазону, выделяются одинаковым цветом или узором; • проволочная (прозрачная); • контурная. Представляет собой вид сверху на поверхность диаграммы. Цвета представляют интервалы значений; 12. Коническая, цилиндрическая, пирамидальная диаграмм-мы – гистограммы или линейчатые диаграммы, в которых значения представлены не прямоугольниками, а конусами, цилиндрами или пирамидами. Существуют еще и нестандартные типы. Из них наиболее интересным и иллюстративным является совмещенная диаграмма, включающая гистограмму и график. Кроме указанных выше видов диаграмм, MS Excel предоставляет пользователю средство для иллюстрации структурированного отчета по нескольким таблицам данных, характеризующим некоторую сферу. Это так называемый отчет сводной диаграммы. Отчет сводной диаграммы – интерактивная диаграмма с данными графического анализа существующих списков, баз данных и отчетов сводных таблиц. Создав отчет сводной диаграммы, его можно просматривать на различных уровнях подробности. Для изменения структуры диаграммы можно перетаскивать мышью ее поля и элементы или выбирать в раскрывающихся списках полей элементы, которые должны отображаться на экране. Отчет сводной диаграммы следует использовать в случаях, когда требуется быстро изменять вид диаграммы и просматривать данные в различных представлениях для сравнения данных и выявления тенденций. Лекция 2 Виды компьютерной графики. Программные средства компьютерной графики Виды компьютерной графики Несмотря на то, что для работы с КГ существует множество классов программного обеспечения, выделяют всего три вида КГ: растровую, векторную и фрактальную графику. Они различаются принципами формирования изображения при отображении на экране монитора или при печати на бумаге. Растровая графика применяется при разработке электронных и полиграфических изданий. Иллюстрации, выполненные средствами растровой графики, редко создают вручную с помощью компьютерных программ. Чаще для этой цели сканируют иллюстрации, подготовленные художником на бумаге, или фотографии. В последнее время для ввода растровых изображений в компьютер нашли широкое применение цифровые фото- и видеокамеры. Соответственно, большинство графических редакторов, предназначенных для работы с растровыми иллюстрациями, ориентированы не столько на создание изображения, сколько на их обработку. В Интернете, в основном, применяются растровые иллюстрации. Программные средства для работы с векторной графикой наоборот предназначены, в первую очередь, для создания иллюстраций и в меньшей степени для их обработки. Такие средства широко используют в рекламных агентствах, дизайнерских бюро, редакциях и издательствах. Оформительские работы, основанные на применении шрифтов и простейших геометрических элементов, решаются средствами векторной графики намного проще. Существуют примеры высокохудожественных произведений, созданных средствами векторной графики, но они скорее исключение, чем правило, поскольку художественная подготовка иллюстраций средствами векторной графики чрезвычайно сложна. Программные средства для работы с фрактальной графикой предназначены для автоматической генерации изображений путем математических расчетов. Создание фрактальной художественной композиции состоит не в рисовании или оформлении, а в программировании. Фрактальную графику редко применяют для создания печатных или электронных документов, но ее часто используют в развлекательных программах. Растровая графика. Основным элементом растрового изображения является точка. Если изображение экранное, то эта точка называется пикселом. В зависимости от того, на какое графическое разрешение экрана настроена операционная система компьютера, на экране могут размещаться изображения, имеющие 640х480, 800х600, 1024х768 и более пикселов. С размером изображения непосредственно связано его разрешение. Этот параметр измеряется в точках на дюйм (dots per inch - dpi). У монитора с диагональю 15 дюймов размер изображения на экране составляет примерно 28х21 см. Зная, что в 1 дюйме 25,4 мм, можно рассчитать, что при работе монитора в режиме 800х600 пикселов разрешение экранного изображения равно 72 dpi. При печати разрешение должно быть намного выше. Полиграфическая печать полноцветного изображения требует разрешения 200-300 dpi. Стандартный фотоснимок размером 10х15 см должен содержать примерно 1000х1500 пикселов. Нетрудно также установить, что всего такое изображение будет иметь 1,5 млн точек, а если оно цветное и на кодирование каждой точки использованы три байта, то обычной цветной фотографии соответствует массив данных размером свыше 4 Мбайт. Вследствие того, что растровое изображение состоит из большого количества отдельных точек, растровая графика имеет два существенных недостатка, которые следует учитывать при выборе программного средства. Первый недостаток – большие объемы данных при работе с растровыми изображениями. Для активных работ с иллюстрациями большого размера (типа журнальной полосы) требуются компьютеры с исключительно большими объемами оперативной памяти и высокопроизводительными процессорами. Второй недостаток растровой графики – эффект пикселизации – связан с невозможностью увеличения изображения для рассмотрения деталей. Поскольку изображение состоит из точек, то увеличение приводит к тому, что точки становятся крупнее. Никаких дополнительных деталей при увеличении растрового изображения рассмотреть не удается, а увеличение точек растра визуально искажает иллюстрацию и делает ее грубой. Векторная графика. Если в растровой графике основным элементом изображения является точка, то в векторной графике – линия (при этом неважно, прямая это линия или кривая). Разумеется, в растровой графике тоже существуют линии, но там они рассматриваются как комбинации точек. Для каждой точки линии в растровой графике отводится одна или несколько ячеек памяти (чем больше цветов могут иметь точки, тем больше ячеек им выделяется). Соответственно, чем длиннее растровая линия, тем больше памяти она занимает. В векторной графике объем памяти, занимаемый линией, не зависит от размеров линии, поскольку она представляется в виде формулы, а точнее говоря, в виде нескольких параметров. Что бы мы ни делали с этой линией, изменяются только ее параметры, хранящиеся в ячейках памяти. Количество же ячеек остается неизменным для любой линии. Линия – это элементарный объект векторной графики. Все, что есть в векторной иллюстрации, состоит из линий. Простейшие объекты объединяются в более сложные (например, объект четырехугольник можно рассматривать как четыре связанные линии, а объект куб еще более сложен: его можно рассматривать либо как 12 связанных линий, либо как 6 связанных четырехугольников). Из-за такого подхода векторную графику часто называют объектно-ориентированной графикой. П р и м е р. В общем случае уравнение кривой третьего порядка можно записать в виде x3+a1y3+a2x2y+a3xy2+a4x2+a5y2+a6xy+a7x+a8y+a9=0. Видно, что для записи достаточно девяти параметров. Для задания отрезка кривой третьего порядка надо иметь на два параметра больше. Если добавить к ним параметры, выражающие такие свойства линии, как толщина, цвет, характер и прочее, то для хранения одного объекта достаточно будет 20-30 байтов оперативной памяти. Достаточно сложные композиции, насчитывающие тысячи объектов, расходуют лишь десятки и сотни Кбайт. Как и все объекты, линии имеют свойства: форма линии, ее толщина, цвет, характер (сплошная, пунктирная и т.п.). Замкнутые линии имеют свойство заполнения. Внутренняя область замкнутого контура может быть заполнена цветом, текстурой, картой. Простейшая линия, если она не замкнута, имеет две вершины, которые называются узлами. Узлы тоже имеют свойства, от которых зависит, как выглядит вершина линии и как две линии сопрягаются между собой. Заметим, что объекты векторной графики хранятся в памяти в виде набора параметров, но на экран все изображения все равно выводятся в виде точек (просто потому, что экран так устроен). Перед выводом на экран каждого объекта программа производит вычисления координат экранных точек в изображении объекта, поэтому векторную графику иногда называют вычисляемой графикой. Аналогичные вычисления производятся и при выводе объектов на принтер. Соотношение между векторной и растровой графикой. Говоря о растровой графике, мы указали на два ее существенных недостатка: значительный объем массивов данных, которые надо хранить и обрабатывать, а также невозможность масштабирования изображения без потери качества. Векторная графика лишена этих недостатков, но работа по созданию художественных иллюстраций средствами векторной графики значительно сложнее. На практике средства векторной графики используют не для создания художественных композиций, а для оформительских, чертежных и проектно-конструктор-ских работ. В векторной графике легко решаются вопросы масштабирования. Если линии задана толщина, равная 0,15 мм, то сколько бы мы ни увеличивали или ни уменьшали рисунок, эта линия все равно будет иметь только такую толщину, поскольку это одно из свойств объекта, жестко за ним закрепленное. Распечатав чертеж на малом или на большом листе бумаги, мы всегда получим линии одной и той же толщины. Это свойство векторной графики широко используется в картографии, в конструкторских САПР и в автоматизированных системах архитектурного проектирования. Фрактальная графика. Фрактальная графика, как и векторная – вычисляемая, но отличается от нее тем, что никакие объекты в памяти компьютера не хранятся. Изображение строится по уравнению (или по системе уравнений), поэтому ничего, кроме формулы, хранить не надо. Изменив коэффициенты в уравнении, можно получить совершенно другую картину. Рассмотрим пример построения фрактального изображения. Простейшим фрактальным объектом является фрактальный треугольник (рис. 1). 1. Постройте обычный равносторонний треугольник со стороной a. 2. Разделите каждую из его сторон на три отрезка. 3. На среднем отрезке стороны постройте равносторонний треугольник со стороной, равной 1/3 стороны исходного треугольника. 4. С полученными треугольниками повторите те же операции. Из рисунка видно, что треугольники последующих поколений наследуют свойства своих родительских структур. Так рождается фрактальная фигура. Процесс наследования можно продолжать до бесконечности. Фрактальными свойствами обладают многие объекты живой и неживой природы. Обычная снежинка, многократно увеличенная, оказывается фрактальным объектом. Фрактальные алгоритмы лежат в основе роста кристаллов и растений. Взгляните на ветку папоротникового растения, и вы увидите, что каждая дочерняя ветка во многом повторяет свойства ветки более высокого уровня. Способность фрактальной графики моделировать образы живой природы вычислительным путем часто используют для автоматической генерации необычных иллюстраций. Классы программ для работы с растровой графикой Средства создания изображений: ● графический редактор Paint, входящий в состав ОС Windows; ● Painter; ● Fauve Matisse. Эти программы ориентированы непосредственно на процесс рисования. В них акцент сделан на использование удобных инструментов рисования и на создание новых художественных инструментов и материалов. Средства обработки изображений: ● Adobe Photoshop; ● Corel Photo-Paint; ● Photostyler; ● Picture Publisher. Эти растровые графические редакторы предназначены не для создания изображений "с нуля", а для обработки готовых рисунков с целью улучшения их качества и реализации творческих идей. Исходный материал для обработки на компьютере может быть получен разными путями: сканирование иллюстрации, загрузка изображения, созданного в другом редакторе, ввод изображения от цифровой фото- или видеокамеры, использование фрагментов изображений из библиотек клипартов, экспортирование векторных изображений. Средства каталогизации изображений: ● ASDSee32; ● Imaging (Windows 98). Программы-каталогизаторы позволяют просматривать графические файлы множества различных форматов, создавать на жестком диске удобные альбомы, перемещать и переименовывать файлы, документировать и комментировать иллюстрации. Средства создания и обработки векторных изображений В тех случаях, когда основным требованием к изображению является высокая точность формы, применяют специальные графические редакторы, предназначенные для работы с векторной графикой. Такая задача возникает при разработке логотипов компаний, при художественном оформлении текста (например, журнальных заголовков или рекламных объявлений), а также во всех случаях, когда иллюстрация является чертежом, схемой или диаграммой, а не рисунком. Наиболее распространены следующие программы: ● Adobe Illustrator; ● Macromedia Freehand; ● CorelDraw. Особую группу программных средств, основанных на принципах векторной графики, составляют системы трехмерной графики: 3D Studio Max, Adobe Dimension, LightWave 3D, Maya, Corel Bryce. Средства создания фрактальных изображений Основным производителем программ фрактальной графики является компания Meta Creations. Наиболее известны программы, позволяющие создавать фрактальные объекты или использовать их в художественных композициях (для фона, заливок и текстур каких-либо объектов): ● Fractal Design Painter (Corel Painter); ● Fractal Design Expression; ● Fractal Design Detailer; ● Meta Creations Art Dabbler. Лекция 3 Основные понятия КГ Разрешение изображения и его размер Следует четко различать разрешение экрана, разрешение печатающего устройства и разрешение изображения. Все эти понятия относятся к разным объектам. Друг с другом эти виды разрешения никак не связаны, пока не потребуется узнать, какой физический размер будет иметь картинка на экране монитора, отпечаток на бумаге или файл на жестком диске. Разрешение экрана – свойство компьютерной видеосистемы (зависит от параметров монитора и видеокарты) и операционной системы (зависит от настроек Windows). Разрешение экрана измеряется в пикселах на дюйм (ppi - pixel per inch) и определяет размер изображения, которое может быть размещено на экране целиком. Разрешение принтера – свойство принтера, выражающее количество отдельных точек, которые могут быть напечатаны на участке единичной длины. Оно измеряется в единицах dpi (dots per inch – точки на дюйм) и определяет размер изображения при заданном качестве или, наоборот, качество изображения при заданном размере. Разрешение изображения – свойство самого изображения. Оно измеряется в точках на дюйм (dpi) и задается при создании изображения в графическом редакторе или с помощью сканера. Значение разрешения изображения хранится в файле изображения и неразрывно связано с другим свойством изображения – его физическим размером. Физический размер изображения. Может измеряться как в пикселах, так и в единицах длины (миллиметрах, сантиметрах, дюймах). Он задается при создании изображения и хранится вместе с файлом. Если изображение готовят для демонстрации на экране, то его ширину и высоту задают в пикселах, чтобы знать, какую часть экрана оно занимает. Если изображение готовят для печати, то его размер задают в единицах длины, чтобы знать, какую часть листа бумаги оно займет. Нетрудно пересчитать размер изображения из пикселов в единицы длины и наоборот, если известно разрешение изображения (см. таблицу). Связь между размером иллюстрации (в пикселах) и размером отпечатка (в мм) при разных разрешениях отпечатка Размер иллюстрации в пикселах Размер отпечатка, мм при разрешениях 75 dpi 150 dpi 300 dpi 600 dpi 640х480 212х163 108х81 55х40 28х20 800х600 271х203 136х102 68х51 34х26 1024х768 344х260 173х130 88х66 44х33 1152х864 390х292 195х146 98х73 49х37 1600х1200 542х406 271х203 136х102 68х51 Понятие растра Появление и широкое использование растра основано на свойстве человеческого зрения воспринимать изображение, состоящее из отдельных точек, как единое целое. Эту особенность зрения с давних пор использовали художники. На ней основана и технология полиграфической печати. Изображение проецируется на светочувствительную пластину через стекло, на которое равномерно нанесена непрозрачная растровая решетка. В результате непрерывное полутоновое изображение оказывается разбитым на отдельные ячейки, которые называются элементами растра. Растр получил широкое распространение при изготовлении различного рода печатной продукции: газет, журналов, книг. Понятие непрерывного полутонового изображения пришло из фотографии. На самом деле фотографический отпечаток при просмотре его через оптический прибор с очень большим увеличением тоже состоит из отдельных элементарных точек. Однако они настолько малы, что неразличимы невооруженным глазом. Другие методы представления изображений: полиграфия, распечатка на принтере, вывод на монитор – используют сравнительно большие по размеру элементы растра. Методы растрирования В полиграфии плотность заполнения элемента растра черной краской определяет восприятие данной точки на отпечатке как более светлой или темной. Таким образом, интенсивность тона регулируют изменением размера растровой точки: чем темнее точка на отпечатке, тем больше степень заполнения черной краской ячейки растра. Такой метод называют растрированием с амплитудной модуляцией. Интенсивность тона можно регулировать за счет изменения числа черных точек одинакового размера, размещаемых в растровой ячейке. Такой метод называют растрированием с частотной модуляцией. Если черные точки расположены внутри растровой ячейки случайным образом, метод называют стохастическим растрированием. Интенсивность тона (светлоту) принято подразделять на 256 уровней, т.е. для воспроизведения всего полутонового диапазона достаточно, чтобы размер растровой ячейки составил 16х16 точек. Таких ячеек, накладываемых на изображение, должно быть столько, чтобы не пропали какие-то мелкие детали изображения. Следовательно, чем больше ячеек растра содержится в каждой строке, тем более высокое качество мы получим при печати изображения. Расстояние между центрами растровых ячеек одинаково, их число на единицу длины называется линиатурой растра и измеряется в линиях на дюйм (lpi - lines per inch). Чем выше значение lpi растра, тем более четким выглядит изображение, так как мелкие детали попадают в несколько ячеек растра. Современное качественное полиграфическое оборудование может иметь линиатуру растра до 300 lpi. При печати на принтере линиатура растра составляет порядка 65-90 lpi. В полиграфической печати растровую сетку принято поворачивать на угол 45˚ (для черной краски). Это связано с особенностью человеческого глаза фиксировать линии, близкие к вертикали или горизонтали. При использовании цветной печати угол поворота может быть иным, в зависимости от количества цветов. Линиатуру растра необходимо учитывать при печати изображения на принтере. Для получения качественного изображения надо знать зависимость между линиатурой, разрешением и тоновым диапазоном. В настоящий момент для ввода изображения используются, в основном, цифровые устройства (сканеры, фото- и видеокамеры). Эти устройства характеризуются постоянным размером пятна. Следовательно, чтобы заполнить растровую ячейку, попавшую в темную область изображения, в ней размещают много пятен одинакового размера. Такие пятна называют точками. Максимальное число точек одинакового размера, которые могут поместиться в отрезке фиксированной длины (по вертикали или горизонтали) отпечатка, называют разрешающей способностью печатающего устройства. В качестве единицы измерения используется dpi. Например, разрешение принтера 600x1200 dpi (разрешение по горизонтали – 600, по вертикали – 1200). Тоновый диапазон, линиатура растра и разрешающая способность печатающего устройства связаны следующим соотношением: Основы теории цвета При работе с цветом используют понятия цветовое разрешение (его еще называют глубиной цвета) и цветовая модель. Цветовое разрешение определяет метод кодирования цветовой информации, и от него зависит то, сколько цветов на экране может отображаться одновременно. Для кодирования двухцветного (черно-белого) изображения достаточно выделить по одному биту на представление цвета каждого пиксела. Выделение одного байта позволяет закодировать 256 различных цветовых оттенков. Два байта (16 битов) позволяют определить 65536 различных цветов. Этот режим называется High Color. Если для кодирования цвета используется три байта (24 бита), возможно одновременное отображение 16,5 млн цветов. Этот режим называется True Color. Цвета в природе редко являются простыми. Большинство цветовых оттенков образуется смешением основных цветов. Способ разделения цветового оттенка на составляющие называется цветовой моделью. Существует много различных типов цветовых моделей, но в компьютерной графике, как правило, применяется не более трех. Эти модели известны под названиями RGB, CMYK и HSB. Цвет – один из факторов нашего восприятия светового излучения. Для характеристики цвета используются следующие атрибуты. Цветовой тон. Можно определить преобладающей длиной волны в спектре излучения. Цветовой тон позволяет отличить один цвет от другого, например, зеленый от красного, желтого и других. Яркость. Определяется энергией, интенсивностью светового излучения. Выражает количество воспринимаемого света. Насыщенность или чистота тона. Выражается долей присутствия белого цвета. В идеально чистом цвете примесь белого отсутствует. Если, например, к чистому красному цвету добавить в определенной пропорции белый цвет (у художников это называется разбелом), то получится светлый бледно-красный цвет. Указанные три атрибута позволяют описать все цвета и оттенки. То, что атрибутов именно три, является одним из проявлений трехмерных свойств цвета. Наука, которая изучает цвет и его измерения, называется колориметрией. Она описывает общие закономерности цветового восприятия света человеком. Одними из основных законов колориметрии являются законы смешивания цветов. Эти законы в наиболее полном виде были сформулированы в 1853 г. немецким математиком Германом Грассманом: 1. Цвет трехмерен - для его описания необходимы три компоненты. Любые четыре цвета находятся в линейной зависимости, хотя существует неограниченное число линейно независимых совокупностей из трех цветов. Иными словами, для любого заданного цвета (Ц) можно записать такое цветовое уравнение, выражающее линейную зависимость цветов: Ц = к1 Ц1 + к2 Ц2 + к3 Ц3, где Ц1, Ц2, Ц3 – некоторые базисные, линейно независимые цвета, коэффициенты к1, к2, и к3 – количество соответствующего смешиваемого цвета. Линейная независимость цветов Ц1, Ц2, Ц3 означает, что ни один из них не может быть выражен взвешенной суммой (линейной комбинацией) двух других. Первый закон можно трактовать и в более широком смысле, а именно в смысле трехмерности цвета. Необязательно для описания цвета применять смесь других цветов, можно использовать и другие величины, но их обязательно должно быть три. 2. Если в смеси трех цветовых компонентов один меняется непрерывно, в то время как два других остаются постоянными, цвет смеси также изменяется непрерывно. 3. Цвет смеси зависит только от цветов смешиваемых компонентов и не зависит от их спектральных составов. Смысл третьего закона становится более понятным, если учесть, что один и тот же цвет (в том числе и цвет смешиваемых компонентов) может быть получен различными способами. Например, смешиваемый компонент может быть получен, в свою очередь, смешиванием других компонентов. Лекция 4 Цветовые модели и палитры. Цветовые профили Аддитивная цветовая модель RGB Эта модель используется для описания цветов, которые получаются с помощью устройств, основанных на принципе излучения. В этой модели работают мониторы и бытовые телевизоры. Любой цвет считается состоящим из трех основных компонентов: красного (Red), зеленого (Green) и синего (Blue). Эти цвета называются основными. Считается также, что при наложении одного компонента на другой яркость суммарного цвета увеличивается. Совмещение трех компонентов дает нейтральный цвет (серый), который при большой яркости стремится к белому (рис. 2). Предысторией системы RGB явились опыты Томаса Юнга (три фонаря с цветными светофильтрами: красным, зеленым и синим). Некоторое время спустя Джемс Максвелл изготовил первый колориметр, с помощью которого человек мог сравнивать монохроматический цвет и цвет смешивания в заданной пропорции компонентов RGB. Регулируя яркость каждого из смешиваемых компонентов, можно добиться уравнивания цветов смеси и монохроматического излучения. Это описывается следующим образом: Ц = rR + gG + bB, где r, g, b – количество соответствующих основных цветов. Соотношение коэффициентов r, g, b Максвелл наглядно показал с помощью треугольника, впоследствии названного его именем. Треугольник Максвелла является равносторонним, в его вершинах располагаются основные цвета: R, G и B (рис. 3). Из заданной точки проводятся линии, перпендикулярные сторонам треугольникам. Длина каждой линии и показывает соответствующую величину коэффициента r, g или b. Одинаковые значения r = g = b имеют место в центре треугольника и соответствуют белому цвету. Следует также отметить, что некоторый цвет может изображаться как внутренней точкой такого треугольника, так и точкой, лежащей за его пределами. В последнем случае это соответствует отрицательному значению соответствующего цветового коэффициента. Сумма коэффициентов равна высоте треугольника, а при высоте, равной единице, r + g + b = 1. К настоящему времени система RGB является официальным стандартом. Решением Международной комиссии по освеще- нию – МКО (CIE – Commision International de l'Eclairage) – в 1931 г. были стандартизированы основные цвета, которые рекомендовано использовать в качестве R, G и B. Это монохроматические цвета светового излучения с длинами волн соответственно: R – 700 нм; G – 546,1 нм; B – 435,8 нм. Еще одним важным параметром для системы RGB является цвет, получаемый смешением трех компонентов в равных количествах. Это белый цвет. Оказывается, для того, чтобы смешиванием компонентов R, G и B получить белый цвет, яркости соответствующих источников должны быть не равны друг другу, а находиться в пропорции LR : LG : LB = 1 : 4,5907 : 0,0601. Если расчеты цвета производятся для источников излучения с одинаковой яркостью, то указанное соотношение яркостей можно учесть с соответствующими масштабными коэффициентами. Теперь рассмотрим другие аспекты. Цвет, создаваемый смешиванием трех основных компонентов, можно представить вектором в трехмерной системе координат R, G и B (рис. 4). Черному цвету соответствует центр координат – точка (0, 0, 0). Белый цвет выражается максимальным значением компонентов. Пусть это максимальное значение вдоль каждой оси равно единице. Тогда белый цвет – это вектор (1, 1, 1). Точки, лежащие на диагонали куба от черного к белому, соответствуют равным значениям: Ri = Gi = Bi. Это градации серого – их можно считать белым цветом различной яркости. Вообще говоря, если все компоненты вектора (r, g, b) умножить на одинаковый коэффициент (k = 0…1), то цвет (kr, kg, kb) сохраняется, изменяется только яркость. Поэтому для анализа цвета важно соотношение компонентов. Если в цветовом уравнении Ц = rR + gG + bB разделить коэффициенты r, g и b на их сумму: то можно записать такое цветовое уравнение: Ц = r' R + g' G + b' B. Это уравнение выражает векторы цвета (r', g', b'), лежащие в единичной плоскости r'+ g'+ b' =1. Иными словами, мы перешли от куба к треугольнику Максвелла. Заметим, что система RGB имеет неполный цветовой охват – некоторые насыщенные цвета не могут быть представлены смесью указанных трех компонентов. В первую очередь, это цвета от зеленого до синего, включая все оттенки голубого (ненасыщенные голубые цвета смешиванием компонентов RGB получить можно). Несмотря на неполный охват, система RGB широко используется в настоящее время, в первую очередь в цветных телевизорах и дисплеях компьютеров. Отсутствие некоторых оттенков не слишком заметно. Еще одним фактором, способствующим популярности системы RGB, является ее наглядность – основные цвета находятся в трех четко различимых участках видимого спектра. Кроме того, одной из гипотез, объясняющих цветовое зрение человека, является трехкомпонентная теория, которая утверждает, что в зрительной системе человека есть три типа светочувствительных элементов. Один тип реагирует на зеленый, другой – на красный, а третий – на синий цвет. Такая гипотеза высказывалась еще Ломоносовым, ее обоснованием занимались многие ученые, начиная с Т.Юнга. Впрочем, трехкомпонентная теория не является единственной теорией цветового зрения человека. Субтрактивная цветовая модель CMYK Эта цветовая модель используется для описания цвета при получении изображений на устройствах, которые реализуют принцип поглощения (вычитания) цветов. Эту модель используют для подготовки не экранных, а печатных изображений. Они отличаются тем, что их видят не в проходящем, а в отраженном свете. Чем больше краски положено на бумагу, тем больше света она поглощает и меньше отражает. Совмещение трех основных красок поглощает почти весь падающий свет, и со стороны изображение выглядит почти черным. В отличие от модели RGB увеличение количества краски приводит не к увеличению визуальной яркости, а наоборот, к ее уменьшению. Поэтому для подготовки печатных изображений используется не аддитивная (суммирующая) модель, а субтрактивная (вычитающая). Цветовыми компонентами этой модели являются не основные цвета, а те, которые получаются в результате вычитания основных цветов из белого: Голубой (Cyan) = Белый - Красный = Зеленый + Синий Пурпурный (Magenta) = Белый - Зеленый = Красный + Синий Желтый (Yellow) = Белый - Синий = Красный + Зеленый Эти три цвета называются дополнительными, потому что дополняют основные цвета до белого. Существенную трудность в полиграфии представляет черный цвет. Теоретически его можно получить совмещением трех основных или дополнительных красок, но на практике результат оказывается неудовлетворительным. Поэтому в цветовую модель CMYK добавлен четвертый компонент - черный. Ему эта система обязана буквой K в названии (blacK). Цветоделение. В типографиях цветные изображения печатают в несколько приемов. Накладывая на бумагу по очереди голубой, пурпурный, желтый и черный отпечатки, получают полноцветную иллюстрацию. Поэтому готовое изображение, полученное на компьютере, перед печатью разделяют на четыре составляющих одноцветных изображения. Этот процесс называется цветоделением. Современные графические редакторы имеют средства для выполнения этой операции. Преобразование между моделями RGB и CMYK Графические редакторы позволяют работать с цветным изображением в разных цветовых моделях, но все-таки модель RGB для компьютера "ближе". Это связано с методом кодирования цвета байтами. Поэтому создавать и обрабатывать цветные изображения принято в модели RGB, а при выполнении цветоделения рисунок преобразовывают в модель CMYK. При печати рисунка RGB на цветном четырехцветном принтере драйвер принтера также преобразует рисунок в цветовую модель CMYK. Соотношение для перекодирования цвета из модели CMY в RGB: и обратно - из модели RGB в CMY: Здесь считается, что компоненты кодируются числами в диапазоне от 0 до 1. Цветовая модель HSV Рассмотренные выше цветовые модели так или иначе используют смешение некоторых основных цветов. Теперь рассмотрим цветовую модель, которую можно отнести к иному, альтернативному типу. В модели HSV (рис. 5) цвет описывается следующими параметрами: цветовой тон H (Hue), насыщенность S (Saturation), яркость, светлота V(Value). Значение H измеряется в градусах от 0 до 360, поскольку здесь цвета радуги располагаются по кругу в таком порядке: красный, оранжевый, желтый, зеленый, голубой, синий, фиолетовый. Значения S и V находятся в диапазоне (0…1). Приведем примеры кодирования цветов для модели HSV. При S=0 (т.е. на оси V) - серые тона. Значение V=0 соответствует черному цвету. Белый цвет кодируется как S=0, V=1. Цвета, расположенные по кругу напротив друг друга, т.е. отличающиеся по H на 180 º, являются дополнительными. Задание цвета с помощью параметров HSV достаточно часто используется в графических системах, причем обычно показывается развертка конуса. Цветовая модель HSV удобна для применения в тех графических редакторах, которые ориентированы не на обработку готовых изображений, а на их создание своими руками. Существуют такие программы, которые позволяют имитировать различные инструменты художника (кисти, перья, фломастеры, карандаши), материалы красок (акварель, гуашь, масло, тушь, уголь, пастель) и материалы полотна (холст, картон, рисовая бумага и пр.). Создавая собственное художественное произведение, удобно работать в модели HSV, а по окончании работы его можно преобразовать в модель RGB или CMYK, в зависимости от того, будет ли оно использоваться как экранная или печатная иллюстрация. Существуют и другие цветовые модели, построенные аналогично HSV, например модели HLS (Hue, Lighting, Saturation) и HSB также использует цветовой конус. В модели HSB тоже три компонента: оттенок цвета (Hue), насыщенность цвета (Saturation) и яркость цвета (Brightness). Регулируя их, можно получить столь же много произвольных цветов, как и при работе с другими моделями. Другие цветовые модели Для решения проблемы отрицательных коэффициентов, характерной для модели RGB, в 1931 г. Международной комиссией по освещению (CIE) была принята колориметрическая система XYZ, в которой за основные были приняты также три цвета, однако они являются условными, нереальными. Цветовая модель CIE L*a*b*. Все вышеперечисленные модели описывают цвет тремя параметрами и в достаточно широком диапазоне. Теперь рассмотрим цветовую модель, в которой цвет задается одним числом, но уже для ограниченного диапазона цветов (оттенков). На практике часто используются черно-белые (серые) полутоновые изображения. Серые цвета в модели RGB описываются одинаковыми значениями компонентов, т.е. ri = gi = bi . Таким образом, для серых изображений нет необходимости использовать тройки чисел - достаточно и одного числа. Это позволяет упростить цветовую модель. Каждая градация определяется яркостью Y. Значение Y=0 соответствует черному цвету, максимальное значение Y – белому. Для преобразования цветных изображений, представленных в системе RGB, в градации серого используют соотношение Y = 0,299R + 0,587G + 0,114B, где коэффициенты при R, G и B учитывают различную чувствительность зрения к соответствующим цветам и, кроме того, их сумма равна единице. Очевидно, что обратное преобразование R =Y, G =Y, B =Y не даст никаких других цветов, кроме градаций серого. Еще один пример использования различных цветовых моделей. При записи цветных фотографий в графический файл формата JPEG используется сжатия объемов информации растрового изображения преобразование из модели RGB в модель (Y, Cb, Cr). При чтении файлов JPEG выполняется обратное преобразование в RGB. Разнообразие моделей обусловлено различными областями их использования. Каждая из цветовых моделей была разработана для эффективного выполнения отдельных операций: ввода изображений, визуализаций на экране, печати на бумаге, обработки изображений, сохранения в файлах, колориметрических расчетов и измерений. Преобразование из одной модели в другую может привести к искажению цветов изображения. Цветовые профили Изложенные выше теории восприятия и воспроизведения цвета на практике используются с серьезными поправками. Образованный в 1993 г. Международный консорциум по цвету (ICC) разработал и стандартизировал системы управления цветом (Color Management System, CMS). Такие системы призваны обеспечить постоянство цвета на всех этапах работы для любых устройств, учитывая особенности конкретных устройств при воспроизведении цвета. В реальности не существует устройств с цветовым охватом, полностью совпадающим с моделями RGB, CMYK, CIE и любыми другими. Поэтому для приведения возможностей устройств к некоторому общему знаменателю были разработаны цветовые профили. Цветовой профиль – средство описания параметров цветовоспроизведения. В компьютерной графике всякая работа начинается в пространстве RGB, поскольку монитор физически излучает эти цвета. По инициативе компаний Microsoft и Hewlett Packard была принята стандартная модель sRGB, соответствующая цвето- вому охвату монитора среднего качества. В таком цветовом пространстве должна без проблем воспроизводиться графика на большинстве компьютеров. Но эта модель весьма упрощенная, и ее цветовой охват существенно уже, чем у качественных мониторов. В настоящее время практически повсеместным стандартом стали цветовые профили, создаваемые в соответствии с требованиями ICC. Основное содержание такого профиля составляют таблицы (матрицы) соответствия цветов при различных преобразованиях. Самый заурядный профиль монитора должен содержать как минимум матрицы для преобразования CIE – RGB и таблицу для обратного преобразования, параметры белого цвета и градационную характеристику (параметр Gamma). Главная особенность ICC-профиля печатающего устройства - необходимость учета взаимовлияния цветов. Если на мониторе точки люминофора излучают практически независимо, то при печати краски накладываются на бумагу и друг на друга. Поэтому профили печатающих устройств содержат огромные матрицы для пересчета взаимных преобразований пространств XYZ и Lab, математические модели различных вариантов таких преобразований. Лекция 5 Кодирование цвета. Палитра Кодирование цвета Для того чтобы компьютер имел возможность работать с цветными изображениями, необходимо представлять цвета в виде чисел - кодировать цвет. Способ кодирования зависит от цветовой модели и формата числовых данных в компьютере. Для модели RGB каждая из компонент может представляться числами, ограниченными некоторым диапазоном, например дробными числами от нуля до единицы либо целыми числами от нуля до некоторого максимального значения. Наиболее распространенной схемой представления цветов для видеоустройств является так называемое RGB-представление, в котором любой цвет представляется как сумма трех основных цветов – красного, зеленого, синего – с заданными интенсивностями. Все возможное пространство цветов представляет собой единичный куб, и каждый цвет определяется тройкой чисел (r, g, b) – (red, green, blue). Например, желтый цвет задается как (1, 1, 0), а малиновый – как (1, 0, 1), белому цвету соответствует набор (1, 1, 1), а черному – (0, 0, 0). Обычно под хранение каждого из компонентов цвета отводится фиксированное число n бит памяти. Поэтому считается, что допустимый диапазон значений для компонент цвета не [0; 1], а [0; 2n-1]. Практически любой видеоадаптер способен отобразить значительно большее количество цветов, чем то, которое определяется размером видеопамяти, отводимой под один пиксел. Для использования этой возможности вводится понятие палитры. Палитра – массив, в котором каждому возможному значению пиксела ставится в соответствие значение цвета (r, g, b). Размер палитры и ее организация зависят от типа используемого видеоадаптера. Наиболее простой является организация палитры на EGA-адаптере. Под каждый из 16 возможных логических цветов (значений пиксела) отводится 6 бит, по 2 бита на каждый цветовой компонент. При этом цвет в палитре задается байтом вида 00rgbRGB, где r,g,b,R,G,B могут принимать значение 0 или 1. Таким образом, для каждого из 16 логических цветов можно задать любой из 64 возможных физических цветов. 16-цветная стандартная палитра для видеорежимов EGA, VGA. Реализация палитры для 16-цветных режимов адаптеров VGA намного сложнее. Помимо поддержки палитры адаптера EGA, видеоадаптер дополнительно содержит 256 специальных DAC-регистров, где для каждого цвета хранится его 18-битовое представление (по 6 бит на каждый компонент). При этом с исходным логическим номером цвета с использованием 6-битовых регистров палитры EGA сопоставляется, как и раньше, значение от 0 до 63, но оно уже является не RGB-разложением цвета, а номером DAC-регистра, содержащего физический цвет. 256-цветная для VGA. Для 256-VGA значение пиксела непосредственно используется для индексации массива DAC-регистров. В настоящее время достаточно распространенным является формат True Color, в котором каждый компонент представлен в виде байта, что дает 256 градаций яркости для каждого компонента: R=0…255, G=0…255, B=0…255. Количество цветов составляет 256х256х256=16.7 млн (224). Такой способ кодирования можно назвать компонентным. В компьютере коды изображений True Color представляются в виде троек байтов, либо упаковываются в длинное целое (четырехбайтное) - 32 бита (так, например, сделано в API Windows): C = 00000000 bbbbbbbb gggggggg rrrrrrrr. Индексные палитры При работе с изображениями в системах компьютерной графики часто приходится искать компромисс между качеством изображения (требуется как можно больше цветов) и ресурсами, необходимыми для хранения и воспроизведения изображения, исчисляемыми, например, объемом памяти (надо уменьшать количество байтов на пиксел). Кроме того, некоторое изображение само по себе может использовать ограниченное количество цветов. Например, для черчения может быть достаточно двух цветов, для человеческого лица важны оттенки розового, желтого, пурпурного, красного, зеленого, а для неба – оттенки голубого и серого. В этих случаях использование полноцветного кодирования цвета является избыточным. При ограничении количества цветов используют палитру, предоставляющую набор цветов, важных для данного изображения. Палитру можно воспринимать как таблицу цветов. Палитра устанавливает взаимосвязь между кодом цвета и его компонентами в выбранной цветовой модели. Компьютерные видеосистемы обычно предоставляют возможность программисту установить собственную цветовую палитру. Каждый цветовой оттенок представляется одним числом, причем это число выражает не цвет пиксела, а индекс цвета (его номер). Сам же цвет разыскивается по этому номеру в сопроводительной цветовой палитре, приложенной к файлу. Такие цветовые палитры называют индексными палитрами. Индексная палитра – это таблица данных, в которой хранится информация о том, каким кодом закодирован тот или иной цвет. Эта таблица создается и хранится вместе с графическим файлом. Разные изображения могут иметь разные цветовые палитры. Например, в одном изображении зеленый цвет может кодироваться индексом 64, а в другом этот индекс может быть отдан розовому цвету. Если воспроизвести изображение с "чужой" цветовой палитрой, то зеленая елка на экране может оказаться розовой. Фиксированная палитра В тех случаях, когда цвет изображения закодирован двумя байтами (режим High Color), на экране возможно изображение 65 тысяч цветов. Разумеется, это не все возможные цвета, а лишь одна 256-я доля общего непрерывного спектра красок, доступных в режиме True Color. В таком изображении каждый двухбайтный код тоже выражает какой-то цвет из общего спектра. Но в данном случае нельзя приложить к файлу индексную палитру, в которой было бы записано, какой код какому цвету соответствует, поскольку в этой таблице было бы 65 тыс. записей и ее размер составил бы сотни тысяч байтов. Вряд ли есть смысл прикладывать к файлу таблицу, которая может быть по размеру больше самого файла. В этом случае используют понятие фиксированной палитры. Ее не надо прилагать к файлу, поскольку в любом графическом файле, имеющем 16-разрядное кодирование цвета, один и тот же код всегда выражает один и тот же цвет. Безопасная палитра Термин безопасная палитра используют в Web-графике. Поскольку скорость передачи данных в Интернете пока оставляет желать лучшего, для оформления Web-страниц не применяют графику, имеющую кодирование цвета выше 8-разрядного. При этом возникает проблема, связанная с тем, что создатель Web-страницы не имеет ни малейшего понятия о том, на какой модели компьютера и под управлением каких программ будет просматриваться его произведение. Он не уверен, не превратится ли его "зеленая елка" в красную или оранжевую на экранах пользователей. В связи с этим было принято следующее решение. Все наиболее популярные программы для просмотра Web-страниц (броузеры) заранее настроены на некоторую одну фиксированную палитру. Если разработчик Web-страницы при создании иллюстраций будет применять только эту палитру, то он может быть уверен, что пользователи всего мира увидят рисунок правильно. В этой палитре не 256 цветов, как можно было бы предположить, а лишь 216. Это связано с тем, что не все компьютеры, подключенные к Интернету способны воспроизводить 256 цветов. Такая палитра, жестко определяющая индексы для кодирования 216 цветов, называется безопасной палитрой. Лекция 6 Визуализация изображений. Основные понятия Наиболее известны два способа визуализации: растровый и векторный. Первый используется в таких графических устройствах, как дисплей, телевизор, принтер, второй – в векторных дисплеях, плоттерах. Оптимально, если способ описания графического изображения соответствует способу визуализации. В противном случае требуется конвертация: при выводе растрового изображения на векторном устройстве используется векторизация; при выводе векторного изображения на растровом устройстве – растеризация (растрирование). Растровая визуализация основывается на представлении изображения на экране или бумаге в виде совокупности отдельных точек или пикселов. Вместе все эти пикселы образуют растр. Векторная визуализация основывается на формировании изображения на экране или бумаге путем рисования линий (или векторов). Совокупность типов линий (графических примитивов), которые используются как базовые для векторной визуализации, зависит от определенного устройства. Типичная последовательность действий для плоттера или векторного дисплея такова: переместить перо в начальную точку (для дисплея - отклонить пучок электронов); переместить перо в конечную точку; поднять перо (уменьшить яркость луча). Качество векторной визуализации для векторных устройств обуславливается точностью вывода и набором базовых графических примитивов - линий, дуг, кругов, эллипсов и других. В настоящее время наиболее распространен растровый способ визуализации, что связано с преобладанием растровых дисплеев и принтеров. Главный недостаток растровых устройств – дискретность изображения. Недостатки векторных устройств – проблемы при сплошном заполнении фигур, меньшее по сравнению с растровыми устройствами количество цветов, меньшая скорость визуализации. Растр – это матрица ячеек (пикселов). Каждый пиксел может иметь свой цвет. Совокупность пикселов различного цвета образует изображение. В зависимости от расположения пикселов в пространстве различают квадратный, прямоугольный, гексагональный или иные типы растра. Для описания расположения пикселов используют различные системы координат. Общим для всех таких систем является то, что координаты пикселов образуют дискретный ряд значений (необязательно целые числа). В компьютерных графических системах наиболее широкое распространение получила система целых координат – номеров пикселов с (0, 0) в левом верхнем углу. Основные геометрические характеристики растра Разрешающая способность растра характеризует расстояние между соседними пикселами. Измеряется разрешающая способность растра количеством пикселов на единицу длины, обычно используется единица измерения ppi (pixel per inch) – количество пикселов в дюйме (1 дюйм ≈ 2,54 см). Размер растра определяется количеством пикселов по горизонтали и вертикали. Для компьютерных графических систем наиболее удобным является растр с одинаковым размером по горизонтали и вертикали: ppiX = ppiY. В противном случае возникают проблемы при выводе изображений. Например, если растр прямоугольный (как в устаревших мониторах EGA), окружность на экране может выглядеть как эллипс. Форма пикселов растра определяется особенностями устройства графического вывода и может быть прямоугольной, квадратной (дисплей) или круглой (принтеры). Количество цветов (глубина цвета) – одна из важнейших характеристик растра. По количеству цветов различают следующие виды изображений: ● двухцветные (бинарные) – 1 бит на пиксел (чаще всего это черно-белые изображения); ● полутоновые. Используют градации серого или какого-то другого цвета, например 256 градаций – 1 байт на пиксел; ● цветные изображения. Используют от 2 бит на пиксел и выше. Глубина цвета 16 бит на пиксел (65 536 цветов) соответствует палитре High Color; 24 бит на пиксел (16б7 млн цветов) – True Color. В современных компьютерных графических системах используется и большая глубина цвета – 32, 48 и более бит на пиксел. Методы улучшения растровых изображений: антиэлайзинг и дизеринг Как уже отмечалось выше, основным недостатком растровой визуализации является эффект пикселизации. Рассмотрим некоторые из существующих методов, позволяющих визуально улучшать качество растровых изображений. При одних и тех же значениях технических параметров устройства графического вывода может быть создана иллюзия увеличения разрешающей способности или количества цветов. Однако следует иметь в виду, что улучшение одной характеристики может происходить за счет ухудшения другой. Антиэлайзинг. В растровых системах при невысокой разрешающей способности (меньше 300 dpi) существует проблема ступенчатого эффекта (aliasing). Этот эффект особенно заметен на изображении наклонных линий – при большом шаге сетки растра пикселы образуют как бы ступени лестницы. Рассмотрим это на примере отрезка прямой линии. Растровое изображение объекта определяется алгоритмом закрашивания пикселов, соответствующих площади изображаемого объекта. Различные алгоритмы могут дать разные варианты растрового изображения одного и того же объекта. Можно сформулировать условие корректного закрашивания следующим образом: если в контур изображаемого объекта попадает больше половины площади ячейки растра, то соответствующий пиксел закрашивается цветом объекта (С), иначе пиксел сохраняет цвет фона (Сф). Устранение ступенчатого эффекта называется по-английски antialiasing. Для того чтобы растровое изображение линии выглядело более гладким, можно цвет угловых пикселов "ступенек лестницы" заменить на некоторый оттенок, промежуточный между цветом объекта и цветом фона. Вычислим цвет пропорционально части площади ячейки растра, покрываемой идеальным контуром объекта. Если площадь всей ячейки обозначить как S, а часть площади, покрываемой контуром, – Sx, то искомый цвет равен: Методы сглаживания растровых изображений можно разделить на две группы: ● алгоритмы генерации сглаженных изображений отдельных простейших объектов (линий, фигур); ● методы обработки уже существующего изображения. Для сглаживания растровых изображений часто используют алгоритмы цифровой фильтрации. Один из таких алгоритмов - локальная фильтрация. Она осуществляется путем взвешенного суммирования яркости пикселов, расположенных в некоторой окрестности текущего обрабатываемого пиксела. Можно представить себе, что в ходе обработки по растру скользит прямоугольное окно, которое выхватывает пикселы, используемые для вычисления цвета некоторого текущего пиксела. Если окрестность симметрична, то текущий пиксел находится в центре окна. Базовая операция такого фильтра может быть представлена в виде следующей зависимости: где P – значение цвета текущего пиксела; F – новое значение цвета пиксела; K –- нормирующий коэффициент; M – двумерный массив коэффициентов, который определяет свойства фильтра (такой массив называется маской). Размеры окна фильтра: по горизонтали jmax - jmin + 1, по вертикали imax - imin + 1. На практике наиболее часто используется фильтр с окном 3х3, который получается при imin, jmin = -1 и imax, jmax = +1. При обработке всего растра указанные вычисления производятся для каждого пиксела. Если в ходе обработки новые значения цвета пикселов записываются в исходный растр и вовлекаются в вычисления для очередных пикселов, то такую фильтрацию называют рекурсивной. При нерекурсивной фильтрации в вычисления вовлекаются только прежние значения цвета пикселов. При сглаживании цветных изображений можно использовать модель RGB и производить фильтрацию по каждой компоненте. Локальная цифровая фильтрация применяется не только для сглаживания контуров, но и в процессе других видов обработки изображений: повышения резкости, выделения контуров и др. Дизеринг. Современные растровые дисплеи позволяют достаточно качественно отображать миллионы цветов, но для растровых печатающих устройств дело обстоит иначе. Устройства печати обычно имеют высокую разрешающую способность, зачастую на порядок выше, чем дисплеи, но в то же время не позволяют воссоздать даже сотню градаций серого, не говоря уже о миллионах цветов. Оттенки цветов (для цветных изображений) или полутоновые градации (для черно-белых) имитируются комбинированием, смесью точек. Чем качественнее полиграфическое оборудование, тем меньше отдельные точки и расстояние между ними. Для устройств печати на бумаге особенно важна проблема качества красок. В полиграфии для получения цветных изображений обычно используют три цветных краски и одну черную, что в смеси дает восемь цветов (включая черную краску и белый цвет бумаги). Иногда встречаются системы с шестью и восемью базовыми цветами, однако такая технология печати намного сложнее. Если графическое устройство не способно воссоздавать достаточное количество цветов, тогда используют растрирование - независимо от того, растровое это устройство или не растровое. Эти способы основываются на свойстве человеческого зрения - пространственной интеграции. Если достаточно близко расположить маленькие точки различных цветов, то они будут восприниматься как одна точка с некоторым усредненным цветом. Если на плоскости густо расположить много маленьких разноцветных точек, то будет создана визуальная иллюзия закрашивания плоскости некоторым усредненным цветом. Эти методы часто используются в графических системах. Они позволяют увеличить количество оттенков цвета за счет снижения пространственного разрешения растрового изображения. Такие методы получили название дизеринг (от англ. dithering – дрожание, разрежение). Простейшим вариантом дизеринга можно считать создание оттенка цвета парами соседних пикселов. Если в ячейке размерами n x n пикселов использованы два цвета, то с помощью такой ячейки можно получить n2+1 различных цветовых градаций. Возможны две предельные комбинации: все пикселы ячейки имеют цвет C1 – вся ячейка имеет, соответственно, цвет C1, все пикселы ячейки имеют цвет C2 – вся ячейка имеет цвет C2. Все иные комбинации дают цвета, промежуточные между C1 и C2. Таким образом получается растр с разрешающей способностью в n раз меньшей, чем у исходного растра, а глубина цвета возрастает пропорционально n2. Для характеристики изображений, получаемых методом дизеринга, используется термин линиатура растра. Линиатура вычисляется как количество линий (ячеек) на единицу длины и измеряется обычно в единицах lpi (lines per inch). Один из способов создания достаточно качественных изображений – диффузный дизеринг (diffused dithering). Он заключается в том, что ячейки создаются случайно (или псевдослучайно), поэтому даже для фрагмента растра пикселов с постоянным цветом не образуются регулярные структуры и изображение не выглядит созданным из ячеек. Лекция 7 Геометрическое моделирование. Системы координат. Аффинные преобразования Основные понятия геометрического моделирования Моделирование – один из основных методов познания, который заключается в выделении из сложного явления (объекта) некоторых частей и замещении их другими объектами, более понятными и удобными для описания, объяснения и разработки. Модель – реальный физический объект или процесс, теоретическое построение, упорядоченный набор данных, которые отражают некоторые элементы или свойства изучаемого объекта или явления, существенные с точки зрения моделирования. Математическая модель – модель объекта, процесса или явления, представляющая собой математические закономерности, с помощью которых описаны основные характеристики моделируемого объекта, процесса или явления. Геометрическое моделирование – раздел математического моделирования – позволяет решать разнообразные задачи в двумерном, трехмерном и, в общем случае, в многомерном пространстве. Геометрическая модель включает в себя системы уравнений и алгоритмы их реализации. Математической основой построения модели являются уравнения, описывающие форму и движение объектов. Все многообразие геометрических объектов является комбинацией различных примитивов – простейших фигур, которые в свою очередь состоят из графических элементов - точек, линий и поверхностей. В настоящее время геометрическое моделирование успешно используется в управлении и других областях человеческой деятельности. Можно выделить две основные области применения геометрического моделирования: проектирование и научные исследования. Геометрическое моделирование может использоваться при анализе числовых данных. В таких случаях исходным числовым данным ставится в соответствие некоторая геометрическая интерпретация, которая затем анализируется, а результаты анализа истолковываются в понятиях исходных данных. Этапы геометрического моделирования: ● постановка геометрической задачи, соответствующая исходной прикладной задаче или ее части; ● разработка геометрического алгоритма решения поставленной задачи; ● реализация алгоритма при помощи инструментальных средств; ● анализ и интерпретация полученных результатов. Методы геометрического моделирования: ● аналитический; ● графический; ● графический, с использованием средств машинной графики; ● графоаналитические методы. Графоаналитические методы основываются на разделах вычислительной геометрии, таких как теория R-функций, теория поверхностей Кунса, теория кривых Безье, теория сплайнов и др. Для современных научных исследований характерно использование, наряду с двумерными и трехмерными, многомерных геометрических моделей (физика элементарных частиц, ядерная физика и т.д.). Системы координат Система координат (СК) – совокупность базисных (линейно независимых) векторов и единиц измерения расстояния вдоль этих векторов (e1, e2, …, en). Если базисные вектора нормированы (единичной длины) и взаимно ортогональны, то такая СК называется декартовой (ДСК). Мировая система координат (МСК) – xyz – содержит точку отсчета (начало координат) и линейно независимый базис, благодаря которым становится возможным цифровое описание геометрических свойств любого графического объекта в абсолютных единицах. Экранная система координат (ЭСК) – xэyэzэ. В ней задается положение проекций геометрических объектов на экране дисплея. Проекция точки в ЭСК имеет координату zэ = 0. Тем не менее, не следует отбрасывать эту координату, поскольку МСК и ЭСК часто выбираются совпадающими, а, вектор проекции [xэ, yэ, 0] может участвовать в преобразованиях, где нужны не две, а три координаты. Система координат сцены (СКС) – xсyсzс –  описывает положение всех объектов сцены - некоторой части мирового пространства с собственным началом отсчета и базисом, которые используются для описания положения объектов независимо от МСК. Объектная система координат (ОСК) – xоyоzо – связана с конкретным объектом и совершает с ним все движения в СКС или МСК. Правая ДСК – оси ориентированы так, что вращение ортов происходит в положительном направлении (против часовой стрелки с точки зрения наблюдателя, находящегося на конце третьего свободного орта): Левая ДСК – оси ориентированы так, что вращение ортов происходит в отрицательном направлении. В двумерном пространстве (R2) наиболее распространены декартова СК (x, y) и полярная СК (r, φ) (r – радиус-вектор точки, φ – угол поворота). Соотношение между ДСК и ПСК: В трехмерном пространстве (R3): ● ортогональная декартова СК (x, y, z); ● цилиндрическая СК (ρ, y, φ); ● сферическая СК (r, φ, ω). Соотношение между декартовой СК и цилиндрической СК: Соотношение между декартовой СК и сферической СК: Соотношение между цилиндрической СК и сферической СК: Аффинные преобразования Аффинным называется преобразование, обладающее следующими свойствами: ● любое аффинное преобразование может быть представлено как последовательность операций из числа простейших: сдвиг, растяжение/сжатие, поворот; ● сохраняются прямые линии, параллельность прямых, отношение длин отрезков, лежащих на одной прямой, и отношение площадей фигур. Аффинные преобразования координат на плоскости: (x, y) – двумерная система координат, (X, Y) – координаты старой СК в новой системе координат. Общий вид аффинного преобразования: A, B, C, D, E, F – константы. Обратное преобразование также является аффинным: Простейшие аффинные преобразования системы координат. 1. Параллельный сдвиг координат: Обратное преобразование: 2. Растяжение/сжатие осей: Обратное преобразование: Коэффициенты могут быть отрицательными. Например, при kx = -1 получаем зеркальное отображение относительно оси y. 3. Поворот системы координат (x,y) на угол α: Обратное преобразование – поворот системы (X,Y) на угол (-α): Аффинные преобразования объектов на плоскости. x, y – старые координаты точки, X, Y – новые координаты точки. 1. Сдвиг: Обратное преобразование: 2. Масштабирование объекта: Обратное преобразование: 3. Поворот вокруг центра координат: Обратное преобразование: Лекция 8 Геометрические модели плоских объектов Основные понятия Положение точки в пространстве Rn (n-мерном пространстве) задается радиус-вектором p=[p1, p2, …, pn], имеющим n координат p1, p2, …, pn и разложение по n линейно-независимым базисным векторам e1, e2, …, en : . Таким образом положение точки на плоскости определяется радиус-вектором точки p=[px, py]= pxex +pyey или p=[r, φ] в полярной системе координат. Расстояние между двумя точками p1 и p2 равно: Линия на плоскости может быть задана с помощью уравнения в неявной форме: (НФ) f(x,y)=0; или в параметрической форме: (ПФ) p(t)=[x(t), y(t)]. В любой регулярной (гладкой и некратной) точке на линии p0=[x0, y0]=p(t0) возможна линеаризация кривой, т.е. проведение к ней касательной прямой, уравнения которой имеют вид (НФ) Nx(x - x0) + Ny(y - y0) = 0 или N ◦ (p - p0) = 0, (ПФ) x(t) = x0 + Vx t, y(t)= y0 + Vy t или p(t) = p0 + Vt. Вектор нормали N=[Nx, Ny] ортогонален линии и направлен в ту сторону, где f(p)> 0. Направляющий вектор линии V=[Vx, Vy] начинается в точке p0 и направлен по касательной к p(t) в сторону увеличения t. Векторы N и V ортогональны, т.е. N ◦ V = 0 или NxVx + NyVy = 0. Связь вектора нормали и направляющего вектора: N=[Vy, - Vx], V=[-Ny, Nx] Способы описания (модели) прямой линии Неявное уравнение прямой задается тремя коэффициентами A, B и D, составляющими вектор F=[A, B, D]: (НФ): Ax+By+D=0. Хотя бы одно из чисел A или B должно быть ненулевым. Если оба коэффициента ненулевые (A≠0 и B≠0), то прямая проходит наклонно к осям координат и пересекается с ними в точках (-D/A, 0) и (0, -D/B). При A=0, B≠0 уравнение By+D=0 описывает горизонтальную прямую y= –D/B . При A≠0, B=0 уравнение Ax+D=0 описывает вертикальную прямую x= –D/A. Прямая проходит через начало координат: f(0,0)=0 при D=0. Благодаря свойству прямой разделять плоскость на две полуплоскости с противоположными знаками, неявное уравнение позволяет определять положение точки (точек) на плоскости относительно прямой: 1) точка q лежит на прямой, если f(q)=0; 2) точки a и b лежат по одну сторону от прямой, если f(a)∙f(b)>0; 3) точки a и b лежат по разные стороны от прямой, если f(a)∙f(b)<0. Для построения прямой по неявному уравнению необходимо и достаточно иметь либо две несовпадающие точки p0 и p1, через которые она проходит, либо точку p0 и направляющий вектор V, с помощью которого вторая точка p1 вычисляется как p1=p0+V. Из неявного уравнения прямой N=[A, B]  V=[-B, A]. Нормальное уравнение прямой – прямая описывается с помощью точки p0 и вектора нормали N и выводится из условия ортогональности векторов N и (p-p0) для всех точек p, принадлежащих прямой f(p)=N◦(p-p0). Неявная функция позволяет оценить положение точки p относительно вектора нормали прямой: ● при f(a)>0 точка a лежит в том же полупространстве, куда направлена нормаль, а угол (a-p0, N) острый; ● при f(b)<0 угол (b-p0, N) тупой, а точка b и нормаль находятся по разные стороны от прямой. Параметрическая функция прямой p(t)=p0+Vt, где V=[-Ny, Nx] удобна для задания и построения частей прямой – отрезков и лучей. Для этого необходимо указать пределы изменения параметра t: ● бесконечный интервал -0 точка a лежит справа от точки p0, так что угол (a-p0, V) положительный; ● при f(b)<0 угол (b-p0, V) отрицательный, а точка b лежит слева от точки p0. Неявная форма уравнения прямой, проходящей через две точки a=[ax, ay] и b=[bx,by], выводится из условия принадлежности прямой этих точек и точки p=[x,y]. Выбрав направление движения по прямой от точки a к точке b, получим направляющий вектор V=b-a и параметрическую модель линии: (ПФ): x(t)=ax+(bx-ax)t, y(t)= ay+(by-ay)t или p(t)=a+(b-a)t. Условие существования прямой очевидное: V≠0, т.е. a≠b. При изменении параметра t от 0 до 1 движение точки происходит внутри отрезка ab от точки a до точки b. Взаимное расположение графических элементов на плоскости 1. Три точки p1, p2, p3 коллинеарны, т.е. лежат на одной прямой, если 2. Точка p лежит на отрезке ab при нулевом угле между векторами p-a и b-p: (p - a) ◦ (b - p)= |p - a|·|b - p| , . Взаимное расположение прямых. 1. Две прямые совпадают, если F1 × F2 =03 (векторное произведение равно нулевому вектору). 2. Две прямые параллельны, если 3. Две прямые ортогональны, если N1◦ N2=0 или V1◦ V2=0. Взаимное расположение точки и прямой 1. Уравнение перпендикуляра, опущенного из точки q=[qx, qy] на прямую, выглядит следующим образом: (НФ): Ny(x-qx)-Nx(y-qy)=0, (ПФ): p┴(t)=q+Nt или p┴(t)=q+V┴t , где V┴=[Vy, -Vx]=N. 2. Расстояние от точки q до прямой равно: 3. Зеркальное отражение точки q относительно прямой лежит на перпендикуляре к прямой на расстоянии 2d от q в сторону, противоположную проекции вектора q-p0 на нормаль N: Пересечение двух прямых. Пусть имеются две прямые, заданные уравнениями в НФ: A1x+B1y+D1=0 и A2x+B2y+D2=0, тогда координаты точки пересечения вычисляются следующим образом: Возможны следующие три случая: 1. A1B2-A2B1≠0, т.е. A1/A2≠B1/B2 – прямые не параллельны, точка пересечения единственная и ее координаты вычисляются по вышеприведенным формулам. 2. A1B2-A2B1=0, D1B2-D2B1≠0 или A1D2-A2D1≠0 – прямые параллельны и точек пересечения нет. 3. A1B2-A2B1=0, D1B2-D2B1=0 и A1D2-A2D1=0, т.е. прямые совпадают во всех точках. Угол между двумя пересекающимися прямыми находится как угол между векторами нормали или направляющими векторами (N1, N2) = (V1, V2). Уравнения пучка прямых и биссектрисы угла Уравнение пучка прямых, заключенных между двумя, прямыми определяется следующим образом: (НФ) (ПФ) Изменение параметра пучка в интервале 0≤λ≤1 дает такие промежуточные прямые, что вращение происходит по кратчайшим углам. Уравнение биссектрисы угла между двумя прямыми получается при λ=0,5, если |N1|=|N2| или |V1|=|V2|. В результате параметры биссектрисы можно найти по формулам Fбис=|N2|F1+|N1|F2, pбис(t)=q+Vбисt, Vбис=|V2|V1+|V1|V2. Расчет биссектрис бывает необходим, например, при построении окружности, вписанной в треугольник. Как известно, ее центр лежит в точке пересечения биссектрис внутренних углов этого треугольника. При построении биссектрисы внутреннего угла следует учитывать направления подставляемых в формулу векторов сторон треугольника: они должны либо оба выходить из вершины, либо оба входить в нее. При несоблюдении этого правила по указанной формуле будет проведена биссектриса дополнительного угла треугольника, а окружность окажется вневписанной. Лекция 9 Кривые 2-го порядка. Сплайны. Кривые Безье Кривые второго порядка Общий вид уравнения линии 2-го порядка: a1x2+a2y2+a3xy+a4x+a5y+a6=0. Рассмотрим различные формы линий 2-го порядка. Уравнение окружности: (x-x0)2+(y-y0)2=r2 – нормальное уравнение окружности, C(x0, y0) – центр окружности, M(x,y) – произвольная точка окружности, x2+y2+x+y+=0, =-2x0; =-2y0; =x02+y02-r2. Ax2+Ay2+Dx+Ey+F=0 – общее уравнение окружности. Действительная окружность при (2+2)/4-0, где =D/A; =E/A; =F/A. Таким образом, действительная кривая 2-го порядка является окружностью тогда и только тогда, когда: 1) коэффициенты при квадратах текущих координат равны между собой; 2) отсутствует член, содержащий произведение текущих координат. Центральные кривые 2-го порядка – кривые, имеющие собственный центр симметрии. A(x-x0)2+C(y-y0)2=D, AC. O(x0, y0) – центр симметрии кривой; x=x0, y=y0 – оси симметрии кривой. Пусть x0=0 и y0=0. Кривая 2-го порядка принадлежит эллиптическому типу, если коэффициенты A и C имеют одинаковые знаки, т.е. AC>0. Пусть A>0 и C>0, тогда если: ● D>0 – действительный эллипс, x2/a2+y2/b2=1 – каноническое уравнение эллипса; ● D=0 – вырожденный эллипс (кривая вырождается в точку); ● D<0 – мнимый эллипс. Кривая 2-го порядка является кривой гиперболического типа, если коэффициенты A и C имеют противоположные знаки, т.е. AC<0. Пусть A>0, тогда C<0: ● если D>0 – гипербола (рис. 7), x2/a2-y2/b2=1 – каноническое уравнение гиперболы; ● если D=0 – вырожденная гипербола представляет собой пару пересекающихся прямых ; ● если D<0 – сопряженная гипербола (рис. 7), xy=a2 (a>0) – обратная пропорциональность. Графиком является равнобочная гипербола (к уравнению гиперболы легко прийти, повернув оси координат на 45 º – рис. 8). Нецентральные кривые 2-го порядка не имеют центра симметрии или имеют бесконечное множество центров, могут иметь ось симметрии. (y-y0)2=2p(x-x0) – парабола, O(x0, y0) – вершина параболы, P – параметр параболы. Если вершина параболы находится в начале координат и p>0, то y2=2px – каноническое уравнение параболы. Параметрические уравнения линий. Параметрическое уравнение окружности: Параметрическое уравнение эллипса: Параметрическое уравнение параболы: Циклоида (кривая, описываемая точкой окружности, катящейся без скольжения по прямой линии): Спираль Архимеда: =a (a>0) – уравнение в полярных координатах. Сплайны. Кривые Безье Сплайн – гладкая кривая, которая проходит через две или более опорных точек, а также имеет расположенные вне ее управляющие точки, влияющие на форму сплайна. Наиболее общие типы сплайнов – кривые Безье и B-сплайны (B-spline curves). Типичным примером сплайнов являются также неоднородные рациональные B-сплайны (Non-Uniform Rational B-Spline – NURBS). Сплайны состоят из вершин (Vertices) и сегментов (Segments). Каждая вершина сплайна имеет касательные векторы (Tangents), снабженные на концах управляющими точками, или маркерами (Handels). Маркеры касательных векторов управляют кривизной сегментов сплайна при входе в вершину, которой принадлежат касательные векторы, и выходе из нее. Кривые Безье разработаны математиком Пьером Безье. Кривые и поверхности Безье использовались в 60-х годах компанией "Рено" для компьютерного проектирования формы кузовов автомобилей. В настоящее время они широко используются в компьютерной графике. Кривые Безье описываются в параметрической форме: x=Px(t), y=Py(t). Значение t выступает как параметр, которому отвечают координаты отдельной точки линии. Многочлены Безье для Px и Py имеют следующий вид: где Cmi – сочетание m по i, а xi, yi – координаты точек ориентиров Pi. Значение m можно рассматривать и как степень полинома, и как значение, которое на единицу меньше количества точек-ориентиров. Рассмотрим кривые Безье, классифицируя их по значени- ям m. m=1 (по двум точкам). Кривая вырождается в отрезок прямой линии, определяемой концевыми точками P0 и P1. Параметрическое уравнение: P(t)=(1-t)P0 + tP1. m=2 (по трем точкам). Параметрическое уравнение: P(t)=(1-t)2P0 + 2t(1-t)P1 + t2P2. m=3 (по четырем точкам – кубическая). Используется довольно часто, в особенности в сплайновых кривых. Параметрическое уравнение: P(t)=(1-t)3P0 + 3t(1-t)2P1 + 3t2(1-t)P2 + t3P3. Геометрический алгоритм для кривой Безье позволяет вычислить координаты (x, y) точки кривой Безье по значению параметра t (рис. 9). 1. Каждая сторона контура многоугольника, проходящего по точкам-ориентирам, делится пропорционально значению t. 2. Точки деления соединяются отрезками прямых и образуют новый многоугольник. Количество узлов нового контура на единицу меньше, чем количество узлов предыдущего контура. 3. Стороны нового контура снова делятся пропорционально значению t и т.д. Это продолжается до тех пор, пока не будет получена единственная точка деления – точка кривой Безье. Сегмент кривой Безье 3-го порядка описывается положением четырех точек. Две из них являются опорными (узлами кривой): начальная точка P0 (x0, y0) и конечная P3 (x3, y3). Точки P1 (x1, y1) и P2 (x2, y2), определяющие положение касательных относительно отрезка, называются управляющими. Метод построения кривой Безье основан на использовании пары касательных (управляющих линий), проведенных к сегменту кривой в его окончаниях. На форму кривой влияют угол наклона касательной и длина ее отрезка. Параметрическое уравнение Безье описывает положение точек и, тем самым, форму кривой. Уравнение решают относительно параметра t, принимающего значения от 0 (в начальной точке) до 1 (в конечной точке). При построении сегмента кривой Безье на плоскости рассчитывают координаты x и y (для четырех точек, из них двух управляющих): R(t)=P0(1-t)3 + P1t(1-t)2 + P2t2(1-t) + P3t3, где 0 0) и подсчете числа его пересечений с ребрами p. Анализ пар дает следующие критерии ориентации точки относительно полигона: точка является внутренней, если число пар нечетно (ti>0, 0<i<1); точка является внешней, если число пар четно, в том числе равно нулю; точка лежит на границе p, если найдется хотя бы одна пара, для которой ti=0, 0i1. Особенности лучевого теста (рис. 14): ● неопределенность числа пересечений при прохождении луча точно через вершину pi при i=1 или вершину pi+1 при i=0. Необходимо повторить тест заново с другим направлением луча V; ● требуется расчет параметров пересечения луча со всеми ребрами полигона. Исследуются параметры пересечения луча с отрезками pi+(pi+1–pi), 01. Лекция 11 Базовые растровые алгоритмы Алгоритмы вывода прямой линии Пусть заданы координаты (x1,y1) и (x2,y2) концов отрезка прямой линии. Для вывода линии необходимо закрасить в определенный цвет все пикселы вдоль линии. Для того чтобы закрасить каждый пиксел, необходимо знать его координаты. Наиболее просто нарисовать отрезок горизонтальной линии (y1=y2): для x от x1 до x2 с шагом 1 закрашиваются соседние пикселы (x, y1). (Эта операция достаточно проста и применяется в алгоритмах закрашивания полигонов.) Аналогично изображается отрезок вертикальной линии. Горизонтали и вертикали представляют собой частный случай линий. Рассмотрим линию общего вида. Известно несколько методов расчета координат точек линии. Прямое вычисление координат. Пусть заданы координаты конечных точек отрезка. Координаты внутренней точки отрезка вычисляются следующим образом: x=f(y): x=x1+(y-y1)(x2-x1)/(y2-y1) или y=F(x): y=y1+(x-x1)(y2-y1)/(x2-x1). В зависимости от угла наклона прямой выполняется цикл по оси x (если |x2-x1|>|y2-y1|) или по оси y (в противном случае). Для того чтобы свести к минимуму вычисления в цикле, все операции над константами выносятся из тела цикла: k=(y2-y1)/(x2-x1), yy=y1-x1*k. В цикле вычисляется y=yy+x*k. Если учесть, что вычисления выполняются как итеративный процесс, где x на каждом шаге увеличивается на единицу, то вычисления в данном алгоритме еще более упрощаются: k=(y2-y1)/(x2-x1), y=y1. Для x от x1 до x2 с шагом 1 вычисляется y=y+k. С учетом того, что вычисление дробей в компьютере происходит с определенной погрешностью, возможно ситуация, когда на последнем шаге цикла x окажется не равным x2. Это необходимо учитывать при использовании алгоритма. Положительные черты алгоритма прямого вычисления координат: ◦ простота, ясность построения алгоритма; ◦ возможность работы с нецелыми значениями координат отрезка. Недостатки: ◦ использование операций с дробными числами или целочисленных операций умножения и деления обуславливает малую скорость; ◦ при вычислении координат путем добавления приращений может накапливаться ошибка. Инкрементные алгоритмы Брезенхэм предложил подход, позволяющий разрабатывать так называемые инкрементные алгоритмы растеризации. Основной целью разработки таких алгоритмов было построение циклов вычисления координат на основе только целочисленных операций сложения/вычитания без использования умножения и деления. Уже известны инкрементные алгоритмы не только для отрезков прямых, но и для кривых линий. Инкрементные алгоритмы выполняются как последовательное вычисление координат соседних пикселов путем добавления приращений координат. Приращения рассчитываются на основе анализа функции погрешности. В цикле выполняются только целочисленные операции сравнения и сложения/вычитания. Достигается повышение быстродействия для вычисления каждого пиксела по сравнению с прямым способом. Один из вариантов алгоритма Брезенхэма ([12, с. 100-101]): xerr:=0; yerr:=0; dx:=x2-x1; dy:=y2-y1; Если dx>0, то incX:=1; dx=0, то incX:=0; dx<0, то incX:=-1; Если dy>0, то incY:=1; dy=0, то incY:=0; dy<0, то incY:=-1; dx:=|dx|; dy:=|dy|; Если dx>dy, то d:=dx иначе d:=dy; x:=x1; y:=y1; Закрасить пиксел с координатами (x, y); Выполнить d раз цикл: xerr:=xerr+dx; yerr:=yerr+dy; Если xerr>=d, то xerr:=xerr-d, x:=x+incX; Если yerr>=d, то yerr:=yerr-d, y:=y+incY; Закрасить пиксел с координатами (x, y). Рассмотрим пример работы приведенного выше алгоритма Брезенхэма для отрезка (2;3) - (8;6). Этот алгоритм восьмисвязный, т.е. при вычислении приращений координат для перехода к соседнему пикселу возможны восемь случаев: 2 3 4 5 6 7 8 incY=-1 3 4 incX=-1 incX=1 5 6 incY=1 Известны также четырехсвязные алгоритмы. Они более просты, но генерируют менее качественное изображение линий за большее количество тактов работы. Для приведенного примера четырехсвязный алгоритм работает 10 тактов, а восьмисвязный - только 7: 2 3 4 5 6 7 8 incY=-1 3 4 incX=-1 incX=1 5 6 incY=1 Алгоритм вывода окружности Для вывода контура круга можно использовать соотношение между координатами X и Y для точек окружности X2+Y2=R2 и построить алгоритм прямого вычисления координат. Однако в этом случае необходимо вычислять квадратный корень (как элемент бесконечной последовательности приближений). Приведем запись инкрементного алгоритма Брезенхэма: r2:=radius*radius; dst:=4*r2; dxt:=radius/1.414213562373; t:=0; s:=-4*r2*radius; e:=(-s/2)-3*r2; ca:=-6*r2; cd:=-10*r2; x:=0; y:=radius; Закрасить пиксел (xc,yc+radius); Закрасить пиксел (xc,yc-radius); Закрасить пиксел (xc+radius,yc); Закрасить пиксел (xc-radius,yc); Для indx от 1 до dxt с шагом 1: x:=x+1; Если e>=0 то e:=e+t+ca иначе y:=y-1, e:=e+t-s+cd, s:=s+dst; t:=t-dst; Закрасить пиксел (xc+x,yc+y); Закрасить пиксел (xc+y,yc+x); Закрасить пиксел (xc+y,yc-x); Закрасить пиксел (xc+x,yc-y); Закрасить пиксел (xc-x,yc-y); Закрасить пиксел (xc-y,yc-x); Закрасить пиксел (xc-y,yc+x); Закрасить пиксел (xc-x,yc+y). В этом алгоритме используется симметрия круга - в основном цикле вычисляются координаты точек окружности только для одного октанта и сразу рисуются восемь симметрично расположенных пикселов. Алгоритм вывода эллипса Инкрементный алгоритм для эллипса подобен алгоритму для круга, но несколько сложнее его: a:=|enx-xc|; b:=|eny-yc|; a2:=a*a; b2:=b*b; dds:=4*a2; ddt:=4*b2; dxt:=a2/sqrt(a2+b2); t:=0; s:=-4*a2*b; e:=(-s/2)-2*b2-a2; ca:=-6*b2; cd:=ca-4*a2; x:=xc; y:=yc+b; Закрасить пиксел (x, y); Закрасить пиксел (x, 2*yc-y); Закрасить пиксел (2*xc-x, 2*yc-y); Закрасить пиксел (2*xc-x, y); Для indx от 1 до dxt с шагом 1: x:=x+1; Если e>=0 то e:=e+t+ca иначе y:=y-1, e:=e+t-s+cd, s:=s+dds; t:=t-ddt; Закрасить пиксел (x, y); Закрасить пиксел (x, 2*yc-y); Закрасить пиксел (2*xc-x, 2*yc-y); Закрасить пиксел (2*xc-x, y); dxt:=|y-yc|; e:=e-(t/2+s/2+b2+a2); ca:=-6*a2; cd:=ca-4*b2; Для indx от 1 до dxt с шагом 1: y:=y-1; Если e<=0 то e:=e-s+ca иначе x:=x+1, e:=e-s+t+cd, t:=t-ddt; s:=s+dds; Закрасить пиксел (x, y); Закрасить пиксел (x, 2*yc-y); Закрасить пиксел (2*xc-x, 2*yc-y); Закрасить пиксел (2*xc-x, y). В этом алгоритме использована симметрия эллипса по квадрантам. Алгоритм состоит из двух циклов. Сначала для x от 0 до dxt, где а потом цикл до точки x=a, y=0. Лекция 12 Алгоритмы закрашивания Задача графического вывода фигур Будем считать фигурой плоский геометрический объект, который состоит из линий контура и точек внутри него. В общем случае линий контура может быть несколько – когда объект имеет внутри пустоты. В этом случае для описания таких фигур необходимы два и более контуров (рис. 15). Графический вывод фигур разделяется на две задачи: вывод контура и вывод точек заполнения. Поскольку контур представляет собой линию, то вывод контура производится на основе алгоритмов вывода линий. В зависимости от сложности контура это могут быть отрезки прямых, кривых или произвольная последовательность соседних пикселов. Для вывода точек заполнения известны методы, разделяющиеся в зависимости от использования контура на два типа: алгоритмы закрашивания от внутренней точки к границам произвольного контура и алгоритмы, которые используют математическое описание контура. Алгоритмы закрашивания В общем виде алгоритм закрашивания произвольного контура, который уже нарисован в растре, предполагает выполнение следующих действий: – находим пиксел внутри контура фигуры; – цвет этого пиксела изменяем на нужный цвет заполнения; – производим анализ соседних пикселов; – если цвет некоторого соседнего пиксела не равен цвету границы контура или цвету заполнения, то цвет этого пиксела изменяется на цвет заполнения; – анализируем цвет пикселов, соседних с предыдущим; и так далее, до тех пор, пока внутри контура все пикселы не перекрасятся в цвет заполнения. Пикселы контура – это граница, за которую нельзя выходить в ходе последовательного перебора всех соседних пикселов. Соседними могут считаться только четыре пиксела (справа, слева, сверху, снизу – четырехсвязность) или все восемь (восьмисвязность). Не всякий контур может служить границей закрашивания (рис. 16). Простейший алгоритм закрашивания. Для всех алгоритмов закрашивания необходимо задавать начальную точку с координатами x0, y0 внутри контура. Простейший алгоритм может быть описан следующим образом. 1. Определить x0, y0. 2. Выполнить процедуру Закрасить(x0, y0). Процедура Закрасить(x,y) описана в виде: если цвет пиксела (x,y) не равен цвету границы, то установить для пиксела (x,y) цвет заполнения; закрасить(x+1, y); закрасить(x-1, y); закрасить(x, y+1); закрасить(x, y-1). Такое определение процедуры является рекурсивным. Рекурсия позволяет упростить запись некоторых алгоритмов. Но для этого алгоритма рекурсия порождает существенные проблемы - рекурсивные вызовы процедуры закрасить () делаются для каждого пиксела, что обычно приводит к переполнению стека в ходе выполнения компьютерной программы. Практика показывает, что этот алгоритм неприемлем для фигур площадью в тысячу и больше пикселов. Волновой алгоритм закрашивания был разработан Т.А. Блиновой и В.Н. Поревым и предназначался для расчета центра тяжести объектов по соответствующим изображениям – на основе волнового алгоритма поиска трассы на графе. Суть подобных алгоритмов состоит в том, что для начальной точки (вершины на графе) находятся соседние точки (другие вершины), которые отвечают двум условиям: во-первых, эти вершины связаны с начальной; во-вторых, они еще не отмечены, т.е. рассматриваются впервые. Соседние вершины текущей итерации отмечаются в массиве описания вершин, и каждая из них становится текущей точкой для поиска новых соседних вершин в следующей итерации. Если в специальном массиве отмечать каждую вершину номером итерации, то, когда будет достигнута конечная точка, можно совершить обратный цикл – от конечной точки к начальной по убыванию номеров итераций. В ходе обратного цикла и находятся все кратчайшие пути (если их несколько) между двумя заданными точками на графе. Относительно закрашивания растровых фигур вершинами графа являются пикселы, а отметка пройденных пикселов делается прямо в растре цветом закрашивания. Это почти полностью повторяет идею простейшего алгоритма, однако здесь не используется рекурсия, что обусловливает другую последовательность обработки пикселов при закрашивании. От начальной точки распространяется волна пикселов закрашивания в виде ромба (рис. 171). В одном цикле закрашиваются пикселы вдоль линии периметра ромба (или нескольких ромбов в зависимости от сложности фигуры). Необходимо заметить, что этот алгоритм не является самым быстрым из известных алгоритмов закрашивания. Большую скорость закрашивания обеспечивают алгоритмы, которые обрабатывают не отдельные пикселы, а сразу блоки из многих пикселов, которые образуют прямоугольники или линии. Алгоритм закрашивания линиями получил широкое распространение в компьютерной графике. От приведенного ранее простейшего рекурсивного алгоритма он отличается тем, что на каждом шаге закрашивания рисуется горизонтальная линия, которая размещается между пикселами контура (рис. 18). Алгоритм рекурсивный, но поскольку вызов функции осуществляется для линии, а не для каждого отдельного пиксела, то количество вложенных вызовов уменьшается пропорционально длине линии. Это снижает нагрузку на стековую память компьютера. На этом алгоритме основан принцип работы процедуры FloodFill API Windows. Алгоритмы заполнения, использующие математическое описание контура Математическим описанием контура может служить уравнение y=f(x) для окружности, эллипса или другой кривой. Для многоугольников (полигонов) контур задается множеством координат вершин (xi, yi). Возможны и другие формы описания контура. В любом случае алгоритмы данного класса не предусматривают обязательное предварительное создание пикселов контура растра - контур может совсем не выводиться в растр. Рассмотрим некоторые подобные алгоритмы заполнения. Заполнение прямоугольника (рис. 19). Если прямоугольник задан координатами противоположных углов, например, левого верхнего (x1, y1) и правого нижнего (x2, y2), тогда алгоритм может заключаться в последовательном рисовании горизонтальных линий заданного цвета: для y от y1 до y2 с шагом 1: нарисовать горизонтальную линию с координатами (x1, y)-(x2, y) Заполнение круга. Для заполнения круга можно использовать алгоритм вывода контура, который был рассмотрен на предыдущих лекциях. В процессе выполнения этого алгоритма последовательно вычисляются координаты пикселов контура в границах одного октанта. Для заполнения надлежит выводить горизонтали, которые соединяют пары точек на контуре, расположенные симметрично относительно оси y (рис. 20). Аналогично может быть построен и алгоритм заполнения эллипса. Заполнение полигона. Контур полигона (в векторной форме) определяется вершинами, которые соединены отрезками прямых (рис. 21). Один из наиболее популярных алгоритмов заполнения полигона заключается в закрашивании фигуры отрезками прямых горизонтальных линий. Алгоритм представляет собою цикл вдоль оси y, в ходе этого цикла выполняется поиск точек сечения линии контура с соответствующими горизонталями. Этот алгоритм получил название XY (Ж.Эгрон): 1. Найти min{yi} и max{yi} среди всех вершин Pi. 2. Выполнить цикл по y от y=min до y=max: 3. Найти точки пересечения всех отрезков контура с горизонталью y; 4. Координаты xj точек сечения записать в массив; 5. Отсортировать массив {xj} по возрастанию x; 6. Вывести горизонтальные отрезки с координатами (x0, y) - (x1, y) (x2, y) - (x3, y) ……………… (x2k, y) - (x2k+1, y) Каждый отрезок выводится цветом заполнения. В этом алгоритме использовано свойство топологии контура фигуры. Оно состоит в том, что любая прямая линия пересекает любой замкнутый контур четное число раз. Для выпуклых фигур существуют ровно две точки пересечения с любой прямой. Таким образом, на шаге 4 этого алгоритма в массив {xj} всегда должно записываться парное число течек сечения. При нахождении точек пересечения горизонтали с контуром необходимо принимать во внимание особые точки. Если горизонталь имеет координату y, совпадающую с yi вершины Pi, тогда надлежит анализировать то, как горизонталь проходит через вершину. Если горизонталь при этом пересекает контур (как, например, в вершинах P0 или P4), то в массив записывается одна точка сечения. Если горизонталь касается вершины контура (в этом случае вершина соответствует локальному минимуму или максимуму, как, например, в вершинах P1, P2, P3 или P5), тогда координата точки касания или не записывается, или записывается в массив два раза. Это условие четности числа количества точек пересечения, хранящихся в массиве {xj}. Процедура определения точек пересечения с горизонтальной разверткой, учитывая анализ на локальный максимум, может быть достаточно сложной. Это замедляет работу. Для определения координат (x) точек пересечения для каждой горизонтали необходимо перебрать все n отрезков контура. Координаты пересечения отрезка pi-pk с горизонталью равны: x = xi + (yk - y)(xk - xi)/(yk - yi). Количество тактов работы этого алгоритма: Nтактов  (ymax - ymin)Nгор , где ymax, ymin – диапазон координат y, Nгор – число тактов, необходимых для одной горизонтали. Оценим величину Nгор как пропорциональную числу вершин: Nгор  k*n, где k – коэффициент пропорциональности, n – число вершин полигона. Приведенные выше алгоритмы заполнения могут быть использованы не только для рисования фигур. На их основе могут быть разработаны алгоритмы для других целей, например, для определения площади фигуры, если считать площадь пропорциональной числу пикселов заполнения. Или, например, алгоритм для поиска объектов по внутренней точке – эта операция часто используется в векторных графических редакторах. Лекция 13 Фрактальные алгоритмы Понятие фрактала Латинское слово fractus означает "составленный из фрагментов". Фрактал можно определить как объект довольно сложной формы, получающийся в результате выполнения простого итерационного цикла. Итерационность, рекурсивность обусловливают такие свойства фракталов, как самоподобие – отдельные фрагменты фрактала похожи по форме на весь фрактал в целом. В 1975 г. французский математик Бенуа Мандельброт издал книгу "The fractal Geometry of Nature". "Почему геометрию часто называют холодной и сухой? Одна из причин заключается в ее неспособности описать форму облака, горы, дерева или берега моря. Облака – это не сферы, горы – не конусы, линии берега – не окружности, и кора не является гладкой, и молния не распространяется по прямой… Природа демонстрирует нам не просто более высокую степень, а совсем другой уровень сложности. Математики… предпочли все больше и больше отдаляться от природы, изобретая теории, которые не соответствуют ничему из того, что можно увидеть или почувствовать…" (Б.Мандельброт). Мандельброт предложил сначала определение фрактала в таком виде: "Фракталом называется множество, размерность Хаусдорфа-Безиковича которого строго больше его топологической размерности". Затем он сформулировал более простое выражение: "Фракталом называется структура, состоящая из частей, которые в каком-то смысле подобны целому". Так что строгого и полного определения фракталов до сих пор не существует. Выделяют несколько разновидностей фракталов: алгоритмические, геометрические и фракталы на основе метода IFS. Алгоритмические фракталы Фрактал Мандельброта. Мандельброт исследовал предельное (при k  ) поведение последовательности комплексных чисел zk+1= zk2 + z0 , k=0, 1, 2, …; z0=c при различных значениях комплексных чисел c. Последовательность zk с ростом числа итераций демонстрирует поведение двух типов в зависимости от выбора начальной точки z0. Ее элементы либо постепенно уходят в бесконечность, либо всегда остаются в определенной замкнутой области, совершая циклическое движение или сходясь в точку. Математиками строго доказано, что если при некотором k модуль |zk|>rmin, где rmin=2 – минимальный радиус расходимости множества Мандельброта, то далее последовательность расходится. Множество точек z0, для которых последовательность не расходится, называется множеством Мандельброта. Графическая интерпретация множества Мандельброта удивительно красива и бесконечно разнообразна. Для ее получения используется следующий алгоритм. Комплексное число z=x+iy может быть изображено на плоскости точкой с координатами (x, y). Изображение строится в некоторой прямоугольной области с разрешением n*m точек. Формула итераций для фрактала Мандельброта выглядит следующим образом: zk+1= zk2 + z0 , k=0, 1, 2, … Цикл итераций для фрактала Мандельброта можно выполнять в диапазоне для x0=(от -2,2 до 1) , для y0=(от -1,2 до 1,2) – начальные точки z0. Для каждой начальной точки вычисляется количество k точек, попадающих в круг сходимости (k – число итераций). Условием завершения итераций является |zk|>2. Суть алгоритма сводится к итерационному выводу точек, попадающих в круг сходимости для каждой начальной точки, в пределах заданного графического окна. Для каждого цикла итерации (для каждой начальной точки) выбирается свой цвет. Если принять значения k для каждой начальной точки (x,y) в качестве высот некоторой поверхности в данной точке можно построить объемное изображение множества Мандельброта или его части, которое при специально подобранном освещении может выглядеть и как скала с плоской вершиной, и как водопад, и как горная пещера. Типичный фрактал, каким является множество Мандельброта, представляет собой иерархический объект, состоящий из родительского тела в форме кардиоиды и многочисленных потомков, повторяющих форму предков, от которых они ответвляются. Само подобие элементов фрактала хорошо видно на его изображении. Связность множества означает, что его элементы, даже самого малого размера, которые Мандельброт назвал "фрактальной пылью", не обособлены, а соединены тончайшими нитями в одно целое. Продолжая процесс увеличения пограничных областей, мы всюду видим бесконечное разнообразие форм, поражающих гармонией, великолепием и удивительным сходством с изображениями регулярно-хаотических явлений природы: молний, снежинок, ледяного узора, инея на ветвях деревьев, кораллов, паутины, солнечных протуберанцев, звездных скоплений и т.п. Фрактал Джулио (Жюлио) внешне совсем не похож на фрактал Мандельброта, хотя формула итераций для этого фрактала почти полностью совпадает с формулой для фрактала Мандельброта: zk+1= zk2 + c , k=0, 1, 2, … где c – комплексная константа. Если при генерации фрактала Мандельброта значение z0 каждый раз совпадает со значением в начальной точке на данном шаге итераций, то для фрактала Джулио значение c всегда одно и то же комплексное число. В программе, (приведенной в приложении 2), построено изображение фрактала Джулио для c=0,36+i*0,36. Итерационная формула для фрактала Ньютон имеет вид где z – также комплексные числа, причем z0=x+iy соответствует координатам точки изображения. Условием прекращения цикла итераций для фрактала Ньютон есть приближение значений |z4-1| к нулю. Границы расчета: для x – от -1 до 1, для y – от -1 до 1. Геометрические фракталы Геометрическими названы фракталы, форма которых может быть описана как последовательность простых геометрических операций. Геометрические фракталы строятся на основе исходной фигуры – линии, полигона, полиэдра – путем ее дробления и выполнения аффинных и логических преобразований (объединения или исключения) полученных фрагментов. Метод построения фрактального объекта может быть как итерационным, так и рекурсивным, причем рекурсивный чаще бывает богаче возможностями и проще в программировании. Например, кривая Кох становится фракталом в результате бесконечного количества итераций, в ходе которых выполняется деление каждого отрезка прямой на три части. На средней части отрезка строится правильный треугольник, затем процесс повторяется для каждого из полученных отрезков, кроме среднего (рис. 22). Алгоритм основан на рекурсивном вызове процедуры для каждого из полученных отрезков. Аналогичный алгоритм используется при построении фрактального треугольника. Вообще алгоритм построения кривой Кох можно применить к любому многоугольнику или ломаной линии, запустив алгоритм построения кривой Кох для каждого из составляющих фигуру отрезков (в приложении 2 содержится программа построения кривой Кох и фрактального треугольника с помощью этой процедуры). Площадные фракталы Строительными элементами площадных геометрических фракталов служат плоские полигоны, чаще всего трех- и четырехугольники. Самым знаменитым фракталом этого класса является треугольник Серпинского, строящийся путем разбиения треугольника – не обязательно равностороннего – средними линиями на четыре подобных треугольника, исключения центрального и рекурсивного разбиения угловых треугольников до получения площадных элементов желаемого или минимально видимого разрешения. Алгоритм построения треугольника Серпинского (рис. 23). 1. Внутри исходного треугольника выбирается центральная точка: 2. Задается число m итераций генерирования случайных точек. 3. В цикле для k от 1 до m: – случайным образом выбирается номер n одной из вершин треугольника pn (генерируется случайное число в интервале от 1 до 3). – вычисляется очередная точка qk в середине отрезка qk-1 pn: Благодаря выбору точки q0 внутри треугольника p1 p2 p3 центр отрезка q0 pn (точка q1) никогда не окажется внутри центрального треугольника, отмеченного на рисунке пунктиром. При достаточно большом числе итераций m генерируемые точки qk образуют случайный узор, предельная форма которого стремится к треугольнику Серпинского. Следует отметить, что небольшое число начальных точек qk все-таки может попасть в запретные области. В частности, это случится при выборе точки q0 в центре треугольника p1 p2 p3 . Аналогично треугольнику Серпинского может быть построена треугольная пирамида Серпинского. Фракталы на основе метода IFS Эту группу составляют фракталы, которые генерируются согласно методу "систем итеративных функций" – IFS (Iterated Functions Systems). Данный метод может быть описан как последовательный итеративный расчет координат новых точек в пространстве: где Fx и Fy – функции преобразования координат, например аффинного преобразования. Эти функции и определяют форму фрактала. В случае аффинного преобразования необходимо найти соответствующие числовые значения коэффициентов. Примером такого фрактала является построение изображения листа папоротника (рис. 24). Для начала итераций необходимо задать стартовые координаты линии – точки 1 и 2. На каждом шаге итераций рассчитываются координаты других точек. Точка 3 получается поворотом точки 2 на угол  относительно центра в точке 1: x3=(x2-x1)cos-(y2-y1)sin+x1, y3=(x2-x1)sin+(y2-y1)cos+y1. Если =0, то ствол и все ветви прямые. Находим точку 4. От нее будут распространяться ветви. Пусть соотношение длин отрезков 1-4 и 1-3 равно k (0lmin, то Вычисляем координаты точек 3-7: x3=(x2-x1)A ­- (y2-y1)B + x1 y3=(x2-x1)B + (y2-y1)A + y1 x4=x1C + x3D y4=y1C + y3D x5=x4E + x3F y5=y4E + y3F x6=(x5-x4)G - (y5-y4)H + x4 y6=(x5-x4)H + (y5-y4)G + y4 x7=(x5-x4)G + (y5-y4)H + x4 y7=-(x5-x4)H + (y5-y4)G + y4 Рисуем отрезок (x1, y1 - x4, y4) ШАГ(x4, y4, x3, y3, num) ШАГ(x4, y4, x6, y6, num+1) ШАГ(x4, y4, x7, y7, num+1) Для того чтобы нарисовать фрактал, необходимо вызвать процедуру ШАГ, установив соответствующие значения ее аргументов: ШАГ(x1,y1,x2,y2,0). Параметр num показывает степень детализации расчета дерева. Это значение можно использовать для прекращения итеративного процесса. Завершение циклов итерации в нашем алгоритме происходит тогда, когда длина ветви становится меньше некоторой величины lmin. Применение методов фрактальной графики Метод IFS применяется не только для создания изображений. Барнсли и Слоан использовали его для эффективного сжатия графических изображений при записи в файлы. Основная идея такова: поскольку фракталы могут представлять очень сложные изображения с помощью простых итераций, то описание этих итераций требует значительно меньшего объема информации, чем соответствующие растровые изображения. При кодировании изображения необходимо решать обратную задачу: для изображения (или его фрагмента) подобрать соответствующие коэффициенты аффинного преобразования. Этот метод используется для записи цветных фотографий в файлы со сжатием в десятки и сотни раз без заметного ухудшения изображения. Формат таких графических файлов назван FIF (Fractal Image Format) и запатентован фирмой Iterated Sistems. Фрактальный подход нашел широкое распространение во многих областях компьютерной графики, искусства и науки. Так, появилась теория фрактальных трещин, фрактальная механика древесно-полимерных композитов и другие отрасли. В задачах КГ фрактальная технология получила наибольшее распространение при формировании объектов природного ландшафта: линии горизонта, неровных поверхностей, холмов, гор, каньонов и прочих нерегулярных образований. Построение основано на рекурсивном разбиении исходного объекта средними точками и смещении этих точек по методу управляемой случайности. Начальные объекты выбираются из простых геометрических фигур: отрезков, треугольников, прямоугольников, тетраэдров. Фракталы широко применяют в растровых редакторах (Adobe Photoshop, Corel Painter), в векторной (Corel Draw, Adobe Illustrator) и трехмерной (Corel Bryce, 3Dmax) графике. Существует программа FractalWorld российского программиста Юрия Щербакова, позволяющая строить изображения фракталов, описываемых системой двух уравнений второго порядка: x[k+1] = a1x[k]2 + a2 y[k]2 + a3 x[k] y[k] +a4 x[k] + a5 y[k] +a6; y[k+1] = b1x[k]2 + b2 y[k]2 + b3 x[k] y[k] +b4 x[k] + b5 y[k] +b6. Задавая коэффициенты a и b, создают непохожие изображения. Цвет точки изображения соответствует количеству итераций. Критерий завершения итераций: x2+y2>10 для заданной стартовой точки. Классификация фрактальных алгоритмов. По принципу преобразования элементов между итерациями фрактальные алгоритмы делятся на линейные (геометрические фракталы) и нелинейные (фрактал Мандельброта). По характеру изменения объема пространства, занимаемого фрактальными объектами, между соседними уровнями рекурсии, фракталы делятся на аддитивные (увеличивающие объем занимаемого фракталом пространства) и субтрактивные (объем занимаемого фракталом пространства уменьшается – треугольник Серпинского). Свойства фракталов. 1. Прежде всего фрактал – это не линия или поверхность в виде привычных уравнений. Фракталы выражаются не в первичных геометрических формах, а в алгоритмах, которые трансформируются в геометрические формы с помощью компьютерной программы. 2. Характер большинства фрактальных алгоритмов преимущественно рекурсивный. 3. Теоретически глубина рекурсии фрактала бесконечна. 4. Независимо от природы и метода построения у всех фракталов есть одно важное общее свойство, характеризующее степень их раздробленности и предельные свойства. Это – фрактальная размерность. Согласно идее Мандельброта ее можно определить подсчетом числа элементов N, принадлежащих фрактальному множеству, при различных разрешениях  – минимальных линейных размерах элементов. 5. Размерность фрактала может быть дробной. Лекция 14 Методы и алгоритмы трехмерной графики. Модели описания поверхностей Понятие "трехмерная графика" подразумевает не способы построения собственно трехмерных объектов, а их изображения на плоскости. Истинно трехмерные способы отображения объектов пока что недостаточно широко распространены. Рассмотрим методы представления трехмерных объектов в системах КГ. Для описания формы их поверхностей могут использоваться разнообразные модели. Аналитическая модель поверхности Аналитической моделью называется описание поверхности математическими формулами: z=f(x,y) – описание с помощью функции, F(x,y,z)=0 – описание с помощью неявного уравнения. Зачастую используется параметрическая форма описания поверхности: где s и t – параметры, которые изменяются в определенном диапазоне, а функции Fx, Fy и Fz определяют форму поверхности. Преимущество параметрической формы заключается в легкости описания поверхностей, которые отвечают неоднозначным функциям, и замкнутых поверхностей. Параметрическое описание можно задать таким образом, что формула не будет существенно изменяться (усложняться) при поворотах поверхности, и ее масштабировании. В качестве примера рассмотрим аналитическое описание поверхности шара. — явная функция двух аргументов, x2 + y2 + z2 -R2 = 0 — неявное уравнение, x = R sin s cos t, y = R sin s sin t, z = R cos s — в параметрической форме. Для описания сложных поверхностей часто используют сплайны. Сплайн – это специальная функция для аппроксимации отдельных фрагментов поверхности. Несколько сплайнов образуют модель сложной поверхности. Иными словами, сплайн – это тоже поверхность, но такая, для которой можно достаточно просто вычислять координаты ее точек. В трехмерной графике обычно используют кубические сплайны по двум основным причинам: – третья степень – наименьшая из степеней, позволяющих описывать любую форму; – при стыковке сплайнов можно обеспечить непрерывную первую производную – такая поверхность будет без изломов в местах стыка. Сплайны, как правило, задают параметрически. Рассмотрим одну из разновидностей сплайнов – сплайн Безье. В обобщенной форме (степени m*n): где Pij – опорные точки-ориентиры, 0  s  1, 0  t  1, Cmi и Cnj – коэффициенты бинома Ньютона, которые рассчитываются по формуле Кубический сплайн Безье соответствует значениям m=3, n=3. Для его определения необходимо 16 точек-ориентиров Pij; коэффициенты Cmi и Cnj равны 1, 3, 3, 1 при i, j = 0, 1, 2, 3. Аналитическая модель наиболее пригодна для многих операций анализа поверхностей. Достоинства модели (с позиций КГ): ● легкость расчета координат каждой точки поверхности, нормали; ● небольшой объем данных для описания достаточно сложных форм. Недостатки: ● сложность формул описания с использованием функций, которые медленно вычисляются на компьютере, снижают скорость выполнения операций отображения; ● невозможность в большинстве случаев применить данную форму описания непосредственно для изображения поверхности - поверхность отображается как многогранник, координаты вершин и граней которого рассчитываются в процессе отображения, что уменьшает скорость сравнительно с полигональной моделью описания. Векторная полигональная модель Для описания пространственных объектов используются следующие элементы: вершины, отрезки прямых (векторы), полилинии, полигоны, полигональные поверхности. Элемент "вершина" (vertex) – главный элемент описания, все остальные являются производными. При использовании трехмерной декартовой системы координаты вершин определяются как (xi, yi, zi). Каждый объект однозначно определяется координатами собственных вершин. Вершина может моделировать отдельный точечный объект, размер которого не имеет значения, а также может использоваться в качестве конечных точек для линейных объектов и полигонов. Двумя вершинами задается вектор. Несколько векторов составляют полилинию. Полилиния может моделировать отдельный линейный объект, толщина которого не учитывается, а также может представлять контур полигона. Полигон моделирует площадный объект. Один полигон может описывать плоскую грань объемного объекта. Несколько граней составляют объемный объект в виде полигональной поверхности – многогранник или незамкнутую поверхность (в литературе часто используется название "полигональная сетка"). Векторную полигональную модель можно считать наиболее распространенной в современных системах трехмерной КГ. Она широко используется в САПР, ГИС, компьютерных тренажерах, играх и т.д. Положительные черты векторной полигональной модели: ● удобство масштабирования объектов. При увеличении или уменьшении объекты выглядят более качественно, чем при растровых моделях описания. Диапазон масштабирования определяется точностью аппроксимации и разрядностью чисел для представления координат вершин; ● небольшой объем данных для описания простых поверхностей, которые адекватно аппроксимируются плоскими гранями; ● необходимость вычислять только координаты вершин при преобразованиях систем координат или перемещении объектов; ● аппаратная поддержка многих операций в современных графических видеосистемах, которая обусловливает достаточно высокую скорость для анимации. Недостатки: ● сложность алгоритмов визуализации для создания реалистичных изображений; сложность алгоритмов выполнения топологических операций, таких, например, как разрезы; ● аппроксимация плоскими гранями приводит к погрешности моделирования. При моделировании поверхностей, которые имеют сложную фрактальную форму, обычно невозможно увеличивать число граней из-за ограничений по быстродействию и объему памяти компьютера. Воксельная модель Воксельная модель – это трехмерный растр. Подобно тому, как пикселы располагаются на плоскости двумерного изображения, вокселы образуют трехмерные объекты в определенном объеме. Воксел – это элемент объема (voxel – volume element). При создании двумерного изображения каждый пиксел должен иметь свой цвет. В воксельной модели каждый воксел также имеет свой цвет и, кроме того, прозрачность. Полная прозрачность воксела означает пустоту соответствующей точки объема. При моделировании объема каждый воксел представляет элемент объема определенного размера. Чем больше вокселов в определенном объеме и меньше размер вокселов, тем точнее моделируются трехмерные объекты – увеличивается разрешающая способность. В современной КГ воксельный метод считается одним из самых перспективных. Например, в медицине при сканировании томографом (computer tomography) получают изображения срезов объекта, которые потом объединяют в виде объемной модели для дальнейшего анализа. Воксельный метод используется в геологии, сейсмологии, в компьютерных играх, для графических устройств отображения, которые создают действительно объемные изображения. Положительная черта воксельной модели – простота: при описании сложных объектов и сцен; при отображении объемных сцен; при выполнении топологических операций над отдельными объектами и сценой в целом. Например, просто выполняется показ разреза – для этого соответствующие вокселы можно сделать прозрачными. Недостатки воксельной модели: ● большое количество информации, необходимой для представления объемных данных (например, объем 256х256х256 имеет небольшую разрешающую способность, но требует свыше 16 млн вокселов); ● значительные затраты памяти ограничивают разрешающую способность, точность моделирования; большое количество вокселов обусловливает малую скорость создания изображений объемных сцен; ● как и для любого растра, возникают проблемы при увеличении или уменьшении изображения. Например, при увеличении ухудшается качество изображения. Равномерная сетка Эта модель описывает координаты отдельных точек поверхности следующим способом. Каждому узлу сетки с индексами (i, j) приписывается значение высоты zij. Индексам (i, j) отвечают определенные значения координат (x, y). Расстояние между узлами одинаковое – dx по оси x, dy по оси y. Фактически такая модель – это двумерный массив, растр, матрица, каждый элемент которой сохраняет значение высоты. Не каждая поверхность может быть представлена этой моделью. Если в каждом узле (i, j) записывается только одно значение высоты, то это означает, что поверхность описывается однозначной функцией z = f (x, y). Иначе говоря, это такая поверхность, которую каждая вертикаль пересекает только один раз. Не могут моделироваться также вертикальные грани. Необходимо заметить, что сетка может быть задана не только в декартовых координатах. Например, для того чтобы описать поверхность шара однозначной функцией, можно использовать полярные координаты. С помощью равномерной сетки часто описывают рельеф земной поверхности. Положительные черты равномерной сетки: ● простота описания поверхностей; ● возможность быстро узнать высоту любой точки поверхности простой интерполяцией. Недостатки равномерной сетки: ● поверхности, которые соответствуют неоднозначной функции высоты в узлах сетки, не могут быть смоделированы; ● для описания сложных поверхностей необходимо большое количество узлов, которое может быть ограничено объемом памяти компьютера. Неравномерная сетка. Изолинии Неравномерной сеткой называется модель описания поверхности в виде множества отдельных точек {(x0, y0, z0), (x1, y1, z1), …,(xn-1, yn-1, zn-1)}, принадлежащих поверхности. Эти точки могут быть получены, например, в результате измерений поверхности какого-нибудь объекта с помощью определенного оборудования. Такую модель можно считать обобщением для некоторых рассмотренных выше моделей. Например, векторная полигональная модель и равномерная сетка могут считаться разновидностями неравномерной сетки. Рассмотрим модель поверхности в виде множества точечных значений, логически никак не связанных между собой. Неравномерность задания опорных точек усложняет определение координат для других точек поверхности, которые не совпадают с опорными точками. Требуются специальные методы пространственной интерполяции. Пусть задача заключается в вычислении значения координаты z по известным координатам (x, y). Для этого необходимо найти несколько самых близких точек, а затем вычислить искомое значение z, исходя из взаимного расположения этих точек в проекции (x, y). Для равномерной сетки эта задача решается достаточно просто – поиска фактически нет, сразу рассчитываются индексы самых близких опорных точек. Вторая задача заключается в отображении (визуализации) поверхности. Эту задачу можно решать несколькими способами. Один из наиболее распространенных – триангуляция. Процесс триангуляции может быть представлен следующим образом: ● находим первые три самые близкие друг к другу точки - получаем одну плоскую треугольную грань; ● находим точку, ближайшую к этой грани, и образовываем смежную грань, и т.д., пока не останется ни одной отдельной точки. Это – общая схема триангуляции. В литературе можно встретить множество алгоритмов триангуляции, сводящихся к описаному выше. Один из наиболее распространенных – триангуляция Делоне. Описание поверхности треугольными гранями можно уже считать разновидностью векторной полигональной модели. В англоязычной литературе для ее названия используется аббревиатура TIN (Triangulated Irregular Network). После триангуляции получаем полигональную поверхность, отображение которой выполнить уже достаточно просто. Рассмотрим еще один из вариантов описания поверхности – изолинии высоты. Любая изолиния состоит из точек, представляющих одно числовое значение какого-то показателя, в данном случае значение высоты. Изолинии высоты также можно рассматривать как контуры разреза поверхности горизонтальными плоскостями (поэтому для изолиний высоты часто применяется название "горизонтали"). Описание поверхности изолиниями высоты часто используется, например в картографии. Для описания поверхности можно использовать не только изолинии высоты, но и другие, например x- или y-изолинии. В компьютерных системах изолинии часто описываются векторно – полилиниями. Используются также изолинии в виде сплайновых кривых. Точки, составляющие изолинии, и отдельные опорные точки располагаются неравномерно. Это усложняет расчет координат точек поверхности. В графических компьютерных системах для выполнения многих операций, в первую очередь, для визуализации поверхности, обычно требуется преобразование описания поверхности из одной формы в другую. Преобразование изолиний в полигональную модель также выполняется методами триангуляции (здесь алгоритмы триангуляции сложнее, чем для триангуляции отдельных точек). Для преобразования неравномерной сетки в равномерную используют специальную интерполяцию. Положительные черты неравномерной сетки: ● использование отдельных опорных точек, наиболее важных для заданной формы поверхности, обусловливает меньший объем информации по сравнению с другими моделями, например с равномерной сеткой; ● применение изолиний на картах и планах позволяет наглядно отображать рельеф поверхности. Недостатки: ● невозможность или сложность выполнения многих операций над поверхностями; ● сложность алгоритмов преобразования в другие формы описания поверхностей. Моделирование объектов в системах КГ Основой моделирования объемных тел в трехмерном пространстве являются плоские многоугольники. Для трехмерных приложений главной характеристикой многоугольника является вовсе не число сторон, а его тип: выпуклый или вогнутый. Операции с выпуклыми многоугольниками происходят быстрее и проще. Для повышения скорости визуализации (рендеринга) на практике многоугольники разбивают на простейшие фигуры – треугольники, поскольку они обладают двумя важнейшими свойствами: всегда выпуклые и всегда плоские. Этот процесс получил название тесселяция сложных поверхностей (High Order Surface Tessellation). Многие программы трехмерной графики позволяют строить объемные модели на основе полиномиальных поверхностей (сплайнов) различного типа, описываемых набором контрольных точек, например поверхностей Безье. Вместе с тем такие поверхности являются исключительно "внутренним" делом программы, поскольку при выводе на экран они все равно должны быть разбиты на треугольники на одном из этапов визуализации. Таким образом, любой объект в трехмерной графике в конечном итоге предстает как совокупность треугольников. Треугольник описывается координатами вершин и вектором нормали к его поверхности. Многоугольники могут содержать треугольники с общими вершинами (так называемые ленты и веера треугольников), что значительно упрощает расчет трансформаций и освещения. Если вектор нормали направлен к плоскости визуализации, эта сторона объекта считается передней и проецируется на плоскость. В противном случае треугольник не отображается, так как считается невидимым. Операции трансформации объекта (изменение размеров, смещение, вращение) сводятся к расчету новых координат вершин треугольников по отдельности или в составе объединения (для общих вершин). Не вдаваясь в подробности, заметим, что расчеты выполняются достаточно просто на основе матричных преобразований. Присутствующий в трехмерной сцене объект отображается на экране только в том случае, если он попадает на плоскость визуализации, т.е. не закрыт другими объектами и не вышел из поля зрения. Лекция 15 Визуализация трехмерных изображений Проецирование трехмерных объектов на картинную плоскость Важнейшей операцией при визуализации трехмерной графики является проектирование, поскольку изображение строится на плоской поверхности экрана. Проектирование – это преобразование, ставящее в соответствие точкам трехмерного пространства точки на некоторой плоскости, называемой картинной. В компьютерной графике используются два основных вида проектирования: параллельное и перспективное. Параллельное проектирование (рис. 25) Пусть уравнение плоскости задано в виде nxx + nyy + nzz + d = 0, где x, y, z – координаты произвольной точки p этой плоскости. Уравнение плоскости может быть записано в виде скалярного произведения векторов: n=(nx, ny, nz) и p=(x, y, z): (n, p) + d = 0. Рассмотрим плоскость π: (n, p) + d = 0 в трехмерном пространстве, на которую будет осуществляться проектирование (картинную плоскость). Пусть задан вектор l, вдоль которого будет осуществляться проектирование. При этом будем считать, что (l, n) ≠ 0. Для нахождения проекции произвольной точки q на плоскость π проведем через точку q прямую с направляющим вектором l. Точка пересечения этой прямой с плоскостью π – qпр – является проекцией точки q на плоскость π вдоль направления l. Координаты произвольной точки q' прямой, проходящей через точку q и имеющей направляющий вектор l: q' = q + tl, tR. Тогда параметр t точки пересечения этой прямой и плоскости π можно найти, подставив уравнение прямой в уравнение плоскости: (q + tl, n) + d = 0. Отсюда получаем Зная t, можно найти проекцию точки q по формуле qпр = q + tl. Так как параллельное преобразование является аффинным, то его можно задать при помощи матрицы однородного преобразования. Приведем матрицу канонического параллельного проектирования, осуществляемого на плоскость Oxy вдоль оси Oz. Несмотря на свою простоту, параллельное проектирование обычно малоприменимо для визуализации сложных трехмерных сцен. Перспективное проектирование (рис. 26). Рассмотрим картинную плоскость π: (n, p) + d = 0 . Пусть задана точка c, которую будем называть центром проектирования. Тогда перспективной проекцией точки q назовем точку qпр пересечения плоскости π с лучом, выходящим из c и проходящим через q при условии, что точка q лежит в положительном полупространстве относительно плоскости π. Пусть проекцией точки q является точка qпр. В силу того, что qпр лежит на отрезке [q, c], справедлива формула qпр = (1 - t)c + tq, t  [0, 1]. Тогда из условия принадлежности проекции плоскости получаем Как видно из этой формулы, перспективное преобразование не является аффинным (принадлежит классу дробно-линейных преобразований). Тем не менее, его также можно записать при помощи матрицы однородного преобразования. Выпишем каноническое уравнение перспективного преобразования. Пусть центр проектирования равен (0, 0, -1)Т, а картинная плоскость задается уравнением z = 1. Тогда проекцией произвольной точки q = (x, y, z) будет точка qпр=(x/(z+1), y/(z+1), 1)2. Это преобразование осуществляется при помощи матрицы: поскольку Таким образом, как произвольное аффинное преобразование, так и параллельное и перспективное проектирование могут быть записаны при помощи матриц однородных преобразований. Уровни визуализации Любой объект, в том числе и объемный, может быть изображен различными способами. В одном случае необходимо показать внутреннюю структуру объекта, в другом – его внешнюю форму, в третьем – имитировать реальную действительность. Условно способы визуализации можно разделить по характеру изображений и по степени сложности соответствующих алгоритмов на уровни: 1) каркасная (проволочная) модель; 2) показ поверхностей в виде многоугольников с плоскими гранями или сплайнов с удалением невидимых точек; 3) показ поверхностей с использованием методов закрашивания объектов для имитации отражения света, затенения, прозрачности, наложения текстур. Простейшая каркасная модель часто применяется в процессе редактирования объемных объектов. Визуализация второго уровня используется для упрощенного показа объемных объектов. Например, для графиков функций z = f(x, y) (в виде рельефа поверхности) часто достаточно показать все грани сетки одним цветом, но при этом необходимо обязательно удалить невидимые точки. Это более сложная процедура по сравнению с выводом каркасного изображения. Сложность процесса графического вывода возрастает по мере приближения к некоторому идеалу для компьютерной графи-ки – создания иллюзии живых, реалистичных изображений. При создании реалистичных изображений учитываются законы оптики, описывающие свет и тень, отражение и преломление. Каркасная визуализация Каркас обычно состоит из отрезков прямых линий (соответствует многограннику), хотя можно строить его и на основе кривых, в частности сплайновых кривых Безье. Все ребра, показанные в окне вывода видны – как ближние, так и дальние. Для построения каркасного изображения необходимо: ● получить координаты всех вершин в мировой системе координат; ● преобразовать координаты каждой вершины в экранные координаты в соответствии с выбранной проекцией; ● выполнить цикл вывода в плоскости экрана всех ребер как отрезков прямых или кривых, соединяющих вершины. Показ с удалением невидимых точек. Классификация методов Одной из важнейших задач при визуализации сложных трехмерных сцен является определение того, какие части объектов (ребра, грани), находящихся в трехмерном пространстве, будут видны при заданном способе проектирования, а какие закрыты от наблюдателя другими объектами. В качестве возможных видов проектирования традиционно рассматривается параллельное и центральное (перспективное). Плоскость, на которую осуществляется проектирование, называют картинной. Задача удаления невидимых линий и поверхностей достаточно сложна и зачастую требует значительных объемов вычислений. Существует большое число различных методов решения этой задачи, включая и аппаратные. Эти методы различаются по следующим основным параметрам. 1. По способу представления объектов: ● аналитические (явные и неявные); ● параметрические; ● полигональные. 2. По способу визуализации сцены. При построении каркасных изображений (wireframe – рисуются только ребра) используются методы удаления невидимых линий (ребер каркасных изображений), для визуализации сплошных изображений (solid – рисуются закрашенные грани) – методы удаления невидимых поверхностей (граней сплошных изображе- ний). 3. По пространству, в котором производится анализ видимости: ● методы, работающие непосредственно в пространстве самих объектов; ● методы, работающие в пространстве картинной плоскости, т.е. работающие с проекциями объектов. 4. По виду получаемого результата (его точности): ● набор видимых областей или отрезков, заданный с машинной точностью (имеет непрерывный вид); ● информация о ближайшем объекте для каждого пиксела экрана (имеет дискретный вид). Методы первого класса дают точное решение задачи удаления невидимых линий и поверхностей, никак не привязанное к растровым свойствам картинной плоскости. Они могут работать как с самими объектами, выделяя те их части, которые видны, так и с их проекциями на картинную плоскость, выделяя на ней области, соответствующие проекциям видимых частей объектов, и, как правило, практически не привязаны к растровой решетке и свободны от погрешностей дискретизации. Так как эти методы работают с непрерывными исходными данными и получающиеся результаты не зависят от растровых свойств, то их иногда называют непрерывными (continuous methods). Простейший вариант непрерывного подхода заключается в сравнении каждого объекта со всеми остальными, что дает временные затраты, пропорциональные n2, где n – количество объектов в сцене. Однако следует иметь в виду, что непрерывные методы, как правило, достаточно сложны. Методы второго класса (point-sampling methods) дают приближенное решение задачи удаления невидимых линий, определяя видимость только в некотором наборе точек картинной плоскости – в точках растровой решетки. Они очень сильно привязаны к растровым свойствам картинной плоскости и фактически заключаются в определении для каждого пиксела той грани, которая является ближайшей к нему вдоль направления проектирования. Изменение разрешения приводит к необходимости полного перерасчета всего изображения. Простейший вариант дискретного метода имеет временные затраты порядка Cn, где C – общее количество пикселов экрана, n – число объектов. Всем методам второго класса традиционно свойственны ошибки дискретизации (aliasing artifacts). Однако, как правило, дискретные методы отличаются простотой реализации. Кроме этого существует довольно большое число смешанных методов, работающих как в объектном пространстве, так и в картинной плоскости, выполняющих часть работы с непрерывными данными, а часть с дискретными. Большинство алгоритмов удаления невидимых граней и поверхностей тесно связано с различными методами сортировки. Одни алгоритмы проводят сортировку явно, в других она присутствует в скрытом виде. Приближенные методы различаются фактически только порядком и способом проведения сортировки. Очень распространенной структурой данных в задачах удаления невидимых линий и поверхностей являются различные типы деревьев: двоичные (BSP-trees), четверичные (Quadtrees), восьмеричные (Octtrees) и др. Методы, применяющиеся в настоящее время, в большинстве являются комбинациями ряда оптимизированных простейших алгоритмов. Рассмотрим поверхности в виде многогранников или полигональных сеток. Для показа с удалением невидимых точек известны следующие методы: сортировка граней по глубине, метод плавающего горизонта, метод Z-буфера, алгоритм Робертса, алгоритм художника и др. Сортировка граней по глубине предполагает рисование полигонов и граней от самых дальних к самым близким. Он не является универсальным, поскольку иногда нельзя четко различить, какая грань ближе. Метод сортировки по глубине эффективен для показа поверхностей, заданных функциями z = f(x,y). Метод плавающего горизонта. Грани выводятся в последовательности от ближайших к самым дальним. На каждом шаге границы граней образуют две ломаные линии – верхний горизонт и нижний горизонт. Во время вывода каждой новой грани рисуется только то, что выше верхнего горизонта, и то, что ниже нижнего горизонта. Каждая новая грань поднимает верхний и опускает нижний горизонты. Этот метод часто используется для показа поверхностей, описываемых явным уравнением z = f (x, y). Метод Z-буфера основывается на использовании дополнительного массива, буфера в памяти, в котором сохраняются координаты точек Z для каждого пиксела растра. Координата Z соответствует расстоянию точек пространственных объектов до плоскости проецирования. Например, она может быть экранной координатой Z в системе экранных координат (X, Y, Z), если ось Z перпендикулярна плоскости экрана. Рассмотрим алгоритм рисования объектов по этому методу. Пусть чем ближе точка в пространстве к плоскости проецирования, тем больше значение Z: ● сначала Z-буфер заполняется минимальными значениями; ● затем начинается вывод всех объектов, причем порядок вывода объектов не имеет значения – для каждого объекта выводятся все его пикселы в любом порядке; ● во время вывода каждого пиксела по его координатам (X, Y) находится текущее значение Z в Z-буфере; ● если рисуемый пиксел имеет большее значение Z, чем значение в Z-буфере, то, следовательно, эта точка ближе к наблюдателю. В этом случае пиксел действительно рисуется, а его Z-координата записывается в Z-буфер. Таким образом, после рисования всех пикселов всех объектов растровое изображение будет состоять из пикселов, которые соответствуют точкам объектов с самыми большими значениями координат Z, т.е. видимые точки ближе всех к зрителю. Этот метод прост и эффективен благодаря тому, что не требует сортировки объектов или их точек. При рисовании объектов, которые описываются многогранниками или полигональными сетками, манипуляции со значениями Z-буфера легко совместить с выводом пикселов заполнения полигонов плоских граней. В настоящее время метод Z-буфера используется во многих графических 3d-акселераторах, которые аппаратно реализуют этот метод. Оптимально, если акселератор имеет собственную память для Z-буфера, доступ к которой осуществляется быстрее, чем к оперативной памяти компьютера. Возможности аппаратной реализации используются разработчиками и пользователями компьютерной анимации, позволяя достичь большой скорости прорисовки кадров. Алгоритм Робертса предназначен для построения выпуклых замкнутых поверхностей с плоскими гранями и выводит на экран только лицевые грани, обращенные внешней стороной к наблюдателю. Идентификация i-й грани заключается в оценке угла видимости i= Ni Si между векторами наблюдателя Si и внешней нормали Ni. Ячейка является лицевой при остром угле видимости, и это быстро определяется из условия Ni ◦ Si > 0 без вычисления самого угла. Порядок вывода лицевых граней произволен. Модификация алгоритма Робертса для невыпуклой поверхности заключается в присвоении каждой грани определенного приоритета вывода по правилу: чем внутреннее находится грань, тем выше у нее приоритет. В этой разновидности алгоритма Робертса также выводятся только лицевые грани, но теперь в порядке уменьшения приоритетов. Порядок вывода граней с равными приоритетами произволен. Данный метод обеспечивает корректное экранирование внутренних ячеек внешними при наложении их экранных проекций. Незамкнутая выпуклая каркасная поверхность также может быть изображена модифицированным методом Робертса, если внутренним сторонам ячеек присвоить высший приоритет и определять их видимость по правилу Ni ◦ Si < 0, где Ni – внешняя нормаль к плоскости i-й ячейки. Алгоритм художника предназначен для изображения произвольных поверхностей и выводит на экран все ячейки целиком по мере их приближения к наблюдателю. Проекции ближних граней могут частично или полностью наложиться на ранее построенные проекции дальних граней подобно тому, как художник наносит на холст один мазок поверх ранее нанесенного мазка, тем самым скрывая последний от зрителя. Метод основан на вычислении удаленности (глубины) di центров ячеек ci (в разных вариантах алгоритма используются и другие опорные точки ячеек) от наблюдателя, сортировке и выводе ячеек в порядке уменьшения элементов вектора d. При наблюдателе, находящемся в конечной точке S, глубина точки ci равна расстоянию di = | ci - S |, а в вычислительном аспекте более эффективно использовать квадрат расстояния как скалярное произведение: di2 = (ci - S) ◦ (ci - S). В случае наблюдателя, бесконечно удаленного в направлении вектора S, расстояния от него до всех точек также бесконечны. Впрочем, для сортировки можно использовать и относительные глубины, отсчитываемые вдоль любой оси d, противоположной направлению вектора S. Запишем проекцию точки ci на вектор S: Увеличение значения ti означает приближение точки ci к наблюдателю. Следовательно, в качестве эквивалента глубины, который должен уменьшаться с ростом ti, можно принять легко вычислимое скалярное произведение di = -ci ◦ S. Алгоритм художника отличается высоким быстродействием, но, к сожалению, имеет серьезный недостаток: ячейки каркаса должны быть примерно одинакового и достаточно малого размера по сравнению с габаритами поверхности. При определенном ракурсе разновеликие ячейки могут быть выведены на экран в неверном порядке. Общим недостатком алгоритма Робертса и алгоритма художника, которые выводят грани целиком, является невозможность правильного изображения двух пересекающихся ячеек, каждая из которых видна лишь частично. Лекция 16 Методы Гуро и Фонга для закрашивания поверхностей. Методы прямой и обратной трассировки лучей Закрашивание поверхностей Рассмотрим методы закрашивания объектов, моделируемых многогранниками и полигональными сетками. Они основаны на моделях отражения света. Зеркальное отражение. Угол между нормалью и падающим лучом равен углу между нормалью и отраженным лучом. Оба луча и нормаль располагаются в одной плоскости (рис. 27). Поверхность считается идеально зеркальной, если на ней отсутствуют какие-либо неровности, шероховатости. Собственного цвета такая поверхность не имеет. Световая энергия падающего луча отражается только по линии отраженного луча. Какое-либо рассеяние в стороны от этой линии отсутствует. В природе, вероятно, нет идеально гладких поверхностей, поэтому полагают, что если глубина шероховатостей существенно меньше длины волны излучения, то рассеяние не наблюдается. Для видимого спектра можно принять, что глубина шероховатостей поверхности зеркала должна быть существенно меньше 0,5 мкм. Если поверхность зеркала отполирована неидеально, то наблюдается зависимость интенсивности отраженного света от длины волны: чем больше длина волны, тем лучше отражение. Например, красные лучи отражаются сильнее, чем синие. При наличии шероховатостей имеется зависимость интенсивности отраженного света от угла падения. Отражение света максимально для углов падения луча, близких к 90°. Падающий луч, попадая на слегка шероховатую поверхность реального зеркала, порождает не один отраженный луч, а несколько лучей, рассеиваемых по различным направлениям. Зона рассеивания зависит от качества полировки и может быть описана некоторым законом распределения. Как правило, форма зоны рассеивания симметрична относительно линии идеального зеркально отраженного луча. К числу простейших, но достаточно часто используемых относится эмпирическая модель распределения Фонга, согласно которой интенсивность зеркально отраженного излучения пропорциональна (cos )p, где  – угол отклонения от линии идеально отраженного луча. Показатель p находится в диапазоне от 1 до 200 и зависит от качества полировки. Соотношение можно записать следующим образом: Is = I Ks cos p, где I – интенсивность излучения источника; Ks – коэффициент пропорциональности. Диффузное отражение. Этот вид отражения присущ матовым поверхностям. Матовой можно считать такую поверхность, размер шероховатостей которой уже настолько велик, что падающий луч рассеивается равномерно во все стороны. Диффузное отражение описывается законом Ламберта, согласно которому интенсивность отраженного света пропорциональна косинусу угла между направлением на точечный источник света и нормалью к поверхности: Id = I Kd cos , где I – интенсивность источника света; Kd – коэффициент, который учитывает свойства материала поверхности. Значение Kd находится в диапазоне от 0 до 1. Интенсивность отраженного света не зависит от расположения наблюдателя. Матовая поверхность имеет свой цвет. Наблюдаемый цвет определяется комбинацией собственного цвета поверхности и цвета излучения источника света. Поскольку в природе не существует идеально зеркальных или полностью матовых поверхностей, то при изображении объектов средствами КГ обычно моделируют сочетание зеркального и диффузного рассеивания в пропорции, характерной для конкретного материала. В этом случае модель отражения записывают в виде суммы диффузного и зеркального компонентов: Iотр = I (Kd cos  + Ks cos p), где константы Kd, Ks определяют отражательные свойства материала. Согласно этой формуле интенсивность отраженного света равна нулю для некоторых углов  и . Однако в реальных сценах обычно нет полностью затемненных объектов, следует учитывать фоновую подсветку, освещение рассеянным светом, отраженным от других объектов. В таком случае интенсивность может быть эмпирически выражена следующей формулой: Iотр = Ia Ka + I (Kd cos  + Ks cos p), где Ia – интенсивность рассеянного света, Ka – константа, определяющая рассеиваюшие свойства поверхности. Следует учесть тот факт, что энергия от точечного источника света уменьшается пропорционально квадрату расстояния. Использования такого правила вызывает определенные сложности, поэтому на практике часто реализуют модель, выражаемую эмпирической формулой Iотр = Ia Ka + I (Kd cos  + Ks cos p)/(R + k), где R – расстояние от центра проекции до поверхности, k – константа, подбираемая эмпирически. Определение цвета закрашивания точек объектов в соответствии с описанной моделью. Наиболее просто выполняется расчет в градациях серого цвета (например, для белого источника света и серых объектов). В данном случае интенсивность отраженного света соответствует яркости. Сложнее обстоит дело с цветными источниками света, освещающими цветные поверхности. Например, для модели RGB составляются три формулы расчета интенсивности отраженного света для различных цветовых компонентов. Коэффициенты Ka и Kd различны – они выражают собственный цвет поверхности. Поскольку цвет отраженного зеркального луча равен цвету источника, то коэффициент Ks будет одинаковым для всех компонентов цветовой модели. Цвет источника света выражается значениями интенсивности I для соответствующих цветовых компонентов. Метод Гуро Этот метод предназначен для создания иллюзии гладкой криволинейной поверхности, описанной в виде многогранников или полигональной сетки с плоскими гранями. Если каждая плоская грань имеет один постоянный цвет, определенный с учетом отражения, то различные цвета соседних граней очень заметны и поверхность выглядит именно как многогранник. Казалось бы, этот дефект можно замаскировать за счет увеличения числа граней при аппроксимации поверхности. Но зрение человека имеет способность подчеркивать перепады яркости на границах смежных граней – такой эффект называется эффектом полос Маха. Поэтому для создания иллюзии гладкости нужно намного увеличить число граней, что приводит к существенному замедлению визуализации – чем больше граней, тем меньше скорость рисования объектов. Метод Гуро основывается на идее закрашивания каждой плоской грани не одним цветом, а плавно изменяющимися оттенками, вычисляемыми путем интерполяции цветов примыкающих граней. Закрашивание граней по методу Гуро осуществляется в четыре этапа. 1. Вычисляются нормали к каждой грани. 2. Определяются нормали в вершинах. Нормаль в вершине определяется усреднением нормалей примыкающих граней (рис. 28). 3. На основе нормалей в вершинах вычисляются значения интенсивности в вершинах согласно выбранной модели отражения света. 4. Закрашиваются полигоны граней цветом, соответствующим линейной интерполяции значений интенсивности в вершинах. Вектор нормали в вершине (a) равен: Na = (N1 + N2 + N3) / 3. Интерполированные значения интенсивности отраженного света в каждой точке грани (и, следовательно, цвет каждого пиксела) удобно определять во время цикла заполнения полигона. Рассмотрим заполнение контура грани горизонталями в экранных координатах (рис. 29). Интерполированная интенсивность I в точке (X, Y) определяется исходя из пропорции (I - I1) / (X - X1) = (I2 - I1) / (X2 - X1). Отсюда I = I1 + (I2 - I1) (X - X1) / (X2 - X1). Значения интенсивностей I1 и I2 на концах горизонтального отрезка представляют собой интерполяцию интенсивности в вершинах: (I1 - Ib) / (Y - Yb) = (Ic - Ib) / (Yc - Yb) (I2 - Ib) / (Y - Yb) = (Ia - Ib) / (Ya - Yb) или I1 = Ib + (Ic - Ib) (Y - Yb) / (Yc - Yb) I2 = Ib + (Ia - Ib) (Y - Yb) / (Ya - Yb) Метод Фонга Метод Фонга аналогичен методу Гуро, но при его использовании для определения цвета в каждой точке интерполируются не интенсивности отраженного света, а векторы нормалей (рис. 30). 1. Определяются нормали к граням. 2. По нормалям к граням определяются нормали в вершинах. 3. В каждой точке закрашиваемой грани определяется интерполированный вектор нормали. 4. По направлению векторов нормали определяется цвет точек грани в соответствии с выбранной моделью отражения света. Рассмотрим, как можно получить вектор нормали в каждой точке грани. Для интерполяции будем оперировать векторами N'a, N'b и N'c, исходящими из центра координат плоскости проецирования и параллельными соответствующим нормалям Na, Nb и Nc в вершинах a, b и c. Сначала найдем N'1 и N'2: где XNa, YNa, ZNa, XNb, YNb, ZNb, XNc, YNc, ZNc – координаты векторов N'a, N'b и N'c. Теперь найдем координаты вектора N': Вектор N' параллелен вектору N для нормали в точке (X, Y), поэтому его можно использовать для расчета отражения света так же, как и вектор нормали N. Метод Фонга сложнее метода Гуро. Для каждой точки (пиксела) поверхности необходимо выполнять намного больше вычислительных операций (рис. 31). Тем не менее он дает значительно лучшие результаты, в особенности при имитации зеркальных поверхностей. Методы трассировки лучей Прямая трассировка. В методе прямой трассировки генерируется пучок лучей, выходящих из источника во всевозможных направлениях. Большинство лучей, испущенных источником, не попадает в приемник, а значит, и не влияет на формируемое в нем изображение. Лишь очень малая часть лучей после всех отражений и преломлений в конце концов попадает в приемник, создавая изображение сцены в его рецепторах. На шероховатых поверхностях возникает множество диффузно отраженных лучей. Все их нужно программно генерировать и отслеживать, что лавинообразно усложняет задачу трассировки. Прохождение луча в неидеальной среде сопровождается рассеянием и поглощением световой энергии на ее микрочастицах. Эти физические процессы чрезвычайно трудно адекватно моделировать на ЭВМ с ее конечными вычислительными ресурсами. На практике ограничиваются применением коэффициента затухания энергии луча на единицу пройденного им расстояния. Аналогично вводятся коэффициенты уменьшения энергии луча при его отражении и преломлении на поверхности раздела сред. С учетом этих коэффициентов отслеживается уменьшение энергии всех первичных и вторичных лучей в процессе их блуждания в пространстве сцены. Как только энергия некоторого луча становится меньше заданного абсолютного уровня или уменьшается в заданное число раз, трассировка данного луча прекращается. Таким образом, главными недостатками метода прямой трассировки являются его большая трудоемкость и малая эффективность. При реализации метода большая часть работы по расчету пересечений лучей с объектами оказывается проделанной впустую. Обратная трассировка. Метод обратной трассировки разработан в 80-х годах. Основополагающими считаются работы Уиттеда и Кея. Для отсекания лучей, не попавших в приемник, достаточно рассматривать наблюдателя в качестве источника обратных лучей. Первичным лучом будет считаться луч V от наблюдателя к какой-либо точке на поверхности объекта. По рассмотренным выше методикам рассчитываются вторичные, третичные и т.д. лучи. В результате для каждого первичного луча строится дерево трассировки, ветви которого составляют вторичные лучи. Ветвление трассы заканчивается, если: ● луч выходит за пределы сцены, ● луч встречается с непрозрачным телом, поглощающим свет, ● луч попадает в источник света, ● интенсивность луча падает ниже порога чувствительности, ● число расщеплений первичного луча становится слишком большим для имеющихся машинных ресурсов. Результирующая прямая световая энергия (цвет и интенсивность), попавшая в приемник из направления V, слагается из энергий терминальных вершин дерева с учетом их потерь при распространении в оптических средах. Метод обратной трассировки фактически аккумулирует все лучи, в действительности приходящие в приемник из определенного направления независимо от их начала. Это позволяет видеть и изображать на экране: ● непрозрачные объекты, поглощающие обратные лучи; ● прозрачные объекты, через которые благодаря преломлению наблюдателю видны другие объекты; ● отражения объектов на зеркальных поверхностях, в том числе и блики, соответствующие попаданию обратных лучей в источник света; ● тени, образующиеся в точках поверхности, заслоненных от источника другими объектами; ● другие разнообразные оптические эффекты. Количество "зондирующих" обратных лучей, подвергаемых трассировке, ограничено числом точек на поверхностях объектов сцены, видимых из точки расположения наблюдателя и перебираемых с конечным шагом, зависящим от разрешения экрана. Благодаря этому объем вычислительных затрат в методе обратной трассировки существенно уменьшается по сравнению с методом прямой трассировки. Возможно комбинирование обоих методов для оптимизации алгоритмов и снижения их трудоемкости. Алгоритмы трассировки носят характер рекурсивной процедуры, которая вызывает саму себя при появлении вторичного луча (анализируемый луч отражается или преломляется). Большая часть вычислений при реализации методов трассировки приходится на расчет пересечений лучей с поверхностями, в связи с чем они применяются для изображения оптических эффектов в сценах с небольшим числом объектов. При практической реализации метода обратной трассировки вводят нижеприведенные ограничения. Некоторые из них необходимы, чтобы можно было в принципе решить задачу синтеза изображения, а некоторые ограничения позволяют значительно повысить быстродействие трассировки. Ограничения метода обратной трассировки: 1. Среди всех типов объектов выделим источники света. Они могут только излучать свет, но не могут его отражать или преломлять. Обычно рассматриваются точечные источники. 2. Свойства отражающих поверхностей описываются суммой двух компонентов: диффузного и зеркального. 3. Зеркальность, в свою очередь, также описывается двумя составляющими. Первая (reflection) учитывает отражение от других объектов, не являющихся источниками света. Строится только один зеркально отраженный луч r для дальнейшей трассировки. Вторая компонента (specular) означает световые блики от источников света. Для этого направляются лучи на все источники определяются углы, образуемые этими лучами с зеркально отраженным лучом обратной трассировки (r). При зеркальном отражении цвет точки поверхности определяется цветом того, что отражается. В простейшем случае зеркало не имеет собственного цвета поверхности. 4. При диффузном отражении учитываются только лучи от источников света. Лучи от зеркально отражающих поверхностей игнорируются. Если луч, направленный на данный источник света, закрывается другим объектом, значит, данная точка объекта находится в тени. При диффузном отражении цвет освещенной точки поверхности определяется собственным цветом поверхности и цветом источников света. 5. Для прозрачных (transparent) объектов обычно не учитывается зависимость коэффициента преломления от длины волны. Иногда прозрачность вообще моделируют без преломления, т.е. направление преломленного луча t совпадает с направлением падающего луча. 6. Для учета освещенности объектов светом, рассеиваемым другими объектами, вводится фоновая составляющая (ambient). 7. Для завершения трассировки вводят некоторое пороговое значение освещенности, которое уже не должно вносить вклад в результирующий цвет, либо ограничивают число итераций. Положительные черты метода обратной трассировки: ● универсальность, применимость для синтеза изображений достаточно сложных пространственных сцен. Воплощает многие законы оптики. Просто реализуются разнообразные проекции; ● даже усеченные варианты данного метода позволяют получить достаточно реалистичные изображения. Например, если ограничиться только первичными лучами (из точки проецирования), то это дает удаление невидимых точек. Трассировка уже одного-двух вторичных лучей дает тени, зеркальность, прозрачность; ● все преобразования координат (если таковые есть) линейны, поэтому достаточно просто работать с текстурами; ● для одного пиксела растрового изображения можно трассировать несколько близко расположенных лучей, а потом усреднять их цвет для устранения эффекта ступенчатости; ● поскольку расчет отдельной точки изображения выполняется независимо от других точек, то это может быть эффективно использовано при реализации данного метода в параллельных вычислительных системах, в которых лучи могут трассироваться одновременно. Недостатки метода обратной трассировки: ● проблемы с моделированием диффузного отражения и преломления; ● для каждой точки изображения необходимо выполнять много вычислительных операций. Трассировка лучей относится к числу самых медленных алгоритмов синтеза изображений. Лекция 17 Формирование изображений средствами современных видеосистем. Графические интерфейсы и стандарты программирования графики Принципы формирования изображения на экране Дисплей персонального компьютера включает в себя экран с электронно-лучевой трубкой (Cathode Rate Tube, CRT), а также комплекс оптических и электронных средств, обеспечивающих формирование изображения. Изнутри экран монитора покрыт специальным веществом – люминофором, который освещается электронным лучом (потоком частиц, исходящих из электронной пушки). Каждый элемент люминофора состоит из трех точек разного цвета: красного, зеленого и синего. Свойства люминофора таковы, что он изменяет свою окраску и яркость при бомбардировке электронами и сохраняет этот цвет в течение некоторого времени (даже если луч на него уже не направлен). В результате соударения пучка электронов с поверхностью экрана, покрытой люминофором, образуется светящаяся точка - пиксел, причем интенсивность ее свечения зависит от энергии электронного пучка. Изменяя энергию пучка, можно получить различную яркость пиксела. Электронный луч обегает экран слева направо и сверху вниз с определенной скоростью, последовательно формируя множество пикселов, которые, сливаясь друг с другом, воспринимаются глазом как единое целое. Происходит это так быстро, что люминофор в первой зажженной точке не успевает "забыть" свой цвет даже к тому моменту, когда луч находится уже в самом дальнем от точки углу монитора. Физически луч начинает свое движение с левого верхнего угла экрана, прорисовывает самую верхнюю строку пикселов, затем переходит ко второй строке и т.д. Заканчивается маршрут в правом нижнем углу. Длительность прорисовки всего экрана определяется настройками видеоадаптера, точнее, частотой обновления экрана. При частоте обновления 120 Гц длительность прорисовки кадра равна 1/120 с. Вертикальная развертка и двойная буферизация Изображение на экране монитора формируется в специальной буферной памяти – видеопамяти. Схемы электронной развертки отображают построенное в видеопамяти изображение на экране. Программа может поместить нужное значение в видеопамять или прочитать из нее ранее установленное значение точно так, как это делается с обычной оперативной памятью. Если данные видеопамяти изменились в момент прорисовки кадра, то луч сначала "дорисовывает" кадр на основе старых данных и только при новом проходе отображает измененные данные. Вследствие этого возникают (хотя и кратковременные) дефекты изображения, так называемое "мерцание" экрана. Одно из решений этой проблемы заключается в том, чтобы обновлять данные видеопамяти в тот момент, когда луч находится в правом нижнем углу экрана, но это не всегда возможно. Поэтому применяется метод двойной буферизации (double buffering), который заключается в следующем. Создается невидимый "виртуальный" экран, и изображение рисуется только на нем. На основной экран содержимое виртуального экрана копируется в тот самый момент, когда луч находится в правом нижнем углу. Операция блокового копирования обычно производится очень быстро - для ее выполнения бывает достаточно даже сотой доли секунды. Любая современная библиотека (например, DirectX для Windows) позволяет переназначать указатель видеопамяти на любой виртуальный экран, и указанный экран становится основным. Тогда никакого копирования вообще не происходит и механизм работает очень быстро. В этом случае, если требуется внести изменения в изображение (например, передвинуть объект), нет необходимости стирать что-то и рисовать в новой позиции, новый кадр рисуется с нуля и копируется поверх предыдущего на основной экран. Таким образом, при использовании метода двойной буферизации каждый кадр накладывается на предыдущий, что позволяет получить плавную анимацию без эффекта мерцания. Архитектура современных видеосистем Видеопамять вместе с электронными схемами управления дисплеем располагается на одной печатной плате, которая называется дисплейным адаптером (видеокартой). Одной из наиболее важных характеристик видеокарты является размер размещенной на ней видеопамяти. От этого зависят такие важные параметры изображения, как количество пикселов по горизонтали и вертикали – разрешающая способность, а также количество цветов, которые могут одновременно отображаться на экране, - палитра. Видеопамять. Видеопамять персонального компьютера (VRAM - Video RAM) хранит растровое изображение, которое показывается на экране монитора. Изображение на мониторе полностью соответствует текущему содержанию видеопамяти. Видеопамять постоянно сканируется с частотой кадров монитора. Запись новых данных в видеопамять немедленно изменяет изображение на мониторе. Необходимый объем видеопамяти вычисляется как площадь экрана в пикселах, умноженная на количество бит (или байтов) на пиксел (установленный видеорежим). Наблюдается тенденция увеличения объемов видеопамяти соответственно увеличению разрешающей способности и глубины цвета видеосистем. В видеопамяти могут храниться несколько кадров изображения, что часто используется при анимации. Кроме того, в некоторых видеоадаптерах предусмотрена возможность использования видеопамяти для хранения другой информации, например Z-буфера, растров текстур. Физически видеопамять организована в виде одномерного вектора байтов в общем адресном пространстве. Как правило, адрес первого байта видеопамяти равен A000:0000 (сегмент: смещение) или A0000 (абсолютный адрес). Кроме физической организации видеопамяти следует учитывать ее логическую организацию, которая зависит от видеорежима. Например, в видеорежиме VGA (256 цветов, 320х200) используются четыре массива байтов памяти. Каждый массив назван битовой плоскостью, для каждого пиксела используются одинаковые биты данных различных плоскостей. Каждая битовая плоскость содержит 80 байтов в одной строке. Плоскости имеют одинаковый адрес в памяти, для доступа к отдельной плоскости необходимо устанавливать индекс плоскости в соответствующем регистре видеоадаптера. Подобный способ организации видеопамяти используется во многих других видеорежимах, он позволяет, например, быстро копировать массивы пикселов. Для сохранения нескольких кадров изображения в некоторых видеорежимах предусматриваются отдельные страницы видеопамяти с одинаковой логической организацией. Тогда можно изменять стартовый адрес видеопамяти – это приводит к сдвигу изображения на экране. Во всех графических видеорежимах стартовый адрес видеопамяти соответствует левому верхнему пикселу на экране. Поэтому координатная система с центром координат (0,0) в левом верхнем углу растра часто используется в качестве основной (или устанавливается по умолчанию) во многих графических интерфейсах программирования, наприме, в API Windows. Графический процессор. Современные видеоадаптеры представляют собой сложные электронные устройства. Кроме видеопамяти, на плате видеоадаптера (или видеокарты) располагается мощный специализированный графический процессор, который по сложности уже приближается к центральному процессору. Кроме визуализации содержимого видеопамяти графический процессор выполняет как относительно простые растровые операции: копирование массивов пикселов, манипуляции с цветами пикселов, так и более сложные. Там, где ранее использовался исключительно центральный процессор, в настоящее время все чаще применяется графический процессор видеоадаптера, например для выполнения операций графического вывода линий, полигонов. Первые графические процессоры видеоадаптеров выполняли преимущественно операции рисования плоских элементов. Современные графические процессоры выполняют уже много базовых операций 3D-графики, например, поддержку Z-буфера, наложение текстур и т.п. Видеоадаптер выполняет эти операции аппаратно, что позволяет намного ускорить их в сравнении с программной реализацией данных операций центральным процессором. Так появился термин графические акселераторы. Быстродействие таких видеоадаптеров часто измеряется в количестве графических элементов, которые рисуются за одну секунду. Современные графические акселераторы способны рисовать миллионы треугольников за секунду. Локальная шина. Вывод графики и особенно анимации требует очень высокой скорости передачи данных. Это требование учтено в архитектуре современных персональных компьютеров: контроллер видеосистемы (или видеоадаптер) располагается рядом с процессором и оперативной памятью и подключен к системной шине через скоростную локальную шину, что позволяет ускорить обмен данными между оперативной памятью и видеопамятью. Обмен данными по системной шине для видеосистемы обеспечивают процессор, видеоадаптер и контроллер локальной шины. До недавнего времени для подключения видеоадаптеров использовалась локальная шина PCI (Peripherical Component Interconnect local bus), которая является стандартом для подключения различных периферийных устройств. В настоящее время видеоадаптеры подключаются через локальную шину AGP (Accelerated Graphics Port), разработанную для повышения скорости обмена данными между видеоадаптером и оперативной памятью по сравнению с возможностями шины PCI. Шина AGP позволяет достичь большей частоты кадров при работе графических 3D-акселераторов. Высокая скорость обмена данных с оперативной памятью позволяет хранить растровые текстуры в оперативной памяти, а не в видеопамяти. Кроме того, использование AGP-порта снижает нагрузку на шину PCI, что повышает быстродействие компьютера. Графические видеорежимы. Эволюция видеоадаптеров. Видеоадаптеры позволяют выводить информацию на экран в текстовом и графическом режимах. В текстовом режиме возможности адаптера характеризуются числом строк на экране и числом символов в строке. Графический режим определяется размером растра и глубиной цвета (количеством одновременно выводимых на экран цветов). Перечислим наиболее распространенные виды видеоадаптеров: MDA(Monochrom display Adapter) предназначен для работы в текстовом режиме 25 строк по 80 символов в строке. Hercules Grapphic Card поддерживал, помимо текстового, графический черно-белый режим 720х348 пикселов. CGA(Color Graphic Adapter) позволял работать в цветном текстовом или графическом режимах. Два графических режима: черно-белый 640х200 пикселов и цветной 320х200 пикселов. В цветном режиме можно было отображать только четыре цвета одновременно (глубина цвета 2 бита на пиксел). EGA(Enchanced Graphic Adapter) поддерживал 16-цветный графический видеорежим 640х350 пикселов, цвета выбирались из палитры 64 цветов. Главным недостатком этого режима была различная разрешающая способность по горизонтали и вертикали, т.е. пикселы имели прямоугольную форму (круг выглядел овалом). MCGA (Multi-Color Graphic Array) и VGA(Video Graphic Array) обеспечивали 256-цветные видеорежимы. Адаптер VGA имеет два видеорежима: 1) 256-цветный графический видеорежим с размерами растра 320х200, цвета можно выбирать из палитры в 256 тысяч цветов, пикселы прямоугольной формы; 2) 16-цветный видеорежим 640х480, пикселы квадратные. SuperVGA поддерживают графические видеорежимы: 16-цветные 800х600 и 1024х768; 640х480, 800х600 и более для 256 цветов. Targa24 - первый видеоадаптер с глубиной цвета в 24 бита, что позволило получить цветовой видеорежим True Color. На современных компьютерах с процессорами класса Pentium используются различные видеоадаптеры растрового типа, позволяющие устанавливать глубину цвета до 32 бит на пиксел при размерах растра 1600х1200 и более. Существуют стандарты на видеорежимы, установленные VESA (Video Electronic Standards Association). Видеоадаптеры могут различаться не только по быстродействию и возможностям для работы с цветом, но и по уровню реализации тех или иных графических операций. Например, видеоадаптеры Matrox позволяют создавать качественную двумерную графику, Nvidia GeForce считаются удачными игровыми 3D-акселераторами, а видеоадаптеры 3Dlabs Wildcat могут использоваться для профессионального 3D-моделирования. Использование программистами графических возможностей видеосистемы может осуществляться на различных уровнях. 1. Использование возможностей BIOS для выполнения простейших операций, таких как определение графического видеорежима, вывода пикселов на экран и др. 2. Использование функций операционной системы. Раз-личные операционные системы предоставляют в этом плане различные возможности: в MS-DOS практически нет графических функций, но программист имеет свободный доступ ко всем аппаратным ресурсам компьютера, в том числе и непосредственный доступ к видеопамяти; операционная система Windows запрещает прикладным программам непосредственный доступ к аппаратным ресурсам, но содержит несколько сотен графических функций – интерфейс API (Application Program Interface). 3. Использование специализированных графических интер-фейсов и библиотек, которые поддерживают аппаратные возможности современных графических процессоров. Современные стандарты и интерфейсы программирования компьютерной графики Одним из наиболее известных графических интерфейсов является OpenGL. Этот интерфейс в виде библиотеки графических функций представляет собой открытый стандарт, разработанный и утвержденный в 1992 г. девятью фирмами, среди которых были Digital Equipment Corp., Evans & Sutherland, Hewlett Packard Co., IBM Corp., Intel Corp., Silicon Graphics Inc., Sun Microsystems и Microsoft. В основу стандарта легла библиотека IRIS GL, разработанная фирмой Silicon Graphics Inc. Этот стандарт поддерживается многими операционными системами (в том числе и Windows), а также производителями графических акселераторов. Другим известным графическим интерфейсом является DirectX с подсистемой трехмерной графики Direct3D, а также подсистемой DirectDraw, которая обеспечивает, в частности, непосредственный доступ к видеопамяти. Этот интерфейс разработан Microsoft и предназначен только для Windows. В отличие от OpenGL, который сразу разрабатывался для функционирования с графическими ускорителями, Direct3D был изначально ориентирован на программный рендеринг. Кроме того, Direct3D фактически не является стандартом в строгом смысле этого слова – это лишь некоторый интерфейс, объявленный и полностью контролируемый компанией Microsoft. Известны также другие разработки графических интерфейсов для видеоадаптеров. Например, интерфейс Glide, разработанный 3Dfx для графических видеоадаптеров семейства Voodoo (следует заметить, что компания 3Dfx недавно прекратила свое существование как изготовитель видеоадаптеров). OpenGL. Современные графические ускорители (видеоадаптеры) обладают большим набором возможностей и высокой производительностью, но при этом они часто имеют и серьезные внутренние различия. Для того чтобы эффективно работать с такими ускорителями, не привязываясь к особенностям какого-либо конкретного устройства, обычно применяются библиотеки, предоставляющие некоторый унифицированный интерфейс к нему. На сегодняшний день для персональных компьютеров существует два таких интерфейса: OpenGL, уже более 10 лет являющийся стандартом, и Direct3D, предложенный и поддерживаемый компанией Microsoft. OpenGL представляет собой открытый процедурный интерфейс к видеоадаптеру, позволяющий легко задавать объекты в пространстве и операции над ними. С самого начала OpenGL разрабатывался как эффективный, аппаратно- и платформенно-независимый интерфейс. Он не включает в себя специальных команд, привязанных к какой-либо конкретной операционной системе. Для выполнения операций работы с окнами и организации ввода-вывода существуют дополнительные библиотеки. Библиотека OpenGL позволяет легко создавать объекты из геометрических примитивов (точек, линий, граней), располагать их в трехмерном пространстве, выбирать способ и параметры проектирования, вычислять цвета пикселов с использованием текстур и источников света. Поскольку OpenGL разрабатывался как открытый стандарт, то производители видеоадаптеров легко могут добавлять в него свои функции, реализующие дополнительные возможности. Работа с OpenGL основывается на модели клиент-сервер. Приложение выступает в роли клиента - оно генерирует команды, а сервер OpenGL выполняет их. Библиотека OpenGL поддерживает различные палитровые режимы, позволяет работать в режимах непосредственного задания цвета High Color и True Color. Для облегчения работы с OpenGL, и в частности работы с окнами и вводом, удобно использовать библиотеку glut. Эта кросс-платформенная библиотека позволяет легко создавать переносимые приложения, использующие OpenGL. Библиотека glut (OpenGL Utility Toolkit) является прозрачным интерфейсом для написания переносимых программ, использующих OpenGL и взаимодействующих с оконной системой. Она позволяет писать программы на ряде языков, включая C++, Delphi. Для рисования геометрических объектов OpenGL организует несколько буферов: буфер изображения (фрейм-буфер), буфер глубины (z-буфер), буфер трафарета и аккумулирующий буфер. Библиотека OpenGL может выводить точки, линии, полигоны и битовые изображения. Под линией в OpenGL понимается отрезок, заданный своими начальной и конечной вершинами. Под гранью (многоугольником) подразумевается замкнутый выпуклый многоугольник с несамопересекающейся границей. Все геометрические примитивы задаются в терминах вершин. Каждая вершина задается набором чисел. OpenGL работает с однородными координатами (x, y, z, w). Если координата z не задана, то она полагается равной 0. Если координата w не задана, то она полагается равной единице. В процессе построения изображения координаты вершин подвергаются различным преобразованиям (видовым, проектирования, перспективного деления и др.). В OpenGL существуют две матрицы для преобразования координат точки: матрица моделирования (modelview matrix) и матрица проектирования (projection matrix). Первая служит для задания положения объекта и его ориентации, а вторая отвечает за выбранный способ проектирования. Кроме того, существует матрица преобразования текстурных координат (texture matrix). Имеется набор различных процедур, умножающих текущую матрицу (моделирования или проектирования) на матрицу выбранного геометрического преобразования. Если последовательно указано несколько преобразований, то в результате текущая матрица будет последовательно умножена на матрицы соответствующих преобразований. Чтобы задаваемые объекты могли быть нарисованы, необходимо задать способ проектирования. Преобразование проектирования определяет, как объекты будут проецироваться на экран и какие части объектов будут отсечены как не попадающие в поле зрения. OpenGL поддерживает два вида проектирования: параллельное и перспективное. Поле зрения при перспективном преобразовании является усеченной пирамидой. В случае параллельного проектирования полем зрения является прямоугольный параллелепипед. OpenGL поддерживает модель освещенности, в которой свет приходит из нескольких источников, которые по отдельности могут быть включены или выключены. Кроме того существует еще и общее фоновое освещение (ambient). Для правильного освещения объектов необходимо для каждой грани задать материал, обладающий определенными свойствами. Материал может испускать свой собственный свет, рассеивать падающий свет во всех направлениях (диффузное отражение) или отражать свет в определенных направлениях подобно зеркалу. Пользователь может определить до восьми источников света, каждый со своими свойствами (цвет, расположение, направление). Линия или заполненная грань может быть нарисована одним цветом (плоское закрашивание) или путем интерполяции цветов в вершинах (закрашивание методом Гуро). Текстурирование позволяет наложить изображение на многоугольник и вывести этот многоугольник с наложенной на него текстурой, преобразованной соответствующим образом. OpenGL поддерживает одно- и двухмерные текстуры и различные способы их наложения. П р и л о ж е н и е 1 Наиболее распространенные форматы графических файлов BMP (Windows Device Independent Bitmap) – Наиболее распространенный формат файлов для растровых изображений в системе Windows. В файле этого формата сначала записывается палитра, если она есть, а затем растр в виде битового (а точнее, байтового) массива. В битовом массиве последовательно записываются байты строк растра. Число байтов в строке должно быть кратно четырем, поэтому если количество пикселов по горизонтали не соответствует такому условию, то справа в каждую строку дописывается некоторое число битов (выравнивание строк на границу двойного слова). Формат служит для обмена растровыми изображениями между приложениями ОС Windows. Формат поддерживает большинство цветовых моделей, вплоть до 24-битного пространства RGB. Полиграфический стандарт CMYK не поддерживается. В качестве алгоритма сжатия применяется RLE (Run Length Encoding) - компрессия без потери информации. Сфера применения - электронные публикации. Файлы в данном формате занимают значительный объем, для них характерно низкое качество изображений, выводимых на печать. GIF (CompuServeGraphics Interchange Format). Разработан в 1987 г. фирмой CompuServ для представления в Интернете графики, "независимой" от аппаратного обеспечения. Модернизирован в 1989 г. (версия GIF89a). Формат поддерживает функции прозрачности цветов и некоторые виды анимации. Запись изображения происходит через строку, т.е. полукадрами, аналогично телевизионной системе развертки. Благодаря этому на экране сначала появляется картинка в низком разрешении, позволяющая представить общий образ, а затем загружаются остальные строки. Этот формат поддерживает 256 цветов. Один из цветов может получить свойство прозрачности благодаря наличию дополнительного двухбитового альфа-канала. Допускается включение в файл нескольких растровых изображений, воспроизводимых с заданной периодичностью, что обеспечивает демонстрацию на экране простейшей анимации. Все данные в файле сжимаются методом Lempel-Ziv-Welch (LZW) без потери качества, что дает наилучшие результаты на участках с однородной заливкой. PNG (Portable Network Graphics). Появился как альтернатива устаревающему GIF. Формат также основан на дискретной записи, однако, не только по строкам, но и по столбцам. Метод восстановления изображения на экране остался прежним. Глубина цветового охвата возросла до 48 бит. Альфа-канал поддерживает 8-битную градацию яркости (256 уровней), что позволило применять эффекты неполной прозрачности. Абсолютно новой функцией стала запись в файл информации о гамма-коррекции, т.е. поддержания одинакового уровня яркости изображения независимо от особенностей представления цвета в различных операционных системах и приложениях. Сохранилась возможность подкачки растровых изображений для создания анимации. Применен усовершенствованный метод сжатия без потери информации Deflate, принципиально схожий с LZW. Новый метод сжатия позволил сократить объем файлов. JPEG (Joint Photographic Expert Group). По существу является методом сжатия изображений с потерей части информации. Традиционно файлы с расширением jpg считают записанными в данном формате, хотя и другие форматы поддерживают сжатие методом JPEG. Преобразование данных при записи происходит в несколько этапов. Независимо от исходной цветовой модели изображения все пикселы переводятся в цветовое пространство CIE LAB. Затем отбрасывается не менее половины информации о цвете, спектр сужается до палитры, ориентированной на особенности человеческого зрения. Далее изображение разбивается на блоки размером 8х8 пикселов. В каждом блоке сначала кодируется информация о "среднем" цвете пикселов, а затем описывается разница между "средним" цветом блока и цветом конкретного пиксела. Очевидно, что крупные элементы изображения будут представлены меньшим набором чисел, чем мелкие. На этом основан принцип действий на следующем этапе: выбранный уровень качества определяет сохранность мелких элементов. Чем ниже уровень качества, тем более крупные элементы "выбрасываются" из картинки. На последнем этапе кодовая последовательность сжимается методом Хафмана. Применение компрессии JPEG позволяет до 500 раз уменьшить объем файла по сравнению с обычным bitmap. Вместе с тем искажение цветовой модели и деградация деталей не позволяют использовать этот формат для хранения изображений высокого качества. Обычно используется для электронных публикаций. PCD (PhotoCD - Image Pac). Разработан фирмой Kodak для хранения цифровых растровых изображений высокого качества. Файл имеет внутреннюю структуру, обеспечивающую хранение изображения с фиксированными величинами разрешений, и поэтому размеры любых файлов лишь незначительно отличаются друг от друга и находятся в диапазоне 4-5 Мбайт. Каждому разрешению присвоен собственный уровень, отсчитываемый от так называемого базового (Base), составляющего 512х768 точек. Всего в файле пять уровней – от Base/16 (128х192 точек) до Base*16 (2048х3072 точек). При первичном сжатии исходного изображения применяется метод субдискретизации, практически без потери качества. Затем вычисляются разности Base-Base*4 и Base*4-Base*16. Итоговый результат записывается в файл. Чтобы воспроизвести информацию с высоким разрешением, производится обратное преобразование. Для хранения информации о цвете использована модель YCC. Обеспечивает высокое качество полутоновых изображений. PCX (PC Paintbrush File Format). Растровый формат. Впервые появился в программе PC Paintbrush для MS-DOS. После лицензирования программы Paintbrush для Windows стал использоваться рядом приложений Windows. TGA (TarGa Image File). Растровый формат. Используется для работы с видео- и фотоизображениями. Разработан компанией Truevision при создании графических адаптеров Targa,Vista, NuVista для компьютеров PC и Macintosh. TIFF (Tagged Image File Format). Считается лучшим форматом для записи полутоновых изображений. Популярность формата объясняется его широкими возможностями: поддержка множества цветовых моделей, наличие 8-битного альфа-канала, сохранение обтравочных контуров, различные алгоритмы сжатия без потери информации. Формат распознается практически всеми графическими программами и позволяет хранить изображения высочайшего качества. Последние версии формата поддерживают несколько способов сжатия изображений: LZW (без потери информации), ZIP (без потери информации), JPEG (с потерей части информации). Универсальным считают метод сжатия LZW. WMF (Windows MetaFile). Является "внутренним" форматом ОС Windows на платформе IBM PC. Изначально предназначен для обмена векторными данными между приложениями через буфер обмена. Однако "универсальность" сослужила ему плохую службу, поскольку не все программы умеют правильно обрабатывать его код. Типичными ошибками при переносе изображений являются искажения цветов, неправильная установка толщины контуров и свойств заливки, непонимание многих параметров объектов, заданных в векторных редакторах. Кроме того, в формат WMF нельзя включить растровое изображение. Таким образом, хранить что-либо ценное в данном формате не рекомендуется, а перенос векторной графики между приложениями возможен лишь для самых простых объектов. AI. Формат графических файлов векторного редактора Adobe Illustrator. Практически полностью совместим с EPS. CDR (CorelDraw). Векторный формат. Рабочий формат графического пакета CorelDraw. PS (PostScript). Строго говоря является языком описания страниц, разработанным фирмой Adobe для лазерных устройств вывода. Файл с расширением ps содержит команды, позволяющие печатному устройству, оснащенному интерпретатором PostScript, верно вывести графику и текст любой сложности. Файл включает сам документ, все связанные с ним растровые и векторные файлы, используемые шрифты, информацию о цветовой модели, параметрах цветоделения, линиатуре растра, форме растровой точки и другие данные, необходимые устройству вывода. Не каждое приложение способно сгенерировать правильный код PostScript. Наилучшие результаты дают программы Adobe: Illustrator, Photoshop, PageMaker, InDesign, последние версии Corel Draw. EPS (Encapsulated PostScript). Является форматом, поддерживающим упрощенную версию PostScript. Используется в профессиональной среде компьютерного дизайна, при допечатной подготовке. Не поддерживает многостраничные документы, не содержит ряд команд управления параметрами устройства вывода.Сохраняет все необходимые данные о свойствах самого изображения, цветовая модель, канал прозрачности, обтравочный контур, треппинг (перекрытие цветов на границах), внедренные шрифты, параметры внедренной растровой картинки. Специальный раздел в файле EPS выделен под заголовок, который представляет собой растровый образ (эскиз) документа. Открыть файл EPS для просмотра и редактирования способны немногие программы, в частности Adobe Illustrator и CorelDraw. PDF (Portable Document Format). Переносимый формат представления документов. Является развитием языка PostScript в направлении интерактивной работы. Если PostScript изначально создавался как язык выводных устройств, то целью создания PDF была задача разработки единого формата, как для электронных публикаций, так и для вывода на печать. Формат позволяет включать в документ мультимедийные расширения (звук, видео), создавать диалоговые экранные формы, поддерживает гиперссылки, как внутри одного документа, так и между документами. П р и л о ж е н и е 2 Тексты программ для построения фрактальных изображений Программа для построения фрактала Мандельброта Program fr_mandelbrot; uses crt,graph; const mi=511; var gd,gm:integer; function c(index:integer):integer; {определение цвета точки} begin c:=1*(mi-index) end; {** функция подсчета количества итераций **} function iteration(x,y:double):integer; var i:integer; xx,yy,xk,yk:double; begin xx:=x; yy:=y; i:=0; while (sqr(xx)+sqr(yy)<=4) do begin xk:=sqr(xx)-sqr(yy)+x; yk:=2*xx*yy+y; xx:=xk; yy:=yk; i:=i+1; if i>=mi then break end; iteration:=i; end; {*** процедура формирования фрактала ***} procedure mand(xx,yy,cx,cy:integer; minx,maxx,miny,maxy:double); var stepx, stepy,x,y:double; i,j,iter:integer; begin stepx:=(maxx-minx)/cx; stepy:=(maxy-miny)/cy; y:=miny; for j:=0 to cy do begin x:=minx; for i:=0 to cx do begin iter:=iteration(x,y); putpixel(xx+i,yy+j,c(iter)); x:=x+stepx; end; y:=y+stepy end; end; begin gd:=Detect; initgraph(gd,gm,'C:\BP\BGI'); setBkcolor(1); {формирование фрактала с разной степенью детализации} mand(0,0,640,480,-2.2,1,-1.2,1.2); {весь фрактал} readkey; cleardevice; {увеличенные фрагменты фрактала} mand(0,0,640,480,-0.85,-0.7,0.1,0.25); readkey; cleardevice; mand(0,0,640,480,-0.8,-0.7,0.2,0.3); readkey; cleardevice; mand(0,0,640,480,-1.25,-1,-0.5,-0.25); readkey; cleardevice; mand(0,0,640,480,-1.05,-1,-0.35,-0.3); readkey; closegraph; end. Программа для построения фрактала Джулиа Program fr_Julia; uses crt,graph; const mi=511; var gd,gm:integer; function c(index:integer):integer; {определение цвета точки} begin c:=7*(mi-index) end; {** функция подсчета количества итераций **} function iteration(x,y:double):integer; const cx=0.36;cy=0.36; var i:integer; xx,yy,xk,yk:double; begin xx:=x; yy:=y; i:=0; while (sqr(xx)+sqr(yy)<=4) do begin xk:=sqr(xx)-sqr(yy)+cx; yk:=2*xx*yy+cy; xx:=xk; yy:=yk; i:=i+1; if i>=mi then break end; iteration:=i; end; {*** процедура формирования фрактала ***} procedure julia(xx,yy,cx,cy:integer; minx,maxx,miny,maxy:double); var stepx, stepy,x,y:double; i,j,iter:integer; begin stepx:=(maxx-minx)/cx; stepy:=(maxy-miny)/cy; y:=miny; for j:=0 to cy do begin x:=minx; for i:=0 to cx do begin iter:=iteration(x,y); putpixel(xx+i,yy+j,c(iter)); x:=x+stepx; end; y:=y+stepy end; end; begin gd:=Detect; initgraph(gd,gm,'C:\BP\BGI'); setBkcolor(1); {формирование фрактала с разной степенью детализации} julia(0,0,640,480,-1,1,-1.2,1.2); {весь фрактал} readkey; cleardevice; {увеличенные фрагменты фрактала} julia(0,0,640,480,-0.1,0.1,-0.1,0.1); readkey; cleardevice; julia(0,0,640,480,-1,0,-1.2,0); readkey; cleardevice; julia(0,0,640,480,-1,-0.5,-0.5,0); readkey; cleardevice; julia(0,0,640,480,-0.75,-0.06,-0.5,-0.35); readkey; cleardevice; julia(0,0,640,480,-0.68,-0.65,-0.37,-0.36); readkey; closegraph; end. Программа для построения фрактала Кох Program fr_kox; uses graph,crt; var x0,y0,x,y,gd,gm:integer;x1,y1:real; {*** рекурсивная процедура построения линии Коха ***} procedure kox(xn,yn,xk,yk:real); var x2,y2,x3,y3,x4,y4:real; c:char; begin if abs(xn-xk)<2 then exit; x2:=xn+(xk-xn)/3; y2:=yn+(yk-yn)/3; x3:=xn+(xk-xn)*2/3; y3:=yn+(yk-yn)*2/3; x4:=x2+(x3-x2)*cos(pi/3)+(y3-y2)*sin(pi/3); y4:=y2-(x3-x2)*sin(pi/3)+(y3-y2)*cos(pi/3); line(round(x2),round(y2),round(x4),round(y4)); line(round(x3),round(y3),round(x4),round(y4)); if keypressed then halt; kox(xn,yn,x2,y2); {рекурсивные вызовы} kox(x2,y2,x4,y4); kox(x4,y4,x3,y3); kox(x3,y3,xk,yk); end; begin x0:=50; y0:=250; x:=590; y:=250; gd:=Detect; initgraph(gd,gm,'C:\BP\BGI'); setcolor(10); line(x0,y0,x,y); kox(x0,y0,x,y); {Рисование фрактала - линии Коха} readkey; cleardevice; {Рисование фрактального треугольника с использованием} {процедуры для построения линии Коха} x0:=150; y0:=320; x:=490; y:=320; x1:=x0+(x-x0)*cos(pi/3)+(y-y0)*sin(pi/3); y1:=y0-(x-x0)*sin(pi/3)+(y-y0)*cos(pi/3); kox(x0,y0,x1,y1); kox(x1,y1,x,y); kox(x,y,x0,y0); readkey; closegraph end. Программа для построения ветки папоротника Program fr_paporotnik; uses crt, graph; const alfa=80;beta=2.1; k=0.3; k1=0.5; lmin=1; var a,b,c,d,e,f,g,h:real; gd,gm:integer; {*** рекурсивная процедура на основе метода IFS ***} procedure step(x1,y1,x2,y2:real; nom:integer); var x3,y3,x4,y4,x5,y5,x6,y6,x7,y7:real; begin if sqr(x1-x2)+sqr(y1-y2)>lmin then begin {координаты точек вычисляются по формулам} x3:=(x2-x1)*a-(y2-y1)*b+x1; y3:=(x2-x1)*b+(y2-y1)*a+y1; x4:=x1*c+x3*d; y4:=y1*c+y3*d; x5:=x4*e+x3*f; y5:=y4*e+y3*f; x6:=(x5-x4)*g-(y5-y4)*h+x4; y6:=(x5-x4)*h+(y5-y4)*g+y4; x7:=(x5-x4)*g+(y5-y4)*h+x4; y7:=(x5-x4)*(-h)+(y5-y4)*g+y4; line(round(x1),round(y1),round(x4),round(y4)); {рекурсивные вызовы для рисования фрагментов фрактала} step(x4,y4,x3,y3,nom); step(x4,y4,x6,y6,nom+1); step(x4,y4,x7,y7,nom+1); end; end; begin gd:=Detect; initgraph(gd,gm,'C:\BP\BGI'); setBkcolor(1); {вычисление коэффициентов} a:=cos(pi/alfa); b:=sin(pi/alfa); c:=1-k; d:=k; e:=1-k1; f:=k1; g:=cos(pi/beta); h:=sin(pi/beta); step(200,350,225,70,0); {рисование ветки папоротника} readkey; closegraph end. Программа построения треугольника Серпинского program fr_treug_serpinsky; uses graph,crt; const m=2500; { количество точек фрактала } type koord=array[1..3] of integer; var gd,gm: integer; x,y: koord; { массивы координат } {**** Процедура заполнения заданного треугольника точками ****} procedure serpinsky(xs,ys:koord); var x0,y0,xk,yk: real; n,k: integer; begin randomize; x0:=(xs[1]+xs[2]+xs[3])/3; { координаты начальной точки } y0:=(ys[1]+ys[2]+ys[3])/3; for k:=1 to m do begin n:=random(3)+1; { случайная вершина } xk:=(x0+xs[n])/2; { середина отрезка, соединяющего } yk:=(y0+ys[n])/2; { начальную точку с вершиной } putpixel(round(xk), round(yk), 12); { вывод точки } x0:=xk; { новые координаты для начальной точки } y0:=yk end; end; begin gd:=Detect; initgraph(gd,gm,'C:\BP\BGI'); setcolor(10); setviewport(20,20,500,250, true); x[1]:=320; y[1]:=50; { координаты вершин треугольника } x[2]:=150; y[2]:=200; x[3]:=450; y[3]:=200; serpinsky(x,y); { процедура вывода треугольника Серпинского } readkey; closegraph end. Библиографический список 1. Бордман Т. 3DS Max 5: Учебный курс. СПб., Питер, 2004. 2. Боресков А.В. Графика трехмерной компьютерной игры на основе OpenGL. М.: ДИАЛОГ-МИФИ, 2004. 3. Голованов Н.Н. Геометрическое моделирование. М.: Изд-во физ.-мат. лит-ры, 2002. 4. Костельцев А.В. GTK+. Разработка переносимых графических интерфейсов. СПб.: БХВ-Петербург, 2002. 5. Костюкова Н.И. Введение в компьютерную графику: Методические рекомендации. Новосибирск: Сиб. университетское изд-во, 2003. 6. Литвиненко Н.Ю. Построение графиков в Excel: тонкости. М.: Солон-Пресс, 2003. 7. Мозговой М.В. Занимательное программирование: Самоучитель. СПб.: Питер, 2004. 8. Мураховский В.И. Компьютерная графика / Под ред. С.В.Симоновича. М.: АСТ-Пресс, 2002. 9. Никулин Е.А. Компьютерная геометрия и алгоритмы машинной графики. СПб.: БХВ-Петербург, 2003. 10. Пекарев Л. Самоучитель 3DS Max 5. Спб.: БХВ, 2003. 11. Петров М.Н., Молочков В.П.. Компьютерная графика. СПб., "Питер", 2004. 12. Порев В. Компьютерная графика. СПб.: БХВ-Петербург, 2002. 13. Симонович С., Евсеев Г., Алексеев А.. Специальная информатика. М.: АСТ-Пресс, 1999. 14. Слободецкий И. 3D Studio Max. Практический курс. М.: Компьютерная литература, 2004. 15. Соловьев М. Трехмерный мир 3D Studio Max 5.0. М.: Солон-Пресс, 2003. 16. Уокенбах Джон. Диаграммы в Excel. М.-Спб.-Киев: Диалектика, 2003. 17. Чекотовский Э.В. Графический анализ статистических данных в Microsoft Excel 2000. М.: "Диалектика", 2002. С о д е р ж а н и е П р е д и с л о в и е 3 Лекция 1. Введение в компьютерную графику 5 Основные направления компьютерной графики 5 Деловая графика 8 Лекция 2. Виды компьютерной графики. Программные средства компьютерной графики 12 Виды компьютерной графики 12 Классы программ для работы с растровой графикой 16 Средства создания и обработки векторных изображений 17 Средства создания фрактальных изображений 18 Лекция 3. Основные понятия КГ 18 Разрешение изображения и его размер 18 Понятие растра 19 Методы растрирования 20 Основы теории цвета 21 Лекция 4. Цветовые модели и палитры. Цветовые профили 23 Аддитивная цветовая модель RGB 23 Субтрактивная цветовая модель CMYK 26 Преобразование между моделями RGB и CMYK 27 Цветовая модель HSV 28 Другие цветовые модели 29 Цветовые профили 30 Лекция 5. Кодирование цвета. Палитра 32 Кодирование цвета 32 Индексные палитры 33 Фиксированная палитра 34 Безопасная палитра 35 Лекция 6. Визуализация изображений. Основные понятия 35 Основные геометрические характеристики растра 36 Методы улучшения растровых изображений: антиэлайзинг и дизеринг 37 Лекция 7. Геометрическое моделирование. Системы координат. Аффинные преобразования 41 Основные понятия геометрического моделирования 41 Системы координат 42 Аффинные преобразования 44 Лекция 8. Геометрические модели плоских объектов 47 Основные понятия 47 Способы описания (модели) прямой линии 48 Взаимное расположение графических элементов на плоскости 50 Уравнения пучка прямых и биссектрисы угла 51 Лекция 9. Кривые 2-го порядка. Сплайны. Кривые Безье 52 Кривые второго порядка 52 Сплайны. Кривые Безье 55 Лекция 10. Многоугольники (полигоны). Тесты ориентации точки относительно полигона 59 Понятие полигона. Геометрическая модель плоского полигона 59 Свойства плоских многоугольников 59 Тесты ориентации точки относительно полигона 60 Лекция 11. Базовые растровые алгоритмы 63 Алгоритмы вывода прямой линии 63 Инкрементные алгоритмы 64 Алгоритм вывода окружности 65 Алгоритм вывода эллипса 66 Лекция 12. Алгоритмы закрашивания 67 Задача графического вывода фигур 67 Алгоритмы закрашивания 68 Алгоритмы заполнения, использующие математическое описание кон- тура 71 Лекция 13. Фрактальные алгоритмы 75 Понятие фрактала 75 Алгоритмические фракталы 75 Геометрические фракталы 77 Площадные фракталы 78 Фракталы на основе метода IFS 79 Применение методов фрактальной графики 81 Лекция 14. Методы и алгоритмы трехмерной графики. Модели описа- ния поверхностей 83 Аналитическая модель поверхности 83 Векторная полигональная модель 85 Воксельная модель 86 Равномерная сетка 87 Неравномерная сетка. Изолинии 88 Моделирование объектов в системах КГ 90 Лекция 15. Визуализация трехмерных изображений 91 Проецирование трехмерных объектов на картинную плоскость 91 Уровни визуализации 94 Каркасная визуализация 95 Показ с удалением невидимых точек. Классификация методов 95 Лекция 16. Методы Гуро и Фонга для закрашивания поверхностей. Методы прямой и обратной трассировки лучей 100 Закрашивание поверхностей 100 Метод Гуро 103 Метод Фонга 105 Методы трассировки лучей 107 Лекция 17. Формирование изображений средствами современных видеосистем. Графические интерфейсы и стандарты программирова- ния графики 110 Принципы формирования изображения на экране 110 Вертикальная развертка и двойная буферизация 111 Архитектура современных видеосистем 112 Современные стандарты и интерфейсы программирования компью- терной графики 116 П р и л о ж е н и е 1. Наиболее распространенные форматы графических файлов 120 П р и л о ж е н и е 2. Тексты программ для построения фрактальных изображений 123 Библиографический список 129 Снижко Елена Александровна Компьютерная геометрия и графика Редактор и корректор Г.М. Звягина Подписано в печать 09.08.2005. Формат 60х84/16. Бумага документная. Печать трафаретная. Усл. печ. л. 8,13. Уч.-изд. л. 8,25. Тираж 500 экз. Заказ №155. Балтийский государственный технический университет Типография БГТУ 190005, С.-Петербург, 1-я Красноармейская ул., д. 1