Petitverse

Naさん
速度は確かに遅くはなりますね。
16×16だと256要素。完全には重ならないので最大でその倍。ARYOP使えば多少は速くはなりますが、衝突しているスプライトの数が多くなると…
まぁ速度に関してはvectorでもある程度はかかるとは思います。
メモリもその分かかりそう。(これは使い回しが効く)
あと、回転が入ると結構厄介です。(メモリも倍ぐらいに増える)
ぶつかった方向を出すのも難しそう。

4×4とか8×8とかならある程度実用的だと思います。

中心の速度情報からどこから当たったか判別できない例その�@
まぁそもそもへこみのある図形は想定してないので、これは仕方ない。

その�A
回転がかかると一気に複雑になる。

SatoshiMcCloudさん
質量とか慣性モーメントは当たり判定の仕事ではないので別実装でお願いします。(一応撃力やトルクを求めるのに十分な情報は返してるはず)
実際当たり判定について考察してるのは物理シミュレーション的なことをやろうとしてるから。
前作ったブロック崩しをマスコットアプリ文化祭用にリメイクしようと思って。

https://youtu.be/1OrAfja5x0c?36m52s

内積(dot/inner product)
内積とは、2つのベクトルに対して行う計算です。
v1=(r1,j1)とv2=(r2,j2)の内積v1・v2は r1*r2+j1*j2で計算することができます。
その大きさは「v1のv2方向成分にv2の大きさを掛けたもの」となります。
つまり、v2の大きさが1だった場合はv1のv2方向成分となります。
内積はv1とv2を入れ替えても同じ結果になるため、「v2ベクトルのv1方向成分にv1の大きさを掛けたもの」と言い換えることも出来ます。
def dot(r1,j1,r2,j2)
　return r1*r2+j1*j2
end

行列式(determinant)/二次元外積(cross product)
行列Aを
a b
c d
としたとき、 ad-bcを行列式と言います。
ここで2つのベクトルv1=(r1,j1)とv2=(r2,j2)を上下に並べた行列の行列式 v1×v2=r1*j2-r2*j1はいくつかの嬉しい性質を持ちます。

性質1
v1から見てv2が右側を向いている場合、v1×v2は正となり、左側を向いている場合は負になる。(右手座標系の場合)

性質2
点a,b,cが存在したとき、cとaの位置ベクトルv1とcとbの位置ベクトルv2の行列式v1×v2はaと線分bcの距離にv2の大きさを掛けたものとなる。
つまり、v2の大きさが1だった場合、v1×v2は点aと線分bcの距離に等しい

この演算は3次元および7次元ベクトルの計算である外積に似ているため、二次元外積と呼ばれることが多いです。

内積は計算の順序が変わっても結果は変わらないですが、二次元外積は性質1からも明らかなように計算順序により結果が変わるので注意する必要があります。

def cross(r1,j1,r2,j2)
　return r1*j2-r2*j1
end

正規化(normalize)
先の内積と行列式でv2の大きさが1だった場合を考えましたが、ベクトルではこのように大きさが1だと都合がいい場合があります。
ベクトルの大きさが1でない場合は1にすれば良いです。
ベクトルの大きさを1にすることを正規化と言います。
正規化はベクトルを自身の大きさで割れば良いです。

def norm ri,ji out ro,jo
　var a#=cabs(ri,ji)
　ro=ri/a#
　jo=ji/a#
end


点同士の当たり判定
点同士の判定は非常にシンプルで、二点の座標が一致すればよいです。
ただし、座標が実数の場合、正確に一致することは稀なため、整数に丸めたり、ある程度の誤差を許容するなどの工夫が必要です。
DEF POINTHITPOINT X1,Y1,X2,X2 OUT HIT,CX,CY
　CX=(X1 OR 0):CY=(Y1 OR 0)
　HIT=CX==(X2 OR 0)&&CY==(Y2 OR 0)
END
なお、法線については定義が出来ないため考えないものとします。(常に0とかでも問題ないけど)

円と点の当たり判定
円の中心座標と点の座標の距離が円の半径以下なら衝突です。衝突座標は点の座標、衝突した方向は円と点の座標の位置ベクトルを正規化したものです。

def circlehitpoint x1,y1,r,x2,y2 out hit,nr,nj,cx,cy
　nr=x2-x1:nj=y2-y1
　cx=x2:cy=y2
　norm nr,nj out nr,nj
　if dist(x1,y1,x2,y2)<=r then
　　hit=1
　else
　　hit=0
　endif
end


円と円の当たり判定
円と点の判定とほぼ同じです。衝突座標の計算が少し変わります。(内分点の公式を使います)

def circlehitcircle x1,y1,r1,x2,y2,r2 out hit,nr,nj,cx,cy
　nr=x2-x1:nj=y2-y1
　cx=(x1*r2+x2*r1)/(r1+r2):cy=(y1*r2+y2*r1)/(r1+r2)
　norm nr,nj out nr,nj
　if dist(x1,y1,x2,y2)<=r1+r2 then
　　hit=1
　else
　　hit=0
　endif
end

ところで、dist(x1,y1,x2,y2)<r1+r2の部分は、両辺を2乗して
(x2-x1)*(x2-x1)+(y2-y1)*(y2-y1)<r1+r2にすると少し速くなると思われます。(未検証)

ツララさん
歪に変形ってどれのことだろう？
まぁTriTriHit○○とか○○HitTriTriとかは作ろうと思ってるので複数オブジェクトへの分割は出来ると思いますよ

中心速度で法線を判定しようとしたときの回転がある場合のやつですかね(反例�A)

そもそも速度で法線を判別しようとすること自体あまり良いやり方と思えないんですよね。速度と法線にあまり関連性が見られないですし、二次元だったものを三次元で考えなきゃいけなくなる。

速度を考えずに法線が出せるならそっちの方がシンプル。

円と直線の当たり判定
線と円の距離が円の半径以下なら衝突です。そう、二次元外積。
法線が少し厄介ですが、直線のベクトルを正規化して90度回転させると良いでしょう。

def circlehitline x1,y1,r,x2,y2,x3,y3 out hit,nr,nj,cx,cy
　var r23#=x3-x2,j23#=y3-y2
　var d#=dot(r23,j23,x1-x2,y1-y2)
　var c#=cross(r23,j23,x1-x2,y1-y2)
　cx=x2+r23#*d#
　cy=y2+j23#*d#
　if abs(c#)<=r then
　　hit=1
　else
　　hit=0
　endif
　if c#>0 then
　　norm -j23#,r23# out nr,nj
　else
　　norm j23#,-r23# out nr,nj
　endif
end

円と線分の当たり判定
以下の3つの条件のいずれかを満たせば衝突です。
条件1
円と直線が衝突している
(始点と終点の位置ベクトルv23)・(始点と円の位置ベクトルv21)が正
(終点と始点の位置ベクトルv32)・(終点と円の位置ベクトルv31)が正
の全ての条件を満たす
条件2
円と始点が衝突している
条件3
円と終点が衝突している
def circlehitlseg x1,y1,r,x2,y2,x3,y3 out hit,nr,nj,cx,cy
　circlehitline x1,y1,r,x2,y2,x3,y3 out hit,nr,nj,cx,cy
　if hit==0||dot(x3-x2,y3-y2,x1-x2,y1-y2)<0||dot(x2-x3,y2-y3,x1-x3,y1-y3)<0 then
　　circlehitpoint x1,y1,r,x2,y2 out hit,nr,nj,cx,cy
　　if hit==0 then
　　　circlehitpoint x1,y1,r,x3,y3 out hit,nr,nj,cx,cy
　　endif
　endif
end

SatoshiMcCloudさん
それが出来れば理想なんですけどね。
実際には難しいので毎フレーム取ってそう。
今衝突しているかを判断するよりこれから衝突するかを判断するのは直感的に遥かに難しそう。(レイトレーシングあたりを想像するとそんな気がする)

衝突が多ければかえって重くなるどころか、実際には衝突しないもの(衝突する前に別の物体に衝突するものとか)についても考えなきゃいけなくなりそう。

ブロック崩し作りたい欲が出てきたのでRe:flow

SatoshiMcCloudさん
「速度ベクトルが変化しないと仮定すると」
この条件見落としてました。
x,yに加えて時間の次元が増えたと考えると3D空間の当たり判定と捉えることが出来るので、「回転しない」という条件が加われば出来そうですね。
回転が入った場合、曲面からなる立体になるので、曲面は多角形で近似するという3Dのセオリー通りにやるならどうしても時間軸での分割が入りますね。
とはいえ、瞬間で判定するよりは良い近似になるので、時間の分割の頻度は下がりそうですね。計算負荷的にどうかは微妙ですが。

新たなトピック建てました。
メモ帳に残ってた書きかけの残骸だけ放出しときます。
http://petitverse.hosiken.jp/community/petitcom/topic/?read=1819&ukey=0

直線と線分の当たり判定/線分と直線の当たり判定

直線から見て線分の片方の端が右側、もう片方が左側にあれば衝突です。
つまり、直線の方向ベクトルと、直線上の点と線分の端の位置ベクトルとの二次元外積の符号が異なれば衝突です。

def linehitlseg x11,y11,x12,y12,x21,y21,x22,y22 out hit,nr,nj,cx,cy
　var cros0#=cross(x12-x11,y12-y11,x21-x11,y21-x11)
　var cros1#=cross(x12-x11,y12-y11,x22-x11,y22-x11)
　if sgn(cros0#)!=sgn(cros1#) then
　　hit=1
　else
　　hit=0
　endif
　if sgn(cros0#)<=0 then swap cros1$,cros0#
　if abs(cros0#)>abs(cros1#) then
　　norm -y12+y11,x12-x11 out nr,nj
　else
　　norm y12-y11,-x12+x11 out nr,nj
　endif
end

線分と線分の当たり判定

直線1と線分2が衝突している
線分1と直線2が衝突している

以上の2つの条件を満たせば衝突です