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

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 −
−=