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