Лекция 01. Преобразования в двухмерном пространстве 23 icon

Лекция 01. Преобразования в двухмерном пространстве 23


2 чел. помогло.
Смотрите также:
Лекция Преобразования Лоренца и следствия из них § Преобразование Лоренца для координат...
Лекция Удаление невидимых линий и поверхностей (продолжение)...
Лекция Удаление невидимых линий и поверхностей (продолжение)...
Реферат на тему «Геометрические преобразования»...
Лекция III
Лекция организована в рамках междисциплинарного семинара "Образы прошлого в пространстве...
Как передаётся информация в пространстве...
Лекция 10
Метрия 2005, том 42, n 3, стр. 64-69 Журнал переводится на английский язык. Optoelectronics...
Учебное пособие для подготовки к егэ по математике Раздел 4...
«рождение нового человечества» в городе хмельницком, 8-10 апреля 2011 г...
Лекция №12



Загрузка...
скачать

277248.doc Степулёнок Денис Олегович Герасимова Т.В. стр. 15.10.2011


Что такое компьютерная графика. 2

Виды обработки графической информации 3

Основные понятия КГ 4

Графические данные 4

Формы растра 5

Геометрическое моделирование 5

Математические основы компьютерной графики 7

Геометрические определения базовых типов 7

Декартова (Картезианская) система координат 9

Базовая косоугольная система координат 10

Полярная система координат 10

Цилиндрические координаты 11

Сферические системы координат 11

Косоугольная система координат 11

Симметрия 12

Многогранники 13

Платоновы тела 13

Тетраэдр 14

Октаэдр 15

Додекаэдр 15

Свойства Платоновых тел 16

Фрактал и фрактальная геометрия 16

Свойства фракталов 18

Виды фракталов. 18

Геометрический фрактал 18

Алгебраический фрактал 19

Стохастические фракталы 20

Способы построения фракталов 20

L-система 20

Система итерирующих функций IFC 22

Часть I / Лекция 01. Преобразования в двухмерном пространстве 23

Преобразование точки 23

Преобразование фигуры 23

Однородные координаты. Операции в них 24

Общий вид преобразования 25

Операция смещения 25

Операция масштабирования 25

Общее полное масштабирование 25

Поворот на угол  25

Отображение или зеркалирование 25

Поворот фигуры вокруг произвольной точки (m, n) на произвольный угол  25

Центральное проецирование (перспектива) 25

Примечания 25

Нахождение точки пересечения двух линий (пример) 25


ВВЕДЕНИЕ

История развития компьютерной графики. Визуальное представление информации. Знаковая, координатная и видео информация. Анализ, синтез и обработка изображений. Геометрическое моделирование и геометрические абстракции. Виртуальная реальность

^

Что такое компьютерная графика.



КГ – это область относящаяся к информатике. В сферу интересов этой науки входят аспекты связанные с формированием изображения.

ЭВМ используется для: формирования, преобразования и вывода изображения (графических объектов)



Существует 3 направления:

- компьютерное зрение КЗ (Computer Vision - CV)

- обработка изображения ОИ (Computer Image Processing - IP)

- компьютерная графика КГ (Computer Graphics. - CG)


^ Компьютерное зрение – у нас есть изображение, хотим получить описание, т.е. занимаемся анализом образов



Обработка изображения - есть изображение, а мы производим его обработку

Компьютерная графика – имеется описание, хотим получить отображение (синтез изображения)

^

Виды обработки графической информации


Изображение в системах МГ может рассматриваться как единое целое или как составное из отдельных функционально независимых элементов. Любое составное изображение имеет некоторое структурное описание. Формирование изображения из элементов, находящихся в графической базе данных. Назовем синтезом изображения. Задача синтеза изображения является основной задачей МГ. Эта задача может решаться по разомкнутому или замкнутому циклу.



Рис. Схема организации процессов в графической системе

Задачи синтеза изображения:

  • построение модели объекта и генерация изображения,

  • преобразование модели и изображения,

  • идентификация объекта и получение требуемой информации.

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

Обработка – процесс, который используется для улучшения качества изображения (приведения изображения к виду удобному для его последующего анализа и синтеза)

Задачи обработки:·

  • повышение качества изображения,

  • оценка изображения - определение формы, местоположения, размеров и других параметров требуемых объектов,

  • · распознавание образов - выделение и классификация свойств объектов (обработка аэрокосмических снимков, ввод чертежей, системы навигации, обнаружения и наведения).

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

БД – база данных структурированного описания изображения
^

Основные понятия КГ


К основным понятиям машинной графики относятся:

- принципы описания и представления их в памяти ЭВМ,

- алгоритмы формирования и преобразования изображения ,

- принципы построения технических средств ввода вывода изображения ,

- принципы организации систем машинной графики их программного обеспечения .
^

Графические данные


Реальный или синтезированный объект представляется в компьютере как модель, а выводится как изображение. Модель – абстрактное описание формы объекта (вершины) и атрибутов (цветов), которые могут использоваться для нахождения всех точек объекта, соответствующих пикселям в области вывода.

Изображение – просто двумерный массив пикселей. Под изображением будем понимать совокупность данных, хранящихся в ЭВМ и обеспечивающих формирование картинки на изображающей поверхности некоторого устройства графического вывода. Существует множество описаний изображений.

:

Рис. Виды описания графической информации.

Изображения может содержать информацию о математических, в частности геометрических объектах (точка, прямая, кривая, плоскость и др.). Математическое описание этих объектов производится в некоторой системе координат, не всегда совпадающей с системой координат изображающей поверхности. Описание таких объектов носит название координатной информации.

Объектом графического вывода может являться и условный знак, принадлежащей используемого в графической системе алфавиту. Знаками могут являться алфавитно-цифровые символы, стрелки, маркеры и др.. В ЭВМ хранится коды знаков. Последовательность кодов знаков называется знаковой или символьной информацией. Если знак или набор знаков связаны с определенной ориентацией или координатами, то такая информация называется координатно-символьной.

Реальные изображения вводятся в ЭВМ с помощью специальных устройств ввода, обеспечивающих их дискретизацию и квантование. Полученные в результате данные часто называют видеоинформацией. Видеоинформация представляется массивом квантованных отчетов на некотором дискретном поле.
^

Формы растра


Расположение отсчетов на дискретное поле соответствует узлам равномерной решетки, то говорят о растре, на котором задано цифровое представление изображения. Наиболее распространенным является прямоугольный растр, который составлен из примыкающих друг к другу прямоугольников заданного размера – элементов растра (рис. ). В качестве элемента растра могут быть элементы другой формы (рис. и рис.), соответствующие следующим требованиям:

  • Все фигуры должны быть одинаковыми

  • Должны полностью покрывать плоскость без наезжания и дырок







Значение отсчета, соответствующее элементу растра, может рассматриваться как третья координата изображения. В МГ эта координата носит название цветности, так как кодирует цветовой тон, насыщенность и яркость.
^

Геометрическое моделирование


Целью геометрического моделирования (ГМ) является представление объектов

Чаще всего объекты реальные

Требования к ГМ :

- Любая модель, которую можно сконструировать не должна противоречить реальному объекту (непротиворечивость модели);

- Допустимость конструирования модели целиком (мощность модели);

- Возможность вычисления дополнительных параметров (объема, веса и т.п.) (вычисляемость модели).

Компактность модели – количество информации необходимое чтобы эту модель использовать в различном алгоритме.

Характер открытости – возможность применения модели в других системах.

Тема 1. Математические основы компьютерной графики


Ортогональные системы координат. Понятие точки, линии, поверхности. Многомерные пространства и проекции. Классические Платоновы тела. Симметрия многогранников. Аффинная и проективная геометрия.

^

Математические основы компьютерной графики



Способы представления базовых геометрических объектов (типов), преобразования

Представление геометрических объектов не зависит от конкретного времени.

Представления о геометрической сущности

Способы описания этой сущности в конкретной системе координат

Способы описания математической абстракции

Базируется на понятии аффинной геометрии и проекционного пространства.

Базируется на 3-х типах: скаляры, точки и вектора. (носят геометрическую сущность)
^

Геометрические определения базовых типов


Роль фундамента в геометрии выполняет точка.

«Точка – то, что не имеет частей» (Евклид)



Точка в - положение этой точки.

Для описания положения точки можно использовать:

Векторное (линейное) пространство

Аффинное пространство

Евклидово пространство

^ Скаляр – вещественное число, которое задают для описания геометрических объектов.

Вектор – некоторая направленная линия

3D вектор

  • Имеет длину и направление V = [vx, vy, vz]

  • Длина задается ||V|| =

  • V•U = [vx, vy, vz] • [ux, uy, uz] = vxux + vyuy + vzuz = ||V|| ||U|| cos ß
    результата – скалярное значение

  • V x U = [vyuz - vzuy, vzux - vxuz, vxuy - vyux]

V x U = - ( U x V)

Результата – вектор, направление которого зависти от координатной системы и порядка векторов, но всегда перпендикулярно двум остальным векторам

^ Л
t > 1

инейное пространство
создают скаляры и векторы.

П
t = 1
араметрическое вычисление линий.


Даны две точки P1 = (x1, y1, z1), P2 = (x2, y2, z2)

x
P2


t = 0

= x
1 + t (x2 - x1)

y
P1

t < 0

= y
1 + t (y2 - y1)

z = z1 + t (z2 - z1)


Даны точка P1 и вектор V = [vx, vy, vz]

x = x1 + t vx, y = y1 + t vy , z = z1 + t vz

Компактная форма

L = P1 + t[P2 - P1] или L = P1 + Vt

^ Вычисление плоскостей

Дано: Ax + By + Cz + D = 0, тогда [ A,B,C ] вектор нормали.


Даны две точки Р1 и Р2 на плоскости, вектор [ Р1 - Р2] на плоскости и

[A,B, C] • [ P2 - P1] = (Ax2 + By2 +Cz2) - (Ax1 + B y1 + Cz1)

= ( - D ) - ( - D )

= 0

^ Альтернативная форма: A'x + B'y + C'z +D' = 0

где A' = A/d, B' = B/d, C' = C/d, D' = D/d и d =

Расстояние между точкой и плоскостью задается через : A'x + B'y + C'z +D'


^ Получение уравнения плоскости

Для получения уравнения плоскости заданы три точки: P1, P2, P3

[ P3 - P1] x [ P2 - P1] = N, ортогональный вектор,

_ Дана точка P = (x,y,z):

N • [P - P1] = 0 если P расположена на плоскости.

_


Или дана точка (x,y,z) на плоскости и

вектор нормали N тогда N • [x,y,z] = -D


Пример

Найдите плоскость, содержащую точки (0,0,0), (1,2,3) и (4,5,6).

[1,2,3] x [4,5,6] = [-3,6,-3] - вектор нормали

-3x + 6y - 3z + D = 0

Замещающая точка (0,0,0): 0+0+0+D = 0

D=0

Уравнение плоскости: -3x + 6y - 3z = 0

^ Аффинное пространство – добавляется понятие точки.

Евклидово пространство – вводят понятие расстояние.


Системы координат: Положение точки в пространстве может быть описано в виде комбинации некоторых линейно-независимых векторов . Если ввести скаляры , то можно описать вектор (положение точки) так:



^

Декартова (Картезианская) система координат


Структура взаимосвязей между системами координат




Базовая косоугольная система координат


Координаты определяются осями ( х – ось абсцисс, у - ось ординат)

Расстояние определяется проекциями
^

Полярная система координат







Точка О – полюс, - полярный угол , r – полярное расстояние.

M(r, )

Соответственно


^

Цилиндрические координаты




Есть некая плоскость Z проекция на точку M

Сферические системы координат






угол - полярное расстояние

угол - долгота

Соответственно

1.

2.

3.


^

Косоугольная система координат






Декартова система координат

M(x,y,z)




Полярная

M()



Цилиндрическая

M()



Сферическая с коор.

M()




0 в середине экрана у Картезианской системе координат.

(.) Все наши представления в векторах, в виде матрицы

Симметрия


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

  • Симметрия отображения (зеркальная)



Поворота на определённый угол. Элемент симметрии – ось поворота (поворотная ось симметрии).

Элементарный угол – угол, на который нужно повернуть фигуру, чтобы она совместилась сама с собой. Элементарный угол поворота определяет порядок оси симметрии. Например, если угол = 90 градусов, то ось 4-ого порядка.

  • Симметрия переноса (повторяемость через определённое расстояние) – симметрия параллельного переноса. Повторение в пространстве фигуры с помощью переноса на определённый вектор.

Симметрия переноса + зеркальная симметрия = калейдоскоп

  • Винтовая симметрия (перемещение и поворот по определённой траектории). Пример: листья на деревьях

Многогранники


Многогранники – тела, ограниченные определенным количеством поверхностей – граней. Грани – многоугольники.
^

Платоновы тела


Платоновы тела – правильные многогранники, выпуклые, обладают максимальной трёхмерной плотностью упаковки. Каждый правильный многогранник может быть описан сферой или вписан в сферу.

^ Платоновыми телами называются правильные однородные выпуклые многогранники, то есть выпуклые многогранники, все грани и углы которых равны, причем грани - правильные многоугольники. К каждой вершине правильного многогранника сходится одно и то же число рёбер. Все двугранные углы при рёбрах и все многогранные углы при вершинах правильного многоугольника равны.

Платоновы тела - трехмерный аналог плоских правильных многоугольников.

Существует лишь пять выпуклых правильных многогранников - тетраэдр, октаэдр и икосаэдр с треугольными гранями, куб (гексаэдр) с квадратными гранями и додекаэдр с пятиугольными гранями. Доказательство этого факта известно уже более двух тысяч лет; этим доказательством и изучением пяти правильных тел завершаются «Начала» Евклида.

Также существует семейство тел, родственных платоновым - это полуправильные выпуклые многогранники, или архимедовы тела. У них все многогранные углы равны, все грани - правильные многоугольники, но нескольких различных типов.



ТЕТРАЭДР





ОКТАЭДР



^ КУБ (ГЕКСАЭДР)





ДОДЕКАЭДР



ИКОСАЭДР










Число сторон у грани

Число рёбер у вершины

Число граней

Число вершин

Число ребер

Тетраэдр

3
треугольники

3

4

4

6

Куб (Гексаэдр)

4

квадраты

3

6

8

12

Октаэдр

3

треугольники

4

8

6

12

Додекаэдр

5

пятиугольники

3

12

20

30

Икосаэдр

3

треугольники

5

20

12

30

Вершины октаэдра находятся в центрах граней куба

Тетраэдр


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


Октаэдр


Рассмотрите внимательно рис. 18.2. Как видно, две вершины октаэдра расположены по обе стороны квадрата. Предположим, что стороны квадрата 1-2-3-4 имеют единичную длину. Точка 7 расположена в центре квадрата и также является центром октаэдра, а точка 8 находится посередине ребра 4-1. Поскольку точка 5 лежит на перпендикуляре в точке 7, то все, что нам надо знать, это расстояние h между этими двумя точками. Здесь можно использовать тот факт, что все вершины правильного многоугольника находятся на одинаковом расстоянии от центра. Следовательно, треугольник 1-5-7 является равнобедренным треугольником. Следовательно, весь октаэдр состоит из последовательности равнобедренных треугольников.


Додекаэдр


Эта фигура имеет 12 граней, 30 ребер, 20 вершин. Каждая из 12 граней является правильным пентагоном (пятиугольником). Додекаэдр вполне вписывается в куб (рис. 18.3), и это его свойство можно использовать для конструирования.


^
Свойства Платоновых тел

Платоновы тела обладают симметрией многогранников (на примере куба):

Центр симметрии – у куба присутствует

Плоскости симметрии

- 3 плоскости симметрии перпендикулярные рёбра в их середине

- 6 плоскостей симметрии, проходящих через противоположные рёбра

3. Оси симметрии

- 3 оси симметрии 4-ого порядка (проходят через центры граней)

- 6 осей симметрии 2-ого порядка (проходят через середины противоположных рёбер)

- 4 оси зеркальной симметрии (через противоположные вершины)

(!) В кубе существуют все виды симметрии.




^

Фрактал и фрактальная геометрия


Понятия фрактал и фрактальная геометрия, появившиеся в конце 70-х, с середины 80-х прочно вошли в обиход математиков и программистов. Слово фрактал образовано от латинских слов fractus - дробный и frangere - ломать, что отражает суть фрактала, как "изломанного", нерегулярного множества. Оно было предложено Бенуа Мандельбротом в 1975 году для обозначения нерегулярных, но самоподобных структур, которыми он занимался. Рождение фрактальной геометрии принято связывать с выходом в 1977 году книги Мандельброта `The Fractal Geometry of Nature'. В его работах использованы научные результаты других ученых, работавших в период 1875-1925 годов в той же области (Пуанкаре, Фату, Жюлиа, Кантор, Хаусдорф). Но только в наше время удалось объединить их работы в единую систему.

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

Одним из основных свойств фракталов является самоподобие. Определение фрактала, данное Мандельбротом, звучит так: "Фракталом называется структура, состоящая из частей, которые в каком-то смысле подобны целому".

Один из методов генерации фракталов – использование комплексного преобразования. Комплексные числа имеют вид

Z = X + iY, где X и Y действительные числа, а i2=-1.

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

Естественно, что при этом требуется – нелинейная зависимость между результатом и начальным значением, то есть динамический закон

X N+1 = f(XN) должен быть сложнее, чем X N+1 = KXN

^ Кривая ПИАНО

Рекурсивна, в каждой части отрезка применяется

Процедура

Фрактал – это вызов подобного себе.


Пока с целое – ничего особенного

с вещественное – множество Монденброта
^

Свойства фракталов




  • Компактно и ограничено.

  • Самоподобие – основное свойство фрактала

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

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

Линия не самопересекается.
^

Виды фракталов.


  • Геометрический

  • Алгебраический

  • Система итерируемых функций - IFS

  • Стохастический

Геометрический фрактал


Геометрический – фрактал получаемый путем простых геометрических преобразований. Во всех детерминированных фракталах самоподобие проявляется на всех уровнях. Это означает, что независимо от того, на сколько вы приближаетесь к фракталу, вы увидите все тот же узор.

Детерминированный фрактал образуется в процессе, называемом итерацией, которая применяет основной рисунок к итератору, после чего применяет его к результату и так далее.

Кривая Пиано,





Рис. Снежинка Коха.

Рассмотрим один из таких фрактальных объектов - триадную кривую Кох [3]. Построение кривой начинается с отрезка единичной длины (рис.) - это 0-е поколение кривой Кох. Далее каждое звено (в нулевом поколении один отрезок) заменяется на образующий элемент, обозначенный на рис.1 через n=1. В результате такой замены получается следующее поколение кривой Кох. В 1-ом поколении - это кривая из четырех прямолинейных звеньев, каждое длиной по 1/3.



Рис. представлены пять поколений кривой Коха

Для получения 3-го поколения проделываются те же действия - каждое звено заменяется на уменьшенный образующий элемент. Итак, для получения каждого последующего поколения, все звенья предыдущего поколения необходимо заменить уменьшенным образующим элементом. Кривая n-го поколения при любом конечном n называется предфракталом. На рис. представлены пять поколений кривой
^

Алгебраический фрактал


Алгебраический – строятся на основе некоторых алгебраических формул.

Это самая крупная группа фракталов. Получают их с помощью нелинейных процессов в n-мерных пространствах. Наиболее изучены двухмерные процессы. Интерпретируя нелинейный итерационный процесс, как дискретную динамическую систему, можно пользоватся терминологией теории этих систем: фазовый портрет, установившийся процесс, аттрактор и т.д.

Известно, что нелинейные динамические системы обладают несолькими устойчивыми состояниями. То состояние, в котором оказалась динамическая система после некоторого числа итераций, зависит от ее начального состояния. Поэтому каждое устойчивое состояние (или как говорят - аттрактор) обладает некоторой областью начальных состояний, из которых система обязательно попадет в рассматриваемые конечные состояния. Таким образом фазовое пространство системы разбивается на области притяжения аттракторов. Если фазовым является двухмерное пространство, то окрашивая области притяжения различными цветами, можно получить цветовой фазовый портрет этой системы (итерационного процесса). Меняя алгоритм выбора цвета, можно получить сложные фрактальные картины с причудливыми многоцветными узорами. Неожиданностью для математиков стала возможность с помощью примитивных алгоритмов порождать очень сложные нетривиальные структуры.

В качестве примера рассмотрим множество Мандельброта (см. pис. и рис.). Алгоритм его построения достаточно прост и основан на простом итеративном выражении:

Z[i+1] = Z[i] * Z[i] + C,

где Zi и C - комплексные переменные. Итерации выполняются для каждой стартовой точки C прямоугольной или квадратной области - подмножестве комплексной плоскости. Итерационный процесс продолжается до тех пор, пока Z[i] не выйдет за пределы окружности радиуса 2, центр которой лежит в точке (0,0), (это означает, что аттрактор динамической системы находится в бесконечности), или после достаточно большого числа итераций (например 200-500) Z[i] сойдется к какой-нибудь точке окружности. В зависимости от количества итераций, в течении которых Z[i] оставалась внутри окружности, можно установить цвет точки C (если Z[i] остается внутри окружности в течение достаточно большого количества итераций, итерационный процесс прекращается и эта точка растра окрашивается в черный цвет).
^

Стохастические фракталы


Еще одним известным классом фракталов являются стохастические фракталы, которые получаются в том случае, если в итерационном процессе случайным образом менять какие-либо его параметры. При этом получаются объекты очень похожие на природные - несимметричные деревья, изрезанные береговые линии и т.д. Двумерные стохастические фракталы используются при моделировании рельефа местности и поверхности моря [2].

Существуют и другие классификации фракталов, например деление фракталов на детерминированные (алгебраические и геометрические) и недетерминированные (стохастические).
^

Способы построения фракталов

L-система


L-система (от имени Lindenmayer) - это грамматика некоторого языка (достаточно простого), которая описывает инициатор и преобразование, выполняемое над ним, при помощи средств, аналогичных средствам языка Лого (аксиоматическое описание простейших геометрических фигур и допустимых преобразований на плоскости и в пространстве).

L-системы часто называются ещё и системами черепашьей графики. Черепашья графика - это такой способ рисования линий на экране компьютера. Он состоит в том, что программист как бы управляет движением как бы черепашки. Черепашка, ползая по экрану, оставляет за собой след. При этом цель программиста – управлять черепашкой так, чтобы черепашка нарисовала нужную линию. Команды управления черепашкой просты: сделать шаг вперёд (обозначается F), повернуть направо (обозначается +), повернуть налево (обозначается -), сделать шаг вперёд без перерисовки (прыжок, обозначается B). Вот из этих команд и составляется сценарий построения линии – строка команд. Величина одного шага и угол одного поворота при движении черепашки всегда остаются постоянными и задаются предварительно.

Например, ^ F++F++F это равносторонний треугольник, если угол поворота равен pi/3, а F+F+F+F – это квадрат, если угол поворота равен pi/2 .

Построение L-системы происходит в три этапа.

  1. Сначала создаётся сценарий поведения черепашки.

  2. Потом подсчитывается размер линии, которая получится, если запустить этот сценарий на исполнение. Линия как бы рисуется в уме, а потом смотрится её размер. На основе этого размера подправляется масштаб, чтобы вся линия уместилась на экране.

  3. На экран запускается черепашка, которая рисует линию.

Фракталы – самоподобные фигуры, значит, и сценарии у них должны быть самоподобные.

Вот как это делается.

  • Берётся начальная фигура (называется - аксиома), например, F++F++F с углом pi/3.

  • Задаётся правило замены F (называется правило newF) , например, new F = F-F++F-F ;

  • в имеющейся фигуре все F заменяются на newF

У деревьев есть ветки. Тут имеющимся набором команд не обойдёшься. Приходится вводить ещё пару команд: начало ветви (обозначается [ ), конец ветви (обозначается ] ). Что бедная черепашка должна делать по этим командам? В начале ветви она должна запомнить своё состояние (положение и направление взгляда), а вот когда ей встретится соответствующий конец ветви, она должна вернуться в то положение, которое запомнила.

Вот, например, данные для построения куста.


axiom = F


newF = -F+F+[+F-F-]-[-F+F+F]


turn = pi / 8


Для трёх шагов получим такую картинку ->



Если вы хотите строить объёмные деревья и другие фракталы, то вам придётся ввести ещё пару команд – поворотов из плоскости (предлагаю символы >, <). Короче, + - это повороты в плоскости XY, а >, < это повороты в плоскости XZ.

Вот, например, данные для построения 3d-кустика.


axiom = F

newF = -F+F[>F+FF+F][+FF][-F>F+F
turn = pi / 8


Для двух шагов получите вот такое деревце --->


^

Система итерирующих функций IFC



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

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

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

2. Следующее звено строится с использованием всех возможных преобразований, а именно: сжатие в три раза, поворот на - 60о и параллельный перенос на 1/3 по оси X.

3. Третье звено строится аналогично второму: сжатие в три раза, поворот на 60о, параллельный перенос на 2/3 по оси X.

4. Последнее звено: сжатие в три раза, параллельный перенос на 2/3 по оси X.

В дальнейшем правила построения кривой Кох будем называть IFS дл кривой Кох.
^

Часть I / Лекция 01. Преобразования в двухмерном пространстве


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

Преобразование точки


Точка на плоскости представляется двумя координатами: |x y|. Матрица преобразования точки выглядит так:


Ниже показано преобразование точки через квадратную матрицу; здесь xn = xa + yc и yn = xb + yd — новые координаты точки после преобразования:

^

Преобразование фигуры


Если представить фигуру как совокупность точек, то можно провести и ее преобразование. В следующем примере задано четыре точки: A(0, 0), B(1, 0), C(1, 1), D(0, 1), каждая из которых после преобразования переходит соответственно в A*(0, 0), B*(a, b), C*(a + c, b + d), D*(c, d):


Геометрически это соответствует деформации фигуры:



При этом площадь новой фигуры равна площади старой фигуры, умноженной на детерминант матрицы преобразования: S2 = S1 * |ad - bc|.



^

Однородные координаты. Операции в них


Любая система координат, в которой представление точки в двухмерном (трехмерном) пространстве задается при помощи трех (четырех) координат (Р1, Р2, Р3(, Р4)), называется системой однородных координат. Вообще, для n-мерного пространства число однородных координат должно быть на единицу больше: n + 1.

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

Геометрическая интерпретация на случай двухмерного пространства: введение третьей координаты, равной единице, можно трактовать как переход в трехмерное пространство, в котором разрешено работать только в плоскости z = 1. Следует представлять себе, что экран компьютера (картинная плоскость, плоскость изображения) находится в плоскости z = 1:



В случае выхода рисунка за сечение z = 1 рисунок возвращается принудительно в данное сечение — для того, чтобы были возможны последующие операции:



Такая операция называется нормализацией однородных координат:




^

Общий вид преобразования



Операция смещения




Матрица преобразования содержит в себе константы m и n, под действием которых точка смещается наm единиц вдоль оси x и на n единиц — вдоль оси y:


^

Операция масштабирования




За счет коэффициентов a и d матрицы преобразования происходит увеличение (или уменьшение) значения координат точки (x, y) в a и d раз по осям x и y соответственно:


^

Общее полное масштабирование




В данном случае при s < 1 будет происходить увеличение значения координат точки (x, y) в s раз; при s > 1 мы получим обратный эффект — уменьшение значения координат (x, y) в s раз.
^

Поворот на угол 




Здесь  — угол, на который требуется повернуть точку (x, y). Обратите внимание: поворот происходит относительно точки (0, 0) декартовой системы координат против часовой стрелки!

А теперь вот вам маленькое задание. Попробуйте повернуть треугольник на угол  = 90o, координаты точек можете взять любые. Наш вариант представлен здесь.
^

Отображение или зеркалирование


  • Зеркалирование относительно прямой y = x (рис. 1.6a):


  • Зеркалирование относительно прямой x = 0 (рис. 1.6b):


  • Зеркалирование относительно прямой y = 0 (рис. 1.6c):


  • Зеркалирование относительно начала координат (рис. 1.6d):



^

Поворот фигуры вокруг произвольной точки (m, n) на произвольный угол 


Чтобы провести любое сложное преобразование, необходимо разложить его на базовые операции. Поворот фигуры вокруг произвольной точки (m, n) на произвольный угол  состоит из трех базовых операций: 1) перенос фигуры на вектор A(-m, -n) для совмещения точки (m, n) с началом координат; 2) поворот фигуры на угол ; 3) перенос фигуры на вектор A'(m, n) для возвращения ее в исходное положение. Так как фигуру можно представить набором точек, то операции 1) - 3) можно выполнять последовательно для каждой точки. Покажем это на примере.

Пусть мы хотим повернуть треугольник с координатами A(x, y), B(x1, y1), C(x2, y2) вокруг точки D(m, n) на угол . Пусть P-s — матрица переноса точки на вектор A(-m, -n), V — матрица поворота на угол , Ps — матрица переноса точки на вектор A'(m, n).

Итак, мы имеем все данные, необходимые для проведения сложного преобразования первой точки A(x, y):


Точно такие же преобразования необходимо провести для оставшихся двух точек треугольника, подставляя соответствующие их координаты взамен x и y (последовательность операций см. на рис. 1.7). Таким образом, сложная операция разбивается на простейшие и задается произведением соответствующих матриц преобразования, причем порядок, в котором перемножаются матрицы, существенно определяет результат.


^

Центральное проецирование (перспектива)




px + qy + 1 = H — плоскость.

Примечания


  1. В общем случае от перемены матриц местами результат меняется.

  2. Матрицы операций, идущие подряд, можно перемножать раздельно, главное — не менять их порядок следования (см. примечание 1).

  3. Линии при описанных выше (аффинных) преобразованиях переходят в линии. Поэтому обычно производится пересчет только координат вершин фигуры, а после этого соответствующие вершины в результирующей фигуре соединяются, как и в исходной фигуре.
^

Нахождение точки пересечения двух линий (пример)


Пусть имеются две линии: x + y = 1, 2x - 3y = 0, необходимо найти точку их пересечения. Решение может быть найдено с использованием матриц. Перенесем все члены уравнений в левую часть: x + y - 1 = 0, 2x - 3y - 0 = 0; запишем коэффициенты первого уравнения в первый столбец матрицы, второго уравнения — во второй:


Условие, при котором пересекаются две прямые, выглядит следующим образом:
|x y 1| * M = |0 0 1|

Для нахождения ответа необходимо обе части предыдущего уравнения домножить справа на обратную матрицу M-1 (при перемножении M и M-1 получается единичная матрица E):
|x y 1| * E = |0 0 1| * M-1



|x y 1| = |3/5 2/5 1|

Ответ: точка пересечения прямых: x = 3/5, y = 2/5.




Скачать 283,68 Kb.
оставить комментарий
Дата17.10.2011
Размер283,68 Kb.
ТипЛекция, Образовательные материалы
Добавить документ в свой блог или на сайт

плохо
  1
средне
  1
отлично
  4
Ваша оценка:
Разместите кнопку на своём сайте или блоге:
rudocs.exdat.com

Загрузка...
База данных защищена авторским правом ©exdat 2000-2017
При копировании материала укажите ссылку
обратиться к администрации
Анализ
Справочники
Сценарии
Рефераты
Курсовые работы
Авторефераты
Программы
Методички
Документы
Понятия

опубликовать
Загрузка...
Документы

Рейтинг@Mail.ru
наверх