Patent ID: 8706452

Claim:
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, an extension value corresponding to the start point, and a diameter for the pipe; determining an extension point, by the data processing system, according to the start point and the extension value; determining, by the data processing system, sample points between the extension point and destination point; building a graph, by the data processing system, including the sample points and the extension point and the destination points as nodes and a plurality of edges connecting the nodes, and including an edge between the start point and the extension point that is designated as collision-free; computing a plurality of paths, by the data processing system, through the graph between the extension point and the destination point; for each node in each 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 a path of the plurality of paths, then designating that path as a successful path; determining, by the data processing system, a shortest successful path of any designated successful paths, 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; processing the shortest successful path to remove at least one collinear point; and displaying the shortest successful path to a user by the data processing system.