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:

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; }

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:

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:

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;

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:

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:

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.

## One thought on “Marching Squares with distance functions”