C++中的碰撞检测算法优化：利用BVH/Octree等空间数据结构加速

好的，以下是一篇关于C++中使用BVH/Octree等空间数据结构加速碰撞检测算法的技术文章，以讲座形式呈现：

碰撞检测算法优化：利用BVH/Octree等空间数据结构加速

大家好，今天我们要探讨的是游戏开发、物理模拟等领域中一个非常核心的问题：碰撞检测。碰撞检测的效率直接影响着程序的性能，尤其是在场景复杂、物体数量庞大的情况下。暴力检测（即两两比较所有物体）的时间复杂度是O(n^2)，这在实际应用中往往是不可接受的。因此，我们需要使用更高效的算法来加速碰撞检测过程。本文将重点介绍如何利用BVH（Bounding Volume Hierarchy）和Octree（八叉树）等空间数据结构来优化碰撞检测。

1. 碰撞检测的基本概念

首先，我们需要明确碰撞检测的目的是什么。简单来说，就是判断场景中的两个或多个物体是否发生了重叠或接触。在实际应用中，碰撞检测通常分为两个阶段：

• Broad-Phase Collision Detection（粗略阶段碰撞检测）: 快速排除大部分不可能发生碰撞的物体对，缩小需要进行精确检测的范围。
• Narrow-Phase Collision Detection（精细阶段碰撞检测）: 对Broad-Phase筛选出的可能碰撞的物体对进行精确的碰撞检测，确定是否真的发生了碰撞，并计算碰撞信息（如碰撞点、碰撞法线等）。

本文主要关注Broad-Phase的优化，因为这是提高整体碰撞检测效率的关键。

2. 暴力检测的局限性

暴力检测，顾名思义，就是将场景中所有物体两两进行碰撞检测。其代码实现简单，但效率极低。

struct Object {
  // 物体数据，如位置、大小等
  float x, y, z;
  float radius; // 使用球体作为简单碰撞体
};

bool isColliding(const Object& a, const Object& b) {
  // 简单的球体碰撞检测
  float distance = sqrt(pow(a.x - b.x, 2) + pow(a.y - b.y, 2) + pow(a.z - b.z, 2));
  return distance < (a.radius + b.radius);
}

void bruteForceCollisionDetection(std::vector<Object>& objects) {
  int n = objects.size();
  for (int i = 0; i < n; ++i) {
    for (int j = i + 1; j < n; ++j) {
      if (isColliding(objects[i], objects[j])) {
        // 处理碰撞
        std::cout << "Collision detected between object " << i << " and object " << j << std::endl;
      }
    }
  }
}

时间复杂度为O(n^2)，当n很大时，性能会急剧下降。

3. 空间数据结构：加速碰撞检测的利器

为了避免暴力检测，我们需要使用空间数据结构来对场景中的物体进行组织，从而能够快速排除大量不可能发生碰撞的物体对。常用的空间数据结构包括：

• BVH (Bounding Volume Hierarchy): 一种树状结构，每个节点包含一个包围盒（Bounding Volume），用于包含其子节点或叶子节点中的物体。
• Octree (八叉树): 一种树状结构，将空间递归地分割成八个子立方体。
• KD-Tree: 一种树状结构，将空间沿不同的轴进行分割。
• Grid: 将空间划分成均匀的网格。

本文将重点介绍BVH和Octree。

4. BVH (Bounding Volume Hierarchy)

BVH是一种自底向上构建的树状结构。每个节点包含一个包围盒，包围盒可以是AABB（Axis-Aligned Bounding Box）、球体、OBB（Oriented Bounding Box）等。AABB最简单，计算量最小，是常用的选择。

4.1 BVH的构建

BVH的构建过程通常采用递归方式：

1. 根节点： 创建一个包含所有物体的包围盒作为根节点。
2. 分割： 将根节点中的物体分割成两个或多个子集。常用的分割方法有：
   • 轴对齐分割： 沿某个坐标轴分割，例如选择包含物体最多的轴，将物体分割成两部分。
   • 表面积启发式分割 (SAH): 一种更高级的分割方法，它会尝试不同的分割方案，并选择表面积最小的方案，以减少后续的碰撞检测次数。
3. 递归： 对每个子集递归执行步骤2，直到子集中包含的物体数量小于某个阈值（例如1）。
4. 叶子节点： 当子集中包含的物体数量小于阈值时，将该子集作为叶子节点。叶子节点包含实际的物体。

struct AABB {
  float minX, minY, minZ;
  float maxX, maxY, maxZ;

  bool intersects(const AABB& other) const {
      return (maxX >= other.minX && minX <= other.maxX) &&
             (maxY >= other.minY && minY <= other.maxY) &&
             (maxZ >= other.minZ && minZ <= other.maxZ);
  }
};

struct BVHNode {
  AABB bbox;
  BVHNode* left;
  BVHNode* right;
  std::vector<Object*> objects; // 叶子节点才包含物体
};

AABB calculateAABB(const std::vector<Object*>& objects) {
    AABB bbox;
    if (objects.empty()) return bbox;

    bbox.minX = objects[0]->x - objects[0]->radius;
    bbox.minY = objects[0]->y - objects[0]->radius;
    bbox.minZ = objects[0]->z - objects[0]->radius;
    bbox.maxX = objects[0]->x + objects[0]->radius;
    bbox.maxY = objects[0]->y + objects[0]->radius;
    bbox.maxZ = objects[0]->z + objects[0]->radius;

    for (size_t i = 1; i < objects.size(); ++i) {
        bbox.minX = std::min(bbox.minX, objects[i]->x - objects[i]->radius);
        bbox.minY = std::min(bbox.minY, objects[i]->y - objects[i]->radius);
        bbox.minZ = std::min(bbox.minZ, objects[i]->z - objects[i]->radius);
        bbox.maxX = std::max(bbox.maxX, objects[i]->x + objects[i]->radius);
        bbox.maxY = std::max(bbox.maxY, objects[i]->y + objects[i]->radius);
        bbox.maxZ = std::max(bbox.maxZ, objects[i]->z + objects[i]->radius);
    }

    return bbox;
}

BVHNode* buildBVH(std::vector<Object*> objects) {
  BVHNode* node = new BVHNode();
  node->bbox = calculateAABB(objects);
  node->left = nullptr;
  node->right = nullptr;
  node->objects = objects; // initially store all objects in the node

  if (objects.size() <= 1) {
    return node; // Leaf node
  }

  // Simple split strategy: Split along the longest axis
  float xLength = node->bbox.maxX - node->bbox.minX;
  float yLength = node->bbox.maxY - node->bbox.minY;
  float zLength = node->bbox.maxZ - node->bbox.minZ;

  enum { X_AXIS, Y_AXIS, Z_AXIS };
  int axis = X_AXIS;
  if (yLength > xLength) axis = Y_AXIS;
  if (zLength > yLength) axis = Z_AXIS;

  std::vector<Object*> leftObjects;
  std::vector<Object*> rightObjects;
  float splitPosition;

  if (axis == X_AXIS) {
      splitPosition = (node->bbox.minX + node->bbox.maxX) / 2.0f;
      for (Object* obj : objects) {
          if (obj->x < splitPosition) {
              leftObjects.push_back(obj);
          } else {
              rightObjects.push_back(obj);
          }
      }
  } else if (axis == Y_AXIS) {
      splitPosition = (node->bbox.minY + node->bbox.maxY) / 2.0f;
      for (Object* obj : objects) {
          if (obj->y < splitPosition) {
              leftObjects.push_back(obj);
          } else {
              rightObjects.push_back(obj);
          }
      }
  } else { // Z_AXIS
      splitPosition = (node->bbox.minZ + node->bbox.maxZ) / 2.0f;
      for (Object* obj : objects) {
          if (obj->z < splitPosition) {
              leftObjects.push_back(obj);
          } else {
              rightObjects.push_back(obj);
          }
      }
  }

  if (leftObjects.empty() || rightObjects.empty()) {
    // Avoid empty splits
    return node;
  }

  node->objects.clear(); // No longer needed in internal nodes
  node->left = buildBVH(leftObjects);
  node->right = buildBVH(rightObjects);

  return node;
}

4.2 BVH的遍历和碰撞检测

构建好BVH后，就可以利用它进行碰撞检测了。碰撞检测的过程也是递归的：

1. 根节点： 从BVH的根节点开始。
2. 相交测试： 将要检测的物体（或另一个BVH节点）的包围盒与当前节点的包围盒进行相交测试。
   • 如果两个包围盒不相交，则说明当前节点及其所有子节点中的物体都不可能与该物体发生碰撞，直接返回。
   • 如果两个包围盒相交，则继续执行步骤3。
3. 递归： 如果当前节点是叶子节点，则将该节点中的物体与要检测的物体进行精细阶段的碰撞检测。否则，递归地对当前节点的左右子节点执行步骤2。

void traverseBVH(BVHNode* node, Object& object, std::vector<std::pair<Object*, Object*>>& collisionPairs) {
  if (!node->bbox.intersects({object.x - object.radius, object.y - object.radius, object.z - object.radius,
                              object.x + object.radius, object.y + object.radius, object.z + object.radius})) {
    return; // No intersection, prune this branch
  }

  if (node->left == nullptr && node->right == nullptr) {
    // Leaf node, check for collisions with objects in this node
    for (Object* obj : node->objects) {
      if (isColliding(object, *obj)) {
        collisionPairs.push_back({&object, obj});
      }
    }
  } else {
    // Internal node, traverse children
    if (node->left != nullptr) {
      traverseBVH(node->left, object, collisionPairs);
    }
    if (node->right != nullptr) {
      traverseBVH(node->right, object, collisionPairs);
    }
  }
}

void bvhCollisionDetection(BVHNode* root, std::vector<Object>& objects, std::vector<std::pair<Object*, Object*>>& collisionPairs) {
    collisionPairs.clear();
    for (Object& obj : objects) {
        traverseBVH(root, obj, collisionPairs);
    }
}

4.3 BVH的优点和缺点

• 优点： 适用于动态场景，可以高效地排除大量不可能发生碰撞的物体对。
• 缺点： 构建过程相对复杂，如果物体分布不均匀，可能导致BVH的性能下降。

5. Octree (八叉树)

Octree是一种树状结构，将空间递归地分割成八个子立方体。每个节点代表一个立方体区域，根节点代表整个场景空间。

5.1 Octree的构建

Octree的构建过程与BVH类似，也是采用递归方式：

1. 根节点： 创建一个包含整个场景空间的立方体作为根节点。
2. 分割： 如果当前节点包含的物体数量超过某个阈值，则将该节点分割成八个子立方体。
3. 递归： 对每个子立方体递归执行步骤2，直到子立方体包含的物体数量小于阈值，或者达到最大递归深度。
4. 叶子节点： 当满足终止条件时，将该子立方体作为叶子节点。叶子节点包含实际的物体。

struct OctreeNode {
  float centerX, centerY, centerZ;
  float halfSize;
  OctreeNode* children[8];
  std::vector<Object*> objects;
};

OctreeNode* buildOctree(float centerX, float centerY, float centerZ, float halfSize, std::vector<Object*> objects, int depth = 0, int maxDepth = 8, int capacity = 4) {
    OctreeNode* node = new OctreeNode;
    node->centerX = centerX;
    node->centerY = centerY;
    node->centerZ = centerZ;
    node->halfSize = halfSize;

    for (int i = 0; i < 8; ++i) {
        node->children[i] = nullptr;
    }
    node->objects = objects;

    if (objects.size() <= capacity || depth >= maxDepth) {
        return node;
    }

    // Subdivide
    float newHalfSize = halfSize / 2.0f;
    for (int i = 0; i < 8; ++i) {
        float xOffset = newHalfSize * ((i & 1) ? 1 : -1);
        float yOffset = newHalfSize * ((i & 2) ? 1 : -1);
        float zOffset = newHalfSize * ((i & 4) ? 1 : -1);

        std::vector<Object*> childObjects;
        for (Object* obj : objects) {
            if (obj->x >= centerX + xOffset - newHalfSize && obj->x <= centerX + xOffset + newHalfSize &&
                obj->y >= centerY + yOffset - newHalfSize && obj->y <= centerY + yOffset + newHalfSize &&
                obj->z >= centerZ + zOffset - newHalfSize && obj->z <= centerZ + zOffset + newHalfSize) {
                childObjects.push_back(obj);
            }
        }

        node->children[i] = buildOctree(centerX + xOffset, centerY + yOffset, centerZ + zOffset, newHalfSize, childObjects, depth + 1, maxDepth, capacity);
    }

    node->objects.clear(); // Objects are now in child nodes
    return node;
}

5.2 Octree的遍历和碰撞检测

Octree的碰撞检测过程与BVH类似：

1. 根节点： 从Octree的根节点开始。
2. 相交测试： 判断要检测的物体的包围盒是否与当前节点的立方体区域相交。
   • 如果不相交，则直接返回。
   • 如果相交，则继续执行步骤3。
3. 递归： 如果当前节点是叶子节点，则将该节点中的物体与要检测的物体进行精细阶段的碰撞检测。否则，递归地对当前节点的八个子节点执行步骤2。

void traverseOctree(OctreeNode* node, Object& object, std::vector<std::pair<Object*, Object*>>& collisionPairs) {
    //Quick AABB test
    if(object.x + object.radius < node->centerX - node->halfSize || object.x - object.radius > node->centerX + node->halfSize ||
       object.y + object.radius < node->centerY - node->halfSize || object.y - object.radius > node->centerY + node->halfSize ||
       object.z + object.radius < node->centerZ - node->halfSize || object.z - object.radius > node->centerZ + node->halfSize)
        return;

    if (node->children[0] == nullptr) {
        // Leaf node
        for (Object* obj : node->objects) {
            if (isColliding(object, *obj)) {
                collisionPairs.push_back({&object, obj});
            }
        }
    } else {
        // Internal node
        for (int i = 0; i < 8; ++i) {
            if (node->children[i] != nullptr) {
                traverseOctree(node->children[i], object, collisionPairs);
            }
        }
    }
}

void octreeCollisionDetection(OctreeNode* root, std::vector<Object>& objects, std::vector<std::pair<Object*, Object*>>& collisionPairs) {
    collisionPairs.clear();
    for (Object& obj : objects) {
        traverseOctree(root, obj, collisionPairs);
    }
}

5.3 Octree的优点和缺点

• 优点： 实现简单，适用于静态场景或物体移动缓慢的场景，空间分割均匀。
• 缺点： 对于物体分布不均匀的场景，可能导致某些叶子节点包含大量的物体，降低碰撞检测效率。另外，对于动态场景，Octree的维护成本较高。

6. BVH vs. Octree

特性	BVH	Octree
分割方式	基于物体分布的自适应分割	均匀空间分割
适用场景	动态场景，物体分布不均匀的场景	静态场景，物体分布相对均匀的场景
构建复杂度	较高	较低
维护成本	较低（对于动态场景，只需要更新受影响的节点）	较高（对于动态场景，需要频繁地重新构建）

选择哪种数据结构取决于具体的应用场景。如果场景中的物体经常移动，且分布不均匀，则BVH可能更适合。如果场景中的物体基本静止，且分布相对均匀，则Octree可能更适合。

7. 其他优化技巧

除了使用空间数据结构外，还可以采用以下优化技巧来提高碰撞检测效率：

• 包围盒优化： 使用更紧密的包围盒，如OBB，可以减少不必要的相交测试。
• 并行计算： 将碰撞检测任务分配到多个线程或处理器上并行执行。
• SIMD指令： 使用SIMD指令可以同时处理多个数据，提高计算效率。
• 缓存优化： 优化数据访问模式，提高缓存命中率。

8. 代码示例：AABB相交测试的SIMD优化

#include <immintrin.h> // Include for intrinsics

// AABB struct (assuming single-precision floats)
struct AABB_SIMD {
    __m128 min; // x, y, z, w (w unused)
    __m128 max; // x, y, z, w (w unused)
};

// SIMD optimized AABB intersection test
bool intersects_SIMD(const AABB_SIMD& a, const AABB_SIMD& b) {
    // Load AABB mins and maxs into SIMD registers
    __m128 a_min = a.min;
    __m128 a_max = a.max;
    __m128 b_min = b.min;
    __m128 b_max = b.max;

    // Compare a.max >= b.min and b.max >= a.min using SIMD
    __m128 cmp1 = _mm_cmpge_ps(a_max, b_min); // a.max >= b.min
    __m128 cmp2 = _mm_cmpge_ps(b_max, a_min); // b.max >= a.min

    // AND the results of the two comparisons
    __m128 result = _mm_and_ps(cmp1, cmp2);

    // Extract the x, y, and z components (first three floats)
    float* res = (float*)&result;
    return (res[0] != 0.0f && res[1] != 0.0f && res[2] != 0.0f);
}

这个例子展示了如何使用SIMD指令并行地比较AABB的最小和最大坐标，从而加速相交测试。

9. 总结：高效碰撞检测的关键在于空间数据结构的合理应用

在实际应用中，我们需要根据具体的场景和需求选择合适的空间数据结构和优化策略，以达到最佳的碰撞检测性能。理解各种空间数据结构的原理和优缺点，并灵活运用各种优化技巧，是开发高性能碰撞检测系统的关键。

更多IT精英技术系列讲座，到智猿学院