What algorithm does rhino use to parse an stl file into disjoint meshes

Hi there,

We’re writing a custom piece of code to control a resin based dlp-3d-printer.
In the software i would like to be able load an .stl file and recognize disjoint meshes.

I noticed Rhino does this very fast.
Even if i manually hussle the facets in a ascii .stl file rhino still figures out correctly that i disjoint meshes.
(So it doesn’t use the order of the facets either)

Is there any commonly accepted algorithm that is used for recognizing this?
I’ve written a test algorithm that detects neighbours of faces but it behaves very slow with large stl files.

Thought i ask here :slight_smile:

kind regards,
Elco

If your code ran as a Rhino plug-in, then you could just call RhinoSplitDisjointMesh (C++) or Rhino.Geometry.Mesh.SplitDisjointPieces (.NET) to split a mesh into its ts unconnected pieces.

Hi Dale,

I’m affraid that’s not possible; it’s a stand alone application with it’s own stl importer and handling.

I’m just looking for info on what the most efficient algorithms are. If any.

Perhaps the sharper question is what the most efficient way is to get the mesh connectivity map out of an .stl file?
I’m assuming that is how rhino stores it’s meshes internally as well?

kind regards,
Elco

I found this post:

It basically says loop over all faces and create the connectivity-matrix one by one.
But then you would have to loop something in the order of n! times checking all previous index vertices for existence…

How does rhino solve this trick?

All meshes in Rhino are represented by ON_Mesh. To split disjoint meshes, use ON_Mesh::GetConnectedComponents.

Hi Dale,

I found some time to research it further; in case anyone ever finds this topic this seems to be the answer:
The algoritm that is used most commonly is the use of a HashTable (in .NET a Dictionary) to create the mesh connectivity. (probably rhino also uses this under the hood)

A dictionary allows for superfast search for a key. (constant time).
So if you take your vertices as keys you can quickly process all vertices from a .stl file (triangle soup) into an indexed version.

Next phase is then determining the neighbours and and storing it as a directed-edge structure.
This allows for fast processing of local errors in the stl and should also allow for finding the disjoint meshes.

Elco