# Ad: Scales Ahoy!

As you may know, I tend to get distracted from my main project if I get an idea that seems worth exploring. Recently I have been working on a mobile app for recognizing musical scales from user-selected notes.

The app is called ”Scales Ahoy!” and I’m hoping to release it on Google Play this coming spring! So if you are a musician, composer or just plain interested in making and/or understanding music theory check it out: scalesahoy.com. The website is still a work in progress, full features and links to Google Play will be added once the product is finished.

# Side trip: How to draw a line in Unity

I’ve been secretly working on a another game project (codename ”Grow Some Ball”). For that game I implemented a line drawing script since the Unity’s own Line Renderer was too restricted. The script draws a line during mouse dragging – between the start click point and the current mouse position. The line is a quad drawn with two adjacent triangles.

Mouse drag line drawn with red material (thickness increased to show the quad)

The code is quite straightforward and I though it might be useful to some of your starting with Unity (and mesh generation). It simply transforms the mouse drag screen coordinates to world coordinates (with z -1.0) and calculates the positions of the four vertices that form the line quad. So here it is!

using UnityEngine;

public class LineDrawer : MonoBehaviour
{
public Material lineMaterial;
public float lineZ = -1.0f;
public float lineThickness;

bool dragOn = false;

GameObject lineGO;
Mesh lineMesh;
Vector3[] lineNormals = new Vector3[4];
Vector3[] lineVertices = new Vector3[4];
int[] lineTriangles = new int[6];

Vector3 dragStartPosition;
Vector3 mouseCurrentPosition;

void Start ()
{
lineGO = new GameObject("DragLine");
MeshRenderer renderer =
renderer.material = lineMaterial;

lineMesh = new Mesh();
MeshFilter meshFilter = lineGO.AddComponent<MeshFilter>();
meshFilter.mesh = lineMesh;

lineTriangles[0] = 0;
lineTriangles[1] = 1;
lineTriangles[2] = 2;
lineTriangles[3] = 0;
lineTriangles[4] = 2;
lineTriangles[5] = 3;
lineNormals[0] = new Vector3(-1.0f, 0.0f, 0.0f);
lineNormals[1] = new Vector3(-1.0f, 0.0f, 0.0f);
lineNormals[2] = new Vector3(-1.0f, 0.0f, 0.0f);
lineNormals[3] = new Vector3(-1.0f, 0.0f, 0.0f);
lineVertices[0] = new Vector3(0.0f, 0.0f, lineZ);
lineVertices[1] = new Vector3(0.0f, 0.0f, lineZ);
lineVertices[2] = new Vector3(0.0f, 0.0f, lineZ);
lineVertices[3] = new Vector3(0.0f, 0.0f, lineZ);
}

void DrawDragLine()
{
Debug.Assert(dragOn);

if (dragStartPosition == mouseCurrentPosition) return;

Vector3 lineStart;
Vector3 lineEnd;

if (dragStartPosition.x > mouseCurrentPosition.x)
{
lineStart = mouseCurrentPosition;
lineEnd = dragStartPosition;
}
else
{
lineStart = dragStartPosition;
lineEnd = mouseCurrentPosition;
}

float angle = Mathf.Atan2(
lineEnd.y - lineStart.y, lineEnd.x - lineStart.x);
float angle2 = Mathf.PI / 2.0f - angle;
float dx = lineThickness * Mathf.Cos(angle2);
float dy = lineThickness * Mathf.Sin(angle2);

lineVertices[0].x = lineStart.x + dx;
lineVertices[0].y = lineStart.y - dy;

lineVertices[1].x = lineStart.x - dx;
lineVertices[1].y = lineStart.y + dy;

lineVertices[2].x = lineEnd.x - dx;
lineVertices[2].y = lineEnd.y + dy;

lineVertices[3].x = lineEnd.x + dx;
lineVertices[3].y = lineEnd.y - dy;

lineMesh.vertices = lineVertices;
lineMesh.triangles = lineTriangles;
lineMesh.normals = lineNormals;
}

void Update ()
{
if (!dragOn)
{
if (Input.GetMouseButtonDown(0))
{
dragStartPosition = Camera.main.ScreenToWorldPoint(
Input.mousePosition);
dragOn = true;
}
}
else
{
if (Input.GetMouseButton(0))
{
mouseCurrentPosition =
Camera.main.ScreenToWorldPoint(
Input.mousePosition);
DrawDragLine();
}
else
{
if (Input.GetMouseButtonUp(0))
{
lineMesh.Clear();
dragOn = false;
}
}
}
}
}

Sorry for the lack of syntax highlighting 🙁 If your want to test the script create a new 2D project in Unity, create an empty GameObject to the scene and drag the script to it (so it becomes a Component). Assign a material to the script in the Inspector and select the desired line thickness. Have fun!

# Busy!

The blog has been quiet since I have been busy with personal stuff, moving into a new apartment etc. But the game is project is still going on!

I have been experiencing some glitches with my splitting / triangulation algorithm. At the moment I am testing the splitting code by splitting meshes with a randomly placed and oriented plane to pinpoint the cases where the errors occur (e.g. the split intersection cannot be triangulated, holes in meshes, etc.).

After the bug fixes I am hoping to move on into one of the following topics: breaking an armature with a plane, blood with GPU particles or implementing a dynamically controllable ragdoll character. So stay tuned 🙂

# Little progress is still progress!

I wanted to share a screenshot from Unity to show something concrete. I created a simple low-poly humanoid model in Blender. Then I imported it into Unity and cut in half with my mesh splitting algorithm.

The splitter still leaves holes in meshes (triangles missing) and doesn’t always find an edge loop to triangulate 🙁 So some work is still needed! But I hope the screenshot gives you an idea of the gameplay I am aiming for in this game – knights battling and cutting of limbs!

# Joining adjacent triangles

Previously I wrote about useless triangles that are created when a mesh is split in two. By useless I mean they are adjacent to each other and on the same plane (plus have the same normal vectors). So why not join them? In the following I present two simple rules that can be used to determine if three triangles (created by splitting a mesh by plane) can be presented with two triangles.

## From polygon to triangles

We need to reduce the number of triangles in a mesh. A quad (polygon with four vertices) can be represented with two triangles. So if we find quads that consist of more than two triangles we optimize!

A quad can be presented with two triangles, a polygon with five vertices needs more.

When looking for optimization candidates we only have to check the triangles that have one or two vertices on the splitting plane. We don’t want to accidentally ”optimize” other parts of the model that should be unaffected by the splitting 🙂 Also, if a triangle has one or all vertices on the splitting plane it is not interesting as it is not split.

## A quad with three triangles, gross!!

If we take a triangle that has one or two vertices on a plane we have one of the following ”neighborhood situations”:

The light green triangle has one or two vertices on the splitting plane (yellow line). All the triangles are on the same plane.

Below the triangles is the number of vertices in a polygon created by the intersecting triangle (light green) and its neighbors. If n = 4 we have a quad and we can represent that with two triangles. If n = 3 the situation is even better – we can represent all three triangles with a single triangle. Cool! If n > 4 we cannot join the triangles since impossibru!

Thats it! In one of the next articles I will show what kind of impact these two simple optimizations can actually have when implemented (in Unity).

# Generating a mesh in Unity

Before writing about split mesh optimization I would like share a simple example that generates a mesh from scratch in Unity. The example is in C# and for Unity since I use it in my project 🙂

Generating a mesh allows manipulating of existing scene meshes or creation of new ones. For example, when splitting a mesh in half we have to modify the mesh of the original game object (since it is ”losing” a part) and create a new mesh for a new GameObject (the detached part).

In the following example I create a pyramid mesh and a GameObject to bring that mesh to the scene. We start by creating a new Mesh object:

Mesh newMesh = new Mesh();

Once we have a mesh we have to define its geometry. A mesh consists of one or more triangles. A triangle is formed by joining three vertices. So we need a bunch of vertices to create triangles. To create a pyramid we need four vertices: three for the base and one for the tip:

Vector3[] vertices = new Vector3[4];

// Pyramid base vertices
vertices[0] = new Vector3(-1.0f, 0.0f, 0.0f);
vertices[1] = new Vector3(0.0f, 0.0f, -1.5f);
vertices[2] = new Vector3(1.0f, 0.0f, 0.0f);

// Pyramid tip vertex
vertices[3] = new Vector3(0.0f, 1.0f, -0.8f);

Now we have vertices, let’s create the triangles! A common practice to specify triangle vertices is with indices that point to the vertex array:

int numTriangles = 4;
int[] triangleIndices = new int[3 * numTriangles];

// Botton triangle
triangleIndices[0] = 0;
triangleIndices[1] = 1;
triangleIndices[2] = 2;

// Side triangles
triangleIndices[3] = 0;
triangleIndices[4] = 3;
triangleIndices[5] = 1;

triangleIndices[6] = 1;
triangleIndices[7] = 3;
triangleIndices[8] = 2;

triangleIndices[9] = 2;
triangleIndices[10] = 3;
triangleIndices[11] = 0;

Now we have one array that contains the vertex positions and one array that specifies the triangles. Next we have assign them to the mesh:

newMesh.vertices = vertices;
newMesh.triangles = triangleIndices;

Important: as far as I know the size of Mesh.triangles has to be divisible by three.

To bring the new mesh to the scene we need the following:

GameObject pyramidGameObject = new GameObject("PeteThePyramid");
MeshFilter mf = pyramidGameObject.AddComponent<MeshFilter>();
mf.mesh = newMesh;

MeshRenderer component is needed so we actually see the mesh 🙂 (although without assigning a material to it we see the default magenta ”no material” color when pressing play). MeshFilter binds the newly created mesh to this GameObject.

The triangle that the code above creates should look something like this (wireframe mode in Scene view, paused):

I GIMPed the numbers on top of the triangle to show which vertices (of the array ”vertices”) are which.

When defining triangles with vertex indices the order of the vertices is VERY important. In Unity triangles are defined by listing the vertices in clockwise order (from the camera viewpoint). So the visible triangles in the picture above would be 0-3-1, 1-3-2 and 2-3-0.

If we define the last triangle in counter-clockwise order like this…

triangleIndices[9] = 0;
triangleIndices[10] = 3;
triangleIndices[11] = 2;

…the winding order of the triangle would be reversed and the triangle would not be visible:

So be careful when defining triangles!

Now we have a simple pyramid mesh in the scene, cool! As you see generating a mesh is fairly simple but I wanted to post this since there cannot be too many examples 🙂

THE END

Special bonus to make thing more herp derp:

MeshCollider mc = pyramidGameObject.AddComponent<MeshCollider>();
mc.convex = true;
mc.sharedMesh = newMesh;
Rigidbody rb = pyramidGameObject.AddComponent<Rigidbody>();

As you probably guessed this makes the mesh a collider and adds a RigidBody component to the new GameObject. A view of the MeshCollider:

# Problem: coplanar neighbor triangles

Splitting an already split mesh just by splitting all of the triangles that intersect the splitting plane and outputting a new set of triangles creates an bunch of new triangles that are adjacent to each other and are on the same plane.

On the left: the original cube. Center: cube split in two – this is still ok. On the right: splitting the bottom part of the cube again creates triangles that could be joined to their neighbors.

These triangles are essentially useless since in most cases they can be joined to their neighboring triangles. This optimization is not mandatory but the more your split your meshes the more messier it gets. The picture below illustrates one clear candidate for optimization.

Meshes containing very thin triangles caused by non-optimized splitting algorithm.

In the next articles I will explain a simple optimization technique which will hopefully reduce the number of triangles in you scene significantly.

# Triangle splitting and polygon triangulation

## Triangle splitting

The first problem I needed to solve was how to split a mesh (at least a convex one) in two with a plane. This will hopefully be a helpful tool for severing arms, legs and heads 🙂

A simple cube and a split plane

I started by splitting all the mesh triangles that intersect the splitting plane. The splitting algorithm I wrote is based on two very helpful articles written by Randy Gaul:

After the split we have a bunch of triangles that are on one side of the plane and a bunch of triangles that are on the other side of the plane. One could use these triangles to output two meshes but they would be missing a face (the intersection area).

## Filling ”the gap”

### Intersection polygon

So both of the meshes (or ”bunch of triangles”) created have an intersection area that has to be filled. This can be done by calculating a polygon from the intersection area and triangulating that into a face.

Triangles that are ”touching” the intersection plane have vertices that are on the intersection plane. From these vertices, I calculated the longest ”streak” of vertices that are connected to each other (with an edge) trying to ”get around” the intersection area. Hopefully this forms an edge loop (first and last vertices are connected) and we have the polygon that we can fill.

### Triangulation

Filling a polygon means (in this context) triangulating the polygon. I used an simple polygon ear clipping method described in Ear-clipping Based Algorithms of Generating High-quality Polygon Triangulation.

Splitting a mesh and triangulating the intersection area were my first steps in this coding adventure. The first implementation was not very robust and needed many optimizations to reduce excess triangle creation. I will try to write about them in the following articles.

Cube split in two (meshes)

Triangulated intersection area in a cylinder showing very ”thin” triangles caused by the ear clipping method