Parallel Computation of 3D Clipped Voronoi Diagrams

Area of Science:

• Computational Geometry
• Computer Graphics
• Scientific Computing

Background:

• Voronoi diagrams have numerous applications in restricted domains.
• Existing parallel algorithms effectively compute 2D and surface Voronoi diagrams on graphics hardware.
• Computing clipped Voronoi diagrams within volumes remains a significant computational challenge.

Purpose of the Study:

• To propose an efficient GPU algorithm for computing clipped Voronoi diagrams within volumes.
• To address the limitations of existing methods for volumetric Voronoi diagram computation.
• To develop a method that outperforms current state-of-the-art CPU techniques.

Main Methods:

• A preprocessing step discretizes the input volume into a tetrahedral mesh.
• The algorithm clips Voronoi cells using the four planes of each tetrahedron.
• This approach contrasts with existing methods that clip tetrahedra using bisecting planes.

Main Results:

• The proposed GPU algorithm efficiently computes clipped Voronoi diagrams in volumes.
• The strategy of clipping Voronoi cells with tetrahedron planes simplifies computation.
• Performance improvements of up to an order of magnitude compared to CPU methods were achieved.

Conclusions:

• The developed GPU algorithm provides an efficient solution for computing clipped Voronoi diagrams in volumes.
• The novel clipping strategy offers a significant advantage over existing approaches.
• This work advances the state-of-the-art in parallel computation of Voronoi diagrams for volumetric data.