ViewDesignEngine/include/vde/collision/sat.h

/**
 * @file sat.h
 * @brief SAT (Separating Axis Theorem) 碰撞检测
 *
 * 基于分离轴定理的凸多面体相交检测。
 * 若存在一条轴使得两形状投影不重叠，则不相交。
 *
 * @ingroup collision
 */

#pragma once
#include "vde/core/point.h"
#include <vector>
#include <array>

namespace vde::collision {
using core::Point3D;

/**
 * @brief SAT 凸多面体相交检测
 *
 * 分离轴定理：两个凸多面体不相交，当且仅当存在一条分离轴，
 * 使得二者在该轴上的投影区间不重叠。
 *
 * 待检测的分离轴集合：
 * - A 的每个面法线
 * - B 的每个面法线
 * - A 的每条边与 B 的每条边的叉积
 *
 * 对每条候选轴，计算两个多面体投影区间的最小/最大值。
 * 若某轴上投影区间无重叠 → 不相交（早停）。
 * 所有轴都重叠 → 相交。
 *
 * 最坏时间复杂度 O(n_a · n_b)，其中 n_a, n_b 为面数。
 * 对于凸多面体通常在遍历部分轴后即早停。
 *
 * @param verts_a 多面体 A 的顶点数组
 * @param faces_a 多面体 A 的面索引数组（每个面为 {v0, v1, v2}）
 * @param verts_b 多面体 B 的顶点数组
 * @param faces_b 多面体 B 的面索引数组
 * @return 相交返回 true
 *
 * @note 适用于任意凸多面体。对于胶囊/球等光滑形状，GJK 更合适。
 *
 * @code{.cpp}
 * // 两个凸四面体相交检测
 * std::vector<Point3D> va = {{0,0,0}, {1,0,0}, {0,1,0}, {0,0,1}};
 * std::vector<std::array<int,3>> fa = {{0,2,1}, {0,1,3}, {0,3,2}, {1,2,3}};
 * std::vector<Point3D> vb = {{0.5,0.5,0.5}, {1.5,0.5,0.5}, ...};
 * std::vector<std::array<int,3>> fb = { ... };
 * bool hit = sat_intersect(va, fa, vb, fb);
 * @endcode
 *
 * @see gjk_intersect, tri_tri_intersect
 */
bool sat_intersect(const std::vector<Point3D>& verts_a,
                   const std::vector<std::array<int,3>>& faces_a,
                   const std::vector<Point3D>& verts_b,
                   const std::vector<std::array<int,3>>& faces_b);

}  // namespace vde::collision