Note: Descriptions are shown in the official language in which they were submitted.
CA 02212240 1997-08-01
--1--
GUIDANCE SYSTEM WITH TARGET LINE G~N~TION IN vlkluAL
REALITY DISPLAY
BACKGROUND OF THE lNv~NllON
This invention relates to devices for providing guidance to
an operator of a vehicle to precisely navigate the vehicle
over a work area. The invention may be used with
agricultural machines such as sprayers, spreaders, seeders,
etc., and for machines used in land planing and profiling
such as graders, scrapers and bulldozers. The invention
can also be applied in the forest industry, mining industry
and in marine applications.
Currently, to navigate a vehicle over a field in order to
spray pesticides or fertilizer over crops a vehicle
operator must be careful not to re-spray a sprayed area and
not to overestimate or underestimate the overlap of the
spray on successive passes~
Some of the chemicals used for spraying are very difficult
to see, which forces vehicle operators to try to remember
the exact path and spray widths used for each pass over the
field. When the field includes obstacles that must be
avoided while driving, or, if the operator has few
landmarks with which to navigate, the chances of over-
spraying or under-spraying areas of the field are greatly
increased, resulting in wastage of chemicals and un-sprayed
areas.
If the vehicle operator stops work due to weather or time
constraints and returns to spraying the field at a later
date or time, the operator has no way of knowing exactly
which areas have already been sprayed.
The agricultural industry has addressed this problem by
using a foam dispenser positioned on a distal end portion
CA 02212240 1997-08-01
of a boom to dispense foam to mark an outer edge of a work
area traversed by the sprayer or other agricultural
implement. An operator of the implement can then see lines
of foam marking sprayed or worked boundaries. Foam
markers, however, are affected by weather conditions such
as rain and the like and have only a temporary presence.
In addition, foam markers can only be used when there is
enough light to enable the operator to see them and,
therefore, they may be unsatisfactory at night.
Other solutions include GPS-based navigation systems, which
compute the position of the vehicle or implement from
satellite signals. Computations are then performed to
present the vehicle operator with guidance information.
Currently available systems provide guidance information by
suggesting a system of parallel paths to cover a work area.
Such systems are ineffective in work areas where driving
paths will be not parallel to each other. Non-parallel
path operation can be important for irregularly shaped work
areas with obstacles.
In addition, some GPS systems include only a digital map
display, which presents the position of the vehicle,
completed work, work to be completed, and work area
landmarks. This type of display is useful for navigation
in the field, but is difficult to use for guidance because
it is difficult to make decisions about future directions
and turns.
Other systems employ a light bar display. A light bar
display indicates to the vehicle operator any deviation of
the current vehicle position relative to a path that the
vehicle should follow. This type of indicator also fails
to notify the operator of upcoming turns, which is
important if the path is not straight. This can lead to
operator fatigue.
CA 02212240 1997-08-01
object derived from the coordinates of various points on
the surface of the object.
Preferably, the processor is programmed to produce a
virtual reality representation of the space, as seen from
the viewpoint in the direction of the heading, the virtual
reality representation including a representation of at
least one object, derived from the coordinates of various
points on the surface of the object.
Preferably, the processor is programmed to simultaneously
produce the virtual reality representation and a plan view
of the space.
Preferably, the processor is programmed to receive mapping
data representing the coordinates of various points on
respective surfaces of a plurality of objects in the space,
to store the coordinates in memory and to produce
respective representations of each of the objects in the
visual representation such that the user can view the
respective representations simultaneously.
Preferably, the processor is programmed to identify
coordinates of an area representing at least a portion of
the space, to identify objects within the area, and to send
to the display commands including the coordinates of
surfaces of objects within the area.
Preferably, the processor is programmed to compute point
positions of a plurality of respective target line
segments, relative to the first and second spacial
positions, to produce a representation of a target line
extending at a first pre-defined distance from at least one
of the first and second spacial positions, the point
positions being computed such that the target line segments
associated with respective point positions do not extend
between points representing the surface of an object.
CA 02212240 1997-08-01
It would therefore be desirable to have a device which
allows the vehicle operator to observe a graphical
representation of the work area, including completed work,
the path the operator should follow to complete the work,
area landmarks and a representation of further directions
and turns. It would also be desirable for the device to be
capable of providing guidance in irregularly shaped areas
and for the device to be able to provide guidance for
different driving modes, including parallel and spiral
modes. It would also be desirable for the vehicle operator
to observe a graphical representation of areas that have
been sprayed and areas to be sprayed by providing a path on
which to take the vehicle to optimize the spraying of a
field to reduce over-spray and avoid un-sprayed areas. The
present invention addresses this need.
BRIEF SU~$ARY OF THE l~v~;NllON
In accordance with one aspect of the invention, there is
provided an apparatus for displaying a representation of an
area in a space. The apparatus includes a mapping data
receiver for receiving mapping data representing the
coordinates of various points identifying a surface contour
of at least one object in the space, memory for storing the
coordinates, a position signal receiver operable to move in
a path in the space and for receiving position signals
indicative of at least first and second spacial positions
of the position signal receiver, a display and a processor.
The processor is in communication with the mapping data
receiver, the memory, the position signal receiver, and the
display and is programmed to compute a heading of the
receiver from the position signals. The processor is
programmed to compute a viewpoint relative to at least one
of the first and second spacial positions, and to produce
commands recognizable by the display for causing the
display to produce a visual representation of the space, as
seen from the viewpoint in the direction of the heading.
The visual representation includes a representation of the
CA 02212240 1997-08-01
Preferably, the processor is programmed to compute the
point positions such that the point positions are no nearer
than a safety distance to the object.
Preferably, the processor is programmed to compute the
point positions such that the target line generally follows
the contour of an object.
Preferably, the processor is programmed to produce a visual
representation of the target line.
Preferably, the processor is programmed to update the
visual representation as the receiver moves in the space.
lS In accordance with another aspect of the invention, there
is provided guidance apparatus. The guidance apparatus
includes a mapping data receiver for receiving mapping data
representing the coordinates of various points identifying
a surface contour of at least one object in the space,
memory for storing the coordinates, a position signal
receiver operable to move in a path in the space and for
receiving position signals indicative of at least first and
second spacial positions of the position signal receiver,
and a processor in communication with the mapping data
receiver, the memory, and the position signal receiver.
The processor is programmed to compute point positions of
a plurality of respective target line segments, relative to
the first and second spacial positions, to produce a
representation of a target line extending from at least one
of the first and second spacial positions. The point
positions are computed such that the target line segments
associated with respective point positions do not extend
between the points representing the contour of any object
represented by the mapping data stored in the memory at the
time at least one point position is computed, such that
each of the point positions is computed using mapping data
available at the time at it is calculated. The processor
CA 02212240 1997-08-01
further produces a signal representing a prediction of the
path of the receiver as indicated by the point positions.
Preferably, the processor is programmed to receive and
store new mapping data after at least one point position is
computed such that the calculation of subsequent point
positions is performed using the initial mapping data and
the new mapping data.
Preferably, the processor is programmed to accumulate, in
a completed work record, position points of the receiver,
the position points representing positions which the
receiver has traversed.
Preferably, the processor is programmed to accumulate a
pre-defined number of position points in the completed work
record and store the completed work record in a completed
work list when the completed work record contains the pre-
defined number of position points and to include the
completed work list in the new mapping data.
Preferably, the processor is programmed to divide the
initial mapping data and the new mapping data into sub-
portions of coordinates of points representing the contours
of surfaces of objects, where the surfaces of the objects
are within a corresponding sub-portion of the space.
Preferably, the processor is programmed to compute the
point positions such that the point positions are no nearer
than the safety pre-defined distance to the object.
Preferably, the processor is programmed to compute the
position of a viewpoint relative to at least one of the
first and second spacial positions.
Preferably, the processor is programmed to compute from the
position signals, a heading of the receiver.
CA 02212240 1997-08-01
Preferably, apparatus further includes a display and
preferably the processor is programmed to produce display
commands for causing the display to produce a visual
representation of the target line.
Preferably, the visual representation includes a virtual
reality representation of the space, as seen from the
viewpoint in the direction of the heading, the virtual
reality representation including the representation of the
target line.
Preferably, the virtual reality representation includes a
representation of at least one object derived from the
coordinates of the various points representing the contour
of the surface of the object.
Preferably, the processor is programmed to produce display
commands which cause the display to simultaneously produce
the virtual reality view and a plan view of the target
line.
Preferably, the processor is programmed to update the
prediction as the receiver moves in the space.
Preferably, the processor is programmed to compute the
point positions such that the target line generally follows
the contour of an object.
Preferably, the processor is programmed to receive and
store in a mapping data list a plurality of pairs of
coordinates identifying the surface of an object within the
space, the pairs of coordinates representing heads and
tails respectively of obstacle line segments approximating
the surface of the object.
Preferably, the processor is programmed to identify
coordinates of an area representing at least a portion of
CA 02212240 1997-08-01
the space and identify pairs of coordinates in the mapping
data list which are associated with objects within the
area.
Preferably, the processor is programmed to identify
coordinates of obstacles within the area and within a
second pre-defined distance of a current point position.
Preferably, the processor is programmed to compute the
point positions such that the target line segments
associated with respective point positions do not cross
obstacle line segments within the second pre-defined
distance of the current position point.
Preferably, the processor is programmed to compute
coordinates of a plurality of possible target line
segments, to compare each target line segment with obstacle
line segments within the second pre-defined distance of the
current position point to determine whether any target line
segment crosses an obstacle line segment, and to eliminate
from the plurality of possible target line segments target
line segments which cross obstacle line segments within the
second pre-defined distance of the current position point.
Preferably, the processor is programmed to eliminate from
the plurality of possible target line segments, each target
line segment having a headpoint no nearer than a safety
distance to the object.
Preferably, the processor is programmed to select
coordinates identifying a target line segment nearest at
least one obstacle line segment of the object as
coordinates which identify a target line head segment.
Preferably, the processor is programmed to determine which
of the target line segments has a head point corresponding
to a position in space nearest to at least one of the first
~NI ~Y:YANCOUVER ;10- 9-97 ; 3:26PM ; 650 W. GEORGIA ST.~ 819 953 9538;# 2~ 9
CA 02212240 1997-08-01
and second spacial position~ of the receiver, a~ compared
to the position~ in space of headpoints of remaining target
line segment~.
Preferably, the proCe~Bor is proyrammed to determine
coordinates of a new target line head segment when the
di~tance between the point nearest to the spacial position
o~ the receiver an~ the di~tal point i~ les~ than said
fir~t pre-defined di~tance.
Preferably, ~he proce~or i~ programmed to delete the
coordinates of a tar~et line tail ~egment of the target
line when the coardinates of a new target line head ~3egrnent
are deter~ined to maintain a target line having a pre-
defined length.
In accordance with another aspect of the invention, there
i~ provided a method of displaying ~ repre~entation of an
area in a ~pace, the method i~cluding the ~teps of:
a) re~eiving m~pping data representing coordinate~
o~ va~iou~ point~ on a surface of at least one
o~ject in the space and 6toring the coordinate~
in memory;
b) receivin~ po~ition signal~ indicative of at least
fir~t and ~econd ~pacial position~ of a receiver
operable to move and to rec~ive the po~ition
~ignals in the ~pace;
c) cornputing a heading o~ the receiver from the
po~ition ~ignal~i
~ computing a viewpoint relative to at least one of
35the fir~t and ~econd ~pacial position~i and
CA 02212240 1997-08-01
-10-
e) producing a visual representation of the space,
as seen from the viewpoint in the direction of
the heading, the visual representation including
a representation of the object derived from the
coordinates of various points on the surface of
the object.
In accordance with another aspect of the invention, there
is provided a method of guidance in a space, the method
comprising the steps of:
a) receiving and storing in memory mapping data
representing the coordinates of various points
identifying a surface contour of at least one
object in the space;
b) receiving position signals indicative of at least
first and second spacial positions of a receiver
operable to move in a path in the space, and
operable to receive the position signals;
c) computing point positions of a plurality of
respective target line segments, relative to the
first and second spacial positions, to produce a
representation of a target line extending from at
least one of the first and second spacial
positions, the point positions being computed
such that the target line segments associated
with respective point positions do not extend
between the points representing the contour of
any object represented by the mapping data stored
in the memory at the time at least one point
position is computed, such that each of the point
positions is computed using mapping data
available at the time at which the point
positions are calculated; and
CA 02212240 1997-08-01
d) producing a signal representing a prediction of
the path of the receiver as indicated by the
point positions.
In effect, the apparatus and method according to the
invention provide a way of guiding a vehicle or even a
hand-held receiver by predicting a path the vehicle or
receiver is to take, on the basis of obstacle information
which may be previously stored and which may be gathered
during operation of the apparatus. The invention
contemplates including a worked area as obstacle
information, which allows the path of a farm vehicle, for
example, to be predicted with the knowledge of where the
vehicle has been, allowing the path to be predicted in such
a manner that the vehicle avoids areas already traversed.
This has applications in spraying crops, for example, where
the vehicle operator can be guided to avoid spraying areas
already sprayed, without the need for markers and the like
which are subject to weather conditions for visibility.
BRIEF DESCRIPTION OF THE SEVERAL VIEWS OF THE DRAWING
In drawings which illustrate embodiments of the invention,
Figure 1 is an overhead plan view of the work area
according to the first embodiment of the
invention;
Figure 2 is a block diagram of an apparatus according to
the first embodiment of the invention;
Figure 3 is a view of a display showing a perspective view
of a work area according to the first embodiment
of the invention;
CA 02212240 1997-08-01
Figure 4a is a schematic diagram of a mapping data record
format, according to the first embodiment of the
invention;
Figure 4b is a schematic diagram of a target line list,
according to the first embodiment of the
invention;
Figure 4c is a schematic diagram of an obstacle list,
according to the first embodiment of the
invention;
Figure 4d is a schematic diagram of a heading list,
according to the first embodiment of the
invention;
Figure 4e is a schematic diagram of a target ray list,
according to the first embodiment of the
invention;
Figure 5 is a flow chart illustrating a main algorithm,
according to the first embodiment of the
invention;
~5 Figures 6a and 6b depict a flow chart of a previous work
algorithm called by the main algorithm,
according to the first embodiment of
the invention;
~0 Figure 7 is a flow chart of a target line algorithm called
by the main algorithm, according to the first
embodiment of the invention;
Figure 8 is a flow chart of a closest segment algorithm
called by the target line algorithm, according to
the first embodiment of the invention;
CA 02212240 1997-08-01
Figure 9 is a flow chart of a point/segment distance
algorithm according to the first embodiment of
the invention;
Figure 10 i8 a flow chart of a target line segment
algorithm called by the target line algorithm,
according to the first embodiment of the
invention;
Figure 11 is a schematic representation of a calculation of
a new target line head segment according to the
target line algorithm;
Figures 12a 12b, and 12c depict a flow chart of an
obstacle routine called by the target line
segment algorithm, according to the first
embodiment of the invention;
Figure 13 is a flow chart of a segment crossing algorithm
called by the obstacle routine, according to the
first embodiment of the invention;
Figures 14a and 14b depict a flowchart of a bounding
rectangle algorithm according to the first
embodiment of the invention; and
Figure 15 is a flowchart of a visible square algorithm
according to the first embodiment of the
invention.
DETAI~ED DESCRIPTION
Fiqure 1
Referring to Figure 1, a field is shown generally at 10.
The field is bounded by a ditch 12, a fence 14, a grove of
trees 16 and a road 18. Within the field, there is a work
CA 022l2240 l997-08-Ol
-14-
area 20 in which a crop 22 is planted and in which there is
a weed area 15.
The crop 22 is sprayed by employing a vehicle 24 such as
a tractor to transport a spray boom 26 operable to spray
insecticide, for example, over the work area 20 until the
entire work area has been sprayed. It will be appreciated
that the ditch 12, fence 14 and grove of trees 16 are
landmarks which must be avoided by the vehicle and
therefore must be treated as obstacles while the road 18,
crop 22 and weed area 15 landmarks may be traversed by the
vehicle 24 and are not considered obstacles. The spray
boom 26 acts as a working device and may be replaced with
other implements without departing from the scope of the
invention.
According to this embodiment of the invention, the vehicle
24 is provided with a guidance apparatus 28 which guides
an operator of the vehicle to transport the spray boom 26
over the work area 20 such that portions 29 of the work
area already sprayed are not re-sprayed on successive
passes over the work area.
Figure 2
Referring to Figure 2, a block diagram of the guidance
apparatus 28, according to a first embodiment of the
invention, is shown. The apparatus includes a GPS receiver
shown generally at 32 and a computer 34.
The GPS receiver 32 includes a processor 36, an antenna 38,
a position output 40, a time output 42 and a status output
44. The antenna 38 is operable to receive signals from a
plurality of satellites in the conventional manner. These
signals are then used by the processor 36 to determine
geographical position coordinates of the antenna and to
determine a quality value associated with the geographical
CA 02212240 1997-08-01
position coordinates. The processor provides at the
position output 40, position signals providing a digital
representation of the geographical position coordinates in
the World Geodetic System (1984) datum, provides at the
time output 42 a digital representation of the time the
position coordinates that were derived and provides at the
status output 44 a digital representation of status
information which allows the quality of the geographical
position coordinates to be estimated.
The computer 34 includes a microprocessor 46, an
Input/Output (I/O) port 48, a Random Access Memory (RAM)
50, a Read Only Memory (ROM) 52, a keypad 54, a display
interface 56, and a display 58, all in communication with
the microprocessor 46.
In this embodiment, the keypad 54 has a work control
key 60, a driving mode key 62, a landmark control key 64,
a map control key 66, a perspective view control key 67, a
field control key 68 and a plurality of alphanumeric keys
69. The keypad also has a selection output 70. The keypad
54 is operable to provide signals representing an actuated
key, at the selection output 70.
The display interface 56 includes a display control input
72 for receiving display command signals from the I/O port
48 under the control of the microprocessor 46 running a
program entitled OpenGL, licensed by Microsoft Corporation.
The display interface 56 is operable to control the display
58 to simultaneously display a perspective view and an
overhead mapping view of the work area, as will be
explained below.
The I/O port 48 includes a display control output 74, a
position input 76, a time signal input 78, a status signal
input 80 and a selection input 82. The display control
output 74 is connected to the display control input 72 to
CA 022l2240 l997-08-Ol
-16-
communicate display command signals from the I/O port 48 to
the display control input 72 of the display interface 56.
The position input 76 is connected to the position output
40 for receiving the representation of the geographical
position data from the GPS receiver 32. The time signal
input 78 is connected to the time output 42 to receive the
time signal from the GPS receiver 32 and the status signal
input 80 is connected to the status output 44 for receiving
from the GPS receiver 32 the representation of the quality
of the position data. The selection input 82 is connected
to the selection output 70 for receiving signals
representing an actuated key of the keypad 54. The I/O
port thus acts as a receiver for receiving position signals
indicative of a spacial position of the vehicle.
The I/O port 48 is in communication with the microprocessor
46 by a conventional address and data bus 47. The I/O port
48 has read and write registers 84, 86, 88, 90, and 92
which are associated with display control output 74 and
inputs 76-82 respectively. By reading registers 86-90 in
the I/O port 48, the microprocessor 46 is operable to read
the geographical position data received at the position
input 76, to read the time data received at the time signal
input 78, to read the representation of the status received
at the status signal input 80 and to read the signals
representing an actuated key, received at the selection
input 82. By writing to register 84, the microprocessor 46
is operable to provide display command signals at the
display control output 74.
The ROM 52 has a plurality of registers in which are stored
blocks of program instruction codes for directing the
processor 46 to execute various algorithms. The stored
blocks of code implement a main algorithm 94, a coordinate
conversion algorithm 95 and a Kalman filter algorithm 96.
Within the blocks of code implementing the main algorithm
are included sub-blocks which implement a previous work
CA 02212240 1997-08-01
algorithm 98, a target line algorithm 100, a closest
segment algorithm 104, a point/segment distance algorithm
106, a target line segment algorithm 108, an obstacle
algorithm 110, a segment crossing algorithm 112, a bounding
rectangle algorithm 111, and a visible square algorithm
116.
The coordinate conversion algorithm 95 is implemented by
blocks of code which direct the microprocessor 46 to read
data representing a latitude and a longitude coordinate in
the World Geodetic System (1984) datum from the position
register 86 and to apply a conversion function, as
disclosed in ~GPS Satellite Surveying", 2nd Edition, by
Alfred Leick, published by John Wiley & Sons, Inc., and
incorporated herein by reference. The conversion function
provides UTM coordinate data representing vehicle position
in northing and easting coordinates, in the UTM coordinate
system.
The Kalman filter algorithm 96 is of the type described in
a book entitled "Applied Optimal Estimations", by Arthur
Gelb et al., available from the I.T. Press, Cambridge
Massachusetts incorporated herein by reference. In this
embodiment, the Kalman filter algorithm uses an internal
threshold distance value of one meter and, therefore,
ignores any position data received from the GPS receiver,
representing a change in position of less than one meter
from an immediately previous position.
The microprocessor 46 is in communication with the ROM 52
and is operable to execute the program instructions of
respective blocks of code to effect the functionality of
the algorithms indicated.
Fiqure 3
Referring to Figure 3, the instruction codes according to
the algorithms indicated in Figure 2 cooperate to direct
CA 02212240 1997-08-01
-18-
the microprocessor to send signals to the display 58 to
depict a perspective view 41 of the work area 30 to be
sprayed by the spray boom 26. The perspective view 41
includes representations of physical landmarks including
5 the ditch 12, fence 14, weed 15 and grove of trees 16. The
user identifies such landmarks prior to using the apparatus
and enters information regarding these landmarks through
the alphanumeric keys 69 on the keypad 54. In addition,
such information may be entered while the apparatus is in
use to cause the processor to store information relating to
landmarks and to generate display commands to cause
representations of such landmarks to be displayed on the
display. Such display commands are provided in a format
compatible with the OpenGL forming part of the display
interface.
In addition to the display of landmarks, the instruction
codes stored in the ROM 52 cooperate to direct the
microprocessor 46 to produce display commands which cause
the display to depict an indication of an area which has
already been sprayed, in this embodiment, portion 29, so
the operator can ascertain areas completed and areas which
are yet to be completed. This is particularly important in
spraying as typically, the operator cannot determine which
areas have been sprayed simply by looking at the ground, as
many sprays are invisible.
The instruction codes stored in the ROM 52 also cooperate
to direct the microprocessor 46 to produce display commands
which cause the display to depict a target pattern which,
in this embodiment, includes a target line 43 having a
plurality of target line segments 45, 55 including a head
segment 49 and a tail segment 51. The target line 43
provides a visual indication to the operator, of a path on
which to take the vehicle in order to spray the work area
in view of work already completed. The target line
segments 45, 55, etc., are calculated and displayed for an
CA 02212240 1997-08-01
-19-
area sufficiently far ahead of the vehicle to provide
advance notice to the operator, of any upcoming turns to
avoid landmarks or obstacles.
Referring back to Figure 2, the RAM 50 is in communication
with the microprocessor 46 and has a plurality of registers
or buffers which the microprocessor uses to store data
characterized and structured as positioning information
113, initial vehicle parameter list 114, a target line
parameter list 118, a perspective view parameter list 120,
an initial mapping data list 121, a user-inputted landmarks
list 124, a completed work list 128, a mapping data list
122, a target line point list 126, a working device width
buffer 130, a work control flag buffer 132, a smoothed
position buffer 134, a smoothed heading buffer 136, an
obstacle list 140, a heading list 142, a target ray list
146, temporary storage buffers 148, and a standard
deviation limit buffer 149.
Positioninq Information
The positioning information buffer 113 is used to store the
representations of the GPS position, time and status
information as received from the GPS receiver 32.
Initial Vehicle Parameter List
The initial vehicle parameter list 114 includes fields (not
shown) for storing data relating to vehicle width, position
of driver~s seat, position of the centre of the working
device, GPS antenna position, physical working device width
and overlap. Overlap is calculated as the working device
width less the actual distance between adjacent completed
work. Overlap must be less than one-half all of the
working device width. Generally, the initial vehicle
parameter list fields are filled by the microprocessor 46
with data supplied by the user, which the user determines
from known specifications of the vehicle, and which are
entered by the user at the keypad. This is done before the
CA 022l2240 l997-08-Ol
-20 -
main algorithm is executed. The driver's seat, the centre
of the working device and the GPS antenna position data is
provided in a Cartesian coordinate reference frame in
meters utilizing the GPS antenna 38 as the origin with the
5 normal, forward direction of travel of the vehicle
coincident with the positive y-axis.
Tarqet Line Parameter List
The target line parameter list 118 includes fields (not
shown) for storing data relating to the width of target
line segments, segment length, forward length of target
line, maximum target line length, number of rays, ray
spacing, maximum deviation distance, initial observation
angle and additional observation angle. The segment width
15 data specifies the width of the target line in relation to
other physical objects to be displayed. The segment length
data specifies the distance between the two end points of
a target line segment, which in this embodiment, is one
meter. In general, the segment length should be
20 approximately equal to the internal threshold distance used
in the Kalman filter which effectively sets the resolution
of the apparatus, indicating the minimum distance between
points in the space to be represented on the display. The
forward length of target line specifies the minimum
25 distance between the nearest segment to the vehicle and to
the head of the target line, along the path of the target
line, before a new segment is added to the target line.
The maximum target line length data specifies the maximum
length of the target line in relation to other physical
3 0 objects to be displayed. The number of rays sets the number
of rays that will be considered before constructing the
target line and must always be an odd number. The ray
spacing is automatically calculated by the microprocessor
46 when the user enters an initial observation angle, by
35 taking the quotient of the initial observation angle and
the number of rays according to the following relation:
CA 022l2240 l997-08-Ol
-21 -
Observation Anqle = angular spacing value (a)
(Number of Rays - 1)
The maximum deviation distance sets a threshold on the
distance the GPS antenna can move from the target line
5 before a new target line will be generated. The additional
observation angle specifies an additional angle in which
additional rays are calculated, beyond the initial
observation angle. The target line parameter list is
filled by the user before the main algorithm is executed,
by entering data through the keypad 54. Generally data in
the target line list is set according to the type of work
and user preferences for the display of the target line.
Perspective View Parameter List
15 The perspective view parameter list 120 includes fields
(not shown) for storing data relating to the distance from
the viewer to the far clipping plane, the field of view
angle in degrees in the horizontal direction, sky colour,
ground colour, ground grid colour and grid spacing.
Initial MaPDinq Data List
Referring to Figure 4a, the initial mapping data list 121
includes a plurality of records each having at least an
identification field 91, position fields 93, attribute
fields 102, and bounding rectangle fields 97. The ID field
91 is used to identify whether the record relates to a
tree, rock, pole, building, surface, fence, previous work,
etc. The position data fields 93 are used to store a
plurality of x and y coordinates, or pairs of coordinates
identifying a surface of an object within the space, the
pairs of coordinates representing heads and tails
respectively of landmark line segments approximating the
surface and representing points no less than approximately
one meter apart in this embodiment. In general, the
distance between points need not be any less than the
internal threshold distance used by the Kalman filter
algorithm 96. The RAM 50 thus acts as a receiver for
CA 02212240 1997-08-01
receiving and storing pairs of coordinates in a mapping
data list. The attribute fields 102 include fields for
storing geometrical attributes, in this embodiment sizes
and safety distances and for storing physical attributes,
for example colour, contrast and barrier/non-barrier
information. Barrier/non-barrier information relates to
whether or not the object to which the record relates acts
as a barrier to the vehicle. The bounding rectangle fields
97 are used to store maximum northing, minimum northing,
maximum easting, minimum easting values as boundary values
describing a bounding rectangle encompassing the object.
These are determined by locating the maximum and minimum
northing and easting value of all of the coordinates in the
record and storing the greatest northing value, greatest
easting value, least northing value and least easting value
and the boundary values. The processor is thus programmed
to compute and store in memory, the coordinates of a
bounding rectangle encompassing the surface of the object.
The memory thus acts as a mapping data receiver for
receiving and storing mapping data representing the
coordinates of various points identifying a surface contour
of at least one object in the space.
User Inputted Landmark List
The user-inputted landmarks list 124 includes a plurality
of records having fields of the type described above for
storing information regarding landmarks the user wishes to
view on the display and/or may wish to avoid while driving.
While the apparatus is in use, information regarding
landmarks is accumulated in the user-inputted landmark
list. Thus, the processor is programmed to receive mapping
data representing the coordinates of various points on a
surface of an object in the space.
CA 02212240 1997-08-01
Completed Work List
The completed work list 128 includes a plurality of
completed work records having fields of the type described
above for storing information regarding completed work.
S Each completed work record, however, is operable to store
only a maximum of twenty-five position points. While the
apparatus is in use, information regarding completed work
is accumulated in the completed work list 128.
MapPinq Data List
The mapping data list 122 includes a collection of records
including the initial mapping data records, landmark
records from previous operations of the apparatus and work
records from previous operations of the apparatus.
Tarqet Line Point List
Fiqure 4b
Referring to Figure 4b, the target line point list 126 is
used to store a plurality 127 of target line point records
129, 131, 133, each record having fields 135 and 137 for
storing number pairs (X1, Y1) representing northing and
easting coordinates respectively of a point. Each number
pair represents a target line segment of the target line.
A finite number of number pairs are stored, this number
depending on the forward length of the target line. The
target line list further includes a target line headpoint
index buffer 138 for storing a value identifying the target
line point record in which is stored a number pair
identifying the head of the target line. The target line
list further includes a target line point index buffer 139
which is used to store a value representing a currently
addressed target line point record. The target line point
list further includes a target line heading buffer 119 used
to store a number representing the current heading of the
target line represented by the target line point records.
CA 02212240 1997-08-01
-24 -
Workinq Device Width Buffer
The working device width buffer 130, is used to store a
value representing the width of the working device operated
by the vehicle to work the work area. In this embodiment,
the working device includes the spray boom 26.
Work Control Flaq Buffer
The work control flag buffer 132, is used to store a value
representing whether or not the working device is active.
The work control flag is set to active or inactive by the
actuation of the work control key 60, in conjunction with
the previous work algorithm 98.
Smoothed Position Buffer
The smoothed position buffer 134 is used to store a number
pair representing the current spacial position of the
vehicle as derived by filtering raw position data from the
positioning information buffer 113 under the Kalman filter
algorithm 96.
Smoothed Headinq Buffer
The smoothed heading buffer 136 is used to store a number
derived by filtering raw position data from the positioning
information buffer 113 under the Kalman filter algorithm
96.
Obstacle List
Referring to Figure 4c, the obstacle list 140 includes an
index field and plurality of obstacle segment records
having first and second point fields for storing first and
second points respectively, identifying a line segment of
an obstacle.
Headinq List
Referring to Figure 4d, the heading list 142 includes a
plurality of heading fields 143 for storing values
representing headings of the vehicle.
CA 02212240 1997-08-01
-25 -
Tarqet RaY List
Referring to Figure 4e, the target ray list 146 includes a
ray index buffer 147 and a plurality of ray line point
records 145, 151, etc, the actual number of rays being
5 specified by the contents of the number of rays field in
the target line parameter list 118. Each ray line point
record has fields 153, 155, for storing a number pair
(xl,yl) representing an end point of a ray line segment.
The ray index buffer is used to hold a ray index value
pointing to a currently addressed ray line point record.
Temporary Storaqe Buffers
The temporary storage buffers 148 include first, second,
third, fourth, fifth, and sixth temporary buffers. The
15 microprocessor 46 is operable to read and write data to
each of these buffers.
Standard Deviation Limit Buffer
The standard deviation limit buffer 149 is used to store a
value representing a standard deviation limit for use in
calculating whether or not a calculated standard deviation
value exceeds the standard deviation limit.
The microprocessor 46 is programmed to follow a start-up
2 5 algorithm (not shown) under which the microprocessor is
directed to store predetermined data into the buffers
described above, and to clear the contents of the work
control flag buffer 132. The processor is then directed to
the blocks of code implementing the main algorithm 94.
Main Alqorithm
Fiqure 5
Referring to Figure 5, generally, the main algorithm 94
directs the microprocessor to accept new position data from
35 the GPS receiver, accept new landmark data from the user,
update the completed work list, produce a new target line
CA 02212240 1997-08-01
segment if required, and update the display with the above
information.
Referring to Figures 2 and 5, upon entry into the code
implementing the main algorithm 94, block 150 directs the
microprocessor 46 to read the position data from the
position register 86, to read the time data from the time
input register 88, and to read the status data from the
status input register 90.
Block 157 then directs the microprocessor 46 to execute
code implementing the coordinate conversion algorithm 95
using the position data obtained in block 150. The
coordinate conversion algorithm 95 generates data
representing the northing and easting coordinates, in the
UTM position system, from the position data obtained in
block 150.
Block 152 then directs the microprocessor 46 to execute
code implementing the Kalman filter algorithm 96 using the
position data obtained in block 157 and the time data and
status data obtained in block 150. The Kalman filter
algorithm 96 generates data representing a smoothed vehicle
position and data representing a smoothed heading of the
vehicle, based on current and past position data. As part
of the Kalman filter algorithm, the microprocessor 46
stores the smoothed position data in the smoothed position
buffer 134 and stores the heading data in the smoothed
heading buffer 136. If the vehicle moves in reverse, the
microprocessor 46 calculates the heading as the forward
heading less 180 degrees and stores the calculated heading
value in the smoothed heading buffer 136. If the vehicle
stops, although the GPS will produce random positions due
to the nature of GPS, the Kalman filter algorithm will
recognize when the vehicle has stopped and will maintain
the last heading before the vehicle stopped, in the
smoothed heading buffer 136 and will maintain the last
CA 02212240 1997-08-01
position value obtained before the vehicle stopped in the
smoothed position buffer 134.
Block 154 then directs the microprocessor 46 to read the
selection input register 92 to determine whether or not the
landmark control key 64 has been actuated. If so, then
block 156 directs the microprocessor 46 to store user-
inputted landmark data in the user-inputted landmarks list
124, of Figure 4a. If the landmark control key 64 is not
actuated, the microprocessor 46 is programmed to proceed
with block 158 which directs the microprocessor 46 to read
the contents of the work control flag buffer 132 to
determine whether or not the work control flag is active.
If the work control flag is active the microprocessor 46 is
programmed to proceed to block 160 which directs the
microprocessor to call the previous work algorithm 98.
Otherwise, the microprocessor 46 is programmed to proceed
to block 162 to again read the selection input register 92
to determine if the work control key 60 has been actuated.
If the work control key has been actuated, the
microprocessor 46 is directed to proceed to block 160 where
it calls the previous work algorithm 98. If the work
control key has not been actuated or the previous work
algorithm 98 has just been completed, the target line
algorithm 100 is called at block 164 to produce a new
target line.
Upon completion of the target line algorithm 100, block 166
directs the microprocessor 46 to call the visible s~uare
algorithm 116 which directs the processor to send display
commands to the display interface to cause the display of
the perspective view 41 of at least a portion of the work
area in a space, as viewed from the present position as
determined from the smoothed position data and the smoothed
heading data stored in the smoothed position and smoothed
heading buffers 134 and 136 respectively. The display
commands also cause the display of an overhead plan view,
CA 02212240 1997-08-01
-28 -
including the target line such as shown in Figure 1, of the
area shown in the perspective view 41. The display is thus
operable to simultaneously display the perspective view and
a plan view of the target line. The main algorithm 94 is
then repeated.
Previous work alqorithm
Fiqures 6a and 6b
Generally, the previous work algorithm 98 directs the
microprocessor to load the completed work list with
position and boom width information which is displayed,
according to the main algorithm 94, as a sprayed or worked
area in the overhead and perspective views shown in Figures
1 and 3 respectively.
Referring to Figures 2 and 6a, the previous work algorithm
is shown generally at 98 and begins with block 168 which
directs the microprocessor 46 to read the contents of the
work control flag buffer 132 and to determine whether or
20 not it contains data representing an active state. If it
does not, block 169 directs the processor to write data
representing an active state into the work control flag
buffer 132 to active. Referring to Figures 4a and 6b,
block 171 then directs the processor to create a new
2 5 completed work record.
Block 173 then directs the processor to read the contents
of the smoothed position buffer 134 and the contents of the
working device width buffer 130 and to store these values
in the first position field and in the attribute field
respectively. Block 175 then directs the processor to
clear the heading list 142. Block 177 then directs the
processor to read the contents of the smoothed heading
buffer 136 and to store the contents in the heading list
142. The previous work algorithm 98 is then ended. In
other words, if the work control flag has not been
CA 02212240 1997-08-01
-29-
previously set, a new work record is created and the
heading list is initialized.
If at block 168 of Figure 6a, the work control flag buffer
contains data representing an active state, block 170
directs the microprocessor 46 to read the contents of the
selection input register 92 to determine whether or not the
work control key has been actuated. If the work control
key has been actuated, the microprocessor 46 is directed to
proceed to block 174 which directs the microprocessor 46 to
write data representing an inactive state into the work
control flag buffer 132. Otherwise, if the work control
key has not been actuated the microprocessor 46 is directed
to proceed to block 179 which directs the microprocessor 46
to count the number of position data points stored in the
current work record and to determine whether or not twenty-
four points of position data are contained therein.
If there are twenty-four position data points in the work
record, block 178 directs the processor to read the
contents of the smoothed position buffer 134 and store the
position stored therein in the work record. The work record
then contains 25 positions and is considered to be a
complete work record. Block 180 then directs the processor
to compute bounding rectangle maximum and minimum points
and store these points in thè completed work record. To do
this, the processor is directed to determine the maximum X
value Xmax of all the points in the work record and the
maximum Y value YmaX of all the points in the work record and
to determine the minimum X value Xmin of the points in the
work record and to determine the minimum Y value Ymin of all
the points in the work record to produce two points
identifying a bounding rectangle, the first point being
specified by Xmin and Ymin and the second point being
specified by Xmax and YmaX. The boundary points are then
stored in the completed work record. Thus, the processor
is programmed to compute bounding rectangle points
SENT BY:VANCOUVER ;10- 9-97 ; 3:26~M ; 650 W. GEORGIA ST.~ 819 953 9538;# 3
CA 02212240 1997-08-01
-30-
repre~enting the coordinate~ of a bounding re~tangle
encompa6sing the points in the completed work record and to
~tore the bounding rectan~le point~3 in as~30ciation with the
c~mpleted work reco~d.
~lock 182 then direct~ the proce~or to ~tore t~e work
re~o~d by appending it to the completed work list 128 of
Figure 4a. The proce~sor i~ then directed to blocks 171
thr~ugh 177 shown in Figure 6b which set ~p a new ~lank
completed work record, and the algori'chrn i8 ended. The
ef~ect of block~ 17~, 178, 180, lB~ and 171-177 is to limit
completed work re~ord~ ~o cont~in a maxi~um of twenty-five
po~ition point~, to append completed work records having
twenty-five po~ition points to the co~pleted work li~t and
to create a new ~o~pleted work record each time a completed
work record i8 appended to the completed work list. Thu~,
the proce6~0r i~ pro~ra~med to accumulate, in a completed
work record, poYition points of the vehicle, the po~ition
poin~s repre~enting positions ~hich the vehicle ha~
traver~ed. In other word~, the proces~or i~ programmed to
accumulate a predefined number of po6ition points in the
completed work record and ~tore the completed work record
in a completed work list when the completed work record
colltaill~ the predefined number of po~ition point~.
Referring back to Figure ~, if at block 17~, there are
les~ than 25 lap po~ition points in the completed work
record, the proce~or i~ ~irected to block 176 which
directs the proce~o~ to copy the heading ~t~red in the
~moothed heading buffer 136 into the heading li~t 142.
Block 184 ~hown in Figure 6~, then directs the proce~60r to
calculate ~he ~tandard deviation of the content~ o~ the
heading li~t 142 a~d to determine whethe~ or not such
standard deviation is le~ than or equal to the content~ of
the ~andard deviation limit buffer 149. If ~o, then the
perviou~ work algorithm is ende~ and the current ~moothed
pc~ition is not added to ~he co~pleted work record. If the
CA 02212240 1997-08-01
standard deviation is not less than the limit, the
processor is directed to blocks 173 through 177 which
direct the processor to add the current smoothed position
to the completed work record, clear the heading list 142
and add the current smoothed heading to the heading list
142. The algorithm is then ended.
Referring back to block 170 in Figure 6a, if at block 170
the work control key has been actuated then block 174
directs the processor to clear the work control flag by
writing a null value to the work control flag buffer 132.
slock 188 then directs the processor to copy the contents
of the smoothed position buffer 134 to the current
completed work record.
Block 189 then directs the processor to determine the
maximum X value Xm~ of all the points in the work record and
the maximum Y value YmaX of all the points in the work record
and to determine the minimum X value Xmin of all of the
points in the work record and to determine the minimum Y
value Ymin of all the points in the work record to produce
two points identifying a bounding rectangle, the first
point being specified by Xmin and Yminand the second point
being specified by X~ax and YmaX. The boundary points are
then stored in the completed work record.
Block 191 then directs the processor to store the work
record by appending it to the completed work list 128. The
pervious work algorithm is then ended. Thus, the processor
is programmed to accumulate points indicated by the
position signals, the points representing an area traversed
by the vehicle and the processor is programmed to
accumulate the points in a work record having a finite
length, the points identifying line segments of a work
swath produced by the vehicle and the processor is
CA 02212240 1997-08-01
programmed to store the work record in the completed work
list, which is included in the mapping data list.
Tarqet Line Alqorithm
Figure 7
Generally, the target line algorithm directs the
microprocessor to produce a new target line if one has not
already been produced. In addition, a segment will be
added to a current target line if a headpoint of that
segment does not lie within a predefined distance of an
obstacle, as determined by the obstacle algorithm. When a
target line is near an obstacle, any new segments will be
added such that the segments follow the contour of the
obstacle. In this embodiment, previous work is considered
to be an obstacle and, therefore, if the apparatus is used
in a field with an obstacle such as a retangular fence
which acts as a boundary between which the vehicle is
driven, the proximity of the previous work and the fence as
obstacles will result in the target pattern being generated
as a rectangular serpentine line. If the vehicle position
is such that the vehicle is surrounded by obstacles, target
line generation is halted. This situation may occur when
all work in the field has been completed. Finally, if the
vehicle's position exceeds a predefined distance from the
target line, a new target line beginning at the vehicle's
position will be initiated. This could occur if the
vehicle makes a 180-degree turn to pursue a new direction
at the boundary of the field and continues to proceed in
that new direction until the vehicle's position exceeds the
predefined distance from the target line headpoint.
Referring to Figures 2, 4b and 7, in the target line
algorithm 100, block 190 directs the microprocessor 46 to
determine whether or not a target line has already been
produced by reading the contents of the target line point
list 126 to determine whether or not the target line point
record addressed by the target line headpoint index buffer
CA 02212240 1997-08-01
138 shown in Figure 4b, contains a null value. If so, then
it is considered that no valid data is stored in the target
line point list 126 and the microprocessor 46 is directed
to block 192 which directs the microprocessor 46 to
initialize the target line by storing the contents of the
smoothed heading buffer 136 in the target line heading
buffer 119, storing the contents of the smoothed position
buffer 134 in the first target line point record 129 of the
target line point list 126 and by setting the contents of
the target line headpoint index buffer 138 and the contents
of the target line point index field to point to the first
target line point record 129.
If at block 190 the target line point record addressed by
the target line headpoint index buffer 138 does not contain
a null value, block 194 directs the microprocessor 46 to
call the closest segment algorithm 104 shown in Figure 8,
to determine which target line segment is nearest the
vehicle's position.
Closest Seqment Alqorithm
The closest segment algorithm directs the microprocessor to
determine which of the line segments forming the target
line is closest to the present position of the vehicle.
Referring to Figure 8, the closest segment algorithm 104
begins with block 300 which sets the contents of the target
line point index buffer 139 to that of the target line
headpoint index buffer 138. Block 302 then directs the
processor to retrieve from the target line point list 126
a first point addressed by the target line point index
buffer 139 and a second point immediately preceding the
point addressed by the target line point index buffer 139.
The first and second points thus represent a head and tail
respectively of a target line segment. In addition, the
microprocessor 46 is directed to retrieve and store in a
the first temporary buffer of the temporary storage buffers
CA 02212240 1997-08-01
-34 -
148, the number pair representing the vehicle's position,
from the smoothed position buffer 134. Block 304 then
directs the microprocessor to call the point/segment
distance algorithm 106 shown in Figure 9.
Point/Seqment Alqorithm
Fiqure 9
Referring to Figure 9, the point/segment distance algorithm
106 directs the microprocessor to calculate the distance
between a given point and a given line segment, where the
line segment may be a line segment of an obstacle or a
segment of the target line.
Referring to Figure 9, the point/segment distance algorithm
106 begins with block 204 which directs the microprocessor
46 to calculate a difference in X-coordinates, and a
difference in Y-coordinates for the segment, a segment
length and a distance value from the segment to the point.
The difference in X-coordinates, DX is calculated according
to the relation:
X=X2-X1
where X1 is the contents of the temporary register
holding the X-coordinate of the first point
of the segment; and
X2 is the contents of the temporary register
holding the X-coordinate of the second point
3 0 of the segment.
The difference in X-coordinates, DX, is stored in the
second temporary buffer of the temporary storage buffers
148. The difference in Y-coordinates is calculated
according to the equation:
CA 02212240 1997-08-01
DY=Y2-Y1
where Y1 is the content of the temporary register
holding the Y coordinate of the first part
of the segment; and
Y2 is the content of the temporary register
holding the Y coordinate of the second point
of the segment.
The difference in Y-coordinates, DY, is stored in the third
temporary buffer of the temporary storage buffers 148.
The segment length, L, is calculated from the difference in
Y-coordinates of the segment and the difference is
X-coordinates of the segment, using the following relation:
L=sqrt (DX*DX+DY*DY)
The calculated segment length value, L, is stored in the
fourth temporary buffer of the temporary storage buffers
148.
The distance, D, from the line segment to the point is
calculated according to the following relation:
D=(X-X1) *DX/L+(Y-Yl)*DY/L
The calculated distance value, D, is stored in the fifth
buffer of the temporary storage buffers 148.
Block 206 then directs the microprocessor 46 to determine
whether or not the distance value stored in the fifth
buffer of the temporary storage buffers 148 is less than or
equal to zero. If the distance is less than or equal to
zero, the nearest point on the segment to the point under
consideration is the tail point (X1, Y1) of the segment.
The microprocessor 46 is therefore directed to block 208 in
CA 02212240 1997-08-01
-36-
which a distance value is calculated according to the
following equation:
distance=sqrt((X1-X)A2 + (Yl-Y)A2)
If, at block 206, the distance value stored in the fourth
temporary register is not less than or equal to zero, block
210 directs the microprocessor 46 to read the distance
stored in the fifth temporary buffer of the temporary
storage buffers 148 and to read the segment length stored
in the third temporary register and determine whether or
not the distance value is greater than the segment length
value and if so, the nearest point on the segment to the
point under consideration is the headpoint (X2, Y2) of the
segment. The microprocessor is therefore directed to
proceed to block 212 which directs the microprocessor 46 to
calculate a distance value according to the relation:
distance=sqrt((X2-X)A2 + (Y2-Y)A2)
This distance value is stored in the fourth temporary
register.
If at block 210, the distance value is not greater than the
segment length value, the point under consideration is
considered to lie between the end points of the segment and
the perpendicular distance to the segment is calculated.
In this regard, block 214 directs the microprocessor 46 to
calculate a distance value according to the following
equation:
distance= (Y-Yl) *DX/L + (X-Xl) *DY/L
After calculating a distance value, block 216 directs the
microprocessor to store the calculated distance value in a
sixth temporary buffer of the temporary storage buffers
148. The microprocessor 46 is then directed to exit the
CA 02212240 1997-08-01
point/segment distance algorithm 106 and return to the
closest segment algorithm 104 shown in Figure 8.
Referring back to Figure 8, when the Point/Segment distance
algorithm is completed at block 304, block 221 directs the
microprocessor 46 to compare the distance calculated by the
point segment distance algorithm stored in the sixth
temporary buffer of the temporary storage buffers 148, with
the contents of a smallest distance register not shown and
to store the lesser of the distance calculated by the point
segment distance algorithm and the contents of the smallest
distance register (not shown), and to store the target line
point index value associated with the headpoint of the
target line segment associated with the smallest distance
value in a smallest index register not shown.
Block 219 then directs the processor to repeat blocks 300,
302, 304 and 221 until each target line segment has been
considered. This has the effect of updating the smallest
distance register to ultimately contain the smallest
distance value of all segments considered and the smallest
index register to contain the index or the associated
segment.
Block 223 then directs the microprocessor 46 to store the
smallest distance value in the second temporary buffer and
to store the target line point index value associated with
the smallest distance value in the third temporary buffer
of the temporary storage buffers 148. The closest segment
algorithm 104 is then ended and processing returns to the
target line algorithm 100 shown in Figure 7.
Referring back to Figure 7, upon calculating the distance
from the vehicle to the target line, and identifying the
nearest target line point, block 196 directs the
microprocessor 46 to read the maximum deviation distance
data stored in the target line parameter list 118, and the
CA 02212240 1997-08-01
-38 -
data representing the smallest distance stored in the
second temporary buffer of the temporary storage buffers
148. If the data representing the smallest distance value
is greater than the data representing the maximum deviation
5 distance, the microprocessor 46 is directed to proceed to
block 192, which initializes the target pattern as
described above. Otherwise, the microprocessor 46 is
directed to proceed to block 198 which directs the
microprocessor 46 to calculate the distance from the
nearest target line point as addressed by the contents of
the third temporary buffer of the temporary storage buffers
148 to the point addressed by the target line headpoint
index buffer 138 shown in Figure 4b, i.e., the point
representing the head of the target line head segment.
This is done by multiplying the segment length stored in
the target line parameter list by the number of points in
the target line list, between the nearest target line
point, i.e., the point representing the head of the target
line segment associated with the smallest distance and the
point representing the head of the target line.
Block 200 then directs the microprocessor 46 to determine
whether or not the distance calculated in block 198 is less
than the forward length of target line value stored in the
25 target line parameter list 118. If it is, the vehicle
position is considered to be near the headpoint of the
target line and block 202 directs the microprocessor 46 to
call the target line segment algorithm 108 shown in Figure
10 to generate a new target line segment. Otherwise, the
30 target line algorithm 100 is completed and the
microprocessor 46 returns to block 166 of the main
algorithm 94 shown in Figure 5. Thus, the processor is
programmed to determine which of the target line segments
has a headpoint corresponding to a position in space
35 nearest to the spacial position of the vehicle, as compared
to the positions in space of headpoints of the remaining
target line segments. In addition, the processor is
CA 022l2240 l997-08-Ol
-39-
programmed to determine the coordinates of a new distal
point, i.e. target line head segment when the sum of the
predefined distances between the point nearest to the
spacial position of the vehicle and the distal point is
5 less than a first predefined distance, the first predefined
distance corresponding to the forward length of target line
value stored in the target line parameter list 118.
Tarqet Line Seqment Alqorithm
Fiqure 10
Referring to Figure 10, the target line segment algorithm
108 directs the microprocessor to identify a safety square,
and to identify records having bounding rectangle fields
bounding areas common to the safety square, and to call the
15 obstacle algorithm to produce a new head segment of the
target line, where the head segment does not interfere with
obstacles within the safety square.
Fiqure 11
Referring to Figures 10 and 11, upon entry into the target
line segment algorithm 108, block 218 directs the
microprocessor 46 to read the target line head position 53
from the target line headpoint record stored in the target
line point list 126, to read the segment length stored in
25 the target line parameter list 118, and to read the maximum
working device width stored in the initial vehicle
parameter list 114. Block 224 directs the microprocessor 46
to call the bounding rectangle algorithm shown in Figures
14a and 14b.
Boundinq Rectanqle Alqorithm
Fiqures 14a and 14b
Referring to Figure 14a, Block 293 directs the processor to
write data representing an active state into a last
35 inputted segment flag buffer (not shown). Block 262 then
directs the processor to address the mapping data list 122
to locate a first record having an attribute field having
CA 02212240 1997-08-01
-40 -
a barrier flag set to active. Upon finding such a record,
block 263 then directs the microprocessor 46 to calculate
a safety width by adding the safety distance to the target
line segment length stored in the target line parameter
5 list and one-half of the maximum working device width
stored in the maximum working device width buffer 130. The
result is stored as the safety width, in the first
temporary buffer of the temporary storage buffers 148.
Referring to Figures 11 and 14a, Block 267 then directs the
microprocessor 46 to determine and store in temporary
registers Xmin, Xmax and Ymin, YmaX coordinates 252, 254, 256
and 258 of a safety square 259 centred at the distal point
or target line head position 53 and having sides of length
15 equal to twice the safety width. Thus, the processor is
programmed to compute the coordinates of a safety square
having a centre coincident with the distal point and sides
having a length of a-t least twice the first predefined
distance.
Block 264 then directs the processor to load the bounding
rectangle values of the record under consideration into
further temporary registers (not shown).
25 Block 266 directs the processor to compare the safety
square maximum X,max, Y1maX and minimum (X,min, Y,min) coordinates
to the maximum (X2max and Y2maX) and minimum coordinates of the
bounding rectangle of the record under (X2max Y2max)
consideration. If either of the maximum safety square X1max
30 and YlmaX coordinates is less than the respective values
representing the minimum X2min and Y2min or if either value
representing the minimum safety square X,min and Y,min
coordinate is greater than the respective values
representing the maximum X2max and Y2maX of the bounding
35 rectangle, the landmark associated with the record under
consideration is considered to be out of the range of the
safety square and is ignored, whereupon the processor is
CA 022l2240 l997-08-Ol
-41-
directed to block 278. Otherwise, the processor is
directed to block 268 of Figure 14b. Thus, the processor
is programmed to compare coordinates of the bounding
rectangle of the object with the coordinates of the safety
square to determine whether or not any portion of the
object is within the safety square.
Referring to Figure 14a, Block 278 directs the processor to
determine whether or not all records in the mapping data
list 122 have been examined. If all records have been
examined the processor is directed to exit the bounding
rectangle algorithm. Otherwise, the processor is directed
back to block 262 to examine the next record.
Referring to Figure 14b, at block 268 the processor is
directed to retrieve a pair of points from the position
data field 93 of the record under consideration. The pair
of points represent a line segment head and tail of a line
segment associated with the landmark or work swath
associated with the record under consideration. Block 270
then directs the processor to load the identified line
segment head and tail points into temporary registers (not
shown).
Block 272 then directs the processor to determine whether
or not either point of the identified line segment is
contained within the safety square, by comparing the head
and the tail points of the line segment to the minimum and
maximum X and Y coordinates of the safety square. If at
block 272, either point of the identified line segment is
contained within the safety square, block 283 directs the
processor to write data representing an inactive state into
the last inputted segment flag buffer and the processor is
directed to block 276. Otherwise, if neither of the points
identifying the line segment is contained within the safety
square, the processor is directed to block 287 which
directs the processor to determine whether or not the last
CA 022l2240 l997-08-Ol
-42 -
inputted segment flag buffer contains data representing an
inactive state. If the data represents an active state the
processor is directed to block 276. If the data represents
an inactive state, the processor is directed to block 274
which directs the microprocessor 46 to place the
coordinates of the line segment under consideration and the
safety distance associated with the segment under
consideration in an obstacle record and to append this
obstacle record to the obstacle list 140 shown in Figure
4c. Thus, the processor is programmed to, for objects
having bounding rectangle coordinates within the safety
square, determine pairs of coordinates of successive
points, representing heads and tails respectively of
respective obstacle line segments approximating the surface
15 of the object, and determine whether or not either of the
pairs of coordinates representing an obstacle line segment
is within the safety square, the safety square representing
at least a portion of the space. In addition, the
processor is programmed to place the coordinates of
20 obstacle line segments having at least one coordinate
within the safety square in respective obstacle records and
append the obstacle records to an obstacle list. If the
line segment is associated with initial mapping data, the
safety distance is obtained from the associated attribute
25 field whereas if the line segment is associated with
completed work, the safety distance is obtained from the
vehicle parameter list. Thus, line segments of the work
swath are treated as obstacle line segments. Block 276
directs the processor to consider whether or not all line
segments identified by the points stored in the record
under consideration have been considered and, if so, the
processor is directed to proceed to block 278 of Figure 14a
and continue processing.
Otherwise, the processor is directed to return to block 268
whereupon the next segment associated with the record under
consideration is considered. Thus, the bounding rectangle
CA 022l2240 l997-08-Ol
- -43 -
algorithm acts to direct the processor to append to the
obstacle list 140 a plurality of pairs of points which
identify segments of landmarks, which lie within the
bounding rectangle and which are to be considered obstacles
5 or barriers to the vehicle. It also directs the processor
to store with each landmark the safety distance associated
with the landmark.
Upon completion of the bounding rectangle algorithm after
block 278 thereof, the processor is directed back to the
block 227 of the target line segment algorithm 108 shown in
Figure 10.
Referring back to Figure 10, block 227 of the target line
15 segment algorithm 108 directs the processor to read the
obstacle list to determine whether or not the obstacle list
includes any records. If not, then block 229 directs the
processor to calculate a new target line head position
according to the relations:
X~ew = segment length * Cos (heading) + X
Ynew = segment length * Sin (heading) + Y1
2 5 where X1, Y1 represent the headpoint of
the target line head
segment;
heading is the heading value stored
in the buffer target line
heading buffer;
Xnew, Ynew is the new target line
headpoint
Thus, the processor is directed to determine the
coordinates of a first point in space disposed at a second
predefined distance from the spacial position, where the
40 second predefined distance is the segment length. Each
time the target line algorithm is run, the processor
effectively determines the coordinates of a successive
point in space spaced apart from the first point by the
CA 02212240 1997-08-01
--44 -
second predefined distance, the successive point
representing a target line ray.
The new target line head position Xnew, YneW is then stored in
the target line record and the target line point index
buffer 139 is updated to contain the location of the new
target line head position. A new target line head segment
has thus just been added to the target line list.
If the obstacle list 140 is not empty, block 228 of the
target line segment algorithm 108 then directs the
microprocessor to call the obstacle algorithm 110 shown in
Figure 12, which directs the microprocessor 46 to determine
whether or not an obstacle is located within user-defined
observation angles on opposite sides of the target line
heading.
Obstacle alqorithm
Fiqure 12
Referring to Figure 12, the obstacle algorithm 10 directs
the microprocessor to produce a plurality of possible
target line head segments, that is, possible distal target
line segments most distal to the current position, or view
point of the vehicle. The possible target line head
segments are produced at various angles to the current
target line heading and then segments which cross a line
segment of an obstacle or which extend beyond a
predetermined distance to a line segment of an obstacle are
eliminated, leaving only possible target line segments
which do not interfere with nearby obstacles. Of these
possible target line segments, the target line segment
having a headpoint disposed at the least distance from the
nearest line segment of the nearest obstacle is selected as
the new target line segment.
Referring to Figures 11 and 12, the obstacle algorithm
begins with block 230 which directs the microprocessor to
CA 022l2240 l997-08-Ol
-45 -
retrieve the heading of the target line from the target
line heading buffer 119.
Block 232 then directs the microprocessor 46 to calculate
5 possible rays from the headpoint of the target line head
segment identified by the target line headpoint index
buffer 138 by reading the segment length, the number of
rays, ray spacing, and the initial observation angle from
the target line parameter list 118.
In this embodiment, the initial observation angle is 60
degrees and, therefore, has boundaries 288 and 290 between
which the possible rays are calculated. In this
embodiment, the number of rays is five and, therefore, the
15 angular spacing value is 15 degrees. The rays thus extend
at multiples of 15 degrees on opposite sides of the heading
and, directly on the heading. Thus, the processor is
programmed to produce a list of points such that the
headpoints identify headpoints of target line rays at
20 multiples of a predefined angle to the current heading of
the distal target line segment.
Distal end points of respective rays 280, 281, 282, 284,
285 are calculated according to the following relations:
For N = 1 to Number of Rays
X~w =segment_length* cos(heading angle + Na) + X
Y~w =segment_length* sin(heading angle + Na) + Yl
where Xnew, YneW is end point of ray, segment
3 5 length is a value obtained
from the target line buffer,
heading angle is the
smoothed heading value
stored in the smoothed
heading buffer 136,
N is an integer between 0 and
2 and
CA 02212240 1997-08-01
-46-
Xl, Y1 is the current headpoint of
the target line.
(a) is the angular spacing value
Each of the rays has a common tail point, namely the end
point (Xl, Y1) of the target line head segment.
Using the end points of respective rays and the common tail
point, the microprocessor stores a plurality of sets of
number pairs in the target ray list 146 shown in Figure 4e,
where each set corresponds to a distal end point of a
respective ray. Thus, the processor is programmed to
produce a target ray list of points representing respective
headpoints of target line rays representing possible distal
target line segments, each of the points including an x
coordinate and a y coordinate.
Block 231 then directs the microprocessor to write data
representing an active state into a first obstacle flag
buffer (not shown).
Block 233 then directs the processor to retrieve a ray
point from the target ray list and to clear the first
temporary buffer of the temporary storage buffers 148. The
ray retrieved from the target ray list is addressed by the
contents of the ray index buffer 147 and, at this point in
the algorithm, the first ray line point record 145 is
addressed.
Block 235 then directs the processor to set the obstacle
list index to address the first obstacle record. Block 237
then directs the processor to call the segment crossing
algorithm shown in Figure 13.
CA 02212240 1997-08-01
Seqment Crossinq Alqorithm
Fiqure 13
Referring to Figure 13, the segment crossing algorithm 112
directs the microprocessor to use linear algebra principles
to find an intersection point of a line identified by the
end points of a segment under consideration and a line
identified by the end points of a target line segment. If
the intersection point is within the limits of the
coordinates of the points identifying each line, the
segments are considered to cross and the segment under
consideration is eliminated from consideration.
Referring to Figures 11 and 13, if the ray under
consideration is ray 285 and the landmark line segment
under consideration is segment 275, block 246 directs the
microprocessor to produce linear equations representing the
ray 284 and the object line segment 275 respectively, by
applying conventional mathematical methods to respective
end points of ray 284 as obtained from the target ray list
146 in Figure 4e and the object line segment 275 as
determined from the obstacle list 140 shown in Figure 4c.
After producing such equations, the equations are solved
using linear algebra, to obtain a solution which is a pair
of coordinates representing an intersection point 291 of
the lines represented by the equations, if an intersection
point exists.
Block 248 of the segment crossing algorithm then directs
the microprocessor 46 to determine whether or not the
intersection point 291 is between the coordinates of the
ray line and the object line respective segment, by
determining whether or not the X-coordinate of the solution
is between both X-coordinates of the ray 285 and both
X-coordinates of the object line segment 275 and by
determining whether or not the Y-coordinate of the solution
is between both Y-coordinates of the ray 285 and both
Y-coordinates of the object line segment 275. Thus, the
CA 02212240 1997-08-01
-48 -
processor is programmed to determine whether or not a
target line ray crosses the obstacle line segment by
producing linear equations representing the target line ray
and the obstacle line segment, and by solving the linear
equations to determine a point of intersection of the
target line ray and the obstacle line segment, and by
determining whether or not the point of intersection is
within respective X coordinates and respective Y
coordinates of the points identifying the target line ray
and the obstacle line segment. If the X and Y-coordinates
of the solution are within the indicated bounds, the ray
and object line segments are considered to cross and block
250 directs the microprocessor to remove the number pairs
representing the ray under consideration from the target
ray list 146 to eliminate the ray from further
consideration and directs the processor to write data
representing an active state into a ray eliminated flag
buffer (not shown). Thus, in Figure 11, the number pair
corresponding to ray 285 is eliminated from the target ray
list 146. Thus, the processor is programmed to eliminate
from the target ray list of points, headpoints identifying
target line rays which cross an obstacle line segment
identified by coordinates stored in the obstacle list. In
other words, the processor is programmed to eliminate from
the plurality of possible target line segments target line
segments which cross obstacle line segments within the
second pre-defined distance of the current position point.
If either the X or Y-coordinate of the solution is not
within the indicated bounds such as in the case of rays
280, 281, 282, 284 with respect to object line segment 275,
these rays and segment are considered not to cross and the
number pairs representing these rays are left intact in the
target ray list 146 for further consideration. The number
pairs associated with rays 280, 281, 282 and 284 are
therefore left intact in the target ray list 146 and the
segment crossing algorithm is ended. Effectively, the
CA 02212240 1997-08-01
-49 -
segment crossing algorithm and the obstacle algorithm code
direct the processor to compare each target line segment
with obstacle line segments within the second pre-defined
distance of the current position point to determine whether
any target line segment crosses an obstacle line segment.
Upon completion of the segment crossing algorithm 112, the
processor is directed back to block 239 of the obstacle
algorithm shown in Figure 12a, block 239 directs the
processor to read the ray elimination flag to determine
whether or not a ray has been eliminated. If so, block 241
directs the processor to increment the ray index and
proceed back to block 233 where the next ray in the target
ray list 146 is addressed.
If at block 239, the microprocessor finds that the ray
elimination flag has not been set, block 243 directs the
processor to calculate the distance between the end point
of the ray, as specified by the contents of the ray line
point record 145, and the segment under consideration.
Block 243 directs the microprocessor to pass the two points
identifying the current obstacle segment under
consideration and the end point of the current ray under
consideration to the point/segment distance algorithm 106
shown in Figure 9. As described above, the point/segment
distance algorithm 106 returns a distance value. Block 245
then directs the processor to compare this distance value
against the sum of the safety distance attributed to the
obstacle segment associated with the object and one-half of
the current boom width stored in the working device width
buffer, to determine whether or not the distance value is
less than this sum. If so, then block 247 directs the
processor to remove the number pair associated with the
current ray under consideration from the target ray list
146 to eliminate the ray from further consideration. The
processor is then directed to block 241 which directs the
processor to increment the ray index to point to the next
CA 02212240 1997-08-01
-50 -
ray in the target ray list. If at block 245, the distance
value is not less than the sum indicated then the number
pair associated with the current ray under consideration is
left intact in the target ray list 146. Thus, the
processor is programmed to eliminate from the target ray
list, headpoints identifying target line rays having
headpoints which are disposed nearer than a second
predefined distance to an obstacle line segment identified
by coordinates stored in the obstacle list. In other
words, the processor is programmed to eliminate from the
plurality of possible target line segments, each target
line segment having a headpoint no nearer than the safety
distance to the object. In the example shown in Figure 11,
rays 281, 282 and 284 have endpoints too close to the
object, therefore, the number pairs associated with rays
281, 282 and 284 are removed from the target ray list 146
leaving only the number of pairs associated with ray 280.
Thus, the processor is programmed to determine whether or
not the target line ray crosses any of the obstacle line
segments and whether or not the end point of the target
line ray, is within a second predefined distance of any of
the obstacle line segments where the second predefined
distance is the sum of the safety distance attributed to
the obstacle segment associated with the object and one-
half of the current boom width stored in the working devicewidth buffer 130.
Referring to Figure 12b, block 249 then directs the
processor to read the first obstacle flag buffer to
determine whether or not this is the first obstacle segment
considered. If so, block 251 directs the processor to
store the distance calculated in block 243 in the first
temporary buffer of the temporary storage buffers 148 and
to set the first obstacle flag to inactive.
If at block 249, the obstacle segment under consideration
is not related to the first obstacle, i.e., the first
CA 02212240 1997-08-01
obstacle flag is not set, block 253 directs the processor
to determine whether the distance calculated in block 243
is less than the distance value stored in the first
temporary buffer. If so, then the current distance is
transferred to the first temporary buffer. If not, then
block 255 directs the processor to review the current
obstacle record to determine whether or not all line
segments have been considered by the algorithm. If not,
then the processor is then directed to block 238 which
directs the processor to increment the obstacle list index
to point to the next record in the obstacle list. The
processor is then returned to block 235 of Figure 12a,
where the next segment identified by the currently
addressed obstacle list record is retrieved and considered
in the algorithm as described above.
Referring back to Figure 12b, if at block 255 all segments
have been considered, block 257 directs the processor to
determine whether or not the ray under consideration is the
first ray to be addressed by this portion of the algorithm.
If so, then block 260 directs the processor to transfer the
distance value stored in the first temporary buffer to the
second temporary buffer of the temporary storage buffers
148 and to store the current ray index value in the third
temporary buffer of the temporary storage buffers 148.
If at block 257, the ray under consideration is not the
first ray to be addressed by this part of the algorithm,
block 261 directs the processor to determine whether or not
the distance stored in the first temporary buffer is less
than the distance stored in the second temporary buffer and
if so, to proceed to block 260 to transfer the contents of
the first temporary buffer into the second temporary buffer
and to store the current ray index in the third temporary
buffer. After completion of block 260 or if the distance
contained in the first temporary buffer is not less than
the distance contained in the second temporary buffer,
CA 02212240 1997-08-01
-52 -
block 265 of Figure 12c directs the processor to determine
whether or not all rays left in the target line list have
been considered. If not, then block 241 directs the
processor to increment the ray index and the processor is
5 directed back to block 233 to retrieve the next ray in the
target ray list.
If at block 265, all rays have been considered, block 269
directs the processor to determine whether or not the third
temporary buffer has any contents, i.e., is undefined.
This would be the case where there are no rays left in the
target ray list. If the contents of the third temporary
buffer are defined, then block 279 directs the processor to
select as the new target segment, the ray identified by the
15 contents of the third temporary buffer, as this ray is
disposed at the least distance from an obstacle line
segment. The processor is then returned back to the target
line segment algorithm, shown in Figure 10. Thus, the
processor is programmed to select as the distal target line
20 segment, a target line ray having a headpoint disposed at
the least distance from an obstacle line segment.
Otherwise, at block 269 if the contents of the third
temporary buffer are undefined, block 271 directs the
processor to calculate two extra rays extending at plus and
25 minus 5 degrees respectively from respective boundaries 288
and 290 of the observation angle. As, in this embodiment,
the initial observation angle stored in the target line
parameter list 118, is 60 degrees, the two extra rays
adjacent the first observation angle boundary would extend
at 35 and -35 degrees respectively relative to the target
line heading. The extra rays so calculated are stored in
the target ray list.
Each time the processor encounters block 269, if no ray
points are stored in the target ray list 146, block 271
directs the processor to calculate two new rays at a
further 5 degree increment from the initial observation
CA 02212240 1997-08-01
angle boundaries. Block 273 then directs the processor to
determine whether or not the new rays calculated extend at
angles greater than the additional observation angle limit
stored in the target line parameter list. If the newly
calculated rays extend relative to the initial observation
angle boundaries at angles greater than the additional
observation angle limit, the algorithm is ended and the
processor terminates generation of the target line.
If at block 273, extra rays have been generated and have
been placed in the target ray list, block 277 directs the
processor to calculate the heading for the extra rays and
clears the first temporary buffer. The processor is then
directed back to block 235 where subsequent portions of the
algorithm are repeated.
The effect of block 271 and 273 is that new rays are
produced at + 5 degrees, + 10 degrees, + 15 degrees, etc.,
from the initial observation boundaries until at least one
ray is produced which allows the processor to reach block
269 with a ray point in the target ray list 146 or until
the new rays calculated extend at an angle which exceeds
the additional observation angle stored in the target line
parameter list 118. In other words, the processor is
programmed to determine whether or not the target ray list
146 is empty and if so, produce new target line rays having
angles which are multiples of a pre-defined angle from
boundaries of the initial observation angle until the
target ray list 146 includes at least one headpoint
identifying a target line ray which does not cross an
obstacle line segment and which is not nearer than the
second predefined distance to the obstacle line segment.
The effect of the obstacle algorithm is to store in the
third temporary buffer of the temporary storage buffers
148, the ray index of a ray identified in the target ray
list, such ray being the ray which will become the most
CA 02212240 1997-08-01
distal target line segment. Thus, in effect, the processor
is programmed to determine the coordinates of a successive
point in space spaced apart from the first point by the
second pre-defined distance, the successive point
representing a target line ray. In other words, the
processor is programmed to select coordinates identifying
a target line segment nearest at least one obstacle line
segment of the object as those which identify a target line
head segment.
As the target line point list is only capable of storing a
finite number of number pairs, each time a new target line
head segment is added, a target line tail segment is
deleted from the target line print list. Thus, the
processor is programmed to delete the coordinates of a
target line tail segment of the target line when the
coordinates of a new target line head segment are
determined to maintain a target line having a pre-defined
length.
At any time, the processor may receive and store new
mapping data in the mapping data list. This new mapping
data is thus taken into account each time a new target line
head segment is calculated. Thus, the processor is
programmed to receive and store new mapping data after at
least one point position is computed such that the
calculation of subsequent point positions is performed
using the initial mapping data and the new mapping data.
The algorithms implemented by code stored in the ROM,
except the code for implementing the visible square
algorithm, provide direction to the processor to compute
point positions of a plurality of respective target line
segments, relative to the first and second spacial
positions, to produce a representation of a target line
extending from at least one of the first and second spacial
positions, the point positions being computed such that the
CA 02212240 1997-08-01
-55-
target line segments associated with respective point
positions do not extend between the points representing the
contour of any object represented by the mapping data
stored in the memory at the time at least one point
position is computed, such that each of the point positions
is computed using mapping data available at the time at
which the point positions are calculated.
Visible Square Alqorithm
Referring to Figure 15, the visible square algorithm 116 is
called by block 166 of the main algorithm shown in Figure
5. Generally, the visible square algorithm acts to send to
the display interface, information regarding landmarks and
the target line which are with the field of view determined
by the perspective view parameter list 120. The particular
items to be viewed in the perspective display are
determined according to the visible square algorithm shown
in Figure 15, which determines which records of the user-
inputted landmark list (124), completed work list (128) and
mapping data list (122), have points located within the
portion of the work area to be viewed and which forwards
such points in OpenGL commands to the display interface.
This acts as a filtering procedure for filtering points to
be sent to the display such that only those points within
the required viewing area are sent to the display. This
has the effect of relieving the display interface of the
task of filtering, thereby more rapidly producing an
updated perspective view.
Block 292 directs the microprocessor 46 to set variables
Xlmax, X1min, YlmaX and Ylmin to variables representing the
coordinates of the area to be viewed. These variables are
determined from the present position of the vehicle
(smoothed position buffer) and the parameters stored in the
perspective view parameter list 120, and represent the
viewing coordinates of the area to be depicted on the
display.
CA 022l2240 l997-08-Ol
-56-
Block 294 then directs the microprocessor 46 to retrieve a
record from the mapping data list 122, the target line
point list 126, the user-inputted landmarks list 124, or
the completed work list 128. When a record is retrieved
5 from the completed work list, the processor calculates a
swath width from the vehicle position stored in the
completed work record and the contents of the working
device width buffer 130. Effectively, two points are
produced, on opposite sides of the vehicle position, at
right angles to the direction of travel, or vehicle
heading. The processor is thus programmed to compute, from
the position points of the vehicle, position points
traversed by a working device transported by the vehicle in
the space.
Block 296 then directs the processor 46 to determine the
minimum and maximum X values and the minimum and maximum Y
values in the record and to assign these values to
variables X2min, X2max, Y2min, Y2maX respectively. This has the
20 effect of assigning the ranges of points within the record.
Block 298 then directs the processor to determine whether
the maximum X point in the record is less than the minimum
X viewing coordinate, or the minimum X point of the record
25 iS greater than the maximum X viewing coordinate, or the
maximum Y point in the record is less than the minimum Y
point of the viewing coordinates, or the minimum Y point of
the record is greater than the maximum Y viewing
coordinate, and if so, to direct the processor to block 303
which directs the processor back to block 294. Otherwise,
the processor is directed to block 301. Effectively, block
298 directs the processor to determine whether or not any
landmarks indicated by the record under consideration lie
outside the viewing coordinates and if so, to ignore such
3 5 landmarks.
CA 02212240 1997-08-01
Block 301 is reached when all points contained in the
record under consideration lie within the viewing area.
This block directs the processor to send a display command,
in the OpenGL language, to the display interface 56. The
display interface further performs its own filtering of
points to create the display. The display command includes
a view point or point from which the perspective view is
seen which is computed relative to a special position of
the vehicle. Thus the processor is programmed to produce
commands recognizable by the display for causing the
display to produce a visual representation of the space, as
seen from the viewpoint in the direction of the heading,
the visual representation including a representation of the
object derived from the coordinates of various points on
the surface of the object.
The display command further includes instructions to
display at least one target line segment extending at the
heading between the view point and the headpoint. Thus,
the processor is programmed to identify the coordinates of
an area representing a sub-portion of the space and to send
to the display commands including the coordinates of
objects in the mapping data list, where the coordinates
identify points within the area, such that representations
of the objects are displayed in the perspective view.
Thus, the processor is programmed to divide the initial
mapping data and the new mapping data into sub-portions of
coordinates of points representing the surface contour of
objects, where the surface contours are within a
corresponding sub-portion of the space.
The display shown at 58 in Figure 3 thus acts as a display
for displaying a visual representation of at least a
portion of the space, in response to the target line
display command, the visual representation including the
viewpoint, the headpoint and the target line segment
extending at the first heading between the viewpoint and
CA 02212240 1997-08-01
-58 -
the headpoint. The visual representation is effectively a
virtual reality representation of the space and is seen as
perspective view of the space, the perspective view
including the viewpoint, the headpoint and the target line.
5 The target line acts as a prediction of the path of the
vehicle in view of obstacles which may be in the path of
the vehicle. The path is predicted on the basis of
information available at the instant a new target line
segment point position is calculated. Thus, the target
line is dynamically generated.
It may also be said that the processor is programmed to
produce commands to the display for the display to display
in the perspective view, representations of the successive
points in space and a target line having segments extending
between respective pairs of the representations of
successive points in space, the target line segments
including a distal target line segment most distal to the
viewpoint, the distal target line segment having a current
heading.
It will be appreciated that blocks 294, 296, 298 and 303
form a loop which has the effect of directing the processor
to examine each record in each list to determine whether or
not it should be used in the display of the area viewed by
the operator, and if so, to cause an appropriate display
command to be sent to the display interface 56.
Alternatives
Alternatively, the GPS receiver may be replaced with a GPS
receiver having a VHF receiver for receiving differential
GPS signals used to correct the signal produced by
conventional GPS to overcome selective tuning to produce
more accurate position signals.
CA 022l2240 l997-08-Ol
-59-
In effect, the apparatus and method according to the
invention provide a way of guiding a vehicle or even a
hand-held receiver by predicting a path the vehicle or
receiver is to take on the basis of obstacle information
5 which may be previously stored and which may be gathered
during operation of the apparatus. The invention
contemplates including a worked area as obstacle
information, which allows the path of the vehicle to be
predicted with the knowledge of where the vehicle has been,
allowing the path to be predicted in such a manner that the
vehicle avoids areas already traversed. This has
applications in spraying crops, for example, where the
vehicle operator can be guided to avoid spraying areas
already sprayed, without the need for markers and the like
15 which are subject to weather conditions for visibility.
While specific embodiments of the invention have been
described and illustrated, such embodiments should be
considered illustrative of the invention only and not as
limiting the invention as construed in accordance with the
accompanying claims.
