|
|
Главная
Статьи
Ссылки
Скачать
Скриншоты
Юмор
Почитать
Tools
Проекты
Обо мне
Гостевая
|
Одним из довольно простых и эффективных средств для моделирования растений являются предложенные в 1968 году биологом Аристидом Линденмайером так называемые L-системы.
Основной идеей его подхода было моделирование растений при помощи развития довольно простого объекта. При этом развитии происходит постоянное замещение простых частей на более сложные, к частям которых применяется тот же самый процесс замещения и так до любой желаемой степени детализации.
Для этого крайне удачным оказался аппарат формальных грамматик. В простейшем случае (так называемых D0L-систем, т.е. детерминированных, контекстно-независимых L-систем) система описывается следующими параметрами:
Рассмотрим следующую D0L систему:
В качестве алфавита возьмем всего два символа 'a' и 'b'. В качестве начальной строки возьмем символ 'b'. Правила замены определим следующим образом:
a -> ab
b -> a
Согласно этим правилам символ 'a' заменяется на строку 'ab', а символ 'b' - на символ 'a'.
При этом мы считаем, что все замены в строке происходят одновременно, т.е. одна замена не влияет на возможность применения других правил на этом шаге.
Рассмотрим каким образом будет происходить развитие этой системы для шагов 1..6.
Для того, чтобы при помощи L-систем получать модели растений, следует приписать отдельным символам некоторый геометрический смысл, позволяющий сопоставлять строке символов геометрический объект.
Традиционно для этого используется так называемая черепашья графика (turtle graphics) - некоторое устройство (черепашка), которое может перемещаться вперед на заданное расстояние и поворачивать вправо и влево на заданный угол. При этом перемещение черепашки может происходить как с рисованием линии, так и без рисования.
Обычно используются следующая интерпретация символов:
Рассмотрим следующую D0L-систему:
Начальное состояние 'F+F+F+F'.
Правило: 'F' -> 'F+F-F-FF+F+F-F'
В начальном состоянии данная система дает квадрат (см. рис 1. ).
Рис 1. "Острова Коха".
В результате последовательного применения правила подстановки мы получаем замкнутые кривые, похожие на "Остров Коха".
К сожалению описанным выше способом можно строить только простая ломаные (замкнутые или нет). Для построения древовидных (иерархических) структур, столь часто встречающихся среди растений, этого набора символов недостаточно.
Однако оказывается, что для поддержки древовидных структур достаточно добавить в алфавит всего два символа (вместе с их интерпретациями) '[' и ']'.
Символ '[' вызывает сохранение текущего состояния черепашки (положения, ориентации, величины перемещения и т.п.) на стеке. Символ ']' вызывает восстановление состояния системы со стека.
Следующий пример L-системы (системы, использующие символы [] называют bracketed) демонстрирует достаточность введения этих символов для построения древовидных систем.
Начальное состояние: 'F'.
Правило: 'F' -> 'F[-F]F[+F][F]'.
Рис 2. Простейшая древовидная система.
Еще несколько различных двухмерных систем:
Начальное состояние: 'X'
Правило: 'X' -> 'F[++X]-F[--X]X'
Начальное состояние: 'F'.
Правило: 'F' -> 'F[+F]F[-F]F'
Начальное состояние: 'F'.
Правило: 'F' -> 'FF-[-F+F+F]+[+F-F-F]'
Если необходимо получить трехмерный объект, то вместо двухмерной черепашки удобнее использовать "самолетик", ориентация которого задается тремя углами - крен (roll), наклон (pitch) и поворот (yaw).
Рис 3. Интерпретация углов.
Символы 'F', 'f', '+', '-', '[' и ']' сохраняют смысл, но также вводятся еще четыре символа, соответствующие двум добавленным степеням свободы:
Также полезным оказывается ввести еще один символ '!', определив его действие как смену знака поворота, т.е. он меняет между собой действия символов '+' и '-', '&' и '^' и '<' и '>'.
Ниже приводятся два примера простейших трехмерных L-систем.
Начальное состояние: 'F'.
Правило: 'F' -> 'F[-F]<[F]>[+F][F]'
Начальное состояние: 'AB'
Правила:
'A' -> '[F[+FCA][-FCA]]'
'B' -> '[F[>FCB][<FCB]]'
Все рассмотренные ранее L-системы являются детерминированными, т.е. их развитие однозначно определяется начальным состоянием и правилами.
В то же время в растениях часто имеет место элемент случайности, т.е. развитие системы не является жестко предопределенным, существуют варианты.
Для моделирования этого можно использовать так называемые стохастические L-системы. Их отличием от детерминированных L-систем заключается в том, что для каждого символа алфавита можно задать не одно правило, а несколько, снабдив каждое из них вероятности его применения.
В этом случае развитие системы уже не будет жестко предопределенным - при подстановках будет происходить случайный выбор одного правила из нескольких с соответствии с заданными вероятностями.
Одним из довольно простых примеров стохастических L-систем является следующая:
Начальная строка: 'FAF'.
Правила:
'A' -> '[+FBF] (0.8)
'A' -> F (0.2)
'B' -> '[-FBF] (0.6)
'A' -> F (0.4)
Для реализации описанных классов L-систем можно использовать приведенные ниже классы.
#ifdef _WIN32
#pragmawarning (disable:4786)
#endif
#include "Vector3D.h"
#include "Matrix3D.h"
#include "BoundingBox.h"
#include <string>
#include <stack>
#include <map>
using namespace std;
class LSystem
{
struct State
{
Vector3D pos;
Vector3D dir;
Vector3D angles;
float angle;
float invert;
};
map <char, string> rules;
string initialString;
float angle;
float distScale;
float angleScale;
string currentString;
BoundingBox bounds;
public:
LSystem ();
void setInitialString ( const char * str )
{
initialString = str;
}
void addRule ( char symbol, const char * rule )
{
rules [symbol] = rule;
}
void setAngle ( float newAngle )
{
angle = newAngle;
}
const string& getCurrentString () const
{
return currentString;
}
void setDistScale ( float newScale )
{
distScale = newScale;
}
void setAngleScale ( float scale )
{
angleScale = scale;
}
void interpretString ( const string& str );
void buildSystem ( int numIterations );
void draw ()
{
interpretString ( currentString );
}
const BoundingBox& getBounds () const
{
return bounds;
}
protected:
string oneStep ( const string& in ) const;
Vector3D step ( const State& state ) const
{
return Matrix3D :: rotateZ ( state.angles.z ) * Matrix3D :: rotateY ( state.angles.y ) *
Matrix3D :: rotateX ( state.angles.x ) * state.dir;
}
virtual void drawLine ( const Vector3D& p1, const Vector3D& p2, int level ) const;
virtual void updateState ( State& state, const Vector3D& dir, int level ) const;
};
Метод setInitialString служит для задания начальной строки, по умолчанию она равна "F".
Метод addRule служит для задания правила замены одного символа на строку. Никаких правил по умолчанию нет.
Метод setAngle служит для задания угла, на который происходит поворот по командам '+','-', '&','^','<' и '>'.
Метод getCurrentString возвращает текущую строку, являющуюся результатом выполнения метода buildSystem.
Метод setDistScale позволяет задать параметр, определяющий во сколько раз необходимо изменить величину шага после выполнения команд 'F' и 'f'. За осуществление этого изменения служит виртуальный метод updateState.
По умолчанию этот параметр равен единице. Задание его в диапазоне 0.3-0.7 позволяет контролировать размер веток "нового поколения" по сравнению с родительскими.
Метод setAngleScale позволяет задать параметр, определяющий во сколько раз необходимо изменить угол, на который осуществляется поворот. Изменение происходит по командам 'F' и 'f'. За осуществление этого изменения служит виртуальный метод updateState.
Метод interpretString осуществляет построение изображения по передаваемой строке. Для рисования отрезков используется виртуальный метод drawLine.
Метод buildSystem служит для построения состояния системы, соответствующего начальной строке, правилам и заданному количеству итераций.
void LSystem :: buildSystem ( int numIterations )
{
bounds.reset ();
currentString = initialString;
for ( int i = 0; i < numIterations; i++ )
{
currentString = oneStep ( currentString );
printf ( "%s\n", currentString.c_str () );
}
}
Метод draw осуществляет построения отрезка. По умолчанию рисуется простой отрезок средствами OpenGL.
Метод getBounds возвращает ограничивающее тело (ААВВ), соответствующее текущему состоянию системы. Поскольку размеры системы могут сильно изменяться в зависимости от количества итераций и других параметров, то использвоание этого метода позволяет настроить текущее преобразование для получения изображения требуемого размера.
Метод oneStep осуществляет один шаг в развитии данной L-системы. Ниже приводится его реализация.
string LSystem :: oneStep ( const string& in ) const
{
string out;
map <char, string> :: const_iterator it;
for ( int i = 0; i < in.length (); i++ )
{
it = rules.find ( in [i] );
if ( it != rules.end () )
out += it -> second;
else
out += in [i];
}
return out;
}
Метод step возвращает вектор, на который необходимо произвести перемещение на данном шаге.
Метод drawLine осуществляет построение отрезка по начальной и конечной точкам. Он может быть переопределен для получения изображения с учетом цветов, толщины веток и других параметров.
Метод updateState служит для коррекции состояния системы после команд 'F' и 'f'. Его реализация приводится ниже.
void LSystem :: updateState ( State& state, const Vector3D& dir, int level ) const
{
state.pos += dir;
state.dir *= distScale;
state.angle *= angleScale;
}
Для работы со стохастическими L-системами можно слегка модифицировать описанный выше класс. В результате мы приходим к следующему классу:
#ifdef _WIN32
#pragma warning (disable:4786)
#endif
#include "Vector3D.h"
#include "Matrix3D.h"
#include "BoundingBox.h"
#include <string>
#include <stack>
#include <map>
#include <list>
using namespace std;
class StochasticLSystem
{
struct State
{
Vector3D pos;
Vector3D dir;
Vector3D angles;
float angle;
float invert;
};
typedef pair<float,string> Rule;
typedef list<Rule> Rules;
map <char, Rules> rules;
string initialString;
float angle;
float distScale;
float angleScale;
string currentString;
BoundingBox bounds;
public:
StochasticLSystem ();
void setInitialString ( const char * str )
{
initialString = str;
}
void addRule ( char symbol, const char * rule )
{
rules [symbol].push_front ( make_pair ( 1.0f, rule ) );
}
void addRule ( char symbol, const char * rule, float probability )
{
rules [symbol].push_front ( make_pair ( probability, rule ) );
}
void setAngle ( float newAngle )
{
angle = newAngle;
}
const string& getCurrentString () const
{
return currentString;
}
void setDistScale ( float newScale )
{
distScale = newScale;
}
void setAngleScale ( float scale )
{
angleScale = scale;
}
void interpretString ( const string& str );
void buildSystem ( int numIterations );
void draw ()
{
interpretString ( currentString );
}
const BoundingBox& getBounds () const
{
return bounds;
}
protected:
string oneStep ( const string& in ) const;
Vector3D step ( const State& state ) const
{
return Matrix3D :: rotateZ ( state.angles.z ) * Matrix3D :: rotateY ( state.angles.y ) *
Matrix3D :: rotateX ( state.angles.x ) * state.dir;
}
virtual void drawLine ( const Vector3D& p1, const Vector3D& p2, int level ) const;
virtual void updateState ( State& state, const Vector3D& dir, int level ) const;
};
Основным отличием интерфейса этого класса от интерфейса класса LSystem является метод addRule - в нем появился дополнительный параметр - вероятность применения данного правила. Можно также задать правило без вероятности - в этом случае вероятность его применения считается равной единице.
Кроме рассмотренных выше типов L-систем, есть и другие типы. Одним из них являются контекстно-зависимые L-системы. В контекстно-зависимой (n,m) L-системе для каждого правила можно задать окружающий контекст - до n символов слева и до m символов справа.
По этой ссылке можно скачать весь исходный код к этой статье. Также доступны для скачивания откомпилированные версии для M$ Windows, Linux и Mac OS X.
