Voronoi图在随机聚合网屏和路径规划中的应用研究

论文摘要

Voronoi图是计算几何的一种仅次于凸包的重要几何结构,也是计算几何的重要研究内容之一。由于Voronoi图具有最近性、邻接性等众多性质和比较系统的理论体系,如今已经在图形学、机械工程、地理信息系统、虚拟现实、机器人、图像处理、CAD等领域得到广泛应用,也是解决距离计算、碰撞检测、路径规划等计算几何其它问题的有效工具。本文利用Voronoi图理论,对路径规划,随机聚合网屏等问题做了深入研究。本文路径规划问题的主要研究背景是虚拟博物馆漫游。一般的,虚拟漫游方式分为两种:一种是指定路径的漫游,另一种是交互方式的漫游。传统的鼠标、键盘指引式的交互方式,漫游方式比较单一,用户只能通过不断的用鼠标、键盘调整方位从而达到漫游的目的。指定路径的漫游一般是先记录一些路径,在用户漫游时再选择这些路径进行漫游。这种方式需要程序员预先设定,用户参与度低。由于我们研究开发的虚拟博物馆是以平面多边形的的Voronoi图作为几何数据结构的,所以本文重点的是在平面多边形的的Voronoi图已知的情况下,如何快速、有效提供几种路径进行漫游。本文主要研究了offset路径,skeleton路径以及最短路径三种路径规划方式,该三种路径漫游方式可以大大提高用户对于路径漫游的参与度,系统根据用户指定的漫游目的地可以快速的计算相应的漫游路径,满足不同用户的不同漫游需要。其中的最短漫游路径规划问题涉及到了平面最短路问题。欧几里德最短路径问题是计算几何中最重要也是最为人所知的问题之一。在本文中我们关注的是一类简单的最短路问题,即:简单多边形内任意两点s,t间的最短路径SP(s,t)。常见的算法大都基于经典的Dijkstra算法,Dijkstra算法能得出最短路径的最优解,但效率较低,算法的最坏时间复杂度为D(n~2)。另外,在印刷印染行业如何用单个或少数几个颜色来印制连续的丰富色彩是一个基本和难点的问题。目前,工业上常用调幅网屏技术来实现。但是这种技术在印刷中会产生明显的干扰图案,不同角度和频率的网屏叠加时也会产生龟纹,印刷质量难以保证。随机网屏(调频网屏)代表了彩色印刷的另外一种方案,能产生比传统网屏更细微的颗粒,这种方法允许叠加多于3层而不会产生龟纹,可表现更加丰富的颜色及灰度过渡层次以及更加细腻的图象细节。在本文的研究中,我们结合Voronoi图理论和图形处理器(Graphic Process Unit)技术提出了一种新的随机聚合网屏生成算法。该算法生成的网屏,可以表现更加丰富细腻的图像信息,且速度上比传统算法有了很大的提高。通过调节参数,还可以改变网点大小,以适应不同的印刷设备与印刷需求。归纳的,本文的创新和贡献在于:1.提出了一种基于Voronoi图计算简单多边形P内任意两点s,t间的最短路径的算法。该算法首先找到s,t间的Voronoi骨架路径S(s,t),以及骨架路径S(s,t)上的关联内尖点与关联边;然后沿着骨架路径S(s,t)进行可见性计算,逐步求得s,t间的最短路径SP(s,t)。该算法的时间复杂度为O(n)。2.给出了三种基于多边形Voronoi图的路径规划方法:即offset路径、skeleton路径、最短路径等。其中的offset路径利用了多边形的offset曲线,使用户在选择漫游整个场景的同时可以选择自己需要的观察角度。skeleton路径利用了多边形Voronoi图的Voronoi骨架作为路径的主干,使用户可以任意选择游览目的地,最短路径采用了本文中提出的多边形内任意两点间的最短路径的算法,使用户经过最短的距离即可到达目的地。此三种路径规划方法大大提高了虚拟场景中交互式漫游的灵活性,丰富了漫游方式,满足用户的不同漫游需要。3.提出了一个基于GPU的随机聚合网屏生成算法。算法首先构造了一个大的抖动矩阵,随机放置中心网点;然后根据离散点集的Voronoi图的最近性、邻接性利用GPU计算每个中心网点的最大覆盖区域;最后利用GPU对每个网点的覆盖区域进行灰度填充,得到一个大的阈值矩阵,也就是我们的随机聚合网屏。算法中可以通过参数,改变网点的大小,使其可以适应不同的印刷设备。验证明,采用这种方法生成的随机网屏对高分辨率的印刷设备效果更好,可以表现更为细腻的层次和灰度。这些工作可以应用于山东大学的“数字博物馆应用支撑平台”和“集成化计算机辅助图案设计与制版系统”,有重要的理论意义和实际应用价值。

论文目录

• 摘要
• ABSTRACT
• 第一章 引言
• 1.1 Voronoi图
• 1.2 路径规划
• 1.3 随机聚合网屏
• 1.4 本文工作
• 1.5 本文组织方法
• 第二章 相关知识
• 2.1 Voronoi图
• 2.2 数字半色调技术
• 2.2.1 基本概念
• 2.2.2 研究现状
• 2.3 GPU技术
• 2.4 最短路径
• 第三章 基于Voronoi图的最短路径计算
• 3.1 基本概念
• 3.2 算法思想与步骤
• 3.3 算法分析与总结
• 第四章 基于Voronoi图的路径规划
• 4.1 offset路径
• 4.2 skeleton路径
• 4.2.1 skeleton路径计算
• 4.2.2 算法分析与小结
• 4.3 最短路径
• 4.4 总结
• 第五章 基于Voronoi图的随机聚合网屏算法
• 5.1 随机聚合网屏算法
• 5.2 网点的随机放置
• 5.3 基于CPU的网点Voronoi化
• 5.4 利用CPU填充网点的最大覆盖区域
• 5.5 算法实验结果与分析
• 5.5.1 算法时间分析
• 5.5.2 网屏质量分析
• 5.6 总结
• 第六章 总结与展望
• 参考文献
• 致谢
• 攻读学位期间发表的学术论文
• 学位论文评阅及答辩情况表