[과제] 2주차) Basic Programming 조정민

2주차 과제로 다각형을 직선으로 잘라 조각내는 예제를 만들었습니다. 드래그로 선을 그으면 도형이 그 각도로 갈라지고, 잘린 조각은 사라지지 않고 남아서 다시 자를 수 있습니다.

브랜치: https://github.com/YoungB0/thorvg.example/tree/example/polygon-slicing

왜 이걸 만들었나

해커톤 프로젝트로 도형을 계속 잘라나가는 게임을 등록해뒀습니다. 그런데 정작 “직선 하나로 도형을 둘로 나누는 것”이 되는지를 확인 안 한 상태였습니다. 이게 안 되면 기획이 통째로 무너지는 항목인데 계속 미루고 있었습니다.

과제랑 같이 하면 되겠다 싶어서 이걸로 정했습니다. 계산한 좌표를 moveTo/lineTo로 그리는 게 전부라 2주차 범위에도 맞았습니다.

자르는 방법

처음엔 경계 추적(boundary tracing)을 쓰려고 했습니다. 교차점을 전부 구한 뒤 테두리와 선을 번갈아 따라가며 조각을 완성하는 방식인데, 오목한 도형도 처리된다는 게 장점입니다.

찾아보니 볼록 도형만 다룰 거면 훨씬 간단한 방법이 있었습니다. 반평면 클리핑(Sutherland-Hodgman)입니다.

자르는 직선을 기준으로 평면이 두 쪽으로 나뉩니다. 꼭짓점을 순서대로 돌면서 “이 점이 어느 쪽인가”만 보고 남길 쪽만 모읍니다. 한 점은 남기는 쪽인데 다음 점은 버리는 쪽이면 그 변이 선을 넘어간 거니까, 교차점을 계산해서 끼워넣습니다.

부호 판정은 외적 하나로 끝납니다.

//Signed area of the triangle abp. The sign tells which side of ab the point lies on.
static float side(const Point& a, const Point& b, const Point& p)
{
    return (b.x - a.x) * (p.y - a.y) - (b.y - a.y) * (p.x - a.x);
}

한쪽 부호로 한 번, 반대로 한 번 돌리면 조각 두 개가 나옵니다.

auto left = clipHalf(piece.outline, a, b, true);
auto right = clipHalf(piece.outline, a, b, false);

여기서 성질이 하나 있습니다. 볼록 도형을 직선으로 자르면 두 조각도 반드시 볼록합니다. 볼록집합과 반평면의 교집합은 볼록이기 때문입니다. 그래서 오각형으로 시작하면 몇 번을 잘라도 조각들이 끝까지 볼록으로 남고, 이 방법의 전제가 안 깨집니다.

선 하나가 조각 여러 개를 관통해도 상관없습니다. 조각들이 이미 따로 떨어진 다각형이라 각각에 같은 계산을 돌리면 됩니다.

전부 합쳐 40줄 정도였습니다. 경계 추적을 안 써서 다행이라고 생각했습니다.

흩어짐

자르기만 하면 조각이 붙어 있어서 잘렸는지 안 보입니다. 그래서 밀려나게 했습니다.

방향은 무작위가 아니라 자른 선의 수직 방향으로 잡았습니다. 칼이 지나가면서 벌어지는 느낌을 내보려고 했습니다. 여기에 작은 흔들림을 더했습니다.

auto nx = -dy / length;
auto ny = dx / length;

순간이동하면 밋밋해서 감속하며 미끄러지게 했습니다. 매 프레임 속도에 0.97을 곱해 3%씩 깎습니다. 처음엔 빠르게 벌어지다가 갈수록 느려지고 멈춥니다.

숫자를 맞추는 데 시간이 좀 걸렸습니다. 감속을 완만하게 하면 시간이 늘어나는 대신 거리도 같이 늘어나서, 초기 속도를 낮춰 상쇄해야 했습니다. 두 값이 붙어 있는 줄 몰랐습니다.

조각 색도 잘릴 때마다 부모 색에서 조금씩 어긋나게 했습니다. 여러 번 자르면 같은 계열인데 미묘하게 다른 조각들이 생겨서, 어느 게 어디서 갈라져 나왔는지 보입니다.

좌표를 직접 옮기고 translate()는 안 썼습니다. translate()는 화면상 위치만 바꾸는 거라 데이터 좌표는 제자리에 남습니다. 그러면 다음에 자를 때 판정이 어긋납니다.

사용한 API

API	용도
`Shape::gen`	조각·배경·가이드 선
`Shape::moveTo` / `lineTo` / `close`	계산된 조각 경로
`Shape::appendRect`	배경
`Shape::fill`	조각 색
`Shape::strokeFill` / `strokeWidth`	테두리, 가이드 선
`Shape::strokeDash`	드래그 중 점선
`Canvas::add`	씬에 추가
`Canvas::remove`	인자 없이 부르면 전체 삭제
`Canvas::update`	변경 반영

Example.h의 clickdown / motion / clickup / update를 override해서 마우스랑 프레임을 처리했습니다.

화면이 멈췄습니다

몇 번 자르다 보면 프로그램이 굳었습니다. 크래시가 아니라 창이 그대로 멈추는 형태였습니다.

조각이 많아져서 무거워진 줄 알았는데, 멈춘 화면을 보니 조각이 아직 하나였습니다. 자르는 중이 아니라 드래그하는 중에 멈춘 거였습니다.

문제는 그리는 시점이었습니다. motion() 안에서 바로 화면을 다시 그리고 있었습니다.

bool motion(tvg::Canvas* canvas, int32_t x, int32_t y) override
{
    dragEnd = {(float)x, (float)y};
    redraw(canvas);   //여기
    return true;
}

redraw()는 canvas->remove()로 Paint를 전부 지우고 다시 만든 뒤 canvas->update()를 부릅니다. 그런데 Example.h의 루프를 보면 쌓인 SDL 이벤트를 while로 다 처리한 다음에야 draw()랑 sync()를 부릅니다.

마우스를 움직이면 SDL이 MOUSEMOTION을 아주 빠르게 뱉습니다. 그게 큐에 쌓이면 while 한 바퀴에서 update()가 수십 번 불리는데, sync()는 그 뒤에 한 번뿐입니다.

튜토리얼에 이런 문장이 있습니다.

모든 렌더링 작업은 내부적으로 비동기적으로 실행되므로 적절한 시점에 Canvas::sync()를 호출하여 올바른 동기화를 보장해야 합니다.

동기화 없이 update()를 계속 던지면서 그 사이에 remove()로 Paint를 부수고 있었던 것 같습니다.

그리는 시점을 옮겨서 고쳤습니다. 입력 핸들러는 상태만 바꾸고 dirty 플래그를 세웁니다. 실제로 그리는 건 update()에서 프레임당 한 번입니다.

bool motion(tvg::Canvas* canvas, int32_t x, int32_t y) override
{
    if (!dragging) return false;
 
    dragEnd = {(float)x, (float)y};
    guideVisible = true;
    dirty = true;
    return false;
}

그 뒤로는 안 멈췄습니다. 드래그도 눈에 띄게 부드러워졌는데, 이벤트마다 씬을 새로 만들던 걸 안 해서 그런 것 같습니다.

조각 수가 생각과 다르게 늘었습니다

자를 때마다 조각 수를 찍어봤습니다.

cut 1, pieces 2
cut 2, pieces 4
cut 3, pieces 7
cut 4, pieces 10
cut 5, pieces 14
cut 6, pieces 18
cut 7, pieces 21
cut 8, pieces 27
cut 9, pieces 35
cut 10, pieces 40

한 덩어리를 계속 자른다면 n번째 선은 앞선 선들과 최대 n-1번 교차하니까 조각이 n개씩 늘어야 합니다. 2, 4, 7, 11, 16, 22, 29, 37, 46, 56이 되어야 하는데 당연하게도 4회째부터 어긋납니다.

조각이 벌어져 있어서 선 하나가 관통할 수 있는 조각 수가 줄어들고 항상 이상적인 조각을 낼수 없기 때문입니다. 흩어짐도 잘린 게 보이라고 넣은 건데, 결과적으로 난이도처럼 작동하고 있었습니다.

아직 모르는 것

조각이 수백, 수천 개가 돼도 버티는지 확인을 못 했습니다. 지금은 매 프레임 Shape를 전부 지우고 다시 만들어서 정지한 조각까지 재생성하고 있습니다. 조각마다 Shape를 유지한 채 변환만 갱신하는 게 맞을 것 같은데 아직 안 해봤습니다.
update()에서 elapsed로 직접 dt를 계산했는데, Example.h에 더 적절한 방법이 있는지 모르겠습니다.
오목한 도형으로 시작하면 반평면 클리핑이 깨집니다. 그땐 경계 추적이 필요할 텐데 작업량이 가늠이 안 됩니다.
아주 작은 조각은 안 만들도록 넓이 임계값을 뒀는데(60), 이 숫자는 그냥 감으로 정했습니다.

마치며

막힌 게 API 자체가 아니라 언제 그리느냐였다는 게 좀 의외였습니다. 즉시 모드처럼 생각하고 이벤트마다 그렸는데, 유지형 씬 그래프에서는 프레임 단위로 그리는 게 맞았습니다. 문서의 “비동기적으로 실행된다”는 문장을 읽을 때는 그냥 넘어갔는데, 겪고 나서 다시 보니 다르게 읽혔습니다.