three.js SortUtils 模块radixSort 混合基数排序源码解析与 BatchedMesh 深度排序实战【免费下载链接】three.jsJavaScript 3D Library.项目地址: https://gitcode.com/GitHub_Trending/th/three.js导读SortUtils 是 three.js 官方提供的工具模块其核心导出函数radixSort实现了一种基于混合基数排序Hybrid Radix Sort的高性能排序算法专门面向无符号 32 位整数数组进行优化。它在 three.js 中最典型的应用场景是BatchedMesh批量网格的自定义排序当透明物体需要按相机深度从远到近正确混合时开发者可以借助radixSort将深度值映射到 UINT32 区间后极速排序替代传统Array.prototype.sort。读完本文你将掌握radixSort的完整 API、参数语义、底层原理并能在实际项目中复现官方示例如 webgl_mesh_batch.html里的深度排序方案。一、模块定位与导入方式SortUtils 是 three.js 的附加组件addon不属于核心构建产物必须显式导入。官方文档 Installation#Addons 明确了这类模块的用法它们位于examples/jsm/目录通过three/addons/...别名导入。标准导入语句与源码文件 examples/jsm/utils/SortUtils.js 中的three_import注释完全一致import * as SortUtils from three/addons/utils/SortUtils.js; // 或者只按需导入函数 import { radixSort } from three/addons/utils/SortUtils.js;该模块的文档页 module-SortUtils.html 记载的唯一公开 API 是静态方法radixSort。在仓库中radixSort被 examples/webgl_mesh_batch.html 与 examples/webgpu_mesh_batch.html 两个官方示例引用均作为BatchedMesh.setCustomSort()的排序内核是验证其用途最直接的证据。二、radixSort API 详解2.1 函数签名与文档定义radixSort( arr : Array.Object, opt : Object ) : undefined按官方文档 module-SortUtils.html 的说明arr— 待排序数组opt— 选项对象前置条件函数期望数组元素按无符号 32 位整数值参与排序Expects unsigned 32b integer values.。从源码 examples/jsm/utils/SortUtils.js 可以还原opt的三个可选字段选项字段默认值语义opt.auxnew arr.constructor( len )辅助缓冲区auxiliary buffer用于双缓冲交替读写传入预分配的数组可避免高频排序时反复申请内存opt.getel el恒等函数从元素中取出参与排序的键值key的回调opt.reversedfalse是否降序排序false为升序true为降序三个字段的解析逻辑如下源码 L43-L45const options opt || {}; const aux options.aux || new arr.constructor( len ); const get options.get || defaultGet;排序是原地in-place语义排序完成后结果写回arraux仅在内部作为临时缓冲不必关心其最终内容。2.2 排序方向与比较器语义radixSort并非通用比较排序它按元素取出键值后的整数大小决定顺序比较方向由opt.reversed控制。源码 L51-L110 中两个分支分别定义了compare、accumulate、recurse三个内部闭包reversed false升序compare ( a, b ) a b前缀和从左到右累加bin[ j ] bin[ j - 1 ]reversed true降序compare ( a, b ) a b前缀和从右到左累加bin[ j ] bin[ j 1 ]。因此在使用时不要试图通过get返回负数来反向因为函数内部会做 0无符号化处理负值会被解释为巨大的无符号数排序结果将不符合直觉。三、算法原理Hybrid Radix Sort 的源码级拆解radixSort的算法来源是 sciecode 的 gist 与 three.js PR #27202 中的讨论源码注释 L27-L32 与文档页均引用了这两处。它属于混合基数排序原因在于它把**基数排序radix sort与插入排序insertion sort**结合起来先按二进制位分组做基数排序当某个分桶规模小于等于 32 个元素时改用插入排序收尾以降低小规模递归的开销。3.1 常量配置源码 examples/jsm/utils/SortUtils.js 顶部的常量决定了算法结构const POWER 3; // 每次处理 3 位 const BIT_MAX 32; // 键值为 32 位无符号整数 const BIN_BITS 1 POWER; // 8每个桶按 8 个取值区分 const BIN_SIZE 1 BIN_BITS; // 256桶数量 const BIN_MAX BIN_SIZE - 1; // 255 const ITERATIONS BIT_MAX / BIN_BITS; // 10.67 → 实际循环 4 轮需要特别说明BIT_MAX / BIN_BITS在 JavaScript 中等于10.67非整除而实际处理轮数由radixSortBlock中的depth递推决定——depth从 0 递增当depth ITERATIONS - 1时返回源码 L167。结合shift ( 3 - depth ) POWERL149可见depth只在 03 之间取 4 个有效值即算法实际上只扫描了键值的高 4 组 × 3 位 12 位。这一设计是精度与性能的折中对深度排序这类应用12 位精度4096 个层级已足够区分绝大多数物体的前后关系却只需 4 轮分桶。严格来说radixSort的排序在键值高位完全相同时不保证低位序属于非稳定排序的特性被该截断放大使用时需注意这一精度边界。3.2 共享桶缓冲区的复用设计源码 L14-L23 在模块加载时一次性分配了所有桶const bins new Array( ITERATIONS ); const bins_buffer new ArrayBuffer( ( ITERATIONS 1 ) * BIN_SIZE * 4 ); let c 0; for ( let i 0; i ( ITERATIONS 1 ); i ) { bins[ i ] new Uint32Array( bins_buffer, c, BIN_SIZE ); c BIN_SIZE * 4; }这里用ArrayBuffer切分出ITERATIONS 1个Uint32Array视图每个视图 256 个桶。设计意图有两个其一桶缓冲区是模块级共享的多个radixSort调用复用同一块内存避免每次排序都 GC 分配其二每轮排序需要一对cache上一轮桶计数与bin当前轮桶计数bins[ depth ]与bins[ depth 1 ]恰好天然错位见 L152-L153。代价是同一个模块实例上的radixSort调用不能并发/嵌套执行否则共享缓冲区会被覆盖。3.3 每轮分桶的三步流水线以radixSortBlock源码 L144-L171为例每一轮depth的核心步骤是计数遍历[start, end)区间对每个元素取键值get( a[ j ] )右移shift位后与BIN_MAX取与得到 0255 的桶下标并累加计数L157-L158bin[ ( get( a[ j ] ) shift ) BIN_MAX ] ;前缀和accumulate对计数数组做前缀和得到每个桶在输出缓冲中的起始偏移升降序方向不同累加方向也不同L160 调用accumulate。回填从区间末尾倒序遍历按桶偏移把元素写回另一块缓冲b同时cache.set( bin )保存本轮计数供recurse定位下一轮的子区间L162-L165for ( let j end - 1; j start; j -- ) b[ start -- bin[ ( get( a[ j ] ) shift ) BIN_MAX ] ] a[ j ];3.4 小桶插入排序收尾recurse遍历本轮各桶计数源码 L91-L109当某个桶内元素数diff 32时递归调用radixSortBlock继续分桶否则调用insertionSortBlockL113-L142用插入排序处理这个小块。插入排序借助compare闭包保持与总体排序方向一致并且在奇数深度轮次结束时把数据从a拷贝回b保证双缓冲的数据落位一致L135-L140。四、实战在 BatchedMesh 中做透明物体深度排序radixSort在仓库中最有代表性的用法来自官方示例 webgl_mesh_batch.html其 WebGPU 版本见 webgpu_mesh_batch.html。示例通过BatchedMesh.setCustomSort()源码定义于 src/objects/BatchedMesh.js该 API 接受一个接收实例列表 相机的排序函数列表元素自带z深度字段把排序逻辑接入渲染管线import { radixSort } from three/addons/utils/SortUtils.js; function sortFunction( list ) { // 初始化选项只初始化一次后续复用 this._options this._options || { get: el el.z, aux: new Array( this.maxInstanceCount ) }; const options this._options; options.reversed this.material.transparent; // 透明物体从远到近绘制 let minZ Infinity; let maxZ - Infinity; for ( let i 0, l list.length; i l; i ) { const z list[ i ].z; if ( z maxZ ) maxZ z; if ( z minZ ) minZ z; } // 将深度映射到无符号 32 位整数区间 const depthDelta maxZ - minZ; const factor ( 2 ** 32 - 1 ) / depthDelta; // UINT32_MAX / z 范围 for ( let i 0, l list.length; i l; i ) { list[ i ].z - minZ; list[ i ].z * factor; } // 调用混合基数排序 radixSort( list, options ); }4.1 关键点一get 返回 UINT32 键值radixSort的文档与源码都强调期望无符号 32 位整数值。示例中的get: el el.z之所以能工作是因为在调用排序之前示例先把浮点深度做了归一化映射z ( z - minZ ) * ( 2^32 - 1 ) / ( maxZ - minZ )映射后的z落在[0, 2^32-1]区间成为合法的 UINT32 键。WebGPU 版示例 webgpu_mesh_batch.html 使用了更简单的映射factor ( 2 ** 32 - 1 ) / camera.far直接把深度按相机远裁剪面归一化。两版都验证了同一结论凡是把键值规约到 UINT32 区间的数据都可以套用radixSort。4.2 关键点二透明材质必须降序options.reversed this.material.transparent对应图形学中的绘制顺序规则不透明物体升序近到远即可深度缓冲会遮挡后方物体透明物体必须降序远到近绘制才能保证混合结果正确。由于reversed在sortFunction内被每次调用动态赋值同一份_options对象可以安全地服务于透明/不透明两种状态切换这也是官方示例把_options缓存在this上的原因——避免每次排序都重建get/aux把性能花在刀刃上。4.3 关键点三复用 aux 缓冲aux: new Array( this.maxInstanceCount )预分配了与最大实例数等长的辅助数组。radixSort内部通过data [ arr, aux ]源码 L47在每轮交替读写aux容量不足或频繁重建都会显著拖慢排序。在每帧排序的渲染场景中将aux缓存并在尺寸不变时复用是官方示例给出的最佳实践。4.4 接入渲染管线示例中sortFunction通过mesh.setCustomSort( api.useCustomSort ? sortFunction : null )webgl_mesh_batch.html挂载到BatchedMesh实例上。setCustomSort在 src/objects/BatchedMesh.js 中的实现只是把函数存入this.customSort并返回this支持链式调用真正的调用时机在渲染流程中BatchedMesh 会把包含实例z深度信息的列表交给该函数排序从而控制透明实例的绘制次序。需要关闭自定义排序时传入null即可恢复默认排序行为。五、适用场景与注意事项5.1 推荐用法BatchedMesh 透明实例排序官方两个 mesh_batch 示例的既定用途与setCustomSort配合最佳大数组数值排序键值天然是无符号整数、且数组规模较大数万以上时基数排序比Array.prototype.sort的O(n log n)比较排序更具缓存友好性与吞吐优势深度、优先级、LOD 等级等整型键排序凡可归一化到 UINT32 的标量键都适用。5.2 边界与限制键值必须无符号 32 位整数浮点、负数必须预先映射参考示例的归一化步骤内部get( ... ) 0会把非法值无符号化结果可能出乎意料。共享缓冲区不可重入模块级bins缓冲意味着同一页面上并发调用如 Web Worker 之外的嵌套调用会相互污染需要并行排序时应避免在同一模块实例上交叉调用。高位截断的非严格排序如前所述算法仅处理键值的高 12 位4 轮 × 3 位高位相同而低位不同的元素不保证次序属于近似深度排序对绝大多数图形场景足够但如需严格全序请评估精度需求。非稳定排序相等键值的相对顺序不保证混合场景如同时要求深度序与绘制 ID 序需自行权衡。reversed语义只影响整数大小比较方向不能通过它实现自定义比较逻辑更复杂的比较策略应在上游把键值映射好。六、源码索引内容仓库路径radixSort 实现examples/jsm/utils/SortUtils.js官方文档本文章依据docs/pages/module-SortUtils.html.mdWebGL 示例深度映射 降序透明排序examples/webgl_mesh_batch.htmlWebGPU 示例按 camera.far 归一化examples/webgpu_mesh_batch.htmlsetCustomSortAPI 定义src/objects/BatchedMesh.js结语SortUtils.radixSort是一个小而专的性能型工具它以 100 余行代码实现了混合基数排序并通过双缓冲、共享桶、小桶插入排序收尾等手段把常数因子压到极低。在 three.js 中它的正确打开方式是配合BatchedMesh.setCustomSort()做透明实例的远-近排序——先深度归一化到 UINT32再交给radixSort即可在保持绘制顺序正确的同时获得远超通用比较排序的性能。理解它的键值约束与高位截断特性是安全使用它的前提。【免费下载链接】three.jsJavaScript 3D Library.项目地址: https://gitcode.com/GitHub_Trending/th/three.js创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
