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 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 2 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 3 Biểu diễn đoạn thẳng „ Biểu diễn tường minh P(x2 , y2) (y-y1)/( x-x1) = ( y2-y1)/( x2-x1)1 y = kx + m „ Biểu diễn không tường minh u (y2-y1)x - (x2-x1)y + x2y1 - x1y2 = 0 hay rx + sy + t = 0 „ Biểu diễn tham biến P(x1, y1) P(u) = P1 + u(P2 - P1) u [0,1] m (c) SE/FIT/HUT 2002 4 Thuật toán DDA (Digital Differential Analizer) 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 ); }} Giải thuật DDA „ Với 0 < k < 1 xi+1 = xi + 1 yi+1 = yi + k với i=1,2,3.... (c) SE/FIT/HUT 2002 5 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 „ 2 d1 d2 1 0 0 (c) SE/FIT/HUT 2002 1 2 6 Giải thuật Bresenham d2 = y - yi = k(xi +1) + b - yi d1 = yi+1 - y = yi + 1 - k(xi + 1) - b A yi+1 d1 d2 yi B xi xi+1 (c) SE/FIT/HUT 2002 7 Giải thuật Bresenham (c) SE/FIT/HUT 2002 8 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