How to convert 3D mesh to voxelated array image?


#1

Dear community. I’m looking for some image related functionality which may already be implemented in Julia. I haven’t managed to find them, but that may be because I do not know what to search for (I’ve limited experience in computer graphics). So before I go ahead reinventing wheels, I thought it might be worth asking here.

I need the following.

  1. Given a triangular 3D mesh (i.e. a vector of coordinate vertices, and a corresponding vector of triplets of indices which define the faces), can I get a binary voxelated 3D image which indicates inside/outside region defined by the mesh (i.e. a 3 dimensional array of bools, together with information regarding the extent of the 3D image).
  2. Given a line segment defined by (x,y,z) coordinates of the endpoints, and a 3D image array as described above, give as output an array of bools corresponding to voxel values which the line segment penetrates.

I intend to use the above to calculate whether a line segment is penetrate the mesh boundary. I need to evaluate a large number of line segment per mesh (O(N^2) where N is the number of faces), so I figured that evaluating segments in the binarised representation would be more efficient than to loop over the entire set of mesh faces for each line segment (I might be wrong here).

In any case, is there an image framework or similar which provides this or similar functionality? If not, are there related functionality I could utilize to implement it myself?

Best Jon


#2

I just wrapped TetGen for tetrahedralizing meshes.
It’s a bit in an early stage and unregistered yet, but should be good to use!

With tetgen, you can tetrahedralize your mesh. I’m not sure if that’s the best way to voxelize a mesh, but it should be much easier to check if your voxel lies within a tetrahedron, than check if it’s inside the triangle mesh :wink: If you come up with a point tetrahedron intersection algorithm, would be nice to integrate that into the package :slight_smile:


#3

Nice!

Does anybody know if there is a package out there that can mesh an N-dimensional region with simplices (i.e. N-dimensional tetrahedra)?


#4

I think tetgen can actually do that… Maybe it needs a bit of help here and there (e.g transform all n-simplices to tetrahedrons), but I think most of the functionality should be there :wink:


#5

Thanks @sdanisch, I will definitely check that out. By “point tetrahedron intersection algorithm” do you mean to check if point is contained within the tetrahedron. If so, isn’t this as simple as checking that the point lies on the negative side of each tetahedron face (assuming that positive face points outwards)? If the point in question is x, and each of the triangles are described by points a, b, c. This amounts to evaluating sign(dot(cross(b-a, c-a), x-a)) for each of the faces.


#6

yeah it should be very easy that, was my point :slight_smile: but it doesn’t seem like there is an existing implementation anywhere…


#7

My summer student had implemented something in https://github.com/ShnitzelKiller/MeshTools.jl a while ago. Unfortunately, we had to put the project on hold for a while, but feel free to dig around there, there may be useful stuff in there.


#8

Thanks for the link @jstrube. Instructive to go through related code!