basic research in computer science and software engineering at sklcs

The State Key Laboratory of Computer Science (SKLCS) is committed to basic research in computer science and software engineering. The research topics of the laboratory include: concurrency theory, theory and algorithms for real-time systems, formal specifications based on context-free grammars, semantics of programming languages, model checking, automated reasoning, logic programming, software testing, software process improvement, middleware technology, parallel algorithms and parallel software, computer graphics and human-computer interaction. This paper describes these topics in some detail and summarizes some results obtained in recent years.

外科手术计算机辅助导航技术

外科手术计算机辅助导航即利用计算机图形图像技术对放射影像学资料进行处理 ,重建二维或三维的医学图像模型 ,同时结合各种空间定位技术 ,在医师的双眼、手术工具及患者的头部之间建立一个实时的环路 ,实现手术过程中器械位置的实时或准实时显示。我们综述了外科手术计算机辅助导航系统的发展历史和研究现状 (重点阐述了其系统结构和关键技术 ,包括空间定位技术、图像处理与显示技术、系统配准技术、头部定位技术等 (最后给出了手术导航系统的发展趋势

嵌入式DSP系统中SDF模型的层次化存储优化方法

在同步数据流模型(SDF)描述的嵌入式数字信号处理(DSP)系统中,计算体单一出现调度(SAS)算法对于存在反馈环和数据密集处理的应用不可解或内存优化效果很差.文中提出了将SAS和Non-SAS类型调度算法相结合的层次化的存储优化方法,定义了数据密集分量和强连通分量来描述环和数据密集处理结构,并依据数据优先消耗原则设计了启发式的Non-SAS调度算法对分量进行存储优化.该方法适用于任意SDF模型,并有良好的存储优化效果.实验结果证明了其有效性.

基于贝塞尔曲线的WSN等值线绘制算法

从无线传感器网络(WSN)环境数值监测应用的实际需求出发,提出了一种应用于该类场景中的等值线绘制(CMBC)算法.CMBC算法基于图形学中常用的贝塞尔(Bezier)曲线理论,通过选择部分节点提供信息给网关节点绘制等值线.此方法有效解决了监测应用场景中对最终监测精度的需求与大量报告节点所引发的高流量负载和网络能耗之间的矛盾.仿真结果表明,CMBC算法和已有研究工作相比能够使用更少的汇报节点完成高精度等值线的绘制,因此CMBC算法能够节省节点的能量,延长网络的生存期.

基于桶内动态融合的透明现象的高效绘制

基于桶排序的顺序独立透明现象绘制算法,采用桶排序原理将投影收集到同一个像素上的多个片元并排序,当发生桶内片元冲突时会产生错误的绘制结果.为此,提出一种基于桶内动态融合的透明现象的高效绘制算法.此算法采用桶内动态融合和并发读/写的方法逐一融合落入同一个桶内的所有片元,并在后处理中按从前向后的顺序融合各个桶内的颜色值.由于同时发生桶内片元冲突和读/写冲突的概率非常小,因而可以大大提高绘制结果的准确性.实验结果表明,与基于桶排序的绘制算法相比,采用文中算法可以更准确地绘制场景,生成与真实结果非常相近的绘制效果,同时算法的效率基本保持不变.

工程地质三维建模与可视化技术应用开发

Synthetic Geology Information System (SGIS) is an important constituent part of the theory of Engineering Geomechanics Mate-Synthetic (EGMS), and is the information system more suited for the collection, storage, management, analysis and processing to the information coming from engineering geology,' geological engineering and geotechnical engineering. Its contents involve various works and methods of the investigation, design, and construction in different stages of the geological engineering. Engineering geological and three-dimensional modeling and visualization is the fundamental part of the SGIS, and is a theory, method and technique by which, adopting the computer graphics and image processing techniques, the data derived from engineering geological survey and the calculated results obtained from the geomechanical numerical simulation and analysis are converted to the graphics and images displayed on the computer screen and can be processed interactively. In this paper, the significance and realizing approaches of the three-dimensional modeling and visualization for the complex geological mass in the engineering geology are discussed and the methods of taking advantage of the interpolation and fitting for the scattered and field-surveyed data to simulate the geological layers, such as the topography and earth surface, the groundwater table and the stratum boundary, are researched into. At the mean time, in mind the characteristics of the structure of the basic data for three-dimensional modeling, its visual management can be resolved into the engineering surveyed database management module, plot parameter management module and data output module and the requirement for basic data management can be fulfilled. In the paper, the establishment and development of the three-dimensional geological information system are probed tentatively, and an instance of three-dimensional visual Engineering Distribution Information System (EDIS), theConstruction Management Information System for an airport, in which the functions, such as the real-time browse among the three-dimensional virtual-reality landscapes of the airport construction from start to finish, the information query to the airport facility and the building in the housing district and the recording and playback of the animation sets for the browse and the takeoff and landing of the planes, is developed by applying the component-mode three-dimensional virtual-reality geological information system (GIS) software development kits (SDK), so the three-dimensional visual management platform is provided for the airport construction. Moreover, in the gaper, integrated with the three-dimensional topography visualization and its application in the Sichuan-Tibet Highways, the method of the digital elevation model (DEM) data collection from the topographic maps is described, and the three-dimensional visualization and the roaming about the terrain along the highway are achieved through computer language programming. Understanding to the important role played by the varied and unique topographical condition in the gestation and germination of the highly-dense, frequently-arising and severely-endangered geological hazards can be deepened.

地震勘探三维可视化方法研究与实现

This thesis mainly studies the technologies of 3-D seismic visualization and Graphic User Interface of seismic processing software. By studying Computer Graphics and 3-D geological modeling, the author designs and implements the visualization module of seismic data processing software using OpenGL and Motif. Setting seismic visualization flow as the subject, NURBS surface approximation and Delaunay Triangulation as the two different methods, the thesis discusses the key algorithms and technologies of seismic visualization and attempts to apply Octree Space Partitioning and Mip Mapping to enhance system performance. According to the research mentioned above, in view of portability and scalability, the author adopts Object-oriented Analysis and Object-oriented Design, uses standard C++ as programming language, OpenGL as 3-D graphics library and Motif as GUI developing tool to implement the seismic visualization framework on SGI Irix platform. This thesis also studies the solution of fluid equations in porous media. 2-D alternating direction implicit procedure has been turned into 3-D successive over relaxation iteration, which possesses such virtues as faster computing speed, faster convergence rate, better adaptability to heterogeneous media and less memory demanding.