volume of set of points in 3d space with gap

Hello,

I have a set of 3D points that represent an artery that has a bifurcation in it, so it splits from one to two branches. I am trying to find the volume. I have tried delaunay triangulation and convex hull but this results in the gap also being filled (see image). Is there any way to make the convex hull fit better to the true data set?

thanks!

[Umar]

Hi @Lotte ,

When dealing with complex geometries like artery bifurcations, achieving an accurate volume calculation can be challenging due to gaps or inaccuracies in the mesh generated by methods like delaunay triangulation or convex hull. To improve the fit of the convex hull to the true dataset and calculate the volume more accurately, you can employ a technique called alpha shapes, a generalization of the convex hull that allow for concave regions to be included in the shape. By adjusting the alpha parameter, you can control the level of detail in the shape and potentially capture the intricate geometry of the artery bifurcation more accurately. Below is an example code snippet that demonstrates how to calculate the volume of an artery bifurcation using alpha shapes:

% Generate sample 3D points representing the artery bifurcation

points = randn(100,3); % Replace with your actual 3D points

% Create alpha shape with an appropriate alpha value

alpha_value = 0.5; % Adjust based on the dataset

shp = alphaShape(points, alpha_value);

% Calculate the volume enclosed by the alpha shape

volume = volume(shp);

% Visualize the alpha shape

plot(shp);

axis equal;

xlabel('X');

ylabel('Y');

zlabel('Z');

title('Artery Bifurcation Alpha Shape');

disp(['Volume of Artery Bifurcation: ', num2str(volume)]);

Please see attached.

So, in this example code snippet, replace points with your actual 3D point data representing the artery bifurcation. Feel free to adjust the alpha_value parameter to control the level of detail in the alpha shape. Then, calculate the volume enclosed by the alpha shape using the volume function. Afterwards, visualize the alpha shape to inspect how well it fits the artery bifurcation geometry. By utilizing alpha shapes, you can potentially achieve a better fit to the true dataset and calculate the volume of the artery bifurcation more accurately, addressing the gaps or inaccuracies encountered with traditional convex hull methods. For more information on this function, please refer to alphaShape

Hope this helps. Please let me know if you have any further questions.

Answer 1

[Umar]

Hi @Lotte ,

After collaborating thoughts with experts, I used the boundary function by generating same sample 3D points (again replace with actual data representing the artery bifurcation). Then, set a custom shrink factor (shrink_factor = 0.3 in this case) to adjust how tightly the convex hull envelops the points. The boundary function is used with the specified shrink factor to create the convex hull (k) and finally, plot the original points along with the improved fit of the convex hull using the adjusted shrink factor. Here is updated code,

% Generate sample 3D points representing the artery bifurcation points = randn(100,3); % Example data, replace with actual data

% Create the convex hull with a custom shrink factor

shrink_factor = 0.3; % Adjust the shrink factor as needed

k = boundary(points, shrink_factor);

% Plot the original points and the convex hull

figure;

trisurf(k, points(:,1), points(:,2), points(:,3), 'FaceColor', 'cyan', 'FaceAlpha', 0.5);

hold on;

scatter3(points(:,1), points(:,2), points(:,3), 50, 'filled', 'MarkerFaceColor', 'r');

axis equal;

title('Improved Convex Hull Fit for Artery Bifurcation');

legend('Convex Hull', 'Original Points');

Please see attached plot.

Feel free to experiment with different shrink factor values closer to 0, so you can achieve a better fit of the convex hull to the true data set of the artery bifurcation, ensuring accurate volume calculations without filling the gap. Also, adjust the shrink factor based on the specific characteristics of your data to optimize the fit for your application.

[Lotte]

Thanks for all the replies. I tried all and CRUST seems to be the best option, but I does not seem to have an option to give the enclosed volume?

[Umar]

Hi @ Lotte,

Please see my response to your comments,” I tried all and CRUST seems to be the best option, but I does not seem to have an option to give the enclosed volume?”

Summary of Analysis Report on Enclosed Volume of Bifurcating Artery

The analysis focuses on the "Enclosed Volume" of 9.1584 units, representing the three-dimensional space occupied by the bifurcating artery as delineated by a set of 3D points. This volume serves as a critical metric in understanding the geometric and flow characteristics of the artery, with interpretations varying based on specific research objectives.

Key Findings:

Volume Interpretation

The significance of the enclosed volume is context-dependent. A larger volume may suggest a more complex or tortuous arterial structure, relevant for morphological studies, while a smaller volume could indicate more streamlined flow dynamics, beneficial for hemodynamic analyses.

Algorithm Utilization

 Various algorithms were employed to calculate the enclosed volume:
Convex Hull: Defines the smallest convex boundary around the point set, providing a straightforward geometric representation.

AlphaShape: Captures irregular geometries effectively by adjusting an alpha parameter to better fit the point cloud.

Boundary Detection: Identifies outer edges using edge detection and morphological techniques, aiding in boundary extraction.

Crust Algorithm: Approximates the medial axis, offering insights into branching patterns.

Consistency Across Algorithms

Notably, all algorithms yielded consistent volume results (approximately 9.1579 units), indicating robustness in boundary formation and reliability in capturing the spatial extent of the artery's geometry. This uniformity suggests that regardless of the algorithm's approach, they accurately enclose the same spatial region defined by the bifurcating artery points.

Geometric Insights

The enclosed volume provides a foundation for further analysis, including metrics such as surface area, centroid location, and moments of inertia. These additional parameters can deepen understanding of arterial morphology and function.

Further Considerations

Future analyses could include comparative studies against other arteries or reference values to contextualize findings within broader physiological norms. Statistical techniques may also be applied to assess deviations from expected volume ranges.

Points.mat file used for data analysis

Since set of 3D points that represent an artery that has a bifurcation in it, so it splits from one to two branches data was not provided by OP, I had to create binary data format file in Matlab and saved it as “Points.mat”

alphaShape Algorithm

 load('points.mat')

% Create an alphaShape object

shp = alphaShape(p);

% Plot the boundary of the alphaShape object

figure;

plot(shp);

title('Boundary of Alpha Shape');

% Calculate the boundary of the points in 3D

boundary_points = boundaryFacets(shp);

% Compute the volume enclosed by the boundary

volume = volume(shp);

% Display the results

disp(['Number of boundary points: ', num2str(size(boundary_points, 1))]);

disp(['Volume enclosed by the boundary: ', num2str(volume)]);

Number of boundary points: 626

Volume enclosed by the boundary: 9.1579

ConvexHull Algorithm

Using Convexhull Method and volume results Interpretation

 load('points.mat')

 % Create a Delaunay triangulation from the points

DT = delaunayTriangulation(p);

% Compute the convex hull of the Delaunay triangulation

[C, v] = convexHull(DT);

% Plot the boundary of the convex hull

trisurf(C, p(:,1), p(:,2), p(:,3), 'FaceColor', 'cyan', 'FaceAlpha', 0.5);

axis equal;

title('Convex Hull of Bifurcating Artery');

% Calculate the volume enclosed by the convex hull

volume_enclosed = v;

% Display the results

disp(['Volume enclosed by the convex hull: ', num2str(volume_enclosed)]);

Volume enclosed by the convex hull: 9.1585

Boundary Algorithm (suggested by @Star Strider)

 % Load the points from the saved .mat file

load('points.mat');

% Create a boundary around the points in 3D

k = boundary(p);

% Plot the boundary

trisurf(k, p(:,1), p(:,2), p(:,3), 'FaceColor', 'cyan', 'FaceAlpha', 0.8);

axis equal;

xlabel('X');

ylabel('Y');

zlabel('Z');

title('Boundary around Bifurcating Artery Points');

 % Calculate the boundary of the points in 3D

k = boundary(p);

% Compute the volume enclosed by the boundary

[~, volume] = boundary(p);

% Display the results

disp('Boundary Points:');

disp(p(k,:));

disp(['Enclosed Volume: ', num2str(volume)]);

Crust Algorithm (suggested by @John D Ericco)

load points.mat

%% Run program

[t,tnorm]=MyRobustCrust(p);

% Calculate volume using the tetrahedral decomposition method

volume = 0;

% Loop through each triangle

for i = 1:size(t, 1)

    % Get vertices of the triangle

    v0 = p(t(i, 1), :);

    v1 = p(t(i, 2), :);

    v2 = p(t(i, 3), :);

    % Calculate volume contribution of this triangle (as if it were a tetrahedron)

    volume = volume + dot(v0, cross(v1, v2));

end

% Final volume calculation

volume = abs(volume) / 6;

fprintf('The enclosed volume is: %.4f\n', volume);

% Plotting

figure(1);

set(gcf,'position',[0,0,1280,800]);

subplot(1,2,1)

hold on

axis equal

title('Points Cloud','fontsize',14)

plot3(p(:,1),p(:,2),p(:,3),'g.')

view(3);

axis vis3d

% Plot of the output triangulation

subplot(1,2,2)

hold on

title('Output Triangulation','fontsize',14)

axis equal

trisurf(t,p(:,1),p(:,2),p(:,3),'facecolor','c','edgecolor','b');

view(3);

axis vis3d;

Attached plots & results

Conclusion

The analysis underscores the importance of the enclosed volume as a fundamental metric in characterizing 3D point clouds representing bifurcating arteries. The consistent results across various boundary algorithms validate their effectiveness in accurately depicting spatial properties, facilitating a more comprehensive understanding of arterial morphology and its implications for hemodynamics and medical research. Further exploration of additional metrics will enhance insights into arterial characteristics and contribute to improved diagnostic and therapeutic strategies. In addition to these comments,the "Enclosed Volume" value of 9.1584 represents the volume enclosed by the boundary of the 3D points that make up the bifurcating artery. This value is a measure of the space occupied by the artery within the boundary. The interpretation of the enclosed volume value can vary depending on the goals of the analysis. If the goal is to study the morphology or geometry of the artery, a larger enclosed volume may indicate a more complex or tortuous artery. This could be of interest in certain medical or biomechanical studies where the shape and structure of the artery are important factors. On the other hand, if the goal is to analyze the flow dynamics or hemodynamics of the artery, a smaller enclosed volume may be desirable. A smaller volume suggests a more streamlined flow and potentially better flow characteristics. Another important factors to add is about choosing appropriate algorithm based on the nature of your boundary points. For example, if your points form a convex shape, you can use the Convex Hull algorithm. If your points are irregularly distributed, you can use the Delaunay Triangulation algorithm.To further analyze the enclosed volume and its significance, additional steps can be taken using MATLAB. For instance, one can compare the enclosed volume of the bifurcating artery with other arteries or with a reference value to assess its relative size or shape. Statistical analysis techniques can also be employed to determine if the obtained volume falls within a certain range or if it deviates significantly from expected values.

[Umar]

Hi @ Lotte,

Glad that you have accepted our answers. If you have still have any further questions or concerns, please let us know. We will be more happy to help you out.

Answer 2

[Umar]

Hi @Lotte ,

When dealing with complex geometries like artery bifurcations, achieving an accurate volume calculation can be challenging due to gaps or inaccuracies in the mesh generated by methods like delaunay triangulation or convex hull. To improve the fit of the convex hull to the true dataset and calculate the volume more accurately, you can employ a technique called alpha shapes, a generalization of the convex hull that allow for concave regions to be included in the shape. By adjusting the alpha parameter, you can control the level of detail in the shape and potentially capture the intricate geometry of the artery bifurcation more accurately. Below is an example code snippet that demonstrates how to calculate the volume of an artery bifurcation using alpha shapes:

% Generate sample 3D points representing the artery bifurcation

points = randn(100,3); % Replace with your actual 3D points

% Create alpha shape with an appropriate alpha value

alpha_value = 0.5; % Adjust based on the dataset

shp = alphaShape(points, alpha_value);

% Calculate the volume enclosed by the alpha shape

volume = volume(shp);

% Visualize the alpha shape

plot(shp);

axis equal;

xlabel('X');

ylabel('Y');

zlabel('Z');

title('Artery Bifurcation Alpha Shape');

disp(['Volume of Artery Bifurcation: ', num2str(volume)]);

Please see attached.

So, in this example code snippet, replace points with your actual 3D point data representing the artery bifurcation. Feel free to adjust the alpha_value parameter to control the level of detail in the alpha shape. Then, calculate the volume enclosed by the alpha shape using the volume function. Afterwards, visualize the alpha shape to inspect how well it fits the artery bifurcation geometry. By utilizing alpha shapes, you can potentially achieve a better fit to the true dataset and calculate the volume of the artery bifurcation more accurately, addressing the gaps or inaccuracies encountered with traditional convex hull methods. For more information on this function, please refer to alphaShape

Hope this helps. Please let me know if you have any further questions.

[John D'Errico]

@Umar

You mention improving the fit of the convex hull, but the boundary surface of an alpha shape is not a convex hull at all.

I also suggested the possibility of an alpha shape in my (parallel) answer, however in my experience, an alpha shape will very likely fail here, for several reasons. Why do I say it will fail?

First, a bifurcation of arteries will have a sharp internal corner at the point of bifurcation. An alpha shape, since they use an alpha ball of given radius, will never see that corner well. If you try to make the alpha radius small enough, then you lose everything, as the alpha ball penetrates everywhere.

Next, the data for this class of problem will be merely points on the surface of those vessels. That means there are large internal holes everywhere. So unless you have points that uniformly cover the surface, the alpha ball will end up penetratign into the volume of the vessel. And that makes it erode the entire mess. You have nothing left.

Worse, the data comprising a cloud that represents an artery will have holes at each end too. An alpha shape will erode those holes, UNLESS the alphs ball is sufficiently large, and then it will never represent the necessary bifurcation well.

Remember that an alpha shape uses the metaphor of a ball, of radius alpha moving around the surface of what will be initially a Delaunay triangulation. Wherever that alpha ball can penetrate into the triangulation, so where there are external facets that are sufficiently large to allow the ball to pass through, you delete the corresponding simplexes from the triangulation. This metaphor works very nicely for sufficiently dense data. But data that lies only on the surface of an object, where that object also has holes in it? The alpha shape fails miserably, virtually EVERY TIME.

This is why I recommended CRUST as a better tool. It seems to work far better on this class of problem. That is not to say an alpha shape will definitely fail, but in the 30 years or so that I have been using alpha shapes as a consultant, I have in the past tried recommending than, and they ALWAYS have failed to work on this class of problem.

[Umar]

Hi @John D'Errico ,

While alpha shapes have their advantages in certain scenarios, but after digesting your detailed analysis about its implications, you have a point that they may not be the most suitable method for accurately calculating volumes in complex geometries like artery bifurcations due to their limitations in handling sharp corners, holes, and non-convex regions. So, considering alternative approaches like CRUST as you suggested can offer better outcomes by addressing these specific challenges more effectively as mentioned here: CRUST

[John D'Errico]

Honestly, I know a LOT about alpha shapes. I wrote versions of them for our own use long before they were officially implemented in MATLAB. And we used them heavily for my former employer. So I've been using them for maybe 30 years. But I've never really used CRUST, as it would not have been useful for our purposes. I just know that alpha shapes always failed on problems like this. Sorry.

I can only say is that CRUST seems designed to solve a basic problem where the point cloud lives only on the surface of a body. And that would make it a far better fit for this problem.

[Umar]

Hi @ John D'Errico,

Your observation about CRUST being better suited for certain problems is well-founded, particularly when working with surface-restricted point clouds. It’s always beneficial to evaluate the specific characteristics of your dataset when choosing between these methods to ensure optimal results.

Answer 3

[John D'Errico]

Is there any way you can make the convex hull adequately represent a region that is not in fact convex? Of course not!

You have a region with a hole in it, and you want the hole to remain a hole.

A delaunay triangulation is bounded by the convex hull. And the convex hull is essentially unique, with the caveat what if there are 4 or more coplanar points on the surface, the surface triangulation may not be unique. But wish as much as you want, you CANNOT force a convex hull to do as you wish.

And that means you CANNOT use a delaunay triangulation. The result will have the convex hull covering the bifurcation. Some of the time, you might be able to use other tools. For example, alpha shapes, or CRUST. (I would bet a large sum of money that an alpha shape is not the tool you want to use here however, for reasons I point out in my comment to @Umar.) So I would start with CRUST, or something like it.

Honestly, your data does not seem to cover the surface of the vessel very uniformly from the image you show, and that will probably cause issues (ambiguiities in the resulting surface) regardless of what method you use. But CRUST may have a shot. In fact, I recall there is a CRUST tool on the file exchange, and I recall it works in 3-d.