Open Graphics Library 9

1. Sutherland-Hodgman Polygon Clipping Algorithm

• 목적: 볼 수 있는 시야 영역(Viewport) 외부에 위치한 다각형의 일부를 잘라내는 알고리즘.
• 알고리즘 개요:
  1. 다각형의 각 변을 시야 영역의 경계선(Top, Bottom, Left, Right) 중 하나와 비교하여 클리핑.
  2. 한 경계선에서 클리핑 후, 결과를 다음 경계선으로 전달.
  3. 반복적으로 모든 경계를 처리하여 최종 다각형을 얻음.

입출력 규칙:

1. In-In (안쪽-안쪽):
   • 두 정점 모두 경계선 안쪽에 위치.
   • 다음 정점(vi+1)을 출력.
2. In-Out (안쪽-바깥쪽):
   • 첫 번째 정점은 안쪽, 두 번째 정점은 바깥쪽.
   • 경계와의 교차점(w)을 출력.
3. Out-Out (바깥쪽-바깥쪽):
   • 두 정점 모두 경계선 바깥.
   • 출력 없음.
4. Out-In (바깥쪽-안쪽):
   • 첫 번째 정점은 바깥쪽, 두 번째 정점은 안쪽.
   • 교차점(w)과 두 번째 정점(vi+1)을 출력.

예제:

• 입력 다각형: \(\{v0, v1, v2, v3\}\)
• 출력 다각형:
  1. v0v1 ⟹ v1 (In-In)
  2. v1v2 ⟹ v2 (In-In)
  3. v2v3 ⟹ w (In-Out)
  4. v3v0 ⟹ w’, v0 (Out-In)
• 최종 출력: \(\{v1, v2, w, w’, v0\}\)

---

2. 래스터화 (Rasterization)

• 정의: 기하학적 요소(선분, 삼각형 등)를 픽셀로 변환하여 화면에 표시.
• 과정:
  1. 입력: 기하학적 요소(예: 삼각형)의 정점 좌표.
  2. 출력: 프래그먼트(Fragment) 집합.
     • 각 프래그먼트는 픽셀 위치와 색상 정보를 포함.

---

3. 선분 래스터화

DDA 알고리즘 (Digital Differential Analyzer)

1. 선분의 시작점과 끝점을 기반으로 기울기를 계산: \[ m = \frac{\Delta y}{\Delta x} \]
2. \(x\)를 1씩 증가시키며 \(y\) 값을 계산:
   • \(y = y1 + m \cdot (x - x1)\)
   • 반올림(Rounding)을 사용하여 픽셀 선택.

DDA 알고리즘의 문제점:

1. 반올림 연산이 필요.
2. 부동소수점 연산이 포함되어 느림.
3. 오차가 누적될 수 있음.

---

4. 브레스넘 알고리즘 (Bresenham Algorithm)

• 목적: DDA 알고리즘의 단점을 개선한 정수 기반 알고리즘.
• 장점:
  1. DDA 알고리즘의 나눗셈 연산 -> 곱셈 연산으로
  2. DDA 알고리즘 float연산 및 반올림 -> 정수 연산

작동 원리:

1. 결정 변수(D)를 사용하여 픽셀 선택.
   • 초기 결정 변수: \[ D = 2 \cdot \Delta y - \Delta x \]
   • \(D > 0\): 대각선 방향 픽셀 선택.
   • \(D \leq 0\): 수평 방향 픽셀 선택.
2. \(D\) 값 업데이트:
   • 대각선 픽셀 선택 시: \[ D = D + 2 \cdot (\Delta y - \Delta x) \]
   • 수평 픽셀 선택 시: \[ D = D + 2 \cdot \Delta y \]

선분의 암묵적 표현 (Implicit Representation)

• 선분의 방정식: \[ f(x, y) = A \cdot x + B \cdot y + C = 0 \]
  • \(A = \Delta y\), \(B = -\Delta x\), \(C = \Delta x \cdot b\)
• 한 점 \((x, y)\)가 선분 위/아래에 있는지 판단:
  • \(f(x, y) > 0\): 선분 아래.
  • \(f(x, y) < 0\): 선분 위.

브레스넘 알고리즘 예제

선분: 시작점 \((0, 0)\), 끝점 \((6, 2)\)

1. 초기값:
   • \(D = 2 \cdot \Delta y - \Delta x = -2\)
   • \(incrE = 2 \cdot \Delta y = 4\)
   • \(incrNE = 2 \cdot (\Delta y - \Delta x) = -8\)
2. 첫 번째 픽셀:
   • \(D \leq 0\): 동쪽 픽셀 선택.
   • \(D = D + incrE = 2\)
3. 두 번째 픽셀:
   • \(D > 0\): 대각선 픽셀 선택.
   • \(D = D + incrNE = -6\)
4. 반복: \(x = x2\)까지 진행.

---