Performance tuning and sparse traversal technique for a cell‐based fetch length algorithm on a GPU

For determining distances (fetch lengths) from points to polygons in a two‐dimensional Euclidean plane, cell‐based algorithms provide a simple and effective solution. They divide the input area into a grid of cells that cover the area. The objects are stored into the appropriate cells, and the resulting structure is used for solving the problem. When the input objects are distributed unevenly or the cell size is small, most of the cells may be empty. The representation is then called sparse. In the method proposed in this work, each cell contains information about its distance to the nonempty cells. It is then possible to skip over several empty cells at a time without memory accesses. A cell‐based fetch length algorithm is implemented on a graphics processing unit (GPU). Because control flow divergence reduces its performance, several methods to reduce the divergence are studied. While many of the explicit attempts turn out to be unsuccessful, sorting of the input data and sparse traversal are observed to greatly improve performance: compared with the initial GPU implementation, up to 45‐fold speedup is reached. The speed improvement is greatest when the map is very sparse and the points are given in a random order. Copyright © 2015 John Wiley & Sons, Ltd.     

曲线轮廓汉字的网格适配技术

要提高曲线轮廓汉字的还原质量, 需要在字形还原时采用网格适配技术本文介绍了网格适配的基本原理, 并在分析汉字字形还原失真现象的基础上, 给出了我们自己设计并实现的适合于曲线轮廓汉字特点的二种网格适配方法, 即动态的补象素算法和曲线轮廓汉字的技术     

基于网络加权Voronoi图的点群选取

传统基于Voronoi图的算法忽略了点与点之间是通过实际网络距离相连这一事实,针对此缺陷,提出一种基于网络加权Voronoi图的点群选取算法. 1）利用网络扩展法构建点群的网络加权Voronoi图;2）计算每个点对应的网络Voronoi多边形面积及扩展弧段总长度,并以此为依据,为点群中所包含的统计、专题、拓扑和度量信息分别选定量化描述因子;3）提出“同心圆”算法,解决点群取舍问题. 实验结果表明,提出的方法顾及了点群权重以及与点群相关联的道路等级、方向及局部密度对选取结果的影响,较好地保持了原始点群的各类信息,选取结果符合实际地理空间特征.     

OpenGL设计理论

OpenGL被认为是高性能图形和交互式视景处理的标准,可以制作出顺畅的3D效果,且性能也是非常出色的。所以在当今的三维绘制领域,其占据了不可动摇的位置。我国的三维创作发展起步相当晚,必须努力钻研迎头赶上。     

几何特征保持的文物点云去噪算法

三维激光扫描是一种快速获取高精度点云的新技术,但由于受物体本身的构造、粗糙程度、纹理以及测量环境等因素的影响,获取的点云数据大多存在孤立的噪声点。针对文物点云数据模型中复杂噪声难以去除的问题,提出一种几何特征保持的点云去噪算法。首先通过栅格划分删除点云中的大尺度噪声;然后定义点云中数据点的曲率因子和密度因子,并通过对其加权构造模糊C均值聚类（Fuzzy C-means clustering, FCM）的目标函数;最后采用该特征加权FCM算法删除小尺度噪声,从而实现点云的去噪处理。实验结果表明,该几何特征保持的去噪算法对文物点云数据具有良好的去噪效果,是一种有效的点云去噪算法。     

布料人体快速连续碰撞检测与响应

碰撞检测是3D虚拟服装中的重要环节,而在布料和人体模型的分辨率比较高的情况下,常规的碰撞检测算法往往无法达到实时.使用深度图像进行实时的连续碰撞检测,并结合法线图像进行碰撞响应.首先从指定的摄像机为人体预先渲染生成前后部深度图像与法线图像;然后对于要检测碰撞的布料质点,计算其深度值,并将其位置变换到图像空间,然后根据图像空间坐标从深度图像中读取深度值,通过与质点的深度值进行比较即可判断质点是否与人体碰撞,若发生碰撞,则通过修改的DDA直线光栅化算法在质点前一步与后一步位置确定的深度图像坐标区间内搜索插值参数,该插值参数用来计算碰撞接触点以及接触点处的法线,以支持连续碰撞响应.实验结果表明,该算法的预处理速度快,在布料和人体的分辨率都比较高的情况下也可以获得实时的碰撞检测与响应.     

计及碳排放的电动汽车充电站多目标规划

合理的电动汽车充电站规划是推广应用电动汽车的基础。提出一种计及碳排放的电动汽车充电站多目标选址定容规划模型,模型以充电站建设运行成本、用户充电耗费时间和驶向充电站引起的碳排放为综合优化目标,以充电站的容量限制为约束条件,并采用Pareto最优前沿分析可选的选址定容方案。为确定可选站址所服务的区域范围,提出一种基于需求点栅格化和Voronoi图求解的计算方法。最后,通过案例分析验证了该规划模型和求解方法的实用性和有效性,为电动汽车充电站的选址定容提供了新的思路。     

Visibility Driven Rasterization

We present a new visibility driven rasterization scheme that significantly increases the rendering performance of modern graphic subsystems. Instead of rasterizing, texturing, lighting, and depth-testing each individual pixel, we introduce a two-level visibility mask within the rasterization stage which facilitates the removal of groups of pixels and triangles from rasterization and subsequent pipeline stages.
Local visibility information is stored within the visibility mask that is updated several times during the generation of a frame. The update can easily be accomplished by extending already available (in hardware) occlusion culling mechanisms (i.e. those of HP and SGI), where it is possible to integrate the additional functionality without any additional delay cycles. In addition to these existing hardware based occlusion culling approaches—which cull only geometry contained in bounding volumes determined as occluded —we are able to significantly accelerate the rendering of the geometry determined as visible . However, our approach does not specifically rely on such occlusion culling hardware.The proposed new rasterization scheme is well suited for hardware implementation, can easily be integrated into low-cost rasterizers, and its scalability can vary upon available chip real estate. Only incremental modifications of modern graphics subsystems are required to achieve a significant improvement in rendering performance.     

提高曲线轮廓汉字还原质量的一些方法

本文讨论了曲线轮廓汉字还原输出时的质量问题，并从还原算法及字库设计等方面探讨了提高曲线轮廓汉字还原质量的一些方法。     

Collision detection with relative screw motion

We introduce a framework for collision detection between a pair of rigid polyhedra. Given the initial and final positions and orientations of two objects, the algorithm determines whether they collide, and if so, when and where. All collisions, including collisions at different times, are computed at once along with properness values that measure the extent to which the collisions are between parts of the objects that properly face each other. This is useful for handling multiple (nearly) concurrent collisions and contact points.The relative motions of the rigid bodies are limited to screw motions. This limitation is not always completely accurate, but we can estimate the error introduced by the assumption.Our implementation uses rasterization to approximate the position and time of the collisions. This allows level-of-detail techniques that provide a tradeoff between accuracy and computational expense.The collision detection algorithms are only approximate, both because of the screw motion assumption and because of the rasterization. However, they can be made robust so as to give consistent information about collisions and to avoid sensitivity to roundoff errors.