图形学中常用的数据结构及其应用

图形学中的常用数据结构

  • 本篇文章的内容受到一篇高性能并行数据结构的文献启发,介绍一下一些常见的数据结构,自己也是工作之余肝了demo做了一些动画,由于用了一些工作的组件,不太好开源,等有时间了写成taichi

Uniform Grid(网格)

  • 将三维空间区域(domain),使用尺寸一致立方体(cell)来填充,每个立方体包含一些数据信息

Spacial(空间位置)方法

  • 构建时通过空间位置决定每个cell在数据结构中的位置
  • 使用的方法就是上次写的文章
  • 近邻查询时使用prefix sum来排序粒子的空间

voxel

  • 这种数据结构用于近邻查找,十分迅速,只需要O(1)的复杂度
  • 图中的红色色块代表了当前体素
  • 绿色代表近邻的体素

taichi-voxel

  • 再画个太极体素:)

Hash方法

  • Spacial方法存在内存占用过大(O(N^3))的问题
  • 使用hash表可以有效减少内存占用,同时查询时间依旧为O(1)

HASH-GRID

  • 红色粒子是当前粒子

  • 绿色就近邻粒子

  • 粉红透明球是搜索半径

  • 在我之前实现的sph方法里面有源码

  • 原理在 matthias的视频中有提到,核心技巧就是利用magic function映射cell的索引

  • 另外hash grid有一个非常好的优点(unbounded),可以让domain是无限大,免去了计算所有粒子(体素)的最大最小边界

Bvh(包围层次盒)

  • 一棵二叉树,可以有效的进行空间划分

  • 它是做光线追踪必备的数据结构,可以使用自上而下串行构建高质量的树,也可以自下而上并行构建中低质量的树

  • 使用SAH(表面积启发式算法)构建的树,质量最好,也是检验各种算法的依照

  • 这里给大家贴一个我觉得特别牛的开源代码,做bvh分析特别透彻

  • 我在自己的开源代码中实现了完全并行的bvh构建,利用莫顿码和radix sort实现

  • 像embree/optix这些组件就是利用硬件极致得实现bvh的查询与构建

SAHBVH-DRAGON

  • 上图演示了bvh可视化的效果,以及单根光线追踪mesh表面获取交点的演示

SAHBVH

  • taichi模型也来一个

Kdtree

  • K维数也是一种空间二叉树,它比bvh做近邻查询更加迅速,但是构建起来比较麻烦
  • 它的原理就是每次划分子树时,需要评估以X,Y,Z三个轴
    中哪个轴作为划分依据,然后就要按照X,Y,Z坐标进行快速排序,找到中位数
  • 常见的划分方法有最长轴,以及最大方差
  • 渲染中,光子图方法依赖于有效的kdtree的构建

KDTREE-DRAGON

  • 上图演示了整个划分过程
  • 红色是X轴划分,绿色是Y轴划分,蓝色是Z轴划分

KDTREE

其他数据结构

  • 八叉树
  • bsp树
  • 这两个我就贴贴链接,自己本身没什么研究,期待有大手子能够讲解一下

数据结构的应用

level set实现(sdf)

  • 通过构建bvh可以计算空间一点到一个三角形mesh的最短距离
  • 然后就可以利用Grid储存这些距离,形成离散化的有向距离场

SDF之一——DiscreGrid

  • 最近学习了一下一个有效的SDF开源实现
  • 该算法通过Octree和多项式拟合(勒让得),降低了sdf降采样的精度损失
  • 分析策略为,统计建立新的8个子节点降低误差A,不建立子节点通过多项式拟合降低误差B,比较AB两种方法误差降低,哪种更有效。该方法原文,也就是HP(hierarchy,polynomial)的含义
  • 也就是说网格里储存不仅仅是有向距离,还有多项式系数
  • 拿来做了一个动画
    GRID
  • 一个mesh被sdf储存为有向距离场后,可视化就需要利用切片形式(有点像断层扫描)
  • 每个切片形成的图像中绿色代表了该点位于mesh的内部,红色则是外部,且越靠近边缘,值越小越黑
  • 可惜taichi模型没法简单实现,必须得把每个字母拆开来,然后再做bool操作(懒)

SDF之二——NanoVDB

  • 它是获得奥斯卡奖的openvdb,:)的gpu版本,不仅有C++/C,还有HLSL/GLSL的开源实现
  • 感觉可以拿taichi实现一个nanovdb的插件也不是难事
  • 核心数据结构是一个固定深度的B+树
  • openvdb的数据结构,可以做类似图像处理的膨胀腐蚀操作(利用数据结构中bitmask),其实就是个三维图像,而nanovdb的限制比较大,有些操作没法完成,但是可以被gpu直接使用
  • 拿来做个动画:)
    NANO-VDB
  • 使用nanovdb主要是有效降低内存占用
  • 上图中图像从马赛克逐渐平滑,使用了最近点,线性,二次方插值

采样方法

  • 这里介绍一个泊松圆盘采样,也是之前我在流体仿真中实现的一个边界条件的方法,先上图
    POSSIONDISK-SAMPLE-DAGON
  • 就是有效得在mesh上均匀撒点,它的实现依赖于hash-grid数据结构
  • 该方法可以做成完全并行,核心思想是reduce方法。例如,并行求和我们可以利用2的整数次幂来构建互不影响的求和序列,而这里的采样方法可以通过构建27组空间中近邻不受影响的序列,序列内部并行处理

POSSION-DISK

  • taichi模型也来一个

四面体化(Tetrahedralize)

  • 在软体仿真中常常需要把mesh四面体化,这样就可以依据体积恢复到初始状态的假设,让物体具有弹性效果了
  • matthias视频中,使用bvh做有效的查询,来四面体化。
  • 如今最快,鲁棒性最高的四面体化算法,就是tetwild
  • 我也是编译后,做了一个动画,能力不足以实现 :smiling_face_with_tear:
    tet

总结

  • 底层数据结构的实现是十分重要的,上层算法的性能和可行性都依赖于这些数据结构。
  • 最近关注到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 光子图
  • 欢迎补充
7 Likes

写的很好。请教一个问题,做碰撞检测来说,hash-grid 和 bvh两种方法的优劣点分别是啥呢?

  • 容易理解的对比项,包括适用范围,查询的速度,精度
  • 这两者最重要的差别就是适用范围
  • grid这种数据结构最适合储存同样大小的物体(primitive),比如等大的球状粒子
  • bvh则不挑形状,啥都可以塞进去,反正都是aabb
  • 所以就导致了,描述一个物体时,使用grid,只能把它体素化(等大),丢失了细节,而bvh可以把三角形储存起来
  • 精度: grid < bvh
  • 速度: grid > bvh
  • 但是我们可以通过grid结构,制作sdf。结合八叉树/B+树,储存距离场/拟合系数,也就是上文中discreGrid和nanovdb的做法,提升精度,但是还是有误差,学术研究从未停止探索
  • bvh也可以通过优化遍历的性能,从硬件/软件上,来弥补它的缺点,学术研究同样一直在发展中