MMO-индустрия: Procedural World: Гладь озёр

Перевод статьи из блога Мигеля Сеперо, в котором он рассказывает о трудностях перевода двумерной карты водоёма в трёхмерный вариант. procworld.blogspot.ru/2014/01/leveling-lakes.html

Этот пост продолжает повествование о воде.

Возможно вы захотите перечитать предыдущую заметку о воде. Мы закончили на создании двумерной булевой карты, где истина означает присутствие в этом месте воды. Неплохо, но нам ещё нужно решить противную проблемку — мы должны создать гладкий уровень воды в озёрах.


Будет проще, если мы взглянем на картинки. Представьте, что это участок, который нам нужно просчитать. Изначально он представляет из себя лишь карту высот и карту моря (в нашем случае это уровень моря):

MMO-индустрия: Procedural World: Гладь озёр

А здесь видно фазу с расположением рек и озёр из прошлого поста. Они отмечены ярко розовым:

MMO-индустрия: Procedural World: Гладь озёр

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

Если бы мы обладали безграничным временем, можно было бы в первой фазе найти озёра, а потом выполнить своего рода повторяющееся выравнивание с помощью смягчения и/или фильтрации. Но у нас есть всего доля секунды на это, поэтому надо действовать по-другому.

Мы испробовали самые разные подходы. Большая часть из них была связана с растеризацией и интерполяцией, в первую очередь от берега к берегу, затем мы обратились за помощью к производным уровня воды. Ничего из этого не работало.

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

Берега образовывали множество мелких квадратиков, но чем дальше от них, тем больше становились участки.

MMO-индустрия: Procedural World: Гладь озёр

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

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

Полный процесс обсчёта достаточно быстр. На картинке ниже рендеринг найденных водоёмов. Он выглядит немного преувеличенным, но, думаю, вы поняли мысль.

MMO-индустрия: Procedural World: Гладь озёр

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

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

14 комментариев

avatar
«если вы в отчаянии, используйте квадродерево и всё будет в порядке»

Просто таки гениально! :)
  • +1
avatar
Квадродерево выручит в любой ситуации ^_^
  • 0
avatar
Нам известно, что береговые линии одного озера находятся на одной высоте. Проблема в том, чтобы вычислить уровень воды между А и В
Похоже, что это ключевая фраза для понимая, что вообще считают в этой статье — проблема в том, что лично я её немного не понял.

Если береговые линии находятся на одной высоте, то уровень воды между А и В = 0, но тогда и все эти вычисления не нужны. Возможно, тут тоже трудности перевода?)

В предыдущей статье это тоже было несколько неоднозначно:

Мне понравилось, что озёра появляются на разных высотах. Также, если вы рассмотрите значения высот на берегах озёр, вы заметите что они не сильно различаются. Это означает, что поверхность озера почти плоская. В реальности часто это не так потому, что озеро на самом деле тоже течёт.

Тоесть, как бы береговые линии всё же не на одной высоте и озеро таки течёт… но с другой стороны тут написано, что всё же не течёт)
  • 0
avatar
Если береговые линии находятся на одной высоте, то уровень воды между А и В = 0, но тогда и все эти вычисления не нужны. Возможно, тут тоже трудности перевода?)
Как объяснить видеокарте где рисовать плоскость? Плоскость определяется тремя точками полигона, но какие точки выбрать? Их множество. Отсюда и проблема.

Тоесть, как бы береговые линии всё же не на одной высоте и озеро таки течёт… но с другой стороны тут написано, что всё же не течёт)
Он не писал «горизонтальное», он писал именно «плоское». Но думаю, что разница действительно настолько невелика, что ей можно пренебречь.
  • +1
avatar
Как объяснить видеокарте где рисовать плоскость? Плоскость определяется тремя точками полигона, но какие точки выбрать? Их множество. Отсюда и проблема.
Даже будь это не воксельный движок, я сомневаюсь, что кто-то уже стал бы делать полигоны размером с те огромные квадраты — обычно это выглядит не слишком хорошо.

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

Он не писал «горизонтальное», он писал именно «плоское». Но думаю, что разница действительно настолько невелика, что ей можно пренебречь.
Если б разницей действительно можно было пренебречь, то достаточно было просто по булевой карте озера набросать колонны воды до уровня берега.
Опять же, будь оно плоским — то это была бы та же банальная интерполяция, о которой идёт речь в статье.

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

В предыдущей статье говорится, что озёра берутся из алгоритма просчёта рек, правда не вдаётся в подробности. Тоесть, проблема возникла скорее из-за приблизительного алгоритма составления самой булевой карты — которая дала в результате довольно кривые по высоте берега у озера. Их просто нельзя было простым способом интерполировать.
  • 0
avatar
Даже будь это не воксельный движок

Это не воксельный движок в том виде, в котором ты подразумеваешь. Пройди по тэгу Voxel Farm, почитай.
  • 0
avatar
И озера не выпуклые. Смотри на верхние (северные) — они плоские. А те, что южнее — просто еще не посчитаны до конца (там нарисованы прямоугольники, по которым идет просчет). Сама по себе задача как раз интересна. Тебе надо найти контур озера, зная его высоту. Проблема в том, что никаких вычислительных мощностей не хватит, чтобы это делать простым образом — перебирая все точки воксельной карты. А быстро это надо делать для того, чтобы при изменении ландшафта менялись и озера: Пробурил сток — оно вытекло (т.е. речь не про то, чтобы один раз просчитать для карты и успокоиться).
  • +2
avatar
Смотри на верхние (северные) — они плоские. А те, что южнее — просто еще не посчитаны до конца (там нарисованы прямоугольники, по которым идет просчет).
Озёра сверху — это на самом деле моря. А нижние действительно не до конца просчитаны, поэтому выглядят такими выпуклыми большими каплями.
А быстро это надо делать для того, чтобы при изменении ландшафта менялись и озера: Пробурил сток — оно вытекло (т.е. речь не про то, чтобы один раз просчитать для карты и успокоиться).
Да, кстати в комментариях он часто говорит о возможности соорудить дамбу например, а потом взорвать её.

Вода же в окончательном варианте, как я понял, будет состоять из т.н. «высоких вокселей», где есть всего несколько верхних слоёв обычных вокселей и один нижний неравномерный слой столбиков. Этот вариант довольно давно применяется и довольно шустрый, нежели если считать всё.
  • 0
avatar
Сама по себе задача как раз интересна. Тебе надо найти контур озера, зная его высоту.

Дык об этом была как раз предыдущая статья, а это уже ведёт речь об алгоритме, использующему рассчитанные контуры озера.
  • 0
avatar
Восстановил в памяти. И да, и нет. В предыдущей заметке он сказал, что «получаются озера», но оговорился, что это получается не точный берег. Всего лишь способ понять, что тут озеро.

С другой стороны ты прав, он строит не горизонтальное озеро, а как в реальной жизни — с течением, т.е. наклонное.
  • 0
avatar
А для воксельного движка полигон обычно сопоставим с размерами вокселя. Собственно и вся прелесть вокселей в том, что графическая часть уже работает по неким единообразным алгоритмам и про неё можно вообще забыть.
Движок этот работает так, что сначала создаётся растровая карта высот, по которой потом восстанавливаются воксели, но они не рендерятся видеокартой напрямую, таких видеокарт просто нет, они преобразуются в полигональный меш. Озёра и реки на данном этапе ещё даже не в виде вокселей, Мигель с командой пока создаёт алгоритм, по которому генерируется карта высот для воды, что и отображено в заметке.

Но если у тебя вопросы технического характера, то лучше, конечно, обратиться к самому Мигелю за разъяснениями. Ссылка на его блог в статье указана. Можно ещё его найти в g+ под тем же именем.
  • +1
avatar
они не рендерятся видеокартой напрямую, таких видеокарт просто нет, они преобразуются в полигональный меш
Единого подхода к рисованию вокселей нет, это да — но разве сейчас актуально экономить полигоны? я к тому, что в этих статьях о графике вообще речь не идёт. Тут решают задачи с физикой — именно в этом первоочередное назначение вокселей.
  • 0
avatar
Актуально экономить на всём, на чём можно сэкономить. Особенно это касается ландшафтов, когда горизонт стараются отдалить от наблюдателя как можно дальше. Шутка ли, рисовать в одной сцене весь Скайрим или даже два.

Именно оптимизацией больше всего и занимается Мигель. Все предыдущие его посты были в основном как раз о графике. А вот например ими придуманный потрясающий метод гладкого перехода между LODами https://www.youtube.com/watch?v=rakmUDn7O_s
  • 0
avatar
Ничего не понял, но очень красиво.
  • 0
Только зарегистрированные и авторизованные пользователи могут оставлять комментарии.