Comment by ColinWright
21 days ago
Hmm.
This was a long time ago, so we didn't have GPUs or fancy rendering h/ware. We addressed every pixel individually.
So a radar image was painted to the screen, and then the next update was painted on top of that. But that just gives the live radar image ... we wanted moving objects to leave "snail trails".
So what you do for each update is:
* Decrement the existing pixel;
* Update the pixel with the max of the incoming value and the decremented value.
This then leaves stationary targets in place, and anything that's moving leaves a trail behind it so when you look at the screen it's instantly obvious where everything is, and how fast they're moving.
Ideally you'd want to decrement every pixel by one every tenth of a second or so, but that wasn't possible with the h/ware speed we had. So instead we decremented every Nth pixel by D and cycled through the pixels.
But that created stripes, so we needed to access the pixels in a pseudo-random fashion without leaving stripes. The area we were painting was 1024x1024, so what we did was start at the zeroth pixel and step by a prime number size, wrapping around. But what prime number?
We chose a prime close to (2^20)/phi. (Actually we didn't, but that was the starting point for a more complex calculation)
Since phi has no good rational approximation, this didn't leave stripes. It created an evenly spread speckle pattern. The rate of fade was controlled by changing D, and it was very effective.
Worked a treat on our limited hardware (ARM7 on a RiscPC) and easy enough to program directly in ARM assembler.
Thanks for the story.
What's decrementing a pixel ?
I(x,y,t+1) = I(x,y,t) - c ?
Exactly that ... for a given pixel, reducing the existing level/brightness by some value, the default is usually 1, or a fixed percentage.
Ah! Now I understand.
I was stepping out with my wife for a day out and had read your reply very cursorily. That reading had left me quite puzzled -- "I would have done exponentially weighted moving average (EWMA) over time for trails. Why is \phi important here in any form. Is \phi the weight of the EWMA ?".
Now I get it, decrementing the pixels were quite peripheral to the main story.
The main story is that of finding a scan sequence that (a) cycles through a set of points without repetition and (b) without obvious patterns discernible to the eye.
In this, the use \phi is indeed neat. I don't think it would have occurred to me. I would have gone with some shift register sequence with cycle length 1024 * 1024 or a space filling curve on such a grid.
This becomes even more interesting if you include the desiderata that the minimum distance between any two temporally adjacent pixels must not be small (to avoid temporal hot spots).
Finding MiniMax, min over temporal adjacency, max over all 1024* 1024! sequences, might be intractable.
Another interesting formulation could be, that for any fixed kxk sized disc that could be drawn on the grid, the temporal interval between any two "revisit" events need to be independent of the disk's position on the grid.
I think this is the road to small discrepancy sequences of quasi Monte Carlo.