glm::vec3 coral(1.0f, 0.5f, 0.31f);

우리가 보는 사물의 색은 실제 그 사물이 가진 색이 아니다. 사물로부터 반사된 색이다. 사물로부터 흡수된(absorbed)게 아니라 우리가 인지하고 있는 것. 한 예시로 태양의 빛은 다양한 색으로 결합된 하얀 빛으로 인지된다. 이 하얀 빛을 파란 물체에 비추면 파란색을 제외한 모든 하얀색을 구성하는 부수적인 색들을 흡수한다. 이 물체는 파란색을 흡수하지 못하기때문에 반사시킨다. 이 반사된 빛이 눈에 들어오고, 물체가 파란색을 가진 것처럼 보이게 한다. 위 이미지는 산호색의 물체에 관한 것.

하얀 태양빛은 모든 색의 집합체이고 물체는 그 색상들의 큰 부분을 흡수. 물체의 색을 나타내는 색상들을 비추며 그 색상들의 조합이 우리가 인지하는 것.

OpenGL에서 광원을 정의할 때 이 빛을 하나의 색으로 준다. 이 빛의 색상값과 사물의 색상값을 곱하면 결과 색상값은 사물의 반사된 색상이다.

glm::vec3 lightColor(1.0f, 1.0f, 1.0f);
glm::vec3 toyColor(1.0f, 0.5f, 0.31f);
glm::vec3 result = lightColor * toyColor; // = (1.0f, 0.5f, 0.31f);

물체의 색이 하얀 빛의 큰 부분을 흡수하지만 물체가 가진 색을 토대로 몇가지 빨강, 초록, 파랑 값들을 반사한다. 이는 실제로 색상이 어떻게 작용하는지 표현. 물체가 빛으로부터 반사되는 각각의 색상의 원소의 양으로 물체의 색을 정의. 만약 초록빛을 사용하면?

glm::vec3 lightColor(0.0f, 1.0f, 0.0f);
glm::vec3 toyColor(1.0f, 0.5f, 0.31f);
glm::vec3 result = lightColor * toyColor; // = (0.0f, 0.5f, 0.0f);

물체는 흡수하거나 또는/그리고 반사할 수 있는 빨강과 파랑빛을 가지지 않는다. 이 물체는 또한 초록빛 값의 반을 흡수할뿐만아니라 반사한다. 이 물체의 색은 어두운 초록색이라 인지될 것. 초록빛을 사용하면 초록색의 원소만 반사되어 인식될 수 있다.

glm::vec3 lightColor(0.33f, 0.42f, 0.18f);
glm::vec3 toyColor(1.0f, 0.5f, 0.31f);
glm::vec3 result = lightColor * toyColor; // = (0.33f, 0.21f, 0.06f);

위 예시는 dark olive-green 빛이다.

A lighting scene

먼저 빛을 발하는 물체가 필요하고 이전 챕터의 큐브를 생성해 사용할 것. 빛 자원이 3D 배경에서 어디에 위치하는지 나타낼 빛 오브젝트 필요. 간단하게 표현하기 위해서 큐브를 사용하여 광원을 나타낸다.

vertex buffer objects 채우고 vertex attribute pointer들을 세팅한다.

첫번째로 큐브 컨테이너를 그릴 vertex shader가 필요. 컨테이너의 vertex position은 똑같으므로 코드는 그대로다.

#version 330 core
layout (location = 0) in vec3 aPos;

uniform mat4 model;
uniform mat4 view;
uniform mat4 projection;

void main()
{
    gl_Position = projection * view * model * vec4(aPos, 1.0);
}

vertex 데이터와 vertex attribute pointer 업데이트

unsigned int lightVAO;
glGenVertexArrays(1, &lightVAO);
glBindVertexArray(lightVAO);
// we only need to bind to the VBO, the container’s VBO’s data
// already contains the data.
glBindBuffer(GL_ARRAY_BUFFER, VBO);
// set the vertex attribute
glVertexAttribPointer(0, 3, GL_FLOAT, GL_FALSE, 3 * sizeof(float), (void*)0);
glEnableVertexAttribArray(0);

#version 330 core
out vec4 FragColor;
uniform vec3 objectColor;
uniform vec3 lightColor;
void main()
{
    FragColor = vec4(lightColor * objectColor, 1.0);
}

Fragment shader는 컨테이너의 색과 광원의 색을 union변수로 받을 수 있다. 여기서 물체에 반사된 색과 광원의 색을 곱한다. 광원의 색과 물체의 색을 설정

lightingShader.use();
lightingShader.setVec3("objectColor", 1.0f, 0.5f, 0.31f);
lightingShader.setVec3("lightColor", 1.0f, 1.0f, 1.0f);

다음 챕터에서 lighting shaders를 업데이트 시작할 때 광원인 물체도 영향을 받을 것인데 이는 원치 않는 결과이다. 광원의 물체의 색이 빛을 계산하는 것으로부터 영향을 받지 않게 다른 것과 다르게 그대로 유지. 광원이 다른 색에 의해 영향을 받지 않고 상수 밝기의 색을 가지게 하게 한다.

위를 수행하기 위해서 다른 shader를 추가한다. 이는 광원을 그리고 lighting shader의 변화에 안전함을 위함이다.

광원의 fragment shader는 아래와 같이 생성

#version 330 core

out vec4 FragColor;

void main()
{
    FragColor = vec4(1.0); // set all 4 vector values to 1.0
}

light 쉐이더가 점더 실제적인 결과를 얻게 업데이트할 동안 광원은 광원 쉐이더의 정의에 따라 렌더링되고 그려지게 한다.

광원의 주 목적은 어디서 빛이 오는지 보여주는 것. 보통 광원의 위치를 scene의 어느 지점에 두는데 시각적 의미를 두지 않는다. scene의 빛의 상태에 상관없이 항상 하얀색으로 유지되게 광원 쉐이더에 정의된 컨테이너형태로 나타낸다.

world 공간 좌표에서의 광원의 위치를 전연벽수 vec3로 나타낸다.

glm::vec3 lightPos(1.2f, 1.0f, 2.0f);

광원을 나타내는 물체를 광원의 지점으로 이동시키고 크기 조정을 하기 위해서 아래와 같이 코드 작성

model = glm::mat4(1.0f);
model = glm::translate(model, lightPos);
model = glm::scale(model, glm::vec3(0.2f));

렌더링 하는 코드에서 광원의 물체에 관한 코드는 아래와 같이 작성할 수 있다.

lightCubeShader.use();
// set the model, view and projection matrix uniforms
[...]
// draw the light cube object
glBindVertexArray(lightCubeVAO);
glDrawArrays(GL_TRIANGLES, 0, 36);

e.g. 데이터베이스(B-트리), 데이터 인코딩/압축(허프만 트리), 그래프 컬러링, 할당 문제, 최소 거리 문제 등

계층적 문제

• 회사 조직도
• 교과 과정 계층도

순환 종속성

• 관계도(SNS 친구 관계)
• 도로망

Tree

모든 노드는 자식 노드가 없거나 하나 이상의 자식 노드를 가질 수 있다.

루트 노드를 제외한 모든 노드는 하나의 부모 노드를 가진다.

어떤 노드의 degree는 그 노드가 가진 자식 노드의 수를 말한다.

같은 노드를 부모 노드를 가지는 노드들은 sibling이라 표현

degree에 따라서 leaf 노드인지 internal 노드인지 구별한다.

경로(Path)

edge의 개수는 경로의 길이

Depth

노드의 depth는 루트로부터의 해당 노드까지의 길이를 말한다. → 루트에서 그 노드까지의 경로의 길이 → edge의 개수

Height

가장 큰 depth → 트리의 Height

e.g. 루트 노드 하나라면 0, empty tree는 -1

Ancestor and Descendant

자기 자신은 조상이면서 자손

루트 노드는 모든 노드의 조상 ancestor

트리 순회

• 전위 순회(preorder traversal)

  • Current Node→Left→Right

    preorder(전위 순회)(노드 주소)
      if 인자로 전달된 노드 주소가 없다면
          종료
      노드의 값 출력 또는 전달
      preorder(노드의 왼쪽에 연결견된 주소)
      preorder(노드의 오른쪽에 연결된 주소)

• 중위 순회(inorder traversal)

  • Left→Current Node→Right

    inorder(중위 순회)(노드 주소)
      if 인자로 전달된 노드 주소가 없다면
          종료
      inorder(노드의 왼쪽에 연결견된 주소)
      노드의 값 출력 또는 전달
      inorder(노드의 오른쪽에 연결된 주소)

• 후위 순회(postorder traversal)

  • Left→Right→Current Node

    postorder(중위 순회)(노드 주소)
      if 인자로 전달된 노드 주소가 없다면
          종료
      postorder(노드의 왼쪽에 연결견된 주소)
      postorder(노드의 오른쪽에 연결된 주소)
      노드의 값 출력 또는 전달

• 레벨 순서 순회(level order traversal)

  • 트리의 맨 위 레벨부터 아래 레벨까지, 왼쪽 노드에서 오른쪽 노드 순서로 방문. 트리의 루트 노드부터 단계별로 차례대로 나열하는 것과 같다.

    레벨 순서 순회(level order traversal)(노드 주소)
      if 노드 주소가 없다면
          종료
      큐 생성 후 노드 주소 할당
      while 큐가 비어있지 않으면
          for 큐의 크기만큼
              큐에서 노드를 꺼내고 current에 저장
              current 노드의 값을 출력 또는 반환
              if current 노드의 left에 노드 존재 확인
                  있으면 큐에 저장
              if current 노드의 right에 노드 존재 확인
                  있으면 큐에 저장
    

다양한 트리 구조

• 이진 검색 트리 BST, binary search tree

  • 특징

    • 부모 노드의 값 ≥ 왼쪽 자식 노드의 값
    • 부모 노드의 값 ≤ 오른쪽 자식 노드의 값
    • BST가 마지막 레벨을 제외한 모든 노드에 두 개의 자식 노드가 있을 경우, 이 트리의 높이는 $\log_2N$이 되고 $N$은 원소의 개수이다. 이로서 BST 검색 및 삽입 동작은 $O(\log N)$의 시간 복잡도를 갖는다. (complete binary tree)

  • 이진 트리 다양한 형태들

    • Full Binary Tree

      • 모든 노드가 자식이 없거나 2개의 자식을 가지고 있다.

        the number of internal nodes - $i$

        the total number of nodes - $n$

        number of leaves - $l$

        number of levels - $L$

        • 레벨 L의 트리의 높이(height)는 $L - 1$
        • leaf 노드 수는 $i + 1$
        • 전체 노드 수는 $2i + 1$
        • internal 노드 수는 $(n + 1) / 2$
        • 총 노드 수 $2l - 1$
        • 총 internal 노드 수는 $l - 1$
        • leaf 노드의 가장 많을 때는 $2^L - 1$

    • Complete Binary Tree

      • 모든 leaf 노드들은 같은 level에 있으면서(같은 depth를 가지면서) 왼쪽면에서 채워지는 트리. 마지막 레벨을 제외한 레벨은 full
        • $d$ depth에서 complete binary tree의 노드 수는 $2^d$
        • $n$개의 노드를 가진 complete binary tree의 높이는 $\log(n+1)$

    • Perfect Binary Tree

      • internal 노드들 모두 두 자식 노드들을 가지고 있으며 모든 leaf 노드들은 같은 level에 있다.
        • $h$ 높이의 perfect binary tree는 $2^{h+1} - 1$개의 노드들을 갖는다.

구현

원소 검색

노드 주소 find(찾는 값, 노드 주소)
    if 노드 주소가 없다면
        종료 또는 현재 노드 반환(insert 함수 때 재사용시)
    if 노드 주소의 값 == 찾는 값
        노드 주소 반환
    if 노드 주소의 값 > 찾는 값
        find(찾는 값, 노드 오른쪽 주소) 함수 반환
    find(찾는 값, 노드 왼쪽 주소) 함수 반환

원소 삽입

insert(값)
    if root가 없으면
        root에 값 저장
    else
        _insert(root, 값)

_insert(노드, 값)
    if 값 < 노드의 값
        if 노드의 왼쪽이 없으면
            노드의 왼쪽에 노드 생성 후 값 저장
        else
            _insert(노드의 왼쪽 주소, 값)
    else
        if 노드의 오른쪽이 없으면
            노드의 오른쪽에 노드 생성 후 값 저장
        else
            _insert(노드의 오른쪽 주소, 값)
---------------------------------
insert(값)
    find(값, 루트) 반환된 주소 값에 노드 생성 후 값 저장

원소 삭제 - 여러 방식이 있다.

/* 자식 노드가 없는 경우
 * -> 단순 삭제
 * 자식 노드가 하나만 있는 경우
 * -> 노드 삭제 후 부모 노드의 포인터가 해당 자식 노드를 가리키게 한다.
 * 자식 노드가 두 개 있는 경우
 * -> 노드 삭제 후, 현재 노드를 후속 노드로 대체
 * -> successor를 구할지 predecessor를 구하는 건 마음이 가는대로.
 */

/* 전임자냐 후임자냐 == 삭제하는 노드의 값 바로 전의 값이나 후의 값으로 교체할지 결정 */
노드 successor(노드) // Left-most child of the right subtree of the target node
    current 노드 변수에 노드의 오른쪽 주소를 저장
    while(current가 없으면서 current의 왼쪽이 없으면)
        current에 current의 왼쪽 주소 저장
    current 반환 // successor 노드 반환

노드 predecessor(노드) // Right-most child of the left subtree of the target node
    current 노드 변수에 노드의 왼쪽 주소를 저장
    while(current가 없으면서 current의 오른쪽이 없으면)
        current에 current의 오른쪽 주소 저장
    current 반환 // predecessor 노드 반환
----------------------------------------------

노드 delete(노드, 찾는 값)
    if 찾는 값 < 노드의 값
        노드의 왼쪽 = delete(노드의 왼쪽, 찾는 값)
    else if 찾는 값 > 노드의 값
        노드의 오른쪽 = delete(노드의 오르쪽, 찾는 값)
    /* 위의 코드는 원소 검색 함수로 재사용 가능하다 */
    /* if find(노드)의 반환 값이 NULL이라면 NULL 반환 */
    else
        if 노드의 left가 없다면 // 자식 노드가 전혀 없거나, 왼쪽 자식 노드만 없는 경우
            노드의 오른쪽 주소를 변수에 저장
            노드 삭제
            저장한 주소 값 반환
        if 노드의 right가 없다면 // 오른쪽 자식 노드만 없는 경우
            노드의 왼쪽 주소를 변수에 저장
            노드 삭제
            저장한 주소 값 반환
        // 자식 노드가 둘 다 있는 경우
        노드의 후속노드를 가져와서 노드의 데이터에 후속노드의 데이터를 저장
        // 오른쪽 서브 트리에서 후속노드 찾아 삭제
        노드의 오른쪽에 delete(노드의 오른쪽, 후속노드의 데이터) 함수 반환 값 저장
    노드 반환
----------------------------------------------

트리 연산 시간 복잡도

• BST 검색에 필요한 시간 T(N) = T(N/2) + 1 = O(\log N)
  • Complete binary tree가 아닌 한 이 시간 복잡도는 항상 성립하지 않는다.
  • 균형 이진 트리가 이 문제를 해결

균형 balanced trees

문제는 BST가 어떻게 데이터가 삽입됐냐에 따라서 효율성이 나뉜다.

→ 최악의 경우 연결 리스트, 최상의 경우 complete binary tree

기준 노드의 양쪽 서브트리의 높이(h)의 차가 -1, 0, 1인 경우 balanced 균형잡힌 상태라 한다.

• 용어

  • mountain - 양쪽 노를 가지고 있는 형태
  • stick - 한방향 + 하나의 자식 노드만으로 이루어진 형태
  • rotation - 회전
  • balance factor - 두 서브트리 높이의 차. 여기서는 ‘BF = RSH - LSH’로 계산.
  • elbow - 하나의 자식 노드들로 이루어졌으며 오른쪽 자식 노드에서 왼쪽 자식노드를 가진 형태(팔 구부린 형상)

• 목표

  • balance factor가 큰 stick이나 elbow 형태인 트리를 rotation하여 mountain 형태로 변형

• Rotations

  • balance factor를 구하고 거기에 맞춰서 회전을 하여 균형있는 형태로 변형

  • Left Rotation

    • BF = RSH(2) - LSH(0) = 2 & BF = RSH(1) - LSH(0) = 1

  • Right Rotation

    • BF = RSH(0) - LSH(2) = -2 & BF = RSH(0) - LSH(1) = -1

  • Left-Right Rotation

    • BF = RSH(0) - LSH(2) = -2 & BF = RSH(1) - LSH(0) = 1
    • elbow → stick → mountain

  • Right-Left Rotation

    • BF = RSH(2) - LSH(0) = 2 & BF = RSH(0) - LSH(1) = -1
    • elbow → stick → mountain

• Rotation summary - BF = RSH - LSH로 한 표. LSH - RSH로 했을 때는 부호를 바꾸면 된다.

|  | Balance factor of the lowest point of imbalance | Balance factor of the node in the direction of imbalance |
| --- | --- | --- |
| Left Rotation | 2 | 1 |
| Right Rotation | -2 | -1 |
| L-R Rotat | -2 | 1 |
| R-L Rotation | 2 | -1 |

위의 균형 트리를 AVL 트리라 한다.

• 이진 트리와 같다. 다만, 삽입과 삭제에서 더 많은 작업을 해야한다.
  • 어떤 작업?
    • balance factor를 빠르게 계산하기 위해 각 노드의 높이를 저장
    • 삽입 및 삭제시 회전하고 새로 높이를 업데이트한다.
• 연산
  • 탐색 - BST와 같다.
  • 삽입 - BST와 같이 삽입하고 Balance Factor를 체크한 후 -1, 0 또는 1이 아닌 경우 Rotation 한다.
  • 삭제 - BST와 같이 선임자 노드를 찾고 swap한 후 삭제하고 Balance Factor를 체크한 후 -1, 0 또는 1일 경우 Rotation한다.

코드 설명 : 기본 bst로 만든 dictionary 코드와 비교

BST

/* ADT */
template<typename K, typename D>
class Dictionary
{
public:
    Dictionary();
    const D& find(const K& key);
    void insert(const K& key, const D& data);
    const D& remove(const K& key);
    const D& max() const;
    const D& min() const;
    void print();

private:
    class TreeNode
    {
    public:
        const K& key;
        const D& data;
        TreeNode* left;
        TreeNode* right;
        TreeNode(const K& key, const D& data);
    };

    TreeNode* root_;

    // all in private to hide the information
    const D& _max(TreeNode* cur) const;
    const D& _min(TreeNode* cur) const;

    TreeNode*& _find(const K& key, TreeNode*& cur) const;
    const D& _remove(TreeNode*& node);
    TreeNode*& _predecessor(TreeNode*& cur) const;
    TreeNode*& _successor(TreeNode*& cur) const;
    TreeNode*& _rightmost(TreeNode*& cur) const;
    TreeNode*& _leftmost(TreeNode*& cur) const;
    TreeNode*& _swap(TreeNode*& node1, TreeNode*& node2);
};

/* key값으로 node 찾기 */
template <typename K, typename D>
const D& Dictionary<K, D>::find(const K& key)
{
    TreeNode*& node = _find(key, root_);
    if (node == nullptr) throw std::runtime_error("Error: key not found in _find()");
    return node->data;
}

template<typename K, typename D>
typename Dictionary<K, D>::TreeNode*& Dictionary<K, D>::_find(const K& key, TreeNode*& cur) const
{
    if (cur == nullptr || key == cur->key)
        return cur;
    else if (key < cur->key)
        return _find(key, cur->left);
    else
        return _find(key, cur->right);
}

/* find() 함수로 노드를 찾고 삽입하기 */
template <typename K, typename D>
void Dictionary<K, D>::insert(const K& key, const D& data)
{
    TreeNode*& node = _find(key, root_);
    node = new TreeNode(key, data);
}

/* key값으로 노드 삭제 */
template <typename K, typename D>
const D& Dictionary<K, D>::remove(const K& key)
{
    TreeNode*& node = _find(key, root_);
    return _remove(node);
}

template<typename K, typename D>
const D& Dictionary<K, D>::_remove(TreeNode*& node)
{
    std::cout << std::endl;
    if (!node) {
        throw std::runtime_error("Error: _remove() used on non-existent key");
    }
    if (node->left == nullptr ) {
        const D& data = node->data;
        TreeNode* tmp = node;
        node = node->right;
        delete tmp;
        return data;
    }
    if (node->right == nullptr) {
        const D& data = node->data;
        TreeNode* tmp = node;
        node = node->left;
        delete tmp;
        return data;
    }
    TreeNode*& predecessor = _predecessor(node);
    // TreeNode*& successor = _successor(node);
    if (!predecessor)
        throw std::runtime_error("Error: predecessor not found");
    TreeNode *&moved_node = _swap(node, predecessor);
    return _remove(moved_node);
}

template <typename K, typename D>
typename Dictionary<K, D>::TreeNode*& Dictionary<K, D>::_predecessor(TreeNode*& cur) const
{
    if (!cur)
        return cur;
    if (!(cur->left))
        return cur->left;
    return _rightmost(cur->left);
}

template <typename K, typename D>
typename Dictionary<K, D>::TreeNode*& Dictionary<K, D>::_successor(TreeNode*& cur) const
{
    if (!cur)
        return cur;
    if (!(cur->right))
        return cur->right;
    return _leftmost(cur->right);
}

template <typename K, typename D>
typename Dictionary<K, D>::TreeNode*& Dictionary<K, D>::_rightmost(TreeNode*& cur) const
{
    if (!cur || !(cur->right))
        return cur;
    return _rightmost(cur->right);
}

template <typename K, typename D>
typename Dictionary<K, D>::TreeNode*& Dictionary<K, D>::_leftmost(TreeNode*& cur) const
{
    if (!cur || !(cur->left))
        return cur;
    return _leftmost(cur->left);
}

template <typename K, typename D>
typename Dictionary<K, D>::TreeNode*& Dictionary<K, D>::_swap(TreeNode*& node1, TreeNode*& node2)
{
    // for _predecessor()
    if (node1->left == node2) {
        TreeNode *tmp = node2;
        std::swap(node1->right, node2->right);
        node1->left = tmp->left;
        tmp->left = node1;
        node1 = tmp;
        return node1->left;
    }
    // for _successor()
    if (node1->right == node2)
    {
        TreeNode *tmp = node2;
        std::swap(node1->left, node2->left);
        node1->right = tmp->right;
        tmp->right = node1;
        node1 = tmp;
        return node1->right;
    }
    std::swap(node1->left, node2->left);
    std::swap(node1->right, node2->right);
    std::swap(node1, node2);
    return node2;
}

/* 나머지 함수들의 body */
/** constructor of Dictionary class */
template <typename K, typename D>
Dictionary<K, D>::Dictionary()
    : root_(nullptr)
{}

/** constructor of TreeNode class in  Dictionary class */
template <typename K, typename D>
Dictionary<K, D>::TreeNode::TreeNode(const K& key, const D& data)
    : key(key), data(data), left(nullptr), right(nullptr)
{}

/** the right-most data of the tree */
template <typename K, typename D>
const D& Dictionary<K, D>::max() const { return _max(root_); }

/** the left-most data of the tree */
template <typename K, typename D>
const D& Dictionary<K, D>::min() const { return _min(root_); }

template <typename K, typename D>
const D& Dictionary<K, D>::_max(TreeNode* cur) const
{
    while (cur && cur->right)
        cur = cur->right;
    return cur->data;
}

template <typename K, typename D>
const D& Dictionary<K, D>::_min(TreeNode* cur) const
{
    while (cur && cur->left)
        cur = cur->left;
    return cur->data;
}

AVL 트리 - ADT, 삽입, 삭제

template<typename K, typename D> // key & data
class AVL
{
public:
    AVL() : head_(nullptr) {}

    const D& find(const K& key);
    bool contains(const K& key);
    void insert(const K& key, const D& data);
    const D& remove(const K& key);
    bool empty() const;
    void clear();

private:
    class Node
    {
    public:
        const K &key;
        const D &data;
        Node *left;
        Node *right;
        int height;
        Node(const K &key, const D &data) : key(key), data(data), left(nullptr), right(nullptr), height(0) {}
    };

    Node* head_;

    Node*& _find(const K& key, Node*& cur) const;
    void _find_and_insert(const K& key, const D& data, Node*& cur);
    const D& _find_and_remove(const K& key, Node*& cur);
    const D& _remove(Node*& node);

    // 삭제를 위해 삭제할 노드와 스왑할 in-order의 전임자를 찾기 위한 함수들
    const D& _iopRemove(Node*& targetNode);
    const D& _iopRemove(Node*& targetNode, Node*& iopAncester, bool isInitialCall);
    Node*& _swap_nodes(Node*& node1, Node*& node2);

    void _updateHeight(Node*& cur);
    void _ensureBalance(Node*& cur);

    void _rotateLeft(Node*& cur);
    void _rotateRight(Node*& cur);
    void _rotateLeftRight(Node*& cur);
    void _rotateRightLeft(Node*& cur);

    int _get_height(Node*& node) const;
    int _get_balance_factor(Node*& node) const;
};

삽입

// BST와 같지만 Balance Factor를 계산해야한다.
template <typename K, typename D>
void AVL<K, D>::_find_and_insert(const K& key, const D& data, Node*& cur)
{
    if (!cur) {
        cur = new Node(key, data);
        return;
    }
    else if (cur->key == key) {
        throw std::runtime_error("ERROR::INSERT::key already exists");
    }
    else if (cur->key > key) {
        _find_and_insert(key, data, cur->left);
        _ensureBalance(cur);
        return ;
    }
    else {
        _find_and_insert(key, data, cur->right);
        _ensureBalance(cur);
    }
}

template <typename K, typename D>
void AVL<K, D>::_ensureBalance(Node*& cur)
{
    if (!cur) return;

    // cur 노드의 balance factor 계산
    int initial_balance = _get_balance_factor(cur);

    // balance를 확인하고 불균형인 곳이 있으면 그곳의 방향을 찾아 회전시킨다.
    if (initial_balance == -2)
    {
        const int left_balance = _get_balance_factor(cur->left);
        if ((left_balance == -1) || (left_balance == 0))
            _rotateRight(cur);
        else if (left_balance == 1)
            _rotateLeftRight(cur);
        else
            // error check;
    }
    else if (initial_balance == 2)
    {
        const int right_balance = _get_balance_factor(cur->right);
        if ((right_balance == 1) || (right_balance == 0))
            _rotateLeft(cur);
        else if (right_balance == -1)
            _rotateRightLeft(cur);
        else
            // error check;
    }
        // 높이를 업데이트
    _updateHeight(cur);

    // 마지막 error check
    const int final_balance = _get_balance_factor(cur);
    if (final_balance < -1 || final_balance > 1)
    {
        //error check
    }
}

template <typename K, typename D>
void AVL<K, D>::_updateHeight(TreeNode*& cur) 
{
  if (!cur) return;
  cur->height = 1 + std::max(_get_height(cur->left), _get_height(cur->right));
}

int _get_height(TreeNode*& node) const 
{
      if (!node) 
        return -1;
      else
        return node->height;
}

삭제

template <typename K, typename D>
const D &AVL<K, D>::_find_and_remove(const K& key, Node*& cur)
{
    if (!cur) throw std::runtime_error("ERROR::FIND_AND_REMOVE::key not found");
    else if (cur->key == key) return _remove(cur);
    else if (cur->key < key)
    {
        const D& data = _find_and_remove(key, cur->right);
        _ensureBalance(cur);
        return data;
    }
    else
    {
        const D& data = _find_and_remove(key, cur->left);
        _ensureBalance(cur);
        return data;
    }
}

template <typename K, typename D>
const D& AVL<K, D>::_remove(Node*& node)
{
    if (!node) throw std::runtime_error("ERROR::REMOVE::the function used on nullptr");

    if (!node->left && !node->right) // 자식이 없을때
    {
        const D& data = node->data;
        delete node;
        node = nullptr;
        return data;
    }
    else if (node->left && !node->right) // 왼쪽만
    {
        const D& data = node->data;
        Node* temp = node;
        node = node->left;
        delete temp;
        temp = nullptr;
        return data;
    }
    else if (!node->left && node->right) // 오른쪽만
    {
        const D& data = node->data;
        Node* temp = node;
        node = node->right;
        delete temp;
        temp = nullptr;
        return data;
    }
    else // 둘다
    {
        return _iopRemove(node);
    }
}

// 선임자 찾는 함수들
template <typename K, typename D>
const D& AVL<K, D>::_iopRemove(Node*& targetNode)
{
    if (!targetNode) throw std::runtime_error("ERROR::IOP_REMOVE:: this function called on nullptr");

    const D& data = _iopRemove(targetNode, targetNode->left, true);

    if (targetNode->left)
        _ensureBalance(targetNode->left);
    _ensureBalance(targetNode);
    return data;
}

template <typename K, typename D>
const D& AVL<K, D>::_iopRemove(Node*& targetNode, Node*& iopAncester, bool isInitialCall)
{
    if (!targetNode) throw std::runtime_error("ERROR::IOP_REMOVE:: targetNode is nullptr");
    if (!iopAncester) throw std::runtime_error("ERROR::IOP_REMOVE:: iopAncester is nullptr");

    if (!iopAncester->right)
    {
        const D &data = _iopRemove(targetNode, iopAncester->right, false);
        if (!isInitialCall)
            if (iopAncester)
                _ensureBalance(iopAncester);
        return data;
    }
    else
    {
        Node*& movedTarget = _swap_nodes(targetNode, iopAncester);
        const D& data = _remove(movedTarget);
        return data;
    }
}

// 선임자를 찾고 그 노드와 삭제할 노드 스왑
template <typename K, typename D>
typename AVL<K, D>::Node*& AVL<K, D>::_swap_nodes(Node*& node1, Node*& node2)
{
    Node* orig_node1 = node1;
    Node* orig_node2 = node2;
    std::swap(node1->height, node2->height);
    if (node1->left == node2)
    {
        std::swap(node1->right, node2->right);
        node1->left = orig_node2->left;
        orig_node2->left = node1;
        node1 = orig_node2;
        return node1->left;
    }
    else if (node1->right == node2)
    {
        std::swap(node1->left, node2->left);
        node1->right = orig_node2->right;
        orig_node2->right = node1;
        node1 = orig_node2;
        return node1->right;
    }
    else if (node2->left == node1)
    {
        std::swap(node2->right, node1->right);
        node2->left = orig_node1->left;
        orig_node1->left = node2;
        node2 = orig_node1;
        return node2->left;
    }
    else if (node2->right == node1)
    {
        std::swap(node2->left, node1->left);
        node2->right = orig_node1->right;
        orig_node1->right = node2;
        node2 = orig_node1;
        return node2->right;
    }
    else
    {
        std::swap(node1->left, node2->left);
        std::swap(node1->right, node2->right);
        std::swap(node1, node2);
        return node2;
    }
}

https://www.cs.usfca.edu/~galles/visualization/AVLtree.html

구현 후 비교하면서 에러 체크.

Left-Leaning Red-Black Tree

모든 레드 블랙 트리는 2-3 또는 2-3-4 트리 구현에 기초한다.

• 재귀적 구현
• 모든 3-노드들은 왼쪽으로 기울게 한다.
• 트리로 올라가면서 Rotation을 수행.

2-3 tree는 3차인 B-tree.

성질

• 두 개의 자식노드를 가지고 있으면 2-node라 한다. 2-node는 하나의 데이터 값과 두 자식 노드를 갖는다.
• 세 개의 자식노드를 가지고 있으면 3-node라 한다. 3-node는 두 데이터 값들과 세 자식 노드를 갖는다.
• 데이터 값은 정렬되어 저장.
• 균형 트리
• 모든 자식 노드는 같은 레벨이다.

Red Black Tree(Left Leaning Red Black Tree)

성질

• 레드 링크는 왼쪽으로 기울어져있다.
• 부모로부터의 연결이 레드 링크면 레드 노드
• 어떤 노드도 레드 링크 두 개와 연결될 수 없다.
• 레드 노드의 자식은 블랙
• null 노드는 블랙
• 루트 노드는 블랙
• 블랙을 기준으로 균형잡혀있다. (레드는 무시)
  • 어떤 노드에서 null 노드까지의 모든 경로의 블랙 거리는 같다.

연산(회전, 색 뒤집기)이 일어나는 상황

• 레드 링크가 오른쪽에 있을때(right leaning red link)
• 트리가 편향되었을때 → 같은 방향으로 노드가 계속 추가 되었을때

Insertion

삽입 코드

void insert(const K& key, const D& data);

bool _isRed(Node*& node) const;
void _insert(Node*& node, const K& key, const D& data);
void _balance(Node*& node);
void _rotateRight(Node*& node);
void _rotateLeft(Node*& node);
void _colorFlip(Node*& node);
Color _colorChange(Color c);

template <typename K, typename D>
bool RB<K, D>::_isRed(Node*& node) const
{
    if (!node) return BLACK; // null(nil) nodes are black.
    return node->color == RED;
}

template <typename K, typename D>
void RB<K, D>::insert(const K& key, const D& data)
{
    _insert(root, key, data);
    root->color = BLACK; // 루트는  항상 블랙
}

template <typename K, typename D>
void RB<K, D>::_insert(Node*& node, const K& key, const D& data)
{
    if (!node) {
        node = new Node(key, data, RED, 1);
        return;
    }
    else if (node->key == key) {
        Node* tmp = node;
        Node* n = new Node(node->key, data, node->color, node->size);
        n->left = node->left;
        n->right = node->right;
        node = n;
        delete tmp;
        return;
    }
    else if (node->key < key) {
        _insert(node->right, key, data);
    }
    else { //node->key > key
        _insert(node->left, key, data);
    }

    if (_isRed(node->right) && !_isRed(node->left)) _rotateLeft(node);
    if (_isRed(node->left) && _isRed(node->left->left)) _rotateRight(node);
    if (_isRed(node->left) && _isRed(node->right)) _colorFlip(node);

    node->size = 1 + _size(node->left) + _size(node->right);
}

template <typename K, typename D>
void RB<K, D>::_rotateRight(Node*& node)
{
    Node* tmp = node->left;
    node->left = tmp->right;
    tmp->right = node;
    tmp->color = node->color;
    node->color = RED;
    tmp->size = node->size;
    node->size = 1 + _size(node->left) + _size(node->right);
    node = tmp;
}

template <typename K, typename D>
void RB<K, D>::_rotateLeft(Node*& node)
{
    Node* tmp = node->right;
    node->right = tmp->left;
    tmp->left = node;
    tmp->color = node->color;
    node->color = RED;
    tmp->size = node->size;
    node->size = 1 + _size(node->left) + _size(node->right);
    node = tmp;
}

template <typename K, typename D>
void RB<K, D>::_colorFlip(Node*& node)
{
    node->color = _colorChange(node->color);
    node->left->color = _colorChange(node->left->color);
    node->right->color = _colorChange(node->right->color);
}

template <typename K, typename D>
typename RB<K, D>::Color RB<K, D>::_colorChange(Color c)
{
    return c == BLACK ? RED : BLACK;
}

삭제 - 어렵다.

공통적으로 가장 인기있는 방식은 부모 포인터를 기반으로 둔다. 이는 상당한 오버헤드를 가지고 처리되어야할 것들이 줄어주지 않는다.

LLRB 2-3 트리에 관한 delete() 함수는 탑다운 2-3-4 트리에서 삽입 연산에 사용된 접근 방식의 역을 토대로 둔다. 이는 2-노드에서 탐색이 끝나지 않게 보장하기 위해서 탐색 경로로 내려가면서 회전과 색 변환을 수행한다. 그래서 가장 아래에서 노드를 삭제할 수 있다. 삽입 연산시 재귀 호출에 따라오는colorFlip(), rotateRight()와 rotateLeft()에 사용되는 코드를 공유하기 위해 코드를 _fixUp()함수로 사용. 이 함수덕에 탐색 경로를 따라 내려가면서 나오는 오른쪽의 레드 링크와 균형이 깨진 4-노드들은 그대로 나둘 수 있다. 남겨진 불균형 부분들은 이 함수를 통해 트리를 올라가면서 고쳐질 것이다. 여기서 오른쪽 노드가 4-노드일때 추가 회전이 요구된다.

// 삽입에서 사용하던 코드를 함수로 만들어 사용
template <typename K, typename D>
void RB<K, D>::_fixUp(Node*& node)
{
    if (!node) return ;
    if (_isRed(node->right) && !_isRed(node->left))
        _rotateLeft(node);
    if (_isRed(node->left) && _isRed(node->left->left))
        _rotateRight(node);
    if (_isRed(node->left) && _isRed(node->right))
        _colorFlip(node);

    node->size = 1 + _size(node->left) + _size(node->right);
}
// 삽입 코드는 아래와 같이 된다.
template <typename K, typename D>
void RB<K, D>::_insert(Node*& node, const K& key, const D& data)
{
    if (!node) {
        node = new Node(key, data, RED, 1);
        return;
    }
    else if (node->key == key) {
        Node* tmp = node;
        Node* n = new Node(node->key, data, node->color, node->size);
        n->left = node->left;
        n->right = node->right;
        node = n;
        delete tmp;
        return;
    }
    else if (node->key < key) {
        _insert(node->right, key, data);
    }
    else { //node->key > key
        _insert(node->left, key, data);
    }
    _fixUp(node);
}

먼저 웜업으로 deletion-the-minimum 연산을 고려해보면, 균형을 유지하면서 좌측 최하단의 노드를 삭제하는 것이 목적이다. 그렇게 하기 위해서 현재 노드나 그 노드의 왼쪽 자식이 레드인 것을 변하지 않게 유지한다. 현재 노드가 레드이고 그 노드의 왼쪽 자식과 왼쪽의 손자 노드 모두 블랙이 아닌 경우가 아니라면 왼쪽으로 이동함으로서 연산 수행할 수 있다. 이런 경우 colorFlip으로 트리가 변하지 않게 유지할 수 있지만 오른쪽으로 레드 링크로 이어진 노드를 맞이할 수 있다. 이 경우엔 두 회전과 colorFlip으로 교정할 수 있다. 이러한 연산들은 moveRedLeft에서 구현된다.

template <typename K, typename D>
void RB<K, D>::deleteMin()
{
    _deleteMin(root);
    root->color = BLACK;
}

template <typename K, typename D>
void RB<K, D>::_deleteMin(Node*& node)
{
    if (!node->left) {
        delete node;
        node = nullptr;
        return;
    }

    if (!_isRed(node->left) && !_isRed(node->left->left))
        _moveRedLeft(node);

    _deleteMin(node->left);
    _fixUp(node);
}

template <typename K, typename D>
void RB<K, D>::_moveRedLeft(Node*& node)
{
    _colorFlip(node);
    if (_isRed(node->right->left))
    {
        _rotateRight(node->right);
        _rotateLeft(node);
        _colorFlip(node);
    }
}

template <typename K, typename D>
void RB<K, D>::deleteMax()
{
    _deleteMax(root);
    root->color = BLACK;
}

template <typename K, typename D>
void RB<K, D>::_deleteMax(Node*& node)
{
    if (_isRed(node->left))
        rotateRight(node);

    if (!node->right)
    {
        delete node;
        node = nullptr;
        return;
    }

    if (!_isRed(node->right) && !_isRed(node->right->left))
        _moveRedRight(node);

    _deleteMax(node->right);

    _fixUp(node);
}

template <typename K, typename D>
void RB<K, D>::_moveRedRight(Node*& node)
{
    _colorFlip(node);
    if (_isRed(node->left->left))
    {
        _rotateRight(node);
        _colorFlip(node);
    }
}

앞서 말했듯이 Top-down 2-3-4트리로 조건에 맞게 3, 4-노드로 변환하면서 경로로 내려온다. 삭제 후 재귀적으로 fixUp() 호출하여 규칙에 맞게 다시 갖춰진다.deleteMin()과 deleteMax()를 잘 보고 그려보면 된다.

일반적인 삭제는 moveRedRight가 필요. deleteMax()에서 사용해봤다. 이 함수는 moveRedLeft()와 유사하지만 더 간단하다. 트리를 불변하게 유지 시키기 위해서 왼쪽의 레드 링크를 탐색경로에서 오른쪽으로 회전시켜야한다. 만약 internal 노드를 삭제할 때 오른쪽 서브트리에서의 최소 노드와 값과 데이터를 바꾸고 그 최소노드를 삭제한다.

template <typename K, typename D>
void RB<K, D>::_remove(Node*& node, const K& key)
{
    if (key < node->key) { // when the search path is towards the left sub-tree of the node, similar to deleteMin()
        if (!_isRed(node->left) && !_isRed(node->left->left))
            _moveRedLeft(node);
        _remove(node->left, key);
    }
    else { // when the search path is towards the right sub-tree of the node, similar to deleteMax() and when it finds the target
        if (_isRed(node->left)) _rotateRight(node);

        // when found the key and its right-sub-tree doesn't exist
        if (key == node->key && node->right == nullptr) {
            delete node;
            node = nullptr;
            return;
        }

        if (!_isRed(node->right) && !_isRed(node->right->left))
            _moveRedRight(node);

        if (key == node->key) {
            Node* tmp = _min(node->right);
            Node* replace = new Node(tmp->key, tmp->data, node->color, node->size);
            replace->left = node->left;
            replace->right = node->right;
            tmp = node;
            node = replace;
            delete tmp;
            _deleteMin(node->right);
        }
        else
            _remove(node->right, key);
    }
    _fixUp(node);
}

• 출처 : 홍정모의 알고리듬 압축코스 part 1 & https://sedgewick.io/wp-content/themes/sedgewick/papers/2008LLRB.pdf

Dictionary, AVL and Red-Black tree 코드 : https://github.com/kkj-100-010-110/tree

B-Tree

디스크 드라이브나 직접 접근 기억 장치들(direct-access secondary storage devices) 잘 작동하기 위해 디자인된 균형 이진 탐색 트리이다. 레드 블랙 트리와 비슷하지만 B-tree는 디스크 접근 연산들을 최소화 부분에서 더 낫다. 많은 데이터 베이스에서 이 트리를 사용한다.

B-tree 노드는 다양한 노드 수를 가질 수 있다. B-tree의 ‘branching factor’는 꽤 클 수 있다. 다만, 이 크기는 사용되는 디스크 드라이브에 의존적. log의 밑은 높이를 나타내는데 branching factor가 커질 수록 이 높이는 매우 낮아진다.

B-tree는 자연스럽게 이진 탐색 트리를 일반화한 것.

• Data structure on secondary storage

컴퓨터는 메모리 용량을 제공하는데 다양한 기술들을 이용. 메인 메모리는 실리콘 칩으로 구성되어있고 이는 테이프나 디스크 드라이브 같은 자기 저장 기계(magnetic storage technology)보다 빠르고 비싸다. 대부분의 컴퓨터는 solid-state drives(SSD)나 magnetic disk drive 형태의 secondary storage를 가진다. 상대적으로 느리지만 많은 데이터를 저장할 수 있다. 드라이버 구성

디스크 드라이브는 기계 부품을 움직여야 하므로 굉장히 느리다. 두 부품의 움직임이 있는데 이는 platter들의 회전과 arm들의 움직임이다. 회전의 속도는 분당 5,400-15,000 회전(RPM, revolution per minute)을 가진다. 일반적으로 서버 등급의 드라이브들은 15,000 RPM, 데스크탑 7,200 RPM, 랩탑 5,400 PRM을 가진다. 7,200 RPM은 빨라 보이지만 한번의 회전이 8.33 ms가 소요. 이는 메인 메모리에서 일반적으로 데이터 접근 시간 50 ns 보다 다섯자리 차이 난다. 다른 말로, 컴퓨터가 특정 아이템으로 read/write head에 위치하기 위한 full rotation을 대기하면, 그시간 동안 컴퓨터는 100,000 번 메인 메모리에 접근할 수 있다. 평균 wait 대기하는데 반만 회전하는데 이 또한 메모리 접근 시간에 비하면 굉장히 차이가 크다. arm들의 움직임도 시간이 조금 걸린다. 평균 4 ms 소요. 기계 움직임에 대기하는데 소요되는 시간(latency)를 줄이기 위해서 디스크 드라이브들은 하나의 아이템이 아닌 여러개의 아이템에 한번에 접근한다. 정보(information)는 많은 track 내부에서 연속적으로 나타나는 bit들의 동일한 크기의 block들로 나누어지고, 각 디스크가 읽고 쓰는데 하나 이상의 블록들을 가진다. 전형적인 디스크 블록 사이즈는 512 - 4096 bytes 크기. read/write head가 정확하게 위치해 있고 platter가 원하는 block의 시작점에 회전했을때 자기 저장 디스크 드라이브를 읽고 쓰는 것은 완전한 전자활동을 하며 큰 데이터의 양을 디스크 드라이브는 빠르게 읽고 쓸 수 있다. 종종 디스크 드라이브로부터 정보의 블록에 접근하고 읽는 것이 읽은 모든 정보들을 처리하는 시간보다 더 걸린다. 실행 시간의 두 가지 주요한 요소들은

• 디스크 접근의 수(the number of disk accesses)
• CPU 시간

디스크 접근 수를 디스크 드라이브에 쓰거나 그것으로부터 읽어오는데 필요한 정보의 block 수로 측정. 디스크 접근 시간은 상수가 아님에도(현재 track과 요구되는 track 사이의 거리에 의존적이며, platter의 초기 회전하는 지점에 또한 의존적), 읽고 쓰여진 block의 수는 디스크 드라이브에 접근하는데 사용된 전체 시간의 괜찮은 1차 근사값(first-order approximation)을 제공한다.

전형적인 B-tree 응용에서 처리되는 데이터의 양은 모든 데이터가 메인 메모리에 한번에 알맞게 들어맞을 수 없을 정도로 크다. B-tree 알고리듬은 필요에 따라 디스크로부터 선택된 blocks을 메인 메모리에 복사하고 변경된 block들을 다시 디스크에 쓴다(write). B-tree 알고리듬은 언제든 메인 메모리에 일정한 크기의 block들을 유지하고 메인 메모리의 크기는 B-tree의 크기를 제한하지 않는다.

B-tree의 절차(procedure)는 디스크로부터 정보를 메인 메모리로 읽어(read)올 수 있어야하고 메인 메모리에서 정보를 디스크로 쓸(write) 수 있어야한다. 오브젝트 x가 있다고 가정. x가 현재 메인 메모리에 있다면, 코드는 x의 어트리뷰트들을 참조할 수 있다. 그렇지만 x가 디스크 드라이브에 있다면, 프로시져는 오브젝트 x를 가지고 있는 block을 메인 메모리로 읽기 위해서 x의 어트리뷰트들을 참조하기전에 DISK-READ(x)를 실행시켜야한다.(만약 x가 메인 메모리에 있으면 DISK-READ(x)는 disk accesss를 필요로 하지 않는다. 이를 ‘no-op’이라 한다.) 유사하게 오브젝트 x 어트리뷰트 변경된 내용들을 저장하고 담고 있는 block을 디스크에 쓰기(write) 위해 DISK-WRITE(x)를 호출한다.

x = a pointer to some object
DISK-READ(x)
operations that access and/or modify the attributes of x
DISK-WRITE(x) // omitted if no attributes of x were changed
operations that access but do not modify the attributes of x 

컴퓨터는 항상 오직 제한된 수의 block들을 메인 메모리에 유지할 수 있다. B-tree 알고리듬은 컴퓨터가 자동으로 더이상 사용하지 않는 block들을 메인 메모리로부터 보내는(flush) 것을 가정한다.

대부분 B-tree 알고리듬의 실행 시간은 DISK-READ와 DISK-WRITE 연산 수에 달려있다. 이 연산들 각각 가능한 많은 정보를 read 또는 write 하기 원한다. 그래서 B-tree의 노드는 보통 전체 디스크 block의 크기 만큼 크고 이 크기는 B-tree가 가질 수 있는 자식의 수를 제한한다.

디스크 드라이브에 저장된 사이즈가 큰 B-tree는 block의 크기에 비례한 key의 크기에 따라 종종 50-2,000 branching factor를 가진다. branching factor가 크다면 트리의 높이와 키를 찾는 디스크 접근의 수도 현저히 줄어든다. branching factor가 1001이고 height가 2인 트리는 키를 10억개 이상 저장할 수 있다. 만약 루트노드가 영구적으로 메인 메모리에 유지되면 트리에서 키를 찾는 경우 많아봐야 2번의 디스크 접근이면 충분하다.

출처 - Introduction Algorithms

참고 자료 https://www.cs.cornell.edu/courses/cs312/2004sp/lectures/lec24.html

• B-tree 특징 - (출처: 유튜브 - 쉬운코드)
  • 각 노드의 최대 자식 수를 M이라하면 각 노드의 최대 키의 수는 M-1이다.
  • 루트와 리프 노드를 제외한 각 노드의 최소 자식 수는 $\lceil M/2 \rceil$(무조건 올림, e.g. M이 3이라면 2)
  • 루트 노드를 제외한 각 노드의 최소 키의 수는. $\lceil M/2 \rceil$ - 1
  • internal 노드의 키의 수가 x개라면 자녀 노드의 수는 x+1개이다.
    • 몇 차 B-tree인지 상관없이 internal 노드는 최소한 2개의 자식 노드를 가진다.
    • M이 정해지면 internal 노드들은 최소 $\lceil M/2 \rceil$ 개의 자식 노드를 가진다.
• B-tree 특징 - (출처: geeksforgeeks)
  • 모든 리프 노드들은 같은 레벨이다.
  • 최소 차수 ‘t’에 의해 정의, ‘t’의 값은 disk block 크기에 의존적
  • 루트 노드를 제외한 모든 노드들은 최소 t-1 키들을 가져야한다. 루트 노드는 최소한 하나의 키를 가지고 있다.
  • 루트를 포함한 모든 노드들은 최대 2*t-1 키들을 가질 수 있다.
  • 한 노드의 자식 수는 그 노드의 키 수에 1 더한 값과 동일
  • 한 노드의 모든 키는 오름차순으로 정렬되어있다. 두 키 k1과 k2 사이의 자식은 k1에서 k2까지의 범위에서 모든 키를 가질 수 있다.
  • 이진 탐색 트리와 달리 루트로 부터 커지거나 줄어든다.
  • 다른 균형 이진 탐색 트리들과 같이 탐색, 삽입, 삭제 연산에서 시간복잡도는 O(log n)
  • 삽입은 항상 리프 노드에서 발생

https://www.cs.usfca.edu/~galles/visualization/BTree.html

To Be Continued..

이번 챕터에서는 OpenGL에서 어떻게 카메라를 설정하는지 알아보고 3차원 공간에서 카메라가 어떻게 자유롭게 움직이게 할 수 있는지 알아본다. 또한 카메라 클래스 생성과 키보드, 마우스 입출력을 다룰 것.

Camera/View space

view 행렬이 모든 world 좌표들을 카메라의 위치와 방향과 연관된 view 좌표로 변환하는 것. 카메라를 정의하기 위해서 world-space에서 카메라의 위치, 카메라로부터 바라보는 방향, 우측을 가리키는 벡터와 상단을 가리키는 벡터가 필요하다. 실제로 수직인 세 단위 축과 원점인 카메라의 위치로 좌표계를 생성.

Camera position

카메라 위치를 갖는 것은 쉽다. 카메라 위치는 카메라 위치를 가리키는 world-space 공간의 하나인 벡터. 이전 챕터와 같이 설정

glm::vec3 cameraPos = glm::vec3(0.0f, 0.0f, 3.0f);

양의 방향인 z축으로 움직이면 카메라는 뒤쪽으로 움직인다.

Camera direction

그 다음 벡터는 카메라의 방향을 요구한다. 지금은 카메라를 scene의 원점(0, 0, 0)을 향하게 했다. scene의 원점과 카메라의 위치 벡터 간의 차를 구하여 방향을 구한다. view 행렬의 좌표계에 관해 z축을 양의 방향이길 원하고 OpenGL 관습에 의해 카메라는 음의 z축을 가리키기 때문에 그 방향 벡터의 부호를 바꾸길 원한다. 벡터 간의 뻴셈의 순서를 바꾸면 카메라의 양의 z축을 가리키는 벡터를 갖는다.

glm::vec3 cameraTarget = glm::vec3(0.0f, 0.0f, 0.0f);
glm::vec3 cameraDirection = glm::normalize(cameraPos - cameraTarget);

Right axis

Camera-space의 양의 x축을 나타내는 right 벡터를 필요로 한다. 이 벡터를 갖기 위해서 world-space에서 위를 가르키는 up 벡터를 먼저 지정함으로 약간의 트릭을 사용한다. 이 up 벡터와 카메라의 방향 벡터를 외적한다. 외적의 결과는 두 벡터와 수직인 벡터이고 이 벡터는 양의 x축이다. 외적의 순서가 바뀌면 축의 부호도 바뀐다.

glm::vec3 up = glm::vec3(0.0f, 1.0f, 0.0f);
glm::vec3 cameraRight = glm::normalize(glm::cross(up, cameraDirection));

Up axis

카메라의 양의 y축을 가르키는 벡터를 갖는 것은 조금 쉽다. right 벡터와 방향벡터를 외적하면 된다.

glm::vec3 cameraUp = glm::cross(cameraDirection, cameraRight);

외적을 통하여 view/camera space에 관한 모든 벡터를 생성할 수 있다. Gram-Schmidt process로 알려져있다.

• Gram-Schmidt Process

  임의의 벡터 집합을 orthogonal 벡터들의 집합으로 변환

  orthnormal set은 위에서 구한 벡터들을 normalize한 벡터 집합

  en.wikipedia.org/wiki/Gram-Schmidt_process

이러한 카메라 벡터들을 사용하여 LookAt 행렬을 생성할 수 있다.

Look at

세 수직인 축을 사용하여 좌표 공간을 정의하면 그 세 축과 이동 벡터와 함께 행렬을 만들 수 있고 이 행렬을 곱하는 것으로 그 좌표 공간에 어느 벡터도 변환할 수 있다. 이것이 LookAt 행렬의 역할이고 지금 세 축과 카메라 벡터를 정의하는 지점으로 LookAt 행렬을 만들 수 있다.

$LookAt = \begin{bmatrix} R_x \ R_y \ R_z \ 0 \ U_x \ U_y \ U_z \ 0 \ D_x \ D_y \ D_z \ 0 \ 0 \quad 0 \quad 0 \quad 1 \end{bmatrix} \cdot \begin{bmatrix} 1 \quad 0 \quad 0 \ -P_x \ 0 \quad 1 \quad 0 \ -P_y \ 0 \quad 0 \quad 1 \ -P_z \ 0 \ \ \ \ 0 \ \ \ \ 0 \quad \ \ \ \ 1 \end{bmatrix}$

R은 right 벡터, U는 up 벡터, D는 방향 벡터, P는 카메라의 위치 벡터이다. 회전(왼쪽 행렬)과 이동(오른쪽 행렬) 부분은 도치된다. world를 회전 시키고 이동시키기 때문에 카메라를 반대 반향으로 이동 시킨다. view 행렬로서 LookAt 행렬을 사용하는 것은 모든 world 좌표를 정의된 view 공간으로 효율적으로 변환시킨다. 그러면 LookAt 행렬은 정확하게 주어진 타겟을 보는 view 행렬을 생성하는 것.

GLM은 이미 이러한 작업을 가능하게 한다. 카메라의 위치, 타겟 지점, world-space의 up을 나타내는 벡터만 명시하면 된다. 그러면 GLM은 view 행렬을 사용할 수 있는 LookAt 행렬을 생성한다.

glm::mat4 view;
view = glm::lookAt(glm::vec3(0.0f, 0.0f, 3.0f),
                   glm::vec3(0.0f, 0.0f, 0.0f),
                   glm::vec3(0.0f, 1.0f, 0.0f));

glm::lookAt 함수는 위치, 타겟, up 벡터를 각각 요구. 위 예시는 view 행렬을 생성하는데 이전 챕터에서 생성한 view 행렬과 같다.

사용자 입력을 좀 더 알아보기 전에 scene 주위를 도는 카메라를 생성. 타겟을 (0, 0, 0)으로 둔다. 원에서 지점을 나타내는 각 프레임, x, z 좌표를 생성하기 위해 삼각법을 사용하고 이것을 카메라의 지점으로 둔다. 시간이 지남에 따라 x와 y 좌표를 재계산하는 것으로 원을 모든 지점을 순회할 것. 그렇게 하여 카메라가 scene 주위를 돈다. 이 원을 미리 지정한 반지름만큼 원을 확대하고 GLFW의 glfwGetTime 함수를 사용하여 새로운 view 행렬을 생성한다.

const float radius = 10.0f;
float camX = sin(glfwGetTime()) * radius;
float camZ = cos(glfwGetTime()) * radius;
glm::mat4 view;
view = glm::lookAt(glm::vec3(camX, 0.0, camZ), glm::vec3(0.0, 0.0, 0.0), glm::vec3(0.0, 1.0, 0.0));

아래와 같이 반지름 기준으로 계속 회전하는 카메라를 볼 수 있다.

Walk around

카메라의 움직임을 조작하자. 먼저 카메라 시스템을 설정해야하므로 프로그램 상단에 카메라 변수를 정의하면 유용하다.

glm::vec3 cameraPos = glm::vec3(0.0f, 0.0f, 3.0f);
glm::vec3 cameraFront = glm::vec3(0.0f, 0.0f, -1.0f);
glm::vec3 cameraUp = glm::vec3(0.0f, 1.0f, 0.0f);

LookAt 함수는 다음과 같이 된다.

view = glm::lookAt(cameraPos, cameraPos + cameraFront, cameraUp);

첫번째 cameraPos를 설정, 방향은 현재 position과 방향 벡터의 합. 이는 움직임에도 불구하고 카메라는 계속 목표지점을 바라보게 한다. 키를 입력했을 때 cameraPos 벡터가 업데이트된다.

앞에 정의해놓은 processInput 함수에 아래 코드를 추가

void processInput(GLFWwindow *window)
{
    ...
    const float cameraSpeed = 0.05f; // adjust accordingly
    if (glfwGetKey(window, GLFW_KEY_W) == GLFW_PRESS)
        cameraPos += cameraSpeed * cameraFront;
    if (glfwGetKey(window, GLFW_KEY_S) == GLFW_PRESS)
        cameraPos -= cameraSpeed * cameraFront;
    if (glfwGetKey(window, GLFW_KEY_A) == GLFW_PRESS)
        cameraPos -= glm::normalize(glm::cross(cameraFront, cameraUp)) *
        cameraSpeed;
    if (glfwGetKey(window, GLFW_KEY_D) == GLFW_PRESS)
        cameraPos += glm::normalize(glm::cross(cameraFront, cameraUp)) *
        cameraSpeed;
}

WASD 키 중 하나를 누를때마다 카메라의 위치는 키에 맞게 업데이트된다. 카메라를 앞이나 뒤로 움직일 때 speed 값에 의해 크기 조정된 위치 벡터로부터 방향 벡터를 더하거나 뺀다. 양쪽으로 움직일 때 right 벡터를 생성하기 위해서 외적하고 right 벡터따라 움직인다. 이는 카메라를 이용할 때 친숙한 strafe 효과를 생성한다.

여기서 right 벡터를 normalize한다. 만약 하지 않으면 외적의 결과는 cameraFront 변수를 토대로 다른 크기의 벡터들을 반환할지도 모른다. 그 벡터를 normalize하지 않으면 카메라의 방향을 근거로 느리거나 빠르게 움직일 것이다.

Movement speed

현재 움직임에 관해 상수값을 사용하고 있다. 이론적으로 문제없지만 실제로 컴퓨터들은 다른 처리 출력을 가지고 있으며 그 결과 몇몇은 매초 다른 것들보다 더 많은 프레임들을 렌더링 할 수 있다. 사용자가 다른 사용자보다 더 많은 프레임을 그릴때마다 더 자주 processInput을 호출한다. 그 결과는 설정에 따라 속도가 상이하다. 모든 하드웨어에 똑같은 속도로 애플리케이션을 작동할 수 있어야한다.

그래픽 애플리케이션과 게임은 마지막 프레임을 그린 시간을 저장하는 deltatime 변수를 기록한다. 그리고 모든 속도들을 deltatime과 곱한다. 하나의 프레임에서 큰 deltatime을 가질 때(마지막 프레임이 평균보다 더 많이 걸릴 때), 그 프레임에 관한 속도는 균형을 맞추기 위해 더 높을 것이다. 이를 이용하여 어느 pc에 상관없이 각 유저들이 똑같이 느낄 수 있도록 카메라의 속도 균형을 맞출 것.

deltatime을 계산하기 위해서 2개의 전역변수를 기록

float deltaTime = 0.0f; // Time between current frame and last frame
float lastFrame = 0.0f; // Time of last frame

매 프레임 안에서 새로운 deltatime을 계산한다.

float currentFrame = glfwGetTime();
deltaTime = currentFrame - lastFrame;
lastFrame = currentFrame;

속도를 계산할 때 deltatime을 계산에 넣는다.

void processInput(GLFWwindow *window)
{
    float cameraSpeed = 2.5f * deltaTime;
    [...]
}

deltatime을 사용함으로 카메라는 초당 2.5 단위의 일정 속도로 움직일 것이다. 더불어 scene 주위를 도는 부드럽고 변함없이 일정한 카메라 시스템을 가졌다.

Look around

제한된 움직임에서 마우스 입력으로 회전 기능을 추가한다. 이를 위해서 마우스 입력을 토대로 cameraFront벡터를 바꿔야한다. 다만 마우스 회전에 맞게 방향 벡터를 바꾸는 것은 조금 복잡하고 삼각법을 요구한다.

Euler angles

오일러 각은 1700년대 오일러 레온하르트가 정의한 3D에서 회전을 표현할 수 있는 3가지 값이다. 3가지 오일러 각이 있다: pitch, yaw 그리고 roll.

pitch 각은 어느 정도로 아래와 위를 볼 것인지 묘사하고 yaw는 좌우의 정도를 나타내고 roll은 빙글 빙글 도는 정도를 나타낸다. 각각의 오일러각은 단일 변수에 의해 표현되며 세가지 모두 조합하여 3D에서 회전 벡터를 계산할 수 있다.

현재 카메라 시스템에서 pitch와 yaw 값들만 신경쓰고 roll 값은 배제한다. 새로운 방향 벡터를 나타내는 3D 벡터에 주어진 pitch와 yaw 값을 변환한다. pitch와 yaw 값을 방향벡터로 변환하는 과정은 삼각함수를 요구. yaw의 값을 구한다.

glm::vec3 direction;
direction.x = cos(glm::radians(yaw)); // convert to radians first
direction.z = sin(glm::radians(yaw));

pitch의 값을 구한다.

direction.y = sin(glm::radians(pitch));

xz평면은 cos pitch에 영향을 받으므로 xz 각 축에 cos pitch를 곱한다.

direction.x = cos(glm::radians(yaw)) * cos(glm::radians(pitch));
direction.y = sin(glm::radians(pitch));
direction.z = sin(glm::radians(yaw)) * cos(glm::radians(pitch));

위 식에 대해서 약간의 설명

• direction vector(행벡터) * pitch matrix * yaw matrix 를 하면 위의 식이 나온다.

  (pitch matrix * yaw matrix)$^t$ * direction vector(열벡터)

모든 설정은 끝났다. 주의할 것은 -z축 방향을 바라보도록 맞춰준다.

yaw = -90.0f;

Mouse input

마우스의 수직 움직임으로 yaw와 수평 움직임으로 pitch 값을 갖게 한다. 이런 마우스의 움직임을 카메라에 적용.

먼저 GLFW가 커서를 숨기게하고 캡쳐하게 한다. 커서를 캡쳐하는 것은 애플리케이션이 초점을 가지는 순간 마우스 커서를 화면 창의 센터에 위치하게 하는 것.

glfwSetInputMode(window, GLFW_CURSOR, GLFW_CURSOR_DISABLED);

이 함수 호출 이후, 마우스를 움직이는 곳은 보이지 않고 창 밖으로 나갈 수 없다. 이는 완벽한 FPS 카메라 시스템이다.

pitch와 yaw 값을 계산하기 위해서 GLFW이 마우스 이벤트를 인식할 수 있게 해야한다. 이를 아래와 같은 프로토타입을 가진 함수를 생성함으로 수행한다.

void mouse_callback(GLFWwindow* window, double xpos, double ypos);

여기서 xpos와 ypos는 현재 마우스의 위치를 나타낸다. 마우스가 움직일 때마다 mouse_callback함수가 호출되게 GLFW에 콜백함수를 등록한다.

glfwSetCursorPosCallback(window, mouse_callback);

fly style 카메라에 관한 마우스 입력을 처리할 때, 카메라의 방향 벡터를 완전히 계산할 수 있기전에 몇 가지 해야하는 스텝들이 있다.

1. 마지막 프레임 이후 마우스의 offset 계산
2. 카메라의 yaw와 pitch 값에 offset 값을 추가
3. pitch 값의 minimum/maximum 최소/최대값에 제약 추가
4. 방향 벡터 계산

첫번째 단계에서 먼저 애플리케이션에서 마지막 마우스 위치를 저장해야한다. 이는 스크린의 중앙에 위치하게 초기화 한다. 여기서 800 x 600이므로 아래와 같이 설정

float lastX = 400, lastY = 300;

이후 마우스 콜백 함수에서 바로 이전의 프레임과 현재 프레임 사이의 offset movement 계산한다.

float xoffset = xpos - lastX;
float yoffset = lastY - ypos; // reversed: y ranges bottom to top
lastX = xpos;
lastY = ypos;

const float sensitivity = 0.1f;
xoffset *= sensitivity;
yoffset *= sensitivity;

여기서 각 offset 값에 sensitivity를 곱한다. 만약 이를 생략하면 마우스의 움직임이 엄청 강할 것이다. 이는 sensitivity 값을 기호에 알맞게 조절할 수 있다.

다음에 전역으로 선언된 pitch와 yaw 값에 offset 값을 더한다.

yaw += xoffset;
pitch += yoffset;

세번째로는 카메라에 몇가지 제약을 추가하는데 사용자들이 이상한 카메라 움직임을 가지지 못하게 할 수 있다. LookAt을 한번 뒤집어 방향벡터가 world의 up 방향과 평행이 되는 것도 못하게 할 수 있다. pitch가 89도 보다 더 높게 못보게 한다. 90도에서 뒤집힌 LookAt을 갖기 때문이다. -89 이하로도 못보게 한다.

if(pitch > 89.0f)
    pitch = 89.0f;
if(pitch < -89.0f)
    pitch = -89.0f;

yaw에는 제약을 두지 않는데 만약 원한다면 비슷한 방식으로 두면 된다.

마지막으로 바로 이전에 구했던 식을 사용하여 실제 방향 벡터를 계산한다.

glm::vec3 direction;
direction.x = cos(glm::radians(yaw)) * cos(glm::radians(pitch));
direction.y = sin(glm::radians(pitch));
direction.z = sin(glm::radians(yaw)) * cos(glm::radians(pitch));
cameraFront = glm::normalize(direction);

이는 방향 벡터를 계산하고 마우스의 움직임으로 계산된 모든 회전을 갖는다. glm의 LookAt 함수에 cameraFront 벡터가 이미 포함되어 있기에 준비는 다 되어있다.

지금 바로 실행하면 창이 생기자마자 커서에 위치에 따라 카메라가 바로 큰 급격한 변화가 생긴다. 이는 커서가 창에 들어서자마자 마우스 콜백 함수가 호출되고 xpos와 ypos 위치가 스크린으로부터 들어선 마우스 위치로 되기 때문이다. 이는 스크린의 중앙으로부터 많이 벗어난 위치가 될 수도 있고 이러한 큰 offset의 결과로 이같은 급격한 창 안의 scene의 변화를 가진다. 이러한 이슈를 피하는 방식은 bool 타입의 전역 변수를 정의하여 먼저 마우스의 입력 값을 받았는지 체크한다. 처음엔 초기 마우스 위치를 xpos와 ypos 값으로 업데이트한다.

if (firstMouse) // initially set to true
{
    lastX = xpos;
    lastY = ypos;
    firstMouse = false;
}

최종적으로 아래의 코드가 된다.

void mouse_callback(GLFWwindow* window, double xpos, double ypos)
{
    if (firstMouse)
    {
        lastX = xpos;
        lastY = ypos;
        firstMouse = false;
    }
    float xoffset = xpos - lastX;
    float yoffset = lastY - ypos;
    lastX = xpos;
    lastY = ypos;

    float sensitivity = 0.1f;
    xoffset *= sensitivity;
    yoffset *= sensitivity;

    yaw += xoffset;
    pitch += yoffset;

    if(pitch > 89.0f)
        pitch = 89.0f;
    if(pitch < -89.0f)
        pitch = -89.0f;

    glm::vec3 direction;
    direction.x = cos(glm::radians(yaw)) * cos(glm::radians(pitch));
    direction.y = sin(glm::radians(pitch));
    direction.z = sin(glm::radians(yaw)) * cos(glm::radians(pitch));
    cameraFront = glm::normalize(direction);
}

이제 실행하면 마우스 입력을 통해서 회전하는 것을 볼 수 있다.

Zoom

zooming 인터페이스를 구현할 것이다. 이전 챕터에서 FoV(Field of View)가 scene을 얼마나 볼 수 있는지 대해서 알아봤고 FOV가 작아질 때 scene의 투영된 공간도 작아진다. 이 더 작아진 공간은 같은 NDC로 투영, zooming in 된 것처럼 된다. 줌인을 위해서 마우스 스크롤 휠을 이용. 마우스 이동과 키보드 입력과 비슷하게 마우스 스크롤에 관한 콜백함수를 가질 것.

void scroll_callback(GLFWwindow* window, double xoffset, double yoffset)
{
    Zoom -= (float)yoffset;
    if (Zoom < 1.0f)
    Zoom = 1.0f;
    if (Zoom > 45.0f)
    Zoom = 45.0f;
}

스크롤할 때 yoffset 값은 수직으로 스크롤된 양을 말해준다. scrool_callback 함수가 호출되었을 때 전역으로 선언된 fov 변수의 내용을 변경한다. 45.0이 디폴트 fov 값이므로 zoom level을 1.0-45.0 사이로 제약을 둔다.

이제 GPU의 각 프레임에 perspective projection matrix를 올려야한다. 이때 fov 변수와 함께 올린다.

projection = glm::perspective(glm::radians(fov), 800.0f / 600.0f, 0.1f, 100.0f);

마지막으로 스크롤 콜백 함수를 등록한다.

glfwSetScrollCallback(window, scroll_callback);

그럼 이제 줌이되는 결과를 볼 수 있다.

참고 - projection 행렬은 이제 렌더 루프 안으로 가야한다.

Camera class

Learn OpenGL github에서 확인.

여기서 소개된 카메라 시스템은 오일러 각을 이용하고 대부분의 작업과 목적에 잘 맞는 fly like 카메라이다. 다만, FPS나 flight simulation(비행시뮬레이션)과 같은 다른 카메라 시스템을 생성할 때 조심해야한다. 각 카메라 시스템은 자기만의 트릭과 기이한 점들을 가지고 있으므로 그에 대해 많은 공부를 해야한다. 예를들어 fly 카메라는 pitch 값이 90도이상이 안되고 roll 값을 고려하지 않을 때 static up 벡터 (0, 1, 0)는 작동하지 않는다.

좌표계를 NDC로 변환하는 것은 보통 최종적으로 물체들의 vertices들을 NDC로 변환되기 전에 그 vertices를 여러 좌표계로 변환하는 단계적 방식으로 하는 것. 좌표들을 여러 intermediate 좌표계들로 변환하는 이점은 몇가지 연산/계산들이 특정 좌표계에서는 더 쉬워진다는 것. 총 다섯가지 다른 좌표계들이 있다. 이는

• Local space (or Object space)
• World space
• View space
• Clip space
• Screen space

여기 5가지 모두 다 다른 상태이며 vertices이 fragments로 되기전 변환되는 곳들이다.

The global picture

좌표들을 하나의 공간에서 다음 좌표 공간으로 변환하기 위해서 여러가지 변환 행렬을 사용할 것. 여기서 가장 중요한 것은 model, view, projection 행렬이다. vertex 좌표들이 제일 처음 지역(local) 좌표 또는 지역 공간에서 시작하고 그 후 world 좌표, view 좌표, clip 좌표 마지막으로 screen 좌표로 된다.

1. Local 좌표들은 local 원점과 연관있는 오브젝트의 좌표들, 오브젝트들이 시작하는 좌표.
2. 다음 단계는 local 좌표를 world-space 좌표로 변환(더 넓은 세계의 좌표). 다른 오브젝트들도 이 world의 기준으로 위치 조정
3. 그 다음 이 world 좌표들을 view-space로 변환 → 각각의 좌표는 카메라나 viewer의 시점인 방식
4. 이 후 view-space의 좌표들을 clip 좌표로 투영. Clip 좌표들은 -1.0 ~ 1.0 범위로 처리하며 어떤 vertices들이 스크린으로 나타나는지 결정. 이 clip 좌표들을 원근 투영을 원하면 원근법 추가할 수 있다.
5. 마지막으로 glViewport에 정해진 범위 -1.0 ~ 1.0으로 좌표들을 변환하는 viewport 변환을 호출하는 처리로 clip 좌표를 screen 좌표로 변환. 이 결과를 fragment들로 되게 하기 위해서 rasterizer로 전송.

각 공간에 어떤 것을 사용할지 알고 있을 것이다. 각각의 다른 공간들에 vertices를 변환하는 이유는 특정 좌표계에서 몇몇 연산들은 좀 더 타당하고 쉽게 사용할 수 있는 점이다. 예를들어 오브젝트를 수정할 때 local space에서 연산하는게 가장 알맞고 반면에 오브젝트들의 위치에 관해서 계산하는 특정 연산들은 world-space에서 가장 알맞는다. Local-space에서 clip-space까지 한번에 하나의 변환 행렬을 할 수도 있다. 다만 좀 더 낮은 유연성을 지닌다.

Local space

Local space는 오브젝트가 시작하는 오브젝트의 지역에 관한 좌표 공간이다. Blender 같은 모델링 소프트웨어 패키지에서 큐브를 생성한다고 생각해보자. 마지막 응용단계에서 큐브의 위치는 다를지라도 큐브의 원점은 (0, 0, 0)일 것이다. 아마도 생성한 모든 모델 오브젝트들은 (0, 0, 0)의 시작 지점을 갖는다. 따라서 모든 모델의 vertices들은 local-space에 있다.

World space

모든 오브젝트들을 애플리케이션에 바로 불러오면 (0, 0, 0)의 world 좌표계의 원점에 서로 겹쳐져 있을 것. 더 큰 세계 안에 각 오브젝트들의 위치를 정의해야한다. World space의 좌표는 말 그대로 world에 연관된 vertices의 좌표. 어떤 장소 주변에 각 오브젝트들이 흩어져 있는 방식으로 오브젝트들을 변환하는 좌표 공간이다. 이는 model 행렬로 수행한다.

Model matrix는 오브젝트들이 world에 놓여지는 위치와 방향에 맞게 이동, 크기 조정, 회전 변환을 하는 행렬.

View space

OpenGL의 카메라로서 보통 언급되는 것이 view space이다. 이는 camera space 또는 eye space라고도 한다. View space는 world-space의 좌표를 사용자 시점 앞으로의 좌표로 변환한 결과이다. 더구나 view-space는 카메라의 시점으로부터 보여지는 공간이다. 회전과 이동 조합의 변환으로 카메라 앞으로 특정 오브젝트들이 변환되게 수행된다. 이런 결합된 변환은 보통 view matrix 안에 저장되어있다.

Clip space

vertex shader의 동작 끝지점에 OpenGL은 좌표들이 특정 범위 안에 있는 것을 예상하며 범위를 벗어난 좌표들은 깎아내어진다(clipped). 깎여진 좌표들은 버려지고 남겨진 좌표들은 fragment로 되어 스크린에 보여진다.

보여지는 모든 좌표들을 -1.0 ~ 1.0 범위로 명시하는 것은 직관적이지 못하기 때문에 개별의 좌표계를 알맞게 설정하고 OpenGL이 알 수 있는 NDC로 변환한다.

vertex 좌표들을 view에서 clip space로 변환하기 위해서 좌표를 명시하는 projection matrix라 불리는 것을 정의한다. 예를들어 각 차원에서 -1000 ~ 1000인 좌표 범위. 그럼 projection matrix는 그 명시된 범위 안의 좌표들을 NDC(-1.0 ~ 1.0)으로 변환한다. 범위 밖의 좌표들은 -1.0 ~ 1.0 사이에서 맵핑되지 않고 짤리게 될 것. Projection matrix에서 명시된 좌표내에 좌표(1250, 500, 750)은 보여지지 않는다. 왜냐하면 x 좌표가 범위 밖이고 NDC로 변환되면 1.0보다 큰 값이기 때문이다. 그러므로 깎여진다.

Projection matrix가 생성하는 viewing box는 절두체(frustum)이라 불리고 이 frustum 내부에 속하는 각 좌표들은 스크린으로 보여진다. 명시된 범위 안의 좌표들을 2D view-space 좌표로 맵핑될 수 있는 NDC로 변환하는 총 과정을 projection이라 한다. 이 projection matrix는 3차원 좌표를 쉽게 2차원으로 맵핑하는 NDC로 투영하기 때문이다.

모든 vertices가 clip-space로 변환되었을때 마지막 연산인 perspective division이 작동하는데 이 작동하는 부분은 벡터의 동차좌표계의 원소 w에 의해 각 위치 x, y, z 요소가 나누어지는 곳이다. Perspective division은 4D clip space 좌표들을 3D NDC로 변환하는 것. 이 단계는 vertex shader 단계의 마지막 부분에 자동으로 수행된다.

이 단계 이후 결과로 나온 좌표들이 glViewport의 설정을 이용하여 스크린으로 맵핑되고 fragment로 된다.

view 좌표들을 clip 좌표로 변환하는 projection matrix는 보통 두 가지 다른 형식을 취한다. 각각의 형식은 특정 frustum을 정의한다. Orthographic(정사영) projection이나 perspective(원근) projection을 생성할 수 있다.

Orthographic projection

Orthographic projection matrix는 큐브와 같은 frustum box를 정의하는데 이 box는 이 box의 범위 밖의 각 vertex가 clipped(깎여진)된 곳인 clipping space를 정의한다. Orthographic projection matrix를 생성할 때 보이는 frustum의 길이, 폭, 높이를 명시한다. 이 frustum 안의 모든 좌표는 이 행렬의 변환 후 NDC 범위 안에 속할 것이고 clipped되지 않는다. 이 frustum은 컨테이너 같이 보여진다. 이 frustum은 보여지는 좌표들을 정의하며 폭, 높이, 가까운 평면(near plane)과 먼 평면(far plane)으로 명시된다. 가까운 평면 앞의 좌표와 먼 평면의 뒤 좌표는 clipped된다. 이 orthographic frustum은 frustum 내의 모든 좌표를 NDC로 바로 맵핑한다. 이는 부작용(side effects)가 없는데 왜냐하면 변환된 벡터의 w 요소를 건들지 않기 때문이다. 만약 w 요소의 값이 1.0이라면 perspective division은 좌표를 바꾸지 않는다.

이 정투영 행렬을 생성하기 위해서 GLM의 built-in 함수 glm::ortho를 사용한다.

glm::ortho(0.0f, 800.0f, 0.0f, 600.0f, 0.1f, 100.0f);

첫번째 두 인자는 frustum의 좌우 좌표를 명시하고 세번째 인자와 네번째 인자는 위아래의 좌표를 명시한다. 이 네 점들로 가까운 평면과 먼 평면의 크기를 정의했고 다섯번째와 여섯번째의 인자는 두 평면의 거리를 정의한다. 이 특정 projection 행렬은 정해진 x, y, z 범위 내의 모든 좌표를 NDC로 변환한다.

Orthographic projection matrix는 비현실적 결과를 낳는데 이는 원근감을 고려하지 않았기 때문이다.

Perspective projection

그림처럼 원근법으로 인해 거리에 따라 차이가 보인다. Perspective projection matrix를 사용하여 이러한 효과를 모방한다. Projection matrix는 clip space에 주어진 frustum 범위에 매핑될 뿐만아니라 viewer로부터 거리가 멀수록 w 요소의 값은 더 올라가는 방식으로 각 vertex 좌표의 w 값을 조작한다. 좌표들이 clip-space로 변환되었을 때 좌표들은 -w ~ w 범위 안에 있다(범위 밖은 clipped). OpenGL은 보여지는 좌표들이 최종 vertex shader 출력값으로 -1.0 ~ 1.0 범위로 떨어지는 것을 요구한다. 이렇게하여 좌표들이 clip-space에 있을 때 perspective division은 clip-space 좌표들에 적용된다:

$out = \begin{pmatrix}x/w\y/w\z/w\end{pmatrix}$

vertex 좌표의 각 요소는 w 요소로 나누어진다. 이는 w요소가 왜 중요한지 말해준다. 결과로 나온 좌표들은 이제 NDS에 들어간다.

참고자료 시작

Projection matrix(https://www.songho.ca/opengl/gl_projectionmatrix.html)

컴퓨터 모니터는 2D 표면, OpenGL에 의해 렌더링되는 3D 장면들은 2D 이미지로 스크린에 투영되어야한다. GL_PROJECTION 행렬은 이 projection 변환을 위해 사용된다. 첫번째 이것은 모든 vertex 데이터들을 view space 좌표에서 clip space 좌표로 변환한다. 이후 이 clip 좌표들은 clip 좌표 w 요소로 나누어지는 것에 의해 NDC로 변환된다. 그러므로 clipping과 NDC 변환은 GL_PROJECTION으로 통합되어 있다. 6개의 파라미터(left, right, bottom, top, near and far)로 projection 행렬을 만드는지 알아보자

clipping은 clip 좌표들로 수행되는데 이는 $w_c$요소로 나누기 바로 전이다. clip 좌표 $x_c$, $y_c$, $z_c$는 $w_c$와 비교하여 검사된다. 만약 셋 중 어느 좌표가 $-w_c$보다 작으거나 $w_c$보다 크면 그 vertex는 버려진다.

$-w_c < x_c,,y_c,,z_c < w_c$ 그 이후 OpenGL은 clip이 발생한 다각형의 끝지점들을 재구성한다.

Perspective Projection

perspective projection에서 끝이 짤린 피라미드형의 절두체에서 3D point(view 좌표)는 큐브(NDC)에 매핑된다.

x 좌표의 범위는 [l, r] → [-1, 1], y 좌표의 범위는 [b, t] → [-1, 1], z 좌표의 범위는 [-n, -f] → [-1, 1] view 좌표는 오른손 좌표계, NDC는 왼손 좌표계. 이는 view space에서 원점에서 카메라는 -Z 축을 따라 보고 NDC에서는 +Z 축을 따라 본다. glFrustum 함수는 near와 far의 거리의 값을 양수값만 취하기 때문에 GL_PROJECTION 행렬의 구성 중에 이들 값에 부호를 반대로 해야한다.

OpenGL에서 view space에서 3D point는 near 평면에 투영된 것. 절두체의 상면도에서 view space의 $x$ 좌표 $x_e$는 $x_p$와 매핑된다. 측면도에서 view space의 $y$ 좌표 $y_e$는 $y_p$와 매핑된다. 여기서 $x_p$와 $y_p$는 $z_e$에 종속된다. 이 두 좌표는 $z_e$에 반비례. 이는 두 좌표가 $-z_e$로 나누어진다는 말. GL_PROJECTION을 구성하는 첫번째 단서. GL_PROJECTION 행렬 곱에 의해 view space 좌표가 변환된 후에 clip-space 좌표들은 여전히 동차좌표계이다. 마지막으로 clip 좌표들의 $w$ 요소로 나누어짐으로 의해 NDC가 된다.

$\begin{bmatrix}x_{clip}\y_{clip}\z_{clip}\w_{clip}\end{bmatrix} = M_{Projection} \cdot \begin{bmatrix}x_{view}\y_{view}\z_{view}\w_{view}\end{bmatrix}$, $\begin{bmatrix}x_{ndc}\y_{ndc}\z_{ndc}\end{bmatrix}=\begin{bmatrix}x_{clip}/w_{clip}\y_{clip}/w_{clip}\z_{clip}/w_{clip}\end{bmatrix}$

따라서 clip 좌표 $w$ 요소를 $-z_e$로 설정

$\begin{bmatrix}x_{clip}\y_{clip}\z_{clip}\w_{clip}\end{bmatrix} = \begin{bmatrix}\quad.\quad\quad . \quad\quad . \quad\quad .\quad\.\quad\quad . \quad\quad . \quad\quad .\.\quad\quad . \quad\quad . \quad\quad .\ \quad 0\quad\quad 0\quad -1\quad\quad 0\quad\end{bmatrix} \cdot \begin{bmatrix}x_{view}\y_{view}\z_{view}\w_{view}\end{bmatrix}$

GL_PROJECTION 행렬의 네번째 행의 요소들은 0, 0, -1, 0이며 $w_{view} = -z_e$ 이다.

다음은 $x_p$와 $y_p$를 NDC의 $x_n$과 $y_n$으로 일차 관계식으로 매핑하는 것. 그다음 위 방정식에서 $x_p$와 $y_p$에 그 위에서 구했던 값을 대입한다. 각 방정식에서 두 항 모두 $x_c/w_c$, $y_c/w_c$ 에 맞게 $-z_e$로 나누어지게 만들었다. 이로부터 GL_PROJECTION 행렬의 첫번째와 두번째 행을 만든다.

$\begin{bmatrix}x_{clip}\y_{clip}\z_{clip}\w_{clip}\end{bmatrix} = \begin{bmatrix}\ \frac{2n}{r-l}\quad 0\quad \frac{r+l}{r-l} \quad 0\ \ \ 0\quad\frac{2n}{t-b}\quad \frac{t+b}{t-b}\quad 0\ \.\quad . \quad . \quad .\ 0\quad 0\quad -1\quad 0\end{bmatrix} \cdot \begin{bmatrix}x_{view}\y_{view}\z_{view}\w_{view}\end{bmatrix}$

이제 세번째 행만 남았다. $z_n$을 찾는 것은 이전 것들과 조금 다른데 왜냐하면 view space에서 $z_e$는 항상 near 평면의 -n에 투영되기 때문이다. 그래서 clipping과 깊이 테스트에 관한 $z$ 값이 필요하다. 더해서 이에 대한 역변환도 가능해야한다. $z$값이 $x$와 $y$에 종속되지 않기 때문에 $z_e$와 $z_n$ 사이의 관계를 찾기 위해서 $w$ 요소를 빌린다. 따라서 세번째 행은 아래와 같다.

$\begin{bmatrix}x_{clip}\y_{clip}\z_{clip}\w_{clip}\end{bmatrix} = \begin{bmatrix}\ \frac{2n}{r-l}\quad 0\quad \frac{r+l}{r-l} \quad 0\ \ \ 0\quad\frac{2n}{t-b}\quad \frac{t+b}{t-b}\quad 0\ \ \ 0\quad \ 0 \quad \ A \quad \ B\ 0\quad 0\quad -1\quad 0\end{bmatrix} \cdot \begin{bmatrix}x_{view}\y_{view}\z_{view}\w_{view}\end{bmatrix}$, $z_n = z_c / w_c = \frac{Az_e + Bw_e}{-z_e}$

view-space에서 w_e는 1이므로 방정식은

$z_n = z_c / w_c = \frac{Az_e + B}{-z_e}$이 된다.

A, B, 계수를 찾기 위해서 ($z_n$, $z_e$) 관계식을 사용. (-n, 1) 과 (-f, 1) 그리고 이것들을 위 방정식에 대입하면 GL_PROJECTION 행렬의 모든 요소를 찾았다. Projection 행렬은 아래와 같다.

$\begin{bmatrix}\frac{2n}{r-l}\quad 0\quad \frac{r+l}{r-l} \quad 0\ 0\quad\frac{2n}{t-b}\quad \frac{t+b}{t-b}\quad 0\ \ 0\quad0 \ \frac{-(f+n)}{f-n}\ \frac{-2fn}{f-n}\ 0\quad 0\quad -1\quad 0\end{bmatrix}$

이는 일반적인 frustum에 관한 projection 행렬이다. viewing volume이 대칭적이라면 $r = -l$ 과 같고 $t = -b$ 이므로

$\begin{bmatrix}\frac{n}{r}\quad 0\quad 0 \quad 0\ 0\quad\frac{n}{t}\quad 0\quad 0\ \ 0\quad0 \ \frac{-(f+n)}{f-n}\ \frac{-2fn}{f-n}\ 0\quad 0\quad -1\quad 0\end{bmatrix}$

여기서 $z_e$와 $z_n$ 사이의 관계식을 보면 유리 함수이면 비선형 관계이다. 이는 near 평명에 매우 높은 정밀도가 있고 far 평면에서는 매우 낮은 정밀도가 있음을 의미한다. 만약 [-n, f]의 범위가 커지면 커질수록 깊이 정밀도 문제(depth precision problem)을 야기시킨다. far 평면에서의 $z_e$의 작은 변화는 $z_n$에 영향을 주지 않는다. 이러한 문제를 최소화하기 위해서 n과 f의 거리는 가능한 짧아야한다. Infinite Perspective Matrix

perspective projection matrix는 far 평면을 행렬의 세번째 행에서 무한대로 설정하여 간단하게 할 수 있다. $\begin{bmatrix}\frac{2n}{r-l}\quad 0\quad \frac{r+l}{r-l} \quad 0\ 0\quad\frac{2n}{t-b}\quad \frac{t+b}{t-b}\quad 0\ \ 0\quad0 \ -1\ -2n\ 0\quad 0 \ -1\quad 0\end{bmatrix}$,$\begin{bmatrix}\frac{n}{r}\quad 0\quad 0 \quad 0\ 0\quad\frac{n}{t}\quad 0\quad 0\ \ 0\quad0 \ -1\ -2n\ 0\quad 0\quad -1\quad 0\end{bmatrix}$

일반 perspective projection matrix와 대칭 perspective projection matirx에 무한 far 평면으로 했을 때 위와 같은 행렬들이 나온다.

이 또한 depth precision error를 갖는다.

Perspective matrix with Field of View(FOV)

특정 창 크기에서 perspective projection에 관한 주어진 near 평면과 far 평면과 4개의 매개변수를 제대로 결정하기 어렵다. 폭과 높이 그리고 수직, 수평의 FOV와 aspect ratio(화면비, 종횡비 등)으로부터 4개의 매개변수를 쉽게 끌어낼 수 있다. 하지만 이는 대칭 perspective projection matrix에서만 가능.

// This creates a symmetric frustum with vertical FOV
// by converting 4 params (fovy, aspect=w/h, near, far)
// to 6 params (l, r, b, t, n, f) 
Matrix4 makeFrustum(float fovY, float aspectRatio, float front, float back)
{
    const float DEG2RAD = acos(-1.0f) / 180;

    float tangent = tan(fovY/2 * DEG2RAD);    // tangent of half fovY
    float top = front * tangent;              // half height of near plane
    float right = top * aspectRatio;          // half width of near plane

    // params: left, right, bottom, top, near(front), far(back)
    Matrix4 matrix;
    matrix[0]  =  front / right;
    matrix[5]  =  front / top;
    matrix[10] = -(back + front) / (back - front);
    matrix[11] = -1;
    matrix[14] = -(2 * back * front) / (back - front);
    matrix[15] =  0;
    return matrix;
}

// This creates a symmetric frustum with horizontal FOV
// by converting 4 params (fovx, aspect=w/h, near, far)
// to 6 params (l, r, b, t, n, f) 
Matrix4 makeFrustum(float fovX, float aspectRatio, float front, float back)
{
    const float DEG2RAD = acos(-1.0f) / 180;

    float tangent = tan(fovX/2 * DEG2RAD);    // tangent of half fovX
    float right = front * tangent;            // half width of near plane
    float top = right / aspectRatio;          // half height of near plane

    // params: left, right, bottom, top, near(front), far(back)
    Matrix4 matrix;
    matrix[0]  =  front / right;
    matrix[5]  =  front / top;
    matrix[10] = -(back + front) / (back - front);
    matrix[11] = -1;
    matrix[14] = -(2 * back * front) / (back - front);
    matrix[15] =  0;
    return matrix;
}

Orthographic projection

Orthographic projection(정투영)에 관한 GL_PROJECTION 구현은 상대적으로 쉽다. view-space의 모든 요소는 NDC와 선형적으로 매핑된다. w 요소는 orthographic projection에 필요 없기때문에 네번째 행은 (0, 0, 0, 1)이다.

$\begin{bmatrix}\frac{2}{r-l}\quad 0\quad 0 \quad -\frac{r+l}{r-l}\ 0\quad\frac{2}{t-b}\quad 0\quad -\frac{t+b}{t-b}\ 0\quad0 \quad\ \frac{-2}{f-n}\quad -\frac{f+n}{f-n}\ 0\quad\ 0\quad\quad 0\quad\quad 1\end{bmatrix}$

view volume이 대칭이라면 좀 더 간단하게 할 수 있다. $r = -1$ 그리고 $t = -b$

$\begin{bmatrix}\frac{1}{r}\quad 0\quad 0 \quad 0\ 0\quad\frac{1}{t}\quad 0\quad 0\ 0\quad 0\quad \frac{-2}{f-n} -\frac{f+n}{f-n}\ 0\quad\ 0\quad 0\quad 1\end{bmatrix}$

참고자료 끝

perspective projection matrix는 GLM에서 생성가능하다.

glm::mat4 proj = glm::perspective(glm::radians(45.0f), (float)width /
                                                                    (float)height, 0.1f, 100.0f);

glm::perspective는 큰 절두체를 생성하는데 이는 visible space를 정의하고 clip-space 볼륨에서 벗어난 어느 것도 절두체에서 결과물로 나오지 않고 clip된다. 첫번째 매개변수는 FOV를 정의, 이는 field of view의 약어이며 viewspace를 얼마나 크게할지 설정. 사실적인 뷰를 위하여 45도로 설정, 하지만 좀 더 doom-style 결과를 원하면 좀 더 높게 설정할 수 있다. 두번째 매개변수는 aspect ratio(종횡비, 화면비 등)를 설정한다. 이는 viewport의 폭을 높이로 나눈 것으로 계산한다. 세번째와 네번째는 절두체의 near와 far 평면 설정. 보통 near 거리는 0.1 그리고 far 거리는 100.0으로 설정. near와 far 평면의 사이와 절두체 내부의 모든 vertices는 렌더링된다.

perspective 행렬의 near 값이 10.0과 같이 매우 높게 설정될 때마다 OpenGL은 카메라에 가까운 모든 좌표 즉 0과 10.0사이의 좌표들은 clip한다. 이는 아마 비디오게임하면서 경험해봤을 수도 있다. 특정 오브젝트에 가깝게 갔을때 그러한 결과를 볼 수 있다.

orthographic projection을 사용할 때 각 vertex 좌표는 clip space에 바로 매핑된다. orthographic projection은 perspective projection을 사용하지 않으므로 멀리 떨어진 물체들이 더 작게 보이지 않는다. 이는 기괴한 결과물을 보여준다. 이러한 이유로 orthographic projection은 주로 2D 렌더링에서 주로 사용되며 perspective에 의해 삐뚤어진 vertices를 가지지 않는 몇몇 건축학 또는 공학 애플리케이션에서 사용된다. 3D 모델링에 사용되는 Blender 같은 애플리케이션들은 가끔 orthographic projection을 사용하기도 한다. 이는 각 오브젝트들의 치수를 좀 더 정확하게 그리기 위함이다. Blender에서 두 projection을 한 경우를 보면 vertex간의 간격이 다르다.

Putting it all together

앞서 언급한 단계들 각각에 관한 변환 행렬들을 만들었다: model, view, projection matrix. vertex 좌표들은 이제 clip 좌표로 변환된다.

$V_{clip} = M_{projection}\cdot M_{view}\cdot M_{model}\cdot V_{local}$.

행렬 곱셈의 순서는 뒤집힌다. 행렬 곱셈을 왼쪽에서 오른쪽으로 하는 것을 기억하자. 이 결과로 나온 vertex들은 vertex shader에 있는 gl_Position에 할당되고 OpenGL은 자동으로 perspective division과 clipping을 수행한다.

• vertex shader의 출력값은 clip-space 좌표로 되기 위한 변환된 좌표를 요구하고 OpenGL을 clip-space 좌표들을 perspective division을 수행하고 NDC로 변환한다. 그리고 OpenGL은 glViewport로부터 매개변수를 사용하는데 이는 NDC를 screen 좌표로 매핑하기 위함이다. 이 처리는 viewport transformation이라 한다.

Going 3D

2D에서 3D로 바꿔볼 것.

3D로 그리기위해서 먼저 model 행렬을 생성한다. model 행렬은 모든 오브젝트들의 vertices를 global world space로 변환을 적용하기 원하는 이동, 크기 조정, 회전들로 구성되어있다.

glm::mat4 model = glm::mat4(1.0f);
model = glm::rotate(model, glm::radians(-55.0f), glm::vec3(1.0f, 0.0f, 0.0f));

vertex 좌표를 model 행렬에 곱하여 vertex 좌표를 world space 좌표로 변환한다.

그 다음 view 행렬을 만든다. scene을 살짝 뒤로 움직여서 물체를 보이게 한다.

• 카메라를 뒤로 움직이는 것은 전체 scene을 앞으로 움직이는 것과 같다.

OpenGL은 오른손 좌표계이므로 -z 방향은 앞으로 이동, z방향은 뒤로 이동이다. scene을 -z 방향으로 움직인다.

scene 주위를 움직이는 것은 다음 챕터에서 자세히 다룰 것이고 여기서는 아래의 코드로 설정

glm::mat4 view = glm::mat4(1.0f);
// note that we’re translating the scene in the reverse direction
view = glm::translate(view, glm::vec3(0.0f, 0.0f, -3.0f));

마지막으로 projection 행렬 정의한다. perspective projection을 사용할 것이며 설정은 아래와 같다.

glm::mat4 projection;
projection = glm::perspective(glm::radians(45.0f), 800.0f / 600.0f, 0.1f, 100.0f);

이제 변환 행렬들을 다 만들었고 shader에게 전달한다. 먼저 vertex shader에서 uniform으로 변환 행렬들을 설정하고 vertex 좌표들과 곱한다.

#version 330 core
layout (location = 0) in vec3 aPos;
...
uniform mat4 model;
uniform mat4 view;
uniform mat4 projection;

void main()
{
    // note that we read the multiplication from right to left
    gl_Position = projection * view * model * vec4(aPos, 1.0);
    ...
}

이제 변환 행렬들을 shader로 보낸다.

int modelLoc = glGetUniformLocation(ourShader.ID, "model");
glUniformMatrix4fv(modelLoc, 1, GL_FALSE, glm::value_ptr(model));
... // same for View Matrix and Projection Matrix

이제 vertex 좌표를 model, view, projection 행렬을 통해서 변환된다. 그 결과물은 아래와 같다.

• 바닥과 뒤쪽으로 기울어졌다.
• 조금 멀리 떨어져있다.
• 원근감있다.

More 3D

지금까지 3차원 공간에서 2차원 평면을 가지고 작업했다. 이제 2차원 평면을 3차원 큐브로 확장한다. 큐브를 렌더링하기 위해서 총 36개의 vertices(6 faces * 2 triangle * 3 vertices) 필요.

    float vertices[] = {
        -0.5f, -0.5f, -0.5f,  0.0f, 0.0f,
         0.5f, -0.5f, -0.5f,  1.0f, 0.0f,
         0.5f,  0.5f, -0.5f,  1.0f, 1.0f,
         0.5f,  0.5f, -0.5f,  1.0f, 1.0f,
        -0.5f,  0.5f, -0.5f,  0.0f, 1.0f,
        -0.5f, -0.5f, -0.5f,  0.0f, 0.0f,

        -0.5f, -0.5f,  0.5f,  0.0f, 0.0f,
         0.5f, -0.5f,  0.5f,  1.0f, 0.0f,
         0.5f,  0.5f,  0.5f,  1.0f, 1.0f,
         0.5f,  0.5f,  0.5f,  1.0f, 1.0f,
        -0.5f,  0.5f,  0.5f,  0.0f, 1.0f,
        -0.5f, -0.5f,  0.5f,  0.0f, 0.0f,

        -0.5f,  0.5f,  0.5f,  1.0f, 0.0f,
        -0.5f,  0.5f, -0.5f,  1.0f, 1.0f,
        -0.5f, -0.5f, -0.5f,  0.0f, 1.0f,
        -0.5f, -0.5f, -0.5f,  0.0f, 1.0f,
        -0.5f, -0.5f,  0.5f,  0.0f, 0.0f,
        -0.5f,  0.5f,  0.5f,  1.0f, 0.0f,

         0.5f,  0.5f,  0.5f,  1.0f, 0.0f,
         0.5f,  0.5f, -0.5f,  1.0f, 1.0f,
         0.5f, -0.5f, -0.5f,  0.0f, 1.0f,
         0.5f, -0.5f, -0.5f,  0.0f, 1.0f,
         0.5f, -0.5f,  0.5f,  0.0f, 0.0f,
         0.5f,  0.5f,  0.5f,  1.0f, 0.0f,

        -0.5f, -0.5f, -0.5f,  0.0f, 1.0f,
         0.5f, -0.5f, -0.5f,  1.0f, 1.0f,
         0.5f, -0.5f,  0.5f,  1.0f, 0.0f,
         0.5f, -0.5f,  0.5f,  1.0f, 0.0f,
        -0.5f, -0.5f,  0.5f,  0.0f, 0.0f,
        -0.5f, -0.5f, -0.5f,  0.0f, 1.0f,

        -0.5f,  0.5f, -0.5f,  0.0f, 1.0f,
         0.5f,  0.5f, -0.5f,  1.0f, 1.0f,
         0.5f,  0.5f,  0.5f,  1.0f, 0.0f,
         0.5f,  0.5f,  0.5f,  1.0f, 0.0f,
        -0.5f,  0.5f,  0.5f,  0.0f, 0.0f,
        -0.5f,  0.5f, -0.5f,  0.0f, 1.0f
    };

재미를 위해서 큐브를 회전 시킨다.

model = glm::rotate(model, (float)glfwGetTime() * glm::radians(50.0f),
glm::vec3(0.5f, 1.0f, 0.0f));

glDrawArrays을 사용하여 큐브를 그리는데 지금은 36개의 vertices을 사용하므로 이에 맞게 설정.

glDrawArrays(GL_TRIANGLES, 0, 36);

큐브처럼 보이지만 무언가 잘못됐다. 이는 OpenGL이 triangle by triagle, fragment by fragment으로 그리고 이는 이전에 그려진 픽셀을 덮어 겹쳐 그려진다. OpenGL은 draw 함수 호출에서 렌더링된 삼각형들의 순서를 고려하지 않기때문에 다른 삼각형보다 앞에 있는 삼각형이 있음에도 그 위에 삼각형들이 그려진다.

OpenGL이 겹쳐 그릴지 말지 결정하게 해주는 z-buffer라 불리는 버퍼에 depth information(깊이 정보)를 저장한다. z-buffer를 사용하여 OpenGL이 depth-testing(깊이 테스트)를 할 수 있게 설정할 수 있다.

Z-buffer

OpenGL은 depth buffer라 불리는 z-buffer에 depth 정보를 저장한다. GLFW는 자동으로 이런 버퍼를 생성한다(출력 이미지의 색상을 저장하는 color-buffer를 가지는 것과 같다). depth는 각 fragment(fragment의 z값)에 저장되며 fragment가 색상을 출력하기 원할 때마다 OpenGL은 z-buffer와 fragment의 z 값을 비교한다. 만약 현재 fragment가 다른 fragment에 뒤에 있으면 현재의 것이 버려진다. 아닌 경우 덮어쓰여진다. 이러한 처리를 depth-testing이라 하며 OpenGL에 의해서 자동으로 수행된다.

OpenGL이 실제 depth testing을 수행하는지 확실하게 하고 싶으면 먼저 OpenGL이 depth testing을 가능하게 해야한다. 왜냐하면 기본값은 가능하지 않게 되어 있다. glEnable을 사용하여 설정한다. glEnable과 glDisable 함수는 OpenGL에서 특정 기능들을 사용 가능하게 하거나 사용 못하게 할 수 있다. 이 함수들로 설정한 부분들을 다시 설정할 함수들이 나와 설정을 변경할 때까지 설정 값들이 유지된다. GL_DEPTH_TEST를 가능하게 해준다.

glEnable(GL_DEPTH_TEST);

depth 버퍼를 사용하기때문에 렌더 루프에서 매번 depth 버퍼를 정리해야한다. 아니면 depth 정보가 이전 프레임에 관한 것으로 남아있다. 이는 색상 버퍼를 정리해주는 것과 같다. glClear에 DEPTH_BUFFER_BIT을 명시하면 된다.

glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT);

아래와 같이 깔끔한 큐브가 나온다.

More cubes

10개의 큐브들을 이제 스크린에 나타내보자. 각 큐브는 똑같지만 회전과 world-space에서의 위치가 다르다. 그래픽적인 레이아웃은 이미 정의되어있으므로 버퍼와 attribute array는 바꿀 필요가 없다. 해야할 것은 각 오브젝트들을 world-space로 model 행렬을 통해 변환하는 것.

먼저 world-space에서 각 큐브에 관한 이동 벡터에 대한 위치를 정의. 10개의 큐브 위치를 glm::vec3 배열에 정의.

glm::vec3 cubePositions[] = {
    glm::vec3( 0.0f, 0.0f, 0.0f),
    glm::vec3( 2.0f, 5.0f, -15.0f),
    glm::vec3(-1.5f, -2.2f, -2.5f),
    glm::vec3(-3.8f, -2.0f, -12.3f),
    glm::vec3( 2.4f, -0.4f, -3.5f),
    glm::vec3(-1.7f, 3.0f, -7.5f),
    glm::vec3( 1.3f, -2.0f, -2.5f),
    glm::vec3( 1.5f, 2.0f, -2.5f),
    glm::vec3( 1.5f, 0.2f, -1.5f),
    glm::vec3(-1.3f, 1.0f, -1.5f)
};

렌더 루프에서 glDrawArrays 10번 불러야하지만 이번에 draw call 보내기전에 다른 model 행렬을 vertex shader에 보낸다. 다른 model 행렬을 오브젝트를 10번 그리는 렌더 루프안에 작은 루프문을 매번 생성한다. 또한 각 컨테이너에 작은 특정 회전을 추가한다.

glBindVertexArray(VAO);
for(unsigned int i = 0; i < 10; i++)
{
    glm::mat4 model = glm::mat4(1.0f);
    model = glm::translate(model, cubePositions[i]);
    float angle = 20.0f * i;
    model = glm::rotate(model, glm::radians(angle),
    glm::vec3(1.0f, 0.3f, 0.5f));
    ourShader.setMat4("model", model);
    glDrawArrays(GL_TRIANGLES, 0, 36);
}

위 코드는 매번 새로운 큐브가 그려질 때 model 행렬을 업데이트를 총 10번한다. 아래의 결과물을 갖는다.

행렬은 매우 강력한 수학적 개념들이다. 처음엔 매우 어려워 보인다. 그렇지만 익숙해지면 매우 유용한 것을 알 수 있다. 몇몇 수학적 지식들에 뛰어들어야하고 이에 더 알아보기 원하면 여러 자료들을 찾아보면 된다.

transformation에 대한 완전한 이해를 위해서 행렬에 관해 얘기하기전에 먼저 벡터에 관해 좀 더 깊이 있게 탐구해야한다. 이 챕터는 후에 나오는 개념들을 이해하기 위해서 기본적인 수학적 개념들을 배운다. 조금 어렵다고 느껴지면 계속해서 이 챕터로 돌아와서 복습하면 된다.

기본적으로 Learn OpenGL의 책을 따라가면서 정리하는데 여기서는 수학적 개념을 설명하기에 여기서 나오는 개념들을 개인적으로 정리한 부분이 크다.

주로 벡터와 행렬, 즉 선형대수학인데 여기서 나오는 부분들만, 순서대로 개인적으로 알아보고 참고한 자료들로 채움.

벡터

공간벡터

행렬

외적 Cross Product

외적은 삼차원 공간에서만 정의된다. 평행하지 않는 두 벡터를 받아서 두 벡터에 수직인 벡터를 산출한다. 만약 두 벡터가 수직이라면 결과로 나오는 벡터 포함하여 모든 벡터가 수직이다.

삼차식의 행렬의 기하학적 정의를 보면 외적에 의미를 조금 쉽게 볼 수 있다. 이차식의 행렬은 평행사변형의 면적이고 삼차식의 행렬은 평행육면체의 부피이다. 부피를 구할 때 한 면과 높이의 곱인데 그 높이를 구하기 위해서 외적의 결과가 필요하다.

• 행렬식의 성질 중에서 행렬을 각각의 벡터로 가지고 그 벡터 중 중복되는 벡터가 있으면 행렬식은 0이된다. 만약 삼차식의 행렬 $M(\vec{a}, \vec{b}, \vec{c})$이 있을 때 그리고 벡터 $\vec{u}$를 $\begin{bmatrix}a_2b_3-a_3b_2 \ a_3b_1-a_1b_3\a_1b_2-a_2b_1\end{bmatrix}$ 로 놓으면(참고로 이게 외적의 결과다.) $\vec{c}$에 $\vec{a}$나 $\vec{b}$를 놓으면 행렬식의 성질에 따라 행렬식은 0이 나온다. 이는 $\vec{u}\cdot \vec{a} = 0$과 $\vec{u}\cdot \vec{b} = 0$으로 나타난다. 이는 벡터 $\vec{u}$가 두 벡터와 직교하고 두 벡터의 평행사변형에 수직이라는 것
• 외적의 성질

항등 행렬(Identity Matrix)

가장 간단한 변환 행렬은 항등 행렬이라고 생각할 수 있다. 항등 행렬은 대각에 있는 성분을 제외하고 0인 NxN 행렬을 말한다.

$\begin{bmatrix}1\ 0\ 0\ 0\ 0\ 1\ 0\ 0\0\ 0\ 1\ 0 \0\ 0\ 0\ 1\end{bmatrix} \cdot \begin{bmatrix}1\2\3 \4\end{bmatrix} = \begin{bmatrix}1 \cdot 1\1 \cdot 2\1 \cdot 3\1 \cdot 4\end{bmatrix} = \begin{bmatrix}1\2\3 \4\end{bmatrix}$

어디서 사용? 항등 행렬은 다른 변환 행렬을 만들기 위한 시작점

추가

• 대칭 이동

  $\begin{bmatrix}1\quad 0\\ 0\ -1\end{bmatrix} \cdot \begin{bmatrix}x\y\end{bmatrix} = \begin{bmatrix}x^\prime \ y^\prime\end{bmatrix}$ x축에 관한 대칭 이동

  $\begin{bmatrix}-1\quad 0\\ 0\ -1\end{bmatrix} \cdot \begin{bmatrix}x\y\end{bmatrix} = \begin{bmatrix}x^\prime \ y^\prime\end{bmatrix}$ 원점에 관한 대칭 이동

  $\begin{bmatrix}-1\quad 0\\ 0\quad 1\end{bmatrix} \cdot \begin{bmatrix}x\y\end{bmatrix} = \begin{bmatrix}x^\prime \ y^\prime\end{bmatrix}$ y축에 관한 대칭 이동

  $\begin{bmatrix}\ 1\ 0\\ 0\ 1\end{bmatrix} \cdot \begin{bmatrix}x\y\end{bmatrix} = \begin{bmatrix}x^\prime \ y^\prime\end{bmatrix}$ y = x 선분에 관한 대칭 이동

Scaling

벡터의 크기를 조정할 때, 원하는 크기의 양만큼 같은 방향을 유지하면서 길이를 증가할 벡터의 크기를 증가시킨다. 이차원이나 삼차원 벡터 둘 중 하나로 작업하므로 이차원이나 삼차원 scaling 변수에 의해 정의할 수 있다.

$\vec{v} = \begin{bmatrix} 3\2 \end{bmatrix}$를 x축으로 0.5, 즉 두 배로 줄이고 y축으로 2, 두배로 늘리면 $\vec{v} = \begin{bmatrix} 1.5\4 \end{bmatrix}$가 된다. OpenGL은 보통 이차원 경우에도 삼차원 공간에서 작동되므로 z축을 1로 둔다. 이러한 연산을 non-uniform scale인데 왜냐하면 각축에 대한 scaling 요소(factors)들이 똑가지 않기 때문. 만약 각축에 대한 스칼라가 같으면 uniform scale이라 부른다.

이제 위의 항등 행렬 1들을 바꾸면 scaling matrix를 만들 수 있다. 마지막은 1은 그냥 둔다.

$\begin{bmatrix}S_1\ 0\ 0\ 0\ 0\ S_2\ 0\ 0\0\ 0\ S_3\ 0 \0\ 0\ 0\ 1\end{bmatrix} \cdot \begin{bmatrix}x\y\z \1\end{bmatrix} = \begin{bmatrix}S_1 \cdot x\S_2 \cdot y\S_3 \cdot z\1 \cdot 1\end{bmatrix} = \begin{bmatrix}S_1\S_2\S_3 \1\end{bmatrix}$

역행렬을 구하는 프로세스를 기하학적으로 간단하게

$\begin{bmatrix}\ \frac{1}{S_1}\ 0\ 0\ 0\ \ 0\ \frac{1}{S_2}\ 0\ 0\ \ 0\ 0\ \frac{1}{S_3}\ 0 \ \ 0\ \ 0\ \ 0\ \ 1\end{bmatrix}$ 이렇게 역행렬을 만들 수 있다.

Translation

Translation은 다른 위치를 가진 새로운 벡터를 반환하기위해 기존 벡터에 다른 벡터를 더하는 과정 translation 벡터를 토대로 벡터를 움직이는 것.

4x4 행렬에 3개의 요소 값을 넣어서 특정 연산을 수행. Translation 벡터를 $(T_x, T_y, T_z)$로 나타내면 translation 행렬을 다음과 같이 정의할 수 있다.

$\begin{bmatrix}1\ 0\ 0\ T_x\ 0\ 1\ 0\ T_y\0\ 0\ 1\ T_z\0\ 0\ 0\ 1\end{bmatrix} \cdot \begin{bmatrix}x\y\z \1\end{bmatrix} = \begin{bmatrix}x+T_x\y+T_y\z+T_z\1\end{bmatrix}$

translation 값들은 벡터의 w열에 의해 곱해지고 벡터의 원래 값에 더해진다. 이는 3x3 행렬에는 불가능.

벡터의 w의 요소는 동차 좌표계(homogeneous coordinate)라 알려져있다. homogeneous 벡터로부터 3차원 벡터를 갖기 위해서 x, y, z를 w 좌표로 나눈다. 보통 w 요소가 1.0이기에 이를 신경쓰지 않음. 동차좌표계를 쓰는 것은 몇 가지 이점이 있다. 삼차원 벡터에서 행렬 translation을 할 수 있고 다음 장에서 w 값을 3D perspective를 생성하기 위해 사용한다. 동차 좌표계가 0이라면 그 벡터가 방향 벡터라는 것을 말해준다. 왜냐하면 0이여서 translation이 불가하기때문이다.

• 이동의 역행렬은 마지막 열의 세가지 원소의 값이 음수면 된다.

Rotation

이번 변환 행렬은 위 항등 행렬과 이동 행렬과는 달리 상대적으로 어렵다.

Khan Academy

Linear Algebra | Khan Academy

벡터의 rotation? 2D나 3D에서 rotation은 angle(각)으로 표현된다. 각은 도나 라디안으로 표현 가능. 여기서는 도로 설명.

라디안에서 도로 변환하는 것은 어렵지 않다.

PI = 3.14159265359
angle_in_degrees = angle_in_radians * (180 / PI)
angle_in_radians = angle_in_degrees * (PI / 180)

반원을 회전하는 것은 180도, 원의 1/5 오른쪽 회전은 72도로 오른쪽으로 회전. 그림은 2차원 벡터 $\vec{k}$에서 1/5 오른쪽으로 회전했을때 $\vec{v}$를 나타낸다. 삼차원에서 회전은 각과 회전축으로 명시된다. 명시된 각은 주어진 회전축을 따라 물체를 회전시킨다. 삼각함수를 사용하여 벡터를 주어진 각에 맞게 새롭게 회전된 벡터들로 변환 가능하다. 회전 변환의 선형성 만족 → 선형 변환 각각의 축에 의한 회전 변환 프로젝션(정사영)도 선형성 만족 → 선형 변환 Projection transformation
회전 변환 행렬 유도 Rodrigues' rotation formula

위의 역행렬은 각만 바꾸면 된다. 따라서 row-major일때는 $\vec{v}R_n$, column-major일 때는 $R_n^T\vec{v}$

위의 변환 행렬은 짐벌락이라는 문제점을 야기시킨다. 자유도 3 → 2로 되는 상황.

Gimbal lock

이 문제점을 예방하기 위해서 사원수(quaternion) 사용하여 회전을 표현해야하는데 이는 더 안전할 뿐만 아니라 컴퓨터 친화적이다. 뒤에서 더 다뤄볼 예정

Combining matrices (Affine Transformation)

여러가지 변환들을 묶어서 사용할 수 있는 것이 변환 행렬 사용의 큰 장점이다. 이제 이러한 수학적 개념을 사용하는데 OpenGL은 행렬과 벡터에 관한 형식을 가지고 있지 않다. 그래서 수학 클래스와 함수를 따로 정의해야한다. 다행히도 OpenGL에 맞춰진, 사용하기 쉬운 수학 라이브러리가 있다.

GLM(OpenGL Mathematics)

GLM은 header-only 라이브러리이다. 이는 헤더만 include만 하면 끝이다. 링킹과 컴파일은 필요하지 않다. glm.g-truc.net/0.9.8/index.html 여기서 다운로드 가능하다. 헤더파일의 루트 디렉토리를 includes 폴더에 복사하여 사용.

• Eigen 이라는 C++로 만들어진 선형대수 라이브러리도 있다.

우리가 필요한 GLM의 기능 대부분은 아래의 3가지 헤더에서 다 찾을 수 있다.

#include <glm/glm.hpp>
#include <glm/gtc/matrix_transform.hpp>
#include <glm/gtc/type_ptr.hpp>

한번 테스트 겸 아래와 같이 코드를 작성해보자.

glm::vec4 vec(1.0f, 0.0f, 0.0f, 1.0f);
glm::mat4 trans = glm::mat4(1.0f);
trans = glm::translate(trans, glm::vec3(1.0f, 1.0f, 0.0f));
vec = trans * vec;
std::cout << vec.x << vec.y << vec.z << std::endl;

위 코드를 살펴보면 GLM built-in 클래스를 사용하여 4차원 벡터를 vec으로 생성, 그 다음 4x4행렬을 1.0f만 입력하여 대각선이 다 1.0으로 초기화되는 항등 행렬을 생성한다. 만약 초기화 값 1.0f를 넣지 않으면 요소들 전부 0인 null 행렬이 된다.

다음은 변환 행렬을 생성하는데 glm::translate함수에 항등 행렬을 전달하고 translation 벡터 값도 함께 전달한다. 그리고 벡터와 변환 행렬을 곱하여 결과물을 출력해보면 210이 나온다.

한번 이전에 만들었던 컨테이너 오브젝트를 한번 크기 조정하고 회전해보자.

glm::mat4 trans = glm::mat4(1.0f);
trans = glm::rotate(trans, glm::radians(90.0f), glm::vec3(0.0, 0.0, 1.0));
trans = glm::scale(trans, glm::vec3(0.5, 0.5, 0.5));

먼저 각 축으로 0.5배 만큼 크기 조정하고 z축으로 90도 회전 시킨다. GLM은 그 각을 라디안으로 받기에 glm::radians함수로 변환해준다. 그리고 이전에 만든 오브젝트는 xy 평면에 있으므로 z축을 회전시킨다. 우리가 회전시키는 축은 단위 벡터이여야하는 것을 명심. X 또는 Y나 Z축으로 회전하는게 아니면 normalize하자.

이제 어떻게 shader로 전달할까? shader도 이전 GLSL에서 공부했듯이 mat4 형이 있다. 따라서 uniform 으로 mat4 형 변수를 만들어서 전달하면 된다.

#version 330 core
layout (location = 0) in vec3 aPos;
layout (location = 1) in vec2 aTexCoord;

out vec2 TexCoord;

uniform mat4 transform;

void main()
{
    gl_Position = transform * vec4(aPos, 1.0f);
    TexCoord = vec2(aTexCoord.x, aTexCoord.y);
}

gl_Position에 uniform 변환 행렬을 벡터와 연산하여 전달한다.

unsigned int transformLoc = glGetUniformLocation(ourShader.ID,"transform");
glUniformMatrix4fv(transformLoc, 1, GL_FALSE, glm::value_ptr(trans));

먼저 uniform 변수의 위치를 묻고 그 다음 glUniform에 Matrix4fv를 접미사를 붙여 사용하여 행렬 데이터를 shader로 보낸다.

첫번째 인자는 데이터를 보낼 uniform 변수의 위치, 두번째는 보낼 행렬의 수. 세번째 인자는 행렬을 전치 행렬로 바꾸길 원하는지에 대한 값을 넣어야한다(column과 row를 바꾸는 것). OpenGL 개발자는 종종 내부 행렬 레이아웃을 사용하며, 이는 column-major 형식이고 GLM에서의 디폴트 행렬 레이아웃이다. 따라서 전치할 필요가 없다. 마지막 매개변수에는 실제 행렬의 데이터를 전달하는데 OpenGL의 원하는 방식에 항상 부합하지 않는 방식으로 GLM은 행렬의 데이터를 저장하므로 데이터를 GLM built-in 함수인 glm::value_ptr함수를 사용하여 변환한다. 사이즈가 두배 작아지고 z축에서 90도로 회전시킨 결과물이 나온다.

여러가지 테스트를 해볼 수 있다. 다시 오브젝트를 우하단쪽으로 위치시키게 한다. 이 오브젝트를 시간이 지나는 것에 따라 회전시키기 위해서 변환 행렬을 렌더링 루프안에서 업데이트해줘야한다. 왜냐하면 각 프레임마다 업데이트해야하기 때문에.

glm::mat4 trans = glm::mat4(1.0f);
trans = glm::translate(trans, glm::vec3(0.5f, -0.5f, 0.0f));
trans = glm::rotate(trans, (float)glfwGetTime(),
glm::vec3(0.0f, 0.0f, 1.0f));

GLFW의 시간 함수를 사용하여 시간의 변화에 따라 회전각도 변하게 한다. 이전 경우에는 변환 행렬을 어디든 선언할 수 있었지만 이같은 경우에는 변환 행렬을 렌더 루프안에서 다시 생성해야한다. 보통 렌더링할 때 각 프레임에 대한 새로운 값을 가지고 재생성된 여러가지 변환 행렬을 가진다.

여기서 처음에 컨테이너 오브젝트를 원점에서 회전시키고 회전된 버전을 우하단으로 이동시킨다. 실제 변환 순서는 반대인 것을 기억하자. 비록 코드에서는 이동시키고 회전하지만 실제 변환은 회전을 먼저 적용하고 이동시킨다. 이러한 모든 복합 변환들의 조합들을 이해하는 것과 어떻게 오브젝트들에 적용되는지 이해하기 어렵다. 위와 같이 우하단에서 계속 회전하는 결과물을 얻을 수 있다. 이동과 회전을 하나의 행렬로 했다. 이는 그래픽스에서 매우 중요한 부분이다. 무한히 많은 양의 변환을 정의할 수 있고 이것들을 원하는 만큼 재사용할 수 있게 하나의 행렬로 결합할 수 있다. 이같은 변환을 vertex shader에서 사용하는 것은 vertex 데이터들을 다시 재정의하는 수고를 덜 수 있으며 처리하는 시간 또한 절약한다. 매번 데이터를 다시 보낼 필요가 없기 때문이다. 해야할 일은 변환 uniform을 업데이트하는 것이다.

참고

• DirectX는 row-major matrix, $\vec{u^\prime} = \vec{u}T$
• HLSL는 column-major matrix, $\vec{u^\prime} = T\vec{u}$

보충 자료 출처

• Khan Academy - Linear Algebra
• Honglabs - 홍정모의 컴퓨터 그래픽스 새싹 코스 Part 2
• 수학 독본

예로 삼각형에 texture를 맵핑하기 위해서 삼각형 각 vertex가 texture의 어느부분과 일치하는지 명시해야한다. 각 vertex는 texture coordinate(텍스쳐 좌표계)를 가져야하는데 이는 texture 이미지의 어떤 부분을 샘플링하는지 연관되어있다. 그 후 fragment interpolation가 나머지 작업을 한다.

texture coordinate의 범위는 x와 y축에서 0부터 1까지이며 texture coordinate을 사용하여 texture 색상을 찾는 것을 샘플링이라고 한다. 텍스쳐 좌표계에서 (0, 0)은 텍스쳐 이미지의 좌하단 모서리이고 (1, 1)은 우상단 모서리이다. 위 그림을 보듯이 세개의 텍스쳐 좌표 지점을 볼 수 있다. 좌측 하단(0, 0), 우측 하단(1, 0), 중앙 상단(0.5, 1)을 텍스쳐 좌표로 사용. 이 세 텍스쳐 좌표만 vertex shader로 보내고 보내진 이 좌표들을 토대로 fragment shader가 각각의 fragment에 관한 텍스쳐 좌표를 보간(interpolate)한다.

float texCoords[] = {
    0.0f, 0.0f, // lower-left corner
    1.0f, 0.0f, // lower-right corner
    0.5f, 1.0f // top-center corner
};

텍스쳐 샘플링은 정밀하지 않은 interpolation을 가지며 다양한 방식으로 된다. 더해서 텍스쳐를 어떻게 샘플링할 것인지 OpenGL에 알려주는 것도 프로그래머의 일이다.

texture wrapping

앞서 말했듯이 텍스쳐 좌표의 범위는 (0, 0) ~ (1, 1)이다. 이를 벗어난다면? OpenGL은 기본적으로 이미지 반복으로 처리한다. 이에 대하여 다양한 옵션들을 제공한다.

• GL_REPEAT: 디폴트 옵션, 이미지 반복
• GL_MIRRORED_REPEAT: 이미지 반복이지만 상이 바뀐다.
• GL_CLAMP_TO_EDGE: 범위를 벗어나면 텍스쳐 좌표의 끝지점이 이어진다.
• GL_CLAMP_TO_BORDER: 범위를 벗어나면 사용자 지정 경계 색상값으로 채워진다. 위의 옵션들은 glTexParameter*함수에서 텍스쳐 좌표계(s, t, p(만약 3D 이미지라면), 이는 x, y, z에 상응)에 맞게 설정된다.

glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_WRAP_S, GL_MIRRORED_REPEAT);
glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_WRAP_T, GL_MIRRORED_REPEAT);

첫번째 인자는 텍스쳐 타겟, 여기서 2D 텍스쳐를 사용하기에 GL_TEXTURE_2D. 두번째는 어느 텍스쳐 축에 적용할 것인지, 여기서 S(X), T(Y) 다 똑같이 설정. 마지막 인자는 어떤 모드로 텍스쳐 렙핑 할 것인지, 여기서 GL_MIRRORED_REPEAT으로 설정. 따라서 위 두 코드는 OpenGL에게 2D 텍스쳐를 사용하여 S, T 축 모두 범위 밖의 처리는 이미지가 상이 바뀌어 반복적으로 채워지게 설정하라는 것.

만약 GL_CLAMP_TO_BORDER로 설정하려면 색상값을 명시해줘야한다. fv를 전달하기에 그에 맞는 glTexParameterfv와 함께 옵션과 float array로 된 색상 값을 입력.

float borderColor[] = { 1.0f, 1.0f, 0.0f, 1.0f };
glTexParameterfv(GL_TEXTURE_2D, GL_TEXTURE_BORDER_COLOR, borderColor);

texture filtering

텍스쳐 좌표계는 해상도와 무관하지만 부동소수점 값일 수도 있다. 게다가 OpenGL은 텍스쳐 좌표에 맞는 맵핑을 위해 어느 텍스쳐 픽셀인지 계산해야한다. texture pixel을 texel이라 알려져있다. 매우 큰 object와 낮은 해상도의 texture를 가진 경우 이는 매우 중요해진다. OpenGL이 texture filtering에 관한 옵션을 가진 것을 예상할 것이며, 몇 가지 옵션들이 있는데 그 중 가장 중요한 것은 GL_LINEAR와 GL_NEAREST이다.

GL_NEAREST(nearest neighbor 또는 point 필터링이라 불러진다)는 OpenGL의 기본 디폴트 텍스쳐 필터링 옵션이다. 이를 설정했을시 OpenGL은 텍스쳐 좌표가 가장 가까운 texel을 선택한다. GL_LINEAR((bi)linear 필터링이라 알려져있다) 는 텍스쳐 좌표의 이웃 texel들로부터 보간된(interpolated) 값을 가진다. texels 간 색상값을 근사치를 낸다. 각 texture filtering 방식의 시각적 효과는? GL_NEARSET는 사각형 패턴의 결과가 나타나면서 픽셀이 잘 보이는반면 GL_LINEAR는 좀 더 부드러운 형태를 나타내면서 픽셀의 경계가 흐릿하다.

texture filtering은 magnifying과 minifying 연산을 설정할 수 있다. 아래와 같이 GL_NEAREST을 축소하고 GL_LINEAR를 확대하는 식으로 함수호출하여 설정 가능하다.

glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_MIN_FILTER, GL_NEAREST);
glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_MAG_FILTER, GL_LINEAR);

Mipmaps

엄청 큰 공간에 수천개의 objects와 각각 texture가 첨가됐다고 가정해보자. 보는 사람에게 가까운 objects처럼 고해상도 texture가 붙은 objects가 멀리 떨어져있을거고 멀리떨어져 있으므로 개수가 조금 적은 fragment을 가지므로 OpenGL은 고해상도 texture로부터 그 fragment에 관한 값을 찾는 것에 대한 어려움을 갖는다. texture의 큰 부분을 범위을 가지는 fragment에 관한 색상값을 골라야하기때문이다. 이는 작은 물체에 관해 굉장히 선명한 인공물 생산하며, 작은 물체에 고해상도의 텍스쳐를 사용함으로 메모리 사용의 낭비는 말할 필요도 없다.

이러한 문제를 해결하기위한 것이 mipmaps이다. mipmaps는 텍스쳐 이미지들을 모아놓은 것인데 그 이미지들은 서로 다른 사이즈를 가진 똑같은 이미지들이다. 각 이미지들은 이전 이미지들의 사이즈 두배 작은 것들이다. OpenGL은 objects의 거리에 따라서 최적의 텍스쳐를 mipmaps에서 찾아 사용할 것이다. 보는 사람으로부터 멀리 떨어진 물체에 조금더 낮은 해상도의 텍스쳐를 사용함으로 이질감을 줄인다. 따라서 OpenGL은 알맞는 texel을 샘플링할 수 있고 mipmap에서 그 부분을 샘플링할 때 더 적은 cache 메모리가 들어간다.

각 텍스쳐 이미지들에 대한 mipmap된 텍스쳐들을 모음을 수동으로 만드는 것은 복잡하다. 운좋게 하나의 함수 호출로 이 일을 할 수 있다. 텍스쳐를 생성한 뒤 glGenerateMipmaps을 호출한다.

렌더링 중 mipmap들에서 texture 스위칭이 일어날 때 OpenGL은 두 mipmap layer 사이에서 더 선명한 모서리들이 보이는 물체를 보여줄 수 있다. 일단 texture filtering과 같이 mipmap 단계 사이에 NEAREST와 LINEAR 옵션을 사용하여 filter를 줄 수 있다.

• GL_NEAREST_ MIPMAP_NEAREST: 픽셀 사이즈에 맞는 nearest mipmap을 가지며 texture 샘플링에 관해서 nearest neighbor interpolation 사용
• GL_LINEAR_MIPMAP_NEAREST: 픽셀 사이즈에 맞는 nearest mipmap을 가지며 texture 샘플링에 관해서 linear interpolation 사용
• GL_NEAREST_MIPMAP_LINEAR: 픽셀 사이즈에 가장 가까운 두 mipmap들을 linear interpolation하며 샘플링에 관해서 nearest neighbor interpolation을 사용
• GL_LINEAR_MIPMAP_LINEAR: 픽셀 사이즈에 가장 가까운 두 mipmap들을 linear interpolation하며 샘플링에 관해서 linear interpolation 사용

glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_MIN_FILTER, GL_LINEAR_MIPMAP_LINEAR);
glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_MAG_FILTER, GL_LINEAR);

흔한 실수 중 하나는 mipmap filtering 옵션에서 magnifying(확대) filter를 하는 것이다. mipmap은 주로 사이즈를 줄이는데 사용되기 때문이다. GL_INVALID_ENUM 에러코드 발생

Loading and creating textures

Texture image는 여러가지 파일 형식으로 저장될 수 있다. 각각 파일형식에 맞는 구조와 데이터 순서가 있다. 그럼 어떻게 애플리케이션으로 가져올 것인가? 하나의 해결책은 하나의 파일형식의 선택하여, 예를들면 .PNG 그리고 그 파일형식을 바이트로 구성된 큰 배열로 변환하는 이미지 로더를 작성한다. 이는 크게 어렵지 않지만 여전히 번거롭다. 그리고 더 다양한 파일형식을 지원하고 싶다면? 각각의 파일형식에 맞는 이미지 로더를 작성해야한다.

또 다른 해결책은 여러 파일 형식을 지원하는 이미지 로딩 라이브러리를 사용하는 것.

std_image.h

std_image.h는 Sean Barrett이 작성한 유명한 단일 헤더 이미지 로딩 라이브러리이다. 다양한 파일 형식의 이미지를 로드할 수 있으며 프로젝트에 쉽게 통합 가능하다. github.com/nothings/stb/blob/master/stb_image.h 에서 다운 받을 수 있다. 간단하게 단일 헤더 파일만 받고 프로젝트에 추가 하면 된다.

#define STB_IMAGE_IMPLEMENTATION
#include "stb_image.h"

STB_IMAGE_IMPLEMENTATION define하는 것은 전처리기가 관련 있는 definition 소스 코드만 가지면서 효과적으로 헤더파일을 cpp파일로 변환하기위해 헤더 파일을 수정한다. std_image.h를 include하고 컴파일 하면 된다.

이미지 로드하기 위해서 std_image.h를 가지고 stbi_load 함수를 사용

int width, height, nrChannels;
unsigned char *data = stbi_load("container.jpg", &width, &height,
                                                                &nrChannels, 0);

함수 첫번째 인자는 이미지 파일 경로, 나머지 인자들은 std_image.h가 이미지의 폭, 높이 그리고 색상 채널 값을 채워줄 정수형 변수들을 넣는데 차후에 width, height, nrChannels을 사용할 예정이다.

Generating a texture

다른 objects들과 마찬가지로 texture도 ID를 받는다.

unsigned int texture;
glGenTextures(1, &texture);

glGenTextures 함수의 첫번째 인자는 얼마나 많은 텍스쳐를 만들고 unsigned int 배열 저장할 것인지 두번째는 그 배열(unsigned int 배열). 다만, 여기서는 하나만 받으니 단일 변수로 처리했다. 다음도 다른 object들처럼 바인딩한다.

glBindTexture(GL_TEXTURE_2D, texture);

텍스쳐가 바인딩이 된 후 이전에 로드된 이미지를 사용하여 텍스쳐를 만들 수 있다. glTexImage2D 함수로 만든다.

glTexImage2D(GL_TEXTURE_2D, 0, GL_RGB, width, height, 0, GL_RGB,
                         GL_UNSIGNED_BYTE, data);
glGenerateMipmap(GL_TEXTURE_2D);

이 함수는 조금 많은 인자들을 가진다.

• 첫번째 인자는 texture target. 현재 바인딩된(bound) texture object에 texture을 만들기에 같은 target이여야한다. 그래서 GL_TEXTURE_2D. GL_TEXTURE_1D나 GL_TEXTURE_3D으로 바인된 texture에는 영향을 주지 않는다.
• 두번째 인자는 mipmap level. 각 mipmap level을 수동으로 설정할지 안할지에 대한 값.
• 세번째 인자는 OpenGL에 그 texture를 어떠한 형식으로 저장할지 알려준다. 여기서 image는 RGB만 가지므로 GL_RGB
• 네번째와 다섯번째 인자는 폭과 높이
• 여섯번째는 항상 ‘0’. (legacy stuff)
• 일곱번째와 여덟번째 인자는 소스 이미지의 데이터 형식(GL_RGB)과 데이터 타입(GL_UNSIGNED_BYTE). 여기서 RGB값을 가진 로드했고 chars(bytes)로 저장했다. 따라서 이 정보를 명시한다.
• 마지막 인자는 실제 이미지 데이터

glTexImage2D가 호출되는 순간 현재 바인딩된 texture object가 텍스쳐 이미지 첨가된채로 가진 상태이다. 그러나 로드한 텍스쳐 이미지의 기초 단계를 가졌을 뿐이며 mipmap 사용을 원한다면 모든 이미지들에 대해서 매뉴얼로 명시하거나 glGenerateMipmap 함수를 texture을 만들어 낸 후에 호출한다. 이는 자동으로 현재 바인딩된 texture에 관한 모든 mipmap을 만들어낸다.

texture와 그에 맞는 mipmap을 만들어낸 후 이미지 메모리를 해제한다.

stbi_image_free(data);

texture를 만들어내는 코드 전체적으로 보면

unsigned int texture;
glGenTextures(1, &texture);
glBindTexture(GL_TEXTURE_2D, texture);
// set the texture wrapping/filtering options (on currently bound texture)
glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_WRAP_S, GL_REPEAT);
glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_WRAP_T, GL_REPEAT);
glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_MIN_FILTER, GL_LINEAR);
glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_MAG_FILTER, GL_LINEAR);
// load and generate the texture
int width, height, nrChannels;
unsigned char *data = stbi_load("container.jpg", &width, &height,
&nrChannels, 0);
if (data)
{
    glTexImage2D(GL_TEXTURE_2D, 0, GL_RGB, width, height, 0, GL_RGB,
    GL_UNSIGNED_BYTE, data);
    glGenerateMipmap(GL_TEXTURE_2D);
}
else
{
    std::cout << "Failed to load texture" << std::endl;
}
stbi_image_free(data);

Applying texture

glDrawElements 함수로 직사각형 그린 vertices에 색상값과 텍스쳐 좌표계를 추가

float vertices[] = {
    // positions      // colors         // texture coords
    0.5f,   0.5f, 0.0f, 1.0f, 0.0f, 0.0f, 1.0f, 1.0f, // top right
    0.5f,  -0.5f, 0.0f, 0.0f, 1.0f, 0.0f, 1.0f, 0.0f, // bottom right
    -0.5f, -0.5f, 0.0f, 0.0f, 0.0f, 1.0f, 0.0f, 0.0f, // bottom left
    -0.5f,  0.5f, 0.0f, 1.0f, 1.0f, 0.0f, 0.0f, 1.0f  // top left
};

이제 vertex attributes를 설정해줘야한다. 아래의 그림과 같이 맞춰야한다.

glVertexAttribPointer(2, 2, GL_FLOAT, GL_FALSE, 8 * sizeof(float),
                                            (void*)(6 * sizeof(float)));
glEnableVertexAttribArray(2);

직사각형에 맞게 맞춘 코드도 8 * sizeof(float)으로 변경하고 아래에 위의 코드를 추가한다.

이제 vertex shader를 아래의 코드와 같이 수정한다.

#version 330 core
layout (location = 0) in vec3 aPos;
layout (location = 1) in vec3 aColor;
layout (location = 2) in vec2 aTexCoord;
out vec3 ourColor;
out vec2 TexCoord;
void main()
{
    gl_Position = vec4(aPos, 1.0);
    ourColor = aColor;
    TexCoord = aTexCoord;
}

이제 fragment shader에 전달해주고 fragment shader가 텍스쳐 오브젝트에 접근해야한다. 어떻게 전달할 것인가? GLSL은 sampler라 불리는 텍스쳐 오브젝트에 관한 빌트인 데이터 타입을 가지고 있다. 이 sampler 타입은 텍스쳐 타입을 접미사로 함수명 뒤에 붙는다. e.g. sampler1D, sampler3D, 여기서는 sampler2D. 나중에 texture를 할당하기 위해 uniform sampler2D로 선언한다.

#version 330 core
out vec4 FragColor;
in vec3 ourColor;
in vec2 TexCoord;
uniform sampler2D ourTexture;
void main()
{
    FragColor = texture(ourTexture, TexCoord);
}

texture의 색상값을 sampling하기 위해서 GLSL의 빌트인 texture 함수를 사용. 첫번째 인자는 texture sampler, 두번째 인자는 상응하는 texture 좌표를 갖는다. texture 함수는 우리가 이전에 설정했던 texture parameter들을 사용하여 상응하는 색상값을 샘플링한다. fragment shader의 output은 보간된(interpolated) 텍스쳐 좌표에서 필터링된(filtered) 텍스쳐 색상값이다.

이제 남은 것은 glDrawElements 함수 이전에 texture를 바인딩하고 자동으로 fragment shader의 sampler에 texture가 할당되는 것.

glBindTexture(GL_TEXTURE_2D, texture);
glBindVertexArray(VAO);
glDrawElements(GL_TRIANGLES, 6, GL_UNSIGNED_INT, 0);

위와 같은 결과물이 나온다.

texture 색상값과 vertex 색상값을 섞을 수 있다. 간단하게 fragment shader에서 texture 색상값의 결과와 vertex 색상값을 곱한다.

FragColor = texture(ourTexture, TexCoord) * vec4(ourColor, 1.0);

그럼 아래와 같은 결과물을 볼 수 있다.

Texture units

위에서 glUniform을 사용하여 값을 할당하는 것도 아닌데 왜 sampler2D가 uniform으로 선언되는지 궁금했을 것이다. glUniform1i을 사용하여 실제로 location 값을 texture sampler에 할당할 수 있고 fragment shader에서 여러 texture들을 한번에 설정할 수 있다. texture의 위치는 texture unit이라고 더 흔하게 말한다. 하나의 texture의 디폴트 texture unit은 0이다. 이는 default active texture unit이다. 그래서 이전에 location을 할당할 필요가 없었다. 주의할 것은 모든 그래픽 드라이버들이 default texture unit을 할당하지 않는다. 바로 전에 했던 예시들이 렌더링 안될 수도 있다.

texture unit의 주 목적은 shader에서 더 많은 texture를 사용하게 해주는 것. texture unit을 sampler에서 할당하는 것으로 그 상응하는 texture unit이 먼저 활성화되는 한 여러 texture들이 한번에 바인딩된다. glBindTexture와 같이 texture unit을 전달받는 glActiveTexture을 사용하여 texture unit들을 활성화할 수 있다.

glActiveTexture(GL_TEXTURE0); // activate texture unit first
glBindTexture(GL_TEXTURE_2D, texture);

texture unit을 활성화한 후 다음 glBindTexture 호출은 현재 활성화된 texture unit에 texture를 바인딩한다. texture unit GL_TEXTURE0은 항상 디폴트로서 활성화되어 있다. 따라서 이전 예시들에서 glBindTexture를 사용할 때 활성화할 필요가 없었다.

OpenGL은 적어도 최저 16개의 texture unit을 사용할 수 있게 한다. 따라서 GL_TEXTURE0부터 GL_TEXTURE15를 사용해서 활성화할 수 있다. 또한 GL_TEXTURE8을 GL_TEXTURE0 + 8로 가질 수 있다. 이는 여러 texture unit을 루프로 가질 때 유용하다.

또 다른 sampler를 가지기 위해서 fragment shader를 수정해본다.

#version 330 core
...
uniform sampler2D texture1;
uniform sampler2D texture2;
void main()
{
    FragColor = mix(texture(texture1, TexCoord),
    texture(texture2, TexCoord), 0.2);
}

최종 색상 값은 texture1과 texture2, 두 텍스쳐가 조합된 색. GLSL의 빌트인 mix함수는 입력의 두 값을 세번째 인자 값을 기본으로하여 선형적으로 보간(linearly interpolate)한다. 세번째 인자 값이 0.0이라면 첫번째 입력된 texture를 반환, 1.0이면 두번째 texture를 반환. 0.2는 첫번째 입력값은 80퍼센트 두번째는 20퍼센트로 두 텍스쳐가 섞여서 결과로 나온다.

이제 또 다른 texture를 생성하자. 먼저 또 다른 texture object 생성, 이미지 로드 그리고 glTexImage2D함수로 texture를 만든다.

unsigned char *data = stbi_load("awesomeface.png", &width, &height,
&nrChannels, 0);
if (data)
{
    glTexImage2D(GL_TEXTURE_2D, 0, GL_RGB, width, height, 0, GL_RGBA,
    GL_UNSIGNED_BYTE, data);
    glGenerateMipmap(GL_TEXTURE_2D);
}

.png 이미지는 alpha값을 가지므로 이미지 데이터 인자로 GL_RGBA를 넣는다.

두번째 texture를 사용하기 위해서 해당하는 texture unit에 두 texture들을 바인딩함으로 렌더링 절차를 조금 바꿔야한다.

glActiveTexture(GL_TEXTURE0);
glBindTexture(GL_TEXTURE_2D, texture1);
glActiveTexture(GL_TEXTURE1);
glBindTexture(GL_TEXTURE_2D, texture2);
glBindVertexArray(VAO);
glDrawElements(GL_TRIANGLES, 6, GL_UNSIGNED_INT, 0);

glUniform1i를 사용하여 어떤 texture unit이 설정된 각 sampler에 각 shader sampler가 속하는지 OpenGL에 알려줘야한다. 이는 한번만 설정하고 render loop전에 할 수 있다.

shader.use(); // don’t forget to activate the shader first!
glUniform1i(glGetUniformLocation(shader.ID, "texture1"), 0); // manually
shader.setInt("texture2", 1); // or with shader class
while(...)
{
    [...]
}

glUniform1i을 통해 sampler들을 설정함으로 각 uniform sampler을 올바른 texture unit에 일치하게 하하면 아래의 결과를 갖는다.

위 아래가 뒤집힌 결과를 갖는데 이는 OpenGL이 y축에서 (0, 0) 좌표가 이미지의 아래쪽으로 인식한다. 이미지는 y축의 제일 위로 (0, 0) 좌표점을 가진다. 다행히도 stb_image.h 는 이미지 로딩 중 y축을 뒤집을 수 있다. 코드는 아래와 같다.

stbi_set_flip_vertically_on_load(true);

아래와 같이 뒤집혀있지 않고 제대로 나타나는 것을 확인할 수 있다.

GLSL

shader들은 C형식의 언어 GLSL로 쓰여졌다. GLSL은 그래픽스 사용에 맞춰져있으며 특히 벡터와 행렬 조작에 특화된 유용한 기능들을 가지고 있다.

shader들은 항상 버전 선언으로 시작 그다음 input, output 변수들, 그리고 uniform들과 main함수가 나온다. 각 shader의 entry point는 main함수이며 이 함수에서 output 변수에 input 변수를 처리한 출력의 결과물을 대입한다.

#version version_number
in type in_variable_name;
in type in_variable_name;
out type out_variable_name;
uniform type uniform_name;
void main()
{
    // process input(s) and do some weird graphics stuff
    ...
    // output processed stuff to output variable
    out_variable_name = weird_stuff_we_processed;
}

이제 vertex shader에 대해 얘기하자면, 각 input 변수는 vertex attribute라 알려져있다. 이 vertex attribute의 최대수는 하드웨어에 정해져있다. OpenGL은 항상 최소 16, 4개의 component vertex attributes를 보장한다. GL_MAX_VERTEX_ATTRIBS로 현재 하드웨어의 최대허용치를 검색할 수 있다.

int nrAttributes;
glGetIntegerv(GL_MAX_VERTEX_ATTRIBS, &nrAttributes);
std::cout << "Maximum nr of vertex attributes supported: " << nrAttributes
<< std::endl;

데이터 타입

GLSL의 대부분의 데이터 타입은 C 형태의 언어의 데이터 타입을 가진다.

• int, float, double, uint 그리고 bool

또한 벡터와 행렬을 사용하는 두 가지 컨테이너 타입을 가지고 있다.

vector

N은 차원을 나타낸다. e.g. 1, 2, 3, 4.

• vecN - the default vector of N floats
• bvenN - a vector of N booleans
• ivecN - a vector of N integers
• uvecN - a vector of N unsigned integers
• dvecN - a vector of N double components

기본 vecN 형식을 가장 많이 사용하며 거의 모든 작업을 하기에 충분하다.

각 component에 접근하는 방식은 ‘.’을 사용한다. e.g. vec.x, vec.y, vec.z, vec.w

• xyzw == rgba(색상) == stpq(texture coordinate, 텍스쳐 좌표계)

벡터 데이터 타입은 swizzling을 통해 component 선택을 할 수 있다.

vec2 someVec;
vec4 differentVec = someVec.xyxx;
vec3 anotherVec = differentVec.zyw;
vec4 otherVec = someVec.xxxx + anotherVec.yxzy;

또한 이 문자들을 조합하여 벡터 타입을 생성시 사용 가능할 수 있다.

vec2 vect = vec2(0.5, 0.7);
vec4 result = vec4(vect, 0.0, 0.0);
vec4 otherResult = vec4(result.xyz, 1.0);

Ins and Outs

GLSL은 in과 out 키워드를 이용하여 각 shader들이 주고 받을 수 있게 정의했다. 각 shader들은 이 키워드로 inputs과 outputs을 명시하고 output 변수와 다음 shader 단계의 input과 매칭되는 변수로 전달할 수 있다.

vertex shader는 input의 몇가지 형식을 받아야한다. 그렇지 않으면 좀 비효율적이다. vertex shader가 input과 다르다면 vertex data로부터 곧장 input을 받는 점이다. vertex data를 어떻게 정리할지 정의하기 위해서 location metadata와 함께 input 변수를 명시하여 CPU에 vertex attributes를 설정할 수 있다. layout(location = 0)처럼 vertex shader는 input에 관한 layout 명시를 요구하며 이는 vertex data와 연결할 수 있다.

layout(location = 0) 을 생략 가능하며 glGetAttribLocation 함수로 attribute location에 관해 OpenGL으로부터 질의하여 답을 구할 수 있다. 다만 이는 더 많은 작업이 요구된다.

또 fragment shader는 vec4 색상 output 변수가 필요하다. 이는 fragment shader가 최종 색상 값을 출력해야기 때문이다. 만약 없다면 그 fragment에 관한 색상 버퍼 출력은 undefined(여기서 검정색이나 하얀색이 그려진다)

하나의 shader로부터 out 키워드로 정의된 변수의 데이터를 다른 shader에서 in 키워드로 정의된 데이터가 보내지는데 두 변수명은 같아야한다.

// vertex shader
#version 330 core
layout (location = 0) in vec3 aPos; // position has attribute position 0
out vec4 vertexColor; // specify a color output to the fragment shader
void main()
{
    gl_Position = vec4(aPos, 1.0); // we give a vec3 to vec4’s constructor
    vertexColor = vec4(0.5, 0.0, 0.0, 1.0); // output variable to dark-red
}

// fragment shader
#version 330 core
out vec4 FragColor;
in vec4 vertexColor; // input variable from vs (same name and type)
void main()
{
    FragColor = vertexColor;
}

코드에서 vertex shader에서 out 키워드로 선언된 vertexColor는 fragment shader에서 in 키워드로 선언된 vertexColor와 연결된다.

result

Uniforms

CPU에 있는 application으로부터 GPU에 있는 shader로 데이터를 전달하는 또 다른 방식. uniform은 vertex attributes와 비교하여 약간의 차이가 있다. 첫번째로 uniforms은 global 변수이다. uniform 변수는 shader 프로그램 전 단계에서 각 shader가 접근 가능하다. 두번째로 uniform 값을 설정하면 그 값이 재설정되거나 업데이트될 때까지 유지된다.

#version 330 core
out vec4 FragColor;
uniform vec4 ourColor; // we set this variable in the OpenGL code.
void main()
{
    FragColor = ourColor;
}

이제 OpenGL 코드에서 어떻게 하는지 보면

float timeValue = glfwGetTime();
float greenValue = (sin(timeValue) / 2.0f) + 0.5f;
int vertexColorLocation = glGetUniformLocation(shaderProgram, "ourColor");
glUseProgram(shaderProgram);
glUniform4f(vertexColorLocation, 0.0f, greenValue, 0.0f, 1.0f);

먼저 glfwGetTime()를 통해서 running time을 찾고 색상 범위는 sin함수를 통해 -1.0 ~ 1.0 사이로 만들고 2.0f로 나누고 0.5f를 더하면 0.0 ~ 1.0사이로 변화를 주고 그 값을 greenValue에 저장한다. glGenUniformLocation 함수를 사용하여 ourColor uniform의 위치를 질의하며 그 위치를 vertexColorLocation에 저장한다. glGenUniformLocation 함수가 -1을 리턴하면 두번째 인자명의 uniform 변수를 찾지 못한 것. 마지막으로 glUniform4f 함수를 통하여 uniform 값을 설정. uniform location을 찾는 것은 shader program을 먼저 사용하는 것을 요구하는게 아니라 uniform을 변경하는 것이 프로그램을 먼저 사용하는 것(glUseProgram 호출)을 요구하는 것. 왜냐하면 이는 현재 활성화된 shader program에서 uniform을 설정하기때문.

OpenGL은 그 내부(core)는 C library이기에 함수 오버로딩 지원을 하지않으므로 OpenGL은 새로운 함수들은 각 타입에 맞게 정의되어있고 그 타입에 맞게 호출되어야한다. glUniform 이 최적의 예시이다. 이 함수는 어떤 타입으로 uniform을 설정할 것인지 함수명에 접미사를 붙여야한다.

• f - float
• i - int
• ui - unsigned int
• 3f - 3 floats; Nf - N floats
• fv - float vector/array

위 코드를 render loop안 glUseProgram와 glBindVertexArray(VAO)사이에 넣으면 삼각형 색이 반복적으로 시간에 따라 초록색에서 점점 검정색으로 되었다가 다시 초록색으로 바뀌는 것을 볼 수 있다.

More attributes

다시 VAO와 VBO를 사용하여 색상값을 설정해보자. 아래와 같이 삼각형의 각 꼭지점을 표현하는 vertices 뒤에 RGB 색상값을 추가.

float vertices[] = {
    // positions // colors
    0.5f, -0.5f, 0.0f, 1.0f, 0.0f, 0.0f, // bottom right
    -0.5f, -0.5f, 0.0f, 0.0f, 1.0f, 0.0f, // bottom left
    0.0f, 0.5f, 0.0f, 0.0f, 0.0f, 1.0f // top
};

이제 vertex shader에 더 많은 데이터를 전달하기때문에 vertex shader를 수정해야한다. 아래의 코드로 수정한다.

#version 330 core
layout (location = 0) in vec3 aPos; // position has attribute position 0
layout (location = 1) in vec3 aColor; // color has attribute position 1
out vec3 ourColor; // output a color to the fragment shader
void main()
{
    gl_Position = vec4(aPos, 1.0);
    ourColor = aColor; // set ourColor to input color from the vertex data
}

layout specifier와 함께 aColor attribute의 location을 설정

아래는 fragment shader로 uniform으로 지정한 변수를 in으로 하여 vertex shader로부터 전달 받는다.

#version 330 core
out vec4 FragColor;
in vec3 ourColor;
void main()
{
    FragColor = vec4(ourColor, 1.0);
}

위와 같이 vertex attribute를 추가하였고 VBO memory를 수정했으므로 vertex attribute pointer를 재설정해야한다. 업데이트된 VBO 메모리는 아래와 같을 것이다. 위와 같이 코드를 수정하면

// position attribute
glVertexAttribPointer(0, 3, GL_FLOAT, GL_FALSE, 6 * sizeof(float),
(void*)0);
glEnableVertexAttribArray(0);
// color attribute
glVertexAttribPointer(1, 3, GL_FLOAT, GL_FALSE, 6 * sizeof(float),
(void*)(3* sizeof(float)));
glEnableVertexAttribArray(1);

달라진 점은 VBO의 vertices에 따라 location이 추가됨에따라 glVertexAttribPointer 함수와 glEnableVertexAttribArray 함수 각각 하나씩 더 추가되었고, 첫번째 glVertexAttribPointer에서 수정한 부분은 5번째 인자의 stride 부분을 수정했다. 위치에 맞게 색상값을 건너뛰게 24바이트로 설정. 두번째 location 1 색상값을 설정하기 위해서 첫번째 인자는 1 그리고 위와 마찬가지로 stride 부분을 24바이트로 설정, 마지막 인자는 offset으로 색상 attribute가 위치 데이터 뒤에 시작하므로 12바이트로 설정.

result

설정해준 부분을 보면 삼각형의 세꼭지점의 지점과 그 지점의 색상값이다. 위 결과물을 보면 세꼭지점에서 중점으로 오면서 색상이 변한다. 이는 fragment shader에서 fragment interpolation으로 불리는 것의 결과다. 실제 삼각형을 렌더링할 때 rasterization 단계에서 원래 명시했던 vertices보다 더 많은 fragment들을 낳는다. rasterizer는 fragment가 삼각형 모양에 속하는 것을 토대로 각각의 fragment의 위치를 결정, 이 위치에 따라서 fragment shader의 input 변수 모두 interpolate(보간)한다.

나머지 부분들은 책에서 나오듯이 shader 클래스를 만들고 메인에서 코드 정리하면된다. 책에서 제공하는 코드도 참고하여 변경하면 된다.

3차원 좌표를 2차원 픽셀로 변환하는 작업은 OpenGL의 그래픽 파이프라인에 의해서 관리된다. 그래픽 파이프라인은 크게 두 파트로 나눌 수 있다. 첫번째는 3차원을 2차원으로 변환하는 것, 두번째는 그 2차원을 실제 색상을 입힌 픽셀로 변환하는 것.

그래픽 파이프라인은 3차원 좌표들로 이루어진 집합을 입력값으로 받고 이를 색상을 입힌 2차원 픽셀로 변환하는 것. 그래픽 파이프라인은 여러 스텝으로 나누어질 수 있는데 각각의 단계에서 입력값으로 이전의 출력값을 요구한다. 이러한 모든 단계들은 각 단계에 맞게 분화되어있고 쉽게 병렬로 처리될 수 있다. 이러한 성질로 오늘날 그래픽 카드는 그래픽 파이프라인 내부에서 빠르게 데이터를 처리하기 위해서 수천개의 작은 프로세싱 코어들을 가진다. 이러한 코어들을 처리하는 것은 파이프라인 각각의 단계에 맞게 GPU에 있는 작은 프로그램을 실행한다. 이런 작은 프로그램들을 shader라 부른다.

현재 사용하는 디폴트 shader를 대체하기 위해서 몇몇 shader들은 개발자들 개인에게 맞는 shader를 작성할 수 있게 환경 설정이 가능하다. 이는 우리에게 파이프라인 특정부분에서 좀더 세세하게 제어할 수 있게 해주며 shader들이 GPU에서 작동하므로 CPU 처리(가장 중요한) 시간을 줄여준다. OpenGL Shading Language(GLSL)로 shader들은 작성되어있다.

그래픽 파이프라인의 전과정을 추상화한 것을 볼 수 있다. 각각의 단계를 간략하게 살펴보자

VERTEX DATA라 불리는 배열 하나의 삼각형 형식으로 되어야하는 세개의 3차원 좌표의 목록을 그래픽 파이프라인의 입력값으로 전달. vertex는 각 3차원 좌표에 해당하는 데이터 모음이다. vertex 데이터는 원하는 어떤 데이터든 담을 수 있는 vertex attribute(속성)을 사용하여 나타낸다. 간단하게 3차원 위치와 색상 값으로 구성되어 있다고 가정하자.

OpenGL이 좌표들의 모음과 색상 값으로 무엇을 만들어낼건지 알기 위해서 OpenGL은 데이터에 맞는 형식으로 어떤 종류의 렌더 타입인지 알려주길 요구한다. 데이터가 점이나 삼각형 또는 긴 선분으로 그려지길 원하는가? 이런 힌트들은 primitives 불리며 그리는 명령어들이 호출되는 중에 OpenGL에 전달된다. 그것들 중에 대표적으로 GL_POINTS, GL_TRIANGLES 그리고 GL_LINE_STRIP이 있다.

파이프라인의 첫 단계인 단일 vertex를 입력값으로 받는 vertex shader이다. 이 vertex shader의 주된 목적은 3차원 좌표를 또다른 3차원로 변환하고 vertex attribute에 몇 가지 기본적인 처리작업을 하게 해준다.

primitive assembly 단계는 주어진 primitive 모양에서 primitive 구성하고 모든 점을 모아 조합하는 vertex shader로부터 모든 vertices를 입력값으로 받거나 GL_POINTS이 선택되어있으면 vertex를 받는다. 여기서는 삼각형 모형.

primitive assembly 단계에서의 출력값은 geometry shader로 전달된다. primitive 형식인 vertices의 모음을 입력값으로 받고 새로운 거나 또 다른 primitive를 구성하기 위해서 새로운 vertices를 냄으로서 다른 모양을 생산할 능력을 가진다. 여기서는 주어진 모양에서 두번째 삼각형을 생성.

geometry shader의 출력값은 rasterization 단계에 전달. rasterization단계에서 결과물이 스크린에 상응하는 픽셀과 맵핑되며 fragment shader를 사용하기 위해 fragment로 된다. fragment shader가 실행되기 전에 clipping이 수행된다. clipping은 성능향상을 위해 view 바깥쪽의 fragment를 폐기한다.

OpenGL에서 하나의 fragment는 OpenGL이 하나의 픽셀을 렌더하기 위해 요구되는 모든 데이터들이다.

fragment shader의 주된 목적은 픽셀의 마지막 색상을 계산하는 것이며 이는 일반적으로 고급 OpenGL 효과들이 일어나는 단계이다. fragment sahder는 일반적으로 (광원, 그림자, 광원색 등과 같은) 마지막으로 색상을 계산하기 위해서 사용하는 3차원 장면에 관한 데이터들을 담고 있다.

상응하는 모든 색상 값들이 정해진 후 마지막 object(물체)가 alpha test와 blending로 불리는 단계를 통해서 전달된다. 이 단계에서 fragment의 depth와 stencil 값이 상응하는지 확인하고 다른 물체보다 앞에 있는지 뒤에 있는지 확인하기 위해서 그 값들을 사용하고 그것들에 맞춰 잘라낸다. 이 단계에서 또 alpha 값을 확인하고 그에 맞게 물체를 blend(조합)한다. fragment shader에서 픽셀 출력값이 계산된다고 하더라도, 마지막 픽셀 색상은 여러 삼각형들이 그려질 때 완전히 다른 어떤 색이 될 수 있다.

이렇듯 그래픽스 파이프라인은 전체적으로 복잡하고 많은 환경설정해야하는 부분들을 포함한다. 그렇지만, 거의 대부분의 경우 vertex, fragment shader 이 두 가지만 작업한다. geometry shader는 옵션이고 보통 디폴트로 놔둔다. 또 tessellation 단계와 변환 피드백 루프가 있지만 나중에 알아본다.

현대 OpenGL은 최소한 vertex shader와 fragment shader를 정의하길 요구된다. 이 이유로 배우기 어렵고 힘들다.

Vertex Input

무엇을 그리기전에 OpenGL에 입력 vertex 데이터를 주어야한다. OpenGL은 3차원 그래픽 라이브러리이며 OpenGL에서 명시한 좌표들은 전부 3차원이다. OpenGL은 간단하게 3차원을 2차원으로 변환하지 않는다. OpenGL은 좌표들이 세 축(x,y,z)에서 -1.0 ~ 1.0 범위안에 있을때만 3차원 좌표들을 처리. 모든 좌표가 normalized device coordinates 범위 안에 있으면 스크린에 나타난다.

단일 삼각형을 그리기 때문에 각 vertex가 3차원 위치를 갖는 세개의 vertices를 다 명시해야한다. float형 배열에 그 vertices를 normalized device coordinates로 정의한다.

float vertices[] = {
            -0.5f, -0.5f, 0.0f,
             0.5f, -0.5f, 0.0f,
             0.0f,  0.5f, 0.0f
};

OpenGL은 3차원 공간에서 작업하므로 각각의 vertex의 z축은 0.0을 가진다.(2차원 삼각형이기때문에)

Normalized Device Coordinates(NDC)

vertex 좌표들이 vertex shader에서 처리되었다면, 그 좌표들은 NDC.

NDC는 glViewport 함수에 건네는 데이터를 사용해서 viewport transform을 통해서 screen-space coordinates로 변환된다. 그 후 screen-space coordinates는 fragment shader의 입력값으로 fragments로 변환된다.

일반적인 스크린 좌표계와는 달리 (0, 0)은 좌상단이 아닌 정중앙.

이 NDC는 glViewport 데이터를 사용하여 viewport transform을 거쳐서 screen-space coordinates로 변형되고 그 결과물은 fragment shader의 입력값으로 fragment로 변형된다.

그래픽 파이프라인의 첫 번째 과정에 입력값으로서 보내려고 정의된 vertex data는 vertex shader이다. 이는 GPU에서 메모리 생성으로부터 끝나는데 이 메모리는 vertex data를 저장하고 어떻게 OpenGL이 메모리를 해석하는지 환경 설정하고 그래픽 카드에 데이터를 어떻게 보낼지 명시하는 곳이다. 그러고 vertex shader는 그 메모리로부터 가능한 많은 vertices을 보낼 수 있게 양을 처리한다.

GPU 메모리에 아주 많은 vertices를 저장할 수 있는 vertex buffer object(VBO)라 불리는 곳을 통하여 메모리 관리. 이러한 버퍼 오브젝트를 사용하는 이점은 데이터를 한꺼번에 크게 묶어서 그래픽카드에 보낼 수 있게 해주며 한번에 하나의 데이터를 보내는 것 없이 메모리가 충분히 남았다면 메모리에서 데이터를 유지할 수 있다. CPU에서 그래픽 카드로 데이터를 보내는 것은 상대적으로 느리다. 그래서 한번에 모아서 보내려고 한다. 그래픽 카드에 데이터가 있자마자 vertex shader는 거의 즉각 vertices에 접근해서 빠르게 처리한다.

다른 object들과 같이 VBO는 버퍼에 상응하는 고유 ID를 가진다. glGenBuffers 함수를 이용해서 buffer ID와 buffer 생성

unsigned int VBO;
glGenBuffers(1, &VBO);

OpenGL은 다양한 타입의 버퍼 오브젝트를 가지고 있으며 VBO의 버퍼 타입은 GL_ARRAY_BUFFER이다. OpenGL은 버퍼들이 서로 다른 타입이라면 한번에 여러 버퍼들을 바인드 할 수 있게 해준다. 새로 생성된 버퍼를 glBindBuffer 함수를 사용해 GL_ARRAY_BUFFER 타겟으로 묶을 수 있다.

glBindBuffer(GL_ARRAY_BUFFER, VBO);
                                    target

GL_ARRAY_BUFFER 타겟에서 버퍼 호출들은 현재 바인드된 버퍼, 즉 VBO를 환경 설정하기 위해 사용될 것. 이후 버퍼 메모리에 이전에 정의된 버퍼들을 복사하는 glBufferData 함수를 호출할 수 있다.

glBufferData(GL_ARRAY_BUFFER, sizeof(vertices), vertices, GL_STATIC_DRAW);

glBufferData 사용자 정의된(user-defined) 데이터를 현재 바인드된(bound) 버퍼에 복사하기 위한 함수. 첫번째 인자는 데이터를 복사할 버퍼의 타입(여기서 GL_ARRAY_BUFFER 타겟에 바인드된 VBO). 두번째는 버퍼로 보낼 데이터의 사이즈, 세번째 인자는 실제 데이터, 네번째 인자는 주어진 데이터를 그래픽 카드가 어떻게 처리할지에 대한 정보, 여기에 3가지 형식이 있다.

GL_STREAM_DRAW: 데이터는 한번만 설정되고 GPU에 의해 많아봐야 몇번 사용되어진다. GL_STATIC_DRAW: 데이터는 변하지 않고 많이 사용된다. GL_DYNAMIC_DRAW: 데이터는 정말 많이 변하고 많이 사용된다.

삼각형의 위치 데이터는 변하지 않으며 많이 사용되고 매번 렌더 호출 있을 때마다 같은 곳에 있기 때문에 이에 맞는 타입은 GL_STATIC_DRAW이다. 만약 예를들어 자주바뀌는 데이터를 가진 버퍼를 가진다면 GL_DYNAMIC_DRAW 타입의 사용이 그래픽 카드가 더 빠른 작업을 하게 메모리에 데이터를 놓아두게 해준다.

Vertex shader

Vertex shader는 사용자가 프로그래밍 가능한 shader 중 하나. 현대 OpenGL은 최소한 vertex, fragment shader 설정하는 것을 요구.

GLSL shader 언어에서 vertex shader 작성이 첫번째 해야할 일이고 그리고 난 뒤 이 shader를 컴파일해서 사용할 애플리케이션에 적용.

#version 330 core
layout (location = 0) in vec3 aPos;

void main()
{
    gl_Position = vec4(aPos.x, aPos.y, aPos.z, 1.0);
}

위 코드를 보면 알겠지만 C와 굉장히 비슷하다. 각 shader들은 처음에 그 version을 선언. GLSL 버전과 OpenGL 버전과 매치해야한다(420이면 OpenGL 4.2). 또한 core profile 기능을 사용할거라고 명시.

다음은 vertex shader에 vertex 속성을 ‘in’이라는 키워드와 함께 입력값을 선언한다. 현재 위치 데이터만 신경쓰므로 단일 vertex attribute만 필요. GLSL는 postfix digit을 기반으로 1 ~ 4개의 float형을 담고 있는 벡터 데이터 타입을 가진다. 각각의 vertex는 3차원 좌표값을 가지고 있기에 aPos 명으로 vec3 변수를 생성. layout (location = 0)을 통해 입력 변수의 위치를 특정해서 설정한다. 이는 왜 필요한지 나중에 알아갈 것

컴퓨터 그래픽스에서의 Vector - 수학적 개념으로 많이 사용. 이는 점/위치 개념으로 사용하고 유용한 수학적 성질을 가진다. GLSL에서 벡터의 최대 사이즈는 4이며 각각의 값에 검색/접근은 vec.x, vec.y, vec.z 그리고 vec.w이다. vec.w의 성분은 공간의 위치 개념이 아닌 원근법을 나타낸다.

vertex shader의 출력값을 설정하기위해 미리 정의된 gl_Position(vec4) 변수에 위치 데이터를 할당해야한다. 메인 함수 끝에 gl_Position에 설정하는 어떤 값이든 vertex shader의 출력값으로 사용되어질 것. 여기서 사용되는 벡터의 크기는 vec3라서 vec4로 형변환을 해야한다. w 성분값에 1.0f를 넣는다.

위 예시는 가장 간단한 케이스다. 실제 응용 프로그램의 데이터들은 Normalized Device Coordinates가 안된 상태이기에 OpenGL 영역에 맞는 좌표로 변환해줘야한다.

Compiling a shader

먼저 const C string을 코드 최상단에 놓고 저장

const char *vertexShaderSource = "#version 330 core\n"
    "layout (location = 0) in vec3 aPos;\n"
    "void main()\n"
    "{\n"
    " gl_Position = vec4(aPos.x, aPos.y, aPos.z, 1.0);\n"
    "}\0";

OpenGL이 shader를 사용할 수 있게 소스코드로부터 실행시간에 동적으로 컴파일해야 한다. 첫번째는 ID에 의해서 참조되게 shader object 생성. 그래서 vertexShader를 unsinged int로 선언하고 glCreateShader로 shader 생성.

unsigned int vertexShader;
vertexShader = glCreateShader(GL_VERTEX_SHADER);

glCreateShader의 인자로 원하는 shader type을 전달한다. vertex shader를 필요하니 GL_VERTEX_SHADER를 전달한다.

glShaderSource(vertexShader, 1, &vertexShaderSource, NULL);
glCompileShader(vertexShader);

glShaderSource 함수는 컴파일 할 shader object를 첫번째 인자로 받고 두번째는 전달하는 소스코드가 얼마나 많은 문자열(string)이 있는지 명시. 세번째는 vertex shader의 실제 코드를 인자값으로 받는다. 여기서 네번째 인자는 NULL이다.

glCompileShader 함수가 성공적으로 확인하기 원하면 컴파일 때 에러 체크를 하기위해서 아래와 같이 작성

int success;
char infoLog[512];
glGetShaderiv(vertexShader, GL_COMPILE_STATUS, &success);

glGetShaderiv 함수를 이용해서 컴파일이 성공적인지 확인할 수 있다. 실패하면 success 변수에 0이 할당되고 아래와 같이 분기문을 만들어 그 분기문 안으로 들어가게 하여 glGetShaderInfoLog 함수를 호출하여 infoLog를 매개 변수로 전달하여 에러 메시지를 담는다.

if(!success)
{
    glGetShaderInfoLog(vertexShader, 512, NULL, infoLog);
    std::cout << "ERROR::SHADER::VERTEX::COMPILATION_FAILED\n" <<
    infoLog << std::endl;
}

Fragment shader

Fragment shader는 픽셀의 섹상 출력값을 계산한다. 여기서는 오렌지 계열 색상 이용

컴퓨터 그래픽스에서 색은 4개의 값으로된 배열을 표현. RGBA(빨강, 초록, 파랑, 투명도 / Red, Green, Blue, Alpha)로 나타낸다. OpenGL 또는 GLSL에서 색을 정의할 때, 성분의 값을 0.0에서 1.0 사이의 값으로 설정. 주어진 색상 3가지 성분으로 1600만개의 다른 색을 표현 수 있다.

#version 330 core
out vec4 FragColor;

void main()
{
    FragColor = vec4(1.0f, 0.5f, 0.2f, 1.0f);
}

여기에서 fragment shader는 vec4로 최종 색상값이 정의된 하나의 출력 변수만 요구. ‘out’ 키워드와 함께 출력 변수 FragColor 선언. 그리고 그 변수에 vec4의 색상값 할당.

fragment shader를 컴파일하는 과정은 shader type으로 GL_FRAGMENT_SHADER인 거 말고는 vertex shader와 비슷하다.

unsigned int fragmentShader;
fragmentShader = glCreateShader(GL_FRAGMENT_SHADER);
glShaderSource(fragmentShader, 1, &fragmentShaderSource, NULL);
glCompileShader(fragmentShader);

Shader program

Shader program object는 결합된 여러 shader들의 최종 링크된 버전. 현재 컴파일된 shader들을 사용하기 위해서 shader program object에 링크해야하고 object들을 렌더링할 때 shader program을 활성화해야한다. 활성화된 shader program의 shader들은 렌더 호출이 일어날 때 사용될 것.

shader들을 프로그램으로 연결시킬 때 각각의 shader의 출력값들을 다음 shader에 연결한다. 여기서 또한 입력물과 출력물의 매칭이 잘못되면 에러.

unsigned int shaderProgram;
shaderProgram = glCreateProgram();

glCreateProgram 함수는 program을 생성하고 새로 생성된 program object의 ID 참조값을 리턴한다. glLinkProgram 함수를 사용하여 이전에 컴파일된 shader들을 program object에 붙이고 그것들을 연결한다.

glAttachShader(shaderProgram, vertexShader);
glAttachShader(shaderProgram, fragmentShader);
glLinkProgram(shaderProgram);

새로 생성된 program object를 인자로 받아서 glUseProgram 함수를 호출함으로써 program object를 활성화 할 수 있다.

glUseProgram(shaderProgram);

glUseProgram 이후 모든 쉐이더와 렌더링 호출은 이 프로그램 객체를 사용할 예정.

shader들을 program object에 링크한 이후 shader object들을 삭제해야한다.

glDeleteShader(vertexShader);
glDeleteShader(fragmentShader);

현재 입력 vertex 데이터를 GPU로 보냈고 vertex, fragment shader 안에 있는 vertex 데이터들을 어떻게 처리해야하는지 GPU에 알려줬다.

아직 OpenGL은 메모리에 있는 vertex 데이터를 어떻게 해석하는지 모르고 어떻게 vertex 데이터를 shader attribute와 연결하는지 모른다.

Linking vertex attributes

vertex shader는 어느 입력값이든 vertex attribute의 형식에 맞게 명시할 수 있게 해준다. 이는 더 나은 유연성을 주지만 수동으로 vertex shader에서 어느 vertex attribute로 입력 데이터의 어떤 부분이 가는지 명시해야한다는 것. 이는 OpenGL에게 렌더링 전에 어떻게 입력 데이터를 해석해야하는지 명시하는 것. vertex buffer data는 위와 같이 구성되어있다.

• 위치 데이터는 32-bit float 값으로 저장
• 각각의 위치는 세개의 값으로 구성
• 세가지 값 사이 공간이나 다른 값은 없다. 배열이 값들로 꽉 채워져있다.
• 첫번째 값은 버퍼의 시작점이다.

glVertexAttribPointer 함수로 OpenGL에게 vertex 데이터를 어떻게 해석해야하는지 알려준다.

glVertexAttribPointer(0, 3, GL_FLOAT, GL_FALSE, 3 * sizeof(float),(void*)0);
glEnableVertexAttribArray(0);

glVertexAttribPointer 함수는 조금 많은 인자를 가진다.

• 첫번째는 어떤 vertex attribute를 환경 설정 원하는지 명시. vertex shader에서 layout (location = 0)와 position vertex attribute의 location을 명시한 걸 기억. 이는 vertex attribute의 position을 0으로 설정했고 이 vertex attribute에 데이터를 보내길 원하기 때문에 0을 전달한다.

• 두번째는 vertex attribute의 크기를 명시. 여기서 vertex attribute는 vec3이기에 세개의 값으로 구성

• 세번째는 데이터 형식을 명시. GLSL에서 vec*은 float형으로 되어있다.

• 네번째는 정규화가 되어있는지 아닌지 명시. 만약에 integer 형의 데이터 타입을 넣는다면, GL_TRUE를 설정. 정수형 데이터는 float형으로 변환될 때 0(또는 부호가 있을 때 -1)과 1로 normalized 되어있다. 여기서는 GL_FALSE.

• 다섯번째 인자는 stride로 연속적인 vertex attribute들의 간의 크기를 말한다. 다음 위치 데이터의 설정은 정확히 stride로 값을 명시한 것처럼 float형의 3배 크기만큼 떨어져 있다. 배열이 꽉꽉 채워있기때문에(vertex attribute 간의 빈 공간이 없으므로) stride를 0으로 주어 OpenGL이 stride를 알아낼 수 있게 할 수 있다(vertex attribute 간 빈 공간이 없을 경우). vertex attribute가 더 많아질 수록 신경써서 그 간격의 공간을 정의

• 마지막 인자는 void*(보이드 포인터)형으로 버퍼에서 위치 데이터가 시작하는 곳의 offset. 여기서 배열의 데이터가 시작하는 점이 위치 데이터이므로 값 0이 전달.

  각각의 vertex attribute는 VBO에 의해 관리되는 메모리로부터 자기의 데이터를 가져오고 VBO가 그 데이터를 어디서 가져오는지는 glVertexAttribPointer 함수 호출시 현재 GL_ARRAY_BUFFER와 묶인(bound) VBO에 의해 결정. 이전에 정의된 VBO는 계속 glVertexAttribPointer 호출전에 묶여(bound)있기에 vertex attribute 0은 그 vertex 데이터와 관련있다.

이제 OpenGL에게 vertex data를 어떻게 해석해야하는지 명시했고 vertex attribute location을 인자로 받는 glEnableVertexAttribArray 함수 활성화?해야한다. (OpenGL이 vertex attribute array에 접근 가능하게 하는 건지 vertex attribute array가 뭘 할 수 있게 하는지 잘 모르겠음). vertex attribute는 디폴트로 disable이다. 이점으로부터 모든게 준비되었다. → vertex buffer object 사용할 버퍼에 vertex data를 초기화, vertex와 fragment 쉐이더 설정과 OpenGL에 vertex shader의 vertex attribute에 vertex data를 어떻게 연결하는지 알려줬다. OpenGL에서 하나의 object를 그리는 것은 아래와 같다.

// 0. copy our vertices array in a buffer for OpenGL to use
glBindBuffer(GL_ARRAY_BUFFER, VBO);
glBufferData(GL_ARRAY_BUFFER, sizeof(vertices), vertices, GL_STATIC_DRAW);
// 1. then set the vertex attributes pointers
glVertexAttribPointer(0, 3, GL_FLOAT, GL_FALSE, 3 * sizeof(float),
(void*)0);
glEnableVertexAttribArray(0);
// 2. use our shader program when we want to render an object
glUseProgram(shaderProgram);
// 3. now draw the object
someOpenGLFunctionThatDrawsOurTriangle();

object를 그릴 때마다 위와 같은 프로세스가 반복해야한다. 만약 수백개의 object를 위와 같이 해야한다면? 적절한 buffer object를 바인딩하고 각각의 object에 관한 vertex attribute를 설정하는 것은 굉장히 벅차고 힘든 일이된다. 이러한 모든 설정들을 하나의 object(객체)에 저장하고 그 상태를 되찾기 위해 그 object를 간단히 바인딩하는 방법이 있다면?

Vertex array object

vertex array object(VAO)는 VBO와 같이 묶여(bind)질 수 있고 차후 vertex attribute는 VAO안에 저장될 지점으로부터 호출. 이는 vertex attribute pointer들을 설정할 때 그러한 호출을 한번에 만들어주게 하고 object를 그리기 원할 때마다 그에 상응하는 VAO로 bind할 수 있다. 다른 VAO를 바인딩하는 거 만큼 쉽게 다른 vertex data와 attribute 설정 사이를 전환하게 만든다. 설정한 모든 상태(state)는 VAO안에 저장된다.

Core OpenGL은 VAO를 사용하여 vertex 입력값과 어떻게 할 것을 알려주는 것을 요구. VAO bind가 실패했을 때 OpenGL은 그리는 것을 거절할 것.

VAO는 다음을 저장

• glEnableVertexAttribArray 또는 glDisableVertexAttribArray 호출
• glVertexAttribPointer을 통한 vertex attribute 환경 설정
• glVertexAttribPointer 호출에 의한 vertex attribute들과 연관된 Vertex buffer objects VAO를 생성하는 것은 VBO를 생성하는 것과 비슷하다.

unsigned int VAO;
glGenVertexArrays(1, &VAO);

VAO를 사용하기 위해서 해야할 것은 glBindVertexArray 사용하여 VAO를 binding하는 것. 이지점으로부터 상응하는 VBO와 attribute pointer를 bind와 configure해야하고 그런 뒤에 나중에 사용을 위해서 VAO를 unbind한다. object를 그릴때 그전에 정해놓은 설정과 VAO를 간단하게 bind한다.

// ..:: Initialization code (done once (unless your object frequently changes)) :: ..

// 1. bind Vertex Array Object
glBindVertexArray(VAO);
// 2. copy our vertices array in a buffer for OpenGL to use
glBindBuffer(GL_ARRAY_BUFFER, VBO);
glBufferData(GL_ARRAY_BUFFER, sizeof(vertices), vertices, GL_STATIC_DRAW);
// 3. then set our vertex attributes pointers
glVertexAttribPointer(0, 3, GL_FLOAT, GL_FALSE, 3 * sizeof(float),
(void*)0);
glEnableVertexAttribArray(0);
[...]
// ..:: Drawing code (in render loop) :: ..
// 4. draw the object
glUseProgram(shaderProgram);
glBindVertexArray(VAO);
someOpenGLFunctionThatDrawsOurTriangle();

다음 내용들 모두 이지점으로부터 이끌어진다. VAO는 vertex attribute 설정과 어떤 VBO을 사용할지 저장되어있다. 보통 여러 object들을 그릴 때 먼저 모든 VAO를 생성, 설정하고 저장. 여러 object들 중 하나를 그리는 순간 그에 상응하는 VAO를 바인드하고 그리고 언바인드한다.

선택한 오브젝트를 그리기위해 OpenGL은 glDrawArrays 함수를 제공한다. 이 함수는 현재 활성화된 shader, 이전에 정의된 vertex attributes 설정과 VAO를 통해 간접적으로 바인딩된 VBO의 vertex를 사용하여 primitives를 그린다.

glUseProgram(shaderProgram);
glBindVertexArray(VAO);
glDrawArrays(GL_TRIANGLES, 0, 3);

glDrawArrays 함수는 첫번째 인자로 primitive type을 두번짼는 vertex array의 시작 index 마지막 세번째는 얼마나 많은 vertex(vertices)를 그릴 것인지 전달

Element Buffer Objects

EBO(element buffer objects) 이 어떻게 동작하는지는 예를 통해서 보는게 좋다.

직사각형을 그린다고 하자 → 삼각형 두 개를 사용하여 그릴 수 있다. (OpenGL은 주로 삼각형을 대상으로 한다.) 그래서 두 vertex(vertices)를 만들어보면

float vertices[] = {
    // first triangle
    0.5f, 0.5f, 0.0f, // top right
    0.5f, -0.5f, 0.0f, // bottom right
    -0.5f, 0.5f, 0.0f, // top left
    // second triangle
    0.5f, -0.5f, 0.0f, // bottom right
    -0.5f, -0.5f, 0.0f, // bottom left
    -0.5f, 0.5f, 0.0f // top left
};

여기서 bottom right와 top left는 겹친다. 4개의 정점만 있으면 만들어지는 직사각형이기때문에 이는 50퍼센트의 오버헤드다. 이는 더 복잡하고 큰 오브젝트를 그릴때 더 큰 오버헤드, 즉 겹치는 부분들이 무수히 많을 것이다. 그럼 어떻게 해야할까?

OpenGL은 이에 대한 해결책으로 EBO 제공, 이는 vertex buffer object와 같은 버퍼이며 OpenGL이 어떤 vertices를 그릴지 결정하기 위해 사용하는 indices를 저장하는 버퍼. 이는 indexed drawing이라 불리며 위에 언급된 문제를 정확하게 해결

float vertices[] = {
    0.5f, 0.5f, 0.0f, // top right
    0.5f, -0.5f, 0.0f, // bottom right
    -0.5f, -0.5f, 0.0f, // bottom left
    -0.5f, 0.5f, 0.0f // top left
};
unsigned int indices[] = { // note that we start from 0!
    0, 1, 3, // first triangle
    1, 2, 3 // second triangle
};

vertices가 6개에서 4개로 줄었고 indices가 추가. 이 후 EBO 생성

unsigned int EBO;
glGenBuffers(1, &EBO);

VBO와 비슷하게 EBO도 바인드하고 glBufferData로 버퍼에 indices를 복사. GL_ELEMENT_ARRAY_BUFFER을 버퍼 타입으로 명시

glBindBuffer(GL_ELEMENT_ARRAY_BUFFER, EBO);
glBufferData(GL_ELEMENT_ARRAY_BUFFER, sizeof(indices), indices,
GL_STATIC_DRAW);

그리고 glDrawArrays 대신 glDrawElements 을 호출. 이는 현재 바인딩된 EBO에서 제공된 indices를 사용하여 그린다.

glBindBuffer(GL_ELEMENT_ARRAY_BUFFER, EBO);
glDrawElements(GL_TRIANGLES, 6, GL_UNSIGNED_INT, 0);

glDrawArrays 와 같이 첫번째 인자는 그리는 형식, 두번째는 elements의 수, 세번째는 indices의 타입, 마지막은 EBO에서 offset을 명시. 이 함수는 현재 GL_ELEMENT_ARRAY_BUFFER 에 바인딩된 EBO로부터 indices를 가진다. 이는 복잡하고 큰 indices를 가진 오브젝트를 렌더링할때마다 상응하는 EBO를 바인딩해야하는 것. VAO가 EBO 바인딩들을 계속 찾아가게 만든다. VAO는 타겟이 GL_ELEMENT_ARRAY_BUFFER 이라면 glBindBuffer 호출을 저장. 이는 또한 unbind 함수도 저장하기에 VAO를 unbind하기전에 element array buffer를 unbind해서는 안되는 것. 그렇지 않으면 설정된 EBO를 가지지 못한다.

// ..:: Initialization code :: ..
// 1. bind Vertex Array Object
glBindVertexArray(VAO);
// 2. copy our vertices array in a vertex buffer for OpenGL to use
glBindBuffer(GL_ARRAY_BUFFER, VBO);
glBufferData(GL_ARRAY_BUFFER, sizeof(vertices), vertices, GL_STATIC_DRAW);
// 3. copy our index array in a element buffer for OpenGL to use
glBindBuffer(GL_ELEMENT_ARRAY_BUFFER, EBO);
glBufferData(GL_ELEMENT_ARRAY_BUFFER, sizeof(indices), indices,
GL_STATIC_DRAW);
// 4. then set the vertex attributes pointers
glVertexAttribPointer(0, 3, GL_FLOAT, GL_FALSE, 3 * sizeof(float),
(void*)0);
glEnableVertexAttribArray(0);
[...]
// ..:: Drawing code (in render loop) :: ..
glUseProgram(shaderProgram);
glBindVertexArray(VAO);
glDrawElements(GL_TRIANGLES, 6, GL_UNSIGNED_INT, 0);
glBindVertexArray(0);

아래와 같은 결과물들을 얻을 수 있다. 두번째 결과물은 wireframe mode에서 나온 것. 아래의 코드를 render loop안에 추가하면 확인 가능.

// render loop
glPolygonMode(GL_FRONT_AND_BACK, GL_LINE);

함수 첫번째 인자는 삼각형의 전면과 후면에 적용하는 플래그를 입력, 두번째는 선으로 나타내는 플래그 입력

std::array

// 전달 받는 배열의 크기 고정
void print(std::array<int, 5> arr)
{
    for (auto& e : arr)
        std::cout << e << " ";
    std::cout << std::endl;
}

// 깊은 복사 X, 범용적인 배열의 출력 가능
template<size_t N>
void print(const std::array<int, N>& arr)
{
    for (auto& e : arr)
        std::cout << e << " ";
    std::cout << std::endl;
}

참고 사이트 :

1. https://en.cppreference.com/w/cpp/language/template_parameters
2. https://en.cppreference.com/w/cpp/language/parameter_pack

빠르고 범용적인 데이터 저장 컨테이너 만드는 방식

// template<typename ... Args>
// std::array<?, ?> build_array(Args&& ... args)

// template<typename ... Args>
// auto build_array(Args&& ... args) -> std::array<typename std::common_type<Args...>::type, ?>
// {
//     using commonType = typename std::common_type<Args...>::type;
//     // 배열 생성
// }

template<typename ... Args>
auto build_array(Args&&... args) -> std::array<typename std::common_type<Args...>::type, sizeof...(args)>
{
    using commonType = typename std::common_type<Args...>::type;
    return {std::forward<commonType>((Args&&)args)...};
}

int main()
{
    auto data = build_array(1, 0u, 'a', 3.2f, false);
    // auto data2 = build_array(1, "Packt", 2.0); error, there's no common type.

    for (auto& e : data)
        std::cout << e << " ";
    std::cout << std::endl;
}

<type_traits> std::common_type std::forward

std::array는 C 스타일 배열의 발전된 형태. 다만, 실제 개발에서 불편한 점이 있다.

• std::array의 크기는 컴파일 시간에 결정되는 상수이어야한다. 실행 중 변경 x
• 크기가 고정되어 있어서 원소를 추가하거나 삭제 x
• std::array의 메모리 할당 방법을 변경할 수 없다. 항상 스택 메모리 사용

대부분 실제 응용 프로그램에서 데이터는 동적. 데이터의 크기를 미리 알고 있으면 std::array가 좋다.
std::vector

std::vector는 C 스타일 배열과 std::array의 고정 크기 문제 보완.

std::vector<int> vec;               // 크기가 0인 벡터 선언
std::vector<int> vec = {1,2,3,4,5}; // 지정한 초깃값으로 이루어진 크기가 5인 벡터 선언
std::vector<int> vec(10);           // 크기가 10인 벡터 선언
std::vector<int> vec(10, 5);        // 크기가 10이고, 모든 원소의 값이 5로 초기화하는 벡터 선언

push_back()함수

push_back(val)
    if size < capacity
        마지막 원소 뒤에 val 저장
        size + 1
    else (size == capacity)
        메모리 두 배로 새로 할당
        기존 원소들 복사
        데이터 포인터에 새로 할당한 메모리 주소로 지정
        마지막 원소 다음 val 저장
        size + 1

공간이 남아 있을 때 삽입 시 시간 복잡도는 O(1)이며, 공간이 없을 때 O(n)의 시간이 걸리지만 두 배를 늘리는 경우가 많지 않다. 따라서 연산의 평균 속도는 O(1)에 가깝다. 참고로 +2씩 늘리는 경우 O(n^2)의 속도를 갖는다.

$\sum_{k=1}^{r}2\cdot k = 2\cdot ({r(r+1)}/2) = r^2 + r = (\frac{n}{2})^2 + \frac{n}{2} = O(n^2)$

$\sum_{k=1}^{r}2^k = 2\cdot (2^r-1) = 2\cdot (2^{\log(n)}-1) = 2(n-1) = O(n),;Avg;O(n) / n==O(1)$

위 두 테이블과 수식은 +2씩 증가하는 경우와 두 배로 증가하는 경우의 시간을 나타낸다.

insert()의 경우 위치 다음의 모든 원소를 이동시켜야하는 연산이 필요. 따라서 $O(n)$의 시간이 걸린다. push_front()는 없다. vec.insert(vec.begin(), 0);로 대체 가능.

push_back() 과 insert()의 단점은 이 두 함수가 추가할 원소를 먼저 임시로 생성한 후, 벡터 버퍼 내부 위치로 복사 또는 이동을 수행한다는 점. 이 단점을 새로운 원소가 추가될 위치에서 해당 원소를 생성하는 방식으로 최적화하는 기능은 emplace_back() 또는 emplace() 함수에 구현되어있다. 몇가지 vector 멤버 함수들

vec.pop_back() // O(1)
// erase() 함수는 O(n)
vec.erase(vec.begin()); // 맨 처음 원소 제거
vec.erase(vec.begin() + 1, vec.begin() + 4); // 1번째 원소부터 4번째 원소 '앞'까지 제거
vec.clear(); // 모든 원소 제거
vec.reserve(capacity); // 벡터에서 사용할 용량을 지정. 지정한 값이 현재 용량보다 크면 크기만큼 재할당, 같거나 작으면 작동 x
vec.shrink_to_fit(); // size == capacity, 벡터의 용량과 크기를 같게 설정

std::vector할당자 std::vector는 template parameter에서 데이터 타입 다음에 할당자(allocator)를 전달할 수 있다. std::array의 단점 해결. 사용자 정의 할당자를 사용하려면 정해진 인터페이스를 따라야한다. 벡터는 메모리 접근과 관련된 대부분의 동작에서 할당자 함수를 사용하므로 할당자는 allocator(), deallocate(), construct(), destroy()등의 함수를 제공해야한다. 할당자는 메모리 할당과 해제, 그리고 여타 동작에서 데이터를 손상시키지 않도록 주의해야 한다. 일반적인 heap 메모리 대신 자체적인 메모리 풀(memory pool) 또는 이와 유사한 자원을 사용하거나 자동 메모리 관리가 필요한 응용 프로그램을 만들어야하는 경우에 사용자 정의 할당자를 사용하면 유용. 참고 사이트 : https://en.cppreference.com/w/cpp/named_req/Allocator
std::forward_list 연결 리스트와같은 형태의 자료 구조. 연결 리스트 구현이 어렵지 않지만 자칫 잘못하면 찾기 어려운 버그를 양산. 따라서 C++는 기본적인 연결 리스트에 대한 래퍼 클래스인 std::forward_list 클래스 제공. std::forward_list는 기본적인 연결 리스트의 성능을 유지하면서 추가적인 기능을 제공. 성능 유지를 위해 std::forward_list는 전체 리스트의 크기를 반환하거나 또는 첫 번째 원소를 제외한 나머지 원소에 직접 접근하는 기능을 제공하지 않는다. 원소 삽입과 삭제는 배열, vector와는 조금 다르게 동작. push_front() 함수로 연결 리스트 맨 앞에 새로운 원소 삽입하거나 insert_after() 함수를 사용. 배열같이 중간에 삽입하고 그 뒤 나머지 원소를 복사하는 과정이라면 리스트는 연결만 제대로 해주면 끝이다.

std::forward_list<int> fwd_list = {1,2,3};
fwd_list.push_front(0);       // {0,1,2,3};
auto it = fwd_list.begin();
fwd_list.insert_after(it, 5); // {0,5,1,2,3}
fwd_list.insert_after(it, 6); // {0,6,5,1,2,3}

std::vector와 유사하게 emplace_front()와 emplace_after() 함수 제공. 삽입 함수와 같은 기능을 수행하지만 추가적인 복사나 이동을 하지 않아 더 효율적. 삭제같은 경우도 pop_front(), erase_after()와 같인 std::vector와 비슷.

std::forward_list<int> fwd_list = {1,2,3,4,5};
fwd_list.pop_front();                     // {2,3,4,5}
auto it = fwd_list.begin();
fwd_list.erase_after(it);                 // {2,4,5}
fwd_list.erase_after(it, fwd_list.end()); // {2}

기타 멤버 함수로 remove()와 remove_if() 함수도 제공. remove()함수는 삭제할 원소 값 하나를 인자로 받아서 이 매개변수와 같은 값과 일치하는 모든 원소를 찾아 삭제. 오직 등호 연산만으로 찾아내고 등호 연산이 지원되지 않는 타입이면 에러. 좀 더 유연한 remove_if()를 통해서 조건자 하나를 받아 조건자가 true를 반환하는 모든 원소들을 삭제. 조건자 자리에 람다 표현식(lambda expression)을 사용할 수 있다.

struct citizen
{
    std::string name;
    int age;
};


int main()
{
    std::forward_list<citizen> citizens = {
        {"Kim", 22}, {"Lee", 25}, {"Park", 18}, {"Jin", 16}
    };

    auto citizens_copy = citizens;

    citizens.remove_if([](const citizen &c){
        return (c.age < 19);
    });
    // {"Park", 18}, {"Jin", 16} 삭제

    citizens_copy.remove_if([](const citizen &c){
        return (c.age != 18);
    });
    // {"Park", 18} 제외한 나머지 다 삭제

    return 0;
}

참고 사이트 : https://en.cppreference.com/w/cpp/language/lambda remove()와 remove_if()는 리스트 전체 순회하면서 조건에 맞는 원소 삭제하므로 $$O(n)$$ 시간을 갖는다. std::forward_list는 sort() 멤버 함수를 갖는다. 그리고 std::sort(first_iterator, last_iterator) 함수를 사용 할 수 없다. sort()멤버 함수는 두 가지 형태를 지원, 하나는 < 연산자 기반으로 정렬, 다른 하나는 매개변수로 전달된 비교자(comparator)를 사용. 기본 sort() 함수는 std::less<value_type>을 비교자로 사용.

std::forward_list fl{23, 0, 1, -3, 34, 32};
fl.sort();
// -3 0 1 23 32 34
fl.sort(std::greater<int>());
// 34 32 23 1 0 -3

참고 사이트 - https://en.cppreference.com/w/cpp/container/forward_list/sort 기타 멤버 함수들

    std::forward_list<int> list1 = {2, 53, 1, 0, 4, 10};
    // 2 53 1 0 4 10 
    // 10 4 0 1 53 2
    list1.reverse(); // 원소 거꾸로 나열

    list1 = {0, 1, 0, 1, -1, 10, 5, 5, 10, 0};
    list1.unique(); // 인접한 원소 간에 값이 동일하면 하나만 남기고 제거
    // 0 1 0 1 -1 10 5 10 0

    list1 = {0, 1, 0, 1, -1, 10, 5, 5, 10, 0};
    list1.sort();
    list1.unique();
    // -1 0 1 5 10

    // 리스트에서 특정 원소가 바로 앞 원소보다 2 이상 크지 않으면 삭제 
    list1.unique([](int a, int b) { return (b - a) < 2; });
    // -1, 1, 5, 10

반복자 참고 사이트 - https://en.cppreference.com/w/cpp/iterator 반복자는 포인터와 비슷하지만 STL 컨테이너에 대해 공통의 인터페이스 제공. 벡터와 배열 같은 경우 random access iterator, std::forward_list는 forward iterator. 반복자 타입에 따라 사용할 수 있는 함수들이 다르다. 순반향 반복자에 대해 prev() 함수 를 사용하면 에러 발생

아래는 단일 연결 리스트 구현 코드

#include <iostream>
#include <algorithm>

struct singly_ll_node
{
    int data;
    singly_ll_node* next;
};

class singly_ll
{
public:
    using node = singly_ll_node;
    using node_ptr = node *;

private:
    node_ptr head;

public:
    void push_front(int val)
    {
        auto new_node = new node { val, NULL };
        if (head != NULL)
            new_node->next = head;
        head = new_node;
    }

    void pop_front()
    {
        auto first = head;
        if (head)
        {
            head = head->next;
            delete first;
        }
    }

    struct singly_ll_iterator
    {
    private:
        node_ptr ptr;

    public:
        singly_ll_iterator(node_ptr p) : ptr(p) {}
        int &operator*() { return ptr->data; }
        node_ptr get() { return ptr; }
        singly_ll_iterator& operator++()
        {
            ptr = ptr->next;
            return *this;
        }
        singly_ll_iterator operator++(int)
        {
            singly_ll_iterator result = *this;
            ++(*this);
            return result;
        }

        friend bool operator==(const singly_ll_iterator& left, const singly_ll_iterator& right)
        {
            return left.ptr == right.ptr;
        }

        friend bool operator!=(const singly_ll_iterator& left, const singly_ll_iterator& right)
        {
            return left.ptr != right.ptr;
        }
    };

    singly_ll_iterator begin() { return singly_ll_iterator(head); }
    singly_ll_iterator end() { return singly_ll_iterator(NULL); }
    singly_ll_iterator begin() const { return singly_ll_iterator(head); }
    singly_ll_iterator end() const { return singly_ll_iterator(NULL); }

    singly_ll() = default;

    singly_ll(const singly_ll& other) : head(NULL)
    {
        if (other.head)
        {
            head = new node{0, NULL};
            auto cur = head;
            auto it = other.begin();
            while (true)
            {
                cur->data = *it;
                auto tmp = it;
                ++tmp;
                if (tmp == other.end())
                    break;
                cur->next = new node{0, NULL};
                cur = cur->next;
                it = tmp;
            }
        }
    }

    singly_ll(const std::initializer_list<int>& ilist) : head(NULL)
    {
        for (auto it = std::rbegin(ilist); it != std::rend(ilist); it++)
            push_front(*it);
    }
};

std::list std::forward_list는 아주 기본적인 형태, 메모리를 적게 쓰고 빠른 성능 유지한다. 다만, 기능이 매우 적다. 그래서 다양한 기능이 있는 std::list가 있다. 이는 양방향 연결 리스트이다.

struct singly_ll_node
{
    int data;
    singly_ll_node* next;
};

struct doubly_ll_node
{
    int data;
    doubly_ll_node* next;
    doubly_ll_node* prev;
};

따라서 push_back() 함수와 size() 함수 지원. std::list 멤버 함수들은 std::forward_list의 멤버 함수들 중 _after로 끝나는 함수들이 _after없는 형태. 한 예로 insert_after()가 insert()로 된다.

#include <iostream>
#include <list>

int main()
{
    std::list<int> list1 = {1,2,3,4,5};
    list1.push_back(6); // 1,2,3,4,5,6
    list1.insert(next(list1.begin()), 0); // 1,0,2,3,4,5,6
    list1.insert(list1.end(), 7); // 1,0,2,3,4,5,6,7
    list1.pop_back(); // 1,0,2,3,4,5,6
}

std::forward_list와 std::list의 공통 함수들의 시간복잡도는 같지만 std::list에서는 연산이 조금 더 필요로 한다. -> 두 개의 포인터를 관리해야하기 때문 반복자 같은 경우 std::forward_list와는 달리 역방향(reverse iterator)으로 이동 가능하기에 더 유연하지만 ramdom-access iterator 만큼은 아니다. std::list의 반복자는 bidirectional iterators라 한다.
반복자 무효화 컨테이너가 변경되어 특정 노드 또는 원소의 메모리 주소가 바뀌면 사용하던 반복자가 무효화될 수 있다. undefined behaviour 발생 vector::push_back()이나 vector::insert()함수에서 메모리 공간을 재할당을 받을 경우 기존의 반복자와 포인터, 참조는 무효화된다. 벡터와 달리 리스트는 무효화가 되지는 않는다.

std::vector<int> vec = {1,2,3,4,5};
auto v_it4 = vec.begin() + 4;
vec.insert(vec.begin() + 2, 0); // v_it4 반복자 무효

std::list<int> lst = {1,2,3,4,5};
auto l_it4 = next(lst.begin(), 4);
lst.insert(next(lst.begin(), 2), 0); // l_it4 반복자는 여전히 유효

std::deque 덱은 양방향 큐의 약자(double-ended queue). 덱은 단일 메모리 청크를 사용하지 않는다. 대신 크기가 같은 여러 개의 메모리 청크를 사용하여 데이터를 저장. 이때 청크의 인덱스 및 크기를 이용하여 특정 위치의 원소가 어느 청크에 저장되어 있는지를 알 수 있다. 덱이 다른 컨테이너들과 다른 점은 성능과 메모리 요구 사항이다. 덱은 다소 복잡한 구조를 가지고 있다.

컨테이너 어댑터 앞의 컨테이너들은 바닥부터 만들어졌고 std::stack, std::queue, std::priority_queue는 이미 존재하는 컨테이너를 기반으로 만들어진 컨테이너들이다. std::stack을 먼저 보면 LIFO(Last In First Out)구조. std::deque으로 만든 간단한 래퍼로서 스택 자료 구조에서 꼭 필요한 인터페이스만을 제공. 이러한 방식으로 만들어진 것을 container adaptor라 한다. std::deque이 기본 컨테이너로 사용하는데 이는 재할당 시 벡터처럼 원소 전체를 이동할 필요가 없기 때문이다. 그럼에도 몇몇 컨테이너가 더 효율적일 수도 있다. 아래와 같이 기본 컨테이너를 명시하여 사용 가능하다.

std::stack<int, std::vector<int>> stk;
std::stack<int, std::list<int>> stk;

std::queue는 FIFO(First In First Out)구조이다. std::queue도 스택과 마찬가지로 덱을 기본 컨테이너로 사용. std::priority_queue 우선순위 큐는 힙(heap)이라고 부르는 매우 유용한 구조를 제공. 힙은 컨테이너에서 가장 작거나 큰 원소에 빠르게 접근할 수 있는 자료 구조. 최소/최대 원소에 접근하는 동작은 $$O(n)$$이 걸리며 원소 삽입은 $$O(\log n)$$이 걸린다. 기본 컨테이너는 벡터를 사용한다. 삽입과 삭제 시 비교자(기본으로 std::less)를 사용하여 재정렬하는 heapify 알고리즘을 구현해야한다. 스택, 큐, 우선순위 큐에서 모든 원소를 순회하는 작업을 할 필요는 없다. 언제든 특정 위치에 있는 원소 하나만을 참조할 수 있으면 된다. 따라서 STL은 이 어댑터에 대해서는 반복자를 지원하지 않는다.

벤치마킹 각각의 컨테이너는 다양한 장단점을 지니고 있다. 모든 상황에 알맞는 컨테이너는 존재하지 않는다. 따라서 benchmarking-통계 데이터를 기반으로 더 나은 접근 방식을 결정하는 방법이 좋은 해결책. std::vector와 std::deque에 맞는 문제가 있을 시 어느 것을 사용할 지 선택해야한다. 이러한 경우 실제 모델과 비슷한 작은 프로토타입을 만들고 두 컨테이너를 사용하여 구현하고 성능 측정하여 선택한다. 이런 경우 많은 오차와 다른 외부 요인들로 인해 정확한 결과를 갖기가 쉽지 않아서 많은 반복을 통해서 수행 시간을 측정하는 것이 좋다. https://quick-bench.com/ 이 사이트를 통해서 도움 받을 수 있다.

https://school.programmers.co.kr/learn/courses/30/lessons/17686?language=cpp

#include <string>
#include <vector>
// add
#include <algorithm>

using namespace std;

struct filename
{
    std::string head;
    int num;
    int idx;
};

bool compare(filename& f1, filename& f2)
{
    if (f1.head == f2.head) {
        if (f1.num == f2.num)
            return f1.idx < f2.idx;
        return f1.num < f2.num;
    }
    return f1.head < f2.head;
}

vector<string> solution(vector<string> files) {
    vector<string> answer;
    vector<filename> list;
    for (int i = 0; i < files.size(); ++i)
    {
        size_t pos1 = files[i].find_first_of("0123456789", 0);
        size_t pos2 = files[i].find_first_not_of("0123456789", pos1);
        if (pos2 == files[i].npos)
            pos2 = files[i].size() - 1;
        std::string head = files[i].substr(0, pos1);
        std::transform(head.begin()
                      , head.end()
                      , head.begin()
                      , [](unsigned char c) { return std::tolower(c); });

        list.push_back({head, stoi(files[i].substr(pos1, pos2)), i});
    }
    std::sort(list.begin(), list.end(), compare);
    for (auto& e : list)
        answer.push_back(files[e.idx]);

    return answer;
}

/* lambda function instead */
#include <string>
#include <vector>
// add
#include <algorithm>

using namespace std;

struct filename
{
    std::string head;
    int num;
    int idx;
};

vector<string> solution(vector<string> files) {
    vector<string> answer;
    vector<filename> list;
    for (int i = 0; i < files.size(); ++i)
    {
        size_t pos1 = files[i].find_first_of("0123456789", 0);
        size_t pos2 = files[i].find_first_not_of("0123456789", pos1);
        if (pos2 == files[i].npos)
            pos2 = files[i].size() - 1;
        std::string head = files[i].substr(0, pos1);
        std::transform(head.begin()
                      , head.end()
                      , head.begin()
                      , [](unsigned char c) { return std::tolower(c); });

        list.push_back({head, stoi(files[i].substr(pos1, pos2)), i});
    }
    std::sort(list.begin(), list.end(), [](filename &f1, filename &f2) {
        if (f1.head == f2.head) {
            if (f1.num == f2.num)
                return f1.idx < f2.idx;
            return f1.num < f2.num;
        }
        return f1.head < f2.head;
    });
    for (auto& e : list)
        answer.push_back(files[e.idx]);

    return answer;
}

Memo

• std::string 멤버 함수 find_first_of(), find_first_not_of()
• std::transform()
• std::sort()

std::sort - cppreference.com

std::transform - cppreference.com

std::basic_string<CharT,Traits,Allocator>::find_first_of - cppreference.com

std::find, std::find_if, std::find_if_not - cppreference.com

출처 : 구체수학, 수학독본

• 프랑스 수학자 에두아르 뤼카가 1883년에 고안한 퍼즐
  • 원반 여덟 개로 된 탑으로 시작
  • 원반들은 세 개의 기둥 중 하나에 큰 것부터 크기순으로 쌓여 있다(꼭대기에 제일 작은 원반)
  • Goal: 원반을 하나씩 이동해서 탑 전체를 다른 기둥으로 옮기는 것
    • 단, 작은 원반 위에 큰 원반을 놓아서는 안된다는 규칙이 있다.

1. 일반화

   • 원반이 n개의 경우
     • small case들을 살펴보는 것부터 시작

2. 적절한 표기법

   • 규칙에 따라 다른 한 기둥으로 옮기는데 필요한 최소한의 이동 횟수를 $T_n$으로 표기
     • $T_1$이 1이고 $T_2$는 3이다.

3. Think small

   • $T_0$은 0

4. Think big

   • 원반 세 개의 경우

     • 위에서 2번째 원반까지 가운데 기둥으로 옮기고, 마지막 제일 큰 원반을 목표 기둥으로 옮기고, 가운데 있는 두 원반을 세번째 기둥으로 옮기는 것이다.

       • 여기서 n개의 원반을 옮기는 문제의 힌트가 있다.

         1. 가장 작은 원반부터 n-1개를 다른 기둥으로 옮기고(필요한 이동 횟수 $T_{n-1}$)

         2. 가장 큰 원반을 또 다른 기둥으로 옮기고(필요 이동 횟수 1)

         3. 남은 원반 n-1개를 옮기는 것(필요한 이동 횟수 $T_{n-1}$)

            $\therefore;T_0=0,;T_n=2T_{n-1}+1,;n\gt0$

            위 같은 등식을 점화식(recurrence formula)또는 점화관계식(recurrence relation)이라 부른다.

   • 수학적 귀납법

     • 원반의 개수에 따른 이동 횟수를 세어보면
       • $T_3=2\cdot3+1=7$
       • $T_4=2\cdot7+1=15$
       • $T_5=2\cdot15+1=31$
       • $T_6=2\cdot31+1=63$
       • $T_n=2\cdot T_{n-1}+1=2^n-1, n\ge0$
     • 수학적 귀납법(mathematical induction)은 정수 n에 관한 어떤 명제가 모든 $n \ge n_0$에 대해 참임을 증명하는 방법.
       • $n=1$일 때 $P(n)$이 성립하고 $n=k$일때 성립한다고 가정 → $n=k+1$일 때에도 $P(n)$성립, 즉 $P(k)→P(k+1)$
         • $T_n=2^n - 1$에서 1을 넣으면 성립
         • $T_{k+1}=2\cdot T_k + 1=2^{k+1} - 1$에서 $T_k$는 $2^n - 1$이며 $2\cdot (2^n-1) + 1=2^{k+1} - 1$ 따라서 $k+1$일 때도 성립

풀이

출처 : Accelerated Computer Science Fundamentals Specialization(Coursera)

원반 4개인 경우

Solution 1.

• Check the movement and see the pattern. S is a stack, M is a movement.

| S | M | S |
| --- | --- | --- |
| 0 | → | 1 |
| 0 | → | 2 |
| 1  | → | 2 |
| 0 | → | 1 |
| 0 | ← | 2 |
| 1  | ← | 2 |
| 0 | → | 1 |
| 0 | → | 2 |
| 1  | → | 2 |
| 0 | ← | 1 |
| 0 | ← | 2 |
| 1  | → | 2 |
| 0 | → | 1 |
| 0 | → | 2 |
| 1  | → | 2 |
- 0, 0, 1과 1, 2, 2의 반복된 패턴을 볼 수 있다.
- 원반의 이동, 즉 화살표만 다르다.

```cpp
while (target 기둥의 원반 갯수가 4개인가?) // 목표 기둥에 원반 4개가 없으면 1, 아니면 0
{
    pattern(0, 1)
    pattern(0, 2)
    pattern(1, 2)
}

pattern(기둥의 인데스 1, 기둥의 인덱스 2) // 두 인자를 받는다.
{
    if 1의 기둥에 원반이 없으면서 2의 기둥에 원반이 있으면
        2에 있는 원반을 1로 옮긴다
    else if 1의 기둥에 원반이 있으면서 2의 기둥에 원반이 없으면
        1에 있는 원반을 2로 옮긴다.
    else if 1의 기둥에 원반이 있으면서 2의 기둥에도 원반이 있으면
    {
        1의 기둥에서 제일 위에 있는 원반의 크기와 2의 기둥에서 제일 위에 있는 원반의 크기 비교
        1의 기둥의 원반의 크기가 작으면 2의 기둥으로 이동
        아니면 2의 기둥의 원반을 1의 기둥으로 이동
    }
}
```

Solution 2

원반 4개인 경우

1. 가장 큰 원반을 제외한 원반들을 하나의 기둥으로 옮긴다

2. 마지막 제일 큰 원반을 목표 지점의 기둥으로 옮긴다.

3. 나머지 원반들을 제일 큰 원반이 있는 기둥으로 옮긴다.

   여기서 마지막 원반이 없다고 가정하며, 목표 기둥은 위에서 제일 큰 원반이 있는 기둥이 아닌 다른 기둥

   1. 가장 큰 원반을 제외한 원반들, 즉 2개의 원반을 하나의 기둥으로 옮긴다.

   2. 가장 큰 원반을 목표 기둥으로 옮긴다.

   3. 2개의 원반을 가장 큰 원반 위로 옮긴다.

      여기서 또 마지막 원반이 없다고 가정하며, 목표 기둥은 위의 기둥과 다른 기둥

      1. 둘 중 작은 원반 하나를 다른 기둥으로 옮긴다.
      2. 큰 원반을 목표 지점으로 옮긴다.
      3. 작은 원반을 큰 원반 위로 올린다.
         • 원반이 하나 남았을때, 위의 목표 지점과는 다른 기둥으로 옮긴다.

위에서 하나의 패턴을 볼 수 있다.

- 원반이 하나씩 없앨때마다 목표 기둥이 바뀐다.

조금 더 자세히

4개의 원반인 경우

• 높이는 4, 높이의 index 범위(0 ~ 3)
• 기둥 3개, index 범위(0 ~ 2), 0 - Source, 1 - Spare, 2 - Target.
  • 여기서 Target과 Spare는 높이에 따라 바뀐다.

Goal : 4개의 원반을 목표 기둥으로 이동

[num] - 기둥, {num} - 원반, → - movement

move(Source[0]{0..3} → Target[2])

1. move(Source[0]{1..3} → Spare[1])
   1. move(Source[0]{2..3} → Spare[1])
      1. move(Source[0]{3..3} → Spare[1])
         • move(Source[0]{3} → Spare[1])
      2. move(Source[0]{2} → Target[2])
         • move(Source[0]{2} → Target[2])
      3. move(Spare[1]{3..3} → Target[2])
         • move(Spare[1]{3} → Target[2])
   2. move(Source[0]{1} → Target[1])
      • move(Source[0]{1} → Target[1])
   3. move(Spare[2]{2..3} → Target[1])
      1. move(Source[2]{3..3} → Spare[0])
         • move(Source[2]{3} → Spare[0])
      2. move(Source[2]{2} → Target[1])
         • move(Source[2]{3} → Target[1])
      3. move(Spare[0]{3..3} → Target[1])
         • move(Spare[0]{3} → Target[1])
2. move(Source[0]{0} → Target[2])
   • move(Source[0]{0} → Target[2])
3. move(Spare[1]{1..3} → Target[2])
   1. move(Spare[1]{2..3} → Source[0])
      1. move(Spare[1]{3..3} → Target[2])
         • move(Spare[1]{3} → Target[2])
      2. move(Spare[1]{2} → Source[0])
         • move(Spare[1]{2} → Source[0])
      3. move(Target[2]{3..3} → Source[0])
         • move(Target[2]{3} → Source[0])
   2. move(Spare[1]{1} → Target[2])
      • move(Spare[1]{1} → Target[2])
   3. move(Source[0]{2..3} → Target[2])
      1. move(Source[0]{3..3} → Spare[1])
         • move(Source[0]{3} → Spare[1])
      2. move(Source[0]{2} → Target[2])
         • move(Source[0]{2} → Target[2])
      3. move(Spare[1]{3..3} → Target[2])
         • move(Spare[1]{3} → Target[2])

많이 헷갈릴 수 있다.

void move(uint16_t start, uint16_t end, Stack& source, Stack& spare, Stack& target)
{
    if (start == end) {
        target.push_back(source.removeTop())
    } else {
        move(start+1, end  , source, target, spare);
        move(start  , start, source, spare , target);
        move(start+1, end. , spare , source, target);
    }
}

// 호출시 인자의 값을 확인
move(가장 낮은 높이, 가장 높은 높이, 시작 기둥, 여분 기둥, 목표 기둥);

끝.

GLFW를 초기화하고 glfwWindowHint 함수를 가지고 환경 설정한다.

• 이 함수의 첫번째 인자는 어떤 옵션을 환경 설정하고 싶은지
  • GLFW_로 시작하는 옵션들이 enum로 되어있으며 여기서 선택 가능
• 두번째 인자는 옵션의 값을 설정
• 모든 가능한 옵션들은 아래의 사이트에서 찾을 수 있다.

GLFW: Window guide

여기서 3.3 version을 사용하기에 GLFW에 사용하는 OpenGL version을 알려주어야 GLFW는 OpenGL context를 생성할 때 제대로된 방식으로 만들 수 있다. 이는 사용자가 올바른 버전을 가지지 않았을 때 GLFW가 실행을 못하게 한다.

여기서 major와 minor를 3으로 설정하고 core profile을 사용한다고 명시한다고 GLFW에 알려준다. core profile을 사용하는 것을 알려주는 것은 더 이상 필요없는 구버전에 호환이 가능한 기능들 없이 OpenGL 기능의 더 작은 부분까지 접근할 수 있다는 것이다.

Mac에서는 마지막 줄을 추가해야한다.

glxinfo 함수를 통해서 버전 확인 가능

다음은 윈도우 생성

GLFWwindow* window = glfwCreateWindow(800, 600, "LearnOpenGL", NULL, NULL);
if (window == NULL)
{
    std::cout << "Failed to create GLFW window" << std::endl;
    glfwTerminate();
    return -1;
}
glfwMakeContextCurrent(window);

glfwMakeContextCurrent

창 생성 이후 이 창의 context를 현재 스레드에서 메인 context로 지정한다고 GLFW에 알려준다.

GLAD

GLAD는 OpenGL에 관한 함수 포인터들 관리, 그래서 OpenGL 함수를 사용하기 전에 초기화 함수 실행

if (!gladLoadGLLoader((GLADloadproc)glfwGetProcAddress))
{
    std::cout << "Failed to initialize GLAD" << std::endl;
    return -1;
}

OS마다 다른 OpenGL 함수 포인터들의 주소를 불러오는 GLAD 함수를 통한다. GLFW는 OS에 맞는 정확한 함수 정의하는 glfwGetProcAddress 함수를 준다.

Viewport

렌더링하기전 마지막 단계. 렌더링할 윈도우의 사이즈를 OpenGL에 알려준다. OpenGL은 윈도우에 맞게 어떻게 데이터와 좌표계를 디스플레이할 지 안다.

glViewport(0, 0, 800, 600);

glViewport의 첫 두 개의 인자는 윈도우의 좌하단의 위치 세번째 네번째 인자는 width와 height의 렌더링할 픽셀, 이는 윈도우의 크기와 같게 설정함.(물론 다르게 가능)

윈도우 창 크기 조절할 때마다 viewport의 크기도 조절되어야한다.

void framebuffer_size_callback(GLFWwindow* window, int width, int height);
void framebuffer_size_callback(GLFWwindow* window, int width, int height)
{
glViewport(0, 0, width, height);
}

위와 같이 콜백 함수를 만들고 아래의 함수 호출에 사용하면 크기 조절에 맞춰 viewport도 수정

glfwSetFramebufferSizeCallback(window, framebuffer_size_callback);

Ready your Engines

이미지를 바로 창에 띄우고 바로 종료되는 애플리케이션을 원하지 않고 명시적으로 종료하는 순간까지 이미지를 그리고 사용자입력을 받길 원하는 건 당연. 이러한 이유로 루프문 구현, 이 루프를 렌더 루프라 한다. 이 렌더 루프는 GLFW가 종료될 때까지 실행.

while(!glfwWindowShouldClose(window))
{
    glfwSwapBuffers(window);
    glfwPollEvents();
}

glfwWindowShouldClose 함수는 GLFW가 종료지시를 받았는지 루프 시작점에서 확인.

glfwPollEvents 함수는 어떤 이벤트가 작동, 윈도우 창 업데이트, 그 이벤트에 맞는 함수 호출 체크.

glfwSwapBuffers 함수는 렌더링 반복 중 렌더하기 위해 사용되는 색상 버퍼를 스왑한다. 그리고 스크린에 출력.

Double Buffer : front buffer는 마지막 출력물을 담고 스크린에 나타난다. 언제까지? back buffer에 다음 출력물이 그려질때까지 그리고 스왑한다. 이러한 식으로 렌더링 한다.

마무리

glfwTerminate();
return 0;

glfwTerminate 함수는 이제 종료되기 전에 GLFW의 자원을 정리하기 위해서 호출

Input

GLFW에서 입력 처리

void processInput(GLFWwindow *window)
{
    if(glfwGetKey(window, GLFW_KEY_ESCAPE) == GLFW_PRESS)
        glfwSetWindowShouldClose(window, true);
}

GLFW의 glfwGetKey 함수를 사용. 이 함수의 인자는 window와 키값을 받는다.

키값이 입력되지 않으면 함수 리턴값으로 GLFW_RELEASE를 받는다. Escape 키를 누르면 분기문으로 들어가 glfwSetWindowshouldClose 함수 실행한다.

while (!glfwWindowShouldClose(window))
{
    processInput(window);
    glfwSwapBuffers(window);
    glfwPollEvents();
}

위의 코드처럼 렌더 루프문에 넣어서 처리

렌더링

// render loop
while(!glfwWindowShouldClose(window))
{
    // input
    processInput(window);
    // rendering commands here
    ...
    // check and call events and swap the buffers
    glfwPollEvents();
    glfwSwapBuffers(window);
}

렌더링 명령어들을 모두 렌더 루프에 넣는다.

glClear 스크린 색상 버퍼를 지우는 함수

glClearColor(0.2f, 0.3f, 0.3f, 1.0f);
glClear(GL_COLOR_BUFFER_BIT);

glClearColor 함수는 glClear 함수 호출 시 색상 버퍼를 정리할 때 마다 색상 버퍼 전체는 glClearColor로 설정된 색으로 채워진다.

여기서 glClearColor는 state-setting 함수, glClear는 state-using 함수이다.

• 위의 작업들은 OS마다 다르며, OpenGL은 의도적으로 위 작업들로부터 그 자체를 추상화하려고 한다.
  • 이는 창 생성, context 정의, 사용자 입력 처리 전부 개인 스스로 처리해야만 한다.
  • 운좋게 위의 작업들을 위한 기능들을 제공하는 몇몇 라이브러리가 있다. 그 중 몇몇은 OpenGL에 특정되어 있다. 이런 라이브러리들은 모든 OS 특정 작업들을 하지 않도록 해주고 window와 OpenGL context를 제공
  • 대중적인 라이브러리들 - GLUT, SDL, SFML, GLFW.
    • 여기서 GLFW를 사용, 대부분 다른 라이브러리는 GLFW의 설정과 유사

GLFW

• OpenGL을 대상으로 C언어로 쓰여진 라이브러리이다.
  • 스크린에 멋진 그래픽을 렌더링에 요구되는 가장 기본적인 필수 기능들을 제공
    • OpenGL context 생성, window 매개변수 정의와 사용자 입력 처리를 하게 해준다.

Building GLFW

https://www.glfw.org/download.html

CMake를 사용해서 프로젝트 관리

GLAD

• OpenGL은 단순 설명서라고 했었다. 이는 특정 그래픽 카드가 지원하는 드라이버에 맞는 구현은 드라이버 제조사에 달려있다.

• OpenGL 드라이버들의 다른 버전들이 많이 있기 때문에 그에 맞는 함수들 대부분의 위치는 컴파일 타임에 알지 못하며 런타임에 분기문이 필요.

• 필요한 함수의 위치를 찾거나 그 함수들을 함수 포인터에 저장하는 것은 개발자의 업무.

• 함수 위치들을 찾는 것은 OS마다 다르다.

    // Windows
  
    // define the function’s prototype
    typedef void (*GL_GENBUFFERS) (GLsizei, GLuint*);
    // find the function and assign it to a function pointer
    GL_GENBUFFERS glGenBuffers =
    (GL_GENBUFFERS)wglGetProcAddress("glGenBuffers");
    // function can now be called as normal
    unsigned int buffer;
    glGenBuffers(1, &buffer);

  위 코드를 보면 복잡하고 다루기 힘들다. GLAD를 사용하면 편하다.

GLAD는 복잡하고 힘든 일을 다루는 오픈 소스 라이브러리, 다른 일반적인 오픈 소스 라이브러리와 조금은 다른 환경설정을 가진다. GLAD에 OpenGL 버전에 맞는 기능들을 불러오고 정의하고 싶은 것들을 GLAD 웹 서비스에서 확인해서 사용

http://glad.dav1d.de/

위 사이트를 들어가서 체크

• C++, version 3.3, Core → generate a loader → library files

#include <glad/glad.h>

설정 코드 참고

OpenGL

• 그래픽과 이미지 조작하기 위해 사용할 수 있는 함수들을 모아둔 하나의 큰 세트를 제공하는 API(Application Programming interface)라고 주로 생각한다.
• 하지만 OpenGL 그자체는 API가 아니다. 크로노스 그룹이 만들고 유지보수하는 하나의 설명서일 뿐.
• OpenGL 설명서는 각각의 함수들이 어떻게 작동하고 그 결과나 산출물이 정확히 무엇인지 명시한다.
  • 구현에 관한 세부사항들을 알려주지 않는다.
• 실제 OpenGL 라이브러리를 개발하는 사람들은 그래픽 카드 회사 사람들이고 각각의 그래픽 카드는 그 그래픽 카드에 맞게 개발된 버전을 제공
• 크로노스 그룹에서 모든 버전에 관한 설명서들을 관리한다.
  • 크로노스 그룹 홈페이지 : https://www.khronos.org/
• 거의 모든 구현은 그래픽 카드 제조사들에 의해 설계되어있기 때문에 버그가 발생할 때마다 비디오 카드 드라이버를 업데이트 해주는 것으로 일반적으로 해결이 된다.
  • 그런 드라이버들은 새로운 OpenGL 버전을 포함한다
  • 왜 항상 그래픽 드라이버를 업데이트하라는 이유 중 하나

Core-profile vs Immediate mode

• 예전에는 OpenGL을 사용하는 것은 Immediate mode에서 개발하는 것을 의미
  • immediate mode == fixed function pipeline
  • 이는 그래픽을 그리기 위한 쉬운 방식
• OpenGL의 거의 모든 기능은 라이브러리에 숨겨져 있고 개발자들은 OpenGL이 어떻게 계산을 하는지에 관한 제어권을 가지지 않았다.
  • 위 내용에 의해서 개발자들이 좀 더 유연성을 원하게 했고 결국 그래픽에 대한 제어권을 갖게 되었다.
• Immediate mode는 사용하고 이해하기 정말 쉬웠지만 비효율적이었다.
  • 이런 이유로 3.2 버전 이후로부터 immediate mode 기능들 사용을 반대하기 시작했다.
    • Core-profile mode에서 개발하기를 권장했다.
    • 중요도가 떨어졌던 예전 기능들을 삭제
• OpenGL의 core-profile을 사용할 때 OpenGL은 현대식으로 사용하게 강요
  • 예전 deprecated 기능들을 사용할때마다 OpenGL은 에러를 띄우거나 그리는 것을 멈춤
• 현대식으로 접근하는 것을 배우는 장점은 유연하고 효율적이지만 배우기 어려움
• Immediate mode는 OpenGL이 수행하는 실제 연산들로부터 상당히 많이 추상화했지만 배우기 쉽다, 실제로 OpenGL이 어떻게 작동하는지 파악하기 힘들다.
• 현대적 접근방식은 OpenGL과 그래픽을 제대로 이해하는 것을 요구하는 반면, 어렵다. 이는 훨씬 효율적이고 유연하고 중요하다. → 더 나은 그래픽 프로그래밍의 이해
• Learn OpenGL 책에서 core-profile OpenGL version 3.3 기준으로 작성.
  • 3.3 이후로 유용한 기능들이 추가될 뿐 실제 코어 머신은 바뀌지 않았다.
  • 모든 컨셉과 기술들은 똑같다. 3.3 버전으로 완벽히 충분하다.

Extensions

• OpenGL의 큰 특징은 extensions의 지원이다. 그래픽 회사들이 새로운 기술들이나 렌더링 최적화를 가지고 나올 때마다 드라이버들 안에서 구현된 extension을 찾을 수 있다. 만약 하드웨어가 앞서 말한 extension들을 제공한다면, 개발자들은 그 extension으로부터 제공된 기능들을 사용하여 더 나은 더 효율적인 그래픽스를 사용할 수 있다. 단순하게 그래픽 카드가 지원하는 extension을 확인하는 것으로부터 차후 버전에서의 기능들을 포함하는 OpenGL을 기다려야하는 일 없이 새로운 렌더링 기술을 계속해서 사용할 수 있게 해준다.

• 개발자들은 이러한 extensions들이 사용되기전에 이용가능한지 물어야한다.

    if(GL_ARB_extension_name)
    {
    // Do cool new and modern stuff supported by hardware
    }
    else
    {
    // Extension not supported: do it the old way
    }

State machine

• OpenGL은 큰 상태 머신 그 자체 : OpenGL이 현재 어떻게 연산해야하는지 정의하는 변수들의 집합
  • 또한 OpenGL의 상태(state)는 context라고 불린다.
• OpenGL을 사용할 때, 종종 몇몇 옵션을 세팅하고 버퍼를 조작하고 최신 context를 사용하여 그리는 것으로 그 상태를 변경한다.
• 예를들어 OpenGL에게 삼각형을 그리는 대신 지금 선분들을 그리길 원한다고 알릴 때마다 OpenGL이 어떻게 그려야하는지 설정하는 context 변수들을 바꿈으로써 OpenGL의 상태를 바꾼다. OpenGL에 선분들을 그려야하는 것을 알리는 것으로 context를 바꾸자마자 다음 그리는 명령어는 삼각형 대신 선분들을 그릴 것
• OpenGL에서 작업 중 context를 바꾸는 state-changing functions과 OpenGL의 최신 상태를 근거로 연산을 수행하는 state-using functions를 발견할 것.
• OpenGL이 기본적으로 하나의 큰 상태 머신이라는 것을 명심하기만 하면 대부분의 그 기능들의 의미를 더 이해할 것이다.

Objects

• OpenGL 라이브러리는 C로 쓰여졌으며 다른 언어들에서 많은 어원을 참작한다. 그러나 그 핵심은 C-library로 남아있다. C언어의 상당수가 다른 고차원 언어로 옮겨지지 않기 때문에 OpenGL은 몇가지 추상화를 유념하여 개발되었다. 그 추상화들 중 하나는 object이다.

• OpenGL에서 object는 OpenGL의 상태의 부분집합을 표현하는 옵션들의 콜렉션이다. 예를들어 창을 그리는 설정들을 표현하는 object를 가질 수 있다. 그 사이즈, 몇가지 색상 등을 설정할 수 있다.

    struct object_name {
        float option1;
        int option2;
        char[] name;
    };
  
    // The State of OpenGL
    struct OpenGL_Context {
    ...
    object_name* object_Window_Target;
    ...
    };
  
    // create object
    unsigned int objectId = 0;
    glGenObject(1, &objectId);
    // bind/assign object to context
    glBindObject(GL_WINDOW_TARGET, objectId);
    // set options of object currently bound to GL_WINDOW_TARGET
    glSetObjectOption(GL_WINDOW_TARGET, GL_OPTION_WINDOW_WIDTH, 800);
    glSetObjectOption(GL_WINDOW_TARGET, GL_OPTION_WINDOW_HEIGHT, 600);
    // set context target back to default
    glBindObject(GL_WINDOW_TARGET, 0);

  1. Create an object and store a reference to it as an id(실제 데이터는 scene 뒤에 저장) : object 색성과 id로서의 참조자를 저장 - glGenObject()
  2. Bind the object to the target location of the context(GL_WINDOW_TARGET) : context의 타겟 지점에 object를 바인드 - glBindObject()
  3. Set the window options : 창 옵션 세팅
  4. Un-bind the object by setting the current object id of the window target to 0. : window target의 현재 object id 세팅으로 되어있는 object를 언바인드(0으로 바인드)

• 이러한 objects를 사용하는 것에 관한 중요한 것은 애플리케이션에 하나 이상의 object를 정의할 수 있고, 옵션들을 설정할 수 있고, OpenGL의 상태를 사용하는 연산들을 시작할 때마다 선호하는 설정값으로 objects를 바인드할 수 있다.

• 여러 object들을 3D 모델 데이터로서 컨테이너 objects들로 역할을 할 수 있고 그 중 하나를 그리기 원할 때마다 그 object를 바인드한다.

위 필기에서 오타 수정 : BC$\bot$CA → BH$\bot$CA

자료 출처: 수학독본 3권

호도법과 일반각

삼각비와 특수각에 따른 각각의 값들

삼각함수 용어 설명, 역수관계인 삼각함수들, 사영정리 및 피타고라스 정리

삼각함수의 주요 공식

삼각함수 그래프 특징

덧셈정리

삼각함수의 합성

삼각함수 여러가지 공식

증명을 위한 기초 기하 몇 가지

삼각함수와 삼각형(사인정리, 코사인정리, 삼각형의 넓이 등)

사인정리 → 삼각형의 넓이

코사인 정리 → 덧셈정리

삼각함수 코사인정리, 피타고라스 정리

삼각형의 넓이

몇가지 흥미로운 문제

삼각형의 오심

• 노드라 불리는 구조체의 체인이다.
• 각 노드들은 다음 노드를 가르키는 포인터를 가지고 있다.
• 마지막 노드는 null pointer를 가진다.
  • [N] -> [N] -> [N] -> [N] -> NULL
• 배열과 비교
  • 연결 리스트는 배열보다 더 유연하다.
  • 연결리스트에 노드를 삽입, 삭제를 쉽게 할 수 있고 리스트를 더 키우거나 줄일 수 있다. 그러나 random access(인덱스로 접근)의 기능을 잃는다. 배열은 어떤 원소에 접근하는 시간(O(1))은 같다. 그러나 연결 리스트의 경우 접근하는 데이터의 노드가 가장 앞에 있을 때 빠르고(O(1)) 가장 뒤에 있을 때 느리다.(O(n))

연결 리스트 구현 (데이터는 int형, 단순 기능들(생성, 삭제, 검색, 추가 등)) linked_list.h

#ifndef LINKED_LIST_H
#define LINKED_LIST_H

struct node {
    int data;
    struct node *next;
}

#include <stdlib.h> // memory allocation

struct node *create_node(int n);
struct node *add_to_list(struct node *list, int n);
void add_to_list(struct node **list, int n); // pointers to pointers
struct node *read_numbers(void);
struct node *search_list(struct node *list, int n);
struct node *delete_from_list(struct node *list, int n);
void delete_from_list(struct node **list, int n); // pointers to pointers
void delete_list(struct node **list);
struct node *insert_into_ordered_list(struct node *list, struct node *new);

#endif

linked_list.c

#include "linked_list.h"

struct node *create_node(int n)
{
    struct node *new;
    if (new == NULL) {
        printf("Error: malloc failed in create_node\n");
        return NULL;
    }
    new->data = n;
    new->next = NULL;

    return new;
}

struct node *add_to_list(struct node *list, int n)
{
    struct node *new_node;

    new_node = malloc(sizeof(struct node));
    if (new_node == NULL) {
        printf("Error: malloc failed in add_to_list\n");
        exit(EXIT_FAILURE);
    }
    new_node->value = n;
    new_node->next = list;
    return new_node;
}

// pointers to pointers
void add_to_list(struct node **list, int n)
{
    struct node *new_node;

    new_node = malloc(sizeof(struct node));
    if (new_node == NULL) {
        printf("Error: malloc failed in add_to_list\n");
        exit(EXIT_FAILURE);
    }
    new_node->value = n;
    new_node->next = *list;
    *list = new_node;
}

struct node *read_numbers(void)
{
    struct node *first = NULL;
    int n;

    printf("Enter a series of integers (0 to terminate): ");
    for (;;) {
        scanf("%d", &n);
        if (n == 0)
            return first;
        first = add_to_list(first, n);
    }
}

struct node *search_list(struct node *list, int n)
{
    while (list != NULL && list->value != n)
        list = list->next;
    return list;
}

struct node *delete_from_list(struct node *list, int n)
{
    struct node *cur, *prev;

    for (cur = list, prev = NULL;
         cur != NULL && cur->value != n;
         prev = cur, cur = cur->next)
        ;
    if (cur == NULL)
        return list;
    if (prev == NULL)
        list = list->next;
    else
        prev->next = cur->next;
    free(cur);
    return list;
}

void delete_from_list(struct node **list, int n)
{
    struct node *temp; // a pointer to the node you delete

    if ((*list)->value == n) {
        temp = *list;
        *list = (*list)->next;
        free(temp);
        return ;
    }
    while ((*list)->next != NULL && (*list)->next->value != n)
        list = &(*list)->next;
    if ((*list)->next != NULL) {
        temp = (*list)->next;
        (*list)->next = (*list)->next->next;
        free(temp);
    }
}

void delete_list(struct node **list)
{
    struct node *temp;

    if (*list == NULL)
        return;
    while (*list != NULL) {
        temp = *list;
        *list = (*list)->next;
        free(temp);
    }
}

struct node *insert_into_ordered_list(struct node *list, struct node *new)
{
    struct node *cur = list, *prev = NULL;

    while (cur != NULL && cur->value <= new_node->value) {
        prev = cur;
        cur = cur->next;
    }
    if (prev == NULL) {
        new->next = cur;
        list = new;
    } else {
        new->next = cur;
        prev->next = new;
    }
    return list;
}

몇 가지 실수했던 부분들

• 포인터에 대한 이해도 있어야되지만 범위를 이해하고 있는게 더 중요하다.

  • 먼저 함수의 매개변수도 지역변수이므로 범위를 벗어나면 사라진다. 이 매개변수를 잘 이용하면 된다.

    • 단일 포인터 매개변수도 잘 이용할 수 있다. 어차피 범위를 벗어나면 사라지니 매개변수의 활용이 중요.

      void delete_from_list(struct node **list, int n)
      ...
      // 아래 while문 안에서 매개변수를 이용해야한다. 아니면 원래 주소(매개변수가 가르키는 주소)의 이동이 발생
      while ((*list)->next != NULL && (*list)->next->value != n)
          list = &(*list)->next;
      if ((*list)->next != NULL) {
          temp = (*list)->next;
          // 여기서는 본 주소의 이동이 필요
          (*list)->next = (*list)->next->next;
          free(temp);
      }
      ...
      

• 루프문 안에서 범위를 이용할 수도 있다. 괄호를 벗어나면 사라진다. 주소를 찍어보면 이해하기 수월하다. 책에서는 전역 포인터 변수를 사용하는 부분이 있는데 그 부분에서 유용했다.

    struct node *delete_node(struct node *list, int n)
    {
        struct node *temp; // 삭제할 노드를 임시적으로 담을 포인터 변수
  
        for (struct node *p = list; p->next != NULL; p = p->next) {
            if (p->next->value == n) {
                temp = p->next;
                p->next = p->next->next;
                free(temp);
                // break; 또는 같은 값을 계속 찾아 지우게 나두면 된다.
            }
        }
        return list; // list의 주소에는 변화가 없다
    }

• 포인터 같은 경우 주소를 일일이 대조해서 찍어보면 이해하는데 무리 없을 것이다.

출처: K.N.KING C PROGRAMMING A MODERN APPROACH