Z order (also known as Morton coding) is a very interesting, but also much under-used space filling fractal curve. It is similar to Hilbert's curve, but is easier to use in practice.
(note: I were referring to it simply as variation of Hilbert curve before I found that wiki page) This article describes novel approach to collision detection (between dynamic objects) by using Morton order. Described method runs in O(n*log(n)) where n is number of objects to be checked.
The advantages of Morton order collision detection over plain octree include elegance and simplicity of implementation, high performance, fewer heap allocations and improved cache coherency, lower memory usage, and reliance on well optimized sorting algorithms (you can do it in parallel on multicore by using some available parallelized sort implementation). This method is used in my videogame '
The Polynomial'.
Morton coordinates:
The Morton encoded coordinate (later, simply Morton coordinate) in 3 dimensions is given by interlacing X Y Z coordinate's bits as xyzxyzxyz... .
Each 3 consecutive bits of Morton coordinate correspond to cell choice in octree, and each incomplete sequence, such as xyzxyzxyz??????... (where ? bits can take any value for locations within cell) corresponds to volume of octree cell.
Sorting objects by Morton-encoded coordinate allows to identify overlapping objects or locate proximate objects in logarithmic time using binary search.
High level outline of the algorithm:
- Each object being tested is converted to a list of bounding octree cells. An octree cell struct contains collision object ID, Morton-encoded coordinate of the lowest corner of the box, and octree level (e.g. level 0 means sides of length 1, level 4 means sides of length 16). Those cells are appended to the array of cells.
- Array of cells is sorted by Morton-encoded coordinate.
- Array of cells is traversed, overlapping cells are identified, and pairs of object IDs are stored (each pair is made to have first element smaller than second, so that same pairs are equal)
- Pairs of object IDs are sorted (using std::sort) and made unique (using std::unique)
- Potentially overlapping objects are called to preform their own fine grained collision detection and response, for example, a bullet may raytrace the player to test if bullet path goes through the player (that topic is outside scope of this article)
Easy improvements:
Efficient collision detection against static objects which are pre-sorted into separate array.
Persistent cells, 'dirty' flags, use of sorting algorithms that are efficient on partially sorted arrays.
Internal references between cells, for a full octree structure.
Interface to query the sorted array for elements overlapping given cell (in logarithmic time, using binary search to progressively locate overlapping cells).
Specifics:
Morton-encoding using lookup table:
int bit_interlace_table[2048];
class ztree_initializer{
public:
ztree_initializer(){
for(int i=0;i<2048;++i){
int v=0;
for(int j=0;j<11;++j){
v|=((i>>j)&1)<<(j*3);
}
bit_interlace_table[i]=v;
}
}
};
static ztree_initializer initializer;
int64_t BitInterlace_11(int x, int y, int z){
x&=2047;
y&=2047;
z&=2047;
return (((int64_t(bit_interlace_table[z])<<1)|bit_interlace_table[y])<<1)|bit_interlace_table[x];
}
#ifdef BUILDTYPE_PROFILE
int64_t BitInterlace_21(int x, int y, int z) __attribute__((noinline));
#endif
int64_t BitInterlace_21(int x, int y, int z){
return (BitInterlace_11(x>>11,y>>11,z>>11)<<33)|BitInterlace_11(x,y,z);
}
void BitDeinterlace(int64_t v, int &x, int &y, int &z){
x=0;
y=0;
z=0;
int i=0;
while(v){
x|=(v&1)<<i;
y|=(v&2)<<i;
z|=(v&4)<<i;
v>>=3;
i++;
}
y>>=1;
z>>=2;
}
Morton-encoded cell:
struct Entry{
/// start<=a<end
int64_t start;
unsigned contained_by:24;
unsigned size:8;
int object_id;
inline int64_t range_end() const{
return start+(int64_t(1)<<(size*3));
}
inline bool operator<(const Entry &other) const{/// ordering: z order, plus on equal sizes largest first
return start==other.start? size>other.size: start<other.start;
}
};
Conversion of axis aligned bounding box into Morton-encoded cell:
void AddAABB_raw(std::vector<CollisionDetector::Entry> &entries, int id, const math3::Vec3<int> &pos, const math3::Vec3<int> &size){
int d=size.x;
if(d<size.y)d=size.y;
if(d<size.z)d=size.z;
int sz2;/// cell size, power of 2.
int szp;/// actual power of 2
for(sz2=1, szp=0; sz2<d; sz2<<=1, szp++);
int lx=pos.x;
int ly=pos.y;
int lz=pos.z;
if(lx<0)lx=0;
if(ly<0)ly=0;
if(lz<0)lz=0;
int hx=pos.x+size.x;
int hy=pos.y+size.y;
int hz=pos.z+size.z;
if(hx>=CollisionDetector::resolution)hx=CollisionDetector::resolution-1;
if(hy>=CollisionDetector::resolution)hy=CollisionDetector::resolution-1;
if(hz>=CollisionDetector::resolution)hz=CollisionDetector::resolution-1;
int mask=sz2-1;
lx&=~mask;
ly&=~mask;
lz&=~mask;
hx|=mask;
hy|=mask;
hz|=mask;
int iterations=0;
if(szp>10){
//std::cout<<"wtf"<<std::endl;
}
for(int iz=lz; iz<=hz ; iz+=sz2){
for(int iy=ly; iy<=hy; iy+=sz2){
for(int ix=lx; ix<=hx; ix+=sz2){
///should be max. 8 iterations.
CollisionDetector::Entry entry;
entry.start=BitInterlace_21(ix, iy, iz);
entry.size=szp;
entry.contained_by=invalid_contained_by;
entry.object_id=id;
entries.push_back(entry);
iterations++;
}
}
}
#ifdef BUILDTYPE_DEBUG
if(iterations>8){
std::cout<<"too many iterations"<<std::endl;
}
#endif
}
Identification of overlapping cells:
void CollisionDetector::Process(Collisions &result){
std::sort(entries.begin(),entries.end());
for(int i=0;i<entries.size();++i){
int j=i+1;
int64_t range_end=entries[i].range_end();
while(j<entries.size() && entries[j].start<range_end){
Entry &a=entries[i];
Entry &b=entries[j];
if(a.object_id==b.object_id){
logger<<"CollisionDetector bug"<<std::endl;
}
/// uncomment this line to disable reporting of collision for identical boxes
//if(a.size>b.size)
b.contained_by=i;
result.AppendCollision(Collisions::CollisionID(a.object_id,b.object_id));
j++;
}
}
result.raw_collision_count=result.ids.size();
}
Example source code (Note: this is NOT a library, and this is NOT a piece of code which you can just cut n paste into your software. Its not something you download and then configure&&make. It is an example provided to help explain the method presented on this page)
