几何建模中表面模型完整包络的自动检测方法

摘要

本发明涉及一种几何建模中表面模型完整包络的自动检测方法，包括多边形面片间缝隙或面片悬挂检测算法、多边形面片重叠算法。利用该检测方法，可以对通过人机交互或模型自动转换得到的表面模型是否完整包络进行自动检测，以便检测出未完整包络的表面模型，提示技术人员去修正模型，从而最终得到符合矩量法网格划分和电磁计算所要求的表面模型。

说明书

技术领域

本发明属于电磁兼容领域，涉及电磁场数值分析所用表面模型 包络检测方法，具体的说是几何建模中表面模型完整包络的自动检 测方法，用于电磁兼容领域几何建模及其它领域几何建模问题的研 究。

背景技术

随着现代电子科学技术的快速发展和不断进步，车辆、飞机、 舰船等通信系统载体上装备了各种不同的用于接收和发射信号的设 备，由于对通信系统载体性能要求的不断提高，使得其上装的各类 无线电子设备的密度增加，导致这些电子、电器设备通信之间的电 磁信号更加密集，电磁环境日益恶化。设备间以及设备与环境间的 电磁干扰会影响设备和系统的使用性能，使它们不能正常工作，造 成无法预知的后果，甚至会造成无法弥补的损失。因此，通信系统 的电磁兼容问题不容忽视。

计算电磁学是系统电磁兼容预测分析的主要工具。计算电磁学 使用的方法主要有两类：一类是以电磁场问题微分方程为基础的数 值方法，如有限元法；另一类是以电磁场问题积分方程为基础的数 值方法，如矩量法。矩量法是电磁场数值分析计算中应用最早的一 种方法，它是内域积分形式的加权余量法的总称。矩量法最早被 Richmand和Harrington用于求解电磁场问题，而后Harrington将 矩量法加以系统的论述，从此成为求解电磁场问题的主要方法。在 电磁兼容分析和预测中，矩量法也得到了广泛的应用，而基于矩量 法的电磁兼容分析软件更是为设备和系统的电磁兼容分析提供了方 便而高效的手段。矩量法是以积分方程为基础的，因此，应用于电 磁计算中就要求模型划分后的电流满足连续性，所以要保证载体模 型在几何上满足一定的连续性。表面模型要完整包络，模型面片之 间不能出现缝隙，模型面片不能出现悬挂，模型面片之间不能重 叠。所以针对几何建模中通过人机交互或模型自动转换得到的表面 模型完整包络的检测就非常有必要，模型如果没有完整包络，则计 算结果会出现一定的误差甚至导致错误的结果。

几何建模中表面模型完整包络的自动检测内容包含面片间缝隙 检测、面片悬挂检测和面片重叠检测。文献“空间信息系统原理” (科学出版社，2001，作者：王家耀)通过选取负面积多边形，找 出面积绝对值比负面积大，且多边形的最小外接矩形包含负面积多 边形的所有多边形，然后判断负面积多边形的内点在哪些多边形内 来确定多边形的相对位置关系；论文“确定两个任意简单多边形空 间关系的算法”(计算机工程与应用，2003年1月，91-94，作 者：朱雅音等)通过把简单多边形的边分为奇偶边，根据一个多边 形的边与另外一个多边形的拓扑关系，划分边为5种拓扑类型：内 边、外边、重叠边、相交边、复杂边，进而通过一定的算法确定两 个多边形空间关系。可以看出，已有研究成果存在以下问题：(1) 对模型面片之间缝隙和面片悬挂的研究很少；(2)对模型面片重叠 的判断研究虽然很多，方法也很成熟，但是算法比较复杂，不适合 用于表面模型面片重叠检测；(3)已有的研究算法都是针对多边形 之间的位置判断，几乎没有针对整个表面模型完整包络的检测算 法。

发明内容

本发明的目的在于克服上述现有研究中存在的问题，提供一种 针对几何建模中表面模型完整包络的自动检测方法，以便检测出未 完整包络的表面模型，提示技术人员去修正模型，从而最终得到符 合矩量法网格划分和电磁计算所要求的表面模型。

本发明的目的是这样实现的：几何建模中表面模型完整包络的 自动检测方法，其特征是：包括如下步骤：

步骤101：打开由三角形、四边形面片构成的表面模型文件；

步骤102：将表面模型数据读入到tempcom_list链表中， tempcom_list链表中每一个存储单元存储一个三角形或四边形面片 数据信息；

步骤103：判断tempcom_list链表中的数据是否读完，如果读 完，转至步骤104；如果没有读完，转至步骤105；

步骤104：提示模型完整包络；

步骤105：读取tempcom_list链表中一个存储单元存储的多边 形数据，将读取出的多边形作为基多边形；这里的多边形指三角 形、四边形面片；

步骤106：读取tempcom_list链表中除去基多边形外其他所有 的多边形，将这些多边形依次作为相对多边形，判断相对多边形到 基多边形各条边距离为零的边是否将基多边形完整包围，如果基多 边形被完整包围，转至步骤108；如果基多边形没有被完整包围， 转至步骤107；

步骤107：提示面片之间有缝隙或面片悬挂；

步骤108：遍历tempcom_list链表，读取tempcom_list链表 中除去基多边形的非基多边形，判断tempcom_list链表中是否有与 基多边形在同一平面的非基多边形，如果有与基多边形在同一平面 的非基多边形，转至步骤109；如果没有与基多边形在同一平面的 非基多边形，转至步骤103；

步骤109：找出与基多边形在同一平面的所有非基多边形，将 与基多边形在同一平面的所有非基多边形依次作为相对多边形；

步骤110：读取基多边形的三个顶点P₁、P₂、P₃，取P₁为局部 坐标系的原点，取向量的方向为局部坐标系的X轴正方向，取 向量的方向作为局部坐标系的Z轴正方向，取向量 的方向作为局部坐标系的Y轴正方向，对基多边 形和相对多边形做世界坐标系到局部坐标系的变换，变换后基多边 形和相对多边形的z坐标全部为零，去掉基多边形和相对多边形顶 点坐标的z坐标，得到转换基多边形和转换相对多边形，转换基多 边形和转换相对多边形均为二维图形；

步骤111：求转换基多边形和转换相对多边形的轴向包围盒；

步骤112：判断轴向包围盒是否相交，如果相交，转至步骤 113；如果不相交，转至步骤103；

步骤113：判断转换基多边形和转换相对多边形是否相交，如 果相交，转至步骤114；如果不相交，转至步骤103；

步骤114：提示面片重叠。

所示步骤106中到基多边形各条边距离为零的边是否将基多边 形完整包围的判断方法，包括以下步骤：

步骤201：读取基多边形的数据；

步骤202：基多边形的边是否全部判断完，如果全部判断完， 转至步骤203；如果没有全部判断完，转至步骤204；

步骤203：提示基多边形被完整包围；

步骤204：读取基多边形的一条边作为被判断边；

步骤205：遍历tempcom_list链表，读取tempcom_list链表 中除去基多边形外的非基多边形，然后判断是否有非基多边形的边 到被判断边距离为零的边，如果有非基多边形的边到被判断边距离 为零的边，转至步骤206；如果没有，转至步骤213；

步骤206：找出到被判断边距离为零的所有边；

步骤207：在找到的到被判断边距离为零的所有边中删除与被 判断边方向相同的边，剩余的边作为判断边；

步骤208：求出所有判断边两个端点在被判断边向量上的投影 系数；

步骤209：对每一个判断边，由两个端点的投影系数构造一个 区间，并使区间右端点值不小于左端点值；

步骤210：求出所有判断边对应区间的并集U；

步骤211：判断区间U是否包含[0,1]区间，如果包含，转至步 骤212；如果不包含，转至步骤213；

步骤212：被判断边被完整包围；

步骤213：被判断边没有被完整包围，亦即基多边形未被完整 包围。

所述的步骤113中转换基多边形与转换相对多边形是否相交的 判断，包含如下步骤：

步骤301：读取转换基多边形和转换相对多边形的数据；

步骤302：转换基多边形的顶点是否判断完，如果判断完，转 至步骤305；如果没有判断完，转至步骤303；

步骤303：读取转换基多边形的一个顶点；

步骤304：判断顶点是否在转换相对多边形内部，如果顶点在 转换相对多边形内部，转至步骤312；如果顶点不在转换相对多边 形内部，转至步骤302；

步骤305：转换基多边形的边是否判断完，如果判断完，转至 步骤306；如果没有判断完，转至步骤307；

步骤306：判断转换基多边形与转换相对多边形是否完全重 合，如果是，转至步骤312；如果不是，转至步骤311；

步骤307：读取转换基多边形的一条边；

步骤308：判断转换基多边形的边是否与转换相对多边形的至 少一条边相互跨立，如果是，转至步骤312；如果不是，转至步骤 309；

步骤309：判断转换基多边形的边是否与转换相对多边形的两 条边相交，如果是，转至步骤310；如果不是，转至步骤305；

步骤310：判断两个交点是否为转换相对多边形的两个相邻的 顶点，如果是，转至步骤305；如果不是，转至步骤312；

步骤311：基多边形与相对多边形不重叠；

步骤312：基多边形与相对多边形重叠。

所述的步骤208中求取判断边两个端点在被判断边向量上的投 影系数，包含以下步骤：

步骤401：读取被判断边数据，记被判断边的起始端点和终止 端点分别为M、N；

步骤402：读取判断边数据，记判断边的起始端点和终止端点 分别为P、Q；

步骤403：连接点M、P构成向量端点P在被判断边向量 上的投影系数为$l_P=\frac{(\overrightarrow{\mathrm{MP}},\overrightarrow{\mathrm{MN}})}{(\overrightarrow{\mathrm{MN}},\overrightarrow{\mathrm{MN}})};$

步骤404：连接点M、Q构成向量端点Q在被判断边向 量上的投影系数为$l_Q=\frac{(\overrightarrow{\mathrm{MQ}},\overrightarrow{\mathrm{MN}})}{(\overrightarrow{\mathrm{MN}},\overrightarrow{\mathrm{MN}})}.$

本发明有如下优点：

(1)能够自动检测表面模型是否完整包络，从而为矩量法网 格划分和电磁计算所需正确模型提供了自动检查的手段；

(2)所提出的面片间缝隙、面片悬挂以及面片重叠的算法简 单、可靠；

(3)所提出的模型包络检测方法除适用于矩量法模型检测 外，也适用于其他领域有封闭性要求的表面模型检测，适应面较广。

附图说明

图1是本发明的总流程图；

图2是多边形完整包围判断流程图；

图3是多边形重叠判断流程图；

图4是求取判断边两个端点的投影系数流程图；

图5是边包围判断示例图；

图6是线段端点的投影系数计算示意图；

图7(a)、(b)是基多边形的一条边与相对多边形的两条边 相交且两个交点不是相对多边形的相邻的两个顶点时的多边形重叠 判断示意图；

图8是某表面模型示例图。

具体实施方式

本发明的几何模型为表面模型。表面模型是由三角形面片、四 边形面片围成的几何体，且三角形面片、四边形面片的顶点顺序由 模型外观察时是逆时针方向，三角形面片和四边形面片的边是有向 边。

本发明重点研究几何建模中表面模型完整包络的自动检测，检 测完成后给出一个表面模型是否完整包络的结论。

参照图1，本发明的表面模型完整包络的自动检测包括如下步 骤：

步骤101：打开由三角形、四边形面片构成的表面模型文件；

步骤102：将表面模型数据读入到tempcom_list链表中， tempcom_list链表中每一个存储单元存储一个三角形或四边形面片 数据信息；

步骤103：判断tempcom_list链表中的数据是否读完，如果读 完，说明模型的所有面片都没有缝隙、悬挂、重叠，则转至步骤 104提示模型完整包络；如果没有读完，转至步骤105；

步骤104：提示模型完整包络；

步骤105：读取tempcom_list链表中一个存储单元存储的多边 形数据，将读取出的多边形作为基多边形，基多边形表示被判断的 多边形；这里的多边形指三角形、四边形面片；

步骤106：读取tempcom_list链表中除去基多边形外其他所有 的多边形，将这些多边形依次作为相对多边形，判断相对多边形到 基多边形各条边距离为零的边是否将基多边形完整包围，如果基多 边形被完整包围，转至步骤108；如果基多边形没有被完整包围， 转至步骤107；两条边距离为零表示一条边的两个端点到另外一条 边的距离都为零，即两条边在同一条直线上；

步骤106中到基多边形各条边距离为零的边是否将基多边形的 各条边完整包围的判断方法，参照图2，包括以下步骤：

步骤201：读取基多边形的数据，参照图5，面片2为基多边 形；

步骤202：基多边形的边是否全部判断完，如果全部判断完， 转至步骤203；如果没有全部判断完，转至步骤204；如果基多边形 的边全部被判断完，说明基多边形的所有边都被完整包围，则基多 边形被完整包围；

步骤203：提示基多边形被完整包围；

步骤204：读取基多边形的一条边作为被判断边，参照图5， 边为被判断边；

步骤205：遍历tempcom_list链表，读取tempcom_list链表 中除去基多边形外的非基多边形，然后判断是否有非基多边形的边 到被判断边距离为零的边，如果有非基多边形的边到被判断边距离 为零的边，转至步骤206；如果没有，转至步骤213；参照图5，到 边距离为零的边有

步骤206：找出到被判断边距离为零的边，参照图5，找出到被 判断边边距离为零的边有

步骤207：在找到的到被判断边距离为零的所有边中删除与被 判断边方向相同的边，剩余的边作为判断边；由于多边形的边都是 有向边，与被判断边方向相同的边不可能包围被判断边，因此删除 与被判断边相同的边，参照图5，边和边与被判断边方 向相同，删除掉边和边，剩余的判断边为

步骤208：求出所有判断边两个端点在被判断边向量上的投影 系数，参照图5，判断边的端点在被判 断边上的投影系数分别记为l₁₁、l₁₂，l₂₁、l₂₂，l₃₁、l₃₂，l₄₁、 l₄₂，l₅₁、l₅₂；

步骤208中求取判断边两个端点在被判断边向量上的投影系 数，参照图4，包含以下步骤：

步骤401：读取被判断边数据，记被判断边的起始端点和终止 端点分别为M、N；

步骤402：读取判断边数据，记判断边的起始端点和终止端点 分别为P、Q；

步骤403：连接点M、P构成向量端点P在被判断边向量 上的投影系数为参照图6，由投影系数计算公 式可知，判断边的端点P在被判断边上的投影系数l_P的范围为 0＜l_P＜1，判断边的端点P₁在被判断边上的投影系数的范围 为判断边的端点P₂在被判断边上的投影系数的范围 为

步骤404：连接点M、Q构成向量端点Q在被判断边向 量上的投影系数为$l_Q=\frac{(\overrightarrow{\mathrm{MQ}},\overrightarrow{\mathrm{MN}})}{(\overrightarrow{\mathrm{MN}},\overrightarrow{\mathrm{MN}})}.$

步骤209：对每一个判断边，由两个端点的投影系数构造一个 区间，并使区间右端点值不小于左端点值；参照图5，判断边两 个端点的投影系数分别为l₁₁＝1.2215、l₁₂＝0.8591，相应区间为 [0.8591,1.2215]；两个端点的投影系数分别为l₂₁＝0.8591、 l₂₂＝0.604，相应区间为[0.604,0.8591]；两个端点的投影系数分 别为l₃₁＝0.604、l₃₂＝0.2215，相应区间为[0.2215,0.604]；两个 端点的投影系数分别为l₄₁＝0.2215、l₄₂＝-0.1342，相应区间为 [-0.1342,0.2215]；两个端点的投影系数分别为l₅₁＝-0.1342、 l₅₂＝-0.3154，相应区间为[-0.3154,-0.1342]；

步骤210：求出所有判断边对应区间的并集U，参照图5， U＝[-0.3154,1.2215]；

步骤211：判断区间U是否包含[0,1]区间，如果包含，转至步 骤212；如果不包含，转至步骤213；参照图5， U＝[-0.3154,1.2215]包含[0,1]区间；

步骤212：被判断边被完整包围，参照图5，被判断边被完 整包围；

步骤213：被判断边没有被完整包围，亦即基多边形未被完整 包围。

步骤107：提示面片之间有缝隙或面片悬挂；

步骤108：遍历tempcom_list链表，读取tempcom_list链表 中除去基多边形的非基多边形，判断tempcom_list链表中是否有与 基多边形在同一平面的非基多边形，如果有与基多边形在同一平面 的非基多边形，转至步骤109，如果没有与基多边形在同一平面的 非基多边形，转至步骤103；由于只有处在同一平面的面片才会重 叠，因此基多边形与相对多边形如果不在同一平面，则不用进行后 续判断；

步骤109：找出与基多边形在同一平面的所有非基多边形，将 与基多边形在同一平面的所有非基多边形依次作为相对多边形；

步骤110：读取基多边形的三个顶点P₁、P₂、P₃，取P₁为局部 坐标系的原点，取向量的方向为局部坐标系的X轴正方向，取 向量的方向作为局部坐标系的Z轴正方向，取向量 的方向作为局部坐标系的Y轴正方向，对基多边 形和相对多边形做世界坐标系到局部坐标系的变换，变换后基多边 形和相对多边形的z坐标全部为零，去掉基多边形和相对多边形顶 点坐标的z坐标，得到转换基多边形和转换相对多边形，转换基多 边形和转换相对多边形均为二维图形；

步骤111：求转换基多边形和转换相对多边形的轴向包围盒；

步骤112：判断轴向包围盒是否相交，如果相交，转至步骤 113；如果不相交，转至步骤103；如果包围盒不相交，则基多边形 和相对多边形一定不会重叠，就不用进行后续判断；

步骤113：判断转换基多边形和转换相对多边形是否相交，如 果相交，转至步骤114；如果不相交，转至步骤103；

步骤113中转换基多边形与转换相对多边形是否相交的判断， 参照图3，包含如下步骤：

步骤301：读取转换基多边形和转换相对多边形的数据；

步骤302：转换基多边形的顶点是否判断完，如果判断完，转 至步骤305；如果没有判断完，转至步骤303；

步骤303：读取转换基多边形的一个顶点；

步骤304：判断顶点是否在转换相对多边形内部，如果顶点在 转换相对多边形内部，转至步骤312；如果顶点不在转换相对多边 形内部，转至步骤302；

步骤305：转换基多边形的边是否判断完，如果判断完，转至 步骤306；如果没有判断完，转至步骤307；

步骤306：判断转换基多边形与转换相对多边形是否完全重 合，如果是，转至步骤312；如果不是，转至步骤311；

步骤307：读取转换基多边形的一条边；

步骤308：判断转换基多边形的边是否与转换相对多边形的至 少一条边相互跨立，如果是，转至步骤312；如果不是，转至步骤 309；

步骤309：判断转换基多边形的边是否与转换相对多边形的两 条边相交，如果是，转至步骤310；如果不是，转至步骤305；参照 图7，(a)图中转换基多边形ABCD的BC边与转换相对多边形 AEFD的AE边和FD边分别相交于点B和点C；(b)图中转换基 多边形GKI的IG边与转换相对多边形GHIJ的GH边和HI边分别 相交于点G和点I；

步骤310：判断两个交点是否为转换相对多边形的两个相邻的 顶点，如果是，转至步骤305；如果不是，转至步骤312；参照图 7，(a)图中两个交点B和C不是转换相对多边形AEFD的相邻的 两个顶点，(b)图中两个交点G和I不是转换相对多边形GHIJ的 相邻的两个顶点；

步骤311：基多边形与相对多边形不重叠；

步骤312：基多边形与相对多边形重叠。

步骤114：提示面片重叠。

仿真实例

本发明对图8所示的表面模型进行模型完整包络的检测，该模 型包含16个四边形面片和3个三角形面片，记四边形ADCB为面片 1，四边形FBCG为面片2，四边形AEHD为面片3，四边形HGCD为面 片4,四边形ABFE为面片5，四边形HEIJ为面片6，四边形IKNM 为面片7，四边形OLJP为面片8，四边形QMNR为面片9，四边形 OPSE₁为面片10,四面形SPMQ为面片11，四边形RNOE₁为面片12， 四边形QRE₁S为面片13,四边形TUSE₁为面片14，四边形KYXV为面 片15，四边形ZFWA₁为面片16，三角形LB₁C₁为面片17，三角形L C₁G为面片18,三角形C₁D₁G为面片19。

假设tempcom_list链表存储模型面片的顺序是面片1、2、3、 4、5、6、7、8、9、10、11、12、13、14、15、16、17、18、19， 经本发明检测算法的流程判断，面片1、2、3、4、5、6、7、8、 9、10、11被判断为完整包络，而进行到面片12判断时，到面片12 边距离为零的边有删除与边方向相 同的边和剩余的边和在边的投影系数对应的区 间为[l_K，l_V]、，这两个区间的并集且 l_K＜0,l_L＞1,因此并集U不包含区间[0，1]，边未被完整包围，从而面片12未被完整包围(因为面片12处有缝 隙)，检测结束。

假设tempcom_list链表存储模型面片的顺序是面片1、2、3、 4、5、6、7、8、9、10、11、13、14、12、15、16、17、18、19， 经本发明检测算法的流程判断，面片1、2、3、4、5、6、7、8、 9、10、11、13被判断为完整包络，而进行到面片14判断时，没有 到面片14的边距离为零的边，边未被完整包围，从而面片 14未被完整包围(因为面片14悬挂)，检测结束。

假设tempcom_list链表存储模型面片的顺序是面片1、2、3、 4、5、6、7、8、9、10、11、13、15、16、17、18、12、14、19， 经本发明检测算法的流程判断，面片1、2、3、4、5、6、7、8、 9、10、11、13被判断为完整包络，而进行到面片15判断时，找出 与面片15在同一平面的面片有面片6、7、8、16、17、18、19，面 片经世界坐标到局部坐标转换后，面片6、7、8的轴向包围盒与面 片15的轴向包围盒不相交，面片16的轴向包围盒与面片15的轴向 包围盒相交，并且面片15的边与面片16的边和边分别 相交于点Y和点X，且两个交点Y和X不是面片16的相邻的两个顶 点，所以面片15和面片16重叠，检测结束。