Finding Hexahedrizations for Small Quadrangulations of the Sphere

Authors: Kilian Verhetsel, Jeanne Pellerin, Jean-François Remacle


(The meshes above can be rotated by clicking on them and dragging your cursor.)

Suppose you drew a set of n quadrangles on a sphere, covering its entirety. How many cubes do you need to fill the interior of that sphere? This question is surprisingly difficult to answer, even with only a few quadrangles (the case n = 8 is notoriously hard, and of the 3 cases where n = 10, only one is easy to solve).

Our contribution to SIGGRAPH 2019 shows that with n quadrangles on the boundary, 78n combinatorial cubes (or hexahedra) are always enough. This is a significant improvement over the previous upper bound: 5396n (Carbonera and Shepherd, 2010). Our result is based on a proof by Erickson (2014): we computed hexahedral meshes of the two base cases that it uses (shown above).

In most cases, there are significantly smaller solution. The paper gives an algorithm to search for such solutions. This was fast enough to compute hexahedral meshes for all 54,943 quadrangulations of up to 20 quadrangles for which a solution exists. The worst case required only 72 hexahedra.

Paper: One machine, one minute, three billion tetrahedra

We recently published a paper on fast parallel 3D Delaunay triangulation in the International Journal for Numerical Methods.

The paper describe how we designed a library able to compute up to 65 million tetrahedra per second*.

*on an AMD EPYC 7551 (2×32 core)

Paper: There are 174 subdivisions of the hexahedron into tetrahedra

A new paper was published, wherein we enumerate all possible ways to subdivide a hexahedron into tetrahedra, and which of those subdivisions can be realized geometrically in 3-dimensional space.

The paper will be presented at SIGGRAPH Asia 2018.


Paper: A 44-Element Mesh of Schneiders’ Pyramid

We recently published a paper in which we describe a new mesh of Schneiders’ pyramid (see images below). The paper describes two new algorithms used to construct it:

  1. A procedure to enumerate all hexahedral meshes with a specific boundary
  2. A procedure which locally modifies a hexahedral mesh to reduce the number of hexahedra without changing the boundary.

Our implementation of the algorithms described in the paper and our results can be downloaded below.

Abstract: This paper shows that constraint programming techniques can successfully be used to solve challenging hex-meshing problems. Schneiders’ pyramid is a square-based pyramid whose facets are subdivided into three or four quadrangles by adding vertices at edge midpoints and facet centroids. In this paper, we prove that Schneiders’ pyramid has no hexahedral meshes with fewer than 18 interior vertices and 17 hexahedra, and introduce a valid mesh with 44 hexahedra. We also construct the smallest known mesh of the octagonal spindle, with 40 hexahedra and 42 interior vertices. These results were obtained through a general purpose algorithm that computes the hexahedral meshes conformal to a given quadrilateral surface boundary. The lower bound for Schneiders’pyramid is obtained by exhaustively listing the hexahedral meshes with up to 17 interior vertices and which have the same boundary as the pyramid. Our 44-element mesh is obtained by modifying a prior solution with 88 hexahedra. The number of elements was reduced using an algorithm which locally simplifies groups of hexahedra. Given the boundary of such a group, our algorithm is used to find a mesh of its interior that has fewer elements than the initial subdivision. The resulting mesh is untangled to obtain a valid hexahedral mesh.

Paper: Computing cross fields, a PDE approach based on Ginzburg-Landau theory

We developed an innovative way to compute cross fields in order to spawn points which are consistent with a square grid. The mathematical background is built step by step to highlight the meaningful use of Ginzburg-Landau functional. An interesting result is obtained over the sphere: the anti-cube. The computation is extended to asterisk fields for equilateral triangular grid.


view on GitLab

view on gitlab
HXTSortHextreme Sorting Library

HXTSort is a single header library including lightning fast Parallel Radix Sort macros.

It can sort 400 million integers per second on a laptop’s  i7-6700HQ and up to 1 billion integers per second on a Intel® Xeon Phi™  7210 ( 1.30GHz).


HXTSort is a lot faster than qsort
Because HXTSORT32_UNIFORM does not always pick the best underlying algorithm on the core i7, we manually chose the best of LSB32 and PARALLEL_HYBRID32.

It includes multiple  key-based algorithms for sorting data on any standard computer (single-node SMPs). It could also be a very good core algorithm for a MPI merge sort implementation for Clusters.

HXTSort will be used in our future Mesh Generation Library. A version of this library containing only a basic Mesher will be released soon.

Paper: Robust and efficient validation of the linear hexahedral element

We present a method to compute the true validity of hexahedra in an efficient manner. More than 6 million hexahedra are analyzed on a single core per second.

First paper: Combination of tetrahedra in hexahedra

We developed a method to very efficiently combine the elements of a tetrahedral mesh into hexahedra.  The new vertex based algorithm builds all the feasible potential hexahedra  under given quality constraints. Around 3 millions of potential hexahedra are generated in 10 seconds. A greedy combination is used to compute the final hex-dominant mesh.