컴퓨터 구조 9주차 딥다이브
이번주꺼는 진짜 진짜 안읽히네요 ㅠㅠ 그냥 몇 개 주제만 정리해봤어요
주제 1. "정수 덧셈만으로 직선을 그린다" – 브레슨햄 알고리즘의 진짜 가치
✅ 목적
데카르트 좌표계의 실수 기반 직선을 이산적인 픽셀 공간(스크린 좌표계)에 정수 연산만으로 근사해서 표현하기 위한 알고리즘입니다.
실수 계산은 CPU 자원을 많이 소모하므로 효율이 떨어집니다.
정수만으로 표현하면 속도가 빠르고, 임베디드나 저사양 환경에서 특히 유리합니다.
1) 왜 부동소수점 대신 정수 덧셈을 쓸까?
정수 덧셈은 단순히 ‘빠르다’기보다, 더 ‘예측 가능하고, 에너지 효율적이며, 하드웨어 친화적’입니다.
✅ CPU 구조 관점:
정수 연산 유닛(Integer Unit)은 대부분의 프로세서에서 가장 기본적이고 빠른 연산 블록입니다.
반면, 부동소수점 연산은 **별도의 FPU(Floating Point Unit)**에서 처리되며, 연산 명령 하나에 더 많은 클럭 주기와 에너지를 사용합니다.
✅ 예측 가능성 측면:
정수 덧셈은 항상 일정한 시간에 끝나므로, 실시간 시스템이나 게임 루프에서 타이밍 예측이 훨씬 용이합니다.
✅ 캐시 및 전력 관리:
부동소수점 계산은 더 많은 레지스터를 요구하며, 일부 모바일/임베디드 CPU에서는 연산 자체가 비활성화되어 있기도 합니다.
📌 특히 1960년대 IBM 메인프레임이나 1980년대 초기 가정용 컴퓨터(애플 II, 코모도어 64 등)에서는 부동소수점 연산이 아예 없거나 매우 느렸기 때문에, 정수 기반 알고리즘은 하드웨어 제약에 꼭 맞는 해법이었습니다.
2) 브레슨햄 알고리즘의 핵심 철학: "계산을 하지 말고 차이를 더하라"
브레슨햄은 다음의 ‘깨달음’을 이용했습니다:
직선은 단순히 점의 나열이 아니라, 변화의 누적이다.
각 점마다 (x, y) 위치를 직접 계산하는 대신, 변화량만 추적하면 된다.
예:
y = y + m같은 계산에서 m이 부동소수점이면 느리고 정밀도 오류도 있지만, ‘기울기 대신 누적 판단 변수 d’를 사용하면 정수만으로 동작 가능!
3) 어떤 방식으로 최적화되나?
브레슨햄 알고리즘에서는 다음과 같은 정수 최적화 기법이 사용됩니다:
Decision Variable d
각 픽셀마다 y를 증가시킬지 판단하는 기준
Δx, Δy
시작점과 끝점 사이의 x, y 변화량
2Δy, 2Δx
정수 계산을 위해 분수를 없애고 두 배로 사용
분기(branch) 최소화
조건문과 비교를 최소화해 CPU 파이프라인 효율 증가
4) 왜 특허가 안 걸린 게 중요했나?
IBM 발명 사무소는 당시 “이건 너무 사소한 발명”이라며 특허 출원을 거절했지만, 이는 오히려 오픈소스 문화에 큰 선물이 됐습니다.
이후 거의 모든 그래픽스 시스템에서 이 알고리즘을 자유롭게 도입
Unix, X Window System, OpenGL 초기 구현 등에도 반영
심지어 마이크로컨트롤러 펌웨어와 프린터 내장 OS에서도 사용
📌 특허가 있었다면 컴퓨터 그래픽의 대중화는 10년 이상 늦어졌을 수 있습니다.
5) 오늘날에도 유효한가?
✔ 여전히 유효합니다! 특히 다음과 같은 곳에서 널리 사용됩니다:
저전력 MCU (예: Arduino, STM32)에서의 디스플레이 드라이버
2D 게임에서의 라인 렌더링
터미널 기반 UI에서 라인 그리기
💡 GPU에서는 더 고급 알고리즘(Super Sampling, Anti-Aliasing)이 적용되지만, Bresenham 알고리즘은 여전히 하위 계층에서 기본 도구로 사용됩니다.
6) 좌표계의 차이
값의 성질
연속 (Real Number)
이산 (Integer Grid)
방향
x: → / y: ↑
x: → / y: ↓
좌표
실수 (벡터)
정수 (픽셀)
7) 브레슨햄 알고리즘 핵심 아이디어
1. 선분의 두 점이 주어진다 → 픽셀 단위로 직선을 그린다
두 픽셀 사이에 선이 정확히 걸칠 수는 없으므로 가까운 픽셀을 선택해야 함.
이때 기준은: “다음으로 이동할 x+1 지점에서 y를 유지할지, y를 바꿔야 할지?”
2. 실수 기반 방정식을 정수 연산으로 바꿔보기
3. ✨ 부동소수점 제거 → 정수로 만드는 과정
다음처럼 전개됩니다:
원래 부등식을 Δx로 양변 곱함
이항해서 한쪽으로 모음
전체에 2를 곱해 정수로 만듬
결과적으로 나온 식:
2Δy−Δx<02Δy - Δx < 0
이게 바로 브레슨햄의 초기 판별식입니다. 이후 반복하면서 y를 언제 증가시킬지, 안 할지를 결정하는 데 이 식을 기준으로 삼습니다.
📈 픽셀 중간 기준으로 더 자세히 보면?
중간 기준: 어떤 픽셀 두 개 사이에 선이 걸칠 경우, 중간선을 기준으로 어떤 픽셀을 선택할지 결정합니다.
이때 사용되는 것이 결정 변수(decision variable) d입니다.
📊 브레슨햄 알고리즘 정리
입력
두 점 (x₀, y₀) ~ (x₁, y₁)
목표
각 x에 대응하는 y를 정수로 구해 가장 가까운 픽셀에 점 찍기
핵심 변수
d: 결정 변수, dx, dy: x/y 변화량
핵심 연산
정수 덧셈/뺄셈만으로 다음 픽셀 결정
브레슨햄 알고리즘은 실수 기반의 직선을 픽셀 단위로 정수 연산만을 통해 효율적으로 근사하는 알고리즘입니다. 중간값을 기준으로 다음 픽셀의 위치를 결정하며, 부동소수점 연산 없이도 거의 완벽한 직선을 표현할 수 있습니다.
📌 확장 주제: ‘브레슨햄의 알고리즘을 이용한 원형, 타원 그리기’ 원과 타원도 선처럼 정수 덧셈으로 그릴 수 있을까요?
답은 ‘예’입니다.
그리고 그 방법은 놀랍게도 선을 그릴 때의 아이디어를 그대로 확장한 것이죠.
주제 2. "타원도 정수 덧셈으로?" – 브레슨햄 타원 알고리즘의 확장
1) 브레슨햄 알고리즘, 타원에도 적용할 수 있을까?
네, 가능합니다. 브레슨햄 선 그리기 알고리즘은 "점진적 판단"의 철학을 갖고 있습니다. 즉,
"지금 이 시점에서 세 후보 중 어느 점이 수학적으로 이상적인 경로에 가장 가까운가?"
이 아이디어는 직선뿐 아니라 곡선에도 자연스럽게 확장됩니다. 특히, 중심이 원점이고 x축과 y축과 평행한 타원이라면 계산 복잡도 없이도 구현할 수 있습니다.
2) 타원의 방정식, 정수 계산으로 바꿔보기
일반적인 타원의 식:
Ax^2 + By^2 - AB = 0 \quad \text{(A = b², B = a²)}
이 식을 보면 연산량이 많죠. 곱셈도 많고, 각 픽셀마다 이 식을 평가하면 성능이 떨어집니다.
→ 그래서 "변화량"만 추적합니다.
세 가지 가능한 점을 두고, 식을 근사 평가:
현재 위치: (x, y)
오른쪽으로: (x + 1, y)
위로: (x, y - 1)
대각선: (x + 1, y - 1)
각 지점의 d = Ax² + By² - AB 값을 계산해서 0에 가까운 점을 선택합니다.
📌 이때, 곱셈 없이도
dx,d2x,dy,d2y등 차이만 추적하면 점을 찍어갈 수 있습니다.
3) 어떻게 곱셈을 제거하나?
d = Ax² + By² - AB
dx = d(x+1, y) - d(x, y)
d2x = dx(x+1, y) - dx(x, y)위 연산에서 중요한 건 다음입니다:
d는 변화 추적용 decision variabledx,dy는 현재 위치에서 각각 x 또는 y로 한 칸 이동했을 때의 변화량d2x,d2y는 그 변화량 자체의 변화
이처럼 계산을 펼쳐서 모든 항을 정수 누적으로 표현하면, 부동소수점 연산 없이 타원을 그릴 수 있습니다.
4) 한 사분면만 그리는 이유는?
타원은 4방향 대칭성을 가지기 때문에, 1사분면만 그리면 나머지는 좌우/상하 반전만 하면 됩니다.
(x, y) → (-x, y), (x, -y), (-x, -y)
따라서 계산은 1/4만 하고, 나머지는 대칭으로 복사!
💡 이 전략은 원(circle) 알고리즘에서는 8방향 대칭성으로 확장됩니다.
5) 타원 판단 알고리즘의 흐름
아래는 타원 그리기의 실제 흐름입니다:
시작점: x = 0, y = b
A = b², B = a²
d = B - A*b + A/4 (초기값)Region 1 (기울기 ≤ 1):
수평/대각선 중 선택
Region 2 (기울기 > 1):
수직/대각선 중 선택
→ d값을 비교해 어떤 방향으로 점을 찍을지 결정합니다.
6) 이 알고리즘을 쓰는 이유
✅ GPU가 없는 임베디드 환경에서도 타원을 정확하고 빠르게 그릴 수 있음
✅ 화면 해상도가 낮거나 리소스가 제한적인 경우에 매우 유리
✅ 정수 덧셈만으로 동작하므로 저전력 시스템에 최적
7) 실제 사용 사례
자동차 계기판, 전자시계, 스마트워치 등 임베디드 디바이스
구형 LCD 디스플레이에서 속도/메모리 최적화
OS 부트 시 뜨는 로고 같은 로우레벨 그래픽
예: 리눅스 커널 초기 로딩 화면 로고도 이런 정수 기반 알고리즘을 활용합니다!
✍️ 요약 정리
목표
부동소수점 없이 타원 그리기
핵심 아이디어
변화량(d, dx, d2x 등)을 추적하며 점을 결정
대칭성
한 사분면만 계산하고 나머지는 반영
사용 이유
정수 연산만으로 빠르고 예측 가능한 렌더링 가능
실제 응용
임베디드 그래픽, 간단한 UI, 디스플레이 펌웨어 등
주제 3. 다항식 계산과 브레슨햄의 철학 – 배비지의 차분 기관과 디지털 그래픽 알고리즘의 연결
1) 곡선 그리기, 왜 어려운가?
직선과 달리 곡선은 아래와 같은 특성을 가집니다:
방향이 계속 변함
위치마다 기울기, 곡률이 다름
특히 고차 다항식의 경우, 한 픽셀 단위에서도 굽는 정도가 달라짐
🧠 즉, 곡선은 "다음 점이 어디일지 예측하기 어렵다"는 특성이 있습니다. → 곱셈/나눗셈/루트/삼각함수 등 복잡한 연산이 필연적으로 동반됩니다.
하지만 브레슨햄은 이 복잡한 곡선조차도 정수 덧셈 누적만으로 처리하는 원리를 제시했습니다.
2) 핵심 아이디어: ‘차분’을 사용하면 어떤 함수든 계산할 수 있다!
다항식 일반식:
f(x)=Axn+Bxn−1+Cxn−2+⋯+Zf(x) = Ax^n + Bx^{n-1} + Cx^{n-2} + \dots + Z
직접 계산하려면 곱셈과 제곱을 계속해야 하지만… 차분 방식(difference method)을 쓰면, 오로지 덧셈만으로 위 함수를 매번 계산하지 않고 "누적"할 수 있습니다.
3) 배비지의 차분 기관과 컴퓨터 그래픽의 연결
💡 배비지의 차분 기관(Difference Engine)
19세기 찰스 배비지는 y = ax² + bx + c 형태의 2차 함수만으로 천문표를 만들고 싶었습니다.
그가 고안한 기계는 이 함수를 매번 계산하지 않고, 이전 결과에 변화량만 더해가는 방식으로 작동했습니다.
f(0)을 계산하고
그다음은 Δf, Δ²f(변화량과 그 변화량의 변화)를 차례대로 더해감
즉, 복잡한 계산 없이도 결과를 만들어낼 수 있었죠.
🖥 이 방식이 그래픽에 적용되면?
"모든 점을 계산하지 않고, 변화량만 추적하자."
점점 변하는 속도(m), 그 변화량(dm), 그 변화량의 변화량(ddm)… → 차수(n) 만큼의 누적 변수만 있으면 된다!
결국, 고차 다항식도 "누적 덧셈"으로만 처리할 수 있는 기반이 마련됩니다.
4) 이 접근의 그래픽 응용: 부드러운 곡선 그리기
예: y = ax³ + bx² + cx + d
이 곡선은 불연속적인 굽힘이 발생합니다. 하지만 다음처럼 각 계수별로 변화를 추적하면 됩니다:
1차 차분 Δ
y(x+1) - y(x)
2차 차분 Δ²
Δ(x+1) - Δ(x)
3차 차분 Δ³
Δ²(x+1) - Δ²(x)
📌 이 3차 차분이 일정하다면 → 루프 돌 때마다 세 개의 변수만 덧셈으로 갱신!
이러한 방식으로 계산하면:
✅ 연산은 덧셈뿐
✅ 정확도는 충분
✅ 속도는 빠름
✅ 메모리 사용량도 적음
5) 직관적으로 정리하면?
# 일반적인 곡선 함수
y = ax³ + bx² + cx + d
# 이걸 루프로 계산하면?
let y = d
let delta = c
let delta2 = 2b
let delta3 = 6a
for (x = 0; x <= max; x++) {
draw(x, y)
y += delta
delta += delta2
delta2 += delta3
}변화량을 누적하면, 곡선도 정수 연산으로 그릴 수 있다!
6) 실생활 응용 – 이게 왜 중요한가?
💡 저사양 임베디드 시스템에서 곡선 그래픽을 그리고 싶다면?
💡 복잡한 GUI에서 부드러운 커브가 필요한데 성능이 부족하다면?
💡 부동소수점 연산이 비싼 환경(RISC, 초소형 MCU 등)에서는?
이 기술은 그래픽 연산을 부동소수점 없이 가능하게 만들어줍니다.
미세한 손떨림 보정, 부드러운 트랜지션 효과, 게임 캐릭터 곡선 경로 등에서 여전히 쓰입니다.
✍️ 요약 정리
핵심 원리
다항식도 차분(Δ)을 통해 누적 덧셈으로 처리 가능
구현 방식
이전 값 + 변화량 + 변화량의 변화 + …
대표 사례
배비지 차분 기관, 정수 기반 곡선 렌더링
장점
부동소수점 없이 고차 곡선을 정밀하게 표현 가능
응용
저사양 그래픽 시스템, 실시간 반응 UI 등
주제 4. 정수만으로 타원을 그린다고? – 브레슨햄 타원 알고리즘과 대칭성의 마법
1) 곡선보다 더 어려운 곡선, 타원
타원은 원보다 계산이 까다롭습니다. 왜냐하면 타원은 두 축(a, b)의 길이가 다르기 때문에 점마다 곡률이 다르고, 위치에 따라 방향이 빠르게 바뀌죠.
타원의 일반 방정식:
x2a2+y2b2=1\frac{x^2}{a^2} + \frac{y^2}{b^2} = 1
이걸 다시 정리하면:
Ax2+By2−AB=0(A = b2,B = a2)A x^2 + B y^2 - A B = 0 \quad (\text{A = } b^2, \text{B = } a^2)
복잡해 보이죠? 게다가 저 식을 매 픽셀마다 계산한다면 정수 곱셈과 제곱이 매번 반복됩니다.
2) 💡 해결책: 변화량(차분)을 추적해서 곱셈을 없애자!
브레슨햄의 타원 알고리즘은 이런 방정식 전체를 매번 계산하는 대신, 한 점에서 다음 점으로의 이동만을 덧셈과 뺄셈으로 계산합니다.
그 중심 개념이 다음과 같은 결정 변수 dd입니다.
결정 변수 d의 의미:
현재 점이 이상적인 타원에 얼마나 가까운지 측정
다음 점을 선택할 때, 가능한 3개 중 어떤 점이 dd를 0에 가깝게 만들지 비교
3) 계산 과정 – 왜 덧셈만으로 가능한가?
예를 들어, 세 점 중에서 고를 수 있어요:
현재 위치: (x, y)
후보 1: (x + 1, y)
후보 2: (x, y - 1)
후보 3: (x + 1, y - 1)각 후보 위치에서 식 Ax2+By2−ABA x^2 + B y^2 - AB을 다시 계산하면 되지만… 우리는 이 계산의 변화량(차이)만 추적할 수 있습니다.
예를 들어:
dx=A⋅(2x+1)dx = A \cdot (2x + 1)
d2x=2⋅Ad2x = 2 \cdot A
마찬가지로 dy, d2y도 계산 가능
이 델타값들만 갱신하면서 d를 계산해 나가면 됩니다.
4) 대칭성(symmetry): 4분의 1만 그리고 나머지는 복사!
타원은 4사분면에 완벽히 대칭입니다. 즉, (x, y)에 점을 찍으면 동시에 다음도 찍으면 돼요:
(-x, y)
(x, -y)
(-x, -y)
이렇게 하면 단 1/4만 계산해서 전체 타원을 효율적으로 완성할 수 있죠!
원을 그릴 땐 이걸 8방향 대칭으로 늘릴 수 있습니다.
5) 아핀 변환과 타원 그리기의 관계
브레슨햄 타원 알고리즘은 기하학적 변환의 한 종류, 즉 아핀 변환에서 출발합니다.
평행이동 (translation)
크기 조절 (scaling)
회전 (rotation)
타원은 사실 원에 scaling만 적용하면 만들어지는 도형입니다. 따라서 원 그리기 알고리즘에서 크기만 조정하면 타원을 만들 수 있고, 브레슨햄 알고리즘은 이걸 정수 기반으로 ‘똑똑하게’ 풀어낸 사례죠.
6) 알고리즘 요약 플로우
시작: (x, y) = (0, b)
d = 초기 결정 변수
loop:
d 값 기반으로 다음 이동 결정 (수평, 수직, 대각선)
결정변수 갱신
대칭 위치에 점 찍기
종료: y < 0 or x > a
7) 실제 응용 예시
✅ 게임 엔진에서 캐릭터의 움직임 경로 (부드러운 회전)
✅ 하드웨어 디스플레이 장치 (LCD/LED 타원 렌더링)
✅ SVG 그래픽 구현체, CAD 도면 출력
✅ 디지털 시계 문자판, 곡선 기반 UI 컴포넌트 등
특히 그래픽을 픽셀 단위로 제어해야 하는 환경에선 지금도 쓰이고 있습니다.
✍️ 요약 표
핵심 원리
타원 식을 직접 계산하지 않고 변화량 추적으로 이동
덧셈만으로 가능?
가능. dd, dxdx, dydy, d2xd2x, d2yd2y 등을 사용
대칭 활용
1/4 타원만 그리고 나머지는 대칭 복사
수학적 배경
아핀 변환, 미분 기반 최적화, 점진적 오차 추적
활용 분야
디지털 그래픽, 임베디드 렌더링, 경로 시뮬레이션
주제 5. 픽셀로 다항식을 계산한다고? – 점진적 차분과 찰스 배비지의 차분 기관
1) 픽셀 기반 곡선 표현의 한계
브레슨햄의 선이나 타원 알고리즘은 비교적 단순한 1차 또는 2차 수학 함수(직선, 원, 타원)에만 적용할 수 있었습니다.
하지만 더 복잡한 곡선, 즉 3차 이상의 다항식(polynomial)을 그리려면 어떻게 해야 할까요?
예를 들어 이런 식 말이죠:
y=Ax3+Bx2+Cx+Dy = Ax^3 + Bx^2 + Cx + D
이런 곡선들은 픽셀 하나 안에서도 방향이 바뀔 수 있고, 복잡한 미분값 변화도 있기 때문에 단순 오차 추적으로는 처리하기 어렵습니다.
2) 💡 해결책: 차분을 누적해가는 방식
우리는 이런 곡선을 그릴 때도 정수 연산만으로 계산할 수 있습니다. 그 핵심 아이디어는 차분을 점진적으로 누적하는 것이에요.
다항식의 변화량 구조
다항식은 계속 미분하면 최종적으로 상수가 됩니다.
예를 들어,
f(x)=Ax3+Bx2+Cx+Df(x) = Ax^3 + Bx^2 + Cx + D
1차 미분하면:
f′(x)=3Ax2+2Bx+Cf'(x) = 3Ax^2 + 2Bx + C
2차 미분하면:
f′′(x)=6Ax+2Bf''(x) = 6Ax + 2B
3차 미분하면:
f′′′(x)=6Af'''(x) = 6A
이걸 정수 덧셈만으로 시뮬레이션할 수 있다면, 아주 복잡한 곡선도 부동소수점 연산 없이 그릴 수 있습니다!
3) 📜 찰스 배비지의 차분 기관(Difference Engine)
이 원리를 실제 기계로 만든 사람이 바로 컴퓨터의 아버지 **찰스 배비지(Charles Babbage)**입니다.
"내가 다항식만 알 수 있다면, 나머지는 톱니바퀴가 계산해줄 것이다."
그가 설계한 차분 기관(Difference Engine)은 바로 차분 누적법으로 다항식 계산을 자동화하려는 기계였어요.
기계 구조는 각 계수(차수)별로 덧셈 누적용 톱니바퀴를 가지고 있었고,
수동 계산자가 반복해 했던 작업을 자동화해 낼 수 있었습니다.
4) 점진적 계산의 예시 – 2차 함수
간단한 예를 들어봅시다. 2차 다항식:
y=x2y = x^2
이 경우, 각 x값에 대해:
첫 번째 차분 (delta1): y_{i+1} - y_{i} = 2x + 1
두 번째 차분 (delta2): 항상 2
그래서 아래처럼 갱신 가능:
let y = 0;
let delta1 = 1;
let delta2 = 2;
for (let x = 1; x <= width; x++) {
y += delta1;
delta1 += delta2;
draw(x, y);
}✅ 곱셈 없이 덧셈만으로 x2x^2을 계산한 것!
5) 다항식 표현을 위한 일반 구조
n차 다항식을 그리기 위해선:
1차:
값2차:
차이3차:
차이의 차이…
n차:
최종 상수
각 차수를 위한 누적용 변수 세트를 만들어서 반복문마다 차례대로 갱신하면 됩니다.
이 구조 차분기관(차분기계)와 완전히 동일한 원리입니다.
6) 왜 이게 중요한가요?
이 방식은 단순히 '정수로 연산하자'는 것을 넘어서서:
CPU/GPU 없이도 계산 가능한 알고리즘입니다.
복잡한 연산이 필요한 임베디드 시스템, 저전력 장치에 매우 적합합니다.
WebGL 같은 환경에서 부동소수점 지원이 제한된 브라우저/디바이스에서도 고차 곡선 렌더링이 가능하게 합니다.
7) ✍️ 요약 표
핵심 원리
고차 다항식을 차분 누적으로 표현
적용 방식
각 계수별 차분값을 반복문 내에서 갱신
역사적 배경
찰스 배비지의 Difference Engine
수학적 기반
다항식의 유한 차분, 미분계수 누적
실전 활용
정수 기반 곡선 렌더링, 디지털 신호 처리, 낮은 전력 환경에서의 연산 최적화
✨ 마무리하며: 계산을 하지 않는 계산
11장 전체의 핵심 메시지는 이것입니다:
“컴퓨터를 잘 쓴다는 건, 계산을 잘 시키는 것이 아니라 계산을 줄이는 것이다.”
반복 계산을 덧셈으로 바꾸는 것
부동소수점을 정수로 바꾸는 것
실제 값을 미리 테이블화하는 것
이 모든 건 ‘계산의 방향을 바꾸는 사고’에서 비롯됩니다. 그리고 그 핵심은 수학의 구조를 꿰뚫고 이를 컴퓨터 구조에 맞게 재배열하는 능력이죠.
Last updated