ASCII-Graphics-Implementation

C++ 구현

위 gif 가 작업물

헬로월드 별찍기 printf 하는 그 콘솔창으로 3D 공간 구현

GPT 적극적으로 활용

서론

(클릭하면 유튜브 영상으로 넘어감)

위 영상을 보고

막연히 저런거 한번 만들어봐야겠다는 생각을 평소 가지고있었고,
이 작업물은 그 생각을 실행으로 옮김

본론

벡터

시작은 일단 벡터부터 만들었음 Vec2 Vec3 Vec4 다 있음

Cross 만 짧게 설명 하고 끝냄
두 벡터 외적해서 노멀벡터(평면에 수직인 벡터) 구하는데 쓰이고, 삼각형 넓이 구하는데도 쓰임

행렬

벡터 만들었으니 이제 행렬 만들어야함

위 그림은 Mat4x4 즉, 4차원 벡터 다룰때 쓰이는 행렬이고, Mat3x3도 있음

Translation, Scale, Rotation 설명하고

LookAt 이랑 Perspective 자세히 설명해보겠음

Translation

translation임 좌표에 값 더해서 평행이동

Scale

scale임 크기 키우거나 줄임

Rotation

Rotation임, 순서대로 z x y 축 회전

LookAt

LookAt 임

카메라가 어디에서 어느위치를 바라보는지? 를 나타내는 행렬임

World Coordinate -> View Coordinate 변환에 쓰임

일단 원리는 위 그림과 같음

카메라 음수위치만큼 translation하고, 카메라 좌표계인 u v n 을 이용해서 회전행렬 만들고

그 둘을 한번에 곱해서 땡처리 행렬 M을 만들면 그게 LookAt 임

유도식 보면,

M 행렬의 translation 부분은 카메라 좌표와 u v n 내적값 음수와 같음을 알 수 있음

그럼 u v n 이 무엇인지지?

카메라 좌표계 x y z 축임

u v n 은 다음과 같이 만들 수 있음

camera 위치, look위치 이용해서 n 벡터를 만듬, 카메라좌표계의 z축임

up 벡터 정해야함, 다음 축 그냥 구할 순 없음, 경우의 수 무한개임

보통 월드의 위쪽을 나타내는 (0, 1, 0) 을 이용함

up벡터랑 n벡터 외적해서 u 벡터 구함, 카메라좌표계의 x축임

n 이랑 u 외적해서 v 구함, 카메라좌표계의 y축임

u v n, 각각 행 순서로 나열한게 왜 카메라좌표계 회전행렬이 되는지?

를 설명하는 증명임

정규화된 단위벡터 각 축에 정사영 때려서 좌표값 구한다고 직관적으로 볼 수 있음

코드는 위와 같음

Perspective

퍼스펙티브는 엔진에서 구현 극히 일부분으로 끝나지만

나름 그래픽스의 꽃이라 생각해서 좀 자세히 이야기 해보겠음

핀홀 카메라의 원리임

그 원리를 그대로 들고옴

prp : projection reference point

cop : center of projection

vp : view plane

prp 랑 cop 는 같은 개념

퍼스펙티브는 쉽게 생각하면

직선의 방정식에서 한 점의 위치 알아내는 것이라고 볼 수 있음

우리는 3d 공간을 2d 이미지로 볼거임

-> 어떻게 보는지?

-> view plane에 점 투영시켜야함

-> 어떻게 투영시키는지?

-> view plane z 위치 미리 정해놓고, 카메라위치랑 보고 싶은 점의 위치로 직선의 방정식 만든다음,

z값 대입해서 투영 시킬 위치 구함

사실 view plane 값이 아니라 s*z + t 를 이용해서 z값을 살리지만 원리는 위와 같음

(Xp, Yp, Zvp) 로 투영될 좌표구할 수 있음

근데 식에 x 랑 y 계수에 z가 들어가있어서 비선형이됨

비선형이면 행렬곱으로 표현을 못함

그래서 동차좌표 4차원 을 도입해서 이 문제를 해결함

이제 정규화 해야함

일반화하려면 중간에 Oblique Projection, Shear도 들어가는데,

구현할 때 안쓰기도 했고, 내용이 난해하니 그냥 넘어감

cliping window 기반으로 -1 ~ 1 크기 정규화를 해야함

정규화를 왜 하는지?

-> 해두면 추후에 뷰포트 변환할 때 편함

보통 일반화된 표현은 위 그림과 같으나

view plane 이랑 near clipping plane은 보통 같게 설정함

다르게 하고 싶으면 행렬식 수정하면 됨

이거 두개 더하면 2*Xprp 인데

Xprp 는 보통 0으로 두기때문

이제 s*z + t 에 대해 다뤄야함

단순 view plane 투영이 아니라, z값을 살리는 투영임

-1 ~ 1 정규화를 염두에두고 s값이랑 t 값이 정해짐

s와 t 값 구하는 식은 다음과 같음

이렇게 된다.

여기에 아 까 s*z + t 에서 유도해냈던 계수인

가 나온다

위에서 설명했던 정규화용 스케일,

이렇게 해서 정규화하는 퍼스펙티브 행렬까지 유도 가능함

위 식을 이용해서 퍼스펙티브 행렬을 최종적으로 다음과 같이 만들 수 있음

구현은 위 그림과 같음

각종 기본 요소들

버텍스 메쉬 트랜스폼 AABB 이렇게 만들었음

이론에는 edge도 있고 plane도 있지만

인덱스 순서와 버텍스 객체 정보를 이용해서 plane을 구성할 수 있으므로
버텍스만 구현해도 괜찮음

크게 이야기 할 부분은 없어서
헤더만 보고 대략적인 파악만 해도 무방함

컬링과 클리핑

이제 뷰볼륨 안에 안들어온 엔티티들 걸러내고
걸친 것들은 잘라내야함

이야기할거리는 크게 세가지 정도 있음

1. frustum plane

2. AABB

3. 클리핑 알고리즘 (sutherland-hodgman 알고리즘)

들어가기에 앞서

MC : model coordinate

WC : world coordinate

VC : view coordinate

P : VC to Clip Space

V : WC to VC

M : MC to WC

라고 용어를 미리 알림

P V는 위에서 다뤘고 ( 각각 Perspective, lookAt ),

M은 나중에 다룰 예정

Frustum Plane

점이 P * V * M * vertex 를를 거치면

위 그림대로, -h ~ h 범위로 뷰볼륨 내외 판정을 할 수 있음

그래서 저 방식대로 구현을 할 생각이었는데

AABB ( Axis Aligned Bounding Box ) 를

이용해서 일단 확실하게 non promising한 엔티티들을 빠르게 걸러내고

그 후에 애매한 애들 클리핑 하는게 좋다고 함

왜냐면 클리핑 알고리즘이 비교적 비싼연산이기 때문

AABB 컬링을 하려면 frustum plane이 필요하고, 그리고 클리핑도

frustum plane을 이용해서 가능하다고 함

그래서 이 방식을 채택했음

그럼 저 frustum plane들을 어떻게 뽑아 낼건지?

평면의 방정식 형태로 나타내면 그게 frustum plane 6개임

이런 원리로 뽑아낼 수 있음

구현은 위 같음

평면의 방정식이 Ax + By + Cz + D = 0 이런식으로 표현되니

A B C D 이렇게 값 4개만 살려서 Vec4 형태로 씀

vertex랑 plane 내적해서 이 값이 0 보다 크면 내부인거고, 음수면 밖임

물론 6개 다 통과해야함

여기서 내가 구현상 겪었던 문제가 2가지가 있었음

ExtractFrustumPlanes() 함수 콜 해서 frustum plane 뽑아 낼 때,

ExtractFrustumPlanes(P)

ExtractFrustumPlanes(P*V)

ExtractFrustumPlanes(P * V * M)

이 세가지중 뭐가 정답인지 모르겠다는 것

그리고 대충 뽑아냈다 치더라도

frustum plane들이 어느 공간에 있는지?

WC? VC? Clip Space?

frustum planes 는 어느 행렬로 뽑아내야 하는가?

일단 M 행렬은 entity 마다 다름,

범용적으로 컬링 및 clipping 해야하는 것에 안맞으므로 PVM 은 탈락

그러면 PV 와 P가 남는데,

vertex 상태가 World Coordinate 이면

ExtractFrustumPlanes(P*V) 로 뽑아내고

View Coordinate 이면

ExtractFrustumPlanes(P) 행렬로 뽑아내는 거임

proved by ac에 근거해서 굳이 증명까지는 안돌렸음

ExtractFrustumPlanes(P*V) 로 평면들을 뽑아냈다 치자, 이 평면들이 어느 공간에 있는지?

아까 위에서 표현했던 평면의방정식의 성분을 표현하면

이렇게 나옴

각각의 값이 평면의 방정식 Ax + By + Cx + D 에서

A B C D를 의미함

이는 아까 위에 써뒀던 A B C D 계수와 일치함을 알 수 있음

결론적으로, PV 로 뽑아낸 Frustum plane은

World Coordinate 공간에 존재하고,

컬링이든 클리핑이든 WC 기준으로 돌아가야함을 의미함

AABB

AABB는 각 엔티티들이 직육면체를 의미하고,

렌더링 과정에서, 클리핑 전에 빠르게 컬링하는데 쓰임

axis aligned라서 딱 min좌표 max좌표 2개로 직육면체를 표현하는게 특징임

AABB 에 대해서 이야기할 것은 다음과 같음

Entity의 AABB 계산

Local AABB to World AABB

Culling AABB from frustum plane

AABB 계산

AABB 는 일단 Model Coordinate 에서 전처리 느낌으로 미리 계산됨

버텍스 쭉 순회하면서 x y z 민맥스 구해서 제일 작은 값, 제일 큰 값 갱신함

이건 메쉬단위고, 이제 엔티티는 여러개의 메쉬로 이루어져있어서 AABB 끼리

Union 연산 해서 최종 엔티티의 AABB를 구함

Local AABB to World AABB

로컬로 존재하는 AABB를 월드로 보낼 때는, 그냥 M 곱해서는 안되고

특별한 과정을 거쳐서 변환되어야함

증명은 아래와 같음

개념은 원의 방정식 d + r , d - r 이랑 비슷한거 같음

코드로 표현하면 위와 같음

Culling AABB from frustum plane

그렇다면 이제 WC에서

AABB랑 frustum plane이랑 어떤 원리가 작용해서 컬링이 가능한지 알아야함

증명은 아래와 같음

코드는 위와 같고

box.max = c + e

box.min = c - e

를 의미함

Sutherland-Hodgman 알고리즘

알고리즘 구현, out -> in, in -> out 일때 교차점 계산하는데

렌더링

이제 렌더링을 해야함

할 이야기 많아서 대충 흐름대로 서술하겠음

일단 Model Coordinate to World Coordinate 부터 이야기 해보겠음

Model Coordinate to World Coordinate

메쉬를 구성하는 폴리곤의 값들은

자기 Model Coordinate에서 정의되어있음

해당 메쉬는 entity에 속해있을 것이고,

해당 entity는 월드에서의 정보인 transform 을 가진다

트랜스폼임

이 정보들로 M 행렬을 만듬

position 이 translation 행렬

rotation 이 rotation 행렬

scale 이 scale 행렬을 만드는데 쓰임

T R S 행렬들을 써서 최종 MC to WC 행렬을 만듬

M 행렬 정의는 위와 같고,

T * Rz * Ry * Rx * S 를 한번에 압축시키면 비용 절감 가능함

괜히 복잡해 보이는데 그냥 행렬 다 곱하는 것임

구현은 위 그림과 같음

이거 가져오면 P V M 대표 세 행렬 중에서 M 행렬 가져오는거임

이제 버텍스의 법선에 대한 이야기를 해야함

Normal Vector Transformation

일단 법선은 그냥 M 을 곱하면 안되고 Inverse Transpose M 을 곱해야함

아래는 왜 Inverse Transpose M 을 써야되는지에 대한 증명임

Normal Vector is not affected by Translation

제일 쉽고 직관적인 증명임

p1 p2 p3 점을 정의하고, 그걸로 외적돌려서 노멀벡터 얻음

각 점들을 t만큼 translation 해도 노멀벡터가 똑같음

결론적으로, 노멀벡터는 translation에 영향을 받지 않음

그래서 M 행렬에서 topleft 3x3만 써도됨

구현은 위 그림과 같음

MC to WC 프로세스에 관한 코드임임

이제 Illumination 구현해야함

Illumination

그래픽스 빛의 종류는는

Ambient, Diffuse, Specular 가 있음

Ambient는 빛반사 주변광 수치로 근사

Diffuse는 주변으로 넓게 퍼지는 빛

Specular는 집중적으로 크게 반사되어서 밝게 빛나는 것

N·L 둘다 단위벡터라 내적으로 cos 나타낼 수 있음

각도 90 넘어가면 내적값 음수인데 이러면 빛반사가 안되니 ambient 항만 살아남음

Specular는 Blinn Phong 썼음

Specular는 카메라 시점에 영향 받음

R과 V의 각도가 좁아질수록 더 밝아지고 쎄짐

V·R 이 저 코사인 표현한거고,

blinn phong은 V·R 을 Normalized( L+V ) 로 대체하는거임, 연산은 블린퐁쪽이 더 쌈

한 씬에 빛이 한개만 있는건 아니므로,

일반화는 위와 같음

구현은 위와 같음

원래 빛쪽에도 rgb를 써야하는데 ASCII로 찍을꺼니 일단 지금 구현은 그냥 float만 쓰고있음

언제든지 수정가능

specular 같은경우는 색값에 함께 곱해버리면 반사광이 물들어버리므로 그냥 따로 더해주는 형식

참고로 셰이딩은 WC 에서 했음

이제 투영한걸 그림으로 찍는 레스터라이즈를 해봅시다

Rasterize

삼각형 그리기

원래는 스캔라인 기법을 생각했는데 생각보다 구현이 힘들어서서

그냥 min max 범위구해서 사각형 범위 2중포문 돌리면서 바라센트릭으로 찍는걸로 했음

직관적이고 쉽고 간단함

삼각형 내부에 점 하나 찍으면, 세개의 삼각형으로 나눌 수 있는데, 세 삼각형의 넓이 비율을 이용하는 거임

이걸로 정점 A B C의 속성들을 interpolation 함 그리고 이걸로 삼각형 내외 판별도 가능함

일단 점을 NDC로 변환한 후, 다시 0~1 구간으로 renormalize함

array에서의 y값은 위에서 아래로 증가하므로, 1.0f 에 다시 값을 빼줘야함, flip 하는거임

그 후,

x 는 width

y는 height 에 곱해서

view window에 어디찍힐지 대략적인 수치를 구함

width, height는 창 가로 세로임

랜더링 전에 미리 정해짐

구현은 이런느낌

min max 직사각형 범위 구해서 그 구간 2중포문 돌면서 삼각형 찍는거임

음수 삼각형 넓이 나오면, 삼각형 외부라는 뜻임, 그러면 찍으면 안되니 continue로 스킵

삼각형 넓이구하는건 외적을 이용함

원래는 1/2 곱해야 삼각형 넓이인데, 어차피 비율을 보는거라 안나눠도 상관없음

Visible Surface Detection

굉장히 많은 방법이 있는데

그냥 제일 쉽고 간단하고 직관적인 Z Buffer method 썼음

일단 모든 삼각형을 그리는데, z 값 비교해서 더 가까운 거 그리는 거임

이거 비교해서 조건 검사 통과하면 z_buffer 값 갱신함

중간 시연

일단 대략적인건 다 이야기 하였음

워낙 구현한게 많아 다 다룰 수는 없어서 생략된게 좀 있음

이야기한거 + 이야기하지 않았던 모든 요소들을 구현하고

그리고 발생하는 온갖 버그들을 디버깅하고 수정하고 난 후의 첫 결과물은 다음과 같음

잘못 그려지긴 하지만 그래도 굴러는 간다는 점에서 의의가 있음

시행착오와 개선

씬 구성에는 directional light를 썼었음
태양광을 의미함

이론도 그렇고 구현도 그렇고 light 벡터는 버텍스에서 광원 쪽으로 향해야함
이부분 실수했었고 수정했음

이 버그 찾는데 무수한 시간이 소요되었음

버그 수정하고 많이 나아졌지만 그런데 아직도 illumination 버그가 있음 일단 이건 차치하고

정육면체 그리면 원래 이렇게 그려짐

위에 그렸던 건 사실 y scale 압축시킨 직육면체였음

이 문제가 발생하는 이유는 console창 char 한칸 cell의 크기가 세로가 더 길기 때문임

콘솔창 셀의 세로가 대충 2배 기니 0.5 곱했음

일단 비율 문제는 해결했는데

아직도 뭔가 문제가 있음

수많은 노가다와 시간간격이 소요된 후,

이게 Z Fighting 문제임을 알아냈음

정육면체라서 버텍스의 Z 값이 같으니 Z buffer method가 제대로 작동을 안함

그래서...

Back Face Removal

일단 이론은
View Coordinate 에서,
polygon의 법선벡터가 음수면 back face 이다 -> 컬링해라
인데

결론부터 말하면
잘 작동안함

Back Face Removal2

back face culling 다른버전임

보니깐 폴리곤 배열된걸 CCW 돌려서
버텍스의 위치만으로 면의 법선벡터를 구할 수 있음

이게 어떻게 가능하냐면
애초에 모델 만들 때,
폴리곤의 법선벡터가 모델의 외부로 향하도록 버텍스 순서를 맞춰서 전처리함

Z 위치만 다른 두 삼각형을 가정해보자,
일반적으론, 저 두삼각형 외적 돌리면 같은 법선이 나와야하는데,
메쉬에 삼각형 집어넣을 때, 하나는 ABC 순서로 집어넣고
다른건 ACB 순서로 집어넣어서 외적돌렸을 때, 다른방향이 나오게 하는거임


그 후 평면위의 아무 한 점 잡아서 (보통 vertex 의 p0)
카메라까지의 방향벡터를 구하고 (to eye)
to eye 벡터랑 내적 돌려서 이게 양수이면 카메라에서 보임, 음수면 back face라 컬링 가능임

위 수식은 간단한 증명임
s(x) 는 삼각형을 포함하는 평면의 방정식
카메라의 위치는 (0, 0, 0) 이 정석이므로 0을 집어넣음

이건 평면위의 아무 점을 잡던간에 판별에 영향을 주지 않음을 보여주는 증명
e1 e2는 평면위의 평행하지 않은 두 벡터이고 이걸로 평면위의 어떠한 점이라도 표현 가능함
내적시켜보면 싹다 0으로 날라가서 부호가 항상 일정함을 보여줌

결론적으로, Back face culling 까지 적용하고 나면

꽤 잘 작동한다

Texture

이제 텍스쳐 만들어야함

이미지 정보가 rgb데이터로 width height 이렇게 존재할텐데
가중치 기반으로 정보 추출해오는 거임

예를들어,예를들어 width 100, height 100 짜리 이미지에 Sample(0.5, 0.5) 한다 가정해보자
그러면 pixel[50][50] 인덱스의 rgb 가져오는거임 (인덱스 디테일은 살짝 다를 수 있음)

CLAMP REPEAT NEAREAST LINEAR는 생략

이런느낌으로 색깔에 곱해서 썼음

그 후,
텍스쳐 매니저 제작
패턴베이크 이미지등록
렌더링 파이프라인에 끼워넣기
수많은 시간간격이 소요된 버그들 수정
등등의 많은 일이 있었지만
이야깃거리는 아니라서 스킵


이제 보정보간 해야함

perspective correct

일단 문제는 다음과 같음

Vertex에는

position,
normal,
color,
uv,

가 존재함

근데 파이프라인은
PVM * vertex 하고,
vextex의 각 x y z 를 w 로 나눠서 ndc로 맞추는데

color랑 uv는 이런과정을 안거친다는 것이고,
이를 바라센트릭 보간 가중치를 그대로 갖다쓰면 왜곡이 발생함

그래서,

보정 보간을 해야하는데
증명은 다음과 같음

이를 NDC 로 투영시키면
위 수식과 같이 나옴

color든 uv든,
바라센트릭으로 레스터라이즈할때, 이 수식으로 구현해야함

구현은 위와 같음
u_over_w, r_over_w ..
등등은 u/w , r/w 랑 같음
연산감소용으로 미리 전처리해서 구해두는 값


아무튼 최종적으로

체커텍스쳐 적용

벽돌 텍스쳐 적용

결론

이제 온갖 구현된걸 기반으로

메인이랑 엔진 사이에

인풋핸들러 카메라컨트롤러 월드메이커 같은 추상층 만들고 그걸 기반으로 공간 만들면 다음 GIF 같이 나온다

Further Work

방향성은 매우 많은 듯함

1. 멀티쓰레드, GPU 등의 병렬화 및 analysis

2. 스타1, 메월 같은 2D 플랫폼에 그대로 이식해서 3D게임 만들기

3. 레이트레이싱

4. 이대로 DOOM 제작

5. 코드 최적화

6. 각종 기법들 적용해보고 성능 analysis

등등 있고 이중 하나를 골라잡아 진행할 예정