「Splitter Critters」というゲームが面白くて、どうやって作るか興味を持ったので、
2DのMeshを直線で分割する記事を書きました。
1. 必要な知識の紹介
2DのMesh分割を実装するのに必要な３つの数学的な知識を先に紹介します。
1.1 直線による平面分割
直線による平面分割は外積の符号を利用します。
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 => ドットの順で見たときに、
時計回りなら赤色、反時計回りなら青色にドットを表示しています
1.2 直線と直線の交点
直線ABと直線CDの交点を求めます。
三角形ACDと三角形BCDの面積を外積で求めて、面積の比を計算します。（面積は符号付き）
面積の比は、点Aから交点までの長さ、点Bから交点までの長さに比に一致するので、交点の座標が求まります。
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直線の交点を面積比で求めています
参考：４点からなる交点の求め方
http://imagingsolution.blog107.fc2.com/blog-entry-137.html
1.3 線分と直線の交点
直線ABと線分CDの交点を求めます。
直線ABと直線CDの交点は1.2で求めるとができるので、直線ABと線分CDが交差するかだけ調べれば十分です。
ABCが時計回りか、ABDが時計回りかを調べて、向きが異なれば交差します。
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は交点をもつ
2. 三角形の分割
Unityの場合はMeshは三角形で構成されているので、三角形の分割ができればMesh分割が実装可能になります。
まず三角形ABCを直線PQで切断したときのケースを考えます。全部で5ケースです。
- 直線PQと三角形ABCが交わらない（時計回り側に存在：赤色）
- 直線PQと三角形ABCが交わらない（反時計回り側に存在：緑色）
- 直線PQが線分AB、線分BCと交わる
- 直線PQが線分AB、線分CAと交わる
- 直線PQが線分BC、線分CAと交わる
- 直線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つに分割される
3. 実装
ここまでで方針が決まりました。あとは実装しましょう。
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を直線で分割できていますね！
画像説明：四角形ポリゴンを直線で分割した様子
画像説明：四角形ポリゴンを直線で分割した様子
青線：WireFrame
そうだ、魚を切ろう！
魚のフォントテクスチャをポリゴンに貼りつけて、分割してみます。
3.で実装したプログラムは、uvの分割も実装済みです。
魚切れた。
5. Splitter Crittersの研究
Splitter Crittersがもつ以下の特徴を実装しました。
- 3回まで連続して分割することができる
- 分割後の移動に制限がある
- 分割を取り消すことができる
- 分割時に画面が揺れる
ゲームとして遊べるまで研究したかったけど、
時間がなかったのでここまで。
6. 発展
今回は直線で、Meshを分割していますが、
曲線で分割できるようにしたら面白そうだったり、
-> AssetStoreにありました。「Smart Slicer 2D」
重なっている部分を切り取るようなゲームにしたり、
-> 「いっしょにチョキッと スニッパーズ プラス 紹介映像」
切るという遊びは、まだまだ面白いものが作れそうな気がします。
以上でこの記事は終わりです。
またどこかで会いましょう。