【八叉树】从上千万个物体中【**瞬间**】就近选取坐标

众里寻他千百度，蓦然回首，那人却在灯火阑珊处

前情提要

在某些情况下，我们在场景中创建了数百万个物体，这些物体没有直接的网格或碰撞体（例如，通过GPU绘制的物体），因此无法通过常规的射线检测与碰撞体进行交互。我们仅掌握这些物体的坐标或顶点位置。在这种情况下，我们该如何通过鼠标来“选中”这些物体呢？

常规方式

1.创建鼠标到世界的射线

 Ray ray = _camera.ScreenPointToRay(Input.mousePosition);
 Vector3 rayDirection = ray.direction;
 Vector3 rayOrigin = ray.origin;
 Vector3 rayEnd = rayOrigin + rayDirection * maxPickDistance;

2.遍历所有坐标点

①借用点积夹角计算筛选出与与射线方向一致

foreach (Vector3 point in points)
        {
            //点与射线夹角
            float dotAngle = Vector3.Dot(rayDirection, (point - rayOrigin).normalized);
            if (dotAngle > 0.99f)
            {
                float camDist = Vector3.Distance(rayOrigin, point);
                //点到射线距离
                var pointRayDist = SqDistPointSegment(rayOrigin, rayEnd, point);
                var normCamDist = (camDist / maxPickDistance) * pointRayDist * pointRayDist;

                if (normCamDist < nearestPointRayDist)
                {
                    if (pointRayDist > maxPickDistance) continue;
                    nearestPointRayDist = normCamDist;
                    nearestPoint = point;
                    isFindNearestPoint = true;
                }
            }
        }

②通过点积投影得到点到射线的距离

    public static float SqDistPointSegment(Vector3 start, Vector3 end, Vector3 point)
    {
        var ab = end - start;
        var ac = point - start;
        var bc = point - end;
        float e = Vector3.Dot(ac, ab);
        float f = Vector3.Dot(ab, ab);
        if (e >= f) return Vector3.Dot(bc, bc);
        return Vector3.Dot(ac, ac) - e * e / f;
    }

如此便可求得离射线最近坐标位置。

那么问题来了：当有上千万个点左边信息的时候，如此遍历一遍势必消耗大量的时间。下面我们将借助八叉树来优化该方案。

八叉树优化后的方案

1.创建八叉树

... 
Octree = new Octree(boundingBox, 500);//场景的范围Bounds和Octree迭代限制
//将所有点传入Octree初始化八叉树结构
        foreach (var point in pointCloudData)
        {
            Octree.Insert(point);
        }
... 

2.获取被射线穿过的Octree节点

    public List<Octree> GetNodesIntersectedByRay(Ray ray)
    {
        List<Octree> intersectedNodes = new List<Octree>();

        if (bounds.IntersectRay(ray))
        {
            intersectedNodes.Add(this);

            if (children != null)
            {
                foreach (var child in children)
                {
                    intersectedNodes.AddRange(child.GetNodesIntersectedByRay(ray));
                }
            }
        }

        return intersectedNodes;
    }

3.获取射线穿过Octree节点中的坐标数据

        var nodes = this._octree.GetNodesIntersectedByRay(ray);
        var points = new List<Vector3>();
         foreach (var node in nodes)
         {
             points.AddRange(node.points);
         }

4.通过常规方法遍历经过筛选后的Octree节点中的坐标数据

...
 foreach (Vector3 point in points)
        {
            float dotAngle = Vector3.Dot(rayDirection, (point - rayOrigin).normalized);
            if (dotAngle > 0.99f)
            {
...

经过八叉树优化后几乎可以做到实时选取

注意：可以调整八叉树的迭代分割限制条件来寻找更好的子节点Bounds范围，以此来加快最近点的玄策