1/*
2 * KdTree.h
3 * RVO2-3D Library
4 *
5 * Copyright 2008 University of North Carolina at Chapel Hill
6 *
7 * Licensed under the Apache License, Version 2.0 (the "License");
8 * you may not use this file except in compliance with the License.
9 * You may obtain a copy of the License at
10 *
11 * https://www.apache.org/licenses/LICENSE-2.0
12 *
13 * Unless required by applicable law or agreed to in writing, software
14 * distributed under the License is distributed on an "AS IS" BASIS,
15 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
16 * See the License for the specific language governing permissions and
17 * limitations under the License.
18 *
19 * Please send all bug reports to <geom@cs.unc.edu>.
20 *
21 * The authors may be contacted via:
22 *
23 * Jur van den Berg, Stephen J. Guy, Jamie Snape, Ming C. Lin, Dinesh Manocha
24 * Dept. of Computer Science
25 * 201 S. Columbia St.
26 * Frederick P. Brooks, Jr. Computer Science Bldg.
27 * Chapel Hill, N.C. 27599-3175
28 * United States of America
29 *
30 * <https://gamma.cs.unc.edu/RVO2/>
31 */
32/**
33 * \file KdTree.h
34 * \brief Contains the KdTree class.
35 */
36#ifndef RVO3D_KD_TREE_H_
37#define RVO3D_KD_TREE_H_
38
39#include <cstddef>
40#include <vector>
41
42#include "Vector3.h"
43
44namespace RVO3D {
45 class Agent3D;
46 class RVOSimulator3D;
47
48 /**
49 * \brief Defines <i>k</i>d-trees for agents in the simulation.
50 */
51 class KdTree3D {
52 public:
53 /**
54 * \brief Defines an agent <i>k</i>d-tree node.
55 */
56 class AgentTreeNode3D {
57 public:
58 /**
59 * \brief The beginning node number.
60 */
61 size_t begin;
62
63 /**
64 * \brief The ending node number.
65 */
66 size_t end;
67
68 /**
69 * \brief The left node number.
70 */
71 size_t left;
72
73 /**
74 * \brief The right node number.
75 */
76 size_t right;
77
78 /**
79 * \brief The maximum coordinates.
80 */
81 Vector3 maxCoord;
82
83 /**
84 * \brief The minimum coordinates.
85 */
86 Vector3 minCoord;
87 };
88
89 /**
90 * \brief Constructs a <i>k</i>d-tree instance.
91 * \param sim The simulator instance.
92 */
93 explicit KdTree3D(RVOSimulator3D *sim);
94
95 /**
96 * \brief Builds an agent <i>k</i>d-tree.
97 */
98 void buildAgentTree(std::vector<Agent3D *> agents);
99
100 void buildAgentTreeRecursive(size_t begin, size_t end, size_t node);
101
102 /**
103 * \brief Computes the agent neighbors of the specified agent.
104 * \param agent A pointer to the agent for which agent neighbors are to be computed.
105 * \param rangeSq The squared range around the agent.
106 */
107 void computeAgentNeighbors(Agent3D *agent, float rangeSq) const;
108
109 void queryAgentTreeRecursive(Agent3D *agent, float &rangeSq, size_t node) const;
110
111 std::vector<Agent3D *> agents_;
112 std::vector<AgentTreeNode3D> agentTree_;
113 RVOSimulator3D *sim_;
114
115 friend class Agent3D;
116 friend class RVOSimulator3D;
117 };
118}
119
120#endif /* RVO3D_KD_TREE_H_ */
121