SOFT SHADOW RENDERING

1 . A method of computing a horizon map from a multiple resolution pyramid, comprising:

computing a multiple resolution pyramid comprising pyramid resolution levels differing by a factor of 2 1/k , where k is any number from a set of numbers comprising non-integers and integers;

indexing pyramid resolution levels increasing in resolution coarseness corresponding respectively to an increase in a distance from a shadow castor point to a receiver point;

generating a set of height difference samples at respective pyramid resolution levels by sampling heights at a receiver point and at azimuthal distances in an azimuthal direction, and subtracting the heights to get height difference samples;

computing angles as a function of azimuthal distances from the receiver point;

approximating a horizon angle of the angles as a function of azimuthal distances.

2 . The method of claim 1 , using a multi-scale derivative to compute the angles as a function of azimuthal distances.

3 . The method of claim 1 , generating the set of height difference samples comprising:

computing a height difference between the receiver point and shadow castor points for respective distances at a corresponding pyramid resolution level for the azimuthal direction.

4 . The method of claim 2 , the multi-scale derivative approximating the function comprising a tangent of the angles as a function of azimuthal distances from the receiver point.

5 . The method of claim 1 , approximating the horizon angle comprising approximating a maximum horizon angle of the function generated by interpolating the function using an interpolation.

6 . The method of claim 5 , the interpolation comprising a 1D bspline interpolation or a bilinear interpolation.

7 . The method of claim 1 , where height differences are determined using a 2D bspline interpolation with the multiple resolution pyramid.

8 . The method of claim 1 , where the angles are computed with an arc tangent of the multi-scale derivative

9 . The method of claim 1 , the multiple resolution pyramid comprising coarser pyramid levels for pre-filtering height variations as distances increase from the receiver point to the shadow castor point, and finer pyramid levels for pre-filtering height variations as distances decrease.

10 . The method of claim 1 , the multiple resolution pyramid determining a sampling density that increases logarithmically with increasing distance towards the receiver point, and applying increased pre-filtering to height variations as distances increase from the receiver point.

11 . A method for rendering soft shadowing onto a horizon map comprising:

extracting a horizon map from a set of sample points indexing a sequence of horizon angles;

rendering visibility wedges from the sequence of horizon angles by using an area-supported basis for a visibility hemisphere; and

rendering a total visibility at the set of sample points from visibility wedges represented by the area-supported basis for the visibility hemisphere.

12 . The method of claim 11 , comprising:

generating an environmental visibility sample at sample points on the horizon map, parameterized by a complete swath (cos φ, sin φ), φ ∈ [0, 2π]; and

generating a key lighting sample from sample points on the horizon map, parameterized by a partial azimuthal swath.

13 . The method of claim 11 , comprising computing visibility wedges in a partial azimuthal swath, and extracting the horizon map using a multiple resolution pyramid comprising levels of resolution differing by a factor of 2 1/k , where k is any number from a set of numbers comprising non-integers and integers, and applying an interpolation to angles therein.

14 . The method of claim 13 , the interpolation comprising a smooth interpolation converting angle samples at respective pyramid resolution levels of a multiple resolution pyramid to a substantially smooth function that is continuous according to a first equation as follows:

ω(τ,x,φ)= b spline(τ,{ω n ( x,φ,d n ),ω 1 ( x,φ,d 1 ), . . . ,ω N−1 ( x,φ,d N−1 )});

ω i denoting a angle sample at respective pyramid resolution levels i;

x denoting a receiver point, φ denoting an azimuthal direction, and d i denoting distance; and τ defining a space parameter of negative log distance away from the receiver point; and

computing a horizon angle from the substantially smooth function according a second equation as follows:

ω(x,φ) ω(τ,x,φ)

15 . The method of claim 14 , the horizon angle from the substantially smooth function according to the second equation is an approximately maximum horizon angle.

16 . The method of claim 11 , the area-supported basis for the visibility hemisphere is a spherical harmonic representation.

17 . The method of claim 12 , comprising generating approximately sixteen environmental lighting samples for rendering an environmental light, and approximately three key lighting samples for rendering a key light.

18 . A method of extracting a horizon map and rendering soft shadows thereon from a light environment comprising:

computing a multiple resolution pyramid on a height field, the multiple resolution pyramid comprising pyramid resolution levels differing by a factor of 2 1/k , where k is any number from a set of numbers comprising non-integers and integers;

indexing the pyramid resolution levels increasing in resolution coarseness corresponding respectively to an increase in distance from a shadow castor point to a receiver point;

generating a set of height difference samples at respective pyramid resolution levels by sampling heights at a receiver point and at azimuthal distances in an azimuthal direction, and subtracting the heights to get height difference samples;

computing angles as a function of azimuthal distances from the receiver point using a multi-scale derivative approximating the function comprising an arc tangent of a horizon angle as a function of a distance from the receiver point;

interpolating the function;

approximating the horizon angle that is an approximately maximum horizon angle of the function interpolated by interpolating again;

indexing sequential pairs of horizon angles and converting the sequential pairs into visibility wedges represented using a spherical harmonic basis of fourth order, the visibility wedges restricted to a partial azimuthal swath less than 2π;

rendering a total visibility at the set of height difference samples from the visibility wedges represented by a spherical harmonic representation.

the light environment comprising a key light and/or environmental light,

the multiple resolution pyramid determining a sampling density that increases logarithmically with increasing distance towards the receiver point, and applying increased pre-filtering to height variations as distances increase from the receiver point.

19 . The method of claim 18 , where the environmental light is a broader light than the key light.

20 . The method of claim 18 , where interpolating comprises a 1 dimensional bspline interpolation, a bilinear interpolation, or a 2 dimensional bspline interpolation.