Generating Smooth Connections in 3D Mesh Models of Brain Arteries
By Wojciech Malara
In the previous articles in this series my colleagues described some challenges we faced regarding processing of 3D mesh models of brain aneurysms. One of them was to automatically generate connections from inlet and outlet branches of an aneurysm to some external points.
Let’s talk about
our 3D modelling solutions!
Whereas that article described the process of finding the starting points of that connection on the vessel model, in this article I am going to focus on the next step, i.e. generating the actual mesh and appending it to a model in a seamless manner.
Figure 1. The original model of a vessel (red) with centerlines (blue) and the generated connection (gray)
Figure 2. The original model of a vessel cut and merged with the generated connection
The first step towards creating connections is generating paths along which connection “tubes” should be placed. In fact, these paths are centerlines of the connections. At this stage all vessels have centerlines generated and on each branch there is a certain point selected to be the start of a connection. In order to ensure that connections are seamless we decided to use cubic B-splines in which the starting part is tangent to a centerline at the selected point and the ending is tangent to a configured vector.
Figure 3. Generated connection spline with starting and ending vectors
There is one more crucial requirement for these connections. Not only should they be smooth in terms of the starting and ending vectors but the generated 3D mesh itself should be connected with the original anatomy seamlessly. This means it should start with the exact contour of a branch cross-section and transition smoothly into a target circular shape.
The solution to this requirement can be divided into following steps:
1. cut a vessel at a certain point,
2. get a contour of the section,
3. “sweep” the contour along the generated spline,
4. modify the swept contour to ensure that it transitions into a circle,
5. generate the actual mesh,
6. connect the generated 3D mesh with the cut vessel.
In the subsequent parts of this article I am going to describe each of these steps in detail, focusing in particular on the most interesting ones for us, i.e. “sweeping” a shape along a path and making it transition to a circle.
Cutting a vessel at a certain point
The task of cutting a vessel mesh at a certain point may seem trivial as we take a vector tangent to a centerline at this point and use it as a normal vector of a cutting plane. For a mesh containing meandering vessels with multiple branches this solution is unacceptable as there is a high probability of cutting other parts of the vessel. Some improvement could be using a disc instead of a plane, but we would need to determine its radius first. Still, there is the possibility that the neighboring parts of a vessel may get cut. Thankfully, in Graylight Imaging we have a common and ever growing set of programming libraries with solutions to common problems and in this case we used a tool which returns a polygon cross-section of a vessel at a certain point of its centerline. This slice could then be used in order to cut the mesh by looking at how these meshes collide with each other.
Obtaining a section contour
Another important piece of data obtained from the aforementioned collisions analysis is boundary vertices and edges known almost right away by looking at colliding cells of the vessel mesh lying in the half-space indicated by a vector opposite the normal defining the cut. These boundaries form a “loop” which can be used as a starting shape for sweeping of the connection from the vessel to the target point and shape.
“Sweeping” a contour along path
How to sweep a contour along some path in 3D? Let us start with the simplest idea, meaning translating the contour into consecutive points on the curve. This would work only if the curve was a straight line segment, but for every other case this approach is incorrect as it violates the requirement that the contour orientation is defined by a normal vector tangent to the curve at that point at each point on the curve.
Consequently, the second approach would be not only to translate the contour into path points but also to take its orientation into account. The orientation could be calculated as follows: for each point on the path (except the first point where the orientation of the contour is known), we take the vector tangent to the curve at this point and the corresponding vector from the previous point. Then, we calculate the angle between these two vectors and the cross product of these vectors in order to get a vector perpendicular to them. This way we have all the rotations between the consecutive points in axis-angle representation. Having all this information, we can use e.g. Rodrigues’ formula to rotate the contour’s vertices at each path point sequentially. This solution worked almost as required, but with a single reservation as the problem was that at each point on the path the starting state was the rotation from the previous point and for long paths with many curvatures and many points, the numerical errors accumulated and the orientation at the final point would sometimes not be exactly perpendicular to the tangent vector.
As a result, we came up with a better idea which was also based on the tools we had already had in our Graylight Imaging “toolbox”. The solution was to generate a moving frame (orthonormal basis) at each point on the curve. We used the idea similar to Frenet-Serret frame, but with more stable normal vectors. Having all the basis vectors, we were able to construct change-of-basis matrices for each path point and convert contour vertices to those bases independently with a simple matrix multiplication.
Figure 4. Bases along the connection spline points
Transforming a contour into another shape during “sweeping”
As mentioned before, not only did we have to create a connection starting from the contour of a vessel cross-section, but the contour should also transition into a different shape smoothly along a given path. In our case, the final shape was probably the simplest one – a circle, but the idea presented here can be utilized for almost any other 2D shape as well. The idea is simple: take each vertex of the starting contour and assign a position on a final shape to it in the same coordinate system, then use e.g. a linear interpolation to create intermediate positions for each vertex at each step (path point). To move these vertices to the appropriate positions in 3D space, we use the change-of-basis matrices described in the previous section. It is worth mentioning that in some cases it might be necessary to increase the resolution of the starting polygon by subdividing its segments.
Figure 5. Two ends of the same connection. Generated “rings” of points transforming from a contour of a vessel section (left) into a circular shape (right)
Generating the actual connection 3D mesh
The result of the previous step was a collection of “rings” consisting of vertices. Knowing exactly the order of the “rings” as well as the consistent order of vertices in them, mesh cells can be created efficiently in a vectorized way using the “right-hand rule”.
Figure 6. Generated connection mesh
Connecting the generated 3D mesh with the cut vessel mesh
There are multiple ways to connect the generated 3D mesh with the cut vessel mesh. The solution we chose was to treat corresponding boundary edges of a vessel and a generated connection as two closed polygons (“loops”) and then create a mesh that would bridge them. However, the real challenge was that meshes representing real anatomical structures could be unpredictable and appending artificially generated meshes to them may often result in non-manifold edges. Fixing non-manifold issues in meshes is a broad topic in itself and will not be covered in this article. Nor will be another significant problem which we also needed to handle which is merging multiple connection meshes starting from different branches and ending at the common target point.
Figure 7. Cut model of a vessel (red), generated connection (gray) and the bridge between them (green)
3D mesh models of brain arteries – summary
The task of generating seamless connections from 3D mesh models of blood vessels was a truly interesting challenge. We were able to create the automated solution to difficult problems traditionally requiring sophisticated CAD tools and a qualified technician, by breaking the task down to smaller problems, using our broad expertise in Graylight Imaging as well as utilizing a suite of previously developed tools.
See the previous post by Piotr Mokry: Generating 3D printable mesh models of brain arteries