Thuật toán DDA - Digital Differential Analyzer được dùng để xác định các điểm ảnh được vẽ của đường thẳng trên màn hình. Bài viết giới thiệu về thuật toán DDA, một thuật toán vẽ đường thẳng đơn giản và dể hiểu.
Đồ họa máy tính C/C++ Khoa học máy tính Vũ Trọng Quang 2017-06-01 10:00:07

Giới thiệu

Để thể hiện một đường thẳng trên màn hình, ta 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 nếu 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. Ở bài viết này, tôi sẽ giới thiệu các bạn thuật toán DDA để chọn các điểm ảnh khi vẽ đường thẳng trên màn hình.

Ngoài DDA, bạn có thể tham khảo thêm một vài thuật toán vẽ đường thẳng khác:

Tiền đề bài viết

Bài viết nằm trong chuỗi bài viết về thuật toán vẽ đường thẳng.

Đối tượng hướng đến

Dành cho những lập trình viên mới bước chân vào con đường tìm hiểu đồ họa máy tính (Computer Graphics) và có kiến thức lập trình căn bản C/C++. Các đối tượng khác vui lòng xem bài viết như là một tài liệu để tham khảo.

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 và đơn giản nhất:

  1. Giả sử ta có 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.
  2. Tính số điểm ảnh của đường thẳng được vẽ thêm trên màn hình. Chúng ta sẽ 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) suy ra dx = 3, dy = 4, |dy| > |dx|  vậy steps = 4. Các ô gạch màu xanh thể hiện các giao điểm bị cắt qua.

thuat-toan-dda-digital-differential-analyzer-1

  1. Sau khi xác định được số giao điểm steps, ta sẽ xác định được giá trị cộng vào cho x và y bắt đầu từ tọa độ A (xA, yA) cho tới tọa độ điểm B (xB, yB). Các giá trị này sẽ được tính như sau: x_inc = d/ steps, y_inc = d/ steps, giá trị là số thực.

Ví dụ: Với A (2, 3) và B (6, 6), dx = 3, dy = 4, steps = 4, x_inc = 0.75, y_inc =1.

  1. 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 chúng ta sẽ tiến hành bước cuối cùng đó là tìm các tọa độ cần vẽ. Ta chỉ cần cộng xA, yA với x_inc, y_inc theo công thức xi+1 = xi + x_inc, yi+1 = yi +y_inc. Sau đó ta cần 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. Ta lần lượt có các giá trị sau khi thêm x_inc, y_ince: (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).

thuat-toan-dda-digital-differential-analyzer-2

Lưu đồ thuật toán

luu-do-thuat-toan-dda-digital-differential-analyzer

Triển khai code 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);
    }
}