基于Voronoi图的动态虚拟场景可见性计算方法

项目名称： 基于Voronoi图的动态虚拟场景可见性计算方法

项目编号： No.61070093

项目类型： 面上项目

立项/批准年度： 2011

项目学科： 金属学与金属工艺

项目作者： 杨承磊

作者单位： 山东大学

项目金额： 11万元

中文摘要： 课题主要以三维室内虚拟世界的实时绘制与漫游为背景，以多边形的Voronoi图为空间划分方法与场景表示模型，重点研究快速有效的可见性计算方法，提出了基于Voronoi图的潜在可见集的数据结构，给出了可快速查询点、线段、区域以及移动点的可见信息的系列算法。并针对其中的预处理步骤中计算潜在可见集的需要，提出了多边形的Voronoi图点定位的O(logn)算法，提出了NURBS曲线的弱可见多边形计算方法，以及点的可见性计算方法。提出了层次化Voronoi图数据结构，以此为基础提出了速度快、空间节省的优化Voronoi骨架路径、最短路径计算方法。并研究开发基于多触控技术与Voronoi图的博物馆设计与漫游系统，以便集成上述算法。 另外，还提出一个一致分布点集Delaunay三角化最佳期望时间算法；提出基于流算法的海量三维点云模型的三角网格表面重构算法；提出一种计算分割两个平面点集的最小数目分割圆的算法。对于一般曲面，提出了一个基于二次重新参数化的优化算法来改进曲面的参数化。针对NURBS曲面上G1连续近似曲线的生成，提出了一个基于三次重新参数化的抛物线近似算法。

中文关键词： Voronoi图; 可见性计算; 路径规划; 点定位

英文摘要： This project researched how to speed up rendering virtual indoor scenes such as virtual museums. It used Voronoi diagrams of polygons(VDP) to represent indoor virtual scenes. Based on VDP , it presented a data structure called the potentially visible sets of VDP, based on which, efficient algorithms were designed to fast query the visibility information in the polygon for a point, a line segment, a region and a moving view point when the users roaming in the virtual worlds. To compute the potentially visible sets of VDP, a point-location data structure and an algorithm were created to query the Voronoi region containing a query point in O(logn) time, an algorithm was presented to compute the weak visibility polygons of NURBS curves inside simple polygons, and an algorithm to find the visibility polygon of a point based the subdivision of a polygon. It also gave some methods to compute skeleton paths and (approximate) shortest paths based on VDP. Based on these work and the multi-touch technology and VDP, a system for designing and roaming digital museums is being designed. An improved algorithm of Delaunay triangulation is also presented. Compared with the existed algorithms, it is more efficient and extends the region of the sites distributed from unit sphere to any convex polyhedron. It also presented a memory and time efficient surface reconstruction algorithm for large sets of points, without normal information, that may not fit within the main memory. Given two sets of points R and B, it presented an approximation algorithm for computing the set with minimal number of separating circles, satisfying the condition that every point in R is covered by at least one circle and each point in B is not covered by any circle. For a general surface, it presented an optimization algorithm to improve the surface parameterization based on the quadratic reparameterization. To generate G1 continuous approximate curves lying completely on the NURBS surfaces, it presents a parabola approximation method based on the cubic reparameterization.

英文关键词： Voronoi diagram; visibility; path planning; point location