﻿ 基于自适应三角化的船舶曲面分段网格细分
 舰船科学技术  2018, Vol. 40 Issue (6): 25-28 PDF

Ship plate section surface mesh segmentation based on adaptive triangulation
LI Chun-jin, YANG Qiu-lin
Jiangsu University of Science and Technology, Zhenjiang 212003, China
Abstract: Combined with the theory of unstructured meshing, the advantages and disadvantages of existing delaunay triangulation and subdivision algorithm are analyzed.Aim at the precision propertie of Ship curved piecewise division to the features rather than the calculation efficiency,the mesh segmentation of ship surface is changed by changing the step value in the adaptive algorithm, and then the meshes are subdivided by Delaunay triangulation. After adaptive gridding, Of the surface of the final triangulation. At the end of this paper, the ship curved surface segmentation is taken as an example to verify the correctness of the subdivision algorithm by comparing with the curvature cloud image which is estimated by the curved surface,which has certain practical significance in the field of ship surface shell expansion.
Key words: ship curved piecewise     delaunay     adaptive segmentation
0 引　言

1 Delaunay三角网格化 1.1 Delaunay定义

Delaunay三角网格划分为数值分析及图形学方面重要技术手段，如图1所示，Delaunay三角网格是将空间测量数据点投影到平面来实现的二维划分法。算法基本思想为每一个Delaunay三角形的外接圆内部不包含其他结点，一旦检测到三角形外接圆含有其他结点后，就必须修改局部的网格划分，直至满足起始条件为止。

 图 1 Delaunay三角网格示意图 Fig. 1 Sketch map of Delaunay triangular grid
1.2 Delaunay三角网格划分算法

Delaunay三角网格划分步骤为：

1）构造大外接圆 ${G_0}$ ，使其包含所有结点，进行步骤2；

2）每次导入一个结点，重复进行步骤3～步骤5；

3）找出已有三角形中哪些外接圆包含新引入的结点，转步骤4；

4）删除这些三角形中离新结点最近的一条边，转步骤5；

5）将新结点与老结点连接，产生新的三角形，算法示意图如图2所示。

 图 2 三角划分步骤3～步骤5示意图 Fig. 2 Schematic diagram of triangulation step 3 ~ step 5

2 细分曲面算法

2.1 蝶形算法

 $a = 1/2,b = 1/8 + 2w,c = - 1/16 - w{\text{。}}$ (1)

 图 3 蝶形算法模型示意图 Fig. 3 Butterfly algorithm model diagram
2.2 多面体算法

 图 4 多面体算法示意图 Fig. 4 Schematic diagram of polyhedron algorithm
2.3 Loop算法

Loop算法是一种逼近细分算法，其算法步骤主要分为3步，首先生成边界点，之后移动原有顶点，最后生成光滑表面（切平面连续）。

 $V_0^{k + 1} = 1 - n\beta V_0^k + \beta \mathop \sum \limits_{i = 1}^n V_i^k,$ (2)
 $V_0^{k + 1} = \frac{1}{8}\left( {3V_0^{k + 1} + V_{i - 1}^k + 3V_i^k + V_{1 + i}^k} \right),i = 1, \cdots \cdots ,n,$ (3)

 $\begin{array}{l}\left[\!\!\!\!\!\!\!\!\!\!\!\!\! {\begin{array}{*{20}{c}}{V_0^{k + 1}}\\{\begin{array}{*{20}{c}}{V_0^{k + 1}}\\{\begin{array}{*{20}{c}}{V_0^{k + 1}}\\ \vdots \end{array}}\\{V_0^{k + 1}}\end{array}}\\{V_0^{k + 1}}\end{array}}\!\!\!\!\!\!\!\!\!\!\!\!\! \right] = \frac{1}{8}\left[\!\!\!\!\! {\begin{array}{*{20}{c}}{8 - 8np}\!\!&\!\!{\begin{array}{*{20}{c}}{8\beta }\!\!&\!\!{8\beta }\!\!&\!\! \cdots \end{array}}\!\!&\!\!{8\beta }\!\!&\!\!{8\beta }\\{\begin{array}{*{20}{c}}3\\3\\ \vdots \end{array}}\!\!&\!\!{\begin{array}{*{20}{c}}{\begin{array}{*{20}{c}}3\!\!&\!\!1\!\!&\!\! \cdots \!\!\end{array}}\\{\begin{array}{*{20}{c}}1\!\!&\!\!3\!\!&\!\! \cdots \!\!\end{array}}\\{\begin{array}{*{20}{c}} \vdots \!\!&\!\! \vdots \!\!&\!\! \cdots \!\!\end{array}}\end{array}}\!\!&\!\!{\begin{array}{*{20}{c}}0\\0\\ \vdots \end{array}}\!\!&\!\!{\begin{array}{*{20}{c}}1\\0\\ \vdots \end{array}}\\3\!\!&\!\!{\begin{array}{*{20}{c}}0\!\!&\!\!0\!\!&\!\! \cdots \!\! \end{array}}\!\!&\!\!3\!\!&\!\!1\\3\!\!&\!\!{\begin{array}{*{20}{c}}1\!\!&\!\!0\!\!&\!\! \cdots \!\!\end{array}}\!\!&\!\!1\!\!&\!\!3\end{array}}\!\!\!\!\! \right] \left[\!\!\!\!\!\!\!\! {\begin{array}{*{20}{c}}{V_0^k}\\{V_1^k}\\{\begin{array}{*{20}{c}}{V_2^k}\\ \vdots \\{V_{n - 1}^k}\end{array}}\\{V_n^j}\end{array}}\!\!\!\!\!\!\!\! \right]{\text{。}} (4)\end{array}$

3 自适应三角网格划分算法（ATM） 3.1 ATM算法思想

1）提取船舶型值表数据，通过B样条工具进行参数化曲面重构，得到参数化曲面 $r\left( {u,v} \right)$

2）选定曲面适当区域，在参数化曲面 $u,v$ 方向上选取相向的2条曲线，从一端的顶点开始搜索，计算步长两端点弦长或者弧长（估算值）差的绝对值，将其值称为弦弧差；

3）设定弦弧差许用范围，将步骤2得到的值与弦弧差范围比较，如果在弦弧差范围之内，记录步长，并生成划分用网格线，否则步骤4；

4）调整步长重新判断，直至满足弦弧差范围；

5）重复步骤2～步骤4，直到搜索至边界的终点；

6）所有搜索完毕后得到的是四边形网格，此时进行Delaunay三角化生成细分网格。

3.2 步长划分准则

3.1节所述ATM算法步骤适用于矩形参数域。对于非矩形参数域而言，需要先对曲面进行扩展补充，通过 $uv$ 方向的最大与最小参数值 ${u_{\max }},{v_{\max }},{u_{\min }},{v_{\min }}$ 确定一个矩形域，此矩形域为原先非矩形参数域的最小外接矩形域。

$u$ 向网格划分为例，如图5所示，原先参数域为非矩形参数域，建立如图的 $uv$ 坐标系，通过最大参数值 ${u_{\max }},{v_{\max }}$ 及最小参数值 ${u_{\min }},{v_{\min }}$ 构建最小外接矩形参数域，包含原有的多边形域 $p_1p_2p_3p_4p_5$ 中所有点。Bb之间距离的绝对值为划分的步长值，将其与设定的弦弧差范围比较。

 图 5 步长自适应划分示意图 Fig. 5 Step size adaptive division diagram

3.3 步长关系调整

 图 6 实际弦弧差与许用弦弧差关系图 Fig. 6 The actual chord arc and allow the use of chord arc diagram

1）在情况1中，实际的弦弧差范围均处于许用弦弧差范围内， ${\delta _{\min }} \geqslant {\varepsilon _{\min }}$ ${\delta _{\max }} \leqslant {\varepsilon _{\max }}$ ，满足判断条件，可以记录步长，生成网格划分线，并进行下一步搜索；

2）在情况2中，实际弦弧差与许用弦弧差关系为 ${\delta _{\min }} < {\varepsilon _{\min }}$ ${\varepsilon _{\min }} < {\delta _{\max }} < {\varepsilon _{\max }}$ ，此时需要加大步长，在其满足判断条件后记录步长，生成网格划分线；

3）在情况3中，实际弦弧差最大值小于许用弦弧差最大值，关系为 ${\delta _{\min }} < {\varepsilon _{\min }}$ ${\varepsilon _{\min }} < {\delta _{\max }} < {\varepsilon _{\max }}$ ，跟情况2的不同之处在于此时实际弦弧差最大值 ${\delta _{\max }}$ 接近于许用弦弧差 ${\varepsilon _{\max }}$ ，不能加大步长，记录步长，生成网格划分线；

4）情况4中实际弦弧差与许用弦弧差关系为 ${\delta _{\min }} > {\varepsilon _{\min }}$ ${\delta _{\max }} > {\varepsilon _{\max }}$ ，此时需要缩小步长，使得 ${\delta _{\max }} \leqslant {\varepsilon _{\max }}$ ，即满足情况1或情况3的状态，当满足这个条件时记录步长，并生成网格划分线；

5）情况5中实际弦弧差与许用弦弧差关系为 ${\delta _{\min }} < {\varepsilon _{\min }}$ ${\delta _{\max }} < {\varepsilon _{\max }}$ ，此时需要增大步长值，在其满足判断条件后记录步长，生成网格划分线；

6）情况6中实际弦弧差与许用弦弧差关系为 ${\delta _{\min }} > {\varepsilon _{\max }}$ ，此时需要缩小步长，记录步长，在其满足判断条件后记录步长，生成网格划分线；

7）情况7中实际弦弧差与许用弦弧差关系为 ${\delta _{\min }} < {\varepsilon _{\min }}$ ${\delta _{\max }} > {\varepsilon _{\max }}$ ，此时减少步长值，使其达到情况3的状态。

4 实例应用

 图 7 船舶曲面分段网格细分实现流程图 Fig. 7 Flow chart of segmentation of ship surface

 图 8 船舶外板曲面实例效果图 Fig. 8 Effect of the outer surface of ship

 ${\varepsilon _j} = \frac{{\mathop \sum \nolimits_{i = 1}^v \frac{{\left| {{S_i} - {s_i}} \right|}}{{{S_i}}}}}{{{v}}}{\text{。}}$ (5)

5 结　语

 [1] 李承铭, 卢旦. 自由曲面单层网格的智能布局设计研究[J]. 土木工程学报, 2011, 3: 1–7. [2] 丁慧. 自由形态空间网格结构的网格设计方法研究与实现[D]. 杭州: 浙江大学, 2014. [3] 江存. 自由曲面空间网格结构网格划分、优化及力性能研究[D]. 杭州: 浙江大学, 2015. [4] 陈永就, 林川. 基于直接剖分的球面四边形离散格网生成方法[J]. 地理空间信息, 2015, 3: 130–132+12. http://www.cnki.com.cn/Article/CJFDTOTAL-JSJF200201012.htm [5] 卫洪春. 多边形三角剖分与三角细分的研究与实现[J]. 计算机与现代化, 2015, 7: 65–68, 76. http://www.cqvip.com/QK/97264X/201507/665337864.html [6] 石磊, 薛珊. 基于三角形网格的几种典型细分曲面方法概述[J]. 赤峰学院学报(自然科学版), 2013, 14: 13–14. http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=cfxyxb201314007 [7] LI Qi-rui. Surfaces expanding by the power of the Gausscurvature flow[J]. Proceedings of the American Mathematical Society, 2010.