Equal-area sparse spherical shell partitioning

Question

I'm trying to solve a particular problem that arose in a computer graphics context, but can be generalised to a bigger problem as well. I'm not entirely sure if this question belongs to MathExchange either, so any suggestions are greatly appreciated.

If you with to skip the preamble, fell free to go to the "Main Problem" section.

The original problem

(a little background, for the ones not inclined to computer graphics: bump-maps are simply computer images in which each pixel stores a normalised three-dimensional vector, instead of three discrete color intensity values)

I got an idea the other day, when trying to optimize bump/normal mapping on a very computing-power-restricted environment, to replace my RGB bump-map with an indexed image. This way, instead of calculating the lightning equation/dot product for each pixel on display, I would just need to calculate it for each normal stored on the image index, and replace the image index by the equivalent light intensity obtained for each normal when displaying the image. It has obvious shortcomings, such as the need for an infinitely distant (or parallel) light source (instead of point light sources), but for my purposes it works just fine.

So, in a new attempt to reduce even further the computing power required for the operation, and compress the map even further, I imagined what would be needed to generate an ideal index, given an space constraint (amount of stored normals). Turns out it's the very key idea about my question that will solve this as well.

The main problem

The above problem can be solved for N indexes if there's a way to partition a spherical shell of unitary radius into N equal-area shell segments/cuts, much like an optimised Voronoi Diagram, albeit in spherical space. A turtle shell is probably the best real-world analog to this idea:

My question basically boils down to, "Is there a way to partition a spherical shell into N polygonal segments, akin to a Voronoi Diagram (where the edges of the polygons themselves are straight arcs on the shell surface and the regions themselves are as "uniform" and sparse as possible on the shell surface), where each of those segments occupy exactly the same shell area?"

Considerations

• I assume a solution to this problem would be dependent on some sort of constraint, like a set of initial vectors or orientations. If possible, I'm asking for the method which requires the least amount of user-supplied data.
• Randomized methods are not an option; I'm looking for an exact and repeatable solution.

Answer 1

A similar problem has been studied before here: take a look at the last page of the article, where the partitions of the sphere are presented. The problem is to minimize the sum of polygon perimeters while keeping constant areas. The result is a hexagonal + $12$ pentagons packing (for $N \geq 14$). I'm not sure how high you could get with $N$. In the paper they do it for $N \leq 32$. For large values it can be hard to do such an optimization.

I did some work recently on this: http://www.lama.univ-savoie.fr/~bogosel/modica_mortola_sphere.html The same observation: it works until $N=32$, maybe even higher, but for arbitrarily large $N$ the computations get slow.

Another uniform partition of the sphere in equal areas is presented here: http://fr.mathworks.com/matlabcentral/fileexchange/13356-eqsp--recursive-zonal-sphere-partitioning-toolbox This is fast, even for $N$ greater than a milion. The advantage is that it works with spherical rectangles, so each set of the partition is governed by only a few parameters.

Answer 2

This doesn't work for arbitrary $N$, but ...

Take an inscribed icosahedron, and project its edges outwards onto the surface of the sphere. This will give you 20 identical "equilateral" spherical triangles that cover the sphere. If you need more triangles, subdivide these 20. Division into 3 is easy, so you can get partionings that consist of 20, 60, 180, 540 pieces, and so on.

You could do the same sort of thing starting with a tetrahedron, actually. This would give you partions with 4, 12, 36, 108 pieces, and so on.

In fact, I guess you could use any Platonic solid as a starting point.

Subdividing triangles into 4 smaller ones (rather than 3) might be better, since the smaller triangles will then be more nearly equilateral.

Answer 3

If it's just about equal area pieces the following is simplest:

Let $N=p\cdot q$. Divide the interval $[{-1},1]$ on the $z$-axis into $p$ equal parts $[z_{k-1},z_k]$ and intersect the sphere $S^2$ with the equidistant planes $z=z_k$. Then intersect $S^2$ with $q$ meridianal half planes at equal angles ${2\pi\over q}$. This will produce $2q$ spherical triangles and $N-2q$ "spherical rectangles", all of the same area.

When you want "rounder" pieces, look up here:

http://en.wikipedia.org/wiki/Fullerene

Here the sphere is tessellated in a honeycomb manner, with twelve exceptional pentagons.