|
Newton sets |
Like the better-known Mandelbrot and Julia sets, Newton sets are colourings of the complex plane according to the number of iterations that some process, started at that point, takes to converge.
A Newton set corresponds to a polynomial with complex coefficients -- or, more conveniently for visual representations -- to a set of points in the plane, from which the polynomial is built as (x-p1) (x-p2)... where the pi are complex numbers x+yi corresponding to the x and y co-ordinates of the points
The iterative process is Newton-Raphson iteration :
x -> x - p(x) / p'(x)
and we measure convergence by waiting for successive values of the function to be closer than some small distance - say 10-6. Some sources describe the Newton set as the object obtained by colouring each point on the plane by a label indicating which root of the polynomial the iteration converged to: in my experience, this produces rather ugly, lumpy pictures, as well as slowing the iterative process down substantially, so I no longer bother to record that information.
For polynomials of reasonable degree, the iteration can be rather slow: multiplying two complex numbers takes four FP-multiply instructions, and evaluating a polynomial of degree n requires 2n complex multiplications. Evaluating the derivative takes n-1 more (we don't have to recompute the powers of x ), and the final division requires six FP-multiply instructions and one FP division.
The result of all this computation - my current implementation, which uses SSE2 to compute the polynomials efficiently, takes about 2.2 seconds to compute a 1024x1024 image on a P4/1300: see here for some implementation notes - is, if you've chosen the points appropriately and picked a suitable colour-map, a quite startlingly beautiful filigree pattern: thin, graceful chains rather than the brash spirals and sea-horses of the Mandelbrot world. Moreover, by moving the points around the complex plane, the filigree patterns morph together in a continuous, seamless and always-surprising way.
Some images are reminiscent of jewelled necklaces, some of arcing lightning in a Hollywood mad scientist's laboratory, some of cell division, some of bubbles in boiling liquid. The animations are reminiscent of a wildly complex but decorous dance, as chains of delicate patterns bow to one another, or swap off in fantastic complexity.
 |
|
 |
 |
 |
|
I'm not yet anything like finished on this project: I've slightly gone off at a tangent, looking for good ways to store and play the animations. I'd prefer a lossless compression format, and I'd quite like to be able to handle animations of a few thousand 1024x1024 frames: so I need the compressed format to be small enough to load sixty compressed frames from hard disc in a second, and decompress one while reading the next. I don't know of any standard tools for this; at the moment I'm not bothering with compression, just saving consecutive frames one after the other and using MRIcro, a wonderful program written by my housemate Chris Rorden and designed to display volume data acquired from MRI scanners, to load the frames as a 1024x1024x256 object and display consecutive slices.
My current thought on the compression is here; it's inspired by quad-trees and MIP-mapping, though at the moment it produces results which are about a third the size of the original images, and when ZIPped compress by a further factor two, to something only slightly longer than ZIPping the original image.
I'm also not at all sure what a good user interface for a program for setting up points to move along paths to produce animations would be: that's a slightly longer-term project.