众里寻他千百度，蓦然回首，那人却在灯火阑珊处
前情提要
在某些情况下，我们在场景中创建了数百万个物体，这些物体没有直接的网格或碰撞体（例如，通过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范围，以此来加快最近点的玄策
