Bài giảng Computer graphics and virtual reality - Bài 2: Các giải thuật sinh các thực thể cơ sở - Lê Tấn Hùng

1Các giải thuật sinh các thực thể 
cơ sở
Le Tan Hung
hunglt@it-hut.edu.vn
0913030731
Rendering Pipeline: 3-D
Transform
Illuminate
Transform
Clip
Project
Rasterize
Model & Camera
Parameters Rendering Pipeline Framebuffer Display
The Rendering Pipeline: 3-D
Scene graph
Object geometry
Lighting
Calculations
Clipping
• Các điểm của hệ thống tọa độ 3D thế giới thực 
• Các điểm bóng theo mô hình chiếu sáng
• Các điểm trong mô hình hệ tọa độ Camera hay tọa độ điểm nhìn
• 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
• Điểm 2-D theo tọa độ màn hình sau phép chiếu được xén tỉa
Modeling
Transforms
Viewing
Transform
Projection
Transform
Phép biến đổi Transformations
z screen space- không gian màn hình
z model space Không gian mô hình 
(a.k.a. object space or world space)
z 3 loại phép biến đổi:
– Modeling transforms
– Viewing transforms
– Projection transforms
Rendering: Transformations
z Modeling transforms
– Size, place, scale, and rotate objects parts of the 
model w.r.t. each other
– Object coordinates Æ world coordinates
Z
X
Y
X
Z
Y
Rendering: Transformations
z Viewing transform
– Rotate & translate the world to lie directly in front of 
the camera
z Typically place camera at origin
z Typically looking down -Z axis
– World coordinates Æ view coordinates
2Rendering: Transformations
z Projection transform
– Apply perspective foreshortening
z Distant = small: the pinhole camera model
– View coordinates Æ screen coordinates
Rendering: Transformations
z All these transformations involve shifting 
coordinate systems (i.e., basis sets)
z Oh yeah, that’s what matrices do
z Represent coordinates as vectors, transforms 
as matrices
z Multiply matrices = concatenate transforms!
⎥⎦
⎤⎢⎣
⎡⎥⎦
⎤⎢⎣
⎡ −=⎥⎦
⎤⎢⎣
⎡
′
′
Y
X
Y
X
θθ
θθ
cossin
sincos
Rendering: Transformations
z Homogeneous coordinates: represent 
coordinates in 3 dimensions with a 4-vector
– Denoted [x, y, z, w]T
z 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
z Transformations are 4x4 matrices
z Why? To handle translation and projection
The Rendering Pipeline: 3-D
Modeling
Transforms
Scene graph
Object geometry
Lighting
Calculations
Viewing
Transform
Clipping
Projection
Transform
Result:
• All vertices of scene in shared 3-D “world” coordinate system
• Vertices shaded according to lighting model
• Scene vertices in 3-D “view” or “camera” coordinate system
• Exactly those vertices & portions of polygons in view frustum
• 2-D screen coordinates of clipped vertices
Rendering: Ánh sáng - Lighting
z Illuminating a scene: coloring pixels according to 
some approximation of lighting
– Global illumination: solves for lighting of the whole 
scene at once
– Local illumination: local approximation, typically 
lighting each polygon separately
z Interactive graphics (e.g., hardware) does only 
local illumination at run time
The Rendering Pipeline: 3-D
Modeling
Transforms
Scene graph
Object geometry
Lighting
Calculations
Viewing
Transform
Clipping
Projection
Transform
Result:
• All vertices of scene in shared 3-D “world” coordinate 
system
• Vertices shaded according to lighting model
• Scene vertices in 3-D “view” or “camera” coordinate 
system
• Exactly those vertices & portions of polygons in view 
frustum
• 2-D screen coordinates of clipped vertices
3Rendering: Clipping
z Clipping a 3-D primitive returns its intersection 
with the view frustum:
Rendering: Xén tỉa - Clipping
z Clipping is tricky!
– We will have a whole assignment on clipping
In: 3 vertices
Out: 6 verticesClip
Clip In: 1 polygon
Out: 2 polygons
The Rendering Pipeline: 3-D
Transform
Illuminate
Transform
Clip
Project
Rasterize
Model & Camera
Parameters Rendering Pipeline Framebuffer Display
Modeling: The Basics
z Common interactive 3-D primitives: points, 
lines, polygons (i.e., triangles)
z Organized into objects
– Collection of primitives, other objects
– Associated matrix for transformations
z Instancing: using same geometry for multiple 
objects 
– 4 wheels on a car, 2 arms on a robot
Modeling: The Scene Graph
z Đồ 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 đó
z Nút là đối tượng;
z Cành là các thực thể biến đổi
– Tương ứng là các ma trận Robot
BodyHead
ArmTrunkLegEyeMouth
Modeling: The Scene Graph
z Traverse the scene graph in depth-first order, 
concatenating transformations
z Maintain a matrix stack of transformations
ArmTrunkLegEyeMouth
Head Body
Robot
Foot
Matrix
Stack
Visited
Unvisited
Active
4Modeling: The Camera
z Finally: need a model of the virtual camera
– Can be very sophisticated
z Field of view, depth of field, distortion, chromatic aberration
– Interactive graphics (OpenGL):
z Camera pose: position & orientation
– Captured in viewing transform (i.e., modelview matrix)
z Pinhole camera model
– Field of view
– Aspect ratio
– Near & far clipping planes
Modeling: The Camera
z Camera parameters (FOV, etc) are encapsulated 
in a projection matrix
– Homogeneous coordinates Æ 4x4 matrix!
– See OpenGL Appendix F for the matrix
z The projection matrix premultiplies the viewing 
matrix, which premultiplies the modeling matrices
– Actually, OpenGL lumps viewing and modeling 
transforms into modelview matrix
Rời rạc hoá điểm ảnh
(Scan Conversion rasterization)
z 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
z Tính chất các đối tượng cần đảm bảo :
– smooth
– continuous
– pass through specified points
– uniform brightness
– efficient
Biểu diễn đoạn thẳng
z 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 
z 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 
z 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 ) m
P(x1, y1)
P(x2 , y2)
u
Sinh đường tròn
Scan Converting Circles
z Implicit: f(x) = x2+y2-R2
z Explicit: y = f(x)
z Parametric:
2 2y R x= ± −
cos
sin
x R
y R
θ
θ
=
=
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.
Usually, we draw a quarter circle by 
incrementing x from 0 to R in unit steps 
and solving for +y for each step.
- by stepping the angle from 0 to 90
- avoids large gaps but still insufficient.
Thuật toán DDA 
(Digital Differential Analizer)
Giải thuật DDA
z Với 0 < k < 1 
xi+1 = xi + 1 
yi+1 = yi + k
với i=1,2,3....
Thuậttoán ddaline (x1, y1, x2, y2)
x1, y1, x2, y2 : tọa độ 2 điểm đầu
cuối
k : hệ số góc
x,y,m :biến
begin
m =(x2-x1)/(y2-y1);
x = x1;
y = y1;
k = 1/m;
putpixel(x,y);
while x<x2 
begin
x = x+1;
y = y+k;
putpixel(round(x),round(y));
end; end;
Giải thuật thông thường
DrawLine(int x1,int y1, int x2,int y2, 
int color)
{
float y;
int x;
for (x=x1; x<=x2; x++) 
{
y = y1 + (x-x1)*(y2-y1)/(x2-x1)
WritePixel(x, Round(y), color );
}}
5Giải thuật Bresenham
z 1960 Bresenham thuộc
IBM 
z điểm gần với đường thẳng
dựa trên độ phân giai hưu
hạn
z 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 
z Xét đoạn thẳng với 0 < k < 1
0 1 2
0
1
2 d2
d1
Giải thuật Bresenham
d2 = y - yi = k(xi +1) + b - yi
d1 = yi+1 - y = yi + 1 - k(xi + 1) -
b
z If d1 ≤ d2 => yi+1 = yi + 1
else d1 > d2 => yi+1 = yi
z D = d1 - d2
= -2k(xi + 1) + 2yi - 2b + 1
z Pi = ΔxD = Δx (d1 - d2)
d1
d2
xi xi+1
yi
yi+1
Pi = -2Δyxi + 2Δxyi + c
Pi+1 - Pi
= -2Δy(xi+1 - xi) + 2Δx(yi+1 - yi) 
z Nếu Pi ≤ 0 ⇒ yi+1 = yi + 1
Pi+1 = Pi - 2Δy + 2Δx
z Nếu Pi > 0 ⇒ yi+1 = yi
Pi+1 = Pi - 2Δy 
P1 = Δx(d1 - d2)
P1 = -2Δy + Δx
Giải thuật Bresenham
yi+1
M
( xi , yi ) 
xi xi+1
Giải thuật trung điểm-Midpoint 
z Jack Bresenham 1965 / Pitteway 1967 
z VanAken áp dụng cho việc sinh các đường
thẳng và đường tròn 1985
z Các công thức đơn giản hơn, tạo được các
điểm tương tự như với Bresenham
z d = F (xi + 1, yi + 1/2) là trung điểm của đoạn
AB
z Việc so sánh, hay kiểm tra M sẽ được thay
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 + 
1
– 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.
A
M
B
Bresenham’s Algorithm: Midpoint 
Algorithm
z Sử dụng phương pháp biểu diễn không tường minh
z Tại mỗi trung điểm của đoạn thẳng giá trị được tính
là: 
z Chúng ta gọi di là biến quyết định của bước thứ i
0=++ cbyax ( )
( )
( )iiii
iiii
iiii
yxcbyax
yxcbyax
yxcbyax
,0
,0
,0
⇒>++
⇒<++
⇒=++ on line
above line
below line
( ) cybxad iii +⎟⎠
⎞⎜⎝
⎛ +++=
2
11
Bresenham’s Algorithm: Midpoint 
Algorithm
z If di > 0 then chọn điểm A⇒ trung điểm tiếp theo sẽ có dạng:
( )
bad
cybxadyx
i
iiiii
++=
+⎟⎠
⎞⎜⎝
⎛ +++=⇒⎟⎠
⎞⎜⎝
⎛ ++ + 2
32
2
3,2 1
6Bresenham’s Algorithm: Midpoint 
Algorithm
z if di < 0 then chọn điểm B và trung điểm mới là
z Ta có:
z Ðiểm đầu
( )
[ ]
2
2
11
2
1,1
bacbyax
cybxadyx
startstart
startstartstartstartstart
++++=
+⎟⎠
⎞⎜⎝
⎛ +++=⇒⎟⎠
⎞⎜⎝
⎛ ++
( )
ad
cybxadyx
i
iiiii
+=
+⎟⎠
⎞⎜⎝
⎛ +++=⇒⎟⎠
⎞⎜⎝
⎛ ++ + 2
12
2
1,2 1
Cx
x
yy
xCc
xxxb
yyya
startend
startend
+Δ
Δ=
⎪⎭
⎪⎬
⎫
Δ=
−=Δ−=
−=Δ=
 where
2
0 ba ++=
Midpoint Line Algorithm
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
d = d+(2*dy)
x = x+1
else
d = d+2*(dy-dx)
x = x+1
y = y+1
endif
SetPixel(x,y)
endwhile
initialisation
choose B
choose A
Giải thuật
Bresenham's Midpoint
z d = a(xi + 1) + b(yi + 1/2) + c
z Nếu điểm được chọn là B thi M sẽ tang 
theo x một đơn vị
– di +1 = F(xi +2, yi + 1/2)
= a(xi +2) + b(yi + 1/2) + c
– di = a(xi + 1) + b(yi + 1/2) + c
z 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.
¾ Với a + b = dy - dx.
d <= 0
B¾t ®Çu
x = x1 ;
y = y1;
dx = x2 - x1;
dy = y2 - y1;
d = dy - dx/2;
Putpixel (x ,y);
x < x2
KÕt thóc
d = d + dy
d = d + dy - dx
y = y + 1
yes
no
No
yes
x = x + 1
Midpoint Circle Algorithm
z Sử dụng phương pháp biểu diễn
không tường minh trong giải thuật
z Thực hiện giải thuật trên 1/8 
đường tròn và lấy đối xứng xho
các góc còn lại.
z Với di là giá trị của đường tròn tại
một điểm bất kỳ ta có
( ) ( ) 0222 =−−+− ryyxx cc
( )
( )
( )
circle outside is , if 0
circleon is , if 0
circle inside is , if 0
⎪⎩
⎪⎨
⎧
>
=
<
=
ii
ii
ii
i
yx
yx
yx
d
Midpoint Circle Algorithm
z 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:
z If di < 0 we choose pixel A otherwise we choose pixel B
– Note: we currently assume the circle is centered at the origin
( ) 222
2
11 ryxd iii −⎟⎠
⎞⎜⎝
⎛ −++=
Midpoint Circle Algorithm
z Again, as with the line algorithm, the choice of A or B can be 
used to determine the new value of di+1
z If A chosen then next midpoint has the following decision 
variable:
z Otherwise if B is chosen then the next decision variable is given 
by:
( )
32
2
12
2
1,2 2
2
2
1
++=
−⎟⎠
⎞⎜⎝
⎛ −++=⇒⎟⎠
⎞⎜⎝
⎛ −+ +
ii
iiiii
xd
ryxdyx
( )
522
2
32
2
3,2 2
2
2
1
+−+=
−⎟⎠
⎞⎜⎝
⎛ −++=⇒⎟⎠
⎞⎜⎝
⎛ −+ +
iii
iiiii
yxd
ryxdyx
7Midpoint Circle Algorithm
z If we assume that the radius is an integral value, then the first 
pixel drawn is (0, r) and the initial value for the decision variable 
is given by:
z Although the initial value is fractional, we note that all other 
values are integers.
⇒ we can round down:
r
rrrdr
−=
−⎟⎠
⎞⎜⎝
⎛ +−+=⇒⎟⎠
⎞⎜⎝
⎛ −
4
5
4
11
2
1,1 220
rd −=10
Midpoint Circle Algorithm
d = 1-r
x = 0
y = r
while y < x 
if d < 0 then
d = d+2*x+3
x = x+1
else
d = d+2*(x-y)+5
x = x+1
y = y-1
endif
SetPixel(cx+x,cy+y)endwhile
initialisation
choose B
choose A
Translate to the circle center
stop at diagonal ⇒ end of octant
Scan Converting Ellipses
z 2a is the length of the major axis along the x axis.
z 2b is the length of the minor axis along the y axis.
z The midpoint can also be applied to ellipses.
z For simplicity, we draw only the arc of the ellipse that 
lies in the first quadrant, the other three quadrants can 
be drawn by symmetry
2 2 2 2 2 2( , ) 0F x y b x a y a b= + − =
Scan Converting Ellipses: Algorithm
z Firstly we divide the quadrant into two regions
z 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 
equal magnitude 
2 2( , ) / / 2 2grad F x y F x F y b x a y=∂ ∂ +∂ ∂ = +i j i j
A
M tiep tuyen = -1
B gradient
B C
M
i
Ellipses: Algorithm (cont.)
z At the next midpoint, if a2(yp-0.5)2
z In region 1, choices are E and SE
– 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 
DeltaSE = b2(2xp+3)+a2(-2yp+2)
z In region 2, choices are S and SE
– 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 
DeltaSE = b2(2xp+2)+a2(-2yp+3)
z Stop in region 2 when the y value is zero. 
Ký tự Bitmap
z Trên cơ sỏ định nghĩa mỗi ký tự
với một font chư cho trước là một
bitmap chữ nhật nhỏ
z Font/typeface: set of character 
shapes
z fontcache
– các ký tự theo chuỗi liên tiếp nhau
trong bộ nhớ
z Dạng cơ bản
– (thường N, nghiêng I, đậm B, 
nghiêng đậm B+I) 
z Thuộc tính
– Also colour, size, spacing and 
orientation
ab
8Cấu trúc font chữ
Typedef struct
{
int leftx, 
int width; 
} Char location; //Vị trí của text
Typedef struct
{
CacheId;
Heiglit; // Độ rộng chữ
CharSpace; // Khoảng
cách giữa các ký tự
Charlocation Table [128];
} fontcache
Ký tự vector
z 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. 
z Tốn kém nhất về mặt tính
toán
z Chất lượngcao
So sánh
z Đơn giản trông việc sinh ký
tự ( copypixel) 
z Lưu trữ lớn
z Các phép biến đổi (I,B, 
scale) đòi hỏi lưu trữ thêm
z Kích thước không dổi
z Phức tạp (Tính toán
phương trình)
z Lưu trữ gọn nhẹ
z Các phép biến đổi dựa vào
các công thức biến đổi
z Kích thước phụ thuôc vào
môi trường ( ko có kích
thước cố định)
Giải thuật đường quét sinh đa giác
Polygon Scan Conversion
z Tồn tại rất nhiều giải thuật sinh đa giác.
z Mỗi giải thuật phục vụ cho 1 loại đa giác nhất 
định:
– some algorithms allow triangular polygons only
– others require that the polygons are convex and non self-
intersecting and have no holes
triangular convex non-convex self-intersecting religious
Polygon Scan Conversion
z Polygon scan conversion là giải thuật chung kinh điển cho các 
loại khác nhau
z 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.
z This represents the heart of a scan-line rendering algorithm
used in many commercial products including Renderman and 
3D Studio MAX.
Polygon Scan Conversion
z 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.
z Các diểm phải:
– Không bị chia sẻ bởi các đa giác
lân cận
– Các đa giác chỉ toàn các điểm
cạnh( điểm biên)
z Đả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.
9Polygon Scan Conversion
z Thủ tục chung:
– 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
z Need to handle 4 cases to prevent pixel sharing:
– if intersection has fractional x value, do we round up or down?
z if inside (on left of span) round up, if outside (on right) round down
– what happens if intersection is at an integer x value?
z if on left of span assume its interior otherwise exterior
– how do we handle shared vertices?
z ignore pixel associated with ymax of an edge 
– how do we handle horizontal edges?
z handled as a result of previous rule (lower edges not drawn)
Polygon Scan Conversion
rounded down for A
rounded up for B
integer x value is on
right = exterior
ymax not 
included
horizontal edge
removed
Polygon Scan Conversion
z Determining intersections with polygon edges is expensive
– rather than re-computing all intersections at each iteration, use 
incremental calculations
– i.e. if we intersect edge e on scan-line i then it is likely we will 
intersect the edge on scan-line i+1 (this is known as edge-
coherence)
z Assume slope of the edge > 1 (other edges obtained via 
symmetries)
– incremental DDA calculation was:
– slope m is given by
– note that numerator and denominator are integral ⇒ we can use 
integer DDA.
m
xxyy iiii
1,1 11 +=+= ++
( )
( )startend
startend
xx
yym −
−=