Biofractal을 이용한 나무 시뮬레이션
이 글은 린덴마이어 시스템에 대한 간단한 소개와 린덴마이어 시스템을 이용한 나무그리기 소프트웨어인 Biofractal에 대한 간단한 해설입니다.
L-system
린덴마이어 시스템,통상 L-system은 생물학자 아리스티드 린덴마이어(Aristid Lindenmayer)에 의해 제안된 수학적 형식언어(mathematical formalism)이다.린덴마이어는 단순한 대상들을 일련의 대입규칙 또는 생성규칙을 이용해 계속 대체시켜 나감으로써 복잡한 대상들을 만들어낼 수 있다고 제안했다.이 린덴마이어의 작업은 언어학자인 노암 촘스키의 형식문법에 기초하고 있다.중요한 차이점이 있다면 촘스키의 생성문법은 계기적으로(successively) 적용되는데 대해 린덴마이어의 L-system은 병렬적으로(in parallel) 적용된다는 점이다.이런면에서 이 L-system은 생명체의 성장방식을 더 근사하게 닮고 있다.
여기에 대한 직관상을 얻기 위해서 다음 사례를 보자.(이것은 문맥독립적인 결정론적 계라는 의미에서 D0L=deterministic and 0-context라고 불린다.)
a,b 두 문자들로 된 기호열을 생각해 보자.한 문자를 다른 문자로 대체시키는 대입규칙(rewriting rule)으로 a->ab, b->a라는 규칙을 부여하자.b에서 시작하면 이 규칙은 어떤 문자열을 생성시킬까?아래 그림은 그 생성의 과정을 보여주고 있다.
L-system의 원리도 기본적으로 이와 같다.이 L-system을 이용하여 식물의 성장과정을 근사하게 시뮬레이션할 수 있다.
식물들은 모두 구조적 유사성을 갖고 있다.그것은 apex라 불리는 성장점과 internode 라 불리는 줄기들로 된 단위모듈들의 반복으로 만들어진다.그러므로 식물의 기본형태는 apex와 internode를 새로운 apex와 internode로 대체시키는 알고리듬을 정의하는 생성규칙을 알고 있다면 만들어낼 수 있다.
apex(성장점)을 "A"로 internode(마디)를 "I"로 표기하도록 하자. 그러면 마디의 생성은 다음과 같이 나타낼 수 있다.
I = II
이것은 마디가 2배로 증식한다는 것을 나타내는 것으로 앞의 그림의 우측이 그것을 보여주고 있다.
성장점에서는 가지치기(branching)가 일어난다.그래서 성장점은 가지를 가진 하부단위로 대체되는데 그림의 좌측이 이것을 보여주고 있다.가지를 [ ]으로 표기하고 가지가 좌우 어느쪽으로 나왔느냐를 나타내기 위해 각각 +.-로 표기한다.이 방식으로 위 그림의 나뭇가지의 생성규칙을 기호열로 표기하면 다음과 같다.
A = I[+A][-A]IA
I = II
이것을 일반적으로 표현한 것이 Turtle Graphics이다.여기서 사용하는 명령어 가운데 몇가지는 아래와 같다.
F 앞으로 진행한다.
+ 좌회전(시계반대방향)
- 우회전(시계방향)
[ 위치와 방향을 기억한다.
] 출발점으로 복귀한다.
밑에서 시작해서 한 단위 진행한 다음(F) 좌측으로 가지를 친다.([+F])
[ ]은 출발점으로 되돌아 온다는 것을 의미하므로 분지되기전의 출발점(붉은색으로 표시한 곳)으로 돌아온다.
다음 다시 우측으로 가지를 치고([-F]) 다시 출발점으로 되돌아 온다.
다음 위로 두 단위 진행한다.(FF)
Biofractal은 이것을 다음과 같이 표기한다.
공리 A
규칙1 A=I[+A][-A]IA
규칙2 I=II
물론 이것은 앞서 설명한 대입규칙에 따라 그 단계를 원리적으로 무한히 진행할 수 있다.
1. A
2. I[+A][-A]IA(1단계)
2의 I에 II를,A에 I[+A][-A]IA를 대입하면 다음 기호열을 얻는다.
3. II[+I[+A][-A]IA][-I[+A][-A]IA]II[+A][-A]IA(2단계)
이 기호열을 그림으로 그리면 다음과 같다.(2단계 적용)
2단계 적용
여기에 다시 I에 II를,A에 II[+I[+A][-A]IA][-I[+A][-A]IA]II[+A][-A]IA을 대입해서 다음식을 얻는다.
4. IIII[+II[+II[+I[+A][-A]IA][-I[+A][-A]IA]II[+A][-A]IA][- II[+I[+A][-A]IA][-I[+A][-A]IA]II[+A][-A]IA]II II[+I[+A][-A]IA][-I[+A][-A]IA]II[+A][-A]IA][-II[+ II[+I[+A][-A]IA][-I[+A][-A]IA]II[+A][-A]IA][- II[+I[+A][-A]IA][-I[+A][-A]IA]II[+A][-A]IA]II II[+I[+A][-A]IA][-I[+A][-A]IA]II[+A][-A]IA]IIII[+ II[+I[+A][-A]IA][-I[+A][-A]IA]II[+A][-A]IA][- II[+I[+A][-A]IA][-I[+A][-A]IA]II[+A][-A]IA]11I I[+I[+A][-A]IA][-I[+A][-A]IA]II[+A][-A]IA(3단계)
이것을 Turtle언어로 바꾸기 위해서는 A와 I를 모두 F로 바꿔주면 된다.이 기호열을 그림으로 그리면 다음과 같다.(3단계 적용)
3단계 적용
.
반복적 기계적 절차라서 손으로 하기는 번거러운 일이지만 감을 잡기 위해서 2단계 까지는 손으로 그려 보는 것이 도움이 된다.그러나 3단계 이상에 그것을 요구하는 것은 무리다.이제 소프트웨어의 도움을 받을 차례이다.
L-system의 소프트웨어로 티모시 페르츠(Timothy C.Perz)의 L-system이 DOS 버전 이래로 정평이 나 있다.이것은 3차원상에서 구현된다.그러나 그만큼 복잡해서 감을 잡기에는 적합하지 않다.보다 간단한 Biofractal을 가지고 공부해 보기로 하자.
Biofractal
좌측 파넬의 상단에 미리 로드되어 있는 패턴들의 목록이 나와 있다.그중 어느 하나를 다블 클릭하면 해당 패턴이 나타난다.그 하단의 >>을 클릭하면 그 다음 단계를 보여준다.그리고 그 하단에 그 패턴을 만들어내는 규칙이 나와 있다.규칙을 바꾸어 다른 패턴을 만들고 싶다면 edit를 클릭하면 된다.그러면 다음과 같은 편집화면이 나온다.
규칙들을 바꿔줌으로써 근사한 나무를 생성시킬 수가 있다.아래는 그 몇가지 예들이다.여기서 회전각(rotation)이 60도로 되어 있다.앞서 논의의 편의상 각도는 언급하지 아니했지만 각도도 규정해 주어야 한다.
몇가지 반복계산의 사례들
반복계산이 만들어내는 알고리듬이 직관적으로 분명하지 않을 것이다.여기서 몇가지 사례들을 검토해 보자.
공리; A
규칙; F→F+F--F+F
회전각; 60도
한단계 진행한 다음(F),시계반대 방향으로 60도 회전해서 한단계 진행한다.(+F)다음 시계방향으로 120도(-은 시계방향으로 60도 --이므로 120도) 회전해서 한단계 진행한다.(--F) 다음 다시 시계반대 방향으로 한단계 진행한다.(+F)
반복계산의 다음 결과 step2는 어떻게 될까?앞서 논의한 대입규칙에 따라 step1의 각 F에 F+F--F+F을 대입한다.그러면 step2의 기호열이 만들어진다.
다음 단계 step3는 step1의 각 F에 step2의 결과를 재대입하는 것이다...이 과정을 반복함으로 코흐곡선이 만들어진다.
코흐의 눈송이(Koch flake)는 코흐곡선의 규칙은 그대로 두고 공리를 약간 바꾸면 얻어진다.
공리; F++F++F
규칙; F→F+F--F+F
회전각; 60도
step0 F++F++F
step1 F+F--F+F+F+F--F+F--F+F--F+F+F+F--F+F
step2 F+F--F+F+F+F--F+F--F+F--F+F+F+F--F+F+F+F--F+F--F+F--F+F+.......
.
.
다음은 Biofractal이 코흐 눈송이의 step5 단계의 결과를 보여주고 있다.
약간 까다로운 것이 arrowhead나 dragon curve와 같은 것이다. arrowhead의 공리와 규칙을 보자.
공리 YF
규칙 X→YF+XF+Y
Y→XF-YF-X
회전각 60도
step0. YF
step1 XF-YF-XF ←공리에 따라 Y의 값에 F를 부가한다.
step2 YF+XF+YF-XF-YF-XF-YF+XF+YF
여기서 X,Y는 표기의 편의상 가져온 것이며 단순히 F이다.그러므로 step1은 FF-FF-FF이고 step2는 FF+FF+FF-FF-FF-FF-FF+FF+FF이다.
step1의 궤적을 머릿속에 그려 보자.어떤 형태일까? 2단위 진행한다음(FF),시계방향으로 60도 회전해서 다시 2단위 진행하고(-FF) 다시 시계방향으로 60도 회전해서 2단위 진행한다.(-FF)
이 형태는 좌측과 같이 될 것이다.이것을 Biofractal의 arrowhead를 선택해서 확인해 보도록 하자.
아래는 step2,step6 단계의 형태이다
아래 그림은 어떻게 만들어질까?
plant6을 클릭하면 이 형태가 만들어진다.이것의 공리와 규칙은 다음과 같다.
공리 F
규칙 F→F[-F]F[+F]F
회전각 20도
step1 F[-F]F[+F]F
step2 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) 시계방향으로 20도 꺽어 한 단위 진행한 다음 출발점으로 돌아온다.([+F]) 거기서 원래의 방향으로 한 단위 진행한다.(F) 다음 시계반대방향으로 20도 꺽어 한 단위 진행하고 다시 출발점으로 돌아온다.([+F]) 다시 원래의 방향으로 한 단위 진행한다.(F)그러면 위 그림의 제일 좌측의 간단한 형태가 만들어질 것이다.이것을 반복계산함으로써 제일 우측의 근사한 나무의 형태가 만들어진다.