01. 물리엔진의 구조

2D 물리엔진은 무엇으로 이루어지는가
물리엔진의 구조 (매 프레임마다 이뤄지는 broad/narrowPhase, colResolve) +게임 엔진에서, 렌더러와의 통합)
World & Body 클래스 맛보기

2D 물리엔진은 무엇으로 이루어지는가

2D 물리엔진의 목적은,

'2차원 세상 속에서 서로 상호작용하는 물체의 움직임을 시뮬레이션'

하는 데 있습니다.

한번 저 시뮬레이션에 대해 생각을 해봅시다.

물리엔진이 사용되는 예시로써 플랫포머 게임 만한 게 없죠.

밑 사진은 슈퍼 마리오 시리즈 플레이화면입니다.

마리오가 벽돌 위에 올라가 있네요.

시뮬레이션 내에서는, 위 상황을 밑 그림처럼 해석하고 있는 중일 겁니다.

마리오가 벽돌을 밟고 있을 수 있는 이유는,

물리 시뮬레이션에서 '움직이는 캐릭터가 벽돌과 충돌했다' 라는 정보를 감지하고,

마리오가 벽돌을 뚫고 떨어지지 않도록

해당 충돌에 대해서 캐릭터를 벽돌 위에 유지시키고 있기 때문입니다.

이때 물리 시뮬레이션에서는 저 '충돌 정보'를

위 사진에서 빨간색 점 2개로 그려진

'접촉(Contact)'들로 저장해 둡니다.

이제 저희는 물리엔진의 핵심적인 요소 3가지를 유추할 수 있습니다.

2차원 세계 World
(세계 안의) 물체 : Body
(물체 간의 상호작용으로 인한) 접촉 : Contact(s)

물리엔진이 제공하는 가장 큰 인터페이스는

World라고 불리는, 2차원 세계를 나타내는 클래스입니다.

사용자가 새 World를 만들어서

그 안에 여러 Body를 추가하면,

물리 엔진 측에서는 매 프레임마다

세계를 갱신해가면서

어떤 물체들이 충돌하는지를 관찰하고

그에 맞는 조정을 수행합니다.

보통 Contact 클래스는 World 내에서만 사용되는 클래스로써,

게임 클라이언트 프로그래머가 접촉 정보를 고려할 일은 많지 않습니다.

2D 물리엔진의 구조

대개 '물리엔진' 이라고 하면,

최소한 다음 조건을 만족해야 합니다.

가장 중요한 2개의 클래스인 'World' 와 'Body' 인터페이스를 사용자에게 제공함
World 에는 '한 프레임을 진행하는 메서드' 가 존재함
사용자는 자신이 만든 Body 객체의 위치 & 회전 정보를 읽을 수 있음

이를 예시 코드로 나타내면, 이렇게 되겠네요.

int main() {

    namespace pe = ::PhysicsEngine;

    // 물리엔진이 제공하는 'World' 를 생성
    pe::World world{};

    // 물체를 생성하고, 세계 안에 집어넣기
    pe::Body* body = world.AddBody();

    while (IsRunning) {

        // 시뮬레이션 한 프레임 진행하기.
        world.Step();

        // 물체의 위치 정보 얻기.
        printf("물체의 위치 : (%f, %f)\n", body->GetPosition().x, body->GetPosition().y);
    }

}

하지만 저 3개의 인터페이스만으로는

땅에 떨어지는 사과 같은 건 쉽게 구현하겠지만,

복잡한 장면은 구현하기가 힘듦니다.

본격적인 2D 물리엔진을 만드려면,

'사용자 단' 에서 이러한 인터페이스가 있어야 합니다.

제약(Constraint) 인터페이스 + 다양한 조인트
콜라이더와 여러 도형(Shape)의 정의
도형 분해(Decomposition)와 합성(Composition)

또한, 사용자가 볼 수 없는 부분에서는

매우 많은 개념을 도입해주어야 합니다.

간단히 나열해보죠.

충돌 감지 알고리즘
충돌 해결(=Solver) 알고리즘
공간 분할 시스템
최적화 시스템 (대충 8개정도 됩니다.)

좋습니다.

설명을 좀 두서없이 했으니,

이제 2D 물리엔진이 어떻게 돌아가는지 알아봅시다.

사용자가 월드를 만들어 그 안에 Body들을 이미 추가했다고 가정하고,

world.step() 메서드 안에서 무슨 일이 일어나는지를 차례차례 보는 겁니다.

1. 브로드 페이즈 (Broad Phase)

물리 엔진 내에서, 한 프레임이 시작되었을 때

가장 먼저 하는 것은

'충돌 가능성이 높은 쌍' 목록을 만드는 것입니다.

밑 사진을 봐주세요.

알록달록한 도형들이 월드 안의 바디라고 해 보죠.

파란색 오각형에 주목해주세요.

그 주변에는 하늘색 삼각형, 테니스공색 사각형이 있네요.

파란색 오각형의 속도/각속도가 크지 않다고 가정합시다.

만약, 이 프레임, 한 순간에서

파란색 오각형과 빨간색 오각형이 충돌할 가능성이 있을까요?

없습니다. 다만, 그 주변에 있는 2개의 도형과는

충돌할 가능성이 있죠.

그렇기에 물리적으로 가까이 있는 도형들끼리 묶어서

나중에 그 안의 도형끼리만 '충돌 검사' 를 하는 것입니다.

이때 '물리적으로 가까이 있는 도형들을 묶는' 과정을

브로드 페이즈 (Broad Phase) 라고 하며,

바로 다음 단계에서, 실질적인 충돌 검사 -

즉 Narrow 한 검사 이전에 넓은 (Broad) 관점으로 거르기에

이러한 이름이 붙었습니다.

그런데 이 과정이 왜 필요한 걸까요?

물리 엔진은 그냥

'두 물체가 충돌하면, 적절히 두 물체를 떼어놓는다'

라는 직관에 충실하면 되지 않을까요?

이 과정이 필요한 이유는,

한 바디를 월드 안의 모든 바디에 대해 검사해 버리면

시간복잡도가 O(n²) 로 고정되기 때문입니다.

코드로 나타내면 밑과 같죠.

for (int i = 0; i < N; i++) {
    for (int j = (i + 1); j < N; j++) {
        충돌감지(objects[i], objects[j]);
    }
}

알고리즘을 조금이라도 공부해 보셨다면,

저게 무슨 의미인지 알 거라고 생각합니다.

반면에, 브로드 페이즈 단계를 도입해서

'충돌 가능성이 높은 쌍' 을 만든다.

즉, '충돌할 수 없는 쌍' 을 모두 '제거'하면

O(NlogN) 까지 줄어듭니다.

지금은 어떤 방식으로 이러한 '쌍'을 찾는지는

모르고 계셔도 됩니다.

애초에 공간을 나누는 방법에는

여러 가지가 있기 때문에,

차근차근 알아가 봅시다.

이 과정에서 입력과 출력을 직관적으로 정리해보면,

입력 : 물체 리스트
출력 : 물체 쌍 리스트

이렇게 되겠네요.

2. 내로우 페이즈 (Narrow Phase)

좋습니다. 앞에서

'충돌 가능성이 없는 쌍을 걸러내는' 작업을 해두었기에,

이제 가능한 쌍을 모두 순회하면서

첫 번째 물체와 두 번째 물체가

충돌하는지 검사하면 됩니다.

이를 내로우 페이즈 (Narrow Phase) 라고 합니다.

어떤 물체 A가

바닥 역할의 B라는 물체에 떨어진 상황을 생각해봅시다.

위 그림은, 빠르게 운동하던 A가

B 물체를 뚫는 시점을 포착한 것입니다.

내로우 페이즈에서 하는 일은,

이 시점에서

A와 B의 충돌점
A와 B를 떨어뜨리기 위한 최소한의 벡터

를 계산하는 것입니다.

이때 저 빨간색 점 2개가 충돌점이 되고,

'A의 꼭짓점을 B의 면으로부터 떨어뜨리기 위해'

위를 향하는 벡터가 생길 겁니다.

(어떤 물체를 기준으로 이 벡터가 계산되는지는

이 다음 글, 02. 충돌 감지 알고리즘에서 자세히 다룹니다)

그렇게 '한 충돌 이벤트에 관한 정보'들을 묶은 것을

물리 엔진에서는 관습적으로

Contact Manifold 라고 칭합니다.

쌍들을 순회하면서,

충돌이 일어난 경우에만 다음 단계를 위해서

'무슨 물체끼리, 어떤 형태로 충돌하였는지' 를 모아두면

내로우 페이즈가 끝납니다.

내로우 페이즈의 입력과 출력은:

입력 : 물체 쌍 리스트
출력 : Contact Manifold 리스트

이렇게 됩니다.

3. 제약 풀기 (Solving Constraints)

앞서서 '제약 인터페이스' 라는 걸 언급했죠.

제약 (Constraints) 이란 무엇일까요?

물리 엔진에서, 제약을 정의한다고 하면

'두 물체에 외부 임펄스를 가하는, 조건 및 수식' 을 만드는 것으로 나타납니다.

말이 어려우니 쉽게 이해해 봅시다.

밑의 그림은 물체 A와 물체 B를 줄로 이어놓은 상황입니다.

만약 A와 B 사이의 거리가

줄의 길이보다 작다면

A와 B는 자유로이 움직일 수 있을 것이고 -

A와 B 사이의 거리가 줄의 길이만큼 떨어져 있거나

팽팽히 당기고 있는 상황이라면

A와 B는 각각 당기는 방향으로는 더이상 움직일 수 없을 겁니다.

여기서, 저 "줄을 이어놓는다" 라는 행위가

'제약'을 거는 것입니다.

저 상황을 프로그래머의 관점에서 해석해 봅시다.

(줄이 묶인 부분은 고려하지 않고요)

A와 B사이의 거리가 줄의 길이보다 가깝다면 아무것도 하지 않는다.
반대로, 더 멀다면 A -> B 방향의 단위 벡터에 상수를 곱해, A에 그만큼의 힘을 준다. (B에도 마찬가지)

혹시 눈치 채셨나요?

맞습니다. 접촉이 일어난 상황도, 제약으로 바라볼 수 있습니다.

제약을 걸지 않아도 되는 상황은

두 물체가 아예 겹치지 않았을 때이고 -

두 물체가 겹쳤을 때 비로소

"두 물체를 떨어뜨리기 위해, 적절한 임펄스를 가한다"

라는 제약인 것이죠.

제약 '인터페이스' 라고 한 것은 이 떄문입니다.

물리 엔진에서 흔히 볼 수 있는

고무줄 같이 두 물체를 묶어놓는 등의

'조인트(Joint)' 와, 물체 간의 접촉(Contact)을 없애는 건

2개의 물체를 타겟으로 하고

Solve() 라는 메서드를 가지는 인터페이스로 표현됩니다.

아무튼,

지금은 접촉에 대해서만 생각합시다.

이전 단계에서 접촉 매니폴드들을 생성해 놓았죠?

이 단계에서는, 그 매니폴드들을 전부 순회하면서

접촉 제약을 실질적으로 만들고

그걸 풉니다(Solving).

이때,

두 물체의 마찰력, 탄성 계수같은

여러 속성들을 고려하여

적절히 떨어뜨리기 위한 방법에는

여러 가지가 있습니다.

이들을 솔버(Solver) 로 부릅니다.

대표적인 솔버 계열로는

PBD (position based dynamics)
PGS (projected gauss-seidel)
LCP (linear complementarity problem)

가 있습니다.

box2d의 제작자 Erin Catto 님께서 만드신

8개의 솔버를 비교하는 프로젝트가 있습니다.

깃허브 소스

영상 보기

다양한 솔버를 공부하고 싶으시다면 꼭 보시는 것을 추천드립니다.

앞으로의 글에서는 Box2D 에서 사용된

PGS 솔버를 메인으로 설명하겠습니다.

(PGS 솔버는 순차적 임펄스, Sequential impulse 방식으로도 알려져 있습니다)

사실 물리 엔진을 이해하는데에

가장 어려운 부분이 이 부분입니다.

분명 코드 자체의 양은 많지 않지만

이러한 공식이 어떻게 도출되었는지를 깊게 알려면

야코비안 행렬, 라그랑지안 계수 같은

순수한 수학 & 물리 개념을

이해해야 하기 때문입니다.

4. 적분 및 최적화

이 단계에서 말하는 적분이란,

위치 - 속도 - 가속도 와

회전 - 각속도 - 각가속도 의 관계에서

(각)가속도를 (각)속도에 누적하고

(각)속도를 위치 / 회전값에 누적해가는 걸 말합니다.

한 마디로 말하면

"현재 상태를 가지고, 다음 상태를 예측한다"

인 것이죠.

현재 World 안에 들어있는

모든 물체에 대해서,

수치적분을 수행한다고 하면

for (auto& body : m_bodies){

    body.velocity += body.acceleration * dt;
    body.position += body.velocity * dt;

}

이런 식입니다.

(위 과정은 반-암시적 오일러 방법(Semi-Implicit Euler Method) 이라 하는

수치적분의 한 종류입니다)

적분이 끝난 후에도,

최신 물리 엔진에는

들어가는 세부적인 기술들이 많습니다.

다음은 그 목록입니다.

Warm Starting
Accumulated Impulse
Position Correction
Sub Stepping
TOI (Time of impact)
CCD (Continous Collision Detection)
Islanding
Sleeping

이 기술들은 전부 Box2D 안에 구현되어 있으며,

물리 엔진을 한층 더

안정적이고 세밀하게 만드는 데에 의의가 있습니다.

각각의 기술들은 앞으로의 글에서

하나씩 다뤄보도록 하겠습니다.

(참고로 무조건 적분이 끝난 후에

이 최적화들이 진행되는 건 아닙니다.)

World & Body 클래스 맛보기

다음 글부터 이 클래스를 구현할 것은 아니지만,

제일 중요한 두 클래스를 간략히 봅시다.

참고로 '이런 기능이 있겠구나' 하고

그냥 추상적으로 적은 코드입니다.

먼저 World입니다.

class World2D {

private:
    // 이 월드 안에 있는 물체들.
    std::vector<Body2D*> m_bodies{};

    // 제약들 모아두기
    std::vector<Contact2D*> m_contacts{};
    std::vector<Joint2D*> m_joints{};

public:

    void step(const float& dt);

public:

    Body2D* add_box_body(const Vector2f& size);
    Body2D* add_polygon_body(const std::vector<Vector2f>& vertices);
    Body2D* add_circle_body(const float& radius);

    Joint2D* add_spring_joint(Body2D* a, Body2D* b);
    ...
};

단순히 이 물체 / 조인트가

어느 월드에 존해는지를 구별하기 위한

래핑 / 컨텍스트 클래스로 보셔도 됩니다.

다음은 Body입니다.

class Body2D {

private:

    std::vector<Collider2D*> m_colliders{};

private:
    Vector2f m_force{};
    Vector2f m_velocity{};
    Vector2f m_position{};

    float m_torque = 0.0f;
    float m_angular_velocity = 0.0f;
    float m_rotation = 0.0f;

public:

    void update(const float& dt);

public:

    void set_position(const Vector2f& value);
    void set_velocity(const Vector2f& value);
    void set_force(const Vector2f& value);

    void set_rotation(const float& value);
    void set_angular_velocity(const float& value);
    void set_torque(const float& value);

public:

    const Vector2f& get_position() const;
    const Vector2f& get_velocity() const;
    const Vector2f& get_force() const;

    const float& get_rotation() const;
    const float& get_angular_velocity() const;
    const float& get_torque() const;

};

위에서는 언급하지 않았지만,

추후에 Collider2D 와 그 안에 들어가는 Shape2D 클래스를 구현하게 됩니다.

Shape2D 는 인터페이스로써,

원인지 / (볼록) 다각형인지 / 캡슐인지, 형태를 나타냅니다.

그리고 이 '형태' 를 실질적을 띄고 있는,

위치 & 회전 정보를 가지는 클래스를

Collider2D 라고 합니다.

Note

Shape2D 클래스는 '로컬 좌표계' 상에서의
정보만을 갖습니다.
그래픽스의 모델 <-> 월드 좌표계 개념을 떠올려 주세요.
Shape2D 가 모델 공간의 정점 데이터라면,
Collider2D 가 그 데이터를 쓰는
엔진 단의 물체라고 생각하시면 됩니다.

나머지는

위치 / 속도 / 힘(가속도)

이렇게 이뤄진 선형 운동(Linear motion) 값과

회전 / 각속도 / 토크(각가속도)

로 이뤄진 각운동(Angular motion) 값이 있고,

이에 대한 setget이 있습니다.

Body2D::update(float) 를 불러서

이를 수치적분하게 됩니다.

다음 게시글에서는,

물리 엔진의 첫 번째 난관인

충돌 감지에 대해서 다룹니다.

물리 엔진을 극단적으로 2개의 과정으로 나눈다면

충돌을 감지(Collision Detection) 과

충돌을 해소(Collision Resolving) 로 나눠질 정도로

충돌 감지는 매우 중요한 과정입니다.