2016년 5월 26일 목요일

공간 변환: 투영 행렬 정리

공간 변환


Object Space(Local Space or Model Space) : 물체가 기준인 공간

World Space : 모든 물체가 공유하는 공간. 실제 세상 공간.

View Space(Camera Space) : 카메라가 세상의 중심인 공간. 카메라 기준으로 World를 바라본 공간.

Projection Space : View Space를 투영한 공간. x, y는 -1~1까지의 좌표를, z는 0~1까지의 좌표를 가짐.

Screen Space : 화면 공간. 왼쪽 상단이 (0, 0)으로 시작하여 (w-1, h-1)까지의 좌표를 가짐.


Local Space -> World Space


물체가 중심인 세상에서 월드 공간으로 나온다는 것은
크기(Scale), 회전(Rotation), 이동(Translation)
즉 W=SRT라고 할 수 있고 행렬은 다음과 같다


World Space -> Camera Space


월드 공간에서 어느 하나의 오브젝트가 중심인 공간으로 공간 변환을 한다는 것은 World Space에서 해당 오브젝트의 Local Space로 이동하는 것과 같다.

다시 말해, World Marix는 해당 오브젝트가 세상에 나오기 위한 행렬이었으므로, 특정 오브젝트가 중심인 공간으로 변환한다는 것은 해당 오브젝트의 World Matrix의 역 행렬을 사용하면 된다.

그래서 카메라가 중심인 Local Space에서 World Space로 나오기 위한 행렬 W의 역 행렬을 구하면 그 행렬이 카메라가 중심인 공간(Camera Space)으로의 변환 행렬을 뜻한다고 할 수 있다.

또한 World Space와 Camera Space는 동일 공간상의 변환이므로 크기 변환은 제외되어 있다고 할 수 있다. 즉 W=SRT 이므로, W=RT로 생각해볼 수 있으며, 그 역행렬은 W-1 = T-1R-1으로 표현 가능하다.


Camera Space -> Projection Space


FOV(field of view) : 시야각

Aspect Ratio(종횡비) : screen width/ screen height

Projection Window는 Near Plane과 Far Plane과 동일한 비율을 가지므로 실제 크기는 중요치 않다.

그래서 Near Plane과 Projection Window를 동일하게 보는 경우가 많다.

그런 이유로 r(=width/height)을 구할 때 실제 크기보다 비율이 중요하므로 height를 2로 하여(위/아래 각각 1) 단순화 시켜서 계산하도록 한다.






d와 r이 구해지면 β를 구할 수 있다. 식의 r에 의해 β는 계속 변화한다.


3차원 공간상의 점 (x, y, z)를 투영공간에 변환한 점 (x', y', z')은 비례값에 의해 
라고 할 수 있으므로, 다음의 식이 성립한다.


y값 또한 마찬가지로 x의 위치에 대신 올 수 있다.

이렇게 구한 값에 따라

x'는 -r <= x' <= r
y'는 -1 <= y' <= 1
z는 n <= z' <= f

일 때 절두체 내부에 있다고 할 수 있다.

앞선 방식은 r에 의해 x', y'의 값이 좌우된다. 즉 하드웨어에서 계산을 하기 위해서 항사 r(Aspect ratio)를 필요로 한다는 문제가 생긴다.

이를 단순화 하기 위해 NDC(Normalized Device Coordinates) 좌표로 변환을 한다.
x'와  y'에 대해서 r로 나누는 것이다.

이를 통해 범위는 다음으로 조정 가능하다.
r로 나눈 값에 의해 x'는 NDC 좌표계에서 다음과 같이 표현 가능하다.
x, y는 선형 연산이 가능하나 z는 선형 변환이 되지 않는다.(z로 나누어 투영을 처리하기 때문)
그래서 z 나누는 연산을 나중으로 미뤄두고 선형행렬을 구성한다.



z축 값에는 x, y의 값이 없으므로 0.
A, B는 무슨 값이 들어갈지 모르므로 상수 A, B를 설정

나중에 z로 나누기 위해서는 z값이 존재해야 하는데 동차 좌표상의 w값에 이 값을 잠시 복사해두면 된다. 
그래서 3행 4열 성분과 4행 4열 성분을 각각 1과 0으로 설정

계산의 편의를 위해 각 성분에 z를 곱해버린다.


최종적으로 구해진 (zx', zy', zz', z)를 w 값인 z로 나누면 다음과 같다.


투영된 z의 값(=z')은 0~1의 범위를 가져야 한다. (깊이 테스트를 위한 것)
이를 위해 구해진 다음의 식을 풀어야 한다.
z에 0과 1을 대입하여 B에 대해서 풀면 B = -An이 나오고 이에 따라 식을 풀면 다음과 같다.



이제 앞서 구해놓은 투영 행렬에 새로 구한 A, B의 값을 채운다.

이렇게 구해진 z의 값은 다음과 같은 그래프 모양으로 나타난다. 카메라에서의 거리가 가까울수록 깊이에 대한 묘사가 섬세해진다.


2016년 5월 16일 월요일

C++ 상태 머신 디자인

http://www.codeproject.com/Articles/1087619/State-Machine-Design-in-Cplusplus

의 글을 번역 및 정리하였습니다.




등장 배경


많은 개발자들이 사용하는 디자인 테크닉으로 유한상태머신(FSM)이 있습니다. 복잡한 프로그램을 상태와 상태 전이로 나누어 정복하는 것인데, 많은 구현 방법이 있습니다.

스위치 문을 사용하여 구현하는 것은 가장 쉽고 흔한 방법입니다. 보통 다음과 같이 구현합니다.

switch (currentState) {
   case ST_IDLE:
       // do something in the idle state
       break;
    case ST_STOP:
       // do something in the stop state
       break;
    // etc...
}

이 방법은 많은 경우에 적합한 방법이지만, 이벤트 기반의 멀티 스레드 프로젝트에 적용하려면 상당히 제한됩니다.
첫 번째 문제는 어떤 상태 전이가 유효하고 어떤 것이 유효하지 않은지 조절하는 것입니다. 모든 상태 전이는 어떤 상황에도 허용되는데 이 경우 적합하지 않습니다. 이러한 전이를 강제할 방법이 없습니다.
또 다른 문제는 특정 상태로 데이터를 전달하는 것입니다. 모든 상태 머신이 한 개의 함수에 존재하므로 추가적인 데이터를 주고받은 것이 어렵습니다.
마지막으로 멀티 스레드 환경에 적합하지 않습니다. 상태 머신이 싱글 스레드에서만 불려지도록 해야합니다.


상태 머신을 왜 사용할까요?


상태 머신을 사용하여 코딩을 하면 복잡한 문제를 단순화하기에 매우 좋습니다. 프로그램을 우리가 상태라고 불리는 것들로 나누고 각 상태는 제한된 동작만을 수행합니다. 이벤트 들은 자극으로, 상태머신이 상태 사이에서 이동하거나 전환하도록 합니다.

간단한 예제를 위해 자동차 프로그램을 만들어 봅시다. 자동차가 출발하고 정지해야 되고 속력도 바뀌어야 합니다. 클라이언트에 노출되는 이벤트는 다음과 같을 것입니다.

1. Set Speed - 자동차의 속력을 특정 속도로 조절합니다
2. Halt - 자동차를 멈춥니다

멈춰있는 자동차를 특정 속력으로 바꾸어 움직이기 시작하거나 이미 움직이고 있는 자동차의 속력을 바꿀 수 있습니다. 또한 멈출 수도 있죠. 자동차 프로그램에서 이 두 이벤트 혹은 함수는 외부 이벤트로 정의됩니다. 하지만 사용하는 클라이언트의 입장에서는 그냥 클래스 안의 함수이겠지요.

이 이벤트들이 상태머신은 아닙니다. 이 이벤트를 이용하는 방법은 상태마다 다릅니다. 이 경우 상태들은 다음과 같습니다.

1. Idle - 자동차가 움직이지 않고 있는 상태
   - 아무것도 하지 않음
2. Start - 멈춰있는 자동차를 움직임
   - 자동차에 전원을 넣음
   - 속력을 변경함
3. Change Speed - 이미 움직이고 있는 자동차의 속력을 조절함
   - 속력을 변경함
4. Stop - 자동차를 멈춤
   - 전원을 끔
   - Idle 상태로 변경함

이렇게 다양한 상태로 나누면 어떻게 자동차를 움직여야 할지, 그 규칙을 더 쉽게 정의할 수 있게 됩니다.

모든 상태머신은 "현재 상태"라는 개념이 있습니다. 현재 상태머신의 상태를 의미합니다. 프로그램이 실행 중일 때 상태머신은 단 한 개의 상태만 가질 수 있습니다. 상태머신 클래스가 생성될 때 construction에서 특정 상태가 주어집니다. 그런데 이 상태는 실행되지는 않고 이벤트가 주어져야만 실행됩니다.

이 자동차 제어 프로그램의 상태도는 다음과 같습니다. 각 상자는 상태를 나타내고 화살표로 연결되어 있습니다. 이름이 적혀있는 화살표는 외부 이벤트이고, 이름이 없는 화살표는 내부 이벤트입니다. 외부 이벤트와 내부 이벤트의 차이는 추후 설명합니다.


이벤트가 도착했을 때 상태변이는 현재 머신의 상태에 따라 달라집니다. SetSpeed 이벤트가 도착했을 때 만약 자동차가 Idle 상태이면 Start 상태로 변이됩니다. 하지만 같은 SetSpeed 이벤트가 오더라도, 자동차가 Start 상태이면 자동차가 ChangeSpeed 상태로 전이됩니다. 또한 모든 상태 변이가 가능한 것은 아님을 확인할 수 있습니다. 예를 들어 자동차는 ChangeSpeed 상태에서 Stop을 거치지 않고 바로 Idle 상태로 갈 수 없습니다.


외부 이벤트와 내부 이벤트


이벤트란 상태머신이 상태 사이에서 전이되게 하는 자극입니다. 예를 들면 버튼이 눌리는 것이 이벤트가 될 수 있죠. 이벤트는 두 종류로 나뉩니다. 외부 이벤트와 내부 이벤트죠.

외부 이벤트는 가장 기본적인 개념에서, 상태머신 오브젝트를 호출하는 함수입니다. 이러한 함수는 퍼블릭이고 상태머신 밖에서 불릴 수 있습니다. 시스템의 어떤 스레드나 작업이라도 외부 이벤트를 발생시킬 수 있죠. 반면 내부 이벤트는 상태머신의 상태 실행 도중 자동으로 생성되는 이벤트입니다.

외부 이벤트가 발생하면 상태머신의 현재 상태를 기반으로 어떤 전이가 일어나야 하는지 찾아집니다. 찾아지면 전이가 일어나고 그 상태의 코드가 실행됩니다. 상태 함수가 끝나면 내부 전이가 일어났는지 체크합니다. 만약 있었다면 다른 상태전이가 일어나서 새로운 상태가 실행됩니다. 이 과정은 상태머신이 더 이상 내부 이벤트를 생성하지 않을 때까지 반복됩니다. 즉, 첫 번째 외부 함수 호출이 리턴 될 때 까지요. 이 모든 것은 호출자의 스레드에서 일어납니다.

한 번 외부 이벤트가 발생해서 상태머신이 동작하면 다른 외부 이벤트에 의해서 방해받을 수 없습니다. 이러한 모델은 상태전이시 멀테스레드에서 안전한 동작을 제공합니다. 세마포나 뮤텍스를 사용하여 다른 스레드의 접근을 막습니다. 소스코드의 ExternalEvent()를 확인하세요.


이벤트 데이터


이벤트가 생성될 때 상태 함수가 이용할 수 있는 데이터를 추가적으로 가지고 갈 수 있습니다. 상태의 실행이 끝나면 이벤트 데이터는 다 사용됬다고 보고 삭제됩니다. 따라서 상태머신에 전송된 모든 데이터는 new를 통해서 힙 영역에 올라가야 합니다. 또한 이러한 구현을 위해서 이벤트 데이터는 EventData 베이스 클래스를 상속받아야 합니다. 이렇게 하면 상태머신이 어떤 데이터를 지울지 알 수 있습니다.

class EventData 
{
public:
    virtual ~EventData() {}
};


상태 전이

외부 이벤트가 생성될 때, 행동의 상태전이를 결정하기 위한 검색이 실행됩니다. 이벤트에 대한 결과는 세 가지 경우가 있습니다. 새로운 상태, 이벤트 무시, 실행될 수 없음. 새로운 상태는 실행 가능한 새로운 상태로의 전이를 일으킵니다. 지금 실행 중인 상태로의 전이도 가능합니다. 현재 상태가 재실행 됩니다. 이벤트 무시의 경우 상태가 실행되지 않습니다. 그리고 이벤트 데이터는 삭제됩니다. 마지막 실행될 수 없는 경우는 이벤트가 현재 상태에서 유효하지 않은 경우입니다. 시스템이 중지됩니다.

이것을 구현할 때 내부 이벤트는 전이 유효를 검사할 필요가 없습니다. 유효하다고 가정됩니다. 유효한 내부 이벤트를 검사할 수도 있지만 예제에서 이렇게 하는 것은 작은 효과를 위해 많은 공간과 시간을 낭비하는 것입니다. 전이 유효성을 검사하는 것은 비동기 외부 이벤트에서 클라이언트가 적합하지 않은 시간에 이벤트를 발생시키는 것을 검사하는 것입니다. 상태머신은 실행중에는 방해될 수 없습니다. 크래스의 프라이빗 구현이 컨트롤 하며 전이 체크가 무의미합니다. 이렇게 하면 많은 전이 테이블을 관리할 필요 없이 디자이너에게 자유롭게 내부 이벤트를 통해 상태를 바꿀 수 있게 해줍니다.


상태머신 클래스


여러분의 상태머신을 만들 때 두 가지 베이스 클래스가 필수적입니다. StateMachine과 EventData 입니다. StateMachine을 상속받는 클래스는 상태 전이에 필수적인 메커니즘과 이벤트 핸들링을 상속받습니다. 상태 함수에게 고유한 데이터를 전송하기 위해 해당 구조는 반드시 EventData를 베이스 클래스로 상속받아야 합니다.

class StateMachine 
{
public:
    enum { EVENT_IGNORED = 0xFE, CANNOT_HAPPEN };

    StateMachine(BYTE maxStates, BYTE initialState = 0);
    virtual ~StateMachine() {}

    BYTE GetCurrentState() { return m_currentState; }
    
protected:
    void ExternalEvent(BYTE newState, const EventData* pData = NULL);
    void InternalEvent(BYTE newState, const EventData* pData = NULL);
    
private:
    const BYTE MAX_STATES;
    BYTE m_currentState;
    BYTE m_newState;
    BOOL m_eventGenerated;
    const EventData* m_pEventData;

    virtual const StateMapRow* GetStateMap() = 0;
    virtual const StateMapRowEx* GetStateMapEx() = 0;
    
    void SetCurrentState(BYTE newState) { m_currentState = newState; }

    void StateEngine(void);     
    void StateEngine(const StateMapRow* const pStateMap);
    void StateEngine(const StateMapRowEx* const pStateMapEx);
};

StateMachine은 이벤트를 핸들링하고 상태 전이를 위해 사용되는 베이스 클래스입니다. 인터페이스는 다음 네 개의 함수 안에 담겨있습니다.

void ExternalEvent(BYTE newState, const EventData* pData = NULL);
void InternalEvent(BYTE newState, const EventData* pData = NULL);
virtual const StateMapRow* GetStateMap() = 0;
virtual const StateMapRowEx* GetStateMapEx() = 0;

ExternalEvent()는 상태 머신에게 외부 이벤트를 생성하며 새로운 상태와 EventData 오브젝트에 대한 포인터를 인자로 가지고 있습니다. InternalEvent() 함수는 같은 인자를 사용하여 내부 이벤트를 생성합니다.

GetStateMap()과 GetStateMapEx()함수는 StateMapRow이나 StateMapRowEx 객체의 배열을 반환하는 함수로 적당한 시점에 상태 엔진에 의해 호출됩니다. 상속받는 클래스는 이 중 하나의 함수를 사용하여 배열을 반환해야 합니다. 만약 상태머신이 상태 함수만 가지고 있다면 GetStateMap()을 사용하고, guard/entry/exit 기능이 필요하다면 GetStateMapEx()이 사용됩니다. 다른 사용하지 않는 버전은 반드시 NULL을 반환해야 합니다. 하지만 곧 설명할 멀티라인 매크로가 이 함수의 구현을 위해 제공됩니다.



자동차 예제



Motor와  MotorNM 클래스는 어떻게 StateMachine을 사용하는지에 대한 예제입니다. MotorNM(No Macro)는 Motor의 디자인과 정확히 일치하지만 매크로를 사용하지 않습니다. 모든 매크로를 사용된 코드를 더 쉽게 이해할 수 있게 해줍니다. 하지만 매크로는 필요한 소스를 기계적으로 감추어주어 사용성을 극대화합니다.

아래 구현된 MotorNM 클래스는 매크로를 포함하고 있지 않습니다.


class MotorNMData : public EventData
{
public:
    INT speed;
};

// Motor class with no macros
class MotorNM : public StateMachine
{
public:
    MotorNM();

    // External events taken by this state machine
    void SetSpeed(MotorNMData* data);
    void Halt();

private:
    INT m_currentSpeed; 

    // State enumeration order must match the order of state method entries
    // in the state map.
    enum States
    {
        ST_IDLE,
        ST_STOP,
        ST_START,
        ST_CHANGE_SPEED,
        ST_MAX_STATES
    };

    // Define the state machine state functions with event data type
    void ST_Idle(const NoEventData*);
    StateAction<MotorNM, NoEventData, &MotorNM::ST_Idle> Idle;

    void ST_Stop(const NoEventData*);
    StateAction<MotorNM, NoEventData, &MotorNM::ST_Stop> Stop;

    void ST_Start(const MotorNMData*);
    StateAction<MotorNM, MotorNMData, &MotorNM::ST_Start> Start;

    void ST_ChangeSpeed(const MotorNMData*);
    StateAction<MotorNM, MotorNMData, &MotorNM::ST_ChangeSpeed> ChangeSpeed;

    // State map to define state object order. Each state map entry defines a
    // state object.
private:
    virtual const StateMapRowEx* GetStateMapEx() { return NULL; }
    virtual const StateMapRow* GetStateMap() {
        static const StateMapRow STATE_MAP[] = { 
            &Idle,
            &Stop,
            &Start,
            &ChangeSpeed,
        }; 
        C_ASSERT((sizeof(STATE_MAP)/sizeof(StateMapRow)) == ST_MAX_STATES); 
        return &STATE_MAP[0]; }
};

비교를 위해 Motor 클래스는 매크로를 사용합니다.

class MotorData : public EventData
{
public:
    INT speed;
};

// Motor class using macro support
class Motor : public StateMachine
{
public:
    Motor();

    // External events taken by this state machine
    void SetSpeed(MotorData* data);
    void Halt();

private:
    INT m_currentSpeed; 

    // State enumeration order must match the order of state method entries
    // in the state map.
    enum States
    {
        ST_IDLE,
        ST_STOP,
        ST_START,
        ST_CHANGE_SPEED,
        ST_MAX_STATES
    };

    // Define the state machine state functions with event data type
    STATE_DECLARE(Motor,     Idle,            NoEventData)
    STATE_DECLARE(Motor,     Stop,            NoEventData)
    STATE_DECLARE(Motor,     Start,           MotorData)
    STATE_DECLARE(Motor,     ChangeSpeed,     MotorData)

    // State map to define state object order. Each state map entry defines a
    // state object.
    BEGIN_STATE_MAP
        STATE_MAP_ENTRY(&Idle)
        STATE_MAP_ENTRY(&Stop)
        STATE_MAP_ENTRY(&Start)
        STATE_MAP_ENTRY(&ChangeSpeed)
    END_STATE_MAP    
};

Motor는 이론적으로 우리의 자동차 제어 상태머신을 구현합니다. 고객은 특정한 속도로 자동차를 출발시키거나 멈출 수 있습니다. SetSpeed()와 Halt() 퍼블릭 함수는 외부 이벤트로 구분됩니다. SetSpeed()는 자동차의 속력을 의미하는 이벤트 데이터를 받습니다. 데이터 구조는 상태 과정이 끝나면 삭제됩니다. 따라서 그 구조가 반드시 EventData를 상속 받고 함수가 불리기 전에 operator new를 통해서 생성되야 합니다.

Motor 클래스가 생성되면 시작 상태는 Idle 입니다. 첫 번째 SetSpeed() 호출은 상태를 Start로 바꾸고 자동차는 움직이기 시작합니다. 이어지는 SetSpeed() 이벤트는 ChangeSpeed 상태로 전시시켜 이미 움직이는 자동차의 속도을 바꿉니다. Halt() 이벤트는 Stop 상태로 전이시키고 상태 실행 도중 내부 이벤트가 생성되어 Idle 상태로 돌립니다.

새로운 상태머신은 다음과 같은 단계를 밟습니다.

1. StateMachine 베이스 클래스를 상속받는다.
2. 각 상태 함수에 대해 States enum을 생성한다.
3. STATE 매크로를 사용하여 상태 함수를 생성한다.
4. 각 상태에 대해 매크로를 사용하여 guard/entry/exit를 생성한다. (옵션)
5. STATE_MAP 매크로를 사용하여 하나의 상태 맵 검색을 생성한다.
6. TRANSITION_MAP 매크로를 사용하여 각 외부 이벤트에 대하여 하나의 상태 맵 검색 테이블을 생성한다.



상태 함수



상태 함수는 각 상태를 구현합니다. 상태머신의 상태 당 한 개의 상태가 존재하고, 해당 구현에서 모든 상태 함수는 반드시 다음과 같은 상태 함수의 형태를 지녀야 합니다.

void <class>::<func>(const EventData*)

예를 들면 void Motor::ST_Start(const MotorData*)과 같이 구현합니다. 중요한 부분은 이 함수가 데이터를 리턴하지 않고 EventData* 만을 인자로 취한다는 것입니다.

STATE_DECLARE 매크로를 사용하여 상태 함수를 정의합니다. 매크로의 인자는 상태 머신의 클래스 이름, 상태 함수의 이름, 이벤트 데이터 타입입니다.

STATE_DECLARE(Motor,     Idle,            NoEventData)
STATE_DECLARE(Motor,     Stop,            NoEventData)
STATE_DECLARE(Motor,     Start,           MotorData)
STATE_DECLARE(Motor,     ChangeSpeed,     MotorData)

위 매크로의 실행 결과는 다음과 같습니다.

void ST_Idle(const NoEventData*);
StateAction<Motor, NoEventData, &Motor::ST_Idle> Idle;

void ST_Stop(const NoEventData*);
StateAction<Motor, NoEventData, &Motor::ST_Stop> Stop;

void ST_Start(const MotorData*);
StateAction<MotorNM, MotorData, &Motor::ST_Start> Start;

void ST_ChangeSpeed(const MotorData*);
StateAction<Motor, MotorData, &Motor::ST_ChangeSpeed> ChangeSpeed;

각 상태 함수의 이름 앞에 ST_가 붙어있습니다. 그리고 state/guard/entry/exit 함수가 자동으로 매크로에 의해 생성됩니다.  STATE_DECLARE(Motor, Idle, NoEventData)를 사용해 함수를 정의했다면 실제 상태함수의 이름은 ST_Idle()이 될 것입니다 .

1. ST_ 상태 함수 앞에 붙는 단어
2. GD_ 가드 함수 앞에 붙는 단어
3. EN_ 엔트리 함수 앞에 붙는 단어
4. EX_  종료 함수 앞에 붙는 단어

상태 함수가 정의되면 STATE_DEFINE 매크로를 사용하여 구현합니다. 인자는 상태 머신 클래 스이름, 상태 함수 이름, 이벤트 데이터 타입입니다. 상태의 구현부는 상태 함수 안으로 들어갑니다. 주의할 점은 모든 상태 함수 코드는 InternalEvent()을 사용하여 다른 상태로 스위치할 수 있다는 것입니다. Guard/entry/exit 함수는 InternalEvent()을 호출할 수 없습니다. 만약 호출하면 런타임 에러가 날 것입니다.


STATE_DEFINE(Motor, Stop, NoEventData)
{
    cout << "Motor::ST_Stop" << endl;
    m_currentSpeed = 0; 

    // perform the stop motor processing here
    // transition to Idle via an internal event
    InternalEvent(ST_IDLE);
}

위 매크로를 확장하면 상태 함수 구현은 다음과 같습니다.


void Motor::ST_Stop(const NoEventData* data)
{
    cout << "Motor::ST_Stop" << endl;
    m_currentSpeed = 0; 

    // perform the stop motor processing here
    // transition to Idle via an internal event
    InternalEvent(ST_IDLE);
}

각 상태 함수는 반드시 매칭되는 enum을 가지고있어야 합니다. 이 enum은 상태 머신의 현재 상태를 저장하기 위해 사용됩니다. Motor의 경우 States가 enum을 제공합니다. 이 부분은 전이 맵을 인덱싱 하는데 사용되고 상태 맵 룩업 테이블에도 사용됩니다.

enum States
{
    ST_IDLE,
    ST_STOP,
    ST_START,
    ST_CHANGE_SPEED,
    ST_MAX_STATES
};

enum의 순서가 상태 맵에 제공된 순서와 일치하는 것은 중요합니다. 이렇게 하면 상태 enum은 특정 상태 호출에 묶입니다. EVENT_IGNORED 와 CANNOT_HAPPEN은 이 상태들과 더불어 이용됩니다. EVENT_IGNORED 가 일어나면 바로 return 하고 아무것도 하지 않습니다. CANNOT_HAPPEN은 일반적으로 일어나면 안 되는 경우이고, 상태 엔진을 정지시킵니다.


상태 맵


상태 머신 엔진은 상태 맵을 이용해서 어떤 상태를 불러와야 할지 알게 됩니다. 상태 맵은 m_currentState 변수를 특정 상태와 매핑합니다. 예를 들어 만약 m_currentState의 값이 2 라면, 세 번째 상태 맵 함수 포인터의 시작점이 호출될 것입니다(0부터 셈으로). 상태 맵은 다음의 세 매크로를 통해 생성됩니다.


BEGIN_STATE_MAP
STATE_MAP_ENTRY
END_STATE_MAP

BEGIN_STATE_MAP은 상태 맵 순서를 시작합니다. 각 STATE_MAP_ENTRY는 상태 함수 이을 인자로 가집니다. END_STATE_MAP은 맵을 종료합니다. Motor의 상태 맵은 다음과 같습니다.


BEGIN_STATE_MAP
    STATE_MAP_ENTRY(&Idle)
    STATE_MAP_ENTRY(&Stop)
    STATE_MAP_ENTRY(&Start)
    STATE_MAP_ENTRY(&ChangeSpeed)
END_STATE_MAP    

완전한 상태 맵은 StateMachine 베이스 클래스의 순수 가상 함수인 GetStateMap()을 구현합니다. 이제 StateMachine 베이스 클래스는 이 호출을 통해 모든 StateMapRow 오브젝트를 가져올 수 있습니다. 매크로를 사용하지 않은 코드는 다음과 같습니다.


private:
    virtual const StateMapRowEx* GetStateMapEx() { return NULL; }
    virtual const StateMapRow* GetStateMap() {
        static const StateMapRow STATE_MAP[] = { 
            &Idle,
            &Stop,
            &Start,
            &ChangeSpeed,
        }; 
        C_ASSERT((sizeof(STATE_MAP)/sizeof(StateMapRow)) == ST_MAX_STATES); 
        return &STATE_MAP[0]; }

C_ASSERT 매크로를 유의하세요. 상태 맵이 잘못된 숫자의 시작점을 갖는 것을 컴파일 타임에 방지해 줍니다. 비주얼 스튜디오는 error C2118: negative subscript 에러를 표시합니다. 컴파일러마다 조금씩 다를 수 있습니다.

이완 다르게 guard/entry/exit 기능들은 _EX 버전의 매크로를 필요로 합니다.


BEGIN_STATE_MAP_EX
STATE_MAP_ENTRY_EX or STATE_MAP_ENTRY_ALL_EX 
END_STATE_MAP_EX

트랜지션 맵의 각 시작점은 StateMapRow에 들어있습니다.


struct StateMapRow
{
    const StateBase* const State;
};

StateBase 포인터는 StateEngine()에 의해 호출된 순수 가상 인터페이스를 가지고 있습니다.


class StateBase
{
public:
    virtual void InvokeStateAction(StateMachine* sm, const EventData* data) const = 0;
};

StateBase에서 파생된 StateAction의 유일한 임무는 InvokeStateAction()을 구현하고 StateMachine과 EventData의 포인터를 올바른 클래스 형태로 변환하고, 상태 멤버 함수를 호출하는 것입니다. 
따라서 각 상태 함수를 호출하는 상태 엔진의 오버헤드는 가상 함수 호출 하나,  static_cast<> 하나, 그리고 dynamic_cast<> 하나 입니다.


template <class SM, class Data, void (SM::*Func)(const Data*)>
class StateAction : public StateBase
{
public:
    virtual void InvokeStateAction(StateMachine* sm, const EventData* data) const 
    {
        // Downcast the state machine and event data to the correct derived type
        SM* derivedSM = static_cast<SM*>(sm);

        // Dynamic cast the data to the correct derived type        
        const Data* derivedData = dynamic_cast<const Data*>(data);
        ASSERT_TRUE(derivedData != NULL);

        // Call the state function
        (derivedSM->*Func)(derivedData);
    }
};

StateAction<>에 대한 템플릿 인자는 상태 머신 클래스(SM), 이벤트 데이터 타입(Data), 그리고 상태 함수에 대한 멤버 함수 포인터(Func) 입니다.



트랜지션 맵


마지막으로 덧붙일 세부사항은 트렌지션 규칙입니다. 상태 머신이 어떤 전이가 일어나야 할지 어떻게 알까요? 답은 전이 맵에 있습니다. 전이 맵은 룩업테이블로 m_currentState 변수를 상태 enum 상수에 매칭합니다. 모든 외부 이벤트는 상태 맵 테이블이 다음 세 가지 매크로로 구현되어 있습니다.


BEGIN_TRANSITION_MAP
TRANSITION_MAP_ENTRY
END_TRANSITION_MAP

Motor의 Halt() 함수는 다음과 같이 구현되어 있습니다.


void Motor::Halt()
{
    BEGIN_TRANSITION_MAP                                      // - Current State -
        TRANSITION_MAP_ENTRY (EVENT_IGNORED)                  // ST_IDLE
        TRANSITION_MAP_ENTRY (CANNOT_HAPPEN)                  // ST_STOP
        TRANSITION_MAP_ENTRY (ST_STOP)                        // ST_START
        TRANSITION_MAP_ENTRY (ST_STOP)                        // ST_CHANGE_SPEED
    END_TRANSITION_MAP(NULL)
}

매크로를 사용하지 않은 Halt() 함수는 다음과 같습니다.  이번에도, C_ASSERT 매크로가 컴파일 타임의 올바르지 않은 트랜지션 맵 도입 숫자가 사용되는 것을 막아줍니다.


void Motor::Halt()
{
    static const BYTE TRANSITIONS[] = {
        EVENT_IGNORED,                    // ST_IDLE
        CANNOT_HAPPEN,                    // ST_STOP
        ST_STOP,                          // ST_START
        ST_STOP,                          // ST_CHANGE_SPEED
    };
    ExternalEvent(TRANSITIONS[GetCurrentState()], NULL); 
    C_ASSERT((sizeof(TRANSITIONS)/sizeof(BYTE)) == ST_MAX_STATES);     
}



상태 엔진


상태엔진은 상태함수를 생성된 이벤트에 의거하여 실생합니다. 전이 맵은 StateMapRow 객체의 배열로 m_currentState 변수의 값에 의해 인덱싱 되어있습니다.  StateEngine() 함수가 실행되면 GetStateMap()를 호출하여 StateMapRow 배열을 살펴봅니다. 


void StateMachine::StateEngine(void)
{
    const StateMapRow* pStateMap = GetStateMap();
    if (pStateMap != NULL)
        StateEngine(pStateMap);
    else
    {
        const StateMapRowEx* pStateMapEx = GetStateMapEx();
        if (pStateMapEx != NULL)
            StateEngine(pStateMapEx);
        else
            ASSERT();
    }
}

StateMapRow 테이블에 새로운 상태 값을 인덱싱 하는 것은 InvokeStateAction()을 호출하여 이러우집니다.


const StateBase* state = pStateMap[m_newState].State;
state->InvokeStateAction(this, pDataTemp);

상태 함수가 실행될 기회를 가진 뒤 이벤트 데이터는 삭제됩니다. 그 뒤 내부 이벤트가 생성되었는지 확인합니다. 하나의 완전한 상태 엔진 함수는 아래 정의되어 있습니다. 다른 오버로드 된 상태 엔진 함수는 상태 머신을 StateMapRowEx 테이블로 다룹니다.


void StateMachine::StateEngine(const StateMapRow* const pStateMap)
{
    const EventData* pDataTemp = NULL;    
    
    // While events are being generated keep executing states
    while (m_eventGenerated)
    {
        // Error check that the new state is valid before proceeding
        ASSERT_TRUE(m_newState < MAX_STATES);
    
        // Get the pointer from the state map
        const StateBase* state = pStateMap[m_newState].State;
            
           // Copy of event data pointer
        pDataTemp = m_pEventData;

        // Event data used up, reset the pointer
        m_pEventData = NULL;

        // Event used up, reset the flag
        m_eventGenerated = FALSE;

        // Switch to the new current state
        SetCurrentState(m_newState);

        // Execute the state action passing in event data
        ASSERT_TRUE(state != NULL);
        state->InvokeStateAction(this, pDataTemp);

        // If event data was used, then delete it
        if (pDataTemp)
        {
             delete pDataTemp;
             pDataTemp = NULL;
        }
    }
}



이벤트 생성


이 시점에서 우리는 동작 가능한 상태 머신을 만들었습니다. 이제 이벤트를 어떻게 생성하는지 보겠습니다. 외부 이벤트는 new를 사용하여 이벤트 데이터 구조를 힙에 생성하고, 구조 멤버 변수를 대입하고, 외부 이벤트 함수를 호출함으로써 생성됩니다. 다음 코드는 비동기 콜이 만들어지는 방법입니다.

MotorData* data = new MotorData();
data->speed = 50;
motor.SetSpeed(data);

내부 이벤트를 상태 함수 안에서 생성하는 방법은 InternalEvent()를 호출하는 것입니다. 목적지가 이벤트 데이터를 받지 않는다면 함수는 필요한 상태만 가지고 호출됩니다.

InternalEvent(ST_IDLE);

위의 예제에서 상태 함수가 실행을 마치면 상태 머신은 Idle 상태로 전이할 것입니다. 하지만 이벤트 데이터가 목적 상태에서 필요로 한다면, 데이터 구조가 힙에 생성되고 인자로 전달되어야 합니다.


MotorData* data = new MotorData();
data->speed = 100;
InternalEvent(ST_CHANGE_SPEED, data);


멀티스레드 안전성


상태 머신이 실행중에 있을 때 다른 스레드에 의해서 영향 받는 것을 방지하기 위해 StateMachine 클래스는 ExternalEvent() 안에서 락을 사용할 수 있습니다. 외부 이벤트가 실행되기 전에 세마포가 락이 걸립니다. 그리고 외부 이벤트와 모든 내부 이벤트가 끝났을 때 소프트웨어 락이 풀리고, 다른 외부 이벤트가 상태 머신 안으로 들어올 수 있게 됩니다.

코드의 주석에 어디에 락과 언락이 들어가야 하는지 나와있습니다. 각 StateMachine은 각자의 소프트웨어 락을 가지고 있어야 합니다. 이렇게 해야 한 개의 객체가 다른 모든 StateMachine의 동작을 막는 현상을 방지할 수 있습니다. 주의할 점은 소프트웨어 락은 StateMachine이 멀티스레드 환경에서 동작할 때만 필요하다는 것입니다. 만약 그러지 않다면 락은 필요 없습니다.



장점


상태 머신을 이러한 방법으로 구현하는 것은 기존의 스위치 케이스 구현에 비해 많은 노력이 들어갑니다. 하지만 페이오프는 모든 멀티스레드 환경에서 동작 가능한 더 탄탄한 구조를 갖는다는 것입니다. 각 상태가 각자의 함수 안에 들어가있는 것은 하나의 큰 스위치 구문보다 읽기 쉽습니다. 그리고 각 상태별로 고유한 이벤트 데이터를 주고받을 수 있게 해줍니다. 추가적으로, 상태 전이의 유효성을 검사하는 것은 사용자가 원하지 않는 상태 전이를 사용함으로써 올 수 있는 에러들을 방지해줍니다.