Implementing Midpoint Displacement Algorithm

Processing Coding Questions
1

Hi, i want to implement the Midpoint displacement algorithm. Please help!

I can’t find a good source to follow in 1D and i dont understand it fully that i can implement it myself alone. I’m not interested in 2d case before i manage to make something like the image below.

This is the code i have so far. The loop does the calculation necessary from a math perspective.

Things i think im missing:
random numbers and assigning all the info to a straight line on screen

float[] v = new float[1025];

void setup() {
 size(600,600); 
}

void draw() {
  for(int i = 2*2*2*2*2*2*2*2*2*2;  i > 1; i /= 2) {
    for(int j = i / 2; j < 2*2*2*2*2*2*2*2*2*2; j = j + i ) {
    /*   
    give value to v[j] =  + number * rnd function
    */
    }
  }
}

I’m simply looking to create something like this:

0fd97fc7ab7ac5a7670935f1695d2a0c614e5252 (1)

Example found on google.

1 Like
2

The MPD algorithm is best done using a recursive method, the code you show uses an iterative approach which will not work well or if at all.

So the algorithm works like this. Lets keep it simple and assume that we have just 9 points rather than the 1025 in your code. In fact we can have any number of points np provided np = 2^n + 1 where n is any positive integer.

Lets call these points p_0, p_1 … to p_8 and we start with knowing the values for the first and last point.

So step one is to calculate the mid point
p_4 = (p_0 + p_8)/2 + displacement.

Now we have three points we can calculate two more mid points
p_2 = (p_0 + p_4)/2 + displacement.
p_6 = (p_4 + p_8)/2 + displacement.

Now we repeat the process
p_1 = (p_0 + p_2)/2 + displacement.
p_3 = (p_2 + p_4)/2 + displacement.
p_5 = (p_4 + p_6)/2 + displacement.
p_7 = (p_6 + p_8)/2 + displacement.

Where displacement is some random value and we now have all 9 points.

You can see we are repeating the same process but with smaller and smaller segments, this is typically done recursively.

2 Likes
3

Thank you i really appreciate your answer. Sadly i’m not skilled enough to fully understand the connection between what you have written and how it would look like in code. I do understand what you have written though, that makes sense to me.

Could you give me steps to solving with recusive method? or could you explain how i would do the recursion and then how i would apply the implemented function.

4

I can provide simple code to do the 1D case and that will demonstrate the recursive method do you want me to post it?

2 Likes
5

I would like that very much thank you. That would be very helpful.

6

This is only a guide for you to experiment with there are several improvements for instance using noise() instead of random() and use bezier curves to get a smoother contour.

// Number of points must be 2^n + 1 where n is any
// positive integer
int np = 65;

float[] p = new float[np];
float stepSize; // horizontal distance between points
float displacement; // the maximum vertical displacement 
                    // at the mid point (may be + or -)

void setup(){
  size(1025, 400);
  stepSize = float(width) / (np- 1);
  displacement = 2 * stepSize;
  // Initialise the values 
  p[0] = random(0.2, 0.45) * height;
  p[np - 1] = random(0.55, 0.8) * height;
  mpd(p, 0, p.length -1);
}

void draw(){
  background(255);
  stroke(255,0,0);
  strokeWeight(1.1);
  for(int i = 1; i < p.length; i++){
    line( (i-1) * stepSize, p[i-1], i * stepSize, p[i]);
  }
}

// This is a recursive function because it calls itself!
void mpd(float[] array, int ps, int pe){
  // find the index for the centre array position
  int pmid = (pe + ps)/ 2;
  // if it is the same as the start then recursion is finished
  // We must have some condition to halt recursion otherwise we 
  // crash the sketch
  if(pmid == ps) return; // finished
  // Calculate the midpoint position and add a displacement
  array[pmid] = 0.5 *( array[ps] + array[pe]) + random(-displacement, displacement);
  // Now recurse the function with the two 'sub arrays'
  mpd(array, ps, pmid);
  mpd(array, pmid, pe);
}
2 Likes