Algorithms for Identifying Rigid Subsystems in Geometric Constraint Systems

Christophe Jermann, Bertrand Neveu, Gilles TrombettoniIJCAI 2003

Introduction

In fields ranging from computer-aided design (CAD) and robotics to molecular biology, determining the rigidity of a system of geometric objects is a fundamental challenge. A Geometric Constraint Satisfaction Problem (GCSP) consists of objects (points, lines, planes) and constraints (distances, angles, incidences). A system is considered rigid if no continuous motion of the objects is possible without violating constraints, and over-constrained if it contains redundant constraints that may lead to mathematical inconsistencies.

Examples of Geometric Constraint Satisfaction Problems (GCSPs) where traditional counting fails.

The Failure of Degree-of-Freedom Counting

Historically, industry-standard algorithms like the "Dense" algorithm have relied on "structural rigidity." This approach simplifies the problem by counting degrees of freedom (DOF): if the number of constraints equals the DOFs, the system is assumed rigid. However, this purely combinatorial method ignores the underlying geometry.

Pathological cases, such as systems involving parallel lines or specific point-line configurations, often cause these algorithms to fail. For instance, three parallel lines admit different displacements than three lines in a general configuration. Standard solvers frequently misidentify these as over-rigid, causing significant issues in CAD software and robotic path planning.

Proposed Methodology: Extended Structural Rigidity

To address these limitations, researchers from EPFL and INRIA have introduced a new approach based on extended structural rigidity. The core of this method is the Degree of Rigidity (DOR), which replaces fixed DOF counts with a measure that accounts for specific geometric properties.

The proposed Over-Rigid algorithm improves upon previous methods through two key innovations:

  1. Geometric Awareness: By utilizing the DOR, the algorithm correctly identifies the number of independent displacements a subsystem actually admits, preventing the false positives common in DOF-counting methods.
  2. Active Constraint Flow Distribution: Traditional methods often fail because they apply "overflow" (excess constraints) to a single node. The new algorithm introduces a dedicated "Active constraint" node ($R$) that can distribute flow across multiple objects, allowing for a more accurate diagnostic of subsystem rigidity.
Object-constraint networks showing flow distribution for identifying rigid subsystems.

Flow-Based Identification

The algorithm constructs an object-constraint network and employs maximum flow techniques (such as the Ford-Fulkerson algorithm) to determine if the network can "absorb" the constraints. If the flow cannot be fully distributed, the algorithm identifies the specific subsystem that is over-rigid. By focusing on "DOR-minimal" subsystems, the algorithm maintains computational efficiency, avoiding the exponential complexity of checking every possible combination of objects.

Results and Complexity

The algorithm was evaluated using well-known "pathological" configurations in both 2D and 3D. In every test case, including the parallel line configuration shown in Figure 1a, the Over-Rigid algorithm correctly identified the system's status where previous state-of-the-art solvers failed.

Crucially, this increased accuracy does not come at a high computational cost. The time complexity remains $O(n^2(n + m))$, where $n$ is the number of objects and $m$ is the number of constraints—equivalent to the complexity of the less accurate algorithms currently in use.

Conclusion

By bridging the gap between combinatorial counting and geometric reality, the Over-Rigid algorithm provides a more robust foundation for geometric modeling. Its ability to handle complex geometric dependencies without increasing computational overhead makes it a prime candidate for integration into industrial CAD tools and robotic motion planners. Future work will look toward expanding this framework to include deformable objects, such as circles with variable radii.

Summary updated

BibTeX
@inproceedings{jermann2003algorithms,
  author = {Christophe Jermann and Bertrand Neveu and Gilles Trombettoni},
  title = {{Algorithms for Identifying Rigid Subsystems in Geometric Constraint Systems}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2003},
}
Figure