소프트웨어 렌더러 만들기 - 7 (직선 그리기)

여기까지의 작업내용: https://github.com/hwi-middle/HimchanSoftwareRenderer/tree/3c741c781e32f772d56da936a6d7e51f08b4d452

GitHub - hwi-middle/HimchanSoftwareRenderer: C++로 구현한 소프트웨어 렌더러입니다.

Graphics 모듈 추가

뭔가 화면에 그려주는 처리 같은걸 어디서 해줄까 고민을 하다가 HCGraphics라는 모듈을 하나 추가해줬다. 이번에 구현한 직선을 그리는 처리는 여기서 진행한다.

코헨-서덜랜드 알고리즘을 통한 라인 클리핑

static class DrawHelper
{
private:
    typedef int ViewportRegion;
    static constexpr ViewportRegion INSIDE_VIEWPORT = 0b0000;
    static constexpr ViewportRegion LEFT = 0b0001;
    static constexpr ViewportRegion RIGHT = 0b0010;
    static constexpr ViewportRegion BOTTOM = 0b0100;
    static constexpr ViewportRegion TOP = 0b1000;

    static bool ClipLine(Vector2& InOutStartPos, Vector2& InOutEndPos, const Vector2& InMinPos, const Vector2& InMaxPos)
    {
        ViewportRegion StartRegion = ComputeViewportRegion(InOutStartPos, InMinPos, InMaxPos);
        ViewportRegion EndRegion = ComputeViewportRegion(InOutEndPos, InMinPos, InMaxPos);

        while (true)
        {
            if (!(StartRegion | EndRegion))
            {
                return true;
            }
            else if (StartRegion & EndRegion)
            {
                return false;
            }
            else
            {
                ViewportRegion RegionToClip = max(StartRegion, EndRegion);
                Vector2 ClippedPos;

                float Width = (InOutEndPos.X - InOutStartPos.X);
                float Height = (InOutEndPos.Y - InOutStartPos.Y);
                
                // 여차저차 직선의 방정식을 통해 클리핑...
            }
        }
    }

    static ViewportRegion ComputeViewportRegion(const Vector2& InPos, const Vector2& InMinPos, const Vector2& InMaxPos)
    {
        ViewportRegion Result = INSIDE_VIEWPORT;
        if (InPos.X < InMinPos.X)
        {
            Result |= LEFT;
        }
        else if (InPos.X > InMaxPos.X)
        {
            Result |= RIGHT;
        }

        if (InPos.Y < InMinPos.Y)
        {
            Result |= BOTTOM;
        }
        else if (InPos.Y > InMaxPos.Y)
        {
            Result |= TOP;
        }

        return Result;
    }
    
    // ...
}

직선을 그리기 전에 뷰포트 바깥으로 벗어난 부분은 없는지 확인하고, 벗어난 부분이 있다면 잘라내어야한다. 왜냐하면 눈에 보이지도 않는 영역에 선을 그으며 성능을 낭비할 필요가 없기 때문이다. 이러한 라인 클리핑 처리는 코헨-서덜랜드 알고리즘을 사용하여 구현했다.

 

일단 <이득우의 게임수학> 서적을 통해 이론을 충분히 이해한 다음 위키피디아의 구현과 CK렌더러의 구현을 모두 참고하여 내 취향에 맞는 쪽을 부분부분 취사선택하였다.

 

코헨-서덜랜드 알고리즘은 대단히 흥미로웠다. 4비트 정수를 상위 2비트, 하위 2비트로 나누어 뷰포트 바깥 상하좌우의 정보를 담고 bitwise연산을 통해서 알아내는 것인데 감탄스러웠다.

 

별개로 <이득우의 게임수학>에서는 뷰포트 내에 존재하는지 확인하는 처리에 대한 설명은 담았지만 실질적인 클리핑 처리는 독자의 몫으로 남겨두었다. 다만 직선의 방정식을 활용한다는 핵심적인 개념을 언급해주어서 직접 구현을 살펴보는 입장에서 이해에 큰 도움이 되었다.

 

브레젠험 알고리즘을 통한 직선 그리기

// ...
static void DrawLine(const HDC InHdc, const Vector2& InScreenSize, const Vector2& InStartPos, const Vector2& InEndPos, const COLORREF InColor)
{
    Vector2 HalfScreen = InScreenSize * 0.5f;
    Vector2 MinScreen = -HalfScreen;
    Vector2 MaxScreen = HalfScreen;
    Vector2 ClippedStartPos = InStartPos;
    Vector2 ClippedEndPos = InEndPos;

    if (!ClipLine(ClippedStartPos, ClippedEndPos, MinScreen, MaxScreen))
    {
        return;
    }

    Vector2 StartPosScreen = ScreenPoint::CartesianToScreen(ClippedStartPos, InScreenSize.X, InScreenSize.Y);
    Vector2 EndPosScreen = ScreenPoint::CartesianToScreen(ClippedEndPos, InScreenSize.X, InScreenSize.Y);

    int Width = EndPosScreen.X - StartPosScreen.X;
    int Height = EndPosScreen.Y - StartPosScreen.Y;

    bool bIsGradualScope = Math::Abs(Width) >= Math::Abs(Height);
    int DeltaX = (Width >= 0) ? 1 : -1;
    int DeltaY = (Height >= 0) ? 1 : -1;
    int Fw = DeltaX * Width;
    int Fh = DeltaY * Height;

    int Discriminant = bIsGradualScope ? Fh * 2 - Fw : 2 * Fw - Fh;
    int DeltaWhenDiscriminantIsNegative = bIsGradualScope ? 2 * Fh : 2 * Fw;
    int DeltaWhenDiscriminantIsPositive = bIsGradualScope ? 2 * (Fh - Fw) : 2 * (Fw - Fh);

    int X = StartPosScreen.X;
    int Y = StartPosScreen.Y;

    if (bIsGradualScope)
    {
        while (X != EndPosScreen.X)
        {
            SetPixel(InHdc, X, Y, InColor);

            if (Discriminant < 0)
            {
                Discriminant += DeltaWhenDiscriminantIsNegative;
            }
            else
            {
                Discriminant += DeltaWhenDiscriminantIsPositive;
                Y += DeltaY;
            }

            X += DeltaX;
        }
    }
    else
    {
        while (Y != EndPosScreen.Y)
        {
            SetPixel(InHdc, X, Y, InColor);

            if (Discriminant < 0)
            {
                Discriminant += DeltaWhenDiscriminantIsNegative;
            }
            else
            {
                Discriminant += DeltaWhenDiscriminantIsPositive;
                X += DeltaX;
            }

            Y += DeltaY;
        }
    }
}

라인 클리핑도 했으니 이제 직선을 그릴 차례다. 직선을 그리는 것은 브레젠험 알고리즘을 사용했다. 이 부분은 CK렌더러 코드를 가져왔다. 사실 더 개선해보려고 했는데 더 지저분해지기만 해서 네이밍만 바꾸는 것으로 결정했다.

 

브레젠험 알고리즘은 시작점과 끝점이 주어졌을 때, 직선의 방정식을 이용하여 스크린 공간에서 직선을 긋는 알고리즘이다. 이것도 식을 이러쿵 저러쿵 정리해서 간단한 판별식만 남게되는게 흥미로웠다. <이득우의 게임수학>이 아니었다면 접하기도 어려웠을 것 같다. 다시 한 번 교수님께 감사합니다...

 

실행화면

이렇게 직선을 몇개 그어보고 로그를 찍어보면 클리핑이 잘 되는걸 볼 수 있다!

 

사실 <이득우의 게임수학>이라는 말이 되게 어색한게, 학교에서는 이득우 '교수님'이라고만 부르는데 책 이름을 칭할 때 '이득우의 게임수학'이라고 하면 되게 죄책감(?)든다...

렌더러 구조에 대한 고민

이번에 확실히 느낀게, 렌더러 구조가 많이 부족하다고 느꼈다. 지금은 HimchanSoftwareRenderer 모듈에서 WinAPI에 대한 처리라던가 하는 부분을 다 하고 있는데, HCGraphics쪽에 이런 처리를 많이 위임해야할 것 같다. 뭐랄까, 엔진같은 구조를 만들어야겠다는 생각이다. Update(Tick) 같은 것도 있고, fps 체크하는 것도 있고, 이런 처리들을 간단하게 가져다 쓸 수 있는 구조가 필요하다.

 

특히, 이번에 직선을 그리는 기능을 구현하다보니 이러한 구조를 잡는게 시급하다고 느꼈다. 지금은 디바이스 컨텍스트hdc를 파라미터로 넘겨서 거기다 그리고 있는데, 근본적으로 구조가 바뀌어야한다. 다음 작업은 이 부분이 될 것 같은데 다소 막막하다. 일단 CK렌더러의 구조를 더 살펴봐야겠다.