# How Computers Draw Weird Shapes (Marching Squares)

## Метаданные

- **Канал:** Reducible
- **YouTube:** https://www.youtube.com/watch?v=6oMZb3yP_H8

## Содержание

### [0:00](https://www.youtube.com/watch?v=6oMZb3yP_H8) Segment 1 (00:00 - 05:00)

a couple of months ago I stumbled across some pretty cool animations the basis of these animations come from just eight circles but how they merge together in an organic way is what pops out here I was curious how exactly this works and my journey into this turned out to be way more interesting than I expected turns out these circular objects that naturally merge together are called metaballs and there's a lot of deep mathematical and computational ideas that you interact with when you try to create metaballs if you're anything like me when you see these animations you immediately wonder how you even begin to approach solving a problem like this one I mean really think about it imagine you were given the task of figuring out how to generate metaballs how do you even frame the problem what does it mean to have circles that organically merge together how does a computer render something like this on the screen these are all super hard problems in today's video you and I are going to go on a journey of how folks and computer Graphics approach this very problem the core algorithm that plays an essential role in generating these animations is called marching squares and it's actually a technique that's used a lot in graphics applications as well as Medical Imaging but as useful as marching squares is I think what you might enjoy the most about this journey is how elegant the approach to solving such a problem can be there's real Beauty in taking a vague problem and transforming it into a form that is specific and approachable the real goal of this video is to give you that sense of joy in discovering the shifts and perspective that make hard problems like this one solvable so let's start by breaking down the case of two metaballs from a bird's ey view what we need to do is find a way to generate every frame of this animation and if we slow down the animation we can get a sense of how this evolves over time take a second to study it and see if you gain any insight a lot of times when I ask you to do that there's supposed to be some sort of reveal afterwards where I show you just the right way to look at it and boom there's the clue but this time I'm right here with you I have absolutely no clue what we can do here no shame in admitting it so let's maybe ask a more basic question are there any frames of this animation that seem easier to render than others any frames with two circles immediately pop out as easy cases but as the circles come closer together they start deforming and that's the part that's unclear but amidst the chaos there are a few frames where if we isolate them our image looks a lot simpler for example here we actually have a shape that looks pretty much like an ellipse right and here when the original Circle are right on top of each other we end up with just one larger Circle so even though we have no idea how to put these frames together there are a few isolated frames that aren't that difficult to render sometimes when faced with a really hard problem it helps to focus on what can be achieved let's start our journey with a quick discussion on circles and ellipses they form the basis of the ideas around metaballs mathematically defining a circle just requires two parameters a center and a radius for an ellipse given a center and the length of the following two segments we can Define it with this equation not surprisingly these functions are pretty similar in format both of these functions are examples of implicit functions we have some function in terms of X and Y and the output of that function is some constant value this is in contrast to other functions where we can have one variable explicit L defined as a function of the other a lot of times the implicit function definition is just easier to work with as is the case with circles and ellipses so going back to metaballs for these particular frames we know that if we can get the appropriate parameters of our circles or ellipses we have the full definition of the shape that we need to render so then a natural question that arises is maybe the other frames have some mysterious implicit function that we can Define even though we don't have proof of this intuitively it does seem that there should be some sort of implicit function similar to circles and ellipses for these shapes and maybe these metabol implicit functions have properties that can allow for us to render them but again a lot of uncertainty here so far our approach has relied a lot on wishful thinking so maybe it's time to shift our perspective a lot of you are most likely familiar with the problem solving technique where the key idea is to ask a

### [5:00](https://www.youtube.com/watch?v=6oMZb3yP_H8&t=300s) Segment 2 (05:00 - 10:00)

simpler version of the problem there's another counterintuitive technique where sometimes it makes sense to actually ask a harder version of a problem right now we're trying to figure out how to render frames of an animation where some frames are implicit functions that nicely Define a circle or ellipse and others could be implicit functions that render these merged variations of shapes the hope is that some of the ideas from how we render circles and ellipses may help us figure out how to render the other unclear frames but this is just a specific case of a larger question can we figure out a way to render any implicit function of the form f ofx y is equal to some constant this question looks like it might be much harder but it's actually exactly the question we need to make some real progress on this problem let's play a game suppose I have some mysterious function that takes a point in 2D space and gives a scalar value you are allowed to sample any point in the space and I can give you the value of the function at that point your job is to figure out all the points in the space that equal a specific value in our example let's say we want to find all points that equal one how do we approach this problem the most basic idea is to Simply sample points randomly and if we're within some threshold of our value we can then say we've identified a Target point but the problem here is that even with a fairly large threshold it's highly unlikely that we end up close to a Target point so this is not a real solution to the problem so you think for a bit and maybe you decide to simplify things a little there are essentially two cases every point you sample is either greater than or less than the target value and we can color code the cases points less than one will be blue and points greater than green now let's sample and see what happens about 1,000 points in you don't see much but as we get to about 10,000 maybe now you see it once we sample 20,000 points the separation between the two cases starts to nicely Define the outline we want I'll add some Target points now just to make sure we're on the same page by the way I'll refer to these Target points on the outline here as a contour of our implicit function what we're really trying to do here is find a contour at the value one and I'll also admit an ulterior motive here I've always wanted to find a way to incorporate Batman into one of my videos and this is one where I figured it out some of you may be familiar with the Batman function which I got from a random math stack exchange post but fun fact it's an example of an implicit function a pretty ugly implicit function if we're being honest but it yields a nice result and what's really nice for our purposes is that the Contour at the value one is defined by a change between points that are above one and points that are below one that sounds obvious when you see it laid out but this is a really important idea that we can use to our advantage let's say I have two points from our implicit function there are a couple cases to consider it's possible both of the evaluated points are greater than one here we have learned absolutely nothing about the Contour we're trying to outline we just know that these points are inside the Contour but how far inside is unknown another case is if both points are less than one which is equally useless we are outside the Contour but have no real information on where the Contour could lie relative to these points the third case is the interesting one suppose our function at Point a evaluates to less than one and the function at point B evaluates to greater than one what does this tell us well it must be the case now that the Contour where all the points are equal to one is somewhere between these two points and in fact we could theoretically find at least one target point we can continuously BCT the points any number of steps with more steps leading to higher Precision it's essentially a binary search of a real numbers and this is the essence of the simplest root finding algorithms one quick note right now we're assuming that points greater than our Target value are inside the Contour while points less than our Target value are outside the Contour we'll keep this assumption for the rest of the video but just so you know this is just a convention and in some literature you will see this convention flipped

### [10:00](https://www.youtube.com/watch?v=6oMZb3yP_H8&t=600s) Segment 3 (10:00 - 15:00)

it doesn't actually matter since what we care about is the points that are equal to Target value all right so we're making some progress we have a way to find a point on the Contour of our function over 2D space remember our goal is to find an estimation of the entire Contour what we really need is some organized method to sample points in any sort of Graphics application the first simple thing to try is to sample points in a grid G like manner let's say we create a grid of the falling resolution and Sample corners of each cell of the grid let's zoom in on a particular cell and think about what happens there are a couple key cases If All sample points on the cell are less than one we know this particular cell is outside the Contour when all sample points are greater than one the cell must be inside the Contour in both of these scenarios there's not much we can do to figure out an approximation of where the Contour is but if there's at least one point that's greater than one and less than one we gain some information suppose the top left sample point is inside the Contour and all other points are outside what does this imply well what we do know for sure is that the Contour must pass through this cell and in fact we can perform the exact exercise we did earlier on these two points one of these points is inside the Contour and the other is outside so with root finding we can find the point on the Contour we can repeat the process on these two points as well and the key idea here is if we connect these two points that's an approximation for how the Contour passes through the cell let's see another example of this idea in action in this particular cell we have the points on the left Edge inside the Contour and the points on the right Edge outside we perform root finding on the edges with a point inside and outside the Contour to find exactly where the Contour passes through the edge and then we can approximate the Contour as a line passing through these two points the overall idea is that as these grids become smaller and smaller the lines used to approximate the Contour within the cell become more accurate so we saw two cases for how a contour could pass through a cell let's take a look at the rest of the cases there's a total of 16 cases since a point on the Square is either inside or outside a contour a good exercise here is to check your understanding and see if you can draw an approximation of the Contour through the cell for each of these cases we've already seen how it works for these four examples don't worry about exactly where the points are on the edge that will depend on the implicit function remember depending on the values of the implicit function at the corners of the cell the end points of the Contour could be anywhere on the relevant Edge to simplify things in your drawings assume the Contour just passes through the midpoint of any relevant Edge now go ahead and see if you can work out the remaining cases what you may have noticed is that even though there are 12 remaining cases there's a lot of symmetry let's do some organization these two cases are essentially the same since the outline of the Contour does not pass through the cell then we have squares where only one corner is inside the grid the next group is where every square has points on one Edge inside the Contour and the points on the other Edge outside the Contour there's also two cases where the points inside the cont Contour are on opposite corners and lastly we have the cases where only one point is outside the Contour in practice the simplest method to implement this logic is with a lookup table containing this data I do want to make a quick note about some subtle edge cases that you might have to think about depending on the application in these two cases we're assuming that all points inside the space here are also inside the Contour but that's not necessarily true there's nothing that prevents our function from having a point outside the Contour in the center of the grid most of the time this won't be an issue but it's something you have to be aware of and handle if necessary a reasonably simple workaround that makes the approximation better is you can sample the center point as well to differentiate between these scenarios so taking a step back to find a contour of an implicit function here's what we've done so far we take our

### [15:00](https://www.youtube.com/watch?v=6oMZb3yP_H8&t=900s) Segment 4 (15:00 - 20:00)

two-dimensional space and split it into a grid of squares given any Square on that grid with sampled points from our implicit function it's guaranteed to have a configuration of one of the cases we just went through and then depending on the case we'll find the points on the edges of the square where the Contour equals our Target value through root finding we then connect those points appropriately now root finding is the primary method we've discussed to find the points on the Contour with arbitrary Precision but in practice there's actually a more efficient method that's still fairly accurate let's do a quick thought experiment say I have a cell with the following sampled values from our implicit function if the top left corner of the cell has the value 1. 5 and the top right corner has the value zero instead of doing a root find between these points to find the exact XY coordinate that gives the value one we can just approximate it and assume the Contour crosses the edge a third of the way between the two points we can repeat the same process on the bottom Edge where we expect the Contour to cross the edge at roughly 3/4 of the way between the two points when we have an edge on our square with a point inside the Contour and a point outside the Contour we can take advantage of a couple of key ideas to estimate the point in between first of all we're always going to know either the x value or the Y value immediately remember our Contour point between these two sampled points is always on either a vertical or horizontal line so there's only one unknown coordinate and then the important assumption we'll make is the values of the function are going to change linearly from one point to another which then allows us to determine the other coordinate with a little bit of algebra the exact math of this defines a common Graphics technique called linear interpolation and this calculation is significantly faster than root finding in most applications this approximation is good enough that it's the preferred method so let's put what we've discovered together into an algorithm which is formally called marching squares to restate the problem more formally we have some implicit function and we want to get an approximate Contour of the function where all the points on the Contour equal some specific value you might see these types of Contours of the same value be referred to as ISO Contours marching squares is an algorithm designed to extract ISO Contours from implicit functions but as complicated as that sounds what we do is simple in principle we Define a resolution for a grid and we basically March a square through the grid most of the squares will have either all the points outside the Contour or inside the Contour in which case we just move on to the next Square but the important squares will be one of the other cases where the Contour actually passes through the square when we encounter one of these cases we can find the points of intersection on the edges through linear interpolation and get a local approximation of how the Contour passes through the cell when our resolution is low our Contour is not going to look quite accurate but as the resolution increases the accuracy the final Contour improves that right there is the core idea behind marching squares pretty elegant algorithm overall now clearly the higher the resolution is of the grid we use to perform marching squares the longer it'll take to generate a contour so there's always a trade-off between accuracy and speed when it comes to this algorithm but there's one more property of marching squares that makes it quite appealing for graphics applications the there's a term in computer science that I always found kind of funny we call an algorithm embarrassingly parallel when it's easily able to be transformed into independent parallel tasks what a term right marching squares is an example of such an algorithm and here's how it works an easy way to understand the parallel version of marching squares is Imagine for some grid resolution I gave you a separate computer for each cell the idea here is that you can process each cell independently from all other cells in practice you'll need a method to provide each computer with an easy way to calculate the scalar function value at Each corner of its respective cell that can be achieved by having a readon map of points to scalar function value shared between all computers then once a computer processes the individual case for each cell it can write geometry information to a shared memory location

### [20:00](https://www.youtube.com/watch?v=6oMZb3yP_H8&t=1200s) Segment 5 (20:00 - 25:00)

across all computers once all computers complete the right operation we can use the information to render the entire Contour almost all applications that require some level of performance with marching squares use the parallel version of the algorithm to their advantage let's now take a step back and look at the bigger picture of what we've accomplished thus far remember we started this whole journey with the question of how we might render metaballs we had a belief that metaballs are just a specific type of implicit function so then we went down a path of attempting to solve a harder problem of rendering Contours of any implicit function that's what led us to the marching squares algorithm now we've solved the harder problem so the remaining question is how do we apply marching squares to generating metaballs if we have an implicit function of metaballs it's actually pretty straightforward for but what is the implicit function of a metaball now at this point I could just spoil the answer but there's actually one really incredible connection that I want to share that gives the motivation behind why the implicit function of metaballs is defined as it is it's pretty cool I promise so far we've really only thought about implicit functions with respect to a single Contour value but what if we considered several Contour values simultaneously when we try that the Contours of our implicit function put together look kind of like an energy field and here's something that's really cool by modeling each individual shape as an energy field it's kind of interesting to ask what might happen when I put two energy Fields together what does that look like well a natural way to model the merging of these fields is constructive interference and how we get that constructive interference is by summing together the individual implicit functions that's where the curvature comes from pretty mind-blowing right oh and we're not done yet the inspiration behind these ideas is something some of you may already realize those of you who have taken a physics class might recognize that what we see here is quite similar to how equip potential lines from two charges in an electric field act if you have two positive charges and draw their electric field lines as well as their electric potential lines this is actually a diagram you've probably seen before the math behind metabol implicit functions ends up being quite similar the electric potential at a particular point in this space is a sum of each individual electric potential contribution from a charge and the actual electric potential value is inversely proportional to the distance from each charged particle can you guess the implicit function that we use to model a single metaball it's essentially the same relationship for a single metab ball we use the implicit function 1 / R where R is the distance from the center of the metaball and then if we want to model two metaballs the final implicit function is the sum of the individual implicit functions from each metaball I can't imagine what exactly you're thinking at this point but when I first saw this it just absolutely blew me away what a nice connection between the realm of computer Graphics mathematics and physics having this implicit function makes it quite easy to modify features of our metaballs we can increase the size of a single metaball by scaling our implicit function and we can also easily change the location of a metaball if we have any number of metab balls that we'd like to model we can just sum up the individual contribution from each implicit function with these tools making this type of Animation is actually not terribly difficult we Define an implicit function for the number of metaballs we'd like to animate and then we give each metab ball a velocity and update its position over time every new position leads to a new implicit function and every frame is just a rendering of that implicit function with the specified Contour value marching squares then takes care of the rest before we close on these metaballs I do want to give a quick note that even though the true implicit function for a metaball is defined as the inverse distance function in practice no one really uses that function since there are a few annoying properties that make it a little bit cumbersome folks in graphics actually prefer to use a polinomial approximation of this function that basically gives the same result the reasons why are a little complicated and not something I want to get into but I'll leave some further reading in the description for those that are interested the same principles can also be applied

### [25:00](https://www.youtube.com/watch?v=6oMZb3yP_H8&t=1500s) Segment 6 (25:00 - 27:00)

to three-dimensional functions to render a three-dimensional implicit function we can use marching cubes if you understand marching squares marching cubes is a natural extension to 3D spaces we split our space now into a 3D grid and we March a cube through our space the key difference is we now use sampled points at the corners of the cube to identify approximations of triangles that represent the surface locally when you apply this to the entire space you get a group of triangles that form a mesh that you can then use to represent your 3D object marching cubes is a really powerful algorithm and if you want to see some really cool applications of it I highly recommend this video by Sebastian lag it's really incredible and definitely worth your time you now have a pretty good idea of some of the MTH and the algorithms that are behind animations such as metaballs this is definitely a non-standard introduction to marching squares implicit functions and metaballs but in a way I think it's a nice method to learn the concepts as a quick personal story when I was in college I briefly learned about marching squares and marching cubes in one of the graphics courses I took it's a classic story I learned about the topic in a lecture there were some examples to demonstrate the concept we had some homework on the topic and eventually there was an exam and then like most people I basically forgot everything about it going back through my notes from the course I realized I never really understood how beautiful and elegant these ideas were when I first encountered them all this to say it was really quite amazing to me when I randomly encountered the topic of metaballs my interaction with this concept was completely different I mean it was really nice day I was so interested in figuring out exactly how this worked all the details and I even implemented it as part of this video and I think for me framing it in a way where my goal was to actually build something using it and then learning the details as I went through the Journey was a lot more meaningful than listening to it from a standard lecture there's a pretty big lesson to take away from that a key part of learning new ideas and Concepts especially in the world of computer science is to actually try play around with Concepts that you interact with whenever you get the chance there's so many extensions to ideas in computer science and if anything I hope you come away from this video with the feeling that the time you take to explore these ideas on your own can really be quite meaningful thanks for watching and I'll see you all in the next one

---
*Источник: https://ekstraktznaniy.ru/video/38915*