My third series in my AP Portfolio was on terrain generation. Computers mainly use terrain generation for simulations and games. For each of the visualizations in this series, I variations on the “midpoint displacement algorithm.”  The idea behind this algorithm is that you can add layers of detail to a data set by adding values based on the averages of the surrounding values. For example, if you have two points with the values 10 and 20, you can add another point at 15. By adding in a bit of random variation, a computer can create realistic terrain from only two starting points. This is called the midpoint displacement algorithm.

One Dimension: Noise

The first version of this is generating noise. At each iteration, the computer creates new points in between pairs of existing points.test

Over multiple iterations, this creates a more and more detailed set of points spaced at different distances. This can be audiolized as tones (hence the name “noise”) or can just be left as a series of randomly spaced points.

My final piece for this visualization included some extra colored circles for context:

End9.png


Two Dimensions: Path

In two dimensions, instead of varying the spacing, the algorithm varies the height of each point. With some coloring, this eventually creates a detailed 2D terrain like the bottom layer:Terrain Generation Algorithm

To better illustrate this, I laid out the algorithm’s steps by color:End56


Three Dimensions: Terrain

The midpoint displacement algorithm is most commonly used for 3D terrain generation. In this form, it is called the diamond-square algorithm.

Diamond_Square.svg

As shown in the above image, the algorithm takes a series of alternating diamonds and squares and fills in the center point of each. By repeating this hundreds of times, you end up with a 3D terrain map.

For my final piece on 3D terrain generation for my concentration, I again tried to combine each step in the algorithm into the final image. This image is shown to the right. Each step is displayed, stacked on top of the previous and denoted by a difference in the color. You can see how it gets more and more detailed as the algorithm progresses.

Terrain Generation 3-dimensions (1)


Four Dimensions: Space

This is where this all gets a little bit confusing. The first three dimensions of this algorithm are somewhat straightforward. They have basic goals and display methods. The fourth dimension, time, is a bit harder to picture. To make it a bit easier, imagine the fourth dimension is color. In each previous visualization, only the last dimension is affected by the algorithm. For the terrain, the x and y positions of each pixel are set, only the height of the pixel is changed. Extending this to the fourth-dimensional visualization, the position is completely locked and only the color is changed. Two different examples:

 

These are essentially clouds of color formed by what I call the Octo-Hexahedron algorithm. Essentially, it is a 3D extension of the diamond-square algorithm. These are full cubes filled with clouds of color. The fourth dimension can also be represented by transparency.

Screenshot 2016-08-24 23.36.18


Finally, you can actually represent the fourth dimension with time. This is in the form of an animation:


To tie these all together, I made a video with both the color and time-based animation:


Hexahedron-Octohedron AlgorithmFor the final still image for my concentration, I had to once again combine steps into one image. I used the same stacked approach with color changes to show time progression.


I had a ton of fun making this collection of pieces and exploring the midpoint displacement algorithm and its uses.

If you have any questions, comment below! Thanks!

 

Advertisements