Maybe it's my physics background, but when you asked how we would approach it, my mind immediately went to contour lines on a potential field. Of course, I had no idea how to use that to actually render the metaballs, but I'll take what I can get.
Same, I immediately thought they look like a contour of inverse square law. Funny that you really get at feel for how different functions looks and behaves in different situations.
Haha yeah, secretly, my favorite part of making this video was explaining that really cool connection with potential lines in an electric field. For me, it was just an amazing connection. I love hearing how people from different backgrounds think about these problems. Thanks for sharing!
As an electrical engineer, I had the exact same though as you did. Marching squares makes it a lot more efficient, and that was the part I couldn't come up with by myself.
A "cheaty" way to draw metaballs is to start with a black-and-white picture with solid circles (or any shapes, since they could be constructed by combining circles), apply gaussian blur, then reduce it back from grayscale to purely black-and-white with a threshold function.
That actually sounds like it resolves to essentially the same approach seen here! Additive gaussian blurs will behave like sums of inverse-radius functions. (No marching squares tho; just per-pixel shading)
Well this video tries to get the the bare bones of computer graphics and "applying gaussian blur" involves just as much math and deliberation as the video.
@@mayabartolabac CS is allowed in SoME1, i think its more because SoME1 was to encourage people who are thinking about starting a channel to start, whilst he already has videos
Amazing, once you understand marching squares/cubes and how they are "embarrassingly" parallel, you seem to understand that why graphics cards are much more powerful at rendering than a normal processor. This is probably always skipped when people explain the difference between CPUs and GPUs.
Yeah I actually originally had an entire section of the script dedicated to the differences of the CPU and GPU and how there are specialized programs called shaders that allow a path of communication with the GPU for highly parallel operations. In practice, almost any high performance implementation of marching squares should use shaders. I wanted to go there, but if I did, it would be an hour long video :) Perhaps some time in the future.
Just a clarification: those oblong shapes are *not* ellipses. Also, this algorithm only works well if all the details of your shape are significantly larger than your starting grid. If not, then the 16 classifications can be *way* off from the shape.
Thanks for clearing up, I had a similar thing in mind: What if the shape has very fine details, like a couple of jags inside such a grid cell, and what about shapes with many small holes? Either you need a very fine grid resolution (inefficient for realtime applications), or use quad/oct trees at the expense of simplicity. It's fine like it is for simple, smooth shapes. Yet I wished for a more universal concept covering all shapetypes - I suppose that's a lot asked). Very good video illustration on this topic though!
@@cooperfeld If you need that much precision then nothing is stopping you from making the grid 1px in size, and thank the gpu for being good at its job haha
You're right, but that same problem occurs with any sampling-based method-details of the contour might get lost between samples. So you need to pick a resolution which corresponds to how much complexity your implicit function has.
Yes, you are correct -- I put the "Ellipses" part in quotation purposefully here, but I probably should have been more clear. And also, good point on the details of the shape, this is an important consideration when implementing this in practice.
Yah, the grid resolution is basically some 2D analogy with a low pass filter. Any details whose features are significantly smaller than a cell of the grid will be lost.
Unknowingly, you brought me 30 years ago. Back then, I was obsessed with Mandelbrot sets. I had programmed a rendering algorithm for it but it took ages to complete, and I was desperately trying to find a faster way. In the end, I succeeded but, reinventing a variant of marching squares. 1. First compute all the points on a, say 16*16 grid. This is roughly 16*16=256 times faster than computing all the whole image. 2. For any center of a 16*16 square, if all corners have the same value, then set the center value to be the same. Otherwise, compute it. You end up with a "diamond" grid. 3. For each diamond, do the same. You and up with an 8*8 grid. Go back to step 1 until you have an 1*1 grid. With this, I could draw a Mandelbrot set much, much faster than before. Once I had done this, I wanted to compute in real time animations on the Mandelbrot set. To save even more time, I used the old picture to guess the points on the first 16*16 grid. If all the neighbors of a point on the old 16*16 gris had the same value, then I guessed that the corresponding point on the new grid also had the same value. Both technics can be used to speed up marching squares for graphics animations but the drawback is the it becomes far less obvious how to obtain a parallel version.
Yo I literally came up with this search-then-refine idea while I was watching the video. Kinda reminds me of how collision detection works with kd-trees. This video: ru-vid.com/video/%D0%B2%D0%B8%D0%B4%D0%B5%D0%BE-eED4bSkYCB8.html
2 года назад
Fractint had even more tracks up its sleeves back in the day to render fractals really fast even on underpowered 80386s. You can use the amazing.fact that the Mandelbrot set is connected.
I've certainly heard about marching cubes in the past, and have even seen Sebastian's video before. But framing it as a general purpose solution for finding implicit curves, wow. To me, that's a very "sticky" way of explaining it. Fabulous!
Great video! When you said at the start, "How would you even start?", I decided to pause the video and accept the challenge (i guess I'm one of the people who is "anything like you" :D). I theorycrafted a solution and implemented a proof of concept in simple JavaScript with Canvas. Then I watched the video to compare with your results, and it turns out I arrived at the same shape function, just my rasterization was slightly different (pixel based instead of vector based), but I suppose both approaches lend themselves to different applications. The last part really resonated with me, because I'd heard of all these concepts in one way or another in university lectures. While I didn't quite "forget" them and was happy to find them somewhere in the back of my mind to apply to this problem, tackling a "practical" challenge such as this one, outside of the "campus environment", refreshed me on these subjects, enhanced my understanding of them and is really going to cement them in my brain!
If you have time, you might want to experiment with implementing adaptive refinement. A coarse grid produces jagged resolutions, and a fine grid wastes a lot of computation. Instead, you can successively divide the boundary cells into smaller cells until you reach some pre-set number of levels, and then apply marching squares to the list of edges within the adaptive grid. A similar method is used in many computational fluid dynamics codes. You would also have the option at that point to skip the marching squares stage if you divide down to the point where you grid matches the output resolution (the pixel is either filled or not). If you're wondering about parallelization for such an implementation, typically the domain is divided into chunks based on the number of parallel processors, and if one chunk becomes overloaded with computation while others are idle, then it can shed some of the load to the idle processors (who then take on those sub-chunk regions). Also, you can utilize the previous state (for an animation or simulation) as a starting point for the next time step. There you know that grid cells need to be merged or subdivided further, which would be based on the function evaluations in the next time step. It can quickly become very complicated, but it's always cool to see the grid changing every timestep.
And if you want to optimize even further, you can use your knowledge of the function: For metaballs, there are n known locations (where n is the number of circles) that must be inside the function (the centers of the circles). If you start marching there until you hit an edge and then follow the edge, you reduce the number of squares you need to look at dramatically. Or even better, you start at distance r away from each center and march outward until you find the edge.
@@HenryLoenwind That could help to accelerate this specific problem, but not the more general problem of arbitrary functions (which is the more interesting case). Although, there are methods for basically phrasing general functions in the form of overlapping radial functions (essentially a basis transformation - that's essentially the difference between grid based and particle based fluid dynamics simulations, and you could use the center -> edge marching method to convert the particle case to the grid case). Note that the edge distance R is only known in the case where particles / meatballs don't overlap, when they do, the potential field is shifted and that distance is no longer correct. One disadvantage to doing the radial walking approach though, is that you may end up visiting a cell multiple times which wastes computation. Also it's not embarrassingly parallel anymore, nor is it regular in the memory access patern.
I think the strengths of this type of technique really shine with the 3D sibling: marching cubes. Jagged edges like that become much less apparent on 3D geometry once you start diving into vertex value interpolation, used for smoothing surface normals across a triangle & more, and other more advanced techniques that break up the visual patterns. It's not necessarily the best there either, because there are more refined competing algorithms that do similar things like dual contouring or marching tetrahedra, but it's still a perfectly fine technique that can be used to great effect. It's a popular style of technique because it makes great use of modern hardware, works well in general cases, and often gets close enough to the desired result that no real end user is ever going to notice something is off.
11:10 is a really trippy visual illusion that I've never seen before! Some of the blue dots look like black dots with a blue outline, but when you go to look at that dot it changes back into a solid blue dot.
If you actually look at one place for long enough, the outline dots will disappear completely and only the grid will be left in your peripheral vision! For your brain it's much easier to just assume it's a simple grid so it "caches" a simple grid instead of actually focusing on what you actually see!
I use the 3D variant of this - marching cubes - to render simulated fluids volumetrically, directly on the GPU in parallel. The simulation determines the very limited lattice resolution, so resolution is not a free parameter in my case. See my channel for examples :)
A very interesting application of these iso fields is "signed distance functions" used in raymarching, which allow highly performant rendering of 3d fractals.
Signed Distance Fields can also be used in font rendering. (Valve literally wrote the white paper on it.) Unreal Engine 5 also uses then for virtual geometry.
You don't need marching squares for metaballs, you can create the same effect using only shaders, maybe ddxy for antialiasing. But yes, marching squares, cubes are amazing.
Nice exposition, but I was left wondering about the special cases where you may miss a local maxima or minima within a square. For the metaball problem that should be relatively easy to avoid reliably since all local maxima are given (= the coordinates of the balls), but if you're working with an arbitrary function it's a risk, regardless how fine a grid you use (and for fractals it's a certainty). I can imagine these things are a bit messy to go into, but I think it's worth mentioning.
One thing missing is properly deciding how to do the thickness of the line segments within the squares. You naively just used a rectangle but what you actually want is a trapezium, so the edges do not have little triangular gaps between squares (and so they don't overlap, though that's less important if the shape is entirely opaque)
9:27 this method is really good for finding the border of a shape, but in concave shapes only! if you have a convex shape you will only find 1 border that cuts the line between the two points
When you are on the point that you can teach it, like you did here, you "groked" the concept. You may forget details but the concept will live forever on your toolbox.
One ~kinda~ extension / similar concept of this I personally like is the use of signed-distance functions in ray marched rendering, allowing you to render perfectly mathematical objects with high precision by just sequentially polling a math function to ask "how far away am I from the surface of the closest function" then pushing your ray tracing ray forward by that amount in space (therefor never passing any object which the ray may intersect with) with this you can then render 3d fractals with incredible detail fairly easily. if you want to render multiple fractles its also easy as you just take the minimum of their signed distance funciton.
This was so amazing! I have a question, I'm trying to animate a honey drop as it falls and I feel like this's is very related to it the only problem is finding the potential field for the drop , but could the method you showed work for modeling a honey drop or do I have to use other methods like the Navier-Stokes equations?
I've watched only the introduction section and I've almost solved the problem myself, and it looks exactly like the animation! Here is my solution. Inspired by the how the influence of the other circle diminishes drastically as it moves further away as well as how an ellipse has two foci, I realized that the equation 1/sqrt((x-d)^2+y^2) + 1/sqrt((x+d)^2+y^2) = 1 reproduces the exact behavior, where d is half the distance between the centers. Testing this out in desmos gives the correct behavior. Adding more circles works by simply adding more 1/sqrt(distance) terms to the LHS, so the program really just needs to keep track of circle positions and be able to draw the resulting curve. Drawing the resulting curve is obviously the hard part.
You are a wonderful narrator, I really enjoyed every section of the video, how you begin with a well-defined goal, and how you reach the final goal in a beautiful eased flow.
eg. 25:17 You can probably improve the drawing speed by marking the neighboring cubes (or squares) around every place where you HAVE drawn a line (like an array with coordinates), then the marked cubes gets checked first for any lines (and surrounding cubes are marked again if a line is drawn), you can speed it up even further by analyzing the direction of the line & only add the spaces in the CORRECT direction to the marked list (can add the other surrounding cubes to a list of lower priority). Then you can have like just one computer core running the normal marching square algorithm, just in case there is another object that isn't connected, so you "brute force" its detection.
16:16 me, not quite understanding what I'm watching, but having a little maths knowledge: "couldn't you just lerp? idk" 17:02 me, still trying to understand everything he just said 17:05 me: "Wait, linear interpolation?! That's lerp! Heck yea, I predicted it!" lmao
First intuition without watching the video You create a scalar field in the entire scene. Each circle creates a distortion in the field with an equation like that r*exp(s*d) where r is the radius, s is some kind of constant smooth factor, and d is the distance to the center of the circle This creates some kind of "energy" emanating from the center of the circle, fading as you get further away from it. You sum the energy of the circles over the entire field, and when it hits a specific value (more like a small range in practice), you color your pixel So the final equation would look something like a = ln(0.5) r1*exp(s*a*d1) + r2*exp(s*a*d2) + ... + rn*exp(s*a*dn) == 0.5 computed for every point, with dn being the distance from that point to the center of circle n I guess this should produce similar results ? ///after watching/// holy shit I wasn't far off lol, just replace the exp by a division and change some constants and here you go
is there an implicit assumption that the implict functions are continuous? because otherwise the greater than and less than 1 technique would not work right?
Good point, yes that is an assumption that we have to make with how I described marching squares. The next question you might have is how you deal with discontinuities. What I've read about it states that a common technique people use is they locally interpolate any discontinuities with a continuous function, which isn't perfect, but good enough in practice. There's so much depth to this stuff that I really didn't have time to get into and this is one of those questions that opens an interesting can of worms :)
I wonder if you could optimize this by starting off with a coarse grid of squares, then keep a list of "interesting" squares, to go back and refine the details with Edit: though that does have the drawback of potentially missing small, isolated details
I think you mentioned a few different words for implicit curves but I don't think you said either "level sets" or "level curves", which is how I first came across them when taking multivariable. Of course, I had also had them introduced to me as "equipotential" in physics classes, so it's just interesting to see how the same concept gets different names across so many fields!
I am in second year of an engineering degree. I hate all my courses and I could not care less about any of them. While I do my course work or bash my head against my desk I just wish I had time to work on the things I want to work on. Never have I heard something I resonate with so strongly. "And I think for me, framing it in a way where my goal was actually to 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."
Your videos are just amazing and so inspirational. I felt a bit ashamed though, having majored in physics and not having had the slightest clue initially that electric charges where acting behind the scenes. Just, incredible. Thank you very much.
Great video! I like how you explain the algorithm as the solution to a specific problem, it gives more insight on why the algorithm is how it is, and it's something that other videos on marching square lack.
The animation of the meta-balls reminds me of playing with blurry shadows on the ground, cast by the sun. Bringing my finger shadows together seems to make them "stretch" and try to merge in a strange way.
Why using the field potential 1/r and not just r ? Since the solution to F=1 are the same, both give circles, but the sum won't be the same. What is the motivation of one and not the other? Just because 1/r looks nicer ? Why not 1/r^2, 1/sqrt(r), or anything?
Good question! You actually can use both 1/r^2 and 1/sqrt(r) (although with the latter, seems a little overkill because of a double square root calculation). The linear function doesn't get the blobby like effect however since there is no smooth portion of the function that nicely creates the constructive interference we are looking for. That's why polynomial approximations of the function work in practice. It's hard to explain without a diagram though so I'll point you to a couple of resources. One good summary of is here: www.scratchapixel.com/lessons/advanced-rendering/rendering-distance-fields/blobbies The original part of the script had an unreasonably long section on alternatives to this implicit function but I cut it out because it felt I was going on way too much of a tangent. You're asking the right questions though -- there is a lot of interesting properties surround implicit functions to use for metaballs. One of the best overall in depth resources on this I found was www.researchgate.net/publication/242914163_Data_Structure_for_Soft_Objects
i love this video! an idea i had while watching it would be to keep a queue of all squares that the contour passes through the contour. then we could iteratively divide each square in the queue into four smaller squares and perform the same root-finding algorithm on them to further refine the quality of our contour, and push those four squares back onto the queue. we discard squares from the queue once they reach a certain size (i.e., once they're small enough). i wonder if anyone's done that!
As soon as the physics connection was made it was like a wave of everything hitting me at once of what I had learnt in physics class and realised i've also fallen into the study-test-forget loop.
you know after seeing the contour cases i couldn't help but think that that's exactly the style of tiling that pixel art uses. with those basic shapes, they can essentially create any style of terrain and make it look organic.
18:40 couldnt you theoretically make code that runs marching squares, then subdivides and runs back over only the squares it detected a contour in, thereby allowing a less than exponential computing time
or, following the parrallelity of the next chapter, couldnt you, as one marching square algorithm runs, do a more resolute marching square on each square that contains a contour
When I made a stupid small lava lamp app a long long time ago, my first approach was literally just to make blurry white circles on a black background, add them together, and then clamp the pixel values above and below a specific value between black and white. Just use that as a mask for some texture, add shading and other effects, and boom. That's it. It just instinctively made sense. In this case, your metaballs use an inverse square "blur" instead of a linear "blur" or a Gaussian "blur" (which I used). There are many interesting functions that could be used to make different kinds of "metaballs", but the inverse square seems to be the most common function used, probably because it goes to infinite distance, resulting in smoother metaballs.
That was a great description! I’ve heard of marching squares before, but seeing this video has helped me see it a different way. Could you make a video about dual contouring? It’s another similar method that has cleaner results but is more complicated.
Good question! Mainly because these functions don't have finite support. A function with finite support means that as the distance past a certain point, the function will evaluate to 0, and this never happens with inverse functions. Functions with finite support are nice because efficient and intelligent implementations can ignore points outside of a particular distance when computing the implicit function. The lack of finite support is one of the "annoying properties" of the inverse functions.
Thanks so much for making this video! This encouraged me to try making my own metaball renderer using marching squares, which I completed. It works well but did take like ~3 days to write. (mostly bug fixing the marching squares)
Excellent video and incredible work ! One very small note though, blue and green was a poor choice of colors, these are too close and the low contrast is hard on the eyes
Yeah, I'm sorry about that. I made a mistake there. I generally have my display brightness to low amounts and for me I didn't see any problems with it while generating the animations. It was only after I had finished the final cut of the video that I realized it could be a little harsh at times, but it was too much of pain to go through and fix at that point. My apologies here!
If you know that the implicit curve for a given potential has a single connected component, could you, like, start with a low resolution, and then only on the squares which seem to contain the boundary, recourse into them with a higher resolution grid? Or is this pointless because the parallelism of GPUs is enough to just hit all the high resolution squares at once?
I imagine there is some optimizations possible on this level, but in practice, you are right, shaders are just so effective at parallelizing these computations that you most probably don't have to worry about this.
@@Reducible I‘d imagine it could be more worthwhile in 3D where the number of points grows much faster with increasing resolution. Still, probably only good for really fine resolutions
It's a rather odd choice to frame the video in such a way that you need marching cubes to render implicit functions. Sounds like you made it into a much harder problem than it really is. In 2D you can render them trivially through sampling - what you showed in the "guessing game" part. In 3D it becomes more interesting, as you need to solve an equation that considers all points along the ray and find the closest intersection with the implicit function to the camera. But even that is doable with Newton's method. To make it more efficient and fun, you can explore the idea of Signed Distance Fields, how rendering them is easier than rendering implicit functions and then reformulate the metaballs as a SDF.
12:00 This must be a script editing mistake. You're presenting the values as binary (f(C) 1) in this segment and treat these quadrants as set patterns but suddenly whip out root-finding based on real values of the points for this one step. Rather confusing out of advanced context.
this is wonderful, however I was thinking of another approach (I still don't know if it's applicable in all scenarios) what if we tried to find only one point (x,y) with a value of 1 then calculate the gradiant vector at that point, knowing that a slight mouvement in the direction of the orthogonal vector to the gradient result in no change of value, we can slightly move the point (x,y) orthogonally to the gradient vector that way we can pretty much assume that the value of the function f(x,y) at the new location is technically the same. the only problem this could face is that after several iterations the error value can grow until it's not tolerated anymore. but in some cases it would be perfectly fine. I would be very grateful to hear your thoughts about this :)
Interesting video, that really helped explain to me how to do something I wondered about before but never figured out a nice equation for (granted, my initial problem was a bit different: I wanted convex meshes of arbitrary shape to merge like this to other convex meshes, *except they should abide to preservation of volume*. And that they should _actually_ merge them once they touch, at least once they merged enough for the resulting shape to be convex). The idea of simply adding two field-functions together is a rather neat way of doing that (even if I have no clue how to generate an equation for arbitrary convex 3d shapes - and I am rather certain volume won't be preserved - but it should be possible to preserve "mass" which is "good enough") which I never really considered (had somehow tunnelvisioned myself into trying to describe the shapes with parametric functions which only worked somewhat because my meshes were still only spheres) And something that stuck out to me in that video as soon as you mentioned adding them together, was that you never addressed a rather obvious performance concern/optimization. If you are to add the equations for 2 metaballs, you are inevitably going to take an infinite amount of time (the grid is infinite). And even if you limit the grid, traversing it in its entirety for every frame to calculate each cells value would be ill-advised. So should probably have been some mention that the best way to go about it is probably to compute each sphere individually, adding the value of its equation to the cells near it (using a threshold for when to consider its contribution "negligible", so you can limit the amount of cells considered (or you would, again, end up traversing out to infinity). If you have the memory to spare, you can even optimize further by caching the (local) positions considered relevant, and their respective value.
Huh, pretty cool to look at it from another perspective. I've been working with SDFs for animations, and my first instant Intuition would have been circle SDFs and smooth union all of them, which would have achieved the same thing... I guess I just take advantage of modern hardware and just execute it for every pixel multiple times (Antialiasing).
For the curious among us, sabestian lague made a video about marching squares generalized to 3D in his terraforming video. This was a great explaination for the 2D case!
I literally rediscovered by my own what you explain in the sections "contours around two points" and "sampling the space" some days ago when designing a method for aproximating the shape of a given curve with no known expression. I couldn't believe it when you explained what I had just written on my notebook, math is amazing, two persons will always reach the same conclusion even without knowing of each other. Really loved your vid, amazing work, keep it up!
Nicely done. That 'play with it' step at the end for actually learning it is exactly what many of us want our students doing with homework problems, but scores for homework tend to make students optimize a little different. That stops in grad school eventually and we 'play' with our research topics. My experience is we don't really know a thing until we play with that thing. We might pass exams and get good scores, but that's not really a measure of what we've learned.
amazing video. I can't even explain how inspiring your channel is to me! It would be nice if you would make a video that documents your process for making videos
(I'm typing this after having only watched 2:30 of this video) I think it might have something to do with 2 points. The geometric definition of a circle is all of the points a distance X from a given point. I have no proof of this right now, but I think it might be "A pixel is colored if (value+tolerance)>1/(distance from point 1)**2+1/(distance from point 2)**2>(value-tolerance)". The tolerances are only there because otherwise you'd almost never see anything. (At 23:30) I was right! Perhaps it's because I'm already a physics nerd.
The "potential" function in the animations seems to be more like R^2/r^2 (like a force) instead of R/r. Can you confirm? As two bubbles are approaching each other they seem to grow very little until they are very close. Additionally, the max growth of radius for two overlapping bubbles vs one seems to be closer to times sqrt(2) rather than times 2. Example: A. for the 1/r case (as stated in the video): R=5 leads to a bubble with radius 5 since R/r boundary of 1 occurs when r=5 also. With 2 bubbles overlapping, 5/10 + 5/10 = 1 so the new circle from two overlapping centers has radius 10. B. For the 1/r^2 case (as suggested by the animations): R=5 leads to a bubble with radius 5 just like above since 5^2/5^2 = 1. But for two bubbles overlapping, we have 5^2/7^2 +5^2/7^2 is about 1, meaning the new boundary of the larger bubble with 2 centers is around 7 units (7/5 = sqrt(2)).
Another way to generate something that is close to metaballs is… the locus of a point whose product of the distances from two given points is a constant. So if the given points are (x_1, y_1) and (x_2, y_2) and the constant product is "a", then the inplicit equation would be √((x - x_1) ^ 2 + (y - y_1) ^ 2) * √((x - x_2) ^ 2 + (y - y_2) ^ 2) = a. Also, this locus is a toric section.
You can use complex polynomials! Imagine you want to make n of these circles in an m by m grid. You can define each center with a complex number x+yi, and then define the polynomial f(z) = (z-c_0)*(z-c_1)....(z-c_n) with c denoting the centers. now, you can plot the absolute value, more and less than some values to give you circles. now, by moving each center, you have an animated version; no need for any implicit circle and/or ellipse formula!
There's a similar one which seems to be called an organic maze that look like corals... but the pathways keeps changing in that liquid like fashion. It doesn't look like a warped version of a horizontal by vertical type of maze, but maybe of every angle shifting around while warped with Perlin noise as the walls constantly slither everywhere into the next wall.
Reducible: this is how you use marching squares Sebastian league: this is how you use marching cubes.. Loki probably: Alright, Time to start my marching tessaracts video
I'm on 1:07, so a bit of head-on idea: 1. Make canvas; 2. Make N circle objects move independently; 3. On each render step, trace the NxN network of connections between any two circles 4. For each two circles that come in 'contact', calculate four points where the circles merge - expression can be made out of an equation system for circle and say, hyperbole (for which the line that connects centres of circles would be both a symmetry axis and an asymptote), in such case it would be two equation systems; 5. Aaand gradually render outline, have never practiced this part. Upd: yep, the whole video about p.5. Good one!
As a programmer i would have just had each circle have another circle surrounding it, any circle within the outer circle radius will change the inner circles shape based on distance, and each inner shape can be a set of lines this would also work with any other shape, and increasing the line count increases the shape quality
I find the thought process at the start interesting, because I had already been spoiled to the "solution" before I had ever seen a meta-balls effect. I got started with computer graphics messing around in BASIC on Apple ][ and other 8-bit computers. There usually wasn't a built in command to draw a circle, so I came up with a lot of dumb ways to do it. I didn't really have a grasp on the idea of what makes a computer algorithm efficient or not, so one of the really dumb ways I came up with was to go to each X-Y coordinate and use the textbook equation for a circle - see if X squared plus Y squared was greater than a number. Anyway, you do lots of stupid stuff like that, and you get an intuitive idea of what "slices" of an altitude formula give you. I never was clever enough to optimize the algorithm with anything like marching squares. I just had a stupid amount of patience for watching my dumb BASIC programs fill in a picture one pixel at a time. (The result would be filled in circles/blobs, not the outline.)
...... I've been skeptical about this reality being a simulation....... Until I saw the batman thing... I'm not joking. This is causing me an existential crisis.
1. Draw gaussian "balls" with add function. 2. Render outline with some threshold. That's it. 13:20 There is similar statistic algorithm that upscales binary images.
It's funny, I learnt marching squares in a completely unrelated field. I mean, outside of computing. I actually learnt it while studying topography for engineering. I never had to implement it on a computer, but it's just a natural way of visualizing a land surface. I didn't know it was called "marching squares"; I didn't even know it had a name.
1. Draw your circles as discs (like a bitmap with white background and black discs) 2. Do a gaussian blur on that (heavy blur will results with smoother curves and circles will blend from a greater distance) 3. Perform thresholding so that the individual disks are the same size as before 4. Then do edge detection so you have circles not discs 5. Problem solved
After looking at metaballs for a while, they seem to be _much_ more general than just circles. It seems they can be generated with any kind of level curve. of the form f(v ⃗) = ±1, with curves usually defined as f(v ⃗) = r being transformed to r/f(v ⃗). f in this case doesn't need to be a circle. It doesn't even need to be an ellipse. It doesn't even need to be _closed._ Similarly, r doesn't have to be positive. It can also be negative, which makes that "negaball" "eat away" at the other metaballs.
I find it funny that i understood basically nothing about this problem, though i did understand the marching squares part just fine. But the one thing i really took away from this is just how BAD schools are at teaching young ones new concepts. [LECTURE] [EXAMPLES] [HOMEWORK] [EXAM] -> [FORGET] That is basically exactly how schools operate, and one could phrase it in a different manner. [BLA BLA BLA] [BORING IRRELEVANT] [PUNISHMENT] [JUDGEMENT DAY] -> [DISGUST] And you did touch on the solution to this particular problem, how should schools approach a new topic? And the answer is quite simple. Make it... [BUILD INTEREST] [WHY/WHAT/WHEN] [PLAY AROUND PRACTICALLY] [REWARD INNOVATION] -> [WAS FUN, WILL REMEMBER] I've learned ALMOST everything i know OUTSIDE of the school environment. After i learned the alphabet, simple arithmetic, some key words and phrases in English (non-English speaker here) i simply had so much disgust for the topic in a school environment that i was absent from most future classes on those subjects. Of course, finding knowledge was extremely difficult outside of school at the time i was a kid. And i didn't really have a taste for libraries. BUT, the moment i got interested in computers and the moment i got access to the internet where i could search for interesting things my knowledge base grew more than a thousand fold over just 3 years where i had already spent some 10 years in a school environment. I started out programming and i really enjoyed making shapes using cos(a) and sin(b), making circles was easy but i played around with different values a and b over time to create interesting squiggles and from there on i learned a lot of programming topics and so it snowballed into what I know today. Or to put it in other words, the reason i can read, write and speak fluent English today is not thanks to any school or any family relationship. It's because i got interested in programming and so for the topic of English, here's what the school should have done for me: BUILD INTEREST - So this guy goes to China to create a production line for a revolutionary new bicycle. But he doesn't speak neither Mandarin or Cantonese so he can't communicate with the executives owning the factories. Is there a language that is so commonly spoken across the world that you could pretty much bet on at least someone around there being able to speak it? What language is the movies on your television mostly broadcasted in outside of our own country's language? English is known by at least ~1% of Chinese people, which just happens to be the lowest spread in the whole world BUT one in a hundred Chinese people speak English on a daily basis. And one in five have at least some basic communication skills in English. WHY/WHAT/WHEN - The guy can use his communication skills in English to explain in simple terms what he wants to have done alongside some drawings and requirements of materials, even when speaking to those that have the most basic knowledge of the English language. Imagine how little progress there would have been if not a single word was understood between the two parties. Now apply this logic to any other international endeavor, especially when meeting other native English speakers such as you would whenever you go to the US. PLAY AROUND PRACTICALLY - "Hevlow maj nejm ish Hans unt aj äm fram Görmany" -"Excuse me?" Instead of focusing so much effort on learning the intricate details of the language in the early stage, just play around with it. Communicate in English to set up a bicycle production line (these topics of course will tie in to other classes around the school focusing on the same task) and see how much your current knowledge of English helps and realize how much more you need to learn TOGETHER before you can communicate your intentions between each other in English. REWARD INNOVATION - Those that progress the farthest through innovating communication solutions beyond strictly following the rules of the language will be rewarded with more third party interest in their product. Outside actors (usually teachers) would gather around those with the best communication abilities and show that those that need to learn more should spend more time doing that instead of wasting time learning about sports and reality TV etc. Those who do fall between the cracks will of course need some special assistance and so that's where focus will be put outside the project, teaching them what words to use in certain situations so they can catch up with the rest of the group. ... I personally live by this type of thought process on a daily basis. While i am not a teacher, i am responsible for introducing and mentoring new arrivals at work. Where i don't just say "do this, this and that exactly like this" but instead spend a little extra time talking about why what we do is great, WHY we do things like this/that/thus and what to do when. I then let the new arrivals figure it out on their own for a while, only stepping in when what they are doing is harmful to the end product of the company i work for. At this point i steer them towards finding the best method FOR THEM. Not for me, not for the company but for them individually. Not everyone are the same shape, we all have differences in agility, strength and mental abilities which determine how we accomplish something. And of course most importantly of all, i REWARD them whenever they come up with a solution that works well for both themselves AND the team as a whole. Every time they do something that HELPS them and us i offer encouragement and say things like "I wish i spent more time working together with you". Which i actually do wish, because i arrived at this workplace well into the "mid term" so to speak. People there have been taught in the "traditional" manner of "this is how we do things PERIOD" and any innovations they have had have been left unnoticed and so they have only learned to dislike what they do and innovate ways to NOT DO IT AT ALL. Such as just throwing a bunch of quantity of produce out there, not caring for quality. Buffering up a lot of sub-par materials so they can sit around checking their phone and complain about how slowly the time is passing. I just hope that the new arrivals don't take after the old guard and that whenever they move on to other workplaces they remember their old place as being FUN, even at the worst of times.
If border meets other border, then join shape. When original shape exits border display original shape. Yeah, I'm a high level coder. You can't afford me 😁
I really really love this video, and now I understand a lot of new things. When you introduced the problem, I had the same 3 questions that you proposed! Thank you, great video.
I had seen marching cubes on Sebastian Lague's channel already, so when I saw you start talking about marching squares I thought to myself "I wonder if he'll bring up Sebastian's video once he gets to cubes?" and I cackled out loud when you did.
I think it's important to mention that for concluding the point (x,y) such that f(x,y) = 1 must be on a line between two points with f(x,y) < 1 and f(x,y) > 1 one must assume f is continuous. And a function to be approximately linear between too point close in space, f should be differentiable
14:43: "A reasonably simple solution that makes the approximation better...". In most cases, but the region we're examining may fill anything at all inside that square except the centre point. In a worst-case scenario this proposed method won't improve the technique at all.
Could the algorithm follow the contour around, adjacent square by square (once you’ve found one), until you loop back, rather than searching all of them? Most sets of four grid points are a waste of computation. I suppose this wouldn’t help with parallelising it in a GPU, but in some cases like circles it might be faster than a shader call? One could also dynamically change the size of each square based on the curvature of the approximate contour to try and capture more detail in such areas.
