A Hardware Oriented Approximate Convex Hull Algorithm and its FPGA Implementation

Tatsuma MORI; Taito MANABE; Yuichiro SHIBATA

doi:10.1587/transfun.2021VLP0016

IEICE TRANSACTIONS on Fundamentals

Open Access
A Hardware Oriented Approximate Convex Hull Algorithm and its FPGA Implementation

Tatsuma MORI, Taito MANABE, Yuichiro SHIBATA

Full Text Views

46

Cite this

Free PDF (1.5MB)

Summary :

The convex hull is the minimum convex surrounding a given set of points. Since the process of finding convex hulls has various practical application fields including embedded real-time systems, efficient acceleration of convex hull algorithms is an important problem in computer geometry. In this paper, we discuss an FPGA acceleration approach to address this problem. In order to compute the convex hull of an unsorted point set, it is necessary to store all the points during the computation, and thus the capacity of a on-chip memory is likely to be a major constraint for efficient FPGA implementation. On the other hand, approximate convex hulls are often sufficient for practical applications. Therefore, we propose a hardware oriented approximate convex hull algorithm, which can process the input points as a stream without storing all the points in the memory. We also propose some computation reduction techniques for efficient FPGA implementation. Then, we present FPGA implementation of the proposed algorithm, which is parallelized both in temporal and spatial domains, and evaluate its effectiveness in terms of performance and accuracy. As a result, we demonstrated 11 to 30 times faster performance compared to the widely-used convex hull software library Qhull. In addition, accuracy assessment revealed that the maximum approximation error normalized to the diameters of point sets was 0.038%, which was reasonably small for practical use cases.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E105-A No.3 pp.459-467

Publication Date: 2022/03/01

Publicized: 2021/09/02

Online ISSN: 1745-1337

DOI: 10.1587/transfun.2021VLP0016

Type of Manuscript: Special Section PAPER (Special Section on VLSI Design and CAD Algorithms)

Category

Authors

Tatsuma MORI
  Nagasaki University
Taito MANABE
  Nagasaki University
Yuichiro SHIBATA
  Nagasaki University

Keyword

convex hull, hardware algorithm, FPGA, approximated algorithm

Cite this

Copy

Tatsuma MORI, Taito MANABE, Yuichiro SHIBATA, "A Hardware Oriented Approximate Convex Hull Algorithm and its FPGA Implementation" in IEICE TRANSACTIONS on Fundamentals, vol. E105-A, no. 3, pp. 459-467, March 2022, doi: 10.1587/transfun.2021VLP0016.
Abstract: The convex hull is the minimum convex surrounding a given set of points. Since the process of finding convex hulls has various practical application fields including embedded real-time systems, efficient acceleration of convex hull algorithms is an important problem in computer geometry. In this paper, we discuss an FPGA acceleration approach to address this problem. In order to compute the convex hull of an unsorted point set, it is necessary to store all the points during the computation, and thus the capacity of a on-chip memory is likely to be a major constraint for efficient FPGA implementation. On the other hand, approximate convex hulls are often sufficient for practical applications. Therefore, we propose a hardware oriented approximate convex hull algorithm, which can process the input points as a stream without storing all the points in the memory. We also propose some computation reduction techniques for efficient FPGA implementation. Then, we present FPGA implementation of the proposed algorithm, which is parallelized both in temporal and spatial domains, and evaluate its effectiveness in terms of performance and accuracy. As a result, we demonstrated 11 to 30 times faster performance compared to the widely-used convex hull software library Qhull. In addition, accuracy assessment revealed that the maximum approximation error normalized to the diameters of point sets was 0.038%, which was reasonably small for practical use cases.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.2021VLP0016/_p

Copy

@ARTICLE{e105-a_3_459,
author={Tatsuma MORI, Taito MANABE, Yuichiro SHIBATA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={A Hardware Oriented Approximate Convex Hull Algorithm and its FPGA Implementation},
year={2022},
volume={E105-A},
number={3},
pages={459-467},
abstract={The convex hull is the minimum convex surrounding a given set of points. Since the process of finding convex hulls has various practical application fields including embedded real-time systems, efficient acceleration of convex hull algorithms is an important problem in computer geometry. In this paper, we discuss an FPGA acceleration approach to address this problem. In order to compute the convex hull of an unsorted point set, it is necessary to store all the points during the computation, and thus the capacity of a on-chip memory is likely to be a major constraint for efficient FPGA implementation. On the other hand, approximate convex hulls are often sufficient for practical applications. Therefore, we propose a hardware oriented approximate convex hull algorithm, which can process the input points as a stream without storing all the points in the memory. We also propose some computation reduction techniques for efficient FPGA implementation. Then, we present FPGA implementation of the proposed algorithm, which is parallelized both in temporal and spatial domains, and evaluate its effectiveness in terms of performance and accuracy. As a result, we demonstrated 11 to 30 times faster performance compared to the widely-used convex hull software library Qhull. In addition, accuracy assessment revealed that the maximum approximation error normalized to the diameters of point sets was 0.038%, which was reasonably small for practical use cases.},
keywords={},
doi={10.1587/transfun.2021VLP0016},
ISSN={1745-1337},
month={March},}

Copy

TY - JOUR
TI - A Hardware Oriented Approximate Convex Hull Algorithm and its FPGA Implementation
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 459
EP - 467
AU - Tatsuma MORI
AU - Taito MANABE
AU - Yuichiro SHIBATA
PY - 2022
DO - 10.1587/transfun.2021VLP0016
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E105-A
IS - 3
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - March 2022
AB - The convex hull is the minimum convex surrounding a given set of points. Since the process of finding convex hulls has various practical application fields including embedded real-time systems, efficient acceleration of convex hull algorithms is an important problem in computer geometry. In this paper, we discuss an FPGA acceleration approach to address this problem. In order to compute the convex hull of an unsorted point set, it is necessary to store all the points during the computation, and thus the capacity of a on-chip memory is likely to be a major constraint for efficient FPGA implementation. On the other hand, approximate convex hulls are often sufficient for practical applications. Therefore, we propose a hardware oriented approximate convex hull algorithm, which can process the input points as a stream without storing all the points in the memory. We also propose some computation reduction techniques for efficient FPGA implementation. Then, we present FPGA implementation of the proposed algorithm, which is parallelized both in temporal and spatial domains, and evaluate its effectiveness in terms of performance and accuracy. As a result, we demonstrated 11 to 30 times faster performance compared to the widely-used convex hull software library Qhull. In addition, accuracy assessment revealed that the maximum approximation error normalized to the diameters of point sets was 0.038%, which was reasonably small for practical use cases.
ER -

IEICE TRANSACTIONS on Fundamentals