2026
2025
2024
2023
2022
2021
2020
2019
2018
2017
2016
2015
2014
2013
2006年04月の記事
全31件 (31件中 1-31件目)
1
-
Real-Time Collision Detection 5.5.6 Intersecting Moving Sphere against Triangle (and Polygon)
Real-Time Collision Detection という本を読んでいます。http://www.realtimecollisiondetection.net/5.5.6 Intersecting Moving Sphere against Triangle (and Polygon)三角形（およびポリゴン）に対する動いている球の交差について。球S(中心:C 半径:r)と定義しSの方向ベクトルをvとします。球の中心の運動が C(t)=C+tv (0≦t≦1)として与えられているとします。また三角形Tの法線をnとします。ここで紹介されている Nettle さんの手法では球を三角形ののる平面の裏側まで動かして交差時間と交差点を求め交差点が三角形の内部かどうかを調べているようです。概念的にはTをSでスゥイープして得られるTとSのミンコフスキー和を形成するボリュームと光線の判定ととらえればよいでしょうね。まあ動いているもののコリジョンって全部そんなものですが。衝突点を正確に求められれば正確な物理演算を施せるので便利なことが多いでしょうね。ということで今日はここまで。
2006年04月30日
コメント(0)
-
Real-Time Collision Detection 5.5.5 Intersecting Moving Sphere against Sphere
Real-Time Collision Detection という本を読んでいます。http://www.realtimecollisiondetection.net/5.5.5 Intersecting Moving Sphere against Sphere平面に対する動いている球の交差について。２つの球 S0 および S1 の半径が r0, r1 で与えられ運動ベクトルが v0 および v1 で与えられるとします。球の中心の運動は 0 ≦ t ≦ 1, P0(t) = C0 + tv0 および P1(t) = C1 + tv1 として記述できます。時間 t における球の中心間の距離を示すベクトル v は以下で与えられます。d(t) = ( C0 + tv0 ) - ( C1 + tv1 ) = ( C0 - C1 ) + t( v0 - v1 )球は最初の状態では接触していないと仮定すると d の長さが半径の和に等しいときに接触することになります。最適化のため両辺を平方すると d(t)・d(t) = (r0+r1)^2 となります。これを解くと t の２次方程式となります。したがって判別式で解の個数を求めることができて接触点も解の公式で求まります。後は開始時に接触していないかどうかきちんと確認すればよいと思います。ここまでのソースが本文にありますので後はそちら参照ということで。
2006年04月29日
コメント(0)
-
Real-Time Collision Detection 5.5.5 Intersecting Moving Sphere against Sphere
Real-Time Collision Detection という本を読んでいます。http://www.realtimecollisiondetection.net/5.5.5 Intersecting Moving Sphere against Sphere平面に対する動いている球の交差について。２つの球 S0 および S1 の半径が r0, r1 で与えられ運動ベクトルが v0 および v1 で与えられるとします。球の中心の運動は 0 ≦ t ≦ 1, P0(t) = C0 + tv0 および P1(t) = C1 + tv1 として記述できます。時間 t における球の中心間の距離を示すベクトル v は以下で与えられます。d(t) = ( C0 + tv0 ) - ( C1 + tv1 ) = ( C0 - C1 ) + t( v0 - v1 )球は最初の状態では接触していないと仮定すると d の長さが半径の和に等しいときに接触することになります。最適化のため両辺を平方すると d(t)・d(t) = (r0+r1)^2 となります。これを解くと t の２次方程式となります。したがって判別式で解の個数を求めることができて接触点も解の公式で求まります。後は開始時に接触していないかどうかきちんと確認すればよいと思います。ここまでのソースが本文にありますので後はそちら参照ということで。
2006年04月28日
コメント(0)
-
Real-Time Collision Detection 5.5.4 Intersecting Moving AABB against Plane
Real-Time Collision Detection という本を読んでいます。http://www.realtimecollisiondetection.net/5.5.4 Intersecting Moving AABB against Plane平面に対する動いているAABBの交差について。平面 π:n・X = d (n:単位ベクトル) によって記述されるとします。AABB Bが中心C、ローカル軸ベクトル u0 = ( 1 , 0, 0 ), u1 = ( 0, 1, 0 ), u2 = ( 0, 0, 1 ) および幅 e0, e1, e2 によって記述されるとします。そして v は B の方向ベクトルであり、ボックスの中心の運動を C(t) = C + tv ( 0 ≦ t ≦ 1 ) として与えられるとします。平面の法線 n を分離軸と考えます。Bの半径の軸 n に対する射影をまず求めます。AABBなので軸ベクトルは固定できますので r = e0l nx l + e1| ny | + e2| nz | と記述できます。前の節同様に平面をAABBに向けてRだけ変異させることにより平面は ( n・X ) = d + r となります。後は平面に最初に接触するAABB上の点は Q = C(t) - rn となり C(t) が接触点となります。ということであとは本文参照ください。なんだか図もソースもなくようわからん。
2006年04月27日
コメント(0)
-
Real-Time Collision Detection 5.5.3 Intersecting Moving Sphere against Plane
Real-Time Collision Detection という本を読んでいます。http://www.realtimecollisiondetection.net/5.5.3 Intersecting Moving Sphere against Plane平面に対する動いている球の交差について。平面 π:n・X=d (n:単位ベクトル) とし球Sが中心Cおよび半径rによって記述されているとします。そして v は S の方向ベクトルとし球の中心の運動は C(t) = C + tv (0≦t≦1)として与えられます。点Rの平面までの符号つき距離は (n・R) - d です。したがってまず最初に球が平面と重なるのは| (n・C) - d | ≦ r の場合になります。n・v ＞ 0 であれば平面の表側にあり球は平面から離れるように動きます。球が平面の裏側なら近づきますn・v ＜ 0 であれば逆のことがいえます。(n・C) - d の符号が示しているのは平面のどちら側に球があるかなのでもう少し簡潔にいえば(n・v )( n・C - d ) ＞ 0 の場合に球は平面から離れるようにして動いて(n・v )( n・C - d ) ＜ 0 の場合に球は平面に向かって動いています。n・v = 0 の場合は球は平面に平行に動いています。球が平面に向かって動いていると仮定した場合球と平面との間で最初に接触が起こる時間を見つけるには直接的な方法として平面を球の半径だけ球に向かって移動させ線分 S(t) = C + tv (0≦t≦1) との交差を扱う方法があります。ここまでの数式とソースが本文にあります。あとは交差点を求めるのではなく交差するかどうかだけなら最初の点と最後の点が平面の反対側にあるかどうかだけ調べれば良いですね。まずはこれで絞り込んだあとに交点を求めるのがよいでしょうね。
2006年04月26日
コメント(0)
-
Real-Time Collision Detection 5.5.2 Separating Axis Test for Moving Convex
Real-Time Collision Detection という本を読んでいます。http://www.realtimecollisiondetection.net/5.5.2 Separating Axis Test for Moving Convex動いている凸オブジェクトに対する分離軸判定について。回転していない凸のポリゴンあるいは多面体オブジェクトが一定の速度で移動している場合分離軸判定の修正が交差時間を決定するのに利用可能です。２つの移動しているオブジェクトAおよびBに対してAの速度をBから引き算して静止オブジェクトAと運動オブジェクトBとの交差として考えることができます。AおよびBが接触し始める時間ではAおよびBを射影して得られる線分の間隔がどれかの軸に対しては離れていなければなりません。接触終わりの時間でも同様です。結果的にBとAの交差判定は射影してできる線分間隔が交差する始めと終わりの時間における各分離軸に対して計算すれば十分です。任意の時間間隔の間で交差が生じているかどうかで衝突結果を決定できるわけです。ということで今日は分離軸判定。なんだか処理負荷高そうかも。
2006年04月25日
コメント(0)
-
Real-Time Collision Detection 5.5.1 Interval Halving for Intersecting Moving Objects
Real-Time Collision Detection という本を読んでいます。http://www.realtimecollisiondetection.net/5.5.1 Interval Halving for Intersecting Moving Objects運動しているオブジェクトの交差に対する間隔の等分化による方法について。前の節で扱ったサンプリングによる方法と連続スィープによる判定方法の中間にあると言える方法をここで扱います。概要としてはオブジェクトの運動全体に対する再起的なバイナリ探索を実行して、衝突の時間がもしあれば発見するという流れになります。具体例として球対Sが高速に移動していて静止しているオブジェクトをすりぬける場合に発生する問題について再び考えることにします。Sが位置Aにありその運動がベクトルｖによって記述されているとします。最初にAおよびA＋ｖにおいて球体をすっぽりと包括できる境界球を作ることから始めます。そしてこの球と他のオブジェクトの交差判定を行います。交差がなければ終わりそうでなければ前後半分を再起的に調べていくことになります。ここまでのソースが本文にあります。この方法なら任意の動きをする複雑なオブジェクトにも適用できますね。まあ処理負荷はそれなりにかかってしまうわけですが。
2006年04月24日
コメント(0)
-
Real-Time Collision Detection 5.5 Dynamic Intersection Tests
Real-Time Collision Detection という本を読んでいます。http://www.realtimecollisiondetection.net/5.5 Dynamic Intersection Tests動的な交差判定に関して。ここまでの判定方法はすべて任意の時間に起こる２つのオブジェクトの交差判定を扱っていました。ただオブジェクト同士が高速に移動している場合などは本来衝突するはずのオブジェクトがすり抜けてしまいます。これはトンネリングといって好ましくない状況です。スピード感のあるゲームの場合はよくおこりますね。解決方法としては・連続スウィープ判定・オブジェクトのパスのサンプリングの２つが取り上げられています。連続スィープの場合は球かつ直線移動の場合はカプセル状の判定を行うことによってできますね。ただ形状が複雑だったり運動が複雑な場合は非常に計算量が増えてつらいところです。しょうがないので妥協案としてオブジェクトのパスをサンプリングすることになるのですがこれは単に動く間の時間をより細かい単位に分けて計算するだけです。なんというか根本的な解決にはなっていない気がしますがまあごまかせるケースも多いのでしょう。詳しいことは後の章で扱うようですので今日はここまで。
2006年04月23日
コメント(0)
-
Real-Time Collision Detection 5.4.5 Intersection of Three Planes
Real-Time Collision Detection という本を読んでいます。http://www.realtimecollisiondetection.net/5.4.5 Intersection of Three Planes3つの平面の交差に関して。ここで扱う３平面をπ1:n1・X = d1、π2:n2・X = d2、π3:n3・X = d3 と定義します。交差として考えるのは以下の５ケース１．３つの平面がすべて平行。２．３つの平面は平行で残り１つの平面は他の２平面を横切り平行な交差線を作ります。３．３つの平面がすべて１つの直線で交差します。４．平面がペアになって直線で交差し、３つの平行な交差の直線を作ります。５．３つの平面が１点で交差します。５．は n1・( n2 x n3 ) = 0 となることによって識別できます。他もまあ似たように計算すれば求まるでしょう。平面がたった一つの点Xで交差する場合この点は平面の方程式を 3x3 の線形方程式として考えることによって解くことが可能です。n1・X = d1n2・X = d2n2・X = d3この解法をしめしたソースとそれを最適化したものが本文にあります。ぶっちゃけよく分からないなぁ。なんか理屈もわからんがこの３平面の交差を求めるような状況自体思い浮かびません。まだ私には早いということなのでしょうね。
2006年04月22日
コメント(0)
-
Real-Time Collision Detection 5.4.4 Intersection of Two Planes
Real-Time Collision Detection という本を読んでいます。http://www.realtimecollisiondetection.net/5.4.4 Intersection of Two Planes2つの平面の交差について。２つの平面 π1 : n1・X = d1, π2 : n2・X = d2 によって与えられるとしましょう。平面が平行でない場合は直線 L = p + td で交差します。またこの場合 L は両方の平面上にあるので、両方の法線に対して垂直です。そのため L の方向ベクトル d は２つの平面の外積として計算することができ、d = n1 x n2 になります。もし d がゼロベクトルの場合、平面は平行か一致しています。Lを完全に決定させるためには点Pが乗っている直線も与えられなければなりません。点を平面上でd に対して垂直になるように表現します。平面は n1, n2 によって網羅できますので P = k1n1 + k2n2 によって与えられます。さらに P はあるπ1およびπ2の両方に乗っているので両方の平面の方程式を満足します。Pの表現を平面の方程式においてXの代わりに置き換えることによって2次方程式が得られますのでこれを解けば良いというわけです。ということで後は本文とソース参照で。
2006年04月21日
コメント(0)
-
Real-Time Collision Detection 5.4.3 Testing Point in Polyhedron
Real-Time Collision Detection という本を読んでいます。http://www.realtimecollisiondetection.net/5.4.3 Testing Point in Polyhedron多面体の中にある点の判定について。最も単純な判定は多面体が凸で複数の半空間の交差として与えられる場合でこの場合は点が半空間の内側にあればよいことになります。ここでもし多面体が接続の情報のない頂点の集合のみで与えられる場合、第９章で説明するGJK法は点が含まれているかどうかを効率よく調べる方法になります。さらにBSPツリーを用いる方法が第８章にあるようです。別の方法としてある方向から（典型的には+X軸方向などの主軸）光線を発射し交差する面の数を考える方法もあるようです。ただいろいろ上げているわりには本文にはそれ以上の情報が無いのが残念ですね。というかまあ後の章でやるのでまあいいのかな。
2006年04月20日
コメント(0)
-
Real-Time Collision Detection 5.4.2 Testing Point in Triangle
Real-Time Collision Detection という本を読んでいます。http://www.realtimecollisiondetection.net/5.4.2 Testing Point in Triangle三角形内の点の判定について。三角形ABCに点Pが含まれているかどうかを調べたいとします。PがABCの内側にあるのは三角形PAB,PBC,PCAがすべて時計回りであるか、もしくは反時計回りである場合に限ります。事前にPが原点にくるように平行移動してあるなら外積 u = BxC, v = CxA, w = AxB が同じ方向にあるかどうか、すなわち u・v ≧ 0および u・w ≧ 0 かどうかを調べればよいことになります。これをそのまま実装したソースが本文に書かれていますのでそちらをあわせてみればよくわかるのではないかと思います。外積が高価な場合のためにラグランジュの恒等式で内積を用いて書き直すこともできるようです。なるほどなるほど。今日はよく理解できました。
2006年04月19日
コメント(0)
-
Real-Time Collision Detection 5.4 Additional Tests
Real-Time Collision Detection という本を読んでいます。http://www.realtimecollisiondetection.net/5.4 Additional Tests追加の判定。なんといういけてない訳なんでしょ。5.4.1 Testing Point in Polygonポリゴンにおける点の判定について。凸状の n 頂点ポリゴンにおいて反時計回りに頂点が V0, V1, …V(N-1)と並んでいるとします。クエリの点Pが V0 および Vk を通る方向のある直線の左側にあるか右側にあるか判定することでそれ以降の判定でポリゴンの半分を除外することができます。またPがポリゴンの外側にある（つまりV0からV1を通る方向のある直線の右側にあるか、あるいはV0およびV(n-1) を通る直線の左側にある）と判明するか、２つの方向のある直線V0およびVkを通る直線との間にあると判明するまで k の値は段階に応じて調整され、処理は繰り返し行われます。後者の場合は、さらにPが V(k) および V(k+1) を通る方向のある直線の左側にある場合に P はポリゴンに含まれています。いわゆる２分探索で挟んでいく感じですかね。ここまでのソースが本文にありますのでそちらを参照ください。なんというか図をみないとよく理解できないですね。しかも図が次のページにあったので最初さっぱり理解できなかったよ（笑）。
2006年04月18日
コメント(0)
-
Real-Time Collision Detection 5.3.8 Intersecting Ray or Segment against Convex Polyhedron
Real-Time Collision Detection という本を読んでいます。http://www.realtimecollisiondetection.net/5.3.8 Intersecting Ray or Segment against Convex Polyhedron凸多面体に対する光線や線分の交差について。このペアの場合は凸多面体側を半空間の集合としてとらえ線分 S( t ) = A + t( B - A ), 0 ≦ t ≦ 1 の値の範囲で半空間の内側に存在するようにすれば良いということになります。効率の良い方法としては半空間の外側にある部分を切り取ることで単純に線分を各半空間に対してクリッピングします。このクリッピング処理の後に線分がゼロになった場合は交差なしとするわけです。平面に平行な場合はすぐに交差なしと判定することができますし、線分が半空間の内側にあるかどうかは端点を平面の方程式に挿入すれば計算できます。本文にはここまでの流れをまとめたソースがあります。基本的にスラブなどと考えは同じなので理解しやすいですね。
2006年04月17日
コメント(0)
-
Real-Time Collision Detection 5.3.7 Intersecting Ray or Segment against Cylinder
Real-Time Collision Detection という本を読んでいます。http://www.realtimecollisiondetection.net/5.3.7 Intersecting Ray or Segment against Cylinder円柱に対する光線または線分の交差について。ここで扱う円柱を２点PおよびQによって定義される直線と半径 r で記述するとします。Xが円柱の表面上の点をさしている場合、円柱の表面は以下の陰関数方程式を満足します。（ v - w ）・（ v - w ） - r^2 = 0 ここでv = X - Pd = Q - Pw = ( v・d / d・d )dとします。交差判定に使用する点ABで表される直線を L(t) = A + t( B - A ) とすると円柱との交点は先ほどのXを L(t) で置き換えたものになります。計算自体は本文を参照ください。最終的に２次方程式になりますので判別式で交点の数がもとまり解はそのまま交点です。ここまでは本文にソースがありますのでそれをパクればなんとかなるでしょう。
2006年04月16日
コメント(0)
-
Real-Time Collision Detection 5.3.6 Intersecting Ray or Segment against Triangle
Real-Time Collision Detection という本を読んでいます。http://www.realtimecollisiondetection.net/5.3.6 Intersecting Ray or Segment against Triangle三角形に対する光線または線分の交差について。直線と三角形の交差は前の節で扱ったとおりですが光線および線分に関しては少しだけ異なった手法があるようです。ここで扱う三角形をABCとしABCの平面上の点を T( u, v, w ) = uA + uB + uC, ( u + v + w = 1 ) で定義できるとします。また T が ABC の内側にあるのは重心座標が 0 ≦ u, v, w ≦ 1 を満たすときになります。２つの点PおよびQの間にできる方向のある線分はパラメータ R(t) = P + t( Q - P ), (0 ≦ t ≦ 1 ) によって定義できますので T( u, w ) を R(t) に置き換え解くことで交点を求めることが可能になります。実際にはクラメールの公式で解くことができます。このあたりは本文の数式参照。ここまでのソースもありますのでそちらを読めば実装も問題ないでしょう。副産物として三角形の法線も求まるようです。本文にはさらなる最適化の例も挙げられていますがそちらは省略。基本的には事前計算できるところを計算してそれを利用といった流れになるでしょうか。
2006年04月15日
コメント(0)
-
Real-Time Collision Detection 5.3.5 Intersecting Line against Quadrilateral
Real-Time Collision Detection 5.3.5 Intersecting Line against Quadrilateral Real-Time Collision Detection という本を読んでいます。http://www.realtimecollisiondetection.net/5.3.5 Intersecting Line against Quadrilateral四辺形に対する直線との交差について。四辺形の交差判定は実は前の節で解説した方法と大差ない感じに判定できます。まずここで利用する四辺形をABCDと定義し凸で反時計回りに配置してあるとします。まずはABCDの内側にあるためには三角形ABCまたは三角形DACの内側になければいけません。そこで対角にあたるCAに関して右か左か調べてその方向にある三角形に関して絞り込んで交差判定を行えばよいわけです。まああとは前の節と同様ですかね。交点も重心座標から求められますね。本文に分かりやすいソースがありますのでこれをみればだれでも理解できるでしょう。ただ四辺形と直線との交差を直接みる頻度って少ないのかも。面倒だからこういうの三角形に分割してもらうようなことが今までは多かったかな。でも細かく対応した方が作業が楽だったりパフォーマンス的に有利なこともあるでしょうからよく覚えておきましょう。
2006年04月14日
コメント(0)
-
Real-Time Collision Detection 5.3.4 Intersecting Line against Triangle
Real-Time Collision Detection という本を読んでいます。http://www.realtimecollisiondetection.net/5.3.4 Intersecting Line against Triangle三角形に対する直線の交差に関して。これはおそらくゲームで最も良く利用されるところなのでしょうね。ここでは三角形をABC、直線をPQで与えられ交差点をRとして考えます。交差の判定方法としてはまずRを計算してそれが三角形の内側にあるかどうかの判定を行う方法があります。Rが辺AB、BC、CAの左側にある場合ABCが反時計回りにならんでいるならRはABCの内側にあることになります。同様にRがすべての辺の右側にあってABCが時計回りであってもよいですね。Rがどちら側にあるかを判定するために直線PQを三角形の辺を直接利用してスカラ３重積を考えることで求めることができます。もし三重積がすべて同じ符号を持っている場合内側を通ることになります。これは理解しやすいですね。そして交差点は重心座標から求まります。ここまでのソースが本文にありますので参考にするのがよいのではないかと思います。本文にはこの後難しい最適化の話が出てくるのですがここでは割愛。というかぶっちゃけPlucker座標よく分からん。
2006年04月13日
コメント(0)
-
Real-Time Collision Detection 5.3.3 Intersecting Ray or Segment against Box
Real-Time Collision Detection という本を読んでいます。http://www.realtimecollisiondetection.net/5.3.3 Intersecting Ray or Segment against Boxボックスに対する光線や線分の交差について。ここではボックスを直角な３つのスラブの交差として考えます。光線とスラブの交差間隔は光線のパラメータ方程式 R(t) = p + td をスラブの平面を表す方程式X・n = d に対して挿入し t について解くことによって得られます。こちら AABB と光線との交差を求めるソースが本文にありますのでそれをみれば実装できるでしょう。もし線分とボックスが交差しているかどうかだけなら分離軸による手法も利用できます。この例も本文にソースがありますね。線分とボックスが平行になった際に問題が生じますので外積を利用して除外しているところが重要でしょうか。ということで今日は分かったような分からないような。このパターン仕事で使ったことないんですよね。
2006年04月12日
コメント(0)
-
Real-Time Collision Detection 5.3.2 Intersecting Ray or Segment against Sphere
Real-Time Collision Detection という本を読んでいます。http://www.realtimecollisiondetection.net/5.3.2 Intersecting Ray or Segment against Sphere球に対する光線または線分の判定について。光線を R(t) = P + td, t ≧ 0 として定義します。後の計算を楽にするため d は正規化しておくことにします。線分ではないので t ≧ 0 の範囲を扱います。また球の境界を ( X - C )・( X - C ) = r^2 で定義します。ここで C は球の中心で r は半径です。X を R で置き換えて以下の式を得ます。( P + td - C)・( P + td - C) = r^2 m = P - C とすると( m + td )・( m + td ) = r^2 (d・d)t^2 + 2( m・d )t + ( m・m ) = r^2 d は正規化済みなので d ・d = 1t^2 + 2( m・d )t + ( m・m ) - r^2 = 0ということで２次方程式になりました。判別式で解の個数がわかり（ここではまさに交差の数）２次方程式の解の法則（だっけ?）で交点も求まります。ということで後は本文のソースをよめば良いでしょう。ということで今日は簡単でした。
2006年04月11日
コメント(0)
-
Real-Time Collision Detection 5.3 Intersecting Lines, Rays, and (Directed) Segments
Real-Time Collision Detection という本を読んでいます。http://www.realtimecollisiondetection.net/5.3 Intersecting Lines, Rays, and (Directed) Segments直線、光線、（方向のある）線分の交差に関して。レイトレみたいな衝突判定でよく使うところ。5.3.1 Intersecting Segment against Plane平面に対する線分の交差に関して。(n・X) = d によって与えられる平面Pとパラメータ方程式 S(t) = A + t( B - A),0≦ｔ≦1 によって与えられる線分の交差を考えることにします。数学的には高校数学の範囲。いきなりソースで示すとint IntersectSegmentAndPlane( Point a, Point b, Plane p, float &t, Point &q ){// 方向のある直線 ab に対して平面と交差する t の値を計算Vector ab = b - a;t = ( p.d - Dot( p.n, a ) ) / Dot( p.n, ab );if ( t ＞＝ 0.0f && t ＜＝ 1.0f ){q = a + t * ab;return 1}return 0}とこんな感じ。本文にはもう１パターンあるのでそっちも参考に。何れにせよそれほど難しくはないのではないかと思います。ここはよくテストにでるところかなぁ（笑）
2006年04月10日
コメント(0)
-
Real-Time Collision Detection 5.2.10 Testing Triangle against Triangle
Real-Time Collision Detection という本を読んでいます。http://www.realtimecollisiondetection.net/5.2.10 Testing Triangle against Triangle三角形に対する三角形の判定について。ここでは２つの三角形ABCとDEFの交差の判定を扱うことにします。まずは最も直接的な判定方法。交差は以下の２パターンなのでそれを調べる方法です。・一方の三角形の２つの辺が他方の三角形の内部を貫通している・各三角形のそれぞれの一辺が他方の三角形の内部を貫通しているこれらは結局のところ最大６つの辺対三角形の判定によって実装できます。この際三角形が同一平面上にある場合か１つあるいは両方の三角形が縮退している場合などはうまくあつかえないので例外処理を組み込む必要があります。次に説明されているのは分離軸判定を適用する方法。２つの三角形の交差に対して１１の分離軸が判定される必要があります。２つの三角形の面の法線に対して平行な軸１つずつおよび１つの三角形から１つずつの辺の９通りの組み合わせです。しかしこれはさすがに力技な感じ・・・。そこでより効率的なアルゴリズムとしては間隔重複法と呼ばれる手法が説明されています。これはまず最初の段階として２つの面法線が分離軸として働くかどうかを判定します。両方の三角形に対して１つの三角形の頂点が他方の三角形の片側に完全にあるかどうかを判定することによって行います。もしそうなら三角形は交差していません。そうでなければこの時点で三角形の平面が直線L（L(t)=P+td(ここで d = n1 x n2 は２つの三角形の法線 n1, n2 の外積)）で交差しています。さらにこの直線は両方の三角形に対して交差していなければならないので三角形とLの間にある交差間隔の大きさをこれで計算できます。これらの間隔が交差していれば三角形は交差しているというわけです。ソースはこの辺http://www.acm.org/jgt/papers/Moller97/なんだかとてもややこしいなぁ…。ということでより概念的には分かりやすい判定は貫通法です。流れとしてはこんな感じ。１．三角形１の平面の方程式を計算。三角形２の頂点がすべてこの平面に対して同じ側にある場合は交差なしと判定して終了。２．三角形２と三角形１の平面の間にある交差を計算します。これは三角形１の平面上における線分になります。３・線分が三角形２と交差するか包括されるか判定しそうなら交差。そうでなければ交差していない。なるほどこの方法が一番よさそうですね。今日はなかなか難しいところでしたが収穫も大きいところといったところでしょうか。
2006年04月09日
コメント(0)
-
Real-Time Collision Detection 5.2.9 Testing AABB against Triangle
Real-Time Collision Detection という本を読んでいます。http://www.realtimecollisiondetection.net/5.2.9 Testing AABB against Triangle三角形に対するAABBの判定について。こいつは大変です。以下の13種類の軸を射影のために考慮する必要があります。１．AABBからの３つの面の法線。２．三角形からの１つの面の法泉。３．両方からの辺の組み合わせに対してそれぞれの外積を計算して与えられる９つの軸。これらの分離軸判定は３－１－２の順に行うのが良いようです。またここで扱うAABBに関してはOBB同様に中心Cローカル軸 u0 = ( 1, 0, 0 ), u1 = ( 0, 1, 0 ), u2 = ( 0, 0, 1)長さの大きさはは e0, e1, e2 です。判定する三角形は各点 V0 = ( v0x, v0y, v0z ), V1 = ( v1x, v1y, v1z ),V2 = ( v2x, v2y, v2z ) により与えられるとします。１．のAABBからの面法線(u0,u1,u2) はAABBと三角形のAABBを計算しその交差を判定することによって判定することができます。２．の面法線に平行な軸に対する判定はAABBが三角形の平面と交差しているかどうかの判定と一致します。これは５．２．３で扱ったとおり。３．です。厄介です。ぶっちゃけよく理解できません。オブジェクトを原点に移動させて単純化させるのが肝でしょうか。ということで後は本文のソースを参照といったところでしょうか。かなり大変なのでこの交差は他の手法で代用したいところです。
2006年04月08日
コメント(0)
-
Real-Time Collision Detection 5.2.8 Testing Sphere against Polygon
Real-Time Collision Detection という本を読んでいます。http://www.realtimecollisiondetection.net/5.2.8 Testing Sphere against Polygonポリゴンに対する球の判定に関して。こいつは今までのものよりも厄介です。まず考えられる手法はポリゴン上で球の中心と最も近い最近接点とを計算しこの２つの点の間の距離を球の半径と比較します。与えられた点Pに対するポリゴン上の最も近い点はポリゴンを三角形に分割してPに対して最も近い点を各三角形に対して計算し、その中でPに最も近い点を返します。分割してあれこれするのでいかにも効率悪そうです。別の方法として以下の判定を行うこともできます。１．球とポリゴンの平面の交差判定２．ポリゴンの各辺が球を貫通しているか判定３．球の中心をポリゴンの平面に射影します。そしてこの点がポリゴンの内部にあるか判定します。ということで後は本文のソース参考でお願いします。なかなかこのペアの判定は厄介だなぁ。
2006年04月07日
コメント(0)
-
Real-Time Collision Detection 5.2.6 Testing Sphere against OBB
Real-Time Collision Detection という本を読んでいます。http://www.realtimecollisiondetection.net/5.2.6 Testing Sphere against OBBOBBに対する球の判定に関して。これもAABB同様でとくになし。最近接点を求めて計算すれば衝突判定のついでに接触点がとれて便利ですよと。5.2.7 Testing Sphere against Triangle球の三角形に対する判定に関して。これも最近接点を求めて計算します。衝突判定と衝突点が同時にとれて便利なのも同じ。というか球はやっぱ楽ですね。ということで今日は簡単なところ２つだけ。ちょっとものたりないですね。
2006年04月06日
コメント(0)
-
Real-Time Collision Detection 5.2.5 Testing Sphere against AABB
Real-Time Collision Detection という本を読んでいます。http://www.realtimecollisiondetection.net/5.2.5 Testing Sphere against AABBAABBに対する球の判定に関して。これはAABBを球の大きさで膨らませる感じの手法でできるかと思いますがここでは球の中心点からAABBまでの距離を求める手法を扱っていますね。基本的に 5.1.3.1 まま。しいていうなら最近接点を求めそこから円の中心へのベクトルを求めその２乗距離でみるようにすれば接触判定を行い同時に接触点も求めることができるので便利なところでしょうか。また注意点としてAABBの面の外側にあればよいわけではないというところでしょうか。図を書けば分かるのですが球は四角じゃないので角が正確にとれないんですよね。ということで今日は簡単でした。
2006年04月06日
コメント(0)
-
Real-Time Collision Detection 5.2.4 Testing Cone against Plane
Real-Time Collision Detection という本を読んでいます。http://www.realtimecollisiondetection.net/5.2.4 Testing Cone against Plane平面に対する円錐の判定について。平面が (n・X) = d (平面上の点Pに対して d = -P・n が成立して n は単位ベクトルとする) で与えられ円錐は頂上T、正規化された方向軸d, 高さh, そして底面の半径 r によって記述されるとします。円錐上にある点のうちどれか1つでも負の半空間の内側にある場合、すなわち (n・X) ＜ d となる点Xがあれば平面の半空間と交差していることになります。この際に円錐の２点だけ判定すればよいことになります。・円錐の頂上T・円錐の円形の底面上にある点Qのうち n の逆方向について最も離れている点後者の判定のためにQを以下のように求めます。Q = T + hv + rmここで m = ( n x v ) x v によって求めます。（この辺は本文の図を参照しないときついなぁ）ということで無事交差を求められました。ここは図をみつつ取り組むしかないですね。
2006年04月05日
コメント(0)
-
Real-Time Collision Detection 5.2.3 Testing Box against Plane
Real-Time Collision Detection という本を読んでいます。http://www.realtimecollisiondetection.net/5.2.3 Testing Box against Plane平面に対するボックスの判定について。平面 P を (n・X) = d で与えられるとします。ボックス B が P と交差しているかどうかは分離軸判定で判定できます。平面は無限に延長可能なので平面の法線 n に平行な軸の判定のみでOKです。最初にBがOBBの場合を考えてみます。Bの半径をnに平行な直線L(= b.c + t * p.n)上に射影してできる距離を計算して、平面からボックスの中心までの距離を比較してその絶対値をとれば良いことになります。詳しくは本文のソースを参照すればよくわかるのではないかと思います。次にAABBを扱います。事前にローカル軸 u0, u1, u2 が前もって知られている場合、コードが単純化されます。AABBの中心を計算して正の方向を計算しLに対して射影する形になります。こちらも本文にソースがありますのでこちらを読めば良く理解できるのではないかと思います。ということで今日はここまで。比較的わかりやすかったかな。
2006年04月04日
コメント(1)
-
Real-Time Collision Detection 5.2.2 Testing Sphere against Plane
Real-Time Collision Detection という本を読んでいます。http://www.realtimecollisiondetection.net/5.2.2 Testing Sphere against Plane平面に対する球の判定について。ここでは以下の3つが挙げられています。・球が平面に対して交差しているかどうかの判定。・球が平面の裏側に完全にあるかどうかの判定。・球が平面の負の反空間に交差しているかどうかの判定。球Sを中心点Cおよび半径ｒによって記述されるとし、平面πを単位ベクトルnを用いて (n・X) = d として記述するとします。こうしておけば平面の方程式を球の中心に対して評価できます。得られる値は球の中心から平面への符号付距離になります。あとはこの距離の絶対値が球の半径より小さければ平面が球に交差していることになります。同様にして球の半径の負の値より小さければ平面の裏側にあり球の半径より小さければ負の半空間と交差することになります。ということで今日はここまで。詳しいことは本文にソースがあるのでそちら参照。
2006年04月03日
コメント(0)
-
Real-Time Collision Detection 5.2.1.1 Robustness of the Separating Axis Test
Real-Time Collision Detection という本を読んでいます。http://www.realtimecollisiondetection.net/5.2.1.1 Robustness of the Separating Axis Test分離軸判定の頑健性について。robustness を頑健性と訳すのはどうかな。ロバストってカタカナで書いている人も結構いるし翻訳はむずかしいなぁ。さて分離軸の問題について。分離軸が各オブジェクトの辺の外積によって形成される場合は問題があるようです。これらの辺が平行になる場合は結果がゼロベクトルになりこの軸に対するすべての射影がゼロになってしまいます。対処法としては結果として得られる外積がゼロに近いベクトルであるかどうかを調べ、もしそうなら２つのベクトルに対して垂直な他の軸を生成するかその軸を無視すれば良いようです。ソースは付属していますがちょっと不完全で良く分からず。まあ今日のところはこういった問題が発生しうるというところまで理解しておくことにします。
2006年04月02日
コメント(0)
-
Real-Time Collision Detection 5.2 Testing primitives
Real-Time Collision Detection という本を読んでいます。http://www.realtimecollisiondetection.net/5.2 Testing primitivesプリミティブの判定について。つうか test を判定と訳すのも微妙だな。5.2.1 Separating Axis Test分離軸判定について。分離超平面理論（separating hyperplane theorem）というものに従うと２つの凸集合AおよびBが与えられた場合に２つの集合が交差しているかそうでなければ分離超平面PがAがPの一方の側にBがもう片方にあるように存在するということを示すそうな。分け分からん書き方ですがようは分離軸が存在する場合は2つのオブジェクトは接触しないということなのですね。AおよびBを分離する超平面Pが与えられると分離軸はPに対して垂直な直線Lになります。なぜこのLが分離軸と呼ばれるのかというと A, B を L に対して垂直に射影した結果が２つの重なり合いのない線分になるからです。この分離軸が存在するのは分離超平面が存在する場合に限るのでどちらも判定に利用することができます。さてでは分離軸をどのように決定するのが良いのでしょうか。本文にはいろいろかいてありますが要約すると面体面、面対辺、辺対辺になります。このうち面対面、面対辺の場合は両方のオブジェクトの面法線をありえる分離軸として判定するだけで十分です。辺対辺の場合は2つの辺の外積を分離軸と一致する可能性があるとして判定します。よってこれらのケースを考えるとよいようです。・オブジェクトAの面の法線に対して平行な軸・オブジェクトBの面の法線に対して平行な軸・Aのすべての辺とBのすべての辺の外積によって得られるベクトルに平行な軸ここまでみれば分かるように分離軸判定はかなりの力技です。したがって分離軸判定を成功した分離軸をキャッシュしておきそれを使って判定する方法でパフォーマンスを稼ぐのがよさそうです。
2006年04月01日
コメント(0)
全31件 (31件中 1-31件目)
1
-
-
- 何か手作りしてますか?
- ミニ革靴を作る その３２
- (2026-07-27 19:20:03)
-
-
-
- フィギュア好き集まれ～
- 1/6 『アズールレーン』 大鳳 ナイト…
- (2026-07-27 12:07:00)
-
-
-
- がんばれ！地方競馬♪
- 7/29名古屋・園田の１点勝負＋門別
- (2026-07-28 21:55:21)
-
