GPU并行计算加速的实时可视外壳三维重建及其虚实交互

针对现有的基于图像的三维重建方法难以实现真实物体的快速三维重建,无法满足虚实交互等应用需求的问题,提出一种基于GPU并行计算的实时三维重建及其虚实交互方法.首先把物体所在空间剖分成具有数据独立性的体素集合,结合可视外壳重建算法和精确行进立方体算法并行遍历每个体素得到体素状态序列;然后并行压缩体素状态序列得到非空体素集合,对非空体素进行并行三角形网格化,并利用图形硬件的多重纹理映射和可编程功能进行基于像素的纹理映射;最后假定虚拟物体的粒子为运动受限的拉格朗日流体粒子,重建物体网格顶点为流体边界,通过流体动力学方程的并行光滑粒子动力学方法求解来计算虚实交互.实验结果表明,该方法在GPU上进行完全并行求解,在32×32×32的空间剖分精度下,实现了实时三维重建和20帧/s左右的虚实交互计算,适用于计算机图形学和虚拟现实等领域中的虚实交互应用.     

基于CUDA实现MRRR算法并行

MRRR(Multiple Relatively Robust Representations)算法是求解对称三对角矩阵本征值问题高效、精确的算法之一。在分析MRRR算法及CUDA(Compute Unified Device Architecture)并行体系结构的基础上,针对算法的可并行性,采用单指令多线程并行方式实现了基于CUDA的MRRR算法并行,并从存储结构方面优化算法。实验结果显示,与LAPACK库中串行MRRR实现相比,并行方法在保证精度的基础上获得了20倍的加速比,进而从计算精度和计算时间上说明MRRR算法适合在GPU上并行。     

CUDA加速的DNA-蛋白质匹配及其优化

设计实现了一种使用统一计算设备架构(CUDA)加速DNA-蛋白质匹配的方法。详细介绍了一种基于退火算法的DNA-蛋白质匹配方法和CUDA的特点,从计算的角度对匹配方法进行了分析。基于CUDA设计实现并行化方法,并根据CUDA的线程调度策略对并行方法进行了优化。实验结果表明,最大可获得15倍左右的加速比。     

基于CUDA的并行粒子群优化算法的设计与实现

针对处理大量数据和求解大规模复杂问题时粒子群优化(PSO)算法计算时间过长的问题, 进行了在显卡(GPU)上实现细粒度并行粒子群算法的研究。通过对传统PSO算法的分析, 结合目前被广泛使用的基于GPU的并行计算技术, 设计实现了一种并行PSO方法。本方法的执行基于统一计算架构（CUDA）, 使用大量的GPU线程并行处理各个粒子的搜索过程来加速整个粒子群的收敛速度。程序充分使用CUDA自带的各种数学计算库, 从而保证了程序的稳定性和易写性。通过对多个基准优化测试函数的求解证明, 相对于基于CPU的串行计算方法, 在求解收敛性一致的前提下, 基于CUDA架构的并行PSO求解方法可以取得高达90倍的计算加速比。     

基于GPU的H.264并行解码算法

针对并行处理H.264标准视频流解码问题,提出基于CPU/GPU的协同运算算法。以统一设备计算架构(CUDA)语言作为GPU编程模型,实现DCT逆变换与帧内预测在GPU中的加速运算。在保持较高计算精度的前提下,结合CUDA混合编程,提高系统的计算性能。利用NIVIDIA提供的CUDA语言,在解码过程中使DCT逆变换和帧内预测在GPU上并行实现,将并行算法与CPU单机实现进行比较,并用不同数量的视频流验证并行解码算法的加速效果。实验结果表明,该算法可大幅提高视频流的编解码效率,比CPU单机的平均计算加速比提高10倍。     

CUDA平台下信息熵多种群遗传算法设计

为了进一步提高信息熵多种群遗传算法的计算效率,缩短计算时间,提出了一种基于CUDA平台的信息熵多种群遗传算法。通过分析原算法的并行因素,结合CUDA开发平台,对原算法进行适合GPU加速的并行化处理,实现了遗传算子、惩罚函数和空间收缩因子等的并行计算,有效地提高了算法效率。例题数值测试表明,在保持了快速收敛特性和计算精度的前提下,CUDA并行算法相对于原算法具有很高的加速效率。     

基于CUDA架构的改进Marching Cubes算法

Marching Cubes是医学体数据可视化的经典算法,但生产的网格质量差、算法执行速度慢成为阻碍其用于数值分析的两个主要缺点。文中提出一种基于硬件加速的Marching Cubes改进算法。该算法采用统一设备架构(CUDA)充分发挥Marching Cubes算法分而治之的优点,利用CUDA的可编程性并行分类体数据,加快了活跃体素和活跃边的提取;同时,该改进算法将得到的活跃边按照中点投影方式进行偏移,从而达到了改善网格质量的目的。最后通过实验表明,该算法可以保证在阈值未知的情况下,进行交互式的高质量网格建模。     

基于CUDA海量空间数据实时体绘制研究

针对海量空间科学数据的精细及实时三维绘制需求,提出并实现了一种基于CUDA语言的并行化光线投射体绘制加速算法,利用传统体绘制算法中光线投射法的可并行特点和GPU中高速的纹理查询的优点,通过一个实际坐标到纹理坐标的转换函数实现了对不规则采样数据的准确采样,并完成了绘制算法的CUDA并行化改造,通过CUDA语言利用GPU强大的并行计算能力实现了对海量空间数据的实时三维光线投射绘制.     

基于CUDA的并行K-近邻连接算法实现

针对大规模空间数据的K-近邻连接查询问题,设计了一种CUDA编程模型下K-近邻连接算法的并行优化方法。将K-近邻连接算法的并行过程分两个阶段:1)对参与查询的数据集P和Q分别建立R-Tree索引;2)基于R-Tree索引进行KNNJ查询。首先根据结点所在位置划分最小外包框,在CUDA下基于递归网格排序算法创建R-Tree索引。然后在CUDA下基于R-Tree索引进行KNNJ查询,其中涉及并行求距离和并行距离排序两个阶段:求距离阶段利用每一个线程计算任意两点之间的距离,点与点之间距离的求取无依赖并行;排序阶段将快速排序基于CUDA以实现并行化。实验结果表明,随着样本量的不断增大,基于R-Tree索引的并行K-近邻连接算法的优势更加明显,具有高效性和可扩展性。     

基于混合编程模型的支持向量机训练并行化

支持向量机(support vector machine, SVM)是一种广泛应用于统计分类以及回归分析的监督学习方法.基于内点法(interior point method, IPM)的SVM训练具有空间占用小、迭代趋近快等优点,但随着训练数据集规模的增大,仍面临处理速度与存储空间所带来的双重挑战.针对此问题,提出利用CPU-GPU异构系统进行大规模SVM训练的混合并行机制.首先利用计算统一设备架构(compute unified device architecture, CUDA)对基于内点法的SVM训练算法的计算密集部分并行化,并改进算法使其适合利用cuBLAS线性代数库加以实现,提高训练速度;然后利用消息传递接口(message passing interface, MPI)在集群系统上实现CUDA加速后算法的分布并行化,利用分布存储有效地增加所处理数据集规模并减少训练时间;进而基于Fermi架构支持的页锁定内存技术,打破了GPU设备存储容量不足对数据集规模的限制.结果表明,利用消息传递接口(MPI)和CUDA混合编程模型以及页锁定内存数据存储策略,能够在CPU-GPU异构系统上实现大规模数据集的高效并行SVM训练,提升其在大数据处理领域的计算性能和应用能力.     

GPU-based parallel construction of compact visual hull meshes

Building a visual hull model from multiple two-dimensional images provides an effective way of understanding the three-dimensional geometries inherent in the images. In this paper, we present a GPU accelerated algorithm for volumetric visual hull reconstruction that aims to harness the full compute power of the many-core processor. From a set of binary silhouette images with respective camera parameters, our parallel algorithm directly outputs the triangular mesh of the resulting visual hull in the indexed face set format for a compact mesh representation. Unlike previous approaches, the presented method extracts a smooth silhouette contour on the fly from each binary image, which markedly reduces the bumpy artifacts on the visual hull surface due to a simple binary in/out classification. In addition, it applies several optimization techniques that allow an efficient CUDA implementation. We also demonstrate that the compact mesh construction scheme can easily be modified for also producing a time- and space-efficient GPU implementation of the marching cubes algorithm.     

A volumetric fusion technique for surface reconstruction from silhouettes and range data

Optical triangulation, an active reconstruction technique, is known to be an accurate method but has several shortcomings due to occlusion and laser reflectance properties of the object surface, that often lead to holes and inaccuracies on the recovered surface. Shape from silhouette, on the other hand, as a passive reconstruction technique, yields robust, hole-free reconstruction of the visual hull of the object. In this paper, a hybrid surface reconstruction method that fuses geometrical information acquired from silhouette images and optical triangulation is presented. Our motivation is to recover the geometry from silhouettes on those parts of the surface which the range data fail to capture. A volumetric octree representation is first obtained from the silhouette images and then carved by range points to amend the missing cavity information. An isolevel value on each surface cube of the carved octree structure is accumulated using local surface triangulations obtained separately from range data and silhouettes. The marching cubes algorithm is then applied for triangulation of the volumetric representation. The performance of the proposed technique is demonstrated on several real objects.     

移动立方体算法中的三角剖分

Marching Cubes（MC）算法是基于规则体数据抽取等值面的经典算法。分析了该算法中的交点连接问题,解决连接上的二义性问题,从而更好地生成多边形;对于生成的非平面多边形,对三角剖分进行了优化,以此改进了移动立方体算法,通过实验验证了算法的正确性。     

Graphics processing unit‐based triangulations of Blinn molecular surfaces

Computing the surface of a molecule (e.g., a protein) plays an important role in the analysis of its geometric structure as needed in the study of interactions between proteins, protein folding, protein docking, and so forth. There are a number of algorithms for the computation of molecular surfaces and their triangulations, but only a few take advantage of graphics processing unit computing. This paper describes a graphics processing unit‐based marching cubes algorithm to triangulate molecular surfaces. In the end of the paper, a performance analysis of three implementations (i.e., serial CPU, CUDA, and OpenCL) of the marching cubes‐based triangulation algorithm takes place as a way to realize beforehand how molecular surfaces can be rendered in real‐time in the future. Copyright © 2011 John Wiley & Sons, Ltd.     

增量式精确多面体可见外壳

提出一种新的增量式计算精确多面体可见外壳的算法IEPVH。首先,在新视图的图像平面,计算旧可见外壳的边被新光椎切割得到的交点。然后,恢复旧可见外壳的边上交点的局部方向信息并同时获得新光椎边上的交点。接着,恢复新光椎边上交点的局部方向信息。最后,新可见外壳的多边形面片通过一次遍历网格的边的过程被识别出来,并为了便于显示而被划分为三角面片。与EPVH等其他算法相比,IEPVH不但能够让用户更多地参与基于图像3维重建的过程,而且具有空间计算复杂度小。实验证明此算法的高效和鲁棒性。IEPVH的特点使其更易于在移动设备中得到应用。     

基于约束的地质网格曲面重建算法

提出一种基于地质约束的地质曲面重建算法,为在三维地质建模中构造线性不连续层位面片提供一种解决方案.应用"移动立方体"算法从点云重建出无约束的层位三角网格曲面,在断层曲面的约束下,利用初始点云对层位曲面进行网格拟合处理,使层位曲面的各个面片在交线附近能很好地体现断层对层位面的切分效果.实验结果证明,该算法运行稳定、有效.     

采用变形模型的图像序列可视外壳计算方法

针对基于图像序列变形模型三维重建中至关重要的初始模型计算问题,提出一种基于图像序列计算可视外壳的方法.该方法基于Snake活动轮廓变形模型,将真实物体可视外壳的计算问题转化为初始曲面通过内外力作用驱动收敛于目标物体的问题.以真实物体图像序列中提取的物体轮廓为输入,根据轮廓信息和光滑度信息计算内力及轮廓力大小,驱动球体初始曲面变形收敛于可视外壳;在变形过程中加入删除短边、分裂长边、对角线翻转等网格优化操作,以避免发生网格错乱.实验结果表明,文中方法有效地克服了传统的基于体元素细分产生网格算法网格质量不高的缺点,且参数可调,易于实现,占用内存少,生成的曲面更加光滑,细节恢复效果理想.     

多尺度图割曲面重建算法

针对图割曲面重建算法计算量过大的难题, 根据代数多栅理论对图割计算过程进行多尺度分解, 仅对最后一级进行最大流计算, 其他级的标记值通过插值得到。首先, 根据点云法向和重建曲面法向的一致性构建能量函数; 其次, 将能量函数映射到三维权重图的顶点和边上; 然后, 定义顶点间的一致性并由此构造抽取矩阵, 以决定哪些图的顶点参与图割运算; 之后, 构造插值矩阵, 将最后一级图割计算结果逐级插值到第一级; 最后, 利用步进立方体算法得到重建曲面的三角网格表示。实验结果表明, 与窄带图割算法相比, 本方法计算速度更快, 当图的顶点数越多时速度提高得越多; 对于不均匀采样的点云数据, 重建效果更好; 其他情况下两者效果相当。     

基于照片序列的多面体虚拟壳快速生成算法

介绍了一个基于照片序列的三维模型重构系统，通过照片图像中提取物体轮廓对应的光锥相交得到多面体虚拟壳，并介绍一个基于活性点列的快速相交算法。     

Parallel‐optimizing SPH fluid simulation for realistic VR environments

In virtual environments, real‐time simulation and rendering of dynamic fluids have always been the pursuit for virtual reality research. In this paper, we present a real‐time framework for realistic fluid simulation and rendering on graphics processing unit. Because of the high demand for interactive fluids with larger particle set, the computational need is becoming higher. The proposed framework can effectively reduce the computational burden through avoiding the computation in inactive areas, where many particles with similar properties and low local pressure cluster together. While in active areas, the computation is fully carried out; thus, the fluid dynamics are largely preserved. Here, a robust particle classification technique is introduced to classify particles into either active or inactive. The test results have shown that the technique improves the time performance of fluid simulation largely. We then incorporate parallel surface reconstruction technique using marching cubes to extract the surfaces of the fluid. The introduced histogram pyramid‐based marching cubes technique is fast and memory efficiency. As a result, we are able to produce plausible and interactive fluids with the proposed framework for large‐scale virtual environments. Copyright © 2013 John Wiley & Sons, Ltd.