libcs

# Configuration space library

The code is available under the terms of GPLv3 licence and hosted on GitHub: http://github.com/pdobrowo/libcs

The configuration space library is a set of algorithms to compute the configuration space of a rotating body. The library contains code responsible for creation of various configuration spaces and to perform motion planning in the precomputed configuration spaces.

The library is implemented in C++ and designed in a general fashion, usually called C++ generic programming.It is supported on Windows and Linux platforms. The library uses CGAL’s linear kernel and extends it by implementing Spin_3 kernel representing $Spin(3)$ space. On top of it there is a implementation of a configuration space in $Spin(3)$ represented by Spin_configuration_space_3 class. The library supports polyhedral geometry as well as ball-only geometry and even custom geometry predicates.

The implementation is highly modular so the most of underlying algorithms can be replaced and the whole library can be parametrized by an arbitrary number type. There is a number of levels of abstraction in the libcs library. These can be organized as in schema 1.

Figure 1. Levels of abstraction in libcs library

A short description of each level of abstraction will be discussed hereafter. In each section a short code example is provided.

1. Base number type

At the maximum level of abstraction there are different number types. The library can be parametrized by any ring type. For the exact computations the type LiDIA::bigint from the LiDIA library is used. This type encapsulates integer values of arbitrary length. Internally, LiDIA::bigint type is implemented with the GMP library, as most of the similar solutions. The arbitrary length integer arithmetic provided by the GMP is known to be the fastest implementation publicly available. When inexact computations are sufficient, it is possible to use double or float types. To achieve better accuracy it is suggested to use double type, as there is no practical difference in performance for both types. It is important to note that for the exact scenes rational numbers are not used but integers. The reason is that most of numerical algorithms work faster on integer types and a rational scene can be easily converted to the integer one by scaling everything by the smallest common multiple of all coordinates. For the rotational motion planning, scaling of a scene does not change motion paths nor configuration space. During the research, guaranteed interval arithmetic was also tested as the underlying number type. In the interval arithmetic each number is an interval. An elementary operation transforms an interval to another giving the guarantee that the result belongs to a resulting interval. With this toolset, it should be theoretically possible to operate on floating-point numbers (which is fast) and having a guarantee of the results. Unfortunately, the type CGAL::Gmpfi providing such functionality did not present the expected performance thus using of this kind of number type was abandoned. A base number type is usually typedef-ed once for the whole program. This is shown in code A.1.

# include <LiDIA/bigint.h>

// kernel settings
typedef LiDIA::bigint RT; // ring type


Code A.1. Base number type definition

1. Linear space kernel

The next level of abstraction is a linear space. Since a configuration space is a linear space, points and vectors and all standard operations for them have to be introduced. It can be easily achieved by using CGAL’s CGAL::Cartesian or CGAL::Simple_cartesian kernel. Both kernels are nearly identical but the latter one is more appropriate for the debugging purposes. A kernel is a set of geometric objects together with a set of operations on these objects. CGAL’s kernel introduce many different types of objects from which the most important are CGAL::Point_3, CGAL::Vector_3 and CGAL::Triangle_3 with all associated operations. CGAL’s filtered kernel has also been tested. An object which encapsulates a given one and provides the same interface as the encapsulated is called a proxy. CGAL::Filtered kernel is a proxy kernel which aims to improve the speed of exact computations by preceding some of the elementary operations with guaranteed approximate arithmetic. Some practical results are known to show that this process actually improves the performance of computations. Unfortunately, during the tests no meaningful improvements were observed. As an example, code defining a linear kernel is shown in code A.2.

#include <LiDIA/bigint.h>
#include <CGAL/Cartesian.h>

// kernel settings
typedef LiDIA::bigint RT; // ring type
typedef CGAL::Cartesian<RT> Kernel_base; // linear kernel (base kernel)


Code A.2. Linear kernel definition

1. $Spin(3)$ space kernel

The $Spin(3)$ space is introduced with one of two kernels: CS::Spin_kernel_3 or CS::Spin_inexact_kernel_3. The first one is used for exact computations. It declares the exact, cell and raster configuration space representations. The second one is used for inexact computations and it does not introduce the exact configuration space representation. Only two latter representations are available (cell and raster). Since an implementation of spin-quadric intersection for an inexact arithmetic is not available, it is not possible to use exact spin kernel with inexact number type such as double. A spin kernel contains basic spin types such as spin-quadric, spin-QSIC, spin-QSIP and spinor. It also contains a group of predicates that can be used to describe a scene: H, S, G, TT and BB. There are also a few classes which are called meshers and are used to create a geometrical visualization of the involved objects. Lastly, there are three configuration space classes which are used to create a chosen representation of a configuration space.

An example of definition of an exact $Spin(3)$ kernel is shown in code A.3.

#include <LiDIA/bigint.h>
#include <CGAL/Cartesian.h>
#include <cs/Spin_kernel_3.h>

// kernel settings
typedef LiDIA::bigint RT; // ring type
typedef CGAL::Cartesian<RT> Kernel_base; // linear kernel (base kernel)
typedef CS::Spin_kernel_3<Kernel_base> Kernel; // Spin(3) kernel


Code A.3. Spin kernel definition

1. Base predicate and Spin(3) configuration space

Depending on what kind of scene is considered, different types of predicates are used. For a triangulated scene the CS::Predicate_tt_3 predicate is used and for a ball-only scene the CS::Predicate_bb_3 predicate is used. In the libcs library, a configuration space definition is based on a selected predicate and a selected type of representation. For example, if one is going to use triangulated exact scenes, the code A.4 is appropriate.

#include <LiDIA/bigint.h>
#include <CGAL/Cartesian.h>
#include <cs/Spin_kernel_3.h>

// kernel settings
typedef LiDIA::bigint RT;
typedef CGAL::Cartesian<RT> Kernel_base;
typedef CS::Spin_kernel_3<Kernel_base> Kernel;

// scene type
typedef Kernel::Predicate_tt_3 Predicate_tt_3;
typedef Kernel::Spin_exact_configuration_space_3<Predicate_tt_3>::Type Configuration_space_3;


Code A.4. Base predicate and configuration space definition

In this research the following three basic types of a configuration space were developed: Spin_exact_configuration_space_3, Spin_cell_configuration_space_3 and Spin_raster_configuration_space_3. These correspond to the exact algorithm, the cell algorithm and the raster algorithm respectively. Each configuration space can be defined for one of the two base predicates: CS::Predicate_tt_3 and CS::Predicate_bb_3.

These predicates correspond to the TT and the BB predicates respectively. When any of the three types of a configuration space is parametrized with any of the two base predicates, it gives a total of six different types of configuration spaces.

In order to generate a list of predicates for the configuration space, the implementation uses the CS::Predicate_list_generator class. Configured with a selected predicate it generates a list of predicates from a geometry in scene. For instance, the class CS::Predicate_list_generator<CS::Predicate_tt_3> generates CS::Predicate_tt_3 predicates from a list of CGAL::Triangle_3. This functionality is encapsulated and a configuration space provides a simple interface to create a list of predicates automatically. From the technical point of view, the developed algorithms always convert a triangle-triangle predicate TT and a ball-ball predicate BB to a set of S or H predicates. Then, these predicates are further converted to a set of G predicates. In result, only G predicates have to be considered. The process is depicted in figure 2.

Figure 2. Transformation of a scene to a list of predicates

In the CS::Predicate_list_generator class there is a mechanism embedded which is responsible for discarding superfluous predicates.

1. Configuration space representation

With the configuration space object one can access the computed representation and execute motion planning queries. When a configuration space is created one gives a number of optional parameters which alter the method of computing a configuration space. For instance, a cell configuration space is parametrized with the number of samples to generate. The following simple example A.5 creates a raster configuration space of two triangles.

#include <cs/Spin_kernel_3.h>
#include <CGAL/Cartesian.h>

// kernel settings
typedef double RT;
typedef CGAL::Cartesian<RT> Kernel_base;
typedef CS::Spin_inexact_kernel_3<Kernel_base> Kernel;

// scene type
typedef Kernel::Predicate_tt_3 Predicate_tt_3;
typedef Kernel::Spin_raster_configuration_space_3<Predicate_tt_3>::Type Configuration_space_3;

// objects
typedef Kernel::Triangle_3 Triangle_3;
typedef Kernel::Point_3 Point_3;

// representation
typedef CS::Spin_raster_graph_3<Kernel, Predicate_tt_3> Spin_raster_graph_3;

void example_simple_raster()
{
// rotating object
Triangle_3 rotating(Point_3(0, 0, 0), Point_3(0, 1, 0), Point_3(1, 0, 0));

// obstacle
Triangle_3 obstacle(Point_3(0, 0, 0.5), Point_3(0, 1, 0.5), Point_3(1, 0, 0.5));

// configuration space
Configuration_space_3 cs;
cs.create_from_scene(&rotating, &rotating + 1,
&obstacle, &obstacle + 1,
Configuration_space_3::Parameters(64));

const Spin_raster_graph_3 &raster_graph = cs.rep();

// access individual voxels in raster
const Spin_raster_graph_3::Voxel &voxel = raster_graph.voxel(0, 0, 0);
}


Code A.5. Construct a simple raster configuration space

5.1. Exact graph representation

As for the low-level access, the exact representation CS::Spin_exact_graph_3 provides a set of methods to traverse the list of spinquadric, the list of spin-QSICs and the list of spin-QSIPs. The exact configuration space also provides a group of methods allowing one to access high-level graph of intersections. It consists of a number of edges and a number of vertices, connected together by adjacency lists.

5.2. Cell graph representation

The cell representation CS::Spin_cell_graph_3 of configuration space provides an access to the list of cells. Each cell contains a list of adjacent cells and a list of samples that define a cell. A parameter indicating a number of sample to generate can be passed to the cell configuration space on creation.

5.3. Raster graph representation

In the raster algorithm a configuration space is represented by a raster graph CS::Spin_raster_graph_3. Each cell is an element of the raster grid and is called a voxel. One can access an individual voxel by giving its coordinate in the grid. A voxel contains a flag indicating whether it represents a colliding part of the configuration space, a position of the voxel in the configuration space and the set of adjacent voxels. The configuration space takes a parameter which is the size of the raster (a power of two).

1. Querying a motion path

A configuration space object contains the method find route() which can be used to find a motion path between two configurations. Because there are three different representations of a configuration space, an implementation of an abstract interface CS::Spin_configuration_space_3::Route was selected to represent a route. The interface allows one to check whether a route exists. If a route is present, the interface provides a simple parametrization $f(t): [0; 1] \longrightarrow Spin(3)$, which moves the object from the initial configuration to the terminal configuration. The following example A.6 finds a motion path in a raster configuration space.

#include <cs/Spin_kernel_3.h>
#include <CGAL/Cartesian.h>

// kernel settings
typedef double RT;
typedef CGAL::Cartesian<RT> Kernel_base;
typedef CS::Spin_inexact_kernel_3<Kernel_base> Kernel;

// scene type
typedef Kernel::Predicate_tt_3 Predicate_tt_3;
typedef Kernel::Spin_raster_configuration_space_3<Predicate_tt_3>::Type Configuration_space_3;

// objects
typedef Kernel::Triangle_3 Triangle_3;
typedef Kernel::Point_3 Point_3;

// representation
typedef CS::Spin_raster_graph_3<Kernel, Predicate_tt_3> Spin_raster_graph_3;

// path searching
typedef Configuration_space_3::Sample Sample;
typedef Configuration_space_3::Route Route;

void example_find_path()
{
// rotating object
Triangle_3 rotating(Point_3(0, 0, 0), Point_3(0, 1, 0), Point_3(1, 0, 0));

// obstacle
Triangle_3 obstacle(Point_3(0, 0, 0.5), Point_3(0, 1, 0.5), Point_3(1, 0, 0.5));

// configuration space
Configuration_space_3 cs;
cs.create_from_scene(&rotating, &rotating + 1,
&obstacle, &obstacle + 1,
Configuration_space_3::Parameters(64));

// find a path
Sample begin(0, 0, 0, 1); // s0 = 1
Sample end(1, 0, 0, 0); // s1 = e12
Route route = cs.find_route(begin, end);

// check if path was found
if (!route.is_valid())
return;

std::vector<Sample> path_nodes = route.nodes();
std::size_t number_of_path_nodes = path_nodes.size();

// calculate configurations along the path
for (int i = 0; i <= 100; ++i)
{
double t = 0.01 * i;
Sample sample = route.evaluate(t);

// sample is the rotation of the object at the moment t, where t is in [0; 1]
}
}


Code A.6. Find a motion path in a raster configuration space