茂之钳
226 lines
6.8 KiB
C++
226 lines
6.8 KiB
C++
/**
|
||
* @file bvh.h
|
||
* @brief 包围盒层次结构 (Bounding Volume Hierarchy)
|
||
*
|
||
* 基于二叉树的自适应空间划分结构，适用于三角形网格的快速
|
||
* 射线求交、范围查询与最近邻查询。
|
||
*
|
||
* 默认使用 SAH (Surface Area Heuristic) 启发式策略进行
|
||
* 自顶向下构建，在质量和构建时间之间取得较好平衡。
|
||
*
|
||
* @ingroup spatial
|
||
*/
|
||
|
||
#pragma once
|
||
#include <optional>
|
||
#include "vde/spatial/spatial_index.h"
|
||
#include "vde/core/aabb.h"
|
||
#include "vde/core/triangle.h"
|
||
|
||
namespace vde::spatial {
|
||
using core::Point3D;
|
||
using core::Vector3D;
|
||
using core::Ray3Dd;
|
||
using core::Triangle3D;
|
||
|
||
/**
|
||
* @brief BVH 构建分裂策略
|
||
*/
|
||
enum class BVHSplitStrategy {
|
||
Middle, /**< 按最长轴中点分裂 */
|
||
Equal, /**< 按数量均等分裂 */
|
||
SAH /**< Surface Area Heuristic — 最小化射线击中概率期望 */
|
||
};
|
||
|
||
/**
|
||
* @brief BVH 构建选项
|
||
*
|
||
* 控制 BVH 树的构建行为和质量参数。
|
||
*/
|
||
struct BVHBuildOptions {
|
||
BVHSplitStrategy strategy = BVHSplitStrategy::SAH; /**< 分裂策略 */
|
||
int leaf_size = 4; /**< 叶节点最大图元数 */
|
||
int max_depth = 64; /**< 树的最大深度 */
|
||
};
|
||
|
||
/**
|
||
* @brief 包围盒层次结构 — 三角形网格加速结构
|
||
*
|
||
* BVH 将三角形集合递归划分为嵌套的包围盒树。
|
||
* 每个内部节点存储其子节点包围盒的并集，
|
||
* 叶节点包含不超过 leaf_size 个三角形的引用。
|
||
*
|
||
* 构建时间复杂度 O(n log n)，空间 O(n)。
|
||
* 单条射线查询 O(log n)，最近命中 O(log n)。
|
||
*
|
||
* 三种分裂策略：
|
||
* - Middle: 沿最长轴按包围盒中点一分为二，构建最快但质量一般
|
||
* - Equal: 按三角形数量平分，适合均匀分布
|
||
* - SAH: 最小化随机射线命中成本期望，构建慢但查询最快（默认）
|
||
*
|
||
* @code{.cpp}
|
||
* BVH bvh(BVHBuildOptions{ .strategy = BVHSplitStrategy::SAH, .leaf_size = 8 });
|
||
* bvh.build(triangles);
|
||
* auto hit = bvh.query_ray_nearest(ray);
|
||
* auto near = bvh.query_knn(p, 10);
|
||
* @endcode
|
||
*
|
||
* @see SpatialIndex, Octree, KDTree, RTree
|
||
*/
|
||
class BVH : public SpatialIndex<Triangle3D> {
|
||
public:
|
||
/**
|
||
* @brief 构造 BVH 并指定构建选项
|
||
*
|
||
* @param opts 构建选项（分裂策略、叶节点大小、最大深度）
|
||
*/
|
||
explicit BVH(const BVHBuildOptions& opts = {}) : opts_(opts) {}
|
||
|
||
/**
|
||
* @brief 清除已有数据并重建 BVH
|
||
*
|
||
* 使用 SAH（或指定策略）自顶向下递归构建。
|
||
* 构建复杂度 O(n log n)。
|
||
*
|
||
* @param tris 三角形数组
|
||
*/
|
||
void build(const std::vector<Triangle3D>& tris) override;
|
||
|
||
/**
|
||
* @brief 插入单个三角形
|
||
*
|
||
* 当前实现：加入图元列表后全量重建。
|
||
* 如需增量插入，建议使用 RTree。
|
||
*
|
||
* @param tri 要插入的三角形
|
||
*/
|
||
void insert(const Triangle3D& tri) override;
|
||
|
||
/**
|
||
* @brief 删除三角形
|
||
*
|
||
* @param tri 要删除的三角形
|
||
* @return 删除成功返回 true
|
||
*/
|
||
bool remove(const Triangle3D& tri) override;
|
||
|
||
/**
|
||
* @brief AABB 范围查询
|
||
*
|
||
* 遍历与 range 相交的 BVH 节点，收集叶节点中重叠的三角形。
|
||
* 复杂度 O(log n + k)，k 为结果数量。
|
||
*
|
||
* @param range 查询包围盒
|
||
* @return 与 range 相交的三角形列表
|
||
*/
|
||
std::vector<Triangle3D> query_range(const AABB3D& range) const override;
|
||
|
||
/**
|
||
* @brief K 近邻查询
|
||
*
|
||
* 使用最小堆遍历 BVH，按包围盒距离剪枝。
|
||
*
|
||
* @param point 查询点
|
||
* @param k 返回数量
|
||
* @return 最近的 k 个三角形
|
||
*/
|
||
std::vector<Triangle3D> query_knn(const Point3D& point, size_t k) const override;
|
||
|
||
/**
|
||
* @brief 射线查询：返回所有命中的三角形
|
||
*
|
||
* 深度优先遍历，收集所有与射线相交的叶节点三角形。
|
||
* 复杂度 O(log n + k)。
|
||
*
|
||
* @param ray 查询射线
|
||
* @return 按命中顺序排列的三角形列表
|
||
*/
|
||
std::vector<Triangle3D> query_ray(const Ray3Dd& ray) const override;
|
||
|
||
/**
|
||
* @brief 清空 BVH 树和所有三角形
|
||
*/
|
||
void clear() override;
|
||
|
||
/**
|
||
* @brief 三角形数量
|
||
*
|
||
* @return 当前索引的三角形总数
|
||
*/
|
||
size_t size() const override { return primitives_.size(); }
|
||
|
||
/**
|
||
* @brief 射线最近命中查询结果
|
||
*/
|
||
struct HitResult {
|
||
double t; /**< 沿射线的参数 t */
|
||
Triangle3D tri; /**< 命中的三角形 */
|
||
Point3D point; /**< 命中点的世界坐标 = origin + t * dir */
|
||
};
|
||
|
||
/**
|
||
* @brief 射线最近命中查询
|
||
*
|
||
* 遍历 BVH，维护当前最近 t 值进行剪枝，
|
||
* 返回射线方向上第一个命中的三角形。
|
||
* 典型复杂度 O(log n)。
|
||
*
|
||
* @param ray 查询射线
|
||
* @return 最近命中结果（若无命中则返回空）
|
||
*
|
||
* @note 比 query_ray() 更高效，仅返回最近命中
|
||
*
|
||
* @code{.cpp}
|
||
* if (auto hit = bvh.query_ray_nearest(ray)) {
|
||
* std::cout << "Hit at t=" << hit->t << ", point=" << hit->point << "\n";
|
||
* }
|
||
* @endcode
|
||
*/
|
||
std::optional<HitResult> query_ray_nearest(const Ray3Dd& ray) const;
|
||
|
||
private:
|
||
/**
|
||
* @brief BVH 节点
|
||
*
|
||
* 内部节点存储左右子节点索引（left, right）；
|
||
* 叶节点存储图元列表的起始索引和数量（first_prim, prim_count）。
|
||
*/
|
||
struct Node {
|
||
AABB3D bounds; /**< 节点的包围盒（所有子节点/图元的并集） */
|
||
int left = -1; /**< 左子节点索引，叶节点为 -1 */
|
||
int right = -1; /**< 右子节点索引，叶节点为 -1 */
|
||
int first_prim = 0; /**< 叶节点第一个图元的索引 */
|
||
int prim_count = 0; /**< 叶节点图元数量 */
|
||
|
||
/** @brief 判断是否为叶节点 */
|
||
bool leaf() const { return left < 0; }
|
||
};
|
||
|
||
std::vector<Node> nodes_; /**< 节点数组（根节点为 nodes_[0]） */
|
||
std::vector<Triangle3D> primitives_; /**< 图元数组 */
|
||
BVHBuildOptions opts_; /**< 构建选项 */
|
||
|
||
/**
|
||
* @brief 递归构建 BVH 子树
|
||
*
|
||
* @param node 当前节点索引
|
||
* @param first 图元范围的起始索引
|
||
* @param count 图元数量
|
||
* @param depth 当前递归深度
|
||
*/
|
||
void build_recursive(int node, int first, int count, int depth);
|
||
|
||
/**
|
||
* @brief 计算 SAH 分裂代价
|
||
*
|
||
* @param n_left 左子树图元数
|
||
* @param n_right 右子树图元数
|
||
* @param left 左子树包围盒
|
||
* @param right 右子树包围盒
|
||
* @return SAH 代价估值
|
||
*/
|
||
double sah_cost(int n_left, int n_right, const AABB3D& left, const AABB3D& right) const;
|
||
};
|
||
|
||
} // namespace vde::spatial
|