Marching Squares

Visualising Scalar Fields : Marching Squares Part 2 : Metaballs

June 16, 2016

Tags: , , , , , , , , , , , , , , ,

Previous : Visualising Scalar Fields : Marching Squares Part 1 : Contour Map


In the demo project, open up Scenes/Metaballs and hit play. You’ll see that we have several circles that move around the screen and it looks like a 2D lava lamp. This is what we’ll be creating:

Screen Shot 2016-06-16 at 16.50.38

Scene view pictured on another frame, with gizmos to display the circles and debug lines to show the grid:

There are two changes in implementation between this and the contour map example – the way we generate the scalar field and making our scalar field non-static.

To get this working, we need to do the following:

  • Create a number of circles (Metaballs)
  • Each frame, move those circles and regenerate our scalar field
  • Marching squares as normal.

For this example, I’ll go through how to generate the values for the scalar field, some optimisation, and the ambiguous marching square cases (5 and 10). The rest isn’t really relevant to marching squares so I won’t go through it here, but you can take a look in the demo project for a basic implementation.

Generating the scalar field

We want it to we want to assign a value to each point on our grid relative to the distance from the centre of the circle, with the maximum value (the size of the radius) in the centre and tending towards 0 as the points get further away.

To determine if a corner point is inside a circle, we can use the following the equation:

(corner.x - circle.position.x)^2 + (corner.y - circle.position.y)^2 \leq  radius^2

Rearranging, we can see that the point is in the circle if the value is greater or equal to 1

\frac{radius^2}{((corner.x - circle.position.x)^2+(corner.y - circle.position.y)^2)} \geq 1

The value of any point in the circle must be greater or equal to 1, with points on the circumference having a value of 1. The following allows us to give any point in our grid a value relative to a circle:

f(x,y) = \frac{radius^2}{((x - circle.x)^2 + (y - circle.y)^2)}

We can use this equation to create our scalar field, with one final amendment. It is important in metaballs that the value given to a point is the sum of the value of the point for all the circles displayed. This is the part that allows the circles to connect as they approach one another.

f(x,y) = \sum_{i=0}^{n} \frac{radius_i^2}{((x - circle_i.x)^2 + (y - circle_i.y)^2)}

Now we know how to work out our scalar field, we simply follow the marching squares algorithm as normal, using the threshold value to determine the outlines of our isosurfaces.

Ambiguous Cases

The marching square ambiguous cases can be seen in this example when the circles get close to each other. They are easier to see if you lower the grid resolution down to about 20. If you tick UseAlternative5And10Cases in the Metaballs inspector, the saddle configuration for these cases will be used (where the two corners are joined with a block).

Screen Shot 2016-06-16 at 16.48.52

You can compare how these display with the separated configuration by unchecking the box again.

Screen Shot 2016-06-16 at 16.49.02

The separated configuration is the default setting for Metaballs – when we get case 5 or 10, we want the circle outlines to be separate.

Optimisation

If you look at the code in the demo project, you’ll notice that I’ve optimised it slightly.

Running at a grid resolution of 100 with several circles is pretty sluggish – I managed a frame rate of around 30-40. None of the calculations used are very intensive, but some are called a lot, particularly when we work out the corner values (4 corners per square x squares in grid x number of circles).

This is fairly simple to optimise. If you imagine iterating through a grid through column and row (bottom to top, from left to the right), when we get to a square with a value of y greater than 0, two of its corners will already have been given values, as the square below will have already been evaluated (it’s bottom corners will be the evaluated square below’s top corners). When we get to a square with a value of x > 0, it will share two corners with the square to the left of it (it’s left corners will be its evaluated neighbour’s right corners). So, for most squares in the grid (all except the first column and first row), we can get values for three corners, meaning we only have to evaluate the top right corner for most squares, and only the square at 0,0 needs to work out all four corner values. With this in mind, you can optimise the calculations – this is why you’ll see neighbour references in my GridSquare class.

Other obvious optimisations would be to reduce the grid resolution and/or the number of circles used. To increase the speed of the calculations, you could use threading, as the calculations for each corner can easily be done in parallel.

 

Click here to see the demo (opens in new tab).


Previous : Visualising Scalar Fields : Marching Squares Part 1 : Contour Map

Next : Visualising Scalar Fields : Marching Squares Part 3 : Tilemaps

0 likes

Author

Your email address will not be published.