zzun.net zzun's blog since 2001

Computer Graphics
SNU CSE / 2007 Spring / Prof. 신영길

Functions of Graphic Package (OpenGL, DirectX)
- Provide prmitives for graphic description
- Build and maintain graphic representation model
- Provide primitives for viewing operations
- Support user interaction with application program
- Interact directly with users to allow them modify viewing parameters, if possible

Frame Buffer
- 일반적으로 스크린 크기의 메모리
- 각 pixel은 color, 불투명도 등의 값을 기억하고 있음
- 나중에 모니터로 보내 화면으로 보여줌(그래픽카드), 모니터로 뿌리기 바로 직전의 데이터
- Alpha Channel(8bit) : 투명도(transparency) 정보를 갖고 있음
- Z-buffer(depth buffer, 16bit) : 각 pixel의 depth(view point 로부터의 거리)
- Double Buffering : read/write를 동시에 못하고 lock을 걸어야 하므로 2개의 버퍼를 둠

Graphics Processor(Graphics Adapter)
- Frame Buffer + Display Controller +Display Processor

Resolution depends on
- Frame buffer resolution
- Display HW characteristics
- Sampling method

Interlacing
- scan-line의 짝수, 홀수로 구분해 한번씩 refreshing 하는 기법

Color model
- RGB : additive model : 더하면 더할수록 흰색이 됨
- CMYK : subtractive model : 더하면 더할수록 검은색이 됨

Rendering : model -> primitives -> image(pixel)
- Scan Conversion : primitive들을 pixel 값으로 변환하는 것
- Clipping : window 바깥 부분을 잘라내는 것
- Transformation : 좌표계 변환
- Shading : color 입히기

Midpoint Line Algorithm (Bresenham's Line Algorithm)
- 기울기가 0~1인 line (나머지는 symmety)
- integer 덧셈과 *2 연산만 있으므로 매우 빠르다.

Area Filling (Scan-line Approach)의 Coherences
- Span coherence : 같은 span 내의 pixel은 같은 값일 확률이 높다.
- Scan-line coherence : 연속된 scan-line은 비슷할 확률이 높다.
- Edge coherence : n번째 scan-line에서 만난 edge는 n+1번째에서도 만날 확률이 높다.

Parity Fill Approach
- 한 pixel에서 임의의 방향으로 선을 그었을 때 홀수번 만나면 inside, 짝수번 만나면 outside

Winding Number Approach
- 같은방향으로 교차하면 +1, 다른방향이면 -1 : cross product 계산
- 0 이면 바깥, 1 이상이면 안쪽 (몇 겹 안쪽인지 알 수 있음)

Span Rules (Edge Crossing Rules)
- intersections : 한 span에서 leftmost는 안쪽, rightmost는 바깥쪽으로 간주
- shared vertices : y_min에서만 parity를 계산(교점으로 취급)
- horizontal edges : 무시함 (parity를 계산하지 않음)

Character and Symbols
- Stroke tables : vector 형태로 저장, rotate/scale 쉬움
- Bitmap : pixel 형태로 저장, rotate/scale 이 제한적.

Nyquist Theorem
- sampling frequency > 2 * signal bandwidth 해야지만 orginal wave를 recover 가능

Prefiltering
- Low-pass filter : Nyquist limit 보다 큰 frequency 를 없앰 (blurring)

Postfiltering
- Supersampling : 많은 point 를 sampling 해서 한 pixel 로 average down

Projective Transformation
- Projective Transformation : Affine Transformation + Perspective Projection
- Affine Transformation : Linear Transformations + Translation (Affine Space (point + vector) 에서의 변환)
- Rigid Transformation : rotation, tralation 같은 object의 변형이 없는 변환들

Cohen-Sutherland Line-Clipping Algorithm
- 상하좌우에 각 1 bit 씩 할당해서 두 점을 AND 해서 0000 일 경우엔 reject
- Midpoint Subdivision : midpoint 를 찾아 나눠서 두 선의 accept / reject 를 결정함
- extreame case (reject/accept가 많은 경우)에 좋은 알고리즘

Parametric Line Clipping (Cyrus-beck Technique)
- viewport edge 상의 임의의 점(pe)을 잡아서, 그 edge의 outward normal vector와 p-pe vector의 내적
- 내적 결과 음수이면 inside, 양수이면 outside, 0이면 edge 위에 있음 => 교점을 쉽게 구할 수 있음
- 최대 4개의 교점을 구한 후, t>1 또는 t<0 인 점은 버림
- PE(Potentially Entering), PL(Potentially Leaving) 을 Normal vector와 p0-p1 vector 의 내적으로 구함(PL이 +)
- max_t PE 와 min_t PL 을 선택해 두 점 사이를 취함 ( PE>PL 이면 버림 )
- trivial accept/reject 가 불가능하고 모두 계산해야함

Liang-Barsky Line Clipping
- 교점 계산을 통해 4개의 t를 먼저 구함
- normal vector 와 p1-p0 vector 의 내적으로 entering t 와 exiting t 를 구분함
- entering_t_min < exiting_t_max 이면 선을 그림

Sutherland-Hodgeman Algorithm
- 임의의 v1 -> v2 선과 edge와의 교점 v' 이 있을 때,
- out -> in 인 경우(entering) : v' - v2 를 그림
- in -> in 인 경우 : v1 - v2 를 그림
- in -> out 인 경우(leaving) : v1 - v' 를 그림
- out -> out 인 경우 : 그리지 않음
- concave (not convex) polygon 인 경우 bridge가 생기므로 : 2개 이상의 convex로 나누어 계산

Weiler-Atherton Polygon Clipping
- entering 후에는 polygon boundary를 따라 가고,
- leaving 후에는 window boundary를 CCW(반시계)로 따라 가면서 clipping

Euler's Theorem
- 임의의 rotation 을 x,y,z축의 rotation 3개로 표현하는 것
- Gimble Lock : rotation의 3축 중 2축이 align 되면 한 축의 rotation 정보가 사라짐 : ambiguity : 서로 다른 rotation

Quaternions
- 4차원 복소수(실수항1,허수항3) 2개를 곱하면 3D Rotation 과 같은 효과
- Gimble Lock 이 생기지 않으므로 Animation 에 좋음
- Interpolation (중간값 추정) 에 많은 계산이 들어감

3D Viewing Pipeline
- Modeling Coordinates -> World C. -> Viewing C. -> Projection C. -> Normalized C. -> Device C.

Viewing Coordinate Parameters
- VRP : Viewing Reference Point : VC의 원점, eye point
- VPN : View Plane Normal : VC z축의 Normal(WC의 a Reference Point -> VRP), z_vp=(VRP와 View Plane간의 거리)
- VUP : View Up Vector : VC의 y축을 정의하기 위한 것
- n 은 N의 normal 이고, VUP x n 로 u를 구하고, n x u 로 v 를 구함
- N, VUP은 WC에서 정의하지만 View Plane은 VC에서 정의 : View Point가 바뀔때마다 다시 계산하지 않으려고

World-toViewing Transformation
- VC의 세 축 u,v,n을 WC의 세 축 x,y,z에 align 되도록 rotation 시킴

Projection
- VRC에서 window 정의 (두 점을 주면 됨)
- PRP : Projection Reference Point 를 주면 COP/DOP가 결정됨
- DOP : parallel projection에서 PRP -> CW(Center of Window)
- COP : perspective projection에서 PRP = COP

Parallel Projections
- DOP(Direction of Projection)가 Parallel
- Orthographic Parallel Projection : DOP가 projection plane에 수직
- Oblique Parallel Projection : projection plane이 기본축에 기울어져 있지만 DOP는 projection plane에 수직

Perspective Projections
- 원근감을 주는 방법, 세 축에 대해 vanishing point가 존재함

3D Viewing 순서
- VRP, VPN, VUP을 주고 VRC를 정의
- Projection Type 정의
- VRC 상에 PRP를 정의
- z_vp : view plane distance 지정 (view plane은 VRC 상에서 n축과 수직)
- window size 정의 (두 점의 좌표)
- View Volume 정의 (near, far)
- Projection Viewport Size 정의 (device 상의 window)
- NPC : Normalized Projection Coordinate 로 변환 후 Device로 다시 변환

Normalizing Transformation
- VRP를 WC의 원점으로 translate
- VRC의 u,v,n축을 WC의 x,y,z축으로 rotation
- (Persepective Projection인 경우에만) PRP가 WC의 원점으로 오도록 다시 translate
- DOP가 z축과 평행하도록 shearing
- canonical view volume 이 되도록 tranlate & sacle

Clipping and Homogeneous Coordinates
- Canonical View Volume 으로의 변환이 쉽다
- w가 음수인 경우 이중계산이 될 수 있으므로 양수로 변환 후 clipping을 계산한다.