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.

- 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*

- 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*

- $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*

- 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.

- 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));
// get access to configuration space representation
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).

- 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;
// read all path nodes
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*