A tilted span walks a staircase

Along a line of constant depth the page is affine found the one direction in which a renderer can step a texture across a receding surface without dividing at every pixel. Every plane meets each plane of constant camera depth in a line parallel to the picture, those lines image parallel to the plane’s own vanishing line, and along one of them the projection is affine: the worst texel on a 120-pixel span is $7\times10^{-14}$ px. Bank the floor twenty degrees about the line of sight and that direction tips by the same twenty degrees, so the page’s rows — exact on a level floor — are 13.26 px out.

The obvious consequence is that a renderer should walk the tilted direction rather than the rows. The obvious objection is that the page is made of rows. A span at twenty degrees crosses a new page row every 2.9 pixels, and a renderer does not visit the span, it visits pixels — so the walk is a staircase, and the pixels of a staircase are not on the line.

This measures what the staircase costs, and what has to be bought with it.

The pixels are not on the line #

A renderer walking a tilted span visits the grid point nearest the ideal line at each step. That pixel sits up to half a pixel off the line, perpendicular — and half a pixel perpendicular to a constant-depth line is a change of depth.

So that exactness belongs to the line and not to the walk. The attribute a renderer hands a pixel is the one the ideal line carries at the foot of the perpendicular; the attribute the surface actually has at that pixel is a different one, because the pixel is at a different depth. The difference is the staircase’s cost, and it is measured here the same way every error in this field is measured — in pixels of page along the span, so it can be set beside the 13.26.

On a floor banked twenty degrees, a 120-pixel span a hundred pixels below the horizon costs 0.577 px snapped, against $2\times10^{-14}$ unsnapped. The staircase is real and it is small.

Twenty-three times better, and never worse #

The comparison to make is between that number and what the same span costs along a row.

A row walk’s error is the closed form in the depth ratio between the span’s ends, and it grows steadily with the bank: 0.63 px at one degree, 3.15 at five, 13.26 at twenty, 40.0 at forty-five. The snapped tilted walk stays between 0.15 and 0.76 px across the same range.

At a twenty-degree bank the tilted walk is twenty-three times better. At forty-five degrees it is better by a factor no number properly describes, because the staircase there costs nothing at all. And at one degree, where a row walk is only 0.63 px out and hardly worth replacing, the tilted walk is still 0.15 px — it never loses.

That answers the first half of the question. Snapping tilted spans to the pixel grid leaves a texel error far smaller than the row walk makes on the same banked floor, at every bank.

It is worth noticing what the two curves are made of, because they are not the same kind of quantity. The row walk’s error is geometry: the depth ratio between a span’s ends, which the surface and the camera fix between them, and which a texture does not interpolate on the page gave in closed form as $(\sqrt{k}-1)/(\sqrt{k}+1)$ of the span’s length. Nothing a renderer does changes it except dividing. The tilted walk’s error is arithmetic: where a line of a given slope falls relative to a lattice of unit squares. The first grows without limit as a surface recedes or tips; the second cannot exceed what half a pixel of offset is worth, whatever the scene does.

That difference is the reason the comparison is so one-sided, and it is also the reason the result is robust. A scene twice as deep, a lens twice as long or a floor twice as steep moves the row walk’s curve and leaves the staircase’s where it is.

The cost is the grid’s, not the floor’s #

The second half asked how the error depends on the bank angle and on the depth. Neither dependence is the one the question expected.

Swept finely, the staircase does not grow with the bank. It jumps about, reaching 1.22 px at its worst and collapsing to nothing at a forty-five-degree bank, where the line’s slope is exactly one and every step of the walk lands on the line. The cost of a nearest-pixel walk depends on how nearly the line’s slope is a ratio of small whole numbers, which is a fact about the grid and about arithmetic, and not about the floor.

The dependence on depth is just as lopsided. Near the horizon, where the floor recedes fastest, a row walk on a banked floor is 35.65 px out on a 120-pixel span; a hundred and ninety pixels down the page it is 6.92. The staircase over the same range runs between 0.404 and 1.118 px, and not monotonically — it does move, and it is not tracking the recession. Half a pixel off a constant-depth line is half a pixel wherever it is, and what that costs is set by how fast the attribute changes across the line, which near the horizon is large and far down small. The two effects partly cancel.

So the tilted walk is not merely better; it is better in a way that does not deteriorate where a renderer is most exposed. The row walk’s error is worst exactly where a floor’s texture is most compressed, and the staircase’s is not.

What has to be bought with it #

Nothing here is free, and along a line of constant depth the page is affine named the price: neighbouring spans must tile the surface without gaps or double-drawn pixels.

They do not tile. Twenty-four spans a pixel apart across a banked floor draw 1,368 pixels between them and cover 1,315 distinct ones: 53 pixels — 3.9 per cent — are visited twice, and none is missed. The double visits are harmless for an opaque surface and are not harmless for anything that accumulates: a blend, a stencil count, an additive light.

That no pixel is missed is worth as much as the count of doubles, and it is not an accident of this band. Spans spaced a pixel apart along the direction of steepest depth change are spaced a little more than a pixel apart on the page, because that direction is not aligned with either axis of the grid; rounding each span’s pixels inward is what produces the overlap, and rounding is also what prevents the gap. A scheme that spaced the spans to avoid the overlap would produce holes instead, and a hole is the worse defect — a pixel drawn twice is wrong in a way that shows only under accumulation, and a pixel drawn never is wrong in every picture.

That is the bookkeeping a tilted-span renderer owes, and it is the honest form of the last part of the question — at what bank a per-pixel division is cheaper than walking tilted spans. The answer is that the comparison is not between two errors, because the tilted walk’s error is under 1.22 px at every bank and a divide’s is zero. It is between a divide at every pixel and the cost of deciding, once per pixel, which span owns it. A renderer that already writes each pixel exactly once has that bookkeeping; one that does not has to build it, and the pixels it would draw twice are the reason.

Why a nearest-pixel walk is as good as it is #

The staircase’s size deserves an account, because half a pixel of perpendicular offset sounds like it should cost more than it does.

The attribute being stepped along a constant-depth span changes with position on the page in two ways. Along the span it changes affinely, which is the result along a line of constant depth the page is affine reached, and is why the span was chosen. Across the span it changes with depth, and near the horizon it changes fast. So the cost of being half a pixel off the line ought to be the gradient across the line, times a half.

It is not, and the reason is that a renderer hands the pixel the attribute at the foot of the perpendicular rather than at the span’s own centre. Two of the three errors a half-pixel offset could produce cancel there: the along-the-span position is right, and the depth is wrong only by what the perpendicular half-pixel changes it by. What remains is the second-order term — the curvature of the attribute across the line — and a second-order term in a half pixel is small.

That also says where the scheme would break. If the perpendicular offset were a whole pixel rather than half of one, the term would be four times larger; if a renderer stepped along the nominal direction rather than recomputing the foot at each pixel, the error would be first-order in the offset instead of second and the staircase would cost tens of pixels rather than tenths. The scheme is good because of a detail in how the attribute is looked up, and a renderer that skipped that detail would find the tilted walk no better than the rows.

What a renderer would actually decide #

Three readings, in the order a renderer would need them.

A banked surface is worth walking tilted. The error falls by a factor of twenty-three at a twenty-degree bank and by more at steeper ones, and it never rises above 1.22 px at any bank, which is under the tolerance a texture filter already imposes. A pixel is not a point is the essay about why a pixel’s own extent is the floor under any such tolerance.

A nearly level surface is not. At one degree of bank a row walk is 0.63 px out and the tilted walk 0.15, so the whole gain is half a pixel and the bookkeeping is the same bookkeeping. There is a bank below which the scheme is not worth its complexity, and on these numbers it is somewhere around two or three degrees — not because the tilted walk gets worse but because the row walk stops being bad.

And a surface whose bank varies across the frame is the hard case. A curved screen is eight flat ones is the same difficulty in another part of the pipeline: a surface that is not one plane is handled by being cut into planes, and what the cutting costs is a separate measurement from what each piece costs. The constant-depth direction is the plane’s own vanishing line, so it is one direction for one plane, but a scene is many planes at many banks and each wants its own walk. A renderer choosing per triangle pays the bookkeeping per triangle, which is where one plane is nearly free and the cost of a plane change becomes the question.

What this does not settle #

One floor, one frame, one field. The camera stands 1.5 m up with a sixty-degree field on a 690 × 400 frame, and the spans are 120 px long. A longer span crosses more rows and a shorter one fewer, and the staircase scales with neither in a simple way, because its size is a property of the slope rather than of the length.

The walk is nearest-pixel and nothing else. A renderer could sample each pixel’s own position rather than the line’s, which removes the staircase entirely and reintroduces a division — that is the trade this essay is about, and only one side of it is measured here. Supersampling, or a half-pixel offset chosen per span, would both move the number.

The attribute is position on the surface. Every error above is a texel error in page pixels, which is the currency a texture does not interpolate on the page established. A renderer interpolating a colour, a normal or a depth code has the same geometry and a different tolerance, and depth is a reciprocal is about why the last of those is the touchy one.

The double-drawn pixels were counted, not repaired. Deciding which span owns a contested pixel is a rule, and a rule that assigns each pixel to exactly one span changes which attribute it receives — by up to the same half-pixel offset, on the losing span’s terms. The divide is postponed is the essay about the discipline of doing arithmetic in the right order, and this is a place where the order has not been settled.

And the surface is a plane. A curved surface has no constant-depth lines at all in this sense, and the tilted-span scheme has nothing to walk along. What it has instead is the plane of each triangle, which is what a renderer actually works with, and the approximation error of that is not measured here.

The staircase, priced #

A span along a banked floor’s own constant-depth direction is exact and a renderer cannot visit it. The pixels it visits instead sit up to half a pixel off the line, perpendicular, and perpendicular to a constant-depth line is where the depth changes.

Snapped to the grid, a 120-pixel span on a floor banked twenty degrees costs 0.577 px of texel where the same span along a page row costs 13.26 — twenty-three times better — and across banks from one degree to forty-five the snapped walk never exceeds 1.22 px while the row walk runs from 0.63 to 40.0.

What the staircase costs is a fact about the grid and not about the floor. It collapses to nothing at a forty-five-degree bank, where the slope is one and every step lands on the line, and it stays between 0.404 and 1.118 px down the whole picture where the row walk runs from 35.65 px near the horizon to 6.92 far down it.

The price is bookkeeping. Twenty-four spans a pixel apart draw 53 of their 1,368 pixels twice, so a renderer walking tilted spans has to decide which span owns each pixel — which is a different kind of cost from a division and is the reason the choice is not simply arithmetic.

Still open: whether a triangle can be walked in its own frame #

Everything above walks spans across a surface and snaps them to the page’s grid, because the page’s grid is where pixels are. The staircase exists entirely because those two lattices are not aligned, and the measurement shows the cost is a property of the angle between them.

There is an arrangement in which they would be. A renderer could rasterise a triangle in a frame of its own — one axis along the constant-depth direction, the other across it — producing samples on a lattice that has no staircase at all, and then resample that image onto the page’s grid once at the end.

The question with a number in it is what the resampling costs against what the staircase costs. A resample is a filter and a filter blurs; the tilted lattice’s samples would be spaced differently from the page’s, by a factor that depends on the bank, so the reconstruction is not free and its error is not a texel error but a loss of sharpness. The measurement that settles it draws the same banked floor both ways at the same sample count, compares the two against a heavily supersampled reference, and asks at what bank a resample’s blur first exceeds the 1.22 px the staircase costs at its worst — and whether the answer moves when the texture is a checker rather than a gradient, since a filter’s damage depends on what is being filtered and a texel error’s does not.