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, which can be found on the Computer Society Digital Library at http://doi.ieeecomputersociety.org/10.1109/TVCG.2019.2945961.
Original language | English (US) |
---|---|
Article number | 8865648 |
Pages (from-to) | 2970-2981 |
Number of pages | 12 |
Journal | IEEE Transactions on Visualization and Computer Graphics |
Volume | 26 |
Issue number | 10 |
DOIs | |
State | Published - Oct 1 2020 |
Keywords
- 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