--- title: "Dual Polytopes for Mesh Hull Simplification" description: "Learn how the polar dual of a convex polytope works via support function level sets, and how dual transformations simplify convex hulls for collision detection and mesh processing." slug: "dual-polytopes-for-mesh-hull-simplification" published: true read_time: 7 created_at: "2026-09-30 21:37:09.654 +0000 UTC" updated_at: "2026-09-30 21:37:09.658 +0000 UTC" author: "Typen" author_url: "https://typen.blog/@typen" tags: - "Featured" - "Open Source" - "AI" --- # Dual Polytopes for Mesh Hull Simplification Learn how the polar dual of a convex polytope works via support function level sets, and how dual transformations simplify convex hulls for collision detection and mesh processing. ![https://media.typen.blog/img/id/01a0f43f-fc87-708c-9bf2-7731de5566aa](trendbot-3574809464.webp) ## Why Simplify Convex Hulls? Convex hulls are a workhorse of geometry processing. They show up in collision detection, where a cheap bounding volume is often preferable to the full mesh; in physics, where contact resolution benefits from a small set of face planes; and in mesh processing, where a simplified hull can stand in for a detailed surface during broad-phase queries. A common way to simplify a convex hull is to start from its face planes, merge or drop some of them, and then rebuild the hull from the remaining planes. That rebuild step is where things get interesting. There are two standard approaches: 1. Treat each plane as a giant quad and clip it against every other plane, repeating for each plane. 2. Take the convex hull of the face normals, which is the convex hull of the dual polytope. The second approach is elegant but often poorly understood. This article explains the dual polytope using the level sets of the support function, following the explanation by Cairn Overturf, and then connects it back to hull simplification. ## The Support Function Let \(P\) be a convex polytope with vertices \(v_1, v_2, \dots, v_k\) and the origin inside it. Its support function is: \[ h(y) = \max_{x \in P} (x \cdot y) = \max_i (v_i \cdot y) \] The support function is piecewise linear. Its linear regions are wedges, one per vertex, where wedge \(i\) is the set of directions whose support vertex is \(v_i\). On the sphere, these wedges are the regions of the Gauss map. ### Level Sets of the Support Function Consider the level sets of \(h\). Because \(h\) is linear inside each wedge, a level set of \(h\) is flat inside each wedge and can only bend on the seams between wedges. This gives two key properties: - The wireframe of a level set projects onto the Gauss map. - Its faces sit over the regions of the Gauss map, one per vertex of \(P\). - Its vertices sit over the points where the arcs meet, one per face of \(P\). For the cube \([-1,1]^3\), the support function is \(h(y) = |y_1| + |y_2| + |y_3|\), and its level sets are nested octahedra. The octahedron face with normal \(v\) sits over the highlighted region of \(v\) in the Gauss map. ## The Polar Dual The polar dual of \(P\) is defined as: \[ P^{\circ} = \{y : x \cdot y \leq 1,\ \forall x \in P\} \] The central theorem is: for \(c > 0\), the level set \(\{h \leq c\}\) is \(cP^{\circ}\), and \(P^{\circ}\) is a convex polytope. ### Faces and Vertices Swap The faces of \(P^{\circ}\) are the vertices of \(P\). Face \(i\) lies in the plane \(v_i \cdot y = 1\), so its normal is \(v_i\). Conversely, the vertices of \(P^{\circ}\) are the faces of \(P\). A face of \(P\) with plane \(n \cdot x = d\) becomes the vertex \(n/d\). Projecting the edges of \(P^{\circ}\) onto the sphere gives the Gauss map. ### Why the Theorem Holds From the definition of \(h\): \[ h(y) \leq 1 \iff x \cdot y \leq 1 \ \text{ for all } x \in P \] so \(\{h \leq 1\} = P^{\circ}\). Since \(h(ty) = t\,h(y)\) for \(t > 0\), the other level sets are scaled copies: \[ \{h \leq c\} = cP^{\circ} \] Because \(h\) is a max of linear functions, \(P^{\circ} = \bigcap_i \{y : v_i \cdot y \leq 1\}\) is an intersection of finitely many half spaces. It is bounded because the origin is inside \(P\), so \(h(y) \geq m \lVert y \rVert\) for some \(m > 0\). On wedge \(i\), \(h(y) = v_i \cdot y\), so inside that wedge the boundary of \(P^{\circ}\) is the plane \(v_i \cdot y = 1\). Different vertices give different planes, so neighbouring faces meet at an angle along the seams. By homogeneity, every ray from the origin crosses the boundary of \(P^{\circ}\) exactly once, at \(y/h(y)\). Projecting onto the sphere sends each face of \(P^{\circ}\) to its wedge and each edge to a seam, which is the Gauss map. The vertices of \(P^{\circ}\) lie where three or more wedges meet, which is along the face normals \(n\) of \(P\). Along that ray: \[ h(tn) = t\,d = 1 \implies t = \frac{1}{d} \] so the vertex is \(n/d\). ## Back to Hull Simplification Now the practical picture becomes clear. Merging or dropping face normals edits the vertices of \(P^{\circ}\), and taking their convex hull rebuilds \(P^{\circ}\). By the theorem, each face \(w \cdot y = 1\) of the new hull gives the vertex \(w\) of the simplified polytope. In other words, the dual transformation turns a plane-merging problem into a point-merging problem. Instead of clipping giant quads against each other, you manipulate points in the dual space and rebuild a convex hull. That is often simpler to implement and can be more robust, since convex hull algorithms are well studied and widely available. ### Practical Implications For collision detection, a simplified hull with fewer face planes means fewer separating-axis tests and cheaper contact generation. The dual approach lets you control the face count directly by controlling how many dual points you keep. Dropping a dual point removes a face from the primal hull; merging dual points approximates nearby face normals. For mesh processing, the dual view connects naturally to the Gauss map. Simplifying the hull is equivalent to simplifying the spherical image of its faces. If you are already working with normal clustering or spherical Voronoi diagrams, the dual polytope gives you a consistent geometric framework. ### Tradeoffs - **Numerical stability:** The dual transform \(n/d\) requires \(d \neq 0\). If a face plane passes through the origin, the dual point goes to infinity. In practice, you translate the polytope so the origin is strictly inside before dualizing. - **Rebuild cost:** Taking a convex hull in dual space is not free, but it replaces a sequence of clipping operations that can be harder to parallelize and more prone to degeneracies. - **Approximation quality:** Merging dual points is a heuristic. The resulting primal hull may not contain the original, depending on how you merge. If containment matters, you need to be careful about which dual points you combine. - **Topology changes:** Dropping a dual point can change the combinatorial structure of the hull. This is usually desirable for simplification, but it means you cannot assume a one-to-one mapping between original and simplified faces. ## A Minimal Dual Rebuild The core operation is small enough to sketch. Given a set of face planes \((n_i, d_i)\) with the origin inside the polytope: ```python # Each plane is n . x = d, with d > 0 after translating the origin inside. dual_points = [n / d for (n, d) in planes] # Optionally merge or drop dual_points here. # Rebuild the dual polytope. new_dual = convex_hull(dual_points) # Each face w . y = 1 of new_dual gives a vertex w of the simplified primal hull. simplified_vertices = [face.normal for face in new_dual.faces] ``` The exact API depends on your geometry library, but the structure is the same: transform planes to points, simplify in dual space, rebuild, and read back vertices. The theorem guarantees that the faces of the rebuilt dual correspond to vertices of the simplified primal polytope. ## Summary The dual polytope is not just an abstract curiosity. It is the level set of the support function, and its faces and vertices are the vertices and faces of the original polytope, swapped. That swap is what makes it useful for hull simplification: you can edit face normals as points, rebuild a convex hull, and recover a simplified primal hull. For collision detection and mesh processing, this offers a clean alternative to plane-clipping rebuilds, with its own set of numerical and approximation tradeoffs to manage.