【作者】 程志全；

【导师】 金士尧；

【作者基本信息】 国防科学技术大学 ， 计算机科学与技术， 2008， 博士

【摘要】 在万维网刚刚出现的时候,人们曾梦想建立一个能自由游历的三维虚拟世界。在此网络虚拟环境中,通过“三维图形界面”,用户不再受限于物理时空的约束,可以方便地进行交流、研讨、训练、娱乐,甚至协同完成同一件比较复杂的产品设计或进行同一艰难任务的演练。但迄今为止,这个梦想仍然没有实现。目前面临的情况是:一方面,图形表示的直观性能帮助人们理解抽象而复杂的事物,人们越来越离不开三维几何图形;另一方面,三维几何模型数据的复杂性给数据在网络上的传输带来了困难,可能让使用者失去等待的耐心。造成目前窘境的根本原因是:通过互联网来存取异地的三维几何模型,使得本已十分有限的网络带宽变得更加紧张;更重要的是,互联网目前的速度远不能满足复杂三维几何模型实时传输的需求。从而,研究如何在网络上高效提供和实时传输用户所需的三维几何信息是促进网络图形学技术迅速发展的当务之急。流式传输是当前最流行的网络媒体传输形式。作为新兴的数字媒体,三维几何模型将点播视频时的被动接受变为主动控制,体现了比图像和视频等传统媒体更高的优越性。但因为三维几何模型自身的复杂性,既有的流媒体技术难以高效地传输三维几何模型。因此,本文研究三维几何模型的流式传输技术:用户不必等待完整的文件下载完毕,就可以实现三维几何模型的尽快“真实”交互和连续“实时”传输。在确立了“三维几何模型的流式传输”概念后,本文深入地研究了其关键技术:三维几何模型的渐进式压缩、视点相关的流式传输、具有错误控制功能的流式传输和基于当前/下一代网络的高效安全的分布式通信框架。首先,以三角形网格模型为研究对象,本文提出了一种三维几何模型渐近式压缩算法。该算法能有效减小三维几何模型的占用空间,并将其转变为适合于网络传输的表示。该算法对三角形网格进行渐进式度驱动拓扑压缩,并根据网格模型几何信息中切向和法向要素重要程度不同这一事实,采用不同的量化方法对切向信息和法向信息进行几何压缩。实验表明,本文的渐进式度驱动算法在拓扑压缩和几何压缩两个方面都具有很好的编码效率。特别是,与SIGGRAPH 2001上发表的原渐进式度驱动算法相比,测试模型的几何压缩性能提高了4%～20%;并具有更好的率失真曲线。其次,本文提出了一种基于网格有意义分割的视点相关的流式传输算法。以视觉分割领域的最小值规则为基础,网格有意义分割将三维几何模型视作不同子部分的集合体,并将对象上的凹部看成组成要素的边界。通过计算各顶点的最小主曲率值,算法将具有较低负值的顶点集标识为凹部,并进一步提取出凹部的特征轮廓线;对于所有的特征轮廓线,在排序后,按照优先级从高到低的顺序依次进行闭合处理和显著性测试,进而将通过测试的闭合轮廓线视作不同子块间分割的边界边。接下来,对各分割子块进行基于半边折叠的渐进式压缩,进而利用一种新型数据结构实现随机访问和视点相关的流式传输。从而,该算法可以根据视点信息灵活控制模型各子部分的分辨率,更加有效地降低传输模型数据时对网络带宽的需求。再次,采用两种技术来实现具有错误控制的流式传输,减小和预防包丢失等错误带来的影响。一种是降低错误扩散范围的网格分割机制。新的网格分割算法扩展了分解二维图形轮廓的捷径规则,将其拓展到三维网格分割领域。在分割算法执行过程中,先用垂直于局部骨架段的切割面扫描模型骨架的排序分支,通过测量切割面的拓扑和几何属性来确定用分割关键点标识的大致分割位置,而后利用大致分割位置附近的模型表面凹部特征来定义子块间的具体合理边界,从而得到鲁棒的有意义分割结果。另一种是加入冗余信息的容错算术编码方案。本文提出了一种面向三维几何模型压缩的容错扩展多步量化EMQ(extended multiplequantization)算术编码算法。通过插入周期性的起止位,该容错的EMQ算术编码算法进一步分割了传输的比特流,并提供了基本的错误检测和校正功能。最后,本文提出一种传输三维几何模型的新型分布式通信框架。该框架采用面向服务的客户端、中间服务层和企业信息系统三层软件结构,其中的客户端和中间服务层均采用了“模型-视图-控制器”设计模式。在该分布式通信框架设计中,我们开发了一种带纹理的三维几何模型的自适应生成算法,阐述了流式传输三维几何场景的有效组织结构以及合理的分发机制,提出了一种服务质量控制方案来确保客户端的实时交互性。并利用虚拟战场环境的应用实例对该框架进行了充分测试。测试结果表明,该框架可以满足远程用户实时访问的需求,恢复出的模型具有较好的逼真度。简而言之,该分布式通信框架具有合理的体系结构,并具有适应性好和可扩展性强等特点。本论文的研究成果对丰富计算机网络和图形学有重大的学术价值,对研究和开发网络虚拟博物馆、计算机辅助异地协同设计、科学计算远程可视化和因特网地理信息系统等应用具有重要的指导意义和参考价值。而且,其研究成果已在实际工程项目中获得了重要应用,取得了显著的效益。更多还原

【Abstract】 At the emergence of the World Wide Web, people ever dreamed about building a free-surfing three-dimensional (3D) virtual world. In this world, users could conveniently commune, deliberate, educate, entertain, even cooperate to design one sophisticated product or drill one difficult task by easy 3D graphical interface, while no longer constrained by physical space-time conditions. However, the vision has not come true until now. At present, the actual status can be illustrated as the following: on the one hand, peoples are more depending on the 3D graphics due that the graphical representation, especially the abstract and sophisticated things, is intuitional and easy to understand, on the other hand, the complexity of 3D geometrical data results in difficulty of network transmission, even out of user patience for waiting the data. The prime bottleneck preventing remote rending applications from extensive use is the antinomy between the network transmission and the geometrical data. In fact, the finite network bandwidth is more insufficient for 3D models, and the speed of current internet is far from the real-time transmitting requirement of large-scale 3D geometrical models. Consequently, the research on effective provision and real-time transmission of 3D geometrical information required by the user is one urgent affair, which can greatly promote the development of network graphics. This demand has not been fulfilled by software standards or their implementations, leaving a wide potential field for technical innovations.Currently, streaming is one of the most popular forms for network media transmission. As one burgeoning digital media, 3D geometrical model is more advantaged than traditional media, e.g., image and video, since it is initiative command rather than passive acceptance when ordering program of visualization. However, existed streaming media technique does not offer efficient transfers due to the complexity of 3D geometry. Thereby, the 3D streaming technologies are thoroughly investigated in the dissertation, whose main goal is to provide 3D contents in real time for users over a network connection, such that the interactivity and visual qualities of contents may match as closely as if they were stored locally, especially making interactions with 3D data possible without a complete download. Following the first established concept, streaming transmission of 3D geometry models, the key technique is studied. In the concrete, the researched themes include new pioneering designs and solutions for progressive compression, view-dependent and error-controlling streaming technologies for 3D models as well as technologies and applications for distribution frameworks, networking technologies for efficient and robust data communication mechanisms on current and next generation networks.Firstly, a progressive compression algorithm for triangle meshes is proposed, which can effectively reduce the storage size of triangle models by encoding it in a compact format and is suitable for network. The compression is driven by progressive degree-based topological encoding and a simple multi-granularity quantization in geometrical encoding, which allows making better of the dynamic range (different number bits in normal/tangential components) than with a fixed-bit representation. Experiments have shown that the presented method outperforms in the compression ratio. Particularlly, our proposed coder outperforms the original, proposed in SIGGRAPH 2001, in the rate-distortion curve and geometry coding efficiency, and the range of improvements is typically around 4%~20%.Secondly, a view-dependent mesh streaming algorithm has been proposed in this dissertation, which first attempts to effectively integrate the mesh compression with meaningful segmentation. The proposed algorithm first divides a mesh model into several meaningful components based on the minima rule from cognitive theory. The minima rule states that human perception usually divides a surface into parts along the concave discontinuity of the tangent plane. Our segmentation method extracts features, based on the minimal principal curvature value of surface vertices, to find candidate contours located in the valley. These open contours are prioritized to select the most salient one. Then, the selected open contour is automatically completed to form a loop around a specific part of the mesh by principal component analysis of its vertices. And then, the approach encodes each partition independently by a progressive half-edge collapse compression algorithm. The whole scene is organized by a new data structure, called hierarchical element tree, to progressively transmit and render selective meaningful parts in a view-dependent and random-access way. Therefore, the method can flexibly manipulate the resolution of different parts by elimination of insignificant details, and can reduce the required bandwidth by transmitting only high-resolution of visible parts while cutting out unusable details of invisible parts.Thirdly, two error-controlling mesh streaming approaches have been respectively adopted to reduce and prevent the error effects caused by package missing on network. The one is mesh segmentation scheme to depress channel error propagation. The typical 2D silhouette parsing short-cut rule is introduced to 3D mesh segmentation domain. Guided by the extended 3D short-cut rule theory, the method makes use of new geometrical and topological functions of skeleton to define initial cutting critical points by sweeping a given mesh perpendicular to every skeleton branch, and then employs salient contours with negative minimal principal curvature values to determine natural final boundary curves among parts. And sufficient experiments have been carried out on many meshes, and shown that our algorithm can provide more reasonable perceptual results in more robust way. The other is error detection through checks in the residual redundancy on the arithmetic coded data. An error resilient 3D mesh coding algorithm is developed, which employs Extended Multiple Quantization (EMQ) arithmetic coder method, inspired by the error-resilience mechanisms presented in Joint Photographic Experts Group (JPEG) 2000 image coding standards. With periodic arithmetic coder restarting and termination markers, the error resilient EMQ coder further divides bit stream into little independent parts and enables basic transmission error containment.Fourthly, the adaptive progressive remote rendering architecture (APRR), a new service-oriented architecture for progressive delivery and adaptive rendering of 3D contents, is proposed. APRR framework is designed by three common tiers, including client, middle server, and enterprise information system. The front two tiers, client and middle server, are implemented by famous "model-view-controller" design pattern. Especially, the middle service tier is comprised by loose-coupled and high-encapsulated functional modules, i.e., adaptive generation of 3D geometrical models with textures, hierarcial organization of 3D scene, and reaonable delivery mechanism of 3D modalities. The client tier is controled by a quality of service (QoS) controller for remote rendering of 3D contents, aiming at higher real-time performance just as rendering local 3D scenes. The prototype of APRR is developed and tested by a virtual military environment. The results have shown the advantages of APRR framework, which can greatly enrich the perception and performance of 3D objects in distributed applications. In a nutshell, APRR framework has many better properties, such as logical software architecture, easy flexibility and expansibility.The achievements of the dissertation have the significant academic values to enrich the computer network and computer graphics science and technology, and have the instructional meanings to develop the other projects, such as, networked Virtual Meseum, distributed collaborative Computer Aided Design, internet Geographic Information System, remote Visualization in Scientific Computing. This dissertation not only has made major progress in principle, but also has the important applications in the practical engineering projects. In fact, there are many economical/social benefits to be obtained remarkably.更多还原