zzun.net

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 연산만 있으므로 매우 빠르다.

dx = x1-x0; dy = y1-y0; d = 2 * dy - dx;
incrE = 2 * dy; incrNE = 2 * (dy - dx);
x = x0; y = y0;
write(x, y);
while ( x < x1 ) {
  if d<= 0
    d += incrE;
  else
    d += incrNE; y++;
  x++
  write(x, y);
}

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을 계산한다.

Comment +3

Computer Architecture
SNU CSE / 2007 Spring / Prof. 민상렬

* Design Techniques (ex. Pipelining, Cache, Multiprocessor)
1. Engineering methodology
- common case를 optimize / rare case를 correct하게
2. Correctness criteria
- pipeline, cache 등의 테크닉을 사용하더라도 가장 simple한 디자인(테크닉 없는)에서와 같은 결과가 나오게
3. Evaluation methods
- Time(Resoponse time)과 Rate(throughput)
4. Technology trends
- VLSI에서 트랜지스터가 작아질 경우 : 집적도 향상 / signal path가 짧아짐 / switch 시간이 짧아짐(clock rate 향상)
- VLSI 기술 향상 속도에 비해 몇 배의 속도로 Computer Architecture가 발전하고 있음.

ISA design goals : max(Performance), min(Cost), min(Power Consumptioon)
ISA design constraint : Compiler 지원, OS 지원

CISC to RISC
- 과거엔 Memory 속도가 느렸기 때문에 하나의 instruction으로 최대한 많은 작업을 해야 했음(CISC)
- Cache, Pipelining, Single Chilp Processor의 등장으로 RISC로 발전함.

IBM System/360 : 최초로 한 ISA에 여러 Implemenatation : 다양한 성능의 욕구를 충족시킬 수 있게 됨

MIPS instructions
- addu (add unsigned) : overflow가 발생할 수 없음
- addi addiu는 있으나 subi subiu가 없는 이유 : addi addiu로 가능하고, I-format의 개수가 제한되어 있으므로(2^6)
- sll srl sra : logical shift는 0으로 채우고, arithmatic shift는 sign bit로 채움
- sh sb lh lb : Register의 4 byte 중 Least Significant Byte를 보내고 받음
- lhu (load halfword unsinged) : 읽어온 정보를 bit stream으로 취급하여 남은 16bit를 0으로 채움

MIPS Addressing Modes
- PC-relative branch : PC +- immediate
- Pseudo-direct addressing jump : PC 4bit + immediate 26bit + 00(2 bit)
- Addressing Mode가 복잡하면 pipelining이 어려우므로 RISC에서는 Load/Store Architecture

MIPS Register Convention
- for Interoperability between different compilers on the same ISA : seperate compilation
- $fp (frame pointer) : 같은 function 내에서도 $sp는 시간에 따라 바뀌므로 reliable pointer가 필요함

MIPS Calling Convention
- Hybrid between Caller-Save and Callee-Save : why? Evaluation method : min(Load/Store instructions)
- $a0-3, $v0-1, $ra는 무조건 caller-save : call(jal) 순간에 해당 레지스터의 값이 덮어써지므로 callee는 불가능

Comment +0

2007 Spring / SNU CSE / Prof. 이재진
Textbook - Compilers : Principles, Techniques and Tools 2/E by Aho, Lam, Sethi, Ullman (Pearson International Edition)

Chapter 2. A Simple Syntax-Directed Translator
This chapter is about the front end of a compiler : lexical analysis, parsing, intermediate code generation
Syntax-directed translator : infix arithmetic expressions into postfix expressions

2.1 Introduction
Three-address instruction : x = y op z (op:binary operator, x,y,z:addresses)

2.2 Syntax Definition
Context-free grammar (wikipedia)
ex) stmt → if ( expr ) stmt else stmt
  such a rule is called a production
  terminals : if else ( )
  nonterminals : stmt expr
  context-free : nonterminal → a sequence of terminals and/or nonterminals

2.2.5 Associativity of Operators
Left-associative : 9-5-2 : 5 belongs to the left - operator : (9-5)-2
Right-associative : a=b=c : b belongs to the rihgt = opertor : a=(b=c)

2.2.6 Precedence of Operators
Example grammar : * / have higher precedence than + -
expr → expr + term | expr - term | term
term → term * factor | term / factor | factor
factor → digit | ( expr )

2.3 Syntax-Directed Translation
Attributes : any quantity associated with a programming construct. : X.a (X:grammar symbol, a:attribute)
Translation Scheme : a notation for attaching program fragments to the productions of a grammar.

2.3.1 Postfix Notation
No parentheses are need in postfix notation.
ex) 952+-3*
1. find leftmost operator : +
2. its operands : 5 and 2 : 9(52+)-3* = 97-3*
3. next leftmost operator : -
4. its operands : 9 and 7 : (97-)3* = 23*
5. 23* = 6

2.3.2 Syntehsized Attributes
an attribute that its value at a parse-tree node N is determined from attribute values at the children of N and at N itself (bottom-up)
anotated parse tree : showing the attribute values at eache node

2.3.3 Simple Syntax-Directed Definitions
THE SAME ORDER concatenation of the translations of the nonterminals as in the production

2.3.5  Translations Schemes
semantic actions : program fragments : {print('+')}
need to perform a left-to-right depth-first postorder traversal

(to be continued)

Comment +0


티스토리 툴바