Contour Maps with NASA Data

13th Oct 2023

Making Things CNC Art NASA Contour Maps

Earlier this year I decided to breathe some new life into my DIY CNC project from a couple of years ago. After I initially built the machine, I ended up not getting much use out of it. I decided that this year I was going to find some projects to use it for and test out it's real usefulness. Admittedly, the machine doesn't have huge practical utility for me, but building it was ultimately where the benefit came from. With that said, the machine is still useful in some ways. I recently undertook a project to merge some of my passions in AI and software to use the CNC to generate little art pieces to be engraved into wood, you can read about that here. In this article we are going to look at my next steps along this path. I decided to try and generate contour maps and have my CNC machine engrave them. I had no idea where to even start with this, but I got there, so come and join me in this journey!

The TL;DR

I started out with a super simple idea of taking 2d raster data (a 2d array of integers) of elevations and generating a contour plot from it. I had no idea how to do this, but then I stumbled on the Marching Squares algorithm which provided a simple to understand and easy to implement method of generating angular abstract contour maps from raster data. With this algorithm cracked, I then needed to take this a step further and figure out how I might get real world map data into this format to generate contour maps of real places. I discovered the Shuttle Radar Topography Mission (SRTM) and using free data sets from NASA I was able to build up a 3d elevation map of the entire island of Ireland. Using the incredible tool GrassGIS, I was able to export just the data I wanted for a specific location in Ireland in exactly the same format I required to plug it into my format above. Finally, I was able to run the exact algorithms from above and generate g-code for my CNC to engrave abstract contour maps of actual places in Ireland! If you want to know more, read on! You can also find all the code on my GitHub here and you can find the full video on this topic on my YouTube channel here.

Making a Contour Map

The first step in this entire process was trying to figure out how to generate a contour map. This is something I had never really thought about before and as such I had no idea how to start with it. My first and only real idea was that this was probably going to involve some sort of 2d array data structure which would be my input map data. The idea I had was that each cell would in the abstract represent some x-y coordinate (or real world latitude and longitude) and the value in the cell (integers in my case), would represent the elevation at that point. I had no real idea if this was going to be a useful model at the start, but, fortunately for me; it turns out that this is actually more or less exactly how this data is modelled in the real world (more on this later). With the data modelled and some test data generated, it was time to figure out how exactly I could generate a contour map. I tried a few approaches, most of which didn't really work. The main thing I learned from these failed attempts was that I knew what I needed to get out of the algorithm. Remember, the goal here was to be able to generate g-code from whatever contours I came up with. When generating g-code, the easiest move to make is a straight line between two points. With this in mind, I needed an algorithm with which I could derive a set of "strokes" comprising of a start and end point x-y coordinate for each section of the contour. This is worth keeping in mind when we discuss the algorithm I found while researching.

The algorithm I ended up using is called the Marching Squares algorithm. Looking at the patterns that this algorithm generates, it should become apparent why it jumped out to me when you consider my above point about straight lines. This algorithm effectively generates a straight line segment which corresponds to a "stroke" for each block of 4 adjacent squares in the raster map. Conveniently, we can simple represent each "stroke" as two x-y coordinates, one for the start point and one for the end. Each of these could then be stitched together to form a "path" that the CNC machine can follow to engrave the contour.

Implementing the marching squares algorithm wasn't very hard, the basics of the algorithm above are simple enough. However, I noticed a couple of things that I wanted to create optimisations for and performance improvements I wanted to make, so my final implantation of the code here, isn't the easiest to understand, but lets talk about it at a high level anyway (feel free to dive into the code if you like anyway!). The first thing you may notice in the truth table above with all the patterns drawn out, there is symmetry present. For example, case 3 and 12 are the exact same. This means that we can use the same function to generate each, that's handy! Another thing you might notice, and this is a slight problem for our CNC machine, in case 5 and 10, we have two "strokes" per cell. This kind of messes up our earlier idea that each "stroke" is a single movement from a start point to and end point. That is until you realise that each of individual strokes in the cell are actually a composition of two other individual cases already created in the truth table. So really, all we need to do is combine them together and create two strokes for each line referencing the already existing ones. Take a second to look at the table and you can see case 5 is actually just the combination of case 2 and case 7. I handle this in the code with a handy lookup hash of lambda functions, it works out neatly in Ruby!

Another optimisation I made as I worked through this came after attempting to run the algorithm on a very large real world map. The algorithm was extremely slow with the simple implementation I had used, it was also very memory inefficient. My initial implementation had been to store everything in a 2d array in memory and iterate through each cell for each thresholding pass per elevation step as per the algorithm. Instead of this, I decided to store the points in a hash map where each key as the x-y coordinate of the point and the value the elevation. I would also not update the values with each threshold, instead I would process each cell in order testing adjacent cells and generating the strokes for each elevation. This turned out to be much faster and better in terms of memory usage. The output of the algorithm is then just a simple list of all of the strokes generated by feeding the adjacent cell data into the table above.

Generating the G-Code

As I mentioned above, each portion of the contours to be engraved is going to be made of of an individual segment with a start and end coordinate. To make a program that my CNC machine can understand, I need to stitch all of these coordinates together into sequential instructions known as G-Code. Broadly speaking we are only interested in two types of commands. Travel commands and milling commands. This is a simplified way of thinking about it, but broadly speaking lets say milling commands are any time the engraving tool is going to cut a segment between two points, and a travel command is any time the engraving bit is moved off the surface of the work and moved between two points. With this in mind, the easiest first step to generate a program for our CNC would be to loop through each stroke in our list, write a travel command to move to the start of the stroke, then a milling command to move from the start to the end of the stroke, then finally a travel command to move to the start of the next stroke and repeat until we have done each stoke. You might be able to see where I am going with this, but here is a visual of what the program would look like were it to be executed. The blue lines are the milling commands and the yellow are the travel commands.

It is clear to see from the above that there are a lot of travel moves in this piece. In general, you want to minimise the amount of travel moves you perform for any given program. On a low grade homemade (or simple hobby class machine) machine like this, each travel move opens up the possibility of accumulating error as the z-axis moves. This is also going to be fairly slow. Travel moves are wasting time the machine could be using for cutting especially if the machine is moving back and forth over the same ground many times.

The solution for this issue was to attempt to write an algorithm to combine individual strokes into paths that the machine can follow. In the simple example above of the test data, you can see there are 7 fully closed loop paths in the map. It should be possible to generate a program that contains far fewer wasted travel moves and instead executes each milling move one after the other along the path to complete one full contour before it needs to lift up for a travel move to the next contour. This would reduce our number of travel moves from over 100 in this case to just 6. It might not be obvious, but we will still be executing the same number of milling commands as the above example, but our algorithm will just group and order them such that each milling move in a path can be executed one after the other without needing a travel move. To generate this data, we start with a single stroke and then loop through all the remaining strokes to see if it's start matches the end of another stroke or vice versa. If we find a match, we out the strokes in order in an array, and contain the process using the newly found start and end points of the total path we now have. We continue this until we can't match any more strokes to the path. At this point, we have one full path finished, or in the above case of the test data, we have closed the loop of the contour. The above algorithm is not very efficient, but it does have one benefit that the longer it runs, the fewer unmatched strokes remain in the list and so the faster it runs.

Once this algorithm has run, the final step is to write out the G-Code commands. For this, we loop through each group of strokes in each path, we write a travel command to get to the first stroke start point, then we write in order a milling command to go from the start point of the first stroke to the end point. This is where it becomes apparent that the number of milling commands stays the same. It now just so happens that our next milling stroke has a start point that is the same as the previous end point and our milling bit is already there. So we now just need to write a command to mill to the next endpoint. This continues in a loop until we reach the end of this path. At this point we issue a commands to travel to the next paths start point and continue as above. You can see below what the join up paths looks like when simulated, it should be obvious which program is better!

Getting Real Data

At the start of this project, I knew that I would like to generate real pieces from real mountains etc., however, I had no idea where I was going to get the data from or what format it would be in. Even after writing my algorithm for generating the contour maps and the g-code, I still didn't have a clear picture of where or how to get the data. I kind of assumed I would need to get a dataset and write code to then transform it into my simple 2d raster map format. This ended up kind of only being partly true. To my surprise, 2d raster elevation data (provided in a text file), is actually a very common format called Arc/Info ASCII Grid (AAIGrid). Having never looked into this type of technology before the next few days of research were a baptism of fire, that ended up paying off in the long run!

My first break in my struggle to find data was discovering a personal website where someone was painstakingly assembling lists of sources to download satellite data. As of writing this, I can't seem to recreate my google search to find this original source, if I find it I will link it here as it's really where it all began and I would like to credit the creator. In amongst all the links and acronyms I didn't understand I saw "NASA" and "SRTM". NASA, I recognised straight away, and then a google of SRTM blew my mind! There are incredibly detailed elevation data datasets of most of the planet available to download for free! Here is a great tool that can help find the datasets you might want.

Getting the data was a great start, I downloaded an archive with the data I needed covering the island of Ireland. This was great, however, I was now at a point where I needed to work with these data files and had no idea how. The files were downloaded in a binary format, in total I believe I had 13 files each covering a chunk of the island. My goal was to use this data to extract elevation data for a specific square area centred on a set of latitude and longitude coordinates. This is where I discovered the kind of system used to work with these type of map files is called a Geographic Information System (GIS) and I found a free open source tool called GrassGIS that I could use to help me. With this tool, I was able to import all of my 13 sections of the map of Ireland and create one single map. The learning curve here was steep, but I managed to muddle through and figured out how to export a specific area I could specify in the AAIGrid format. With this data in hand, it was simply a matter of plugging it into my previous algorithms and everything pretty much just worked!

Some small tweaks not withstanding, nothing major had to really be changed between the test versions of the system and the final version with the real data. I made a few tweaks and optimisations as I went along but fundamentally it was the same. This was shocking and very exciting to me. It's not everyday you start a project with some vague idea and it ends up working more or less perfectly through the entire process. Call it instinct, call it look, I call it satisfying all the same!

What's Next?

Playing around with generating G-Code for my CNC has been really fun in the last two projects I've done with it. There is something fun about pushing the boundaries the confluence of many of my interests. I think I will keep playing around with what I can do with it, what kind of art I can make and keep having fun with it. I really love this system for generating contour maps. I think they are kind of a cool memento or keepsake of somewhere important to a person. I haven't really ut serious thought into selling them or anything, but I think I would take the commission if someone wanted one!

Keep on making
- Ian

If you enjoyed reading this article and would like to help funding future content, please consider supporting my work on Patreon.