Bài giảng môn Đồ họa và hiện thực ảo - Bài 2: Các giải thuật sinh các thực thể cơ sở

Rendering Pipeline: 3-D

Các giải thuật sinh các thực thể cơ sở

Transform

Illuminate

Transform

Clip

Project

Rasterize

Le Tan Hung hunglt@it-hut.edu.vn 0913030731

Rendering Pipeline Rendering Pipeline

Framebuffer Framebuffer

Display Display

Model & Camera Model & Camera Parameters Parameters

The Rendering Pipeline: 3-D

Phép biến đổi Transformations

(cid:122) screen space- không gian màn hình (cid:122) model space Không gian mô hình

Các điểm của hệ thống tọa độ 3D thế giới thực •• Các điểm của hệ thống tọa độ 3D thế giới thực

(a.k.a. object space or world space)

Scene graph Object geometry

Các điểm bóng theo mô hình chiếu sáng •• Các điểm bóng theo mô hình chiếu sáng

Modeling Transforms

Các điểm trong mô hình hệ tọa độ Camera hay tọa độ điểm nhìn •• Các điểm trong mô hình hệ tọa độ Camera hay tọa độ điểm nhìn

Lighting Calculations

(cid:122) 3 loại phép biến đổi: – Modeling transforms – Viewing transforms – Projection transforms

Các tọa độ điểm của vùng hình chóp cụt với điểm nhìn xác định •• Các tọa độ điểm của vùng hình chóp cụt với điểm nhìn xác định

Viewing Transform

•• ĐĐiểm 2

theo tọa độ màn hình sau phép chiếu được xén tỉa iểm 2--DD theo tọa độ màn hình sau phép chiếu được xén tỉa

Clipping

Projection Transform

Rendering: Transformations

(cid:122) Modeling transforms

(cid:122) Viewing transform

model w.r.t. each other

the camera

– Size, place, scale, and rotate objects parts of the – Rotate & translate the world to lie directly in front of

(cid:122) Typically place camera at origin (cid:122) Typically looking down -Z axis

– Object coordinates (cid:198) world coordinates

– World coordinates (cid:198) view coordinates

Y

Z

X

Z

1

Rendering: Transformations

(cid:122) Projection transform

(cid:122) All these transformations involve shifting

(cid:122) Distant = small: the pinhole camera model – View coordinates (cid:198) screen coordinates

coordinate systems (i.e., basis sets) (cid:122) Oh yeah, that’s what matrices do… (cid:122) Represent coordinates as vectors, transforms

as matrices

−

θ θ

– Apply perspective foreshortening

sin cos

⎤ ⎥ ⎦

⎡ X ⎢ Y ⎣

θ ⎤ ⎥ θ ⎦

⎡ cos ⎢ sin ⎣

′ ⎤ =⎥ ′ ⎦

⎡ X ⎢ Y ⎣

(cid:122) Multiply matrices = concatenate transforms!

Rendering: Transformations

The Rendering Pipeline: 3-D

(cid:122) Homogeneous coordinates: represent

Result: Result:

•• All vertices of scene in shared 3

D “world” coordinate system All vertices of scene in shared 3--D “world” coordinate system

Scene graph Object geometry

coordinates in 3 dimensions with a 4-vector – Denoted [x, y, z, w]T

Vertices shaded according to lighting model •• Vertices shaded according to lighting model

Modeling Transforms

(cid:122) Note that w = 1 in model coordinates – To get 3-D coordinates, divide by w:

[x’, y’, z’]T = [x/w, y/w, z/w]T

•• Scene vertices in 3

D “view” or “camera” coordinate system Scene vertices in 3--D “view” or “camera” coordinate system

Lighting Calculations

Exactly those vertices & portions of polygons in view frustum •• Exactly those vertices & portions of polygons in view frustum

Viewing Transform

(cid:122) Transformations are 4x4 matrices (cid:122) Why? To handle translation and projection

D screen coordinates of clipped vertices •• 22--D screen coordinates of clipped vertices

Clipping

Projection Transform

Rendering: Ánh sáng - Lighting

The Rendering Pipeline: 3-D

(cid:122) Illuminating a scene: coloring pixels according to

Result: Result:

some approximation of lighting – Global illumination: solves for lighting of the whole

Scene graph Object geometry

•• All vertices of scene in shared 3 system system

scene at once

D “world” coordinate All vertices of scene in shared 3--D “world” coordinate Modeling Transforms

lighting each polygon separately

(cid:122) Interactive graphics (e.g., hardware) does only

local illumination at run time

– Local illumination: local approximation, typically Lighting Calculations Vertices shaded according to lighting model •• Vertices shaded according to lighting model D “view” or “camera” coordinate Scene vertices in 3--D “view” or “camera” coordinate Viewing Transform •• Scene vertices in 3 system system Clipping •• Exactly those vertices & portions of polygons in view Exactly those vertices & portions of polygons in view frustum frustum D screen coordinates of clipped vertices •• 22--D screen coordinates of clipped vertices Projection Transform

2

Rendering: Clipping

Rendering: Xén tỉa - Clipping

(cid:122) Clipping a 3-D primitive returns its intersection

(cid:122) Clipping is tricky!

with the view frustum:

– We will have a whole assignment on clipping

In: 3 vertices In: 3 vertices Out: 6 vertices Out: 6 vertices

Clip

In: 1 polygon In: 1 polygon Out: 2 polygons Out: 2 polygons

Clip

The Rendering Pipeline: 3-D

Modeling: The Basics

Transform

(cid:122) Common interactive 3-D primitives: points,

Illuminate

lines, polygons (i.e., triangles)

Transform

(cid:122) Organized into objects

Clip

Project

– Collection of primitives, other objects – Associated matrix for transformations

Rasterize

(cid:122) Instancing: using same geometry for multiple

objects – 4 wheels on a car, 2 arms on a robot

Rendering Pipeline Rendering Pipeline

Framebuffer Framebuffer

Display Display

Model & Camera Model & Camera Parameters Parameters

Modeling: The Scene Graph

(cid:122) Traverse the scene graph in depth-first order,

concatenating transformations

(cid:122) Đồ thị cảnh scene graph : cây đồ thị lưu trữ đối tượng, quan hệ giũa các đối tượng và các phép biến đổi trên đối tượng đó

(cid:122) Maintain a matrix stack of transformations

Robot

Head

Body

(cid:122) Nút là đối tượng; (cid:122) Cành là các thực thể biến đổi – Tương ứng là các ma trận

Robot

Visited Visited

Leg

Mouth

Eye

Trunk

Arm

Head

Body

Unvisited Unvisited

Foot

Mouth

Eye

Leg

Trunk

Arm

Matrix Matrix Stack Stack Active Active

3

Modeling: The Camera

(cid:122) Finally: need a model of the virtual camera

(cid:122) Camera parameters (FOV, etc) are encapsulated

(cid:122) Field of view, depth of field, distortion, chromatic aberration…

– Can be very sophisticated

in a projection matrix – Homogeneous coordinates (cid:198) 4x4 matrix! – See OpenGL Appendix F for the matrix

(cid:122) Camera pose: position & orientation

(cid:122) The projection matrix premultiplies the viewing

– Captured in viewing transform (i.e., modelview matrix)

matrix, which premultiplies the modeling matrices – Actually, OpenGL lumps viewing and modeling

transforms into modelview matrix

(cid:122) Pinhole camera model – Field of view – Aspect ratio – Near & far clipping planes

– Interactive graphics (OpenGL):

Biểu diễn đoạn thẳng

Rời rạc hoá điểm ảnh (Scan Conversion rasterization)

(cid:122) Biểu diễn tường minh (y-y1)/( x-x1) = ( y2-y1)/( x2-x1)1

y = kx + m

–

k = (y2-y1)/( x2-x1)

– m = y1- kx1

–

Δy = k Δx

(cid:122) Là tiến trình sinh các đối tượng hình học cơ sở bằng phương pháp xấp xỉ dựa trên lưới phân giải của màn hình (cid:122) Tính chất các đối tượng cần đảm bảo : P(x2 , y2)

(cid:122) Biểu diễn không tường minh (y2-y1)x - (x2-x1)y + x2y1 - x1y2 = 0

–

hay rx + sy + t = 0 s = -(x2-x1 )

–

r = (y2-y1) và t = x2y1 - x1y2

– smooth – continuous – pass through specified points – uniform brightness – efficient

P(x1, y1)

(cid:122) Biểu diễn tham biến P(u) = P1 + u(P2 - P1)

u [0,1]

X = x1 + u( x2 - x1 )

Y = y1 + u( y2 - y1 )

Thuật toán DDA (Digital Differential Analizer)

Sinh đường tròn Scan Converting Circles

(cid:122) Explicit: y = f(x)

= ±

Thuậttoán ddaline (x1, y1, x2, y2)

x1, y1, x2, y2 : tọa độ 2 điểm đầu

Giải thuật thông thường DrawLine(int x1,int y1, int x2,int y2, int color) {

cuối

− Usually, we draw a quarter circle by incrementing x from 0 to R in unit steps and solving for +y for each step.

k : hệ số góc x,y,m :biến

(cid:122) Parametric:

begin

- by stepping the angle from 0 to 90 - avoids large gaps but still insufficient.

cos sin

θ θ

m =(x2-x1)/(y2-y1); x = x1; y = y1;

x R = y R = (cid:122) Implicit: f(x) = x2+y2-R2

k = 1/m; putpixel(x,y);

If f(x,y) = 0 then it is on the circle.

f(x,y) > 0 then it is outside the circle. f(x,y) < 0 then it is inside the circle.

while x

float y; int x; for (x=x1; x<=x2; x++) { y = y1 + (x-x1)*(y2-y1)/(x2-x1) WritePixel(x, Round(y), color );

putpixel(round(x),round(y));

end; end;

}} Giải thuật DDA (cid:122) Với 0 < k < 1 xi+1 = xi + 1 yi+1 = yi + k với i=1,2,3....

4

Giải thuật Bresenham

IBM

d2 = y - yi = k(xi +1) + b - yi d1 = yi+1 - y = yi + 1 - k(xi + 1) -

d2 d1

yi+1

(cid:122) 1960 Bresenham thuộc

(cid:122) điểm gần với đường thẳng dựa trên độ phân giai hưu hạn

= -2k(xi + 1) + 2yi - 2b + 1

xi+1

(cid:122) loại bỏ được các phép toán chia và phép toán làm tròn như ta đã thấy trong gỉai thuật DDA (cid:122) If d1 ≤ d2 => yi+1 = yi + 1 else d1 > d2 => yi+1 = yi (cid:122) D = d1 - d2 (cid:122) Xét đoạn thẳng với 0 < k < 1

(cid:122) Pi = ΔxD = Δx (d1 - d2)

Giải thuật Bresenham

Giải thuật trung điểm-Midpoint

(cid:122) Jack Bresenham 1965 / Pitteway 1967 (cid:122) VanAken áp dụng cho việc sinh các đường

Pi = -2Δyxi + 2Δxyi + c Pi+1 - Pi

thẳng và đường tròn 1985

= -2Δy(xi+1 - xi) + 2Δx(yi+1 - yi)

(cid:122) Các công thức đơn giản hơn, tạo được các

yi+1

điểm tương tự như với Bresenham

(cid:122) d = F (xi + 1, yi + 1/2) là trung điểm của đoạn

M

(cid:122) Nếu Pi ≤ 0 ⇒ yi+1 = yi + 1 Pi+1 = Pi - 2Δy + 2Δx

(cid:122) Nếu Pi > 0 ⇒ yi+1 = yi

(cid:122) Việc so sánh, hay kiểm tra M sẽ được thay

Pi+1 = Pi - 2Δy

A M B ( xi , yi )

xi

xi+1

bằng việc xét giá trị d. – Nếu d > 0 điểm B được chọn, yi+1 = yi – nếu d < 0 điểm A được chọn. ⇒ yi+1 = yi +

P1 = Δx(d1 - d2) P1 = -2Δy + Δx

– Trong trường hợp d = 0 chúng ta có thể

chọn điểm bất kỳ hoặc A, hoặc B.

Bresenham’s Algorithm: Midpoint Algorithm

(cid:122) If di > 0 then chọn điểm A ⇒ trung điểm tiếp theo sẽ có dạng:

(cid:122) Sử dụng phương pháp biểu diễn không tường minh

on line

) 2 ++

x i

y i

( xa i

1 +

3 2

⎛ ⎜ ⎝

⎞ d =⇒⎟ ⎠

⎛ yb ⎜ i ⎝

⎞ +⎟ ⎠

0 ⇒<+

d i

0 ⇒>+

) yx , i i ) yx , i i )i yx , i

ax 0=+ by c + by c 0 + ⇒=+ i by i by i

ax i ax i ax i

( ( ( (cid:122) Tại mỗi trung điểm của đoạn thẳng giá trị được tính

above line below line

là:

) 1 ++

( xa i

1 2

⎛ yb ⎜ i ⎝

⎞ +⎟ ⎠

(cid:122) Chúng ta gọi di là biến quyết định của bước thứ i

5

Midpoint Line Algorithm

Bresenham’s Algorithm: Midpoint Algorithm

(cid:122) if di < 0 then chọn điểm B và trung điểm mới là

) 2 ++

x i

y i

( xa i

1 +

1 2

(cid:122) Ta có:

⎞ ⇒⎟ ⎠

⎛ ⎜ ⎝

⎞ +⎟ ⎠

⎛ yb ⎜ i ⎝

initialisation

y =Δ=

−

=Δ−=

−

Cx +

y end x end

y start x start

y Δ x Δ

xCc Δ=

⎫ ⎪ where ⎬ ⎪ ⎭

(cid:122) Ðiểm đầu

dx = x_end-x_start dy = y_end-y_start d = 2*dy-dx x = x_start y = y_start while x < x_end if d <= 0 then choose B d = d+(2*dy) x = x+1 else

( xa

) 1 ++

start

1 2

⎛ ⎜ ⎝

⎞ ⇒⎟ ⎠

a ++=

⎛ yb ⎜ ⎝ +

a ++

[ ax

]

start

b 2

⎞ +⎟ ⎠ b 2

choose A d = d+2*(dy-dx) x = x+1 y = y+1 endif SetPixel(x,y) endwhile

B¾t ®Çu

Midpoint Circle Algorithm

Giải thuật Bresenham's Midpoint

x = x1 ; y = y1; dx = x2 - x1; dy = y2 - y1; d = dy - dx/2;

(cid:122) Sử dụng phương pháp biểu diễn

(cid:122) d = a(xi + 1) + b(yi + 1/2) + c (cid:122) Nếu điểm được chọn là B thi M sẽ tang

không tường minh trong giải thuật

−

02 =

(

)

(

)

x c

y c

Putpixel (x ,y);

(cid:122) Thực hiện giải thuật trên 1/8

theo x một đơn vị – di +1 = F(xi +2, yi + 1/2)

= a(xi +2) + b(yi + 1/2) + c

d <= 0

– di = a(xi + 1) + b(yi + 1/2) + c

đường tròn và lấy đối xứng xho các góc còn lại.

d = d + dy - dx

x = x + 1

(cid:122) Với di là giá trị của đường tròn tại

yes

một điểm bất kỳ ta có

d = d + dy

y = y + 1

inside circle

yes

x < x2

d i

(cid:122) Nếu điểm A được chọn thi` M tăng theo 2 hướng x và y với cùng một đơn vị. di + 1 = F (xi + 2, yi + 3/2) – = a(xi + 2) + b(yi +3/2) + c – di + 1 = di + a + b.

on circle outside circle

( if 0 ( if 0 ( if 0

) is ) is ) is

yx , i i yx , i i yx , i i

< ⎧ ⎪ = ⎨ ⎪ > ⎩

(cid:190) Với a + b = dy - dx.

KÕt thóc

Midpoint Circle Algorithm

(cid:122) Again, as with the line algorithm, the choice of A or B can be

used to determine the new value of di+1

(cid:122) As with the line, we determine the value of the decision variable by substituting the mid-point of the next pixel into the implicit form of the circle:

−

(

) 1

x i

y i

variable:

1 2

⎛ ⎜ ⎝

2 ⎞ −⎟ ⎠

−

(cid:122) If di < 0 we choose pixel A otherwise we choose pixel B

) 2

(

y i

x i

1 +

1 2

– Note: we currently assume the circle is centered at the origin

(cid:122) If A chosen then next midpoint has the following decision 2 ⎞ −⎟ ⎠

⎞ d =⇒⎟ i ⎠

⎛ ⎜ ⎝

⎛ ⎜ ⎝ 3

x i

(cid:122) Otherwise if B is chosen then the next decision variable is given

by:

−

(

) 2

x i

y i

x i

y i

1 +

3 2

2 ⎞ −⎟ ⎠

⎞ d =⇒⎟ i ⎠

⎛ ⎜ ⎝

⎛ ⎜ ⎝ 2

3 2 5

−

d i

x i

y i

6

Midpoint Circle Algorithm

(cid:122) If we assume that the radius is an integral value, then the first

stop at diagonal ⇒ end of octant

initialisation

r +−

−

1 4

1 2

⎞ −⎟ ⎠

⎞ d +=⇒⎟ 0 ⎠

⎛ ⎜ ⎝

pixel drawn is (0, r) and the initial value for the decision variable is given by: ⎛ r ,1 ⎜ ⎝

5 −= 4 (cid:122) Although the initial value is fractional, we note that all other

d = 1-r x = 0 y = r while y < x if d < 0 then choose A d = d+2*x+3 x = x+1 else

values are integers. ⇒ we can round down:

−=10

Translate to the circle center

choose B d = d+2*(x-y)+5 x = x+1 y = y-1 endif SetPixel(cx+x,cy+y) endwhile

Scan Converting Ellipses: Algorithm

Scan Converting Ellipses

A M B

tiep tuyen = -1 gradient

F x y ( ,

)

2 b x

2 a y

2 2 a b

−

B C M

i

(cid:122) Firstly we divide the quadrant into two regions (cid:122) Boundary between the two regions is

– the point at which the curve has a slope of -1 – the point at which the gradient vector has the i and j components of

lies in the first quadrant, the other three quadrants can be drawn by symmetry

grad F x y ( , )

F x /

F y /

2 b x 2

(cid:122) 2a is the length of the major axis along the x axis. (cid:122) 2b is the length of the minor axis along the y axis. (cid:122) The midpoint can also be applied to ellipses. (cid:122) For simplicity, we draw only the arc of the ellipse that equal magnitude

i

2 a y 2

j

= ∂

i ∂ +∂

j ∂ =

Ellipses: Algorithm (cont.)

Ký tự Bitmap

(cid:122) At the next midpoint, if a2(yp-0.5)<=b2(xp+1), we switch region 1=>2 (cid:122) In region 1, choices are E and SE

với một font chư cho trước là một bitmap chữ nhật nhỏ

(cid:122) Trên cơ sỏ định nghĩa mỗi ký tự

– Initial condition: dinit = b2+a2(-b+0.25) – For a move to E, dnew = dold+DeltaE with DeltaE = b2(2xp+3) – For a move to SE, dnew = dold+DeltaSE with

(cid:122) Font/typeface: set of character

shapes (cid:122) fontcache

– các ký tự theo chuỗi liên tiếp nhau

(cid:122) In region 2, choices are S and SE

trong bộ nhớ (cid:122) Dạng cơ bản

DeltaSE = b2(2xp+3)+a2(-2yp+2)

ab

–

– Initial condition: dinit = b2(xp+0.5)2+a2((y-1)2-b2) – For a move to S, dnew = dold+Deltas with Deltas = a2(-2yp+3) – For a move to SE, dnew = dold+DeltaSE with

(thường N, nghiêng I, đậm B, nghiêng đậm B+I)

(cid:122) Stop in region 2 when the y value is zero.

– Also colour, size, spacing and

orientation

DeltaSE = b2(2xp+2)+a2(-2yp+3) (cid:122) Thuộc tính

7

Cấu trúc font chữ

Ký tự vector

(cid:122) Xây dựng theo phương

pháp định nghĩa các ký tự bởi đường cong mềm bao ngoài của chúng.

toán

Typedef struct { int leftx, int width; } Char location; //Vị trí của text (cid:122) Tốn kém nhất về mặt tính

(cid:122) Chất lượngcao Typedef struct { CacheId; Heiglit; CharSpace; // Độ rộng chữ // Khoảng cách giữa các ký tự Charlocation Table [128]; } fontcache

Giải thuật đường quét sinh đa giác Polygon Scan Conversion

So sánh

(cid:122) Tồn tại rất nhiều giải thuật sinh đa giác. (cid:122) Mỗi giải thuật phục vụ cho 1 loại đa giác nhất

tự ( copypixel)

(cid:122) Phức tạp (Tính toán (cid:122) Đơn giản trông việc sinh ký

định: – some algorithms allow triangular polygons only – others require that the polygons are convex and non self-

scale) đòi hỏi lưu trữ thêm

intersecting and have no holes

(cid:122) Lưu trữ lớn (cid:122) Các phép biến đổi (I,B,

phương trình) (cid:122) Lưu trữ gọn nhẹ (cid:122) Các phép biến đổi dựa vào các công thức biến đổi (cid:122) Kích thước phụ thuôc vào môi trường ( ko có kích thước cố định)

(cid:122) Kích thước không dổi

triangular convex non-convex self-intersecting religious

Polygon Scan Conversion

(cid:122) Polygon scan conversion là giải thuật chung kinh điển cho các

loại khác nhau

(cid:122) Dùng giải thuật (trung điểm) để xác định các điểm biên cho mỗi đa giác theo thứ tự tăng của x.

(cid:122) Các diểm phải:

– Không bị chia sẻ bởi các đa giác

(cid:122) Cho mỗi đoạn thẳng quét, chúng ta xác định các cạnh của đa giác cắt đoạn thẳng compute spans representing the interior portions of the polygons along this scan-line and fill the associated pixels.

(cid:122) This represents the heart of a scan-line rendering algorithm

– Các đa giác chỉ toàn các điểm

lân cận

used in many commercial products including Renderman and 3D Studio MAX.

(cid:122) Đảm bảo các đa giác chia sẻ điểm biên mà không chia sẻ các điểm ảnh bên trong của mình.

cạnh( điểm biên)

8

Polygon Scan Conversion

– Xác định giao của đường thẳng quét với cạnh đa giác – Sắp xếp các giao điểm theo mức độ tăng dần của x value – Điền các điểm ảnh vào giữa cặp các điểm x

integer x value is on right = exterior (cid:122) Thủ tục chung:

– if intersection has fractional x value, do we round up or down? (cid:122) if inside (on left of span) round up, if outside (on right) round down

– what happens if intersection is at an integer x value? (cid:122) if on left of span assume its interior otherwise exterior

– how do we handle shared vertices?

(cid:122) ignore pixel associated with ymax of an edge

– how do we handle horizontal edges?

(cid:122) handled as a result of previous rule (lower edges not drawn)

(cid:122) Need to handle 4 cases to prevent pixel sharing:

ymax not included horizontal edge removed rounded down for A rounded up for B