Precise convex hull computation for freeform models using a hierarchical Gauss map and a Coons bounding volume hierarchy

•Present an interactive-speed algorithm for computing the precise convex hull of freeform geometric models.•Employing two pre-built data structures, a hierarchical Gauss map and a Coons bounding volume hierarchy, we develop an efficient culling technique that can eliminate the majority of redundant surface patches.•Construct the precise convex hull boundary using numerical methods.

We present an interactive-speed algorithm for computing the precise convex hull of freeform geometric models. The algorithm is based on two pre-built data structures: (i) a Gauss map organized in a hierarchy of normal pyramids and (ii) a Coons bounding volume hierarchy (CBVH) which effectively approximates freeform surfaces with a hierarchy of bilinear surfaces. For the axis direction of each normal pyramid, we sample a point on the convex hull boundary using the CBVH. The sampled points together with the hierarchy of normal pyramids serve as a hierarchical approximation of the convex hull, with which we can eliminate the majority of redundant surface patches. We compute the precise trimmed surface patches on the convex hull boundary using a numerical tracing technique and then stitch them together in a correct topology while filling the gaps with tritangent planes and bitangent developable scrolls. We demonstrate the effectiveness of our algorithm using experimental results.

Graphical abstractFigure optionsDownload full-size imageDownload as PowerPoint slide