基于CAE模型的船舶舱室自动识别高效算法

章志兵，杨明润，王丽荣，陈有芳

（1.华中科技大学，武汉 430074；2.中国船级社技术研究中心，北京 100007）

船舶舱室识别是船舶设计的关键环节，是船舶有限元分析（CAE）和船舶结构性能校核（Structure Design Program, SDP）的基础[1—2]，因此，提高舱室识别效率和准确性，增强识别过程的自动性，对于船舶设计具有重大意义。

针对舱室识别问题，国内外学者研究提出了众多典型解决方案。单威俊等[3—5]提出了“切分拼接”方法，首先利用自由边过滤舱室内部结构，再根据船舶相交结构的特征，定义一系列规则，将模型切分成一块块舱室面，最后将舱室面拼接成舱室空间。该方法具有较高的自动性，但对船舶特征依赖性强，对于不同类型的船舶，需要定义不同的识别规则，并且经实验验证，识别准确率仅能达到60%，需要大量的人工干预，才可做到准确识别全船的舱室，并且识别效率不高，以大型油船、散货船为例，识别船体中单个舱室即需要耗费5 min。LEE S U等[6]采用自顶向下方法，利用分割面，进行布尔运算，将整个船体模型逐步切分，直至识别出所有舱室。该方法识别准确率高，但属于半自动方法，需要人工干预操作。在4万t的大型船舶上进行实验，表明该船体识别出所有舱室模型，需耗费约1 h。KONINGH D等[7]提出一种新的模型切分方法，混合使用体与平面来划分船体模型，简化了舱室建模过程，提高了舱室识别准确率，但自动化程度不高，需要人工进行图形交互操作，导致效率难以有突破性提高。

文中利用一种新思路，将舱室抽象识别为三维模型中的封闭空间，基于半边半面模型，定义了封闭空间的方向。以此为基础，提出了时间复杂度O(n)（n为模型中半面的数量）的半面扩展算法，利用模型拓扑关系和空间坐标数值计算，可高效识别出种子半面所属的极小封闭空间。在半面扩展算法基础上，实现了高效的舱室自动识别算法。

1 半边半面模型

CHEN H，LI Guang-ming，DANOVARO E 等[8—13]的研究表明，半边数据结构在三维模型的网格简化、模型切割方面具有良好的性能表现，并且易于拓展成紧凑性数据结构，在大规模模型处理中可节省较多的存储空间。DYEDOV V，RAY N等[14—16]的研究表明，半面数据结构在网格面细化、曲面重构方面具有良好的性能表现。为了提高舱室识别算法的可拓展性，在该算法中使用半边半面数据结构来表示几何元素，使该算法将来可融合于多种功能模块中。

一条无向边可拆分为两条方向相反的有向边。将有向边称为半边（Half-edge）。同一条无向边拆分成的两条方向相反的半边互为伴随半边（Accompany half edge）。

如图1所示，无向边e被拆分为Eh0和Eh1两条有向边，Eh0和Eh1互为伴随半边。无向边e具有两个端点v0和v1。半边Eh0的起点为v0，终点为v1；半边Eh1的起点为v1，终点为v0。

在半边模型基础上，可将一个无向面拆分为两个方向相反的有向面，有向面的方向根据组成该面的半边方向由右手定则确定。将有向面称为半面（Half-face）。同一个无向面拆分成的两个方向相反的有向面互为伴随半面（Accompany half face）。若半边Eh参与构成半面Fh，则称半面Fh包含半边Eh、半边Eh属于半面Fh。

图1 半边定义Fig.1 Definition of half-edge

如图2所示，无向面f被拆分为Fh0和Fh1两个有向面（为了图示清晰性，无向面f未在图中画出），Fh0和Fh1互为伴随半面。半边Eh0，Eh2，Eh4，Eh6构成半面Fh0，属于半面Fh0。半边Eh1，Eh3，Eh5，Eh7构成半面Fh1，属于半面Fh1。半面Fh0，Fh1的方向根据半边方向由右手定则确定。

图2 半面定义Fig.2 Definition of half-face

张奇华等基于拓扑学原理，提出了“有向性”和“封闭性”的概念[17]。在此基础上，结合半边半面模型，将封闭空间定义为由一组有向面围成的封闭区域，其中每个有向面的方向都指向该封闭区域内部。该定义相较于使用无向面定义封闭空间，具有以下优点：①提供了一种统一的封闭空间特征，可利用该特征，设计更简洁高效的封闭空间识别算法；② 使得相邻的封闭空间之间不再存在公共面，使所有的封闭空间相互独立，从设计上降低数据结构耦合；③ 利用组成封闭空间的有向面的方向，易于判断一个三维空间坐标是否处于封闭空间内部，提高算法可扩展性。

2 CAE船舶舱室自动识别算法

舱室识别算法总流程如图3所示。

Step 1：获取模型的所有face及face包含的edge元素。

Step 2：建立CAE模型的拓扑关系，并创建半边半面数据结构存储拓扑关系。

Step 3：取一个尚未被访问的半面作为种子半面；若不存在未被访问的种子半面，则结束。

Step 4：识别种子半面所属的极小封闭空间。使用半面扩展算法，以种子半面为始，向相邻半面扩展，并递归执行该过程，识别出所有属于该封闭空间的半面。

Step 5：存储识别结果。以一个新的半面数组存储表示该封闭空间。回到 Step3，递归地执行舱室识别过程。

Step 6：采用半自动方式剔除船体外部空间。程序标识出半面数量最多的一个极小封闭空间，用户可确认该空间为船体外部空间；或用户手动点选船体外壳上的一个半面，程序识别出该半面所属的极小封闭空间，标识为船体外部空间。

图3 舱室识别算法总流程Fig.3 Flow of cabin identify algorithm

2.1 CAE模型拓扑关系建立

船舶舱室是由一组面组成的封闭空间区域，封闭空间的边界面构成流形拓扑，因此要求在舱室识别过程中，能够通过给定的面获取其边界线，并通过边界线获取其连接的面，即给定的面相邻的面。

在船舶CAE模型中，曲线段已被离散为分段的直线段，曲面已被离散为空间2D单元[18]，可将空间2D单元视为face，则舱室为由一组face组成的封闭空间区域。

在文中舱室识别算法中，需要建立的拓扑关系有：半面与半边的包含关系；半边与半边的伴随关系。

如图4所示，半面Fh0包含半边Eh0，Eh1，Eh2，Eh3；半面Fh1包含半边Eh4，Eh5，Eh6，Eh7；半边Eh1与Eh5互为伴随半边，并由此可推断出半面Fh0与半面Fh1相邻。

对于模型中每个空间 2D单元表示的无向小平面，创建两个方向相反的有向半面，并创建每个半面包含的半边。

图4 CAE模型拓扑关系示意图Fig.4 Diagram of CAE model topology relationship

为了建立半边的伴随关系，对每个半边的起点和终点构成的二元组（Star point，end point）进行编码，使得二元组（Star point，end point）的编码与二元组（End point，star point）的编码互为相反数，并且所有编码均不为 0。使用 Hash表进行存储，以二元组编码作为 Key，以半边数组作为 Value。创建每个半边时，设该半边的编码为x，则将该半边加入Key为x对应的Value半边数组中，并在Hash表中查询半边编码为−x的半边，记录半边伴随关系。

2.2 半面扩展算法

半面扩展算法用于识别三维模型中由半面构成的封闭空间。算法根据一个种子半面，识别出其相邻半面，并保证了被选择的相邻半面与种子半面属于同一封闭空间。递归执行上述过程，可识别出模型中与种子半面属于同一封闭空间的所有半面，即构成该封闭空间的所有半面。

图5a所示为三维网格模型的局部示例，图5b展示了该示例在二维视角下的半面扩展过程，即以空间内一个半面为起始，逐渐向周围半面搜索扩展，直至搜索出该空间内的所有半面。

图5c所示为半面扩展过程的一个详细示例。在本例中，以半面Fh0为种子半面，识别出其相邻半面中与Fh0处于同一封闭空间的半面Fh1，Fh2，Fh3，Fh4。递归执行半面扩展过程，以半面Fh1为种子半面，识别出半面Fh5，Fh6，Fh7；以半面Fh2为种子半面，识别出半面Fh8和Fh9；以半面Fh3为种子半面，识别出半面Fh10和Fh11；以半面Fh4为种子半面，识别出半面Fh12。不断递归执行此过程，直到识别出该封闭空间的所有半面为止。

种子半面在一个半边处可能存在多个相邻半面，针对该情况，文中提出了“半面匹配规则”。根据该规则，给定种子半面及其一条半边，可识别出种子半面在该半边处相邻的所有半面，并选择一个匹配的相邻半面，该半面与种子半面属于同一个封闭空间。在下文中，将该过程称为“半面匹配过程”。

如图5d和5e所示，从不同视角可看出半面Fh2与Fh13均与半面Fh0相邻，但以半面Fh0为种子半面进行半面扩展时，通过半面匹配规则判断，半面Fh2与Fh0处于同一极小封闭空间，故扩展到半面Fh2而没有扩展到半面Fh13。

如图6所示，种子半面为Fhseed，半面Fhseed的指定半边为Eh0。半边Eh0的伴随半边Eh1，Eh2，Eh3（为了图示清晰性，半边Eh2，Eh3未在图中画出）所属的半面分别为Fh1，Fh2，Fh3，共3个半面，这些半面称为半面Fhseed在半边Eh0处的相邻半面，其中半面Fh3为种子半面Fhseed的伴随半面。如图6b所示，以半边Eh0为轴，按照半面Fhseed的方向，从半面Fhseed到半面Fh1，Fh2，Fh3的有向角分别为θ1，θ2，θ3，角度值的范围为(0，2π]。

图5 半面扩展算法示意图Fig.5 Diagram of half-face expansion algorithm

图6 半面匹配规则示意图Fig.6 Diagram of half-face matching rule

半面匹配规则描述如下：对于给定的半面半边二元组（Fhseed，Eh0），其中半面Fhseed为种子半面，Eh0为Fhseed的一条半边，半面集合FH中的所有半边Fhi均为半边Eh0关联的半边所属的半面。其中集合FH一定不为空集，因为种子半面Fhseed的伴随半面必定属于集合FH。以半边Eh0为轴，按照Fhseed方向从半面Fhseed到集合FH中半面Fhi的有向角为θi，则种子半面Fhseed在半边Eh0处的匹配半面为最小有向角θj对应的半面Fhj。半面Fhj与种子半面Fhseed处于同一封闭空间。

例如在图示 6b中，θ1为最小有向角，根据该规则，种子半面Fhseed在半边Eh0处所匹配的半面为Fh1。

如3.1节所述，在舱室识别算法总流程中，使用半面扩展算法识别出种子半面所属的封闭空间。半面扩展算法流程如图7所示。

Step 1：新建一个半面数组，表示种子半面所属的封闭空间，用于存储识别出的半面。

Step 2：新建一个半面队列。在半面扩展算法执行过程中，该队列中的半面状态为：已被识别出属于当前封闭空间，但尚未执行以该半面为种子半面的半面匹配过程。

Step 3：将种子半面加入队列尾部，并标记为已访问。

Step 4：判断队列是否为空。若队列为空，则半面扩展算法过程结束；否则继续执行半面扩展算法。

Step 5：从队列首部取一个半面作为种子半面，并从队列中将其删除。

图7 半面扩展算法流程Fig.7 Flow of half-face expansion algorithm

Step 6：执行半面匹配过程。根据半面匹配规则，识别出种子半面相邻的、尚未被访问的、属于同一封闭空间的半面。

Step 7：将 Step 6中识别出的半面加入半面队列，后续作为种子半面递归地执行半面匹配过程。将其标记为已访问，防止后续被重复加入队列，导致冗余计算。

Step 8：将Step 5中取的种子半面加入表示该封闭空间的半面数组。回到Step 4，递归地执行半面扩展过程。

分析可知，在识别过程中，对模型中的每个半面，仅进行了常数次访问；由于船舶模型中任何半面包含的半边仅有常数个，且任何半边的伴随半边仅有常数个，故半面匹配过程耗时为O(1)，所以舱室识别过程的时间复杂度为O(n)，已达渐进最优，其中n为模型中半面的总个数。

3 应用实例

在NX11.0平台上，以C++语言实现文中的CAE舱室自动识别算法，并使用多种船体模型进行测试。测试计算机CPU为Intel Core i5-6400 2.70 GHz，内存容量为8 GB，操作系统为64位。

图8所示为一个18万t大型散货船CAE模型，图9所示是对该模型的舱室识别结果。该模型共有CAE单元329 509个，识别结果共有1190个封闭空间。

经多次重复测试，测量算法中“建立拓扑关系”、“识别舱室”两部分的耗时情况，测量结果为：建立拓扑关系耗时约3.2 s；识别舱室耗时约0.5 s，总耗时约4 s。

分析测试结果可以发现，建立CAE模型拓扑关系过程耗时较多，因为该过程涉及大量的内存申请、赋值操作，且半边查找总过程平均情况时间复杂度为O(n)，最坏情况时间复杂度为O(nlogn)（其中n为模型中半边的总个数）；识别舱室过程耗时较短，因为仅仅涉及数值计算和数据结构的调用，且该过程时间复杂度为O(n)（其中n为模型中face的总个数）。从算法复杂度角度可证明该识别算法的高效性。

图8 18万t大型散货船CAE模型示意图Fig.8 Diagram of CAE model for 180,000 tons large bulk carrier

图9 大型散货船CAE模型舱室识别结果示意图Fig.9 Diagram of CAE model cabin identification results for large bulk carriers

对比测试使用NX系统内置的船舶模块中的舱室识别功能。该功能需要选择种子点，一次识别种子点所在的单个舱室，使用二次开发方式利用该功能循环识别出所有舱室，并使用计时工具仅累积测量识别过程的耗时，排除其他因素影响。利用上述模型重复测试，结果表明，识别出所有舱室耗时约180～200 s。

测试结果表明，该算法效率较高，18万t大型散货船CAE模型的舱室识别仅耗时4 s；识别准确率较高，所有CAE舱室都已准确识别，无遗漏部分、无多余部分。

4 结语

提出了一种半面扩展算法，并基于此提出了CAE舱室自动识别算法。经实际工程项目应用检验表明，算法具有很高的效率和准确性；算法可拓展性强，在该算法基础上，易于拓展出船舶舱室的相关功能，例如，识别舱室边界构件和内部构件、识别舱室中的型材、舱室合并等。该算法可广泛应用于船舶 CAE系统中，提供舱室相关构件的高效、准确的识别功能。本质上，该算法是对三维模型中封闭空间的识别，可预期在未来应用于各类三维建模系统中。