移動する線が移動する点と交差しているかどうかを正確に判断する｜Twisted Oak Studios Blog

11月 3, 2021

Determining exactly if/when/where a moving line intersected a moving point
Destination
直感
Model
解
Generalizing
まとめ
Discuss on Reddit
アーカイブ

Determining exactly if/when/where a moving line intersected a moving point

posted by Craig Gidney on February 5, 2013

ライブラリを公開する際にはサンプルプロジェクトを含めるように心がけています。 Perishable Collection の場合、サンプルプロジェクトは実際には、マウスポインターで線を切ることに基づいたシンプルなゲームでした。

サンプルを書く一環として、マウスポインターが線を横切ったかどうか、いつ、どこで横切ったかを判断するという問題を解決しなければなりませんでした（またはその逆の場合もあります）。私がいつも参照するジオメトリアルゴリズムには解決策が含まれていなかったので、自分で解決策を開発しました。この解決策は、少量のソースコード (コメントとサポートするメソッド/型を含めて約 150 行) で実装されており、github で入手できます。

Destination

“Did the mouse pointer cut the moving line?” は、最初は比較的単純な制約で始まり、解くうちにかなり複雑に見えるが、最後の数ステップでほぼすべてが相殺または結合されて、とんでもなく単純なものに行きつく、魔法の数学問題の 1つであると判明した。 (そして、解答を見直すために戻ってみると、ずっと簡単な道があったことがわかります。)

参考とモチベーションのために、説明する前に、実装の肉をここに投じるつもりです。下線は github の対応するコードへのリンクです。

public static IEnumerable<Sweep> WhenLineSweepsPoint(LineSegment pathOfLineStartPoint, LineSegment pathOfLineEndPoint, Point point) {var a = point - pathOfLineStartPoint.Start;var b = -pathOfLineStartPoint.Delta;var c = pathOfLineEndPoint.Start - pathOfLineStartPoint.Start;var d = pathOfLineEndPoint.Delta - pathOfLineStartPoint.Delta;return from t in QuadraticRoots(b.Cross(d), a.Cross(d) + b.Cross(c), a.Cross(c)) where t >= 0 && t <= 1 let start = pathOfLineStartPoint.LerpAcross(t) let end = pathOfLineEndPoint.LerpAcross(t) let s = point.LerpProjectOnto(new LineSegment(start, end)) where s >= 0 && s <= 1 orderby t select new Sweep(timeProportion: t, acrossProportion: s);}

あなたはどうかわかりませんが、上記のコードで問題が解決することに私は驚きました。あまりにも素直で、しかも関係なさそうです。コーナーケースのようなものがあってはならないのでしょうか？さらに、この単純なクロスプロダクトはどこから来たのでしょうか？ 2次多項式に入力することで、どのような効果があるのでしょうか？ 8142>

直感

この問題を直感的に理解するために、遭遇する可能性のあるいくつかのケースを検討することから始めましょう。

単純：両端が同じ速度で、線の法線ベクトルに沿って動く。
横：線がそれ自身の長さに沿って動いている縮退したケース。
Dive: 一方の端点が斜めに動き、他方は垂直に動く (真ん中を「潜る」)。

Various sweep cases

Note that a line can sweep a point 0, 1, or 2 times as its endpoints move at a constant rate from one position to another.これは、線の端点がある位置から別の位置に一定速度で移動し、0、1、または2回掃引できることに注意。 Raise’ の場合は、都合よく3つの可能性をすべて含んでいます。

もう一つの有用な発見は、線が一定の速度で動く、あるいは静止しているなど、いくつかのケースは最高次の係数がゼロである退化した二次方程式に対応することです（すなわちまたはさえあるのです）。

Model

からまでの線分が点を含むためには、二つの条件を満たさなければならない。まず、からまでの「オフセット」ベクトルはからまでの「デルタ」ベクトルと平行でなければならない。これを数学的に表すには、それらのクロスプロダクトがゼロであることを要求すればよい。 $(c-p) \times (q-p) = 0$ となる。これはが線分を両方向に伸ばした線上にあること(あるいは退化した一点鎖線であること)を保証している。次に、オフセットベクトルのデルタベクトルへのスカラー投影が正しい範囲にあること。 $0 \leq s = \frac{(c-p) \cdot (q-p)}{(q-p)^2} となります。 \⑭1$ 。

時間がからになるとき、現在の線分がを含む時間があるときだけ、線分は点を横切ることになります。線分の端点は一定の速度で移動しているので、それらがたどる道も線分である。からへ移動する端点は、時刻に線形補間した点 $lerp(p_0, p_1, t) = p_0 + (p_1 - p_0) \cdot t$ に位置することになる。なお、をと略すのは、スペースを節約するためである。移動する点を「線分が点を含む」式に差し込むと、 $0 \leq t 1$ と $(c - (p_0 + p_d \cdot t)) を満たす <img src=$ を求めなければならないことがわかります。 \⑭（(q_0 + q_d ⑭cdot t)-(p_0 + p_d ⑭cdot t)) = 0″ height=”18″ width=”394″ style=”vertical-align: -4px” class=”alignleft”> and 0 \leq s = \frac{(c-(p_0 + p_d \cdot t))) \Ъ((q_0 + q_d \cdot t)-(p_0 + p_d \cdot t))}{((q_0 + q_d \cdot t)-(p_0 + p_d \cdot t))^2} ⑭(q_0＋q_d・)・(p_0＋p_d・))・(q_0＋q_d・・) \ʕ-̫͡-ʔ 「ある交差積が0にならなければならない」というのは、問題の枠組みとして唯一の方法ではないことに注意してください。また、の範囲にあるとで、両端点をで横切り、両端点間をで横切った結果がとなるものを探すと考えることも理にかなっているのです。数学的には、ということになる。変数とは「いつ」「どこで」交差点が発生するかにおおよそ対応している。ただし、この形だとが最初は孤立していないので解きにくいので、（最初と違って…）十字積のハメコミを使います。

解

十字積とドット積には、を孤立させやすくするとても良い性質があります。まず、足し算を分配することで、 $u \times (v + w) = u \times v + u \times w$ 、 $u \cdot (v + w) = u \cdot v + u \cdot w$ ということになります。次に、スケーリングはどちらの積の前でも後でも可能で、 $(c \cdot u) \times v = c \cdot (u \times v)$ と $(c \cdot u) \cdot v = c \cdot (u \cdot v)$ ( は実数)と言う事になります。最後に、内積は可換なので、 $u \cdot v = v \cdot u$ ですが、外積は反可換なので、 $u \times v = -v \times u$ となります。

この積の知識を適用し、特定の部分式を個々の変数として扱うことを後知恵で知ることで、cross-product-is-zero 式を 2 次方程式に変換できます:

$◇begin{align*} 0 =(c - (p_0 + p_d \cdot t)) \times ((q_0 + q_d \cdot t)-(p_0 + p_d \cdot t)) \= ((c - p_0) - p_d \cdot t) \times ((q_0 - p_0) - (q_d - p_d) \cdot t) \= (a + b \cdot t) \times (c + d \cdot t) \;↘;↘;;;;。\;where;\; a = c - p_0 \;\;where;\; b = -p_d \;where;petition; c = q_0 - p_0 \;where;petition; c = q_0 - p_0 \;where;where;petition;petition; c = q_0 - p_0 \;Where;where;where;petition; b = -p_d d = -(q_d -) p_d) \= a \times c + a \times d \cdot t + b \times c \cdot t + b \times d \cdot t \= t^2 \cdot (b \times d) + t \cdot (a) \times d + b \times c) + (a \times c) \end{align*}$

(this is hilarly simpled than the route I first time took.).)

ああ、これでコード解の形がどこから来たのかがはっきりしましたね。私たちはゼロに等しい外積（直線から点へのベクトルは直線に平行であると主張する）から始めて、の異なる累乗を含む項の和を分離するために積を分割する必要がありました。そうすると、当然、クロス積を含む係数を持つ2次方程式が求まります。 8142>

これは非常に「頑丈な」方程式であることに注意してください。なぜなら、途中でベクトルやスカラーについて何も仮定していないからです。たとえば、変数で割る（または暗黙のうちに打ち消す）ことはしないので、ゼロ以外の条件が潜んでいることはありません。

単純化した方程式で、の可能な値を決定することは、「二次多項式の解決」の標準作業だけです。

の可能な値がわかったら、先ほどのplug-t-int-line-segment-point-containmentの公式を使って、衝突が起こった場所を正確に見つけることができます。 $s = \frac{(c-(p_0 + p_d \cdot t)) \cdot ((q_0 + q_d \cdot t)-(p_0 + p_d \cdot t))}{((q_0 + q_d \cdot t)-(p_0 + p_d \cdot t))^2}$ となります。この式はを時間の直線に投影したもので、を戻すために直線の始点から終点まででレープする割合を返しているので、

public static double LerpProjectOnto(this Point point, LineSegment line) { var b = point - line.Start; var d = line.Delta; return (b * d) / (d * d); // when d == 0, result is +-infinity or NaN}

最後に、とが得られたら、それらがの範囲に入っているかどうかをチェックする必要があります。もしが範囲外であれば、現在の時間ステップでは衝突は起こりません。が範囲外であれば、衝突は延長線上で発生しますが、線分では発生しません。とは衝突がいつ/どこで起こったかを見つけるためにどれだけ反復するかを記述しているので、呼び出し元に返す有用な情報でもあります。

Generalizing

まだ言及していない重要な詳細は、動いているマウスポインタは明らかに点に対応しないことです。幸いなことに、線分の動きから差し引くことで、最後の時間ステップでのマウスポインタの動き (線形であると仮定) をキャンセルすることができます。これは系を解けるものに減らすだけでなく、結果として得られるとの値は逆変換のようなものをせずに有効です。使用方法は次のようになります:

// time goes from t0 to t1// line segment endpoint 1 moves from p0 to p1// line segment endpoint 2 moves from q0 to q1// point moves from c0 to c1var results = from hit in WhenLineSweepsPoint(new LineSegment(p0 - c0, p1 - c1), new LineSegment(q0 - c0, q1 - c1), new Point(0, 0)) let hitPos = new LineSegment(c0, c1).LerpAcross(hit.TimeProportion) let hitTime = t0 + (t1-t0)*hit.TimeProportion select new { p = hitPos, t = hitTime }foreach (var result in results) { System.Diagnostics.Debug.WriteLine(string.Format("Hit at p={0}, t={1}", result.p, result.t);}

複雑になる可能性があるのは、長さのない（両端が等しい）縮退した線分です。このコードはこのケースを明示的に処理しませんが、あたかも実際に点である線を切ることは不可能であるかのように振る舞います。の計算が到達すると、ゼロで割ります。その結果 (-infinity、+infinity、または NaN) は範囲チェックに失敗します。

私がカバーしていないもうひとつの側面は「カット角度」です。さまざまなケースを示すアニメーションでは、赤い切り口は 2 つの端点の速度の間を乗算することで方向付けられます (結果の速度が 0 の場合は、ランダムな角度が選択されます)。しかし、「カット角度は点の速度」というような別のアプローチも使ったことがある。基本的には、「カット角」の本当の意味を理解しようとするのではなく、良さそうなもの、自然に感じられるものを何でも使うということです。

まとめ

この問題は、線形代数からの知識を適用するとすぐに些細なことになります。線形代数（と多項式）は特に幾何学ではどこでも出てくるので、あまり驚くことではないと思います。

この問題の自然な一般化は、厚さを含めることです。スクリーン上に描かれた線は、結局のところ、無限に薄いわけではありません。太さを持つことは、異なる時間ステップ中に異なる方向で丸められる浮動小数点エラーの影響を減らす良い方法でもあります。また、ゲームオブジェクトは自由落下することが多いので、放物線のパスを扱えるようにするのも有効な変更点です。一方、「太い線」を等速のタイムステップでポリゴンとして扱うのは、おそらく簡単だと思います。

–

Discuss on Reddit

–

Twisted Oak Studios ではハイテクインタラクティブプロジェクトに関するコンサルティングと開発を担当しています。私たちのポートフォリオをご覧ください。また、本当に素晴らしいエンジニアがお手伝いするべきだと思うことがあれば、ぜひお声がけください。

Savage Rose

移動する線が移動する点と交差しているかどうかを正確に判断する｜Twisted Oak Studios Blog

Determining exactly if/when/where a moving line intersected a moving point

Destination

直感

Model

解

Generalizing

まとめ

Discuss on Reddit

アーカイブ

コメントを残すコメントをキャンセル

Determining exactly if/when/where a moving line intersected a moving point

Destination

直感

Model

解

Generalizing

まとめ

Discuss on Reddit

アーカイブ

コメントを残す コメントをキャンセル

コメントを残すコメントをキャンセル