Progressive Convex Hull Simplification Volume: 45 Issue: 5

Alec Jacobson University of Toronto · 2026

Read Progressive Convex Hull Simplification Volume: 45 Issue: 5 by Alec Jacobson University of Toronto (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-14468.txt.

Introduction

Jacobson tackles conservative simplification of convex hulls down to a set number of half-spaces while adding as little volume or surface area as possible. Hull complexity grows linearly with input, so working in the dual representation, he offers an efficient greedy optimization that scales near-linearly with input size. Existing methods fall short on efficiency, tightness, or safety by comparison. Tests across varied shapes and downstream uses, from collision detection to ray intersection and distance computation, show the method succeeding.

Catalog record

CREATORAlec Jacobson University of Toronto
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE32822
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2604.14468

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Progressive Convex Hull Simplification Volume: 45 Issue: 5 Alec Jacobson University of Toronto Abstract Convex hulls are useful as tight bounding proxies for a variety of tasks including collision detection, ray intersection, and distance computation. Unfortunately, the complexity of polyhedral convex hulls grows linearly with their input. We consider the problem of conservatively simplifying a convex hull to a specified number of half-spaces while minimizing added volume or surface area. By working in the dual representation, we propose an efficient O ⁡ ( n ​ log ⁡ n ) O(n\log n) greedy optimization. In comparisons, we show that existing methods either exhibit poor efficiency, tightness or safety. We demonstrate the success of our method on a variety of input shapes and downstream application domains. \SpecialIssueSubmission † † year: 2026 † † year: 2026 † † editors: M. Skouras and M. Livesu † † subject: Eurographics Symposium on Geometry Processing CGF Vol No † † teaser: Our convex hull simplification iteratively removes the next halfspace that would add the least amount of volume. This results in very tight fitting hulls (under 5% increase) down to a small number of faces (18). Even for an extreme simplification (6 faces), the simplified hull is a modestly tighter fit than an oriented bounding box (1.61× vs. 1.72×). 1 Introduction Convex hulls are — by definition — the tightest convex bounding volume of a shape. This makes them useful as primitives in bounding volume hierarchies or directly as broadphase proxies for a variety of shape query tasks including ray intersection, collision detection & handling, distance computation, and sampling. Unfortunately, the complexity of a polyhedral convex hull grows linearly with that of the shape it encloses: a surface mesh with n triangles will generally induce a convex hull with O(n) faces. For example, the convex hull of the modest triangle mesh in Figure has over 2,000 faces. Compared to the fixed-complexity of simpler bounding boxes or k -DOPs, the complexity of convex hulls slows down their promise of acceleration as a bounding volume. Convex hull simplification methods exist, but their simplified hulls are either no longer guaranteed to contain the input shape or sacrifice the tightness of the hull by adding too much volume or surface area. These issues are compounded for convex hulls of subparts of a shape during approximate convex decomposition (see Figure 1 ). Figure 1: Our simplification is a natural drop-in to approximate convex decomposition methods, e.g., CoACD [ 30 ] . Their software optionally allows decimation (vertex dropping) as a post-process, but results in gaps between hulls, which permit false negatives during collision handling. Our simplification is tight and safe. In this paper, we build on the theoretical results promising the effectiveness of successive halfspace removal (e.g., [ 22 , 16 , 17 ] ) and present a practical conservative convex hull simplification heuristic based on greedy halfspace removal using a priority queue in the style of triangle mesh simplification [ 12 , 8 ] . By utilizing the duality of convex polyhedra, the computation of each candidate halfspace removal is not only efficient (requiring only local information) but also simple to implement robustly. The simplified hull remains conservative — strictly containing the input hull — at every step. Our simplified convex hulls are significantly tighter than alternative heuristics. Our optimization-based approach lends itself to customization, e.g., favoring minimum surface-area instead of minimum-volume, constraining selected faces on the output, inner approximations instead of outer. We demonstrate the effectiveness of our simplification on a variety of input shapes and as part of a large bounding volume hierarchy and approximate convex decomposition workflows. Our source code is released open source at https://github.com/[redacted]/progressive-convex-hull-simplification (see supplemental for now). 2 Background We are interested in polyhedral convex hulls bounding a finite set of points or a triangulated mesh. These convex hulls are polyhedra with finite vertices connected by (possibly non-triangular) faces. Methods for hull simplification differ primarily based on whether the hull is represented by its supporting vertices (V-representation) or as a set of intersecting halfspaces corresponding to each face-plane (H-representation). Before discussing related work, we lay out some foundations. Common convex hull algorithms (e.g., [ 2 , 6 ] ) and implementations (e.g., CGAL , QHull ) work with V-representations for input and output: given as input a set of 3D points, return as output a set of faces indexing those vertices. However, downstream applications will often make use of the output’s H-representation, converting each face i to a plane equation defined by \mathbf{x}\cdot\mathbf{n}_{i}+b_{i}\leq 0 , where \mathbf{n}_{i} and b_{i} are the normal to the plane and its distance (as a multiple of \mathbf{n}_{i} ) from the origin. For example, to test if two convex shapes overlap we can gather the halfspaces of their H-representations and determine if the total intersection is empty by solving a pure-feasibility linear program. \displaystyle\text{find }\mathbf{x}\in\mathbb{R}^{3}\quad\text{subject to }\mathbf{n}_{i}\cdot\mathbf{x}\leq-b_{i}\quad\forall i (1) where i runs over total m halfspaces gathered from both convex shapes. This fixed dimension problem can be solved very efficiently in O(m) time [ 25 ] . As we’ve seen, any V-representation output hull can be easily converted to a H-representation. It’s also straightforward to bootstrap any convex hull algorithm to work with halfspaces as input by leveraging convex duals (see, e.g., [ 9 ] for a complete reference). Suppose we’re given a set of n halfspaces (see 2D inset). We can compute the convex set forming the intersection of these halfspaces by first choosing a center point \mathbf{c}\in\mathbb{R}^{3} known to lie inside the resulting intersection. For each primal halfspace , we construct its dual vertex about this center point via: \mathbf{\phi}_{i}=\frac{-\mathbf{n}_{i}}{\mathbf{n}_{i}\cdot\mathbf{c}+b_{i}}. (2) Now, we run any V-representation convex hull algorithm on these \phi_{i} vertices, producing a list of face indices referencing them (see 2D inset). Dual vertices incident on these faces correspond to primal halfspaces contributing to the intersection’s surface; unreferenced (interior) dual vertices correspond to halfspaces too far outside the intersection to matter (grey in insets). Each dual face’s plane defines a dual halfspace , corresponding to a primal vertex , via: \mathbf{v}_{j}=\mathbf{c}-\frac{\mathbf{\eta}_{j}}{\beta_{j}}, (3) where \mathbf{\eta}_{j} and \beta_{j} are the normal and distance (as a multiple of \eta_{j} ) from the origin of the j th dual halfspace. The connectivities of the primal and dual hulls are dual in the typical fashion [ 9 , 11 , 19 , 14 ] : i.e., edges between vertices of the primal mesh correspond to face-adjacency in the dual mesh, and vice versa . Exploiting the dual-representation allows construction of the polyhedral intersection of primal halfspaces without any delicate intersection constructions or mesh arrangements (e.g., [ 31 ] ). Common convex hull implementations (e.g., CGAL , QHull ) offer halfspace intersection routines implemented in this dual fashion. The choice of center point \mathbf{c} doesn’t matter so long as its interior. In practice, Eqs. 2 and 3 become numerically sensitive as \mathbf{c} gets too close to any halfspace boundary. For a safe and efficiently identified choice (or to determine that the halfspace intersection is empty or unbounded), we can solve a linear program to construct the center of the largest inscribed sphere, the Chebyshev center: \displaystyle\mathop{\text{maximize}}_{\mathbf{c}\in\mathbb{R}^{3},r\geq 0} \displaystyle\quad r (4) subject to \displaystyle\quad\mathbf{n}_{i}\cdot\mathbf{c}+\|\mathbf{n}_{i}\|r\leq-b_{i}\quad\forall i. (5) Once again, the dimension of this

Read the complete text