bingu일기

RB Tree 조건

1. 각 노드의 색은 Red or Black이다.
2. 루트 노드의 색은 Black이다.
3. 모든 리프 노드의 색은 Black이다.
4. Red노드의 자식 노드는 전부 Black이다.
5. 루트 노드에서 시작해서 리프 노드에 이르는 모든 경로에는 동일한 개수의 Black노드가 존재한다.

RB Tree 특징

NIL노드 : 존재하진 않지만 존재한다 생각하는 노드이다.

                트리의 끝에 항상 존재하며 색은 Black이다.

삽입시의 해당 노드는 Red로 들어간다.

삼촌 노드 : 부모 노드의 형제 노드를 뜻한다.

RB Tree Rotation

트리를 삽입하고 삭제하는 과정에서 RB의 조건이 맞지 않는 경우가 있는데 이를 우리는 회전을 하거나 색을 바꿔줌으로써 조건을 맞춰간다.

위의 그림을 보면 간단하게 보일지도 모른다.

하지만 step by step으로 거쳐간 상황들이 몇 가지 있다.

Rotation

왼쪽 그림에서 오른쪽 그림으로 변형시키는 과정이다.

아래의 그림이 슈도 코드인데 한 줄씩 따라가면서 해보면 간단하다.

과정은 간단하게 2 과정이다.

1. 자식 교환
2. 부모 교환

Right Rotation은 위 코드에서 right->left & left->right로 교환하면 된다.

RB Tree Insert

트리의 삽입은 일반적인 삽입 후에 조건을 만족하도록 교정하는 과정이 있다.

RB의 조건을 만족하지 못하는 경우의 수는 3가지이다.

1. 삽입한 노드가 루트 노드일 때
2. 부모 노드와 삼촌 노드가 Red일 때
3. 부모 노드가 Red인데 삼촌 노드가 Black일 때

삽입한 노드가 루트 노드일 때

부모 노드와 삼촌 노드가 Red일 때

부모 노드가 Red인데 삼촌 노드가 Black일 때

RB Tree Delete

삭제는 2가지 case로 삭제가 진행되고 RB의 조건에 맞게 조정한다.

일단 삭제할 노드, 대체할 노드, 대체할 노드를 대체할 노드를 알고 시작해야한다.

대체할 노드는 3가지 경우가 있다.

1. 삭제할 노드의 왼쪽 자식 노드(오른쪽 자식 노드가 NIL 노드일 때)
2. 삭제할 노드의 오른쪽 하위 트리의 가장 작은 노드(오른쪽 자식 노드가 NIL 노드일 때)
3. NIL노드(자식 노드가 모두 NIL 노드일 때)

대체할 노드를 대체할 노드는 2가지 경우가 있다.

1. 대체할 노드의 오른쪽 노드
2. NIL 노드

그렇게 정하고 대체할 노드위치에 대체할 노드를 대체할 노드를 넣고 삭제할 노드위치에 대체할 노드를 넣으면 된다.

하지만, 우리가 지울노드가 만약 Black노드였다면 우리는 이미 균형이 잡혀진 트리에 불균형을 초래하는 것이다.

Black노드가 지워지면 "루트노드부터 리프노드의 Black의 수가 같아야한다."는 조건을 위반하는 것으로 재조정이 필요하다.

RB Tree를 사용하는 의미는 복잡하지만 복잡한 만큼 효율적이고 최악의 경우에도 우수한 실행시간을 보이기 때문이다.

근데 색만 바꿔버리면 최종 높이들이 달라질 것이다.

그렇기 때문에 우리는 단편만 보는 것이 아니라 전체적인 트리를 보아야 하는 것이다.

Delete-fixup의 수도 코드를 보자.

형태는 복잡하게 생겼다.

크게 나누면 2가지, 다음으로는 4가지 정도가 나온다.

먼저 크게 나눠서 보자.

1. 삼촌 노드의 색이 Red일 때
2. 삼촌노드의 색이 Black일 때

삼촌 노드의 색이 Red일 때의 코드를 해석해보면, 부모 노드의 색을 Black으로 만들려 한다.

원래 존재했던 Red를 왼쪽으로 옮기는 과정이다.

이 부분은 이후 나오는 과정에서 왜 그렇게 되는지 알 수 있다.

그다음의 4가지 나눠짐을 보자.

1. 삼촌의 자식들의 모두 Black일 때
2. 삼촌의 자식 중 왼쪽이 Red일 때
3. 삼촌의 자식들이 모두 Black이 아닐 때

1번 -> 삼촌 노드를 Red로 바꾸는데, 이는 RB Tree 4번 조건에 'Red의 자식은 모두 Black이다.'를 만족시키면서 균형 잡힌 트리를 만들기 위함이다.

2번 -> 삼촌의 왼쪽 자식이 Red, 오른쪽 자식이 Black인 경우 고르게 분포되어있다고 판단한 것처럼 느껴진다.

            그래도 삼촌의 왼쪽 자식을 Black으로, 삼촌을 Red로 바꾸고 우회전을 하는데 이는 왼쪽 트리의 높이를 한 칸 더 길게 만든 것이다.

            그리고 삼촌을 다시 지정한 뒤, 삼촌의 색을 부모의 색으로 바꾸고, 부모의 색을 Black으로 바꾼다.

            또한, 삼촌의 오른쪽 자식의 색을 Blakc으로 바꾼 뒤, 좌회전을 하여 오른쪽 트리의 높이를 한 칸 더 길게 만든다.

            그리고 끝날 수 있도록 x를 루트 노드로 지정한다.

3번 -> 삼촌의 색을 부모의 색으로 바꾸고, 부모의 색을 Black으로 바꾼다.

            또한, 삼촌의 오른쪽 자식의 색을 Blakc으로 바꾼 뒤, 좌회전을 하여 오른쪽 트리의 높이를 한 칸 더 길게 만든다.

            그리고 끝날 수 있도록 x를 루트 노드로 지정한다.

처음 보았을 땐, 뭐 이리 거지같이 만들어 놨는지 모르겠다는 생각이었는데 구조와 색을 신경 쓰는 방식은 두 개의 손을 한 손씩 다른 일을 하는 것만큼 어려운듯하다.

결론적으로는 지운 노드가 Black인지 Red를 확인하는 작업에서 루트 노드의 왼쪽, 오른쪽 하위 트리에서 리프 노드로 도달하는 과정에서의 Black노드의 개수를 조절하는데, 이것을 대체 노드의 위치부터 양쪽의 균형을 유지하는 방식인 것이다.

최종 느낀점

아래 내용은 단순히 내 생각을 적는 공간입니다. 참고만 해주세요.

일단 RB Tree는 어려운 게 맞았다.

사람들이 괜히 AVL Tree로 꺾는 게 아니었다. (다만, AVL Tree도 어렵다.)

RB Tree는 Red와 Black의 조합인데, 여러 가지 조건들을 만족시켜야 한다.

조건들은 위에 있다.

하지만 나와있는 조건만 고려하면 살짝 문제가 생기는데,

이는 문제를 풀면서 각 조건들 만족하지만 루트 노드의 양쪽 하위 노드의 높이가 맞지 않다면,

그에 따라 높이도 맞춰주어야 한다는 것이다.

즉, 각각의 루트 노드까지 Black의 개수가 같다는 것은 높이 차이가 커도 1 정도일 것이다.

근데 생각해보면 우리는 Double Red는 허용하지 않지만 Double Black은 허용한다.

나는 이 부분을 생각해서 Double Black은 생각하지 않았다.

하지만, 생각해보면 우리는 자가 균형 이진 탐색 트리를 만들어야 한다는 것을 기억하고 있어야 한다.

스스로 균형을 맞추는데 이 균형을 맞출 때 고려해야 하는 부분은 리프 노드까지의 높이와 리프 노드까지의 Black이다.

예를 들자면, 어떤 조건도 위배하지 않은 트리의 루트 노드의 하위 노드 중 왼쪽은 Black으로만 이뤄져 있고, 오른쪽은 Red, Black이 균형 있게 이뤄져 있다.

그렇다면 이를 균형이 잡혀있다고 말할 수 있을지에 대한 고민을 해봐야 한다.

결과적으로, 최종적으로 존재해야 하는 조건은 Double Black은 사용할 수 있지만 자제해야 한다고 생각한다.

끄읕!!!!!

Map을 구현하기 전 cplusplus에서 어떻게 생겨먹은 놈인지 확인해야 한다.

설명을 보자 하니 듣던 대로 암 걸리는 놈이긴 한 듯하다.

기본 설정

Map은 key, value로 이루어져 저장되는 컨테이너이다.

또한, 매핑된 값은 해당 key와 관련된 내용을 저장한다.

key와 매핑된 값의 타입은 다를 수 있고, 이 둘은 member type으로 그룹화되는데 그룹화의 방식은 pair이다.

typedef pair<const Key, T> value_type;

내부적으로는 항상 정렬되어 있는데, 이는 내부의 비교 object(key_comp)를 따라 key를 기준으로 정렬된다.

기본 Map과는 다르기 Unordered_map이 있는데 Unordered_map은 정렬을 해주지 않기 때문에 기존 Map보다 더 빠르다.

Map은 bracket operator(operator [])로 key값을 통해 접근할 수 있다. (이것으로 보아 key는 중복이 허용되지 않는다.)

Map은 전형적으로 BST(binary Search Tree)로서 작동한다.

BST(Binary Search Tree)[이진 탐색 트리]

BST는 여러 가지 규칙을 가진 노드 기반 이진트리 데이터이다.

1. 노드의 왼쪽은 해당 노드의 key보다 작은 key들의 모임이다.
2. 노드의 오른쪽은 해당 노드의 key보다 큰 key들의 모임이다.
3. 왼쪽, 오른쪽 트리는 똑같은 형태를 갖고 있다.

BST는 빠른 탐색, 삽입, 삭제가 가능한 자료구조이다.

그리고 구현 방식은 매우 많다.

ex) AA, AVL, Red-Black, splay, etc....

많은 방식들이 존재하지만 몇 가지만 들춰볼 것이다.

AVL Tree

AVL Tree는 발명자(Adelson-Velsky and Landis)에서 따온 자가 균형 이진 탐색 트리이다.

자가 균형 이진 탐색 트리는 스스로 균형을 잡는 데이터 구조인데 지금은 여러 가지 방식이 있지만 AVL이 그 첫 발자국이다.

균형을 잡는 기준은 높이이다.

한 노드의 두 자식 서브 트리의 높이는 항상 최대 1만큼 차이가 나는데, 만약에 높이 차이가 1보다 커지면 속성을 유지하기 위해 스스로 균형을 잡는다.(높이 균형 성질)

검색, 삽입, 삭제는 모두 평균과 최악의 경우 O(log n)을 갖는다.

삽입과 삭제는 한 번 이상의 트리 회전을 통해 균형을 잡을 수 있다.

일반적인 BST처럼 삽입, 삭제를 동작하면 높이 균형 성질을 만족하지 못하니 동작할 때 회전을 통해 트리를 재구성하여 높이 균형 성질을 만족시킨다.

Red-Black Tree

Red-Black Tree는 이진 트리의 특수한 형태로서, 컴퓨터 공학 분야에서 숫자 등의 비교 가능한 자료를 정리하는 데 쓰이는 자료구조이다.

Red-Black Tree는 자료의 삽입과 삭제, 검색에서 최악의 경우에도 일정한 실행 시간을 보장한다.

AVL은 RB보다 엄격하게 균형이 잡혀있기 때문에 삽입, 삭제를 할 때 더 많은 회전이 발생한다.

RB Tree는 함수형 프로그래밍에서 특히 유용한데, 연관 배열이나 set 등을 내부적으로 RB Tree로 구현해 놓은 경우가 많다.

RB Tree는 몇가지 특징들을 갖고 있는 아래와 같다.

1. 노드는 Red or Black이다.
2. 루트 노드는 Black이다.
3. 모든 리프 노드들은(NIL)은 Black이다.
4. Red 노드의 자식 노드들은 Black이다.(즉, Red 노드는 연달아 나타날 수 없다.)
5. 어떤 노드로 부터 시작되어 그에 속한 하위 리프 노드에 도달하는 모든 경로에는 리프 노드를 제외하면 모두 같은 개수의 Black노드가 있다.

AA Tree

AA Tree는 RB Tree를 응용한 Tree로 RB Tree의 많은 조건을 일부 제거하여 구현을 더 간단하게 만든 트리로 균형을 맞추기 위해 레벨의 개념을 사용한 Tree이다.

부모와 레벨이 같은 자식 노드의 견결을 수평 링크라 하며, 이 노드를 구분하기 위해 Red라는 개념을 이용한다.

AA Tree는 몇 가지 특징들을 갖고 있는 아래와 같다.

1. 왼쪽 자식은 Red가 될 수 없다.
2. 연속으로 Red가 올 수 없다.(이중 Red 불가 == 이중 수평 링크)
3. 루트 노드에서 리프 노드까지의 경로에는 동일한 개수의 Black 노드가 존재한다.(RB Tree)
4. 모든 리프 노드의 레벨은 1이다.
5. 모든 왼쪽 자식의 레벨은 부모의 레벨보다 1 낮다.
6. 모든 오른쪽 자식의 레벨은 부모의 레벨과 같거나 1 낮다.
7. 모든 오른쪽 손자의 레벨은 할아버지 노드보다 낮다.
8. 1보다 큰 레벨의 모든 노드들은 2개의 자식을 갖는다.

다 어려워 보이는데... 이래서 map부터 막막하다고 들었던 것 같다.

또한, 보너스에서 set을 구현하는데 위에서 말했듯이 set은 내부적으로 RB Tree로 구현해 놓은 경우가 많으니 map도 RB Tree로 구현한 느낌이다.

나도 보너스를 포기할 수 없으니 RB Tree로 구현해보고 나중에 AVL, AA를 따로 구현해보도록 하겠다.

일반화 프로그래밍

데이터와 행동을 나누는 것을 기반으로 하며, 객체지향의 다음 세대라고 불러지기도 한다.

템플릿의 사용으로 임의의 타입에 사용할 수 있는 자료구조를 만들수 있다.

내부 구조에 상관없이 임의의 데이터 집합에 적용할 수 있는 일반화된 알고리즘을 제공한다.

템플릿

매개변수의 타입에 따라 함수나 클래스를 생성하는 메커니즘을 의미한다.

템플릿은 매개변수의 타입에 따라 달라지므로 여러 타입에서 동작할 수 있는 단 하나의 함수나 클래스를 작성하는 것이 가능하다.

함수 템플릿

함수의 일반화된 선언을 의미한다.

임의의 타입으로 작성된 함수에 특정 타입을 매개변수로 전달하면 C++ 컴파일러는 해당 타입에 맞는 함수를 생성한다.

template <typename 타입이름>
함수 원형
{
	함수 본체
}

C++ 컴파일러는 템플릿 정의 내의 typename은 class와 같은 것으로 간주한다.

정의된 함수 템플릿을 호출할 때 매개변수로 int형을 전달하면, 함수의 원형과 본체에서 정의된 타입 이름은 모두 int형으로 바뀐다.

명시적 특수화

호출된 함수에 정확히 대응하는 특수화된 정의를 발견하면, 템플릿은 찾지 않고 해당 정의를 사용한다.

template <typename T>
void 함수(T &a, T &b);
template <typename T> void 함수(T &a, T &b);

//명시적 특수화
template <typename T> void 함수<double>(double &, double &) {...};

위 처럼 특수화되면 double형에 대한 동작은 새로 정의한 행동을 동작한다.

클래스 템플릿

클래스의 일반화된 선언을 의미하고 동작은 함수 템플릿과 같다.

클래스 템플릿을 사용하면 타입에 따라 다르게 동작하는 클래스 집합을 만들 수 있다.

template <typename 타입 이름>
class 클래스 탬플릿 이름
{
	클래스 멤버의 선언
}

함수 템플릿과는 다르게 클래스 탬플릿은 사용하기 위해선 선언시에 타입을 지정해야한다.

클래스 이름<int> A // A는 int의 자료형으로 template가 지정됨
클래스 이름<std::string> B // B는 std::string의 자료형으로 template가 지정됨

중첩 클래스 템플릿

클래스 내부에 클래스 템플릿을 선언할 수 있는데, 클래스나 클래스 템플릿 내에 또다른 템플릿을 정의한 것은 멤버 템플릿이다.

이런 멤버 템플릿 중에서도 클래스 템플릿을 중첩 템플릿을 중첩 클래스 템플릿이라고 한다.

중첩 클래스 템플릿은 바깥쪽 클래스의 범위 내에서 클래스 템플릿으로 선언된다.

하지만 정의는 바깥쪽 클래스의 범위 내에서 뿐만이 아니라 범위 밖에서도 선언 가능하다.

클래스 템플릿의 특징

• 하나 이상의 템플릿 인수를 가질 수 있다.
• 디폴트 템플릿 인수를 명시할 수 있다.
• 클래스 템플릿을 기초 클래스로 상속할 수 있다.

명시적 특수화

함수 템플릿과 마찬가지로 클래스 템플릿도 템플릿 인수에 대해 특수화할 수 있다.

template <> class 클래스 이름<double> {...};

double형에 대한 동작만 변경하는 명시적 특수화.

부분 특수화

만약 템플릿 인수가 두 개 이상이고, 그 중 일부에 대해서만 특수화를 해야 할 때는 부분 특수화를 사용할 수 있다.

방법은 아래와 같다.

// 원본
template <typename T1, typename T2>
class X
{...};

// 부분 특수화[T1은 특수화 되지 않는다.]
template <typename T1> class X<T1, double> {...};

// 명시적 특수화
template <> class X<doulbe, double> {...};

과거의 캐스팅

double	d = 3.141592;
int	conv_i = (int)d;

C에서 사용했었던 자료형의 형 변환이다.

C++에서의 캐스팅 종류

1. static_cast
   • 컴파일 단계에서 형 변환에 대한 안정성 검사를 한다.
   • 기본 자료형 간의 형 변환.
   • 부모-자식 클래스 사이의 형 변환은 가능하지만 안전하진 않다.
2. dynamic_cast
   • 런타임 단계에서 형 변환에 대한 안정성 검사를 한다.
   • 부모-자식 클래스 사이의 형 변환이 안전하게 처리한다.
   • 단, 자식 클래스에서 부모 클래스로 형변환이 가능하다.
   • 부모 클래스에서 자식 클래스로 형 변환은 하나 이상의 가상 함수를 가진 다향성 클래스에 한해서만 가능하다.
3. reinterpret_cast
   • 포인터/참조와 관련된 형 변환만 가능하다.
   • 막무가내의 형 변환이 가능하다.(말 그대로 재해석)
4. const_cast
   • const의 성질을 제거하기 위한 형 변환이다.
   • 하지만 const의 성질을 제거했더라도 실제 데이터를 직접 접근하여 변경하지는 못한다.

상속

클래스 상속이란 기존에 정의된 클래스의 모든 멤버 변수와 멤버 함수를 사용할 수 있는 새로운 클래스를 만드는 것이다.

이는 기존에 존재하는 클래스를 재활용하거나 공통되는 파트를 제거할 수 있어 유용하다.

파생 클래스

파생 클래스에는 기초 클래스의 접근할 수 있는 모든 멤버 변수들이 저장되고 모든 멤버 함수들을 사용할 수 있다.

단, 기초 클래스의 private 멤버에는 접근할 수 없다.(즉, private 멤버가 존재한다면 초기화해줄 생성자는 필수!)

오버 라이딩

오버 로딩(overloading)은 서로 다른 매개변수를 갖는 여러 가지의 함수를 만드는 것인데,

오버 라이딩(overriding)은 이미 정의된 함수를 무시, 새롭게 같은 이름으로 만드는 것이다.

주의할 점은 오버 라이딩은 함수의 동작만 재정의하는 것이므로 함수의 원형은 같아야 한다.

방법은 두 가지이다.

1. 파생 클래스에서 직접 오버라이딩
2. 가상 함수를 이용해서 오버라이딩

파생 클래스에서 직접 오버 라이딩하는 것은 말 그대로다.

그렇지만 이는 문제 될 수 있는 상황이 있다.

    기초 클래스 *C
    기초 클래스 A
    파생 클래스 B

    C = &A
    C->오버라이딩된 함수---------------1
    C = &B
    C->오버라이딩된 함수---------------2

두 개의 결과는 기초 클래스의 함수가 호출된다.

이에 대한 이유는 C++의 컴파일러는 포인터의 타입으로 함수를 호출하기 때문이다.

이러한 문제 때문에 우리는 가상 함수를 이용할 수 있다.

파생 클래스에서 가상 함수(virtual)로 오버 라이딩했을 때 위의 예시를 사용하면,

A는 기초 클래스의 함수 호출, B는 파생 클래스의 함수 호출이 된다.

가상 함수(virtual)

기초 클래스에서 virtual을 사용하여 가상 함수를 선언하면, 파생 클래스에서 재정의된 멤버 함수도 자동으로 가상 함수가 된다.

다중 상속의 문제점

1. 상속받은 기초 클래스들에서 같은 이름의 멤버가 존재할 수도 있다.
2. 하나의 클래스를 간접적으로 두 번 이상 상속받을 가능성이 있다.
3. 가상 클래스가 아닌 기초 클래스를 다중 상속하면, 기초 클래스 타입의 포인터로 파생 클래스를 가리킬 수 없다.

바인딩

C++ 컴파일러는 함수를 호출할 때 정확한 메모리 위치, 어느 블록에 있는 함수를 호출하는지 알고 있어야 한다.

그래서 어떤 블록인지 지정하는 것을 바인딩이라고 한다.

가상 함수가 아닌 멤버 함수는 정적 바인딩(컴파일 타임에 고정된 메모리 주소로 변환)을 하게 된다.

하나, 가상 함수는 프로그램이 실행될 때 객체를 결정하기에 컴파일 타임에 객체를 특정할 수 없다.

그래서 가상 함수는 런타임에 올바른 함수가 실행될 수 있게 동적 바인딩을 해주어야 한다.

이에 관한 이야기는 컴파일러마다 다르다.

일반적으로는 가상 함수들의 주소를 갖고 있는 가상 함수 테이블을 탐색하여 호출한다.

가상 소멸자

기초 클래스의 소멸자는 가상으로 선언해주어야 한다.

그 이유는 가상 소멸자로 선언이 되어있어야 호출된 클래스의 소멸자를 호출하지 않고 내부까지 소멸자를 호출하게 될 테니깐.

순수 가상 함수

순수 가상 함수는 가상 함수와 기능은 같지만 한 가지 제한점이 있다.

반드시 함수를 재정의 해야 한다는 점이다.

순수 가상 함수는 일반적으로 함수의 동작을 정의하는 함수가 없다.

그렇기에 파생 클래스에서 재정의하지 않으면 사용할 수 없다.

추상 클래스

하나 이상의 순수 가상 함수를 포함하는 클래스를 추상 클래스라고 한다.

추상 클래스를 상속받는 클래스는 가상 메소드를 반드시 구현하지 않아도 된다.

다중상속이 불가능하다.

인터페이스

인터페이스에서는 구현이 없으며 가상 소멸자와 순수가상함수만 포함되어있다.

인터페이스에서는 상태와 구현이 전혀 없다.

인터페이스를 구현하는 클래스는 인터페이스의 모든 메소드를 구현해야한다.

인터페이스는 다중상속이 가능하다.

그래픽스를 공부한지 어언 4~5달이 지난것 같다.

mlx는 이미 다 까먹고 새것을 보는 느낌이다.

나만 그런건 아닐거라 믿는다.

일단 처음해야할 것 예전에 봤던 mlx를 이용한 예제들을 다시 재구현한다.

대신 이전에는 OpenGL을 사용했는데 이는 정적라이브러리라고 한다.

정적라이브러리는 말만 들어도 뭔가 한꺼번에 사용할 것 같은 느낌.

동적라이브러리인 mms를 사용하는 것이 좋다는 슬랙에서의 말씀들을 듣고 다시 시작이다.

동적라이브러리를 더 찾아보면 좋겠지만 이미 정리를 너무 잘해둔 분들이 있어서 간단명료하게 적기만 할 것이다.

1. intra에서 tar파일을 다운받고 압축을 푼다.
2. 디렉토리의 이름을 mlx로 간편하게 바꾼 후 들어간다.
3. 이제 make를 치면? Warning들과 Error의 향연일 것이다.
4. 여기서 잘 보면 error중에 "UInt32(1)"에 error가 떠있는데 이것을 boolean_t(1)로 바꿔준다.
5. 그리고 make를 해보면 "libmlx.dylib"라는 파일이 생긴다.
6. 그리고 예제를 만들어서 "-L../mlx -Imlx -framework OpenGL -framework ÅppKit" 플래그를 사용하여 컴파일.
7. 실행파일을 실행하면 Abort가 뜨는데 "dyld: (대충)라이브러리 못찾음" 이런 경고문을 볼 수 있다.
8. mlx의 절대 경로를 "DYLD_LIBRARY_PATH"라는 환경변수에 지정해주면 실행할 수 있다!

예제 시작

ex01

#include "../../mlx/mlx.h"

int     main(void)
{
    void    *mlx;
    void    *win;

    mlx = mlx_init();
    win = mlx_new_window(mlx, 500, 500, "mlx_project");
    mlx_loop(mlx);
    return (0);
}

위의 코드를 써보면 이미지를 간단하게 500x500의 사이즈로 열어볼 수 있다.

result

ex02

#include "../../mlx/mlx.h"
#include <stdio.h>
#include <stdlib.h>

#define X_EVENT_KEY_PRESS   2
#define X_EVENT_KEY_RELEASE 3
#define X_EVENT_KEY_EXIT    17

#define KEY_ESC             53
#define KEY_Q               12
#define KEY_W               13
#define KEY_E               14
#define KEY_R               15
#define KEY_A               0
#define KEY_S               1
#define KEY_D               2

typedef struct s_param
{
    int     x;
    int     y;
    char    str[3];
}   t_param;

void    param_init(t_param *param)
{
    param->x = 3;
    param->y = 4;
    param->str[0] = 'a';
    param->str[1] = 'b';
    param->str[2] = '\0';
}

int     key_press(int keycode, t_param *param)
{
    static int  a;

    if (keycode == KEY_W)
        param->y += 1;
    else if (keycode == KEY_S)
        param->y -= 1;
    else if (keycode == KEY_A)
        param->x -= 1;
    else if (keycode == KEY_D)
        param->x += 1;
    else if (keycode == KEY_ESC)
        exit(0);
    printf("Current Position : (%d, %d)\n", param->x, param->y);
    return (0);
}

int main(void)
{
    void    *mlx;
    void    *win;
    t_param param;

    param_init(&param);
    mlx = mlx_init();
    win = mlx_new_window(mlx, 500, 500, "mlx_project");
    printf("------------------------------------------\n");
    mlx_hook(win, X_EVENT_KEY_PRESS, 0, &key_press, &param);
    mlx_loop(mlx);
    return (0);
}

위의 코드는 이미지를 열고서 key event를 이용해서 내부의 변수를 조정하는 것을 할 수 있다.

당장 보이는 변화는 없다 그렇지만 이를 통해서 할 수 있는것은 많다고 본다.

result

ex03

이제는 색을 입히는데 Ray Tracing in One Week를 C언어로 변형해서 따라해보자.

그냥 색을 입히는 것이 아니라 그라데이션을 그려주는 작업을 할 것 이다.

#include <stdio.h>
#include <stdlib.h>
#include "../../mlx/mlx.h"

# define WIN_WIDTH 256
# define WIN_HEIGHT 256

# define IMG_WIDTH 256
# define IMG_HEIGHT 256

typedef struct  s_img
{
    void    *img_ptr;
    char    *data;
    int     size_l;
    int     bpp;
    int     endian;
}   t_img;

typedef struct s_mlx
{
    void    *mlx_ptr;
    void    *win;
}   t_mlx;

void	my_mlx_pixel_put(t_img *img, int x, int y)
{
    int     r;
    int     g;
    int     b;
    int     rgb_color;
    char	*dst;

    r = (int)(255.999 * ((double)x / (IMG_WIDTH - 1)));
    g = (int)(255.999 * ((double)y / (IMG_HEIGHT - 1)));
    b = (int)(255.999 * 0.25);
    rgb_color = (r << 16) | (g << 8) | b;
    dst = img->data + (x * (img->bpp / 8)) + ((IMG_HEIGHT - y - 1) * img->size_l);
	*(unsigned int *)dst = rgb_color;
}

int main(void)
{
    t_mlx   *mlx;
    t_img   img;
    int     count_w;
    int     count_h;

    mlx = malloc(sizeof(t_mlx));
    mlx->mlx_ptr = mlx_init();
    mlx->win = mlx_new_window(mlx->mlx_ptr, WIN_WIDTH, WIN_HEIGHT, "Gadation");
    img.img_ptr = mlx_new_image(mlx->mlx_ptr, IMG_WIDTH, IMG_HEIGHT);
    img.data = mlx_get_data_addr(img.img_ptr, &img.bpp, &img.size_l, &img.endian);
    count_h = IMG_HEIGHT;
    while (--count_h >= 0)
    {
        count_w = -1;
        while (++count_w < IMG_WIDTH)
            my_mlx_pixel_put(&img, count_w, count_h);
    }
    mlx_put_image_to_window(mlx->mlx_ptr, mlx->win, img.img_ptr, 0, 0);
    mlx_loop(mlx->mlx_ptr);
    free(mlx);
    return (0);
}

여기서는 좌표에 따른 값을 RGB로 변환하여 나타내 주는 것이다.

R과 G는 0~ 255.999까지의 범위를 x, y 좌표로 인해 만들어 준다.

B는 255.999 / 4의 값으로 고정이다.

그리고 비트연산 후 위치를 찾아서 넣는다.

result

결과를 보면 x축과 y축이 좌측 하단에 있는것을 확인할 수 있다. ((0, 0)이면 B만 남을테니까.)

이는 img의 data에서 위치를 찾을 때 y축을 반전 시켜주면 된다.

ex04

이번에는 하늘을 표현해보자.

#include <stdio.h>
#include <stdlib.h>
#include "../../mlx/mlx.h"
#include "vector.h"
#include "ray.h"

# define WIN_WIDTH 800
# define WIN_HEIGHT 600

# define IMG_WIDTH 800
# define IMG_HEIGHT 600

typedef struct  s_img
{
    void    *img_ptr;
    char    *data;
    int     size_l;
    int     bpp;
    int     endian;
}   t_img;

typedef struct s_mlx
{
    void    *mlx_ptr;
    void    *win;
}   t_mlx;

void	my_mlx_pixel_put(t_img *img, t_cam cam, int x, int y)
{
	char	*dst;
    double  u;
    double  v;
    double  t;
    int     rgb_color;
    t_ray   ray;
    t_vec   color;

    u = (double)x / (double)(IMG_WIDTH - 1);
    v = (double)y / (double)(IMG_HEIGHT - 1);
    ray = make_ray(cam.origin, sub_vec(add_vec(add_vec(cam.left_bottom_corner, \
                                                mul_vec_(cam.horizontal, u)), \
                                                mul_vec_(cam.vertical, v)), \
                                                cam.origin));
    t = 0.5 * (unit_vec(ray.direction).y + 1.0);
    color = mul_vec_(add_vec(mul_vec_(make_vec(1.0, 1.0, 1.0), (1.0 - t)), \
                    mul_vec_(make_vec(0.5, 0.7, 1.0), t)), 255.999);
    rgb_color = ((int)color.x << 16) | ((int)color.y << 8) | (int)color.z;
	dst = img->data + (x * img->bpp / 8) + ((IMG_HEIGHT - y - 1) * img->size_l);
	*(unsigned int *)dst = rgb_color;
}

int main(void)
{
    t_mlx   *mlx;
    t_img   img;
    t_cam   cam;
    int     count_w;
    int     count_h;
    double  aspect_ratio;

    mlx = malloc(sizeof(t_mlx));
    mlx->mlx_ptr = mlx_init();
    mlx->win = mlx_new_window(mlx->mlx_ptr, WIN_WIDTH, WIN_HEIGHT, "Sky");
    img.img_ptr = mlx_new_image(mlx->mlx_ptr, IMG_WIDTH, IMG_HEIGHT);
    img.data = mlx_get_data_addr(img.img_ptr, &img.bpp, &img.size_l, &img.endian);
    aspect_ratio = 4.0 / 3.0;
    cam = make_cam(make_vec(0, 0, 0), 2.0 * aspect_ratio, 2.0, 1.0);
    count_h = IMG_HEIGHT;
    while (--count_h >= 0)
    {
        count_w = -1;
        while (++count_w < IMG_WIDTH)
            my_mlx_pixel_put(&img, cam, count_w, count_h);
    }
    mlx_put_image_to_window(mlx->mlx_ptr, mlx->win, img.img_ptr, 0, 0);
    mlx_loop(mlx->mlx_ptr);
    free(mlx);
    return (0);
}

우리가 보는 시선, 광선은 3차원의 벡터로 표현이 가능하다.

그렇기에 vector구조체를 만들어주고 각종 연산들을 수행하는 함수들을 만든다.

예를 들면 사칙연산, 내적, 외적, 단위벡터화를 말할 수 있다.

Ray라는 구조체를 추가한다. 나는 Ray를 광선의 정보로 생각했다.

Ray는 origin과 direction이라는 두 개의 벡터를 갖고있다.

이는 $P(t) = A + Bt = origin + (direction * t)$와 같은 말이며 해석은 다음과 같다.

• 광원이 존재해야 광선도 존재한다.
• 원점으로부터 광원의 위치를 나타내는 벡터가 A(origin)이다.
• 광원으로부터 뻗어나가는 광선의 벡터가 B이다.
• 그렇다면 t는 무엇이냐? 이는 광선의 강도이다.

이로서 Ray를 통해 광선의 정보를 알 수 있다.

또 다른 cam이라는 구조체를 추가한다. 사람으로 치면 눈이다.

구조체 cam의 구조는 Ray Tracing에 사용되는 변수들을 갖고있다.

viewport_width, viewport_height, focal_length, etc ....

이것을 어떻게 사용해야할지 모르기 때문에 Ray Tracing에 대해 자세히 파고들어가보자.

Ray Tracing은 우리가 보고있는 3차원의 형상을 2차원으로 해석한다.

왜냐? 우리가 표현해야할 화면은 2차원이 될테니까.

즉, 동적으로 있는 배경을 정적으로 바라보고 있다고 생각해야 한다.

그렇게 하려면 정지된 세계예서 우리가 보고있는 장면의 크기를 결정해야 한다.

여기서 viewport는 '우리가 보고있는 장면'을 의미한다.

또한, 여기서 viewport와 기준점과의 거리를 focal_length라고 할 수 있다.

한 가지 더 생각하면 무조건 화면의 크기와 보고있는 장면이 같다고 볼 수는 없다.

이게 무슨 말이냐 하면 1600x900의 화면에 800x600의 장면으로 나타낼 수 있다는 것이다.

이를 어떻게 하느냐 하면 화면의 기준에서 (0, 0)은 좌측 하단에 존재한다 볼 수 있다.

하지만 장면의 기준에서 좌측 하단이 (0, 0)이 아니기 때문에 계산을 통해 알 수 있다.

$Left\ Bottom\ Corner = origin(현재 눈의 위치) - (\frac{view\ port_w} {2}, \frac{view\ port_h} {2}, focal\ length)$

이 정도면 이해가 갈 것이라 생각한다.

그렇게 되면 my_mlx_pixel_put에서 ray를 생성하는데 여기서 direction을 계속해서 정의해준다.

이는 픽셀의 기준으로 생각하면 되는데 우리가 보는 viewport는 픽셀들의 조합이다.

즉, 픽셀 하나씩 확인하면서 광원에서의 광선을 재정의하는 과정인 것이다.

$t = \frac {unit(ray.direction.y)\ +\ 1} {2}$

위 수식으로 t값을 정의한다. (이거 왜 이렇게 정의 되는지 모르겠음)

그리고 선형 혼합(Linear Blend)의 식을 통해서 색을 정해준다.

$선형 혼합 => result = (1 - t) * First\ Color + t * Last\ Color$

이렇게 First Color는 흰색, Last Color는 푸른색이 되어서 색감을 결정해준다.

result

ex04

이제 우리는 새빨간색의 구를 화면에 표시할 것이다.

이것은 생각했을 때 정말 간단하게 생각하면 된다.

구의 좌표와 크기를 설정해주고 만들어준 뒤 캠에서 색에대한 정보를 정의해줄때 구를 보고 있다면 새빨간색을 정의해주면 되는 것이다.

그러기 위해서는 눈과 픽셀을 정의한 벡터와 구가 만나는지 확인해주면 된다.

이를 확인하기 위해선 우리는 교점에 대해 확인하면 된다.

구의 테두리 좌표를 하나씩 전부 갖고 있을 수는 없으니 함수를 사용하자.

$구의 함수 => x^2 + y^2 + z^2 = r^2$

위 함수를 보면 구조체 sphere가 갖고 있어야할 정보는 구의 중심(x, y, z)과 반지름r이다.

typedef struct  s_sphere
{
    t_vec   centor;
    double  radius;
}   t_sphere;

그리고 우리는 구와의 교점을 찾을 수식을 계산할 함수를 만들어야 한다.

int         hit_sphere(t_sphere sp, t_ray ray)
{
    t_vec   oc;
    double  a;
    double  b;
    double  c;
    double  discriminant;

    oc = sub_vec(ray.origin, sp.centor);
    a = dot_vec(ray.direction, ray.direction);
    b = dot_vec(oc, ray.direction);
    c = dot_vec(oc, oc) - (sp.radius * sp.radius);
    discriminant = b * b - a * c; // 점화식
    if (discriminant >= 0)
        return (1);
    else
        return (0);
}

조금 어려운 벡터의 개념이므로 잘 작성해보도록 하겠다.

일단 구의 중심을($C_1$, $C_2$, $C_3$)라고 생각했을 때의 구의 함수는 아래와 같다.

$(x - C_1)^2 + (y - C_2)^2 + (z - C_3)^2 = r^2$

여기서 반지름r은 눈에서 구의 중심까지의 벡터(C)와 눈에서 구의 테두리 좌표까지의 벡터(P)로 표현할 수 있다.

즉, $r^2 = (P - C) \cdot (P - C)$가 된다.

그리고 위 수식을 Ray와 관련해서 쓰게 된다면 $P(t) = A + tB$로 아래와 같이 표현할 수 있다.

$r^2 = (A + Bt - C) \cdot (A + Bt - C) = (Bt + (A - C))$

$(B \cdot B)t^2 + 2tB \cdot (A - C) + (A - C) \cdot (A - C) - r^2 = 0$

위 수식은 t에 관한 2차 방정식으로 근의 공식을 이용하면 t의 값이 존재하는지 확인할 수 있다.

$근의 공식 = \frac {-b \pm \sqrt {b^2 - 4ac}} {2a} = \frac {-b_{half} \pm \sqrt {b_{half}^2 - ac}} {a}$

여기서 $b_{half}^2 - ac >= 0$를 충족한다면 t의 값이 존재하는 것으로 교점이 있다는 것을 확인할 수 있다.

따라서 계산식은 아래와 같다.

$a = (B \cdot B)$

$b = B \cdot (A - C)$

$c = (A - C) \cdot (A - C) - r^2$

    if (hit_sphere(img->sp, ray))
        color = mul_vec_(make_vec(1.0, 0.0, 0.0), 255.999);
    else
    {
        t = 0.5 * (unit_vec(ray.direction).y + 1.0);
        color = mul_vec_(add_vec(mul_vec_(make_vec(1.0, 1.0, 1.0), (1.0 - t)), \
                        mul_vec_(make_vec(0.5, 0.7, 1.0), t)), 255.999);
    }

그렇게 되면 결과적으로 my_mlx_pixel_put에서 color를 결정하는 것이 된다.

hit_sphere에서의 결과값이 1이라면 구와 교점이 있는 것으로 붉은색을 칠한다.

result

위와 같이 구가 형상화 된다.

ex05

이제 구에도 그라데이션을 그려봅시다!

double  hit_sphere(t_sphere sp, t_ray ray)
{
    t_vec   oc;
    double  a;
    double  b;
    double  c;
    double  discriminant;

    oc = sub_vec(ray.origin, sp.centor);
    a = dot_vec(ray.direction, ray.direction);
    b = dot_vec(oc, ray.direction);
    c = dot_vec(oc, oc) - (sp.radius * sp.radius);
    discriminant = b * b - a * c; // 점화식
    if (discriminant < 0)
        return (-1.0);
    else
        return ((-b + sqrt(discriminant)) / a); // 근의 공식
}

바뀐것은 근의 값을 결과값으로 반환한다는 것뿐이다.

    t = hit_sphere(img->sp, ray);
    if (t > 0.0)
    {
        tmp = unit_vec(sub_vec(at_ray(ray, t), img->sp.centor));
        color = mul_vec_(add_vec(make_vec(1.0, 1.0, 1.0), tmp), 255.999 * 0.5);
    }
    else
    {
        t = 0.5 * (unit_vec(ray.direction).y + 1.0);
        color = mul_vec_(add_vec(mul_vec_(make_vec(1.0, 1.0, 1.0), (1.0 - t)), \
                        mul_vec_(make_vec(0.5, 0.7, 1.0), t)), 255.999);
    }

이렇게 t의 값을 결정하고 양수일 때 색을 결정하도록 해주면 된다.

result

사실 근은 2개로 적용된다.

Phong Lighting Model

다음 예제를 진행하기 전에 phong Lighting Model에 대한 이론적 부분을 알고 가야한다.

phong Lighting Model은 기본적으로 3가지 빛의 요소로 계산이 가능하다.

1. Ambient Reflection(주변광)
   • 다른 물체에 의한 반사광, 대기 중의 산란광 등을 단순화시킨 요소이다.(빛이 닿지 않아도 어둡진 않다.)
   • $I = k_aI_a$
   • $k_a는 주변광 계수, I_a는 광원의 세기$
2. Diffuse Reflection(확산광 / 난반사)
   • 같은 방향으로 빛이 들어와도 서로 다른 방향으로 퍼지는 형태이다.
   • $I\ =\ k_dI_dcos\theta\ =\ k_dI_d(\hat N \cdot \hat L)$
   • $I_d는\ 광원의\ 세기,\ k_d는\ 확산광\ 계수,\ \hat N은\ 단위\ 법선\ 벡터,\ \hat L은\ 단위\ 광원\ 벡터$
3. Specular Reflection(경면광 / 정반사)
   
   • $I\ =\ k_sI-lcos^n\phi\ =\ k_sI-l(\hat R \cdot \hat V)^n$
   • $k_s는\ 경면광\ 계수,\ I_s는\ 광원의\ 세기,\ ^n는 광택 계수$

ex06

일단 ambient Reflection만을 적용시킨다.

그리고 광원이 있어야 하기 때문에 light라는 구조체를 추가함과 동시에 다른 구조체의 요소를 추가해주었다.

typedef struct  s_rec
{
    t_vec   p;
    t_vec   normal;
    double  tmin;
    double  tmax;
    double  t;
    int     front_face;
    t_vec   ambient;
    t_vec   albedo; // 추가
}   t_rec;

typedef struct  s_sphere
{
    t_vec   centor;
    double  radius;
    t_vec   albedo; // 추가
}   t_sphere;

typedef struct s_light // 생성
{
    t_vec   origin;
    t_vec   light_color;
    double  bright_ratio;
}   t_light;

표현한 것을 잘 볼 수 있게 바닥처럼 생각할 수 있는 큰 구 하나와 색의 차이가 있는 2개의 구를 그려서 보자!

#include <stdio.h>
#include <stdlib.h>
#include "../../mlx/mlx.h"
#include "vector.h"
#include "ray.h"

# define WIN_WIDTH 800
# define WIN_HEIGHT 600

# define IMG_WIDTH 800
# define IMG_HEIGHT 600

typedef struct  s_img
{
    void        *img_ptr;
    char        *data;
    int         size_l;
    int         bpp;
    int         endian;
    t_sphere    *sp;
}   t_img;

typedef struct s_mlx
{
    void        *mlx_ptr;
    void        *win;
}   t_mlx;

t_vec   phong_lighting(t_light light, t_rec rec)
{
    t_vec   light_color;

    light_color = make_vec(0, 0, 0);
    light_color = add_vec(light_color, rec.ambient);
    return (min_vec(mul_vec(light_color, rec.albedo), make_vec(1, 1, 1)));
}

void	my_mlx_pixel_put(t_img *img, t_cam cam, int x, int y)
{
    char	*dst;
    double  	u;
    double  	v;
    double  	t;
    int     	rgb_color;
    t_ray   	ray;
    t_vec   	color;
    t_vec   	tmp;
    t_rec   	rec;
    t_light 	light;

    u = (double)x / (double)(IMG_WIDTH - 1);
    v = (double)y / (double)(IMG_HEIGHT - 1);
    ray = make_ray(cam.origin, sub_vec(add_vec(add_vec(cam.left_bottom_corner, \
                                                mul_vec_(cam.horizontal, u)), \
                                                mul_vec_(cam.vertical, v)), \
                                                cam.origin));
    rec.ambient = mul_vec_(make_vec(1, 1, 1), 0.1); // ambient set
    if (is_hit_sphere(img->sp, ray, &rec, 9999))
    {// color of phong model
        light = make_light(make_vec(0, 5, 0), make_vec(1, 1, 1), 0.5); // 빛 생성
        tmp = phong_lighting(light, rec); // phong model에 따른 색 분포 벡터 생성
        color = mul_vec_(tmp, 255.999);
    }
    else
    {
        t = 0.5 * (unit_vec(ray.direction).y + 1.0);
        color = mul_vec_(add_vec(mul_vec_(make_vec(1.0, 1.0, 1.0), (1.0 - t)), \
                        mul_vec_(make_vec(0.5, 0.7, 1.0), t)), 255.999);
    }
    rgb_color = ((int)color.x << 16) | ((int)color.y << 8) | (int)color.z;
	dst = img->data + (x * img->bpp / 8) + ((IMG_HEIGHT - y - 1) * img->size_l);
	*(unsigned int *)dst = rgb_color;
}

int main(void)
{
    t_mlx   *mlx;
    t_img   img;
    t_cam   cam;
    int     count_w;
    int     count_h;

    mlx = malloc(sizeof(t_mlx));
    mlx->mlx_ptr = mlx_init();
    mlx->win = mlx_new_window(mlx->mlx_ptr, WIN_WIDTH, WIN_HEIGHT, "Phong Model");
    img.img_ptr = mlx_new_image(mlx->mlx_ptr, IMG_WIDTH, IMG_HEIGHT);
    img.data = mlx_get_data_addr(img.img_ptr, &img.bpp, &img.size_l, &img.endian);
    img.sp = malloc(sizeof(t_sphere) * 3);
    img.sp[0] = make_sphere(make_vec(-1, 0, -5), 2, make_vec(0.5, 0, 0));
    img.sp[1] = make_sphere(make_vec(1, 0, -5), 2, make_vec(0, 0.5, 0));
    img.sp[2] = make_sphere(make_vec(0, -1000, -100), 999, make_vec(1, 1, 1));
    cam = make_cam(make_vec(0, 0, 0), 2.0 * 8.0 / 6.0, 2.0, 1.0);
    count_h = IMG_HEIGHT;
    while (--count_h >= 0)
    {
        count_w = -1;
        while (++count_w < IMG_WIDTH)
            my_mlx_pixel_put(&img, cam, count_w, count_h);
    }
    mlx_put_image_to_window(mlx->mlx_ptr, mlx->win, img.img_ptr, 0, 0);
    mlx_loop(mlx->mlx_ptr);
    free(img.sp);
    free(mlx);
    return (0);
}

설명할 것은 ambient의 수식에 관한 것 뿐이다.

albedo는 $k_a$를 뜻해서 반사광 계수를 벡터화 시킨것이다.(색의 벡터을 뜻하는 것으로 추측)

이것은 make_sphere에서 마지막 변수로 정의되었고 이를 rec가 가져온다.

그리고 처음 light_color는 빛의 색을 말하지만 후에 light_color는 빛의 강도까지 표현되는 것으로 생각하고 있다.(색에도 빛이 있으니까)

result

이렇게 보면 두개의 구가 겹쳐있는데 이 두개의 구가 정말 잘...보면 색이 사알짝 다르다.

구분이 안가면 패스!(나도 잘 안감ㅎ)

ex07

이제 diffuse와 specular를 적용시키면 된다.

참고로 수식이해가 된다면 굉장히 쉽게 적용할 수 있는 상황이 된다.

일단 추가되는 함수는 아래에 있다.

t_vec   reflect(t_vec v, t_vec n)
{
    return (sub_vec(v, mul_vec_(n, dot_vec(v, n) * 2.0)));
}

t_vec   specular_lighting(t_light light, t_rec rec, t_ray ray)
{
    t_vec   light_dir;
    t_vec   specular;
    t_vec   view_dir;
    t_vec   reflect_dir;
    double  spec;
    double  ksn;
    double  ks;

    light_dir = unit_vec(sub_vec(light.origin, rec.p));
    view_dir = unit_vec(mul_vec_(ray.direction, -1.0));
    reflect_dir = reflect(mul_vec_(light_dir, -1.0), rec.normal);
    ksn = 64;
    ks = 0.5;
    spec = pow(fmax(dot_vec(view_dir, reflect_dir), 0.0), ksn);
    specular = mul_vec_(mul_vec_(light.light_color, ks), spec);
    return (specular);
}

t_vec   diffuse_lighting(t_light light, t_rec rec)
{
    t_vec   diffuse;
    t_vec   light_dir;
    double  kd;

    light_dir = unit_vec(sub_vec(light.origin, rec.p));
    kd = fmax(dot_vec(rec.normal, light_dir), 0.0);
    diffuse = mul_vec_(light.light_color, kd);
    return (diffuse);
}

각각의 vec의 합을 반환하면 된다.

    light_color = add_vec(light_color, rec.ambient);
    light_color = add_vec(light_color, diffuse_lighting(light, rec));
    light_color = add_vec(light_color, specular_lighting(light, rec, ray));
    return (min_vec(mul_vec(light_color, rec.albedo), make_vec(1, 1, 1)));

result

아래 그림은 ambient와 diffuse를 적용시킨 사진이다.

아래 그림은 ambient, diffuse 그리고 specular를 적용시킨 phong model인 것이다.

마지막 그림에서 광원의 존재를 알수 있었다~!

예제는 오늘로 끝!

보기 전에 혹시 떠올리셨나요? '아이디어'

제가 과거에 정리했던 내용이지만 전부 맞다고 생각이 들진 않아요.

본인의 아이디어를 떠올려보고 참고용으로 봐주시면 감사하겠어요.

1. prompt

prompt를 만들어주는 방법은 두 가지 방법이 있다.

첫 번째는 터미널 제어 속성을 수정해주는 방식이 있다.

두 번째는 readline을 이용한 방식이 있다.

첫 번째 방법은 시도해봤지만 너무 복잡하게 이어져있어서 두 번째 방법으로 구현했다.

일단 readline을 brew로 설치해야한다.

그리고 readline이 설치된 경로들을 알고있어야 한다.

컴파일시에 지정을 해줘야 하기 때문이다.

readline은 여러가지 변수들과 함수들을 사용할 수 있다.

하지만 함수들은 허용된 것들만 사용가능하고 변수는 따로 extern 해주어야 사용이 가능하다.

일단 허용함수들을 살펴보자.

rl_on_new_line : readline실행 중 다음줄로 이동되었다고 설정해주는 함수이다.

rl_replace_line : readline실행 중 들어온 입력을 첫번째 인자로 다시 설정해주는 함수이다.

rl_redisplay : readline실행 중 다시 readline을 실행할 때 사용하는 함수이다.

이들은 signal중 Ctrl + C를 제어할 때 사용된다.

변수들을 확인해보자.

rl_catch_signals : readline 실행중에 signal을 표시할지 안할지 설정하는 변수이다.(default = 1)

이제 readline을 알아보자.

readline은 엔터가 입력됬을때 입력된 값을 반환한다.

또한 add_history로 키보드 화살표 위, 아래키를 이용해서 이전 커멘드를 다시 표시할 수 있다.

이렇게 readline으로 prompt 끝!

2. tokenizing

tokenizing실행 전에 Error Check를 먼저 실행되어야 한다.

Error Check는 여러가지가 있다.

1. ', "로 문자열을 열었지만 닫지 않은 경우
2. '|', ';'를 연속적으로 사용했을 경우
3. 기타 등등(전부 찾기는 힘들다.)

tokenizing은 readline으로 입력된 command를 '|', ';' 기준으로 자르는 과정이다.

1. 과정중에 연속된 space는 하나의 space로 수정해주어야 한다.
2. '$'로 시작하는 문자열은 환경변수를 참조해서 변경시켜주어야 한다.
3. '로 둘러 쌓인 문자열은 수정이 가져와야 한다.(환경변수 참조X, 연속된 space변경X)
4. "로 둘러 쌓인 문자열은 환경변수 참조하여 수정해준다.(환경변수 참조O, 연속된 space변경X)

위 과정으로 자른 문자열들을 queue에 넣어주어야하기 때문에 node에 넣어줄때 자른 token이 '|'라면 pipe인 것을 확인할 수 있는 변수를 만들어 설정해주는다.

또한, node에 넣을때는 space를 기준으로 넣어주는데 ', " 내부는 취급하지 않는다.

tokenizing 끝!

3. 로직

전체적인 로직은 아래와 같다.

1. 모든것을 포함한 구조체 초기화
2. 제작자들의 개성을 나타내 줄 logo 출력
3. inf_loop 시행
   1. readline으로 cmd 입력
   2. cmd의 Error Check
   3. tokenizing
   4. execute
   5. tokenizing된 command_queue 메모리 해제
4. 모든 구조체 메모리 해제

execute는 single command, multi command로 나눈다.

single command는 builtin function일 때만 자식 프로세스를 만들지 않고 실행된다.

왜냐하면 현재 프로세스의 데이터를 직접 수정, 생성해야하기 때문이다.

그 외는 fork를 이용해 자식 프로세스를 만들고 수행시킨다.

4. redirection

redirection은 총 4가지의 구성이 있다.

> {인자} : {인자}를 STDOUT_FILENO로 지정한다. [{인자}라는 파일을 생성(있다면 새로 만든 것처럼 생성)]

< {인자} : {인자}를 STDIN_FILENO로 지정한다.[{인자}라는 파일을 연다.]

>> {인자} : {인자}를 STDOUT_FILENO로 지정한다. [{인자}라는 파일을 생성(있다면 내부 데이터의 가장 끝을 가리켜야 한다.)]

<< {인자} : {인자}를 stop sign으로 취급하고 stop sign이 나올때까지의 문자열들을 STDIN_FILENO로 지정한다.[새로운 파일 생성해서 쓰고 그 파일을 STDIN_FILENO로 지정했다.][이 과정은 home document라고 칭한다.]

여기서 내가 가장 헤메게 된 이유는 하나의 문자열로 생각해서 많이 헤멨다.

이 말이 무슨 뜻이냐면 한꺼번에 처리를 해야한다는 생각이었는데 이는 맞는 말이지만 틀린말이기도 하다.

여러개의 redirection이 온다면 각각 지정하는것은 맞다.

하지만 이를 수행하는 것은 가장 마지막으로 지정한 것이다.

또한, 여러개의 redirection이 있을때 사이사이에 커멘드들이 들어갈 수 있었다.

그렇기에 따로 command를 지정할 수 있는 char **가 필요했다.

예시를 들어보면

$> < a > b1 > b2 cat > b3 -e >> b4

위의 풀이는 a를 STDIN_FILENO로 지정하고 b1, b2, b3, b4를 생성하는데 STDOUT_FILENO는 b4로 지정된 것이다.

또한, command는 'cat -e'으로 들어가게 되어 입력으로는 a가 들어가게 된다.

이를 검증하고 싶다면 'cat -e' 만 따로 bash의 입력으로 넣어주면 표준입력 입력할 수 있는 상황이 되는데 그 지점이 a가 되는 것이다.

그리고 만약 b4가 이미 존재하고 있다면 데이터의 가장 뒤에 a를 insert해주는 상황이 되는 것이다.

요약

command : cat -e

생성된 파일 : b1, b2, b3, b4

STDIN_FILENO : a라는 파일

STDOUT_FILENO : b4라는 파일

5. pipe

위에서 우리는 node당 pipe로 잘렸는지 확인하는 변수를 만들어주었다.

또한, 나는 node에 pipe[2]를 따로 지정해주었다.

pipe로 잘렸다면 사용이 되지만 pipe로 잘리지 않았다면 사용이 안된다.

pipe는 multi command 상황에서 사용된다.

3가지 경우의 수가 있다.

1. 시작전 pipe를 열어주는 경우
2. 자식의 pipe 관리해주는 경우
3. 부모의 pipe 관리해주는 경우

시작전엔 pipe를 열어주는 것 뿐이다.

자식의 pipe관리는 이전 node의 pipe 상태를 보고 pipe[1]를 STDIN_FILENO로 넣어주고,

현재 node의 pipe상태를 보고 pipe[0]를 STDOUT_FILENO로 넣어주는 것을 관리해준다.

부모의 pipe관리는 현재와 이전 노드의 파이프 상태를 보고 pipe를 닫아주는 관리해준다.

즉, 이렇게 관리가 된다면 파이프로 연결되었던 커멘드들을 연결시켜줄 수 있는 상황이 되는 것이다.

6. builtin_function

cd

1. cd or cd ~ -> $HOME참조
2. cd {file_name} -> file_name이 없으면 "minishell: cd: {file_name}: No such file or directory\n"
3. cd - -> $OLDPWD참조 -> 만약 없으면 "minishell: cd: OLDPWD not set\n"
4. cd는 상대/절대 경로를 참조할 수 있다.
5. cd는 인자로 2개 이상 들어온다면 첫번째 경로로 간다.
6. cd로 움직였을경우 PWD, OLDPWD 모두 바뀌어야한다.
7. cd로 처음 움직였을 때, OLDPWD가 없다면 생성해주어야 한다.
8. 성공시 exit_status = 0, 실패시 exit_status = 1

env

1. env는 입력되는 인자가 없어야한다. -> "env: {첫번째 인자}: No such file or directory"
2. env는 node->is_ok가 1인 것만 출력한다. [node->is_ok는 '='의 존재 유무이다. 또한, $?는 -1로 고정]
3. 성공시 exit_status = 0, 실패시 exit_status = 1

export

1. export는 인자없이 들어왔을 때, Ascii code 오름차순 출력한다.[출력시 앞에 "declare -x "를 먼저 출력한다.]\
2. export는 인자없이 들어왔을 때, node->is_ok가 -1이 아닌 것만 출력한다.[node->is_ok 가 0라면 key만 출력하고 '='는 출력X]
3. export는 인자의 첫 문자가  알파벳 혹은 '_'이 아니면 "minishell: export: `인자': not a valid identifier"
4. export는 인자의 첫 문자를 제외하고 숫자가 들어갈 수 있다.['_'이외의 특수문자가 들어가면 3번의 오류출력을 따른다.]
5. export는 인자가 '_' 혼자 들어왔을 때 무시한다.[환경변수를 나타내지도 추가하지도 않음]
6. export는 인자들은 반드시 나눠져있다.[node->command는 'char **' 이다.]
7. export는 환경 변수를 추가할때 '='가 있는 인자는 node->is_ok=1 아니라면 node->is_ok=0이다.
8. export는 중복되는 변수가 있다면 수정해준다.
9. 성공시 exit_status = 0, 실패시 exit_status = 1

unset

1. unset은 인자없이 들어왔을 때 행동없이 끝난다.
2. unset은 인자가 여러개 들어올 수 있다.
3. unset은 인자가 환경변수에 없다면 행동없이 끝난다.
4. unset는 인자의 첫 문자가  알파벳 혹은 '_'이 아니면 "minishell: unset: `인자': not a valid identifier"
5. unset는 인자의 첫 문자를 제외하고 숫자가 들어갈 수 있다.['_'이외의 특수문자가 들어가면 3번의 오류출력을 따른다.]
6. 성공시 exit_status = 0, 실패시 exit_status = 1

echo

1. echo는 인자없이 들어왔을 때 개행출력.
2. echo는 인자가 여러개 들어올 수 있다.
3. 내 생각엔 그냥 출력하면 될듯?[이미 tokenizing에서 "와 '구분을 전부 해놨음]
4. exit_status = 0;

exit

1. exit는 인자가 없으면 0
2. exit는 인자는 256으로 나눈 나머지가 exit_status
3. exit {인자} -> 인자가 숫자가 아니면 "minishell: exit: {인자}: numeric argument required" [exit_status = 255]
4. exit는 여러개의 인자가 들어오면 "minishell: exit: too many arguments" [exit_status = 1]
5. 3번이 4번보다 우선순위이다.
6. exit는 single command일때 에러가 나도 exit를 출력하고 종료된다.[multi command일때는 에러만 출력한다.]
7. 음수가 들어올 수 있다. 음수일 땐 256을 뺀 값이다.
8. exit는 인자의 범위가 long long의 범위이다.[넘어가면 3번의 결과]

혼자 정리한 builtin_function은 여기까지지만 아직 찾을것이 많은 것 같다.