Similar to 2D maximum inscribed circle problem, when we have a set of 3D points , how to choose a good method to get 3D maximum inscribed sphere in a volume?
Especially, if we have a long vessel object in 3D coordinate and its surface can be represented in triangle mesh. The target is to find the a series of 3D maximum inscribed sphere along its center points.
Other than the image pixels, the volume surface is represented in triangle polygon mesh, maybe we need to construct Voronoi diagram.
This may get you started:
Xie, Snoeyink and Xu (2006)
Efficient algorithm for approximating maximum inscribed sphere in high dimensional polytope
http://dl.acm.org/citation.cfm?id=1137861
http://www.cse.yorku.ca/~andy/courses/6114/lecture-notes/MAX-Inscribed-Sphere.pdf
see also:
Natali, Biasotti, Patane, Falcidieno (2011)
Graph-based representations of point clouds
http://saturno.ge.imati.cnr.it/ima/personal/patane/PersonalPage/Patanes_Home_Page/Publications_files/patane-GMOD-2011.pdf
There are more articles and algorithms about bounding spheres, eg:
Thomas Larsson
(2008)
Fast and Tight Fitting Bounding Spheres
https://truesculpt.googlecode.com/hg-history/before%20draw%20merge/Doc/fast_tight_bounding_sphere.pdf
For your problem you might check Plumber method of Mortara et al. http://dl.acm.org/citation.cfm?id=1217875.1217929 or Hierarchical Mesh Segmentation based on Fitting Primitives available on Marco Attene's page http://www.ima.ge.cnr.it/ima/personal/attene/PersonalPage/attene.html
In Matlab there are some functions that may be of your interest. For example: "convhulln" and "voronoin" functions allows to obtain the facets and the voronoi vertices and cells of points in N-dimensional space respectively. Results can be displayed using "trisurf".
According to me, you must go through the recommended articles, but at the same time, you can try the function available in Matlab. Please go through the code and am sure you will find easy enough to convert it into any other language....
I have done the same (I converted it into fortran and so far it works fine)
- Badges
- Science topic