在次世代开放世界中，广袤茂密的温带阔叶林、挺拔苍翠的针叶针叶林以及荒漠中苍凉古拙的胡杨，是赋予游戏世界生命力与地域辨识度的第一视觉载体。然而，如何在大规模生态中生成姿态各异、符合植物生长生物学规律且绝不机械重复的树木三维资产，是计算机图形学与程序化内容生成（PCG）长盛不衰的核心课题。

传统的基于形式文法的L-System（林登迈耶系统），虽然能够借助字符串递归替换生成精巧的分形几何，但在大尺度树木模拟上存在致命缺陷：

• 缺乏对三维物理空间的感知，枝条经常发生严重的自身交叉与空间穿模；
• 无法表达树冠为了争夺阳光而自适应填充空间空隙的“向光性（Phototropism）”与竞争行为；
• 很难直接受美术师给出的宏观体量外形轮廓约束。

为了在严格的美术指导（Art Direction）下生成具备真实植物竞争与空间填充特性的树木拓扑，现代游戏工业界广泛采用了由 Runions 等学者提出的空间殖民算法（Space Colonization Algorithm）。本文将深入拆解空间殖民算法的生物学竞争数学模型、达西分枝截面法则，并给出工业级 C++ 骨架生成与网格化实战方案。

一、生物学空间竞争与空间殖民算法数学模型

空间殖民算法的核心哲学是：树枝的生长不是盲目的，而是被空间中离散分布的“虚构光能养分吸引子（Attractor Points）”所牵引诱导的竞争性过程。

1.1 空间吸引子与树冠流形包络（Crown Envelope）

算法的第一步是在三维空间中撒下大量代表光照与生长空间的离散点（吸引子集合 $\mathbf{A} = {A_1, A_2, \dots, A_M}$）：

• 美术师可以定义一个宏观的三维封闭网格（如椭球形代表橡树、圆锥形代表冷杉、伞形代表金合欢）；
• 在该封闭网格流形内部，通过泊松圆盘采样（Poisson Disk Sampling）均匀播撒数千个吸引子；
• 树木的根部节点从地面开始向上发芽。

1.2 感知半径与绝杀距离（Influence Radius & Kill Distance）

算法定义两个极其核心的物理距离门限：

1. 影响半径（Influence Radius $D_{influence}$）：如果某个吸引子 $A_j$ 与树枝节点 $N_i$ 的欧氏距离小于 $D_{influence}$，该吸引子被激活，开始向该树枝节点施加空间牵引力；
2. 绝杀距离（Kill Distance $D_{kill}$，通常 $D_{kill} \ll D_{influence}$）：当新生长的树枝末梢逼近某个吸引子到 $D_{kill}$ 以内时，表明该区域的光照与养分已被该枝干彻底“吸干榨尽”。该吸引子被从空间中永久抹除销毁！

二、枝干向量合成与达西分枝截面积法则

在每一个迭代生长轮次（Growth Iteration），所有未被杀死的空间吸引子分别寻找距离自己最近的树枝节点。

2.1 归一化生长矢量合成

对于树干上的任意节点 $N_i$，假设当前受到 $K$ 个吸引子 ${A_1, A_2, \dots, A_K}$ 的共同牵引：

• 每个吸引子贡献一个单位牵引方向向量：$\vec{d}_{ij} = \frac{A_j - N_i}{|A_j - N_i|}$；
• 节点 $N_i$ 的最终新生生长方向为所有牵引矢量的平均归一化向量，并附带微小的向上向光性偏置（Phototropism Vector）：

$$\vec{D}{growth} = \text{Normalize}\left( \frac{1}{K} \sum{j=1}^{K} \vec{d}{ij} + w{light} \cdot (0, 1, 0) \right)$$

沿该方向向前推进一个固定步长 $L_{step}$，生成一个新的次级树枝节点。这保证了枝条天然地向着未被占据的空旷有光空间伸展，彻底杜绝了分支之间的自身穿模。

2.2 达西-达芬奇分枝法则（Leonardo da Vinci's Rule of Trees）

文艺复兴时期的达芬奇在观察树木时发现了一条伟大的流体力学几何定律：一棵树在任意高度处所有分枝的横截面积总和，精确等于它们母干的横截面积。
在现代流体力学中，这直接对应于树木维管束水分传输的守恒连续性方程：

$$R_{parent}^2 = \sum_{k} R_{child_k}^2 \implies R_{parent} = \left( \sum_{k} R_{child_k}^n \right)^{1/n}$$

通常指数 $n$ 取值在 $2.0$ 到 $2.5$ 之间。我们在骨架生成完毕后，从末梢枝杈（半径固定为嫩枝微小初值，如 0.02 米）开始，自底向上执行一次逆向拓扑递归遍历，依次反算每一个父级枝干乃至主干根部的物理半径，使得树木天然展现出根部苍劲粗壮、逐级平滑收缩过渡的完美自然形态。

三、工业级 C++ 空间殖民树木生长生成器核心实现

下面展示在离线资产烘焙或运行时 PCG 关卡生成中落地的空间殖民算法核心 C++ 代码。代码涵盖了吸引子采样、最近邻归属判定、枝干前向迭代生长以及达芬奇半径逆向解算。

#include <iostream> #include <vector> #include <cmath> #include <algorithm> #include <memory> struct Vector3 { float x{0}, y{0}, z{0}; Vector3 operator+(const Vector3& o) const { return {x + o.x, y + o.y, z + o.z}; } Vector3 operator-(const Vector3& o) const { return {x - o.x, y - o.y, z - o.z}; } Vector3 operator*(float s) const { return {x * s, y * s, z * s}; } float LengthSq() const { return x * x + y * y + z * z; } float Length() const { return std::sqrt(LengthSq()); } Vector3 Normalized() const { float len = Length(); return len > 1e-5f ? Vector3{x / len, y / len, z / len} : Vector3{0, 1, 0}; } }; // 1. 树枝骨架节点 struct BranchNode { int nodeID; int parentID{-1}; Vector3 position; Vector3 growthDirection{0, 1, 0}; float radius{0.05f}; int growingAttractorCount{0}; Vector3 accumulatedAttractorDir{0, 0, 0}; }; // 2. 空间养分吸引子 struct AttractorPoint { Vector3 position; bool active{true}; }; class SpaceColonizationTreeGenerator { public: static constexpr float INFLUENCE_RADIUS = 3.5f; // 吸引影响半径 static constexpr float KILL_DISTANCE = 0.6f; // 绝杀养分耗尽距离 static constexpr float STEP_LENGTH = 0.4f; // 单步生长距离 void Initialize(const std::vector<Vector3>& crownAttractors, const Vector3& rootPos) { m_attractors.clear(); for (const auto& p : crownAttractors) { m_attractors.push_back({p, true}); } m_nodes.clear(); BranchNode root; root.nodeID = 0; root.parentID = -1; root.position = rootPos; m_nodes.push_back(root); } // 执行固定步数生长演化 void Grow(int maxIterations) { for (int iter = 0; iter < maxIterations; ++iter) { // 1. 重置所有节点的牵引状态 for (auto& node : m_nodes) { node.growingAttractorCount = 0; node.accumulatedAttractorDir = {0, 0, 0}; } // 2. 吸引子向最近的活跃节点施加牵引力 bool anyAttractorActive = false; for (auto& attr : m_attractors) { if (!attr.active) continue; anyAttractorActive = true; int closestNodeIndex = -1; float minDistSq = INFLUENCE_RADIUS * INFLUENCE_RADIUS; for (size_t i = 0; i < m_nodes.size(); ++i) { float dSq = (attr.position - m_nodes[i].position).LengthSq(); if (dSq < minDistSq) { minDistSq = dSq; closestNodeIndex = static_cast<int>(i); } } if (closestNodeIndex != -1) { Vector3 pullDir = (attr.position - m_nodes[closestNodeIndex].position).Normalized(); m_nodes[closestNodeIndex].accumulatedAttractorDir = m_nodes[closestNodeIndex].accumulatedAttractorDir + pullDir; m_nodes[closestNodeIndex].growingAttractorCount++; } } if (!anyAttractorActive) break; // 养分耗尽，生长停止 // 3. 为受到牵引的节点派生新子枝节 size_t currentTreeSize = m_nodes.size(); for (size_t i = 0; i < currentTreeSize; ++i) { if (m_nodes[i].growingAttractorCount > 0) { Vector3 avgDir = (m_nodes[i].accumulatedAttractorDir * (1.0f / m_nodes[i].growingAttractorCount)).Normalized(); // 叠加向光性与前向微动量 Vector3 finalGrowthDir = (avgDir * 0.85f + Vector3{0, 1, 0} * 0.15f).Normalized(); BranchNode child; child.nodeID = static_cast<int>(m_nodes.size()); child.parentID = m_nodes[i].nodeID; child.position = m_nodes[i].position + finalGrowthDir * STEP_LENGTH; child.growthDirection = finalGrowthDir; m_nodes.push_back(child); } } // 4. 绝杀阶段：若吸引子与任意枝节过近，判定养分吸收完毕并杀死 float killDistSq = KILL_DISTANCE * KILL_DISTANCE; for (auto& attr : m_attractors) { if (!attr.active) continue; for (const auto& node : m_nodes) { if ((attr.position - node.position).LengthSq() < killDistSq) { attr.active = false; break; } } } } // 5. 达西分枝法则：自顶向下逆向递归解算物理半径 SolveBranchRadii(); std::cout << "[空间殖民算法] 树木骨架生长完成！生成枝干节点数: " << m_nodes.size() << "\n"; } private: void SolveBranchRadii() { // 从最末端的子节点向根节点逆向扫描 for (int i = static_cast<int>(m_nodes.size()) - 1; i >= 0; --i) { if (m_nodes[i].parentID >= 0) { int pID = m_nodes[i].parentID; // R_parent^2 = R_parent^2 + R_child^2 m_nodes[pID].radius = std::sqrt(m_nodes[pID].radius * m_nodes[pID].radius + m_nodes[i].radius * m_nodes[i].radius); } } } std::vector<AttractorPoint> m_attractors; std::vector<BranchNode> m_nodes; };

四、多边形蒙皮网格化与四元数切线框架（Skinning & Mesh Extrusion）

得到了三维骨架节点与各级半径后，如何将其蒙皮挤出为三维渲染网格？

1. 平行输运坐标框架（Parallel Transport Frames / Bishop Frame）：沿着连续弯曲的枝干前向滑动时，传统的欧拉角会遭遇万向节死锁与突发扭转。我们采用 Bishop 正交基底，仅通过四元数极小旋转（Minimal Rotation Quaternion）平滑传递局部正交基底 $(U, V)$；
2. 多边形截面圆环挤出：在每个骨架节点处生成一个拥有 $N$ 个顶点（如 8 边形）的圆环截面，根据该节点的达西半径向外膨胀：

$$\mathbf{P}{ring}(k) = \mathbf{P}{node} + R_{node} \cdot \left( \cos\left(\frac{2\pi k}{N}\right) \cdot \mathbf{U} + \sin\left(\frac{2\pi k}{N}\right) \cdot \mathbf{V} \right)$$

3. 分枝节点布尔平滑过渡（Branch Junction Blending）：在分叉三叉路口处，采用有限元隐式表面膨胀（Implicit Skinning），消除机械插接带来的硬生生折角。

五、生态多样性与工业化生产力跃迁

空间殖民算法为开放世界森林的大规模程序化量产带来了质的飞跃：

• 美术可控性（Art Directability）：概念设计师只需雕刻几个不同剪影的低模多边形作为树冠包络体（如苍劲的盘龙松外壳），算法即可在包络体内部自组织生长出完全贴合该剪影的真实树木；
• 障碍避让与悬崖自适应生根：吸引子只播撒在空气中，若树旁有巨石或城墙，由于巨石内部没有吸引子，树木枝丫会自动向巨石背侧绕道避让生长，呈现出极其逼真的“依山顺势”自然生态感；
• 无缝衔接风场顶点色：在生成网格的同时，根据骨架树状层级深度自动烘焙我们此前在 T1/T4 专栏中详述的顶点风场权重（Trunk/Branch/Leaf Masks）。

通过用严密的空间引力竞争取代死板的形式语法，以达芬奇分枝法则守住流体力学守恒底线，空间殖民算法让每一株虚拟森林中的树木，都在争夺阳光与大地的奋斗中，长出了独一无二的壮丽风骨。