04 — 2차원 그래픽스의 기본

출처: SSU 컴퓨터 그래픽스 슬라이드 — SSU_CG_04_2차원그래픽스의기본.pdf 주차: 4주차

수학적인 점·선·면을 이산적인 픽셀 로 변환하는 래스터화(Scan Conversion) 알고리즘, 그 위에 올라가는 채우기·폰트·앤티앨리어싱·색상 표현까지 한 번에 다룹니다.

1. 점과 선

1.1 점과 선의 정의 및 속성

• 점 (Point): 기하 공간에서 좌표 로 정의. 속성은 크기(Size) · 명암(Intensity) / 색상(Color) · 모양(Shape) 등.
• 선 (Line):
  • 시작점 와 끝점 의 절대좌표 로 정의
  • 또는 시작점과 좌표의 증가값 (Δx, Δy) 인 상대좌표 로 정의
  • 속성: 선 유형(Line Type), 굵기(Width), 색상, 선끝 모양(Line Cap) 등
• 다중선 (Polyline): 시작점부터 마지막 점까지의 좌표열. 선 속성에 추가로 선 이음(Line Join) 속성.

1.2 DDA 선 그리기 알고리즘

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

개요

선의 공식 를 기반으로, 기울기 에 따라 증분을 결정합니다.

• : x 를 1씩 증가 → y 는 m 만큼 증가.
• : y 를 1씩 증가 → x 가 만큼 증가.
• 기울기가 음수: x 증가에 따라 y 는 증가 대신 감소.

인 경우에 x를 기준축으로 그리면 픽셀이 듬성듬성 찍히는 오류 가 발생 — 그래서 축 전환이 필요합니다.

알고리즘

1. 초기화:

1. 인 경우 ():

1. 인 경우 ():

특징

• 곱하기 없이 부동소수(Floating-point) 더하기만 반복.
• 매번 정수 좌표를 구할 때마다 Round() 에 의한 오차 축적.

1.3 Bresenham 선 그리기 알고리즘 ⭐️

부동소수 계산 없이 정수 더하기·시프트만으로 선을 그리는 알고리즘. DDA의 누적 오차 문제를 해결.

상황 설정

(즉 가로가 세로보다 길거나 같은 선) 이라고 가정. 여기서 (끝점 − 시작점). 예: 이면 .

현재 픽셀 에서 다음에 찍을 픽셀은 둘 중 하나:

• 오른쪽 — y는 유지
• 대각선 오른쪽 위 — y도 한 칸 올림

둘 중 실제 직선에 더 가까운 쪽 을 골라야 합니다. x는 매 단계 무조건 1씩 증가 — 결정해야 할 건 오로지 "y를 올릴까 말까".

판별식 의 기하학적 의미

두 후보 픽셀의 중간 높이 와 실제 직선의 차이를 재면 됩니다.

• 실제 직선이 중간보다 위 라면 → 대각선 픽셀이 더 가까움 → y 올려야
• 실제 직선이 중간보다 아래 라면 → 오른쪽 픽셀이 더 가까움 → y 유지

이 "위냐 아래냐" 판정을 소수 없이 정수로만 해낸 것이 . 분수를 배로 곱해 없애고 남긴 부호 판별용 정수:

즉 는 판별값(스칼라), 는 현재 픽셀의 가로 좌표. 서로 다른 양이지만 같은 k 인덱스를 쓸 뿐입니다. 는 k 단계에서 k+1 이 되고, 는 업데이트 공식에 따라 새 숫자가 됩니다.

업데이트 공식 — 곱셈 없이 덧셈으로

을 새로 계산하지 않고, 에서 상수만 더해서 얻습니다:

• (중간보다 아래) → 다음 픽셀
• (중간보다 위) → 다음 픽셀

는 루프 시작 전에 한 번만 계산. 이후 매 단계는 정수 덧셈 하나.

초기값

직선이 에서 시작하므로 첫 중간점 와의 차이를 전개하면:

워크샵: (1, 1) → (8, 5)

위 시뮬레이터의 기본 설정과 동일. Step 을 눌러 비교해보세요.

, 초기 .

첫 줄을 읽는 법: "현재 (1,1) 이고 p_1=1 이다. 조건 ≥ 0 이므로 y도 올려 (2,2) 로 이동. 그 과정에서 p 는 1 + C_2 = −5 로 업데이트."

2. 원, 타원 및 기타 곡선

2.1 원 그리기

극좌표계 방법

원의 방정식 , 일반적으로 .

매개변수 의 일정 간격으로 점을 구해 선분으로 연결. 만 계산 하고 나머지는 8방향 대칭 으로 처리.

Bresenham 원 그리기 알고리즘 ⭐️

제곱근·삼각함수 없이 정수 연산만으로 처리. 한 픽셀 의 다음은 반드시 또는 둘 중 하나 (원이 오른쪽 바깥으로 내려가는 방향).

알고리즘 (중심 , 반지름 r)

1. 초기화: .
2. 동안 반복 (1/8 구간 종료 조건):
   • : 다음 점 ,
   • : 다음 점 ,

2.2 타원 그리기

타원 방정식 →

에 대해서만 적당한 간격으로 선분 연결, 나머지는 4방향 대칭 으로 처리.

2.3 기타 곡선 그리기 (Bezier 등)

함수 형태로 표현 가능한 곡선은 적당한 간격의 x 값에서 점을 구해 선분으로 연결. Sine, Exponential, Polynomial, Spline 함수 등.

베지어 곡선은 제어점 사이를 일정 비율()로 내분하며 점을 찍어나가는 De Casteljau 알고리즘 으로 생성됩니다.

3. 영역 및 다각형 채우기

3.1 영역의 특성과 연결 방식

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

• 4방향 연결 (4-Connected): 상·하·좌·우.
• 8방향 연결 (8-Connected): 대각선 포함 8방향.

경계와 내부의 조합 규칙 ⭐️

경계와 내부는 서로 다른 연결 방식을 사용 해야 누수가 없습니다.

일반적인 래스터 시스템: Bresenham 선은 8방향 연결 방식으로 찍히므로, 영역 채우기 알고리즘은 4방향 연결 로 내부를 채웁니다.

3.2 채우기의 두 접근

• 시드채우기 방식: 이미지가 이미 그려진 후, 영역 내부의 한 픽셀(시드) 에서 번져가며 채움. 페인팅 소프트웨어 · 대화식 이미지 처리 에서 주로 사용.
• 다각형 주사변환 방식: 다각형의 벡터 정보(에지)를 받아 주사선(Scanline) 단위로 내부를 판정해 채움. 벡터 방식 그리기 소프트웨어 에서 주로 사용.

3.3 시드 채우기 (Seed Fill)

내부 영역의 정의 방식에 따라 두 가지:

범람채우기 (Flood Fill) — 내부로 정의된 영역

void flood_fill(int x, int y) {           // 시드 (x,y) 에서 시작
  if (read_pixel(x, y) == bgColor) {       // 현재 픽셀이 배경색 'bgColor' 이면
    write_pixel(x, y, fillColor);          // 채우기 색 'fillColor' 로 칠한다.
    flood_fill(x+1, y);                    // 오른쪽으로 반복
    flood_fill(x-1, y);                    // 왼쪽으로 반복
    flood_fill(x, y+1);                    // 아래로 반복
    flood_fill(x, y-1);                    // 위로 반복
  }
}

경계채우기 (Boundary Fill) — 경계로 정의된 영역

void boundary_fill(int x, int y) {
  int current = read_pixel(x, y);
  if ((current != bdColor) && (current != fillColor)) {
    write_pixel(x, y, fillColor);          // 내부를 채우기 색 'fillColor' 로 칠한다.
    boundary_fill(x+1, y);                 // 오른쪽으로 반복
    boundary_fill(x-1, y);
    boundary_fill(x, y+1);
    boundary_fill(x, y-1);
  }
}

차이점: Flood Fill 은 "같은 색" 기준, Boundary Fill 은 "경계색에 도달할 때까지" 채웁니다.

3.4 다각형 내부 판단 규칙 ⭐️

홀짝 규칙 (Even-Odd Rule)

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

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

주사선 별로:

• 아래쪽 방향 에지와 교차하면 접기 횟수 +1
• 위쪽 방향 에지와 교차하면 -1
• 누적이 0이 아니면 내부 로 판단

차이: 자기 교차(self-intersecting) 다각형에서 결과가 달라집니다. 홀짝 규칙은 가운데를 "구멍"으로, 접기횟수 규칙은 "내부" 로 취급.

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

기본 개념

• EL (Edge List): 다각형의 전체 에지 목록. 시작점 Y좌표 최소값 순으로 정렬.
• AEL (Active Edge List): 현재 주사선과 교차하는 활성 에지 목록.
• 매 주사선에서 EL 에서 새로 교차하는 에지를 꺼내 AEL 로 이동, 그리기 완료된 에지는 제거.
• 해당 주사선과 각 에지의 교차점을 2개씩 짝을 지어 사이를 채움.
  • 홀짝 규칙: X값 순으로 정렬 후 순서대로 짝.
  • 접기횟수 규칙: X 정렬 후 아래쪽/위쪽 방향 교차점이 짝을 이뤄 채움.

알고리즘

1. 초기화: 각 에지들을 Y좌표 최소값 순으로 정렬하여 EL 구성.
2. 매 주사선 에서:
   • (a) AEL 갱신:
     • AEL 에서 인 에지 삭제 (완료)
     • EL 에서 인 에지를 AEL 로 이동 (삽입)
     • 두 리스트에 에지가 없으면 종료.
   • (b) 교차점 계산: AEL 의 각 에지와 주사선의 교차점 X 좌표. 증분 최적화: .
   • (c) 교차점 X 정렬 후 각 쌍 사이를 채운다.

특징: 에지 목록의 부분적 일관성(Coherence) 을 활용해 효율이 높습니다.

4. 문자의 표현

4.1 폰트의 종류

래스터 폰트 (Raster Font / Bitmap Font)

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

벡터 폰트 (Vector Font / Outline Font)

• 글자의 윤곽선 을 직선·원호·곡선으로 나누어 표현하고 제어점 을 저장.
• MS 윈도우의 TrueType 폰트 = 2차 B-스플라인(B-Spline) 곡선 사용.
• PostScript 의 Type1 폰트 = 3차 베지어(Bezier) 곡선 사용.

벡터 폰트의 처리 과정

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

특징: 확대/축소해도 출력 품질이 동일 하게 유지. 기하변환이 쉬운 대신 계산 시간 증가.

4.2 문자와 텍스트의 속성

• 문자(Character) 속성: 폰트, 색상, 크기(폭·높이), 스타일(굵은체·이탤릭·밑줄) 등.
• 텍스트(Text / String) 속성:
  • 세우기 방향 (Orientation) — Character Up 벡터로 표현.
  • 쓰기 방향 (Direction) — Text Path Direction 으로 표현.
  • 정렬 (Alignment), 행간격, 문자간격.

5. 앤티앨리어싱 (Antialiasing)

5.1 래스터 출력의 문제점: 앨리어싱 (Aliasing)

래스터 출력장치에서 디지털화 과정의 샘플링 오차로 인한 왜곡 현상.

• 사선의 굵기가 수평선의 굵기와 다르게 보이는 현상.
• 사선이나 곡선 부분에 나타나는 계단 현상 (Jaggies).

5.2 앤티앨리어싱의 원리

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

5.3 수퍼샘플링 (Super Sampling)

하나의 픽셀 영역을 여러 개로 분할 샘플링 한 뒤, 원래 해상도로 환원할 때 픽셀의 명암값을 서브샘플 개수에 비례하여 계산.

5.4 영역 샘플링 (Area Sampling) — Pitteway & Watkinson

Bresenham 선그리기 알고리즘을 응용. 픽셀이 다각형 내부영역에 얼마나 포함되는지 면적 비율 을 수식으로 계산.

직선 와 픽셀 중심 의 양 끝 x 좌표에서:

픽셀 내부 면적:

이 면적에 비례하는 명암으로 픽셀을 칠합니다.

6. 색상의 표현

6.1 RGB 컬러 표현 방식

프레임버퍼 내의 R평면, G평면, B평면 에 각 픽셀의 해당 값을 저장. 표현 가능한 색상 수는 픽셀 깊이(Pixel Depth) 와 프레임버퍼 메모리 크기에 의해 결정.

픽셀 깊이별 색상 표 ⭐️

6.2 알파 채널 (Alpha Plane)

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

6.3 프레임 버퍼 크기 계산

필요한 메모리 = 해상도 × 픽셀 깊이.

• 예: 1024 × 768 해상도에 32비트(4바이트) →
• 예: 1280 × 1024 해상도에 32비트(4바이트) →

6.4 인덱스 컬러 방식 (CLUT)

인덱스컬러 개념

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

CLUT (Color Look-Up Table)

• 색상 팔레트 의 개념으로 사용하려는 색상을 저장하는 표.
• 프레임버퍼에는 색상 값이 아니라 CLUT 의 번호(Index) 를 기록.
• 팔레트를 바꾸면 프레임 버퍼 내 그림의 색상도 따라서 바뀜 → 애니메이션·테마 전환에 활용.

메모리 절약

예: CLUT 크기 256, 각 RGB 8비트 → 프레임버퍼 깊이는 8비트. 표현 가능한 색 중 동시에 256개 사용 가능. 24비트 직접 저장 대비 메모리 1/3 로 축소.

📝 Knowledge Check: 2D 기본 종합

🔗 다음 학습

• 이전: 02 — 컴퓨터 그래픽스 시스템 (2주차)
• 다음: 05 — 2D 변환과 클리핑 (5주차) — 픽셀을 그렸으니 이제 변환하고 잘라낼 차례.