Để thể hiện một đường thẳng trên màn hình, sử dụng các điểm ảnh pixel để tạo ra một đường thẳng. Các điểm ảnh phải có tọa độ (x, y) là số nguyên nên việc lựa chọn điểm ảnh pixel không đúng sẽ xảy ra vấn đề tạo ra đường gấp khúc khi nhìn vào đường thẳng được tạo ra. Thuật toán DDA - Digital Differential Analyzer là 1 trong các thuật toán hỗ trợ lựa chọn điểm ảnh để vẽ các đường trên màn hình.
Mô tả thuật toán
Lý thuyết cơ sở
Thuật toán DDA - Digital Differential Analyzer (bộ phân tích vi sai) có thể tóm tắt qua các bước một cách tổng quan:
- Giả sử tọa độ của hai điểm
A(xA, yA)
,B(xB, yB)
không trùng nhau với điều kiện làxA
,yA
,xB
,yB
đều là số nguyên. - Tính số điểm ảnh của đường thẳng được vẽ thêm trên màn hình.
- So sánh trị tuyệt đối của
dx = xB - xA
,dy = yB - yA
và lấy trị tuyệt đối lớn nhất vì xác định càng nhiều số giao điểm thì đường thẳng càng rõ và mịn. - Gọi là
steps
là số điểm ảnh được vẽ thêm, khi đósteps = max(|dx|, |dy|)
. - Ví dụ: với
A(2, 3)
vàB(6, 6)
- Thì
dx = 3
,dy = 4
,|dy| > |dx|
vậysteps = 4
. Các ô gạch màu xanh thể hiện các giao điểm bị cắt qua.
- Thì
- So sánh trị tuyệt đối của
- Sau khi xác định được số giao điểm
steps
sẽ xác định được giá trị cộng vào chox
vày
bắt đầu từ tọa độA(xA, yA)
cho tới tọa độ điểmB(xB, yB)
. Các giá trị này sẽ được tính như sau:x_inc = dx / steps
,y_inc = dy / steps
, giá trị là số thực.- Ví dụ: với
A(2, 3)
vàB(6, 6)
- Thì
dx = 3
,dy = 4
,steps = 4
,x_inc = 0.75
,y_inc = 1
.
- Ví dụ: với
- Sau khi có tất cả các thông số cần thiết bao gồm
A(xA, yA)
,B(xB, yB)
,steps
,x_inc
,y_inc
, tiến hành bước cuối cùng là tìm các tọa độ cần vẽ. Chỉ cần cộngxA
,yA
vớix_inc
,y_inc
theo công thứcxi+1 = xi + x_inc
,yi+1 = yi +y_inc
. Sau đó làm tròn kết quả về số nguyên để ra các tọa độ tiếp theo.- Ví dụ: với
A(2, 3)
vàB(6, 6)
,dx = 3
,dy = 4
,steps = 4
,x_inc = 0.75
,y_inc = 1
. - Lần lượt có các giá trị sau khi thêm
x_inc
,y_inc
:(3, 2)
,(3.75, 3.0)
,(4.5, 4.0)
,(5.25, 5.0)
,(6.0, 6.0)
. - Kết quả sau khi làm tròn:
(3, 2)
,(4, 3)
,(5, 4)
,(5, 5)
,(6, 6)
.
- Ví dụ: với
Lưu đồ thuật toán
Code mẫu thuật toán DDA bằng C++
void drawLineDDA(int xA, int yA, int xB, int yB) { int dX = xB - xA, dY = yB – yA, color = 4; float steps = max(abs(dX), abs(dY)); float x_inc = dX / steps; float y_inc = dY / steps; float x = xA, y = yA; putpixel(x, y, color); int k = 0; while (k < steps) { k++; x += x_inc; y += y_inc; putpixel(Round(x), Round(y), color); } }