面向虚拟森林仿真的多层场景引擎设计

为快速绘制具有真实感的大规模虚拟森林场景,在分析虚拟森林场景仿真特点的基础上,提出面向虚拟森林仿真多层场景引擎的总体结构,对该场景引擎中的实时地形生成技术、地形模型的简化算法和渲染加速等关键技术展开研究,开发了虚拟森林仿真系统。应用结果表明,面向虚拟森林仿真的多层场景引擎有助于提高复杂森林场景的绘制效率,能较好地满足用户进行实时漫游和交互控制的需求。     

面向森林动态生长过程的场景系统设计和实现*

植物的模拟一直是计算机图形学领域研究的热点问题之一。近年来,国内外的研究人员在提高植物建模的精细度方面开展了大量研究,但是针对大规模植物场景建模的体系结构设计问题,尤其是支持动态生长变化的场景体系结构设计问题的研究还比较少见。针对森林动态生长过程场景系统的仿真应用,提出了一个全新的森林场景架构设计方案,采用了模块化与层次化相结合的思想构建森林场景系统。该系统不仅支持传统方法不能解决的用户动态交互（修改场景实体、漫游）的需求,而且具有良好的维护性和扩展性。     

GPU适用的并行纹理合成算法

基于样图的纹理合成是一个大计算量过程,为了利用GPU的并行计算能力进行大规模纹理合成,我们提出一种并行纹理合成算法.该算法综合块查找和全局纹理优化算法分多遍进行纹理的合成和优化,其中每一遍分为串行纹理块定位和并行最优块匹配2个阶段.纹理块定位阶段在CPU端按照扫描线顺序确定待合成的邻域,并将邻域位置传入GPU;最优块匹配阶段在GPU端并行计算待合成邻域与对应样本邻域的全局距离,并查找出最优解得到匹配块.最后根据匹配过程统计数据自适应调整优化规模,在全局范围内对纹理进行迭代优化.实验结果表明,文中算法在保证大规模纹理合成效果的基础上减少了计算时间,能够满足交互式纹理合成的应用.     

基于样本的大规模人群快速创作

人群作为虚拟环境中必不可少的一部分,能够极大地提高场景的真实感.文中提出一种基于样本的大规模人群快速创作方法,将人视为具有分布和角色信息的粒子,通过从真实图片中获取包含小规模人群粒子信息的样本,由样本建立Wang Tile集合,使用Wang Tile非周期性拼接覆盖场景区域,从而快速生成任意规模人群.文中的创作方法简单快速,用户只需输入若干样本和场景区域.同时,用户可以通过调整Tile的边颜色快速地进行局部人群修改,也可以使用密度图得到用户需要的效果.实验给出了3个场景的人群创作效果,表明文中的方法可以十分迅速地生成大规模具有真实分布信息的多样人群.     

样本驱动的大规模植被分布高效合成

针对自然场景中丰富多样的植被分布模式的模拟时,现有的通用拟合算法计算耗时,不能满足大规模分布与实时交互分布的需要.为了解决任意分布模式的快速合成问题,提出一种基于样本分布控制并结合Wang tiles优化的高效点分布合成方法.该方法由离线预计算过程和实时拼接过程组成.在离线预计算过程中,首先通过基于环形点对距离统计的对相关函数特征拟合过程合成多块首尾分布连续,以及与样本分布相似的初始点分布tile,然后通过对初始tile的边界处理得到一组可以非周期性拼接且接缝处分布保持连续的Wang tiles;在此基础上,利用这组Wang tiles进行实时拼接,从而实现以极快的速度和极小的内存占用合成大规模的分布的目的.实验结果表明,该方法适用于随机、均匀、聚集等各种分布特征的数据,是一种对各类样本分布模式通用的分布合成方法;并在大规模分布的合成上比原有的基于样本驱动的分布拟合算法达到3～6个量级的速度提升;可有效地应用于自然场景模拟中大规模植被的分布信息构建,及其他有实时交互分布需求的应用中.     

数据驱动的大规模森林场景真实感动画

提出一种基于数据驱动的大规模森林场景真实感动画的实现方案.该方案预先对单株样本树在风力作用下的运动作高精度的动力学计算,得到高分辨率、精确的树骨架形变序列;然后采用分簇主元分析方法对形变序列数据进行压缩与简化,构建单株树各枝干运动的细节层次;最后基于多株样本树多个细节层次的运动数据合成大规模森林的群体运动.实验结果表明:该方案实现了力学形变数据的高效重用,在森林动画合成效率和真实感上具有一定的优势,能满足对规模和画质要求较高的应用,如影视动画与媒体广告等的需求.     

基于Lévy分布的不平衡数据过采样方法

针对不平衡数据集上的分类问题，提出了基于Lévy分布的过采样方法，其核心思想是根据初始数据集的分布，利用Lévy分布构造新样本的密度分布。基于Lévy分布的特性，使得从边界样本合成的新样本密度最大，靠近多数类的样本合成的新样本密度次之，靠近少数类的样本合成的新样本密度最小。因此，该算法可以增强分类边界，同时可以减小噪声生成。通过在多个数据集上的实验，表明所提算法可以有效改善不平衡数据的分类效果。     

面向虚拟场景的深度全景视频绘制技术

高度复杂的三维场景通常包含几千万甚至上亿个三角形和丰富的纹理,大大超过了目前图形硬件的处理能力。传统基于几何的绘制系统通过牺牲画面质量来实现场景的快速绘制。与此不同,基于图像的绘制技术利用逼真的图像序列来生成高质量的目标画面。研究面向虚拟场景的IBR(Image-Based Rendering)技术来克服现有方法的不足,提出以深度全景视频DPV作为场景表示的基本单元,通过多段深度全景视频组成的深度全景视频网络来表示虚拟场景的漫游区域,它允许视点在漫游平面的封闭区域内连续运动。绘制算法根据目标视点参数计算深度全景视频环中对目标图像有贡献的候选区域,综合利用GPU的强大处理能力和浮点格式的绘制目标,以及多幅深度图像混合绘制技术对候选区域进行绘制来生成目标图像。实验结果表明,深度全景视频绘制技术可实现大规模虚拟场景高质量实时绘制。     

螺旋线轨迹在纹理合成算法中的应用

本文在MRF模型和已有块拼贴算法的基础上,根据纹理的邻域相关性以及匹配点的位置分布在上次合成匹配点邻域的概率较大这一特点,直接选取前一匹配块的相邻块为待选最佳匹配块,使算法能够快速地采样到最优匹配块,并能较好的保持合成纹理的邻域相关性;同时,采用螺旋顺序逐块合成纹理,能够加强对合成过程的约束,克服了合成过程中不连续区域的出现。本文算法较好的维持了样本图的结构特征,在保证纹理合成质量的同时,能够有效的减少算法的计算量。     

视点依赖的温室场景模拟与交互式漫游

为对包含日光温室的农业场景进行实时、逼真的绘制,采用基于视点的连续细节层次（LOD）来减少实际需要绘制的网格数据量,并基于包围盒技术实现了视点的碰撞检测,同时使用可见性剔除算法来加速场景渲染速度。在渲染温室内植物时,通过几何变换实现了大规模植物群体的快速构建,并在场景中使用阴影体算法来渲染阴影,生成了具有真实感的大规模温室农业场景。模拟结果表明该方法能有效地减少渲染的面元数目,大大提高了绘制速率,场景有较高的真实感,能够满足交互式实时漫游的要求。     

Fast adaptive blue noise on polygonal surfaces

This paper proposes a novel method for the computation of hierarchical Poisson disk samplings on polygonal surfaces. The algorithm generates a pointerless hierarchical structure such that each level is a uniform Poisson disk sampling and a subset of the next level. As the main result, given a dynamically-varying importance sampling function defined over a surface, the hierarchy is capable of generating adaptive samplings with blue noise characteristics, temporal-coherence and real-time computation. Classical algorithms produce hierarchies in tight ratios, which is a serious bottleneck specially for a large number of samples. Instead, our method uses sparse ratios and decreases the adaptation error of the hierarchy through a fast optimization process. Therefore, we save a considerable amount of time (up to 74% in our experiments) while preserving the good blue noise properties. We present applications on Non-Photo Realistic rendering (NPR), more specifically, on surface stippling effects. First, we apply our method by taking illumination to be the importance sampling to shade the surface, and second, we dynamically deform a surface with a predefined stippled texture.     

A parallel algorithm for improving the maximal property of Poisson disk sampling

This paper presents a simple yet effective algorithm to improve an arbitrary Poisson disk sampling to reach the maximal property, i.e., no more Poisson disk can be inserted. Taking a non-maximal Poisson disk sampling as input, our algorithm efficiently detects the regions allowing additional samples and then generates Poisson disks in these regions. The key idea is to convert the complicated plane or space searching problem into a simple searching on circles or spheres, which is one dimensional lower than the original sampling domain. Our algorithm is memory efficient and flexible, which generates maximal Poisson disk sampling in an arbitrary 2D polygon or 3D polyhedron. Moreover, our parallel algorithm can be extended from the Euclidean space to curved surfaces in an intrinsic manner. Thanks to its parallel structure, our method can be implemented easily on modern graphics hardware. We have observed significance performance improvement compared to the existing techniques.     

Approximate Poisson disk sampling on mesh

Poisson disk sampling has been widely used in many applications such as remeshing, procedural texturing, object distribution, illumination, etc. While 2D Poisson disk sampling is intensively studied in recent years, direct Poisson disk sampling on 2-manifold surface is rarely covered. In this paper, we present a novel framework which generates approximate Poisson disk distribution directly on mesh, a discrete representation of 2-manifold surfaces. Our framework is easy to implement and provides extra flexibility to specified sampling issues like feature-preserving sampling and adaptive sampling. We integrate the tensor voting method into feature detection and adaptive sample radius calculation. Remeshing as a special downstream application is also addressed. According to our experiment results, our framework is efficient, robust, and widely applicable.     

The 4-way deterministic tiling problem is undecidable

It is shown that the (infinite) tiling problem by Wang tiles is undecidable even if the given tile set is deterministic by all four corners, i.e. a tile is uniquely determined by the colors of any two adjacent edges. The reduction is done from the Turing machine halting problem and uses the aperiodic tile set of Kari and Papasoglu.     

Capacity-Constrained Delaunay Triangulation for point distributions

Sample point distributions possessing blue noise spectral characteristics play a central role in computer graphics, but are notoriously difficult to generate. We describe an algorithm to very efficiently generate these distributions. The core idea behind our method is to compute a Capacity-Constrained Delaunay Triangulation (CCDT), namely, given a simple polygon P in the plane, and the desired number of points n, compute a Delaunay triangulation of the interior of P with n Steiner points, whose triangles have areas which are as uniform as possible. This is computed iteratively by alternating update of the point geometry and triangulation connectivity. The vertex set of the CCDT is shown to have good blue noise characteristics, comparable in quality to those of state-of-the-art methods, achieved at a fraction of the runtime. Our CCDT method may be applied also to an arbitrary density function to produce non-uniform point distributions. These may be used to half-tone grayscale images.     

一种城区LiDAR点云数据的抽稀算法

当城区LiDAR点云数据密度较大时，存在大量的数据冗余，造成了计算量大、效率低、显示不便等一系列问题，使得建筑物的三维可视化及三维重建等应用受到较大挑战。针对该问题，结合泊松碟采样在测地空间中的地形自适应特点，提出了适用于城区LiDAR点云数据的抽稀算法。泊松碟采样随机将与已有采样点的测地距离大于某一阈值的点加入采样点集，并不断重复这一过程直至没有新的采样点加入为止。在此基础上，依据LiDAR点云数据的特点，定义了一种新的与所选点与其邻域内其他点间高度差标准差相关的加权测地距离，改进了泊松碟采样算法。该方法能有效调整城区建筑物的采样率，从而尽可能地保持建筑物的原始特征，并保留良好的可视化效果。四组对比实验结果表明了该算法的适用性及高效性。     

一种城区LiDAR点云数据的抽稀算法

当城区LiDAR点云数据密度较大时,存在大量的数据冗余,造成了计算量大、效率低、显示不便等一系列问题,使得建筑物的三维可视化及三维重建等应用受到较大挑战。针对该问题,结合泊松碟采样在测地空间中的地形自适应特点,提出了适用于城区LiDAR点云数据的抽稀算法。泊松碟采样随机将与已有采样点的测地距离大于某一阈值的点加入采样点集,并不断重复这一过程直至没有新的采样点加入为止。在此基础上,依据LiDAR点云数据的特点,定义了一种新的与所选点与其邻域内其他点间高度差标准差相关的加权测地距离,改进了泊松碟采样算法。该方法能有效调整城区建筑物的采样率,从而尽可能地保持建筑物的原始特征,并保留良好的可视化效果。四组对比实验结果表明了该算法的适用性及高效性。     

离散曲面的近似Poisson盘采样

Poisson盘采样作为计算机图形学的一个重要课题,在重网格化、过程纹理、物体分布、光照计算等方面都有重要应用.虽然最近几年对于2维平面Poisson盘采样的研究比较密集,但是直接对于2维流形表面上的Poisson盘采样的研究却比较少.在本文中,我们提出了一种可以直接在Mesh表面生成近似Poisson盘分布的方法.此方法实现简单,同时可以通过简单修改适用于保特征的采样和自适应采样.文中引入了张量投票的方法来实现特征识别和自适应采样半径的计算,并给出了采样后的重网格化结果,作为此算法的一个后期应用.通过大量实例表明,本文方法快速、鲁棒、适用广泛.     

基于DNA Tiles自组装的布尔逻辑运算

大量研究工作表明,DNA tiles自组装现象是分子生物计算过程中一个很重要的计算方式.分子自组装的基本特点在于由许多小分子在一定机理的作用下,自动形成更大规模的超级分子结构的过程.自组装用于计算,在于这种组装模式可以抽象成一个自动化的系统,只需根据问题的需要设计好输入,再将其输入到运算系统,经过分子自组装过程,最后能生成问题的解.文中基于这样的运算机理,在DNA tiles自组装这个计算平台上,尝试做布尔逻辑运算,针对4变量4句子的布尔逻辑问题,提出一个DNA tiles自组装自动化运算系统.     

A Comparison of Methods for Generating Poisson Disk Distributions

Poisson disk distributions have many applications in the field of computer graphics. Besides sampling, Poisson disk distributions are used in object distribution, non‐photorealistic rendering and procedural texturing. Over the years, a large number of methods for generating Poisson disk distributions have been proposed, making it difficult to choose the right method for a given application. In this paper, we present a detailed comparison of most techniques for generating Poisson disk distributions. The methods we study include dart throwing, relaxation dart throwing, Lloyd's relaxation, Shade's Poisson disk tiles, tiled blue noise samples, fast hierarchical importance sampling with blue noise properties, edge‐based Poisson disk tiles, template Poisson disk tiles, corner‐based Poisson disk tiles and recursive Wang tiles for real‐time blue noise. Analysing all of these methods within a single framework is one of the major contributions of this work.