АЛГОРИТМЫ ПРОЦЕДУРНОЙ ГЕНЕРАЦИИ РАСТЕНИЙ

АННОТАЦИЯ

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

Ключевые слова: алгоритм, процедурная генерация, природные объекты, PCG.

Введение

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

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

Рисунок 1. Пример шума Перлина

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

Алгоритм процедурного роста растений с учётом конкуренции начинается с задания начальных «посевных» точек, которые могут распределяться случайно или по карте шума. Затем в ходе итеративного моделирования каждое растение либо стареет, либо растёт, причём шансы на выживание зависят от его возраста[4].

Рисунок 2. Модель конкуренции растения за ресурсы

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

Рисунок 3. Этапы функционирования алгоритма на основе модели роста

Если в процессе развития растения оказываются слишком близко друг к другу, включается стадия самопрореживания: конкурирующие особи «сражаются» за свет, воду и питательные вещества, после чего слабейшая из них удаляется[5]. Для оценки конкуренции используется поле соседства (FON), определяющее радиус поиска конкурентов. Существует два основных способа распределения ресурсов между растениями: симметричный, когда соседи равного размера получают их поровну, и асимметричный, при котором более сильный конкурент получает больший «кусок» экологического пирога[6].

Формула симметричного способа распределения ресурсов:

Формула ассиметричного способа распределения ресурсов:

Все этапы — рост, размножение и прореживание — повторяются до достижения заданного возраста[7] или требуемой плотности посадки[8]. Достоинством такого метода является естественное распределение растений и формирование участков без растительности[9], однако к его недостаткам относятся значительная вычислительная нагрузка, длительное время генерации и невозможность мгновенной подгонки плотности «на лету», что делает его более подходящим для офлайн-утилит[10], таких как Procedural Foliage Tool, а не для динамической генерации в реальном времени.

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

Список литературы:

1. Jonas Freiknecht and Wolfgang Effelsberg. A survey on the procedural generation of virtual worlds. Multimodal Technologies and Interaction, 1(4):27, 2017.
2. N. Chomsky. Three models for the description of language. IRE Transactions on Information Theory, 2(3):113–124, September 1956. ISSN 0096-1000. doi: 10.1109/TIT.1956.1056813.
3. Timm Dapper. Practical procedural modeling of plants. http://www.td-grafik. de/artic/talk20030122/overview.html, 2003. Accessed on 2017-10-02.
4. Oliver Deussen, Pat Hanrahan, Bernd Lintermann, Radom´ır Mˇech, Matt Pharr, and Przemyslaw Prusinkiewicz. Realistic modeling and rendering of plant ecosystems. In Proceedings of the 25th Annual Conference on Computer Graphics and Interactive Techniques, SIGGRAPH ’98, pages 275–286, New York, NY, USA, 1998. ACM. ISBN 0-89791-999-8. doi: 10.1145/280814.280898. URL http://doi.acm.org/10.1145/280814.280898.
5. P Prusinkiewicz, J Hanan, M Hammel, R Mech, PM Room, WR Remphrey, et al. Plants to ecosystems: Advances in computational life sciences. Colingwood (Australia): CSIRO, pages 1–134, 1997.
6. Radom´ır Mˇech and Przemyslaw Prusinkiewicz. Visual models of plants interacting with their environment. In Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, pages 397–410. ACM, 1996.
7. Kristin A Sorrensen-Cothern, E David Ford, and Douglas G Sprugel. A model of competition incorporating plasticity through modular foliage and crown development. Ecological Monographs, 63(3):277–304, 1993.
8. Xuejin Chen, Boris Neubert, Ying-Qing Xu, Oliver Deussen, and Sing Bing Kang. Sketch-based tree modeling using markov random field. ACM Trans. Graph., 27 (5):109:1–109:9, December 2008. ISSN 0730-0301. doi: 10.1145/1409060.1409062. URL http://doi.acm.org/10.1145/1409060.1409062.
9. Makoto Okabe, Shigeru Owada, and Takeo Igarash. Interactive design of botanical trees using freehand sketches and example-based editing. In Computer Graphics Forum, volume 24, pages 487–496. Wiley Online Library, 2005.
10. Alex Reche-Martinez, Ignacio Martin, and George Drettakis. Volumetric reconstruction and interactive rendering of trees from photographs. In ACM transactions on graphics (ToG), volume 23, pages 720–727. ACM, 2004.