在实际工程中，线缆通常用于连接电气设备、传输各种信号能源，被广泛应用于航空、航天和船舶等领域，所以在实际工程中线缆的布线、后期维护等工作成为大型机电产品研发过程中的重要环节^[1]。在数字化虚拟三维线缆布线过程中，线缆具有柔性可变形特性，并且可以任意移动，常与周围的物体(刚性结构件、管路和线缆等)发生干涉,所以常常造成线缆外皮磨损等问题，严重影响了产品的可靠性^[2]，并且为后续的实际线缆布线参考造成了很大影响。为了保证布线的合理性和正确性，对线缆进行干涉检测是十分有必要的一项工作。 对虚拟三维线缆进行干涉检测必须满足准确性和实时性的要求，准确快速的线缆干涉检测算法对于提升线缆的敷设质量具有重要意义。

目前，在三维模型干涉检测领域国内外学者做了很多重要的工作，并且提出了很多重要的干涉检测算法，比如层次包围盒法和空间分割法等干涉检测算法^[3]，但这类算法研究更多地是针对刚性结构件而展开的相关研究。目前在三维柔性物体的干涉检测方面的研究相对于刚性物体研究较少，且研究主要体现在二维层面的干涉检测领域^[4]和一些实验仿真验证，对于虚拟三维线缆这样的三维变形体的干涉检测研究成果不多。Bertail等^[5]对Cosserat模型采用分段螺旋线的方法进行离散化表示，但由于线缆形变复杂且长度较长，所以处理线缆时计算量较大。Ritchie等^[6]使用沉浸式虚拟现实技术解决线束的设计和敷设问题,但在描述线缆时,采用空间点间连线构造线缆,线缆逼真度不够。李蕴奇^[7]提出了一种基于可变形物体的检测算法，算法应用蚁群算法优化蛇形轮廓物体并将蛇形轮廓模型应用于固定方向凸包包围盒的更新过程中,提高了干涉检测效率。Hergenrother等^[8]将一定长度的线缆模型构建为许多相同长度的圆柱体，并采用球形结点方式将相邻的圆柱体连接起来，在结点上设置弹性能量，以能量最低来判断线缆是否发生形变。黄劲等^[9]提出一种基于大步长优化框架下的快速接触检测和响应算法，采用该算法可以以较低的内存开销来进行线缆检测，但需要采用一系列的数学方法来避免可能的粘连抖动问题。Shang等^[10]针对机电复杂产品提出了一种基于框架的线缆创建和布线模。Zhuo等^[11]提出了采用等效电缆束的方式对复杂线缆进行建模表示。谢世富等^[1]建立质点-弹簧模型，提出了线缆分层精确碰撞检测算法，但其实质仍然是对线缆采用了包围盒算法。

上述研究虽然对线缆干涉检测取得了一定成果，但均存在一定程度的不足。为满足工程实际的需要，针对柔性线缆采用面片方式表达复杂和难以用传统的包围盒法进行检测的特点，本文基于CREO线缆和结构件的几何特征提出了一种基于CREO三维柔性线缆干涉检测算法。算法首先根据已布线完成的三维线缆模型建立线缆中心线动态离散点模型，并获取结构件模型的空间位置关系，然后分析线缆动态离散点模型空间的几何特性；根据线缆动态离散点模型和结构件几何特征信息，判断线缆、结构件模型之间的空间位置关系，以实现虚拟三维线缆快速准确的干涉检测。

1 线缆与线缆干涉检测算法 1.1 线缆离散表示

在CREO中，三维线缆采用样条曲线方法构造线缆母线，而后附加曲面片材质形成线缆实体。由于线缆具有柔软可变形特性，并且线缆形状较不规则^[12]，所以传统的包围盒算法一般不适用于线缆模型。本文提出将线缆用空间坐标进行离散表达。线缆在几何上通常可抽象为等截面可变形圆柱体,且圆柱体的中心线在理论上可以无限延伸，所以线缆的中心线的变化形式也就是线缆的变化形式。

对线缆的中心线模型进行动态离散表示，设离散距离为l，取离散间距l=2r(r为待检测线缆的半径)。假定线缆长度为s，则离散点个数为n=s/l。离散点为空间坐标，表示为p(x,y,z)。将各离散点按布线起始点到终止点顺序编号为 p₁,p₂,p₃,…,p_n(n为整数)。

三维线缆模型可以随意弯曲变形，但由于基于线缆中心线的离散点也会跟随线缆移动而移动变化，所以基于线缆中心线的离散模型可以很好地表示三维线缆的变化。基于线缆中心线动态离散模型表示如图 1所示。图 2(a)为三维线缆模型，图 2(b)为线缆中心线模型。

1.2 空间坐标转换

在虚拟装配环境中，线缆作为实体特征占据了其自身的空间位置，由于线缆具有自身的坐标参考系，所以需要将线缆自身坐标系转换为虚拟装配坐标系。

在CREO三维模型中，由于模型的坐标系一般用三维坐标来描述，所以坐标系中的位置坐标一般用Double vector^[13]来表达。一般三阶矩阵可以用来表达坐标系与坐标系之间的转换，但在计算机图形学中通常会涉及到坐标系之间的平移和缩放，所以通常用4阶矩阵来进行三维模型坐标系的转换，变换矩阵可表示为

$X=\left| \begin{matrix} {{x}_{11}} & {{x}_{12}} & {{x}_{13}} & {{x}_{14}} \\ {{x}_{21}} & {{x}_{22}} & {{x}_{23}} & {{x}_{24}} \\ {{x}_{31}} & {{x}_{32}} & {{x}_{33}} & {{x}_{34}} \\ {{x}_{41}} & {{x}_{42}} & {{x}_{43}} & {{x}_{44}} \\ \end{matrix} \right|$

(1)

在计算机图形表达中，三维齐次坐标(x,y,1)可以用来表示平面空间点p(x,y)。同样，在进行三维空间中，立体空间点p(x,y,z)可以用四维齐次坐标(x,y,z,1)来表达。立体空间点的变换表示为p*=p×T。式中T为三维图形变换矩阵。变换矩阵T为4×4方阵，即

$T=\left| \begin{matrix} {{t}_{11}} & {{t}_{12}} & {{t}_{13}} & {{t}_{14}} \\ {{t}_{21}} & {{t}_{22}} & {{t}_{23}} & {{t}_{24}} \\ {{t}_{31}} & {{t}_{32}} & {{t}_{33}} & {{t}_{34}} \\ {{t}_{41}} & {{t}_{42}} & {{t}_{43}} & {{t}_{44}} \\ \end{matrix} \right|$

(2)

如图 3所示，在虚拟装配坐标系O_xyz中，Θ的坐标为(Θ_x,Θ_y,Θ_z)，Θ_u为单位向量(u_x,u_y,u_z)，Θ_v为单位向量(v_x,v_y,v_z)，Θ_w为单位向量(w_x,w_y,w_z)，因为两个坐标系不统一，所以需要进行坐标系转换，线缆坐标系Θ_uvw和虚拟装配坐标系O_xyz之间的步骤如下：首先平移使Θ落于原点O，变换为T(-Θ_x,-Θ_y,-Θ_z)，之后绕x轴旋转角度α，使w轴落于xOz平面，旋转变换为R_x(α)；其次绕y轴旋转角度β，使w轴与z轴同向且重合，然后旋转变化为R_y(β)；最后绕z轴旋转角度γ，使u轴和x轴同向且重合，旋转变换为R_z(γ)；则变换矩阵为^[14]

$\begin{array}{*{35}{l}} {{M}_{uvw\to xyz}}={{R}_{z}}\left( \gamma \right)\cdot {{R}_{y}}\left( \beta \right)\cdot {{R}_{x}}\left( \alpha \right)\cdot \\ T\left( -{{\Theta }_{x}},-{{\Theta }_{y}},-{{\Theta }_{z}} \right) \\ \end{array}$

(3)

令R=R_z(γ)·R_y(β)·R_x(α)，则

${{M}_{uvw\to xyz}}=R\cdot T(-{{\Theta }_{x}},-{{\Theta }_{y}},-{{\Theta }_{z}})$

(4)

即

${{M}_{uvw\to xyz}}=\left| \begin{matrix} {{u}_{x}} & {{u}_{y}} & {{u}_{z}} & 0 \\ {{v}_{x}} & {{v}_{y}} & {{v}_{z}} & 0 \\ {{w}_{x}} & {{w}_{y}} & {{w}_{z}} & 0 \\ 0 & 0 & 0 & 1 \\ \end{matrix} \right|\cdot \left| \begin{matrix} 1 & 0 & 0 & -{{\Theta }_{x}} \\ 0 & 1 & 0 & -{{\Theta }_{y}} \\ 0 & 0 & 1 & -{{\Theta }_{z}} \\ 0 & 0 & {} & 1 \\ \end{matrix} \right|$

(5)

式(3~5)可求出从坐标系Θ_uvw到坐标系O_xyz的变换矩阵，其中(Θ_x,Θ_y,Θ_z)为模型在线缆坐标系中的坐标，(α,β,γ)为模型在线缆坐标系中的方位^[15]，M_uvw→xyz为线缆坐标系到装配坐标系的变换矩阵。

1.3 基于几何特征的线缆自干涉算法

与三维线缆模型相比，常规几何特征不会产生形变，模型外观也不会发生大的改变，而在三维线缆布线过程中，三维线缆往往会根据实际需要不断改变线缆位置和外观形状。常规几何特征一般仅有自身的移动和旋转发生的位置变动，而线缆除了会有线缆本身的移动和旋转，还存在着柔性物体所特有的扭曲变形、线缆局部弯曲等多种情况。常规几何特征一般具有规则的几何外观，而三维线缆外观不规则，不适合传统的干涉检测算法。三维线缆在CREO平台内不能单独打开编辑修改，常规几何特征则可以进行任意的编辑修改。

在实际布线过程中，线缆自身干涉并不常见,本文提出一种线缆自干涉检测方法。为了检测线缆的自身干涉，首先将线缆自身按照前文所述的线缆中心线动态离散方法进行表示，为了保证线缆干涉检测的准确性和可操作性，将离散间距l设置为线缆直径即l=2r，这样可保证在没有干涉产生的情况下，所有离散点之间的距离均不小于线缆直径，从而避免了误判干涉发生的情况，然后对线缆自身的离散点进行遍历。自线缆起点至终点进行逐一遍历，获取离散点的空间位置信息。计算各个离散点之间的空间距离，因为相邻离散点之间的距离初始化设置为检测线缆直径，所以不存在两个相邻离散点之间的距离小于检测线缆直径的情况。不同离散点之间的距离为

$d=\sqrt{{{(x-{{x}_{b}})}^{2}}+{{(y-{{y}_{b}})}^{2}}+{{(z-{{z}_{b}})}^{2}}}$

(6)

空间坐标(x_b,y_b,z_b)为相邻离散点的空间位置坐标，若检测完所有离散点后发现存在d小于检测线缆直径的情况，则可以直接确定线缆发生自干涉,如图 4所示。

若均未发现干涉情况(因为可能存在进行判断的两个离散点的连线不垂直于该离散点所在线缆切线方向的情况，在此种情况下虽然检测的d大于检测线缆直径的情况，但仍有可能发生线缆干涉(如图 5所示)。进行下一步检测，提取相邻离散点之间的中点坐标为

$\left( \frac{{{x}_{m}}+{{x}_{n}}2}{2},\frac{{{y}_{m}}+{{y}_{n}}}{2},\frac{{{z}_{m}}+{{z}_{n}}}{2} \right)$

(7)

式中空间坐标(x_m,y_m,z_m)和(x_n,y_n,z_n)分别为除待判断离散点之外的两个相邻离散点。

令

${{x}_{c}}=\frac{{{x}_{m}}+{{x}_{n}}}{2},{{y}_{c}}=\frac{{{y}_{m}}+{{y}_{n}}}{2},{{z}_{c}}=\frac{{{z}_{m}}+{{z}_{n}}}{2}~$

(8)

计算待判断离散点与中点坐标距离

$d=\sqrt{{{(x-{{x}_{c}})}^{2}}+{{(y-{{y}_{c}})}^{2}}+{{(z-{{z}_{c}})}^{2}}}$

(9)

依次计算出全部距离，若d小于检测线缆直径则说明线缆发生自干涉，否则说明线缆没有发生自干涉。虽然待检测的离散点与两个相邻离散点中点之间的连线并不一定垂直于两个相邻离散点的连线，但因为离散间距和线缆直径均较小，故误差可忽略不计，如图 6所示。线缆自干涉算法基本算法流程如图 7所示。

1.4 基于几何特征的非自身线缆干涉算法

在实际工程布线过程中，线缆之间非常容易发生干涉，其中最容易出现线缆与线缆之间交叉走线的情况，特别是在敷设线缆较密集的地方，相互干涉的线缆往往很难通过肉眼检查出来，只能一根根排查。对于线缆与线缆之间的干涉检测，可采用的比较精确的检测方法是对构成线缆的面片体进行干涉判断，但由于一条完整线缆由许多面片体组成，且面片体之间干涉检测需要相关面片体的矢量信息，计算组成线缆面片体的矢量较复杂，所以一般不采用此类方法^[16]。本文根据三维线缆模型的几何特征，提出了一种基于三维线缆几何特征的检测方法。

对线缆进行中心线动态离散表示时，为了控制线缆干涉检测精度，将离散间距设置为两线缆半径之和。线缆与线缆干涉检测方法如下。首先对两根待检测线缆进行线缆中心线动态离散表达，离散点分别表示为p_1i={p₁₁,p₁₂,p₁₃,…,p_1n}(i,n为整数)和p_2j={p₂₁,p₂₂,p₂₃,…,p_2n}(j,n为整数)，提取两根待检测线缆的半径分别为r₁和r₂；计算两根线缆中心线之间的距离，取第1根线缆的第1个线缆中心线离散点p₁₁(x₁,y₁,z₁)作为被检测点，再取第2根线缆的第1个线缆中心线离散点p₂₁(x₂,y₂,z₂)作为检测点，计算两个离散点之间的距离。设p₁₁和p₂₁之间距离为d₁，则

${{d}_{1}}=\sqrt{{{({{x}_{1}}-{{x}_{2}})}^{2}}+{{({{y}_{1}}-{{y}_{2}})}^{2}}+{{({{z}_{1}}-{{z}_{2}})}^{2}}}$

(10)

下面依次计算p₁₁和p₂₂,p₂₃,p₂₄,…,p_2j之间的距离d₂,d₃,d₄,…,d_j，记D₁={d₁,d₂,d₃,…,d_n}(n=j)。同理分别计算p₁₂和p₂₁,p₂₂,p₂₃,…,p_2j，p₁₃和p₂₁,p₂₂,p₂₃,…,p_2j之间的距离，直至p_1i和p₂₁,p₂₂,p₂₃,…,p_2j之间的距离全部计算完毕，且分别记为

$\begin{align} & {{D}_{2}}=\{{{d}_{1}},{{d}_{2}},{{d}_{3}},\ldots ,{{d}_{n}}\} \\ & {{D}_{3}}=\{{{d}_{1}},{{d}_{2}},{{d}_{3}},\ldots ,{{d}_{n}}\} \\ & \vdots \\ & {{D}_{i}}=\{{{d}_{1}},{{d}_{2}},{{d}_{3}},\ldots ,{{d}_{n}}\} \\ \end{align}$

(11)

求出所有距离中最短距离d_i，取d_i作为判断依据，如果d_i≥r₁+r₂，则未发生干涉(见图 8)；否则，两根线缆发生干涉(见图 9)。重复此过程直至检测完所有线缆。图 10为线缆与线缆干涉判断流程图。

2 线缆与刚性结构件干涉检测算法

在三维模型中刚性结构件一般可以采用包围盒算法进行处理，但无论是典型包围盒算法中的轴向层次包围盒算法(Aligned axis bounding box，AABB)、方向层次包围盒算法(Oriented bounding box，OBB)，还是固定方向凸包算法(Fixed directions hulls，FHD)，都存在简单性与紧密性之间的矛盾^[3]。尤其是在实体结构件造型比较复杂时，包围盒的紧密性会大大下降，从而影响干涉检测的精度。本文根据刚性结构件三维模型在计算机中表达的特性，针对线缆和刚性结构件干涉检测提出了针对线缆和结构件几何特征的检测算法。

因为电气结构件绝大多数都是由规则的几何体构成，故在对结构件进行检测时主要以规则结构件为主，对于结构件中出现的曲面，则采用CREO/TOOLKIT提供的计算空间位置与CREO内核中的曲面距离的函数计算空间位置与曲面之间的最小距离，若计算出的最小距离小于线缆直径，则线缆与该结构件发生干涉；否则，线缆与该结构件没有发生干涉。

三维线缆与结构件干涉检测方法如下。该方法首先获取结构零件，对结构零件进行几何属性分析，获取结构件的空间位置数据和实体面数据。如图 11(a)所示，设模型的面组合L={M_i|i=1,2,…,n}，获取模型构成面的单位法向量组合F={N_j=(x,y,z)|j=1,2,…,n}。图 11(b)中模型包含6个面，其中A面包含一个轮廓和4条边：边E1为面A和面B的交线，也是轮廓C1和C2的公共部分。

其次将线缆中心线以空间坐标点的形式离散表示

$P=\left\{ {{p}_{k}}=\left( x,y,z \right)|k=1,2,\ldots ,n \right\}$

(12)

首先判断线缆中心线离散点是否被包含于结构件中，即计算离散点的空间坐标是否包含于结构件所占的空间内。如果离散点被包含于结构件内，则该线缆一定和结构件发生干涉。如果离散点不被包含于结构件内(见图 12(a))，则任意获取被测面内一点B(x_b,y_b,z_b)，构建空间向量

$B{{P}_{k}}=(x-{{x}_{b}},y-{{y}_{b}},z-{{z}_{b}})$

(13)

计算离散点与结构件被测面之间的距离

$d=\left| B{{P}_{k}}\cdot {{N}_{j}} \right|$

(14)

如果距离d小于线缆半径r，则线缆和结构件在该位置处发生部分嵌入，可以判断线缆和结构件在此处发生干涉(见图 12(b))。

3 实例验证

算法的验证硬件平台为配备有Core7 Elite 8380 3.40 GHz 处理器，4 GB 内存的惠普台式主机。在硬件平台上应用Visual Studio 2010编译工具和CREO软件，采用C++语言和TOOLKIT工具^[13]进行三维线缆干涉检测试验。在试验中，首先在CREO软件中导入已完成布线的CAD模型,对CAD模型进行干涉检测验证，发生干涉的线缆和结构件加亮显示。实例验证表明，本文所提出的线缆干涉检测算法可以很好满足线缆干涉检测的准确性和快速性要求。图 13为线缆干涉验证实例。表 1为实例验证测试结果,其中复杂程度为简单的线缆数量为百根以下，复杂程度为复杂的线缆数量为百根以上，结构件数量为两百以上。

通过实例验证可以得知，在线缆和结构件模型均简单的情况下，计算时间很短，运行速度较快，如表 1中算例(a~d)所示。在线缆和结构件较复杂的情况下，因要处理大量的运算和模型分析，计算时间变长。在结构件模型组成相似的情况下,线缆数量的差异对线缆与线缆之间的干涉检查所花费的时间影响不大，如表 1中算例(e~h)所示。在进行线缆与结构件干涉检测时，结构件组成较复杂时，干涉检测时间明显增加，如表 1中算例(e~h)所示。线缆与结构件干涉检测所花费时间的增加主要是由于结构件较多时，系统需要花费大量时间进行模型的分析处理。在实际应用时，干涉检测所花费时间可以满足工程实际的需要。

4 结束语

本文针对三维线缆干涉检测算法，分别对线缆自干涉，线缆与线缆干涉，线缆与刚性结构件干涉提出了不同的解决方法。利用线缆在计算机中表达的几何特征，对线缆进行中心线动态离散表示,根据结构件实体在计算机中的表示特性，提取实体的几何特征信息进行分析判断，实现三维线缆的全局干涉检测，解决了虚拟布线过程中线缆全局干涉检测的问题。实验表明，算法准确率高，适合于线缆虚拟布线中的线缆干涉检测。