※ 引述《luckychild (兌現承諾)》之銘言：
: 一個3D空間有很多具有不同幾何形狀的物體會持續生成.
: 我想要知道某一瞬間各個粒子間是否互相重疊.
: 所以我應該先取得特定時刻每個物體特定點的座標.這些特定點足以標定物體的位置.
: 譬如圓心或長桿物的兩端點.
: 我需要知道物體有哪些鄰居然後做一些計算判斷是否重疊.
: 像蒐集很多物體的資料並判斷哪些是鄰居這件事有沒有什麼好的方法可以達成?
用 grid。
原理是把空間切割成許多小方格，每個方格都記錄該方格中包含了哪些物體。
這麼一來要判斷有哪些鄰居，只要去查詢鄰近的方格內有哪些物體即可。
方格的大小必須約略大於物體的平均大小，這樣會比較有效率。
然而當物體的大小差異很大時，最好使用階層性的資料結構 (ex. adaptive grid)
會比固定大小的方格切割法好一點。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 219.87.151.2