- 书接上回
图形学中的常用数据结构
- 本篇文章的内容受到一篇高性能并行数据结构的文献启发,介绍一下一些常见的数据结构,自己也是工作之余肝了demo做了一些动画,由于用了一些工作的组件,不太好开源,等有时间了写成taichi
Uniform Grid(网格)
- 将三维空间区域(domain),使用尺寸一致立方体(cell)来填充,每个立方体包含一些数据信息
Spacial(空间位置)方法
- 构建时通过空间位置决定每个cell在数据结构中的位置
- 使用的方法就是上次写的文章
- 近邻查询时使用prefix sum来排序粒子的空间
- 这种数据结构用于近邻查找,十分迅速,只需要O(1)的复杂度
- 图中的红色色块代表了当前体素
- 绿色代表近邻的体素
- 再画个太极体素:)
Hash方法
- Spacial方法存在内存占用过大(O(N^3))的问题
- 使用hash表可以有效减少内存占用,同时查询时间依旧为O(1)
-
红色粒子是当前粒子
-
绿色就近邻粒子
-
粉红透明球是搜索半径
-
在我之前实现的sph方法里面有源码
-
原理在 matthias的视频中有提到,核心技巧就是利用magic function映射cell的索引
-
另外hash grid有一个非常好的优点(unbounded),可以让domain是无限大,免去了计算所有粒子(体素)的最大最小边界
Bvh(包围层次盒)
-
一棵二叉树,可以有效的进行空间划分
-
它是做光线追踪必备的数据结构,可以使用自上而下串行构建高质量的树,也可以自下而上并行构建中低质量的树
-
使用SAH(表面积启发式算法)构建的树,质量最好,也是检验各种算法的依照
-
这里给大家贴一个我觉得特别牛的开源代码,做bvh分析特别透彻
-
我在自己的开源代码中实现了完全并行的bvh构建,利用莫顿码和radix sort实现
-
像embree/optix这些组件就是利用硬件极致得实现bvh的查询与构建
- 上图演示了bvh可视化的效果,以及单根光线追踪mesh表面获取交点的演示
- taichi模型也来一个
Kdtree
- K维数也是一种空间二叉树,它比bvh做近邻查询更加迅速,但是构建起来比较麻烦
- 它的原理就是每次划分子树时,需要评估以X,Y,Z三个轴
中哪个轴作为划分依据,然后就要按照X,Y,Z坐标进行快速排序,找到中位数 - 常见的划分方法有最长轴,以及最大方差
- 渲染中,光子图方法依赖于有效的kdtree的构建
- 上图演示了整个划分过程
- 红色是X轴划分,绿色是Y轴划分,蓝色是Z轴划分
其他数据结构
数据结构的应用
level set实现(sdf)
- 通过构建bvh可以计算空间一点到一个三角形mesh的最短距离
- 然后就可以利用Grid储存这些距离,形成离散化的有向距离场
SDF之一——DiscreGrid
- 最近学习了一下一个有效的SDF开源实现
- 该算法通过Octree和多项式拟合(勒让得),降低了sdf降采样的精度损失
- 分析策略为,统计建立新的8个子节点降低误差A,不建立子节点通过多项式拟合降低误差B,比较AB两种方法误差降低,哪种更有效。该方法原文,也就是HP(hierarchy,polynomial)的含义
- 也就是说网格里储存不仅仅是有向距离,还有多项式系数
- 拿来做了一个动画
- 一个mesh被sdf储存为有向距离场后,可视化就需要利用切片形式(有点像断层扫描)
- 每个切片形成的图像中绿色代表了该点位于mesh的内部,红色则是外部,且越靠近边缘,值越小越黑
- 可惜taichi模型没法简单实现,必须得把每个字母拆开来,然后再做bool操作(懒)
SDF之二——NanoVDB
- 它是获得奥斯卡奖的openvdb,:)的gpu版本,不仅有C++/C,还有HLSL/GLSL的开源实现
- 感觉可以拿taichi实现一个nanovdb的插件也不是难事
- 核心数据结构是一个固定深度的B+树
- openvdb的数据结构,可以做类似图像处理的膨胀腐蚀操作(利用数据结构中bitmask),其实就是个三维图像,而nanovdb的限制比较大,有些操作没法完成,但是可以被gpu直接使用
- 拿来做个动画:)
- 使用nanovdb主要是有效降低内存占用
- 上图中图像从马赛克逐渐平滑,使用了最近点,线性,二次方插值
采样方法
- 这里介绍一个泊松圆盘采样,也是之前我在流体仿真中实现的一个边界条件的方法,先上图
- 就是有效得在mesh上均匀撒点,它的实现依赖于hash-grid数据结构
- 该方法可以做成完全并行,核心思想是reduce方法。例如,并行求和我们可以利用2的整数次幂来构建互不影响的求和序列,而这里的采样方法可以通过构建27组空间中近邻不受影响的序列,序列内部并行处理
- taichi模型也来一个
四面体化(Tetrahedralize)
- 在软体仿真中常常需要把mesh四面体化,这样就可以依据体积恢复到初始状态的假设,让物体具有弹性效果了
- matthias视频中,使用bvh做有效的查询,来四面体化。
- 如今最快,鲁棒性最高的四面体化算法,就是tetwild
- 我也是编译后,做了一个动画,能力不足以实现
总结
- 底层数据结构的实现是十分重要的,上层算法的性能和可行性都依赖于这些数据结构。
- 最近关注到GLTF的extension中也出现了网格quantization的特性,再次联想到quan-taichi,数据结构真的太重要了
数据结构 | hash-grid | bvh | kdtree |
---|---|---|---|
构建速度 | O(n) | O(nlog(n)) | O(nlog(n) |
插入 | 不支持 | 不支持 | 支持O(log(n)) |
近邻搜索 | O(1) | 一般不用它 | O(log(n)) |
光追 | ray-marching | ray-trace | 光子图 |
- 欢迎补充