Patate Lib
0.5

This 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 [3] 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 [2], techniques to analyze points clouds in scalespace to discover salient structures [4], methods to compute multiscale principal curvatures [5] and methods to compute surface variation using a plane instead of a sphere for the fitting [7]. See the table below:
Primitive  Supported Input  Fitting techniques  Analysis/Tools  Other usages 

Plane  Points  CovariancePlaneFit  Surface Variation[7]  
Algebraic Sphere  Oriented points  OrientedSphereFit [3]  GLS[4]  Ray Traced Curvature[5] 
Algebraic Sphere  Nonoriented points  UnorientedSphereFit [2] 
In the following, we focus on a basic use of the module, using 3D points equipped with oriented normals fitted by a Grenaille::AlgebraicSphere. First, one must set up data samples that interface with an external code; then run the fitting process in itself, and finally collect outputs. We also show how to compute curvatures with the very same approach, as this is a common requirement of many geometric processing algorithms.
We structured Grenaille as follow: a "core" folder defining operators that rely on no data structure and work both with CUDA and C++; and an "algorithms" folder with methods that may interface with userprovided data structures, with optimized solutions in C++, CUDA or both. The rationale behind this separation is to provide two levels of complexity: core operators implement atomic scientific contributions that are agnostic of the host application; algorithms implement stepbystep procedures that will likely rely on core operators and/or structure traversal.
In its current state, we do not have algorithms for Grenaille implemented: it's work in progress (we are open to contributions). If you want to use Grenaille, just include its main header:
Grenaille can be used directly on GPU, thanks to several mechanisms:
DEIGEN_DEFAULT_DENSE_INDEX_TYPE=int
Check the C++/Cuda and Python/Cuda (using PyCuda) examples for more details and howto.
You are now ready to read the next sections, and discover how to interface Grenaille with your datastructures, how to fit various primitives and compute geometrical and differential properties.
The first step needed to use Grenaille is to define how samples are represented inside the module. A strength of Grenaille is to define all these structures at compile time to generate optimized code for fast evaluation at runtime.
The class Grenaille::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.
As an example, let's fit a Grenaille::AlgebraicSphere onto points equipped with normals using the Grenaille::OrientedSphereFit. To this end, we must define a structure MyPoint containing a normal vector and its associated accessors. Depending on the fitting procedure we will use, we may need to define a Matrix Type. This is for instance required to compute Principal Curvatures. This leads to the following class:
To make the code more readable, we also define typedef
helpers for Scalar
and Vector
types outside of the MyPoint class:
Two template classes must be specialized to indicate how a fit will be applied.
The first step consists in identifying a weighting function: it defines how neighbor samples will contribute to the fit, as illustrated in Figure 2(a) in 2D. In this example, we choose a weight based on the Euclidean distance using Grenaille::DistWeightFunc, remapped through a bisquare kernel defined in Grenaille::SmoothWeightKernel:
The second step identifies a complete fitting procedure through the specialization of a Grenaille::Basket. In our example, we want to apply an Grenaille::OrientedSphereFit to input data points, which outputs an Grenaille::AlgebraicSphere by default. We further require such a sphere to be reparametrized using a Grenaille::GLSParam extension, which provides more intuitive parameters. This leads to the following specialization:
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 iniate the fit at an arbitrary position 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
Internally, the container is traversed and the method finalize
is called at the end:
After calling finalize
or compute
, it is better to test the return state of the fitting before using it. There are diffent states but the most important one is STABLE
.
You may also use accessors to perform the same check:
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 properties of the fitted scalarfield, as defined in Grenaille::AlgebraicSphere :
This generates the following output:
You may rather access properties of the fitted sphere (the 0isosurface of the fitted scalar field), as defined in Grenaille::AlgebraicSphere :
You will obtain:
Alternatively, you may prefer accessing parameters provided by the Grenaille::GLSParam extension:
You will obtain:
Thanks to the Grenaille::AlgebraicSphere, you may also project an arbitrary point onto the fitted sphere via:
You will then obtain:
This part presents how to compute curvature values from the various fitting procedures and extensions available in Grenaille.
A fast approximation of the mean curvature is provided by GLSParam::kappa() and illustrated at two scales on a 3D surface in Figure 3:
It can also be extracted by analysing the spatial derivatives of fitted normals, provided by GLSDer::deta(). Note that the computational cost is more important in this case.
fit.deta()
, using an implicit cast from VectorArray
to MatrixType
. It will require a more careful conversion when the basket contains different extensions. More details here.Principal curvatures and their associated directions can be computed by an eigen decomposition of the spatial derivatives of eta, provided by the extension GLSCurvatureHelper (based on the analysis of GLSDer::deta()):
This page was intended to show you a standard use of the Grenaille module. However, there is more to it than Grenaille::OrientedSphereFit, as shown in its reference. For example, you can create a totally different Basket with a Grenaille::CompactPlane and its extension Grenaille::CovariancePlaneFit using plane instead of algebraic sphere to procede the fit in order to compute Grenaille::CovariancePlaneFit::surfaceVariation. We encourage you to make your own tests and have a look at our examples. It will give you ideas about how to use this module inside your own applications.