#author("2018-06-23T01:59:11+09:00","","")
*八分木 [#r39dcf25]
[[モートン番号テーブル化]]を利用して当たり判定用の八分木モジュールを作ってみました。~
内部で自動的にオクツリーの分割レベルを調整しています。~
二次元や四次元への変更も比較的簡単にできると思います。~

☆★ このモジュールを利用した当たり判定の仕方 ☆★~

まずオクツリーを生成する。~
あとはフレーム毎に~

１.オクツリーに全てのオブジェクトを登録する。~
２.オクツリーから衝突候補リストを取得する。~
３.衝突候補リストを元に詳細な当たり判定を行う。~

を繰り返すだけです。~

**ソース [#wc1634e4]
	//--"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
**八分木のメモリ占有量 [#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       |非対応  |非対応        |