サイラス・ベック・アルゴリズム - 版の履歴

2022年10月26日 (水) 06:53にAdministratorによる

2022-10-26T06:53:10Z

← 古い版		2022年10月26日 (水) 06:53時点における版
119行目:		119行目:
	[[category: 2DCG]]		[[category: 2DCG]]
	[[category: 3DCG]]		[[category: 3DCG]]
	[[category: ~~コンピューターグラフィックス~~]]		[[category: コンピューター・グラフィックス]]

Administrator: /* 概要 */

2020-05-07T01:56:52Z

概要

← 古い版		2020年5月7日 (木) 01:56時点における版
8行目:		8行目:
	またコーエン・サザーランド・アルゴリズムは長方形のみなのに対して、サイラス・ベック・アルゴリズムは多角形にも適用できる。		またコーエン・サザーランド・アルゴリズムは長方形のみなのに対して、サイラス・ベック・アルゴリズムは多角形にも適用できる。

	米空軍が考案しただけあって[[シューティングゲーム]]の[[実装]]が捗る。		米空軍が考案しただけあって[[ベクターグラフィックス]]で表現された[[シューティングゲーム]]の[[実装]]が捗る。

	== 詳細 ==		== 詳細 ==

2020年5月7日 (木) 01:56にAdministratorによる

2020-05-07T01:56:04Z

← 古い版		2020年5月7日 (木) 01:56時点における版
1行目:		1行目:
	'''サイラス・ベック・アルゴリズム'''（[[英語]]：Cyrus Beck algorithm）とは、[[コンピューターグラフィックス]]におけるラインクリッピングの[[アルゴリズム]]~~である。~~		'''サイラス・ベック・アルゴリズム'''（[[英語]]：Cyrus Beck algorithm）とは、[[コンピューターグラフィックス]]におけるラインクリッピングの[[アルゴリズム]]（直線が多角形の内側にあるかを判断するアルゴリズム）である。

	== 概要 ==		== 概要 ==
	1978年に米国空軍研究所のMike CyrusとJay Beckが発表した[[アルゴリズム]]である。		1978年に米国空軍研究所のMike CyrusとJay Beckが発表した[[アルゴリズム]]である。

2020年4月28日 (火) 06:34にAdministratorによる

2020-04-28T06:34:08Z

← 古い版		2020年4月28日 (火) 06:34時点における版
1行目:		1行目:
	'''サイラス・ベック・アルゴリズム'''（[[英語]]：Cyrus Beck algorithm）とは、[[コンピューターグラフィックス]]におけるラインクリッピングの[[アルゴリズム]]である。		'''サイラス・ベック・アルゴリズム'''（[[英語]]：Cyrus Beck algorithm）とは、[[コンピューターグラフィックス]]におけるラインクリッピングの[[アルゴリズム]]である。

			== 概要 ==
			1978年に米国空軍研究所のMike CyrusとJay Beckが発表した[[アルゴリズム]]である。
			Generalized two- and three-dimensional clipping (Computers & Graphics, 1978: 23–28.)
			https://www.sciencedirect.com/science/article/pii/0097849378900213

	コーエン・サザーランド・アルゴリズムより効率的になるよう設計されている。		コーエン・サザーランド・アルゴリズムより効率的になるよう設計されている。
	またコーエン・サザーランド・アルゴリズムは長方形のみなのに対して、サイラス・ベック・アルゴリズムは多角形にも適用できる。		またコーエン・サザーランド・アルゴリズムは長方形のみなのに対して、サイラス・ベック・アルゴリズムは多角形にも適用できる。

			米空軍が考案しただけあって[[シューティングゲーム]]の[[実装]]が捗る。

	== 詳細 ==		== 詳細 ==

2020年4月28日 (火) 06:23にAdministratorによる

2020-04-28T06:23:04Z

← 古い版		2020年4月28日 (火) 06:23時点における版
113行目:		113行目:
	[[category: 2DCG]]		[[category: 2DCG]]
	[[category: 3DCG]]		[[category: 3DCG]]
			[[category: コンピューターグラフィックス]]

2020年4月28日 (火) 06:22にAdministratorによる

2020-04-28T06:22:49Z

← 古い版		2020年4月28日 (火) 06:22時点における版
1行目:		1行目:
	~~サイラス・ベック・アルゴリズム（英語：Cyrus~~ Beck ~~algorithm）とは、コンピューターグラフィックスにおけるラインクリッピングのアルゴリズムである。~~		'''サイラス・ベック・アルゴリズム'''（[[英語]]：Cyrus Beck algorithm）とは、[[コンピューターグラフィックス]]におけるラインクリッピングの[[アルゴリズム]]である。

	コーエン・サザーランド・アルゴリズムより効率的になるよう設計されている。		コーエン・サザーランド・アルゴリズムより効率的になるよう設計されている。
13行目:		13行目:
	:<math> 0 \leq t \leq 1 </math>.		:<math> 0 \leq t \leq 1 </math>.

	~~クリッピング領域との交点を見つけるために、領域の辺の法線（多角形を構成する直線の法線）と直線の内積を計算する。~~'''p'''<sub>''E''</sub> ~~は多角形の頂点。~~ '''n'''~~は法線。~~		クリッピング領域との交点を見つけるために、領域の辺の[[法線]]（多角形を構成する直線の法線）と直線の[[内積]]を計算する。'''p'''<sub>''E''</sub> は多角形の[[頂点]]。 '''n'''は[[法線]]。
	:<math>\mathbf n \cdot (\mathbf p(t) - \mathbf p_E)</math>		:<math>\mathbf n \cdot (\mathbf p(t) - \mathbf p_E)</math>

107行目:		107行目:
	* [[Cohen–Sutherland algorithm]]		* [[Cohen–Sutherland algorithm]]
	* [[Liang–Barsky algorithm]]		* [[Liang–Barsky algorithm]]
			* [[Cyrus Beck algorithm]]
	* [[Nicholl–Lee–Nicholl algorithm]]		* [[Nicholl–Lee–Nicholl algorithm]]
	* [[Fast clipping]]		* [[Fast clipping]]

Administrator: ページの作成:「サイラス・ベック・アルゴリズム（英語：Cyrus Beck algorithm）とは、コンピューターグラフィックスにおけるラインクリッピング…」

2020-04-28T06:21:35Z

ページの作成:「サイラス・ベック・アルゴリズム（英語：Cyrus Beck algorithm）とは、コンピューターグラフィックスにおけるラインクリッピング…」

新規ページ

サイラス・ベック・アルゴリズム（英語：Cyrus Beck algorithm）とは、コンピューターグラフィックスにおけるラインクリッピングのアルゴリズムである。

コーエン・サザーランド・アルゴリズムより効率的になるよう設計されている。
またコーエン・サザーランド・アルゴリズムは長方形のみなのに対して、サイラス・ベック・アルゴリズムは多角形にも適用できる。

== 詳細 ==
直線のパラメトリック方程式
:<math>
\begin{align}
\mathbf p(t) &= t \mathbf p_1 + (1 - t) \mathbf p_0\\
\end{align}
</math>
:<math> 0 \leq t \leq 1 </math>.

クリッピング領域との交点を見つけるために、領域の辺の法線（多角形を構成する直線の法線）と直線の内積を計算する。'''p'''<sub>''E''</sub> は多角形の頂点。 '''n'''は法線。
:<math>\mathbf n \cdot (\mathbf p(t) - \mathbf p_E)</math>

この値が、
* if < 0, 直線は内側になる。
* if = 0, 直線は平行である。
* if > 0, 直線は内側にない。

== 2Dでの実装例 ==
verticesからなる多角形と、point0とpoint1からなる直線に対して、
サイラスベックアルゴリズムを適用し、直線が多角形外であればnullを、多角形内であれば接点となる2点を返す。

<source lang="csharp">
public static Vector2[] CyrusBeck(Vector2[] vertices, Vector2 point0, Vector2 point1)
{
// 引数チェック
if (vertices == null || vertices.Length < 3)
{
throw new ArgumentException(nameof(vertices));
}

// 頂点数
var vcount = vertices.Length;

// 法線を計算
var normal = new Vector2[vcount];

for (int i = 0; i < vcount; i++)
{
normal[i].X = vertices[i].Y - vertices[(i + 1) % vcount].Y;
normal[i].Y = vertices[(i + 1) % vcount].X - vertices[i].X;
}

// P1-P0を計算
var p1p0 = point1 - point0;

// P0-PEiを計算
var p0pei = new Vector2[vcount];

for (int i = 0; i < vcount; i++)
{
p0pei[i] = vertices[i] - point0;
}

// 分子と分母を計算
var numerator = new float[vcount];
var denominator = new float[vcount];

for (int i = 0; i < vcount; i++)
{
numerator[i] = Vector2.Dot(normal[i], p0pei[i]);
denominator[i] = Vector2.Dot(normal[i], p1p0);
}

// enterとleavingを計算
var t = new float[vcount];
var tE = new List<float>();
var tL = new List<float>();

for (int i = 0; i < vcount; i++)
{
t[i] = numerator[i] / denominator[i];

if (0 < denominator[i])
tE.Add(t[i]);
else
tL.Add(t[i]);
}
tE.Add(0);
tL.Add(1);

var temp = new float[2];
temp[0] = tE.Max();
temp[1] = tL.Min();

// 範囲外（外側）にあると思われる
if (temp[1] < temp[0])
{
return null;
}

// 結果
var result = new Vector2[2];
result[0].X = point0.X + p1p0.X * temp[0];
result[0].Y = point0.Y + p1p0.Y * temp[0];
result[1].X = point0.X + p1p0.X * temp[1];
result[1].Y = point0.Y + p1p0.Y * temp[1];
return result;
}
</source>

== 関連項目 ==
* [[Cohen–Sutherland algorithm]]
* [[Liang–Barsky algorithm]]
* [[Nicholl–Lee–Nicholl algorithm]]
* [[Fast clipping]]

[[category: 2DCG]]
[[category: 3DCG]]