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

efficient
(c) SE/FIT/HUT 2002
4
Biểudiễn đoạnthẳng

Biểudiễntườ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

Biểudiễ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

Biểudiễnthambiến
P(u) = P1 + u(P2 - P1)
u [0,1]
X = x1 + u( x2 - x1 )
Y = y1 + u( y2 - y1 )
m
P(x
1
, y
1
)
P(x
2
, y
2
)
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
begin
x = x+1;
y = y+k;
putpixel(round(x),round(y));
end; end;
Giảithuậ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 );
}}
(c) SE/FIT/HUT 2002
6
Giảithuật Bresenham

1960 Bresenham thuộcIBM

điểmgầnvới đường thẳng dựa
trên độ phân giai hưuhạn

loạibỏđược các phép toán
chia và phép toán làm tròn
như ta đãthấytronggỉai thuật
DDA

Xét đoạnthẳng với 0 < k < 1
012
0
1
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

D = d
1
-d

2
= -2k(xi + 1) + 2yi - 2b + 1

Pi = ΔxD = Δx (d
1
-d
2
)
d1
d2
x
i
x
i
+1
y
i
y
i
+1
(c) SE/FIT/HUT 2002
8
Pi = -2Δyxi + 2Δxyi + c
P
i+1
-P
i
= -2Δy(x
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

i+1
M
( x
i
, y
i
)
x
i
x
i+1
Giảithuật trung điểm-Midpoint

Jack Bresenham 1965 / Pitteway 1967

VanAken áp dụng cho việc sinh các đường
thẳng và đường tròn 1985

Các công thức đơngiảnhơn, tạo đượccácđiểm
tương tự như với Bresenham

d = F (xi + 1, yi + 1/2) là trung điểmcủa đoạn
AB

Việc so sánh, hay kiểmtraM sẽđược thay
bằng việc xét giá trị d.

Nếud > 0 điểmB đượcchọn, y
i+1
= y

i

nếud < 0 điểmA đượcchọn. ⇒ y
i+1
= y
i
+
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
⇒>++
⇒<++
⇒
=++
on line
above line
below line
()
cybxad
iii
+
⎟
⎠
⎞
⎜
⎝
⎛
+++=
2
1
1

(c) SE/FIT/HUT 2002
11
Bresenham’s Algorithm:
Midpoint Algorithm

If d
i
> 0 then chọn điểmA ⇒ trung điểmtiếptheosẽ có dạng:
()
bad
cybxadyx
i
iiiii
++=
+
⎟
⎠
⎞
⎜
⎝
⎛
+++=⇒
⎟
⎠
⎞
⎜
⎝
⎛
++
+

2
3
2
2
3
,2
1
(c) SE/FIT/HUT 2002
12
Bresenham’s Algorithm:
Midpoint Algorithm

if d
i
< 0 then chọn điểm B và trung điểmmớilà

Ta có:

Ðiểm đầu
()
[]
2
2
1
1
2
1
,1
b
acbyax

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

⎝
⎛
+++=⇒
⎟
⎠
⎞
⎜
⎝
⎛
++
+
2
1
2
2
1
,2
1
Cx
x
y
y
xCc
xxxb
yyya
startend
startend
+
Δ
Δ

=
⎪
⎭
⎪
⎬
⎫
Δ=
−=Δ−=
−=Δ=
where
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
(c) SE/FIT/HUT 2002
14
Giảithuật
Bresenham's Midpoint

d = a(xi + 1) + b(yi + 1/2) + c

Nếu điểm đượcchọnlàB thiM sẽ tang
theo x một đơnvị

d
i+1
= F(xi +2, yi + 1/2)
= a(xi +2) + b(yi + 1/2) + c

di = a(xi + 1) + b(yi + 1/2) + c

Nếu điểmA đượcchọnthi` M tăng theo 2
hướng x và y với cùng một đơnvị.
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
(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
θ
θ
=
=
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.
(c) SE/FIT/HUT 2002
16
Midpoint Circle Algorithm

Sử dụng phương pháp biểudiễn không
tường minh trong giảithuật

Thựchiệngiảithuậttrên1/8 đường
tròn và lấy đốixứng xho các góc còn
lại.

Với d
i
là giá trị của đường tròn tại
một điểmbấtkỳ ta có
( ) ( )
0
2
22
=−−+−
ryyxx
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
substituting the mid-point of the next pixel into the implicit form of the
circle:

If d
i
< 0 we choose pixel A otherwise we choose pixel B

Note: we currently assume the circle is centered at the origin

()
2
2
2
2
1
1 ryxd
iii
−
⎟
⎠
⎞
⎜
⎝
⎛
−++=
(c) SE/FIT/HUT 2002
18
Midpoint Circle Algorithm

Again, as with the line algorithm, the choice of A or B can be used to
determine the new value of d
i+1

If A chosen then next midpoint has the following decision variable:

Otherwise if B is chosen then the next decision variable is given by:
()
32
2

1
2
2
1
,2
2
2
2
1
++=
−
⎟
⎠
⎞
⎜
⎝
⎛
−++=⇒
⎟
⎠
⎞
⎜
⎝
⎛
−+
+
ii
iiiii
xd
ryxdyx

()
522
2
3
2
2
3
,2
2
2
2
1
+−+=
−
⎟
⎠
⎞
⎜
⎝
⎛
−++=⇒
⎟
⎠
⎞
⎜
⎝
⎛
−+
+
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
−=
−
⎟
⎠
⎞
⎜
⎝
⎛
+−+=⇒

⎟
⎠
⎞
⎜
⎝
⎛
−
4
5
4
1
1
2
1
,1
22
0
rd −=1
0
(c) SE/FIT/HUT 2002
20
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(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

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
22
(, ) / / 2 2gradFxy Fx Fy bx ay=∂ ∂ +∂ ∂ = +ijij
A
M tiep tuyen = -1
B gradient
B C
M
i
(c) SE/FIT/HUT 2002
23
Ellipses: Algorithm (cont.)

At the next midpoint, if a
2
(y
p
-0.5)<=b
2

(x
p
+1), we switch region 1=>2

In region 1, choices are E and SE

Initial condition: d
init
= b
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
+3)+a
2
(-2y
p
+2)

In region 2, choices are S and SE

Initial condition: d
init
= b
2
(x
p
+0.5)
2
+a
2
((y-1)

2
-b
2
)

For a move to S, d
new
= d
old
+Delta
s
with Delta
s
= a
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
shapes

fontcache

các ký tự theo chuỗiliêntiếp nhau trong
bộ nhớ

Dạng cơ bản

(thường N, nghiêng I, đậm B, nghiêng
đậmB+I)


Thuộctính

Also colour, size, spacing and
orientation
ab
KHoa CNTT-DDHBK Hà nội

0913030731
5
(c) SE/FIT/HUT 2002
25
Cấutrúcfont chữ
Typedef struct
{
int leftx,
int width;
} Char location; //Vị trí củatext
Typedef struct
{
CacheId;
Heiglit; // Độ rộng chữ
CharSpace; // Khoảng cách
giữacáckýtự
Charlocation Table [128];
} 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
Giải thuật đường quét sinh đa giác
Polygon Scan Conversion

Tồn tại rất nhiều giải thuật sinh đa giác
.

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
(c) SE/FIT/HUT 2002
29
Polygon Scan Conversion

Polygon scan conversion là giải thuật chung kinh điển cho các loại
khác nhau


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.

This represents the heart of a scan-line rendering algorithm used in
many commercial products including Renderman and 3D Studio
MAX.
(c) SE/FIT/HUT 2002
30
Polygon Scan Conversion

Dùng giảithuật (trung điểm) để xác
định các điểmbiênchomỗi đagiác
theo thứ tự tăng củax.

Các diểmphải:

Không bị chia sẻ bởicácđagiáclân
cận

Các đagiácchỉ toàn các điểmcạnh(
đ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.