# 前言

画布实现好了，该需要能在画布上画点东西，比如一个点一条线，点好实现，线则需要 Bresenham 算法实现。
完整的代码地址在此。

# 画点

之前已经实现了 TGA 的图像生成。画点只需要在 TGA 图像的缓冲区写入像素数据即可，然后生成即可。

	static void draw2d_point_utils(int x, int y, unsigned char color, image_t image) {

	// (y * height * channels) + (x * channels);
	int position = get_image_position(image, x, y);
	int totalPixels = image->width * image->height * image->channels;

	if (position <= (totalPixels - image->channels) && position > 0) {
	for (int i = 0; i < image->channels; i++) {
	image->data[position + i] = color[i];
	}

	// rgb to bgr
	if (image->channels >= 3) {
	swap_char((image->data + position), (image->data + position + 2));
	}
	}
	}

# 画线

Bresenham 算法最基本的假设情况是有两个点 $(x_0,y_0),(x_1,y_1)$ ，且 $x_0<x_1,y_0<y_1,0<k<1$ 。则伪代码如下。

	procedure BresenhamLine(in int x0, y0, x1, y1; colorval color) {
	assert: (x0 < x1) and ((y1 – y0) < (x1 – x0))
	declare: int x, y, δy, δy, d, incrE, incrNE;
	δx = x1 – x0; δy = y1 – y0;
	incrE = 2 * δy;
	incrNE = 2 * (δy - δx);
	d = 2 * δy – δx;
	x ← x0; y ← y0;
	printpixel(x, y, color);
	while (x < x1) {
	x++;
	if (d < 0) {
	d += incrE; /* go East */
	} else {
	y++;
	d += incrNE; /* go NorthEast */
	} end if
	printpixel(x, y, color);
	} end while
	} end procedure BresenhamLine

对应的代码实现为

	static void draw2d_line_utils(vec2i p0, vec2i p1, unsigned char color, image_t image) {
	int x, y;
	/* x0<x1 0<k<1 */
	int dx = p1.x - p0.x;
	int dy = p1.y - p0.y;
	int incrE = 2 * dy;
	int incrNE = 2 * (dy - dx);
	int d = 2 * dy - dx;
	for (x = p0.x, y = p0.y; x < p1.x; x++) {
	draw2d_point_utils(x, y, color, image);
	if (d < 0) {
	d += incrE;
	} else {
	y++;
	d += incrNE;
	}
	}
	}

这只是最基本的情况，不足以画出任意斜率的线，所以需要考虑其他的情形。

# $x_0>x_1$

这种情况只需要交换两个点 $(x_0,y_0),(x_1,y_1)$ 的位置，然后走之前的伪代码，最后画点即可。

	static void draw2d_line_utils(vec2i p0, vec2i p1, unsigned char color, image_t image) {
	/* x0>x1 */
	if(x0>x1) swap_point(&p0, &p1);
	.........
	if(x0>x1) draw2d_point_utils(x, y, color, image);
	........
	}

# $k>1$

对于斜率大于 1 的情况，则需要交换起始点和终点的 $xy$ 位置，然后走之前的伪代码，最后画点时重新交换 $xy$ 坐标即可。

	static void draw2d_line_utils(vec2i p0, vec2i p1, unsigned char color, image_t image) {
	/* k>1 */
	if(k>1)
	swap_int(&p0.x, &p0.y);
	swap_int(&p1.x, &p1.y);
	.........
	if(k>1) draw2d_point_utils(y, x, color, image);
	........
	}

# $k<0$

对于斜率小于 0 大于 - 1 的情况，则需要反转起始点和终点的 $y$ 坐标，然后走之前的伪代码，最后画点时重新反转 $y$ 坐标即可。

	static void draw2d_line_utils(vec2i p0, vec2i p1, unsigned char color, image_t image) {
	/* k<0 */
	if(k<0)
	p0.y = -p0.y;
	p1.y = -p1.y;
	.........
	if(k>1) draw2d_point_utils(X, -Y, color, image);
	........
	}

# 综合情形 $x_0>x_1,y_0<y_1,k<-1$

对于斜率小于 - 1 的情况，则包含了上面三种情形，则需要三种情况一次走一遍，最后即可，注意最后在画布上的点坐标为 $(y, -x)$ 。

	static void draw2d_line_utils(vec2i p0, vec2i p1, unsigned char color, image_t image) {
	/* x0>x1 */
	if(x0>x1) swap_point(&p0, &p1);
	/* k<0 */
	if(k<0)
	p0.y = -p0.y;
	p1.y = -p1.y;
	/* k>1 */
	if(k>1)
	swap_int(&p0.x, &p0.y);
	swap_int(&p1.x, &p1.y);
	.........
	if(x0>x1&& k<0 && k>1)
	draw2d_point_utils(Y, -X, color, image);
	........
	}

这里的测试顺序不能更改，先测试 $k>1$ 后测试 $k<0$ 可能会导致不可知的情况。

# $x_0=x_1,y_0>y_1$

对于垂直线，直接画点即可，因为线中的每个是已知可计算的。

# $x_0<x_1,y_0=y_1$

对于水平线，直接画点即可，因为线中的每个是已知可计算的。

# 完整的实现

	static void draw2d_line_utils(vec2i p0, vec2i p1, unsigned char color, image_t image) {

	int x, y;

	/* vertical line */
	if (0 == (p1.x - p0.x)) {
	for (x = p0.x, y = p0.y; y < p1.y; y++) {
	draw2d_point_utils(x, y, color, image);
	}
	/* horizontal line */
	} else if (0 == (p1.y - p0.y)) {
	for (x = p0.x, y = p0.y; x < p1.x; x++) {
	draw2d_point_utils(x, y, color, image);
	}
	} else {
	/* x0>x1 */
	if (p0.x > p1.x) {
	swap_point(&p0, &p1);
	}
	/* k<0 */
	bool mirror = false;
	if ((float)(p1.y - p0.y) / (float)(p1.x - p0.x) < 0) {
	p0.y = -p0.y;
	p1.y = -p1.y;
	mirror = true;
	}

	/* k>1 */
	bool steep = false;
	if ((float)(p1.y - p0.y) / (float)(p1.x - p0.x) > 1) {
	swap_int(&p0.x, &p0.y);
	swap_int(&p1.x, &p1.y);
	steep = true;
	}

	/* x0<x1 0<k<1 */
	int dx = p1.x - p0.x;
	int dy = p1.y - p0.y;
	int incrE = 2 * dy;
	int incrNE = 2 * (dy - dx);
	int d = 2 * dy - dx;

	for (x = p0.x, y = p0.y; x < p1.x; x++) {
	if ((true == steep) && (false == mirror)) {
	draw2d_point_utils(y, x, color, image);
	} else if ((false == steep) && (false == mirror)) {
	draw2d_point_utils(x, y, color, image);
	} else if ((false == steep) && (true == mirror)) {
	draw2d_point_utils(x, -y, color, image);
	} else if ((true == steep) && (true == mirror)) {
	draw2d_point_utils(y, -x, color, image);
	}
	if (d < 0) {
	d += incrE;
	} else {
	y++;
	d += incrNE;
	}
	}
	}

	}

# 参考

CG C

# 前言

# 画点

# 画线

# x0>x1x_0>x_1x0​>x1​

# k>1k>1k>1

# k<0k<0k<0

# 综合情形 x0>x1,y0<y1,k<−1x_0>x_1,y_0<y_1,k<-1x0​>x1​,y0​<y1​,k<−1

# x0=x1,y0>y1x_0=x_1,y_0>y_1x0​=x1​,y0​>y1​

# x0<x1,y0=y1x_0<x_1,y_0=y_1x0​<x1​,y0​=y1​