Patent US4888707A successfully refreshed from Google Patents.
US4888707A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Object collision detection method and apparatus
Assignee: International Business Machines Corp
•
Filing: 1988-08-18
•
Granted: 1989-12-19
•
Expires: 2008-08-18
Abstract
Abstract A collision detection system with less computation time and higher performance is provided. The shortest distance between the surface of one object and the surface of another at the beginning or end of a period to be checked is compared with the sum of the maximum length of paths along which points of the surface of the one object move in the period, and the like of the other. If the former is bigger than the later, then it is sure that the two objects cannot collide in the period. If not, it is not sure, and the period is divided into two parts, and then such a test is done for each partial period. Such a test and division are recursively performed until the whole period is ensured to have no collision or an approximate collision is detected. The approximate collision is defined as a state of the shortest distance between the surface of the one object and the surface of the other being less than a predetermined threshold. This invention is useful in CAD/CAM system in particular for off-line robot movement teaching.
Inventors
- 👤 Kenji Shimada
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-07 22:20
CPC Classifications
B; B25; B25J; B25J9/00; B25J9/16; B25J9/1656; B25J9/1664; B25J9/1666; G; G05; G05B; G05B19/00; G05B19/02; G05B19/18; G05B19/406; G05B19/4061; Y; Y02; Y02P; Y02P90/00; Y02P90/02
Claims Analysis
Total Claims: 24
Claim 1
Independent Claim
122 words
An object collision detection apparatus comprising: means for obtaining the shortest distance between the surface of one object and the surface of another object at the start time and/or the end time of a given check time interval; means for obtaining the longest movement path length of points on each of said one object and said another object during said check time interval; determination means for comparing said shortest distance at said start time and/or said end time with the sum of said longest movement path lengths of said one object and said another object, and further for determining whether or not it is ensured that said one object cannot collide with said another object, according to the result of said comparing.
Claim 2
Dependent Claim
122 words
An object collision detection apparatus comprising: means for obtaining the shortest distance between the surface of one object and the surface of another object at the start time and/or the end time of a given check time interval; means for obtaining the longest movement path length of points on each of said one object and said another object during said check time interval; determination means for comparing said shortest distance at said start time and/or said end time with the sum of said longest movement path lengths of said one object and said another object, and further for determining whether or not it is ensured that said one object cannot collide with said another object, according to the result of said comparing.
Claim 3
Dependent Claim
126 words
An object collision detection apparatus as described in claim 1, wherein: said determination means at first determines whether or not it is ensured that said one object cannot collide with said another object, according to said result of said comparing in respect with one of said start time and said end time of said check time interval, and next only if it is not ensured that said one object cannot collide with said another object, determines whether or not it is ensured that said object cannot collide with said another object, according to the comparison between said shortest distance at another of said start time and said end time, and the sum of said longest movement path lengths of said one object and said another object.
Claim 4
Dependent Claim
57 words
An object collision detection apparatus as described in claim 1, wherein: said determination means determines that is is ensured that said one object cannot collide with said another object, when said shortest distance at said start time and/or end time is larger than said sum of said longest movement path lengths of said one and another object.
Claim 5
Dependent Claim
296 words
An object collision detection apparatus comprising: means for initially setting a check time interval in which whether or not it is ensured that one object cannot collide with another object is checked; means for obtaining the shortest distances between the surface of one object and the surface of another object at the start time and the end time of a current check time interval; means for obtaining the longest movement path length of points on each of said one object and said another object during said current check time interval; first determination means for comparing said shortest distance at said start time and said end time with the sum of said longest movement path lengths of said one object and said another object, and further for determining whether or not it is ensured that said one object cannot collide with said another object, according to the result of said comparing; check time interval renewal means for dividing said current check time interval into a plurality of sub time intervals when said first determination means determines that it is not ensured that said one object cannot collide with said another object, and for setting said sub time intervals in turn as a new check time interval; second determination means for checking whether or not said shortest distance(s) at said start time and said end time is less than a predetermined threshold value, when said first determination means determines that it is ensured that said one object cannot collide with said another object during said current check time interval, and for determining that said one object approximately collides with said another object at said start time and/or said end time, when said shortest distance(s) at said start time and/or said end time is less than said threshold value.
Claim 6
Dependent Claim
296 words
An object collision detection apparatus comprising: means for initially setting a check time interval in which whether or not it is ensured that one object cannot collide with another object is checked; means for obtaining the shortest distances between the surface of one object and the surface of another object at the start time and the end time of a current check time interval; means for obtaining the longest movement path length of points on each of said one object and said another object during said current check time interval; first determination means for comparing said shortest distance at said start time and said end time with the sum of said longest movement path lengths of said one object and said another object, and further for determining whether or not it is ensured that said one object cannot collide with said another object, according to the result of said comparing; check time interval renewal means for dividing said current check time interval into a plurality of sub time intervals when said first determination means determines that it is not ensured that said one object cannot collide with said another object, and for setting said sub time intervals in turn as a new check time interval; second determination means for checking whether or not said shortest distance(s) at said start time and said end time is less than a predetermined threshold value, when said first determination means determines that it is ensured that said one object cannot collide with said another object during said current check time interval, and for determining that said one object approximately collides with said another object at said start time and/or said end time, when said shortest distance(s) at said start time and/or said end time is less than said threshold value.
Claim 7
Dependent Claim
58 words
An object collision detection apparatus as described in claim 4, wherein: said first determination means determines that it is ensured that said one object cannot collide with said another object, when said shortest distance at said start time and/or end time is larger than said sum of said longest movement path lengths of said one and another object.
Claim 8
Dependent Claim
48 words
An object collision detection apparatus as described in claim 5, wherein: said check time interval renewal means sets said divided sub time intervals as a check time interval in order of nearness of said sub time intervals to said start time of said initially set check time interval.
Claim 9
Dependent Claim
75 words
An object collision detection apparatus as described in claim 6, wherein: said check time interval renewal means checks whether or not said one object overlap with said another object at said end time of said current check time interval, and in case of overlapping, divides said current check time interval into sub time intervals without determination by said first determination means, and sets said sub time intervals as a new check time interval in turn.
Claim 10
Dependent Claim
48 words
An object collision detection apparatus as described in claim 4, wherein: said check time interval renewal means sets said divided sub time intervals as a check time interval in order of nearness of said sub time intervals to said start time of said initially set check time interval.
Claim 11
Dependent Claim
75 words
An object collision detection apparatus as described in claim 8, wherein: said check time interval renewal means checks whether or not said one object overlap with said another object at said end time of said current check time interval, and in case of overlapping, divides said current check time interval into sub time intervals without determination by said first determination means, and sets said sub time intervals as a new check time interval in turn.
Claim 12
Dependent Claim
24 words
An object collision detection apparatus as described in claim 4, wherein: the number of said sub time intervals divided in a time is two.
Claim 13
Dependent Claim
118 words
An object collision detection method comprising the steps of: obtaining the shortest distance between the surface of one object and the surface of another object at the start time and/or the end time of a given check time interval; obtaining the longest movement path length of points on each of said one object and said another object during said check time interval; comparing said shortest distance at said start time and/or said end time with the sum of said longest movement path lengths of said one object and said another object, and further for determining whether or not it is ensured that said one object cannot collide with said another object, according to the result of said comparing.
Claim 14
Dependent Claim
118 words
An object collision detection method comprising the steps of: obtaining the shortest distance between the surface of one object and the surface of another object at the start time and/or the end time of a given check time interval; obtaining the longest movement path length of points on each of said one object and said another object during said check time interval; comparing said shortest distance at said start time and/or said end time with the sum of said longest movement path lengths of said one object and said another object, and further for determining whether or not it is ensured that said one object cannot collide with said another object, according to the result of said comparing.
Claim 15
Dependent Claim
125 words
An object collision method as described in claim 11, wherein said comparing step further comprises: determining whether or not it is ensured that said one object cannot collide with said another object, according to said result of said comparing in respect with one of said start time and said end time of said check time interval, and next only if it is not ensured that said one object cannot collide with said another object, determines whether or not it is ensured that said object cannot collide with said another object, according to the comparison between said shortest distance at another of said start time and said end time, and the sum of said longest movement path lengths of said one object and said another object.
Claim 16
Dependent Claim
59 words
An object collision detection method as described in claim 11, wherein said comparing step further comprises: determining that it is ensured that said one object cannot collide with said another object, when said shortest distance at said start time and/or end time is larger than said sum of said longest movement path lengths of said one and another object.
Claim 17
Dependent Claim
276 words
An object collision method comprising the steps of: initially setting a check time interval in which whether or not it is ensured that one object cannot collide with another object is checked; obtaining the shortest distances between the surface of one object and the surface of another object at the start time and the end time of a current check time interval; obtaining the longest movement path length of points on each of said one object and said another object during said current check time interval; comparing said shortest distance at said start time and said end time with the sum of said longest movement path lengths of said one object and said another object, and further for determining whether or not it is ensured that said one object cannot collide with said another object, according to the result of said comparing; dividing said current check time interval into a plurality of sub time intervals when said comparing step determines that it is not ensured that said one object cannot collide with said another object, and for setting said sub time intervals in turn as a new check time interval; checking whether or not said shortest distance(s) at said start time and said end time is less than a predetermined threshold value, when said comparing step determines that it is ensured that said one object cannot collide with said another object during said current check time interval, and for determining that said one object approximately collides with said another object at said start time and/or said end time, when said shortest distance(s) at said start time and/or said end time is less than said threshold value.
Claim 18
Dependent Claim
276 words
An object collision method comprising the steps of: initially setting a check time interval in which whether or not it is ensured that one object cannot collide with another object is checked; obtaining the shortest distances between the surface of one object and the surface of another object at the start time and the end time of a current check time interval; obtaining the longest movement path length of points on each of said one object and said another object during said current check time interval; comparing said shortest distance at said start time and said end time with the sum of said longest movement path lengths of said one object and said another object, and further for determining whether or not it is ensured that said one object cannot collide with said another object, according to the result of said comparing; dividing said current check time interval into a plurality of sub time intervals when said comparing step determines that it is not ensured that said one object cannot collide with said another object, and for setting said sub time intervals in turn as a new check time interval; checking whether or not said shortest distance(s) at said start time and said end time is less than a predetermined threshold value, when said comparing step determines that it is ensured that said one object cannot collide with said another object during said current check time interval, and for determining that said one object approximately collides with said another object at said start time and/or said end time, when said shortest distance(s) at said start time and/or said end time is less than said threshold value.
Claim 19
Dependent Claim
57 words
An object collision detection apparatus as described in claim 14, wherein: said comparing step determines that it is ensured that said one object cannot collide with said another object, when said shortest distance at said start time and/or end time is larger than said sum of said longest movement path lengths of said one and another object.
Claim 20
Dependent Claim
42 words
An object collision detection apparatus as described in claim 15 wherein: setting said divided sub time intervals as a check time interval in order of nearness of said sub time intervals to said start time of said initially set check time interval.
Claim 21
Dependent Claim
72 words
An object collision detection method as described in claim 16, wherein: said dividing step checks whether or not said one object overlap with said another object at said end time of said current check time interval, and in case of overlapping, divides said current check time interval into sub time intervals without determination by said first determination means, and set said sub time intervals as a new check time interval in turn.
Claim 22
Dependent Claim
42 words
An object collision detection apparatus as described in claim 14 wherein: setting said divided sub time intervals as a check time interval in order of nearness of said sub time intervals to said start time of said initially set check time interval.
Claim 23
Dependent Claim
72 words
An object collision detection method as described in claim 18, wherein: said dividing step checks whether or not said one object overlap with said another object at said end time of said current check time interval, and in case of overlapping, divides said current check time interval into sub time intervals without determination by said first determination means, and set said sub time intervals as a new check time interval in turn.
Claim 24
Dependent Claim
24 words
An object collision detection method as described in claim 14, wherein: the number of said sub time intervals divided in a time is two.
References Cited (Backward Citations)
US4578757A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1992-12-18 | 1993-06-19 | 1993-12-19 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1996-12-18 | 1997-06-19 | 1997-12-19 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2000-12-18 | 2001-06-19 | 2001-12-19 | $7700.00 | Window Closed / Lapsed |