Fast Volume Computation for 3D Meshes Using Divergence Theorem

Introduction to the Algorithm

This article details a fast algorithm for computing the volume of a simple, closed, triangulated 3D mesh. The approach is based on the divergence theorem, which allows for the transformation of a volume integral into a surface integral. This method is specifically applicable to meshes that meet these criteria, with potential for future generalization.

Mathematical Foundation

The volume of a region is initially defined as a triple integral. By selecting a function whose divergence is one, the divergence theorem converts this triple integral into a surface integral over the mesh's surface. This surface integral is then broken down into a sum of integrals over each individual triangle of the mesh.

Parametrization and Calculation

Each triangle in the mesh is parametrized using its vertices. This parametrization allows for the direct evaluation of the surface integral. The cross product involved in the calculation is constant across each triangle and can be efficiently computed from vertex data, focusing only on the relevant component.

Compact Formula and Efficiency

The direct evaluation of the integral leads to a compact formula for the volume. This final algorithm avoids numerical integration or differentiation. It operates with a single loop over the triangles, resulting in an O(n) complexity where 'n' is the number of triangles. Each per-triangle calculation is also efficient, involving a minimal number of additions and multiplications.

Performance Advantages

Compared to naive algorithms that might involve rendering and sampling the mesh, this method offers significant speed improvements. The total computational cost for a mesh of 'n' triangles is quantified by a specific number of additions and multiplications, indicating its high efficiency for volume computation.