Half-Space Power Diagrams and Discrete Surface Offsets

Abstract

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.

@article{Chen:2020:HSP,
    doi = {10.1109/tvcg.2019.2945961},
    url = {https://doi.org/10.1109/tvcg.2019.2945961},
    year = {2020},
    month = oct,
    publisher = {Institute of Electrical and Electronics Engineers ({IEEE})},
    volume = {26},
    number = {10},
    pages = {2970--2981},
    author = {Chen, Zhen and Panozzo, Daniele and Dumas, J{\'e}r{\'e}mie},
    title = {Half-Space Power Diagrams and Discrete Surface Offsets},
    journal = {{IEEE} Transactions on Visualization and Computer Graphics}
}