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.

The Uniaxial Tensile Deformation of Ni Nanowire: Atomic-Scale Computer Simulations

The mechanical deformations of nickel nanowire subjected to uniaxial tensile strain at 300 K are simulated by using molecular dynamics with the quantum corrected Sutten-Chen many-body force field. We have used common neighbor analysis method to investigate the structural evolution of Ni nanowire during the elongation process. For the strain rate of 0.1%/ps, the elastic limit is up to about 11% strain with the yield stress of 8.6 GPa. At the elastic stage, the deformation is carried mainly through the uniform elongation of the distances between the layers (perpendicular to the Z-axis) while the atomic structure remains basically unchanged. With further strain, the slips in the {111} planes start to take place in order to accommodate the applied strain to carry the deformation partially, and subsequently the neck forms. The atomic rearrangements in the neck region result in a zigzag change in the stress-strain curve; the atomic structures beyond the region, however, have no significant changes. With the strain close to the point of the breaking, we observe the formation of a one-atom thick necklace in Ni nanowire. The strain rates have no significant effect on the deformation mechanism, but have some influence on the yield stress, the elastic limit, and the fracture strain of the nanowire.

Dependence of collision frequency on distance between two hard-sphere particles estimated by computer simulation

A Monte Carlo simulation is performed to study the dependence of collision frequency on interparticle distance for a system composed of two hard-sphere particles. The simulation quantitatively shows that the collision frequency drops down sharply as the distance between two particles increases. This characteristic provides a useful evidence for the collision-reaction dynamics of aggregation process for the two-particle system described in the other reference.

Computer Simulation Of Random Sphere Packing In An Arbitrarily Shaped Container

Most simulations of random sphere packing concern a cubic or cylindric container with periodic boundary, containers of other shapes are rarely studied. In this paper, a new relaxation algorithm with pre-expanding procedure for random sphere packing in an arbitrarily shaped container is presented. Boundaries of the container are simulated by overlapping spheres which covers the boundary surface of the container. We find 0.4 similar to 0.6 of the overlap rate is a proper value for boundary spheres. The algorithm begins with a random distribution of small internal spheres. Then the expansion and relaxation procedures are performed alternately to increase the packing density. The pre-expanding procedure stops when the packing density of internal spheres reaches a preset value. Following the pre-expanding procedure, the relaxation and shrinking iterations are carried out alternately to reduce the overlaps of internal spheres. The pre-expanding procedure avoids the overflow problem and gives a uniform distribution of initial spheres. Efficiency of the algorithm is increased with the cubic cell background system and double link data structure. Examples show the packing results agree well with both computational and experimental results. Packing density about 0.63 is obtained by the algorithm for random sphere packing in containers of various shapes.

Computer simulation of influence of sedimentation on rapid coagulation

A computer simulation was performed to explore the features and effects of sedimentation on rapid coagulation. To estimate the accumulated influence of gravity on coagulation for dispersions, a sedimentation influence ratio is defined. Some factors possibly related to the influence of sedimentation were considered in the simulation and analysed by comparing the size distribution of aggregates, the change in collision number, and coagulation rates at different gravity levels (0 g, 1 g and more with g being the gravitational constant).

Computer simulation on the collision-sticking dynamics of two colloidal particles in an optical trap

Collisions of a particle pair induced by optical tweezers have been employed to study colloidal stability. In order to deepen insights regarding the collision-sticking dynamics of a particle pair in the optical trap that were observed in experimental approaches at the particle level, the authors carry out a Brownian dynamics simulation. In the simulation, various contributing factors, including the Derjaguin-Landau-Verwey-Overbeek interaction of particles, hydrodynamic interactions, optical trapping forces on the two particles, and the Brownian motion, were all taken into account. The simulation reproduces the tendencies of the accumulated sticking probability during the trapping duration for the trapped particle pair described in our previous study and provides an explanation for why the two entangled particles in the trap experience two different statuses. (c) 2007 American Institute of Physics.

Collective evolution characteristics and computer simulation of short fatigue cracks

Fatigue testing was conducted using a kind of triangular isostress specimen to obtain the short-fatigue-crack behaviour of a weld low-carbon steel. The experimental results show that short cracks continuously initiate at slip bands within ferrite grain domains and the crack number per unit area gradually increases with increasing number of fatigue cycles. The dispersed short cracks possess an orientation preference, which is associated with the crystalline orientation of the relevant slip system. Based on the observed collective characteristics, computer modelling was carried out to simulate the evolution process of initiation, propagation and coalescence of short cracks. The simulation provides progressive displays which imitate the appearance of experimental observations. The results of simulation indicate that the crack path possesses a stable value of fractal dimension whereas the critical value of percolation covers a wide datum band, suggesting that the collective evolution process of short cracks is sensitive to the pattern of crack site distribution.