- Bresenham's line-drawing algorithm is a first-order delta-sigma
converter. This isn't news to the world, but it was news to me.
When I use a first-order delta-sigma converter instead of the usual
PWM crap to drive the LEDs to fade, they flicker a lot less.
A kragen-hacks post is on the way.
Anti-aliasing in time?
Of course, whether PWM is crap or not depends upon your final time
constant. If the output is too fast, even delta-sigma won't properly
average out for reconstruction and one will see the digital PDM
waveform instead. Economically, if actors in markets are too
responsive, this translates into boom-bust cycles. Personally, I find
it valuable to consciously low-pass the ups and downs of daily
experience[0] -- it stands to reason that keeping one's equilibrium
results in a more accurate perception of the underlying input waveform.
On the other hand, if the output is slow enough, even PWM is good
enough. We have a TIG inverter which I believe has its current
controlled by PWM, and since the relevant time scale for even a tiny
manual weld pool[1] is on the same order as eighth- or sixteenth-notes,
PDM would probably just introduce more switching losses without any
improvement in the ultimate process. Think of "jaggies" with Bresenham
-- one winds up at the same place with PWM as PDM, but by following the
edges of the rectangle, rather than working along the diagonal. When
the rectangles are on the order of the pixel size, there's not much
difference.
There's a theoretical parallel to all of this as well: one can think of
batch computation as being the PWM pattern: first we provide all the
inputs, then get all the outputs, whereas interactive computation (or a
unix pipeline composed of online components) is the PDM pattern: inputs
and outputs interleaved smoothly over the course of execution. On a
finer scale, one can look at the patterns of substitutions and
reductions over the course of a computation -- it is theoretically
possible to follow the PWM style, and do all of the substitutions,
followed by all of the reductions, but the exponential blow ups
involved mean that we usually compute more in the PDM style, and
interleave substitutions with reductions.[2]
Floyd-Steinberg and other error-diffusion dithers seem to be the
equivalent for spatial, rather than temporal, smoothing. It makes
sense that PWM would result in a more "posterized" LED pattern than
PDM.
I wonder what other SIMDish operations are enabled by
perfect-shuffle. The idea that perfect-shuffle is useful for doing
the Walsh transform isn't new, but I haven't seen it suggested in
the context of implementations on CPUs before.
Entries in an ordered-dither matrix are generated by the
perfect-shuffle of the coordinate values.
Last month I ran across two independent sources which were wishing for
such an instruction, and unfortunately can't remember them now. (SIMD
was definitely the context, though -- somewhat like a bit-level zip?)
I think Knuth argues that as long as we're throwing silicon at things,
might as well use 64-bit registers to do arbitrary 8x8 boolean matrix
multiplies, of which shuffles are special cases.
- the persistence-of-vision lettering is actually quite hard to see,
partly because it appears backwards half the time ... partly because
it appears in a different position on every stroke.
How about trying to phase lock (or simply trigger) on a little
ball-bearing switch? It might sound like shaking up spraypaint, but
should be pretty cheap...
-Dave
:: :: ::
[0] in general, people (both for raw sense data[3] and for emotions)
are very insensitive at low frequencies, and as stampedes and riots (or
their larger cousins, wars) show, overly sensitive at high frequencies.
I wonder what the human equivalent of a gyrator[4] would be?
[1] welding is one of those cases where one can't distinguish between
DC and AC simply by what frequencies occur in the spectrum. A pool of
molten Al reacts differently depending upon which direction the current
is flowing -- to the torch, or to the work -- and so even a pulsed
square wave, which as far as a mathematician is concerned has plenty of
high-frequency harmonics, and hence would seem to be AC, behaves like
DC as far as the metal is concerned, unless some of the pulses actually
have their polarity reversed.
[2] in this model, one can compute (bresenham: move horizontally) or
output (bresenham: move vertically). Would a transaction system, where
one can output UNDOes as well as DOes, then be somewhat like a
second-order delta-sigma?
[3] I was taught the CS view of neurons, in which after integrating a
certain amount of input excitation, they produce an output spike, and
reset the integrator. That sounds quite a bit like the inner loop of
bresenham, which outputs a vertical and resets after integrating a
certain amount of error. Is the biologists view of a neuron at all
close?
[4] a device which synthesizes an inductance from amplifiers and
capacitances. How many differentiators does it take to build an
integrator?
