7.2 高度图与 LOD
7.1 讲了地形怎么组织成网格。这一节讲两块核心机制:高度从哪里来(高度图采样)和远处的地形怎么变粗糙(距离 LOD)。
本章与站内既有内容的分工
helio 四卷没有地形;cg 三卷讲过高度图的双线性采样公式。这里解析真实 OGRE 的实现细节:getHeightAtPoint 的 LOD 步长双线性插值、getHeightAtTerrainPosition 的偶/奇行三角形选面求高,以及 W. de Boer 2000 的距离 LOD 公式。
getHeightAtPoint:LOD 步长上的双线性插值
地形的原始数据是 terrainSize*terrainSize 的高度数组。getHeightAtPoint(x, y) 先按当前「最高已准备 LOD」计算步长 skip,落在步长网格点上就直接取数据,否则在四个相邻网格点间双线性插值:
// Components/Terrain/src/OgreTerrain.cpp:Terrain::getHeightAtPoint(v14.6.3 源码摘录)
float Terrain::getHeightAtPoint(uint32 x, uint32 y) const
{
// clamp
x = std::min(x, mSize - 1u);
y = std::min(y, mSize - 1u);
int highestLod = mLodManager->getHighestLodPrepared();
uint32 skip = 1 << (highestLod != -1 ? highestLod : 0);
if (x % skip == 0 && y % skip == 0)
return *getHeightData(x, y);
uint32 x1 = std::min( (x/skip) * skip , mSize - 1u );
uint32 x2 = std::min( ((x+skip) / skip) * skip, mSize - 1u );
uint32 y1 = std::min( (y/skip) * skip , mSize - 1u );
uint32 y2 = std::min( ((y+skip) / skip) * skip, mSize - 1u );
float rx = (float(x % skip) / skip);
float ry = (float(y % skip) / skip);
return *getHeightData(x1, y1) * (1.0f-rx) * (1.0f-ry)
+ *getHeightData(x2, y1) * rx * (1.0f-ry)
+ *getHeightData(x1, y2) * (1.0f-rx) * ry
+ *getHeightData(x2, y2) * rx * ry;
}
要点:
skip是当前最高 LOD 的采样步长:LOD 0 时skip=1(用全分辨率),LOD 1 时skip=2(隔一个点采样)。- 四角坐标
x1/x2/y1/y2被钳到[0, mSize-1],避免越界。 - 插值权重
rx/ry是采样点在步长单元内的归一化位置。
getHeightAtTerrainPosition:选面求解高度
getHeightAtTerrainPosition(x, y) 把 [0,1] 地形空间坐标折算进格子,然后按偶/奇行选两个三角形之一构造平面,解出高度:
// Components/Terrain/src/OgreTerrain.cpp:Terrain::getHeightAtTerrainPosition(v14.6.3 源码摘录,已删减)
float Terrain::getHeightAtTerrainPosition(Real x, Real y) const
{
// get left / bottom points (rounded down)
Real factor = (Real)mSize - 1.0f;
Real invFactor = 1.0f / factor;
uint32 startX = static_cast<uint32>(x * factor);
uint32 startY = static_cast<uint32>(y * factor);
uint32 endX = startX + 1;
uint32 endY = startY + 1;
// now get points in terrain space (effectively rounding them to boundaries)
// note that we do not clamp! We need a valid plane
Real startXTS = startX * invFactor;
Real startYTS = startY * invFactor;
Real endXTS = endX * invFactor;
Real endYTS = endY * invFactor;
// now clamp
endX = std::min(endX, mSize-1u);
endY = std::min(endY, mSize-1u);
// get parametric from start coord to next point
Real xParam = (x - startXTS) / invFactor;
Real yParam = (y - startYTS) / invFactor;
/* For even / odd tri strip rows, triangles are this shape:
even odd
3---2 3---2
| / | | \ |
0---1 0---1
*/
// Build all 4 positions in terrain space, using point-sampled height
Vector3 v0 (startXTS, startYTS, getHeightAtPoint(startX, startY));
Vector3 v1 (endXTS, startYTS, getHeightAtPoint(endX, startY));
Vector3 v2 (endXTS, endYTS, getHeightAtPoint(endX, endY));
Vector3 v3 (startXTS, endYTS, getHeightAtPoint(startX, endY));
// define a plane in terrain space
// do not normalise as the normalization factor cancels out in the final
// equation anyway
Vector4 plane;
if (startY % 2)
{
// odd row
bool secondTri = ((1.0 - yParam) > xParam);
if (secondTri)
plane = Math::calculateFaceNormalWithoutNormalize(v0, v1, v3);
else
plane = Math::calculateFaceNormalWithoutNormalize(v1, v2, v3);
}
else
{
// even row
bool secondTri = (yParam > xParam);
if (secondTri)
plane = Math::calculateFaceNormalWithoutNormalize(v0, v2, v3);
else
plane = Math::calculateFaceNormalWithoutNormalize(v0, v1, v2);
}
// Solve plane equation for z
return (-plane.x * x - plane.y * y - plane.w) / plane.z;
}
关键点:
- 三角带方向隔行翻转:偶行对角线是
/(0-2斜线),奇行是\(1-3斜线),所以选面条件不同。 - 同一个格子位置在两个三角形上高度可能不同:这就是地形网格「折痕」的来源。OGRE 用
xParam/yParam判断点落在哪半边。 - 平面不归一化(
calculateFaceNormalWithoutNormalize),因为最终方程里归一化因子会抵消。
距离 LOD:W. de Boer 2000 公式
地形每个 LOD 有一个「向下过渡」的距离:distTransition = maxHeightDelta * cFactor。cFactor 由相机与视口算出来:
// Components/Terrain/src/OgreTerrainAutoUpdateLod.cpp:TerrainAutoUpdateLodByDistance(v14.6.3 源码摘录,已删减)
// W. de Boer 2000 calculation
// A = vp_near / abs(vp_top)
// A = 1 / tan(fovy*0.5) (== 1 for fovy=45*2)
Real A = 1.0f / Math::Tan(cam->getFOVy() * 0.5f);
// T = 2 * maxPixelError / vertRes
Real maxPixelError = TerrainGlobalOptions::getSingleton().getMaxPixelError() * cam->_getLodBiasInverse();
Real T = 2.0f * maxPixelError / (Real)vp->getActualHeight();
// CFactor = A / T
Real cFactor = A / T;
A 只依赖相机 FOV,T 把「允许的最大像素误差」换算成视口比例。遍历地形四叉树时,对每个 LOD 比较距离与过渡距离:
// Components/Terrain/src/OgreTerrainAutoUpdateLod.cpp:TerrainAutoUpdateLodByDistance::traverseTreeByDistance(v14.6.3 源码摘录,已删减)
// For each LOD, the distance at which the LOD will transition *downwards*
// is given by
// distTransition = maxDelta * cFactor;
for (uint16 lodLevel = 0; lodLevel < node->getLodCount(); ++lodLevel)
{
// If we have no parent, and this is the lowest LOD, we always render
// this is the 'last resort' so to speak, we always enoucnter this last
if (lodLevel+1 == node->getLodCount() && !node->getParent())
return lodLevel + node->getBaseLod();
else
{
// Calculate or reuse transition distance
Real distTransition;
if (Math::RealEqual(cFactor, node->getLodLevel(lodLevel)->lastCFactor))
distTransition = node->getLodLevel(lodLevel)->lastTransitionDist;
else
distTransition = node->getLodLevel(lodLevel)->maxHeightDelta * cFactor;
if ((dist - holdDistance) < distTransition)
return lodLevel + node->getBaseLod();
}
}
maxHeightDelta:该 LOD 在过渡时允许的最大高度差(粗糙细节对应的误差预算)。holdDistance:相机的「驻留距离」,用于延迟 LOD 切换避免抖动。- 结果
lodLevel + baseLod直接作为目标 LOD 传给terrain->load(maxLod, ...)。 lastTransitionDist缓存:cFactor没变时复用上次计算的过渡距离,省掉重复乘法。
高度样本、插值表面与远处网格
一个地形位置需要先确定网格坐标和邻接高度,再按对应面求高度。远处渲染网格的 LOD 由屏幕误差或距离相关规则选择,采样网格和显示网格的密度可不同。
固定相机沿坡面移动,记录高度样本、所选 LOD 和相邻块的过渡。对照边缘与边界,避免用一张全景截图推断插值正确。
高度查询与地形网格更新
flowchart LR
W["世界坐标"] --> G["地形网格坐标"]
G --> H["相邻高度样本和所属三角面"]
H --> A["查询高度"]
C["相机与误差设置"] --> L["选择显示 LOD"]
L --> M["选择或更新渲染网格"]
H -.->|"同源高度数据"| M
M --> R["渲染地形"]
源码定位
Components/Terrain/src/OgreTerrain.cpp:getHeightAtPoint(1126)、getHeightAtTerrainPosition(1168)、getHeightAtWorldPosition(1235)Components/Terrain/include/OgreTerrain.h:getHeightAtPoint(797)、getHeightAtTerrainPosition(810)Components/Terrain/src/OgreTerrainAutoUpdateLod.cpp:cFactor计算(62-78)、traverseTreeByDistance(84)、distTransition = maxDelta * cFactor(126-140)Components/Terrain/src/OgreTerrainLodManager.cpp:updateToLodLevel(240)、getHighestLodPrepared(供getHeightAtPoint取 skip)
上游引用固定到 OGRE v14.6.3 源码 。
可运行产物:C++ 最小验证
下面用纯 C++ 复现高度采样与距离 LOD。它与 src/07-2-terrain-heightmap-lod.cpp 逐字节一致:
// file: src/07-2-terrain-heightmap-lod.cpp
// tier: L1
// verify: clang++ -std=c++20 -I. src/07-2-terrain-heightmap-lod.cpp -o bin/07-2-terrain-heightmap-lod && ./bin/07-2-terrain-heightmap-lod
//
// 复现地形高度采样与距离 LOD(对应 OgreTerrain.cpp 1126- 的 getHeightAtPoint/getHeightAtTerrainPosition、
// OgreTerrainAutoUpdateLod.cpp 55- 的 cFactor 与 distTransition=maxDelta*cFactor):
// getHeightAtPoint() 在 LOD 步长网格上做双线性插值(skip=2 时取相隔点);
// getHeightAtTerrainPosition() 把 (x,y) 参数折算到格子内,按偶/奇行选两个三角形之一,
// 构造平面并解出高度;
// LOD 距离过渡:A=1/tan(fovy*0.5),T=2*maxPixelError/vertRes,cFactor=A/T,
// 每个 LOD 的过渡距离 distTransition=maxDelta*cFactor,距离小于过渡距离时进入该 LOD。
// 独立最小验证,非 OGRE 源码。
#include "verify.h"
#include <algorithm>
#include <cmath>
#include <cstdint>
#include <utility>
#include <vector>
namespace ogre_repro {
// 对应 Vector3 的最小实现(仅平面计算需要)
struct V3 {
float x, y, z;
};
static V3 sub(V3 a, V3 b) { return {a.x - b.x, a.y - b.y, a.z - b.z}; }
static V3 cross(V3 a, V3 b) {
return {a.y * b.z - a.z * b.y, a.z * b.x - a.x * b.z, a.x * b.y - a.y * b.x};
}
static float dot(V3 a, V3 b) { return a.x * b.x + a.y * b.y + a.z * b.z; }
// 平面 n·p + w = 0(对应 Vector4 plane)
struct Plane {
float x, y, z, w;
};
static Plane planeFrom(const V3& v0, const V3& v1, const V3& v2) {
V3 n = cross(sub(v1, v0), sub(v2, v0));
return {n.x, n.y, n.z, -dot(n, v0)};
}
static float solveHeight(const Plane& p, float x, float y) {
return (-p.x * x - p.y * y - p.w) / p.z;
}
// 对应 Terrain(OgreTerrain.h):高度图采样与地形空间求高
class Terrain {
public:
Terrain(std::vector<float> data, uint32_t size)
: mData(std::move(data)), mSize(size) {}
void setHighestLod(int lod) { mHighestLod = lod; }
float at(uint32_t x, uint32_t y) const { return mData[x + y * mSize]; }
// 对应 Terrain::getHeightAtPoint(OgreTerrain.cpp 1126-)
float getHeightAtPoint(uint32_t x, uint32_t y) const {
x = std::min(x, mSize - 1u);
y = std::min(y, mSize - 1u);
int highestLod = mHighestLod;
uint32_t skip = 1u << (highestLod != -1 ? highestLod : 0);
if (x % skip == 0 && y % skip == 0) return at(x, y);
uint32_t x1 = std::min((x / skip) * skip, mSize - 1u);
uint32_t x2 = std::min(((x + skip) / skip) * skip, mSize - 1u);
uint32_t y1 = std::min((y / skip) * skip, mSize - 1u);
uint32_t y2 = std::min(((y + skip) / skip) * skip, mSize - 1u);
float rx = float(x % skip) / float(skip);
float ry = float(y % skip) / float(skip);
return at(x1, y1) * (1.0f - rx) * (1.0f - ry) +
at(x2, y1) * rx * (1.0f - ry) +
at(x1, y2) * (1.0f - rx) * ry +
at(x2, y2) * rx * ry;
}
// 对应 Terrain::getHeightAtTerrainPosition(OgreTerrain.cpp 1168-)
float getHeightAtTerrainPosition(float x, float y) const {
float factor = float(mSize) - 1.0f;
float invFactor = 1.0f / factor;
uint32_t startX = static_cast<uint32_t>(x * factor);
uint32_t startY = static_cast<uint32_t>(y * factor);
uint32_t endX = startX + 1;
uint32_t endY = startY + 1;
float startXTS = float(startX) * invFactor;
float startYTS = float(startY) * invFactor;
float endXTS = float(endX) * invFactor;
float endYTS = float(endY) * invFactor;
endX = std::min(endX, mSize - 1u);
endY = std::min(endY, mSize - 1u);
float xParam = (x - startXTS) / invFactor;
float yParam = (y - startYTS) / invFactor;
V3 v0{startXTS, startYTS, getHeightAtPoint(startX, startY)};
V3 v1{endXTS, startYTS, getHeightAtPoint(endX, startY)};
V3 v2{endXTS, endYTS, getHeightAtPoint(endX, endY)};
V3 v3{startXTS, endYTS, getHeightAtPoint(startX, endY)};
Plane plane;
if (startY % 2) {
// odd row
bool secondTri = ((1.0f - yParam) > xParam);
plane = secondTri ? planeFrom(v0, v1, v3) : planeFrom(v1, v2, v3);
} else {
// even row
bool secondTri = (yParam > xParam);
plane = secondTri ? planeFrom(v0, v2, v3) : planeFrom(v0, v1, v2);
}
return solveHeight(plane, x, y);
}
private:
std::vector<float> mData;
uint32_t mSize;
int mHighestLod = -1;
};
// W. de Boer 2000 的 cFactor(OgreTerrainAutoUpdateLod.cpp 55-)
float computeCFactor(float fovy, float maxPixelError, int vpHeight) {
float A = 1.0f / std::tan(fovy * 0.5f); // 1/tan(fovy*0.5)
float T = 2.0f * maxPixelError / float(vpHeight);
return A / T;
}
// 按距离选 LOD:distTransition = maxDelta * cFactor
int selectLod(float dist, float holdDistance, const std::vector<float>& maxDeltas,
float cFactor) {
for (uint16_t lodLevel = 0; lodLevel < maxDeltas.size(); ++lodLevel) {
float distTransition = maxDeltas[lodLevel] * cFactor;
if ((dist - holdDistance) < distTransition) return int(lodLevel);
}
return -1; // 无 LOD 满足
}
} // namespace ogre_repro
int main() {
using namespace ogre_repro;
// 5x5 高度图,h = 2*x*y(x 列、y 行)
std::vector<float> data;
for (uint32_t y = 0; y < 5; ++y)
for (uint32_t x = 0; x < 5; ++x) data.push_back(2.0f * float(x) * float(y));
Terrain ter(data, 5);
// getHeightAtPoint:skip=1 直接取点,越界 clamp
CHECK_EQ(ter.getHeightAtPoint(2, 2), 8.0f);
CHECK_EQ(ter.getHeightAtPoint(7, 7), 32.0f); // clamp 到 (4,4)
// getHeightAtPoint:最高 LOD=1 时 skip=2,跨点双线性插值
ter.setHighestLod(1);
CHECK(std::fabs(ter.getHeightAtPoint(1, 1) - 2.0f) < 1e-4f); // 四角 (0,0)(2,0)(0,2)(2,2)
CHECK(std::fabs(ter.getHeightAtPoint(1, 3) - 6.0f) < 1e-4f); // 四角 (0,2)(2,2)(0,4)(2,4)
ter.setHighestLod(-1);
// getHeightAtTerrainPosition:落在顶点
CHECK_EQ(ter.getHeightAtTerrainPosition(0.25f, 0.25f), 2.0f);
// 偶行 secondTri(v0,v2,v3)
CHECK(std::fabs(ter.getHeightAtTerrainPosition(0.3f, 0.2f) - 2.0f) < 1e-4f);
// 同一位置若用 firstTri(v0,v1,v2)会是 3.2,证明三角形选择有实质影响
// 偶行 firstTri(v0,v1,v2)
CHECK(std::fabs(ter.getHeightAtTerrainPosition(0.2f, 0.1f) - 0.8f) < 1e-4f);
// 奇行 secondTri(v0,v1,v3)
CHECK(std::fabs(ter.getHeightAtTerrainPosition(0.3f, 0.3f) - 2.8f) < 1e-4f);
// 平面地形:任意参数位置都返回 5.0
std::vector<float> flat(25, 5.0f);
Terrain f(flat, 5);
CHECK_EQ(f.getHeightAtTerrainPosition(0.7f, 0.6f), 5.0f);
// 右上角 (1,1) -> 顶点 (4,4)
CHECK_EQ(ter.getHeightAtTerrainPosition(1.0f, 1.0f), 32.0f);
// LOD:cFactor = A/T
float cf = computeCFactor(1.5707963f /* 90° */, 3.0f, 600);
CHECK(std::fabs(cf - 100.0f) < 1e-3f); // A=1, T=0.01
CHECK(std::fabs(0.5f * cf - 50.0f) < 1e-3f); // distTransition=0.5*100
std::vector<float> deltas{0.5f, 1.0f};
CHECK_EQ(selectLod(30.0f, 0.0f, deltas, cf), 0); // 30 < 50
CHECK_EQ(selectLod(80.0f, 20.0f, deltas, cf), 1); // 60 不 <50,但 <100
CHECK_EQ(selectLod(200.0f, 0.0f, deltas, cf), -1); // 200 超出两个过渡距离
// 像素误差翻倍 -> cFactor 减半 -> 过渡距离减半
float cf2 = computeCFactor(1.5707963f, 6.0f, 600);
CHECK(std::fabs(cf2 - 50.0f) < 1e-3f);
CHECK_EQ(selectLod(30.0f, 0.0f, deltas, cf2), 1); // 30 不 <25,但 <50
return lab::report("07-2 高度图与LOD");
}
本机实测(Apple clang 16,clang++ -std=c++20):编译通过(-Wall 零警告),断言 17/17 通过。
小结
getHeightAtPoint在 LOD 步长网格上双线性插值,skip = 1 << highestLod。getHeightAtTerrainPosition按偶/奇行选两个三角形之一,构造平面解出高度。- 距离 LOD 用 W. de Boer 2000:
cFactor = A/T,distTransition = maxHeightDelta * cFactor。 holdDistance延迟切换、lastTransitionDist缓存避免重复计算。- 目标 LOD 直接驱动
terrain->load(lod),联动地形加载(第八章)。
阅读导航:上一节:7.1 地形组件 · 下一节:7.3 地形材质 。
继续阅读
探索更多技术文章
浏览归档,发现更多关于系统设计、工具链和工程实践的内容。