c++ 实现 BIH 算法-Go服务器开发

以下是一个简单的 C++ 实现 BIH 算法的示例代码，可以用于加速物体碰撞检测：

#include <vector>
#include <algorithm>

// 定义 AABB 包围盒结构体
struct AABB {
    float min_x, max_x;
    float min_y, max_y;
    float min_z, max_z;
};

// 定义节点结构体
struct Node {
    int left_child;   // 左子节点索引
    int right_child;  // 右子节点索引
    AABB box;         // 当前节点所代表的包围盒信息
};

// 构建二叉树层级结构并返回根节点索引值
int BuildBIHTree(std::vector<AABB>& objects, std::vector<Node>& tree) {
    if (objects.empty()) {
        return -1;  // 物体列表为空则返回 -1 表示空节点
    }

    // 计算场景范围（即所有物体包围盒的最小外接矩形）
    AABB scene_box = objects[0];
    for (auto& obj : objects) {
        scene_box.min_x = std::min(scene_box.min_x, obj.min_x);
        scene_box.max_x = std::max(scene_box.max_x, obj.max_x);
        scene_box.min_y = std::min(scene_box.min_y, obj.min_y);
        scene_box.max_y = std::max(scene_box.max_y, obj.max_y);
        scene_box.min_z = std::min(scene_box.min_z, obj.min_z);
        scene_box.max_z = std::max(scene_box.max_z, obj.max_z);
    }

    // 创建根节点并递归构建子节点
    int root_index = tree.size();
    tree.push_back(Node());
    BuildBIHNode(objects, tree, scene_box, root_index);

    return root_index;
}

// 递归构建 BIH 节点
void BuildBIHNode(std::vector<AABB>& objects, std::vector<Node>& tree, AABB box, int node_index) {
    // 将物体按照当前坐标轴方向进行排序
    auto CompareObjects = [&](const AABB& a, const AABB& b) -> bool {
        return (a.min_x + a.max_x) < (b.min_x + b.max_x);
    };
    std::sort(objects.begin(), objects.end(), CompareObjects);

    // 计算最优切割位置和代价函数（这里使用 SAH 算法）
    float best_cost = FLT_MAX;
    int best_pos = 0;
    for (int i = 1; i < objects.size(); ++i) {
        AABB left_box = GetBoundingBox(objects.begin(), objects.begin() + i);
        AABB right_box = GetBoundingBox(objects.begin() + i, objects.end());
        float cost = CalculateSAHCost(left_box, right_box);
        if (cost < best_cost) {
            best_cost = cost;
            best_pos = i;
        }
    }

    // 如果无法继续分裂，则将该节点标记为叶子节点，并记录物体列表的起始索引和数量
    if (best_cost >= CalculateLeafCost(objects.size())) {
        tree[node_index].left_child = -1;
        tree[node_index].right_child = -objects.size();
        return;
    }

    // 分别构建左右子节点
    tree[node_index].left_child = tree.size();
    tree[node_index].right_child = tree.size() + 1;
    tree.push_back(Node());
    tree.push_back(Node());
    BuildBIHNode(std::vector<AABB>(objects.begin(), objects.begin() + best_pos), tree, GetBoundingBox(objects.begin(), objects.begin() + best_pos), tree[node_index].left_child);
    BuildBIHNode(std::vector<AABB>(objects.begin() + best_pos, objects.end()), tree, GetBoundingBox(objects.begin() + best_pos, objects.end()), tree[node_index].right_child);

    // 更新当前节点的包围盒信息
    AABB left_box = tree[tree[node_index].left_child].box;
    AABB right_box = tree[tree[node_index].right_child].box;
    box.min_x = std::min(left_box.min_x, right_box.min_x);
    box.max_x = std::max(left_box.max_x, right_box.max_x);
    box.min_y = std::min(left_box.min_y, right_box.min_y);
    box.max_y = std::max(left_box.max_y, right_box.max_y);
    box.min_z = std::min(left_box.min_z, right_box.min_z);
    box.max_z = std::max(left_box.max_z, right_box.max_z);

    // 将当前节点的包围盒信息存储到树结构中
    tree[node_index].box = box;
}

// 计算物体列表的最小外接矩形包围盒
AABB GetBoundingBox(std::vector<AABB>::iterator begin_iter, std::vector<AABB>::iterator end_iter) {
  AABB box;
  if (begin_iter == end_iter) {
      return box;
  }
  
  box = *begin_iter;
  for (auto iter = begin_iter + 1; iter != end_iter; ++iter) {
      box.min_x = std::min(box.min_x, iter->min_x);
      box.max_x = std::max(box.max_x, iter->max_x);
      box.min_y = std::min(box.min_y, iter->min_y);
      box.max_y = std::max(box.max_y, iter->max_y);
      box.min_z = std::min(box.min_z, iter->min_z);
      box.max_z = std::max(box.max_z, iter->max_z);
  }
  
  return box;
}

// 计算 SAH 代价函数
float CalculateSAHCost(AABB left_box, AABB right_box) {
    float left_area = (left_box.max_x - left_box.min_x) * (left_box.max_y - left_box.min_y) * (left_box.max_z - left_box.min_z);
    float right_area = (right_box.max_x - right_box.min_x) * (right_box.max_y - right_box.min_y) * (right_box.max_z - right_box.min_z);
    float total_cost = CalculateTraversalCost(left_area + right_area);

    auto CountObjectsInBox = [](std::vector<AABB>& objects, AABB box) -> int {
        int count = 0;
        for (auto& obj : objects) {
            if ((obj.min_x >= box.min_x && obj.max_x <= box.max_x)
                && (obj.min_y >= box.min_y && obj.max_y <= box.max_y)
                && (obj.min_z >= box.min_z && obj.max_z <= box.max_z)) {
                ++count;
            }
        }
        return count;
    };
    
    // 在最优切割位置处分别计算左右子树包含的物体数量
    int num_left = CountObjectsInBox(objects, left_box);
    int num_right = CountObjectsInBox(objects, right_box);

    // 计算每个子树的 SAH 代价并加权求和
    float cost_left = CalculateTraversalCost(left_area) + CalculateIntersectionCost(num_left, left_area);
    float cost_right = CalculateTraversalCost(right_area) + CalculateIntersectionCost(num_right, right_area);
    return (cost_left * num_left + cost_right * num_right) / total_cost;
}

// 计算遍历代价（这里默认为 1.0）
float CalculateTraversalCost(float area) {
    return 1.0f;
}

// 计算相交代价（这里默认为 2.0）
float CalculateIntersectionCost(int count, float area) {
    return 2.0f;
}

// 计算叶子节点代价函数
float CalculateLeafCost(int count) {
    return static_cast<float>(count);   // 这里使用物体数量作为叶子节点的代价
}

注意，以上代码仅是 BIH 算法的一个简单实现示例，并不包括一些优化技巧，如空间分区、面积启发式等。在实际应用中，需要根据具体情况进行调整和优化。

内容由零声教学AI助手提供，问题来源于学员提问