Реализация алгоритмов

ОГЛАВЛЕНИЕ Оглавление 2 1. Лабораторная работа № 1 3 1.1.Постановка задачи . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.2.Проектирование программы . . . . . . . . . . . . . . . . . . . . . . 3 1.2.1.Формат файла сцены . . . . . . . . . . . . . . . . . . . . . . . 3 1.2.2.Считывание из файла . . . . . . . . . . . . . . . . . . . . . . . 4 1.2.3.Структура данных программы . . . . . . . . . . . . . . . . . . 5 1.3.Неочевидные вопросы . . . . . . . . . . . . . . . . . . . . . . . . . 10 2. Лабораторная работа № 2 11 2.1.Постановка задачи . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.2.Проектирование программы . . . . . . . . . . . . . . . . . . . . . . 11 2.2.1.Формат файла сцены . . . . . . . . . . . . . . . . . . . . . . . 11 2.2.2.Реализация алгоритма Робертса . . . . . . . . . . . . . . . . . 12 2.3.Возможные вопросы . . . . . . . . . . . . . . . . . . . . . . . . . . 14 3. Лабораторная работа № 3 15 3.1.Постановка задачи . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 3.2.Проектирование программы . . . . . . . . . . . . . . . . . . . . . . 15 3.2.1.Формат файла сцены . . . . . . . . . . . . . . . . . . . . . . . 15 3.2.2.Реализация алгоритма Z-буфера . . . . . . . . . . . . . . . . . 16 3.3.Возможные вопросы . . . . . . . . . . . . . . . . . . . . . . . . . . 18 4. Лабораторная работа № 4 19 4.1.Постановка задачи . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 4.2.Проектирование программы . . . . . . . . . . . . . . . . . . . . . . 19 2 ГЛАВА 1. ЛАБОРАТОРНАЯ РАБОТА № 1 1.1. Постановка задачи Написать программу, которая: – загружает из текстового файла трёхмерную сцену, состоящую из отрезков; – отображает трёхмерную сцену (проекцию сцены на плоскость XY , ось X направлена вправо, Y – вверх, Z – на наблюдателя, начало координат расположено в центре области отображения); – осуществляет над сценой аффинные преобразования: параллельный перенос, масштабирование, поворот вокруг осей координат и косой сдвиг; – осуществляет над сценой ОПП1 с заданным параметром; – параметры преобразований задаются пользователем; – осуществляет вписывание сцены в область отображения без искажений (одинаковое масштабирование по всем осям, отсутствие вращений). 1.2. Проектирование программы 1.2.1. Формат файла сцены Рассмотрим задачу описания трёхмерной сцены в текстовом файле. Так как сцена состоит из отрезков, можно, к примеру, задавать каждый отрезок шестью координатами, по три координаты для каждого конца, x1 y1 z1 x2 y2 z2 , разделённые пробелом. Каждый отрезок может быть записан в своей строке. Тогда содержание файла будет примерно таким: 0.0 0.0 0.0 10.0 12.0 15.0 10.0 12.0 15.0 10.0 12.0 0.0 Ещё один способ задать сцену из отрезков – отделить геометрическое описание точек в пространстве от топологии (связей между ними). В таком случае, содержание файла для сцены из первого примера будет выглядеть так: 1 ОПП – одноточечное проективное преобразование 3 0.0 0.0 0.0 10.0 12.0 15.0 10.0 12.0 0.0 0 1 1 2 В начале файла описаны точки в каждой строке по три координаты. Координаты разделены пробелами. Далее в каждой строке по одному записаны отрезки. Каждый отрезок описывается двумя порядковыми номерами точек, соответствующих концам отрезка. Такой вариант описания сцены является более удобным, так как в геометрических фигурах каждая вершина часто является концом нескольких отрезков. 1.2.2. Считывание из файла Для упрощения считывания из файла трёхмерной сцены можно ввести некоторые изменения в ранее предложенные форматы файла, а именно – ввести «блоки» точек и топологии. Содержание файла с блоками может выглядеть так: 3 0.0 0.0 0.0 10.0 12.0 15.0 10.0 12.0 0.0 2 0 1 1 2 Как видно из приведённого примера, к предыдущему описанию добавлено две строки. В первой указано количество точек, записанных в файле, во второй – количество отрезков. Такой подход позволяет не тратить время на анализ информации в строке, а заранее предполагать что именно, точка или отрезок, описаны в строке. Программа может прочитать из первой строки количество точек, затем повторить считывание точек из последующих строк указанное количество раз. Аналогично программа поступит и с «блоком» отрезков. Конечно, при та4 ком подходе нужно условиться, что количества точек и отрезков всегда указаны верно, в противном случае программа не сможет прочитать файл сцены. 1.2.3. Структура данных программы Необходимо определиться со структурой данных, которая будет хранить трёхмерную сцену. В зависимости от порядка обработки данных структура хранимых переменных может меняться. Самый примитивный класс, с которым необходимо работать,– это класс точки. Лучше всего хранить точку в виде массива из четырёх чисел с плавающей запятой. Таким образом, можно хранить однородные координаты точки и иметь доступ к каждой из координат по её номеру в массиве. [ ] x y z h Данные о геометрии и топологии предлагается хранить таким же образом, как и в файле: точки хранить в отдельном массиве, для каждого отрезка хранить номера его концов в массиве точек. Разделять информацию о точках с информацией об отрезках более разумно, так как: работа с геометрической информацией отделена от работы с топологической (алгоритмы преобразования работают с координатами точек), объём используемой памяти обычно меньше (так как устраняется дублирование геометрической информации о точках при описании геометрических фигур). Матрицы преобразования Матрицы преобразования отличаются для точек, представленных в виде матрицы строки и матрицы столбца. Условимся, что точки представлены в виде матрицы строки. Тогда матрицы преобразования будут выглядеть так2 : 2 См. Роджерс Д. «Математические основы машинной графики» 5   a b   d e   h i  l m c p   f q ,  j r  n s где a, e, j отвечают за масштабирование соответственно по осям x, y, z; l, m, n отвечают за параллельный перенос соответственно по осям x, y, z Матрица параллельного переноса на вектор ⃗a (x, y, z):  1 0   0 1   0 0  x y  0 0   0 0 .  1 0  z 1 Матрица масштабирования по оси X:   k 0  x   0 1    0 0  0 0 0 0   0 0 .  1 0  0 1 Матрица масштабирования по оси Y :   1 0    0 ky   0 0  0 0 0 0   0 0 .  1 0  0 1 6 Матрица масштабирования по оси Z:   1 0   0 1   0 0  0 0 0 0   0 0 .  kz 0   0 1 Матрица поворота вокруг оси X на угол α:   1    0 cos α sin α 0    0 − sin α cos α 0  1    .    Матрица поворота вокруг оси Y на угол α:  cos α    0    sin α  0 − sin α 0 1 1 cos α    0 .  0  1 Матрица поворота вокруг оси Z на угол α:   cos α sin α 0 0    − sin α cos α 0 0    1 0  0 1    .    7 Матрица косого сдвига оси X по оси Y с коэффициентом k:  1 0   k 1   0 0  0 0  0 0   0 0 .  1 0  0 1 Матрица косого сдвига оси X по оси Z с коэффициентом k:  1 0   0 1   k 0  0 0  0 0   0 0 .  1 0  0 1 Матрица косого сдвига оси Y по оси X с коэффициентом k:  1 k   0 1   0 0  0 0  0 0   0 0 .  1 0  0 1 Матрица косого сдвига оси Y по оси Z с коэффициентом k:  1 0   0 1   0 k  0 0  0 0   0 0 .  1 0  0 1 8 Матрица косого сдвига оси Z по оси X с коэффициентом k:  1 0   0 1   0 0  0 0  k 0   0 0 .  1 0  0 1 Матрица косого сдвига оси Z по оси Y с коэффициентом k:  1 0   0 1   0 0  0 0  0 0   k 0 .  1 0  0 1 Матрица ОПП по оси X с фокусным расстоянием fx :   1 fx 1 0 0     0 1 0 0  .    0 0 1 0    0 0 0 1 Матрица ОПП по оси Y с фокусным расстоянием fy :  1 0   0 1   0 0  0 0  0 0    .  1 0   0 1 1 fy 9 Матрица ОПП по оси Z с фокусным расстоянием fz :  1 0   0 1   0 0  0 0  0 0   0 0  . 1  1 fz   0 1 Порядок обработки. Существует два варианта порядка обработки точек: 1. Хранение исходной сцены, обрабатываемой через итоговое преобразование перед отрисовкой, итоговое преобразование – это матрица, являющаяся результатом произведения матриц всех преобразований в соответствующем порядке. 2. Хранение преобразованной сцены с последовательным применением преобразований. 1.3. Неочевидные вопросы 1. Для ОПП можно задавать фокусное расстояние или непосредственно величину соответствующего элемента матрицы преобразования. Что именно используется в программе – часто задаваемый вопрос. 2. Сколько существует разных простых косых сдвигов? Существует шесть косых сдвигов: x/y (x по y) – элемент d матрицы преобразования, x/z – элемент h, y/x, y/z, z/x, z/y 10 ГЛАВА 2. ЛАБОРАТОРНАЯ РАБОТА № 2 2.1. Постановка задачи Дополнить возможности программы первой лабораторной работы возможностями задания в исходном файле многогранника и выполнения анализа видимости для этого многогранника с помощью алгоритма Робертса. 2.2. Проектирование программы 2.2.1. Формат файла сцены В первой работе мы выбрали способ представления сцены, составленной из отрезков. Сейчас нам нужно расширить его для представления многогранников. Наиболее простой способ задания многогранника – задать его как набор граней (многоугольников). Продолжая использовать идею о разделении геометрической и топологической информации, логично сохранить способ представления набора точек, а многоугольник задавать как последовательность целых чисел, размещенных в одной строке файла. Каждое из этих чисел соответствует одной вершине многоугольника и представляет собой номер точки в списке точек. Единичный квадрат в плоскости XZ тогда может быть представлен как: 4 0.0 0.0 0.0 1.0 0.0 0.0 0.0 0.0 1.0 1.0 0.0 1.0 1 0 1 3 2 или 11 4 0.0 0.0 0.0 1.0 0.0 0.0 0.0 0.0 1.0 1.0 0.0 1.0 2 0 1 3 0 3 2 В последнем случае мы разбили квадрат на 2 треугольника. При таком подходе все преобразования, реализованные в задаче № 1, продолжают работать без каких-либо изменений. Для отображения многоугольников нужно внести очевидные изменения, т.е. добавить возможность рисования набора отрезков, заданного последовательностью номеров вершин. 2.2.2. Реализация алгоритма Робертса Для корректной работы алгоритма Робертса необходимо вычислить внешнюю нормаль для каждой грани заданного пользователем многогранника. Имеет смысл разделить эту задачу на две части. Сначала вычислить какую-нибудь нормаль, а затем определить, является ли она внешней. Если да, то задача решена, в противном случае нужно изменить направление найденного вектора нормали на противоположное. Найти какую-нибудь нормаль проще всего векторным произведением двух векторов, соответствующих двум последовательным ребрам исходного многоугольника. Если мы можем быть уверены, что два последовательных ребра неколлинеарные, то больше ничего не нужно. Если такой уверенности нет, то есть смысл проделать эту процедуру для всех пар последовательных векторов и выбрать векторное произведение с максимальным модулем. Такой подход все еще не приведет к результату, если многоугольник вырожден в отрезок, но в этом случае задача неразрешима в принципе, т.к. невозможно разумным образом определить понятие нормали для такого многоугольника. 12 Проверка является ли найденная нормаль внешней не может, очевидно, быть выполнена локально. Это значит, что невозможно сделать эту проверку, рассматривая только одну грань. Необходимо будет использовать другие вершины многогранника, т.е. вершины, принадлежащие другим граням. Если многогранник выпуклый, а алгоритм Робертса способен работать только с выпуклыми, то достаточно одной такой точки. Более точно, нам нужно найти любую вершину многогранника, не лежащую в плоскости рассматриваемой грани. Если считать, что никакие две точки в списке точек не совпадают, то нам нужно найти вершину, номер которой не содержится в списке номеров вершин рассматриваемой грани. Для этого просто будем перебирать номера всех вершин многогранника, для каждой из них перебирать все вершины текущей грани и сравнивать. Поиск закончен, когда очередная вершина многогранника не совпала ни с одной вершиной текущей грани. Эта процедура, конечно, может быть выполнена более эффективно, но это не является принципиальным в данном случае. Пусть теперь ⃗n – найденный нами вектор нормали, v – одна из вершин текущей грани, p – найденная нами вершина многогранника, не принадлежащая текущей грани. Тогда очевидно, что нормаль является внешней если и только если (p − v) · ⃗n < 0. После того, как внешние нормали найдены реализация алгоритма Робертса сводится к проверке знака скалярного произведения ⃗n · ⃗e для каждой грани. Здесь ⃗n – внешняя нормаль, а ⃗e – направление взгляда. В нашем случае вектор ⃗e имеет координаты ( 0 0 −1 ), т.к. ось Z направлена на наблюдателя. Если это скалярное произведение отрицательно, то грань видима. Если положительно, то грань невидима. 13 2.3. Возможные вопросы 1. Если задать исходные точки так, чтобы многогранник оказался невыпуклым, то результат анализа видимости при каком-то ракурсе окажется неправильным. Почему это происходит? Какие именно вычисления в вашей программе приводят к такому результату? 2. Как ваша программа отличает внешнюю нормаль от внутренней? 14 ГЛАВА 3. ЛАБОРАТОРНАЯ РАБОТА № 3 3.1. Постановка задачи Расширить возможности программы второй лабораторной работы возможностью выполнять анализ видимости с помощью алгоритма Z-буфера. 3.2. Проектирование программы 3.2.1. Формат файла сцены Алгоритм Z-буфера, в отличие от алгоритма Робертса, способен обрабатывать сцену, составленную из произвольного набора многоугольников, а не только один многогранник. К счастью, способ представления многогранника, который мы использовали для решения задачи № 2, годится и для этого случая без каких-либо изменений. Однако, есть, все-таки, один нюанс. Алгоритм Z-буфера является растровым. Результатом его работы будет изображение закрашенных многоугольников, заданных в исходном файле. Если все эти многоугольники будут закрашены одним цветом, то невозможно будет отличить один от другого, а, следовательно, невозможно будет представить себе сцену и оценить правильность работы алгоритма анализа видимости. Более того, изображение будет одинаковым как с анализом видимости, так и без него. В рамках следующей, четвертой лабораторной работы мы научимся вычислять цвет для каждой грани в соответствии с заданным освещением. Тогда проблема отпадет сама собой. Чтобы избежать ее уже сейчас, можно либо выполнять эти две работы одновременно, либо задать в исходном файле свой цвет для каждой грани, либо присваивать эти цвета внутри программы по какому-нибудь правилу. Во втором случае придется внести небольшие изменения в структуру исходного файла, а именно, добавить возможность задать цвет для каждой грани. 15 3.2.2. Реализация алгоритма Z-буфера Есть 2 пути, по которым можно пойти при выполнении этой работы. Первый – использовать готовый продукт, в котором алгоритм Z-буфера уже реализован (например, OpenGL). На этом пути объем работы по программированию будет существенно меньше, но придется самостоятельно освоить все, что касается основ работы с OpenGL. Второй путь – самостоятельная реализация алгоритма. Обсудим его подробнее. Алгоритм Z-буфера можно записать так: A. Инициализировать Z-буфер и буфер кадра. B. Для каждого многоугольника в сцене: 1. Для каждого пикселя, принадлежащего проекции многоугольника на картинную плоскость (X, Y): A. Вычислить значение Z(X, Y). B. Если Z(X, Y) > Zb(X, Y): 1. Заменить значение Zb(X, Y) на Z(X, Y). 2. Заменить цвет элемента (X, Y) буфера кадра на цвет текущего многоугольника. Здесь Zb(X, Y) – значение элемента (X, Y) из Z-буфера. Обсудить реализацию имеет смысл для пунктов B.1 и B.1.A. Начнем со второго. Вычислить значение Z для плоскости при заданных X и Y проще всего, построив уравнение этой плоскости в виде Ax + By + Cz + D = 0 и подставив в него X и Y . Коэффициенты A, B и C в этом уравнении есть компоненты вектора нормали к плоскости. Вычисление этого вектора обсуждалось в задаче № 2. Для вычисления D можно подставить в качестве x, y, z координаты любой точки, лежащей в плоскости, например, одной из вершин. Рассмотрим еще вырожденные случаи. Формула для вычисления Z будет иметь вид: 16 Z=− A·X +B·Y D Особенность здесь возникает только при D = 0. Такая плоскость оказывается перпендикулярной к картинной плоскости и, следовательно, ее можно игнорировать, т.к. она на вносит никакого вклада в результирующее изображение. Рассмотрим теперь подробнее пункт B.1. Здесь должен быть использован какойнибудь алгоритм растровой развертки (закраски) многоугольника. Например, алгоритм со сканирующей строкой: A. Для каждой строки растра (Y): 1. Для каждого ребра многоугольника: A. Найти точку пересечения ребра с горизонтальной прямой y = Y. B. Упорядочить все найденные точки пересечения по возрастанию координаты X. Нумеровать, начиная с индекса 0. C. Для каждой точки с четным индексом: 1. Для каждого пикселя в текущей строке, лежащего между этой точкой и следующей: A. Передать пиксель для дальнейшей обработки в алгоритме Z буфера. Особенностью работы этого алгоритма является его непредсказуемое поведение в случае, когда сканирующая прямая точно попадает в вершину многоугольника, т.е. координата Y одной из вершин многоугольника совпадает со значением Y для сканирующей прямой. Есть различные способы устранения этой непредсказуемости. В нашем случае проще всего пойти по пути небольших изменений значения Y сканирующей прямой, до тех пор пока оно не перестанет совпадать с координатой Y какой-либо вершины. При этом мы обязаны обеспечить, чтобы сканирующая прямая не вышла за пределы строки растра, 17 для которой она построена. Если сканирующая прямая изначально проводится в середине строки пикселей, то это значит, что суммарное изменение Y не может превышать половину высоты пикселя. Для того чтобы обеспечить выполнение этого условия, достаточно задать значение «небольшого изменения» меньшим, чем H 2(N +1) , где H – высота пикселя, а N – количество вершин мно- гоугольника. Реализация пункта A.1.A – это, конечно, просто нахождение точки пересечения прямой и отрезка. В данном случае его можно выполнить так. Сначала проверить лежит ли значение Y сканирующей прямой между значениями Y начальной и конечной точки отрезка. Если да, то вычислить значение X точки пересечения по формуле: X = X0 · (1 − d) + X1 · d d= |Y0 − Y | |Y0 − Y1 | где X0 , Y0 , X1 , Y1 – координаты X и Y начальной и конечной точек отрезка. Единственная особенность в этой формуле возникает при Y0 = Y1 , т.е. когда отрезок горизонтальный. В нашем случае неприятности, связанные с этой особенностью, возникнуть не могут, т.к. либо этот отрезок не пройдет входной тест (Y лежит между ...), либо будет распознана ситуация попадания сканирующей прямой в вершину и значение Y этой прямой будет изменено, после чего отрезок уже точно не пройдет тест. 3.3. Возможные вопросы 1. Что произойдет, если вершины одного многоугольника не лежат в одной плоскости? 2. Как в программе реализовано эффективное использование всего диапазона изменения Z? 18 ГЛАВА 4. ЛАБОРАТОРНАЯ РАБОТА № 4 4.1. Постановка задачи Дополнить возможности программы автоматическим определением цвета для каждой грани в соответствии с простейшей моделью освещения и обеспечить пользователю возможность изменять коэффициенты зеркального и диффузного отражения и степень зеркальности. 4.2. Проектирование программы Эта задача, наверное, самая простая из четырех. Необходимо обеспечить вычисления по заданным формулам модели освещения. Исходными данными для этих расчетов будут вектор нормали к плоскости многоугольника, направление взгляда и направление света. Задание не требует возможности управлять двумя последними параметрами, поэтому их можно сделать одинаковыми и равными ( 0 0 −1 ). Это будет означать что пользователь смотрит вдоль оси Z и свет падает в таком же направлении. Рассеянное отражение Интенсивность рассеянного отражения равна: Id = I · kd · cos θ; 0 ≤ θ ≤ π 2 Из формулы видно, что значение угла θ нам не нужно, достаточно получить значение cos θ. Скалярное произведение векторов выглядит следующим образом: ⃗a · ⃗b ⃗ ⃗ ⃗a · b = |⃗a| · b · cos θ ⇒ cos θ = |⃗a| · ⃗b Пусть ⃗a – это вектор падающего на поверхность луча, ⃗b = −⃗n – это вектор, обратный вектору нормали, тогда cos θ – это косинус угла между падающим лучом и нормалью к поверхности. Получается, что вычисление значения угла не является необходимым. 19 Зеркальное отражение Интенсивность зеркального отражения равна: Im = I · km · cosn β где β – это угол между лучом зрения и отражённым лучом. Получение вектора отражённого луча Зная вектор нормали ⃗n и вектор ⃗ можно получить вектор отражённого луча по следующей падающего луча L формуле: ⃗=L ⃗ −2· S ( ) ⃗ ⃗n · ⃗n · L |⃗n|2 Особенностей в этих формулах быть не может, т.к. единственный знаменатель – квадрат модуля вектора нормали. Рассматривая алгоритм Робертса, мы уже обсуждали, как добиться того, чтобы этот вектор не был нулевым. Подумать нужно только о знаках cos α и cos β в этих формулах. Ясно, что знак cos α зависит от выбора направления вектора нормали к поверхности. Если мы хотим, чтобы cos α всегда был неотрицательным, то вектор нормали должен быть направлен так, чтобы скалярное произведение вектора взгляда на вектор нормали было неотрицательным. Точно такой же эффект мы получим если просто подставим в формулу модуль cos α . Такой подход часто называют «односторонним» представлением. Здесь имеется в виду, что обе стороны грани являются абсолютно равноправными, т.е. вычисленная интенсивность не зависит от того, с какой стороны наблюдатель смотрит на грань. Двустороннее представление позволяет различать разные стороны одной и той же грани и, соответственно, вычислять для них различные атрибуты. В этом случае для положительных значений cos α используются одни коэффициенты, а для отрицательных – другие. Со знаком cos β ситуация другая. Направление вектора отраженного луча ⃗ вычисленного по приведенной выше формуле, не будет зависеть от направS, ления нормали. Точнее, не будет зависеть от того, какую из двух возможных 20 нормалей мы выберем. Знак будет зависеть от того, по одну сторону от плоскости грани находятся наблюдатель и источник света или по разные стороны. Здесь тоже можно использовать различные стратегии по определению атрибутов для различных случаев взаимного расположения наблюдателя и источника света. Например, можно считать, что если наблюдатель и источник находятся по разные стороны, т.е. знаки скалярных произведений вектора направления взгляда на вектор нормали и вектора направления света на вектор нормали разные, то этот источник света не влияет на наблюдателя и соответствующее значение интенсивности равно нулю. 21