一、CDLOD 的原理
CDLOD 全称是 Continuous Distance-Dependent Level of Detail,由 Filip Strugar 在 2010 年发表的一篇技术论文里提出。原文叫 “Continuous Distance-Dependent Level of Detail for Rendering Heightmaps (CDLOD)”
CDLOD 的核心想法可以用三句话概括:
- 整个地形是一棵完全四叉树。根节点覆盖全世界,每个node都有 4 个children,孩子是父节点的 1/4。叶节点对应最细的 LOD。
- 每帧根据相机距离做自顶向下的选择。如果一个节点离相机够远、它的尺度对应的细节级别就够用,那这个节点直接作为一个 patch 渲染;否则递归到children。
- 所有 patch 共享同一个固定网格(比如 65×65 顶点),把它缩放、平移到世界空间。高度在 vertex shader 里采样 heightmap 现取。
CDLOD 真正的特别之处在第四点:
- LOD 之间的过渡靠 per-vertex morph,不靠 stitching strip,也不需要 skirt。
这是 CDLOD 名字里 “Continuous” 的来源。当相机接近一个 LOD 距离带的边界时,细那一级的”多余顶点”会沿着自己的位置向粗一级网格的位置平滑插值(morph),直到完全重合。等到真正切换 LOD 的瞬间,细网格和粗网格在几何上已经一样了,所以切换不会跳。

二、我们的实现
1 | TerrainConfig.h 所有常量、辅助函数 |
2.1 四叉树数据结构
[TerrainQuadTree.h]的节点结构:
1 | struct QuadTreeNode { |
整棵树是一个 std::vector<QuadTreeNode>,孩子用 4*parent+1 硬算,跟完全二叉堆同源。好处是不用维护指针,整棵树直接memcpy。地形是规则四叉树。
1 | uint32_t firstChild = 4 * nodeIndex + 1; |
1 | 索引: 0 │ 1 2 3 4 │ 5 6 7 8 │ 9 10 11 12 │ 13 14 15 16 │ ... |
2.2 MinMax Mipmap
每个节点都要知道自己覆盖的那一块的高度范围,用于 AABB / frustum culling / LOD 。所以预处理阶段直接建一个金字塔:level 0 是原图,往上每一层把 2×2 块取 min/max 折叠一次。1025×1025 的图建 10 层,整个数据结构跟 HiZ 是同构的。
查询时根据节点像素覆盖大小算出 mipLevel = log2(pixelSize),O(1) 拿到结果。
2.3 LOD 距离表
1 | endDistance[L] = Σ baseDistance × multiplier^k (k = 0..L) |
errorFudge = 0.01 是把 morphEnd 向 morphStart 缩 1%,让 morph 在到达 LOD 边界之前略早一点完成,给浮点误差留余量。
baseDistance 怎么选。让 baseDistance 跟 leaf 节点的世界尺寸挂钩:
1 |
|
2.4 LOD 选择:递归 + 象限掩码
SelectLODRecursive 每帧跑一次:
1 | 对当前节点 N: |
注意第 5–6 步:本节点和它的孩子可以同时进入渲染列表。哪几个象限被孩子接管了,本节点对应的位就清掉,本节点只画剩下的部分。这避免了”要么全画自己、要么全交给孩子”的二选一——大多数时候视野里的 patch 都是部分细化的。
childCoverageMask的作用:
1 | bit 0 (0b0001) = BottomLeft 孩子(Child 0) |
2.5 共享网格按象限切索引
65×65 网格的索引缓冲被切成 4 段,每段对应一个 32×32 quad 的象限:
1 | mSharedMesh.quadrantIndexStart[0..3] // BL, BR, TL, TR |
绘制时,selectionMask == 0xF 一次 DrawIndexed 画完;否则按位发多个 DrawIndexed:
1 | for (int q = 0; q < 4; ++q) |
2.6 Push Constants:
1 | struct TerrainPatchPushConstants { |
constY = mEnd / (mEnd - mStart)、constZ = 1 / (mEnd - mStart) 是 Strugar 原文的 vertex shader 用的形式。CPU 端预算好了,shader 里就剩一次 fma 加一次 saturate。
2.7 Vertex Shader 里的 morph
shader morph:
1 | float ComputeMorphFactor(float3 worldPos, float displayLod, |
fracPart 在偶数 grid 上是 0,在奇数 grid 上恰好是 1/64。乘上 morphK ∈ [0,1] 就是奇数顶点向”下一级粗网格上对应的偶数顶点”靠拢。morphK = 1 的瞬间,奇数顶点完全坐到粗网格位置上,此时切换 LOD 不会有任何跳变。
vertex 主体里只需要 (isOddX || isOddZ) 的判定就够了。偶数顶点是 LOD 切换的锚点,永远不动;morph 之后必须重采一次 heightmap,否则远处地面会肉眼可见地”抖”。
三、接缝:CDLOD 不需要处理 T-junction
写到这一节才是这篇博客的真正重点。别的 LOD 实现接缝处理都是要么生成裙边(skirt)、按邻居 LOD 差生成 stitching strip之类的。CDLOD 这套实现里不需要。
3.1 T-junction 是怎么产生的
LOD 边界处,相邻两块网格的顶点密度不同:

细层在公共边上多出的”奇数格顶点”在粗层那一侧没有对应顶点。光栅化时粗层的边是直线段,而细层奇数顶点的高度多半不在这条直线上——于是它们之间漏出背景色或天空,就是裂缝。
传统 LOD 方案的处理思路无非两种:
- 几何对齐:往细层多塞顶点跟粗层对齐(stitching strip),或者直接给每块 patch 加一圈向下垂的”裙边”挡住缝。
- 数据传递:CPU 端算邻居关系,传一个 mask 给 shader,shader 把细层边缘奇数顶点”吸附”到粗层网格位置。
如果在 LOD 切换的那个距离上恰好满足:
1 | ① 细层 (LOD L): morphK_L = 1.0 ← 已完全 morph 到粗网格 |
那两层在公共边上的顶点完全重合。是数学上等于。没有 T-junction,没有裂缝。
3.2 morph
每个 patch 是一张 65×65 顶点的小网格,顶点坐标在 vertex buffer 里都是 [0, 1] 的归一化值:
1 | gridPos.x = 0, 1/64, 2/64, 3/64, ..., 63/64, 1.0对应 gridX = 0, 1, 2, 3, ..., 63, 64 |
vertex shader里把这些归一化坐标乘 patchWorldSize 加 patchCorner,变成真正的世界坐标。
把 65 个顶点按下标编号:
1 | gridX: 0 1 2 3 4 5 6 7 8 ... |
如果把这 65 个点变成下一级粗网格,保留的是偶数那些:
1 | gridX: 0 2 4 6 8 ... |
也就是说,奇数顶点是”细网格独有”的。如果我们能让奇数顶点在 morph 完成时坐到旁边某个偶数顶点的位置上,几何就跟粗网格一样了。
morph就是这件事——把每个奇数顶点向左边那个偶数顶点(gridX 小 1)平滑滑过去。
1 | float2 fracPart = frac(gridPos * gridDim * 0.5) * (2.0 / gridDim); |
gridDim = (64, 64),gridPos 是归一化 UV。我们代入具体数字看看每个顶点拿到什么 fracPart:
| gridX | gridPos.x | × 64 | × 0.5 | frac() | × (2/64) |
|---|---|---|---|---|---|
| 0 偶 | 0.0000 | 0 | 0.0 | 0.0 | 0 |
| 1 奇 | 0.0156 | 1 | 0.5 | 0.5 | 1/64 |
| 2 偶 | 0.0313 | 2 | 1.0 | 0.0 | 0 |
| 3 奇 | 0.0469 | 3 | 1.5 | 0.5 | 1/64 |
| 4 偶 | 0.0625 | 4 | 2.0 | 0.0 | 0 |
| 5 奇 | 0.0781 | 5 | 2.5 | 0.5 | 1/64 |
规律一目了然:
1 | fracPart = 0 如果是偶数顶点 |
这一行就是个”奇偶判定器”——用浮点数 frac 代替了 if (gridX % 2 == 1)。
第二行:把奇数顶点向左挪
1 | return worldXZ - fracPart * patchWorldSize * morphK; |
fracPart 在归一化空间里是 1/64(奇数)或 0(偶数)。乘上 patchWorldSize 就换算成世界单位,1/64 × patchWorldSize 恰好是一个网格 cell 的宽度。
所以这一行的几何意义:
1 | 偶数顶点:worldXZ -= 0 (不动) |
举个具体例子:cellSize = 10 米的 patch,相邻顶点世界 X 坐标是 0, 10, 20, 30, 40…
| gridX | morphK=0 | morphK=0.5 | morphK=1.0 |
|---|---|---|---|
| 0 偶 | 0 | 0 | 0 |
| 1 奇 | 10 | 5 | 0 |
| 2 偶 | 20 | 20 | 20 |
| 3 奇 | 30 | 25 | 20 |
| 4 偶 | 40 | 40 | 40 |
| 5 奇 | 50 | 45 | 40 |
morphK = 0 时是原始细网格。morphK = 1 时,1 号顶点跑到 0 的位置、3 号跑到 2 的位置、5 号跑到 4 的位置——这正好就是粗网格(顶点间距 20 米的那个)
几何上是怎么”缝合”的
morphK 在 0→1 之间渐变时:
1 | morphK = 0.0 、 |
morphK = 1.0 时奇数顶点和左边偶数顶点几何上重合,视觉上整个网格就变成了粗网格。
二维情况
X 和 Z 两个轴是独立做的(float2 fracPart)。一个顶点根据自己 gridX、gridZ 的奇偶性,落在 4 种情况之一:
1 | (偶, 偶) ── 完全不动 |
morphK = 1 时,所有奇数下标的顶点都坍缩到最近的偶偶顶点上,剩下的偶偶顶点正好构成下一级粗网格。
CPU端的距离设置
第 0 步:先想一个最简单的 LOD 方案
假设没有 morph、没有任何花样,纯粹按相机距离选 LOD:
1 | 距离 0────────────────────────────────→ |
每个 LOD 占一段距离区间。某个节点离相机多远,就用对应区间的 LOD。这些区间的边界值就是 “endDistance” 数组。
1 | endDistance[0] = LOD 0 的最远距离(再远就换 LOD 1) |
第 1 步:边界怎么排——几何级数
很自然地希望”越细的 LOD 占越窄的距离带、越粗的占越宽”。CDLOD 用的是几何级数:
1 | endDistance[L] = Σ baseDistance × multiplier^k (k = 0..L) |
比如:worldSize=4096, maxLOD=6 → baseDistance=64, multiplier=2:
1 | LOD 0 带宽 = 64 × 2^0 = 64 |
画在数轴上:
1 | 0────64────192────448────────960──────────────1984 |
这就是”距离带”。。
第 2 步:每个带末尾留一段 “morph 区”
如果就这么用,LOD 0 → LOD 1 切换的瞬间网格密度突变,肉眼可见跳变。CDLOD 的做法是:在每个 LOD 带的后半段做 morph 过渡,让细 LOD 在还没到切换点之前就开始向粗 LOD 形变。
1 | LOD L 带: 0─────────────────────endDistance[L] |
- 距离 < morphStart[L]:morphK = 0(保持原细网格)
- 距离 ∈ [morphStart[L], morphEnd[L]]:morphK 从 0 线性涨到 1
- 距离 > morphEnd[L]:morphK = 1(已经完全等于粗网格了)
morphStart 在带内的位置由 morphStartRatio 控制,默认 0.66——也就是”前 66% 不 morph,后 34% morph”。
第 3 步:morphStart 怎么算
1 | // LODRangeCalculator::CalculateRanges |
沿 morphStart 串联:
1 | prevPos=0 |
第 4 步:为什么要沿 morphStart 串联?
回想接缝消除的核心约束:
1 | endDistance[L] < morphStart[L+1] |
意思是”LOD L 切到 L+1 的那个点,L+1 自己还没开始 morph”。要满足这个,morphStart[L+1] 必须比 endDistance[L] 大一点。
1 | endDistance[0] = 64 vs morphStart[1] = 141 ✓ 141 > 64 |
每一组都安全。如果走”在每个带内算 66%”的朴素写法,morphStart[L+1] 会更靠后(因为它从 endDistance[L] 而不是 morphStart[L] 起步乘 0.66),约束更宽松——这两种都能用。为了让每个 morph 区都有接近相同的相对宽度,不会随 LOD 等级累积偏掉。
画出来看一下,串联写法长这样:
1 | 0 42 64 141 192 344 448 |
切换点(每段竖线 64、192、448)恰好落在下一级”没 morph 区”的内部。
第 5 步:errorFudge 是干嘛的
1 | constexpr float errorFudge = 0.01f; |
字面意思:把 morphEnd 往 morphStart 方向拉 1%,让它略小于 endDistance。
数字举例(带 1,mStart=141, mEnd=192):
1 | 原始 morphEnd = 192 |
差 0.5 个世界单位,看起来很小,作用却很关键。
考虑约束 ①:相机走到 endDistance[L] = 192 时,LOD L 的 morphK 必须等于 1。morphK 的公式是 (dist - mStart) / (mEnd - mStart),如果 mEnd 就等于 192:
1 | dist=192 时 morphK = (192 - 141) / (192 - 141) = 1.0 理论上对 |
但浮点运算不精确,dist 实际上可能是 191.9999 或 192.0001,morphK 算出来可能是 0.9999——只差万分之一,奇数顶点没完全坐到偶数位置上,可能就会像素的裂缝在闪。
把 mEnd 提前 1% 之后:
1 | dist=192 时 morphK = (192 - 141) / (191.49 - 141) = 1.01 → saturate 到 1.0 |
无论浮点怎么抖,到 endDistance 时 morphK 一定已经被 clamp 到 1.0。。
第 6 步:完整数据流图
最后把整个 CPU 侧距离带的设计画在一起:
1 | ┌─ baseDistance = worldSize / 2^maxLOD |
morph和选择lod无关
SelectLODRecursive 里用 endDistances 这张表的两个相邻项做判定:
1 | const bool withinCurrentRange = isCoarsest || (distance < mLodEndDistances[lodIdx]); |
- withinCurrentRange:这个节点离我够近、不在就直接 cull 掉。
- shouldRefine:这个节点是不是”近到该用更细的孩子了”?是的话递归下去。
endDistances 是真正的决定 LOD ——morphStart/End 只负责形变插值,
距离带的设计本质上是三层叠加:
- 几何级数决定每个 LOD 的覆盖范围(endDistances);
- morphStart 串联让 morph 区在切换边界之外提前完成(保证 ①+②);
- errorFudge给浮点误差留 1% 余量。
①是怎么保证的?errorFudge = 0.01 把 morphEnd[L] 缩到比 endDist[L] 略小 1%。相机到达 LOD 切换距离时,眼距已经超过 morphEnd[L],morphK_L 被 saturate 到 1.0。代码里就这一行:
1 | morphEnd[lod] = mEnd + (mStart - mEnd) * errorFudge; |
②是怎么保证的?,
3.3 visDistTooSmall:
场景:两个相邻 patch 处在不同 LOD
相机站在某个位置,让画面里出现两个相邻的 patch:
- 左边 A 是 LOD L(细),世界边长
S_L - 右边 B 是 LOD L+1(粗),世界边长
S_L+1 = 2 × S_L
它们共享一条公共边。这条边上分布着若干顶点,每个顶点都有一个确定的世界位置——它既属于 A 也属于 B。
per-vertex morph 带来的”协调问题”
这条边上的每个顶点 V 在世界里只有一份。但因为它出现在两个 patch 的 vertex shader 调用里,它会被算两次 morphK:
1 | endDist[L] < morphStart[L+1] |
visDistTooSmall 检查的是:已经被选中的 LOD L patch,它的最远点是否超过了 LOD L+1 的 morphStart。
1 | if (lodIdx + 1 < mLodLevelCount) |
为什么这会危险:LOD L 还可能和更细的 LOD L-1 共存;但它自己的远端已经进入 LOD L -> L+1 的 morph 区间。于是 LOD L-1 在对齐 LOD L,而 LOD L 又在对齐 LOD L+1,边界目标不一致,就会裂。
3.5 高差很大的地形怎么办
maxDist = sqrt(2 × S² + (ΔH/2)²) 里如果 ΔH 大到不能忽略(比如 maxHeight = 600,单 leaf 节点跨百米高差),最细那一级可能 maxDist > morphStart[1],约束又会失败。
两种解法:
- 增大
morphStartRatio(从 0.66 调到 0.80),morphStart 往前挪。 - 增大
maxLOD,让叶节点更小(同时 baseDistance 也相应变小,但比例不变,所以高度项才是真的”变小”)。
实际上单个 64×64 leaf 节点的局部高差通常远小于 maxHeight。
相关阅读
- Strugar, F. (2010). Continuous Distance-Dependent Level of Detail for Rendering Heightmaps (CDLOD).