How to get triangles from triangulation 3D Delaunay

I have the triangulation dt(or possibly tetrahedrization) of a three-dimensional point cloud, and I would like to find a good way to extract triangles from it. Notice, I know how to get tetrahedra, just dt.ConnectivityList, is there an effective way to get triangles from tetrahedra? Each triangle should appear only once in the list.

I am currently doing the following - however, it is very slow:

dt = delaunayTriangulation([X Y Z]);
tetrahedra = dt.ConnectivityList;

tris = cell(1, size(tetrahedra, 1)); % contains indices of tris in a tetra
for tt=1:size(tetrahedra, 1)
    vertIds = tetrahedra(tt, :); % vertex indices

    vmask = logical([0 1 1 1]);
    tris{tt} = [vertIds(circshift(vmask, [0 0 0 0]));
                vertIds(circshift(vmask, [1 1 1 1]));
                vertIds(circshift(vmask, [2 2 2 2]));
                vertIds(circshift(vmask, [3 3 3 3]))];
end

tris = unique(sort(cell2mat(tris'), 2), 'rows');
+4
source share
1 answer

Here is the vector version:

% take all four subsets of three points from the tets and concatenate
tris2 = [tetrahedra(:,[1 2 3]); tetrahedra(:,[1 2 4]); tetrahedra(:,[1 3 4]); tetrahedra(:, [2 3 4])];
% sort each row
tris2 = sort(tris2, 2);
% eliminate duplicates
tris2 = unique(tris2, 'rows');

With 100,000 test points (random numbers) I get

Cellmethod: time=9.870982, numelements = 1344960
Vectmethod: time=1.014797, numelements = 1344960
+2
source

Source: https://habr.com/ru/post/1527553/


All Articles