L-SYSTEM

정해진 규칙에 의해 특정 문자열을 반복하여 전개한 후 전개된 문자열에 의거하여 그림을 그리는 것을 L-시스템이라 한다. 1986년 린덴마이어(Lindenmayer)가 생태계의 성장 모형, 특히 나무의 분기 모형을 연구하는 목적으로 고안하였다.

L-SYSTEM 개요

F, +, -

L-시스템에서는 거북이 그래픽과 문자열에 의거하여 프랙탈을 그리는데, 문자열의 문자 중 다음의 문자를 만나면 거북이 그래픽을 수행하여 선을 그리고 회전을 한다.

• F : 일정한 길이의 선을 그리고 현재의 점을 선의 끝점으로 이동

• • : 왼쪽 방향으로 angle 만큼 회전

• • : 오른쪽 방향으로 angle 만큼 회전

변환규칙

아래와 같은 코호 곡선을 그리는 경우를 생각해 보자.

1. 선을 그린다 ( F )

2. 60 도 좌회전한다 ( + )

3. 선을 그린다 ( F )

4. 60 도 우회전한다 ( - )

5. 60 도 우회전한다 ( - )

6. 선을 그린다 ( F )

7. 60 도 좌회전한다 ( + )

8. 선을 그린다 ( F )

이에 해당하는 문자열은 다음과 같다.

1차 변환 : F+F--F+F

위는 1 차원의 코호 곡선을 그린 것이다. 그렇다면 아래의 2 차원의 코호 곡선은 어떻게 그릴까? 1 차 코호 곡선을 그리는 규칙을 A라 한다면 A 는 다음과 같이 된다. A( F+F--F+F)

1. A 를 그린다

2. 60 도 좌회전한다 ( + )

3. A 를 그린다

4. 60 도 우회전한다 ( - )

5. 60 도 우회전한다 ( - )

6. A 를 그린다

7. 60 도 좌회전한다 ( + )

8. A 를 그린다.

이에 해당하는 문자열은 다음과 같다.

A+A--A+A

위의 규칙을 A -> F + F - - F + F 로 고쳐보면 다음과 같다.

2차 변환 : F+F--F+F+F+F--F+F--F+F--F+F+F+F--F+F

이를 3차 변환 해 본다면 아래와 같이 된다.

3차 변환 : F+F--F+F+F+F--F+F--F+F--F+F+F+F--F+F+F+F--F+F+F+F--F+F--F+F--F+F+F+F--F+F--F+F--F+F+F+F--F+F--F+F--F+F+F+F--F+F+F+F--F+F+F+F--F+F--F+F--F+F+F+F--F+F

이와 같이 F -> F+F--F+F 로 변환하는 규칙을 변환규칙이라고 한다. 이 변환 규칙을 3번 변환하면 위의 3차 변환이 나오게 된다.

공리

수학에서 공리는 가장 기본을 이룬다. 예를 들어 '삼각형 내각의 합은 180도이다' 가 공리의 예이다. 이러한 공리에서 많은 수학적 정리들이 만들어졌다. 즉 공리는 가장 기본적인 원칙이라고 할 수 있다. 이 공리는 마치 유전자와도 같다. 간단한 유전자가 생물체의 여러 가지 복잡한 성장을 제어한다. L-시스템에서도 공리는 이와 비슷한 개념을 갖는다. 다시 말하자면 L-시스템에서 공리는 복잡한 프랙탈안에 숨어 있는 유전자라고 할 수 있다.

L-SYSTEM 구현

지금부터 구현해볼 L-시스템은 다음과 같은 규칙을 갖는다.

• F : 전진

• + : 좌회전

• - : 우회전

• @ : 점을 그린다.(열매를 그린다)

• [ : 현재 위치와 각도를 스택에 저장한다.

• ] : 현재 위치와 각도를 스택의 최상위 아이템의 위치와 각도로 설정한다.

• { : 현재 위치만을 스택에 저장한다.

• } : 현재 위치를 스택의 최상위 아이템의 위치와 각도로 설정한다.

• | : 왼쪽으로 180 도 회전한다.

이를 위해서 거북이 그래픽 클래스가 약간 변형되었다. 스택에 저장하는 내용과 Push() 함수에 새로운 인자가 설정된 것이다. 소스 코드를 보면 이해가 갈 것이다.

struct StackItem
{
    Point3D cp;
    float angle;
    bool save_angle;
    StackItem() { cp.x=cp.y=cp.z=0.0f; angle=0.0f; save_angle=false; }
    StackItem(const Point3D& pt, float a, bool s)
    {
        cp.x = pt.x;
        cp.y = pt.y;
        cp.z = pt.z;
        angle = a;
        save_angle = s;
    }
    StackItem(const StackItem& i)
    {
        cp = i.cp;
        angle = i.angle;
        save_angle = i.save_angle;
    }
};

typedef stack<StackItem> pstack;

class Turtle
{
    ... 
    void Push(bool save_angle=true);
    void Pop(void);
    ... 
};

void Turtle::Push(bool save_angle)
{
    int index = PointList.size()-1;
    Point3D pt(PointList[index].x, PointList[index].y, PointList[index].z);
    //포인트 리스트에 저장되어 있는 마지막 점을 push 한다.
     // save_angle 이 true 이면 pop 수행시 저장된 각도가 현재 각도가 된다.
    StackItem s(pt, angle, save_angle);
    PointStack.push(s);
}

void Turtle::Pop(void)
{
    if(PointStack.size())
    {
        StackItem s(PointStack.top());
        PointStack.pop();
        PointList.push_back(s.cp);
        if(s.save_angle)
        {
            angle = s.angle;
        }
    }
}

이제 L 시스템을 구현해 보자. 아래는 소스 코드를 나타낸 것이다. 따로 설명은 하지 않고 주석을 달았다.

/*******************************************************************************
{ LSystem Class
{ written by Sungcheol Kim
{ 2003.4.27
{
{ F : 전진
{ + : 왼쪽으로 회전
{ - : 오른쪽으로 회전
{ | : 왼쪽으로 180 도 회전
{ [ : 현재좌표, 현재 각도를 스택에저장
{ ] : 현재좌표, 현재 각도를 저장했던 좌표,각도로 설정
{ { : 현재좌표만 저장
{ } : 현재좌표만 저장했던 좌표로 설정
{ @ : 열매를 그린다.
*******************************************************************************/

#ifndef _LSYSTEM_H_
#define _LSYSTEM_H_

#pragma warning(disable : 4786)

#include <map>
#include <string>
#include "turtle.h"

using namespace std;

typedef map< char, string > trule_list;
typedef map< char, string >::iterator ai;

class LSystem
{
public:
    string TotalAxiom; //최종 공리
    trule_list TRuleList; //변환규칙 리스트
    float angle; //회전각도
    float length; //진행길이
    float factor; //길이의 배율
    Turtle *turtle; //거북이
public:
    LSystem();

    void SetAngle(float rotate_angle); //회전 각도를 설정한다.
    void SetLength(float move_distance); //전진 거리를 설정한다.
    void SetFactor(float magnification); //전진 비율을 설정한다. 최종 전진 거리는 length*factor 와 같다.

    void SelectTurtle(Turtle *pturtle); //거북이를 선택한다.
    void AddTransRule(char name, string rule); //변환 규칙을 생성, 추가한다.
    void MakeAxiom(string axiom, int n); //공리를 만든다. n 차까지 공리 변환
    void Draw(void); //공리에 의한 L-시스템을 그린다.
};

#endif

#include "LSystem.h"

LSystem::LSystem(void)
{
    angle = 0.0f;
    length = 1.0f;
    factor = 1.0f;
    turtle = NULL;
    TotalAxiom = "";
    TRuleList.clear();
}
void LSystem::SetAngle(float rotate_angle)
{
    angle = rotate_angle;
}
void LSystem::SetLength(float move_distance)
{
    length = move_distance;
}
void LSystem::SetFactor(float magnification)
{
    factor = magnification;
}
void LSystem::SelectTurtle(Turtle *pturtle)
{
    turtle = pturtle;
}
void LSystem::AddTransRule(char name, string rule)
{
    TRuleList[name] = rule;
}
void LSystem::MakeAxiom(string axiom, int n)
{
    ai fi;
    string buffer;
    TotalAxiom = axiom;
    for(int x=0; x<n; ++x) //n차까지 변환
    {
        buffer.erase(buffer.begin(), buffer.end());//공리를 담을 버퍼
        for(int i=0; i<TotalAxiom.length(); ++i)
        {
            switch(TotalAxiom[i])
            {
                case 'F':
                    fi = TRuleList.find('F'); // F 에 대해서 정의된 변환 규칙이 있으면 그 규칙을 버퍼에 넣고 아니면 그냥 F(전진) 자를 넣는다.
                    if(fi!=TRuleList.end())
                    {
                        buffer += fi->second;
                    }
                    else
                    {
                        buffer += "F";
                    }
                    break;
                case '@':
                    buffer += "@";
                    break;
                case '+':
                    buffer += "+";
                    break;
                case '-':
                    buffer += "-";
                    break;
                case '[':
                    buffer += "[";
                    break;
                case ']':
                    buffer += "]";
                    break;
                case '{':
                    buffer += "{";
                    break;
                case '}':
                    buffer += "}";
                    break;
                case '|':
                    buffer += "|";
                    break;
                default: //위의 문자 이외의 문자는 해당 문자에 해당하는 변환규칙이 있으면 버퍼에 넣는다.
                    fi = TRuleList.find((char)(TotalAxiom[i]));
                    if(fi!=TRuleList.end())
                    {
                        buffer += fi->second;
                    }
                    break;
            }
        }
        TotalAxiom = buffer; //버퍼를 최종 공리에 넣는다.
    }
}

void LSystem::Draw(void)
{
    for(string::iterator i = TotalAxiom.begin(); i!=TotalAxiom.end(); ++i)
    {
        switch((char)(*i))
        {
            case 'F':
                turtle->Forward(length*factor); //전진
                break;
            case '@':
                turtle->MarkCurrentPoint(); //열매그리기 
                break;
            case '+':
                turtle->Left(angle); //좌회전 
                break;
            case '-':
                turtle->Right(angle); //우회전 
                break;
            case '|':
                turtle->Left(180); //좌로 180 도 회전
                break;
            case '[':
                turtle->Push(true); //위치, 각도 저장
                break;
            case ']':
            case '}':
                turtle->Pop(); //위치 또느 각도 화원
                break;
            case '{':
                turtle->Push(false); //위치 저장
                break;
        }
    }
}

아래의 코드는 L-시스템을 사용하는 일련의 코드를 보여준다.

#include "lib\egl.h"
#include "LSystem.h"

using namespace egl;

class RenderWindow : public Window
{
private:
    LSystem lsystem;
    Turtle turtle;
public:
    virtual BOOL InitGL(void);
    virtual void RenderGLScene(void);
};

BOOL RenderWindow::InitGL(void)
{
    Window::InitGL();

    lsystem.SelectTurtle(&turtle); //거북이 선택
    lsystem.SetAngle(60.0f); //회전 각도를 60 도로 설정
    lsystem.SetLength(1.0f); //전진 거리를 1.0 으로 설정
    lsystem.SetFactor(1.0f); //전진 비율을 1.0 으로 설정
    lsystem.AddTransRule('F', "F+F--F+F"); //코흐 곡선을 그리는 변환 규칙 F 생성 및 추가
    lsystem.MakeAxiom("F", 3); //공리 F 를 3 차에 걸쳐 변환 

    return TRUE;
}

void RenderWindow::RenderGLScene(void)
{
    Window::RenderGLScene();
    turtle.SetStartPoint(-13.0f, 0.0f, -30.0f); //거북이의 시작위치를 정하고 
    lsystem.Draw(); //L-시스템에 의해 생성된 프랙탈을 그린다.
}

int APIENTRY WinMain(HINSTANCE hInstance, HINSTANCE hPrevInstance, LPSTR lpCmdLine, int nShowCmd)
{
    RenderWindow app;
    if(!app.Create(FALSE, "EDin's OpenGL - Texture2D"))
        return EXIT_FAILURE;
    return app.Run();
}

아래는 실행 결과이다.

다음 장에서 L-시스템을 활용한 여러가지 프랙탈을 그려보자.