《OGRE 3D 渲染引擎原理与架构》9.3 合批与顶点缓存

9.3 讲顶点缓存优化。Triangle::sharesEdge 用反向边匹配共享边;IndexData::optimiseVertexCacheTriList 贪心重排三角形;VertexCacheProfiler 用 FIFO 环形缓存统计 ACMR。lab 复现共享边判定、贪心重排与 ACMR 下降,12 项断言。

9.3 合批与顶点缓存

GPU 顶点数据是经「顶点缓存」(post-transform cache)喂给片元阶段的:三角形引用的顶点若是刚处理过的,就能直接命中缓存,省一次顶点变换。命中率取决于索引顺序——相邻三角形最好共享边。OGRE 在 OgreVertexIndexData.cpp 里提供两件工具:Triangle::sharesEdge 判定两个三角形是否共享一条反向边,IndexData::optimiseVertexCacheTriList 按共享边贪心重排索引,再用 VertexCacheProfiler 统计优化前后的「平均缓存缺失率」ACMR(miss 数除以三角形数)。

本章与站内既有内容的分工

9.2 通过渲染状态排序减少 CPU 侧切换;本节把目光移到索引数据本身:同样的顶点集,重排三角形顺序就能提升 GPU 顶点缓存命中率。lab 复现共享边匹配与贪心重排,并用 FIFO 环形缓存计算 ACMR。

sharesEdge:按反向边匹配共享边

Triangle 是一个三元组 a,b,c。判定两个三角形共享边时,源码不比较同向边而是反向边——两个三角形沿公共边方向相反(A 的 a->b 对 B 的 b->a)。一个四边形条带里相邻三角形正好满足这种关系,九种组合把三条边各自的正反方向都枚举出来:

// OgreMain/src/OgreVertexIndexData.cpp:Triangle::sharesEdge(v14.6.3 源码摘录,已删减)
        inline bool sharesEdge(const Triangle& t) const
        {
            return( (a == t.a && b == t.c) ||
                    (a == t.b && b == t.a) ||
                    (a == t.c && b == t.b) ||
                    (b == t.a && c == t.c) ||
                    (b == t.b && c == t.a) ||
                    (b == t.c && c == t.b) ||
                    (c == t.a && a == t.c) ||
                    (c == t.b && a == t.a) ||
                    (c == t.c && a == t.b) );
        }

lab 里用 tris[0].sharesEdge(tris[2]) 验证四边形条带中 t0=(0,1,4) 与 t1=(1,5,4) 共享边 1-4(注意 t1 的 b=5、c=4,边的方向与 t0 的 a->b=1->4 相反,走 a == t.b && b == t.a 这一支)。

optimiseVertexCacheTriList:贪心重排

重排算法维护一个 visited[] 数组与「起始三角形」指针:每个未访问三角形入列后,扫描剩余三角形找第一个与它共享边的,作为下一个;找不到就跳到下一个未访问的。这样共享边三角形尽量相邻,形成条带化访问序列:

// OgreMain/src/OgreVertexIndexData.cpp:IndexData::optimiseVertexCacheTriList(v14.6.3 源码摘录,已删减)
        // sort triangles based on shared edges
        uint32 *destlist = OGRE_ALLOC_T(uint32, nTriangles, MEMCATEGORY_GEOMETRY);
        unsigned char *visited = OGRE_ALLOC_T(unsigned char, nTriangles, MEMCATEGORY_GEOMETRY);

        for (i = 0; i < nTriangles; ++i) visited[i] = 0;

        uint32 start = 0, ti = 0, destcount = 0;

        bool found = false;
        for (i = 0; i < nTriangles; ++i)
        {
            if (found)
                found = false;
            else
            {
                while (visited[start++]);
                ti = start - 1;
            }

            destlist[destcount++] = ti;
            visited[ti] = 1;

            for (j = start; j < nTriangles; ++j)
            {
                if (visited[j]) continue;
                
                if (triangles[ti].sharesEdge(triangles[j]))
                {
                    found = true;
                    ti = static_cast<uint32>(j);
                    break;
                }
            }
        }

lab 的 optimiseTriList 复现同一逻辑(std::vector<uint8_t> visited + destlist),并断言重排不丢三角形、顶点集合不变。

VertexCacheProfiler:FIFO 环形缓存与 ACMR

VertexCacheProfiler 维护一个环形缓存:每个索引先线性扫缓存找命中(hit++),未命中(miss++)就写入 tail 位置并推进。buffersize 最多涨到 size(默认 16 槽)。profile() 把整个索引缓冲过一遍,triangles += numIndexes/3,ACMR 即 miss / triangles:

// OgreMain/src/OgreVertexIndexData.cpp:VertexCacheProfiler::inCache(v14.6.3 源码摘录,已删减)
    bool VertexCacheProfiler::inCache(unsigned int index)
    {
        for (unsigned int i = 0; i < buffersize; ++i)
        {
            if (index == cache[i])
            {
                hit++;
                return true;
            }
        }

        miss++;
        cache[tail++] = index;
        tail %= size;

        if (buffersize < size) buffersize++;

        return false;
    }

以及默认缓存大小与平均缺失率:

// OgreMain/include/OgreVertexIndexData.h:VertexCacheProfiler(v14.6.3 源码摘录,已删减)
            VertexCacheProfiler(unsigned int cachesize = 16)
                : size ( cachesize ), tail (0), buffersize (0), hit (0), miss (0), triangles(0)
            {
                cache = OGRE_ALLOC_T(uint32, size, MEMCATEGORY_GEOMETRY);
            }
            void reset() { hit = 0; miss = 0; tail = 0; buffersize = 0; triangles = 0; }
            void flush() { tail = 0; buffersize = 0; }
            unsigned int getHits() { return hit; }
            unsigned int getMisses() { return miss; }
            unsigned int getSize() { return size; }
            float getAvgCacheMissRatio() { return (float)miss / triangles; }
            unsigned int size;
            uint32 *cache;
            unsigned int tail, buffersize;
            unsigned int hit, miss;
            uint32 triangles;

lab 用 4 槽缓存(VertexCacheProfilerRepro(4))放大小缓存局部性:四边形条带 6 个三角形乱序输入时 ACMR 偏高,贪心重排后 avgCacheMissRatio() 下降,同时命中数上升——这就是顶点缓存优化的量化验证。

源码定位

  • OgreMain/src/OgreVertexIndexData.cpp:Triangle::sharesEdge(839-850 行)
  • OgreMain/src/OgreVertexIndexData.cpp:IndexData::optimiseVertexCacheTriList(902-1008 行)
  • OgreMain/src/OgreVertexIndexData.cpp:VertexCacheProfiler::profile/inCache(1011-1051 行)
  • OgreMain/include/OgreVertexIndexData.h:VertexCacheProfiler(286-319 行)

上游引用固定到 OGRE v14.6.3 源码 。

可运行产物:C++ 最小验证

Triangle 按反向边判共享,optimiseTriList 贪心重排,VertexCacheProfilerRepro(4) 用 4 槽 FIFO 缓存统计优化前后的 ACMR 与命中。它与 src/09-3-batching-vertex-cache.cpp 逐字节一致:

// file: src/09-3-batching-vertex-cache.cpp
// tier: L1
// verify: clang++ -std=c++20 -I. src/09-3-batching-vertex-cache.cpp -o bin/09-3-batching-vertex-cache && ./bin/09-3-batching-vertex-cache
//
// 复现顶点缓存优化(对应 OgreMain/src/OgreVertexIndexData.cpp 902-1008 的
//   IndexData::optimiseVertexCacheTriList 与 1011-1051 的 VertexCacheProfiler):
//   Triangle::sharesEdge 按"反向边"匹配共享边;优化按共享边贪心重排三角形;
//   VertexCacheProfiler 用 FIFO 环形缓存统计命中/未命中并给出 ACMR。
// 独立最小验证,非 OGRE 源码。
#include "verify.h"

#include <cstdint>
#include <set>
#include <vector>

namespace ogre_repro {

// 对应 OgreVertexIndexData.cpp 812-850 的 Triangle(sharesEdge 用反向边匹配)
struct Triangle {
    uint32_t a, b, c;

    bool sharesEdge(const Triangle& t) const {
        return ((a == t.a && b == t.c) || (a == t.b && b == t.a) || (a == t.c && b == t.b) ||
                (b == t.a && c == t.c) || (b == t.b && c == t.a) || (b == t.c && c == t.b) ||
                (c == t.a && a == t.c) || (c == t.b && a == t.a) || (c == t.c && a == t.b));
    }
};

// 对应 OgreVertexIndexData.cpp 286-322 的 VertexCacheProfiler(FIFO 环形缓存)
class VertexCacheProfilerRepro {
public:
    explicit VertexCacheProfilerRepro(uint32_t cachesize = 16)
        : mSize(cachesize), mTail(0), mBufferSize(0), mHit(0), mMiss(0), mTriangles(0) {
        mCache.assign(mSize, 0);
    }

    void reset() {
        mHit = 0;
        mMiss = 0;
        mTail = 0;
        mBufferSize = 0;
        mTriangles = 0;
    }

    // 对应 VertexCacheProfiler::profile:逐索引调 inCache
    void profile(const std::vector<uint32_t>& indexes) {
        for (uint32_t idx : indexes)
            inCache(idx);
        mTriangles += indexes.size() / 3;
    }

    // 对应 VertexCacheProfiler::inCache
    bool inCache(uint32_t index) {
        for (uint32_t i = 0; i < mBufferSize; ++i) {
            if (index == mCache[i]) {
                ++mHit;
                return true;
            }
        }
        ++mMiss;
        mCache[mTail++] = index;
        mTail %= mSize;
        if (mBufferSize < mSize)
            ++mBufferSize;
        return false;
    }

    float avgCacheMissRatio() const {
        return mTriangles == 0 ? 0.0f : static_cast<float>(mMiss) / static_cast<float>(mTriangles);
    }
    uint32_t getHits() const { return mHit; }
    uint32_t getMisses() const { return mMiss; }

private:
    uint32_t mSize;
    std::vector<uint32_t> mCache;
    uint32_t mTail;
    uint32_t mBufferSize;
    uint32_t mHit;
    uint32_t mMiss;
    uint32_t mTriangles;
};

// 对应 IndexData::optimiseVertexCacheTriList 925-958 的贪心重排:
// 从起始三角形出发,逐个找共享边的下一个三角形
std::vector<Triangle> optimiseTriList(std::vector<Triangle> input) {
    const size_t n = input.size();
    std::vector<uint8_t> visited(n, 0);
    std::vector<uint32_t> destlist(n);
    uint32_t start = 0;
    uint32_t ti = 0;
    bool found = false;

    for (size_t i = 0; i < n; ++i) {
        if (found) {
            found = false;
        } else {
            while (visited[start])
                ++start;
            ti = start;
        }
        destlist[i] = ti;
        visited[ti] = 1;

        for (size_t j = 0; j < n; ++j) {
            if (visited[j])
                continue;
            if (input[ti].sharesEdge(input[j])) {
                found = true;
                ti = static_cast<uint32_t>(j);
                break;
            }
        }
    }

    std::vector<Triangle> out;
    out.reserve(n);
    for (uint32_t o : destlist)
        out.push_back(input[o]);
    return out;
}

std::vector<uint32_t> flatten(const std::vector<Triangle>& tris) {
    std::vector<uint32_t> idx;
    idx.reserve(tris.size() * 3);
    for (const Triangle& t : tris) {
        idx.push_back(t.a);
        idx.push_back(t.b);
        idx.push_back(t.c);
    }
    return idx;
}

}  // namespace ogre_repro

int main() {
    using namespace ogre_repro;

    // 四边形条带 2 行 4 列:顶点 0..7,三角形共享边
    // 乱序给出(t0,t3,t1,t4,t2,t5)
    std::vector<Triangle> tris;
    tris.push_back({0, 1, 4});   // t0
    tris.push_back({2, 6, 5});   // t3
    tris.push_back({1, 5, 4});   // t1
    tris.push_back({2, 3, 6});   // t4
    tris.push_back({1, 2, 5});   // t2
    tris.push_back({3, 7, 6});   // t5

    // sharesEdge 用反向边匹配:t0=(0,1,4) 与 t1=(1,5,4) 共享边 1-4
    CHECK(tris[0].sharesEdge(tris[2]));
    CHECK(tris[1].sharesEdge(tris[3]));
    // 不共享边的两个三角形
    CHECK(!tris[0].sharesEdge(tris[1]));
    CHECK(!tris[0].sharesEdge(tris[5]));

    std::vector<Triangle> opt = optimiseTriList(tris);
    CHECK_EQ(opt.size(), tris.size());  // 重排不丢三角形

    // 顶点集合不变
    std::set<uint32_t> before, after;
    for (const Triangle& t : tris) {
        before.insert(t.a);
        before.insert(t.b);
        before.insert(t.c);
    }
    for (const Triangle& t : opt) {
        after.insert(t.a);
        after.insert(t.b);
        after.insert(t.c);
    }
    CHECK_EQ(before.size(), 8u);
    CHECK(before == after);

    VertexCacheProfilerRepro p1(4), p2(4);  // 小缓存更能体现条带局部性
    p1.profile(flatten(tris));   // 优化前
    p2.profile(flatten(opt));    // 优化后
    CHECK(p2.avgCacheMissRatio() < p1.avgCacheMissRatio());
    CHECK(p1.getMisses() > 0);
    // 缓存是 16 槽 FIFO;三角形条带共享顶点后命中率必然改善
    CHECK(p2.getHits() > 0);

    // 空输入不会除零
    VertexCacheProfilerRepro p3;
    p3.profile({});
    CHECK_EQ(p3.getMisses(), 0u);
    CHECK(p3.avgCacheMissRatio() == 0.0f);

    return lab::report("9.3 合批与顶点缓存");
}

本机实测(Apple clang 16,clang++ -std=c++20 -Wall):编译通过(零警告),断言 12/12 通过。

小结

  • 顶点缓存命中的前提是相邻三角形共享顶点,sharesEdge 用反向边匹配判定共享边。
  • 贪心重排维护 visited[],从每个三角形出发找下一个共享边三角形,形成条带化访问序列。
  • VertexCacheProfiler 是 FIFO 环形缓存,miss / triangles 即 ACMR,值越低顶点缓存效率越高。
  • 优化只重排索引顺序,不增删顶点,顶点集合保持不变。
  • 小缓存(lab 中 4 槽)放大了条带局部性的收益,ACMR 下降与命中数上升同时被验证。

阅读导航:上一节:9.2 渲染状态切换优化 · 下一节:10.1 后台资源队列 。

继续阅读

探索更多技术文章

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

全部文章 返回首页

「books」更多文章

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