2023/04/08 by Benjamin Kenwright, Kenwright, Ben
Computer Science · Engineering · #Computational Geometry and Mesh Generation #Computer Graphics and Visualization Techniques #3D Shape Modeling and Analysis
paper · pdf · doi:10.48550/arxiv.2304.04079
Writing an uncomplicated, robust, and scalable three-dimensional convex hull algorithm is challenging and problematic. This includes, coplanar and collinear issues, numerical accuracy, performance, and complexity trade-offs. While there are a number of methods available for finding the convex hull based on geometric calculations, such as, the distance between points, but do not address the technical challenges when implementing a usable solution (e.g., numerical issues and degenerate cloud points). We explain some common algorithm pitfalls and engineering modifications to overcome and solve these limitations. We present a novel iterative method using support mapping and surface projection to create an uncomplicated and robust 2d and 3d convex hull algorithm.