Three advantages of integer arithmetic for raster graphics are:

Cheap, fast operations. Historically, integer addition, subtraction and shifts needed much less hardware and execution time than floating-point arithmetic, especially on machines without a floating-point unit. An incremental Bresenham's line algorithm needs only a few additions and a decision per pixel.
Exact decisions. Provided integer overflow is excluded, the scaled midpoint line decision is exact. There is no accumulated rounding error that can move a decision across a half-pixel boundary; equality has a reproducible tie rule.
Simple storage and hardware. Integer coordinates already identify pixels. An implementation can keep coordinates and decision variables in ordinary registers and use a small add/compare datapath, avoiding conversion between floating-point numbers and integer screen addresses.

These are historical and structural advantages, not a claim that every modern processor executes every integer operation faster. An integer implementation still needs sufficient width for its intermediate results. The compact answer is

fast elementary operations; exact decisions; simple hardware and storage .

(1)

b

 0  0

Solution

 0  0

By exchanging axes, reversing endpoint order and reflecting coordinate signs where necessary, reduce a general line segment to the first octant:

Δ x = x_{1} - x_{0} > 0, 0 \leq Δ y = y_{1} - y_{0} \leq Δ x, m = \frac{Δ y}{Δ x} \in [0, 1] .

(1)

The vertical case is handled by exchanging axes. In this octant, increasing

x

by one requires increasing

y

by either zero or one. Thus, from the currently plotted pixel

(x, y)

the candidates are

E = (x + 1, y)

and

NE = (x + 1, y + 1)

Use the implicit equation of the line

f (X, Y) = Δ y (X - x_{0}) - Δ x (Y - y_{0}) .

(2)

At a fixed

X

f (X, Y) > 0

means that

(X, Y)

lies below the exact line. The midpoint line decision evaluates

M = (x + 1, y + 1/2)

, halfway between the two candidate pixel centres. If

f (M) < 0

, the exact line lies below

M

, so choose

E

; if

f (M) > 0

, choose

NE

. At equality either candidate is equally near, but a fixed tie rule is essential. We choose

NE

on a tie throughout these solutions:

f (x + 1, y + 1/2) < 0 \Rightarrow E; f (x + 1, y + 1/2) \geq 0 \Rightarrow NE .

(3)

This chooses the closest vertical-grid pixel centre in each column, with ties rounded upward. Since

0 \leq m \leq 1

, the result has one pixel per column and consecutive pixels share an edge or a corner.

c

 0  0

Solution

 0  0

Multiply the midpoint line decision by two to remove the fraction. At the current pixel

(x, y)

, maintain

d = 2 f (x + 1, y + 1/2) = 2Δ y (x + 1 - x_{0}) - 2Δ x (y - y_{0}) - Δ x .

(1)

At the initial endpoint this is

d_{0} = 2Δ y - Δ x

. If

E

is chosen, the next decision midpoint is displaced by

(1, 0)

and

d

increases by

2Δ y

. If

NE

is chosen, its displacement is

(1, 1)

and

d

increases by

2 (Δ y - Δ x)

. Both increments are constant, so the per-pixel work uses only integer arithmetic:

d_{0} = 2Δ y - Δ x, incrE = 2Δ y, incrNE = 2 (Δ y - Δ x) .

(2)

The completed code, using the tie rule of part (b), is:

void midpointLine(int x0, int y0, int x1, int y1)
{
    int dx, dy, incrE, incrNE, d, x, y;
    x = x0; y = y0;
    dx = x1 - x0;
    dy = y1 - y0;
    incrE = 2 * dy;
    incrNE = 2 * (dy - dx);
    d = 2 * dy - dx;
    drawPoint(x, y);

    while (x < x1) {
        if (d < 0) {
            d += incrE;
        } else {
            d += incrNE;
            y++;
        }
        x++;
        drawPoint(x, y);
    }
    return;
}

Thus guard1 is x < x1, and guard2 is d < 0. Multiplication by two is the only multiplication. Signed decision variables are convenient because

d

and incrNE can be negative; this remains an integer arithmetic algorithm. A strictly unsigned hardware representation would need an equivalent biased or separated-sign encoding. As with the printed int skeleton, assume all intermediate values fit the chosen type; integer overflow would invalidate the mathematical decisions.

To verify the geometry, write

k = x - x_{0}

. The chosen ordinate is

y (x) = y_{0} + ⌊ \frac{2Δ y k + Δ x}{2Δ x} ⌋ .

(3)

The midpoint line decision selects exactly this nearest integer, rounding halves upward. Its increment between successive columns is zero or one. At

k = 0

and

k = Δ x

, it gives exactly

y_{0}

and

y_{1}

, respectively, so both endpoints are included and the line segment has precisely

Δ x + 1

distinct pixels.

Figure 1.
Bresenham pixels for a slope of 3/8, with the upper pixel selected at the midpoint tie
. **Details**.

For the illustrated endpoints

(1, 1)

and

(9, 4)

, the ordinates are

1, 1, 2, 2, 3, 3, 3, 4, 4

. In particular the exact ordinate at

x = 5

5/2

, and the chosen pixel is

(5, 3)

d

 0  0

Solution

 0  0

The verifier can check the final geometric criterion directly, independently of the incremental decision variable. Set

d x = x_{1} - x_{0}

d y = y_{1} - y_{0}

, and define the scaled vertical residual

e = 2 d y (x - x_{0}) - 2 d x (y - y_{0}) .

(1)

The exact line ordinate is

y_{*} = y_{0} + d y (x - x_{0}) / d x

, so

e = 2 d x (y_{*} - y)

. Nearest-integer selection with upward ties is precisely

x_{0} \leq x \leq x_{1}, - d x \leq e < d x .

(2)

The strictness matters: at a half-integer ordinate the upper pixel has

e = - d x

and passes, whereas the lower pixel has

e = d x

and fails. Each column has exactly one accepted integer ordinate.

With reject() terminating verification unsuccessfully, suitable outline code is:

void checkPoint(int x, int y)
{
    Wide a = Wide(x) - x0;
    if (a < 0) reject();                    // inequality 1
    Wide b = Wide(x1) - x;
    if (b < 0) reject();                    // inequality 2

    Wide dx = Wide(x1) - x0;
    Wide dy = Wide(y1) - y0;
    Wide e = 2 * dy * a - 2 * dx * (Wide(y) - y0);
    Wide lower = e + dx;
    if (lower < 0) reject();                // inequality 3
    Wide upper = dx - e;
    if (upper <= 0) reject();               // inequality 4

    counter[x]++;
}

Wide denotes a signed integer type large enough for the products and differences, with conversion before subtraction. These are exactly four inequalities against zero, all applied to named integer variables. The arithmetic restriction on the drawing loop in part (c) does not restrict multiplication in this verifier. The screen endpoints are assumed valid, with

0 \leq x_{0} < x_{1} < MAX_SCREEN_WIDTH

and valid endpoint ordinates, so indexing is safe after the first two checks. These endpoint and screen preconditions belong in initialization if they are not guaranteed by the caller.

No separate

y

-range tests are needed: for

x

between the endpoints,

y_{*}

lies in

[y_{0}, y_{1}]

, and its nearest integer lies in the same interval because both bounds are integers. The counters defer detection of omissions and repetitions to part (e). As for every finite counter, use adequate capacity or a sticky failure on overflow; saturating each counter at two also suffices because only zero, one, and “more than one” matter.

e

 0  0

Solution

 0  0

After every proposed pixel has passed part (d), insist on exactly one call in every column of the closed endpoint interval:

void final()
{
    for (int x = x0; x <= x1; x++) {
        if (counter[x] != 1) reject();
    }
    accept();
}

Part (d) already rejected every out-of-range column and every incorrect ordinate. A zero counter now detects an omitted column; a counter greater than one detects a repeated call in that column. Because the residual interval in part (d) allows exactly one integer ordinate in each column, accepted calls in a repeated column must address the same pixel. Conversely, a counter of one in every column forces the complete set of nearest pixels, including both endpoints. Consecutive correct columns differ in ordinate by at most one, which proves that there are no gaps in the resulting thin line segment.

The verifier certifies the final plotted set; it need not require calls to arrive in increasing

x

order. Its final condition is simply

counter [x] = 1 for every x = x_{0}, \dots, x_{1} .

(1)

Past exam of the computer science course of the University of Oxford / 2015 / Computer graphics / 1

a

Solution

b

Solution

c

Solution

d

Solution

e

Solution

 Ancestors (9)

 Discussion (0) New discussion

 Articles by others on the same topic (0)

Past exam of the computer science course of the University of Oxford / 2015 / Computer graphics / 1

 Discussion (0)  Subscribe (1) New discussion

 Discussion (0) New discussion