CN110941940B - 一种基于碰撞检测的3d绕线方法、存储设备和系统 - Google Patents

Abstract

本发明涉及一种基于碰撞检测的3D绕线方法、存储设备和系统，具体包括下述步骤：步骤（1）：初始化绕线信息；步骤（2）：创建绕线轨迹和节点；步骤（3）：布线；步骤（4）：绕线结束判断；判断是否还有未处理的待绕线网络，若有，则取一个待绕线网络并至步骤（2）执行，否则完成绕线，获得绕线结果。本发明在绕线过程采用多方向的探索，包括层间的探索，避免了单层绕线产生绕线失败的情况。

Description

一种基于碰撞检测的3D绕线方法、存储设备和系统

技术领域

本发明是关于集成电路技术领域，特别涉及一种基于碰撞检测的3D绕线方法及系统。

背景技术

随着集成电路技术的快速发展，集成电路进入了超深亚微米时代，这样使得电子器件的特征尺寸越来越小，芯片的规模越来越大，越来越多的元器件可以集成在单一的芯片上，复杂度急剧上升，而对于版图中的布线方法由人工设计布线方法早已无法满足集成电路设计的需要，计算机自动布线已经在版图设计布线中占有越来越大的比例。而布线的算法对于布线的速度、效率有着极其重要的影响，如何能够设计出所需要时间空间更少、复杂度更低、效率更高的算法成为了半导体计算机辅助设计所面临的巨大问题。针对于详细布线，传统的平面布线算法比较常见的方法有：

1、李氏迷宫绕线算法(Lee’s Maze Routing Algorithm)：该绕线算法是一种单网络绕线算法；首先将绕线平面划分为大小一致的均匀网格，从起始网格开始，设置其水平与垂直方向的相邻网格，并且未被占用的4个网格的代价值，迭代这一步骤，代价值按照升序增加，最终搜索到目标网格，从目标网格回溯到起始网格，从而得到最短路径。该算法对于单网络绕线效果较好，但存在效率低、存储需求大的问题。

2、顺序绕线算法(Sequential Routing)：该算法是一种多网络绕线算法；首先设置待绕线网络的绕线顺序，按照顺序对待绕线网络进行绕线，当一个网络完成绕线，则更新全局绕线资源的拥塞度，这会导致后续待绕线的网络被迫使用过拥塞的绕线资源。该绕线算法对于绕线的顺序异常敏感，通常会导致先绕线完成的网络影响到后绕线的网络。

由上可知，传统的绕线方法主要针对单一平面绕线，对于绕线过程中产生的绕线冲突问题并没有较好的解决方案，通常会引起先生成的绕线阻挡了后续生成的绕线，最终导致绕线失败；并且传统的绕线方法通常会产生密集的绕线节点，在绕线时需要消耗更多的内存。因此，在集成电路三维绕线领域，还没有一种成熟的多层绕线方法。

发明内容

本发明的主要目的在于克服现有技术中的不足，提供一种多层绕线的方法及系统，用于解决集成电路三维绕线中存在的绕线碰撞问题。为解决上述技术问题，本发明的解决方案是：

提供一种基于碰撞检测的3D绕线方法，具体包括下述步骤：

步骤(1)：初始化绕线信息；

获取信息包括待绕线网络、绕线平面、元器件和障碍物的信息；其中，所述待绕线网络中包括两个待绕线元器件的信息(包括待绕线元器件的位置、待绕线引脚的信息等)；所述绕线平面有N个，N为大于0的自然数，N个绕线平面相互平行；

取一个待绕线网络进行后续步骤处理；

步骤(2)：创建绕线轨迹和节点；

分别在每个绕线平面的绕线区域中创建绕线轨迹，包括水平绕线轨迹和垂直绕线轨迹，且在每个绕线平面中，水平绕线轨迹和垂直绕线轨迹的交点为节点；

所有绕线平面中的节点形成3D的节点矩阵，并设定邻接节点：在同一绕线平面中水平或垂直方向上相邻的节点，或者沿着垂直于绕线平面方向上相邻绕线平面中的节点(即具有相同平面坐标但属于相邻绕线平面的节点)；

步骤(3)：布线；

获取待绕线网络的起始引脚和目的引脚，确定起始节点和目的节点，利用碰撞检测探索从起始节点到目的节点的路径；所述碰撞检测是指对于探索到的节点，根据该节点及其邻接节点的位置信息，来判断该节点是否能够绕线；

若该待绕线网络的布线探索成功，进行绕线以生成绕线拓扑结构，即该待绕线网络成功绕线；否则，该待绕线网络绕线失败；

步骤(4)：绕线结束判断；

判断是否还有未处理的待绕线网络，若有，则取一个待绕线网络并至步骤(2)执行，否则完成绕线，获得绕线结果。

作为进一步的改进，所述步骤(2)中，在每个绕线平面中，分别根据绕线区域、元器件、待绕线引脚、障碍物和绕线拓扑结构创建绕线轨迹，包括水平绕线轨迹和垂直绕线轨迹，能形成大小不同的稀疏网格；创建方式具体如下：

对绕线区域创建绕线轨迹：绕线区域至少包括2条水平的绕线轨迹和2条垂直的绕线轨迹，绕线区域为矩形的区域，设绕线区域边缘的左下角坐标和右上角坐标分别为(mLLX,mLLY)和(mURX,mURY)，2条垂直绕线轨迹的横坐标分别为X₁,X₂，2条水平绕线轨迹的纵坐标分别为Y₁,Y₂，则满足：

X₁＝mLLX+width/2

X₂＝mURX-width/2

Y₁＝mLLY+width/2

Y₂＝nURY-width/2

对元器件或障碍物创建绕线轨迹：首先获取能够包含该元器件或障碍物的最小矩形，设该矩形的左下角坐标和右上角坐标分别为(mLLX,mLLY)和(mURX,mURY)，每个元器件或障碍物至少包括6条水平的绕线轨迹和6条垂直的绕线轨迹，设6条垂直绕线轨迹的横坐标分别为X₁,X₂,X₃,X₄,X₅,X₆，6条水平绕线轨迹的纵坐标分别为Y₁,Y₂,Y₃,Y₄,Y₅,Y₆，则满足：

X₁＝mLLX-width/2-space

X₂＝mLLX-space

X₃＝mLLX

X₄＝mURX

X₅＝mURX+space

X₆＝mURX+width/2+space

Y₁＝mLLY-width/2-space

Y₂＝mLLY-space

Y₃＝mLLY

Y₄＝mURY

Y₅＝mURY+space

Y₆＝mURY+width2+space

对引脚创建绕线轨迹：引脚至少包括3条绕线轨迹，引脚为矩形的引脚，根据引脚不同的引出方向分别进行创建：

若引脚的引出方向为水平方向，设引脚的下上边缘的纵坐标分别为py₁,py₂，3条绕线轨迹都是水平的绕线轨迹且纵坐标分别为Y₁,Y₂,Y₃，则满足：

Y₁＝py1-width/2-space

Y₂＝(py1+py2)/2

Y₃＝py2+width2+space

若引脚的引出方向为垂直方向，设引脚的左右边缘的横坐标分别为px₁,px₂，3条绕线轨迹都是垂直的绕线轨迹且横坐标分别为X₁,X₂,X₃，则满足：

X₁＝px1-width/2-space

X₂＝(px1+px2)/2

X₃＝px2+width2+space

对绕线拓扑结构创建绕线轨迹：先将绕线拓扑结构分割为若干个矩形拓扑结构，包括沿着水平方向的矩形拓扑结构和沿着垂直方向的矩形拓扑结构；每个分割后的矩形拓扑结构至少包括4条绕线轨迹，根据矩形拓扑结构不同的方向分别进行创建：

若矩形拓扑结构是沿着水平方向的拓扑结构，设该矩形拓扑结构下上边缘的纵坐标分别为sy₁,sy₂，4条绕线轨迹都是水平的绕线轨迹且纵坐标分别为Y₁,Y₂,Y₃,Y₄，则满足：

Y₁＝sy₁-width/2-space

Y₂＝sy₁

Y₃＝sy₂

Y₄＝sy₂+width/2+space

若矩形拓扑结构是沿着垂直方向的拓扑结构，设该矩形拓扑结构左右边缘的横坐标分别为sx₁,sx₂，4条绕线轨迹都是垂直的绕线轨迹且横坐标分别为X₁,X₂,X₃,X₄，则满足：

X₁＝sx₁-width/2-space

X₂＝sx₁

X₃＝sx₂

X₄＝sx₂+width/2+space。

其中，所述width是指预设的绕线宽度；所述space是指预设的绕线间距。

作为进一步的改进，所述步骤(2)中，还根据每个节点与绕线区域、元器件、障碍物、绕线拓扑结构的位置关系，设置节点的状态：无效节点、遮挡节点或普通节点；以及根据预设的绕线宽度和节点的位置信息，设置每个节点在水平方向上和在垂直方向上占据的宽度；

其中，无效节点是指不在绕线区域内的节点，以及在元器件或障碍物影响范围内的节点；具体具体判断方法为：设绕线平面内某一个节点坐标为(x,y)，当该节点满足下述任意一项条件，则该节点为无效节点；

条件1)设绕线区域的左下角和右上角的坐标分别为(mLLX,mLLY)和(mURX,mURY)，该节点满足：x≤mLLX+width/2，或者x≥mURX-width/2，或者y≤mLLY+width/2，或者y≥mURY-width/2；

条件2)绕线平面中某元器件或障碍物的左下角和右上角的坐标分别为(X₁,Y₁)和(X₂,Y₂)，该节点满足：X₁-space≤x≤X₂+space且Y₁-space≤y≤Y₂+space；

遮挡节点是指在绕线拓扑结构影响范围内的节点，具体具体判断方法为：绕线拓扑结构被分割为若干个矩形拓扑结构，设某矩形拓扑结构的左下角和右上角的坐标分别为(X₁,Y₁),(X₂,Y₂)，设绕线平面内某一个节点坐标为(x,y)，如果满足下述条件则该节点为遮挡节点：X₁≤x≤X₂且Y₁≤y≤Y₂；

普通节点是指除无效节点和遮挡节点外的剩余节点。

作为进一步的改进，根据预设的绕线宽度和节点的位置信息，设置每个节点在水平方向上和在垂直方向上占据的宽度(可仅设置遮挡节点和普通节点占据的宽度，无效节点不进行设置)，方法具体如下：

先初始化每个节点占据的宽度：

x_occupied_width＝width

y_occupied_width＝width

其中，所述x_occupied_width是指节点在水平方向上占据的宽度，所述y_occupied_width是指节点在垂直方向上占据的宽度；所述width是指预设的绕线宽度；

再依次判断每个节点是否在引脚引出线上，所述引脚的引出线是指以该引脚的引出点为端点，以该引脚的引出方向作为方向，而产生的射线；若某节点在水平的引脚引出线上，设该引脚的上下边缘的垂直坐标值分别为py₁,py₂,该节点在垂直方向占据的宽度设为：y_occupied_width＝py₁-py₂；若某节点在垂直的引脚引出线上，设该引脚的左右边缘的水平坐标值分别为px₁,px₂，该节点在水平方向占据的宽度设为：x_occupied_width＝px₂-px₁。

作为进一步的改进，所述步骤(3)中，获取待绕线网络的起始引脚和目的引脚后，根据引脚的引出点和引出方向，确定起始节点和目的节点；

具体确定方法为：在绕线平面内，在引脚引出线上距离引出点space距离处，沿着垂直于引脚的引出方向创建一条直线，该直线与引脚引出线的交点即作为该起始引脚的起始节点或该目的引脚的目的节点；所述引脚引出线是指以该引脚的引出点为端点，以该引脚的引出方向作为方向，而产生的射线；所述space是指预设的绕线间距。

作为进一步的改进，所述步骤(3)中，在布线探索过程中，遍历探索当前节点cur_grid除其父节点外的邻接节点(起始节点为首个当前节点，且起始节点无父节点)，获取普通节点状态的邻接节点adj并利用碰撞检测分别判断每个adj是否能够绕线，将能够绕线的adj作为候选节点，用于从候选节点中确定新的当前节点；

利用碰撞检测分别判断每个adj是否能够绕线，具体如下：

遍历adj的探索方向，探索adj在每个探索方向上的邻接节点check_node(不包括父节点cur_grid)；若adj获取到邻接节点check_node，则依次利用每个check_node判断adj是否可绕，当利用所有check_node都分别得出adj可绕，则判断该adj能够绕线，当存在利用任一个check_node得出adj不可绕，则判断该adj不能够绕线并结束碰撞检测；

任取一个check_node，判断adj是否可绕：先计算check_node和adj之间的距离dist，并根据不同的情况判断adj是否可绕：

情况1)若check_node是目的节点，则判断adj可绕；

情况2)若check_node是无效节点，当dist不小于预设的阈值A，则判断adj可绕，否则判断adj不可绕；

情况3)若check_node是遮挡节点，当dist不小于预设的阈值B，则判断adj可绕，否则判断adj不可绕；

情况4)若check_node是普通节点，则根据dist以及check_node的位置信息，来判断adj是否可绕。

作为进一步的改进，从候选节点中选择代价最小的一个节点作为新的当前节点；

候选节点的代价new_cost的计算方式为：

若候选节点仅横坐标与当前节点的横坐标相同，则new_cost＝dist*width/y_occupied_width+cost；

若候选节点仅纵坐标与当前节点的纵坐标相同，则new_cost＝dist*width/x_occupied_width+cost；

若候选节点与当前节点分别处于不同的绕线平面，且横、纵坐标都相同，则new_cost＝0；

其中，所述dist是指候选节点与当前节点的距离；所述width是指预设的绕线宽度；所述x_occupied_width是指候选节点在水平方向上占据的宽度；所述y_occupied_width是指候选节点在垂直方向上占据的宽度；所述cost是当前节点的代价。

作为进一步的改进，当候选节点中，代价最小的节点不只一个时，则从候选节点中选择代价最小且转弯值最小的节点作为新的当前节点；

候选节点的转弯值turn_cnt的计算方式为：

若当前节点cur_grid的父节点到当前节点cur_grid的方向，与当前节点cur_grid到该候选节点adj的方向不同，则turn_cnt＝turn_count+1；

若当前节点cur_grid的父节点到当前节点cur_grid的方向，与当前节点cur_grid到该候选节点adj的方向相同，则turn_cnt＝turn_count；

其中，所述turn_count为当前节点cur_grid的转弯值。

作为进一步的改进，当候选节点中，代价和转弯值都最小的节点不只一个时，则从候选节点中选择代价、转弯值和使用层数都最小的节点作为新的当前节点；

候选节点的使用层数是指该当前节点到该候选节点所经过的绕线平面层数。

作为进一步的改进，所述步骤(3)中，对于布线探索成功的待绕线网络，根据路径中每个节点的绕线宽度进行绕线以生成绕线拓扑结构；

所述节点的绕线宽度是指：当生成水平方向的绕线拓扑结构时，以节点在垂直方向上占据的宽度作为绕线宽度，当生成垂直方向的绕线拓扑结构时，以节点在水平方向上占据的宽度作为绕线宽度。

提供一种存储设备，其中存储有多条指令，所述指令适用于处理器加载并执行：上述基于碰撞检测的3D绕线方法。

提供一种基于碰撞检测的3D绕线系统，包括处理器和存储设备，处理器适于实现各指令，存储设备适于存储多条指令，所述指令适用于处理器加载并执行：上述基于碰撞检测的3D绕线方法。

与现有技术相比，本发明的有益效果是：

1、本发明在绕线过程采用多方向的探索，包括层间的探索，避免了单层绕线产生绕线失败的情况。

2、本发明在探索的过程中对探索节点的周围节点进行碰撞检测，能够及时判断节点是否能够用于绕线。

3、本发明不再局限于固定的绕线轨迹的间隔，能够根据pin的宽度来设置与pin直线连接的绕线的宽度。

附图说明

图1为绕线区域的绕线轨迹创建示意图。

图2为元器件或障碍物的绕线轨迹创建示意图。

图3为水平方向引出的引脚的绕线轨迹创建示意图。

图4为垂直方向引出的引脚的绕线轨迹创建示意图。

图5为水平方向的拓扑结构的绕线轨迹创建示意图。

图6为垂直方向的拓扑结构的绕线轨迹创建示意图。

图7为节点矩阵示意图。

图8为无效节点示意图。

图9为遮挡节点示意图。

图10为确定水平引出方向的引脚的起始节点及该节点的绕线宽度示意图。

图11为实施例中当前节点cur_grid探索到普通状态的邻接节点示意图。

具体实施方式

下面结合附图与具体实施方式对本发明作进一步详细描述：

一种基于碰撞检测的3D绕线方法，能在三维的多层绕线平面环境下实现绕线；设绕线平面设有N个，N为大于0的自然数，N个绕线平面相互平行，在本实施例中，每个绕线平面上的绕线区域大小相同且能在沿着垂直于绕线平面的方向平移后完全重叠，则该基于碰撞检测的3D绕线方法具体包括下述步骤：

步骤(1)：初始化绕线信息；

获取所有待绕线网络、绕线平面、元器件和障碍物的信息，设置绕线宽度width和绕线间距space；其中，所述待绕线网络中包括两个待绕线元器件的信息，包括待绕线元器件的位置、待绕线引脚的信息等。

设置每个待绕线网络的状态为等待，并任取一个等待状态的待绕线网络进行后续步骤。

步骤(2)：创建绕线轨迹和节点；

在每个绕线平面中，分别创建绕线区域、元器件、待绕线引脚、障碍物和绕线拓扑结构的绕线轨迹，包括水平绕线轨迹和垂直绕线轨迹。具体创建方式如下：

对于绕线区域：如图1所示，绕线区域为矩形的区域，设绕线区域边缘的左下角坐标和右上角坐标分别为(mLLX,mLLY)和(mURX,mURY)，绕线区域的绕线轨迹包括2条横坐标分别为X₁,X₂的垂直绕线轨迹，以及2条纵坐标分别为Y₁,Y₂的水平绕线轨迹，则满足：

X₁＝mLLX+width/2

X₂＝mURX-width/2

Y₁＝mLLY+width/2

Y₂＝mURY-width/2。

对于元器件或者障碍物：如图2所示，首先获取能够包含该元器件或障碍物的最小矩形，设该矩形的左下角坐标和右上角坐标分别为(mLLX,mLLY)和(mURX,mURY)，每个元器件或障碍物包括6条横坐标分别为X₁,X₂,X₃,X₄,X₅,X₆的垂直绕线轨迹，以及6条纵坐标分别为Y₁,Y₂,Y₃,Y₄,Y₅,Y₆的水平绕线轨迹，则满足：

X₁＝mLLX-width/2-space

X₂＝mLLX-space

X₃＝mLLX

X₄＝mURX

X₅＝mURX+space

X₆＝mURX+width/2+space

Y₁＝mLLY-width/2-space

Y₂＝mLLY-space

Y₃＝mLLY

Y₄＝mURY

Y₅＝mURY+space

Y₆＝mURY+width/2+space。

对于引脚：引脚为矩形，根据该引脚的引出方向不同，分别创建引脚的3条绕线轨迹。

若引脚的引出方向为水平方向，如图3所示，设引脚的下上边缘的纵坐标分别为py₁,py₂，3条绕线轨迹都是水平的绕线轨迹且纵坐标分别为Y₁,Y₂,Y₃，则满足：

Y₁＝py1-width/2-space

Y₂＝(py1+py2)/2

Y₃＝py2+width/2+space

若引脚的引出方向为垂直方向，如图4所示，设引脚的左右边缘的横坐标分别为px₁,px₂，3条绕线轨迹都是垂直的绕线轨迹且横坐标分别为X₁,X₂,X₃，则满足：

X₁＝px1-width/2-space

X₂＝(px1+px2)/2

X₃＝px2+width/2+space

绕线拓扑结构：先将绕线拓扑结构分割为若干个矩形拓扑结构，包括沿着水平方向的矩形拓扑结构和沿着垂直方向的矩形拓扑结构；每个分割后的矩形拓扑结构包括4条绕线轨迹，根据矩形拓扑结构不同的方向分别进行创建。

若矩形拓扑结构是沿着水平方向的拓扑结构，如图5所示，设该矩形拓扑结构下上边缘的纵坐标分别为sy₁,sy₂，4条绕线轨迹是纵坐标分别为Y₁,Y₂,Y₃,Y₄的水平绕线轨迹，则满足：

Y₁＝sy₁-width/2-space

Y₂＝sy₁

Y₃＝sy₂

Y₄＝sy₂+width/2+space

若矩形拓扑结构是沿着垂直方向的拓扑结构，如图6所示，设该矩形拓扑结构左右边缘的横坐标分别为sx₁,sx₂，4条绕线轨迹是横坐标分别为X₁,X₂,X₃,X₄的垂直绕线轨迹，则满足：

X₁＝sx₁-width/2-space

X₂＝sx₁

X₃＝sx₂

X₄＝sx₂+width/2+space。

绕线轨迹创建完成后，在每个绕线平面中，水平绕线轨迹和垂直绕线轨迹的交点为节点。如图7所示，所有绕线平面中的节点形成3D的节点矩阵，并设定邻接节点：在同一绕线平面中水平或垂直相邻的节点，或者具有相同平面坐标但属于相邻绕线平面的节点。

步骤(3)：初始化节点信息；

根据每个节点与绕线区域、元器件、障碍物、绕线拓扑结构的位置关系，更新节点的状态，包括：无效节点、遮挡节点和普通节点。具体判断方式如下：

无效节点是指不在绕线区域内的节点，以及在元器件或障碍物影响范围内的节点，即，如图8所示，设绕线平面内某一个节点坐标为(x,y)，当该节点满足下述任意一项条件，则该节点为无效节点；

条件1)设绕线区域的左下角和右上角的坐标分别为(mLLX,mLLY)和(mURX,mURY)，该节点满足：x≤mLLX+width/2，或者x≥mURX-width/2，或者y≤mLLY+width/2，或者y≥mURY-width/2；

条件2)绕线平面中某元器件或障碍物的左下角和右上角的坐标分别为(X₁,Y₁)和(X₂,Y₂)，该节点满足：

X₁-space≤x≤X₂+space

Y₁-space≤y≤Y₂+space。

遮挡节点是指在绕线拓扑结构影响范围内的节点，绕线拓扑结构被分割为若干个矩形拓扑结构，如图9所示，设某矩形拓扑结构的左下角和右上角的坐标分别为(X₁,Y₁),(X₂,Y₂)，设绕线平面内某一个节点坐标为(x,y)，如果满足下述条件则该节点为遮挡节点：

X₁≤x≤X₂

Y₁≤y≤Y₂。

判断出无效节点和遮挡节点后，其余的节点则为普通节点。

然后，设置每个遮挡节点和普通节点占据的宽度，具体设置方式如下：

先初始化每个节点占据的宽度：

x_occupied_width＝width

y_occupied_width＝width

其中，所述x_occupied_width是指节点在水平方向上占据的宽度，所述y_occupied_width是指节点在垂直方向上占据的宽度；

再依次判断每个节点是否在引脚引出线上，所述引脚的引出线是指以该引脚的引出点为端点，以该引脚的引出方向作为方向，而产生的射线；若某节点在水平的引脚引出线上，设该引脚的上下边缘的垂直坐标值分别为py₁,py₂,该节点在垂直方向占据的宽度设为：y_occupied_width＝py₁-py₂，可参考图10；若某节点在垂直的引脚引出线上，设该引脚的左右边缘的水平坐标值分别为px₁,px₂，该节点在水平方向占据的宽度设为：x_occupied_width＝px₂-px₁。

步骤(4)：布线；

获取待绕线网络的起始引脚和目的引脚，并根据引脚的引出点和引出方向，确定起始节点和目的节点：在绕线平面内，在引脚引出线上距离引出点space距离处，沿着垂直于引脚的引出方向创建一条直线，该直线与引脚引出线的交点即作为该起始引脚的起始节点或该目的引脚的目的节点，可参考图10。

利用碰撞检测探索从起始节点到目的节点的路径：若布线探索成功，则根据路径中每个节点的绕线宽度进行绕线以生成绕线拓扑结构，将该拓扑结构作为新的绕线拓扑结构加入到绕线区域中，并更新该待绕线网络的状态为通过；若布线探索失败，则更新该待绕线网络的状态为失败。所述节点的绕线宽度是指：当生成水平方向的绕线拓扑结构时，以节点在垂直方向上占据的宽度作为绕线宽度，当生成垂直方向的绕线拓扑结构时，以节点在水平方向上占据的宽度作为绕线宽度。

在布线探索过程中，遍历探索当前节点cur_grid除其父节点外的邻接节点(起始节点为首个当前节点，且起始节点无父节点)，获取普通节点状态的邻接节点adj并利用碰撞检测分别判断每个adj是否能够绕线，将能够绕线的adj作为候选节点，用于从候选节点中确定新的当前节点。比如图11所示，当前节点cur_grid在其所在绕线平面中的水平向右方向和向上层绕线平面方向探索时，分别获取到两个普通节点状态的邻接节点adj，则需要分别对这两个邻接节点进行碰撞检测判断其是否能够绕线。

其中，利用碰撞检测分别判断每个adj是否能够绕线的方法具体如下：遍历adj的探索方向，探索adj在每个探索方向上的邻接节点check_node(不包括父节点cur_grid)；若adj获取到邻接节点check_node，则依次利用每个check_node判断adj是否可绕，当利用所有check_node都分别得出adj可绕，则判断该adj能用于绕线，当存在利用任一个check_node得出adj不可绕，则判断该adj不能用于绕线，并结束碰撞检测；

任取一个check_node，判断adj是否可绕，具体方法如下：先计算check_node和adj之间的距离dist，并根据不同的情况判断adj是否可绕：

情况1)若check_node是目的节点，则判断adj可绕；

情况2)若check_node是无效节点，当dist不小于预设的阈值A，则判断adj可绕，否则判断adj不可绕；

情况3)若check_node是遮挡节点，当dist不小于预设的阈值B，则判断adj可绕，否则判断adj不可绕；

情况4)若check_node是普通节点，则根据dist以及check_node的位置信息，来判断adj是否可绕。

利用碰撞检测，确定了候选节点后，需要从候选节点中选择一个节点作为新的当前节点，选择标准如下：

①代价：从候选节点中选择代价最小的一个节点作为新的当前节点；

候选节点的代价new_cost的计算方式为：

若候选节点仅横坐标与当前节点的横坐标相同，则new_cost＝dist*width/y_occupied_width+cost；

若候选节点仅纵坐标与当前节点的纵坐标相同，则new_cost＝dist*width/x_occupied_width+cost；

若候选节点与当前节点分别处于不同的绕线平面，且横、纵坐标都相同，则new_cost＝0；

其中，所述dist是指候选节点与当前节点的距离；所述width是指预设的绕线宽度；所述x_occupied_width是指候选节点在水平方向上占据的宽度；所述y_occupied_width是指候选节点在垂直方向上占据的宽度；所述cost是当前节点的代价。

②代价+转弯值：当候选节点中，代价最小的节点不只一个时，则从候选节点中选择代价最小且转弯值最小的节点作为新的当前节点；

候选节点的转弯值turn_cnt的计算方式为：

若当前节点cur_grid的父节点到当前节点cur_grid的方向，与当前节点cur_grid到该候选节点adj的方向不同，则turn_cnt＝turn_count+1；

若当前节点cur_grid的父节点到当前节点cur_grid的方向，与当前节点cur_grid到该候选节点adj的方向相同，则turn_cnt＝turn_count；

其中，所述turn_count为当前节点cur_grid的转弯值。

③代价+转弯值+使用层数：当候选节点中，代价和转弯值都最小的节点不只一个时，则从候选节点中选择代价、转弯值和使用层数都最小的节点作为新的当前节点；

候选节点的使用层数是指该当前节点到该候选节点所经过的绕线平面层数。

步骤(5)：绕线结束判断；

判断是否还有等待状态的待绕线网络，若有，则获取一个等待状态的待绕线网络并至步骤(2)继续执行，否则完成全部绕线，获得绕线结果。

上述基于碰撞检测的3D绕线方法，在绕线轨迹创建时，只需要在元器件、障碍物、pin和已绕线拓扑结构周围创建绕线轨迹，避免了密集的绕线节点，并且绕线轨迹间的距离不再有要求至少为width+space；另外，绕线宽度可以随着pin的宽度大小而变化，并利用碰撞检测来确定节点是否可绕线，有效优化了绕线过程。

最后，需要注意的是，以上列举的仅是本发明的具体实施例。显然，本发明不限于以上实施例，还可以有很多变形。本领域的普通技术人员能从本发明公开的内容中直接导出或联想到的所有变形，均应认为是本发明的保护范围。

Claims (12)

1.一种基于碰撞检测的3D绕线方法，其特征在于，具体包括下述步骤：

步骤(1)：初始化绕线信息；

获取信息包括待绕线网络、绕线平面、元器件和障碍物的信息；其中，所述待绕线网络中包括两个待绕线元器件的信息；所述绕线平面有N个，N为大于0的自然数，N个绕线平面相互平行；

取一个待绕线网络进行后续步骤处理；

步骤(2)：创建绕线轨迹和节点；

分别在每个绕线平面的绕线区域中创建绕线轨迹，包括水平绕线轨迹和垂直绕线轨迹，且在每个绕线平面中，水平绕线轨迹和垂直绕线轨迹的交点为节点；

所有绕线平面中的节点形成3D的节点矩阵，并设定邻接节点：在同一绕线平面中水平或垂直方向上相邻的节点，或者沿着垂直于绕线平面方向上相邻绕线平面中的节点；

步骤(3)：布线；

获取待绕线网络的起始引脚和目的引脚，确定起始节点和目的节点，利用碰撞检测探索从起始节点到目的节点的路径；所述碰撞检测是指对于探索到的节点，根据该节点及其邻接节点的位置信息，来判断该节点是否能够绕线；

若该待绕线网络的布线探索成功，进行绕线以生成绕线拓扑结构，即该待绕线网络成功绕线；否则，该待绕线网络绕线失败；

步骤(4)：绕线结束判断；

判断是否还有未处理的待绕线网络，若有，则取一个待绕线网络并至步骤(2)执行，否则完成绕线，获得绕线结果。

2.根据权利要求1所述的一种基于碰撞检测的3D绕线方法，其特征在于，所述步骤(2)中，在每个绕线平面中，分别根据绕线区域、元器件、待绕线引脚、障碍物和绕线拓扑结构创建绕线轨迹，包括水平绕线轨迹和垂直绕线轨迹，能形成大小不同的稀疏网格。

3.根据权利要求1所述的一种基于碰撞检测的3D绕线方法，其特征在于，所述步骤(2)中，还根据每个节点与绕线区域、元器件、障碍物、绕线拓扑结构的位置关系，设置节点的状态：无效节点、遮挡节点或普通节点；以及根据预设的绕线宽度和节点的位置信息，设置每个节点在水平方向上和在垂直方向上占据的宽度；

其中，无效节点是指不在绕线区域内的节点，以及在元器件或障碍物影响范围内的节点；遮挡节点是指在绕线拓扑结构影响范围内的节点；普通节点是指除无效节点和遮挡节点外的剩余节点。

4.根据权利要求1所述的一种基于碰撞检测的3D绕线方法，其特征在于，所述步骤(3)中，获取待绕线网络的起始引脚和目的引脚后，根据引脚的引出点和引出方向，确定起始节点和目的节点。

5.根据权利要求3所述的一种基于碰撞检测的3D绕线方法，其特征在于，所述步骤(3)中，在布线探索过程中，遍历探索当前节点cur_grid除其父节点外的邻接节点，获取普通节点状态的邻接节点adj并利用碰撞检测分别判断每个adj是否能够绕线，将能够绕线的adj作为候选节点，用于从候选节点中确定新的当前节点；

利用碰撞检测分别判断每个adj是否能够绕线，具体如下：

遍历adj的探索方向，探索adj在每个探索方向上的邻接节点check_node；若adj获取到邻接节点check_node，则依次利用每个check_node判断adj是否可绕，当利用所有check_node都分别得出adj可绕，则判断该adj能够绕线，当存在利用任一个check_node得出adj不可绕，则判断该adj不能够绕线并结束碰撞检测；

任取一个check_node，判断adj是否可绕：先计算check_node和adj之间的距离dist，并根据不同的情况判断adj是否可绕：

情况1)若check_node是目的节点，则判断adj可绕；

情况2)若check_node是无效节点，当dist不小于预设的阈值A，则判断adj可绕，否则判断adj不可绕；

情况3)若check_node是遮挡节点，当dist不小于预设的阈值B，则判断adj可绕，否则判断adj不可绕；

情况4)若check_node是普通节点，则根据dist以及check_node的位置信息，来判断adj是否可绕。

6.根据权利要求5所述的一种基于碰撞检测的3D绕线方法，其特征在于，当候选节点中，代价最小的节点不只一个时，则从候选节点中选择代价最小且转弯值最小的节点作为新的当前节点；

候选节点的转弯值turn_cnt的计算方式为：

若当前节点cur_grid的父节点到当前节点cur_grid的方向，与当前节点cur_grid到该候选节点adj的方向不同，则turn_cnt＝turn_count+1；

若当前节点cur_grid的父节点到当前节点cur_grid的方向，与当前节点cur_grid到该候选节点adj的方向相同，则turn_cnt＝turn_count；

其中，所述turn_count为当前节点cur_grid的转弯值。

7.根据权利要求6所述的一种基于碰撞检测的3D绕线方法，其特征在于，当候选节点中，代价和转弯值都最小的节点不只一个时，则从候选节点中选择代价、转弯值和使用层数都最小的节点作为新的当前节点；

候选节点的使用层数是指该当前节点到该候选节点所经过的绕线平面层数。

8.根据权利要求1所述的一种基于碰撞检测的3D绕线方法，其特征在于，所述步骤(3)中，对于布线探索成功的待绕线网络，根据路径中每个节点的绕线宽度进行绕线以生成绕线拓扑结构；

所述节点的绕线宽度是指：当生成水平方向的绕线拓扑结构时，以节点在垂直方向上占据的宽度作为绕线宽度，当生成垂直方向的绕线拓扑结构时，以节点在水平方向上占据的宽度作为绕线宽度。

9.根据权利要求3所述的一种基于碰撞检测的3D绕线方法，其特征在于，根据预设的绕线宽度和节点的位置信息，设置每个节点在水平方向上和在垂直方向上占据的宽度，方法具体如下：

先初始化每个节点占据的宽度：

x_occupied_width＝width

y_occupied_width＝width

其中，所述x_occupied_width是指节点在水平方向上占据的宽度，所述y_occupied_width是指节点在垂直方向上占据的宽度；所述width是指预设的绕线宽度；

再依次判断每个节点是否在引脚引出线上，所述引脚的引出线是指以该引脚的引出点为端点，以该引脚的引出方向作为方向，而产生的射线；若某节点在水平的引脚引出线上，设该引脚的上下边缘的垂直坐标值分别为py₁,py₂,该节点在垂直方向占据的宽度设为：y_occupied_width＝py₁-py₂；若某节点在垂直的引脚引出线上，设该引脚的左右边缘的水平坐标值分别为px₁,px₂，该节点在水平方向占据的宽度设为：x_occupied_width＝px₂-px₁。

10.根据权利要求5所述的一种基于碰撞检测的3D绕线方法，其特征在于，从候选节点中选择代价最小的一个节点作为新的当前节点；

候选节点的代价new_cost的计算方式为：

若候选节点仅横坐标与当前节点的横坐标相同，则new_cost＝dist*width/y_occupied_width+cost；

若候选节点仅纵坐标与当前节点的纵坐标相同，则new_cost＝dist*width/x_occupied_width+cost；

若候选节点与当前节点分别处于不同的绕线平面，且横、纵坐标都相同，则new_cost＝0；

其中，所述dist是指候选节点与当前节点的距离；所述width是指预设的绕线宽度；所述x_occupied_width是指候选节点在水平方向上占据的宽度；所述y_occupied_width是指候选节点在垂直方向上占据的宽度；所述cost是当前节点的代价。

11.一种存储设备，其中存储有多条指令，所述指令适用于处理器加载并执行：权利要求1至8任意一项所述的基于碰撞检测的3D绕线方法。

12.一种基于碰撞检测的3D绕线系统，包括处理器和存储设备，处理器适于实现各指令，存储设备适于存储多条指令，所述指令适用于处理器加载并执行：权利要求1至8任意一项所述的基于碰撞检测的3D绕线方法。

Images