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

МИНОБРНАУКИ РОССИИ федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Самарский государственный технический университет» А. И. ПУГАЧЕВ ГРАФИЧЕСКИЕ СИСТЕМЫ КОМПЬЮТЕРОВ Курс лекций Самара 2013 УДК 681.3 П 88 Пугачев А.И. П 88 Графические системы компьютеров: курс лекций / А.И. Пугачев. – Самара: Самар. гос. техн. ун-т, 2013. – 113 с.: ил. Изложены принципы описания объектов двумерной и трехмерной графики, даны теоретические основы их синтеза. Рассмотрены методики и алгоритмы визуализации различных классов геометрических объектов, способы выполнения над ними геометрических преобразований. Приведены сведения о языках программирования графических систем. В разделе трехмерной компьютерной графики изложены принципы моделирования распространения света, виды проецирования и другие аспекты построения реалистичных изображений трехмерных объектов. Для студентов, обучающихся по программе бакалавриата по направлениям 230100 – Информатика и вычислительная техника и 231000 – Программная инженерия. УДК 681.3 П 88  А.И. Пугачев, 2013  Самарский государственный технический университет, 2013 1 ВВЕДЕНИЕ Компьютерная графика – область информатики, которая рассматривает геометрические объекты: их информационные модели, методы визуализации и анимации. Геометрические объекты – это точки и линии на плоскости, плоские фигуры, а также пространственные линии, поверхности, трехмерные геометрические тела. Их информационные модели в первую очередь опираются на математические методы (аналитическая и проективная геометрия, векторная алгебра, теория множеств и др.). В соответствии с размерностью рассматриваемых объектов компьютерную графику делят на двумерную и трехмерную. Цель визуализации – построение изображения объектов на экране монитора или другого графического устройства по их информационным моделям. Для разных классов геометрических объектов разработаны свои методы и алгоритмы визуализации. При этом разработчики стремятся достичь максимально высокого быстродействия этих алгоритмов. Высокая скорость построения изображений нужна для поддержания интерактивной работы с графическими приложениями. Она необходима и в компьютерной анимации, т.е. в моделировании движения или других видимых изменений объектов во времени. Кроме синтеза и визуализации двумерных и трехмерных объектов предметом компьютерной графики также являются оцифровка готовых изображений, полученных в аналоговой форме (печатные, фото– и киноматериалы), а также различные виды обработки цифровых изображений [2]. Типичные операции обработки – трансформация изображений, цветовая коррекция, фильтрация, комбинирование нескольких изображений в одно и т.п. Разрабатываемые в компьютерной графике методы обработки изображений используются в самых разных областях: полиграфии, производстве видеопродукции, в системах распознавания образов. 2 Стоит также отметить, что по своему предмету к компьютерной графике близка компьютерная геометрия [4], основной целью которой является программное решение позиционных и метрических задач над геометрическими объектами. Компьютерная графика как наука служит теоретической основой разработки графического программного обеспечения, а также различных графических устройств: мониторов, видеоадаптеров персональных компьютеров, сканеров, плоттеров и др. Все шире методы компьютерной графики используются в цифровой фото– и видеоаппаратуре, мобильных устройствах коммуникации. 3 1. РАСТРОВЫЕ ИЗОБРАЖЕНИЯ И ТЕХНИЧЕСКИЕ СРЕДСТВА ГРАФИЧЕСКИХ СИСТЕМ 1.1. РАСТРОВЫЕ ИЗОБРАЖЕНИЯ Компьютерные изображения представляются в растровой форме, т.е. в форме прямоугольной матрицы со строками (строками растра) и столбцами. Это универсальный формат, пригодный для представления любого изображения, поскольку каждый элемент матрицы, называемый пикселем (от английских слов picture element), может иметь свой цвет. В то же время растровый формат имеет дискретный характер, что накладывает определенные ограничения на возможности представления изображений. Первым ограничением является конечное число строк и число элементов в строке, что ставит предел в воспризведении мелких деталей изображения. Второе ограничение определяется конечной разрядностью кодов цветов, что приводит к ограничению в количестве используемых цветов. Из сказаного следует, что наиболее важными характеристиками изображения являются:  разрешающая способность, т.е. количество элементов по горизонтали и вертикали;  глубина цвета, т.е разрядность используемых кодов цвета или число использумых цветов;  цветовая модель, т.е. способ кодирования цветов. Выбор этих характеристик определяется главным образом возможностями используемых устройств, формирующих изображения и устройств вывода. Растровые изображения формируются либо программным путем, либо с помощью устройств ввода, таких, как цифровые фотоаппараты или сканеры. В качестве графических устройств вывода используются мониторы, принтеры, плоттерры и др. Безусловно, чаще всего изображения воспроизводятся мониторами, поэтому разрешающая 4 способность и глубина цвета изображений обычно определяются аналогичными характеристиками применяемых мониторов. Типичные значения разрешающей способности современных мониторов 1280x1024, 1920х1080 и выше. Основной цветовой моделью графических устройств служит модель RGB, в которой каждый цвет образуется смешиванием трех основных цветов; красного (red), зеленого (green) и синего (blue). В наиболее популярном формате TrueColor этой модели цвета в изображениях кодируются тремя байтами – по одному байту на каждую составляющую R, G и B. Для хранения растровых изображений используются файлы различных форматов. Файлы наиболее распространенных форматов имеют расширения BMP, GIF, JPG, TIF, PNG [1]. Формат BMP (BMP – сокращение от bitmap) разработан фирмой Microsoft для операционных систем Windows. В этом формате изображение может храниться без сжатия или со сжатием. Цвета могут кодироваться с помощью 256-цветной палитры, которая в этом случае записывается в файл или в формате TrueColor. Чаще используют BMP-формат без сжатия. В этом формате размер файла значительно больше, чем со сжатием, но зато вывод изображения из него на монитор выполняется с максимальной скоростью, так как не требуется использовать сложные алгоритмы декодирования. Многие системы программирования и приложения Windows имеют функции для записи и вывода BMP-изображений. Формат GIF (Graphics Interchange Format) разработан в 1987 г. фирмой CompuServe как экономичный вариант хранения изображений со сжатием. Цвета кодируются с помощью 256-цветной палитры. В GIF-файле может храниться несколько кадров изображения. В настоящее время GIF используется практически на всех платформах и стал стандартным форматом изображений в оформлении Web-страниц. Формат JPG разработан Объединенной группой экспертов по фотографии (Joint Photographic Experts Group – JPEG). В этом формате графические данные записываются со сжатием и потерями. Степень 5 сжатия и соответственно степень потерь можно задавать при записи. Это самый популярный формат для хранения фотографических изображений. В большинстве цифровых фотоаппаратов фотографии сохраняются в формате JPG. Формат TIF (Tagged Image File Format – TIFF) также использует сжатие. В этом формате оно основано на применении тегов различных видов. В тегах размещается как общая информация, так и данные по отдельным элементам изображения. Количество видов тегов составляет несколько десятков. Сжатие производится без потерь, поэтому TIFF достаточно широко используется, в первую очередь, в издательских системах, требующих изображения наилучшего качества. Формат PNG (Portable Network Graphics) разработан сравнительно недавно и ориентирован специально на Web в качестве замены GIFформата. В отличие от GIF поддерживает кодирование цветов до 48 бит на пиксель. Использует сжатие без потерь. Кроме того, данный формат предоставляет ряд новых полезных возможностей таких, как альфаканалы (возможность плавно задавать прозрачность пикселей), гаммакоррекция (межплатформенное управление контрастностью изображения), возможность чересстрочной развертки при выводе изображения. Растровый файл обычно содержит информацию двух видов – графическую и неграфическую. В графических данных указываются цвета пикселей, а неграфические содержат различную информацию, необходимую для восстановления изображения, например его высоту и ширину. Неграфическая часть файла может также включать другую информацию, такую, как номер версии или сведения об авторских правах. Формат SVG (Scalable Vector Graphic – масштабируемая векторная графика) разработан Консорциумом Всемирной паутины (World Wide Web Consortium – W3C). Версия 1.1 вышла в 2001 году. Файлы с расширением SVG испльзуются для записи изображений двумерной векторной и смешанной векторно-растровой графики, заданных с помощию языка масштабируемой векторной графики SVG, являющегося подмножеством языка разметки XML. 6 Описание может включать и анимацию, в том числе и сложную, включающую расчеты координат, а также различные визуальные эффекты. Язык и формат SVG ориентированы прежде свего на использование в Web. 1.2. ГРАФИЧЕСКИЕ УСТРОЙСТВА ВВОДА-ВЫВОДА К наиболее распространенным графическим устройствам относятся:  мониторы (дисплеи);  принтеры;  плоттеры;  сканеры;  цифровые фотоаппараты;  дигитайзеры. Как уже отмечалось, мониторы – самые распространённые устройства вывода растровых изображений. Изображение в растровых мониторах формируется из строк пикселей, образующих матрицу с координатной адресацией по осям X и Y. Особенность экранной системы координат в том, что ось OY направлена вниз. По принципу действия мониторы можно разделить на следующие остновные виды:  с электронно-лучевой трубкой (ЭЛТ, CRT – cathode ray tube);  плазменные (PDP – Plasma Display Panels);  жидкокристаллические (ЖК, LCD – Liquid Crystal Display). Мониторы с ЭЛТ уже становятся прошлым. Плазменные панели, как и жидкокристаллические, широко используются в телевизорах, однако подавляющая часть современных мониторов для персональных компьютеров жидкокрисаллические. В LCD-дисплеях используются ЖК-панель, имеющая многослойную структуру, в которой главную роль играют две 7 стеклянные подложки и находящийся между ними слой жидких кристаллов с молекулами стержневидной формы. На подложках нанесены параллельные бороздки. Бороздки двух подложек ортогональны друг к другу, и на пересечении бороздок образуются ячейки, соответствующие пикселям. Бороздки создают первначальную ориентацию молекул кристалла, соприкасающихся с ними. При этом продольные оси молекул самого верхнего слоя жидких кристаллов будут расположены под прямым углом по отношению к осям молекул из нижнего слоя. Ориентация молекул между слоями плавно меняется от одного края к другому. В таком состоянии ячейки прозрачны для света ламп подсветки, расположенных за ЖК-панелью. Степенью прозрачности кристаллов можно управлять, меняя плоскость поляризации молекул за счет электрического напряжения, подаваемого на кристаллы. В качестве управляющих элементов используются тонкопленочные транзисторы (TFT – Thin Film Transistor), образующие матрицу из строк и столбцов соответственно ячейкам экрана. В цветных LCD-дисплеях для каждого пикселя используются три примыкающих друг к другу ячейки ЖК-панели – три субпикселя, подсветка на каждый из которых подается соответсвенно через красный, зеленый и синий светофильтры (рис. 1.1). Правильное восприятие цвета формируется за счет того, что при малых размерах субпикселей фактическое сложение цветовых составляющих в один цвет происходит в зрительном аппарате человека. R G B Количество столбцов и строк в матрице пикселей определяет максимальную Рис. 1.1 разрешающую способность монитора. Как уже говорилось, типичные значения разрешающей способности мониторов составляют 1280x1024, 1920х1080 и выше. Другая характерисика этого же свойства – разрешение монитора [1]. Оно 8 определяет число пикселей на дюйм по горизонтали (или вертикали). Чаще разрешение в обоих направлениях совпадает. Измеряется в единицах, обозначаемых как ppi (pixel per inch). Типичное разрешение современных мониторов при максимальной разрешающей способности развертки достигает 100 ppi. Другими наиболее важными параметрами мониторов являются яркость, контрастность, количество цветов, угол обзора, время отклика, интерфейс. Максимальная яркость изображения на экране монитора в значительной мере определяется подсветкой. Для большинства LCDмониторов максимальная яркость лежит в пределах 200 – 500 кд/м2. Контрастность определяется как соотношение между максимальной и минимальной яркостью. Хотя постоянная подсветка и создает проблемы, для современных мониторов достигает высоких значений в пределах от 1:1000 до 1:100000. Стандартное количество отображаемых цветов составляет 16,7 Млн., что соответствует диапазону значений цветов формата TrueColor. Максимальный угол обзора определяется как угол, при обзоре с которого контрастность изображения уменьшается в 10 раз. Различают горизонтальный и вертикальный углы обзора. Типовые значения – 1700 и 1600 соответственно. Время отклика – это время, за которое транзистор ячейки панели успевает изменить пространственную ориентацию молекул жидких кристаллов. Диапазон типовых значений 2 – 8 мс, что достаточно для воспроизведения любых динамических сцен. Хотя в LCD-мониторах используется цифровое управление выводом изображения, многие из них имеют аналоговый интерфейс VGA (Video Graphics Array), разработанный еще для мониторов на базе ЭЛТ. В более современных мониторах используются цифровые интерфейсы DVI (Digital Visual Interface) и HDMI (High-Definition Multimedia Interface), обеспечивающие более высокое качество воспроизведения изображения. 9 Наиболее известными производителями жидкокристаллических мониторов являются фирмы Acer, Samsung, LG, Philips. Помимо мониторов используется большая номенклатура различных устройств ввода и вывода графической информации. Практически все современные принтеры (игольчатые, струйные, лазерные) по принципу формирования изображения являются матричными, поэтому хорошо подходят для печати на бумаге не только текстовых документов, но и растровых изображений. Разрешение принтеров с матричным способом печати указывается в единицах dpi (dot per inch) – точек на дюйм. Обозначает возможность вывода указанного количества мельчайших печатных точек на дюйм. Однако при печати изображений с полутонами каждый пиксель приходится воспроизводить не одной печатной точкой, а квадратной матрицей печатных точек, например матрицей размером 16х16. Типичное разрешение лазерных принтеров составляет от 600х600 до 1200х1200 dpi, струйных – до 4800х1200 dpi и выше. Плоттер (графопостроитель) – устройство вывода изображений на бумагу, пластик, фоточувствительный материал или иной носитель путем черчения, фоторегистрации, гравирования или иным способом. Существуют планшетные, рулонные и барабанные плоттеры. Планшетные плоттеры (flatbed plotter) относятся к векторным устройствам. В них лист фиксируется на планшете электростатическим способом. Изображение строится с помощью пишущего узла, который может перемещаться по планшету одновременно по двум координатам. В пишущем узле используются специальные фломастеры или ручки с возможностью их автоматической замены. Формат бумажных листов от А4 до А0. В настоящее время графопостроители этого типа уже не выпускаются. Рулонные графопостроители (roll-feed plotter) по принципу действия относятся к растровому типу. В них чертежная головка перемещается в одном направлении, перпендикулярном направлению движения бумаги. Таким образом, изображение строится построчно. 10 Ширина бумаги соответствует формату А1 или А0, а длина рулона может быть несколько десятков метров. В барабанных плоттерах (drum plotter) носитель изображения закрепляется на вращающемся барабане. По способу печати растровые плоттеры подразделяются следующим образом:  электростатические;  струйные, основанные на принципе струйной печати;  лазерные;  светодиодные, отличающиеся от лазерных способом перенесения изображения с барабана на бумагу;  термические графопостроители (thermal plotter);  фотоплоттеры с фиксацией изображения на светочувствительном материале путем экспозиции. Разрешение растровых графопостроителей находится в переделах 300 – 2500 dpi. Цифровые фотоаппараты – безусловно, самый распространенный вид графических устройств ввода. Для регистрации изображения используется матрица светочувствительных элементов, преобразующих оптическое изображение в электрическое. Каждый элемент матрицы регистрирует в виде заряда информацию о яркости соответствующего пикселя изображения. Оптическое изображение формируется объективом фотокамеры и регистрируется в матрице в процессе экспозиции в аналоговой форме. После этого элементы матрицы последовательно опрашиваются, уровни напряжения в ее элементах преобразуются аналого-цифровыми преобразователями (АЦП) в цифровую форму и записываются сначала в оперативную память, а из нее для хранения – во флэш-память в формате JPG или TIF. Применяется два типа светочувствительных матриц:  CMOS – Complementary Metal-Oxide-Semiconductor (комплементарный металлооксидный полупроводник (КМОП)); 11  CCD – Charged Couple Devices (приборы с зарядовой связью (ПЗС)). CMOS-матрицы используются в более дорогих, профессиональных фотоаппаратах. Основные характеристики фотокамер – емкость матрицы в мегапикселях (10 – 15 МПикс); максимальная разрешающая способность изображения (3648х2736, 4320х3240 и выше). Сканер – это устройство ввода графической информации главным образом с бумажных носителей. Обычно это бумажные документы и фотографии [1, 2]. Наиболее распространены планшетные сканеры. В них сканируемый документ или фотография располагаются на планшете и равномерно освещаются источником белого света. Используются принципы цифровой фотографии. Фоточувствительным элементом сканера служит CCD-линейка или CCD-матрица. Оптической системой, аналогичной оптике фотоаппарата, формируется проекция изображения на CCD. CCD-линейка способна зафиксировать лишь одну строку проекции. К кому же, для того чтобы получить цветное изображение, используют 3 цветных светофильтра – красный, синий и зеленый, поэтому в сканерах с CCD-линейкой ввод изображения ведется построчно, а перемещение CCD-линейки к очередной строке производится шаговым двигателем. В планшетных сканерах с CCD-матрицей не требуется ее перемещения. При экспозиции изображение фиксируется во всех ее чувствительных элементах одновременно, так же, как в цифровых фотоаппаратах. Разрешение сканеров чаще всего, как и для принтеров, указывают в единицах dpi, хотя правильнее бы было использовать единицу ppi, так как оптическое разрешение сканера характеризует число пикселей формируемого изображения, приходящихся на 1 дюйм. Оптическое разрешение сканеров лежит в пределах от 600 dpi, что с учетом сказанного нужно понимать как 600 пикселей на дюйм, до 4800 dpi. 12 Дигитайзер (графический планшет) – это устройство, предназначенное для ручного рисования и оцифровки изображений. Дигитайзер состоит из планшета и курсора, который пользователь может двигать по поверхности планшета для формирования рисунка. Принцип действия основан на фиксации местоположения курсора с помощью встроенной в планшет сетки. При нажатии на кнопку курсора его местоположение на поверхности планшета фиксируется, а его координаты передаются в компьютер. Сетка состоит из проволочных или печатных проводников с шагом 3 – 6 мм, однако механизм регистрации положения позволяет получить шаг считывания информации намного меньше шага сетки (до 100 линий на мм). Важная характеристика дигитайзера – регистрируемое число степеней нажима электронного пера. Степень нажатия оцифровывается и обрабатывается программным путем для преобразования, например, в толщину проводимой линии. В современных дигитайзерах число различаемых степеней нажатия достигает 256. 1.3. ВИДЕОАДАПТЕРЫ В современных персональных компьютерах при формировании изображения на экране монитора наиболее сложную и трудоемкую обработку выполняет видеоадаптер (графический адаптер, графическая плата, видеоплата, видеокарта и т.п.). Видеоадаптер обеспечивает прием графической информации из оперативной памяти компьютера, преобразование ее в растровую форму (растеризация), буферизацию в видеопамяти, а также периодическое считывание содержимого видеопамяти для формирования видеосигнала. Для этого современный видеоадаптер включает в себя следующие устройства:  видеопамять;  графический процессор (Graphics processing unit, GPU);  видеоконтроллер;  цифроаналоговый преобразователь (ЦАП); 13  ПЗУ BIOS (Basic Input/Output System) с основными функциями, поддерживающими интерфейс между оборудованием видеоадаптера и программным обеспечением. Кроме этого, в составе видеоадаптера обычно имеется контроллер внешней шины данных (например, PCI Express x 16), а также контроллер внутренней шины данных. Для повышения производительности графического процессора разрядность внутренней шины и шины видеопамяти расширяют до 64 – 256 разрядов и выше. Видеопамять необходима для буферизации изображения, формируемого видеоконтроллером. Она представляет собой СОЗУ на базе быстродействующих микросхем статической памяти (SRAM) типов DDR или GDDR емкостью от 0,5 до 2 Гбайт и выше. Каждому пикселю экрана в видеопамяти соответствует ячейка, где хранится код его цвета. В формате TrueColor цвет пикселя кодируется тремя байтами – по одному байту на каждую цветовую составляющую R, G и B. Содержимое видеопамяти периодически с частотой 75 – 100 Гц считывается видеоконтроллером для регенерации изображения на экране монитора. Графический процессор выполняет основную часть графических вычислений, тем самым освобождая центральный процессор для остальных задач. Для достижения высокой производительности, необходимой для поддержки интерактивной графики, в графических процессорах широко используется распараллеливание за счет конвейерной организации обработки данных с помощью специализированных устройств. Видеоконтроллер отвечает за формирование изображения в видеопамяти, а также за периодическое последовательное считывание данных из нее и передачу их на вход ЦАП для преобразования в аналоговую форму для формирования сигналов развертки монитора. Современные графические адаптеры обычно имеют не менее двух видеоконтроллеров, работающих независимо друг от друга и управляющих одновременно одним или несколькими мониторами каждый. 14 Большинство ЦАП видеоадаптеров имеют разрядность 8 бит на каждый основной цвет. Это позволяет воспроизводить до 16,7 млн. различных цветов. Разрядность ЦАП более дорогих видеоадаптеров по каждому каналу составляет 10 бит, что дает возможность отображать более 1 млрд. цветов. Быстродействие ЦАП достигает 300 МГц и выше, что позволяет при оптимальных частотах регенерации изображения (75 – 85 Гц и более) поддерживать высокое разрешение на экране монитора. Видеоадаптеры с быстродействием ЦАП от 300 МГц и выше позволяют поддержать разрешающую способность монитора до 1920 х 1200 при частотах регенерации изображения 75 Гц и выше. Характеристики графической подсистемы компьютера зависят не только от аппаратуры видеоадаптера, но и во многом определяются используемой для него шиной обмена. В настоящее время в персональных компьютерах для обмена с видеоадаптерами обычно используется высокоскоростная шина PCI Express (PCI-E). Наиболее известными производителями видеоадаптеров являются фирмы ATI и nVidia (США). 15 2. ДВУМЕРНАЯ КОМПЬЮТЕРНАЯ ГРАФИКА 2.1. ДВУМЕРНЫЕ ПРИМИТИВЫ В компьютерной графике простейшие геометрические объекты, которые служат элементами для синтеза более сложных объектов, принято называть примитивами. К двумерным примитивам относят точки, линии, отрезки прямых (векторы) и кривых линий, многоугольники, ограниченные области плоскости. Границей области могут служить многоугольник или кривая линия, например окружность. Конкретный состав используемых примитивов в зависимости от прикладного назначения программы может быть различным. Примитивы характеризуются описанием их геометрии и видом закрашивания. Закрашивание может быть однотонным, т.е. задаваться кодом цвета. Кроме этого используется текстурное закрашивание ограниченных областей с помощью образцов текстур. Рассмотрим описание геометрии наиболее общих видов примитивов. Точки на плоскости обычно задаются своими координатами (x, y). Для аналитического задания линий используют алгебраические уравнения или системы функций. Алгебраические линии описываются алгебраическими уравнениями вида F(x, y) = 0. Из них на практике чаще используют прямые линии и линии второго порядка (эллипсы, параболы, гиперболы). Прямые линии в алгебраической форме задаются уравнением первого порядка: a1 x + a2 y + a3 = 0. (2.1) Общее уравнение линии второго порядка имеет следующий вид: a11 x2 + a22 y2 + 2 a12 x y + 2 a13 x + 2 a23 y + a33 = 0. (2.2) Произвольные гладкие кривые принято задавать параметрическими функциями вида 16 P(t )  x(t ) y(t ). (2.3) Матрица-строка P(t) содержит функции x(t), y(t) от общего параметра t, которые определяют значения координат x, y всех точек параметрической кривой. Если дополнительно ограничить область изменения параметра t1  t  t2, то на линии будет выделен отрезок. Например, отрезок параболы между точками (x0, y0) и (x0 + kx, y0 + ky) задается функциями x(t) = x0 + kx t, y(t) = y0 + ky t2 и ограничением 0  t  1. В качестве базисных функций для x(t) и y(t) используют полиномиальные функции, такие, как полиномы Лежандра, Ньютона, Эрмита, Бернштейна. Выбор базиса зависит от постановки задачи и требований к качеству кривой. Полиномиальные параметрические кривые называются сплайнами. Кроме выбора базиса для описания конкретной кривой нужно задать начальные условия. Начальные условия определяют расположение, размеры и общий характер линии, поэтому при конструировании сплайнов в качестве начальных условий стремятся использовать такие, которые имеют понятный геометрический смысл: узловые точки кривой, касательные векторы к кривой. В то же время начальные условия должны однозначно определять все коэффициенты функций x(t) и y(t). Многоугольник общего вида описывается списком его вершин, т.е. списком точек P1, P2,…, Pn на плоскости, которые последовательно соединяются отрезками прямых, причем имеется в виду, что последняя точка соединяется с первой: Pg = (P1, P2,…, Pn). (2.4) В этом смысле многоугольник является частным случаем ломаной линии и не представляет особого интереса для синтеза более сложных объектов, поэтому в компьютерной графике, говоря о многоугольнике, в качестве примитива обычно рассматривают ограниченную многоугольную область, т.е. область плоскости с границей в виде многоугольника (рис. 2.1). Частными случаями многоугольников являются правильные многоугольники, т.е. многоугольники, у которых равны все стороны и 17 углы между смежными сторонами. Правильный многоугольник может быть вписан в окружность (рис. 2.2), поэтому правильные многоугольники удобно задавать через параметры описанной окружности (xc, yc), R и число сторон n. P1 P2 P3 R P8 (xc, yc) P4 P7 P6 P5 Рис. 2.1 Рис. 2.2 Следует только отметить, что в этом способе задания однозначно не определяется расположение вершин многоугольника на окружности. Однако если в программной процедуре расчета вершин многоугольника определенный порядок их расположения на окружности выбирается по умолчанию, то в большинстве случаев это бывает приемлемым. Области на плоскости могут ограничиваться не только многоугольниками, но и кривыми линиями, например окружностями, но для сокращения объема вычислений при визуализации их обычно аппроксимируют многоугольниками, т.е. все ограниченные области приводятся к единому полигональному формату. 2.2. ВИЗУАЛИЗАЦИЯ НА ДИСКРЕТНОЙ ОБЛАСТИ ВЫВОДА Визуализация – это процесс формирования изображения и его вывод с помощью графического устройства вывода. Чаще всего изображение выводится на монитор, поэтому в дальнейшем будем подразумевать именно это устройство. Рассмотрим специфику визуализации в отношении точности воспроизведения геометрии изображаемых объектов. Формально область вывода монитора или другого графического устройства растрового типа представляет собой прямоугольную часть 18 дискретной плоскости, для адресации пикселей в которой используется целочисленная система координат. На рис. 2.3 показана ограниченная область вывода с системой координат, используемой в мониторах. Диапазоны изменения координат по осям OX и OY составляют соответственно [0..Xemax] и [0..Yemax]. Например, для монитора с разрешающей способностью 1280 х 1024 этими диапазонами будут [0..1279] и [0..1023]. x Xemax X y P(x, y) = (r, g, b) Yemax Y Рис. 2.3 Для определенности будем считать, что всякая пара координат (x, y) в области вывода задает центр соответствующего пикселя. Дискретный характер области вывода предопределяет, что изображение точно заданных геометрических объектов всегда будет построено с погрешностью. На рис. 2.4 в качестве примера приведено представление на дискретной области отрезка прямой. Первая причина погрешности заключается в том, что на дискретной плоскости точно можно представить лишь центры точек с целыми координатами. Для изображения точек с вещественными координатами их приходится округлять до целых значений. Погрешностью δ в изображении всякой точно заданной точки (x, y) следует считать 19 расстояние между этой точкой и центром пикселя, изображающего данную точку. На рис. 2.4 центры пикселей отмечены точками, однако, говоря о максимальной погрешности визуализации из-за округления, чаще вместо этого способа ее оценки для простоты рассматривают максимальную погрешность от округления координат пикселей. В этом случае максимальная погрешность визуализации будет 0,5 пикселя, что не сильно отличается от точной оценки. δ Рис. 2.4 Вторая причина погрешности состоит в том, что пиксели в отличие от математических точек имеют реальные размеры, что приводит к искажению заданных размеров объектов. В частности, как видно на рис. 2.4, длина всякого отрезка прямой при визуализации возрастает примерно на 1 пиксель. Кроме этого у отрезка появляется толщина примерно в 1 пиксель. При визуализации приходится учитывать и другие особенности. В частности, алгоритмы визуализации линейных объектов (отрезков линий) должны изображать их без разрывов. На дискретной плоскости непрерывность между точками в изображении линий и отрезков основана на понятии связности соседних пикселей. Рассматриваются 2 вида связности – 4– и 8-связность (рис. 2.5) [4]. Для 4-связности соседними с данным пикселем (x, y) считаются 4 ближайших, у которых одна из координат (xn, yn) отличается на 1 от координат этого пикселя (см. рис. 2.5, а), т.е. такие, для которых |x – xn| + |y – yn| = 1. Для 8-связности соседними считаются пиксели, у ко20 торых одна или обе координаты отличаются от (x, y) на 1 (см. рис. 2.5, б), т.е. такие, для которых |x – xn| + |y – yn|  [1, 2]. а б Рис. 2.5 На рис. 2.5 показано растровое изображение одинаковых по размерам и ориентации отрезков с использованием 4-связного и 8связного соседства. В алгоритмах визуализации обычно используется 8-связность, поскольку в этом случае изображение непрерывных линий выглядит более гладким. 2.3. ВИЗУАЛИЗАЦИЯ ОТРЕЗКОВ ПРЯМЫХ Пусть на дискретной области вывода требуется построить отрезок между двумя заданными точками, начальной P1 с целыми координатами (x1, y1) и конечной P2 с координатами (x2, y2), т.е. изобразить его с помощью непрерывной последовательности пикселей с наименьшей погрешностью (рис. 2.6). Очевидно, что все промежуточные точки отрезка также должны иметь целые координаты. Далее для определенности будем считать, что целые координаты области вывода соответствуют центрам пикселей. Уравнение прямой, проходящей через P1 и P2, имеет вид 21 x  x1 y  y1 .  x2  x1 y2  y1 (2.5) Y F(x, y) = 0 P2 F(x, y) < 0 выбранные пиксели ∆y P1 отвергнутые пиксели F(x, y) > 0 X ∆x Рис. 2.6 Обозначив приращения координат x2 – x1 = ∆x; представим уравнение (2.5) следующим образом: ∆y(x – x1) – ∆x(y – y1) = 0. y2 – x1 = ∆y, (2.6) Функцию F(x, y) = ∆y(x – x1) – ∆x(y – y1) в левой части уравнения (2.6) будем называть оценочной, поскольку ее значение характеризует степень отклонения всякой точки (x, y) от прямой P1P2. Действительно, в соответствии с уравнением (2.6) для всех точек прямой F(x, y) = 0. При удалении всякой точки (x, y) плоскости OXY от P1P2 абсолютная величина F(x, y) возрастает прямо пропорционально расстоянию между (x, y) и прямой, поэтому |F(x, y)| может использоваться в качестве меры отклонения оцениваемых точек от строящегося отрезка. Это свойство оценочной функции позволяет вместо непосредственного расчета координат точек отрезка по уравнению прямой линии последовательно выбирать очередные точки для изображения отрезка из соседних на основе сравнения значений F(x, y). 22 Начнем построение отрезка, взяв за начальное значение текущей точки P точку P1. Будем двигаться от нее по дискретной плоскости к конечной точке P2, стремясь отклоняться от прямой P1P2 в наименьшей степени. Направление движения и значения элементарных шагов sx и sy по осям зависят от знаков приращений ∆x и ∆y. Если ∆x > 0, то sx = 1. Если же ∆x < 0, то sx = -1. Следовательно, sx = sign(∆x). Аналогично элементарным шагом по координате y будет sy = sign(∆y). Любая точка на дискретной плоскости имеет 8 соседних. Если учитывать направление движения от P1 к P2, то для выбора очередной точки вместо 8 достаточно рассматривать только 3 соседние точки. Чтобы еще сократить выбор, рассмотрим частный случай, когда |∆x|  |∆y|. Ему соответствуют отрезки с углом наклона к оси OX, меньшим или равным 450. Тогда новым значением текущей точки P с координатами (x, y) может быть либо точка (x + sx, y), либо (x + sx, y + sy). Для выбора лучшей из них используем оценочную функцию. Так как за начальное значение P принята точка P1, лежащая на прямой P1P2, то начальное значение F(x , y) = 0. Для соседней точки (x + sx, y) имеем F(x + sx, y) = ∆y(x + sx – x1) – ∆x(y – y1) = F(x, y) + sx ∆y. (2.7) Для соседней точки (x + sx, y + sy) F(x + sx, y + sy) = ∆y(x + sx – x1) – ∆x(y + sy – y1) = = F(x + sx, y) – sy ∆x. (2.8) Рекурсивный вид формул (2.7) и (2.8) позволяет заметно сократить вычисления по сравнению с непосредственным вычислением F(x , y). Поскольку ∆x, ∆y, sx, sy – постоянные величины, то расчеты по формулам (2.7), (2.8) можно еще сократить, если заранее вычислить ∆Fx = sx ∆y и ∆Fy = sy ∆x. Тогда F(x + sx, y) = F(x, y) + ∆Fx; F(x + sx, y + sy) = F(x + sx, y) – ∆Fy. 23 (2.9) (2.10) Если F(x + sx, y) < F(x + sx, y + sy) , то точка (x + sx, y) лежит ближе к прямой P1P2, чем точка (x + sx, y + sy), и ее следует принять за новое положение текущей точки P. Иначе новым значением P должна стать точка (x + sx, y + sy). Далее процесс построения надо повторять до тех пор, пока текущая точка P не достигнет конечной P2. В итоге алгоритм визуализации отрезка для рассматриваемого частного случая можно представить следующим образом. 1. Установить цвет рисования Color. 2. Вычислить: ∆x = x2 – x1; ∆y = y2 – y1; sx = sign(∆x); sy = sign(∆y); Если sx > 0, тогда ∆Fx = ∆y, иначе ∆Fx = – ∆y. Если sy > 0, тогда ∆Fy = ∆x, иначе ∆Fy = – ∆x. x = x1; y = y1; // начальные координаты текущей точки F = 0. // начальное значение оценочной функции 3. Вывести пиксель с координатами (x, y) цветом Color. 4. Если x = x2 , то – конец алгоритма. 5. Вычислить: Fx = F + ∆Fx; F = Fx – ∆Fy; x = x + sx. 6. Если Fx  < F , то вычислить F = Fx, иначе – вычислить y = y + sy. 7. Перейти к п. 3. В алгоритме переменная F обозначает текущее значение оценочной функции, а Fx – новое ее значение при шаге по x. Для сокращения вычислений новое значение оценочной функции при одновременном шаге по x и y также обозначается через F. Вторую часть алгоритма для построения отрезков с наклоном к оси OX более 450 легко разработать по аналогии. Близким к рассмотренному, но еще более экономичным по объему вычислений на один пиксель, является алгоритм растрового построения отрезка, разработанный Брезенхемом [5, 7] в 1965 г. 24 2.4. КУБИЧЕСКИЕ СПЛАЙНЫ Кубическими сплайнами называются параметрические кривые, для которых в качестве базисных функций используются полиномы 3-й степени вида a t 3 + b t 2 + c t + d. (2.11) На плоскости кубический сплайн задается следующим образом:  P(t )  axt 3  bxt 2  cxt  d x  a y t 3  by t 2  c y t  d y . (2.12) Параметр t изменяется в пределах 0  t  1. При этом начальной точкой сплайна будет P(0), а конечной – точка P(1). Для однозначного задания кубического сплайна в форме Эрмита [1] используют следующие начальные условия (рис. 2.7):  кривая должна проходить через заданные начальную T1 и конечную T2 точки;  в начальной и конечной точках должны быть заданы касательные векторы T1 и T2 к кривой. P (0) T 1 P(t) P(0) P(1) T1 P (1) T2 T2 Рис. 2.7 Далее для удобства матрицу-строку [x y] координат (x, y) какойлибо точки T или вектора T будем обозначать так же, как и саму точку или вектор. 25 Напомним также, что координатами вектора являются приращения координат по соответствующим осям между его конечной и начальной точками. Представим (2.12) в следующей форме:  P(t )  t 3 t 2 ax b x t 1   cx  d x  ay  by    t 3 t 2 t 1  L, cy   dy    (2.13) где L – матрица неизвестных коэффициентов полиномов. Первое начальное условие дает следующие соотношения: P(0) = T1; P(1) = T2. (2.14) Используя (2.13), запишем их в матричной форме: P(0) = [0 0 0 1]  L = T1; (2.15) P(1) = [1 1 1 1]  L = T2. (2.16) Второе начальное условие дает дополнительные соотношения P(0) = T1; P(1) = T2. (2.17) Касательный вектор к кривой P(t) находится как производная P(t). В данном случае  dx P' (t )    dt   dy   3a xt 2  2bxt  cx  dt  3a y t 2  2by t  c y . (2.18) Запишем P(t) в форме, аналогичной (2.13):  P' (t )  3t 2  1 0  L. 2t (2.19) Используя (2.19), представим условия (2.17) также в матричной форме: 26 P(0) = [0 0 1 0]  L= T1; (2.20) P(1) = [3 2 1 0]  L= T2 . (2.21) Теперь все начальные условия (2.15), (2.16), (2.20), (2.21) объединим в единое матричное уравнение с неизвестной матрицей L: 0 1  0  3 1 2 1 1 1 1  T1  T  1   L   2 . T 1  0    0 T 2  (2.22) Для нахождения L умножим слева обе части равенства (2.22) на матрицу Mh, обратную матрице с числовыми коэффициентами. В итоге получим  2  3 L 0  1 2 3 1 2 1 1   T1     1  T2    M h  Gh . 0  T 1     0  T 2  (2.23) Матрица Mh называется эрмитовой, а вектор Gh с начальными условиями – геометрическим вектором Эрмита. Несмотря на это общепринятое название Gh, следует помнить, что каждый элемент Gh представляет собой строку из двух элементов. Формула (2.23) позволяет рассчитать коэффициенты матрицы L по заданным начальным условиям, после чего можно построить и сам сплайн P(t), используя формулу (2.12). 2.5. КРИВЫЕ БЕЗЬЕ В 1962 г. французский ученый П. Безье предложил теорию сплайнов, основанную на использовании интерполяционных полиномов Бернштейна. Такой сплайн, получивший название кривой Безье [7], за27 дается списком опорных точек Lp = (T0, T1, ... Tn). Кривая должна проходить только через начальную и конечную точки списка. Остальные точки влияют лишь на форму кривой. При этом векторы T0T1 и Tn-1Tn являются касательными векторами в начальной и конечной точках кривой (рис. 2.8). Число точек в списке Lp может быть любым, большим 1. При этом степень кривой на 1 меньше числа точек, т.е. равна n – 1. Математически кривая Безье описывается в виде функции полиномиальной интерполяции между начальной T0 и конечной Tn точками списка Lp с помощью полиномов Бернштейна. Полином Бернштейна n – ной степени имеет вид J n, i (t )  n! t i (1  t ) n  i , 0  i  n. i!(n  i)! (2.24) T1 T2 P(t) T4 P(0) P(1) T0 T3 Рис. 2.8 Сама кривая Безье описывается через базисные функции (2.24) и начальные условия следующим образом: n P(t )   Ti J n,i (t ), 0  t  1. i 0 (2.25) Здесь Ti = [xi yi] – координаты i-той точки списка Lp. Отметим, что степень n полиномов в P(t) на единицу меньше числа вершин. 28 В шрифтах TrueType при определении контуров символов используются квадратичные кривые Безье (n = 2). Для задания такой кривой нужны три точки Lp = (T0, T1, T2). В качестве примера рассмотрим кривую подробнее. Сначала запишем для нее все интерполяционные полиномы: J 2,0 (t )  t 0 (1  t ) 2  (1  t ) 2 ; J 2,1 (t )  2! t 1 (1  t )1  2t (1  t ); 1!(2  1)! J 2, 2 (t )  t 2 (1  t )0  t 2 . (2.26) (2.27) (2.28) В итоге на основании (2.25) кривая Безье второй степени будет задаваться следующей функцией: n P(t )   Ti J n, i (t )  T0 J 2,0 (t )  T1 J 2,1 (t )  T2 J 2, 2 (t )  i 0  T0 (1  t )2  T1 2t (1  t )  T2t 2 . (2.29) Более детально (2.29) означает следующее: x(t )  x0 (1  t ) 2  x1 2t (1  t )  x2 t 2 ; y (t )  y0 (1  t )  y1 2t (1  t )  y2 t . 2 2 (2.30) Кривые Безье применяются во всех популярных графических программах, например в CorelDraw и PhotoShop. Во многих программных продуктах ограничиваются использованием кубических кривых, строящихся по четырем точкам. В частности, кубические кривые Безье используются в API (Application Programming Interface – интерфейс прикладного программирования) Windows. Ограничение кубическими кривыми вызвано разными причинами. Одна из них – глобальное влияние на форму кривой любой из опорных точек, что практически затрудняет ручное сопряжение кривой с другими элементами изображения, поэтому, ограничиваясь кубическими кривы29 ми, более сложные строят путем гладкого сопряжения нескольких кубических кривых. Ниже в качестве примера приводится алгоритм визуализации кривой Безье n -ной степени с постоянным шагом табуляции по t. 1. Установить цвет рисования Color. 2. Вычислить: nFact = Factorial(n); dt = Const; t = dt; xPred = Lp[0].x; yPred = Lp[0].y. 3. Пока t < 1 + dt/2 выполнить пп. 3.1 – 3.4. 3.1. Вычислить: xt = 0; yt = 0; i = 0. 3.2. Пока i <= n выполнить п. 3.2.1. 3.2.1. Вычислить J = t i * (1 – t) n-i * nFact/(Factorial(i)* Factorial(n-i)); xt = xt + Lp[i].x * J; yt = yt + Lp[i].y * J; i = i + 1. 3.3. Вывести отрезок (xPred, yPred, xt, yt) цветом Color. 3.4. Вычислить: t = t + dt; xPred = xt; yPred = yt. В приведенном алгоритме предполагается, что список Lp исходных точек T0, T1, ... Tn организован как массив, а для вычисления факториала используется функция Factorial. 2.6. ЗАКРАШИВАНИЕ ОГРАНИЧЕННЫХ ОБЛАСТЕЙ ПЛОСКОСТИ Ограниченные области задаются описанием своих границ. Если область ограничивается криволинейными границами, то их, как правило, предварительно аппроксимируют ломаными линиями. Такой прием позволяет использовать универсальное решение для визуализации областей с любым граничным контуром. Погрешность 30 от аппроксимации всегда можно задать в пределах погрешности от дискретного характера области вывода. Граничный многоугольник области задается упорядоченным списком вершин Pg = (P1 , P2 , … , Pn), однако задания границы еще недостаточно. Для полноты формального описания необходимо также задать правило, определяющее то, с какой стороны от граничной линии располагаются ближайшие внутренние точки области. Из топологии известно что, если произвольная прямая пересекается с границей замкнутой области, то число точек пересечения всегда четно (рис. 2.9). Исходя из этого свойства, одно из наиболее простых и понятных правил определения внутренних и внешних точек области можно сформулировать следующим образом: всякая точка плоскости является внутренней точкой ограниченной области, если луч, проведенный из этой точки в любом направлении, пересекает границы области нечетное число раз. Y Ymax P1 xl Y P6 P3 xr P P2 P4 Ymin P5 X Рис. 2.9 Сказанное справедливо и для горизонтальных строк растра, поэтому закрашивание многоугольника можно выполнять построчно в пределах от Ymin до Ymax, где Ymin – координата Y самой нижней вершины многоугольника; Ymax – координата Y самой верхней вер31 шины. Если список точек пересечения сторон многоугольника с текущей строкой Y упорядочить по возрастанию или убыванию координаты x, то каждая очередная пара точек в списке будет определять границы (xl, Y) и (xr, Y) закрашиваемого сегмента строки (см. рис. 2.9). Расчет границ Ymin и Ymax закрашивания по Y позволяет сократить число рассматриваемых строк. Однако, по разным причинам, например за счет масштабирования, многоугольник может частично или полностью выйти по Y за пределы интервала 0..Yemax, где Yemax – максимальное значение координаты y области вывода. Чтобы исключить безрезультатные вычисления в этих случаях, найденные значения следует скорректировать так: Ymin  max(Ymin, 0); (2.31) Ymax  max( Ymax, Yemax). (2.32) При реализации метода следует учесть случаи, требующие особой обработки. Во-первых, это вершины многоугольника. В каждой вершине сопрягаются две смежные стороны. Если при закрашивании учитывать все точки пересечения сторон со строками, не исключая начальную и конечную, то каждой вершине будут соответствовать две совпадающие границы сегментов, что во многих случаях может привести к неправильному закрашиванию. Вторым особым случаем закрашивания являются горизонтальные стороны (∆y = 0) граничного многоугольника, поскольку они не пересекают строки растра, а лежат на них. На рис. 2.10 приведен пример граничного контура многоугольника, на котором цифрами отмечены особые случаи: 1 – это вершины, которые должны обрабатываться как одна граница сегмента; 2 – вершины, которые следует рассматривать как две совпадающие границы; 3 – граничные вершины горизонтальных сторон. Если для всякой стороны PiPi+1 приращение по y рассчитывать как y  yi1  yi , 32 (2.33) то случаи 1 и 2 легко различать между собой по знаку ∆y смежных сторон, примыкающих к вершинам. В случае 1 они совпадают, а в случае 2 – противоположны. Y 3 2 ∆y = 0 3 ∆y > 0 ∆y < 0 ∆y > 0 2 1 ∆y > 0 ∆y < 0 1 ∆y < 0 3 1 ∆y > 0 ∆y < 0 ∆y = 0 3 2 X Рис. 2.10 Для корректной обработки особых случаев примем следующее правило: если сторона многоугольника направлена вверх (∆y > 0), то из расчета точек пересечения со строками будем исключать ее начальную вершину, и наоборот, если сторона многоугольника направлена вниз (∆y < 0), то из расчета точек пересечения со строками будем исключать ее конечную вершину. В остальных случаях для каждой стороны нужно установить, пересекается ли она с текущей строкой, и если – да, то вычислить координату x точки пересечения. Пусть для очередной стороны многоугольника yi – координата y начальной вершины, а yk – координата y ее конечной вершины. Тогда критерием пересечения стороны со строкой Y будет выполнение следующего условия: ((yi < Y) и (yk >= Y)) или ((yi >= Y) и (yk < Y)). 33 (2.34) Легко установить, что помимо сторон, не пересекающихся со строкой Y, данное условие блокирует и обработку горизонтальных сторон, а также начальных вершин для сторон, направленных вверх, и конечных вершин для сторон, направленных вниз, т.е. обеспечивает корректное вычисление границ сегментов в особых случаях. С учетом сделанных выводов алгоритм закрашивания будет иметь вид, приведенный ниже. 1. Последовательно просматривая список вершин (P1, P2, . . , Pn), найти границы сканирования Ymin и Ymax. 2. Вычислить Ymin = max(Ymin, 0); Ymax = min(Ymax, Yеmax). 3. Для каждой строки Y из [Ymin . . Ymax] выполнить пп. 3.1 – 3.4. 3.1. Очистить список Xb. 3.2. Для всех i из [1. . n] выполнить п. 3.2.1 – 3.2.2. 3.2.1. Если i < n, то k = i + 1, иначе k = 1. 3.2.2. Если ((yi < Y) и (yk >= Y)) или ((yi >= Y) и (yk < Y)), то вычислить координату x точки пересечения стороны Pi Pk со строкой Y и записать в Xb. 3.3. Отсортировать список Xb по возрастанию. 3.4. Последовательно беря из списка Xb пары xl, xr , закрасить соответствующие им сегменты строки Y. В алгоритме для каждой строки Y сначала очищается список Xb границ сегментов, а затем циклически рассматриваются все стороны PiPk многоугольника, i – индекс текущей, а k – индекс последующей вершины. Учитывается, что за вершиной Pn следует вершина P1. В цикле производится тестирование сторон PiPk многоугольника по критерию (2.34). Для сторон, удовлетворяющих условию (2.34), вычисляется координата x точки пересечения стороны со строкой и записывается в Xb. Когда обработка списка вершин заканчивается, список Xb сортируется по возрастанию. Сортировка гарантирует, что после этого левые и правые границы сегментов при движении от начала к концу списка будут чередоваться, поэтому на заключительном этапе 34 для закрашивания сегментов строки из Xb последовательно берутся пары элементов. У данного алгоритма есть некоторые особенности. Во-первых, вершины локального максимума по Y будут всегда закрашиваться, а вершины локального минимума – нет (рис. 2.11). Это следствие принятого к обработке сторон критерия (2.34). На рис. 2.11 центры квадратиков соответствуют вершинам. Y X Рис. 2.11 Во-вторых, как видно из того же рисунка, тонкие слабонаклонные к оси OX выступы многоугольника могут закрашиваться не до конца и с разрывами. Здесь причина в построчном способе закрашивания. Максимальная погрешность в расчете границ сегментов из-за их округления составляет 0,5 пикселя, но погрешность в изображении 35 сторон в таких случаях может стать значительно большей. Чтобы визуально улучшить вид многоугольника и снизить погрешность изображения тонких слабонаклонных выступов, можно после завершения закрашивания обрисовать граничный контур многоугольника тем же цветом, что и цвет закраски. 2.7. АЛГОРИТМ ЗАКРАШИВАНИЯ ОРИЕНТИРОВАННЫХ МНОГОУГОЛЬНИКОВ Для определения внутренних точек закрашиваемой многоугольной области можно применить более формальное и более универсальное правило, основанное на использовании понятия ориентации граничного контура. Если исходить из того, что порядок вершин в списке (P1, P2 , . . , Pn) определяет и порядок построения сторон многоугольника, то каждую сторону PiPi+1 можно рассматривать как вектор, направленный из Pi в Pi+1. Тогда правило определения внутренних точек многоугольной области сформулируем следующим образом: при движении от начала всякого вектора граничного контура к его концу ближайшие внутренние точки области расположены слева от него (рис. 2.12). Y ∆y < 0 ∆y > 0 X Рис. 2.12 36 Из принятого правила следует, что при обходе вершин против часовой стрелки внутренние точки области лежат внутри многоугольника, а при обходе по часовой стрелке – вне многоугольника. В последнем случае должна закрашиваться вся область вывода кроме точек внутри граничного многоугольника. В соответствии со сказанным далее многоугольник будем считать ориентированным по часовой стрелке или против в зависимости от заданного в списке (P1, P2 , … , Pn) направления обхода его вершин. Использование понятия ориентации для границы многоугольника позволяет разрабатывать более универсальные алгоритмы закрашивания, имеющие и более широкие возможности. Как видно из рис. 2.12, стороны многоугольника, направленные вверх (приращение ∆y > 0), являются правыми границами, а стороны, направленные вниз (∆y < 0), – левыми границами закрашиваемых сегментов строки. Точки пересечения сторон с очередной строкой по знаку ∆y можно сразу классифицировать как левые или правые границы сегментов. В связи с этим вместо общего списка Xb границ сегментов строки здесь удобнее формировать отдельно список Xl левых и список Xr правых границ. Очевидно, что очередную координату x следует заносить в список Xr, когда ∆y > 0, и в список Xl – в противном случае. Когда все точки пересечения сторон многоугольника со строкой будут найдены, количество элементов в списках Xl и Xr должно быть одинаковым. Если граничный многоугольник ориентирован так, что должна закрашиваться внешняя область (по часовой стрелке), то все строки, не имеющие точек пересечения с многоугольником, должны закрашиваться полностью (рис. 2.13). Для остальных строк список Xl не будет содержать левой границы первого закрашиваемого сегмента, а список Xr не будет содержать правой границы последнего сегмента строки. В этих случаях для закрашивания в пределах области вывода в качестве недостающей левой границы первого сегмента следует 37 взять левую границу области вывода, а в качестве недостающей правой границы последнего сегмента строки – ее правую границу. Ориентацию (по часовой стрелке или против) граничного многоугольника можно определить аналитически. Для этого не требуется анализ взаимного расположения всех вершин. Ориентация граничного многоугольника совпадает с ориентацией невырожденного треугольника, составленного из высшей или низшей вершины многоугольника и двух смежных с ней вершин. Для определенности найдем в списке Pg наивысшую вершину Pj и две смежные с ней Pj -1 и Pj+1 (рис. 2.13). Y Ymax Pj Pj+1 Pj-1 Ymin Xemax X Рис. 2.13 Очевидно, что для расположения осей координат как на рис. 2.13 ориентация треугольника Pj -1 Pj Pj+1 будет по часовой стрелке (clockwise direction), если вершина Pj+1 правее вершины Pj -1, то есть xj+1 > xj -1. Иначе ориентация треугольника будет против часовой стрелки. Анализ показывает, что значение площади, вычисленное по этой формуле, положительно, если обход вершин Pj-1, Pj, Pj+1 соответствует движению против часовой стрелки, и отрицательно, если обход этих точек соответствует движению по часовой стрелке. Если рассматривается многоугольник без самопересечений, то его ориентация совпадает с ориентацией данного треугольника. Если же контур многоугольника 38 имеет самопересечения, то само понятие ориентации становится неприменимым. Ниже представлен алгоритм закрашивания ориентированных многоугольников, построенный на основании изложенного материала. 1. Последовательно просматривая список вершин (P1, P2 , . . , Pn), найти индекс j наивысшей вершины, а также границы сканирования Ymin и Ymax. 2. Вычислить Ymin = max(Ymin, 0); Ymax = min(Ymax, Yеmax). 3 . Если Pj +1.x > Pj -1.x, то CW = True, иначе CW = False. 4. Если CW, то строки области вывода от 0 до Ymin закрасить целиком. 5. Для каждой строки Y из [Ymin . . Ymax] выполнить пп. 5.1 – 5.5. 5.1. Очистить списки Xl и Xr. 5.2. Для всех i из [1. . n] выполнить п. 5.2.1 – 5.2.2. 5.2.1. Если i < n, то k = i + 1, иначе k = 1. 5.2.2. Если ((yi < Y) и (yk >= Y)) или ((yi >= Y) и (yk < Y)), то выполнить пп. 5.2.2.1 – 5.2.2.2. 5.2.2.1. Вычислить координату x точки пересечения стороны Pi Pk со строкой Y. 5.2.2.2. Если Pk.y – Pi.y > 0, то записать x в Xr, иначе – записать x в Xl. 5.3. Если CW, то дополнить список Xl левой границей области вывода, а список Xr – ее правой границей. 5.4. Отсортировать списки Xl и Xr по возрастанию. 5.5. Последовательно беря из списков Xl и Xr по одному элементу в качестве границ xl, xr сегмента, закрасить все сегменты строки Y. Причем, если xl > xr, то закрашивание производить не следует. 6. Если CW, то строки области вывода от Ymax до Yеmax закрасить целиком. Для обработки особых случаев в данном алгоритме используется тот же критерий, что и в предыдущем алгоритме. Особенностью является учет ориентации многоугольника, а также использование раздельных списков левых Xl и правых Xr границ сегментов строки. Следует отметить, что два рассмотренных алгоритма закрашивания отличаются между собой не только правилами выбора внутренних точек. Они дают разные результаты и в том случае, когда гранич39 ный контур области имеет самопересечения. Кроме того, второй алгоритм без существенных переделок пригоден и для закрашивания многосвязных областей, т.е. областей, ограниченных несколькими граничными многоугольниками. 2.8. ТЕОРЕТИКО-МНОЖЕСТВЕННЫЕ ОПЕРАЦИИ НАД ДВУМЕРНЫМИ ОБЛАСТЯМИ Для синтеза сложных фигур из примитивов используют теоретико-множественные операции (ТМО), такие, как объединение, пересечение, разность, симметрическая разность (рис. 2.14). A B A B Объединение A B A B A B A B A\ B A B Пересечение Разность Симметрическая разность Рис. 2.14 Если имеются примитивы с криволинейными границами, то такие границы аппроксимируются ломаными линиями из отрезков прямых, поэтому далее в качестве примитивов будем иметь в виду многоугольники. Результатом ТМО над многоугольниками может быть как односвязная, так и многосвязная область плоскости. Поиск точного описания границ результирующей области требует сложных вычислений и тонкого анализа возможных вариантов взаимного расположения границ исходных областей [4]. Достоинство этого подхода в том, что сложный алгоритм ТМО нужно выполнять только один раз, после чего для визуализации будут использоваться рассчитанные границы результирующей области. Другой подход к ТМО основан на том, что изображение формируется построчно, и поэтому ТМО про40 ще выполнять непосредственно во время визуализации над сечениями исходных областей строками растра. На рис. 2.15 показана реализация построчного выполнения ТМО над сечениями SA и SB исходных фигур A и B строками Y растра. A B Y SA SB S  S A  SB S  S A  SB S  S A \ SB S  S A  SB xAl xBl xAr xB r X Рис. 2.15 Переменная S обозначает сечение результирующей области, полученное с помощью ТМО над SA и SB. Сплошные участки сечений фигур будем называть сегментами; xAl, xBl, xAr, xBr – левые и правые границы сегментов для SA и SB. Поставим в соответствие внутренним точкам сегментов сечения S всякой многоугольной области функцию L(x), которую будем называть пороговой. Определим ее следующим образом: 0, если x  S ; L( x )   1, если x  S . 41 (2.35) Поведение пороговой функции для сечения S многоугольной области иллюстрирует рис. 2.16. Как видно, внутренним точкам области на строке Y соответствует значение L(x) = 1. Сечение S многоугольника строкой Y Y L(x) 1 X Рис. 2.16 Пусть теперь имеются сечения SA и SB одной строкой Y двух фигур A и B, над которыми необходимо произвести ТМО. Обозначим через La(x) и Lb(x) их пороговые функции. Рассмотрим взвешенную сумму Q(x) = gLa(x) + hLb(x) пороговых функций (рис. 2.17) для g ≠ h и g,h ≠ 0. Анализ свойств суммы Q(x) позволяет выделить области значений, соответствующие различным видам ТМО. Результат приведен в табл. 2.1. Таблица 2.1 Q(x) ≥ min(g, h) =g+h = g, h =g =h ТМО Объединение Пересечение Симметрическая разность Разность A\B Разность B\A 42 SA SB Q(x) g+h g h x Рис. 2.17 Из табл. 2.1 видно, что рассмотренный метод применим для реализации всех основных видов ТМО. 2.9. ПОСТРОЧНЫЙ АЛГОРИТМ ТМО Перейдем к разработке алгоритма выполнения ТМО над сечениями двух плоских фигур A и B. Будем считать, что в качестве исходных данных для очередной строки Y будут использоваться массивы левых Xal и правых Xar границ сегментов сечения SA фигуры A и массивы левых Xbl и правых Xbr границ сегментов сечения SB фигуры B. Закодируем все ТМО, а также примем конкретные значения весов для расчета Q(x): g = 2; h = 1. Тогда табл. 2.1 примет вид табл. 2.2. Код заданной ТМО также будет параметром алгоритма. Таблица 2.2 Код ТМО 1 2 3 4 5 ТМО Q(x) ≥1 =3 = 1, 2 =2 =1 Объединение Пересечение Симметрическая разность Разность A\B Разность B\A Для совместной обработки исходных границ сегментов используем рабочий массив M. Элементы массива M представляют собой записи с 43 полями M[i].x и M[i].dQ. Поле M[i].x служит для записи координаты x границы сегмента, а поле M[i].dQ – для записи соответствующего приращения пороговой функции с учетом веса операнда. Поле dQ необходимо для того, чтобы при последовательном просмотре массива M можно было однозначно восстановить вид функции Q(x). Результатом работы алгоритма будут массивы Xrl и Xrr левых и правых границ сегментов сечения S результирующей области R строкой Y. Кроме упомянутых выше в алгоритме использованы также следующие переменные: SetQ – множество значений Q(x), соответствующее заданной ТМО; k и m – счетчики элементов соответственно в массивах Xrl и Xrr; Xemin и Xemax – соответственно левая и правая границы области вывода. Для удобства представления алгоритма используется функция Length(X), возвращающая заполненное количество элементов в массиве X. Алгоритм выполнения любой из перечисленных в табл. 2.2 ТМО представлен ниже. 1. Если TMO = 1, то SetQ = [1, 3] {объединение} иначе если TMO = 2, то SetQ = [3, 3] {пересечение} иначе если TMO = 3, то SetQ = [1, 2] {сим. разность} иначе если TMO = 4, то SetQ = [2, 2] {разность А – В} иначе если TMO = 5, то SetQ = [1, 1] {разность B – A} 2. n = Length(Xal). 3. Для всех i из [1. . n] выполнить M[i].x = Xal[i]; M[i].dQ = 2. 4. nM = n; n = Length(Xar). 5. Для всех i из [1. . n] выполнить M[nM + i].x = Xar[i]; M[nM + i].dQ= -2. 6. nM = nM + n; n = Length(Xbl). 7. Для всех i из [1. . n] выполнить M[nM + i].x = Xbl[i]; M[nM + i].dQ = 1. 8. nM = nM + n; n = Length(Xbr). 9. Для всех i из [1. . n] выполнить M[nM + i].x = Xbr[i]; M[nM + i].dQ = -1, 10.nM = nM + n; {общее число элементов в массиве M} 11.Отсортировать массив M по возрастанию M[i].x. 12.k = 1; m = 1; Q = 0. 44 13.Если (M[1].x >= Xemin) и (M[1].dQ < 0), то Xrl[1] = Xemin; Q = -M[1].dQ; k = 2. 14.Для всех i из [1. . nM] выполнить пп. 14.1 – 14.4. 14.1. x = M[i].x; Qnew = Q + M[i].dQ. 14.2. Если (Q  SetQ) и (Qnew  SetQ), то Xrl[k] = x; k = k + 1. 14.3. Если (Q  SetQ) и (Qnew  SetQ), то Xrr[m] = x; m = m + 1. 14.4. Q = Qnew. 15. Если Q  SetQ, то Xrr[m] = Xemax. В первой части алгоритма границы сегментов из исходных массивов Xal, Xbl, Xar, Xbr переписываются в рабочий массив M. При этом в поле dQ записываются приращения пороговых функций с учетом веса операндов. Цель сортировки массива M по возрастанию – упорядочивание значений аргумента функции Q(x). После сортировки начинается обработка массива M. Особым случаем является такой, когда первым элементом массива M оказывается правая граница сегмента, т.е. M[1].x >= Xemin и M[1].dQ < 0. В этой ситуации список Xrl левых границ сегментов необходимо дополнить значением Xemin. В циклической части алгоритма последовательно просматриваются элементы массива M. В качестве текущего значения переменной x всегда выбирается очередное значение M[i].x. При этом функция Q изменяется на величину M[i].dQ. Если в очередном цикле предыдущее значение Q не входило в SetQ, а новое ее значение Qnew в SetQ входит, значит x – координата левой границы сегмента результирующей области. Это значение записывается в Xrl. Аналогичным образом устанавливаются случаи, в которых x является координатой правой границы. Такие значения x записывается в массив Xrr. По завершении цикла обработки M число левых границ в массиве Xrl должно быть равно числу правых границ в массиве Xrr. Если же в этот момент Q  SetQ, значит не найдена правая граница последнего сегмента. Тогда за нее принимается правая граница Xemax области вывода. 45 2.10. ДВУМЕРНЫЕ ГЕОМЕТРИЧЕСКИЕ ПРЕОБРАЗОВАНИЯ Практически всегда над объектами требуется производить преобразования, направленные на изменение их положения на плоскости, размеров или ориентации. Будем называть такие преобразования геометрическими. В математике перечисленные преобразования относятся к линейным преобразованиям над координатами (x, y) точек объектов и описываются линейными зависимостями: x'  a11 x  a12 y  a13 ; y '  a21 x  a22 y  a23 . (2.36) Здесь (x, y) – координаты точки (x, y) после преобразования. Для линейных преобразований характерно то, что прямая линия преобразуется в прямую, при этом углы между прямыми могут изменяться. Наиболее распространенными видами линейных преобразований, из комбинации которых можно представить любое другое линейное преобразование, являются:  плоскопараллельное перемещение;  масштабирование;  поворот. Например, плоскопараллельное перемещение точки (x, y) на расстояние mx по оси x и на my по оси y записывается как x'  x  mx ; y'  y  my . (2.37) Чтобы все линейные преобразования можно было представить единообразно в матричной форме, удобно использовать применяемые в проективной геометрии однородные координаты [5, 7, 8]. Замена обычных координат однородными состоит в том, что всякой точке (x, y) на плоскости OXY можно поставить в соответствие точку в координатном пространстве OXYV с координатами (xТ, yТ, v), называемыми однородными координатами, причем v  0 и v = const для всех точек плоскости OXY (рис. 2.18). Соответствие между обычными (де46 картовыми) и однородными координатами устанавливается следующим правилом преобразования однородных координат в декартовы: x = xТ / v; y = yТ / v. Y (2.38) v = const yТ /v (x, y) (xТ, yТ, v) v /(1 – v) xТ /v V v X Рис. 2.18 Из соотношений (2.38) следует, что все прямые, связывающие точки в однородной системе координат с соответствующими им точками на плоскости OXY, сходятся в одной точке на оси OV с координатами (0, 0, v/(1 – v)). Если возможно, то стремятся использовать значение v = 1. При этом прямые, связывающие точки в однородной и декартовой системах координат, будут параллельны оси OV, а однородные координаты xТ, yТ совпадают с обычными. Далее для описания геометрических преобразований будем использовать однородные координаты. В однородных координатах любое линейное геометрическое преобразование можно представить в матричной форме следующим образом: x ' y ' v   x  w11 y 1   w21   w31 w12 w22 w32 w13  w23   C  W .  w33  (2.39) Здесь C = [x y 1] – матрица исходных координат; C' = [x' y' v] – матрица новых координат после преобразования; W – матрица преоб47 разования. Отметим, что v = 1 только для тех преобразований, в матрице W которых w13, w23 = 0 и w33 = 1. Для всякого линейного преобразования существует точка, называемая центром преобразования, для которой это преобразование инвариантно, т.е. не изменяет координат этого центра. Преобразование плоскопараллельного перемещения (сдвига) задается следующим образом: 1  C'  C   0 mx 1 my 0  0  x  mx 1 y  m y 1. (2.40) Здесь mx, my – смещения по соответствующим осям. Для плоскопараллельного перемещения центром преобразования формально считается точка (, , 1) . Преобразование масштабирования относительно начала координат sx C'  C   0   0 sy 0 0  s x x s y y 1 .  1   (2.41) Здесь sx, sy – масштабные коэффициенты по соответствующим осям. Масштабными коэффициентами могут быть любые числа, отличные от 0. При sx, sy > 1 преобразование приводит к увеличению размеров, а при sx, sy < 1 – к уменьшению. Если sx = sy, масштабирование называется пропорциональным. При отрицательных значениях масштабных коэффициентов происходит не только изменение размеров, но и зеркальное отражение преобразуемой фигуры относительно соответствующей оси. В частности, преобразование   1 0 0 C '  C   0  1 0   x  y 1    0 0 1 (2.42) задает отражение относительно осей OX и OY, что эквивалентно повороту на 1800. 48 Преобразование поворота на угол  относительно начала координат  cos  C '  C   sin    0 sin  cos  0 0 .  1 (2.43) Направление поворота определяется знаком угла  . 2.11. СОВМЕЩЕНИЕ ПРЕОБРАЗОВАНИЙ. ПРЕОБРАЗОВАНИЕ ОТНОСИТЕЛЬНО ЗАДАННОГО ЦЕНТРА Часто над объектами приходится последовательно выполнять несколько преобразований. Пусть последовательность преобразований задана матрицами W1, W2, . . . , Wn. Рассмотрим преобразование точки с координатами C = [x y 1]. В результате преобразования W1 получим C '  C W1 , (2.44) C"  C 'W2  C W1 W2 . (2.45) а после преобразования W2 Продолжая выполнять очередные преобразования, в итоге будем иметь n C ( n )  C  W1  W2  ...  Wn  C   Wi . i 1 (2.46) n Если вычислить матрицу U   Wi , то заданную последовательi 1 ность преобразований можно заменить одним результирующим преобразованием с матрицей U. Замечание. Умножение матриц некоммутативно, поэтому матрицы W1, W2, . . . , Wn следует умножать в той последовательности, в которой они заданы. Такие элементарные преобразования, как масштабирование и поворот, приведенные в форме (2.41) - (2.43), выполняются относитель49 но начала координат. Если же преобразование W необходимо выполнить относительно произвольно заданного центра (xc , yc), то его производят в следующей последовательности. 1. Заданную точку P с матрицей координат С и центр преобразования сместить преобразованием M так, чтобы центр преобразования совпал с началом координат: C'  C  M . (2.47) 2. Выполнить над P заданное преобразование W относительно начала координат, а, следовательно, и относительно заданного центра преобразования: C ' '  C 'W  C  M  W . (2.48) 3. Обратным преобразованием перемещения M-1 точку и центр преобразования сместить так, чтобы центр преобразования снова оказался на исходном месте: C ' ' '  C"M 1  C  M W  M 1. (2.49) Матрица преобразования смещения M и обратная ей матрица M-1 имеют следующий вид:  1 M  0   xc 1  yc 0 1 0 ; M 1   0   1  xc 1 yc 0 0.  1 (2.50) Таким образом, матрица U результирующего преобразования относительно заданного центра вычисляется как U  M W  M 1 . (2.51) Предварительный расчет матрицы U перед выполнением преобразования позволяет сократить объем вычислений при расчете новых координат точек. 50 2.12. ПРЕОБРАЗОВАНИЕ АЛГЕБРАИЧЕСКИХ ЛИНИЙ Линейные геометрические преобразования можно применять не только к отдельным точкам, но и к другим объектам, имеющим аналитическое описание. В частности, можно производить преобразование алгебраических линий. Уравнение прямой линии общего положения a1 x + a2 y + a3 = 0 (2.52) представим в матричной форме: C  A = 0, (2.53)  a1  где C  x y 1, A  a2  .    a3  Пусть над линией необходимо выполнить преобразование с матрицей W, т.е. всякой точке на прямой с матрицей исходных координат С нужно поставить в соответствие точку с матрицей координат C = C  W. Из последнего соотношения выразим C. Для этого умножим обе части равенства на матрицу W -1, обратную матрице W: C   W -1 = C  W  W –1. (2.54) После сокращения получим С = C   W –1. Подставим выражение для C в исходное уравнение прямой (2.53): C   W -1  А = 0. (3.55) Поскольку C – матрица координат после преобразования, то уравнение (2.55) будет соответствовать той же прямой после преобразования, а W -1  А – это матрица-столбец коэффициентов уравнения прямой после преобразования, т.е. для преобразования с матрицей W формула для расчета матрицы A новых коэффициентов уравнения прямой имеет следующий вид: A = W -1  А. 51 (2.56) Рассмотрим теперь преобразование линии 2-го порядка общего вида с уравнением a11 x 2  a22 y 2  2 a12 x y  2 a13 x  2 a23 y  a33  0. (2.57) Представим (2.59) в матричной форме: C  A  C Т = 0, (2.58)  a11 a12 a13  где A  a21 a22 a23  – матрица коэффициентов уравнения линии.   a31 a32 a33  Причем матрица A симметрическая, т.е. aij = aji для i, j = 1, 2, 3. Матрица-столбец C Т означает транспонированную матрицу C. Как и в предыдущем случае, сделаем в уравнении (2.58) замену С = C   W –1. В результате получим С  W –1  A  (C   W –1)T = 0. (2.59) Чтобы привести (2.59) по форме к первоначальному виду, воспользуемся следующей известной в математике формулой о транспонировании произведения матриц: (C  W –1)T = (W –1)T  (C)T. На основании нее уравнение (2.59) можно представить следующим образом: С  W –1  A  (W –1)T  (C)T = 0. (2.60) Сравнивая (2.58) и (2.60), можно заключить, что W –1  A  (W –1)T должно быть матрицей коэффициентов уравнения линии. Следовательно, формула для вычисления новых коэффициентов уравнения линии 2го порядка после преобразования W будет иметь следующий вид: A = W –1  A  (W –1)T. (2.61) Приведенные здесь выводы позволяют производить геометрические преобразования над любыми объектами, заданными в аналитическом виде. 52 2.13. НЕПРЕРЫВНЫЕ ГЕОМЕТРИЧЕСКИЕ ПРЕОБРАЗОВАНИЯ Непрерывные геометрические преобразования – важный инструмент в интерактивных графических программах, с помощью которого производится построение и размещение фигур на экране монитора. Другим применением непрерывных преобразований является анимация, т.е. моделирование различных видов движения объектов по заранее разработанным траекториям или других непрерывных изменений их геометрии. В силу дискретного характера формирования изображения в компьютере плавные, непрерывные преобразования получают как последовательность малых преобразований. Результат каждого преобразования, как кадр фильма, выводится на экран. Реализация непрерывных преобразований возможна в двух формах – интегральной и дифференциальной. В интегральной форме в любой момент времени t матрица С(t) текущих координат рассчитывается на основе матрицы С0 исходных, т.е. первоначально заданных и неизменяемых координат: C(t) = C0  W(t), (2.62) где W(t) – матрица текущего преобразования на момент времени t. Начальным значением матрицы W(t) для t = 0 будет единичная матрица I, т.е. W(0) = I. В дифференциальной форме для расчета матрицы С(t + ∆t) новых координат на очередном шаге преобразования используется матрица С(t) координат, полученных на предыдущем шаге: C(t + ∆t) = C(t)  ∆W, (2.63) где ∆W – матрица элементарно малого преобразования за время ∆t. Начальным значением С(t) при t = 0 будет матрица первоначально заданных координат, т.е. С(0) = C0. В программах, моделирующих движение объектов в реальных условиях, параметры t и ∆t соответствуют времени. В большинстве же других графических приложений более важным бывает сам факт 53 движения объектов. Тогда в качестве величины, сопоставимой со временем, удобнее использовать программные циклы по расчету результатов элементарных преобразований и визуализации, т.е. t в этом случае будет соответствовать номеру цикла, а ∆t = 1. Ниже показано, как в интегральной форме выглядят частные виды непрерывных преобразований. Преобразование плоскопараллельного перемещения  1 0   C (t )  C0  M (t )  C0   0 1 0 , mx (t ) m y (t ) 1 (2.64) где mx(t) и my(t) – функции, задающие непрерывное перемещение по соответствующим осям. Для равномерного прямолинейного перемещения mx(t) = vxt; my(t) = vy t, где vx, vy – составляющие скорости [1/цикл]. Преобразование вращения относительно начала координат  cos  (t ) sin  (t ) 0 C (t )  C0  R(t )  C0   sin  (t ) cos  (t ) 0 .    1 (2.65) Функция  (t ) определяет непрерывное изменение угла поворота. Для моделирования равномерного вращения  (t )  w t следует задать угловую скорость w [рад/цикл]. Преобразование масштабирования относительно начала координат 0  s x (t ) C (t )  C 0  S (t )  C 0   0 s y (t ) 0 ,    0 1 (2.66) где sx(t) и sy(t) – функции, задающие непрерывное изменение масштабных коэффициентов по соответствующим осям. Для моделирования линейного изменения масштабов по осям со скоростями vx и vy формулы изменения масштабных коэффициентов будут следующими: 54 s x (t )  1  v x t ; s y (t )  1  v y t ; 0  | v x |, | v y |  1. (2.67) При программной реализации этого закона необходимо контролировать и не допускать использование нулевых значений sx(t) и sy(t), приводящих к вырождению преобразуемых объектов. Эффекту приближения и удаления фигур лучше соответствует показательный закон изменения масштаба: s x (t )  (1   x ) t ; s y (t )  (1   y ) t ; 0 |  x |, |  y | 1. (2.68) Этот закон удобен и в реализации, так как нулевые значения sx(t) и sy(t) здесь исключаются. Простейшие законы изменения параметров в приведенных непрерывных преобразованиях даны в качестве примеров. Если необходимо, то можно использовать и более сложные законы, в том числе и задаваемые с помощью различных средств ввода: мыши, джойстика, трекбола и других устройств управления или контроля. Например, в системах виртуальной реальности значения этих параметров поступают с датчиков, контролирующих движения пользователя. Теперь рассмотрим, как выглядят непрерывные преобразования в дифференциальной форме. Плоскопараллельное перемещение:  1 0 0   C (t  t )  C (t )  M  C (t )   0 1 0. mx m y 1 (2.69) Здесь ∆mx, ∆my – элементарно малые перемещения по соответствующим осям за время ∆t. 55 Вращение вокруг начала координат:  cos  sin  0 C (t  t )  C (t )  R  C (t )   sin  cos  0 .    0 1 (2.70) Здесь ∆φ – элементарно малый угол поворота за время ∆t. Масштабирование относительно начала координат: 0 1   x C (t  t )  C (t )  S  C (t )   0 1   y 0 .    0 1 (2.71) Здесь (1 + δx), (1 + δy) – элементарно малые изменения масштабных коэффициентов. Заметим, что моделирование масштабирования в дифференциальной форме по результату соответствует масштабированию в интегральной форме на основе показательного закона изменения масштабных коэффициентов. Сравнивая между собой интегральную и дифференциальную формы геометрических преобразований, можно сделать следующие выводы:  в дифференциальной форме ошибки от каждого элементарного преобразования со временем накапливаются в значениях координат, что при большом числе шагов преобразования может привести к отклонению от заданной траектории и к необратимым искажениям формы фигур, интегральная форма исключает накопление погрешности;  в интегральной форме легко задавать различные законы изменения параметров, в дифференциальной форме легко реализуются только линейные законы изменения параметров (для масштабирования – показательный). 56 2.14. ЛИНЕЙНЫЕ ПРЕОБРАЗОВАНИЯ ФРАГМЕНТОВ ИЗОБРАЖЕНИЯ При работе с готовыми растровыми изображениями часто возникает необходимость в преобразовании какого-либо выделенного фрагмента изображения в другую заданную область. Исходное и результирующее изображения могут размещаться либо непосредственно в видеопамяти, либо в оперативной памяти (обычно в формате bitmap). Рассмотрим вначале частный случай, когда обе области – исходная Im1 и новая Im2 ограничены параллелограммами, причем ориентация и размеры параллелограммов могут быть различными (рис. 2.19). Y W T4 P1 P4 T1 P T Im2 P2 Im1 P3 T3 T2 X Рис. 2.19 Для задания области Im1 достаточно указать три вершины параллелограмма, например T1, T2 и T3. Координаты вершины T4 при необходимости несложно рассчитать по точкам T1, T2 и T3. Область Im2 также должна быть задана тройкой вершин P1, P2, P3, соответствующих вершинам T1, T2, T3. Координаты точки Р4. можно найти по координатам точек P1, P2, P3. Если иметь преобразование W, ставящее в соответствие всякой точке P из Im2 точку T из Im1 (см. рис. 2.19), то поставленную задачу можно решить путем построчного сканирования области Im2, в процессе которого для каждой точки P с целочисленными координатами 57 из Im2 с помощью W находится соответствующая точка T в Im1. Когда точка T найдена ее цветом нужно закрасить точку P. Для наглядности матрицы-строки однородных координат точек T1, T2, T2, P1, P2, P3 будем обозначать так же, как и сами точки: T1 = [xT1 yT1 1], T2 = [xT2 yT2 1], T3 = [xT3 yT3 1]; P1 = [xP1 yP1 1], P2 = [xP2 yP2 1], P3 = [xP3 yP3 1]. Преобразование W должно быть единым для всех точек области прибытия Im2, в том числе и для точек P1, P2, P3, соответствующих точкам T1, T2, T3. Поэтому T1 = P1 W; (2.72) T2 = P2 W; (2.73) T3 = P3 W. (2.74) Отметим, что преобразование W должно возвращать значение координаты v=1 . Чтобы найти W, объединим соотношения (2.72) – (2.74) в общую формулу: Mt = Mp W,  P1   xP1 где M p   P2    xP 2     P3   xP 3 y P1 1 T1   xT 1 y P 2 1, M t  T2    xT 2     T3   xT 3 y P 3 1 (2.75) yT 1 1 yT 2 1.  yT 3 1 Умножим слева обе части уравнения (2.77) на матрицу Mp -1 , обратную матрице Mp: Mp -1  Mt = Mp -1  Mp  W. 58 (2.76) В результате получим формулу для вычисления коэффициентов матрицы W искомого преобразования: W = Mp -1  Mt. (2.77) Ниже приводится алгоритм преобразования фрагмента изображения из области Im1 в область Im2. 1. Последовательно просматривая список вершин (P1, P2, P3, P4) области прибытия, найти границы ее сканирования Ymin и Ymax. 2. Для каждой строки Y из [Ymin . . Ymax] выполнить пп. 2.1 – 2.2. 2.1. Найти координаты xl и xr левой и правой точек пересечения области Im2 со строкой Y. 2.2. Для каждого целого X из [xl . . xr] выполнить пп. 2.2.1– 2.2.2. 2.2.1. Преобразовать с помощью преобразования W точку P = (X, Y) области Im2 в область Im1, т.е. вычислить координаты (X1, Y1) соответствующей точки T. 2.2.2. Считать код цвета точки T и переписать его в точку P. Данный алгоритм гарантированно заполняет новую область Im2 пикселями из Im1 без пропусков и повторений. При его реализации следует учитывать, что при хотя бы частичном наложении Im1 и Im2, размещающихся в общей области памяти, корректность работы алгоритма может нарушиться из-за попадания точек области Im2 в область Im1 и возможности включения их в производимые преобразования. В рассмотренном частном случае выполнялось преобразование фрагмента изображения, ограниченного параллелограммом. Однако преобразованию (2.72) можно подвергнуть и все исходное изображение. Для вычисления матрицы W в этом случае нужно лишь задать на исходном изображении любую тройку точек, не лежащих на одной прямой, и поставить им в соответствие три точки результирующей области. 59 2.15. ГРАФИЧЕСКАЯ БИБЛИОТЕКА OPENGL Для облегчения разработки графических приложений на более высоком уровне необходимы программные инструменты, содержащие в себе наборы базовых алгоритмов таких, как визуализация простых геометрических объектов. Одним из самых популярных прикладных программных интерфейсов для разработки приложений в области двумерной и трехмерной графики является OpenGL (Open Graphics Library – открытая графическая библиотека). OpenGL ориентируется на следующие две задачи:  cкрыть сложности адаптации различных 3D-ускорителей, предоставляя разработчику единый API1;  cкрыть различия в возможностях аппаратных платформ за счет реализации недостающей функциональности с помощью программной эмуляции. Основным принципом работы OpenGL является получение наборов векторных графических примитивов в виде точек, линий и многоугольников с последующей математической обработкой полученных данных и построением растровой картинки на экране и/или в памяти. OpenGL является низкоуровневым процедурным API, что вынуждает программиста писать точную последовательность шагов, чтобы сформировать результирующее растровое изображение (императивный подход). Это является основным отличием от дескрипторных подходов, когда вся сцена представляется в виде структуры данных (чаще всего дерева), которая обрабатывается и строится на экране. С одной стороны, императивный подход требует от программиста глубокого знания законов трехмерной графики и математических моделей, с другой стороны – дает свободу внедрения различных инноваций. API (Application Programming Interface) интерфейс программирования приложений набор готовых классов, структур, процедур и функций, предоставляемых приложением (библиотекой, сервисом) для использования во внешних программных продуктах. 1 60 Стандарт OpenGL был разработан и утвержден в 1992 году ведущими фирмами в области разработки программного обеспечения как эффективный аппаратно-независимый интерфейс, пригодный для реализации на различных платформах. Основой стандарта стала библиотека IRIS GL, разработанная фирмой Silicon Graphics Inc. На сегодняшний день графическая система OpenGL поддерживается большинством производителей аппаратных и программных платформ. OpenGL может использоваться в среде Windows, в операционной системе Mac OS X компьютеров Apple. Свободно распространяемые коды системы можно компилировать в большинстве операционных систем, в том числе в Linux. OpenGL состоит из набора библиотек. Все базовые функции хранятся в основной библиотеке GL. В OpenGL все примитивы и более сложные объекты являются трехмерными, поэтому двумерная графика - это частный случай трехмерной. Помимо библиотеки GL OpenGL включает в себя несколько дополнительных библиотек. Первая из них GLU (GL Utility) – библиотека утилит GL. Все функции GLU определены через базовые функции GL. В состав GLU вошла реализация более сложных функций, таких как набор популярных геометрических примитивов (куб, шар, цилиндр, диск, тор), функции построения сплайнов, реализация дополнительных операций над матрицами и т.п. OpenGL не включает в себя никаких специальных команд для работы с окнами или для ввода информации от пользователя. Поэтому были созданы специальные переносимые библиотеки для обеспечения часто используемых функций взаимодействия с пользователем и для отображения информации с помощью оконной подсистемы. Наиболее популярной является библиотека GLUT (GL Utility Toolkit). Формально она не входит в OpenGL, но фактически включается почти во все его дистрибутивы и имеет реализации для различных платформ. GLUT предоставляет только минимально необходимый набор функций для создания OpenGLприложения. 61 В платформе .NET Framework, применяемой в Visual Studio (Microsoft), нет прямой поддержки данной библиотеки. Поэтому для разработки проектов в Visual Studio удобно использовать библиотеки, включающие в себя OpenGL, и ориентированные на использование в Visual Studio. К числу таких библиотек относятся библиотеки Tao Framework и OpenTK. Tao Framework – свободно распространяемая библиотека, с открытым исходным кодом, предназначенная для быстрой и удобной разработки кросс-платформенного мультимедийного программного обеспечения в среде .NET Framewrok. В состав библиотеки на данный момент входят все современные средства, которые могут понадобиться в ходе разработки мультимедиа программного обеспечения: реализация библиотек OpenGL, FreeGLUT и многие другие. Функции OpenGL реализованы в модели клиент-сервер. Приложение выступает в роли клиента. Оно вырабатывает команды, а сервер OpenGL интерпретирует и выполняет их. Сам сервер может находиться как на том же компьютере, на котором находится клиент (например, в виде динамически загружаемой библиотеки DLL), так и на другом (при этом может быть использован специальный протокол передачи данных между машинами). GL обрабатывает и рисует в буфере кадра графические примитивы с учетом некоторого числа выбранных режимов. Каждый примитив – это точка, отрезок, многоугольник и т.д. Каждый режим может быть изменен независимо от других. Определение примитивов, выбор режимов и другие операции описываются с помощью команд в форме вызовов функций прикладной библиотеки. Примитивы определяются набором из одной или более вершин (vertex). Вершина определяет точку, конец отрезка или вершину многоугольника. С каждой вершиной ассоциируются некоторые данные (координаты, цвет, нормаль, текстурные координаты и т.д.), называемые атрибутами. В большинстве случаев каждая вершина обрабатывается независимо от других. 62 С точки зрения разработчиков, OpenGL – это набор команд, которые управляют использованием графической аппаратуры. Если аппаратура состоит только из адресуемого буфера кадра, тогда OpenGL полностью поддерживается центральным процессором. Обычно графический адаптер предоставляет различные уровни ускорения: от аппаратной реализации вывода линий и многоугольников до сложных графических процессоров с поддержкой различных операций над геометрическими данными. Этим повышается производительность графических приложений и одновременно разгружается центральный процессор. 2.16. СИНТАКСИС КОМАНД OPENGL. ДВУМЕРНЫЕ ПРИМИТИВЫ Все команды (процедуры и функции) библиотеки GL начинаются с префикса gl, все константы – с префикса GL_. Соответствующие команды и константы библиотек GLU и GLUT аналогично имеют префиксы glu (GLU_) и glut (GLUT_). Чтобы не было путаницы в именах функций, используют несколько договоренностей (правил), по которым строятся имена функций OpenGL. Кроме префикса, в имена команд входят суффиксы, несущие информацию о числе и типе передаваемых параметров. В OpenGL полное имя команды имеет следующий формат: gl[n][type] После названия функции указывается количество n параметров (если существуют одноименные функции с разным числом параметров). И, наконец, в конце добавляется окончание type, указывающее тип параметров (Табл. 2.3). Таблица 2.3 i Тип OpenGL параметров GLint целое ui GLuint целое без знака type Описание 63 s GLshort короткое целое us GLushort короткое целое без знака b GLbyte байт ub Lubyte байт без знака f GLfloat вещественное, с плавающей точкой d GLdouble вещественное двойной длины v этот символ показывает, что в качестве параметров функции используется указатель на массив значений Например: glVertex2d(1.0, 0.5); // 2d означает: 2 параметра типа GLdouble glVertex3f(1.0f, 0.5f, 0.0f); // 3f означает: 3 параметра типа GLfloat Символы в квадратных скобках в некоторых названиях не используются. В документации по OpenGL, чтобы не перечислять все функции одного семейства, принято записывать только имя общей части всех функций семейства и в конце ставить звёздочку "*". Например, функции, задающие координаты вершин записывают так: glVertex*. Любой трехмерный объект, какой бы сложный он не был, строится из двухмерных (плоских) составляющих. Эти составляющие в OpenGL называются примитивами. Примитивы определяются одной или несколькими вершинами (точками в трехмерном пространстве), которые в OpenGL задаются внутри командных скобок glBegin/glEnd: procedure glBegin(mode); procedure glEnd(); Параметр mode задает вид примитивов. Доступны следующие значения, приведенные в табл.2.4. 64 Таблица 2.4 Mode GL_POINTS Описание Каждая вершина – отдельная точка GL_LINES Каждая пара вершин – отдельный отрезок прямой. 1 3 2 GL_LINE_STRIP 4 7 3 2 5 4 Замкнутая ломаная линия 1 2 3 4 5 6 GL_TRIANGLES 8 5 Ломаная линия 1 GL_LINE_LOOP 6 Каждая тройка вершин – отдельный треугольник 1 9 2 3 5 4 7 8 6 GL_TRIANGLE_STRIP Лента связанных треугольников. 3 5 1 6 4 2 GL_TRIANGLE_FAN Веер связанных треугольников. 1 5 3 2 65 4 GL_QUADS Каждые четыре вершины – отдельный четырехугольник. 2 3 8 5 1 4 GL_QUAD_STRIP 6 Лента связанных четырехугольников. 6 4 2 8 1 GL_POLYGON 7 3 5 7 Один выпуклый многоугольник 1 2 6 4 5 3 Polygon - закрытая область, определенная с помощью vertices. Ребра в полигоне не должны пересекаться. Полигон также должен быть выпуклым. На число сегментов ограничений нет. Rectangles - этот графический примитив прорисовывается командой glRect*(). Каждый полигон имеет 2 стороны - front и back. Это позволяет правильно рисовать обьекты,имеющие внутренние невидимые полости. Функция glPolygonMode() - контролирует прорисовку полигонов: glPolygonMode(GL_FRONT, GL_FILL); glPolygonMode(GL_BACK, GL_LINE). Полигоны, у которых ваются front-facing. Команда glCullFace() совместно с командой вершины появляются в порядке против часовой стрелки, назыФункция glFrontFace() контролирует этот процесс. задает порядок прорисовки - front или back, выполняется glEnable(). Для задания вершины предусмотрена процедура: glVertex[2 3 4][s i f d][v](coord) Вершины задаются в однородном пространстве OXYZW координатами (x, y, z, w), Команда glVertex2* (x, y) задает вершину на 66 плоскости OXY, при этом автоматически устанавливается z = 0 и w = 1. Например, glVertex2f(1, 0.1) создает точку с вещественными координатами x = 1, y = 0.1, z = 0, w = 1. В команде glVertex3* (x, y, z) автоматически устанавливается w = 1. Если используется формат glVertex3* (x, y, z, w), то нужно указывать все четыре координаты. Для визуализации координаты x, y, z делятся на w. Дополнительными командами с каждой вершиной можно связать такие данные, как:  текущий цвет (окончательный цвет высчитывается с учетом света от источников света), задается процедурой glColor*;  текущие координаты текстуры, задаются процедурой glTexCoord*;  текущая нормаль (нормальный вектор в данной вершине), задается процедурой glNormal*;  текущая позиция растра – используется для определения положения растра при работе с пикселями и битовыми массивами, задается процедурой glRasterPos* . Что касается примитивов, то, как уже указывалось, они задаются конструкциями с использованием glBegin и glEnd. Ниже приведены несколько примеров задания примитивов. glBegin(GL_TRIANGLES); glColor3f(1.0, 0.0, 0.0); // красный glVertex3f(0.0, 0.0, 0.0); glColor3ub(0,255,0); // зеленый glVertex3f(1.0, 0.0, 0.0); glColor3f (0.0, 0.0, 1.0); // синий glVertex3f(1.0, 1.0, 0.0); glEnd(); Команды glColor* задают текущий цвет вершин. В данном примере цвета задаются в RGB-формате относительными значениями цветовых компонент в интервале 0 – 1. 67 2.17. ВИЗУАЛИЗАЦИЯ ГРАФИКИ OPENGL Основным назначением библиотеки OpenGL является проектирование и визуализация трехмерных сцен. Двумерная графика представляет частный случай трехмерной. Поэтому для визуализации помимо задания геометрии объектов, цвета их поверхности и других свойств необходимо также с помощью специальных команд определить ряд параметров и настроить некоторые инструменты. Для вывода изображения необходимо определить область вывода. Без этого изображение не будет отображаться. Область вывода определяется с помощью команды glViewport (x, y, width, height) Параметры x, y задают положение верхнего левого угла области на PictureBox (или ином объекте области вывода), а width, height – ее ширину и высоту. Если OpenGL инициализирована с помощью Tao Framework, то область вывода с такими параметрами задается автоматически. Команда glClearColor(r, g, b, alfa) задает цвет фона в формате RGBA. Параметры r, g, b – значения составляющих цвета, alfa – значение α-канала. Используется для реализации различных визуальных эффектов, например, прозрачности. Если такие эффекты не используются, то alfa = 1. Перед формированием изображения необходимо очистить буфера цвета и глубины. Для этого используется вызов команды Clear: glClear(mask) Параметр mask задается константой библиотеки Gl. Если в качестве параметра используется константа GL_COLOR_BUFFER_BIT то очищается буфер изображения. Буфер заполняется фоновым цветом. Буфер глубины используется для визуализации трехмерных сцен. Визуализация пространственной сцены, в том числе и состоящей из фигур в плоскости OXY, всегда выполняется путем проецирования. Поэтому параметры проецирование также важно задавать, как и 68 область вывода. Для двумерных объектов формально надо использовать ортогональное проецирование на плоскость OXY. В OpenGL для этого имеется команда glOrtho. Она формирует матрицу проецирования, на которую умножаются координаты вершин примитивов. Формат команды: glOrtho(l, r, b, t, n, f) Каждая пара параметров определяет координаты границ области видимости для каждой из осей координат: l, r – левая и правая границы области видимости по оси OX; b, t – нижняя и верхняя границы области видимости по оси OY; n, f – ближняя и дальняя границы области видимости по оси OZ. Фактически параметры команды определяют расположение граничных плоскостей, ограничивающих видимую область пространства. Обычно эту команду задают со следующим набором параметров glOrtho(-1, 1, -1, 1, -1, 1) Таким образом выделяется видимый объем пространства с координатами по каждой оси в интервале [-1, 1]. При таких настройках координаты вершин примитивов задаются в этих диапазонах, т.е. относительными значениями. Процесс визуализации включает преобразование координат вершин примитивов к области вывода. Для этого они умножаются на текущую матрицу преобразования. Чтобы в качестве текущей задать матрицу ортогонального проецирования задается следующая последовательность команд // Режим, задающий текущей матрицу проекции glMatrixMode(GL_PROJECTION); // Единичная текущая матрица glLoadIdentity(); // Ортогональное проецирование gluOrtho2D(-1.0, 1.0, -1.0, 1.0); 69 Ниже в качестве примера приведен текст небольшой программы, написанной с использованием библиотеки GLUT. Приведен текст файла FormTao1.cs using using using using using using using using using System; System.Collections.Generic; System.ComponentModel; System.Data; System.Drawing; System.Linq; System.Text; System.Threading.Tasks; System.Windows.Forms; using Tao.OpenGl; // для работы с библиотекой OpenGL using Tao.FreeGlut; // для работы с библиотекой FreeGLUT // для работы с элементом управления SimpleOpenGLControl using Tao.Platform.Windows; namespace FirstTao { public partial class FormTao1 : Form { public FormTao1() { InitializeComponent(); GlControl.InitializeContexts(); } private void FormTao1_Load(object sender, EventArgs e) { // инициализация Glut Glut.glutInit(); // Glut.glutInitDisplayMode(Glut.GLUT_RGB); // установка порта вывода по размерам элемента GlControl Gl.glViewport(0, 0, GlControl.Width, GlControl.Height); // очиcтка окна Gl.glClearColor(1, 1, 1, 0); // белый // параметр задает формат кодирования цвета пикселей Gl.glClear(Gl.GL_COLOR_BUFFER_BIT); // настройка проекции Gl.glMatrixMode(Gl.GL_PROJECTION); // Единичная текущая матрица Gl.glLoadIdentity(); // Ортогональное проецирование 70 Glu.gluOrtho2D(-1.0, 1.0, -1.0, 1.0); Gl.glColor3f(1, 0, 0); // красный // многоугольник Gl.glBegin(Gl.GL_LINE_LOOP); Gl.glVertex2d(-0.6, -0.6); Gl.glVertex2d(0.6, 0.7); Gl.glVertex2d(0.2, -0.6); Gl.glEnd(); // // Gl.glFlush(); GlControl.Invalidate(); // } } } В данной программе не все параметры заданы явно. Некоторые из них устанавливаются значениями по умолчанию при запуске программы. 71 3. ТРЕХМЕРНАЯ КОМПЬЮТЕРНАЯ ГРАФИКА 3.1. ТРЕХМЕРНЫЕ ПРИМИТИВЫ Предметом трехмерной компьютерной графики являются различные пространственные объекты. По геометрическим свойствам их можно разделить на следующие виды:  точки в пространстве;  пространственные линии и отрезки линий;  поверхности;  многогранники;  геометрические тела сложной формы. Для синтеза реалистичных изображений кроме геометрии объектов необходимо также моделировать распространение света, что заставляет задавать и использовать ряд физических свойств объектов и всей пространственной сцены. К ним относятся расположение и яркость источников света, цвета и степень зеркальности (гладкости) поверхностей объектов, коэффициенты преломления света на границах прозрачных сред, степень их прозрачности и др. Ниже в качестве примитивов будут рассмотрены точки, линии, поверхности и многогранники. Tочка P в пространстве задается своими координатами (x, y, z). В трехмерной компьютерной графике традиционно используют левостороннюю систему координат, показанную на рис. 3.1. Причем изображение строится на плоскости OXY, называемой картинной плоскостью. На нее проецируются изображаемые объекты. На рис. 3.1 Pr(P) означает проекцию точки P на картинную плоскость. Часть этой плоскости, соответствующая экрану монитора, обозначена как Scr. 72 Для задания линий в пространстве используется алгебраическая и параметрическая формы. В алгебраической форме линия в пространстве задается как пересечение двух поверхностей, что представляется в виде системы алгебраических уравнений Y P Scr Pr(P) Z X Рис. 3.1  F1 ( x, y, z )  0;   F2 ( x, y, z )  0. (3.1) Пространственные кривые в параметрической форме отличаются от плоских, рассмотренных в п. 2.3, 2.4, лишь тем, что изменение координаты z задается третьей функция z(t): P(t )  x(t ) y(t ) z (t ) . (3.2) Формулы и выводы, приведенные в п. 2.3, 2.4, несложно модифицировать для описания кубических сплайнов и кривых Безье в пространстве. Поверхности, как и линии, задаются в алгебраической и параметрической формах. Алгебраическая поверхность описывается уравнением вида F(x, y, z) = 0. Например, уравнение сферической поверхности с центром в начале координат и радиусом R имеет вид x2 + y2 + z2 – R2 = 0. (3.3) В параметрической форме задаются четырехугольные куски S(u,v) произвольных гладких поверхностей (рис. 3.2). Закон изменения каждой из координат поверхности должен быть описан своей функцией от двух параметров u и v: 73 S (u, v)  x(u, v) y(u, v) z (u, v). (3.4) Как и для параметрических кривых, в качестве области изменения параметров u и v обычно используют интервал [0, 1], т.е. 0  u  1, 0  v  1. S(1, 1) S(1, 0) S(0, 1) u v S(0, 0) Рис. 3.2 При интерактивном синтезе параметрических поверхностей для функций x(u, v), y(u, v) и z(u, v) используют те же полиномиальные базисы, что и в двумерной графике. Разработаны математическая теория и алгоритмы для создания полиномиальных кубических поверхностей, поверхностей Безье и других видов полиномиальных сплайн-поверхностей [3, 5]. В то же время для задания некоторых видов поверхностей удобнее использовать другие базисы. Так, особым классом поверхностей являются поверхности вращения [5]. Поверхностью вращения называется поверхность, образованная вращением плоской кривой вокруг неподвижной оси, лежащей в одной плоскости с кривой. Например, функция S (u, v)  x(u) cos v x(u) sin v z(u), u  0, 1, v  0, 2  (3.5) определяет поверхность, описанную вращением кривой P(u) = [x(u) z(u)], заданной в плоскости OXZ, вокруг оси OZ (рис. 3.3). 74 Другим примером поверхности вращения может служить сферическая поверхность радиусом R с центром в начале координат, описываемая следующим образом: S (u, v)  R sin u cos v R sin u sin v R cos u, u, v  0, 2 . (3.6) Y Z P(u) = S(u,0) X Рис. 3.3 Отметим, что параметры u и v определяют на поверхности географическую систему координат, в которой u является долготой, а v – широтой. Полюса этой сферы расположены на оси OZ. 3.2. АППРОКСИМАЦИЯ КРИВОЛИНЕЙНЫХ ПОВЕРХНОСТЕЙ Представление криволинейной поверхности в параметрической форме S(u, v) позволяет визуализировать ее с любой точностью и детальностью. Однако прямые вычисления значений функций x(u, v), y(u, v) и z(u, v) в общем случае весьма трудоемки, поэтому при разработке быстрых алгоритмов визуализации параметрические поверхности предварительно подвергают полигональной аппроксимации, т.е. криволинейную поверхность заменяют многогранной поверхностью из плоских многоугольников. Общепринято аппроксимировать криволинейные по- 75 верхности плоскими треугольниками. На рис. 3.4 показан результат такой аппроксимации для поверхности, изображенной на рис. 3.2. S(1, 1) S(1, 0) S(0, 1) u v S(0, 0) Рис. 3.4 Основная процедура аппроксимации состоит в расчете узловых точек поверхности S(u, v), т.е. точек, которые будут использоваться в качестве вершин аппроксимирующих треугольников. Для этого выполняют табуляцию S(u, v) по обоим параметрам u и v. Шаги табуляции u и v чаще выбирают постоянными. В итоге заполняется двумерный массив V координат узловых точек. Элемент V[i, j] массива – это координаты (x, y, z) точки поверхности S(u, v), вычисленные для значений параметров u = i u и v = j v. Модель криволинейной поверхности в форме массива V, получившаяся в результате линейной аппроксимации, называется полигональной [8]. В дальнейшем при формировании изображения рассматривается множество примыкающих к друг другу треугольников, вершины, которых хранятся в массиве V. 3.3. МНОГОГРАННИКИ И СЛОЖНЫЕ ОБЪЕКТЫ Кусок параметрической поверхности S(u, v) может быть замкнутым. Примером может служить сфера. После аппроксимации замкнутой поверхности получится поверхность, ограничивающая геометри76 ческое тело в виде многогранника. Многогранники часто выделяются в самостоятельный вид трехмерных примитивов. Произвольный многогранник Mg, ограниченный n гранями, описывается списком граней, т.е. плоских многоугольников: Mg = (G1, G2, …, Gn). (3.7) Каждая грань Gi в свою очередь задается упорядоченным списком вершин: Gi = (Pi1, Pi2, …, Pim). (3.8) Частным случаем многогранников являются правильные многогранники, т.е. многогранники с одинаковыми гранями в виде правильных многоугольников [4]. Примером правильных многогранников является гексаэдр, обычно называемый кубом (рис. 3.5). Его геометрия задается одним параметром – длиной ребра. Правильные многогранники вписываются в сферическую поверхность. Характеризуются количеством n граней и числом m сторон граней. Всего существует лишь пять видов правильных многогранников, называемых также Платоновыми телами: тетраэдр (n = 4, m = 3), гексаэдр (n = 6, m = 4), октаэдр (n = 8, m = 3), икосаэдр (n = 20, m = 3), додекаэдр (n = 12, m = 5). Для описания правильного многогранника достаточно задать координаты (xc, yc, zc) центра и радиус R описанной сферической поверхности, а также значения m и n. Для каждого вида правильных многогранников существуют свои алгоритмы расчета координат вершин по этим данным [4]. Математическое описание и визуализация трехмерных объектов сложной формы, поверхность S которых состоит из граней в виде кусков алгебраических или параметрических поверхностей, представляет определенную проблему. На рис. 3.6 приведен пример сложного объекта с плоскими гранями и обозначены его видимые грани. 77 G1 G2 G3 G4 G5 Рис. 3.5 Рис. 3.6 Очевидным подходом к описанию сложного геометрического объекта по аналогии с многогранниками является представление его поверхности списком граней S = (G1, G2, …, Gm). Описание каждой грани Gi в свою очередь должно включать описание поверхности, частью которой является грань, и описание граничного контура, т.е. отрезков всех линий пересечения данной грани со смежными гранями. Однако независимое конструирование граней для сборки их в одну поверхность с гарантией их точного сопряжения трудно реализовать практически, что и ограничивает применение этого подхода. Как и в двумерной графике, для конструирования сложных пространственных объектов из примитивов можно использовать теоретико-множественные операции (ТМО). Однако программная реализация пространственных ТМО по сравнению с двумерными значительно сложнее. Единственной операцией, которая реализуется естественным образом без дополнительных расчетов, является объединение геометрических тел, поэтому при разработке недорогих графических систем часто выбирают компромиссное решение, когда сложные объекты собираются путем объединения заготовок более простых форм. Заготовки фактически являются расширением набора примитивов формами, характерными для конкретной прикладной области. Например, типичными заготовками для машиностроительных систем автоматизированного проектирования (САПР) являются цилиндры, конусы, параллелепипеды, шестигранники, пирамиды и т.п. 78 3.4. СВЕТ И ЦВЕТ Для трехмерной компьютерной графики основополагающими являются понятия света и цвета. Свет – это электромагнитное излучение, воспринимаемое человеческим зрением. Видимый свет занимает участок спектра электромагнитного излучения с длинами волн от 400 до 700 нм. Свет излучается источниками света и характеризуется яркостью и цветом. Свет одной длины волны имеет определенный цвет и называется монохроматическим. Обычно источник света излучает поток световых волн с разными длинами и амплитудами. В белом свете присутствуют световые волны всего видимого спектра. В остальных случаях свет имеет цвет, определяемый доминирующими длинами волн в световом потоке. Для правильного понимания физической сущности природы света кратко рассмотрим основные светотехнические величины и единицы измерения [1]. Световой поток F характеризует мощность светового излучения, проходящего на элемент поверхности площадью S , освещаемый источником света. Измеряется в люменах (лм). Полный световой поток Fc равен мощности светового излучения сквозь произвольную замкнутую поверхность, охватывающую источник света. В общем случае источник света излучает его неравномерно по разным направлениям. Плотность светового потока в телесном угле выбранного направления называется силой света. Она находится как I dF , d (3.9) где  – телесный угол с центром в источнике света. Для точечного источника света, излучающего свет равномерно по всем направлениям, сила света находится как I Fс . 4 79 (3.10) Единица измерения силы света называется канделла (кд, [кд] = [лм/ср]). Освещенностью E элемента поверхности называется отношение приходящегося на нее светового потока dF к ее площади dS: E dFс . dS (3.11) Единица измерения освещенности называется люкс (лк, [лк] = [лм/м2]). Яркостью B источника называется поверхностная плотность силы света в заданном направлении. Яркость находится как отношение силы света к площади проекции светящейся поверхности на плоскость, перпендикулярную к этому направлению: B dI , dS (3.12) где dS – площадь проекции элемента светящейся поверхности. Яркость измеряется в единицах кд/м2. В компьютерной графике наиболее популярной моделью представления света является аддитивная модель, сокращенно обозначаемая как RGB [3]. В аддитивной модели считается, что любой свет образуется за счет смешения трех основных цветовых составляющих – красной (red), зеленой (green)и синей (blue). Отметим, что смешение света трех основных цветов используется и при формировании изображения на экране мониторов. При использовании RGB модели обозначать яркость источника света, как и в физике, буквой B неудобно, поскольку она же используется для обозначения синего цвета, поэтому, как и в большинстве публикаций по компьютерной графике, для обозначения яркости в дальнейшем будем использовать букву E. Тогда в аддитивной модели источник света будет характеризоваться цветовыми составляющими – красной ER , зеленой EG и синей EB. Яркость источника белого света 80 можно задавать одной величиной E. При этом считается, что яркости всех трех цветовых компонент белого света равны друг другу. Основными видами идеализированных источников света являются точечный и бесконечно удаленный. Точечный источник света помимо цветовых компонент яркости характеризуется еще координатами (xe, ye, ze) его расположения. В этом случае для всякой точки (x, y, z) освещаемой поверхности направление излучаемого света определяется координатами источника и этой точки. Бесконечно удаленный источник света излучает параллельные лучи света, направление которых всюду определяется вектором Ve = (vxe, vye, vze). Еще одно отличие компьютерной графики от физики состоит в том, что яркость моделируемых источников света, как правило, задается не в физических, а в относительных единицах. Обычно используется ограниченный диапазон целых чисел, например 0..255, используемый при кодировании компонент цвета в RGB модели. Зрение основано на том, что свет от источников освещает поверхности предметов, которые частично отражают его. Часть отраженного света попадает в глаз, что позволяет сформировать представление о геометрии предметов и цвете их поверхностей. Этот же принцип используется в фото– и видеоаппаратуре, а также при машинном синтезе изображений виртуальных сцен, поэтому для компьютерной графики наиболее важной физической характеристикой поверхности является ее цвет, который характеризует отражательную способность поверхности в разных областях спектра белого света. В цветовой модели RGB цвет поверхности также задается цветовыми компонентами R, G и B, но, в отличие от света, значения R, G и B характеризуют отражательную способность поверхности соответственно для красной, зеленой и синей составляющих света. В компьютерных программах значения R, G и B для вычислений удобнее задавать в диапазоне от 0 до 1 или в процентах. Кроме RGB используются и иные цветовые модели с другими методами образования цветов из фиксированного набора основных. Так, в 81 субтрактивной модели CMY тоже используются три основных цвета – голубой (cyan), пурпурный (magenta) и желтый (yellow) [1, 3]. Эти цвета считаются дополнительными соответственно к красному, зеленому и синему цветам модели RGB, т.е. могут быть получены вычитанием из белого соответственно красного, зеленого и синего цветов. Модель CMY первоначально использовалась в полиграфии при печати цветных изображений на белой бумаге, поскольку она хорошо отражает получение новых цветов при смешивании красок. Модификацией CMY является расширенная субтрактивная модель, обозначаемая как CMYK. В этой модели используется еще один цвет – черный, а буква K в обозначении соответствует последней букве в слове black – черный. Добавление черного цвета связано с тем, что смешиванием красок трех дополнительных цветов трудно добиться чисто черного цвета. Существуют соотношения, позволяющие преобразовывать CMYK-модель в RGB и наоборот [1]. 3.5. ДИФФУЗНАЯ МОДЕЛЬ РАСПРОСТРАНЕНИЯ СВЕТА Диффузная модель распространения света [2, 5] является одной из наиболее простых. В ней поверхности тел рассматриваются как идеальные рассеиватели света, отражающие падающий на них свет равномерно по всем направлениY ям. Тогда согласно закону ЛамN берта (закон косинусов) яркость L света, отражаемого в направлении плоскости проекции (в P направлении наблюдателя), проS Z порциональна косинусу угла между нормальным вектором N к поверхности и вектором L X направления на источник света Рис. 3.7 (рис. 3.7). 82 Для более детального знакомства с диффузной моделью рассмотрим элемент произвольной поверхности S, которая освещается источником света с яркостью цветовых составляющих ER, EG и EB. Если рассматривается бесконечно удаленный источник света, то L = – Ve. При точечном источнике вектор L для каждой точки P поверхности S приходится рассчитывать через координаты этой точки и координаты источника. Косинус угла между векторами N и L можно найти как скалярное произведение этих векторов после приведения их к единичной длине (нормирования). Нормальный вектор N к поверхности, заданной уравнением F(x, y, z) = 0, находится с помощью частных производных:  F F F  N  ( nx , n y , nz )   , , .  x y z  (3.13) Выполним его нормирование: N '  (nx' , n'y , nz' )  (nx d , n y d , nz d ). (3.14) Здесь d – евклидова норма (длина) вектора N, которая находится следующим образом: d  nx  n y  nz . 2 2 2 (3.15) Будем считать, что вектор L уже нормирован. Скалярное произведение векторов N' и L обозначается как (N'∙ L) и вычисляется по формуле ( N 'L)  n' x lx  n' y l y  n' z lz . 83 (3.16) В итоге для диффузной модели цветовые компоненты света, отраженного в направлении плоскости проекции (наблюдателя), рассчитываются следующим образом: I R  ER R( N 'L)  E0 R; (3.17) I G  EG G( N 'L)  E0 G; (3.18) I B  E B B( N 'L)  E0 B. (3.19) Переменная E0 в формулах (3.17) – (3.19) обозначает яркость рассеянного белого света. В данной модели она упрощенно учитывает тот факт, что в реальной действительности кроме направленных лучей света, падающих от источников, всегда присутствует свет, равномерно рассеянный по разным направлениям. Рассеяние света происходит как в среде распространения света (обычно в воздухе), так и за счет многократного отражения света от поверхностей окружающих предметов. Составляющая E0 позволяет регулировать контрастность формируемого изображения. В приведенных формулах считается, что яркость E света источника всюду постоянна, что справедливо лишь для бесконечно удаленных источников. Если же используется точечный источник, расположенный на конечном расстоянии от рассматриваемой сцены, то необходимо учитывать, что реальная яркость Ere света снижается с увеличением расстояния d от источника до элемента поверхности. Эта зависимость имеет следующий вид: Ere = E / (d + c), (3.20) где c – постоянная, задаваемая опытным путем. Формула применима как для белого, так и для компонент цветного света. Следует отметить, что при разработке программ значения E, ER, EG, EB, E0 можно задавать как реальные физические величины в соответствующих единицах измерения яркости, но при выводе изображения 84 вычисленные величины IR, IG, IB должны быть приведены путем нормирования к диапазону значений в используемой цветовой палитре компьютера. В силу сказанного в программах трехмерной графики яркости источников и рассеянного света чаще задают в условных единицах. 3.6. ЗЕРКАЛЬНОЕ ОТРАЖЕНИЕ СВЕТА В диффузной модели предполагалось, что свет, падающий от источников на поверхности объектов, отражается равномерно по всем направлениям, в том числе и в направлении плоскости проекций. Эта модель хорошо соответствует освещению реальных объектов с матовой поверхностью, однако поверхности многих предметов, особенно металлических, обладают ярко выраженными зеркальными свойствами. Для них наибольшая доля света рассеивается от поверхности в соответствии с законом зеркального отражения: угол падения равен углу отражения (рис. 3.8). Модели распространения света, учитывающие зеркальные свойства поверхностей, называются рефлексными [8]. Z L Θ N Θ V Vr β X Рис. 3.8 На рис. 3.8 L – вектор направления на источник света; N – нормальный вектор к поверхности. 85 Яркость света, отраженного в направлении V плоскости проекции, зависит от величины угла β между вектором Vr направления зеркального отражения и вектором V. Эта зависимость различна для разных материалов и гладкости их поверхности. Для реальных материалов она определяется экспериментально. При машинном же синтезе изображений виртуальных объектов для качественного моделирования зеркальности чаще используют эмпирические модели. Так, в рефлексной модели, предложенной Фонгом [1, 5], интенсивность света, отраженного в направлении вектора V, считается пропорциональной величине сosn α, где n – коэффициент зеркальности. На практике значение n выбирают в диапазоне 1 – 200. Если векторы Vr и V уже нормированы, то сos α можно рассчитать как скалярное произведение этих векторов, т.е. cos   (Vr  V ) . Тогда формулы для расчета значений цветовых компонент света, отраженного в направлении плоскости проекции (наблюдателя), примут следующий вид: I R  ER R( N 'L)  ER R(Vr  V )n  E0 R; (3.21) I G  EG G( N 'L)  EG G(Vr  V ) n  E0 G; (3.22) I B  EB B( N 'L)  EB B(Vr  V ) n  E0 B. (3.23) Формулы (3.21) – (3.23) отражают обе модели распространения света – диффузную и рефлексную. 4.7. ТРЕХМЕРНЫЕ ГЕОМЕТРИЧЕСКИЕ ПРЕОБРАЗОВАНИЯ Так же, как и в двумерной графике, при интерактивной работе с трехмерными объектами над ними приходится производить различные геометрические преобразования. Трехмерные линейные преобразования в однородных координатах отличаются от двумерных только числом координат и размерностью матриц преобразования, равной 4 x 4. 86 В общем виде линейное трехмерное преобразование с матрицей W в однородных координатах x, y, z, v представляется следующим образом:  w11 w12 w w x' y' z ' v  x y z 1  21 22  w31 w32   w41 w42 w13 w23 w33 w43 w14  w24    C  W . (3.24) w34   w44  Здесь C = [x y z 1] – матрица исходных координат; C’ = [x' y' z' v] – матрица новых координат после преобразования. Важно иметь в виду, что значение координаты v остается равным 1 только в таких преобразованиях, для которых w14, w24, w34 = 0 и w44 = 1. В противном случае для перехода к обычной системе координат необходимо выполнить пересчет: x = x' / v; y = y' / v; z = z' / v. Приведем формулы для основных преобразований в пространстве. Преобразование перемещения 1 0 C'  C   0  mx 1 my 1 mz видов (3.25) геометрических 0 0   C  M. 0  1 (3.26) Здесь mx, my, mz – составляющие перемещения по соответствующим осям. Преобразование масштабирования относительно начала координат 87 sx 0 C' C   0  0 sy 0 0   C  S. 0  1 sz (3.27) Здесь sx, sy, sz – масштабные коэффициенты по соответствующим осям. Ограничения на значения масштабных коэффициентов здесь те же, что и для двумерного случая. Преобразование поворота относительно оси OX на угол φ 1 0 cos  C'  C   0  sin   0 sin  cos  0 0   C  Rx . 0  1 (3.28) Преобразование поворота относительно оси OY на угол φ  cos   0 C'  C    sin    0 0 sin  1 0 cos  0 0   C  Ry . 0  1 (3.29) Преобразование поворота относительно оси OZ на угол φ  cos   sin  C'  C    0   0 sin  cos  1 0 0   C  Rz . 0  1 (3.30) Стоит отметить, что формула (3.5) в п. 3.1 для поверхности вращения получена путем применения преобразования вращения вокруг оси OZ к кривой, заданной параметрической функцией P(u). 88 Для выполнения трехмерных преобразований относительно заданного центра сначала его следует совместить с началом координат, затем выполнить заданное преобразование относительно начала координат, а после этого сместить объект и центр в исходное положение. 4.8. ПРОЕЦИРОВАНИЕ ТРЕХМЕРНЫХ ОБЪЕКТОВ Целью визуализации является синтез изображения в виде проекции объектов пространственной сцены, поэтому проецирование является важным этапом процесса визуализации. Это преобразование каждой точке P поверхности ставит в соответствие ее проекцию, т.е. точку Pr(P) на плоскости проекций. Обычно используют один из двух следующих видов проецирования – параллельное или центральное (перспективное). При параллельном проецировании все линии проецирования параллельны между собой. Наиболее простым частным вариантом параллельного проецирования является ортогональное проецирование (рис. 3.9), в котором линии проецирования перпендикулярны плоскости проекций. P Y Z Pr(P) X Рис. 3.9 89 В системе однородных координат ортогональное проецирование на плоскость OXY представляется как преобразование координат C = [x y z 1] с вырожденной матрицей преобразования: 1 0 C' C   0  0 1 0 0   x 0  1 y 0 1 . (3.31) Практически же, как это следует из (3.31), для получения координат C' точек Pr(P) проекции в данном случае достаточно отбросить координаты z проецируемых точек P. Ортогональное проецирование широко используется в САПР при построении чертежей и изображений машиностроительных изделий и их деталей. Центральное проецирование применяется при синтезе изображений пространственных сцен большой протяженности. В этом виде проецирования учитывается то, что в реальном мире видимые размеры объектов уменьшаются при удалении от наблюдателя пропорционально расстоянию (рис. 3. 10). P Y Z Pr(P ) ) Pc X Рис. 3.10 90 Центральное проецирование состоит из двух преобразований – перспективного преобразования и преобразования ортогонального проецирования. На рис. 3.10 показаны результат перспективного преобразования параллелепипеда с точкой P и последующее ортогональное проецирование его на плоскость OXY. Перспективное преобразование приводит к фактическому сокращению размеров объектов с удалением их от наблюдателя. В однородных координатах перспективное преобразование с осью проецирования OZ представляется следующим образом: 1 0 C' C   0  0 1 1 0 0   x k  1 y z 1  k z. (3.32) Коэффициент k называется коэффициентом перспективы. Он определяет степень сокращения видимых размеров в зависимости от удаления. Геометрически коэффициент k определяет положение точки схода Pc на оси OZ, в которой в результате преобразования сходятся все линии, располагавшиеся параллельно оси OZ. В данном случае перевод однородных координат в обычные требует деления на значение координаты v. В итоге обычными координатами точки P' будут (x/(k z + 1), y/(k z + 1), z/(k z + 1)). Чтобы определить координаты точки схода, вычислим пределы: x  0; lim k z  1 z (3.33) y  0; lim k z  1 z (3.34) z  1/ k . lim k z  1 z (3.35) 91 Таким образом, для преобразования (3.32) Pc = (0, 0, 1/ k). Если требуется построить центральную проекцию с точкой схода, координаты xc и yc которой отличны от нуля (например, должны соответствовать центру области вывода), то используют тот же прием, что и при выполнении геометрических преобразований относительно заданного центра. В данном случае сначала необходимо выполнить преобразование смещения по x и y на -xc и -yc соответственно, затем перспективное преобразование, а в заключение – обратное преобразование смещения. Преобразование ортогонального проецирования после перспективного необходимо для получения проекций объектов на картинную плоскость. Поскольку перспективное преобразование искажает размеры и ориентацию в пространстве элементов поверхностей, то для правильного моделирования распространения света фотометрические расчеты следует производить до перспективного преобразования, а удаление невидимых точек поверхностей должно выполняться после перспективного преобразования. На практике это может значительно усложнить расчеты, поэтому чтобы не исказить фотометрические расчеты, часто перспективное преобразование применяют и к источникам освещения. Такой прием позволяет совместить удаление невидимых точек и фотометрические расчеты в одном этапе обработки. Более подробный материал по видам проецирования и их свойствам можно найти в [4, 5]. 3.9. ОРИЕНТАЦИЯ И ПОТЕНЦИАЛЬНАЯ ВИДИМОСТЬ ПОВЕРХНОСТЕЙ При машинном формировании изображения геометрического тела необходимо различать между собой внутреннюю, т.е. обращенную в сторону внутренних точек тела, и внешнюю стороны его поверхности. Очевидно, что на изображении должны быть видимы только внешние стороны поверхностей. 92 Формально стороны поверхности можно различать по направлению нормального вектора к ней. Для определенности примем правило, согласно которому внешней стороной поверхности геометрического тела будет считаться та, со стороны которой располагаются нормальные векторы к поверхности, рассчитанные аналитически. Выше уже говорилось, что для поверхности с уравнением F(x, y, z) = 0 нормальный вектор в любой ее точке  F F F  находится как N  (nx , n y , nz )   , , .  x  y  z   Чтобы лучше понять важность принятого правила, рассмотрим следующий пример. Пусть задана сферическая поверхность с уравнением x2 + y2 + z2 – R2 = 0 (рис. 3.11). Из уравнения следует, что нормальный вектор к этой поверхности будет N = (2x, 2y, 2z). Возьмем на поверхности точку с координатами (0, 0, -R). Для нее N = (0, 0, -2R), т.е. нормальный вектор располагается вне шара, ограниченного сферой. Это же справедливо и для всех остальных точек сферы. Следовательно, внешняя сторона рассматриваемой сферы ограничивает шар радиусом R с центром в начале координат. Для той же сферы, но с уравнением -x2 – y2 – z2 + R2 = 0, нормальный вектор находится как N = (-2x, -2y, -2z). В данном случае в соответствии с принятым правилом нормальные векторы к поверхности будут направлены к ее центру (см. рис. 3.11), поэтому поверхность будет границей сплошного бесконечного тела со сферической пустотой. Не все элементы внешней стороны поверхности геометрического тела представляются на проекции, поскольку обычно потенциально видима только часть внешней стороны поверхности. Термин «потенциальная видимость» означает, что точка поверхности будет видима на изображении, если она не загораживается другими поверхностями. Если в отношении ориентации поверхности геометрического тела придерживаться сформулированного выше правила, то тогда всякая точка поверхности тела будет потенциально видима, если нормальный вектор к поверхности в этой точке направлен в сторону плоскости проекции (в сторону наблюдателя) (рис. 3.12). 93 Y Y Z X (0, 0, -R) X x2 + y2 + z2 – R2 = 0 -x2 – y2 – z2 + R2 = 0 x2 + y2 + z2 – R2 = 0 Рис. 3.11 Имея в виду, что при ортогональном проецировании на плоскость OXY линии проецирования параллельны оси 0Z, а сама ось направлена от наблюдателя, условием потенциальной видимости точки (x, y, z) поверхности будет отрицательное значение составляющей nz нормального вектора N, т. е. F ( x, y, z )  0. z (3.36) Y F 0 z V Направление проецирования F 0 z F 0 z Z Рис. 3.12 94 X Нормальный вектор можно найти и к регулярной параметрической поверхности S (u, v)  x(u, v) y(u, v) z(u, v). Для любых заданных u и v он вычисляется как   ( y , z )  ( z , x )  ( x, y )  N  ,  ( u , v )  ( u , v )  ( u , v )   (3.37) где частные производные рассчитываются по формулам ( y, z ) y z z y ( z, x) z x x z ( x, y ) x y y x   ,   ,   . (u, v) u v u v (u, v) u v u v (u, v) u v u v Но, как уже отмечалось выше, при визуализации криволинейные поверхности аппроксимируются плоскими треугольниками, поэтому анализ потенциальной видимости элементов криволинейной поверхности сводится к анализу потенциальной видимости треугольников, на которые она заменяется. Рассмотрим один из треугольников, аппроксимирующих криволинейную поверхность (рис. 3.13). Обозначим его вершины как P1, P2, P3. Уравнение плоскости, проходящей через три точки P1 = (x1, y1, z1), P2 = (x2, y2, z2), P3 = (x3, y3, z3), имеет следующий вид: y1 y2 z1 1 z1 z2 1 x  z2 x1 1 x1 x 2 1 y  x2 y1 1 x1 y 2 1 z  x2 y1 y2 z1 z 2  0. y3 z3 1 x3 1 y3 1 y3 z3 z3 x3 x3 (3.38) Очевидно, что для всей плоскости, включая и треугольник P1 P2 F P3, производная равна коэффициенту при z, т.е. z x1 F  x2 z x3 y1 y2 1 1. y3 1 (3.39) Отсюда в соответствии с (3.32) условием потенциальной видимости треугольника будет следующее: 95 x1 x2 y1 y2 1 1  0. x3 y3 1 (3.40) P2 P3 P1 Рис. 3.13 Порядок расположения координат точек в определителе соответствует обходу вершин треугольника, показанному на рис. 3.13. Если его поменять на противоположный, то это приведет к перестановке строк в определителе и, следовательно, к изменению его знака на противоположный. Следовательно, порядок обхода вершин (по часовой стрелке или против) должен быть единым для всех треугольников. Для криволинейной поверхности он в целом определяет ее внешнюю и внутреннюю стороны. В некоторых случаях необходимо визуализировать поверхности как самостоятельные объекты. Если при этом надо показывать обе стороны поверхности, то понятие потенциальной видимости теряет смысл. 96 3.10. УДАЛЕНИЕ НЕВИДИМЫХ ТОЧЕК ПОВЕРХНОСТЕЙ Анализ потенциальной видимости элементов поверхностей примерно вдвое сокращает объем вычислений при построении изображения. Но эта обработка окончательно не решает проблему удаления невидимых точек поверхностей, т.е. таких, которые заслоняются другими поверхностями. Решению данной задачи посвящено большое число работ [3, 4, 5]. Большинство из приведенных в них алгоритмов ориентировано на построение каркасных изображений геометрических тел, т.е. видимых частей сторон аппроксимирующих треугольников. При построении закрашенных полутоновых изображений геометрических тел задачу о конкурировании приходится решать для каждой потенциально видимой точки поверхности. Универсальным решением, нашедшим преимущественное применение в системах полутоновой трехмерной графики, является метод Z-буфера [5]. Суть метода Z-буфера очень проста и сводится к следующему. Аналогично видеопамяти аппаратно или программно создается буфер памяти для хранения координат z видимых на текущий момент точек поверхностей (рис. 3.14). В Z-буфере используется такая же координатная организация обращения к его элементам по координатам X и Y, как и в видеопамяти, т.е. каждому пикселю области вывода в Zбуфере соответствует элемент, определяемый его координатами. Желательно, особенно если возможен синтез перспективных изображений, чтобы элементы Z-буфера были вещественного типа. Перед началом построения изображения Z-буфер заполняется максимально возможными значениями, соответствующими бесконечно удаленным по z точкам. Далее в процессе построения изображения, прежде чем рассчитать код цвета очередной точки поверхности при заданных координатах X и Y, рассчитывается ее координата z. Если z < Z[Y, X], то это значит, что на текущий момент данная точка ближе других конкурирующих точек к плоскости проекции. Тогда в соответствии с выбранной моделью распространения света 97 необходимо рассчитать код цвета, соответствующего этой точке пикселя, и записать его в видеопамять, а координату z записать в Z-буфер. Иначе точка закрывается другой, ранее рассчитанной, которая расположена ближе к плоскости проекции или на таком же расстоянии. В этом случае рассматриваемая точка исключается из дальнейшей обработки. X Z [x, y] Y Рис. 3.14 Благодаря Z-буферу при завершении обработки всех поверхностей независимо от их числа в области вывода будут изображены только видимые элементы поверхностей. Достоинство метода Z-буфера – его универсальность. Метод можно использовать в программах независимо от способов задания поверхностей и алгоритмов их обработки. В отличие от большинства других алгоритмов удаления невидимых точек, в которых время, затрачиваемое на удаление, с увеличением сложности сцены растет нелинейно в степени, большей 1, здесь оно пропорционально общей площади проекций всех потенциально видимых элементов поверхности сцены, что также можно отнести к достоинствам метода Z-буфера. Во многих видеоадаптерах современных персональных компьютеров для лучшей поддержки компьютерных игр метод Z-буфера реализуется аппаратно. 98 3.11. МЕТОД ВИЗУАЛЬНОГО СГЛАЖИВАНИЯ ГУРО Наиболее существенным недостатком полигональной аппроксимации криволинейных поверхностей является то, что если не принимать специальных мер, на изображении явно видны границы треугольников, которыми заменяются поверхности. Это связано с тем, что в пределах всякого плоского треугольника нормальный вектор остается неизменным, а потому одинаковыми будут цвет и яркость всех точек треугольника. В результате на границах сопряжения смежных треугольников возникает скачкообразное изменение яркости, что очень остро улавливается зрением. На рис. 3.15, поясняющем проблему, показано сечение фрагмента аппроксимированной криволинейной поверхности плоскостью Y = const. Поверхность освещается бесконечно удаленным источником света, направление которого задается вектором Ve. Здесь N1, N2, N3, N4 – нормальные векторы к треугольникам, попавшим в рассматриваемое сечение. Z Y = const N4 N1 N2 N3 I(x) Ve I I2(x) X Рис. 3.15 График I(x) демонстрирует скачкообразное изменение яркости изображения на границах смежных треугольников. 99 Для подавления рассмотренного недостатка Гуро [5] предложил метод визуального сглаживания яркости при построении изображений аппроксимированных криволинейных поверхностей. Суть метода состоит в том, что в каждой узловой точке поверхности, где сопрягаются несколько смежных треугольников, расчетным путем на основании нормальных векторов этих треугольников находится усредненный нормальный вектор Ns. В зависимости от расположения в узловой точке могут сопрягаться от одного до шести треугольников (рис. 3.16), поэтому n N s   N i , n  1,2,3,6. (3.41) i 1 Здесь имеется в виду векторное суммирование, причем перед усреднением векторы Ni путем нормирования должны быть приведены к единичной длине. N6 Ns N5 N1 N2 N4 N3 Рис. 3.16 В результате этих предварительных расчетов для всех узлов полигональной сетки, являющихся также вершинами треугольников, будут определены свои нормальные векторы, причем в вершинах каждого треугольника все три нормальных вектора в общем случае будут различными. Для того, чтобы затем выполнить фотометрические расчеты, нормальные векторы Ns в узловых точках также следует пронормировать. 100 Используя усредненные нормальные векторы, рассчитывают цветовые составляющие в узловых точках. В итоге для каждого аппроксимирующего треугольника будем иметь цветовые составляющие IR1, IG1, IB1, IR2, IG2, IB2, IR3, IG3, IB3 его вершин (рис. 3.17). (x1, y1) 1 Y IR1, IG1, IB1 x31, IR31 x12, IR12 (x3, y3) 3 IR3, IG3, IB3 2 (x2, y2) IR2, IG2, IB2 X Рис. 3.17 Цвет остальных точек проекции треугольника рассчитывают с помощью билинейной интерполяции между вершинами. Для этого сначала производят линейную интерполяцию компонент IR, IG, IB по Y вдоль сторон треугольника. В зависимости от строки Y значение яркости цветовой компоненты IR по стороне 1-2 будет меняться следующим образом: I R12  I R1  I R 2  I R1 (Y  y1 ) . y2  y1 (3.42) Формулы для расчета цветовых компонент IG12 и IB12 аналогичны. Для двух других сторон, если они пересекаются строкой Y, таким же образом рассчитывают IR23, IG23, IB23 и IR31, IG31, IB31. Далее для расчета текущих значений цветовых компонент в пределах каждой строки Y также используют линейную интерполяцию, но уже по x. Например, в строке Y между сторонами 101 1-2 и 3-1 красная составляющая будет меняться по x следующим образом: I R  I R 31  I R12  I R 31 ( x  x31 ) . x12  x31 (3.43) Формулы для расчета цветовых компонент IG и IB аналогичны. Поскольку смежные треугольники в общих вершинах имеют одни и те же нормальные векторы, то при переходе от одного треугольника к другому яркость точек будет меняться без скачков. Как видно из рис. 3.15, метод визуального сглаживания Гуро изменяет ступенчатый характер первоначальной зависимости I(x) на непрерывный, в виде ломаной линии I2(x). 3.12. МЕТОД ВИЗУАЛЬНОГО СГЛАЖИВАНИЯ ФОНГА Более качественное, чем в модели Гуро, визуальное сглаживание было предложено Фонгом [5]. Сначала в его методе, как и в методе Гуро, рассчитываются усредненные нормальные векторы единичной длины для узловых точек. Затем, в отличие от метода Гуро, на основе усредненных нормальных векторов в вершинах треугольников производится билинейная интерполяция нормальных векторов по поверхности треугольников. Линейная интерполяция нормального вектора вдоль стороны 1-2 (рис. 3.18) по Y выполняется следующим образом: N12  N1  N 2  N1 (Y  y1 ) . y2  y1 (3.44) Интерполяция по другим сторонам треугольника, пересекающимся с текущей строкой Y, производится аналогичным образом. Рассчитываемые значения нормальных векторов для дальнейших расчетов необходимо нормировать. Интерполяция нормального вектора в строке Y между x31 и x12 по x и между нормированными значениями N31 и N12 имеет следующий вид: 102 N12  N 31 ( x  x31 ) . x12  x31 N  N 31  (4.45) Отметим, что в формулах (4.44), (4.45) имеются в виду векторные операции. Y (x1, y1) 1 N1 x31, N31 x12, N12 (x3, y3) 3 N3 2 (x2, y2) N2 X Рис. 3.18 Рассчитанные таким образом нормальные векторы для каждой точки треугольника приводят к единичной длине и далее используют для вычисления цветовых компонент IR, IG, IB пикселя в соответствии с выбранной моделью распространения света. Объем вычислений, приходящихся на закрашивание одной и той же криволинейной поверхности, в методе Фонга больше, чем в методе Гуро, однако и качество визуального сглаживания получается выше. 3.13. СИСТЕМЫ КООРДИНАТ В ПРОСТРАНСТВЕННОЙ СЦЕНЕ Для описания объектов и их частей, а также для представления всей пространственной сцены используются различные системы координат, межу которыми должны быть установлены правила преобразования [1, 3, 7]. Локальное пространство (local space), или пространство моделирования (modeling space), – это пространство с собственной системой 103 координат OXlYlZl, в которой описывается объект (в виде списка треугольных граней). Систему координат этого пространства выбирают независимо от других объектов сцены так, чтобы описание данного объекта было наиболее простым и удобным (рис. 3.19). Свое локальное пространство может иметь каждый объект сцены. Yl Zl Xl Рис. 4.19 Объект, созданный в собственной системе координат, для использования в сцене необходимо нужным образом разместить в едином мировом пространстве (world space) с глобальной (мировой) системой координат OXwYwZw (рис. 3.20). Для размещения в мировой системе каждого объекта нужно использовать преобразование, в общем случае состоящее из перемещения, масштабирования и вращения. Это преобразование принято называть мировым преобразованием (world transformation). Запишем его как Cwi  Cli Wi . (3.46) Здесь Cli – матрица-строка координат i-того объекта в собственной локальной системе координат; Cwi – матрица-строка координат i-того объекта в мировой системе координат; Wi – матрица преобразования из локальной системы координат в мировую. 104 Yw Yc Yl Xc Xl4 камера Yl31 Xl3 Zc Yl2 Yl4 Xl5 Xl1 Yl5 Xl2 Zl1 Zw X w Рис. 3.20 Таким образом, для каждого объекта его мировое преобразование устанавливает взаимосвязь между локальным и мировым пространством. Для наглядности процесса проецирования объектов сцены и формирования изображения используют понятие виртуальной камеры [3]. Виртуальная камера задается в собственной системе координат OXcYcZc. Для формирования изображения камеру следует разместить в определенной точке пространства, сориентировать нужным образом ее по отношению к сцене, а также задать параметры проецирования. Для виртуальной камеры также необходимо задать преобразование Wwc, связывающее мировую систему координат с системой координат камеры OXcYcZc: Cc  Cw Wwc . (3.47) Здесь Cli – матрица-строка координат в мировом пространстве; Cwi – матрица-строка координат в пространстве вида. Данное преобразование называется преобразованием к пространству вида (view space transformation). После него все объекты сцены будут расположены в общем пространстве вида (view space). При этом сцена будет проецироваться на плоскость OXcYc камеры (рис. 3.21). 105 Xc Yc Рис. 4.21 Необходимо отметить, что при проектировании сложных технических изделий число уровней систем координат может быть еще большим, чем рассмотрено в этом параграфе. Пребразование координат к пространству вида в таком случае выполняют последовательно, двигаясь по ступеням иерархии от примитивов ко все более сложным объектам. 3.14. ПОСТРОЕНИЕ ИЗОБРАЖЕНИЯ С ТЕНЯМИ Для большей реалистичности изображения пространственных сцен необходимо учитывать, что некоторые элементы поверхностей не освещены источником света, т.е. находятся в тени и освещаются только рассеянным светом. Существует два вида теней:  собственная тень;  проекционная тень. Собственная тень образуется в том случае, если угол α между нормальным вектором N к рассматриваемому элементу поверхности и вектором L = (lx, ly, lz) направления на источник света становится больше π/2. Из сказанного следует, что признаком образования собственной тени для рассматриваемого треугольника должно быть условие cos α < 0. Рассмотрим треугольный элемент поверхности с вершинами 1, 2, 3 (рис. 3.22). 106 Согласно (3.38) проекции нормального вектора N = (nx, ny, nz) к треугольнику находятся как y1 z1 1 z1 x1 1 x1 y1 1 n x  y 2 z 2 1 , n y  z 2 x 2 1 , n z  x 2 y 2 1. y3 z 3 1 z 3 x3 1 N L x3 (3.48) y3 1 2 α 1 3 Рис. 3.22 Если оба вектора пронормированы (приведены к единичной длине), то cos  ( N  L)  nxlx  nyl y  nz lz , (3.49) а признаком собственной тени треугольного элемента будет условие nxlx  nyl y  nz lz  0 . (3.50) Проекционные тени – это тени, которые образуются на рассматриваемой поверхности другими поверхностями, загораживающими распространение прямых лучей света от источника к данной поверхности. Проекционные тени строятся значительно сложнее. Для этого необходима информация о взаимном расположении элементов поверхностей. Используются два основных подхода к формированию проекционных теней:  прямая трассировка лучей (ray tracing);  обратная трассировка лучей (ray casting). 107 Прямая трассировка основана на прослеживании трасс лучей света от источника света. Для каждой трассы рассчитываются точки ее пересечения с элементами поверхностей, встречающимися на ее пути. После этого точки пересечения сортируются по расстоянию до источника света. Самая близкая к источнику точка будет освещена, а остальные лежат в тени. У данного метода много недостатков. В частности, тестирование трассы может быт безрезультатным, если не будет найдено ни одного пересечения с поверхностями. Этот метод практически не используется из-за большой трудоемкости и низкой эффективности. Обратная трассировка более эффективна в отношении объема вычислений, поэтому рассмотрим ее более подробно. В методе обратной трассировки для каждой визуализируемой точки P поверхности строится трасса лучей от этой точки к источнику света (рис. 3.23). При этом делается проверка пересечения трассы со всеми остальными элементами поверхностей (треугольниками). Если обнаруживается хотя бы одно пересечение, значит рассматриваемая точка находится в тени. Иначе рассматриваемая точка будет освещена источником света. Z P L P* X Рис. 3.23 Пусть задан вектор L = (lx, ly, lz) направления на источник света. Сначала отметим, что если изображение строится с использованием ортогонального проецирования на плоскость OXY и вектор L перпен108 дикулярен плоскости проекции, т.е. L = (0, 0, lz), то проекционные тени отсутствуют. Причем, если lz < 0, то источник освещает невидимые части поверхностей, а видимые будут целиком в тени. Если же lz > 0, то наоборот - видимые элементы поверхностей полностью освещены. Контроль этих ситуаций несложно организовать программно, поэтому далее рассмотрим более общий случай, когда вектор L не перпендикулярен плоскости проекции. Уравнение трассы, проходящей через рассматриваемую точку P = (x0, y0, z0) поверхности в направлении L, имеет вид x  x0 y  y0 z  z0   . lx ly lz (3.51) Для расчета возможных точек пересечения трассы с другими треугольниками для каждого из них нужно использовать уравнение плоскости, содержащей этот треугольник: nx x  n y y  nz z  с  0, (3.52) где (nx, ny, nz) – проекции нормального вектора к анализируемому треугольнику; c – коэффициент, рассчитываемый как и nx, ny, nz, на основании координат вершин треугольника (3.48). Координаты точки T = (xt, yt, zt) пересечения находятся как решение системы уравнений (3.51) и (3.52). Если система не имеет решения, значит плоскость, в которой лежит тестируемый треугольник, параллельна трассе. Такие треугольники не дают тени и поэтому не требуют дальнейшей обработки. В остальных случаях для точки T нужно установить, лежит ли она внутри треугольника или расположена вне его. Для упрощения решения данной задачи вместо самого треугольного элемента поверхности достаточно рассмотреть его ортогональную проекцию либо на плоскость OXY проекции, если nx, ny ≠ 0, либо на другую плоскость системы координат, например на OXZ, в остальных случаях. Проецирование в данном случае сводится к отбрасыва109 нию одной из координат. Далее для конкретности рассмотрим проецирование на плоскость OXY, когда отбрасываются координаты z. Пусть на проекции вершины треугольника обозначены как 1, 2, 3, а проекция точки T обозначена через Q (рис. 3.24). Если точка Q лежит внутри треугольника 123, то отрезками, исходящими из Q к вершинам, треугольник делится на три треугольника 12Q, 23Q и 31Q, площади которых обозначим соответственно как S12, S23 и S31. Y 2 Q' 1 Q 3 X Рис. 3.24 Очевидно, что в этом случае площадь S123 всего треугольника 123 будет равна сумме S12, S23 и S31, т.е. |S12| + |S23| + |S31| = |S123|. (3.53) Если же точка Q лежит вне треугольника 123 (точка Q' на рис. 3.24), то |S12| + |S23| + |S31| > |S123|. (3.54) Площади треугольников на основании координат их вершин можно рассчитать по формуле (2.35), причем, как показано в п. 2.7, знак результата зависит от направления обхода вершин, поэтому в условиях (3.53), (3.54) используются абсолютные величины площадей. 110 Как только будет найдено первое пересечение трассы с очередным тестируемым треугольным элементом поверхности такое, что выполняется условие (3.53), тестирование остальных треугольников прекращается, поскольку уже понятно, что рассматриваемая точка (x0, y0, z0) находится в тени. Ее закрашивание следует рассчитывать без учета освещения от источника света. Если же при тестировании не будет найдено ни одного элемента поверхности, заслоняющего точку (x0, y0, z0) от источника света, то тогда для ее закрашивания нужно учесть и свет источника. Как видно, трассировка лучей весьма трудоемка. Время трассировки без оптимизации пропорционально квадрату числа треугольных элементов сцены. Существуют различные технологии оптимизации. Например, объекты сцены объединяются в группы, которые содержатся в простых геометрических формах вроде сферы. Сначала проверяется, пересекает ли данный луч объемлющую сферу, и только если пересекает, рассматриваются внутренние объекты. Эффективным способом снижения трудоемкости может служить также трассировка с использованием теневого z-буфера. Рассмотрим подробнее суть этого метода. Сначала сцена проецируется на плоскость, перпендикулярную вектору, на источник света. Если рассматривается точечный источник света, то вместо ортогонального проецирования надо использовать центральное проецирование с точкой схода в точке размещения источника. При проецировании изображение не формируется, а заполняется теневой Z-буфер Zt по аналогии с Z-буфером, используемый для удаления невидимых точек поверхностей (рис. 3.25). После окончания теневого проецирования всей сцены выполняется обычная визуализация с использованием обычного Z-буфера для удаления невидимых точек поверхности. При этом, если точка поверхности видима, то ее координаты (x, y, z) пересчитываются в систему координат теневого буфера Zt. Пусть в результате пересчета координаты той же точки будут (x', y', z'). Если z' < Zt[x', y'], значит эта 111 точка загораживается от источника освещения другими поверхностями, т.е. она находится в тени. Для расчета ее цвета используется только рассеянный свет. Если же z' ≥ Zt[x', y'], значит точка освещается источником света и для нее нужен фотометрический расчет с учетом всех составляющих света. Y' Zt Y Z' X Z ' X Рис. 3.25 Существенный недостаток метода трассировки с использованием теневого Z-буфера заключается в том, что его размеры по X' и Y', необходимые для построения всех теней, зависят от размеров всей сцены, а не от размеров той ее части, которая проецируется в область вывода. Другими словами, для сцен большой протяженности может потребоваться чрезвычайно большой теневой буфер, что сделает его использование труднореализуемым или неэффективным. 112 СПИСОК ЛИТЕРАТУРЫ 1. Божко, А.Н. Компьютерная графика / А.Н. Божко, Д.М. Жук, В.Б. Маничев. – М.: МГТУ им. Н. Э. Баумана, 2007. – 392 с. – ISBN 978-5-7038-3015-4 2. Дегтярев В.М. Компьютерная геометрия и графика : учебник для студ. высш. учеб. заведений – М.: Академия, 2010. – 192 с. – ISBN 978-5-76955888-7 3. Сиденко Л.А. Компьютерная графика и геометрическое моделирование. Учебное пособие - СПб: Питер, 2009. – 224 с. - ISBN 978-5-388-00339-3 4. Константинов А. В. Компьютерная графика. Конспект лекций – М.: Феникс, 2006. – 224 с. – ISBN: 5-222-0199615-7 5. Херн, Д., Бейкер, М.П. Компьютерная графика и стандарт OpenGL, 3-е изд.: Пер. с англ.. – М: Изд. дом «Вильямс», 2005. – 1168 с. – ISBN 5-8459-0772-1 6. Пугачев, А.И. Основы компьютерной графики: курс лекций / А.И. Пугачев. – Самара: Самар. гос. техн. ун-т, 2011. – 104 с. http://sourceforge.net/projects/taoframework/files/latest/download Проблема решена!!! Просто при инсталяции Tao Framework [2.1.0] на вашу x64 ОС выбираете директорию установки С:\Program files(x86)\Tao Framework. Затем, что бы запустить ваше OpenGL приложение на Visual Studio 2008 меняете настройки проекта на платформу x86, затем заходите в С:\Program files(x86)\Tao Framework\source\lib\win32deps и копируете все dll в Windows\system32. По итогу всё ровно работает 113 ОГЛАВЛЕНИЕ ВВЕДЕНИЕ ............................................................................................................................................ 2 1. РАСТРОВЫЕ ИЗОБРАЖЕНИЯ И ТЕХНИЧЕСКИЕ СРЕДСТВА ГРАФИЧЕСКИХ СИСТЕМ ................................................................................................................................................ 4 1.1. РАСТРОВЫЕ ИЗОБРАЖЕНИЯ .....................................................................................................................4 1.2. ГРАФИЧЕСКИЕ УСТРОЙСТВА ВВОДА-ВЫВОДА ...........................................................................................7 1.3. ВИДЕОАДАПТЕРЫ ...................................................................................................................................13 2. ДВУМЕРНАЯ КОМПЬЮТЕРНАЯ ГРАФИКА ....................................................................... 16 2.1. ДВУМЕРНЫЕ ПРИМИТИВЫ .......................................................................................................................16 2.2. ВИЗУАЛИЗАЦИЯ НА ДИСКРЕТНОЙ ОБЛАСТИ ВЫВОДА ..............................................................................18 2.3. ВИЗУАЛИЗАЦИЯ ОТРЕЗКОВ ПРЯМЫХ ........................................................................................................21 2.4. КУБИЧЕСКИЕ СПЛАЙНЫ ...........................................................................................................................25 2.5. КРИВЫЕ БЕЗЬЕ .......................................................................................................................................27 2.6. ЗАКРАШИВАНИЕ ОГРАНИЧЕННЫХ ОБЛАСТЕЙ ПЛОСКОСТИ ........................................................................30 2.7. АЛГОРИТМ ЗАКРАШИВАНИЯ ОРИЕНТИРОВАННЫХ МНОГОУГОЛЬНИКОВ ....................................................36 2.8. ТЕОРЕТИКО-МНОЖЕСТВЕННЫЕ ОПЕРАЦИИ НАД ДВУМЕРНЫМИ ОБЛАСТЯМИ ............................................40 2.9. ПОСТРОЧНЫЙ АЛГОРИТМ ТМО ................................................................................................................43 2.10. ДВУМЕРНЫЕ ГЕОМЕТРИЧЕСКИЕ ПРЕОБРАЗОВАНИЯ ...............................................................................46 2.11. СОВМЕЩЕНИЕ ПРЕОБРАЗОВАНИЙ. ПРЕОБРАЗОВАНИЕ ОТНОСИТЕЛЬНО ЗАДАННОГО ЦЕНТРА ................49 2.12. ПРЕОБРАЗОВАНИЕ АЛГЕБРАИЧЕСКИХ ЛИНИЙ.........................................................................................51 2.13. НЕПРЕРЫВНЫЕ ГЕОМЕТРИЧЕСКИЕ ПРЕОБРАЗОВАНИЯ ...........................................................................53 2.14. ЛИНЕЙНЫЕ ПРЕОБРАЗОВАНИЯ ФРАГМЕНТОВ ИЗОБРАЖЕНИЯ .................................................................57 2.15. ГРАФИЧЕСКАЯ БИБЛИОТЕКА OPENGL ...................................................................................................60 2.16. СИНТАКСИС КОМАНД OPENGL. ДВУМЕРНЫЕ ПРИМИТИВЫ ............................................................63 2.17. ВИЗУАЛИЗАЦИЯ ГРАФИКИ OPENGL ..............................................................................................68 3. ТРЕХМЕРНАЯ КОМПЬЮТЕРНАЯ ГРАФИКА ..................................................................... 72 3.1. ТРЕХМЕРНЫЕ ПРИМИТИВЫ ......................................................................................................................72 3.2. АППРОКСИМАЦИЯ КРИВОЛИНЕЙНЫХ ПОВЕРХНОСТЕЙ...............................................................................75 3.3. МНОГОГРАННИКИ И СЛОЖНЫЕ ОБЪЕКТЫ .................................................................................................76 3.4. СВЕТ И ЦВЕТ ...........................................................................................................................................79 3.5. ДИФФУЗНАЯ МОДЕЛЬ РАСПРОСТРАНЕНИЯ СВЕТА.....................................................................................82 3.6. ЗЕРКАЛЬНОЕ ОТРАЖЕНИЕ СВЕТА .............................................................................................................85 4.7. ТРЕХМЕРНЫЕ ГЕОМЕТРИЧЕСКИЕ ПРЕОБРАЗОВАНИЯ ................................................................................86 4.8. ПРОЕЦИРОВАНИЕ ТРЕХМЕРНЫХ ОБЪЕКТОВ .............................................................................................89 3.9. ОРИЕНТАЦИЯ И ПОТЕНЦИАЛЬНАЯ ВИДИМОСТЬ ПОВЕРХНОСТЕЙ ..............................................................92 3.10. УДАЛЕНИЕ НЕВИДИМЫХ ТОЧЕК ПОВЕРХНОСТЕЙ.....................................................................................97 3.11. МЕТОД ВИЗУАЛЬНОГО СГЛАЖИВАНИЯ ГУРО ..........................................................................................99 3.12. МЕТОД ВИЗУАЛЬНОГО СГЛАЖИВАНИЯ ФОНГА .....................................................................................102 3.13. СИСТЕМЫ КООРДИНАТ В ПРОСТРАНСТВЕННОЙ СЦЕНЕ .........................................................................103 3.14. ПОСТРОЕНИЕ ИЗОБРАЖЕНИЯ С ТЕНЯМИ...............................................................................................106 СПИСОК ЛИТЕРАТУРЫ............................................................................................................... 113 ОГЛАВЛЕНИЕ.................................................................................................................................. 114 114 Учебное издание Графические системы компьютеров ПУГАЧЕВ Анатолий Иванович Редактор С.И. Костерина Компьютерная верстка И.О. Миняева Выпускающий редактор Н.В. Беганова Подп. в печать 18.05.13. Формат 60х84 1/16. Бумага офсетная. Усл. п. л. 6,04. Уч.-изд. л. 6,01. Тираж 50 экз. Рег. № 271/10. Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Самарский государственный технический университет» 443100. г. Самара, ул. Молодогвардейская, 244. Главный корпус Отпечатано в типографии Самарского государственного технического университета 443100. г. Самара, ул. Молодогвардейская, 244. Корпус № 8 115