Does geogram support incremental Delaunay?

[kimren227]

Hi,

Thank you for providing this wonderful repository! Really appreciated it.

I am doing a research project that involves the iterative addition of vertices (~1K vertices) to an existing 3D Delaunay (~10M vertices). The implementation in Geogram is quite fast, but I am curious if there are any ways to avoid rebuilding the entire 3D Delaunay from scratch in each iteration.

Best regards,

Daxuan

[BrunoLevy]

(I'm sorry I am a bit slow to answer, need to finish a batch of changes / bugfixes then I'll come back to you right after).

[servantf]

Hello,

Same question here.

Fabien

[vcbsousa]

Hello Bruno,

I would really appreciate if you could address the question on this topic.
I also have the same inquiry as these other two people.

Thank you.

Victor

[BrunoLevy]

Situation for Delaunay2d, Parallel/Periodic Delaunay3d:

Hello, incremental Delaunay is not (yet) part of the API, but internally the implementation uses incremental insertion. For now, the easiest way is probably to derive your own class from Delaunay.

There are several reasons why iterative insertion is not exposed:

• the implementation uses spatial sorting internally to make insertion faster
• there are two different modes, depending on whether infinite tetrahedra / infinite triangles should be kept or not, and iterative insertion can only work if infinite triangles are stored

(but maybe I'll expose the functionality in a future version if it does not break too many things, keeping the API coherent is a bit subtle here...)

Situation for CDT2d,ExactCDT2d:

The situation is different from the Constrained 2D Triangulation class of geogram, that supports both point-by-point and batch insertion (as well as constraints enforcement, in any order).

[vcbsousa]

Hello Bruno,
Thank you so much for your reply!
It was very enlightening.
Can I ask you a follow up question?
How would you go about deriving your own delaunay class for the parallel/periodic delaunay3d that would support the iterative reconstruction of the graph?
It would be very helpful if you could provide insights into which functions to look into.
I appreciate your help.
Sincerely,
Victor

[BrunoLevy]

Hi Victor,
I guess that you will want performance / the multithreaded version, that add some difficulties (so let us suppose that).
There are even more difficulties if you consider periodic boundary conditions. Let us start with the case without boundary conditions:

without periodic boundaries

You will need to inherit from ParallelDelaunay3d.

• You will need to set keep_infinite_tetrahedra (else insertion of additional points outside the convex hull will not work).
• You will probably store your points in a std::vector, and the base address may change each time you insert new points in it, so you need to update points_ and nb_points_ each time a new point is inserted.
• Insertions are made by the (inner) ParallelDelaunayThread class, so you will need to keep one of them active and properly initialized for each time you want to insert a point.

With periodic boundary conditions

You will need to inherit from PeriodicDelaunay3d.

All what I said in previous paragraph applies, plus there is a handle_periodic_boundaries() function that detects the Voronoi cells that cross the domain boundary and "sends them on the other side" as need be. So you will need to keep the information of what vertex was sent where (which is stored temporarily already, but you will need to make this information stored permanently), then you will need to call the function after each insertion of additional point(s), taking into account what was done before (yes, it is complicated !!!)

[vcbsousa]

Last question Bruno.
Thank you for all the help so far.
I have done the steps you mentioned in the without periodic boundaries case but I am having trouble with the threads themselves.
How do I keep them active and properly initiatialized?
At this moment I am trying to use a single thread to add the extra points in my regeneration step and I am updating the pointers to the master_ delaunay, the nb_vertices_ and the vertices_ vector, etc..
i am updating all of the quantities that are initialized when a new thread object is created except for the ones updated by the set_pool subroutine. I am not sure what to do in the case where I just want to add extra points instead of computing the whole graph.
Maybe I am thinking about this in the wrong way. Should I just created new thread objects that just operate on the extra points?
Any guidance would be helpful.
Sincerely,
Victor

[BrunoLevy]

See also this discussion

[BrunoLevy]

The easiest way is to use the DelaunayThread objects already created in set_vertices(). For instance, you can use thread 0, update its interval of points to be added using set_work(), then call the run() function directly.

There may be a catch: the set_vertices() function has an "epilogue", that "compresses" the arrays. By "compressing", I mean removing the "gaps", that come from unused tetrahedra, but in your case you want to reuse these "gaps" when creating the new tets required by the new points, so you may need an option to not call "compress".

If you have many additional points to insert, then you may want to insert them in parallel, so you will need to do two different things:

• pre-allocate the tets (using an estimate of their numbers)
• call set_work() for each thread
• call run_threads()
• if some points were not inserted due to not enough tets allocated, then insert them sequentially using thread0 (like in the existing code in set_vertices()

Another (important !) couple of things:

• in the new code, use assertion checks whenever there is something with indices
• create a set of test cases / non-regression test
• test in release, debug mode, test with valgrind
  (doing so saved the day ... almost every day !)

[BrunoLevy]

Refactoring planned, see #217

[vcbsousa]

Awesome!.. looking forward to it!

[BrunoLevy]

Please be patient ! (it is not a small refactoring !!)

[vcbsousa]

No rush!.. I am just excited about it.