Đồ HỌA MÁY TÍNH C Ă C r í l ĩ r r ệ í : Ỹ Ũ Ễ r ĩ V ( i n r r r r T ĩ g 'ế '' Ĩ.I1 ]j.J j.ệ .p • Giả sử tọa độ các điểm nguyên sau khi xấp xỉ đối tượng thực lần lượt là (Xi,yi),i = 0,.... Đây là các điểm nguyên sẽ được hiển thị trên màn hình. • Bài toán đặt ra là nếu biết được ix i>yi) là tọa độ nguyên xác định bước thứ i, điểm nguyên tiếp theo (^H-iơi+ilsẽ được xác định như th ế nào. • Đối tượng hiển thị trên lưới nguyên được liền nét, các điểm mà (Xi+1 Ji+ i) có thể chọn chỉ là một trong tám điểm được đánh số từ 1 đến 8 trong hình sau (điểm đen chính là (x i*yi )).Hay nói cách khác : ( * i + i » y i + i ) = ( * i ± l , y í ± 1) . • Dáng điệu của đường sẽ cho ta gợi ý khi chọn một trong tám điểm trên. Cách chọn các điểm như th ế nào sẽ tùy thuộc vào từng thuật toán trên cơ sở xem xét tới vấn đề tối Ưu tốc độ. Dương Anh Đức, Lê Đình Duy Các thuột ỉoán vẽ dường 1/22 Đồ HỌA MÁY TÍNH I í ì r r ậ ĩ : Ĩ n ã ĩ ĩ v ã ( î n f f t î g i f î l r î g • Xét đoạn thẳng có hệ sô" góc 0 < ra < 1 và Dx > 0. • Với các đoạn thẳng dạng này, nếu là điểm đã xác định được bước thứ i (điểm màu đen) thì điểm cần chọn fc+iJ^j+i) ở bước thứ (i+1) sẽ là một trong hai trường hợp như hình vẽ sau : '*i+i = x i +1 y i+1 e {y¿>y¡ + !} • Vấn đề còn lại, là cách chọn một trong hai điểm trên như th ế nào để có thể tối ưu về m ặt tốc độ. Dương Anh Đức, Lê Đình Duy Các thuột ỉoán vẽ dường 2/22 Đồ HỌA MÁY TÍNH T h u ậ t toán. (JJj.gj.taI JJj.ffereD.tj.aI Aj3.sj.yzer) • Việc quyết định chọn 3//+1 là 3^ hay y* + 1, dựa vào phương trình của đoạn thẳng y = + ố . Nghĩa là, ta sẽ tính tọa độ của điểm (xi +l,;y) thuộc về đoạn thẳng thực. Tiếp đó, yi+1 sẽ là giá trị sau khi làm tròn giá trị tung độ y. y = m(xị + l) + b • Như vậy : yM = Round(y) (Xị, V ị) • Nếu tính trực tiếp giá trị thực y ở mỗi bước từ phương trình y = mx + b thì phải cần một phép toán nhân và một phép toán cộng sô" thực. Để cải thiện tốc độ, người ta tính giá trị thực của y ở mỗi bước theo cách sau để khử phép tính nhân trên số thực : • Nhận xét rằng : ysau = mxi+1 + b = m(xị + 1) + b ytrưóc =mxi +b => y Sau = y trước + rn Dương Anh Đức, Lê Đình Duy Các thuột ỉoán vẽ dường 3/22