Marc Stamminger

George Drettakis

Perspective Shadow Maps

Keywords: I.3.3 [Computer Graphics]: Picture/Image Generation-Bitmap and framebuffer operations; I.3.7 [Computer Graphics]: Three-Dimensional Graphics and Realism-Color, shading, shadowing, and texture Frame Buffer Algorithms, Graphics Hardware, Illumination, Level of Detail Algorithms, Rendering, Shadow Algorithms

Figure 1: (Left) Uniform 512x512 shadow map and resulting image. (Right) The same with a perspective shadow map of

Introduction

Shadows are an important element for any computer graphics image. They provide significant visual cues, aiding the user to understand spatial relationships in a scene and add realism to synthetic images. The challenge of generating shadows goes back to the early days of computer graphics, where various geometric algorithms such as those based on clipping [START_REF] Weiler | Hidden surface removal using polygon area sorting[END_REF], or shadow volumes £ Marc.Stamminger|George.Drettakis @sophia.inria.fr The first author is now at the Bauhaus-Universität, Weimar, Germany. [START_REF] Crow | Shadow algorithms for computer graphics[END_REF] were introduced. These methods often suffer from robustness problems due to the geometric computations required, and may also require non-trivial data structures or involve a significant rendering overhead. In addition, such algorithms are usually a preprocess, and are thus best suited to static scenes.

The introduction of shadow maps [START_REF] Williams | Casting curved shadows on curved surfaces[END_REF] marked an important step in the evolution of shadow algorithms. With shadow maps, we simply render the scene from the viewpoint of the light source, creating a depth image. When rendering each pixel in the final image, the visible point is transformed into the light coordinate system, and a depth comparison is performed with the corresponding shadow map pixel to decide whether the point is hidden with respect to the light source. A single shadow map is sufficient for directional lights and spot lights; omnidirectional point lights require several shadow maps to cover all emission directions. When considering point lights in this paper, we implicitly mean spot lights, but the ideas developed here transfer to omnidirectional point lights easily.

Compared to shadow algorithms which require geometric calculations prone to robustness problems, shadow maps are much more general. Due to their simplicity, they have been incorporated into graphics hardware, first on the Infinite Reality [START_REF] Montrym | Infinitereality: A real-time graphics system[END_REF] and more recently on consumer-level graphics cards such as the NVIDIA GeForce3. The possibility to have shadows for large scenes makes shadow maps particularly interesting for rendering-intensive applications like video games. Shadow maps are also widely used in offline, high-quality rendering systems because of their simplicity and flexibility. In the RenderMan standard, for example, shadow maps are the most widely used method to generate images with shadows [START_REF] Upstill | The RenderMan Companion[END_REF].

However, as with any method based on a discrete buffer, shadow maps suffer from aliasing problems, if the shadow map resolution used is insufficient for the image being rendered. This is particularly true for scenes with a wide depth range, where nearby shadows need high resolution, whereas for distant shadows low resolution would be sufficient. Recent shadow map approaches [START_REF] Tadamura | Rendering optimal solar shadows with plural sunlight depth buffers[END_REF][START_REF] Fernando | Adaptive shadow maps[END_REF] adapt shadow map resolution by using multiple shadow maps of varying resolution. However, by using multiple shadow maps, several rendering passes are required, and due to the more involved data structures, the methods no longer map to hardware.

In this paper, we present a novel approach to adapt shadow map resolution to the current view. By using a non-uniform parameterization, a single perspective shadow map is generated, providing high resolution for near objects, and decreased resolution as we move away from the viewpoint. An example is shown in Fig. 1. A standard shadow map (left) has insufficient resolution for nearby objects (center left). In contrast, in our perspective shadow map (center right), resolution varies such that nearby objects have sufficient shadow map resolution (right).

Our shadow map projection can still be represented by a 4 ¢ 4 matrix, so that it fully maps to hardware. It can easily be used to improve any interactive and offline rendering method based on shadow maps, with only marginal overhead for the computation of the optimized projection matrix. Perspective shadow maps often reduce aliasing dramatically. In a few difficult cases, our parameterization converges to standard uniform shadow maps. Our approach is view-dependent, requiring the generation of a new shadow map at each frame or at least after major camera movements. This is necessary for scenes containing moving objects anyhow, such as those used in video games or other interactive applications. In this case, we have no significant speed penalty compared to a standard, fixed-resolution shadow map.

Shadow Map Aliasing

First, we briefly formalize the aliasing problems of shadow maps for point light sources. Every pixel in the shadow map represents a sheared pyramid of rays, passing through a shadow map pixel of size d s x d s on the (shadow) image plane (Fig. 2). In the following, we will call the reciprocal of d s the shadow map resolution.

To increase shadow map resolution we decrease d s and vice versa. When the ray bundle through a shadow map pixel hits a surface at distance r s under angle α, the size of the intersection is approximately d s r s cos α. In the final image, this intersection with the surface has size:

d d s r s r i cos β cos α
where β is the angle between the light source direction and the surface normal and r i is the distance from the camera to the intersection.

Figure 2: Shadow map projection quantities.

For directional light sources, d is independent of r s , so d only depends on d s r i . Analogously, for an orthogonal view d is proportional to d s r s .

Shadow map undersampling appears when d is larger than the image pixel size d i . This can happen when d s r s r i becomes large, which typically happens when the user zooms into a shadow boundary so that single shadow map pixels become visible. We will call this perspective aliasing. Due to limited memory, the shadow map resolution 1 d s can only be increased up to a certain limit in practice. Perspective aliasing can be avoided by keeping the fraction r s r i close to a constant. As we show in this paper, this is what is achieved when we compute the shadow map after perspective transformation.

When cos β cos α becomes large, projection aliasing appears. This typically happens when the light rays are almost parallel to a surface, so that the shadow stretches along the surface. Projection aliasing is not treated by perspective shadow maps, since this would require a local increase in shadow map resolution. This is not possible without much more involved data structures, and it would force us to abandon hardware acceleration.

Note that there are also other sources of aliasing when using shadow maps, e.g., depth quantization, which we will not treat here.

Related Work

The literature on shadow generation in computer graphics is vast, and far beyond the scope of this paper (see [START_REF] Woo | A survey of shadow algorithms[END_REF] for an old, but nice survey). We thus concentrate our review on previous work directly related to shadows maps and our novel approach.

Reeves et al. [START_REF] Reeves | Rendering antialiased shadows with depth maps[END_REF] introduced the concept of percentage closer filtering. The idea is to filter the shadows obtained from shadow maps by interpolating the binary result of the depth comparison instead of the depth values. The deep shadow maps of Lokovic et al. [START_REF] Lokovic | Deep shadow maps[END_REF] extend the idea of filtering shadow maps by storing approximate attenuation functions for each shadow map pixel, thus capturing self shadowing within hair, fur or smoke. Both approaches perform anti-aliasing in that they filter undersampling artifacts, but they do not solve the problem of undersampling as such.

Tadamura et al. [START_REF] Tadamura | Rendering optimal solar shadows with plural sunlight depth buffers[END_REF] introduce multiple shadow maps with varying resolution as a solution to the aliasing problem for large outdoor scenes. This solves the problem of perspective aliasing, but it does not map to hardware and is thus not appropriate for interactive applications.

An interesting improvement to traditional shadow maps is the adaptive shadow map method [START_REF] Fernando | Adaptive shadow maps[END_REF]. This approach replaces the "flat" shadow map with an adaptive, hierarchical representation, which is updated continuously during a walkthrough. For each frame, a first rendering pass is required to determine which parts of the hierarchical shadow map need refinement. This is achieved using OpenGL texture mip-mapping capabilities. Perspective and projection aliasing are detected. The most critical parts of the shadow map are then rendered at higher resolution, read back, and inserted into the hierarchical shadow map structure. Oversampled parts of the hierarchy are truncated. The method is a software solution, since it requires the traversal and refinement of a hierarchical data structure instead of a shadow map, and thus cannot entirely map to hardware. Rapid view changes make it necessary to update a large number of nodes in the hierarchy, so either the frame rate drops or aliasing appears until the hierarchical structure has been updated. The generation of a new node essentially requires an entire rendering pass, albeit with a small part of the model, but with the full cost of a frame-buffer readback to update the data structure. Scenes with moving objects would require the generation of the entire hierarchical structure at each frame, which would require many rendering passes.

Shadow maps are closely related to textures, so we assume the reader is familiar with the texturing and the projective mapping process. Most standard graphics textbooks treat these issues [START_REF] Foley | Computer graphics, principles and practice[END_REF]. A particularly nice and thorough description can be found in [START_REF] Heckbert | Survey of Texture Mapping[END_REF].

Overview

Perspective shadow maps are computed in post-perspective space of the current camera, or, using standard graphics terminology, the space of normalized device coordinates [START_REF] Foley | Computer graphics, principles and practice[END_REF]. In the traditional rendering pipeline, perspective is obtained by transforming the world to a perspectively distorted space, where objects close to the camera are enlarged and distant objects are shrunk (see Fig. 3). This mapping is projective [START_REF] Heckbert | Survey of Texture Mapping[END_REF] and can thus be represented by a 4 ¢ 4 matrix with homogeneous coordinates. It projects the current viewing frustum to the unit cube; the final image is generated by a parallel projection of this cube along z.

The idea of perspective shadow maps is to first map the scene to post-perspective space and then generate a standard shadow map in this space by rendering a view from the transformed light source to the unit cube. We can work in post-perspective space almost as in world space, with the exception of objects behind the viewer, which will be handled in Sect. 4. Because the shadow map "sees" the scene after perspective projection, perspective aliasing (see Sect. 1.1) is significantly decreased, if not completely avoided.

To explain this principle a special case is depicted in Fig. 3. The scene is illuminated by a vertical directional light source. In postperspective space the shadow map is an orthogonal view from the top onto the unit cube and the final image is an orthogonal view from the front. Consequently, all shadow map pixels projected onto the ground in this scene have the same size in the image. Thus, in the sense of Sect. 1.1, perspective aliasing is completely avoided for this case.

Post-Perspective Light Sources

To apply our new method, we first transform the scene to postperspective space, using the camera matrix. We then transform the light source by the same matrix, and generate the shadow map. The different cases which arise are described next.

Directional Light Sources

Directional light sources can be considered as point lights at infinity. The perspective mapping can move these sources to a finite position; the set of possible cases is shown in Fig. 3 and4. A directional light source parallel to the image plane remains at infinity. All other directional light sources become point lights on the infinity plane at z f • nµ ´f nµ, where n and f are the near and far distance of the viewing frustum (see Fig. 3).

A directional light source shining from the front becomes a point light in post-perspective space (Fig. 4, left), whereas a directional light source from behind is mapped to a "inverted" point light source (center). In this context, "inverted" means that all light rays for these light sources do not emanate, but converge to a single point. Such inverted point light sources can easily be handled as point lights with their shadow map depth test reversed, such that hit points furthest from the point source survive. The extreme cases are directional lights parallel (facing or opposite to) the view direction, which are mapped to a point light just in front of the viewer (right).

Point Light Sources

The different settings for point light sources are shown in Fig. 5. Point light sources in front of the viewer remain point lights, (left). Point lights behind the viewer are mapped beyond the infinity plane and become inverted (center). Point lights on the plane through the view point which is perpendicular to the view direction (camera plane), however, become directional (right).

Discussion

In post-perspective space, the final image is an orthogonal view onto the unit cube. Following our observations in Sect. 1.1, this means that perspective aliasing due to distance to the eye, r i , is avoided. However, if the light source is mapped to a point light in post-perspective space, aliasing due to the distance to the shadow map image plane, r s , can appear.

The ideal case occurs when, after the perspective mapping, the light source is directional. Perspective aliasing due to r s is thus also avoided. This happens for: ¯a directional light parallel to the image plane (see Fig. 3), ¯a point light in the camera plane. The typical example is the miner's head-lamp, that is a point light just above the camera.

It is known that this setting is also ideal for standard shadow maps [7]. With our parameterization, the offset can be arbitrarily large, as long as the point remains in the camera plane.

On the other hand, the less optimal cases appear when we obtain a point light with a large depth range in post-perspective space. The extreme example is a directional light parallel to the viewing direction. In post-perspective space, this becomes a point light on the infinity plane on the opposite side of the viewer (see Fig. 4 right). In this worst case the two perspective projections with opposite viewing directions cancel out mutually and we obtain a standard uniform shadow map.

In general, for directional light sources the benefit is maximal for a light direction perpendicular to the view direction. Since these are also parallel lights in post-perspective space, perspective aliasing is completely avoided in this case. Consider the smaller of the two angles formed between the light direction and the viewing direction. The benefit of our approach decreases as this angle becomes smaller, since we move further away from the ideal, perpendicular case. If the angle is zero our parameterization corresponds to a uniform shadow map.

For point lights, the analysis is harder, since the point light source also applies a perspective projection. Informally, the advantage of our parameterization is largest when the point light is far away from the viewing frustum, so that it is similar to a parallel light, and if the visible illuminated region exhibits a large depth range. For the case of a miner's lamp, which is known to be ideal for uniform shadow maps [7], our parameterization again converges to the uniform setting.

A common problem in shadow maps is the bias necessary to avoid self-occlusion or surface acne [7]. This problem is increased for perspective shadow maps, because objects are scaled non-uniformly. We use a constant offset in depth in shadow map space, which may require user adjustment depending on the scene.

Including all Objects Casting Shadows

Up to now, we ignored an important issue: our shadow map is optimized for the current viewing frustum. But the shadow map must contain all objects within that frustum plus all potential occluders outside the frustum that can cast a shadow onto any visible object.

World Space

More formally, we define the set of points that must appear in the shadow map as follows: Let S be an envelope of the scene objects, typically its bounding box. V is the viewing frustum and L the light source frustum. The light source is at position l (for directional lights L R 3 and l is at infinity). First, we compute the convex hull M of V and l, so M contains all rays from points in V to l. From M we then remove all points outside the scene's bounding box and the light frustum: H M S L (shown in yellow in Fig. 6 (right)).

Figure 6: The current view frustum V , the light frustum L with light position l, and the scene bounding box S (left). M is obtained by extending V towards the light (center). Then M is intersected with S and L to obtain the set of points that need to be visible in the shadow map (right).

In our implementation we use the computational geometry library CGAL (www.cgal.org) to perform these geometric computations. As a result, the window of the shadow map is chosen so that all points in H are included. However, the shadow map will not see H , but its transformation to post-perspective space, so we have to consider how H changes by the perspective mapping.

Post-perspective Space

Under projective transformations lines remain lines, but the order of points along a line can change. For perspective projections, this happens when a line intersects the camera plane, where the intersection point is mapped to infinity. As a result, we can quickly transform the convex set H to post-perspective space by transformation of its vertices, as long as H is completely in front of the viewer. An example where this is not the case is shown in Fig. 7. Points behind the viewer had to be included, because they can cast shadows into the viewing frustum. However, in post-perspective space, these points are projected to beyond the infinity plane. In this case, possible occluders can be on both sides of the infinity plane.

Figure 7: The scene is lit by a directional light source coming from behind (top left). After perspective projection, an object behind the viewer is inverted and appears on the other side of the infinity plane (lower left). To treat this we move the center of projection back (upper right), so that we are behind the furthermost point which can cast a shadow into the view frustum. After this, a standard shadow map in post-perspective space is again sufficient (lower right).

One solution would be to generate two shadow maps in this case. A first one as described previously, and a second one that looks "beyond" the infinity plane. We avoid this awkward solution by a virtual camera shift. We virtually move the camera view point backwards, such that H lies entirely inside the transformed camera frustum; the near plane distance remains unchanged and the far plane distance is increased to contain the entire previous frustum. Note that this camera point displacement is only for the shadow map generation, not for rendering the image.

By this, we modify the post-perspective space, resulting in decreased perspective foreshortening. If we move the camera to infinity, we obtain an orthogonal view with a post-perspective space that is equivalent to the original world space; the resulting perspective shadow map then corresponds to a standard uniform shadow map.

Consequently, we can say that by moving back the camera, our parameterization degrades towards that of a standard shadow map. By this, perspective aliasing is reintroduced, however, in practice this is only relevant for extreme cases, so we found it preferable to the double shadow map solution. It is interesting to note that for the cases that are ideal for perspective shadow maps, no such shift is necessary, because H will always be completely in front of the camera. The shift distance will be significant only if the light source is far behind the viewer. But in this case, our parameterization converges to the uniform shadow map anyway.

Point rendering (e.g., [START_REF] Pfister | Surfels: Surface elements as rendering primitives[END_REF][START_REF] Rusinkiewicz | Qsplat: A multiresolution point rendering system for large meshes[END_REF][START_REF] Stamminger | Interactive sampling and rendering for complex and procedural geometry[END_REF][START_REF] Wand | The randomized z-buffer algorithm: Interactive rendering of highly complex scenes[END_REF]) has proven to be a very effective means for rendering complex geometry. Points are particularly well suited for natural objects. However, for the generation of uniform shadow maps point rendering loses most of its benefits. A very large, dense point set needs to be generated in order to render a high-resolution uniform shadow map. Frequent regeneration of the shadow map for dynamic scenes becomes highly inefficient.

On the other hand, our projective shadow map parameterization fits nicely with the point rendering approaches presented in [START_REF] Wand | The randomized z-buffer algorithm: Interactive rendering of highly complex scenes[END_REF][START_REF] Stamminger | Interactive sampling and rendering for complex and procedural geometry[END_REF], in the sense that the point sets generated by these methods can also be used for the rendering of the shadow map. The reason is that these approaches generate random point clouds, with point densities adapted to the distance to the viewer. In post-perspective space, these point clouds have uniform point density. Since perspective shadow maps are rendered in this space, the shadow map can assume that point densities are uniform. It is thus easy to select the splat size when rendering the shadow map such that holes are avoided.

Implementation and Results

We implemented perspective shadow maps within an interactive rendering application using OpenGL hardware assisted shadow maps.

The following results, and all sequences on the accompanying video, were obtained under Linux on a Compaq AP550 with two 1 GHz Pentium III processors and an NVIDIA GeForce3 graphics accelerator.

We used the shadow map extensions GL SGIX depth texture and GL SGIX shadow. The shadow maps are rendered into p-buffers (GLX SGIX pbuffer) and are applied using register combiners (GL NV register combiners).

In order to obtain optimal results from perspective shadow maps, we require that the near plane of the view be as far as possible. We achieve this by reading back the depth buffer after each frame, searching the minimal depth value, and adapting the near plane accordingly. Due to the fast bus and RAM of our computer, the speed penalty for reading back the depth buffer is moderate, e.g., 10ms for reading back depth with 16 bits precision at 640 by 480 pixel resolution. The increase in quality is well worth this overhead.

Fig. 1 shows a chess board scene, lit by a spot light source. The left image shows a uniform shadow map, the center left image is the resulting rendering with well visible shadow map aliasing. The far right image was obtained with a perspective shadow map of the same size, which is shown on the center right.

Fig. 8 shows Notre Dame in Paris, augmented with a crowd and trees. With point based rendering for the trees and the crowd, the views shown are still obtained at about 15 frames/sec.

In the street scene in Fig. 9 the cars and two airplanes are moving. The figure shows three snapshots from an interactive session; all images were obtained at more than ten frames per second with perspective shadow maps of size 1024 ¢1024.

Our final test scene is a complete ecosystem, consisting of hundreds of different plants and a few cows. The view shown in Fig. 10 contains more than 20 million triangles. We show the image without shadows (left), with shadows from a 1024 ¢1024 uniform shadow map (center) and with shadows from a projective shadow map of the same size (right).

Conclusions

We have introduced perspective shadow maps, a novel parameterization for shadow maps. Our approach permits the generation of shadow maps with greatly improved quality, compared to standard uniform shadow maps. By choosing an appropriate projective mapping, shadow map resolution is concentrated where appropriate. We have also shown how our method can be used for point rendering, thus allowing interactive display of very complex scenes with highquality shadows. Perspective shadow maps can be used in interactive applications and fully exploit shadow map capabilities of recent graphics hardware, but they are also applicable to high-quality software renderers.

Figure 3 :

 3 Figure 3: The scene is illuminated by a vertical directional light source (left). By applying the eye-view perspective transformation and then generating the shadow map (right), the shadow map pixels projected on the ground are evenly distributed in the image.

Figure 4 :

 4 Figure 4: Directional lights in world space (top row) become point lights in post perspective space (bottom row) on the infinity plane.Lights from behind become inverted, i.e., the order of hits along a ray is inverted.

Figure 5 :

 5 Figure 5: Mapping of point lights in world space (top row) to postperspective space (bottom row). A point light in front of the user remains a normal point light (left), a point light behind the viewer becomes inverted (center). Boundary cases are mapped to directional lights (right).

Figure 8 :

 8 Figure 8: Notre Dame rendered with shadow maps of size 1024 ¢ 1024. The left image and the right halves of the center and right image were rendered with perspective shadow maps at about 15 frames per second. The left sides of the center and right image have been generated with uniform shadow maps of the same size. The rendering of the trees and the crowd is accelerated by point rendering.

Figure 9 :Figure 10 :

 910 Figure 9: A street scene with moving cars and planes. The images were rendered at more than 10 frames per second with perspective shadow maps of size 1024 ¢1024. Note the different shadow details at varying distances.

Acknowledgments

The first author has been supported by a Marie-Curie postdoctoral Fellowship while doing this work. L. Kettner implemented the frustum intersection code in CGAL (www.cgal.org). Thanks to F. Durand for his very helpful comments. Most of the models in the result section were downloaded from www.3dcafe.com and www.help3d.com.


Pierre Poulin

Marc Stamminger

Franc ¸ois Duranleau

Marie-Claude Frasson

George Drettakis

Interactive Point-based Modeling of Complex Objects from Images

Modeling complex realistic objects is a difficult and time consuming process. Nevertheless, with improvements in rendering speed and quality, more and more applications require such realistic complex 3D objects. We present an interactive modeling system that extracts 3D objects from photographs. Our key contribution lies in the tight integration of a point-based representation and user interactivity, by introducing a set of interactive tools to guide reconstruction. 3D color points are a flexible and effective representation for very complex objects; adding, moving, or removing points is fast and simple, facilitating easy improvement of object quality. Because images and depths maps can be very rapidly generated from points, testing validity of point projections in several images is efficient and simple. These properties allow our system to rapidly generate a first approximate model, and allow the user to continuously and interactively guide the generation of points, both locally and globally. A set of interactive tools and optimizations are introduced to help the user improve the extracted objects.

Introduction

In the last decade, the realism of images and 3D objects has greatly improved, but it is still quite difficult and time consuming to create models of complex realistic objects, such as those often appearing in nature. Flower beds, plants, trees, tangled rope, crumpled paper, junkyards, etc., are all examples of very complex objects because of the combined presence of numerous surface details, textures, tiny structures, occlusions, holes, discontinuities, specularities, etc. There is however an important need in computer graphics applications (games, film, virtual/augmented reality) for convincing models of realistic complex 3D objects.

For certain classes of such complex objects, specialised modeling methods have been designed with great success; e.g., mountains, waves, plants, cities, etc. However, each method is restricted to its class of objects, and cannot easily be extended to other classes. Imagebased methods [START_REF] Levoy | Light field rendering[END_REF][START_REF] Gortler | The lumigraph[END_REF][START_REF] Buehler | Unstructured lumigraph rendering. A: Fruit bowl[END_REF][START_REF] Matusik | Image-based 3D photography using opacity hulls[END_REF] are quite general, and can produce objects that are visually very complex. They reparametrize radiance information from a large number of input images to display new views of a 3D object with little or no underlying geometry. Unfortunately these representations require lots of memory, and most have difficulty handling mutual occlusion and illumination with other objects. This makes their complete integration in a typical rendering system cumbersome and sometimes impossible.

Reconstruction of 3D objects from photographs is a particularly powerful way to model real objects. With known camera parameters, correspondences between image pixels are used to compute the 3D location and color of a surface. Even though good results have been obtained with these methods (see Section 2), reconstruction of complex and detailed geometry is still cumbersome.

To improve the quality of the extracted objects, we believe it is very important to appropriately involve the user in the reconstruction process to guide the spatial and spectral quality of the reconstructed objects. To support such user interaction we need to be able to interactively display and manipulate the (partially) reconstructed objects during the modeling process. Good support for interactivity is the main design choice in the system we present here.

Reconstructing complex objects from images also calls for a flexible object representation, which can be interactively rendered. 3D points augmented with color or texture attributes are such a general representation that do not require the computation of an intermediate representation such as a triangulation for display. They offer good visual quality when displayed from an appropriate distance, and are also well adapted for efficient visibility culling and levels of detail, facilitating interactivity. Several point-based rendering systems have recently been introduced [START_REF] Pfister | Surfels: Surface elements as rendering primitives[END_REF][START_REF] Rusinkiewicz | Qsplat: A multiresolution point rendering system for large meshes[END_REF][START_REF] Stamminger | Interactive sampling and rendering for complex and procedural geometry[END_REF]; we use an adaptation of [START_REF] Stamminger | Interactive sampling and rendering for complex and procedural geometry[END_REF].

Based on these two requirements, user interaction for modeling and efficient display of complex objects, we present an interactive system to extract a plausible set of 3D color points from images. The method and the point-based representation are general enough to model any kind of object, but their power is better exploited with complex textured objects. The modeling process is quite simple: a random 3D point is generated in a 3D zone of interest and projected into all the images to gather its colors. If a sufficient number of these colors confirm that the point is plausible, it is kept. Depth maps from this plausible set of 3D points are constructed at certain intervals in time to ignore images where the generated 3D point would be hidden.

We provide a set of interactive tools, which allow the user to guide the iterative solution in critical zones of interest, to modify various quality thresholds and recheck the validity of the set of 3D points, to eliminate outlier 3D points, to fill undesired holes, etc. This user control is a key element of our approach. It is made possible at every stage of the reconstruction process, because we use our point-based representation for efficient rendering of (possibly partially reconstructed) complex objects.

After a brief survey of methods to reconstruct surfaces from images (Section 2), we describe the various elements of our interactive system (Section 3). Results and statistics follow (Section 4). We finally conclude and present directions for further research.

Previous Work

In this paper, we address the problem of interactively reconstructing complex objects from images. We will thus not discuss techniques based on 3D scanners (lasers and structured light) or on other sensors. We will also restrict our research to already calibrated images, i.e., images for which the camera parameters have been computed. A vast literature exists on exploiting various cues to reconstruct objects, such as silhouettes, shadows, focus/defocus, motion, shading, etc. We will not specifically use these cues, even though they could improve the reconstruction process by providing additional information. The reader interested in the numerous methods developed over the years should consult books [START_REF] Ayache | Artificial Vision for Mobile Robots -Stereo-vision and Multisensor Perception[END_REF][START_REF] Faugeras | Three-Dimensional Computer Vision -A Geometric Viewpoint[END_REF][START_REF] Klette | Computer Vision: Three-Dimensional Data from Images[END_REF][START_REF] Trucco | Introductory Techniques for 3-D Computer Vision[END_REF], surveys [START_REF] Zhang | Shape from shading: A survey[END_REF][START_REF] Bernardini | The 3D model acquisition pipeline[END_REF], and collections of papers [START_REF] Stereo | [END_REF] dedicated to these topics.

Reconstructing 3D geometry from one, two, or more photos is a fundamental problem that has received extensive attention in computer vision. The more traditional approach is based on shape-from-stereo [START_REF] Dhong | Structure from stereo -a review[END_REF]. It consists in identifying a feature in one image and searching for a correspondence amongst a number of probable candidates in another image along its epipolar line (projection of the line of sight of the feature onto the other image). Very good results have been obtained in controlled conditions, such as the proximity of viewpoints, spatial or temporal smoothness of adjacent features, or particular shapes. Unfortunately, a good and complete solution still remains a very difficult problem since occlusions, holes, sharp edges, noise, shading, etc., complicate the match-ing process. In a general 3D scene, there exists an infinity of equivalent shapes that can reproduce the original photos.

An alternative of particular interest to us is volumetric object reconstruction [23,[START_REF] Kutulakos | A theory of shape by space carving[END_REF][START_REF] Dyer | Volumetric scene reconstruction from multiple views[END_REF][START_REF] Slabaugh | A survey of volumetric scene reconstruction methods from photographs[END_REF]. The approach is based on building a 3D volumetric object that is consistent with the images, rather than directly extracting 3D information from the images. In a typical process, 3D space is voxelized and voxels considered invalid (e.g., outside the silhouette in one image) are carved out from the volumetric representation. Besides testing silhouettes, information in each voxel about visibility, transparency, shading, etc., can all be tested with the images for photoconsistency. The set of color voxels or a surface fitted to these voxels can then be projected to form new images of the object; impressive results have thus been obtained.

Most of the above techniques are designed to be fully automatic, because the major applications of reconstruction from images have been in object recognition or collision avoidance in robotics. Furthermore, partial, and therefore non-photorealistic results are often quite satisfactory for these applications. Photorealism of the extracted surfaces has only received more attention over the last decade.

Since it is difficult to determine the appropriate quality-level of photorealism for various applications, the elusive additional requirements of photorealism are often better served by integrating the user in the reconstruction process. In fact, reconstruction of architectural 3D models with simple polygonal shapes and high quality textures has greatly benefited in realism from direct interventions of the user. A number of research [START_REF] Debevec | Modeling and rendering architecture from photographs: A hybrid geometry-and image-based approach[END_REF][START_REF] Sato | Object shape and reflectance modeling from observation[END_REF][START_REF] Poulin | Interactively modeling with photogrammetry[END_REF][START_REF] Hertzmann | Interactive 3D scene reconstruction from images[END_REF][START_REF] Guillou | Using vanishing points for camera calibration and coarse 3D reconstruction from a single image[END_REF][START_REF] Shlyakhter | Reconstructing 3D tree models from instrumented photographs[END_REF][START_REF] Dedieu | Adaptation of a 3D Model Reconstruction System from Photos to User Knowledge[END_REF] and commercial systems [30,32,33] have been developed on this premise. Unfortunately, only simple polygonal surfaces are extracted from these systems. Manually positioning polygons is clearly a time consuming and sometimes impossible task for complex objects. Even with the help of stereo-based algorithms [START_REF] Debevec | Modeling and rendering architecture from photographs: A hybrid geometry-and image-based approach[END_REF][START_REF] Hertzmann | Interactive 3D scene reconstruction from images[END_REF], ambiguities in these complex objects create severe difficulties that a user might be able to correct.

In the next section, we describe how we integrate user intervention at different stages of our interactive system for point-based reconstruction from images. It was inspired and has several similarities with the more traditional algorithms discussed above, but by tightly integrating our point-based representation with the interactive extraction process, we produce a more flexible tool to create improved models of complex objects. Its design also allows easy integration of most past and future improvements in the related algorithms. As an example, we show in Section 4.4 how our limited implementation of voxel coloring [23] can be integrated in our system.

Another interactive point-based modeling system was recently presented [START_REF] Rusinkiewicz | Realtime 3D model acquisition[END_REF]. It uses structured light to generate 3D points in regions of interest by letting the user manipulate the 3D real-world model with respect to a fixed camera. While many goals are identical, their system suffers from the inherent limitations of structured light, e.g., hard to use in large outdoor scenes and in presence of highly-specular surfaces.

Point Modeling

Our point modeling basic process starts with an initialization step followed by three main loops (point generation, interactive cleanup, and user-driven refinement). These are executed to produce a set of 3D color points approximating the 3D objects displayed in the images. The algorithm is summarized next. In what follows sufficient number is a user-controlled parameter. • Interactively define a smaller zone of interest and restrict point generation, jittering, etc., to this zone, or

• Interactively select a 3D point and use it as a source for 3D point filling, or

• Jitter the 3D points to increase their plausibility, or

• Merge nearby 3D points 5. Display the resulting set of 3D points.

A typical work session is depicted in Fig. 1 for the reconstruction of an intricate rope. An associated web site [31] provides higher resolution images and more detailed statistics. An accompanying video available on this web site demonstrates the interactivity of our system in action.

Note that steps 2 to 4 of our algorithm do not need to be executed sequentially. In practice the user starts with step 2, and then decides which of steps 2 to 4 is the next appropriate step. Since our underlying model, the 3D point set, can be rendered immediately and interactively, the user always has direct feedback about his actions and can quickly react and control the process efficiently. This feedback is possible after only a few seconds of interaction, even of very partial reconstructions of the objects (see Fig. 1).

In the rest of this section, we describe each individual step in detail.

Initialization

The input of our system is a set of calibrated digital images. We use ImageModeler TM from RealViz [33] to calibrate a relatively small (2-20) set of photos of resolutions between 1080×720 and 2160×1440 taken from a Canon EOS-DS30 digital camera. We try to preserve object colors as much as possible in the different photos by keeping the same picture exposure and zoom factors. In our examples, the photos are at approximately the same distance from the object, reducing distortion problems. This way, a 3D point from a mostly-lambertian surface appears similar in all photos. ImageModeler TM is an interactive calibration system exploiting feature points and epipolar geometry; it has proven quite robust in our scenes. Any other standard camera calibration algorithm could also be used (e.g., [START_REF] Tsai | A versatile camera calibration technique for high accuracy 3D machine vision metrology using off-the-shelf TV cameras and lenses[END_REF]).

Once the images have been calibrated, we select a primitive (any closed polyhedron) and transform it in 3D space with ImageModeler TM to define an envelope around the object to reconstruct. The projections of this 3D envelope in all images must enclose the object to reconstruct. The user can also draw a mask (with gimp or Photoshop) for each image to indicate pixels clearly outside the objects to reconstruct.

Generation of 3D Points

The basic process generates 3D points uniformly distributed within the envelope. To achieve this distribution, we randomly generate a 3D point in the bounding box of the envelope. To determine if it is interior to the envelope, we count the intersections of the envelope with a ray in a random direction. More systematic generation patterns, such as jittered points in a regular 3D grid (similar to the space carving approach [START_REF] Kutulakos | A theory of shape by space carving[END_REF][START_REF] Dyer | Volumetric scene reconstruction from multiple views[END_REF][START_REF] Slabaugh | A survey of volumetric scene reconstruction methods from photographs[END_REF]), did not improve the result significantly; random sampling proved much faster (in order of seconds) to produce an initial set of 3D points. As we shall show later (Section 3.4), more goal-directed point distributions give better results.

Validation of 3D points

We must next validate whether each new candidate 3D point can possibly be part of the model. The validation step consists in projecting the point on each image and gathering the colors at the corresponding pixels. An image can be augmented by a mask, automatically or manually painted by the user, to indicate each pixel clearly outside the object to reconstruct. If the image has such a mask and the 3D point projects onto an invalid pixel, the 3D point is immediately rejected. A depth map contains a distance (depth) at each pixel. If the image has such an associated depth map and the distance contained in its pixel is shorter than the distance to the candidate 3D point, the 3D point is considered occluded by earlier 3D points in this image, and the image and its pixel color are not considered in the validation.

This results in a list of images that see the 3D point and the colors the 3D point exhibits in these images. This list is used to compute a plausibility value for the 3D point in order to decide if we should keep the 3D point or not. In general, a point is plausible if one color clearly dominates in the color list. In order to find this dominant color, we compare colors by computing the Euclidean distance in a color space and compare it with a user-defined color threshold. We experimented with the color spaces RGB, CIE xy, CIE Luv, and CIE Lab, but for our purpose we could not detect that one color space outperformed the others. Comparisons in RGB are the fastest, since no color conversion is required.

An alternative is to color quantize all images to a common color palette, and then to compare colors by testing for equality. In a modeling session we typically test a very large number (millions) of candidate 3D points; since the equality test is much more efficient (2-4 times), this choice speeds up the overall process significantly. Moreover because the quantization is done at a preprocessing stage, it can be quite sophisticated, dealing with colors from adjacent pixels, perceptual criteria, etc. This quantization process has a general tendency to reduce shading variations in the images.

In our system, the user selects the maximum number of desired colors to represent all the quantized images. We use ppmquantall from the UNIX ppm tools. As a general rule of thumb, fewer colors will produce more color matches, and therefore more 3D points will qualify as valid. However, some of these 3D points considered as valid would have been rejected if their original colors had been evaluated. The loss of accuracy in color comparison is therefore compensated by an important gain in generation speed. Many of these false 3D points will be removed at the cleanup stage (Section 3.3). In our tests, we usually work in color quantization mode and select between 32 and 128 colors.

Testing Plausibility

To test whether one color dominates in the color list of a 3D candidate, we compare each color in the list with all others. The color with the most matches is considered the dominant color; the ratio of the number of matches over the list size is called plausibility. Finally, a 3D point is considered plausible, if the plausibility of its color list is above a user-defined plausibility threshold. Other more sophisticated standard variance measures could be applied instead, but this simple test gave satisfying results.

Consider the example in Fig. 2(left), showing four cameras looking at the rope scene of Fig. 1. Point A on the object is visible in all images. Consequently, all four images have the same color in the direction to A. The plausibility of A is thus 100%. Point B, also on the object, is hidden in two images. Nevertheless, the dominant color is still the same, but only with a plausibility of 50%. C is a completely wrong candidate, thus it delivers four different colors, resulting in a plausibility of 25%.

Visibility

Point B in the previous example has a plausibility of only 50% because occlusion is not considered properly. If we determine that cameras 3 and 4 do not see point B, we can remove the false colors from the list, so that it only contains two colors. The new color list then has a plausi-bility of 100%.

To handle occlusions, once a first rough approximate point set has been generated and validated, we compute the depth map of the point set for each image. This is similar to the approach of Szeliski and Golland [START_REF] Szeliski | Stereo matching with transparency and matting[END_REF]. Then in the plausibility test, any 3D candidate that is further from the camera than its corresponding depth map value, is considered hidden in the corresponding image and its color is not added to the color list for the point. This is depicted in Fig. 2(right). With a depth map for camera 4, point B cannot be visible from camera 4, the same is true for camera 3. Thus the resulting list only contains two elements, both of the same, correct color.

Interactive Cleanup

In early phases of a modeling session, false 3D points can be generated. As soon as better depth information is available, a large fraction of these points can be removed automatically. During an interactive session, the user modifies the thresholds and the system reevaluates the plausibility of all previously accepted 3D points, using the most recent depth maps. The system then removes all points below the current thresholds (color, fraction of visible images, etc.). The effect is illustrated in Fig. 1(d)-(g). This iterative process is directly controlled by the user who chooses the thresholds, when to generate new depth information, and when to clean up, according to the results displayed.

We also clean up the point set by rendering the points from the viewpoint of each input image and comparing the rendered images with the original images. All 3D points that result in a significantly different color in an image pixel are discarded. An item buffer with a unique number per 3D point identifies which 3D point is visible in a pixel of one input image. The rendering verification step works best with our texture reprojection method, which will be explained in Section 3.5.

User-directed Refinement of the 3D Model

The two more automatic techniques described above can significantly improve the set of 3D points and can also be run as a background process when computing power is available. However, a more interactive approach is usually better to refine the set of 3D points where the user feels details are needed. We present a set of four tools, which allow the user to interactively improve the quality of the model.

Interactive Modeling Tool

Our first technique lets the user position a smaller primitive in 3D space, and restrict most of the above described operations to this more confined zone of interest. In our implementation, this is a sphere, which has as center the intersection of the eye ray through the current mouse pointer position with the point set (see accompanying video [31]). The user can move this sphere intuitively, and increase or decrease its size. Usually, the sphere is used to restrict point generation, in order to add points and thus detail to undersampled regions. However, it can also be used to clean up certain regions, or remove large incorrectly classified object parts.

3D Filling Tool

Another type of interactive manipulation lets the user position special sources of 3D point generation, similarly to the approach of Chen and Medioni [START_REF] Chen | A volumetric stereo matching method: Application to image-based modeling[END_REF]. These sources generate 3D points according to certain rules, such as following branching structures in trees, or sampling the surface of a polygon. The same manipulation as above is used to select the 3D location of a source, but we also consider the color of this 3D point (or colors of 3D points around it) as a color criteria to flood fill the 3D space. The location of 3D points are therefore generated by the flood fill algorithm. A direction will only be visited recursively if its generated 3D point is considered plausible.

Another filling tool consists in displaying the current point set from the virtual camera, and then to try to generate a 3D point in each empty pixel. 3D points are generated along the line of sight of the pixel until a validated point is found (up to a maximum number of attempts).

Jittering Tool

In a loop, we randomly select a 3D point and apply a small user-specified random perturbation (jittering) on its location. We reevaluate its plausibility and keep its new location if its plausibility increases. In practice, this process improves the point set. In the example of Fig. 1, we applied jittering (about 0.1% of the object size) to the point set (h) for 3 min to result in the new point set (i). In the beginning, 15% of the perturbations improve the plausibility, after 3 min the fraction decreased to 2%, illustrating that the set of 3D points quickly settles to a stable configuration, and it becomes less interesting to use jittering after this point.

Merging Tool

The random nature of our 3D point generation as well as the interactive refinements can result in a large number of 3D points within a very constrained neighborhood. The user can reduce this set by clustering 3D points within a specified distance and selecting the best representative(s) according to the color distances and distribution within each cluster. This is implemented by placing a voxel grid of specified resolution into the envelope and keeping the best 3D point(s) inside each voxel, or merging the 3D points inside the same voxel according to various criteria (color and spatial distances). This allows us to reduce the point set to different point densities in different portions of the 3D model.

Display

To display the reconstructed object, we use OpenGL's GL POINTS primitive. With vertex arrays, we achieve a rate of 6 million colored 3D points per second on an nVIDIA GeForce3, which is enough to render complex objects in real-time, giving the user immediate feedback on the current progress of the reconstruction.

Texture reprojection produces higher quality results. We render the point set and read back the depth buffer. For each pixel P , we then reconstruct the corresponding 3D position p and look for the camera that sees p from the angle closest to the current view. We then project p into this view, read the corresponding pixel color and write it into the frame buffer pixel P . This is a simplified version of previous approaches [START_REF] Debevec | Modeling and rendering architecture from photographs: A hybrid geometry-and image-based approach[END_REF][START_REF] Buehler | Unstructured lumigraph rendering. A: Fruit bowl[END_REF], using only the angular criterion, which is reevaluated per pixel. This step could be optimized, but with our current implementation we already achieve about 2 frames per second, depending on the image size.

Results

Various results of our system are provided in this section, as well as on an accompanying video available from the web site associated with this paper [31].

Synthetic Objects

Synthetic objects can help better understand the behavior and limitations of our algorithms because of the more controlled environment. In Fig. 4A, purely diffuse textured surfaces are rendered with a standard ray tracer at resolution 512 × 512; we know the exact camera parameters. Fig. 4A(bottom) shows a novel view not contained in the original images: (left) a ray traced image of the original objects, (center) the directly rendered point set (more than 30 fps on a GeForce3), and (right) the point set rendered with texture reprojection (software solution at 1.5 fps).

Soldier and Snack

Figs. 4B and4C show two further test objects from real scenes. The soldier (Fig. 4B) exhibits smooth surfaces, but also difficult thin structures (flag post) for the automatic generation of our system. The snack (Fig. 4C) has complex (ham) and smooth (plate, cheese, mushroom) surfaces with limited shading, while the grapes are glossier.

Synthetic Trees

To illustrate the efficiency of our simple algorithm to fill 3D samples according to special structures, we produced 10 images of a synthetic tree from our implementation of an L-system. In Fig. 3(left), selecting one of the 62 randomly generated points as the seed to our 3D space filling algorithm, produces 15,562 points of the selected color filling the branches in 10s. Because of remaining variations in quantized colors of the images (resulting from shading and antialiasing in the original images), the space filling does not reach the tip of the branches. Selecting a set of colors (instead of a single one) easily helps to fill the rest of the branches. The resulting points are displayed on top of a semi-transparent input image.

In Fig. 3(right), we show the impact of occlusions by leaves. In the rightmost image, after 8,553 points were generated in 7s with our filling algorithm, 11,081 additional points were randomly distributed to fill mostly leaves in about 7 min.

A Comparison with Voxel Coloring

The flexibility of our interactive system and our pointbased representation allows easy integration with other algorithms. We implemented a simplified version of voxel coloring [23,[START_REF] Kutulakos | A theory of shape by space carving[END_REF]. Voxel coloring requires the reconstructed 3D objects to lie outside the convex hull formed by the cameras, which is the case in the scene of Fig. 1. Instead of carving out voxels, we simply generate points in a rectangle, and process several such rectangles in front-to-back order, thus filling a 3D grid of points. Our depth maps are computed after each such rectangle filling through the 3D grid, and we use our color comparisons. We compare the results in Fig. 4D.

Voxel coloring demonstrates its efficiency due to coherence. The example shows that our approach can lead to similar results, but we have the advantage of being able to interact with the generation process at any point in time.

However, our interactive tools permit direct integration of other generation algorithms. In the accompanying video [31], we show how we use voxel coloring to generate an initial point set and then improve the result using our interactive tools.

Additional advantages of our random-point generation compared to a regular approach are its flexibility and the fact that randomly distributed points can deliver a more desirable visual effect for point-based rendering.

Conclusions

In this paper, we have presented our interactive system to extract complex objects from images. One major contribution of this system is the central control offered to the user. A set of interactive tools allow the user to guide more automatic reconstruction techniques where details are needed, or neglect regions of unnecessary difficulties. A typical interactive session using the system allows the user to stop a process, modify a value, select another al- gorithm, merge/refine/revalidate the current result, undo an unsatisfying partial result, etc., each time visualizing the objects being reconstructed in 3D at interactive rates.

The second essential contribution of our system is the use of a point-based representation, which can efficiently display complex and partially reconstructed complex objects. Thanks to this efficient rendering process the user can interactively visualize the behavior of the extraction process, and modify or guide it when necessary. A 3D point is simple and its reconstruction does not require any additional constraint on surfaces, neighborhood, or smoothness. Occlusions between 3D points are also well treated with simple depth maps. Finally, synthetic objects composed of 3D points are easy to integrate within most rendering systems, up to the quality limit of the actual point representation.

By tightly integrating these two key concepts (user interaction and point representation) into our system, it offers a very flexible platform to extract complex objects. Its flexibility also allows interactive experimentation to understand the limits of certain algorithms, and to design new solutions to the challenging problems of modeling from images. We designed our system with this simplicity in mind. Many of our solutions are built on mature techniques, such as color comparisons, camera calibration, 3D space filling, depth maps, 3D point jittering and clustering, texture reprojection, etc. We did not implement more sophisticated techniques because our emphasis was on implicating the user in the process. The advantage is that any improvement to the techniques used could be easily integrated in our system, leading to equivalent improvements in the results. One important source of improvements, as demonstrated in our limited implementation, should come from a tighter integration of our interaction techniques with the space carving literature [23,[START_REF] Kutulakos | A theory of shape by space carving[END_REF][START_REF] Dyer | Volumetric scene reconstruction from multiple views[END_REF][START_REF] Slabaugh | A survey of volumetric scene reconstruction methods from photographs[END_REF].

Future Work

In its current state, the realism of the objects modeled by our system is very promising, but it is not entirely satisfactory for photorealistic applications. Often, our objects are reconstructed to a given level of quality, but automatic algorithms also seem to settle near this level. User intervention can further improve the model quality but achieving full photorealism is very challenging. In fact in general, we are fundamentally limited by the quality and resolution of the original images. Moreover many other factors other than color and geometry must be extracted from the images to achieve full photorealism.

Nevertheless, there is much room for improvement. We plan to improve the two following aspects in our system. Firstly, our color matching assumes very limited BRDFs, close to lambertian. Shadows and shading variations should be integrated within our color matching test. Other criteria, such as mirror reflection and transparency, could also be integrated into the matching process. Secondly, the information of the original images could be increased with video sequences and high dynamic range images.

1 .• 4 .

 14 Initialization: (a) Take photos (images) (b) Calibrate the images (c) Define a 3D zone of interest (envelope) (d) Draw a mask for each image (optional) 2. Generation Loop: (a) Generate a random 3D point within the zone of interest (b) Validation of 3D points: (i) Project the 3D point into each image; gather its associated colors from every visible image (ii) Keep the 3D point if the color distances are below a threshold in a (user controlled) sufficient number of images (c) Visibility: From time to time, recompute a depth map for each image from the set of 3D points 3. Interactive Cleanup: • Cleanup by reevaluation (a) Interactively increase the value of sufficient number, recompute depth maps (b) Discard the 3D points failing the new criteria (sufficient number and depth maps) Cleanup by rendering: For each view (i.e., original image): (a) Generate an image of the set of 3D points from this view (b) Compare the pixel colors in the original image with those in the generated image (c) Discard the 3D points resulting in incorrect image pixels User-directed Refinement Loop:

a) 4 Figure 1 :

 41 Figure 1: Typical interactive modeling session, using our system.

Figure 2 :

 2 Figure 2: Plausibility tests for points A, B, and C.

Figure 3 :

 3 Figure 3: Synthetic tree with/without leaves. 10 original images of resolution 640×443 quantized to 50 colors; (left) 62 random points, the seed of our filling algorithm (yellow sphere); 15,562 points filled in 10s. (right) 147 random points, seed of filling algorithm (yellow sphere); 19,639 points filled more occluded branches with leaves in 7 min.

Acknowledgements

Financial support for this work was provided by an IN-RIA invited professorship (P. Poulin), a Marie-Curie postdoctoral fellowship (M. Stamminger), and FCAR graduate (F. Duranleau) and doctoral (M.-C. Frasson) scholarships.


Katrien Jacobs

Cameron Angus

Celine Loscos

Jean-Daniel Nahmias

Alex Reche

Anthony Steed

Automatic generation of consistent shadows for Augmented Reality

Keywords: Augmented reality, image based rendering, common illumination

In the context of mixed reality, it is difficult to simulate shadow interaction between real and virtual objects when only an approximate geometry of the real scene and the light source is known. In this paper, we present a realtime rendering solution to simulate colour-consistent virtual shadows in a real scene. The rendering consists of a three-step mechanism: shadow detection, shadow protection and shadow generation. In the shadow detection step, the shadows due to real objects are automatically identified using the texture information and an initial estimate of the shadow region. In the next step, a protection mask is created to prevent further rendering in those shadow regions. Finally, the virtual shadows are generated using shadow volumes and a pre-defined scaling factor that adapts the intensity of the virtual shadows to the real shadow. The procedure detects and generates shadows in real time, consistent with those already present in the scene and offers an automatic and real-time solution for common illumination, suitable for augmented reality.

Introduction

A wide range of applications use computer-generated animations in combination with pictures or footage of real scenes. Examples of such mixed reality applications are manufacturing, medical training, medical surgery, entertainment, education or cultural heritage. Some (e.g. surgery [START_REF] State | Case study: Observing a volume-rendered fetus within a pregnant patient[END_REF]) require that the inclusion of the virtual elements in the real scene is instantaneous, without preprocessing time and without having a model of the real scene. This implies numerous calibration and registration problems when inserting the virtual elements [START_REF] Azuma | A survey of augmented reality[END_REF][START_REF] Azuma | Recent advances in augmented reality[END_REF]. Others (e.g. cultural heritage [START_REF] Loscos | The create project: Mixed reality for design, education, and cultural heritage with a constructivist approach[END_REF]) allow pre-processing and use a reconstruction model of the real scene, allowing a more accurate calibration and registration of the virtual elements within this model.

Important progress has been made in registration and calibration [START_REF] Azuma | Recent advances in augmented reality[END_REF][START_REF] Lepetit | Fully automated and stable registration for augmented reality applications[END_REF]. However, the rendering of the virtual objects within the real scene often remains inconsistent: their illumination is different from that of the real objects. Few attempts are made to understand the current lighting in order to compute the shading. It is clear that a consistent illumination improves the overall impression of the mixed reality. First, a consistent shadow of the virtual objects gives a correct interpretation of the relative distance between the virtual objects and the real objects. Second, a correct lighting enhances the feeling that the virtual objects are part of the real scene.

Since the early nineties [START_REF] Jacobs | Classification of illumination methods for mixed reality[END_REF] a few solutions for the illumination inconsistency have been proposed. Most of them assume that a model of the real scene is available. This reconstruction can be obtained with a scanner, but most commonly real scenes are reconstructed using photographs from different viewpoints [START_REF] Poulin | Interactively modeling with photogrammetry[END_REF][START_REF] Debevec | Modeling and rendering architecture from photographs: A hybrid geometry-and image-based approach[END_REF]21,[START_REF] Renoir | [END_REF][START_REF][END_REF]8]. The latter is a photogrammetric, error prone process as the reconstruction usually contains a mismatch between the simplified geometry and the texture. Due to the various errors, shadows generated using the approximated geometry and light source position may not align with the shadows visible in the texture.

Figure 1: Virtual model obtained using stereopsis. Left: outdoor scene set-up. Middle: reconstructed geometry. Right: geometry and texture combined, the shadow is visible in the texture. A clear mismatch between geometry and texture is visible, the curved shape of the shadow indicates that the geometric model is inaccurate.

In Figure 1 (Middle) an example is shown of the 3D reconstructed model of a real object photographed in a real outdoor environment (Left). The reconstructed geometry is a fair but simple approximation of the real shape that consists of many curved surfaces. A clear mismatch between texture and geometry is visible (Right). Due to the misalignments resulting from the reconstruction, it may not be straightforward to extract the illumination properties accurately [START_REF] Patow | A survey on inverse rendering problems[END_REF]. One can spend more time on the geometry reconstruction or use a more accurate geometry reconstruction procedure (e.g. laser) to guarantee that all geometry parameters are exact, but this adds an overhead cost to the application. In this paper a new procedure is presented that offers a solution for rendering consistent shadows in real time for mixed reality, regardless of the quality of the geometric reconstruction.

Related work

Jacobs et al. [START_REF] Jacobs | Classification of illumination methods for mixed reality[END_REF] provid a classification of the illumination methods for mixed reality. The methods for consistent rendering can be classified in two categories: common illumination and relighting. Common illumination simulation provides a consistent lighting when virtual objects are inserted in a real context. Relighting goes one step further and enables the modification of the original illumination. Using inverse illumination [START_REF] Patow | A survey on inverse rendering problems[END_REF] is one way to achieve common illumination or relighting. This refers to the retrieval of the illumination parameters such as the BRDF of the objects in the real scene. In the classification of Jacobs et al. [START_REF] Jacobs | Classification of illumination methods for mixed reality[END_REF], some methods provide a real-time rendering for common illumination [START_REF] Bimber | Consistent illumination within optical see-through augmented environments[END_REF][START_REF] Agusanto | Photorealistic rendering for augmented reality using environment illumination[END_REF][START_REF] Haller | A real-time shadow approach for an augmented reality application using shadow volumes[END_REF][START_REF] Gibson | Rapid shadow generation in real-world lighting environments[END_REF]. However to our knowledge no method has yet been proposed that provides a real-time illumination estimate. Most of the time, a lot of effort is spent in the pre-computation step to find an accurate model of the real scene and the lighting properties via inverse illumination methods. After the geometry is captured, the pre-computed set up usually takes a minimum of a few minutes to several hours.

Illumination methods in computer graphics can consider local and global illumination. Local illumination effects simulate only the direct effects due to a light source, global illumination deals with the inter-reflections between objects as well. While it is important to consider the global effect of an added virtual object, local illumination is essential, especially for shadows. Recent developments provide the possibility of simulating shadows at low cost, using for example shadow maps [START_REF] Blinn | Me and my (fake) shadow[END_REF] or shadow volumes [START_REF] Crow | Shadow algorithms for computer graphics[END_REF]. A recent survey [START_REF] Hasenfratz | A survey of real-time soft shadows algorithms[END_REF] presents the classification of soft shadow methods that could be used in the context of mixed reality. State et al. [START_REF] State | Superior augmented reality registration by integrating landmark tracking and magnetic tracking[END_REF] demonstrate the use of shadow maps in an augmented reality system. To achieve a similar effect Haller et al. [START_REF] Haller | A real-time shadow approach for an augmented reality application using shadow volumes[END_REF] use shadow volumes. While these two methods showed impressive improvement in the capability of registration, overlap between virtual and real shadows were avoided. Gibson et al. [START_REF] Gibson | Rapid shadow generation in real-world lighting environments[END_REF][START_REF] Gibson | Interactive rendering with realworld illumination[END_REF] developed two methods for simulating soft shadows of virtual objects in complex mixed reality environments. While the rendering of the shadow is interactive, the method requires accurate input geometry and a good estimate of the BRDF and original illumination.

From the examples shown in the papers, it is also not clear if the overlap between real and virtual shadows are handled. The method presented in this paper provides a real-time system both for processing the original shadow regions due to real objects and rendering new shadows due to the insertion of virtual objects. Therefore overlap between real and virtual shadows are treated and the shadows of virtual objects due to a real light source are consistent with the shadows of real objects.

Method overview

In this paper, a solution is presented to provide consistent shadows between virtual and real objects for a scene with one main real light source. The geometry of the considered real objects and the position of the real light source only need to be known approximately. Algorithms such as State et al. [START_REF] State | Superior augmented reality registration by integrating landmark tracking and magnetic tracking[END_REF] or Haller et al. [START_REF] Haller | A real-time shadow approach for an augmented reality application using shadow volumes[END_REF] to render the shadows of the virtual objects, provide a solution similar to the one shown in Figure 2(a), where the shadows of the virtual objects (virtual avatar and box) lie correctly on the ground as expected, but overlap incorrectly with the shadow of the real statue due to a real light source. The correct result should be as in Figure 2(c) which is computed using the algorithm presented in this paper.

When the virtual shadow is rendered using shadow maps or shadow volumes, those pixels that lie inside the virtual shadow have their intensity scaled using an appropriate scaling factor. When virtual and real shadow partially overlap one need to decide how to select the scaling factor. If the scaling factor is 1 (no scaling), those pixels in the overlapping part have a colour consistent with the real shadow pixels, the non-overlapping pixels, however, will be brighter than required for a consistent shadow. If the scaling factor is smaller than 1, the pixels in the non-overlapping areas will have a colour similar to that of the real shadow pixels, but the pixels in the overlapping area will be too dark, making the shadow, again, inconsistent. Based on this information, a three-step mechanism is designed and each step is briefly discussed here; a schematic overview is given in Figure 3.

The shadow detection step, deals with the detection of the position and shape of the real shadows of the real objects in the scene, conform with the texture of the real scene. It takes as input the scene geometry, its texture and an approximation of the light source position present in the scene. First a shadow contour estimate is calculated using the geometry and the light source position. Due to the reconstruction errors, mentioned in the introduction, and the error in the registration of the light source in the scene, this estimate deviates from the shadows visible in the texture. Next, the exact shadow contour is extracted, for instance by using a Canny edge detector [START_REF] Canny | A computational approach to edge detection[END_REF] in a region defined by the shadow contour estimate.

(a) (b) (c) (d)
Once the true shadow contour is known, it is possible to calculate a scaling factor per material in shadow that reflects the colour intensity in the shadow region. This factor relates the colour of the material in shadow with the one not in shadow. A more detailed explanation of the shadow detection step is given in section 2.

In the shadow protection step, a binary shadow mask is created that is used to protect those points inside a real shadow from any scaling. The scaling factor is chosen to match the colour of the non-overlapping areas with the points inside the real shadow. If the geometrical estimate is used to protect the real shadow points, this results in a misalignment of the shadow mask with the real shadow as can be seen in Figure 2(b). When the output of the shadow detection step is used to complete the shadow mask, all points inside the real shadow are correctly blocked from further rendering: the resulting virtual shadow is consistent, see Figure 2(c). More details about the shadow protection step are given in Section 3.

In the shadow generation step, a real-time shadow method such as shadow maps or shadow volumes is used to generate the virtual shadows. The intensity of the shadow relates to the appropriate scaling factor computed previously; overlap between real and virtual shadows is prevented by using the mask generated in the previous step. Those parts of the virtual shadow that lie inside a real shadow are ignored. The intensities of the pixels in the virtual shadow in the non-overlapping regions are calculated by scaling the texture colour with the scaling factor. The influence of the choice of the scaling factor is illustrated in Figure 2(c) and 2(d). During the rendering, a different scaling factor needs to be used for different materials and for polygons with a different orientation towards the light source. Section 4 provides more details about this third and final step.

After presenting the three-step method, the performance of the system is illustrated using various scenes in a different context in Section 5, followed by a conclusion in Section 6.

Automatic shadow detection 2.1 Shadow contour detection

In order to protect the existing shadows in the scene from any post-processing, the shadow pixels in the texture need to be identified. Two types of shadows exist: soft shadows and hard shadows. Ideally both types of shadows are detected, but in practice it is much easier to detect hard shadows. This paper does not aim at developing a new state of the art shadow detection method but instead claims that the three-step mechanism is independent of the choice of shadow detection in this first step. In this paper a hard shadow detector is implemented. Hard shadows appear in scenes with bright light sources, e.g. sunny outdoor scenes, indoor scenes with one main light source. The presented shadow detector has been tested in both types of scenes with good results. However, it should be stressed that if a soft shadow detector is used the method can be applied on less restricted scenes.

A Canny edge detector [START_REF] Canny | A computational approach to edge detection[END_REF] is implemented to detect shadow contours in a similar approach as in [START_REF] Bevilacqua | Effective shadow detection in traffic monitoring applications[END_REF][START_REF] Salvador | Shadow identification and classification using invariant color models[END_REF][START_REF] Salvador | Cast shadow segmentation using invariant color features[END_REF]. The main advantage of the Canny edge detector is that it returns one-pixel thick edges and that it effectively neglects edges due to noise because of the non-maximal suppression and hysteresis. The shadow detector uses a geometric estimate of the shadow contour to generate the contour of the real shadow. The geometric estimate of the shadow contour comes from the generated shadow computed from the approximate geometry and the light position. In general the shadow estimate gives a good indication of the position of the real shadow, but it can be inaccurate due to the error of the estimated light source position within the scene and the geometric approximation of the real scene geometry. An example of input and output of the Canny edge detector is given in Figure 4. This type of shadow edge detector guarantees a correct shadow contour detection when:

1. The position of the geometrical estimate is close to that of the real shadow, regardless of the difference in shadow shape or detail.

2. The shadow is a hard shadow or a soft shadow that shows a relatively high contrast with the background.

3. The contrast of the shadow and the background is larger than the contrast in the texture pattern of the background. Using an appropriate choice of the size of the smoothing filter and the upper and lower thresholds, the edges of the background texture will be suppressed against the edges of the shadow.

Usually an edge detector can only detect hard shadows and give a rough estimate of a soft shadow contour as long as the gradient of the soft edge is larger than the gradient of any other underlying structures in the texture. When the parameters of the edge detector are tuned to detect the soft edges, the amount of false edges due to noise for instance, increases as well. This restriction to hard shadows might be a limitation of the presented technique, since true hard shadows are rare in nature. Nevertheless, a pseudo-shadow detection algorithm is implemented with satisfying results, as is explained in Section 3. The pseudo-soft shadow detector achieves good results on outdoor sunny scenes and indoor scenes where the main light source is a spotlight directed onto the objects under consideration, this is discussed in Section 5.

The computation speed of the shadow edge detector depends on the resolution of the input image. Since the most time consuming operations are the smoothing and gradient convolutions these can be implemented in the fourier domain, hereby decreasing the computation time. However, this is not implemented since the search window in which the edge detector operates is already drastically reduced by limiting the search to a region around the geometrical estimate of the real shadows. In other words, the computation speed rather depends on the size of the real shadows. When the real shadows cover a large region in the image, one can argue that the shadow edge detector might not operate in real time. But even in this case the size of the search window can be reduced if we consider only the region where real and virtual shadows overlap. In all experiments carried out, the shadow detection operated in real time (30 frames per second).

Automatic estimate of the shadow intensity

Once the shadow edge is defined, it is possible to calculate a scaling factor for each material in shadow. The scaling factor is in fact a triplet [ρ R , ρ G , ρ B ], defined by dividing the three colour channels of the pixels inside the shadow with those outside the shadow. In the current implementation, a small region of pixels inside and a small region of pixels outside the shadow were selected and used to derive a mean scaling factor. The follow-ing equation explains how the triplet is calculated. C = {R, G, B} represents the colour channel: red, green or blue; SR stands for shadow region, while N SR stands for non shadow region; P SR and P N SR are the number of pixels in respectively the shadow and non shadow region:

ρ C = ∀p∈SR Cp P SR ∀p ∈N SR C p P N SR
The colour of the virtual shadow is now defined by the multiplication of the underlying texture value and the scaling factor. In general this scaling factor varies across the points on a surface, and depends on the orientation of that surface to the light source. Though it would be better to assign a scaling factor per pixel, only one scaling factor was used per material, but it has been identified that a better scaling factor selection procedure needs to be implemented for future applications.

Shadow protection

Based on the shadow contour, a binary mask is constructed. This mask is used to indicate which points in the real model are in shadow or not. In a way, it can be considered as a texture map that overlays the textures of the scene. The output of the shadow detector is an edge image, containing information about the shadow contour, at pixel level (see Figure 4, Right). Since the Canny edge detector detects edges of one-pixel thickness and removes most noise inside the image, the shadow region can be derived relatively easy: the shadow mask construction takes the edge map as input and uses a region growing algorithm to fill the shadow region inside the shadow contour. The starting point of the region growing can be any point inside the shadow region, which can be derived from the shadow estimate. An example of a shadow mask is given in Figure 5 (Left). The edge detector can only detect hard shadows. Nevertheless the creation of a pseudo-soft shadow mask enables the use of the presented method on soft shadows.

As is illustrated in Figure 5 (Right), a grey-level shadow mask is constructed with values ranging from 0 to 1 instead of a binary one. Those pixels inside the shadow are entirely protected (bright), the pixels outside the shadow are not protected (dark), the pixels at the shadow edge are partially protected (gradient grey level). The gradient in the soft region is quadratic to reflect the visibility variation in respect to an area light source. The support of the quadratic gradient increases with the degree of softness. This can be estimated if the distance of the light source and its area are approximately known. For instance for an outdoor scene, on a sunny day it is known that the sun has a solid angle of 0.5 degrees. Together with the geometry estimate and the direction of the sunlight an approximation of the degree of softness can be calculated . In the other cases, one can use the behaviour of the pixel intensities around the detected shadow edge. Up till now, the degree of softness has been defined manually.

The design of a shadow mask allows any upgrade of the system to soft shadow detection once an implementation is provided to detect soft shadows at pixel level. For each pixel a grey level can be written in the shadow mask, that indicates how much light it still receives, without modifying the shadow generation step.

Shadow generation

Once the real shadow regions are identified, it is possible to simulate the shadows due to the insertion of the virtual objects. These shadows can be generated with different algorithms. In the current implementation, shadow maps and shadow volumes are used, but any other realtime shadow generation procedure, including soft shadows, is suitable. The shadows are computed using the approximate position of the real light source and consider the interactions between virtual and real objects. Shadows from virtual objects are therefore cast on real and virtual objects, and real objects can cast shadows on virtual objects. Shadows due to real objects onto other real objects are already included. The intensity of the shadows are estimated using the scaling factor as computed in Section 2.2. This scaling factor differs for each object on which the shadow is cast. It should reflect both the material properties and the ambient light received in each region.

In order to prevent any overlap between the generated shadows and the real shadows the shadow mask computed in Section 3 is used to indicate the regions that can be drawn in the colour buffer. Regions with zero values (dark) in the shadow mask, can be overdrawn and regions with one values (bright) are fully protected. Regions with grey level values are partially protected. We use the shadow mask in two different ways. When a textured model of the real scene is available, the multitexturing capability of OpenGL is used to multiply the original texture and the shadow mask texture. When AR-ToolKit is used, we draw the shadow mask directly in the stencil buffer. In this implementation each (visible) scene point needs to have one entry in the shadow mask.

An alternative implementation could pass a geometrical shadow mask instead of the texture mask in the stencil buffer. The geometric mask can be created by representing the edges of the shadow contour as found in the shadow edge detection step analytically. However the texture mask ensures that complex shapes can easily be dealt with. For a more complex scene for which texture memory is an issue, a geometric mask can be extracted from the shadow detection and used in the stencil buffer.

Results

The presented method has been tested in two different contexts. One is computer augmented reality where a textured model representing the reality is used and the shadow detection is carried out offline. The other is augmented reality using a pre-estimated geometry of the real scene and texture information from a video camera. In both cases the interactions of the virtual objects are computed in real time.

Computer augmented reality

Figure 2 (c) already showed the result of the presented method on an outdoor scene using a pseudo-soft shadow map. Another example of a more complex scene is given here. A geometric model, shown in Figure 6 (a), was reconstructed from photographs of a real scene, see Figure 6 (b), using [START_REF][END_REF]. It is a fairly simple geometric model but it contains many different objects that cast shadows on different, sometimes textured materials. The scene was illuminated by a spotlight to create distinct shadows with a low degree of softness created by the indirect sunlight coming through the windows, see Figure 6 (b). Once the edge detector is used to find shadow edges, a shadow mask with soft borders is constructed as explained in Section 3.

Figure 6 (c)(d) illustrate the shadow protection and generation, using the calculated shadow masks shown in Figure 6 (f), when two virtual objects (a floating box and an avatar) are added to the scene. Figure 6 (e) gives a closeup of the shadow protection. It is clear that the smoothness introduced in the grey-level shadow mask is not sufficient to compensate for the soft shadow edges, but the approximation is of such quality that the user can hardly detect the shadow border when an appropriate scaling factor is used.

In this type of application, the light source position cannot change, since the texture information is only known for one distinct light source position. There is however no restriction on the viewpoint position.

Real-time application using ARToolkit

The second experiment uses ARToolkit [START_REF] Kato | Artoolkit[END_REF] to perform real-time tracking of the camera. While the camera captures the scene, a virtual avatar walks across the real shadow borders. The virtual shadows of the avatar are rendered consistently within the real scene, using the scaling factor and the shadow mask calculated after the real-time shadow detection. In the same manner, the avatar receives shadows from the real object. The camera calibration is updated every frame and therefore the shadow mask also needs to be updated every frame, rather than calculating it once and incorporating it into the scene geometry.

The illumination sources in the scene are the light coming from the windows in the room and a spotlight di- rected to the real objects under consideration, to enhance the sharpness of their shadows. No further action has been undertaken to create more beneficial environment influences and therefore the shadows are not hard shadows. An example of the original scene and the process of the shadow detection and masking is shown in Figure 7 (a)(b), the projection of the known geometry is overlaid on the image. The computation of the shadow region using only the geometric position of the light source and the model is shown in (c). The position of the shadow at this stage is incorrect compared to the real shadow. In (d), the edge detection is shown. A search region, constructed from (c) is shown in (e). The shadow extracted from the region in (e) using our algorithm is shown in (f).

In Figure 8 examples of the shadow generation are shown with a virtual avatar walking around the computer.

The program runs at 15 to 30 frames per second on an input image of 320x240, and 10 to 15 frames per second on an input image of 640x480. These timings were recorded on a HP 3000+ Athlon with a GeForce FX 5950 Ultra. These timings include all computations and the camera capture at each frame; except for the geometry extraction and the light source registration no pre-computations are made. It is important to notice that only a rough estimate of the shadow region is needed. The light source can be physically moved around its original position without making a position update in the system. The shadow detector has no problem with tracking the modified shadow position. The new position of the shadow can be used to track the position of the light source but this is currently not implemented.

Conclusions and future work

A real-time algorithm was presented that offers a consistent shadow simulation for mixed reality applications. There are three requirements for a successful shadow detection and generation: the geometry and the light source position need to be known approximately and only hard or semi-soft shadows are allowed.

The method consists of a three-step mechanism: shadow detection, shadow protection and shadow generation. This three-step algorithm generates consistent shadows between real and virtual objects in real-time. This allows the use of the presented method in augmented reality applications. Even though the shadow detection is not implicitly made for soft shadows, the experiments carried out show that the method manages to detect the shadow contours. To our knowledge no such real-time and automatic algorithm has been presented before that treats overlapping shadow regions between virtual and real objects.

We have shown results in two different contexts: com-puter augmented reality and augmented reality. Further efforts need to be undertaken to scale the method to more complex environments. We will also search for ways in making our algorithm more robust for any types of soft shadows.

In this paper, we have considered only one light source and we have ignored the overall lighting conditions. It is therefore possible that the shadow of a virtual object falls on a highlight making the blend unrealistic. In future work we would like to provide a more general algorithm that will adapt to several light sources and compensate for illumination effects.

Figure 2 :

 2 Figure 2: (a) Generation of the virtual shadows using one scaling factor. (b) Pixels inside the geometrical estimate of the real shadow are protected against the scaling. Due to misalignments not all pixels of the real shadow are protected.(c) When using an appropriate scaling factor and protecting the shadow pixels identified by the shadow detection step, the virtual shadows are consistent with the real shadow. (d) The virtual shadow is inconsistent with the real shadow when an inappropriate scaling factor is used.

Figure 3 :

 3 Figure 3: Three-step mechanism: a schematic overview of the three steps and their interaction.

Figure 4 :

 4 Figure 4: Left: the input texture image of the shadow detector. Right: based on a geometrical estimate, the shadow contour visible in the texture is extracted.

Figure 5 :

 5 Figure 5: Left: close-up of a pseudo-soft shadow grey level mask, the gradient of the border protection is quadratic. Right: a binary shadow mask.

Figure 6 :

 6 Figure 6: (a) The geometry extracted. (b) Scene set-up. (c), (d) Addition of two virtual objects (floating box and an avatar) in the scene projecting shadows onto the captured real objects. (e) A closeup view of the shadow of the box on the wooden shelf, interacting with real shadows. (f) The shadow masks projected on top of the geometry, white indicates that the pixels are in shadow.

Figure 7 :

 7 Figure 7: (a) A picture of the real scene set up. (b) The projection of the reconstructed laptop using ARToolKit. (c) Shadow as computed using the geometry input is shown in yellow. There is a clear mismatch with the real shadow. (d) Result of the edge detector. (e) Search region extracted from the shadow in (c), in which the shadow region detection is performed. (f) Result of the shadow mask generation.

Figure 8 :

 8 Figure 8: Results of the algorithm for an animated virtual avatar walking around a real laptop. Shadows are automatically detected and generated using our real-time algorithm.

Acknowledgements

This project was partly funded by CREATE (IST-2001-34231), a 3-year RTD project funded by the 5th Framework Information Society Technologies (IST) Programme of the European Union, and by the UK's EQUATOR Interdisciplinary Research Collaboration (EPSRC Grant GR/N15986/01).