《OGRE 3D 渲染引擎原理与架构》7.2 高度图与 LOD

地形的高度来自高度图采样:getHeightAtPoint 在 LOD 步长网格上双线性插值,getHeightAtTerrainPosition 用偶/奇行三角形选面求解高度;LOD 用 W. de Boer 2000 公式,cFactor=A/T,过渡距离 distTransition=maxDelta*cFactor。lab 复现采样与距离选 LOD。

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["渲染地形"]

源码定位

上游引用固定到 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 地形材质 。

继续阅读

探索更多技术文章

浏览归档,发现更多关于系统设计、工具链和工程实践的内容。

全部文章 返回首页

「books」更多文章

  1. 《大规模分布式计算深入解析》15.3 落地:从 Neo4j 到自研图引擎
  2. 《大规模分布式计算深入解析·图计算与图数据库内核》 · 目录与学习路径(45 篇)
  3. 《大规模分布式计算深入解析》15.2 十一卷主线:从切分到图