Polyhedra: Nature’s Answer to Meshing

By Stephen Ferguson

In Cole Porter’s famous song: “... Birds do it, bees do it. Even educated fleas do it….” Inreality, however, though bees are very good at it, birds and fleas donot do much polyhedral meshing—but then, up until recently, neitherdid most CFD engineers.

Whether polyhedral meshes are the best for all types of CFDcalculations still remains to be proved (although many think that theevidence in their favor is rather compelling). Nature however, has cometo her own conclusions and is full of examples of 2D and 3Dtessellations that bear remarkable similarities to polyhedral meshingtechnology, which — ahem — the company I work for, CD-adapco develops.In contrast, you’ll find that there are relatively few examples ofhexahedral and tetrahedral mesh structures that occur naturally.

So, how is it that honeybees (average brain size 1g) manage to out-meshthe vast majority of CFD engineers (average brain size 1250g)? Theanswer, then, is not that bees are more intelligent than engineers,albeit there are a few notable exceptions.





Polyhedral mesh of a tortoise shell (left) and the real thing (right). Click images to enlarge.

Whereas CFD and associated meshing technology has been around for just30 years, bees benefit from several billion years of evolution. From apurely evolutionary viewpoint, the hexagonal structure of the honeycombis the endpoint of an exercise in energy optimization. The walls ofeach honey cell are fashioned from wax and are manufactured to a hightolerance (within 0.2% of their 100-micron thickness). Creating thiswax costs energy that could be better used making honey to rear thenext generation of bees. As Charles Darwin wrote:

With respect to the formation of wax, it is known that bees are oftenhard pressed to get sufficient nectar ... it has been experimentallyproved that from 12 to 15 pounds of dry sugar are consumed by a hive ofbees for the secretion of a pound of wax.

Darwin also described the honeycomb as “a masterpiece of engineering” that is “absolutely perfect in economizing labor and wax.”

Biologists have long contended that the honeycomb was the idealstructure for containing the maximum amount of honey while containingthe minimum amount of wax. However, mathematical proof of thisso-called “honeycomb conjecture” was a long time in coming. Theconjecture, which has been a subject of mathematical curiosity sincethe third century AD, was not proved until June 1999, when Thomas C.Hales of the University of Michigan, finally demonstrated conclusivelythat “a hexagonal grid represents the best way to divide a surface intoregions of equal area with the least total perimeter.”

As good as honeybees might be at meshing in two dimensions, mostpractical CFD work requires 3D meshing. (This might offer a degree ofrelief to any CFD engineers who are nervous about losing their job to aswarm of inexpensive meshing bees.)

In the same way as bees benefit from minimizing the amount the amountof wax used in producing a certain volume of honey, face-addressing CFDsolvers benefit from minimizing the number of faces used in acomputational mesh for a given mesh resolution. (Using face-addressing,the solver must loop over all cell faces at every solutionlevel—minimizing the number of faces obviously has a huge payback interms of solver efficient.)

From this point of view, tetrahedra are the worst type of computationalcell. As the lowest-order polyhedron, they fill space less efficientlythan any other element. If bees worked in three dimensions, theywouldn’t use tetrahedra, as the cost of wax to honey would be too high.Although hexahedra are better from this point of view, they too are farfrom the ideal.

The obvious question is therefore: Which type of mesh has the fewestnumber of faces per unit volume? Once again nature has the answer….

In 1887 Lord Kelvin became intrigued by the packing of bubbles in aperfect foam — one in which all bubbles had equal volume. He askedhimself “How would bubbles of equal volume pack together to give theleast possible amount of surface film between them?”





On the surface a polyhedral mesh resembles a honeycomb, but inside … Click images to enlarge.


His answer was a 14-sided polyhedron that he painfully named the"tetrakaidecahedron.” This element was appealing because it led to aregular symmetric partitioning of space—offering an apparentimprovement over nature, which, in real soap foams, uses a combinationof irregular polyhedrons.




... the cells are packed like soap bubbles. Click images to enlarge.


The tetrakaidecahedron stood as the best way of partitioning spaceuntil 1994 when physicists Denis Weaire and Robert Phelan rejectedKelvin’s symmetrical partitioning in favor of a more nature-inspiredsolution. The so-called Weaire-Phelan structure is a mixture of 12- and14-sided polyhedra that partitions space 3 percent more efficientlythan Kelvin’s foam.

Well, polyhedral meshes typically consist of cells of 12 and 14 faces(although the number of faces is unrestricted). This means that theyfill space in close to the most efficient way possible. For a givenresolution level, a mesh consisting of polyhedral cells has fewer facesthan a mesh of any other cell type.

Apart from the obvious benefits of economy, polyhedral meshes provideother advantages too. Because each polyhedral cell has more faces, italso has more neighbors than traditional cell types.  Atetrahedral cell communicates with only four neighbor cells, and ahexahedral just six. In both cases this limits the influence of eachcell to just a few neighbors. By contrast, each polyhedral cell has onaverage 12 or 14 neighbors. The net result of this is that informationpropagates much more quickly through a polyhedral mesh, ultimatelyleading to an increased rate of convergence.

In the same way that a polyhedral cell “speaks” to more of itsneighbors than other cell types, it also “listens” to information frommore of them. Because each polyhedral cell receives information frommore of its surroundings, the cell-centered values calculated for thecell are more accurate than for other types.

The downside? We’re not sure that there are any. While a flow-fittedhexahedral meshes still offers some advantages, they are difficult andexpensive to create (and if you know how to make your mesh trulyflow-fitted, you probably don’t need to run the calculation in thefirst place). Polyhedral meshes can be created at the click of a buttonand have advantages in efficiency and accuracy.

Sometimes nature knows best.

Stephen Ferguson is a senior consultant engineer with CD-adapco inLondon. Prior to joining CD-adapco, Stephen worked for a majorautomotive company and for Europe’s largest engineering consultancy. Heis currently CD-adapco’s sector manager for the building services andbiomedical industries. Stephen received an MSc in computationalfluid dynamics from Imperial College London in 1998. Send your commentsabout this article through e-mail by clicking here. Please reference"Polyhedra, November 2006” in your message.

CD-adapco
London, UK

Here are a couple of more examples of polyhedra in nature. Click images to enlarge.