Latex formulas

воскресенье, 26 февраля 2012 г.

Ъ-3d сценка

Таким же методом, как и при создании ландшафта создал 3d сценку - куб и над ним срезанный цилиндр

Размер мира - 32x32x128 (решил не заморачиваться над чем-то большим). Данные о высотах хранятся в массиве 32x32x128 послойно. Массив заполняется значениями -1, далее если нужно узнать высоты слоев с координатой (x,y) делаем так: idx = x*32*32 + y*32; Далее hei[idx] - нижняя координата 1 слоя, hei[idx+1] - верхняя 1-го, потом 2 слой итд, пока не найдем -1.

На экране рисуются уже не столбцы от низа экрана, а отрезки, соответствующие высоте слоя. Вся картинка оказывается нарисованной как бы "лентами", параллельными экрану.

Самое сложное в методе (и поэтому я не уверен, что он единcтвенно верный) - обнаружение перекрытий на экране. Вспомните, в ландшафте мы сравнивали экранную координату sy c величиной из массива, корректируя массив по необходимости. Тут же приходится считать перекрытия отрезков, что несколько сложнее. К тому же быстрота подсчета перекрытий зависит от числа связных множеств (отрезков), объединение которых составляет множество точек, уже нарисованных на экране.

Тем не менее такая простая сцена рендерится быстрее, чем методом рисования back-to-front.

Вот код:

Открыть спойлер
Автор: на 06:47 0 коммент.

пятница, 17 февраля 2012 г.

Разная всячина

Нашел тут способ "эмулировать" 5-ую степень свободы без затрат на вычисления.

Так как это при проецировании используются некоторые хитрости, этот способ не даст нам настоящей проекции, но он оказался очень хорош, когда мы "ходим" по карте невысоко и не заглядываем слишком низко. Способ предельно прост: мы просто меняем угол, под которым лучи идут к карте высот. Соответственно, уравнение для координаты z точки на луче примет вид:



Увеличивая или уменьшая k и получим пятую степень свободы. Когда плоскость экрана и карта высот параллеьлны, точка на карте должна соответствовать точке на экране, но у нас всё до сих пор рисуется столбцами. Вот почему этот способ не действует всегда. Но меня удивило, что он вообще действует (и неплохо) ;)

Ещё я дорисовал к своей демке кружочек в середину экрана, который уменьшается при пересечении с более дальними объектами. Коэффициент уменьшения нахожу так:



dc - расстояние от камеры до точки пересечения, которе ищем в цикле по d

dc = d, если

1) sx = scw/2 - координата на экране x равна половине ширины экрана
2) sy <= sch/2 - текущая экранная координата y такая, что столбец будет нарисован выше, чем на полэкрана
3) sy_old>sch/2 - а предыдущая - ниже
4) maxh[sx]>sy - гарантия того, что столбец точно будет нарисован (y-буффер обновляется ниже по коду). О том, что такое maxh смотри вторую статью.

Может быть такое, что на всей длине луч не пересекся ни с одной точкой, которая отображается в середине экрана. Это проверить так: после цикла по d проверить условия:

1) sx = scw/2
2) max[sx] > sch/2 (теперь y-буффер обновлен и если самый высокий пиксел так и не достиг половины экрана, то прицел не рисуем)

Для надежности d лучше определять как среднее арифметическое между d в текущем цикле и в предыдущем (когда d соответствует sy_old)

Зная, какой sx = scw/2 соответствует луч, можно восстановить координаты на карте высот x,y пересечения луча с ландшафтом (об этом не буду, см. статью 2).

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


void addheight (int *map, int x, int y, int add)
{
    if (add > 5)
    {
        int bin1 = mapw*(maph-1);
        int bin2 = maph-1;
        int idx = ((x*mapw) & bin1) + (y&bin2);
        map[idx] += add/50;
        addheight (map, x-1, y, add-10);
        addheight (map, x+1, y, add-10);
        addheight (map, x, y-1, add-10);
        addheight (map, x, y+1, add-10);
    }
    
}


При add = 100 получаются мелкие зазубринки, таким образом мы можем менять ландшафт прямо в демке - вот неоспоримое достоинство вокселей!

Код, за чистотой которого я совсем перестал следить: testgrad.bmp - ч/б картинка "прицела" 32x32

Открыть спойлер
Автор: на 09:44 0 коммент.

понедельник, 13 февраля 2012 г.

Приделеал Ч/Б текстурки с тенями

Решил к своей программе для генерации теней приделать возможность сохранять результат в indexed bmp (с помощью SDL_SaveBMP), а рендереру - возможность загружать bmp из текстуры. Вышло всё вот так:
Явно видны тени во впадинах (источник света высоко над пиком)

Сама карта теней была размыта в gimp'е (писать гауссовское размытие непосредственно в генератор - лень) + смешена с отрендеренными в gimp'е же облаками. Вышло следующее:


Явно видна недоработка: карта несимметрична (это именно ошибка генератора теней). В чём дело пока не понял. Вообще, эта фигня мне уже изрядно поднадоела, пойду спрашивать на геймдев, как можно наиболее оптимально разблокировать ещё одну степень свободы)
Автор: на 09:07 0 коммент.

суббота, 11 февраля 2012 г.

Фильтруй базар!


Добился почти идеального качества картинки, правда за счет резкого падения производительности (правда на моём компьютере програмка бегает очень даже шустро, если включить оптимизацию в clang).

В этой программе я буду использовать карту высот 512x512 и такую же "текстурку" (на самом деле простой массив, генерируемый на ходу, но SDL также отлично работает и с файлами.)

Вспомним, теперь, что координаты в пространстве мы представляли числами типа int (что и понятно, ведь из координат строится индекс массива - целое число!).

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

Как найти эту функцию? Тут мы будем пользоваться техникой билинейной фильтрации, основанной на билинейной интерполяции.

Допустим, мы знаем, что в координатах x = x0, y = y0 f(x,y) = z0, где x0, y0 целые числа.
Аналогично:
f(x1,y0) = z1
f(x0,y1) = z2
f(x1,y1) = z3 (все координаты - целые)

Определим z = f(x,y) так:





Как определить высоту ландшафта в точках (2.32, 3.54)? Возьмем x0=2, y0=3, x1=3, y1=4 как можно ближе к нашим координатам и воспользуемся данными формулами.

В этом и заключается принцип билинейной фильтрации - взять 4 соседних пиксела, где значение высоты известно и интерполировать по ним.

Формулы можно упростить. Как? Смотри википедию. Я лишь приведу готовый результат + картинки.

Картинка до (картинка после - в начале статьи):


Недостаток таков: при передвижении по миру высота пика будет меняться + картинка выглядит блочной. Это связано с тем, что семплы на карте высот берутся не все, а через некоторый шаг.
Избавиться от этого просто: уменьшить шаг хода луча. Тогда получим идеальную картинку, лишенную всякой блочности (но потеряем в производительности):



Код программы:

Открыть спойлер
Автор: на 08:58 0 коммент.

пятница, 10 февраля 2012 г.

Немного о тенях от точечного источника

Ничего не нашел лучше, чем посчитать карту теней статически, а потом загружать её вместе с уровнем.

Подсчет производить будем "в лоб": для каждого источника с координатами (x0, y0, z0) и для каждой точки на карте (x1, y1, z1) напишем уравнение луча, соединяющего их. Для координаты x:



Для остальных координат уравнение аналогичное. Теперь, двигаясь по лучу от источника освещения к точке на карте (в цикле по t от 0 до 1) делаем проверку

if (map[y][x]>z) установить_тень(x1,y1);


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

Открыть спойлер
Автор: на 06:36 0 коммент.

воскресенье, 5 февраля 2012 г.

Простой ландшафт


Помнится, была такая программка "ландшафты Марса". Попробуем сделать нечто подобное. В этой программе будет использоваться карта высот 64x64 точки. По ней мы будем рендерить на экран картинку, причем камера сможет перемещаться с 4 степенями свободы: 3 поступательным и 1 вращательной. Обычно, в играх используются 5 степеней: те же поступательные (кнопки w-s, a-d + прыжки) и 2 вращательных (посмотреть вверх-вниз, влево-вправо). От обзора вверх-вниз пока откажемся.

Итак, в пространстве наша карта высот и глаз (я связал с ним маленькую плоскость - экран для наглядности) выглядят так, как показано слева (качество ужасное, да).

На рисунке а) видна плоскость экрана и проекция его на карту высот. На б) видна карта высот и система координат, связанная с ней. К тому же с проекцией плоскости экрана тоже свяжем СК y', x' (на рисунке, увы, её нет, но догадаться несложно). Ориентацию экрана в пространстве зададим координатами posx, posy, posz (свяжем с ними любую фиксированную точку экрана) и углом φ между нормалью к экрану и осью x.

Переход от координат, связанных с экраном к тем, что связанны с картой высот таков:


Как мы будем строить картинку? Разобьем наш экран на столбцы и пронумеруем их от 0 до 799 (я строил картинку для разрешения 800x600). Мы будем пускать лучи (на самом деле отрезки;) из точки с координатами posx, posy, posz (координаты глаза) под разными углами β к оси x' и углом α к карте высот. Угол β возьмем пропорциональным номеру столбца.


Зададим ещё одну переменную - d, показывающую проекцию луча на ось x'
Проекция наших лучей на карту высот должна быть такая, как показанно на рисунке (я очень долго экспериментировал, прежде чем получить нужное):

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

Координаты x' и y' будут изменятся по ходу луча так:

К тому же координата z (высота от карты высот до точки на луче) изменится так:


Соответственно, для любой точке на лучах, заданной параметрами d и sx можно получить x и y - координаты проекции этой точки на карту высот, сначала расчитав x' и y', а потом и нужные координаты по формулам поворота.

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

Пусть h - высота поверхности в точке (x, y), а z - высота точки с проекцией (x,y) на некотором фиксированном луче.

Номер строки восстановим так:
sh/2 = 600/2 = 300 - выбранный нами уровень горизонта, k - некий коэффициент пропорциональности (подобрать по вкусу). Что это значит? Чем объект выше, тем отклонение от горизонта больше, а чем он дальше - тем он ближе к горизонту.

Теперь нужно только отрисовать столбик на экране с координатами (sx,syi), где syi изменяется от 0 (низ экрана) до sy.

Но что, если при увеличении d таким образом мы затрем объект, который расположен ближе к нам? Есть два выхода:

1) простой и медленный. Рисовать всё, но начинать с более удаленных объектов (уменьшая d)
2) чуть сложный и куда более быстрый. Рисовать, начиная с близких объектов (увеличивая d), но создать массив, где будут храниться максимальные уже нарисованные sy для данного столбика. Тогда нам нужно будет выполнить проверку

if (sy>maxh[sx])
{
draw();
maxh[sx] = sy;
}
draw() рисует столбец от позиции (sx, maxh[sx]) до (sx, sy). Цвет для рисования можно взять из ещё одного массива 64x64. Ещё одна маленькая хитрость: что, если координата x и y выйдет за пределы 64x64? Ничего страшного, в карте высот, представленной в виде одномерного массива, индекс элемента с координатами (x,y) можно получить так:

int i,x,y;
....
i = ((64*x)&0xfc0 + (y&0x3f));


0xfc0 = 64*64 - 64
0x3f = 64 -1

В двоичной системе эти числа представляются как 111111000000 и 111111, что сразу делает вещи ясными: с помощью этих операций побитового И мы периодически продолжаем карту 64x64 докуда только хватит типа int.


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

Приведу готовую программу. Для компиляции нужна готовая библиотека SDL. Собирать так:

cc -I/path/to/SDL/headers -L/path/to/SDL/library -lm -lSDL -o test test.c


На FPS я её не ограничивал, так что не удивляйтесь, что будет жрать весь процессор.

Код готовой программы
Автор: на 10:33 0 коммент.

Зачем нужны эти записки?

Пишу в принципе для себя, но если материала будет достаточно, кину ссылку на ЛОР(linux.org.ru), где я обычно обитаю. Буду писать здесь про воксельные технологии, которые я сейчас пытаюсь освоить в качестве хобби. В интернете довольно много информации по этой теме, но на русском мало. К тому же я буду стараться писать настолько подробно, насколько могу, так как сам вдоволь поломал голову, чем чего-либо добиться. Информацию по возможности буду добавлять сразу, как только что-то узнаю (а пока я знаю крайне мало).

Полезными ссылками также будут сайт Кена Сильвермана и его движок voxlap, а также этот сайт.

Воксели заинтересовали меня благодаря играм "Outcast" и "Вангеры".

Пользуюсь ОС FreeBSD как основной и Debian Linux. Программы будут написаны на языке C с использованием библиотеки SDL
Автор: на 10:07 0 коммент.
Подписаться на: Сообщения (Atom)