Make various geogram functions thread-safe

[jdumas]

By "thread-safe" here I mean "being able to call geogram functions concurrently". E.g. being able to run Delaunay triangulation on two meshes in parallel (which can happen when integrating Geogram functions in a node-base application like Blender). This is why having a central scheduler (like OneTBB) helps a lot. Currently a lot of geogram routines use global static variables. Using thread_local instead would help. Some examples:

• CVT.h
• lbfgs_optimizers.cpp
• HLBFGS/LineSearch.cpp
• HLBFGS/ICFS.cpp

Ideally this should be tested with ThreadSanitizer by calling Delaunay triangulation on a few meshes in parallel...

[BrunoLevy]

ForLBFGS/ HLBFGS, Dmitry Sokolov wrote a new version, that probably does not have all these globals. I'll take a look !

[Abenabbou]

Hi Bruno,
We have the same issue in SLB for 2D Delaunay triangulation. We cannot call this algorithm in parallel. Actually, we can have millions of 2d patchs (point sets) that we want to triangulate in parallel. We use openMP (we tried also with TBB) to parallelize the call to the 2D Delaunay triangulation.

Please let me know if you need data set to reproduce the issue.

Thanks,
A. Benabbou

[BrunoLevy]

Hi @Abenabbou,

• Which class do you use for 2D Delaunay triangulation ?

• What are the symptoms ? If it is a crash, did you take a look at the stack trace ? Where was it ?

• The class Delaunay2d uses the citation system that has globals, it may be the culptrit (I will deactivate it or make it optional in a future release). In the meanwhile, you can try commenting-out the cite() function in src/lib/geogram/bibliography.cpp.

• If what you need is constrained 2D Delaunay triangulation, the class DelaunayTriangle is a wrapper around Jonathan Shewchuk's constrained Delaunay triangulation Triangle code, but it is not thread-safe, but...

• ...there is a new CDT2d class in geogram/delaunay/CDT_2d.h (available in the current version 1.8.4-rc from the repository). See comments at the end of the file for the "operating manual". It does both constrained and unconstrained 2D Delaunay triangulation. This one works super well in parallel (I designed it with this requirement, because me too, I had zillions 2d patches to triangulate). If you use the batch insertion function, you may need to call Process::enable_multithreading(false) before (else spatial search used by batch insertion will try to run in parallel, which you do not want if you are already in parallel...).

[Abenabbou]

Hi @BrunoLevy,
Thank you for your answer. Below the answers to you questions.

- Which class do you use for 2D Delaunay triangulation ?

We use the factory in Delaunay::create(2) after settings the args in cmdline. Below how we do it:

GEO::initialize(GEO::GEOGRAM_NO_HANDLER);
  //create a delaunay algo
  CmdLine::import_arg_group("standard");
  CmdLine::import_arg_group("algo");
  CmdLine::declare_arg(
    "convex_hull", false,
    "compute just the convex hull of the points"
  );
  CmdLine::declare_arg(
    "dimension", 2, "3 for 3D, 2 for 2D"
  );
  CmdLine::set_arg("algo:delaunay", "BDEL2d");
   -----------------------this is the part we want to call in //----------------
  GEO::Delaunay_var delaunay2d = GEO::Delaunay::create(2);
  delaunay2d->set_vertices((GEO::index_t)pts.size()/2, pts.data());

What are the symptoms ? If it is a crash, did you take a look at the stack trace ? Where was it ?

yes we have a crash. Below the trace of the crash (from a Gtest):

    GEO::Biblio::cite(const char * ref, const char * file, int line, const char * function, const char * info) Line 194    C++
    GEO::Delaunay2d::Delaunay2d(unsigned char dimension) Line 116    C++
    GEO::FactoryCreator1<GEO::Delaunay,unsigned char>::create<GEO::Delaunay2d>(const unsigned char & param1) Line 332    C++
     GEO::Factory1<GEO::Delaunay,unsigned char>::create_object(const std::string & name, const unsigned char & param1) Line 362    C++
    GEO::Delaunay::create(unsigned char dim, const std::string & name_in) Line 162    C++

The class Delaunay2d uses the citation system that has globals, it may be the culptrit (I will deactivate it or make it optional in a future release). In the meanwhile, you can try commenting-out the cite() function in src/lib/geogram/bibliography.cpp.

Yes we have already done this and it woks, as you said a temporary solution!

CD2T

This is a very good news :), we will give it a try and let you know. We have already a CD2T in house, for that we use your D2T and insert the constraints by an algorithm we have in our side. In our algorithm, we have the option to restore the Delaunay after constraints insertion and we don't have additional point (Steiner). Is your CD2T has these features too?

Regards,
Azeddine

[BrunoLevy]

Hi Azeddine,

Yes, the CDT2d class has the option to restore Delaunayness after constraints insertion, and does not insert Steiner points. It also handles intersecting constraints (then it automatically inserts the intersection in the triangulation)

[Abenabbou]

Thank you Bruno. We will try it.

[jdumas]

ForLBFGS/ HLBFGS, Dmitry Sokolov wrote a new version, that probably does not have all these globals. I'll take a look !

Is this version available somewhere btw?

[BrunoLevy]

Yes, here
(Note: licensed under Afferro GPL)

[jdumas]

Would you be able to use it in Geogram under a different license then?

[BrunoLevy]

It would be problematic for some users of geogram in the industry,
but it will be OK for some others...

[jdumas]

If Dmitry doesn't want to release his implementation under a permissive license, it'd be good to make it possible to plug other L-BFGS implementations into Geogram, e.g. via the use of a templated or polymorphic interface. E.g. I've used CppNumericalSolvers in the past and I like how it's designed. There's also optim which has a permissive license and a few interesting features. In any case it'd be good to make the L-BFGS backend solver configurable so we can hook up a thread-safe implementation for industrial applications.