Fitting trimmed B-splines to unordered point clouds

This tutorial explains how to run a B-spline fitting algorithm on a point-cloud, to obtain a smooth, parametric surface representation. The algorithm consists of the following steps:

  • Initialization of the B-spline surface by using the Principal Component Analysis (PCA). This assumes that the point-cloud has two main orientations, i.e. that it is roughly planar.

  • Refinement and fitting of the B-spline surface.

  • Circular initialization of the B-spline curve. Here we assume that the point-cloud is compact, i.e. no separated clusters.

  • Fitting of the B-spline curve.

  • Triangulation of the trimmed B-spline surface.

In this video, the algorithm is applied to the frontal scan of the stanford bunny (204800 points):

Theoretical background

Theoretical information on the algorithm can be found in this report and in my PhD thesis.

PCL installation settings

Please note that the modules for NURBS and B-splines are not enabled by default. Make sure you enable “BUILD_surface_on_nurbs” in your ccmake configuration, by setting it to ON.

If your license permits, also enable “USE_UMFPACK” for sparse linear solving. This requires SuiteSparse (libsuitesparse-dev in Ubuntu) which is faster, allows more degrees of freedom (i.e. control points) and more data points.

The program created during this tutorial is available in pcl/examples/surface/example_nurbs_fitting_surface.cpp and is built when “BUILD_examples” is set to ON. This will create the binary called pcl_example_nurbs_fitting_surface in your bin folder.

The code

The cpp file used in this tutorial can be found in pcl/doc/tutorials/content/sources/bspline_fitting/bspline_fitting.cpp. You can find the input file at pcl/test/bunny.pcd.

  1#include <pcl/point_cloud.h>
  2#include <pcl/point_types.h>
  3#include <pcl/io/pcd_io.h>
  4
  5#include <pcl/visualization/pcl_visualizer.h>
  6#include <pcl/surface/on_nurbs/fitting_surface_tdm.h>
  7#include <pcl/surface/on_nurbs/fitting_curve_2d_asdm.h>
  8#include <pcl/surface/on_nurbs/triangulation.h>
  9
 10typedef pcl::PointXYZ Point;
 11
 12void
 13PointCloud2Vector3d (pcl::PointCloud<Point>::Ptr cloud, pcl::on_nurbs::vector_vec3d &data);
 14
 15void
 16visualizeCurve (ON_NurbsCurve &curve,
 17                ON_NurbsSurface &surface,
 18                pcl::visualization::PCLVisualizer &viewer);
 19
 20int
 21main (int argc, char *argv[])
 22{
 23  std::string pcd_file, file_3dm;
 24
 25  if (argc < 3)
 26  {
 27    printf ("\nUsage: pcl_example_nurbs_fitting_surface pcd<PointXYZ>-in-file 3dm-out-file\n\n");
 28    exit (EXIT_FAILURE);
 29  }
 30  pcd_file = argv[1];
 31  file_3dm = argv[2];
 32
 33  pcl::visualization::PCLVisualizer viewer ("B-spline surface fitting");
 34  viewer.setSize (800, 600);
 35
 36  // ############################################################################
 37  // load point cloud
 38
 39  printf ("  loading %s\n", pcd_file.c_str ());
 40  pcl::PointCloud<Point>::Ptr cloud (new pcl::PointCloud<Point>);
 41  pcl::PCLPointCloud2 cloud2;
 42  pcl::on_nurbs::NurbsDataSurface data;
 43
 44  if (pcl::io::loadPCDFile (pcd_file, cloud2) == -1)
 45    throw std::runtime_error ("  PCD file not found.");
 46
 47  fromPCLPointCloud2 (cloud2, *cloud);
 48  PointCloud2Vector3d (cloud, data.interior);
 49  pcl::visualization::PointCloudColorHandlerCustom<Point> handler (cloud, 0, 255, 0);
 50  viewer.addPointCloud<Point> (cloud, handler, "cloud_cylinder");
 51  printf ("  %lu points in data set\n", cloud->size ());
 52
 53  // ############################################################################
 54  // fit B-spline surface
 55
 56  // parameters
 57  unsigned order (3);
 58  unsigned refinement (5);
 59  unsigned iterations (10);
 60  unsigned mesh_resolution (256);
 61
 62  pcl::on_nurbs::FittingSurface::Parameter params;
 63  params.interior_smoothness = 0.2;
 64  params.interior_weight = 1.0;
 65  params.boundary_smoothness = 0.2;
 66  params.boundary_weight = 0.0;
 67
 68  // initialize
 69  printf ("  surface fitting ...\n");
 70  ON_NurbsSurface nurbs = pcl::on_nurbs::FittingSurface::initNurbsPCABoundingBox (order, &data);
 71  pcl::on_nurbs::FittingSurface fit (&data, nurbs);
 72  //  fit.setQuiet (false); // enable/disable debug output
 73
 74  // mesh for visualization
 75  pcl::PolygonMesh mesh;
 76  pcl::PointCloud<pcl::PointXYZ>::Ptr mesh_cloud (new pcl::PointCloud<pcl::PointXYZ>);
 77  std::vector<pcl::Vertices> mesh_vertices;
 78  std::string mesh_id = "mesh_nurbs";
 79  pcl::on_nurbs::Triangulation::convertSurface2PolygonMesh (fit.m_nurbs, mesh, mesh_resolution);
 80  viewer.addPolygonMesh (mesh, mesh_id);
 81
 82  // surface refinement
 83  for (unsigned i = 0; i < refinement; i++)
 84  {
 85    fit.refine (0);
 86    fit.refine (1);
 87    fit.assemble (params);
 88    fit.solve ();
 89    pcl::on_nurbs::Triangulation::convertSurface2Vertices (fit.m_nurbs, mesh_cloud, mesh_vertices, mesh_resolution);
 90    viewer.updatePolygonMesh<pcl::PointXYZ> (mesh_cloud, mesh_vertices, mesh_id);
 91    viewer.spinOnce ();
 92  }
 93
 94  // surface fitting with final refinement level
 95  for (unsigned i = 0; i < iterations; i++)
 96  {
 97    fit.assemble (params);
 98    fit.solve ();
 99    pcl::on_nurbs::Triangulation::convertSurface2Vertices (fit.m_nurbs, mesh_cloud, mesh_vertices, mesh_resolution);
100    viewer.updatePolygonMesh<pcl::PointXYZ> (mesh_cloud, mesh_vertices, mesh_id);
101    viewer.spinOnce ();
102  }
103
104  // ############################################################################
105  // fit B-spline curve
106
107  // parameters
108  pcl::on_nurbs::FittingCurve2dAPDM::FitParameter curve_params;
109  curve_params.addCPsAccuracy = 5e-2;
110  curve_params.addCPsIteration = 3;
111  curve_params.maxCPs = 200;
112  curve_params.accuracy = 1e-3;
113  curve_params.iterations = 100;
114
115  curve_params.param.closest_point_resolution = 0;
116  curve_params.param.closest_point_weight = 1.0;
117  curve_params.param.closest_point_sigma2 = 0.1;
118  curve_params.param.interior_sigma2 = 0.00001;
119  curve_params.param.smooth_concavity = 1.0;
120  curve_params.param.smoothness = 1.0;
121
122  // initialisation (circular)
123  printf ("  curve fitting ...\n");
124  pcl::on_nurbs::NurbsDataCurve2d curve_data;
125  curve_data.interior = data.interior_param;
126  curve_data.interior_weight_function.push_back (true);
127  ON_NurbsCurve curve_nurbs = pcl::on_nurbs::FittingCurve2dAPDM::initNurbsCurve2D (order, curve_data.interior);
128
129  // curve fitting
130  pcl::on_nurbs::FittingCurve2dASDM curve_fit (&curve_data, curve_nurbs);
131  // curve_fit.setQuiet (false); // enable/disable debug output
132  curve_fit.fitting (curve_params);
133  visualizeCurve (curve_fit.m_nurbs, fit.m_nurbs, viewer);
134
135  // ############################################################################
136  // triangulation of trimmed surface
137
138  printf ("  triangulate trimmed surface ...\n");
139  viewer.removePolygonMesh (mesh_id);
140  pcl::on_nurbs::Triangulation::convertTrimmedSurface2PolygonMesh (fit.m_nurbs, curve_fit.m_nurbs, mesh,
141                                                                   mesh_resolution);
142  viewer.addPolygonMesh (mesh, mesh_id);
143
144
145  // save trimmed B-spline surface
146  if ( fit.m_nurbs.IsValid() )
147  {
148    ONX_Model model;
149    ONX_Model_Object& surf = model.m_object_table.AppendNew();
150    surf.m_object = new ON_NurbsSurface(fit.m_nurbs);
151    surf.m_bDeleteObject = true;
152    surf.m_attributes.m_layer_index = 1;
153    surf.m_attributes.m_name = "surface";
154
155    ONX_Model_Object& curv = model.m_object_table.AppendNew();
156    curv.m_object = new ON_NurbsCurve(curve_fit.m_nurbs);
157    curv.m_bDeleteObject = true;
158    curv.m_attributes.m_layer_index = 2;
159    curv.m_attributes.m_name = "trimming curve";
160
161    model.Write(file_3dm.c_str());
162    printf("  model saved: %s\n", file_3dm.c_str());
163  }
164
165  printf ("  ... done.\n");
166
167  viewer.spin ();
168  return 0;
169}
170
171void
172PointCloud2Vector3d (pcl::PointCloud<Point>::Ptr cloud, pcl::on_nurbs::vector_vec3d &data)
173{
174  for (unsigned i = 0; i < cloud->size (); i++)
175  {
176    Point &p = cloud->at (i);
177    if (!std::isnan (p.x) && !std::isnan (p.y) && !std::isnan (p.z))
178      data.push_back (Eigen::Vector3d (p.x, p.y, p.z));
179  }
180}
181
182void
183visualizeCurve (ON_NurbsCurve &curve, ON_NurbsSurface &surface, pcl::visualization::PCLVisualizer &viewer)
184{
185  pcl::PointCloud<pcl::PointXYZRGB>::Ptr curve_cloud (new pcl::PointCloud<pcl::PointXYZRGB>);
186
187  pcl::on_nurbs::Triangulation::convertCurve2PointCloud (curve, surface, curve_cloud, 4);
188  for (std::size_t i = 0; i < curve_cloud->size () - 1; i++)
189  {
190    pcl::PointXYZRGB &p1 = curve_cloud->at (i);
191    pcl::PointXYZRGB &p2 = curve_cloud->at (i + 1);
192    std::ostringstream os;
193    os << "line" << i;
194    viewer.removeShape (os.str ());
195    viewer.addLine<pcl::PointXYZRGB> (p1, p2, 1.0, 0.0, 0.0, os.str ());
196  }
197
198  pcl::PointCloud<pcl::PointXYZRGB>::Ptr curve_cps (new pcl::PointCloud<pcl::PointXYZRGB>);
199  for (int i = 0; i < curve.CVCount (); i++)
200  {
201    ON_3dPoint p1;
202    curve.GetCV (i, p1);
203
204    double pnt[3];
205    surface.Evaluate (p1.x, p1.y, 0, 3, pnt);
206    pcl::PointXYZRGB p2;
207    p2.x = float (pnt[0]);
208    p2.y = float (pnt[1]);
209    p2.z = float (pnt[2]);
210
211    p2.r = 255;
212    p2.g = 0;
213    p2.b = 0;
214
215    curve_cps->push_back (p2);
216  }
217  viewer.removePointCloud ("cloud_cps");
218  viewer.addPointCloud (curve_cps, "cloud_cps");
219}

The explanation

Now, let’s break down the code piece by piece. Lets start with the choice of the parameters for B-spline surface fitting:

 1  // parameters
 2  unsigned order (3);
 3  unsigned refinement (5);
 4  unsigned iterations (10);
 5  unsigned mesh_resolution (256);
 6
 7  pcl::on_nurbs::FittingSurface::Parameter params;
 8  params.interior_smoothness = 0.2;
 9  params.interior_weight = 1.0;
10  params.boundary_smoothness = 0.2;
11  params.boundary_weight = 0.0;

  • order is the polynomial order of the B-spline surface.

  • refinement is the number of refinement iterations, where for each iteration control-points are inserted, approximately doubling the control points in each parametric direction of the B-spline surface.

  • iterations is the number of iterations that are performed after refinement is completed.

  • mesh_resolution the number of vertices in each parametric direction, used for triangulation of the B-spline surface.

Fitting:

  • interior_smoothness is the smoothness of the surface interior.

  • interior_weight is the weight for optimization for the surface interior.

  • boundary_smoothness is the smoothness of the surface boundary.

  • boundary_weight is the weight for optimization for the surface boundary.

Note, that the boundary in this case is not the trimming curve used later on. The boundary can be used when a point-set exists that defines the boundary. Those points can be declared in pcl::on_nurbs::NurbsDataSurface::boundary. In that case, when the boundary_weight is greater than 0.0, the algorithm tries to align the domain boundaries to these points. In our example we are trimming the surface anyway, so there is no need for aligning the boundary.

Initialization of the B-spline surface

  // initialize
  printf ("  surface fitting ...\n");
  ON_NurbsSurface nurbs = pcl::on_nurbs::FittingSurface::initNurbsPCABoundingBox (order, &data);
  pcl::on_nurbs::FittingSurface fit (&data, nurbs);
  //  fit.setQuiet (false); // enable/disable debug output

The command initNurbsPCABoundingBox uses PCA to create a coordinate systems, where the principal eigenvectors point into the direction of the maximum, middle and minimum extension of the point-cloud. The center of the coordinate system is located at the mean of the points. To estimate the extension of the B-spline surface domain, a bounding box is computed in the plane formed by the maximum and middle eigenvectors. That bounding box is used to initialize the B-spline surface with its minimum number of control points, according to the polynomial degree chosen.

The surface fitting class pcl::on_nurbs::FittingSurface is initialized with the point data and the initial B-spline.

  // mesh for visualization
  pcl::PolygonMesh mesh;
  pcl::PointCloud<pcl::PointXYZ>::Ptr mesh_cloud (new pcl::PointCloud<pcl::PointXYZ>);
  std::vector<pcl::Vertices> mesh_vertices;
  std::string mesh_id = "mesh_nurbs";
  pcl::on_nurbs::Triangulation::convertSurface2PolygonMesh (fit.m_nurbs, mesh, mesh_resolution);
  viewer.addPolygonMesh (mesh, mesh_id);

The on_nurbs::Triangulation class allows easy conversion between the ON_NurbsSurface and the PolygonMesh class, for visualization of the B-spline surfaces. Note that NURBS are a generalization of B-splines, and are therefore a valid container for B-splines, with all control-point weights = 1.

  // surface refinement
  for (unsigned i = 0; i < refinement; i++)
  {
    fit.refine (0);
    fit.refine (1);
    fit.assemble (params);
    fit.solve ();
    pcl::on_nurbs::Triangulation::convertSurface2Vertices (fit.m_nurbs, mesh_cloud, mesh_vertices, mesh_resolution);
    viewer.updatePolygonMesh<pcl::PointXYZ> (mesh_cloud, mesh_vertices, mesh_id);
    viewer.spinOnce ();
  }

Refinement and fitting of the B-spline surface

At this point of the code we have a B-spline surface with minimal number of control points. Typically they are not enough to represent finer details of the underlying geometry of the point-cloud. However, if we increase the control-points to our desired level of detail and subsequently fit the refined B-spline, we run into problems. For robust fitting B-spline surfaces the rule is: “The higher the degree of freedom of the B-spline surface, the closer we have to be to the points to be approximated”.

This is the reason why we iteratively increase the degree of freedom by refinement in both directions (line 85-86), and fit the B-spline surface to the point-cloud, getting closer to the final solution.

  // surface fitting with final refinement level
  for (unsigned i = 0; i < iterations; i++)
  {
    fit.assemble (params);
    fit.solve ();
    pcl::on_nurbs::Triangulation::convertSurface2Vertices (fit.m_nurbs, mesh_cloud, mesh_vertices, mesh_resolution);
    viewer.updatePolygonMesh<pcl::PointXYZ> (mesh_cloud, mesh_vertices, mesh_id);
    viewer.spinOnce ();
  }

After we reached the final level of refinement, the surface is further fitted to the point-cloud for a pleasing end result.

Initialization of the B-spline curve

Now that we have the surface fitted to the point-cloud, we want to cut off the overlapping regions of the surface. To achieve this we project the point-cloud into the parametric domain using the closest points to the B-spline surface. In this domain of R^2 we perform the weighted B-spline curve fitting, that creates a closed trimming curve that approximately contains all the points.

  // parameters
  pcl::on_nurbs::FittingCurve2dAPDM::FitParameter curve_params;
  curve_params.addCPsAccuracy = 5e-2;
  curve_params.addCPsIteration = 3;
  curve_params.maxCPs = 200;
  curve_params.accuracy = 1e-3;
  curve_params.iterations = 100;

  curve_params.param.closest_point_resolution = 0;
  curve_params.param.closest_point_weight = 1.0;
  curve_params.param.closest_point_sigma2 = 0.1;
  curve_params.param.interior_sigma2 = 0.00001;
  curve_params.param.smooth_concavity = 1.0;
  curve_params.param.smoothness = 1.0;

The topic of curve fitting goes a bit deeper into the thematics of B-splines. Here we assume that you are familiar with the concept of B-splines, knot vectors, control-points, and so forth. Please consider the curve being split into supporting regions which is bound by consecutive knots. Also note that points that are inside and outside the curve are distinguished.

  • addCPsAccuracy the distance of the supporting region of the curve to the closest data points has to be below this value, otherwise a control point is inserted.

  • addCPsIteration inner iterations without inserting control points.

  • maxCPs the maximum total number of control-points.

  • accuracy the average fitting accuracy of the curve, w.r.t. the supporting regions.

  • iterations maximum number of iterations performed.

  • closest_point_resolution number of control points that must lie within each supporting region. (0 turns this constraint off)

  • closest_point_weight weight for fitting the curve to its closest points.

  • closest_point_sigma2 threshold for closest points (disregard points that are further away from the curve).

  • interior_sigma2 threshold for interior points (disregard points that are further away from and lie within the curve).

  • smooth_concavity value that leads to inward bending of the curve (0 = no bending; <0 inward bending; >0 outward bending).

  • smoothness weight of smoothness term.

  // initialisation (circular)
  printf ("  curve fitting ...\n");
  pcl::on_nurbs::NurbsDataCurve2d curve_data;
  curve_data.interior = data.interior_param;
  curve_data.interior_weight_function.push_back (true);
  ON_NurbsCurve curve_nurbs = pcl::on_nurbs::FittingCurve2dAPDM::initNurbsCurve2D (order, curve_data.interior);

The curve is initialized using a minimum number of control points to represent a circle, with the center located at the mean of the point-cloud and the radius of the maximum distance of a point to the center. Please note that interior weighting is enabled for all points with the command curve_data.interior_weight_function.push_back (true).

Fitting of the B-spline curve

  // curve fitting
  pcl::on_nurbs::FittingCurve2dASDM curve_fit (&curve_data, curve_nurbs);
  // curve_fit.setQuiet (false); // enable/disable debug output
  curve_fit.fitting (curve_params);
  visualizeCurve (curve_fit.m_nurbs, fit.m_nurbs, viewer);

Similar to the surface fitting approach, the curve is iteratively fitted and refined, as shown in the video. Note how the curve tends to bend inwards at regions where it is not supported by any points.

Triangulation of the trimmed B-spline surface

  // triangulation of trimmed surface

  printf ("  triangulate trimmed surface ...\n");
  viewer.removePolygonMesh (mesh_id);
  pcl::on_nurbs::Triangulation::convertTrimmedSurface2PolygonMesh (fit.m_nurbs, curve_fit.m_nurbs, mesh,
                                                                   mesh_resolution);
  viewer.addPolygonMesh (mesh, mesh_id);

After the curve fitting terminated, our geometric representation consists of a B-spline surface and a closed B-spline curved, defined within the parametric domain of the B-spline surface. This is called trimmed B-spline surface. In line 140 we can use the trimmed B-spline to create a triangular mesh. The triangulation algorithm first triangulates the whole domain and afterwards removes triangles that lie outside of the trimming curve. Vertices of triangles that intersect the trimming curve are clamped to the curve.

When running this example and switch to wire-frame mode (w), you will notice that the triangles are ordered in a rectangular way, which is a result of the rectangular domain of the surface.

Some hints

Please bear in mind that the robustness of this algorithm heavily depends on the underlying data. The parameters for B-spline fitting are designed to model the characteristics of this data.

  • If you have holes or steps in your data, you might want to work with lower refinement levels and lower accuracy to prevent the B-spline from folding and twisting. Moderately increasing of the smoothness might also work.

  • Try to introduce as much pre-conditioning and constraints to the parameters. E.g. if you know, that the trimming curve is rather simple, then limit the number of maximum control points.

  • Start simple! Before giving up on gaining control over twisting and bending B-splines, I highly recommend to start your fitting trials with a small number of control points (low refinement), low accuracy but also low smoothness (B-splines have implicit smoothing property).

Compiling and running the program

Add the following lines to your CMakeLists.txt file:

 1cmake_minimum_required(VERSION 3.5 FATAL_ERROR)
 2
 3project(bspline_fitting)
 4
 5find_package(PCL 1.7 REQUIRED)
 6
 7include_directories(${PCL_INCLUDE_DIRS})
 8link_directories(${PCL_LIBRARY_DIRS})
 9add_definitions(${PCL_DEFINITIONS})
10
11add_executable (bspline_fitting bspline_fitting.cpp)
12target_link_libraries (bspline_fitting ${PCL_LIBRARIES})

After you have made the executable, you can run it. Simply do:

$ ./bspline_fitting ${PCL_ROOT}/test/bunny.pcd

Saving and viewing the result

  • Saving as OpenNURBS (3dm) file

You can save the B-spline surface by using the commands provided by OpenNurbs:

  // save trimmed B-spline surface
  if ( fit.m_nurbs.IsValid() )
  {
    ONX_Model model;
    ONX_Model_Object& surf = model.m_object_table.AppendNew();
    surf.m_object = new ON_NurbsSurface(fit.m_nurbs);
    surf.m_bDeleteObject = true;
    surf.m_attributes.m_layer_index = 1;
    surf.m_attributes.m_name = "surface";

    ONX_Model_Object& curv = model.m_object_table.AppendNew();
    curv.m_object = new ON_NurbsCurve(curve_fit.m_nurbs);
    curv.m_bDeleteObject = true;
    curv.m_attributes.m_layer_index = 2;
    curv.m_attributes.m_name = "trimming curve";

    model.Write(file_3dm.c_str());
    printf("  model saved: %s\n", file_3dm.c_str());
  }

The files generated can be viewed with the pcl/examples/surface/example_nurbs_viewer_surface.cpp.

  • Saving as triangle mesh into a vtk file

You can save the triangle mesh for example by saving into a VTK file by:

#include <pcl/io/vtk_io.h> … pcl::io::saveVTKFile (“mesh.vtk”, mesh);

PCL also provides vtk conversion into other formats (PLY, OBJ).