JS实现八叉树octree(js二叉树的遍历算法)
1.什么是八叉树
最近几年无人驾驶闹的比较火热，其中高精地图是无人驾驶走向成功必须具备的基础。通过雷达采集或者经过算法实现的三维重建都会生成PointCloud点云数据，除了使用CloudCompare或者MeshLib等工具可视化点云数据，各个公司也在考虑通过前端来可视化点云数据，目前比较主流的点云可视化开源框架有potree和plas.io，一份点云数据包含几千万上亿点集，一方面需要考虑切割，另一方面需要考虑建立索引。potree以及plas都采用八叉树来建立索引。
八叉树是一种数据结构，其中每个内部节点有8个子节点。八叉树常用表示3维空间中对象之间的关系，通常用于表示三维图像。可实现在O(LogN)时间复杂度下的最近邻接点搜索。二叉树将一维空间分割成两个区域，八叉树将三维空间分割成8个格子，每个格子用一个节点表示。八叉树在存储三维数据时能节省大量空间，特别是空间分布较稀疏的情况下。如果在一个维度为N的三维空间下有k个点，则该树的使用空间为O(kLogN)。
八叉树包含Point Node、Empty Node、Region Node共3种节点，Point Node代表一个点云，类型为叶子结点；Empty Node表示该区域没有点云存在，其类型为叶子节点；Region Node作为八叉树的内部节点，表示一个区域，并且一定包含8个子节点。
2.JS实现八叉树
2.1 数据存储
考虑如何存储八叉树，首先定义了Octree构造函数存储八叉树的根节点，构造函数包含三个参数，accuracy表示精度，在空间比较时会考虑精度，例如精度为0.005，在做比较时每个方向都会附加上精度(例如x方向[minX - 0.005, maxX + 0.005)；size表示八叉树的空间大小；root为根节点。
/**
* 八叉树构造函数
* @param {*} position 初始位置，立方体的(left, bottom, far)位置作为起始坐标
* @param {*} size 八叉树空间大小
* @param {*} accuracy 精度，判断点是否相等的精度
*/
function Octree(position, size, accuracy) {
this.accuracy = accuracy || 0;
this.size = size;
this.root = new Cell(this, position, size, 0);
}复制代码根节点类型为Cell，Cell为存储节点的数据结构，level为当前节点所在层次，根节点层次为0；points存储点云坐标，data存储点云附加的数据；children为子节点列表，要么为空，要么长度为8。
/**
* 八叉树节点构造函数
* @param {*} tree octree容器
* @param {*} position 起始位置
* @param {*} size 大小
* @param {*} level 深度
*/
function Cell(tree, position, size, level) {
this.tree = tree;
this.position = position;
this.size = size;
this.level = level;
this.points = [];
this.data = [];
this.children = [];
}复制代码假如现在我们要增加一个点云到八叉树，需要对Octree扩展add函数，该函数会调用根节点root的add函数。
Octree.prototype.add = function (p, data) {
this.root.add(p, data);
}复制代码我们接着在Cell上扩展add函数，首先将点云存储到points列表，并将对应的数据存储到data数组中。如果children不为空，则将点云和数据添加到子节点中，当第一次添加点云，例如new Vec3(0.2, 0, 0)，由于points只包含一个点云，if和else中的逻辑都不会命中，假如再添加第二个点new Vec3(0.5, 0, 0)，此时points.length > 1，将执行split函数进行切割。
/**
* 添加点云
* @param {*} p 点云
* @param {*} data
*/
Cell.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();
}
}
}复制代码接下来看如果定义split函数，该函数为八叉树节点最重要的函数，通过八叉树的定义我们知道一个Region Node有且仅有8个子节点，假如父节点的坐标为(x, y, z)，父节点尺寸为size，每个方向求得半尺寸w2（x方向)、h2(y方向)、d2(z方向)，切割的所有子节点深度变为level + 1。例如父节点坐标为[0, 0, 0]，size为[4, 4, 4]，第一个子节点坐标为[0, 0, 0], 第二个子节点坐标为[2, 0, 0]，....，并且所有节点尺寸减半变为[2, 2, 2]。
/**
* 将当前节点拆分为八个子节点
*/
Cell.prototype.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
// 例如父节点坐标[0, 0, 0]、size为[4, 4, 4]
// 坐标变为[0, 0, 0], size为[2, 2, 2]
this.children.push(new Cell(this.tree, Vec3.create(x, y, z), Vec3.create(w2, h2, d2), this.level + 1));
// 坐标变为[2, 0, 0]
this.children.push(new Cell(this.tree, Vec3.create(x + w2, y, z), Vec3.create(w2, h2, d2), this.level + 1));
// 坐标变为[0, 0, 2]
this.children.push(new Cell(this.tree, Vec3.create(x, y, z + d2), Vec3.create(w2, h2, d2), this.level + 1));
// 坐标变为[2, 0, 2]
this.children.push(new Cell(this.tree, Vec3.create(x + w2, y, z + d2), Vec3.create(w2, h2, d2), this.level + 1));
// 坐标变为[0, 2, 0]
this.children.push(new Cell(this.tree, Vec3.create(x, y + h2, z), Vec3.create(w2, h2, d2), this.level + 1));
// 坐标变为[2, 2, 0]
this.children.push(new Cell(this.tree, Vec3.create(x + w2, y + h2, z), Vec3.create(w2, h2, d2), this.level + 1));
// 坐标变为[0, 2, 2]
this.children.push(new Cell(this.tree, Vec3.create(x, y + h2, z + d2), Vec3.create(w2, h2, d2), this.level + 1));
// 坐标变为[2, 2, 2]
this.children.push(new Cell(this.tree, Vec3.create(x + w2, y + h2, z + d2), Vec3.create(w2, h2, d2), this.level + 1));
// 将保存的点移动到下一层子节点存储
for (var i = 0; i < this.points.length; i++) {
this.addToChildren(this.points[i], this.data[i]);
}
}复制代码切割完成后，遍历points中所有点云，并调用addToChildren函数将其移动到对应位置的子节点中。addToChildren函数遍历所有子节点，并通过contains函数判断点云p是否包含在子节点空间范围内，满足条件则将其添加到子节点中。
/**
* 将点云移动到下一层子节点存储
* @param {*} p 点云坐标
* @param {*} data 点云数据
*/
Cell.prototype.addToChildren = function (p, data) {
// 遍历8个子节点
for (var i = 0; i < this.children.length; i++) {
// 如果点云坐标包含在节点空间内，则添加到对应子节点
if (this.children[i].contains(p)) {
this.children[i].add(p, data);
break;
}
}
}复制代码contains函数定义如下，该函数的判断逻辑比较简单，直接和三个维度的范围进行比较，需要注意的是，在进行比较时需要附加上精度accuracy。假如第一个点云为new Vec3(0.2, 0, 0)，满足第一个子节点(坐标为(0,0,0), 尺寸为(2, 2, 2))。再添加第二个点云new Vec3(0.5, 0, 0)，还是命中第一个子节点，但此时第一个子节点的points长度大于1，需要递归对该节点进行拆分，其拆分后的子节点深度level变为2.
/**
* 判断点云是否包含在当前节点空间内
* @param {*} p 点云坐标
* @returns
*/
Cell.prototype.contains = function (p) {
// 比较时附加上精度buffer，假如精度为0.005，则x轴比较范围[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;
}复制代码结合add、split、addToChildren、contains函数，可以实现点云数据的递归添加，并将点云数据添加到正确的子节点中。
2.2 数据检索
2.2.1 找最近的点
实现了八叉树的存储结构，接下来考虑如何对存储的数据实现快速检索。假如现在有点云p1(0.3, 0, 0)，想找出octree中离p1最近的点，该如何实现？我们在Octree实体上定义findNearestPoint函数，专门用于检索最近的点，函数第二个参数包含三个可选项，includeData是否包含数据、maxDist最大判断距离、notSelf排除自身(距离为0的情况)。函数内部将调用节点Cell实体的findNeareastPoint函数来获取最近的点。
/**
* 检索最近的点云，options包含部分附加条件
* @param {*} p 匹配的点云
* @param {includeData: 是否包含数据, maxDist: 最大距离, notSelf: 不包含自身 } options 可选参数
* @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;
// 调用根节点的findNearestPoint进行递归遍历
var result = this.root.findNearestPoint(p, options);
if (result) {
if (options.includeData) return result;
else return result.point;
}
else return null;
};复制代码以下代码为Cell实体定义的获取最近点函数，先判断当前节点有没有数据(points.length>0)，如果当且节点有数据并且无子节点，那么直接判断当前节点内部的点距离即可，需要注意的是，内部的点有可能最后一个才是最优值，所有必须遍历完所有的数据。
如果有子节点，则应该从子节点中找最近距离，因为在存储阶段我们知道所有的数据都会存储到子节点中。函数在28行到30行对children做了排序，如果节点空间中心点离被检索的p点越近越排在前面，优先算距离，避免不必要的计算。
接下来遍历所有children，38行到43行判断p是否在节点空间范围内，不在则直接跳过，判断下一个节点。否则，递归调用子节点的findNearestPoint继续查找最优点。通过遍历和递归的策略，找出最终符合条件的最优点。
/**
* 检索离点最近的节点
* @param {*} p 被检索的点
* @param {*} options {includeData: 是否包含数据, bestDist: 最大距离, notSelf: 不包含自身 } options 可选参数
* @returns
*/
Cell.prototype.findNearestPoint = function (p, options) {
var nearest = null;
var nearestData = null;
var bestDist = options.bestDist;
// 当前节点包含点并且没有子节点，则直接判断当且节点下的point和目标point距离是否满足条件
if (this.points.length > 0 && this.children.length == 0) {
// 遍历所有的points找到最近的点
for (var i = 0; i < this.points.length; i++) {
var dist = this.points[i].distance(p);
if (dist <= bestDist) {
// 如果dist为0，为自身，需排除
if (dist == 0 && options.notSelf)
continue;
bestDist = dist;
nearest = this.points[i];
nearestData = this.data[i];
}
}
}
// 每个children按中心点到目标point距离从近到远排序，优先考虑近的
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) {
// 判断目标点在不在节点空间范围内，不在则直接跳过
if (p.x < child.position.x - bestDist || p.x > child.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 = childNearest.point;
bestDist = childNearestDist;
nearestData = childNearest.data;
}
}
}
}
return {
point: nearest,
data: nearestData
}
};复制代码2.2.2 找附近的点
除了找最近的点，某些场景需要找出附近的点集合，例如按半径r查找范围内的点集合。在Octree原型链上定义findNearByPoints函数，函数内部会从根节点root开始查找满足范围r内的点集合。
/**
* 查找范围内的点集合
* @param {} p 被检索的点
* @param {} r 检索半径
* @param { includeData: 是否包含数据, maxDist: 最大距离, notSelf: 不包含自身 } options 可选参数
* @returns
*/
Octree.prototype.findNearbyPoints = function (p, r, options) {
options = options || { };
var result = { points: [], data: [] };
this.root.findNearbyPoints(p, r, result, options);
return result;
};复制代码节点中查找附近的点的实现和findNearestPoint类似，如果当且节点无子节点，则直接遍历其下的points列表，找出和p距离满足r范围内的点集合。否则，第28到33行结合r、p两个参数判断整个节点空间范围是否满足条件，实现初步筛选。筛选通过的再调用子节点的findNearbyPoints实现递归查找，最终满足条件的point都会存储到result。
/**
* 查找节点范围内的点集合
* @param {*} p 被检索的点
* @param {*} r 检索半径
* @param {*} result 检索结果
* @param {*} options { includeData: 是否包含数据, maxDist: 最大距离, notSelf: 不包含自身 } options 可选参数
*/
Octree.Cell.prototype.findNearbyPoints = function (p, r, 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);
}
}
}
};复制代码3.优缺点
octree一个立方体等分为八份，并可以持续的分下去，虽然每个节点都要分为八个子立方体，但等分空间，相对于k-d树的图示，容易理解，上手比较快。
八叉树的算法实现比较简单，但大数据量点云的情况下，其使用比较困难的是最小粒度(叶节点)的确认，粒度交大时，有的节点数据量可能比较大，后续查找效率比较低，反之，八叉树的深度增加，需要的内存就比较大，每个非叶子节点需要八个指针，效率也比较低。而等分的划分依据，使得在数据重心有偏移的情况下，手划分深度限制，其效率也不太高。
4.应用
在三维可视化应用场景，可以使用octree存储图形顶点，并且可快速对其进行检索，如potree、plas.io都是使用octree实现存储和检索功能，另外，很多三维场景也借助octree来实现Collision detection，能快速检测出两个三维Object在移动过程中是否发生碰撞。
对于Collision detection, 可以通过octree的root节点一层层往下判断，直到检测到有叶子结点和目标物体有相交，则认为两Object发生了碰撞。
作者：前端下饭菜
链接：https://juejin.cn/post/7040736028109307935