Hexagonal Tessellation on a sphere

Question

I want to detect collision of a sphere with another object and to find out(show) the deformation of the sphere. I have come to know that hexagon(regular)tessellation of a sphere is the most appropriate one. What are the advantages of tessellating a sphere with regular hexagons over squares and triangles? How can I use this regular hexagon tessellation on the sphere to detect collision and find out in which part of the sphere deformation has occurred? Why regular hexagons are better than squares or triangles? I want a detailed explanation on this topic.

Answer 1

It is impossible to tessellate (regularly or otherwise) a sphere with hexagons, at least when three hexagons meet at each vertex.

If you have $F$ hexagons, this means you must have $3F$ edges (since each hexagon has six edges, shared by two hexagons) and $2F$ vertices (since each hexagon has six vertices, shared by three hexagons). Plugging into the Euler characteristic formula you get

$$V-E+F = 2F-3F+F = 0\neq 2$$

which cannot be a topological sphere.

What if you allow three or more hexagons to meet at a vertex, instead of exactly three? You get that $V \leq 2F$ and you're in the same boat, since now $V-E+F$ is still $\leq 0$.

To get Euler characteristic two you must therefore have some vertices where only two hexagons meet. For example, you could take two hexagons, glue them on top of each other, and call that a "sphere." I would consider any such tiling to be degenerate, but if that's what you really want, it is at least possible to construct.

Note that you could instead use a mix of hexagons and pentagons. These tesselation are well-known (consider the soccer ball, or geodesic dome).

---

Now back to your original question. I can't think of any plausible reason you would want a hexagonal (or mostly-hexagonal) tesselation of the sphere for simulation or collision detection purposes. If you have a complicated object, it's common to build a conservative collision cage around the object using discrete oriented polytopes (k-DOPs) and the common $18$-DOP will contain hexagons and squares. But I don't see why you'd want to discretize the object itself as a hexagonal mesh, especially if the object is going to deform, since you then have your pick of two unpleasant poisons: 1) maintaining a planarity constraint on the faces as the hexagons deform, or 2) allowing nonplanar hexagons and interpolating the boundary using your choice of generalized barycentric coordinates, and any choice you pick is going to do the exact opposite of simplifying collision detection.

Answer 2

A sphere cannot be tessellated using only regular hexagons. You need to place twelve pentagons with sides the same as those of the hexagons; the pentagon centers must be at the face centers of a dodecahedron. Then you can complete the tessellation using some number of hexagons; for example, I think the old-fashioned standard soccer ball uses 12 pentagonal and 20 hexagonal faces.

I strongly suspect, however, that you will have a better time with your collision detection and deformation algorithms if you then move to a triangular covering, by placing another vertex at the center of each such hexagon or pentagon, and connecting that vertex to the 6 or five corners.

The advantage of triangular tessellation is that for a hexagon, there can be multiple solutions to the local deformation, which would be easy to disambiguate by eye, but which require great care to reliably disambiguate algorithmically. You get the best of both worlds by basing the triangular tessellation on that nearly-regular hexagonal pre-tessellation, because a square pre-tesselation does not generalize to an arbitrarily fine grid, while the hexagonal one does.

Using triangular tessellation, you then can model collision deformation by simulating a damped stiff spring between each neighboring pair of vertices (on each colliding sphere), and giving vertices in different "spheres" a repulsive potential with force steeper than $1/r^2$ but with some cutoff range so that you don't have to sum forces over every pair of vertices. The spring stiffness, repulsion and range must be chosen, however, such the sort of collisions you want don't completely collapse any spring, and such that a foreign vertex coming in between 3 springs encounters enough net repulsion (in the collisions you are considering) to prevent it crossing through the plane of the triangle.