General, robust, and efficient polyhedron intersection in the Interface Reconstruction Library

Intersecting a polyhedron with a half-space or another polyhedron is required in various fields, including computer graphics, computer-aided design, and many methods used in computational physics. Often, the polyhedra involved are complicated non-convex objects, and intersecting them constitutes a significant computational cost. To address this, we present a general, geometrically robust, and efficient polyhedron intersection algorithm based on the half-edge data structure and implemented in the open-source Interface Reconstruction Library. We then employ this algorithm in a novel graph-based approach to distribute the volume of a polyhedron over a computational mesh. To demonstrate their performance, the two methods are tested on randomly generated configurations. Compared to the open-source packages VOFTools and R3D, the polyhedron intersection algorithm shows superior speed over the range of convex and non-convex polyhedra tested. The volume distribution method also proves to be discretely conservative, even for meshes containing degenerate faces. (C) 2021 Elsevier Inc. All rights reserved.

Automated summary

This study introduces a general, geometrically robust, and efficient polyhedron intersection algorithm based on the half-edge data structure, as well as a novel method for distributing polyhedron volume over a computational mesh. Both methods demonstrate superior performance, with the polyhedron intersection algorithm showing faster speed and the volume distribution method proving to be discretely conservative.