Patent US1079564A successfully refreshed from Google Patents.
Patent US5349533A successfully refreshed from Google Patents.
US5349533A
Expired / Lapsed
US
⏱️ 0.0 years remaining
System and method for collision checking between solid objects and vectors
Assignee: Lockheed Martin Corp
•
Filing: 1992-05-08
•
Granted: 1994-09-20
•
Expires: 2012-05-08
Abstract
Abstract A path analyzer for determining if a specified path is blocked by a given solid obstacle in three dimensional space. A programmable comparator converts path endpoints into first and second map signals, wherein each map signal indicates whether the corresponding path endpoint's position on predefined X, Y and Z coordinate axes is above, below or within a range of coordinate values associated with a specified obstacle. The specified obstacle is modelled as a rectangular parallelepiped, regardless of the actual shape of the obstacle. A first high speed decoder uses these map signals to make an initial determination as to whether the specified path is blocked, not blocked, or may be blocked by the specified obstacle. Whenever the first decoder determines that the path may be blocked, a second decoder determines the minimum number of additional computations needed to resolve whether the specified path is blocked. Depending on the number of sides of the specified obstacle that are "in view" of the specified paths's endpoints, one to three pairs of path intersection computations are required. In the preferred embodiments a dedicated computational unit is used to perform the calculations specified by the decoder to resolve whether the specified path is blocked. The dedicated computation unit is preprogrammed to perform six different pairs of computations, corresponding to the six sides of the obstacle. The second decoder determines which pairs of computations have to be performed for any particular path blockage determination.
Inventors
- 👤 Vibeke Libby
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-24 09:23
CPC Classifications
B; B25; B25J; B25J9/00; B25J9/16; B25J9/1656; B25J9/1664; B25J9/1666; G; G06; G06F; G06F30/00; G06F30/10; G06F30/18; G05; G05B; G05B2219/00; G05B2219/30; G05B2219/39; G05B2219/39082
Claims Analysis
Total Claims: 12
Claim 1
Independent Claim
285 words
A path analyzer, comprising a programmable comparator that converts a specified path's first and second endpoints in three dimensional space into first and second map signals, wherein each map signal indicates whether the corresponding path endpoint's position on predefined X, Y and Z coordinate axes is above, below or within a range of coordinate values associated with a specified obstacle; wherein said specified obstacle is specified by coordinate values corresponding to a rectangular parallelepiped having six sides; a first decoder that decodes said first and second map signals and generates a path analysis signal that specifies one of three path conditions selected from the group comprising: blocked (said specified path is blocked by said specified obstacle), unblocked (said specified path is not blocked by said specified obstacle), and may-be-blocked (said specified path may be blocked by said specified obstacle); and a dedicated computational unit, coupled to said first decoder, that is activated only when said first decoder generates a path analysis signal specifying a may-be-blocked path condition; said dedicated computational unit including (1) an arithmetic unit having a controller preprogrammed to perform selected ones of six predefined path intersection computations, each predefined path intersection computation determining whether any specified path intersects a distinct one of any specified obstacle's six sides; and (2) a second decoder that decodes said first and second map signals and generates identifier signals that identify a minimum number of said predefined path intersection computations necessary to determine whether said specified path is blocked by said specified obstacle; wherein said controller is coupled to second decoder for receiving said identifier signals and for directing said arithmetic unit to perform the ones of said predefined path intersection computations identified by said identifier signals.
Claim 2
Dependent Claim
285 words
A path analyzer, comprising a programmable comparator that converts a specified path's first and second endpoints in three dimensional space into first and second map signals, wherein each map signal indicates whether the corresponding path endpoint's position on predefined X, Y and Z coordinate axes is above, below or within a range of coordinate values associated with a specified obstacle; wherein said specified obstacle is specified by coordinate values corresponding to a rectangular parallelepiped having six sides; a first decoder that decodes said first and second map signals and generates a path analysis signal that specifies one of three path conditions selected from the group comprising: blocked (said specified path is blocked by said specified obstacle), unblocked (said specified path is not blocked by said specified obstacle), and may-be-blocked (said specified path may be blocked by said specified obstacle); and a dedicated computational unit, coupled to said first decoder, that is activated only when said first decoder generates a path analysis signal specifying a may-be-blocked path condition; said dedicated computational unit including (1) an arithmetic unit having a controller preprogrammed to perform selected ones of six predefined path intersection computations, each predefined path intersection computation determining whether any specified path intersects a distinct one of any specified obstacle's six sides; and (2) a second decoder that decodes said first and second map signals and generates identifier signals that identify a minimum number of said predefined path intersection computations necessary to determine whether said specified path is blocked by said specified obstacle; wherein said controller is coupled to second decoder for receiving said identifier signals and for directing said arithmetic unit to perform the ones of said predefined path intersection computations identified by said identifier signals.
Claim 3
Dependent Claim
32 words
The path analyzer of claim 1, wherein said first and second map signals indicate which of 27 predefined spatial relationships said first and second endpoints have with respect to said specified obstacle.
Claim 4
Dependent Claim
75 words
The path analyzer of claim 2, wherein said second decoder selects one of said first and second map signals in accordance with predefined computation minimization criteria, said predefined computation minimization criteria comprises selecting one of said first and second map signals so that the corresponding one of said first and second path endpoints is in view of no more sides of said specified object than the other one of said first and second path endpoints.
Claim 5
Dependent Claim
61 words
The path analyzer of claim 1, wherein said second decoder means includes a first logic circuit that selects one of said first and second map signals in accordance with predefined computation minimization criteria, and a memory coupled to said first logic circuit, said memory using said selected map signal as an address, the output of said memory being said identifier signals.
Claim 6
Dependent Claim
48 words
The path analyzer of claim 1, said dedicated computational unit including three parallel arithmetic units, each having a controller preprogrammed to perform a distinct subset of said six predefined path intersection computations, and control means for initiating computations by said arithmetic units in accordance with said identifier signals.
Claim 7
Dependent Claim
267 words
In a method of determining whether a specified path is blocked by a specified obstacle, converting a specified path's first and second endpoints in three dimensional space into first and second map signals, wherein each map signal indicates whether the corresponding path endpoint's position on predefined X, Y and Z coordinate axes is above, below or within a range of coordinate values associated with a specified obstacle; wherein said specified obstacle is specified by coordinate values corresponding to a rectangular parallelepiped having six sides; decoding said first and second map signals so as to generate a path analysis signal that specifies one of three path conditions selected from the group comprising: blocked (said specified path is blocked by said specified obstacle), unblocked (said specified path is not blocked by said specified obstacle), and may-be-blocked (said specified path may be blocked by said specified obstacle ); and when said first decoding step generates a path analysis signal specifying a may-be-blocked path condition, further decoding said first and second map signals so as to generate identifier signals that identify a minimum number of one to three predefined path intersection computations necessary to determine whether said specified path is blocked by said specified obstacle; wherein said minimum number of predefined path intersection computations are selected from a set of six predefined path intersection computations, each predefined path intersection computation determining whether any:specified path intersects a distinct one of any specified obstacle's six sides; and performing said predefined path intersection computations identified by said identifier signals until said specified path is determined to be blocked or not-blocked by said specified obstacle.
Claim 8
Dependent Claim
267 words
In a method of determining whether a specified path is blocked by a specified obstacle, converting a specified path's first and second endpoints in three dimensional space into first and second map signals, wherein each map signal indicates whether the corresponding path endpoint's position on predefined X, Y and Z coordinate axes is above, below or within a range of coordinate values associated with a specified obstacle; wherein said specified obstacle is specified by coordinate values corresponding to a rectangular parallelepiped having six sides; decoding said first and second map signals so as to generate a path analysis signal that specifies one of three path conditions selected from the group comprising: blocked (said specified path is blocked by said specified obstacle), unblocked (said specified path is not blocked by said specified obstacle), and may-be-blocked (said specified path may be blocked by said specified obstacle ); and when said first decoding step generates a path analysis signal specifying a may-be-blocked path condition, further decoding said first and second map signals so as to generate identifier signals that identify a minimum number of one to three predefined path intersection computations necessary to determine whether said specified path is blocked by said specified obstacle; wherein said minimum number of predefined path intersection computations are selected from a set of six predefined path intersection computations, each predefined path intersection computation determining whether any:specified path intersects a distinct one of any specified obstacle's six sides; and performing said predefined path intersection computations identified by said identifier signals until said specified path is determined to be blocked or not-blocked by said specified obstacle.
Claim 9
Dependent Claim
50 words
The method of claim 6, wherein said second decoding step includes selecting one of said first and second map signals in accordance with predefined computation minimization criteria, and generating said identifier signals by reading said identifier signals from a lookup table using said selected map signal as a lookup address.
Claim 10
Dependent Claim
24 words
The method of claim 7, said performing step including performing each of said minimum number of predefined path intersection computations in parallel computational units.
Claim 11
Dependent Claim
31 words
The method of claim 6, wherein said first and second map signals indicate which of 27 predefined spatial relationships said first and second endpoints have with respect to said specified obstacle.
Claim 12
Dependent Claim
75 words
The method of claim 9, wherein said further decoding step selects one of said first and second map signals in accordance with predefined computation minimization criteria, said predefined computation minimization criteria comprises selecting one of said first and second map signals so that the corresponding one of said first and second path endpoints is in view of no more sides of said specified object than the other one of said first and second path endpoints.
References Cited (Backward Citations)
US4862373A
Cited
US4888707A
Cited
US5047916A
Cited
US5229941A
Cited
US5056031A
Cited
US5150452A
Cited
US5150026A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1997-09-19 | 1998-03-21 | 1998-09-20 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2001-09-19 | 2002-03-21 | 2002-09-20 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2005-09-19 | 2006-03-21 | 2006-09-20 | $7700.00 | Window Closed / Lapsed |