Half-Space Power Diagrams and Discrete Surface Offsets

Area of Science:

• Computational Geometry
• Computer-Aided Design (CAD)
• Digital Fabrication

Background:

• Offset surfaces are crucial in various geometric applications, including digital fabrication and computer graphics.
• Existing methods for offset surface computation often rely on computationally expensive volumetric distance field calculations.
• The dexel data structure discretizes shapes, posing challenges for efficient offset surface generation.

Purpose of the Study:

• To present an efficient and parallelizable algorithm for computing offset surfaces of dexel-discretized shapes.
• To introduce a novel approach leveraging half-space power diagrams for offset surface construction.
• To enable interactive processing of high-resolution models for applications like digital fabrication.

Main Methods:

• A two-stage sweeping procedure is employed, simplifying implementation and enhancing efficiency.
• The algorithm avoids traditional volumetric distance field computations.
• The construction utilizes properties of half-space power diagrams, a novel application for offset surfaces.

Main Results:

• The proposed algorithm achieves efficient and trivially parallelizable computation of offset surfaces.
• Experimental timings demonstrate competitive performance compared to previous approaches.
• The method successfully enables interactive processing of high-resolution models.

Conclusions:

• This novel algorithm offers a significant improvement in efficiency and simplicity for offset surface computation.
• Its applicability extends to interactive modeling for digital fabrication, topology optimization, collision detection, and skeleton extraction.
• The use of half-space power diagrams presents a new avenue for geometric offset computations.