End of engeenering studies project
(ENSIMAG-ENSERG), done
in collaboration with Total and the laboratory LIS (Laboratory of Image
and signals, Grenoble). During this project, I achieved an algorithm
able to cut a surface at its thicknesses. This was based on a new
theoretical approach using the critical points of the distance
function, computed using the tetrahedrisation of Delaunay. Application
was to cut potential reserves of hydrocarbures.
ALGORITHM
Without any
details, basics steps are :
Delaunay
tetrahedrisation computation and its dual Voronoi graph,
using the CGAL library
Computation
of the critical points of the distance function, as the
intersections of Voronoi Graph and its dual Delaunay tetrahedrisation.
Computation
of the stable manifold of the level 2 critical point, as
surface that are a boundary between two sub-parts of the objects
Computation
of the stable manifold
of the level 3 critical point, as the inner part of
an union of stable manifold of critical points of level 2.
Filtering
of the critical points of level
3( these are the maxima of the distance
function, ie the subobjects) that are outside the given input surface
Merge
between some subobjects, if the thickness between them is
weak
Deletion
of small objects
ILLUSTRATIONS
Here is a simple example of a
closed surface
we want to cut as an human would do, in two equal parts. Black dots are
the surface vertices.
In read are the two found maxima of
the distance function. These are the two critical point of level 3. la
fonction distance.
The green surface is a stable
manifold of an
interesting critical point of level 2 (shown in green, as the
intersection of a delaunay triangle and its dual a Voronoi edge). The
blue path is the gradient descent on the two sides of the critical
point, leading to two associated critical points of level 3..
This single triangle is also a
stable manifold
of a critical point of level 2. It is a border between an
inner
maximum of the distance function, and another maximum, outside the
object that is at the infinite.
The stable manifold of a critical
point of level 3. Clearly, it is a desirable sub-object
In red are themaxima. In blue are
the critical points of level 1.
We can see here that for a more
complex object, there are many maxima, not all corresponding to a
sub-object.
An even more complicated sub-object.
And its many maxima
Here, all maxima are associated to a
sub-object.
Some maxima are merged and that
leads to the correct segmentation.
It works on this bone
A little problem, the cut could be
more precisely positionned on the legs.
