МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования
‹‹КУБАНСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ››
(ФГБОУ ВПО ‹‹КубГУ››)
Кафедра вычислительных технологий
МЕТОДЫ СОЗДАНИЯ НЕПЕРИОДИЧЕСКИХ ИЗОБРАЖЕНИЙ
Краснодар 2014
СОДЕРЖАНИЕ
ВВЕДЕНИЕ. 3
1. ТЕОРИЯ: ОПИСАНИЕ ТЕХНОЛОГИЙ, МЕТОДОВ.. 3
1.1. “Принцип цикады”. 3
1.2. Мозаика Вана. 3
2. ПРИМЕНЕНИЕ МЕТОДОВ. 3
2.1. “Принцип цикады”. 3
2.2. Пример мозаики Вана. 3
2.3. Описание программы. 3
ЗАКЛЮЧЕНИЕ. 3
СПИСОК ИСПОЛЬЗУЕМЫХ ИСТОЧНИКОВ. 3
ПРИЛОЖЕНИ программы генерации мозаики Вана на движке Unity
3D 3
ПРИЛОЖЕНИ программы генерации матрицы для мозаики
Вана 3
ВВЕДЕНИЕ.
Целью данной курсовой работы является изучение и применение различных алгоритмов для создания непериодических изображений (текстуры).
Текстурирование модели – это наложение на модель изображения (текстуры). Если размер текстуры недостаточный, текстуру необходимо повторять до тех пор, пока она не заполнит поверхность модели. Так как “узор” текстуры повторяется многократно, может возникнуть следующая проблема: при простом повторении текстуры много раз, теряется реалистичность изображения. Для избежания этого, необходимо использовать текстуры с большим разрешением (количеством пикселей) и с неповторяющимся рисунком.
При невозможности такую текстуру нарисовать вручную, можно использовать автоматические методы генерации текстуры.
1. ТЕОРИЯ: ОПИСАНИЕ ТЕХНОЛОГИЙ, МЕТОДОВ
1.1. “Принцип цикады”
Цикада - это насекомое из отряда полужесткокрылых. Чем они интересны для генерации непериодической текстуры? Дело в том, что их жизненный цикл составляет 17 (у некоторых видов - 11, 7 или 13) лет. Это помогает цикадам сохранять популяцию. Их естественные враги имеют короткий цикл (2-6 лет) между пиком и спадом популяции. В случае, если бы жизненный цикл цикад был другим (например, 8 лет), то хищники, имеющие жизненный цикл в 2 и 4 года, могли бы полакомиться цикадами в период пика популяции, что для цикад не очень хорошо.
Но у цикад цикл - 17 лет (или 13). Что общего между этими числами? Они простые, то есть наименьшее общее кратное (НОК) для такого числа и любого другого будет равно их произведению. То есть, если пик популяции для цикад и хищника выпал на один год, то следующее такое событие произойдет очень нескоро - цикады успеют восстановить свою популяцию.
“Принцип цикады” в генерации непериодического изображения - это применение простых чисел. Если просто взять несколько блоков (маленьких изображений, из которых будем генерировать большое) и последовательно соединить их, то натуральности в таком изображении не будет.
Если же использовать простые числа и наложение слоев, то получим псевдослучайность. Хотя она и не настоящая, но глазу будет тяжело это заметить, так как узора будет повторяться через большие промежутки.
Этот принцип подходит для веб-разработки при генерации фоновых изображений или динамических изображений.
1.2. Мозаика Вана
Мозаика Вана - одна из непериодических мозаик, которую придумал китайский математик Хао Ван в 1961 году. Элементы этой мозаики можно представить в виде прямоугольников с разноцветными гранями.
Для начала опишем метод, как собирать обычную мозаику. Необходимо, чтобы края соседних элементов мозаики сочетались – плавно перетекали друг в друга.
Основная задача при построении мозаики Вана - создание атласа: сетки граней, которые будут сочетаться между собой. Ведь при соединении двух элементов мозаики появляются швы - резкие переходы узора.
Атлас - это маленькая картинка, созданная из исходной, представляющая собой сетку из условных линий (граней) разных цветов. Два квадрата из атласа сочетаются, если соприкасаются одноцветными гранями.
При генерации текстуры нужно просто брать случайный квадрат из тех, что сочетаются с текущим.
Размер атласа для полного набора плиток очень быстро растёт с количеством вариаций граней. Расчёт ведётся по следующей формуле: N2*M2, где N — количество горизонтальных граней, M — количество вертикальных граней.
2. ПРИМЕНЕНИЕ МЕТОДОВ.
2.1. “Принцип цикады”.
Для того, чтобы создать псевдослучайную последовательность, создадим несколько слоев, которые будем накладывать друг на друга. При этом слой будет заполнен (кроме первого) лишь частично. Тогда в этих промежутках будут проступать предыдущие слои.
При этом сам слой будет состоять из блоков, число которым - одно из последовательности простых чисел.
Пример 1:
В качестве блоков возьмем буквы “а”, “б”, “в”.
Если их совмещать подряд, то получим “абвабвабвабв...”, где хорошо прослеживается “узор” из сочетания “абв”.
Если же применять “принцип цикады”, то будет следующее:
слой 1: “аааааааааааааааааааааааааааааааааааааааа” – спложной слой.
слой 2: “.б..б..б..б.“, то есть узор (паттерн) будет “.б.“ - простое число 3
слой 3: “.в...в.” – паттерн с интервалом - простое число 7.
При наложении этих слоев получаем: “аваабвабвабавб”. В такой последовательности тяжело найти шаблон - повторяющийся участок (потому что его нет в приведенном участке последовательности). Шаблон возникнет лишь через 1х3х7 = 21 символ, что увидеть будет сложно. При добавлении четвертого слоя с числом 11 получим, что повторение будет через 1х3х7х11 = 231 символ.
Пример 2:
Возьмем изображение, из него возьмем в качестве трех слоев части изображения. Создадим слои с повторение элементов через 3 и 7 блоков. Первый слой - сплошной. Остальные следуют паттернам:
Слой 2 – “.п.”
Слой 3 – “.п…п.”, где точка означает пустое пространство (альфа-канал), “п” – элемент картинки.
Для пояснения смотрите рисунки 1 – 5.
рисунок 1 - исходное изображение
рисунок 2 - слой 1
рисунок 3 - слой 2
рисунок 4 - слой 3
Рисунок 5 - результат
2.2. Пример мозаики Вана.
Возьмем картинку и разобьём ее на равные блоки (квадраты).
Далее выберем наиболее подходящие границы (блоки) для создания атласа. Никакого правила, как именно выбирать границы, нет.
Нарисуем схему атласа – каждый цвет означает свою блок.
В соответствии с этим атласом наложим на картинку сетку из блоков.
Вручную обработаем полученный атлас, чтобы скрыть резкие переходы (швы). К сожалению, алгоритма для скрытия швов нет – так как программа не в состоянии определить резкий переход.
 |  |  |
Пример.
 |  |
А Б В
Г Д
Е
рисунок 6 – А – исходное изображение
рисунок 7 – Б – схема атласа
рисунок 8 – В – наложение схемы на изображение
рисунок 9 – Г – сетка из блоков
рисунок 10 – Д – атлас
рисунок 11 – Е – результат генерации
2.3. Описание программы.
Программа генерации мозаики Вана была разработана на языке C#, так как движок Unity 3D работает с этим языком. Движок был выбран для облегчения работы с графикой.
Программа содержит класс, наследуемый от стандартного для движка класса. Он включает стандартные (для движка) методы работы с изображением и псевдослучайными последовательностями (рандом).
Программа генерации матрицы для мозаики Вана была разработана на языке C++, так как были использованы части другой, ранее написанной мною программы.
Программа содержит класс для более удобной работы с матрицами (двумерными массивами) и класс генерации матрицы для мозаики Вана.
Загружаем созданный атлас в программу. Так как он разбит (условно) на одинаковые квадраты, то можно выделить отдельные блоки (тайлы). Первый тайл выбираем случайно. Остальные тайлы ряда выбираем случайно, с тем условием, что он сочетается с предыдущим.
Второй и последующие ряды выбираем так же как и первый, с той лишь разницей, что учитываем еще и тайл из предыдущего ряда того же столбца.
Таким образом укладываем плитку по самого конца, заполняя весь рисунок.
ЗАКЛЮЧЕНИЕ.
В данной работе разработано программное приложение, которое позволяет автоматически генерировать текстуру (непериодическое изображение).
Генерация изображений позволит создавать текстуры большого объема “на лету”, либо позволит не рисовать огромные текстуры вручную, а ограничиться рисованием атласа.
“Принцип цикады” применим для веб-разработки, мозаика Вана – для объемных клиенстких приложений.
СПИСОК ИСПОЛЬЗУЕМЫХ ИСТОЧНИКОВ.
1. Kari J. A small aperiodic set of Wang tiles //Discrete Mathematics, - 1996 - 259–264 с.
2. Alex Walker The Cicada Principle and Why It Matters to Web Designers [электронный ресурс] URL: http://www. /the-cicada-principle-and-why-it-matters-to-web-designers [дата обращения: 22 мая 2014]
3. Chris Creating Tile-Based Texture Maps for Games [электронный ресурс] URL: http://www. /forum/view-thread/55091 [дата обращения: 21 мая 2014]
4. “Бесконечные неповторяющиеся текстуры с помощью мозаики Вана” [электронный ресурс] URL: http://habrahabr. ru/post/185760/ [дата обращения: 21 мая 2014]
ПРИЛОЖЕНИЕ А.
“Код программы генерации мозаики Вана на движке Unity
3D”
Компиляция и запуск возможно только при использовании движка Unity 3D.
using System. Collections. Generic;
using UnityEngine;
public class WangTiles : MonoBehaviour {
public Texture2D squares;
private Texture2D textureSource;
private Texture2D texture;
private List<int> lastRowUp;
private List<int> currentRowUp;
private int lastTileRight;
private System. Random rnd;
void Awake(){
rnd = new System. Random();
lastRowUp = new List<int>();
currentRowUp = new List<int>();
lastTileRight = 1;
textureSource = squares;
texture = new Texture2D(1024, 1024){ filterMode = FilterMode. Point };
for (var i = 0; i < texture. width/32; i++){
lastRowUp. Add(1);
}
RandomizeTexture();
}
void RandomizeTexture(){
for (var y = 0; y < texture. height / 32; y++){
for (var x = 0; x < texture. width / 32; x++){
texture. SetPixels(x * 32, y * 32, 32, 32, WangTile(lastTileRight, lastRowUp[x]));
}
lastRowUp. Clear();
lastRowUp. AddRange(currentRowUp);
currentRowUp. Clear();
}
texture. Apply();
renderer. material. mainTexture = texture;
}
Color[] WangTile(int left, int down){
int i, j;
if (left == 1)
i = RandomChoice(new List<int>() { 0, 1 });
else
i = RandomChoice(new List<int> { 2, 3 });
if (down == 1)
j = RandomChoice(new List<int>() { 0, 1 });
else
j = RandomChoice(new List<int> { 2, 3 });
if (i == 0 || i == 3)
lastTileRight = 1;
if (i == 1 || i == 2)
lastTileRight = 2;
if (j == 0 || j == 3)
currentRowUp. Add(1);
if (j == 1 || j == 2)
currentRowUp. Add(2);
return textureSource. GetPixels(i*32, j*32, 32, 32);
}
Temp RandomChoice<Temp>(List<Temp> obj){
return obj[rnd. Next(0, obj. Count)];
}
void Update(){
if(Input. GetKey("space"))
RandomizeTexture();
}
}
ПРИЛОЖЕНИЕ Б.
“Код программы генерации матрицы для мозаики
Вана”
