CGGC Seminar: Precise Convex Hull Computation for FreeformModels using a Hierarchical Gauss Map and a Coons Bounding Volume Hierarchy

Speaker:
Yong Joon Kim (CS, Technion)
Date:
Sunday, 3.11.2013, 13:00
Place:
Room 337-8 Taub Bld.

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 tri-tangent planes and bi-tangent developable scrolls. We demonstrate the effectiveness of our algorithm using experimental results.

Back to the index of events