6 ms·

Metaballs and Marching Squares

109 points by zodiac 12y ago

VikingCoder 12y ago
You don't care, but I got to shake hands with Bill Lorensen (marching cubes), Alvy Ray Smith (cofound Pixar, co-invented the alpha channel), Jim Blinn (need I say more?), Tony DeRose (really improved Subdivision Surfaces), Anthony Apodaca (Director of Graphics Research and Development at Pixar Animation Studios, co-created RISpec)... I'm like a Computer Graphics groupie.
kirkbackus 12y ago
Something really cool about this approach is the marching squares algorithm is highly parallelizable which would make this a good candidate for GPU acceleration provided that there is enough memory.
- thibauts 12y ago
  I implemented marching cubes in the 00's to extract isosurface meshes from PET scans. As far as I can remember I had it operating real-time on regular CPUs. The volumes were in the order of 512^3 if my memory serves me well. I guess GPUs could help for very large volumes though.
  - jonhohle 12y ago
    You wouldn't need marching cubes to operate real time - it runs once, generates an iso-surface mesh which can be efficiently rendered in hardware. Edit: my thesis advisor was the first to prove that there were exactly 15 distinct configurations of voxels in MC, which gives you the ability to perform constant time lookup for the (configuration, rotation) for vertices on the edge of any particular voxel. http://graphics.stanford.edu/courses/cs164-10-spring/Handouts/paper_p83-nielson.pdf http://graphics.stanford.edu/courses/cs164-10-spring/Handout...
    - thibauts 12y ago
      The thing is there was slider to move the isosurface boundary.
    - VikingCoder 12y ago
      What he's referring to is a transfer function. The marching cubes are not just evaluated to find the surface where Voxel(xyz)=value But rather F(Voxel(xyz))=value What gets interesting is that both pre-interpolated, and post-interpolated versions are interesting.
- rdw 12y ago
  This is the basis of the Voxel Farm engine, which Miguel talks about in this early blog post: http://procworld.blogspot.com/2010/11/opencl-first-iteration.html http://procworld.blogspot.com/2010/11/opencl-first-iteration...
GuiA 12y ago
So metaballs aren't distinct mathematical objects that you can model on their own (like a fractal or a cylinder)- rather, they're artefacts that are created when sampling in certain ways circles/spheres intersecting?
- phleet 12y ago
  They don't inherently have to be sampled. Just like you can define the perimeter of a circle given constants (x_0, y_0, r): (x-x_0)^2 + (y-y_0)^2 = r^2 you can define the perimeter a metaball on a list of (x_i, y_i, r_i) as described in the post.
- jlarocco 12y ago
  No. Metaballs are a thing, and marching cubes is one way of implementing them. Another approach is ray-casting.
- corysama 12y ago
  Metaballs are a family of implicit equations that are visually interesting and easy to set up. They all come in the form of a summation of some function of distance from a control point over a set of control points. The appearance of spheres/circles intersecting is a consequence of the popular falloff-type functions. You can think of metaballs as a bunch of glowy points. The implicit surface that is shown is all of the points where the glows add up to some target value.
  - peterfirefly 12y ago
    Blumenthal, "Introduction to Implicit Surfaces". Possibly quite dated, though.
jjwiseman 12y ago
For a nice description of doing this in 3D: http://paulbourke.net/geometry/polygonise/ http://paulbourke.net/geometry/polygonise/ I used that in the 90s to do a Lisp implementation: http://people.cs.uchicago.edu/~wiseman/3D/marching-cubes/ http://people.cs.uchicago.edu/~wiseman/3D/marching-cubes/
userbinator 12y ago
I remember when almost every demo had metaballs in them. Now that's been replaced with distance functions/raymarching, which can produce far more interesting scenes.
- Voltage 12y ago
  I did some 3d metablobs using raymarching in a 4k exe. https://www.youtube.com/watch?v=sBcwQCBpEiE https://www.youtube.com/watch?v=sBcwQCBpEiE
asadlionpk 12y ago
I have used alpha threshold trick to achieve metaballs for my fluid simulation[1][2]. I wonder how efficient Marching Squares method is. [1]https://jsexperiments.herokuapp.com/sph/ https://jsexperiments.herokuapp.com/sph/ [2]https://github.com/asadlionpk/SPHjs https://github.com/asadlionpk/SPHjs
- w0utert 12y ago
  It's pretty efficient, O(N), where N is the number of cells (partially) covered by something (which means some pruning of the cells that need to be processed is desirable otherwise you'd have to evaluate all of them for quadratic complexity). The algorithm is also embarassingly parallel, every cell can be processed independently so it scales perfectly with the number of processors available (if you forget about contention effects).
thisjepisje 12y ago
Blender has 3d metaballs, if you want to play around with them without too much fuss.
jwmerrill 12y ago
Quick Desmos graph, if you want to play around with some of the math with less of the programming: https://www.desmos.com/calculator/mvnrzlrhrz https://www.desmos.com/calculator/mvnrzlrhrz

109 points by zodiac 12y ago

You don't care, but I got to shake hands with Bill Lorensen (marching cubes), Alvy Ray Smith (cofound Pixar, co-invented the alpha channel), Jim Blinn (need I say more?), Tony DeRose (really improved Subdivision Surfaces), Anthony Apodaca (Director of Graphics Research and Development at Pixar Animation Studios, co-created RISpec)... I'm like a Computer Graphics groupie.

kirkbackus 12y ago

Something really cool about this approach is the marching squares algorithm is highly parallelizable which would make this a good candidate for GPU acceleration provided that there is enough memory.

thibauts 12y ago
I implemented marching cubes in the 00's to extract isosurface meshes from PET scans. As far as I can remember I had it operating real-time on regular CPUs. The volumes were in the order of 512^3 if my memory serves me well. I guess GPUs could help for very large volumes though.
- jonhohle 12y ago
  You wouldn't need marching cubes to operate real time - it runs once, generates an iso-surface mesh which can be efficiently rendered in hardware. Edit: my thesis advisor was the first to prove that there were exactly 15 distinct configurations of voxels in MC, which gives you the ability to perform constant time lookup for the (configuration, rotation) for vertices on the edge of any particular voxel. http://graphics.stanford.edu/courses/cs164-10-spring/Handouts/paper_p83-nielson.pdf http://graphics.stanford.edu/courses/cs164-10-spring/Handout...
  - thibauts 12y ago
    The thing is there was slider to move the isosurface boundary.
  - VikingCoder 12y ago
    What he's referring to is a transfer function. The marching cubes are not just evaluated to find the surface where Voxel(xyz)=value But rather F(Voxel(xyz))=value What gets interesting is that both pre-interpolated, and post-interpolated versions are interesting.
rdw 12y ago
This is the basis of the Voxel Farm engine, which Miguel talks about in this early blog post: http://procworld.blogspot.com/2010/11/opencl-first-iteration.html http://procworld.blogspot.com/2010/11/opencl-first-iteration...

GuiA 12y ago

So metaballs aren't distinct mathematical objects that you can model on their own (like a fractal or a cylinder)- rather, they're artefacts that are created when sampling in certain ways circles/spheres intersecting?

phleet 12y ago
They don't inherently have to be sampled. Just like you can define the perimeter of a circle given constants (x_0, y_0, r): (x-x_0)^2 + (y-y_0)^2 = r^2 you can define the perimeter a metaball on a list of (x_i, y_i, r_i) as described in the post.
jlarocco 12y ago
No. Metaballs are a thing, and marching cubes is one way of implementing them. Another approach is ray-casting.
corysama 12y ago
Metaballs are a family of implicit equations that are visually interesting and easy to set up. They all come in the form of a summation of some function of distance from a control point over a set of control points. The appearance of spheres/circles intersecting is a consequence of the popular falloff-type functions. You can think of metaballs as a bunch of glowy points. The implicit surface that is shown is all of the points where the glows add up to some target value.
- peterfirefly 12y ago
  Blumenthal, "Introduction to Implicit Surfaces". Possibly quite dated, though.

jjwiseman 12y ago

For a nice description of doing this in 3D: http://paulbourke.net/geometry/polygonise/ http://paulbourke.net/geometry/polygonise/ I used that in the 90s to do a Lisp implementation: http://people.cs.uchicago.edu/~wiseman/3D/marching-cubes/ http://people.cs.uchicago.edu/~wiseman/3D/marching-cubes/

userbinator 12y ago

I remember when almost every demo had metaballs in them. Now that's been replaced with distance functions/raymarching, which can produce far more interesting scenes.

Voltage 12y ago
I did some 3d metablobs using raymarching in a 4k exe. https://www.youtube.com/watch?v=sBcwQCBpEiE https://www.youtube.com/watch?v=sBcwQCBpEiE

asadlionpk 12y ago

I have used alpha threshold trick to achieve metaballs for my fluid simulation[1][2]. I wonder how efficient Marching Squares method is. [1]https://jsexperiments.herokuapp.com/sph/ https://jsexperiments.herokuapp.com/sph/ [2]https://github.com/asadlionpk/SPHjs https://github.com/asadlionpk/SPHjs

w0utert 12y ago
It's pretty efficient, O(N), where N is the number of cells (partially) covered by something (which means some pruning of the cells that need to be processed is desirable otherwise you'd have to evaluate all of them for quadratic complexity). The algorithm is also embarassingly parallel, every cell can be processed independently so it scales perfectly with the number of processors available (if you forget about contention effects).

thisjepisje 12y ago

Blender has 3d metaballs, if you want to play around with them without too much fuss.

jwmerrill 12y ago

Quick Desmos graph, if you want to play around with some of the math with less of the programming: https://www.desmos.com/calculator/mvnrzlrhrz https://www.desmos.com/calculator/mvnrzlrhrz