KHoa CNTT-DDHBK Hà nội

0913030731
1
(c) SE/FIT/HUT 2002
Bài 2:
Các giảithuật sinh
các thực thể cơ sở
Le Tan Hung

0913030731
(c) SE/FIT/HUT 2002
2
Giảithuậtxâydựng các
thựcthể cơ sở
 Giảithuậtsinhđường thẳng – Line
 Giảithuậtsinhđường tròn - Circle
 Giảithuật VanAken sinh Ellipse
 Giảithuậtsinhđagiác
 Giảithuậtsinhkýtự
(c) SE/FIT/HUT 2002
3
Rờirạchoáđiểm ảnh
(Scan Conversion rasterization)
 Là tiếntrìnhsinhcácđốitượng hình họccơ sở bằng phương
pháp xấpxỉ dựatrênlưới phân giảicủamànhình
 Tính chất các đốitượng cần đảmbảo:
 smooth
 continuous
 pass through specified points
 uniform brightness

)
u
(c) SE/FIT/HUT 2002
5
Thuật toán DDA
(Digital Differential Analizer)
Giảithuật DDA
 Với 0 < k < 1
x
i+1
= x
i
+ 1
y
i+1
= y
i
+ k
với i=1,2,3
Thuậttoán ddaline (x1, y1, x2, y2)
x1, y1, x2, y2 : tọa độ 2 điểm đầucuố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

2
d2
d1
KHoa CNTT-DDHBK Hà nội

0913030731
2
(c) SE/FIT/HUT 2002
7
Giảithuật Bresenham
d
2
= y - yi = k(xi +1) + b - yi
d
1
= yi+1 - y = yi + 1 - k(xi + 1) - b
 If d
1
≤ d
2
=> y
i+1
= yi + 1
else d
1
> d
2
=> y
i+1
= yi

i+1
- xi) + 2Δx(yi
+1
-yi)
 NếuPi ≤ 0 ⇒ yi
+1
= yi + 1
Pi
+1
= Pi - 2Δy + 2Δx
 Nếu Pi > 0 ⇒ yi
+1
= yi
Pi
+1
= Pi - 2Δy
P
1
= Δx(d
1
-d
2
)
P
1
= -2Δy + Δx
Giảithuật Bresenham
(c) SE/FIT/HUT 2002
9
y

1
 Trong trường hợp d = 0 chúng ta có thể
chọn điểmbấtkỳ hoặc A, hoặcB.
A
M
B
(c) SE/FIT/HUT 2002
10
Bresenham’s Algorithm:
Midpoint Algorithm
 Sử dụng phương pháp biểudiễn không tường minh
 Tạimỗi trung điểmcủa đoạnthẳng giá trịđượctínhlà:
 Chúng ta gọi d
i
là biến quyết định củabướcthứ i
0=
+
+
cbyax
()
()
()
iiii
iiii
iiii
yxcbyax
yxcbyax
yxcbyax
,0
,0

> 0 then chọn điểm A⇒ trung điểmtiếptheosẽ có dạng:
()
bad
cybxadyx
i
iiiii
++=
+
⎟
⎠
⎞
⎜
⎝
⎛
+++=⇒
⎟
⎠
⎞
⎜
⎝
⎛
++
+
2
3
2
2
3
,2
1

⎛
+++=⇒
⎟
⎠
⎞
⎜
⎝
⎛
++
()
ad
cybxadyx
i
iiiii
+=
+
⎟
⎠
⎞
⎜
⎝
⎛
+++=⇒
⎟
⎠
⎞
⎜
⎝
⎛
++

2
0
b
a ++=
KHoa CNTT-DDHBK Hà nội

0913030731
3
(c) SE/FIT/HUT 2002
13
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

x < x2
KÕt thóc
d = d + dy
d = d + dy - dx
y = y + 1
yes
no
No
yes
x = x + 1
(c) SE/FIT/HUT 2002
15
Sinh đường tròn
Scan Converting Circles
 Implicit: f(x) = x
2
+y
2
-R
2
 Explicit: y = f(x)
 Parametric:
22
yRx=± −
cos
sin
xR
yR
θ
θ

cc
(
)
()
()

circle outside is , if 0
circleon is , if 0
circle inside is , if 0
⎪
⎩
⎪
⎨
⎧
>
=
<
=
ii
ii
ii
i
yx
yx
yx
d
(c) SE/FIT/HUT 2002
17
Midpoint Circle Algorithm
 As with the line, we determine the value of the decision variable by

()
32
2
1
2
2
1
,2
2
2
2
1
++=
−
⎟
⎠
⎞
⎜
⎝
⎛
−++=⇒
⎟
⎠
⎞
⎜
⎝
⎛
−+
+
ii

−+
+
iii
iiiii
yxd
ryxdyx
KHoa CNTT-DDHBK Hà nội

0913030731
4
(c) SE/FIT/HUT 2002
19
Midpoint Circle Algorithm
 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:
 Although the initial value is fractional, we note that all other values are
integers.
⇒ we can round down:
r
rrrdr
−=
−
⎟
⎠
⎞
⎜
⎝
⎛
+−+=⇒

d = d+2*(x-y)+5
x = x+1
y = y-1
endif
SetPixel(c
x
+x,c
y
+y)
endwhile
initialisation
choose B
choose A
Translate to the circle center
stop at diagonal ⇒ end of octant
(c) SE/FIT/HUT 2002
21
Scan Converting Ellipses
 2a is the length of the major axis along the x axis.
 2b is the length of the minor axis along the y axis.
 The midpoint can also be applied to ellipses.
 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
22 22 22
(, ) 0Fxybxayab=+−=
(c) SE/FIT/HUT 2002
22
Scan Converting Ellipses: Algorithm
 Firstly we divide the quadrant into two regions

2
+a
2
(-b+0.25)
 For a move to E, d
new
= d
old
+Delta
E
with Delta
E
= b
2
(2x
p
+3)
 For a move to SE, d
new
= d
old
+Delta
SE
with
Delta
SE
= b
2
(2x
p

2
(-2y
p
+3)
 For a move to SE, d
new
= d
old
+Delta
SE
with
Delta
SE
= b
2
(2x
p
+2)+a
2
(-2y
p
+3)
 Stop in region 2 when the y value is zero.
(c) SE/FIT/HUT 2002
24
Ký tự Bitmap
 Trên cơ sỏđịnh nghĩamỗikýtự với
một font chư cho trướclàmột
bitmap chữ nhậtnhỏ
 Font/typeface: set of character

} fontcache
(c) SE/FIT/HUT 2002
26
Ký tự vector
 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.
 Tốnkémnhấtvề mặt tính
toán
 Chất lượngcao
(c) SE/FIT/HUT 2002
27
So sánh
 Đơngiảntrôngviệcsinhkýtự
( copypixel)
 Lưutrữ lớn
 Các phép biến đổi (I,B, scale)
đòi hỏilưutrữ thêm
 Kích thước không dổi
 Phứctạp(Tínhtoánphương
trình)
 Lưutrữ gọnnhẹ
 Các phép biến đổidựa vào các
công thứcbiến đổi
 Kích thướcphụ thuôc vào môi
trường ( ko có kích thướccố
định)
(c) SE/FIT/HUT 2002
28

điểmbiên)
 Đảmbảocácđagiácchiasẻđiểm biên
mà không chia sẻ các điểm ảnh bên
trong của mình.
KHoa CNTT-DDHBK Hà nội

0913030731
6
(c) SE/FIT/HUT 2002
31
Polygon Scan Conversion
 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
 Need to handle 4 cases to prevent pixel sharing:
 if intersection has fractional x value, do we round up or down?
• if inside (on left of span) round up, if outside (on right) round down
 what happens if intersection is at an integer x value?
• if on left of span assume its interior otherwise exterior
 how do we handle shared vertices?
• ignore pixel associated with y
max
of an edge
 how do we handle horizontal edges?
• handled as a result of previous rule (lower edges not drawn)
(c) SE/FIT/HUT 2002
32
Polygon Scan Conversion
rounded down for A

(
)
()
startend
startend
xx
yy
m
−
−
=
(c) SE/FIT/HUT 2002
34
Giảithuật đường quét
Scan-Line Algorithm
 The scan-line algorithm uses edge-coherence and incremental
integer calculations
for maximum efficiency:
 Tạobảng edge table (ET) tậpcủacáccạnh đagiáctheothứ tự giá trị
y
min
của chúng
 Tạobảng active edge table (AET) tậpcáccạnh giao vớI đoạnthẳng
quét scan-line
 Trong tiến trình quét các cạnh sẽ chuyểntừ ET ra AET.
 Các cạnh sẽởtrong AET cho đến khi giá trị y
max
củacạnh đạt
tới = scanline
 Lúc nay cạnh sẽ bị loạirakhỏiAET.

0913030731
7
(c) SE/FIT/HUT 2002
37
Scan-Line Algorithm
y = y of first non empty entry in ET
AET = null
repeat
move all ET entries in slot y to AET
sort AET entries according to x
min
fill spans using pairs of AET entries
for all AET members
if y
max
= y then remove from AET
y = y+1
for all AET members
update numerator
if numerator>denominator
numerator=numerator-denominator
x = x+1
until AET and ET empty