分层 RLE 水平集：紧凑且多功能的可变形表面表示 Hierarchical RLE Level Set: A Compact and Versatile ... 论文阅读笔记

最新推荐文章于 2025-05-14 17:50:45 发布

hijackedbycsdn

最新推荐文章于 2025-05-14 17:50:45 发布

阅读量786

点赞数 23

分类专栏：航工文章标签：论文阅读笔记

本文链接：https://blog.csdn.net/hijackedbycsdn/article/details/136161203

版权

概述

结合了 DT-Grid 和 RLE 水平集

H-RLE 水平集以维度递归方式采用 RLE。 RLE 方案允许连续非窄带区域的紧凑存储，同时沿每个轴的维度递归编码有效地压缩非窄带平面和体积。

本文除了介绍 H-RLE 水平集数据结构及其高效的核心算法之外，还描述了从我们使用该结构中受益的众多应用：我们的统一隐式对象表示、高效且鲁棒的网格到水平集转换、快速射线跟踪、水平集变形、碰撞检测和完全稀疏流体模拟（包括 RLE 向量和矩阵表示）。我们将流行的八叉树水平集和 Peng 水平集结构与 H-RLE 水平集进行比较，表明后者在窄带顺序访问速度和总体内存使用率

引言

我们的一般方法是通过层次维分解的方式使用采样水平集的紧凑游程编码（RLE）。这种方法通过递归定义推广到任何维度，并允许 H-RLE 水平集与几何表面的面积成比例地缩放。此外，我们的多功能网格表示具有真正动态的优点；它是无界的并且可以无限扩展（在机器精度内）。最后我们注意到，我们的数据结构可用于存储任何体积定义的字段，例如体积纹理、流体速度场、弹性张量场和稀疏矩阵。我们通过几种不同的具有挑战性的图形应用程序来说明这种数据结构的重要价值

相关工作

原始水平集方法 O(n^3)

Adalsteinsson and Sethian [1995] 引入窄带方法，将大多数计算限制为紧邻界面周围的活动体素的细带，从而将时间复杂度降低到 O(n^2)。然而，这种窄带方案的存储复杂度仍然是 O(n^3)。此外，窄带结构的定期更新需要 O(n3) 操作，其中访问整个体积上的体素以重建活动体素列表。

Whitaker [1998] 的近似稀疏域水平集方法消除了 O(n^3 ) 时间复杂度。稀疏场水平集方法采用一组链表来跟踪界面周围的活动体素。这允许根据需要增量扩展活动区域，而不会产生任何重大开销。虽然在时间上始终有效，但稀疏域水平集方法仍然需要 O(n^3 ) 存储空间。

Peng et al. [1999] 专为更精确的有限差分方案而设计，并且不需要慢速链表。然而，他们的方法没有克服 O(n^3) 存储要求和 O(n3 ) 定期更新

事实上，需要额外的存储来跟踪窄带中存在的实际网格点。因此，这种二分法的存在推动了研究减少水平集的存储需求，而不会显着影响 O(n2 ) 的计算效率。最近的两种方法是稀疏块网格和八叉树。

Bridson [2003] 的稀疏块网格方法将大小为 n^3 的整个包围体划分为每个 m^3 体素的小立方体块。