'프로그래밍'에 해당되는 글 31건

  1. 2009.10.27 TDD에 대한 단상 2
  2. 2009.02.17 행렬 구현
  3. 2009.02.11 크리티컬 섹션 문제
  4. 2009.02.07 단위 변환
  5. 2009.02.03 벡터는 벡터일 뿐
  6. 2009.02.02 데크란 말이다!!
  7. 2009.02.01 충돌처리
  8. 2009.01.28 통계자료 수집
  9. 2009.01.27 개발 계획
  10. 2008.06.25 Dark Side of the Source
dev.log2009. 10. 27. 04:15
TDD는 코딩 전에 테스트를 정의하는 방법론이다. TDD가 말하는 바는, 작성하는 코드가 어떻게 동작하여야 하는지를 정의하고, 이 정의에 부합하도록 동작하는지, 그리고 이 정의에 부합하지 않는 쪽으로 동작하지 않는지를 검증하는 코드를 먼저 짜야 한다는 것이다. 내가 지금까지 코딩해왔던 방식이랑 비교하자면, 난 일단 특정 모듈의 행동양식을 정의하고, 사용처에서 사용하고자 하는 방식을 적어놓고 컴파일해본다. 컴파일 에러가 모두 사라지고 구현하면 동작하는 코드가 나오는 방식.
의식의 흐름 기법으로 정리해 보면.
  1. "파일에서 뭘 하나 읽어와야겠군"
    int XXX::open_file( const string& filename )
    {
    }
  2. "그럼 스트림을 추상화해야겠군"
    int XXX::open_file( const string& filename )
    {
        stream file( filename );
        file.read( this->buffer, this->size );
    }
  3. "컴파일 에러로군"
    class stream
    {
    public:
        stream( const string& name );
        int read( void* buffer, size_t size );
    };

    int XXX::open_file( const string& name )
    {
        stream file( name );
        return file.read( this->buffer, this->size );
    }
  4. "구현을 해야겠지?"
    class stream
    {
    public:
        stream( const string& name );
        int read( void* buffer, size_t size );
    };

    int XXX::open_file( const string& name )
    {
        stream file( name );
        return file.read( this->buffer, this->size );
    }

    stream::stream( const string& name )
    {
        // ...................
    }
    int stream::read( void* buffer, size_t size )
    {
        // ...................
    }
  5. "파일이 제대로 열리나?"
    class stream
    {
    public:
        stream( const string& name );
        int read( void* buffer, size_t size );
    };

    int XXX::open_file( const string& name )
    {
        stream file( name );
        return file.read( this->buffer, this->size );
    }

    stream::stream( const string& name )
    {
        // ...................
    }
    int stream::read( void* buffer, size_t size )
    {
        // ...................
    }

    int main()
    {
        // ...................
        XXX x;
        int result = x.open_file( ",,,,,,,,,,,,,,,," );
        assert( result != ERROR );
        assert( memcmp( x.buffer, dummy ) == 0 );
    }
  6. "버그 잡자"
내가 코딩하는 방식과 TDD에서 제시하는 방식의 차이는, 바라는 동작을 정의하는 부분이 워킹 코드이냐 테스트용 코드이냐 하는 점이다. 지금 내 방식의 단점은, 코드가 바뀌고 나면 동작의 일관성이 깨져도 그걸 체크할 방법이 바뀐 코드와 함께 유실돼 버린다는 것. TDD의 유용성이 느껴지는 부분이다.

TDD의 방법론은 실천 지침이 명확하다는 점에서 유용한 듯 하다. "코드보다 테스트코드 먼저". 이 얼마나 간단 명료한 지침인가. 내 생각으로는, 이 간단한 지침에 숨겨진 효용은 대충 이런 것 같다. 테스트를 작성하기 위해서는 내가 쓰고자 하는 코드가 어떤 식으로 동작해야 하는지를 정의해야 한다. 동작을 정의하기 위해서는 설계를 머리 속에 담고 있어야 하고, 이는 결국 코딩하기 전에 생각하라-는 오래된 금언을 실천하기 위한 매우 유용한 방법론인 것이다.
생각해 보면, 코딩하기 전에 생각하는 것이 습관화된 사람에게 TDD는 별달리 임팩트를 주진 않을 것 같다. TDD의 사용자에게 작용하는 궁극적이고 장기적인 영향은 코딩하기 전에 생각하는 습관을 들이게 하는 거라는 점에서 그렇다. (TDD의 다른 장점은 프로젝트에 작용하는 장점이지, 사람에게 작용하는 장점이 아니다) 하지만 그럼에도 장점은 있는데, 일단 남들에게 가르치기 쉽고, 또한 각 단계가 매우 짧고 보상이 정확하기 때문에 마치 게임을 하는 것처럼 코딩을 할 수 있다는 거다. "만렙까지 알아서 레벨 올리세요"와 "남쪽골짜기에서 토끼를 잡으면 레벨이 하나 올라요"의 차이랄까. 나에게 TDD란, 프로그래밍이란 게임의 규칙이란 느낌. 한 단계씩 레벨 올려서 만렙이 되면 프로그램이 완성되는 게임.

Posted by uhm
dev.log2009. 2. 17. 00:00
행렬을 구현하는 데에 있어서 가장 어려운 것은, 바로 메모리상의 배열 우선순위(major ordering)를 정하는 것이다. 단위 배열로 행벡터를 쓸 것인가 열벡터를 쓸 것인가를 결정하는 것인데, 행벡터는 행렬에 있어서 같은 행번호를 가진 원소가 서로 인접하도록 메모리 상에 배치하는 것이고, 열벡터는 같은 열 번호를 가진 원소가 서로 인접하도록 메모리 상에 배치하는 것. 어차피 둘 중의 하나 밖에 선택할 수 없기 때문에 심플한 문제이기는 한데, 좀 미묘한 문제가 걸려 있다.

우선, 행우선(row major) 배치는, 다음을 보자.


이와 같은 행렬이 행 우선 배열에서는 메모리 상에 선형으로 다음과 같이 배치된다.

 a00 a01 a02 a03 a10 a11 a12 a13 a20 a21 a22 a23 a30 a31 a32 a33

이는 C/C++의 2차원 배열 선언과 동일한 배치이다.

float a[4][4]

위와같은 선언은 메모리를 다음과 같이 배치한다.

a[0][0] a[0][1] a[0][2] a[0][3] a[1][0] a[1][1] a[1][2] a[1][3] a[2][0] a[2][1] a[2][2] a[2][3]
... a[3][0] a[3][1] a[3][2] a[3][3]

따라서, 배열의 첨자가 그냥 순서대로 [행번호][열번호]가 된다는 편리함이 있다. 행렬의 이름이 '행', '열' 순서이므로 이름과 잘 일치한다. 또한 C/C++의 기본 배열과 개념상 일치해 보인다는 장점이 있고, Direct3D에서 사용하는 방식이므로 별다른 변환 없이 Direct3D에서 사용이 가능하다. 유혹적이다.

반면, 열우선(column major) 배치는 행렬을 메모리에 배열하는 방법이 반대다.

 a00 a10 a20 a30 a01 a11 a21 a31 a02 a12 a22 a32 a03 a13 a23 a33

이를 2차원 배열로 표현한다면 [열번호][행번호]의 순서로 첨자를 부여해야 한다는 점이 C/C++의 표준과 불일치한다는 인상을 준다. 하지만 어차피 가로/세로의 선호는 사람에 따라 달라지는 것이므로 열이 앞이냐 행이 앞이냐 하는 문제는 표준에 정의되어 있지 않은 문제이다. 메모리를 가로 방향으로 나열해서 그렇지, 다음과 같이 나열하면 자연스러워 보인다.

 a00
 a10
 a20
 a30
 a01
 a11
 a21
 a31
 a02
 a12
 a22
 a32
 a03
 a13
 a23
 a33

이는 전적으로 메모리가 위아래로 뻗어있느냐 양옆으로 뻗어있느냐로 보는 것의 차이인데, 사실 어느 쪽을 택해도 무방하다. 물론 행렬을 표현한 2차원 배열에서 첨자의 순서가 '행','열' 순서가 아닌 점은 약간 불편할 것 같긴 하다. 하지만 흔히 쓰는 수학적인 (벡터를 세로로 적고 행렬의 뒤에 곱하는) 표현과 일치한다는 장점이 있고, OpenGL에서 사용하는 오더링이므로 OpenGL에서 별다른 변환 없이 사용이 가능하다.

ice 프로젝트의 요구조건중 하나가 OpenGL과 Direct3D의 동시 지원이었기 때문에, 가능한 방법은 3가지다
1. 행 우선 배치로 구현하고, OpenGL에서는 일일이 transpose하여 로드한다.
2. 열 우선 배치로 구현하고, Direct3D에서는 일일이 transpose하여 로드한다.
3. 둘 다 구현한다.
사실, 둘 다 구현하는게 바람직하긴 한데, 문제는 그렇게 할 경우에 클래스가 2개 생기므로 이름 공간이 더럽혀지는 결과가 초래되는 점이 아름답지 못하다. row_matrix와 col_matrix가 공존하는 구조를 용납할 수는 없는 법.

그래서 전에 벡터 클래스를 만들 때 SSE 스페셜라이제이션을 템플릿 매개변수로 컨트롤했던 것을 약간 이용하여, 역시 템플릿 매개변수로 major ordering을 결정하는 방법을 취하기로 했다.
enum SPECIALIZE_POLICY
{
    SPECIALIZE_DEFAULT,
    SPECIALIZE_SSE,
};

enum MAJOR_ORDER
{
    ROW_MAJOR,
    COLUMN_MAJOR,
};

// OpenGL용 열우선 배열을 기본으로 구현
template <class scalar_t, MAJOR_ORDER order = COLUMN_MAJOR, SPECIALIZE_POLICY policy = SPECIALIZE_DEFAULT >
struct matrix4t
{
    enum { MAJOR_VECTOR = order };
    typedef scalar_t                    scalar_type;
    typedef vector4t<scalar_t, policy>  vector_type;
    typedef vector3t<scalar_t, policy>  coord_type;
    union
    {
        vector_type v[4];
        scalar_type s[16];
    } m;
public:
    matrix4t() {}
    matrix4t(   scalar_type _11, scalar_type _12, scalar_type _13, scalar_type _14,
                scalar_type _21, scalar_type _22, scalar_type _23, scalar_type _24,
                scalar_type _31, scalar_type _32, scalar_type _33, scalar_type _34,
                scalar_type _41, scalar_type _42, scalar_type _43, scalar_type _44 )
                :m.v[0](_11,_21,_31,_41),
                 m.v[1](_12,_22,_32,_42),
                 m.v[2](_13,_23,_33,_43),
                 m.v[3](_14,_24,_34,_44)
    {
    }
    template <class scalar>
    explicit matrix4t( const scalar* a )
        :m.v[0](a[0], a[4], a[8], a[12] ),
         m.v[1](a[1], a[5], a[9], a[13] ),
         m.v[2](a[2], a[6], a[10],a[14]),
         m.v[3](a[3], a[7], a[11],a[15])
    {
    }
};

// Direct3D용 행 우선 배열을 위한 부분 스페셜라이제이션
template < class scalar_t, SPECIALIZE_POLICY policy >
struct matrix4t< scalar_t, ROW_MAJOR, policy >
{
    enum { MAJOR_VECTOR = ROW_MAJOR };
    typedef scalar_t                    scalar_type;
    typedef vector4t<scalar_t, policy>  vector_type;
    typedef vector3t<scalar_t, policy>  coord_type;
    union
    {
        vector_type v[4];
        scalar_type s[16];
    } m;

   
    static const matrix4t zero;
    static const matrix4t identity;
public:
    matrix4t() {}

    matrix4t(   scalar_type _11, scalar_type _12, scalar_type _13, scalar_type _14,
                scalar_type _21, scalar_type _22, scalar_type _23, scalar_type _24,
                scalar_type _31, scalar_type _32, scalar_type _33, scalar_type _34,
                scalar_type _41, scalar_type _42, scalar_type _43, scalar_type _44 )
                :m.v[0](_11,_12,_13,_14),
                 m.v[1](_21,_22,_23,_24),
                 m.v[2](_31,_32,_33,_34),
                 m.v[3](_41,_42,_43,_44)
    {
    }

    template <class scalar>
    explicit matrix4t( const scalar* a )
        :m.v[0](a[0], a[1], a[2], a[3] ),
         m.v[1](a[4], a[5], a[6], a[7] ),
         m.v[2](a[8], a[9], a[10],a[11]),
         m.v[3](a[12],a[13],a[14],a[15])
    {
    }
};

// SSE 템플릿 매개변수는 명시적으로 스페셜라이제이션할 경우에만 허용하도록 막아둠
template< class scalar_t, MAJOR_ORDER order >
struct matrix4t< scalar_t, order, SPECIALIZE_SSE >
{
    scalar_t error[0]; // SSE spcecialization is not allowed unless explicit
};

쓸 때는 어떤 오더링을 쓸 것인지와 SSE 스페셜라이제이션을 쓸 것인지를 명시하면 된다.

matrix4t<float, COLUMN_MAJOR, SPECIALIZE_DEFAULT >

물론, 위와 같이 쓰는 것은 불편하므로, OpenGL 모듈에서는 다음과 같이 타입으로 선언하는 것이 편리.

[render_ogl.h]
typedef matrix4t<float, COLUMN_MAJOR, SPECIALIZE_DEFAULT > matrix4;

물론, Direct3D모듈에서도 비슷하게 타입으로 선언할 수 있다.

[render_d3d.h]
typedef matrix4t<float, ROW_MAJOR, SPECIALIZE_DEFAULT > matrix4;

구현은 두개를 다 해야 하니 빡세도, 쓸때는 골라쓰는 재미가 있을듯; ice 프로젝트의 철학은 '클라이언트 측에서 엔진의 구성요소를 고를 수 있게 한다'는 것이므로.

Posted by uhm
dev.log2009. 2. 11. 01:02
회사에서 하는 금요 세미나. 저번주에는 K군이 크리티컬 섹션에 대해 발표했었다. K군이 발표에 삽질을 좀 했지만, 크리티컬 섹션 문제는 parallelism에서 매우 중요한 개념이므로 정리하고 넘어가자.

크리티컬 섹션이란, 두 개 이상의 쓰레드(혹은 프로세스)가 있을 때, 같은 공유자원에 접근하고자 시도하는 코드 구간을 말한다. 크리티컬 섹션이 왜 치명적인가 하면, 크리티컬 섹션이 아닌 구간에서는 패러럴리즘에 의해 잘못된 결과가 나올 리가 없기 떄문이다. 논리적으로 타당함에도 불구하고 패러럴리즘에 의해 잘못된 결과가 나올 수 있는 부분은 공유자원을 두 개 이상의 쓰레드에서 동시에 접근하려고 시도하는 곳 외에는 없다. 그래서, 다른 쓰레드와의 공유 자원에 접근하려고 하는 부분을 '치명적 구간'이라고 하는 것이다. 일부 번역서에서는 '임계영역'이라고 하기도 하는데, '제대로 관리하지 않으면 오류가 일어나는 부분'이라는 의미가 잘 살아나지 않는 것 같다. 개인적으로는 '치명적 구간'이라고 하기를 좋아하지만, 이래저래 (잘못된) 번역에 익숙해진 한국 프로그래머가 많으므로 난 그냥 '크리티컬 섹션'이라고 한다.

크리티컬 섹션을 제대로 처리해주지 않으면 잘못된 결과가 나오는 것은 전형적으로 다음과 같은 두 쓰레드를 생각하면 된다.

thread a :
int i=0;
void thread_a()
{
    i++;
}

thread b:
extern int i;
void thread_b()
{
    i--;
}

쓰레드 a와 b가 동시에 시작했다고 치면, 두 쓰레드가 종료했을 때 i의 값은 -1, 0, 1의 세 값중 어느 값이라도 가질 수 있게 된다. 이는 C++의 단항 증감연산자가 기계어로는 로드/산술연산/저장의 3가지 단계로 나뉘기 때문이다. 단순하게 생각하자면 A쓰레드의 로드/연산/저장이 순서대로 실행될 때 사이사이에 B쓰레드의 로드/연산/저장이 끼어든다고 보면 된다. 가능한 경우의 수는 많지만 대표적인 결과가 나오는 경우만 보면 다음과 같다.

A로드 > A연산 > A저장 > B로드 > B연산 > B저장 ==>  0
A로드 > B로드 > A연산 > A저장 > B연산 > B저장 ==> -1
A로드 > B로드 > A연산 > B연산 > B저장 > A저장 ==>  1

따라서 크리티컬 섹션 문제를 해결하는 것은 특정 쓰레드의 동작 사이에 다른 쓰레드가 끼어들지 못하도록 어떻게 하느냐 하는 것으로 귀결된다. 대략적으로 크리티컬 섹션 문제의 해결책은 다음과 같이 사용하게 된다.

wait( S )      // wait for entering critical section
..............    // critical section
signal( S )   // allow other threads to enter critical section

OS책에서는 크리티컬 섹션 문제의 해결책은 다음 조건을 만족해야 한다고 나온다. 중요하다.
  • Mutual Exclusion (상호 배제)
  • Progress (진행)
  • Bounded Waiting (유한 대기)
상호 배제는, 크리티컬 섹션 문제의 본질인, 한 쓰레드가 자원 R에 대한 크리티컬 섹션을 수행중일 때에는, 다른 쓰레드가 같은 자원 R에 대한 크리티컬 섹션에 들어가서는 안된다는 뜻이다. 진행 조건은, R에 대한 크리티컬 섹션을 수행중인 쓰레드가 하나도 없을 때에는, 어떤 쓰레드가 R에 대한 크리티컬 섹션에 들어가려고 하면 즉시 진행이 되어야 한다는 조건이다. 유한 대기는 말 그대로, 어떤 쓰레드가 R의 크리티컬 섹션을 수행하려고 할 때에는 다른 쓰레드의 R 크리티컬 섹션 진입이 유한한 횟수만큼만 이루어져야 한다는 조건. 당연한 소리같아보이지만, OS책에 나오는 크리티컬 섹션 문제의 솔루션들은 위 3가지 조건을 만족하게 만들기 까지의 발전과정이다. 언뜻 금방 생각할 수 있는 해결책들은 위 3가지 조건을 모두 만족하기가 쉽지 않다.

크리티컬 섹션 문제 해결에 가장 중요한 개념은 wait와 signal에 atomic operation이 도입되었다는 점이다.atomic operation을 뭐라 번역해야 할지는 모르겠지만, (원자적 연산;같은 구린 번역은 꺼져라!) atom의 원래의미인 '쪼갤 수 없는' 연산이란 뜻이다. (atom을 물질계에 적용한 용어인 '원자'가 어울리는 번역이 아닌 이유) 위에서C++의 단항 증감 연산자가 로드/연산/저장의 3단계로 나뉘어서 배열될 수 있는 데 비해, 아토믹 연산은 항상 단체로몰려다니고, 쪼개져서 배열될 수 없는 연산을 가리키는 개념이다. 현대적인 CPU는 모두 다 CPU의 기본 명령어중에 아토믹 연산이 명시되어 나오므로, OS는 크리티컬 섹션 문제의 해결책에 CPU의 아토믹 명령을 쓸 수 있다. 하드웨어의 도움으로 좀 더 우아한 해결책이 나올 수 있는 것은 자명한 일.

대표적인 해결책은 위대한 컴퓨터 과학자인 Dijkstra가 제안한 세마포다. 세마포의 기본적인 아이디어는 공유자원에 동시에 접근할 수 있는 쓰레드의 갯수를 미리 정해두고 지정된 수의 쓰레드만이 크리티컬 섹션에 진입할 수 있도록 한다;는 것이다. 2개 이상의 쓰레드가 동시에 같은 자원을 공유하는 크리티컬 섹션에 들어갈 수 있으면 counting semaphore, 오직 1개만이 크리티컬 섹션에 진입할 수 있으면 binary semaphore라고 한다. 사실 counting semaphore는 binary semaphore를 이용해서 구현할 수 있으므로 binary semaphore가 더 중요하다.
세마포를 이용한 크리티컬 섹션 문제의 해결책은 크게 두가지 구현방법이 있을 수 있다. 한 가지는 busy waiting, 혹은 spinlock이라고 부르는, 쓰레드가 계속 루프를 돌면서 크리티컬 섹션에 진입하기를 기다리는 방법이고, 다른 한 가지는 쓰레드 자체를 대기 상태로 바꿔버리고 세마포의 대기 큐에 들어가게 만드는 것이다. 각기 일장 일단이 있는데, 스핀락 구현은 크리티컬 섹션 진입에 컨텍스트 스위칭에 들어가는 오버헤드가 없다는 점은 좋지만 싱글 프로세서 시스템에서는 쓸 수 없다는 단점이 있다. (한 쓰레드가 CPU에서 계속 루프를 돌고 있는데 다른 쓰레드가 CPU에 올라갈 수 있을 리가 없다) 반면, 쓰레드를 대기 상태로 바꾸는 해결책은 싱글 프로세서 시스템에서도 별다른 문제 없이 쓸 수 있지만, 컨텍스트 스위칭 비용이 들어가게 된다는 점이 좋지 못하다.
결국, 크리티컬 섹션 진입 빈도에 따라 적절한 방법을 선택하는 것이 중요하다는 말씀.

Posted by uhm
dev.log2009. 2. 7. 18:33
일상적으로 통용되는 단위가 두가지 이상이라면 매우 헷갈린다. 미국은 미터법(metric system)과 영국단위(imperial system)의 차이 때문에 우주선[각주:1]을 하나 날려먹은 적도 있다. 그만큼은 심각한 것은 아니지만 회사에서 K군이 카메라 FOV를 조정할 때 라디안(radian)과 도(degree)의 차이 때문에 무척 헷갈려 하는 걸 본 적도 있다.

라디안은 우아하기 때문에 수학자나 공학자, 물리학자들이 좋아하고, 도는 역사가 오래기 때문에 세상 다른 모든 사람들이 선호하는 각도의 단위이다. 하지만 세상 모든 사람들이 우아하지 못한 단위를 사용한다고 해서 우리네 프로그래머까지 그런 단위를 써야만 한다는 것은 어불성설이라는 굳은 믿음을 갖고, 심심하던 차에 각도 클래스를 만들어 봤다.

기본 요구사항은 2가지.
  1. 어떤 각도를 나타내는 값이 도인지 라디안 인지가 항상 명확해야 한다.
  2. 도와 라디안의 변환은 인간이 신경을 쓰지 않도록 자동적으로 이루어져야 한다.
1번 요구사항은 그냥 angle = 3.5f; 라고 했을 때, 이 3.5가 도인지 라디안인지는 코드만 보고는 알 수 없기 때문에 혼동의 여지를 준다는 뜻이다. 이를테면, angle = radian(3.5f); 같은 식으로 이루어지면 항상 명확할 수 있다.
2번 요구사항은, 라디안을 받아들이는 함수에 실수로 도 단위로 90.f라는 값을 넣더라도, 1번에 의해 어떤 단위가 사용되고 있는지 항상 명시되므로, 자동으로 변환돼야 인간의 실수가 오류를 불러일으키지 않을 수 있다는 것.

const float pi = 3.14159265358979323846f;                           // 물론, float 타입은 이렇게 큰 정밀도를 저장하지 못한다.
const float pi_half = 3.14159265358979323846f*0.5f;

class radian;
class degree;

class radian
{
public:
    radian() {}
    explicit radian( float v ) : _value( v ) {}
    radian( const degree& r );

    operator float() const { return _value; }
    radian& operator=( float f ) { _value = f; return *this; }
    radian& operator=( const degree& d );

private:
    float _value;
};

class degree
{
public:
    degree() {}
    explicit degree( float v ) : _value( v ) {}
    degree( const radian& r );

    operator float() const { return _value; }
    degree& operator=( float f ) { _value = f; return *this; }
    degree& operator=( const radian& r );

private:
    float _value;
};


radian::radian( const degree& d )
{
    _value = static_cast<float>(d) * pi / 180.f;
}

radian& radian::operator=( const degree& d )
{
    _value = static_cast<float>(d) * pi / 180.f;
    return *this;
}

degree::degree( const radian& r )
{
    _value = static_cast<float>(r) * 180.f / pi;
}

degree& degree::operator=( const radian& r )
{
    _value = static_cast<float>(r) * 180.f / pi;
    return *this;
}

각 클래스의 float을 받아들이는 생성자가 explicit인 이유는, 함수 인자로 그냥 float 값을 넣을 때 어떤 단위를 의도하는지를 명시할 것을 강제하기 위해서이다. explicit이 아니라면 다음과 같은 일이 일어난다.

class radian
{
public:
    radian() {}
    radian( float v ) : _value( v ) {}
};

void rotate( radian r ); // radian을 받아들이는 함수
....
rotate( 90.f );              // 인간이 90도를 의도하며 함수를 호출하면 원치 않는 동작

하지만 float 생성자를 explicit으로 선언함으로써, 위와 같은 의도가 명확치 않은 코드는 아예 컴파일 단계에서 제거해 버릴 수가 있다. 컴파일 에러를 통해서;

class radian
{
public:
    radian() {}
    explicit radian( float v ) : _value( v ) {}
};

void rotate( radian r ); // radian을 받아들이는 함수
....
rotate( 90.f );              // ERROR!!!
rotate( radian(90.f) );   // 이렇게 하면 동작하지만 코드를 씀과 동시에 이상함을 발견하게 된다.
rotate( degree(90.f) );  // 이것이 원하는 동작.

그 밖의 경우에는 그냥 자연스럽게 동작한다.

radian a( pi/3.f );  // pi/3 을 지정
degree b = a;       // 도로 변환하면 60도
b = 90.f;               // 90도를 지정
a = b;                  // 라디안으로 변환하면 pi/2

이런 방법은 약간만 잘 이용하면 m/ft, ms/s, kg/pound 등등 다른 단위가 이용될 수 있는 모든 부분에서 인간의 헷갈림에 의한 실수를 원천봉쇄할 수 있지 않을까 싶다;

  1. Mars Climate Orbiter는 단위계의 차이로 파괴된 우주선이다. 추력을 설정할 때 지상의 운영 프로그램은 파운드 단위를, 기체의 제어 프로그램은 kg 단위를 기준으로 제작되어 발생한 사고. [본문으로]
Posted by uhm
dev.log2009. 2. 3. 22:19
벡터는 벡터일 뿐, 3차원 벡터는 좌표 3개가 아니다.
3D게임 프로그래밍을 시작하는, 특히 2D게임을 만들다가 3D로 전향하려는 사람들에게서 잘 드러나는 것 같은데, 벡터를 벡터로 보지 않고 계산해야 할 좌표 3개로 보는 경향이 있는 것 같다. 사실, 벡터를 조작하여 얻고자 하는 무언가는 대부분의 경우 주어진 벡터로부터 특정한 방향을 가진 벡터, 혹은 주어진 벡터의 길이와 관계된 것일 경우가 많다. 이런 것을 구하기 위해서는 벡터를 좌표 3개로 분할할 필요가 없는데도, 습관처럼 좌표를 쪼개서 계산한다면, 벡터 연산에 익숙하지 않기 때문일 것 같다.

3차원 공간상의 벡터에 정의된 연산은 대략 반전, 덧셈, 뺄셈, 실수 곱셈, 실수 나눗셈, 그리고 내적과 외적이 거의 전부다. 이를 적절히 이용하면 간략한 표현으로 원하는 결과를 얻을 수 있는데, 좌표로 쪼개서 계산하면 고려해야할 예외적 상황이 증가하여 오히려 코드가 복잡해지는 결과가 초래되곤 한다.

오늘 본 문제는 '어떤 점에서 선분에 내린 수선의 발이 그 선분을 분할하는 비율'이다. 조금 더 상세히 정의하자면 선분의 시작점 s, 끝점 t가 주어졌을때, 임의의 점 p에서 내린 수선의 발 f에 대해서 |sf|/|st|의 값을 구하라는 것이다. 이런 문제는, 고등학교 수학시간에도 나오는 문제이지만, 이를 좌표로 쪼개서 풀려고 다음과 같이 하는 것을 보았다. (정확히 기억하고 있진 않을 수도 있지만)
  1. 각 벡터 p, s, t를 한 평면, 이를테면 xy평면에 투영하여 p', s', t'으로 한다.
  2. xy평면에서 선분s't'의 방향은 ( tx-sx, ty-sy )이다.
  3. xy평면에서 선분s't'과 직교하는 선분의 방향 d는 ( -ty+sy, tx-sx )이다.
  4. p'의 s'에 대한 변위 o를 구한다. 이때 o( p'x-s'x, p'y-s'y )이다.
  5. 점 o를 지나고 d와 평행한 직선과 선분 s't'의 교점 q를 연립방정식으로 구하면 그 점이 수선의 발.
  6. qx/(tx-sx)가 구하고자 하는 값이다.

대충 돌아가기는 하겠지만, 몇가지 예외사항이 존재한다. 우선 과정1에서 선분st가 xy평면에 수직일 경우 다른 평면을 골라 투영해야 한다. 또한 6단계에서 선분s't'이 y축에 평행하면 0/0의 꼴이 되어 부정이 되므로 역시 다른 좌표축을 골라야 한다. 여러가지 복잡한 예외를 고려해야 하기 때문에 결과적으로는 코드 길이가 원래보다 2배 정도 길어지게 마련이다. 하지만, 이는 내적의 성질을 이용해서 다음과 같은 간략한 방법으로 구할 수 있다.

이렇게 하면 선분의 방향이 어떠하든 일반적인 해를 구할 수 있다. 내적은 두 벡터의 길이의 곱에 사잇각의 코사인을 곱한 것과 같다는 성질을 이용한 것인데, 벡터의 길이에 코사인을 곱하면 다른 쪽 벡터에 투영된 길이가 나온다는 점을 생각하면 되겠다.

물론, 이런 방법으로는 길이의 비만 구할 수 있기 때문에 수선의 발 자체가 필요한 경우에는 따로 계산을 해야 하겠지만, 그때에도 위 결과로부터 직접 구할 수 있다. 선분 ts와 선분 fs의 길이의 비를 이미 구했으므로, 선분 ts를 이 비율대로 곱하기만 하면 수선의 발이 직접 구해진다. 따라서 수선의 발 f는 다음과 같이 구할 수 있다.

벡터에 정의된 연산이 몇개가 안되므로, 성급하게 벡터를 좌표로 쪼개려고 하는 것보다는, 벡터 연산으로 요리조리 조작해 보는 편이 더 일반적으로 유효한 결과를 가져온다. 3D프로그래밍의 시작은 벡터를 좌표의 집합이 아닌, 벡터 그 자체로 보는 것이라고나.


Posted by uhm
geek.log2009. 2. 2. 00:57
블로그 유입경로를 보다 보니 이런게 눈에 띄었다.


어허허허허허허

물론, deque는 dequeue와 동일한 대상을 가리키는 것이 맞지만, 사전을 찾아보면, deque의 발음은 [데크]이고, dequeue의 발음이 [디큐]이다. 그리고, STL에서 double-ended queue를 구현할때는 이름을 dequeue라 붙이지 않고, deque라 붙였으므로, 우리는 [데크]라고 읽는 것이 맞지 않을까 싶다.

지금까지 본 유사한 예로

height를 [헤이트]라고 읽은 k군,
enum을 [에넘]이라고 읽은 l씨,
등이 생각난다.

사전 한번만 찾아보면 되는 것을, 자기가 알고 있는게 맞다는 굳은 신념때문에 안 찾아보기 때문일지도 -_-a


Posted by uhm
dev.log2009. 2. 1. 23:29
회사에서는 1주일마다 주간회의때 주제 하나씩을 잡아서 간략한 설명형식의 세미나를 한다.
지금까지 다뤄왔던 주제는 다음과 같다.
  • STL 컨테이너
  • 시간복잡도
  • 컴파일 & 링크
  • 프로세스와 쓰레드
  • 비동기 환경에서의 문제해결
  • 메모리 할당자
  • 커스텀 자료구조 설계
  • lua 스크립트 언어
  • GUI 설계변경
  • 곡선표현
  • 물리연산
  • 소프트웨어 설계 방법론
  • 애니메이션 기법
  • 커스텀 데이터 매니징
  • CPU 아키텍쳐
  • 회전변환
  • 개발 프로세스 리뷰

다는 생각이 안나지만, 대략 이러한 종류의 주제들로 약 8개월동안 진행해 왔다. 단순계산으로 24가지 주제를 다뤄온 셈인데, 이제부터라도 기록을 남기기 위해 포스팅을 해 놓아야 겠다는 생각이 든다.

지난주의 주제는 충돌.
충돌계산의 핵심은 매개변수(parametric form) 방정식이다.
좌표평면에서 x절편 A, y절편 B를 가지는 직선의 방정식은 일반적으로 다음과 같이 쓰곤 한다.
y = -(B/A)x + B
이때 A' = -B/A 로 정의하면 간략히 다음과 같이 쓸 수 있다.
y = A'x + B
이와 같은 형태는 표현은 간단하지만, 직선이 y축과 평행한 경우는 절대로 표현이 불가능하다. 따라서, 평면에서 임의의 직선을 표현하는 좀 더 나은 방식은 음함수 형태로, 다음과 같이 쓰는 것이다.
Bx + Ay - AB = 0
이와 같은 형태는 평면상에서 임의의 직선을 표현할 수는 있지만, 특정한 조건을 만족하는 점을 계산하려면 (이를테면, 두 직선의 교점) 여러차례의 이항과 소거를 거쳐야 하는 단점이 있다. 또한 3차원 이상의 공간상에서의 직선은 이와 같은 형태로 표현이 불가능하다는 결점이 있다.
매개변수 방정식에는 위와 같은 결점이 없다. 위의 2차원 평면상의 직선은, 매개변수 t에 대하여, 다음과 같이 쓸 수 있다.
x = -At + A
y = Bt
이는 다시, 벡터 방정식으로 a=(A,0), b=(b,0)으로 정의하면, 직선 l은, 다음 식으로 표현된다.
l = (b-a)t + a
이러한 형태의 표현은 3차원 이상의 공간에서도 일반적으로 성립하며, 표기도 간단하고, 매개변수 t의 범위를 제한함으로써 선분이나 반직선등을 용이하게 표현할 수 있다. 또한 한가지 변수 t만 결정하면 직선상의 한 점을 지정할 수 있으므로, 풀이도 비교적 용이하다. 기본적인 충돌 계산은, 충돌 대상이 되는 도형을 매개변수 형태로 표현하는 것으로 시작한다.

보통 충돌 시스템을 구현할 때에는 간단한 기하도형을 몇가지 정해놓고 시작하는데, 일반적으로 다음과 같은 도형들이 충돌계산에 사용되곤 한다.
  • 직선
  • 선분
  • 캡슐
  • 실린더
  • AABB
  • OBB
  • 삼각형

대략 9개 정도의 도형이 널리 이용되는데, 이들에 대한 구현을 모두 하려면, 각 도형이 다른 도형, 혹은 같은 도형과 충돌할 수 있으므로, 45 가지 경우를 구현해야 한다. 이에 대한 설명을 모두 하는 것은 길고 시간이 오래걸리므로, 여기에서는 직선-구, 직선-삼각형의 경우만 다룬다.

일반적으로 직선 l은, 직선의 방향벡터 d와 직선위의 한점을 가리키는 위치벡터 p가 주어질 때, 실매개변수 t에 대하여 다음 형태로 쓸 수 있다.
l = dt + p
또한 일반적인 구 s는, 중심 c와 반지름 r만으로 완전하게 정의할 수 있으므로, 구의 방정식은 벡터 형태로 다음과 같이 쓸 수 있다.
|s - c| = r
이와 같은 형태는 계산이 곤란하므로, 내적 형태로 다음과 같이 쓸 수 있다.
(s-c)·(s-c) = r*r
이때, 구 s와 직선 l의 교차점은 s = l 로 놓고 풀어 직선의 매개변수 t를 결정하는 작업이다. 구의 방정식에서 s = l을 대입하고 전개하면, t에 대한 2차방정식을 구할 수 있으므로, 이 2차방정식의 근으로 교점을 결정할 수 있다. 이 방정식이 2개의 실근을 가지면 직선은 구를 관통하며, 1개의 중근을 가지면, 직선은 구와 접하고, 허근을 가지면 직선은 구와 만나지 않는다.

3차원 공간상에서 삼각형과 직선의 충돌은 먼저, 삼각형을 매개변수 형태로 표현하는 것으로 시작한다. 삼각형 ABC에서, 벡터CA를 a, 벡터CB를 b라고하고, 점C의 위치벡터를 c라고 재명명하면, 삼각형 내부의 영역 q는, 두 매개변수 u,v에 대하여 다음과 같이 표현된다.
q = au + bv + c (u >= 0, v >= 0, 0 <= u+v <= 1 )
여기서 삼각형과 직선의 교점을 구하는 것은, 직선 l이 주어졌을 때, q = l로 놓고 풀어 직선의 매개변수 t와 삼각형의 매개변수 u,v를 구하는 문제로 바뀐다. l을 대입하면, 풀어야할 방정식이 나온다.
dt + p = au + bv + c
매개변수에 대한 항을 이항하면, 다음과 같다.
dt - au -bv = c-p
표현을 간단히 하기 위해 a' = -a, b' = -b, o = c-p 로 치환하면, 다음과 같이 된다.
dt + a'u + b'v = o
이는 3차원 벡터 (t,u,v)에 대한 전형적인 선형변환이므로, 행렬 형태로 바꾸면 다음과 같다.
dx
a'x
b'x
×
t =
ox
dy
a'y
b'y
u
oy
dz
a'z
b'z
v
oz
이때 행렬 (d, a', b')을 M이라고 쓰고, 벡터 (t,u,v)를 s라고 다시 쓰면,
Ms = o
곧, M의 역행렬을 M'이라고 하면
s= M'o
따라서, M의 역행렬을 구하고 벡터 o를 계한하여 둘을 곱하면 세 매개변수 t, u, v를 모두 결정할 수 있다. 유일한 해가 존재하고, u,v가 삼각형의 매개변수 조건을 만족하면, 직선 l과 삼각형 q는 교차한다.
이때, M의 역행렬을 구할 수 없는 경우는 직선과 삼각형이 평행하거나 삼각형이 직선을 포함하는 경우이므로, 이때는 삼각형의 세변과 직선을 직선-직선 간의 충돌 계산으로 교차 여부를 검사해야 한다.

Posted by uhm
dev.log2009. 1. 28. 23:38
ice 프로젝트를 시작하려다보니, 기초 수학 클래스의 성능을 측정해야만 했다. 그래서, 옛날 R모 게임을 만들던 시절에 만져본 언리얼엔진2의 스탯 수집방식을 좇아서 비슷하게 만들어 보기로 했다. 기본 방식은 수집할 스탯의 이름과 타입을 등록하여 인덱스를 지정한 후 수집할 구역의 시작과 끝을 지정하는 것. 여기에 시간 통계를 위한 API콜은 별도의 레이어로 분리하면 대략적인 틀이 나온다.
class syscore
{
public:
    static int64 clock()
    {
        int64 begin;
        QueryPerformanceCounter( (LARGE_INTEGER*)&begin );
        return begin;
    }
    static int64 clockpersec()
    {
        int64 freq;
        QueryPerformanceCounter( (LARGE_INTEGER*)&freq );
        return freq;
    }
};

class stat_collector
{
public:
    stat_collector() { _freq = (float)syscore::clockpersec(); }
    void flush();
    uint32 enroll( const string& name, uint type );
    void start( uint index );
    void stop( uint index );

    float mean_stat( uint index );
    float inst_stat( uint index );
    float total_stat( uint index );
    int   sample_count( uint index );

    class block_stat
    {
    public:
        block_stat( stat_collector& collector, uint index )
            :_collector( &collector ), _index( index )
        {
            _collector->start( _index );
        }
        ~block_stat()
        {
            _collector->stop( _index );
        }
    private:
        stat_collector* _collector;
        uint            _index;
    };

    enum stat_type
    {
        STAT_TIME,
        STAT_COUNT,
    };

private:

    struct stat_item
    {
        stat_item( const string& name, uint type )
            : _count(0), _name(name), _type(type)
        {}

        uint   _count;
        string _name;
        uint   _type;
    };
    std::vector<sint64> _prv_stats;
    std::vector<sint64> _cur_stats;
    std::vector<stat_item> _stat_info;
    float _freq;
};

void stat_collector::flush()
{
    //_prv_stats = _cur_stats;
}

uint32 stat_collector::enroll( const string& name, uint type )
{
    assert( _prv_stats.size() == _cur_stats.size() );
    assert( _prv_stats.size() == _names.size()  );
    uint32 index = _cur_stats.size();
    _prv_stats.push_back( 0 );
    _cur_stats.push_back( 0 );
    _stat_info.push_back( stat_item( name, type ) );

    return index;
}

void stat_collector::start( uint index )
{
    _prv_stats[index] = _cur_stats[index];

    switch ( _stat_info[index]._type )
    {
    case STAT_TIME:
        _cur_stats[index] -= syscore::clock();;
        break;
    case STAT_COUNT:
        break;
    default:
        assert( "unkown stat type!!!!!!!!!" && 0 );
    };
}

void stat_collector::stop( uint index )
{
    switch ( _stat_info[index]._type )
    {
    case STAT_TIME:
        _cur_stats[index] += syscore::clock();
        break;
    case STAT_COUNT:
        _cur_stats[index]++;
        break;
    default:
        assert( "unkown stat type!!!!!!!!!" && 0 );
    }

    _stat_info[index]._count++;
}

float stat_collector::mean_stat( uint index )
{
    switch ( _stat_info[index]._type )
    {
    case STAT_TIME:
        return _cur_stats[index]/(_freq * _stat_info[index]._count);
    case STAT_COUNT:
        return (float)_cur_stats[index]/_stat_info[index]._count;
    default:
        assert( "unkown stat type!!!!!!!!!" && 0 );
        return 0;
    }
}


float stat_collector::inst_stat( uint index )
{
    switch ( _stat_info[index]._type )
    {
    case STAT_TIME:
        return (_cur_stats[index]-_prv_stats[index])/_freq;
    case STAT_COUNT:
        return (float)_cur_stats[index]-_prv_stats[index];
    default:
        assert( "unkown stat type!!!!!!!!!" && 0 );
        return 0;
    }
}

네이밍 컨벤션은.. C/C++ 표준 위원회의 스타일을 따라가 봤다.
사용법은,
#define TEST_LIST() \
    TEST( l = c.length() )                   \
    TEST( c = vector_t::cross( a, b ) ) \
    TEST( l = vector_t::dot( b, c ) )      \

stat_collector _stats;

template <class vector_t>
void test_run( const char* filename, uint stat_index )
{
    static vector_t a, b, c;

    std::ofstream log( filename, ios::app );
#define TEST( expression ) #expression "\n"
    log << "=======================================" << endl;
    log << TEST_LIST();
    log << "---------------------------------------" << endl;
#undef TEST
    for ( int count = 0; count < 10; ++count )
    {
        vector_t::scalar_type x = (float)rand();
        vector_t::scalar_type y = (float)rand();
        vector_t::scalar_type z = (float)rand();
        volatile vector_t::scalar_type l = 0;
        a = vector_t( x, y, 0 );
        b = vector_t( -y, x, 0 );
        c = vector_t( x, y, z );

        _stats.start( stat_index );
        for ( int i = 0; i < 10000000; ++i )
        {
#define TEST( expression ) expression;
            TEST_LIST();
#undef TEST
        }
        _stats.stop( stat_index );
        log << _stats.inst_stat(stat_index) << std::endl;
    }
    log << "======== " << _stats.mean_stat(stat_index) << " sec/sample ==========" << std::endl;
}

int WINAPI WinMain( HINSTANCE , HINSTANCE, char* , int )
{
    uint imp_stat, exp_stat;
    imp_stat = _stats.enroll( _t("imp"), stat_collector::STAT_TIME );
    exp_stat = _stats.enroll( _t("exp"), stat_collector::STAT_TIME );
    test_run<vector3def>( "log_imp.txt", imp_stat );
    test_run<vector3sse>( "log_exp.txt", exp_stat );

    return 0;
}

이름과 타입을 등록하고, 측정할 구간을 start/end로 지정하면 끝. TEST_LIST는 테스트 대상이 어떤 코드였는지에 대한 로그를 남기기 위한 매크로.

부족한 부분은 나중에 수정하자.

Posted by uhm
dev.log2009. 1. 27. 23:02
설도 지났으니, ice 개발 계획을 본격적으로 잡아야 겠다;는 생각이 들었다.
전체적으로는 각 기능간 커플링을 없도록 제작하여 기능별로 독립적으로 사용할 수 있도록
작업하는 것이 목적. 제네릭 프로그래밍을 엔진 레벨에서 적용해 보는 것도 이 프로젝트의
목적중 하나.
  1. 벡터/행렬 클래스
    - 템플릿 기반으로 SSE 특수화 구현
  2. 드로잉
    - OGL/DX 공용 드로잉, 다중 쓰레드 구현
  3. 맥스 플럭인/익스포터
    - 맥스 뷰포트로 렌더링, 바이너리/텍스트 포맷으로 저장
  4. 장면 트리
    - octree/BSP
  5. 애니메이션
    - 버텍스 스키닝/애니메이션블렌딩, 익스포터 제작
  6. 셰이더
    - 맥스의 머티리얼과 대응하는 개념으로 제작, 맥스 셰이더 플럭인 제작
  7. 에디터
    - height field/BSP+PVS, 독립 어플리케이션으로 seamlessness 구현.
  8. 파티클
    - 맥스 플럭인 제작
  9. 물리 시뮬레이션
    - 충돌/IK/강체역학/마찰/스프링+댐퍼, 맥스 플럭인
  10. 그림자
    - 부드러운 경계
Posted by uhm
geek.log2008. 6. 25. 23:10

A : Darth Programous was a Dark Lord of the Code, so powerful and so wise he could use the Source to influence the binary code to bypass exceptions. He had a knowlege of the dark side that he could even keep the softwares he cared about from crashing.
B : He could actually keep softwares from crash?
A : The Dark side of the Source is pathway to many softwares some considers to be unnatural.
B : Is it possible to learn this code?
A : NOT from a professor.


A : 다스 프로그래머스는 코드의 암흑제왕이었다. 그는 매우 강력하고 현명해서 소스를 사용하여 바이너리 코드에 영향을 미쳐 예외를 건너뛰게 할 수 있었지. 그는 다크사이드의 지식을 갖고서 그가 소중하게 생각하는 소프트웨어가 뻗지 않게 하기도 했었다.
B : 그가 정말로 소프트웨어를 뻗지 않게 막을 수 있었다고요?
A : 소스의 다크사이드는 몇몇 사람들은 부자연스럽다고 생각하기도 하는 많은 소프트웨어로의 지름길이지.
B : 그런 코딩을 배우는 게 가능한가요?
A : 교수한테서는 안돼.


 May the Source be with you.


Posted by uhm