Half-Space Power Diagrams and Discrete Surface Offsets

Zhen Chen, Daniele Panozzo, Jeremie Dumas

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.
BibTeX
@misc{chen2018half,
  author = {Zhen Chen and Daniele Panozzo and Jeremie Dumas},
  title = {{Half-Space Power Diagrams and Discrete Surface Offsets}},
  year = {2018},
  eprint = {1804.08968},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1804.08968},
}
Figure