Automatically Approximating 3D Points with Co-Axisal Objects

In this paper, we investigate the problem of approximating a set S of 3D points with co-axisal objects typically from CAD/CAM (namely, cylindrical segments, cones and conical frustums). The objective is to minimize the sum of volumes of these objects (as well as the number of objects used). The general problem when the objects can have arbitrary axes is strongly NP-hard as a cylindrical segment, a cone and a conical frustum can all degenerate into a line segment. We present a general algorithm which combines a neat doubling search method to decompose S into desired subsets (or components). For each subset S, we present a unified practical approximation algorithm for minimizing the volume of the cone (conical frustum, or cylindrical segment) which encloses points in S. Preliminary empirical results indicate that the algorithm is in fact very accurate.