One warped shadow map, and what it cannot reach

A shadow map’s texels land by two distances and two cosines measured how large a shadow map’s texels arrive in the eye’s picture, and found a closed form: the ratio of the two focal lengths squared, the ratio of the lamp’s distance to the eye’s distance squared, and the ratio of the two cosines at the surface. For a lamp 40 m ahead of the eye, 5 m up and facing back, a 1024-texel map lands texels of 8.69 px on the floor 5 m from the eye and half a pixel at 20 m. For none to exceed a pixel anywhere on the floor the eye sees, the map would have to be 9,530 texels square — 90.8 million texels, nearly all of them spent on floor far from the eye where the unwarped map is already finer than a pixel.

It closed on the alternative to splitting the eye’s view into slabs with a map for each. One map whose projection is chosen so that more of its texels go where the eye looks hardest: a lamp’s picture drawn through a perspective warp. It asked how much of the 9,530 texels such a warp can remove, what the best warp is, and whether what remains is exactly the cosine ratio, which no warp of the lamp’s picture can reach.

Most of it can be removed. What remains is not the cosine ratio, or not in the sense the question meant.

The bound: one texel per pixel #

Before pricing any particular warp it is worth finding the floor no warp can go below, because it turns out to be a number that can be read without any warping at all.

A warp of the lamp’s picture is a way of spending texels unevenly over it: dense where a texel lands large in the eye’s picture, sparse where it lands small. At each place in the lamp’s picture the floor there needs a certain density of texels for its texels to reach the eye no larger than a pixel — the need is exactly the footprint the earlier essay measured, expressed per unit of the lamp’s picture. The best any warp can do is to give every place exactly its need, and the total is the need summed over the lamp’s picture.

That sum has a closed value. The need at a place is how many square pixels of the eye’s picture one unit of the lamp’s picture covers there — the footprint a wall does not get darker measured for one camera, taken through two; summing it over the lamp’s picture counts every square pixel of the eye’s picture that shows the floor, once. So the fewest texels any single map can spend is one texel per pixel of the eye’s picture of the floor. For the floor out to 60 m in the eye’s 690 by 360 picture that is 148 thousand texels — a map 385 texels square, against 9,530 unwarped.

The bound is the obvious statement once written down. A shadow map that is perfectly matched to the eye is the eye’s own picture sampled a second time from a different place; it can never need more texels than the eye has pixels showing the surface. Everything between 90.8 million and 148 thousand is the price of taking the second picture from the lamp’s position with the lamp’s evenly spaced grid.

Where the texels go in the lamp’s picture #

The need is not spread evenly over the lamp’s picture, and the way it is spread decides what a warp can do.

The floor the eye sees lands in the lower part of the lamp’s picture, from 41 per cent of the way down to the bottom edge, across its whole width. Within that the need varies more than fifty-thousandfold. It is greatest along the top of the band — the lamp’s view toward its own horizon, where the floor near the eye, 35 m from the lamp, lands — and falls steeply down the picture toward the floor near the lamp’s feet, which is far from the eye and needs almost nothing.

So the first thing any renderer does costs nothing to reason about: fit the lamp’s frustum to the part of its picture the floor occupies. That crops the unused top of the lamp’s picture and brings the map from 90.8 million to 53.6 million texels. It is a modest saving because the unused part is less than half the picture, and it leaves the essential problem untouched — at one density, the whole crop is still paid for at the density the worst row needs.

One projective parameter #

The warp a perspective shadow map applies is a projective re-spacing of the lamp’s picture along one direction: rows crowded toward one edge the way a perspective crowds a receding floor toward its horizon, controlled by one number that says how strongly. Applied to the fitted crop’s rows, with the crowding toward the top edge where the need is greatest, it can be priced directly.

With no warp the fitted map needs 53.6 million texels. As the warp strengthens the need falls, steeply and then more slowly, to 1.42 million at its best — a map about 1,190 texels square — and rises again beyond it, as the rows at the far end of the crop are starved of the texels the near end has taken. One parameter, well chosen, takes the map from 9,530 texels square to under 1,200: sixty-four times fewer texels.

How good is one parameter against any re-spacing of the rows at all? The best row warp of any shape gives every row exactly its neediest point’s density and needs 1.11 million. The projective warp is 28 per cent above it. Its single curve cannot follow the need exactly, but it follows it well.

The reason it follows so well is the shape of the need itself. The floor near the eye is a small patch of the lamp’s picture seen at a grazing angle, and the floor near the lamp’s feet is a large patch seen steeply, so the need falls fast near the top of the crop and slowly further down. A projective warp’s density is one over the square of a linear function of the row, which falls in the same way; it is a family of curves already shaped like the need. The gap between the two curves is where the floor’s real need departs from a projective shape, and it is never more than a small factor.

What a row warp cannot follow #

That leaves the gap between 1.11 million, the best any warp of the rows can do, and 148 thousand, the best any warp at all can do — a factor of 7.5. It is larger than everything the projective warp left on the table, and it has nothing to do with cosines.

A warp of rows gives every place in one row of the lamp’s picture the same density, so each row must be paid at the density its neediest point wants. Across a row of the facing lamp’s picture the need is not constant: the floor directly between the lamp and the eye is nearer the eye than the floor off to either side at the same distance from the lamp, and needs more. A row warp spends that row’s peak density across its whole width. The factor of 7.5 is the cost of warping in one direction when the need varies in two.

A warp in both directions, or one whose density varies freely over the picture, could take that back — the bound says the need summed over the picture is 148 thousand, and any density the need can be written as is reachable by some smooth re-spacing of a square grid. What a renderer can actually build is usually a projective warp of the whole lamp picture, which is a stronger family than a warp of rows but still a single projective map; how much of the factor of 7.5 it recovers is the question the essay leaves for later, with the bound to measure it against.

The cosine is not what is left #

The earlier essay expected the residue to be the cosine ratio: the angle at which the lamp’s rays and the eye’s rays meet the surface, which no rearrangement of the lamp’s picture can change because the lamp’s picture does not know orientations. The measurement says that is only half right.

For a single surface the cosine ratio is a property of each point on it, and a warp can give each point any density it likes. So a warp matched to the floor absorbs the floor’s cosine ratio completely: the bound of one texel per pixel includes every cosine the floor has. There is nothing special about the cosine on one surface. It is just one more factor in the need.

What a warp cannot absorb is two surfaces that want different densities along one ray from the lamp. The lamp’s picture has one density per direction; a floor and a wall meeting along a lamp ray at different angles want two, and the map has to give the larger.

To price it, put a vertical wall through every point of the floor, turned toward the eye, and ask the bound again with both surfaces present. For the lamp beside the eye it rises only 12 per cent: that lamp sees the walls and the floor at nearly the angles the eye does, and the two surfaces want nearly the same density. For the lamp facing back it rises 1.70 times, the wall wanting more than the floor at 41 per cent of points. For the lamp overhead it rises 171 times, because an overhead lamp’s rays skim every vertical wall, and a surface the lamp’s rays graze needs texels without limit.

That is the part of the answer the earlier essay was right about, stated precisely. What no warp of the lamp’s picture can reach is not the cosine ratio of a surface; it is the disagreement between the cosine ratios of different surfaces seen along the same ray from the lamp. A shadow is a second projection is the reason: the lamp’s picture is a picture, and a picture has one pixel per direction.

Six ways to spend one map #

Put in order, the ways of spending one map for the facing lamp read as a descending sequence, with one rise at the end.

90.8 million over the whole picture at one density; 53.6 million fitted to the floor; 1.42 million with the best projective warp of its rows; 1.11 million with any warp of its rows; 148 thousand at one texel per pixel of the floor; 252 thousand at one texel per pixel with a wall through every point. The first step down is geometry anyone does. The second is the large one, a factor of 38, and it is bought with one number. The third is small. The fourth is a factor of 7.5 that needs a warp in both directions. The last is a rise, and it is the one no warp can undo.

Set against a tile is an off-centre frustum, which cut the eye’s view into slabs and gave each its own map, the comparison is in texels rather than in principle: a handful of cascaded maps can approach the bound too, by making each slab’s map fit its own slab. What a single warped map offers is getting within a factor of ten of the bound with one map and one parameter, which is why it was worth asking.

What the numbers are for #

The unwarped map was the wrong baseline. The 9,530 texels the earlier essay priced were the cost of the lamp’s own grid, not of the shadow. The cost of the shadow itself is one texel per pixel of the surface in the eye’s picture, 148 thousand for this floor, and every step above that is a choice about how the lamp’s picture is laid out.

One parameter does most of the work. From 53.6 million to 1.42 million is a projective warp’s single number chosen well. A renderer that fits its frustum — narrowing the lamp’s field, which a focal length is not an angle prices in texels — and warps its rows is within a factor of ten of the best any single map can do, for this lamp and this floor.

The remaining factor has two parts with different remedies. A factor of about 7.5 comes from warping in one direction only and would yield to a warp that varies in both. A factor that depends on the scene — 1.12, 1.70 or 171 here — comes from surfaces that disagree along one lamp ray, and yields only to more maps or to softer comparisons where the lamp grazes.

Where this reading stops #

Texels no larger than a pixel, by area. The requirement is on each texel’s footprint area in the eye’s picture. The earlier essay found texels arriving stretched, up to 2.9 to 1 on this floor and 56 to 1 where a lamp grazes, and a stretched texel meets an area requirement while being several pixels long in one direction. A requirement on the long side would cost more everywhere and more still where the stretch is largest.

One floor, one eye, three lamps. The scene is the earlier essay’s: a floor out to 60 m seen by an eye 1.7 m up with a 50° field. The bound is always one texel per pixel of whatever the eye sees lit, but every factor in the sequence above it depends on where the lamp stands.

The depth each texel stores is another budget. A texel holds a depth, compared against the point’s depth from the lamp, and the precision a depth buffer has left runs out in a different place from the texel size. A warped map also warps where its depth precision goes, which is not measured here.

And the warp is taken as free. Every warp here is a re-spacing of the lamp’s picture with no cost of its own. In a renderer the warp is a matrix the shadow map is drawn through and a matrix every lookup is transformed by — the same divide by w that a texture does not interpolate on the page is about — the matrices of four numbers and a window; a projective warp is one extra matrix, and a warp that varies freely in both directions is not a matrix at all.

One map, priced #

A shadow map for a lamp facing the eye needs 90.8 million texels spent evenly over its picture for none to land on the floor larger than a pixel. Fitted to the floor it needs 53.6 million; with the best one-parameter projective warp of its rows, 1.42 million; with any warp of its rows, 1.11 million. No map can need fewer than one texel for each pixel of the eye’s picture that shows the floor — 148 thousand — because a map matched to the eye is the eye’s picture taken again.

Of the gap from the projective warp to the bound, a factor of about 7.5 is warping in one direction when the need varies in two. The cosine of a single surface is not left over: a warp absorbs it as it absorbs everything else about that surface. What no warp reaches is two surfaces wanting different densities along one lamp ray, which with a wall through every point costs 1.12 times for a lamp beside the eye, 1.70 for the lamp facing back and 171 for a lamp overhead.

Still open: how much of the last factor a full projective warp takes back #

The warp priced here re-spaces only the rows of the lamp’s picture. A perspective shadow map can also be warped by a full projective map of the whole picture — a homography with eight free numbers rather than one — which crowds texels toward a point rather than toward an edge, and so can follow a need that varies across rows as well as down them.

The factor of 7.5 between the best row warp and one texel per pixel is the room such a warp has to work in. The measurement fits the best homography of the facing lamp’s fitted frustum, prices the texels it needs against the same bound, and asks how much of the 7.5 it recovers. If most of it, then one map with one matrix is within a small factor of perfect for a single surface, and the only argument left for several maps is the disagreement between surfaces. If little of it, then the across-the-row variation is shaped unlike anything a homography can follow, and splitting the map by slabs is the cheaper way to pay for it.