shrink_spheres

shrink_spheres(
    V,
    F,
    num_spheres=1000,
    preserve_features=True,
    thres_concave=0.2,
    thres_convex=40.0,
    max_iter=-1,
    seed=200,
)

Sample medial spheres with the ball-shrinking algorithm.

For each random surface sample p with inward normal n, a large sphere tangent to the surface at p is shrunk until it touches the surface at a second point and becomes maximal inside the shape [Ma et al. 2012]. Its center lies (approximately) on the medial axis. With preserve_features=True, sharp and concave features are detected first and spheres stop at concave edges.

Parameters:

Name	Type	Description	Default
V	(n,3) numpy double array	Vertex positions of a closed, manifold triangle mesh.	required
F	(m,3) numpy int array	Triangles.	required
num_spheres	int, optional (default 1000)	Number of surface samples. At most one sample is drawn per triangle, so at most m spheres are created; spheres that fail to converge or duplicate an existing sphere are discarded.	1000
preserve_features	bool, optional (default True)	Detect sharp/concave features and take them into account.	True
thres_concave	float, optional (default 0.2)	Concave edge threshold, see detect_sharp_features.	0.2
thres_convex	float, optional (default 40.0)	Sharp edge threshold in degrees, see detect_sharp_features.	40.0
max_iter	(int, optional(default - 1))	Maximum number of shrinking iterations per sphere (-1: no limit).	-1
seed	int, optional (default 200)	Seed of the random surface sampling.	200

Returns:

Name	Type	Description
C	(s,3) numpy double array	Sphere centers, in the coordinates of V.
R	(s,) numpy double array	Sphere radii.
types	(s,) numpy int array	Sphere types, see libmat.SPHERE_TYPES.

See Also

regular_triangulation : neighborhood of the spheres (power diagram dual). medial_mesh_from_spheres : connect the spheres into a medial mesh (CUDA).

Notes

Internally the mesh is normalized to [0, 1000]^3, the scale the default parameters are tuned for; outputs are mapped back to the input coordinates.

C++: void libmat::shrink_spheres(V, F, options, C, R, types) in <libmat/shrink_spheres.h>.

Examples:

import libmat
V, F = libmat.read_surface_mesh("data/mesh_69058.obj")
C, R, types = libmat.shrink_spheres(V, F, num_spheres=1000)
print(C.shape, R.min(), R.max())

C++

#include <libmat/shrink_spheres.h>

struct ShrinkSpheresOptions {
  // number of random surface samples, one sphere is shrunk per sample; at
  // most one sample per triangle, so at most #F spheres
  int num_spheres = 1000;
  // detect sharp/concave features first and let spheres stop at them
  bool preserve_features = true;
  // feature detection thresholds, see detect_sharp_features()
  double thres_concave = 0.2;
  double thres_convex = 40.;
  // maximum number of shrinking iterations per sphere (-1: no limit)
  int max_iter = -1;
  // seed of the random surface sampling
  unsigned int seed = 200;
};

// Sample medial spheres with the ball-shrinking algorithm [Ma et al. 2012]:
// a sphere touching the surface at a random sample p (with inward normal n)
// is shrunk until it is maximal inside the shape. Sphere types are the
// values of SphereType in libmat/matbase/medial_sphere.h.
//
// Inputs:
//   V  #V by 3 vertex positions of a closed triangle mesh
//   F  #F by 3 triangles
//   options  see ShrinkSpheresOptions
// Outputs:
//   C      #S by 3 sphere centers (in the coordinates of V)
//   R      #S sphere radii
//   types  #S sphere types (SphereType)
void shrink_spheres(const Eigen::MatrixXd& V, const Eigen::MatrixXi& F,
                    const ShrinkSpheresOptions& options, Eigen::MatrixXd& C,
                    Eigen::VectorXd& R, Eigen::VectorXi& types);