Streaming computation of Delaunay triangulations
Streaming computation of Delaunay triangulations
复制标题
DOI：
10.1145/1179352.1141992
复制
发表时间：
2006-07
期刊：
影响因子：
--
通讯作者：
M. Isenburg;Yuanxin Liu;J. Shewchuk;J. Snoeyink
中科院分区：
文献类型：
--
作者：
M. Isenburg;Yuanxin Liu;J. Shewchuk;J. Snoeyink
我们展示了如何通过利用点流中的自然空间一致性来极大地加速计算2D和3D中巨大的、均匀分布的点集的Delaunay三角剖分的算法。我们通过将空间终结引入点流来获得巨大的性能提升：我们将空间划分为区域，并使用终结标签来增加输入点流，以指示何时一个点是其区域中的最后一个点。通过扩展Delaunay三角剖分的增量算法以使用Finfinition标签和生成流网格输出，我们在48分钟内从11.2 GB的LIDAR数据计算出Neuse River系统的十亿个三角形地形表示，在带有两个硬盘的笔记本电脑上仅使用70MB的内存。这比以前最快的核外Delaunay三角测量软件快了12倍。
We show how to greatly accelerate algorithms that compute Delaunay triangulations of huge, well-distributed point sets in 2D and 3D by exploiting the natural spatial coherence in a stream of points. We achieve large performance gains by introducing spatial finalization into point streams: we partition space into regions, and augment a stream of input points with finalization tags that indicate when a point is the last in its region. By extending an incremental algorithm for Delaunay triangulation to use finalization tags and produce streaming mesh output, we compute a billion-triangle terrain representation for the Neuse River system from 11.2 GB of LIDAR data in 48 minutes using only 70 MB of memory on a laptop with two hard drives. This is a factor of twelve faster than the previous fastest out-of-core Delaunay triangulation software.