понедельник, 14 января 2008 г.

Растительность. Часть 1. Генерация.



Первоначально планировался один общий текст. Но т.к. получилось "слишком много букв" разбил на 3 части

Посмотрел я на ландшафт, что у меня получатся, и решил что чего-то не хватает. Было принято решение добавить немного растительности.

Генерация
Этап генрация довольно интересен. Ибо просто нагенерить случайные значения нельзя. Объясню почему.

Предположим, у нас есть регион 3х2 метра, который нужно засеять травой.


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

Например вот


или вот


Очевидно, что такая "генерация" неприемлима, ибо абсолютно непредсказуема. Нужен алгоритм, при котором "засеивание" должно быть относительно равномерным. Как это сделать?

Для начала надо ввести коэффициент, описывающий плотность засеивания травы. Обозначим его как d( от density ).

d - количество объектов, расположенных на 1кв.м. поверхности

Очевидно что увеличивая d, увеличивается плотность засеивания. Получаем довольно "прозрачное" управление.

Нужно ввести ещё одно понятие - регион. Это область, содержащая 1 объект( куст ). С его помощью можно будет добиться равномерного засеивания.

u = 1 / ( sqrt( d ) )

u - Сторона региона.

Получаем:


Осталось только добавить немного "хаоса" =) Рандомно генерируем точку в пределах каждого региона.

Получаем:


Как раз то что и было нужно.

Рассаживаем на ландшафте
Область мы сгенерировали. Но этого мало, нужно ещё "рассадить" всё это дело на ландшафте. Тут, на самом деле, всё просто. Всё что нужно - это определить высоту( "y" координату ) точки ландшафта, где будет располагаться куст. Интереса ради я попробовал решить это проблему "в лоб". "Пробивал" лучом каждый треугольник патчей при помощи функции D3DXIntersectTri. Получилось ну очень медленно. Код был спешно стёрт и предан забвению.

Есть более оптимальный вариант. Ландшафт у нас строиться из карты высот? Да. Значит сетка регулярная? Да. Значит зная x и z координату( то что мы сгенерировали ) можно высчитать смещение и точно определить нужный треугольник? Да. Ну а 2 треугольника( квад ) проверить на пересечение побыстрее будет, чем несколько тысяч.

Если интересно как сделано у меня - посмотреть можно здесь [link] или здесь [link].

Вот что у нас получилось в итоге:


Маска
Маска нужна - это очевидно. Ибо квадратная область засеяной травы смотриться несколько... странно. Я использовал TGA формат( 8 бит на пиксель, без компрессии ) для этих целей. Какой точке на маске соответствует "травинка" считаем:

mask_offset_x =
( ( grass_pos.x - grass_region_bbox.min.x ) /
grass_region_bbox_width ) * mask_width );
mask_offset_y =
( ( grass_pos.z - grass_region_bbox.min.z ) /
grass_region_bbox_height ) * mask_height );
_Winnie C++ Colorizer


Дальше я считал так - если цвет пикселя менее 64, то сажать в этом месте мы ничего не будем. Если же значение > 64, то цвет будет использовать для масштабирования. Считаем как

scale_factor = ( mask_pixel - 64 ) / ( 255 - 64 );

Итого
После всех этих сложных телодвижения можно наконец-то построить матрицу каждой травинки. Для "естественности" добавим немного рандомайза в финальные вычисления. Итого мы получаем:
float scale = math::lerp(
scale_min, scale_max, ( float )rand() / ( float )RAND_MAX );
scale *= scale_factor;

matrix mat_tr = math::matrix_translation(
mat_tr, pos );
matrix mat_sc = math::matrix_scaling(
mat_sc, vec3( 1.f, 1.f, 1.f ) * scale );
matrix mat_rot = math::matrix_rotation_y(
mat_rot, ( float )rand() / ( float )RAND_MAX );

matrix mat_res = mat_sc * mat_rot * mat_tr;
_Winnie C++ Colorizer


Всё, генерация закончена. Следующий этап - отрисовка( будет завтра ).

4 комментария:

Sergey Semenov комментирует...

Без обид, но на фразах:
..."засеивание" должно быть относительно равномерным...
...Рандомно генерируем точку в пределах каждого региона…
...нужно ещё "рассадить" всё это дело на ландшафте...

У меня появился образ трудолюбивого накодельца, планирующего посевы конопли =)

А если серьезно, очень интересно, спасиб!

Timai комментирует...

2Сергей Семёнов

А я всё гадал, когда ассоциации с коноплёй пойдут =)

Анонимный комментирует...

Довольно примитивный способ расстановки. На самом деле гораздо бОльших результатов можно добиться если использовать маску как карту вероятностей. Масштабирование травы смысле не имеет вовсе...

Так же данный алгоритм не решает проблему со спавном двух травинок в (почти) одной точке - два соседних квада могут заиметь травинки на общем ребре.

Как бегиннерский алгоритм - хорошо, но надо идти дальше. Сразу :)

Timai комментирует...

бОльших результатов можно добиться если использовать маску как карту вероятностей

Интересно о каких "бОльших" результатах может идти речь? Мой пример растанавливает точки на ландшафте. И всё. Что тут можно сделать больше?

Так же данный алгоритм не решает проблему со спавном двух травинок в (почти) одной точке - два соседних квада могут заиметь травинки на общем ребре.
Я и не ставил своей целью решение этой пробелемы. Как и другие мелочи. Ибо они _очень легко_ решаемы. К примеру эта надуманная проблема решается 3-мя строчками кода. Если это так сложно для Вас - сочувствую.

Как бегиннерский алгоритм - хорошо, но надо идти дальше. Сразу :)
А каков смысл публиковать дотошно подробные и оптимизированные решения? Я описываю общую схему. "Дорабатывать напильником" каждый будет под под свои нужды, в зависимости от своих потребностей.

В первую очередь я пишу для себя. Ибо это хорошо развивает способность объяснять.
Во вторую очередь - для людей кому это может быть интересно.

"Небегиннерам" которые сходу знают как сделать лучше смысла читать данные выкладки нет. Они и так "всё знают лучше меня".