프로그래밍 언어 입문서가 아닌 프로그래밍 기초 개념 입문서
문과생, 비전공자를 위한 프로그래밍 입문책입니다.
jobGuid 꽃미남 프로그래머 "Pope Kim"님의 이론이나 수학에 치우치지 않고 실무에 곧바로 쓸 수 있는 실용적인 셰이더 프로그래밍 입문서 #겁나친절 jobGuid "1판의내용"에 "새로바뀐북미게임업계분위기"와 "비자관련정보", "1판을 기반으로 북미취업에 성공하신 분들의 생생한 경험담"을 담았습니다.
Posted by rihwan
안녕하세요. 처음으로 글을 쓰는 rihwan (유인환) 입니다. 사실 이렇게 글을 쓰는 것은 참으로 오래 간만이라 살짝 어색하지만, 나름대로 열심히 써보도록 하겠습니다. 우선 간략하게 제 소개를 드리면 저는 현재 대학원에서 석사 과정으로 그래픽스를 공부하고 있고, 또 박사를 들어가려고 준비하고 있습니다. 그리고 제 주요 관심사는 Photorealistic rendering과 Real-time rendering 이렇게 주로 2가지 분야입니다. 제 공부의 목표 중 하나는 Photorealistic scene을 실시간으로 만들어내는 것이죠. 이 부분에 대해서는 나중에 다뤄보도록 하겠습니다.

앞으로 저의 목표는 Siggraph, Eurograph, 그리고 Siggraph Asia의 논문을 분석하고 또 게임에 응용할 수 있는 방법에 대해서 제 생각을 얘기하고 또 토론을 해보고 싶습니다. 하지만 곰곰히 생각해보니, 무작정 저 논문들을 이해한대로 그대로 쓰고 끝냈다가는 중간의 내용이 너무 붕뜨는 경향이 있을 것 같아 천천히 하나씩 가장 쉬운 부분부터 복잡한 부분까지 최대한 자세히 써보고자 합니다. 물론 부족한 부분이 매우 많을 것이므로, 틀린 부분을 찾으시면 과감히 지적해주시면 수정하도록 하겠습니다.

앞으로 제가 관심있게 분석해볼 논문들은

Ray Tracing 계열
 - Ray Casting
 - Simple Ray Tracing
 - Distributed Ray Tracing
 - Path Tracing
 - Photon Mapping

Character Animation 계열
 - Mesh Deformation
 - Skeleton animation

Subdivision & Level of Detail 계열

Fluid Simulation 계열

Large scale rendering 계열
 - Terrain
 - Character

Etc...

이제 잡담은 그만하고 바로 본론으로 들어가 보겠습니다. 오늘은 "Automatic Rigging and Animation of 3D Characters" 라는 2007년 Siggraph 논문입니다.

논문은 아래의 링크를 따라가시면 있습니다.
http://www.mit.edu/~ibaran/autorig/

링크에 들어가시면 비디오, 논문 (PDF), 소스 코드, 실행 파일까지 해서 모두 공개되어 있습니다. 그러니 한번 직접 실행해보시면 이 논문의 목표를 이해하는데 도움이 됩니다. 혹시나 영어로 써 있어서 움찔하시는 분들을 위해서... 우선 실행을 직접 해보기 위해서 아래의 링크를 우선 갑니다.

http://www.mit.edu/~ibaran/autorig/pinocchio.html

그럼 Windows Binary라고 있는데, zip 파일을 다운로드 합니다. 그리고 압축을 어딘가에 풀어주시고, 콘솔 윈도우를 열어 해당하는 디렉토리로 들어갑니다. 그리고 다음과 같이 쳐서 실행합니다.

"DemoUI.exe /data/cheb.obj -motion /data/walk.txt"

위의 명령에서 첫번째 argument인 /data/cheb.obj는 메쉬 데이터입니다. OBJ 파일 포맷은 3D Mesh를 정의하는 ASCII 파일 포맷으로 매우 단순한 포맷이기 때문에 자주 사용되고는 합니다. 거의 Position, Normal, Texture, Index, Material 정보만을 포함하는 문자열 포맷입니다. 그리고 두번째 argument인 -motion은 다음에 나오는 것이 에니메이션 데이터임을 의미하고, 마지막의 /data/walk.txt는 실제 에니메이션 정보만을 가지고 있습니다.

위 이미지는 프로그램을 실행한 모습입니다.

해당하는 모델 파일은 아래와 같습니다. 즉 아무 것도 없는 메쉬 파일에다가 뼈대를 끼워맞추고 에니메이션을 적용하는 것이 목표입니다.


Rigging이라는 용어를 이해하기 위해서는 기본적으로 Skeleton animation이 돌아가는 방식에 대해서 살짝 언급할 필요가 있습니다. Skeleton animation은 사람이 움직이는 방식을 본 뜬 에니메이션 방법입니다. 사람이 움직일 때 우선 근육이 뇌의 명령에 따라서 수축 및 이완을 하고 그 수축 및 이완된 힘이 사람의 뼈를 움직이게 합니다. 단단한 뼈대가 움직이면서 사람이 움직이게 됩니다. 당연히 그에 따라서 당연히 사람의 겉모습(피부, 스킨)도 움직이게 되지요. 물론 가장 정확하게 사람의 움직임을 표현하려면 근육을 시뮬레이션해야 겠지만, 그것은 사실상 게임에서는 너무 계산량이 커서 현재까지는 거의 불가능해 보입니다. 하지만 근육은 무시하고 피부가 뼈대에 붙어 있다고 생각하여 실제로 뼈대만 움직이고 피부는 뼈대를 따라 움직이게 할 수 있다면 에니메이션을 만들어내는 것이 생각보다 단순해질 수 있습니다. 위와 같은 이유로 Skeleton animation이 만들어졌지요. 여기서 피부를 뼈대에 붙이는 작업을 Rigging이라고 합니다.

다시 얘기해보면, 피부(skin)은 정점과 인덱스들로 구성되어 있습니다. 그리고 각각의 정점은 일부의 뼈대로부터 영향을 받게 되어 있습니다. (좀 더 정확한 내용을 보고 싶으시다면 Real-Time Rendering 제 2판의 76 페이지 부분을 살펴보시면 좀 더 자세히 설명되어 있습니다. 또는 해골책이라고 불리우는 IT EXPERT 3D 게임 프로그래밍을 보셔도 해당 내용이 훨씬 자세히 설명되어 있습니다) 예를들면 팔꿈치의 피부는 팔의 윗부분 뼈(윗팔뼈)와 아랫부분 뼈(자뼈 & 노뼈)의 영향을 동시에 받게 됩니다. 이와 같이 각각의 피부(정점)이 어디어디의 뼈에 어느 정도의 영향을 받는지를 설정하는 것을 Rigging이라고 합니다.

한가지 Rigging의 문제점은 모델러 또는 에니메이터분들이 Rigging을 하는데 생각보다 오랜 시간이 걸린다는데 있습니다. 또 변경하는 것도 쉽지가 않습니다. 따라서 만약 Rigging을 자동적으로 계산해낼 수 있다면 모델러와 에니메이터분들께 매우 큰 도움이 될 수 있으며, 또한 하나의 에니메이션 뼈대를 가지고 여러개의 메쉬에 바로바로 Attaching을 할 수 있게 됩니다. 이 것은 엄청난 장점이 될 수 있는 것이, 만약 에니메이션 동작 하나를 디자인해놓고, 이 동작을 여러 모델에 바로 적용할 수 있으면 게임 제작하는데 엄청난 효율성을 주게 되지요.

But! 그럼 이 논문이 주는 방법이 완벽하냐? 제가 테스트해보고 확인해본 바로는 완벽하지 않습니다. 제한 조건이 꽤나 까다롭습니다. 모든 메쉬는 closed여야 합니다. 의미는 모든 삼각형은 서로서로 완벽하게 연결되어 있으며, 어디에도 빈틈이 없어야 한다는 의미입니다. 또한 뼈대의 구조와 비슷한 메쉬의 형태를 가지고 있어야 합니다. 또한 뼈대는 미리 정의된 빼대만을 허용하고 있으며 손가락등의 디테일은 표현할 수 없습니다.

하지만 위의 단점에도 불구하고 주는 장점이 매우 크며, 약간 제한적으로 적용한다면 게임에도 적용할 수 있다고 저는 생각하고 있습니다. 그래서 이제 자세히 분석을 해보자면...

이 논문은 2개의 중요한 카테고리로 나눠져 있습니다. 첫번째는 미리 정의된 뼈대를 mesh에 끼워맞추는 작업입니다(embedding). 두번째 작업은 끼워맞춰진 뼈대를 가지고 heat diffusion 방정식을 사용해서 각 피부의 정점에 어떤 뼈대가 어느 정도의 영향을 끼치는지 계산해내는 작업입니다.

Skeleton embedding
만약 존재하는 하나의 메쉬가 있다고 했을 때 그 메쉬 안에 미리 정의된 뼈대를 (비율을 조절하고, 또 위치를 좀 바꿔서) 가장 잘 집어 넣는 방법이 이 작업의 목표입니다. 이 작업은 사실 완벽하게 해결하기란 거의 불가능에 가깝습니다. 그래서 여기서 제시하고 있는 해결책도 사실 완벽하다고 볼 수 없습니다.



1. 캐릭터를 우선 Unit scale로 re-scaling 합니다.

2. Distance Fields를 계산합니다. 여기서 Distance Fields라는 것은 3 차원에서 하나의 점이 있을 때 그 점에서 가장 가까운 Mesh에서의 거리를 의미합니다. 즉 가장 가까운 삼각형을 찾고, 또 그 가장 가까운 삼각형에서의 정확한 거리를 계산한다는 의미입니다. 일반적인 거리는 양수와 음수가 없으므로, 안인지 밖인지가 구분되지 않습니다. 따라서 여기서는 삼각형의 normal을 이용해서 안과 밖을 구분하는 것으로 보이는데 이 부분은 정확하지는 않습니다. 어쨋든 양수와 음수를 구분해서 메쉬의 안인지 밖인지를 구분할 수 있도록 Distance field를 계산합니다. 이 계산은 3D Volume 데이터로서 계산하는 것이 아니라 Octree로 메쉬를 나누고 그 Octree의 하나의 셀마다 계산한다는 의미입니다.

3. Octree에 기록된 Distance field 값을 기준으로 하여 뼈대의 위치가 될 수 있는 후보군을 추출해냅니다. 이 추출은 값의 연속성(C1 continuity)을 기준으로 하여 다른 셀과 비교하여 결정하게 됩니다.

4. 3번에서 추출된 후보군들을 가지고 우선 거리 순으로 정렬을 하고 다시 거리가 큰 순서로 sphere를 만들어냅니다. 이 중에서 sphere는 다른 sphere의 center를 포함할 수 없다는 규칙도 동시에 가지고 있습니다.

5. 4번에서 추출된 sphere들을 가지고 graph 구조를 만들어냅니다. graph 구조를 만들 때 서로 겹치는 sphere들을 연결하여 만듭니다.

6. graph 구조를 skeleton과 비교하여 graph를 노드들을 일부 제거합니다. skeleton과 같은 수준의 joint를 가지도록 조절하게 됩니다. 이 부분은 살짝 애매하네요...

7. 나머지 작업은 해당하는 본을 끼워넣는 작업입니다. 이 부분에서는 뼈대의 비율들, 뼈대의 축들, 그리고 뼈대의 사이즈를 미리 정의된 뼈대와 비슷하도록 6번에서 계산된 결과를 수정하는 작업을 의미합니다. 또한 여기서는 정점 내에 들어갈 때 좀 더 잘 맞도록 수정하는 작업도 포함하고 있습니다. 수학적인 계산들이 들어가며 모든 조건을 만족시키는 완벽한 해법은 사실상 존재하지 않기에 테스트와 또 penalty function이라는 것을 두어 어느 비율, 축, 사이즈에 대한 가장 적절한 해법을 제시하고 있습니다.

위의 과정을 마무리하게 되면 사실 mesh에 끼워맞춰진 skeleton이 나오게 됩니다. 이렇게 나온 skeleton은 제가 테스트해본 결과 사실 가끔 에러가 있습니다. 메쉬가 잘 영역이 구분되어 있어야 에러가 없어지는 경향도 있었구요.

Skin Attachment
이 논문에서는 Linear Blend Skinning(LBS)라고 불리우는 사실은 가장 일반적인 형태의 Skinning을 사용하고 있습니다. 또 가장 일반적인 형태의 Skinning에서는 하나의 정점에 여러개의 본(일반적으로 최대 4개)이 각각 자기의 영향력 (W_i)를 가지고 있습니다. 즉 피부를 뼈대에 붙이기 위해서는 각각의 정점에 대해서 어느 뼈대가 영향을 미치는지, 그리고 어느 정도 영향을 미치는지를 계산해내어야 합니다.

이 계산을 위해서 조건이 몇가지 있는데, 우선 mesh의 resolution에 관계가 없어야 합니다. 즉 삼각형이 몇개든 관계없이 정확하게 계산할 수 있어야 합니다. 뼈대의 영향력은 부드럽게 변화되어야 합니다. 세번째 조건은 두 뼈대의 근처의 정점의 두 영향력은 거의에 어느 정도는 비례해야 합니다. 가까운 뼈대가 더 영향력을 많이 주어야 한다는 의미입니다. 위 조건을 만족하는 방법으로 이 논문의 저자는 heat diffusion 방정식을 제시하고있습니다. heat diffusion 방정식의 평형 조건은 위 3가지 조건을 만족시키기 때문입니다. 사실 heat diffusion 방정식은 매우 많은 영역에 사용되고 있으며 그 부분을 skin weights(각 정점의 붙은 뼈때의 영향력들)에 응용한 것이죠.


사실 정상적으로 heat diffusion 방정식의 평형 상태(equilibrium)을 계산해내기 위해서는 volumetric 연산을 해야 하지만 너무 느려서 여기서는 메쉬 위에서 해당 방정식을 근사하는 방법을 택합니다.

논문에서는 수학적으로 좀 더 자세히 설명하고 있습니다. 이 부분은 사실 좀 저도 완전하지는 않고 희미하게 이해하고 있습니다. 그러니 좀 복잡하다 싶으면 그냥 건너뛰셔도 관계는 없습니다. 사실상 목표와 해법은 제시되어 있고 실제로 어떻게 계산하느냐에 대한 부분이니까요. 이 부분을 이해하시면 직접 구현할 수 있습니다만, 목표는 이 논문의 전체적인 흐름을 이해하고 응용하는 것이니까요. 아래는 평형 상태인 heat diffusion 방정식이고...


i = i 번째 bone
j = j 번째 vertex

첫번째 term인 -w^i 는 △는 discrete surface Laplacian
w^i는 벡터. i 번째 bone으로부터 받는 영향력 벡터입니다
p^i는 벡터. 만약 j번째 정점의 가장 가까운 bone이 i인 경우에만 1이고 나머지의 경우는 모두 0입니다.
H는 행렬. H_jj = c / { d(j)^2 }. d(j) = j번째 정점의 가장 가까운 bone과의 거리. c는 상수.

즉 위 공식은 복잡해보여도, 전체적으로 보면 단순한 계산입니다. 우선 bone을 기준으로 정점을 선택하거나 아님 정점을 기준으로 bone을 선택하던지 간에 관계없이, bone (i 번째)와 vertex (j 번째)가 선택이 되면 가능한 weight을 계산하는 방법입니다. laplacian 연산을 통해서 부드럽게 미분된 형태의 weight 값을, 그리고 두번째 H*weight을 통해서 거리에 의한 영향력을 연산하고 있으며, 마지막 H*p는 전체 합은 항상 1이 되게끔 (equilibrium)을 만족시키고 있습니다. 위의 연산을 모두 하게 되면 각각의 정점마다 어느 bone으로부터 어느 정도의 영향력을 받아야 하는지를 모두 계산해낼 수 있습니다.

장점 & 단점 분석
자동적인 Rigging을 위한 Heat diffusion 부분은 매우 unique하며 다른 많은 논문에서 이 아이디어를 차용하고 있습니다. 물론 계산된 결과도 매우 훌륭하지요. 하지만 skeleton embedding에 대한 부분은 결과는 그럭저럭 괜찮아 보이지만, 완전하지 않습니다. 특히 또다른 논문 (Skeleton Extraction by Mesh Contraction)에서 제시하고 있는 방법에 비하면 단점이 많습니다 (http://visgraph.cse.ust.hk/projects/skeleton/). 그래서 만약 두 논문을 합치면 생각보다 좋은 결과물이 나올 것으로 보입니다만, 이미 비슷한 아이디어 (완전히 같지는 않지만 비슷한 연산을 하는)로 나온 논문이 존재합니다.

어쨋든 게임의 실무적으로 보자면 Skeleton embedding을 방금 제시한 Skeleton Extraction By Mesh Contraction을 이용해서 처리하고, Heat Diffusion을 이용하여 skin weights를 계산해낸다면 하나의 동작을 여러개의 메쉬에 바로바로 적용할 수 있을 것으로 생각됩니다.
TAG

댓글을 달아 주세요

  1. Favicon of http://twitter.com/choijaekyu 최재규 2011.12.25 14:08  댓글주소  수정/삭제  댓글쓰기

    오오!! 앞으로 기대하겠습니다ㅎㅎ

  2. Favicon of https://gamedevforever.com 김포프 2011.12.25 15:12 신고  댓글주소  수정/삭제  댓글쓰기

    역시 인환씨는 논문을 제대로 이해하고 파시면서도 실용성의 끈을 절대 놓지 않는 드물고도 멋진 연구자/프로그래머~~ ^^ (이 분 프로그래밍 경력도 꽤 되요.. 최근에 연구 더 해보시겠다고 유학가셨음. 요리왕의 꿈도 점점 이뤄가시는듯 하지만.... -_-)

    좋은 글 계속 기대하겠습니다. ^^

    • Favicon of https://gamedevforever.com rihwan 2011.12.26 18:17 신고  댓글주소  수정/삭제

      음 감사합니다. 위에 내용이 저도 완전히 이해하지 못한 내용들이 있는지라 좀 중간에 대충 쓴 내용이 있는 듯 해서 좀 그렇지만, 사실 목표가 세부적인 내용을 완벽하게 이해하는 것보다는 전체적인 흐름을 따라가는거라서 우선은 이렇게 써놨어요 ㅋ 좀 반응을 보면서 수정해야 할 듯 합니다요. ㅋ

  3. Favicon of https://gamedevforever.com 귀거리 2011.12.26 09:56 신고  댓글주소  수정/삭제  댓글쓰기

    반정도만 이해하겠어요....저 기호와 공식들은......ㄷㄷㄷ

    • Favicon of https://gamedevforever.com 대마왕J 2011.12.26 11:02 신고  댓글주소  수정/삭제

      으윽 반이나 이해하시면 설명좀 해주세요 OTL

    • Favicon of https://gamedevforever.com 귀거리 2011.12.26 14:11 신고  댓글주소  수정/삭제

      그...그게......그러니까....아....다시보니 10프로? ㅎㅎ후

    • Favicon of https://gamedevforever.com rihwan 2011.12.26 18:20 신고  댓글주소  수정/삭제

      저도 수식은 반만 이해하고 있어요. Larplacian의 경우는 미분을 통해서 부드럽게 값을 흐트러트리는데 목표가 있습니다. 그래서 저 위에 -△w^i은 w^i를 부드럽게 미분한다는 의미입니다. w^i는 벡터이구요. 그리고 H는 대각행렬이고, 위에 보시는대로 가장 가까운 삼각형의 거리의 역을 취하고 있습니다. 그러니까 거리가 멀수록 weight는 줄어들게 만드는거지요. 마지막 p^i는 대각 행렬에서 원하는 값 (1또는 0)만 남기게 만들어서 전체적으로 평형 상태(Equilibrium)를 만들게 해줍니다. 저도 각각의 텀만 이해하고 있고, 그 세부적으로 어떻게 연산했는지는 확인해보지 않았습니다. (죄송 ㅋ)

  4. Favicon of https://gamedevforever.com 대마왕J 2011.12.26 11:02 신고  댓글주소  수정/삭제  댓글쓰기

    훌륭한 내용입니다! 앞으로도 기대할께요!! 논문분석 해주세요!!!

  5. Favicon of https://twitter.com/#!/dozingLamb/following/tweets 잠자는양 2011.12.26 12:23  댓글주소  수정/삭제  댓글쓰기

    에니메이션에 관해 정리가 잘된 책으로
    Game Engine Architecture 저자 JASON GREGORY를 추천합니다.
    100 페이지가 넘는 분량으로 기본 부터 응용 까지 정리가 잘되어 있어요.
    (번역본은 존재하지 않습니다)

  6. Favicon of https://hgcoder.tistory.com hgcoder 2011.12.26 19:31 신고  댓글주소  수정/삭제  댓글쓰기

    스키닝 공식을 코드로 보면 좀 어떠실까요?

    Blend이니 Weight합은 1이 되구여

    matResult = matPalette[blendIndex[0]] * weight[0];
    matResult += matPalette[blendIndex[1]] * weight[1];
    matResult += matPalette[blendIndex[2]] * weight[2];
    matResult += matPalette[blendIndex[3]] * weight[3];

    worldPos = localPos * matResult;

    코드로 보면 좀 간단해보이실거 같아서 올려봤어요 ㅎ

  7. Favicon of https://gamedevforever.com 김포프 2011.12.27 03:07 신고  댓글주소  수정/삭제  댓글쓰기

    'rihwan'이라는 태그를 달았습니다. 필자별 검색을 돕기위해 ^_^ 다음부터 달아주세요~

  8. 유래너스 2011.12.27 17:24  댓글주소  수정/삭제  댓글쓰기

    오..피노키오 군요.

    애니메이션 계통에서는 유명한 논문이네요.^^

    앞으로도 좋은 논문 많이 설명해주세요~ 기대하겠습니다~ ^^

  9. 유래너스 2011.12.27 19:16  댓글주소  수정/삭제  댓글쓰기

    한가지만 더 적어보자면 laplacian의 기하학적 의미는 "주변값들의 평균값과 자신의 차" 라고 생각하시면 될 듯 합니다. 즉, 자기가 주변의 평균값보다 높은가 낮은가 를 생각하기 위함이라고 이해하시면 될 듯 하네요.