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

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

前情提要

在某些情况下，我们在场景中创建了数百万个物体，这些物体没有直接的网格或碰撞体（例如，通过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范围，以此来加快最近点的玄策