検索
AND検索
OR検索
トップ
|
リロード
|
新規
|
一覧
|
単語検索
|
最終更新
|
ヘルプ
モートン番号テーブル化 / 八分木 をテンプレートにして作成
メニュー
簡易掲示板
LINK集
y.tackの公式BBSブックマーク
practice room
?
最新の20件
2022-10-09
多角形の内外判定
2021-05-19
RecentDeleted
2018-08-01
FrontPage
文字列型変数管理サブルーチン
GAME作成システム
2018-07-31
double型変数管理サブルーチン
int型変数管理サブルーチン
2018-07-21
GUIとメイン分割処理。たたき台2
2018-07-11
memo
NO_579_sample
GUIとメイン分割処理。たたき台
2018-06-28
NO_714
NO_712
NO_706
NO_705
NO_704
NO_703
NO_702
2018-06-23
Shift_JIS
モートン番号テーブル化 / 八分木
total
0
today
0
yesterday
0
now
2
Menu
Total:0/Today:0
開始行:
*八分木 [#r39dcf25]
[[モートン番号テーブル化]]を利用して当たり判定用の八分木...
内部で自動的にオクツリーの分割レベルを調整しています。~
二次元や四次元への変更も比較的簡単にできると思います。~
☆★ このモジュールを利用した当たり判定の仕方 ☆★~
まずオクツリーを生成する。~
あとはフレーム毎に~
1.オクツリーに全てのオブジェクトを登録する。~
2.オクツリーから衝突候補リストを取得する。~
3.衝突候補リストを元に詳細な当たり判定を行う。~
を繰り返すだけです。~
**ソース [#wc1634e4]
//--"Octree.hsp"
#ifndef Octree
#include "MortonNo.hsp" ; ←モートン番号モジュールをイン...
//八分木モジュール
#module Octree data, dn, EnabledSpace, en , _EnabledSpac...
#const MAXPARTITIONLEVEL 6 ; (0〜8)
#const DEFPARTITIONLEVEL 3 ; (0〜↑の値まで)
#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, dou...
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, ...
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 =...
if p2 < p5{ areay = p2: areasy = p5 - p2} else{ areay =...
if p3 < p6{ areaz = p3: areasz = p6 - p3} else{ areaz =...
return
#modfunc AddOctree int ID, double p1, double p2, double ...
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...
lpoke data(N), index + 4, limit(y, 0, yn) | abs(yn - y...
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 "左クリックで球一時停止 右クリックでカメラ一時停止...
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...
}
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(cn...
; ┃ ┗━━━━━━━━┳━━━━━━━━━━┛┗━━━━━━━━┳━━━━...
; ID 占有範囲起点 ...
loop
//八分木からリスト取得
判定数 = OctreeListing(oct, list)
bp += d3timer()
np = -d3timer()
repeat 判定数
ID1 = wpeek(list(cnt), 2) ; 上位2バイトと
ID2 = wpeek(list(cnt) ) ; 下位2バイトに衝突可能性あ...
あたり判定
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) & ...
d3circle px(cnt), py(cnt), pz(cnt), r(cnt)
col(cnt) = $FFFFFF
loop
//情報描画
pos 0,0: color 0, 255
if 八分木{
mes "八分木で判定中 : 分割レベル = " + GetOctreeLevel(...
}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),...
col(ID1) = $FF0000
col(ID2) = $FF0000
衝突+
}
return
**八分木のメモリ占有量 [#wc1634e4]
|分割レベル|空間数 |占有メモリ(KB)|
| 0 |1 | 0 |
| 1 |15 | 1 |
| 2 |127 | 8 |
| 3 |1023 | 64 |
| 4 |8191 | 552 |
| 5 |65535 | 4096 |
| 6 |524287 | 32768 |
| 7 |4194303 | 262144 |
| 8 |33554431|2097152 |
| 9 |非対応 |非対応 |
終了行:
*八分木 [#r39dcf25]
[[モートン番号テーブル化]]を利用して当たり判定用の八分木...
内部で自動的にオクツリーの分割レベルを調整しています。~
二次元や四次元への変更も比較的簡単にできると思います。~
☆★ このモジュールを利用した当たり判定の仕方 ☆★~
まずオクツリーを生成する。~
あとはフレーム毎に~
1.オクツリーに全てのオブジェクトを登録する。~
2.オクツリーから衝突候補リストを取得する。~
3.衝突候補リストを元に詳細な当たり判定を行う。~
を繰り返すだけです。~
**ソース [#wc1634e4]
//--"Octree.hsp"
#ifndef Octree
#include "MortonNo.hsp" ; ←モートン番号モジュールをイン...
//八分木モジュール
#module Octree data, dn, EnabledSpace, en , _EnabledSpac...
#const MAXPARTITIONLEVEL 6 ; (0〜8)
#const DEFPARTITIONLEVEL 3 ; (0〜↑の値まで)
#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, dou...
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, ...
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 =...
if p2 < p5{ areay = p2: areasy = p5 - p2} else{ areay =...
if p3 < p6{ areaz = p3: areasz = p6 - p3} else{ areaz =...
return
#modfunc AddOctree int ID, double p1, double p2, double ...
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...
lpoke data(N), index + 4, limit(y, 0, yn) | abs(yn - y...
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 "左クリックで球一時停止 右クリックでカメラ一時停止...
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...
}
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(cn...
; ┃ ┗━━━━━━━━┳━━━━━━━━━━┛┗━━━━━━━━┳━━━━...
; ID 占有範囲起点 ...
loop
//八分木からリスト取得
判定数 = OctreeListing(oct, list)
bp += d3timer()
np = -d3timer()
repeat 判定数
ID1 = wpeek(list(cnt), 2) ; 上位2バイトと
ID2 = wpeek(list(cnt) ) ; 下位2バイトに衝突可能性あ...
あたり判定
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) & ...
d3circle px(cnt), py(cnt), pz(cnt), r(cnt)
col(cnt) = $FFFFFF
loop
//情報描画
pos 0,0: color 0, 255
if 八分木{
mes "八分木で判定中 : 分割レベル = " + GetOctreeLevel(...
}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),...
col(ID1) = $FF0000
col(ID2) = $FF0000
衝突+
}
return
**八分木のメモリ占有量 [#wc1634e4]
|分割レベル|空間数 |占有メモリ(KB)|
| 0 |1 | 0 |
| 1 |15 | 1 |
| 2 |127 | 8 |
| 3 |1023 | 64 |
| 4 |8191 | 552 |
| 5 |65535 | 4096 |
| 6 |524287 | 32768 |
| 7 |4194303 | 262144 |
| 8 |33554431|2097152 |
| 9 |非対応 |非対応 |
ページ名: