Контрольная работа по "Компьютерная графика"

Такая итерационная процедура  с вырезанием сквозных отверстий  и последующего превращения каждого  оставшегося кубика в 20 еще более  мелких кубиков с размером в три  раза меныие исходного продолжается до бесконечности. В результате этих операций и образуется идеально самоподобный объект губка Менгера. Каждая грань  исходного куба выглядит при этом так же, как ковер Серпинского.

Фрактальная размерность  губки Менгера равна 

 

Поскольку то губка имеет нулевой объем, но обладает бесконечной площадью поверхности своих пор.

Легко заметить, что для  фигур, обладающих свойством идеального самоподобия, правило позволяющее  определить размерность  можно сформулировать следующим образом.

Если множество, состоящее  из одинаковых элементов, строится с  помощью самоподобного процесса, причем на любом шаге каждый из элементов  с линейными размерами заменяется подобными элементами,  размерами каждый, то фрактальная размерность такого объекта очевидно равна

 

Для всех рассмотренных выше регулярных фракталов фрактальная  размерность оказалась меньше, чем размерность того пространства d в котором находится данный фрактальный объект. Неравенство отражает факт некомпактности фрактала, причем, чем больше различаются величины и d , тем более рыхлым является фрактал.

Кривая  Госпера

Инициатором для кривой является отрезок единичной длины, а генератор  показан на рисунке справа. Он состоит  из 7 отрезков длиной каждый. Фрактальная размерность этой кривой равна 2.

Пунктиром показана треугольная решетка, служащая своеобразной образующей для  этого генератора. Следующие три  шага процесса построения показаны на рисунке.

Интересной отличительной  особенностью кривой Госпера является то, что граница области, называемой "островом Госпера", которую она  заполняет в пределе бесконечного числа шагов, сама является фрактальной  с нецелочисленной размерностью 1.1291. Такие острова можно использовать для непрерывного покрытия плоскости, так как можно показать, что они идеально стыкуются друг с другом. Более того, семь таких островов, состыкованных вместе (один в центре и шесть вокруг него), образуют снова остров Госпера в три раза большего размера. Заметим, что подобным свойством из правильных многоугольников обладает только квадрат.

Пример кривой Пеано – «дракон» Хартера-Хейтуэя

Рассмотрим кривую Пеано, для которой область, которую  она заполняет на плоскости, имеет  весьма причудливую форму. Это так  называемый дракон Хартера-Хейтуэя. Первые 4 шага его построения изображены на рисунке. Как следует из рисунка, каждый из отрезков прямой

на следующем шаге заменяется на два отрезка, образующих боковые  стороны равнобедренного прямоугольного треугольника, для которого исходный отрезок являлся бы гипотенузой. В результате отрезок как бы прогибается  под прямым углом. Направление прогиба  чередуется. Первый отрезок прогибается  вправо (по ходу движения слева направо), второй – влево, третий – опять  вправо и т. д. Для удобства восприятия на каждом рисунке пунктиром показана конфигурация предыдущего шага. Таким  образом, после каждого шага число  имеющихся отрезков удваивается, а  длина каждого соответ-ственно  уменьшается в раз. Поэтому фрактальная размерность образующейся в результате (после бесконечного числа шагов) кривой равна 2, т. е., кривая «заметает» собой конечную площадь. 0 форме образующейся необычной фигуры можно получить представление из рисунка, где изображены 12-е и 16-е "поколения" дракона. Дракон представляет собой своеобразную гирлянду в форме двухсторонней правой спирали, состоящую из подобных друг другу спиралевидных звеньев, непрерывно уменьшающихся в размерах от центра к периферии.

Обратите внимание, что такой  достаточно примитивный алгоритм приводит к столь необычной геометрической конструкции. Биологический подтекст, фигурирующий в названии кривой, заставляет задуматься, а не закодирована ли в  генах каким-нибудь схожим простым  образом информация о форме и  размерах существующих в природе  живых организмов? Рассмотренная  выше кривая представляет собой лишь один из многих примеров так называемых Л-систем, изобретенных Аристидом Линденмаером в 1968 г. для моделирования биологического роста. Он показал, что предельная геометрия даже очень простых систем может быть фрактальной.

Вселенная Фурнье

В попытке понять устройство Вселенной учёные неизбежно сталкиваются с понятием фрактала.

Предположим, что нужно  определить, с какой средней плотностью распределены звезды или галактики  в видимой части Вселенной. Представим сферу достаточно большого радиуса  внутри которой находится очень много звезд. Тогда по определению средняя концентрация звезд где — объем сферы. Можно предположить, что если радиус сферы достаточно велик, то концентрация звезд не будет зависеть от этого радиуса.

Опытные данные, однако, говорят  об обратном. С ростом величина п непрерывно уменьшается. И, что интересно, уменьшение происходит примерно по степенному закону , где т. е., намного меньше 3. Это соответствует тому, что число звезд в сфере радиуса растет как N = R^1,23, т. е., гораздо медленнее, чем было бы в случае их однородного распределения в пространстве. Таким образом, распределение звезд и галактик во Вселенной сильно неоднородно. Количественной мерой этой неоднородности может служить отличие показателя степени от 3. Саму же величину можно отождествить с фрактальной размерностью распределения материи во Вселенной.

Действительно, при определении, например, фрактальной размер-ности береговой линии, мы исходили из соотношения где величина была расстоянием между парой точек А и В на береговой линии по прямой, длина была нашим масштабом измерения, а число показывало, сколько раз этот масштаб укладывался вдоль береговой линии между точками А и В. В соответствии с этой формулой фрактальную размерность можно трактовать двояко. С одной стороны, в полном согласии с определением она показывает, как с уменьшением масштаба растет число элементов, с помощью которых можно покрыть некоторую выделенную область на данном фрактале. С другой стороны, она показывает, как то же число растет с увеличением , размера этой области. Причина такой двойственности, очевидно, кроется в том, что у фрактала нет своего собственного масштаба длины, а поскольку число должно быть безразмерным, то показатель степени оказывается одним и тем же как для зависимости так и для зависимости

Как можно себе наглядно представить распределение звезд  в трехмерном пространстве, имеющее  фрактальную размерность  близкую к единице? Разумеется, ответ на этот вопрос сильно неоднозначен. Существует бесконечное количество различных конструкций, имеющих одно и то же значение фрактальной размерности. Одним из классических примеров, который мы сейчас рассмотрим, является вселенная Фурнье, названная так по имени американского журналиста и изобретателя, который предложил ее в 1907 году. Она показана на рисунке.

Каждая точка на этом рисунке  представляет собой одну галактику. Они объединены в скопления радиуса  по 7 галактик в каждом скоплении. На рисунке видны только пять из них: недостающие две расположены симметрично над и под плоскостью рисунка, на прямой, проходящей через центр скопления. В свою очередь, семь таких скоплений аналогичным образом объединены в одно суперскопление радиуса Затем по такому же принципу из семи суперскоплений строится одно суперсуперскопление радиуса , причем и т. д. В результате многократного повторения такого процесса возникает самоподобная фрактальная структура.

Ее фрактальную размерность  легко определить, заметив, что, как  следует из рисунка, в сфере радиуса  содержится в семь раз больше галактик, чем в сфере радиуса , т. е. Решением этого уравнения является степенная функция где D=ln7/ln(R₂/R₁)

У Фурнье , поэтому размерность такой вселенной равняется 1. Как видно, она для этого вовсе не обязательно должна быть прямой или какой-нибудь другой плавной кривой. Более того, она даже не должна быть связной. Меняя отношение легко построить фрактальные вселенные с другими размерностями близкими к единице.

 

Матрицы преобразований координат  точек

Матрицы являются пожалуй самым удобным инструментом описания преобразований координат и присутствуют во всех серьезных API для работы с трехмерной графикой как OpenGl и DirectX. Для свободного понимания данного материала необходимо знать основные сведения о матрицах, особенно правило их перемножения.

Строко-ориентированные и столбцово-ориентированные матрицы (row-major / column-major matrix)

Для устранения дальнейшей всякой путаницы, сразу разъясню, что  существует два способа задания  матриц преобразований: строко-ориентированное и столбцово-ориентированное. В чем их разница? Чтобы добавить новое преобразование N к текущей матрице преобразований M в случае столбцово-ориентированных матриц, мы должны умножить матрицу N на матрицу M справа:

M'=M*N.

Для строко-ориентированных матриц, мы должны умножить матрицу N на матрицу M слева:

M'=N*M.

Для получения новых координат  вершины v(x,y,z,d), нужно умножить строку координат на матрицу преобразований справа для столбцово-ориентированной матрицы:

v'(x',y',z',d') = v(x,y,z,d) * M

Для строко-ориентированных необходимо столбец координат умножить на матрицу преобразований слева

                        x

v'(x',y',z',d') = M  *  y

                        z

                       d

Чтобы перевести матрицу  из строко-ориентированной в столбцо-ориентированную или наоборот, необходимо лишь транспонировать ее.

Базовые преобразования

• сдвиг вдоль координатных осей
• масштабирование
• поворот вокруг координатных осей

Все остальные преобразования реализуются через них.

Примеры базовых  матриц

Ниже приведены строко-ориентированные матрицы преобразований для правосторонней системы координат (ось Х направлена влево, ось Y вверх, ось Z из экрана)

Единичная матрица

Единичная матрица является матрицей тождественного преобразования, т.е. новые координаты равны старым. В таких API как OpenGl она является начальной матрицей преобразования, к которой добавляются все остальные.

 

Сдвиг

                        |1 0 0 a_x|

x'=x+a_x                 |0 1 0 a_y|

y'=y+a_y -> (x',y',z',0)=|0 0 1 a_z| (x,y,z,1)^T

z'=z+a_z                 |0 0 0 1 |

Масштабирование

                       |b_x 0 0 0|

x'=b_xx                 |0 b_y 0 0|

y'=b_yy -> (x',y',z',0)=|0 0 b_z 0|(x,y,z,1)^T

z'=b_zz                 |0 0 0 1 |

Если b равно -1, то получим  зеркальное отражение относительно соответствующей оси.

Поворот вокруг оси Z на угол alfa

                           |cos(alfa) -sin(alfa) 0 0|

x'=xcos(alfa)-ysin(alfa)   |sin(alfa)  cos(alfa) 0 0|

y'=xsin(alfa)+ycos(alfa) ->| 0           0       1 0|(x,y,z,1)^T

z'=z                       | 0           0       0 1|

>

Повороты вокруг оси X и Y

| 1   0         0         0|  |cos(alfa)  0  sin(alfa) 0|

| 0 cos(alfa) -sin(alfa)  0|, |0          1   0        0|

| 0 sin(alfa)  cos(alfa)  0|  |-sin(alfa) 0  cos(alfa) 0|

| 0   0         0         1|  |0          0   0        1|

Знак - у sin соответствует правосторонней системе координат. Также легко запомнить, что cos на главной диагонали.

Примеры прочих матриц

Приведенные ниже матрицы  не являются базовыми и могут разложены на базовые преобразования.

Поворот вокруг вектора

а - уголь поворота

x,y,z нормализованные координаты вектор оси

t=1-cos(a)

|t*x²+cos(a)        t*x*y-sin(a)*z    t*x*z+sin(a)*y   0|

|t*x*y+sin(a)*z     t*y²+cos(a)       t*y*z-sin*x      0|

|t*x*z-sin(a)*y     t*y*z+sin(a)*x    t*z²+cos(a)      0|

| 0                          0                0        1|

Перспективная проекция

Ограничиваем объем видимости  шестью плоскостями:

• r и l правая и левая отсекающие плоскости;
• t и b верхняя и нижняя отсекающие плоскости;
• f и n дальняя и ближняя плоскости.

Проекция происходит на ближнюю  плоскость. Координаты нормализуются.

| 2n/(r-l)  0          (r+l)/(r-l)    0         |

|   0       2n/(t-b)   (t+b)/(t-b)    0         |

|   0       0          -(f+n)/(f-n)   -2fn/(f-n)|

|   0       0          -1             0         |

 

(в OpenGl генерируется функцией glFrustum)

Ортографическая проекция

Ограничиваем объем шестью плоскостями:

• r и l правая и левая отсекающие плоскости;
• t и b верхняя и нижняя отсекающие плоскости;
• f и n дальняя и ближняя плоскости.