《OGRE 3D 渲染引擎原理与架构》5.2 排序策略

透明物体要先画远的再画近的,OGRE 用 OrganisationMode 位掩码声明排序需求:OM_SORT_DESCENDING 按相机平方视深降序,DistanceSortDescendingLess 以 Pass 哈希做平局;超过 2000 项换双趟基数排序。lab 复现位掩码、比较器与阈值分支。

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));
        }
    };

取负技巧:基数排序只能升序处理无符号值,降序距离就存负的平方视深。

源码定位

上游引用固定到 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 与提交 。

继续阅读

探索更多技术文章

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

全部文章 返回首页

「books」更多文章

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