New in CGAL: Shape Regularization package

16 November 2021

Dmitry Anisimov°, Gennadii Sytov, Simon Giraudot°, Jean-Philippe Bauchet, Florent Lafarge

°GeometryFactory, *INRIA Sophia Antipolis

A typical reconstruction pipeline from a point set includes a *shape regularization* step. During this step, geometric shapes, which have been detected in the previous steps, such as lines and planes, are being regularized. Usually, three types of regularities among these shapes are reinforced:

Parallelism: near parallel shapes are made exactly parallel.
Orthogonality: near orthogonal shapes are made exactly orthogonal.
Collinearity: collinear shapes are made exactly collinear.

With the next CGAL release, a new package will add one more step towards a robust and component-based reconstruction pipeline.

The Shape Regularization Package

This new CGAL package enables to regularize a set of segments and open or closed contours in 2D and a set of planes in 3D such that all input objects are rotated and aligned with respect to user-specified conditions. In addition, it provides a global regularization framework that can be adjusted to user needs and for any type of geometric objects. This package can also be used in conjunction with the Shape Detection package.

Segments

Given a set of unordered 2D segments, users can reinforce the three types of regularities above among these segments. This regularization component is based on the global regularization framework. We call this framework *QP Regularization* because at its core is a *Quadratic Programming (QP)* global regularization algorithm. Segments are regularized twofold. The first two types of regularities: parallelism and orthogonality make a part of so-called *angle-based regularization* because angles are being adjusted while the third regularity: collinearity makes a part of so-called *offset-based regularization* because the distance between segments is adjusted. The offset regularization is performed after angle regularization. In the figure below, a set of 2D segments before (red) and after (green) the angle and offset regularization are depicted.

The example below illustrates how to achieve the result from this figure using shape regularization in CGAL.


#include <CGAL/Simple_cartesian.h>
#include <CGAL/Shape_regularization/regularize_segments.h>

using Kernel = CGAL::Simple_cartesian<double>;
using Point_2 = typename Kernel::Point_2;
using Segment_2 = typename Kernel::Segment_2;

int main()
{
  // Create input segments.
  std::vector<Segment_2> segments =
  {
    Segment_2(Point_2(0.2, 0.0), Point_2(1.2, 0.0)),
    Segment_2(Point_2(1.2, 0.1), Point_2(2.2, 0.1)),
    Segment_2(Point_2(2.2, 0.0), Point_2(2.0, 2.0)),
    Segment_2(Point_2(2.0, 2.0), Point_2(1.0, 2.0)),
    Segment_2(Point_2(1.0, 1.9), Point_2(0.0, 1.9)),
    Segment_2(Point_2(0.0, 2.0), Point_2(0.2, 0.0))
  };

  // Regularize all segments: both angles and offsets.
  CGAL::Shape_regularization::Segments::regularize_segments(segments);

  return EXIT_SUCCESS
}

Contours

Given a set of ordered 2D points connected by segments, which form a *contour*, closed or open, users can reinforce the three regularities above among consecutive edges of this contour. When regularizing contours, we assume that each contour has at least one principal direction that is a reference direction towards which the contour edges are rotated. Given a set of such directions either estimated or user-specified, each edge is made either parallel or orthogonal to these direction(s). In the figure below, a closed contour before (red) and after (green)regularization is depicted. The principal direction is the direction of the longest edge.

The example below shows the most straightforward entry point to the CGAL algorithm, where we regularize a simple closed contour.


#include <CGAL/Simple_cartesian.h>
#include <CGAL/Shape_regularization/regularize_contours.h>

using Kernel = CGAL::Simple_cartesian<double>;
using Point_2 = typename Kernel::Point_2;

int main()
{
  // Create input contour.
  const std::vector<Point_2> contour =
  {
    Point_2(0.00,  0.00),
    Point_2(0.50, -0.05),
    Point_2(1.00,  0.00),
    Point_2(1.05,  0.50),
    Point_2(1.00,  1.00),
    Point_2(0.00,  1.00)
  };

  // Regularize this contour.
  std::vector<Point_2> regularized;
  CGAL::Shape_regularization::Contours::regularize_closed_contour(contour, std::back_inserter(regularized));

  return EXIT_SUCCESS;
}

Planes

An old hierarchical plane regularization algorithm that has been a part of CGAL Shape Detection component is refactored and its API is improved. The algorithm enables to regularize a set of planes in 3D.

Performance

The performance of the shape regularization for segments based on the global QP regularization framework mostly depends on the used QP solver. The plot below shows how the computation time depends on the number of input segments when using the external OSQP) solver.

Time in seconds to regularize angles (solid red) and offsets (solid green) without regrouping input segments and with the groups of 10 segments for angles (dashed red) and offsets (dashed green).

The contour regularization algorithms, both closed and open, have, in practice, a near-linear time behavior with respect to the number of contour vertices as it can be seen from the plot below.

Time in seconds to regularize closed (red) and open (green) contours.

Status

The package Shape_Regularization is already integrated in CGAL's master branch on the CGAL GitHub repository, and will be officially released in the upcoming version of CGAL, CGAL 5.4, scheduled for December 2021.

Documentation of the package Shape_Regularization
CGAL master branch on GitHub

New in CGAL: Shape Regularization package