Methods and apparatus for expediting detecting collision between any of N objects
AssigneeIntel Corporation
InventorsCharles M. Forest, Oliver A. Heim
Life of this patent
Estimating the term…
Abstract
Methods and apparatus for expediting detection of collision between any of N objects are disclosed. When a determination is made that a plurality of the N objects are one of (a) located in a plane and (b) collinear along a line parallel to an axis of a first coordinate system; one example method selects a second coordinate system wherein less than the plurality of the N objects lie in any plane of the second coordinate system; and performs a sweep and prune process on the N objects using the second coordinate system. Another example method responds to the determination by performing a sweep and prune process on the N objects while ignoring any set of objects having more than a predetermined number of members.
Claims35
A method of expediting detection of collision between any of N objects comprising:
- generating a plurality of sets of potentially colliding pairs of the N objects;
- comparing a number of members in each of the plurality of sets to a predetermined threshold;
- and
- identifying an intersection of any sets in the plurality of sets which have less members than the predetermined threshold.
A method of expediting detection of collision between any of N objects comprising:
- (a) projecting each of the N objects onto each of a first axis, a second axis and a third axis;
- (b) creating a first set containing pairs of the N objects having overlapping projections on the first axis;
- (c) creating a second set containing pairs of the N objects having overlapping projections on the second axis;
- (d) creating a third set containing pairs of the N objects having overlapping projections on the third axis;
- and
- (e) if any of the first, second and third sets include more than a predetermined number of pairs, (1) defining a new coordinate system, (2) repeating (a)–(e) using the new coordinate system, and (3) determining an intersection of the first, second and third sets created using the new coordinate system.
A method of detecting collision between any of N objects comprising:
- generating a first plurality of sets of potentially colliding pairs of N objects using a first coordinate system;
- and
- if any of the sets in the first plurality include more than a predetermined number of members, (1) defining a second coordinate system, (2) generating a second plurality of sets of potentially colliding pairs of N objects using the second coordinate system, and (3) performing a collision test on an intersection of the sets in the second plurality of sets.
An apparatus for expediting detection of collision between any of N objects comprising:
- a set generator to generate a plurality of sets of potentially colliding pairs of the N objects;
- a set tester to compare a number of members in each of the plurality of sets to a predetermined threshold;
- and
- an intersection generator to develop an intersection of any set(s) in the plurality of sets which have less members than the predetermined threshold.
A tangible medium storing computer readable instructions which when executed cause a processor:
- to generate a plurality of sets of potentially colliding pairs of the N objects;
- to compare a number of members in each of the plurality of sets to a predetermined threshold;
- and
- to develop an intersection of any sets in the plurality of sets which have less members than the predetermined threshold.
An apparatus for expediting detection of collision between any of N objects comprising:
- a coordinate setter to set a coordinate system;
- a set generator to generate a plurality of sets of potentially colliding pairs of the N objects using the coordinate system set by the coordinate system setter;
- a set tester to compare a number of members in each of the plurality of sets developed by the set generator to a predetermined number, wherein the coordinate setter defines a new coordinate system if the set tester determines that any of the plurality of sets contains more than the predetermined number of members;
- and
- an intersection generator to develop an intersection of the sets in the plurality of sets after the coordinate setter has defined a coordinate system wherein the number of members in each of the plurality of sets is below the predetermined number.
A method of detecting collision between any of N objects comprising:
- determining that a plurality of the N objects are one of (a) located in a plane and (b) collinear along a line parallel to an axis of a first coordinate system;
- selecting a second coordinate system wherein less than the plurality of the N objects lie in any plane associated with the second coordinate system;
- and
- performing a sweep and prune process on the N objects using the second coordinate system.
A method of detecting collision between any of N objects comprising:
- determining that a plurality of the N objects are one of (a) located in a plane and (b) collinear along a line parallel to an axis of a first coordinate system;
- and
- performing a sweep and prune process on the N objects while ignoring any set of objects having more than a predetermined number of members.
Dependencies are inferred from the claim text.