来源：第三维度
    作者：孙昱浩，尹勇，高帅
    单位：大连海事大学 航海动态仿真与控制重点实验室

    摘 要：冰区航行在实际航海活动中越来越受到人们的关注。实用性强且具有逼真仿真度的冰区航行模拟器的应用，对船员培训与航运评估等航海科学应用领域都有着很重要的实际意义。将冰区航行模拟器为整体设想框架，本文以冰区视景仿真为基本研究内容，在理论与具体实现上对冰区中海冰的模型建立与其可视化方法进行了初步的探索和研究。本文参考了Koch分形曲线的思想，分析和建立了基本的海冰模型，实现了浮冰破碎以及随波漂动效果，并借鉴了 Cohen-Sutherland等相关计算机图形学算法，实现了船舶冰区航行时海冰与船间的快速碰撞检测。

    引 言1

    在实际航海活动中，航行于冰区水域的船舶会经历各种各样与常规航海不同的风险[1]，比如通信与导航设施不足、高精度海图相对缺乏、天气恶劣等。冰区航行(Ice Navigation)会在航行定位、船舶操纵和确保安全航行等具体方面给船舶驾驶人员带来很多困难。航海驾驶操作训练在这种环境下必须要有独特的训练方式和训练内容。所以，在航海模拟器中加入冰区航行相关视景势在必行，而这其中冰区视景的仿真度与实用性会直接影响到冰区航行模拟器能否应用于冰区航行驾驶训练培训。

    研究冰区航行视景的最终目的就是完成一个仿真度高沉浸感强的航海模拟器。挪威船级社(DNV, DET NORSKE VERITAS)在 2011 年提出了航海模拟器的新认证标准[2][3]，此标准中对想要参与冰区航行培训的船舶模拟器增加了一些相关附加要求，而这其中对冰区航行模拟器中视景功能的相关要求如下：

    1) 冰区内海冰的边缘与船舶产生碰撞、固态冰体本身对船体的作用压力，以及由于破冰作用所造成的船舶失速效应等，这些形态的模拟需冰区航行水动力模型的理论支持；

    2) 动态模拟海冰冰层的厚度、冰块的形状以及它们之间的聚集度；

    3) 视景系统需要动态模拟包括破冰过程以及冰区航道的形成过程；

    4) 视景系统需要拥有各式各样聚集度厚度的大冰块和碎冰的效果显示；

    5) 尽量逼真的仿真船舶拖船操作，这其中包括仿真不同强度和弹性的船舶钢索缆绳的拖曳设备装置，以及操作人员在不同位置上的拖曳动作等相关操作；

    6) 视景系统需要动态模拟冰区航道中由于冰块的存在所引起的本船失速效应；

    7) 视景系统需要模拟显示船体探照灯。

    本文的目的就是对冰区航行模拟器中的视景系统进行可视化方法的研究，以加强提高整体系统中的环境真实感。

    1 冰区航行视景仿真的关键技术

    视景仿真的关键就是使计算机最终形成的三维动态视景尽可能地与自然界的真实景观相契合，本文以此为中心提出了以分形算法以及碰撞检测算法思想为基础的海冰建模理论以及碎冰漂浮视景的生成与应用。

    1.1 冰区航行视景中的海冰建模分析

    冰区航行视景中最主要就是海冰模型，它别于其它航海场景中的船舶、岸上建筑物以及码头堆物场等模型，因为上述模型若建立生成将不发生变化，只是在场景中显示就可以了。现实冰区中因为海冰与船舶存在交互作用和影响，海冰在船舶的碰撞下会发生破碎、漂浮等现象，这就要求海冰的模型建立必须与其相对应。

    1.2 分形算法在破冰过程场景仿真中的应用

    本文应用图形学中的分形算法主要是冰区海面上碎冰、冰区航道边缘的图形状态都与图形学中分形算法生成的图像表现十分类似，而且它相对成熟，有利于计算机程序绘图。分形算法有很多不同的曲线模型，这里不多赘述[4-6]。本文只涉及最典型的Koch曲线，如图1所示。

图1 形成 Koch 曲线模型的分图表示

  文中所提到的破冰过程是指在船舶经过冰区海域时，航行的船舶会与冰区中的冰层发生碰撞作用，整体海冰冰块区域会在碰撞后留下破碎后生成的碎浮冰以及具有不规则航道边缘的冰区航道。因为 Koch 曲线算法中所绘制出的图像效果有很强的规律重复性，若直接应用，形成的航道必然拥有规则的航道边缘如图2(a)所示，这不是被期望的。本文是需要模拟如图2(b)所示无规则边缘的冰区航道，因此需要改进Koch分形曲线生成算法。

(a)规则的冰区航道结构 (b)不规则的冰区航道结构

(c) 本文冰区航道的形成结构图
图2 冰区航道的边缘结构

    如何使用 Koch曲线逼真的模拟冰区的航道边缘，本文是这样构想的：如图2(c)所示，冰区的冰面由N个大冰块(Ice Block)组成。冰区航道的边缘是在整体海冰区域在船舶碰撞作用下碎裂后所遗留的无规律残冰组成。因为现实中的船舶破冰作用是将海冰大冰块由大变小以及由整变零的动态自然过程，本文中设想海冰 Ice Block 模型是由形状各异且支离破碎的小冰块模型拼合形成，再因为船舶的碰撞进而分离破碎。这其中小冰块的基础建模需要结合 Koch 分形算法。

    如图2(c)中第1个Ice Block所示，将其进一步放大得到Ice Block 结构俯视图 3(a)，图中的每一个红色拐点都是应用Koch 分形算法程序自动生成。但是这样生成的拐点是完全对称规律的，若直接将 Ice Block 结构图 3(a)应用于绘图程序中会得到非常规律的冰区航道边缘，如图2(a)所示。

图3 大冰块模型的结构俯视图

    为了防止这样在自然界中不会出现的规律边缘的生成，本文改进了 Koch 分形曲线模型的生成算法，本文考虑到可以在每个红色拐点上附加自然随机位置的控制，具体设想如图 3(b)所示，图中每一个拐点附近的绿色圆圈即为拐点的随机移动最大范围，拐点的位置在圆圈内随机选取。这样限定范围的随机位置生成算法经过实际绘图程序测试效果如图4所示，其中图 4(a)是通过原始 Koch 分形算法程序绘制的航道边缘图，图 4(b)是改进 Koch 算法后绘制的航道边缘图，其效果更加贴近自然景象。

图4 Koch 算法改进前后对比图

    1.3 小浮冰的建模仿真

    由于船舶破冰作用，生成的浮冰在冰区航行视景中，主要依靠一下两个参数进行表现：

    (1)浮冰模型的形状与大小；

    (2)浮冰在冰区航道中随波漂浮的速度与场景位置。

   小浮冰在自然界中是各种各样没有固定形状的，这就需要在虚拟仿真程序中必须有很强的自然随机性来体现它的形状与大小。

    本文是这样构想的：假设小浮冰在冰区航道中的形状大小是在一定范围内动态随机生成，其在航道内的漂浮过程中可以在一定条件下组成各式各样的大的浮冰形状，进而可以很好的模拟出现实中浮冰的状态。具体来说，假设每块浮冰是由 N 个基本点构成其表面形状，本文以小于等于 8 个点为例进行分析研究，图 5、6 所表现的即为 N≤8 时由基本点构成的浮冰表面形状结构。为了有利于绘图程序设计，指定了这 N 个点在单位图形中的顺序排列，其中 ~ 按顺时针方向排列于坐标系内 X 轴和 Y 轴的一侧， ~ 按顺时针方向排列在坐标系内 X 轴和 Y 轴的另一侧，并且规定了每个基本点的最大随机移动范围(绿色虚线圈以内)。

图5 每个浮冰中各基础点的随机活动范围示意图

    在小浮冰建模过程中，第一步需要确定生成随机小浮冰表面图形点的个数 C(本文规定其随机数目范围为 3~8)，这些基本点是构成随机小浮冰图形的基础，然后按上文顺序连接这C个点。如图6所示，(1)为3个点构成的小浮冰图形、(2)为4个点构成的小浮冰图形……以此类推，可以产生三角形到八边形这六种基本浮冰图形。

图6 单位基础点构成浮冰的随机形状，从三角形到八边形

    由于每个生成的小浮冰的基本点的数目、位置，小浮冰的旋转方向，小浮冰的面积大小等都是可以通过浮冰绘图程序随机生成，这就使得小浮冰在冰区视景中的图形种类更加丰富全面，基本没有完全类同的形状。最终绘制的可视化效果图如图7 所示。

图7 结合分形算法，简单仿真模拟浮冰的各种形状

    对于浮冰在冰区航道中速度与位置的分析研究，由于海水中的浮冰是随波漂浮着的，所以其运动规律是可以按照海浪的运动规律加以微调而形成。关于海浪的运动仿真相关的内容不是本文的重点，请参考相关资料[7,8]。

    1.4 碰撞检测的引入和应用

    本文涉及的主要视景模型(船舶模型和海冰模型)是存在相互作用的，需要实时地在三维场景中进行模型与模型之间的碰撞检测。怎样选择一个实时性和实用性都很高效的碰撞检测算法是对于冰区航行视景是至关重要的，本文对此作出了如下的分析与研究。

    1.4.1 碰撞检测算法在冰区航行视景中的分类

    本文中的碰撞检测按类型可以分为：、

    1) 大冰块(Ice Block)与本船之间的碰撞；

    2) 细分后小冰块与本船之间的碰撞；

    3) 航道内浮冰与本船之间的碰撞。

    为尽量提高碰撞检测算法的工作效率，节省程序运行时间，提高程序的实时性，本文将复杂三维模型之间的碰撞检测进一步简化表达为二维图形图像之间的重合判断。对于上文中提到的三种碰撞类型，分别应用了不同的检测算法，具体实现方法下面予以一一阐述。

    1.4.2 基于 Cohen-Sutherland 算法的碰撞检测

    因为本文中的海冰模型是由很多个立方体大冰块(Ice Block)模型按一定顺序排列构成，这些大冰块模型经本文1.2节所述方法细分为有着分形规律的三角网格模型，如图8 所示。由于海冰的整体区域非常大，为提高碰撞检测算法的工作效率，本文将Cohen-Sutherland算法首先应用于检测船轮廓线构成的多边形与组成初始海冰区域的四边形网格之间的碰撞效应。

图8 海冰模型中细分后的随机三角网格图

    Cohen-Sutherland 算法在计算机图形学 (Computer Graphics)[9]中主要是应用于窗口与线段之间的裁剪变换，作者在算法中加以改进变化，在本文中使该算法成为一个适合于大面积海冰模型并且具有较高效率的碰撞检测算法。如图 9(a)将本船的水线面轮廓线规定为一组线段的序列组合，海冰与本船碰撞时，将单位海冰模型看作计算机图形学中四边形的裁剪窗口，线段序列作为被裁减线段，若形成裁减条件，即定义为碰撞，循环应用Cohen-Sutherland算法。若碰撞发生，如图8所示四方体冰块用细分后的小碎冰代替，一部分散落漂浮在海面上形成海面浮冰，另一部分附着在相邻大冰块上形成不规律的冰区航道边缘。

图9 两次碰撞检测示意图

    1.4.3 三角形小冰块与船轮廓线之间的碰撞判断

    使用Cohen-Sutherland算法碰撞检测的结果是标记将要破碎的 Ice Block 的位置，再对其进行第二次检测，即应用于破碎细分后的三角形小冰块网格和本船之间碰撞判断。

    结合图 9 对于大冰块模型破碎细分后的碰撞检测判断可分解成两种类别：

    冰区航道中每个三角形小冰块与本船船首三角部分的检测判断，在计算机图形学中可以理解为成三角形与三角形之间的相交判断。

    每个三角形小冰块与本船船体部分的碰撞检测，在计算机图形学中可以理解为成三角形与四边形之间的相交判断。

    针对类别[1]，本文使用的是点与三角形之间的位置判断方法，即判断某个点是否在已知三角形的区域内。计算机图形学中相关的判断算法有很多，本文采取的是点与三角形解析几何函数判断法[10]：

    设需判断的三角形三个点位置坐标为：

    故，三角形三条边的直线解析方程为：

    以BC边为例，在三角形ABC内的点必须与点A在BC边的同一侧。所以对任意点D(x, y)，只需比较以下三个式子，判断 O、P、Q 的符号，即可以判断点 D 与三角形 ABC 之间的位置关系：

    根据公式(4)~(6)，判断如下：

    1) O、P、Q 的三个值至少有一个负数，则 D 点在三角形ABC外；

    2) O、P、Q的三个值都为正数，则D点在三角形ABC内；

    3) O、P、Q的三个值中有且只有一个0，另外两个为正数，则D点在三角形ABC的边上；

    4) O、P、Q的三个值为一个正数一个0一个负数，则D 点在三角形 ABC 边的延长线上，也算在三角形外，因为其结果满足结论1)；

    5) O、P、Q 的三个值有二个是 0，则 D 点在三角形ABC的顶点上；

    6) 不可能出现一个0两个负数，或三个负数，或三个0的情况。

    上文算法只用于点与三角形的位置判断，为确保判断的正确性与完整性，需对冰块三角形模型与船首三角形模型进行双向检测，其具体做法是先遍历船首三角形的顶点对三角形小冰块进行检测判断，然后再遍历三角形小冰块的顶点对船首三角形进行检测判断，若在程序中出现重合现象则标记为碰撞发生。

    针对类别[2]，可以把本船的船体部分看作类似矩形截面加以检测，这样的话检测程序就可以转换为判断矩形与三角形之间的重合，再将此状态转换为三条有序线段同四边形裁剪窗口之间的位置判断，进而还可以继续使用上文中提到的Cohen-Sutherland 算法加以检测，循环遍历检查船舶周围的三角形小浮冰的边缘与矩形船体四边形之间的位置关系，这至于本船与航道中浮冰之间的碰撞检测，由图6所示，小浮冰的基本形状是由多个基本三角形和四边形组成，同样可使用上文提到的Cohen-Sutherland改进算法与本节的算法相结合，然后再循环遍历检测本船周围的小浮冰。

    2 冰区航行视景集成

    本章节在上一章节的基础上使用 VC+OSG 开发引擎，以OpenGL为图形接口语言，对相关类进行了程序设计，编程实现了海冰模型的动态构建，以及在船舶作用下的海冰破碎过程和冰区航道内船冰之间的碰撞检测，并实现了浮冰漂浮等相关视景效果，最终效果如图10所示，其中(a)(b)图为不同视角。

图10 集成效果图

    3 总结

    冰区航行视景的仿真是冰区航行模拟器的重要组成部分，本文建立了基本的海冰模型并应用了改进后的 Koch分形曲线模型，提出了一种针对冰区航道内浮冰建模与仿真的方法，并且将计算机图形学中的Cohen-Sutherland算法思想应用于船舶轮廓线与冰区内海冰冰块模型之间的碰撞检测运算，完成了船舶模型在冰区航行时与海冰模型的快速碰撞检测，提高了算法效率，最后应用三维场景管理引擎在理论和应用上基本实现了冰区视景的可视化，同样也验证了文中提到的相关算法理论。这样就可以完成本船与大冰块之间的碰撞检测部分。

    参考文献:

    [1] John Tucker, Anthony Patterson, Glenn Fiander, Carl Harris, Don Spencer. Simulation and Modeling of Navigating in Ice [C]// International Navigation Simulator Lecturers’ Conference (INLSC-14)，July 3-7, 2006.

    [2] DET NORSKE VERITAS (DNV). Standard for Certification No.2.14 Maritime Simulator Systems January 2011[R]. DNV Press, 2011. 1.

    [3] 金一丞, 尹勇. STCW公约与航海模拟器的发展[J]. 大连海事大学学报, 2002, 28(3): 53-55.

    [4] http://baike.baidu.com/view/609817.htm[EB/OL]

    [5] 李敏. 几种分形算法的Mathematic实现[J]. 长江大学学报(自科版)理工卷, 2007,4(2): 138-139

    [6] 袁杰. 分形算法与应用研究[D]. 哈尔滨: 哈尔滨工程大学, 2002.

    [7] 尹勇, 任鸿翔, 张秀凤, 金一丞. 航海仿真虚拟环境的海浪视景生成技术[J]. 系统仿真学报, 2002, 14(3): 313-315.

    [8] 任鸿翔, 尹勇, 金一丞. 大规模海浪场景的真实感绘制[J]. 计算机辅助设计与图形学学报, 2008, 20(12): 1617-1621.

    [9] Donald Hearn, M. Pauline Baker. 计算机图形学 [M]. 第2 版. 北京: 电子工业出版社, 2002.

    [10] http://blog.csdn.net/leishiwei/archive/2009/03/20/4009193.aspx[EB/OL].