Collision detection

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:

### 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:

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)

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'.

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.

- 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)

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).

Morton-encoded cell:intbit_interlace_table[2048];classztree_initializer{public: ztree_initializer(){for(inti=0;i<2048;++i){intv=0;for(intj=0;j<11;++j){v|=((i>>j)&1)<<(j*3);}bit_interlace_table[i]=v;}}};staticztree_initializer initializer;int64_t BitInterlace_11(intx,inty,intz){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(intx,inty,intz)__attribute__((noinline));#endif int64_t BitInterlace_21(intx,inty,intz){return(BitInterlace_11(x>>11,y>>11,z>>11)<<33)|BitInterlace_11(x,y,z);}voidBitDeinterlace(int64_t v,int&x,int&y,int&z){x=0;y=0;z=0;inti=0;while(v){x|=(v&1)<<i;y|=(v&2)<<i;z|=(v&4)<<i;v>>=3;i++;}y>>=1;z>>=2;}

Conversion of axis aligned bounding box into Morton-encoded cell:structEntry{/// start<=a<endint64_t start;unsignedcontained_by:24;unsignedsize:8;intobject_id;inlineint64_t range_end()const{returnstart+(int64_t(1)<<(size*3));}inlinebooloperator<(constEntry &other)const{/// ordering: z order, plus on equal sizes largest firstreturnstart==other.start? size>other.size: start<other.start;}};

Identification of overlapping cells:voidAddAABB_raw(std::vector<CollisionDetector::Entry> &entries,intid,constmath3::Vec3<int> &pos,constmath3::Vec3<int> &size){intd=size.x;if(d<size.y)d=size.y;if(d<size.z)d=size.z;intsz2;/// cell size, power of 2.intszp;/// actual power of 2for(sz2=1,szp=0;sz2<d;sz2<<=1,szp++);intlx=pos.x;intly=pos.y;intlz=pos.z;if(lx<0)lx=0;if(ly<0)ly=0;if(lz<0)lz=0;inthx=pos.x+size.x;inthy=pos.y+size.y;inthz=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;intmask=sz2-1;lx&=~mask;ly&=~mask;lz&=~mask;hx|=mask;hy|=mask;hz|=mask;intiterations=0;if(szp>10){//std::cout<<"wtf"<<std::endl;}for(intiz=lz;iz<=hz;iz+=sz2){for(intiy=ly;iy<=hy;iy+=sz2){for(intix=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_DEBUGif(iterations>8){std::cout<<"too many iterations"<<std::endl;}#endif}

voidCollisionDetector::Process(Collisions &result){std::sort(entries.begin(),entries.end());for(inti=0;i<entries.size();++i){intj=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)

(C) 2004..2013 Dmytry Lavrov.

Want to say something or ask some question? Contact: