mieki256's diary



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

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

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

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

_love2dで凸多角形の内外判定

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

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

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

なんでも、2つのアルゴリズムがあるそうで…。 自分も大学時代にこの手のアルゴリズムを試したけど、その際は Crossing Number Algorithm を使った記憶があるなと。

今回は、角度の合計を調べる Winding Number Algorithm を試してみたい。JavaScript で実装した以下の版をそのまま参考にさせてもらって、Lua で書き直してみる。

_多角形の内外判定(javascriptでの実装を添えて) - 加具留矢流余

こんな感じになった。

concave_poly_collision_ss.gif

ソースは以下。

_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 する。
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_collision_ss.gif

ソースは以下。今回は、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" のほうは形がおかしくなるようで…。

draw_polygon_ss.png

ソースは以下。

_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

draw_polygon_tri_ss.png

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

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

「次期WindowsはWindows11になるよ」と発表されたらしい…。

自分のメインPC(Windows10 x64 20H2、AMD Ryzen 7 1700 + GIGABYTE B450M S2H rev. 1.x) で、Winodws11にアップグレード可能かどうかをチェックできるツールをインストールして動かしてみたけれど。

_Microsoft、Windows 11互換性チェックプログラムを公開 - PC Watch

「お前のPCはアップグレードできねえよ」と表示されてしまった…。このツール、一体何が原因でアップグレードできないのか、そのあたりの情報を一切表示してくれないあたりがなんというか…。

TPM 2.0の問題。 :

Windows11導入時に要求される条件を眺めてみたら、TPM 2.0 が必要、てなあたりが気になった。

Windows10でデバイスマネージャを表示して(スタートボタンを右クリック → デバイスマネージャ)、「セキュリティデバイス」内に「トラステッド プラットフォーム モジュール 2.0」があれば対応しているっぽい。自分のPCには無かった…。

ただ、Ryzen 7 1700 でも、有効にできる可能性があるらしい。M/BのBIOS設定画面に入って(電源投入直後にDELキーを叩くとBIOS設定画面に入れる)、設定を確認してみたら、「周辺機器」の中で、「AMD CPU fTPM」なる項目が無効になっていた。有効にしてみたところ、Windows10起動後のデバイスマネージャで、「トラステッド プラットフォーム モジュール 2.0」が出現してくれた。

しかし、TPM 2.0 を有効にしたはずが、相変わらず「お前のPCはアップグレードできねえよ」と言われる。

UEFIモードの問題。 :

Windows11は、BIOSモードが「UEFI」じゃないと導入できないらしい。

BIOSモードは、msinfo32(システム情報) で確認できる。msinfo32 を起動 → 「BIOSモード」。自分のPCは「レガシ」になってた…。更に、「セキュアブートの状態」が「サポートされていません」になっていた。

BIOSモードを Legacy(レガシ)から UEFIにするためには、起動ディスクが MBR ではなく GPT になっていないといかんそうで。

起動ディスクの状態は、ディスクの管理で確認できる。スタートボタンを右クリック → ディスクの管理。「ディスク0」を右クリック → プロパティ → ボリューム → パーティションのスタイル。自分のPCは「マスターブートレコード(MBR)」になってた…。

MBR を GPT にする方法はあるらしい。MBR2GPT.EXE を使うのだとか。

_MBR2GPTでブートセクタをMBRからGPTに変換してレガシBIOSをUEFIモードに変換する - Windows 10
_Windows 10 64bitがインストールされているSSDをLegacyからUEFIに変換してみた | 銀メモ -SilveryMemo-
_今後のことを考えて、MBRをGPTに変換。 - もうやんの自作パソコンへの道

でも、GPT にした場合、HDD関連ツールは対応できるのだろうか…。例えば、HDD/SSDの調子が悪くなってファイルを救出したい場合、その手のツールがGPTに未対応だったりすると困りそう…。

M/BのBIOS設定で、UEFIモードを有効にする方法も分からない。HDD/SSDがGPTなら、自動でUEFIモードになるのだろうか。それとも、どうにかして手動で設定しないといかんのだろうか。

そのあたりよく分からんので、もうちょっと調べてから、GPTに変換するかどうかを検討しよう…。

2021/06/26追記。 :

そもそも、Windows11が使えるCPU一覧に、Ryzen 1000番台は入ってなかった。酷い。なんだかそこで弾いてそうだな…。

以上、1 日分です。

過去ログ表示

Prev - 2021/06 - Next
1 2 3 4 5
6 7 8 9 10 11 12
13 14 15 16 17 18 19
20 21 22 23 24 25 26
27 28 29 30

カテゴリで表示

検索機能は Namazu for hns で提供されています。(詳細指定/ヘルプ


注意: 現在使用の日記自動生成システムは Version 2.19.6 です。
公開されている日記自動生成システムは Version 2.19.5 です。

Powered by hns-2.19.6, HyperNikkiSystem Project