Mostly geometry.

, we discussed collision detection in general and surveyed some techniques for narrow phase collision detection.

In this article we will go into more detail on broad phase collision detection for.

This was a big problem in the 1970’s and early 1980’s in , which resulted in many efficient algorithms and data structures being developed around that period.

Here we survey some approaches to this problem and review a few theoretical results.

A box is a of , so if we want to represent a d-dimensional box, it is enough to represent a tuple of d 1-dimensional intervals.

There are at least two ways to do this: function sweepIntervals(intervals) { var events = [], result = [], active = [] intervals.forEach(function(interval, id) { events.push( { t: interval[0], id: id, create: 1 }, { t: interval[1], id: id, create: 0 }) }) events.sort(function(a, b) { return a.t – b.t || b.create – a.create }) events.forEach(function(ev) { if(ev.create) { active.forEach(function(id) { result.push([ev.id, id]) }) active.push(ev.id) } else active.splice(active.indexOf(ev.id), 1) }) return result } //Assume each box is represented by a list of d intervals //Each interval is of the form [lo,hi] function sweepAndPrune(boxes) { return sweepIntervals(boxes.map(function(box) { return box[0] }).filter(function(pair) { var A = boxes[pair[0]], B = boxes[pair[1]] for(var i=1; i

one can store the active set in an (more on this later),.

If we just store the active set as an array, then this technique is known as sweep-and-prune collision detection.

#### Which is widely used in packages like I-COLLIDE

J.

Cohen, M.

Lin, D.

Manocha, M.

Ponamgi.

#### (1995) “” Symposium on Interactive 3D Graphics W

#### Franklin (1989) “” Proceedings of Auto-Carto //Same convention as above

boxes are list of d intervals // H is the side length for the grid function gridIntersect2D(boxes, H) { var grid = {}, result = [], x = [0,0] boxes.forEach(function(b, id) { for(x[0]=Math.floor(b[0][0]/H); x[0]<=Math.ceil(b[0][1]/H); ++x[0]) for(x[1]=Math.floor(b[1][0]/H); x[1]<=Math.ceil(b[1][1]/H); ++x[1]) { var list = grid[x] if(list) { list.forEach(function(otherId) { var a = boxes[otherId] for(var i=0; i<2; ++i) { var s = Math.max(a[i][0], b[i][0]), t = Math.min(a[i][1], b[i][1]) if(t < s || Math.floor(s/H) !== x[i]) return } result.push([id, otherId]) }) list.push(id) } else grid[x] = [id] } }) return result } Size variation: If the side lengths of the boxes have enormous variability, then we can’t pick just one grid size. Hierarchical grids or are a possible solution here, though it remains difficult to tune parameters like the number of levels. After grids, the second most widely recommended approach to collision detection are partition based tree data structures. Sometimes called “,” partition based data structures recursively split space into smaller regions using trees. Objects are iteratively tested against these trees, and then inserted into the resulting data structure. Function bvhIntersect(boxes) { var tree = createEmptyTree(), result = [] boxes.forEach(function(box, id) { bvhQuery(tree, box).forEach(function(otherBox) { result.push([box, otherBox]) }) bvhInsert(tree, box) }) return result } function bvhQuery(node, box) { if(!node.bounds.intersects(box)) return [] if(isLeaf(node)) return [ node.item ] return node.children.reduce(function(child, result) { return result.concat(bvhQuery(child, box)) }, .

#### []) } : Axis aligned hyperplane

(aka AABB trees, box-trees): Axis aligned boxes.

: Oriented boxes/slabs.

: Balls.

: Hyperplanes.

H.

Samet.

(2006) ““ In the case of all the aforementioned trees these conditions hold.

Furthermore, let us assume that insertion into the tree is “cheap”, that is at most time; then the total complexity of bvhIntersect is in the worst case, B.

Chazelle.

#### (1990) “” Journal of the ACM B

Chazelle.

#### (1988) “” SIAM Journal of Computing Finally

let us look at one particular type of bounding volume hierarchy in detail; specifically the.

Originally invented by Guttmann, R-trees have become widely used in GIS databases due to their low storage overhead and ease of implementation, A.

Guttmann, (1984) “” SIGMOD P.

K.

Agarwal, M de Berg, J.

Gudmundsson, M.

Hammar, H.

J.

Haverkort.

(2002) “” Discrete & Computational Geometry So far none of the approaches we’ve seen have managed to break the barrier in the worst case (with the exception of 1D interval sweeping and a brief digression into Shamos & Hoey’s algorithm).

To the best of my knowledge, all efficient approaches to this problem make some essential use of.

#### Range trees were invented by Bentley in 1979

and they solve the orthogonal range query problem for points in time using space (these results can be improved somewhat using and other more sophisticated techniques).

The first application of range tree like ideas to rectangle intersections was done by Bentley and Wood, J.

Bentley, D.

Wood.

#### (1980) “” IEEE Transactions on Computers In this paper they

introduced the concept of a , which solves the problem of interval stabbing queries.

One can improve the space complexity of their result in 2D using an instead, giving a algorithm for detecting rectangle intersections.

These results were generalized to higher dimensions and improved by Edelsbrunner in a series of papers, H.

Edelsbrunner.

## (1983) “” International Journal of Computer Math H

Edelsbrunner.

### (1983) “” International Journal of Computer Math A

Zomorodian, H.

Edelsbrunner (2000) “” SoCG we will look at some actual performance data from real benchmarks for each of these approaches.

Stay tuned.

This entry was posted in , , ,.

Bookmark the permalink.

8 Responses to Collision detection (part 2): Box intersection.

January 18, 2015 at 9:50 pm Great article, thanks.

I would love to see you tie this back to the real world too – What algorithms do popular physics engines use these days (Bullet, Havok, etc).

#### Reply mikolalysenko January 18

2015 at 9:52 pm I plan to cover some of this in the next part.

Reply.

Andrew January 19, 2015 at 9:49 am I know that bullet has at least an AABB tree and an 3d incremental sweep and prune.

The AABB tree is the default/recommnded.

When using the AABB tree, two trees are actually used; one for static objects and one for dynamic.

http://www.bulletphysics.org/mediawiki-1.5.8/index.php?title=Broadphase Reply jelle January 19, 2015 at 6:42 pm interesting post… AABB trees are often used for broadphase collision detection.

For the narrowphase, when working on meshes, the GJK [1] algorithm is often utilized.

I use collision detection for robotics applications and use the FCL [2] library.

Works great, and there’s no need to pre-process / partition meshes to a number of convex meshes.

[1] http://en.wikipedia.org/wiki/Gilbert%E2%80%93Johnson%E2%80%93Keerthi_distance_algorithm [2] https://github.com/flexible-collision-library/fcl.

jonas29ach January 19, 2015 at 2:36 pm Really interesting article, thank you.

I have recently hacked together a 2d physics engine in javascript and did a very rough comparison between sweep & prune and uniform grid (hash and array backed) at least in my simple test case the sweep & prune was as fast as the grid based approaches while significantly lower in complexity and overhead.

It helps that at least in a side scrolling view objects are usually distributed nicely along one axis.

Reply.

harry January 23, 2015 at 5:05 am Code is not understandable without define what box is.

I cannot find out the meaning of those magic numbers like box[0][0] and box[1][0] Reply mikolalysenko January 23, 2015 at 1:48 pm I added some comments, hopefully this clears things up a bit.

Reply.

Clark November 7, 2015 at 1:28 am Thank you.

I KNEW I was going to have to deal with collision detection, but I had no idea how to really get away from the brute force method or what I believe is the broadphase now.

I am about to have a toke of box-intersect and see what happens ???? All the best.

Reply.

Leave a Reply Cancel reply.

Enter your comment here.

Email Name Website You are commenting using your WordPress.com account.

( / ) You are commenting using your Google account.

( / ) You are commenting using your Twitter account.

( / ) You are commenting using your Facebook account.

( / ).

Follow.

Post to bloggers like this:.