8

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.

WesDec
  • 190
  • 6

2 Answers2

2

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.

Wolfgang Bangerth
  • 55,373
  • 59
  • 119
  • 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? – WesDec 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. – Wolfgang Bangerth Sep 18 '12 at 01:42
1

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

WesDec
  • 190
  • 6
  • Shewchuk's isosurface stuffing paper is really good. I was going to post it before I scrolled down and saw this. – Nick Alger Nov 05 '12 at 16:19