0评论

在Unity向量空间内绘制几何:利用平面几何知识画像素直线

文章来自CSDN博客 2018-11-07 33浏览

想免费获取内部独家PPT资料库?观看行业大牛直播?点击加入腾讯游戏学院游戏开发行业精英群711501594

像素类型的游戏一直都有不少的玩家,这类型的游戏中,经常会用到各种直线,本篇文章要分享的就是在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