Patent US718061A successfully refreshed from Google Patents.
Patent US5564033A successfully refreshed from Google Patents.
Patent US5452238A successfully refreshed from Google Patents.
US5452238A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method for solving geometric constraint systems
Assignee: Schlumberger Technology Corp
•
Filing: 1992-11-20
•
Granted: 1995-09-19
•
Expires: 2012-11-20
Abstract
Abstract A method, useful in computer-aided design, for finding possible configurations of a system having a collection of geometric entities and constraints. The method represents the geometric entities in terms of degrees of freedom and systematically satisfies the constraints reducing the degrees of freedom of the geometric entities. The method uses a number of specialized routines, called plan fragments, which satisfy a particular constraint relating to a particular geometric entity. Each plan fragment changes the configuration of a geometric entity in space--i.e. the location and orientation--satisfying a constraint and reducing a degree of freedom. The series of plan fragments which reduce the degrees of freedom and satisfy the constraints comprise an assembly plan for possible configurations of the system. The method identifies overconstrained, fully constrained, and underconstrained systems to the user and assists in finding possible configurations if the constraints are changed, added, or deleted. The method is useful in solving any geometric constraint problem, such as describing mechanical assemblies constraint-based sketching and design, geometric modeling for CAD, and kinematic analysis of robots and linkage mechanisms. By reasoning symbolically about the geometry of the system, the method provides faster solutions, numerical stability, user feedback, and the ability to handle redundant constraints.
Inventors
- 👤 Glenn A. Kramer
- 👤 Walid T. Keyrouz
- 👤 Jahir A. Pabon
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-08 10:30
CPC Classifications
G; G06; G06F; G06F30/00; G06F30/10; G06F30/17
Claims Analysis
Total Claims: 27
Claim 1
Independent Claim
143 words
In a digital computer having a processor and memory, a method of determining the configuration of a system comprising a collection of geometric entities satisfying a set of constraints, comprising the steps of: representing the geometric entities in terms of degrees of freedom and storing the geometric entities in memory; building an assembly plan comprising a plurality of plan fragments using said processor to incrementally satisfy constraints and systematically reduce the degrees of freedom, including the substeps-- using a first plan fragment for a first geometric entity and a first constraint which transforms the geometric entity to a first configuration satisfying the first constraint and reducing at least one degree of freedom, using other plan fragments for other geometric entities and other constraints satisfying constraints and reducing degrees of freedom; determining possible configurations of the collection of geometric entities using said assembly plan.
Claim 2
Dependent Claim
143 words
In a digital computer having a processor and memory, a method of determining the configuration of a system comprising a collection of geometric entities satisfying a set of constraints, comprising the steps of: representing the geometric entities in terms of degrees of freedom and storing the geometric entities in memory; building an assembly plan comprising a plurality of plan fragments using said processor to incrementally satisfy constraints and systematically reduce the degrees of freedom, including the substeps-- using a first plan fragment for a first geometric entity and a first constraint which transforms the geometric entity to a first configuration satisfying the first constraint and reducing at least one degree of freedom, using other plan fragments for other geometric entities and other constraints satisfying constraints and reducing degrees of freedom; determining possible configurations of the collection of geometric entities using said assembly plan.
Claim 3
Dependent Claim
18 words
The method of claim 1, said representing step including parameterizing geometric entities by a set of configuration variables.
Claim 4
Dependent Claim
23 words
The method of claim 2, the geometric entity comprising a rigid body and the configuration variables comprising translational and rotational degrees of freedom.
Claim 5
Dependent Claim
18 words
The method of claim 2, the set of configuration variables describing translational, rotational, and dimensional degrees of freedom.
Claim 6
Dependent Claim
18 words
The method of claim 1, said representing step comprising creating a data structure having a plurality of invariants.
Claim 7
Dependent Claim
23 words
The method of claim 1, said building step including developing a unique plan fragment for each geometric entity and constraint in the system.
Claim 8
Dependent Claim
27 words
The method of claim 6, including storing the developed plan fragments as subroutines in computer memory and calling the subroutines for use in building said assembly plan.
Claim 9
Dependent Claim
37 words
The method of claim 6, including the substep of organizing in a table the plan fragments for a type of geometric entity with the number of plan fragments corresponding to the number of possible combinations of invariants.
Claim 10
Dependent Claim
24 words
The method of claim 1, said building step including repeating the use of the plan fragments until all of the system constraints are satisfied.
Claim 11
Dependent Claim
28 words
The method of claim 9, said determining step including identifying a closed form solution if all of the degrees of freedom of the system are reduced to zero.
Claim 12
Dependent Claim
50 words
The method of claim 1, said building step including the substeps of grouping a plurality of geometric entities as a subnetwork, solving the subnetwork by temporarily grounding one of the geometric entities and using plan fragments to satisfy the constraints, and reformulating the subnetwork as a single, rigid-body, geometric entity.
Claim 13
Dependent Claim
33 words
The method of claim 11, the subnetwork comprising a chain and the solving substep satisfies constraints of respective geometric entities causing the geometric entities to be fixed rigidly with respect to each other.
Claim 14
Dependent Claim
24 words
The method of claim 11, the subnetwork comprising a loop and the solving substep satisfying the constraints relating the geometric entities to each other.
Claim 15
Dependent Claim
24 words
The method of claim 13, including the substep of identifying the loop with the fewest degrees of freedom and solving the identified loop first.
Claim 16
Dependent Claim
54 words
The method of claim 1, including a second geometric entity related to the first geometric entity by a constraint, including the step of determining the locus of possible configurations of at least a portion of the first and second geometric entities as the intersection of the loci of possible configurations for each geometric entity.
Claim 17
Dependent Claim
52 words
The method of claim 15, including a third geometric entity related by a constraint to at least one of the first or second geometric entities, including the substep of finding the locus of the third entity in terms of the loci of the first or second geometric entity and known geometric relations.
Claim 18
Dependent Claim
38 words
The method of claim 1, including the steps of changing the system by adding, deleting, or altering a constraint, identifying portions of the system affected by the change, and rebuilding an assembly plan only for the affected portions.
Claim 19
Dependent Claim
135 words
In a digital computer, having processor means and memory means a method of determining the configuration of a geometric constraint system comprising a collection of geometric entities satisfying a set of constraints, comprising the steps of: a. storing information in memory means for entities and constraints, said information comprising constraints, geometric entities, and a plurality of plan fragments which each transform a geometric entity to a configuration satisfying a constraint; b. using said stored information by said processor means to generate an assembly plan for at least partially assembling a computer representation of a configuration of said geometric constraint system; c. storing said assembly plan in memory means; and d. using said assembly plan by said processor means to at least partially assemble computer representations of one or more configurations of said geometric constraint system.
Claim 20
Dependent Claim
135 words
In a digital computer, having processor means and memory means a method of determining the configuration of a geometric constraint system comprising a collection of geometric entities satisfying a set of constraints, comprising the steps of: a. storing information in memory means for entities and constraints, said information comprising constraints, geometric entities, and a plurality of plan fragments which each transform a geometric entity to a configuration satisfying a constraint; b. using said stored information by said processor means to generate an assembly plan for at least partially assembling a computer representation of a configuration of said geometric constraint system; c. storing said assembly plan in memory means; and d. using said assembly plan by said processor means to at least partially assemble computer representations of one or more configurations of said geometric constraint system.
Claim 21
Dependent Claim
17 words
The method of claim 18, wherein the geometric entities are represented in terms of degrees of freedom.
Claim 22
Dependent Claim
16 words
The method of claim 19, the representation comprising a data structure having a plurality of invariants.
Claim 23
Dependent Claim
20 words
The method of claim 18, including the substep of developing a unique plan fragment for each geometric entity and constraint.
Claim 24
Dependent Claim
23 words
The method of claim 18, said using said assembly plan step includes identifying a closed form solution indicative of a single topological configuration.
Claim 25
Dependent Claim
29 words
The method of claim 18, said using said assembly plan step includes adding default constraints to the system and assembling a computer representation of a configuration of the system.
Claim 26
Dependent Claim
25 words
The method of claim 23, including iteratively varying the default constraints and assembling a configuration until an error function in the plan fragments approaches zero.
Claim 27
Dependent Claim
42 words
The method of claim 17, where one or more of the constraints is input to the system in step a., including the step of e. numerically executing the assembly plan, checking for degeneracies, and recording the degrees of freedom of the assembly.
References Cited (Backward Citations)
US4791579A
Cited
US4757461A
Cited
EP0161964A1
Cited
US4736206A
Cited
US4831548A
Cited
US4868766A
Cited
US4831546A
Cited
US4858146A
Cited
US4912657A
Cited
US4866663A
Cited
US4928233A
Cited
US4855939A
Cited
US4835709A
Cited
US4965740A
Cited
US5043929A
Cited
US5253189A
Cited
US5297057A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1998-09-18 | 1999-03-20 | 1999-09-19 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2002-09-18 | 2003-03-20 | 2003-09-19 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2006-09-18 | 2007-03-20 | 2007-09-19 | $7700.00 | Window Closed / Lapsed |