中国科学院软件研究所机构知识库
Advanced  
ISCAS OpenIR  > 中科院软件所  > 中科院软件所
题名:
计算机图形学中若干基本问题及光线跟踪技术的研究
作者: 李静
答辩日期: 2007-06-08
授予单位: 中国科学院软件研究所
授予地点: 软件研究所
学位: 博士
关键词: 光线跟踪 ; 加速 ; 凸剖分 ; 包容性检测 ; 裁剪 ; ; 多边形 ; 多面体
其他题名: Research on Several Fundamental Problems in Computer Graphics and Ray Tracing Techniques
摘要: 加速三维场景的真实感绘制一直是计算机图形学中的研究热点。其中,光线跟踪是真实感绘制的重要方法之一,它能精确地模拟再现场景,产生高度真实的绘制结果。但是,这种方法的计算量巨大,妨碍了它的绘制速度,难以进行实时绘制。因此,光线跟踪加速算法一直是计算机图形学中的重要研究内容。因为这方面的工作涉及大量的基本几何运算,本文旨在探索相关的基础几何运算的高效实现,并由此发展先进的光线跟踪技术,以提高三维场景的绘制速度。本文对点在多边形/多面体内的判定计算、任意多边形的线裁剪、多面体的凸剖分等基本几何运算进行了深入研究,并发展了若干创新技术;提出了新颖的空间组织技术,极大地提高了光线跟踪计算的速度,能交互地对大规模动态场景进行高度真实感的绘制。 本文的主要贡献和创新点如下: (1)提出两种多边形点包容性的高效判定算法,即基于边层的判定算法和基于凸剖分的判定算法。前者通过将多边形的边划分为一些边层来进行加速。其空间复杂度为O(n),预处理时间复杂度介于O(n)和O(n2)之间,判定时间复杂度介于O(log n)和O(n)之间,但在大多数情况下小于O((log n)2)。后者的加速则基于将多边形剖分为一些凸多边形。其期望预处理时间复杂度为O(n log n),空间开销为O(n),判定时间复杂度为O(log n),与现有的先进算法(如梯形法)相当。但由于该算法需要处理的对象(凸多边形)个数较少,因此它能比其它先进算法更快。此外,这两种算法均无需处理奇异情况,优于许多常用算法。 (2)提出一种基于层次的多面体表示方法,并以其为基础给出了一种解决多面体点包容性问题的有效方法,即对多面体的面和边进行顺序组织,从而可以用二分查找法加速点的包容性检测。由于许多几何信息被隐含表示,因此该算法的空间需求大大小于传统表示法。其预处理时间介于O(n)与O(n2)之间;其判定时间复杂度在O(n)至O(log n) 之间变化,且 在大多数情况下小于O((log n)3)。当它与组织多面体面片的八叉树结构结合。后,其判定速度与目前最快的基于BSP的点包容性判定算法相若,但能显著降低预处理时间和空间需求,特别适合处理大模型。 (3)提出两种多边形窗口线裁剪算法,一种是通过将多边形剖分成一些凸多边形进行加速,另一种则是通过将多边形的边分解为凸片段进行加速。两者的裁剪计算复杂度均在O(log n)和O(n)之间自适应变化,并在大多数情况下小于O(n)。它们非常适合对同一复杂多边形窗口进行多次裁剪的应用。实验表明,在某些情况下,如多边形对多边形的裁剪,新方法的总执行速度(包括预处理时间和裁剪时间)依然要比已有的不要预处理的裁剪算法快很多。 (4)提出一种多面体凸剖分新算法,它利用多面体各个元素(点、边、面)之间的遮挡关系将多面体分割成一些单层多面体,然后再对各个单层多面体进行凸剖分。对于实践中的常用模型,新方法的时间复杂度、空间复杂度、剖分结果凸多面体个数皆近似为O(n),其新增加顶点数的复杂度近似 为O(r + n1/2),其中n为多面体的点数,r为多面体凹边个数。由于该方法对凹边数量不敏感且易于处理多种非流形情况,因此在处理复杂多面体时具有很高的效率,优于目前国际上的类似工作。 (5)提出了一项光线跟踪新方法,能有效提高光线在空白区域的行进速度。该方法首先用一种新方法创建网格,然后用较少的空盒自适应聚集空网格单元,以加快光线跟踪的计算。新加速结构的创建时间复杂度和空间复杂度均是O(n),而在光线跟踪计算时的时间复杂度为O(log n),与kd 树结构相当。当它与已有的一些加速结构相结合后,能极大地提高光线跟踪计算速度,很好地处理大规模动态场景。
英文摘要: Increasing the speed of 3d photorealistic rendering is always a hot topic in the field of Computer Graphics. Ray tracing is one of the most important method for photorealistic rendering. It can simulate and reproduce scenes precisely, producing images of high photorealistic quality. However, such method requires heavy computation, which jeopardizes its speed and makes it hard to render scenes in real time. Therefore, algorithms for accelerating ray tracing have long been important contents of computer graphics research. Works on this aspect involve a large amount of fundamental geometrical computations. So we aims to explore high efficient implementations of these fundamental geometrical computations, from which we develop advanced ray-tracing techniques to increase the rendering speed. In this thesis, several fundamental geometrical problems, for example, point-in-polygon/polyhedron problem, line clipping against arbitrary polygons, convex decomposition of polyhedron, are studied thoroughly and some novel techniques are developed. This thesis also proposes new techniques for spatial organization, which increase the speed of ray tracing so evident that we can interactively render large and dynamic scenes on a common PC. Its contribution and novelties are mainly in the following aspects: (1) We propose two high efficient algorithm for point-in-polygon problem, namely the method based on edge layers and the method based on convex decomposition. The former accelerates the test by classifying polygon edges into layers. Its storage complexity is O(n), here, n is the number of the edge of polygon. The time complexity of its preprocess ranges from O(n) to O(n2). And its inclusion test has a time complexity between O(log(n)) and O(n), but less than O((log(n))2) in most cases. The later speed up the test by decomposing original polygon into convex subpolygons. Its expected complexity for preprocessing time, storage and testing time are O(nlog(n)), O(n) and O(log(n)) respectively, which is compatible with current advanced algorithms, such as trapezoidation-based method. However, as the subparts to be handled (convex polygon) are fewer, it can run faster than other advanced algorithms. Moreover, the two method both do not need to handle singularities, which excels many general methods. (2) We present a layer-based representation of polyhedrons. And based on it, we gave an efficient solution to point-in-polyhedron tests. That is, by sequentially arranging the facets and edges of a polyhedron, inclusion tests can be speeded up at the aid of binary search algorithm. As much geometrical information can be represented implicitly, the new algorithm’s storage requirement is much less than the conventional representation. The new method’s time complexity on preprocess is between O(n) and O(n2). Its time complexity on inclusion test varies from O(n) to O(logn), and less than O(log3n) in most cases. When it is combined with an octree for organizing polyhedrons, it can run in a speed comparable with that by BSP-based inclusion test methods, the fastest methods to date, while reducing storage and preprocessing time greatly, which is very suitable for handling large polyhedrons. (3) We give two novel line clipping approaches against a general polygon. Their strategies for accelerating are decomposing the polygon into elementary convex parts and partitioning the polygon’s edge into convex segments respectively. Their clipping time complexities are both between O(n) and O(log(n)), and better than O(n) in most cases. They are very suitable for applications where multiple clipping are needed against the same complex polygon. Our experiments showed that under some conditions, for example, clipping a polygon against another polygon, the total executing speed, including preprocessing time and clipping time, is still much faster than that of the clipping algorithms without preprocess. (4) We provide a novel approach for decomposing a general polyhedron into convex polytypes. It firstly makes use of the occlusion relationships between polyhedron’s elements (vertices, edges and facets) to partition the polyhedron into some so-called single-layer polyhedrons. Then, it decomposes every non-convex single-layer polyhedron into convex subpolyhedron. For common complex models in practice, the new method’s complexity for decomposing time, storage requirement and the number of resulting convex parts are all approach O(n), and the complexity for the number of new added vertices is similar to O(r+n1/2), where n is the original polyhedron’s vertex number and r is its reflex edge number. Since the method is not sensitive to reflex edge number and can handle many kinds of non-manifold cases easily, it has higher efficiency than other state-in-art works when dealing with complex polyhedrons. (5) We propose a new technique of ray tracing for speeding up ray traversal in empty regions. It first presents a novel method to produce grids, and then takes empty boxes to largely gather empty grids. With respect to both construction time and storage requirements, the new structures are all of complexity O(n), while with respect to ray tracing, the new structures behave like kd-trees of complexity O(logn). When this technique is integrated with existing hierarchical structures, ray tracing computation can be greatly sped up and large and dynamic scenes can be handled nicely.
语种: 中文
内容类型: 学位论文
URI标识: http://ir.iscas.ac.cn/handle/311060/6796
Appears in Collections:中科院软件所

Files in This Item:
File Name/ File Size Content Type Version Access License
10001_200418015029048李静_paper.pdf(8350KB)----限制开放-- 联系获取全文

Recommended Citation:
李静. 计算机图形学中若干基本问题及光线跟踪技术的研究[D]. 软件研究所. 中国科学院软件研究所. 2007-06-08.
Service
Recommend this item
Sava as my favorate item
Show this item's statistics
Export Endnote File
Google Scholar
Similar articles in Google Scholar
[李静]'s Articles
CSDL cross search
Similar articles in CSDL Cross Search
[李静]‘s Articles
Related Copyright Policies
Null
Social Bookmarking
Add to CiteULike Add to Connotea Add to Del.icio.us Add to Digg Add to Reddit
所有评论 (0)
暂无评论
 
评注功能仅针对注册用户开放,请您登录
您对该条目有什么异议,请填写以下表单,管理员会尽快联系您。
内 容:
Email:  *
单位:
验证码:   刷新
您在IR的使用过程中有什么好的想法或者建议可以反馈给我们。
标 题:
 *
内 容:
Email:  *
验证码:   刷新

Items in IR are protected by copyright, with all rights reserved, unless otherwise indicated.

 

 

Valid XHTML 1.0!
Copyright © 2007-2017  中国科学院软件研究所 - Feedback
Powered by CSpace