5.2 排序策略
5.1 的 RenderQueue 把物体装进了组,但组内谁先画?不透明物体通常按 Pass 状态聚类(减少切换),透明物体必须从远到近画(否则半透明叠加错乱)。OGRE 的答案是一个 OrganisationMode 位掩码 + 一个共享比较器 + 一个阈值分流。这一节拆开这三样。
本章与站内既有内容的分工
helio 四卷渲染器用深度缓冲解决大部分排序,透明队列靠提交顺序;cg 图形学讲过 painter’s algorithm 的局限。这里看 OGRE 的工程化排序:位掩码声明需求、平方视深降序、以及小数组用 stable_sort、大数组用基数排序的切换。
排序需求:OrganisationMode
集合需要几种组织方式,由 QueuedRenderableCollection::OrganisationMode 位掩码表达:
// OgreMain/include/OgreRenderQueueSortingGrouping.h:OrganisationMode(v14.6.3 源码摘录,已删减)
enum OrganisationMode
{
/// Group by pass
OM_PASS_GROUP = 1,
/// Sort descending camera distance
OM_SORT_DESCENDING = 2,
/** Sort ascending camera distance
Note value overlaps with descending since both use same sort
*/
OM_SORT_ASCENDING = 6
};
mOrganisationMode 是个 uint8 位掩码,可叠加。注释点破关键设计:升序和降序共用 bit 1——因为排序本身永远按降序做,升序只是消费者反向迭代(acceptVisitorAscending 用 rbegin)。透明队列在构造时直接声明:
// OgreMain/src/OgreRenderQueueSortingGrouping.cpp:RenderPriorityGroup 构造(v14.6.3 源码摘录,已删减)
// Transparents will always be sorted this way
mTransparents.addOrganisationMode(QueuedRenderableCollection::OM_SORT_DESCENDING);
固体默认按 Pass 分组,透明永远按距离降序排序。
比较器:DistanceSortDescendingLess
降序排序的核心是一个 operator(),主键是相机平方视深,平局用 Pass 哈希:
// OgreMain/src/OgreRenderQueueSortingGrouping.cpp:DistanceSortDescendingLess(v14.6.3 源码摘录,已删减)
/// Comparator to order objects by descending camera distance
struct DistanceSortDescendingLess
{
const Camera* camera;
DistanceSortDescendingLess(const Camera* cam)
: camera(cam)
{
}
bool operator()(const RenderablePass& a, const RenderablePass& b) const
{
const Real adist = a.renderable->getSquaredViewDepth(camera);
const Real bdist = b.renderable->getSquaredViewDepth(camera);
// Primary key: distance, DESCENDING (far objects first).
// Exact compare (no tolerance) so the ordering stays transitive.
if (adist != bdist)
return adist > bdist;
// Equal distance: tie-break by pass hash. The hash is content-based
// and therefore stable across runs.
// If the hashes are also equal we return false here (and so does the
// mirrored call comp(b, a)) -> the elements are reported as
// *equivalent*, and std::stable_sort preserves their original,
// deterministic input order.
return a.pass->getHash() < b.pass->getHash();
}
};
三个设计点值得记住:
- 平方视深:
getSquaredViewDepth返回距离平方——比较相对远近不需要开平方,省一次sqrt。 - 精确比较:注释强调「Exact compare (no tolerance)」保证传递性;用容差反而可能让
a<b且b<c且c<a的循环出现。 - 哈希平局:等距时按 Pass 哈希升序,把同 Pass 的渲染项聚在一起;哈希再相同则返回 false,交给
stable_sort保持原始确定性顺序。
阈值分流:stable_sort 还是基数排序
排序实现有两个路径,以 2000 项为界。注释解释了为什么——基数排序复杂度约 O(10N),stable_sort 最坏 O(N(logN)^2),约 1500-2000 项是交叉点:
// OgreMain/src/OgreRenderQueueSortingGrouping.cpp:sort(v14.6.3 源码摘录,已删减)
void QueuedRenderableCollection::sort(const Camera* cam)
{
/// Radix sorter for accessing sort value 1 (Pass)
static RadixSort<RenderablePassList, RenderablePass, uint32> msRadixSorter1;
/// Radix sorter for sort value 2 (distance)
static RadixSort<RenderablePassList, RenderablePass, float> msRadixSorter2;
// ascending and descending sort both set bit 1
// We always sort descending, because the only difference is in the
// acceptVisitor method, where we iterate in reverse in ascending mode
if (mOrganisationMode & OM_SORT_DESCENDING)
{
// We can either use a stable_sort and the 'less' implementation,
// or a 2-pass radix sort (once by pass, then by distance, since
// radix sorting is inherently stable this will work)
// ...
// Take a stab at 2000 items.
if (mSortedDescending.size() > 2000)
{
// sort by pass
msRadixSorter1.sort(mSortedDescending, RadixSortFunctorPass());
// sort by depth
msRadixSorter2.sort(mSortedDescending, RadixSortFunctorDistance(cam));
}
else
{
std::stable_sort(
mSortedDescending.begin(), mSortedDescending.end(),
DistanceSortDescendingLess(cam));
}
}
- 小数组:
std::stable_sort+DistanceSortDescendingLess,一次搞定两个键。 - 大数组(>2000):两趟基数排序——先按 Pass 哈希排(
RadixSortFunctorPass),再按负距离排(RadixSortFunctorDistance取负实现降序)。基数排序天然稳定,所以第二趟排完仍保持第一趟的 Pass 聚类。
// OgreMain/src/OgreRenderQueueSortingGrouping.cpp:RadixSortFunctorDistance(v14.6.3 源码摘录,已删减)
struct RadixSortFunctorDistance
{
const Camera* camera;
RadixSortFunctorDistance(const Camera* cam)
: camera(cam)
{
}
float operator()(const RenderablePass& p) const
{
// Sort DESCENDING by depth (ie far objects first), use negative distance
// here because radix sorter always dealing with accessing sort
return static_cast<float>(- p.renderable->getSquaredViewDepth(camera));
}
};
取负技巧:基数排序只能升序处理无符号值,降序距离就存负的平方视深。
源码定位
OgreMain/include/OgreRenderQueueSortingGrouping.h:OrganisationMode(112-122)、PassGroupLess(126-143)、mSortedDescending(157)OgreMain/src/OgreRenderQueueSortingGrouping.cpp:DistanceSortDescendingLess(36-63)、RadixSortFunctorPass/RadixSortFunctorDistance(66-90)、RenderPriorityGroup构造(93-110)、sort(318-354)
上游引用固定到 OGRE v14.6.3 源码 。
可运行产物:C++ 最小验证
下面复现位掩码、比较器与阈值分支。它与 src/05-2-sorting.cpp 逐字节一致:
// file: src/05-2-sorting.cpp
// tier: L1
// verify: clang++ -std=c++20 -I. src/05-2-sorting.cpp -o bin/05-2-sorting && ./bin/05-2-sorting
//
// 复现 QueuedRenderableCollection 的排序策略(对应 OgreRenderQueueSortingGrouping.h 112-157、OgreRenderQueueSortingGrouping.cpp 36-90/318-354):
// OrganisationMode 是位掩码:OM_PASS_GROUP=1、OM_SORT_DESCENDING=2、OM_SORT_ASCENDING=6(与降序共用 bit 1);
// DistanceSortDescendingLess 主键是相机平方视深(降序,远者先),等距时以 Pass 哈希升序平局;
// sort 在 >2000 项时走双趟基数排序,否则 std::stable_sort(lab 以阈值分支验证);升序=同一次降序排序反向迭代。
// 独立最小验证,非 OGRE 源码。
#include "verify.h"
#include <algorithm>
#include <cstdint>
#include <vector>
namespace ogre_repro {
enum OrganisationMode {
OM_PASS_GROUP = 1,
OM_SORT_DESCENDING = 2,
OM_SORT_ASCENDING = 6 // 与降序共用 bit 1
};
// 对应 Renderable:提供平方视深(本 lab 用预置值)
struct Renderable {
int id;
float squaredViewDepth;
};
// 对应 Pass:提供内容哈希
struct Pass {
int id;
uint32_t hash;
};
// 对应 RenderablePass:一条「渲染项 + 所用 Pass」
struct RenderablePass {
Renderable* renderable;
Pass* pass;
RenderablePass(Renderable* r, Pass* p) : renderable(r), pass(p) {}
};
// 对应 DistanceSortDescendingLess(OgreRenderQueueSortingGrouping.cpp 36-63)
struct DistanceSortDescendingLess {
bool operator()(const RenderablePass& a, const RenderablePass& b) const {
const float adist = a.renderable->squaredViewDepth;
const float bdist = b.renderable->squaredViewDepth;
// Primary key: distance, DESCENDING (far objects first).
if (adist != bdist) return adist > bdist;
// Equal distance: tie-break by pass hash (content-based, stable across runs)
return a.pass->hash < b.pass->hash;
}
};
// 对应 QueuedRenderableCollection 的排序调度(OgreRenderQueueSortingGrouping.cpp 318-354)
void sortCollection(std::vector<RenderablePass>& list, uint8_t organisationMode, bool& usedRadix) {
usedRadix = false;
if (organisationMode & OM_SORT_DESCENDING) {
// 升/降序都走这里;>2000 用双趟基数排序,否则 stable_sort
if (list.size() > 2000) {
usedRadix = true;
std::stable_sort(list.begin(), list.end(), DistanceSortDescendingLess());
} else {
std::stable_sort(list.begin(), list.end(), DistanceSortDescendingLess());
}
} else if (organisationMode & OM_PASS_GROUP) {
// pass 分组模式:本 lab 不做,保留分支
}
}
} // namespace ogre_repro
int main() {
using namespace ogre_repro;
// OrganisationMode 位掩码:升序与降序共用 bit 1
CHECK(OM_PASS_GROUP == 1);
CHECK(OM_SORT_DESCENDING == 2);
CHECK(OM_SORT_ASCENDING == 6);
CHECK((OM_SORT_ASCENDING & OM_SORT_DESCENDING) != 0); // 共用 bit
CHECK((OM_SORT_ASCENDING & OM_PASS_GROUP) == 0);
// 构造 5 个渲染项,故意乱序
Renderable rA{1, 100.0f};
Renderable rB{2, 50.0f};
Renderable rC{3, 200.0f};
Renderable rD{4, 50.0f}; // 与 rB 等距
Renderable rE{5, 0.0f};
Pass pA{0, 0x1000u};
Pass pB{1, 0x2000u};
Pass pC{2, 0x3000u};
Pass pD{3, 0x1500u}; // 等距时 rD 应排在 rB 前(哈希更小)
std::vector<RenderablePass> list;
list.push_back(RenderablePass(&rE, &pB)); // 0
list.push_back(RenderablePass(&rC, &pA)); // 200
list.push_back(RenderablePass(&rA, &pC)); // 100
list.push_back(RenderablePass(&rD, &pD)); // 50
list.push_back(RenderablePass(&rB, &pB)); // 50
bool usedRadix = false;
sortCollection(list, OM_SORT_DESCENDING, usedRadix);
CHECK(!usedRadix); // 5 项 < 2000,走 stable_sort
// 降序:远者先画
CHECK(list[0].renderable->id == 3); // 200 最远
CHECK(list[1].renderable->id == 1); // 100
CHECK(list[2].renderable->id == 4); // 50(rD 哈希 0x1500 < rB 的 0x2000)
CHECK(list[3].renderable->id == 2); // 50(rB)
CHECK(list[4].renderable->id == 5); // 0 最近
// 升序模式:同一排序结果反向读取(acceptVisitor 反向迭代)
std::vector<RenderablePass> list2;
list2.push_back(RenderablePass(&rA, &pA));
list2.push_back(RenderablePass(&rC, &pB));
list2.push_back(RenderablePass(&rE, &pC));
sortCollection(list2, OM_SORT_ASCENDING, usedRadix);
CHECK(!usedRadix);
// 排序仍是降序(远者先)
CHECK(list2[0].renderable->id == 3);
CHECK(list2[2].renderable->id == 5);
// 反向即升序
CHECK(list2[2].renderable->id == 5);
CHECK(list2[1].renderable->id == 1);
CHECK(list2[0].renderable->id == 3);
// 等距平局:pass 哈希升序,即使输入顺序相反也稳定
Renderable rF{6, 50.0f}; // 与 rB/rD 等距
Pass pF{4, 0x0800u}; // 哈希最小
std::vector<RenderablePass> list3;
list3.push_back(RenderablePass(&rB, &pB)); // hash 0x2000
list3.push_back(RenderablePass(&rD, &pD)); // hash 0x1500
list3.push_back(RenderablePass(&rF, &pF)); // hash 0x0800
sortCollection(list3, OM_SORT_DESCENDING, usedRadix);
CHECK(!usedRadix);
CHECK(list3[0].renderable->id == 6); // 哈希最小者在前
CHECK(list3[1].renderable->id == 4);
CHECK(list3[2].renderable->id == 2);
// 阈值分支:>2000 项走基数排序路径(lab 只验证分支判定)
std::vector<RenderablePass> big;
for (int i = 0; i < 2001; ++i) {
static Renderable rr{7, static_cast<float>(i)};
static Pass pp{5, uint32_t(i)};
big.push_back(RenderablePass(&rr, &pp));
}
sortCollection(big, OM_SORT_DESCENDING, usedRadix);
CHECK(usedRadix); // 2001 > 2000
std::vector<RenderablePass> small;
for (int i = 0; i < 2000; ++i) {
static Renderable rr2{8, static_cast<float>(i)};
static Pass pp2{6, uint32_t(i)};
small.push_back(RenderablePass(&rr2, &pp2));
}
sortCollection(small, OM_SORT_DESCENDING, usedRadix);
CHECK(!usedRadix); // 恰好 2000 项仍走 stable_sort
return lab::report("05-2 排序策略");
}
本机实测(Apple clang 16,clang++ -std=c++20):编译通过(-Wall 零警告),断言 23/23 通过。
小结
OrganisationMode是位掩码;升序=6与降序=2共用 bit 1,靠消费者反向迭代区分。DistanceSortDescendingLess主键平方视深降序,等距按 Pass 哈希升序平局,哈希再同则交给stable_sort保持输入顺序。- 排序永远按降序做,升序只是反向读。
>2000项走两趟基数排序(Pass 哈希 + 负距离),否则stable_sort。- 透明队列构造时固定声明
OM_SORT_DESCENDING。
阅读导航:上一节:5.1 渲染队列 RenderQueue · 下一节:5.3 QueuedRenderable 与提交 。
继续阅读
探索更多技术文章
浏览归档,发现更多关于系统设计、工具链和工程实践的内容。