Книги, научные публикации
Московская финансово-промышленная академия Артюхин В.В.
Компьютерная графика Москва, 2005 УДК 004.92 ББК 32.973.202 А 867 Артюхин В.В. Компьютерная графика /Московская финансово промышленная академия. - М., 2005. - 72 с.
й Артюхин В.В., 2005 й Московская финансово-промышленная академия, 2005 2 Содержание 1. Введение........................................................................................................4 2. Основные понятия машинной графики.....................................................5 2.1. Обработка графической информации.....................................................5 2.2.Области применения машинной графики..............................................6 2.3. Растры против векторов...........................................................................9 3. Аффинные преобразования и проектирование.......................................12 3.1. Аффинные преобразования на плоскости............................................ 3.2. Однородные координаты точки............................................................. 3.3. Аффинные преобразования в пространстве......................................... 3.4. Проектирование и его виды................................................................... 4. Растровые алгоритмы................................................................................ 4.1. Растровая развертка отрезка.................................................................. 4.2. Отсечение отрезка................................................................................... 4.3. Определение принадлежности точки многоугольнику....................... 4.4. Закраска области, заданной цветом границы....................................... 4.5. Пересечение произвольного луча с простейшими геометрическими объектами........................................................................................................ 5. Алгоритмы удаления невидимых линий и поверхностей...................... 5.1. Отсечение нелицевых граней................................................................. 5.2. Удаление невидимых линий. Алгоритм Робертса............................... 5.3. Алгоритм Аппеля.................................................................................... 5.4. Удаление невидимых граней. Метод z-буфера.................................... 5.5. Алгоритмы упорядочения...................................................................... 5.6. Метод построчного сканирования......................................................... 5.7. Алгоритм Варнака................................................................................... 6. Аппроксимация кривых и поверхностей................................................. 6.1. Сплайн - функции................................................................................... 6.2. Сплайновые кривые................................................................................ 7. Освещение и методы закраски.................................................................. 7.1. Закраска методом Гуро........................................................................... 7.1. Закраска методом Фонга........................................................................ 8. Когнитивная графика................................................................................. 9. Хранение графических данных................................................................. 9.1. Алгоритмы сжатия данных.................................................................... 9.2. Пример форматов графических файлов................................................ Глоссарий........................................................................................................ Литература...................................................................................................... 1. Введение За последние десять лет, персональный компьютер из инструмента для профессионалов превратился в общедоступное и необходимое средство, без которого сегодня немыслима никакая аналитическая деятельность. В связи с постоянным ростом числа пользователей ПК и, одновременно, с общим понижением необходимого для их работы профессионального уровня, современная индустрия программного обеспечения накладывает на специалиста в этой области дополнительные требования.
В настоящее время к программному обеспечению (продукту) предъявляются не только требования надежности и эффективности, но также удобства использования и наглядности. На смену бесконечным таблицам с числовыми результатами моделирования, оценки, анализа и т. д. пришли простые для понимания графики и диаграммы;
на смену двумерным чертежам и схемам Ч понятные и реалистичные трехмерные модели. Очевидно, что практически любое приложение, будь то программа финансового анализа или компьютерная игра, в той или иной мере нуждается в указанных средствах. Компьютерная графика как неотъемлемая часть науки программирования в целом дает в руки будущего специалиста по информационным технологиям необходимые средства для облегчения работы пользователя, то есть для реализации удобных и наглядных программ. Предлагаемая дисциплина является необходимой для будущего математика-программиста, так как находит свое применение в программных продуктах практически для любой отрасли.
В данном курсе будут изучаться, в основном, базовые понятия, математические методы и часто применяемые алгоритмы, а не на языковых средства или методы различных графических библиотек.
Дисциплина включает также ряд обзорных тем. Программы по данной дисциплине могут создаваться на любом языке программирования, будь то C++, Pascal или Basic и для любой операционной системы, будь то DOS, Windows или UNIX.
2. Основные понятия машинной графики 2.1. Обработка графической информации При обработке информации, связанной с изображением на мониторе, выделим четыре основных направления: распознавание образов, обработку изображений, машинную графику и когнитивную графику.
Основная задача распознавания образов в преобразовании уже имеющегося изображения на формально - понятный язык символов.
Распознавание образов есть совокупность методов, позволяющих получить описание изображения, поданного на вход, либо отнести заданное изображение к некоторому классу. При этом рассматриваемое изображение часто преобразуется в более абстрактное описание - набор чисел, набор символов или граф. Одной из интересных задач распознавания образов является так называемая скелетизация, при которой восстанавливается некоторая основа объекта, его скелет.
Символически распознавание изображений, или система технического зрения COMPUTER VISION (CV), может быть описана так:
Х вход - изображение;
Х выход - символ (текст) (рисунок 2.1.1).
Изображение CV Описание Рисунок 2.1.1.
Обработка изображений рассматривает задачи, в которых и входные и выходные данные являются изображениями. Примерами обработки изображений могут служить: передача изображений вместе с устранением шумов и сжатием данных, переход от одного вида изображения (полутонового) у другому (каркасному), контрастирование различных снимков, а также синтезирование имеющихся изображений в новые, например по набору поперечных сечений объекта построить продольные сечения или восстановить сам объект.
Тем самым система обработки изображений IMAGE PROCESSING (IP) имеет следующую структуру:
Х вход - изображение;
Х выход - изображение (рисунок 2.1.2).
Изображение IP Изображение Рисунок 2.1.2.
Компьютерная (машинная) графика воспроизводит изображение в случае, когда исходной является информация неизобразительной природы. Например, визуализация экспериментальных данных в виде графиков, гистограмм или диаграмм, вывод информации на экран в компьютерных играх, синтез сцен для тренажеров.
Можно сказать, что компьютерная графика рисует, опираясь на формальное описание и имеющийся набор средств.
Символически систему компьютерной графики COMPUTER GRAPHICS (CG) можно представить следующим образом:
Х вход - формальное описание;
Х выход - изображение (рисунок 2.1.3).
Формальное CG Изображение описание Рисунок 2.1.3.
В последние несколько лет от компьютерной графики отделилось еще одно самостоятельное направление, получившее название когнитивной графики. В случае когнитивной графики на выходе мы также получаем изображение, однако описание, поступающее на вход вовсе не обязано быть формальным (то есть четким и однозначным).
Примером может послужить генерация трехмерных сцен по описанию на естественном (человеческом) языке, который как известно неоднозначен, избыточен и неточен.
Основной целью изучаемого кура является именно компьютерная (машинная) графика.
2.2. Области применения машинной графики На сегодняшний день практически невозможно представить себе компьютер, не имеющий графических возможностей. Простейший пример таких возможностей Ч графический интерфейс пользователя, завоевавший в той или иной реализации практически весь сектор персональных компьютеров и рабочих станций, а также получивший широкое распространение на серверах. Основными достоинствами графического интерфейса являются наглядность и простота использования. Однако, интерфейс Ч это лишь средство для управления работой компьютера, графические же возможности этим не ограничиваются, их применение обширно Ч от простейших иллюстраций и движущихся изображений до красочных презентаций и сложнейших спецэффектов для кино. Без графики сегодня немыслима работа дизайнеров, проектировщиков, архитекторов, специалистов по радиоэлектронике и многих других.
Сформулируем точнее основные области применения компьютерной графики:
Х Графический интерфейс пользователя. Как уже отмечалось выше, он призван облегчить взаимодействие человека и компьютера.
Являясь относительно простым в реализации (ограниченное число плоских графических объектов заранее известного вида, модульность построения изображения и т.п.), графический интерфейс, тем не менее, может выглядеть достаточно привлекательно, и его значение трудно переоценить. Основные примеры: семейство MS Windows, Mac OS, X Windows для UNIX-подобных систем.
Х Создание иллюстративного материала, то есть изображений для последующего использования в печатной продукции либо в электронных документах. Такие задачи решаются при помощи графических редакторов различной сложности, в основном Ч растровых (см. ниже). Простейшие редакторы позволяют рисовать графические примитивы (круг, квадрат, линия, точка и т.д.), закрашивать области определенным цветом или шаблоном. Профессиональные пакеты предоставляют гораздо более широкие возможности. Приведем лишь некоторые: работа с несколькими плоскостями изображения, преобразование цветовой гаммы, создание сложных визуальных эффектов (размывание, затенение, эффект мазков и т.п.). Несколько особняком в этой группе стоят векторные графические редакторы. О достоинствах и недостатках векторной графики мы поговорим в следующем разделе, а здесь отметим только, что подобные редакторы используются, в основном, для создания различных схем и не слишком применимы при работе с фотоизображениями и любыми другими изображениями сложных предметов (людей, животных, растений).
Основные примеры: УMS PaintФ (простейший редактор);
УCorel PhotoPaintФ, УAdobe PhotoShopФ (профессиональные растровые редакторы);
УCorel DrawФ, УMS DrawФ (векторные редакторы различной сложности).
Х Автоматизированное проектирование двумерных и условно двумерных объектов. В основном речь идет об электросхемотехнике, но существуют также подобные программы для проектирования различных коммуникаций и сооружений, для которых достаточно лишь плана, то есть вида сверху. В смысле использования графических возможностей компьютера эти программы подобны векторным графическим редакторам, но отличаются определенной специализацией, поскольку им приходится отображать ограниченный набор предметов и проводить достаточно специфические преобразования. И вообще, графика в таких системах Ч функция вторичная, а первичным является проектирование по заданным параметрам. Наиболее известный пример Ч пакет для проектирования и подготовки к производству печатных плат УPCADФ.
Х Создание плоских анимационных роликов Ч движущихся картинок. Программы для их создания являются логическим продолжением обычных графических редакторов. Особенно хочется отметить, что использование векторной графики способно значительно сэкономить затраченные усилия, поскольку в этом случае можно описать не только движение объекта от кадра к кадру (это несложно сделать и при использовании растровой графики), но и его трансформацию. Примеры: УAutodesk AnimatorФ (растровый), УCorel MoveФ (векторный).
Х Трехмерная (3D1) анимация Ч вершина компьютерного лизобразительного искусства. Ни о какой растровой графике речь уже не идет, любой объект имеет точное описание. Отсюда Ч практически неограниченные возможности построения изображений и манипуляции ими. Имеется возможность работы с поверхностями различной структуры (текстурирование, градиентная закраска);
можно создать практически любое освещение и спецэффекты (туман, зеркальная поверхность и т.п.). Единственным сдерживающим фактором является быстродействие вычислительной техники, поскольку все алгоритмы для работы с 3D графикой используют большой объем сложных расчетов. В связи с этим существует два несколько различных подхода к использованию 3D анимации. В первом из них во главу угла ставится качество и правдоподобность изображения. При этом на создание одного кадра изображения может потребоваться от нескольких секунд до нескольких часов (!). Конечным результатом такой работы обычно является растровый анимационный файл, который потом может воспроизводиться в реальном времени при достаточно невысоких требованиях к аппаратуре. Другой подход заключается в обсчете и выводе изображения в режиме реального времени. Поскольку для относительно плавного движения необходимо создание не менее десяти пятнадцати кадров в секунду, а требования к оборудованию не должны быть слишком высоки (речь идет в основном о компьютерных играх), качеством и точностью здесь приходится жертвовать, упрощая вычисления (например, заменяя арифметику с плавающей точкой целочисленной), схематизируя освещение и закраску и опуская незначительные детали. Основные примеры: У3D StudioФ (первый подход);
практически все игры типа 3D-action, например УQuakeФ (второй подход).
Х Автоматизированное проектирование 3D объектов Ч архитектура, автомобиле-, корабле- и самолетостроение и многое другое. Использует в основном те же алгоритмы, что и 3D анимация, причем зачастую оба подхода. Подобные программы значительно облегчают труд проектировщиков, позволяя не израсходовав ни грамма материалов и ни копейки денег (если не считать тех миллионов, которые идут на оплату техники, программ, высококвалифицированных специалистов и, наконец, электроэнергии) посмотреть на проектируемый объект с любой стороны, получить изображение фотографического качества при любом освещении и в любом От английского three dimensions Ч три измерения.
окружении, на лету подправить какие-то детали и практически сразу увидеть результат. Разумеется, возможности систем автоматизированного проектирования этим не ограничиваются, но описание таких функции, как автоматический контроль за соблюдением определенных параметров объекта (геометрических, стоимостных и т.п.) выходит за рамки данной работы. В качестве примера приведем одну из самых современных программ для проектирования автомобилей Ч УAutoStudioФ от УAlias/wavefrontФ. Говорят, одна из новинок фирмы УMercedes-BenzФ (ныне Ч часть УDaimler-ChryslerФ), УMercedes A-classeФ был полностью спроектирован при помощи этой программы, практически без использования моделей и прототипов в железе. Вот только после начала выпуска автомобиля оказалось, что он склонен к переворачиваниюЕ Таков далеко не полный список областей применения компьютерной графики.
2.3. Растры против векторов Прежде всего, определимся с терминологией. Графику разделяют на растровую и векторную. Сегодня эти понятия используются не совсем так, или даже совсем не так, как они использовались изначально.
Было время, когда тип графики определялся типом монитора и деление было следующим. Если электронно-лучевая трубка (ЭЛТ) монитора имела строчно-кадровую развертку (растр), то говорили о растровой графике, то есть графике точек (пикселей2), образующих прямоугольную область, внутри которой можно отдельно менять параметры любой точки и эти изменения будут немедленно отображены на экране монитора. Если же ЭЛТ имела координатную развертку, т.е. луч лумел двигаться по некоторой траектории (как правило, по отрезкам прямой), последовательно обходя набор точек (вершин), то говорили о векторной графике, то есть графике вершин (векторов3) и соединяющих их линий, когда можно говорить о цвете отдельной линии (в простейшем случае Ч видима или нет), но никак не точки экрана. Векторные мониторы имели широкое распространение там, где необходимо было выводить на экран четкие чертежи (в том числе и трехмерные), ведь, как будет показано далее, в растровой графике рисование линий Ч одна из самых сложных проблем. Главными недостатками таких мониторов, которые и привели к их практически полному исчезновению, были сложность создания и невозможность отображения сплошных фигур.
В результате, на сегодняшний день вся графика является растровой, даже та, которую называют векторной. Во всяком случае, в той части ее реализации, которая начинается в видеопамяти и От английского pixel Ч минимальный элемент изображения.
r Вспомним, что с точки зрения многих разделов математики понятия точка A(x, y) и вектор a (x, y) являются взаимозаменяемыми.
заканчивается на экране монитора. В чем же различие? В способе хранения и обработки. Растровое изображение хранится и обрабатывается как набор пикселей (или несколько наборов в случае нескольких плоскостей изображения, что, впрочем, не меняет сути). К тому же, имеет смысл говорить только о плоском растровом изображении. Векторное изображение хранится и обрабатывается как набор графических примитивов, т.е. геометрических объектов, описанных аналитически. Типичным примером графического примитива является треугольник, для которого хранятся следующие атрибуты:
координаты трех вершин (необязательно двумерные) и цвет (текстура).
Можно также хранить цвет каждого ребра треугольника.
Главным достоинством векторного способа обработки и хранения графической информации (в дальнейшем Ч векторной графики) является возможность легко работать с любым элементом изображения.
Не составляет никакого труда переместить, повернуть или изменить в размерах как отдельный примитив, так и все изображение в целом, причем операция не внесет искажений и будет обратима, чего нельзя сказать о растровом изображении. В самом деле, в случае векторным изображением необходимо будет только поменять координаты вершин треугольника, когда как в растровом придется по довольно сложным алгоритмам добавлять недостающие пиксели (в случае растяжения) либо убирать лишние (в случае сжатия), либо закрывать другие части изображения (в случае поворота и переноса).
А недостатки? Они, как всегда, являются продолжением достоинств. Во-первых, в силу того, что видеопамять и монитор работают с растровой графикой, для вывода на экран необходимо произвести растеризацию изображения, т.е. преобразование в пиксельную форму. Во-вторых, при каждом конкретном размере рисунка растровое изображение всегда будет иметь лучшее качество, чем векторное. Приведем пример. Пусть при помощи очень хорошего сканера нам удалось ввести в компьютер растровое изображение картины Мона Лиза размером 2000х3000 точек. Предположим также, что у нас есть очень хорошая программа для векторизации растровой картинки (а такие программы есть, например Ч УCorel TraceФ).
Полученное с помощью этой программы изображение будет очень похоже на первоначальное, но в силу особенностей векторной графики оно будет уступать ему по качеству (будут заметны резкие переходы в цвете от примитива к примитиву, некоторая лугловатость и т.д.).
Однако, если мы теперь сожмем оба изображения в десять раз (200х точек), разница будет менее заметна, возможно даже, что векторный вариант будет более четким и узнаваемым. А уж если мы произведем затем обратную операцию, растровое изображение вообще перестанет быть похожим на оригинал, а векторное останется все тем же. Еще один пример, на этот раз из области игр. Предположим, нам надо изобразить монстра на расстоянии десяти шагов от игрока. Можно сделать безумно красивое изображение, задействовав каждый пиксель, отведенный для этого изображения, чтобы передать всю кровожадность и отвратительность чудовища. И даже самая тщательная векторная модель монстра не сможет сравниться с полученным изображением Ч все те же угловатость и резкие переходы плюс треугольное непонятно что вместо лица (или морды). Но стоит подойти на пять шагов, и становится ясно, что лучше уж треугольная морда, чем лэто.
В растровой графике уже все сделано. Такие же слова были сказаны в свое время молодому Максу Планку (будущему основоположнику квантовой физики) по поводу положения дел в теоретической физике. Чем это кончилось Ч общеизвестно. Но на сегодняшний день все выглядит именно так, и не видно никаких способов что-то кардинально улучшить (можно только постепенно увеличивать быстродействие отдельных компонентов системы). Все основные алгоритмы (а некоторые из них мы рассмотрим далее) были разработаны и отшлифованы уже давно. Затем, для ускорения вывода изображений и разгрузки центрального процессора, часть этих алгоритмов была реализована на аппаратном уровне Ч появились 2D акселераторы (видеокарты с аппаратной поддержкой вывода графических примитивов) и видеобластеры (видеокарты с аппаратной поддержкой масштабирования изображения). Что еще делать Ч неясно.
Но кто знает, может быть через несколько лет произойдет прорыв в этой области. Такой же, какой произошел (или продолжает происходить) в области графики векторной.
Сразу оговоримся, речь идет не о векторной графике в целом, а о наиболее широко используемой ее разновидности Ч 3D графике. И прорыв этот связан не с алгоритмами 3D преобразований Ч они просты и давно известны, а с процессом растеризации. Дело в том, что различные стадии растеризации изображения (освещение, текстурирование, формирование Z-буфера) сопряжены с интенсивными вычислениями, а центральный процессор помимо этого вынужден делать массу другой работы. Выход был найден по аналогии с растровой графикой Ч соответствующие алгоритмы реализовали аппаратно.
Однако, обилие этих алгоритмов и сложность их реализации привели к тому, что с первого раза далеко не все получилось хорошо. И теперь большое число фирм-разработчиков 3D акселераторов работают над тем, чтобы заложить в свои детища как можно больше возможностей, а главное Ч заставить их работать как можно быстрее и как можно точнее.
3. Аффинные преобразования и проектирование Вывод изображения на экран монитора и разнообразные действия с ним, в том числе и визуальный анализ, требуют от пользователя известной геометрической грамотности. Геометрические понятия формулы и факты, относящиеся к плоскому и трехмерному случаям, играют в задачах компьютерной графики особую роль. Геометрические соображения, подходы и идеи в соединении с постоянно расширяющимися возможностями вычислительной техники являются неиссякаемым источником существенных продвижений на пути компьютерной графики, ее эффективного использования в научных и иных исследованиях. Порой даже самые простые геометрические методики обеспечивают заметное продвижение на различных этапах решения большой графической задачи.
3.1. Аффинные преобразования на плоскости Для начала определимся с системами координат. В задачах компьютерной графики приходится иметь дело с несколькими различными системами координат на различных этапах решения. Все эти системы являются прямоугольными, то есть все оси перпендикулярны друг другу. Различия заключаются в направлении этих осей. Например, от того, какой графической библиотекой мы пользуемся и в какой операционной системе работаем направление оси ординат может изменяться на противоположное. Наиболее часто приходится учитывать разницу в направлении оси аппликат. Если ось аппликат направлена от нас (от зрителя, в глубь монитора и т. д.) система координат называется левосторонней, если наоборот, то правосторонней.
В компьютерной графике все, что относится к двумерному случаю, принято обозначать символом 2D4.
Допустим, на плоскости введена прямолинейная координатная система. Тогда каждой точке M ставится в соответствие упорядоченная пара чисел (x,y) ее координат (рисунок 3.1.1). Вводя на плоскости еще одну прямолинейную систему координат, мы ставим в соответствие той же точке M другую пару чисел -- (x*, y*).
От английского two dimensions - два измерения Y M (x, y) 0 X Рисунок 3.1.1.
Переход от одной прямолинейной координатной системы к другой описывается следующими соотношениями:
x* = x + y +, * y = x + y + ,,,,,, где -- произвольные числа, связанные неравенством.
Эти формулы можно трактовать двояко: либо сохраняются координаты точки и меняется координатная система (рисунок 3.1.2), либо координатная система сохраняется и меняется положение точки (рисунок 3.1.3).
Y Y * M Y* X* M M 0* 0 X X Рисунок 3.1.2. Рисунок 3.1.3.
В дальнейшем мы будем рассматривать приведенные формулы как правило, согласно которому в заданной системе прямолинейных координат преобразуются точки плоскости.
В аффинных преобразованиях на плоскости особую роль играют несколько важных частных случаев, имеющих хорошо прослеживаемые геометрические характеристики. При исследовании геометрического смысла числовых коэффициентов в приведенных формулах для этих случаев нам удобно считать, что заданная система координат является прямоугольной декартовой.
A. Поворот (вокруг начальной точки на угол ) (рисунок 3.1.4) описывается формулами x* = x cos - y sin, * y = x sin + y cos.
Б. Растяжение (сжатие) вдоль координатных осей (рисунок 3.1.5) можно задать так:
x* = x, y* = y, > 0, >.
В. Отражение (относительно оси абсцисс) (рисунок 3.1.6) задается при помощи формул x* = x, y* = - y.
Г. Перенос описывается так:
x* = x +, y* = y + .
Выбор этих четырех частных случаев определяется двумя обстоятельствами:
1. Каждое из приведенных выше преобразований имеет простой и наглядный геометрический смысл (геометрическим смыслом наделены и постоянные числа, входящие в формулы).
2. Как доказывается в курсе аналитической геометрии, любое преобразование всегда можно представить как последовательное исполнение (суперпозицию) простейших преобразований вида А, Б, В и Г (или части этих преобразований).
Для эффективного использования этих известных формул в задачах компьютерной графики более удобной является их матричная запись. Матрицы, соответствующие случаям А, Б и В, строятся легко и имеют соответственно следующий вид:
cos sin 0 1,,.
0 - - sin cos Построить матрицу переноса сложнее из-за присутствующих в формулах свободных членов. Однако для решения рассматриваемых далее задач весьма желательно охватить матричным подходом все четыре простейших преобразования, а, значит, и общее аффинное преобразование. Этого можно достичь, например, так: перейти к описанию произвольной точки плоскости не упорядоченной парой чисел, а упорядоченной тройкой чисел.
3.2. Однородные координаты точки Пусть M - произвольная точка плоскости с координатами (x, y), вычисленными относительно заданной прямолинейной координатной системы. Однородными координатами этой точки называется любая x1, x2,h тройка одновременно неравных нулю чисел ( ), связанных с заданными величинами x и y следующими соотношениями:
x1 x = x, = y.
h h Применение однородных координат оказывается удобным уже при решении простейших задач.
Рассмотрим, например, вопросы, связанные с изменением масштаба чисел. Если устройство отображения работает только с целыми числами, то для точки с координатами (0.5, 0.1) можно ввести однородные координаты, выбрав значение h=10 и, тем самым привести координаты точки к виду (5, 1, 10).
Рассмотрим другой случай. Чтобы результаты преобразования не приводили к арифметическому переполнению, для точки с координатами (80000, 1000) можно взять, например, h=0.001. В результате получим (80, 1).
Приведенные примеры показывают полезность использования однородных координат при проведении расчетов. Однако основной целью введения однородных координат в компьютерной графике является их несомненное удобство в применении к геометрическим преобразованиям.
При помощи троек однородных координат и матрицы третьего порядка, считая h=1, общее аффинное преобразование можно записать следующим образом:
(x* y* 1) = (x y 1) 0.
Элементы матрицы произвольного аффинного преобразования не несут в себе явно выраженного геометрического смысла. Поэтому, чтобы реализовать то или иное отображение, то есть найти элементы соответствующей матрицы по заданному геометрическому описанию, необходимы специальные приемы. Обычно построение этой матрицы в соответствии со сложностью рассматриваемой задачи и с описанными выше частными случаями разбивают на отдельные этапы.
На каждом этапе ищется матрица, соответствующая тому или иному из выделенных выше случаев А, Б, В или Г, обладающих хорошо выраженными геометрическими свойствами. Затем эти матрицы перемножаются.
Выпишем соответствующие матрицы третьего порядка.
А. Матрица вращения (rotation) cos sin [R]= sin cos - 0 0 Б. Матрица растяжения(сжатия) (dilatation) 0 [D]= 0 0 В. Матрица отражения (относительно оси абсцисс) (reflection) 1 0 [M ]= -1 0 0 Г. Матрица переноса (translation) 1 0 [T]= 1.
Пример Построить матрицу поворота вокруг точки A(a, b) на угол.
1-й шаг. Перенос на вектор A(-a, -b) для совмещения центра поворота с началом координат.
1 0 [T- A]= 0 1 -- матрица соответствующего преобразования.
- a - b 2-й шаг. Поворот на угол.
cos sin [R ]= sin cos -- матрица соответствующего преобразования.
- 0 0 3-й шаг. Перенос на вектор A(a, b) для возвращения центра поворота в прежнее положение.
1 0 [TA]= 1 -- матрица соответствующего преобразования.
a b Перемножим матрицы в том же порядке, как они выписаны:
[T- A]*[R ]*[TA].
В результате получим, что искомое преобразование (в матричной записи) будет выглядеть следующим образом:
cos sin (x*y*1) = (xy1)* - sin cos.
- acos + bsin + a - asin - bcos + b Элементы полученной матрицы (особенно в последней строке) не так легко запомнить. В то же время каждая из трех перемножаемых матриц по геометрическому описанию соответствующего отображения строится достаточно легко.
3.3. Аффинные преобразования в пространстве Обратимся теперь к трехмерному случаю и начнем рассмотрение сразу с введения однородных координат.
Поступая аналогично тому, как это было сделано в размерности два, заменим координатную тройку (x, y, z), задающую точку в пространстве на четверку чисел (x, y, z, 1) или, более общо, на четверку (hx, hy, hz, h), h 0.
Предложенный переход к новому способу задания точек дает возможность воспользоваться матричной записью и в более сложных, трехмерных задачах.
Любое аффинное преобразование в трехмерном пространстве может быть представлено в виде суперпозиции вращений, растяжений, отражений и переносов. Поэтому уместно подробно описать матрицы именно этих преобразований.
А. Матрицы вращения в пространстве Матрица вращения вокруг оси абсцисс на угол :
1 0 0 0 cos sin [Rx]=.
- sin cos 0 0 0 Матрица вращения вокруг оси ординат на угол :
cos 0 - sin 0 1 0 [Ry]=.
sin 0 cos 0 0 0 Матрица вращения вокруг оси аппликат на угол :
cos sin 0 - sin cos 0 [Rz ]=.
0 0 1 0 0 0 Б. Матрица растяжения (сжатия):
0 0 0 0 [D]=, где 0 0 0 0 0 > 0 -- коэффициент растяжения (сжатия) вдоль оси абсцисс;
> 0 -- коэффициент растяжения (сжатия) вдоль оси ординат;
> 0 -- коэффициент растяжения (сжатия) вдоль оси аппликат;
В. Матрицы отражения Матрица отражения относительно плоскости xy:
1 0 0 0 1 0 [M ]=.
z 0 0 -1 0 0 0 Матрица отражения относительно плоскости yz:
-1 0 0 0 1 0 [M ]=.
x 0 0 1 0 0 0 Матрица отражения относительно плоскости xz:
1 0 0 0 -1 0 [M ]=.
y 0 0 1 0 0 0 Г. Матрица переноса (здесь (, ,) --вектор переноса):
1 0 0 0 1 0 [T]=.
0 0 1 Пример:
Построить матрицу вращения на угол вокруг прямой L, проходящей через точку A(a, b, c) и имеющую направляющий вектор (l, m, n). Можно считать, что направляющий вектор прямой является единичным: l + m2 + n2 = 1.
Решение сформулированной задачи разбивается на несколько этапов. Опишем последовательно каждый из них.
1-й шаг. Перенос на вектор ЦA(-a, -b, -c) при помощи матрицы 1 0 0 0 1 0 [T]=.
0 0 1 - a - b - c В результате этого переноса мы добиваемся того, чтобы прямая L проходила через начало координат.
2-й шаг. Совмещение оси аппликат с прямой L двумя поворотами вокруг оси абсцисс и оси ординат.
1-й поворот - вокруг оси абсцисс на угол (подлежащий определению). Чтобы найти этот угол, рассмотрим ортогональную проекцию L` исходной прямой L на плоскость X=0.
Направляющий вектор прямой L` определяется просто - он равен (0, m, n).
n m cos =,sin = Отсюда сразу же вытекает, что, где d d d = m2 + n2.
Соответствующая матрица вращения имеет следующий вид:
1 0 0 n m d d [Rx]=.
m n 0 - d d 0 0 0 Под действием преобразования, описываемого этой матрицей, координаты вектора (l, m, n) изменятся. Подсчитав их, в результате получим (l,m,n,1)[Rx]= (l,0,d,1).
2-й поворот - вокруг оси ординат на угол, определяемый соотношениями cos = l,sin = -d.
Соответствующая матрица вращения записывается в следующем виде:
1 0 d 0 1 0 [Ry]=.
- d 0 l 0 0 0 3-й шаг. Вращение вокруг прямой L на заданный угол.
Так как теперь прямая L совпадает с осью аппликат, то соответствующая матрица имеет следующий вид:
cos sin 0 - sin cos 0 [Rz ]=.
0 0 1 0 0 0 4-й шаг. Поворот вокруг оси ординат на угол.
5-й шаг. Поворот вокруг оси абсцисс на угол.
Вращение в пространстве некоммутативно. Поэтому порядок, в котором проводятся вращения, является весьма существенным.
6-й шаг. Перенос на вектор A(a, b, c).
Перемножив найденные матрицы в порядке их построения, - [T]*[Rx]*[Ry]*[Rz ]*[Ry] *[Rx]-1 *[T]- получим следующую матрицу:.
Выпишем окончательный результат, считая для простоты, что ось вращения L проходит через начальную точку:
l2 + cos(1- l2) l(1- cos)m + nsin l(1- cos)n - msin l(1- cos)m - nsin m2 + cos(1- m2) m(1- cos)n + l sin.
l(1- cos)n + msin m(1- cos)n - l sin n2 + cos(1- n2) 0 0 0 3.4. Проектирование и его виды Для того, чтобы изобразить трехмерную сцену на двумерном экране, применяется операция, называемая проектированием при помощи пучка прямых. В компьютерной графике используется несколько различных видов проектирования (иногда называемого так же проецированием). Наиболее употребляемые на практике виды проектирования суть параллельное и центральное (перспективное).
Для получения проекции объекта на картинную плоскость необходимо провести через каждую его точку прямую из заданного проектирующего пучка (собственного или несобственного) и затем найти координаты точки пересечения этой прямой с плоскостью изображения. В случае центрального проектирования все прямые выходят из одной точки - центра собственного пучка. При параллельном проектировании центр (несобственного) пучка считается лежащим в бесконечности (рисунок 3.4.1).
Каждый из этих двух основных классов разбивается на несколько подклассов в зависимости от взаимного расположения картинной плоскости и координатных осей (рисунки 3.4.2 и 3.4.3).
Параллельные проекции Ортографическая Аксонометрическая Косоугольная проекция проекция проекция Триметрическая проекция Свободная Кабинетная проекция проекция Диметрическая проекция Изометрическая проекция Рисунок 3.4. Перспективные проекции Одноточечная Двухточечная Трехточечная проекция проекция проекция Рисунок 3.4. При ортографической проекции картинная плоскость совпадает с одной из координатных плоскостей, то есть фактически для отображения трехмерного объекта на двумерном мониторе производится обнуление одной из трех координат всех точек (рисунок 3.4.4.).
Матрица проектирования вдоль оси X на плоскость YZ имеет вид:
0 0 0 0 1 0 [Px]=.
0 0 1 0 0 0 В случае, если плоскость проектирования параллельная координатной плоскости, а не совпадает с ней, необходимо умножить матрицу [Px] на матрицу сдвига. В результате получаем:
1 0 0 0 0 0 0 0 1 0 0 0 1 0 [Px]* =.
0 0 1 0 0 0 1 p 0 0 1 p 0 0 Аналогично записываются матрицы проектирования вдоль двух других координатных осей:
1 0 0 0 1 0 0 0 0 0 0 0 1 0 [Py]= [Pz ]=,.
0 0 1 0 0 0 0 0 q 0 1 0 0 r При аксонометрической проекции проектирующие прямые перпендикулярны картинной плоскости.
В соответствии со взаимным расположением плоскости проектирования и координатных осей различают три вида проекций:
Х триметрию - нормальный вектор картинной плоскости образует с каждой координатной осью различные углы;
Х диметрию - два угла между нормалью координатной плоскости и координатными осями равны;
Х изометрию - все три угла между нормалью координатной плоскости и координатными осями равны.
Каждый из трех видов указанных проекций получается комбинацией поворотов, за которой следует параллельное проектирование.
При повороте на угол относительно оси ординат, на угол вокруг оси абсцисс и последующего проектирования вдоль оси аппликат возникает матрица cos 0 - sin 0 1 0 0 0 1 0 0 0 1 0 0 0 cos sin 0 0 1 0, [M ]= * * sin 0 cos 0 0 - sin cos 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 cos sin sin 0 0 cos 0.
[M ]= sin - sin cos 0 0 0 0 Проекции для получения которых используется пучок прямых, не перпендикулярных плоскости экрана, принято называть косоугольными.
При косоугольном проектировании орта оси Z на плоскость XY имеем:
(0 0 1 1) ( 0 1 ).
Матрица соответствующего преобразования имеет следующий вид:
1 0 0 0 1 0.
0 0 0 0 Выделяют два вида косоугольных проекций: свободную (угол наклона проектирующих прямых равен 45 градусам) и кабинетную (частный случай свободной - масштаб по оси аппликат вдвое меньше).
= = cos В случае свободной проекции, а в случае = = cos кабинетной.
2 Перспективные (центральные) проекции строятся намного более сложно и рассматриваться нами не будут.
4. Растровые алгоритмы Так как в подавляющем большинстве графические устройства являются растровыми, то есть представляют изображение в виде прямоугольной матрицы (сетки, целочисленной решетки) пикселей (растра), то, естественно, возникает необходимость в растровых алгоритмах.
Хотя большинство графических библиотек содержат внутри себя достаточное количество простейших растровых алгоритмов, таких, как:
Х переведение идеального объекта (отрезка, окружности и др.) в их растровые образы;
Х обработка растровых изображений, тем не менее часто возникает необходимость явного построения растровых алгоритмов.
4.1. Растровая развертка отрезка Достаточно важным понятием для растровой сетки является связность - возможность соединения двух пикселей растровой линией, то есть последовательным набором пикселей. При этом возникает (x1, y1) (x2, y2) вопрос, когда пиксели и можно считать соседними.
Вводится два понятия связности:
Х 4-связность, когда пиксели считаются соседними, если либо их x-координаты, либо y-координаты отличаются на единицу, то есть x1 - x2 + y1 - y2 1;
Х 8-связность, когда пиксели считаются соседними, если их x- и y-координаты отличаются не более чем на единицу, то есть x1 - x2 1, y1 - y2 1.
Понятие 4-связности является более сильным, чем 8-связность:
любые два 4-связных пикселя являются и 8-связными, но не наоборот (рисунок 4.1.1).
В качестве линии на растровой сетке выступает набор пикселей P1,P2,..., Pn, где любые два пикселя Pi, Pi+ являются соседними.
Так как понятие линии базируется на понятии связности, то естественным образом возникает понятие 4- и 8-связных линий.
Поэтому, когда мы говорим о растровом представлении, например, отрезка, то следует ясно понимать, о каком именно представлении идет речь. При этом нужно иметь в виду, что растровое представление объекта не является единственным и возможны различные способы построения.
Рассмотрим задачу построения растрового изображения отрезка, (x1, y1) (x2, y2) соединяющего точки. Для простоты будем считать, и 0 y2 - y1 x2 - x что. Тогда отрезок описывается следующим уравнением:
y2 - y y = y1 + (x - x1), x [x1, x2] или y = kx + b.
x2 - x Простейший алгоритм растрового представления отрезка имеет вид:
//File Line1.cpp void Line(int x1, int y1, int x2, int y2, int color) { double k=(y2-y1)/(x2-x1);
double b=y1-k*x1;
for(int x=x1;
x<=x2;
x++) putpixel5(x, round(k*x+b),color);
} Используя рекуррентное соотношение для вычисления y, можно упростить функцию, однако это не устраняет основного недостатка алгоритм - использования вещественных чисел для работы на целочисленной решетке.
В 1965 году Брезенхеймом был предложен простой целочисленный алгоритм для растрового построения отрезка, первоначально предназначенный для использования в графопостроителях.
При построении растрового изображения отрезка всегда выбирается ближайший по вертикали пиксель. При этом из двух точек A и B (рисунок 4.1.2) выбирается та, которая ближе к исходной прямой (в данном случае выбирается точка A, так как a Здесь и далее putpixel - некоторая абстрактная функция, отображающая на экране точку по заданным координатам и цвету. В случае d>0 значение y от предыдущей точки увеличивается на 1, 2(y - x) а d - на. В противном случае значение y не изменяется, а 2y значение d заменяется на. Реализация приведенного алгоритма представлена ниже. //File Line2.cpp void Line(int x1, int y1, int x2, int y2, int color) { int dx=x2-x1; int dy=y2-y1; int d=(dy<1)-dx; int d1=dy<1; int d2=(dy-dx)<1; putpixel (x1, y1, color); for (int x=x1+1, y=y1; x<=x2; x++) { if (d>0) { d+=d2; y+=1; } else d+=d1; putpixel (x, y, color); } } Из предложенного примера несложно написать функцию для построения 4-связной развертки отрезка. //File Line3.cpp void Line(int x1, int y1, int x2, int y2, int color) { int dx=x2-x1; int dy=y2-y1; int d=0; int d1=dy<1; int d2=-(dx<1); putpixel (x1, y1, color); for (int x=x1, y=y1, i=1; i i++) { if (d>0) { d+=d2; y+=1; } else { d+=d1; x+=1; } putpixel (x, y, color); } } Общий случай произвольного отрезка легко сводится к рассмотренному выше, следует только иметь в виду, что при y x выполнении неравенства необходимо поменять местами x и y. 4.2. Отсечение отрезка Необходимость отсечь выводимое изображение по границам некоторой области встречается довольно часто. В простейших ситуациях в качестве такой области, как правило, выступает прямоугольник. Ниже рассматривается достаточно простой и эффективный алгоритм отсечения отрезков по границе произвольного прямоугольника. Он заключается в разбиении всей плоскости на областей прямыми, образующими прямоугольник. В каждой из этих областей все точки по отношению к прямоугольнику расположены одинаково. Определив, в какие области попали концы рассматриваемого отрезка, легко понять, где именно необходимо отсечение. Для этого каждой области сообщается 4-битовый код, где установленный Х бит 0 означает, что точка лежит левее прямоугольника, Х бит 1 означает, что точка лежит выше прямоугольника, Х бит 2 означает, что точка лежит правее прямоугольника, Х бит 3 означает, что точка лежит ниже прямоугольника. Приведенная ниже программа реализует алгоритм Сазерленда - Кохена отсечения отрезка по прямоугольной области. //File clip.cpp void Swap (int &a, int &b) { int c; c=a; a=b; b=c; } int OutCode(int x, int y, int X1, int Y1, int X2, int Y2) { int code=0; if (x if (y if (x if (y return code; } void ClipLine(int x1, int y1, int x2, int y2, int X1, int Y1, int X2, int Y2) { int code1=OutCode(x1, y1, X1, Y1, X2, Y2); int code2=OutCode(x2, y2, X1, Y1, X2, Y2); int inside=(code1|code2)==0; int outside=(code1&code2)!=0; while(!outside&&!inside) { if (code1==0) { Swap(x1,x2); Swap(y1,y2); Swap(code1,code2); } if(code1 & 0x01) { y1+=(long)(y2-y1)*(X1-x1)/(x2-x1); x1=X1; } else if(code1 & 0x02) { x1+=(long)(x2-x1)*(Y1-y1)/(y2-y1); y1=Y1; } else if(code1 & 0x04) { y1+=(long)(y2-y1)*(X2-x1)/(x2-x1); x1=X2; } else if(code1 & 0x08) { x1+=(long)(x2-x1)*(Y2-y1)/(y2-y1); y2=Y2; } code1=OutCode(x1, y1, X1, Y1, X2, Y2); code2=OutCode(x2, y2, X1, Y1, X2, Y2); inside=(code1|code2)==0; outside=(code1&code2)!=0; } line6 (x1, y1, x2, y2); } 4.3. Определение принадлежности точки многоугольнику Пусть задан многоугольник, ограниченный не P1,P2,..., Pn самопересекающейся замкнутой ломаной, и некоторая точка A(x, y) и требуется определить, содержится ли эта точка внутри многоугольника или нет. Выпустим из точки A(x, y) произвольный луч и найдем количество точек пересечения этого луча с границей многоугольника. Если отбросить случай, когда луч проходит через какую-либо вершину многоугольника, то решение задачи тривиально - точка лежит внутри, если количество точек пересечения нечетно, и снаружи, если четно. Ясно, что для любого многоугольника можно построить луч, не проходящий ни через одну из вершин. Однако построение луча связано с определенными трудностями и, кроме того, проверка пересечения с произвольным лучом сложнее, чем с фиксированным, например горизонтальным. Возьмем луч, выходящий из точки A, и рассмотрим к чему может привести прохождение луча через вершину. Основные возможные случаи изображены на рисунке 4.3.1. В простейших случаях а и в, когда ребра, выходящие из соответствующей вершины, лежат либо по разные стороны от луча, либо по одну сторону от луча, можно договориться, что четность количества пересечений меняется в первом случае и не меняется во втором. К случаям б и г такой подход непосредственно не годится. Несколько изменим его, заметив, что в случаях а и б вершины, лежащие на луче являются экстремальными значениями в тройке вершин треугольника. В других случаях экстремума нет. Здесь и далее line - некоторая абстрактная функция, отображающая на экране линию по заданным координатам ее начала и конца. В результате приходим к следующему алгоритму. Все отрезки, кроме горизонтальных, проверяются на пересечение с горизонтальным лучом, выходящим из точки A. При попадании луча в вершину пересечение засчитывается только с теми отрезками, выходящими из вершины, для которых она является верхней. 4.4. Закраска области, заданной цветом границы Рассмотрим область, ограниченную набором пикселей заданного цвета, и точку (x, y), лежащую внутри этой области. Задача заполнения области заданным цветом в случае, когда область не является выпуклой, может оказаться довольно сложной. //File fill1.cpp void PixelFill(int x, int y, int BorderColor, int color) { int c=getpixel(x,y); if((c!=BorderColor) && (c!=color)) { putpixel(x,y,color); PixelFill(x-1,y,BorderColor,color); PixelFill(x+1,y,BorderColor,color); PixelFill(x,y-1,BorderColor,color); PixelFill(x,y+1,BorderColor,color); } } Простейший алгоритм, показанный выше, хотя и абсолютно корректно заполняющий даже самые сложные области, является слишком неэффективным, так как уже для отрисованного пикселя функция вызывается еще три раза, и, кроме того, требует слишком большого стека из-за большой глубины рекурсии. Поэтому для решения задачи закраски области предпочтительнее алгоритмы, способные обрабатывать сразу целые группы пикселей. Рассмотрим версию одного из самых популярных алгоритмов подобного типа, когда для заданной точки (x, y) определяется и [x1, xr ] заполняется максимальный отрезок, содержащий эту точку и лежащий внутри области. После этого в поисках еще не заполненных пикселей проверяются отрезки, лежащие выше и ниже. Если такие пиксели находятся, то функция рекурсивно вызывается для их обработки. Этот алгоритм эффективно работает даже для областей с дырками (рисунок 4.4.1). //File fill2.cpp #include int Color = GREEN; int LineFill(int x, int y, int dir, int PrevX1, int PrevXr) { int x1=x; int xr=x; int c; do c=getpixel(--x1,y); while((c!=BorderColor)&&(c!=Color)); do c=getpixel(++xr,y); while((c!=BorderColor)&&(c!=Color)); x1++; xr++; line(x1,y,xr,y); for(x=x1; x<=xr; x++) { c=getpixel(x,y+dir); if((c!=BorderColor) &&(c!=Color)) x=LineFill(x,y+dir,dir,x1,xr); } for(x=x1; x x++) { c=getpixel(x,y-dir); if((c!=BorderColor) &&(c!=Color)) x=LineFill(x,y-dir,-dir,x1,xr); } for(x=PrevXr; x x++) { c=getpixel(x,y-dir); if((c!=BorderColor) &&(c!=Color)) x=LineFill(x,y-dir,-dir,x1,xr); } return xr; } void Fill(int x,int y); { LineFill(x, y, 1, x, x); } main() { int driver=DETECT; int mode; int res; initgraph(&driver, &mode, УФ); if((res=graphresult())!=grOk) { printf(У\nGraphics error: %s\nФ, grapherrormsg(res)); exit(1); } circle(320,200,140); circle(260,200,40); circle(380,200,40); getch(); setcolor(Color); Fill(320,300); getch(); closegraph(); } 4.5. Пересечение произвольного луча с простейшими геометрическими объектами Эффективные алгоритмы отыскания точки пересечения произвольного луча (ближайшей к его началу) с геометрическими объектами, такими, как сферы, плоскости, призмы, пирамиды, цилиндры, конусы и так далее, часто оказываются очень полезными при рассмотрении самых разных задач компьютерной графики. Одной из таких задач - пользователей является метод трассировки лучей, в котором определение точек пересечения лучей с объектами занимает 95% вычислений, причем значительная часть расчетов падает на лучи, не пересекающие ни один из объектов. Поэтому при обработке сцены этим методом весьма желательно исключить из рассмотрения как можно раньше и как можно больше лучей, избегающих встречи с объектами сцены. Для этого поступают следующим образом: при помощи попарно непересекающихся простых поверхностей локализуют (отделяют друг от друга) сложные объекты сцены и после относительно простых вычислений находят, а затем отбрасывают те лучи, которые не имеют с этими поверхностями общих точек. Ясно, что среди отброшенных не окажется ни одного луча, который пересекал бы объекты исходной сцены. Что же касается оставшихся лучей, то, как правило, они требуют более деликатного обращения. Луч с началом в точке O, определяемой начальным вектором R0 = (x0, y0, z0) L = (l, m, n) и направляющим вектором описывается при помощи параметрического уравнения в векторной R(t) = R0 + Lt,t > форме, или координатными параметрическими уравнениями (рисунок 4.5.1) x = x0 + lt, y = y0 + mt, (t > 0), z = z0 + nt В случае, если направляющий вектор L заданного луча единичный l2 + m2 + n2 = --, параметр t имеет простой геометрический смысл: его значение t равно расстоянию от начальной точки O заданного луча до его текущей точки M(t), отвечающей этому значению параметра. 5. Алгоритмы удаления невидимых линий и поверхностей Для построения правильного изображения трехмерных объектов необходимо уметь определять, какие части объектов (ребра, грани) будут видны при заданном проектировании, а какие будут закрыты другими гранями объектов. В качестве возможных видов проектирования традиционно рассматриваются параллельное и центральное (перспективное) проектирования. Проектирование осуществляется на так называемую картинную плоскость (экран): проектирующий луч к картинной плоскости проводится через каждую точку объектов. При этом видимыми будут те точки, которые вдоль направления проектирования лежат дальше всего от картинной плоскости. Несмотря на кажущуюся простоту, эта задача является достаточно сложной и требует зачастую больших объемов вычислений. Поэтому существует ряд различных методов решения задач удаления невидимых линий, включая и методы, опирающиеся на аппаратные решения. Далее будем считать, что все объекты представлены набором выпуклых плоских граней, которые пересекаются только вдоль своих ребер. К решению задачи удаления невидимых линий и поверхностей можно выделить два основных подхода. Первый подход заключается в определении для каждого пикселя того объекта, который вдоль направления проектирования находится дальше от него. При этом работа ведется в пространстве картинной плоскости и существенно использует растровые свойства дисплея. Второй подход заключается в непосредственном сравнении объектов друг с другом для выяснения того, какие части каких объектов будут являться видимыми. В данном случае работа ведется в исходном пространстве объектов и никак не привязана к растровым характеристикам дисплея. Существует большое количество смешанных методов, объединяющих оба описанных подхода. 5.1. Отсечение нелицевых граней Рассмотрим многогранник, для каждой грани которого задан единичный вектор внешней нормали (рисунок 5.1.1.) несложно заметить, что вектор нормали грани n составляет с вектором l, определяющим направление проектирования, тупой угол, то эта грань заведомо не может быть видна. Такие грани называются нелицевыми. В случае, когда соответствующий угол является острым, грань называется лицевой. В случае параллельного проектирования условия на угол можно записать в виде (n,l) 0, поскольку направление проектирования l от грани не зависит. При центральном проектировании с центром в точке c вектор l = c проектирования для точки p будет равен - p. Для определения того, является заданная грань лицевой или нет, достаточно взять произвольную точку p этой грани и проверить условие (n,l) 0. Знак этого скалярного произведения не зависит от выбора точки грани, а определяется тем, в каком полупространстве относительно полуплоскости, содержащей данную грань, лежит центр проектирования. В случае, когда сцена представляет собой один выпуклый многогранник, удаление нелицевых граней полностью решает задачу удаления невидимых граней. В общем случае предложенный подход хотя и не решает задачу полностью, но позволяет примерно вдвое сократить количество рассматриваемых граней. 5.2. Удаление невидимых линий. Алгоритм Робертса Самым первым алгоритмом, предназначенным для удаления невидимых линий, был алгоритм Робертса, требующий, чтобы каждая грань была выпуклым многоугольником. Опишем этот алгоритм. Сначала отбрасываются все ребра, обе определяющие грани которых являются нелицевыми (ни одно из таких ребер не будет видно). Следующим шагом является проверка каждого из оставшихся ребер со всеми гранями многогранника на закрывание. Возможны следующие случаи: Х грань не закрывает ребро; Х грань полностью закрывает ребро (и оно тогда удаляется из списка рассматриваемых ребер); Х грань частично закрывает ребро (в этом случае ребро разбивается на несколько частей, из которых видимыми являются не более двух; само ребро удаляется из списка, но в этот список проверенных ребер добавляются те его части, которые не закрываются данной гранью). Если общее количество граней равно n, то временные затраты для O(n2 ) данного алгоритма составляют. Можно заметно сократить количество проверок, если воспользоваться разбиением картинной плоскости. Картинная плоскость разбивается на равные клетки, и для каждой клетки составляется список тех граней, проекции которых имеют непустое пересечение с данной клеткой (рисунок 5.2.1.) для проверки произвольного ребра сначала находятся все клетки, в которые попадает проекция этого ребра, и рассматриваются только те грани, которые содержатся в списках данных клеток. Несмотря на то, что этот вариант алгоритма требует определенных затрат для построения разбиения и соответствующих списков, при удачном выборе разбиения он имеет порядок O(n). 5.3. Алгоритм Аппеля Введем понятие так называемой количественной невидимости точки как количества лицевых граней, ее закрывающих. Точка является видимой только в том случае, когда ее количественная невидимость равна нулю. Рассмотрим, как меняется количественная невидимость вдоль ребра. Количественная невидимость точек ребра изменяется на единицу при прохождении позади так называемой контурной линии, состоящей из тех ребер, для которых одна из проходящих граней является лицевой, а другая - нелицевой. Так, для многогранника на рисунке 5.3.1 контурной линией является ломаная ABCIJDEKLGA. Для определения видимости ребер произвольного многогранники берется какая-нибудь его вершина и затем непосредственно определяется ее количественная невидимость. Далее прослеживается изменение количественной невидимости вдоль каждого из ребер, выходящих из этой вершины. Эти ребра проверяются на прохождение позади контурной линии, и в соответствующих точках их количественная невидимость изменяется. Те части отрезка, для которых количественная невидимость равна нулю, сразу рисуются. Следующим шагом является определение количественной невидимости для всех ребер, выходящих из новой вершины, и так далее. В результате, когда рассматривается изменение количественной невидимости вдоль ребра, выходящего из вершины, принадлежащей контурной линии, необходимо проверить, не закрывается ли это ребро одной из граней, выходящей из этой вершины, как, например, грань DEKJ закрывает ребро DJ. Так как для реальных объектов количество ребер, входящих в контурную линию, намного меньше общего числа ребер, то алгоритм Аппеля является более эффективным, чем алгоритм Робертса. 5.4. Удаление невидимых граней. Метод z-буфера Одним из самых простых алгоритмов удаления невидимых граней и поверхностей является метод z-буфера (буфера глубины). В силу крайней простоты этого метода часто встречаются его аппаратные реализации. Сопоставим каждому пикселю (x, y) картинной плоскости, кроме цвета, хранящегося в видеопамяти, его расстояние до картинной плоскости вдоль направления проектирования z(x, y) (его глубину). Изначально массив глубин инициализируется +. Для вывода на картинную плоскость произвольной грани она переводится в свое растровое представление на картинной плоскости и для каждого пикселя этой грани находится его глубина. В случае, если эта глубина меньше значения глубины, хранящегося в z-буфере, пиксель рисуется и его глубина заносится в z-буфер. Данный метод работает исключительно в пространстве картинной плоскости и не требует никакой предварительной обработки. 5.5. Алгоритмы упорядочения Подход заключается в таком упорядочении граней, чтобы при их выводе в этом порядке получалось корректное изображение. Для этого необходимо, чтобы более дальние грани выводились раньше, чем более близкие. Существуют различные методы построения такого упорядочения, однако часто встречаются такие случаи, когда заданные грани нельзя упорядочить. В подобных случаях необходимо произвести разбиение одной или нескольких граней, чтобы получившееся после разбиения множество граней можно было упорядочить. Метод сортировки по глубине Наиболее простым подходом к упорядочиванию граней является их сортировка по минимальному расстоянию до картинной плоскости (вдоль направления проектирования) с последующим выводом их в порядке приближения. Этот метод великолепно работает для ряда сцен, включая, например, построение изображения нескольких пересекающихся достаточно простых тел. Однако возможны случаи, когда просто сортировка по расстоянию до картинной плоскости не обеспечивает правильного упорядочения, поэтому желательно после такой сортировки проверить порядок, в котором грани будут выводиться. Предлагается следующий алгоритм этой проверки. Для простоты будем считать, что рассматривается параллельное проектирование вдоль оси Oz. Перед выводом грани P следует убедиться, что никакая другая грань Q, проекция которой на ось Oz не пересекается с проекцией грани P, не может закрываться гранью P. И если это условие выполнено, то грань P должна быть выведена раньше. Предлагаются следующие тестов в порядке возрастания сложности проверки: 1. Пересекаются ли проекции этих граней на ось Ox? 2. Пересекаются ли их проекции на ось Oy? 3. Находится ли грань P по другую сторону от плоскости, проходящей через грань Q, чем начало координат (наблюдатель)? 4. Находится ли грань Q по ту же сторону от плоскости, проходящей через грань P, что и начало координат (наблюдатель)? 5. Пересекаются ли проекции этих граней на картинную плоскость? Если хотя бы на один из этих вопросов получен отрицательный ответ, то считаем, что эти две грани - P и Q упорядочены верно, и сравниваем P со следующей гранью. В противном случае считаем, что эти грани необходимо поменять местами, для чего проверяются следующие тесты: Находится ли грань Q по другую сторону от плоскости, проходящей через грань P, чем начало координат? Находится ли грань P по ту же сторону от плоскости, проходящей через грань Q, что и начало координат? В случае если ни один из этих тестов не позволяет с уверенностью решить, какую из этих двух граней нужно выводить раньше, то одна из них разбивается плоскостью, проходящей через другую грань. В этом случае вопрос об упорядочении оставшейся грани и частей разбитой грани легко решается. Метод двоичного разбиения пространства Существует другой, крайне элегантный способ упорядочивания граней. Рассмотрим некоторую плоскость в объектном пространстве. Она разбивает множество всех граней на два непересекающихся множества (кластера), в зависимости от того, в каком полупространстве относительно плоскости эти грани лежат (будет считать, что плоскость не пересекает ни одну из этих граней). При этом очевидно, что ни одна из граней, лежащих в полупространстве, не содержащем наблюдателя, не может закрывать собой ни одну из граней, лежащих в том же полупространстве, что и наблюдатель. Тем самым сначала необходимо вывести грани из дальнего кластера, а затем уже и из ближнего. Применим подобную технику для упорядочения граней внутри каждого кластера. Для этого построим разбиение граней каждого кластера на два множества очередной плоскостью, а затем для вновь полученных граней повторим процесс разбиения, и будем поступать так до тех пор, пока в каждом получившемся кластере останется не более одной грани (рисунок 5.5.1). Обычно в качестве разбивающей плоскости рассматривается плоскость, проходящая через одну из граней (на самом деле при этом множество разбивается на 4 класса - лежащих на плоскости, пересекающих ее, лежащих в положительном полупространстве и лежащих в отрицательном полупространстве относительно этой плоскости). Все грани, пересекаемые этой плоскостью, разобьем вдоль этой плоскости. В результате мы приходим к дереву разбиения пространства, узлами которого являются грани. При этом слева от узла будет вершина поддерева граней, лежащих в положительном полупространстве, а справа вершина поддерева граней отрицательного полупространства. Процесс построения дерева заключается в выборе грани, проведении через нее плоскости и разбиении множества всех граней. В этом процессе присутствует определенный произвол в выборе очередной грани. Существует два основных критерия для выбора: Х получить как можно более сбалансированное дерево; Х минимизировать количество разбиений. К сожалению, эти критерии, как правило, являются взаимоисключающими, поэтому выбирается некоторый компромиссный вариант. После того, как это дерево построено, осуществляется построение изображения в зависимости от используемого проектирования. Одним из основных преимуществ этого метода является его полная независимость от положения центра проектирования, что делает его крайне удобным для построения серий изображений одной и той же сцены из разных точек наблюдения. 5.6. Метод построчного сканирования Метод построчного сканирования является одним из примеров метода, работающего в пространстве картинной плоскости. Однако вместо того, чтобы решать задачу удаления невидимых граней для проекций объектов на картинную плоскость, сведем ее к серии простых одномерных задач. Все изображение на картинной плоскости можно представить как ряд горизонтальных (вертикальных линий) пикселей. Рассмотрим сечение сцены плоскостью, проходящей через такую линию и центр проектирования. Пересечение этой плоскости с объектами сцены будет множество непересекающихся (за исключением концов) отрезков, которые и необходимо спроектировать. Задача удаления невидимых частей для такого набора отрезков решается тривиально. Рассматривая задачу удаления невидимых граней для каждой такой линии, мы тем самым разбиваем исходную задачу на набор гораздо более простых задач. Подобные алгоритмы с успехом используются для создания компьютерных игр. 5.7. Алгоритм Варнака Алгоритм Варнака является еще одним примером алгоритма, основанного на разбиении картинной плоскости на части, для каждой из которых исходная задача может быть решена достаточно просто. Разобьем видимую картинную плоскость на четыре равные части. В случаях, когда часть картинной плоскости полностью накрывается проекцией ближайшей грани и часть не накрывается проекцией ни одной грани вопрос о закрашивании соответствующей части решается тривиально. В случае, когда ни одно из этих условий не выполнено, данная часть разбивается на 4 части, для каждой из которых проверяется выполнение этих условий, и так далее. Очевидно, что разбиение имеет смысл проводить до тех пор, пока размер части больше, чем размер пикселя. В противном случае для части размером в один пиксель явно находится ближайшая грань и осуществляется закрашивание. 6. Аппроксимация кривых и поверхностей Историю сплайнов принято отсчитывать от момента первой работы Шенберга в 1946 году. Сначала сплайны рассматривались как удобный инструмент в теории и практике приближения функций. Однако довольно скоро область их применения начала стремительно расширяться и обнаружилось, что существует очень много сплайнов самых разных типов. Сплайны стали активно использоваться в численных методах, в системах автоматического проектирования и автоматизации научных исследований, во многих других областях человеческой деятельности и, конечно, в компьютерной графике. Сам термин сплайн происходит от английского spline. Именно так называется гибкая полоска стали, при помощи которой чертежники проводили через заданные точки плавные кривые. В былые времена подобный способ построения плавных обводов различных тел, таких, как, например, корпус корабля, кузов автомобиля, а потом крыло или фюзеляж самолета, был довольно широко распространен в практике машиностроения. В результате форма тела задавалась при помощи очень точно изготовленных сечений - плазов. Появление компьютеров позволило перейти от этого, плазовоЦшаблонного, метода к более эффективному способу задания поверхности обтекаемого тела. В основе этого подхода к описанию поверхностей лежит использование сравнительно несложных формул, позволяющих восстанавливать облик изделия с необходимой точностью. Ясно, что для большинства тел, встречающихся на практике, вряд ли возможно отыскание простых универсальных формул, которые описывали бы соответствующую поверхность глобально, то есть, как принято говорить, в целом. Это означает, что при решении задачи построения достаточно произвольной поверхности обойтись небольшим количеством формул, как правило не удается. Вместе с тем аналитическое описание (описание посредством формул) внешних обводов изделия, то есть задание в трехмерном пространстве двумерной поверхности, должно быть достаточно экономным. Это особенно важно, когда речь идет об обработке изделий на станках с числовым программным управлением. Обычно поступают следующим образом: задают координаты сравнительно небольшого числа опорных точек, лежащих на искомой поверхности, и через эти точки проводят плавные поверхности. Именно так поступает конструктор при проектировании кузова автомобиля (ясно, что на этой стадии процесс проектирования сложного объекта содержит явную неформальную составляющую). На следующем шаге конструктор должен получить аналитическое представление для придуманных кривых или поверхностей. Вот для таких задач и используются сплайны. Средства компьютерной графики, особенно визуализация, существенно помогают при проектировании, показывая конструктору, что может получиться в результате, и давая ему многовариантную возможность сравнить это с тем, что сложилось у него в голове. Достаточно типичной является следующая задача: по заданному массиву точек плоскости (2D) или в пространстве (3D) построить кривую либо проходящую через все эти точки (задача интерполяции), либо проходящую вблизи от этих точек (задача сглаживания). Совершенно естественно возникают вопросы: 1. В каком классе кривых искать решение поставленной задачи? 2. Как искать? 6.1. Сплайн - функции Случай одной переменной Обратимся для определенности к задаче интерполяции и начнем рассмотрение с обсуждения правил выбора класса кривых. Ясно, что допустимый класс кривых должен быть таким, чтобы решение задачи было единственным (это обстоятельство сильно помогает в преодолении многих трудностей поиска). Кроме того, желательно, чтобы построенная кривая изменялась плавно. Пусть на плоскости задан набор точек (xi, yi ),i = 0,1,..., m, таких, что x0 < x1 <... < xm -1 < xm. То обстоятельство, что точки заданного набора занумерованы в порядке возрастания их абсцисс, позволяет искать кривую в классе графиков функций. В данном случае ограничимся поиском решения в виде многочлена. Как известно из курса математического анализа, существует интерполяционный многочлен Лагранжа m m m (x) Lm (x) = yi (x - x ), где (x) =, m j (x - xi )m (xi ) i =0 j = график которого проходит через все заданные точки (xi, yi ),i = 0,1,..., m. Это обстоятельство и простота описания (заметим, что многочлен однозначно определяется набором своих коэффициентов в данном случае их число совпадает с количеством точек в заданном наборе) являются несомненными достоинствами построенного интерполяционного многочлена. Однако полезно остановиться на некоторых недостатках предложенного подхода. 1. Степень многочлена Лагранжа на единицу меньше числа заданных точек. Поэтому, чем больше точек задано, тем выше степень такого многочлена. И хотя график интерполяционного многочлена Лагранжа всегда будет проходить через все точки массива, его уклонение (от ожидаемого) может оказаться довольно значительным. 2. Изменение одной точки (ситуация, довольно часто встречаемая на практике) требует полного пересчета коэффициентов интерполяционного многочлена и к тому же может существенно повлиять на вид задаваемой им кривой. Приближающую кривую можно построить и совсем просто если последовательно соединить точки заданного набора прямолинейными отрезками, то в результате получится ломаная. При такой, кусочно линейной, интерполяции требуется найти всего 2m чисел (каждый прямолинейный отрезок определяется ровно двумя коэффициентами), но, к сожалению, построенная таким образом апроксимирующая кусочно-линейная функция не обладает нужной гладкостью: уже первая производная этой функции терпит разрывы в узлах интерполяции. Рассмотрев эти две крайние ситуации, попробуем найти класс функций, которые в основном сохранили бы перечисленные выше достоинства обоих подходов и одновременно были бы в известной степени свободны от их недостатков. Для этого поступим так: будем использовать многочлены (как и в первом случае) и строить их последовательно, звено за звеном (как во втором случае). В результате получится так называемый полиномиальный многозвенник. При подобном подходе важно правильно выбрать степени привлекаемых многочленов, а для плавного изменения результирующе кривой необходимо еще тщательно подобрать коэффициенты многочленов (из условий гладкого сопряжения соседних звеньев). То, что получится в результате описанных усилий, называют сплайн-функциями или просто сплайнами. Для того, чтобы понять, какое отношение имеют сплайн-функции к чертежным сплайнам, возьмем гибкую стальную линейку, поставим ее на ребро и, закрепив один из концов в заданной точке, поместим ее между опорами, которые располагаются в плоскости Oxy в точках (xi, yi ),i = 0,1,..., m x0 < x1 <... < xm -1 < xm. , где Интересно отметить, что функция y=S(x), описывающая профиль линейки, обладает следующими интересными свойствами: Х с довольно большой точностью часть графика этой функции, заключенную между любыми двумя соседними опорами можно считать многочленом третьей степени; Х на всем промежутке [x0, xm ] функция y=S(x) дважды непрерывно дифференцируема. Построенная функция S(x) относится к так называемым интерполяционным кубическим сплайнам. Этот класс в полной мере удовлетворяет высказанным выше требованиям и обладает еще целым рядом замечательных свойств. Перейдем однако к точным формулировкам. Интерполяционным кубическим сплайном называется функция S(x), обладающая следующими свойствами: 1. График этой функции проходит через каждую точку заданного массива, S (xi ) = yi,i = 0,1,..., m ; 2. На каждом из отрезков [xi, xi +1],i = 0,1,..., m -, функция j S(x) = aij (x - xi ) является многочленом третьей степени, ; j = 3. На всем отрезке [x0, xm ] функция S(x) имеет непрерывную вторую производную. [xi, xi +1] Так как на каждом из отрезков функция S(x) определяется четырьмя коэффициентами, то для его полного построения на всем отрезке задания необходимо найти 4m чисел. Третье условие будет выполнено, если потребовать непрерывности сплайна во всех внутренних узлах xi,i = 1,..., m - (это дает m-1 условий на коэффициенты), а также его первой (m-1 условий) и второй (еще m- условий) производных в этих узлах. Вместе с первым условием получаем m-1+m-1+m-1+m+1=4m-2 равенства. Недостающие два условия для полного определения коэффициентов можно получить, задав, например, значения первых производных на концах отрезка [x0, xm ] S`(x0 ) = l0, S`(xm ) = lm. (граничные условия): Существуют граничные условия и других типов. Случай двух переменных Более сложная задача построения по заданному набору точек в трехмерном пространстве интерполяционной функции двух переменных решается похожим образом. Расскажем прежде всего, что такое интерполяционный бикубический сплайн. (xi, y ) Пусть на плоскости задан набор из (m+1)(n+1) точек, j i = 0,1,..., m; j = 0,1,..., n x0 < x1 <... < xm -1 < xm, y0 < y1 <... < yn-1 < yn. , где (xi, y ) zij Добавим к каждой паре третью координату -- j (xi, y, zij ). j (xi, y, zij ) i = 0,1,..., m; j = 0,1,..., n Тем самым получаем массив,. j Прежде чем строить поверхность, проходящую через все точки заданного массива, определим функцию, графиком которой будет эта поверхность. Интерполяционным бикубическим сплайном называется функция двух переменных S(x, y), обладающая следующими свойствами: 1. График этой функции через каждую точку заданного массива, S (xi, y ) = zij,i = 0,1,..., m; j = 0,1,..., n ; j 2. На каждом частичном прямоугольнике [xi, xi +1][y, y ],i = 0,1,..., m -1; j = 0,1,..., n -, функция представляет j j + собой многочлен третьей степени по каждой из переменных, ij S(x, y) = alk (x - xi )l ( y - y )k ; j l,k = 3. На всем прямоугольнике задания [x0, xm ][y0, yn] функция S(x, y) имеет по каждой переменной непрерывную вторую производную. {(xi, y, zij )} Для того, чтобы построить по заданному массиву j интерполяционный бикубический сплайн, достаточно определить все 16mn коэффициентов. Как и в одномерном случае, отыскание коэффициентов сплайн-функции сводится к построению решения системы линейных уравнений, связывающих искомые коэффициенты ij alk. Эта система возникает из первого и третьего условий после добавления к ним недостающих соотношений путем задания значений производной искомой функции в граничных узлах прямоугольника [x0, xm ][y0, yn] (или иных соображений). Подведем некоторые итоги. Достоинства предложенного способа несомненны: для решения линейных систем, возникающих в ходе построения сплайн-функции, существует много эффективных методов, к тому же эти системы достаточно просты; графики построенных сплайн-функций проходят через все заданные точки, полностью сохраняя первоначально заданную информацию. Вместе с тем изменение лишь одной точки (случай на практике довольно типичный) при описанном подходе заставляет пересчитывать заново, как правило, все коэффициенты. К тому же во многих задачах исходный набор точек задается приближенно и, значит, требование неукоснительного прохождения графика искомой функции через каждую точку этого набора оказывается излишним. От этих недостатков свободны некоторые из методов сглаживания, к описанию которых мы и переходим. Но прежде всего мы значительно расширим классы, в которых будет вестись поиск соответствующих кривых и поверхностей. Более точно, мы откажемся от требования однозначного проектирования искомой кривой на координатную ось, а поверхности - на координатную плоскость. Такой подход позволяет ослабить и требования к задаваемому массиву. Начнем как и прежде с кривых. 6.2. Сплайновые кривые Нам будет удобно пользоваться параметрическими уравнениями кривой. Напомним необходимые понятия. Параметрически заданной кривой называется множество точек M(x, y, z), координаты x, y, z которых определяются соотношениями, x = x(t), y = y(t), z = z(t), a t b, где x(t), y(t), z(t) - функции, непрерывные на отрезке [a,b]. Эти соотношения называются параметрическими уравнениями кривой. Без ограничения общности можно считать, что a=0 и b=1; этого всегда можно добиться при помощи замены вида t - a u =. b - a Полезна векторная форма записи параметрических уравнений r = r(t),0 t, где r(t)=(x(t), y(t), z(t)). Параметр t задает ориентацию параметризированной кривой (порядок прохождения точек при монотонном возрастании параметра). r`(t) Кривая называется регулярной кривой, если в каждой ее точке. Это означает, что в каждой точке кривой существует касательная к ней и эта касательная меняется непрерывно вслед за перемещающейся вдоль кривой ее текущей точки (рисунок 6.2.1). Единичный вектор касательной к кривой равен r`(t) T (t) =. r`(t) Если дополнительно потребовать, чтобы задающая кривую векторная функция имела вторую производную, то будет определен вектор кривизны кривой [r`(t) r``(t)] r`(t) K(t) =, модуль которого характеризует степень ее r`(t) отклонения от прямой. В частности, если -- отрезок прямой, то K=0. Кривые Безье Рассмотрим некоторые подходы к построению сглаживающей кривой. Пусть на плоскости или в пространстве задан упорядоченный набор точек, определяемых векторами V0,V1,...,Vm (рисунок 6.2.2). Ломаная V0V1...Vm называется контрольной ломаной, порожденной массивом V = {V0,V1,...,Vm} (рисунок 6.2.3). Кривой Безье, определяемой массивом V, называется кривая, определяемая векторным уравнением m r(t) = Ci ti (1- t)m-iVi,0 t 1, m i= m! i Cm = где - коэффициенты в i!(m - i)! разложении бинома Ньютона (число сочетаний из m элементов по i). Кривая Безье обладает замечательными свойствами: Х она является гладкой; V0 Vm Х начинается в точке и заканчивается в точке, касаясь при V0V1 Vm-1Vm этом отрезков и контрольной ломаной; i Cmti (1- t)m-i Х функциональные коэффициенты при вершинах Vi, i=0, 1, Е, m, суть универсальные многочлены (многочлены Бернштейна); они неотрицательны и их сумма равна единице. Поэтому кривая Безье целиком лежит в выпуклой оболочке, порождаемой массивом (рисунок 6.2.4). Далее приведена программа изображающая кривую Безье на основе введенных количества и координат опорных точек. //File Bezie.cpp #include int * YBas; int Count; double t_Step; void DrawCurve (void) { long fact1,fact2=1,fact3; double SumX; double SumY; long double coeff; double Newton; int i,j; for (i=0; i<=Count; i++) putpixel(XBas[i],YBas[i],LIGHTGREEN); for(j=1; j<=Count; j++) fact2*=j; moveto(XBas[0]+1,YBas[0]); setcolor(LIGHTRED); for (double Param=t_Step; Param<=1; Param+=t_Step) { SumX=0; SumY=0; for (i=0; i<=Count; i++) { fact1=1; fact3=1; for(j=1; j<=i; j++) fact1*=j; for(j=1; j<=Count-i; j++) fact3*=j; Newton=fact2/(fact1*fact3); coeff=Newton*pow(Param,i)*pow((1 Param),(Count-i)); SumX+=coeff*XBas[i]; SumY+=coeff*YBas[i]; } lineto(SumX,SumY); }; }; void main (void) { cout<"Please enter number of values: "; cin>>Count; cout XBas=new int[Count]; YBas=new int[Count]; for (int i=0; i i++) { cout<"Please enter X coord of point number " cin>>XBas[i]; cout cout<"Please enter Y coord of point number " cin>>YBas[i]; cout } Count--; cout<"Please enter step of parameter:"; cin>>t_Step; cout int driver=DETECT; int mode; int res; initgraph(&driver,&mode,""); if ((res=graphresult())!=grOk) { cout<"**ERROR:" exit(EXIT_FAILURE); } DrawCurve(); getch(); closegraph(); delete XBas; delete YBas; }; При m=3 получаем (элементарную) кубическую кривую Безье, V0,V1,V2,V определяемую четверкой точек и описываемую параметрическим уравнением r(t) = (((1- t)V0 + 3tV1)(1- t) + 3t V2 )(1- t) + t3V3 0 t,. Порядок точек в заданном наборе существенно влияет на вид даже элементарной кривой Безье. Находясь в одной и той же выпуклой оболочке и пытаясь повторить контрольную ломаную в гладком варианте, при разном порядке опорных точек, кривые будут иметь совершенно разный вид. Наряду с отмеченными достоинствами кривые Безье обладают и определенными недостатками: Х степень функциональных коэффициентов напрямую связана с количеством точек в заданном наборе Х при добавлении хотя бы одной точки в заданный набор необходимо провести полный пересчет функциональных коэффициентов в параметрическом уравнении кривой; Х изменение хотя бы одной точки приводит к заметному изменению вида всей кривой. В практических вычислениях часто оказывается удобным пользоваться кривыми, составленными из элементарных кривых Безье, как правило кубических. Геометрически непрерывные кривые При построении кривой из определенным образом подобранных фрагментов важна не только регулярность самих этих фрагментов, но и выполнение некоторых условий гладкости в точках их состыковки. Только в этом случае составная кривая, получающаяся в результате проведенных построений, будет обладать достаточно хорошими геометрическими характеристиками. Однако при построении составных кривых часто приходится сталкиваться с ситуацией, когда каждый из регулярных фрагментов, участвующих в создании новой кривой, имеет свою собственную параметризацию. Чтобы учесть это обстоятельство, удобно использовать класс так называемых геометрически непрерывных кривых. G1- Составная кривая называется (геометрически) непрерывной, если вдоль этой кривой единичный вектор ее касательной изменяется G непрерывно, и - (геометрически) непрерывной, если вдоль этой кривой изменяется непрерывно, кроме того, и вектор кривизны. Обратимся к рассмотрению составных кривых Безье. Составная кубическая кривая Безье представляет собой 1,..., m объединение элементарных кубических кривых Безье, таких, ri (1) = ri +1(0), i = 0,..., m - 1 r = ri (t),0 t что, где - параметрическое i уравнение кривой. Чтобы составная кривая Безье, определяемая набором вершин V0,V1,...,Vm-1,Vm, G1- была непрерывной кривой, необходимо, чтобы каждые три V3i-1,V3i,V3i+ точки, этого набора лежали на одной прямой; была замкнутой G1- непрерывной кривой, необходимо, кроме V0 = Vm того, чтобы совпадали первая и последняя точки, и три точки Vm-1,Vm = V0,V лежали на одной прямой; G была - непрерывной кривой, необходимо, чтобы каждые пять V3i-2,V3i-1,V3i,V3i+1,V3i+ точек заданного набора лежали в одной плоскости. Существуют и другие классы кривых, сохраняющие достоинства кривых Безье, но лишенные их недостатков. 7. Освещение и методы закраски Следующим шагом на пути создания реалистических изображений является проблема закрашивания поверхностей, ограничивающих построенные объекты. Мы остановимся на описании некоторых простейших моделей, требующих сравнительно небольших вычислительных затрат. Световая энергия, падающая на поверхность от источника света, может быть поглощена, отражена и пропущена. Количество поглощенной, отраженной и пропущенной энергии зависит от длины световой волны. При этом цвет поверхности объекта определяется количеством поглощаемыми длинами волн. Свойства отраженного света зависят от формы и направления источника света, а также от ориентации освещаемой поверхности и ее свойств. Свет, отраженный от объекта, может быть диффузным и зеркальным: диффузно отраженный свет рассеивается равномерно по всем направлениям, зеркально отражение происходит от внешней поверхности объекта. Свет точечного источника отражается от идеального рассеивателя по закону косинусов Ламберта: I = Ilkd cos,0, (1) где I - интенсивность отраженного света; Il - интенсивность точечного источника; kd - коэффициент диффузного отражения (постоянная величина 0 kd ); - угол между направлением на источник света и (внешней) нормалью к поверхности (рисунок 7.1). На объекты реальных сцен падает еще и рассеянный свет, соответствующий отражению света от других объектов. Поскольку точный расчет рассеянного освещения требует значительных вычислительных затрат, в компьютерной графике при вычислении интенсивности поступают так: I = Iaka + Ilkd cos,0, (2) Ia где - интенсивность рассеянного света; ka - постоянный коэффициент диффузного отражения 0 ka рассеянного света,. Интенсивность света, естественно, зависит от расстояния d от объекта до источника света. Для того, чтобы учесть это, пользуются следующей моделью освещения: Ilkd I = Iaka + cos, (3) d + K где K - произвольная постоянная. Интенсивность зеркально отраженного света зависит от угла падения, длины волны и свойств вещества. Так как физические свойства зеркального отражения довольно сложны, то в простых моделях освещения обычно пользуются следующей эмпирической моделью (моделью Фонга): p Is = Ilks cos, (4) ks где - экспериментальная постоянная; - угол между отраженным лучом и вектором наблюдения; p - степень, аппроксимирующая пространственное распределение света (рисунок 7.2). Объединяя последние две формулы, получаем модель освещения (функцию закраски), используемую для расчета интенсивности (или тона) точек поверхности объекта (или пикселей изображения): Il p I = Iaka + (kd cos + ks cos ). (5) d + K Функцию закраски, используя единичные векторы внешней нормали n, а также единичные векторы, определяющие направления: на источник света (вектор l), отраженного луча (вектор r) и наблюдения (вектор s), можно записать в следующем виде: Il p I = Iaka + (kd (n 1) + ks (r s) ). (6) d + K Чтобы получить цветное изображение, необходимо найти функции закраски для каждого из трех основных цветов - красного, зеленого и синего. Поскольку цвет зеркально отраженного света определяется ks цветом падающего, то постоянная считается одинаковой для каждого из этих цветов. Если источников света несколько, скажем m, то модель освещения определяется так m Il j j I = Iaka + (kd cos + ks cosp ) j j. (7) d + K j= Если освещаемая поверхность в рассматриваемой точке гладкая (имеет касательную плоскость), то вектор внешней нормали вычисляется непосредственно. В случае многогранной поверхности векторы внешних нормалей можно найти только для ее граней. Что касается направлений векторов внешних нормалей на ребрах и в вершинах этой поверхности, то их значения можно найти только приближенно. Пусть многогранная поверхность задана своими вершинами (рисунок 7.3). Тогда векторы, определяющие направления приближенных внешних нормалей в ее вершинах можно найти, используя векторные произведения, построенные на векторах, идущих вдоль ребер, исходящих из соответствующих вершин. Например, для V того, чтобы определить внешнюю нормаль в вершине, необходимо V1V2 V1V3,V1V3 V1V4,V1V4 V1V сложить векторные произведения. Если перед сложением найденные векторные произведения нормировать, то полученная сумма будет отличаться от предыдущей и по длине, и по направлению. Рассмотрим произвольную сцену, составленную из полигональных (многогранных) фигур. Определение освещенности для каждой видимой точки каждой грани каждой фигуры. требует гигантских расчетов. Простейший способ построения сцены заключается в том, что на каждой из граней выбирается по точке, для нее определяется освещенность, и затем вся грань закрашивается с использованием найденной освещенности. Предложенный алгоритм обладает, однако, одним большим недостатком - полученное изображение имеет неестественный многогранный вид. Это объясняется тем, что определяемая подобным образом освещенность сцены не является непрерывной величиной, а имеет кусочно-постоянный характер. Существуют специальные методы закрашивания, позволяющие создавать иллюзию гладкости. Рассмотрим два из них. 7.1. Закраска методом Гуро Наиболее простым методом является метод Гуро, который основывается на определении освещенности грани в ее вершинах с последующей билинейной интерполяцией получившихся величин на всю грань. Обратимся к рисунку 7.1.1, на котором изображена выпуклая четырехугольная грань. Предположим, что интенсивности в ее вершинах IV, IV, IV, IV. V1,V2,V3,V известны и равны соответственно 1 2 3 Пусть W - произвольная точка грани. Для определения интенсивности (освещенности) в этой точке проведем через нее горизонтальную прямую. Обозначим через U и V точки пересечения проведенной прямой с границей грани. Будем считать, что интенсивность на отрезке UV изменяется линейно, то есть IW = (1 - t)IU + tIV, где UW t =,0 t 1. UV Для определения интенсивности в точках U и V вновь воспользуемся линейной интерполяцией, также считая, что вдоль каждого из ребер границы интенсивность изменяется линейно. Тогда интенсивность в точках U и V вычисляется по формулам IU = (1 - u)IV + uIV, IV = (1 - v)IV + uIV, где 4 1 4 V4U V1V u =,0 u 1, v =,0 v 1. V4V1 V1V Метод Гуро обеспечивает непрерывное изменение интенсивности при переходе от одной грани к другой без разрывов и скачков. Еще одним преимуществом этого метода является его инкрементальный характер: грань рисуется в виде набора горизонтальных отрезков, причем так, что интенсивность последующего пикселя отрезка отличается от интенсивности предыдущего на величину постоянную для данного отрезка. Кроме того, при переходе от отрезка к отрезку значения интенсивности в его концах также изменяются линейно. Таким образом, процесс рисования грани слагается из следующих шагов: 1. Проектирование вершин грани на экран. 2. Отыскание интенсивностей в вершинах по формуле (3). 3. Определение координат концов очередного отрезка и значений интенсивности в них линейной интерполяцией. 4. Рисование отрезка с линейным изменением интенсивности между его концами. При определении освещенности в вершине, естественно, встает вопрос о выборе нормали. Часто в качестве нормали к вершине выбирается нормированная сумма нормалей прилегающих граней a1n1 +... + ak nk n = a1n1 +... + ak nk, где a1,..., ak - произвольные весовые коэффициенты. 7.1. Закраска методом Фонга Как и описанный выше метод закраски Гуро, закраска Фонга при расчете интенсивности также опирается на интерполирование. Однако в отличие от метода Гуро здесь интерполируется не значение интенсивности по уже известным ее значениям в опорных точках, а значение вектора внешней нормали, которое затем используется для вычисления интенсивности пикселя. Поэтому закраска Фонга требует заметно большего объема вычислений. Правда, при этом и изображение получается более близким к реалистичному (в частности, при закраске Фонга зеркальные блики выглядят довольно правдоподобно). Метод Фонга заключается в построении для каждой точки вектора, играющего роль вектора внешней нормали, и использовании этого вектора для вычисления освещенности в рассматриваемой точке по формуле (5). При этом схема интерполяции, используемая при закраске Фонга, аналогична интерполяции в закраске Гуро. nW Для определения вектора нормали в точке W проводим через эту точку горизонтальную прямую и, используя значения векторов nU nV нормалей и в точках ее пересечения U и V с ребрами грани, получаем (1 - t)nU + tnV nw = (1 - t)nU + tnV, где UW t =, UV а векторы внешних нормалей в точках U и V находятся, в свою очередь (также линейной интерполяцией), по векторам нормалей в концевых точках соответствующих ребер рассматриваемой многоугольной грани: nU = (1 - u)nV + unV, nV = (1 - v)nV + vnV, где 4 1 1 V4U V1V u = v = V4V1, V1V2. nW Нормирование вектора необходимо вследствие того, что в формулах (1)-(5) используется единичный вектор нормали. Как и метод Гуро метод Фонга также в значительной степени носит инкрементальный характер. Применяя метод Фонга, мы фактически строим на многогранной модели непрерывное поле единичных векторов, использование которого в качестве поля внешних нормалей обеспечивает гладкость получаемого изображения. Ясно, что требования к качеству изображения напрямую связаны с точностью рассматриваемой модели и объемом соответствующих ей вычислений. Несомненным достоинством предложенных моделей закраски (Гуро и Фонга) является их сравнительная простота. Однако вследствие значительных упрощений получаемый результат не всегда оказывается удовлетворительным. Этот барьер качества преодолевается с помощью более совершенных (и дорогостоящих по вычислениям) методов, например, с помощью метода трассировки лучей и его вариаций. 8. Когнитивная графика Несмотря на гигантское количество разработанных алгоритмов и многообразие программных продуктов, трехмерная (да и любая другая) графика остается областью широкого использования ручного труда. Это труд дизайнеров, инженеров, архитекторов, проектировщиков, художников. Словом, всех тех, кто изо дня в день сидит за компьютером и при помощи мыши, графического планшета или любого другого устройства ввода чертит, рисует, создает графические композиции. Можно ли облегчить их труд, уменьшить количество затрачиваемого времени, повысить производительность труда, снизить затраты, наконец? Ведь немалая часть звеньев технологических цепочек (т.е. технологических операций, ТО), в которых участвуют вышеперечисленные профессии давно сокращена либо вовсе исчезла благодаря автоматизации. Например, если раньше после проектирования какого-нибудь здания требовалось составить план работ, смету затрат, перечень необходимых материалов (а ведь еще надо рассчитать требуемое количество!), то теперь архитектору достаточно сделать необходимые чертежи в системе автоматизированного проектирования (САПР), а дальше компьютер сам составит необходимую сопроводительную документацию. Итак, что можно сделать для дальнейшей автоматизации? Рассмотрим структуру любого звена любой технологической цепочки. Есть входные данные и есть выходные данные, получаемые в результате обработки входных7. Процесс преобразования входных данных в выходные, разумеется, контролируется и управляется кем-то или чем-то. В качестве контролера может выступать человек, машина или даже закон природы. Поэтому любая задача автоматизации формулируется в упрощенном виде так: необходимо заменить контролера-человека контролером-машиной. Вернемся к графике. Выходными данными для интересующих нас ТО является графический материал либо некая информация, на основе которой потом можно этот графический материал восстановить уже без вмешательства человека. А что является входными данными? Для проектировщика Ч техническое задание, для художника мультипликатора Ч сценарий и указания режиссера. В обоих случаях входные данные представлены на естественном языке и являются по сути некоторым описанием. Отсюда сразу становится понятно направление дальнейшей автоматизации. Необходимо научить компьютер понимать описание объектов и сцен и создавать на их основе изображения. Разумеется, понятие данные здесь весьма условно. Это может быть и железо для ковки, и яблоки для компота. Но суть от этого не меняется Ч есть вход, есть выход и есть процесс. Такой способ получения изображений называется когнитивной (описательной) графикой. На сегодняшний день когнитивная графика еще не имеет полноценной практической реализации. Разработчики сталкиваются здесь с теми же проблемами, что и при создании программ переводчиков. Естественный язык очень плохо поддается формализации (так как с точки зрения теории формальных систем он неточен, неоднозначен, избыточен и так далее), к тому же нередко значение отдельных слов или фраз меняется в зависимости от общего контекста. А если учесть, что даже человек не всегда адекватно интерпретирует отдельные предложения, сложность задачи возрастает многократно. Добавив к перечисленному необходимость наделения компьютера воображением и линициативой для заполнения пробелов в описании, мы получаем действительно интересную задачу, решение которой Ч дело ближайших пяти или даже десяти лет. В мощных графических студиях, таких как Maya, существуют модули когнитивной графики, но они являются скорее демонстрацией потенциальных возможностей такого решения, игрушкой для энтузиастов, чем реальным рабочим инструментом. 9. Хранение графических данных Графические данные традиционно подразделяются на два класса: векторные и растровые. В компьютерной графике векторные данные обычно используют для представления прямых, многоугольников и кривых (или любых объектов, которые могут быть созданы на их основе) с помощью определенных в численном виде контрольных (ключевых) точек. Программа воспроизводит линии посредством соединения ключевых точек. С векторными данными всегда связана информация об атрибутах (например, цвете и толщине линии) и набор соглашений (или правил), позволяющий программе начертить требуемые объекты. Растровые данные представляют собой набор числовых значений, определяющих цвета отдельных пикселей. Обычно говорят, что растр - это массив пикселей, хотя технически растр является массивом числовых значений, задающих, окрашивающих или включающих соответствующие пиксели при отображении образа на устройстве вывода. 9.1. Алгоритмы сжатия данных Сжатие - это процесс, применяемый для уменьшения физического размера блока информации. Работая с компьютерной графикой, мы заинтересованы в том, чтобы уменьшить размер блока графических данных и таким образом поместить в заданное физическое пространство больше информации. Сжатие можно применять и для того, чтобы помещать большие изображения в блок памяти заданного размера. Существует множество алгоритмов сжатия графической информации, однако наиболее часто применяются лишь несколько из них. Большинство распространенных схем являются вариантами методов: Х группового кодирования (RLE); Х Лемпела - Зива - Велча (LZW); Х CCITT (один из типов этого сжатия является вариантом сжатия по алгоритму Хаффмена); Х дискретный косинус-преобразований (DCT), применяемого в JPEG-сжатии; Х JBIG; Х ART; Х фрактального сжатия. Сжатие растровых, векторных и метафайловых данных осуществляется по-разному. В растровых файлах сжимаются только данные изображения; заголовок и все остальные данные (таблица цветов, концовка и так далее) всегда остаются несжатыми. Векторные файлы сжимаются редко, так как представление данных изображения в компактной форме заложено в основу любого векторного формата. Схемы сжатия, применяемые в метафайлах, часто похожи на схемы, используемые для сжатия растровых изображений. Их выбор зависит от содержащейся в метафайле информации. Важно уяснить, что алгоритмы сжатия не описывают определенный дисковый файловый формат. Алгоритмы сжатия определяют только способ кодирования данных, но не формат их записи на диск. Групповое кодирование (RLE) Групповое кодирование - алгоритм сжатия данных, поддерживаемый большинством растровых файловых форматов, таких как TIFF, BMP и PCX. Алгоритм RLE позволяет сжимать данные любых типов, невзирая на содержащуюся в них информацию. Однако сама информация влияет на полноту сжатия. Хотя большинство алгоритмов RLE не могут достигать высокой степени сжатия, характерной для более совершенных алгоритмов, но групповое кодирование легко и быстро выполняется, являясь хорошей альтернативой применению сложных алгоритмов сжатия или отказу от использования таковых вообще. RLE уменьшает физический размер повторяющихся строк символов. Такие повторяющиеся строки, называемые группами, обычно кодируются в двух байтах. Первый байт определяет количество символов в группе и называется счетчиком группы. На практике закодированная группа может содержать от 1 до 128 или 256 символов, что часто записывается в счетчик группы в виде: количество символов минус единица (значение от 0 до 127 или 255). Второй байт группы содержит значение символа в группе, которое находится в диапазоне от 0 до 255 и называется значением группы. Несжатая символьная группа из 15 символов А обычно занимает 15 байт: После RLE-кодирования та же строка займет всего два байта: 15А Код 15А, сгенерированный для представления символьной строки называется RLE-пакетом. Первый байт данного пакета (15) является счетчиком группы и содержит количество повторений. Второй байт (А) служит значением группы и хранит повторяемое значение. Новый пакет генерируется каждый раз, когда изменяется группа или когда количество символов в группе превышает максимальное значение счетчика. Предположим, что наша 15-символьная строка теперь содержит четыре различных символьных группы: AAAAAAbbbXXXXXt Применив групповое кодирование, мы сможем сжать ее в двухбайтовых пакета: 6A3b5X1t Таким образом, в результате группового кодирования 15-байтовая строка станет занимать только 8 байт. В данном случае групповое кодирование позволило получить степень сжатия, примерно равную 2:1. В определенных типах данных длинные группы встречаются крайне редко. Например, текст в формате ASCII редко включает длинные группы. В предыдущем примере последняя группа (содержащая символ t) имеет единичную длину, тем не менее, это все же группа, следовательно, счетчик группы и значение группы будут записаны в два байта. Для кодирования группы в RLE требуется как минимум два байта, поэтому группы из одиночных символов займут больше памяти. Схемы RLE просты и быстры, но эффективность сжатия зависит от типа данных изображения, подлежащего кодированию. Черно-белые изображения, содержащие значительно больше белого цвета, кодируются очень хорошо, поскольку включают большие объемы непрерывных данных постоянного цвета. Однако сложные изображения с большим количеством цветов, типа фотографий, кодируются весьма плохо. Причиной тому является сложность изображения, а именно большое количество различных цветов и относительно малое количество групп одинакового цвета. LZW-сжатие Схема сжатия Лемпела - Зива - Велча (LZW) является одной из наиболее распространенных в компьютерной графике. Этот метод сжатия данных без потерь применяется в различных форматах файлов изображений, в частности GIF и TIFF, и включен в стандарт сжатия для модемов V.42bis и PostScript Level 2. В 1977 году Абрахамом Лемпелом и Джекобом Зивом был создан первый компрессор из широко известного сегодня семейства компрессоров LZ. Алгоритмы сжатия LZ77 широко использовались для сжатия текста, а также стали основой таких архивирующих программ как compress, lha, zoo, pkzip и arj. Алгоритмы сжатия LZ78 более часто применялись для сжатия двоичных данных, например растровых. В 1984 году, являясь сотрудником Unisys, Терри Велч модифицировал компрессор LZ78 с учетом применения высокоскоростных дисковых контроллеров. Полученный в результате алгоритм LZW широко используется и сегодня. Алгоритм LZW позволяет работать с любым типом данных. Он обеспечивает достаточно быстрое сжатие и распаковку данных, не требуя при этом выполнения операций с плавающей запятой. Благодаря тому, что LZW пишет сжатые данные байтами, а не словами, результат может быть идентичен и в системах с порядком байтов старший в младшем, и в системах с порядком байтов младший в младшем. Алгоритм LZW относится к алгоритмам подстановок, или базирующимся на словарях. Этот алгоритм из данных входного потока строит словарь данных (также называемый переводной таблицей или таблицей строк). Образцы данных (подстроки) идентифицируются в потоке данных и сопоставляются с записями словаря. Если подстрока не представлена в словаре, то на базе содержащихся в ней данных создается и записывается в словарь кодовая фраза. Затем эта фраза записывается в выходной поток сжатых данных. Если эта подстрока встречается во входном потоке повторно, фраза, соответствующая ей, читается из словаря и записывается в выходной поток. Поскольку такая фраза имеет меньший физический размер, чем подстрока, которую она представляет, мы говорим, что произошло сжатие данных. Декодирование LZW-данных осуществляется в порядке, обратном кодированию. Ряд файловых форматов, в том числе и TIFF, применяют подобный метод кодирования для графических файлов. В TIFF пиксельные данные пакуются в байты до того, как поступают на вход LZW. Следовательно исходный байт LZW может быть пиксельным значением, частью пиксельного значения или несколькими пиксельными значениями (в зависимости от битовой глубины изображения и количества цветовых каналов). GIF требует, чтобы каждый входной символ LZW был пиксельным значением. Поскольку GIF позволяет сохранять глубину изображений от 1 до 8 битов, то в нем могут существовать от 2 до 256 входных символов LZW и словарь LZW инициализируется соответствующим образом. Не имеет значения, как были упакованы пиксели в оригинале - LZW будет работать с ними как с последовательностью символов. 9.2. Пример форматов графических файлов Microsoft Windows Bitmap BMP (Bitmap Picture) - это собственный растровый формат Windows, который используется для хранения практически всех типов растровых данных. Большинство приложений, работающих с графикой в среде Microsoft Windows поддерживают создание и отображение файлов в формате BMP. Он очень популярен в операционной системе MS-DOS, является родным форматом растровых файлов для системы OS/2. На рисунке 9.2.1 показана структура файла BMP. Первым элементом любого BMP-файла является заголовок BITMAPFILEHEADER. Как показано на рисунке 9.2.1 он занимает ровно 14 байт. typedef struct tagBITMAPFILEHEADER { UINT bfType; DWORD bfSize; UINT bfReserved1; UINT bfReserved2; DWORD bfOffBits; } BITMAPFILEHEADER; Х bfType - должен содержать два ASCII-символа: B и M, разумеется означающие bitmap. Соответствующие шестнадцатеричные значения равны 0x42 и 0x4D. При других значениях этого поля файл не является растровым изображением, принятым в Windows. Х bfSize - равен размеру файла в байтах, как указано в соответствующем элементе оглавления дискового каталога. Используется для проверки целостности файла и для распределения памяти под весь файл. Х bfReserved1 и bfReserved2 - не документировано и не используется, должно быть равно 0. Х bfOffBits - специфицирует байтовое смещение до начала растрового изображения. Используется для определения местонахождения массива aBitmapBits в файле. В целях безопасности для идентификации BMP-файла поля bfType и bfSize обычно используются вместе. Если bfType содержит символы B и M, а bfSize не равен длине файла, то это не BMP-файл. Этот прием предотвращает ошибки, возникающие при попытке отобразить другой файл как картинку, например текстовый файл, начинающийся с букв B и M. Следующей частью BMP-файла является структура BITMAPINFOHEADER, которая полностью описывает растровое изображение. С помощью нее можно подготовить растровое изображение к показу на экране, распаковке и прочим операциям. typedef struct tagBITMAPINFOHEADER { DWORD biSize; LONG biWidth; LONG biHeight; WORD biPlanes; WORD biBitCount; DWORD biCompression; DWORD biSizeImage; LONG biXPelsPerMeter; LONG biYPelsPerMeter; DWORD biClrUsed; DWORD biClrImportant; } BITMAPINFOHEADER; Х biSize - специфицирует собственный размер структуры в байтах. Должен быть равен 40 (0x28 в шестнадцатеричной системе). Если этот элемент структуры равен 12, то растровое изображение, вероятно, принадлежит системе OS/2. Х biWidth и biHeight - содержат ширину и высоту изображения в пикселях соответственно. Х biPlanes - должен быть равен единице, так как BMP-файлы, какого бы типа они не были, содержат только одну цветовую плоскость. Х biBitCount - содержит число битов на пиксель. Кроме того, отличает монохромное изображение от цветного. Должно быть равно 1, 4, 8 или 24. Обычно используется в сочетании с biClrUsed и biClrImportant. В следующей таблице описываются значения biBitCount и то, как они влияют на содержимое массива aColors. biBitCount Действие 1 Помечает изображение как монохромное. Показывает, что массив aColors содержит два элемента типа RGBQUAD. Каждый бит изображения, хранимый в массиве aBitmapBits, служит индексом массива aColors. Бит, равный 0, окрашен в соответствии с содержимым bmiColors[0], единичный бит - в соответствии с содержимым bmiColors[1]. Программа не должна предполагать, что монохромные пиксели непосредственно представляют белый и черный цвета, хотя часто так оно и есть. 4 Показывает, что массив aColors содержит до 14 цветовых значений типа RGBQUAD. В этом формате каждый байт содержит два четырехбитовых пикселя, а каждый пиксель есть индекс массива aColors, определяющего цвет. Например, байт изображения, равный 0x23, содержит два пикселя, один из которых равен 0x02, а второй - 0x03. Цвет первого пикселя равен aColors[0x02], а цвет другого aColors[0x03]. 8 Показывает, что массив aColors содержит до 256 цветовых значений типа RGBQUAD. Каждый байт в массиве aBitmapBits представляет собой отдельный пиксель, являющийся индексом массива. Цвет любого пикселя q равен aColors[q]. 24 Этот формат может описывать изображение с более чем 16-ю миллионами цветовых оттенков. Иногда называемые полноцветными (true color), эти изображения обычно используются для представления фотографий. В данном формате массив aColors отсутствует. Вместо этого 24-разрядные значения массива aBitmapBits представляют каждый пиксель как красно-зелено синюю триаду (тип RGBTRIPLE). BMP-файл этого типа может занимать огромное пространство на диске и в памяти. Х biCompression - показывает, хранится ли данное изображение в сжатом виде, а также метод его упаковки. Равен BI_RGB (изображение не сжато), BI_RLE8 (8-разрядное групповое кодирование) или BI_RLE4 (4 разрядное групповое кодирование). Х biSizeImage - содержит размер растрового изображения в байтах. Может быть нулевым, если biCompression равно BI_RGB. Х biXPelsPerMeter, biYPelsPerMeter - указывают предпочтительное разрешение в пикселях на метр по горизонтали и вертикали соответственно. Теоретически чем ближе разрешающая способность устройства отображения соответствует этим параметрам, тем лучше будет выглядеть изображение на экране. На практике эти параметры используются редко. Х biClrUsed - обычно содержит число цветов, используемое в растровом изображении и определяемое массивом aColors типа RGBQUAD. Если biClrUsed равен 0, как это обычно и бывает, в изображении используется максимальное количество цветов, возможное для изображения данного типа. Х biClrImportant - содержит число важных цветов изображения. Например, если это значение равно 3, первые три значения цвета в массиве aColors должны отображаться на экране с как можно более точным соответствием. Другие пиксели могут отображаться с измененным цветом или безболезненно пропускаться. Если biClrImportant равен 0, все цвета считаются важными. Этот параметр не имеет смысла для растровых изображений с 24-разрядным представлением цвета. Как было отмечено выше пиксели растрового изображения в общем случае являются индексами массива цветовых значений типа RGBQUAD. Цветовое значение представляет собой трехбайтовую композицию интенсивностей красного, зеленого и синего цветов. Четвертый байт дополняет структуру таким образом, что каждый элемент в RGBQUAD массиве начинается с четного адреса. Хотя это несколько расточительно, данная схема сильно повышает производительность, так как процессоры Intel могут выбирать выровненные на четную границу данные быстрее. В BMP-файле элемент aBitmapBits (если таковой вообще присутствует) содержит массив структур типа RGBQUAD. typedef struct tagRGBQUAD { BYTE rgbBlue; BYTE rgbGreen; BYTE rgbRed; BYTE rgbReserved; } RGBQUAD; Х rgbBlue - содержит относительную интенсивность синего цвета от 0 до 255. Х rgbGreen - содержит относительную интенсивность зеленого цвета от 0 до 255. Х rgbRed - содержит относительную интенсивность красного цвета от 0 до 255. Х rgbReserved - не используется. Предполагается равным 0, хотя, его физическое значение не важно. Как было отмечено выше массив aBitmapBits содержит пиксели, которые различаются по формату в зависимости от типа растрового изображения. Кроме того, байты могут быть сжаты. Байты хранятся строками слева направо, а каждая строка представляет собой линию развертки (scan line), которая может быть дополнена до 32-разрядной границы. Линии развертки упорядочены снизу вверх, то есть первый элемент массива содержит пиксели последней строки изображения. В растровых изображениях с 24-разрядным представлением цвета, где массив aColors отсутствует, байты aBitmapBits непосредственно представляют 24-разрядные триадные цвета пикселей. В других растровых изображениях пиксели из aBitmapBits представляют собой индексы массива aColors. Глоссарий Аффинные преобразования Ч масштабирование, перенос, отражение или поворот геометрического объекта на плоскости или в пространстве. Векторная графика Ч способ описания изображения, при котором все объекты сцены задаются в виде координат их вершин. Воксель (вогель) Ч пиксель в трехмерном пространстве. Выпуклый многоугольник Ч многоугольник, все диагонали которого лежат внутри его границы. Когнитивная графика Ч генерация изображений по их неформальному описанию (как правило по описанию на естественном языке). Пиксель Ч минимальная единица растрового изображения. Растровая графика Ч способ описания изображения, в виде последовательности цветных точек без выделения конкретных геометрических объектов. Текстура Ч одномерное или двумерное изображение наклеиваемое на плоский или трехмерный объект для придания большей реалистичности. Трассировка лучей Ч метод построения трехмерных изображений, при котором изображаемые пиксели и их цвет определяются с помощью слежения за лучами от источника света. Триангуляция Ч декомпозиция произвольного многоугольника на треугольники. Литература 1. Шикин Е.В., Боресков А.В. Компьютерная графика - М.: "Диалог-МИФИ", 1995. 2. Красота фракталов - М.: Мир, 1994. 3. Джеймс Д. Мюррей, Уильям ван Райпер Энциклопедия форматов графических файлов - К.: BHV, 1997. 4. Том Сван Форматы файлов Windows - М.: Binom, 1995. 5. Борзенко А., Федоров А. Мультимедиа для всех - М.: "Компьютер-пресс", 1995. 6. Корриган Д. Компьютерная графика. Секреты и решения - М.: "Энтроп", 1995. 7. Мультимедиа Под ред. Петренко А.И. - М., БИНОМ, 1994. Книги, научные публикации