用于管道和管的路径的无冲突CAD设计的系统和方法

摘要

一种用于在CAD系统中自动创建管道和管的无冲突路径的系统、方法和计算机程序产品。一种方法包括在数据处理系统中接收限定CAD环境中的管道的至少开始点和目的地点的输入，以及管道的直径。该方法还包括确定开始点和目的地点之间的采样点。该方法还包括构建包括作为节点的采样点和开始点和目的地点以及连接所述节点的多个边的图形。该方法还包括计算通过开始点和目的地点之间的图形的路径。该方法还包括对于路径中的每个节点测试连接到节点的每个边，以确定在CAD环境中沿着测试对象模型和背景模型几何构型之间的边是否存在冲突，并且从图形移除具有冲突的任何边。如果沿着路径的任何边不存在冲突，则将路径指定为成功的路径并且通过数据处理系统将成功路径显示给用户。

说明书

其他申请的交叉引用

本申请要求2008年6月26日提交的美国临时专利申请61/075,927的优先权，通过引用将其结合于此。

技术领域

本公开总体上涉及计算机辅助设计、制造和可视化系统，在此处被共同描述为CAD系统。

背景技术

CAD系统被用于设计、可视化和制造简单和复杂的系统。CAD系统允许用户在制造物理项（item）之前或代替制造物理项设计对象和系统的图形模型。

发明内容

所公开的实施例包括用于CAD系统中的管道（pipe）和管（tube）的无冲突（collision-free）路径的自动化创建的系统、方法和计算机程序产品。示例性方法包括在数据处理系统中接收限定针对CAD环境中的管道的开始点和目的地点（destination point）的输入以及管道的直径。该方法包括确定开始点和目的地点之间的采样点。该方法还包括构建图形，该图形包括作为节点的采样点和开始点和目的地点以及连接所述节点的多个边（edge）。该方法还包括计算穿过开始点和目的地点之间的图形的路径。该方法还包括，针对路径中的每个节点，测试连接到节点的每个边以确定在CAD环境中沿着测试对象模型和背景模型几何构型（geometry）之间的边是否存在冲突，并且从图形移除具有冲突的任何边。如果沿着路径的边不存在冲突，则将该路径指定为成功路径并且由该数据处理系统将所述成功路径显示给用户。

前述内容已经相当广泛地阐述了本公开的特征和技术优点，以使得本领域技术人员更好地理解下面的详细描述。在下文中将描述形成权利要求主题的本公开的附加特征和优点。本领域技术人员将认识到，他们可以容易地使用作为修改或设计用于实施本公开的相同目的的其他结构的基础而公开的概念和特定实施例。本领域技术人员还将认识到这样的等同构造不偏离本公开在其最广泛形式上的精神和范围。

在开始进行下面的详细描述之前，阐述遍及该专利文献所使用的某些词或短语的限定是有利的：术语“包括”和“包含”以及其派生词意味着包括但不限于；术语“或”是包括性的，意味着和/或；短语“与...相关联”和“与其相关联”以及其派生词可以意味着包括、被包括在内、与其交互、包含、被包含在内、连接到或与...连接、耦合到或与...耦合、可与...通信、与...协作、交错、并置、接近于、束缚于或与...密切相关、具有、具有...属性等等；并且术语“控制器”意味着控制至少一个操作的任何设备、系统或其部件，而不管这样的设备是以硬件、固件、软件或他们中的至少两个的某些组合来实施。应该注意，与任何特定控制器相关联的功能可以被局部地或远程地集中或者分散。遍及该专利文档提供了对某些词和短语的限定，并且本领域普通技术人员将会理解这样的限定在许多（如果不是大多数）实例中应用于这样限定的词和短语的先前和将来的使用。尽管某些术语可以包括各种各样的实施例，所附权利要求可以清楚地将这些术语限于特定实施例。

附图说明

为了更完全地理解本公开以及其优点，现在结合附图参考下面的描述，其中相似的编号指示相似的对象，并且其中：

图1描绘可以在其中实施所公开的系统和方法的实施例的数据处理系统的框图；

图2示出无冲突路径的示例；

图3A示出两个圆柱体之间的接合（joint）的可接受的自相交；

图3B示出无效的自相交（invalid self-intersection）；

图4A图示当两个对象边界（boundary）重叠时的干扰（interference）；

图4B图示当一个对象在另一个内部时的容纳（containment）；

图5描绘根据本公开实施例的过程；

图6示出向前扩展（forward extension）的示例；

图7示出具有其干扰球体（interfering sphere）表示和其无干扰圆柱体表示的示例限定点；

图8示出具有向前、向后或者向前和向后值的限定点的示例；

图9图示针对背景几何构型的限定点之间的冲突检查；

图10示出最短路径上的冲突检查的示例；以及

图11图示利用不同选项建模的管道的示例。

具体实施方式

下面讨论的图1至图11以及被用来描述在该专利文档中的本公开的原理的各种实施例仅以说明的方式并且无论如何不应该被解释成限制本公开的范围。本领域技术人员将会理解，可以在任何适当布置的设备中实施本公开的原理。将参考示例性非限制实施例来描述本申请的各种创新教导。

限定：下面是在本申请中使用的某些技术术语的通常意义的短的限定。（然而，本领域普通技术人员将会认识到上下文是否需要不同的意义。）可以在标准技术词典和杂志中找到附加限定。

面数据（Facet Data）：面数据被某些CAD和CAD数据可视化系统使用来存储或建模固体。面数据包括三角形群组（也被称为网格）。这些三角形被一起调适以使得这些面形成近似于固体的表面。

管道/管：术语管道和管通常在此处可交换地使用，并且一个术语的使用意图包括其他术语的使用。各种公开实施例将管道建模和处理为圆柱体链。最后建模的管道可以具有更详细模型，其包括建模管道或弯头（elbow）中的“弯曲（bend）”的圆角（fillet）曲线。下面的图以及特别地图10说明利用不同选项建模的管道的示例。在最简单的实施方式中所公开各种实施例将所有管道看作没有弯曲或弯头。

弯曲/接合：弯曲或接合是标记管道方向上的变化的位置。这些术语通常在此处可交换地使用。优选实施例将这些仅仅看作将管道的线接合到一起（端对端）的简单点，然而，在其他实施例中，客户或用户可以限定在这些位置处的过渡（transition）。过渡可以是管道中的弯曲，在该情况下管道是已使用弯曲机弯曲的单片管道材料。另一可能的过渡是通过弯头，它是插入管道区段（section）的端部上的单独配件（fitting）。

管道和管通常在CAD系统中被建模为端对端连接的线和弧的集合。CAD系统的用户通过限定各种属性（例如弯曲半径和管道材料）和限定这些曲线的点的位置来创建这些曲线。管道和管将一个项（或系统）连接到另一系统或项。项的示例可以包括三通管（tee）（用于限定分支）、泵或罐。

管道的开始和结束点由目的地项（例如罐上的入口）来限定。可以通过挑选现有的实体（例如行进通过隔板的弧中心）来指定某些中间限定点。必须在自由空间中限定其他中间限定点。在自由空间中限定点尤其困难，因为不存在参考几何构型并且用户必须“猜测”点的坐标。

此外，管道的始端和末端之间的障碍物需要用户限定附加点。避免障碍物，通常需要用户反复创建点直到他们具有限定不与障碍物干扰或冲突的管道的限定点集合为止。该过程会需要相当大的工作量，因为它需要用户重复地修改并检查管道路径。

所公开的实施例包括用于自动确定产生无冲突管道或管的通过自由空间的中间限定点集合的系统、方法和计算机程序产品。这些方法计算交互环境中的这些限定点，所用的时间量与模型的复杂性（即障碍物的数目）成比例。所公开的方法处理使用三维CAD系统中的面化（faceted）CAD数据所限定的障碍物。

图1描绘可以在其中实施所公开的系统和方法的实施例的数据处理系统的框图。所描绘的数据处理系统包括连接到二级高速缓存/桥接器（bridge）104的处理器102，所述二级高速缓存/桥接器104又连接到本地系统总线106。本地系统总线106可以是例如外围设备互连（PCI）架构总线。在所描绘的示例中还连接到本地系统总线的是主存储器108和图形适配器110。该图形适配器110可以连接到显示器111。

其他外围设备（例如局域网（LAN）/广域网/无线（例如WiFi）适配器112）还可以连接到本地系统总线106。扩展总线接口114将本地系统总线106连接到输入/输出（I/O）总线116。I/O总线116连接到键盘/鼠标适配器118、磁盘控制器120和I/O适配器122。磁盘控制器120可以连接到存储设备126，其可以是任何适合的机器可用或机器可读的存储介质，包括但不限于非易失性、硬编码类型的介质（例如只读存储器（ROM）或电可擦可编程只读存储器（EEPROM）、磁带存储设备）以及用户可记录类型的介质（例如软盘、硬盘驱动器和压缩盘只读存储器（CD－ROM）或数字多功能盘（DVD））以及其他已知的光、电或磁存储设备。

在所示示例中还连接到I/O总线116的是音频适配器124，扬声器（未示出）连接到该音频适配器124以用于播放声音。键盘/鼠标适配器118提供用于定点设备（未示出）的连接，所述定点设备例如鼠标、跟踪球、跟踪指示器等等。

本领域普通技术人员将会认识到在图1中描绘的硬件可以针对特定实施方式而改变。例如，其他外围设备（例如光盘驱动器等等）还可以另外在所描绘的硬件中使用或者代替所描绘的硬件来使用。仅为了解释目的而提供所描绘的示例，并且其不意味着暗示关于本公开的架构限制。

根据本公开的实施例的数据处理系统包括采用图形用户界面的操作系统。该操作系统允许同时在图形用户界面中呈现多个显示窗口，其中每个显示窗口为不同应用或相同应用的不同实例提供界面。图形用户界面中的光标可以由用户通过定点设备来操控。光标的位置可以被改变和/或诸如单击鼠标按钮之类的事件被生成以驱动期望响应。

各种商业操作系统（例如位于华盛顿雷蒙德的Microsoft公司的产品，Microsoft Windows^TM的版本）之一可以在经适当修改的情况下被采用。根据所描述的本公开来修改或创建操作系统。

LAN/WAN/无线适配器112可以连接到网络130（不是数据处理系统100的一部分），如本领域技术人员已知的那样其可以是任何公共或专用数据处理系统网络或网络的组合，包括因特网。数据处理系统100可以通过网络130与服务器系统140通信，所述服务器系统140也可以不是数据处理系统100的一部分，而是可以被实施为例如单独的数据处理系统100。

定义通过自由空间的管道和管是非常耗时的操作。造船业客户特别地花费大量时间来限定管道系统。高达船只的三分之一重量例如来自于管道系统。在严格限制的空间（例如引擎块）中，用户限定无冲突路径非常困难。所公开的实施例包括自动建造管道和管的无冲突路径的工具。

所公开的实施例包括用于为管道或管寻找无冲突路径的系统和方法，有时在此处被称为“快速路径（Quick Path）”。过程检测障碍物（在一些实施例中被建模为面化的几何构型），并且还在尝试最小化或满足某些设计约束的情况下避免这些障碍物。所公开的实施例由此创建用于管道或管的有效路径。在更广泛系统的背景中所得到的路径在全局上可能不是最优的，但是然后可以被用户或设计者修改，从而降低限定管道所需的总工作量。

在一些实施例中，快速路径使用两个主（primary）约束集合，所述集合驱动路径点的有效集合的确定。硬约束是快速路径保证不被所得到的路径所违反的约束。软约束是快速路径在寻找路径时尝试满足的约束，但是不保证他们将由所得到的路径满足。除约束之外，快速路径还尝试最小化所得到的管道中的接合的数目以及管道的总长度。

图2示出无冲突路径的示例。一个硬约束是无冲突路径，其中所得到的管道路径200将与障碍物（例如3D模型中的障碍物210）无冲突。快速路径将管道建模为具有相同直径的圆柱体链。圆柱体的直径包括由用户指定的材料的直径加上由用户限定的间隙值（clearance value）。所得到的路径将在这些圆柱体和3d模型之间没有冲突。内部固体是管道220的直径并且外部固体230是与间隙值结合的管道的直径。

另一硬约束是无自相交，以便所得到的路径将不与其自身相交，除了在链中接合每个圆柱体的接合位置处。图3A示出两个圆柱体之间的接合处的可接受的自相交310。图3B示出当确定路径点时快速路径不允许的自相交320，其是无效的自相交，不在接合处。

软约束包括：最小直长度（Minimum Straight Length），其是管道的每个直区段的最小长度；以及最大弯曲数目，其是所得到的管道中所允许的弯曲或接合的最大数目。

快速路径使用冲突检测过程来确保所得到的路径不与3D模型中的任何几何构型干扰冲突。冲突检测过程支持针对干扰和容纳（一个对象在另一个内部）的冲突检查。图4A图示当两个对象边界在410处重叠时的干扰；图4B图示当一个对象在另一个内部时的容纳。冲突检测系统应该支持针对面化CAD数据的圆柱体、球体和块的冲突检查。

在一些实施例中，用于冲突检测的数据结构和过程基于（based off of）本领域技术人员已知的OBB树算法，并且例如在S. Gottschalk, M. Lin, and D. Manocha. OBB-Tree: A hierarchical structure for rapid interference detection. Proc. of ACM Siggraph'96, pages 171-180, 1996中被描述，通过引用将其结合于此。OBB树存储包围几何构型的框的层级。由框包围的下层（underlying）几何构型可以是面化固体数据的群组或诸如球体和圆柱体之类的基本3D形状。各种快速路径实施例通过检查当前模型中的所有几何构型并且针对该几何构型建造OBB树结构来初始化冲突检测系统。模型中的几何构型被标记为“背景”几何构型。

冲突检测系统遍历每一块前景（foreground）几何构型，并且执行前景几何构型和每一块背景几何构型之间的冲突检查。检查器一找出该前景几何构型和一块背景几何构型之间的冲突，该检查器就停止前景几何构型的所有处理。

冲突检查的第一阶段遍历背景对象集合中的每一块几何构型，并且通过沿着OBB树的层级向下执行OBB－OBB干扰检查来寻找具有与前景几何构型干扰的可能性的那些对象。

第二阶段执行前景几何构型和没有被OBB－OBB干扰检查排除的任何背景几何构型之间的低等级干扰检查。可以使用如例如在本领域技术人员已知的、且通过引用将其结合于此的M. Held, ERIT - a collection of efficient and reliable intersection tests, Journal of Graphics Tools, VoI 2, issue 4:25-44 (1997)中所描述的圆柱体－圆柱体检查和圆柱体－三角形检查来实施低等级几何构型检查。根据例如本领域技术人员已知的、且通过引用将其结合于此的E. Karabassi, G. Papaioannou, and T. Theoharis, Intersection test for collision detection in particle systems, Journal of Graphics Tools, VoI 4, issue 1, pages 25-37, 1999实施球体－三角形检查。

下一步骤是确定前景几何构型对象是否在背景对象的内部，或者反之亦然。该步骤仅对不具有干扰的前景几何构型执行；即其没有冲突地通过冲突检查。容纳检查简单地从前景几何构型中的某任意点朝向某任意方向抽取平行射线（infinite ray）。然后检查该射线与潜在地包含前景几何构型的背景几何构型的相交。如果射线相交奇数次，则前景几何构型在背景几何构型内部。然后仅针对与前景几何构型相交的射线和背景几何构型上的任意位置处的点重复检查。该简单的检查基于公知的用于确定点是否在多边形内部的光线投射算法，例如在en.wikipedia.org/wiki/Point_in_polygon处提交时找到的“Point in Polygon”的Wikipedia文章中描述的那样。

图5描绘根据所公开的实施例的过程。

在快速路径过程中使用的某些技术类似于机器人技术应用中的路径规划的某些概念。存在已经针对机器人技术（例如在本领域技术人员已知的、且通过引用将其结合于此的S. M. LaVaIIe, Planning Algorithms, Cambridge University Press, Cambridge, U.K., 2006中描述的那些机器人技术）而研究的各种路径规划技术。

快速路径工具过程可以与用于机器人的路径寻找问题相比较。机器人必须在避免冲突的同时寻找其通过空间的路线。在一般情况下，机器人可以具有d维移动（例如对于具有接合的机器人为九）。在快速路径过程中，“机器人”可以被看作具有三维自由度的球体。

此处所使用的技术类似于落入被称为“概率路线图规划者（Probabilistic Roadmap Planner，PRM）”的机器人技术算法的子集的那些。在PRM系统中，模型被从连续空间转换成离散空间。大多数PRM规划者通过计算必须移动通过空间的对象（“机器人”）的各种定向和位置并且将这些定向和位置与移动连接来完成这一点。这形成了图形，其中图形的节点是机器人的定向和位置并且边是这些定向和位置之间的机器人的移动。根据图形原理的各种算法然后被用来计算从机器人的初始配置/位置到机器人的最终配置/位置的移动的有效集合。

可以使用例如在本领域技术人员已知的、且通过引用将其结合于此的R. Bohlin and L.E. Kavraki, A lazy PRM for single query path planning, Proc. of the IEEE Int. Conf. on Robotics and Automation, 2000中描述的惰性概率路线图(Lazy Probabilistic Roadmap)的修改和特殊化来实施快速路径过程的某些方面。惰性PRM算法尝试通过简单地避免冲突检查直到找到路径之后为止来最小化冲突检查（这是高代价的）的数目。惰性PRM首先构建机器人的随机配置的图形（具有那些配置之间的随机连接）。然后，惰性PRM计算路径，检查仅沿着该路径的冲突，并且从该路径移除产生冲突的任何配置。重复该过程直到发现无冲突路径为止。

惰性PRM的目标是避免冲突检查，因为它们在有效路径的计算中是最高代价的步骤。在复杂模型中，惰性PRM算法产生遍历处理过的图形的许多许多迭代。这将计算从冲突检测推向路径遍历。此处所述的快速路径过程可以使用若干次试探来避免该问题并且减少总计算时间。

如广泛描述的那样，所公开的过程包括这样的步骤，如在空间中采样某些点，其至少在所述点周围具有足够的空间来容纳等于管道直径的球体；连接这些点以形成图形；寻找通过图形从开始点到目标点的路径；检查沿着从开始到目标的路径的冲突；并且从图形移除与背景几何构型冲突的（路径上的）任何边。如果存在任何冲突，则该过程重复寻找新路径。

参考图5所描绘的过程500，快速路径过程的第一步骤是从用户接收输入或者从配置文件加载输入（步骤510）。该输入至少指定开始和目的地点，以及他们想包括在路径中的任何中间点，和管道的直径。在每个点处，用户还具有在每个点处指定向前和向后扩展的选项。扩展限定其中将不检查冲突的区域。这些扩展是有用的，因为他们阻止快速路径寻找与表面（例如容器（receptacle））的冲突，其可能干扰所得到的路径但是是可接受的干扰。

图6示出向前扩展的实例。在该图中，扩展610在路径620的开始处被限定，并且被用来避免位于开始点处的容器630处的干扰。

在各种实施例中，用户可以限定用于快速路径的下述数据。在至少一个实施方式中，以（所需的）标记的项必须由用户在执行过程的后续步骤之前指定。

（所需的）限定点：用户必须指定至少两个不重合点，但可以指定与期望的一样多的点。

扩展方向和向前/向后长度：用户可以可选地在任何限定点处指定这些。

（所需的）管道的材料或直径：管道的外直径被用来强制所得到的路径不具有冲突。

间隙：间隙限定必须是无冲突的管道的轴线周围的附加区域。

最小直长度和最大弯曲数目如上所述。

如果用户不针对限定点指定方向，则快速路径自动确定基于由用户选择的限定所述限定点的几何构型的扩展方向。例如，如果用户挑选一条线，则自动扩展方向是所述线的轴线。如果几何构型不具有轴线（或者点在自由空间中），则快速路径使用限定点和下一限定点（对于最后限定点而言是先前限定点）之间的方向。自动扩展使用为零的向前和向后值。

该过程中的下一步骤是确定通常在开始点和目的地点之间的采样点（步骤520），其然后可以被用作附加中间限定点。确定采样配置和定向被用于路径规划，并且采样的点影响所得到的路径，以及是否可以发现路径。存在可用于选择采样位置的各种采样方法。快速路径使用特别针对管道/管的创建而设计的若干新型采样策略。

对于快速路径，“机器人”被建模为球体。这减小仅针对3D空间中的点的采样（不考虑定向）。所发现的路径必须是无冲突的，以使得球体可以从开始限定点移动到末端限定点，而不会干扰背景几何构型。

优选地使用惰性PRM算法，该系统构建包括作为节点的采样点、开始点和目的地点和任何其他限定点以及连接所述节点的多个边的图形，该图形中采样点和接合这些采样点的边被假设成无冲突的。对于密集模型，这导致寻找图形、寻找冲突并且从图形移除边的巨大数目的迭代。快速路径通过确保所有采样点是无冲突来降低路径寻找迭代的数目。这种在前面的冲突检查大幅降低密集模型中的无效路径的数目。冲突检查非常快，因为针对面化数据针对球体的冲突检查是非常快的操作。

快速路径采样策略包括在四个阶段中构建空间中的无冲突采样球体的列表（其被存储为3D点）。

初始的点列表包括限定点。这些点被限定为无冲突的，因为在限定点处的球体将最有可能干扰现有模型。该干扰实际上是错误肯定（false positive）的，因为在该点处开始的最后管道或管将是圆柱体的盖子而不是球体。图7示出示例限定点以及其干扰球体表示710和其无干扰圆柱体表示720。

如果用户在限定点处限定向前或向后扩展值，该限定点由从限定点偏移用户沿着扩展方向指定的扩展距离的新点代替。快速路径将限定点和扩展点之间的圆柱体区段看作无冲突。

快速路径计算每一对输入限定点（或它们的代替扩展点）之间的路径，其通常是通过开始点和目的地点之间的图形。图8示出具有向前、向后或者向前和向后值的限定点的示例。在该示例中，用户挑选点A、B和C，并且在A和B处限定向前扩展值810，并且在B和C处限定向后扩展值820。快速路径将确定点A1和B1之间的路径830，以及点B2和C1之间的另一路径840。

修复（heal）点是使用若干不同试探所计算的点。这些试探限定模板或原型路径的集合，并且然后快速路径对沿着这些模板路径的点采样。快速路径使用上述每一对限定点以及相关联的扩展方向来计算每一个模板路径。

存在在各种实施例中使用的三种基本类型的模板路径：直（Direct）、相交和基本（Cardinal）。快速路径通过限定输入p1、p2（原点），v1、v2（扩展方向）偏移值（d）以及输入方法来计算这些路径中的每一个。每一个模板路径首先将沿着扩展方向的偏移值应用于每一个相应的输入点（o1＝p1＋d*v1，o2＝p2＋d*v2）。该方法然后确定哪个算法被用来计算偏移点之间的路径。返回的模板路径不包含任何重合点。

直模板路径简单地将偏移位置与直线接合。所有每个直路径包括p1、o1、o2和p2。

相交模板路径简单地寻找由（o1、v1）和（o2、v2）限定的两条无限线的相交点i1、i2。模板路径然后包括点p1、o1、i1、i2、o2和p2。如果在两条线之间不存在相交点，则快速路径丢弃该路径。相交点是限定线（o1、v1）和（o2、v2）之间的最短线的点。在提交时在本领域技术人员已知的、且通过引用将其结合于此的Paul Bourke, The shortest line between two lines in 3D, Local.wasp.uwa.edu.au/~pbourke/geometry/lineline3d/中描述用于限定此类点的一种示例性方法。

基本模板路径使用接合输入点的偏移位置的基本方向（X，Y，Z）来计算两个新位置。存在与这种类型的模板路径相关联的六个子方法，每个方法限定应用基本方向的特定次序。例如，子方法XYZ首先应用X方向，然后是Y，然后是Z。所计算的模板路径是p1、o1、c1、c2、o2和p2，其中在表1中限定c1和c2。

表1 用于基本模板路径的子方法

快速路径通过在不同的修复方法和子方法上循环来迭代地计算修复路径。对于每种方法，快速路径使用扩展矢量（v1，v2）、（－v1，v2）、（v1，－v2）和（v1，－v2）的组合来计算修复路径。对于每种组合，快速路径使用扩展值来计算修复路径，该扩展值等于p1和p2之间的距离（distance）乘以当前迭代数目（k）除以最大迭代数目（m）。算法2.1中的伪代码示出算法：

快速路径计算模板路径位置的轴向对准的边框，并且将冲突检查仅限制成与该边框相交或者由该边框包含的背景几何构型。当所有计算的路径将在边框内部时，该步骤降低针对检查冲突的背景几何构型的量。

快速路径对沿着由模板路径限定的每条线的固定数目的点（在当前实施方式中为100个点）采样。针对背景几何构型（作为球体）就冲突检查每个点，并且仅那些不没有干扰的点被保留。

网格点：在确定沿着模板路径的采样点之后，快速路径然后计算沿着以限定点为中心的3D网格的采样点。这些网格包含固定数目的采样点，并且基于由用于计算网格的采样点的数目的立方根来除的X、Y和Z方向上的最大范围使用delta（增量）偏移来计算这些网格。

此外，快速路径还存储针对修复路径点（在网格中具有XY、XZ和YZ平面）计算的每一模板路径线的相交处的采样点。

随机点：先前步骤计算大量的采样点。在先前步骤中的采样点是完全确定性的（相同的输入总是产生相同的采样点集合）。确定性的采样点限定非常简单的路径（沿着模板路径的直线，沿着网格平面的线），它们对于生成线性管道路径非常有用。然而，这些采样点可能不足以用于寻找非常密集或杂乱模型中的路径。如果点采样不足够密集，或者如果碰巧是障碍物以使得先前技术产生非常少的有效采样点，则返回的路径可能不是非常最优的，即它计算太复杂或太长的管道，或者路径可能根本就没被发现。随机化的采样方法以及为什么随机点在密集模型中产生更好的结果的原因是本领域技术人员已知的，并且例如在 N. M. Amato and Y. Wu., A randomized roadmap method for path and manipulation planning, IEEE Int. Conf. Robot. & Autom., pages 113-120, 1996中被描述，通过引用将其结合于此。

快速路径选择上面计算的边框内的大量随机点，并且针对框中的背景几何构型就冲突检查每个随机点。在各种实施例中，快速路径确保所得到的采样点列表具有至少2000个随机无冲突点。

再次参考图5的过程，系统然后将构建连接采样点的图形（步骤530）。快速路径使用若干试探来将图形数据结构中的采样点彼此接合。该图形必须被保持相对小以避免过多的存储器使用，并且必须非常适合于最短路径搜索。

快速路径首先尝试将每个采样点连接到最接近于它的其他采样点，每个采样点或者连接到k个最接近的点（其中在至少一个实施例中k＝5），或者连接到具有等于以采样点为中心的管道直径（加上间隙）的直径的球体内的所有点。快速路径将采样点连接到具有最大数目的点（k－最接近的，或者球体中）的点集合。这样近地将点连接到一起允许快速路径在确定管道路径时采用小增量的步长。本领域技术人员已知的用于寻找最接近的点（以及球体内的点）的一种适合的算法在提交时由D. Mount and S. Arya, ANN: A Library for Approximate Nearest Neighbor Searching, www.cs.umd.edu/~mount/ANN/描述，通过引用将其结合于此。

第二试探将每个采样点与至少j个随机采样点接合，其中在一些实施方式中j＝10。这些随机点尚未与采样点接合。这些随机连接允许快速路径采用大步长（寻找远离的采样点）并且潜在地以较小步长寻找目标点之间的路径。

然后快速路径将每一对限定点接合起来。如果在限定点之间不存在障碍物，则返回路径将简单地是接合限定点的线。添加限定点之间的边确保快速路径将找到该单个线而不用搜索整个图形。

快速路径创建的最后的边集合在修复点步骤中计算的采样点中的每一个与m个随机的其他修复点以及到每一个限定点之间，其中在某些实施方式中m＝20。这些额外的连接促进快速路径发现更接近在修复路径步骤中计算的模板路径的路径。

在步骤530处构建图形之后，快速路径检验附接到限定点的所有边（步骤540）。快速路径通过构建圆柱体来针对任何背景模型几何构型就冲突测试每个边，该圆柱体半径等于管道的半径加上在限定点和由边限定的其他点之间的间隙值。快速路径对附接到限定点的每个边执行该冲突检查以尝试寻找通过图形的至少一条路径。

如果附接到一个或多个限定点的所有边具有冲突，则在限定点之间不存在可能的无冲突路径。检查附接到限定点的所有边具有快速检测下述情况的优点，在该情况中用户已选择完全在包围的区域内的点（例如配件的中间，或者闭合的空间内部），通过迭代性地在后续步骤中寻找路径进行检测将花费非常长的时间。

图9示出根据所公开的实施例的冲突检查的示例。在该示例中，系统检查通常在背景几何构型框模型920内的第一限定点910到其他限定点之间的路径上的冲突。如所示出的那样，存在沿着路径940到限定点930的冲突（因为它与框920相交），以及到其他限定点的类似冲突。系统已找到沿着路径960到限定点950的有效（无冲突）路径，因为它通过框920中的孔970。

如果出自限定点的边没有一个是无冲突的（例如如果在图9的框920中没有孔970），则不可能存在路径，并且系统将这报告给用户并且停止所有进一步处理（步骤550）。附加优点是这降低快速路径可能检查的潜在无效路径的数目。

寻找图形中的路径：至少一些实施方式使用公知的A*算法来寻找通过图形的最短路径，如在提交时在 en.wikipedia.org/wiki/A*_search_algorithm中的Wikipedia entry for A* Search Algorithm中所描述的那样。在这种情况下，最短的路径不一定就是具有最短长度的路径，而是在满足尽可能多的软约束的同时尽可能短的路径。其他已知的算法适合于寻找最短的路径：Dijkstras算法，并且来自A*算法的其他变形（例如IDA*和SMA*）可以代替快速路径过程中的A*。

快速路径所使用的试探只是应用于路径的成本函数（下文中将会定义），其中假设路径中的最后节点直接连接到目标采样点。

对于给定路径的成本是下述各项的和：

· 当前路径长度除以两个限定点之间的距离并乘以任意加权值w1。

· 当前路径中的弯曲的数目除以所允许的最大弯曲数目。如果所允许的最大弯曲数目是零，则弯曲的数目被看作零。该值乘以另一任意加权值w2。

· 小于最小直长度的路径的线性区段的数目。这些线性区段可以包括路径中的多于一个点，如果在路径中存在共线点的话。该值乘以任意处罚因子（penalty factor）e1。

· 如上所述的路径中的自相交的数目。该值乘以任意处罚因子e2。

在各种实施例中，权重w1和w2必须总计小于或者等于1.0。这些权重确保，如果路径不违反硬约束（例如自相交），则路径的总成本将小于或等于1.0。最优路径是两个限定点之间的直线，因为它的成本为零。快速路径过程的至少一种实施方式使用w1＝w2＝0.5，这给出有助于降低路径长度和降低弯曲数目的相等权重。

在各种实施例中，误差因子e1和e2必须大于或等于1.0。这确保违反约束的路径具有大于1.0的成本。处罚越高，路径的成本就越高，并且对它的期望就越低。快速路径的至少一个实施方式是使用e1＝e2＝1.0。

该成本函数具有若干重要的特征。第一特征是该成本函数尝试最小化管道的总长度。较短的管道通常在生产和制造时较低代价。通过用“最优”管道（直线）的长度除以路径的长度来实现该长度的最小化。路径越长，该值就越小。因为成本函数从1.0减去该值，该值越小，路径的值就会越接近1.0。

除了最小化该长度之外，成本函数还尝试降低弯曲的数目。如果路径中弯曲的数目大于用户限定的最大弯曲数目，则该项将以变成大于1.0结束（其然后乘以加权因子w2），从而导致路径成本将潜在大于1.0。

有可能违反最大弯曲数目并且仍具有小于1.0的成本，然而，这是如上所述的快速路径算法的所接受的条件。

如果最小直长度违反和自相交的数目中的任一个都不为零，则它们将自动将路径成本推为超过1.0。这些在对那些约束的任何违反上都放上沉重的成本，并且降低快速路径将选择这些路径的可能性。此外，快速路径通过在碰到自相交的路径时跳过这样的路径来消除具有自相交的任何路径，从而成为图形中到达顶点的最短路径（快速路径采取第二最短等等）。

检查最短路径：一旦快速路径已发现最短路径，先前的步骤确保该路径在期望的限定点处开始和结束并且不具有自相交。如果先前步骤不能寻找路径（在步骤540处），则快速路径停止处理并且将此作为错误报告给用户（步骤550）。

快速路径构建3D圆柱体以表示最短路径中的每一条线。快速路径然后执行3D圆柱体的该链和包括其他对象模型的背景几何构型之间的冲突检查（步骤560）。具有冲突的边被标记为“无效”并且在路径寻找步骤中被忽略。不具有冲突的边被标记为“已检查”并且不会被冲突检查器再次检查。

在对最短路径的边执行冲突检查之后，快速路径执行另一冲突检查。第二冲突检查针对附接到快速路径在先前冲突检查中在其上碰到冲突的边的节点的所有边。该额外检查清除最短路径算法可以在后续最短路径搜索上找到的尽头（dead-end）路径。

如果节点在最短路径上并且在该节点处碰到冲突，则最短路径算法将在下一搜索上找到最短路径上的该节点是有可能的。额外的冲突检查将移除图形中靠近原始最短路径的许多无效路径（步骤570），这可以显著降低必须由快速路径检查的潜在最短路径的数目。

图10示出额外冲突检查的优点的示例。在该示例中，最短路径（实线）1010具有冲突。移除其他冲突边1020将防止最短路径算法向下穿过虚线的冲突边。在该附图中，最短路径被示出为实线；第二路径被示出为虚线。

如果最短路径中的任何边发生冲突，则快速路径在执行其所有冲突检查之后重新开始最短路径算法（返回到步骤540）。该过程继续直到快速路径或者找到没有冲突的路径或者最短路径算法不能找出任何路径为止。

快速路径过程的结果：快速路径将它碰到的任何错误报告给用户。在各种实施例中，仅存在报告给用户的两种错误条件：在限定点周围没有足够的自由空间以及在限定点之间不能找到路径。

系统可以执行用于确定短路径的单独过程（步骤580）。快速路径后处理无冲突路径以便移除任何共线点，将该路径指定为成功路径，并且创建所得到的路径的CAD表示以为管道或管建模（步骤590）。然后如果需要的话CAD系统中的用户可以修改管道的CAD表示，以便得到期望的管道模型。

快速路径通过减小用户限定管道或管所需的工作量解决了限定管道或管的问题。利用少量的工作量，用户可以得到与他们的输入约束（开始/结束点、间隙等等）相匹配的初始管或管道。在许多情况下，所生成的管道或管将是用户可接受的。如果管或管道不可接受，则用户可以使用现有的用于修改管道的CAD工具来编辑该管或管道。

图11图示利用不同选项建模的管道的示例。在该图中，利用缺省连接1110、具有弯曲1120的连接以及具有弯头1130的连接来建模管道。

通过引用结合的美国专利7,444,269描述了不同于快速路径的路径选择方法，因为其尝试寻找全局最优的管。该功能仅支持有限的障碍物（例如块）集合，并且需要用户输入这些块。如果存在大量障碍物的话，算法的运行时间会非常长。

本领域技术人员将会认识到存在各种路径规划算法，它们将被用来代替由上述优选快速路径过程所使用的惰性PRM算法。利用另一算法代替惰性PRM不一定会改变由快速路径实现的结果（即所得到的路径），但是将会改变该算法的运行时间。大多数PRM算法需要大量时间来构建初始图形，因为在接受图形中的每一个边之前，必须验证该边。

诸如在本领域技术人员已知并且通过参考结合于此的S. M. LaVaIIe, Rapidly-exploring random trees: A new tool for path planning. TR 98-11, Computer Science Dept., Iowa State Univ, Oct. 1998中所描述的算法之类的其他PRM算法实时构建线路图图形。这消除了在构建图形中的预先处罚（up-front penalty）。使用这种算法的结果通常很不适合于降低成本或处理约束。

本领域技术人员将会认识到存在可被分类为“强力”的用于寻找路径的其他方法。这些算法不会将问题分解成离散问题的解决方案，而是它们将问题留作针对解决方案而查遍连续空间。它们典型地需要通过一些措施来生成猜测路径（可能是随机的，可能是确定性的），看该路径是否冲突并且然后使用某一标准来重复以在每次迭代中修改该路径。例如某些实施方式可以使用遗传算法来修改过程的每个迭代中的测试路径（或多个路径）。其他实施方式可以限定单个猜测路径并且迭代性地修改该路径，从而评估每次迭代中的约束。这些变化有潜力寻找比上述优选快速路径过程更低成本的路径，但是它们通常需要针对小模型的许多迭代并且每个迭代需要大量的计算（成本的评估、路径的冲突检查、确定下一步骤）。

本领域技术人员将会认识到为了简单和清楚，适合于和本公开一起使用的所有数据处理系统的完全结构和操作在此处没有被描绘或描述。而是，仅描绘并描述了对本公开来说是唯一的或者对理解本公开来说是必须的许多数据处理系统。数据处理系统100的构造和操作的剩余部分可遵照本领域已知的任何各种当前实施方式和实践。

重点指出的是，尽管本公开包括全功能系统的上下文中的描述，但是本领域技术人员将会认识到本公开的机制的至少部分能够以包含在各种形式中的任何形式的机器可用、计算机可用或计算机可读介质中的指令形式分布，并且本公开同等地应用，而不管实际用于实行所述分布的指令或信号承载介质或存储介质的特定类型。机器可用/可读或计算机可用/可读介质的示例包括：非易失性硬编码类型的介质（例如只读存储器（ROM）或电可擦除可编程只读存储器（EEPROM），以及用户可记录类型的介质（例如软盘、硬盘驱动器和压缩盘只读存储器（CD－ROM）或数字多功能盘（DVD）。

尽管已详细描述了本公开的示例性实施例，但是本领域技术人员将会理解可以在不偏离本公开最宽泛形式的精神和范围的情况下完成本公开的各种变化、替换和改进。

本申请中的描述都不应该被看作暗示任何特定元素、步骤或功能是必须被包括在权利要求范围（仅由所允许的权利要求限定的专利主题的范围）中的基本元素。此外，这些权利要求都不意图调用35 USC§112的第六段，除非确切词“用于…的装置”后面是分词。