网站视觉设计方案,wordpress ip 访问,做商城网站那个好,网站层次索引模板八叉树碰撞检测是一种在三维空间中高效处理物体碰撞检测的算法#xff0c;其原理可以类比为一个管理三维空间物体的智能系统。这个示例包含两个部分#xff1a;八叉树部分用于宏观检测#xff0c;AABB用于微观检测。AABB可以更换为均值或节点检测来提高检测精度。
八叉树的…八叉树碰撞检测是一种在三维空间中高效处理物体碰撞检测的算法其原理可以类比为一个管理三维空间物体的智能系统。这个示例包含两个部分八叉树部分用于宏观检测AABB用于微观检测。AABB可以更换为均值或节点检测来提高检测精度。
八叉树的构建
确定根节点范围 首先要为整个碰撞检测系统确定一个初始范围这就像是为所有参与碰撞检测的物体划定一个 “活动区域”。这个范围是一个能够完全容纳所有待检测物体的三维立方体空间它构成了八叉树的根节点。递归分割空间 为了更高效地管理和查找物体八叉树会对这个初始的大立方体空间进行递归分割。具体做法是沿着三个坐标轴的中点将大立方体分割成八个小立方体每个小立方体对应根节点的一个子节点。之后系统会检查每个子节点所包含的物体数量 若某个子节点中的物体数量小于预设的阈值就认为该区域内的物体分布较为稀疏无需再进行分割这些物体就存储在该节点中。 若物体数量超过阈值说明该区域物体较为密集需要进一步细分。于是会将这个节点的空间继续分割成八个更小的子空间并对每个子空间重复上述检查过程直到满足停止条件。 碰撞检测过程插入物体 在将物体的轴对齐包围盒AABB插入八叉树时系统会从根节点开始判断物体的 AABB 与当前节点的空间是否相交 如果不相交表明该物体不在当前节点所管理的空间范围内无需在此节点存储该物体。 如果相交则将物体插入当前节点。若当前节点已经被分割成子节点系统会进一步判断物体的 AABB 与哪个子节点的空间相交并将物体插入对应的子节点中。查询碰撞 当需要检测某个物体用其 AABB 表示是否与其他物体发生碰撞时系统会从八叉树的根节点开始查询 若该物体的 AABB 与当前节点的空间不相交说明该节点及其子节点中的物体都不可能与该物体发生碰撞无需继续检查该节点及其子树。 若相交则检查当前节点中存储的物体的 AABB 与该物体的 AABB 是否相交。 若当前节点有子节点系统会递归地对每个子节点进行相同的查询操作直到遍历完所有可能发生碰撞的节点。 八叉树碰撞检测的优缺点 优点 高效性通过对三维空间进行递归分割八叉树将碰撞检测的范围缩小到可能发生碰撞的区域避免了对所有物体进行两两比较从而显著减少了不必要的计算提高了碰撞检测的效率。在处理大量物体的场景中这种优势更为明显。 适应性八叉树能够根据物体在空间中的实际分布情况自适应地进行空间划分对于物体分布不均匀的场景也能有效地组织和管理物体。 缺点 构建和维护成本较高构建八叉树需要对空间进行递归分割并将物体分配到相应的节点中这需要一定的时间和空间开销。特别是在物体频繁移动或新增、删除物体的场景中需要不断更新八叉树的结构增加了维护成本。 存在精度问题使用 AABB 来近似表示物体可能会导致一定的精度损失尤其是对于形状复杂的物体AABB 可能无法精确地描述其外形从而产生误判。
C代码
#include iostream
#include vector
#include memory// 定义三维向量结构体
struct Vec3 {float x, y, z;Vec3(float x 0, float y 0, float z 0) : x(x), y(y), z(z) {}
};// 定义 AABB 结构体
struct AABB {Vec3 min;Vec3 max;AABB(const Vec3 min, const Vec3 max) : min(min), max(max) {}// 判断两个 AABB 是否相交bool intersects(const AABB other) const {return (min.x other.max.x max.x other.min.x) (min.y other.max.y max.y other.min.y) (min.z other.max.z max.z other.min.z);}
};// 定义八叉树节点类
class OctreeNode {
public:AABB bounds;std::vectorAABB objects;std::vectorstd::unique_ptrOctreeNode children;OctreeNode(const AABB bounds) : bounds(bounds) {}// 插入 AABB 到节点中void insert(const AABB object) {if (children.empty()) {if (objects.size() 8) {objects.push_back(object);} else {split();insert(object);}} else {for (auto child : children) {if (child-bounds.intersects(object)) {child-insert(object);}}}}// 分割节点void split() {Vec3 center((bounds.min.x bounds.max.x) / 2, (bounds.min.y bounds.max.y) / 2, (bounds.min.z bounds.max.z) / 2);children.resize(8);children[0] std::make_uniqueOctreeNode(AABB(bounds.min, center));children[1] std::make_uniqueOctreeNode(AABB(Vec3(center.x, bounds.min.y, bounds.min.z), Vec3(bounds.max.x, center.y, center.z)));children[2] std::make_uniqueOctreeNode(AABB(Vec3(bounds.min.x, center.y, bounds.min.z), Vec3(center.x, bounds.max.y, center.z)));children[3] std::make_uniqueOctreeNode(AABB(Vec3(center.x, center.y, bounds.min.z), Vec3(bounds.max.x, bounds.max.y, center.z)));children[4] std::make_uniqueOctreeNode(AABB(Vec3(bounds.min.x, bounds.min.y, center.z), Vec3(center.x, center.y, bounds.max.z)));children[5] std::make_uniqueOctreeNode(AABB(Vec3(center.x, bounds.min.y, center.z), Vec3(bounds.max.x, center.y, bounds.max.z)));children[6] std::make_uniqueOctreeNode(AABB(Vec3(bounds.min.x, center.y, center.z), Vec3(center.x, bounds.max.y, bounds.max.z)));children[7] std::make_uniqueOctreeNode(AABB(center, bounds.max));for (const auto object : objects) {for (auto child : children) {if (child-bounds.intersects(object)) {child-insert(object);}}}objects.clear();}// 检测与指定 AABB 的碰撞void query(const AABB object, std::vectorAABB result) const {if (bounds.intersects(object)) {for (const auto obj : objects) {if (obj.intersects(object)) {result.push_back(obj);}}for (const auto child : children) {child-query(object, result);}}}
};// 定义八叉树类
class Octree {
public:std::unique_ptrOctreeNode root;Octree(const AABB bounds) : root(std::make_uniqueOctreeNode(bounds)) {}// 插入 AABB 到八叉树中void insert(const AABB object) {root-insert(object);}// 检测与指定 AABB 的碰撞std::vectorAABB query(const AABB object) const {std::vectorAABB result;root-query(object, result);return result;}
};// 示例使用
int main() {// 定义八叉树的边界AABB octreeBounds(Vec3(0, 0, 0), Vec3(100, 100, 100));Octree octree(octreeBounds);// 插入一些 AABBoctree.insert(AABB(Vec3(10, 10, 10), Vec3(20, 20, 20)));octree.insert(AABB(Vec3(30, 30, 30), Vec3(40, 40, 40)));// 定义一个查询的 AABBAABB queryAABB(Vec3(15, 15, 15), Vec3(25, 25, 25));// 进行碰撞检测std::vectorAABB collisions octree.query(queryAABB);// 输出碰撞结果std::cout Collisions found: collisions.size() std::endl;for (const auto collision : collisions) {std::cout Collision: min( collision.min.x , collision.min.y , collision.min.z ), max( collision.max.x , collision.max.y , collision.max.z ) std::endl;}return 0;
}
