Solving Systems of 3D Geometric Constraints with Non-rigid Clusters

摘要

We present a new constructive solving algorithm for systems of 3D geometric constraints. The solver is based on the cluster rewriting approach, which can efficiently solve large constraint systems, and incrementally handle changes to a system, but can so far solve only a limited class of problems. The new solving algorithm extends the class of problems that can be solved, while retaining the advantages of the cluster rewriting approach. It rewrites a system of constraints to clusters with various internal degrees of freedom. Whereas previous constructive solvers only determined rigid clusters, we also determine two types of non-rigid clusters. This allows us to solve many additional problems that cannot be decomposed into rigid clusters, without resorting to expensive algebraic solving methods.