Modeled object updating

• US 8,983,805 B2
• Filed: 12/14/2011
• Issued: 03/17/2015
• Est. Priority Date: 12/30/2010
• Status: Active Grant

• Current Assignee: Dassault Systemes SA
• Original Assignee: Dassault Systemes SA
• Inventors: Houdouin, Jean-Michel, Janvier, Jean-Baptiste, Morawska, Jadwiga Maria, Rameau, Jean-Franois
• Primary Examiner(s): Shah, Kamini S
• Assistant Examiner(s): OCHOA, JUAN CARLOS
• Application Number:
  US13/325,885
• Publication Number:
  US 20120173212A1
• Time in Patent Office: 1,189 Days
• Field of Search: 703/2, 703/1, 345/629
• US Class Current: 703/1
• CPC Class Codes: G06F 2111/02 CAD in a network environment, e.g. collaborative CAD or distributed simulation
• CPC Class Codes: G06F 30/00 Computer-aided design [CAD]
• CPC Class Codes: G06T 17/10 Constructive solid geometry [CSG] using solid primitives, e.g. cylinders, cubes
• CPC Class Codes: G06T 19/20 Editing of 3D images, e.g. changing shapes or colours, aligning objects or positioning parts
• CPC Class Codes: G06T 2219/2021 Shape modification

Abstract

Provided is a computer-implemented method for updating a 3D model. The method comprises providing an operation undergone by the 3D model, an old input graph of the 3D model before undergoing the operation, an old output graph of the 3D model corresponding to an application of the operation to the old input graph, and a new input graph of the operation. The new input graph is generated as a result of a modification of the 3D model. The method also comprises computing a double push-out rewriting rule that specifies a part of the old input graph to be replaced, a part of the new input graph to replace the part of the old input graph. The rewriting rule also specifies an interface which is a part common to the part of the old input graph, the part of the new input graph, and the old output graph. The method further comprises applying the rewriting rule directly on the old output graph. This transforms the old output graph to a new output graph representing an updated 3D model of the real world object. The method is an improvement to updating a 3D model in a CAD system.

Claims

1. A computer-implemented method for updating a 3D model, the method comprising:

by a computer device with a processor, associated memory, and a graphical user interface, the processor;

storing in the associated memory, a 3D model, said storing includes storing a history of the 3D model having undergone one or more operations and graphs linked to different points of the history;

retrieving from the associated memory, at least two graphs of the stored graphs linked to the different points of the history, including;

an old input graph of the 3D model before undergoing an operation of the one or more operations, and

an old output graph of the 3D model corresponding to an application of the operation to the old input graph;

generating a new input graph of the operation, wherein the new input graph is generated as a result of a modification of the 3D model, the modification being requested by a user via the graphical user interface;

computing a double push-out rewriting rule that specifies;

(i) a part of the old input graph to be replaced, (ii) a part of the new input graph to replace the part of the old input graph, and (iii) an interface which is a part common to the part of the old input graph, the part of the new input graph, and the old output graph, the rewriting rule corresponding to logical operations which are computed based on the old input graph, the old output graph, and the new input graph; and

applying the rewriting rule directly on the old output graph, such that the old output graph is transformed to a new output graph that represents an updated state of the 3D model as updated by the modification.

2. The method of claim 1, wherein the method further comprises:

(a) computing a second rewriting rule that specifies;

(i) a second part of the old input graph to be replaced, (ii) a part of the old output graph to replace the second part of the old input graph, and (iii) a second interface which is a part common to the second part of the old input graph and the part of the old output graph, the second rewriting rule corresponding to logical operations which are computed based on the old input graph and the old output graph, and

(b) testing that the rewriting rule and the second rewriting rule are commutative before applying the rewriting rule to the old output graph.

3. The method of claim 2, wherein the testing is performed by comparing a first intersection between the part of the old input graph and the second part of the old input graph to a second intersection between the interface and the second interface, the rewriting rule and the second rewriting rule being commutative when the first and second intersections are equal.

4. The method of claim 1, wherein nodes of the old input graph, of the new input graph, and of the old output graph point to geometric data.

5. The method of claim 4, wherein the old input graph, the new input graph, and the old output graph are at least sub-graphs of boundary-representation graphs.

6. The method of claim 5, wherein the old input graph, the new input graph, and the old output graph are face-edge graphs or edge-vertex sub-graphs of boundary-representation graphs.

7. The method of claim 6, wherein the old input graph, the new input graph, and the old output graph are edge-vertex sub-graphs of boundary-representation graphs, and the method further comprises, prior to applying the rewriting rule:

retrieving from the associated memory,

an old face-edge input graph of the 3D model before undergoing the operation, the old face-edge input graph being a sub-graph of the boundary-representation graph of which the old input graph is a sub-graph,

an old face-edge output graph of the 3D model corresponding to an application of the operation to the old face-edge input graph, the old face-edge output graph being a sub-graph of the boundary-representation graph of which the old output graph is a sub-graph, and

a new face-edge input graph of the 3D model undergoing the operation, the new face-edge input graph being a sub-graph of the boundary-representation graph of which the new input graph is a sub-graph;

computing a face-edge rewriting rule that specifies a part of the old face-edge input graph to be replaced, a part of the new face-edge input graph to replace the specified part of the old face-edge input graph, and a face-edge interface which is a part common to the specified part of the old face-edge input graph, the specified part of the new face-edge input graph, and the old face-edge output graph, the face-edge rewriting rule corresponding to logical operations which are computed based on the old face-edge input graph, the old face-edge output graph, and the new face-edge input graph;

computing a second face-edge rewriting rule that specifies a second part of the old face-edge input graph to be replaced, a part of the old face-edge output graph to replace the second part of the old face-edge input graph, and a second face-edge interface which is a part common to the second part of the old face-edge input graph and the part of the old face-edge output graph, the second face-edge rewriting rule corresponding to logical operations which are computed based on the old face-edge input graph and the old face-edge output graph; and

testing that the face-edge rewriting rule and the second face-edge rewriting rule are not commutative.

8. The method of claim 2, wherein the method further comprises testing for 3D compatibility between a volume corresponding to the part of the new input graph and a volume corresponding to the part of the old output graph.

9. The method of claim 1, wherein the operation is a filleting or a rounding operation.

10. The method of claim 1, wherein the steps of retrieving graphs, including the old input graph and the old output graph, generating the new input graph, and computing the rewriting rule are iterated over historical operations of the 3D model, wherein the operation of each iteration being a respective historical operation.

11. A history-based computer-aided design system comprising:

a) a computer memory holding a database storing a 3D model, the database containing;

a history of the 3D model having undergone one or more operations, and

graphs linked to different points of the history;

b) a processor communicatively coupled to the computer memory and configured to retrieve from the database, at least two graphs of the stored graphs linked to different points of the history including;

an old input graph of the 3D model before undergoing an operation of the one or more operations, and

an old output graph of the 3D model corresponding to an application of the operation to the old input graph, and

c) a graphical user interface operatively coupled to the processor, wherein the processor is further configured to;

allow generation of a new input graph of the operation, wherein the new input graph is generated as a result of a modification of the 3D model, the modification being requested by a user via the graphical user interface;

compute a double push-out rewriting rule that specifies;

(i) a part of the old input graph to be replaced, (ii) a part of the new input graph to replace the part of the old input graph, and (iii) an interface which is a part common to the part of the old input graph, the part of the new input graph, and the old output graph, the rewriting rule corresponding to logical operations which are computed based on the old input graph, the old output graph, and the new input graph, and

apply the rewriting rule directly on the old output graph, such that the old output graph is transformed to a new output graph and represents the 3D model as updated by the modification.

12. A non-transitory computer readable storage medium comprising:

a computer memory device having recorded thereon a computer program comprising instructions for execution by a computer, the computer when executing the instructions responsively updates a 3D model,

wherein the instructions comprise;

storing the 3D model in associated memory of a CAD system, said storing includes storing a history of the 3D model having undergone one or more operations and graphs linked to different points of the history;

retrieving from the associated memory, at least two graphs of the stored graphs linked to the different points of the history, including;

an old input graph of the 3D model before undergoing an operation of the one or more operations, and

an old output graph of the 3D model corresponding to an application of the operation to the old input graph;

generating a new input graph of the operation, wherein the new input graph is generated as a result of a modification of the 3D model, the modification being requested by a user via a graphical user interface;

computing a double push-out rewriting rule that specifies (i) a part of the old input graph to be replaced, (ii) a part of the new input graph to replace the part of the old input graph, and (iii) an interface which is a part common to the part of the old input graph, the part of the new input graph, and the old output graph, the rewriting rule corresponding to logical operations which are computed based on the old input graph, the old output graph, and the new input graph; and

applying the rewriting rule directly on the old output graph, resulting in transforming the old output graph to a new output graph representing an updated state of the 3D model as updated by the modification.