S. Mitchell proved that a necessary and sufficient condition, for the existence of a hexahedral mesh constrained to quadrilateral tessellation of the sphere, is that an even number of quadrilaterals in the constraining tessellation. For example, the constrained hexahedral problem for the pyramid in figure 1 can be solved, but no solution has ever been published. A construction for this specific problem will be presented in this report.

The construction of the hexahedral mesh of figure 1 will be done in two steps. First, a simple construction will be provided for the general case of S. Mitchell's result. This simpler is given below

( Four-Split Construction ) For a given quadrilateral tessellation of sphere, split each quadrilateral into four quads by splitting the midpoint of each edge and connecting to the midpoint of the quadrilateral. Figure 2 below illustrates this operation. There is a hexahedral mesh containing 16*<number of quadrilaterals before four-split operation> hexahedra.

(The group of four cells that result after the four split operation on a given quadrilateral will be referred to as the Four Split Cell.) Second, the Four-Split Construction will be used to solve the hexahedral mesh for the pyramid in figure 1.

For example, figure 3 below illustrates the result of a four split on a given tessellation.

The dashed lines represent the added edges. The cells of four new quads will be referred to as the four split cells. The new quadrilateral mesh will be referred to as a Four Split quadrilateral mesh.

To provide the construction

• First, the steps necessary to construct the hexahedral mesh constrained to a Four Split quadrilateral mesh will be given by assuming that the hexahedral mesh for pyramid in figure 4 below is provided.
• Finally, the construction of the hexahedral mesh for the pyramid in figure 4 will be given.

Place two meshes to the pyramid from figure 4 on top of any two adjacent Four Split Cells as illustrated in figure 5.

The quadrilaterals seem to be lying on a plane, but this is just drawn for illustration purposes. In reality, the adjacent Four-Split Cells are not on the same plane at all.

Next, merge the apexes of the two pyramids and the two matching vertices. Thus, the faces that share the same edge on the boundary are merged. This can be done because the triangular looking quadrilaterals have a perfect topological match. This procedure can be performed across all the quadrilaterals of the faces, and, finally, all the apexes could be placed in the center of the sphere.

To construct the hexahedral mesh for figure 4, first extruded a given Four-Split cell as in figure 6 below

 Merge the four corners of the cell into one vertex, and two of the midpoints as shown below.

The result is a highly distorted mesh, that could be improved if desired by offsetting the hexahedron inwards as shown in the next figure.

The boundary of the pyramid looking shape is not convex because of the merge of vertices 5 and 6 mentioned above. To finish our construction, the hexahedral mesh illustrated in figure 7 is shrunk and placed in the interior of the quadrilateral mesh illustrated in figure 9.

Connect the apex of pyramid in fig. 7 to the apex in figure 4, the mid-edges of the faces to the mid-edges of the other pyramid, the corners to the corners, and so on. The resulting operation is equivalent to adding a boundary layer of hexahedra around the concave pyramid. Thus, the construction is finished.

Two basic topological transformations will be discussed before entering into the details of the construction. These topological transformations are divided into two types.

• Add layers to the quadrilateral boundary. The quadrilaterals can be layered. This is an operation in which a selected set of quadrilaterals are extruded inwards by adding a layer of hexahedral elements without collapsing
• Collapse a quadrilateral boundary. The quadrilaterals can be collapse. This is don by adding hexahedral elements on a selected set of quadrilaterals and merging faces of the quadrilaterals.

By adding a collection of hexahedra to a quadrilateral mesh, the appearance of the quadrilaterl mesh is altered. For example, in the quadrilateral given in figure 10 below, a face is selected, and a hexahedron is added to the interior is added.

  In the example above, the faces containing the vertices {10, 11, 12, 6,5,4} will be identified as the bottom face, and the remaining quadrilaterals will be referred to as the top. In this manner, if one were to look at the top and the bottom from the interior, this is what will be seen

If one were to add a hexahedron at face {4, 5, 11, 10 } inwards by adding four vertices { 13, 14, 15, 16 }, and add another hexahedron at face {5,6,12,11} by adding four vertices {17, 18, 19, 20} and connecting them according to figure 12 below,

  In the example above, the faces containing the vertices {10, 11, 12, 6,5,4} will be identified as the bottom face, and the remaining quadrilaterals will be referred to as the top. In this manner, if one were to look at the top and the bottom from the interior, this is what will be seen

one has effectively replaced the original constrained problem by a new one. In the sense that, the constrained problem illustrated by figure 11 has a solution if the one in figure 13 does.

Thus problem 13 could be considered a topological transformation of the constrained problem given by figure 11.

The operation illustrated in this example will be known as a quadrilateral layer operation.

Suppose that two hexahedra are added to the example illustrated in figure 10. But the two hexahedra share two faces this time as illustrated below.

 A look from the interior would yield to the following views:

As in the addition of layers to the quadrilateral boundary, the constrained mesh of figure 15 can be obtained if and only if the constrained hexahedral mesh exist for the example in figure 10.

From now on, instead of illustrating hexahedra elements, the figures of the type "Top View/Bottom View" will be used.

If one were to look at the faces from the interior of the pyramid, this is what will be seen.

The first step is to add layers to the quadrilateral boundary as described earlier. The top and bottom faces can be extruded internally by adding boundary layers, but without forcing the faces of the extruded top to match the adjacent faces on the bottom. The picture below illustrates the idea

If one were to look at the interior of the pyramid after this operation, one would see the following quadrilateral faces:

Hence, the interior of the pyramid has been filled so far with twelve hexahedra. Next, one can collapse the quadrilateral faces by merging the top faces by merging the faces opposed to the diagonal, in the following manner:

Similarly the bottom faces can be collapsed. The result of this operation is that the original faces of the interior of the pyramid has been extruded to look like this

The black circles represent vertices of the quadrilaterals that look like triangles.

The interior of pyramid has been extruded by some horribly distorted hexahedral elements. But, if one would consider the dual of the graph one notices that there no curve is self-intersecting unlike the original set of quadrilaterals. The dual is illustrated below

There are three non-self-intersecting oriented loops. It is possible now to transition the faces from one to four cells. The transition is done in two steps. The one-to-two face transition displayed below is used in two stages. The transition cells are placed as the figure below shows; The transition faces is oriented along the direction of the dual curves, and the vertically split face is position to the right of the curve. This will force on all the curves above the transition splits to match perfectly.

The faces along the direction of the black dual dashed curves are transitioned from one to two, and, afterwards, the red and blue curves are transitioned.

Thus, we have successfully split the faces into modules of four, and, by the four-split result in the previous section, the pyramid of figure 1 can be solved and is filled with a few hundred hexahedra.