Half-Space Power Diagrams and Discrete Surface Offsets

IEEE Transactions on Visualization and Computer Graphics

Published October 11, 2019

Zhen Chen, Jérémie Dumas, Daniele Panozzo

We present an efficient, trivially parallelizable algorithm to compute offset surfaces of shapes discretized using a dexel data structure. Our algorithm is based on a two-stage sweeping procedure that is simple to implement and efficient, entirely avoiding volumetric distance field computations typical of existing methods. Our construction is based on properties of half-space power diagrams, where each seed is only visible by a half space, which were never used before for the computation of surface offsets. The primary application of our method is interactive modeling for digital fabrication. Our technique enables a user to interactively process high-resolution models. It is also useful in a plethora of other geometry processing tasks requiring fast, approximate offsets, such as topology optimization, collision detection, and skeleton extraction. We present experimental timings, comparisons with previous approaches, and provide a reference implementation in the supplemental material.

Learn More

Research Area:  Graphics (2D & 3D)