Motivation
A geometric segment contains infinitely many points. A thin digital line is a finite selection of pixel centers. Before asking how to calculate that selection quickly, we must say what it should mean. A rule that chooses one center per image column is useful for a shallow segment, but it cannot represent a steep segment without leaving large gaps. A rule that rounds a height must also decide what happens when the height is exactly halfway between two rows. These are parts of the mathematical specification, rather than details to postpone until coding.
The triangle note used affine edge functions to test coverage. Here the same idea makes a complete integer algorithm for a segment whose two endpoints are integer pixel centers. We transform the segment into a shallow, rising one; compare its height with the midpoint between the only two possible next rows; and update that comparison by addition. This is a Bresenham-style midpoint line algorithm. The derivation matters more than memorizing its recurrence: it explains which inequality to use, which quantity the stored integer represents, and which changes are needed in another octant.
Our image coordinates are Cartesian, with the second coordinate increasing upward. Pixel centers are the integer pairs. A framebuffer with downward-increasing row indices can be converted into this model, or treated consistently as another coordinate convention. We include both endpoints. We assume exact integer arithmetic throughout the proof; fixed-width overflow is a separate implementation concern. Nothing here specifies a graphics API's native line-primitive coverage rule.
Definitions
Definition 2.2.1
(Canonical major and minor coordinates)
Let the distinct endpoints be and in . If , exchange the two coordinates of both endpoints and call them . Otherwise use , including equality. Reorder the endpoints so that . Put
Then and . In coordinates and , the segment runs from to and has height at integer major coordinate .
The coordinate exchange handles steepness; the endpoint ordering handles leftward or downward traversal along the major axis; the sign handles a negative minor slope. The minor coordinate is the original row for a shallow segment and the original column for a steep one. Each operation has an inverse. Thus we can prove the algorithm once for , then map every selected center back. If the original endpoints coincide, return that one center before forming a slope.
Definition 2.2.2
(Nearest-row rule, with a declared tie)
For each , select the integer minor coordinate
This is a nearest integer to , choosing the larger integer at an exact half. The physical center is before undoing any coordinate exchange. The word “larger” refers to , not necessarily to the original image row.
For negative minor slope, increasing decreases . Consequently the original minor coordinate selected at a tie can be the smaller one. The complete transform and the tie rule together define the result. Our canonical endpoint ordering gives the same output sequence when the input endpoints are exchanged. A caller wanting the original traversal direction may reverse that sequence; its pixel set remains the same.
Theorem / proposition
At a currently emitted center , the next candidates are and . Define the integer decision value
Indeed, : its sign compares the ideal next height with the midpoint of those two rows. Choose the rising candidate when , and the same-row candidate when .
Theorem 2.2.3
(Exact midpoint recurrence and nearest-row bound)
For integers and , start with , , and emit . After each decision, increment by one and use
Stop after emitting major coordinate . At every output, , and
The first and last centers are exactly and . Consecutive centers differ by or , including slopes zero and one.
The bounds are half-open intervals. At an exact half-height the chosen row lies half a unit above the ideal height, so the signed row error can equal but cannot equal . Replacing the decision by a strict positive test defines a different, tie-down algorithm. The weak and strict tests select different pixels at exact ties and are not interchangeable when reproducible coverage matters.
Concept lensGeometric
The decision as a side-of-line test
In canonical coordinates the supporting line is the zero set of . Then , so is twice the value of at the midpoint between the two candidate pixels in the next column. says that this midpoint lies on or below the line, so the line passes above it and the rising pixel is nearer; says the opposite.
Proof sketch or proof idea
Proof
(Induction on the decision value)
Set at a current output. We prove simultaneously that
Initially and , so both statements hold. If , then . Keeping and advancing changes to . Since , we also have . The displayed invariant is preserved. The new decision expression is , which is exactly the update.
If , then . Raising and advancing gives . Because and , we have . Its next decision is , again the stated update. This proves the invariant at every output, without making a floating-point approximation.
Dividing the error bounds by gives , which is equivalent to . Thus each result is the specified nearest row, and the two-candidate decision did not discard a better row. At , is an integer multiple of lying in ; the only possibility is zero, hence . The increment choices give the connectivity statement. Undoing coordinate swaps, sign changes and translations preserves distances and adjacency, proving the corresponding properties in every octant.
Proof X-ray
The stored integer is a future midpoint test
The signed quantity measures the error of the center already emitted. The decision measures the next column relative to a half-row boundary. Confusing these two moments causes a common off-by-one error: first moving to the next column and then using the old formula evaluates the wrong midpoint. The recurrence keeps both meanings aligned. The factor two removes the half, while multiplication by removes the rational slope; every comparison is therefore integral.
Theorem 2.2.4
(Distance to the closed segment)
Under the same hypotheses, every selected center is at Euclidean distance at most from the closed segment.
Proof
(Distance to the supporting line)
In canonical coordinates the supporting line is , so the perpendicular distance of to it is
This is also distance to the closed segment, rather than merely its infinite line. The algorithm is monotone and ends at , hence and . The projection parameter onto the supporting line is , lying between zero and one, so the perpendicular foot lies on the segment. This theorem bounds selected centers. It does not claim that they cover every pixel square intersected by the segment, or that a staircase has the same appearance as a filtered finite-width stroke.
Worked examples
Worked example 2.2.5
(A rational slope, with every decision visible)
Take and . No exchange, reversal or reflection is needed: , , . The ideal minor heights are and the first decision is . The table records and the decision to be used after the current output.
| Emitted center | Next move | |||||
|---|---|---|---|---|---|---|
| 0 | 0 | 0 | same row | |||
| 1 | 0 | 3 | rise | |||
| 2 | 1 | same row | ||||
| 3 | 1 | 2 | rise | |||
| 4 | 2 | same row | ||||
| 5 | 2 | 1 | rise | |||
| 6 | 3 | same row | ||||
| 7 | 3 | 0 | not used | stop |
The largest row error is , attained with opposite signs at and . The corresponding perpendicular distance is , below the bound . The values in the table are exact; rounding a running floating-point height is unnecessary.
Worked example 2.2.6
(Exact halves and endpoint reversal)
For to , the selected minor coordinates are . At the ideal height is , and at it is ; both round upward in canonical coordinates. The decisions before successive moves are . Starting with the input endpoints exchanged first restores the same canonical start , so the output is unchanged.
Now consider an alternative implementation that starts at whichever endpoint was supplied first and breaks a tie by moving its minor coordinate toward its destination. Starting at , it chooses at the first half-height. The canonical result at is . That alternative is a possible directed convention, but it is not invariant under input reversal. Declaring “round to the nearest row” without declaring the tie and ordering rules does not determine a unique pixel set.
Worked example 2.2.7
(A steep segment with a decreasing original horizontal coordinate)
Take and . Since , exchange coordinates: and . Here , , . The canonical minor sequence is . Mapping by gives
One center is emitted for each original row. Iterating only over original columns instead would provide at most three selected centers and could not produce this six-center connected path. The major-axis choice is therefore essential, not merely a speed optimization.
Complete integer procedure and boundary cases
The following pseudocode uses mathematical integers. It returns canonical major-axis order; the list may instead be streamed using a constant number of integer state variables.
function raster_line(P, Q):
if P == Q: return [P]
steep = abs(Q.y - P.y) > abs(Q.x - P.x)
if steep:
(u0, v0) = (P.y, P.x)
(u1, v1) = (Q.y, Q.x)
else:
(u0, v0) = (P.x, P.y)
(u1, v1) = (Q.x, Q.y)
if u0 > u1: exchange (u0, v0) with (u1, v1)
a = u1 - u0
s = 1 if v1 >= v0 else -1
b = s * (v1 - v0)
k = 0
D = 2*b - a
output = []
for t = 0, 1, ..., a:
u = u0 + t
v = v0 + s*k
append (v, u) if steep else (u, v) to output
if t == a: break
if D >= 0:
k = k + 1
D = D + 2*(b-a)
else:
D = D + 2*b
return output
There are output iterations. Under a constant-cost arithmetic model the time is , and the auxiliary state is if output is streamed; a stored output list takes space. Arbitrarily large integers have a bit cost, and fixed-width arithmetic must accommodate differences, doubled quantities and intermediate sums. An integer algorithm is not automatically immune to overflow.
A horizontal segment has , so no minor step occurs. A vertical segment becomes horizontal after the exchange. A diagonal with rises on every move. For example, the reversed horizontal input emits in canonical order; emits . Coincident endpoints emit one center. These cases do not need division by zero, an invented or an additional slope formula.
Including both endpoints is suitable for an isolated segment. In a polyline, adjacent segments then both emit their shared vertex. That may be harmless for a replace operation but can change blending or counting. A half-open segment convention can omit the traversal-terminal endpoint, with a separate rule for the final segment. “Terminal” must refer to the desired polyline direction, not automatically to the canonical major-axis endpoint. This ownership decision belongs to the application and does not alter the proven nearest-row calculation.
Common mistakes
Counterexample mode
Nearest-row selection is not all-touched-pixel coverage
For to our centers are . The point on the segment lies strictly inside the square centered at , with side length one and edges at half-integers. That square is touched over positive segment length, yet its center is not selected. Thus the rule is not a supercover algorithm, which would need to include every intersected pixel square under a specified boundary policy. Nor does a selected center supply a pixel-area integral: antialiasing requires a stroke footprint and a filter or sampling model.
Counterexample mode
Snapping a clipped endpoint can change later rows
The original segment to selects row one at , since its ideal height there is . Clip geometrically to : the exact new endpoint is . If we first round that endpoint to and run the integer-endpoint algorithm to , the new height at is and row zero is selected. Clipping and endpoint snapping have changed the line. Cropping the original rasterization while retaining its implicit line and phase, and rasterizing a newly snapped segment, are different specifications. This note implements the latter only when integer endpoints are the actual input; it does not supply a general rational-endpoint clipping rasterizer.
Common mistake
(Reversing the sign of the decision value but not the test)
Suppose the decision value is defined with the opposite sign, , while the rule "rise when " is kept. In the first worked example the first decision is , so and the segment would rise to , although the ideal height at is nearest to row . Whenever the sign of the implicit function changes, the inequality must change with it.
Common mistake
(Assuming ties always go to the larger original row)
The tie rule rounds the canonical minor coordinate upward, which is the larger original coordinate only when . For to the ideal height at is and the output has row . For to the canonical data are , , , and the same tie gives , hence row , the smaller of the rows and . A rule that always rounds the original row half up would choose there and produce a different pixel set.
Summary
The canonical transform fixes the major axis, traversal order and meaning of a tie. The midpoint invariant then calculates exactly the specified nearest-row selection with integer additions. Endpoint ownership, geometric clipping and filtered stroke coverage require their own rules. They should be chosen explicitly before comparing a software image with the result proved here.
Exercises
Quick check
(Why can the stored value at the last output be ignored?)
Which major coordinate would the last decision refer to?
Solution · Answer
Its sign compares a midpoint at major coordinate , beyond the prescribed closed segment. Both endpoints have already been emitted, and the invariant has established that the last minor coordinate is exactly . An extra decision would extend the rasterization rather than complete it.
Quick check
(Rasterize to . Give all centers and the decisions before the six moves. Verify the signed error invariant at every center.)
Compute , then apply the recurrence; at each center .
Solution · Guided solution
The centers are . Here ; the pre-move decisions are . The values are , all in . Their row errors are , so the maximum absolute error is . The last center is the given endpoint; no seventh move is needed.
Quick check
(Rasterize to using the full canonical transformation. State whether a tie occurs and whether reversing the input changes the pixel set.)
Exchange coordinates first, then order by the major coordinate.
Solution · Guided solution
Exchange coordinates, then order them: , . Thus , , , with . The canonical original-coordinate output is . Reverse this list for the requested traversal from . The reduced slope is , and the listed heights are never half-integers, so no tie occurs. Canonicalization makes the pixel set unchanged by input reversal.
Quick check
(In lowest terms let for a nonzero slope. Prove that an integer major coordinate with exact half-height exists between the endpoints if and only if is even. Use this to explain why the slope example has no tie.)
A tie means for an integer ; clear the denominators.
Solution · Guided solution
A tie means , equivalently . If is odd, coprimality implies divides ; the height is then an integer, a contradiction. If is even, coprimality makes odd. Set : its height is , a half-integer. Since is a positive multiple of , this is strictly between zero and . For , the denominator is odd, so no tie occurs. For zero slope, handle the case directly: every ideal height is zero, so there is no half-height tie.
Quick check
(Change the recurrence to rise only when . For to give the changed centers and the new half-open signed error bound. Does the absolute nearest-row bound survive?)
With the strict test stays on the same row.
Solution · Guided solution
The changed centers are . At a half-height the selected row is the smaller one. Therefore , or equivalently . The absolute error is still at most , but the chosen pixel set differs. A proof must mirror the strict and weak inequalities in the two branches.
Quick check
(Two polyline segments are traversed from through to . List the closed-endpoint outputs in traversal order. Give a concrete rule that emits the shared center only once without losing either exterior endpoint.)
Rasterize each segment separately, then decide which endpoint each one omits.
Solution · Guided solution
The first list is ; the second is under its own canonical tie rule with . Emit every segment except its traversal-terminal endpoint, then emit once after the last segment. This yields . For reversed segments, first restore traversal order before deciding which endpoint to omit. Equality at the corner is an ownership issue, not a failure of the nearest-row proof.
Quick check
(At a current canonical output suppose , , , . Compute , the next center and the next decision. Explain why using instead of would answer a different question.)
Use and , then apply the recurrence.
Solution · Guided solution
Here and . The declared tie rises, so the next center is , with and . The next ideal height is , exactly midway between one and two. The proposed wrong expression is : it compares the ideal height at the current coordinate with , rather than at . Applying it to the next-row decision would stay at one and violate this note's tie convention.