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

(c) SE/FIT/HUT 2002
Bài 2:
Các giải thuật sinh 
các thực thể cơ sở
Le Tan Hung
hunglt@it-hut.edu.vn
(c) SE/FIT/HUT 2002 2
Giải thuật xây dựng các
thực thể cơ sở
„ Giải thuật sinh đường thẳng – Line
„ Giải thuật sinh đường tròn - Circle
„ Giải thuật VanAken sinh Ellipse
„ Giải thuật sinh đa giác
„ Giải thuật sinh ký tự
(c) SE/FIT/HUT 2002 3
Rời rạc hoá điểm ảnh
(Scan Conversion rasterization)
„ Scan Conversion rasterization
„ Tính chất các đối tượng cần đảm bảo :
„ smooth
„ continuous
„ pass through specified points
„ uniform brightness
„ efficient
(c) SE/FIT/HUT 2002 4
Biểu diễn đoạn thẳng
„ Biểu diễn tường minh
(y-y1)/( x-x1) = ( y2-y1)/( x2-x1)1
y = kx + m
„ Biểu diễn không tường minh
(y2-y1)x - (x2-x1)y + x2y1 - x1y2 = 0
hay rx + sy + t = 0 
„ Biểu diễn tham biến
P(u) = P1 + u(P2 - P1)
u [0,1]
m
P(x1, y1)
P(x2 , y2)
u
(c) SE/FIT/HUT 2002 5
Thuật toán DDA 
(Digital Differential Analizer)
Giải thuật DDA
„ Với 0 < k < 1 
xi+1 = xi + 1 
yi+1 = yi + k
với i=1,2,3....
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 );
}}
(c) SE/FIT/HUT 2002 6
Giải thuật Bresenham
„ 1960 Bresenham thuộc IBM 
„ điểm gần với đường thẳng dựa
trên độ phân giai hưu hạn
„ 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 giải thuật
DDA 
„ Xét đoạn thẳng với 0 < k < 1
0 1 2
0
1
2 d1
d2
(c) SE/FIT/HUT 2002 7
Giải thuật Bresenham
d2 = y - yi = k(xi +1) + b - yi
d1 = yi+1 - y = yi + 1 - k(xi + 1) - b
d1
d2
xi xi+1
yi
yi+1
A
B
(c) SE/FIT/HUT 2002 8
Giải thuật Bresenham
(c) SE/FIT/HUT 2002 9
yi+1
( xi , yi ) 
xi xi+1
Giải thuậ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 đơn giản hơn, tạo được các
điểm tương tự như với Bresenham
„ d = F (xi + 1, yi + 1/2) là trung điểm của
đoạn AB
„ 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
(c) SE/FIT/HUT 2002 10
Bresenham’s Algorithm: 
Midpoint Algorithm
„ 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
(c) SE/FIT/HUT 2002 11
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 12
Giải thuật
Bresenham's Midpoint
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 13
Sinh đường tròn
Scan Converting Circles
„ Implicit: f(x) = x2+y2-R2
„ Explicit: y = f(x)
„ 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.
(c) SE/FIT/HUT 2002 14
Midpoint Circle Algorithm
„ Sử dụng phương pháp biểu diễn không
tường minh trong giải thuật
„ 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.
„ Với di là giá trị của đường tròn tại
một điểm bất kỳ ta có
(c) SE/FIT/HUT 2002 15
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 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 −

 −++=
(c) SE/FIT/HUT 2002 16
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
(c) SE/FIT/HUT 2002 17
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
2 2 2 2 2 2( , ) 0F x y b x a y a b= + − =
(c) SE/FIT/HUT 2002 18
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 
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
(c) SE/FIT/HUT 2002 19
Ellipses: Algorithm (cont.)
„ At the next midpoint, if a2(yp-0.5)2
„ 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)
„ 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)
„ Stop in region 2 when the y value is zero. 
(c) SE/FIT/HUT 2002 20
Ký tự Bitmap
„ 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ỏ
„ Font/typeface: set of character 
shapes
„ fontcache
„ các ký tự theo chuỗi liên tiếp nhau trong
bộ nhớ
„ Dạng cơ bản
„ (thường N, nghiêng I, đậm B, nghiêng
đậm B+I) 
„ Thuộc tính
„ Also colour, size, spacing and 
orientation
ab
(c) SE/FIT/HUT 2002 21
Cấu trúc font chữ
(c) SE/FIT/HUT 2002 22
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ốn kém nhất về mặt tính
toán
„ Chất lượngcao
(c) SE/FIT/HUT 2002 23
So sánh
„ Đơn giản trông việc sinh ký tự
( copypixel) 
„ Lưu trữ lớn
„ Các phép biến đổi (I,B, scale) 
đòi hỏi lưu trữ thêm
„ Kích thước không dổi
„ Phức tạp (Tính toán phương
trình)
„ Lưu trữ gọn nhẹ
„ Các phép biến đổi dựa vào các
công thức biến đổi
„ Kích thước phụ thuôc vào môi
trường ( ko có kích thước cố
định)
(c) SE/FIT/HUT 2002 24
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 25
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 26
Polygon Scan Conversion
„ 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.
„ 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)
„ Đả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.
(c) SE/FIT/HUT 2002 27
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 ymax 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 28
Polygon Scan Conversion
rounded down for A
rounded up for B
integer x value is on
right = exterior
ymax not 
included
horizontal edge
removed