[Octree] picks coordinates from tens of millions of objects [**instantaneously**] in close proximity.

I've searched high and low for him, but when I look back, he's in the dead lights.

synopsis (of previous events)

In some cases, we create millions of objects in the scene that do not have a direct mesh or collision body (e.g., objects drawn via the GPU), and thus cannot interact with the collision body via regular ray detection. We only have the coordinates or vertex positions of these objects. In this case, how do we "select" these objects with the mouse?

conventional method

1. Create a mouse-to-world ray

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

2. Iterate over all coordinate points

(1) Borrow the dot product angle calculation to filter out the same direction as with the rays

foreach (Vector3 point in points)
        {
            //Angle between point and ray
            float dotAngle = (rayDirection, (point - rayOrigin).normalized);
            if (dotAngle > 0.99f)
            {
                float camDist = (rayOrigin, point);
                //Point to ray distance
                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;
                }
            }
        }

② Get the distance from the point to the ray by dot product projection

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

In this way, the position of the nearest coordinate to the ray can be found.

So here's the problem: when there are tens of millions of points of left information, traversing it all over again like this is bound to consume a lot of time.In the following we will optimize the scheme with the help of octree.

Optimized scheme for octree

1. Create an octree

...
Octree = new Octree(boundingBox, 500);//scene's range Bounds and Octree iteration limits
// Pass all points into Octree to initialize the octree structure
        foreach (var point in pointCloudData)
        {
            (point);
        }
...

2. Get the Octree node that is crossed by the ray.

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

        if ((ray))
        {
            (this);

            if (children != null)
            {
                foreach (var child in children)
                {
                    ((ray));
                }
            }
        }

        return intersectedNodes;
    }

3. Get the coordinate data of the ray passing through the Octree node.

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

4. Iterate through the coordinate data in the filtered Octree nodes by conventional methods

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

After octree optimization it is possible to pick almost in real time

Note: The iterative splitting constraints of the octree can be adjusted to find a better range of child nodes Bounds as a way of speeding up the nearest-point Genzai