图形学自问自答2——点在三角形内部判定

《巫师3:狂猎》角色ciri

如何判定一个点是否在三角形内部

光栅化的关键步骤是计算某个三角形覆盖到了哪些像素，需要依次判断每个像素的中心是否在三角形内部，那么，给定一个点和一个三角形（由三个点定义），如何判定该点是否在三角形中呢？

• 首先，三角形能够定义一个平面，该点必须在三角形所确定的平面上，才可能在三角形内部
• 在三角形内部的点，具有如下的特性：
  三角形和点
  如上图，当三角形顶点沿逆时针得到三个向量 AB，BC和CA，都有，点P在向量的左边（考虑向量的方向，可以设想从A往B走，P在左边）。
  点在向量点左边还是右边，怎么确定呢？使用向量点叉乘可以处理这个问题，考虑向量BC和点P，连接B点和P点得到向量BP，那么
  得到垂直平面ABC向外的一个向量，同理有 和 其中 ，和是同方向的向量，也就是两两点积结果为1。
  到此可以得到判断点是否在三角形中的代码如下

using UnityEngine;
using System.Collections;

public class Utils
{
    public static bool isPointInPlane(Vector3 point, Vector3 a, Vector3 b, Vector3 c)
    {
        Vector3 ab = Vector3.Normalize(b - a);
        Vector3 bc = Vector3.Normalize(c - b);
        Vector3 ca = Vector3.Normalize(a - c);
        Vector3 ap = Vector3.Normalize(point - a);
        Vector3 bp = Vector3.Normalize(point - b);
        Vector3 cp = Vector3.Normalize(point - c);

        float dotValue1 = Mathf.Abs(Vector3.Dot(ab, ap));
        float dotValue2 = Mathf.Abs(Vector3.Dot(bc, bp));
        float dotValue3 = Mathf.Abs(Vector3.Dot(ca, cp));

        // 是否在三角形边的延长线上
        if (dotValue1 == 1 || dotValue2 == 1 || dotValue3 == 1)
        {
            return true;
        }
        else
        {
            // 与任意两条边叉积得到的法线是否同向或反向
            Vector3 n1 = Vector3.Normalize(Vector3.Cross(ab, ap));
            Vector3 n2 = Vector3.Normalize(Vector3.Cross(bc, ap));

            float cos = Mathf.Abs(Vector3.Dot(n1, n2));

            return cos == 1;
        }
        
    }

    public static bool isPointInTrangle(Vector3 point, Vector3 a, Vector3 b, Vector3 c)
    {
        if (!isPointInPlane(point, a, b, c))
        {
            return false;
        }

        Vector3 ab = b - a;
        Vector3 bc = c - b;
        Vector3 ca = a - c;
        Vector3 ap = point - a;
        Vector3 bp = point - b;
        Vector3 cp = point - c;

        Vector3 n1 = Vector3.Normalize(Vector3.Cross(ab, ap));
        Vector3 n2 = Vector3.Normalize(Vector3.Cross(bc, bp));
        Vector3 n3 = Vector3.Normalize(Vector3.Cross(ca, cp));

        float dotValue1 = Vector3.Dot(n1, n2);
        float dotValue2 = Vector3.Dot(n2, n3);
        float dotValue3 = Vector3.Dot(n3, n1);

        return (dotValue1 == dotValue2) && (dotValue2 == dotValue3) && (dotValue3 == 1);
    }
}

添加如下的测试代码：

using System.Collections;
using System.Collections.Generic;
using UnityEngine;

public class HelloUnity : MonoBehaviour
{
    // Start is called before the first frame update
    void Start()
    {
        Application.targetFrameRate = 60;

        Vector3 a = Vector3.zero;
        Vector3 b = Vector3.right;
        Vector3 c = Vector3.up;

        // Vector3 p = Vector3.forward; // false, false
        // Vector3 p = Vector3.left;    // true, false
        // Vector3 p = new Vector3(0.1f, 0.1f, 0);  // true, true
        // Vector3 p = new Vector3(1f, 1f, 0); // true, false
        Vector3 p = new Vector3(0.2f, 0.2f, 0.2f);  // false, false

        bool inPlane = Utils.isPointInPlane(p, a, b, c);
        bool inTrangle = Utils.isPointInTrangle(p, a, b, c);

        Debug.Log("inPlane:" + inPlane + ", inTrangle:" + inTrangle);
    }
}

• 点在三角形点边上，是否算在三角形内部？在图形学中这是一个典型的 corner case，此时这个点是否在三角形内部，由你自己决定。光栅化时一个像素的中心坐标正好在三角形的边上，三角形是否覆盖这个像素，由引擎自己决定。