Lightweight Implicit Approximation of the Minkowski Sum of an N-Dimensional Ellipsoid and Hyperrectangle

Abstract

This work considers the Minkowski sum of an N-dimensional ellipsoid and hyperrectangle, a combination that is extremely relevant due to the usage of ellipsoid-adjacent primitives in computer graphics for work such as 3D Gaussian splatting. While parametric representations of this Minkowski sum are available, they are often difficult or too computationally intensive to work with when, for example, performing an inclusion test. For performance-critical applications, a lightweight approximation of this Minkowski sum is preferred over its exact form. To this end, we propose a fast, computationally lightweight, non-iterative algorithm that approximates the Minkowski sum through the intersection of two carefully constructed bounding boxes. Our approximation is a super-set that completely envelops the exact Minkowski sum. This approach yields an implicit representation that is defined by a logical conjunction of linear inequalities. For applications where a tight super-set of the Minkowski sum is acceptable, the proposed algorithm can substantially improve the performance of common operations such as intersection testing.