matlabpolygonmeshvoronoi

Voronoi mesh for a 3D polygon

I spent my last week looking for a mesh generator that, given the vertices of a 3 dimensional polygon (such as a cube or a tetrahedron or a dodecahedron and so on) and the number of points (internal to the polygon) creates a voronoi decomposition of the polygon and in outut it gives the vertices of the voronoi cells and a matrix that contains the vertex indices of every cell (i.e. on the i-th row there are listed the indices of the vertices of the i-th voronoi cell).

I know that there exists the library voro++ that can be used for this porpouse, the problem is that I really have zero exerience in C++ and gnuplot, so that would not be the most suitable choice for me. Moreover I am currently working on MATLAB.

In MATLAB I found the following add-on which can generate a voronoi mesh of a cube, of a sphere and a cylinder, but does not work really well, especially when trying to generate a sequence of meshes with the parameter edgeSize that is decreasing (look at the example for the function createVoronoi3dFromMesh).

In Python, there is the pyvoro repository that, since it's based on voro++, should be able to do what I need, but I am unable to use it on Google Colab.

Moreover, it looks like there are lots of packages for generating the voronoi cells inside a cuboid but not for a general polygon. So I wanna ask if someone has a package or functions or software that can help me.

Edit 1

This edit is made to make more clear what I need and to explain why the MATLAB package does not work as intended. The MATLAB add-on here presented pretty much does what I need: fater creating a voronoi3d void object, we pass it the type of geometry we want to work on (there are three possibilities: multicuboid, multisphere and multicylinder) and it discretize its surface and interior using voronoi cells (for what I need, it would be sufficient for me that it only discretize the surface, so that if we want to discretize the geometry multisphere we obtain a polygon with faces given by the voronoi cells and the max edge kength is given by the parameter edgeSize). The problem is that it does not correctly work on this geometry: in fact if I compile the following code:

clear; close all; clc;
% THE PACKAGE NEEDS THE PARTIAL DIFFERENTIAL EQUATION TOOLBOX TO BE INSTALLED
domainMesh = voronoi3d; %create an empty voronoi3d object
myGeo3d = multisphere(1);
edgeSize = 2^(0);
domainMesh = createVoronoi3dFromGeometry(domainMesh, myGeo3d,edgeSize);
%create voronoi by geometry
voronoiPatch(domainMesh,'nodal',domainMesh.Nodes(:,2)) %to plot the mesh

I obtain the following figure As you an see the vertices of the voronoi cells are not correctly connected.

Moreover, I've also already made a post in the MATLAB official forum because there happens to be some problem with the uage of different MATLAB versions, which makes this package not reliable.

I hope that now it's more clear what I would like to have. Thanks in advance.

Edit 2

As @magnesium suggested, there is this Github repository that, using fast marching algorithm, computes a Voronoi triangulation of a 2D or 3D domain. However, it's still a mistery for me how to use it for my porpouse.

On the other hand, I've found this MATLAB toolbox that computes the decomposition into Voronoi cells of a sphere, given a set of points on its surface.

Solution

  • The question is still a bit unclear but here is a way to get a voronoi decompoisition of an arbitrary triangular mesh. It uses this toolbox which should be downloaded and compiled as per its instructions. Then this code gives the voronoi decomposition:

    %%% mesh and seeds
nseeds = 200; % number of voronoi seeds
rng(1); 

% example mesh
[v,f] = read_mesh(which('elephant-50kv.off'));
v = v.'; f = f.'; 
seeds = randsample(height(v), nseeds); 

figure; nexttile; 
patch('Vertices', v, 'Faces', f, 'FaceColor', 'w'); axis image; 
hold on; 
scatter3(v(seeds,1), v(seeds,2), v(seeds,3), 50, 'red', 'filled'); 


%%% geodesic distance
[D,S,Q] = perform_fast_marching_mesh(v', f', seeds); 

% figure; 
nexttile; % distance to nearest seed
patch('Vertices', v, 'Faces', f, 'FaceColor', 'interp', 'FaceVertexCData', D); axis image; 
nexttile; % seed ID - for voronoi partitioning
patch('Vertices', v, 'Faces', f, 'FaceColor', 'interp', 'FaceVertexCData', Q); axis image; 
colormap(gca, lines); 

%%% voronoi of mesh
[vvor, fvor] = compute_voronoi_triangulation_mesh(Q, v', f'); 
% figure; 
nexttile; 
patch('Vertices', vvor', 'Faces', fvor', 'FaceColor', 'w'); axis image; 
hold on; 
scatter3(v(seeds,1), v(seeds,2), v(seeds,3), 50, 'red', 'filled');

    Q contains the seed ID that each vertex has been allocated to. This is shown in panel 3. And the voronoi decomposition of the mesh itself is shown in panel 4.

    mesh voronoi