Real-time interactive visibility computation for quadratic surfaces

The display of a three-dimensional scene consisting of a collection of analytically defined surfaces is accomplished via a projection mapping into the viewing plane. Ray casting is a technique which accomplishes this mapping by firing a mapping ray through each pixel of the screen into the world space. The result is the intersection points of this ray with each of the surfaces. The intersection points so found are further tested in order to determine which one is visible.

Real-time interactive graphics requires that the image be updated fast enough so that the display seems to present fluid or real time motion to the viewer. Given that the refresh of the image takes place approximately every (1/30) of a second, the determination of the above mentioned intersections should take place in this interval of time.

In this paper we present a VSLI-oriented algorithm that determines the intersection points of the mapping rays with a quadratic surface as well as the visible points. A simple shading model is presented and a VSLI architecture is briefly discussed.     

A parallel algorithm for surface-based object reconstruction

This paper presents a parallel algorithm that approximates the surface of an object from a collection of its planar contours. Such a reconstruction has wide applications in such diverse fields as biological research, medical diagnosis and therapy, architecture, automobile and ship design, and solid modeling. The surface reconstruction problem is transformed into the problem of finding a minimum-cost acceptable path on a toroidal grid graph, where each horizontal and each vertical edge have the same orientation. An acceptable path is closed path that makes a complete horizontal and vertical circuit. We exploit the structure of this graph to develop efficient parallel algorithms for a message-passing computer. Givenp processors and anm byn toroidal graph, our algorithm will find the minimum cost acceptable path inO(mn log(m)/p) steps, ifp =O(mn/((m + n) log(mn/(m + n)))), which is an optimal speedup. We also show that the algorithm will sendO(p ²(m + n)) messages. The algorithm has a linear topology, so it is easy to embed the algorithm in common multiprocessor architectures.     

Efficient direct rendering of deforming surfaces via shared subdivision trees

In this paper, we present a subdivision-based approach to rasterize implicit surfaces embedded in volumetric Bézier patches undergoing a nonlinear deformation. Subdividing a given patch into simpler patches to perform the surface rasterization task is numerically robust, and allows guaranteeing visual accuracy even in the presence of geometric degeneracies. However, due to its memory requirements and slow convergence rates, subdivision is challenging to be used in an interactive environment. Unlike previous methods employing subdivision, our approach is based on the idea where for a given patch only one subdivision tree is maintained and shared among pixels. Furthermore, as the geometry of the object changes from frame to frame, a flexible data structure is proposed to manage the geometrically varying Bézier patches. The resulting algorithm is general and maps well to parallel computing platforms such as CUDA. We demonstrate on a variety of representative graphics and visualization examples that our GPU scheme scales well and achieves up to real-time performance on consumer-level graphics cards by guaranteeing visual accuracy.     

A Three Dimensional Image Cache for Virtual Reality

Despite recent advances in rendering hardware, large and complex virtual environments cannot be displayed with a sufficiently highframe rate, because of limitations in the available rendering performance. This paper presents a new approach of software accelerated rendering which draws from the concepts of impostors, hierarchical scene subdivision and levels of detail. So far software optimization in real-time rendering has merely considered individual objects. This work is actually optimizing the rendering of the whole virtual environment by implementing a three dimensional image cache. It speeds up rendering for large portions of the scene by exploiting the coherence inherent in any smooth frame sequence. The implementation of the three dimensional image cache is discussed and the savings in rendering load achievable on a suitable hardware platform are presented.     

参数曲面导矢界估计及其在曲面绘制中的应用

目的是改进参数曲面的绘制效率。采用的方法是在参数曲线导矢界的基础上，进一步提出了3次参数曲面导矢界的公式。基于这些公式，能够较好地解决了参数曲面绘制算法过程中出现的重复绘制的问题和不连续的问题，进一步提高了曲面绘制的效果和效率。     

A parallel micro evolutionary algorithm for heterogeneous computing and grid scheduling

This work presents a novel parallel micro evolutionary algorithm for scheduling tasks in distributed heterogeneous computing and grid environments. The scheduling problem in heterogeneous environments is NP-hard, so a significant effort has been made in order to develop an efficient method to provide good schedules in reduced execution times. The parallel micro evolutionary algorithm is implemented using MALLBA, a general-purpose library for combinatorial optimization. Efficient numerical results are reported in the experimental analysis performed on both well-known problem instances and large instances that model medium-sized grid environments. The comparative study of traditional methods and evolutionary algorithms shows that the parallel micro evolutionary algorithm achieves a high problem solving efficacy, outperforming previous results already reported in the related literature, and also showing a good scalability behavior when facing high dimension problem instances.     

Representation of piecewise continuous algebraic surfaces in terms of B-splines

A method for representing shape using portions of algebraic surfaces bounded by rectangular boxes defined in terms of triple product Bernstein polynomials is described and some of its properties are outlined. The method is extended to handle piecewise continuous algebraic surfaces within rectangular boxes defined in terms of triple products of B-spline basis functions. Next, two techniques for sculptured shape creation are studied. The first is based on geometric manipulation of existing primitives and the second on approximation/interpolation of lower dimensional entities using least-squares techniques based on singular value decomposition. In addition, several interrogation techniques, such as contouring, ray tracing and curvature evaluation, used in the design and analysis of piecewise continuous algebraic surfaces are discussed.     

Defining, contouring, and visualizing scalar functions on point-sampled surfaces

This paper addresses the definition, contouring, and visualization of scalar functions on unorganized point sets, which are sampled from a surface in 3D space; the proposed framework builds on moving least-squares techniques and implicit modeling. Given a scalar function f:P→R, defined on a point set P, the idea behind our approach is to exploit the local connectivity structure of the k-nearest neighbor graph of P and mimic the contouring of scalar functions defined on triangle meshes. Moving least-squares and implicit modeling techniques are used to extend f from P to the surface M underlying P. To this end, we compute an analytical approximation of f that allows us to provide an exact differential analysis of , draw its iso-contours, visualize its behavior on and around M, and approximate its critical points. We also compare moving least-squares and implicit techniques for the definition of the scalar function underlying f and discuss their numerical stability and approximation accuracy. Finally, the proposed framework is a starting point to extend those processing techniques that build on the analysis of scalar functions on 2-manifold surfaces to point sets.     

A parallel sparse grid construction algorithm based on the shared memory architecture and its application to flash calculations

The study of sparse grids has been done in a lot of works, but none of them pay special attention on the concept of “layer”, not to mention the further research on this new concept. This work presents the layer concept at first, and then based on it a new parallel sparse grid construction algorithm is proposed, which fills the niche that few works design such kind of algorithm on shared memory architecture. With the superiorities of the layer concept, the sparse grids can be constructed in a “layer by layer” manner on a much easier structure which is the simplified tree. Different from the classical tree structures used in the former sparse grid construction algorithm, the simplified tree reduces the number of sparse grid points further and at the same time avoids many unnecessary usages of pointers. Moreover, the correctness of the algorithm is guaranteed by the two correctness criterions, and its main advantages include that it can achieve load balance among the threads easily and that it can be applied in the function domains of any kinds of configurations, which is demonstrated by theory. After that, the algorithm is tested on flash calculations which are an important application from reservoir simulations. According to the characteristics of the issue, a modified version of the algorithm is given. By comparing the tested results with those of the former algorithm, it is found that a great quantity of construction time is saved by this algorithm.     

A genetic method for designing TSK models based on objective weighting: application to classification problems.

This paper proposes a genetic-based algorithm for generating simple and well-defined Takagi-Sugeno-Kang (TSK) models. The method handles several attributes simultaneously, such as the input partition, feature selection and estimation of the consequent parameters. The model building process comprises three stages. In stage one, structure learning is formulated as an objective weighting optimization problem. Apart from the mean square error (MSE) and the number of rules, three additional criteria are introduced in the fitness function for measuring the quality of the partitions. Optimization of these measures leads to models with representative rules, small overlapping and efficient data cover. To obtain models with good local interpretation, the consequent parameters are determined using a local MSE function while the overall model is evaluated on the basis of a global MSE function. The initial model is simplified at stage two using a rule base simplification routine. Similar fuzzy sets are merged and the “don’t care” premises are recognized. Finally, the simplified models are fine-tuned at stage three to improve the model performance. The suggested method is used to generate TSK models with crisp and polynomial consequents for two benchmark classification problems, the iris and the wine data. Simulation results reveal the effectiveness of our method. The resulting models exhibit simple structure, interpretability and superior recognition rates compared to other methods of the literature.     

MARS: A tool-based modeling,animation, and parallel rendering system

This paper describes a system for modeling, animating, previewing and rendering articulated objects. The system has a modeler of objects that consists of joints and segments. The animator interactively positions the articulated object in its stick, control vertex, or rectangular prism representation and previews the motion in real time. Then the data representing the motion and the models is sent to a multicomputer [iPSC/2 Hypercube (Intel)]. The frames are rendered in parallel, exploiting the coherence between successive frames, thus cutting down the rendering time significantly. Our main aim is to make a detailed study on rendering of a sequence of 3D scenes. The results show that due to an inherent correlation between the 3D scenes, an efficient rendering can be achieved.     

基于视觉的目标检测与跟踪综述

基于视觉的目标检测与跟踪是图像处理、计算机视觉、模式识别等众多学科的交叉研究课题,在视频监控、虚拟现实、人机交互、自主导航等领域,具有重要的理论研究意义和实际应用价值.本文对目标检测与跟踪的发展历史、研究现状以及典型方法给出了较为全面的梳理和总结.首先,根据所处理的数据对象的不同,将目标检测分为基于背景建模和基于前景建模的方法,并分别对背景建模与特征表达方法进行了归纳总结.其次,根据跟踪过程有无目标检测的参与,将跟踪方法分为生成式与判别式,对基于统计的表观建模方法进行了归纳总结.然后,对典型算法的优缺点进行了梳理与分析,并给出了其在标准数据集上的性能对比.最后,总结了该领域待解决的难点问题,对其未来的发展趋势进行了展望.     

A portable wireless body sensor data logger and its application in video capsule endoscopy

Due to the advancement of low power miniature electronic devices, there is growing interest of physiological data sensing and recording using wireless body sensor networks. The paper presents the design of a portable physiological data logger that includes rechargeable battery, wireless radio frequency and Bluetooth connectivity, and graphical display with touch screen capability. The target application is video capsule endoscopy. Image data are logged in micro SD cards which can be easily transferred to PC or Smartphone using SD card reader, USB interface or Bluetooth wireless link. The hardware design is general and can be used in various medical or industrial applications by changing only the firmware of the microcontroller. The design is prototyped in 109 × 107 × 20 mm printed circuit board (PCB). Tests with animal tissues have been conducted to demonstrate the performance advantages of the data logger. A demonstration of wireless heart pulse monitoring and data logging is also presented.     

自定义特征的图形系统在管网建模上的应用

用自定义特征的方法,介绍了管网建模系统的设计与实现.用基本图元生成特征矢量图标,给出矢量图标生成的过程和属性设置.在管网建模中,介绍了用矢量图标生成管网模型的建模步骤和实例.该系统与工程实际相结合,能够有效地提高管网建模的效率,具有管网建模的通用性和扩展性.整个管网建模系统采用面向对象的程序设计思想进行设计,扩展后可以作为相似行业的管网建模系统使用.     

A multigrid algorithm for parallel computers: CPMG

In this article, we present a multigrid algorithm for parallel computers, the chopped parallel multigrid (CPMG) algorithm. The CPMG algorithm improves the processor utilization by reducing the work load on coarse grids without affecting the convergence rate of the algorithm. This is in contrast to earlier approaches (Gannon and van Rosendale, 1986; Frederickson and McBryan, 1989), where unutilized processors are used to improve the convergence rate. The CPMG algorithm reduces the coarse grid work bychopping the alternate cycles of multigrid. Using analytical results and simulations on sequential machines we show that the CPMG can achieve almost the same convergence rate as standard MG for many cases. Analytically we show that the advantage gained by CPMG over standard MG on a mesh connected massively parallel machine is 33% in hardware utilization, 50% in communication overheads and 38% in overall execution time. We have also evaluated the performance of CPMG on an actual massively parallel machine, the DAP-510. The advantage gained by CPMG over standard MG is 35% in overall execution time. Moreover, the CPMG can be integrated with other parallel multigrid algorithms, such as the PSMG algorithm (Frederickson and McBryan, 1989) and Decker's algorithm (Decker, 1990).     

紧致遗传算法及其在武器目标分配中的应用

介绍了紧致遗传算法的基本原理,并对其进行了改进,通过仿真验证了算法的有效性。针对武器-目标分配（WTA）问题,提出利用紧致遗传算（CGA）法求解该问题,通过验证并与其它方法比较,证明该方法可行。由于紧致遗传算法的编码简单,运行时占用的内存较小,所得到的结果较为稳定并且运行速度较快。     

并行绘制系统中基于网络处理单元的图像合成及显示

随着绘制任务复杂度和绘制数据规模不断增长,使用PC集群进行分布式并行绘制是一个常用的解决方案。Sort-last分布式并行绘制方法具有好的扩展性和负载平衡,但由于图像合成瓶颈的限制,绘制速度不能满足实时需求。本文提出了一个使用网络处理单元（NPU）来进行快速硬件图像合成的方法,开发了一个sort-last并行绘制系统NPUPR。实验表明,针对4个绘制节点,基于NPU的硬件图像合成方法与direct send的合成算法相比,绘制速度有了4倍的提高。本文也给出通过增加网络处理单元来扩展系统支持更多绘制节点的方案,分析表明,系统图像合成性能不会随节点个数的增加而明显降低。     

On simultaneous straight-line grid embedding of a planar graph and its dual

Simultaneous representations of planar graphs and their duals normally require that the dual vertices to be placed inside their corresponding primal faces, and the edges of the dual graph to cross only their corresponding primal edges. Erten and Kobourov [C. Erten, S.G. Kobourov, Simultaneous embedding of a planar graph and its dual on the grid, Theory Computer Systems 38 (2005) 313-327] provided a linear time algorithm on simultaneous straight-line grid embedding of a 3-connected planar graph and its dual such that all the vertices are placed on grid points and each edge is drawn as one straight-line segment except for one which is drawn using two segments. Their drawing size is (2n−2)×(2n−2), where n is the total number of vertices in the graph and its dual. They raised an open question on whether there is a large class of planar graphs that allows this simultaneous straight-line grid embedding on a smaller grid. We answer this open question by giving a linear time simultaneous straight-line grid embedding algorithm for a 3-connected planar graph and its dual on a grid of size (n−1)×n.