Half-Space Power Diagrams and Discrete Surface Offsets

Zhen Chen, Daniele Panozzo, Jeremie Dumas

Research output: Contribution to journalArticlepeer-review


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, which can be found on the Computer Society Digital Library at http://doi.ieeecomputersociety.org/10.1109/TVCG.2019.2945961.

Original languageEnglish (US)
Article number8865648
Pages (from-to)2970-2981
Number of pages12
JournalIEEE Transactions on Visualization and Computer Graphics
Issue number10
StatePublished - Oct 1 2020


  • Geometry processing
  • dexels
  • layered depth images
  • offset
  • power diagram
  • voronoi diagram

ASJC Scopus subject areas

  • Software
  • Signal Processing
  • Computer Vision and Pattern Recognition
  • Computer Graphics and Computer-Aided Design


Dive into the research topics of 'Half-Space Power Diagrams and Discrete Surface Offsets'. Together they form a unique fingerprint.

Cite this