在Unity向量空间内绘制几何:利用平面几何知识画像素直线
发表于2018-11-07
像素类型的游戏一直都有不少的玩家,这类型的游戏中,经常会用到各种直线,本篇文章要分享的就是在Unity向量空间内利用平面几何知识画像素直线的实现方法。
问题:假如有一个像素平面,既是一个充满四方格子平面,给出任意两个格子的坐标,画出两个格子间的直线。
接下来,尝试在平面几何的角度下思考并解决这个问题。
已知两个点A,B。
不论这两个点的相对位置,角度关系如何,一定可以以它们为基础画一个直角三角形。
这个三角形的高,既是BC,就是点A与点B在y轴的间距。三角形的长为两点x轴间距。(Latex太麻烦了 -__-,以下直接用文字代替数学符号。)
AC=绝对值(A.x-B.x); BC=绝对值(A.y-B.y); //(公式1)
根据勾股定理,已知两边长,可得出斜边长度。
AB=开方(AC^2+BC^2); //(公式2)
接下来将斜边当成一个点的集合。给一个间距,把这些点都找出来。
知道了起点的坐标,根据公式:
假设有点D,既是线段AB上的任意一点:
D=(A到D的距离)*Vector3.Normalize(B.position-A.position)+A.position; //(公式3)
Vector3.Normalize(B.position-A.position)得出的是从A走向B的方向,知道了方向和距离,每段的间距,即可依次求出斜线上每个点的坐标。
/*
这里在简单介绍下Normalize的算法,因为接下来的代码中会出现:
有vector a [1,2,3]
ax=1 ay=2 az=3
a 的 magnitude (长度): |a|=sqrt((ax*ax)+(ay*ay)+(az*az));
设Normalize后的ax,ay,az为 anx,any,anz,那么
anx=ax/ |a|
any=ay/ |a|
anz=az/ |a|
*/
当得到了AB上这些点的坐标后,我们假定这些点一定覆盖了两个坐标直线距离中的所有像素块之上, 那么只要进一步把这些点的坐标化为像素块的坐标,既找到了所有像素块的坐标。这种坐标转化是一种舍入操作,只要知道了像素块坐标的单位,然后将我们找到的点根据此单位进行舍入即可,例如假设有点D1=1.1,1.9; D2=1.6,1.0; D3=2.1,2.5; 而像素块的单位间隔为1,则舍入后变为,D1=1,1,; D2=1,1; D3=2,2。最后的步骤,删除重复的点,既得出了此两点间直线所经过的所有像素块的点,也既是模拟两点间的像素直线。
思路总结:
已知两点。
1.求两点间距。
2.找出一堆两点直线上的点。
3.将这堆点化为像素世界坐标。
得出直线。
了解了核心步骤,接下来即可写代码:
//设Point3D为一个存有x,y,z坐标信息的结构体 public static List<Point3D> PathExplore(Point3D start_point, Point3D end_point){ //公式1 int height = Mathf.Abs (start_point.y - end_point.y); int length = Mathf.Abs (start_point.x - end_point.x); //公式2 float hypotenuse_length = Mathf.Sqrt(Mathf.Pow (height, 2) + Mathf.Pow (length, 2)); //最终结果,得出的像素块的地址将会保存至此 List<Point3D> tempList = new List<Point3D> (); //记录前一个被转化为像素块坐标,用于删除同在一个像素坐标内的点。 Point3D previous=new Point3D(); bool init = false; //此num数量决定了斜边上等距模拟点的数量,合理的数值应正好大于斜边上所经过的像素块数量。 int num = Mathf.CeilToInt(hypotenuse_length) * 2; //得出公式3中的B.position-A.position之后的数值。 Point3D temp_minus; temp_minus.x = end_point.x - start_point.x; temp_minus.y = end_point.y - start_point.y; temp_minus.z = start_point.z; //由于是一个2D平面,假设Z值都相同。 //temp_minus_normal_x,y,z既是公式3中的Vector3.Normalize(B.position-A.position)得出的值,这里是手动的进行了规格化。 float length_temp_minus = Mathf.Sqrt (temp_minus.x * temp_minus.x + temp_minus.y * temp_minus.y + temp_minus.z * temp_minus.z); float temp_minus_normal_x=temp_minus.x / length_temp_minus; float temp_minus_normal_y=temp_minus.y / length_temp_minus; float temp_minus_normal_z=temp_minus.z / length_temp_minus; //依次算出每个点的坐标 for (int i = 0; i <= num; i++) { float temp2_x; float temp2_y; float temp2_z; //公式3 temp2_x = (hypotenuse_length/num*i)*temp_minus_normal_x; temp2_y = (hypotenuse_length/num*i)*temp_minus_normal_y; temp2_z = (hypotenuse_length/num*i)*temp_minus_normal_z; temp2_x += start_point.x; temp2_y += start_point.y; temp2_z += start_point.z; //假设像素块的间距单位为1,这里将点根据像素坐标进行舍入操作 Point3D temp3; temp3.x = Mathf.FloorToInt (temp2_x); temp3.y = Mathf.FloorToInt (temp2_y); temp3.z = Mathf.FloorToInt (temp2_z); //如果此点与前一点同在一个像素块坐标,忽略并计算下一个点 if (init&&(temp3.x == previous.x && temp3.y == previous.y && temp3.z == previous.z)) { continue; } //将此像素块坐标放入要返回的数组中 tempList.Add (temp3); previous.x=temp3.x; previous.y=temp3.y; previous.z=temp3.z; init = true; } //此数组内的Point3D坐标即为从startPoint至endPoint所有像素格子的坐标 return tempList; }
效果:
总结:
算法的优势:真实,精确的模拟两点间的直线 。当num为一个较大的数时(相对斜线所经过的像素块),不会出现遗漏的情况(会很精确的爬楼梯)。虽然这种精确并不是计算机在像素级别画线所需要的。
算法的劣势:1,对于在像素领域画线这种重量级操作来说此算法性能太差,计算步骤过于复杂,有些步骤过于消耗性能。只适合效果展示用。2,由于算法思路与传统计算机图形学算法的思路不同,在有些情况下,视觉上一些细节处与传统像素图像会有出路。
附:用C#实现传统的Bresenham’s直线算法
改编于 Ericw.ca
地址:ericw.ca/notes/bresenhams-line-algorithm-in-csharp.html
/// <summary> /// Bresenham's line algorithm /// </summary> /// <returns>The points on line.</returns> /// <param name="start_point">Start point.</param> /// <param name="end_point">End point.</param> public static List<Point3D> GetPointsOnLine(Point3D start_point, Point3D end_point) { int x0 = start_point.x; int y0 = start_point.y; int x1 = end_point.x; int y1 = end_point.y; List<Point3D> temp = new List<Point3D> (); bool steep = Math.Abs(y1 - y0) > Math.Abs(x1 - x0); if (steep) { int t; t = x0; // swap x0 and y0 x0 = y0; y0 = t; t = x1; // swap x1 and y1 x1 = y1; y1 = t; } if (x0 > x1) { int t; t = x0; // swap x0 and x1 x0 = x1; x1 = t; t = y0; // swap y0 and y1 y0 = y1; y1 = t; } int dx = x1 - x0; int dy = Math.Abs(y1 - y0); int error = dx / 2; int ystep = (y0 < y1) ? 1 : -1; int y = y0; for (int x = x0; x <= x1; x++) { // yield return new Point((steep ? y : x), (steep ? x : y)); Point3D temp2; temp2.x = steep ? y : x; temp2.y = steep ? x : y; temp2.z = 0; temp.Add (temp2); error = error - dy; if (error < 0) { y += ystep; error += dx; } } // yield break; return temp; }
来自:https://blog.csdn.net/liu_if_else/article/details/59533204