Multi-threading the mesh->solid converter

Here's the place for discussion related to coding in FreeCAD, C++ or Python. Design, interfaces and structures.
Forum rules
Be nice to others! Respect the FreeCAD code of conduct!
Gip-Gip
Posts: 3
Joined: Mon Jul 05, 2021 2:10 am

Multi-threading the mesh->solid converter

Post by Gip-Gip »

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
GeneFC
Veteran
Posts: 5373
Joined: Sat Mar 19, 2016 3:36 pm
Location: Punta Gorda, FL

Re: Multi-threading the mesh->solid converter

Post by GeneFC »

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
heda
Veteran
Posts: 1348
Joined: Sat Dec 12, 2015 5:49 pm

Re: Multi-threading the mesh->solid converter

Post by heda »

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...
Syres
Veteran
Posts: 2893
Joined: Thu Aug 09, 2018 11:14 am

Re: Multi-threading the mesh->solid converter

Post by Syres »

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:

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
So I'm assuming these all include some sort of mutithreading???
Gip-Gip
Posts: 3
Joined: Mon Jul 05, 2021 2:10 am

Re: Multi-threading the mesh->solid converter

Post by Gip-Gip »

GeneFC 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
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 later

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
wmayer
Founder
Posts: 20245
Joined: Thu Feb 19, 2009 10:32 am
Contact:

Re: Multi-threading the mesh->solid converter

Post by wmayer »

Gip-Gip wrote: Fri Aug 13, 2021 10:34 pm If I import a very detailed STL into FreeCAD and use the mesh-> solid converter, it only utilizes one thread and it takes forever.
When running the conversion then it takes a lot of time but also needs a huge amount of memory.
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
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.

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.
User avatar
jnxd
Posts: 951
Joined: Mon Mar 30, 2015 2:30 pm
Contact:

Re: Multi-threading the mesh->solid converter

Post by jnxd »

wmayer wrote: Wed Sep 15, 2021 11:13 am 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.
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.
wmayer
Founder
Posts: 20245
Joined: Thu Feb 19, 2009 10:32 am
Contact:

Re: Multi-threading the mesh->solid converter

Post by wmayer »

jnxd wrote: Thu Sep 16, 2021 2:16 am 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:
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.
wmayer
Founder
Posts: 20245
Joined: Thu Feb 19, 2009 10:32 am
Contact:

Re: Multi-threading the mesh->solid converter

Post by wmayer »

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.
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.

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;
} 
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.
User avatar
tanderson69
Veteran
Posts: 1626
Joined: Thu Feb 18, 2010 1:07 am

Re: Multi-threading the mesh->solid converter

Post by tanderson69 »

wmayer 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.
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. quilt



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.
Post Reply