1. What is an octree

In recent years, unmanned driving is hot, among which high precision map is the basis for unmanned driving to success. In addition to using tools such as CloudCompare or MeshLib to visualize PointCloud data, companies are also considering using the front-end to visualize PointCloud data. At present, the mainstream open source frameworks for point cloud visualization include Potree and Plas. IO. A point cloud data contains tens of millions of point sets. Both POtree and PLAS use octree to build indexes.

An octree is a data structure in which each internal node has eight child nodes. Octree is usually used to represent the relationship between objects in 3d space, and is usually used to represent three-dimensional images. It can realize the nearest adjacency search in O(LogN) time complexity. A binary tree divides a one-dimensional space into two regions, and an octree divides a three-dimensional space into eight cells, each of which is represented by a node. Octree can save a lot of space when storing 3D data, especially when the spatial distribution is sparse. If there are k points in a three-dimensional space of dimension N, the usable space of the tree is O(kLogN).

Octree contains three types of nodes: Point Node, Empty Node and Region Node. Point Node represents a Point cloud and is a leaf Node. Empty Node indicates that there is no point cloud in this region and its type is leaf Node. A Region Node, as an internal Node in an octree, represents a Region and contains eight child nodes.

2.JS implements octree

2.1 Data Store

To consider how to store the Octree, the Octree constructor is defined to store the root node of the Octree. The constructor contains three parameters, accuracy represents accuracy. Accuracy is considered in spatial comparison, for example, accuracy is 0.005. Precision is added to each direction (for example, x direction [minx-0.005, maxX + 0.005); size indicates the size of the octree; root is the root node.

/** * @param {*} position * @param {*} size Octree space size * @param {*} accuracy, Whether points equal precision * / function Octree (position, size, accuracy) {this. Accuracy = accuracy | | 0; this.size = size; this.root = new Cell(this, position, size, 0); }Copy the code

The type of the root node is Cell. Cell is the data structure of the storage node. Level is the level of the current node. Points stores the coordinates of the point cloud, data stores the additional data of the point cloud; Children is the list of child nodes, either empty or 8 in length.

/** ** Octree node constructor * @param {*} tree Octree container * @param {*} position Start position * @param {*} size size * @param {*} level depth */ function Cell(tree, position, size, level) { this.tree = tree; this.position = position; this.size = size; this.level = level; this.points = []; this.data = []; this.children = []; }Copy the code

If we now want to add a point cloud to the Octree, we need to extend the add function to Octree, which calls the add function of the root node.

Octree.prototype.add = function (p, data) {
    this.root.add(p, data);
}
Copy the code

We then extend the add function on the Cell, first storing the point cloud into the points list and the corresponding data into the data array. If children are not empty, add the point cloud and data to the child node. When the point cloud is first added, such as new Vec3(0.2, 0, 0), since the points contain only one point cloud, the logic in if and else will not be hit. If the second point new Vec3(0.5, 0, 0) is added, then points. Length > 1, the split function will be executed for cutting.

Prototype. Add = function (p, data) {this.points.push(p); this.data.push(data); if (this.children.length > 0) { this.addToChildren(p, data); } else { if (this.points.length > 1 && this.level < Octree.MaxLevel) { this.split(); }}}Copy the code

Next, if we define split function, which is the most important function of octree Node, we know that a Region Node has only 8 child nodes through the definition of octree. If the coordinate of the parent Node is (x, y, z) and the size of the parent Node is size, Half dimensions w2 (x direction), H2 (y direction), d2(Z direction) are obtained in each direction, and the depth of all child nodes is changed to Level + 1. For example, the coordinates of the parent node are [0, 0, 0], size is [4, 4, 4], the coordinates of the first child node are [0, 0, 0], and the coordinates of the second child node are [2, 0, 0],…. And the size of all nodes is halved to [2, 2, 2].

/** * split = function () {var x = this.position.x; var y = this.position.y; var z = this.position.z; Var w2 = this.size. X / 2; var h2 = this.size.y / 2; var d2 = this.size.z / 2; // x, y, z; 2 * 2 * 2 // For example, the parent node coordinates [0, 0, 0], size is [4, 4, 4] // coordinates become [0, 0, 0], size is [2, 2, 2] this.children. Push (new Cell(this.tree, Vec3.create(x, y, z), Vec3.create(w2, h2, d2), this.level + 1)); Vec3. Create (x + w2, y, z), Vec3. Create (w2, h2, d2), this.level + 1)); // This. Children. Push (new Cell(this.tree, Vec3. Create (x, y, z + d2), Vec3. this.level + 1)); // This. Children. Push (new Cell(this.tree, Vec3. Create (x + w2, y, z + d2), Vec3. this.level + 1)); Vec3. Create (x, y + h2, z), Vec3. Create (w2, h2, d2), this.level + 1)); // This. Children. Push (new Cell(this.tree, Vec3. Create (x + w2, y + h2, z), Vec3. this.level + 1)); // This. Children. Push (new Cell(this.tree, Vec3. Create (x, y + h2, z + d2), Vec3. this.level + 1)); Vec3. Create (x + w2, y + h2, z + d2), Vec3. Create (w2, h2, d2), Vec3. this.level + 1)); For (var I = 0; i < this.points.length; i++) { this.addToChildren(this.points[i], this.data[i]); }}Copy the code

After the cutting is complete, all point clouds in points are traversed and the addToChildren function is called to move it to the child node in the corresponding position. The addToChildren function traverses all the child nodes, and determines whether point cloud P is contained in the space of the child node through the contains function. If the condition is met, it will be added to the child node.

/ * * * will point cloud moves to the next straton node storage * @ param} {* * p point cloud coordinates @ param {*} data point cloud data. * / Cell prototype. AddToChildren = function (p, For (var I = 0; i < this.children.length; If (this.children[I].contains(p)) {this.children[I].add(p, data); if (this.children[I].contains(p)) {this.children[I].add(p, data); break; }}}Copy the code

Contains function is defined as follows. The judgment logic of this function is relatively simple, and it is directly compared with the range of three dimensions. It should be noted that accuracy should be added during comparison. If the first point cloud is New Vec3(0.2, 0,0), it satisfies the first child node (coordinate is (0,0,0) and size is (2, 2, 2)). The second point cloud, New Vec3(0.5, 0, 0), still hits the first child node, but the length of points of the first child node is greater than 1 at this time, so the node needs to be recursively split, and the depth level of the child node after splitting becomes 2.

@param {*} p contains = function (p) {// If (param {*} p contains = function (p) {if (param {*} p contains = function (p); If the accuracy is 0.005, Then the X-axis comparison range [MINx-0.005, MaxX + 0.005] return p.x >= this.position.x - this.tree.accuracy && p.y >= this.position.y - this.tree.accuracy && p.z >= this.position.z - this.tree.accuracy && p.x < this.position.x + this.size.x + this.tree.accuracy && p.y < this.position.y + this.size.y + this.tree.accuracy && p.z < this.position.z + this.size.z + this.tree.accuracy; }Copy the code

Combined with add, split, addToChildren and Contains functions, the recursive addition of point cloud data can be realized, and the point cloud data can be added to the correct child nodes.

2.2 Data Retrieval

2.2.1 Find the nearest point

After realizing the storage structure of octree, we consider how to quickly retrieve the stored data. If there is a cloud p1(0.3, 0, 0) and I want to find the nearest point to P1 in the octree, how can I do this? We define the findNearestPoint function on the Octree entity, which is specifically used to retrieve the nearest point. The second parameter of the function contains three options: includeData whether to contain data, maxDist maximum judgment distance, and notSelf excluding itself (if the distance is 0). The findNeareastPoint function of the node Cell entity is called internally to get the nearest point.

* @param {*} p matching point cloud * @param {includeData: whether to includeData, maxDist: maximum distance, notSelf: Does not contain its own} options optional parameters * @ returns * / Octree. Prototype. FindNearestPoint = function (p, options) { options.includeData = options.includeData ? options.includeData : false; options.bestDist = options.maxDist ? options.maxDist : Infinity; options.notSelf = options.notSelf ? options.notSelf : false; / / call the root node findNearestPoint recursive traversal var result = this. Root. FindNearestPoint (p, options); if (result) { if (options.includeData) return result; else return result.point; } else return null; };Copy the code

The following code is the function of obtaining the nearest point defined by the Cell entity. First, judge whether the current node has data (point.length >0). If the current node has data and no child node, then directly judge the distance of the points inside the current node. All data must be traversed.

If there are children, we should look for the nearest distance from the children, because in the storage phase we know that all the data will be stored in the children. The function sorts children in lines 28 to 30. If the center point of node space is closer to the retrieved P point, the children are ranked in the front, and the distance is calculated first to avoid unnecessary calculation.

Next, all children are traversed, and lines 38 to 43 determine whether P is within the space of the node. If not, the node is directly skipped to judge the next node. Otherwise, the findNearestPoint of the child node is recursively called to continue looking for the best. Through the strategy of traversal and recursion, find the best advantage of the final condition.

/** * retrieve the nearest node * @param {*} p retrieve the point * @param {*} options {includeData: whether to contain data, bestDist: maximum distance, notSelf: Does not contain its own} options optional parameters * @ returns * / Cell. The prototype. FindNearestPoint = function (p, options) {var on = null; var nearestData = null; var bestDist = options.bestDist; // The current node contains points and has no children, If (this.points.length > 0 && this.children.length == 0) {// go through all points to find the nearest point for (var i = 0; i < this.points.length; i++) { var dist = this.points[i].distance(p); Dist <= bestDist) {if (dist == 0 && options.notSelf) continue; bestDist = dist; nearest = this.points[i]; nearestData = this.data[i]; Var children = this.children. Map (function(child) {return {child: child, dist: child.squareDistanceToCenter(p) } }) .sort(function(a, b) { return a.dist - b.dist; }) .map(function(c) { return c.child; }); if (children.length > 0) { // eslint-disable-next-line no-redeclare for (var i = 0; i < children.length; i++) { var child = children[i]; If (child.points.length > 0) {// Check whether the target point is in the node space. Don't skip the if (p.x < child. Position. X-ray bestDist | | p.x > child. The position, x + child. Size. X + bestDist | | p.y < child.position.y - bestDist || p.y > child.position.y + child.size.y + bestDist || p.z < child.position.z - bestDist || p.z > child.position.z + child.size.z + bestDist ) { continue; Var childNearest = child.findNearestPoint(p, options); if (! childNearest || ! childNearest.point) { continue; } var childNearestDist = childNearest.point.distance(p); // If (childNearestDist < bestDist) {nearest = childnearestpoint; bestDist = childNearestDist; nearestData = childNearest.data; } } } } return { point: nearest, data: nearestData } };Copy the code

2.2.2 Find nearby points

In addition to finding the nearest point, some scenarios require finding the set of nearby points, such as finding the set of points within the radius r. The findNearByPoints function is defined on the Octree prototype chain. Inside the function, the set of points satisfying the range R will be searched starting from the root node root.

@param {} r * @param {} r * @param {includeData: contains data, maxDist: maximum distance, notSelf: Does not contain its own} options optional parameters * @ returns * / Octree. Prototype. FindNearbyPoints = function (p, r, options) { options = options || { }; var result = { points: [], data: [] }; this.root.findNearbyPoints(p, r, result, options); return result; };Copy the code

The implementation of finding nearby points in a node is similar to findNearestPoint. If when and the node has no child nodes, the list of points under it is directly traversed to find the point set within the range of R with p. Otherwise, in line 28 to 33, the two parameters r and P are combined to determine whether the whole node space range meets the conditions to achieve preliminary screening. If the filter passes, the findNearbyPoints of the child node will be called to achieve recursive search, and all points that meet the conditions will be stored in Result.

@param {*} r search radius * @param {*} result Search result * @param {*} options {includeData: Whether to include data, maxDist: maximum distance, notSelf: Does not contain its own} options optional parameters. * / Octree Cell. The prototype. FindNearbyPoints = function (p, r, the result, options) { if (this.points.length > 0 && this.children.length == 0) { for (var i = 0; i < this.points.length; i++) { var dist = this.points[i].distance(p); if (dist <= r) { if (dist == 0 && options.notSelf) continue; result.points.push(this.points[i]); if (options.includeData) result.data.push(this.data[i]); } } } var children = this.children; if (children.length > 0) { // eslint-disable-next-line no-redeclare for (var i = 0; i < children.length; i++) { var child = children[i]; if (child.points.length > 0) { if (p.x < child.position.x - r || p.x > child.position.x + child.size.x + r || p.y < child.position.y - r || p.y > child.position.y + child.size.y + r || p.z < child.position.z - r || p.z > child.position.z + child.size.z + r ) { continue; } child.findNearbyPoints(p, r, result, options); }}}};Copy the code

3. The advantages and disadvantages

Octree a cube is equally divided into eight parts and can be continuously divided. Although each node is divided into eight sub-cubes, bisector space is easier to understand and faster to learn compared with the diagram of K-D tree.

Octree algorithm is simpler, but the large amount of data under the condition of point cloud, its use more difficult is the smallest size (leaf nodes), granularity, jiaotong university, some nodes may be large amount of data, and the subsequent search efficiency is lower, on the other hand, increase the depth of the octree, need memory is big, each a leaf node need eight pointer, efficiency is low. However, the division basis of equal division makes it less efficient to divide depth by hand when the gravity center of data is offset.

4. The application

In 3d visualization application scenes, Octree can be used to store graph vertices and quickly retrieve them. For example, POtree and PLas. IO all use Octree to realize storage and retrieval functions. In addition, many 3D scenes also use Octree to realize Collision Detection. It can quickly detect whether two THREE-DIMENSIONAL objects collide in the process of movement.

For Collision detection, we can judge from the root node of Octree layer by layer until the intersection between leaf node and target Object is detected, and then the two objects are considered to have collided.

Reference 5.

  1. Octree data structure, iq.opengenus.org/octree/
  2. JS octree, vorg. Making. IO/pex/docs/PE…
  3. Octree collision detection, github.com/Simon089/Sp…
  4. IO/vRMl_engine…

Write in the last

If you have other questions can be directly message, discuss together! Recently I will continue to update Vue source code introduction, front-end algorithm series, interested can continue to pay attention to.