Ponca
576dd57931a6c531adad849a291f29a0ff031401
Point Cloud Analysis library

The fitting module is dedicated to the smooth fitting of point clouds and extraction of useful geometric properties. Figure 1(a) shows a typical example in 2D: we reconstruct a potential function (shown in fake colors) from a few 2D points equipped with normals; then the 0isoline of this potential gives us an implicit curve (in orange) from which we can readily extract further properties like curvature. A great benefit of this implicit technique [6] is that it works in arbitrary dimensions: Figures 1(bc) show how we reconstruct an implicit 3D surface with the same approach, starting from a 3D point cloud. Working with meshes then simply consists of only considering their vertices.
This is just the tip of the iceberg though, as we also provide methods for dealing with points equipped with nonoriented normals [4], techniques to analyze points clouds in scalespace to discover salient structures [10], methods to compute multiscale principal curvatures [11] and methods to compute surface variation using a plane instead of a sphere for the fitting [12].
The goal of this module is to provide lightweight, fast and generic algorithms for 3d point cloud processing. We mostly focus on local regression techniques, which are core components of surface reconstruction techniques [2] [6], geometric descriptors [10] [8] or shape analysis techniques [7]. Most of these techniques share similar computation, and can be combined in several ways. For instance, NormalDerivativesCurvatureEstimator estimates curvature values by analyzing the spatial derivatives of a normal field, and can be combined with any normal estimation technique.
In order to ease the association of multiple computational components, the library is based on the Curiously Recurring Template Pattern (CRTP). In contrast with polymorphism, this method allows to combine multiple short computations without adding runtime overhead (both in terms of memory footprint and execution time). Instead, the combination of the computational components is performed and optimized when compiling the program, and thus require more memory and time for this stage.
Because of some properties of the C++ language, our classes does not inherit from a Base
interface defining the API, but rather follows concepts, as described in Fitting module: Concepts.
The fitting module provides a unified API to perform computations (e.g. fit a Primitive, compute geometrical properties such as Curvatures) over the neighborhood of a given point. The type of computation is controlled by a type (called Fit
in the example below) defined by the user by combining computational components offered in this module. Given an object of type Fit
, the client code will always looks as follows:
Once computations are done, the Fit
object provides both getters to the neighborhood properties (e.g. estimated curvature), and procedures (e.g. projection operator onto the fitted primitive):
The Spatial Partitioning module provides datastructures to collect neighborhood in point clouds.
We provide various approaches to approximate, analyze or characterize the geometric properties of local neighborhoods. In most situations, all these tools are based on the estimation of a geometric Primitive approximating the neighborhood, on top of which we provide more advanced computations. The table below summarizes the Primitives available in the library, as well as the associated fitting techniques:
Primitive  Required Input  Fitting techniques 

Barycenter  Points only  MeanPosition (nD) 
Normal Vector  Oriented points  MeanNormal (nD, codimension 1) 
Covariance Matrix  Points only  CovarianceFitBase (nD) 
Line  Points only  CovarianceLineFitImpl (nD) 
Plane  Points only  CovariancePlaneFitImpl (nD) 
Plane  Oriented points  MeanPlaneFitImpl (nD, codimension 1) 
MongePatch  Points only  MongePatch (3D) 
AlgebraicSphere  Points only  SphereFitImpl (nD) [6] 
AlgebraicSphere  Oriented points  OrientedSphereFitImpl (nD) [6] 
AlgebraicSphere  Nonoriented points  UnorientedSphereFitImpl (nD) [4] 
See section Computational objets, basket and CRTP for more details on how these primitives can be extended for more advanced computation.
In the following, we focus on a basic use of the module, and detail how to:
We also show detail all the available tools for geometrical property estimation (see Section Computational objets, basket and CRTP), with a specific focus on curvature (see Section Computing Curvatures). The last section details how to use this module on CUDA kernels (see Section Cuda).
The Fitting module defines operators that rely on no data structure and work both with CUDA and C++. These core operators implement atomic scientific contributions that are agnostic of the host application. If you want to use the Fitting module, just include its header:
The first step needed to use Ponca is to define how samples are represented inside the module. A strength of Ponca is to define all these structures at compile time to generate optimized code for fast evaluation at runtime.
The class Ponca::Concept::PointConcept defines the interface that has to be implemented to represent a sample. Observe that there is no need for data conversion: all you need to do is to indicate how to access existing data (see the example Ponca datastructure binding).
As an example, let's fit a AlgebraicSphere onto points equipped with normals using Ponca::OrientedSphereFit. To this end, we must define a structure (denoted PointPositionNormal
in the example below) containing a normal vector and its associated accessors. Depending on the fitting procedure we will use, we may need to define a MatrixType
type. This is for instance required for Computing Curvatures. This leads to the following class:
PONCA_MULTIARCH
is optional and required only for Cuda support.PointPositionNormal
needs to be specialized for any scalar type or dimension (you may also use a nontemplate class directly):
Two template classes must be specialized to configure computations.
At this point, most of the hard job has already been performed. All we have to do now is to provide an instance of the weight function, where \(t\) refers to the neighborhood size, and initiate the fit at an arbitrary position \(\mathbf{p}\).
Then neighbors are added sequentially: in this example, we traverse a simple array, and samples outside of the neighborhood are automatically ignored by the weighting function. Once all neighbors have been incorporated, the fit is performed and results stored in the specialized Basket object. STLlike iterators can be used directly for the fit by calling
Spatial structures can be used to accelerate spatial queries. Consider for instance using the KdTree class with range queries:
In these examples, fit1
, fit2
and fit3
should perform exactly the same computations, as long a the neighborhood remains the same between the three calls.
After calling finalize
or compute
, it is recommended to test the return state of the Fit
object before using it:
Some methods require multiple fitting passes, e.g. MongePatch. This is directly handled by the compute
method. If you don't use it, you need to check if eResults == NEED_ANOTHER_PASS
and repeat the addNeighbor()
/finalize()
steps. Don't forget to call startNewPass()
at each iteration.
Now that you have performed fitting, you may use its outputs in a number of ways (see Figure 2(b) for an illustration in 2D).
You may directly access generic properties of the fitted Primitive:
This generates the following output:
You may rather access properties of the fitted sphere (the 0isosurface of the fitted scalar field), as defined in AlgebraicSphere :
You will obtain:
Starting from v1.0, Ponca provides BasketDiff, a class to extend an existing Basket with differentiation tools. Given a specialized type TestPlane
that performs covariance plane fitting (using Ponca::CovariancePlaneFit), and defined as follows:
BasketDiff allows to extend this type to compute its derivatives in space and/or scale:
In addition to Primitive fitting, Ponca allows to compute geometrical properties of the input samples. This is done by aggregating multiple tool classes in the Basket, for instance to compute the Growing Least Squares descriptor [10] (see GLSParam) from multiple sphere fitting techniques:
From a technical point of view, the Basket class combines its template parameters (here Ponca::OrientedSphereFit and GLSParam) following the CRTP rules, ie. to form an object of the type GLSParam<Ponca::OrientedSphereFit<DataPoint, _WFunctor,T>>
, that aggregates the computations provided in each class of the hierarchy.
In practice, Ponca uses these mechanisms under the hood in order to combine atomic computations and minimize code duplication. For instance, Ponca::OrientedSphereFit is defined as an assembly of several computations classes:
Here, the class MeanPosition computes the mean position of the input points. It is also used in Ponca::CovariancePlaneFit:
and Ponca::MeanPlaneFit, among others.
Aggregating small computational objects allows to minimize code duplication, but also to easily combine different techniques. For instance, GLSDer can be used independently of the fitting technique, e.g. Ponca::OrientedSphereFit or Ponca::UnorientedSphereFit, as long as the fitted Primitive is an AlgebraicSphere.
In order to detect if the computational objects are correctly combined, Ponca provides a compiletime equirement/capability system: each computational objects check if the other classes of the CRTP provides the required computations. For instance, in the GLSParam class, we define the following enum:
Base
is a type defined from the CRTP and that represents the inherited classes. If Base
does not define PROVIDES_ALGEBRAIC_SPHERE
, this line generates an error when compiling the program. For instance, compiling the type
generates the following error:
The capability PROVIDES_GLS_PARAMETRIZATION
tells that GLSParam provides the GLS parameterization [10], and other components can access the related information.
PROVIDES_PRINCIPAL_CURVATURES
provides the following methods: kmin()
, kmax()
, kminDirection()
, kmaxDirection()
, kMean()
, GaussianCurvature()
, see CurvatureEstimatorBase.In order to ease tools combinations, each class declare a set of required and provided capabilities, as listed in the two following table:
Fit/Tool (used in Basket)  Requires  Provides 

MeanPosition  PROVIDES_MEAN_POSITION  
MeanNormal  PROVIDES_MEAN_NORMAL  
PrimitiveBase  PROVIDES_PRIMITIVE_BASE  
DryFit  PROVIDES_PRIMITIVE_BASE  
Plane  PROVIDES_PRIMITIVE_BASE  PROVIDES_PLANE 
Ponca::MeanPlaneFitImpl  PROVIDES_MEAN_POSITION ,PROVIDES_MEAN_NORMAL ,PROVIDES_PLANE  
CovarianceFitBase  PROVIDES_MEAN_POSITION  PROVIDES_POSITION_COVARIANCE 
Ponca::CovarianceLineFitImpl  PROVIDES_LINE ,PROVIDES_POSITION_COVARIANCE  
Ponca::CovariancePlaneFitImpl  PROVIDES_PLANE ,PROVIDES_POSITION_COVARIANCE  PROVIDES_TANGENT_PLANE_BASIS 
MongePatch  PROVIDES_TANGENT_PLANE_BASIS ,PROVIDES_PLANE  
AlgebraicSphere  PROVIDES_PRIMITIVE_BASE  PROVIDES_ALGEBRAIC_SPHERE 
Ponca::SphereFitImpl  PROVIDES_ALGEBRAIC_SPHERE  
Ponca::OrientedSphereFitImpl  PROVIDES_ALGEBRAIC_SPHERE ,PROVIDES_MEAN_NORMAL ,PROVIDES_MEAN_POSITION  
Ponca::UnorientedSphereFitImpl  PROVIDES_ALGEBRAIC_SPHERE ,PROVIDES_MEAN_POSITION  
GLSParam  PROVIDES_ALGEBRAIC_SPHERE  PROVIDES_GLS_PARAMETRIZATION 
Fit/Tool (used in BasketDiff)  Requires  Provides 

PrimitiveDer  PROVIDES_PRIMITIVE_BASE  PROVIDES_PRIMITIVE_DERIVATIVE 
CovarianceFitDer  PROVIDES_PRIMITIVE_DERIVATIVE ,PROVIDES_MEAN_POSITION_DERIVATIVE ,PROVIDES_POSITION_COVARIANCE  PROVIDES_POSITION_COVARIANCE_DERIVATIVE 
Ponca::CovariancePlaneDerImpl  PROVIDES_PLANE ,PROVIDES_POSITION_COVARIANCE_DERIVATIVE  PROVIDES_COVARIANCE_PLANE_DERIVATIVE ,PROVIDES_NORMAL_DERIVATIVE 
Ponca::OrientedSphereDerImpl  PROVIDES_ALGEBRAIC_SPHERE ,PROVIDES_MEAN_POSITION_DERIVATIVE ,PROVIDES_PRIMITIVE_DERIVATIVE  PROVIDES_ALGEBRAIC_SPHERE_DERIVATIVE ,PROVIDES_NORMAL_DERIVATIVE 
MlsSphereFitDer  PROVIDES_PRIMITIVE_DERIVATIVE ,PROVIDES_ALGEBRAIC_SPHERE_DERIVATIVE  PROVIDES_NORMAL_DERIVATIVE 
GLSDer  PROVIDES_GLS_PARAMETRIZATION ,PROVIDES_PRIMITIVE_DERIVATIVE ,PROVIDES_ALGEBRAIC_SPHERE_DERIVATIVE  PROVIDES_GLS_DERIVATIVE ,PROVIDES_GLS_GEOM_VAR 
CurvatureEstimatorBase  PROVIDES_PRINCIPAL_CURVATURES  
NormalDerivativesCurvatureEstimator  PROVIDES_NORMAL_DERIVATIVE ,PROVIDES_PRINCIPAL_CURVATURES  
NormalCovarianceCurvatureEstimator  PROVIDES_PRINCIPAL_CURVATURES  
ProjectedNormalCovarianceCurvatureEstimator  PROVIDES_PLANE 
In most cases, only one primitive is included in the Basket, and it is recommended to use the helper classes provided by Ponca for fitting, e.g. Ponca::CovariancePlaneFitImpl, Ponca::OrientedSphereFitImpl. Starting from version 1.0.0, Ponca allows to combine multiple primitives. In order to share intermediate computation results, it is recommended to explicitly define the computational arrangement, e.g.:
Ponca offers several ways to compute curvatures, some of which are reviewed and compared by Lejemble et al. in [8] and listed in the table below:
Estimator Name  Estimated quantities  Usage  Speed  Robustness 

Distance to PCA plane [5]  Mean curvature  Basket<P,W,CovariancePlaneFit> // method potential()  +++   
Surface Variation [12]  Mean curvature  Basket<P,W,CovariancePlaneFit> // method surfaceVariation()  +++   
Growing Least Squares [10]  Mean curvature  Basket<P,W,OrientedSphereFit,GLSParam> // method kappa()  ++  + + 
Point Set Surfaces (PSS) [2]  Curvature Tensor  Basket<P,W,CovariancePlaneFit,CovariancePlaneSpaceDer,NormalDerivativesCurvatureEstimator>  +++  + 
Algebraic Point Set Surfaces (APSS) [6]  Curvature Tensor  Basket<P,W,OrientedSphereFit,OrientedSphereSpaceDer,NormalDerivativesCurvatureEstimator>  ++  + + 
Algebraic Shape Operator (ASO) [8]  Curvature Tensor  Basket<P,W,OrientedSphereFit,OrientedSphereSpaceDer,MlsSphereFitDer,NormalDerivativesCurvatureEstimator>  +  + + + 
Ponca can be used directly on GPU, thanks to several mechanisms:
Eigen::Index
on both CPU and GPU if you plan to transfer memory between the computing units. That's why we recommend to set the following preprocessor variable when compiling your project: exptrelaxedconstexpr
preprocessor option for NVCC
. Example of working cmake file (see Screen Space Curvature using Cuda/C++): Check the C++/Cuda and Python/Cuda (using PyCuda) examples for more details and howto.