Đặt vấn đề Cho 2 điểm A (x1, y1) và B (x2, y2). Vẽ đường thẳng đi qua A, B. Thuật giải Thuật toán Bresenham đưa ra cách chọn yi+1 là yi hay yi+1 theo một hướng khác. Đó là so sánh khoảng cách giữa điểm thực y với 2 điểm gần kề nó nhất.
Nếu điểm nào nằm gần điểm thực hơn thì sẽ được chọn làm điểm vẽ tiếp theo. 4 Tieu luan Hình 1.1: Mô tả thuật toán Bressenham Ta có phương trình đường thẳng có dạng: y = mx +b, m = ∆y / ∆x Gọi d1 là khoảng cách từ điểm M đến điểm Q Gọi d2 là khoảng cách từ điểm M đến điểm P Ta có: Nhìn vào hình bên ta thấy: d1 = yi +1 -y = yi +1 – m(xi+1) – b d2 = y- yi = m(xi+1) + b - yi Ta xét (d1-d2): d1-d2 > 0 => d1>d2 => Yi+1 = Yi +1 Ngược lại: d1 ≤ d2 => Yi+1 = Yi 5 Tieu luan d1 – d2 = [m(xi + 1) + b - yi] – [yi + 1 - m(xi + 1) - b] = m(xi + 1) + b – yi - yi – 1 + m(xi + 1) + b = 2m(xi +1) – 2yi + 2b -1 Dễ thấy d1-d2 tồn tại phép toán với số thực m = dy/dx. Và để tuân thủ theo đúng ý tưởng thuật toán chỉ thực hiện các phép toán trên số nguyên, ta khử phân số (triệt tiêu mẫu số) bằng cách nhân 2 vế với dx: Đặt pi = dx(d1 -d2) Pi = dx[2m(xi +1) + 2b – 2yi -1] Thay m = dy/dx vào phương trình trên ta được: Pi = 2dyxi - 2dxyi + c ( với c = 2dy + (2b – 1)dx ) Mặt khác dx ≥ 0 với mọi trường hợp Dấu của pi cùng dấu với (d1-d2) pi > 0 => yi+1 = yi +1 pi ≤ 0 => yi+1 = yi ta có Pi+1 = 2dyxi+1 – 2dxyi+1 + c Pi = 2dyxi - 2dxyi + c Pi+1 - Pi = 2dy(xi+1 - xi) – 2dx(yi+1- yi) = 2dy – 2dx(yi+1 – yi ) với (xi+1 – xi) = 1 Pi+1 = Pi + 2dy – 2dx(yi+1 – yi ) Nếu Pi < 0 => yi+1 = yi => Pi+1 = Pi + 2dy Ngược lại Pi < 0 => yi+1 = yi +1 => Pi+1 = Pi + 2(dy – dx) Ta có P1 = 2x1dy – 2y1dx + c = 2x1dy -2((dy/dx)x1 + b)dx + 2dy + (2b -1)dx = 2dy -dx Lưu đồ thuật toán: 6 Tieu luan Hình 1.2: Lưu đồ thuật toán Bressenham vẽ đường thẳng Code minh họa: void BrePoint(int x1, int y1, int x2, int y2) { glColor3f(1, 0, 0); glBegin(GL_POINTS); int dx = abs(x2 - x1); int dy = abs(y2 - y1); int p = 2 * dy - dx; int c1 = 2 * dy; int c2 = 2 * (dy - dx); int x = x1; int y = y1; glVertex2i(x, y); while (x < x2) { 7 Tieu luan if (p < 0) { p = p + c1; } else { p = p + c2; y++; } x++; glVertex2i(x, y); } glEnd(); return; } 1. Áp dụng thuật toán Bressenham để vẽ đường tròn 1.
Thuật giải Cho đường tròn tâm (xc,yc) bán kính R: (x-xc)^2 + (y-yc)^2 = R^2 Xét đường tròn tâm (xc,yc) ta có : Đường tròn có tính đối xứng nên ta chỉ cần vẽ 1/8 cung tròn và lấy đối xứng qua các điểm: (-x,y), (x,y), (y,x), (y,-x), (x,-y), (-x,-y), (- y, -x), (-y,x) 8 Tieu luan Hình 1.3: Hình tròn với các điểm đối xứng Ta có xi+1 = xi +1 và yi+1 = yi hay yi+1 = yi -1 Phương trình đường tròn tâm (xc,yc) bán kính R : (x-xc)2 + (y-yc)2 = R2 Đặt d1 = yi 2 – y2 và d2 = y2 – (yi -1)2 Đặt pi = d1-d2 do đó việc chọn tọa độ của yi+1 phụ thuộc và dấu của pi: Hình 1.4: Xác định và vẽ các tọa độ 9 Tieu luan d1 = yi 2 – y2 = yi 2 – (R2 – (xi +1)2) d2 = y2 – (yi -1)2 = (R2 – (xi +1)2) - (yi -1)2 Xét pi = d1-d2 = (yi)2+(yi-1)2-2(R2 – (xi+1)2) Tính pi+1 - pi = 4xi + 6 + 2((yi-1)2 – (yi)2) – 2(yi+1 – yi)) pi+1 = pi + 4xi + 6 + 2((yi-1)2 – (yi)2) – 2(yi+1 – yi)) Xác định dấu của pi thì ta sẽ xác định được yi+1 Nếu pi < 0 thì yi+1 = yi khi đó pi+1 = pi + 4xi + 6 Nếu pi >= 0 thì yi+1 = yi-1 nên pi+1 = pi + 4(xi – yi) + 10 Gía tri p đầu tiên được tính tại điểm (x1,y1) = (0,R) là p1 = 3-2R 10 Tieu luan Hình 1.5: Lưu đồ thuật toán Bressenham vẽ hình tròn 11 Tieu luan Code minh họa : void BresCircle(int xc ,int yc, int r) { glColor3b(1, 1, 0.5); glBegin(GL_POINTS); int p1; p1 = 3 - 2 * r; int x = 0; int y = r; glVertex2i(x, y); while (x <= y) { if (p1 < 0) { p1 += 4 * x + 6; } else { p1 += 4 * (x - y) + 10; y--; } x++; glVertex2i(x + xc, y + yc); glVertex2i(-x + xc, y + yc); glVertex2i(x + xc, -y + yc); glVertex2i(-x + xc, -y + yc); glVertex2i(y + xc, x + yc); glVertex2i(-y + xc, x + yc); glVertex2i(y + xc, -x + yc); glVertex2i(-y + xc, -x + yc); } glEnd(); return; } 12 Tieu luan 1. Áp dụng thuật toán Bressenham để vẽ hình elip 1.1 Thuật giải: Tính khoảng cách từ điểm thực đến 2 điểm vẽ được, xem khoảng cách nào ngắn hơn. Vẽ 1 nửa elip, sau đó lấy đối xứng qua các đường phân giác. Phương trình đường elip có dang: x2/a2 + y2/b2 =1 => y2 = -(b2 / a2).y2+ a2 Chúng ta sẽ đi vẽ từng nửa elip.
Ở mỗi nửa elip, chúng ta lại phải vẽ theo hai nhánh khác nhau. Đó là một nhánh từ trên xuống, và một nhánh từ dưới lên. Hai nhánh này cắt nhau tại giao điểm mà ở đó hệ số góc của tiếp tuyến với Elip bằng -1.Chúng ta dễ dàng thấy được nhánh vẽ từ trên xuống : khi x tăng lên 1 đơn vị thì y chỉ tăng lên rất ít ; và ngược lại với nhánh vẽ từ dưới lên: khi y tăng lên 1 đơn vị thì x chỉ tăng lên rất ít. Nếu như chúng ta chọn cách vẽ liền một mạch thì việc tăng lên không đồng đều của tọa độ x và y sẽ khiến đường elip không mịn, đứt gãy, rất xấu.
Do đó, muốn vẽ được đường elip mịn nét, chúng ta sẽ phải chia elip thành 2 nhánh để vẽ.6: Vẽ elip theo 2 hướng 13 Tieu luan Xét nhánh 1 từ trên xuống : Giả sử giao điểm (xi,yi) đã được vẽ điểm tiếp theo cần được vẽ là điểm (xi+1, yi) hoặc (xi+1, yi-1) Thay (xi+1) vào phương trình ta được: y2 = -(b2 / a2).y2+ a2 Đặt d1 = xi2 – x2 = xi2 + (a2 / b2). Thuật toán Midpoint 2. Thuật toán Midpoint vẽ đường thẳng Thuật giải: Cho 2 điểm A(x1,y1) và B(x2,y2). Vẽ đường thẳng đi qua 2 điểm A,B Hình 1.7 : Vẽ đường thẳng bằng thuật toán midpoint 16 Tieu luan Thuật toán Midpoint đưa ra cách chọn điểm yi+1 là yi hay yi+1 bằng cách so sánh điểm thực Q(xi+1 , y) với điểm Midpoint là trung điểm của S và P.
Nếu điểm Q nằm dưới điểm Midpoint thì ta chọn điểm S là điểm vẽ tiếp theo. Ngược lại , nếu điểm Q nằm trên điểm Midpoint thì ta chọn P. Ta có dạng tổng quát của PT đường thẳng : Ax + By +C=0 Với A= yo –y1 ; B= -(x2 –x1) ; C=x2y1 –x1y2 Đặt F(x,y)= Ax+ By +C Đặt F(x,y)= Ax+ By +C Ta có nhận xét: Vị trí tương đối của điểm Midpoint (x,y) với đường thẳng: F(x,y) < 0 nếu (x,y) nằm phía trên đường thẳng F(x,y) = 0 nếu (x,y) thuộc về đường thẳng F(x,y) > 0 nếu (x,y) nằm phía dưới đường thẳng Lúc này việc chọn các điểm S, P ở trên được đưa về việc xét dấu của pi = 2F(Midpoint) = 2F(xi +1 , yi +1/2) Nếu pi < 0 ⇒ Midpoint nằm phía trên đường thẳng ⇒Lúc này điểm thực Q nằm phía dưới điểm Midpoint ⇒ Chọn S(xi+1,yi). Nếu pi >= 0 ⇒ Midpoint nằm phía dưới đường thẳng ⇒ Lúc này điểm thực Q nằm trên điểm Midpoint ⇒ Chọn P(xi+1,yi+1).
Mặt khác: pi+1 –pi = 2F(xi+1 +1 , yi+1 +1/2) – 2F(xi +1 , yi +1/2) ⇒ pi+1 –pi =2[A(xi+1 +1) + B(yi+1 +1/2) +C] – 2[A(xi +1) + B(yi+1/2) +C] ⇒ pi+1 –pi = 2A + 2B(yi+1 – yi) ⇒ pi+1 –pi = 2Dy – 2Dx(yi+1 – yi) Vậy 17 Tieu luan pi+1 =pi + 2Dy nếu pi <0 do ta chọn yi+1 =yi pi+1 =pi + 2Dy – 2Dx nếu pi >=0 do ta chọn yi+1 =yi +1 Ta tính giá trị p1 ứng với điểm ban đầu (x1, y1) với nhận xét rằng điểm (x1, y1) là điểm thuộc đường thẳng, tức là có Ax1 + By1 + C =0. p1 = 2F(x1 +1, y1 +1/2) = 2[A(x1 +1) +B(y1 +1/2) +C] ⇒ p1 = 2(Ax1 + By1 +C) +2A +B ⇒ p1 = 2A + B ⇒ p1 = 2Dy-Dx Lưu đồ thuật toán: Hình 1.8: Lưu đồ thuật toán midpoint vẽ đường thẳng 18 Tieu luan Code minh họa : void Midpoint(int x1, int y1, int x2, int y2) { //Truong hop 0<m<1 && x1<x2 && y1<y2 glColor3f(1, 0, 0); glBegin(GL_POINTS); int a, b, pi, x, y, p; a = y2 - y1; b = -(x2 - x1); y = y1; x = x1; glVertex2i(x, y); //Ve diem pixel dau tien p = 2 * a + b; //tinh vi tri tuong doi cua diem Midpoint so voi duong thang while (x < x2) { if (p < 0) { p += 2 * a; // ta chon chon diem yi } else { y++; p += 2 * (a + b);//ta chon diem yi +1 } x++; glVertex2i(x, y); } glEnd(); return; } 2. Thuật toán Midpoint vẽ đường tròn Thuật giải: Đường tròn có tâm O(xc, yc) = (0, 0), bán kinh r có phương trình: x2 + y2 = r2 => x2 + y2 - r2 = 0 Đặt f(x, y) = x2 + y2 - r2 19 Tieu luan Với mọi điểm P(x, y) nằm trong hệ tọa độ Oxy, ta có: P(x, y) nằm trên đường tròn O nếu f(x, y) = 0 P(x, y) nằm ngoài đường tròn O nếu f(x, y) > 0 P(x, y) nằm trong đường tròn O nếu f(x, y)< 0 Do đường tròn có tính đối xứng qua các cũng 1/8, nghĩa là ứng với một điểm có tọa độ (x, y) thuộc 1 cung nào đó, ta có thể hoàn toàn xác định được tọa độ 7 điểm còn lại bằng cách lấy đối xứng qua các cung. Từ tính chất đó nên chúng ta chỉnh cần vẽ 1/8 đường tròn là đủ, sau đó sẽ lấy đối xứng để được đường tròn hoàn chỉnh.