Shape Representation

Huge set of 429,921 micro-robots defining a Toy Car.

Programmable matter can be expressed by a huge set of modular robot in which each module can communicate to its connected neighbors and work all together to achieve a common goal, more likely changing the shape of the whole robot. However, when the number of modules increases, the memory used in each module to store the target shape or the computation time to recreate this shape increases too.

For each step of a self-reconfiguration algorithm, each module needs to know if it is already in the goal map, or geometrical information that allows to know positions it must reach in order to reduce the global distance of the current configuration to the final one.

Thus programmable matter needs a vectorial method that allow a representation to be as small as possible to fit in low memory robots and adapt to the desired scale. It can be accomplished in three ways:

  • Representation without coordinates
  • Shared memory
  • Compact representation

We present here a compact representation solution based on CSG that is suitable for the programmable matter needs.

Constructive Solid Geometry for Programmable Matter (CSG4PM)

The objective of Constructive Solid Geometry for Programmable Matter (CSG4PM) is to provide the best trade-off between fidelity to the original shape, memory footprint and decoding processing time to fulfill this task.

This method is derived from simple boolean operations, as difference, union or intersection over simple objects as spheres and cylinders.

Mug CSG Tree.


Tucci, Thadeu, Benoît Piranda, and Julien Bourgeois. “Efficient Scene Encoding for Programmable Matter Self-Reconfiguration Algorithms,” 256–61. ACM Press, 2017.