1차원 무게중심 좌표

앞에서도 설명했지만 더 자세한 공식을 다뤄보겠음

두 점 A, B가 있고, 이는 같은 한 1차원 선분 위에 있음

그리고 이 선분 위에 점 P가 존재함

이 때, 점 P는 점 A, B에 가중치를 고려한 합과 같음

$P = \alpha A + \beta B$

만약 $P = 3, A = 1, B = 5$라면 $1\alpha + 5\beta = 3$이 됨

$\alpha = 4, \beta = \frac{1}{5}$일때 해답이 될 수 있음 또 $\alpha = 1, \beta = \frac{2}{5}$일때도 해답이 될 수 있음

하지만 여기서 문제가 있음

$\alpha$와 $\beta$가 여러 값이 될 수 있으면 이후 계산에 오차가 생김

이거를 해결하기위해 사용하는 핵심 개념이

$0 <= \alpha <= 1$, $0 <= \beta <= 1$, $\alpha + \beta = 1$

임

$\alpha$와 $\beta$를 정규화를 해서 1이라는 총합으로 제한을 두어 어느 상황에서든 값을 통일시키는거임

앞서 살펴본

$P = \alpha A + \beta B$

를 이용해보자

$P = \alpha A + \beta B$ $\alpha + \beta = 1$ $\beta = 1 - \alpha$

$\alpha = 0$ => $P = B$ $\alpha = 0.5$ => $P = 0.5A + 0.5B$ $\alpha = 1$ => $P = A$

이렇게 선형보간이 됨

그럼 이$\alpha$와 $\beta$를 어떻게 구하지?

$\alpha, \beta$ 전개

먼저 $\alpha$를 살펴보자

$\alpha = \frac{B - P}{B - A}$

$P = \alpha A + (1-\alpha)B$ $P = \alpha A + B - \alpha B$ $P - B = \alpha A - \alpha B$ $P - B = -\alpha(-A + B)$ $-\alpha = \frac{P - B}{-A + B}$ $\alpha = \frac{B - P}{B - A}$

혹은 $\alpha = \frac{(B - P) \cdot (-1)}{(B - A) \cdot (-1)} = \frac{P - B}{A - B}$

$\alpha = \frac{B - P}{B - A}$

$\beta = \frac{P - A}{B - A}$

$P = (\frac{B - P}{B - A}) \cdot A + \beta B$ $\beta B = P - (\frac{B - P}{B - A}) \cdot A$ $\beta B = P \cdot (\frac{B - A}{B - A}) - (\frac{B - P}{B - A}) \cdot A$ $\beta B = \frac{P \cdot(B-A) - A \cdot (B - P)}{B - A}$ $\beta B = \frac{PB - PA - AB + AP}{B - A}$ $\beta B = \frac{B(P - A) - PA + AP}{B - A}$ $\beta B = \frac{B(P - A)}{B - A}$ $\beta = \frac{P - A}{B - A}$

$\beta = \frac{P - A}{B - A}$

코드

void line(int ax, int ay, int bx, int by, TGAImage &framebuffer, TGAColor color)
{
    for (int x = ax; x <= bx; x++)
    {
        float alpha = (bx - x) / static_cast<float>(bx - ax);
        int y = alpha * ay + (1 - alpha) * by; //barycentric again
        framebuffer.set(x, y, color);
    }
}

이렇게 쉽게 증가하는 직선을 그릴 수 있음

line(72, 13, 127, 127, framebuffer, white);

2차원 무게중심 좌표

1차원은 점 2개였지?

2차원은 점 3개임

즉 점 A, B, C에 대해 무게중심좌표를 구하는거임 그 외엔 모든게 같음

$P = \alpha A + \beta B + \gamma C$ $\alpha + \beta + \gamma = 1$

임

이건 점 2개를 이용할때처럼 $\alpha , 1 - \alpha$이런식으로 접근하기엔 변수가 많음

그래서 2가지 방법을 사용해볼 수 있음

행렬 이용(비추천)

행렬 변환

행렬 이용하는 거임

연립일차 방정식은 지립일차 방정식은 계수, 미지수, 상수 부로 나눠서 행렬로 표현할 수 있음

먼저 아래 식은 x좌표와 y좌표가 합쳐져 있음

$P = \alpha A + \beta B + \gamma C$ $\alpha + \beta + \gamma = 1$

따라서 행렬로 표현하기 위해선 미지수부를 위해 x, y로 나눠야 함

$\left{ \begin{array}{ll} \alpha A_x + \beta B_x + \gamma C_x &= P_x\ \alpha A_y + \beta B_y + \gamma C_y &= P_y\ \alpha + \beta + \gamma &= 1 \end{array}\right.$

이렇게 나타낼 수 있음

이걸 행렬로 표현해보자

$\begin{pmatrix} A_x & B_x & C_x\ A_y & B_y & C_y\ 1 & 1 & 1 \end{pmatrix} \begin{pmatrix}\alpha \ \beta \ \gamma\end{pmatrix} =\begin{pmatrix}P_x \ P_y \ 1\end{pmatrix}$

가 됨

수반 행렬과 역행렬

우리한테 필요한건 $\begin{pmatrix}\alpha \ \beta \ \gamma\end{pmatrix}$ 임 좌변에 $\begin{pmatrix}\alpha \ \beta \ \gamma\end{pmatrix}$만 남기고 우변으로 이항정리 해보자

역행렬을 곱하면 됨

$\begin{pmatrix} A_x & B_x & C_x\ A_y & B_y & C_y\ 1 & 1 & 1 \end{pmatrix} \begin{pmatrix}\alpha \ \beta \ \gamma\end{pmatrix} =\begin{pmatrix}P_x \ P_y \ 1\end{pmatrix}$

$\begin{pmatrix}\alpha \ \beta \ \gamma\end{pmatrix} = \begin{pmatrix} A_x & B_x & C_x\ A_y & B_y & C_y\ 1 & 1 & 1 \end{pmatrix}^{-1}\begin{pmatrix}P_x \ P_y \ 1\end{pmatrix}$

역행렬을 수반행렬로

수반행렬과 역행렬의 관계 : $A^{-1} = \frac{1}{detA} adjA$

$\begin{pmatrix}\alpha \ \beta \ \gamma\end{pmatrix} = \frac{adj\begin{pmatrix} A_x & B_x & C_x\ A_y & B_y & C_y\ 1 & 1 & 1 \end{pmatrix}\begin{pmatrix}P_x \ P_y \ 1\end{pmatrix}}{\begin{vmatrix} A_x & B_x & C_x \ A_y & B_y & C_y \ 1&1&1 \end{vmatrix}}$

이걸 전개하면 됨

소행렬, 소행렬식, 행렬식 계산, 여인수 전개, 수반행렬

선형대수에서 배우는건데 혹시 모르는 사람 있을까봐 설명함

$A = \begin{pmatrix} 1&2&3\ 4&5&6\ 7&8&9 \end{pmatrix}$ 라는 행렬이 있다고 하자

행렬은 기본적으로 행과 열의 조합으로 나타낼 수 있음

이를 $A_{ij}$와 같은 식으로 표현함

소행렬

$A_{22}$의 소행렬

$A_{22} = \begin{pmatrix} \textcolor{blue}{1}&\textcolor{red}{2}&\textcolor{blue}{3}\ \textcolor{red}{4}&\textcolor{red}{5}&\textcolor{red}{6}\ \textcolor{blue}{7}&\textcolor{red}{8}&\textcolor{blue}{9} \end{pmatrix}$

여기서 빨간색 글자를 제외한 파란색 글자인 부분만 사용하는게 $A_{22}$에 대한 소행렬임

소행렬식

$A_{22}$의 소행렬식

$A_{22} = \begin{vmatrix} 1&3\ 7&9 \end{vmatrix}$

이렇게 행렬식 기호를 이용해 소행렬을 표현하면 그게 행렬식임

행렬식 계산

$A_{22}$ 행렬식 계산

이런 형태로 계산하면됨

$1 * 9 - 3 * 7 = -12$가 $A_{22}$의 행렬식 결과임

이때 중요한게 부호임

여인수 전개

여인수 전개

여인수 전개할때, 필요한건 부호임 $A_{ij}$의 소행렬식의 계산결과를 구하기위해선 $(-1)^{i+j}$의 부호를 붙여 계산해야함

예를들어 ${11}$이면, $(-1)^2$이 되어, $(1,1)$위치의 수반행렬에 $* 1$을 해야함 예를들어 ${34}$이면, $(-1)^7$이 되어, $(4,3)$위치의 수반행렬에 $* -1$을 해야함

즉, 이런 패턴을 가짐

수반행렬

이렇게 모든 행렬의 소행렬에 행렬식 계산시에 필요한 부호를 계산하여 사용하여 모든 행렬식을 계산한것이 수반행렬임

이때 중요한건 행과 열이 바뀐다는거임

수반행렬

$A_{23}$의 소행렬을 계산했다면 이 계산은 수반행렬의 $adjA_{32}$에 저장됨

$A = \begin{pmatrix} 1&2&3\ 4&5&6\ 7&8&9 \end{pmatrix}$ 이걸 위 모든과정을 거쳐 수반행렬 $adjA$로 만들어보자

모든걸 다 할수없으니, 2행에 대해서만 소행렬, 전개, 수반행렬로 만드는 과정을 보여줌

$C_{21} = -\begin{vmatrix} 2 & 3 \ 8 & 9 \end{vmatrix} = -((2 \times 9) - (3 \times 8)) = -(18 - 24) = 6$ $C_{22} = +\begin{vmatrix} 1 & 3 \ 7 & 9 \end{vmatrix} = (1 \times 9) - (3 \times 7) = 9 - 21 = -12$ $C_{23} = -\begin{vmatrix} 1 & 2 \ 7 & 8 \end{vmatrix} = -((1 \times 8) - (2 \times 7)) = -(8 - 14) = 6$

$\text{adj}(A) = \begin{pmatrix} C_{11} & \mathbf{C_{21}}(6) & C_{31} \ C_{12} & \mathbf{C_{22}}(-12) & C_{32} \ C_{13} & \mathbf{C_{23}}(6) & C_{33} \end{pmatrix}$

이 됨

전체를 전부 이런식으로 수반행렬로 만들면

$\text{adj}(A) = \begin{pmatrix} -3 & {6} & -3 \ 6 & {-12} & 6 \ -3 & {6} & -3 \end{pmatrix}$

이렇게 됨

다시 돌아와서

$\begin{pmatrix}\alpha \ \beta \ \gamma\end{pmatrix} = \frac{adj\begin{pmatrix} A_x & B_x & C_x\ A_y & B_y & C_y\ 1 & 1 & 1 \end{pmatrix}\begin{pmatrix}P_x \ P_y \ 1\end{pmatrix}}{\begin{vmatrix} A_x & B_x & C_x \ A_y & B_y & C_y \ 1&1&1 \end{vmatrix}}$

이 식의 수반행렬을 전개해보자

마지막 행이 1행이라 아주 좋음

$$ \begin{aligned} \begin{pmatrix}\alpha \ \beta \ \gamma \end{pmatrix} &= \begin{pmatrix} A_x & B_x & C_x\ A_y & B_y & C_y\ 1 & 1 & 1 \end{pmatrix}^{-1} \begin{pmatrix}P_x \ P_y \ 1\end{pmatrix} \ &= \frac{ \mathrm{adj} \begin{pmatrix} A_x & B_x & C_x\ A_y & B_y & C_y\ 1 & 1 & 1 \end{pmatrix} \begin{pmatrix} P_x \ P_y \ 1 \end{pmatrix} }{ \begin{vmatrix} A_x & B_x & C_x\ A_y & B_y & C_y\ 1 & 1 & 1 \end{vmatrix} } \ &= \frac{ \begin{pmatrix} B_y - C_y & - (B_x - C_x) & B_x C_y - B_y C_x\ -(A_y -C_y) & A_x - C_x & - (A_x C_y - A_y C_x) \ A_y - B_y & - (A_x - B_x) & A_x B_y - A_y B_x \end{pmatrix} \begin{pmatrix}P_x \ P_y \ 1\end{pmatrix} }{ \begin{vmatrix} A_x & B_x & C_x\ A_y & B_y & C_y\ 1 & 1 & 1 \end{vmatrix} } \end{aligned}$$

행렬 곱

행렬곱은 어떻게 계산하지?

두 행렬 $A, B$가 있을 때, $A$의 $i$번째 행과 $B$의 $j$번째 열의 원소들을 차례대로 곱한 뒤 모두 더하면 결과 행렬의 $(i, j)$번째 성분이 됨.

예를들어 $A = \begin{pmatrix} 1&2\ 3&4 \end{pmatrix}$, $B = \begin{pmatrix} 4&5\ 6&7\ \end{pmatrix}$

이 있으면

$A \times B = \begin{pmatrix} 1 * 4 + 2 * 6 & 1 * 5 + 2 * 7\ 3 * 4 + 4 * 6 & 3 * 5 + 4 * 7 \end{pmatrix} = \begin{pmatrix} 16 & 19\ 36 & 43 \end{pmatrix}$

가 되는거임

그럼 다시 돌아와서

$$\frac{\small \begin{pmatrix} B_y - C_y & - (B_x - C_x) & B_x C_y - B_y C_x\ -(A_y -C_y) & A_x - C_x & - (A_x C_y - A_y C_x) \ A_y - B_y & - (A_x - B_x) & A_x B_y - A_y B_x \end{pmatrix} \begin{pmatrix}P_x \ P_y \ 1\end{pmatrix} }{\small \begin{vmatrix} A_x & B_x & C_x\ A_y & B_y & C_y\ 1 & 1 & 1 \end{vmatrix} }$$

을 살펴보면

분모의 행렬에 곱셈을 할 수 있음

분모부분만 살펴보자

$\begin{pmatrix} B_y - C_y & - (B_x - C_x) & B_x C_y - B_y C_x\ -(A_y -C_y) & A_x - C_x & - (A_x C_y - A_y C_x) \ A_y - B_y & - (A_x - B_x) & A_x B_y - A_y B_x \end{pmatrix} \begin{pmatrix}P_x \ P_y \ 1\end{pmatrix}$ 임

그럼 곱을 진행해볼까나...

$\begin{pmatrix} P_x (B_y - C_y) + P_y(C_x - B_x) + 1(B_x C_y - B_y C_x) & P_x(C_y - A_y) + P_y(A_x - C_x) + 1(-(A_x C_y - A_y C_x)) & P_x(A_y - B_y) + P_y(B_x - A_x) + 1(A_x B_y - A_y B_x) \end{pmatrix}$ 가 됨

그걸 행렬식으로 표현하면

$$ \frac{\small \begin{pmatrix} \begin{vmatrix} P_x & B_x & C_x\ P_y & B_y & C_y\ 1 & 1 & 1 \end{vmatrix} & \begin{vmatrix} P_x & C_x & A_x\ P_y & C_y & A_y\ 1 & 1 & 1 \end{vmatrix} & \begin{vmatrix} P_x & A_x & B_x\ P_y & A_y & B_y\ 1 & 1 & 1 \end{vmatrix} \end{pmatrix}^\top }{\small \begin{vmatrix} A_x & B_x & C_x\ A_y & B_y & C_y\ 1 & 1 & 1 \end{vmatrix} }$$

처럼 마무리 되는거지

근데 복잡하지? 저렇게 만들고, 계산하려고 해도 행렬식이 4개라 4개를 다 계산해야함

이거 안씀

실제로는 비율을 더 자주 이용함

비율 & 신발끈 공식 (더 나은 선택)

1차원에서의 무게중심 좌표 구하는 것과 비슷한 맥락임

이런 삼각형이 있다고 가정해보자

점 A를 기준으로 $\overline{BC}$가 밑변이고 높이가 $h_A$일때, $\triangle ABC = \frac {1}{2} (\overline{BC} * h_A)$가 됨

이때, 점 P를 기준으로 $\overline{BC}$가 밑변이고 높이가 $h_P$일때, $\triangle PBC = \frac {1}{2} (\overline{BC} * h_P)$가 됨

즉 $\frac{area(PBC)}{area(ABC)} = \frac{\frac {1}{2} (\overline{BC} * h_P)}{\frac {1}{2} (\overline{BC} * h_A)} = \frac{h_P}{h_A}$임

$P = \alpha A + \beta B + \gamma C$임

위에서 $\overline{BC}$가 밑변일때 $\frac{area(ABC)}{area(PBC) }=\frac{h_A}{h_P}$이므로, $h_P = \alpha h_A + \beta h_B + \gamma h_C$가 성립됨

이때,$\overline{BC}$는 밑변이므로 높이가 존재하지 않음 $h_B = 0, h_C = 0$임 $h_P = \alpha h_A$, $\alpha = \frac{h_p}{h_A}$가 됨

즉, $\alpha$는 $\triangle PBC$가 $\triangle ABC$에 차지하는 비율에 의해 결정됨

$\alpha = \frac{area(PBC)}{area(ABC)}$ $\beta = \frac{area(PCA)}{area(ABC)}$ $\gamma = \frac{area(PAB)}{area(ABC)}$

로 결정되는거임

신발끈 공식

평면위에 다각형의 각 꼭지점 좌표가 있을때,

빨간선으로 이어진 부분을 곱하고 그 결과들을 더한것에서 파란선으로 이어진 부분을 곱하고 그 결과들을 더한것을 빼고 1/2를 곱하면 그게 다각형의 넓이임

이때 중요한건, 꼭짓점의 좌표가 한방향으로 흘러가야한다는거임

$\triangle ABC \ = \frac{1}{2} * |((A_x * B_y) + (B_x * C_y) + (C_x * A_y) - ((B_x * A_y) + (C_x * B_y) + (A_x * C_y)))| \ = \frac{1}{2} * |(A_x B_y + B_x C_y + C_xA_y - B_xA_y - C_xB_y - A_xC_y)| \ = \frac{1}{2} * |(B_y(A_x - C_x) + C_y(B_x - A_x) + A_y(C_x - B_x))|$

이 됨

예시로 $A = (16, 0), B = (0, 12), C = (0,0), P = (4,3)$ 이라고 했을때 위의 공식을 적용해서 $\triangle ABC, \triangle PBC, \triangle PCA, \triangle PAB$를 구하면 $\triangle ABC = 96, \triangle PBC = 24, \triangle PCA = 24, \triangle PAB = 48$이 나옴

$\alpha, \beta, \gamma$는 각각 순서대로 $\triangle PBC, \triangle PCA, \triangle PAB$ 의 전체 삼각형 너비에 대한 비율임

코드

double get_triangle_area(Triangle t) 
{
    return 0.5 * (
        (t.b.y-t.a.y)*(t.b.x+t.a.x) + 
        (t.c.y-t.b.y)*(t.c.x+t.b.x) + 
        (t.a.y-t.c.y)*(t.a.x+t.c.x)
    );
}

먼저 삼각형 너비 구하는 공식임

이거 저번 포스트에서 설명했음

나만의 tiny renderer 만들기 (2) - 삼각형 그리기 - 코드 수정 참고!

우리가 위에서 살펴본 식으로 살펴보면

double get_triangle_area_v2(Triangle t)
{
    return 0.5 * (
        (t.b.y * (t.a.x - t.c.x)) + 
        (t.c.y * (t.b.x - t.a.x)) + 
        (t.a.y * (t.c.x - t.b.x))
    );
}

인거임

삼각형 내부 원하는 색으로 칠하기

void triangle(Triangle t, TGAImage &framebuffer, TGAColor color) 
{
    int minX = std::min(std::min(t.a.x, t.b.x), t.c.x); 
    int minY = std::min(std::min(t.a.y, t.b.y), t.c.y); 
    int maxX = std::max(std::max(t.a.x, t.b.x), t.c.x);
    int maxY = std::max(std::max(t.a.y, t.b.y), t.c.y);

    double total_area = get_triangle_area(t);

    if (total_area < 0) return;

#pragma omp parallel for
    for (int x=minX; x<=maxX; x++) 
    {
        for (int y=minY; y<=maxY; y++) 
        {
            double alpha = get_triangle_area(Triangle(Vec3(x,y,0), Vec3(t.b.x, t.b.y, 0), Vec3(t.c.x, t.c.y, 0))) / total_area;
            double beta  = get_triangle_area(Triangle(Vec3(x,y,0), Vec3(t.c.x, t.c.y, 0), Vec3(t.a.x, t.a.y, 0))) / total_area;
            double gamma =get_triangle_area(Triangle(Vec3(x,y,0), Vec3(t.a.x, t.a.y, 0), Vec3(t.b.x, t.b.y, 0))) / total_area;
            if (alpha<0 || beta<0 || gamma<0) continue;


            framebuffer.set(x, y, color);
        }
    }
}

지금 삼각형을 칠하는 코드는 이런 형태임 alpha, beta, gamma가 위에서 말한 무게중심좌표에 해당함

각 좌표에 대해 먼저 z축을 설정하고 이걸 이용해서 각 z축을 계산한다음, 이걸 색상으로 이용해볼거임

먼저 main.cpp에 다음과 같은 삼각형 코드를 넣음

int main(int argc, char** argv)
{

    Model model(argv[1]);
    TGAImage framebuffer(width, height, TGAImage::RGB);


    triangle(Triangle(Vec3(7, 45, 255), Vec3(35, 100, 255), Vec3(45,  60, 255)), framebuffer);

    framebuffer.write_tga_file("framebuffer.tga");
    return 0;
}

그리고 triangle을 아래처럼 바꿈

void triangle(Triangle t, TGAImage &framebuffer) 
{
    int minX = std::min(std::min(t.a.x, t.b.x), t.c.x); 
    int minY = std::min(std::min(t.a.y, t.b.y), t.c.y); 
    int maxX = std::max(std::max(t.a.x, t.b.x), t.c.x);
    int maxY = std::max(std::max(t.a.y, t.b.y), t.c.y);

    double total_area = get_triangle_area(t);

    if (std::abs(total_area) < 1e-5) return; //backface culling

#pragma omp parallel for
    for (int x = minX; x <= maxX; x++) 
    {
        for (int y = minY; y <= maxY; y++) 
        {
            Vec3 p(x, y, 0);

            double area_a = get_triangle_area(Triangle(p, t.b, t.c)); //PBC
            double area_b = get_triangle_area(Triangle(p, t.c, t.a)); //PCA
            double area_c = get_triangle_area(Triangle(p, t.a, t.b)); //PAB

            double alpha = area_a / total_area;
            double beta  = area_b / total_area;
            double gamma = area_c / total_area;

            if (alpha < -1e-5 || beta < -1e-5 || gamma < -1e-5) continue;

            framebuffer.set(x, y, {
                static_cast<uint8_t>(alpha * t.a.z), 
                static_cast<uint8_t>(beta * t.b.z), 
                static_cast<uint8_t>(gamma * t.c.z), 
                255
            });
        }
    }
}

굳~

#ifndef VEC3_H
#define VEC3_H
#include <cmath>

class Vec3
{
public:
    float x, y, z;

    Vec3(float x_ = 0.0f, float y_ = 0.0f, float z_ = 0.0f)
        : x(x_), y(y_), z(z_) {}

    Vec3 operator-(const Vec3 &v) const
    {
        return Vec3(this->x - v.x, this->y - v.y, this->z - v.z);
    }

    Vec3 operator+(const Vec3 &v) const
    {
        return Vec3(this->x + v.x, this->y + v.y, this->z + v.z);
    }

    float length_squared() const 
    {
        return this->x * this->x + this->y * this->y + this->z * this->z;
    }

    float length() const 
    {
        return std::sqrt(length_squared());
    }
};

inline float dot(Vec3 v1, Vec3 v2)
{
    return v1.x * v2.x + v1.y * v2.y + v1.z * v2.z;
}

inline Vec3 cross(Vec3 v1, Vec3 v2)
{
    return Vec3(
        v1.y * v2.z - v1.z * v2.y,
        v1.z * v2.x - v1.x * v2.z,
        v1.x * v2.y - v1.y * v2.x);   
}

class Triangle
{
public:
    Vec3 a;
    Vec3 b;
    Vec3 c;
    Triangle(Vec3 v1, Vec3 v2, Vec3 v3) : a(v1), b(v2), c(v3) {}

};

#endif // VEC3_H

일단 벡터 클래스와, 벡터 3개를 이용한 Triangle클래스를 만들어줌 ㅇㅇ

벡터클래스에는 연산자 오버로딩, dot, cross 연산을 정의해놓음ㅇㅇ

벡터 외적 특성 이용하기

일단 2차원에서 진행된다는 점을 잊지 말 것!

Triangle t1(Vec3(7,45,0), Vec3(35,100,0), Vec3(45,60,0));
Triangle t2(Vec3(120,35,0), Vec3(90,5,0), Vec3(45,110,0));
Triangle t3(Vec3(115,83,0), Vec3(80,90,0), Vec3(85,120,0));

draw_triangle(t1.a.x, t1.a.y, t1.b.x, t1.b.y, t1.c.x, t1.c.y, framebuffer, red);
draw_triangle(t2.a.x, t2.a.y, t2.b.x, t2.b.y, t2.c.x, t2.c.y, framebuffer, white);
draw_triangle(t3.a.x, t3.a.y, t3.b.x, t3.b.y, t3.c.x, t3.c.y, framebuffer, green);

이렇게 3개의 triangle을 그리도록 했음

draw_triangle은

void line(int ax, int ay, int bx, int by, TGAImage &framebuffer, TGAColor color) 
{
    bool is_x_smaller = (std::abs(ax - bx) < std::abs(ay - by));

    if (is_x_smaller) { std::swap(ax, ay); std::swap(bx, by); }
    if (ax > bx)      { std::swap(ax, bx); std::swap(ay, by); }

    int dx   = bx - ax;
    int dy   = std::abs(by - ay);
    int idiff = 0;
    int y    = ay;
    int ystep = (by > ay) ? 1 : -1;

    for (int x = ax; x <= bx; x++) 
    {
        if (is_x_smaller) framebuffer.set(y, x, color);
        else               framebuffer.set(x, y, color);

        idiff += 2 * dy;
        if (idiff > dx) 
        {
            y     += ystep;
            idiff -= 2 * dx;
        }
    }
}

void draw_triangle(int ax, int ay, int bx, int by, int cx, int cy, TGAImage &framebuffer, TGAColor color) 
{
    line(ax, ay, bx, by, framebuffer, color);
    line(bx, by, cx, cy, framebuffer, color);
    line(cx, cy, ax, ay, framebuffer, color);
}

이렇게 작동함

왜 저런 코드가 나왓는지 궁금하면 나만의 tiny renderer 만들기 (1) - Bresenham Algorithm 참고!

이런 삼각형 3개가 만들어지지

여기에 이제 특정 픽셀이 삼각형 내부인지를 판별해야함 이걸 쉽게 구할 수 있는 방식이 있음

그게 바로 외적 공식의 기하학적 특성을 이용한거임

두 벡터의 외적된 벡터의 절대값(길이)는 두 벡터가 이루는 평행사변형의 크기와 같음

$\frac{1}{2} * 외적 = 삼각형 크기$ 가 되는거임

또, 이렇게
`점 p에서 삼각형 각 꼭짓점까지 만들 수 있는
새로운 삼각형 3개의 넓이의 합 == 기존 삼각형의 넓이`
= 세 삼각형 넓이의 합 - 기존 삼각형 넓이 == 0
라면, 점 p는 삼각형 내부에 있는거임

여기서 외적의 성질을 이용하면 삼각형 넓이가 아닌 두 벡터의 외적 길이인 평행사변형의 크기를 이용해도 문제가 없음

코드

따라서 먼저 다음과 같은 넓이 구하는 코드 + 점 p의 위치가 삼각형 내부에 있는지 판별하는 메서드를 만들어줌

float get_triangle_area(const Triangle &t)
{
    auto ba = t.b - t.a;
    auto ca = t.c - t.a;

    auto cr = cross(ba, ca);

    return cr.length();
}

bool is_inside_triangle(const float area, const Vec3 &p, const Triangle &t)
{
    Triangle pt1(Vec3(p), Vec3(t.a), Vec3(t.b));
    Triangle pt2(Vec3(p), Vec3(t.b), Vec3(t.c));
    Triangle pt3(Vec3(p), Vec3(t.c), Vec3(t.a));

    auto pt1_area = get_triangle_area(pt1);
    auto pt2_area = get_triangle_area(pt2);
    auto pt3_area = get_triangle_area(pt3);

    float diff = area - (pt1_area + pt2_area + pt3_area);

    if (0 <= diff && diff < 1e-4) return true;
    return false;
}

점 p를 이용해 만들 수 있는 삼각형을 만들고, 해당 삼각형의 외적과 외적의 길이를 구하여 평행사변형의 넓이를 구함

왜 std::abs와 같은 절대값 처리가 없음?

쉬움 오른손 좌표계냐 왼손 좌표계냐에 따라 외적의 방향이 달라지지? 두 벡터가 오른손 좌표계에서 외적이 특정 방향(d)이었다면 해당 두 벡터는 왼손 좌표계에서 외적은 -d 가 됨

근데, 벡터의 길이를 구하는 로직은 자기 자신의 모든 좌표를 제곱하는 것과 같음

float length_squared() const 
{
    return this->x * this->x + this->y * this->y + this->z * this->z;
}

그러니까 외적의 특정 축이 음수였다고 하더라도, 길이를 구할때는 무조건 양수가 나오게 되는거임

이제 전체 main.cpp를 봐보자

int main(int argc, char** argv)
{
    TGAImage framebuffer(width, height, TGAImage::RGB);

    Triangle t1(Vec3(7,45,0), Vec3(35,100,0), Vec3(45,60,0));
    Triangle t2(Vec3(120,35,0), Vec3(90,5,0), Vec3(45,110,0));
    Triangle t3(Vec3(115,83,0), Vec3(80,90,0), Vec3(85,120,0));

    draw_triangle(t1.a.x, t1.a.y, t1.b.x, t1.b.y, t1.c.x, t1.c.y, framebuffer, red);
    draw_triangle(t2.a.x, t2.a.y, t2.b.x, t2.b.y, t2.c.x, t2.c.y, framebuffer, white);
    draw_triangle(t3.a.x, t3.a.y, t3.b.x, t3.b.y, t3.c.x, t3.c.y, framebuffer, green);

    float t1_area = get_triangle_area(t1);
    float t2_area = get_triangle_area(t2);
    float t3_area = get_triangle_area(t3);

    for (int i = 0; i < height; i++)
    {
        for (int j = 0; j < width; j++)
        {
            Vec3 p(j, i, 0);

            if (is_inside_triangle(t1_area, p, t1))
            {
                framebuffer.set(j, i, red);
            }

            if (is_inside_triangle(t2_area, p, t2))
            {
                framebuffer.set(j, i, white);
            }

            if (is_inside_triangle(t3_area, p, t3))
            {
                framebuffer.set(j, i, green);
            }
        }
    }

    framebuffer.write_tga_file("framebuffer.tga");
    return 0;
}

height와 width를 전부 돌면서 삼각형 t1,t2,t3와 점 p가 어떤 관계인지를 파악하고 그걸 framebuffer에 넣어 출력하는거임

그럼 이렇게 내부가 칠해진 삼각형이 나오게 됨~~ㄷㄷㄷㄷ

바운딩 박스 최적화

지금 코드는 모든 width와 height의 픽셀에 대하여 해당 픽셀이 삼각형 내부인지 아닌지를 판별함

근데, 사진에서 잘 보면 삼각형 어디에도 절대 포함될 수 없는 픽셀들이 존재함

빨간 삼각형을 기준으로 봐보자

이렇게 빗금칠 된 공간은 절대로 삼각형 내부에 들어갈 수 없음

그래서 저부분을 빼고 계산을 해준다는 개념이 바운딩 박스임

먼저 모든 삼각형을 하나의 객체처럼 관리하기 위해 배열에 넣어줌

std::vector<std::pair<Triangle, TGAColor>> triangles; //add

int main(int argc, char** argv)
{
    TGAImage framebuffer(width, height, TGAImage::RGB);

    Triangle t1(Vec3(7,45,0), Vec3(35,100,0), Vec3(45,60,0));
    Triangle t2(Vec3(120,35,0), Vec3(90,5,0), Vec3(45,110,0));
    Triangle t3(Vec3(115,83,0), Vec3(80,90,0), Vec3(85,120,0));

    triangles.push_back(std::make_pair(t1, red));
    triangles.push_back(std::make_pair(t2, white));
    triangles.push_back(std::make_pair(t3, green));

    //...
}

그리고 특정 점 p가 삼각형 내부인지 판별하기전에 해당 삼각형의 min, max x-y의 범위에서 loop를 돌도록 하면 됨

따라서 전체 main은 다음처럼 바뀜

std::vector<std::pair<Triangle, TGAColor>> triangles;

int main(int argc, char** argv)
{
    TGAImage framebuffer(width, height, TGAImage::RGB);

    Triangle t1(Vec3(7,45,0), Vec3(35,100,0), Vec3(45,60,0));
    Triangle t2(Vec3(120,35,0), Vec3(90,5,0), Vec3(45,110,0));
    Triangle t3(Vec3(115,83,0), Vec3(80,90,0), Vec3(85,120,0));

    triangles.push_back(std::make_pair(t1, red));
    triangles.push_back(std::make_pair(t2, white));
    triangles.push_back(std::make_pair(t3, green));

    draw_triangle(t1.a.x, t1.a.y, t1.b.x, t1.b.y, t1.c.x, t1.c.y, framebuffer, red);
    draw_triangle(t2.a.x, t2.a.y, t2.b.x, t2.b.y, t2.c.x, t2.c.y, framebuffer, white);
    draw_triangle(t3.a.x, t3.a.y, t3.b.x, t3.b.y, t3.c.x, t3.c.y, framebuffer, green);

    for (int ti = 0; ti < triangles.size(); ++ti)
    {
        auto p = triangles[ti];
        Triangle t = p.first;
        TGAColor color = p.second;

         //box bounding
        int minX = std::min(std::min(t.a.x, t.b.x), t.c.x);
        int minY = std::min(std::min(t.a.y, t.b.y), t.c.y);
        int maxX = std::max(std::max(t.a.x, t.b.x), t.c.x);
        int maxY = std::max(std::max(t.a.y, t.b.y), t.c.y);

        float area = get_triangle_area(t);

        for (int j = minY; j <= maxY; ++j)
        {
            for (int i = minX; i <= maxX; ++i)
            {
                Vec3 point(i, j, 0);

                if (is_inside_triangle(area, point, t))
                {
                    framebuffer.set(i, j, color);
                }
            }
        }
    }

    framebuffer.write_tga_file("framebuffer.tga");
    return 0;
}

잘 출력댐

박스 바운딩 전/후 속도차이

박스 바운딩 전	박스 바운딩 후

3개의 삼각형을 그리는데도 차이가 심함!

그러니까 바운딩 박스 최적화를 잘 사용해보자

백페이스 컬링

지금 삼각형 내부를 판별하는 코드는 문제가 있음

대충 어떤 모델을 렌더링한 결과임

잘 보면 이상한 부분이 많음

이게 이렇게 렌더링되는 이유는

• 삼각형의 앞,뒷면을 가리지 않고 모두 렌더링 하기 때문임

코드 수정

먼저 공부중인 코스에 맞춰 코드를 수정함

float get_triangle_area(Triangle t) 
{
    return 0.5 * (
        (t.b.y-t.a.y)*(t.b.x+t.a.x) + 
        (t.c.y-t.b.y)*(t.c.x+t.b.x) + 
        (t.a.y-t.c.y)*(t.a.x+t.c.x)
    );
}

void triangle(Triangle t, TGAImage &framebuffer, TGAColor color) 
{
    int bbminx = std::min(std::min(t.a.x, t.b.x), t.c.x); 
    int bbminy = std::min(std::min(t.a.y, t.b.y), t.c.y); 
    int bbmaxx = std::max(std::max(t.a.x, t.b.x), t.c.x);
    int bbmaxy = std::max(std::max(t.a.y, t.b.y), t.c.y);

    double total_area = get_triangle_area(t);

#pragma omp parallel for
    for (int x=bbminx; x<=bbmaxx; x++) 
    {
        for (int y=bbminy; y<=bbmaxy; y++) 
        {
            double alpha = get_triangle_area(Triangle(Vec3(x,y,0), Vec3(t.b.x, t.b.y, 0), Vec3(t.c.x, t.c.y, 0))) / total_area;
            double beta  = get_triangle_area(Triangle(Vec3(x,y,0), Vec3(t.c.x, t.c.y, 0), Vec3(t.a.x, t.a.y, 0))) / total_area;
            double gamma =get_triangle_area(Triangle(Vec3(x,y,0), Vec3(t.a.x, t.a.y, 0), Vec3(t.b.x, t.b.y, 0))) / total_area;
            if (alpha<0 || beta<0 || gamma<0) continue;
            framebuffer.set(x, y, color);
        }
    }
}

이렇게 코드를 바꿈

is_inside_triangle는 삭제하고 위처럼 코드를 수정함

중요한건

return 0.5 * (
        (t.b.y-t.a.y)*(t.b.x+t.a.x) + 
        (t.c.y-t.b.y)*(t.c.x+t.b.x) + 
        (t.a.y-t.c.y)*(t.a.x+t.c.x)
    );

이부분임

전개

지금은 2차원 평면이므로, 모든 좌표의 z좌표가 0임

두 3차원 벡터의 외적공식은 다음과 같음

$\vec{a} \times \vec{b} = (a_y b_z - a_z b_y, a_z b_x - a_x b_z, a_x b_y - a_y b_x)$

이때 벡터는 각각

$\vec{b-a}, \vec{c-a}$

그리고 z축과 관련된 벡터의 요소는 0임

따라서 $\vec{b-a}, \vec{c-a}$의 외적은 다음과 같음(z축과 관련된 항 모두 제거)

$\vec{b-a} \times \vec{c-a} = {(b_x - a_x)} \cdot {(c_y - a_y)} - {(b_y - a_y)} \cdot {(c_x - a_x)}$

이걸 분배법칙을 이용해 전개해보면 다음과 같음

$= b_xc_y - b_xa_y - a_xc_y + a_xa_y - (b_yc_x - b_ya_x - a_yc_x + a_ya_x)$ $= b_xc_y - b_xa_y - a_xc_y + a_xa_y - b_yc_x + b_ya_x + a_yc_x - a_ya_x$

이때 두 스칼라의 곱셈법칙은 교환법칙이 성립함

$= b_xc_y - b_xa_y - a_xc_y + a_xa_y - b_yc_x + b_ya_x + a_yc_x - .a_xa_y$ $= b_xc_y - b_xa_y - a_xc_y - b_yc_x + b_ya_x + a_yc_x$

좀 어지러우니 식을 정리해보자

$= a_xb_y - a_yb_x + b_xc_y - b_yc_x - a_xc_y + a_yc_x$

여기서 트릭 하나 발동

$0 = b_xb_y - a_xa_y + c_xc_y - b_xb_y + a_xa_y - c_xc_y$

라는 식 한개를 정의해보자 이항정리를 하면 0이 되는걸 알수있음

그럼 이 식은 합이 0이니, 위의 식에 넣어도 0이니, 값에 변화가 없음을 알 수 있음

$= a_xb_y - a_yb_x + b_xc_y - b_yc_x - a_xc_y + a_yc_x \ + b_xb_y - a_xa_y + c_xc_y - b_xb_y + a_xa_y - c_xc_y$

와 같이 두개를 더한거나 아닌거나 기존의 외적과 같은 값이라는거임

그럼 이제 분배법칙을 이용하기 위해 식을 조금 정리해보자

$= b_xb_y + a_xb_y - a_yb_x - a_ya_x \+ c_xc_y + b_xc_y - b_yc_x - b_yb_x \+ a_yc_x + a_ya_x - a_xc_y - c_xc_y$

처럼 전개 가능함(개빡세네 에휴...)

그럼 이제 각 요소의 곱셈자리마다 분배법칙을 이용할 수 있음

$= b_y(b_x + a_x) - a_y(b_x + a_x) \+ c_y(c_x + b_x) - b_y(c_x + b_x) \+ a_y(c_x + a_x) - c_y(a_x + c_x)$

로 식을 변환할 수 있음

그럼 이제 다시 곱셈법칙을 이용해서 처리할 수 있는데

$= (b_y - a_y)(b_x + a_x)$ $+ (c_y - b_y)(c_x + b_x)$ $+ (a_y - c_y)(c_x + a_x)$

로 전개가 완료됨

원래대로 잘 출력됨!

이제 백페이스 컬링 할차례

백페이스 컬링

void triangle(Triangle t, TGAImage &framebuffer, TGAColor color) 
{
    int bbminx = std::min(std::min(t.a.x, t.b.x), t.c.x); 
    int bbminy = std::min(std::min(t.a.y, t.b.y), t.c.y); 
    int bbmaxx = std::max(std::max(t.a.x, t.b.x), t.c.x);
    int bbmaxy = std::max(std::max(t.a.y, t.b.y), t.c.y);

    double total_area = get_area(t);

#pragma omp parallel for
    for (int x=bbminx; x<=bbmaxx; x++) 
    {
        for (int y=bbminy; y<=bbmaxy; y++) 
        {
            double alpha = get_area(Triangle(Vec3(x,y,0), Vec3(t.b.x, t.b.y, 0), Vec3(t.c.x, t.c.y, 0))) / total_area;
            double beta  = get_area(Triangle(Vec3(x,y,0), Vec3(t.c.x, t.c.y, 0), Vec3(t.a.x, t.a.y, 0))) / total_area;
            double gamma =get_area(Triangle(Vec3(x,y,0), Vec3(t.a.x, t.a.y, 0), Vec3(t.b.x, t.b.y, 0))) / total_area;
            if (alpha<0 || beta<0 || gamma<0) continue;
            framebuffer.set(x, y, color);
        }
    }
}

이코드를 잘 봐보자

점 a,b,c가 있을때

오른손 좌표계를 기준으로 함

처럼 됨. 이때 외적 벡터의 z는 양수가 됨

• 왼손 좌표계면 z는 음수지 ㅇㅇ

하지만 이렇게 좌표가 있다면 오른손 좌표계 기준으로 외적 벡터의 z는 음수가 됨

• 왼손 좌표계면 z는 양수지 ㅇㅇ

이렇게 좌표계에 맞춰서 원하는 좌표계를 정했다면

정면이 아닌 z축을 가지는 삼각형은 렌더링을 패싱하면 되는거임

void triangle(Triangle t, TGAImage &framebuffer, TGAColor color) 
{
    int bbminx = std::min(std::min(t.a.x, t.b.x), t.c.x); 
    int bbminy = std::min(std::min(t.a.y, t.b.y), t.c.y); 
    int bbmaxx = std::max(std::max(t.a.x, t.b.x), t.c.x);
    int bbmaxy = std::max(std::max(t.a.y, t.b.y), t.c.y);

    double total_area = get_area(t);

    //add
    if (total_area < 0) return;

#pragma omp parallel for
    for (int x=bbminx; x<=bbmaxx; x++) 
    {
        for (int y=bbminy; y<=bbmaxy; y++) 
        {
            double alpha = get_area(Triangle(Vec3(x,y,0), Vec3(t.b.x, t.b.y, 0), Vec3(t.c.x, t.c.y, 0))) / total_area;
            double beta  = get_area(Triangle(Vec3(x,y,0), Vec3(t.c.x, t.c.y, 0), Vec3(t.a.x, t.a.y, 0))) / total_area;
            double gamma =get_area(Triangle(Vec3(x,y,0), Vec3(t.a.x, t.a.y, 0), Vec3(t.b.x, t.b.y, 0))) / total_area;
            if (alpha<0 || beta<0 || gamma<0) continue;
            framebuffer.set(x, y, color);
        }
    }
}

그게 add 주석 부분임

졸라 간단스

이런 렌더링이 됨

하지만 아직 문제가 있음

뒷면에 해당되는 삼각형 예를들어 입안, 옷 안쪽은 무시되거나 다른 삼각형 위에 렌더링이 됨

이건 다음에 해결하도록~

전체 코드

• main.cpp

  #include <chrono>
  #include <cmath>
  #include <cstdlib>
  #include <ctime>
  #include "tgaimage.h"
  #include <iostream>
  #include <fstream>
  #include <string>
  

#include "Model.h" #include "Vec3.h"

constexpr TGAColor white = {255, 255, 255, 255}; constexpr TGAColor green = { 0, 255, 0, 255}; constexpr TGAColor red = { 0, 0, 255, 255}; constexpr TGAColor blue = {255, 128, 64, 255}; constexpr TGAColor yellow = { 0, 200, 255, 255}; constexpr int width = 1024; constexpr int height = 1024;

float get_triangle_area(Triangle t) { return 0.5 * ( (t.b.y-t.a.y)(t.b.x+t.a.x) + (t.c.y-t.b.y)(t.c.x+t.b.x) + (t.a.y-t.c.y)*(t.a.x+t.c.x) ); }

void triangle(Triangle t, TGAImage &framebuffer, TGAColor color) { int bbminx = std::min(std::min(t.a.x, t.b.x), t.c.x); int bbminy = std::min(std::min(t.a.y, t.b.y), t.c.y); int bbmaxx = std::max(std::max(t.a.x, t.b.x), t.c.x); int bbmaxy = std::max(std::max(t.a.y, t.b.y), t.c.y);

double total_area = get_triangle_area(t);

//if (total_area < 0) return;

#pragma omp parallel for for (int x=bbminx; x<=bbmaxx; x++) { for (int y=bbminy; y<=bbmaxy; y++) { double alpha = get_triangle_area(Triangle(Vec3(x,y,0), Vec3(t.b.x, t.b.y, 0), Vec3(t.c.x, t.c.y, 0))) / total_area; double beta = get_triangle_area(Triangle(Vec3(x,y,0), Vec3(t.c.x, t.c.y, 0), Vec3(t.a.x, t.a.y, 0))) / total_area; double gamma =get_triangle_area(Triangle(Vec3(x,y,0), Vec3(t.a.x, t.a.y, 0), Vec3(t.b.x, t.b.y, 0))) / total_area; if (alpha<0 || beta<0 || gamma<0) continue; framebuffer.set(x, y, color); } } }

std::tuple<int,int> project(Vec3 v) { return { static_cast(std::round((v.x + 1.) * width / 2)), static_cast(std::round((v.y + 1.) * height / 2)) }; }

std::vector<std::pair<Triangle, TGAColor>> triangles;

int main(int argc, char** argv) {
if (argc != 2) { std::cerr << "Err Usage: " << argv[0] << " obj/model.obj" << std::endl; return 1; }

Model model(argv[1]);
TGAImage framebuffer(width, height, TGAImage::RGB);

// triangle(Triangle(Vec3(7, 45, 0), Vec3(35, 100, 0), Vec3(45,  60, 0)), framebuffer, red);
// triangle(Triangle(Vec3(120, 35, 0), Vec3(90,   5, 0), Vec3(45, 110, 0)), framebuffer, white);
// triangle(Triangle(Vec3(115, 83, 0), Vec3(80,  90, 0), Vec3(85, 120, 0)), framebuffer, green);

Vec3 camera_pos(0,0, 1);

for (int i = 0; i < model.nfaces(); i++) 
{    
    auto [ax, ay] = project(model.vert(i, 0));
    auto [bx, by] = project(model.vert(i, 1));
    auto [cx, cy] = project(model.vert(i, 2));

    TGAColor rnd;
    for (int c = 0; c < 3; c++) rnd[c] = std::rand() % 255;

    triangle(Triangle(Vec3(ax, ay, 0), Vec3(bx, by, 0), Vec3(cx, cy, 0)), framebuffer, rnd);
}

framebuffer.write_tga_file("framebuffer.tga");
return 0;

}

- Vec3.h
```cpp
#ifndef VEC3_H
#define VEC3_H
#include <cmath>

class Vec3
{
public:
    float x, y, z;

    Vec3(float x_ = 0.0f, float y_ = 0.0f, float z_ = 0.0f)
        : x(x_), y(y_), z(z_) {}

    Vec3 operator-(const Vec3 &v) const
    {
        return Vec3(this->x - v.x, this->y - v.y, this->z - v.z);
    }

    Vec3 operator+(const Vec3 &v) const
    {
        return Vec3(this->x + v.x, this->y + v.y, this->z + v.z);
    }

    float& operator[](int i)
    {
        if (i == 0) return x;
        if (i == 1) return y;
        return z;
    }

    const float& operator[](int i) const
    {
        if (i == 0) return x;
        if (i == 1) return y;
        return z;
    }

    float length_squared() const 
    {
        return this->x * this->x + this->y * this->y + this->z * this->z;
    }

    float length() const 
    {
        return std::sqrt(length_squared());
    }
};

inline float dot(Vec3 v1, Vec3 v2)
{
    return v1.x * v2.x + v1.y * v2.y + v1.z * v2.z;
}

inline Vec3 cross(Vec3 v1, Vec3 v2)
{
    return Vec3(
        v1.y * v2.z - v1.z * v2.y,
        v1.z * v2.x - v1.x * v2.z,
        v1.x * v2.y - v1.y * v2.x);   
}

class Triangle
{
public:
    Vec3 a;
    Vec3 b;
    Vec3 c;
    Triangle(Vec3 v1, Vec3 v2, Vec3 v3) : a(v1), b(v2), c(v3) {}

};

#endif // VEC3_H

• Model.h

  #ifndef MODEL_H
  #define MODEL_H
  

#include #include

class Vec3;

class Model { std::vector verts = {}; std::vector facet_vrt = {}; public: Model(const std::string filename); int nverts() const; int nfaces() const; Vec3 vert(const int i) const; Vec3 vert(const int iface, const int nthvert) const; };

#endif // MODEL_H

- Model.cpp
```cpp
#include <fstream>
#include <iostream>
#include <sstream>
#include "model.h"
#include "Vec3.h"

Model::Model(const std::string filename) {
    std::ifstream in;
    in.open(filename, std::ifstream::in);
    if (in.fail()) return;
    std::string line;
    while (!in.eof()) {
        std::getline(in, line);
        std::istringstream iss(line.c_str());
        char trash;
        if (!line.compare(0, 2, "v ")) {
            iss >> trash;
            Vec3 v;
            for (int i : {0,1,2}) iss >> v[i];
            verts.push_back(v);
        } else if (!line.compare(0, 2, "f ")) {
            int f,t,n, cnt = 0;
            iss >> trash;
            while (iss >> f >> trash >> t >> trash >> n) {
                facet_vrt.push_back(--f);
                cnt++;
            }
            if (3!=cnt) {
                std::cerr << "Error: the obj file is supposed to be triangulated" << std::endl;
                return;
            }
        }
    }
    std::cerr << "# v# " << nverts() << " f# "  << nfaces() << std::endl;
}

int Model::nverts() const { return verts.size(); }
int Model::nfaces() const { return facet_vrt.size()/3; }

Vec3 Model::vert(const int i) const {
    return verts[i];
}

Vec3 Model::vert(const int iface, const int nthvert) const {
    return verts[facet_vrt[iface*3+nthvert]];
}

기본 점 찍기

#include <cmath>
#include "tgaimage.h"

constexpr TGAColor white   = {255, 255, 255, 255}; // attention, BGRA order
constexpr TGAColor green   = {  0, 255,   0, 255};
constexpr TGAColor red     = {  0,   0, 255, 255};
constexpr TGAColor blue    = {255, 128,  64, 255};
constexpr TGAColor yellow  = {  0, 200, 255, 255};

int main(int argc, char** argv) {
    constexpr int width  = 64 * 4;
    constexpr int height = 64 * 4;
    TGAImage framebuffer(width, height, TGAImage::RGB);

    int ax =  7 * 4, ay =  3 * 4;
    int bx = 12 * 4, by = 37 * 4;
    int cx = 62 * 4, cy = 53 * 4;

    framebuffer.set(ax, ay, white);
    framebuffer.set(bx, by, white);
    framebuffer.set(cx, cy, white);

    framebuffer.write_tga_file("framebuffer.tga");
    return 0;
}

그냥 프레임버퍼에 A, B, C를 흰색상의 픽셀로 찍고 tga로 변환하는거임

그럼 이런 작은 점 3개가 찍힘

Barycentric coordinates

무게중심 좌표라고 불림

$t$ : 보간 비율 (0~1) $P = (1-t) \cdot A + t \cdot B$

이 개념은 두 점 A, B가 있고, 두 점 사이의 간격을 비율로 표현한거임

$t = 0$일때, $A + 0 \cdot B$ $t = 1$일때, $0 \cdot A + B$

가 됨

물론 반대로 $$P=tA+(1-t)B$$ 해도 되긴 한데, 이럼 시작점이 A가 아니라 B가 된다는 차이점만 잇지 ㅇㅇ

$P = (1-t) \cdot A + t \cdot B$ $= A - t \cdot A + t \cdot B$ $= A + t \cdot (B - A)$

로 전개가 가능함

즉, 두 점 A,B를 잇는 선분 사이의 점 P의 좌표를 비율 t를 이용해 구하는 방법임

그리고 2차원 평면에서 진행되므로 $A = (ax,ay)$ 와 $B = (bx,by)$로 표현할 수 있음

따라서 x와 y를 기준으로 살펴보면

$P = A + t \cdot (B - A)$

$x(t) = ax + t \cdot (bx - ax)$ $y(t) = ay + t \cdot (by - ay)$ 가 성립함을 알 수 있음

그냥 선형보간 공식과 같음

void line(int ax, int ay, int bx, int by, TGAImage &framebuffer, TGAColor color) 
{
    for (float t=0.; t<1.; t+=.02) {
        int x = std::round( ax + (bx-ax)*t );
        int y = std::round( ay + (by-ay)*t );
        framebuffer.set(x, y, color);
    }
}

이런 코드를 main.cpp에 선언해줌

그냥 0.1씩 더하면서, t를 비율로 보간해주는거임 그리고 색상은 원하는 색상으루 ㅇㅇ

int main(int argc, char** argv) 
{
    // * 4 없앰
    constexpr int width  = 64;
    constexpr int height = 64;
    TGAImage framebuffer(width, height, TGAImage::RGB);

    int ax =  7, ay =  3;
    int bx = 12, by = 37;
    int cx = 62, cy = 53;

    line(ax, ay, bx, by, framebuffer, blue);
    line(cx, cy, bx, by, framebuffer, green);
    line(cx, cy, ax, ay, framebuffer, yellow);
    line(ax, ay, cx, cy, framebuffer, red);

    framebuffer.set(ax, ay, white);
    framebuffer.set(bx, by, white);
    framebuffer.set(cx, cy, white);

    framebuffer.write_tga_file("framebuffer.tga");
    return 0;
}

그리고 main.cpp를 이렇게 수정해줌

이런 결과가 나옴

빈틈이 보이고, 노란색 픽셀이 빨간선 위에 출력됨

문제가 뭘까?

• $cx$->$ax$ = 62 -> 7 = 55개의 픽셀 $t = 0$ ~ $t = 1$ -> 0.02씩 인터벌 = 51개

즉, 총 55개의 픽셀이 필요한데, 51개만 그려지고 있으니 빈공간이 발생하게 되는거임

해결법. 보간 비율 t를 미리 정의하자

핵심 개념은 쉬움

두 점 $ax, bx$가 있을때, 지금까지는 t를 반복처리 했음 근데 x 혹은 y 좌표를 반복처리 해서 구할수도 있음

두 점 $ax, bx$에 대한 t의 비율은 다음처럼 나타낼 수 있음

$x - ax$ : ax로부터의 x좌표의 거리 $bx - ax$ : bx로부터의 ax까지의 거리 $t = \frac{x - ax}{bx - ax}$

로 나타낼 수 있음

이를 코드로 나타내면

void line(int ax, int ay, int bx, int by, TGAImage &framebuffer, TGAColor color) 
{
    for (int x=ax; x<=bx; x++) 
    {
        float t = (x-ax) / static_cast<float>(bx-ax);
        int y = std::round( ay + (by-ay)*t );
        framebuffer.set(x, y, color);
    }
}

이렇게 코드를 변경하게 되면 위에서 기본적으로 t를 반복할때 나타났던 문제인

• 픽셀의 갯수가 차이남

이 해결되게 됨

하지만 문제가 또 하나 발생함 만약 $ax <bx$면?

따라서 이를 정렬해줘야함

항상 ax가 bx보다 작도록!

void line(int ax, int ay, int bx, int by, TGAImage &framebuffer, TGAColor color) 
{
    if (ax > bx)
    {
        std::swap(ax, bx);
        std::swap(ay, by);
    }

    for (int x=ax; x<=bx; x++) 
    {
        float t = (x-ax) / static_cast<float>(bx-ax);
        int y = std::round( ay + (by-ay)*t );
        framebuffer.set(x, y, color);
    }
}

이렇게 됨

파란쪽은 왜저럴까?

지금 우리는 x를 기준으로 샘플링을 하는 중임 즉, 두 x좌표의 차이가 적고, y좌표의 차이가 크면 y에 비해 x좌표의 샘플수가 적으므로 텅 비어버리는거임

즉 $ax - bx < ay - by$ 인 경우에 x와 y를 바꿔주면 되는거임

void line(int ax, int ay, int bx, int by, TGAImage &framebuffer, TGAColor color) 
{
    bool is_x_smaller = std::abs(ax - bx) < std::abs(ay - by);

    if (is_x_smaller)
    {
        std::swap(ax, ay);
        std::swap(bx, by);
    }

    if (ax > bx)
    {
        std::swap(ax, bx);
        std::swap(ay, by);
    }

    for (int x=ax; x<=bx; x++) 
    {
        float t = (x-ax) / static_cast<float>(bx-ax);
        int y = std::round( ay + (by-ay)*t );

        if (is_x_smaller)
        {
            framebuffer.set(y, x, color); //y, x 스왑된거 적용해주기
        }
        else
        {
            framebuffer.set(x, y, color);
        }
    }
}

이렇게 코드가 바뀜!

가 됐다!!

최적화

#include "tgaimage.h"
#include <chrono>
#include <iostream>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <algorithm>
#include <iomanip>

constexpr TGAColor white   = {255, 255, 255, 255}; // attention, BGRA order
constexpr TGAColor green   = {  0, 255,   0, 255};
constexpr TGAColor red     = {  0,   0, 255, 255};
constexpr TGAColor blue    = {255, 128,  64, 255};
constexpr TGAColor yellow  = {  0, 200, 255, 255};

void line(int ax, int ay, int bx, int by, TGAImage &framebuffer, TGAColor color) 
{
    bool is_x_smaller = (std::abs(ax - bx) < std::abs(ay - by));

    if (is_x_smaller)
    {
        std::swap(ax, ay);
        std::swap(bx, by);
    }

    if (ax > bx)
    {
        std::swap(ax, bx);
        std::swap(ay, by);
    }

    for (int x=ax; x<=bx; x++) 
    {
        float t = (x-ax) / static_cast<float>(bx-ax);
        int y = std::round( ay + (by-ay)*t );

        if (is_x_smaller)
        {
            framebuffer.set(y, x, color);
        }
        else
        {
            framebuffer.set(x, y, color);
        }
    }
}

int main(int argc, char** argv) 
{
    // 1. start-time
    auto start_time = std::chrono::system_clock::now();
    std::time_t start_c = std::chrono::system_clock::to_time_t(start_time);

    constexpr int width  = 64;
    constexpr int height = 64;
    TGAImage framebuffer(width, height, TGAImage::RGB);

    std::srand(std::time(nullptr));
    for (int i=0; i<(1<<24); i++) {
        int ax = rand()%width, ay = rand()%height;
        int bx = rand()%width, by = rand()%height;
        line(ax, ay, bx, by, framebuffer, 
        {
            static_cast<uint8_t>(rand() % 255),
            static_cast<uint8_t>(rand() % 255),
            static_cast<uint8_t>(rand() % 255),
            static_cast<uint8_t>(rand() % 255)
        });
    }

    framebuffer.write_tga_file("framebuffer.tga");

    // 2. end-time
    auto end_time = std::chrono::system_clock::now();
    std::time_t end_c = std::chrono::system_clock::to_time_t(end_time);

    // 3. total-time
    std::chrono::duration<double> execution_time = end_time - start_time;

    std::cout << "start time: " << std::put_time(std::localtime(&start_c), "%Y-%m-%d %H:%M:%S") << "\n";
    std::cout << "end time: " << std::put_time(std::localtime(&end_c), "%Y-%m-%d %H:%M:%S") << "\n";
    std::cout << "total time: " << execution_time.count() << " s\n";

    return 0;
}

이렇게 main문을 살짝 수정함

1<<24번의 반복문을 수행함 총 1600만번의 반복 * 픽셀계산이 합쳐짐

약 29초정도 소요됨ㅇㅇ

이걸 최적화 하려면?

1. y계산 최적화

void line(int ax, int ay, int bx, int by, TGAImage &framebuffer, TGAColor color) 
{
    bool is_x_smaller = (std::abs(ax - bx) < std::abs(ay - by));

    if (is_x_smaller)
    {
        std::swap(ax, ay);
        std::swap(bx, by);
    }

    if (ax > bx)
    {
        std::swap(ax, bx);
        std::swap(ay, by);
    }

    for (int x=ax; x<=bx; x++) 
    {
        float t = (x-ax) / static_cast<float>(bx-ax);
        int y = std::round( ay + (by-ay)*t );

        if (is_x_smaller)
        {
            framebuffer.set(y, x, color);
        }
        else
        {
            framebuffer.set(x, y, color);
        }
    }
}

이부분을 봐보자

그리고 2차원 평면에서 진행되므로 $A = (ax,ay)$ 와 $B = (bx,by)$로 표현할 수 있음

따라서 x와 y를 기준으로 살펴보면

$P = A + t \cdot (B - A)$

$x(t) = ax + t \cdot (bx - ax)$ $y(t) = ay + t \cdot (by - ay)$

가 성립함을 알 수 있음

두 점 $ax, bx$가 있을때, 지금까지는 t를 반복처리 했음 근데 x 혹은 y 좌표를 반복처리 해서 구할수도 있음

두 점 $ax, bx$에 대한 t의 비율은 다음처럼 나타낼 수 있음

$x - ax$ : ax로부터의 x좌표의 거리 $bx - ax$ : bx로부터의 ax까지의 거리 $t = \frac{x - ax}{bx - ax}$

이렇게 두 개념을 위해 설명했음

코드를 보면 우리는 x좌표를 증가시키며 y좌표를 결정짓고 있음 그리고 round연산을 통해 cpu과부하가 걸림

$y(t) = ay + t \cdot (by - ay)$

$t = \frac{x - ax}{bx - ax}$

$y(t) = ay + \frac{x - ax}{bx - ax} \cdot (by - ay)$

로 나타낼 수 잇음

여기서 퀴즈

1. $x-ax$ 는 뭘 의미하는걸까?

정답 : 수열

$y(t) = ay + \frac{x - ax}{bx - ax} \cdot (by - ay)$ $= ay + (x - ax) \cdot \frac{by - ay}{bx - ax}$ 으로 곱셈법칙을 이용해 바꿀 수 있음

$\frac{by - ay}{bx - ax} = \Delta$ 라고 했을때,

1. $x - ax = 0$일때, $y(t) = ay$
2. $x - ax = 1$일때, $y(t) = ay + \Delta$
3. $x - ax = 2$일때, $y(t) = ay + 2 \cdot \Delta = ay + \Delta + \Delta$
   x가 증가함에 따라 이전 값에 누적합을 구해주면 되는거임 즉, y값을 초기화 시켜놓고, x가 반복문을 통해 증가될때마다 delta를 누적합 해주면 그게 y값이 되는거임!
   물론 min y값부터 시작해야함ㅇㅇㅇ

void line(int ax, int ay, int bx, int by, TGAImage &framebuffer, TGAColor color) 
{
    bool is_x_smaller = (std::abs(ax - bx) < std::abs(ay - by));

    if (is_x_smaller)
    {
        std::swap(ax, ay);
        std::swap(bx, by);
    }

    if (ax > bx)
    {
        std::swap(ax, bx);
        std::swap(ay, by);
    }

    float y = ay;

    for (int x=ax; x<=bx; x++) 
    {
        //float t = (x-ax) / static_cast<float>(bx-ax); //delete
        //int y = std::round( ay + (by-ay)*t ); //delete

        if (is_x_smaller) 
            framebuffer.set(y, x, color);
        else 
            framebuffer.set(x, y, color);

        y  += (by - ay) / static_cast<float>(bx - ax);
    }
}

이렇게 코드가 바뀜!!

약 29초 -> 18초로 줄음!!!

2. 픽셀은 정수

먼저 코드부터 보자

void line(int ax, int ay, int bx, int by, TGAImage &framebuffer, TGAColor color) 
{
    bool is_x_smaller = (std::abs(ax - bx) < std::abs(ay - by));

    if (is_x_smaller)
    {
        std::swap(ax, ay);
        std::swap(bx, by);
    }

    if (ax > bx)
    {
        std::swap(ax, bx);
        std::swap(ay, by);
    }

    int y = ay;
    float diff = 0;

    for (int x=ax; x<=bx; x++) 
    {
        //float t = (x-ax) / static_cast<float>(bx-ax); //delete
        //int y = std::round( ay + (by-ay)*t ); //delete

        if (is_x_smaller) 
            framebuffer.set(y, x, color);
        else 
            framebuffer.set(x, y, color);

        diff  += (by - ay) / static_cast<float>(bx - ax);
        if (diff > 0.5f)
        {
            y += by > ay ? 1 : -1;
            diff -= 1;
        }
    }
}

컴퓨터 화면의 픽셀은 소숫점 단위가 아닌 정수 단위임 $1,2,3...$ 이렇게 진행된다는거임

화면은 2차원이지? 만약 5,5위치의 픽셀은 5 * 가로 픽셀 수 + 5개가 되는거임

하지만 이전의 코드는 y가 소숫점 단위임 화면은 어짜피 소숫점 단위의 픽셀에 점을 찍지 못하니 자동으로 round가 적용되어 불필요한 연산이 들어가게 되는거임

브레슨햄 알고리즘은 다음과 같은 개념임

1. 두 좌표 사이의 기울기를 구함
2. 기울기가 지나는 픽셀을 기준으로 절반(0.5)위쪽으로 지나가면 위의 픽셀에 점을 찍음
3. 그게 아니라면 아래 픽셀에 점을 찍음

2차원에서의 두 좌표사이의 기울기는 쉽게 구할 수 있음

a = $ax, ay$, b = $bx, by$라고 할때, $\Delta ab = \frac{by - ay}{bx - ax}$

int y = ay;
float diff = 0;

   for (int x=ax; x<=bx; x++) 
   {        
       if (is_x_smaller) 
        framebuffer.set(y, x, color);
    else 
        framebuffer.set(x, y, color);

    diff  += (by - ay) / static_cast<float>(bx - ax);
    if (diff > 0.5f)
    {
        y += by > ay ? 1 : -1;
        diff -= 1;
    }
}

이 코드에서 diff += (by - ay) / static_cast<float>(bx - ax);는 기울기의 누적 합이고, 해당 합이 0.5를 넘어가면 다음 픽셀에 점을 찍도록 하는거임

연산이 늘어났으므로 시간이 약 18초 -> 20초로 증가함

3. 완전한 bresenham algorithm

void line(int ax, int ay, int bx, int by, TGAImage &framebuffer, TGAColor color) 
{
    //...

    int y = ay;
    float diff = 0;

    for (int x=ax; x<=bx; x++) 
    {
        //...

        diff  += (by - ay) / static_cast<float>(bx - ax);
        if (diff > 0.5f)
        {
            y += by > ay ? 1 : -1;
            diff -= 1;
        }
    }
}

$dx = bx - ax$ $dy = by- ay$

라고 해보자

그럼 위의 코드를 다음과 같이 수식으로 나타낼 수 있음

$diff = \frac{dy}{dx}$ $dx \cdot diff = \frac{dy}{dx} \cdot dx$

이때 diff를 idiff라고 ㅏ면

$idiff = dy$

가 됨

즉, diff가 관여하는 모든 계산에 dx를 곱하면 계산이 간소화 되는거임! ...... 근데 문제가 있음

if (diff > 0.5f) 이 조건문 또한 diff의 영향을 받으므로 양변에 dx를 곱해줘야함 if (idiff > 0.5 * dx)가 됨 이때 dx가 3이라면 조건문의 조건은 1.5가 됨

따라서 완전한 정수연산이 불가능해짐 즉, 모든 diff가 참여하는 연산에dx가 아닌 2 * dx를 해주면 모든 연산이 정수연산이 되어 연산을 최적화 할 수 있음

void line(int ax, int ay, int bx, int by, TGAImage &framebuffer, TGAColor color) 
{
    bool is_x_smaller = (std::abs(ax - bx) < std::abs(ay - by));

    if (is_x_smaller)
    {
        std::swap(ax, ay);
        std::swap(bx, by);
    }

    if (ax > bx)
    {
        std::swap(ax, bx);
        std::swap(ay, by);
    }

    int y = ay;
    int idiff = 0; //idiff = diff * 2 * dx

    for (int x=ax; x<=bx; x++) 
    {
        if (is_x_smaller) 
            framebuffer.set(y, x, color);
        else 
            framebuffer.set(x, y, color);

        int dx = bx - ax;

        idiff  += 2 * (by - ay); //diff * 2 * dx = ((by - ay) / dx) * 2 * dx
        if (idiff > dx /* 0.5f * 2 * dx */ )
        {
            y += by > ay ? 1 : -1;
            idiff -= 2 * dx /* 1 * 2 * dx */;
        }
    }
}

약간 빨라졌는데 1번의 최적화보다는 여전히 느림

사실 부동소수점 계산이 현대의 컴퓨터에서는 정수 계산과 큰 차이가 없음

4. if문 없애기

cpu는 파이프라이닝을 통해 구문들을 진행시킴

연산은 전부 명령어임 자세한건 cs공부를 하도록!

이때 기본적인 연산은 파이프라인 위에 탑승해서 병렬적으로 연산이 수행됨 한번에 하나의 연산만 하지는 않는다는 뜻임

근데 조건문, 특히 연산을 해야하는 조건문은 좀 얘기가 다름

1. 연산 결과는 다른 연산이 끝날때까지 예측이 불가능함
2. 따라서 먼저 true로 예측을 하고, 조건문 내부를 파이프라인에 올림
3. 실제로 true면 그대로 진행
4. false가 되면 파이프라인위의 조건문 내부 코드를 flush 후 다시 진행됨

이래서 특정 if문을 사용하면 느려지는거임

void line(int ax, int ay, int bx, int by, TGAImage &framebuffer, TGAColor color) 
{
    bool is_x_smaller = (std::abs(ax - bx) < std::abs(ay - by));

    if (is_x_smaller)
    {
        std::swap(ax, ay);
        std::swap(bx, by);
    }

    if (ax > bx)
    {
        std::swap(ax, bx);
        std::swap(ay, by);
    }

    int y = ay;
    int idiff = 0;

    for (int x=ax; x<=bx; x++) 
    {
        if (is_x_smaller) 
            framebuffer.set(y, x, color);
        else 
            framebuffer.set(x, y, color);

        int dx = bx - ax;

        idiff  += 2 * (by - ay);
        if (idiff > dx)
        {
            y += by > ay ? 1 : -1;
            idiff -= 2 * dx;
        }
    }
}

현재 우리의 코드에서 문제가 될만한 부분은 반복문 내부의 if조건문들임

is_x_smaller는 이미 동적으로 값이 변경되지 않음 즉, 호출되어도 결과가 100% false, true로 결정되므로 파이프라인 재조립이 필요없음 따라서 파이프라인에 올라가도 문제가 없음

idiff > dx는 동적으로 값이 계속 변경됨 따라서 파이프라인에 올라가있을때, 조건문의 결과에 따라 flush와 재연산이 계속 반복됨으로 연산 속도가 느려지게 됨

즉, 조건문을 없애고, 연산 결과에 조건문을 포함하는 트릭을 이용하면 연산 속도가 좋아지게 됨

핵심 개념은 cpp에서 bool값은 0 혹은 1이라는걸 이용하는거임

void line(int ax, int ay, int bx, int by, TGAImage &framebuffer, TGAColor color) 
{
    bool is_x_smaller = (std::abs(ax - bx) < std::abs(ay - by));

    if (is_x_smaller)
    {
        std::swap(ax, ay);
        std::swap(bx, by);
    }

    if (ax > bx)
    {
        std::swap(ax, bx);
        std::swap(ay, by);
    }

    int dx = bx - ax;
    int dy = std::abs(by - ay);
    int y_step = (by > ay) ? 1 : -1;
    int idiff = 0;

    for (int x = ax; x <= bx; x++) 
    {
        if (is_x_smaller) 
            framebuffer.set(y, x, color);
        else 
            framebuffer.set(x, y, color);

        idiff += 2 * dy;
        y += y_step * (idiff > dx);
        idiff -= 2 * dx * (idiff > dx); 
    }
}

이렇게 코드를 변경시킬 수 있음

결과를 구해두고 동적으로 바뀌는 결과값에 따라 전체 연산을 0 혹은 기존 결과로 유지시키는 전략임

느리네...

결과

1. 최적화 전

2. y계산 최적화

3. 브레슨햄 알고리즘 with float

4. 브레슨햄 알고리즘 with int

5. if브런치 파이프라이닝 제거

사실 이런결과가 나오는건 이유가 있음

코드는 컴파일러의 영향을 크게 받음

나는 젯브레인 라이더를 이용해서 테스트를 함 라이더에서는 vs 2026의 MSVC컴파일러를 이용하는 중임

최신의 컴파일러는 부동소수점 연산과 나눗셈 연산도 최적화를 해놓음 따라서, 조건문이 없는 2번의 y좌표 계산 최적화가 가장 빠른 속도를 내는거임

컴파일러의 성능에 따라 위의 다양한 최적화기법을 사용해볼 수 있다~~ 정도로만 짚고 넘어가자

풀이

재귀형태로 접근하는게 쉬움

재귀의 핵심은 DP와 같음

• 각 재귀의 반환값은 이미 정답임
• 그럼 어떤 값을 반환해야 원하는 값으로 이용할 수 있을지를 생각

그럼 이 문제에서 정답이 되려면, 각 재귀에서 반환값은 TreeNode가 되어야함

1. p 혹은 q가 발견되면 현재 노드를 리턴
2. 자신을 기준으로 왼쪽 노드와 오른쪽 노드를 재귀 탐색
3. 둘 중 하나에서만 값이 반환되었으면, 아직 자신이 조상이 아니므로, 반환된 값 그대로 부모노드로 반환
4. 둘 다 모두 반환되었으면, 자신이 최고깊이에 있는 최소 공통 조상 노드이므로, 자신을 반환

이를 코드로 나타내면 다음과 같음

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {

        //안전장치
        if (!root) return nullptr;

        // 1. p 혹은 q가 발견되면 현재 노드를 리턴
        if (root == p || root == q) return root;

        // 2. 왼쪽 노드와 오른쪽 노드를 재귀 탐색
        auto left = lowestCommonAncestor(root->left, p, q);
        auto right = lowestCommonAncestor(root->right, p, q);

        // 4. 둘 다 모두 반환되었으면, 자신이 최고깊이에 있는 최소 공통 조상 노드이므로, 자신을 반환
        if (left && right) return root;

        // 3. 둘 중 하나에서만 값이 반환되었으면, 아직 자신이 조상이 아니므로, 반환된 값 그대로 부모노드로 반환
        if (left) return left;
        return right;
    }
};

이 문제는 미디엄 난이도인데, 처음으로 알고리즘의 개념을 접하면 접근하기 어려워서 인것같음

푸는 법과 어떤 개념인지 알면, 쉽네

블러라는 말을 들어봤지?

이렇게 원본이미지에서 흐릿하게 만드는걸 블러라고 함

이걸 구현하는 방법은 여러가지가 있음

일단 블러가 어떻게 동작되는지를 알아야함

블러 동작

블러는 기본적으로 흐릿해지는거임

그럼 흐릿한게 뭐냐? 이 질문에 대한 답을 하면, 어떻게 블러를 구현해야할지 감이 올거임

흐릿함은 특정 픽셀의 색상이 해당 픽셀 주변의 픽셀의 색과 비슷하여 흐릿하게 보이는 것

빨간 원을 보면, 왼쪽은 픽셀간 색상 차이가 뚜렷한데 반해 오른쪽은 픽셀간 색상 차이가 미미함

kernel

위키피디아의 image proccessing - kernel에 관한 설명임

블러 효과는 이미지와 이미지의 각 픽셀 색상에 대하여 주변 픽셀의 색을 구한 후, 평균을 내어 만드는 효과임

작은 3*3 : kernel input : 이미지

이렇게 kernel의 가중치를 곱한 후 합산하는 것을 Convolution(합성곱)이라고 함

합성곱 최적화

이게 좀 불편함

2차원 기준으로

이미지가 $NM$크기이고 kernel이 $nm$의 크기일때, 연산 횟수는 $O(NMn*m)$이 됨

즉, 600*360크기의 이미지가 있을때 5*5크기의 kernel을 사용하면

$6003605*5 = 5,400,000$번의 연산이 이뤄지게 됨

이걸 연산횟수를 줄일 수 있음

박스 블러의 kernel을 보자

총 3*3크기의 행렬을 이용중이고, 가중치를 1/9로 모두 동일하게 나누고 있음

이때 kernel을 두 1차원의 행렬의 곱으로 재구성 할 수 있음

이렇게 두 1차원 행렬의 곱이 곧 2차원 kernel과 같다는 것을 알 수 있음

이렇게 되면 $O(NM(n+m))$으로 연산횟수가 줄어들음

즉, 2차원 kernel을 이용할때는 kernel이 정사각형 행렬인만큼 $n^2$만큼의 연산이 소요되었는데, 1차원 kernel을 2개 사용하면, $n * 2$만큼의 연산으로 줄어들게 됨

그리고 kernel의 크기가 클수록 연산횟수 차이가 커짐

그리고 이 개념은 3차원까지 확대가능함

2차원은 x,y 혹은 u,v에 대해서 수행하지만 3차원은 x,y,z이므로, 3차원 kernel이 3개의 1차원 행렬로 표현할 수 있기만 한다면 충분히 최적화가 가능하다는거임

즉, 2차원 kernel이든 3차원 kernel이든, n차원이라고 햇을때, 1차원 kernel을 n개 이용하여 2차원, 3차원 kernel을 만들 수 있으면 해당 1차원 kernel들을 연산에 이용하여 convolution이 가능하다는거임

박스 블러

박스 블러는

이렇게 seperable filter를 적용하여 연산횟수를 줄일 수 있는 블러임

이걸 3*3이 아닌 5*5크기의 kernel을 이용해 계산하겠음

Vec4& Image::GetPixel(int i, int j)
{
    i = std::clamp(i, 0, this->width - 1);
    j = std::clamp(j, 0, this->height - 1);

    return this->pixels[i + this->width * j];
}

void Image::BoxBlur5()
{
    std::vector<Vec4> pixelsBuffer(this->pixels.size());

    //가로 블러
    for (int j = 0; j < this->height; j++)
    {
        for (int i = 0; i < this->width; i++)
        {
            Vec4 neighbor = {0,0,0,1};
            for (int k = -2; k < 3; ++k)
            {
                auto color = this->GetPixel(i + k, j);
                neighbor.v[0] += color.v[0];
                neighbor.v[1] += color.v[1];
                neighbor.v[2] += color.v[2];
            }

            pixelsBuffer[i + this->width * j].v[0] = neighbor.v[0] * 0.2f;
            pixelsBuffer[i + this->width * j].v[1] = neighbor.v[1] * 0.2f;
            pixelsBuffer[i + this->width * j].v[2] = neighbor.v[2] * 0.2f;
        }
    }

    std::swap(this->pixels, pixelsBuffer);

    //세로 블러
    for (int j = 0; j < this->height; j++)
    {
        for (int i = 0; i < this->width; i++)
        {
            Vec4 neighbor = {0,0,0,1};
            for (int k = -2; k < 3; ++k)
            {
                auto color = this->GetPixel(i, j + k);
                neighbor.v[0] += color.v[0];
                neighbor.v[1] += color.v[1];
                neighbor.v[2] += color.v[2];
            }

            pixelsBuffer[i + this->width * j].v[0] = neighbor.v[0] * 0.2f;
            pixelsBuffer[i + this->width * j].v[1] = neighbor.v[1] * 0.2f;
            pixelsBuffer[i + this->width * j].v[2] = neighbor.v[2] * 0.2f;
        }
    }

    std::swap(this->pixels, pixelsBuffer);
}

결국 박스 필터는 픽셀 위치에 대한 가중치가 모두 동일하다고 판단하여

$i,j$번째의 픽셀에 대하여 현재 위치 - 2 ~ 현재 위치 + 2까지의 픽셀에 대하여 색상의 합을 구하고, 모든 픽셀은 같은 가중치를 가지므로 총 5개의 픽셀이니, $/5$를 통해 평균치를 내어, 해당 픽셀을 가로/세로로 구분지어 계산함

이런 원본 사진이 있을때,

한번 밑의 세로부분을 제외하고 가로부분만 살펴보면

그리고 위의 가로부분을 제외하고 세로부분만 살펴보면

마지막으로 전체적으로 살펴보면

이렇게 가로/세로만 따로 했을때는 해당 방향으로 이미지가 늘어난 것을 볼 수 있고, 전체적으로 블러를 적용하면 어우러지는것을 볼 수 있음

가우시안 블러

$ \frac1{16} \begin{bmatrix} 1 \ 4 \ 6 \ 4 \ 1 \end{bmatrix} *\frac1{16} \begin{bmatrix} 1 & 4 & 6 & 4 & 1 \end{bmatrix} =\frac1{256} \begin{bmatrix} 1 & 4 & 6 & 4 & 1 \ 4 & 16 & 24 & 16 & 4 \ 6 & 24 & 36 & 24 & 6 \ 4 & 16 & 24 & 16 & 4 \ 1 & 4 & 6 & 4 & 1 \end{bmatrix} $

로 표현가능함

즉, 1차원 행렬 2개로 계산을 할 수 있다는거임

즉, 2차원 행렬에서 계산시에는 origin을 기준으로 $36/256 = 0.140625$이 되는데

1차원 행렬에서 계산시에는 origin을 기준으로 $6/16 = 0.375$가 됨

이렇게 각각의 가중치를 구하면

$[0.0625f, 0.25f, 0.375f, 0.25f, 0.0625f]$가 됨

따라서 이러한 가중치를 곱하면 됨

이 값은 실제 값이 아닌 근사치임 approximation 실제 값은 $[0.0545f, 0.2442f, 0.4026f, 0.2442f, 0.0545f]$정도가 됨

void Image::GaussianBlur5()
{
    std::vector<Vec4> pixelsBuffer(this->pixels.size());

    //const float weights[5] = { 0.0545f, 0.2442f, 0.4026f, 0.2442f, 0.0545f }; //실제값
    const float weights[5] = {0.0625f, 0.25f, 0.375f, 0.25f, 0.0625f}; //근사치

    // 가로 방향 (x 방향)
    for (int j = 0; j < this->height; j++)
    {
        for (int i = 0; i < this->width; i++)
        {
            Vec4 neighborColor = {0,0,0,1};
            for (int k = 0; k < 5; ++k)
            {
                Vec4 color = this->GetPixel(i + k - 2, j);

                neighborColor.v[0] += color.v[0] * weights[k];
                neighborColor.v[1] += color.v[1] * weights[k];
                neighborColor.v[2] += color.v[2] * weights[k];
            }

            pixelsBuffer[i + this->width * j].v[0] = neighborColor.v[0];
            pixelsBuffer[i + this->width * j].v[1] = neighborColor.v[1];
            pixelsBuffer[i + this->width * j].v[2] = neighborColor.v[2];
        }
    }

    std::swap(this->pixels, pixelsBuffer);

    // 세로 방향 (y 방향)
    for (int j = 0; j < this->height; j++)
    {
        for (int i = 0; i < this->width; i++)
        {
            Vec4 neighborColor = {0,0,0,1};
            for (int k = 0; k < 5; ++k)
            {
                Vec4 color = this->GetPixel(i, j + k - 2);

                neighborColor.v[0] += color.v[0] * weights[k];
                neighborColor.v[1] += color.v[1] * weights[k];
                neighborColor.v[2] += color.v[2] * weights[k];
            }

            pixelsBuffer[i + this->width * j].v[0] = neighborColor.v[0];
            pixelsBuffer[i + this->width * j].v[1] = neighborColor.v[1];
            pixelsBuffer[i + this->width * j].v[2] = neighborColor.v[2];
        }
    }

    std::swap(this->pixels, pixelsBuffer);
}

이런식으로 각 픽셀의 색상마다 가중치를 곱해주고 더해주면... 그게 블러 처리가 된 색상임!

박스 블러, 가우시안 블러 차이

박스 블러	가우시안 블러

블룸

블룸 효과를 만드는법은 간단함

1. 원본 이미지의 밝은 색상부분은 남겨두고, 어두운 색상은 검정색으로 만들어줌
2. 이렇게 만들어진 이미지에 대하여 가우시안 블러를 적용함
3. 원본 이미지와 블러 이미지를 합침

그럼 어두운 색상인지는 어떻게 아냐?

임계값을 정해주고, 해당 임계값을 기준으로 밝은지 어두운지 계산하면 됨

image.Bloom(0.5f, 50, 0.95f);

호출부 0.5f = threshold 밝기 임계값 50 = 가우시안 블러 적용 횟수 0.95f = 블러된 이미지의 곱할 계수

이미지에 값을 곱하여 더 밝게, 어둡게 설정가능

어두운 색상 검은색으로 바꾸기(상대 휘도)

이 개념은 Relative Luminance라는 공식을 이용하면 됨

상대휘도라고 부름

상대 휘도는 인간의 시각에 맞춰 밝기 스펙트럼을 이용해 가중치를 사용하며 나타낸 광도(빛의 밝기)임

Relative Luminance - wikipedia

이걸 보면

이런 공식이 나옴

즉, RGB에 따라 각각 다른 가중치를 곱해주고 더한 값이 밝기라는 뜻임

void Image::Bloom(const float& th, const int& numRepeat, const float& weight)
{
    const std::vector<Vec4> pixelsBackup = this->pixels;// 메모리 내용물까지 모두 복사

    //Brightness가 th 보다 작은 픽셀들을 모두 검은색으로 바꾸기
    for (int j = 0; j < height; j ++)
        for (int i = 0; i < width; i++)
        {
            auto& color = this->GetPixel(i,j);

            const float luminance = color.v[0] * 0.2126 + color.v[1] * 0.7152 + color.v[2] * 0.0722;

            if (luminance < th)
            {
                color.v[0] = 0.0f;
                color.v[1] = 0.0f;
                color.v[2] = 0.0f;
            }

        }
}

이 상태로 호출하여 살펴보면

이렇게 이미지가 바뀜

가우시안 블러 적용

void Image::Bloom(const float& th, const int& numRepeat, const float& weight)
{
    const std::vector<Vec4> pixelsBackup = this->pixels;// 메모리 내용물까지 모두 복사

    //Brightness가 th 보다 작은 픽셀들을 모두 검은색으로 바꾸기
    for (int j = 0; j < height; j ++)
        for (int i = 0; i < width; i++)
        {
            auto& color = this->GetPixel(i,j);

            const float luminance = color.v[0] * 0.2126 + color.v[1] * 0.7152 + color.v[2] * 0.0722;

            if (luminance < th)
            {
                color.v[0] = 0.0f;
                color.v[1] = 0.0f;
                color.v[2] = 0.0f;
            }

        }

    // 가우시안 블러 
    for (int i = 0; i < numRepeat; i++)
    {
        this->GaussianBlur5();
    }
}

이 상태로 호출하여 살펴보면

이미지 합체

블러까지 적용된 이미지에 계수를 곱하고, 원본 이미지와 더하면...

void Image::Bloom(const float& th, const int& numRepeat, const float& weight)
{
    const std::vector<Vec4> pixelsBackup = this->pixels;// 메모리 내용물까지 모두 복사

    //Brightness가 th 보다 작은 픽셀들을 모두 검은색으로 바꾸기
    for (int j = 0; j < height; j ++)
        for (int i = 0; i < width; i++)
        {
            auto& color = this->GetPixel(i,j);

            const float luminance = color.v[0] * 0.2126 + color.v[1] * 0.7152 + color.v[2] * 0.0722;

            if (luminance < th)
            {
                color.v[0] = 0.0f;
                color.v[1] = 0.0f;
                color.v[2] = 0.0f;
            }

        }

    // 가우시안 블러 
    for (int i = 0; i < numRepeat; i++)
    {
        this->GaussianBlur5();
    }

    // 이미지 합체
    for (int i = 0; i < pixelsBackup.size(); i++)
    {
        this->pixels[i].v[0] = std::clamp(pixels[i].v[0] * weight + pixelsBackup[i].v[0], 0.0f, 1.0f);
        this->pixels[i].v[1] = std::clamp(pixels[i].v[1] * weight + pixelsBackup[i].v[1], 0.0f, 1.0f);
        this->pixels[i].v[2] = std::clamp(pixels[i].v[2] * weight + pixelsBackup[i].v[2], 0.0f, 1.0f);
    }
}

clamp를 이용해 값의 제한을 뒀고,

현재 pixels은 가우시안 블러가 적용되어 있고, 복사본인 pixelsBackup은 원본이니까,

pixels에 weight를 곱한 후 pixelsBackup을 더해주면

박스 블러 vs 가우시안 블러 vc 블룸

박스 블러	가우시안 블러	블룸

풀이

가장 큰 둘레를 가지는 이진트리의 길이를 반환하면 된다

bfs로 하려고 햇으나 코드가 너무 복잡해져서 dfs로 해결하기로 함

재귀

재귀의 핵심은 DP와 같음

• 각 재귀의 반환값은 이미 정답임
• 그럼 어떤 값을 반환해야 원하는 값으로 이용할 수 있을지를 생각

먼저 코드를 보자

class Solution {
public:

    int dfs(int &ans, TreeNode* root) {
        if (!root) return 0;

        int l = dfs(ans, root->left);
        int r = dfs(ans, root->right);

        ans = max(ans, l + r);

        return max(l, r) + 1;
    }

    int diameterOfBinaryTree(TreeNode* root) {
        int ans = 0;
        dfs(ans, root);
        return ans;
    }
};

1. 각 재귀의 반환값은 이미 정답임

int l = dfs(ans, root->left);
int r = dfs(ans, root->right);

이 부분을 생각하기전에, 먼저 이진트리고, left, right가 있음

그러니까, left를 계속 타고가면 어떠한 트리이든, 해당 노드를 루트로 가지는 이진트리의 가장 깊은 왼쪽 노드가 반환되는거임

반대는 오른쪽이고 ㅇㅇ

dfs(root->left);
dfs(root->right);

를 하면 그냥 최고 깊이의 노드가 나타나는거 ㅇㅇ

2. 어떤 값을 반환해야 원하는 값으로 이용할 수 있을지를 생각

지금 원하는 값은 최고 길이가 되는 이진트리의 길이를 구하는거임

즉, 특정노드 n을 기준으로 최고길이가 되는 경우를 따지면 되는데, 이말은 루트노드를 거쳐가며 만들 수 있는 이진트리중 길이가 가장 길이가 긴 이진트리가 정답인 이진트리라는거임

즉, 루트노드에서부터 가장 깊은 left, right노드의 깊이를 합하면 최고 길이를 가지는 이진트리의 길이가 됨

그럼 반환값으로 무엇을 반환해야할까?

현재 노드의 깊이를 반환하면 됨

dfs(root->left);
dfs(root->right);

여기서 dfs메서드의 반환 타입은 노드의 깊이니까 int타입이 되어야함

int l = dfs(root->left);
int r = dfs(root->right);

그리고 dfs에서 반환을 해줘야하니,

int l = dfs(root->left);
int r = dfs(root->right);

return std::max(l,r) + 1;

자신 노드의 자식 노드 중 더 깊은 위치에 있는 노드의 깊이를 반환하면 됨

하지만 이걸론 안됨

3. 정답

가장 깊이가 깊은 노드의 깊이를 구하는 문제가 아님

가장 긴 길이를 가지는 이진트리의 길이를 구하는 문제임

즉, 현재 l과 r의 합이 자신 노드에서 가장 길이가 긴 노드가 됨

따라서

int dfs(int &ans, TreeNode* root) 
{
    if (!root) return 0;

    int l = dfs(ans, root->left);
    int r = dfs(ans, root->right);

    ans = max(ans, l + r);

    return max(l, r) + 1;
}

이런 코드가 완성됨

ans는 변수로 빼도 상관없음

class Solution {
public:
    int ans = 0;

    int dfs(TreeNode* root) {
        if (!root) return 0;

        int l = dfs(root->left);
        int r = dfs(root->right);

        ans = max(ans, l + r);

        return max(l, r) + 1;
    }

    int diameterOfBinaryTree(TreeNode* root) 
    {
        dfs(root);
        return ans;
    }
};

정리

1. 재귀에서 반환되는 값이 뭐가 되어야 문제에서 말하는 값을 구할 수 있을지 정의
   • 서브트리의 깊이
2. 반환된 값을 어떻게 처리해야 문제에서 말하는 값을 구할 수 있을지 정의
   • 자식 서브트리의 합 중 가장 큰 값

시야각은 가로, 세로 중 어디를 기준점으로 잡느냐에 따라 좀 달라짐

책에서는 수직 시야각(vertical fov)를 사용한다고 함

현재 우리는 Camere_center에서 focal_length가 1임

즉, (0, 0, 0)에서 z축으로 -1만큼 떨어진 뷰포트를 보는중임

이때 우리가 바라보는 시야의 중앙은 0,0,-1이고, 이 좌표로부터 수직 시야각을 이용하여 상하로 $\theta / 2$ 만큼씩 보고있는 시야각인거임

대략 이렇게 -z축방향으로 카메라가 원점에서 $\theta$의 시야각으로 화면의 수직 방향을 보고 있는거임

이때 $h$는 $\theta$의 대변임

따라서 삼각함수 공식에 따라

$h = \tan(\frac{\theta}{2})$

이 됨

우리는 카메라의 fov를 설정하고, fov를 radian으로 바꾸어 $\theta$를 만든 후, 이를 이용해서 수직 시야범위를 계산할거임

#ifndef CAMERA_H
#define CAMERA_H

#include "Color.h"
#include "hittable.h"
#include "Material.h"

class Camera {
public:
    //...

    double fov          = 90; //시야각

    //...

private:
    //...

    void initialize() {
        //...

        // Camera
        //카메라부터 뷰표트까지의 거리
        double focal_length = 1.0;

        double theta = degrees_to_radians(fov);
        double h = std::tan(fov / 2);
        double viewport_height = 2 * h * focal_length;

        //...
    }

    //...
};

#endif

focal_length를 곱하는 이유

비율임 h는 focal_length에 따라 비율이 변함 예를들어 focal_length가 1일때, h가 2였다면 focal_length가 4일때는 h가 8이 되어야 비율이 맞음

하지만 이걸로는 부족함

실제 카메라는 원점이 0,0,0도 아님 원점은 움직일 수 있고, 이로인해 바라보는 대상을 보는 각도도 바뀜

이를 계산해줘야함

정규 직교 기저

기저 벡터는 n차원 공간에서 사용하는 일종의 좌표 축임

예를들어 2차원 공간은 0,1, 1,0인 2개의 벡터로 표현할 수 있지? 이 2개의 벡터가 기저벡터임

그럼 3차원 공간은 뭐겠어? 0,0,1, 0,1,0, 1,0,0이 기저벡터지

즉, 기저벡터는 n차원 공간을 표현할 수 있는 최소개수의 벡터 집합임

정규 직교 기저

n차원 공간에서 모든 벡터의 크기가 정규화 되었으면서, 서로 수직기저 벡터들의 집합

이 기저벡터를 카메라의 원점을 기준으로 계산하여 카메라의 어느 방향이 오른쪽, 위쪽, 앞쪽 인지 기준점으로 삼을거임

기저벡터가 필요한 이유는 뭔데?

카메라의 방향을 지정함으로써 어디로 움직여야 어느 방향인지를 알 수 있게 하기 위함임

우리가 머리를 살짝 오른쪽으로 회전시켜보자 코를 기준으로 약 90도 오른쪽으로 회전시켰다고 가정하면...

우리가 보는 방향의 위쪽은 원래 머리 방향의 오른쪽임 우리가 보는 방향의 왼쪽은 원래 머리 방향의 위쪽임 우리가 보는 방향의 앞쪽은 원래 머리 방향의 앞쪽임

이렇게 방향에 대한 좌표가 달라지게 됨

이를 해결하기위해 원점에서부터의 기저벡터를 설정하여 해당 기저벡터를 중심으로 각도를 조절할거임

필요한건 다음과 같음

look from - 카메라의 위치 좌표, look at - 카메라가 보는 좌표, u,v,w - 정규 직교 기저,

u: 우측, v: 위쪽, w: 카메라에서 사용자 방향(시야에서 정면의 반대 방향), 오른손 좌표계 기준이라, z축이 -에 있어야 보임, 따라서 사용자는 보는 방향 반대에 위치

추가로 필요한게 잇음 카메라의 위쪽방향에 해당되는 좌표임

vup - 카메라 기준의 위쪽 좌표

그래서 코드는 다음처럼 바뀜

class Camera {
public:
    //...
    double vfov          = 90; //수직 시야각
    Point3 look_from     = Point3(0,0,0); //카메라 원점 좌표
    Point3 look_at       = Point3(0,0,-1); //카메라 보는 곳 좌표
    Vector3 vup          = Vector3(0,1,0); //카메라 기준 위쪽 좌표

private:
    //...
    Vector3 u, v, w; //정규 직교 기저

    void initialize() {
        //...

        camera_center = look_from;

        // Camera
        //카메라부터 뷰표트까지의 거리
        double focal_length = (look_from - look_at).length();

        double theta = degrees_to_radians(vfov);
        double h = std::tan(vfov / 2);
        double viewport_height = 2 * h * focal_length;

        //해상도 비율을 사용하지 않고, 이미지를 사용하는 이유
        //해상도 이미지는 이상적인 비율이고, 실제 이미지의 비율은 해상도 비율과 다를 수 있음
        //width = height / 9 * 16 = height * 16 / 9
        double viewport_width = viewport_height * (static_cast<double>(image_width) / image_height);

        w = unit_vector(look_from - look_at);
        u = unit_vector(cross(w, vup));
        v = cross(w, u);

        //뷰표트의 왼->오, 상->하로 이동하는 최대 좌표 구하기
        Vector3 viewport_u = viewport_width * u;
        Vector3 viewport_v = -viewport_height * -v;

        //뷰포트의 각 픽셀간의 거리 구하기(델타 벡터)
        pixel_delta_u = viewport_u / image_width;
        pixel_delta_v = viewport_v / image_height;

        //최 좌상단 픽셀의 좌표구하기
        //camera_center - Vector3(0, 0, focal_length) : 뷰포트 바로 위에서 focal_length만큼 z방향 반대로 떨어지기
        // - viewport_u/2 - viewport_v/2 : 화면의 가로세로 절반씩 좌, 상으로 이동하기(뺄셈)
        Vector3 viewport_upper_left = camera_center - (focal_length * w) - viewport_u / 2 - viewport_v / 2;
        //위의 공식은 뷰포트의 최좌상단 좌표가 됨. 하지만 픽셀 시작 좌표는 아님
        //따라서 시작지점은 뷰포트 픽셀거리의 절반만큼 띄워진 거리에서부터 시작해야 정확히 너비 * 높이 개의 영역으로 균등하게 나눠짐
        pixel00_loc = viewport_upper_left + 0.5 * (pixel_delta_u + pixel_delta_v);
    }

    //...
};

#endif
//-------------------------------------------//
int main()
{
    HittableList world;

    auto material_ground = make_shared<Lambertian>(Color(0.8, 0.8, 0.0));
    auto material_center = make_shared<Lambertian>(Color(0.1, 0.2, 0.5));
    auto material_hollow_glass = make_shared<Dielectric>(1.5);
    auto material_hollow_in = make_shared<Dielectric>(1.00/1.5);
    auto material_diamond = make_shared<Dielectric>(2.417);
    auto material_right  = make_shared<Metal>(Color(0.8, 0.6, 0.2), 0.5);

    world.add(make_shared<Sphere>(Point3( 0.0, -100.5, -1.0), 100.0, material_ground));
    world.add(make_shared<Sphere>(Point3( 0.0,    0.0, -1.2),   0.5, material_center));
    world.add(make_shared<Sphere>(Point3(-1.0,    0.0, -1.0),   0.5, material_hollow_glass));
    world.add(make_shared<Sphere>(Point3(-1.0, 0.0, -1.0), 0.45, material_hollow_in));
    world.add(make_shared<Sphere>(Point3(-0.1, 0.0, -0.3), 0.1, material_diamond));

    world.add(make_shared<Sphere>(Point3( 1.0,    0.0, -1.0),   0.5, material_right));

    Camera cam;
    cam.aspect_ratio = 16.0 / 9.0;
    cam.image_width = 1200;
    cam.samples_per_pixel = 300;
    cam.max_depth = 50;

    cam.vfov = 20;
    cam.look_from = Point3(-2, 2, 1);
    cam.look_at = Point3(0, 0, -1);
    cam.vup = Vector3(0, 1, 0);

    cam.render(world);
}

그렇게 렌더링하면 아래 사진처럼 나옴

유전체는 더 큰 범주의 절연체임

절연체는 아예 전기가 흐르지 못하고, 전극이 와도 분극되지 못하고 그냥 아예 전기가 막힘

유전체는 전기의 흐름을 방해하는 의미에서 절연체임 유전체는 전극이 흐르면 이를 +, -로 분극을 함

따라서 좋은 유전체는 좋은 절연체이지만, 역은 성립하지 않을 수 있음

스넬 법칙

$\eta , \eta'$ = 매질에 따른 굴절율, $\theta , \theta'$ = 법선으로부터의 입사각, 굴절각

스넬 법칙: $\eta * \sin \theta = \eta' * \sin \theta'$

빛은 매질이 바뀔때, 빛이 닿은 경계면의 평행한 방향의 성분만 유지가 된다는걸 의미함.

각 물체는 굴절률이 다름 빛이 물체에 닿았을때 굴절이 되는데, 빛의 방향의 성분중에서 빛이 닿은 경계면과 평행한 성분만 유지가 되고, 나머지는 굴절율에 의해 굴절이 되는걸을 의미함.

노란 벡터 = 빛 방향, 파란 벡터 = 경계면에서의 Normal 노란 점선 벡터 = 굴절된 후의 빛 벡터 회색 점선 벡터 = 경계면과 평행한 방향(방향만 유지된거임)

이렇게 경계면과 평행한 방향은 유지하면서, 다른 각도로 굴절되는 것이 스넬 법칙임

중요!!! 입사 벡터, 법선 벡터는 모두 정규화된 벡터임!!

스넬 법칙 전개

$\eta * \sin \theta = \eta' * \sin \theta'$

이 식을 살펴보자

우리에게 필요한 것은 $\sin\theta'$임 왜냐고? 표면 바깥에서 굴절되어 표면 내부로 들어올 것이기 때문에ㅇㅇ

따라서 료이키 텐카이를 통해 $\sin\theta'$만 남기고 이항 정리를 함

$\sin\theta' = \frac{\eta}{\eta'}*\sin\theta$

가 됨

1. 벡터 합으로 R' 정의

$R'$ = 경계에 닿은 빛이 굴절된 벡터 $\theta'$ = 굴절각 $R'_\bot$ = 법선 $n'$에서 수직인 벡터 $R'_\parallel$ = 법선 $n'$에서 평행인 벡터

위의 사진에서

$R' = R'_\bot + R'_\parallel$

이라는 것을 확인할 수 있음

2. $R'_\bot = \frac{\eta}{\eta'}(R - (R \cdot N) * N)$ 정리

핵심은 입사각 $R$을 이용하는 거임

현재 우리는 $R, \theta, n$을 알고있음

$R = R_\bot + R_\parallel$

이라는 걸 알 수 있음 위에처럼 ㅇㅇ

• 여기서 $R_\bot$은 $R'_\bot$과 방향이 동일하고 두 수직성분의 비율은 두 굴절율의 비율과 같음
  • 결국 경계면과 평행한 두 수직성분은 굴절율의 비율에 따라 크기가 변화하게 됨

여기서 우리는 $R_\parallel$을 구할 수 있음

Metal재질 반사각 전개 이 링크의 내용을 이용해 $R_\parallel$을 찾은 후 값을 찾아주면됨 아래에서 다시 설명함

$\cos\theta$ = 직각삼각형의 밑변 / 빗변 빗변 = 정규화된 벡터 = 1 $\cos \theta$ = 밑변 = $R_\parallel$

입사 벡터 $\cdot$(내적) 법선 = 입사벡터 * 법선벡터 $\cos \theta$ 입사벡터 = 정규화된 벡터 = 1 법선벡터 = 정규화된 벡터 = 1 입사 벡터 $\cdot$ 법선 = $\cos \theta$

입사 벡터($R$) $\cdot$ 법선($N$) = $\cos \theta$ = $R_\parallel$

하지만 내적은 스칼라값이므로, 정규화된 벡터인 법선과 곱해서 정확한 밑변 벡터를 찾음

-> $R_\parallel = (R \cdot N) * N$

$R = R_\bot + R_\parallel$ = $R_\bot = R - R_\parallel$

따라서 식을 전개해보면

$R_\bot = R - (R \cdot N) * N$

이 되는걸 알 수 있음

여기서 $R_\bot$은 $R'_\bot$과 방향이 동일하고 두 수직성분의 비율은 두 굴절율의 비율과 같음

위에서 살펴본 위 특성에 의해

$R'_\bot = \frac{\eta}{\eta'}(R - (R \cdot N) * N)$

가 되는 것을 알 수 있음

3. $R_\parallel = -\sqrt{1 - |R'_\bot|^2*n}$ 정리

2번은 경계와 평행한 성분인 수직성분을 구함

이번에는 경계와 수직인 성분인 평행성분을 구할 차례임

안타깝게도 수직인 성분에 대해서는 두 굴절률의 비율에 따라 값이 변화하지 않음

따라서 피타고라스 공식을 이용해서 구해주면 됨

피타고라스 정리

• 빗변$^2$ = 밑변$^2$ + 높이$^2$

이때 각 변은 스칼라 값임 그냥 크기라는 거임

따라서 값을 구해주면, 나중에 벡터를 곱해서 방향을 만들어줘야함

빗변 = $R'$ =정규화된 벡터 = 1 밑변 = |$R'_\bot$| = |$R' - (R' \cdot N) * N$| 높이 = |$R'_\parallel$|

이걸 정리해보면

$1^2 = (R'_\bot)^2 + (R'_\parallel)^2$

이 됨

이항정리를 하면

$(R'_\parallel)^2 = 1^2 - ((R'_\bot) * N)^2$

$R'_\parallel = \sqrt{1 - ((R'_\bot) * N)^2}$

위처럼 정리가 됨

그리고 이미 구한 $R'_\bot$을 이용하면

$R'_\parallel = \sqrt{1 - ((R' - (R' \cdot N) * N) * N)^2}$

이라는 식을 구할 수 있음

4. $R' = R'_\bot + R'_\parallel$

다시 이 사진을 보면

$R' = R'_\bot + R'_\parallel$ 이라는 것을 알 수 있음

굴절 코드 구현

//Vector3.h...

inline Vector3 refract(const Vector3& uv, const Vector3& n, double etai_over_etat)
{
    auto cos_theta = std::fmin(dot(-uv, n), 1.0);
    Vector3 r_out_perp =  etai_over_etat * (uv + cos_theta*n);
    Vector3 r_out_parallel = -std::sqrt(std::fabs(1.0 - r_out_perp.length_squared())) * n;
    return r_out_perp + r_out_parallel;
}

먼저 $\cos \theta$를 구하고, 그걸 이용해서 수직성분, 평행성분을 구해준 후 더하면 굴절된 벡터인 $R'$를 구하는거임!

Dielectric머티리얼 구현

class Dielectric : public Material
{
public:
    Dielectric(double refraction_index) : refraction_index(refraction_index) {}

    bool scatter(
        const Ray& r_in,
        const HitRecord& rec,
        Color& attenuation,
        Ray& scattered) const override
    {
        attenuation = Color(1,1,1);
        double ratio_of_refraction_index = rec.front_face ? 1.0 / refraction_index : refraction_index;

        Vector3 unit_direction = unit_vector(r_in.direction());
        Vector3 refracted = refract(unit_direction, rec.normal, ri);

        scattered = Ray(rec.p, refracted);
        return true;
    }

private:
    //굴절률
    double refraction_index;
};

여기서 핵심은

double ratio_of_refraction_index = rec.front_face ? 1.0 / refraction_index : refraction_index;

임!

공기의 굴절률은 1에 수렴함 공기에서 물체의 내부로 들어가는건 front_face인거임

따라서 굴절률 비율은

$1(공기) / 굴절률 = \frac{\eta}{\eta'}$

인거임!

그리고 내부에서 외부로 나올때는 front_face가 아니므로

$굴절률 / 1(공기) = \frac{\eta'}{\eta} = \eta'$

가 되는거임

이제 사용해보자

한번 다이아몬드의 굴절률을 사용해보자

auto material_left   = make_shared<Dielectric>(2.417);

이렇게 수정하고 렌더링을 해보면...

전반사 (Total Internal Reflection)

밀도가 높은 물질에서 밀도가 낮은 물질로 빛이 나가면 어떻게 될까 무조건 굴절이 될까?

절대 그렇지 못함

위의 세션인 스넬 법칙에서 살펴봤듯

$\sin \theta * \eta = \sin \theta' * \eta'$ $\sin\theta' = \frac{\eta}{\eta'} * \sin\theta$

처럼 식이 정리 가능하다.

밀도 높은 물질의 굴절률 = $\eta$ = 2.4(다이아몬드) 밀도 낮은 물질의 굴절률 = $\eta'$ = 1(공기)

라고 해보자

$\sin\theta' = {2.4} * \sin\theta$

이 됨

근데 이러면 문제가 있음

$\sin \theta$가 대략 0.45정도만 되어도 $\sin\theta'$가 1을 넘어가버림 $\sin \theta$는 최대값이 1임

따라서 물질 내부에서 굴절이 안되는 각도의 빛은 반사가 됨

즉, $\sin \theta$가 1이 넘어가는 경우, 임계각을 넘어가는 경우는 굴절이 아닌 반사를 해줘야함

$\sin\theta$는 피타고라스 정리를 이용해서 구할 수 있음

$\sin^2\theta + \cos^2\theta = 1$ $\sin^2\theta = 1 - \cos^2\theta$ $\sin\theta = \sqrt{1 - \cos^2\theta}$

임

위의 스넬법칙에서 $\cos\theta = R\cdot N$이라는 것도 알아냄

따라서 Dielectric머티리얼의 scatter메서드를 조금 수정해주면 됨

class Dielectric : public Material
{
public:
    Dielectric(double refraction_index) : refraction_index(refraction_index) {}

    bool scatter(
        const Ray& r_in,
        const HitRecord& rec,
        Color& attenuation,
        Ray& scattered) const override
    {
        attenuation = Color(1,1,1);
        double ratio_of_refraction_index = rec.front_face ? 1.0 / refraction_index : refraction_index;

        Vector3 unit_direction = unit_vector(r_in.direction());

        //add
        double cos_theta = std::fmin(dot(-unit_direction, rec.normal), 1.0); //코사인 세타
        double sin_theta = std::sqrt(1 - cos_theta * cos_theta);

        bool cant_refract = ratio_of_refraction_index * sin_theta > 1;
        Vector3 direction;

        if (cant_refract)
        {
            direction = reflect(unit_direction, rec.normal);
        }
        else
        {
            direction = refract(unit_direction, rec.normal, ratio_of_refraction_index);
        }

        scattered = Ray(rec.p, direction);
        return true;
    }

private:
    //굴절률
    double refraction_index;
};

cos_theta를 이용해서 sin_thete를 구하고 굴절 가능한지 판별을 한 후 reflect/refract를 수행함

대충 물속(1.33)의 공기(1)이라고 가정하고

auto material_left   = make_shared<Dielectric>(1.00/1.33);

과 같은 코드를 짬ㅇㅇ 그럼 다음과 같은 이미지 차이가 생김

왼쪽은 전반사 코드 추가 전/ 오른족은 전반사 코드 추가 후

전반사 추가 전	전반사 추가 후

이렇게 반사가 다르게 되는걸 볼 수 있음

슐릭 근사(schlick approximation), 프레넬 효과

프레넬 효과는 유니티 쉐이더그래프를 하며 여러번 다뤄서 익숙함

프레넬은 빛의 입사각에 따라 반사되는 빛의 양이 달라지는 것을 의미함 그리고 모든 물체는 프레넬을 가짐

위 사진을 보면 프레넬을 가진 주전자는 입사각이 수직에 가까울때는 비교적 어둡고, 더 완만할때는 빛의 반사가 많은 것을 볼 수 있음(외곽부분)

우리가 만든 구체는 저렇게 프레넬 효과가 적용되지 않은 상태여서, 약간 이상하게 보임

프레넬 방정식 VS 슐릭 근사

프레넬을 구할때, 프레넬 방정식과 슐릭 근사 중 하나를 골라서 사용하면 된다

프레넬 방정식

$F_{equation} = (\frac{\eta * \cos\theta - \eta' * cos\theta'}{\eta * \cos\theta + \eta' * cos\theta'})^2$

$\eta$ : 입사 매질 굴절률 $\eta'$ : 투과 매질 굴절률 $\theta$ : 입사각 $\theta'$ : 굴절각

슐릭 근사

$F_{schlick} = R0 + (1- R0)(1 - \cos\theta)^5$

$R0$ : 빛이 표면에 수직으로 입사했을때 반사율 $cos\theta$ : 입사각(0과 가까울수록 수직, 1과 가까울수록 평행)

$R0 = (\frac{1 - \eta}{1 + \eta})^2$

$\eta$ : 굴절률

코드 구현의 난이도로 보면 슐릭근사가 더 빠르고 쉽게 계산됨

class Dielectric : public Material
{
    //...

    bool scatter(
        const Ray& r_in,
        const HitRecord& rec,
        Color& attenuation,
        Ray& scattered) const override
    {
        //...

        if (cant_refract || schlick_approximate(cos_theta, ratio_of_refraction_index) > random_double())
        {
            direction = reflect(unit_direction, rec.normal);
        }
        //...
    }

private:
    //...

    static double schlick_approximate(double cos, double ratio_of_refraction_index)
    {
        double r0 = (1 - ratio_of_refraction_index) / (1 + ratio_of_refraction_index);
        r0 = r0 * r0;

        return r0 + (1 - r0) * std::pow((1 - cos), 5);
    }
};

여기서 random_double과 비교하는 이유가 있음

특정 입사각에서 반사되어야 하는 빛의 양이 0.5라고 해보자

1. random_double()을 통해 0.4가 나왔다면
   • 반사되어야 할때 무조건 반사
   • 굴절되어야 할때 조건을 만족하지 못하므로 굴절
2. random_double()을 통해 0.6이 나왔다면
   • 반사되어야 할때 무조건 반사
   • 굴절되어야 할때 조건을 만족하므로 반사
     이렇게 조건에 따라 확률적으로 빛을 반사시켜 프레넬 효과를 만드는거임

이걸 이용해서 기존의 왼쪽 구체를 hollow유리 구체로 만들고, 그 구체 앞에 작은 다이아몬드 구체를 만들어보도록 하겠음

유리의 굴절률은 1.5정도임

#include "Camera.h"
#include "Color.h"
#include "HittableList.h"
#include "hittable.h"
#include "RTWeekend.h"
#include "Sphere.h"

using namespace std;

int main()
{
    HittableList world;

    auto material_ground = make_shared<Lambertian>(Color(0.8, 0.8, 0.0));
    auto material_center = make_shared<Lambertian>(Color(0.1, 0.2, 0.5));

    //hollow glass
    auto material_left = make_shared<Dielectric>(1.5);
    auto material_bubble = make_shared<Dielectric>(1.00/1.5);
    //diamond sphere
    auto material_left_front = make_shared<Dielectric>(2.417);

    auto material_right  = make_shared<Metal>(Color(0.8, 0.6, 0.2), 0.5);

    world.add(make_shared<Sphere>(Point3( 0.0, -100.5, -1.0), 100.0, material_ground));
    world.add(make_shared<Sphere>(Point3( 0.0,    0.0, -1.2),   0.5, material_center));

    //hollow glass
    world.add(make_shared<Sphere>(Point3(-1.0,    0.0, -1.0),   0.5, material_left));
    world.add(make_shared<Sphere>(Point3(-1.0, 0.0, -1.0), 0.45, material_bubble));
    //diamond sphere
    world.add(make_shared<Sphere>(Point3(-1.0, 0.0, -0.3), 0.1, material_left_front));

    world.add(make_shared<Sphere>(Point3( 1.0,    0.0, -1.0),   0.5, material_right));

    Camera cam;
    cam.aspect_ratio = 16.0 / 9.0;
    cam.image_width = 1200;
    cam.samples_per_pixel = 300;
    cam.max_depth = 50;

    cam.render(world);
}

이렇게 수정함

그러고 렌더링 해보면...

풀이

또또또 문제 설명 아주그냥 뭐같은 문제임

그냥 핵심은 이진탐색하라는거임

you should minimize the number of calls to the API

라고 함

• 가장 최소의 bad version을 1~n사이의 값 중 찾아야함
• bad version은 isBadVersion메서드의 호출을 통해 해당 숫자가 bad version인지 아닌지 알 수 있음

class Solution {
public:

    int firstBadVersion(int n) {

        long l = 1;
        long mid = 0;

        while(l <= n)
        {
            mid = (l + n) / 2;

            if(isBadVersion(mid))
            {
                n = mid - 1;
            }
            else
            {
                l = mid + 1;
            }
        }

        return l;

    }
};

중요한건 l을 리턴한다는거임

왜? l을 리턴함? mid리턴해야하는거 아님??

ㄴㄴ mid는 단순히 해당 수가 bad version인지 아닌지 판가름 하는 용도로 이 풀이에서는 사용중임

n은 version중 bad version이 발견되면, 바로 bad version의 상한선이 됨

l은 version중 bad version에 관계없이 모든 수의 하한선이 됨

따라서 상한선을 계속 낮추면서 하한선을 올리면서 하한선이 상한선을 추월하는 상황이 바로 bad version의 최하값이 되는거임

세상의 다양한 재질은 빛의 산란(Scattering)과 감쇠(Attenuate)로 재질이 표현됨

챕터 5에서 살펴본 matte재질도 빛의 산란과 감쇄로 구현됨

빛의 산란	빛의 감쇠

class Material
{
public:
    virtual ~Material() = default;

    //재질 별 빛 산란 메서드
    virtual bool scatter(
        const Ray& r_in, //Ray(빛) 입사광
        const HitRecord& rec, //충돌지점 정보 (법선, point)
        Color& attenuation, //빛 감쇠(색 변화)
        Ray& scattered //빛이 산란된 후의 광선
    ) const
    {
        return false;
    }
};

이런 메서드를 만들어주자

근데 문제가 있음 지금 선언된 HitRecord 클래스는 Hittable.h에 들어있음

잘생각해보자

1. Material은 충돌지점에서의 빛 계산을 위해 HitRecord를 참조하고 있어야함
2. HitRecord는 충돌지점의 처리를 위해 Material을 참조하고 있어야함

즉, Materual -> HitRecord HitRecord -> Material

이라는 순환참조관계가 만들어짐

이걸 해결하는건 쉬움

그냥 전방선언하면됨

class Material;

class HitRecord
{
public:
    Point3 p;
    Vector3 normal;
    shared_ptr<Material> mat;
    double t;
    bool front_face;

    void set_face_normal(const Ray& r, const Vector3& outward_normal)
    {
        // 1. 광선(Ray)과 밖을 향하는 법선(outward_normal)의 내적이 음수(< 0.0)인지 확인합니다.
        // 내적이 음수면: 광선이 밖에서 안으로 들어오는 중 (앞면, front_face = true)
        // 내적이 양수면: 광선이 안에서 밖으로 나가는 중 (뒷면, front_face = false)
        front_face = dot(r.direction(), outward_normal) < 0.0;

        // 2. 항상 법선이 광선과 마주 보게(내적이 음수가 되게) 방향을 통일해 줍니다.
        // 앞면을 때렸다면 밖을 향하는 법선을 그대로 사용하고,
        // 뒷면(물체 내부)을 때렸다면 법선을 뒤집어서(-outward_normal) 사용합니다.
        normal = front_face ? outward_normal : -outward_normal;
    }
};

그냥 이렇게 바꾸면 끝~

그리고 Sphere.h에서 구체가 정의될때 Material도 정의되게 한 후, HitRecord의 Material을 해당 MAterial로 초기화해주면 됨

//...

class Sphere : public Hittable
{
private:
    //...
    shared_ptr<Material> mat; //추가
public:
    Sphere();
    Sphere(const Point3& center, double r) : center(center), radius(r) {}; //수정

    bool hit(const Ray& r, MinMaxInterval ray_t, HitRecord& hitRec) const override
    {
        //...

        hitRec.t = root;
        hitRec.p = r.at(hitRec.t);
        Vector3 outward_normal = (hitRec.p - center) / radius;
        hitRec.set_face_normal(r, outward_normal);
        hitRec.mat = mat; //추가

        return true;
    }
};

#endif

람베르트 빛 반사 수정

class Lambertian : public Material
{
public:
    Lambertian(const Color& albedo) : albedo(albedo) {}

    bool scatter(
        const Ray& r_in,
        const HitRecord& rec,
        Color& attenuation,
        Ray& scattered) const override
    {
        auto scatter_direction = rec.normal + random_unit_vector();
        scattered = Ray(rec.p, scatter_direction);
        attenuation = albedo;
        return true;
    }

private:
    Color albedo;
};

이런 Material을 상속받는 Lambertian머티리얼 클래스를 만들어주자

참고로 벡터의 Normal을 구해야할때, 0으로 나누는 division by zero를 유발할 수 있으므로,

random_unit_vector를 사용하는 곳에서 벡터가 0이 되는 경우를 찾아 미리 값을 수정해주어야함

이는 Vector3::near_zero()라는 메서드를 만들어 해결~

//Vector3.h...
bool near_zero() const
{
    double s = 1e-8; //임의의 작은 값
    return (fabs(e[0]) < s) && (fabs(e[1]) < s) && (fabs(e[2]) < s);
}

그리고 위의 Labertian클래스의 Scattering메서드를 수정!

//Lambertian.h ...
 bool scatter(
    const Ray& r_in,
    const HitRecord& rec,
    Color& attenuation,
    Ray& scattered) const override
{

    auto scatter_direction = rec.normal + random_unit_vector();

    if (scatter_direction.near_zero())
    {
        scatter_direction = rec.normal;
    }

    scattered = Ray(rec.p, scatter_direction);
    attenuation = albedo;
    return true;
}

반사

모든 벡터는 normalized된 벡터임.

여기서 R을 구해야하는 문제 먼저 $\Theta$ 를 구해야됨

1. L과 N사이의 각 = $\Theta$ -> 내적
2. 90 - (L과 N사이의 각) = $\Theta$ -> 외적

1. 내적을 이용하는 법

이거임

1-1. 벡터의 합

벡터의 합을 이용해서 L에서 접점으로 향하는 벡터에 + 2x를 하면 R이 된다.

따라서 우리는 x를 구하면 됨

1-2. 삼각함수

L과 N의 각이 세타이므로, N과 R의 각도 세타임(반사때문에)

그리고 x를 y축으로 이동(투영)시키면 위의 그림 형태가 됨.

여기서 우리는 $cos\Theta$를 구할 수 있음

$cos\Theta$ = $\Theta$와 인접한 변{$x$} / 빗변{$R$}

근데 $R$은 normalized상태임

즉, $cos\Theta$ = $x$ 이 됨

$cos\Theta$ = 빗변에 대한 밑변의 비율 = 정규화된 상태에서는 밑변의 길이가 됨

$\Theta$를 끼고 있는 두 벡터는 L, N이고, 두 벡터는 이미 정규화된 상태임

두 벡터 $\vec{a}$와 $\vec{b}$의 $\vec{a} \cdot \vec{b}$는 두 벡터의 크기와 사이각$\Theta$의 코사인 값을 곱한 $\vec{a} \cdot \vec{b} = |\vec{a}||\vec{b}|\cos\Theta$

즉, 정규화된 두 벡터 * $\cos\Theta$ = 두 벡터의 내적임

위의 공식을 사용하면 $\vec{N} \cdot \vec{L} = |\vec{N}||\vec{L}|\cos\Theta$ 이라는 거임

여기서 $|\vec{N}||\vec{L}| = 1$이므로, $\vec{N} \cdot \vec{L} = \cos\Theta$ 임

즉, $\vec{N} \cdot \vec{L} = \cos\Theta = x$가 됨

1-3. $R$ 구하기

이 사진을 다시 살펴보자

$R = L + 2x$임

하지만 여기서 중요한 점이 있음

1. x를 구하는건 좋은데, x가 스칼라 값이라는 거임 스칼라 값은 그냥 이동거리임 꼭 법선벡터 방향이 아니고, x축일수도 있고, -x축일수도 있음 따라서, 정규화된 법선인 N과 곱하여 +y축으로 향하는 방향을 만들어줘야함 그러고 2를 곱해야 R이라는 방향벡터가 나오지 ㅇㅇ

   $R = L + 2x = L + 2 * (\vec{N} \cdot \vec{L}) * N$

이걸 코드로 쓰면 L + 2 * (dot(L,N) * N) 이 됨

2. $L$과 $N$의 시작 정점이 다름 위의 사진에서 L의 연장선을 보면, N과의 각도가 둔각이 됨 따라서 시작점을 맞추어 N과의 각을 예각으로 만들어줘야함 시작점을 맞추는 방법은 L을 뒤집으면 됨

이걸 코드로 쓰면 L + 2 * (dot(-L,N) * N) 이 됨

2. 외적 이용하는 법

각 $\Theta$를 L과 N사이의 각이 아닌 여각으로 두면 됨

이러면 x는 세타의 대변이고, R은 빗변이므로 $\sin \Theta = x / R$이 됨

이걸 이용해서 위처럼 구하면 됨

왜 내적을 사용? 외적은 왜 안씀?

외적을 사용하는 반사공식도 있긴하다는데 잘 모르겠음...

내적이 외적보다 계산이 간단함

이정도의 차이가 있음

최적화가 중요한 그래픽스에서는 내적이 더 연산횟수가 적으니 이걸 더 많이 쓰지 응응

metal재질

inline Vector3 reflect(const Vector3& v, const Vector3& n)
{
    return v + 2 * (dot(-v, n) * n);
}

먼저 이런 반사메서드를 vector3.h에 만들어줌

class Metal : public Material
{
public:
    Metal(const Color& albedo) : albedo(albedo) {}

    bool scatter(
        const Ray& r_in,
        const HitRecord& rec,
        Color& attenuation,
        Ray& scattered) const override
    {

        Vector3 reflectedVector = reflect(r_in.direction(), rec.normal);
        scattered = Ray(rec.p, reflectedVector);
        attenuation = albedo;

        return true;
    }

private:
    Color albedo;
};

이렇게 metal을 만들어줌

lambertian과의 차이점은

• Lambertian -> random vector을 이용
• Metal -> reflect를 이용

이제 만들어진 Material을 사용해야하니, Camera.h의 ray_color메서드를 수정!

Color ray_color(const Ray& r, int depth, const Hittable& world) const
{
    //...
    if (world.hit(r, MinMaxInterval(0.001, infinity), rec))
    {
        Ray scattered;
        Color attenuation;

        if (rec.mat->scatter(r, rec, attenuation, scattered))
            return attenuation * ray_color(scattered, depth-1, world);
        return Color(0,0,0);
    }
    //...
}

그리고 추가한 Sphere에도 생성자에 추가

Sphere(const Point3& center, double r, shared_ptr<Material> mat) : center(center), radius(r), mat(mat) {};

main을 손봐주자

int main()
{
    HittableList world;

    auto material_ground = make_shared<Lambertian>(Color(0.8, 0.8, 0.0));
    auto material_center = make_shared<Lambertian>(Color(0.1, 0.2, 0.5));
    auto material_left   = make_shared<Metal>(Color(0.8, 0.8, 0.8));
    auto material_right  = make_shared<Metal>(Color(0.8, 0.6, 0.2));

    world.add(make_shared<Sphere>(Point3( 0.0, -100.5, -1.0), 100.0, material_ground));
    world.add(make_shared<Sphere>(Point3( 0.0,    0.0, -1.2),   0.5, material_center));
    world.add(make_shared<Sphere>(Point3(-1.0,    0.0, -1.0),   0.5, material_left));
    world.add(make_shared<Sphere>(Point3( 1.0,    0.0, -1.0),   0.5, material_right));

    Camera cam;
    cam.aspect_ratio = 16.0 / 9.0;
    cam.image_width = 400;
    cam.samples_per_pixel = 100;
    cam.max_depth = 50;

    cam.render(world);
}

이렇게 sphere를 만드는데, 머티리얼을 사용해서 초기화 해주면....

이런 두개의 메탈이 만들어짐!!

Fuzzy Reflection

Fuzzy는 흐린, 불명확한, 보풀의 이런 느낌의 형용사임

대충 이런 느낌의 빛반사를 만들거임

아이디어는 간단함

위의 Lambertian반사처럼 반사된 벡터에서 랜덤한 normalized된 벡터를 더한 방향으로의 Ray를 사용하면 됨

먼저 Material.h의 metal의 코드를 살짝 수정

fuzz값이 입력되면, fuzzy를 주고, 아니면 그냥 메탈릭

public:
    Metal(const Color& albedo, double fuzz) : albedo(albedo), fuzz(fuzz < 1 ? fuzz : 1) {}

bool scatter(
    const Ray& r_in,
    const HitRecord& rec,
    Color& attenuation,
    Ray& scattered) const override
{

    Vector3 reflectedVector = reflect(r_in.direction(), rec.normal);

    //fuzz에 따라 랜덤 하게 반사
    reflectedVector = unit_vector(reflectedVector) + random_unit_vector() * fuzz;

    scattered = Ray(rec.p, reflectedVector);
    attenuation = albedo;

    return dot(scattered.direction(), rec.normal) > 0;
}

private:
    double fuzz;

그리고 main의 코드의 material에도 fuzzy를 넣어주자

auto material_left   = make_shared<Metal>(Color(0.8, 0.8, 0.8), 0);
auto material_right  = make_shared<Metal>(Color(0.8, 0.6, 0.2), 0.5);

그럼... 아래처럼 사진이 나옴!

https://leetcode.com/problems/linked-list-cycle/description/

풀이

문제가 좀 개판임 문제 설명이 개같음

말을 드럽게 어렵게 해놨음

그냥 딱 이거임

1. pos는 매개변수로 주어지지 않음
2. tail노드에서 next가 있을때 이때 next가 가리키는 노드를 pos라고 임의로 말함
3. 그러니까, 그냥 tail노드에서 next가 nullptr이면 싸이클이 없는거고 next가 특정 노드면 싸이클이 존재하는거임

1차 풀이

그냥 set을 써서 $O(n\log n)$으로 풀음

class Solution {
public:
    bool hasCycle(ListNode *head) {

        set<ListNode*> set;

        ListNode* n = head;

        bool isFound = false;

        while(n)
        {
            if(set.contains(n))
            {
                isFound = true;
                break;
            }

            set.insert(n);
            n = n->next;
        }

        return isFound;
    }
};

2차 풀이

문제에서 추가 도전사항을 제시해줌

지금은 set을 사용해서 $O(n)$의 메모리 공간을 사용함 이걸 $O(1)$, 즉, 추가 메모리 없이 해결해보라는거임

이건 투포인터를 써야함 핵심은 아래 내용임

1. 어짜피 tail->next는 싸이클이 있거나, nullptr임

그러니까 포인터 2개를 둬서 하나는 1칸씩 움직이고, 하나는 2개씩 움직여서 싸이클이 만들어지면 true, 2개씩 움직인 노드가 nullptr이면 false를 리턴하면 됨

왜 2개씩 움직이는거임? 3개는 안됨?

2개씩 움직여야하는 이유는 nullptr을 편하게 찾기 위해서임

nullptr->next는 에러터짐 근데 이걸 3개, 4개씩 하면 예외처리를 위해 if문이 오지게 쓰임

편하게 하려고 ㅇㅇ

class Solution {
public:
    bool hasCycle(ListNode *head) {

        if(!head) return false;

        ListNode* n = head;
        ListNode* nn = head->next;

        while(nn && nn->next)
        {
            if(n == nn) return true;

            n = n->next;
            nn = nn->next->next;

            if(!nn) return false;
        }

        return false;
    }
};

끝!

풀이

먼저 십진수 변환은 안됨

문자열의 길이가 $10^4$인데, 즉, $2^{10^4}$라는 뜻이라 숫자 개큼 ㅇㅇ

그래서 차례대로 한자리씩 더하면서 계산하면 됨

먼저 Example 1에서 보이듯이 두 문자열 input의 크기가 다를 수 있으므로, 계산 편의성을 위해 빈 자리를 0으로 채워주도록 함

핵심은 carry라는 올림수임

두 이진수의 각 자리의 합과 carry를 더한 수에 따라 값에 차등을 두면 됨

항상 이진수 연산은 끝자리부터, 연산결과는 항상 마지막에 추가산결과는 항상 마지막에 추가

수행과정은 아래와 같음

a : 10111 b : 11011 이라고 해보자

1. carry = 0 1+1+carry = 2 answer = 0...1

2. carry = 1 1+1+carry = 3 answer = 01...1

3. carry = 1 1+0+carry = 2 answer = 010...1

4. carry = 1 0+1+carry = 2 answer = 0100...1

5. carry = 1 1+1+carry = 3 answer = 01001...1
   남은 carry = 1 따라서 answer의 마지막에 올림수에 해당되는 1을 추가해줌
   answer = 010011
   뒤집기 answer = 110010
   

하지만 이는 이진수를 역순으로 연산한 결과라 값이 뒤집혀 있음

그러므로 다시 뒤집어주면됨

class Solution {
public:
    string addBinary(string a, string b) {

        int bl = b.size() - 1;
        int al = a.size() - 1;

        //연산 편의를 위한 자리수 맞추기 작업
        while(a.size() < b.size()) a = '0' + a;
        while(b.size() < a.size()) b = '0' + b;

        string s = "";
        int carry = 0;

        //올림수를 이용해 각 자리별로 연산
        for(int i = b.size() - 1; i >= 0; i--)
        {
            int sum = carry + (a[i] - '0') + (b[i] - '0');

            if(sum == 0) 
            {
                s += "0";
                carry = 0;
            }
            else if(sum == 1)
            {
                s+= "1";
                carry = 0;
            } 
            else if(sum == 2)
            {
                s += "0";
                carry = 1;
            }
            else
            {
                s += "1";
                carry = 1;
            }
        }

        //올림수가 남았을 경우, 결과에 추가해주기
        if(carry > 0)
        {
            s += "1";
        }

        //연산결과 뒤집기
        reverse(s.begin(), s.end());

        return s;
    }
};

$O(n)$으로 해결!

풀이

또귀임 재귀 그냥 죽여버리고 싶음 근데 공부해야댐

그래픽스에서 재귀 오지게 씀 ㅠㅠ

class Solution {
public:

    int height(TreeNode* node) {

        if (node == nullptr) {
            return 0;
        }

        int left = height(node->left);

        if (left == -1) {
            return -1;
        }

        int right = height(node->right);

        if (right == -1) {
            return -1;
        }

        if (abs(left - right) > 1) {
            return -1;
        }

        return max(left, right) + 1;
    }

    bool isBalanced(TreeNode* root) {
        return height(root) != -1;
    }
};

위 경우를 먼저 살펴보자

root = 1 stack = [1] ->left ~ 4

root = 3L stack = [1, 2L, 3L] ->left = 4L

root = 4L stack = [1, 2L, 3L, 4L] //L = 부모 기준 왼쪽노드 ->left = nullptr, 0 ->right = nullptr, 0 return max(0,0) + 1

root = 3L stack = [1, 2L, 3L] ->left = 1 ->right = 4R

root = 4R stack = [1, 2L, 3L, 4R] ->left = nullptr, 0 ->right = nullptr, 0 return max(0,0) + 1

root = 3L stack = [1, 2L, 3L] ->left = 1 ->right = 1 return max(1,1) + 1

이 과정을 쭉 이어나가면 root가 1일때 왼쪽 노드의 깊이가 3이라는게 구해진다.

하지만 2R로 넘어가면, 1이 반환이 되고, root가 1일때 오른쪽 노드의 깊이가 1이 된다.

따라서 두 방향의 깊이의 차가 1보다 크므로 이는 불균형 이진트리가 된다.

이때 1번에서 살펴본 과정을 반복하면 root가 2일때 왼쪽의 깊이는 2, 오른쪽은 0이 되고 두 깊이의 차가 1보다 크므로, -1이 반환된다

!!!!!! 이때 -1이 반환되는 이유는 미리 값을 걸러내기 위함으로

if (left == -1) 
{
    return -1;
}

if (right == -1) 
{
    return -1;
}

이런 코드가 없으면 abs(-1 - 0) + 1 = 2가 되어 불균형 이진트리 임에도 불구하고 이상한 깊이가 반환되게 됨

그러므로 -1이라는 값은 중요!

사실 -1말고 -10000000해도 됨

풀이

간단한 BFS문제이다

class Solution {
public:
    const int moveX[4] {-1,1,0,0};
    const int moveY[4] {0,0,-1,1};

    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) {

        int maxX = image.size();
        int maxY = image[0].size();

        bool visited[51][51] = {false};
        std::queue<pair<int,int>> q;
        int startColor = image[sr][sc];

        q.push(make_pair(sr,sc));
        visited[sr][sc] = true;

        while(q.size() > 0)
        {
            auto srsc = q.front();
            q.pop();

            int x = srsc.first;
            int y = srsc.second;
            image[x][y] = color;

            for(int i = 0; i < 4; i++)
            {
                int mx = x + moveX[i];
                int my = y + moveY[i];

                if (mx < 0 || mx >= maxX || 
                my < 0 || my >= maxY || 
                visited[mx][my] == true || 
                image[mx][my] != startColor) continue;

                visited[mx][my] = true;
                q.push(make_pair(mx,my));
            }
        }

        return image;
    }
};

이렇게 코드를 작성했는데

뭔가... 공간복잡도가 맘에 안들음

그래서 최적화를 고민해봄

먼저 핵심은 2가지임

1. startColor가 제공되는 color와 같으면 startColor의 주변 타일은 볼 필요도 없이 바로 return가능
2. 따라서 visited는 startColor != color인 타일만 찾으면 되므로 필요가 없음

예를들어

| | | |-|-|-| |1|2|1| |0|1|0| |1|1|0|

이런 타일이 있을때,

주어진 좌표가 1,1에 color가 1이라고 해보자

이미 주어진 좌표는 color와 같은 색상인 1이다.

따라서 주어진 좌표 주변에 같은 색상을 가지는 좌표가 있다고 하더라도 주어진 좌표와 색상이 동일하므로, 바로 return을 때릴수 있는것임

개선된 코드

class Solution {
public:
    const int moveX[4] {-1,1,0,0};
    const int moveY[4] {0,0,-1,1};

    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) {

        if(image[sr][sc] == color) return image;

        int maxX = image.size();
        int maxY = image[0].size();

        std::queue<pair<int,int>> q;
        int startColor = image[sr][sc];

        q.push(make_pair(sr,sc));

        while(q.size() > 0)
        {
            auto srsc = q.front();
            q.pop();

            int x = srsc.first;
            int y = srsc.second;
            image[x][y] = color;

            for(int i = 0; i < 4; i++)
            {
                int mx = x + moveX[i];
                int my = y + moveY[i];

                if (mx < 0 || mx >= maxX || 
                my < 0 || my >= maxY || 
                image[mx][my] != startColor) continue;

                q.push(make_pair(mx,my));
            }
        }

        return image;
    }
};

이 됨

BFS말고 재귀로 해결

class Solution {
public:
    void fill(std::vector<std::vector<int>>& image, int sr, int sc, int color, int newColor) {
        if (sr < 0 || sr >= image.size() || sc < 0 || sc >= image[0].size() || 
            image[sr][sc] != color || image[sr][sc] == newColor) {
            return;
        }

        image[sr][sc] = newColor;

        fill(image, sr - 1, sc, color, newColor);
        fill(image, sr + 1, sc, color, newColor);
        fill(image, sr, sc - 1, color, newColor);
        fill(image, sr, sc + 1, color, newColor);
    }

    std::vector<std::vector<int>> floodFill(std::vector<std::vector<int>>& image, int sr, int sc, int color) {
        fill(image, sr, sc, image[sr][sc], color);
        return std::move(image);
    }
};

이렇게 재귀를 이용한 재귀로 해결할수도 있음

더빠르고, 공간복잡도 최상ㅇㅇ

풀이

간단한 이진트리를 뒤집는 문제임

주어지는 이진트리는 left, right로 구분되어 있음

핵심 풀이과정은 다음과 같음

1. 트리의 root를 기준으로 left, right를 교체
2. 레벨을 하나씩 높여가며 root를 새로 정의하고 1번을 수행
3. 위 과정을 root가 null일때까지 반복

그래서 코드는 다음과 같음

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) 
    {
        if(!root) return nullptr;

        auto l = root -> left ? root -> left : nullptr;
        auto r = root -> right ? root -> right : nullptr;

        root -> left = r;
        root -> right = l;

        invertTree(l);
        invertTree(r);

        return root;
    }
};

기본적으로 이진트리는 재귀를 통해 접근하는게 쉬운거같음

근데 재귀는 잘못 다루면 stack overflow가 터지므로 직접 root를 그래프로 보고, bfs나 dfs를 통해 푸는 방법도 알려줌

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) 
    {
        std::queue<TreeNode*> q;
        q.push(root);

        while(q.size() > 0)
        {
            TreeNode* root = q.front();
            q.pop();

            if(!root) continue;

            auto l = root -> left ? root -> left : nullptr;
            auto r = root -> right ? root -> right : nullptr;

            root -> left = r;
            root -> right = l;

            q.push(l);
            q.push(r);
        }

        return root;
    }
};

Muy facil! 베리 이지!

matte의 뜻을 알고있음?

matte 는 무광택이라는 뜻임

그니까 예를들어 의자의 메쉬, 천옷같은것들이 matte재질임

이러한 matte한 재질을 빛을 diffuse시킨다고 함

유광 재질은 빛의 입사각과 반사각이 일정함 하지만 무광 재질은 빛이 이상하게 흡수, 다른 방향, 엉뚱한 방향, 정방향등 랜덤하게 방향이 바뀜

주로 이렇게 빛이 랜덤하게 반사가 됨

물체가 어두울수록 빛이 더 흡수되어 잘 안보이게 되는거임

그리고 빛을 랜덤하게 반사하게만 하면, diffuse material처럼 보임ㅇㅇ

그러니 일단 무작위 Vector를 만드는 코드를 추가하자

//Vector3.h ...
//랜덤 벡터
static Vector3 random()
{
    return Vector3(random_double(), random_double(), random_double());
}

static Vector3 random(double min, double max)
{
    return Vector3(random_double(min, max), random_double(min, max), random_double(min, max));
}
//...

하지만 이 방법으로는 완전한 구 내부의 벡터를 찾을 수 없음 어떤 벡터는 구 외부로 나갈것이고, 어떤 벡터는 바라보는 구 방향의 반대방향을 가리키고 있을것이고,, 어떤 벡터는 구 내부에서만 있을것임.

rejection 샘플링

이때 필요한게 rejection method기반의 샘플링임

Rejection Method

랜덤에 의존적인 샘플링 기법임

특정 랜덤값을 생성하고, 해당 값이 특정 조건이 부합하는지를 판단하여 사용하는 것을 Rejection Method라고 부름

따라서 우리가 할 건, 아래의 요구사항을 구현하는 거임

1. 반지름이 정규화된 벡터인 1의 크기를 가지는 구가 있다고 가정
2. 그 구를 둘러싼 큐브가 있고, 구의 지름의 변의 크기를 가짐
3. 구의 중심에서부터 랜덤으로 모든 요소의 값이 -1~1사이의 값을 가지는 점을 하나 찍음
4. 해당 점이 정규화된 반지름의 크기를 가지는 구 내부에 위치(크기가 특정 값 이하)한다면 해당 점을 이용해 구의 중심에서부터 표면까지 정규화된 벡터를 구함
5. 이 벡터가 원하는 반구의 방향이 아닌, 다른 방향에 위치한다면 -를 곱해 원하는 방향을 향하도록 만들어준다

   1.	2.

따라서 아래처럼 랜덤한 점을 찍고, 해당 점이 구 내부에 위치한다면 단위벡터크기를 가지는 벡터를 만드는 함수를 만들어줌

inline Vector3 random_unit_vector()
{
    while (true)
    {
        Vector3 point = Vector3::random(-1, 1);
        double lenSq = point.length_squared();

        //벡터 길이가 1보다 작으면 무조건 구 안에 존재, 이를 단위벡터로 정규화
        if (lenSq <= 1) return point / sqrt(lenSq);
    }
}

근데 문제가 있음

일단 length_square 메서드를 살펴보자

double length_squared() const
{
    return e[0] * e[0] + e[1] * e[1] + e[2] * e[2];
}

Vector3의 각 요소를 제곱하여 더한 값이 벡터크기이니까 저런 코드가 만들어짐

만약 Vector3의 각 요소가 구의 중심과 매우매우 가까워서 거의 0의 값을 가진다고 가정해보자

double은 소수점 아래 최대 15자리?정도까지 소수점 표현이 가능함. 따라서 특정 좌표가 0.00000000001, 0.00000000001, 0.00000000001라고 할때, 길이를 계산하면 0이라는 값이 나옴.

그리고 이 값을 이용해 정규화를 하면, 벡터/벡터크기라는 식인데, 이는 division by zero식이 되어버림

그래서 이를 방지해줘야함

정밀도 vs 표현범위

10e-160의 이유

double형의 소수점 아래는 15~18자리임 이는 정밀도라고 부름

정밀도는 소수점 아래 몇자리까지 정확하게 표현 가능한가를 의미함

하지만 표현범위는 조금 다름

표현범위는 표현할 수 있는 숫자의 범위를 의미함

double형의 정밀도는 15~18자리인데 반해 double형의 표현범위는 $\pm 2.23 * 10^{-308}$ ~ $\pm1.8 * 10^{308}$ 임

따라서 표현범위를 커버하기위해 -308~308이라는 범위를 커버하기위해 제곱시 320이라는 지수를 가지는 160이 채택된거임

지수 154의 제곱이 308이라 딱 떨어지는거 아님??

맞음 Quora > In Python, why is 1e-323 = 0 false, but 1e-324 = 0 is true? How/why was -324 defined/chosen?

c++ fundamental - range of values

를 살펴보면 이렇게 min sub normal이 $10^{-324}$라고 되어있는것을 볼 수 있음

이 값까지 표현하기위해 제곱시 324이하가 되고, 그냥 계산하기 편해서 그럼ㅇㅇ

1. rejection샘플링을 통해 랜덤 점 -> 정규화된 벡터 구하기

그래서 코드는 다음과 같아짐

inline Vector3 random_unit_vector()
{
    while (true)
    {
        Vector3 point = Vector3::random(-1, 1);
        double lenSq = point.length_squared();

        //벡터 길이가 1보다 작으면 무조건 구 안에 존재, 이를 단위벡터로 정규화
        if (1e-160 < lenSq && lenSq <= 1) return point / sqrt(lenSq);
    }
}

2. 구한 정규화된 벡터의 방향이 원하는 반구의 방향이 아닐때

벡터의 방향이 원하는 반구의 방향이 아닐때, -를 곱해주면 됨.

이때 사용하는건 역시나 내적으로,

두 벡터 랜덤 점에서부터 정규화된 벡터와 Ray를 쏴서 구와의 충돌지점 좌표를 구한 후, 구의 중심에서부터 충돌좌표까지 방향이 구 표면에서의 Normal이기 때문에 이렇게 구한 정규화된 Normal벡터

를 내적을 통해 값이 0 이하면 랜덤 점에서부터 정규화된 벡터는 원하는 반구 방향이 아닌, 반대방향을 가리키고 있다는 뜻으로 -를 곱해 방향을 뒤집어준다!

가 됨

이 각도는 정규화 normal벡터 기준 $0^\circ$ ~ $90^\circ$사이에 위치하거나 $270^\circ$ ~ $360^\circ$사이에 위치할때, 반구 방향임

색상을 결정짓는 코드를 아래처럼 손봐주면 됨!

//Camera.h...
Color ray_color(const Ray& r, const Hittable& world) const
{
    HitRecord rec;
    if (world.hit(r, MinMaxInterval(0, infinity), rec))
    {
        //기존의 hit된 지점에서 normal방향으로 1번 반사에서
        //hit된 지점에서 랜덤한 바라보는 반구방향으로 재귀적으로 반사로 바꿈
        Vector3 dir = random_on_hemisphere(rec.normal);
        return 0.5 * ray_color(Ray(rec.p, dir), world);
    }

    Vector3 unit_direction = unit_vector(r.direction());

    double t = 0.5 * (unit_direction.y() + 1.0);

    return (1.0 - t) * Color(1.0, 1.0, 1.0) + t * Color(0.5, 0.7, 1.0);
}

재귀 문제

하지만 이 코드는 심각한 결점이 있음

일단 stack overflow라고 들어봤지?

재귀가 너무 많이 일어나면 메모리 스택이 터져서 시스템이 뻗어버리는거임ㅇㅇ

지금 코드는 계속해서 재귀를 호출할때 랜덤한 벡터를 만들고, 그 벡터가 구 안에 존재할때 ~~~hemisphere메서드가 호출이 되는거지

근데 만약

여기서 재귀호출로 hit이 계속 되면 어떻게 되지?

ㅇㅇ그냥 잠재적 시스템 폭파범임

그래서 이걸 해결하기위해 재귀의 최대 깊이를 설정해줘야함

//Camera.h...

public:
    int    max_depth    = 10; //재귀 호출 최대 반복 수

    //...

    void render(const Hittable& world) 
    {
        //...
        for (int sample = 0; sample < samples_per_pixel; sample++)
        {
            Ray r = get_ray(i,j);
            pixel_color += ray_color(r, max_depth, world); //max_depth추가
        }
        //...
    }

    //...
private:
    Color ray_color(const Ray& r, int depth, const Hittable& world) const
    {
        if (depth <= 0) return Color(0,0,0);

        HitRecord rec;
        if (world.hit(r, MinMaxInterval(0, infinity), rec))
        {
            //기존의 hit된 지점에서 normal방향으로 1번 반사에서
            //hit된 지점에서 랜덤한 바라보는 반구방향으로 재귀적으로 반사로 바꿈
            Vector3 dir = random_on_hemisphere(rec.normal);
            return 0.5 * ray_color(Ray(rec.p, dir), depth - 1, world);
        }

        Vector3 unit_direction = unit_vector(r.direction());

        double t = 0.5 * (unit_direction.y() + 1.0);

        return (1.0 - t) * Color(1.0, 1.0, 1.0) + t * Color(0.5, 0.7, 1.0);
    }

이렇게 depth를 이용하도록 해주면 됨

그리고 main에서 max_depth를 적절한 값으로 초기화 시키셈

그럼 결과가 아래처럼 나옴

기가막힌다 이거!!

Lambertian Reflection

람베르트 반사라고 불리는 빛 반사 알고리즘임

유니티 쉐이더 기본 - 빛, 램버트 조명 모델 위 링크를 참고해서 약간의 지식을 얻고 가보자

위의 빛 반사는 임시적인 빛 반사로직으로, 실제의 빛 반사와는 거리가 좀 멀음

단순히 Matte재질은 빛을 난반사 한다는 특성을 이용해 구현한거임

핵심 아이디어는 다음과 같음

1. Ray를 쏴서 구의 표면에 점하는 접점을 $P$라고 부름
2. 점 P에서 표면은 2개임
   • 하나는 Normal이 구 바깥으로 뻗는 면
   • 하나는 Normal이 구 내부로 뻗는 면
3. 따라서 이를 이용해 반지름이 단위벡터인 구를 그린다고 가정
4. 구 바깥으로 Normal이 뻗을때 : $구의 중심 = P+N$
   • 구 내부로 Normal이 뻗을때 : $구의 중심 = P-N$
5. $P+N$일때, 구의 단위벡터 반경에서 특정 점을 $S$라고 부름

Ray와 구의 접점 : $P$ 구의 접점에서 구의 바깥방향의 Normal : $N$

단위벡터를 반지름으로 가지는 바깥방향 Normal의 구의 중심 : $C$ $C = P + N$

구의 단위벡터에 있는 랜덤한 점 : $S$, 구의 중심에서 랜덤 단위크기 벡터 : $R$ $S = C + R = (P+N)+R$

구의 단위벡터에 있는 랜덤한 점에서 Ray와 구의 접점 방향 $S-P = (C+R) - P = (P+N)+R - P = N + R$

따라서 접점$P$에서 Normal과 Random단위크기 벡터를 더하면 접점$P$에서 단위벡터 반지름크기 구의 랜덤 접점$S$까지의 크기가 나옴 이걸 이용해서 빛을 계산!

//Camera.h...
Color ray_color(const Ray& r, int depth, const Hittable& world) const
{
    if (depth <= 0) return Color(0,0,0);

    HitRecord rec;
    if (world.hit(r, MinMaxInterval(0, infinity), rec))
    {
        //기존의 hit된 지점에서 normal방향으로 1번 반사에서
        //hit된 지점에서 랜덤한 바라보는 반구방향으로 재귀적으로 반사로 바꿈
        Vector3 dir = rec.normal + random_unit_vector(); //N + R
        return 0.5 * ray_color(Ray(rec.p, dir), depth - 1, world);
    }

    Vector3 unit_direction = unit_vector(r.direction());

    double t = 0.5 * (unit_direction.y() + 1.0);

    return (1.0 - t) * Color(1.0, 1.0, 1.0) + t * Color(0.5, 0.7, 1.0);
}

자 여기서 다시한번 rec.normal이 어떻게 계산되는지 살펴보자

rec.normal 다시보기

//Camera.h : ray_color메서드 if (world.hit(r, MinMaxInterval(0, infinity), rec))

world는 hittableList객체의 변수명임

hittableList.h의 hit를 살펴보자

//HittableList.h

bool hit(const Ray& r, MinMaxInterval ray_t, HitRecord& hitRec) const override
{
    HitRecord tempRec;
    bool doesHitAnything = false;
    double closestSoFar = ray_t.max;

    for (const shared_ptr<Hittable>& obj : objs)
    {
        if (obj -> hit(r, MinMaxInterval(ray_t.min, closestSoFar), tempRec))
        {
            doesHitAnything = true;
            closestSoFar = tempRec.t;
            hitRec = tempRec;
        }
    }

    return doesHitAnything;
}

반복문을 보면 objs라는 배열내의 객체들에 대해 반복문을 돌리고 잇음

그리고 각 객체에 대해 hit메서드를 execute중임

그럼 obj는 Hittable객체이고, Hittable객체는 현재 sphere이니, Sphere.h의 hit를 살펴보자

//Sphere.h

bool hit(const Ray& r, MinMaxInterval ray_t, HitRecord& hitRec) const override
{
    Vector3 oc = center - r.origin();
    double a = r.direction().length_squared();
    double half_b = dot(r.direction(), oc);
    double c = oc.length_squared() - radius * radius;
    double discriminant = half_b * half_b - a * c;

    if (discriminant < 0)
    {
        return false;
    }

    //sqrt연산은 무겁기때문에, 캐싱해둠
    double sqrtDis = sqrt(discriminant);

    //이동거리 스칼라 t에 대해 tmin ~ tmax사이를 이동한 거리 t에 대해서만 구와 ray의 교차범위를 찾음
    double root = (half_b - sqrtDis) / a;

    //tmax와 tmin사이에 없는 경우 false리턴
    if (!ray_t.surrounds(root))
    {
        root = (half_b + sqrtDis) / a;
        if (!ray_t.surrounds(root))
        {
            return false;
        }
    }

    hitRec.t = root;
    hitRec.p = r.at(hitRec.t);
    Vector3 outward_normal = (hitRec.p - center) / radius;
    hitRec.set_face_normal(r, outward_normal);

    return true;
}

구체 그리기 포스트에서 살펴본 근의 공식을 이용해 Ray와 구의 접점을 찾는 공식이 들어가 있음

먼저 a, b, c를 계산하고, 조건에 따라 근을 찾아냄

근이 모든 조건에 부합한다면

1. hitRec의 t(이동거리 스칼라값)을 근으로 초기화함 이 t는 Ray에서부터 구의 접점까지의 이동거리가 됨
2. t를 이용해서 Ray의 원점에서부터 t만큼 이동한 거리에 있는 좌표를 hitRec의 p를 초기화함
3. hitRec.p - 구의 중심을 통해 구의 구의 중심에서부터 p까지 이어지는 Normal을 구하고, 구의 반지름으로 나누어 단위벡터로 만듬
   • 구의 중심 ~ p까지의 벡터는 접점p에서 구 바깥으로 향하는 Normal임
4. hitRec의 Normal을 Ray의 방향과 구한 단위벡터 Normal을 내적하여 Normal이 앞면인지, 뒷면인지 판단 후에 값을 그대로 사용하거나 반전시켜 hitRec.normal에 3번에서 구한 Normal을 초기화

감마 보정

Color ray_color(const Ray& r, int depth, const Hittable& world) const
{
    if (depth <= 0) return Color(0,0,0);
>     
    HitRecord rec;
    if (world.hit(r, MinMaxInterval(0.001, infinity), rec))
    {
        //기존의 hit된 지점에서 normal방향으로 1번 반사에서
        //hit된 지점에서 랜덤한 바라보는 반구방향으로 재귀적으로 반사로 바꿈
        Vector3 dir = rec.normal + random_unit_vector();
 >
        //0.9값을 0.1~0.9까지 0.2씩 증가하며 계산
        return 0.9 * ray_color(Ray(rec.p, dir), depth - 1, world);
    }
>     
    Vector3 unit_direction = unit_vector(r.direction());
> 
    double t = 0.5 * (unit_direction.y() + 1.0);
>
    return (1.0 - t) * Color(1.0, 1.0, 1.0) + t * Color(0.5, 0.7, 1.0);
}

이렇게 구체와 hit가 되었을때 색을 0.5가 아닌, 원하는 값으로 설정해보자 . 난 교재에서 말하는대로 0.1~0.9까지 0.2단위로 렌더링해봄

그럼 이렇게 왼쪽 0.1~오른쪽 0.9까지 색상이 렌더링됨

이때 0.5의 값을 가지는 구간인 중간 이미지를 살펴보자

저 색상이 과연 흰색인 (1,1,1)과 검은색인 (0,0,0)사이인 (0.5, 0.5, 0.5)라고 할 수 있을까? 한번 color picker로 찍어보자

자, 약간의 하늘색이 섞여있다면 실제 회색인 (0.5, 0.5, 0.5)보다 살짝 더 높은 값이거나, 비슷하거나, 약간 낮은 값이 나오겠지?

이 색은 회색보다 예상밖의 어두운 색이라는 거임

이 이유는 감마 보정때문임

감마 보정 (Gamma Correction)

먼저 감마를 알아야함

감마란 입력값과 출력 휘도 사이의 거듭제곱 관계의 지수(exponent)임. 수식으로 표현하면 $출력 = 입력^γ$이고, $γ$(감마) 값이 이 곡선의 형태를 결정함.

이때 감마는 이미지의 인코딩(저장)/디코딩(출력) 곡선의 지수임

우리 눈은 위에서 설명한것처럼 빛의 강도를 비선형적으로 받아들임... 같은 밝기의 형광등이라고 해도, 낮과 밤에 대하여 우리의 눈은 다르게 빛을 받아들임

즉, 사람 눈은 어두운 영역의 변화에 민감하고, 밝은 곳의 변화에는 민감하게 받아들이지 않음.

감마 인코딩

이미지나 비디오를 저장할때 어두운 부분을 더 밝게 만들어 저장하고 이때 지수가 $γ = 1/2.2$임

어두운 부분을 밝게 만드는 이유는 다음과 같음 먼저, 이미지는 휘도를 비트로 저장함. 비트는 0~255까지 256단계임.

감마 인코딩을 하지 않고 그대로 이미지를 저장하면, 이미지의 모든 부분에 선형적으로 비트를 분배하기때문에 밝은부분에 비트가 더 몰리게 됨.

반면 어두운 부분은 비트가 적게 분배되어 색의 계조표현이 부족하게 됨.

계조 : 명암을 디지털로 표현할 때 밝은 부분(명부)과 어두운 부분(암부)으로 이어지는 단계의 차이

따라서 이를 해결하기 위해 어두운 비트를 더 밝게 만들어 많은 비트를 부여함으로써 계조를 늘려 더 세밀한 이미지 색상을 표현할 수 있도록 저장할 수 잇는 거임

감마 인코딩 공식 = $X^\gamma$, $X$ : 입력 이미지 픽셀당 밝기 비트, $^\gamma = 1/2.2$

감마 디코딩

저장된 이미지를 디스플레이에 출력할때 어둡게 만들음

이미 하드웨어적으로 이미지는 인코딩되었다고 가정하여, 출력을 할때 밝아졌던 부분을 어둡게 만들어버림

그것을 $γ = 2.2$ 혹은 감마2.2 라고 부름

감마 디코딩 공식 = $X^\gamma$, $X$ : 입력 이미지 픽셀당 밝기 비트, $^\gamma = 2.2$

오른쪽 사진을 보면 선형의 이미지를 출력하면 원본보다 어두운 감마를 가진 이미지가 출력됨 감마 인코딩된 이미지를 출력하면 원본과 같은 감마를 가진 이미지가 출력됨

따라서 우리는 출력할 이미지를 인코딩된 감마 이미지로 만들고, 이것을 자동으로 디코딩되록 하여 원본의 이미지 색을 구할거임

근데 2.2라는 값은 좀 계산하기 복잡함...

그러니 2.2의 근삿값인 2를 이용할거임

지금 우리에게 필요한건 이 이미지를 직접 손수 감마 인코딩을 해줘야함.

즉, 감마 인코딩 공식인 $^\gamma = 1/2$를 이용할거임

따라서 인코딩 공식에 따라 픽셀당 밝기를 $X$이라고 한다면, $X^\frac{1}{2}$ 을 해주면 됨.

그리고 특정 수 $X$의 $\frac{1}{2}$ 제곱은 $X$의 제곱근을 구하는 것과 같음

중요한건 색상이 0보다 작거나 같은 값인 경우, 유효한 제곱근을 구할 수 없으므로 예외처리 해줘야함

//Color.h

//...

inline double incode_gamma(double linear)
{
    if (linear > 0)
    {
        return sqrt(linear);
    }

    return 0;
}

void write_color(std::ostream& out, const Color& pixel_color) {
    double r = pixel_color.x();
    double g = pixel_color.y();
    double b = pixel_color.z();

    //감마 인코딩
    r = incode_gamma(r);
    g = incode_gamma(g);
    b = incode_gamma(b);

    //...
}

#endif

이렇게 코드를 수정해주면 됨

그럼 아래와 같이 원본 이미지의 색상을 볼 수 있음

반사율	감마 인코딩 전	감마 인코딩 후
0.1
0.3
0.5
0.7
0.9
전체

이거 먼저 하기!

BoxFilter 기반 샘플링

Ray를 일단 카메라에서 뷰포트로 쏘지?

근데 화면 저~ 멀리에 진짜 멀리에 8*8사이즈의 검/흰 체스판이 있다고 생각해보셈

Ray를 쏜 후 해당 체스판에 4개의 Ray가 닿았다고 가정해보자

Ray와 접점이 있는 픽셀의 색이 모두 검은색, 모두 흰색, 혹은 반반 등등 섞여있을 것임

근데 실제로 우리가 진~짜 멀리있는 체스판을 본다고 가정해보면 검/흰으로 보이는게 아니라, 자동적으로 색이 혼합되어 회색으로 보임

이걸 그래픽스를 통해 해결해야함 그리고 이런 기법을 안티앨리어싱이라고 함

픽셀의 각진 부분이나, 색이 혼합되어야 하는 부분을 적절한 기법을 이용해 색을 만드는거임

픽셀은 원임 사각형이 아님

근데 이 BoxFilter 샘플링기법은 픽셀을 사각형이라는 관점으로 바라봄

그래서 픽셀이 도착한 지점을 기준으로 상하좌우 절반씩 확장된 사각형으로 픽셀을 바라본다는거임

그리고 해당 색들의 합의 평균치를 해당 픽셀에 적용시킨다는게 핵심임

이런 기법을 BoxFiltering 기법이라 부르고 SSAA계열의 안티앨리어싱이 이 기법을 사용한 방법임

더 다양한 기법이 있는데 이는 그래픽스 이론책에서 공부할것을 권장!

내가 설명하기엔 너무 길어짐

필요한 메서드 구현

먼저 픽셀에서 랜덤한 좌표를 구할 랜덤 메서드를 만들음ㅇㅇ

//RTWEEKEND.h ....

inline double random_double()
{
    //0~1사이의 랜덤
    return std::rand() / (RAND_MAX + 1.0);
}

inline double random_double(double min, double max)
{
    return min + (max - min) * random_double();
}

그리고 기본적인 색상은 RGB 0-1값임 픽셀의 색상을 계산 후 이 색상에 왜곡이 일어날 수 있음

double계산이 그럼 ㅇㅇ

그러므로 계산된 색상을 특정 범위내에 고정시켜줄 메서드가 필요함 clamp임ㅇㅇ

clamp는 min과 max범위내에서 되어야 하므로, 이를 구현해둔 MinMaxInterval에서 구현하도록 하겠음ㅇㅇ

class MinMaxInterval {
public:
    //...
    bool surrounds(double x) const {
        return min < x && x < max;
    }

     double clamp(double x) const
    {
        if (x < min) return min;
        if (x > max) return max;
        return x;
    }

};

//...

이제 색상을 렌더링하던 메서드에서 색상을 특정 범위내에 잇을 수 있도록 메서드 수정해야함

이렇게 Camera.h에서 사용중인 write_color메서드를 수정해줘야함

//Color.h ...
void write_color(std::ostream& out, const Color& pixel_color) {
    double r = pixel_color.x();
    double g = pixel_color.y();
    double b = pixel_color.z();

    //clamping메서드 추가, rgb를 [0-1]사이의 값으로 clamp
    static const MinMaxInterval clamping(0.000000, 0.999999);
    int rbyte = static_cast<int>(255.999 * clamping.clamp(r));
    int gbyte = static_cast<int>(255.999 * clamping.clamp(g));
    int bbyte = static_cast<int>(255.999 * clamping.clamp(b));

    // Write out the pixel color components.
    out << rbyte << ' ' << gbyte << ' ' << bbyte << '\n';
}

render메서드 수정

이제 픽셀당 샘플수를 결정하고, 해당 샘플수만큼 픽셀에서 랜덤한 위치의 offset(0-1사이)으로 이동한 좌표의 색상을 pick한다음 픽셀의 색으로 변경시키면 된다.

#ifndef CAMERA_H
#define CAMERA_H

#include "Color.h"
#include "hittable.h"

class Camera {
public:
    double aspect_ratio = 1.0;  // Ratio of image width over height
    int    image_width  = 100;  // Rendered image width in pixel count
    int    samples_per_pixel = 10; //픽셀당 랜덤하게 뽑을 샘플의 수

    void render(const Hittable& world) {
        initialize();

        std::cout << "P3\n" << image_width << ' ' << image_height << "\n255\n";

        for (int j = 0; j < image_height; ++j)
        {
            std::clog << "\rScanLines remaining: " << (image_height - j) << ' ' << std::flush;
            for (int i = 0; i < image_width; ++i)
            {
                //pixel_color를 구하기
                Color pixel_color(0,0,0);

                for (int sample = 0; sample < samples_per_pixel; ++sample)
                {
                    Ray r = get_ray(i,j);
                    pixel_color += ray_color(r, world);
                }

                write_color(std::cout, pixel_samples_scale * pixel_color);
            }
        }

        std::clog << "\rDone.    ";
    }

private:
    //...
    double    pixel_samples_scale; //샘플픽셀의 크기, color계산 후 곱해서 해당 픽셀 blurry하게 색상 만들기

    void initialize() 
    {
        //....
        pixel_samples_scale = 1.0 / samples_per_pixel;

        camera_center = Point3(0, 0, 0);

        //...
    }

    Ray get_ray(int i, int j) const
    {
        Vector3 offset = sample_square();
        //(i,j)번째 픽셀의 offset만큼 이동한 center좌표
        Vector3 pixel_sample = pixel00_loc + (i + offset.x()) * pixel_delta_u + (j + offset.y()) * pixel_delta_v;

        Point3 ray_origin = camera_center;
        Vector3 ray_dir = pixel_sample - ray_origin;

        return Ray(ray_origin, ray_dir);
    }

    Vector3 sample_square() const
    {
        return Vector3(random_double() - 0.5, random_double() - 0.5, 0);
    }

    //...
};

#endif

이걸 하면 다음과 같이 결과물이 바뀜

이랬던 픽셀의 테두리가

이렇게 자연스럽게 바뀜!

풀이

쉽게 보면 그리디 문제임

근데 대충 그리디 알고리즘 짜면 개망함

2중포문? 개망함ㅇㅇ

이게 제약조건인데 최대 리스트의 길이가 $10^5$임 2중포문돌면 10억회, 약 10초임

우린 이걸 $O(N^2)$이 아닌 $O(N)$으로 끝낼 방향을 찾아야함

먼저 문제의 핵심은 다음과 같음

1. 무조건 파는 날짜보다 사는 날짜가 빠르다
2. 파는 날의 가격 - 사는 날의 가격 중에 가장 큰 것을 고르면 된다

즉, 사는 날의 가격중 가장 싼 날을 찾고, 파는 날의 가격중 가장 비싼 날을 찾으면 됨

그리고 사는 날은 무조건 파는 날보다 빠름

정리해보면 다음과 같음

1. 사는 날은 가장 저렴한 날이기만 하면 되므로, 저렴한 날이 나올때 마다 갱신
2. 파는 날은 사는 날과 관계없이 팔기만 하면 되므로, 파는날 - 사는날 가격에서 가장 큰 값만 고르기

이걸 코드로 구현하면 다음과 같음

class Solution {
public:
    int maxProfit(vector<int>& prices) {

        int minP = prices[0];
        int max = 0;

        for(int p : prices)
        {
            minp = std::min(minP, p);
            max = std::max(max, p - minP);
        }

        return max;
    }
};

어? 싶지?

minP가 사는 날 중 가장 저렴한 값임

그리고 사는 날과 관계없이 파는날 가격에서 가장 싼 값을 뺀 가격중 가장 큰 값을 고르면 됨

만약 [7,1,3]이 있다고 가정해보면

1. i = 0, minP는 7, max = max(max(0), prices[i] - minP(0))
2. i = 1, minP는 1, max = max(max(0), prices[i] - minP(0))
3. i = 2, minP는 1, max = max(max(0), prices[i] - minP(2))

이렇게 minP가 갱신이 되면 max는 무조건 0이 되어, 항상 최대값만을 갱신하는 코드가 완성되는거임

해설

문제에서 특정 자료구조를 제공함

//Definition for singly-linked list.
struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

이 자료구조를 이용해서 문제를 풀어야 함

문제의 유의사항은 다음과 같음

1. 두 연결리스트의 크기는 다름
2. 반환값은 연결리스트의 head를 반환해야함
3. 주어지는 두 연결리스트는 오름차순 정렬된 리스트임

즉, 포인터를 가지고 놀아야한다는것임

먼저

ListNode* head = nullptr;
ListNode* last = nullptr;

이렇게 head와 last를 구분지어놓는다. head를 반환할거고, last는 head에서부터 이어가며 포인터가 계속 바뀔 객체임

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {

        ListNode* head = nullptr;
        ListNode* last = nullptr;

        while(list1 != nullptr || list2 != nullptr)
        {
            ListNode* t;

            int i1 = list1 == nullptr ? 101 : list1->val;
            int i2 = list2 == nullptr ? 101 : list2->val;

            if(i1 < i2)
            {
                t = list1;
                list1 = list1->next;
            }
            else
            {
                t = list2;
                list2 = list2->next;
            }

            if(head == nullptr)
            {
                head = t;
                last = head;
            }
            else
            {
                last->next = t;
                last = last->next;
            }
        }

        return head;
    }
};

잘 보면 while문에서 주어지는 두 리스트의 nullptr을 체크함

그리고, 최대값인 100을 초과하는 값으로 i1, i2라는 값을 초기화함

i1와 i2를 비교하고, t포인터를 해당 리스트로 바꿔줌

첫 값일때는 head가 nullptr일테니 head 포인터를 t로 바꿔주고, last 포인터는 head로 바꿔줌

그다음부터는 last 포인터를 계속 바꾸면서 수정함

소감

이런 연결리스트는 처음 써봐서 좀 당황... 시간 오래걸림

근데 풀다보니 해결됨

노말벡터 = 법선벡터

법선벡터는 그림자 표현을 위해 사용됨 이는 물체의 표면에서 수직인 벡터(외적)임

bool hit_sphere(const Point3& center, double radius, const Ray& r)
{
    Vector3 oc = center - r.origin();
    double a = dot(r.direction(), r.direction());
    double b = -2.0 * dot(r.direction(), oc);
    double c = dot(oc, oc) - radius * radius;
    double discriminant = b * b - 4 * a * c;

    return (discriminant >= 0);
}

저번시간에 위와 같이 점 $C$를 중심으로 가지는 구에 대해 Ray를 쏜 후 만나는 지점 점 $P$가 구에 속해있는지 아닌지를 판별하는 코드를 짰음

이때 해당 식은 $ax^2 + bx + c = 0$ 형태의 이차방정식이었고, 근의 공식의 판별식을 이용해 판별식이 0보다 크면 Ray는 구를 관통하여 지나가거, 0이면 Ray는 구의 표면을, 0보다 작으면 Ray는 구를 지나가지 않는다는 개념이었음

근데 이건 판별식임

예를들어 햇빛이 뷰포트 기준 y축 높은 곳에 위치했을때, 구의 하단과 상단은 빛의 반사가 다를거임

판별식은 단순히 Ray를 쏜 후 만나는 접점 $P$가 구를 지나는지 아닌지만 판별을 하는 용도임

따라서 구의 어느 부분에 Ray가 만나 접점이 생기고, 해당 접점의 거리가 어느정도인지를 알기 위해선 판별식 말고 다른 개념이 필요함

근의공식

근의공식이 필요한거임

double hit_sphere(const Point3& center, double radius, const Ray& r)
{
    Vector3 oc = center - r.origin();
    double a = dot(r.direction(), r.direction());
    double b = -2.0 * dot(r.direction(), oc);
    double c = dot(oc, oc) - radius * radius;
    double discriminant = b * b - 4 * a * c;

    if (discriminant < 0)
    {
        return -1.0;
    }

    return (-b - sqrt(discriminant)) / (2.0 * a);
}

이렇게 코드를 바꿔보자

discriminant의 반환타입을 bool에서 double로 수정함

discriminant만 return을 할때 구와 접점이 없는 Ray에 대해서는 그냥 -1을 return하고, 접점이 있는 Ray에 대해서 근의 공식을 사용하여 근을 찾음

근의 공식은 근이 2개가 될 수 있는데?

이게 핵심임 우리가 물체를 바라볼때 상황에 따라서 물체 뒷면을 볼 수 있지? 예를들어 투명한 페트병같은거 ㅇㅇ

이런곳에서는 근의 공식을 이용했을때 근 2개가 나오는 경우 모두 사용해야함 그리고 이런 경우는 추가로 alpha값을 계산해서 뒷쪽은 좀 더 불투명하도록 계산을 해야함

하지만 위의 코드는 단순이 먼저 구와 Ray가 만나는 접점, 즉 가장 카메라에서 가장 가까운 접점이 반환되는거임

그러니 구의 앞면 부분과 생기는 접점만 반환되고, 뒷면은 무시하는 코드인거임ㅇㅇ

Color ray_color(const Ray& r)
{
    double t = hit_sphere(Point3(0, 0, -1), 0.5, r);
    if (t > 0.0) {
        // 법선 벡터 N을 단위 길이 벡터로 생성
        Vector3 N = unit_vector(r.at(t) - Vector3(0, 0, -1));
        // 법선 벡터 N의 각 구성요소들을 -1 ~ 1 범위에서 0 ~ 1 범위로 매핑
        return 0.5 * Color(N.x() + 1, N.y() + 1, N.z() + 1);
    }

    Vector3 unit_dir = unit_vector(r.direction());

    //unit_dir은 정규화된 벡터로 -1~1사이의 값을 가짐
    //하지만 색상에 -1~0사이의 값은 없음
    //따라서 이를 0~1로 정규화해줘야함
    //그게 (unit_dir + 1) / 0.5인거임
    //-1일때 : (-1 + 1) / 0.5 = 0
    //1일때 : (1 + 1) / 0.5 = 1
    //즉, -1일때는 최하단으로 흰색
    //0일때는 중간으로 (1,1,1)과 (0.5,0.7,1.0)의 중간 혼합색(선형 블렌딩)
    //1일때는 최상단으로 (0.5,0.7,1.0)색
    t = 0.5 * (unit_dir.y() + 1.0);

    return (1.0 - t) * Color(1.0, 1.0, 1.0) + t * Color(0.5, 0.7, 1.0);
}

이제 ray_color메서드를 수정해야하는데,

1. ray의 광선과 방향을 기준으로 구체와 접점이 생기는 부분을 찾음: t > 0.0

2. 조건에 해당되는 부분은 구체와 접점이 있다는 뜻이므로, 해당 접점을 구의 중심으로부터 Normal을 찾음

   이게 무슨소리냐면...

   구가 있고, 구의 중심에서 접점까지까지의 벡터는 수직벡터임

   접점에서 구의 중심을 빼면 중심에서 해당 접점으로의 방향을 가지는 벡터가 나옴

   • 이때 t는 Ray시작 지점에서부터 접점까지의 이동거리(스칼라)임
   • Ray에서 t만큼의 이동한 벡터와 원의 중심좌표를 빼면, 원 중심에서부터 t만큼 이동한 거리에 있는 벡터의 Normal이 만들어지고, 이를 unit_vector를 이용해 정규화 시킴(계산이 쉽도록)

     Point3 at(double t) const 
     {
     return orig + t * dir;
     }

3. 해당 법선벡터의 정규화된 값은 -11사이의 값이므로 01사이의 값으로 만들어주기위해 모든 요소에 +1을 하고 0.5를 곱한다

그럼 아래와 같은 이미지가 만들어짐

이런 값이 나오는건 xyz, rgb에 따른 결과인거임

Ray가 발사된 카메라에서 살펴보면 구체의 정중앙 부분은 카메라와 가장 가까운 면이 될거임

우리가 계산한 식은 모두 Ray를 기준으로 계산된거임, 빛이 아직은 없는거임

정중앙은 Ray와 z축으로 수직이므로 (0,0,1)이됨 이를 정규화과정을 거치면 아래와 같은 색상이 됨

우측은 Ray를 기준으로 x축으로 수직임 (1,0,0) 따라서 우측의 rgb는 1, 0.5, 0.5임

위쪽은 Ray를 기준으로 y축으로 수직임 (0,1,0) 따라서 위쪽의 rgb는 0.5, 1, 0.5임

왼쪽은 Ray를 기준으로 x축으로 수직이지만 방향이 반대임(-1, 0, 0) 따라서 왼쪽의 rgb는 0, 0.5, 0.5가됨

아래쪽은 Ray를 기준으로 y축으로 수직이지만 방향이 반대임 (0, -1, 0) 따라서 아래쪽의 rgb는 0.5, 0, 0.5임

코드 최적화

double hit_sphere(const Point3& center, double radius, const Ray& r)
{
    Vector3 oc = center - r.origin();
    double a = dot(r.direction(), r.direction());
    double b = -2.0 * dot(r.direction(), oc);
    double c = dot(oc, oc) - radius * radius;
    double discriminant = b * b - 4 * a * c;

    if (discriminant < 0)
    {
        return -1.0;
    }
    return (-b - sqrt(discriminant)) / (2.0 * a);
}

이 코드를 잘 살펴보자

1. 자기자신 벡터와의 내적은 자기자신 벡터의 제곱과 같음

먼저 double a, double c부분을 보자

1. r.direction과 r.direction을 내적하고 있음
2. oc와 oc를 내적하고 있음

자신 벡터와의 내적은 자신 벡터의 제곱과 같음 따라서 아래처럼 코드를 수정가능함

double hit_sphere(const Point3& center, double radius, const Ray& r)
{
    Vector3 oc = center - r.origin();
    //자기자신 벡터와의 내적은 자기자신 벡터의 제곱과 같음
    double a = r.direction().length_squared();
    double b = -2.0 * dot(r.direction(), oc);
     //자기자신 벡터와의 내적은 자기자신 벡터의 제곱과 같음
    double c = oc.length_squared() - radius * radius;
    double discriminant = b * b - 4 * a * c;

    if (discriminant < 0)
    {
        return -1.0;
    }
    return (-b - sqrt(discriminant)) / (2.0 * a);
}

2. 근의 공식 최적화

두번째는 근의 공식 자체를 수정하는거임

$\frac{-b \pm \sqrt{b^2 - 4ac}}{2a}$ 가 근의 공식이지?

만약 이때 b가 어떤 수의 -2의 배수라고 가정을 해보셈

즉 half라는 수가 있고 b = -2h라고 가정을 하는거임

그럼 $\frac{-(-2h) \pm \sqrt{(-2h))^2 - 4ac}}{2a} = \frac{2h \pm \sqrt{4(h^2 - ac)}}{2a} = \frac{2h \pm 2\sqrt{h^2 - ac}}{2a} = \frac{h \pm \sqrt{h^2 - ac}}{a}$ 이렇게 더 간단하게 식 유도가 됨

원래 식에서 생각해보면 $b = -2d \cdot (C - Q)$ 였음 $b = -2h$이므로 $-2h = -2d \cdot (C - Q)$와 같음 $h = d \cdot (C - Q)$가 됨

따라서 hit_sphere메서드를 더 가볍게 최적화 가능함

double hit_sphere(const Point3& center, double radius, const Ray& r)
{
    Vector3 oc = center - r.origin();
    //자기자신 벡터와의 내적은 자기자신 벡터의 제곱과 같음
    double a = r.direction().length_squared();
    double half_b = dot(r.direction(), oc);
     //자기자신 벡터와의 내적은 자기자신 벡터의 제곱과 같음
    double c = oc.length_squared() - radius * radius;
    double discriminant = half_b * half_b - a * c;

    if (discriminant < 0)
    {
        return -1.0;
    }
    return (half_b - sqrt(discriminant)) / a;
}

이렇게 바뀌는거임

구체 여러개 그리기

먼저 코사인에 대해 집고 넘어가자

중학교때 배운 코사인 알지?

즉, 두 벡터의 내적의 결과가 0이면 두 벡터는 수직 1이면 두 벡터는 완전 같은 방향(겹침) -1이면 두 벡터는 완전 반대 방향(정면으로 마주봄)

Ray에서 구체로 쏘아지는 광선 계산

이걸 Ray와 구의 접점에 대해 개념을 옮겨보자

1. Ray가 구 외부에서 구 내부로 들어갈때

Ray의 시작점에서 구 내부: ⬇️ Ray와 구의 법선: ⬆️

즉 Ray와 Normal은 서로 바라보는 방향, 완전히 다른 방향이므로 0보다 작은 값(음수)이 된다.

2. Ray가 구 내부에서 구 외부로 나갈때

Ray의 시작점에서 구 외부: ⬆️ Ray와 구의 법선: ⬆️

즉 Ray와 Normal은 서로 같은 방향, 완전히 같은 방향이므로 0보다 큰 값(양수)이 된다.

이것이 outward_normal임

1번일때 Normal은 구 중심에서 접점으로의 방향에서 내적은 0보다 큰 값(양수) $\overrightarrow{Center ,Point}$: ⬆️ Ray와 구의 법선: ⬆️

2번일때 Normal은 구 중심에서 접점으로의 방향에서 내적은 0보다 작은 값(음수) $\overrightarrow{Center ,Point}$: ⬆️ Ray와 구의 법선: ⬇️

이게 inward_normal임

이 중 편한걸 하면 됨

대신 값 계산은 잘 해야지ㅇㅇ

난 outward_normal을 이용해서 Ray와 법선의 관계를 판단하게뜸

핵심은 뒷면은 보이지 않도록 한다는거임 아래 코드처럼 Hittable.h를 만듬

#ifndef HITTABLE_H
#define HITTABLE_H

#include "Ray.h"

class HitRecord
{
public:
    Point3 p;
    Vector3 normal;
    double t;
    bool front_face;

    void set_face_normal(const Ray& r, const Vector3& outward_normal)
    {
        // 1. 광선(Ray)과 밖을 향하는 법선(outward_normal)의 내적이 음수(< 0.0)인지 확인합니다.
        // 내적이 음수면: 광선이 밖에서 안으로 들어오는 중 (앞면, front_face = true)
        // 내적이 양수면: 광선이 안에서 밖으로 나가는 중 (뒷면, front_face = false)
        front_face = dot(r.direction(), outward_normal) < 0.0;

        // 2. 항상 법선이 광선과 마주 보게(내적이 음수가 되게) 방향을 통일해 줍니다.
        // 앞면을 때렸다면 밖을 향하는 법선을 그대로 사용하고,
        // 뒷면(물체 내부)을 때렸다면 법선을 뒤집어서(-outward_normal) 사용합니다.
        normal = front_face ? outward_normal : -outward_normal;
    }
};

class Hittable
{
public:
    virtual ~Hittable() = default;

    virtual bool hit(const Ray& r, double ray_tmin, double ray_tmax, HitRecord& hitRec) const = 0;
};

#endif

그리고 sphere.h를 만듬

#ifndef SPHERE_H
#define SPHERE_H
#include "hittable.h"

class Sphere : public Hittable
{
private:
    Point3 center;
    double radius;
public:
    Sphere();
    Sphere(Point3 center, double r) : center(center), radius(r) {};

    bool hit(const Ray& r, double ray_tmin, double ray_tmax, HitRecord& hitRec) const override
    {
        Vector3 oc = center - r.origin();
        double a = r.direction().length_squared();
        double half_b = dot(r.direction(), oc);
        double c = oc.length_squared() - radius * radius;
        double discriminant = half_b * half_b - a * c;

        if (discriminant < 0)
        {
            return false;
        }

        //sqrt연산은 무겁기때문에, 캐싱해둠
        double sqrtDis = sqrt(discriminant);

        //이동거리 스칼라 t에 대해 tmin ~ tmax사이를 이동한 거리 t에 대해서만 구와 ray의 교차범위를 찾음
        double root = (half_b - sqrtDis) / a;

        //tmax와 tmin사이에 없는 경우 false리턴
        if (ray_tmax <= root || root <= ray_tmin)
        {
            root = (half_b + sqrtDis) / a;
            if (ray_tmax <= root || root <= ray_tmin)
            {
                return false;
            }
        }

        hitRec.t = root;
        hitRec.p = r.at(hitRec.t);
        Vector3 outward_normal = (hitRec.p - center) / radius;
        hitRec.set_face_normal(r, outward_normal);

        return true;
    };
};


#endif

구체 여러개 관리하기

HittableList를 만들어서 관리할거임

#ifndef HITTABLE_LIST_H
#define HITTABLE_LIST_H
#include <vector>

#include "Hittable.h"

using namespace std;

class HittableList : public Hittable
{
public:
    vector<shared_ptr<Hittable>> objs;

    HittableList();
    HittableList(shared_ptr<Hittable> obj) { add(obj); }

    void clear() { objs.clear(); }
    void add(shared_ptr<Hittable> obj)
    {
        objs.push_back(obj);
    }

    bool hit(const Ray& r, double ray_tmin, double ray_tmax, HitRecord& hitRec) const override
    {
        HitRecord tempRec;
        bool doesHitAnything = false;
        double closestSoFar = ray_tmax;

        for (const shared_ptr<Hittable>& obj : objs)
        {
            if (obj -> hit(r, ray_tmin, closestSoFar, tempRec))
            {
                doesHitAnything = true;
                closestSoFar = tempRec.t;
                hitRec = tempRec;
            }
        }

        return doesHitAnything;
    }
};

#endif

shared_ptr은 cpp의 스마트포인터임 그냥 new 와 delete를 적절하게 알아서 잘 해준다고만 알고 넘어가셈

더 궁금하면 cpp smart pointer라는 개념으로 찾기 ㄱㄱ

계산 쎄리기

#ifndef RTWEEKEND_H
#define RTWEEKEND_H

#include <cmath>
#include <iostream>
#include <limits>
#include <memory>


// C++ Std Usings

using std::make_shared;
using std::shared_ptr;

// Constants

const double infinity = std::numeric_limits<double>::infinity();
const double pi = 3.1415926535897932385;

// Utility Functions

inline double degrees_to_radians(double degrees) {
    return degrees * pi / 180.0;
}

// Common Headers

#include "color.h"
#include "ray.h"
#include "vec3.h"

#endif

먼저 이런 Util클래스를 만들어줌

그리고 main을 수정하자

Color ray_color(const Ray& r, const Hittable& world) {
    HitRecord rec;
    if (world.hit(r, 0, infinity, rec)) {
        return 0.5 * (rec.normal + Color(1, 1, 1));
    }

    Vector3 unit_direction = unit_vector(r.direction());

    double t = 0.5 * (unit_direction.y() + 1.0);

    return (1.0 - t) * Color(1.0, 1.0, 1.0) + t * Color(0.5, 0.7, 1.0);
}

int main()
{
    auto aspect_ratio = 16.0 / 9.0;
    int image_width = 400;

    //height  = width / 16 * 9 = width * 9 / 16 = width / (16 / 9)
    int image_height = int(image_width / aspect_ratio);
    //height가 1보다 작으면 최소한 1이라도 보장하기
    image_height = (image_height < 1) ? 1 : image_height;

    //world
    HittableList world;
    world.add(make_shared<Sphere>(Point3(0, 0, -1), 0.5));
    world.add(make_shared<Sphere>(Point3(0, -100.5, -1), 100));

    // Camera
    //카메라부터 뷰표트까지의 거리
    double focal_length = 1.0;
    double viewport_height = 2.0;
    //해상도 비율을 사용하지 않고, 이미지를 사용하는 이유
    //해상도 이미지는 이상적인 비율이고, 실제 이미지의 비율은 해상도 비율과 다를 수 있음
    //width = height / 9 * 16 = height * 16 / 9
    double viewport_width = viewport_height * (double(image_width) / image_height);
    Point3 camera_center = Point3(0, 0, 0);

    //뷰표트의 왼->오, 상->하로 이동하는 최대 좌표 구하기
    Vector3 viewport_u = Vector3(viewport_width, 0, 0);
    Vector3 viewport_v = Vector3(0, -viewport_height, 0);

    //뷰포트의 각 픽셀간의 거리 구하기(델타 벡터)
    Vector3 pixel_delta_u = viewport_u / image_width;
    Vector3 pixel_delta_v = viewport_v / image_height;

    //최 좌상단 픽셀의 좌표구하기
    //camera_center - Vector3(0, 0, focal_length) : 뷰포트 바로 위에서 focal_length만큼 z방향 반대로 떨어지기
    // - viewport_u/2 - viewport_v/2 : 화면의 가로세로 절반씩 좌, 상으로 이동하기(뺄셈)
    Vector3 viewport_upper_left = camera_center - Vector3(0, 0, focal_length) - viewport_u / 2 - viewport_v / 2;
    //위의 공식은 뷰포트의 최좌상단 좌표가 됨. 하지만 픽셀 시작 좌표는 아님
    //따라서 시작지점은 뷰포트 픽셀거리의 절반만큼 띄워진 거리에서부터 시작해야 정확히 너비 * 높이 개의 영역으로 균등하게 나눠짐
    Vector3 pixel00_loc = viewport_upper_left + 0.5 * (pixel_delta_u + pixel_delta_v);

    //render
    cout << "P3\n" << image_width << ' ' << image_height << "\n255\n";

    for (int j = 0; j < image_height; ++j)
    {
        clog << "\rScanLines remaining: " << (image_height - j) << ' ' << flush;
        for (int i = 0; i < image_width; ++i)
        {
            Vector3 pixel_center = pixel00_loc + (i * pixel_delta_u) + (j * pixel_delta_v);
            Vector3 ray_dir = pixel_center - camera_center;
            Ray r = Ray(camera_center, ray_dir);

            //world인 hittableList를 이용해 색상계산
            Color pixel_color = ray_color(r, world);

            write_color(std::cout, pixel_color);
        }
    }

    clog << "\rDone.                                                     \n";
}

색이 계산되는 과정은 아래와 같음

1. HittableList에 원 2개를 넣음
2. ray_color를 통해 Hittable오브젝트의 hit을 실행함
3. HittableList는 Hittable오브젝트이므로 HittableList를 인자값으로 넣어 HittableList.hit을 실행
4. HittableList의 hit메서드 내부에서 for문을 돌며 List에 담긴 Hittable오브젝트 -> Sphere의 hit을 실행
5. true가 반환되면 참조로 들어갔던 HitRecord객체의 normal을 이용해 색상계산 후 화면에 출력

이 됨

실행결과는 다음과 같음

추가로 https://raytracing.github.io/books/RayTracingInOneWeekend.html#surfacenormalsandmultipleobjects/anintervalclass 이것도 해주자