[Schooll_ĐHMT] Thuật toán Breshenham vẽ đoạn thẳng

Tháng Mười Hai 16, 2014 nguyenvanquan7826 School Đồ họa máy tính 19 responses

Nội dung
1. Xây dựng thuật toán
2. Lưu đồ thuật toán
3. Code minh họa
4. Code cho mọi trường hợp
Đọc thêm
1. Nguyên lý chung vẽ đoạn thẳng
2. Thuật toán DDA vẽ đoạn thẳng
3. Thuật toán Midpoint vẽ đoạn thẳng



1. Xây dựng thuật toán Breshenham

Cho 2 điểm đầu mút M1 (x1, y1), M2(x2, y2) và màu vẽ C.
Trong bài nguyên lý chung vẽ đoạn thẳng chúng ta đã xây dựng phương trình đường thẳng có dạng:

y = mx + b. \text{ Trong do: } \begin{cases} m = \frac{y2 - y1}{x2-x1} = \frac{Dy}{Dx} \\ b = y1 - m.x1 \end{cases}

Để đơn giản hóa giải thuật ta xét đường thẳng với m in [0,1] , Dx > 0
Tại mỗi bước ta cho x tăng lên 1 đơn vị tức là x_{k + 1} = x_{k} + 1 . Bước tiếp theo là ta tính y_{k + 1} nhưng ta sẽ không làm giống thuật toán DDA vì nó phải xử lỹ dữ liệu trên số thực và làm tròn số dẫn tới mất thời gian. Ta sẽ tìm các tính theo các số nguyên.

Giả sử tại bước thứ k ta có được hình vẽ như sau:
thuật toán Breshenham
Gọi y là tung độ chính xác của y_{k + 1}. Ta sẽ lấy giá trị y là giá trị gần nhất với y_{k} + 1 hay y_{k}. Để làm việc này ta xét d1 và d2.
d1 = y - y_{k} = m(x_{i} + 1) + b - y_{k} \\ d2 = y_{k} + 1 - y = y_{k} + 1 - m(x_{i}+1) - b \\ => d1 - d2 = 2m(x_{i} +1) - 2y_{k} + 2b - 1
Nếu d1 > d2 khi đó y_{k + 1} = y_{k} + 1
Nếu d1 < d2 khi đó y_{k + 1} = y_{k}
Do đó nếu ta xác định được dấu của d1 – d2 thì ta sẽ biết được giá trị của y_{k+1} . Ta xét hằng số P_{k} = (x1-x2)(d1-d2) (Ta nhân với (x1-x2) để triệt tiêu được mẫu khi thay m vào khi tính toán).
Do Dx > 0 nên P_{k} chỉ phụ thuộc vào d1 -d2. Ta có:
$latex
m = \frac{y2-y1}{x2-x1} \\
\Rightarrow P_{k} = (x2-x1)(d1 – d2) \\
\indent \indent= (x2-x1).\frac{2(y2-y1)(x_{k}+1) +(x2-x1)(-2y_{k} + 2b – 1)}{x2-x1} \\
\indent \indent = 2(y2-y1)x_{k} – 2(x2-x1)y_{k} + 2(y2-y1) + (x2-x1)(2b-1) \\
\indent \indent = 2x_{k}Dy – 2y_{k}.Dx + c

\\
\Rightarrow P_{k+1} = 2(x_{k}+1)Dy – 2y_{k+1}Dx + c, voi : \left (c= 2Dy + (2b-1)Dx \right ) \\
\\
TH1: P_{k} \geq 0 \Rightarrow d1 \geq d2 \\
\indent \indent \Rightarrow y_{k+1} = y_{k} + 1 \\
\indent \indent \Rightarrow P_{k+1} = 2(x_{k}+1)Dy – 2(y_{k} + 1)Dx + c = P_{k} + 2(Dy – Dx) \\
\\
TH2: P_{k} < 0 \Rightarrow d1 < d2 \\ \indent \indent \Rightarrow y_{k+1} = y_{k} \\ \indent \indent \Rightarrow P_{k+1} = 2(x_{k}+1)Dy - 2y_{k}Dx + c = P_{k} + 2Dy \\ $ Tính P1, ta có: $latex y1 = m.x1 + b = \frac{Dy}{Dx}x1 + b\\ P_{1} = 2x1.Dy - 2y1.Dx + c = 2x1.Dy - 2\left ( \frac{Dy}{Dx}x1 + b \right )Dx + 2Dy + (2b - 1)Dx\\ = 2Dy - Dx $
2. Lưu đồ thuật toán
Breshenham

Thuật toán Bresenham chỉ thao tác trên số nguyên và chỉ tính toán trên phép cộng và phép nhân 2 (phép dịch bit). Đ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ày là ở chỗ xét dấu P i để quyết định điểm kế tiếp.

3. Code minh họa

/* Program create in Linux OS
 * nguyenvanquan7826
 */

#include <graphics.h>
#define DELAY 10
int color = RED;

void Bresenham(int x1, int y1, int x2, int y2){
	int x, y, Dx, Dy, p, c1, c2;
	Dx = abs(x2 - x1);
	Dy = abs(y2 - y1);
	p = 2*Dy - Dx;
	c1 = 2*Dy;
	c2 = 2*(Dy-Dx);
	x = x1;
	y = y1;

	int x_unit = 1, y_unit = 1;

	putpixel(x,y,color);
	while(x != x2){
		delay(DELAY);
		if (p<0) p += c1;
		else{
			p += c2;
			y += y_unit;
		}
		x += x_unit;
		putpixel(x, y, color);
	}
}

int main(){
	int gd,gm=VGAMAX; gd=DETECT;
	initgraph(&gd,&gm,NULL);
	setbkcolor(WHITE);
	Bresenham(50,150, 300, 200);		// ve duong thang
	getchar();
	return 0;
}


4. Code cho mọi trường hợp
Code sau sẽ vẽ 8 đoạn thẳng theo 8 hướng, điểm bắt đầu từ tâm.

/* Program create in Linux OS
 * nguyenvanquan7826
 */
#include <graphics.h>
#define DELAY 10
int colorRedBlue = BLUE;
struct point
{
	int x, y;
};
void lineBresenham(int x1, int y1, int x2, int y2){
	int x, y, Dx, Dy, p, c1, c2;
	Dx = abs(x2 - x1);
	Dy = abs(y2 - y1);
	p = 2*Dy - Dx;
	c1 = 2*Dy;
	c2 = 2*(Dy-Dx);
	x = x1;
	y = y1;

	int x_unit = 1, y_unit = 1;

	if (x2 - x1 < 0)
		x_unit = -x_unit;
	if (y2 - y1 < 0)
		y_unit = -y_unit;

	if (x1 == x2)	// duong thang dung
	{
		while (y != y2+1)
		{
			delay(DELAY);
			y += y_unit;
			putpixel(x, y, colorRedBlue);
		}
	}

	else if (y1 == y2)	// duong ngang
	{
		while (x != x2+1)
		{
			delay(DELAY);
			x += x_unit;
			putpixel(x, y, colorRedBlue);
		}
	}
	else{
		putpixel(x, y, colorRedBlue);
		while(x != x2){
			delay(DELAY);
			if (p<0) p += c1;
			else{
				p += c2;
				y += y_unit;
			}
			x += x_unit;
			putpixel(x, y, colorRedBlue);
		}
	}
}

int main(){
	int gd,gm=VGAMAX; gd=DETECT;
	initgraph(&gd,&gm,NULL);
	setbkcolor(WHITE);
	int x = 100, y = 200;
	point A[9] = {{getmaxx()/2, getmaxy()/2},
					{A[0].x-x, A[0].y-y},
					{A[0].x-x, A[0].y+y},
					{A[0].x+x, A[0].y+y},
					{A[0].x+x, A[0].y-y},
					{A[0].x, A[0].y-y},
					{A[0].x-x, A[0].y},
					{A[0].x, A[0].y+y},
					{A[0].x+x, A[0].y},
				};

	for (int i=1; i<9; i++)
	{
		lineBresenham(A[0].x, A[0].y, A[i].x, A[i].y);
	}

	getchar();
	return 0;
}

Tuy nhiên do lý do làm tròn liên tục y và giá trị làm tròn đó lại được lưu lại để tính toán tiếp nên đường thẳng vẽ bằng thuật toán này không chính xác. Ta có thể quan sát sự khác biệt giữa thuật toán này và DDA với cùng 1 hệ các đường thẳng.

A[] = {
	{getmaxx()/2, getmaxy()/2},
	{A[0].x-x, A[0].y-y},
	{A[0].x-x, A[0].y+y},
	{A[0].x+x, A[0].y+y},
	{A[0].x+x, A[0].y-y},
	{A[0].x, A[0].y-y},
	{A[0].x-x, A[0].y},
	{A[0].x, A[0].y+y},
	{A[0].x+x, A[0].y}
}

so sánh Breshenham và DDA
Các đường thẳng màu xanh là của Breshenham, màu hồng là của DDA. (DDA chính xác hơn). Các đường ngang và dọc thì chúng khớp hoàn toàn với nhau. Và dưới đây là đoạn code cho thuật toán Breshenham cải tiến.

// Ve duong thang Bresenham Cai tien
void lineBresenham_1(int x1, int y1, int x2, int y2) 
{ 
	int c2, c, Dx, Dy, x, y;
	Dx = abs(x2 - x1);
	Dy = abs(y2 - y1);
	c = Dx - Dy;
	c2 = 2*c;
	x = x1;
	y = y1;
	
	int x_unit = 1, y_unit = 1;
	
	if (x2 - x1 < 0)
		x_unit = -x_unit;
	if (y2 - y1 < 0)
		y_unit = -y_unit;

	putpixel(x, y, colorGreen);
	
	if (x1 == x2)	// duong thang dung
	{
		while (y != y2)
		{
			delay(DELAY);
			y += y_unit;
			putpixel(x, y, colorGreen);
		}
	}
	
	else if (y1 == y2)	// duong ngang
	{
		while (x != x2)
		{
			delay(DELAY);
			x += x_unit;
			putpixel(x, y, colorGreen);
		}
	}
	
	else if (x1 != x2 && y1 != y2)	// duong xien
	{
		while(x != x2+1)
		{
			delay(DELAY);
			c2 =2*c;
			if (c2 > -Dy)	
			{
				c = c - Dy;	
				x = x + x_unit;
			}
			if (c2 < Dx)	
			{
				c = c + Dx;	
				y = y + y_unit; 
			}
			putpixel(x, y, colorGreen);
		}
	}
}

Khi chạy bằng đoạn code này so với DDA thì chúng hoàn toàn trùng khớp