Fractal Generation: A Rustacean’s Prespective (2021) | Hacker News Reader

Fractal Generation: A Rustacean’s Prespective (2021)

blocr.github.io

60 pointsnxf718 comments

FWIW, I implemented[1] the exact same algorithm (except only using 2-way SIMD instead of 4-way as that's what my computer at the time supported, and relying on OpenMP's dynamic scheduling for multi-core, and doing grayscale rendering instead of color) in C 9 years ago. I did care about proper alignment, and IIRC it did help performance. I kept the relevant changes and discoveries in the commit log, although can't see right now what happened without alignment. The code is pretty ugly since I'm not relying on any auto-vectorization at all. I guess I should check which of our versions runs faster.

[1] in the "c" folder in https://github.com/pflanze/mandelbrot

(I also implemented the same algorithm again in C++ later on, cleaner, but haven't published that (yet).)

PS. I'll compare versions if you publish your full Rust code.

If you'd like to compare yourself, change `depth` in main.c to 1000, `w` and `h` in `renderScene` to your image size, and change `xcenter`, `ycenter`, and `size` to values that correspond to yours (size is simply the width of the picture in mandelbrot values, instead of pixels). Ah, but it still calculates only 2 pixels at a time, I'll need to look into that tomorrow.

Thanks for sharing. i'm interested to see a comparison and i included the link in one of the comments.

There's a lesser known optimization trick I haven't seen in a while, which is especially effective when a large portion of the Mandelbrot set is visible: there are no holes in it, i.e. it's a compact set.

From an optimization point of view, it means that if a rectangular area's edges contains only values reached the iteration limit without growing larger than the escape value, the entire area belongs to the Mandelbrot set.

The term you're looking for is "simply-connected set."

Simply-connected sets and compact sets are both sometimes informally described as "sets with no holes," but the definition of "holes" is different in both cases.

A compact set contains all of its limiting points (i.e. limits of convergent sequences of points within the set). Therefore it may not have any point-shaped holes. But it may still have a hole shaped like, e.g. an open disc.

To rule out such large holes, you want a simply-connected set, which is a connected set in which any closed path can be continuously shrunk to a point.

Not sure I'd say "no holes", but yes there are no islands, the entire mandelbrot set is connected. However that does not mean that parts of the display that's interesting doesn't cover part of the set, that's not visible in any individual pixel.

For those that want to fly around in the mandelbrot set, even a 2015 desktop can easily keep up, I suggest Xaos which I believe includes all the common mandelbrot optimizations at https://xaos-project.github.io/

There's even a web version at the above URL. It's in most linux repos I tried apt or yum. I couldn't find any docs for what optimizations Xaos uses, but it seems plenty fast for real time zooming, even on old hardware.

How do you best use this in practice? Quadtree-split the rendering area while checking edges?

I used a recursive way: split the image area, calculate the edges for all, checking edges, and then either fill it, or call the function with the sub-areas's region.

Or you can set up a grid and calculate the chunks.

When I was learning a new language in my collage days, my helloworld used to be implementing a Mandelbrot/Julia set on the given language. A few months ago I decided to look into Rust and started to work on my helloworld in Rust, using RayLib :-)

Here's an example output from my version: https://ibb.co/p4bFF7S

> I used a recursive way…

There was a Mandelbrot/Julia set renderer on the Atari ST that did the exact same thing. Instead of waiting rather long for a pixel-perfect image you could see output immediately and it got more refined with each recursive stage. On a box with a 68000 CPU @ ~8 MHz and no FPU it made for a really nice effect.

I wrote this almost a year ago and it has been sitting on my shelf unpublished. i hope someone can get something out of it.

It would be great if you put your code on github so folks could use it. Thanks !

Sorry! i forgot that https://github.com/blocr/oxidfract Thank you.

This is neat! Given how parallelizable Mandelbrot set generation is, doing it on the GPU is even faster! It’s not too hard to write a shader to do the calculation. You can use it for realtime zooms up to some limit.

I was only interested in software rendering, but now i'm curious if hardware rendering can achieve much better results.

that coincidence :). I just implemented this in c++ using shader yesterday. The code is probably not so clean as the goal was to learn how to use shaders. but the code is quite simple as it does only this. https://github.com/edmBernard/bg-generation-mandelbrot

Beautifully structured and implemented post! I'd love to see a book with 20-30 such articles of various lengths.

Having (patiently) plotted my 1st Mandelbrot in the early 80s (Z80 assembler), I really appreciated this post.

Heh. I did my first on an 8088 with a companion cyrix 8087. I started in turbo pascal, writing code based on the description in Scientific American. I later added ASM for the pixel calc, carefully hand optimizing it and managed to keep all the values in the 87's stack so I wouldn't loose the precision. I think the intel x87 used 80 bits of precision, but the Cryix used 90 bits. I then wrote an EGA driver for Turbo pascal based on a description in PC Tech Journal, so I could see Mandelbrots.

I had a university account on a ultrix system, so I ported my pascal to produce 600 dpi bitmaps compressed with RLE. But the fortran libs I could find where only on the VMS system so I moved them over to convert to postscript. The 10 foot long printer in the lab usually spat out 100 pages per minute of pure ASCII stopped for a minute or two processing my 600 dpi mandelbrot. The lab attended ran over to reboot it, I pleaded my case. They waited, were amazed at the result, and everyone wanted one.

Years later fractint came out, and each version seemed to have yet another optimization to make mandelbrots faster. One fun optimization was to surf the edge of a particular depth, then keep progressing inward. Calculating only the edges of the depth changes was fun to watch.

Reply on news.ycombinator.com