Unity动态构建mesh绘制多边形算法流程分析和实践
阅读原文时间:2023年07月13日阅读:1

先说一下,写这篇博文的动机,原文的博主代码写的十分潇洒,以至于代码说明和注释都没有,最近恰逢看到,所以以此博文来分析其中的算法和流程

参考博文:https://blog.csdn.net/linxinfa/article/details/78816362

github网址:https://github.com/linxinfa/Unity-ArbitraryPolygonMesh

先复习一下线代

向量的混合积的数学意义是:两个向量叉乘的结果是一个新向量,这个新向量垂直于原向量组成的平面,并且新向量的长度等于原向量合成的平行四边形的面积

向量的混合积是三个向量组成的平行六面体的体积。叉乘可以看成高是单位长度的平行六面体的体积,也就是其平行四边形的面积

  • 在场景中创建多个几何体作为mesh多边形的顶点
  • 在父物体上,创建几个子物体,顺时针摆放这些物体

  • 先通过叉乘计算多边形的面积,叉乘严格按照Inspector面板的摆放顺序进行计算,保证是同一顺序时针,通过判断计算面积结果正负性(Unity采用右手坐标系,但在此处还是加上判断),提前设置顶点(V[n])的顺序

    // 计算多边形的面积,按照同一顺序进行叉乘
    private float Area()
    {
        // n = 5
        int n = m_points.Count;
        float A = 0.0f;
        Vector2 pval = Vector2.zero;
        Vector2 qval = Vector2.zero;
        for (int p = 0; p < n; p++)
        {
            pval = m_points[p];
            qval = m_points[(p + 1) % n];
            A += pval.x * qval.y - qval.x * pval.y;
        }
        return (A * 0.5f);
    }
  • 按照面积的正负性,改变新创建的顶点数组顺序

        if (Area() > 0)
        {
            // 0 1 2 3 4
            for (int v = 0; v < n; ++v)
                V[v] = v;
        }
        else
        {
            // 将顶点顺序逆过来
            // 4 3 2 1 0
            for (int v = 0; v < n; ++v)
                V[v] = (n - 1) - v;
        }
  • 此处改了一点参考博文的代码,因为n边形的一个顶点出发只能引出(n-2)条对角线,每次枚举三个连续顶点,判断是否能组成三角形(Snip),因为我们提前设置了每个顶点所能发射的最多对角线数量,所以此处无需考虑三个连续顶点重复采用,如果count为0了,可以理解有nv次机会判断是否形成三角形,如果没更新count(也就是没走if里面)则直接返回

        int nv = n;
        int count = nv;
        int u, w;
        // n边形的一个顶点出发只能引出(n-2)条对角线
        for (int v = nv - 1; nv >= 3;)
        {
            // 形成不了三角形时会走这个return
            if ((count--) <= 0)
                return indices.ToArray();
        // 连续三个顶点 不超过nv
        u = v;
        v = u + 1;
        w = u + 2;
    
        u %= nv;
        v %= nv;
        w %= nv;
    
        // u v w连续三个顶点能组成三角形,且保证顺序是合理的
        if (Snip(u, v, w, nv, V))
        {
            int a, b, c;
            a = V[u];
            b = V[v];
            c = V[w];
    
            // 将顶点按照顺序放入list中
            indices.Add(a);
            indices.Add(b);
            indices.Add(c);
    
            // 做了代码修改,原文写法比较麻烦,将V数组中的值从后往前挪一位
            for (int s = v; s + 1 &lt; nv; ++s)
                V[s] = V[s + 1];
    
            nv--;
            // 原博文是 count = 2 * nv 但其实没必要
            count = nv;
        }
    }</code></pre></li>
  • 判断是否能形成三角形

    private bool Snip(int u, int v, int w, int n, int[] V)
    {
        Vector2 A = m_points[V[u]];
        Vector2 B = m_points[V[v]];
        Vector2 C = m_points[V[w]];
    // 面积如果小于Mathf.Epsilon(接近0的最小正浮点数),就为不能切分成三角形
    // AB向量叉乘AC向量结果为ABC三顶点形成封闭图形的面积的两倍,判断是否能形成三角形
    if (Mathf.Epsilon &gt; ((B.x - A.x) * (C.y - A.y)) - ((B.y - A.y) * (C.x - A.x)))
        return false;
    for (int p = 0; p &lt; n; ++p)
    {
        // 直到p为没选到的边
        if ((p == u) || (p == v) || (p == w))
            continue;
    
        Vector2 P = m_points[V[p]];
        // 防止线边交叉
        if (InsideTriangle(A, B, C, P))
            return false;
    }
    return true;
    }
  • 判断线边交叉情况,一般情况下返回值都是false(cCROSSap一般与aCROSSbp和bCROSScp正负性相反,因为选点的时候故意为之的),除非线边交叉,发生叉乘的正负性发生了改变

  • 如下图这种情况,如果注释了InsideTriangle()函数,网格会生成不出来,因为出现了线边交叉情况,导致可能绘制顶点的顺序有顺时针有逆时针,从而导致只有绘制面到了背面或者直接就不出来效果

  • 叉乘结果

\[ BC×BP > 0\\
CA×CP > 0\\
AB×AP > 0
\]

  • 正常情况

\[ BC×BP > 0\\
CA×CP > 0\\
AB×AP < 0
\]

    private bool InsideTriangle(Vector2 A, Vector2 B, Vector2 C, Vector2 P)
    {
        float ax, ay, bx, by, cx, cy, apx, apy, bpx, bpy, cpx, cpy;
        float cCROSSap, bCROSScp, aCROSSbp;

        ax = C.x - B.x; ay = C.y - B.y;
        bx = A.x - C.x; by = A.y - C.y;
        cx = B.x - A.x; cy = B.y - A.y;
        apx = P.x - A.x; apy = P.y - A.y;
        bpx = P.x - B.x; bpy = P.y - B.y;
        cpx = P.x - C.x; cpy = P.y - C.y;

        // BC向量与BP向量叉乘
        aCROSSbp = ax * bpy - ay * bpx;
        // CA向量与CP向量叉乘
        bCROSScp = bx * cpy - by * cpx;
        // AB向量与AP向量叉乘
        cCROSSap = cx * apy - cy * apx;

        // 保证叉乘的顺序都是一致的
        // 此处算的结果一般都为false
        // 画个图就可以得知
        if (((aCROSSbp >= 0.0f) && (bCROSScp >= 0.0f) && (cCROSSap >= 0.0f)))
        {
            Debug.Log($"A.x = {A.x}, A.y = {A.y}");
            Debug.Log($"B.x = {B.x}, B.y = {B.y}");
            Debug.Log($"C.x = {C.x}, C.y = {C.y}");
            Debug.Log($"P.x = {P.x}, P.y = {P.y}");
        }
        // Debug.Log(((aCROSSbp >= 0.0f) && (bCROSScp >= 0.0f) && (cCROSSap >= 0.0f)));
        return ((aCROSSbp >= 0.0f) && (bCROSScp >= 0.0f) && (cCROSSap >= 0.0f));
    }

手机扫一扫

移动阅读更方便

阿里云服务器
腾讯云服务器
七牛云服务器