Take the 2-minute tour ×
Computational Science Stack Exchange is a question and answer site for scientists using computers to solve scientific problems. It's 100% free, no registration required.

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.

share|improve this question
add comment

2 Answers 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.

share|improve this answer
    
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 1:42
add comment
up vote 1 down vote accepted

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

share|improve this answer
    
Shewchuk's isosurface stuffing paper is really good. I was going to post it before I scrolled down and saw this. –  Nick Alger Nov 5 '12 at 16:19
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.