Stream Computation of 3D Approximate Convex Hulls with an FPGA
Stream Computation of 3D Approximate Convex Hulls with an FPGA
复制标题
DOI：
10.1145/3535044.3535053
复制
发表时间：
2022-06
期刊：
影响因子：
--
通讯作者：
Tatsuma Mori;Daiki Furukawa;Keigo Motoyoshi;Haruto Ikehara;Kaito Ohira;Taito Manabe;Yuichiro Shibata-Yuichi
中科院分区：
文献类型：
--
作者：
Tatsuma Mori;Daiki Furukawa;Keigo Motoyoshi;Haruto Ikehara;Kaito Ohira;Taito Manabe;Yuichiro Shibata-Yuichi
凸船体是包围给定点集的最小凸集。求凸壳问题不仅是计算机几何中最基本的算法之一，而且在机器人学、地理信息学等领域有着广泛的应用。本文提出并评估了一种高效的流水线FPGA实现的近似凸船体计算的三维点。所提出的架构不需要输入点预先排序，并且可以以流水线方式执行算法，而无需将所有点存储在存储器中。我们在Intel Stratix 10 FPGA上实现了该架构，以揭示其性能，资源使用和近似精度之间的权衡关系。因此，我们展示了比运行在英特尔酷睿i9 - 9900 K上的凸船体软件库Q船体快9到115倍的性能。准确性评估显示，归一化为点集直径的近似误差仅为0.037%至3.173%，对于实际用例来说，这是可以接受的小。
The convex hull is the minimum convex set which encloses a given point set. A problem to find convex hulls is not only one of the most fundamental algorithms in computer geometry, but also has a wide variety of practical applications such as robotics and geographic informatics. This paper proposes and evaluates an efficient pipelined FPGA implementation of approximate convex hull computing for 3D points. The proposed architecture does not require the input points to be sorted in advance, and can execute the algorithm in a pipelined manner without storing all the points in memory. We implemented the architecture on an Intel Stratix 10 FPGA to reveal the tradeoff relationship among its performance, resource usage, and approximation accuracy. As a result, we demonstrated 9 to 115 times faster performance compared to the convex hull software library Qhull, which was run on the Intel Core i9-9900K. The accuracy assessment revealed that the approximation error normalized to the diameters of point sets was only 0.037% to 3.173%, which was acceptably small for practical use cases.