Mark W. Brunkhart

EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-94-808
May 1994

http://www2.eecs.berkeley.edu/Pubs/TechRpts/1994/CSD-94-808.pdf

Graphics and modeling systems allow users to place objects or primitives in space and permit the individual editing of these objects. A more powerful paradigm allows relationships expressed by constraints to be established and maintained between pairs of these primitives. For example, two lines might be constrained to be parallel or two points constrained to be coincident. These geometric constraints lead to a "live" model in which design changes to one part of the model may induce changes elsewhere thus permitting the encoding of the designer's intent into the model.

Constraints may describe complex non-linear algebraic relationships between the parameters of a model. To provide constraint satisfaction and maintenance in an interactive environment requires extremely fast and general equation solving techniques. We have developed a system called MechEdit for the interactive editing and animation of planar linkages to demonstrate techniques applicable to general geometric constraint-solving problems.

MechEdit combines analytic and iterative numerical techniques for constraint-system solving. A system of equations derived from a linkage is first examined and ordered based upon dependencies between parameters. Parameters that can be solved by propagating values are solved using backsubstitution. Among the remaining unsolved equations, a set of basic geometric reductions are used to identify parameters that can be solved analytically by combining pairs of equations. Finally, Newton-Raphson iteration is used to solve the remaining parameters. Singular value decomposition is used to solve systems of linear equations within the inner-loop of the Newton-Raphson iteration to provide quasi-physical motion for under-constrained and degenerate systems. By providing high-performance, interactive constraint maintenance and robust solving for complex systems, MechEdit demonstrates the power of constraints as a paradigm for specifying relationships between the primitives of a geometric model.

BibTeX citation:

@techreport{Brunkhart:CSD-94-808,
    Author = {Brunkhart, Mark W.},
    Title = {Interactive Geometric Constraint Systems},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {1994},
    Month = {May},
    URL = {http://www2.eecs.berkeley.edu/Pubs/TechRpts/1994/5603.html},
    Number = {UCB/CSD-94-808},
    Abstract = {Graphics and modeling systems allow users to place objects or primitives in space and permit the individual editing of these objects. A more powerful paradigm allows relationships expressed by constraints to be established and maintained between pairs of these primitives. For example, two lines might be constrained to be parallel or two points constrained to be coincident. These geometric constraints lead to a "live" model in which design changes to one part of the model may induce changes elsewhere thus permitting the encoding of the designer's intent into the model. <p>Constraints may describe complex non-linear algebraic relationships between the parameters of a model. To provide constraint satisfaction and maintenance in an interactive environment requires extremely fast and general equation solving techniques. We have developed a system called MechEdit for the interactive editing and animation of planar linkages to demonstrate techniques applicable to general geometric constraint-solving problems. <p>MechEdit combines analytic and iterative numerical techniques for constraint-system solving. A system of equations derived from a linkage is first examined and ordered based upon dependencies between parameters. Parameters that can be solved by propagating values are solved using backsubstitution. Among the remaining unsolved equations, a set of basic geometric reductions are used to identify parameters that can be solved analytically by combining pairs of equations. Finally, Newton-Raphson iteration is used to solve the remaining parameters. Singular value decomposition is used to solve systems of linear equations within the inner-loop of the Newton-Raphson iteration to provide quasi-physical motion for under-constrained and degenerate systems. By providing high-performance, interactive constraint maintenance and robust solving for complex systems, MechEdit demonstrates the power of constraints as a paradigm for specifying relationships between the primitives of a geometric model.}
}

EndNote citation:

%0 Report
%A Brunkhart, Mark W.
%T Interactive Geometric Constraint Systems
%I EECS Department, University of California, Berkeley
%D 1994
%@ UCB/CSD-94-808
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/1994/5603.html
%F Brunkhart:CSD-94-808