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

stra

A Geometric Constraint Solver

William Bouma Ioannis Fudosy Christoph Ho mann

Department of Computer Science, Purdue University

West Lafayette, IN 47907-1398

Departmen

Jiazhen Caiz Robert Paigez

t of Computer Science, Courant Institute

251 Mercer Str., New York, NY 10012

Report CSD-TR-93-054x

Abstract

We report on the development of a two-dimensional geometric con-

CAD

int solver. The solver is a major component of a new generation of

resenta

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.

purp

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

o

capabilities or technical characteristics of the solver, and is independent

sk

f the interface. Such a representation can become the basis for archiving

sk

etches in a neutral format, with the ability to retrieve the archived

lar

etch and edit it; 13, 12 . Our solution is also a building block for a

an

ger project of developing a new generation of CAD systems based on

and

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

g

LEX and Yacc, our constraint solver also makes use of the high level lan-

tr

uage SETL2 27 to specify complex combinatorial algorithms and the

sy

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-

clude

a redirecting the solver to a di erent solution of a well-constrained

sketch,

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

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.

tere

Solving over- and underconstrained sketches is of signi cant practical in-

proa

st. In our experience, solving underconstrained sketches is customarily ap-

metr

ched by adding, as the solution progresses, constraints derived from the

const

ic properties of initial sketch, using ad-hoc rules for the selection of such

solved

raints. We can prove that an underconstrained sketch can be partially

straints

in a unique way, using the given constraints; 10 . However, adding con-

must rely

the

deduced from the metric properties of the user-supplied rough sketch

We als

cons

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.

proc

se

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

og

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.

expr

While users of geometric constraint solving systems think geometrically and

inter

ess themselves with visual gestures, constraint solvers work with a di erent

unde

nal representation. Most users will be quite unaware of the nature of the

Coup

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,

intent,

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.

3

Title: paperA.dvi

Creator: dvips 5.485 Copyright 1986-92 Radical Eye Software

Producer: Acrobat Distiller Command 3.01 for Solaris 2.3 and later (SPARC)

CreationDate: Sat Dec 10 11:55:31 1910

Tagged: no

Form: none

Pages: 30

Encrypted: no

Page size: 612 x 792 pts (letter) (rotated 0 degrees)

File size: 232851 bytes

Optimized: no

PDF version: 1.2