# Octree cubes to tetrahedrons

I'm trying to learn more about volume meshing and have decided to try to implement a simple volume mesher. The strategy I have chosen is to subdivide my space using an octree, refined based on some criteria. I have made sure that my octree is balanced, such that the difference between two neighbouring cells is no more than 1 (the so-called 2:1 rule).

I now have to cut my cells into tetrahedrons. I have read that Body Centered Cubic (BCC) is a popular way to do this but unfortunately I have not found any literature that explains well how to handle differences between two neighbouring cubes of different levels.

I have also seen that cutting cubes into 6 tetras as shown below is common, but again I have found nothing explaining how to handle cubes of different levels:

http://www.ics.uci.edu/~eppstein/projects/tetra/sixcube.gif

I would appreciate it if someone could explain how Octree cubes should be cut into tetras or perhaps refer me to a paper/presentation about this subject.

You can do it in two different ways:

• You accept that your mesh has hanging nodes: just like the cells of your octree have a 2:1 relationship where it is refined, you can have the same kind of 2:1 relationship for tet meshes. If you do the isotropic (BCC) refinement of hexahedra into tets, then the 2:1 relationship between adjacent cells of the octree is inherited to the tets as well.

• If you don't want hanging nodes, then you can do a postprocessing step. Assume you have done the BCC refinement, then there may be adjacent tets that differ in size by a factor of 2. You only have to refine the larger ones in such a way that they now match their smaller neighbors. How to do this is easy to understand on a piece of paper in the 2d case. In 3d it's a bit more tricky but you'll see that you can refine a tet anisotropically in such a way that it matches its neighbors.

• Hanging nodes are not allowed. You are right that solving this in 2d is very simple but in 3d it gets complicated. Can you refer me to a paper which explains the BBC refinement and how to deal with hanging nodes? Sep 17 '12 at 12:57
• No, sorry. I'm a hexahedron kind a guy. I don't have the tet literature at hand. You may find something in Graham Carey's Grids book. Sep 18 '12 at 1:42

I found the following papers which describes clearly how to do a BCC mesh, and how to handle the hanging nodes:

Adaptive and Quality Tetrahedral Mesh Generation

Isosurface Stuffing

The following presentation, in addition to describing BCC, also describes Face Centred Cubic (FCC): Unbound Optimal Tetrahedral Mesh

• Shewchuk's isosurface stuffing paper is really good. I was going to post it before I scrolled down and saw this. Nov 5 '12 at 16:19