Major Implementation Tasks

Implementation of a Renderer

Implementation

• graphics system을 구현하는 방법 ? – 핵심은

algorithm

– 현재는 대부분 hardware 구현 가능 – 그러나, 아직도 software 구현 필요

• algorithms

– theoretical versus practical performance – hardware versus software implementations – specific characteristics of an application

7.1 Four Major Tasks

Major Implementation Tasks

• input : geometric entity (polygon)

• output : 화면 상의 display

• output : 화면 상의 display

• 전체 과정에서 필요한 step들

– modeling

– geometric processing

– rasterization

Major Implementation Tasks

• Modeling

(보통, user program)

– a set of vertices that specifies a set of geometric objects

• Geometric Processing

– normalization

– clipping

4

– clipping

– hidden-surface removal – shading

• Rasterization

(= scan conversion)

– generate a set of pixel values for graphics primitives

• Display

– display quality : jaggedness → aliasing

Basic Implementation Strategies

• object-oriented approach for each object

render(object)

• image-oriented approach for each pixel

assign_a_color(pixel)

OpenGL approach

ray-tracing approach

7.2 Implementation of

Transformations

Coordinate Systems

• object

/ world coordinate system

• object

/ world coordinate system

• eye

/ camera / view coordinate system

• clip

coordinate system

– canonical view volume에서 clipping

• NDC

/ normalized device coordinate system – viewport mapping 으로 화면 출력

Viewport Transformation

• NDC → screen 으로의 mapping

– window size가 변해도 같은 화면이 나오도록

8

NDC screen coordinate

m in m ax

m in m ax

m ax m in

m in m ax

m in m ax

m ax m in

) (

) (

y y

y y y

y y

y

x x

x x x

x x

x

v v

v v

v v

v v

−

− − +

=

−

− − +

=

7.3 Line Segment Clipping

Cohen-Sutherland Clipping

• I. E. Sutherland, Sketchpad, A Man-Machine Graphical Communication System, (1963).

• 2D line segment clipping

– window를 벗어난 부분을 없애는 algorithm

10

– 3D 로 쉽게 확장 가능

clip 전 clip 후

Cohen-Sutherland Line Clipping

• 기본 아이디어 #1 : 4 bit code – line의 끝점들을 code 화

• 아예 벗어난 것들은 미리 처리 가능

1000 1010

1001 1000 0000, 0000 : window 내부

0010 1010

0110 0100

0101 0001 1001

0000

left

0000, 0000 : window 내부

0100 & 0010 = 0000 : 경계에 걸릴 수도 있다

Cohen-Sutherland Line Clipping

• line segment with endpoints (x₁, y₁), (x₂, y₂)

• Let o₁ = outcode(x₁, y₁) o₂ = outcode(x₂, y₂)

• o

₁

= o

₂

= 0

: display

– both endpoints are inside the clipping window

• o ≠ 0, o = 0; or vice versa

12

• o

₁

≠ 0, o

₂

= 0; or vice versa

– intersection 계산 필요

• o

₁

AND o

₂

≠ 0

: ignore

– both endpoints lie on the same outside side of the window.

• o

₁

AND o

₂

= 0

– intersection 계산 필요

Cohen-Sutherland Line Clipping

• 기본 아이디어 #2

– 경계에 걸릴 수 있는 것들은 경계를 기준으로 분할

• 다시 벗어난 것들을 제거

P

1 2

1 2

1 1

1

1 ( )

x x

y m y

m y x y

x

x x m y

y

−

= − + −

=

− +

=

P1

P2

P3

′ P2

′ P1

Window

′ P3

) , (x₁ y₁

) , (x₂ y₂ )

, (x y xwmin

x =

Cohen-Sutherland Line Clipping

• 분할 후의 예제

P2

′ P2

Window

P2

P′ Window

14

P1

P3

P4

P2

′ P1

′ P3

P1

P3

P4

′ P2

′ P1

′ P3

각각을 code화 해서 다시 검사

Liang-Barsky Clipping

• Y. Liang and B. Barsky, “A new concept and method for line clipping”, ACM Trans. on Graphics, 3(1):1–22, (1984).

• use the parametric form for lines p₁ = (x₁, y₁), p₂ = (x₂, y₂)

p(α) = (1 – α) p₁₁ + α p₂₂ (0 ≤ α ≤ 1)

• or, equivalently,

x(α) = (1 – α) x

₁

+ α x

₂

y(α) = (1 – α) y

₁

+ α y

₂

• window 의 각 경계에서, parameter 값

α

₁

, α

₂

, α

₃

, α

₄

계산

Liang-Barsky Clipping

• Sort the parameters and determine the topological relationships

• 1 > α₄ > α₃ > α₂ > α₁ > 0 : clipped line segment [α₂, α₃]

• 1 > α₄ > α₂ > α₃ > α₁ > 0 : outside line segment

16

7.4 Polygon Clipping

Polygon clipping

• line clipping 의 단순 확장은 아님

18

Before Clipping After Clipping Before Clipping After Clipping

line clipping polygon clipping

Sutherland-Hodgeman polygon clipping

• I. E. Sutherland and G. W. Hodgeman, “Reentrant Polygon Clipping”, Comm. ACM, 17:32–42, (1974).

• 기본 아이디어 : 문제를 쉽게 분할

– window 의 각 변에서 한 번씩 clipping

– 총 4번 line 에 대한 polygon clipping 수행 – 총 4번 line 에 대한 polygon clipping 수행

Original Polygon

Clip Left

Clip Right

Clip Bottom

Clip Top

Sutherland-Hodgeman polygon clipping

• line 에 대한 polygon clipping은?

– 경계를 따라가면서

line clipping,

내부만 남긴다

S

D

D S I

20

D S

S D

I

S

D

Save D (a)

Save I (b)

No Points Saved

(c)

Save I, D (d)

Sutherland-Hodgeman polygon clipping

• 경우에 따라서는

2개 이상의 polygon 이 나올 수도

• convex polygon만 처리하면 반드시 1개의 polygon 만 생긴다.

– concave polygon :

분할해서 convex polygon 으로

7.5 Clipping of Other Primitives

Bounding Box

• the smallest rectangle, aligned with the window, that contains the polygon

• clipping 이 불필요한 경우를 미리 제거

Clipping of Other Primitives

• curves, surfaces

– complicated to process them directly

– approximate with line segments and planar polygons

24

– approximate with line segments and planar polygons

• texts

– bitmap characters : pixel 단위로 clipping

– stroke(outline) characters : polygon으로 취급

• clipping in the frame buffer

– geometric clipping 이 효과적

– raster objects 는 어쩔 수 없이 frame buffer 에서 clip

7.6 Clipping in Three Dimensions

2D and 3D clipping

• 2D clipping

– window : clipping rectangle

• 3D clipping

– view volume : clipping volume

26

3D clipping algorithms

• 대부분, 2D clipping algorithm을 확장

• Cohen-Sutherland

line clipping algorithm

– use 6-bit outcode in parallelepiped view volume – 그 이후는 사실상 동일

3D clipping algorithms

• Liang-Barsky

line clipping algorithm

– add the parametric equation for z-axis z(α) = (1 – α) z₁ + α z₂

– find 6 α values

28

• Sutherland-Hodgeman

polygon clipping algorithm – add extra two clippers for the z-axis components

3D clipping algorithms

• view volume normalization

– 대부분의 clipping algorithm들은 view volume 이 normalize 되어야 작동

– reduce the computation in clipping

clipping이 까다로움 normalize 후에

clipping 가능

7.7 Hidden-Surface Removal

Hidden Surface Removal

• viewer 가 볼 수 없는 face를 제거하는 algorithm

• 물체를 화면에 표시할 때, 어느 쪽 ?

• 해결책 ?

– hidden-surface elimination algorithm

• 물체의 숨은 면을 제거

– = visible-surface detection algorithm

Hidden Surface Removal

• object-space approaches

– 3D 에서 face 간의 순서를 부여 – painter’s algorithm

32

• image-space approaches

– pixel 마다 보이는 물체를 찾음 – z-buffer algorithm

Back-face Removal

• front face : camera 쪽으로 향한 face

–90° ≤ θ ≤ 90°

– 화면에 나와야 한다

• back face : camera 반대 쪽을 향한 face θ < –90°, θ > 90°

– 화면에 나오면 안 된다

front

⋅ V < 0 N

back

⋅ V > 0 N

V : view vector N_front N_back

θ

Back-face Removal

• view coordinate system 에서는

back-face를 화면에 표시할 필요가 없다 – 다른 면에 의해서 가려지므로

front face back face

34

xv

yv

zv

front face

back face

Z-buffer Algorithm

• E. Catmull, “A hidden-surface algorithm with antialiasing”, Computer Graphics, 12(3):6–11, (1975).

• 기본 아이디어

– 화면 상의 pixel 하나를 그릴 때 마다 z 좌표도 함께 기억

xv

yv

z₁

Z-buffer Algorithm

• 초기 : 모든 pixel 의 z-좌표는 –∞

• pixel 을 그릴 필요가 있으면, – if (z_pixel

< z

_object) then

pixel update, z_pixel = z_object – else ignore

36

−∞

pixel

= z

pixel

= − 100 z

pixel

= − 50 z

pixel

= − 50 z

object1 = −100 z

object2 = −50 z

object3 = −80 z

−∞

background = z

Z-buffer Algorithm

• coherence 의 이용

– pixel 단위 처리일 때, 매번 다시 계산하지 않음

• two points on a polygon (x₁, y₁, z₁), (x₂, y₂, z₂)

a x + b y + c z + d = 0 plane equation

∆x = x – x , ∆y = y – y , ∆z = z – z

∆x = x₂ – x₁, ∆y = y₂ – y₁, ∆z = z₂ – z₁ a ∆x + b ∆y + c ∆z = 0

• 바로 옆 pixel 로 이동시,

∆x = 1, ∆y = 0

∆z = –(c/a) ∆x

Z-buffer Algorithm

• image space algorithm

– 모든 물체는 일단 화면까지 projection 된다

• simple & efficient

– 대부분의 video card 가 채택

38

– 대부분의 video card 가 채택 – OpenGL에서도 사용

• 단점 : 메모리가 많이 필요

– pixel 하나 마다 (R, G, B, Z) 로 저장

• Z 좌표를 저장하기 위한 메모리 필요

Painter’s Algorithm

• 모든 물체를 카메라에서 먼 것부터 정렬 – view coordinate system 에서 정렬

– 멀리 있는 것부터 그린다.

– 가려진 부분은 자동적으로 지워진다

A B

C y

x

A B

C -z

x

sorting

painting (C,B,A)

Painter’s Algorithm

• = list priority algorithm

• = depth sorting algorithm

– 유화 그림 그리는 것과 동일한 순서

– 배경부터 그린 후에, 가까운 것을 그리면, 가려진 부분은 자동으로 사라진다.

40

가려진 부분은 자동으로 사라진다.

• object space algorithm

– 물체를 화면에 가져오기 전에 미리 처리

Depth sorting Algorithm

• 문제점

– 순서대로 정렬할 수 없는 경우도 있다 – 해결책 : 물체를 2개 이상으로 분리

B

A

B

A C

Scan-line Algorithm

• rasterize the polygon scan line by scan line

– determine the visible polygon by incremental depth calculation

– used by Macintosh 3D video cards

42

7.8 Scan Conversion

Scan Conversion

• geometric object를 실제 화면에 출력하는 과정

• 최종 출력 단계는 pixel 하나 단위

write_pixel(int ix, int iy, int value)

– 좌표 (ix, iy)에 색상 value 를 갖는 pixel 출력

44

– 좌표 (ix, iy)에 색상 value 를 갖는 pixel 출력

• line segment 의 scan conversion – DDA algorithm

– Brensenham’s algorithm

Line Segment

• line segment

– (x₁, y₁) – (x₂, y₂) 사이를 연결하는 선분

– raster system : 두 끝점 사이의 pixel들을 on

• 문제점 !

– frame buffer는 array 형태 – frame buffer array

– 두 끝점을 잇다가

소수점

이 나오면?

• round-off 시킴 (

반올림

)

Intuitive Method

• line equation

• line(x_a, y_a, x_b, y_b) 라면,

b x m

y = ⋅ +

a b

a b

x x

y y

x m y

−

= −

∆

= ∆

a

a m x

y

b = − ⋅

y

m

b

_{(x , y )}

(x_b, y_b)

46

for x_i = x_a to x_b

y

_i

= ROUND(m x

_i

+ b) ← ∗

setPixel(x_i, y_i)

– 문제점은 ?

– 더 효과적인 방법은?

a

b x

x

x −

∆

x

b

_(x

a, y_a)

Intuitive Method

• | m | ≥ 1 • | m | ≤ 1

• 하나의 x 에 여러 개의 y값이 필요

• 끊어진 line !

• 해결책

– x, y 역할을 바꾼다

• 출력은 잘 나옴

• 한 pixel을 찍기 위해,

• y_i = ROUND(m x_i + b)

• 너무 복잡한 연산 필요 !

DDA Algorithm

• digital differential analyzer

• –1 ≤ m ≤ 1, x_a < x_b 인 경우 y_k = m x_k + b

x_k+1 = x_k + 1

• algorithm int x_i = x_a

float y_i = y_a

setPixel(x_i, ROUND(y_i) ) for x_i = x_a+1 to x_b

y = y + m

48

x_k+1 = x_k + 1

y_k+1 = m x_k+1 + b

y_k+1 – y_k = m (x_k+1 – x_k) y_k+1 = y_k + m

y_i = y_i + m

setPixel(x_i, ROUND(y_i) )

• ROUND(...) 는 반올림 연산

DDA Algorithm

• | m | > 1,

x_a < x_b 인 경우 y_i = m x_i + b

y_k+1 = y_k + 1

• algorithm

float minverse = 1 / m float x_i = x_a

int y_i = y_a

setPixel(ROUND(x_i), y_i ) for y = y +1 to y

m y b

x_i = m1 _i − y_k+1 = y_k + 1

x_k+1 = (1 / m) y_k+1 – (b / m) x_k = (1 / m) y_k – (b / m)

x_k+1 – x_k = (1 / m) (y_k+1 – y_k) x_k+1 = x_k + (1 / m)

for y_i = y_a+1 to y_b

x_i = x_i + minverse

setPixel(ROUND(x_i), y_i )

DDA Algorithm

• 장점

– 조금 빠르다 (곱하기가 불필요)

• 단점

– m 값이 정확하지 않을 수 있다

• 실수(float)의 정밀도 문제 (예: 1/3)

50

• 실수(float)의 정밀도 문제 (예: 1/3)

• 길이가 길면,

끝점이 빗나간다

– round-off 연산은 비싸다

– 실수(float) 연산도 비싸다

7.9 Bresenham’s Algorithm

Bresenham’s Line Algorithm

• J. E. Bresenham, “Algorithm for computer control for a digital plotter”, IBM Sys. J., January:25–30, (1965).

• symmetry (대칭성) 를 이용해서,

x

_a

< x

_b

, 0 ≤ m < 1

인 경우만 따짐

x, y 역할을 바꿈

52

x축 대칭 기준 !

x축 대칭, x, y 역할을 바꿈 시작점, 끝점을 바꿈

Bresenham’s Line Algorithm

• (x_k, y_k) 를 출력한 후에는,

– (x

_k+1

, y

_k

)

또는

– (x

_k+1

, y

_k

+1)

을 출력해야

– integer(정수) 연산 만으로 선택할 수 있다!

Bresenham’s Line Algorithm

y = m (x_k + 1) + b

y

_k

y

_k

+1

54

d

₂

= (y

_k

+ 1) – y = y

_k

+ 1 – m (x

_k

+ 1) – b d

₁

= y – y

_k

= m (x

_k

+ 1) + b – y

_k

• d₁ ≥ d₂ 이면, d₁ – d₂ ≥ 0

y

_k+1

= y

_k

+ 1

• d₁ < d₂ 이면, d₁ – d₂ < 0

y

_k+1

= y

_k x_k + 1

Bresenham’s Line Algorithm

d

₁

= y – y

_k

= m (x

_k

+ 1) + b – y

_k

d

₂

= (y

_k

+ 1) – y = y

_k

+ 1 – m (x

_k

+ 1) – b

d₁ – d₂ = 2 m (x_k + 1) – 2 y_k + 2 b – 1

= 2 m x_k – 2 y_k + (2 m + 2 b – 1) m = ∆y / ∆x 이므로,

m = ∆y / ∆x 이므로,

p

_k

= ∆x (d

₁

– d

₂

) = 2 ∆y x

_k

– 2 ∆x y

_k

+ c

c = ∆x (2 m + 2 b – 1) = 2 ∆y + ∆x (2 b – 1)

• p_k ≥ 0 이면, ∆x (d₁ – d₂) ≥ 0 y_k+1 = y_k + 1

• p_k < 0 이면, ∆x (d₁ – d₂) < 0 y_k+1 = y_k

Bresenham’s Line Algorithm

p_k+1 = 2 ∆y x_k+1 – 2 ∆x y_{k +1} + c p_k = 2 ∆y x_k – 2 ∆x y_k + c

p_k+1 – p_k = 2 ∆y (x_k+1 – x_k) – 2 ∆x (y_{k +1} – y_k) x_k+1 – x_k = 1 이므로,

p

_k+1

= p

_k

+ 2 ∆y – 2 ∆x (y

_{k +1}

– y

_k

)

56 k+1

=

_k

+ 2 – 2 (

_{k +1}

–

_k

)

y_k+1 은 y_k (p_k < 0) 또는 y_k + 1 (p_k ≥ 0)

p

_k

< 0 : p

_k+1

= p

_k

+ 2 ∆y

p

_k

≥ 0 : p

_k+1

= p

_k

+ 2 ∆y – 2 ∆x 초기값 p

₀ 는 ?

p₀ = 2 ∆y x₀ – 2 ∆x y₀ + c

c = ∆x (2 m + 2 b – 1) = 2 ∆y + ∆x (2 b – 1) 정리하면,

p

₀

= 2 ∆y – ∆x

Bresenham’s Line Algorithm

• Rough Algorithm x₀ = x_a , y₀ = y_a

∆x = x_b – x_a , ∆y = y_b – y_a setPixel(x₀, y₀)

p₀₀ = 2 ∆y – ∆x= 2

for (k = 0; k < ∆x ; k++) x_k+1 = x_k + 1

if p_k < 0, y_k+1 = y_k

p_k+1 = p_k + 2 ∆y if p_k ≥ 0, y_k+1 = y_k + 1

p_k+1 = p_k + 2 ∆y – 2 ∆x setPixel(x , y )

Bresenham’s Line Algorithm

• Algorithm (불필요한 첨자를 없애면) x = x_a , y = y_a

∆x = x_b – x_a , ∆y = y_b – y_a setPixel(x, y)

p = 2 ∆y – ∆x

58

= 2

for (k = 0; k < ∆x ; k++) { x = x + 1

if (p < 0) p = p + 2 ∆y

else { y = y + 1, p = p + 2 (∆y – ∆x ) } setPixel(x, y)

}

Bresenham’s Line Algorithm

• 완전한 알고리즘은?

– x

_a

< x

_b

, 0 ≤ m < 1

인 경우만 설명했음

– 나머지 경우 모두에 대한 알고리즘 필요

• Bresenham’s Line Algorithm은

• Bresenham’s Line Algorithm은

single processor 에서는 가장 빠르다

– 고급 video card 에서는 H/W chip 으로 구현 – 더 빠른 방법은? parallel algorithm

• multi-processor 사용

7.10 Scan Conversion of Polygons

Jordan Theorem

• polygon vs. line

– polygon 외부에서 출발한 직선은 polygon과 반드시 짝수 번 교차

Scan-line Polygon Filling Algorithm

• 기본 아이디어

– polygon vs. scan-line 교차점을 계산 – 교차점 사이의 pixel을 출력

62

scan-line polygon

시작 끝 시작 끝

Scan-line Polygon Filling Algorithm

• degenerate cases

– 특별한 처리가 필요한 경우

변들이 같은 쪽

시작, 끝, 시작, 끝

시작, 끝, 시작, 끝

변들이 서로 다른 쪽 변들이 같은 쪽

Coherence 의 이용

• 전체 polygon fill 시에는

coherence로 빠르게 처리 가능 – coherence : 응집성

– 현재 scan-line을 처리한 후에는, 다음 scan-line은 조금만 변한다.

64

scan-line y_k + 1 scan-line y_k

Bresenham’s line algorithm !

Inside-outside Test

• polygon의 내부/외부 구별

– 왜 ? 내부를 구별해야 fill 가능

– Jordan theorem !

• 해석 방법

– odd-even rule – odd-even rule

• = odd parity rule, even-odd rule – nonzero winding number rule

Inside-outside test

• odd-even rule

– 홀수번 교차 : 내부 – 짝수번 교차 : 외부

• non-zero winding rule – 위에서 아래로 : +1 – 아래에서 위로 : –1 – 합이 0일 때만 외부

66

–1 –1 +1 +1

Boundary-Fill Algorithm

• 정해진 도형의 내부를 정해진 색깔로 채우기 – 내부점: an interior point (x, y)

– 경계 색:a boundary color – 채움 색:a fill color

boundary color

interior point (x, y)

fill color

Boundary-Fill Algorithm

• 기본 아이디어

– interior point 부터

인접한 pixel

들을 – fill color로 바꾼다.

– boundary color를 만날 때까지

68

• 인접한 pixel ?

4-connected 8-connected

4-connected vs. 8-connected

• 4-connected • 8-connected

start point

Boundary-Fill Algorithm

• rough algorithm for 4-connected case

void boundaryFill4(int x, int y, Color fill, Color boundary) { Color current = getPixel(x, y);

if (current ≠ boundary && current ≠ fill) { setPixel(x, y, fill);

70

setPixel(x, y, fill);

boundaryFill4(x+1, y, fill, boundary); // recursion ! boundaryFill4(x–1, y, fill, boundary);

boundaryFill4(x, y+1, fill, boundary);

boundaryFill4(x, y–1, fill, boundary);

}

Flood-Fill Algorithm

• boundary fill 의 변형

– start point와 같은 색인 pixel들을 바꾼다

start point

7.11 Anti-aliasing

Anti-aliasing

• aliasing

– information loss due to low-frequency sampling – jagged or stair-step appearance

• anti-aliasing

– aliasing 제거 방법 – aliasing 제거 방법

aliasing anti-aliasing

Anti-aliasing 기법들

• area 계산법

– pixel 에 걸리는 면적을 직접 계산

• filter

법

% 30 red

% 70 blue

값

pixel = × + ×

면적: 30%

74

• filter

– 면적을 다시 가중치로 적분

• super-sampling

– 한 pixel의 여러 군데를 sample

16 red 6

16 blue 10

값

pixel = × + ×

∫∫

^⋅

= Gaussian(x, y) Value(x, y) dx dy 값

pixel

7.12 Display Considerations

Half-toning and Dithering

• Half-toning (신문의 사진들)

– technique to simulate gray levels by creating patterns of black dots of varying size

• Dithering (= digital half-toning)

– use digital halftone to simulate halftoning with fixed

76

– use digital halftone to simulate halftoning with fixed sized pixels

요약