Solving networks of geometric constraints

• US 8,345,043 B2
• Filed: 04/13/2007
• Issued: 01/01/2013
• Est. Priority Date: 04/13/2007
• Status: Active Grant

• Current Assignee: Autodesk, Inc.
• Original Assignee: Autodesk, Inc.
• Inventors: Kripac, Jiri, Madeira de Freitas Garcia, Jose
• Primary Examiner(s): Wu, Xiao M.
• Assistant Examiner(s): Hoang, Phi
• Application Number:
  US11/735,363
• Publication Number:
  US 20080252663A1
• Time in Patent Office: 2,090 Days
• Field of Search: 345/848, 715/856, 703/1
• US Class Current: 345/420
• CPC Class Codes: G06F 2111/04 Constraint-based CAD
• CPC Class Codes: G06F 30/00 Computer-aided design [CAD]
• CPC Class Codes: G06F 30/17 Mechanical parametric or variational design

Abstract

Systems, program products and program products for accepting a request to move a first geometric entity that is constrained to other geometric entities in a drawing that may contain both one-way and two-way geometric constraints. A set of affected geometric entities that need to be repositioned or otherwise changed as the result of moving the first geometric entity is identified. The affected geometric entities and the geometric constraints are classified into groups which are solved using a variational geometric constraint solver. If the geometric constraints cannot be satisfied, the movement of the first geometric entity is restricted. Otherwise the affected geometric entities are updated.

Claims

1. A computer-implemented method for solving geometric constraints between geometric entities in a drawing, comprising:

accepting a request to move a child geometric entity in a plurality of geometric entities, the child geometric entity being geometrically constrained to at least one parent geometric entity in the plurality of geometric entities by a one-way constraint where the one-way constraint constrains changes to the child relative to the parent geometric entity but does not constrain changes to the parent geometric entity;

identifying a set of affected geometric entities in the plurality of geometric entities that need to be repositioned or otherwise changed based on the request;

classifying the set of affected geometric entities and any associated geometric constraints into a plurality of groups based on the geometric constraints and topologically ordering the groups according to directions of constraints between the groups;

solving the groups according to the ordering using a variational geometric constraint solver to determine one or more updated attributes of the child geometric entity;

determining that an updated attribute of the child geometric entity would, if updated, invalidate the one-way constraint with the parent geometric entity; and

based on determining that the updated attribute of the child geometric entity would, if updated, invalidate the one-way constraint with the parent geometric entity, restricting movement of the child geometric entity,

wherein accepting, identifying, classifying, solving and updating are performed by one or more computers.

2. The method of claim 1 where:

the request for moving the first geometric entity is due to user input to move the first geometric entity or is a result of the first geometric entity being automatically moved in order to satisfy a geometric constraint.

3. The method of claim 1 where:

a geometric entity is two-dimensional or three-dimensional.

4. The method of claim 1 where:

a geometric constraint can be based on one of the following constraints;

distance, angle, radius, coincidence, parallel, perpendicular, collinear, tangential, concentric, equal, horizontal, vertical, or an arithmetic expression involving attribute values.

5. The method of claim 1 wherein classifying the set of affected geometric entities into groups also comprises:

classifying geometric entities and two-way constraints in the affected geometric entities each into individual groups, one group per geometric entity and one group per two-way constraint;

if a two-way geometric constraint in the individual groups is for geometric entities from two or more different groups, merging the different groups into a single group along with the two-way geometric constraint group; and

if a two-way geometric constraint in the individual groups is for geometric entities in a same group, adding the two-way geometric constraint to the same group.

6. A computer program product, encoded on a machine-readable storage device, operable to cause data processing apparatus to perform operations comprising:

accepting a request to move a child geometric entity in a plurality of geometric entities, the child geometric entity being geometrically constrained to at least one parent geometric entity in the plurality of geometric entities, and where the plurality of geometric entities are constrained by a plurality of geometric constraints including at least one two-way constraint, and where the child geometric entity and parent geometric entity are constrained by a one-way constraint;

identifying a set of affected geometric entities in the plurality of geometric entities that need to be repositioned or otherwise changed based on the request;

classifying the set of affected geometric entities and the geometric constraints into a plurality of groups based on the geometric constraints and topologically ordering the groups according to directions of constraints between the groups;

solving the groups according to the ordering using a variational geometric constraint solver to determine one or more updated attributes of the child geometric entity;

determining that an updated attribute of the child geometric entity would, if updated, invalidate the one-way constraint with the parent geometric entity; and

based on determining that the updated attribute of the child geometric entity would, if updated, invalidate the one-way constraint with the parent geometric entity, restricting movement of the child geometric entity.

7. The program product of claim 6 where:

the request for moving the first geometric entity is due to user input to move the first geometric entity or is a result of the first geometric entity being automatically moved in order to satisfy a geometric constraint.

8. The program product of claim 6 where:

a geometric entity is two-dimensional or three-dimensional.

9. The program product of claim 6 where:

a one-way or a two-way geometric constraint can be based on one of the following constraints;

distance, angle, radius, coincidence, parallel, perpendicular, collinear, tangential, concentric, equal, horizontal, vertical, or an arithmetic expression involving attribute values.

10. The computer program product of claim 6 wherein classifying the set of affected geometric entities into groups also comprises:

classifying geometric entities and two-way constraints in the affected geometric entities each into individual groups, one group per geometric entity and one group per two-way constraint;

if a two-way geometric constraint in the individual groups is for geometric entities from two or more different groups, merging the different groups into a single group along with the two-way geometric constraint group; and

if a two-way geometric constraint in the individual groups is for geometric entities in a same group, adding the two-way geometric constraint to the same group.

11. A system comprising processor electronics configured to perform operations comprising:

accepting a request to move a child geometric entity in a plurality of geometric entities, the child geometric entity being geometrically constrained to at least one parent geometric entity in the plurality of geometric entities, and where the plurality of geometric entities are constrained by a plurality of geometric constraints including at least one two-way constraint, and where the child geometric entity and parent geometric entity are constrained by a one-way constraint;

identifying a set of affected geometric entities in the plurality of geometric entities that need to be repositioned or otherwise changed based on the request;

classifying the set of affected geometric entities and the geometric constraints into a plurality of groups based on the geometric constraints and topologically ordering the groups according to directions of one-way constraints between the groups;

solving the groups according to the ordering using a variational geometric constraint solver to determine one or more updated attributes of the child geometric entity;

determining that an updated attribute of the child geometric entity would, if updated, invalidate the one-way constraint with the parent geometric entity; and

based on determining that the updated attribute of the child geometric entity would, if updated, invalidate the one-way constraint with the parent geometric entity, restricting movement of the child geometric entity.

12. The system of claim 11 where:

the request for moving the first geometric entity is due to user input to move the first geometric entity or is a result of the first geometric entity being automatically moved in order to satisfy a geometric constraint.

13. The system of claim 11 where:

a geometric entity is two-dimensional or three-dimensional.

14. The system of claim 11 where:

a one-way or a two-way geometric constraint can be based on one of the following constraints;

distance, angle, radius, coincidence, parallel, perpendicular, collinear, tangential, concentric, equal, horizontal, vertical, or an arithmetic expression involving attribute values.

15. The system of claim 11 wherein classifying the set of affected geometric entities into groups also comprises:

classifying geometric entities and two-way constraints in the affected geometric entities each into individual groups, one group per geometric entity and one group per two-way constraint;

if a two-way geometric constraint in the individual groups is for geometric entities from two or more different groups, merging the different groups into a single group along with the two-way geometric constraint group; and

if a two-way geometric constraint in the individual groups is for geometric entities in a same group, adding the two-way geometric constraint to the same group.

16. A computer-implemented method comprising:

receiving a request to change an attribute of a first geometric entity;

determining by one or more processors that a constraint is in place between the attribute of the first geometric entity and one or more attributes of a second geometric entity, wherein the constraint defines a relation between one or more attributes of the first geometric entity and one or more attributes of the second geometric entity;

determining by the one or more processors that the constraint is a one-way constraint including determining that attributes of the second geometric entity are not constrained by attributes of the first geometric entity;

determining that the attribute would, if changed according to the request, invalidate the constraint between the first geometry entity and the second geometric entity; and

based on determining that the attribute would, if changed according to the request, invalidate the constraint between the first geometry entity and the second geometric entity, restricting the requested change to the attribute of the first geometric entity.