基于手绘草图的感兴趣漫游路径快速生成算法

系统仿真学报 ›› 2016, Vol. 28 ›› Issue (3): 577-583.

基于手绘草图的感兴趣漫游路径快速生成算法

黄东晋, 唐鹏斌, 丁友东

上海大学上海电影学院,上海 200072

收稿日期:2014-10-20 修回日期:2014-12-16 发布日期:2020-07-02
作者简介:黄东晋(1982-), 男, 浙江温州, 博士, 讲师, 研究方向为虚拟现实、计算机图形学、物理仿真等。
基金资助:
国家自然科学基金(61402278, 61303093);上海市自然科学基金(14ZR1415800);上海市科技攻关项目(14511108400);上海市教委科研创新项目(14YZ023);2015年度上海大学电影学高峰学科

Fast Generating Algorithm of Interest Roaming Path Based on Freehand Sketch

Huang Dongjin, Tang Pengbin, Ding Youdong

Shanghai Film Academy, Shanghai University, Shanghai 200072, China

Received:2014-10-20 Revised:2014-12-16 Published:2020-07-02

摘要/Abstract

摘要： 结合智能终端的触摸交互的特点,提出了基于手绘草图的感兴趣漫游路径快速生成算法,并应用于移动三维交互式虚拟展示系统。该算法通过特征点自适应精简方法对草图曲线特征点进行优化,解决特征点局部过多的问题;采用分段曲线拟合的办法处理草图路线经过障碍物的情况,快速生成光滑的避障路线,并通过误差控制使得最终的漫游路径尽可能地逼近手绘草图。实验结果表明,该算法自动生成的用户感兴趣漫游路径使得整个虚拟漫游过程的方位、速度和视角变化过渡自然,具有较好的稳定性和实时性。

关键词: 虚拟漫游, 手绘草图, 曲线拟合, 路径规划, 误差控制

Abstract: Considering properties of touch interaction of intelligent terminals, a fast generating algorithm of interest roaming path based on freehand sketch was proposed and applied in the 3D mobile interactive system of virtual display. The self-adapting reduce method was adopted to optimize the feature points of sketch curve for addressing too much feature points in local. The piecewise curve fitting method was used to quickly generate smooth obstacle avoidance path for handling the case of sketch line over the obstacle, and the final roaming path was adjusted to approximate the freehand sketch as much as possible by error control. Experimental results show that the orientation, velocity and visual angle have changed naturally in whole process of virtual roaming along the generated interest roaming path with better performance in stability and real time.

Key words: virtual roaming, freehand sketch, curve fitting, path planning, error control

中图分类号:

TP391.9

黄东晋, 唐鹏斌, 丁友东. 基于手绘草图的感兴趣漫游路径快速生成算法[J]. 系统仿真学报, 2016, 28(3): 577-583.

Huang Dongjin, Tang Pengbin, Ding Youdong. Fast Generating Algorithm of Interest Roaming Path Based on Freehand Sketch[J]. Journal of System Simulation, 2016, 28(3): 577-583.

参考文献

[1] J Fish, S Scrivener.Amplifying the mind's eye: Sketching and visual cognition[J]. Leonardo (S0024-094X), 1990, 23(1): 117-126.
[2] R E Korf.Depth-first iterative deepening: an optimal admissible tree search[J]. Artificial Intelligence (S0004-3702), 1985, 27(1): 97-109.
[3] S Basu Roy, G Das, S K Das.Algorithms for computing best coverage path in the presence of obstacles in a sensor field[J]. Journal of Discrete Algorithms (S1570-8667), 2012, 13(5): 86-97.
[4] 张彪, 曹其新, 王文珊. 使用三维栅格地图的移动机器人路径规划[J]. 西安交通大学学报, 2013, 47(10): 57-61.
[5] A A Masoud.Motion planning with gamma-harmonic potential fields[J]. IEEE Transactions on Aerospace and Electronic Systems (S0018-9251), 2012, 48(4): 2786-2801.
[6] H T Hsieh, C H Chu.Improving optimization of tool path planning in 5-axis flank milling using advanced PSO algorithms[J]. Robotics and Computer-Integrated Manufacturing (S0736-5845), 2012, 29(6): 3-11.
[7] R Kala.Multi-robot path planning using co-evolutionary genetic programming[J]. Expert Systems with Applications (S0957-4174), 2012, 39(3): 3817-3831.
[8] 姜映映, 田丰, 王绪刚, 等. 基于模板匹配和SVM的草图符合自适应识别方法[J]. 计算机学报, 2009, 32(2): 252-260.
[9] X Z Sun, W Jiang, J Y Sun.Adaptive online multi-stroke sketch recognition based on hidden markov model[C]// Proceedings of the 4th International Conference on Machine Learning and Cybernetics, Guangzhou, China. USA: Springer (Daniel S. Yeung, et al), 2005: 948-957.
[10] 刘伟, 查建中, 徐晓慧, 等. 用RCR特征和NN识别实时手绘工程草图[J]. 计算机辅助设计与计算机图形学学报, 2003, 15(6): 692-696.
[11] 李路, 周良, 丁秋林. 基于贝叶斯网络的草图符号识别研究[J]. 计算机科学, 2011, 38(6): 262-265.
[12] M A Esther.An efficient computable metric for comparing polygonal shapes[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence (S0162-8828), 1999, 13(3): 209-216.
[13] 王卫, 尹建峰, 孙正兴. 一种手绘草图的快速参数化方法[J]. 计算机科学, 2006, 33(1): 264-268.
[14] L Kara, K Shimada.Construction and modification of 3d geometry using a sketch-based interface[C]// Proceedings of Eurographics workshop on sketch-based interfaces and modeling. Vienna, Austria: Eurographics Association (T Stahovich, et al), 2006: 59-66.
[15] 褚标, 朱功勤. 基于增量方法的均匀B样条曲线快速生成算法[J]. 计算机工程与应用, 2006, 42(14): 9-10.