Method of detecting collisions in graphics processing unit
View Patent ↗The present invention relates to a method of detecting collisions on a Graphics Processing Unit (GPU). Each collision detection object O i is projected onto a reference direction, thus obtaining an interval I i represented by a set {m i , M i }. Radix sorting based on obtained m i for all O i , thus obtaining a sorted list L. The sorted list is swept, and then colliding pairs P i are detected. All colliding pairs are configured into a single set, thus obtaining a final colliding pair P. On a GPU, SaP can be performed on a plurality of collision detection objects in parallel using the blocks of a plurality of threads.
1. 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.
2. The method according to claim 1 , wherein one GPU thread is allocated to each O i so that collision detection is performed.
3. The method according to claim 1 , wherein each O i is divided into partitions, each having an identical number of collision detections, and a single GPU thread is allocated to each partition, thus performing collision detection.
4. The method according to claim 3 , wherein binary search is performed on the sorted list L to determine a number of partitions, which is represented by
⌈
p
-
i
τ
⌉
,
where p−i denotes a number of potential colliding pairs, and τ denotes a maximum number of colliding pairs to which a single thread can be allocated.
5. The method according to claim 1 , wherein a sweep direction at c) is determined using Principal Component Analysis (PCA), and the sweep direction is determined by a vector value w 1 given in the following equation, the vector value w 1 being identical to a direction of a first principal component of PCA,
w
1
=
arg
max
w
=
1
Var
{
w
T
X
}
=
arg
max
w
=
1
E
{
w
T
XX
T
w
}
where w 1 denotes an eigenvector corresponding to a largest eigenvalue of a covariance matrix C=XX T .
6. The method according to claim 1 , further comprising a0) dividing a workspace, before a).
7. The method according to claim 6 , wherein a0) comprises:
a0-1) when a sweep direction is assumed to be ‘d’ at c), subdividing the workspace into m×m grid cells cut by a plane parallel to ‘d’; and
a0-2) when there is a collision detection object passing through boundaries of cells subdivided at a0-1), shifting the interval I i using (j−1)×l which is the direction ‘d’,
wherein
m
=
⌈
n
64
K
⌉
,
n is a number of collision detection objects, j is an index of a cell C φ to which O ι belongs, and l is a size of the workspace along the direction ‘d’.
8. The method according to claim 1 , further comprising, before c), performing cell subdivision to remove collision detection objects which do not actually intersect, but have overlapping projection intervals.
9. The method according to claim 8 , wherein the performing cell subdivision is configured to divide a single cell into a reference number of subcells and to eliminate a relevant collision detection object from collision detection objects when the relevant collision detection object is not a collision detection object that shares an identical subcell.
10. A method of detecting collisions in 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:
detecting a set P σμ (t) of colliding pairs between a set O σ (t) of static collision detection objects and a set O μ (t) of moving collision detection objects for each O i belonging to the set O σ (t) of static collision detection objects, by using parallel sweeping;
detecting a set P μ* (t) of colliding pairs by comparing the set O μ (t) of the moving collision detection objects with sets O of all other collision detection objects, for each O i belonging to the set O μ (t) of the moving collision detection objects by using parallel sweeping; and
calculating a union P M (t) of the set P σμ (t) and the set P μ* (t)
d) detecting interfering pairs P σ (t) from the set O σ (t) of the static collision detection objects; and
e) calculating a union of the set P M (t) and the interfering pairs P σ (t) so as to obtain 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.
11. The method according to claim 10 , wherein d) is configured to detect the interfering pairs P σ (t) from the set O σ (t) of the static collision detection objects after a colliding pair P(t−1) corresponding to previous time, wherein P σ (t) is detected by calculating a difference set between P(t−1) and P′ M (t−1) represented by the following equation:
P′ M (t−1)≡{∀(O i ,O j )εP(t−1)|O i εO μ (t) O j εO μ (t)}.
12. The method according to claim 10 , further comprising a0) dividing a workspace, before a).
13. The method according to claim 12 , wherein a0) comprises:
a0-1) when a sweep direction is assumed to be ‘d’ at c), subdividing the workspace into m×m grid cells cut by a plane parallel to ‘d’; and
a0-2) when there is a collision detection object passing through boundaries of cells subdivided at a0-1), shifting the interval I i using (j−1)×l which is the direction ‘d’,
wherein
m
=
⌈
n
64
K
⌉
,
n is a number of collision detection objects, j is an index of a cell C φ to which O ι belongs, and l is a size of the workspace along the direction ‘d’.
14. The method according to claim 10 , wherein:
a sweep direction at c) is determined using Principal Component Analysis (PCA), and the sweep direction is determined by a vector value w 1 given in the following equation, the vector value w 1 being identical to a direction of a first principal component of PCA,
w
1
=
arg
max
w
=
1
Var
{
w
T
X
}
=
arg
max
w
=
1
E
{
w
T
XX
T
w
}
where w 1 denotes an eigenvector corresponding to a largest eigenvalue of a covariance matrix C=XX T .
15. The method according to claim 10 , further comprising, before c), performing cell subdivision to remove collision detection objects which do not actually intersect, but have overlapping projection intervals.
16. The method according to claim 15 , wherein the performing cell subdivision is configured to divide a single cell into a reference number of subcells and to eliminate a relevant collision detection object from collision detection objects when the relevant collision detection object is not a collision detection object that shares an identical subcell.