THUẬT TOÁN DDA

Họ và tên : TRƯƠNG THỊ LỆ CHÂM
Học phần : ĐỒ HỌA MÁY TÍNH
Đơn vị : Khoa Công nghệ thông tin
Năm học : 2016 – 2017
BÀI GIẢNG SÁT HẠCH
Em hãy vẽ mô phỏng màn hình có độ phân giải 8x8 và xác định tọa độ của các điểm sau trên màn hình đó: A(3,2); B(5,7)?
1.4 CÁC THUẬT TOÁN
VẼ ĐOẠN THẲNG
1.4.1 Bài toán
Cho hai điểm ảnh A và B trên màn hình có tọa độ lần lượt là: A(x1, y1) và B(x2,y2).
Yêu cầu: Vẽ đoạn thẳng nối 2 điểm ảnh A và B đã cho bằng một màu định trước.
1.4 CÁC THUẬT TOÁN VẼ ĐOẠN THẲNG
* Phân tích bài toán:
Hệ số góc của đoạn thẳng AB được xác định là:
Với x = x2 - x1, y = y2 - y1
x=0
hay x1=x2 và y  0
m không xác định
1.4 CÁC THUẬT TOÁN VẼ ĐOẠN THẲNG
khi y = 0 hay y1=y2
m =±1
khi |x| = |y|
m = 0
1.4 CÁC THUẬT TOÁN VẼ ĐOẠN THẲNG
* Phân tích bài toán:
* Phân tích bài toán:
1.4 CÁC THUẬT TOÁN VẼ ĐOẠN THẲNG
* Phương pháp:
Xác định các tọa độ nguyên (x,y) với x trong khoảng từ x1 đến x2 và y trong khoảng từ y1 đến y2 gần với đoạn thẳng nhất để làm điểm vẽ.
Vì các Pixel được vẽ ở các vị trí nguyên nên đoạn thẳng được vẽ giống như hình bậc thang.
1.4 CÁC THUẬT TOÁN VẼ ĐOẠN THẲNG
a. Nội dung:
Xác định tọa độ các điểm ảnh gần nhất mà đoạn thẳng AB đi qua và tô màu điểm ảnh đó.
b. Ý tưởng:
Các tọa độ điểm vẽ là tọa độ nguyên nên ta cho một giá trị x (hoặc y) chạy từ tọa độ của điểm A đến tọa độ điểm B, giá trị còn là là y (hoặc x) được tính toán và làm tròn.
1.4.2 Thuật toán DDA
(Digital Differential Analyzer)
1.4 CÁC THUẬT TOÁN VẼ ĐOẠN THẲNG
c. Thuật toán:
Bước 1: Nhập tọa độ hai điểm A(x1,y1) B(x2,y2).
Bước 2: Tính x = x2 - x1 y = y2 - y1 Step = Max(|x| , |y|)
Bước 4: Tính x = x + IncX; y = y + IncY;
Vẽ điểm (Round(x),Round(y)); j=j+1
Bước 5: Nếu j>Step thì dừng
Ngược lại thì quay lại bước 4
Bước 3: Khởi tạo các giá trị: IncX = x/Step; IncY = y/Step;
x = x1; y = y1; Vẽ điểm (x,y); j=1
1.4 CÁC THUẬT TOÁN VẼ ĐOẠN THẲNG
1.4.2 Thuật toán DDA
(Digital Differential Analyzer)
Chú ý: Thủ tục vẽ điểm ở thuật toán này là việc tô điểm vẽ bằng màu dùng để vẽ đoạn thẳng
d. Ví dụ áp dụng
* Ví dụ 1:
Dùng thuật toán DDA để vẽ đoạn thẳng AB trong đó tọa độ A,B trên màn hình là A(2,2); B(6,4).
1.4 CÁC THUẬT TOÁN VẼ ĐOẠN THẲNG
1.4.2 Thuật toán DDA
(Digital Differential Analyzer)
d. Ví dụ áp dụng
Dùng thuật toán DDA để vẽ đoạn thẳng AB trong đó tọa độ A, B trên màn hình là: A(2,2); B(6,4)
B1: Nhập tọa độ A(2,2); B(6,4)
B
B2: x = 4; y = 2 Step = 4
B3: Khởi tạo các giá trị:
IncX =1; IncY =0.5;
x = 2; y = 2; Vẽ điểm (2,2); j=1
B4: x =3; y =2.5;
Vẽ điểm (Round(x),Round(y)) là điểm (3,3) j=j+1=2
B5: j=2 quay lại bước 4
A
1.4 CÁC THUẬT TOÁN VẼ ĐOẠN THẲNG
d. Ví dụ áp dụng
Dùng thuật toán DDA để vẽ đoạn thẳng AB trong đó tọa độ A, B trên màn hình là: A(2,2); B(6,4)
A
B
B 4: x =4; y =3;
Vẽ điểm (Round(x),Round(y) là điểm (4,3)
j=j+1=3
B5: j=3 quay lại bước 4
B4: Tính x =5; y = 3.5;
Vẽ điểm (Round(x),Round(y)) là điểm (5,4) j=j+1=4
B5: j=4 quay lại bước 4
B 4: Tính x = 6; y = 4.4;
Vẽ điểm (Round(x),Round(y)) là điểm (6,4) j=j+1=5
B5: j= 5 lớn hơn 4 nên thuật toán dừng
1.4 CÁC THUẬT TOÁN VẼ ĐOẠN THẲNG
Các điểm vẽ là: (2,2); (3,3); (4,3); (5,4); (6,4)
1.4 CÁC THUẬT TOÁN VẼ ĐOẠN THẲNG
* Cài đặt minh họa thuật toán DDA
Procedure DDALine(x1,y1,x2,y2:Integer);
var dx,dy,step,j:integer;
Incx,Incy,x,y:real;
Begin
dx:=x2-x1; dy:=y2-y1;
If abs(dx)>abs(dy) Then step:=abs(dx)
else step:=abs(dy);
Incx:=dx/step; Incy:=dy/step;
x:=x1; y:=y1;
Putpixel(round(x),round(y),15);
for J:=1 to step do
Begin
x:=x+xInc; y:=y+yInc;
Putpixel(round(x),round(y),15);
End;
End;
d. Ví dụ áp dụng
* Ví dụ 2:
Dùng thuật toán DDA để vẽ đoạn thẳng AB trong đó tọa độ A, B trên màn hình là: A(2,5); B(6,3)
1.4 CÁC THUẬT TOÁN VẼ ĐOẠN THẲNG
* Ví dụ 2:
Dùng thuật toán DDA để vẽ đoạn thẳng AB trong đó tọa độ A, B trên màn hình là: A(2,5); B(6,3)
1.4 CÁC THUẬT TOÁN VẼ ĐOẠN THẲNG
Lý thuyết:



Bài tập:

-Tài liệu tham khảo:
Giáo trình Đồ họa máy tính – TS Nguyễn Thế Lộc.
Giáo trình Lý thuyết đồ họa – Nguyễn Hữu Tài.
Tài liệu học tập Đồ họa máy tính (Lưu hành nội bộ).
BÀI TẬP VỀ NHÀ
- Phân tích các trường hợp của bài toán vẽ đoạn thẳng đi qua hai điểm trên tọa độ màn hình và lấy ví dụ.
- Đọc và tìm hiểu trước thuật toán Bresenham vẽ đoạn thẳng
- Bài tập 1,2 trang 22 trong tài liệu học tập.
Xin cảm ơn các thầy cô
cùng các em !