ChaikinのコーナーカットアルゴリズムでPolygonの角を丸くする【OpenSiv3D】

概要

OpenSiv3Dを使って2Dグラフィックスを扱う際、ポリゴンの角を滑らかにしたいケースがあります。例えば、より有機的な形状を生成したいときや、物理シミュレーション後の解像度が低いポリゴンを滑らかにしたいときなどです。2DSplineを使う方法もありますが、コストがかかる上、曲率が急激に変わるなど望ましくない結果になることがあります。このような場合に、Chaikin's corner cutting algorithmが有効な代替手段となります。

Chaikin's corner cutting algorithmとは

Chaikinのアルゴリズムは、ポリゴンの各頂点を操作して角を滑らかに切り取ることで、より滑らかな曲線を生成する手法です。このアルゴリズムは、与えられた頂点のペアに対して新しい頂点を生成し、そのプロセスを繰り返すことにより、元の形状から滑らかな形状へと変化させます。

引用：https://sighack.com/post/chaikin-curves#:~:text=In%201974%2C%20George%20Chaikin%20presented%20one%20of,from%20a%20given%20set%20of%20control%20points

OpenSiv3Dでの実装

以下にOpenSiv3DでのChaikin's corner cutting algorithmの実装例を示します。

# include <Siv3D.hpp>

Array<Vec2> ChaikinSmooth(const Array<Vec2>& inputVertices, int iterations = 2)
{
	// Error handling for insufficient vertex count
	if (inputVertices.size() < 3)
	{
		throw std::invalid_argument("Input vertices must form a polygon (at least 3 vertices).");
	}

	// Error handling for invalid iteration count
	if (iterations <= 0)
	{
		throw std::invalid_argument("Iterations must be a positive integer.");
	}

	Array<Vec2> currentVertices = inputVertices;

	for (int k = 0; k < iterations; ++k)
	{
		Array<Vec2> newVertices;

		const size_t vertexCount = currentVertices.size();
		for (size_t i = 0; i < vertexCount; ++i)
		{
			// Get current vertex and next vertex (with wrap-around)
			const Vec2& p0 = currentVertices[i];
			const Vec2& p1 = currentVertices[(i + 1) % vertexCount];

			// Compute new vertices
			const Vec2 q = p0 * 0.75 + p1 * 0.25;
			const Vec2 r = p0 * 0.25 + p1 * 0.75;

			// Add new vertices to the list
			newVertices << q << r;
		}

		// Update current vertices for next iteration (if any)
		currentVertices = newVertices;
	}

	return currentVertices;
}

Polygon ChaikinSmoothPolygon(const Polygon& inputPolygon, int iterations = 2)
{
	const Array<Vec2> smoothedVertices = ChaikinSmooth(inputPolygon.outer(), iterations);
	return Polygon(smoothedVertices);
}


void Main()
{
	constexpr Size size{ 800, 600 };
	constexpr Rect rect{ size };
	Subdivision2D subdiv{ rect };

	for (const PoissonDisk2D pd{ size, 40 };
		const auto & point : pd.getPoints())
	{
		if (rect.contains(point))
		{
			subdiv.addPoint(point);
		}
	}

	const Array<Polygon> facetPolygons = subdiv
		.calculateVoronoiFacets()
		.map([rect](const VoronoiFacet& f)
	{
		return ChaikinSmoothPolygon(Geometry2D::And(Polygon{ f.points }, rect).front(), 2);
	});

	while (System::Update())
	{
		for (auto [i, facetPolygon] : Indexed(facetPolygons))
		{
			facetPolygon
				.draw(HSV{ i * 25.0, 0.65, 0.8 })
				.drawFrame(2, ColorF{ 0.25 });
		}
	}
}

上記のコードで定義されるChaikinSmooth関数は、与えられた頂点の配列を滑らかにするために使用されます。iterationsパラメータは、アルゴリズムが繰り返される回数を指定します。

ChaikinSmoothPolygon関数は、Polygonクラスのオブジェクトを受け取り、平滑化されたポリゴンを生成します。

Chaikinのアルゴリズムの理論的な解説

Chaikinのアルゴリズムは、グラフィックスにおいてポリラインやポリゴンの角を滑らかにする手法の一つです。具体的には、多角形の各辺に沿って新たな頂点を計算し、元の頂点を部分的に切り取りながら新しい滑らかな辺を形成します。

アルゴリズムの基本ステップ

元の多角形の各辺に対して、次のステップを行います：

1. 各辺の始点$P_0$と終点$P_1$を選びます。
2. 始点$P_0$に近い側で新しい頂点Qを生成します。計算式は $ Q = 0.75 \cdot P_0 + 0.25 \cdot P_1 $ です。
3. 終点$P_1$に近い側で新しい頂点Rを生成します。計算式は $R = 0.25 \cdot P_0 + 0.75 \cdot P_1 $ です。
4. 元の辺は、新しい辺〈$P_0$, $Q$〉と〈$R$, $P_1$〉に置き換えられます。

アルゴリズムの特徴

• イテレーションの進行による滑らかさ： 各イテレーションでポリゴンはより滑らかになります。ただし、多くのイテレーションを行うと、元の形状から離れる可能性があります。
• 計算コスト： このアルゴリズムは比較的シンプルで計算コストが低いため、リアルタイムアプリケーションに適しています。
• シャープな特徴の維持： 繰り返し回数が少ない場合、元のポリゴンの特徴をある程度保ちつつ滑らかにすることができます。

数学的背景

Chaikinのアルゴリズムは、B-スプライン曲線の概念に部分的に基づいています。このアルゴリズムは、元の頂点間に補間することによって、曲線の近似を行います。イテレーションが進むごとに、ポリゴンの辺は元の辺を補間する曲線の制御点として機能するようになり、結果として全体の曲線は滑らかになります。

応用例

• 物理シミュレーションで生成されたローポリゴンの平滑化
• ソフトボディ、波、ロープなどの表現における滑らかさの向上
• ボロノイ図のセルの境界を滑らかにするために使用

結論

Chaikinのコーナーカットアルゴリズムは、OpenSiv3Dで2Dグラフィックスを扱う際の有力なツールです。これにより、高いコストを要するSplineを使用することなく、滑らかで有機的な表現が可能になります。上記の実装を参考に、さまざまなアプリケーションでのグラフィックスの質を向上させることができるでしょう。

https://search.r-project.org/CRAN/refmans/smoothr/html/smooth_chaikin.html
https://sighack.com/post/chaikin-curves#:~:text=In%201974%2C%20George%20Chaikin%20presented%20one%20of,from%20a%20given%20set%20of%20control%20points.
https://people.ece.ubc.ca/~saifz/eece478/course/chaikin.pdf#:~:text=The%20Method:%20%E2%80%A2%20Chaikin%20uses%20fixed%20ratio,the%20same.)%20Example:%20Given%20a%20control%20polygon.