Применение алгоритма Space Сolonization при трехмерном моделировании сложных природных объектов

Полный текст

Процесс моделирования ландшафтных сцен разбивается на две части: непосредственная генерация самого ландшафта и наполнение исходного ландшафта объектами сцены (растительность, источники воды, света). Моделирование антропогенных объектов (здания, заборы, транспортные средства) не вызывает значительных трудностей, так как геометрия данных объектов состоит из таких примитивов, как куб, шар, цилиндр, и описывается математическими системами однозначно. Необходимость в ландшафтных сценах возникает в различных пакетах архитектурного моделирования, симуляторов виртуальной реальности, геоинформационных системах [1]. Реалистичность ландшафта напрямую зависит от точности объектов, наполняющих эту сцену. Растительность является основным элементом естественного ландшафта, соответственно, от реалистичности полученных моделей деревьев и кустарников будет зависеть сложность и естественность полученной сцены. В свою очередь, моделирование растительности является нетривиальной задачей. Сложность данной задачи заключается в том, что форма объектов деревьев и кустарников далека от геометрических примитивов и их сочетания, обладает ветвящейся структурой, примитивно которую можно описать фракталами. Модели с такой структурой проектируются в CAD-системах неоднозначно, а также требуют значительных временных затрат. Существуют два основных подхода в ландшафтном моделировании: моделирование всей сцены в специальных пакетах трехмерного моделирования (Vue9.5 xStream, 3dsMAX, XSI, Maya, DAZ 3D Bryce) и моделирование на основе данных наземного лазерного сканирования и аэрофотоснимков. Для каждого из этих подходов можно выделить общие принципы моделирования растительности: математическое моделирование, основанное на правилах и грамматиках; интерактивное моделирование, основанное на шаблонах моделей, и моделирование, основанное на ряде изображений исходного объекта. Альтернативой является моделирование роста дерева на основе L-систем, данный подход изобрел датский математик и биолог Линденмайер [2]. L-система - это грамматика некоторого языка программирования: G = {V, ю, P}, (1) где V - алфавит; ю e V + - аксиомы; P e V х V - правила. В программном виде данное определение L-систем выглядит следующим образом: module Apex(age), Internode(length, radius) MAX_AGE, dr = 10, 0.02 # константы Axiom: Apex(0) # определение аксиом production: # описание правил ветвления Internode(l,r) -> Internode(l,r + dr) Apex(age): if age < MAX_AGE: produce Internode(1,0.05)/(137.5) [+(40)Apex(age+1)] Apex(age+1) Алфавит L-систем состоит из набора стандартных символов. Для каждого типа L-систем расширяется стандартный алфавит, например, для скобочных 86 Вестник СибГАУ. № 1(53). 2014 L-систем вводятся символы «[» и «]». Линденмайер описал несколько типов L-систем. Представим классификацию от простых L-систем к более сложным: скобочные (bracketed), параметрические (parametric), контекстно-зависимые (context-sensitive), стохастические (stochastic) [3]. Основное отличие стохастических L-систем заключается в том, для каждого символа алфавита можно задать не одно правило, а несколько, снабдив каждое из них вероятностью его применения. В этом случае развитие системы уже не будет жестко предопределенным - при подстановках будет происходить случайный выбор одного правила из нескольких в соответствии с заданными вероятностями. Дадим определение стохастическим L-системам: пусть существует только одно x из множества V* для каждого a из множества V; если x может быть выбрано с определенной степенью свободы, система называется стохастической L-системой, обозначаемой в виде четверки G = {V, ю, P, п}. Функция п отображает соответствующего предшественника (a) на вероятностях предшественника (x). Общая сумма всех вероятностей x, присваиваемых конкретному a, должна быть равна 1. Пример программной реализации стохастической системы: from random import * # использование генератора случайных чисел p0 = 0.5 # исходная вероятность Axiom: Apex(0) production: Apex(age): # описание процесса ветвления nproduce Internode(1,0.1)/(180) if uniform() < p0: nproduce[+(20)Apex(age+1)] produce Apex(age+1) Данный подход позволяет описывать развитие кроны дерева и кустарника, а также учитывать практически все параметры дерева, измеряемые в природе; сложность заключается в естественном имитировании различных типов ветвления: моноподиальном, симподи-альном и ложнодихотимическом (тернарном). Для каждого из типов ветвления разработаны собственные L-системы (рис. 1). При моноподиальном типе ветвления один из углов ветвления равен нулю и ясно выражена главная ось. Правила ветвления выглядят следующим образом: p1: A(l,w) : *^ !(w)F(l)[&(a0)B(l*r2,w*wr)]/(d)A(l*r1,w*wr) p2: B(l,w) : *^ !(w)F(l) [-(a2)$C(l*r2,w*wr)]C(l*r1 ,w*wr) p3: C(l,w) : *^ !(w)F(l)[+(a2)$B(l*r2,w*wr)]B(l*r1,w*wr) Другие L-системы охватывают симподиальные структуры, в которых оба дочерних сегмента формируют ненулевой угол с материнским. В этом случае активность главной вершины снижена из-за формирования ствола. Тернарный тип ветвления является по сути симподиальным типом и отличается лишь тем, что отсутствует жесткое предопределение длин ветвей, их развитие описывается вместе с процессом роста растительности. Приведем псевдокод описания тернарного типа ветвления: d1= 94.74 # угол ветвления первой боковой оси d2= 132.63 # угол ветвления второй боковой оси a=18.95 # первоначальный угол ветвления lr=1.109 # коэффициент пропорциональности длины ветви vr=1.732 # коэффициент пропорциональности ширины ветви ю : !(1)F(200)/(45)A p1 : A : *^ !(vr)F(50)[&(a)F(50)A]/(d1) [&(a)F(50)A]/(d2)[&(a)F(50)A] p2 : F(l) : *^ F(l*lr) p3 : !(w) : *^ !(w*vr) Для описания растительности в глобальной системе окружающей среды используется особый тип L-систем, зависимый от окружения в модельном пространстве (environmentally sensitive); в данных системах используются различные запросы получения позиции вектора и его ориентации в пространстве: ? P(x, y, z) - получение текущей позиции; ? H(x, y, z) - вектор направления; ? U(x, y, z) - отклонение вверх вектора направления; ? L(x, y, z) - отклонение влево вектора направления. ЙЮШ :Ше Рис. 1. Модели деревьев L-систем: а - моноподиальный тип ветвления; б - симподиальный тип ветвления; в - тернарный тип ветвления в 87 Математика, механика, информатика Кроме приведенной классификации, существуют и «оригинальные» типы ветвления (ветвления типа пагоды и терминалия), которые также заслуживают внимания, хотя в природе не так часто встречаются, однако именно такие объекты придают ландшафту естественность и разнообразие. Тем не менее, несмотря на успешную работу в создании реалистичных моделей деревьев, по-прежнему остается невозможным точно и естественно моделировать процесс ветвления, физические движения деревьев под воздействием ветра, взаимовлияние растительности и соседствующих объектов [4]. Ветровые модели в основном применяются к стволу и ветвям, листья же в общем случае представляются в виде текстуры и являются неподвижными, что сказывается на их трехмерном представлении. Также при взаимодействии растительности друг с другом и другими антропогенными объектами необходимо учитывать развитие кроны дерева в ограниченном пространстве. Взаимодействие растительности с окружающей средой можно рассматривать с глобальной и локальной точки зрения. Глобальные переменные взаимодействуют с растительностью в целом: температурный режим, газовый состав воздуха, воздействие солнечных лучей на рост (фотосинтез) и пр. К локальным переменным относятся те, которые изменяют лишь отдельные параметры растительности, такие как позиция и ориентация объектов в пространстве [5]. Будем рассматривать лишь локальные переменные окружающей среды, а именно, взаимное влияние соседствующей растительности друг на друга, воздействие ветра, ограниченность пространства растущих деревьев: стены, дома и другие архитектурные комплексы, обрезка деревьев. Рассмотрим иной подход к моделированию растительности - использование алгоритма Space Colonization. Несмотря на то, что изначально данный алгоритм применялся для предсказания движения пешеходов в толпе [6], его можно применить и для моделирования растительности, так как нетрудно заметить, что для определения возможной траектории движения пешехода строится некая ветвящаяся структура, подобная растениям. Основная идея алгоритма Space Colonization заключается в итеративном добавлении новых элементов (ветвей) к существующей геометрической структуре объекта (дерева), сформированного на предыдущих шагах [7]. Данный алгоритм является адаптивным, т. е. процесс роста зависит от следующих параметров: близлежащее присутствие объектов окружающего мира, соседство с другими деревьями. Изначально задается облако из N точек (листьев), их суммарное количество обычно составляет сотни или тысячи, соответственно, на этом этапе можно задать некие препятствия роста дерева, причем точки, выходящие за заданные границы, будут отбрасываться. Также на этом этапе задается начальная точка ствола, с которой начинается итеративное построение «скелета» дерева, на каждой итерации воспроизводится ветвь в направлении ближайшей точки кроны дерева. Пошаговая работа алгоритма представлена на рис. 2. Математическая постановка задачи заключается в следующем: пусть имеется некоторая «корневая» точка v, из этой точки может выходить несколько ветвей, т. е. в окрестности данной точки имеется множество точек S(v), находящихся на расстоянии меньшем, чем dj - параметр, задаваемый пользователем (параметр управления). Если множество S(v) непустое, то новая точка v' присоединяется к общей структуре дерева путем построения сегмента (v, v'). Причем новая точка v' находится на расстоянии D от исходной точки v в направлении средненормированного вектора n по отношению ко всем источникам: D - n - seS(v) | v- v (2) n п (3) llnll s-v (4) Данный процесс заканчивается при прохождении всех точек кроны дерева (N) либо при выполнении заданного пользователем количества итераций. Некоторые узловые точки удаляются, т. е. при построении нового сегмента происходит проверка: все точки, находящиеся на расстоянии dk (dk - killdistance, входной параметр) от точки v', удаляются. Далее для более реалистичной визуализации задается сглаживание ветвей - скругление изгибов-переломов на узловых точках, т. е. аппроксимация по точкам (рис. 2, е). На рис. 2, ж показана объемная визуализация полученного «скелета» с помощью цилиндров разных радиусов. При соединении дочерних ветвей в узловой точке разных радиусов r1 и r2, новый радиус r вычисляется по формуле 5: n n . n /г\ r - r1 + r2 , (5) где n e (2,3). На конечном этапе происходит наложение листвы на существующую структуру ветвей (рис. 2, з). Данный алгоритм позволяет получать реалистичные модели деревьев и кустарников различной формы. Приведем примеры различных исходных облаков точек. Для детального построения геометрии дерева необходимо задавать облака точек, содержащих сотни элементов, также немаловажным является и распределение точек по всей области облака (рис. 3). Полученные результаты, приближенные к реальности, представлены на рис. 4. Одна из наиболее важных особенностей данного алгоритма заключается в возможности моделирования деревьев и кустарников различной формы, связанной с воздействием окружающей среды: освещенность, расположенность моделируемых объектов вдоль стены или иных преград, соседство рядом с другой растительностью (рис. 5). Все представленные выше результаты выполнены с помощью динамического языка программирования Python, все исходные облака точек задавались с помощью генератора случайных чисел, дальнейшим направлением работы является использование данных лазерного сканирования (рис. 6). sv 88 Вестник СибГАУ. № 1(53). 2014 Визуализация написанного скрипта выполнена средствами графического редактора Blender (открытое программное обеспечение). Основная геометрия дерева - процесс ветвления - осуществлялся по алгоритму Space Colonization, стохастические L-системы использовались на конечных итерациях (дорисовка мелких ветвей) перед наложением текстур на объект. Построенные в соответствии с изложенным методом 3Б-ландшафтные сцены являются реалистичными и не требуют больших вычислительных затрат. б а в Рис. 2. Последовательность шагов алгоритма SpaceColonization: а - задание облака точек кроны дерева; б - прорисовка общего предварительного «скелета» ветвей; в - инициализация почек; г, д - прореживание точек ветвей; е - скругление ветвей; ж - объемное (цилиндрическое) моделирование ветвей; з - наложение лиственной массы е з б а в г Рис. 3. Результаты первых этапов работы алгоритма SpaceColonization для различных облаков точек: а, б - облако точек с элементами, сосредоточенными ближе к границе / центральной оси; в, г - концентрация элементов облака в верхних и нижних частях соответственно 89 Математика, механика, информатика Рис. 6. Моделирование дерева в Blender с использованием Python API

Об авторах

Анастасия Александровна Ткачева

Сибирский государственный аэрокосмический университет имени академика М. Ф. Решетнева

Email: tkacheva@mail.sibsau
аспирант кафедры ИВТ

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

Дополнительные файлы