Đồ họa máy tính

Thành Viên Trong Nhóm
Nguyễn Vĩnh Hảo  0985401816
Nguyễn Thị Hồng Linh  0987741704
Lê Thụy Hoài Phương  0955002770
Phạm Thị Thủy  0929043688
Nguyễn Lê Cẩm Ngọc  0985024152

ĐỒ HỌA MÁY TÍNH
Tìm hiểu và cài đặt các thuật toán vẽ đường cho trường hợp tổng quát

Input:
(x1,y1)(x2,y2)
Output :
{(x1,y1)(x2,y2)….(xn,yn)}
là những điểm sáng nằm trên đường thẳng.
(x1,y1)
(X2,y2)
(x1,y1)
(x2,y2)
1.Tăng chậm
2.Tăng nhanh
3. Giảm chậm ngược
4. Giảm nhanh ngược
- Đối tượng mô tả trong hệ tọa độ thực là đối tượng liên tục, còn đối tượng trong hệ tọa độ thiết bị là đối tượng rời rạc. Nên cần thực hiện việc rời rạc hóa và việc nguyên hóa một cách tối uư nhất.
Từ đó hình thành các thuật toán khác nhau với những uư thế riêng của nó để tối uư về mặt tốc độ và sự chính xác.

Digital Differential Analyzer
Để hiển thị trên lưới nguyên được liền nét các điểm có tọa độ (xi+1; yi+1) sẽ phải chọn 1 trong 8 điểm có tọa độ (xi + 1;yi + 1 )
3
5
8
2
7
6
4
1
Thuật toán DDA là một thuật toán tính toán các điểm vẽ dọc theo đường thẳng dựa vào hệ số góc của phương trình đường thẳng y = mx + b
Trường hợp 1
Đoạn thẳng tăng chậm với điểm đầu A(x1;y1) ở bên trái và điểm cuối B(xk; yk) ở bên phải và trường hợp đối xứng qua ox
A
B
y = mx + b (0 < |m| <=1 )
m = (yk – y1)/(xk – x1)
Bước 1: Xác định điểm đầu tiên
x1 = x1 ;
y1 =y1;
Bước 2: Xác định những điểm tiếp theo
Lặp
x1 < xk ;
xi+1 = xi +1 ;
y = yi + m ; //đã cải tiến y
yi+1 = Round(y);
A
B
Lưu đồ thuật toán DDA vẽ đoạn thẳng qua 2 điểm (x1,y1) và (x2,y2)
trong trương hợp 1
begin
xend
x=x+1;
y=y+m;
Putpixel(x,Round(y),c);
m=Dy/Dx;
x=x1;
y=y1;
Putpixel(x,y,c);
NO
yes
Cài đặt thuật toán DDA trong trường hợp 1
#include
#include
#include
#define Round(a) int(a+0.5)
using namespace std;
Void DDA_line1(int x1,int y1,int x1,int y2, Color c)
{
int Dx = x2-x1; Dy= y2-y1;
float m = (float)Dy/Dx;
if (abs(m) < 1)
{
int x = x1;
float y = y1;
putpixel(x, Round(y),c);
while (x < x2)
{
x++;
y = y+m;
putpixel(x, Round(y), c);
}
}
}
Trường hợp 2
Đoạn thẳng tăng nhanh với điểm đầu A(x1;y1) ở bên trái và điểm cuối B(xk; yk) ở bên phải và trường hợp đối xứng qua oy
A
B
y = mx + b (|m| > 1 )
m = (yk – y1)/(xk – x1)
Bước 1: Xác định điểm đầu tiên
x1 = x1 ;
y1 =y1;
Bước 2: Xác định những điểm tiếp theo
Lặp
y1 < yk ;
x = xi +1/m;
xi+1 = Round(x) ;
yi+1 = yi +1;
A
B
Lưu đồ thuật toán DDA vẽ đoạn thẳng qua 2 điểm (x1,y1) và (x2,y2)
trong trường hợp 2
begin
yend
x=x+1/m;
y=y+1;
Putpixel(Round(x),y,c);
m=Dy/Dx;
x=x1;
y=y1;
Putpixel(x,y,c);
NO
yes
Cài đặt thuật toán DDA trong trường hợp 2
#include
#include
#include
#define Round(a) int(a+0.5)
using namespace std;
Void DDA_line1(int x1,int y1,int x1,int y2, Color c)
{
int Dx = x2-x1; Dy= y2-y1;
float m = (float)Dy/Dx;
if (abs(m) > 1)
{
float x = x1;
int y = y1;
putpixel(Round(x),y,c);
while (y < y2)
{
x = x+1/m ;
y ++;
putpixel(Round(x), y, c);
}
}
}
Trường hợp 3
Đoạn thẳng giảm chậm với điểm đầu A(x1;y1) ở bên phải trên và điểm cuối B(xk; yk) ở bên trái dưới và đối xứng của nó qua ox
y = mx + b (0 < |m| <=1 )
m = (yk – y1)/(xk – x1)
Bước 1: Xác định điểm đầu tiên
x1 = x1 ;
y1 =y1;
Bước 2: Xác định những điểm tiếp theo
Lặp
x1 > xk ;
xi+1 = xi -1 ;
y = yi - m ;
yi+1 = Round(y);
B
A
B
A
Lưu đồ thuật toán DDA vẽ đoạn thẳng qua 2 điểm (x1,y1) và (x2,y2)
trong trường hợp 3
begin
x >x2
end
x=x-1;
y=y-m;
Putpixel(x,Round(y),c);
m=Dy/Dx;
x=x1;
y=y1;
Putpixel(x,y,c);
NO
yes
Cài đặt thuật toán DDA trong trường hợp 3
#include
#include
#include
#define Round(a) int(a+0.5)
using namespace std;
Void DDA_line1(int x1,int y1,int x1,int y2, Color c)
{
int Dx = x2-x1; Dy= y2-y1;
float m = (float)Dy/Dx;
if (abs(m) < 1)
{
int x = x1;
float y = y1;
putpixel(x, Round(y),c);
while (x > x2)
{
x --;
y = y - m;
putpixel(x, Round(y), c);
}
}
}
Trường hợp 4
Đoạn thẳng giảm nhanh với điểm đầu A(x1;y1) ở bên phải và điểm cuối B(xk; yk) ở bên trái và đối xứng của nó qua oy
A
B
y = mx + b (m > 1 )
m = (yk – y1)/(xk – x1)
Bước 1: Xác định điểm đầu tiên
x1 = x1 ;
y1 =y1;
Bước 2: Xác định những điểm tiếp theo
Lặp
y1 > yk ;
x = xi -1/m;
xi+1 = Round(x) ;
yi+1 = yi -1;
A
B
Lưu đồ thuật toán DDA vẽ đoạn thẳng qua 2 điểm (x1,y1) và (x2,y2)
trong trường hợp 4
begin
y > y2
end
x=x-1/m;
y=y-1;
Putpixel(Round(x),y,c);
m=Dy/Dx;
x=x1;
y=y1;
Putpixel(x,y,c);
NO
yes
Cài đặt thuật toán DDA trong trường hợp 4
#include
#include
#include
#define Round(a) int(a+0.5)
using namespace std;
Void DDA_line1(int x1,int y1,int x1,int y2, Color c)
{
int Dx = x2-x1; Dy= y2-y1;
float m = (float)Dy/Dx;
if (abs(m) > 1)
{
float x = x1;
int y = y1;
putpixel(Round(x),y,c);
while (y > y2)
{
x = x-1/m ;
y --;
putpixel(Round(x), y, c);
}
}
}
Luư đồ thuật toán DDA trong tất cả các trường hợp vẽ đường thẳng
begin
Dx = x2 – x1
Dy = y2 – y1
abs(Dx) > abs(Dy)
xinc = Dx / step
yinc = Dy / step
x = x1; y = y1
putpixel (x, y,c )
end
NO
YES
step = abs(Dx)
step = abs(Dy)
k<= step
YES
NO
YES
x = x + xinc
y = y + yinc
Putpixel(Round(x),Round(y),c)
NO
Cài đặt thuật toán DDA trong trường hợp Tổng quát
#include
#include
#include
#define Round(a) int(a+0.5)
using namespace std;
Void DDA_line1(int x1,int y1,int x1,int y2, Color color){
double x,y; int step;
if(abs(x2-x1)>abs(y2-y1))
step=abs(x2-x1);
else
step=abs(y2-y1);
x=(double)x1;
y=(double)y1;
putpixel(Round(x),Round(y),color);
double m=(double)(x2-x1)/step;
double n=(double)(y2-y1)/step;
for(double i=1;i<=step;i++)
{
x+=m;
y+=n;
putpixel(Round(x),Round(y),color);
}
}
Ví dụ Demo vẽ đường thẳng từ điểm A(2, 10) đến điểm B(21, 16) (0 < m < 1) điểm A(9, 1) đến điểm B(17,12) (m > 1) bằng thuật toán DDA.
A (2, 10) đến B (21, 1) m= 6/19 = 0,316 < 1
i xi yi y
0 2 10 10
3 10 10,316
4 11 10,632
5 11 10,948
6 11 11,264
7 12 11,580
8 12 11,896
9 12 12,212
10 13 12,528
11 13 12,844
12 13 13,160
13 13 13,476
14 14 13,792
15 14 14,108
16 14 14,424
17 15 14,740
18 15 15,056
19 15 15,372
20 16 15,688
21 16 16,004
A ( 9,1 ) đến B (17 , 12 ) m= 11/8 = 1.375> 1
1/m = 0,73
i xi yi x
0 9 1 9
10 2 9,73
10 3 10,46
11 4 11,19
12 5 11,92
13 6 12,65
13 7 13,38
14 8 14,11
15 9 14,84
16 10 15,57
16 11 16,30
17 12 17,03
Tất cả các trường hợp của đoạn thẳng còn lại được vẽ dựa trên thuật toán DDA bằng việc hoán đổi vị trí của điểm đầu và điểm cuối hoặc lấy đối xứng qua các trục tọa độ của 4 trường hợp trên.
Việc sử dụng công thức để tính giá trị y tại mỗi bước đã giúp cho thuật toán DDA nhanh hơn hẳn so với cách tính y từ phương trình y=mx +b do khử được phép nhân trên số thực. Tuy nhiên, việc cộng dồn giá trị thực m vào y có thể sẽ tích lũy sai số làm cho hàm làm tròn có kết quả sai dẫn tới việc xác định vị trí của điểm vẽ ra bị chệch hướng so với đường thẳng thực. Điều này chỉ xảy ra khi vẽ đoạn thẳng khá dài.
Tuy đã khử được phép nhân số thực nhưng thuật toán DDA vẫn còn bị hạn chế về mặt tốc độ do vẫn còn phép toán cộng số thực và làm tròn. Có thể khắc phục thao tác cộng số thực m và làm tròn trong thuật toán bằng cách nhận xét m=Dy/Dx với Dy, Dx là các số nguyên.
- 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 sao cho có thể tối ưu hóa về mặt tốc độ so với thuật toán DDA. Vấn đề mấu chốt ở đây là làm thế nào để hạn chế tối đa các phép toán trên số thực trong thuật toán.
- Ý tưởng chính của thuật toán Bresenham là việc so sánh khỏang cách giữa tọa độ y thực tại vị trí xi+1 với các tọa độ y nguyên trên và dưới nó.
*** Phương pháp của thuật toán Bresenham
Gọi (xi+1,y) là điểm thuộc đoạn thẳng thực.
Ta có: y = m( xi+1) + b. (0 < m <1)
Xét các hiệu khoảng cách của tung độ thực y so với các tung độ nguyên yi và yi+1 để chọn một điểm là S(xi +1, yi) hay P( xi + 1,yi + 1) gần với điểm thực nhất.
Đặt d1 = y - yi
d2 = ( yi+ 1) - y
- Nếu d1- d2 < 0: Chọn điểm S, tức là yi+1=yi.
- Nếu d1- d2 ≥ 0: Chọn điểm P, tức là yi+1 =yi + 1.
Xây dựng pi
Xét pi = Δx (d1 - d2) với Δx= x2- x1; Δy= y2 –y1;
Ta có : d1 - d2 = 2 yi+1 - 2yi - 1 = 2m(xi+1) + 2b - 2yi - 1
=> pi = Δx (d1 - d2) = Δx[2m(xi+1) + 2b - 2yi - 1] = Δx[2 Δy/Δx (xi+1) + 2b - 2yi - 1]
= 2Δy(xi+1) - 2Δx.yi + Δx(2b - 1) = 2Δy.xi - 2Δx.yi+ 2Δy + Δx(2b - 1)
Vậy C = 2Δy + Δx(2b - 1) = Const
=> pi= 2Δy.xi - 2Δx.yi+ C
Nhận xét rằng nếu tại bước thứ i ta xác định được dấu của Pi thì xem như ta xác định
được điểm cần chọn ở bước (i+1). Ta có :
pi +1 - pi= (2Δy.xi+1 - 2Δx.yi+1+ C) - (2Δy.xi - 2Δx.yi+ C )
=> Pi +1 = pi + 2Δy - 2Δx ( yi+1 - .yi)
- Nếu pi< 0 : chọn điểm S, tức là yi +1= yi và pi +1 = pi + 2Δy.
- Nếu pi≥ 0 : chọn điểm P, tức là yi +1= yi +1 và pi +1 = pi + 2Δy - 2Δx
- Giá trị p0được tính từ điểm vẽ đầu tiên (x0,y0) theo công thức :
P0= 2Δy.x0 - 2Δx.y0+ C
Do (x0,y0) là điểm nguyên thuộc về đoạn thẳng nên ta có : y0 = m .x0+ b = Δy/Δx.x0 + b
Thế vào phương trình trên ta được :
p0= 2Δy - Δx
Trường hợp 1
|Dy|<=|Dx|
A
B
A
B
B
A
B
A
Các dạng đường thẳng thỏa |yB - yA| <= |xB – xA|
Giải thuật trong trường hợp 1:
|Dy|<=|Dx|;
Bước 1: Xác định điểm đầu
int Dx = x2 – x1, Dy = y2 – y1;
int p = 2 * Dy – Dx;
int const1 = 2 * Dy, const2 = 2 * (Dy-Dx);
int x = x1, y = y1;
putpixel(x, y, color);
int dx =(Dx>0)? 1:-1;
int dy=(Dy>0)? 1:-1;
Bước 2: Xác định những điểm tiếp theo
Lặp
x!=x2 ;
Nếu p<0:
p+=const1;
Nếu p>=0:
p+=const2;
y+=dy;
x+=dx;
Putpixel(x,y,color);

Luư đồ thuật toán Bresenham trường hợp 1: |Dy|<=|Dx|
begin
p = 2Dy - Dx;
const1=2Dy; const2=2(Dy-Dx);
x = x1; y = y1;
putpixel(x,y,color);
dx = (Dx >0)? 1:-1;
dy = (Dy > 0)?1:-1;
x != x2
p+=const1;
end
NO
YES
p < 0
p+=const2;
y + = dy;
x += dx;
Putpixel(x, y,color);
YES
NO
Cài đặt thuật tóan Bresenham trong trường hợp 1
#include
#include
#include
using namespace std;
Void Bresenham_line (int x1,int y1, int x2, int y2, Color color)
{
int Dx = x2 – x1, Dy = y2 – y1; int x = x1, y = y1;
int p = 2 * Dy – Dx ; int const1 = 2 * Dy , const2 = 2 * (Dy-Dx);
putpixel(x, y, color) ;
int dx =(Dx>0)? 1:-1 ,dy=(Dy>0)? 1:-1;
if(abs(Dy) <= abs(Dx)) {
while(x != x2)
{
if ( p < 0) p+=const1;
else {
p+=const2;
y += dy;
}
x += dx;
putpixel(x,y,color);
}
}
}
A
B
A
B
B
A
A
B
Trường hợp 2
|Dy|<=|Dx|
Các dạng đường thẳng thỏa |Dy| > |Dx|
Giải thuật trong trường hợp 2
|Dy|>|Dx|;
Bước 1: Xác định điểm đầu
int Dx = x2 – x1, Dy = y2 – y1;
int x = x1, y = y1;
int p = 2 * Dx – Dy;
int const1 = 2 * Dx, const2 = 2 * (Dx-Dy);
putpixel(x, y, color);
int dx =(Dx>0)? 1:-1;
int dy=(Dy>0)? 1:-1;
Bước 2: Xác định những điểm tiếp theo
Lặp
y!=y2 ;
Nếu p<0:
p+=const1;
Nếu p>=0:
p+=const2;
x+=dx;
y+=dy;
Putpixel(x,y,color);

Luư đồ thuật toán Bresenham trong trường hợp 2: |Dy|>|Dx|
begin
p = 2Dx - Dy;
const1=2Dx; const2=2(Dx-Dy);
x = x1; y = y1;
putpixel(x,y,color);
dx = (Dx >0)? 1:-1;
dy = (Dy > 0)?1:-1;
y != y2
p+=const1;
end
NO
YES
p < 0
p+=const2;
x+ = dx;
y+= dy;
Putpixel(x, y,color);
YES
NO
Cài đặt thuật toán Bresenham trong trường hợp 2
#include
#include
#include
using namespace std;
Void Bresenham_line (int x1,int y1, int x2, int y2, Color color)
{
int Dx = x2 – x1, Dy = y2 – y1; int x = x1, y = y1;
int p = 2 * Dx – Dy ; int const1 = 2 * Dx , const2 = 2 * (Dx-Dy);
putpixel(x, y, color) ;
int dx =(Dx>0)? 1:-1 ,dy=(Dy>0)? 1:-1;
if(abs(Dy) > abs(Dx)) {
while(y != y2)
{
if ( p < 0) p+=const1;
else {
p+=const2;
x += dx;
}
y += dy;
putpixel(x,y,color);
}
}
}
Ví dụ Demo vẽ đường thẳng bằng thuật toán Bresenham qua hai điểm A(5,8) và B(20,13)
Ta có Dy=5, Dx=15; p=2Dy-Dx=-5
const1=2Dy=10, const2=2(Dy-Dx)=-20
Thuật toán Bresenham chỉ làm việc trên số nguyên và các thao tác trên số nguyên chỉ là phép cộng và phép dịch bit (phép nhân 2) điều này là một cải tiến làm tăng tốc độ đáng kể so với thuật toán DDA.
Ý tưởng chính của thuật toán nằm ở chỗ xét dấu pi để quyết định điểm kế tiếp, và sử dụng công thức truy hồi pi+1- pi để tính pi bằng các phép toán đơn giản trên số nguyên.
Tuy nhiên thuật toán Bresenham xây dựng phức tạp hơn thuật toán DDA.
Thuật toán MidPoint đưa ra cách chọn yi+1 là yi hay yi +1 bằng cách so sánh điểm thực Q với điểm MidPoint là trung điểm của S và P. Ta có :
Nếu điểm Q nằm dưới điểm MidPoint, ta chọn S.
- Ngược lại nếu điểm Q nằm trên điểm MidPoint ta chọn P.
Ta có dạng tổng quát của phương trình đường thẳng là :
Ax + By + C = 0 Với A = y2 –y1; B = - (x2 – x1) ; C = x2y1 -x1y2 
Đặt F(x,y)=Ax + By + C thì ta có nhận xét 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) nằm thuộc đườ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 điểm S hay P được đưa về việc xét dấu của pi = 2F(midpoint) = 2F(xi+1;yi+1/2)
Xây dựng pi trong trường hợp 0<=m<=1, và Dx <0
Giống như một số thuật toán khác, ta không tính toán trực tiếp các giá trị pi để chọn điểm tiếp theo mà tính toán dựa trên kết quả của bước trước.
Xét pi+1-pi=2F(xi+1+1,yi+1+1/2)-2F(xi+1,yi+1/2)
Thay F(x,y)=Ax+By+C với A=Dy, B=-Dx vào ta được kết quả pi+1-pi=2Dy-2Dx(yi+1-yi) (1)
Nhận xét:
Khi yi+1=yi ta có (1) pi+1=pi+2Dy
Khi yi+1=yi+1 ta có (1)  pi+1=pi+2Dy-2Dx=pi+2(Dy-Dx)

Giá trị p0 ứng với điểm ban đầu được tính:
p0=2F(xđầu+1, y đầu+1/2)=2[A(xđầu+1)+B(yđầu+1/2)+C] =2Dy-Dx
Tóm tắt thuật toán:
p0=2Dy-Dx
yi+1=



pi+1=

yi nếu pi <0
yi+1 nếu pi >=0
pi+2Dy nếu pi <0
pi+2(Dy-Dx) nếu pi >=0
Trường hợp 1: |Dy|<=|Dx|
A
B
A
B
B
A
B
A
Giải thuật bằng thuật toán Midpoint trong trường hợp 1
|Dy|<=|Dx|;
. Bước 1: Xác định điểm đầu
int Dx = x2 – x1, Dy = y2 – y1;
int x = x1, y = y1;
int p = 2 * Dy – Dx;
int const1 = 2 * Dy, const2 = 2 * (Dy-Dx);
putpixel(x, y, color);
dx =(Dx>0)? 1:-1;
dy=(Dy>0)? 1:-1;
Bước 2: Xác định những điểm tiếp theo
Lặp
x!=x2 ;
Nếu p<0:
p+=const1;
Nếu p>=0:
p+=const2;
y+=dy;
x+=dx;
Putpixel(x,y,color);

Luư đồ thuật toán Midpoint trường hợp 1: |Dy|<=|Dx|
begin
p = 2Dy - Dx;
const1=2Dy; const2=2(Dy-Dx);
x = x1; y = y1;
putpixel(x,y,color);
dx = (Dx >0)? 1:-1;
dy = (Dy > 0)?1:-1;
x != x2
p+=const1;
end
NO
YES
p < 0
p+=const2;
y + = dy;
x += dx;
Putpixel(x, y,color);
YES
NO
Cài đặt thuật tóan Midpoint trong trường hợp 1
#include
#include
#include
using namespace std;
Void Bresenham_line (int x1,int y1, int x2, int y2, Color color)
{
int Dx = x2 – x1, Dy = y2 – y1; int x = x1, y = y1;
int p = 2 * Dy – Dx ; int const1 = 2 * Dy , const2 = 2 * (Dy-Dx);
putpixel(x, y, color) ;
int dx =(Dx>0)? 1:-1 ,dy=(Dy>0)? 1:-1;
if(abs(Dy) <= abs(Dx)) {
while(x != x2)
{
if ( p < 0) p+=const1;
else {
p+=const2;
y += dy;
}
x += dx;
putpixel(x,y,color);
}
}
}
A
B
A
B
B
A
A
B
Trường hợp 2
|Dy|<=|Dx|
Các dạng đường thẳng thỏa |Dy| > |Dx|
Giải thuật bằng thuật toán MidPoint trong trường hợp 2
|Dy|>|Dx|;
Bước 1: Xác định điểm đầu
int Dx = x2 – x1, Dy = y2 – y1;
int x = x1, y = y1;
int p = 2 * Dx – Dy;
int const1 = 2 * Dx, const2 = 2 * (Dx-Dy);
putpixel(x, y, color);
int dx =(Dx>0)? 1:-1;
int dy=(Dy>0)? 1:-1;
Bước 2: Xác định những điểm tiếp theo
Lặp
y!=y2 ;
Nếu p<0:
p+=const1;
Nếu p>=0:
p+=const2;
x+=dx;
y+=dy;
Putpixel(x,y,color);

Luư đồ thuật toán Midpoint trong trường hợp 2: |Dy|>|Dx|
begin
p = 2Dx - Dy;
const1=2Dx; const2=2(Dx-Dy);
x = x1; y = y1;
putpixel(x,y,color);
dx = (Dx >0)? 1:-1;
dy = (Dy > 0)?1:-1;
y != y2
p+=const1;
end
NO
YES
p < 0
p+=const2;
x+ = dx;
y+= dy;
Putpixel(x, y,color);
YES
NO
Cài đặt thuật toán Midpoint trong trường hợp 2
#include
#include
#include
using namespace std;
Void Bresenham_line (int x1,int y1, int x2, int y2, Color color)
{
int Dx = x2 – x1, Dy = y2 – y1; int x = x1, y = y1;
int p = 2 * Dx – Dy ; int const1 = 2 * Dx , const2 = 2 * (Dx-Dy);
putpixel(x, y, color) ;
int dx =(Dx>0)? 1:-1 ,dy=(Dy>0)? 1:-1;
if(abs(Dy) > abs(Dx)) {
while(y != y2)
{
if ( p < 0) p+=const1;
else {
p+=const2;
x += dx;
}
y += dy;
putpixel(x,y,color);
}
}
}
Mở rộng thuật toán Midpoint trong các trường hợp vẽ đường thẳng với m bất kì
***Trường hợp đặc biệt m = : Đoạn thẳng song song trục tung nên rất đơn giản khi vẽ.
***Trường hợp -1<=m<=1 :Sử dụng các công thức của thuật toán vẽ trong trường hợp 0 < = m <=1, Dx >0 và thay đổi một số điểm sau:
Nếu Dx < 0 thì bước nhảy của x sẽ thay bằng -1 tương tự nếu Dy <0, bước nhảy của y cũng sẽ là -1.
Thay Dx bằng abs(Dx), Dy = abs(Dy) trong tất cả các công thức có chứa Dx,Dy
*** Trường hợp m<= -1 hay m>=1
Thay đổi vai trò của x và y cho nhau, thay đổi vai trò của Dx và Dy cho nhau trong tất cả các công thức
Thực hiện nguyên tắt về bước nhảy và thay đổi Dx, Dy như trong trường hợp -1< = m < =1
Dựa vào tính chất đối xứng của đường tròn ta có thể mở rộng các thuật toán Bresenham và Midpoint cho việc vẽ đường tròn
y
THUẬT TOÁN VẼ ĐƯỜNG TRÒN
y
(x,y)
(y,x)
(-y,x)
(x,-y)
(-x,-y)
(-y,-x)
(y,-x)
(-x,y)
x
Trong hệ tọa độ Descartes, phương trình đường tròn bán kính R có dạng:
Với tâm O(0,0) :
x2 + y2 = R2
Với tâm C(xc,yc):
(x - xc)2 + (y - yc)2 = R2
Trong hệ tọa độ cực :
x = xc+ R.cosθ
y = yc + Y.sinθ
với θ thuộc [0, 2π].
- Do tính đối xứng của đường tròn C (xem hình 1.7) nên ta chỉ cần vẽ 1/8 cung tròn,
- sau đó lấy đối xứng qua 2 trục tọa độ và 2 đường phân giác thì ta vẽ được cả đường tròn.
THUẬT TOÁN VẼ ĐƯỜNG TRÒN BẰNG MIDPOINT
Do tính đối xứng của đường tròn nên ta chỉ cần vẽ 1/8 cung tròn, sau đó lấy đối xứng là vẽ được cả đường tròn.
Thuật toán MidPoint đưa ra cách chọn 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 giữa MidPoind là trung điểm của S1 vàS2.
Chọn điểm bắt đầu để vẽ là (0,R). Giả sử (xi, yi) là điểm nguyên đã tìm được ở bước thứ i (xem hình 1.8), thì điểm (xi+1, yi+1) ở bước i+1 là sự lựa chọn giữa S1 và S2.
Xi+1 = x + 1
yi+1= yi – 1 hoặc yi;

THUẬT TOÁN VẼ ĐƯỜNG TRÒN BẰNG MIDPOINT
Đặt F(x,y) = x2 + y2 - R2 , ta có :
. F(x,y) < 0 , nếu điểm (x,y) nằm trong đường tròn.
. F(x,y) = 0 , nếu điểm (x,y) nằm trên đường tròn.
. F(x,y) > 0 , nếu điểm (x,y) nằm ngoài đường tròn.
Xét Pi = F(MidPoint) = F(xi +1, yi - 1/2). Ta có :
- Nếu Pi < 0 : điểm MidPoint nằm trong đường tròn. Khi đó, điểm thực Q gần với điểm
S1 hơn nên ta chọn yi+1 = yi .
- Nếu Pi>= 0 : điểm MidPoint nằm ngòai đường tròn. Khi đó, điểm thực Q gần với điểm
S2 hơn nên ta chọn yi+1 = yi - 1.
Mặt khác :
Pi+1 - Pi = F(xi+1 +1, yi+1 - 1/2) - F(xi + 1, yi - 1/2)
= [(xi+1 +1)2 + (yi+1 - 1/2)2 - R2 ] - [(xi +1)2 + (yi - 1/2)2 - R2 ]
= 2xi + 3 + ((yi+1)2 + (yi)2 ) - (yi+1 - yi)

Vậy :
- Nếu Pi < 0 : chọn yi+1 = yi. Khi đó Pi+1 = Pi+ 2xi +3
- Nếu Pi >= 0 : chọn yi+1 = yi - 1. Khi đó Pi+1 = Pi+ 2xi - 2yi +5.
- Piứng với điểm ban đầu ( x0 , y0 ) = (0,R) là:
P0 = F(x0 + 1, y0 - 1/2) = F(1, R - 1/2) =5/4 -R
XÂY DỰNG THUẬT TOÁN VẼ ĐƯỜNG TRÒN BẰNG MIDPOINT
Q(xi+1,y)
Midpoint
S1
S2
yi
yi-1
yi+1
(xi,yi)
Luư đồ thuật toán Midpoint cho đường tròn
begin
P = 5/4 - R;
x=0 ; y= R;
Putpixel8(x,y,c);
xP = P + 2*x + 3
end
NO
YES
p < 0
P = P + 2*(x-y)+5
y = y - 1
x++;
putpixel8(x,y,color)
YES
NO
Cài đặt thuật toán Midpoint cho đường tròn
void MidpointCircle(int a,int b,int r,Color c){
int x,y;
x=0;
y=r;
put8pixel(x,y,a,b,c);
int p=1-r;
while(x if(p<0) {
p+=2*x+3;
}
else {
p+=2*(x-y)+5;
y--;
}
x++;
put8pixel(x,y,a,b,c);
}
}
Ví dụ Demo đường tròn bằng thuật toán Midpoint
Midpointcircle(15,16,13,Color(255,0,0));
Vẽ đường tròn bằng thuật toán Bresenham
Tương tự thuật toán vẽ đường thẳng Bresenham, các vị trí ứng với các tọa độ nguyên nằm trên đường tròn có thể tính được bằng cách xác định một trong hai pixel gần
nhất với đường tròn thực hơn trong mỗi bước

S1
S2
yi
yi-1
yi+1=y
(xi,yi)
d1
d2
XÂY DỰNG THUẬT TOÁN BRESENHAM VẼ ĐƯỜNG TRÒN
Ta có :
d1 = (yi)2 - y2 = (yi)2 - (R2- (xi + 1)2 )
d2 = y2 - (yi - 1)2 = (R2- (xi + 1)2 ) - (yi - 1)2Pi = d1 - d2
* Tính Pi+1 - Pi
=> Pi+1 = Pi + 4xi + 6 + 2((yi+1)2 - (yi)2 ) - 2(yi+1 - yi)
- Nếu Pi < 0 : chọn yi+1 = yi. Khi đó Pi+1 = Pi+ 4xi +6
- Nếu Pi >= 0 : chọn yi+1 = yi - 1. Khi đó Pi+1 = Pi+ 4(xi - yi ) + 10.
- P0ứng với điểm ban đầu ( x0 , y0 ) = (0,R) là: P0= 3 - 2R.
Luư đồ thuật toán Bresenham cho đường tròn
begin
P= 3 - 2R
x=0 ; y= R;
Putpixel8(x,y,c);
xP = P+ 4x +6
end
NO
YES
p < 0
P += 4(x - y ) + 10
x++;
putpixel8(x,y,color)
YES
NO
Cài đặt thuật toán Bresenham cho đường tròn
void Bres_circle(int a,int b,int r,Color c){
int x,y;
x=0;
y=r;
put8pixel(x,y,a,b,c);
int p=3-2*r;
while(x {
if(p<0) {
p+=4*x+6;
}
else {
p+=4*(x-y)+10;
y--;
}
x++;
put8pixel(x,y,a,b,c);
}
}
Ví dụ Demo thuật toán Bresenham vẽ đường tròn
Bres_circle(25,26,17,Color(225,0,0));
Ngoài ra ta còn có thể mở rộng thuật toán Bresenham cho việc vẽ đường tròn và các đường conic
VẼ ELIP BẰNG BRESENHAM
Tương tự thuật toán vẽ đường tròn, sử dụng thuật toán Bresenham để vẽ, ta chỉ cần
vẽ 1/4 ellipse, sau đó lấy đối xứng qua các trục tọa độ sẽ vẽ được toàn bộ ellipse.
Xét ellipse có tâm O, các bán kính là a và b, phương trình là x^2/a^2 – y^2/b^2=1
Chọn tọa độ pixel đầu tiên cần hiển thị là (xi ,yi) = (0,b). Cần xác định pixel tiếp theo là
(xi+1 ,yi+1).
Ta có :
xi+1=x+1;
yi+1=yi-1 hay yi
d1 = (yi)^2 – y^2
d2 = y^2 - (yi - 1)^2

XÂY DỰNG THUẬT TOÁN BRESENHAM VẼ ELIP
d1 = (yi)^2 – y^2
d2 = y^2 - (yi - 1)^2
Pi = d1 - d2
Tính Pi+1 - Pi
=> Pi+1 = Pi + 2((yi+1)^2 - (yi)^2 ) - 2(yi+1 - yi)+2b^2/a^2(2xi+3)
- Nếu Pi < 0 : chọn yi+1 = yi. Khi đó Pi+1 = Pi+2b^2/a^2(2xi+3)
- Nếu Pi >= 0 : chọn yi+1 = yi - 1.
Khi đó Pi+1 = Pi+2b^2/a^2(2xi+3)+4(1-yi)
- Pi ứng với điểm ban đầu ( x0 , y0 ) = (0,b) là:
P0=2b^2/a^2-2b+1
YES
Luư đồ thuật toán Bresenham cho đường Elip
begin
int x=0,y=b;
int z1= (b*b)/(a*a), z2= 1/ z1;
int P= 2*z1 - 2*b +1; putpixel4(x,y,color)
z1* (x/y) ≤ 1
P +=2*z1*(2*x+3)
end
NO
p < 0
P +=2*z1*(2*x+3) + 4*(1-y);
y--;
x++;
putpixel4(x,y,color)
YES
NO
int y=0,x=a;
int P= 2*z2 - 2*b +1;
putpixel4(x,y,color)
z2* (y/x) < 1
p < 0
P +=2*z2*(2*x+3)
P +=2*z2*(2*x+3) + 4*(1-y);
x--
YES
NO
NO
YES
y++;
putpixel4(x,y,color)
Cài đặt thuật toán Bresenham cho Elip
int x,y;
void ellipse(int xc, int yc, int a, int b, Color color){
double z1,z2,P;
x=0;y=b;
z1=(double)(b*b)/(a*a);
z2=(double)1/z1;
P=2*z1-(2*b)+1;
while(z1*(double)x/y<=1){
put4pixel(xc+x,yc+y,color);
if (P<0) P+=2*z1*(2*x+3);
else{
P+=2*z1*(2*x+3)+4*(1-y);
y--;
}
x++; }
x=a;y=0;
P=2*z2-2*a+1;
while(z2*(double)y/x<=1){
put4pixel(xc+x,yc+y,color);

if (P<0) P+=2*z2*(2*y+3);
else{
P+=2*z2*(2*y+3)+4*(1-x);
x--;
}
y++; }
}

Ví dụ Demo vẽ đường Elip bằng thuật toán Bresenham
ellipse(23,28,22,10,Color(0,225,0));
Đề tài của nhóm 9 đến đây xin kết thúc. Vì thời gian và kiến thức có hạn nên chắc chắn đề tài của chúng em còn nhiều vấn đề sai sót, rất mong được sự giúp đỡ và việc đóng góp ý kiến của thầy. Điều đó giúp chúng em hoàn thành những đề tài sau này tốt hơn. Chúng em xin cảm ơn thầy. Kính chúc thầy sức khỏe dồi dào.
Cảm ơn