💙 4.1 점과 선

📄 점과 선의 정의 및 속성

점(point)

• 기하적 공간에서 좌표 (x,y)로 정의

• 속성은 크기(Size), 명암(Intensity) 또는 색상(Color), 모양(Shape) 등

  기하적 공간

  

  출력장치의 공간
  

선(Line)

• 시작점 (xa, yb)와 끝점 (xb, yb)의 절대좌표로 정의
• 또는 시작점 좌표 (x,y)와 좌표의 증가값 (△x,△y)의 상대좌표로 정의
• 속성은 선의 유형(Line Type), 굵기(Width), 색상, 선끝 모양(Line Cap) 등

다중선(Polyline)

• 시작점 (x1, y1)부터 마지막 n번 째 점 (xn, yn)까지의 절대좌표로 정의
• 또는 시작점 (x1, y1)과 각 좌표의 증가값들 (△x1, △y1)...(△xn-1, △yn-1)로 정의
• 선의 속성 이외에 추가로 선 이음(Line Join) 등의 속성

---

📄 DDA 선 그리기 알고리즘

선의 양끝 좌표로부터 래스터 출력장치로 변환하는 가장 기본적인 알고리즘

DDA(Digital Differential Analyzer) 알고리즘의 개요

• 선의 공식을 y = mx + c 의 형태로 계산

• 0≤m≤1 인 경우, x를 1씩 증가시키면 y값은 m만큼 증가

• m > 1 인 경우, 그 반대로 y를 매번 1씩 증가시키면 x값이 1/m만큼씩 증가

• 기울기 m이 음수인 경우, x 증가에 따라 y값이 증가대신 감소

  

DDA 선 그리기 알고리즘

1) 초기화를 한다.

△x = xb - xa , △y = yb - ya ,
m = △y / △x
x1 = xa , y1 = ya

2) 기울기에 m의 값에 따라 다음계산을 수행한다.

2a) 기울기 |m|≤1인 경우,
매번 k+1번 째 점에서 (1≤k≤Δx)

    xk+1 = xk + 1
    yk+1 = yk + m
    yk+1의 래스터 좌표 = Round(yk+1)

2b) 2b) 기울기 |m|>1 인 경우,
매번 k+1번 째 점에서 (1≤k≤△y)

    yk+1 = yk + 1
    xk+1 = xk + 1/m
    xk+1의 래스터 좌표 = Round(xk+1)

DDA 알고리즘의 특징

• 곱하기가 없이 소수점(Floating-point) 더하기 연산만을 반복
• 매번 정수좌표를 구할 때마다 오차가 축적

---

📄 Bresenham 선 그리기 알고리즘

소수점 계산 없이 정수의 더하기 연산과 시프트 연산만으로 처리

Bresenham 알고리즘의 기본 개념

• 0≤m≤1일 때, (xk, yk)의 다음 점은
  (xk+1, yk) 또는 (xk+1, yk+1)

• k+1번째 점에서의 차이값으로 판별식을 계산

  pk+1 = pk + 2(△x - △y)
  또는, pk+1 = pk + 2△y

  초기값 p1 = 2△y - 2△x

• 매번 판별식 pk+1을 계산할 때 정수 값인
  상수 C1 또는 C2를 더한다.

• C1 = 2(△y - △x) 또는 C2 = 2△y 의 계산은 처음에 한번만 한다.

Bresenham 선 그리기 알고리즘 (기울기 0 ≤ m ≤ 1 로 가정)

1) 초기값을 구한다.

     C1 = 2△y ,   C2 = 2(△y - △x) ,  p1 = 2△y - △x

2) d1 - d2 의 판별식 pk 값에 따라 다음 점의 위치를 구한다. (1≤k≤△x)

• i) pk < 0 인 경우
  다음 픽셀 점은 (xk+1, yk) 이며, pk+1 = pk + C1 이다
• ii) pk ≥ 0 인 경우
  다음 픽셀 점은 (xk+1, yk+1) 이고, pk+1 = pk + C2 이다.

---

💙 4.2 원, 타원 및 기타 곡선

📄 원 그리기

극 좌표계(Polar Coordinate)를 이용하는 방법

x2 + y2 = r2 일 때 x = r cosθ, y = r sinθ
(x-xc)2 + (y-yc)2 = r2 일 때, x = xc + r cosθ, y = yc + r sinθ

• 매개변수 θ의 일정 간격으로 원주 상의 점을 구한 후 선분으로 연결
• 90°≥ θ ≥ 45°인 경우에만 구하고, 나머지는 원의 8방향 대칭을 이용

Bresenham 원 그리기 알고리즘의 개념

• 제곱근이나 삼각함수 등의 계산이 없이 정수 연산만으로 처리

• 한 픽셀의 다음은 반드시 오른쪽 또는 오른쪽 바로 아래 점

  즉, k번 째 점 (xk,yk)의 다음은 (xk + 1, yk) 또는 (xk + 1, yk - 1)
  

Bresenham 원 그리기 알고리즘 (중심이 xc, yc 이고 반지름이 r 인 경우)

1) 초기화를 한다.

x1 = xc , y1 = yc + r , p1 = 3 - 2r 로 계산한다.

2) xk < yk 인 동안 다음 계산을 반복한다.

k번 째 점에서,

a) pk < 0 인 경우 다음 점은 (xk + 1, yk) 이며
pk+1 = pk + 4 xk + 6 으로 계산하고,

b) pk ≥ 0 인 경우 다음 점은 (xk + 1, yk - 1) 이며
pk+1 = pk + 4 (xk-yk) + 10 으로 계산한다.

📄 타원 그리기

극 좌표계 이용

(x - xc)2 / rx2 + (y - yc)2 / ry2 = 1일 때 x = xc + rx cos θ, y = yc + ry sinθ

90°≥ θ ≥ 0°에 대해 적당한 간격의 선분으로 연결, 나머지는 4방향 대칭으로 처리

📄 기타 곡선 그리기

함수 y = f(x) 로 표현 가능한 곡선

• 적당한 간격의 x값에 해당하는 곡선 상의 점을 구한 후 선분으로 연결

• 삼각(Sine) 함수, 지수(Exponential) 함수, 다항식(Polynomial) 함수, 스플라인(Spline) 함수, 등

---

💙 4.3 영역 및 다각형 채우기

📄 영역의 특성과 채우기 방식

이웃한(Adjacent 또는 Connected) 픽셀간의 연결 방식

• 4방향연결(4-Connected) 방식
• 8방향연결(8-Connected) 방식
  ex) 예) 4방향 연결방식의 경우 영역은 2개, 8방향 연결방식의 경우 영역은 1개

래스터 영역의 경계 픽셀과 내부 픽셀은 연결방식을 다르게,

• 경계 8방향 연결 ⇒ 내부는 반드시 4방향 연결 채우기
• 경계 4방향 연결 ⇒ 일반적으로 내부는 8방향 연결 채우기

일반적인 래스터 방식의 출력장치

• Bresenham 선 그리기 알고리즘은 8방향연결 방식
• 영역채우기 알고리즘은 내부 영역을 4방향연결 방식으로 채우기

시드채우기 방식

• 그림이 래스터 버퍼에 그려진 후 이미지에서 영역의 채우기를 실행
• 영역 내부의 한 픽셀이 시드로 주어지고 이 픽셀에서부터 채워나간다
• 주로 페인팅 소프트웨어나 대화식 이미지 처리 프로그램에서 사용

다각형 주사변환 방식

• 매 주사선 별로 다각형의 내부 구간을 판단하여 해당 픽셀을 칠한다.
• 주사선채우기(Scanline Fill)라고도 한다.
• 주로 벡터방식의 그리기 소프트웨어에서 사용

📄 시드채우기(Seed Fill) 방식

내부 영역에 대한 판단 및 채우기 방식

• 내부로 정의된(Interior-defined) 영역 채우기 => 범람채우기(Flood Fill)
• 경계로 정의된(Boundary-defined) 영역 채우기 => 경계채우기(Boundary Fill)
  

범람채우기(Flood Fill) 알고리즘

경계채우기(Boundary Fill) 알고리즘

📄 다각형 내부의 판단 규칙

홀짝 규칙(Even-Odd Rule)

주사선 별로 에지가 홀수 번째 교차하면 내부가, 짝수 번째 교차하면 외부가시작된다고 판단

접기횟수 규칙(Non-zero Winding Rule)

• 주사선 별로 아래쪽 에지와 교차하면 접기횟수를 1 증가, 위쪽 방향의 에지와 교차하면 1 감소

• 이 때 접기 횟수가 0보다 큰 구간은 다각형의 내부영역으로 판단
  
  

  예) (a) 교차횟수가 1, 3인 부분이 내부
  (b위) 접기횟수가 1인 부분이 내부 => 가운데가 빈 다각형
  (b아래) 접기횟수가 1, 2, 1 인 부분이 내부 => 전체가 내부

📄 다각형 주사변환 방식

Y-X 다각형 주사선 알고리즘의 기본 개념

• 매 주사선에서 교차되는 에지들의 목록을 유지하고 갱신하기 위하여,
  활성화된 에지의 목록은 AEL(Active Edge List),
  다각형의 전체 에지 목록은 EL(Edge List)
• 우선, 다각형의 전체 에지를 시작점의 Y좌표값 순서로 정렬하여 EL을 구성
• 매 주사선에서 새로 교차하는 에지를 EL에서 꺼내어 AEL로 옮겨 관리
  그리기가 완료된 AEL 내의 에지를 찾아서 제거
  EL에서 해당 주사선과 교차되는 새로운 에지를 찾으면 AEL로 이동
• 해당 주사선과 각 에지와 교차점을 2개씩 짝을 지어 사이를 채운다
  홀짝 규칙 : X값 순으로 정렬 후 단순히 순서대로 짝을 만들어 채우기
  접기횟수 규칙 : X 정렬 후 아래쪽 방향과 위쪽 방향의 교차점이 짝을이루어 채우기
• AEL과 EL 각각에 처리해야할 에지가 없으면 종료

알고리즘의 예

Y-X 다각형 주사선 알고리즘의 특징

• Y-X 알고리즘 : Y값 순서로 전체 에지 정렬, 교차점은 X좌표값 순서로 정렬
• 효율성 : 에지의 목록에 대한 부분적인 일관성(Coherence)으로 발생

Y-X 다각형 주사선 알고리즘

1) 초기화를 한다.
각 에지들을 Y좌표의 최소값 순서로 정렬하여 Edge List(EL)를 구성한다.
2) 매 주사선 yk에서 다음을 수행한다.

2a) AEL을 갱신한다.
AEL에서 yb < yk 인 에지를 삭제하고, // 완료된 에지 삭제
EL에서 ya = yk 인 에지를 AEL로 이동한다. // 새로운 에지 삽입
단, AEL 과 EL에 더 이상의 에지가 없으면 종료한다.

2b) AEL에서 각 에지의 교차점을 계산한다.
2c) 교차점 x값을 정렬한 후 각 쌍을 결정하여 그 사이를 채운다.

---

💙 4.4 문자의 표현

📄 폰트의 종류

래스터 폰트(Raster Font 또는 Bitmap Font)

• 글자 크기에 해당하는 사각형 그리드의 픽셀에 1과 0으로 표현
• 메모리 내에서 비트맵에 대한 연산으로 처리하므로 출력 속도가 매우 빠르다
• 제작은 용이하나 확대하면 계단현상(Aliasing)
• 글자의 확대, 회전, 밀림 등 기하변환은 매우 어려우며 변환시 출력 품질 저하

벡터 폰트(Vector Font 또는 Outline Font)

• 글자의 윤곽선을 여러 부분으로 나누어 직선, 원호, 곡선 등으로 표현하고, 이들에 대한 제어점을 저장
• MS 윈도우의 TrueType 폰트는 2차 B-스플라인(B-Spline) 곡선을 사용
• PostScript의 Type1 폰트는 3차 베지어(Bezier) 곡선을 사용

벡터 폰트의 처리과정 :

1) 제어점의 좌표들에 대해 축소하거나 회전하는 등 기하변환을 수행
2) 윤곽선의 곡선 부분을 선 조각으로 나누어 다각형 형태로 표현
3) 다각형 주사선 알고리즘을 이용하여 글자의 내부영역 채우기를 수행

벡터 폰트의 특징

• 확대 또는 축소를 하여도 출력 품질이 동일하게 유지
• 회전 등의 기하변환이 용이, 단, 기하변환을 위한 계산 시간 증가

📄 문자와 텍스트의 속성

문자(Character)의 주요 속성

• 폰트, 색상, 크기 (폭과 높이), 스타일 (굵은체, 이탤릭, 밑줄 등), ...

텍스트(Text 또는 String)의 속성

• 세우기 방향( Orientation) : Character Up 벡터로 표현
• 쓰기 방향(Direction) : Text Path Direction으로 표현
• 정렬(Alignment), 행간격, 문자간격 등

---

💙 4.5 앤티앨리어싱

📄 래스터 출력의 문제점

앨리어싱(Aliasing)

• 래스터 출력장치에서 디지털화 과정의 샘플링 오차로 인한 왜곡현상
• 사선의 굵기가 수평선의 굵기와 다르게 보이는 현상
• 사선이나 곡선부분에 나타나는 계단현상
  

앤티앨리어싱(Antialiasing)

• 컬러 또는 회색조(Gray) 출력 장치에서 경계가 부드럽게 보이도록 하는 기법
• 물체의 경계 픽셀에서 물체와 배경의 색상을 혼합해서 그린다.
• 선 그리기, 다각형 채우기, 문자 생성 등에 적용이 가능

📄 앤티앨리어싱 기법

수퍼샘플링(Super Sampling) 기법

• 하나의 픽셀 영역을 여러 개로 분할하는 수퍼샘플링 과정을 적용하고, 이를 원래의 해상도로 환원할 때 픽셀의 명암 값을 계산
• 픽셀의 영역에 포함되는 고해상도 픽셀의 개수에 비례하여 명암 값을 계산
  
  
  

영역 샘플링(Area Sampling) 기법

• Bresenham 선그리기 알고리즘을 응용하여 Pitteway와 Watkinson이 제안
• 얼마만큼 다각형의 내부영역에 포함되는지 포함된 면적비율을 계산

  y1 = m (xk - 0.5) + c , y2 = m (xk + 0.5) + c

  면적 = { (y1 - (yk - 0.5)) + (y2 - (yk - 0.5)) } / 2
  = m xk + c - yk + 0.5

  

---

💙 4.6 색상의 표현

📄 RGB 컬러 표현방식

RGB 컬러 표현방식

• 프레임버퍼 내의 R평면, G평면, B평면에 각 픽셀의 해당 값이 저장

표현 가능한 색상의 개수는

• 픽셀의 깊이(Pixel Depth)와 프레임버퍼의 메모리 크기에 의해 결정
• 픽셀의 깊이가 k 비트이면 2k 가지의 색상 표현이 가능

픽셀의 깊이에 따라 표현이 가능한 색상의 개수

알파채널/알파평면(Alpha Plane)

• RGBA 컬러 표현방식
• 주로 투명 및 불투명, 안개효과 등을 표현하거나, 은면제거에 사용

프레임 버퍼(Frame Buffer)의 크기

• 필요한 메모리 크기는 화면의 해상도와 픽셀 깊이에 비례

예) 1024 x 768 해상도에 32비트 깊이(4바이트)인 경우,
1024 x 768 x 4 = 3M 바이트가 필요
1280 x 1024 해상도에 32비트 깊이(4바이트)인 경우,
1280 x 1024 x 4 = 5M 바이트가 필요

📄 인덱스컬러 표현방식

인덱스컬러 방식

• 사용 가능한 색상의 수가 제한될 때 사용자가 색상을 선택하여 사용
• 비슷한 색상 중에서 선택하면 원래 그림에 훨씬 가까운 색상으로 표현 가능

색상보기표(CLUT: Color Look-Up Table)

• 색상 팔레트의 개념으로 사용하려는 색상을 저장하는 표의 역할
• 프레임버퍼에는 색상의 값이 아니라 색상보기표의 번호(Index)를 기록
• 팔레트를 바꾸면 프레임 버퍼 내 그림의 색상도 따라서 바뀐다.

색상보기표의 크기와 사용 가능한 색상의 개수

• 색상보기표의 크기가 256이고 각 RGB 색상의 크기가 8비트 인 경우, 프레임버퍼의 깊이는 8비트이며 표현 가능한 색상 224개(1600만개) 중 동시에 256개가 사용 가능
• 이 때 각 픽셀에는 24비트 대신에 8비트만 사용하였으므로 프레임버퍼에 필요한 메모리는 1/3로 축소

---