Poliedro Convexo

Convex polyhedra in practice: the stuff nobody tells you about

A convex polyhedron is a solid bounded entirely by flat polygonal faces where, for every pair of points inside the solid, the line segment connecting them stays completely within the solid. That's the textbook definition. The practical definition is: if you can draw any chord between two interior points without piercing a face, it's convex. Non-convex shapes—think of a torus or a star-shaped dodecahedron—fail this test immediately. Most real-world geometry problems start here because convexity lets you skip half the edge cases.

Poliedro convexo: the convex hull pipeline

In my work, the most common scenario involves computing a convex hull from a noisy point cloud. You get a set of vertices—often from a 3D scanner or a procedural generation step—and you need the convex polyhedron that encloses them. The standard approach uses incremental algorithms or the divide-and-conquer method, both of which run in O(n log n) time for the general case. Qhull is the library I reach for. It handles degenerate inputs better than most alternatives, though not perfectly. The tricky part isn't the algorithm itself. It's what happens when your point cloud contains coplanar vertices or near-collinear arrangements. I spent three days debugging a collision detection system where the convex hull computation was producing unexpected internal faces. The root cause was a set of points lying almost exactly on a plane due to floating-point precision drift. Qhull was splitting them into multiple coplanar triangles instead of merging them into a single quadrilateral face, which then cascaded into incorrect normal calculations downstream. The workaround was simple but unintuitive: I tolled the input by running a voronoi-based simplification pass before the hull computation, which collapsed the near-coplanar points into proper representatives. This cut the face count from about 4,200 to 890 and eliminated the normals issue entirely. Processing time dropped from roughly 340 milliseconds per batch to about 12 milliseconds.

Why convexity matters beyond the definition

Convex polyhedra have properties that non-convex ones simply don't. The most immediately useful one is that the convex hull of any set of points is unique. There's only one convex polyhedron enclosing a given point set, and it's well-defined. This uniqueness is what makes convex hulls useful as bounding volumes in rendering and physics engines. A non-convex bounding shape requires partitioning or hierarchical approximation, which introduces ambiguity and extra overhead. Euler's formula—V minus A plus F equals 2—holds for every convex polyhedron. I find it more practical to use it in reverse: given vertex and face counts, you can verify whether a mesh is topologically valid before running expensive intersection tests. If V - A + F doesn't equal 2, something is wrong with the mesh and further computation is wasted. In one project, I rejected a procedurally generated 14,000-face mesh in under a millisecond after checking Euler's relation, saving maybe forty seconds of wasted rasterization work.

Another property worth knowing: the separating axis theorem applies directly to convex polyhedra. Two convex polyhedra are non-intersecting if and only if there exists a plane that separates them. The candidate axes to test are the face normals of each polyhedron and the cross products of edge pairs. For two convex shapes, this gives you an exact intersection test with no false positives. That said, the test count grows quadratically with the number of faces, so it's not free. A pair of polyhedra with 500 faces each requires testing 500 normal axes plus up to 250,000 edge cross products. In practice, you cull with broad-phase bounding volumes first and only run SAT on promising pairs.

Common pitfalls that aren't obvious

One frequent mistake is assuming that a mesh with all outward-facing normals is convex. It isn't necessarily. You can have a concave dent in the geometry and still have every normal point outward relative to its local face. The only way to verify convexity properly is to check that all dihedral angles are less than or equal to 180 degrees, or equivalently, that every face plane leaves all other vertices on the same side. I wrote a validation function that checks this by testing each face against all vertices. It runs in O(f times v) where f is the number of faces and v is the number of vertices. For a typical mesh of a few thousand elements, this takes a few milliseconds on a modern CPU. Another pitfall involves numerical tolerance. When working with floating-point coordinates, two vertices that should be identical may differ in the seventh or eighth decimal place. This creates sliver faces—triangles with near-zero area that confuse most mesh processing tools. The fix is to snap vertices that are closer than a small epsilon distance to the same position. The epsilon value depends on your scale. In a modeler working at unit scale, 1e-6 works well. In a CAD system handling millimeter-scale parts, 1e-3 is more appropriate. Pick based on your coordinate range, not arbitrarily.

When convex hulls fail you

Convex hulls are not a universal solution. If your shape has genuine concavities that carry geometric meaning—like a mechanical part with a channel or a character model with limbs—the convex hull will overestimate volume and lose important detail. In those cases, you need either a non-convex decomposition or a different bounding volume hierarchy. Convex decomposition tools like HACD or the eigenpoly method exist, but they introduce their own failure modes: degenerate slices, inconsistent normals, and sometimes exponentially growing face counts depending on the input topology. For collision detection specifically, many teams use a convex hull as the coarse approximation and fall back to triangle-level tests only when the hull test indicates a potential overlap. This two-tier approach typically reduces average collision query time by an order of magnitude compared to brute triangle tests, while keeping worst-case latency bounded.

A quick reference for implementation

If you're implementing this from scratch, here's what I consider the minimal viable pipeline. Read your point set. Snap close vertices using an epsilon appropriate to your scale. Compute the convex hull using a library rather than writing your own—Qhull, CGAL, or libigl are solid choices. Validate the result with Euler's formula. Run the face-plane consistency check to confirm convexity. Test your output against a known ground truth, like a cube or an icosahedron, before trusting it on real data. Skipping the validation step is how I once shipped a physics system with inverted normals on half the faces, and the bugs took two weeks to track down.