정점 처리 (vertex processing)

로컬 공간의 정점들에 월드 변환, 뷰 변환, 클립 변환 및 조명 등을 연산하여 적용하는 단계.

월드 변환

선형 변환인 회전, 크기 변환과 아핀 변환인 이동 변환을 적용한다.

이동 변환은 한 차원 높은 행렬을 사용해야 하기 때문에 3차원 공간 기준으로는 4x4 행렬을 사용한다.

참고로 왼손 좌표계(DX)는 회전각이 양수라면 시계, 오른손 좌표계(OpenGL)는 반시계 방향으로 회전한다.

또한 DX는 행벡터를 사용하기 때문에 벡터*행렬 순서로 곱하는 것과 더불어 SRT 순서로 곱한다.

Vworld = Vlocal * S * R * T

V = 정점, S = 크기 변환 행렬, R = 회전 변환 행렬, T = 이동 변환 행렬

정점에 계산되는 월드 행렬(모델링 행렬)을 M이라고 할 때, 크기 변환 행렬의 x,y,z가 균등한 비율의 축소 및 확대라면 노말 벡터에도 적용이 가능하다.

하지만 비균등 축소 및 확대를 포함한다면 사용이 불가능하다. 비균등 축소 및 확대가 적용된 모델링 행렬을 노멀 벡터에 적용한다면 수직 관계가 깨지게 된다.

그래서 노말 벡터에는 M의 역행렬의 전치 행렬을 곱해서 수직 관계를 유지시켜준다.

* 노말 벡터 변환과 관련된 자세한 내용은 34p 참고

뷰 변환

◾ 카메라 공간

정점들이 월드 공간에 배치되면 원하는 부분만 관찰하기 위해 카메라의 파라미터를 설정해야 한다.

월드 공간의 모든 물체는 카메라 공간으로 변환되고, 클리핑을 통해 효율적인 렌더링 알고리즘 설계가 가능해진다.

뷰 변환을 위한 뷰 행렬을 구하는 대표적인 방법으로 EYE, AT, UP 세 가지 파라미터를 사용하여 구하는 방법이 있다.

EYE : 카메라의 좌표

AT : 카메라가 바라보는 기준점 (또는 물체)

UP : 월드 y축 기저벡터

카메라의 forward(z축) 벡터는 AT - EYE를 정규화 시키면 구할 수 있고, right(x축) 벡터는 forward와 UP을 외적하여 구할 수 있다. 마지막으로 forward와 right를 외적하면 up(y축)벡터까지 모두 구할 수 있다.

◾ 공간 이전과 뷰 행렬

월드 공간의 기저벡터는 각 축에 해당하는 e1(1,0,0), e2(0,1,0), e3(0,0,1)이다. 이는 {O, e1, e2, e3}으로 표현할 수 있다.

카메라 공간의 원점은 카메라의 위치에 해당되고 각 축 역시 카메라의 기저벡터에 해당되기 때문에 {EYE, right, up, forward}로 표현할 수 있다.

월드 공간의 좌표를 카메라 공간의 좌표로 변환하는 것을 뷰 변환 또는 카메라 변환이라고 한다.

간단하게 생각하면 된다. 카메라 공간에서는 원점을 카메라의 좌표로 봐야한다. 그러면 카메라를 원점으로 옮기는 행렬을 만들고 그 행렬을 정점들에 곱해주면 카메라 공간에 배치된것처럼 보이게 될 것이다.

계산 또한 매우 간단하다. 어떤 로컬 공간의 정점에 모델링 행렬 M을 곱해서 월드 공간에 배치했다면 M의 역행렬을 곱하면 다시 로컬 공간(0, 0, 0)으로 돌아올 것이다. 마찬가지로 카메라에 M의 역행렬을 곱하면 (0,0,0) 즉, 원점으로 돌아오게 된다. 카메라는 스케일링이 의미가 없기때문에 이동 행렬의 역행렬 * 회전 행렬의 역행렬(T-1 * R-1 = V)을 곱해주면 된다. (행벡터 기준)

이제 각 정점에 V를 곱해주면 정점들은 카메라 공간으로 이동하게 된다.

정점별 조명

차후 조명 연산에서 카메라와 정점간의 각도에 따라 반사된 빛이 카메라에 얼마나 들어오는지 결정하게 된다.

투영 변환

뷰 변환에 의해 모든 정점들이 카메라 공간 {EYE, right, up, forward}로 변환되었다.

이제 이 정점들을 제한된 카메라 시야에 렌더링 해볼 차례이다.

◾ 뷰 프러스텀 (절두체)

일반적으로 카메라의 시야는 제한되어 있어서 카메라 공간의 모든 물체를 화면에 담아낼 수 없다. 이 가시 영역을 뷰 볼륨이라고 부르는데, fovy, aspect, n, f 총 4가지 파라미터를 사용하여 결정한다.

fovy : field of view. 시야각

aspect : 뷰 볼륨의 종횡비 (ex: 4:3, 16:9)

n : near plane. 근평면

f : far plane. 원평면

위의 파라미터를 통해 생성된 절두체 외부에 놓인 물체는 뷰 프러스텀 컬링을 통해 렌더링 파이프라인에 들어가지 못하게 해서 보이지 않는 것으로 처리한다.

그런데 물체가 절두체의 경계에 존재하는 경우가 발생하는데, 이 때 해당 물체 전체가 렌더링되지 않는것이 아니라 절두체 외부에 있는 정점들만 잘라내고 경우에 따라 새로운 삼각형을 생성하는 클리핑 과정이 필요하다.

클리핑을 하기 전에 개별적인 폴리곤 메쉬를 감싸는 바운딩 볼륨을 미리 계산해두고 바운딩 볼륨이 절두체 외부에 있는지를 우선적으로 검사한다.

바운딩 볼륨은 추가적인 비용이 발생하는 것이지만 약간의 CPU 비용을 지불하는 대신 상당량의 GPU 비용을 절감하는 효과를 얻을 수 있다.

폴리곤 메쉬가 절두체의 평면과 겹치는 경우, 절두체 안쪽에 놓인 부분만 잘라내서 파이프라인의 다음 단계로 보낸다.

◾ 투영 행렬

절두체는 피라미드 모양이기 때문에 비스듬한 면이 존재해서 클리핑 연산이 복잡해지는 문제가 있다.

이를 위해 직육면체(2x2x1 크기)의 새로운 뷰 볼륨으로 변환하여 클립 공간으로 보내는 투영 변환이 필요해진다.

이름과는 달리 투영 변환은 카메라 공간의 3차원 물체를 2차원으로 투영하는 대신에 또 다른 3차원 물체로 변형시키는 변환이다.

절두체는 원점에 위치한 카메라로 수렴하는 투영선의 집합으로 이해할수도 있다.

이 투영선들을 직교 투영하여 모두 평행하게 만들어서 원근감을 실현 시킨다. 이것이 투영 변환이다.

투영 변환의 중요한 특징 중 하나는 아핀 변환에서는 마지막 요소인 w가 1이었지만 투영 행렬은 그렇지 않다.

투영 행렬의 유도는 글로 작성하기가 어려워서 책을 다시 보는 것이 좋을 것 같다. (p.51, 이득우의 게임수학 p.402)

C++17 이후부터 등장한 타입이다.

c_str 메소드가 없는것을 빼면 std::string과 인터페이스가 동일하다. 오히려 문자열을 축소시킬 수 있도록 remove_prefix, remove_suffix 메소드가 추가로 제공된다.

string_view는 매개변수로 전달 시 const string&과 달리 오버헤드가 없다. 정확히는 없다기 보다 값으로 전달하지만 스트링에 대한 포인터와 길이만 갖고 있기 때문에 오버헤드가 매우 적다.

그러니 읽기 전용 스트링을 함수의 매개변수로 받는 경우에는 const string&, const char* 대신 string_view를 사용하도록 하자.

string str = "Hello";
string_view sv = " world";
auto result = str + sv; // compile error

둘을 결합시키고 싶다면 data 메소드를 사용하면 된다.

string 리터럴을 string_literals::s를 통해 만들 수 있는 것처럼 string_view 리터럴도 string_view_literals::sv를 통해 만들 수 있다.

// C++17 이전
// 복제 리스트 초기화
auto a = {11}; // initializer_list<int>
auto b = {11, 22}; // initializer_list<int>

// 직접 리스트 초기화
auto c {11}; // initializer_list<int>
auto d {11, 22}; // initializer_list<int>


// C++17 이후
// 복제 리스트 초기화
auto a = {11}; // initializer_list<int>
auto b = {11, 22}; // initializer_list<int>

// 직접 리스트 초기화
auto c {11}; // int
auto d {11, 22}; // compile error

C++17 이후로 auto 타입 추론과 관련하여 복제 리스트 초기화와 직접 리스트 초기화가 달라졌다.

공간 분할 (Spatial Partition)

동기

게임 월드에는 공간이라는 개념이 있기 때문에 게임 오브젝트는 공간 어딘가의 위치에 존재하게 된다.

플레이어는 공간 내에 존재하는 모든 오브젝트와 거리에 상관없이 상호작용 하거나 렌더링 할 필요 없이 일정 거리 이내의 오브젝트들과 상호작용 하거나 렌더링 해주는걸로 충분하다.

이를 위해서는 주변에 어떤 객체들이 있는지를 알아야 한다.

void handleMelee(Unit* units[], int numUnits) {
    for (int a = 0; a < numUnits - 1; ++a) {
        for (int b = a + 1; b < numUnits; ++b) {
            if (units[a]->position() == units[b]->position()) {
                handleAttack(units[a], units[b]);
            }
        }
    }
}

맵에 존재하는 유닛끼리 거리를 확인하여 공격하는 코드를 나이브하게 작성한 완전탐색 코드이다.

매 프레임마다 O(n²)의 시간 복잡도를 소모하게된다. 유닛 수가 많아지면 검사 횟수가 기하급수적으로 늘어나게 되어 성능이 수직 하락하는 문제가 생긴다.

일단 당장 눈에 보이는 문제는 정렬이 되어 있지 않다는 것이다. 만약 거리순으로 정렬이 되어있다면 이진 탐색 등으로 매우 빠른 시간내에 주변 유닛을 탐색할 수 있다.

위의 예시처럼 전체 범위에 대해 1차원 배열을 사용한 것처럼 여러 범위로 쪼개어 확장시키면 2차원 이상의 공간을 사용할 수 있고 이것이 바로 공간 분할 패턴이다.

패턴

객체들은 공간 위에서의 위치 값을 갖는다. 이들 객체를 객체 위치에 따라 구성되는 공간 자료구조에 저장한다. 공간 자료구조를 통해서 같은 위치 혹은 주변에 있는 객체를 빠르게 찾을 수 있다. 객체 위치가 바뀌면 공간 자료구조도 업데이트해 계속해서 객체를 찾을 수 있도록 한다.

언제 쓸 것인가?

동적 오브젝트 뿐만 아니라 지형 등의 정적 오브젝트를 저장하는 데에도 흔하게 사용된다.

복잡한 게임에서는 콘텐츠별로 공간 분할 자료구조를 따로 두기도 한다.

위치 값이 있는 객체가 많고, 위치에 따라 객체를 찾는 질의가 성능에 영향을 줄 정도로 잦을 때 사용한다.

주의사항

공간 분할 패턴을 사용하면 O(n²)인 복잡도를 쓸만한 수준으로 낮출 수 있지만 이는 객체가 많을수록 의미가 생긴다.

만약 n이 충분히 작으면 굳이 신경 쓸 필요가 없다.

객체를 위치에 따라 정리하기 때문에 객체의 위치 변경을 처리하기가 매우 어렵다.

객체의 바뀐 위치에 맞춰서 자료구조를 재정리해야 하기 때문에 코드가 더 복잡해질 뿐더러 CPU도 더 많이 소모하므로 공간 분할 패턴을 적용할만한 값어치가 있는지를 먼저 확인해보아야 한다.

게다가 일반적인 최적화들처럼 속도를 위해 메모리를 희생하기 때문에 메모리가 부족한 환경이라면 오히려 손해일 수도 있다.

예제

전체 전장을 모눈종이의 칸처럼 고정 크기로 나누고 유닛들을 배열이 아니라 격자 안에 넣는다.

칸마다 유닛 리스트가 존재하고 유닛이 해당 칸의 범위 안에 들어오면 그 유닛을 리스트에 저장한다.

그 이후에 전투를 처리할 때는 같은 칸 안에 들어있는 유닛만 신경 쓰면 되기 때문에 훨씬 적은 숫자의 유닛들과 비교할 수 있게 된다.

class Unit {
    friend class Grid;

public:
    Unit(Grid* grid, double x, double y) : grid_(grid), x_(x), y_(y) {}
    void move(double x, double y);

private:
    double x_, y_;
    Grid* grid_;
    Unit* prev_;
    Unit* next_;
};

class Grid {
public:
    Grid() {
        for (int x = 0; x < NUM_CELLS; ++x) {
            for (int y = 0; y < NUM_CELLS; ++y) {
                cells_[x][y] = nullptr;
            }
        }
    }
    
    static const int NUM_CELLS = 10;
    static const int CELL_SIZE = 20;
    
private:
    Unit* cells_[NUM_CELLS][NUM_CELLS];
};

각 유닛은 2차원 위치 좌표와 자신이 속해있는 그리드의 포인터를 가진다.

연결 리스트로 구현할 것이기 때문에 prev, next 포인터 역시 만들어둔다.

Unit::Unit(Grid* grid, double x, double y)
    : grid_(grid), x_(x), y_(y), prev_(nullptr), next_(nullptr) {
    grid_->add(this);
}


void Grid::add(Unit* unit) {
    int cellX = (int)(unit->x_ / Grid::CELL_SIZE);
    int cellY = (int)(unit->y_ / Grid::CELL_SIZE);
    
    unit->prev_ = nullptr;
    unit->next_ = cells+[cellX][cellY];
    cells_[cellX][cellY] = unit;
    
    if (unit->next_ != nullptr)
        unit->next_->prev_ = unit;
}

이제 유닛은 새로 생성될때마다 그리드에 속함과 동시에 리스트에 추가한다. 흐름 자체는 단순하다.

void Grid::handleMelee() {
    for (int x = ; x < NUM_CELLS; ++x) {
        for (int y = 0; y < NUM_CELLS; ++y) {
            handleCell(cells_[x][y]);
        }
    }
}

void Grid::handleCell(Unit* unit) {
    while (unit != nullptr) {
        Unit* other = unit->next_;
        while (other != nullptr) {
            if (unit->x_ == other->x_ && unit->y_ == other->y_)
                handleAttack(unit, other);
            other = other->next_;
        }
        unit = unit->next_;
    }
}

코드만 보면 기존과 동일하게 모든 칸을 순회하며 함수를 호출하지만 차이가 있다면 맵에 존재하는 모든 유닛을 완전탐색 하는것이 아니라 같은 칸에 들어있는 유닛들만 확인하게 되므로 해당 칸을 기준으로 본다면 연산량이 대폭 줄어든다.

성능적인 문제는 해결된듯 하지만 유닛이 항상 칸에 묶여 있어야 하다보니 유닛이 다른 칸으로 이동할 때마다 현재 칸의 리스트에서 제거하고 이동하는 칸의 리스트에 추가해주는 작업을 해주어야 한다.

void Unit::move(double x, double y) {
    grid_->move(this, x, y);
}


void Grid::move(Unit* unit, double x, double y) {
    // 기존에 위치하던 칸 확인
    int oldCellX = (int)(unit->x_ / Grid::CELL_SIZE);
    int oldCellY = (int)(unit->y_ / Grid::CELL_SIZE);
    
    // 새로 이동할 칸 확인
    int cellX = (int)(x / Grid::CELL_SIZE);
    int cellY = (int)(y / Grid::CELL_SIZE);
    
    unit->x_ = x;
    unit->y_ = y;
    
    // 변동이 없으면 작업X
    if (oldCellX == cellX && oldCellY == cellY)
        return;
        
    if (unit->prev_ != nullptr)
        unit->prev_->next_ = unit->next_;
        
    if (unit->next_ != nullptr)
        unit->next_->prev_ = unit->prev_;
    
    // 헤드 교체
    if (cells_[oldCellX][oldCellY] == unit)
        cells_[oldCellX][oldCellY] = unit->next_;
        
    add(unit);
}

많은 유닛들을 매 프레임마다 연결 리스트에서 넣었다 뺄 수 있기 때문에 추가와 삭제가 빠른 이중 연결 리스트를 이용할 수밖에 없다.

여태까지는 같은 칸 안에 있는 유닛들만 검사했지만, 장거리 공격이 가능한 경우라면 같은 칸이 아니더라도 범위를 조금 더 넓게 검사하도록 바꾸면 된다.

위의 그림처럼 사거리 안에 들었음에도 다른 칸인 경우를 꼭 고려해야 한다.

void Grid::handleUnit(Unit* unit, Unit* other) {
    while (other != nullptr) {
        if (distance(unit, other) < ATTACK_DISTANCE)
            handleAttack(unit, other);
        other = other->next_;
    }
}

void Grid::handleCell(int x, int y) {
    Unit* unit = cells_[x][y];
    while (unit != nullptr) {
        handleUnit(unit, unit->next_);
        unit = unit->next_;
    }
}

handleCell 안에서 내부 루프를 따로 빼내어 HandleUnit으로 만든다.

handleCell은 더 이상 유닛 리스트가 아닌 칸의 좌표 값을 받도록 변경한다.

void Grid::handleCell(int x, int y) {
    Unit* unit = cells_[x][y];
    while (unit != nullptr) {
        handleUnit(unit, unit->next_);
        
        if (x > 0) handleUnit(unit, cells_[x-1][y]);
        if (y > 0) handleUnit(unit, cells_[x][y-1]);
        if (x > 0 && y > 0) handleUnit(unit, cells_[x-1][y-1]);
        if (x > 0 && y < NUM_CELLS-1) handleUnit(unit, cells_[x-1][y-1]);
        unit = unit->next_;
    }
}

handleCell을 확장시켜서 주변 8칸 중 좌측 4칸에 대해 충돌 여부를 검사한다.

절반만 검사하는 이유는 중복 처리 문제를 해결하기 위함이지만 일반적으로는 A, B의 관계가 비대칭이기 때문에 주변 칸을 모두 검사해야한다.

디자인 결정

◾ 공간을 계층적으로 나눌 것인가, 균등하게 나눌 것인가?

◾ 객체 개수에 따라 분할 횟수가 달라지는가?

유닛 개수와 위치에 따라 분할 크기를 조절한다. 예제처럼 크기를 모두 균일하게 분할했다가 모든 유닛이 한 칸에 몰려있다면 O(n²)으로 성능이 퇴보하기 때문이다.

◾ 객체를 공간 분할 자료구조에만 저장하는가?

공간 분할 자료구조와 관련된 내용으로는 격자, 쿼드트리, 이진 공간 분할, k-d트리, 경계 볼륨 계층구조를 찾아보면 된다.

덧붙여서,

격자의 1차원 버전은 버킷 정렬

BSP, k-d트리, BVH의 1차원 버전은 이진 탐색 트리

쿼드트리, 옥트리의 1차원 버전은 트라이다.

객체 풀 (Object Pool)

동기

파티클 시스템을 통해 파티클을 생성, 제거하는 과정에서 메모리 단편화가 생기면 안된다.

메모리 단편화가 빈번하게 발생하지 않더라도 메모리 단편화를 계속 방치하면 지속적으로 힙에 구멍을 내기 때문에 시간이 누적되면 결국 게임이 뻗어버린다.

패턴

재사용 가능한 객체들을 모아놓은 객체 풀 클래스를 정의한다. 여기에 들어가는 객체는 현재 자신이 사용 중이닞 ㅇ부를 알 수 있는 방법을 제공해야 한다. 풀은 초기화될 때 사용할 객체들을 미리 생성하고, 이들 객체를 사용 안함 상태로 초기화한다.

새로운 객체가 필요하면 풀에 요청한다. 풀은 사용 가능한 객체를 찾아서 사용 중으로 초기화한 뒤 반환한다. 객체를 더 이상 사용하지 않는다면 사용 안 함 상태로 되돌리고 이런 식으로 메모리나 다른 자원 할당을 신경 쓰지 않고 마음껏 객체를 생성, 삭제할 수 있다.

언제 쓸 것인가?

보통 오브젝트나 파티클같이 시각적으로 보이는 것에 많이 사용된다.

위와 같은 경우에 사용할 수 있다.

주의사항

보통 new, delete로 메모리를 관리한다. GC가 지원되는 언어는 GC로 관리한다.

객체 풀을 만들 때, 얼마나 사용될지 예측하여 크기를 조절해야 한다. 너무 작으면 크래시가 나고 너무 크면 메모리 낭비와 다를 바가 없다.

한 번에 사용 가능한 객체의 개수가 정해져 있기 때문에 장점일수도 있고 단점일수도 있다.

어찌 되었건 간에 객체 풀의 모든 객체가 사용 중이어서 재사용 할 객체를 반환받지 못해서 오버런이 발생할 때를 대비해 두어야 한다.

아예 풀이 부족하지 않도록 최악의 상황을 고려해서 풀을 크게 잡거나 객체 미생성, 기존 객체를 강제로 제거, 풀의 크기를 늘리는 등 해결 방법은 여러 가지가 있으며 각자 장단점이 존재한다.

대부분의 객체 풀은 배열로 구현한다.

풀에 들어가는 객체가 전부 같은 타입이면 상관없지만 크기가 다양한 서로 다른 타입이면 메모리를 낭비하게 된다.

이런 경우는 객체의 크기별로 풀을 나누는 게 좋다.

재사용되는 객체는 저절로 초기화되지 않기 때문에 재사용시에는 주의해서 반드시 객체를 완전히 초기화해야 한다.

예제

class Particle {
public:
    Particle() : frameLeft_(0) {}
    void init(double x, double y, double xVel, double yVel, int lifetime);
    void animate();
    bool inUse() const { return frameLeft_ > 0; }
    
private:
    int frameLeft_;
    double x_, y_;
    double xVel_, yVel_;
};

void Particle::init(double x, double y, double xVel, double yVel, int lifetime) {
    x_ = x;
    y_ = y;
    xVel_ = xVel;
    yVel_ = yVel;
    frameLeft_ = lifetime;
}

파티클은 최초 생성 시 사용 안 함 상태로 초기화되고 나중에 init이 호출되면 파티클이 사용 중 상태로 바뀐다.

void Particle::animate() { // 업데이트 메서드 패턴 사용
    if (!inUse()) return;
    
    frameLeft_--;
    x_ += xVel_;
    y_ += yVel_;
}

매 프레임마다 animate를 호출하며 재사용 가능한 파티클을 확인하여 사용한다.

class ParticlePool {
public:
    void create(double x, double y, double xVel, double yVel, int lifetime);
    void animate();
    
private:
    static const int POOL_SIZE = 100;
    Particle particles_[POOL_SIZE];
};

void ParticlePool::animate() {
    for (int i = 0; i < POOL_SIZE; ++i)
        particles_[i].animate();
}

void ParticlePool::create(double x, double y, double xVel, double yVel, int lifetime) {
    for (int i = 0; i < POOL_SIZE; ++i) {
        if (!particles_[i].inUse()) {
            particles_[i].init(x, y, xVel, yVel, lifetime);
            return;
        }
    }
}

객체 풀 클래스는 꽤 단순하다.

매 프레임마다 animate를 호출해서 풀에 들어 있는 파티클을 순차적으로 애니메이션한다.

새로운 파티클을 생성하는 것도 어렵지 않다. 사용 중이지 않은 파티클을 찾아서 초기화하여 재사용 준비만 시켜주면 된다.

파티클들은 생명 주기가 끝나면 스스로 비활성화된다.

다 좋아보이지만 사용 가능한 객체를 찾기 위해 매 프레임마다 전체 컬렉션을 순회하는 문제가 있다.

◾ 빈칸 리스트

사용 가능한 파티클을 찾느라 전체 컬렉션을 순회하며 낭비하고 싶지 않으면 사용 가능한 파티클을 계속 추적해야 한다. 사용 가능한 파티클 포인터를 별도의 리스트에 저장하는 것도 한 방법이지만 풀에 들어 있는 객체 개수만큼의 포인터가 들어 있는 리스트를 따로 관리해야 한다.

리스트를 따로 관리하는 대신 사용하지 않는 파티클 객체의 데이터 일부를 활용할 수 있다.

class Particle {
public:
    Particle* getNext() const { return state_.next; }
    void setNext(Particle* next) {
        state_.next = next;
    }
    
private:
    int frameLeft_;
    
    union {
        struct {
            double x, y;
            double xVel, yVel;
        } live;
        
        Particle* next;
    } state_;
};

별도로 관리되어야 하는 생명주기를 제외한 모든 멤버 변수를 공용체 내부의 구조체 안으로 옮긴다.

파티클이 활성화 된 동안에는 구조체의 데이터를 사용하고 비활성화 되었을 때는 구조체의 데이터가 필요 없기 때문에 포인터로 사용 가능한 다음 파티클을 가리키면 추가 메모리 낭비 없이 리스트를 만들 수 있다.

이를 빈칸 리스트 기법이라고 부른다.

빈칸 리스트 기법을 적용하기 위해 코드를 일부 수정해야 한다.

class ParticlePool {
    // ...
private:
    Particle* firstAvailable_; // head
};

ParticlePool::ParticlePool() {
    firstAvailable_ = &particles_[0];
    
    for (int i = 0; i < POOL_SIZE - 1; ++i)
        particles_[i].setNext(&particles_[i+1]);
    
    particles_[POOL_SIZE-1].setNext(nullptr);
}

풀을 최초 생성시에는 모든 파티클이 사용 가능하기 때문에 배열 전체를 관통하여 리스트를 만든다.

void ParticlePool::create(double x, double y, double xVel, double yVel, int lifetime) {
    assert(firstAvailable_ != nullptr);
    
    Particle* newParticle = firstAvailable_;
    firstAvailable_ = newParticle->getNext();
    newParticle->init(x, y, xVel, yVel, lifetime);
}

새로운 파티클 생성시에는 첫 번째로 사용 가능한 파티클의 포인터를 바로 얻어오면 된다.

bool Particle::animate() {
    if (!inUse()) return false;
    
    frameLeft_--;
    x_ += xVel_;
    y_ += yVel_;
    
    return frameLeft_ == 0;
}

파티클의 생명주기를 알 수 있도록 반환 값을 bool로 바꾼다.

void ParticlePool::animate() {
    for (int i = 0; i < POOL_SIZE; ++i) {
        if (particles_[i].animate()) {
            particles_[i].setNext(firstAvailable_);
            firstAvailable_ = &particles_[i];
        }
    }
}

추가 메모리 낭비 없이 상수 시간에 생성, 삭제가 가능한 아름다운 객체 풀이 완성됐다.

디자인 결정

풀과 객체의 커플링 여부와 재사용 될 객체를 초기화 할때 주의할 점이 있다.

객체가 풀과 커플링된다면 더 간단하게 구현할 수 있고 객체가 풀을 통해서만 생성될 수 있도록 강제할 수 있다.

커플링되지 않는다면 어떤 객체라도 풀에 넣을 수 있지만 사용 여부를 객체의 외부에서 관리해야 한다.

재사용될 객체를 풀 안에서 초기화한다면 풀은 객체를 완전히 캡슐화 시킬 수 있고 풀 클래스는 객체가 초기화 되는 방법과 결합된다.

객체를 풀 밖에서 초기화한다면 풀의 인터페이스는 단순해진다. 하지만 객체 생성이 실패할 때의 예외 처리를 구현해 두어야 할 수 있다.

객체 풀 패턴은 경량 패턴과 비슷한 점이 많다. 둘 다 재사용 가능한 객체 집합을 관리하지만 재사용의 의미에 차이가 있다.