Content deleted Content added
→Algorithm: Replaced ipart() with floor() to avoid ambiguity around rounding. |
→Algorithm: Follow-up to previous edit: added animation and original symmetrical integer form of Wu's algorithm |
||
| (One intermediate revision by the same user not shown) | |||
Line 17:
==Algorithm==
Like [[Bresenham's line algorithm|Bresenham’s line algorithm]], this method steps
along one axis and considers the two nearest pixels to the ideal line. Instead of
choosing the nearest, it draws both, with intensities proportional to their vertical
distance from the true line. This produces smoother, anti-aliased lines.
[[File:Wu-line-animation.gif|thumb|Animation showing symmetry of Wu's line algorithm ]]
The pseudocode below assumes a line where <math>x_0 < x_1</math>, <math>y_0 < y_1</math>,
and the slope <math>k = \frac{dy}{dx}</math> satisfies <math>0 \le k \le 1</math>. This
is a standard simplification — the algorithm can be extended to all directions using symmetry.
The algorithm is well-suited to older CPUs and microcontrollers because:
* It avoids floating point arithmetic in the main loop (only used to initialize d)
* It renders symmetrically from both ends, halving the number of iterations
* The main loop uses only addition and bit shifts — no multiplication or division
<syntaxhighlight lang="python" line="1">
function draw_line(x0, y0, x1, y1)
N := 8 # brightness resolution (bits)
M := 15 # fixed-point fractional bits
I := maximum brightness value
# Compute gradient and convert to fixed-point step
k := float(y1 - y0) / (x1 - x0)
d := floor((k << M) + 0.5)
# Start with fully covered pixels at each end
img[x0, y0] := img[x1, y1] := I
D := 0 # Fixed-point accumulator
while true:
x0 := x0 + 1
x1 := x1 - 1
if x0 > x1:
break
D := D + d
if D overflows:
y0 := y0 + 1
y1 := y1 - 1
# Brightness = upper N bits of fractional part of D
v := D >> (M - N)
img[x0, y0] := img[x1, y1] := I - v
img[x0, y0 + 1] := img[x1, y1 -1] := v
</syntaxhighlight>
===Floating Point Implementation===
<syntaxhighlight lang="pascal" line="1">
| |||