만델브로트 프랙탈

프랙탈은 자기유사성으로 알려져있는 일부 조각이 전부를 구성하는 모양이 되는 기하학적 구조를 뜻한다. 그중 만델브로트 집합은 풍뎅이인 특유의 모양으로 잘 알려져 있다.

정의

정의된 수열이 발산하지 않는 성질을 갖도록 하는 복수수 c의 집합으로 정의된다.

Z0 = 0
Zn+1 = Zn^2 + c

실제로 그리는 방법

사실 이렇게만 써놓으면 잘 감이 오지 않는다. 이를 실수부 , 허수부로 나눈다.

(X0, Y0) = (0, 0)
Xn+1 = Xn^2 - Yn^2 + a
Yn+1 = 2 * Xn * Yn + b

이것을 X축은 가로 Y축은 세로로 그대로 대입한다. 위 점화식 계산하면서 수열이 발산하는지 아닌지 검사한다. 이때 절대값이 2보다 크다면 Xn^2 + Yn^2 > 2^2 그러면 발산한다고 할수 있으며 연속해서 계산을 하다가 처음으로 벗어나는 순간 카운트를 세고 해당 카운트를 기반으로 색상을 칠한다.

의사코드

C
x = cx;
y = cy;

int cnt = 1024;
for(int i=0; i < 1024; i++){
	if(x*x + y*y > 4.0){
		cnt = i;
		break;
	}
	nx = x*x - y*y + cx;
	ny = 2.0*x*y + cy;

	x = nx;
	y = ny;
}

1024번으로 구간을 정했으므로 1024단계의 색상을 입혀서 칠하면 된다.

OPENGL로 구현하기

OPENGL 등을 통해 그리면 쉽게 구현할 수 있다. 사실 canvas의 한 픽셀 한 픽셀 진행하면서 해당 좌표에 대해서 만델브로트 계산을 하여 몇번만에 벗어나는지 일일히 계산을 하여야 한다. 즉

canvas 좌표계를 만델브로트 좌표계로 변경
만델브로트의 좌표를 가지고 계산 몇번 만에 벗어나는지 카운트
해당 카운트를 가지고 색상 선정
모든 픽셀에 대해 반복

이때 OPENGL은 Vertex Shader를 통해 좌표계 변환을 자동으로 해주고 Fragment Shader를 통해 픽셀마다 반복계산을 자동으로 해준다.

그래도 각 픽셀은 다른 픽셀에 영향을 주지 않고 자신만 계산하면 되므로 병렬계산을 쉽게 활용할 수 있는 주제이다.

TXT
+--------------------------------+
|(0,0)                           |
|                                |
|                                |
|                           (m,n)|
+--------------------------------+
0,0에서 시작하는 좌표계를 만들브로트 집합의 좌표계로 변경
위 좌표계에서 아래 좌표계로 변환

+--------------------------------+
|(-2,1)                          |
|                                |
|                                |
|                          (1,-1)|
+--------------------------------+
한 픽셀씩 진행하면서 만델브로 발산 경계값을 구하고
해당 경계값을 가지고 색상을 정함

이를 WEBGL로 구현 하여 토이프로젝트로 올렸다.

JAVASCRIPT
// {x:-2.0, y:-1.0, w:3.0, h:2.0}
var plot_vertices = [
    -2.0, -1.0,
    -2.0,  1.0,
     1.0, -1.0,
     1.0,  1.0
];
// ...

// plot
var plotPosBuf = gl.createBuffer();
gl.bindBuffer(gl.ARRAY_BUFFER, plotPosBuf);
gl.bufferData(gl.ARRAY_BUFFER, new Float32Array(plot_vertices), gl.STATIC_DRAW);
gl.vertexAttribPointer(plotPos, 2, gl.FLOAT, false, 0, 0);

gl.drawArrays(gl.TRIANGLE_STRIP, 0, 4);

위 Javascript 소스는 만델브로토 집합 좌표계의 버텍스들을 넘겨주어 그리라고 지시한 것이다. canvas의 좌표계를 신경쓸 필요가 없다. GL이 알아서 해준다. 하지만 GL을 사용하지 않는다면 canvas 좌표를 변환하는 과정을 구현하고 각 픽셀마다 동일한 계산을 반복하는 부분까지 구현해야 할 것이다.

부드러운 색상

프랙탈의 색상을 부드럽게 만드는 방법이다. Continuous Smooth Coloring 부분을 참조

C
void main(void){
	float x = 0.0;
	float y = 0.0;
	float nx = 0.0;
	float ny = 0.0;

	float cx = fragPos.x;
	float cy = fragPos.y;

	float zn = 0.0;
	float nu = 0.0;
	float t = 0.0;

	vec3 color1;
	vec3 color2;

	x = cx;
	y = cy;

	int cnt = 1024;
	for(int i=0; i < 1024; i++){
		if(x*x + y*y > 4.0){
			cnt = i;
			break;
		}
		nx = x*x - y*y + cx;
		ny = 2.0*x*y + cy;

		x = nx;
		y = ny;
	}

	// 부드러운 색상 
	zn = sqrt(x*x + y*y);
	nu = log(log(zn) / log(2.0)) / log(2.0);
	t  = 1.0 - nu;

	color1 = coloring(cnt);
	color2 = coloring(cnt+1);

	color1.r = (1.0 - t) * color1.r + t * color2.r;
	color1.g = (1.0 - t) * color1.g + t * color2.g;
	color1.b = (1.0 - t) * color1.b + t * color2.b;

	gl_FragColor = vec4(color1, 1.0);      
}	

생각해볼만한 주제

WEBGL의 한계로 인해 float 은 32비트 부동소수점 숫자로 계산된다. 하지만 이는 Zoom을 몇번만 해도 금방 정밀도가 소진되어 모자이크가 발생하게 된다.

Double Precision 에뮬레이션

옛날 프로그래머들이 구현했던 방법을 사용할 수 있다. Double Emulation float 두개를 가지고 하나의 Double을 표현하는 방법이다. 에뮬레이션 하는 라이브러리를 구하여 적용시켜본다.

Big Float

Double로도 줌을 계속 들어가게되면 금방 정밀도가 떨어지게 된다. 하지만 유투브나 이런 곳을 보면 Zoom을 몇시간 동안이나 하는데도 정밀도가 끝이 없다. 이정도로 줌을 땡길려면 Big Float을 구현해야 할 것이다.

만델브로트프랙탈