Adrien Bousseau

Emmanuelle Chapoulie

Ravi Ramamoorthi

Maneesh Agrawala

Optimizing Environment Maps for Material Depiction

a) Our optimized lighting emphasizes materials (b) Poor lighting de-emphasizes materials

Figure 1: Our method (a) automatically optimizes the lighting to enhance material-specific visual features. The lighting reveals the thin and thick parts of the subsurface scattering wax candle, it accentuates the Fresnel reflections along the side of the porcelain vase and it adds strong specular highlights to emphasize the shiny chrome metal of the sculpture. Poorly designed lighting (b) diminishes these characteristic visual features of the materials. The candle appears more like solid plastic, the vase appears to be made of diffuse clay and the sculpture no longer looks like it is made of chrome.

Introduction

Shading, reflections and refractions are important visual features for understanding the shapes and materials in an image. While well designed lighting configurations can enhance these features and facilitate image perception, poor lighting design can lead to misinterpretation of image content. In Figure 1a for example, the lighting enhances the thickness variations in the subsurface scattering wax candle, it accentuates the Fresnel reflections at grazing angles of the porcelain vase and it adds strong edges in the specular highlights of the chrome sculpture. In Figure 1b however, poor lighting greatly reduces these visual features and makes it more difficult to correctly identify the materials.

In applications such as product design and advertising, lighting is often carefully configured to best depict the material properties of the objects. Such manual lighting design is difficult and requires a deep understanding of the way light interacts with shapes and materials. Manual lighting design is also prohibitive for large databases of 3D models. As an example, a search for "car" in Google Warehouse leads to more than 38000 models, and most of them are lit by a single canonical light source. While automatic lighting design techniques can place a few point lights to enhance shape depiction [START_REF] Shacked R | Automatic lighting design using a perceptual quality metric[END_REF][START_REF] Gumhold | Maximum entropy light source placement[END_REF][START_REF] Lee | Agrawala / Optimizing Environment Maps for Material Depiction dependent lighting[END_REF], the resulting lighting lacks the visual richness of natural lighting environments that have been shown to improve materials depiction [START_REF] Fleming R | Realworld illumination and the perception of surface reflectance properties[END_REF].

In this paper we present the first automated system for optimizing and synthesizing environment maps that emphasize distinctive visual features of the materials in a scene. Our system focuses on material depiction and does not address other goals of lighting design such as overall aesthetic and composition that represent challenging directions for further research. Our work makes three primary contributions:

1. Lighting design principles for material depiction. We have analyzed books on studio photography [START_REF] Montizambert | Creative Lighting Techniques for Studio Photographers[END_REF][START_REF] Hunter | Light: Science and Magic: An Introduction to Photographic Lighting[END_REF] and studies of material perception [PFG00, FDA03, KP03, FJB04, FTA04] to identify distinctive visual features due to lighting, for a variety of materials including glass, metal, plastic, marble and velvet. We derive a set of design principles that an environment map should fulfill in order to emphasize these visual features and effectively depict the materials in the scene (Section 3). We express each design principle in the form of a simple image quality metric that quantifies how well a given rendering of the scene conveys the desired visual features (Sections 4.2 and 4.4).

2. Optimization framework. We introduce a general optimization framework to solve for the environment map that maximizes our image quality metrics (see Figures 3, 4 and5). We express the metrics within this framework as either linear or quadratic combinations of the image radiance values (Section 4). The key idea of our framework is to preintegrate the light transport over the image domain in order to significantly accelerate the optimization. Our approach can be seen as a dual to precomputed radiance transfer methods [START_REF] Kautz | Precomputed radiance transfer for real-time rendering in dynamic, lowfrequency lighting environments[END_REF][START_REF] Ng R | Allfrequency shadows using non-linear wavelet lighting approximation[END_REF] that integrate the light transport over the lighting domain to efficiently render an image.

3. Environment lighting synthesis. While our method can directly generate the optimal lighting for a given set of image metrics, this result may not match the appearance and spatial statistics of a natural environment. We suggest two methods to transform any existing photographic environment map (Section 5). In the first approach (Figures 789) we search for the optimal orientation of the map and show how to accelerate this search using spherical harmonic rotations [START_REF] Makadia | Direct 3d-rotation estimation from spherical images via a generalized shift theorem[END_REF][START_REF] Ramamoorthi R | A signalprocessing framework for reflection[END_REF]. In the second approach, we use constrained texture synthesis [START_REF] Ashikhmin | Synthesizing natural textures[END_REF] to combine the color and details of the photographic environment map with the luminance variation of the optimal lighting (Figures 11).

Related Work

Automatic lighting design. Researchers have developed a variety of techniques for optimizing lighting to enhance shape [SL01, Gum02, LHV06, RBD06, VPB * 09]. While our system also optimizes lighting, we focus on enhancing the visual features that emphasize materials rather than shape. In addition, our system generates complex environment lighting rather than a small set of point lights. In the context of material depiction, Gooch et al. [START_REF] Gooch | A non-photorealistic lighting model for automatic technical illustration[END_REF] describe a nonphotorealistic shading technique for depicting metallic ob-jects. In this paper we compile and automate similar guidelines to depict a variety of materials in photorealistic images.

User interfaces for lighting design. Kerr and Pellacini [START_REF] Kerr | Toward evaluating lighting design interface paradigms for novice users[END_REF] present an excellent survey and evaluation of lighting design interfaces. Researchers have investigated two main interaction paradigms; indirect interfaces in which users adjust lighting features in the image such as shading, shadows and highlights [START_REF] Poulin | Lights from highlights and shadows[END_REF][START_REF] Pellacini | A user interface for interactive cinematic shadow design[END_REF], and painting interfaces in which users paint the distribution of light over the scene and an optimizer solves for the lighting setup that best reproduces this distribution [SDS * 93, AD04, PBMF07]. Okabe et al. [START_REF] Okabe | Illumination brush: Interactive design of all-frequency lighting[END_REF] and Pellacini [START_REF] Pellacini | envylight: an interface for editing natural illumination[END_REF] extend painting and indirect interfaces to the design of environment maps. However, these interfaces do not incorporate the guidelines expert photographers and lighting designers commonly use to enhance the appearance of materials. Users must rely on their own training and experience to set up the lighting. In contrast, we present an automated system that optimizes the lighting based on design principles for material depiction.

PRT for illumination and material editing. Precomputed radiance transfer (PRT) [SKS02,NRH03] significantly accelerates rendering under complex lighting and provides real-time feedback for illumination [START_REF] Okabe | Illumination brush: Interactive design of all-frequency lighting[END_REF][START_REF] Pellacini | envylight: an interface for editing natural illumination[END_REF] and material editing [START_REF] Ben-Artzi A | Real-time brdf editing in complex lighting[END_REF]. We share many mathematical ideas with these methods such as the use of spherical harmonics and rotational convolution [START_REF] Ramamoorthi R | A signalprocessing framework for reflection[END_REF]. However, while traditional PRT integrates light transport over the lighting domain to generate the image, we integrate light transport over the image domain to optimize the environment map.

Design Principles for Material Depiction

Books on studio photography [START_REF] Montizambert | Creative Lighting Techniques for Studio Photographers[END_REF][START_REF] Hunter | Light: Science and Magic: An Introduction to Photographic Lighting[END_REF] and studies of material perception [PFG00, FDA03, KP03, FJB04, FTA04] suggest a variety of techniques for enhancing the appearance of materials. We have compiled these techniques into a set of design principles for depicting many common types of materials. Each principle articulates the distinctive visual features of a class of materials and describes how environment lighting can emphasize those features. Note that some materials can benefit from several principles, like glass which is transparent and reflective.

Transparent materials (e.g. glass, ice). The reflections and refractions along contours should contrast sharply with the refractions in the interior parts of the object to depict transparent materials.

Wine Glass

We base this principle on the bright-field lighting technique used in studio photography [START_REF] Hunter | Light: Science and Magic: An Introduction to Photographic Lighting[END_REF] to delineate the contours of transparent objects (see inset). Photographers place the object in front of a bright background and position dark plates (called gobos) around the object, outside the field of view, to produce dark reflections and refractions along contours.

Dark-field lighting produces the complementary effect using a dark background and bright gobos.

Subsurface scattering materials (e.g. wax, marble). The shading should be darker in thick parts and brighter in thin parts to show how the amount of light passing through the object depends on its thickness when it is made of a subsurface scattering material.

Plant Leaves

Fleming et al. [START_REF] Fleming R | Perceiving translucent materials[END_REF] show that subsurface scattering is better perceived when objects are illuminated from behind, since backlighting provides more visual cues of light scattered through the thin parts of the object (see inset). Subsurface scattering materials appear to have low contrast and look flatter when illuminated from the front as the variations in shading are diffused by multiple scattering.

Shiny materials (e.g. metal, plastic, chrome). The specular reflections should contain high contrast edges to convey shiny materials. The edges should be sharp for mirror-like materials and blurry for rough materials like brushed metal.

Chrome Brushed Metal

Pellacini et al. [START_REF] Pellacini | Toward a psychophysically-based light reflection model for image synthesis[END_REF] show that under the Ward reflectance model, contrast and sharpness of highlights are the two main dimensions in the perception of gloss. Fleming et al. [START_REF] Fleming R | Realworld illumination and the perception of surface reflectance properties[END_REF] demonstrate that realworld illumination contributes to accurate perception of shiny materials because it contains edges and bright light sources. Fleming et al. [START_REF] Fleming R | Specular reflections and the perception of shape[END_REF] also show that distortions of the reflected environment structures contribute to the perception of shape. Finally, Gooch et al. [START_REF] Gooch | A non-photorealistic lighting model for automatic technical illustration[END_REF] show how metal can be conveyed in non photorealistic rendering by alternating sharp dark and light bands oriented in the direction of minimum curvature.

Fresnel materials (e.g. glass, plastic, varnish). The specular reflections at grazing angles should maintain high contrast with respect to the diffuse color of the object to reveal the strong view dependent reflection that is characteristic of Fresnel materials.

Car Paint

The intensity of specular reflections varies with respect to the angle of incidence according to the Fresnel equations. While the strength of reflections is almost constant for conductor materials like metal, it is much stronger at grazing angles for dielectric materials like plastic. In the inset, Fresnel reflections in the car paint delineate the silhouette of the car. Illustrators often exaggerate the Fresnel reflections when drawing cars [START_REF] Robertson | How to Draw Cars the Hot Wheels Way[END_REF].

Asperity scattering materials (e.g. short fur, velvet). The highlights at grazing angles should maintain high contrast with respect to the diffuse color of the object to reveal the scattering properties of materials covered with a thin layer of asperities like velvet, short fur or dust.

Velvet

Koenderink and Pont [START_REF] Koenderink | The secret of velvety skin[END_REF] show that asperity scattering materials produce strong highlights when viewed or lit at grazing angles. In extreme cases like black velvet, strong highlights along occluding contours are the only visible features.

Optimization Framework

Our optimization framework automatically generates lighting environments that best fulfill the material specific design principles. Our key insight is that we can pre-integrate the light transport over the image domain and then efficiently compute the optimal lighting for any material design principle we can express as either a linear or quadratic image quality metric. While we instantiate our system to tackle the specific problem of material depiction, our optimization framework is general and should be of interest for many other lighting design applications such as shape depiction and environment map painting.

Consider a static scene lit by an environment map L. The radiance at each point x in the image is given by

B(x; L(.)) = Z S 2 T (x, ω ω ω)L(ω ω ω)dω ω ω, (1)
where ω ω ω is the incoming light direction and T is the light transport operator that includes the effects of reflectance, visibility, the cosine term, and interreflections. In matrix form we obtain

B = TL, ( 2
)
where T is the light transport matrix and B and L are vectors of the image and lighting environment. Each column of T contains an image of the scene as lit from the direction ω ω ω, and each row of T contains the values of pixel x when lit from all directions. Traditional PRT methods use Equation 2to compute the image B under arbitrary lighting L [NRH03].

Our goal instead is to find the optimal lighting Lopt according to a given material-dependent image quality metric.

Linear Metric

In the linear case, we define the image quality metric C as

C(L(.)) = Z x f (x)B(x)dx, (3)
where f (x) is a per-pixel linear weighting function designed to enhance material-specific visual features in the image B.

Combining Equations 1 and 3 gives

C(L(.)) = Z x Z S 2 f (x)T (x, ω ω ω)L(ω ω ω)dxdω ω ω (4) C = f t B = f t TL, ( 5
)
where B is a vector of image pixels and f is a vector of pixel weights. Our goal is to maximize |C|.

Pre-integration. The image quality metric C is a double integral over the image and the lighting. By inverting the order of the integrals, we can pre-integrate the metric over the image domain

F(ω ω ω) = Z x f (x)T (x, ω ω ω)dx (6) F t = f t T. ( 7
)
The linear metric then becomes a single integral over the lighting domain which we can evaluate as a dot product

C(L(.)) = Z S 2 F(ω ω ω)L(ω ω ω)dω ω ω (8) C = F t L. (9)
F is the vector of weights transferred into the lighting domain. By precomputing F we avoid explicit storage of the transport matrix T and allow the fast evaluation of C as a dot product between F and any lighting L. In Section 4.6 we discuss the precomputation of F and evaluation of F t L.

Optimal Lighting. Since Equation 9 defines C as a dot product between L and F, |C| is maximized when L and F are aligned, i.e. when L is proportional to F. Thus,

Lopt = F √ F t F . ( 10
)
The normalization ensures that the magnitude of Lopt is 1 and prevents infinite values in the solution. However, negative values in F lead to negative values in the lighting, which violate the physics of light. We enforce Lopt ≥ 0 by clamping F to positive values

Lopt = F √ Ft F F = max(F, 0). ( 11
)
The resulting lighting is one solution maximizing |C| under the constraint L(ω ω ω) ≥ 0. We obtain a second when F = max(-F, 0). It should be noted that Lopt is only optimal with respect to our principles for material depiction and may be sub-optimal with respect to other criteria such as composition and aesthetic.

Material-Dependent Linear Metrics

Transparent materials. For transparent objects we obtain either dark-field or bright-field lighting by maximizing the contrast between the pixels along object contours and the surrounding pixels. To differentiate these two groups of pixels we define indicator functions w(x) and w(x) = 1w(x), where w(x) is close to 1 along contours and close to 0 away

L opt ~ F L opt ~ -F L opt ~ F L opt ~ -F Figure 3:
The optimal lighting delineates the contours of the wine glass (a) and produces either a dark-field or a brightfield effect. For marble (b), when the optimal lighting is proportional to F, backlighting reveals subsurface scattering through thin parts of the object. When it is proportional to -F, thin parts are darker yielding a less effective depiction.

from contours. We set w(x) = (1 -(nx.vx)) γ where nx and vx are the surface normal and view vector at point x respectively. The γ parameter controls the decay of the function and we have found that setting γ = 3 delineates thin contours. To ensure good contrast against the background, we set w(x) = 0 for the background pixels immediately surrounding the object. Then we set

f (x) = w(x) R x w(x) - w(x) R x w(x) , (12)
where the first term corresponds to the contour pixels and the second term corresponds to the surrounding pixels. The normalization terms divide by the number of pixels in each group. They ensure that both groups have equal influence on the overall contrast measure when it is integrated over the image according to Equation 3.

Figure 2 shows the weighting vector f in the image domain and the corresponding vector F in the lighting domain for a wine glass. Figure 3a shows the two optimal lighting solutions for this model. When Lopt is proportional to F it enhances the bright contours of the wine glass with the dark-field effect. The second solution, proportional to -F, produces the bright-field effect with dark contours.

Subsurface scattering materials. For subsurface scattering materials we enhance the contrast between thin and thick parts of the object. We first use a raytracer to compute the thickness of the object t(x) along each viewing ray. For simplicity we approximate t(x) as the distance between the first and the last intersection of a ray with the object. To estimate the transmittance through a slab of thickness t we use the indicator function w(x) = e -t(x) l where l is the mean free path in the material [START_REF] Jensen | A practical model for subsurface light transport[END_REF]. In our examples we manually set the mean free path high enough to allow light to travel through the thinner parts of the object. Finally, we use this new indicator function in Equation 12 to compute the contrast between thick and thin parts of the object.

Figure 3b shows that setting Lopt proportional to F produces the desired effect of brightening thin parts of the object and darkening thicker parts. However, setting Lopt proportional to -F brightens thick parts and diminishes the characteristic visual features of subsurface materials. Subsurface scattering is a special case of the linear metric where we must optimize for C rather than |C|.

Quadratic Metric

Our optimization framework also applies to quadratic image quality metrics expressed as

C(L(.)) = Z x Z y Q(x, y)B(x)B(y)dxdy (13) C = B t QB = L t (T t QT)L (14)
where Q(x, y) is a quadratic weighting function between pixels x and y.

Pre-integration. As in the linear case, we accelerate the evaluation of the quadratic metric by pre-integrating components of the metric over the image domain

Q ′ = T t QT (15) C = L t Q ′ L. (16)
In Section 4.6 we provide algorithmic details explaining how to precompute Q ′ and evaluate L t Q ′ L.

Optimal lighting. The optimal lighting Lopt is the solution to argmax

L (C = L t Q ′ L) L t L = 1 ∀ω ω ω, L(ω ω ω) ≥ 0 (17)
where the unit norm constraint L t L = 1 prevents the degenerate solution of an infinite vector. We turn this problem into a minimization by defining Ĉ = -C and we treat the unit norm constraint as a quadratic penalty to obtain argmin

L ( Ĉ = -L t Q ′ L+α(L t L-1) 2 ) ∀ω ω ω, L(ω ω ω) ≥ 0 (18)
where α controls the strength of the unit norm constraint. We set α = 0.5 for our results. The gradient of Ĉ is given by

∇ Ĉ = -2Q ′ L + 4αL(L t L -1). ( 19
)
We solve for Lopt using the quasi-Newton L-BFGS-B algorithm [START_REF] Byrd R | A limited memory algorithm for bound constrained optimization[END_REF]. While this algorithm does not guarantee a global minimum, we have found that the resulting environment maps effectively depict the desired material properties.

An alternative approach is to compute Lopt using power iteration to maximize the Rayleigh Ritz ratio L t Q ′ L L t L , while clamping negative values at each iteration. We have applied this approach to a few test cases and found that it produces visually identical results to the quasi-Newton optimization.

Material-Dependent Quadratic Metrics

Shiny materials. Shiny materials are best depicted when the reflections contain high contrast edges. To encourage the presence of such reflection edges we maximize the metric

C(L(.)) = Z x h ⊗ B(x) 2 dx ( 20
)
where h is a high pass filter and ⊗ is the convolution operator. In matrix form we obtain

Q ′ = (HT) t (HT), (21)
H is formed using a Laplacian kernel along the diagonal

H i, j =      4 if i = j -1 if i = j and pixel i is adjacent to pixel j 0 otherwise.
In multiplying H and T we are applying the high-pass filter to the columns of the light transport matrix. Note that to prevent the object silhouette from contributing to the metric, we initially render an object mask, and only apply the filter to image pixels covered by the object. We illustrate the benefit of this metric in Figure 4a, where the bright reflected highlights contain high frequency variations.

Fresnel materials. To enhance the grazing-angle reflections of Fresnel materials we maximize the contrast between the specular and diffuse components of the shading near object contours using

C(L(.)) = Z x w(x)(Bs(x) -B d (x)) 2 dx (22) C = (W(Bs -B d )) t (Bs -B d ) Q ′ = (Ts -T d ) t W(Ts -T d ) ( 23
)
where Bs is the specular component of the image, B d is the diffuse component and w(x) = (1 -(nx.vx)) γ is an indicator function that forces the contrast to be strongest near the contours. W is a diagonal matrix with W(x, x) = w(x).

Figure 4b shows how the optimal lighting enhances Fresnel reflections on a car. Because the optimal lighting places all of the light at grazing angles, parts of the car that are oriented toward the viewer appear under-exposed. In Section 5 we describe methods for generating environment maps with more natural lighting distributions. Figure 4c shows the effect of optimizing this metric to light a piece of velvet fabric. We use the isotropic microfacet model of Ashikhmin et al. [START_REF] Ashikmin | A microfacet-based BRDF generator[END_REF] to render this velvet BRDF. The optimal lighting emphasizes the specular highlights at grazing angles along the folds of the cloth to enhance the depiction of the velvet material.

Combining Multiple Objectives

Scenes usually contain multiple materials. We can optimize the lighting for all materials by combining the linear and quadratic quality metrics into a single quadratic form. We first transform linear metrics into quadratic metrics by setting Q ′ = FF t and then combine the metrics as a weighted sum of the individual terms

C = L t Q ′ L Q ′ = ∑ i w ′ i Q ′ i . (24)
We define each individual weight w ′ i as a combination of a user-specified weight w i and a normalization factor that normalizes each metric by its maximum value, given by the optimal lighting Lopt i

w ′ i = w i L t opti Q ′ i Lopt i . ( 25
)
Setting w i = 1 gives equal importance to each individual metric in the combination. When C i is a subsurface scattering metric, we only consider the solutions where F t i L ≥ 0. Figure 5 illustrates such a combination with a scene that contains a wine glass and a shiny scuplture. The combined metric produces an optimal environment map that combines the features of the optimal lighting for each material.

Implementation

The input to our system is a description of the scene and its materials. We precompute the light transport T using a custom renderer in the PBRT raytracer [START_REF] Pharr | Physically Based Rendering: From Theory to Implementation[END_REF] that generates each column of T(., ω ω ω) using a black environment map where only the pixel ω ω ω is set to 1; this is essentially the same approach as in standard PRT. For a 100 2 image and a 64 × 32 sampling of the environment, computing T takes about an hour. Note that for the Fresnel and asperity scattering metrics we generate two transport matrices, one for the diffuse and one for the specular term of the BRDF. This roughly doubles computation time.

Choosing the appropriate spatial (image) and angular (lighting) resolution is a practical issue in applying our approach. Figure 6 investigates how the computed optimal lighting varies with spatial and angular resolution for two different materials. When the optimal lighting is sharp, as in Figure 6a, increasing angular resolution (from left to right) produces a more accurate result while, as expected, the lighting is somewhat blurred at low angular resolutions. For lower frequency optimal lighting, as in Figure 6b, there is less difference with angular resolution. The relationship with image resolution is more interesting. Unlike standard PRT, our metric is pre-integrated over the image, rather than visualized directly. Therefore, while the integral (and optimal lighting) does become slightly smoother and more accurate as image resolution increases (bottom to top in Fig- ure 6), low image resolutions are usually adequate to capture the main features of the optimal lighting. In practice, we vary the image dimension between 100 2 and 300 2 and the environment map dimension between 32 × 16 and 128 × 64. We emphasize that once the optimal lighting is found, the final image is then rendered at full resolution; the lower spatial resolution is used only for pre-integrating the image quality metric.

Given the light transport matrix, we precompute the linear term F using Equation 7. The complexity is O(p 2 n 2 ), where p 2 and n 2 are the number of pixels in the image and the environment map respectively. The computation of the quadratic term Q ′ using Equation 15 is more expensive, with complexity O(p 2 n 4 + p 4 n 2 ). However the matrix Q is usually sparse, which significantly reduces the cost (Equation 21 and 23). As reported in Table 1, F can be calculated in a few seconds, while precomputing the quadratic term Q ′ can take a few hours, on the same order as determining the light transport T. Since F and Q ′ can be expressed as integrals of products of functions, an interesting future work is to explore the use of importance sampling over the image domain, dual to the acceleration of lighting integrals in Monte Carlo rendering. In addition, most of the computation can be accelerated by a parallel implementation on a cluster or on the GPU. We report in Table 1 the timings with a single CPU and with a cluster of 100 nodes for the most expensive computations.

The optimization computes the optimal lighting Lopt as described earlier in this section. For the linear metric, this is a direct calculation, while an iterative optimization is needed in the quadratic case, which takes a few seconds.

Synthesizing Natural Environment Maps

While the optimal lighting Lopt enhances material depiction, it lacks the color and often the spatial statistics of natural environment maps. To give lighting designers more flexibility, we propose to rotate a given photographic environment map L so that it maximizes the desired image quality metric. Formally, we seek to find the rotation R that optimizes

C(R) = F t R(L) or C(R) = R(L) t Q ′ R(L) (26)
in the linear and quadratic cases respectively. Since there are only 3 parameters (such as Euler angles) that determine the rotation, we directly search across the 3D space of all orientations. Advanced numerical optimization techniques could be used to accelerate this search. In some cases, physical considerations, such as maintaining a vertical orientation, may restrict the search space to a 1D or 2D set of rotations.

We pre-integrate the metric C over the image domain to obtain F or Q ′ , as described in Section 4.6. To evaluate the metric we first rotate the environment map to determine R(L) and then compute a single dot product in the linear case, or a matrix multiply and a dot product in the quadratic case. We repeat this procedure for a set of regularly sampled rotations R, and we pick the one that maximizes C. Speedup using spherical harmonic rotations. For linear metrics, the direct search over a regular sampling of all possible 3D rotations gives a complexity of O(m 3 n 2 ) where m is the number of samples in each rotation dimension and n 2 is the number of pixels in the environment map. In the quadratic case, the direct search complexity is O(m 3 n 4 ). To speed up this search in the linear case, we observe that the computation of Equation 8 for all rotated lighting L(Rω ω ω) is a rotational convolution over the lighting domain. This enables fast computation of C(R) using spherical harmonic rotations. Mathematical details of the derivation, and a fast multistage algorithm are given in the Appendix. The complexity is reduced by at least a factor of n, which can lead to a speedup of one to two orders of magnitude. While the quadratic case in Equation 16 does not have the same convolution form, we can still use spherical harmonic rotations to speed up the computation of the inner integral.

As shown in Table 1, spherical harmonic rotations yield a significant speedup. In the linear case spherical harmonics reduce running time by over two orders of magnitude and can find the optimal rotation in seconds. Although the computation is more expensive in the quadratic case, spherical harmonics reduce the search time from days to hours.

Compositing multiple rotations. When a scene contains multiple materials, we can optimize the rotation of the environment map for each object individually. However, the optimal rotation for one material is unlikely to be optimal for another material. A better approach is to find the optimal rotation after combining the image quality metric for all the materials (Section 4.5). However, we have found that for some photographic environment maps, a single rotation cannot satisfy the requirements imposed by all materials. Instead, we propose creating a composite result in which each In the final renderings we blurred the environment maps to mimic shallow depth of field. The best orientations enhance the contours of the glass and the thickness of the marble, while the median and worst orientations diminish these material-specific features. The best orientation of the photographic environment map aligns strong light sources with the brightest pixels of the optimal lighting. Compare these renderings to those in Figure 3.

median and best orientations of photographic environment maps for shiny metal (top row), car paint (middle row) and velvet (bottom row)

. The best orientations produce high frequency edges in specular highlights of the metal sculpture, and strong grazing angle reflections for both the Fresnel car paint and the asperity scattering velvet. The median and worst orientations diminish these material-specific features. The best orientation of the photographic environment map aligns strong light sources with the brightest pixels of the optimal lighting. Note that in the car example we restricted the orientation search space to a 1D set of rotations in order to preserve the vertical orientation of the environment. We blurred the environment map for the metal and velvet example to mimic shallow depth of field. Compare these renderings to those in Figure 4. material is lit by its own rotated environment map. Although the lighting in the resulting image is physically incorrect, human observers are remarkably tolerant to inconsistencies in reflections [START_REF] Khan | Image-based material editing[END_REF]. For transparent materials however, inconsistencies in the refractions may be noticeable. Thus, if the scene contains a glass object we set the rotation of the background environment map to the optimal rotation for the glass. Otherwise when the scene only contains opaque materials, we can choose any orientation for the background.

Blurring the background environment or using a shallow depth of field can improve the composite further.

Lighting texture transfer. As an alternative to simply rotating a photographic environment map we can use constrained texture synthesis [START_REF] Ashikhmin | Synthesizing natural textures[END_REF] to generate a new environment map that includes the color and spatial detail of the photographic environment and the intensity distribution of the optimal lighting. Such texture synthesis is especially Figure 9: The image quality metric for materials varies as we rotate a photographic environment. For glass (left) the peaks produce the bright-field effect. For Fresnel car paint (right) there is a large region of suitable orientations because windows provide light at grazing angles. For illustration purposes we only show rotations along a single axis.

useful when the distribution of light in the photographic environment is such that no single rotation will emphasize the materials in the scene.

We apply the fast texture-by-numbers method of Busto et al. [START_REF] Busto | Instant Texture Synthesis by Numbers[END_REF] treating the input photographic environment map as the texture exemplar, its luminance channel as the source label map, and the optimal lighting as the target label map. Since this randomized algorithm is prone to local minima, we rotate the photographic environment map to its best orientation to provide a good initial solution.

Studio Lighting. While overall exposure falls outside the scope of our optimization criteria, our approach is complementary to common studio lighting design practice where a few lights (e.g. key light, fill light, etc.) are placed in canonical positions to ensure that objects are well exposed. In Figure 8 we add a fill light to the optimized environment map for the car to prevent underexposure.

Results

Optimal environment maps. The framework of Section 4 can automatically generate environment maps that enhance material depiction, as already shown in Figures 3 and4. Metrics for multiple materials can be combined to create an overall optimal lighting (Figure 5).

Optimizing lighting orientation. Figures 7 and8 demonstrate how our system can optimize the orientation of a photographic environment map to maximize a material-specific image quality metric. In all of these examples the best orientation aligns the strong light sources in the photographic environment with the brightest regions of the optimal lighting. When the objects are lit with the best orientation, the material-specific visual features are emphasized just as they are in our direct optimization results (Figures 3 and4). For comparison we include images resulting from the median and worst orientations of the environment map. In these cases, the characteristic features of each material are greatly diminished. Note that for some of our results we blurred the environment map to mimic shallow depth of field and focus attention on the objects.

Figure 9 shows how our image quality metrics for transparent and Fresnel materials evolve as we rotate the photographic environment map. For the wine glass there are three strong peaks in this plot that maximize the metric and produce the bright-field effect with dark contours. For this environment most orientations do not produce the desired contrast along contours and generate a very low image quality score. For the car, a window in the environment provides light at a grazing angle for a large set of orientations, but when the window rotates behind the viewer both the image quality score and the Fresnel reflections are reduced. Figure 1a is an example of a composite result combining the optimal rotations for the wax candle (subsurface scattering), porcelain vase (Fresnel) and chrome sculpture (shiny metal). Figure 1b shows the objects lit consistently using the same environment but with a poorly chosen rotation; this lighting de-emphasizes the material-specific characteristics and the objects appear to be made of different materials than in Figure 1a. Figure 10 shows another example of compositing multiple environment rotations. In this case the metric for the wine glass encourages solid backlighting to obtain the bright-field effect while the metric for the metal sculpture encourages the presence of light sources that produce strong edges in the specular reflections. In the composite result each material is lit by its own optimal environment map. To preserve consistency in the refractions, we use the optimal lighting for the wine glass as the background environment. While the lighting on the metal sculpture is inconsistent with the lighting on the glass, the composite result does not appear to be inconsistent.

Lighting texture transfer. Figure 11 illustrates the use of constrained texture synthesis to produce the bright-field effect on a complex glass dinosaur. The best orientation for the exemplar photographic environment is cluttered with highfrequency edges inside the body of the dinosaur. In contrast the synthesized environment map properly delineates the contour and creates a high-contrast bright region in the surrounding pixels to enhance the depiction of glass. How- Sorting environment maps. Because our system is automatic it can be used to automatically process large collections of 3D models and environment maps. Figure 12 illustrates such application where we find the best orientation for a collection of environment maps for three objects made of glass, metal and plastic. In addition, we can use our approach to rank order the most effective environment maps to depict the materials of the object.

Real scenes. An interesting future direction is to apply our approach to design lighting for real-world scenes. Debevec et al. [DHT * 00] captured the light transport of a knight dressed in armor using their LightStage. Figure 13 shows our initial attempt at using our system to compute the optimal lighting for depicting the rough metal material of the armor. One challenge for such real-world scenes is to estimate the geometric information required by some of our image quality metrics (e.g. contour locations, thickness, etc.). In this case we manually created a mask for the chest plate and ran our shiny image metric within this masked region.

Limitations

Our precomputation framework relies on the linearity of light transport and does not account for the effect of nonlinear tone mapping. Only a few papers have studied the influence of non-linear tone mapping on material perception [START_REF] Phillips | Effects of image dynamic range on apparent surface gloss[END_REF], and it is unclear how to model these effects in our context.

While we have demonstrated that design principles for many different classes of materials can be expressed using simple image quality metrics, these principles may not capture all of the subtle features that distinguish one material from another. We believe that further perceptual research is necessary to determine how people recognize different materials. Nevertheless our optimization framework applies to any linear or quadratic metric and could directly benefit from advances in perceptual understanding of materials.

Conclusion and Future Work

Automatic lighting design is a very challenging problem and in its most general form it requires balancing a variety of different criteria, many of which are application specific. In this paper we demonstrate initial steps toward automatic design of environment maps, focusing on the specific goal of enhancing material appearance. Our system is based on material-specific lighting design principles and we show how to quantify these principles as image quality metrics. Extending our system to account for principles on other goals such as composition or portrait photography represents an exciting direction for future work.

Our main technical contribution is a general optimization framework for computing the environment map that maximizes any linear or quadratic image metric. We have also demonstrated how this framework can be used to transform existing photographic environments maps to enhance material depiction while retaining the spatial statistics of natural environments. We plan to further explore the duality between traditional PRT which integrates over the lighting domain and our strategy of pre-integrating over the image domain. Our mathematical framework and pre-integration techniques may also benefit other lighting design techniques such as environment map painting [START_REF] Okabe | Illumination brush: Interactive design of all-frequency lighting[END_REF][START_REF] Pellacini | envylight: an interface for editing natural illumination[END_REF].

Appendix: SH Computation of C(R)

The computation of Equation 8 for all rotated lighting R(L) is a rotational convolution, which we compute efficiently using spherical harmonic rotations [START_REF] Makadia | Direct 3d-rotation estimation from spherical images via a generalized shift theorem[END_REF][START_REF] Ramamoorthi R | A signalprocessing framework for reflection[END_REF]. We first expand the lighting in terms of spherical harmonics

L(ω ω ω) = ∞ ∑ l=0 l ∑ m=-l L lm Y lm (ω ω ω) (27)
where Y lm is a spherical harmonic and L lm are the spherical harmonic coefficients of L. We then denote the rotation as R = Rz(β)Ry(α)Rz(γ),

where Rz is a rotation about the z axis, and Ry is a rotation about the y axis, while

where in the last line, we use Y * ln = (-1) n Y l,-n (and therefore we are able to set p = l, q = -n). We can compute this efficiently in a multi-stage factored process for numerical implementation,

The first part of computing coefficients in Equation 32 is only O(l 3 max ), while Equations 34 and 35 can be computed using fast fourier transforms. The bottleneck is equation 33 that must be computed for each m, n, and α, which has a cost O(l 4 max ) assuming an angular resolution of the order of lmax. This is a savings of lmax over the direct angular computation using equation 8 that would be O(l 5 max ).

Figure 2 :

 2 Figure2: For glass, the image domain weight vector f is positive (green) along contours and negative (red) in the surrounding regions. In the corresponding lighting domain vector F the green pixels spread out over a wide area indicating that the contours are lit by a relatively wide region of the environment map.

  (a) Glass (Transparent) (b) Marble (Subsurface)

Figure 4 :

 4 Figure4: For shiny metal (a) the optimal lighting adds high frequency edges to the reflection. Because of the complex shape of this object, the reflections come from many different lighting directions. For the car paint (b) the optimal lighting positions most of the light at grazing angles creating strong Fresnel reflection. For the velvet (c) the optimal light creates strong highlights along the grazing angles of the folds.

Figure 5 :

 5 Figure 5: Combining multiple metrics produces an environment map that enhances both the reflections along countours of the glass and the sharp reflections of the shiny sculpture.Asperity scattering materials. Like Fresnel materials, asperity scattering materials are enhanced when the lighting produces high contrast reflections along contours. We use the same image quality metric for asperity scattering materials as we introduced for Fresnel materials (Equation23).

Figure 6 :

 6 Figure 6: Optimal lighting for Fresnel (a) and glass (b) materials. As the angular resolution of the lighting increases (left to right) the optimal lighting gains detail, especially for the sharp lighting in (a). As the spatial resolution of the image increases (bottom to top) the optimal lighting remains largely unchanged.

Figure 7 :

 7 Figure 7: Worst, median and best orientations of photographic environment maps for transparent glass (a) and subsurface scattering marble (b).In the final renderings we blurred the environment maps to mimic shallow depth of field. The best orientations enhance the contours of the glass and the thickness of the marble, while the median and worst orientations diminish these material-specific features. The best orientation of the photographic environment map aligns strong light sources with the brightest pixels of the optimal lighting. Compare these renderings to those in Figure3.

Figure 8 :

 8 Figure8: Worst, median and best orientations of photographic environment maps for shiny metal (top row), car paint (middle row) and velvet (bottom row). The best orientations produce high frequency edges in specular highlights of the metal sculpture, and strong grazing angle reflections for both the Fresnel car paint and the asperity scattering velvet. The median and worst orientations diminish these material-specific features. The best orientation of the photographic environment map aligns strong light sources with the brightest pixels of the optimal lighting. Note that in the car example we restricted the orientation search space to a 1D set of rotations in order to preserve the vertical orientation of the environment. We blurred the environment map for the metal and velvet example to mimic shallow depth of field. Compare these renderings to those in Figure4.

Figure 10 :

 10 Figure 10: The optimal environment map rotations for the wine glass (a) and the metallic sculpture (b) differ considerably. With composite image (c) we separately render each object with its own optimal lighting and then composite them together. The result enhances the depiction of both materials.

Figure 11 :

 11 Figure 11: We use constrained texture synthesis to produce an environment map that has the local appearance of a photographic environment map (a) and the global structure of the optimal lighting (b). The synthesized result produces a bright-field effect that strongly delineates contours.

Figure 13 :

 13 Figure 13: Our system emphasizes the shiny metal of the knight's armor. This real-world light transport was captured by Debevec et al. [DHT * 00] using their LightStage. We manually created a mask for the knight's chest plate and ran our shiny image quality metric within this masked region. The optimal lighting orientation favors the presence of highlights on the chest plate while these highlights are diminished in the worst and median orientations.

Figure 12 :

 12 Figure12: We used our automatic approach to find the best best orientation of 6 environment maps for different objects and materials -glass (first and second row), shiny metal (third and fourth row) and glossy plastic (fourth row). We additionally rank order the environment maps according to their score (1 for low score, 6 for high score). from the ICT Graphics lab, the sIBL Archive and Bernhard Vogl. This work was funded in part by NSF grants CCF-0924968, IIS-1011832, CCF-0643552. UC Berkeley thanks Intel, NVIDIA, Adobe Systems and Pixar for additional support through equipment and funding. INRIA acknowledges the generous support of NVIDIA (Professor Partnership Program), Autodesk (Software donation of Maya and 3DSMax), Adobe Systems (research donation) and the Regional Council of Provence Alpes-Côte d'Azur.

  (α, β, γ) are the Euler angles. The expression for a rotated lighting becomesL(Rω ω ω) = Imβ e Inγ Y ln (ω ω ω)(29)where I = √ -1 and D l are the rotation matrices for rotation about the y axis (the rotations about z are simply complex exponentials). The matrices D are related to the matrix representations of the rotation group SO(3). Finally we also expand F from Equation 6 in terms of spherical harmonics F(ω ω ω) = and 30 and using orthonormality of the spherical hamonics we obtainC(R) = ∑ l,m,n,p,qFpqL lm D l mn (α)e Imβ e Inγ

Z S 2

 2 Ypq(ω ω ω)Y ln (ω ω ω) dω ω ω C(α, β, γ) = n F l,-n L lm D l mn (α)e Imβ e Inγ ,

  Cn(α, β)e Inγ.

Table 1 :

 1 Complexity and timing of our method, where p 2 and n 2 are the spatial and angular resolution of the light transport matrix and m 3 is the number of sampled rotations of the lighting. The timings are for p 2 = 100 2 , n 2 = 50 2 and m 3 = 50 3 , for a single CPU and a cluster of 100 nodes.

	Computation	Complexity	CPU	Cluster
	Precomputation
	T transport F linear Q ′ quadratic	Scene dependent O(p 2 n 2 ) O(p 2 n 4 + p 4 n 2 )	∼ 1 h. 12 sec. 4 : 40 h.	7 min. 32 min.
	Metric evaluation
	C = F t L linear C = L t Q ′ L quadr.	O(n 2 ) O(n 4 )	1 milisec. 2.25 sec.
	Optimization
	Linear		0.8 milisec.
	Quadratic		2.65 sec.
	Best rotation
	C(R) linear direct C(R) linear SH C(R) quadr. direct C(R) quadr. SH	O(m 3 n 2 ) O(n 4 ) O(m 3 n 4 ) O(n 6 )	13 min. 6.25 sec. 78 h. 1 : 45 h.	2 min. 2 : 40 h. 14 min.

Acknowledgments. We thank the anonymous reviewers and George Drettakis for their constructive comments. Many thanks to Wesley Willet for the submission video and to Bruno Levy and Manmohan Chandraker for help on optimization. The 3D models used in this paper come from the PBRT book [PH10], the AIM@SHAPE project and the Stanford 3D scanning repository. The environment maps come


Alexander Kolpakov

Alexander Mednykh

Spherical structures on torus knots and links *

Keywords: Spherical geometry, cone-manifold, knot, link

Introduction

A three-dimensional cone-manifold is a metric space obtained from a collection of disjoint simplices in the space of constant sectional curvature k by isometric identification of their faces in such a combinatorial fashion that the resulting topological space is a manifold (also called the underlying space for a given cone-manifold). Such the metric space inherits the metric of sectional curvature k on the union of its 2-and 3-dimensional cells. In case k = +1 the corresponding cone-manifold is called spherical (or admits a spherical structure). By analogy, one defines euclidean (k = 0) and hyperbolic (k = -1) cone-manifolds. The metric structure around each 1-cell is determined by a cone angle that is the sum of dihedral angles of corresponding simplices sharing the 1-cell under identification. The singular locus of a cone-manifold is the closure of all its 1-cells with cone angle different from 2π. For the further account we suppose that every component of the singular locus is an embedded circle with constant cone angle along it. A particular case of cone-manifold is an orbifold with cone angles 2π/m, where m is an integer (cf. [START_REF] Thurston | The geometry and topology of 3-manifolds[END_REF]). The present paper considers two infinite families of cone-manifolds with underlying space the three-dimensional sphere S 3 . The first family consists of cone-manifolds with singular locus the torus knot t(2n + 1, 2) with n ≥ 1. In the rational census [START_REF] Rolfsen | Knots and links[END_REF] these knots are denoted by (2n + 1)/1. The second family of cone-manifolds consists of those with singular locus a two-component torus link t(2n, 2) with n ≥ 2. These links are two-bridge and correspond to the links 2n/1 in the rational census. The simplest examples of such the knots and links are the trefoil knot 3/1 and the link 4/1. In the Rolfsen table [START_REF] Rolfsen | Knots and links[END_REF] one finds them as the knot 3 1 and the link 4 2 1 . By the Theorem of W. Thurston [START_REF] Thurston | Hyperbolic geometry and 3-manifolds[END_REF], the manifold S 3 \3 1 does not admit a hyperbolic structure. However, it admits two other geometric structures [START_REF] Neumann | Notes on geometry and 3-manifolds, with appendix by Paul Norbury[END_REF]: H 2 × R and PSL(2, R). It follows from the paper [START_REF] Seifert | Die beiden Dodecaederräme // Math[END_REF] that the spherical dodecahedron space (i.e. Poincaré homology sphere) is a cyclic 5-fold covering of S 3 branched over 3 1 . Thus, the orbifold 3 1 ( 2π 5 ) with singular locus the trefoil knot and cone angle 2π 5 is spherical. Due to the Dunbar's census [START_REF] Dunbar | Geometric orbifolds[END_REF], orbifold 3

1 ( 2π n ) is spherical if n ≤ 5, Nil-orbifold if n = 6 and PSL(2, R)-orbifold if n ≥ 7.
Spherical structure on the cone-manifold 3 1 (α) with underlying space the three-dimensional sphere S 3 is studied in [START_REF] Derevnin | Geometry of trefoil conemanifold[END_REF]. The consideration of two-bridge torus links is carried out starting with the simplest one possessing non-abelian fundamental group, namely 4 2 1 . The previous investigation on spherical structures for cone-manifolds is carried out mainly in the papers [START_REF] Hilden | On a remarkable polyhedron geometrizing the figure eight cone manifolds[END_REF][START_REF] Mednykh | Volumes and degeneration of cone-structures on the figure-eight knot // Tokyo[END_REF][START_REF] Porti | Spherical cone structures on 2-bridge knots and links // Kobe[END_REF]. The present paper develops a method to analyse existence of a spherical metric for two-bridge torus knot and link conemanifolds. Also, the lengths of singular geodesics are calculated and the volume formulae are obtained (cf. Theorem 1 and Theorem 2).

Projective model S 3 λ

The purpose of the present section is to construct the projective model S 3 λ that one can use to study geometric properties of two-bridge torus knots and links and to build up holonomy representation for the corresponding cone-manifolds. Other projective models for homogeneous geometries are described in [START_REF] Molnár | The projective interpretation of the eight 3-dimensional homogeneous geometries // Beiträge zur Algebra und Geometrie[END_REF]. Consider the set C 2 = {(z 1 , z 2 ) : z 1 , z 2 ∈ C} as a four-dimensional vector space over R. We denote it by C 2 R and equip with Hermitian product

(z 1 , z 2 ), (w 1 , w 2 ) H = (z 1 , z 2 )H (w 1 , w 2 ) T ,
where

H = 1 λ λ 1 is a symmetric matrix with -1 < λ < +1.
The natural inner product is associated to the Hermitian form above:

(z 1 , z 2 ), (w 1 , w 2 ) = Re (z 1 , z 2 ), (w 1 , w 2 ) H
and the respective norm is

(z 1 , z 2 ) = |z 1 | 2 + |z 2 | 2 + λ(z 1 z 2 + z 1 z 2 ).
Call two elements (z 1 , z 2 ) and (w 1 , w 2 ) in

• C 2 R = C 2 R \ (0, 0) equivalent if there is µ > 0 such that (z 1 , z 2 ) = (µ w 1 , µ w 2 ). We denote this equivalence relation as (z 1 , z 2 ) ∼ (w 1 , w 2 ).
Identify the factor-space

• C 2
R / ∼ with the three-dimensional sphere

S 3 λ = {(z 1 , z 2 ) ∈ C 2 R : (z 1 , z 2 ) = 1}, endowed with the Riemannian metric ds 2 λ = |dz 1 | 2 + |dz 2 | 2 + λ(dz 1 dz 2 + dz 1 dz 2 ).
By means of equality

ds 2 λ = 1 + λ 2 |dz 1 + dz 2 | 2 + 1 -λ 2 |dz 1 -dz 2 | 2 ,
the linear transformation

ξ 1 = 1 + λ 2 (z 1 + z 2 ), ξ 2 = 1 -λ 2 (z 1 -z 2 )
provides an isometry between (S 3 λ , ds 2 λ ) and (S 3 , ds 2 ), where ds 2 = |dξ 1 | 2 + |dξ 2 | 2 is the standard metric of sectional curvature +1 on the unit sphere

S 3 = {(ξ 1 , ξ 2 ) ∈ C 2 : |ξ 1 | 2 + |ξ 2 | 2 = 1}. Let P, Q be two points in S 3
λ . The spherical distance between P and Q is a real number d λ (P, Q) that is uniquely determined by the conditions 0 ≤ d λ (P, Q) ≤ π and cos d λ (P, Q) = P, Q .

Torus knots T n

Let T n , n ≥ 1 be the torus knot t(2n + 1, 2) embedded in S 3 . The knot T n is the two-bridge knot (2n + 1)/1 in the rational census (Fig. 1). Let T n (α) denote a cone-manifold with singular locus T n and the cone angle α along it. The aim of the present section is to investigate cone-manifolds T n (α), n ≥ 1 to find out the domain of sphericity in terms of the cone angle and to derive the volume formulae. Two lemmas precede the further exposition: Lemma 1 For every 0 < α < 2π and -1 < λ < +1 the linear transformations

A = 1 0 -2 i e i α 2 λ sin α 2 e iα and B = e iα -2 i e i α 2 λ sin α 2 0 1 are isometries of S 3 λ .
Proof. For the further account let us assume that the multiplication of vectors by matrices is to the right. A linear transformation L of the space C 2 R preserves the corresponding Hermitian form if and only if for every pair of vectors

P, Q ∈ C 2 R it holds that P, Q H = P H Q T = P LHL T Q T = P L, QL H .
The condition above is equivalent to

H = LHL T .
In particular,

cos d λ (P, Q) = P, Q = P L, QL = cos d λ (P L, QL),
that means L preserves the spherical distance between P and Q. Let L = A and L = B in series, one verifies that A and B preserve the Hermitian norm on C 2 R and, consequently, the spherical distance on S 3 λ .

Lemma 2 Let A and B be the same matrices as in the affirmation of Lemma 1.

Then for all integer n ≥ 1 one has

(AB) n A -B(AB) n = 2 U 2n (Λ) e i (2n+1)(π+α) 2 sin α 2 M,
where M is a non-zero 2 × 2-matrix and U 2n (Λ) is the second kind Chebyshev polynomial of power 2n in variable Λ = λ sin α 2 .

Proof. As far as -1 < λ < +1, one obtains

-1 < Λ = λ sin α 2 < +1. Substitute Λ = cos θ,
with the unique 0 < θ < π.

Then matrices A and B are rewritten in the form

A = 1 0 -2 i e i α 2 cos θ e iα , B = e iα -2 i e i α 2 cos θ 0 1 .
On purpose to diagonalize the matrix AB, use

V = i e -i α 2 e -iθ i e -i α 2 e iθ 1 1 ,
and obtain

D = V -1 (AB)V = -e iα e 2iθ 0 0 -e iα e -2iθ .
Note, that V might be not an isometry, but it is utile for computation.

Thus (AB) n A -B(AB) n = (V D n V -1 )A -B(V D n V -1 ) = = 2 sin(2n + 1)θ sin θ e i (2n+1)(π+α) 2 sin α 2 -1 λ -λ 1 = = 2 U 2n (cos θ) e i (2n+1)(π+α) 2 sin α 2 M = 2 U 2n (Λ) e i (2n+1)(π+α) 2 sin α 2 M,
with the matrix

M = -1 λ -λ 1
as the present Lemma claims.

The main theorem of the section follows:

Theorem 1 The cone-manifold T n (α), n ≥ 1 is spherical if 2n -1 2n + 1 π < α < 2π - 2n -1 2n + 1 π.
The length of its singular geodesic (i.e. the length of the knot T n ) equals

l α = (2n + 1) α -(2n -1) π. The volume of T n (α) is Vol T n (α) = 1 2n + 1 2n + 1 2 α - 2n -1 2 π 2 .
Proof. The fundamental group of the knot T n is presented as

π 1 (S 3 \T n ) = a, b|(ab) n a = b(ab) n ,
with generators a and b as at Fig. 1.

Since the cone-manifold T n (α) admits a spherical structure, then there exists a holonomy mapping [START_REF] Thurston | The geometry and topology of 3-manifolds[END_REF], that is a homomorphism

h : π 1 (S 3 \T n ) -→ Isom S 3 λ .
We will choose h in respect with geometric construction of the cone-manifold. All the further computations to find the length of the knot T n and the volume of the cone-manifold T n (α) are performed making use of the corresponding fundamental polyhedron P n (Fig. 2). The construction algorithm for the polyhedron is given in [START_REF] Mednykh | On the structure of the canonical fundamental set for the 2-bridge link orbifolds[END_REF]. The combinatorial polyhedron P n has vertices P i , i ∈ {1, . . . , 4n + 2} and edges

P i P i+1 , i ∈ {1, . . . ,
h(a) = A, h(b) = B,
where A and B are matrices from Lemma 1.

The generators of the fundamental group for T n under the holonomy mapping h correspond to isometries acting on P n . These isometries identify its faces by means of rotation about the edge P 1 P 2n+2 for the top "cupola" of P n and rotation about P 2 P 2n+3 for the bottom one (see, Fig. 2). Then the edges P 1 P 2n+2 and P 2 P 2n+3 knot itself to produce T n (cf. [START_REF] Mednykh | On the structure of the canonical fundamental set for the 2-bridge link orbifolds[END_REF][START_REF] Minkus | The branched cyclic coverings of 2-bridge knots and links // Mem[END_REF]).

In order to construct the polyhedron P n assume that its edge P 1 P 2 is given by

P 1 = (1, 0), P 2 = (0, 1).
Then one has cos d λ (P 1 , P 2 ) = P 1 , P 2 = λ, i.e. the spherical distance between the points P 1 and P 2 can vary from 0 to π. Thus, prescribing certain coordinates to the end-points of the edge P 1 P 2 we do not loss in generality of the consideration. Note, that the axis of the isometry A from Lemma 1 contains P 1 and the axis of B contains P 2 . The aim of the construction for the polyhedron P n is to bring its edges P 1 P 2n+2 and P 2 P 2n+3 to be axes of the respective isometries A and B.

The other vertices P i has to be images of P (c) sum of the inner dihedral angles ψ i along P i P i+1 , i ∈ {1, . . . , 4n + 1} equals 2π;

(d) sum of the dihedral angles φ i for corresponding tetrahedra N SP i P i+1 , i ∈ {1, . . . , 4n + 1} at their common edge N S is 2π; By the orientation of a tetrahedron N SP i P i+1 one means the sign of the Gram determinant det(S, N, P i , P i+1 ) for corresponding quadruple S, N , P i , P i+1 ∈ C 2 R , where i ∈ {1, . . . , 4n + 2}, P 4n+3 = P 1 . A tetrahedron is non-degenerated if det(S, N, P i , P i+1 ) = 0. Thus, claim (e) is satisfied if all the Gram determinants are non-zero and of the same sign. If α = 2π m , m ∈ N, then due to the Poincaré Theorem [14, Theorem 13.5.3] claims (a) -(e) imply that the group generated by the isometries A and B is discreet and its presentation is

Γ = A, B|(AB) n A = B(AB) n , A m = B m = id . The metric space S 3 λ /Γ ∼ = T n ( 2π m
) is a spherical orbifold, and P n is its fundamental polyhedron. If m / ∈ N then the group generated by A and B might be non-discreet. However, the identification for the faces of P n is of the same fashion as if it were m ∈ N and as the result one obtains the cone-manifold T n (α). By means of Lemma 1 and construction of P n claims (a) and (b) are satisfied. For the holonomy mapping h to exist the following relation should be satisfied:

h((ab) n a) -h(b(ab) n ) = (AB) n A -B(AB) n = 0.
By Lemma 2, the condition above is satisfied if and only if U 2n (Λ) = 0, where Λ = λ sin α 2 . Thus, the parameter λ of the metric ds 2 λ is determined completely by a root of the polynomial U 2n (Λ). From the above formula, λ is related to the cone angle α by means of the equality

λ = Λ sin α 2 .
The roots of U 2n (Λ) are given by the following formula:

Λ k = cos kπ 2n + 1 , with k ∈ {1, . . . , 2n}.
The parameter λ for the metric ds 2 λ has to be chosen in order the polyhedron P n be proper and the metric itself be spherical. Note, that the edges P i P i+1 , i ∈ {1, . . . , 4n + 2}, P 4n+3 = P 1 are equivalent under action of the group Γ = A, B . Thus, the relation (AB) n A = B(AB) n implies the equality

2(2n+1) i=1 ψ i = 2kπ,
where k is an integer. Show that one can choose λ for the equality k = 1 to hold for all α in the affirmation of the Theorem. Due to the paper [START_REF] Hodgson | Involutions and isotopies of lens spaces, Knot theory and manifolds[END_REF], every two-bridge knot conemanifold with cone angle π is a spherical orbifold. In this case all the vertices P i of the fundamental polyhedron belong to the same circle and all the dihedral angles ψ i and φ i are equal to each other [START_REF] Mednykh | On the structure of the canonical fundamental set for the 2-bridge link orbifolds[END_REF]:

φ i = ψ i = π 2n + 1 .
As far as cos d λ (N, S) = cos d λ (P i , P i+1 ) = λ, then in case α = π one obtains

λ = Λ k sin π 2 = cos θ
for certain k ∈ {1, . . . , 2n} and then

2(2n+1) i=1 ψ i = 2(2n + 1)θ.
Using the formula for the roots of U 2n (Λ) obtain that

i=1 φ i = 2π
holds, that means claim (d) is also satisfied. Verify that under conditions of the Theorem the metric ds 2 λ is spherical. This claim is equivalent to the inequality

-1 < λ < +1. Note, that for 2n -1 2n + 1 π < α < 2π - 2n -1 2n + 1 π it follows sin α 2 > sin (2n -1)π 2(2n + 1) .
As far as sin α 2 > 0 and Λ 1 = sin (2n-1)π 2(2n+1) > 0, one has 0 < λ < 1.

By analogy with Lemma 1 verify that

C = 0 1 1 0 is an isometry of ds 2 λ . Fixed point sets of A and B in S 3 λ are circles Fix A = {(z 1 , 0) : z 1 ∈ C, |z 1 | = 1} and Fix B = {(0, z 2 ) : z 2 ∈ C, |z 2 | = 1},
correspondingly. The geometric meaning of C is that it maps the first fixed circle to the other. Thus, the relation B = CAC -1 holds.

The following equalities

P 2k+1 = P 1 (AB) k , k ∈ {0, . . . ,
ε(m) = m 2 α - 4n -m 2 π.
By analogy with the proof of Lemma 2 it follows that

(AB) k = C(BA) k C -1 = = -sin(2k-1)θ
sin θ e i ε(2k) -sin 2kθ sin θ e i ε(2k-1) sin 2kθ

sin θ e i ε(2k+1) 2k) ,

sin(2k+1)θ sin θ e i ε(
where θ = π 2n+1 . Suppose N and S to be middle-points of the edges P 1 P 2n+2 and P 2 P 2n+3 , respectively. Then

N = (e i ε(2n+1) 2 , 0), S = (0, e i ε(2n+1) 2 ).
For the lengths l α of the singular geodesic one has cos l α 4 = P 1 , N = P 1 C, N C = P 2 , S .

Thus cos l α 4 = cos (2n + 1)α -(2n -1)π 4 .
By construction of the polyhedron P n , the inequality 0 < l α < 4π holds. Then it follows l α = (2n + 1)α -(2n -1)π.

Given the coordinates of the vertices P i and the poles N and S of the polyhedron P n , verify claim (e). For every four points A, B, C, D ∈ C 2 R , where

A = (A 1 , A 2 ), B = (B 1 , B 2 ), C = (C 1 , C 2 ), D = (D 1 , D 2 ), their Gram determinant is det(A, B, C, D) := det     Re A 1 Im A 1 Re A 2 Im A 2 Re B 1 Im B 1 Re B 2 Im B 2 Re C 1 Im C 1 Re C 2 Im C 2 Re D 1 Im D 1 Re D 2 Im D 2     .
Each tetrahedron N SP i P i+1 with i ∈ {1, . . . , 2n + 1} is isometric to N SP 2n+i+1 P 2n+i+2 , i ∈ {1, . . . , 2n + 1}, P 4n+3 = P 1 by means of the isometry C defined above. Thus, we consider only the tetrahedra N SP i P i+1 with i ∈ {1, . . . , 2n + 1}. Split them into two groups: the tetrahedra N SP 2k+1 P 2k+2 with k ∈ {0, . . . , n} and the tetrahedra N SP 2k P 2k+1 with k ∈ {1, . . . , n}. Substitute α = β + π and proceed with straightforward calculations: ∆

k (β) = det(S, N, P 2k+1 , P 2k+2 ) = cos 2 L 1 β 4 -U 2 2k-1 (cos θ) sin 2 β 2 = = T 2 L1 (cos β 4 ) -U 2 2k-1 (cos θ) sin 2 β 2 , (1)
where k ∈ {0, . . . , n}, L

1 = |2n -4k + 1|, θ = π 2n+1 , β ∈ [-2 θ, 2 θ]; ∆ (2)
k (β) = det(S, N, P 2k , P 2k+1 ) = cos 2 L 2 β 4 -U 2 2k-2 (cos θ) sin 2 β 2 = = T 2 L2 (cos β 4 ) -U 2 2k-1 (cos θ) sin 2 β 2 ,
where k ∈ {1, . . . , n}, L 2 = |2n -4k + 3|, θ and β the same as above. The first kind Chebyshev polynomial of degree k ≥ 0 is denoted by T k . Assume that

U -1 (cos θ) = 0, U 0 (cos θ) = 1
for the sake of brevity.

All the functions ∆ Then for all β ∈ (-2θ, 2θ) (i.e. for all α in the affirmation of the Theorem) det(S, N, P i , P i+1 ) > 0 where i ∈ {1, . . . , 4n + 2}, P 4n+3 = P 1 . Thus, claim (e) for the polyhedron P n is satisfied. Use the Schläfli formula [START_REF] Hodgson | Degeneration and regeneration of hyperbolic structures on three-manifolds[END_REF] to obtain the volume formula for T n (α). One has

dVol T n (α) = l α 2 dα = (2n + 1)α -(2n -1)π 2 dα.
Note, that Vol T n (α) → 0 with α → 2n-1 2n+1 π. In this case d λ (P i , P i+1 ) → 0, where i ∈ {1, . . . , 4n+2}, P 4n+3 = P 1 and the fundamental polyhedron collapses to a point. Thus

Vol T n (α) = 1 2n + 1 2n + 1 2 α - 2n -1 2 π 2 .
Remark 1 The domain of the spherical metric existence in Theorem 1 was indicated before in [10, Proposition 2.1].

Torus links L n

Let L n , n ≥ 2 be a torus link t(2n, 2) with two components. The corresponding link in the rational census is 2n/1 (Fig. 3). The fundamental group of L n is presented as π 1 (S 3 \L n ) = a, b|(ab) n = (ba) n . By Lemma 1, linear transformations A and B are isometries of S 3 λ .

Lemma 3 For every integer n ≥ 2 the following equality holds

(AB) n -(BA) n = 4 U n-1 (Λ) λ e i( α+β 2 +π) n sin α 2 sin β 2 M,
where M is a non-zero 2 × 2 matrix and U n-1 (Λ) is the second kind Chebyshev polynomial of degree n -1 in variable

Λ = (1 -λ 2 ) cos α -β 2 + λ 2 cos α + β 2 .
Proof. By analogy with Lemma 2. With Lemma 3 the main theorem of the section follows: (c) sum of the inner dihedral angles ψ i along the edges P i P i+1 , i ∈ {1, . . . , 4n -1} equals 2π;

(d) sum of the dihedral angles φ i for tetrahedra N SP i P i+1 , i ∈ {1, . . . , 4n-1} at their common edge N S equals 2π;

(e) all the tetrahedra N SP i P i+1 with i ∈ {1, . . . , 4n}, P 4n+1 = P 1 are non-degenerated and coherently oriented.

In order to choose the parameter λ for the corresponding metric consider the fundamental polyhedron F n with α = β = π. Then all its vertices belong to the same circle and all the dihedral angles ψ i of the tetrahedra N SP i P i+1 along the edges P i P i+1 are equal to ψ = π 2n [START_REF] Mednykh | On the structure of the canonical fundamental set for the 2-bridge link orbifolds[END_REF]. Also the dihedral angles φ i of the tetrahedra N SP i P i+1 along their common edge N S are equal to each other:

φ i = φ = π 2n .
In this case λ = P 1 , P 2 = cos φ and Λ = -cos 2φ = cos (n -1)π n .

All the roots of U n-1 (Λ) are given by the formula By analogy with the proof of Theorem 1 one obtains

l α = l β = α + β 2 n -π(n -1).
Given the coordinates of the vertices for the fundamental polyhedron verify claim (e) for all (α, β) in the domain D. Make use of the Schläfli formula [START_REF] Hodgson | Degeneration and regeneration of hyperbolic structures on three-manifolds[END_REF] to obtain the volume of L n (α, β):

d Vol L n (α, β) = l α 2 dα + l β 2 dβ = α + β 2 n -π(n -1) d α + β 2 .
Note, that with α = β → π n -1 n the fundamental polyhedron F n collapses to a point (i.e. the volume tends to 0). The last affirmation of the Theorem follows.

  a

Figure 1 :

 1 Figure 1: Knot (2n + 1)/1

Figure 2 :

 2 Figure 2: Fundamental polyhedron P n for T n (α)

  if α = π. Thus, claim (c) for the polyhedron P n with α = π is satisfied if k = 1. As far as the parameter α varies continuously and sum of the angles ψ i represents a multiple of 2π, one has that

k

  (β), j ∈ {1, 2} are even on the interval [-2θ, 2θ]. Then one considers them only on the interval [0, 2θ]. Note, that the polynomial T 2 Lj (cos β) monotonously decreases and the function sin 2 β 2 monotonously increases with β ∈ [0, 2θ]. Moreover, T 2 Lj (cos 0) = T 2 Lj (1) = 1. Then it follows that ∆ (j) k (β) > 0 with β ∈ (-2θ, 2θ). Also, one has ∆ (j) k (±2 θ) = 0.

Figure 3 :

 3 Figure 3: Link 2n/1Let L n (α, β) denote a cone-manifold with singular locus the link L n and the cone angles α, β along its components. For every α, β ∈ (0, 2π) and λ ∈ (-1, +1), we denoteA = 1 0 -2 i e i α 2 λ sin α 2 e iα

Figure 4 :

 4 Figure 4: The fundamental polyhedron F n for L n (α, β)

Λ 2 = cos α-β 2 + cos π n cos α-β 2 -cos α+β 2 .cos l α 2 = P 1 , N , cos l β 2 =

 22212 k = cos kπ n , k ∈ {1, . . . , n -1}, so one choose the root Λ k with k = n -1. Then, by analogy with Theorem 1are satisfied at the point α = β = π of the domainD = (α, β) : |α -β| < 2π 1 -1 n , |α + β -2π| < 2π n ,depicted at Fig.5.In terms of the parameter λ, that defines the metric ds 2 λ , one has λ As for all (α, β) ∈ D the inequality 0 < λ 2 < 1 is satisfied, the metric ds 2 λ is spherical regarding the corresponding domain. By analogy with Theorem 1 one can show that claims (a) -(d) for the polyhedron F n are satisfied in the interior of D. The lengths l α and l β of singular geodesics for the cone-manifold L n (α, β) meet the relations P 2 , S .

Figure 5 :Remark 2 Remark 3

 523 Figure 5: The domain D of sphericity for L n (α, β)

  4n + 2}, with P 4n+3 = P 1 , also P 1 P 2n+2 and P 2 P 2n+3 . Let N , S denote the middle points (the North and the South poles of P n ) on the edges P 1 P 2n+2 and P 2 P 2n+3 , respectively. Then, consider also edges N P i , SP i , i ∈ {1, . . . , 4n + 2}. Without loss in generality, choose the holonomy representation such that

  1 and P 2 under action of A and B. The polyhedron P n is said to be proper if (a) inner dihedral angles along P 1 P 2n+2 and P 2 P 2n+3 are equal to α; (b) the following curvilinear faces are identified by A and B: A : N P 1 P 2 . . . P 2n+2 → N P 1 P 4n+2 . . . P 2n+3 P 2n+2 , B : SP 2 P 1 P 4n+2 . . . P 2n+3 → SP 2 P 3 . . . P 2n+3 ;

  n}, P 2k = P 2 (AB) k-1 , k ∈ {1, . . . , n + 1}; and P 2k+1 = P 1 (BA) 2n-k+1 , k ∈ {n + 1, . . . , 2n}, P 2k = P 2 (BA) 2n-k+2 , k ∈ {n + 2, . . . , 2n + 1}, follow from the identification scheme of the edges of P n . Define the auxiliary function

The work is performed under auspices of the Swiss National Science Foundation no. 200020-113199/1, "Scientific Schools"-5682.2008.1 and RFBR no. 06-01-00153.

Theorem 2 The cone-manifold L n (α, β), n ≥ 2 is spherical if

The lengths l α , l β of its singular geodesics (i.e. lengths of the components for L n ) are equal to each other and

Proof. One continues the proof by analogy with Theorem 1. Suppose that L n (α, β) is spherical. Then there exists a holonomy mapping [START_REF] Thurston | The geometry and topology of 3-manifolds[END_REF]:

By means of Lemma 3 the equality above holds either if λ = 0, or if

In case λ = 0 the image of h is abelian, because of the additional relation AB = BA. With n ≥ 2 this leads to a degenerate geometric structure. Thus, one has to choose the parameter λ for the metric ds 2 λ using roots of the Chebyshev polynomial U n-1 (Λ). The fundamental polyhedron F n for the cone-manifold L n (α, β) is depicted at Fig. 4. Suppose its vertices P 1 and P 2 to be

The axes of isometries A and B correspond to the edges P 1 P 2n+1 and P 2 P 2n+2 . Points N and S are respective middles of the edges P 1 P 2n+1 and P 2 P 2n+2 . Those are called North and South poles of the polyhedron. The polyhedron F n is said to be proper if (a) respective inner dihedral angles along the edges P 1 P 2n+1 and P 2 P 2n+2 are equal to α and β;