基于Delaunay三角剖分的机器人工作空间体积求解

(辽宁工程技术大学 机械工程学院，辽宁 阜新 123000)

并联机器人因刚度大、精度高、结构紧凑、承载能力强等特点[1]而被广泛应用。并联机构工作空间体积与形状对于并联机构的工作能力有重要关系，因此并联机构工作空间体积通常作为判断机构好坏的指标[2-4]，采用更加便捷的方法求解工作空间体积具有重要意义。并联机器人工作空间三维体积计算常见方法有：微分法[5]，即运用平行于X-Y面的平面将工作空间分割成厚度为ΔZ的微元，计算出每一微元的体积并将所有微元体相加得到的便是机构的工作空间体积；子空间体积叠加法[6]，对Z值一定，厚度为ΔZ的子空间在X-O-Y平面投影并计算每个投影的面积，将面积相加并与剖面距离相乘可得到体积值。上述方法为求解并联机构工作空间体积提供了理论依据，但在实际操作中，由于工作空间的不规则性，求解误差较大且需要对数据进行排序筛选等操作，编程及求解过程麻烦，运算量较大。

Delaunay三角剖分法[7]是比较成熟的方法，已广泛应用在各领域图像和点云的处理上。刘洋[8]采用Delaunay三角剖分法对路面点云进行分析处理，提升了路面三维建模的效率。博志成[9]等人采用Delaunay三角剖分法对海量点云曲面进行重建，提升了重建效率和重建曲面拓扑正确性。鲍鑫[10]引入了Delaunay三角剖分法，将声压级映射为颜色，并绘制成图像，实现对噪声的实时监控。

Delaunay三角剖分法对点云数据处理具有优势，为解决此问题，本文采用Delaunay三角剖分法计算体积值，并进行实验对比，结果表明该方法有效的减少了计算量，提升了体积计算的效率。

1 3-RPS并联机器人建模及仿真

3-RPS并联机器人主轴平台是基于Stewart并联机构原理[6]，机构的结构简图如图1所示。本文采用欧拉角方法[7-8]对机构的特点对其进行几何分析，进行逆解运算。

图1 并联机构坐标系示意图

经计算，可得到3个驱动杆杆长在定坐标系A中的矢量为

(1)

则各驱动杆杆长为

li=|Li|

(2)

3-RPS并联机构是一种少自由度并联机构，其工作空间是指可达工作空间[9]，影响其大小、形状的主要因素[10]有：

(1) 杆长的限制。

lmin≤li≤lmax

(3)

式中，li为支杆i的长度；lmin、l为支杆i的最小、最大长度。

(2) 运动副转角限制。

① 球副转角限制。

(4)

式中，Li为驱动杆方向向量；sbi为球副底座的方向向量；θsimax为球副i的最大许用转角；θsi为球副i的转角。

② 转动副转角限制。

(5)

式中，Li为驱动杆方向向量；si为转动副底座方向向量；θRimax为转动副i最大许用转角；θRi为球副i的转角。

(3) 连杆干涉。

(6)

式中，Ri为转动副i的位置向量；Li为连杆i的方向向量；D为连杆截面直径；Mi为相邻两连杆中心线之间的最短距离。

本文采用搜索法求解3-RPS并联机构的可达工作空间。首先设定尺寸参数，然后确定搜索初值，在某个Z截面上搜索满足约束条件的姿态角α，β；再以增量形式改变Z的值，直到遍历搜索完Z最小值到最大值范围之间所有的截面。3-RPS并联机构的结构尺寸以及工作空间约束条件如表1所示。

表1 并联机构结构参数与转角约束

借助Matlab编程求解可得工作空间如图2所示，并获得1348320个点坐标。

图2 工作空间三维图

2 Delaunay三角剖分相关理论

三角剖分中以Delaunay三角剖分最具有代表性,本节主要介绍相关的Delaunay三角剖分理论和改进的增量式Delaunay三角剖分法算法[11]。

2.1 Delaunay三角剖分的定义及准则

Delaunay边：假设E中的一条边e(两个端点为a,b)，e若满足下列条件，则称之为Delaunay边：存在一个圆经过a,b两点，圆内不含点集V中任何其他的点，这一特性又称空圆特性。

Delaunay三角剖分：如果点集V的一个三角剖分T只包含Delaunay边，那么该三角剖分称为Delaunay三角剖分。

要满足Delaunay三角剖分的定义，必须符合两个重要的准则。

① 空圆特性：Delaunay三角网是唯一的(任意4点不能共圆)，在Delaunay三角形网中任一三角形的外接圆范围内不会有其他点存在。如图3所示。

图3 空圆特性图

② 最大化最小角特性：在散点集可能形成的三角剖分中，Delaunay三角剖分所形成的三角形的最小角最大。从这个意义上讲，Delaunay三角网是“最接近于规则化的”的三角网。具体说是指在两个相邻的三角形构成凸四边形的对角线，在相互交换后，6个内角的最小角不再增大。如图4所示。

图4 最大化最小角特性图

2.2 算法

① 先构建一个初始四面体，形成初始化四面体网格。

② 将散乱点插入当前四面体网格中，对于输入点P，使用随机行走方法来寻找包含P的四面体。先指定一个四面体T，如果P位于该四面体内，则完成行走。如果不在四面体内，则随机指定一个三角面E，如果E所在的平面将T和P分割开(即T和P在平面的两边)，下一个访问的四面体就是共享E的邻近四面体；否则，就按预定的顺序遍历其他的面，直到找到分割开T和P的面。

③ 找到包含P的四面体，则分割该四面体为4个小四面体。

④ 如果P位于当前四面体网格外，则选择网格的一个可见面(即P在面的一侧)，连接P与该三角面的3个顶点构成新的四面体加入到四面体网格中，选择可见面时，尽量避免使新生成的四面体是狭长的。

⑤ 重复步骤②～步骤④，直到所有散乱点都被插入四面体网格。

(6) 验证Delaunay三角剖分的有效性。首先检Delaunay三角剖分数据结构的连贯性，即四面体的邻接关系。

3 工作空间体积求解

基于改进的增量式Delaunay三角剖分法，对图2中并联机器人工作空间点云进行了计算，并与二值化处理求解算法和微元法进行实验对比。

3.1 子空间体积叠加法求解工作空间体积

子空间体积叠加法是借助Matlab中图片处理工具箱(Image Processing Toolbox)，对Z值一定，厚度为ΔZ的子空间在X-O-Y平面投影的不规则图像增加规则边框，然后进行二值化处理[12]。

假设规则图形的面积为S，二值化处理后可以求出不规则图形像素点数占规则图形像素点的比值η，那么可以求得Z值对应的子空间的面积为ΔS=S·η，那么此子空间的体积为ΔV=ΔS·ΔZ，则整个工作空间的体积为

(7)

求解过程可用图5表示。

根据本文的3-RPS并联机构参数，按照上述方法计算每一幅截面图面积，然后求和。在相同电脑配置下，编写Matlab程序求得其体积V=6.2639×105mm3，耗时27 min。

3.2 微元法求解工作空间体积

微元法是运用平行于X-Y面的平面将工作空间分割成厚度为ΔZ的微元，计算出每一微元的体积，将所有微元体相加得到的便是机构的工作空间体积，如图6所示。

令Δρ、Δφ分别为极坐标中的极径和极角的搜索步长，阴影部分面积可以表示为

(8)

工作空间某一截面面积为

图6 体积求解示意图工作空间某一截面面积为

(9)

该截面对应的微元体积为

ΔV=ΔS·ΔZ

(10)

工作空间总体积为

(11)

根据本文的3-RPS并联机构参数，采用微元法编写Matlab程序，计算得到其体积值V=6.2643×105mm3，并耗时31 min。

3.3 Delaunay三角剖分法求解工作空间体积

采用改进的增量式Delaunay三角剖分法进行编程对并联机器人工作空间点云进行三维Delaunay三角剖分生成四面体，如图7所示。

图7 空间散点四面体化示意图

利用convexhull凸包处理函数将所得四面体数据进行分析，得到最外围的凸包，并按着顺序对凸包边界上的点进行排列。同时也直接给出了凸包的体积或者面积。根据本文的3-RPS并联机构参数，采用基于增量式Delaunay三角剖分的改进算法编写Matlab程序计算其体积值V为6.2645×105mm3，并耗时21 min。

以基础算法微元法计算的数值为标准值，则二值法和Delaunay三角剖分法的相对误差分别为6.38×10-3%和3.19×10-3%，由此可知Delaunay三角剖分法的相对误差较小。

4 结束语

针对传统二值化处理法求解并联机器人工作空间体积法的流程，采用改进的Delaunay三角剖分法，本方法通过对空间的散点进行三维Delaunay三角剖分生成四面体，进而求得其体积，与二值化处理法和微元法相比，改进的增量式Delaunay三角剖分法相对误差较小，耗时少，即改进的增量式Delaunay三角剖分法降低了编程难度并提高了计算效率。