一种基于优化路径规划算法的刚性折纸折叠方法

摘要

本发明涉及计算机图形种动态折叠路径规划领域，具体涉及一种基于优化路径规划的刚性折纸折叠方法。将所有折叠角的集合作为一个配置空间，建立刚性折纸折叠模型；确定折纸在折叠过程的折叠运动的完整性。基于优化的RRT路径规划构建折叠路径，即结合RRT的随机性的特征和利用B样条曲线来对模型某条折叠边进行平滑处理，从而使刚性折纸折叠序列稳定性的可控度更高。本发明结合平滑曲线改进折叠路径规划方法，用于初步对选取折痕线折叠路径进行规划和平滑并减少折叠过程中折痕线在折叠过程中的形变量；提出一种基于B‑spline Curve优化刚性折纸折叠路径方法，融合刚性折纸折叠路径规划与折叠路径平滑，解决缺乏折叠稳定性的问题。

说明书

技术领域

本发明涉及计算机图形种动态折叠路径规划领域，具体涉及一种基于优化路径规划的刚性折纸折叠方法。

背景技术

随着计算机技术不断发展，机器人在人类生活工作中应用不断增多。在机器人技术中，折纸被研究人员用作一种手段加深对运动控制和规划方法的理解。路径规划在折纸的折叠过程起到关键的作用。目前来看，存在的路径规划方法主要有A*方法、Dijkstra方法等。但大多数的路径规划方法不适合在高维复杂空间应用。在运用过程中，像A*方法对于启发函数的选择要求较高，必须要选择适合的启发函数才能有较好的效果。Dijkstra方法搜索的效率比较缓慢，复杂度高并且运算成本高。

基于采样快速扩展随机树(RRT)是用于路径规划的新方法之一，与其他用于路径规划如A*方法、Dijkstra方法等传统办法相比，它具有概率完备性和收率速度较快的优点，但是他搜索过于均匀，它得到的路径常常与最短路径有较大的偏差。在此基础上有改进的算法，比如RRT

发明内容

针对现有技术中存在的问题，本发明提出了一种基于优化路径规划算法的刚性折纸折叠方法，利用B样条曲线来对折痕线进行平滑处理，得到一条平滑的路径，提高了对折叠角度折叠序列的稳定控制。

为实现上述发明目的，本发明的具体技术方案如下：一种基于优化路径规划算法的刚性折纸折叠方法，包括如下步骤：

S1)建立刚性折纸折叠模型；

S2)基于优化RRT算法和刚性折纸折叠模型规划刚性折纸折叠运动的路径；

S2.1)选定起点X

S2.2)基于RRT算法扩展搜索树T；

S2.3)对刚性折纸的折叠面进行自交检测，得到刚性折纸折叠模型每个状态所有折痕线角度集合，并生成一条初始的刚性折纸折叠路径；

S3)对S2)中得到的折叠路径进行优化；

S3.1)通过B样条曲线对刚性折纸折叠路径上的折痕线线进行平滑处理,

在配置空间

其中，Q

S3.2)对刚性折纸折叠路径的折痕线初始折叠角度集合进行更新；

将S3.1中平滑处理后的折痕线折叠角度集合替换S2.3中初始刚性折纸折叠路径中的折痕线初始折叠角度集合，最终得到一条经平滑处理后新的刚性折纸折叠路径。

进一步地，上述步骤S1中刚性折纸折叠模型包括以下步骤：

S1.1)用折痕线l

其中，l

S1.2)用矩阵运算形式来表示刚性折纸在空间中的折叠过程，将公式(2)的计算结果与一个1*4的矩阵相乘即得出V

其中，V

进一步地，上述步骤S1.2)中的矩阵B

进一步地，所述步骤S2.2)中基于RRT算法扩展搜索树T具体包括以下内容：

在搜索空间区域内随机产生一个X

其中，X

进一步地，上述步骤S2.3中的自交检测包括以下步骤：

将不同形状的多边形折纸面片拆分成三角面片，设三角形1中一条边为p

p

进一步地，上述步骤S3.1)中三次B样条曲线的基函数具体计算过程为：

C(u)＝Q

其中公式(11)就是三次B样条曲线方程，其中Q

本发明的有益效果如下：

1、结合平滑曲线改进折叠路径规划方法，用于初步对选取折痕线折叠路径进行规划和平滑并减少折叠过程中折痕线在折叠过程中的形变量；

2、提出一种基于B-spline Curve优化刚性折纸折叠路径方法，融合刚性折纸折叠路径规划与折叠路径平滑，解决缺乏折叠稳定性的问题。

附图说明

图1为基于优化RRT算法的刚性折纸折叠方法总流程图。

图2为基于RRT算法扩展搜索树展示图。

图3为刚性折纸折叠面之间的自交检测原理图。

图4为刚性折纸模型一条折痕线进行B样条曲线拟合前后对比图。

图5为刚性折纸模型平滑前后初始状态下和目标状态的刚性折纸模型图。

具体实施方式

下面结合附图和实施实例对本发明作进一步描述。

如附图1所示为本发明的总流程图，包括以下步骤：

S1)建立刚性折纸折叠模型；

作为本发明的优选实施例，步骤S1中刚性折纸折叠模型包括以下步骤：

S1.1)我们使用A

其中，l

S1.2)用矩阵运算形式来表示刚性折纸在空间中的折叠过程，将公式(2)的计算结果与一个1*4的矩阵相乘即得出V

其中，V

作为本发明的优选实施例，步骤S1.2)中的矩阵B

S2)基于优化RRT算法和刚性折纸折叠模型规划刚性折纸折叠运动的路径；

S2.1)首先选定起点X

S2.2)确定初始搜索树后，基于RRT算法扩展搜索树T；

作为本发明的优选实施例，步骤S2.2)中基于RRT算法扩展搜索树T具体包括以下内容：

在搜索空间区域内随机产生一个X

其中，X

S2.3)对刚性折纸的模型折叠面进行自交检测，得到每个状态所有折痕线角度集合，并生成一条初始的刚性折纸折叠路径；

作为本发明的优选实施例，步骤S2.3中的自交检测包括以下步骤：

将不同形状的多边形折纸面片拆分成三角面片，如附图3所示，设三角形1中一条边为p

p

作为本发明的优选实施例，步骤S3.1)中三次B样条曲线的基函数具体计算过程为：

C(u)＝Q

其中，公式(11)为三次B样条曲线方程，Q

根据其递推公式如上式(11)可知，基函数与节点元素的分布以及曲线的阶数有关，而与控制点独立，本发明将使用全部折叠路径节点作为控制点，我们选取一条需要平滑的折痕线，利用三次B样条曲线对特定控制曲线进行拟合，如附图4所示，刚性折纸模型某条折痕线进行B样条曲线拟合前后对比图。生成单条连续的参数化轨迹，为了使得曲线经过指定起点和终点，令节点两端元素均匀分布，这使得我们折纸的折叠曲线有更加良好的局部可修性。

S3)对S2)中得到的刚性折纸折叠路径进行优化；

S3.1)通过B样条曲线对刚性折纸折叠路径上的折叠线进行平滑处理,

在配置空间

其中，Q

S3.2)对刚性折纸折叠路径的折痕线初始折叠角度集合进行更新：

将S3.1中平滑处理后的折痕线折叠角度集合替换S2.3中初始刚性折纸折叠路径中的折痕线初始折叠角度集合，最终得到一条经平滑处理后新的刚性折纸折叠路径。如附图5所示，表示刚性折纸模型平滑前后从初始状态折叠到目标状态对比图。