이런 것, 한 번 쯤은 본적 있지 않은가?

검은 화면, 하얀 색 특수문자들로 돌아가는 3D 도넛을 만든다.
분명 간단한 프로그램 같지만 묘하게 보는 맛이 있다.
이것은 Donut.c이다.
이렇게 ASCII 문자열로 그림을 그리는 것을 ASCII Art라고 한다.

"에이, 그래봤자 콘솔창에 글자 출력하는 건데."

하지만 쉽게 보면 곤란하다.
그래픽에 관련된 만큼, 한 번 파고 들어가보면 심오한 수학의 세계가 펼쳐져 있기 때문.

이 글에서는 그 수학을 한 번 이해해 보려고 한다.

Donut.c

이 콘솔 도넛에 대한 나의 관심은 한 유튜브 동영상에서부터 시작되었다.
그 동영상은 "why you NEED math for programming", 번역하면 "프로그래밍에 수학이 필요한 이유" 라는 영상이다.

이 글의 끝에서 어떻게 도넛이 아스키 코드로 렌더링 되는지를 간략한 수학적 원리로 설명해준다.
그것을 듣고 관심이 생겨 인터넷에 검색해보게 되었다.

놀랍게도, 생각보다 이것에 대한 글이 많이 없었다.
고작 간략한 한국어 소개 글과 복잡한 영어 수학적인 원리를 설명해주는 글 뿐.

처음에는 영어에 복잡한 수학까지 섞여 있어 읽기 꺼려졌지만, 작정하고 읽다보니 읽을 만 했다.

그럼 이제 진짜로 분석을 시작해보자.
여기에 나오는 수학적인 원리는 이 글을 참고했다.

ASCII Art에 대하여

먼저 일반적인 ASCII Art에서 어떤 방식으로 밝기를 표현하는지를 알아보자.

우리가 ASCII Art를 출력할 곳은 터미널인데, 터미널은 일반적으로 바탕이 어두운 색이고 문자가 밝은 색이다.
따라서 한 글자가 차지하는 공간 안에서 픽셀의 밀도가 높으면 밝은 색, 픽셀의 밀도가 낮으면 어두운 색으로 정할 수 있다.
이를 간단한 12 글자로 나타낸 것이 아래의 글자들이다.
.,-~:;=!*#$@
왼쪽이 일정한 공간 내에서 밀도가 가장 낮으므로 가장 어두운 색, 오른쪽이 일정한 공간 내에서 밀도가 가장 높으므로 가장 밝은 색이다.

수학적인 원리

일단, 어떻게 저것을 구현해야 할 지를 생각해 보자.
두 가지가 필요하다.

1. 도넛의 형상을 그리기
2. 도넛의 형상에 밝기를 나타내기

자, 이제 3D 1인칭 시점에서 쓰이는 간단한 수학으로 시작해 보자.

위의 그림은 사람이 스크린 앞에 앉아서 스크린 뒤의 물체를 쳐다보는 그림이다. 3차원의 물체를 2차원에 그리기 위해, 3차원의 각각의 점 $(x, y, z)$(x,y,z)를 시청자의 $z'$z′만큼 떨어진 평면에 투영한다.
그러면 그 점은 $(x', y')$(x′,y′)이 될 것이다.
3차원 물체의 각각의 점의 좌표를 알고 있는 상황에서 2차원의 어디에 투영해야 할 지를 알아야 하므로 $x$x, $y$y를 가지고 $x'$x′, $y'$y′을 알아야 한다. ($z'$z′은 상수이므로 $K_1$K1​이라고 하자.)

수학 식으로 나타내면 $\dfrac{y'}{K_1} = \dfrac{y}{z}$K1​y′​=zy​
$z'$z′을 이항하면 $y' = \dfrac{yK_1}{z}$y′=zyK1​​
이 식은 $x$x에도 똑같이 적용할 수 있다: $x' = \dfrac{xK_1}{z}$x′=zxK1​​
따라서 투영 방정식은 $(x', y')=(\dfrac{K_1x}{z}, \dfrac{K_1y}{z})$(x′,y′)=(zK1​x​,zK1​y​)이 된다.
$K_1$K1​은 2D 창에 표시하기를 원하는 시야각에 따라 임의로 설정할 수 있다. 예를 들어 100x100 사이즈의 창이 있다면 시야는 (50, 50)에 맞춰져 있을 것이다, 이 때 3D 공간에서 시야를 기준으로 5만큼 떨어져있고 너비가 10인 물체를 보고 싶다면, 점 $x=10$x=10, $z=5$z=5인 점의 투영이 화면에 나타나도록 해야 하므로:

• $x'<50$x′<50 이어야 함
• 즉 $\dfrac{10K_1}{z}<50$z10K1​​<50 이어야 함
• 즉 $K_1 < 25$K1​<25 이어야 함

또한 많은 점들을 투영하면서 $x$x와 $y$y는 같지만 $z$z가 다른 점을 투영해야 할 일이 생길 수도 있으므로, 우리가 그리는 모든 것에 대한 $z$z 좌표를 저장하는 z-buffer를 만들 것이다. z-buffer가 있으면 어떤 점을 위치에 표시할 때 그 위치에 이미 있던 것보다 앞에 있는지를 확인할 수 있게 된다.
또한 z-buffer는 $z^{-1}=\dfrac{1}{z}$z−1=z1​를 계산하고 깊이를 버퍼링하는 데 도움을 줄 수 있는데, 그 이유는 다음과 같다.

1. $z^{-1} = 0$z−1=0 이면 $z$z는 무한에 가까우므로, z-buffer의 기본값을 0으로 두고 배경을 무한대 깊이로 설정할 수 있다.
2. $x'$x′과 $y'$y′을 구할 때 다시 이용할 수 있다. ($z^{-1}=\dfrac{1}{z}$z−1=z1​, $z$z를 미리 나눠 둠으로서 굳이 $z$z를 두번 나누지 않고 조금 더 효율적으로 연산할 수 있다.)

도넛 (solid of revolution)

자, 그럼 이제 도넛 형상을 어떻게 만들 지를 고민해야 한다.
다행히도, 도넛은 회전체(solid of revolution) 이므로 다음과 같은 원리를 통해 각각의 점을 구할 수 있다.
보다시피 $(R_2, 0, 0)$(R2​,0,0) 점을 중심으로 한 $R_1$R1​이 반지름인 원이 있다.
$R_1$R1​을 중심으로 한 원은 0360도로 돌려줌으로서 그릴 수 있다.
0360도까지 변하는 변수를 $\theta$θ로 두자.

이것을 식으로 나타내면 다음과 같다.
$(x, y, z) = (R_2, 0, 0) + (R_1\cos\theta, R_1\sin\theta, 0)$(x,y,z)=(R2​,0,0)+(R1​cosθ,R1​sinθ,0)
이 식으로 원 하나를 구할 수 있다.

이제 이 원을 2y축을 따라 돌려보자. 바로 도넛 모양이 나온다는 것을 눈치 챘을 것이다.
이 원을 y축을 따라 회전시키기 위해서는 회전 변환 행렬을 이용해 구할 수 있다.

y축을 따라 돌려야 하므로, 3차원 y축 회전 변환 행렬을 가져와 곱하면 아래와 같은 식이 나온다.

$$\begin{align} & (R_2+R_1\cos\theta,R_1\sin\theta,0)\cdot\left(\begin{matrix}\cos\phi & 0 & \sin\phi \\ 0 & 1 & 0 \\ -\sin\phi & 0 & \cos\phi\end{matrix}\right)\\\\= & ((R_2+R_1\cos\theta)\cos\phi, R_1\sin\theta, -(R_2+R_1\cos\theta)\sin\phi)\end{align}$$=​(R2​+R1​cosθ,R1​sinθ,0)⋅​cosϕ0−sinϕ​010​sinϕ0cosϕ​​((R2​+R1​cosθ)cosϕ,R1​sinθ,−(R2​+R1​cosθ)sinϕ)​​

그런데 우리는 이 도넛이 두 개 이상의 축에서 회전하도록 구현하고 싶기 때문에, 2개의 회전 변환 행렬을 더 가져와 곱한다.
또한 가져온 2개의 회전 변환 행렬에서 쓰이는 각도는 A와 B로 칭한다.
식은 다음과 같다.

$$(R_2+R_1\cos\theta,R_1\sin\theta,0)\cdot\left(\begin{matrix}\cos\phi & 0 & \sin\phi \\ 0 & 1 & 0 \\ -\sin\phi & 0 & \cos\phi\end{matrix}\right)\cdot\left(\begin{matrix}1&0&0\\0&\cos A&\sin A\\0&-\sin A&\cos A\end{matrix}\right)\cdot\left(\begin{matrix}\cos B&\sin B&0\\-\sin B&\cos B & 0\\0 & 0 & 1\end{matrix}\right)$$(R2​+R1​cosθ,R1​sinθ,0)⋅​cosϕ0−sinϕ​010​sinϕ0cosϕ​​⋅​100​0cosA−sinA​0sinAcosA​​⋅​cosB−sinB0​sinBcosB0​001​​

이제 우리는 원점인 $(0, 0, 0)$(0,0,0)을 기준으로 하는, $A$A와 $B$B라는 각에 의해 일정하게 회전하는 도넛의 좌표들을 가지고 있다.

이제 이것을 실제로 화면에 투영하기 위해서는 시청자의 좌표가 $(0, 0, 0)$(0,0,0)이라고 가정하고, 도넛을 시청자의 앞 쪽으로 옮겨야 한다.
도넛을 시청자의 앞쪽으로 옮기기 위해, $z$z에 시청자와 도넛이 떨어진 거리를 더해야 한다.
이 시청자와 도넛이 떨어진 거리를 $K_2$K2​라고 하자.

이제 실제 $(x', y')$(x′,y′)을 구하기 위한 식은 다음과 같다.

$(x', y') = \left(\dfrac{K_1x}{K2 + z}, \dfrac{K_1y}{K_2+z}\right)$(x′,y′)=(K2+zK1​x​,K2​+zK1​y​)

그리고, $(x, y, z)$(x,y,z)를 구하기 위한 식은 다음과 같다.

$$\left(\begin{matrix}x\\y\\z\end{matrix}\right)=\left(\begin{matrix}(R_2+R_1\cos\theta)(\cos B\cos\phi+\sin A\sin B\sin\phi)-R_1\cos A\sin B\sin\theta\\(R_2+R_1\cos\theta)(\cos\phi\sin B-\cos B\sin A\sin\phi)+R_1\cos A\cos B\sin\theta\\\cos A(R_2+R_1\cos\theta)\sin\phi+R_1\sin A\sin\theta\end{matrix}\right)$$​xyz​​=​(R2​+R1​cosθ)(cosBcosϕ+sinAsinBsinϕ)−R1​cosAsinBsinθ(R2​+R1​cosθ)(cosϕsinB−cosBsinAsinϕ)+R1​cosAcosBsinθcosA(R2​+R1​cosθ)sinϕ+R1​sinAsinθ​​

최대한 최적화 하기 위해, 프로그래밍 단계에서는 행렬 곱셈을 쓰지 않고 위의 계산 식을 사용할 것이며, 또한 $(R_2 + R_1 * \cos\theta)$(R2​+R1​∗cosθ)와 같은 값을 미리 계산해 식에서 재사용하도록 할 것이다.

밝기

이제 어느 곳에 점을 둬야 할 지는 알았지만, 그 각각의 점에 대한 밝기는 아직 모른다.
광도를 계산하기 위해 필요한 수학적 개념은 법선surface normal 이다.

이 법선을 구하고 나면, 이 법선과 빛의 방향 간의 내적을 구할 수 있게 되고, 이 내적은 법선과 빛의 방향 간의 각도를 코사인한 값을 포함하고 있다.

벡터 $a$a와 벡터 $b$b에 대한 내적은 $a \cdot b = |a||b|\cos\theta$a⋅b=∣a∣∣b∣cosθ 이므로
만약 이 내적이 0보다 크다면 $\cos\theta > 0$cosθ>0 이므로 그 위치의 점이 빛을 바라보고 있으므로 밝고, 0보다 작다면 그 위치의 점이 빛을 바라보고 있지 않아 어두울 것이다.
즉, 내적이 크면 클 수록 더 많은 빛이 점에 떨어진다.

그런데, 생각해보면 이 법선 벡터는 구하기 매우 쉽다.
왜냐하면 $(0, 0, 0)$(0,0,0)에서 최종적인 $(x, y, z)$(x,y,z)까지의 벡터가 $(x, y, z)$(x,y,z) 점의 법선벡터가 되기 때문이다. 따라서, 위의 회전 변환 행렬과 같이 식을 다시 쓸 수 있다.

$$(N_x,N_y,N_z)=(\cos\theta,\sin\theta,0)\cdot\left(\begin{matrix}\cos\phi&0&\sin\phi\\0&1&0\\-\sin\phi&0&\cos\phi\end{matrix}\right)\cdot\left(\begin{matrix}1&0&0\\0&\cos A&\sin A\\0 & -\sin A&\cos A\end{matrix}\right)\cdot\left(\begin{matrix}\cos B&\sin B&0\\-\sin B&\cos B&0 \\0&0&1\end{matrix}\right)$$(Nx​,Ny​,Nz​)=(cosθ,sinθ,0)⋅​cosϕ0−sinϕ​010​sinϕ0cosϕ​​⋅​100​0cosA−sinA​0sinAcosA​​⋅​cosB−sinB0​sinBcosB0​001​​

이 식에서 다른 점은, 시작점이 $(\cos\theta, \sin\theta, 0)$(cosθ,sinθ,0)이라는 것이다.
이는 정확한 $x$x, $y$y, $z$z의 값이 아니라, 각 $\theta$θ에 대한 코사인과 사인으로 방향만을 나타낸 것이다. (크기는 정확하지 않다.)

자, 그렇다면 이제 빛의 방향을 정해야 한다.
시청자의 뒤쪽 위에서 빛을 비추는 것은 어떨까?
그렇다면 빛의 벡터는 $(0, 1, -1)$(0,1,−1)이 된다.
이제 아까의 법선 벡터와 이 빛의 벡터의 내적을 구해보자.

$$\begin{align}L&=(N_x,N_y,N_z)\cdot(0,1,-1)\\&=\cos\phi\cos\theta\sin B-\cos A\cos\theta\sin\phi-\sin A\sin\theta+\cos B(\cos A\sin\theta-\cos\theta\sin A\sin\phi)\end{align}$$L​=(Nx​,Ny​,Nz​)⋅(0,1,−1)=cosϕcosθsinB−cosAcosθsinϕ−sinAsinθ+cosB(cosAsinθ−cosθsinAsinϕ)​​

자, 이제 마지막으로 해야 할 일은 상수를 정하는 것이다.
정하지 않은 상수에는 도넛의 전체 크기와 링의 두께를 정할 $R_1$R1​, $R_2$R2​가 있고, 또 크기를 나타낼 $K_1$K1​, 관찰자와 도넛 사이의 거리를 나타낼 $K_2$K2​가 있다.

먼저 $R_1$R1​과 $R_2$R2​는 각각 1과 2로 정하고, $K_2$K2​는 5로 정했다.
$K_1$K1​의 경우 크기를 나타내는데, 화면의 크기(한 화면에 나타낼 수 있는 ASCII 글자의 수)에 따라 달라지므로 다음과 같이 식을 짤 수 있다.

먼저 도넛이 나타낼 수 있는 최대 가로(최대 x 좌표)는 $R_1+R_2$R1​+R2​이고, $z$z는 0이다.
그 점이 화면의 가로 $\dfrac{3}{8}$83​ 지점 쯤에 나타나도록 하려면,

screen_width * 3/8 = K1 * (R1+R2) / (K2 + 0)
screen_width * K2 * 3 / (8 * (R1+R2)) = K1

위와 같이 나타낼 수 있다.

최종 코드

따라서 파이썬과 numpy로 나타낸 최종 코드는 다음과 같다.

import numpy as np
screen_size = 40
theta_spacing = 0.07
phi_spacing = 0.02
illumination = np.fromiter(".,-~:;=!*#$@", dtype="<U1") 
A = 1
B = 1
R1 = 1
R2 = 2
K2 = 5
K1 = screen_size * K2 * 3 / (8 * (R1 + R2)) 
def render_frame(A: float, B: float) -> np.ndarray: 
    cos_A = np.cos(A) 
    sin_A = np.sin(A) 
    cos_B = np.cos(B) 
    sin_B = np.sin(B) 
    
    output = np.full((screen_size, screen_size), " ")
    zbuffer = np.zeros((screen_size, screen_size))
    
    cos_phi = np.cos(phi := np.arange(0, 2 * np.pi, phi_spacing)) # (315,) 
    sin_phi = np.sin(phi)
    cos_theta = np.cos(theta := np.arange(0, 2 * np.pi, theta_spacing)) # (90,)
    sin_theta = np.sin(theta)
    
    circle_x = R2 + R1 * cos_theta
    circle_y = R1 * sin_theta
    
    x = (np.outer(cos_B * cos_phi + sin_A * sin_B * sin_phi, circle_x) - circle_y * cos_A * sin_B).T
    y = (np.outer(sin_B * cos_phi - sin_A * cos_B * sin_phi, circle_x) + circle_y * cos_A * cos_B).T
    z = ((K2 + cos_A * np.outer(sin_phi, circle_x)) + circle_y * sin_A).T
    ooz = np.reciprocal(z) 
    xp = (screen_size / 2 + K1 * ooz * x).astype(int)
    yp = (screen_size / 2 - K1 * ooz * y).astype(int)
    L1 = (((np.outer(cos_phi, cos_theta) * sin_B) - cos_A * np.outer(sin_phi, cos_theta)) - sin_A * sin_theta)
    L2 = cos_B * (cos_A * sin_theta - np.outer(sin_phi, cos_theta * sin_A))
    L = np.around(((L1 + L2) * 8)).astype(int).T
    mask_L = L >= 0 
    chars = illumination[L] 
    for i in range(90): 
        mask = mask_L[i] & (ooz[i] > zbuffer[xp[i], yp[i]]) 
        zbuffer[xp[i], yp[i]] = np.where(mask, ooz[i], zbuffer[xp[i], yp[i]])     
        output[xp[i], yp[i]] = np.where(mask, chars[i], output[xp[i], yp[i]]) 
        return output 
def pprint(array: np.ndarray) -> None:
    print(*[" ".join(row) for row in array], sep="\n") 
    
if __name__ == "__main__": 
    for _ in range(screen_size * screen_size): 
        A += theta_spacing 
        B += phi_spacing 
        print("\x1b[H") 
        pprint(render_frame(A, B))