Dependency graph solution for constraint systems

Details Dependency graph solution for constraint systems Dependency graph solution for constraint systems

1995-04-12

1997-04-01

Downs, Robert W.

G06F 1520

Patent

active

056175108

ABSTRACT:
A method, useful in computer-aided design, of identifying possible solutions to an over-constrained system having a collection of entities and constraints. The method represents the entities in terms of degrees of freedom and incrementally assembles the system by adding entities, satisfying constraints and reducing the degrees of freedom of the entities. For an over-constrained system, the method constructs a dependency graph of the system and identifies the set of constraints which over-constrains the system. The over-constraining set includes the constraint which initiated the over-constraint and those constraints back traced in the dependency graph from the initiating constraint. Removal of one or more constraints from the over-constraining set results in a solvable fully or under-constrained system. Intelligent selection of the removed constraint may increase computational efficiency or system stability. The method is useful in diverse constraint satisfaction problems, particularly geometric modeling problems such as describing mechanical assemblies, constraint-based sketching and design, geometric modeling for CAD, and kinematic analysis of robot and linkage mechanisms.

REFERENCES:
patent: 5251290 (1993-10-01), Pabon
patent: 5390294 (1995-02-01), Takeuchi
patent: 5410496 (1995-04-01), Bolon et al.
patent: 5412762 (1995-05-01), Kondo
patent: 5427531 (1995-06-01), Kramer
patent: 5497452 (1996-03-01), Shimizu et al.

Affiliated with

Also associated with

Rating

Dependency graph solution for constraint systems does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Dependency graph solution for constraint systems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Dependency graph solution for constraint systems will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-546518