Patent ID: 6049341
Filing Date: 2000-04-11
Classification: G06T,Y10S

Abstract:
A method for detecting a collision between a first object that is moving and a second object, in a graphics environment effected with a computer, comprising the steps of:(a) extending a plurality of line segments in an ordered sequence, the ordered sequence of the line segments being joined at vertices that are ordered, forming an edge cycle around a projection of the second object onto a plane, each line segment being characterized as either back facing or front facing relative to the first object, as a function of a direction of the ordered sequence of the line segments around the projection;(b) projecting a path of the first object onto the plane as a path line segment extending in a direction along which the first object is moving and employing the path line segment to determine a path line equation that defines a path of the first object;(c) using the path line equation, classifying the vertices of the edge cycle to indicate a side of the path on which each vertex is disposed;(d) identifying any line segment of the edge cycle that is potentially intersected by the path line segment, by detecting consecutive vertices of the edge cycle that when classified, were found to be on different sides of the path;(e) for each said line segment that is potentially intersected by the path line segment, generating an edge cycle line equation; and(f) determining whether the path line segment actually intersects said line segment that is potentially intersected as a function of endpoints of the path line segment and of the edge cycle line equation, intersection of said line segment by the path line segment indicating that the first moving object has collided with the second object.