-
Voronoi图 (简称V图) 因其自然邻近、动态稳定等特性，已在GIS领域得到广泛应用[1-3]。近年来，随着数字地球的发展，球面V图成为GIS领域的研究热点之一，并被应用到全球空间索引、球面插值、球面动态操作等重要领域[4]。很多学者提出了球面V图的生成算法，但是，大多数算法都是基于矢量数据模型，如插入算法[5-7]、扫描算法[8]、投影算法[9]等，这些算法都仅考虑了球面点集的V图。文献[10]利用分解的思想，将“点-线”模型[11]扩展到球面上，把复杂实体分解为点和线等简单实体来生成V图。这种方法虽然能够生成线、面等复杂实体的V图，但所用的数据结构和计算过程十分复杂，不利于全球海量数据的多层次表达[4]。文献[12]将球面偏置曲线应用到球面V图生成中，该方法虽然能够生成球面不同集合之间的矢量V图，但在大数据量的处理方面有一定的局限性，同样不利于全球海量数据的处理。
近年来，一些学者提出了基于栅格的球面V图生成算法，如基于四元三角网 (quaternary triangular mesh, QTM) 的算法[4, 13-14]和球面六边形格网算法[15-16]，这两种算法利用球面多边形扩张生成点集、线集和面集的V图。然而，由于球面流形空间中多边形划分的不规则性，生成球面V图的误差呈不规律分布[4, 13-14](与格网的位置有关) 且无法控制，这严重影响了球面V图的应用。
随着可编程图形处理器 (graphics processing unit，GPU) 的发展，为提高生成效率，一些学者提出了基于GPU的V图生成算法[17-20]，但大多数为生成平面V图的算法，很难扩展到球面上[21]。文献[21]利用2D几何图像，将文献[17]提出的变步长扩张算法 (jump flooding algorithm，JFA) 扩展到球面及其他表面上进行质心Voronoi剖分 (centroidal Voronoi tessellation, CVT)，但没有阐述如何利用JFA生成球面线集和面集的V图。文献[22]提出了一种基于GPU的经纬独立扫描算法，将球面在经度-纬度参数域上参数化并离散映射到二维平面网格中，进行距离变换并生成球面V图，但由于球面经纬格网的不均匀性，该算法从赤道到两极存在着精度的变化。
本文根据QTM的离散特征及内在并行特性，提出了一种球面V图的GPU并行生成算法，用距离的计算与比较代替传统的扩张操作来减少生成球面V图的误差，同时利用GPU并行计算来提高算法的效率。
-
本文算法是以球面V图定义为基础的，因此本节首先给出了基于QTM的球面V图的定义，并以此为基础对算法的原理及并行方法进行阐述。由于算法本身仅涉及到了球面点集，且计算结果仅为球面上格网的最近种子点集合，因此本节也给出了线、面等复杂数据集的处理方法和Voronoi边界提取方法。
-
给定一个区域、一系列的实体si(i=1, 2, 3, …, n) 和一个距离函数d，则实体si的Voronoi区域Vi可定义为：
$$ \begin{align} & {{V}_{i}}=\left\{ \omega \in \mathit{\Omega} \left| d\left( \omega ,{{s}_{i}} \right) < d\left( \omega ,{{s}_{j}} \right) \right., \right. \\ & \ \ \ \ \ \ \ \ \ \ \ \ \ \left. \forall {{s}_{j}}\mathit{ \in \Omega} ,i\ne j \right\} \\ \end{align} $$ (1) 对于一个平面区域，距离d可以为欧氏距离，但对于球面，距离d应定义为大弧距离：
$$ \begin{align} & d=\text{rarccos}\left( \cos {{\varphi }_{1}}\cos {{\varphi }_{2}}\cos \left( {{\lambda }_{1}}-{{\lambda }_{2}} \right)+ \right. \\ & \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \left. \sin {{\varphi }_{1}}\sin {{\varphi }_{2}} \right) \\ \end{align} $$ (2) 式中，(λ1, φ1) 和 (λ2, φ2) 为球面上两点的经纬度；r为球的半径。
如果将式 (1) 中的距离函数d定义为式 (2) 所示的大弧距离，ω定义为QTM格网，Ω定义为整个球面，则式 (1) 所表述的即为基于QTM格网的球面V图。
根据定义，生成球面V图的最关键步骤是为球面上每一个格网找到距离它最近的种子点，以确定它所属的Voronoi区域。本文采取的方法为：将球面按QTM的形式剖分后，遍历所有格网，依次计算每个格网到所有种子点si(i=1, 2, 3, …, n) 的球面距离，并通过比较得到距该格网最近的种子点，作为它的最近种子点。如图 1所示，格网A为球面上任一格网，a、b、c和d为种子点，依次计算格网A到种子点a、b、c和d的球面距离，并通过比较获得最近的种子点 (种子点c)。当对所有的格网计算完成后，所有具有相同最近种子点的格网构成该种子点的Voronoi区域。
图 1 算法原理示意图
Figure 1. Diagram of the Algorithm
-
由算法原理可知，本文算法在生成球面V图时，需要计算球面上每个格网到所有种子点的距离，具有计算密集性的特点。同时，针对每个格网所进行的计算都是相同的，且不同格网之间互不影响，具有指令一致性和相互独立性的特点。因此，本文采用GPU单指令多数据流 (single instruction multiple data, SIMD) 的并行计算模型来执行这些计算。首先，设计一个能够在GPU中执行的核函数，然后启用一定数量的线程 (线程的数量与球面上格网的数量相同，每个线程对应一个格网) 来执行这个函数，线程和它将要处理的数据 (格网) 之间通过线程编号进行索引。
GPU中的全局内存具有较大的存储空间，但访问速度较低。相反，共享内存的存储空间较小，但其访问延迟仅有全局内存的1%左右。由于种子点数据和格网中心点数据量较大，只能存储在全局内存中。设种子点数为N，球面上QTM格网总数为G，则生成球面V图所需要的计算和比较的总次数为2NG，由于对每个格网的计算都需要获取到所有的种子点数据，因此所需要的全局内存访问的次数为 (G+NG)，二者之比为2 NG: (G+NG)≈2:1。即每进行两次计算 (或比较) 就需要进行一次全局内存的访问，这将严重影响算法的效率。因此，在实现过程中，本文采取如下策略：首先将格网中心点数据和种子点数据存储在全局内存中，每次从中取出部分种子点数据存储在共享内存中，供该线程块内的所有线程使用。当该部分种子点数据使用完成后，再取出一部分种子点数据进行计算，依次进行，直至所有的种子点都计算完毕。若每个线程块中的线程数量为B，则每个线程块内所要进行的计算和比较的总次数为2NB，需要进行的全局内存访问次数为 (B+N)(包括从全局内存中取出B个QTM格网数据和N个种子点数据)，则计算 (或比较) 的次数与全局内存访存次数之比为2NB:(B+N)=2N:(1+N/B)。若取N=1 024、B=256，则计算与访存次数之比为2 048:5≈400:1，这样就可以减小全局内存访问的次数，从而提高算法的效率。具体实现的流程图如图 2所示。
图 2 Voronoi图并行生成算法流程图
Figure 2. Flowchart of the Parallel Voronoi Generating Algorithm
-
在QTM格网中，“点”可以用一个格网单元来表示，“线”和“面”则表示为一系列连续的格网单元的集合。而上述算法本身是以格网与种子点之间的距离为基础的，因此，可以直接用于球面点集Voronoi图的生成。对于线集和面集，需要首先将线或面离散成格网单元的集合，在计算时将集合中的所用格网都视作种子点，并用一个标识来标记 (用相同的标识来标记同一线或面经过的所有格网)，计算完成后将该标识作为最近种子点返回。为减少计算量，在处理面数据集时，可以仅将构成面域边界的格网作为种子点。线、面集的处理和点集的不同之处就在于处理点集时可直接返回最近种子点的编号，而处理线、面集时则返回种子点 (即构成线或面的格网单元) 对应的线或面的标识。
-
利用上述算法仅可以得到球面上所有格网的最近种子点集合，为了获取每个种子点的Voronoi区域的边界，本文设计了一个边界提取算法，具体原理为：如果某一格网自身和它的3个邻近格网 (左邻近、右邻近和顶邻近) 都属于同一个Voronoi区域，则该格网位于Voronoi区域的内部；相反，若格网自身和它的3个邻近格网分别属于两个不同的Voronoi区域，则该格网位于Voronoi边界上；若格网自身和它的3个邻近格网分别属于3个不同的Voronoi区域，则该格网为Voronoi顶点 (本文假设所有种子点均不共圆，即格网自身和它的3个邻近格网最多属于3个不同的Voronoi区域)。可以注意到，与前面的V图生成算法类似，边界提取算法同样具有计算密集性、指令一致性及相互独立性的特点，因此本文同样使用GPU并行计算来实现边界提取算法。
-
实现本文算法所用的编程语言为C++和NVIDIA CUDA 6.5，硬件环境为Intel (R) Core (TM) 2 Quad CPU Q8400 @2.66 GHz，2.00 GB内存，NVIDIA GeForce 9600 GT GPU，计算能力1.1。本文在上述环境中将本文算法用串行和GPU并行两种模式进行了实现，并对生成球面V图的精度及算法的效率进行了分析。
-
为测试本文算法对不同数据集的处理能力，本文分别利用全球所有国家的首都 (点)、世界主要河流 (线)、主要湖泊 (面) 生成球面V图，如图 3所示。
图 3 不同数据集的Voronoi图
Figure 3. Voronoi Diagrams of Different Data Sets
由于本文处理线、面等复杂实体的方法是将其离散化为点集进行计算，所以线、面数据集的V图和点集的V图具有一致的精度，而处理线、面数据集的效率与处理线、面 (或面的边界线) 经过的格网 (点集) 的效率一致。因此，本文以点集为基础对精度和效率进行分析。
-
为测试生成球面V图的精度，首先用本文算法生成球面V图，然后利用边界提取算法提取出所有位于Voronoi区域边界和Voronoi顶点的三角形，分别利用式 (3)、(4) 计算边界三角形和顶点三角形的误差e，并利用式 (5) 计算平均误差：
$$ \begin{align} & {{\varepsilon }_{i}}=e\left( {{x}_{i}},x_{i}^{j},x_{i}^{k} \right)=\left| {{d}_{s}}\left( {{x}_{i}},x_{i}^{j} \right)-{{d}_{s}}\left( {{x}_{i}},x_{i}^{k} \right) \right|/ \\ & \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ {{D}_{i}}\ \ \ j,k=\left\{ 1,2 \right\},j\ne k \\ \end{align} $$ (3) $$ {{\varepsilon }_{i}}=\max \left\{ e\left( {{x}_{i}},x_{i}^{j},x_{i}^{k} \right) \right\}\ \ j,k=\left\{ 1,2,3 \right\},j\ne k $$ (4) $$ \bar{\varepsilon }=\frac{1}{n}\sum\limits_{i=1}^{n}{{{\varepsilon }_{i}}} $$ (5) 式中, i={1, 2, …, n}; n为Voronoi边界三角形和顶点三角形的总个数; xi为边界 (或顶点) 三角形的中心点; xij、xik为该边界 (或顶点) 三角形所关联的Voronoi区域的种子点; 函数ds为球面上两点之间的大弧距离; DL为当前层次QTM格网的平均边长; e(xi, xij, xik) 为xi到xij和xik距离之差与格网平均边长DL的比值，即为边界 (或顶点) 三角形的误差εi；ε为所有边界三角形和顶点三角形的平均误差。
计算所有边界三角形和顶点三角形的误差，得到的最大误差为1.98个平均格网单元，平均误差为0.50个平均格网单元。分区间对计算结果进行统计，每个区间内三角形的个数及百分比如表 1所示。由表 1可以看出，本文算法能够将球面V图的误差控制在2个格网以内，且90%左右的Voronoi误差都能够控制在1个格网以内。
表 1 Voronoi误差统计结果
Table 1. Statistical Results of Voronoi Errors
序号 误差区间 三角形个数/个 百分比/% 1 0.0~0.5 37 976 55.51 2 0.5~1.0 23 360 34.15 3 1.0~1.5 6 634 9.70 4 1.5~1.98 440 0.64 合计 68 410 100.00 由§1.1的算法原理可知，本文算法通过直接计算并比较格网与种子点之间的球面距离来确定格网所属的种子点，不存在扩张误差，因此精度远高于扩张算法 (有关扩张算法的精度分析参见文献[5, 15])。但是，与扩张算法类似，本文算法也是将QTM格网作为最小单元，因此也存在一种“形状误差”，即利用三角形 (面) 来代替点所产生的误差，这是本文算法误差的主要来源。本文通过计算格网中心点之间的距离来减少这种误差。
图 4为利用全球所有国家的首都作为种子点，在不同层次的QTM格网上生成的球面V图。从图中可以看出，随着层次的升高，格网尺寸逐渐减小，生成的球面V图精度逐渐增加。
图 4 不同层次的Voronoi图
Figure 4. Voronoi Diagrams of Different Levels
-
为分析本文算法的效率，在不同的格网层次下，利用500个种子点，分别用本文算法的串行和并行两种模式生成球面V图，所用时间及并行加速比如表 2所示。同时，为测试本文并行算法在不同种子点数时的加速效果，以第8层格网为基础，分别利用不同数量的种子点对串行和并行两种模式进行测试，结果如表 3所示。
表 2 不同格网层次下的生成时间及加速比
Table 2. Generating Time and Speed-up Ratios in Different Levels
层次 6 7 8 9 串行算法/ms 241.2 961.4 3 808.1 15 206.6 并行算法/ms 6.6 17.7 56.7 213.4 加速比 36.5 54.3 67.2 71.3 表 3 不同种子点数时的生成时间及加速比
Table 3. Generating Time and Speed-up Ratios with Different Number of Sites
种子点数 10 100 1 000 10 000 串行算法/ms 94.5 805.1 7 551.8 75 282.7 并行算法/ms 19.2 21.7 101.6 918.3 加速比 4.9 37.1 74.3 82.0 由表 2可以看出，由于本文算法的复杂度较高，在串行模式下生成球面V图所用时间较长，而通过利用GPU并行加速，算法的执行时间大大减少，且随着格网层次的增加，获得的加速比也逐渐增大。同样，由表 3还可以看出，随着种子点数的增大，并行算法的加速比也呈增大趋势。这是由于GPU更适合于密集型的计算，当数据量 (计算量) 较小时，算法在GPU中执行时无法很好地隐藏数据传输和内存访问的延迟。随着格网层次和种子点数的增大，数据量 (计算量) 也随之增大，数据传输和内存访问的延迟逐渐被隐藏，从而使算法获得更高的效率。
-
本文在分析现有球面V图生成算法的基础上，以QTM格网为球面剖分方式，提出了一种球面V图的GPU并行生成算法，通过实验得出如下结论。
1) 本文利用距离的计算与比较来代替传统的扩张操作，能够将球面V图的误差控制在两个格网以内。
2) 本文利用的GPU并行计算对算法起到了加速的效果，且数据规模越大 (格网层次越高或种子点数越多)，加速效果越明显。
利用本文算法生成的球面V图误差能够控制在两个格网以内，因此，格网层次越高，格网尺寸越小，生成V图的精度也越高。但同时生成V图所用的时间也越长。虽然本文算法利用GPU并行计算提高了计算效率，但V图生成时间随格网层次的增加仍呈近似指数增长，在格网层次较高时效率较低，未来将研究利用多分辨率格网解决这一问题。
-
摘要: 根据球面四元三角网（quaternary triangular mesh，QTM）的离散特征及图形处理器（graphics processing unit，GPU）的多线程原理，用距离的计算与比较代替传统的扩张操作，提出了一种基于QTM的球面Voronoi图并行生成算法，并给出了Voronoi边界提取算法。利用C++语言及统一计算设备架构（compute unified device architecture，CUDA）开发了实验系统。实验结果表明，本文算法能够在球面上快速生成点、线、面数据集的Voronoi图，且能够将Voronoi误差控制在两个格网以内。同时，GPU并行计算的使用，提高了算法的效率。
-
关键词:
- 球面Voronoi图 /
- 图形处理器 (GPU) /
- 统一计算设备架构 (CUDA) /
- 全球空间格网 /
- 四元三角格网 (QTM)
Abstract: Most of the traditional algorithms for the generation of spherical Voronoi diagram are in vector mode and only good for point sets. Recently, approximate raster-based algorithms that easily generate spherical Voronoi diagrams of point, line, and area sets have been proposed. However, almost all these raster-based algorithms are based on dilation operations. Dilation errors however, increase with the growth of dilation steps and are irregularly distributed. To overcome these deficiencies, a parallel algorithm for generating spherical Voronoi diagrams based on the discrete characteristics of a Quaternary Triangular Mesh (QTM) and the multi-thread principle of GPU (Graphics Processing Unit) is proposed. An algorithm for extracting Voronoi boundaries was also developed. Experiments were conducted using C++ and Compute Unified Device Architecture (CUDA). Results show that this algorithm can handle line sets and area sets as well as point sets and the Voronoi error can be limited within two grids. Additionally, efficiency when generating spherical Voronoi diagrams was improved greatly by using GPU parallel computation. -
图 2 Voronoi图并行生成算法流程图
Figure 2. Flowchart of the Parallel Voronoi Generating Algorithm
表 1 Voronoi误差统计结果
Table 1. Statistical Results of Voronoi Errors
序号 误差区间 三角形个数/个 百分比/% 1 0.0~0.5 37 976 55.51 2 0.5~1.0 23 360 34.15 3 1.0~1.5 6 634 9.70 4 1.5~1.98 440 0.64 合计 68 410 100.00 
下载: 导出CSV
表 2 不同格网层次下的生成时间及加速比
Table 2. Generating Time and Speed-up Ratios in Different Levels
层次 6 7 8 9 串行算法/ms 241.2 961.4 3 808.1 15 206.6 并行算法/ms 6.6 17.7 56.7 213.4 加速比 36.5 54.3 67.2 71.3
下载: 导出CSV
表 3 不同种子点数时的生成时间及加速比
Table 3. Generating Time and Speed-up Ratios with Different Number of Sites
种子点数 10 100 1 000 10 000 串行算法/ms 94.5 805.1 7 551.8 75 282.7 并行算法/ms 19.2 21.7 101.6 918.3 加速比 4.9 37.1 74.3 82.0
下载: 导出CSV
-
[1] 闫浩文, 王邦松.地图点群综合的加权Voronoi算法[J].武汉大学学报·信息科学版, 2013, 38(9):1088-1091 http://www.cnki.com.cn/Article/CJFDTOTAL-WHCH201309018.htm Yan Haowen, Wang Bangsong. A MWVD-Based Algorithm for Point Cluster Generation[J]. Geomatics and Information Science of Wuhan University, 2013, 38(9):1088-1091 http://www.cnki.com.cn/Article/CJFDTOTAL-WHCH201309018.htm [2] 王中辉, 闫浩文.基于方向Voronoi图模型的群组目空间方向关系计算[J].武汉大学学报·信息科学版, 2013, 38(5):584-588 http://www.cnki.com.cn/Article/CJFDTOTAL-WHCH201305018.htm Wang Zhonghui, Yan Haowen. Computation of Direction Relations Between Object Groups Based on Direction Voronoi Diagram Model[J]. Geomatics and Information Science of Wuhan University, 2013, 38(5):584-588 http://www.cnki.com.cn/Article/CJFDTOTAL-WHCH201305018.htm [3] 胡玮, 陶伟东, 苑振宇, 等.一种Voronoi图的扫描地图矢量化方法[J].武汉大学学报·信息科学版, 2013, 38(4):470-474 http://www.cnki.com.cn/Article/CJFDTOTAL-WHCH201304020.htm Hu Wei, Tao Weidong, Yuan Zhenyu, et al. A Method of Vectorization of Scanning Map Based on Voronoi Diagrams[J]. Geomatics and Information science of Wuhan University, 2013, 38(4):470-474 http://www.cnki.com.cn/Article/CJFDTOTAL-WHCH201304020.htm [4] Chen J, Zhao X, Li Z. An Algorithm for the Generation of Voronoi Diagrams on the Sphere Based on QTM[J].Photogrammetric Engineering & Remote Sensing, 2003, 69(1):79-89 [5] Augenbaum J M, Peskin C S. On the Construction of the Voronoi Mesh on a Sphere[J]. Journal of Computational Physics, 1985, 59(2):177-192 doi: 10.1016/0021-9991(85)90140-8 [6] Renka R J. Delaunay Triangulation and Voronoi diagram on the Surface of a Sphere[J]. ACM Transactions on Mathematical Software, 1997, 23(3):416-434 doi: 10.1145/275323.275329 [7] Ma Y, Chen Q. Fast Delaunay Triangulation and Voronoi Diagram Generation on the Sphere[C]. The Second World Congress on Software Engineering, Wuhan, 2010 [8] Dinis J, Mamede M. Sweeping the Sphere[C]. International Symposium on Voronoi Diagrams in Science and Engineering, Quebec, Canada, 2010 [9] Hyeon-Suk N, Chung-Nim L, Otfried C. Voronoi Diagrams on the Sphere[J]. Computation Geometry:Theory and Applications, 2002, 23(2):183-194 doi: 10.1016/S0925-7721(02)00077-9 [10] Christopher G, Mir A M. Towards the Global GIS[J]. ISPRS Journal of Photogrammetry & Remote Sensing, 2000, 55(3):150-163 http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.1.2020 [11] Yang W, Christopher G. Managing Spatial Objects with the VMO-Tree[C]. The 7th International Symposium on Spatial Data Handling, the Netherlands, 1996 [12] 童晓冲, 贲进, 张永生.不同集合的球面矢量Voronoi图生成算法[J].测绘学报, 2006, 35(1):83-89 http://www.cnki.com.cn/Article/CJFDTOTAL-CHXB200601015.htm Tong Xiaochong, Ben Jin, Zhang Yongsheng. The Generation Algorithm for Spherical Voronoi Diagram of Different Aggregation[J].Acta Geodaetica et Cartographica Sinica, 2006, 35(1):83-89 http://www.cnki.com.cn/Article/CJFDTOTAL-CHXB200601015.htm [13] 赵学胜, 陈军, 王金庄.基于O-QTM的球面Voronoi图的生成算法[J].测绘学报, 2002, 31(2):158-163 http://www.cnki.com.cn/Article/CJFDTOTAL-CHXB200202013.htm Zhao Xuesheng, Chen Jun, Wang Jinzhuang. QTM-Based Algorithm for the Generating of Voronoi Diagram for Spherical Object[J]. Acta Geodaetica et Cartographica Sinica, 2002, 31(2):158-163 http://www.cnki.com.cn/Article/CJFDTOTAL-CHXB200202013.htm [14] 赵学胜.基于QTM的球面Voronoi数据模型[M].北京:测绘出版社, 2004 Zhao Xuesheng. Spherical Voronoi Data Model Based on QTM[M]. Beijing:Surveying and Mapping Press, 2004 [15] 贲进, 童晓冲, 张衡, 等.基于球面六边形格网的球面Voronoi图生成算法[J].测绘科学技术学报, 2006, 23(5):328-330 http://cdmd.cnki.com.cn/Article/CDMD-11413-1016062791.htm Ben J, Tong X, Zhang H, et al. A Spherical Voronoi Algorithm Based on Hexagonal Grid[J]. Journal of Zhengzhou Institute of Surveying and Mapping, 2006, 23(5):328-330 http://cdmd.cnki.com.cn/Article/CDMD-11413-1016062791.htm [16] 童晓冲, 贲进, 张永生.基于二十面体剖分格网的球面实体表达与Voronoi图生成[J].武汉大学学报·信息科学版, 2006, 31(11):966-970 http://www.cnki.com.cn/Article/CJFDTOTAL-WHCH200611006.htm Tong Xiaochong, Ben Jin, Zhang Yongsheng. Expression of Spherical Entities and Generation of Voronoi Diagram Based on Truncated Icosahedron DGG[J]. Geomatics and Information Science of Wuhan University, 2006, 31(11):966-970 http://www.cnki.com.cn/Article/CJFDTOTAL-WHCH200611006.htm [17] Rong G, Tiow-S T. Jump Flooding in GPU with Applications to Voronoi Diagram and Distance Transform[C]. The 2006 ACM Symposium on Interactive 3D Graphics and Games, Redwood City, 2006 [18] Kenneth E H, Tim C, John K, et al. Fast Computation of Generalized Voronoi Diagrams Using Graphics Hardware[C]. The 26th Annual Conference on Computer Graphics and Interactive Techniques, Los Angeles, 1999 [19] Cao T-T, Tang K, Mohamed A, et al. Parallel Banding Algorithm to Compute Exact Distance Transform with GPU[C]. The 2010 ACM SIGGRAPH Symposium on Interactive 3D Graphics and Games, Bethesda, 2010 [20] Majdandzic I, Trefftz C, Wolffe G. Computation of Voronoi Diagrams using a Graphics Processing Unit[C]. IEEE International Conference on Electro/Information Technology, Ames, 2008 [21] Rong G, Liu Y, Wang W, et al. GPU-Assisted Computation of Centroidal Voronoi Tessellation[J]. IEEE Transactions on Visualization and Computer Graphics, 2011, 17(3):345-356 doi: 10.1109/TVCG.2010.53 [22] 陈伟锋, 王锐, 潘明皓, 等.基于GPU的快速球面距离变换[J].计算机学报, 2011, 34(3):499-507 http://www.cnki.com.cn/Article/CJFDTOTAL-JSJX201103009.htm Chen Weifeng, Wang Rui, Pan Minghao, et al. GPU-Based Fast Spherical Distance Transform[J]. Chinese Journal of Computers, 2011, 34(3):499-507 http://www.cnki.com.cn/Article/CJFDTOTAL-JSJX201103009.htm -
点击查看大图
图(4) / 表(3)
计量
- 文章访问数: 855
- HTML全文浏览量: 19
- PDF下载量: 373
- 被引次数: 0
