Bài giảng Đồ họa Raster - Các thuật toán vẽ đường tròn

ĐỒ HỌA RASTERCÁC THUẬT TOÁNVẼ ĐƯỜNG TRÒN Giảng viên : Bùi Tiến Lên Trang * Phân loại đường tròn Đường tròn tâm O O Đường tròn tâm bất kỳ Trang * Ứng dụng phép tịnh tiến Nếu (x, y) thuộc đường tròn tâm O Thì (x + xc, y + yc) thuộc đường tròn tâm (xc, yc) O (xc, yc) (x, y) (x+xc, y+yc) Trang * Phương trình đường tròn O r Trang * Tính đối xứng của đường tròn Đường tròn có 4 trục đối xứng -Trục Ox -Trục Oy -Trục phân giác thứ nhất -Trục phân giác thứ hai O x y phân giác 1 phân giác 2 Trang * Ứng dụng tính đối xứng Nếu (x, y) thuộc đường tròn Thì (-x, y), (x, -y), (-x, -y), (y, x), (-y, x), (y, -x) và (-y, -x) thuộc đường tròn O 1 2 3 4 5 6 7 8 chọn Trang * Vẽ cung một phần tám thứ nhất Input r bán kính Output {(x1, y1), (x2, y2) … (xn, yn)} “thuộc” cung một phần tám thứ nhất O A B Trang * Khảo sát cung một phần tám thứ nhất Mục tiêu khảo sát sự biến thiên của hoành độ và tung độ Trang * Khảo sát cung 1/8 thứ nhất Bảng biến thiên Đường cong giảm chậm Trang * Thuật toán trực tiếp Trang * Thuật toán MidPoint Dự đoán điểm sáng thứ i+1 Trang * Thuật toán MidPoint - Khái niệm bên trong / bên ngoài đường tròn - Hàm kiểm tra một điểm bên trong / bên ngoài đường tròn F(x, y) = x2 + y2 – r2 - Cách kiểm tra bên trong bên ngoài Trang * Thuật toán MidPoint Xây dựng biến fi Trung điểm M của AB M(xi + 1, yi – 1/2) Biến fi fi = F(M) fi = F(xi + 1, yi – 1/2) Trang * Thuật toán MidPoint Công thức tính fi Công thức tính fi nguyên Trang * Khi fi không nguyên ! Có hai cách giải quyết để fi thành nguyên Cách 1 fi 0 Cách 2 fi < 0  [fi] < 0 fi  0  [fi]  0 Trang * Thuật toán MidPoint Thuật toán Bước 1 Xác định điểm đầu tiên x1 = 0 y1 = r Bước 2 Xác định những điểm tiếp theo Lặp xi < yi fi = … fi < 0 xi+1 = xi + 1 yi+1 = yi fi ≥ 0 xi+1 = xi + 1 yi+1 = yi – 1 Trang * Thuật toán MidPoint Cách tính fi cải tiến f1 = 1 – r fi < 0 fi+1 = fi + 2xi + 3 fi  0 fi+1 = fi + 2xi – 2yi + 5