К. В. Рябинин вычислительная геометрия и алгоритмы компьютерной графики
 Скачать 1.44 Mb.
|
|
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ Федеральное государственное бюджетное образовательное учреждение высшего образования «ПЕРМСКИЙ ГОСУДАРСТВЕННЫЙ НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ УНИВЕРСИТЕТ» К. В. РЯБИНИН ВЫЧИСЛИТЕЛЬНАЯ ГЕОМЕТРИЯ И АЛГОРИТМЫ КОМПЬЮТЕРНОЙ ГРАФИКИ РАБОТА С 3D-ГРАФИКОЙ СРЕДСТВАМИ OPENGL Допущено методическим советом Пермского государственного национального исследовательского университета в качестве учебного пособия для студентов, обучающихся по направлению подготовки бакалавров «Прикладная математика и информатика» Пермь 2017 УДК 514+004.92 ББК 22.151+32.973–018.2 Р 98 Р 98 Рябинин К. В. Вычислительная геометрия и алгоритмы компьютерной графики. Работа с 3D-графикой средствами OpenGL: учеб. пособие / К. В. Рябинин; Перм. гос. нац. исслед. ун-т. – Пермь, 2017. – 100 с.: ил. ISBN 978-5-7944-2722-6 Пособие нацелено на изучение студентами основ вычислительной геометрии и компьютерной графики, приобретение практических навыков и компетенций разработки приложений, синтезирующих изображения в ре- альном времени с использованием аппаратного ускорения обработки гра- фики на современных GPU. Излагаемый теоретический материал в равной степени относится ко всем низкоуровневым стандартам вывода графики; практическая часть приводится на примере открытого интерфейса OpenGL. Предназначено для студентов, обучающихся по направлению под- готовки бакалавров «Прикладная математика и информатика», изучающих дисциплину «Вычислительная геометрия и алгоритмы компьютерной гра- фики», а также будет полезно студентам других направлений и специаль- ностей, изучающим основы программного построения изображений сред- ствами ЭВМ и осваивающим современные технологии разработки мульти- медийных информационных систем. Ил. 20. Библиогр. 12 назв. УДК 514+004.92 ББК 22.151+32.973–018.2 Печатается по решению редакционно-издательского совета Пермского государственного национального исследовательского университета Рецензенты: к. т. н., доцент каф. информатики и вычислительной техни- ки Перм. гос. гум.-пед. ун-та И. П. Половина; ГК «ИВС» (рецензенты – к. т. н. И. Ф. Федорищев, директор по инновациям ГК «ИВС» А. Н. Полещук) ISBN 978-5-7944-2722-6 © © Рябинин К. В., 2017 Пермский государственный национальный исследовательский университет, 2017 Оглавление Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1. Формирование изображений в компьютерной графике . . . 8 2. Уровни работы с графикой 11 3. Графический конвейер . . . . . . . . . . . . . . . . . . . . . 14 4. Размещение объектов на сцене и проекция на экран . . . . . 17 4.1. Аффинные преобразования . . . . . . . . . . . . . . . 17 4.2. Углы Эйлера и шарнирный замок . . . . . . . . . . . . 22 4.3. Преобразования проекции . . . . . . . . . . . . . . . . 27 5. Структура графического приложения . . . . . . . . . . . . . 33 5.1. Графический контекст . . . . . . . . . . . . . . . . . . 33 5.2. Обобщённое графическое приложение . . . . . . . . . 34 5.3. Анимация . . . . . . . . . . . . . . . . . . . . . . . . . 36 5.4. Многопоточность графического приложения . . . . . . 37 5.5. Буфер кадра . . . . . . . . . . . . . . . . . . . . . . . . 38 5.6. Первое приложение . . . . . . . . . . . . . . . . . . . 39 6. Шейдеры . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 6.1. Свойства шейдеров 43 6.2. Виды шейдеров . . . . . . . . . . . . . . . . . . . . . . 45 6.3. Язык GLSL . . . . . . . . . . . . . . . . . . . . . . . . 47 6.4. Взаимодействие шейдеров . . . . . . . . . . . . . . . . 52 6.5. Шейдерная программа . . . . . . . . . . . . . . . . . . 55 6.6. Реализация . . . . . . . . . . . . . . . . . . . . . . . . 56 7. Представление объектов сцены . . . . . . . . . . . . . . . . 63 7.1. Полигональная сетка . . . . . . . . . . . . . . . . . . . 63 7.2. Хранение объектов сцены в OpenGL . . . . . . . . . . 64 7.3. Реализация . . . . . . . . . . . . . . . . . . . . . . . . 65 3 8. Визуализация сцены . . . . . . . . . . . . . . . . . . . . . . 72 8.1. Порт просмотра 72 8.2. Вызов отрисовки . . . . . . . . . . . . . . . . . . . . . 73 8.3. Разогрев конвейера . . . . . . . . . . . . . . . . . . . . 76 9. Процедурная закраска . . . . . . . . . . . . . . . . . . . . . 78 10. Обработка объёмных структур . . . . . . . . . . . . . . . . 82 10.1. Буфер глубины . . . . . . . . . . . . . . . . . . . . . 82 10.2. Визуализация трёхмерного объекта . . . . . . . . . . 88 10.3. Анимация преобразований . . . . . . . . . . . . . . . 93 11. Отладка графического приложения . . . . . . . . . . . . . 95 Заключение . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98 Список литературы . . . . . . . . . . . . . . . . . . . . . . . . 99 4 Введение Компьютерная графика как совокупность методов преобра- зования данных в визуальные образы с помощью ЭВМ занимает важное место в сфере современных информационных технологий. Она находит применение в индустрии развлечений (создание игр и специальных эффектов для фильмов), в науке и образовании (визуа- лизация результатов научных экспериментов и создание наглядных пособий), в промышленности (автоматизированное проектирование и прототипирование), в средствах массовой информации (создание рекламных и информационных роликов), в бизнесе (визуализация бизнес-процессов и эконометрических данных) и даже в челове- ческом быту (графические интерфейсы пользователя к различным вычислительным устройствам). Научной основой компьютерной графики является вычисли- тельная геометрия – раздел дискретной математики, изучающий во- просы решения геометрических задач средствами ЭВМ. Данное методическое пособие освещает основные вопросы разработки компьютерных программ для синтеза изображений в реальном времени. Рассматриваются математические и алго- ритмические основы компьютерной графики, необходимые для управления процессом подготовки и отображения виртуальных графических сцен различной сложности. Изложенный материал включает в себя теоретические и практические аспекты программи- рования графики и предполагает реализацию описываемых приёмов по мере прочтения. Алгоритмическая и элементная базы компьютерной графики развиваются с каждым годом: выходят всё новые версии видеокарт, драйверов, графических API; потентуются новые приёмы синте- за изображений. Однако существует некоторое алгоритмическое «ядро», сформированное ещё в 60–70-е г. XX в. и остающееся неизменным до сих пор. Данное пособие концентрируется в первую очередь именно на использовании этого «ядра». 5 По мере изложения периодически будут использоваться от- сылки к «настоящему времени» (при описании тех или иных техно- логий, соответствия используемого программного обеспечения тем или иным стандартам и т. п.). В этом контексте под «настоящим вре- менем» понимается первая половина 2017 г . Вполне вероятно, что несколько лет спустя ситуация кардинально изменится, однако учи- тывая историю развития компьютерной графики в последние полве- ка, алгоритмическое «ядро» будет актуально ещё долго – как мини- мум до тех пор, пока в историю не отойдут привычные нам сегодня средства отображения информации, такие как мониторы, дисплеи, проекторы, принтеры и типографские станки. Следует сразу отметить, что данное пособие не является пол- ноценным учебником или техническим руководством по компьютер- ной графике; скорее, оно представляет собой расширенное введение в эту область. Оно ориентировано на начинающих и ставит своей целью подготовить почву для изучения более серьёзных книг (та- ких как, например, «OpenGL Суперкнига» [1]), онлайн-курсов (на- пример, «Neon-Helium» [2]) и прочих источников. Кроме того, оно включает в себя материал нескольких первых лекций курса «Вычис- лительная геометрия и алгоритмы компьютерной графики», который читается в Пермском госудраственном национальном исследователь- ском университете. Предполагается, что читатель обладает базовыми знаниями в области геометрии и линейной алгебры, а также знаком с програм- мированием на языках C/C++. Работа с графикой рассматривается на примере стандарта OpenGL ввиду его мультиплатформенности. Однако все описанные методы и алгоритмы носят универсальный характер, поэтому, ознакомившись с данным пособием, читатель без труда сможет освоить и другие стандарты (например, Direct3D или Metal). Для практической реализации описанных методов и алгорит- мов читателю понадобится компьютер с поддержкой OpenGL версии не ниже 3.3, компилятор языка C++, а также набор библиотек, вклю- чающих реализацию функций стандарта OpenGL и вспомогательных операций. 6 Данное методическое пособие предполагает работу с графи- кой на низком уровне , т. е. на уровне, максимально приближенном к графическому оборудованию (видеокарте, GPU), чтобы у читате- ля сложилось глубокое понимание процессов синтеза изображений средствами современных ЭВМ. 7 1. Формирование изображений в компьютерной графике Наиболее общий вид цепочки преобразований, приводящей к построению изображения средствами ЭВМ, представлен на рис. 1. Рис. 1. Процесс визуализации Сцена – это совокупность объектов, подлежащих отображе- нию, описанная при помощи некоторой математической модели. Ви- зуализация – это процесс преобразования математической модели сцены в вид, пригодный для показа на имеющихся устройствах вы- вода. Отображение – это процесс демонстрации итогового изображе- ния человеку средствами имеющихся устройств вывода. Как правило, отображение осуществляется посредством мони- тора и требует для этого подготовки двумерного растрового изоб- ражения , т. е. структуры данных в виде прямоугольной матрицы за- данного размера, каждая ячейка которой содержит кодировку опре- делённого цвета. Для кодирования чаще всего используется цвето- вая модель RGB , в которой каждый цвет представлен в виде яркости красного, зелёного и синего. Такая модель достаточно хорошо под- ходит для современных мониторов, поскольку они обычно представ- ляют собой набор ячеек прямоугольной (как правило – квадратной) формы, каждая из которых может излучать свет красного, зелёного и синего цветов с контролируемой интенсивностью. 8 Методы и средства компьютерной графики могут быть класси- фицированы по самым разным критериям, но чаще всего разделение проводится по размерности пространства, с элементами которого ве- дётся работа, и по типу математической модели. По размерности пространства принято выделять одномерную (1D), двумерную (2D), трёхмерную (3D) графику и графику высших порядков. По типу математической модели выделяют растровую и векторную графику. Растровая графика предполагает представление сцены в виде сетки элементов одинаковой формы. Векторная графи- ка предполагает математическое описание элементов сцены. Современное аппаратное обеспечение (GPU) нацелено на работу с 3D-графикой, так как она является наиболее естественной для человека и выступает, по сути, математическим обобщением не менее привычной 2D-графики. Однако большая часть современных средств отображения способна воспроизводить только плоские (2D) изображения, т. е. встаёт задача понижения размерности пространства в процессе визуализации. С точки зрения представления сцены на GPU используется векторная модель, потому что в трёхмерном случае она оказывается значительно более эффективной по времени и памяти, чем растро- вая. Однако, как уже отмечалось выше, для отображения на экране необходимо растровое изображение, т. е. в процессе визуализации встаёт задача преобразования векторной сцены в растр. Таким образом, если речь идёт о работе с 3D-графикой на со- временных GPU и отображении результата на мониторе, математиче- ская модель сцены является векторной, а этап визуализации включа- ет в себя проекцию сцены в двумерное пространство, растеризацию и вычисление цвета каждой точки растра в соответствии с параметра- ми объектов сцены. Визуализацию иначе ещё называют рендерингом (от англ. Rendering – преобразование одного в другое). Представление векторной математической модели сцены на сегодняшний день является стандартизированным и единообразным для подавляющего большинства современных GPU. Все объекты сцены представляются в виде множества многоугольников, аппрок- симирующих их поверхности. Многоугольники представляются 9 вершинами и связями между ними. Такую векторную модель иначе ещё называют полигональной (от гр. полигон – многоугольник). Подход на основе полигонализации применяется в силу нали- чия эффективных алгоритмов для растеризации и вычисления визу- альных свойств поверхностей. Обработка поверхностей как дискрет- ных сеток, в свою очередь, хорошо ложится на логическую природу ЭВМ как конечного автомата. Более того, большая часть графического оборудования пред- назначена для работы с сетками треугольников, а не произвольных многоугольников, так как вершины треугольника гарантированно ле- жат в одной плоскости. Это позволяет использовать простые и эф- фективные алгоритмы интерполяции параметров поверхности, дис- кретно заданных в узлах аппроксимирующей её сетки. 10 2. Уровни работы с графикой Любое достаточно сложное приложение, работающее с ком- пьютерной графикой, «в разрезе» выглядит так, как показано на рис. 2. Рис. 2. Структура графического приложения Основной вопрос, на который должен ответить разработчик перед началом создания графического приложения: с какого уровня начинать писать собственный программный код? Программированием на уровне графического оборудования, как правило, занимаются лишь его производители. Графическая библиотека, реализующая определённый стан- дарт абстрагирования от оборудования, напрямую взаимодействует с драйвером. Стандартами абстрагирования являются, например, OpenGL (англ. Open Graphics Library – открытая графическая библиотека; для настольных компьютеров под управлением различ- ных ОС), OpenGLES (англ. Open Graphics Library for Embedded Systems – открытая графическая библиотека для встраиваемых 11 систем; для мобильных устройств под управлением различных ОС), WebGL (англ. Web Graphics Library – графическая библиотека для веб-приложений), Direct3D (для различных ЭВМ под управлением Windows и Windows Phone), Metal (для мобильных устройств под управлением iOS). Реализацией стандартов в виде библиотек функций занимают- ся, как правило, производители оборудования или ОС. Графические библиотеки по природе своей являются универсальными и предпола- гают лишь минимальное повышение уровня API графического драй- вера. Графический движок (модуль графического расширения) при- зван повысить уровень API графической библиотеки для удобства реализации логики приложения. На уровне графической библиоте- ки работа производится с «сырыми» данными объектов сцены, таки- ми как «вершина», «треугольник», «цвет» и т. д., лишёнными какой- либо семантики. На уровне движка выделяются сущности, в той или иной степени привязанные к предметной области приложения. На- пример, игровые движки могут работать в терминологии определён- ного класса игр, имея в своём API такие сущности, как «игрок», «про- тивник», «оружие», «ландшафт», «препятствие», «индикатор очков» и пр. Существуют, однако, и универсальные движки, минимально повышающие уровень API графической библиотеки и работающие с абстрактными понятиями, такими, как «сцена», «трёхмерный объ- ект», «источник света» и пр. На сегодняшний день создано очень большое количество гра- фических движков разной степени универсальности (и многие из них продолжают активно развиваться). По сути, существующее много- образие движков полностью покрывает потребности программистов, собирающихся создать очередное графическое приложение. Несмот- ря на это, иногда принимается решение разрабатывать собственный движок. Мотивация здесь может быть различна: желание иметь пол- ный контроль над кодовой базой и независимость от сторонних раз- работчиков, желание набраться опыта, очень специфические условия задачи, проблемы юридического характера с лицензионными согла- шениями и т. п. В общем случае «изобретение велосипеда» – скорее 12 плохо, чем хорошо, поэтому решение создавать собственный движок при работе над реальным проектом должно быть чётко обосновано. Однако для начинающего разработчика создать собственный (вероятно, достаточно легковесный) движок – это хороший способ глубоко разобраться в вопросах компьютерной графики, а также на- браться опыта в проектировании и реализации сложных программ- ных систем. Данное методическое пособие обходит вопросы выбора гото- вого или реализации собственного движка стороной, концентрируя внимание на вопросах работы низкоуровневых графических библио- тек. Обладая такими знаниями, читатель сможет как быстро осво- ить любой готовый движок, так и, при необходимости, создать свой собственный. 13 3. Графический конвейер Как уже отмечалось выше, общепринятой математической мо- делью в 3D-графике выступает аппроксимация поверхностей объек- тов при помощи сеток из треугольников. Следует отметить, что мето- ды компьютерной графики не ограничиваются таким подходом: су- ществуют модели на основе гладких поверхностей, модели на основе элементов объёма (вокселей, от англ. Voxel – Volume Element, эле- мент объёма) и др. Однако полигональная модель на сегодняшний день является самой популярной и имеет аппаратную поддержку. Атомарной управляемой геометрической единицей в поли- гональной модели является вершина . С ней может быть связан про- извольный набор атрибутов , интерпретация которых осуществля- ется программистом. Чаще всего в этот набор входят, как минимум, пространственные координаты, но также может содержаться и до- полнительная информация, например цвет или данные для его вы- числения, информация о кривизне поверхности, скорость и направ- ление перемещения вершины в пространстве и т. д. Вершины объединяются в примитивы – минимальные отобра- жаемые части объектов. Как правило, графическими библиотеками поддерживаются точки (отображение вершин в виде квадратов или кругов заданного размера), линии (отображение связей между вер- шинами в виде линий заданной толщины) и треугольники. Следу- ет отметить, что графическое оборудование на низком уровне под- держивает только отображение треугольников. Точки и линии явля- ются результатом автоматической триангуляции (покрытия множе- ством треугольников), производимой с использованием внутренних функций графической библиотеки. В связи с этим, при прочих рав- ных, отображение примитивов-треугольников происходит быстрее, чем отображение примитивов-точек и примитивов-линий (графиче- ская библиотека передаёт данные графическому драйверу без пред- варительных преобразований). Данные о вершинах (их атрибуты), связях между ними и типах примитивов, в которые они входят, отправляются из основной про- 14 граммы (из оперативной памяти) в видеопамять (память видеокарты, к которой GPU имеет достаточно быстрый доступ). Как правило, от- правка данных в видеопамять – это подготовительный этап, «загруз- ка сцены». Обычно он производится однократно, на фоне некоторого экрана загрузки, поскольку, как любая операция копирования, зани- мает относительно много времени. Данные, находящиеся в видеопамяти, могут быть отправлены на т.н. графический конвейер (англ. Pipeline ) – цепочку преобразо- ваний, в конце которой получается итоговое растровое изображение. Этапы работы графического конвейера приведены на рис. 3. Рис. 3. Графический конвейер Во время работы конвейера происходит следующее: 1. Вызов отрисовки (англ. Draw Call ): отправка данных на гра- фический конвейер. 2. Преобразование вершин (англ. Vertex Transformation ): вычис- ление финальных координат вершин в пространстве по их ат- 15 рибутам (т.е. определение финального положения объектов на сцене), а также, при необходимости, динамическое порожде- ние новых вершин ( тесселяция поверхности). 3. Сборка примитивов (англ. Primitive Assembling ): объединение отдельных вершин в примитивы. 4. Отсечение (англ. Clipping ): отброс невидимых частей сцены. 5. Растеризация (англ. Rasterization ): подбор точек растра (т. н. фрагментов) итогового изображения, покрывающих проекцию на экран каждого из примитивов. 6. Преобразование фрагментов (англ. Fragment Transformation ): вычисление цвета (и других характеристик) каждой точки рас- тра в соответствии с параметрами объекта, которому эта точка принадлежит. 7. Тест видимости (англ. Visibility Test ): отброс невидимых фраг- ментов. 8. Смешивание (англ. Blending ): объединение вычисленного цве- та каждой точки растра с цветами, вычисленными для этих то- чек растра ранее. 9. Отображение (англ. Displaying ): показ полученного изображе- ния на экране. 16 |