Topological representation of cloth state for robot manipulation

Abstract

Forty years ago the notion of configuration space (C-space) revolutionised robot motion planning for rigid and articulated objects. Despite great progress, handling deformable materials has remained elusive because of their infinite-dimensional shape-state space. Finding low-complexity representations has become a pressing research goal. This work tries to make a tiny step in this direction by proposing a state representation for textiles relying on the C-space of some distinctive points. A stratification of the configuration space for n points in the cloth is derived from that of the flag manifold, and topological techniques to determine adjacencies in manipulation-centred state graphs are developed. Their algorithmic implementation permits obtaining cloth state–space representations of different granularities and tailored to particular purposes. An example of their usage to distinguish between cloth states having different manipulation affordances is provided. Suggestions on how the proposed state graphs can serve as a common ground to link the perception, planning and manipulation of textiles are also made.

1 Introduction

Robot manipulation in human environments is an important research field that in recent years has experienced tremendous progress. Impressive results have been obtained among the many open problems pinpointed a decade ago (Kemp et al. 2007), such as humanoid whole-body reaching, mobile manipulation and human–robot collaboration. Research has focused on core capabilities as grasping everyday objects, carrying and placing them, as well as robot hand-over to or by a person. An important limitation is that the target objects have been —almost exclusively— rigid ones.

Indeed, non-rigid objects —textile items in particular— pose many additional challenges with respect to rigid object manipulation, such as difficult perception, complexity in modelling the object and predicting its behaviour, and the many uncertainties hindering motion planning to reach a desired outcome. Despite these difficulties, the manipulation of clothing items is nowadays gaining attention in the robotics community due to the rise of assistive and service robotics (Torras 2016). As clothing items pervade human environments, automating their versatile manipulation would have a large impact on society, in sectors ranging from healthcare to clothing industry. The key problem underlying all these difficulties is that, whereas handling a rigid object only changes its pose, namely 6 parameters (the configuration space is the well-known ${\mathbb {R}^3\times SO(3)}$), the manipulation of a textile object takes place in a shape-state space which is potentially infinite-dimensional. This huge dimensionality jump prevents the extension of the techniques developed for rigid objects (for perception, planning, learning and manipulation) to textile ones, and calls for a radically different approach.

2 Related work

The extension of available techniques consists of modelling cloth as a finite element mesh and applying both physics simulation and motion planning algorithms for closed-loop multi-articulated objects. This is appropriate for rendering where realistic appearance is sought, and impressive advances have taken place recently in the computer vision and computer graphics communities (Pumarola et al. 2018; Bai et al. 2016), but robot manipulation has not benefited so far from them, because of its substantially different final aims. In the graphics context, the goal can be among others to render the dressing of a human body, representing with accuracy the clothing as offsets from the body (Ma et al. 2019; Guan et al. 2012; Pons-Moll et al. 2017), as well as to estimate with precision the clothing pose based on generative models for 3D shapes using topology (Hilaga et al. 2001).

For these approaches, rendering precision is important, while for robot manipulation, local details such as wrinkles and accurate position can be overlooked in favour of properly determining the macro-state the cloth is in. By macro-state we mean a set of cloth configurations that can be manipulated in the same way, i.e., that have similar grasping affordances.

In the robot manipulation community there is a long-standing general agreement that “low complexity representations for the deformable objects should be the objective” (Smith et al. 2012) and some attempts to use topological constructs to this end have been made, using writhe matrices, winding numbers and Laplacian coordinates for topology-based representations (Ivan et al. 2013; Yuan et al. 2019), as well as loops detection (Pokorny et al. 2013) and topology coordinates for representing human pose as captured by a motion capture system (Koganti et al. 2017), but also in combination with deep learning approaches (Yan et al. 2020).

Further along this line, we propose to characterise cloth macro-states, called just ’states’ in what follows, using combinatorial topology techniques. Inspired by previous works on the topological representation of robot configuration spaces (Canny 1988; Torras et al. 2006), we consider a set of significant points in the cloth and rely on the process of stratification to decompose the configuration space (C-space) of such points into manipulation-wise meaningful states, as well as to derive their adjacencies.

The outcome is a succinct manipulation-oriented cloth state representation in the form of a graph that permits encoding actions as probabilistic state transitions and then applying the powerful probabilistic task planning machinery developed within the AI community (Geißer et al. 2019; Canal et al. 2019). Another potential advantage is the simplification of perception, since states can be recognised without accurately recovering the cloth configuration, and only local features relevant for grasping need to be located.

The paper is structured as follows. In Sect. 3 we use the notion of stratification to study the topological space of configurations of points, focussing first on the case of 4 points. We investigate how such stratification can be obtained using the algebraic condition given by the alignment of three points. This allows us to assign to each configuration of n points a concise “label” and ensure that those with different label are effectively separated by the stratification in different strata. We also provide an explicit algorithm to construct such stratification for the case $n<7$. We proceed then, in Sect. 4, to investigate the complexity of the stratification and how to simplify it. This can be efficiently done using its topological properties and the action of the symmetric group $S_n$, defining the state of a configuration of points as a collection of one or more strata. Thanks to such states, we can investigate how the points of a mesh are distributed with respect to some fixed ones (for example the corner ones in a rectangular textile) and compare different mesh poses based on the state-distribution of their points.

3 Configuration space of a textile rectangle using n points

Given a rectangular cloth on a planar surface, we could consider it as a surface embedded in $\mathbb {R}^3$ with no self-intersection. Unfortunately, considering the different configurations of such surface and studying their space bears difficulties. On the already complex space of all possible surfaces with same area and no self-intersections, we need to impose also constraints such as gravity force and cloth stiffness. In order to simplify, we consider instead the cloth as a set of n points on the real plane $\mathbb {R}^2$ and the space of all possible configurations of them, $Conf_n(\mathbb {R}^2)$. This space belongs to the far more general family of configuration spaces of points on manifolds,

$$\begin{aligned} Conf_n(X) = \left\{ \left( p_1,\dots , p_n\right) \in X^n | p_i\ne p_j~\text {for}~i\ne j\right\} . \end{aligned}$$

Such spaces are interesting topological objects and both their homotopy type and homological properties have been studied by several authors. In Arnold (1969) some results regarding the homotopy type of $Conf_n(X)$ are obtained, assuming X is of dimension 2, while the real homotopy type of $Conf_n(X)$, when X is a smooth projective variety, was independently computed by Kriz (1994) and Totaro (1996). In Cohen et al. (1976) under the assumption $X=\mathbb {R}^n$, the homology of $Conf_n(X)$ is computed and, in particular, it is proved that $Conf_n(\mathbb {R}^n)$ is the classifying space of the n-strand pure braid group.

Since our aim is to distinguish states based on the types of robot manipulations they permit, we will investigate how such space can be subdivided into meaningful regions, each one formed by several configurations of n points. The procedure introduced here allows us to assign to any configuration of points a binary vector, whose length depends on the number of points considered. In this way we can group together configurations with the same vector representation and in addition we will be able to plan which regions of C-space we need to “visit” if we want to move from one state to another.

To obtain such structure for $Conf_n(\mathbb {R}^2)$ we will employ the notion of stratification of a topological space. The idea behind such notion is to decompose topological spaces of dimension m into smooth parts of dimension m, such that the boundary between any two of them is a subspace of dimension $m-1$. As we can iterate such process at each dimension $0\le k\le m$, the stratification assumes the form of a filtration, $\emptyset \subseteq X_1\subseteq X_2\subseteq \dots \subseteq X_m = Conf_n(\mathbb {R}^2)$, where each $X_i$ is the union of disconnected smooth parts, called strata of dimension i and the boundary, called singularity of dimension $i-1$, between two strata belongs to $X_{i-1}$. The structure of a stratification can be quite complex, however for simple cases one can visualise it clearly. Consider 4 points in the plane, as in Fig. 1, such that $p_1$ and $p_2$ are fixed and $\left|\left|p_4-p_1\right|\right| \le d$.

Fig. 1

The points $p_1$ and $p_2$ are fixed, while $p_4$ has to be inside the grey circle, of radius d (Color figure online)

Their C-space is a solid torus, product of a disk, encoding the position of $p_4$, and a circle, encoding the angle of $\overline{p_1~p_2}$ and $\overline{p_3~p_4}$, and it is clearly contained in $Conf_4(\mathbb {R}^2)$. Its stratification can be seen in Fig. 2 , where we use alignment between points to define singularities.

Fig. 2

On the top we can see four disconnected 3D strata of the C-space, obtained by cutting the torus with the 2D singularities. These are two disks (in purple on the bottom), which correspond to $p_3\in \overline{p_1~p_2}$, and one annullus (in light green on the bottom), corresponding to $p_4\in \overline{p_1~p_2}$. On the bottom picture we show also the 1D singularities (in black) and two 0D singularities (in yellow). The former correspond to $p_1 = p_4$ (a circle) and $\overline{p_3~p_4} = \overline{p_1~p_2}$ (two segments). The latter correponds to the case when both $p_4 = p_1$ and $\overline{p_3~p_4} = \overline{p_1~p_2}$ (Color figure online)

Our first step towards the construction of a stratification for $Conf_n(\mathbb {R}^2)$ is to investigate the simplest non-trivial case of $n=4$, which will prove to be essential in the treatment of the general case. For both this case and the general one the main idea consist in identify as singularity a subspace of $Conf_n(\mathbb {R}^2)$, where three points are aligned, so that, in the highest dimensional strata no triple of point can be aligned. We will show that such alignment is defined by an algebraic condition (a null determinant) and it provides us with a concise way to encode the different strata (as vectors of signs of determinants). This property allows us to determine easily the corresponding stratum (or singularity) of any point configuration. We also introduce a constructive way, Algorithm 1, to build such stratification when $n<7$ in a finite number of steps.

3.1 C-space of a textile rectangle using 4 points

For the case $n=4$ we will rely on the stratification of the flag manifold of $\mathbb {R}\mathbb {P}^2$, . The elements of  are the sets $\{v, l\}$ with v a point and l a line in $\mathbb {R}\mathbb {P}^2$ such that $v\in l$. If we fix a flag $\{v^*, l^*\}$, call it reference flag, we are able to construct a stratification of  that encodes the possible pose of any flag with respect to the reference one. The strata corresponding to such stratification are Bruhat cells, as shown in Hiller (1982); Monk (1959). The resulting stratification can be seen in Fig. 3, we refer the reader to Milnor and Stasheff (1975) for a more detailed description.

Fig. 3

Stratification of  into Bruhat cells, where a link indicates that one is in the boundary of the other. The label of each stratum describes if and how any of its flags V intersects with $V^*$, e.g. for any flag in $v-l^*$ it is true that $v\cap l^*\ne \emptyset$

Consider the points $p_1$, $p_2$, $p_3$ and $p_4$ in $\mathbb {R}^2$ as points in the projective plane, by adding 1 as last projective coordinate. We define $V^*= \{p_1, \overline{p_1 p_2}\}$ as reference flag and consider the flag $V = \{p_3, \overline{p_3 p_4}\}$. Note that, in an abuse of language, we are denoting $p_i$ both the point in $\mathbb {R}\mathbb {P}^2$ and the one in $\mathbb {R}^2$. Each stratum in Fig. 3 of dimension at most 2 corresponds to some point alignment. For example if V is in the stratum $v-l^*$ then $\{p_1, p_2, p_3\}$ are aligned, both in $\mathbb {R}^2$ and $\mathbb {R}\mathbb {P}^2$. This means that we can induce a stratification of $Conf_n(\mathbb {R}^2)$ using the one of . In particular, any alignment of $p_i, p_j, p_k$ can be seen as a pure algebraic condition on the points coordinates, given by the singularity of the determinant $d_{i,j,k} = |p_i~p_j~p_k|$. The sign of such determinant will depend on the clockwise or counter-clockwise position of the ordered triple $(p_i, p_j, p_k)$. Because the determinant is a continuous map onto $\mathbb {R}$, if two configurations ${\underline{p}}$ and ${\underline{q}}$ differ by one and only one determinant sign, say $d_{i,j,k}$, then we know that any continuous path from one configuration to the other has to cross the singularity loci of $d_{i,j,k}$.

The stratification in Fig. 2 can be interpreted using the  stratification. Considering the reference flag $V^*= \{p_1, \overline{p_1~p_2}\}$ and $V = \{p_4, \overline{p_4~p_3}\}$, we have that the annulus, singularity of dimension 2, corresponds to $v-l^*$. Inside it we have $v-v^*$, which is the singularity of dimension 1, displayed as a black circle. Finally, the singularities of dimension 0, displayed as yellow points, are $v-v^*, l-l^*$. Actually, there are 2 determinants that we are not considering, namely $d_{1,3,4}$ and $d_{2,3,4}$. The singularity surfaces are more difficult to visualize and would lead to a much finer stratification.

Given any configuration of 4 points in $\mathbb {R}^2$ we can map it continuously to $\mathbb {R}^4$, assigning to each coordinate the determinant value of $d_{1,2,3}, d_{1,2,4}, d_{1,3,4}$ and $d_{2,3,4}$, respectively. The singularity locus of a determinant can be seen either as an alignment of three points, as a flag intersection, or also as a hyperplane in $\mathbb {R}^4$ corresponding to one coordinate equal to 0. If we consider $\mathbb {R}^4$ minus the coordinate hyperplanes, $x_i=0$ for $i=1,\dots 4$, we obtain 16 disconnected smooth regions, each one containing points with same coordinates signs, that is, corresponding to configurations of points with same determinant signs. The reader should be aware however that such mapping is not one-to-one More than one configuration can be mapped to the same point in $\mathbb {R}^4$, as the determinants are invariant under $\mathbb {R}^2$-isometries.

The counter-image of these regions of $\mathbb {R}^4$ are the highest dimensional strata of the stratification of $Conf_n(\mathbb {R}^2)$ and they correspond to the subsets of all configuration with identical determinant signs. We can then uniquely associate to each stratum the label of the determinant signs sequence of any configuration of points in it, that is, a binary vector with 4 entries.

Fig. 4

Three different configurations of the 4 corner points of a rectangular textile, where we coloured in grey the back side. All configurations belong to different strata, $(+~+~+~+)$, $(+~+~-~+)$ and $(-~-~-~-)$, respectively, from left to right (Color figure online)

Note that each configuration in Fig. 4 would require in principle different robot manipulations for a folding task, e.g., using the taxonomy in Borràs et al. (2020), we would use point-tableplane sliding for the spread out configuration; point-point pick-up for the corner in the middle of the cloth; point-gripperplane sliding for the overfolded cloth, so as to turn it out.

These labels will not only tell us how to group “similar” configurations but also how “different” two configurations are. For example, we can count how many signs, resp. singularities, a continuous path from one configuration to another will change, resp. cross. The reader can now see that for $n<4$ such approach would be trivial. In the case of $n=3$ we get only two strata, corresponding to $p_3$ being on the right/left of the line $\overline{p_1~p_2}$. If $n=1,2$ then it is clear we cannot even define any determinant.

In the case $n=4$, the maximum number of strata we could obtain is $2^4=16$, however using the determinants expressions, we derive the following algebraic equation

$$\begin{aligned} d_{1,2,3}+d_{1,3,4}=d_{1,2,4}+d_{2,3,4}. \end{aligned}$$

It is straightforward to see that it is impossible that either $d_{1,2,3}$ and $d_{1,3,4}$ are positive and $d_{1,2,4}$ and $d_{2,3,4}$ are negative or vice versa. We can verify it explicitly considering the regions obtained assuming 3 points fixed, say $p_1, p_2$ and $p_3$, and $d_{1,2,3}$ either positive or negative. The former case is showed in Fig. 5.

Fig. 5

Let $d_{1,2,3}$ be positive, as in the figure. The region on the lower left corner (coloured in green) is the only one in common between the regions in which $d_{1,2,4}$ is negative (left of $\overline{p_1~p_2}$, coloured in yellow) and the ones in which $d_{2,3,4}$ is negative (below $\overline{p_2~p_3}$, coloured in blue). In this region also $d_{1,3,4}$ is negative (Color figure online)

Another consequence of such equation is that, if a configuration of points belongs to a stratum with odd number of minuses in its label, then there exists one point lying inside the triangle spanned by the others. We will call from now on such strata internal, otherwise we call them external. A graph of the adjacencies between the strata is shown in Fig. 6. We refer the reader to “Appendix A” for a thorough study of such relationships with respect to the  stratification for the case $n=4$.

Fig. 6

Representation of $Conf_4(\mathbb {R}^2)$, with strata adjacencies indicated by links between different sign sequences. We used cyan ellipses to denote external strata and red rectangles for internal ones (Color figure online)

3.2 C-space of a textile rectangle using n points

We can apply a similar procedure and obtain a similar definition of stratum for the general case of n points, however some issues regarding the admissibility of sign sequences need to be addressed.

As n increases, the number of flags and their position with respect to each other becomes more difficult to encode and a description based on it would make less clear the structure of the space. To avoid it we will employ only the determinants to detect changes between configurations. We know that given n points we have $k = {\left( \begin{array}{c} n\\ 3\\ \end{array}\right) }$ different triples of points, that is, k possible determinants. We can map any configuration of n points to a point $(x_1, \dots , x_k)$, where each $x_i$ corresponds to the determinant of a particular triple of points. We know that each coordinate hyperplane, $x_i = 0$ for $i=1,\dots , k$, corresponds to a singularity, that is, a determinant equal to zero, and the determinants are again continuous functions. We can then define a stratum of $Conf_n(\mathbb {R}^2)$ as the set of all configurations of n points with the same determinant sign sequence, and represent singularities between strata by null determinants, or equivalently by the alignments of three points. Such strata will correspond to regions of $\mathbb {R}^k$ after removing all coordinate hyperplanes. From now on, we consider the determinants ordered with lexicographic order on their indices with the constraint that for $k=3,\dots , n$, the first $\left( \begin{array}{c} k\\ 3\\ \end{array}\right)$ ones are those of $\{p_1,\dots , p_k\}$.

Even if we are able to encode each configuration of points as a sign sequence, we do not have a priori a way to determine if a sign sequence is admissible. This is an essential step of our study, because we want to be able, not only to group “similar” configurations, but as well navigate such stratification. For example if we want to find the optimal way to move n points from one configuration to another belonging to a different stratum, we might need to know which are the allowable paths, that is, which strata we can visit.

Suppose that $n-1$ points are fixed and we want to study the regions in which the arrangement of lines spanned by pairs of these points divide $\mathbb {R}^2$. Note that, these would represent strata of $Conf_n(\mathbb {R}^2)$, with identical determinant signs for the fixed $n-1$ points. This approach together with the knowledge of the stratification of $Conf_{n-1}(\mathbb {R}^2)$ would allow to construct the stratification of $Conf_n(\mathbb {R}^2)$. Line arrangements, both in the real and projective planes, have been studied extensively in various contexts, see Grünbaum (1972) and references therein. Several authors have worked on how to bound the number of regions, triangles or polygons (Roudneff 1986; Strommer 1977; Simmons 1973). In Aichholzer et al. (2018), the authors consider the problem of characterising geometric graphs using the order type of their vertex set. Using the notion of minimal representation of a graph, they identify which edges prevent the order type from changing via continuous deformations of the graph. Even if this approach is the closest to ours, to our knowledge in the literature there is not a detailed study of the adjacency relations of $Conf_n(\mathbb {R}^2)$. In particular there is not a study that tells us exactly which determinant signs sequence is admissible and which is not. We present here an iterative technique to construct the stratification of $Conf_n(\mathbb {R}^2)$.

The adjacency of two strata $\sigma , \tau$ can be seen as the possibility of nullifying one and only one determinant via continuous movement of a configuration ${\underline{p}}$ in $\sigma$ to another ${\underline{q}}$ in $\tau$. So if, given any stratum $\sigma$, we are able to detect with a deterministic test which determinants can or cannot be nullified, we are effectively identifying which strata are adjacent to $\sigma$. We can iteratively apply such test to these strata and, as $Conf_n(\mathbb {R}^2)$ is connected (Cohen et al. 1976), we would recover all the existing strata. For any $n\ge 3$ there exists always a configuration ${\underline{p}}^*$ such that each determinant sign of any triple of points is positive, namely when the points are placed to form a convex n-gon and they are in counter-clockwise order. In other words, there is always a stratum $\sigma ^*$ whose sign sequence is formed only by positive signs and that can be always used as starting point in such iterative process to find the strata of $Conf_n(\mathbb {R}^2)$. We will now proceed to explain how we can rigorously describe such test.

We know that the symmetric group $\mathbb {S}_n$ acts on $Conf_n(\mathbb {R}^2)$ via point permutations. That is, if we have ${\underline{p}} = \{p_i\}_{i=1}^n$, a configuration of n points, then the induced action of g, call it $f_g$, is defined as ${f_g({\underline{p}}) = \{p_{g(i)}\}_{i=1}^n}$. Note that $f_g$ is an automorphism of $Conf_n(\mathbb {R}^2)$, as $f_g^{-1} = f_{g^{-1}}$, furthermore it is also an automorphism of the singularity loci, as the singularity of a matrix does not change when we permute its rows. The action of g on the sign sequences can be easily deduced. Let $\sigma$ be the stratum of ${\underline{p}}$ and $g\in \mathbb {S}_n$, then the sign of $d_{g(i), g(j), g(k)}$ of the stratum $\tau =g\cdot \sigma$ to which $g\cdot {\underline{p}}$ belongs is the same, resp. opposite, of $d_{i,j,k}$ if the signature of (g(i), g(j), g(k)) is positive, resp. negative. From now on, we will study the adjacency between $\sigma$ and $\tau$ that differs by the sign of $d_{1,2,3}$, otherwise we can reduce to such case via a permutation of $\mathbb {S}_n$. In what follows, we assume w.l.o.g. that $\sigma$ has $d_{1,2,3}$ with positive sign. In other words, the adjacency test for $\sigma$ is reduced, via a suitable permutation, to establish if the determinant $d_{1,2,3}$ can be nullified. Such property is equivalent to the existence of the following map.

Definition 1

(Crossing map) Let ${\underline{p}}$ be a configuration in $Conf_n(\mathbb {R}^2)$ and consider for $1\le i\le n$ the continuous map ${H_i:[0,1]\rightarrow \mathbb {R}^2}$, such that ${H_i(0) = p_i}$. We call ${H = \bigotimes _i^n {H_i}}$ a crossing map for ${\underline{p}}$, if

$\bullet$:

$H(t)\in Conf_n(\mathbb {R}^2)$ for $t\in [0,1]$ ;

$\bullet$:

$d_{u,v,w}(H(t))\ne 0$ for $(u,v,w)\ne (1,2,3)$ and $t\in [0,1]$;

$\bullet$:

$d_{1,2,3}(H(0))\cdot d_{1,2,3}(H(1))<0$;

$\bullet$:

$\exists !~t\in (0,1)$ such that $d_{1,2,3}(H(t)) = 0$.

The existence of a crossing map for ${\underline{p}}\in \sigma$, a continuous path in $Conf_n(\mathbb {R}^2)$, is equivalent to the existence of $\tau$, a stratum with sign sequence identical to that of $\sigma$ but for the $d_{1,2,3}$ sign. It is clear now that such existence for a ${\underline{p}}\in \sigma$ is equivalent to the adjacency test for $\sigma$ we were looking for. We present here two theorems that allow us to determine if and when a crossing map exists. Such theorems are constructive, that is, we show also how we move continuously a point (or more if needed) to change only one determinant sign. We know that any triple of not-aligned points in $\mathbb {R}^2$ divide it in 7 open regions (Fig. 7), which are essential for the following discussion.

Fig. 7

The lines spanned by a triple of non-aligned points ${p_1, p_2, p_3}$ divide $\mathbb {R}^2$ in 7 regions. These can be split in three couples of dual regions and a self-dual region, here visually divided by colour and pattern. Each dual couple is formed by an external region and an internal one, as any point belonging to the former, resp. the latter, together with ${p_1, p_2, p_3}$, forms an external, resp. internal, sign sequence. The self-dual region consists of one internal region (Color figure online)

We are now ready to state the following.

Theorem 1

Let ${\underline{p}}$ be a configuration of points in $Conf_n(\mathbb {R}^2)$, if there exists a point $p_i\in {\underline{p}}$ in the self-dual region then there does not exist a crossing map for ${\underline{p}}$. Similarly, if there exist two points $p_j,p_k$ in two regions that are not dual, such map does not exist either.

Proof

See “Appendix B”. $\square$

The idea behind this theorem is that if we want to nullify $d_{1,2,3}$ we need to align $p_1, p_2, p_3$, without aligning any other triple in the process. For example if a point $p_k$ is inside the triangle spanned by these three points it is clear that aligning them would result in aligning all 4 of them.

As the sign sequence is invariant among all configurations of points in the same stratum $\sigma$, we have the following.

Corollary 1

Let $\sigma$ and $\tau$ be two sign sequences that differ by only one sign, namely that of $d_{1,2,3}$, positive for $\sigma$ and negative for $\tau$. If there exists a $k\ne 1,2,3$ such that the $\sigma$-subsequence relative to indices (1, 2, 3, k) is $(++-+)$ then $\sigma$ and $\tau$ are not adjacent. Similarly, if there exists $j,k\ne 1,2,3$ such that the $\sigma$-subsequences relative to (1, 2, 3, j) and (1, 2, 3, k) are different and not dual, then $\sigma$ and $\tau$ are not adjacent either.

The following result tells us when instead it is possible to change sign, that is when the adjacency exists.

Theorem 2

Consider ${\underline{p}}\in Conf_n(\mathbb {R}^2)$ such that Theorem 1 is not satisfied. Suppose that for any pair $4<i, j\le n$ it is true that either $p_i$ and $p_j$ belong to the same region and the tuple $(p_1,p_3,p_i,p_j)$ has an even number of minuses or they are in a dual couple and the tuple $(p_1,p_3,p_i,p_j)$ has an odd number of minuses. Then there exists a crossing map for ${\underline{p}}$.

Proof

See “Appendix B”. $\square$

When Theorem 2 is satisfied we can construct explicitly a crossing map so that all points but $p_2$ are fixed and $p_2$ moves along the line $\overline{p_4~p_2}$. In terms of strata adjacency we have the following corollary.

Corollary 2

Let $\sigma , \tau$, be two sign sequences that differ by only one sign, namely the one of $d_{1,2,3}$. Suppose that for any pair $4<i<j$ when the 4-tuples (1, 2, 3, i) and (1, 2, 3, j) are equal, resp. dual, we have that the sign subsequence relative to (1, 3, i, j) is external, resp. internal. Then $\sigma$ and $\tau$ are adjacent strata.

Note that, when two signs sequences differ only by one sign, they need to be adjacent, which means that, if they are not, either one or both are not present as strata in $Conf_n(\mathbb {R}^2)$. It is true that Theorem 2 is a necessary and sufficient condition for strata adjacency when $n<7$, but this is not true for higher n. When $n<7$ there is only one pair such that $4<i<j\le n$, that is, $i=5$ and $j=6$. This means that all points are involved: $p_1, p_2$ and $p_3$ determine the dual regions of the plane and $p_4$ determines the crossing map for $p_2$, permitted by the position of $p_5, p_6$. For the case $n\ge 7$ the conditions in Theorem 2 involve subsets of ${\underline{p}}$ and not all of them. When it is not satisfied, there might exist other ways to move $p_2$ across the line $\overline{p_1~p_3}$, that is, a crossing map for ${\underline{p}}$, for example moving more than one point.

The adjacency test between a stratum $\sigma$ with positive sign $d_{1,2,3}$ and $\tau = H_{1,2,3}(\sigma )$, the one with identical determinant signs but $d_{1,2,3}$, follows, where we denoted the duality relationship by $\parallel$ and its negative by $\nparallel$.

In the next section we will describe how to effectively compute the sign sequences admissible in $Conf_n(\mathbb {R}^2)$ when $n\le 6$ and how this structure can then be applied effectively to describe the “state” of the cloth.

4 Implementation and results

In this section we will demonstrate how Theorem 1 and Theorem 2 can be implemented in a finite algorithm that returns the stratification of $Conf_n(\mathbb {R}^2)$. We will show that the number of existing strata increases significantly with the number of points, and to consider such approach, as it is, for a mesh of hundreds of points would be unfeasible, both for the construction of the stratification and its practical use. We propose here to group different strata in macro-states, called just states from now on, using both symmetric relationships and topological properties of the stratification. We will show that using this revised approach we can assign to a mesh on hundreds of points a discrete distribution over such states, allowing us to distinguish between different cloth poses.

In Sect. 3 we showed that the combination of Theorem 1 and Theorem 2 can be used to determine the existence of a crossing map. Algorithm 1 assess the adjacency of a stratum $\sigma$ with respect the singularity of $d_{1,2,3}$. We know that the action of $\mathbb {S}_n$ allows to swap any triple (i, j, k) with (1, 2, 3), so this means that existence of any adjacency with respect to a given $d_{i,j,k}$ can be determined after permuting some indices.

We present now two further algorithms: Algorithm 2 where we combine Algorithm 1 and the action of $\mathbb {S}_n$ on $Conf_n(\mathbb {R}^2)$ to determine all adjacencies of a stratum, and Algorithm 3 where, from a chosen stratum $\sigma$, we search existing adjacencies iteratively to obtain all existing strata in $Conf_n(\mathbb {R}^2)$.

After applying Algorithm 2 to any $\sigma$ we obtain a set of existing strata, to which we can reapply Algorithm 2. This iterative application of Algorithm 2 can be done a finite number of times, as the number of all possible sign sequences is finite. Thanks to the connectedness of $Conf_n(\mathbb {R}^2)$, it is also true that we cannot miss any existing strata, if we iterate enough times. Algorithm 3 encodes such iterative process, assuming that the starting stratum is $\sigma ^*$, with all positive determinant signs, obtained placing n points as vertices of a convex n-gon and in counter-clockwise order.

Thanks to Algorithm 3 we are able to recover the structure of $Conf_n(\mathbb {R}^2)$ and, with it, also the number of strata, that is, sign sequences, present. As we can see in Table 1, the number of strata increases rapidly, and it is expected to rise quadratically in terms of n (Strommer 1977).

Table 1 The number of strata of $Conf_n(\mathbb {R}^2)$ is displayed together with their topological properties considering their adjacency graph

As we are aiming to deal with meshes with hundreds of points, considering the strata as representating cloth poses, it might be computationally challenging as their number grows dramatically. To overcome such problem, we will show how to group different strata, and so configurations entailing similar robotic manipulations, in states. In Cohen et al. (1976) the action of $\mathbb {S}_n$ on $Conf_n(\mathbb {R}^n)$ is studied and, in particular, we obtain that the quotient of this action gives us the unordered configuration space of n points. In terms of our stratification, such action induces an identification between configurations, and so between strata, whose determinant signs coincide after a permutation of the point labels, $\{1,\dots , n\}$. An example of different configurations belonging to the same $\mathbb {S}_n$-state is displayed in Fig. 8.

Fig. 8

Three different configurations of the 4 corner points of a rectangular textile, where we coloured in grey the back side. All configurations belong to different strata, but they are the same with respect to the $S_n$ action. These configuration require in principle different robot manipulations, for example if the goal is folding or unfolding (Color figure online)

Such action however does not always preserve faithfully the adjacency relationships, as it can happen that two strata in the same $\mathbb {S}_n$-equivalence class are adjacent. From our point of view, such possibility should be avoided, as a general rule. It implies that there exists a state containing a singularity loci, as two adjacent strata belong to it. We acknowledge the possibility that for a particular goal, the practitioner might allow it, if that singularity loci is not relevant for the particular task or goal sought.

Each stratum is labelled with a binary vector of determinant signs and we can measure the distance between two strata with the Hamming distance. It measures how many different determinant signs they have, or equivalently the number of singularity loci to be crossed to continuously move from one stratum to the other. The following equivalence relation ensures that no pair of adjacent strata belongs to the same state.

Definition 2

($\sim _\sigma$-States) Given a stratum of $Conf_n(\mathbb {R}^2)$, call it $\sigma$, we say that two strata $\tau _1$ and $\tau _2$ belongs to the same state if they are equally distant from $\sigma$ w.r.t. the Hamming distance and they are in the same $S_n$-state. We will denote such equivalence relation as $\tau _1\sim _{\sigma } \tau _2$.

It is easy to see that given two adjacent strata it is impossible for them to be inside the same state, as they will always have different sign distances from $\sigma$. It can be shown explicitly that, for different $\sigma$, the number of $\sim _\sigma$-states might change. To avoid confusion and be coherent in the choice of such $\sigma$ we will assume from now on that $\sigma = \sigma ^*$, that is, the stratum with correspondent sign sequence formed by only positive signs. Table 2 shows the number of $S_n$-states and $\sim _\sigma$-states for $n<7$.

Table 2 Number of $S_n$-states and $\sim _{\sigma }$-states in $Conf_n(\mathbb {R}^2)$

For any two states we can define a distance between them as the minimum Hamming distance between two strata in each state, which will always be greater than 0 if the states are different. We will say then that two states are adjacent if such distance is 1, as it implies that there exists at least two adjacent strata, one in each state.

As in each state we can have one or more strata, to avoid confusion, from now on we label each state using the sign sequence of one of them. As choice of label we consider the lowest sign sequence in the lexicographic order, assuming $+<-$. In Fig. 9 we can see the $\mathbb {S}^5$-states of $Conf_5(\mathbb {R}^2)$, using the labelling just explained, where we connected together states that are adjacent.

Fig. 9

Adjacency graph of the $\mathbb {S}_5$-states using lexicographic order for the choice of labels

As anticipated such states do not always preserve adjacencies. Consider the sign sequence ${\tau =(+++++}$ ${+++--)}$, which is in $Conf_n(\mathbb {R}^2)$. We know that $\tau$ cannot be in $A=(+++++++++---)$ otherwise it would be its label and so it has to be in $B=(+++++++++-)$. This means that in B we have two adjacent strata, as the label of a state corresponds to a stratum in it. For the $\sim _\sigma$-states this does not happen, thanks to their definition, even if they are a refinement of the $S_n$-states, as to be $\sim _\sigma$-equivalent two strata need to be $S_n$-equivalent. We show their adjacency graph in Fig. 10.

Fig. 10

Adjacency graph of the $\sigma ^*$-states of $Conf_5(\mathbb {R}^2)$ using lexicographic order for the choice of labels

We know that the stratum with all negative signs always exists, as it is obtained displaying the points in clockwise order. Its distance from $\sigma$ is exactly ${\left( \begin{array}{c} n\\ 3\\ \end{array}\right) }$. This means that the number of $\sim _\sigma$-states for $Conf_n(\mathbb {R}^2)$ is at least ${\left( \begin{array}{c} n\\ 3\\ \end{array}\right) }$. Again, even using states for representing C-space, instead of the stratification, their number for a mesh with hundreds of points becomes computationally challenging.

To avoid such challenge we propose to consider instead the distribution of states for the subsets of m points in the mesh, assuming the 4 corner points always in these subsets. As the case of $m=5$ is the simplest and visual considerations can be made quite clearly, we will focus first on this case and only after show its generalisation. The cloth simulations presented here are obtained synthetically using a Blender simulator (Sánchez-Riera et al. 2010).

As we are considering subsets with m points (with 4 corner points always present) there exists a one-to-one matching between each subset and the (internal) point of the mesh. We can then associate the $\mathbb {S}_n$-state, or $\sim _\sigma$-state, of this subset to its unique internal point and vice versa. This allows us to show in a clear fashion how the distribution of states varies from different cloth meshes. In Fig. 11 we show how this distribution can change when using different states, $\mathbb {S}_n$-states and $\sim _\sigma$-states.

Fig. 11

For the same mesh of a rectangular cloth with $\sim 700$ points on the top, we plot on the bottom the distribution of $S_n$-states (on the left) and the $\sim _\sigma$-states (on the right) using different colours for the internal points based on their associated states (Color figure online)

It is clear that we are dividing the mesh cloth in different “zones”, each one associated to a different state, and so having more states could imply obtaining more zones for the same mesh. We refer the reader to “Appendix C” for more particular state definitions. They are presented with a discussion on the differences with the $\mathbb {S}_n$-states and $\sim _\sigma$-states, as well as on the possible uses for the practitioner. It is important to note that the definition of state we propose can be adapted to different needs from the user, as well as different goals. For example the coarsening of the states, that is, of the grouping of strata in $Conf_n(\mathbb {R}^2)$, can be tuned and focus can be put or reduced on different states depending on their relative importance for the task at hand.

Given a mesh, we can map its state-zones to a vector in $\mathbb {R}^k$, with k the number of states considered, simply assigning to the $i^{th}$-coordinate the number of internal points associated to the $i^{th}$ state. In other words, given a mesh of n points, we are assigning to it a vector that encapsulates the state distribution of its points. The reader should bear in mind that this procedure can be also viewed in terms of configurations of n points. We are effectively projecting a configuration in $Conf_n(\mathbb {R}^2)$ to $n-4$ copies of the state-decomposition of $Conf_5(\mathbb {R}^2)$. Then, the state decomposition of $Conf_n(\mathbb {R}^2)$ can be obtained by identifying strata with identical $Conf_5(\mathbb {R}^2)$-state distribution with respect to such projection. Examples of such identification follow in Fig. 12.

Fig. 12

We consider the distribution of points in $\mathbb {S}_5$-states for different cloth meshes. The distribution of points in each $\mathbb {S}_n$-state, a vector in $\mathbb {R}^3$, is displayed for each mesh as a histogram. For brevity we indicate state $(+++++++++-)$ with A, state $(+++++++---)$ with B and state $(++++++++++)$ with C

This state distribution can be considered as a vector in the Euclidean space $\mathbb {R}^k$, so one could also identify “close” enough state-distribution vectors with respect to the Euclidean distance. We show in Fig. 13 how this distance can be able to encode such similarities and differences.

Fig. 13

A confusion matrix between different mesh poses using the heat function to represent low distance values (in red) and high ones (in blue). We can see that the similarity decreases for this particular example as the corner is moved across and out of the initial rectangle area (Color figure online)

If we want to generalise this approach for $m>5$ we should bear in mind that the association with the internal points will be impossible, that is, a “zone” decomposition of the mesh cloth would be meaningless. We will be considering all ${\left( \begin{array}{c} n-4\\ m-4\\ \end{array}\right) }$ subsets of $m-4$ internal points, so we cannot associate uniquely a state to a point. However, given a mesh cloth of n points such that the 4 corner points are given and a state definition, we can again associate to it a vector in $\mathbb {R}^k$ where k is the number of states in $Conf_m(\mathbb {R}^2)$. This allows us to see any cloth mesh as a vector in an Euclidean space and measure distances between different meshes, and additionally it gives also a way to decompose $Conf_n(\mathbb {R}^2)$ into regions on the basis of their associated vectors.

5 Conclusion

We have proposed an approach to represent the state of textiles in a global, coarse way useful for robot manipulation. It is well founded in topological grounds, as it relies on the configuration space (${\text {C-space}}$) of distinctive points in the cloth, whose combinatorial structure is derived from the stratification of the flag manifold. Moreover, two theorems, Theorem 1 and Theorem 2, defining conditions for adjacency in ${\text {C-space}}$, have been proved. Their algorithmic implementation in Algorithm 3 permits to derive the decomposition of the ${\text {C-space}}$ of a rectangular cloth with different granularities dependent on the particular goal sought.

More concretely, we proved in Sect. 3 how to determine computationally the adjacency relations of the strata in $Conf_n(\mathbb {R}^2)$ for $n\le 6$ and we are currently working on more general techniques for $n>6$. Note that this doesn’t limit the number of points used to determine the state of cloth, since all points in the cloth mesh can be used to this end (Fig. 11).

Such topological characterisation of cloth state represents a key element for the development of a theory of cloth manipulation based on computational topology and machine learning, that we are undertaking, as well as its implementation in the mobile manipulation robots servicing in our assisted living facility.

The cloth representation, as a distribution of states, will be used to link perception and planning. As shown in Sect. 4, using a state classification, the practitioner can obtain a subdivision of a rectangular cloth into state-induced “zones”. This could make way for a robot visual recognition of different global states of the cloth, depending on the amount of points in each zone (Fig. 13). Future works would include applying deep learning to cloth state recognition from images, by generating training instances using a physical simulator and labelling them with our proposed state encoding. Since, for the training instances we have the meshes (ground truth) with which the images have been generated, we can exactly obtain the state-distribution vectors of the mesh poses with our algorithms.

On the manipulation planning side, characterising the states of textile objects and the feasible transformations under given actions in a compact operational way (i.e., a graph-encoding manipulation-oriented states and transitions), would permit probabilistic planning of actions that ensure reaching a desired cloth configuration despite low-accuracy perceptions. In this direction, a framework to characterise and systematise grasps, manipulation primitives and tasks for the versatile handling of clothes by robots has been proposed (Borràs et al. 2020). Tasks are represented as sequences of manipulation primitives, which yield state changes. We envisage to map these changes to transitions in our state graph. A toy example of this approach is displayed in Fig. 14.

Fig. 14

Example of subpath of cloth meshes and distribution of $\mathbb {S}_n$-states, that would appear in a graph of states and transitions to plan the folding of a towel, using the taxonomy of Borràs et al. (2020)

In this paper we have only considered static cloth states and envisaged their usage in manipulations where cloth dynamics can be neglected. Other authors have studied recently how to learn dynamics of deformable objects and fluids (Li et al. 2019) and in a reinforcement learning context Jangir et al. (2020) distinguishing between static and dynamic cloth manipulation tasks. These approaches, together with our state-subdivision in zones of the cloth, could determine efficiently the effect of a grasp by propagating the long-range influence among cloth particles, as in Mrowca et al. (2018), and consequently enabling us to determine the state-distribution after the grasp as well as to predict, under dynamical effects, the optimal path between two different state-distribution vectors in $\mathbb {R}^k$.

In sum, we believe that the proposed topological representation of cloth macro-state is a promising element towards effectively closing the perception-action loop in cloth manipulation.

Appendices

Adjacency study

In this appendix, we investigate further the adjacency relations of the stratification of $Conf_n(\mathbb {R}^2)$. We proceed first introducing the concept of affine flag and the corresponding stratification of , subset of affine flags in . Thanks to this stratification and the symmetric action of $\mathbb {S}_4$ on $Conf_4(\mathbb {R}^2)$ we are able to provide a matching between the singularities of  and those of $Conf_4(\mathbb {R}^2)$. This allows us to determine how the singularity, that is, alignment of three points, between two strata has to be crossed, in terms of the relative position of such points.

In Sect. 3 we show how the stratification of $Conf_4(\mathbb {R}^2)$ can be obtained using the  one. This is done after mapping each point to $\mathbb {R}\mathbb {P}^2$ and then considering the pair of flags these projective points determine. These flags are affine flags, as both the point v and the line l in each of them does not belong to the line at infinity $z = 0$. In other words, affine flags are those flag that can be projected in the affine plane $\mathbb {R}^2$. The set of all such flags, indicated with , can be stratified using the stratification of , see Fig. 2. If $X_i$ is the set of i-dimension strata of  then we define the set of i-dimensional strata of  as the connected components of $X_i\cap$ . It can happen that, when intersected with , a stratum of  is disconnected into two connected components. To distinguish them in such cases, we annotate their label with a $+$ or − sign depending on the placement of V and $V^*$ with respect with each other, see Fulton (1997); Hiller (1982). The resulting stratification is displayed in Fig. 15.

Fig. 15

Stratification of  induced by the one of , where stratum signs indicates how the affine flags in it are placed with respect to the reference one, $V^*$

For the singularities $v-l^*$ and $l-v^*$, the difference between the two connected components is the following. If one consider the flag as $V^*= \{p_1, \overline{p_1~p_2}\}$ then $(v-l^*)^+$ is formed by all those flags $V = \{v, l\}$ such that $v\in l^*$ and the vectors $\overline{p_2-p_1}$ and $\overline{v-p_1}$ are concord, otherwise we are in the singularity $(v-l^*)^-$. Similarly happens for the two connected components of $l-v^*$.

Any stratum in $Conf_4(\mathbb {R}^2)$ can be associated to a stratum of  , modulo the definition of V and $V^*$ with respect to $p_1, p_2, p_3$ and $p_4$. For example, the stratum with label $(++++)$ is $\emptyset ^+$ when we consider $V^*=\{p_1, \overline{p_1, p_2}\}$ and $V=\{p_3, \overline{p_3, p_4}\}$. We will show next how we can associated to any singularity of $Conf_4(\mathbb {R}^2)$ between adjacent strata a singularity of . Thanks to the action of $\mathbb {S}_4$ on $Conf_4(\mathbb {R}^2)$, such characterisation can be easily determined.

A permutation $g\in \mathbb {S}_4$ induces on $Conf_4(\mathbb {R}^2)$ the map $f_g$ such that it sends any configuration ${\underline{p}}$ to one determined by $\{p_{g(i)}\}_{i=1}^4$, permuting accordingly the points. The map $f_g$ is an automorphism of $Conf_4(\mathbb {R}^2)$ and when restricted to the singularity loci, it remains an automorphism, as the singularity of a determinant does not change under permutation. The reader should bear in mind that this does not imply that $f_g$ is an automorphism when restricted to each singularity alone. Without loss of generality we can focus only on the maps induced by the permutations (1, 2),  (2, 3) and (3, 4), as they generate the entire $\mathbb {S}_4$. As explained before the singularities $(v-l^*)^\pm$ and $(l-v^*)^\pm$ can be expressed in terms of “concordant” or not alignment of three points. We can track the effect of permutation on such alignments and so we can detect how a permutation g will change any singularity of , again assuming V and $V^*$ are previously defined. In Fig. 16 we show how the alignment changes via permutations, denoting by $i-j-k$ the alignment where $p_j$ belongs to the segment of $p_i$ and $p_k$, identifying $i-j-k$ with $k-j-i$.

Fig. 16

We show the effect of each basis element, $e_i = (i,i+1)$, of $\mathbb {S}_4$ on the alignments of any three points. Any possible alignment of three points is reached using a finite composition of the basis elements

We consider the following flags

$\bullet$:

$V_1 = \{v_1, l_1\}$ with $v_1 = p_1$ and $l_1 = \overline{p_1~p_2}$;

$\bullet$:

$V^*_1 = \{v^*_1, l^*_1\}$ with $v^*_1 = p_3$ and $l^*_1 = \overline{p_3~p_4}$

and

$\bullet$:

$V_1 = \{v_2, l_2\}$ with $v_2 = p_2$ and $l_2 = \overline{p_2~p_1}$;

$\bullet$:

$V^*_2 = \{v_2, l_2\}$ with $v^*_2 = p_4$ and $l^*_2 = \overline{p_4~p_3}$.

Note that, given two adjacent strata $\sigma$ and $\tau$, with connecting singularity $i-j-k$, their images, under the action of any $g\in \mathbb {S}_4$, will still be adjacent and $g(i)-g(j)-g(k)$ will correspond to the singularity between them. We can then rewrite Fig. 16 in terms of the singularity of .

Fig. 17

We show the effect of each basis element, $e_i = (i,i+1)$, of $\mathbb {S}_4$ on the alignments of any three points, in terms of  singularities

Using Fig. 17 and knowing that the connecting singularity of $(++++)$ and $(-+++)$ is $1-2-3$, or also $(v_1-l_1^*)^+$, we can determine the “type” of any singularity between two adjacent strata, that is, the corresponding singularity of , as follows (Fig. 18).

Fig. 18

Representation of $Conf_4(\mathbb {R}^2)$, with strata adjacencies in terms of singularities of , using the pair of flags $V^*_1, V_1$ and $V^*_2, V_2$. We used cyan ellipses to denote external strata and red rectangles for internal ones (Color figure online)

It is easy to check that each possible singularity, $(v_i-l^*_i)^\pm$ and $(l_i-v^*_i)^\pm$, is present in the stratification of $Conf_4(\mathbb {R}^2)$ showed in Fig. 15. In particular we have that any stratum has always at least one singularity in terms of $V_1, V_1^*$ and one $V_2, V_2^*$, which should convince the reader that we need both pairs. We leave the study of singularities with lower dimension, that is, associated to $v_i-v_i^*$ and $(l_i-l_i^*)^\pm$, for the future.

Proofs of Theorems 1 and 2

In this section we will prove Theorem 1 and Theorem 2 in details, using the notion of dual regions, as in Fig. 7, to test if there exists a crossing map between two strata, see Definition 1.

For any crossing map H, the configurations H(0) and H(1) belong to adjacent strata. We can assume then that the configuration $H(0) = {\underline{p}}$, is such that $p_1 = (0,0), p_2 = (1,0)$ and $p_3 = (0,1)$. This can be achieved via $f:\mathbb {R}^2\rightarrow \mathbb {R}^2$ with

$$\begin{aligned} p\mapsto f(p) = \begin{pmatrix}x_2-x_1&{}x_3-x_1\\ y_2-y_1&{}y_3-y_1\end{pmatrix}^{-1}(p-p_1). \end{aligned}$$

(1)

Note that f does not change the sign of any determinant. In addition we can assume that $H_1$ is constant over t, that is $H_1(t)\equiv (0,0)$. If not, we apply to each $H_i:[0,1]\rightarrow \mathbb {R}^2$ the translation $-H_1:[0,1]\rightarrow \mathbb {R}^2$. The map $H-H_1$ is also a crossing map, because for any t the configuration ${{\underline{q}} = \{H_i(t)-H_1(t)\}_{i=1}^n}$ has identical sign sequence to ${\{H_i(t)\}_{i=1}^n}$. In addition, at any t the configuration ${\underline{q}}$ has $q_1=(0,0)$.

Similarly we assume that $p_2$ belongs to the positive x-semiaxis. If not, we apply now a suitable rotation with centre the origin, such that for any t the point $H_2(t)$ is mapped to the positive x-semiaxis. Again we have a crossing map, as rotations are sign-preserving isometries, and clearly for any t the image of $p_2$ with respect to such map is on the positive x-semiaxis. One can alternatively assume that $p_3$ is on the positive, or negative, y-semiaxis instead. Furthermore we can assume that $H_2(t)\equiv (1,0)$, via an homogeneous dilation at each t of $\mathbb {R}^2$ with centre the origin and dilation factor $y_2>0$, which ensures that the sign sequence does not change. If we suppose that $p_3$ is constantly on the positive y-semiaxis, we can similarly assume $H_3(t) \equiv (0,1)$.

In the following proof of Theorem 1, we make use of these assumptions, that w.l.o.g. extremely simplify the proof. For brevity, to denote the determinant of the image of points $p_i, p_j$ and $p_k$ under H, we will write $d_{i,j,k}(t)$ when the context is clear

Proof

Suppose there exists $p_i\in {\underline{p}}$ in the self-dual region (cf. Fig. 7) and H is a crossing map. As the sign sequence of H(0) is $(++-+)$, H(1) has sign sequence $(-+-+)$, which is impossible as it is not an admissible sequence of $Conf_4(\mathbb {R}^2)$.

For $i=1,\dots , n$ let ${H_i(t) = \left( x_i(t), y_i(t)\right) }$ and suppose there exist two points $p_j, p_k$ in two not dual regions. Thanks to our assumptions on H, we have $d_{1,2,3}(t) = y_3(t)$, and, because H is a crossing map, we have that for some $t_0$ it is true that ${y_3(0)>y_3(t_0) = 0>y_3(1)}$. Denoted by $\sigma _s(t)$, for $s = j, k$, the sign sequence of the points $H_1(t), H_2(t), H_3(t)$ and $H_s(t)$, we can analyse each possible case.

Case 1.:

Consider $\sigma _j(0)=(++++)$. If $\sigma _k(0)$ is $(++--)$ or $(+++-)$, we have the following inequalities.

$$\begin{aligned} {\left\{ \begin{array}{ll} 0<d_{1,2,j} = y_j(t)\\ 0<d_{1,2,k} = y_k(t)\\ 0<d_{2,3,j}(t) = d_{1,2,3}(t)-y_j(t)+x_3(t)y_j(t)\\ 0>d_{2,3,k}(t) = d_{1,2,3}(t)-y_k(t)+x_3(t)y_k(t). \end{array}\right. } \end{aligned}$$

then

$$\begin{aligned} {\left\{ \begin{array}{ll} 0<y_j(t_0)\\ 0<y_k(t_0)\\ 0<-y_j(t_0)+x_3(t_0)y_j(t_0)\Rightarrow x_3(t_0)>1\\ 0>-y_k(t_0)+x_3(t_0)y_k(t_0)\Rightarrow x_3(t_0)<1. \end{array}\right. } \end{aligned}$$

This is a contradiction.

Case 2.:

Suppose $\sigma _j(0)$ is $(+++-)$ and $\sigma _k(0)$ is $(+-++)$, or $\sigma _j(0)$ is $(++++)$ and $\sigma _k(0)$ is $(+-++)$. In both cases we have the following inequalities.

$$\begin{aligned} {\left\{ \begin{array}{ll} 0<d_{1,2,j}(t) = y_j(t)\\ 0>d_{1,2,k}(t) = y_k(t)\\ 0<d_{1,3,j}(t) = x_3(t)y_j(t)-y_3(t)x_j(t)\\ 0<d_{1,3,k}(t) = x_3(t)y_k(t)-y_3(t)x_k(t). \end{array}\right. } \end{aligned}$$

then

$$\begin{aligned} {\left\{ \begin{array}{ll} 0<y_j(t_0)\\ 0>y_k(t_0)\\ 0<x_3(t_0)y_j(t_0)\Rightarrow x_3(t_0)>0\\ 0<x_3(t_0)y_k(t_0)\Rightarrow x_3(t_0)<0. \end{array}\right. } \end{aligned}$$

This is a contradiction.

It is left to the reader to see that any other pair of different and not dual configurations can be reduced via a suitable symmetric action to the two considered above.$\square$

Given a couple of dual regions we can map it to another one using the permutation (2, 3, 1) or (3, 1, 2), which will also keep the determinant $d_{1,2,3}$ of the same sign. This means that we can reduce our considerations to only one of such couples, namely ${(++++)}$ and ${(+---)}$. We assume w.l.o.g. that the crossing map is such that $H_1(t)$ is the origin and $H_3(t)\equiv (0,1)$ for any t. We are now ready to prove Theorem 2.

Proof

The proof is divided into three parts. First we prove that any line passing through $p_i$ and $p_j$ with $i,j>4$ does not cross the self-dual region. Then we prove that it does not happen also for the lines passing through $p_1,p_i$ and $p_3,p_i$. As a consequence, we are able in the last part to construct explicitly a crossing map for ${\underline{p}}$.

Consider $L:\mathbb {R}\rightarrow \mathbb {R}^2$, parametric expression of $\overline{p_i~p_j}$, such that we have $L(0) = p_i$ and $L(1) = p_j$.

$$\begin{aligned} L(t)={\left\{ \begin{array}{ll} x(t) &{}= (x_j-x_i)~t+x_i,\\ y(t) &{}= (y_j-y_i)~t+y_i, \end{array}\right. } \end{aligned}$$

(2)

with $p_i = (x_i, y_i)$ and $p_j = (x_j, y_j)$. We show first that the line $\overline{p_i~p_j}$ never crosses the self-dual region. If a point $q = (x,y)$ is in the self-dual region we have $x,y>0$ and $x+y<1$, as its state corresponds to the sign sequence ${(++-+)}$. We will denote $\sigma _{i,j}$ the sign sequence of the state relative to $(p_1, p_3, p_i, p_j)$. As we will make broad use of them, we write the explicit expressions of $d_{1,i,j}$ and $d_{3,i,j}$, given w.l.o.g. that $p_1=(0,0)$, $p_2=(1,0)$ and $p_3=(0,1)$.

$$\begin{aligned} {\left\{ \begin{array}{ll} d_{1,i,j} &{}= x_i~y_j-x_j~y_i,\\ d_{3,i,j} &{}= d_{1,i,j}+x_j-x_i. \end{array}\right. } \end{aligned}$$

(3)

As before we need to examine different cases depending on $\sigma _i$, resp. $\sigma _j$, the sign sequence of the points $p_1, p_2, p_3$ and $p_i$, resp. $p_1, p_2, p_3$ and $p_j$. That is, each case will correspond to a different pair of regions to which $p_i$ and $p_j$ belong.

• Case 1. If both $\sigma _i$ and $\sigma _j$ are ${(+---)}$, then $\sigma _{i,j}$ is either ${(--++)}$ or ${(----)}$. Note that the permutation (i, j) allows to pass from one case to the other, that is, we can assume both $d_{1,i,j}$ and $d_{3,i,j}$ positive. Suppose there exists L(t) from Eq. (2) inside the self-dual region, that is, $x(t)>0$. We know that $x_i,x_j<0$ from the expression of $\sigma _i$ and $\sigma _j$, so by continuity there exists a $t_0$ such that $x(t_0)=0$. In particular, this implies that $x_i-x_j\ne 0$, otherwise x(t) will be constant and always negative.

  • (a) If $x_i<x_j$, from Eq. (2) we have

    

    As $x(t_0) = 0$ then ${z(t_0) = 1+\frac{d_{3,i,j}}{x_j-x_i}}>1$, with $z(t) = x(t)+y(t)$. We have

    

    As ${1<z(t)}$, we have that L(t) is not in the self-dual region.

  • (b) If $x_j<x_i$, from Eq. (2) we have

    

    As $x(t_0) = 0$ then $y(t_0) = \frac{d_{1,i,j}}{x_i-x_j}<0$. From $y_i>1-x_i>0$ we have

    

    Thus, L(t) is not in the self-dual region as y(t) is negative.

• Case 2. If both $\sigma _i$ and $\sigma _j$ are ${(++++)}$, then $\sigma _{i,j}$ is either ${(++--)}$ or ${(++++)}$. Note that the permutation (i, j) allows to pass from one case to the other, that is, we can assume both $d_{1,i,j}$ and $d_{3,i,j}$ negative. Suppose there exists L(t) from Eq. (2) inside the self-dual region, that is, ${z(t)<1}$ for some t. We know that $z_i, z_j$ are greater than 1, as both $d_{1,i,j}$ and $d_{3,i,j}$ are negative, so by continuity there exists $t_0$ such that $z(t_0)=1$. In particular, this implies that ${z_i\ne z_j}$, otherwise z(t) will be constant and always greater than 1.

  • (a) If ${z_i<z_j}$, from Eq. (2) we have

    

    As $z(t_0) = 1$ then we have ${x(t_0) = \frac{d_{3,i,j}}{z_i-z_j}<0}$ from Eq. (2), and, therefore,

    

    Thus, L(t) is not in the self-dual region as $x(t)<0$.

  • (b) If ${z_j<z_i}$, from Eq. (2) we have

    

    As $z(t_0) = 1$ then $y(t_0) = 1+\frac{d_{3,i,j}}{z_j-z_i}>1$ and $x(t_0)<0$. From Eq. (2) we have

    

    Since $x(t)<0$, we have that L(t) is not in the self-dual region.

• Case 3. $\sigma _i$ is ${(++++)}$ and $\sigma _j$ is ${(+---)}$.

  We now have that $\sigma _{i,j}$ is either ${(+-++)}$ or ${(+---)}$, with $i<j$. The case $j<i$ is obtained permuting i with j. The condition ${\sigma _{i,j} = (+-++)}$ is equivalent to ${d_{1,i,j}>0}$ as the sign sequence $(+-+-)$ is not admissible. Similarly we have that $\sigma _{i,j}$ equal to ${(+---)}$ is equivalent to assume ${d_{3,i,j}<0}$. As before, suppose there exists L(t) from Eq. (2) inside the self-dual region, that is, ${x(t), y(t)>0}$ and ${z(t)<1}$ for some t. Note that as $p_3 = (0,1)$ we have ${d_{1,3,k} = -x_k}$ for any $3\le k$. We know that $y_j<0<y_i$ from the expression of $\sigma _i$ and $\sigma _j$, so by continuity of Eq. (2) there exists $t_0$ such that $y(t_0)=0$. Similarly, as $x_j<0<x_i$, there exists a $t_1$ such that $x(t_1)=0$. Thus we have

  

  In particular $t_1<t<t_0$, so $x(t_0)>0$ and $y(t_1)>0$. Furthermore, as $z_i<1<z_j$ we have $z(t_0)<z(t)<z(t_1)$.

  • (a) If $d_{1,i,j}>0$ then, as $x(t_1) = 0$, we have $y(t_1) = \frac{d_{1,i,j}}{x_j-x_i}<0$, contradiction. Then there cannot exists L(t) inside the self-dual region.

  • (b) If $d_{3,i,j}<0$ then, as $z(t_0) = 1+\frac{d_{3,i,j}}{x_i-x_j}>1$, we have $z(t)>1$, contradiction. Then there cannot exists L(t) inside the self-dual region.

In conclusion, any line $\overline{p_i~p_j}$ with $i,j>4$ does not cross the self-dual region.

Consider $\overline{p_1, p_i}$ with $i>4$ and its parametric expression

$$\begin{aligned} L_1(t):\ {\left\{ \begin{array}{ll} x(t) &{}= x_i~t,\\ y(t) &{}= y_i~t. \end{array}\right. } \end{aligned}$$

(4)

If $\sigma _i = (++++)$ then $x_i<0<y_i$, so either $x_i t, y_i t$ are both 0 or they are discordant, that is, the point $L_1(t)$ is never in the self-dual region. Similarly if $\sigma _i = (+---)$.

Consider $\overline{p_3, p_i}$ with $i>4$ and its parametric expression

$$\begin{aligned} L_3(t):\ {\left\{ \begin{array}{ll} x(t) &{}= x_i~t,\\ y(t) &{}= (y_i-1)~t+1. \end{array}\right. } \end{aligned}$$

(5)

If $\sigma _i = (++++)$ then $x_i<0$. Suppose that $L_3(t)$ belongs to the self-dual region, then $t<0$ as $x(t)>0$, but $x_i+y_i<1$ so $x(t)+y(t)>1$. That is, the point $L_1(t)$ is never in the self-dual region. Similarly if $\sigma _i = (+---)$.

In conclusion we have that the only lines crossing the self-dual region will be $\overline{p_2~p_i}$ for $i=1,\dots , n$. In particular as any pair of them crosses at $p_2$, then they cannot cross inside the self-dual region. If we move $p_2$ inside the self-dual region, along $\overline{p_2~p_4}$ and so continuously, the sign sequence of ${\underline{p}}$ remains the same. That is, we are describing a continuous path of $Conf_n(\mathbb {R}^2)$ that is contained inside the stratum $\sigma$ of ${\underline{p}}$. It is only when $\overline{p_2~p_4}$ crosses $\overline{p_1~p_3}$ that the sign sequence changes, that is, when the singularity loci is crossed at $d_{1,2,3}$. Let $L_{2,4} = \overline{p_2~p_4}$ and $\lambda$ such that $L_{2,4}(\lambda )\in \overline{p_1~p_3}$. We can assume, modulo orientation of $L_{2,4}$, that $\lambda >0$ and $L_{2,4}(0) = p_2$, in particular this means that for any $t>\lambda$ we have $L_{2,4}(t)$ with x-coordinate negative. Consider $\mu >\lambda$ such that for any $t>\lambda$ such that $L_{2,4}(t)$ belongs to some $\overline{p_i~p_j}$, we have $t>\mu$. For $i\ne 2$ consider the continuous map $H_i:[0,1]\rightarrow \mathbb {R}^2$ as the constant map $H_i(t) \equiv p_i$ and $H_2$ as follows.

$$\begin{aligned} H_2(t) = \mu (p_4-p_2)t+p_2, \end{aligned}$$

(6)

To check that H is a crossing map we need to check only $H_2$. Clearly $H_2(0)=p_2$ and $H_2$ is continuous. Consider $0<t_0 = \frac{\lambda }{\mu }<1$, then $H_2(t_0)\in \overline{p_1~p_3}$, and as $H_2$ is a linear map this can happen only once. It remains to prove that the sign sequence of H(1) differs only by the sign of $d_{1,2,3}$ with respect to $\sigma$. We have that $H_2(1)$ has negative x-coordinate, so $d_{1,2,3}$ changes sign as wanted. Furthermore, if any other determinant $d_{2,i,j}$ changes sign, for $(i,j)\ne (1,3)$, then $d_{2,i,j}(t)=0$ for $t\in (t_0,1)$, as inside the self-dual region it cannot happen. That is, there exists $\lambda<\nu <\mu$ such that $L_{2,4}(\nu )$ belongs to $\overline{p_i, p_j}$, which is impossible. All in all, $H=\{H_i\}_{i=1}^n$ is a crossing map, as wanted.$\square$

Note that, thanks to these two theorems we are able to construct Algorithm 1, and, thanks to the proof of Theorem 2, we can explicitly construct the crossing map between two adjacent strata.

Different states definitions

In Sect. 4 we proposed two different state definitions based on $\mathbb {S}_4$ and on the topological structure of the stratification of $Conf_n(\mathbb {R}^2)$. A practitioner however might want or need to study the state of a cloth with particular (or less) focus on a subset of points. For example, if ${\underline{q}}$ is a configuration of m points, subset of ${\underline{p}}\in Conf_n(\mathbb {R}^2)$, then one could group together strata of $Conf_n(\mathbb {R}^2)$ depending on the strata of ${\underline{p}}$ and that of ${\underline{q}}$, or instead that of ${\underline{p}}\setminus {\underline{q}}$. In this appendix we will show other two state definition based on the $\mathbb {S}_n$-states and $\sim _\sigma$-ones. Again we will assume that $\sim _\sigma$ is defined using as “base-stratum” the sequence of all positive signs. Even if we show here only two cases, it is clear that depending on the cloth in analysis, the mesh properties but as well the manipulation task in mind, different states can be defined. For now on, we will assume that ${\underline{q}}$ are always the first m points in ${\underline{p}}$, again for user-defined states such assumption might not be true.

Fig. 19

Adjacency graph of $\varGamma (m, n)$-states, blue dashed lines denote a change for the state of ${\underline{q}}$

Fig. 20

Adjacency graph of $\varGamma (n, m)$-states, blue dashed lines denote a change for the state of ${\underline{q}}$ (Color figure online)

As explained previously, if we consider the $\mathbb {S}_n$-states, we are effectively forgetting the labelling given to each point. On the other hand, when using the $\sim _\sigma$-states we are able to track how far away we are from the “base-stratum” $\sigma$. If we are interested on the labels of the first m points and how their distance change, we would define the following.

Definition 3

($\varGamma (m, n)$-States) Given two strata $\tau _1, \tau _2$ of $Conf_n(\mathbb {R}^2)$, for $i=1,2$ we denote by $\sigma _i$ the subsequence of the first ${\left( \begin{array}{c} m\\ 3\\ \end{array}\right) }$ signs, strata in $Conf_m(\mathbb {R}^2)$. We say that $\tau _1$ and $\tau _2$ belong to the same $\mathbb {S}_n$-state if they are in the same $S_n$-state and $\sigma _1$ is in the same $\sim _\sigma$-state of $\sigma _2$. We will denote such equivalence relation as $\tau _1\sim _{(m,n)} \tau _2$.

The adjacency graph of such classes for $n=5$ and $m=4$ is displayed in Fig. 19, note that unlike the $\sim _\sigma$-states, self-loops can now occur as they are a refinement of the $\mathbb {S}_n$-states.

On the opposite case, if our intention is to study the state of the cloth, without giving importance to the labelling of ${\underline{q}}$, then we can define the following states.

Definition 4

($\varGamma (n, m)$-States) Given two strata $\tau _1, \tau _2$ of $Conf_n(\mathbb {R}^2)$, for $i=1,2$ we denote by $\sigma _i$ the subsequence of the first ${\left( \begin{array}{c} m\\ 3\\ \end{array}\right) }$ signs, strata in $Conf_m(\mathbb {R}^2)$. We say that $\tau _1$ and $\tau _2$ belong to the same $\sim _\sigma$-state if they are in the same $S_n$-state and $\sigma _1$ is in the same $\mathbb {S}_m$-state of $\sigma _2$. We will denote such equivalence relation as $\tau _1\sim _{(n,m)} \tau _2$.

The adjacency graph of such states for $n=5$ and $m=4$ is displayed in Fig. 19.

As the graphs displayed in Figs. 19 and 20 are not isomorphic, we know that these two state definitions are different. Note that, as $\varGamma (n, m)$-states are a refinement of the $\sim _\sigma$-states, there cannot be self-loops in its adjacency graph. This does not always happen for the $\varGamma (m, n)$-states as they are a refinement of $\mathbb {S}_n$-states, which do have self-loops.

There are clearly a lot more possible state definitions than the ones we presented here. From our point of view, interesting ones can arise when considering instead of $\mathbb {S}_n$ subgroups of it, for example the one generated by the cycle $(1,2\dots , n)$. This would produce a refinement of $\mathbb {S}_n$-states which is not identical to the one of $\sim _\sigma$. Furthermore one could use such states as in Definition 4 or Definition 3 to group together configuration that are equal after cyclic permutation of m, or n, points.