SYSTEM AND METHOD FOR COLLISION-FREE CAD DESIGN OF PIPE AND TUBE PATHS

• US 20090326876A1
• Filed: 06/24/2009
• Published: 12/31/2009
• Est. Priority Date: 06/26/2008
• Status: Active Grant

• Current Assignee: Siemens Product Lifecycle Management Software Incorporated (Siemens AG)
• Original Assignee: Siemens Product Lifecycle Management Software Incorporated (Siemens AG)
• Inventors: Miller, Justin H.
• Granted Patent: US 8,706,452 B2
• Time in Patent Office: Days
• US Class Current: 703/1
• CPC Class Codes: G06F 2111/06 Multi-objective optimisation, e.g. Pareto optimisation using simulated annealing [SA], ant colony algorithms or genetic algorithms [GA]
• CPC Class Codes: G06F 2113/14 Pipes
• CPC Class Codes: G06F 30/00 Computer-aided design [CAD]
• CPC Class Codes: G06F 30/18 Network design, e.g. design based on topological or interconnect aspects of utility systems, piping, heating ventilation air conditioning [HVAC] or cabling circuit design at the physical level G06F30/39; network planning tools for wireless communication networks H04W16/18

Abstract

A system, method, and computer program product for automated creation of collision-free paths for pipes and tubes in a CAD system. A method includes receiving inputs, in a data processing system, defining at least a start point and destination point for a pipe in a CAD environment, and a diameter for the pipe. The method includes determining sample points between the start point and destination point. The method also includes building a graph including the sample points and the start point and the destination points as nodes and a plurality of edges connecting the nodes. The method also includes computing a path through the graph between the start point and the destination point. The method also includes, for each node in the path, testing each edge connected to the node to determine if there is a collision along the edge between a test object model and a background model geometry in the CAD environment, and removing from the graph any edge that has a collision. If there is no collision along an edge of the path, then designating the path as a successful path and displaying the successful path to a user by the data processing system.

Claims

1. A method for automated creation of collision-free paths for pipes and tubes in a CAD system, comprising:

receiving inputs, in a data processing system, defining at least a start point and destination point for a pipe in a CAD environment, and a diameter for the pipe;

determining, by the data processing system, sample points between the start point and destination point;

building a graph, by the data processing system, including the sample points and the start point and the destination points as nodes and a plurality of edges connecting the nodes;

computing a path, by the data processing system, through the graph between the start point and the destination point;

for each node in the path, testing each edge connected to the node, by the data processing system, to determine if there is a collision along the edge between a test object model and a background model geometry in the CAD environment, and removing from the graph any edge that has a collision; and

if there is no collision along any edge of the path, then designating the path as a successful path and displaying the successful path to a user by the data processing system.

2. The method of claim 1, further comprising determining, by the data processing system, a shortest successful path.

3. The method of claim 2, wherein the shortest path is determined according to a length of the path and a number of bends in the path.

4. The method of claim 2, wherein the shortest path is determined according to a number of linear sections of the path that are less than a selected minimum straight length and a number of self-intersections in the path.

5. The method of claim 1, wherein the test object model is a sphere.

6. The method of claim 1, further comprising marking at least one edge as checked when the edge does not have a collision.

7. The method of claim 1, further comprising building a pipe comprising a plurality of three-dimensional cylinders along the computer path.

8. The method of claim 1, wherein the process is repeated at the computing step when there is no successful path.

9. A data processing system comprising a processor and accessibly memory, the date processing system configured for automated creation of collision-free paths for pipes and tubes in a CAD system by performing the steps of:

receiving inputs defining at least a start point and destination point for a pipe in a CAD environment, and a diameter for the pipe;

determining sample points between the start point and destination point;

building a graph including the sample points and the start point and the destination points as nodes and a plurality of edges connecting the nodes;

computing a path through the graph between the start point and the destination point;

for each node in the path, testing each edge connected to the node to determine if there is a collision along the edge between a test object model and a background model geometry in the CAD environment, and removing from the graph any edge that has a collision; and

if there is no collision along any edge of the path, then designating the path as a successful path and displaying the successful path to a user by the data processing system.

10. The data processing system of claim 9, the data processing system further configured to perform the step of determining a shortest successful path.

11. The data processing system of claim 10, wherein the shortest path is determined according to a length of the path and a number of bends in the path.

12. The data processing system of claim 10, wherein the shortest path is determined according to a number of linear sections of the path that are less than a selected minimum straight length and a number of self-intersections in the path.

13. The data processing system of claim 9, wherein the test object model is a sphere with a diameter at least as great as the received diameter of the pipe.

14. The data processing system of claim 9, the data processing system further configured to perform the step of marking at least one edge as checked when the edge does not have a collision.

15. The data processing system of claim 9, the data processing system further configured to perform the step of building a pipe comprising a plurality of three-dimensional cylinders along the computer path.

16. The data processing system of claim 9, wherein the data processing system repeats at the computing step when there is no successful path.

17. A computer program product comprising a tangible machine-readable medium encoded with computer-executable instructions that when executed cause a data processing system to perform the steps of:

receiving inputs defining at least a start point and destination point for a pipe in a CAD environment, and a diameter for the pipe;

determining sample points between the start point and destination point;

building a graph including the sample points and the start point and the destination points as nodes and a plurality of edges connecting the nodes;

computing a path through the graph between the start point and the destination point;

for each node in the path, testing each edge connected to the node to determine if there is a collision along the edge between a test object model and a background model geometry in the CAD environment, and removing from the graph any edge that has a collision; and

if there is no collision along any edge of the path, then designating the path as a successful path and displaying the successful path to a user by the data processing system.

18. The computer program product of claim 17, the tangible machine-readable medium further encoded with computer-executable instructions for determining a shortest successful path.

19. The computer program product of claim 18, wherein the shortest path is determined according to a length of the path and a number of bends in the path.

20. The computer program product of claim 18, wherein the shortest path is determined according to a number of linear sections of the path that are less than a selected minimum straight length and a number of self-intersections in the path.

21. The computer program product of claim 17, wherein the test object model is a sphere with a diameter at least as great as the received diameter of the pipe.

22. The computer program product of claim 17, the tangible machine-readable medium further encoded with computer-executable instructions for marking at least one edge as checked when the edge does not have a collision.

23. The computer program product of claim 17, the tangible machine-readable medium further encoded with computer-executable instructions for building a pipe comprising a plurality of three-dimensional cylinders along the computer path.

24. The computer program product of claim 17, wherein the data processing system repeats at the computing step when there is no successful path.