[알고리즘]마칭큐브 알고리즘 - 1

1. 마칭큐브란?

The algorithm was developed by William E. Lorensen and Harvey E. Cline as a result of their research for General Electric. At General Electric they worked on a way to efficiently visualize data from CT and MRI devices. - wikipedia

대충 요약하면

General Electric 에서 CT와 MRI 장치들의 효과적인 시각화를 위한 연구결과로, William E. Lorensen 와 Harvey E. Cline 의해서 개발되었다.

그렇다, CT와 MRI 등의 의학 기기들에 적용하기 위해서 개발된 기술이란것을 알 수 있다.

그렇다면, 이 알고리즘이 무엇을 하길래 이런 의료기기에 적용한다는 걸까?

내용을 유추해본다면, CT 혹은 MRI등에서 무언가(사람, 동물 등)를 스캔하여 나온 데이터가 있을것이다.

근대 이것을 시각화 한다는게 무슨 소리일까?

카메라는 단순하게 보이는 그대로 찍는다. 그렇다고 카메라가 단순한 물건이라는 것은 아니다, 다만 사진은 보이는 그대로 단순하게 2차원으로 "찍는다".

이런 장비들은 단순하게 사진처럼 그대로 찍을 순 있지만, 여기서는 2차원 시각화가 아닌, 3차원 시각화를 하려는 것이다.

점이 모이면 선이되고, 선이 모이면 면이된다.

이런식으로 3D상에서 점(정육면체)을 이용해서 표현하는것을(마치 2D의 도트 그림 처럼, 사실 대부분의 이미지는 매우 작은 점으로 표현되어 있다) 복셀(Voxel) 이라고 한다.

복셀의 장점은, 해상도가 높을수록 매우 자연스럽다는것이다.(게임, 영화화 등에서 연기, 물 같은 효과를 리얼하게 주기위해서 복셀을 적용하는 경우가 많다)

단점은 간단하다, 연산량이 엄청나다.. 그렇다고 해상도를 낮추면 낮을수록 모양이 이상해진다.

2020년 지금의 기술로 일반 컴퓨터로는 연산량이 부족하다.

여기서 '마칭큐브'가 나온다.

복셀의 그래픽을, 우리가 흔히 쓰고있는 폴리곤 형식으로 바꾸는 것이다.

이해를 쉽게하기 위해서, 3차원이 아닌 2차원으로 생각해보자.

이런식으로 정사각형의 상자들로(도트) 좌표를 이룬다고 생각하자( 3차원에선 복셀 )

사진으로만 봐도, 도트의 해상도는 매우 낮다

그리고 어떠한 물체가, 빨간색 선 처럼 생겼다고 생각하자

이것을, 2차원 도트로 표현하자

표현 방법은, 사각형의 반절 이상을 차지하면, 파란색으로 칠한다.

이런 모양이 나올것이고, 여기서 한가지 문제에 직면한다.

"원형이랑 모양이 너무 다르잖아?"

위에서 말했던, 저 해상도 = 모양이 이상해진다 = 원형이랑 많이 다르다.

바로 이 문제가 발생하고, 이것을 해상도를 높이자니 3차원 환경에선 연산량이 감당을 못 한다.

그러면 어떻게 할까?

"마칭큐브" 알고리즘을 사용하면 된다.

드디어 마칭큐브 알고리즘을 본격적으로 알아볼 수 있겠다.

빨간색 선이 그리는 모양이 각 도트의 꼭짓점를 포함하면 동그라미를 쳐보자

추가로! 빨간색 선이 다음 사각형에 얼마나 가까워졌는지 값을 ISO 값이라고 하겠다

그리고 이 ISO값이 0.5 이상만 동그라미를 쳐주면 되겠다

(제일 위헤서, 우측 모서리에 동그라미를 깜박하고 안그렸다)

아마 사진을 보더라도 이해가 안될것이다, 그냥 넘어가자

다음 사진을 보면이해가 될 수 있을것이다.

이런식으로 점을 찍을 수 있을것이다.

그래서 저 점들을 이용해서 뭘 하려고?

선을 그려주자!( 3차원으로 말하자면 폴리곤을 만들어 주자! )

하나의 도트에 4개의 꼭짓점이 있다.

각각의 도트에 찍힌 점의 갯수 및 모양에 따라 선을 그려주면 된다.

점 주변의 모서리 중앙에서, 점 주변의 각각의 모서리의 중앙을 대각선으로 선을 그려서 다이아몬드 모양으로 선을 그려준다.

점이 서로 붙어있다면, 일직선으로 선을 그려준다

점이 기준이 아닌, 도트를 기준으로 체크하는 방식이며, 도트의 꼭짓점 4개에 모두 점이 있다면, 선을 그리지 않는다.

하나의 꼭짓점만 점이 찍혀 있다면, 이 경우에 해당하는 대각선을 그려준다고 생각해보자.

꼭짓점에 2개, 3개의 점이 찍혀있다면, 이에 해당하는 그림을 그린다고 생각해보자.

이해가 안된다면 아래 사진을 보자.

이 사진은, 3개의 점이 찍혀있고, 각 도트가 꼭짓점에 찍힌 점의 갯수와 위치에 따라 선을 그린걸 표현한것이고

이해를 돕기위해, 도트마다 색을 넣어주었다.(선의 색갈도 맞추었다)

이런식으로, 도트의 각 꼭짓점에 찍힌 점의 갯수(위치)를 따라 선을 그려주는것이다.

그리고, 이 선을 그리는 경우의 수는

2 * 2 * 2 * 2 = 8 일 것이다! (2 ^ 4)

그러면, 이것을 리스트를 만들어서 정리할  수 있지 않을까?

좌측 하단의 꼭짓점이 1번

우측 하단의 꼭짓점이 2번

좌측 상단의 꼭짓점이 3번

우측 상단의 꼭짓점이 4번

이렇게 1, 2, 3, 4가 있다면

이것을 2진법으로 표현할 수 있다

0 0 0 0

좌측부터 1번 꼭짓점이라 하자

그러면, 사진의 파란색 도트의 경우에는

0 0 0 1

이렇게 표현 할 수 있다

=> 꼭짓점의 찍힌 위치에 및 갯수에 따라 숫자로 정의할 수 있다

=> 리스트를 만들면 도트의 꼭짓점 상태에 따라 해당하는 목록을 바로 찾을 수 있다!

즉, 마칭큐브는 룩업 테이블(리스트)를 만들어서, 복셀의 꼭짓점의 상태(위치와 갯수)에 따라 폴리곤을 어떻게 만들지 미리 계산해둔것이다.

참고로 3차원(복셀, 정육각형)의 꼭짓점은 8개 이므로, 마칭큐브의 경우의 수는 2^8 = 256 가지의 경위 수가 있다

그럼 다시 2차원으로 돌아와서, 아까의 빨간색 선을 마칭큐브 알고리즘을 이용하여 그려보자.

이런 모양이 나올것이고, 아래의 사진은 빨간색 선을 조금 수정하였다.

점이 하나 사라졌고, 그에 따른 선을 그렸다.

빨간선을 무식하게 도트 표현한것보다, 원형모양과 비슷하다.

즉, 저해상도 복셀에서도 폴리곤으로 원형과 비슷하게(상대적으로) 표현할 수 있다.

그리고, ISO값을 기억하는 사람이 있는가? 추가로 이해한 사람이 있는가?

이 ISO값에 따라서 대각선이 점에 더 가깝거나 멀게 그릴지 연산도 가능하다!

그냥 점에다가 ISO값을 기록하고, 선(폴리곤)을 그릴때 이것을 고려하여 그려주면 된다.

즉, 위에는 극단적으로, 점이 있음 or 없음 으로 2차원을 예시로 들었다. 그럼에도 상대적으로 도트로 표현한 것보다 상대적으로 원형에 가까웠다.

ISO 값을 이용하여 점에 더 가깝거나 멀게 그린다면? 더욱 더 원형에 가깝게 그릴 수 있을것이다.

미리 선(폴리곤)을 연산(저장)해서서 룩업 테이블에 저장해놔서, 선(폴리곤)을 그리는게 상대적으로 적은 연산이 들어간다. (도트에 점이 어떻게 찍혀있나 연산을 해주고, 룩업 테이블에서 해당 선(폴리곤)을 찾아 그려주면 끝난다)

이것을 사용하여, CT/MRI 에서도 적은 연산으로( 혹은 적은 데이터? )으로 원형과 비슷하게 3차원 그래픽으로 표현 할 수수 있다.

마칭큐브가 적용된 게임은, 흔히 이러한 특성 때문에 복셀 게임이라고 부르기도 한다(아마도ㅎ정확한건 모르겠다ㅎ)

대표적인 마칭큐브를 사용한 게임으로는 아스트로니어, 마인크래프트가 있겠다.

??? 마인크래프트는 정사각형 세계인데?!!, 이거 그냥 복셀만 사용해서 만든거 아니냐?

우리가 예시를 점의 유/무 에 따라서 극단적으로 그림을 그렸던것 처럼, 마인크래프트는 ISO값을 이용하여 더욱 더 극단적으로 연산한것이다.

추가로, 모든 꼭짓점에 점이 있으면, 선(폴리곤)을 그리지 않는것도 기억하는가?

순수한 복셀 그래픽은 모든곳에 박스를 표현하기 때문에, 연산량이 어마어마 하지만, 이러한 마칭큐브 특성 때문에, 안보이는곳은 연산을 하지 않는다!

아무튼, 약간의 꼼수지만, 마칭큐브를 이용해서 복셀을 구현?했다!

이러한 특성 때문에, 마인크래프트 처럼 마칭큐브가 적용된 게임을 복셀게임이라고 부른다.(아마도)

여담으로 마크에 대해서 좀 더 이야기 하자면

마인크래프트는 각 점에 추가로 블럭의 정보등을 담아서 블럭을 표현한것이다.

보통 컴퓨터는 무한한 숫자를 기록하는것은 매우 힘들기에, 매우 많은것을 넣어야 할 경우에는 약간의 꼼수를 부린다.

(연결 리스트라던지 기타 등등 있다)

마인크래프트의 경우에는, 청크 하나를 만들어서, 거기에 블록 여러개를 넣어버리는것이다.

즉, 마인크래프트는 청크 하나에 여러가지의 블록을 쑤셔 넣고 그것을 맵으로 구현한것이다.

맵을 이동하다보면, 로딩이 큐브 하나하나 되는것이 아니라, 큰 박스(청크) 단위로 로딩이 되는 이유다.

최근에 마칭큐브를 이용한 게임들이 은근 자주 보이고, "페리아 연대기" 라는 게임은 출시도 못하고 관짝에 들어가 버렸다. 엌ㅋㅋㅋ

마인크래프트만 보더라도 은근 오래된 게임이다. 즉, 게임에 적용되기 시작한지는 오래 되었다.

다만, 아직까지 컴퓨터로도 이런 꼼수?를 부려도 복셀을 구현하는것에 매우 큰 연산이 필요하므로..

최적화 병신이네 ㅋㅋㅋ 라는 타이틀을 가진 경우가 많다(마크는 자바로 만들어서 그냥 병신인것)

소스코드 예제는 다음시간에~