Coding in the Cabana 5: Marching Squares

[Music] welcome to another episode of coding in the Cabana today I am going to tackle something called marching squares the topic of marching squares are marching cubes was originally suggested for the coding train on February 18 2019 by Quinn the sunrise so I do want to try marching cubes I suppose that'll either be in a follow-up video whether it's a Cabana one or a livestream I'm not so sure just yet but I'm gonna stick with just marching squares for this first video if you're looking to do some research into this algorithm the first place to look is the 1987 paper marching cubes a high-resolution 3d surface construction algorithm by William Lorenson and Harvey Cline Sebastian lag has a wonderful coding adventure video about using the marching cubes algorithm to create a endless underwater world as well as a video using marching squares for 2d to generate procedural cave patterns coding challenge number 28 on the coding train is about metal balls which I've used a pixel-based approach to create those patterns but you can also use marching squares to create a similar effect and Jamie Wong zero wind online documents this process and a wonderful article about meta balls and marching squares from August 2014 I'm going to demonstrate the marching squares algorithm just by using it on a noise space I'm use the open simplex noise algorithm although you could certainly use worldly noise or any of the other noise algorithms I've talked about and then once I finish that up we can I'll try to return back to some of these ways that you could expand it further into meta balls and terrain generation and 3d and then hopefully you'll make lots of wonderful variations of this and I'll be able to look at those and show them on a live stream someday so here's how marching squares is described a computer graphics algorithm generates contours for a two-dimensional scalar field rectangular array of individual numerical values what so let's try to break that down what that means so the good news is this is a two-dimensional algorithm and it's something that we can visualize in a two dimensional space so a nice little p5 canvas or processing window I think I'm gonna use processing which I like to do in these Cabana videos but always there will be a Java Script p5 GS version released as well that you can find in this video's description what does this mean the rectangular array of individual numerical values as two-dimensional scalar field well if I take my processing window and divide it into a two dimensional grid we could think of each cell of this grid as having a number that's how we visualize two-dimensional Perlin noise or whirling noise or all sorts of other algorithms that I've looked at on this on the coding train but in order to make marching squares happen I need to put a little twist on this I don't actually want to think of the center of each one of these as having a number I want to think of these spots here where each square note the idea of square here has four corners and each of those four corners represents a number ultimately it's the same sort of thing like it's just a matter of where am i drawing my lines and where am i drawing add my dots but there is a 2d grid of numbers and each one of these spots has a value so let me first create a processing window that just draws little dots like this and maybe gives each one a random number between 0 and 1 I think I'll want some type of variable to keep track of what is the resolution what's the what's the distance between any given tot and the next dot so if the pixel window is 600 by 400 maybe each dot is separated by 10 pixels I'll call that rez for short for resolution with the Z so once I have a resolution I want to know how many columns and how many rows and now I have my two-dimensional array which is going to keep track of all these values in this scalar field so let's just write a Luke a nested loop that is to look at every spot in the array oh and I can just say random one then I'm going to do that exact same nested loop in draw to visualize the field I'm gonna visualize it as a stroke color field times 255 point at eye x res J times res right because there's this many columns spaced out by resolution and let's see what that looks like okay we can see that here now let me make those a little bit bigger and we can see here's my two dimensional scalar field or a rectangular array of numerical values so the idea of marching squares is what would be some algorithm to find contours and patterns in this array of numbers and I think just to make this easier to see I'm gonna just increase the resolution to 20 let's actually have the stroke weight be the resolution times like 0.2 or something and actually make that more like 0.4 and there we go so I just wanted to be able to see this a bit more clearly at higher resolution so to demonstrate how this works I think it would be actually easier for me to consider each one of these numerical values as just a zero or one later I'm going to describe what you can do once you have a floating point continuous values and how that affects the marching squares algorithm but something much simpler to start just with zeros and ones so let me actually change that so I'm gonna say floor random - and I'm gonna change this to an integer I'm gonna come back to floats later but let's just leave it as an integer right now let's let the background be gray so I can see whoops and this has to be integers so now I can see I have just black and white dot to figure this out let's look at just one square each one of these corners will call them maybe a B C and D just as a naming device each one of these corners has a value of 0 or 1 so let's just say for the sake of argument this one is 1 and maybe I'll visualize that by filling it in and this one is 2 oh sorry this one is 0 this one is 0 and this one is 0 so I'm gonna just consider we draw that again I'm gonna consider just this one particular configuration well it so happens that this particular configuration the way that I choose to visualize it is by drawing a line here we can see that all of these are empty but this one is full therefore the line goes across from the midpoint here to the midpoint here I could show you another one maybe from this you could guess right this one is full and this one is full so I want to separate that so the idea here is that basically I whichever ones are on or off I want to separate the ones that are on from the ones that are off so for example if this was full and this was full and by full hello it told me that I should say this were one not zero then the line would actually end up here and now how many possible scenarios are there well if there are four corners and each corner could be on or off a zero or a one in each one of these spots whoops zero zero zero all the way up to 1 1 1 1 well this is like a 4-bit number there are 4 bits for zeros or ones 2 to the 4th power equals what that's 16 so there are 16 possible configurations the glorious of water she seems very thirsty it's hot dates early-ish the sun's not beating down in here yet but it's getting worn she looks like she could use some water come on let's go get you some water okay [Music] so these are all 16 possibilities let's put the numbers underneath zero one two three and now let me put these these are called ISO lines so number 10 here just so I have a fixed version of it here should be looking at my processing window right now I realize I'm missing an extra column an extra row right because the idea is I want to look at each square with four corners and the school in order to fill the full space down here at the edges I'm missing the right and bottom corners so I can fix that very easily just by adding one more column and one more row and now see I'm ready to look at each collection of four corners and figure out which isoline should I draw up based on that I look at any individual square these are the important points all right these midpoints between the corners because that's what's gonna connect the line whether it's this or whether it's this or whether it's this any of these are what I'm drawing so I think I'm gonna call this one a B C and D so let me first calculate the positions of each one of those points I'm gonna do this in a separate loop also because I need to stop at minus one because the final column doesn't have any neighbors to the right and the final row doesn't have any neighbors to the bottom a is AP time need is P vector just to figure out what speaker ABC and D the x value is what column I'm on times that resolute and point a which is over here is the x-value of this plus half right this the length of each side is my variable red so half of that plus res times 0.5 that's x and y for a is just at the top so using that same idea I can figure out b c and d c is why is all the way at the bottom and x is again in the middle and then d is X's at its original location of the top left and Y is in the middle and I forgot to make a variable for Y and because of the person who I am which I am just happy to be these days I must align all of the spacing here I [Music] don't know whether that makes it better or worse but I'm very happy with how that looks right now so if I just wanted to put let's say this line at every single spot I would say line from a dot X a dot y to be X B dot y let's say stroke 255 oh and let's make these thinner stroke weight one and there we go so we can see now I've got this line every single at in every single square but that's not what I want to do I only want that line if the squares are this particular configuration configuration number four so B's by the way if I were to say 0 0 0 0 0 0 0 1 0 0 1 0 notice that I'm counting in binary so each one of these maps to the binary representation of the numbers I don't know if I made that totally clear so if I take any binary number I just need to convert this into its base 10 rappers tation this being four and then figure out which one of these it is and draw the appropriate line so let me write a function I'm gonna call it a get state that gets the numeric the int the base ten state based on four zeros and ones so I'm gonna give it four arguments this is kind of silly because I could actually use some type of built-in java function to convert from binary to decimal or base two to base 10 but I'm just gonna do this in a very manual way because I know I only ever have four bits return a times one plus B times two plus C times four plus D times eight and so if I were to now say int state equals get state oh no no no I'm not passing these in what I'm passing in is the value of each of these corners which is in my field array so this is field I J field I plus 1 J I J I plus 1 J I plus 1 J plus 1 I plus 1 okay it all fits on one line so that looks good looks good to me okay so now if state is for this particular line that I've drawn that's only if the state is for Oh guess what here's a really excellent time to use a switch statement oh I'm so afraid of switch statements but I'm gonna be strong and brave and I'm gonna use a switch statement today and I'm not definitely not going to Google syntax for a switch statement in Java no I I know it off the top of my head right cuz I've been programming for 20 years of course I know the syntax for a switch statement off the top of my head [Music] so in the switch the thing that I'm checking is state and then I'm checking whether it's zero one oh let me just add one for zero since this code I copy pasted in here already has starts from one then I'm going all the way up to 15 now you might be thinking oh isn't there some nice elegant way to do this without a separate line of code for each particular state probably I'm so excited for people to watch this video and make all sorts of new and different ways of doing this algorithm with shorter code more efficient code cook more creative code so please share that with me but I'm just gonna get this to work gonna do it based on each state individually of course I actually don't need a case for 0 because in the case of 0 I don't draw anything so I didn't need to put that in there I mean I might want to add those back in if I wanted to do something based on that but let's just add case 1 which is drawing a line from and if you I remember this is from a C to D line and you know what I'm gonna write my own function you can do this in Java because you can overload functions so I'm gonna write a function that gets two P vectors v1 v2 I'm just gonna call it line and draws a line between them so I don't have to like constantly type out the X and the y over and over again so let's do that that's right right XY XY okay good now I'm going to say line from C to D and that makes sense you can see that line appearing every time there's a mmm it's not right Oh the first one is x 8 oh boy this is been there for a while my binary number starts on the left that goes to the right so the left-hand digit 0 or 1 is the amount is the is the 2 to the fourth no two to the third excuse me two third 2 squared 2 to the 1 2 to the 0 there we go now we're seeing that in correct place case number two now I should be able to do these fairly quickly case number two is a line between B and C case number three is a line between a B and D so I'm now going to speed through this and you'll see if you can see I'm sure I'm gonna make a mistake but you'll see if I do I think I've put in all the correct line configurations based on every possible values for the four-corners what this gives me Hey look at that I have now drawn contours around all of the areas of black and white let's try putting in a different algorithm now I'm gonna use open simplex noise I would refer you to some videos that I made on open simplex noise I even worked on a library for processing that incorporates open simplex movies didn't really get finished so I'm just gonna pull in the open simplex noise code directly from one of my previous examples here this was developed by Kurt Spencer in 2014 it's direct Java code without all the processing niceties so I'm actually gonna put it in a opens inflect annoys Java tab and then I should be able to say open simplex noise noise noise equals new open simplex noise and then I what I'm going to do is I'm going to calculate in the draw loop new values each time so let's move this into the draw loop and instead of a random number I'm going to say noise eval and I want to offsets an X offset and a Y offset so let's have X offset start at 0 and let's link seems super strange like when you're talking about X offset Y offset noise eval so you'll have to go back and look at some of my videos on Perlin noise and open simplex noise but the shore the gist of it here is I am looking at this two-dimensional space and looking for smooth random value so I'm going to get nice smooth gradients from white to black like smooth gradients of gray throughout this space by calling this function so first of all let me change this to float that's gonna cause all sorts of problems and then this I have to convert to a float because the noise algorithm gives me a double it just gives me a decimal number with more precision but I don't need that I could convert it right to a float for using it processing let's use this casting syntax to convert the output okay just check to make sure oh my god the mic has been down here this whole time when I had integers just zeros and ones each corner had a value now each corner has a value a noise value and open simplex noise gives me numbers between negative 1 and 1 so I want to keep these values because I might be able to do something more with them if they're continuous values later or at least suggest some things that you could try but basically I think a solution that it could have is you know zero being right here in the middle if it's greater than zero it's a 1 if it's less than zero it's a zero in terms of converting it to a binary representation and I can actually just use the ceiling function so if I have a number between negative 1 and 1 ceiling raises it up so if it's below zero it'll become zero if it's above zero to become one so I think this is going to be a little bit awkward code like in terms of making this so long but I can just put ceiling around each of these all of the values here are all the same because I took the same noise value at the same x offset and wah I offset so I need to move throughout that two-dimensional space so I'm going to create a variable called increment I'm going to call that just I'm gonna just set that to 0.1 and for every column X offset will go up by increment and for every row Y offset will go up by increment and now there we go so we can see this is the noise space and this is drawing a contour around it now maybe what I want to do let me lower the resolution a little bit I think it's time to do that now and there we go we can start to see this terrain it's like terrain like thing with these contours drawn around it I love this alright let's do something a little bit more and let me use the fact that open simplex noise can be calculated in three-dimensional space so while this really could be something quite exciting if I were rendering in 3d and then eventually could use four day open simplex noise what I'm going to do instead is use that third dimension essentially as thinking of it like time so frames of animation so if I create a global variable called Z offset set that equal to zero and then every frame Z offset goes up I think I might want to control this separately from the X often Y off incrementation so I'm just gonna hard code this in there the same number but I want to be able to have separate control over it and now hmm oh well of course I need to add that to the noise calculation whoa that is why I want to control it separately because I want to have it go up much slower and there we go so now you can just see this is very very fast algorithm so some things that might be interesting to try here one is I don't know how much value I'm getting out of rendering those points it's nice to see actually you know what a way that I would like to render them just because I'm curious let me say let me actually make this fill and no stroke just control these as recta this isn't exactly accurate because the value is the corner I'm just sort of curious oh yeah that's kind of nice looking I sort of like seeing it this way that's what I was imagining and I could make the resolution much smaller I could make this fullscreen very slow one thing I could do that might be interesting is just actually not bother drawing this at all the rectangle so that'll speed things up a little bit make the background black and then I could also probably use the P 2d renderer which is a hardware accelerated there we go look at that so here we go this is the this is really the end of this video it's the marching squares algorithm over a 2d open simplex noise field but I have really only scratched the surface I think with the creative possibilities here I have not explored color I'm just creating the field of numbers just with open simplex noise there are lots of other noise algorithms oh I could use an image convert it to grayscale and have those be the values I could use my live webcam image I could use distance from different circles or other objects floating in the space this is what's in the Jamie Wang article about using a moving circle screen a metal balls like pattern you can look at what Sebastian lag did for a procedural cave generation there are so many possibilities but one thing that I haven't explored that you will notice in if you look at the Wikipedia page explanation or Jamie Wong's article is that I am always drawing the lines from these exact midpoints however each one of these corner values now has a floating point number what if I had right if these are ones we know the line goes here but what if these are what if the values here were this is just like 0.01 and this is 0.99 maybe this should be for the higher value not closer to this edge or further away and vice-versa for this so this idea of a linear interpolation where the midpoint is actually variable according to the magnitude of the value on the corner and this is something that would I think if I'm correct about my understanding of this would make for much smoother patterns that feel like they're less blocky looking I might rather like this blocky looking and it kind of works for a certain aesthetic but that's the thing that would be worth exploring and if I'm able to do that after this video you'll be seeing right here next to me a version of that this exact sample of how it looks so thanks for joining me through this a little exploration of the marching squares algorithm I've got to find Gloria pickle where has she gone she never came back for her water maybe the plants actually really I know last time when I made a coating the bad video said I was gonna go water to the plants and then I didn't actually water the plants I mean I might have actually watered the plants if I didn't show you the watering the plants who knows what really matters here but I need to water the plants it's very hot and probably a little bit sweaty does it go cool off water the plants fine pickle make sure she's okay and has some water and some food she probably needs to go for a walk and I'll see you in a future coating the Cabana video [Music]

Channel: The Coding Train

Views: 111,988

Keywords: marching squares, marching cubes, perlin noise, open simplex noise, metaballs, processing, java, JavaScript, p5.js, algorithm, marching squares algorithm, coding in the cabana, coding train, daniel shiffman, dan shiffman, coding tutorial, creative coding

Id: 0ZONMNUKTfU

Length: 26min 27sec (1587 seconds)

Published: Fri Jul 17 2020