regular_triangulation

regular_triangulation(C, R)

Regular triangulation of a set of spheres (dual of the power diagram).

The sphere with center c and radius r is a weighted point with weight r^2. Two spheres are connected in the regular triangulation iff their power cells share a face. A sphere is hidden (its power cell is empty) if it does not appear as a vertex. Computed with CGAL.

Parameters:

Name	Type	Description	Default
C	(n,3) numpy double array	Sphere centers.	required
R	(n,) numpy double array	Sphere radii.	required

Returns:

Name	Type	Description
T	(t,4) numpy int array	Finite tetrahedra, as indices into C.
E	(e,2) numpy int array	Finite edges (sorted pairs of neighboring spheres).
valid	(n,) numpy bool array	False for hidden spheres.

Notes

The restricted power diagram uses this triangulation to find the neighbors of each medial sphere before clipping its power cell against the input shape.

C++: void libmat::regular_triangulation(C, R, T, E, valid) in <libmat/regular_triangulation.h>.

Examples:

import libmat
V, F = libmat.read_surface_mesh("data/mesh_69058.obj")
C, R, _ = libmat.shrink_spheres(V, F, num_spheres=1000)
T, E, valid = libmat.regular_triangulation(C, R)
print(len(E), "neighboring pairs,", (~valid).sum(), "hidden spheres")

C++

#include <libmat/regular_triangulation.h>

// Regular (weighted Delaunay) triangulation of a set of spheres, i.e. the
// dual of their power diagram, computed with CGAL. The sphere with center c
// and radius r has weight r^2.
//
// Inputs:
//   C  #S by 3 sphere centers
//   R  #S sphere radii
// Outputs:
//   T      #T by 4 finite tetrahedra (indices into C)
//   E      #E by 2 finite edges, i.e. pairs of neighboring power cells
//   valid  #S 1 if the sphere is a vertex of the triangulation, 0 if it is
//          hidden (its power cell is empty)
void regular_triangulation(const Eigen::MatrixXd& C, const Eigen::VectorXd& R,
                           Eigen::MatrixXi& T, Eigen::MatrixXi& E,
                           Eigen::VectorXi& valid);