球体衝突の続き
It seems that, in this paper, collisions occur only between spheres within the same subspace grid.
The basis for collision detection is the candidate collision events for each of the spheres. In fact, three types of events are defined: resetting, entering/leaving, and colliding (in fact a fourth type, colliding with the face of the box, is mentioned later). These events are maintained in an event tree. Whenever, B(si) (bound of sphere i) enters a subspace, candidate collision events are computed for that bound with other bounds in that subspace. New candidate enter/leave events are computed as well. These events are stored in an event tree, which is similar to the subspace tree and has log(n) insert/remove time.
In order to prevent B(si) from becoming too large, the diameter is restricted to the length of a subspace side. When it reaches this length, the position anv velocity of si is obtained and the radius of B(si) is reset to be the radius of si. When this occurs, B(si) is removed from the lists of those subspaces which it no longer intersects, and its events are re-calculated.
Similar actions are taken after a collision between time bounds, even if no collision occurred between the spheres themselves.
The paper concludes that each B(si) at a particular time interval has a constant number of candidate events in the event tree. The enter/leave events are constant, as there are at most 8 subspaces intersecting B(si). The number of collisions is constant, because for each of the 8 subspaces, there is a constant number of spheres within. Finally, there is one reset event. Thus, the number of events in the tree is O(n). Any event causes a constant number of events to be update and a constant number of subspaces to be updated. Thus, the total time to process an event is constant*log(n) = log(n). The total time to detect collisions in a given time interval among all spheres is:
O*1 where nt is the number of entering/leaving/resetting events and nc is the number of actual colliding events. Efficiency is improved by not inserting into the tree candidate events which will occur after the next reset (which we know will occur, regardless of where the sphere is, if it does not collide first).
Two experiments were performed using spheres moving in a single box. They were driven by user input in one experiment and by velocity fields (like magnetic fields?) in the second. The algorithm computed entering/leaving events based on when the bound touches a face of the box. Since it can be in only one box, this must occur if and only if a radius is parallel to the normal of a face:
| (x(t)-p)DOT(n) | = r(t) where x is the center of the bound, p is a point on the face, and n is the normal to the face. |
The reset event will occur at a time delta(t) from the current time, where delta(t) = SQRT*2:
| xi(t)-xj(t) | =ri(t)+rj(t) |
In other words, the norm of the vector between the centers of two bounds equals the sum of their radii. xi is the center of B(si), and xj is the center of B(sj). Substitution, squaring, and term rearrangement yields a quartic (order four) equation in terms of delta(t).
In a 200x200x200 box of 1000 spheres with a distribution of radii, initial velocities, and max acceleration norms, the time to compute all collisions for a second was 1.372 seconds. The time-varying bounds algorithm above performs noticeably better (over 2000 times faster for 1000 spheres) than another collision detection algorithm. This algorithm uses four-dimensional space-time bounds. It projects pairs of faces of the bound that are normal to an axis onto an "at plane", where "a" is the axis the faces are normal to. Each collision detection takes O*3 time, where n is the number of line segments and k is the number of collisions. This may be slower than the time needed to numerically solve the quartic above (I am not familiar enough with the space-time representation to understand the derivation of its complexity).
A second experiment with 1000 particles moing in a velocity field resulted in a processing time of 2.846 seconds to simulate 1 second of events. The longer time as compared to the previous experiment may be due to larger acceleration norms and larger radii.
The conclusion notes that the algorithm would be valid for ballistic spheres (acceleration is always A) where the trajectory is known. Future work could involve crowd simulations and interactive software.
