实现Sweep and Prune算法：数据处理设计与更新同步问题

核心思路 #

要实现Entity内部更新Edge时自动同步到全局轴向量，关键是让全局向量和Entity持有同一个Edge实例的指针，而非各自存储独立拷贝。这样修改Entity内的Edge值后，全局向量中的对应Edge数据会自动更新，排序结果也能实时反映最新状态。

具体实现步骤 #

1. 定义可修改的Edge结构体 #

确保Edge的坐标值是可直接修改的成员变量：

struct Edge {
    int entity_id;    // 所属实体ID
    bool is_min;      // true=AABB最小坐标边，false=最大坐标边
    float value;      // 坐标值，支持实时修改
};

2. 设计Entity类，持有自身的Edge实例 #

每个Entity拥有6个Edge（对应x/y/z轴的最小/最大边），提供更新方法直接修改Edge的value，同时暴露Edge指针供全局向量引用：

class Entity {
private:
    Edge x_min_edge;
    Edge x_max_edge;
    Edge y_min_edge;
    Edge y_max_edge;
    Edge z_min_edge;
    Edge z_max_edge;

public:
    Entity(int id) {
        // 初始化Edge基础属性
        x_min_edge = {id, true, 0.0f};
        x_max_edge = {id, false, 0.0f};
        y_min_edge = {id, true, 0.0f};
        y_max_edge = {id, false, 0.0f};
        z_min_edge = {id, true, 0.0f};
        z_max_edge = {id, false, 0.0f};
    }

    // 更新AABB并同步修改对应Edge的坐标值
    void updateAABB(float x_min, float x_max, float y_min, float y_max, float z_min, float z_max) {
        x_min_edge.value = x_min;
        x_max_edge.value = x_max;
        y_min_edge.value = y_min;
        y_max_edge.value = y_max;
        z_min_edge.value = z_min;
        z_max_edge.value = z_max;
    }

    // 获取各Edge的指针，用于注册到全局轴向量
    Edge* getXMinEdge() { return &x_min_edge; }
    Edge* getXMaxEdge() { return &x_max_edge; }
    Edge* getYMinEdge() { return &y_min_edge; }
    Edge* getYMaxEdge() { return &y_max_edge; }
    Edge* getZMinEdge() { return &z_min_edge; }
    Edge* getZMaxEdge() { return &z_max_edge; }
};

3. 全局轴向量存储Edge指针 #

为x/y/z轴分别维护一个存储Edge指针的向量，确保向量元素直接指向Entity持有的Edge实例：

#include <vector>
std::vector<Edge*> x_edges;
std::vector<Edge*> y_edges;
std::vector<Edge*> z_edges;

创建Entity时，将其Edge指针添加到对应轴的全局向量：

Entity* createEntity(int id) {
    Entity* ent = new Entity(id);
    x_edges.push_back(ent->getXMinEdge());
    x_edges.push_back(ent->getXMaxEdge());
    y_edges.push_back(ent->getYMinEdge());
    y_edges.push_back(ent->getYMaxEdge());
    z_edges.push_back(ent->getZMinEdge());
    z_edges.push_back(ent->getZMaxEdge());
    return ent;
}

4. 同步更新与排序维护 #

• 自动同步：调用entity->updateAABB(...)修改Edge的value时，全局向量中指针指向的Edge实例值会自动更新，无需额外操作。
• 插入排序优化：由于Sweep and Prune中Edge的位置变化通常很小，使用插入排序调整单个Edge位置比全量排序更高效。实现调整函数：

#include <algorithm>

// 调整指定Edge在轴向量中的排序位置（插入排序逻辑）
void adjustEdgePosition(std::vector<Edge*>& edges, Edge* target_edge) {
    // 找到目标Edge在向量中的位置
    auto it = std::find(edges.begin(), edges.end(), target_edge);
    if (it == edges.end()) return;

    size_t idx = std::distance(edges.begin(), it);

    // 向前移动到正确位置
    while (idx > 0 && edges[idx-1]->value > target_edge->value) {
        std::swap(edges[idx], edges[idx-1]);
        idx--;
    }

    // 向后移动到正确位置
    while (idx < edges.size()-1 && edges[idx+1]->value < target_edge->value) {
        std::swap(edges[idx], edges[idx+1]);
        idx++;
    }
}

更新Entity的AABB后，调用该函数维护对应轴的向量排序：

// 示例：更新实体AABB后维护x轴向量排序
Entity* my_entity = ...;
my_entity->updateAABB(1.0f, 3.0f, 0.0f, 2.0f, -1.0f, 1.0f);
adjustEdgePosition(x_edges, my_entity->getXMinEdge());
adjustEdgePosition(x_edges, my_entity->getXMaxEdge());

5. 注意事项 #

• 内存安全：销毁Entity时，必须从全局向量中移除对应的Edge指针，避免悬空指针。可在Entity析构函数中处理，或维护实体列表定期清理。
• 线程安全：多线程环境下，对全局向量的访问和修改需要加锁保护。
• 避免拷贝：全局向量必须存储指针而非Edge拷贝，否则无法实现同步更新。

内容的提问来源于stack exchange，提问作者Zoler1337