ViewDesignEngine/include/vde/sdf/sdf_tree.h

#pragma once
/**
 * @file sdf_tree.h
 * @brief SDF 表达式树结构
 *
 * 将 SDF 原语和 CSG 操作以树形数据结构表示，支持树遍历、求值和包围盒估算。
 *
 * ## 架构层级
 *
 * ```
 * SdfNode (树节点)                    — 单节点，含操作类型+参数+子节点
 *   ├─ enum SdfOp                     — 操作枚举（图元/CSG/修饰/变形）
 *   ├─ struct SdfParams               — 参数联合体
 *   ├─ 静态工厂方法                    — 创建各类型节点
 *   └─ visit()                        — 前序遍历
 *
 * evaluate()                          — 递归求值
 * estimate_bounds() / estimate_bbox() — 包围盒估算
 * ```
 *
 * ## 使用模式
 *
 * 通过静态工厂方法构建节点树，然后调用 evaluate() 进行求值：
 *
 * @code{.cpp}
 * auto root = SdfNode::op_union(
 *     SdfNode::sphere(1.0),
 *     SdfNode::box(Point3D(0.5, 0.5, 0.5))
 * );
 * double d = evaluate(root, Point3D(1.0, 0.0, 0.0));
 * @endcode
 *
 * @ingroup sdf
 */
#include "vde/sdf/sdf_primitives.h"
#include "vde/sdf/sdf_operations.h"
#include "vde/core/point.h"
#include <memory>
#include <string>
#include <vector>

namespace vde::sdf {
using core::Point3D;
using core::Vector3D;

// Forward declaration
class SdfNode;
using SdfNodePtr = std::shared_ptr<SdfNode>;

/**
 * @brief CSG 树的所有节点类型
 *
 * 枚举涵盖三类操作：
 * - **图元**（Sphere, Box, ...） — 叶子节点，产生基本几何体
 * - **CSG 布尔**（Union, Intersection, Difference） — 二叉树组合
 * - **修饰/变形**（Round, Translate, Twist, ...） — 单子节点变换
 *
 * @see SdfParams 对应的参数结构
 */
enum class SdfOp : uint8_t {
    // Primitives
    Sphere, Box, RoundBox, Torus, Capsule, Cylinder, Cone, Plane,
    Ellipsoid, TriangularPrism, HexPrism, Link, Wedge,
    // Boolean CSG
    Union, Intersection, Difference,
    SmoothUnion, SmoothIntersection, SmoothDifference,
    // Modifiers
    Round, Onion,
    // Domain transforms
    Repeat, MirrorX, MirrorY, MirrorZ, Translate, Rotate, Scale,
    Twist, Bend, Elongate, CheapBend,
    // Displacement
    Displace
};

/**
 * @brief SDF 节点参数联合体
 *
 * 一个结构体囊括所有可能的参数。不同操作类型使用不同字段子集：
 *
 * | 操作类型          | 使用字段                                    |
 * |-------------------|--------------------------------------------|
 * | Sphere            | radius                                     |
 * | Box / RoundBox    | extents                                   |
 * | Cylinder / Cone   | radius, height, angle_rad                 |
 * | Plane             | normal, offset                            |
 * | Torus             | major_radius, minor_radius                |
 * | Capsule           | pt_a, pt_b, radius                        |
 * | Smooth CSG        | blend_k                                   |
 * | Repeat            | repeat_cell                               |
 * | Translate         | translate_offset                          |
 * | Scale             | scale_factors                             |
 * | Displace          | amplitude, frequency                      |
 * | Twist/Bend        | amount                                    |
 * | Onion             | thickness                                 |
 * | Round             | offset                                    |
 *
 * @warning 不使用的字段保持默认值即可，但不要依赖未使用字段的默认值来做逻辑判断。
 */
struct SdfParams {
    // ── Primitive parameters ──
    double radius = 1.0;        ///< 球体/圆柱/胶囊/圆角半径
    Point3D extents = Point3D(1, 1, 1);  ///< 盒子的半边长
    Point3D pt_a = Point3D(0, -1, 0);    ///< 胶囊端点 A
    Point3D pt_b = Point3D(0, 1, 0);     ///< 胶囊端点 B
    double major_radius = 1.0;   ///< 圆环主半径
    double minor_radius = 0.3;   ///< 圆环副半径
    double angle_rad = 0.5;      ///< 锥体半角（弧度）
    double height = 2.0;         ///< 柱体/锥体/挤出高度
    double thickness = 0.1;      ///< 壳层厚度（Onion）
    Vector3D normal = Vector3D(0, 1, 0);  ///< 平面法向量
    double offset = 0.0;         ///< 平面偏移 / 通用偏移

    // ── Operation parameters ──
    double blend_k = 0.2;        ///< 平滑 CSG 混合参数
    double amount = 0.5;         ///< 扭曲/弯曲量
    double amplitude = 0.1;      ///< 位移扰动幅值
    double frequency = 1.0;      ///< 位移扰动频率
    Point3D repeat_cell = Point3D(2, 2, 2);     ///< 重复晶格尺寸
    Point3D translate_offset = Point3D(0, 0, 0); ///< 平移量
    Point3D scale_factors = Point3D(1, 1, 1);    ///< 缩放因子
};

/**
 * @brief SDF 表达式树节点
 *
 * 每个节点包含：
 * - `op`: 操作类型
 * - `params`: 参数值
 * - `children`: 子节点列表（CSG 布尔 = 2 个子节点，修饰/变形 = 1 个，图元 = 0 个）
 * - `name`: 可选名称（调试用）
 *
 * 使用 make_shared<SdfNode>(op) 或静态工厂方法创建节点。
 * 所有工厂方法返回 SdfNodePtr（shared_ptr），自动管理生命周期。
 *
 * @note 树是不可变的——节点创建后 op 和子节点关系不变，但 params 可被外部修改以支持参数优化。
 */
class SdfNode {
public:
    SdfOp op;                          ///< 操作类型
    SdfParams params;                  ///< 参数值
    std::vector<SdfNodePtr> children;  ///< 子节点
    std::string name;                  ///< 节点名（调试用）

    // ── Primitive factories ──

    /** @brief 创建球体节点 */
    static SdfNodePtr sphere(double r);

    /** @brief 创建轴对齐长方体节点 */
    static SdfNodePtr box(const Point3D& half_extents);

    /** @brief 创建圆角长方体节点 */
    static SdfNodePtr round_box(const Point3D& half_extents, double r);

    /** @brief 创建圆柱体节点 */
    static SdfNodePtr cylinder(double r, double h);

    /** @brief 创建圆环体节点 */
    static SdfNodePtr torus(double major_r, double minor_r);

    /** @brief 创建胶囊体节点 */
    static SdfNodePtr capsule(const Point3D& a, const Point3D& b, double r);

    /** @brief 创建圆锥台节点 */
    static SdfNodePtr cone(double angle_rad, double h);

    /** @brief 创建平面节点 */
    static SdfNodePtr plane(const Vector3D& normal, double offset);

    /** @brief 创建椭球体节点 */
    static SdfNodePtr ellipsoid(const Point3D& radii);

    /** @brief 创建三角棱柱节点 */
    static SdfNodePtr triangular_prism(double h);

    /** @brief 创建六棱柱节点 */
    static SdfNodePtr hex_prism(double h);

    /** @brief 创建双环链接节点 */
    static SdfNodePtr link(double r, double length, double thickness);

    /** @brief 创建楔形体节点 */
    static SdfNodePtr wedge(const Point3D& extents);

    // ── Boolean CSG factories (two children) ──

    /** @brief 创建并集节点: A ∪ B */
    static SdfNodePtr op_union(SdfNodePtr a, SdfNodePtr b);

    /** @brief 创建交集节点: A ∩ B */
    static SdfNodePtr op_intersection(SdfNodePtr a, SdfNodePtr b);

    /** @brief 创建差集节点: A \ B */
    static SdfNodePtr op_difference(SdfNodePtr a, SdfNodePtr b);

    /** @brief 创建平滑并集节点 */
    static SdfNodePtr smooth_union(SdfNodePtr a, SdfNodePtr b, double k);

    /** @brief 创建平滑交集节点 */
    static SdfNodePtr smooth_intersection(SdfNodePtr a, SdfNodePtr b, double k);

    /** @brief 创建平滑差集节点 */
    static SdfNodePtr smooth_difference(SdfNodePtr a, SdfNodePtr b, double k);

    // ── Modifier factories (one child) ──

    /** @brief 创建圆角偏移节点 */
    static SdfNodePtr round(SdfNodePtr child, double r);

    /** @brief 创建壳层修饰节点 */
    static SdfNodePtr onion(SdfNodePtr child, double thickness);

    // ── Domain transform factories (one child) ──

    /** @brief 创建周期重复节点 */
    static SdfNodePtr repeat(SdfNodePtr child, const Point3D& cell);

    /** @brief 创建 X 镜像节点 */
    static SdfNodePtr mirror_x(SdfNodePtr child);

    /** @brief 创建 Y 镜像节点 */
    static SdfNodePtr mirror_y(SdfNodePtr child);

    /** @brief 创建 Z 镜像节点 */
    static SdfNodePtr mirror_z(SdfNodePtr child);

    /** @brief 创建平移节点 */
    static SdfNodePtr translate(SdfNodePtr child, const Point3D& offset);

    /** @brief 创建旋转节点（绕 Y 轴） */
    static SdfNodePtr rotate(SdfNodePtr child, double angle_rad);

    /** @brief 创建缩放节点 */
    static SdfNodePtr scale(SdfNodePtr child, const Point3D& factors);

    /** @brief 创建扭曲节点 */
    static SdfNodePtr twist(SdfNodePtr child, double amount);

    /** @brief 创建弯曲节点 */
    static SdfNodePtr bend(SdfNodePtr child, double amount);

    /** @brief 创建拉伸节点 */
    static SdfNodePtr elongate(SdfNodePtr child, const Point3D& h);

    /** @brief 创建简化弯曲节点 */
    static SdfNodePtr cheap_bend(SdfNodePtr child, double amount);

    /** @brief 创建位移扰动节点 */
    static SdfNodePtr displace(SdfNodePtr child, double amplitude, double frequency);

    /**
     * @brief 前序遍历所有节点
     *
     * 对树中每个节点调用回调函数 fn，遍历顺序为前序（父节点先于子节点）。
     *
     * @tparam Fn 可调用对象，签名为 void(SdfNode&)
     *
     * @code{.cpp}
     * int leaf_count = 0;
     * root->visit([&](const SdfNode& n) {
     *     if (n.children.empty()) ++leaf_count;
     * });
     * @endcode
     */
    template <typename Fn>
    void visit(Fn&& fn) {
        fn(*this);
        for (auto& c : children) c->visit(std::forward<Fn>(fn));
    }

    /**
     * @brief 前序遍历（const 版本）
     *
     * @tparam Fn 可调用对象，签名为 void(const SdfNode&)
     * @see visit(Fn&&)
     */
    template <typename Fn>
    void visit(Fn&& fn) const {
        fn(*this);
        for (auto& c : children) c->visit(std::forward<Fn>(fn));
    }

public:
    /**
     * @brief 构造 SDF 节点
     * @param o 操作类型
     */
    explicit SdfNode(SdfOp o) : op(o) {}
};

/**
 * @brief 在空间点 p 处求值 SDF 树
 *
 * 递归遍历表达式树，在叶节点调用对应图元的 SDF 函数，
 * 在内部节点执行 CSG 操作或域变形。
 *
 * **算法概要:**
 * 1. 域变形节点先对 p 做变换，将变换后的点传入子节点
 * 2. CSG 布尔节点分别求值两个子节点后组合
 * 3. 图元节点直接调用内联 SDF 函数
 *
 * @param root SDF 表达式树的根节点
 * @param p 世界空间中的采样点
 * @return 有符号距离（负 = 内部，零 = 表面，正 = 外部）
 *
 * @code{.cpp}
 * auto root = SdfNode::sphere(1.0);
 * double d = evaluate(root, Point3D(0.5, 0.0, 0.0));  // ≈ -0.5
 * @endcode
 *
 * @see estimate_bounds 估计树的包围盒
 */
[[nodiscard]] double evaluate(const SdfNodePtr& root, const Point3D& p);

/**
 * @brief 估算 SDF 树的包围半尺寸
 *
 * 通过对叶节点包围盒的递归合并，估算从树根到最远角落的半径。
 * 结果是包围盒的半边长（从中心到面的距离）。
 *
 * @param root SDF 树的根节点
 * @param margin 额外安全边距（默认 1.0）
 * @return 包围半边长 (hx, hy, hz)
 *
 * @note 变形节点（旋转/弯曲/扭曲等）会使包围盒放大，以保守估计覆盖变形后区域。
 *
 * @see estimate_bbox 完整 AABB 结果
 */
[[nodiscard]] Point3D estimate_bounds(const SdfNodePtr& root, double margin = 1.0);

/**
 * @brief SDF 树的包围盒（AABB）
 *
 * min/max 分别为最小和最大角点坐标，包围盒以原点对称时 min = -max。
 */
struct SdfBBox {
    Point3D min;  ///< 最小角点
    Point3D max;  ///< 最大角点
};

/**
 * @brief 估算 SDF 树的完整轴对齐包围盒
 *
 * 在 estimate_bounds 基础上计算对称 AABB。
 *
 * @param root SDF 树的根节点
 * @param margin 额外安全边距
 * @return AABB 包围盒
 *
 * @code{.cpp}
 * auto bbox = estimate_bbox(root, 0.5);
 * // bbox.min = (-hx-0.5, -hy-0.5, -hz-0.5)
 * // bbox.max = ( hx+0.5,  hy+0.5,  hz+0.5)
 * @endcode
 */
[[nodiscard]] SdfBBox estimate_bbox(const SdfNodePtr& root, double margin = 1.0);

} // namespace vde::sdf