I’ve been thinking about ranges again, particularly after catching a book error just in time, and looking at Marc’s generic complex type. It struck me that my previous attempts were all very well, and demonstrated parallelisation quite neatly, but weren’t very LINQy. In particular, they certainly didn’t use LINQ for the tricky part in the same way that Luke Hoban’s ray tracer does.
The thing is, working out the “value” of a particular point in the Mandelbrot set visualisation is actually quite well suited to LINQ:
- Start with a complex value
- Apply a transformation to it (square the current value, add the original value from step 1).
- Does the result have a modulus > 2? If so, stop.
- Have we performed as many iterations as we’re willing to? If so, stop.
- Take our new value, and go back to 2.
We only need two “extra” bits of code to implement this: a Complex type, and a way of applying the same transformation repeatedly.
Well, here’s the Complex type – it contains nothing beyond what we need for this demo, but it’ll do. Obviously Marc’s generic implementation is rather more complete.
{
readonly double real;
readonly double imaginary;
public Complex(double real, double imaginary)
{
this.real = real;
this.imaginary = imaginary;
}
public static Complex operator +(Complex c1, Complex c2)
{
return new Complex(c1.real + c2.real, c1.imaginary + c2.imaginary);
}
public static Complex operator *(Complex c1, Complex c2)
{
return new Complex(c1.real*c2.real – c1.imaginary*c2.imaginary,
c1.real*c2.imaginary + c2.real*c1.imaginary);
}
public double SquareLength
{
get { return real * real + imaginary * imaginary; }
}
}
Simple stuff, assuming you know anything about complex numbers.
The other new piece of code is even simpler. It’s just a generator. It’s a static method which takes an initial value, and a delegate to apply to one value to get the next. It then lazily returns the generated sequece – forever.
{
T value = start;
while (true)
{
yield return value;
value = step(value);
}
}
Just as an example of use, remember Enumerable.Range which starts at a particular integer, then adds one repeatedly until it’s yielded as many results as you’ve asked for? Well, here’s a possible implementation, given the Generate method:
{
return Generate(start, x => x + 1).Take(count);
}
These are all the building blocks we require to build our Mandelbrot visualisation. We want a query which will return a sequence of bytes, one per pixel, where each byte represents the colour to use. Anything which goes beyond our maximum number of iterations ends up black (colour 0) and other values will cycle round the colours. I won’t show the drawing code, but the query is now more self-contained:
from col in Enumerable.Range(0, ImageWidth)
// Work out the initial complex value from the row and column
let c = new Complex((col * SampleWidth) / ImageWidth + OffsetX,
(row * SampleHeight) / ImageHeight + OffsetY)
// Work out the number of iterations
select Generate(c, x => x * x + c).TakeWhile(x => x.SquareLength < 4)
.Take(MaxIterations)
.Count() into count
// Map that to an appropriate byte value
select (byte)(count == MaxIterations ? 0 : (count % 255) + 1);
(The various constants used in the expression are defined elsewhere.) This works, and puts the Mandelbrot logic directly into the query. However, I have to admit that it’s much slower than my earlier versions. Heck, I’m still proud of it though.
As ever, full source code is available for download, should you so wish.
Jon Skeet's coding blog 
Very interesting. I looked at your code and once again learned something, i had no clue you needed the unsafe keyword when working with pointers.
Good stuff and the image that is generated is very interested.
LikeLike
I feel like I missed the point. Let’s see, it’s now “much slower” by your own admission, and nearly unreadable to me. Why are you proud again?
LikeLike