【Unity】２DのMeshを直線で分割しよう

「Splitter Critters」というゲームが面白くて、どうやって作るか興味を持ったので、
2DのMeshを直線で分割する記事を書きました。

[Splitter Crittersの動画](http://www.youtube.com/watch?v=2-3mRQeficQ)
[![](http://img.youtube.com/vi/2-3mRQeficQ/0.jpg)](http://www.youtube.com/watch?v=2-3mRQeficQ)


# 1. 必要な知識の紹介
2DのMesh分割を実装するのに必要な３つの数学的な知識を先に紹介します。

## 1.1 直線による平面分割
直線による平面分割は外積の符号を利用します。

```csharp
private static bool IsClockWise(
	float x1, float y1,
	float x2, float y2,
	float x3, float y3)
{
	return (x2 - x1) * (y3 - y2) - (y2 - y1) * (x3 - x2) > 0;
}
```

画像説明：点A => 点B => ドットの順で見たときに、
時計回りなら赤色、反時計回りなら青色にドットを表示しています
![clockwise.gif](https://qiita-image-store.s3.amazonaws.com/0/153010/a7f8d128-2e1a-c3db-2ff1-37f2124228d3.gif)

## 1.2 直線と直線の交点
直線ABと直線CDの交点を求めます。
三角形ACDと三角形BCDの面積を外積で求めて、面積の比を計算します。（面積は符号付き）
面積の比は、点Aから交点までの長さ、点Bから交点までの長さに比に一致するので、交点の座標が求まります。

```csharp
public static bool GetLineAndLineIntersection(
	float x1, float y1,
	float x2, float y2,
	float x3, float y3,
	float x4, float y4,
	ref float x, ref float y)
{
	float s1 = (x4 - x3) * (y1 - y3) - (y4 - y3) * (x1 - x3);
	float s2 = (x4 - x3) * (y3 - y2) - (y4 - y3) * (x3 - x2);
	if ((s1 + s2) == 0f)
	{
		return false;
	}
	x = x1 + (x2 - x1) * s1 / (s1 + s2);
	y = y1 + (y2 - y1) * s1 / (s1 + s2);
	return true;
}
```

画像説明：2直線の交点を面積比で求めています
![intersection.gif](https://qiita-image-store.s3.amazonaws.com/0/153010/e3dbbb3e-0f49-b399-bf3b-7f7246ba21d7.gif)

参考：４点からなる交点の求め方
http://imagingsolution.blog107.fc2.com/blog-entry-137.html

## 1.3 線分と直線の交点

直線ABと線分CDの交点を求めます。
直線ABと直線CDの交点は1.2で求めるとができるので、直線ABと線分CDが交差するかだけ調べれば十分です。
ABCが時計回りか、ABDが時計回りかを調べて、向きが異なれば交差します。

```csharp
public static bool HasIntersectionLineAndLineStrip(
	float x1, float y1,
	float x2, float y2,
	float x3, float y3,
	float x4, float y4)
{
	float a = (x1 - x2) * (y3 - y1) + (y1 - y2) * (x1 - x3);
	float b = (x1 - x2) * (y4 - y1) + (y1 - y2) * (x1 - x4);
	return a * b < 0;
}
```

画像説明：点Cと点Dの色が異なれば直線ABと線分CDは交点をもつ
![intersection_linestrip.gif](https://qiita-image-store.s3.amazonaws.com/0/153010/73a134c8-0d8c-1877-e511-373583642b54.gif)

# 2. 三角形の分割
Unityの場合はMeshは三角形で構成されているので、三角形の分割ができればMesh分割が実装可能になります。
まず三角形ABCを直線PQで切断したときのケースを考えます。全部で5ケースです。

- 直線PQと三角形ABCが交わらない（時計回り側に存在：赤色）
- 直線PQと三角形ABCが交わらない（反時計回り側に存在：緑色）
- 直線PQが線分AB、線分BCと交わる
- 直線PQが線分AB、線分CAと交わる
- 直線PQが線分BC、線分CAと交わる

![triangle_cut.gif](https://qiita-image-store.s3.amazonaws.com/0/153010/991ffb72-1e8a-638e-1b47-cb1374d3497c.gif)

>
- 直線PQと三角形ABCが交わらない（時計回り側に存在：赤色）
- 直線PQと三角形ABCが交わらない（反時計回り側に存在：緑色）

こちらは1.1の直線による平面分割で求まります。
点ABCが全て時計回り側、または反時計回り側にあるか判定すればよいです。

>
- 直線PQが線分AB、線分BCと交わる
- 直線PQが線分AB、線分CAと交わる
- 直線PQが線分BC、線分CAと交わる

こちらは1.2の線分と直線の交点で求まります。
直線PQと三角形のそれぞれの辺が、交点を持つか調べれて、座標を求めれば良いです。

>
- 直線PQが線分AB、線分BCと交わる

このケースについてもう少し掘り下げていきます。
直線PQと線分ABの交点をD、直線PQと線分BCの交点をEと定義しましょう。
三角形が直線によってカットされるとき、【三角形BDE】と【四角形ACED】の2つに分割されます。
四角形ACEDは、三角形ACDと三角形CEDで表現できます。
三角形ABCをカットすると、【三角形BDE】、【三角形ACD】【三角形CED】に分割されるとわかりました。

画像説明：三角形がカットされたときに、1つの三角形と1つの四角形の2つに分割される
![triangle_cut_wireframe.gif](https://qiita-image-store.s3.amazonaws.com/0/153010/19cba636-4ac0-55f3-35b2-e5c261a5f518.gif)

# 3. 実装
ここまでで方針が決まりました。あとは実装しましょう。

```csharp
using System.Collections.Generic;
using UnityEngine;

namespace MeshCut2D
{
	// MeshCutの結果を管理するクラス
	public class MeshCutResult
	{
		public List<Vector3> vertices = new List<Vector3>();
		public List<Color32> colors = new List<Color32>();
		public List<int> indices = new List<int>();
		public List<Vector2> uv = new List<Vector2>();

		public void Clear()
		{
			vertices.Clear();
			colors.Clear();
			uv.Clear();
			indices.Clear();
		}

		public void AddTriangle(
			float x1, float y1,
			float x2, float y2,
			float x3, float y3,
			float uv1X, float uv1Y,
			float uv2X, float uv2Y,
			float uv3X, float uv3Y,
			Color color)
		{
			int vertexCount = vertices.Count;
			vertices.Add(new Vector3(x1, y1, 0));
			vertices.Add(new Vector3(x2, y2, 0));
			vertices.Add(new Vector3(x3, y3, 0));
			colors.Add(color);
			colors.Add(color);
			colors.Add(color);
			uv.Add(new Vector2(uv1X, uv1Y));
			uv.Add(new Vector2(uv2X, uv2Y));
			uv.Add(new Vector2(uv3X, uv3Y));
			indices.Add(vertexCount + 2);
			indices.Add(vertexCount + 1);
			indices.Add(vertexCount + 0);
		}

		public void AddRectangle(
			float x1, float y1,
			float x2, float y2,
			float x3, float y3,
			float x4, float y4,
			float uv1_X, float uv1_Y,
			float uv2_X, float uv2_Y,
			float uv3_X, float uv3_Y,
			float uv4_X, float uv4_Y,
			Color color)
		{
			int vertexCount = vertices.Count;
			vertices.Add(new Vector3(x1, y1, 0));
			vertices.Add(new Vector3(x2, y2, 0));
			vertices.Add(new Vector3(x3, y3, 0));
			vertices.Add(new Vector3(x4, y4, 0));
			colors.Add(color);
			colors.Add(color);
			colors.Add(color);
			colors.Add(color);
			uv.Add(new Vector2(uv1_X, uv1_Y));
			uv.Add(new Vector2(uv2_X, uv2_Y));
			uv.Add(new Vector2(uv3_X, uv3_Y));
			uv.Add(new Vector2(uv4_X, uv4_Y));
			indices.Add(vertexCount + 2);
			indices.Add(vertexCount + 1);
			indices.Add(vertexCount + 0);
			indices.Add(vertexCount + 0);
			indices.Add(vertexCount + 3);
			indices.Add(vertexCount + 2);
		}
	}

	public class MeshCut2D
	{
		public static void Cut(
			IList<Vector3> vertices,
			IList<Color32> colors,
			IList<Vector2> uv,
			IList<int> indices,
			int indexCount,
			float x1, // LinePoint1
			float y1, // LinePoint1
			float x2, // LinePoint2
			float y2, // LinePoint2
			MeshCutResult _resultsA,
			MeshCutResult _resultsB)
		{
			_resultsA.Clear();
			_resultsB.Clear();

			for (int i = 0; i < indexCount; i += 3)
			{
				// 使いやすいように変数に代入しているだけ
				int indexA = indices[i + 0];
				int indexB = indices[i + 1];
				int indexC = indices[i + 2];
				Vector3 a = vertices[indexA];
				Vector3 b = vertices[indexB];
				Vector3 c = vertices[indexC];
				Color color = colors[indexA];
				float uvA_X = uv[indexA].x;
				float uvA_Y = uv[indexA].y;
				float uvB_X = uv[indexB].x;
				float uvB_Y = uv[indexB].y;
				float uvC_X = uv[indexC].x;
				float uvC_Y = uv[indexC].y;

				bool aSide = IsClockWise(x1, y1, x2, y2, a.x, a.y);
				bool bSide = IsClockWise(x1, y1, x2, y2, b.x, b.y);
				bool cSide = IsClockWise(x1, y1, x2, y2, c.x, c.y);
				if (aSide == bSide && aSide == cSide)
				{
					var triangleResult = aSide ? _resultsA : _resultsB;
					triangleResult.AddTriangle(
						a.x, a.y, b.x, b.y, c.x, c.y,
						uvA_X, uvA_Y, uvB_X, uvB_Y, uvC_X, uvC_Y,
						color);
				}
				else if (aSide != bSide && aSide != cSide)
				{
					float abX, abY, caX, caY, uvAB_X, uvAB_Y, uvCA_X, uvCA_Y;
					GetIntersectionLineAndLineStrip(
						x1, y1,
						x2, y2,
						a.x, a.y,
						b.x, b.y,
						uvA_X, uvA_Y,
						uvB_X, uvB_Y,
						out abX, out abY,
						out uvAB_X, out uvAB_Y);
					GetIntersectionLineAndLineStrip(
						x1, y1,
						x2, y2,
						c.x, c.y,
						a.x, a.y,
						uvC_X, uvC_Y,
						uvA_X, uvA_Y,
						out caX, out caY,
						out uvCA_X, out uvCA_Y);
					var triangleResult = aSide ? _resultsA : _resultsB;
					var rectangleResult = aSide ? _resultsB : _resultsA;
					triangleResult.AddTriangle(
						a.x, a.y,
						abX, abY,
						caX, caY,
						uvA_X, uvA_Y,
						uvAB_X, uvAB_Y,
						uvCA_X, uvCA_Y,
						color);
					rectangleResult.AddRectangle(
						b.x, b.y,
						c.x, c.y,
						caX, caY,
						abX, abY,
						uvB_X, uvB_Y,
						uvC_X, uvC_Y,
						uvCA_X, uvCA_Y,
						uvAB_X, uvAB_Y,
						color);
				}
				else if (bSide != aSide && bSide != cSide)
				{
					float abX, abY, bcX, bcY, uvAB_X, uvAB_Y, uvBC_X, uvBC_Y;
					GetIntersectionLineAndLineStrip(
						x1, y1,
						x2, y2,
						a.x, a.y,
						b.x, b.y,
						uvA_X, uvA_Y,
						uvB_X, uvB_Y,
						out abX, out abY,
						out uvAB_X, out uvAB_Y);
					GetIntersectionLineAndLineStrip(
						x1, y1,
						x2, y2,
						b.x, b.y,
						c.x, c.y,
						uvB_X, uvB_Y,
						uvC_X, uvC_Y,
						out bcX, out bcY,
						out uvBC_X, out uvBC_Y);
					var triangleResult = bSide ? _resultsA : _resultsB;
					var rectangleResult = bSide ? _resultsB : _resultsA;
					triangleResult.AddTriangle(
						b.x, b.y,
						bcX, bcY,
						abX, abY,
						uvB_X, uvB_Y,
						uvBC_X, uvBC_Y,
						uvAB_X, uvAB_Y,
						color);
					rectangleResult.AddRectangle(
						c.x, c.y,
						a.x, a.y,
						abX, abY,
						bcX, bcY,
						uvC_X, uvC_Y,
						uvA_X, uvA_Y,
						uvAB_X, uvAB_Y,
						uvBC_X, uvBC_Y,
						color);
				}
				else if (cSide != aSide && cSide != bSide)
				{
					float bcX, bcY, caX, caY, uvBC_X, uvBC_Y, uvCA_X, uvCA_Y;
					GetIntersectionLineAndLineStrip(
						x1, y1,
						x2, y2,
						b.x, b.y,
						c.x, c.y,
						uvB_X, uvB_Y,
						uvC_X, uvC_Y,
						out bcX, out bcY,
						out uvBC_X, out uvBC_Y);
					GetIntersectionLineAndLineStrip(
						x1, y1,
						x2, y2,
						c.x, c.y,
						a.x, a.y,
						uvC_X, uvC_Y,
						uvA_X, uvA_Y,
						out caX, out caY,
						out uvCA_X, out uvCA_Y);
					var triangleResult = cSide ? _resultsA : _resultsB;
					var rectangleResult = cSide ? _resultsB : _resultsA;
					triangleResult.AddTriangle(
						c.x, c.y,
						caX, caY,
						bcX, bcY,
						uvC_X, uvC_Y,
						uvCA_X, uvCA_Y,
						uvBC_X, uvBC_Y,
						color);
					rectangleResult.AddRectangle(
						a.x, a.y,
						b.x, b.y,
						bcX, bcY,
						caX, caY,
						uvA_X, uvA_Y,
						uvB_X, uvB_Y,
						uvBC_X, uvBC_Y,
						uvCA_X, uvCA_Y,
						color);
				}
			}
		}

		private static void GetIntersectionLineAndLineStrip(
			float x1, float y1, // Line Point
			float x2, float y2, // Line Point
			float x3, float y3, // Line Strip Point
			float x4, float y4, // Line Strip Point
			float uv3_X, float uv3_Y,
			float uv4_X, float uv4_Y,
			out float x, out float y,
			out float uvX, out float uvY)
		{
			float s1 = (x2 - x1) * (y3 - y1) - (y2 - y1) * (x3 - x1);
			float s2 = (x2 - x1) * (y1 - y4) - (y2 - y1) * (x1 - x4);

			float c = s1 / (s1 + s2);

			x = x3 + (x4 - x3) * c;
			y = y3 + (y4 - y3) * c;

			uvX = uv3_X + (uv4_X - uv3_X) * c;
			uvY = uv3_Y + (uv4_Y - uv3_Y) * c;
		}

		private static bool IsClockWise(
			float x1, float y1,
			float x2, float y2,
			float x3, float y3)
		{
			return (x2 - x1) * (y3 - y2) - (y2 - y1) * (x3 - x2) > 0;
		}
	}
}

```

感想
頂点カラーの線形補間はやっていないです。
コードフォーマットのせいで縦に伸びていますが、
やっていることはそんなに多くないです。


# 4. 四角形の分割
3.で紹介したコードで四角形を分割してみましょう。
2DのMeshを直線で分割できていますね！

画像説明：四角形ポリゴンを直線で分割した様子
![cut_rectangle.gif](https://qiita-image-store.s3.amazonaws.com/0/153010/2121248e-752f-5e08-3b8b-d27ed4d01a18.gif)

画像説明：四角形ポリゴンを直線で分割した様子　
青線：WireFrame
![cut_rectangle_wire.gif](https://qiita-image-store.s3.amazonaws.com/0/153010/378fa4eb-b787-d40f-e01f-5a1bd10f45a0.gif)

そうだ、魚を切ろう！
魚のフォントテクスチャをポリゴンに貼りつけて、分割してみます。
3.で実装したプログラムは、uvの分割も実装済みです。

![cut_fish.gif](https://qiita-image-store.s3.amazonaws.com/0/153010/16ba9711-d7ec-d274-5dd1-70afa653de52.gif)

魚切れた。

# 5. Splitter Crittersの研究
Splitter Crittersがもつ以下の特徴を実装しました。

- 3回まで連続して分割することができる
- 分割後の移動に制限がある
- 分割を取り消すことができる
- 分割時に画面が揺れる

![mohou.gif](https://qiita-image-store.s3.amazonaws.com/0/153010/a29a0720-d4d4-5a65-25cb-d35068c5bfa7.gif)

ゲームとして遊べるまで研究したかったけど、
時間がなかったのでここまで。

# 6. 発展
今回は直線で、Meshを分割していますが、
曲線で分割できるようにしたら面白そうだったり、
-> AssetStoreにありました。[「Smart Slicer 2D」](https://assetstore.unity.com/packages/tools/physics/smart-slicer-2d-109353)

重なっている部分を切り取るようなゲームにしたり、
-> [「いっしょにチョキッと スニッパーズ プラス 紹介映像」](https://www.youtube.com/watch?v=ZrQZ3sx29L8)

切るという遊びは、まだまだ面白いものが作れそうな気がします。

以上でこの記事は終わりです。
またどこかで会いましょう。

# 7. 最近書いた記事
[【Unity】Ear Clipping Triangulation](https://qiita.com/fujii-kotaro/items/a411f2a45627ed2f156e)