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


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

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


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

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

iiii
iiii
iiii
yxcbyax
yxcbyax
yxcbyax
,0
,0
,0
⇒>++
⇒<++
⇒
=++
on line
above line
below line
()
cybxad
iii
+
⎟
⎠
⎞
⎜
⎝
⎛
+++=
2
1
1

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

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

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

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

⎪
⎩
⎪
⎨
⎧
>
=
<
=
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

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

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

(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

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

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


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