• 삼각형을 그리기 위해 우리는 화면의 가장 위쪽 점부터 가장 아래쪽 점까지 가로선(→방향)을 한 줄씩 그어 내려갈 것
• 문제는 삼각형은 사각형처럼 반듯하지 않음
• 삼각형 중간에는 꺾이는 점$v_1$이 있는데, 이 점을 기준으로 기울기가 달라짐
• 따라서 코드를 작성할 때 이 부분(꺾이는 부분)을 처리하는 게 가장 까다로움

1. 스캔라인 알고리즘

• 복잡한 일반 삼각형을 다루기 쉽게 만들기 위해 모든 삼각형을 쪼개 두 가지 형태의 다루기 단순한 삼각형으로 쪼갠다.

위쪽: Flat-Bottom Triangle

• 위쪽 삼각형은 바닥이 평평한 삼각형이 됨
• $v_0$에서 아래로 내려갈 수록 양쪽으로 넓어짐

아래쪽: Flat-Top Triangle

• 아래쪽 삼각형은 윗면이 평평한 삼각형이 됨
• $v_2$방향으로 내려갈 수록 양쪽이 좁아짐

2. 전체 로직 요약

1. 정렬

   • 점 3개($v_0,v_1,v_2$)를 y좌표 기준으로 정렬

2. 분할

   • $v_1$의 높이에서 삼각형 분할
   • 이때 $v_0$와 $v_2$를 잇는 긴 변 위에서 $v_1$과 높이가 같은 새로운 점$M$을 찾아야 함

   

3. 그리기

   • 위쪽 삼각형 그리기 → $v_0$부터 $v_1$까지 루프를 돌며 가로선을 그음
   • 아래쪽 삼각형 그리기 → $v_1$부터 $v_2$까지 루프를 돌며 가로선을 그음

3. 사용한 공식

1) 선형 보간 공식

• 특정 $x$좌표가 주어졌을 때, 그에 맞는 $y$좌표를 찾는 공식