Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
439565 | Computer-Aided Design | 2011 | 16 Pages |
This paper describes new ways to tackle several important problems encountered in geometric constraint solving, in the context of CAD, and which are linked to the handling of under- and over-constrained systems. It presents a powerful decomposition algorithm of such systems.Our methods are based on the witness principle whose theoretical background is recalled in a first step. A method to generate a witness is then explained. We show that having a witness can be used to incrementally detect over-constrainedness and thus to compute a well-constrained boundary system. An algorithm is introduced to check if anchoring a given subset of the coordinates brings the number of solutions to a finite number.An algorithm to efficiently identify all maximal well-constrained parts of a geometric constraint system is described. This allows us to design a powerful algorithm of decomposition, called WW-decomposition, which is able to identify all well-constrained subsystems: it manages to decompose systems which were not decomposable by classic combinatorial methods.
► A powerful and easy to implement method to decompose constraint systems is presented. ► The decomposition algorithm is not sensitive to the connectivity of the constraint graph. ► A robust way to test rigidity and to identify maximal well-constrained systems is presented. ► All algorithms are incremental and can thus use idle time.