以前師匠の難題７の際にちょっと触れたカリング判定式…検索したらＣＧソフト系の解説で単に３Ｄ処理を軽減する判定…と解説されている記事が見つかりまして。そら、ＣＧツールの利用から考えれば理解する所はそこだけで良いのだけれども…と思って簡単なソースを書いてみました。
そもカリングとは
はい、巻くを意味するカールの動名詞です。それの判定式ですから…
３頂点が右に巻いているか、左に巻いているか、あるいはどちらでも無い（全て同一点もしくは直線状に並んでいる）かの判定に用いられます。
どちらでもなければ０、右／左なら正もしくは負の値を返すのですが…
どちらが右回りでどちらが左回りかは環境によるのでなんとも言えないです、DirectX と OprnGL でも違いましたし、ゲーム機とＣＧツールで齟齬が出た事もありました…すり合わせで地獄を見た記憶が…
カリング判定の計算式
(X1-Px)(Y2-Py)-(X2-Px)(Y1-Py)
えらく簡単です。やっている事は３次元の面法線を外積から求める計算から、必要な部分だけを抽出した計算式…らしいのですが、正直外積の理解がイマイチなので綺麗に説明できません。
ちなみに面法線とは Blender では水色に見えるコレ（面に垂直に立つ面の向いている方向を示すベクトル）の事で、コレが手前に向いているか奥に向いているかを抽出しています。
表示処理の軽減：裏面省略
サイコロのような立方体を考えた際、これを３角ポリゴンで表現するとして…
これらの表面に例えば右巻きのマークを描きます。
で、このサイコロを回してみたらどうなるか？を考えてみましょう。
裏面…というか手前側から観えない面は左巻きになりますよね。
ならば、逆巻になったポリゴンは見えないのだから描画処理を省略すれば良い…というのが裏面省略でした。
…が、最近は光の反射計算等を行っている場合もあるので単純に省略すれば良いと言うものでも無くなってきています。
又、応用として、右巻き／左巻きの面の境界になる辺を線で描画すると輪郭線ができるため、アニメ調のアウトライン処理を行う際にも用いられています。
表示処理の軽減：視界によるオブジェクト省略
この図を上からの俯瞰図ととらえ、三角の下の頂点を視点、三角を視野角の範囲とすると青く変色した×マークが視野角の範囲に入った物で、それ以外は見えていない物になります。
ならば見えていないオブジェクトを省略すれば処理を大きく省略できます。もちろん光の反射等もあるので（以下略
どう判定するのかと言えば…
視野の範囲の三頂点がどちら周りかを調べ…
判定する点と各辺の頂点がどちら周りになるのかを調べます。
これらが全て同じ方向に回転している場合、判定する頂点は三角の中にあると判ります。
視界の範囲…を三角で示しましたが「視界って距離依存だから三角ではなくないか？」という当然の疑問が出ます。はい、正確には円の判定を組み合わせて距離の判定も行います…
円の範囲判定
(Px-Ox)(Px-Ox)+(Py-Oy)(Py-Oy)
これを円の半径の二乗と比較します。式自体はピタゴラスの定理って奴ですね。
直角三角形の底辺の二乗と高さの二乗の値が斜辺の二乗の値に等しいという奴です。
この斜辺の二乗と半径の二乗を比較して半径の二乗の方が大きければ円の範囲内に入っている事になります。
より正確には斜辺の二乗の平方根が斜辺の長さになり（あたり前）、この値と半径の長さを比較すれば良いのだけど、平方根の計算は非常に重い処理である事と、二乗の場合必ず正の値になる為比較が用意である事、各値の絶対値の大小関係と二乗の大小関係が同じである事から二乗の値で比較を行います。
でもって二つの処理を重ねた物がこんな感じ
ソースここから
import pyxel
import random
SCREEN_SIZE_W = 320
SCREEN_SIZE_H = 240
OBJ_MAX = 100
RADIUS = 50
def JudgCircle(px,py,circle_x,circle_y,r):
x = px - circle_x
y = py - circle_y
if r*r >= x*x+y*y:
return True
return False
def JudgCulling(px,py,ax,ay,bx,by):
return (ax-px)*(by-py)-(bx-px)*(ay-py)
def JudgTriangle(px,py,ax,ay,bx,by,cx,cy):
f = JudgCulling(ax,ay,bx,by,cx,cy)
f1 = JudgCulling(px,py,ax,ay,bx,by)
f2 = JudgCulling(px,py,bx,by,cx,cy)
f3 = JudgCulling(px,py,cx,cy,ax,ay)
if f == 0:
return false
if f < 0 and f1 < 0 and f2 < 0 and f3 < 0:
return True
if f > 0 and f1 > 0 and f2 > 0 and f3 > 0:
return True
return False
class Obj:
def __init__(self):
x = 0
y = 0
color = 2
class App:
def __init__(self):
# 画面サイズ 320x240 で初期化
pyxel.init(SCREEN_SIZE_W, SCREEN_SIZE_H, title="judg")
self.object = []
for i in range(OBJ_MAX):
self.object.append(Obj())
self.object[i].x = random.randint(0,SCREEN_SIZE_W)
self.object[i].y = random.randint(0,SCREEN_SIZE_H)
self.object[i].color = 2
pyxel.run(self.update, self.draw)
def update(self):
pass
def draw(self):
# 画面を黒（色番号0）でクリア
pyxel.cls(0)
mx = pyxel.mouse_x
my = pyxel.mouse_y
t1x = mx + int(RADIUS/2)
t1y = my - RADIUS
t2x = mx - int(RADIUS/2)
t2y = my - RADIUS
pyxel.circb(mx,my,RADIUS,15)
pyxel.line(mx,my,t1x,t1y,15)
pyxel.line(mx,my,t2x,t2y,15)
pyxel.line(t1x,t1y,t2x,t2y,15)
for i in range(OBJ_MAX):
self.object[i].color = 2
if JudgCircle(self.object[i].x,self.object[i].y,mx,my,RADIUS):
if JudgTriangle(self.object[i].x,self.object[i].y,mx,my,t1x,t1y,t2x,t2y):
self.object[i].color = 3
pyxel.line(self.object[i].x-5,self.object[i].y-5,
self.object[i].x+5,self.object[i].y+5,
self.object[i].color)
pyxel.line(self.object[i].x+5,self.object[i].y-5,
self.object[i].x-5,self.object[i].y+5,
self.object[i].color)
App()
ソースここまで
…三角だけの時とそこまで変わらなくない？という気がしないでもないですが、オブジェクト表示そのものを省略できるならかなりの軽量化になりますし、
円の判定計算は観ての通り非常に軽いのでやっておいて損は無いと思います。
はい、そんなわけで円と三角のコリジョン判定式でした
ぶっちゃけた話、２Ｄアクションゲームの当たり判定のほとんどはこの二つの式で片付きます。昔はよく取り扱ったなあと思い、書いてみました。
0 件のコメント:
コメントを投稿