Draw Line By Bresenham

Posted on 2019-03-23

Basic

使用Bresenham算法画一个三角形边框

input为三个2D点；output三条直线

这部分主要实现了三个函数

画点：drawPoint
画线：drawLine
画三角形：drawTriangle

画点

因而三角形边框的绘制是这三个函数从下向上调用实现的。画点的过程和上次作业类似，但是上次没有传递参数进去，这里将位置坐标和颜色RGB作为两个参数传递到画点的函数即可，函数原型如下：

1	void drawPoint(const float location[3], const float color[3], const int & VAO);

画线

Bresenham的算法的实现主要在这个函数中：

先计算出Δx和Δy的绝对值；
判断二者中是否存在0，如果Δx为0，则为一条竖直的线，单独画出；同样，如果Δy为0，则为一条水平的线，单独划出；
其他情况下判断斜率绝对值与1的大小，判断出当每次x移动一像素判断y，还是y移动1像素判断x。

这里引入了directionX和directionY两个变量，用于判断在当前直线的情况下x和y的移动方向。取值为{ -1, 1 }
1. while循环内判断x（或y）是否到达了直线终点位置的横（或纵）坐标，由于不知道起点和终点位置的相对大小，因而比较的时候采用当前位置的点坐标和终点位置的点坐标与起点坐标的距离进行比较：
  1
  while (abs(x_i - startPoint[0]) < abs(endPoint[0] - startPoint[0]))...
2. 带入bresenham的递推式判断当前理想位置距离上下（左右）两个整像素的距离差：
  $$
  \begin{align*}
  &p_i = 2\Delta y - \Delta x\
  &if \space p_i <=0 \
  &\qquad p_{i+1}=p_i+2\Delta y \
  &if \space p_i >0 \
  &\qquad p_{i+1}=p_i+2\Delta y - 2\Delta x
  \end{align*}
  $$
  对于坡角大于45°的情形，公式如下：
  $$
  \begin{align*}
  &p_i = 2\Delta y - \Delta x\
  &if \space p_i <=0 \
  &\qquad p_{i+1}=p_i+2\Delta x \
  &if \space p_i >0 \
  &\qquad p_{i+1}=p_i+2\Delta x - 2\Delta y
  \end{align*}
  $$
3. 在大于0的情况下，y变化（或x变化），否则保持不变
4. 每轮循环，x（或y）向directionX（或directionY）方向移动一个像素。

另外，由于这个步骤的x, y坐标均为整数，在调用drawPoint函数传入参数时需要化为float类型：

1 2	float loc[3] = { (float)x_i / windowWidth * 2, (float)y_i / windowHeight * 2 , 0 }; drawPoint(loc, color, VAO);

画三角形

这一步根据三角形三点的整数坐标，传入drawLine函数即可：

1
2
3

drawLine(point1, point2, VAO);
drawLine(point1, point3, VAO);
drawLine(point2, point3, VAO);

结果

使用Bresenham算法画一个圆

画圆的思路是先画出八分之一弧，判断每次x右移一个像素后，y不移动的情况下像素点对应的坐标位置落在圆内还是圆外，如果在圆外就选择(x+1, y-1)的像素填充，否则选择(x+1, y).

while循环条件如下：

1	while (x_i < center[0] + sqrt(2) * radius/2 + 1 )

判断函数如下：
$$
d = (x-centerX)^2+(y-centerY)^2-R^2
$$
如果d > 0，在圆外，否则在圆内。

推出d的递推公式：
$$
\begin{equation}
\begin{aligned}
if \quad d_i <= 0\
d_{i+1} &= (x+1-centerX)^2+(y-centerY)^2-R^2\
&=1+2x-2centerX+d_i\
if \quad d_i > 0\
d_{i+1} &= (x+1-centerX)^2+(y-1-centerY)^2-R^2\
&=1+2x-2centerX+1-2y+2centerY+d_i\
&=2+2(x-y)-2(centerX-centerY)+d_i
\end{aligned}
\end{equation}
$$
对于八分之一弧上的每一点，需要进行8次对称，使得圆完整：

int deltaX = x - center[0];
int deltaY = y - center[1];
int xArray[8] = {center[0] + deltaX, center[0] + deltaX, center[0] - deltaX, center[0] - deltaX, center[0] + deltaY, center[0] + deltaY, center[0] - deltaY, center[0] - deltaY };
int yArray[8] = {center[1] + deltaY, center[1] - deltaY, center[1] + deltaY, center[1] - deltaY, center[1] + deltaX, center[1] - deltaX, center[1] + deltaX, center[1] - deltaX };
for (int i = 0; i < 8; i++) {
    float loc[3] = {(float)xArray[i] / windowWidth * 2, (float)yArray[i] / windowHeight * 2, 0};
    drawPoint(loc, color, VAO);
}

同样，这里在调用drawPoint的时候，也需要将int类型转为float类型。

结果

在GUI在添加菜单栏，可以选择是三角形边框还是圆，以及能调整圆的大小

参考imGui的example，menu的写法如下：

void Homework3::imGuiMenuSetting() {
	if (ImGui::BeginMenu("Homework3"))
	{
		if (ImGui::BeginMenu("Basic"))
		{
			ImGui::MenuItem("Triangle", NULL, &triangleFrame);
			ImGui::MenuItem("Circle", NULL, &circleFrame);
			ImGui::EndMenu();
		}
		if (ImGui::BeginMenu("Bonus"))
		{
			ImGui::MenuItem("Fill Triangle", NULL, &filledTri);
			ImGui::EndMenu();
		}
		ImGui::EndMenu();
	}	
}

其中每个MenuItem的最后一个参数和之前使用checkbox的情况相似，为一个bool变量，判断该图形是否显示。因此，在显示图形绘制窗口的时候也需要相应的控制：

void Homework3::displayController() {
	if (triangleFrame) {
		drawTriangle();
	}
	if (circleFrame) {
		drawCircle();
	}
	if (filledTri) {
		fillTriangle();
	}
}

另外，为了在显示某些元素的时候提供可修改变量的窗口，还需要一个函数在Gui里面控制参数输入：

void Homework3::imGuiSetting() {
	if (circleFrame) {
		ImGui::InputInt("X", &center[0]);
		ImGui::InputInt("Y", &center[1]);
		ImGui::InputInt("Radius", &radius);
	}
	if (triangleFrame) {
		ImGui::InputInt2("Point1", point1);
		ImGui::InputInt2("Point2", point2);
		ImGui::InputInt2("Point3", point3);
		initBound();
	}
}

主函数中调用过程如下：

注意这里Begin最后一个参数需要设置为ImGuiWindowFlags_MenuBar

ImGui::Begin("Options", NULL, ImGuiWindowFlags_MenuBar);
if (ImGui::BeginMenuBar())
{
    homework3.imGuiMenuSetting();
    ImGui::EndMenuBar();
}
homework3.imGuiSetting();
ImGui::End();

while (!glfwWindowShouldClose(window)) {
    // 检查触发事件、更新窗口，回调
    glfwPollEvents();
    displayGUI(window, homework2, homework3);
    // 作业对象的显示控制
    homework3.displayController();
    glfwMakeContextCurrent(window);
    // 交换缓冲、绘制、显示
    glfwSwapBuffers(window);
}

Bonus

使用三角形光栅转换算法，用和背景不同的颜色，填充三角形

填充三角形的主要思路是先使用包围盒将三角形所在的矩形区域判定出来，之后对其中的像素点依次进行遍历，对每一个点使用同向法判断点是否在三角形内部。

包围盒的确定方法

上边框为三角形三个顶点纵坐标的最大值，下边框为最小值；左边框为横坐标的最小值，右边框为最小值。

如果三角形三个顶点位置发生变化，则需要重新确定包围盒。

同向法判断点在三角形内部

原理

沿着三角形的边按顺时针方向走，判断该点是否在每条边的右边（这可以通过叉乘判断），如果该点在每条边的右边，则在三角形内，否则在三角形外。

计算方法

通过判断三次的叉乘是否同向，即两两点乘的结果是否均大于0即可判断点是否在三角形内。
$$
\vec a = \vec {PA}\times\vec {PB}\
\vec b = \vec {PA}\times\vec {PC}\
\vec c = \vec {PC}\times\vec {PB}\
$$
由于三角形三边的向量第三位均为0，因而叉积的结果只有第三维有可能非0。因此，也仅有第三维会参与到点积的计算，直接套用叉积公式将结果作为一维变量保存。

主要代码如下：

bool Homework3::isInTri(const int & x, const int & y) {
	float P2[2] = { x - point2[0], y - point2[1] }; // 2 -> P
	float P3[2] = { x - point3[0], y - point3[1] }; // 3 -> P
	float P1[2] = { x - point1[0], y - point1[1] }; // 1 -> P
	float cross2 = P1[0] * P2[1] - P1[1] * P2[0];
	float cross3 = P2[0] * P3[1] - P2[1] * P3[0];
	float cross1 = P3[0] * P1[1] - P3[1] * P1[0];
 	if (cross2 * cross3 > 0 && cross1 * cross3 > 0 && cross1 * cross2 > 0) {
		return true;
	}
	return false;
}

之后对于包围盒内的每个坐标进行判断，如果在三角形内部，则将坐标转化为[-1.0, 1.0]范围内，并调用drawPoint画点。

结果

源代码：https://github.com/Yuandi-Sherry/CG_Homework/blob/master/README.md