We have a 3D (volume) unstructured, possibly hybrid, degenerative irregular mesh data structure that we are capable of generating (mostly composed of hexahedra and general polyhedra, using a mix of CSG and b-rep) and a set of triangulated surfaces that we know intersect the mesh. We would like to split the volume mesh by the set of intersecting triangulated surfaces and change the topology of the mesh accordingly. These meshes have several uses including computation and visualization. Also the geometries they both represent are highly irregular and complicated, so oct-trees or oct-forests are not being strongly considered. We already have an implementation to detect such intersections in the whole volume. The triangulated surfaces can intersect themselves inside the volume too and split the mesh in another number of topological regions.

What we are looking for is an algorithm to split the mesh accordingly.

Would you know any library (whatever language, but if commercial ones, implemented in C++) or papers that would deal with this?

We are currently looking into using Marching cubes and have started some development towards that effort, but are interested in existing implementations or research on the topic. We have also been looking into CGAL but it does not fit our purpose. We know OpenFOAM by name but we do not know if it can help us.

Thanks for your help!

  • $\begingroup$ I am not really sure which SE site to post this so I cross-posted it to SO and GameDev (even though our soft is not dedicated to games) and Computational Science: stackoverflow.com/questions/8614695/… and gamedev.stackexchange.com/questions/21456/… $\endgroup$ – Marc-Olivier Titeux Dec 23 '11 at 10:20
  • $\begingroup$ MarcO, it is appropriate to post this question here as we definitely deal with these issues in computational science frequently. Reading your question, I'm still not entirely sure what you are asking, though. Perhaps you could try rephrasing it a bit more? $\endgroup$ – Aron Ahmadia Dec 24 '11 at 1:07

VTK has many utilities for cutting meshes with planes and implicitly-defined surfaces. It's possible that would work for you. To use it, you would probably feed your whole mesh into a vtkUnstructuredGrid (or similar) and have VTK do all the cutting. I think you will have a harder time if you want control over how topology changes when a cell is cut.

A lower level and lightweight tool for geometric tasks relating to cutting cells is Voro++. I have used it for some mesh preprocessing tasks and computing sizes of dual cells; it worked well and was unintrusive. Voro++ would be a good choice if you want to cut single cells or collections of cells, then use your own logic for changing mesh topology due to the cut.

You mentioned CGAL, but did not state how it failed to meet your needs. Perhaps you could specify what you are looking for more precisely?

  • $\begingroup$ Thanks a lot for your answers. Voro++ looks very interesting. However, the cells it can generate are not fit for us. This is my fault. The cells we need need to be hexaedral or base-prism. The software we want to use them for requires such limitations. So, my bad... Vtk could be a solution. In the mean time, we have re-iterated some efforts on CGAL. $\endgroup$ – Marc-Olivier Titeux Jan 14 '12 at 20:46
  • $\begingroup$ We are trying two ways: cgal.org/Manual/latest/doc_html/cgal_manual/Mesh_3/… and cgal.org/Manual/latest/doc_html/cgal_manual/Mesh_3/…. It offers some flexibility, and we could generate Tetra mesh as a first try which do not look too bad. Actually, we need to develop some expertise on this. I'll try to post snapshot to illustrate what block us. $\endgroup$ – Marc-Olivier Titeux Jan 14 '12 at 20:46

I'm using OpenFOAM for a while now (for my PhD as well), and I can only recommend it:

It has a huge amount of physical models, and it's written in C++, which means: modularity, encapsulation, automatic parallelism of top level codes, boundary conditions bound to the fields but implemented as a model library, multi physics [6DoF, two phase flow, combustion, all kind of turbulence models, naval hydrodynamics solvers, molecular dynamics... there is a lot in it.. :)], equation mimicking (really easy way of working with new sets of governing equations), etc... btw, its under GPL so it's free to download and modify.

For your specific purpose, there is a mesh generator available that does exactly what you want, called "snappyHexMesh". It takes an STL and intersects it with the underlying unstructured mesh and creates a new mesh ready to be used with OpenFOAM solvers and libraries, so check this out:

snappyHexMesh official info

a good tutorial on snappyHexMesh

  • $\begingroup$ I will look into it and will be back at you. Thanks! $\endgroup$ – Marc-Olivier Titeux Jan 14 '12 at 20:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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