八叉树的范围和射线检测

接typescript八叉树的简单实现
说一下typescript八叉树的范围和射线检测实现。

学习八叉树，并用自己的方式实现一下，理论联系实际

范围检测

应用场景

在3d项目中，针对场景节点较多的情况，需要找到距离目标节点，比如玩家最近的一些其他玩家、怪物、NPC、风景等，把他们显示出来。
或者需要进行碰撞检测的时候，只对附近的物体进行检测。
使用八叉树都可以很大地减少运算量，提升性能。

大体逻辑

如果父节点和给的范围相交，则遍历递归查看子节点哪些相交，直至找到叶子节点，哪些相交。
因为八叉树将场景划分成了八份，给的范围很可能只和其中1份或者2份相交，比如场景有8个堆叠的建筑，玩家很可能只在某个建筑里或者在两个建筑之间的通道里。
确定了和哪个大的空间相交，则必定和其中的一个或者几个小空间相交。
我们的目的是找到具体节点，不是这些虚拟的空间。所以要逐层查找，直至找到最底层的叶子空间，里面包含了1个或者几个具体节点。再对这些具体节点进行是否包含在范围内的判断。
如果父节点的空间直接被包含在了给的范围，则不需要再对子空间进行判断了，直接拿到所有具体节点即可。
然后将所有这些包含在范围内的具体节点打包返回。

核心代码

  //递归函数，每次对子节点进行遍历判断是否相交
  private getNearCubeData(sourcePosition: Vec3, parentOcTree: OcTreeNode, out: CubeData[]) {
      for (let i = 0; i < parentOcTree.children.length; i++) {
        const ocTreeNode = parentOcTree.children[i];
        const { x, y, z } = sourcePosition;
        const { x: ocX, y: ocY, z: ocZ } = ocTreeNode.centerPosition;
        const halfLen = ocTreeNode.sideLength / 2;
        geometry.Sphere.set(this.toolSphere, x, y, z, APPConfig.nearSphereRadius);
        geometry.AABB.set(this.toolAABB, ocX, ocY, ocZ, halfLen, halfLen, halfLen);
        //这里因为是用的cocos引擎，所以直接用了他的几何库。判断球和AABB是否相交
        if (geometry.intersect.sphereAABB(this.toolSphere, this.toolAABB)) {
          if (ocTreeNode.items.length > 0) {
          //将叶子节点的具体元素放入包中
      		out.push(...ocTreeNode.items);
    	  } else if (ocTreeNode.sideLength > APPConfig.ocTreeMinSideLength) {
      		//如果不是叶子节点，且相交的情况，就进行递归查找
      		this.getNearCubeData(sourcePosition, ocTreeNode, out);
    	  }
        }
      }
  }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

射线检测

应用场景

当场景里的元素很多，需要用鼠标选中一个的时候，如果对所有元素进行遍历，那运算量是很大的。八叉树就是把问题分成了8份，尽早筛除无用运算。就像机械加工，先进行粗加工，把大块的无用材料，尽快去掉。
也会对元素之间进行距离检测，比如找到最近的敌人自动锁定之类的。

大体逻辑

射线检测和范围检测几乎一致，只是相交判断由范围变成了一条射线。
射线检测也会获得多个结果。看自己需要是不是获取最近的。
如果是鼠标选中，一般会从摄像机位置发送一条经过近裁剪面点击位置的射线。然后就逐节点检测是否相交，直至找到哪些和射线相交的元素。
如果是距离判断，则360度发送射线，比如每1度发送一条射线，依次找到最近的元素，始终保留最近的那个。则走完后就获得了最近的元素。这个肯定要比对所有元素进行一次排序快非常多。

核心代码

//核心递归代码，检测八叉树节点是否与射线相交
  private getRayHitOcTreeNode(ray: geometry.Ray, ocTreeNode: OcTreeNode) {
    if (this.isRayHitOcTreeNode(ray, ocTreeNode)) {
      if (ocTreeNode.items.length) {
      //如果是叶子节点，则判断是否最近元素
        for (let i = 0; i < ocTreeNode.items.length; i++) {
          const item = ocTreeNode.items[i];
          if (this.isRayHitCubeData(ray, item) && item.curCube) {
            if (!this.rayHitNearestItem) {
              this.rayHitNearestItem = item;
            } else {
              if (Vec3.squaredDistance(item.position, ray.o) < Vec3.squaredDistance(this.rayHitNearestItem.position, ray.o)) {
                this.rayHitNearestItem = item;
              }
            }
          }
        }
      } else {
      //如果不是叶子节点且相交，则递归查找子节点的相交情况
        for (let i = 0; i < ocTreeNode.children.length; i++) {
          this.getRayHitOcTreeNode(ray, ocTreeNode.children[i]);
        }
      }
    }
  }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25