Mesh conversion: 6 quad faces == 1 hex volume
 

I am trying to build a volume mesh from a surface mesh containing all the cell-faces definition.
This translates into reconstructing the faces connectivity which defines the volume elements.
I other words, I have to find out which tuple of 6 quad-faces defines a hex-cell, and write out the result in some mesh format (CGNS, Nastran, whatever).
This seems a trivial operation: the haxahedrons are there, only... I need to "fill" them.

Does anybody know an algorithm (or, even better, a free software tool) to perform efficiently this operation?
I am browsing for references, but I didn't have much luck yet.

Many thanks in advance!

Hi Tiz,
I am not sure if I am getting your question right, but do you think the operation you want to do is described in slides 9-11 of http://of-interfaces.sourceforge.net...1-2-open-e.pdf (create an ordered cell-points list from cell-faces and face-points lists)? If so and if you can bear with a quick and dirty code, you can download my opensource code that includes such a conversion from http://openfoamwiki.net/index.php/Co...r_for_ParaView and take a look at vtkOpenFOAMReaderPrivate::InsertCellsToGrid() in vtkNewOpenFOAMReader.cxx .

Takuya

Hi Takuya,

Thanks for your reply, but actually what I am trying to do is slightly different.
If I got it right, your code add to the following mesh definition hierarchy:

1. List of vertices
2. List of faces, defined in terms of vertex labels
3. List of cells, defined in terms of face labels

an additional list of cells:

• List of cells, defined in terms of vertex labels

In my case, the input to the algorithm should be only:

1. List of vertices
2. List of faces, defined in terms of vertex labels

and the output:

• List of cells (face- or vertex-indexed, it does not matter)

This involves, chosen a face, looping over all the remaining faces and searching for the face set which defines a cell.

I'll try to write down some code, maybe I can handle that (at least for meshes with tet-cells only or hex-cells only).

Tiz

Uh, got it. Although I am by no means an expert and hence don't have a concrete solution, I generally find basic algorithms that you see almost in every programming textbook, such as sorting and binary search, are quite effective and useful for this kind of operations.

For example, if the vertex numbers of your mesh fit in 32bit integer,

1. Take an edge of a face and create its 64bit hash by assigning the vertex numbers of both ends to either higher or lower bits of an 64bit integer so that e.g. the bigger number always comes to the lower bits.
2. By doing the same for all edges of all faces, you can create a list of edge-faces.
3. Sort the list using the hashes as keys. This immediately allows you to group all faces that share an edge for all edges.
4. Take an edge of a face (a base face) again, and binary-search the sorted list to find all faces that share the edge.
5. Do the same for the next edge of the base face.
6. By carefully choosing two faces each of which belongs to either group 4. or 5. and which share a vertex that is not on the base face, you can see that the faces are connected.
7. Do the same for the remaining edges of the base face in turn.

This way you can find 5 out of 6 faces and all vertices that constitutes a hexahedron. Of course this is just a quick thought thus there should be a lot more details, but I hope you get the idea.

Takuya