[Shool_DHMT] DDA algorithm to draw the line

December 16, 2014 nguyenvanquan7826 School Computer Graphics 8 responses

Content
1. Construction algorithm
2. Flowchart algorithm
3. Code illustrations
4. Code for all cases
Read more
1. General Principles of drawing straight lines
2. Algorithm Breshenham draw straight lines
3. Midpoint algorithm to draw the line



1. Construction DDA algorithm (Digital DifferentialAnalyzer)

Give 2 endpoints M1 (x1, y1), M2(x2, y2) and paint C.
In all General principles of drawing straight lines we have built a straight line equation of the form:

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

To simplify the algorithm we consider the line with m in [0,1] , Dx > 0
At each step one for x increases 1 ie unit x_{i + 1} = x_{i} + 1 \Rightarrow y_{i+1} = y_{i} + m

* Because m is a real number should want y_{i + 1} It must be an integer rounding before retrieving coordinates to make the screen.
* With a straight line m > 1 I will do the opposite for variable y and x in the sense that at each step we have y_{i + 1} = y_{i} + 1 \Rightarrow x_{i+1} = x_{i} + frac{1}{m}
* With straight lines with Dx <0 It will decrease rather than increase x.

2. DDA algorithm flowchart
DDA algorithm


3. Code illustrate the algorithm

/* Program create in Linux OS
 * nguyenvanquan7826 
 */

#include <graphics.h>
#define Round(a) (int)(a+0.5)	// lam tron so
#define DELAY 10
int color = RED;

void lineDDA(int x1, int y1, int x2, int y2){		// thuat toan DDA
	int x_unit = 1, Dx = x2 - x1, Dy = y2 - y1;		// Khoi tao cac gia tri ban dau
	int x = x1;
	float y = y1;
	float m = (float)Dy/Dx;		// he so goc m
	putpixel(x, Round(y), color);
	
	while(x < x2){
		delay(10);	// thoi gian tre khi ve 1 diem anh
		x += x_unit;
		y += m;
		putpixel(x,Round(y), color);
	}
}
int main(){
	int gd,gm=VGAMAX; gd=DETECT;
    initgraph(&gd,&gm,NULL);		// khoi tao cua so do hoa
	setbkcolor(WHITE);
	lineDDA(50,150, 300, 200);		// ve duong thang
	getchar();
	return 0;
}

The results illustrate


4. Code for all cases
The following code will draw 8 segment under 8 direction, starting from the center point.

/* Program create in Linux OS
 * nguyenvanquan7826 
 */

#include <graphics.h>
#include <stdio.h>
#define Round(a) (int)(a+0.5)
#define DELAY 10
int color = RED;
struct point		// diem gom tung do x va hoanh do y
{
	int x, y;
};

void lineDDA(int x1, int y1, int x2, int y2)		// DDA algorithm
{			
	int x_unit = 1, Dx = x2 - x1, Dy = y2 - y1;	// Init first value
	int x = x1;
	float y = y1;
	float y_unit = 1;
	
	if (Dx < 0)			
		x_unit = -1;
	if (Dy < 0)
		y_unit = -1;
		
	if (x1 == x2)	// duong thang dung
	{
		while (y != y2)
		{
			delay(DELAY);
			y += y_unit;
			putpixel(x, Round(y), color);
		}	
	}
	else if (y1 == y2)	// duong ngang
	{
		while (x != x2)
		{
			delay(DELAY);
			x += x_unit;
			putpixel(x, Round(y), color);
		}
	}
	else if (x1 != x2 && y1 != y2)// duong xien
	{
		float m = (float) abs(Dy) / abs(Dx);
		x_unit = 1;
		y_unit = m;
		x = x1;
		y = y1;
		
		if (Dx < 0)			
			x_unit = -1;		// ve x giam
		if (Dy < 0)
			y_unit = -m;		// ve y giam
		
		putpixel(x, Round(y), color);
		while(x != x2)
		{
			delay(10);	// thoi gian tre khi ve 1 diem anh
			x += x_unit;
			y += y_unit;
			putpixel(x, Round(y), 1);
		}
	}
}
int main(){
	int gd,gm=VGAMAX; gd=DETECT;
	initgraph(&gd,&gm,NULL);
	setbkcolor(2);
	int x = 200, y = 100;
	char s[] = "nguyenvanquan7826";
	outtextxy(250,100, s);
	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++)
	{
		lineDDA(A[0].x, A[0].y, A[i].x, A[i].y);
	}
	getchar();
	return 0;
}

The results illustrate