Home / geometry calculators and solvers / A Geometric Constrain t Solv er - Purdue University

A Geometric Constrain t Solv er - Purdue University - geometry calculators and solvers

A Geometric Constrain t Solv er - Purdue University-geometry calculators and solvers

A Geometric Constraint Solver
William Bouma Ioannis Fudosy Christoph Ho mann
Department of Computer Science, Purdue University
West Lafayette, IN 47907-1398
Jiazhen Caiz Robert Paigez
t of Computer Science, Courant Institute
251 Mercer Str., New York, NY 10012
Report CSD-TR-93-054x
We report on the development of a two-dimensional geometric con-
int solver. The solver is a major component of a new generation of
systems that we are developing based on a high-level geometry rep-
and ach
tion. The solver uses a graph-reduction directed algebraic approach,
ieves interactive speed. We describe the architecture of the solver
and its basic capabilities. Then, we discuss in detail how to extend the
scope of the solver, with special emphasis placed on the theoretical and
human factors involved in nding a solution | in an exponentially large
search space | so that the solution is appropriate to the application and
the way of nding it is intuitive to an untrained user.
1 Introduction
Solving a system of geometric constraints is a problem that has been consid-
ered by several communities, and using di erent approaches. For example, the
symbolic computation community has considered the general problem, in the
Supported in part by ONR contract N00014-90-J-1599, by NSF Grant CDA 92-23502, and
by NSF Grant ECD 88-03017.
ySupported by a David Ross fellowship.
zSupported in part by ONR contract N00014-90-J-1890, by AFOSR grant 91-0308, and by
NSF grant MIP 93-00210.
xRevised January 1994. This report and others are available via anonymous ftp to
arthur.cs.purdue.edu, in directory pub cmh and subsidiaries.
context of automatically deriving and proving theorems from analytic geome-
try, and applying these techniques to vision problems; 5, 8, 14 . The geometric
modeling community has considered the problem for the purpose of developing
sketching systems in which a rough sketch, annotated with dimension and con-
straints, is instantiated to satisfy all constraints. This work will be reviewed in
the next section. The applications of this approach are in mechanical engineer-
ing, and, especially, in manufacturing.
With this work, we have mainly manufacturing applications in mind. Our
oses and goals are as follows:
1. We develop a constraint solver in which the information ow between
the user interface and the underlying solver has been formalized by a
high-level representation that is minimally committed to the particular
capabilities or technical characteristics of the solver, and is independent
f the interface. Such a representation can become the basis for archiving
etches in a neutral format, with the ability to retrieve the archived
etch and edit it; 13, 12 . Our solution is also a building block for a
ger project of developing a new generation of CAD systems based on
eutral, high-level geometry representation that expresses design intent
preserves the ability to redesign.
2. We explore the utility of several di erent general-purpose and interoperat-
ing rapid prototyping languages and systems for developing speci c tools
for experimenting conveniently with a variety of ideas and approaches to
constraint solving. Aside from well-known special purpose tools such as
LEX and Yacc, our constraint solver also makes use of the high level lan-
uage SETL2 27 to specify complex combinatorial algorithms and the
ansformational system APTS 7, 23 to perform syntactic analysis and
mbolic manipulation of geometrical constraint speci cations.
3. We study a number of neglected aspects of constraint solving. They in-
a redirecting the solver to a di erent solution of a well-constrained
b devising generic techniques for extending the capabilities of the solver
while preserving interactive speed, and
c a rigorous correctness proof of the solver.
Note that the correctness proof is reported separately 10 .
This paper reports substantial progress in all three problem dimensions, and
identi es a number of open issues that remain.
2 Approaches to Geometric Constraint Solving
We consider only well-constrained, two-dimensional sketches formed from points,
lines, circles, segments and arcs. Constraints are explicit dimensions of distances
and angles, as well as constraints of parallelism, incidence, perpendicularity, tan-
gency, concentricity, collinearity, and prescribed radii. We exclude relations on
dimension variables and inequality constraints. In particular, the user speci es
a rough sketch and adds to it geometric and dimensional constraints that are
normally not yet satis ed by the sketch. The sketch only has to be topologi-
cally correct. The constraint solver determines from the sketch the geometric
elements that are to be found, and processes the constraints to determine each
geometric element such that the constraints are satis ed.
Solving over- and underconstrained sketches is of signi cant practical in-
st. In our experience, solving underconstrained sketches is customarily ap-
ched by adding, as the solution progresses, constraints derived from the
ic properties of initial sketch, using ad-hoc rules for the selection of such
raints. We can prove that an underconstrained sketch can be partially
in a unique way, using the given constraints; 10 . However, adding con-
must rely
deduced from the metric properties of the user-supplied rough sketch
We als
on a heuristic selection. We explain in Section 5 why this is di cult.
o argue in Section 5 that consistently over-constrained sketches have
attractive property that the number of possible solutions is reduced. In
equence, such constraint problems can unambiguously specify user-intent.
However, nding a solution is intractable even for very simple con gurations,
and more research is needed to devise demonstrably e ective approaches.
Our constraint solver is variational. That is, the solver is not obliged to
ess the constraints in a predetermined sequence, and the constraints speci-
ed by the user are not parametric in the sense that they must be determined
rially, each as an explicit function of the previous constraints. This is anal-
ous to writing the constraints in a declarative language, where the solution
is independent of the order in which the constraints are written down. This
greatly increases the generality of the constraint solving problem, and demands
solvers that are based on advanced mathematical concepts.
While users of geometric constraint solving systems think geometrically and
ess themselves with visual gestures, constraint solvers work with a di erent
nal representation. Most users will be quite unaware of the nature of the
rlying representation and of the internal workings of the constraint solver.
in gen
led with the fact that a well-constrained geometric constraint problem has,
eral, exponentially many solutions, only one of which satis es the user's
constraint solvers therefore have to address two distinct tasks:
1. Determine whether the problem can be solved and if so, how.
2. Among the possible solutions, identify the one the user has intended.