Nội dungXây dựng thuật toánĐọc thêm1. Nguyên tắc chung vẽ đoạn thẳng2. Thuật toán DDA vẽ đoạn thẳng3. Thuật toán Breshenham vẽ đoạn thẳng
Xây dựng thuật toán
Cho 2 điểm đầu mút M1(x1, y1), cùng M2(x2, y2). Phương trình đưởng thẳng trải qua M1, mét vuông có dạng
Tại cách thứ k+1 ta tiến hành hiện tăng x lên một đơn vị chức năng và tìm phương pháp tính y theo x với những số nguyên. Call S, p lần lượt là những điểm có tọa độ
tài liệu Đồ họa máy tính - những thuật toán vẽ đường: Đồ HỌA MÁY TÍNHC Ă C r í l ĩ r r ệ í : Ỹ Ũ Ễ r ĩ V ( i n r r r r T ĩ g"ế ""Ĩ.I1 > j . J j .ệ .p• mang sử tọa độ các điểm nguyên sau khoản thời gian xấp xỉ đối tượng người sử dụng thực theo thứ tự là (Xi,yi),i = 0,.... Đây là các điểm nguyên sẽ được hiển thị bên trên màn hình.• bài bác toán đặt ra là nếu hiểu rằng ix i>yi) là tọa độ nguyên khẳng định ở cách thứ i, điểm nguyên tiếp theo (^H-iơi+ilsẽ được xác minh như th ế nào.• Đối tượng hiển thị trên lưới nguyên được ngay tắp lự nét, các điểm nhưng (Xi+1 J i+ i) rất có thể chọn chỉ là một trong tám điểm được tấn công số từ là 1 đến 8 trong hình sau (điểm đen đó là (x i*yi )).Hay có thể nói :( * i + i » y i + i ) = ( * i ± l , y í ± 1 ) .• dáng vẻ điệu của mặt đường sẽ đến ta gợi ý khi lựa chọn 1 trong tám điểm trên. Giải pháp chọn các điểm như th ế nào đang tùy ở trong vào từng thuật toán trên cơ sở xem xét tới sự việc tối Ưu tốc độ.Dương Anh Đức, Lê Đình Duy những thuột ỉoán vẽ dường 1/22Đồ HỌA MÁY TÍNHI í ì r r ậ ĩ : Ĩ n ã ĩ ĩ v ã ( î n f f t î g i f î l r î g• Xét...
Bạn đang xem: Thuật toán midpoint vẽ đường thẳng
22 trang | chia sẻ: khủng long thời tiền sử | Lượt xem: 4525 | Lượt tải: 2
Bạn đang xem trước 20 trang mẫu tài liệu Đồ họa máy tính - những thuật toán vẽ đường, để cài đặt tài liệu cội về máy các bạn click vào nút tải về ở trên
Đồ HỌA MÁY TÍNHC Ă C r í l ĩ r r ệ í : Ỹ Ũ Ễ r ĩ V ( i n r r r r T ĩ g"ế ""Ĩ.I1 > j . J j .ệ .p• mang sử tọa độ các điểm nguyên sau khi xấp xỉ đối tượng người dùng thực theo lần lượt là (Xi,yi),i = 0,.... Đây là những điểm nguyên sẽ được hiển thị trên màn hình.• bài toán đề ra là nếu hiểu rằng 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 khẳng định như th ế nào.• Đối tượng hiển thị trên lưới nguyên được tức tốc nét, các điểm nhưng mà (Xi+1 J i+ i) rất có thể chọn chỉ là một trong trong tám điểm được đánh số từ 1 đến 8 vào hình sau (điểm đen chính là (x i*yi )).Hay nói theo một cách khác :( * i + i » y i + i ) = ( * i ± l , y í ± 1 ) .• dáng điệu của mặt đường sẽ mang lại ta gợi ý khi chọn 1 trong tám điểm trên. Bí quyết chọn những điểm như th ế nào đang tùy ở trong vào từng thuật toán trên cơ sở xem xét tới sự việc tối Ưu tốc độ.Dương Anh Đức, Lê Đình Duy các thuột ỉoán vẽ nhường 1/22Đồ HỌA MÁY TÍNHI í ì r r ậ ĩ : Ĩ n ã ĩ ĩ v ã ( î n f f t î g i f î l r î g• Xét đoạn thẳng bao gồm hệ sô" góc 0 0.• Với những đoạn thẳng dạng này, nếu như là điểmđã khẳng định được ở bước thứ i (điểm color đen) thì điểm cần chọn fc+i
J^j+i) ở cách thứ (i+1) sẽ là 1 trong trong hai trường vừa lòng như hình mẫu vẽ sau :"*i+i = x i +1 y i+1 e y¿>y¡ + !• sự việc còn lại, là cách chọn 1 trong nhì điểm trên thế nào để rất có thể tối ưu về m ặt tốc độ.Dương Anh Đức, Lê Đình Duy các thuột ỉoán vẽ nhịn nhường 2/22Đồ HỌA MÁY TÍNHT h u ậ t toán . (JJj.gj.ta
I JJj.ffere
D.tj.a
I Aj3.sj.yzer)• Việc quyết định chọn 3//+1 là 3^ hay y* + 1 , dựa vàophương trình của đoạn thẳng y = + ố . Nghĩa là,ta và tính tọa độ của điểm (xi +l,;y) nằm trong về đoạnthẳng thực. Tiếp đó, yi+1 vẫn là giá bán trị sau khi làm tròn giá trị tung độ y.y = m(xị + l) + b• vì thế : y
M = Round(y)(X ị , V ị)• trường hợp tính trực tiếp quý giá thực y ở mỗi bước từ phương trình y = mx + b thì phải bắt buộc một phép toán nhân với một phép toán cộng sô" thực. Để cải thiện tốc độ, bạn ta tính giá trị thực của y ở từng bước theo bí quyết sau để khử phép tính nhân bên trên số thực :• thừa nhận xét rằng : ysau = mxi+1 + b = m(xị + 1) + bytrưóc = m x i + b => y Sau = y trước + rn
Dương Anh Đức, Lê Đình Duy những thuột ỉoán vẽ nhường nhịn 3/22Đồ HỌA MÁY TÍNHLưu vật dụng thuật toán DDA Begin ▼m=Dy/Dx; x=x1 ;y=yi;putpixel(x, Round(y), c);No
Yes
DDA (int x1, int y1, int x2, int y2){int X = x 1 ; float y = y1;float m = float(y2-y1)/(x2-x1);putpixel(x, Round(ỵ), Color); for(int i=x1; i 0 ? ta sẽ lựa chọn điểm p, tức làyi+i = y t +1• Xét Pi = Dx(d! - d 2)= Dx{2y - 2yi - 1)=> Pi = Dx<2(m(xi + ì ) + b ) - 2 y i - l>Đặt d 2 = ( y i + l ) - y
Đồ HỌA MÁY TÍNH• cố gắng 171 - ß vào phương trình bên trên ta được : Pị = 2Dy
Xị - 2Dxy¿ + c f với c = 2Dy + (26 - 1 )Dx .• dìm xét rằng trường hợp tạ i cách thứ i ta xác minh được lốt của Pi thì coi như ta xác minh được vấn đề cần chọn ở bước (i+1).• Ta gồm :P i+ 1 - Pi = (2D y x i+1 - 2d x y i+! + c ) - { 2d y x i - 2d x y t + c )P i +1 - p. I = 2 Đ y ( x i+1 - X i ) - 2 D x ( y i+1 - y t ) phường /+1 - Pi = 2 íty - 2Dxịyi+1 - y¿ ), vị xi+1 =Xị +l• Từ trên đây ta có thể suy ra cách tính Pi+1 bốn Pi như S8.U I♦ nếu Pi y) theo phương pháp :p 0 = 2Dyxữ - 2Dxyữ + c = 2Dyx0 - 2Dxyữ + 2Dy - (26 - l)zfoc• vì chưng (*^ 0 J 3^ 0 ) là điểm nguyên nằm trong về đoạn thẳng
D ynên ta có ^0 = m x 0 + b = xữ + b " rpkg v£0 phương trình bên trên ta suy ra : Po = 2Dy — D x .Dương Anh Đức, Lê Đình Duy những thuột ỉoán vẽ nhường 7/22Đồ HỌA MÁY TÍNHLưu đồ gia dụng thuật toán Bresenham
Dương Anh Đức, Lê Đình Duy những thuột ỉoán vẽ nhịn nhường 8/22Đồ HỌA MÁY TÍNH• lấy ví dụ như : đến A(12, 20) với B(22, 27),• Ta có♦ Dx = 22-12 = 10, Dy=27-20=7♦ Constl = 2Dy = 14, Const2 = 2(Dy - Dx) = -6♦ Po = 2Dy - Dx = 14-10 = 4í Xi / pi0 12 đôi mươi 1Jí 13 21 -22 14 21 12no 15 2 2 64 16 23 05 17 24 -66 18 24 87 19 25 28 đôi mươi 26 ~/±19 21 26 1010 22 27 4■• thừa nhận xét♦ Thuật toán Bresenham chỉ làm việc trên số nguyên cùng các thao tác làm việc trên số nguyên chỉ với phép cộng và phép dịch bit (phép nhân 2) vấn đề đó là một cải tiến làm tăng tốc độ đáng nhắc so cùng với thuật toán DDA. Ý tưởng thiết yếu củathuật toán nằm ở đoạn xét vệt Pi để ra quyết định điểm kếtiếp, và áp dụng công thức truy tìm hồi Pi+1 ~ Pi nhằm tính Pi bằng các phép toán dễ dàng trên số nguyên.♦ Thuật toán này cho kết quả tương trường đoản cú như thuật toán DDA.Dương Anh Đức, Lê Đình Duy các thuột ỉoán vẽ nhường 9/22Đồ HỌA MÁY TÍNH• setup minh họa thuật toán Bresenham void Line
Bres (int x1, int ỵ1, int x2, int y2){int Dx, Dy, p, Constl, Const2; int X, y;Dx = x2 - x1 ;Dy = y2 - y1 ;p = 2*Dy - Dx; / / Dy « 1 - Dx Constl = 2*Dy; / / Dy « 1 Const2 = 2*(Dy-Dx); / / (Dy-Dx) « 1 X = x1 ; y = y1;putpixel(x, y, Color); for(i=x1 ; i
J/) cùng với điểm Mid
Point là trung điểm của s và phường Ta có :♦ nếu như điểm Q nằm bên dưới điểm Mid
Point, ta lựa chọn s.♦ giả dụ điểm Q nằm trong điểm Mid
Point ta lựa chọn p.• Ta gồm dạng bao quát của phương trình con đường thẳng : Ax + By + C = 0 cùng với A = y2- y , , B = ~{x2 - x , ) ,c = x2y ! - x , y 2• Đặt F(x, y ) = Ax + By + c t ta có nhận xét : 0, ví như (x, y ) nằm ph ía dưới đường thẳng .Dương Anh Đức, Lê Đình Duy những thuột toán vẽ mặt đường 11 /22Đồ HỌA MÁY TÍNHLúc này bài toán chọn các điểm s, p. ở bên trên được mang lại việc xét vết của Pi = 2F(Mid
Point) = 2F X ị +1, + —♦ Nếu p i p. I +1 - p i = 2 A + 2 B { y i+1 - y i ) = 2 Đ y - 2 D x y i+1 - y . )• do vậy :♦ Pi+1 = Pi + trường hợp Pj .)"o), với dấn xét rằng (^o^o) là vấn đề thuộc về đoạn thẳng, tức là có : Ax0 + By0 + c = 0Po = Xo +I,y0 + 2 = 2 Ax0 +1 ) + B y0 + — l+cp0 = 2(Ajc0 + By0 + c)+ 2 A + B = 2 A + B = 2Z)v -Dương Anh Đức, Lê Đình Duy những thuột toán vẽ đường 12/22Đồ HỌA MÁY TÍNH" 7 2 " 7 _ " ¿ ỉ J"J8.u Jj.GI trs .• Xét thuật toán Bresenham, với phương pháp đặt di và (Ỉ2 như trên, có bao giờ di xuất xắc d2 âm hay không ? đến ví dụ minh họa.• lý do phải đối chiếu giá trị Pi với 0 trong số thuật toán Mid
Point cùng Bresenham, bản chất của việc đối chiếu này là gì ?• vì sao phải nhân F(Mid
Point) với 2 khi gán mang lại Pi theo phương pháp pi=2*F(Mid
Point) ?
Dương Anh Đức, Lê Đình Duy các thuột toán vẽ nhường nhịn 13/22Đồ HỌA MÁY TÍNH• thiết lập thuật toán mang lại trường vừa lòng 0 0 đã cài đặt cộng thêm một sô" đổi khác sau :♦ cầm biểu thức x=x+l bởi x=x-l với y=y+l bởi y=y-l vị trong trường phù hợp này X với y đều sút dần.♦ dấn xét rằng lúc p0 ta gán p=p+Const2, Const2 đề xuất là giá trị âm.♦ Từ nhận xét trên, trong số công thức ta sẽ nạm Dx bởi abs(Dx), Dy bằng abs(Dy).• không ngừng mở rộng thuật toán trên nhằm vẽ đoạn thẳng trong trường phù hợp m bất kì.♦ trường hợp quan trọng m=oo : Đoạn thẳng song song trục tung bắt buộc rấ t đơn giản khi vẽ.♦ Trường phù hợp -1 ^1 ) là điểm nguyên đã kiếm được ở bước thứ i, thì điểm f c + i J i + 1 ) ở bước thứ (i+1) là việc lựa lựa chọn giữa s và p.• như vậy :x i+1 = x i + ly i+i e b i , y, - 1• Đặt F x , y ) —X + y —R ; ta bao gồm : 0, giả dụ (x, y ) nằm đi ngoài đường tròn.Dương Anh Đức, Lê Đình Duy những thuột toán vẽ dường 1Ó/22Đồ HỌA MÁY TÍNH• Xét Pi = ^ (Mid
Point) = F ( 1 1xi + 1^ i 9V z y. Ta có♦ nếu Pi yí+i 2 - F/ VX ị + 1 , y , — 1 2 /fe+1+ l)2 + yi+i f e + ự + * 2- R 2 A +1 - p, = 2x, + 3 + (yf+1 - y? ) - (ỵ
M - ỵ )• Vậy :♦ Pi+1 = p i + %x i + 3 nếu p. I 0 ¿0 ta chọny*! = Vi - 1 .• Pữ ứng cùng với điểm ban đầu (*o>yo) - (o, -R) .Po = F *0 + l , y 0 - = F 1 , R - = - - R 4Dương Anh Đức, Lê Đình Duy những thuột toán vẽ mặt đường 17/22Đồ HỌA MÁY TÍNHLưu đồ thuật toán Mid
Point vẽ đường tròn
Dương Anh Đức, Lê Đình Duy các thuột toán vẽ nhường nhịn 18/22Đồ HỌA MÁY TÍNHCài để minh họa thuật toán Mid
Point vẽ mặt đường tròn void Circle
Mid
Point (int R)int X, y;X = 0; y = R;Put8Pixel(x, y);P = 1 - R; / / 5/4-R while (x 0 và giüf nguyên giâ tri vào trtfcfng hç/p ngii
Oc lai cần neu làn lap trirôc giâ tri p>0 thi giâ tri Delta2 së duoc tưng 4 cùng neu làn lap trirôc giâ tri p. 0, dạng hyperbol.Ta đã áp dụng phát minh của thuật toán Mid
Xem thêm:
Point đê vẽ các đường conics và một vài đường cong khác, theo công việc tuần từ sau:• cách 7 ; phụ thuộc dáng điệu và phương trình con đường cong, giúp xem thử rất có thể rút gọn gàng phần mặt đường cong buộc phải vẽ hay không.• cách 2 : Tính đạo hàm để từ đó tạo thành các vùng vẽ :♦ nếu 0 — /* (#) — 1 thì* Í +1 = x i + 1yí+i s b i ^ i + 1) (*)* ¡ .1 = X i + 1tt+ie bi>yt - 1 (*)y i+1 = y> + 1Xui e xi,x l +1 (*)ị y u i = y t + 1♦ giả dụ /"(*) linedrawing_6024.pdf