System and method for collision checking between solid objects and vectors
First Claim
1. A path analyzer, comprisinga 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.
3 Assignments
0 Petitions
Accused Products
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.
23 Citations
10 Claims
-
1. 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); anda 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. - View Dependent Claims (2, 3, 4, 5)
- wherein said specified obstacle is specified by coordinate values corresponding to a rectangular parallelepiped having six sides;
-
6. 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 ); andwhen 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; andperforming 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. - View Dependent Claims (7, 8, 9, 10)
- wherein said specified obstacle is specified by coordinate values corresponding to a rectangular parallelepiped having six sides;
Specification