Our goal in this article is to propose a fast and easy to implement BRDF modeling method that provides both accurate and compact representations for all types of BRDF, i.e., isotropic or anisotropic. To achieve this objective, we use a Bayesian regression method with a Gaussian process prior which allows obtaining compact BRDF representations in a purely analytical way. For this purpose, we use a generalzed distance covariance kernel which is much better suited to BRDF features than the usual Gaussian kernel. To speed up the processing, we adapt this method to the specificities of BRDFs through an appropriate input data structure and distribution of observations so as to drastically reduce the problem dimensionality through an efficient factorization method. In this way, all calculations at both fitting and rendering steps are reduced to basic matrix products and the computation of a BRDF representation with our modeling method takes only a few seconds. Furthermore, rather than using a systematic approach as in state-of-the-art methods, the size and complexity of the BRDF representation can be adapted to the application requirements as regards the fitting accuracy and rendering constraints. Besides, our BRDF representation can be easily converted to spherical harmonics expansions, which allows easier integration in usual rendering algorithms. We also propose importance sampling methods derived from our BRDF modeling method that leads to fast and easy implementations. Experimental applications of our method to various types of isotropic and anisotropic BRDFs show that state-of-the-art methods can be outperformed in most cases by using a small set of observations for the regression.

Gaze behavior of virtual characters in video games and virtual reality experiences is a key factor of realism and immersion. Indeed, gaze plays many roles when interacting with the environment; not only does it indicate what characters are looking at, but it also plays an important role in verbal and non-verbal behaviors and in making virtual characters alive. Automated computing of gaze behaviors is however a challenging problem, and to date none of the existing methods are capable of producing close-to-real results in an interactive context. We therefore propose a novel method that leverages recent advances in several distinct areas related to visual saliency, attention mechanisms, saccadic behavior modelling, and head-gaze animation techniques. Our approach articulates these advances to converge on a multi-map saliency-driven model which offers real-time realistic gaze behaviors for non-conversational characters, together with additional user-control over customizable features to compose a wide variety of results. We first evaluate the benefits of our approach through an objective evaluation that confronts our gaze simulation with ground truth data using an eye-tracking dataset specifically acquired for this purpose. We then rely on subjective evaluation to measure the level of realism of gaze animations generated by our method, in comparison with gaze animations captured from real actors. Our results show that our method generates gaze behaviors that cannot be distinguished from captured gaze animations. Overall, we believe that these results will open the way for more natural and intuitive design of realistic and coherent gaze animations for real-time applications.

Abstract Efficient approximation of incident radiance functions from a set of samples is still an open problem in physically based rendering. Indeed, most of the computing power required to synthesize a photo‐realistic image is devoted to collecting samples of the incident radiance function, which are necessary to provide an estimate of the rendering equation solution. Due to the large number of samples required to reach a high‐quality estimate, this process is usually tedious and can take up to several days. In this paper, we focus on the problem of approximation of incident radiance functions on the sphere. To this end, we resort to a Gaussian Process (GP), a highly flexible function modelling tool, which has received little attention in rendering. We make an extensive analysis of the application of GPs to incident radiance functions, addressing crucial issues such as robust hyperparameter learning, or selecting the covariance function which better suits incident radiance functions. Our analysis is both theoretical and experimental. Furthermore, it provides a seamless connection between the original spherical domain and the spectral domain, on which we build to derive a method for fast computation and rotation of spherical harmonics coefficients.

Abstract Example‐based colour transfer between images, which has raised a lot of interest in the past decades, consists of transferring the colour of an image to another one. Many methods based on colour distributions have been proposed, and more recently, the efficiency of neural networks has been demonstrated again for colour transfer problems. In this paper, we propose a new pipeline with methods adapted from the image domain to automatically transfer the colour from a target point cloud to an input point cloud. These colour transfer methods are based on colour distributions and account for the geometry of the point clouds to produce a coherent result. The proposed methods rely on simple statistical analysis, are effective, and succeed in transferring the colour style from one point cloud to another. The qualitative results of the colour transfers are evaluated and compared with existing methods.

Spherical Fibonacci grids (SFG) yield extremely uniform point set distributions on the sphere. This feature makes SFGs particularly well-suited to a wide range of computer graphics applications, from numerical integration, to vector quantization, among others. However, the application of SFGs to problems in which further refinement of an initial point set is required is currently not possible. This is because there is currently no solution to the problem of adding new points to an existing SFG while maintaining the point set properties. In this work, we fill this gap by proposing the extensible spherical Fibonacci grids (E-SFG). We start by carrying out a formal analysis of SFGs to identify the properties which make these point sets exhibit a nearly-optimal uniform spherical distribution. Then, we propose an algorithm (E-SFG) to extend the original point set while preserving these properties. Finally, we compare the E-SFG with a other extensible spherical point sets. Our results show that the E-SFG outperforms spherical point sets based on a low discrepancy sequence both in terms of spherical cap discrepancy and in terms of root mean squared error for evaluating the rendering integral.

We propose a theoretical framework, based on the theory of Sobolev spaces, that allows for a comprehensive analysis of quadrature rules for integration over the sphere. We apply this framework to the case of shading integrals in order to predict and analyze the performances of quadrature methods. We show that the spectral distribution of the quadrature error depends not only on the samples set size, distribution and weights, but also on the BRDF and the integrand smoothness. The proposed spectral analysis of quadrature error allows for a better understanding of how the above different factors interact. We also extend our analysis to the case of Fourier truncation-based techniques applied to the shading integral, so as to find the smallest spherical/hemispherical harmonics degree L (truncation) that entails a targeted integration error. This application is very beneficial to global illumination methods such as Precomputed Radiance Transfer and Radiance Caching. Finally, our proposed framework is the first to allow a direct theoretical comparison between quadrature- and truncation-based methods applied to the shading integral. This enables, for example, to determine the spherical harmonics degree L which corresponds to a quadrature-based integration with N samples. Our theoretical findings are validated by a set of rendering experiments.

Abstract This paper proposes optimal quadrature rules over the hemisphere for the shading integral. We leverage recent work regarding the theory of quadrature rules over the sphere in order to derive a new theoretical framework for the general case of hemispherical quadrature error analysis. We then apply our framework to the case of the shading integral. We show that our quadrature error theory can be used to derive optimal sample weights (OSW) which account for both the features of the sampling pattern and the bidirectional reflectance distribution function (BRDF). Our method significantly outperforms familiar Quasi Monte Carlo (QMC) and stochastic Monte Carlo techniques. Our results show that the OSW are very effective in compensating for possible irregularities in the sample distribution. This allows, for example, to significantly exceed the regular convergence rate of stochastic Monte Carlo while keeping the exact same sample sets. Another important benefit of our method is that OSW can be applied whatever the sampling points distribution: the sample distribution need not follow a probability density function, which makes our technique much more flexible than QMC or stochastic Monte Carlo solutions. In particular, our theoretical framework allows to easily combine point sets derived from different sampling strategies (e.g. targeted to diffuse and glossy BRDF). In this context, our rendering results show that our approach overcomes MIS (Multiple Importance Sampling) techniques.

Recent progress in digital photography and storage availability has drastically changed our approach to photo creation. While in the era of film cameras, careful forethought would usually precede the capture of a photo; nowadays, a large number of pictures can be taken with little effort. One of the consequences is the creation of numerous photos depicting the same moment in slightly different ways, which makes the process of organizing photos laborious for the photographer. Nevertheless, photo collection organization is important both for exploring photo albums and for simplifying the ultimate task of selecting the best photos. In this work, we conduct a user study to explore how users tend to organize or cluster similar photos in albums, to what extent different users agree in their clustering decisions, and to investigate how the clustering-defined photo context affects the subsequent photo-selection process. We also propose an automatic hierarchical clustering solution for modeling user clustering decisions. To demonstrate the usefulness of our approach, we apply it to the task of automatic photo evaluation within photo albums and propose a clustering-based context adaptation.

The selection of the best photos in personal albums is a task that is often faced by photographers. This task can become laborious when the photo collection is large and it contains multiple similar photos. Recent advances on image aesthetics and photo importance evaluation has led to the creation of different metrics for automatically assessing a given image. However, these metrics are intended for the independent assessment of an image, without considering the possible context implicitly present within photo albums. In this work, we perform a user study for assessing how users select photos when provided with a complete photo album---a task that better reflects how users may review their personal photos and collections. Using the data provided by our study, we evaluate how existing state-of-the-art photo assessment methods perform relative to user selection, focusing in particular on deep learning based approaches. Finally, we explore a recent framework for adapting independent image scores to collections and evaluate in which scenarios such an adaptation can prove beneficial.

Multivariate generalized Gaussian distributions (MGGDs) have aroused a great interest in the image processing community thanks to their ability to describe accurately various image features, such as image gradient fields. However, so far their applicability has been limited by the lack of a transformation between two of these parametric distributions. In this paper, we propose a novel transformation between MGGDs, consisting of an optimal transportation of the second-order statistics and a stochastic-based shape parameter transformation. We employ the proposed transformation between MGGDs for a color transfer and a gradient transfer between images. We also propose a new simultaneous transfer of color and gradient, which we apply for image color correction.

In this paper, we propose a perceptual model for evaluating results from color transfer methods. We conduct a user study, which provides a set of subjective scores for triplets of input, target and result images. Then, for each triplet, we compute a number of image features, which objectively characterize a color transfer. To describe the relationship between these features and the subjective scores, we build a regression model with random forests. An analysis and a cross-validation show that the predictions of our model are highly accurate.

The human visual system is sensitive to relative differences in luminance, but light transport simulation algorithms based on Metropolis sampling often result in a highly nonuniform relative error distribution over the rendered image. Although this issue has previously been addressed in the context of the Metropolis light transport algorithm, our work focuses on Metropolis photon tracing. We present a new target function (TF) for Metropolis photon tracing that ensures good stratification of photons leading to pixel estimates with equalized relative error. We develop a hierarchical scheme for progressive construction of the TF from paths sampled during rendering. In addition to the approach taken in previous work, where the TF is defined in the image plane, ours can be associated with compact spatial regions. This allows us to take advantage of illumination coherence to more robustly estimate the TF while adapting to geometry discontinuities. To sample from this TF, we design a new replica exchange Metropolis scheme. We apply our algorithm in progressive photon mapping and show that it often outperforms alternative approaches in terms of image quality by a large margin.

Abstract Automatically computing a cinematographic consistent sequence of shots over a set of actions occurring in a 3D world is a complex task which requires not only the computation of appropriate shots (viewpoints) and appropriate transitions between shots (cuts), but the ability to encode and reproduce elements of cinematographic style. Models proposed in the literature, generally based on finite state machine or idiom‐based representations, provide limited functionalities to build sequences of shots. These approaches are not designed in mind to easily learn elements of cinematographic style, nor do they allow to perform significant variations in style over the same sequence of actions. In this paper, we propose a model for automated cinematography that can compute significant variations in terms of cinematographic style, with the ability to control the duration of shots and the possibility to add specific constraints to the desired sequence. The model is parametrized in a way that facilitates the application of learning techniques. By using a Hidden Markov Model representation of the editing process, we demonstrate the possibility of easily reproducing elements of style extracted from real movies. Results comparing our model with state‐of‐the‐art first‐order Markovian representations illustrate these features, and robustness of the learning technique is demonstrated through cross‐validation.

Tone Mapping Operators (TMOs) transform High Dynamic Range (HDR) contents to address Low Dynamic Range (LDR) displays. However, before reaching the end-user, these contents are usually compressed using a codec (coder-decoder) for broadcasting or storage purposes. Achieving the best trade-off between rendering and compression efficiency is of prime importance. Any TMO includes a rounding quantization to convert floating point values to integer ones. In this work, we propose to modify this quantization to increase the compression efficiency of the tone mapped content. By using a motion compensation, our technique preserves the rendering intent of the TMO while maximizing the correlations between successive frames. Experimental results show that we can save up to 12% of the total bit-rate as well as an average bit-rate reduction of 8.5% for all the test sequences. We show that our technique can be applied to other applications such as denoising.

Abstract Quasi‐Monte Carlo (QMC) methods exhibit a faster convergence rate than that of classic Monte Carlo methods. This feature has made QMC prevalent in image synthesis, where it is frequently used for approximating the value of spherical integrals (e.g. illumination integral). The common approach for generating QMC sampling patterns for spherical integration is to resort to unit square low‐discrepancy sequences and map them to the hemisphere. However such an approach is suboptimal as these sequences do not account for the spherical topology and their discrepancy properties on the unit square are impaired by the spherical projection. In this paper we present a strategy for producing high‐quality QMC sampling patterns for spherical integration by resorting to spherical Fibonacci point sets. We show that these patterns, when applied to illumination integrals, are very simple to generate and consistently outperform existing approaches, both in terms of root mean square error (RMSE) and image quality. Furthermore, only a single pattern is required to produce an image, thanks to a scrambling scheme performed directly in the spherical domain.

The Monte Carlo method has proved to be very powerful to cope with global illumination problems but it remains costly in terms of sampling operations. In various applications, previous work has shown that Bayesian Monte Carlo can significantly outperform importance sampling Monte Carlo thanks to a more effective use of the prior knowledge and of the information brought by the samples set. These good results have been confirmed in the context of global illumination but strictly limited to the perfect diffuse case. Our main goal in this paper is to propose a more general Bayesian Monte Carlo solution that allows dealing with nondiffuse BRDFs thanks to a spherical Gaussian-based framework. We also propose a fast hyperparameters determination method that avoids learning the hyperparameters for each BRDF. These contributions represent two major steps toward generalizing Bayesian Monte Carlo for global illumination rendering. We show that we achieve substantial quality improvements over importance sampling at comparable computational cost.

Abstract Backward polygon beam tracing methods, that is beam tracing from the light source (L), are well suited to gather path coherency from specular (S) scattering surfaces. These methods are useful for modelling and efficiently simulating caustics on diffuse (D) surfaces; an effect due to LS+D transport paths. This paper generalizes backward polygon beam tracing to include a glossy (G) scattering surface. To this end the details of a beam tracing lumped model and implementation of L(S | G)D transport paths are presented. Although we limit the discussion to short transport paths, we show that backward beam tracing is faster than photon mapping by an order of magnitude for rendering caustics from glossy and specular surfaces.

Abstract Local Principal Component Analysis (LPCA) is one of the popular techniques for dimensionality reduction and data compression of large data sets encountered in computer graphics. The LPCA algorithm is a variant of k‐means clustering where the repetitive classification of high dimensional data points to their nearest cluster leads to long execution times. The focus of this paper is on improving the efficiency and accuracy of LPCA. We propose a novel SortCluster LPCA algorithm that significantly reduces the cost of the point‐cluster classification stage, achieving a speed‐up of up to 20. To improve the approximation accuracy, we investigate different initialization schemes for LPCA and find that the k‐means++ algorithm [ AV07 ] yields best results, however at a high computation cost. We show that similar ideas that lead to the efficiency of our SortCluster LPCA algorithm can be used to accelerate k‐means++. The resulting initialization algorithm is faster than purely random seeding while producing substantially more accurate data approximation.

Abstract Irradiance Caching is one of the most widely used algorithms to speed up global illumination. In this paper, we propose an algorithm based on the Irradiance Caching scheme that allows us (1) to adjust the density of cached records according to illumination changes and (2) to efficiently render the high‐frequency illumination changes. To achieve this, a new record footprint is presented. Although the original method uses records having circular footprints depending only on geometrical features, our record footprints have a more complex shape which accounts for both geometry and irradiance variations. Irradiance values are computed using a classical Monte Carlo ray tracing method that simplifies the determination of nearby objects and the pre‐computation of the shape of the influence zone of the current record. By gathering irradiance due to all the incident rays, illumination changes are evaluated to adjust the footprint’s records. As a consequence, the record footprints are smaller where illumination gradients are high. With this technique, the record density depends on the irradiance variations. Strong variations of irradiance (due to direct contributions for example) can be handled and evaluated accurately. Caching direct illumination is of high importance, especially in the case of scenes having many light sources with complex geometry as well as surfaces exposed to daylight. Recomputing direct illumination for the whole image can be very time‐consuming, especially for walkthrough animation rendering or for high‐resolution pictures. Storing such contributions in the irradiance cache seems to be an appropriate solution to accelerate the final rendering pass.

Abstract Most Monte Carlo rendering algorithms rely on importance sampling to reduce the variance of estimates. Importance sampling is efficient when the proposal sample distribution is well‐suited to the form of the integrand but fails otherwise. The main reason is that the sample location information is not exploited. All sample values are given the same importance regardless of their proximity to one another. Two samples falling in a similar location will have equal importance whereas they are likely to contain redundant information. The Bayesian approach we propose in this paper uses both the location and value of the data to infer an integral value based on a prior probabilistic model of the integrand. The Bayesian estimate depends only on the sample values and locations, and not how these samples have been chosen. We show how this theory can be applied to the final gathering problem and present results that clearly demonstrate the benefits of Bayesian Monte Carlo.

Abstract We present a new approach for accelerated global illumination computation in scenes with glossy surfaces. Our algorithm combines sparse illumination computation used in the radiance caching algorithm with BRDF importance sampling. To make this approach feasible, we extend the idea of lazy illumination evaluation, used in the caching approaches, from the spatial to the directional domain. Using importance sampling allows us to apply caching not only on low‐gloss but also on shiny materials with high‐frequency BRDFs, for which the radiance caching algorithm breaks down.

Abstract Volumetric rendering is widely used to examine 3D scalar fields from CT/MRI scanners and numerical simulation datasets. One key aspect of volumetric rendering is the ability to provide perceptual cues to aid in understanding structure contained in the data. While shading models that reproduce natural lighting conditions have been shown to better convey depth information and spatial relationships, they traditionally require considerable (pre)computation. In this paper, a shading model for interactive direct volume rendering is proposed that provides perceptual cues similar to those of ambient occlusion, for both solid and transparent surface‐like features. An image space occlusion factor is derived from the radiative transport equation based on a specialized phase function. The method does not rely on any precomputation and thus allows for interactive explorations of volumetric data sets via on‐the‐fly editing of the shading model parameters or (multi‐dimensional) transfer functions while modifications to the volume via clipping planes are incorporated into the resulting occlusion‐based shading.

Rendering realistic organic materials is a challenging issue. The human eye is an important part of nonverbal communication which, consequently, requires specific modeling and rendering techniques to enhance the realism of virtual characters. We propose an image-based method for estimating both iris morphology and scattering features in order to generate convincing images of virtual eyes. In this regard, we develop a technique to unrefract iris photographs. We model the morphology of the human iris as an irregular multilayered tissue. We then approximate the scattering features of the captured iris. Finally, we propose a real-time rendering technique based on the subsurface texture mapping representation and introduce a precomputed refraction function as well as a caustic function, which accounts for the light interactions at the corneal interface.

Abstract High quality lighting is one of the challenges for interactive tree rendering. To this end, this paper presents a lighting model allowing real‐time rendering of trees with convincing indirect lighting. Rather than defining an empirical model to mimic lighting of real trees, we work at a lower level by modeling the spatial distribution of leaves and by assigning them probabilistic properties. We focus mainly on precise low‐frequency lighting that our eyes are more sensitive to and we add high‐frequency details afterwards. The resulting model is efficient and simple to implement on a GPU.

Abstract We describe a global illumination method combining two well known techniques: photon mapping and irradiance caching. The photon mapping method has the advantage of being view independent but requires a costly additional rendering pass, called final gathering. As for irradiance caching, it is view‐dependent, irradiance is only computed and cached on surfaces of the scene as viewed by a single camera. To compute records covering the entire scene, the irradiance caching method has to be run for many cameras, which takes a long time and is a tedious task since the user has to place the needed cameras manually. Our method exploits the advantages of these two methods and avoids any intervention of the user. It computes a refined, view‐independent irradiance cache from a photon map. The global illumination solution is then rendered interactively using radiance cache splatting.

3D reconstruction of urban environments is a widely studied subject since several years, as it can lead to many useful applications: virtual navigation, augmented reality, architectural planification, etc. One of the most difficult problem nowadays in this context is the acquisition and treatment of very large scale data if precise reconstruction is aimed. In this paper we present a system for computing geo-referenced positions and orientations of images of buildings from non calibrated videos. Providing such information is a mandatory step to well conditioned large scale and precise 3D reconstruction of urban areas. Our method is based on the registration of multimodal datasets, namely GPS measures, video sequences and rough 3D models of buildings.

We present a novel method for fast, high quality computation of glossy global illumination in animated environments. Building on the irradiance caching and radiance caching algorithms, our method leverages temporal coherence by sparse temporal sampling and interpolation of the indirect lighting. In our approach, part of the global illumination solution computed in previous frames is reused in the current frame. Our reusing scheme adapts to the change of incoming radiance by updating the indirect lighting only where there is a significant change. By reusing data in several frames, our method removes the flickering artifacts and yields a significant speedup compared to classical computation in which a new cache is computed for every frame. We also define temporal gradients for smooth temporal interpolation. A key aspect of our method is the absence of any additional complex data structure, making the implementation into any existing renderer based on irradiance and radiance caching straightforward. We describe the implementation of our method using graphics hardware for improved performance.

In this paper, we present a ray tracing-based method for accelerated global illumination computation in scenes with low-frequency glossy BRDFs. The method is based on sparse sampling, caching, and interpolating radiance on glossy surfaces. In particular, we extend the irradiance caching scheme proposed by Ward et al. to cache and interpolate directional incoming radiance instead of irradiance. The incoming radiance at a point is represented by a vector of coefficients with respect to a hemispherical or spherical basis. The surfaces suitable for interpolation are selected automatically according to the roughness of their BRDF. We also propose a novel method for computing translational radiance gradient at a point.

We present a new fast algorithm for rendering the depth-of-field effect for point-based surfaces. The algorithm handles partial occlusion correctly, it does not suffer from intensity leakage and it renders depth-of-field in presence of transparent surfaces. The algorithm is new in that it exploits the level-of-detail to select the surface detail according to the amount of depth-blur applied. This makes the speed of the algorithm practically independent of the amount of depth-blur. The proposed algorithm is an extension of the elliptical weighted average (EWA) surface splatting. We present a mathematical analysis that extends the screen space EWA surface splatting to handle depth-of-field rendering with level-of-detail, and we demonstrate the algorithm on example renderings.

This paper presents a new navigation system built upon our client-server framework named Magellan. With this system one can navigate through a city model represented with procedural models transmitted to clients over a low bandwidth network. The geometry of these models is generated on the fly and in real time at the client side. The navigation system relies on different kinds of preprocessing such as space subdivision, visibility computation as well as a method for computing some parameters used to efficiently select the appropriate level of detail of objects. These two last kinds of preprocessing are automatically performed by the graphics hardware.

The paper describes a radiosity method well suited to dynamic changes while requiring less memory compared to classical hierarchical radiosity. Our method relies on the concept of interaction meshes and does not need any computation of links between patches. The light originating at emitters and arriving at a receiving input surface is stored on separate meshes, each one corresponding to an emitter-receiver pair. These meshes are called interaction meshes and facilitate the handling of dynamic changes since for each input surface the surfaces illuminating it can be determined very quickly. The second advantage of the method is the use of a refinement criterion based on the comparison between the illuminances (illuminance is a photometric quantity equivalent to irradiance) over the receiving surfaces reconstructed from the interaction meshes. This criterion makes possible the use of artificial and natural lighting. Finally, this meshing technique is well suited to multigridding resolution systems for which the interaction meshes are not refined but recomputed at each iteration without cumulating error due to earlier iterations.

When computing global illumination in environments made up of surfaces with general Bidirectional Reflection Distribution Functions, a three point formulation of the rendering equation can be used. Brute‐force algorithms can lead to a linear system of equations whose matrix is cubic, which is expensive in time and space. The hierarchical approach is more efficient. Aupperle et al. proposed a hierarchical three point algorithm to compute global illumination in the presence of glossy reflection. We present in this paper some improvements we brought to this method: shooting, “lazy” push‐pull, photometric subdivision criterion, etc. Then we will show how our new method takes into account non‐planar surfaces in the hierarchical resolution process.

In this paper we propose a SPMD parallel hierarchical radiosity algorithm relying on a novel partitioning method which may apply to any kind of architectural scene. This algorithm is based on MPI (Message Passing Interface), a communication library which allows the use of either a heterogeneous set of concurrent computers or a parallel computer or both. The database is stored on a common directory and accessed by all the processors (through NFS in case of a network of computers). As the objective is to handle complex scenes such as building interiors, to cope with the problem of memory size, only a subset of the database resides in memory of each processor. This subset is determined with the help of a partitioning into 3D cells, clustering and visibility calculations. A graph expressing visibility between the resulting clusters is determined, partitioned (with a new method based on classification of K‐means type) and distributed amongst all the processors. Each processor is responsible for gathering energy (using the Gauss‐Seidel method) only for its subset of clusters. In order to reduce the disk transfers due to downloading these subsets of clusters, we use an ordering strategy based on the traveling salesman algorithm. Dynamic load balancing relies on a task stealing approach while termination is detected by configuring the processors into a ring and moving a token around this ring. The parallel iterative resolution is of group iterative type. Its mathematical convergence is proven in the appendix.

Hierarchical radiosity is a very demanding process in terms of computation time and memory resources even for scenes of moderate complexity. To handle complex environments which don't fit in the memory, new solutions have to be devised. One solution is to partition the scene into subsets of polygons (3D cells or clusters) and to maintain in memory only some of them. The radiosity computation is performed only for this resident subset which changes during the resolution process. This change entails many read and write operations from or onto the disk. These disk transfers must be ordered to make the radiosity algorithms tractable. The authors propose different ordering strategies which can be seen as complementary to those devised by Teller (1994).

Computing global illumination for complex environments in moderate time and walking through them is one of the challenges in computer graphics. To meet this goal, preprocessing is necessary. This preprocessing consists in partitioning the environment into cells and determining visibility between these cells. Most of the existing partitioning methods rely on the binary space partitioning (BSP) technique which can be easily applied to axial environments. However, for non-axial scenes, BSP has a high complexity of O (n3) in time to construct a tree of size at worst O(n2), n being the total number of input polygons. Moreover, this technique entails a large number of cells that do not necessarily fit with the topology of the environment. We propose in this paper a partitioning method which can be applied to non-axial buildings with several floors. It consists of two steps. In the first step each floor is extracted by applying a BSP technique using the most occlusive horizontal polygons for splitting. In the second step each floor is in turn partitioned with a model-based method operating in a dual 2D space. The result is a low number of cells fitting at best with the environment topology. © 1998 John Wiley & Sons, Ltd.

Abstract In spite of the number of efforts made by the computer graphics researchers, till today the computation of view‐independent global illumination in an environment containing non‐diffusely reflecting objects is a non‐resolved problem. In general, non‐deterministic techniques seem to be capable of solving this problem. In this article we propose one such non‐deterministic method which will permit such calculation by using a combined technique of higher order function approximation and particle tracing. We have used multi‐wavelets as basis functions and have calculated the illumination function approximation coefficients by exploiting the adjointness between the radiance equation and the potential equation.

Abstract 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.

Abstract When using radiosiiy, the visual quality of the rendered images strongly depends on the method employed for discretizing the scene into patches. A too fine discretization may give rise to artifacts, while with a coarse discretization areas with high radiosity gradient may appear. To overcome these problems, the discretization must adapt to the scene. That is, the interaction between two patches must account for the distance between them as well as their surface area. In other words, surfaces far away are discretized less finely than nearby surfaces. These aspects are considered by the new adaptive discretiration method described in this paper. It performs both discretization and system resolution at each iteration of the shooting process, allowing then interactivity.

It has long been observed that the keenness of sight is lower for diagonal directions than for horizontal or vertical ones. This anisotropy of the human eye response can be exploited by using a non-orthogonal sampling pattern with a reduced sampling density. After an introduction to the two-dimensional sampling theory, it is shown that quincunx sampling is well suited to this characteristic. Then a sampling scheme based on this approach is described. This effectively leads to halving the sampling density and thereby the computing time of ray-traced pictures.

This paper deals with the integration of a VLSI chip dedicated to ray tracing bicubic patches. A recursive subdivision algorithm is embedded in this chip. The recursion stops when the termination conditions are met. A software implementation allowed for the determination of key parameters which influenced the choice of the proposed chip' architecture. Only some modules of the chip are, at the present time, simulated and laid out, the rest is being implemented. A detailed description of the chip' modules is given.

A parallel space tracing algorithm is presented. It subdivides the scene into regions. These latter are distributed among the processors of an iPSC hypercube machine designed by Intel company. Each processor subdivides its own region into cells to accelerate the ray tracing algorithm. Processors communicate by means of messages. The pyramidal shape of the regions allows the deletion of the primary ray messages. A method of performing a roughly uniform load distribution is proposed.

Abstract Some theoretical extensions are brought to Koparkar and Mudur's method which deals with a polygonal approximation of parametric surfaces using potential extrema. The proposed extensions allow the determination of both the existence and the equation of a curve solution of potential extrema. Solutions are given to solve the crack problem and to avoid the artificats due to an inexact ray‐surface intersection point near the silhouette or on the higher curvature regions. Moreover, two methods of ray tracing surfaces are proposed.

This paper describes a new algorithm of space tracing. Scenes are modeled by a CSG tree. Space is subdivided regularly into 3D regions called boxes. With each box is associated a subtree which is the restriction of the whole scene CSG tree to primitives belonging to this box. A 3D grid is used to access boxes.