DGtal 1.3.0
|
Part of the Geometry package.
This part of the manual describes what are plane-probing estimators, how to define and use them to estimate normals on digital surfaces.
The following programs are related to this documentation: geometry/surfaces/examplePlaneProbingTetrahedronEstimator.cpp, geometry/surfaces/examplePlaneProbingParallelepipedEstimator.cpp, geometry/surfaces/examplePlaneProbingSurfaceLocalEstimator.cpp, testDigitalPlanePredicate.cpp, testPlaneProbingTetrahedronEstimator.cpp, testPlaneProbingParallelepipedEstimator.cpp.
A plane-probing algorithm (see [69], [101] and [73]) computes the normal vector of a set of digital points from a starting point and a predicate InPlane: "Is a point x in the set of digital points?". This predicate is used to probe the set as locally as possible and decide on-the-fly the next points to consider, in order to deform a particular set of points, which is tangent by construction. The growth direction is given by both arithmetic and geometric properties. The main characteristics of these algorithms is that no parameter is required for the analysis of the local geometry of digital surfaces. Furthermore, they present theoretical guarantees, most notably they extract the exact normal vector of any digital plane.
The first kind of plane-probing algorithms is based on the deformation of a tetrahedron. The objective of the algorithm is to iteratively update one vertex of this tetrahedron until one of its faces is parallel to the digital set. The update procedure will consist in selecting a point inside a candidate set. Multiple candidate sets have been proposed but we will start by describing the simplest one, the so-called H-neighborhood. We start by illustrating its behavior when the digital set is a digital plane segment. The next image shows the initial state of the estimator. We will denote by \( (v_k)_{0 \leq k \leq 2 } \) the three vertices of the base triangle (the blue disks on the left), \( q \) a fixed point outside the set at the top of the tetrahedron (the blue circle). Points that are inside the digital set will be denoted by disks while points that are outside by circles.
We now describe the update procedure in more details, see the next figure.
At a given iteration, the update step consists of the following substeps:
The algorithm stops whether one of the following criteria is verified:
Other candidate sets were proposed namely the R-neighborhood [69] and an optimization that we call R1-neighborhood [73]. The main difference is that instead of considering 6 points of an hexagon, they consider 6 rays. This allows to reduce the number of steps and to obtain a reduced basis at the end. We recommend to use the R1-neighborhood.
The main drawback of this category of algorithms is the fact that they return the correct normal vector on a digital plane only when starting from specific points (precisely reentrant corners of low height). In all other cases, the estimated normal is only an approximation. In the next section, we will present another kind of estimator that can be initialized on any surfel of a digital surface and which returns the correct normal on every surfel of a digital plane.
The second kind of plane-probing algorithms is based on the deformation of a pair of tetrahedra i.e. a parallelepiped introduced in [73]. The parallelepiped is ensured to always be separating (one point is always inside the digital set and one point always outside). This approach allows to start the algorithm on any surfel (at least 4 points inside the digital set) and is more general than the previous one.
This approach is internally based on a new predicate NotAbove that is able to tell whether a digital point \( x \) has a height that is smaller or greater than the one of \( q \). It is easy to see that it can be implemented using ray-casting and the InPlane predicate. It naturally increases the number of calls to InPlane but has several advantages. See [73] or this presentation (in French) for more details.
We will denote by PH, PR and PR1 the three variations of the parallelepiped estimator for the three different candidate sets.
Algorithm | Principle | Initialization | Candidate Set |
---|---|---|---|
H | Downward oriented tetrahedron | Any reentrant corner | 6 points in a hexagon |
R, R1 | Downward oriented tetrahedron | Any reentrant corner | 6 points + 6 rays |
PH | Separating parallelepiped | Any point | 6 points in a hexagon |
PR, PR1 | Separating parallelepiped | Any point | 6 points + 6 rays |
In DGtal, both categories of plane-probing estimators are implemented, see PlaneProbingTetrahedronEstimator for the first category and PlaneProbingParallelepipedEstimator for the second one. In the following, we explain the API for PlaneProbingTetrahedronEstimator.
The general way of instantiating a plane-probing estimator is the following:
And to use it:
The common services shared by plane-probing estimators are the following:
Probing services:
Services specific to PlaneProbingParallelepipedEstimator :
The PlaneProbingDigitalSurfaceLocalEstimator adapter can use any plane-probing estimator class to estimate normals on a digital surface. It is a model of concepts::CSurfelLocalEstimator and concepts::CDigitalSurfaceLocalEstimator.
The definition and instantiation is done as follows:
And to use it:
The parameters that are specific to this estimator are the following:
Model of concepts::CSurfelLocalEstimator :
Model of concepts::CDigitalSurfaceLocalEstimator :
To implement your own candidate set, you need to do the following steps: