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 后台资源队列 。
继续阅读
探索更多技术文章
浏览归档,发现更多关于系统设计、工具链和工程实践的内容。