Multi-threading the mesh->solid converter
Forum rules
Be nice to others! Respect the FreeCAD code of conduct!
Be nice to others! Respect the FreeCAD code of conduct!
Multi-threading the mesh->solid converter
If I import a very detailed STL into FreeCAD and use the mesh-> solid converter, it only utilizes one thread and it takes forever.
Would anyone know if this is already being worked on, or which files I should look at if I want to multi-thread the converter? Any help would be appreciated
Would anyone know if this is already being worked on, or which files I should look at if I want to multi-thread the converter? Any help would be appreciated
Re: Multi-threading the mesh->solid converter
FreeCAD and most of the libraries are single thread. However, some mesh ops are multi-thread.
If you give a bit more information about exactly what you are doing you might get some helpful suggestions.
I have definitely seen multi-thread in the mesh ops used in the Path WB, but I do not know anything about importing STL meshes.
Gene
If you give a bit more information about exactly what you are doing you might get some helpful suggestions.
I have definitely seen multi-thread in the mesh ops used in the Path WB, but I do not know anything about importing STL meshes.
Gene
Re: Multi-threading the mesh->solid converter
importing detailed stl's and converting to shapes is a useful workflow for the 3d print crowd.
and as you have noticed fc is getting slow on this when tri-count goes up.
your aim should rather be multi-process, and turning fc into an application that can do multicore is going to be tricky - most "commercials" also do not do this..., so unless you really know what you are doing in terms of core code and already know all there is about multicore needs (since you would likely have to upgrade code in also external libraries) - I would guess that you have a long road ahead to make something workable.
but lets not get discouraged over that...
fc already now in several places calls external programs and picks up the results from those (by writing temp files to disk).
that is a path to a poor man's multi-processing capability
this way you could use to get access to multicore ability, so you could write a fc-macro that goes something like this...
- import stl into fc gui
- split the stl into chunks, lets say 2 chunks less than your core count
- write all chunks but one to disk
- start subprocesses that picks up these chunks on disk in a new freecadcmd session and
--- imports temp stl
--- makes mesh to shape (possibly a refine as well...)
--- writes result to disk as a fc-file (just the shape)
- in your main process (the gui one)
--- run the mesh to shape
--- gather the chunks made by other fc-sessions and merge them
all this of course comes with a substantial start-up time and memory overhead, but could very well be worth it if you have more than 4 cores.
just remember to leave at least one core free, unless you want to freeze up the whole computer...
and as you have noticed fc is getting slow on this when tri-count goes up.
your aim should rather be multi-process, and turning fc into an application that can do multicore is going to be tricky - most "commercials" also do not do this..., so unless you really know what you are doing in terms of core code and already know all there is about multicore needs (since you would likely have to upgrade code in also external libraries) - I would guess that you have a long road ahead to make something workable.
but lets not get discouraged over that...
fc already now in several places calls external programs and picks up the results from those (by writing temp files to disk).
that is a path to a poor man's multi-processing capability
this way you could use to get access to multicore ability, so you could write a fc-macro that goes something like this...
- import stl into fc gui
- split the stl into chunks, lets say 2 chunks less than your core count
- write all chunks but one to disk
- start subprocesses that picks up these chunks on disk in a new freecadcmd session and
--- imports temp stl
--- makes mesh to shape (possibly a refine as well...)
--- writes result to disk as a fc-file (just the shape)
- in your main process (the gui one)
--- run the mesh to shape
--- gather the chunks made by other fc-sessions and merge them
all this of course comes with a substantial start-up time and memory overhead, but could very well be worth it if you have more than 4 cores.
just remember to leave at least one core free, unless you want to freeze up the whole computer...
Re: Multi-threading the mesh->solid converter
Not surprisingly this has been brought up before, even as far back as 2012. I searched for QtConcurrent in the source code and found the following files:
So I'm assuming these all include some sort of mutithreading???
Code: Select all
src\Mod\Inspection\App\InspectionFeature.cpp
src\Mod\Mesh\App\Core\Curvature.cpp
src\Mod\Mesh\App\Core\Functional.h
src\Mod\Mesh\Gui\ViewProvider.cpp
src\Mod\MeshPart\Gui\CrossSections.cpp
src\Mod\Part\Gui\CrossSections.cpp
src\Mod\Points\App\Points.cpp
src\Mod\Points\App\Properties.cpp
src\Mod\ReverseEngineering\App\ApproxSurface.cpp
src\Mod\Sandbox\Gui\Command.cpp
Re: Multi-threading the mesh->solid converter
I'm going to be 100% honest, I just wanted to tinker with multithreading and I currently do not have a 100% solid plan. Or at least I won't until I look at the code a bit, will get to that laterGeneFC wrote: ↑Fri Aug 13, 2021 11:11 pm FreeCAD and most of the libraries are single thread. However, some mesh ops are multi-thread.
If you give a bit more information about exactly what you are doing you might get some helpful suggestions.
I have definitely seen multi-thread in the mesh ops used in the Path WB, but I do not know anything about importing STL meshes.
Gene
But I assume the conversion process can at the very least be created on it's own thread, so freecad doesn't completely freeze when performing long operations (not that this matters too much, but I want to know the converter is working, not if freecad just tripped and died)
And my main hope is that I can create multiple threads to divide and conquer the mesh->stl process. Though I still need to look at it because I'm not sure how that process works
Re: Multi-threading the mesh->solid converter
When running the conversion then it takes a lot of time but also needs a huge amount of memory.
Theoretically it's possible to make it multi-threaded because a set of facets can be split into several sub-sets and each thread could work on one sub-set. However as said above the memory usage is high and if now all threads need the memory at the same time it could happen that it exceeds the limit or starts to swap. In the worst case an exception (inside a thread) might be thrown and if not handled by OCCT it will cause FreeCAD to crash.Would anyone know if this is already being worked on, or which files I should look at if I want to multi-thread the converter? Any help would be appreciated
You find the current implementation in TopoShape::setFaces. There we create a compound and add each triangle as a trimmed face. Afterwards a sewing algorithm must be executed to build up the correct Brep structure and that's the CPU-intensive and memory-hungry part.
IMO, what we should have a look at is a lower-level API of OCCT where we could directly set up the Brep structure. The BRepBuilderAPI_Sewing class needs to restore a lot of information that we already have for free.
Re: Multi-threading the mesh->solid converter
I'm not entirely sure right now what you're talking about, but having to restore information we already had in the first place (and trying to speed it up using threading) is a theme I encountered before here: https://forum.freecadweb.org/viewtopic. ... 10#p525587. That one, however, required features that weren't taken from salome-mesh into FC's "3rdparty" folder.
My latest (or last) project: B-spline Construction Project.
Re: Multi-threading the mesh->solid converter
To the function TopoShape::setFaces we pass an array of 3d points and another array of triangular facets. For each facet we have three indices that point to a position inside the point array. In other words we already know all facets that share the same 3d point and we can also easily determine the edges that are shared by two adjacent facets.
However, when creating the shape we make a face from a triangular facet and put that into a compound (it's just a container of shapes). At this point we have duplicated all vertexes and edges that might be shared by other faces so that the sewing algorithm then has to restore this lost information.
Re: Multi-threading the mesh->solid converter
Currently each created face has its own vertexes and edges and when running the sewing algorithm over the shape it has a hard job because it must identify all vertexes that are geometrically coincident with the vertexes of other faces. The same must be done for edges.However, when creating the shape we make a face from a triangular facet and put that into a compound (it's just a container of shapes). At this point we have duplicated all vertexes and edges that might be shared by other faces so that the sewing algorithm then has to restore this lost information.
Code: Select all
void TopoShape::setFaces(const std::vector<Base::Vector3d> &Points,
const std::vector<Facet> &Topo, float Accuracy)
{
gp_XYZ p1, p2, p3;
std::vector<TopoDS_Vertex> Vertexes;
std::map<std::pair<uint32_t, uint32_t>, TopoDS_Edge> Edges;
TopoDS_Face newFace;
TopoDS_Wire newWire;
BRepBuilderAPI_Sewing aSewingTool;
Standard_Real x1, y1, z1;
Standard_Real x2, y2, z2;
Standard_Real x3, y3, z3;
aSewingTool.Init(Accuracy, Standard_True);
TopoDS_Compound aComp;
BRep_Builder BuildTool;
BuildTool.MakeCompound(aComp);
uint32_t ctPoints = Points.size();
Vertexes.resize(ctPoints);
// Create array of vertexes
auto CreateVertex = [](const Base::Vector3d& v) {
gp_XYZ p(v.x, v.y, v.z);
return BRepBuilderAPI_MakeVertex(p);
};
for (std::vector<Facet>::const_iterator it = Topo.begin(); it != Topo.end(); ++it) {
if (it->I1 < ctPoints) {
if (Vertexes[it->I1].IsNull())
Vertexes[it->I1] = CreateVertex(Points[it->I1]);
}
if (it->I2 < ctPoints) {
if (Vertexes[it->I2].IsNull())
Vertexes[it->I2] = CreateVertex(Points[it->I2]);
}
if (it->I3 < ctPoints) {
if (Vertexes[it->I3].IsNull())
Vertexes[it->I3] = CreateVertex(Points[it->I3]);
}
}
// Create map of edges
auto CreateEdge = [&Vertexes, &Edges](uint32_t p1, uint32_t p2) {
// First check if the edge of a neighbour facet already exists
// The point indices must be flipped.
auto key1 = std::make_pair(p2, p1);
auto key2 = std::make_pair(p1, p2);
auto it = Edges.find(key1);
if (it != Edges.end()) {
TopoDS_Edge edge = it->second;
edge.Reverse();
Edges[key2] = edge;
}
else {
Edges[key2] = BRepBuilderAPI_MakeEdge(Vertexes[p1], Vertexes[p2]);
}
};
auto GetEdge = [&Edges](uint32_t p1, uint32_t p2) {
auto key = std::make_pair(p1, p2);
return Edges[key];
};
for (std::vector<Facet>::const_iterator it = Topo.begin(); it != Topo.end(); ++it) {
CreateEdge(it->I1, it->I2);
CreateEdge(it->I2, it->I3);
CreateEdge(it->I3, it->I1);
}
for (std::vector<Facet>::const_iterator it = Topo.begin(); it != Topo.end(); ++it) {
if (it->I1 >= ctPoints || it->I2 >= ctPoints || it->I3 >= ctPoints)
continue;
x1 = Points[it->I1].x; y1 = Points[it->I1].y; z1 = Points[it->I1].z;
x2 = Points[it->I2].x; y2 = Points[it->I2].y; z2 = Points[it->I2].z;
x3 = Points[it->I3].x; y3 = Points[it->I3].y; z3 = Points[it->I3].z;
p1.SetCoord(x1,y1,z1);
p2.SetCoord(x2,y2,z2);
p3.SetCoord(x3,y3,z3);
if ((!(p1.IsEqual(p2,0.0))) && (!(p1.IsEqual(p3,0.0)))) {
const TopoDS_Edge& e1 = GetEdge(it->I1, it->I2);
const TopoDS_Edge& e2 = GetEdge(it->I2, it->I3);
const TopoDS_Edge& e3 = GetEdge(it->I3, it->I1);
newWire = BRepBuilderAPI_MakeWire(e1, e2, e3);
if (!newWire.IsNull()) {
newFace = BRepBuilderAPI_MakeFace(newWire);
if (!newFace.IsNull())
BuildTool.Add(aComp, newFace);
}
}
}
aSewingTool.Load(aComp);
#if OCC_VERSION_HEX < 0x070500
Handle(Message_ProgressIndicator) pi = new ProgressIndicator(100);
pi->NewScope(100, "Sewing Faces...");
pi->Show();
aSewingTool.Perform(pi);
#else
aSewingTool.Perform();
#endif
_Shape = aSewingTool.SewedShape();
#if OCC_VERSION_HEX < 0x070500
pi->EndScope();
#endif
if (_Shape.IsNull())
_Shape = aComp;
}
Only with this change the computation time goes down by around a third.
As an example I had a mesh with 42,000 triangles. The non-optimized algorithm takes 1:25 min and the optimized algorithm takes 1:00 min.
At this point the sewing algorithm still has to figure out the shells (a set of connected faces) from the compound. The result might be a single shell or a compound of shells.
If it's OK not to have a single shell/compound of shells but a compound of faces then we can even disable the sewing algorithm which further reduces computation time. With my test mesh file the algorithm only takes 7 s.
- tanderson69
- Veteran
- Posts: 1626
- Joined: Thu Feb 18, 2010 1:07 am
Re: Multi-threading the mesh->solid converter
If you build up with the correct topo sharing as suggested, you can then 'quilt' instead of 'sew'. I believe it is much faster, but haven't profiled. quiltwmayer wrote: ↑Fri Oct 01, 2021 12:25 pm The algorithm above is much faster because beforehand it creates two containers for all vertexes and all edges and then it creates a face for each triangle that already shares the same vertex/edge as its adjacent triangles.
Only with this change the computation time goes down by around a third.
As an example I had a mesh with 42,000 triangles. The non-optimized algorithm takes 1:25 min and the optimized algorithm takes 1:00 min.
At this point the sewing algorithm still has to figure out the shells (a set of connected faces) from the compound. The result might be a single shell or a compound of shells.
If it's OK not to have a single shell/compound of shells but a compound of faces then we can even disable the sewing algorithm which further reduces computation time. With my test mesh file the algorithm only takes 7 s.
IMHO: The practice of bringing in meshes and converting to solids or any TopoDS_Shape should be discouraged. For TopoDS_Shapes the complexity of the shape is designed into the surface definitions and not into topological connections at scale. My guess is users want to convert to solid to do some operations that are missing from the mesh workbenches. I think that is the real problem.