在次世代开放世界中广袤茂密的温带阔叶林、挺拔苍翠的针叶针叶林以及荒漠中苍凉古拙的胡杨是赋予游戏世界生命力与地域辨识度的第一视觉载体。然而如何在大规模生态中生成姿态各异、符合植物生长生物学规律且绝不机械重复的树木三维资产是计算机图形学与程序化内容生成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算法定义两个极其核心的物理距离门限影响半径Influence Radius $D_{influence}$如果某个吸引子 $A_j$ 与树枝节点 $N_i$ 的欧氏距离小于 $D_{influence}$该吸引子被激活开始向该树枝节点施加空间牵引力绝杀距离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{j1}^{K} \vec{d}{ij} w{light} \cdot (0, 1, 0) \right)$$沿该方向向前推进一个固定步长 $L_{step}$生成一个新的次级树枝节点。这保证了枝条天然地向着未被占据的空旷有光空间伸展彻底杜绝了分支之间的自身穿模。2.2 达西-达芬奇分枝法则Leonardo da Vincis 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::vectorVector3 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_castint(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_castint(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_castint(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::vectorAttractorPoint m_attractors; std::vectorBranchNode m_nodes; };四、多边形蒙皮网格化与四元数切线框架Skinning Mesh Extrusion得到了三维骨架节点与各级半径后如何将其蒙皮挤出为三维渲染网格平行输运坐标框架Parallel Transport Frames / Bishop Frame沿着连续弯曲的枝干前向滑动时传统的欧拉角会遭遇万向节死锁与突发扭转。我们采用 Bishop 正交基底仅通过四元数极小旋转Minimal Rotation Quaternion平滑传递局部正交基底 $(U, V)$多边形截面圆环挤出在每个骨架节点处生成一个拥有 $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)$$分枝节点布尔平滑过渡Branch Junction Blending在分叉三叉路口处采用有限元隐式表面膨胀Implicit Skinning消除机械插接带来的硬生生折角。五、生态多样性与工业化生产力跃迁空间殖民算法为开放世界森林的大规模程序化量产带来了质的飞跃美术可控性Art Directability概念设计师只需雕刻几个不同剪影的低模多边形作为树冠包络体如苍劲的盘龙松外壳算法即可在包络体内部自组织生长出完全贴合该剪影的真实树木障碍避让与悬崖自适应生根吸引子只播撒在空气中若树旁有巨石或城墙由于巨石内部没有吸引子树木枝丫会自动向巨石背侧绕道避让生长呈现出极其逼真的“依山顺势”自然生态感无缝衔接风场顶点色在生成网格的同时根据骨架树状层级深度自动烘焙我们此前在 T1/T4 专栏中详述的顶点风场权重Trunk/Branch/Leaf Masks。通过用严密的空间引力竞争取代死板的形式语法以达芬奇分枝法则守住流体力学守恒底线空间殖民算法让每一株虚拟森林中的树木都在争夺阳光与大地的奋斗中长出了独一无二的壮丽风骨。