版图设计文件的解析方法、设备和存储介质与流程

本技术涉及pcb仿真，尤其涉及一种版图设计文件的解析方法、设备和存储介质。

背景技术：

1、为了了解pcb的性能，需要在仿真软件中对pcb和ic进行电磁仿真。相关技术中的仿真软件，首先需要通过layout解析工具将版图设计文件解析为可计算的几何图形数据。但是，同一网络的散碎几何图元在网格剖分前需要执行布尔并运算，以消除冗余几何节点。目前的仿真软件在解析版图设计文件时，通常对各几何图形按序两两合并，即先将前两个图形执行布尔并运算得到中间结果，再将中间结果与下一图形执行布尔并运算，依此类推，直至所有图形合并完成，得到最终合并结果。

2、该按序合并方式中，每一步合并均需遍历参与运算的全部图形顶点，且合并步骤随图形数量n的增加呈平方级增长，整体时间复杂度达到o(n²×v)。当版图中散碎图形数量较多时，布尔并运算耗时随之急剧增加，处理效率受到明显限制，难以满足大规模电磁仿真对几何处理效率的要求。

技术实现思路

1、本技术的主要目的在于提供一种版图设计文件的解析方法、设备和存储介质，旨在解决按序合并导致时间复杂度高的技术问题。

2、为实现上述目的，本技术提供一种版图设计文件的解析方法，所述版图设计文件的解析方法包括：

3、解析得到版图设计文件中的至少一个目标网络，并提取各所述目标网络下的全部几何图形，构成待合并图形集合，所述待合并图形集合包含n个几何图形，各所述几何图形由闭合多边形边界表示；

4、采用两色着色器对所述待合并图形集合中的各所述几何图形，按照索引序号进行交替着色分组，得到两个互补的子集合；

5、对所述子集合分别递归执行所述交替着色分组，直至各所述子集合所包含的几何图形数量不大于一，构建二叉树合并结构；

6、按照自底向上的层序遍历所述二叉树合并结构，逐层执行布尔运算，得到所述目标网络下所述全部几何图形的最终合并图形；

7、输出所述最终合并图形，以所述最终合并图形作为网格剖分的几何输入数据。

8、在一实施例中，所述解析得到版图设计文件中的至少一个目标网络，并提取各所述目标网络下的全部几何图形，构成待合并图形集合，包括：

9、解析所述版图设计文件，得到以电气网络为单位组织的几何图形数据；

10、从所述几何图形数据中确定至少一个目标网络；

11、对各所述目标网络，分别提取归属于所述目标网络的几何图形，构成与所述目标网络对应的待合并图形集合；

12、其中，所述几何图形包括走线段、焊盘、过孔以及覆铜区域中的至少一种，闭合多边形边界包括外环顶点坐标序列和/或孔洞内环顶点坐标序列。

13、在一实施例中，所述解析得到版图设计文件中的至少一个目标网络，并提取各所述目标网络下的全部几何图形，构成待合并图形集合之后，还包括：

14、对所述待合并图形集合中的各所述几何图形进行连通性检查与合法性校验；其中，所述连通性检查为判断各所述几何图形之间是否存在需要合并的连通关系；所述合法性校验包括将顶点数量少于三个的退化几何图形标记为无效几何图形并从所述待合并图形集合中移除，以及对存在自交或其他拓扑错误的几何图形进行修复或标记；

15、在完成所述连通性检查与合法性校验后，统计所述待合并图形集合中有效几何图形的数量，当所述有效几何图形的数量不大于一时，将所述有效几何图形作为最终合并图形输出，或输出空集。

16、在一实施例中，所述采用两色着色器对所述待合并图形集合中的各所述几何图形，按照索引序号进行交替着色分组，得到两个互补的子集合，包括：

17、根据所述待合并图形集合中各所述几何图形的排列顺序，确定各所述几何图像对应的所述索引序号；

18、将所述待合并图形集合中索引序号为奇数的各所述几何图形赋以第一颜色，并划入第一子集合；

19、将索引序号为偶数的各所述几何图形赋以第二颜色，并划入第二子集合。

20、在一实施例中，所述互补子集合包括第一子集合以及第二子集合，所述对所述子集合分别递归执行所述交替着色分组，直至各所述子集合所包含的几何图形数量不大于一，构建二叉树合并结构，包括：

21、分别对所述第一子集合以及所述第二子集合执行所述交替着色分组，得到下一层级的子集合；

22、针对所述下一层级的子集合重复执行所述交替着色分组，直至得到的各子集合所包含的几何图形数量不大于一；

23、以各所述几何图形为叶节点，以对两个子节点所对应的几何图形执行的布尔运算为内部节点，构建所述二叉树合并结构；其中，所述二叉树合并结构的根节点对应所述待合并图形集合中全部几何图形的布尔运算结果，所述二叉树合并结构的深度为以二为底n的对数向上取整，n为所述待合并图形集合中几何图形的数量。

24、在一实施例中，所述按照自底向上的层序遍历所述二叉树合并结构，逐层执行布尔运算，得到所述目标网络下所述全部几何图形的最终合并图形，包括：

25、从所述二叉树合并结构的叶节点对应层级开始，按照自底向上的层序，对当前层级中每一对子节点执行布尔运算，将两个子节点所对应的几何图形合并为一个几何图形，并将合并结果作为上一层级中对应内部节点的子节点；

26、逐层向上执行布尔运算，直至根节点完成布尔运算，得到所述最终合并图形；

27、在一实施例中，所述采用两色着色器对所述待合并图形集合中的各所述几何图形，按照索引序号进行交替着色分组，得到两个互补的子集合之前，包括：

28、计算所述待合并图形集合中各所述几何图形的包围盒中心坐标；

29、按照空间填充曲线对各所述几何图形的包围盒中心坐标进行排序；

30、依据排序结果重新排列各所述几何图形在所述待合并图形集合中的排列顺序，以使得空间上相邻的几何图形具有相邻的索引序号。

31、在一实施例中，当存在目标子集合包含一个第一几何图形，且不存在与所述第一几何图形配对的第二几何图形时，将所述目标子集合所对应的节点作为上一层级节点的输入，并且不执行布尔并运算；

32、当所述最终合并图形包含多个互不连通的子区域时，将各所述子区域分别输出为相互独立的网格剖分的几何输入数据。

33、此外，为实现上述目的，本技术还提供一种版图设计文件的解析设备，所述版图设计文件的解析设备包括：存储器、处理器及存储在所述存储器上并可在所述处理器上运行的计算机程序，所述计算机程序配置为实现如上所述版图设计文件的解析方法的步骤。

34、此外，为实现上述目的，本技术还提供一种存储介质，所述存储介质为计算机可读存储介质，所述计算机可读存储介质上存储有实现版图设计文件的解析方法的程序，所述实现版图设计文件的解析方法的程序被处理器执行以实现如上所述版图设计文件的解析方法的步骤。

35、本技术提供了一种版图设计文件的解析方法，本技术首先通过解析版图设计文件提取目标网络下的全部几何图形构成待合并图形集合；如果采用两色着色器对待合并图形集合中的各几何图形按索引序号进行交替着色分组，得到两个互补子集合，并对子集合分别递归执行着色分组直至各子集合包含的几何图形数量不大于一，构建二叉树合并结构；而在构建二叉树合并结构之后，进一步按照自底向上的层序遍历二叉树合并结构逐层执行布尔运算，同一层内的多个布尔运算互不依赖且可并行执行，从而进一步缩短了实际计算耗时，避免了顺序合并中单核串行执行无法利用多核处理器资源的问题；通过输出最终合并图形作为网格剖分的几何输入数据，使得网格剖分器能够基于合并后的真实物理边界进行合理剖分。本技术通过构建二叉树合并结构将串行布尔运算链重构为深度log2n的二叉树结构，运算深度从顺序合并的n缩减为log2n，且同一层内的布尔运算可并行执行，解决了现有版图设计中大量几何图形顺序合并导致时间复杂度高且无法并行执行的技术问题。