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

《巫师3:狂猎》角色ciri

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

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

  • 首先,三角形能够定义一个平面,该点必须在三角形所确定的平面上,才可能在三角形内部
  • 在三角形内部的点,具有如下的特性:
    三角形和点

    如上图,当三角形顶点沿逆时针得到三个向量 AB,BC和CA,都有,点P在向量的左边(考虑向量的方向,可以设想从A往B走,P在左边)。
    点在向量点左边还是右边,怎么确定呢?使用向量点叉乘可以处理这个问题,考虑向量BC和点P,连接B点和P点得到向量BP,那么
    BC \times BP = n_1 得到垂直平面ABC向外的一个向量n_1,同理有CA\times CP = n_2AB \times AP = n_3 其中 n_1n_2n_3是同方向的向量,也就是两两点积结果为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,此时这个点是否在三角形内部,由你自己决定。光栅化时一个像素的中心坐标正好在三角形的边上,三角形是否覆盖这个像素,由引擎自己决定。
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容