Geometric Constraint Propagation with Quantum Labels

This paper presents an incremental approach to geometric constraint satisfaction that categorizes solutions into so-called quanta. A quantum is a range of solutions with uniform geometric characteristics. This approach is suitable for interactive design because it can handle (perhaps temporarily) incomplete specifications and alternative solutions, and performs satisfaction locally and incrementally. The intermediate solutions are kept in the geometric domain, so that new geometric constraints can be interpreted on the same high level of abstraction, allowing powerful reasoning. Both alternative discrete solutions and continuous ranges of solutions are determined. Propagation of information is performed by ‘propagation of known state’, and the information itself results from ‘solution set inference’, where a solution set is represented in geometrical form by unions and intersections of quantum labels. This representation allows the use of simple logical expressions of constraints, it uniformly handles delayed satisfaction, and it supports ‘constraint inference’, the derivation of implied constraints by geometric reasoning.