Рисуем фракталы на Java

Для одной задумки понадобилась библиотека, для работы с bmp изображениями. Найти ее было не сложно. Сейчас чего-только не написали уже для Java. Спасибо Nayuki Minase за то, что он потрудился и написал библиотеку для работы с bmp.

И вот я конечно же ищу сэмплы, чтобы разобраться как сие диво работает. И что вижу? Одна из демок рисует Множество Мандельброта. Ну вот я и завис, уж простите. В прошлом, когда еще кодил на Delphi я тоже завис - на по-дольше. В результате родилась такой вот фрактальный браузер. Сегодня я решил помянуть это и написать свою версию рисовалки фракталов на основе библиотеки работы с bmp рисунками.

Вот один из рисунков в большом разрешении (клик по рисунку увеличит его, но осторожно - там 20 мег)...
А теперь о реализации (исходник можно скачать тут (зеркало), осторожно внутри исходники библиотеки по работе с BMP, она распостраняется по MIT лицензии).

Итак интерфейсик Фрактала

public interface Fractal {
    Position getZoom();

    int getFunction(double x, double y, int iterations);
}

Вот Мандельброт

public class Mandelbrot implements Fractal {
    private Position mandelbrot = new Position(-1.9, 0.5, -1.2, 1.2);

    @Override
    public Position getZoom() {
        return mandelbrot.zoom(40).move(-1.25, 2).zoom(5);
    }

    @Override
    public int getFunction(double a, double b, int iterations) {
        double r = 0;
        double x = 0;
        double y = 0;
        int color = iterations;
        while (color > 0 && r < 4) {
            double x2 = x * x;
            double y2 = y * y;
            double xy = x * y;
            x = x2 - y2 + a;
            y = 2 * xy + b;
            r = x2 + y2;
            color--;
        }
        return color;
    }
}

Вот Джулия

public class Julia implements Fractal {

    @Override
    public Position getZoom() {
        return new Position(-1.59, 1.527, -1.558, 1.558);
    }

    @Override
    public int getFunction(double x0, double y0, int iterations) {
        double r = 0;
        double a = -0.55;
        double b = -0.55;
        double x = x0;
        double y = y0;
        int color = iterations;
        while (color > 0 && r < 4) {
            double x2 = x * x;
            double y2 = y * y;
            double xy = x * y;
            x = x2 - y2 + a;
            y = 2 * xy + b;
            r = x2 + y2;
            color--;
        }
        return color;
    }
}

Класс Position я сделал для удобной работы с координатами (зум, мув). Простите за французский в названии полей/переменных.

import p79068.bmpio.Rgb888Image;

public class Position {
    private double bxMin;
    private double bxMax;
    private double byMin;
    private double byMax;

    Position(double bxMin, double bxMax, double byMin, double byMax) {
        this.bxMin = bxMin;
        this.bxMax = bxMax;
        this.byMin = byMin;
        this.byMax = byMax;
    }

    public Position zoom(double zoom) {
        double lx = (bxMax - bxMin)*(zoom-1)/(2*zoom);
        double ly = (byMax - byMin)*(zoom-1)/(2*zoom);
        double xMin = bxMin + lx;
        double xMax = bxMax - lx;
        double yMin = byMin + ly;
        double yMax = byMax - ly;

        return new Position(xMin, xMax, yMin, yMax);
    }

    public Position move(double dx, double dy) {
        double xMin = bxMin + (bxMax - bxMin)*dx;
        double xMax = bxMax + (bxMax - bxMin)*dx;
        double yMin = byMin + (byMax - byMin)*dy;
        double yMax = byMax + (byMax - byMin)*dy;

        return new Position(xMin, xMax, yMin, yMax);
    }

    public Position resize(double width, double height) {
        if (width/height > 1) {
            double dx = (bxMax - bxMin)*(width/height - 1)/2;
            double xMin = bxMin - dx;
            double xMax = bxMax + dx;
            double yMin = byMin;
            double yMax = byMax;
            return new Position(xMin, xMax, yMin, yMax);
        } if (width/height < 1) {
            double dy = (byMax - byMin)*(height/width - 1)/2;
            double xMin = bxMin;
            double xMax = bxMax;
            double yMin = byMin - dy;
            double yMax = byMax + dy;
            return new Position(xMin, xMax, yMin, yMax);
        } else {
            return this;
        }
    }

    public double getXMin() {
        return bxMin;
    }

    public double getXMax() {
        return bxMax;
    }

    public double getYMin() {
        return byMin;
    }

    public double getYMax() {
        return byMax;
    }

    public String toString() {
        return String.format("x=[%s...%s]\ny=[%s...%s]",
                bxMin, bxMax, byMin, byMax);
    }
}

Фрактальное изображение, основано на интерфейсе из библиотеки. Суть в том, что метод getRgb888Pixel() будет дергаться либой по каждому пикселю изобраения шириной и высотой getWidth() на getHeight()..

import p79068.bmpio.Rgb888Image;

public class FractalImage implements Rgb888Image {

    private int width;
    private int height;
    private Fractal fractal;
    private Palette palette;
    private Position zoom;

    public FractalImage(int width, int height, Fractal fractal, Palette palette) {
        this.width = width;
        this.height = height;
        this.fractal = fractal;        
        this.palette = palette;
        zoom = fractal.getZoom().resize(width, height);
    }

    @Override
    public int getWidth() {
        return width;
    }

    @Override
    public int getHeight() {
        return height;
    }

    @Override
    public int getRgb888Pixel(int x, int y) {
        double x1 = zoom.getXMin() + (x + 0.5) / width * (zoom.getXMax() - zoom.getXMin());
        double y1 = zoom.getYMax() - (y + 0.5) / height * (zoom.getYMax() - zoom.getYMin());
        int r = fractal.getFunction(x1, y1, palette.getSize() - 1);
        return palette.getColor(r);
    }

    public String getFractalName() {
        return fractal.getClass().getSimpleName();
    }
}

Он зависим не только от фрактала, но и от палитры

public interface Palette {
    int getColor(int index);

    int getSize();
}

Реализация которой в чернобелом варианте будет такой. Всего в палитре этой 256 цветов - 8 бит на канал (red=green=blue).

public class BlackAndWhite256Palette implements Palette {
    @Override
    public int getColor(int r) {
        return (r) | (r << 8) | (r << 16);
    }

    @Override
    public int getSize() {
        return 256;
    }
}

А вот палитра цветная рендомная, она рисует более интересные фракталы.
Код причесал как мог - он был портирован из Delphi. Я его писал лет 15 назад - можешь представить, что там было...

public class RandomPalette implements Palette {
    class Marker {
        int x;
        int color;

        public Marker(int x, int color) {
            this.x = x;
            this.color = color;
        }
    }

    private static final int MW = 8; // ширина маркера
    private static final int[] colorArray = new int[]{
            0xFFFFFF, 0x00FFFF, 0xFF00FF, 0xFFFF00, 0x0000FF, 0xFF0000, 0x00FF00,
            0xC0FFFF, 0xFFC0FF, 0xFFFFC0, 0xC0C0FF, 0xFFC0C0, 0xC0FFC0, 0xC000FF,
            0x00C0FF, 0x00FFC0, 0xC0FF00, 0xFFC000, 0xFF00C0};

    private List<Marker> markers = new LinkedList<Marker>();
    private int[] palette;

    public RandomPalette(int size) {
        palette = new int[size];

        int color = getRandomColor();
        markers.add(new Marker(0, color));
        markers.add(new Marker(size, color));

        int count = random(size / (MW * 3)) + 3;
        double r = size / (count + 1);

        addBlackMarker(MW + 1);
        for (int i = 1; i <= count; i++) {
            int j = (int) (i * r);
            if (yesOrNo()) {
                addBlackMarker(j - MW - 1);
            }
            addMarker(j, getRandomColor());
            if (yesOrNo()) {
                addBlackMarker(j + MW + 1);
            }
        }
        addBlackMarker(size - MW - 1);

        calculatePalette();
    }

    private int getRandomColor() {
        return colorArray[random(colorArray.length)];
    }

    private boolean yesOrNo() {
        return random(2) == 1;
    }

    private void addBlackMarker(int x) {
        addMarker(x, 0);
    }

    private void calculatePalette() {
        int x = markers.get(0).x;
        for (int i = 0; i < markers.size() - 1; i++) {
            int length = markers.get(i + 1).x - markers.get(i).x;
            for (int dx = 0; dx < length; dx++) {
                palette[x + dx] = colorChange(markers.get(i).color, markers.get(i + 1).color, length, dx);
            }
            x = x + length;
        }
        palette[0] = 0;
    }

    private int colorChange(int from, int to, double len, double x) {
        double red = change(getR(from), getR(to), len, x);
        double green = change(getG(from), getG(to), len, x);
        double blue = change(getB(from), getB(to), len, x);

        return rgb((int) red, (int) green, (int) blue);
    }

    private double change(double from, double to, double len, double x) {
        if (from == to) {
            return from;
        }

        double delta = Math.abs(from - to) * x / len;

        if (from < to) {
            return from + delta;
        } else {
            return from - delta;
        }
    }

    private int getR(int col) {
        return (col & 0x0000FF);
    }

    private int getG(int col) {
        return (col & 0x00FF00) >>> 8;
    }

    private int getB(int col) {
        return (col & 0xFF0000) >>> 16;
    }

    private int rgb(int r, int g, int b) {
        return (r) | (g << 8) | (b << 16);
    }

    private void addMarker(int x, int color) {
        // определяем после которого маркера будет создаваемый
        int index;
        for (index = 0; index < markers.size(); index++) {
            if ((markers.get(index).x < x) && (x < markers.get(index + 1).x)) {
                break;
            }
        }

        // если после последнего то выходим
        if (index == markers.size()) {
            return;
        }

        // если маркер некуда втиснуть между двумя ближайшими то выходим
        if (markers.get(index + 1).x - markers.get(index).x < MW + 2) {
            return;
        }

        // очень близко ставить маркер возле соседнего нельзя
        if ((markers.get(index).x + MW + 1 > x) || (markers.get(index + 1).x - MW - 1 < x)) {
            return;
        }

        markers.add(index + 1, new Marker(x, color));
    }

    private int random(int n) {
        return new Random().nextInt(n);
    }

    @Override
    public int getColor(int r) {
        return palette[r];
    }

    @Override
    public int getSize() {
        return palette.length;
    }
}

Небольшой консольный прогресбарчик-декоратор для того, чтобы я знал как долго будет рисоваться фраклат размером 20000x20000 пикселей. Я его прооптимизировал немного, чтобы он не занимался делением каждый пиксель.

public class Progress implements Rgb888Image {
    private long square;
    private long count;
    private long iteration;
    private long next;
    private FractalImage image;

    public Progress(FractalImage image) {
        this.image = image;
        this.square = getWidth()*getHeight();
        this.next = square/100;
    }

    @Override
    public int getWidth() {
        return image.getWidth();
    }

    @Override
    public int getHeight() {
        return image.getHeight();
    }

    @Override
    public int getRgb888Pixel(int x, int y) {
        calculateProgress();

        return image.getRgb888Pixel(x, y);
    }

    private void calculateProgress() {
        iteration++;
        if (iteration == next) {
            count = count + iteration;
            iteration = 0;
            int progress = (int) ((double)count*100 / square);
            System.out.println(progress + "%");
        }
    }

    public String getFractalName() {
        return image.getFractalName();
    }
}

Ну и Main метод

import java.io.File;
import java.io.FileOutputStream;
import java.io.IOException;

import p79068.bmpio.BmpImage;
import p79068.bmpio.BmpWriter;

public final class FractalDemo {
 
    public static void main(String[] args) throws IOException {
        draw(new Mandelbrot());
        draw(new Julia());
    }

    private static void draw(Fractal fractal) throws IOException {
        BmpImage bmp = new BmpImage();
        Palette palette = new BlackAndWhite256Palette();
        Progress image = new Progress(new FractalImage(1920, 1080, fractal, palette));
        bmp.image = image;
        File file = new File(image.getFractalName() + ".bmp");
        FileOutputStream out = new FileOutputStream(file);
        BmpWriter.write(out, bmp);
        out.close();
    }
}

Уверен кто-то это полюбит так же как и я...