如何加速三角形与AABB相交测试以提升网格体素化效率？

性能瓶颈分析 #

你的代码效率低是多个细节的累积开销导致，核心问题包括：

1. 不必要的std::vector构造与内存分配：checkTriangleIntersectAABB每次调用都会创建多个临时vector（如Axis、Point、Edge），频繁的内存分配/释放会带来巨大性能损耗——这个函数会被调用数十万甚至数百万次，累计开销非常可观。
2. 冗余的归一化操作：SAT判断分离轴时不需要对轴向量做归一化，投影的相对大小仅需判断是否重叠，normalized()涉及的平方根计算属于高开销冗余操作。
3. Eigen操作的冗余计算：用vector存储三个顶点/边会增加下标寻址开销；计算CubeProjection时，用坐标轴与轴向量的点积完全可以简化为直接取轴向量的分量，省去点积计算。
4. 临时变量拷贝：voxelizeInSurface中创建Triangle vector会拷贝顶点，增加额外开销。

针对性优化方案 #

1. 消除临时std::vector，改用栈变量 #

将所有动态vector替换为栈上的固定变量，避免内存分配：

bool checkTriangleIntersectAABB(const Eigen::Vector3d& v0, const Eigen::Vector3d& v1, const Eigen::Vector3d& v2, 
                                const Eigen::Vector3d& vCenter, const Eigen::Vector3d& vExtent)
{
    // 直接计算平移后的顶点，无需vector
    const Eigen::Vector3d p0 = v0 - vCenter;
    const Eigen::Vector3d p1 = v1 - vCenter;
    const Eigen::Vector3d p2 = v2 - vCenter;

    // 计算边向量，无需vector
    const Eigen::Vector3d e0 = p1 - p0;
    const Eigen::Vector3d e1 = p2 - p1;
    const Eigen::Vector3d e2 = p0 - p2;

    // 直接定义13个分离轴，无需动态存储
    const Eigen::Vector3d axes[] = {
        Eigen::Vector3d(1,0,0), Eigen::Vector3d(0,1,0), Eigen::Vector3d(0,0,1),
        e0.cross(Eigen::Vector3d(1,0,0)), e0.cross(Eigen::Vector3d(0,1,0)), e0.cross(Eigen::Vector3d(0,0,1)),
        e1.cross(Eigen::Vector3d(1,0,0)), e1.cross(Eigen::Vector3d(0,1,0)), e1.cross(Eigen::Vector3d(0,0,1)),
        e2.cross(Eigen::Vector3d(1,0,0)), e2.cross(Eigen::Vector3d(0,1,0)), e2.cross(Eigen::Vector3d(0,0,1)),
        e0.cross(e1)
    };

    for (int i = 0; i < 13; ++i) {
        const Eigen::Vector3d& axis = axes[i];
        // 直接计算投影值，无需存储到vector
        const double proj0 = p0.dot(axis);
        const double proj1 = p1.dot(axis);
        const double proj2 = p2.dot(axis);

        // 直接找投影的min/max，避免vector构造
        const double minProj = std::min(std::min(proj0, proj1), proj2);
        const double maxProj = std::max(std::max(proj0, proj1), proj2);

        // 简化CubeProjection计算：直接取轴的分量（坐标轴点积等价于取分量）
        const double cubeProj = vExtent.x() * std::abs(axis.x()) +
                                vExtent.y() * std::abs(axis.y()) +
                                vExtent.z() * std::abs(axis.z());

        // 分离判断：找到分离轴立即返回
        if (minProj > cubeProj || maxProj < -cubeProj) {
            return false;
        }
    }
    return true;
}

2. 减少函数调用中的拷贝开销 #

在voxelizeInSurface中直接传递顶点引用，避免拷贝：

// 原代码：创建Triangle vector拷贝顶点
// std::vector<Eigen::Vector3d> Triangle = { vTriangleMesh.vertices_[Indexs[0]], ... };

// 改为直接引用原始顶点
const auto& v0 = vTriangleMesh.vertices_[Indexs[0]];
const auto& v1 = vTriangleMesh.vertices_[Indexs[1]];
const auto& v2 = vTriangleMesh.vertices_[Indexs[2]];

// 调用相交测试函数
if (checkTriangleIntersectAABB(v0, v1, v2, Center, Extent)) {
    // ... 体素标记逻辑
}

3. 预计算体素范围，避免重复操作 #

优化三角包围盒的计算，直接用原始顶点扩展：

Eigen::AlignedBox3d TriangleBound;
TriangleBound.extend(v0);
TriangleBound.extend(v1);
TriangleBound.extend(v2);

4. 启用编译器优化 #

编译时开启-O2/-O3（GCC/Clang）或/O2（MSVC），编译器会自动做循环展开、内存优化等操作，进一步提升性能。

更高效的替代算法 #

如果优化后仍达不到预期性能，可以考虑以下方案：

• 光线投射法：对每个体素从内部发射光线，统计与三角的交点数判断是否在网格内部，结合BVH空间划分加速三角查找。
• 扫描线体素化：沿坐标轴扫描三角网格，跟踪当前被三角覆盖的体素区间，批量标记体素，避免逐个测试体素与三角的相交。
• Open3D批量处理逻辑：Open3D的体素化采用八叉树空间划分+SIMD指令加速，若无需手动实现，可直接调用open3d::geometry::VoxelGrid::CreateFromTriangleMesh。

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