University of California, Davis, USA.
IEEE Trans Vis Comput Graph. 2010 Nov-Dec;16(6):1541-50. doi: 10.1109/TVCG.2010.156.
Applying certain visualization techniques to datasets described on unstructured grids requires the interpolation of variables of interest at arbitrary locations within the dataset's domain of definition. Typical solutions to the problem of finding the grid element enclosing a given interpolation point make use of a variety of spatial subdivision schemes. However, existing solutions are memory- intensive, do not scale well to large grids, or do not work reliably on grids describing complex geometries. In this paper, we propose a data structure and associated construction algorithm for fast cell location in unstructured grids, and apply it to the interpolation problem. Based on the concept of bounding interval hierarchies, the proposed approach is memory-efficient, fast and numerically robust. We examine the performance characteristics of the proposed approach and compare it to existing approaches using a number of benchmark problems related to vector field visualization. Furthermore, we demonstrate that our approach can successfully accommodate large datasets, and discuss application to visualization on both CPUs and GPUs.
将某些可视化技术应用于在非结构网格上描述的数据集需要在数据集的定义域内的任意位置插值感兴趣的变量。解决在给定插值点处找到网格元素的问题的典型解决方案是使用各种空间细分方案。但是，现有的解决方案内存密集，不能很好地扩展到大网格，或者在描述复杂几何形状的网格上不可靠地工作。在本文中，我们提出了一种用于非结构网格中快速单元定位的数据结构和相关构建算法，并将其应用于插值问题。基于边界区间层次结构的概念，所提出的方法具有内存效率高、速度快和数值鲁棒性强的特点。我们使用与向量场可视化相关的一些基准问题来检查所提出方法的性能特征，并将其与现有方法进行比较。此外，我们证明了我们的方法可以成功地适应大型数据集，并讨论了在 CPU 和 GPU 上进行可视化的应用。
