2021/06/25(金) [n年前の日記]
#1 [love2d] love2dで点と凹多角形の内外判定
love2d を使って、点と凹多角形の内外判定を試してみた。環境は Windows10 x64 20H2 + love2d 11.3。
点と凸多角形の内外判定は、先日試してみたのだけど。
_love2dで凸多角形の内外判定
凹多角形との判定はしてなかったので、できるかな、どうかなと。
ググってみたら以下の解説ページが参考になった。ありがたや。
_点と凹多角形の内外判定を行う - e.blog
_【第2回】点の多角形に対する内外判定|【技業LOG】技術者が紹介するNTTPCのテクノロジー|【公式】NTTPC
_ある点と多角形の内外判定 - Qiita
_多角形の内外判定(javascriptでの実装を添えて) - 加具留矢流余
なんでも、2つのアルゴリズムがあるそうで…。
今回は、角度の合計を調べる Winding Number Algorithm を試してみたい。JavaScript で実装した以下の版をそのまま参考にさせてもらって、Lua で書き直してみる。
_多角形の内外判定(javascriptでの実装を添えて) - 加具留矢流余
こんな感じになった。
ソースは以下。
_main.lua
_conf.lua
とりあえず、これで凹多角形との内外判定もできそうだなと…。
点と凸多角形の内外判定は、先日試してみたのだけど。
_love2dで凸多角形の内外判定
凹多角形との判定はしてなかったので、できるかな、どうかなと。
ググってみたら以下の解説ページが参考になった。ありがたや。
_点と凹多角形の内外判定を行う - e.blog
_【第2回】点の多角形に対する内外判定|【技業LOG】技術者が紹介するNTTPCのテクノロジー|【公式】NTTPC
_ある点と多角形の内外判定 - Qiita
_多角形の内外判定(javascriptでの実装を添えて) - 加具留矢流余
なんでも、2つのアルゴリズムがあるそうで…。
- Crossing Number Algorithm : 点から水平に伸びる線と多角形の交差数を数える。
- Winding Number Algorithm : 点から多角形の頂点を見て角度の合計を数える。
今回は、角度の合計を調べる Winding Number Algorithm を試してみたい。JavaScript で実装した以下の版をそのまま参考にさせてもらって、Lua で書き直してみる。
_多角形の内外判定(javascriptでの実装を添えて) - 加具留矢流余
こんな感じになった。
ソースは以下。
_main.lua
function love.load() polys = { {20, 80, 80, 20, 120, 140}, {140, 80, 200, 20, 260, 100, 200, 180}, {340, 20, 400, 60, 380, 160, 320, 160, 280, 80}, {460, 60, 520, 20, 600, 60, 600, 160, 520, 180, 460, 140}, {140, 340, 260, 340, 280, 420, 100, 440, 20, 360, 40, 200, 100, 200}, {500, 320, 460, 220, 380, 240, 440, 340, 300, 360, 340, 440, 500, 420, 520, 460, 620, 420, 600, 320} } hits = {} for i = 1, #polys do hits[i] = false end end function sign(x) return (x < 0 and -1) or 1 end function getDeg(x1, y1, x2, y2) local abs1, abs2, theta, s abs1 = math.sqrt(x1 * x1 + y1 * y1) abs2 = math.sqrt(x2 * x2 + y2 * y2) theta = math.acos((x1 * x2 + y1 * y2) / (abs1 * abs2)) s = sign(x1 * y2 - y1 * x2) return theta * s end function checkInPoly(pos, mx, my) local thetaSum = 0 local x0, y0, x1, y1 local v1x, v1y, v2x, v2y x0, y0 = pos[#pos-1], pos[#pos] if x0 == mx and y0 == my then return true end for i = 1, #pos-1, 2 do x1, y1 = pos[i], pos[i+1] if x1 == mx and y1 == my then return true end v1x, v1y = x0 - mx, y0 - my v2x, v2y = x1 - mx, y1 - my thetaSum = thetaSum + getDeg(v1x, v1y, v2x, v2y) x0, y0 = x1, y1 end thetaSum = math.abs(thetaSum) if thetaSum >= 0.1 then return true end return false end function love.update(dt) local mx, my mx, my = love.mouse.getPosition() for i = 1, #polys do hits[i] = checkInPoly(polys[i], mx, my) end end function love.draw() -- clear canvas love.graphics.clear(0, 0, 0, 1) -- draw polygon for i = 1, #polys do if hits[i] then love.graphics.setColor(1, 0, 0, 1) else love.graphics.setColor(0, 1, 0, 1) end love.graphics.polygon("line", polys[i]) end -- draw text love.graphics.setColor(1, 1, 1, 1) love.graphics.print("ESC to exit.", 8, 8) end function love.keypressed(key, scancode, isrepeat) if key == "escape" then love.event.quit() end end
_conf.lua
function love.conf(t) t.window.width = 640 t.window.height = 480 t.window.title = "Collison concave polygon" t.window.fullscreen = false -- t.window.fullscreentype = "exclusive" end
とりあえず、これで凹多角形との内外判定もできそうだなと…。
◎ HCライブラリを使ってみる。 :
その後ググっていたら、love2d から利用できる衝突判定ライブラリ、HC というものがあると知った。ソレを利用することでも目的を果たせそう。試用してみる。
_vrld/HC: General purpose collision detection library for the use with LoVE.
_HC - General purpose collision detection with LoVE - HC 0.1-1 documentation
ライセンスは…。
_License - HC 0.1-1 documentation
ちょっとよく分からないけど、無料で使えるとか、制限は無いとか書いてあるように見える。
入手の仕方は、github から zip をDLするか(緑色で「code」と書かれてる部分をクリック → Download ZIP)、git を使って clone する。
love2d の main.lua と同階層に、HCというフォルダを作成して、その中に、DLした *.lua 群をコピーする。
main.lua の中では、HC = require "HC" とか、Polygon = require "HC.polygon" を最初のほうに書いてから使う。
試用してみたところ、こんな感じになった。それらしく判定できている。
ソースは以下。今回は、HC.polygon だけを使って処理をしている。
_main.lua
_conf.lua
最初からこのライブラリを使えばよかったのだな…。
_vrld/HC: General purpose collision detection library for the use with LoVE.
_HC - General purpose collision detection with LoVE - HC 0.1-1 documentation
ライセンスは…。
_License - HC 0.1-1 documentation
ちょっとよく分からないけど、無料で使えるとか、制限は無いとか書いてあるように見える。
入手の仕方は、github から zip をDLするか(緑色で「code」と書かれてる部分をクリック → Download ZIP)、git を使って clone する。
git clone https://github.com/vrld/HC.git
love2d の main.lua と同階層に、HCというフォルダを作成して、その中に、DLした *.lua 群をコピーする。
. |-- HC | |-- README | |-- class.lua | |-- gjk.lua | |-- hc-0.1-1.rockspec | |-- init.lua | |-- polygon.lua | |-- shapes.lua | |-- spatialhash.lua | `-- vector-light.lua |-- conf.lua `-- main.lua
main.lua の中では、HC = require "HC" とか、Polygon = require "HC.polygon" を最初のほうに書いてから使う。
試用してみたところ、こんな感じになった。それらしく判定できている。
ソースは以下。今回は、HC.polygon だけを使って処理をしている。
_main.lua
Polygon = require "HC.polygon" function love.load() polys = { {20, 80, 80, 20, 120, 140}, {140, 80, 200, 20, 260, 100, 200, 180}, {340, 20, 400, 60, 380, 160, 320, 160, 280, 80}, {460, 60, 520, 20, 600, 60, 600, 160, 520, 180, 460, 140}, {140, 340, 260, 340, 280, 420, 100, 440, 20, 360, 40, 200, 100, 200}, {500, 320, 460, 220, 380, 240, 440, 340, 300, 360, 340, 440, 500, 420, 520, 460, 620, 420, 600, 320} } hits = {} p = {} for i = 1, #polys do hits[i] = false p[#p + 1] = Polygon(unpack(polys[i])) end end function love.update(dt) local mx, my mx, my = love.mouse.getPosition() for i = 1, #p do hits[i] = p[i]:contains(mx, my) end end function love.draw() -- clear canvas love.graphics.clear(0, 0, 0, 1) -- draw polygon for i = 1, #p do if hits[i] then love.graphics.setColor(1, 0, 0, 1) else love.graphics.setColor(0, 1, 0, 1) end love.graphics.polygon("line", p[i]:unpack()) end -- draw text love.graphics.setColor(1, 1, 1, 1) love.graphics.print("ESC to exit.", 8, 8) end function love.keypressed(key, scancode, isrepeat) if key == "escape" then love.event.quit() end end
_conf.lua
function love.conf(t) t.window.width = 640 t.window.height = 480 t.window.title = "Collision HC" t.window.fullscreen = false -- t.window.fullscreentype = "exclusive" end
- HC.polygon を新規作成する際、配列を unpack(配列名) で渡してやらないとエラーが出る。
- :contains(x, y) で、点がポリゴンの中に入ってるかどうかを true / false で調べられる。
- :unpack() で、ポリゴンの頂点配列を、ポリゴン描画をする love.graphics.polygon() に渡しやすくなる。
最初からこのライブラリを使えばよかったのだな…。
◎ 余談。ポリゴン描画に注意。 :
love2dのポリゴン描画、love.graphics.polygon("fill", ...) を使っていたら、妙な動作に気づいた。環境は、Windows10 x64 20H2 + love2d 11.3 x86版。
love.graphics.polygon() は、線を描画する "line"、塗り潰しをする "fill" のどちらかを指定できるけど、どうも "fill" のほうは形がおかしくなるようで…。
ソースは以下。
_main.lua
_conf.lua
これはバグ…? と思ったら、ドキュメントに記述があった。
_love.graphics.polygon - LOVE
「"fill"を使った時は凸多角形しか正常に描画できないよ」とのことで。仕様だったらしい…。ドキュメントはちゃんと読まないといかんなと…。
love.math.isConvex() を使えば凸多角形か判定できるし、love.math.triangulate() を使えば多角形を三角形に分割できるそうで。凹多角形の可能性があるなら三角形に分割して処理すべし、ということかな…。
_love.math.isConvex - LOVE
_love.math.triangulate - LOVE
せっかくだから、三角形に分割して描画する方法も試してみた。
_main.lua
_conf.lua
凹多角形の場合、三角形に分割して描画できていることが分かる。
love.graphics.polygon() は、線を描画する "line"、塗り潰しをする "fill" のどちらかを指定できるけど、どうも "fill" のほうは形がおかしくなるようで…。
ソースは以下。
_main.lua
function love.load() pos = {500, 320, 460, 220, 380, 240, 440, 340, 300, 360, 340, 440, 500, 420, 520, 460, 620, 420, 600, 320} end function love.update(dt) end function love.draw() love.graphics.clear(0, 0, 0, 1) love.graphics.setColor(0, 0.75, 0, 1) love.graphics.polygon("fill", pos) love.graphics.setColor(1, 0, 0, 1) love.graphics.polygon("line", pos) love.graphics.setColor(1, 1, 1, 1) love.graphics.print("ESC to exit.", 8, 8) end function love.keypressed(key, scancode, isrepeat) if key == "escape" then love.event.quit() end end
_conf.lua
function love.conf(t) t.window.width = 640 t.window.height = 480 t.window.title = "Draw polygon" t.window.fullscreen = false -- t.window.fullscreentype = "exclusive" end
これはバグ…? と思ったら、ドキュメントに記述があった。
_love.graphics.polygon - LOVE
「"fill"を使った時は凸多角形しか正常に描画できないよ」とのことで。仕様だったらしい…。ドキュメントはちゃんと読まないといかんなと…。
love.math.isConvex() を使えば凸多角形か判定できるし、love.math.triangulate() を使えば多角形を三角形に分割できるそうで。凹多角形の可能性があるなら三角形に分割して処理すべし、ということかな…。
_love.math.isConvex - LOVE
_love.math.triangulate - LOVE
せっかくだから、三角形に分割して描画する方法も試してみた。
_main.lua
function love.load() polys = { {40,80,100,20,200,80,180,220,100,260,20,200}, {340,280,300,200,440,180,380,80,460,60,500,160,600,160,620,260,520,300,500,260} } end function love.update(dt) end function love.draw() love.graphics.clear(0, 0, 0, 1) for i, v in ipairs(polys) do local convex = love.math.isConvex(v) if convex then love.graphics.setColor(0, 0.75, 0, 1) love.graphics.polygon("fill", v) else local col = {{0,0,1}, {0,0.25,1}, {0,0.5,1}, {0,0.75,1}} local triangles = love.math.triangulate(v) for i = 1, #triangles do love.graphics.setColor(unpack(col[(i % #col) +1])) love.graphics.polygon("fill", triangles[i]) end end love.graphics.setColor(1, 0, 0, 1) love.graphics.polygon("line", v) love.graphics.setColor(1, 1, 1, 1) local s = convex and "true" or "false" love.graphics.print("Convex : " .. s, 4, i * 20 + 20) end love.graphics.setColor(1, 1, 1, 1) love.graphics.print("ESC to exit.", 4, 4) end function love.keypressed(key, scancode, isrepeat) if key == "escape" then love.event.quit() end end
_conf.lua
function love.conf(t) t.window.width = 640 t.window.height = 480 t.window.title = "Draw polygon as triangle" t.window.fullscreen = false -- t.window.fullscreentype = "exclusive" end
凹多角形の場合、三角形に分割して描画できていることが分かる。
[ ツッコむ ]
以上です。