Triangle clustering of .stl file

Hello everyone,

I am asking help to the MATLAB community since my head is burning :(

So I have stored two matrices F(mx3) and N(ux3), where u is 3 times m. The first matrix F contains the triangles of an .stl file, namely it containes, in each row, the indices of the rows of matrix N where the X, Y, and Z coordinate are stored. So, for example, if F(1,:) = [1 2 3], it means that the coordinates of the vertices of the first triangle have to be found in rows 1,2, and 3 of matrix N.

Plotting the triangles we have this situation:

Now what i want to do is divide the triangles in different regions (in this case 3, but the number of regions should not be a user input).

I have been able to identify the triangles wich lies on the border writing a small algorithm that search, for each triangle, what are the adjacent triangles (looking for the common edges). All the triangles that only have 1 or 2 adjacent triangles are stored as "Border Triangles".

Here, unfortunately, is where i stop. I have thought to use some graph traversal methods to identify the regions but i am not familiar with this type of techniques.

Any suggestions?

I am not attaching any dataset since it will be to heavy and probably to much confusing.

Hoping to find an answer here :)

Thanks

Answer 1

[Aastha]

Hi Lorenzo Pollicini,

As I understand, you'd like to automatically cluster the triangles in a .stl file without user input. To achieve this, you can convert the STL triangles into a point cloud by retaining only the centroids of each triangle in the STL file.

This can be done using the following MATLAB code:

% Assuming F is an mx3 matrix and N is a ux3 matrix where u = 3*m 
% Initialize the matrix to store the centroids 
m = size(F, 1); % Number of triangles 
centroids = zeros(m, 3); 
 
% Loop through each triangle defined in F 
for i = 1:m 
    indices = F(i, :); % Row of F that contains indices 
    vertices = N(indices, :); % Get the corresponding coordinates from N 
    centroids(i, :) = mean(vertices, 1); % Compute the mean of the vertices 
end 
% 'centroids' now contains the centroids of each triangle 

Once you have the point representation of the STL triangles, you can experiment with the clustering methods available in MATLAB to cluster the triangles.

You may refer to the MathWorks documentation for more information on clustering using the following link:

https://www.mathworks.com/discovery/clustering.html

After forming clusters using these point representations, you can uniquely map the points back to their respective triangles, thereby clustering the triangles.

I hope this helps!

Answer 2

[DGM]

How about we do what was requested without throwing away the most useful part of the information? This is modified from an answer from Bruno.

% an STL with two separate objects
unzip tubeplot2.stl.zip % for the forum
T = stlread('tubeplot2.stl');
[F V] = t2fv(T);

% find the connected components of the model
G = graph(F(:,[1 2]),F(:,[2 3]));
I = G.conncomp;

% split the model into objects
nobj = numel(unique(I));
Obj = cell(nobj,1);
for k = 1:nobj
    idx = find(I==k);
    thisV = V(idx,:);
    [b,thisF] = ismember(F,idx);
    thisF = thisF(all(b,2),:);
    Obj{k} = triangulation(thisF,thisV);
end

% plot the things
subplot(ceil(nobj/2)+1,2,[1 2]);
trisurf(T,'facecolor','w','edgecolor','none');
camlight
axis equal
xl = xlim; yl = ylim; zl = zlim;
for k = 1:nobj
    subplot(ceil(nobj/2)+1,2,k+2);
    trisurf(Obj{k},'facecolor','w','edgecolor','none');
    camlight
    axis equal
    xlim(xl); ylim(yl); zlim(zl);
end

There. An actual example. No incomplete AI-generated implementation of a questionable idea extrapolated from a blind fixation on a single word. If you want to know if objects are connected, check if they're connected. The centroid is not a measure of a triangle's extent or connectivity. Given a mesh of poor triangle quality, the centroids of two adjacent triangles will easily be farther apart than two unconnected triangles from completely different objects. It should be easy to come up with a model (the above tube plot may suffice) that would complicate simple clustering efforts. This is squarely in the realm of "just look at the thing", but the AI can't look at the thing. I guess it can't stop the user from copy-pasting all the nbsp's in the web-formatted output, either.

The above example works as shown (barring some spurious complications in older versions), but understand what it does. It subdivides the mesh into vertex-connected components. It suffices in this instance, but it's often more desirable to divide the mesh into edge-connected components. That's a bit more complicated than I'm going to cram into a forum post. This toolbox contains splitconncomp(), which will handle both vertex and edge connectivity. The output is a simple cell array. Included in the toolbox are demos. (See assorteddemos.m)

One thing that hasn't been mentioned is the size of the triangulation. If the length of the vertex list is strictly 3x the length of the face list, then either there are no connected triangles (which we can see is false), or the vertex list hasn't had all the redundant vertex copies pruned during import. If you're using MATLAB's built-in stlread(), the vertex list will be pruned such that it contains no duplicates. If you're using FEX #22409 or almost any other STL reader on the file exchange other than #51200 (or #182013), your vertex list will not be pruned. It will be full of duplicates.

Why is that important? It's important because if the vertex list is nonunique, we don't actually have connectivity anymore. This verifiably explains OP's other question about their triangulation object returning zero neighbors for every single triangle in the mesh. The triangles aren't spatially disconnected; the data is just full of redundant garbage that blinds us.

How do you fix it? Stop using old, incomplete decoders. If the F,V lists came from somewhere else, then prune them yourself:

% given F,V where V is nonunique
[Vpruned,~,IC] = unique(V,'rows','stable');
Fpruned = IC(F);