DGtal & Octree structures

[FMRobS]

Hello,
I am quite new to DGtal, but I have had a good look around many of its packages. For accelerating digital geometry calculations, I would expect spatial acceleration structures like octrees. Is this already supported and have I overlooked it? I am especially interested in thickness calculations of rather thin shell-like 3d objects (therefore dealing with sparse domains).
What are the options with a digital geometry approach, is this (octrees) something that can be trivially implemented?

On another note:
I have read your works on fast thickness calculations. Am I correct that using a (squared) DT as weight image to a PowerMap is the straightforward method? Is there performance gain by generating both at the same time?

Feel free to correct me, I am looking forward to an answer!

Kudos to the DGtal team for this amazing project

[JacquesOlivierLachaud]

Thanks for your interest in DGtal !
Although it could seem quite natural in a digital geometry setting --- and also not very complex to write --- octrees are not implemented yet in DGtal. I have a vague souvenir of ImageContainerByHashTree that can be used for an image octree (@dcoeurjo it think you had written an example at the time), but there is no official way to handle and store hierarchical structures.
In fact, in most digital geometry processing algorithm, an octree structure does not really help.
Quite recently I had discussion with David about dedicated encoded DAG structures to represent huge 3D scenes, like octrees but with similar branches not replicated, but it stayed more as a discussion.
For thickness computation, I let David answer (@dcoeurjo )

[dcoeurjo]

I confirm for the data structure: we do have an experimental octree image container (https://dgtal-team.github.io/doc-nightly/classDGtal_1_1experimental_1_1ImageContainerByHashTree.html) you can play with. We also have a (quite old) branch that uses openvdb containers for sets and images, but nothing stable yet.

For distance computation (and Voronoi/Power diagram construction), the container does not solve the problem completely as you would need to rethink the sweeping process (in the optimal Voronoi map construction for regular grids) for adaptive grids which is not easy.

Concerning the thickness problem, yes power maps are good starting point but it may depend on the exact definition of thickness you are interested in (is it: "At a given interior point p, the thickness is the largest ball in the shape containing p"?). I do have some papers on that subject, feel free to contact me directly if you want to discuss a bit more about that (I have this in mind for instance).

[FMRobS]

Hi David,
I have read your papers [23] and [31] on the matter (using the DGtal documentation references), the maximal ball is indeed what I am looking for. For our case the thickness function is only to be evaluated on the surface.
Do I understand the following correctly:

• The Optimal separable algorithms for EDT are not implemented in DGtal, however the Voronoi based DT is also linear in the number of points
• From [31] I concluded that by using DGtal, a straightforward way for evaluating the thickness function, would be to take the Square EDT as weight image to the power map.
• Does the power mapping then result in the sites 'Sk' (as in [23]), and do I still need to filter them?
• Because I only regard the thickness function on the boundary, the Tau_PI labelling is sufficient compared to the Tau_PI' (Figure 4 in [31])

I understand now that the Voronoi sweeping is not easily solved by an octree representation. I just want to avoid iteration over the large block of empty space. Maybe a simple custom CDomain implementation will also work. I guess octrees are most useful for 3D intersection problems, which is not often the case in digital geometry?
I know I am asking a lot of questions, feel free to answer on what you want.
Regards,

[dcoeurjo]

[..]

• The Optimal separable algorithms for EDT are not implemented in DGtal, however the Voronoi based DT is also linear in the number of points

Not exactly: the EDT can be obtained directly from the (separable) Voronoi map. They both have the exact same complexity (optimal, separable, linear in time), cf https://dgtal-team.github.io/doc-nightly/moduleVolumetric.html

• From [31] I concluded that by using DGtal, a straightforward way for evaluating the thickness function, would be to take the Square EDT as weight image to the power map.

To be more precise: the non-empty cells of the power map give you the inscribed maximal ball. To get the largest one containing a given point, you can either scan the list of maximal balls (linear if you don't have accelerating data structure) and keep the largest one, or approximate that from the Powermap labelling (with the greedy approach to "push the boundaries" that is described in the ref I gave you).

• Does the power mapping then result in the sites 'Sk' (as in [23]), and do I still need to filter them?

Sk of [23] is a subset of the non-empty cells of the Power map (the extra filtering leading to Sk is not yet in DGtal but not that difficult to implement).

• Because I only regard the thickness function on the boundary, the Tau_PI labelling is sufficient compared to the Tau_PI' (Figure 4 in [31])

Let me check that fig..

I understand now that the Voronoi sweeping is not easily solved by an octree representation. I just want to avoid iteration over the large block of empty space. Maybe a simple custom CDomain implementation will also work. I guess octrees are most useful for 3D intersection problems, which is not often the case in digital geometry?

Well, Sparse representation like HashTree are super useful to store large sparse data, with many use-cases for image/geometry processing . The extension of separable sweep line approaches to irregular data is not trivial but feasible (see Refs) but not in DGtal.

I know I am asking a lot of questions, feel free to answer on what you want.

Depending on your context, there are several strategies you could implement to "skip" irrelevant part of the domain (multigrids, narrowing approaches,..). If you want, fill free contact me by email directly if you want to discuss a bit more about that according to your data (not easy on Github discussion).