Midpoint displacement algorithm - weird results

Question

I am writing my own midpoint displacement algorithm for learning purposes and I decided to implement it in my own way to see if I was 1) able to understand the algorithm and 2) see if i could modify it to my liking.

here is the code to generate the fractal:

 public void Generate(Double rg, int size)
    {
        Random rand = new Random();
        int min = -127;
        int max = 128;

        // Starting points of the rectangle
        MDP_Point s1 = new MDP_Point(0, 0, rand.Next(min, max));
        MDP_Point s2 = new MDP_Point(size, 0, rand.Next(min, max));
        MDP_Point s3 = new MDP_Point(size, size, rand.Next(min, max));
        MDP_Point s4 = new MDP_Point(0, size, rand.Next(min, max));

        // Lists containing the rectangles
        List<MDP_Rect> newRect = new List<MDP_Rect>();  // Newly created rectangles
        List<MDP_Rect> oldRect = new List<MDP_Rect>();  // Rectangles being divided


        // Starting rectangle is added to the list
        oldRect.Add(new MDP_Rect(s1, s2, s3, s4));

        // Distance between 2 points in a rectangle
        int h = size;

        while (h > 1)
        {
            foreach (MDP_Rect r in oldRect)
            {
                // Middle points of rectangle segments
                MDP_Point m1 = new MDP_Point();
                MDP_Point m2 = new MDP_Point();
                MDP_Point m3 = new MDP_Point();
                MDP_Point m4 = new MDP_Point();
                // Middle point of rectangle
                MDP_Point mm = new MDP_Point();

                m1.x = (r.C1.x + r.C2.x) / 2;
                m1.y = (r.C1.y + r.C2.y) / 2;
                m1.z = ((r.C1.z + r.C2.z) / 2) +(rand.Next(min, max) * rg);

                m2.x = (r.C2.x + r.C3.x) / 2;
                m2.y = (r.C2.y + r.C3.y) / 2;
                m2.z = ((r.C2.z + r.C3.z) / 2) +(rand.Next(min, max) * rg);

                m3.x = (r.C3.x + r.C4.x) / 2;
                m3.y = (r.C3.y + r.C4.y) / 2;
                m3.z = ((r.C3.z + r.C4.z) / 2) +(rand.Next(min, max) * rg);

                m4.x = (r.C1.x + r.C4.x) / 2;
                m4.y = (r.C1.y + r.C4.y) / 2;
                m4.z = ((r.C1.z + r.C4.z) / 2) + (rand.Next(min, max) * rg);

                mm.x = (r.C1.x + r.C2.x + r.C3.x + r.C4.x) / 4;
                mm.y = (r.C1.y + r.C2.y + r.C3.y + r.C4.y) / 4;
                mm.z = ((r.C1.z + r.C2.z + r.C3.z + r.C4.z) / 4) + (rand.Next(min, max) * rg);

                newRect.Add(new MDP_Rect(r.C1, m1, mm, m4));
                newRect.Add(new MDP_Rect(m1, r.C2, m2, mm));
                newRect.Add(new MDP_Rect(mm, m2, r.C3, m3));
                newRect.Add(new MDP_Rect(m4, mm, m3, r.C4));
            }


            oldRect.Clear();
            oldRect = new List<MDP_Rect>(newRect);
            newRect.Clear();
            h /= 2;
        }

        List<MDP_Rect> sorted = new List<MDP_Rect>();
        sorted = oldRect.OrderBy(y => y.C1.y).ThenBy(x => x.C1.x).ToList();

        List<MDP_Point> mapArray = new List<MDP_Point>();
        mapArray.AddRange(CreateArray(sorted));

        CreateImage(size, mapArray, rg);
    }

MDP_Point only contains x, y and z values MDP_Rectangle contains 4 points, creating a rectangle

The CreateArray() method only takes the ordered rectangle list and outputs and list of points in the correct order to create an image.

CreateArray():

        private List<MDP_Point> CreateArray(List<MDP_Rect> lRect)
    {
        List<MDP_Point> p = new List<MDP_Point>();

        int size = (int)Math.Sqrt(lRect.Count);

        int i = 0;
        foreach (MDP_Rect r in lRect)
        {
            p.Add(new MDP_Point((int)r.C1.x, (int)r.C1.y, (int)r.C1.z));

            if (i > 0 && i % size == size - 1)
            {
                p.Add(new MDP_Point((int)r.C2.x, (int)r.C2.y, (int)r.C2.z));
            }

            i++;
        }

        for (int a = 0; a < size; a++)
        {
            p.Add(new MDP_Point((int)lRect[(size * size - size) + a].C4.x,
                (int)lRect[(size * size - size) + a].C4.y,
                (int)lRect[(size * size - size) + a].C4.z));

            if (a > 0 && a % size == size - 1)
            {
                p.Add(new MDP_Point((int)lRect[(size * size - size) + a].C3.x,
                    (int)lRect[(size * size - size) + a].C3.y,
                    (int)lRect[(size * size - size) + a].C3.z));
            }
        }

        return p;
    }

This is the method to create the image:

        private void CreateImage(int size, List<MDP_Point> arr, double roughness)
    {
        Bitmap map = new Bitmap(size, size);

        int ver = 0;
        for (int i = 0; i < map.Height; i++)
        {
            for (int n = 0; n < map.Width; n++ )
            {
                int h = (int)arr[ver].z + 127;
                if (h < 0)
                {
                    h = 0;
                }
                else if (h > 255)
                {
                    h = 255 ;
                }
                Color c = Color.FromArgb(h, h, h);

                //map.SetPixel(n, i, c);
                map.SetPixel(i, n, c);
                ver++;
            }
        }

        Bitmap m = new Bitmap(map);
        bool saved = true;
        int num = 0;

        while (saved)
        {
            if (File.Exists("map_S" + size + "_R" + roughness + "_" + num + ".png"))
            {
                num++;
            }
            else
            {
                m.Save("map_S" + size + "_R" + roughness + "_" + num + ".png", System.Drawing.Imaging.ImageFormat.Png);
                saved = false;
            }
        }

        map.Dispose();
        m.Dispose();
    }

The fact that any value below 0 is set to 0 and any value above 255 is set to 255 is probably a big issue.... not sure what to do about it.

Here's an image generated by the code: Size: 1024 Roughness: 0.5

enter image description here

The most obvious issues are the diagonal "ridge lines" and the tiled look there is.

At this point, i'm not sure what to do to fix this to make it look more natural. Any ideas?

My understanding is that the midpoint displacement algorithm requires random numbers drawn from a Gaussian distribution. The `rand` calls will draw from a uniform distribution (uniform between 0 and 1). See http://stackoverflow.com/questions/75677/converting-a-uniform-distribution-to-a-normal-distribution and http://stackoverflow.com/questions/8739851/drawing-random-number-from-a-standard-normal-distribution-using-the-standard-ran — sfstewman, Jul 25 '12 at 04:56
I read the links, except i am not too sure how to translate this in values between 0 and 255. — SamHLec, Jul 25 '12 at 05:39

Chibueze Opata · Answer 1 · 2012-07-25T06:10:39.593

1

Here, I think part of the problem is your hacking of the h variable with 255 and 0. I tried the code using:

int h = (int) arr[ver].z;
if (h < 0)
{
    h = Math.Abs(h);
}
while(h > 255)
{
    h -= 255;
}

On my PC the result was: Take 1

and when I used:

int h = (int) arr[ver].z + 127;

Take 2

Note that I just had to create a testing MDP_Point class and MDP_Rect to test this...

edited Jul 25 '12 at 06:10

answered Jul 25 '12 at 05:12

Chibueze Opata

9,856
7
42
65

Yes, the hacking of the h value is really a cheap trick i admit! Still, your code shows the diagonal ridge lines, plus some noise around the peaks/low points. I think this could be fixed with a gaussian distribution like sfstewman suggested, but I am not sure how to implement it properly. – SamHLec Jul 25 '12 at 05:38
Well, I noticed this was better than yours. Randomizing the order in which the lines are placed will help out, btw, this a more complex issue than just programming, there is actually a project on generating contours, ridges and other 2D drawing techniques on [MIT](http://people.csail.mit.edu/tjudd/TilkeJuddMasters.pdf). – Chibueze Opata Jul 25 '12 at 05:48
Yes, it is better of course! I did not mean any offense. And thank you for the MIT link! – SamHLec Jul 25 '12 at 05:56

score 0 · Answer 2 · edited Jul 30 '12 at 15:52

0

To avoid these artifacts, you should use the two-stage method proposed by Peitgen et al. in "The Science of Fractal Images". They also suggest adding additional random displacements to all vertices after each subdivision step. I found a scanned excerpt here (page 45):

http://cs455.cs.byu.edu/lectureslides/FractalsPart2.pdf

edited Jul 30 '12 at 15:52

svick

236,525
50
385
514

answered Jul 30 '12 at 12:13

Chris

1

Midpoint displacement algorithm - weird results

2 Answers2