• 在Unity中，实现类似Houdini里的pcopen()函数。

• 通过 KD Tree + 优先队列 实现高效的临近点搜索功能。

声明和定义

1. Point类

Point类存储点的信息，包括但不限于Position、Normal、Up。

class Point
{
    Vector3 position;
}

2. 比较器

由于使用了优先队列用于维护搜索结果的顺序（按与源点位置的距离排序），所以需要定义比较器。

private class PointComparer : IComparer<Point>
{
    private Point target;
    public PointComparer(Point target)
    {
        this.target = target;
    }
    public int Compare(Point p1, Point p2)
    {
        // 根据距离进行排序，距离越小，优先级越高
        double distance1 = Vector3.Distance(p1.position, target.position);
        double distance2 = Vector3.Distance(p2.position, target.position);
        return distance1.CompareTo(distance2);
    }
}

3. Node类

KD树中，节点的定义。

class Node
{
    public Point Point { get; set; }
    public Node Left { get; set; }
    public Node Right { get; set; }
}

4. KD树

class PointCloud
{
    private Node root;
    private PriorityQueue<Point> _result;

    public Point[] result { get { return _result.ToArray(); } }   //对外只读

    public PointCloud(List<Point> points)
    {
        Build(points);
    }

    private void Build(List<Point> points)
    {
        root = BuildTree(points, 0);
    }

    private Node BuildTree(List<Point> points, int depth)
    {
        if (points.Count == 0)
            return null;

        int axis = depth % 3; // 3维KD树, 随着depth的深入，依次循环X/Y/Z

        points.Sort((a, b) =>
        {
            if (axis == 0)
                return a.position.x.CompareTo(b.position.x);
            if (axis == 1)
                return a.position.y.CompareTo(b.position.y);
            return a.position.z.CompareTo(b.position.z);
        });

        int median = points.Count / 2;
        Node node = new Node
        {
            Point = points[median],
            Left = BuildTree(points.GetRange(0, median), depth + 1),
            Right = BuildTree(points.GetRange(median + 1, points.Count - median - 1), depth + 1)
        };

        return node;
    }

    public void Search(Point target, double radius, int maxCount)
    {
        _result = new PriorityQueue<Point>(new PointComparer(target));
        Search(root, target, radius, maxCount, 0);
        return;
    }

    private void Search(Node node, Point target, double radius, int maxCount, int depth)
    {
        if (node == null)
            return;

        double distance = CalculateDistance(node.Point, target);

        if (distance <= radius)
        {
            _result.Enqueue(node.Point);
            if (_result.Count > maxCount)   _result.Dequeue();
        }

        int axis = depth % 3; // 3维KD树
        double axisValue = GetAxisValue(target, axis);

        if (axisValue - radius <= GetAxisValue(node.Point, axis))
            Search(node.Left, target, radius, maxCount, depth + 1);

        if (axisValue + radius >= GetAxisValue(node.Point, axis))
            Search(node.Right, target, radius, maxCount, depth + 1);
    }

    private double CalculateDistance(Point p1, Point p2)
    {
        return Vector3.Distance(p1.position, p2.position);
    }

    private double GetAxisValue(Point point, int axis)
    {
        if (axis == 0)  return point.position.x;
        if (axis == 1)  return point.position.y;
        return point.position.z;
    }
}

使用方法

List<Point> points = new List<Point>();   //在实际使用中，把存放points的List赋值给points就行了。
PointCloud kdTree = new PointCloud(points); //建树
Point target = points[0];
radius = 5.5;
kdTree.Search(target: target, radius: radius, maxCount: points.Count);    //搜索。

Debug.Log("搜索到的Points:");
foreach (Point point in kdTree.result)
    Debug.Log(Vector3.Distance(point.position, target.position) + " " + point.position.ToString());