实现“扫描和剪枝”——数据处理的总体设计

Question

我正在使用 C++ 和 OpenGL 开发 3D/物理引擎。

目前我正在实施“扫描和修剪”方法，使用 AABB（轴对齐边界框）进行碰撞检查。我大致遵循此处概述的方法（第 1 部分和第 2 部分）：https://leanrada.com/notes/sweep-and-prune/

该算法的工作原理是对每个 AABB 框的每个轴的最小和最大坐标进行排序：

1. X、Y 和 Z 轴的向量（按坐标排序）
2. 算法还需要知道每条边是最小坐标还是最大坐标。
3. 还有它所属实体的ID。

对于此数据，我使用名为 Edge 的结构：

struct Edge {
    int id;
    bool isLeft;
    float coord;

    Edge(int id, bool isLeft, float coord)
        : id(id), isLeft(isLeft), coord(coord) {}
    }
};

具有 Edge 相关功能的实体类示例：

class Entity
{
public:
    int id;
    std::vector<Edge> edgesList;

    std::vector<glm::vec3> vertices;
    std::vector<unsigned int> indices;
    glm::vec3 position;

    // create Edges
    void setupEdges(const std::vector<float>& minMax)
    {
        // Create Edge objects and add them to edgesList
        edgesList.emplace_back(id, true,  minMax[0]); // min_X
        edgesList.emplace_back(id, false, minMax[1]); // max_X
        edgesList.emplace_back(id, true,  minMax[2]); // min_Y
        edgesList.emplace_back(id, false, minMax[3]); // max_Y
        edgesList.emplace_back(id, true,  minMax[4]); // min_Z
        edgesList.emplace_back(id, false, minMax[5]); // max_Z
    }

    // update Edges. The new coordinates are calculated separately in another function
    void updateEdges(const std::vector<float>& minMax)
    {
        edgesList[0].coord = minMax[0];   // new min_X
        edgesList[1].coord = minMax[1];   // new max_X
        edgesList[2].coord = minMax[2];   // new min_Y
        edgesList[3].coord = minMax[3];   // new max_Y
        edgesList[4].coord = minMax[4];   // new min_Z
        edgesList[5].coord = minMax[5];   // new max_Z
    }

为了节省性能，我想对轴向量使用插入排序（因为通常实体不会每帧交换位置）。

我还想从实体对象内部更新边缘结构并让它自动更新轴向量。

问题： 如何将所有实体中的所有边缘结构放入单个向量中，同时仍然能够更新每个实体（结构所属）内部的值？特别是在对所述向量进行排序之后

Answer 1

一个更简单的解决方案似乎只是将每个实体边缘结构的副本保留在单独的向量中，并通过与每个实体对应的边缘结构 ID 更新该向量。

至少这样我就不用处理指针了。进行坐标的双重更新（在每个实体中以及复制的数据中）有点烦人，但我不必以这种方式处理指针