mieki256's diary

2021/06/25(金) [n年前の日記]

#1 [love2d] love2dで点と凹多角形の内外判定

#1 [love2d] love2dで点と凹多角形の内外判定

#2 [windows] Windows11が発表されたらしい

#1 [prog] Godot Engine を起動して眺めてる

#1 [nitijyou] 少し調べ物をしてる

#1 [zatta] 昔のゲームの動画を眺めてたり

#1 [blender] blenderのパーティクルでビルボードを並べられるか実験

#1 [pc][ubuntu] 200円ケース機でUSBメモリにインストールしたLubuntuを起動しようと実験

#2 [nitijyou] Amazonから色々届いた

#3 [anime] 精霊の守り人アニメ版はやっぱり凄いと思う

#1 [python] wxPythonで画像表示とかドラッグ移動とか勉強中

#2 [prog] Atomエディタを再インストール

#3 [emacs] NTEmacsの設定を見直し

#1 [dxruby] DXRubyでラスタースクロールを使ったレースゲームの画面を再現できないか実験してみたり

#1 [nitijyou] 自宅サーバ止めてました

#2 [ruby] RSenseがサービス登録できない

#3 [prog] NetBeans 7.3.1をインストール

#4 [emacs] NTEmacsでRubyスクリプトを書いてたり

#5 [nitijyou] 首が痛い

#6 [anime] 刀語、録画失敗してた

#1 [dtm][hns] Dmoinoをまだ勉強中

#2 [nitijyou] 夜になったら寒くなってきた

#1 [nitijyou] Amazonから色々届いた

#2 [cg_tools] blender 2.58をインストールしてみた

#3 [nitijyou] 左脇腹が痛い

#1 [nitijyou] 蚊取り線香をつけておいた部屋で寝ると必ず悪夢を見るのだが

#2 [pc] 結局PCケースを注文してしまった

#1 [nitijyou] Amazonに某ゲームを注文

#2 [zatta][neta] 「レイプレイ」のソレってなんか話がおかしい気がする

#1 [game][neta] 社交ダンスのゲームって作れないかな

#2 [scheme] Schemeをインストール

#3 [scheme][neta] Lisp だの Scheme だのが不人気なのはどれをインストールすれば良さそうなのかさっぱりわからないから

#1 [zatta] 黒板をデジカメで写したらいかんのかな

#2 [anime] アニメにおける黒板

#3 [zatta] _中年童貞…なぜ生まれる？ 「恋愛資本主義」の肥大化

#1 [windows] 7z.exe でフォルダを圧縮するのって

#2 [nitijyou] チラシをhtmlにしてほしいという

#3 [anime] HDDに溜まってたアニメを鑑賞

#3 [zatta] _中年童貞…なぜ生まれる？「恋愛資本主義」の肥大化

#2 [digital] _ZOX ZTO-217 7インチ液晶テレビ税込9999円

◎ HCライブラリを使ってみる。 :

◎ 余談。ポリゴン描画に注意。 :

◎ HCライブラリを使ってみる。 :

◎ 余談。ポリゴン描画に注意。 :

◎ TPM 2.0の問題。 :

◎ UEFIモードの問題。 :

◎ 2021/06/26追記。 :

◎ 手順をメモ。 :

◎ UVマップを作成しておく。 :

◎ パーティクルを追加。 :

◎ マテリアルを追加。 :

◎ テクスチャ画像を追加。 :

◎ テクスチャとマテリアルの設定。 :

◎ パーティクルのビルボードにマテリアル情報を反映。 :

◎ カメラのアニメをつける。 :

◎ レンダリング。 :

◎ 余談。 :

◎ 課題。 :

◎ 参考ページ。 :

◎ USSBメモリへのインストール。 :

◎ USBメモリから起動してみた感想。 :

◎ 今回試したUSBメモリのベンチマークをメモ。 :

◎ HDDを追加し直した。 :

◎ 無線LAN子機を変えてみた。 :

◎ sshでアクセスしてみたら結構反応が速い。 :

◎ インストールしたパッケージ。 :

◎ コメント行の見た目を変更。 :

◎ キー割り当てを変更。 :

◎ Scriptの修正。 :

◎ HTML5のaudioタグを貼り付けられるか実験。 :

◎ 昔を思い出したり。 :

◎ 2017/03/19追記。 :

◎ MIT/GNU Schemeをインストールしてみたり :

◎ _Scheme 入門 1. Scheme 処理系のインストール :

◎ xyzzyのscheme-modeで使えるように設定する方法が分からない。 :

◎ Gaucheも気になるのだけど。 :

◎ 何のために黒板に字を書いて授業をするんだろう。 :

◎ 黒板をPCの画面と捉えると、 :

◎ _無重力実験とアニメについて:コラム：講義方法に普遍性はない、と思う（黒板をノートへ書くことに意義はあるか） :

◎ _アニメ中学理科 ver2.6 :

◎ _電子黒板 | 松下電器 ビジネスサイト :

◎ _学園戦記ムリョウ：オフィシャルサイト - 監督創作メモ :

◎ _DIGITAL DJ : 黒板でストップモーション・アニメ :

◎ _ネギま！？のアニメの黒板ネタに関しての考察 :

この記事へのツッコミ

◎ _電子黒板 | 松下電器ビジネスサイト :

love2d を使って、点と凹多角形の内外判定を試してみた。環境は Windows10 x64 20H2 + love2d 11.3。

点と凸多角形の内外判定は、先日試してみたのだけど。

_love2dで凸多角形の内外判定

凹多角形との判定はしてなかったので、できるかな、どうかなと。

ググってみたら以下の解説ページが参考になった。ありがたや。

_点と凹多角形の内外判定を行う - e.blog
_【第2回】点の多角形に対する内外判定｜【技業LOG】技術者が紹介するNTTPCのテクノロジー｜【公式】NTTPC
_ある点と多角形の内外判定 - Qiita
_多角形の内外判定（javascriptでの実装を添えて） - 加具留矢流余

なんでも、2つのアルゴリズムがあるそうで…。

Crossing Number Algorithm : 点から水平に伸びる線と多角形の交差数を数える。
Winding Number Algorithm : 点から多角形の頂点を見て角度の合計を数える。

自分も大学時代にこの手のアルゴリズムを試したけど、その際は Crossing 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

とりあえず、これで凹多角形との内外判定もできそうだなと…。

その後ググっていたら、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 する。

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

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

凹多角形の場合、三角形に分割して描画できていることが分かる。

Prev - 2021/09 - Next