Patent ID: 8717382

Claim:
A method of detecting collisions on a Graphics Processing Unit (GPU), the method comprising: a) projecting respectively each of collision detection objects O i onto a reference direction so as to obtain a respective interval I i represented by a set {m i , M i }; b) performing radix sorting based on m i for all O i so as to obtain a sorted list L; c) performing, in parallel, for each O i : sweeping the sorted list L within the interval I i for each of collision detection objects O j where i<j until M i <m j ; and adding a colliding pair (O i , O j ) to colliding pairs P i if O i ∩O j ≠0 where m j εI i for O j ; and d) joining all of the colliding pairs P i into a final colliding pair P, wherein an i-th collision detection object of n collision detection objects is denoted by O i , and m i and M i respectively denote locations of extremal points in the reference direction.