Dependency graph solution for constraint systems
US5617510A · kind A · utility
Assignee
Inventors
Key dates
| Filing date | Apr 12, 1995 |
| Grant date | Apr 1, 1997 |
| Priority date | — |
| Expiry date | Apr 12, 2015 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F30/17
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
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.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.