Stream Computation of 3D Approximate Convex Hulls with an FPGA

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.