6 ms·

Metaballs and Marching Squares

124 points by bobbiechen 6y ago

tylorr 6y ago
I used metaballs and marching cubes on a Kinext game project back in college and had no idea how it actually worked (copy and pasted a lot of code). This description was very helpful to finally understand it.
BugsJustFindMe 6y ago
If you care about doing metaballs well, you should check out http://www.geisswerks.com/ryan/BLOBS/blobs.html http://www.geisswerks.com/ryan/BLOBS/blobs.html from the creator of Milkdrop (among many other cool accomplishments) in 2000. It shows how naively aggregating charge from across the entire field leaves a lot on the table and there are huge efficiency gains that can be achieved. The page also includes descriptions of metacubes and metatorii.
- RBerenguel 6y ago
  I checked this as a reference when I implemented this p5js sketch (note that the link takes you to a blog post with how it works and inspiration, the first link in the post is to the sketch proper) [1] but never went into the hard optimisations once I got it working. I should revisit it, since it's relatively slow. [1]: https://mostlymaths.net/2020/05/blot-painting-p5js-sketch.html/ https://mostlymaths.net/2020/05/blot-painting-p5js-sketch.ht...
tobr 6y ago
You could get something visually similar by animating sprites with blurry edges, and thresholding the composite image. I can’t imagine that would be too expensive to do at high resolution in JavaScript.
- jmiskovic 6y ago
  Depending on blur function the result could be identical. Rendering blurred balls means brute-force calculation of contribution of each metaball for each rendered pixel. The larger your blurred image, the higher your fill rate will be. This would choke the performance for large number of balls. You also end up with sampled (pixelized) output which doesn't give you normals and similar geometry information.
  - rezmason 6y ago
    If your metaballs are mostly the same size, the blurring step can happen ahead of time with a commutative convolution, stored in the texture. Then, rather than applying a threshold to the resulting pixel/voxel contribution, you can apply a sigmoid function (or something cheaper approximating it) and get smooth edges. You can cheat normals like you can with any other sort of height map, by measuring the differences between neighboring fragments. like so: https://rezmason.net/scourge/quick_metaballs.mp4 https://rezmason.net/scourge/quick_metaballs.mp4
- pixelpoet 6y ago
  80s/90s demoscene had a lot of exactly this :) And of course the 3d blobs via marching cubes.
CodeGlitch 6y ago
Wasn't the algorithm wrapped up in a software patent until about 10/15 years ago? I'm sure I looked into using this when I was in the games industry but couldn't due to the patent.
- maffydub 6y ago
  Yes, I think it's https://patents.google.com/patent/US4719585A/en https://patents.google.com/patent/US4719585A/en. It appears to be specifically the marching cubes (i.e. 3D) algorithm - this article just describes the marching squares (i.e. 2D) algorithm.
  - expliced 6y ago
    And people got around the patent by using the marching tetrahedra algorithm, which uses tetrahedrons instead of cubes.
  - rzzzt 6y ago
    It did expire in 2005, according to the page.
andreareina 6y ago
Implemented in POV-Ray using spheres and cylinders as the base shape: http://www.f-lohmueller.de/pov_tut/all_shapes/shapes620e.htm http://www.f-lohmueller.de/pov_tut/all_shapes/shapes620e.htm
jmiskovic 6y ago
Another way to do blobby geometry are signed distance fields (SDFs). You define different geometry solids by specifying function which returns for any point in space how far that point is from the surface of the solid. [1] If they are defined this way, it is easy to smoothly interpolate between two or more solids. When rendering to screen, similar techniques have to be used to convert to screen geometry in realtime. The latest technical marvel that uses this tech is Media Molecules Dreams. With SDFs they made rich modelling tools (constructive solid geometry) that produce geometry for physics and painting-style renderer, all running on PS4. The Learning From Failure talk [2] was quite inspiring on lengths they went to achieve their artistic goals. [1] https://www.iquilezles.org/www/articles/distfunctions/distfunctions.htm https://www.iquilezles.org/www/articles/distfunctions/distfu... [2] https://www.youtube.com/watch?v=u9KNtnCZDMI https://www.youtube.com/watch?v=u9KNtnCZDMI
- frabert 6y ago
  Shameless plug: a couple of years ago I implemented a node editor for distance functions and renderer as a final project for a UI course at uni. https://github.com/frabert/MarchOfTheRays https://github.com/frabert/MarchOfTheRays Raymarching is a very interesting concept, no polygons at all!
  - rezmason 6y ago
    Nice work!
Asooka 6y ago
A better algorithm than marching cubes is surface nets, which doesn't have ambiguous cases and isn't patented AFAIK. See: https://0fps.net/2012/07/12/smooth-voxel-terrain-part-2/ https://0fps.net/2012/07/12/smooth-voxel-terrain-part-2/
- andybak 6y ago
  See also Dual Contouring as implemented in the libfive library.
- danparsonson 6y ago
  The patent appears to have expired fortunately: https://daac.hpc.mil/gettingStarted/Marching_Cubes.html https://daac.hpc.mil/gettingStarted/Marching_Cubes.html
cmenge 6y ago
For a moment, I was wondering how meatballs and Marching Squares could possibly be related... d'oh :)
ema 6y ago
When I experimented with 2D metaballs a decade ago I started with a low resolution scan and then subdivided all squares whose corners weren't either all inside or outside until I had individual pixels. Except for a few glitches when just checking the corners wasn't enough this worked rather well and was easy to implement.
ArtWomb 6y ago
Bookmarking this thread as it's evolving into an encyclopedia of metaball algorithms. And this is just geometry. Realistic fluid physics and chemical reactions extends the scope ad infinitum ;) One more from GPU Gems 3: Point-Based Visualization of Metaballs on a GPU https://developer.nvidia.com/gpugems/gpugems3/part-i-geometry/chapter-7-point-based-visualization-metaballs-gpu https://developer.nvidia.com/gpugems/gpugems3/part-i-geometr...
Pulcinella 6y ago
I wonder if is possible to have it so that when circles are moving towards each other they behave as spheres, but once they have “touched” and begin to move away they have the metaball behavior. That way they look like droplets when separating but don’t have the droplets “magically” seeking other droplets when moving towards each other.
- panzerklein 6y ago
  Should be easy to isolate objects that haven't touched anything yet. Determining when to start isolating already touching objects would be harder. Probably some kind of threshold is needed.
gdubs 6y ago
A while back I put a lot of work into doing 3D implicit surfaces in Swift and Metal (Apple’s low level graphics framework). I put together this video to show what’s going on in the process: https://www.instagram.com/p/BwGgYyQgCO1/?igshid=1cvb4smiik3i9 https://www.instagram.com/p/BwGgYyQgCO1/?igshid=1cvb4smiik3i... A little more polished and optimized “lava lamp” type loop: https://www.instagram.com/p/By9er1LFRKt/?igshid=iu9ouexd7tvs https://www.instagram.com/p/By9er1LFRKt/?igshid=iu9ouexd7tvs Most of it was standing on the shoulders of Tim Bourke’s work [1] and making it all work in GPU shaders. As others have mentioned, Ray Marching is also a nice approach if you don’t need polygons — you can get some really impressive and smooth effects. 1: http://paulbourke.net/geometry/implicitsurf/ http://paulbourke.net/geometry/implicitsurf/
joshuak 6y ago
August 19, 2014, just FYI
bluedino 6y ago
Let me just point out how amazing online resources are, now, compared to "not that long ago". Let's go back in time to 1994. You are a teenager armed with a computer, modem, possibly internet access but more likely an online service such as CompuServe. Since you also have a C or Pascal compiler, and are inspired by the latest trend of 3D graphics in PC games, you download the comp.graphics.algorithims FAQ. You read something about 'Marching Cubes' but don't really grasp anything from it. You also probably don't have access to the textbook or papers that also describe it. Instead of this incredible visual demonstration, you get a couple paragraphs of text and some ASCII art: ---------------------------------------------------------------------- Subject 5.10: What is the marching cubes algorithm? The marching cubes algorithm is used in volume rendering to construct an isosurface from a 3D field of values. The 2D analog would be to take an image, and for each pixel, set it to black if the value is below some threshold, and set it to white if it's above the threshold. Then smooth the jagged black outlines by skinning them with lines. The marching cubes algorithm tests the corner of each cube (or voxel) in the scalar field as being either above or below a given threshold. This yields a collection of boxes with classified corners. Since there are eight corners with one of two states, there are 256 different possible combinations for each cube. Then, for each cube, you replace the cube with a surface that meets the classification of the cube. For example, the following are some 2D examples showing the cubes and their associated surface. - ----- + - ----- - - ----- + - ----- + |:::' | |:::::::| |:::: | | ':::| |:' | |:::::::| |:::: | |. ':| | | | | |:::: | |::. | + ----- + + ----- + - ----- + + ----- - The result of the marching cubes algorithm is a smooth surface that approximates the isosurface that is constant along a given threshold. This is useful for displaying a volume of oil in a geological volume, for example. References: "Marching Cubes: A High Resolution 3D Surface Construction Algorithm", William E. Lorensen and Harvey E. Cline, Computer Graphics (Proceedings of SIGGRAPH '87), Vol. 21, No. 4, pp. 163-169. [Watt:Animation] pp. 302-305 and 313-321 [Schroeder]
- dekhn 6y ago
  Although the resources weren't great, most people in CG think marching cubes is "obvious" because the algorithm was independently discovered by a large number of people (without needing a guide like this!)

124 points by bobbiechen 6y ago

I used metaballs and marching cubes on a Kinext game project back in college and had no idea how it actually worked (copy and pasted a lot of code). This description was very helpful to finally understand it.

BugsJustFindMe 6y ago

If you care about doing metaballs well, you should check out http://www.geisswerks.com/ryan/BLOBS/blobs.html http://www.geisswerks.com/ryan/BLOBS/blobs.html from the creator of Milkdrop (among many other cool accomplishments) in 2000. It shows how naively aggregating charge from across the entire field leaves a lot on the table and there are huge efficiency gains that can be achieved. The page also includes descriptions of metacubes and metatorii.

RBerenguel 6y ago
I checked this as a reference when I implemented this p5js sketch (note that the link takes you to a blog post with how it works and inspiration, the first link in the post is to the sketch proper) [1] but never went into the hard optimisations once I got it working. I should revisit it, since it's relatively slow. [1]: https://mostlymaths.net/2020/05/blot-painting-p5js-sketch.html/ https://mostlymaths.net/2020/05/blot-painting-p5js-sketch.ht...

tobr 6y ago

You could get something visually similar by animating sprites with blurry edges, and thresholding the composite image. I can’t imagine that would be too expensive to do at high resolution in JavaScript.

jmiskovic 6y ago
Depending on blur function the result could be identical. Rendering blurred balls means brute-force calculation of contribution of each metaball for each rendered pixel. The larger your blurred image, the higher your fill rate will be. This would choke the performance for large number of balls. You also end up with sampled (pixelized) output which doesn't give you normals and similar geometry information.
- rezmason 6y ago
  If your metaballs are mostly the same size, the blurring step can happen ahead of time with a commutative convolution, stored in the texture. Then, rather than applying a threshold to the resulting pixel/voxel contribution, you can apply a sigmoid function (or something cheaper approximating it) and get smooth edges. You can cheat normals like you can with any other sort of height map, by measuring the differences between neighboring fragments. like so: https://rezmason.net/scourge/quick_metaballs.mp4 https://rezmason.net/scourge/quick_metaballs.mp4
pixelpoet 6y ago
80s/90s demoscene had a lot of exactly this :) And of course the 3d blobs via marching cubes.

CodeGlitch 6y ago

Wasn't the algorithm wrapped up in a software patent until about 10/15 years ago? I'm sure I looked into using this when I was in the games industry but couldn't due to the patent.

maffydub 6y ago
Yes, I think it's https://patents.google.com/patent/US4719585A/en https://patents.google.com/patent/US4719585A/en. It appears to be specifically the marching cubes (i.e. 3D) algorithm - this article just describes the marching squares (i.e. 2D) algorithm.
- expliced 6y ago
  And people got around the patent by using the marching tetrahedra algorithm, which uses tetrahedrons instead of cubes.
- rzzzt 6y ago
  It did expire in 2005, according to the page.

andreareina 6y ago

Implemented in POV-Ray using spheres and cylinders as the base shape: http://www.f-lohmueller.de/pov_tut/all_shapes/shapes620e.htm http://www.f-lohmueller.de/pov_tut/all_shapes/shapes620e.htm

jmiskovic 6y ago

Another way to do blobby geometry are signed distance fields (SDFs). You define different geometry solids by specifying function which returns for any point in space how far that point is from the surface of the solid. [1] If they are defined this way, it is easy to smoothly interpolate between two or more solids. When rendering to screen, similar techniques have to be used to convert to screen geometry in realtime. The latest technical marvel that uses this tech is Media Molecules Dreams. With SDFs they made rich modelling tools (constructive solid geometry) that produce geometry for physics and painting-style renderer, all running on PS4. The Learning From Failure talk [2] was quite inspiring on lengths they went to achieve their artistic goals. [1] https://www.iquilezles.org/www/articles/distfunctions/distfunctions.htm https://www.iquilezles.org/www/articles/distfunctions/distfu... [2] https://www.youtube.com/watch?v=u9KNtnCZDMI https://www.youtube.com/watch?v=u9KNtnCZDMI

frabert 6y ago
Shameless plug: a couple of years ago I implemented a node editor for distance functions and renderer as a final project for a UI course at uni. https://github.com/frabert/MarchOfTheRays https://github.com/frabert/MarchOfTheRays Raymarching is a very interesting concept, no polygons at all!
- rezmason 6y ago
  Nice work!

Asooka 6y ago

A better algorithm than marching cubes is surface nets, which doesn't have ambiguous cases and isn't patented AFAIK. See: https://0fps.net/2012/07/12/smooth-voxel-terrain-part-2/ https://0fps.net/2012/07/12/smooth-voxel-terrain-part-2/

andybak 6y ago
See also Dual Contouring as implemented in the libfive library.
danparsonson 6y ago
The patent appears to have expired fortunately: https://daac.hpc.mil/gettingStarted/Marching_Cubes.html https://daac.hpc.mil/gettingStarted/Marching_Cubes.html

cmenge 6y ago

For a moment, I was wondering how meatballs and Marching Squares could possibly be related... d'oh :)

ema 6y ago

When I experimented with 2D metaballs a decade ago I started with a low resolution scan and then subdivided all squares whose corners weren't either all inside or outside until I had individual pixels. Except for a few glitches when just checking the corners wasn't enough this worked rather well and was easy to implement.

ArtWomb 6y ago

Bookmarking this thread as it's evolving into an encyclopedia of metaball algorithms. And this is just geometry. Realistic fluid physics and chemical reactions extends the scope ad infinitum ;) One more from GPU Gems 3: Point-Based Visualization of Metaballs on a GPU https://developer.nvidia.com/gpugems/gpugems3/part-i-geometry/chapter-7-point-based-visualization-metaballs-gpu https://developer.nvidia.com/gpugems/gpugems3/part-i-geometr...

Pulcinella 6y ago

I wonder if is possible to have it so that when circles are moving towards each other they behave as spheres, but once they have “touched” and begin to move away they have the metaball behavior. That way they look like droplets when separating but don’t have the droplets “magically” seeking other droplets when moving towards each other.

panzerklein 6y ago
Should be easy to isolate objects that haven't touched anything yet. Determining when to start isolating already touching objects would be harder. Probably some kind of threshold is needed.

gdubs 6y ago

A while back I put a lot of work into doing 3D implicit surfaces in Swift and Metal (Apple’s low level graphics framework). I put together this video to show what’s going on in the process: https://www.instagram.com/p/BwGgYyQgCO1/?igshid=1cvb4smiik3i9 https://www.instagram.com/p/BwGgYyQgCO1/?igshid=1cvb4smiik3i... A little more polished and optimized “lava lamp” type loop: https://www.instagram.com/p/By9er1LFRKt/?igshid=iu9ouexd7tvs https://www.instagram.com/p/By9er1LFRKt/?igshid=iu9ouexd7tvs Most of it was standing on the shoulders of Tim Bourke’s work [1] and making it all work in GPU shaders. As others have mentioned, Ray Marching is also a nice approach if you don’t need polygons — you can get some really impressive and smooth effects. 1: http://paulbourke.net/geometry/implicitsurf/ http://paulbourke.net/geometry/implicitsurf/

joshuak 6y ago

August 19, 2014, just FYI

bluedino 6y ago

Let me just point out how amazing online resources are, now, compared to "not that long ago". Let's go back in time to 1994. You are a teenager armed with a computer, modem, possibly internet access but more likely an online service such as CompuServe. Since you also have a C or Pascal compiler, and are inspired by the latest trend of 3D graphics in PC games, you download the comp.graphics.algorithims FAQ. You read something about 'Marching Cubes' but don't really grasp anything from it. You also probably don't have access to the textbook or papers that also describe it. Instead of this incredible visual demonstration, you get a couple paragraphs of text and some ASCII art: ---------------------------------------------------------------------- Subject 5.10: What is the marching cubes algorithm? The marching cubes algorithm is used in volume rendering to construct an isosurface from a 3D field of values. The 2D analog would be to take an image, and for each pixel, set it to black if the value is below some threshold, and set it to white if it's above the threshold. Then smooth the jagged black outlines by skinning them with lines. The marching cubes algorithm tests the corner of each cube (or voxel) in the scalar field as being either above or below a given threshold. This yields a collection of boxes with classified corners. Since there are eight corners with one of two states, there are 256 different possible combinations for each cube. Then, for each cube, you replace the cube with a surface that meets the classification of the cube. For example, the following are some 2D examples showing the cubes and their associated surface. - ----- + - ----- - - ----- + - ----- + |:::' | |:::::::| |:::: | | ':::| |:' | |:::::::| |:::: | |. ':| | | | | |:::: | |::. | + ----- + + ----- + - ----- + + ----- - The result of the marching cubes algorithm is a smooth surface that approximates the isosurface that is constant along a given threshold. This is useful for displaying a volume of oil in a geological volume, for example. References: "Marching Cubes: A High Resolution 3D Surface Construction Algorithm", William E. Lorensen and Harvey E. Cline, Computer Graphics (Proceedings of SIGGRAPH '87), Vol. 21, No. 4, pp. 163-169. [Watt:Animation] pp. 302-305 and 313-321 [Schroeder]

dekhn 6y ago
Although the resources weren't great, most people in CG think marching cubes is "obvious" because the algorithm was independently discovered by a large number of people (without needing a guide like this!)