Fast Wavelet Radiosity Method

Wavelet analysis has been found [1] to be very useful for functional representation and accurate global solution of radiosity. In radiosity we deal with functions in 2D and 4D spaces. Under such conditions, the biggest bottleneck in applying this wavelet analysis seems to be the large number of multidimensional inner products. In this paper, we propose (i) the use of interpolating wavelets for fast inner product computation and consequently for faster wavelet radiosity solution (ii) the use of hierarchical decomposition technique for determining the smoothness of the radiosity function for optimal adaptive subdivision.     

Algorithms for Handling the Fill Area Primitive of GKS

The fill area primitive of GKS (Graphical Kernel System)¹ is one of the more powerful features which differentiates it from earlier device independent graphics software and systems. Its specification is extremely general in the form of a closed boundary, possibly self-intersecting, and whose interior can be filled in a variety of styles. However a complete implementation of this primitive is very complex. It is difficult to find a single graphics workstation incorporating this primitive in hardware or firmware. Most GKS implementations will have to include software for simulating the appearance of this primitive on the commonly available displays and hard-copy graphics devices. Correct and efficient algorithms are necessary for developing this software. Because of the generality many of the existing algorithms are not directly applicable. In this paper we describe:
1. a new algorithm for clipping a fill area polygon, using what we have named as the Bridge Technique.
2. implementation of a plane sweep algorithm, by Nievergelt and Preparata,² for solid filling and hatching, particularly applicable to vector devices.
3. extension of the plane sweep algorithm for filling with any given pattern on raster as well as vector devices.
The algorithms have been designed to work for all special cases as well. In fact they have been implemented having in mind the fill area set primitive of GKS-3D extension.³ All these algorithms have been very successfully implemented in a commercially available GKS implementation, namely indoGKS.     

ON COMPUTING THE MINIMAL LABELS IN TIME POINT ALGEBRA NETWORKS

We analyze the problem of computing the minimal labels for a network of temporal relations in point algebra. Van Beek proposes an algorithm for accomplishing this task, which takes O (max( n ³, n² m) ) time (for n points and m ≠ -relations). We show that the proof of the correctness of this algorithm given by van Beek and Cohen is faulty, and we provide a new proof showing that the algorithm is indeed correct.     

An Algorithm for Minimal Insertion in a Type Lattice

The problem of inserting a new element x into a lattice of types L is addressed in the paper. As the poset L + x obtained by the direct insertion of x in L is not necessarily a lattice, some set of auxiliary elements should be added to restore the lattice properties. An approach toward the lattice insertion is presented which allows the set of auxiliary elements to be kept minimal. The key idea is to build the final lattice L ⁺ as isomorphic to the Dedekind–McNeille completion of the order L + x . Our strategy is based on a global definition of the set of auxiliary elements and their locations in L ⁺. Each auxiliary is related to a specific element of L , an odd , which represents GLB (LUB) of some elements in L superior (inferior) to x . An appropriate computation scheme for the auxiliary types is given preserving the subtyping in the lattice L ⁺. The insertion strategy presented is more general than the existing ones, since it deals with general kinds of lattices and makes no hypothesis on the location of x in L . An algorithm computing L ⁺ from L and x of time complexity O (| L || J ( L )| ω ^3( L )) is provided.     

Sensitivity analysis on the all pairs q-route flows in a network

Given an undirected edge-weighted network in which one edge capacity is allowed to vary, we propose in this paper a polynomial algorithm that needs only two 2-cut-trees computations to provide the all pairs maximum 2-route flow values. Moreover, we provide an extension to the case where k edge capacities may vary, and show that 2 ^k 2-cut-trees computations are necessary in order to determine the all pairs maximum 2-route-flow values. This makes our algorithm polynomial whenever     .     

Space-Time Hierarchical Radiosity with Clustering and Higher-Order Wavelets

We address in this paper the issue of computing diffuse global illumination solutions for animation sequences. The principal difficulties lie in the computational complexity of global illumination, emphasized by the movement of objects and the large number of frames to compute, as well as the potential for creating temporal discontinuities in the illumination, a particularly noticeable artifact. We demonstrate how space‐time hierarchical radiosity, i.e. the application to the time dimension of a hierarchical decomposition algorithm, can be effectively used to obtain smooth animations: first by proposing the integration of spatial clustering in a space‐time hierarchy; second, by using a higher‐order wavelet basis adapted for the temporal dimension. The resulting algorithm is capable of creating time‐dependent radiosity solutions efficiently.     

Visualization of Isosurfaces with Parametric Cubes

To render images from volume datasets, an interpolation method also called reconstruction is needed. The level of details of the resultant image closely depends on the filter used for reconstruction. We propose here a new filter producing C ¹ continue surfaces. The provided image quality is better than current high-quality algorithms, like splatting or trilinear raycasting, where tiny details are often eliminated. In contrast with other studied high quality filters that are practically unusable, our algorithm has been implemented interactively on a modest platform thanks to an efficient implementation using parametric cubes. We also demonstrate the interest of a min-max octree in the visualization of isosurfaces interactively thresholded.     

Lifting Scheme及其在小波图象编码中的应用

Lifting Scheme是构造第二代小波的关键技术。相对于第一代小波而言,Lifting Scheme是一种比Mallat算法更快、更简单和更容易操作的算法,也是JPEG2000推荐的算法,为了将其应用到小波图象编码中,提出了一种对Lifting Scheme作适当改进以用于小波图象编码的方法。该方法就是先用Lifting Scheme来实现D9/7双正交小波变换,然后再用这种技术实现的D9/7双正交小波变换来进行图象压缩编码。在将Lifting Scheme算法用于小波图象编码的过程中,对该算法做了必要的简化,以便保证每个提升(lifting）环节都是FIR滤波。同时,根据能量守恒的原则,重新调整了尺度因子。实验结果表明,这种经过改进的Lifting Scheme取得了比Mallat算法更好的图象编码效果。     

Efficient Hierarchical Refinement and Clustering for Radiosity in Complex Environments

Generating accurate radiosity solutions of very complex environments is a time-consuming problem. We present a rapid hierarchical algorithm that enables such solutions to be computed quickly and efficiently. Firstly, a new technique for bounding the error in the transfer of radiosity between surfaces is discussed, incorporating bounds on form factors, visibility, irradiance, and reflectance over textured surfaces. This technique is then applied to the problem of bounding radiosity transfer between clusters of surfaces, leading to a fast, practical clustering algorithm that builds on the previous work of Sillion¹. Volumes are used to represent clusters of small surfaces, but unlike previous algorithms, the orientations of surfaces inside each cluster are accounted for in both the error bound and radiosity transfer. This enables an accurate solution to be generated very efficiently, and results are presented demonstrating the performance of the algorithm on a variety of complex models, one containing almost a quarter of a million initial surfaces.     

Efficient Glossy Global Illumination with Interactive Viewing

The ability to perform interactive walkthroughs of global illumination solutions including glossy effects is a challenging open problem. In this paper we overcome certain limitations of previous approaches. We first introduce a novel, memory- and compute-efficient representation of incoming illumination, in the context of a hierarchical radiance clustering algorithm. We then represent outgoing radiance with an adaptive hierarchical basis, in a manner suitable for interactive display. Using appropriate refinement and display strategies, we achieve walkthroughs of glossy solutions at interactive rates for non-trivial scenes. In addition, our implementation has been developed to be portable and easily adaptable as an extension to existing, diffuse-only, hierarchical radiosity systems. We present results of the implementation of glossy global illumination in two independent global illumination systems.     

PC-based Real-time Texture Painting on Real World Objects

The problem of texture mapping on real world objects has attracted attention^11,8 recently. A work by Lensch et al. ⁹ addressed the problem of locating a camera position in the celestial sphere and then mapping the acquired pictures on a real world object. The entire process took a half hour to one hour to map 10 to 15 pictures. In this paper, we propose a new innovative algorithm to speed up the texture mapping or painting process in real-time. We built a PC-based system using a commonly available video card with a geometry engine. Mapping of a picture required about 20 seconds. It is successful in giving an illusion to the operator to paint a colorless real world object with a color texture brush.     

Ray Tracing Triangular Bézier Patches

We present a new approach to finding ray–patch intersections with triangular Bernstein–Bézier patches of arbitrary degree. This paper extends and complements on the short presentation¹⁷ . Unlike a previous approach which was based on a combination of hierarchical subdivision and a Newton–like iteration scheme²¹ , this work adapts the concept of Bézier clipping to the triangular domain.
The problem of reporting wrong intersections, inherent to the original Bézier clipping algorithm¹⁴ , is inves-tigated and opposed to the triangular case. It turns out that reporting wrong hits is very improbable, even close to impossible, in the triangular set–up. A combination of Bézier clipping and a simple hierarchy of nested bounding volumes offers a reliable and accurate solution to the problem of ray tracing triangular Bézier patches.     

Tighter error bounds and weighted error metrics for hierarchical radiosity

In this paper we first derive a tighter error bound on form factors as a subdivision criterion for the hierarchical radiosity algorithm. Such an error bound can reduce more unnecessary links and improve the performance of the hierarchical radiosity algorithm to meet a user-specified error tolerance. We then propose a weighted error metric in form factor computation such that more effort is automatically applied to shadow boundaries. Evaluating form factors along shadow boundaries with a higher degree of precision should enhance the quality of human perception. Using the proposed tighter error bound on the weighted error metric, we not only improve the performance but also increase the accuracy of the hierarchical radiosity algorithm. © 1998 John Wiley & Sons, Ltd.     

Supporting the programmer of a rule based language

Abstract: In this paper we take up the plight of the programmer of a rule based language. Our focus is on the type of development environment that is most supportive of such programmers. Our view will be that programming is programming, whether it be with a rule based, functional or imperative language. While it is true that rule based languages have strong links to the Expert Systems field, our discussion in this paper has less to do with 'expert systems' per se ¹ , and more to do with the view of rule based languages as yet another computational paradigm, often included under the same roof with non-rule-based languages. Just as programming environment research has progressed for non-rule-based languages, we would like to build more powerful environments in the rule based world as well. We report here on an attempt to build such an environment. ²     

An Interpolant with Tension Defined over Triangles

A C ¹ interpolation scheme is described, which is defined over triangular grids. The interpolant is computed on the basis of curves with tension, which permit local control over the shape of the resulting surface.     

A Median Cut Algorithm for Efficient Sampling of Radiosity Functions

This paper presents an efficient method for sampling the illumination functions in higher order radiosity algorithms. In such algorithms, the illumination function is not assumed to be constant across each patch, but it is approximated by a function which is at least C¹ continuous. Our median cut sampling algorithm is inspired by the observation that many form factors are computed at higher precision than is necessary. While a high sampling rate is necessary in regions of high illumination, dark areas can be sampled at a much lower rate to compute the received radiosity within a given precision. We adaptively subdivide the emitter into regions of approximately equal influence on the result. Form factors are evaluated by the disk approximation and a ray tracing based test for occlusion detection. The implementation of a higher order radiosity system using B-splines as radiosity function is described. The median cut algorithm can also be used for radiosity algorithms based on the constant radiosity assumption.     

SOLVING NINE MEN'S MORRIS

The game of Nine Men's Morris is a draw. We obtained this result using a combination of endgame databases (10¹⁰ states) and search. Our improved algorithm for computing endgame databases allowed the game to be solved on a personal computer. Other games have been solved using knowledge-based methods to dramatically prune the search tree. Nine Men's Morris does not seem to profit from such methods, making it the first nontrivial game solved in which almost the entire state space has to be considered.     

Planning in polynomial time: the SAS-PUBS class

This article describes a polynomial-time, O ( n³ ), planning algorithm for a limited class of planning problems. Compared to previous work on complexity of algorithms for knowledge-based or logic-based planning, our algorithm achieves computational tractability, but at the expense of only applying to a significantly more limited class of problems. Our algorithm is proven correct, and it always returns a parallel minimal plan if there is a plan at all.
Cet article décrit un algorithme de planification de temps polynomial O ( n ³) pour une classe restreinte de problemes de planification. Contrairement aux travaux précédents sur la complexité des algorithmes pour la planification basée sur la logique ou les connaissances, l' algorithme dont il est question dans cet article permet d' obtenir la tractabilityé computationnelle; cependant, il ne peut ětre appliqué qu'à une catégorie beaucoup plus restreinte de problèmes. Cet algorithme s'est done révélé correct et il génère toujours un plan minimal en parallèle lorsqu'il y en a un.     

The Applications of Wavelets in Hierarchical Representations and Smoothing of Curves and Surfaces

ＴｈｅＡｐｐｌｉｃａｔｉｏｎｓｏｆＷａｖｅｌｅｔｓｉｎＨｉｅｒａｒｃｈｉｃａｌＲｅｐｒｅｓｅｎｔａｔｉｏｎｓａｎｄＳｍｏｏｔｈｉｎｇｏｆＣｕｒｖｅｓａｎｄＳｕｒｆａｃｅｓ①ＳｕｎＹａｎｋｕｉＺｈｕＸｉｎｘｉｏｎｇＭａＬｉｎｇＢｅｉｊｉｎｇＵｎｖｉｅｒ...     

基于第二代小波变换的图像融合方法及性能评价

提出了一种基于小波提升方案的图像融合新算法. 与传统基于卷积的小波变换融合方法相比, 新算法具有计算简单、融合速度快、所需内存少以及有利于算法的在线快速实现等优点. 此外, 还提出了一种基于区域特征选择的新的融合策略, 针对不同类型的多源图像进行了融合仿真实验, 并采用主观视觉判断与客观评价准则相结合的方式, 对不同变换方式、不同融合规则以及不同分解层数对融合效果的影响进行了比较分析. 实验结果表明本文提出的融合算法和融合策略具有优越的融合性能, 并取得了令人满意的融合效果.