HSPで3D衝突判定を高速化！モートン番号を使ったOctree（八分木）モジュール
こんにちは。HSPで3Dゲームやシミュレーションを作っている皆さん、今日はOctree（八分木）を使った高速衝突判定のテクニックをご紹介します。3D空間で大量のオブジェクト（例: 球やモデル）が存在する場合、すべての組み合わせをチェックする総当たり判定では計算量がO(N²)となり、数百個を超えるとすぐに重くなってしまいます。そこで有効なのが空間分割です。中でもOctreeは、空間を再帰的に8分割していく木構造で、衝突の可能性があるペアだけを効率的に抽出できます。このコードは、以前紹介したモートン番号テーブルを基盤に、3DのOctreeをHSPで実装したモジュールです。特徴は以下の通りです。モートン番号（Z-order曲線）で空間を1次元化し、範囲検索を高速化
大きなオブジェクト（複数セルを占有するもの）にも対応
使用状況に応じて自動的に分割レベルを調整（葉空間の占有率で上下）
ブロードフェーズ（可能性のあるペア抽出）とナローフェーズ（精密衝突判定）を分離
//--"Octree.hsp"
#ifndef Octree
#include "MortonNo.hsp" ; ←モートン番号モジュールをインクルードしてください。
//八分木モジュール
#module Octree data, dn, EnabledSpace, en , _EnabledSpace, _en, level, MaxLevel, LeafSpace, GridMax, table, areax, areay, areaz, areasx, areasy, areasz, divsizex, divsizey, divsizez, count
#const MAXPARTITIONLEVEL 6 ; (０～８)
#const DEFPARTITIONLEVEL 3 ; (０～↑の値まで)
#const FRAMES 60 ; 何フレームごとに分割レベル調整を行うか
#const DOWNLEVEL 30 ; 有効空間のうち葉空間が占める割合が何パーセント以下なら分割レベルを下げるか
#const UPLEVEL 57 ; 有効空間のうち葉空間が占める割合が何パーセント以上なら分割レベルを上げるか
#const DIMENSIONALITY 3 ; 次元数
#const DATASIZE 2 + DIMENSIONALITY * 2
#modinit double p1, double p2, double p3, double p4, double p5, double p6
MaxLevel = -1
level = DEFPARTITIONLEVEL
gosub *SetArea
*LevelChange
gosub *SetDivSize
LeafSpace = 1 << level * DIMENSIONALITY ; この数値未満は子を持つ空間、この数値以上は葉空間
MakeMortonNoTable DIMENSIONALITY, level, table
if level > MaxLevel{
MaxLevel = level
sdim data,, LeafSpace << 1
dim dn, LeafSpace << 1
}
return
#modfunc SetOctreeArea double p1, double p2, double p3, double p4, double p5, double p6
gosub *SetArea
*SetDivSize
GridMax = 1 << level
divsizex = areasx / GridMax
divsizey = areasy / GridMax
divsizez = areasz / GridMax
GridMax-
return
*SetArea
if p1 < p4{ areax = p1: areasx = p4 - p1} else{ areax = p4: areasx = p1 - p4}
if p2 < p5{ areay = p2: areasy = p5 - p2} else{ areay = p5: areasy = p2 - p5}
if p3 < p6{ areaz = p3: areasz = p6 - p3} else{ areaz = p6: areasz = p3 - p6}
return
#modfunc AddOctree int ID, double p1, double p2, double p3, double p4, double p5, double p6
x = limit((p1 - areax) / divsizex, 0, GridMax)
y = limit((p2 - areay) / divsizey, 0, GridMax)
z = limit((p3 - areaz) / divsizez, 0, GridMax)
xn = limit((p4 - areax) / divsizex, 0, GridMax)
yn = limit((p5 - areay) / divsizey, 0, GridMax)
zn = limit((p6 - areaz) / divsizez, 0, GridMax)
N = GetLinerNo3d(table, x, y, z, xn, yn, zn) ; オブジェクトが所属すべき空間番号
index = dn(N) * DATASIZE
memexpand data(N), index + DATASIZE
if N < LeafSpace{
lpoke data(N), index, ID | limit(x, 0, xn) << 16 | abs(xn - x) + 1 << 24
lpoke data(N), index + 4, limit(y, 0, yn) | abs(yn - y) + 1 << 8 | limit(z, 0, zn) << 16 | abs(zn - z) + 1 << 24
if dn(N): else: EnabledSpace(en) = N: en+
}else{
wpoke data(N), index, ID
if dn(N): else: _EnabledSpace(_en) = N: _en+
}
dn(N)+
return
#modcfunc OctreeListing array list
lpoke ln
//子空間を持つすべての有効な空間に対して ( 子空間との組み合わせと空間内総当たり )
repeat en
dup S, EnabledSpace(cnt) ; この空間に対して作業開始
dup ndata, data(S)
dup NN, dn(S)
poke UnScanned, S ; 自空間は走査済みとする
lpoke index
//現在空間の全てのオブジェクトに対して
repeat NN, 1
//オブジェクト情報取得
ID = wpeek(ndata, index) << 16
x = peek(ndata, index + 2)
xn = peek(ndata, index + 3)
y = peek(ndata, index + 4)
yn = peek(ndata, index + 5)
//オブジェクトが占有する全ての葉空間に対して
repeat peek(ndata, index + 7), peek(ndata, index + 6)
i = cnt
repeat yn, y
dup t, table(0, cnt, i)
repeat xn, x
N = t(cnt) ; 葉空間番号
*@ //自空間に向かってループ開始
repeat dn(N)
list(ln) = ID | wpeek(data(N), cnt * DATASIZE): ln+
loop
N >> 1 ; 親空間に移動
if peek(UnScanned, N){ ; 未走査なら
poke UnScanned, N ; 空間を走査済みにして
Checked(cn) = N: cn+ ; 走査済みにした空間を記録して
goto *@b ; ループ
}
loop
loop
loop
//次のオブジェクトのために記録をもとに走査情報クリア
repeat cn
poke UnScanned, Checked(cnt), 1
loop
lpoke cn
//現在空間内オブジェクト同士
repeat NN - cnt, cnt
list(ln) = ID | wpeek(ndata, cnt * DATASIZE): ln+
loop
index += DATASIZE ; 次のオブジェクトへ
loop
poke UnScanned, S, 1 ; 次の空間のために自空間を未走査に戻す
loop
repeat en
lpoke dn(EnabledSpace(cnt))
loop
//全ての有効な葉空間に対して ( 空間内総当たりのみ )
repeat _en
dup ndata, data(_EnabledSpace(cnt))
dup NN, dn(_EnabledSpace(cnt))
repeat NN - 1, 1
ID = wpeek(ndata, cnt * DATASIZE - DATASIZE) << 16
repeat NN - cnt, cnt
list(ln) = ID | wpeek(ndata, cnt * DATASIZE): ln+
loop
loop
lpoke NN
loop
//分割レベル調整
if count \ FRAMES: else{
if _en: else: if en: else: return 0
rate = _en * 100 / (en + _en)
if rate >= UPLEVEL{
if level < MAXPARTITIONLEVEL{
level+
gosub *LevelChange
}
}else: if rate <= DOWNLEVEL{
level-
gosub *LevelChange
}
}
lpoke en
lpoke _en
count+
return ln
#modcfunc GetOctreeLevel
return level
#deffunc InitOctree
i = 1 << MAXPARTITIONLEVEL * DIMENSIONALITY
sdim UnScanned, i
memset UnScanned, 1, i - 1, 1
return
#global
InitOctree
#endif
//--"Octree.hsp" --End Of File
//八分木のテスト
#include "d3m.hsp"
gsel , 1
//対象範囲
sx = -10000.
sy = -10000.
sz = -10000.
ex = 10000.
ey = 10000.
ez = 10000.
//八分木作成
newmod oct, octree, sx, sy, sz, ex, ey, ez
N = 300 ; 球の数
repeat N ; 球生成
r(cnt) = 350. ; 球の半径
px(cnt) = 0. + rnd(18000) - 9000
py(cnt) = 0. + rnd(18000) - 9000
pz(cnt) = 0. + rnd(18000) - 9000
spx(cnt) = (1. + 1./ (rnd(1000) + 1)) * (rnd(2) * 2 - 1)
spy(cnt) = (1. + 1./ (rnd(1000) + 1)) * (rnd(2) * 2 - 1)
spz(cnt) = (1. + 1./ (rnd(1000) + 1)) * (rnd(2) * 2 - 1)
col(cnt) = $FFFFFF
loop
カメラ移動 = 1
球運動 = 1
八分木 = 1
title "左クリックで球一時停止 右クリックでカメラ一時停止 Enterで判定モード変更"
pt = -d3timer()
*main
nt = limit(pt + d3timer(), 0, 100)
pt = -d3timer()
stick key
if key & 512: カメラ移動 ^ 1
if key & 256: 球運動 ^ 1
if key & 32 : 八分木 ^ 1
if カメラ移動{
count += nt
d3setcam cos(double(count) / 6500) * 20000, sin(double(count) / 6600) * 20000, cos(double(count) / 6700) * 20000
}
if 球運動{
repeat N
dup dr, r(cnt)
dup dpx, px(cnt)
dup dpy, py(cnt)
dup dpz, pz(cnt)
dpx += spx(cnt) * nt
dpy += spy(cnt) * nt
dpz += spz(cnt) * nt
//壁跳ね返り処理
if dpx + dr > ex{ spx(cnt) = -absf(spx(cnt))
}else:if dpx - dr < sx: spx(cnt) = absf(spx(cnt))
if dpy + dr > ey{ spy(cnt) = -absf(spy(cnt))
}else:if dpy - dr < sy: spy(cnt) = absf(spy(cnt))
if dpz + dr > ez{ spz(cnt) = -absf(spz(cnt))
}else:if dpz - dr < sz: spz(cnt) = absf(spz(cnt))
loop
}
if 八分木{
bp = -d3timer()
repeat N
dup dr, r(cnt)
//八分木にオブジェクト登録
AddOctree oct, cnt, px(cnt) - dr, py(cnt) - dr, pz(cnt) - dr, px(cnt) + dr, py(cnt) + dr, pz(cnt) + dr
; ┃ ┗━━━━━━━━┳━━━━━━━━━━┛┗━━━━━━━━┳━━━━━━━━━━┛
; ID 占有範囲起点 占有範囲終点
loop
//八分木からリスト取得
判定数 = OctreeListing(oct, list)
bp += d3timer()
np = -d3timer()
repeat 判定数
ID1 = wpeek(list(cnt), 2) ; 上位2バイトと
ID2 = wpeek(list(cnt) ) ; 下位2バイトに衝突可能性ありのIDペアが入っている
あたり判定
loop
np += d3timer()
}else{
判定数 = N * (N - 1) / 2
bp = 0
np = -d3timer()
repeat N - 1
ID1 = cnt
repeat N - cnt - 1, cnt + 1
ID2 = cnt
あたり判定
loop
loop
np += d3timer()
}
//以下描画処理
color: boxf ; 画面初期化
color $66, $FF, $FF: d3box sx, sy, sz, ex, ey, ez ; エリアボックス描画
//球描画
repeat N
color col(cnt) >> 16, col(cnt) >> 8 & 255, col(cnt) & 255
d3circle px(cnt), py(cnt), pz(cnt), r(cnt)
col(cnt) = $FFFFFF
loop
//情報描画
pos 0,0: color 0, 255
if 八分木{
mes "八分木で判定中 : 分割レベル = " + GetOctreeLevel(oct)
}else{
mes "総当たりで判定中"
}
mes "球の数 = " + N
mes "ブロードフェーズ: " + bp + " ms"
mes "ナローフェーズ: " + np + " ms"
mes "判定回数 = " + 判定数
mes "衝突数 = " + 衝突: 衝突 = 0
mes "FPS = " + d3getfps()
redraw
redraw 2
await 16
goto *main
#deffunc あたり判定
if powf(px(ID1) - px(ID2), 2) + powf(py(ID1) - py(ID2), 2) + powf(pz(ID1) - pz(ID2), 2) <= powf(r(ID1) + r(ID2), 2){
col(ID1) = $FF0000
col(ID2) = $FF0000
衝突+
}
returnポイント解説
自動レベル調整：葉空間の占有率が低いと分割を粗く（高速化）、高いと細かく（精度向上）します。
モートン番号の活用：範囲を占有可能な空間を一気にGetLinerNo3dで取得。
大きなオブジェクトは親ノードに登録され、子空間との組み合わせも効率的に処理。
HSPのような軽量言語でも、こうした最適化で数百〜数千オブジェクトの3D衝突判定がリアルタイムで可能になります。物理エンジンの基盤や、粒子シミュレーション、3Dシューティングゲームなどにぜひ活用してみてください！質問や「もっとオブジェクト増やしてみた」報告など、コメントお待ちしています。楽しいHSPプログラミングを！
AI(Grok)さんにソースコードに寄せて文書を書いてもらいました(2025/12)
コメント