Skip to article frontmatterSkip to article content
Site not loading correctly?

This may be due to an incorrect BASE_URL configuration. See the MyST Documentation for reference.

N-D Bresenham: Cython, and why other libraries disagree

_bresenham_nd (compiled locally from bresenham_nd_local/_bresenham.pyx) is the N-D form of scikit-image’s integer Bresenham. In 2-D it matches _line bit for bit. It does not always match ITK’s BresenhamLine or Zingl’s published plotLine3d.

This notebook settles why. The pixel counts agree (Chebyshev length); the paths diverge only on ties, and each library’s ties come from a different place in the arithmetic.

Coordinates are in array order: the first index runs down / along axis 0.

1. The problem, on one short segment

Take (0, 0) to (1, 4) in 2-D. Major length D = 4 is even. Both libraries draw five pixels; they disagree on which row sits at column 2.

ours  [(0, 0), (0, 1), (1, 2), (1, 3), (1, 4)]
zingl [(0, 0), (0, 1), (0, 2), (1, 3), (1, 4)]
ITK   [(0, 0), (0, 1), (0, 2), (1, 3), (1, 4)]
line  [(0, 0), (0, 1), (1, 2), (1, 3), (1, 4)]
<Figure size 924x242 with 3 Axes>

ours matches _line (steps early at the half). The Zingl rule steps late. ITK lands on the same pixels as Zingl here only because its float LastIndex is already distorted for this segment ((1, 5) instead of (1, 4)); when that distortion is absent, ITK matches ours instead (section 4).

2. Three algorithms, three midpoint tests

All three walk Chebyshev length D = max(|Δ|), advancing the major axis every step and deciding when each minor axis keeps up. They differ in the error state that implements the midpoint test.

Ours (scikit-image / notebook bresenham_nd)

For minor delta d and major length D:

error ← 2·d − D
each major step:
    if error ≥ 0:  step minor;  error ← error − 2·D
    error ← error + 2·d

The decision error ≥ 0 is the cleared form of y(k+1) ≥ m + 1/2 from on_lines.md: an exact half steps early. The major axis is not run through this test; it advances unconditionally.

Zingl plotLine3d (easyfilter)

From Zingl’s site. Every axis, including the major, shares one pattern:

err ← D // 2          # integer division
each step (D + 1 times, emitting the current voxel first):
    err ← err − d
    if err < 0:  step this axis;  err ← err + D

For the major axis d = D, so err goes from D//2 to D//2 − D < 0 every time and the major always steps — same cadence as ours, different bookkeeping.

The midpoint convention is the other way around: err < 0 after subtracting d, with initial D//2. When D is odd, D//2 truncates and the two rules align. When D is even, D//2 is an exact half and the < versus ≥ choices disagree on the tie.

ITK BresenhamLine

The integer core (once a LastIndex offset is chosen) is

accum ← 0
each major step:
    for each minor axis:
        accum ← accum + 2·distance
        if accum ≥ D:  step;  accum ← accum − 2·D

Measured below: when LastIndex equals the true integer p1 − p0, this emits exactly our pixels. So ITK’s integer walker is not a third tie-breaking rule — it matches scikit-image.

The Index→Index API does not feed it p1 − p0 directly. It builds a float direction, normalises it, and sets

LastIndex[i] = int( length · Direction[i] )
length = max_i(|p0[i] − p1[i]|) + 2     # max(|Δ|) + 1, plus one

Truncation after normalisation can make LastIndex ≠ p1 − p0. The walker then follows a different line in offset space and stops early when it hits the true endpoint. That is where ITK diverges from ours.

3. Mechanism A — Zingl: even major length

ours vs Zingl-style, D even: 456/1152 (39.6%)
ours vs Zingl-style,  D odd: 1200/1200 (100.0%)
ours vs Zingl-style,    all: 1656/2352 (70.4%)

On this ±3 box, every disagreement with the Zingl rule has even D. With odd D the two sequences are identical.

ours:  initial error = 2d - D = -2   step on first decision? False
zingl: initial err = D//2 = 2
       after err -= d:    1   step? False

For (0, 0) → (1, 4): D = 4, d = 1. Ours opens at error = 2·1 − 4 = −2 and only steps the minor axis once error has climbed to a non-negative value — which, with the ≥ 0 rule, puts the halfway column on the upper row. Zingl opens at err = 2, subtracts d to 1 (still non-negative), and does not step yet — so the halfway column stays on the lower row. The figure in section 1 is that single tie, drawn.

4. Mechanism B — ITK: float LastIndex

LastIndex == p1 - p0 : 384/2352

LastIndex distorted  : 1968/2352
ours vs ITK when LastIndex intact   : 384/384 (100.0%)
ours vs ITK when LastIndex distorted: 1264/1968 (64.2%)

When the float path preserves the integer delta, ITK and ours agree completely. Every disagreement is a distorted LastIndex.

segment (-3, -3) → (-2, -1)
  true delta     : (np.int64(1), np.int64(2))
  ITK LastIndex  : (np.int64(1), np.int64(3))   (length parameter 4)
  ours           : [(-3, -3), (-2, -2), (-2, -1)]
  ITK            : [(-3, -3), (-3, -2), (-2, -1)]
<Figure size 660x264 with 2 Axes>

The true delta is (1, 2). After normalisation ITK asks for offsets (1, 3). The integer walker is then the same algorithm as ours, but aimed at a different stop. The path therefore takes the late minor step that ours rejects, until it lands on the real endpoint and breaks.

5. How often, on a fixed corpus

comparison                                   agree
ours vs skimage _line                    2352/2352  (100.0%)
ours vs Zingl-style (all D)              1656/2352  (70.4%)
ours vs Zingl-style (D odd only)         1200/1200  (100.0%)
ours vs Zingl-style (D even only)         456/1152  (39.6%)
ours vs ITK (all)                        1648/2352  (70.1%)
ours vs ITK (LastIndex intact)            384/384   (100.0%)
ours vs ITK (LastIndex distorted)        1264/1968  (64.2%)
3-D corpus (200 segments)
  zingl_nd port == Zingl's C plotLine3d: 200/200 (100.0%)
  ours == Zingl's C plotLine3d         : 114/200 (57.0%)
  ours == ITK port                     : 154/200 (77.0%)

The Python Zingl port matches Zingl’s own compiled plotLine3d (bresenham_nd_fixtures/zingl_line3d.c) on every 3-D trial here, so the even-D story is not an artefact of reimplementation.

6. What is not going wrong

The differences are different definitions of the same informal name. Bresenham’s 2-D paper leaves the half-pixel tie to the implementer; N-D ports inherit that freedom and then add their own pre-processing (ITK’s float direction).

7. Side-by-side summary of the mechanisms

ours / _lineZinglITK Index→Index
Major advanceunconditionalsame pattern as minors (d = D always fires)unconditional
Initial minor error2d − DD // 20, then += 2d before test
Tie testerror ≥ 0 → step earlyerr < 0 → step latematches ours when delta intact
Extra distortionnonenone (pure integer)LastIndex = int(length · dir̂)
When it matches ours—iff D is oddiff LastIndex == p1 − p0

8. Cython note (stack scratch, 2-D timing)

_bresenham_nd keeps scratch (delta, step, error, at) on a stack array of length _BRESENHAM_MAX_NDIM = 32. Against _line on the ±7 box (50625 segments), after that change:

±7 box: _line 157.8 ms,  _bresenham_nd 108.8 ms,  ratio 0.69x
identity vs _line on full ±7 box: 50625/50625 (measured at Cython bring-up)

Short lines favour the N-D entry after stack allocation; long lines still pay for the axis loop and (ndim, n) stores. That cost is separate from the tie-breaking story above.

9. What not to do

Do not “fix” _bresenham_nd to match ITK or Zingl in order to clear a diff. That would break identity with _line / Pillow / the 2-D Bresenham documented in on_lines.md. If an N-D API must match ITK voxel traversal, expose it as a separate method and document the float LastIndex step.

Do not treat raster_geometry as buggy for disagreeing: it implements Zingl’s published N-D form, including its even-D halves.

Do not use raw ITK Index→Index, Zingl, or raster_geometry as bit-identical regression oracles for an early-step _bresenham_nd. Section 10 says what to use instead.

10. Proposed tests (keep early-step, still test against others)

The goal is lock-in without circularity: keep the early-step rule (same as _line), but do not only assert “Cython matches Cython”. Use oracles that share that rule, plus properties that any correct walk must satisfy, plus one negative check that the Zingl rule was not adopted by mistake.

Suite shape

  1. Invariants on a random N-D corpus (always on).

  2. 2-D cross-implementation: _bresenham_nd ≡ _line ≡ Pillow. OpenCV LINE_8 is only a soft check: even with column-decreasing ends it still disagrees on many ties (~90% on the ±3 in-canvas set).

  3. N-D same-rule oracles: Cython ≡ pure-Python spec ≡ ITK-style integer walker with LastIndex = p1 − p0 (no float normalise).

  4. Checked-in fixtures from (3), so CI need not ship ITK.

  5. Negative: on a fixed even-D set, sequences differ from Zingl.

Skip as equality oracles: Zingl / raster_geometry, ITK’s float LastIndex path, and OpenCV (tie rule differs from _line / Pillow).

10.1 Spec in pure Python (docstring as oracle)

Cython vs Python spec (2-D ±3 box): 2352/2352 (100.0%)

10.2 ITK integer walker, deltas forced intact

ours vs ITK integer walker (forced Δ): 2352/2352 (100.0%)
ours vs ITK Index→Index (float LastIndex): 1648/2352 (70.1%)

10.3 2-D: Pillow (hard); OpenCV (soft only)

Pillow matches _line / early-step on this corpus. OpenCV does not: e.g. (0, 0) → (1, 2) is [(0,0), (1,1), (1,2)] for ours/Pillow and [(0,0), (0,1), (1,2)] for cv2.line(..., LINE_8), even after ordering ends with decreasing column. Treat OpenCV as documentation of a different tie convention, not as a pytest equality oracle.

ours vs Pillow (2-D, in-canvas): 240/240 (100.0%)
ours vs OpenCV LINE_8 (column-decreasing ends): 216/240 (90.0%)
proposal: do not assert OpenCV equality; Pillow is the 2-D library oracle

10.4 Library-agnostic invariants

invariants (length, ends, unit steps): 240/240 (100.0%)
translation invariance: 240/240 (100.0%)

10.5 Negative check: still early-step, not Zingl

even-D segments that differ from Zingl: 696/1152 (60.4%)
proposal: assert differ / len(even_D) > 0.5  (locks early-step; Zingl is late on ties)

10.6 What to check into the repo

ArtefactPurpose
Python bresenham_nd_spec in the test moduleSpec ↔ Cython
itk_integer_walker or precomputed JSON from itN-D external early-step oracle without ITK wheels
Small Pillow 2-D casesIndependent 2-D library (early-step)
Optional OpenCV note / soft checkDocuments a different tie convention
Property tests aboveNo second Bresenham required
One even-D “differs from Zingl” caseGuard against swapping tie convention

The existing bresenham_nd_fixtures/ours_bresenham_nd.json locks current Cython output; replace or supplement it with fixtures from itk_integer_walker / the Python spec so the oracle is not only “yesterday’s binary”.

Summary

ClaimEvidence
ours ≡ _line in 2-Dfull ±7 box at Cython bring-up
ours ≠ Zingl on ties100% agree when D odd; ~40% when D even (±3 box)
Cause of Zingl gapD//2 init and err < 0 vs 2d − D and error ≥ 0
ours ≠ ITK on ties100% agree when LastIndex == Δ; all misses are distortions
Cause of ITK gapIndex API normalises a float direction before the integer walker
How to test anyway§10: spec, ITK integer walker, Pillow, invariants, anti-Zingl

Fixtures for these corpora live under bresenham_nd_fixtures/. Measured with the local bresenham_nd_local Cython build, Zingl’s plotLine3d (bresenham_nd_fixtures/zingl_line3d.c), ITK algorithm from itkBresenhamLine.hxx v5.4.0 (Python port).