Real-time homogenous translucent material editing

This paper presents a novel method for real-time homogenous translucent material editing under fixed illumination. We consider the complete analytic BSSRDF model proposed by Jensen et al. [ [JMLH01] ], including both multiple scattering and single scattering. Our method allows the user to adjust the analytic parameters of BSSRDF and provides high-quality, real-time rendering feedback. Inspired by recently developed Precomputed Radiance Transfer (PRT) techniques, we approximate both the multiple scattering diffuse reflectance function and the single scattering exponential attenuation function in the analytic model using basis functions, so that re-computing the outgoing radiance at each vertex as parameters change reduces to simple dot products. In addition, using a non-uniform piecewise polynomial basis, we are able to achieve smaller approximation error than using bases adopted in previous PRT-based works, such as spherical harmonics and wavelets. Using hardware acceleration, we demonstrate that our system generates images comparable to [ [JMLH01] ]at real-time frame-rates.     

An actor-critic algorithm for constrained Markov decision processes

An actor-critic type reinforcement learning algorithm is proposed and analyzed for constrained controlled Markov decision processes. The analysis uses multiscale stochastic approximation theory and the envelope theorem' of mathematical economics.     

Networks for sorting multitonic sequences

Lee and Batcher have designed networks that efficiently merge k separately provided sorted sequences of known lengths totalling n. We show that the design is still possible, and in fact easier to describe, if we do not make use of the lengths, or even the directions of monotonicity, of the individual sequences—the sequences can be provided in a single undelimited concatenation of length n. The depth of the simplest resulting network to sort sequences that are “k-tonic” and of length n is , generalizing Batcher's 1968 results for the extreme values of k (k=2 corresponding to merging, and k=n/2 corresponding to general sorting).The exposition is self-contained and can serve even as an introduction to sorting networks and Batcher's results.     

矢量图形智能判断技术的研究与应用

研究矢量图形识别是建立工程制图自动阅卷与计算机辅助教学系统的基础。由于组成二维矢量图形图元类型的多样化及图形整体位置状态的不确定性，增加了矢量图形的识别与判断难度。结合开发的《三视图智能解答》系统，研究其智能识别与判断技术。系统中引入三视图导航技术，解决了图形整体定位与识别问题。实现了对矢量图形图元素信息的分类和提取，能够对所提取的的信息与标准答案进行智能判断与评定。该方法已在AutoCAD2000环境下使用AutoLISP语言编程实现。     

A fast digital Radon transform—An efficient means for evaluating the Hough transform

A fast digital Radon transform based on recursively defined digital straight lines is described, which has the sequential complexity of N² log N additions for an N × N image. This transform can be used to evaluate the Hough transform to detect straight lines in a digital image. Whilst a parallel implementation of the Hough transform algorithm is difficult because of global memory access requirements, the fast digital Radon transform is vectorizable and therefore well suited for parallel computation. The structure of the fast algorithm is shown to be quite similar to the FFT algorithm for decimation in frequency. It is demonstrated that even for sequential computation the fast Radon transform is an attractive alternative to the classical Hough transform algorithm.     

On-Line File Caching

Abstract. Consider the following file caching problem: in response to a sequence of requests for files, where each file has a specified size and retrieval cost , maintain a cache of files of total size at most some specified k so as to minimize the total retrieval cost. Specifically, when a requested file is not in the cache, bring it into the cache and pay the retrieval cost, and remove other files from the cache so that the total size of files remaining in the cache is at most k . This problem generalizes previous paging and caching problems by allowing objects of arbitrary size and cost, both important attributes when caching files for world-wide-web browsers, servers, and proxies. We give a simple deterministic on-line algorithm that generalizes many well-known paging and weighted-caching strategies, including least-recently-used, first-in-first-out, flush-when-full, and the balance algorithm. On any request sequence, the total cost incurred by the algorithm is at most k/(k-h+1) times the minimum possible using a cache of size h ≤ k . For any algorithm satisfying the latter bound, we show it is also the case that for most choices of k , the retrieval cost is either insignificant or at most a constant (independent of k ) times the optimum. This helps explain why competitive ratios of many on-line paging algorithms have been typically observed to be constant in practice.     

A stability classification method and its application to pipelined solution of linear recurrences

A new method of classification for numerical stability of parallel algorithms is proposed based on the theoretical foundation of forward error analysis. It partitions the algorithms according to their asymptotic stability—a measure introduced to relate the limiting behavior of the stability to the size of the problem. Using this method, the stability aspect of the pipelined solution technique for first-order and second-order linear recurrences—the core of a tridiagonal linear equation solver—is studied. In particular, it shows that the pipelined solution method of the first-order linear recurrences has the same degree of stability as the commonly used sequential evaluation algorithms. The stability problems of sequential and pipelined solution methods of the second-order linear recurrences are also studied.     

Fast parallel Preconditioned Conjugate Gradient algorithms for robot manipulator dynamics simulation

In this paper fast parallel Preconditioned Conjugate Gradient (PCG) algorithms for robot manipulator forward dynamics, or dynamic simulation, problem are presented. By exploiting the inherent structure of the forward dynamics problem, suitable preconditioners are devised to accelerate the iterations. Also, based on the choice of preconditioners, a modified dynamic formulation is used to speedup both serial and parallel computation of each iteration. The implementation of the parallel algorithms on two interconnected processor arrays is discussed and their computation and communication complexities are analyzed. The simulation results for a Puma Arm are presented to illustrate the effectiveness of the proposed preconditioners. With a faster convergence due to preconditioning and a faster computation of iterations due to parallelization, the developed parallel PCG algorithms represent the fastest alternative for parallel computation of the problem withO(n) processors.     

Covering a string

We consider the problem of finding the repetitive structures of a given stringx. The periodu of the stringx grasps the repetitiveness ofx, sincex is a prefix of a string constructed by concatenations ofu. We generalize the concept of repetitiveness as follows: A stringw covers a stringx if there is a superstring ofx which is constructed by concatenations and superpositions ofw. A substringw ofx is called aseed ofx ifw coversx. We present anO(n logn)-time algorithm for finding all the seeds of a given string of lengthn.Partially supported by SERC Grants GR/F 00898 and GR/J 17844, NATO Grant CRG 900293, ESPRIT BRA Grant 7131 for ALCOMII, and MRC Grant G 9115730.Partially supported by MRC Grant G 9115730 and S.N.U. Posco Research Fund 94-15-1112.     

物联网技术在高校校园中的应用

随着物联网技术的不断发展,物联网在高校的应用也越来越广泛。介绍物联网的概念,提出校园物联网的概念,对校园物联网的工作原理进行介绍,就物联网在高校校园中的应用做深入的探讨,在高校智能教学、教育管理和平安校园等方面做详细的分析。