Help with speeding up a fractal calculation


#1

Hi everyone,

I’ve used p5.js to render a fractal image by running Newton’s method on each pixel in a 600 by 600 grid. This works well enough for rendering the image once, and my result looks like this:

fractal

But, this image takes a few seconds to render even once with all those calculations.
What I’d really like to do is be able to render the image repeatedly so that I can drag the image to recenter it, zoom in/out, etc. However, my image rendering is way too slow for that. Can anyone point me in the direction of something that would speed this up? The problem is extremely parallel in nature, so gpu.js seems like it might do the trick. But I’m not sure, and I don’t want to dive into figuring that library out if there’s a better/easier route. So, I’d appreciate any suggestions.

Thanks, in advance, and my code is below:

function setup() {
  createCanvas(600,600);
  noLoop();
}

function draw() {
  background(204);
  translate(300,300);
  for (var i = -300; i < 300; i += 1) {
    for (var j = -300; j < 300; j += 1) {
      stroke(getColor(i/200,j/200));
      point(i,j);
    }
  }
}

function newton(x,y) {
  bigCoeff = .25/(Math.pow(x*x*x-3*x*y*y,2)+Math.pow(3*x*x*y-y*y*y,2));
  return [.75*x + bigCoeff*(x*x*x-3*x*y*y), .75*y - bigCoeff*(3*x*x*y-y*y*y)];
}

function getColor(x,y) {
  red = [255,0,0];
  green = [0,255,0];
  blue = [0,0,255];
  yellow = [255,255,0];
  black = [0,0,0];

  tolerance = 0.001;
  zeroTolerance = 0.000001

  while (true) {
    if ((x-1)*(x-1) + y*y < tolerance) {
      return green;
    }
    else if (x*x + (y-1)*(y-1) < tolerance) {
      return red;
    }
    else if ((x+1)*(x+1) + y*y < tolerance) {
      return blue;
    }
    else if (x*x + (y+1)*(y+1) < tolerance) {
      return yellow;
    }
    else if (x*x + y*y < zeroTolerance) {
      return black;
    }
    else {
      [x,y] = newton(x,y);
    }
  }
}

#2

I don’t know of any magic solutions to speed this up but I might be able to point in the direction of a couple things that might help.

Probably the simplest solution is to precompute some graphics and then just display them in real-time. I do this sometimes but it limits the range of your program and requires a fair amount more hosting space so it only works in some cases. The way I normally go about it is to write a program in processing (processing normally is much faster with pixel operations). I then save images from processing and use p5.js as a means to display them in a dynamic way on the web.

I think you’re on the right track with parallel processing, I didn’t know about the gpu.js library which could be helpful. Also, web workers are a way to do parallel processing on the web but from my limited experience, they’re kinda difficult to integrate.

Another option is to look into shaders which are designed computing graphics on the GPU. I’m just learning about them myself so here’s a great book and a video series, both are in the context of the web. p5.js also has shader support so you can use anything you make in future sketches.

Best of luck!


#3

Thanks so much for the suggestions @figraham. I’m going to take a look at all of these to see what might work out. If I make any headway with one or more of them I’ll report back. :slight_smile:


#4

Some past related discussions are listed here:

“Zoom fractal mandelbrot”

You could also separate the zooming and dragging problem. Zooming is hard to get right. Simple dragging without re-rendering is easy, though – for example, pre-rendering a 600x3 * 600x3 image (essentially 9 tiles). That image could computerd in memory once and then be saved to a PImage, or it could be and you just drag it around inside the view frame – no recalculation needed.

If you approach zooming through pre-caching, you might make it cheaper by reducing the drag resolution to an aligned unit grid and reducing zoom to a set of specific scale ratios – then you have fewer potential zoom points, and fewer things to pre-cache. On a drag event, lerp to the next destination point.

There might also be another general purpose way to approach this – use a map library, and pre-calculate your output as map tiles for the geography. Some map libraries are specifically designed to support zooming through pyramids of tiles at different resolutions.


#5

Thanks so much for these suggestions @jeremydouglass. I will take a look at them.


#6

stroke/point will be super slow i believe. you’d be better off doing pixel manipulation at least. there are other things you can do as well. here is a version of your code that by my timing is heaps faster.


#7

Wow, I didn’t know anything about this. Thanks so much for the tip @hotfooted, and especially for providing the code!
This speedup may actually be good enough (I’m just demonstrating fractals to some school kids). But I’m going to continue tinkering anyway. :slight_smile:
One such tinker that occurred to me: Given that I know how it will come out, I could “cheat” and only run getColor() on a quarter of the plot. Then use symmetry to fill in the rest. Though this would only work if I keep it centered.


#8

now worries. another speedup might be just to build a table from the newton function (edit: maybe)