RingBuffer 定义和功能简介
RingBuffer叫做环形缓冲区。一维的RingBuffer非常简单，是一个首尾相连的队列，在连续紧密排列的内存地址中最后一位元素的下一位指向地址偏移最小的第一位元素，从而形成闭环，如下图。
这种数据结构一般适用于事先明确了最大容量的情形，且这个容量一般是固定不变的，因为改变缓冲大小会导致运行时闭环的断裂。环形缓冲的最大意义在于能够以最小的内存IO开销获得稳定更新和读取一段数据流的能力。
对于二维RingBuffer，从数据结构的角度看是一个矩阵，它的行和列都是一维的RingBuffer，因此不论从x轴方向还是y轴方向顺序读写数据，都能形成闭环。在图形学中这种2D的RingBuffer较1D的常见，一个主要的应用点是对大世界地表数据的更新和读取：同一时刻只对一块固定大小的区域内数据感兴趣，同时不同时刻可能会向东西，南北方向移动，从而引入新区域内的数据。一个典型的案例我早前已有文章介绍，感兴趣的同学可以参阅。
一维和二维的RingBuffer不是我们今天的主题。
RingBuffer 3D的应用意义
三维的RingBuffer 从数据结构的角度看是一个立方矩阵，参考二维的情形，可以认为该立方阵中的每一行（x-轴向），每一列（z-轴向）和每一纵（y-轴向）都是一条一维的ringbuffer，它们的首尾相连形成闭环。相比于二维矩阵中的每一个格子，在三维世界中对应的是一个小小的立方体，我们不妨称其为体素（voxel），同理二维中的叫纹素（texel）。三维ringbuffer在图形学中任然有广泛的应用，比如说在运行时调取当前视锥内的<Irradiance probe>我们可以使用到它来动态的读写附近的探针数据；再比如最近挺火热的有向距离场（SDF），SDF本身是用来加速Ray Marching(Tracing)的，很多算法（诸如基于SDF的阴影计算，或者BentNormal等）需要使用到预先烘焙好的一定空间范围内的有向距离场数据。鉴于SDF巨大的数据体量，为了避免不必要的IO消耗，我们使用三维的ringbuffer来动态管理当前区域内的场数据。
技术原理 + 图示
我们先从2D剖面入手，如下图所示，这是一种3D RingBuffer的俯视图，左边是该缓冲对应的几何视图，用以观察buffer与空间的联系，以B_top点为原点，向uv正方向展开成一个矩形（红色）。而右边黄色矩形代表了缓冲内的数据视图，我拿它来描述缓冲内初始化状态下的数据分布，简便起见一个小格子对应一个数字。
移动在几何视图中的观察窗口，从红框到绿框处，对应点A到A'的偏移d。这样一来，我们就让原先的热点区域（AreaOfIntreseting）从红框移动到了绿框区域，参考右侧的数据视图，绿框内是新引入的数据，黄框中则是移动前的数据，可以看出黄绿相交的区域有公用的数据{4,5,8,9,12,13}，这些部分我们希望保持不变，我们希望利用ringbuffer的特性，将数据视图中绿色新增的数据“正确”写入到目标缓存中去（对应黄色方框）。
这种ringbuffer特性很简单，我们要做的是如下几步：
1）找到新区域（绿框）中的非重叠部分，如下面左图中的黑框区域
2）加载这个区域对应的数据，如下面右图中{16,17,18,19,20,21,22,23}这些数据对应了左图中的完整黑框区域
3）基于黑框区域在新区域（绿框）中的相对坐标，沿着方向d移动。图中可见黑框位于绿框的左侧，在沿着d方向偏移的话需要继续向左移动2个格子，同时也要向上方移动1个格子。由于ringbuffer首尾相连形成闭环，因此超过边界的部分会在另一个边界出现，对应下图可见，黑框中大一些的区域经过d偏移后来到了矩形区域的右上角，而小一些的区域经过2次首尾转换（一次从极左转极右，一次极上转极下），出现在了矩形区域的右下角。这里的矩形区域为了清晰表述，换成了红色方框，同时也暗示了原有的哪些数据需要清洗和替换。具体变换在下图右侧的数据视图中已经展现了，{16,17,18,19,20,21,22,23}这些新数据出现在了ringbuffer（黄色矩形框）内靠右侧的对应位置。
为了加深印象，我们再考虑剩余的一块新增数据块，如下图绿框中的黑色部分，将其沿着d移动后最终应当会出现在buffer的左下角位置。观察右侧的数据视图，在移动过后，数据段{24,25}被填充在了buffer中正确的位置（黄色矩形框左下角）
如此刷写数据后所得的ringbuffer数据布局看似有些凌乱，但是只要使用正确的方式采样即可得到我们想要的结果：
1）首先假设新区域（绿色框）内的数据是按照它们原来的布局排列的，如下图中间绿框中数据所示，此时的数据布局和原始数据一致
2）假如我们需要采样绿框内红色五角星所表示位置的数据，那么它的正确结果可以参考下面中图中的红色方框，其值为{19}。一般情况下使用红色五角星的uv = {0.375, 0.375}去采样即可，但是由于是经过移动的ringbuffer，实际采样时需要做一些变化。
3）计算出红五星在绿框内的uv偏移{0.375, 0.375}，并与先前获得的偏移d相加，这个过程需要我们左移2格，到达buffer的右侧，再上移一格，如下图左侧绿框内的黄色五角星所示
4）使用新位置的uv坐标{0.875, 0.625}采样变换后的ringbuffer，参考下面右侧图示，可以获得正确的输出{19}
从二维到3维其实是类推的过程，假设先前的偏移向量d是个三维的向量，具体参考下图左一。从中可见除了在uv平面上buffer的几何视图向左偏移了2格，向前偏移了1格，此外还朝向w方向的反方向偏移了1格。现在我们来观察相同buffer在uw平面上的分布，如下图左二所示，原点是立方体的min值，记为B_bottom，它的正上方是之前uv平面上显示的B_top，作为几何视图的初始化状态，我们认为一切以这个B_bottom点为原点进行计算，比如一个朝向d的偏移，如下图左三所示，很显然现在的uw平面上d需要让矩形框沿着u的反向移动2格（左移），同时沿着w的反向移动1格（下沉）。观察新产生的数据区域，如右图所示，将其整块沿d偏移后会出现在矩形区域的另一侧，且由于需要下移，因此有一部分区域（小块黑色区域）会超越w方向上的下边界，并回环到上边界附近。
由此可见三维ringbuffer和二维并无本质差异，只不过多了一个维度需要考虑而已。
我们知道，新区域（绿色框）是在经历了第一次偏移d之后获得的，那么在绿色框位置的基础上再经历一次新的偏移d'后我们再去更新ringbuffer的方式有什么需要注意的么？答案有2点：
1）需要加载的新数据来自于之前的新区域（绿框）基础上产生的偏移d'，而不是基于最初的红框区域偏移（d+d'）产生的区域。因为前者产生的新数据来自于当前偏移d'，后者则代表了历史总偏移产生的数据。
2）计算采样uv时，要使用新区域内部的局部uv + (d+d') 的方式获得，因为uv的基点对应的时上图左二中的B_bottom，也是ringbuffer初始化的起点。
工程实现简介
1.尽可能使用AABB简化问题，比如预烘焙的原数据布局，比如Ringbuffer自己的几何视图都应该以AABB的形式进行存储和计算。
2.3D的Ringbuffer增量部分提取，我分了3步来走，每一步都是基于上一步的结果，将问题拆分为若干个独立且相对简单的子问题，大体上可以归纳为：
1）先计算原始AABB和新AABB在x轴向上的凸出区域，加载数据，记录关键节点位置，随后将新AABB在x轴上的凸起区域削平；
2）在计算Z轴向的凸起，参考第一步一样是加载数据，记录节点，搞定后进一步将新AABB在z轴上的凸起部分削平；
3）最后在前两步的基础上，新的AABB应该只剩下Y轴上可能存在凸起，使用相同方式处理后即可完整且正确无重复的记录下所有新增区域的子AABB包围盒了。
此外需要注意一点，预烘焙的数据一般有专门的逻辑单元负责管理（我管它叫tileMgr），这些Tile一般在世界空间中做如下排布：
因此当经过偏移后，在管理加载数据时需要注意区分，在做凸起切割的过程中将数据区分到不同的数据源Tile中：
如上图，偏移后左侧凸起区域实际上分属于Tile(0,0)和Tile(1,0)，不可混淆在一起。
3.Blit函数详解
负责将CPU端确定的一块AABB区域进行更新。更新的本质就是讲区域对应的源数据找到，然后同步到RingBuffer中的正确位置。
下面CS代码中的_AreaOfIntresetingSize用来表示待更新区域的像素体积，Area Of Intreseting可以表示为感兴趣的区域，后面用AOI代替。 _SrcVolumeTex_MinTexelOffset则表示AOI区域位于数据源（也可以看做是一个AABB）中的什么位置，如果只是读取源数据，那么使用这个Offset足以。当涉及到将读取数据投射到Buffer时，就需要用到另一个Offset：_RingBuffer_MinTexelOffset，它表示AOI之于当前RingBuffer的几何视图的偏移，鉴于RingBuffer天生内部数据是滚动流转的，我们还需要配合参数_MovementTexelDelta来最终确定Buffer内部的目标位置，这个Delta记录了初始状态的RingBuffer几何视图位置到当前位置的偏移，当然已经量化成了像素单位。
Texture3D<half> _SrcVolumeTex;
#if defined(SHADER_API_GLES) || defined(SHADER_API_GLES30)
RWTexture2DArray<half> _RingBuffer; //TODO
#else
RWTexture3D<half> _RingBuffer;
#endif
SamplerState my_bilinear_clamp_sampler;
float3 _AreaOfIntresetingSize;
float3 _SrcVolumeTex_InvTexelSize;
float3 _SrcVolumeTex_MinTexelOffset; //pixel offset from AOI(AreaOfIntreseting) Min position to SrcSDFVolume Min position
float3 _RingBufferSize;
float3 _MovementTexelDelta;
float3 _RingBuffer_MinTexelOffset;
[numthreads(BLIT_UNIT_SIZEX, BLIT_UNIT_SIZEX, BLIT_UNIT_SIZEX)]
void RingBuffer3DBlitCS(
uint3 GroupId : SV_GroupID,
uint3 DispatchThreadId : SV_DispatchThreadID,
uint3 GroupThreadId : SV_GroupThreadID)
{
if (all(DispatchThreadId < (uint3)_AreaOfIntresetingSize))
{
float3 SrcCoordinate = float3(DispatchThreadId.xyz) + _SrcVolumeTex_MinTexelOffset + 0.5;
SrcCoordinate = SrcCoordinate * _SrcVolumeTex_InvTexelSize; //to UVW
float raw = SAMPLE_TEXTURECUBE_LOD(_SrcVolumeTex, my_bilinear_clamp_sampler, SrcCoordinate, 0).r;
int3 TarCoordinate = DispatchThreadId.xyz + (int3)_RingBuffer_MinTexelOffset + (int3)_MovementTexelDelta;
uint3 needShift1 = TarCoordinate < 0;
uint3 needShift2 = TarCoordinate >= (int3)_RingBufferSize;
TarCoordinate = TarCoordinate + (int3)_RingBufferSize * needShift1 - (int3)_RingBufferSize * needShift2;
_RingBuffer[TarCoordinate] = raw;
}
}
4.关于步进
如果你的Ringbuffer3D的体积是128 * 128 * 128，同时使用过了CS去blit数据，且一个Thread拥有[8,8,8]个线程，那么为了CS线程的对齐，建议在驱动Ringbuffer更新的逻辑中，确保每次偏移的d向量都恰好满足8*像素尺寸的整数倍。
5.tileMgr和srcProvider
可以将用于管理空间的瓦块管理器（tileMgr）和用于加载Texture3D的资源加载器抽离出去，使用接口耦合，接口参考如下:
ISourceProvider
public interface ISourceProvider
{
public UnityEngine.Object SyncLoad(string aPath);
public void AyncLoad(Action<UnityEngine.Object, bool> aCallback, string aPath);
}
ITileManager
public interface ITileManager
{
public int GetTileIndexFromOnePointInWorldSpace(Vector3 aPosWS);
public Bounds GetBoundingBoxOfGivenTileIndex(int aTileIndex);
public string GetAssetPathFromTileIndex(int aTileIndex);
}
DEMO
测试时使用了预先烘焙好的全场景SDF，数据被存储在18个资产中，每一份资产对应一张128128128尺寸的Texture3D。
运行时先将探针初始位置附近关联的SDF数据加载进来，并可视化这份3D纹理数据；随后调用脚本指令让探针沿着预设的轨迹前行，同时RingBuffer处理器负责收集统计内部托管数据的变化，及时更新，保证位于探针周围的数据处于正确的状态。
