Marching Squares with distance functions

Development on the “worms” project (blog 1, blog 2) has been going somewhat slowly, but today I have implemented a few key features I have been wanting to. At the point of my previous blog regarding this project, I had implemented marching squares and a player controller, the marching squares worked off of noise generation which was just a random number in each grid tile for the map data. Currently it works with distance functions for a controlled generation.

I began working on the distance functions last week with a circle being generated in the world with the algorithm:

 float Circle (Vector2 circlePos, Vector2 pointPos, float r)
 {
     return (pointPos - circlePos).magnitude - r;
 }

This gave me the distance to the surface of the circle:

1.png

As you can see, the edges are rather… blocky. The reason behind this was the fact that I was just checking if grid space had a value less than 0, which meant that it looks the same as something made out of squares. To fix this, when I generated the vertices, I shifted them along the x and y axes depending on the value in their corresponding grid space and if any surrounding values were above 0:

 void AdjustPosition(ref Vector3 orig, int x, int y)
 {
     //the offset that the vertice will have
     Vector3 relative = new Vector3();
     for (int xx = -1; xx <= 1; xx += 2)
     {
         for (int yy = -1; yy <= 1; yy += 2)
         {
             if (CoordWithinWorld(x + xx, y + yy))
             {
                 if(world[x + xx][y + yy] >= 0)
                 {
                     //add to the offset
                     relative.x += xx * world[x + xx][y + yy];
                     relative.y += yy * world[x + xx][y + yy];
                 }
             }
         }
     }

     //shift the original by the offset
     orig -= relative;
 }

2.png

The mesh generated is much more curved, but there are some problems with it, these of which I believe are created from the exclusion of the diagonal vertice adjustment (it only adjusts for the above, below, left, and right immediate grid spaces). While I was doing this, I found a funky outcome when I accidentally added the relative vector to the orig vector in the AdjustPosition method:

3.png

It was entertaining to me to see this, something I though you might have wanted to see as well.

I wanted to be able to generate multiple shapes in the mesh, something that would allow for a terrain of multiple shapes to be created, so I started with generating multiple circles. For doing the multiple circles, I decided to make a new class called ShapeData that has 1 variable and 1 method:

 public abstract class ShapeData
 {
     public Vector3 position;

     public abstract float Shape(Vector3 checkPos);
 }

The reason I made the class abstract was so I can never have an instance of this, I would need an instance of a child class, which would override the Shape method. The child class is:

 public class CircleShape : ShapeData
 {
     public float radius;

     public override float Shape(Vector3 checkPos)
     {
         return (checkPos - position).magnitude - radius;
     }
 }

 This holds all the information a circle should hold: a radius and position (in the parent class). The distance function of this is the same as the one created by Inigo Quilez for raymarching (Quilez).

Using an array of ShapeData, I put in CircleShapes and parse it into the GenerateWorldData method and have the grid value equal the smallest of the distances generated from the distance functions:

Shape generation:

 ShapeData[] GenerateInitialShapeData()
 {
     ShapeData[] shapes = new ShapeData[5];

     float positionScale = 2.0f;
 
     //generate 5 circles in the shape of the olympic rings for testing
     CircleShape circle1 = new CircleShape();
     circle1.position = Vector3.left * positionScale * radius - Vector3.up * positionScale * 0.5f * radius;
     circle1.radius = radius * 0.4f;

     CircleShape circle2 = new CircleShape();
     circle2.position = Vector3.left * positionScale * 0.5f * radius + Vector3.up * positionScale * 0.5f * radius;
     circle2.radius = radius * 0.4f;

     CircleShape circle3 = new CircleShape();
     circle3.position = Vector3.zero - Vector3.up * positionScale * 0.5f * radius;
     circle3.radius = radius * 0.4f;

     CircleShape circle4 = new CircleShape();
     circle4.position = Vector3.right * 0.5f * positionScale * radius + Vector3.up * 0.5f * positionScale * radius;
     circle4.radius = radius * 0.4f;

     CircleShape circle5 = new CircleShape();
     circle5.position = Vector3.right * positionScale * radius - Vector3.up * positionScale * 0.5f * radius;
     circle5.radius = radius * 0.4f;

     shapes[0] = circle1;
     shapes[1] = circle2;
     shapes[2] = circle3;
     shapes[3] = circle4;
     shapes[4] = circle5;

     return shapes;
 }

Within a nested for-loop for assigning the grid values

 newPoint = ScaleToWorldCoordinates(x, y);

 //go through all of the shapes and get the distance to their surface
 world[x][y] = shapeData[0].Shape(newPoint);

 for (int i = 1; i < shapeData.Length; ++i)
 {
     world[x][y] = Mathf.Min(shapeData[i].Shape(newPoint), world[x][y]);
 }

Mesh:

4.png

Now that I have this, I want to add in another unique shape, a rectangle. The rectangle is a little different, I won’t be able to use the same distance function that Inigo has on his website for the 3D version of a box(plus I have no idea what freaky Maths he is doing), so I’ll have to do it myself. I want to be able to stretch the rectangle to whatever size I want as well as rotate it, so after a bit of fiddling around, I was able to get:

 public class RectangleShape : ShapeData
 {
     public float rotation;

     public Vector3 size;

     public override float Shape(Vector3 checkPos)
     {
         //get where the position we are checking against is in local space
         Vector3 relative = checkPos - position;

         //rotate the rectangle by rotating the relative position we are checking
         relative = new Vector3(
             Mathf.Cos(rotation) * relative.x - Mathf.Sin(rotation) * relative.y,
             Mathf.Sin(rotation) * relative.x + Mathf.Cos(rotation) * relative.y,
             0);

         //make the relative positive in both axes being used
         relative.x = Mathf.Abs(relative.x);
         relative.y = Mathf.Abs(relative.y);

         relative -= size / 2.0f;

         return Mathf.Max(relative.x, relative.y);
     }
 }

Adding a rectangle to the mesh looked like:

 RectangleShape rect = new RectangleShape();
 rect.position = Vector3.zero;
 rect.rotation = Mathf.PI * 0.125f;
 rect.size = Vector3.one * radius + Vector3.right * 5.0f;

 shapes[5] = rect;

5.png

Which is exactly what I wanted. I had a few problems through this addition, but was able to get a rough result of what the end will be like. I am also able to distort the objects, which looks like:

6.png

That was a little fun to play around with, but all it is is just (in the Shape method for RectangleShape):

float percentageAlong = relative.x / size.x + 0.5f;

relative.y += Mathf.Sin(Mathf.PI * 9 * percentageAlong) - 5 * Mathf.Sin(Mathf.PI * percentageAlong);

A problem with the mesh generation I am currently doing is that the mesh is extremely high poly:

7.png

A problem with this is that performance will be lowered due to the number of faces being drawn and the size I am allowed to make the maps at will be affected. The above image shows a mesh created within the world of 400×400 grid spaces which has 36,030 vertices. The mesh has a bit over half of the maximum allowed vertices in a mesh, the maximum being 65,536 vertices, something 400×400 is greatly above (400×400 = 160,000). To overcome this, I’ll need to use an ear-clipping algorithm (Eberly 1) that I mentioned I wouldn’t be able to use due to the way ear-clipping works, but I can work around it by using an altered version that I’ll create later. 

References

Eberly, David. Triangulation By Ear Clipping. 1st ed. Geometric Tools, LLC, 2016. Web. 1 Aug. 2016.

Quilez, Inigo. “Inigo Quilez :: Fractals, Computer Graphics, Mathematics, Demoscene And More”.Iquilezles.org. N.p., 2016. Web. 1 Aug. 2016.

Advertisements

One thought on “Marching Squares with distance functions

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s