FAST 3-D EUCLIDEAN CONNECTED COMPONENTS

Published: 2022

Author(s):

Landis, E. N.
Franklin, R.
Magalhães, S.

Publication Name:

Publication URL: https://wrfranklin.org/p/240-connect-gem-2021.pdf

Research Area:

Industry 4.0

Keywords:

algorithm, computer implementation

Abstract:

We present an efficient algorithm and implementation for computing the connected components within a 3-D cube of voxels, also known as the Euclidean union-find problem. There may be over 109 voxels. The components may be 8-connected or 26-connected. Computing connected components has applications ranging from material failure in concrete under increasing stress to electrical conductivity in complex metal objects to elasticity in 3D printed parts. One key to efficiency is representing voxels by 1-D runs of adjacent voxels. We also compute each components surface area. As a special case, 2-D connected components of images may easily be computed.