US006496189B1
`
`
`
`
`
`
`
`
`United States Patent
`(12)
`US 6,496,189 B1
`(10) Patent No.:
`
`
`
`
`
`
`
`
`Dec. 17, 2002
`(45) Date of Patent:
`Yaron etal.
`
`
`
`
`
`
`
`
`
`
`(54) REMOTE LANDSCAPE DISPLAY AND
`PILOT TRAINING
`
`
`
`
`
`(75)
`
`
`
`
`(*) Notice:
`
`
`
`Inventors: Ronnie Yaron, Kadima; Ofer Shor, Tel
`
`
`
`
`
`
`Aviv, both of (IL)
`
`
`
`
`
`
`
`
`
`(73) Assignee: Skyline Software Systems Ltd., Givat
`
`
`Shmuel (IL)
`
`
`
`
`
`
`Subject to any disclaimer, the term of this
`
`
`
`
`patent is extended or adjusted under 35
`
`
`
`U.S.C. 154(b) by 0 days.
`
`
`
`
`
`(21) Appl. No.: 09/258,663
`
`
`
`
`Filed:
`Feb. 26, 1999
`(22)
`
`
`
`
`
`‘att
`
`
`Dat
`Related U.S. Application
`
`
`
`
`Pphcatton
`eave
`mara
`
`
`
`
`
`
`
`
`
`(63) Continuation-in-part of application No. 08/939,948,filed on
`
`
`
`
`
`
`
`Sep. 29, 1997, now Pat. No. 6,111,583.
`
`
`
`
`
`(51)
`Int. Cl’
`GO6T 17/00
`(52) US. Che
`cecceccssscsenen|345/428:345/582: 345/419
`
`
`
`
`Fi ld f Sah— ,
`345mn19. 582
`58
`
`
`
`
`
`
`
`
`
`0 315/498,345/96,44387O1 456: 70107
`(58)
`Field
`
`
`
`
`
`
`
`;
`ae
`“_
`;
`
`
`
`
`
`
`References Cited
`(56)
`
`
`
`U.S. PATENT DOCUMENTS
`
`
`
`4,070,705 A *
`1/1978 Lockwoodetal. ......... 364/200
`
`
`
`
`
`
`4,359,733 A * 11/1982 O'Neill 0. 342/36
`
`
`
`
`
`
`4,940,972 A
`7/1990 Mouchotetal. ..
`.» 340/747
`
`
`
`
`
`
`
`
`5,550,959 A
`8/1996 Freeman...........
`we. 395/127
`
`
`
`
`
`
`
`5,566,073 A
`10/1996 Margolin .........cce 364/449
`
`
`
`
`
`5,652,863 A *
`7/1997 Asenio et al.
`......... 395/497.04
`
`
`
`
`
`
`
`
`
`
`
`
`6/1998 Migdalet al. ......... 345/430
`5,760,783 A *
`8/1998 Viebahnetal. ............. 340/974
`5,798,713 A *
`
`
`
`
`
`
`
`
`
`
`
`3/1999 Migdal et al... 345/423
`5,886,702 A *
`8/2000 Reberet al. we. 345/327
`6,111,568 A *
`
`
`
`
`
`OTHER PUBLICATIONS
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`“7Buffer,” Caroline Jelinek, Mar. 24, 1996—Materials col-
`
`
`
`
`
`
`
`lected from the World Wide Web—Addressed http://www.c-
`
`s.unc.edu/~bryan/bsg/TechMan/zbuffer.html.
`
`
`
`
`
`
`
`“1.1 Photo-realistic Image Synthesis,” Gary Shea, May 27,
`
`
`
`
`
`
`
`1995—Materials collected from the World Wide Web—
`
`
`Addressed:
`http:/Avww.xmission.com/~shea/thl/
`node5.html#Section0041.
`
`* cited by examiner
`
`
`
`Primary Examiner—Mark Zimmerman
`
`
`
`
`Assistant Examiner—Lance W.Seale
`
`
`
`y
`
`(74) Attorney, Agent, or Firm—Duane Morris LLP
`
`
`
`
`
`
`
`ABSTRACT
`(57)
`
`
`
`
`
`
`
`
`A method of providing data blocks describing three-
`dimensionalterrain to a renderer. The data blocks belong to
`
`
`
`
`
`
`
`a hierarchical structure which includes blocks at a plurality
`
`
`
`
`
`
`
`of different resolution levels. The method includes receiving
`
`
`
`
`
`
`
`
`from the renderer one or more coordinates in the terrain
`
`
`
`
`
`
`
`
`along with indication of a respective resolution level, pro-
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`viding the renderer with a first data block which includes
`
`
`
`
`
`
`
`data corresponding to the one or more coordinates, from a
`
`
`
`
`
`
`
`
`local memory, and downloading from a remote server one or
`
`
`
`
`
`
`
`
`more additional data blocks which include data correspond-
`
`
`
`
`
`
`
`
`
`ing to the one or more coordinatesif the provided block from
`
`
`
`
`
`
`
`
`the local memoryis not at the indicated resolution level.
`
`
`
`
`
`
`24 Claims, 9 Drawing Sheets
`
`
`
`
`
`
`
`PILOT TRAINER
`ON PROCESSOR
`
`
`2
`
`
`
`
` 1S
`
`
`
`FETCH PILOT
`
`
`RAINER PACKAGE
`
`
`FROM SERVER
`
`
`
`SE
`FETCH ROUTE CATALOG
`
`
`
`
`
`AND HEADER RECORD
`
`
`
`
`
`
`
`
`
`
` PROMPT USER
`
`|
`
`
`
`TO CHOGSE
`
`
`ROUTE FROM
`
`
`CATALOG
`
`
`
`
`ACTIVATE
`NAVIGATOR
`
`|
`
`WITH ROUTE !
`
`
`ACTIVATE
`RENDERER
`
`
`
`
`
`
`
`ACTIVATE CACHE
`MANAGER
`
`
`WITH STARTING
`POINT OF
`
`ROUTE
`
`
`
`
`
`
`
`
`
`Page 1 of 20
`
`Unified Patents Exhibit 1028
`
`Page 1 of 20
`
`Unified Patents Exhibit 1028
`
`

`

`U.S. Patent
`
`Dec. 17, 2002
`
`Sheet 1 of 9
`
`US 6,496,189 B1
`
`
`
`FIG.1
`
`LOroo] 24
`
`CEPRyor
`
`
`
`aSosPNSS
`
`
`
`
`
`
`
`
`Page 2 of 20
`
`Unified Patents Exhibit 1028
`
`Page 2 of 20
`
`Unified Patents Exhibit 1028
`
`

`

`U.S. Patent
`
`
`
`
`Dec. 17, 2002
`
`
`
`
`
`Sheet 2 of 9
`
`
`US 6,496,189 B1
`
`
`
`
`
`
`
`
`(0, 20.000
`
`
`0, 30.000
`
`
`
`
`
`
`
`
`
`
`
`20.000, 30.000)
`
`
`
`
`
`
`
`
`
`40
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`LEVEL
`
`
`
`
`
`Page 3 of 20
`
`Unified Patents Exhibit 1028
`
`
`
`
`
`
`44D
`
`
`
`4
`
`Page 3 of 20
`
`Unified Patents Exhibit 1028
`
`

`

`U.S. Patent
`
`
`
`
`Dec. 17, 2002
`
`
`
`
`
`Sheet 3 of 9
`
`
`US 6,496,189 B1
`
`
`
`
`FIG. 3
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`RECEIVE
`
`IMAGES
`
`
`
`CUT IMAGES
`
`
`INTO BLOCKS
`
`
`
`PREPARE HIERARCHY
`
`
`OF RESOLUTION LEVELS
`
`
`
`
`ALIGN BLOCKS
`
`
`
`
`COMPRESS BLOCKS
`
`
`
`
`ADD OBJECTS
`
`
`
`Page 4 of 20
`
`Unified Patents Exhibit 1028
`
`Page 4 of 20
`
`Unified Patents Exhibit 1028
`
`

`

`U.S. Patent
`
`
`
`
`Dec. 17, 2002
`
`
`
`
`
`Sheet 4 of 9
`
`
`US 6,496,189 B1
`
`
`
`
`
`FIG. 4
`
`
`fo
`
`
`
`64
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
` (103622, 9457.6,750eet
`KENNEDY AIRPORT: LANDING
`
`
`
`
`
`
`
`
` GREAT CANYON: FLIGHT
`
`(10367.8,9512.8,749)
`
`
`
`
` YMS AIRPORT LANDING
`
`
`
`
`
`SPEED=152—
`
`
`
`
` ~~.
`
`
`BERMUDA HORROR FLIGHT
`
`.A
`
`A/
`
`\A
`
`\ \
`
`Page 5 of 20
`
`Unified Patents Exhibit 1028
`
`Page 5 of 20
`
`Unified Patents Exhibit 1028
`
`

`

`
`U.S. Patent
`
`
`
`
`
`Dec. 17, 2002
`
`
`
`
`Sheet 5 of 9
`
`
`
`US 6,496,189 B1
`
`|
`
`
`
`
`
`JHOVO
`
`
`
`
`
`
`aanNENEGIEYOLVOIAYN||bl~ZLOL|Lou
`
` !|!||NOLLOINNODNOLLOJNNOD7!dOdO!||||||]j
`
`eemeryeeeEEE027°
`i)zrDLozG‘Old
`
`
`
`AMOWINeo|LR][anes
`
`WAdGOW
`
`YSANASOL
`
`9¢
`
`
`
`Page 6 of 20
`
`Unified Patents Exhibit 1028
`
`Page 6 of 20
`
`Unified Patents Exhibit 1028
`
`
`

`

`U.S. Patent
`
`
`
`
`Dec. 17, 2002
`
`
`
`
`
`Sheet 6 of 9
`
`
`US 6,496,189 B1
`
`
`
`YES
`
`
`
`
`IS
`
`
`PILOT TRAINER
`
`ON PROCESSOR
`
`?
`
`
`
`NO
`
`
`
`FIG. 6
`
`
`
`
`FETCH PILOT
`
`TRAINER PACKAGE
`
`
`FROM SERVER
`
`
`
`FETCH ROUTE CATALOG
`
`
`
`
`
`
`AND HEADER RECORD
`
`
`
`
`
`
`
`
`PROMPT USER
`
`
`TO CHOOSE
`
`
`ROUTE FROM
`
`CATALOG
`
`ROUTE
`
`
`ACTIVATE
`
`NAVIGATOR
`
`
`WITH ROUTE
`
`
`ACTIVATE
`RENDERER
`
`
`
`
`
`
`ACTIVATE CACHE
`
`MANAGER
`
`WITH STARTING
`
`
`POINT OF
`
`
`
`
`Page 7 of 20
`
`Unified Patents Exhibit 1028
`
`Page 7 of 20
`
`Unified Patents Exhibit 1028
`
`

`

`U.S. Patent
`
`
`
`
`Dec. 17, 2002
`
`
`
`
`
`
`Ex
`
`
`
`
`
`c
`S
`oO
`rors
`
`
`
`MBN
`
`*
`O
`—
`
`
`
`
`
`
`
`
`Sheet 7 of 9
`
`
`
`
`
`
`.
`S
`
`US 6,496,189 B1
`wsYY“opYeLesYsWY4, ZiWiig, 4
`
`
`
`
`
`
`
`SS NS
`
`YfoYWY.
`LysYe
`
`
`
`
`
`Page 8 of 20
`
`Unified Patents Exhibit 1028
`
`Page 8 of 20
`
`Unified Patents Exhibit 1028
`
`

`

`U.S. Patent
`
`
`
`
`Dec. 17, 2002
`
`
`
`
`
`Sheet 8 of 9
`
`
`US 6,496,189 B1
`
`
`
`
`
`
`
`
`
`122
`
`
`
`
`BLOCK Y
`
`CURRENTLY NEEDED
`BY RENDERER
`
`
`2
`
`
`
`
`FIG. 8
`
`
`
`
`
`
`
`
`
`
`
`
`DOWNLOAD 4 LEVEL-1 BLOCKS L~102
`
`
`
`
`
`
`
`
`SURROUNDING STARTING POINT
`
`
`
`
`RENDERER REQUEST
`RECEIVE BLOCK Y
`
`
`
`(BLOCK X, LEVEL=N)
`FROM TCP CONNECTION”-[
`1
`104
`yo
`|
`
`
`
`
`
`J=LEVEL OF HIGHEST LEVEL
`NO
`OF ANCESTOR IN CACHE MEMORY
`
`
`
`
`
`106
`
`
`
`a —
`
`
`
`
`
`PROVIDE RENDERER WITH LEVEL
`
`
`
`
`
`
`
`J ANCESTOR OF BLOCK x
`
`
`
`
`
`
`
`ADD ANCESTORS OF LEVELS
`
`
`PROVIDE BLOCK
`
`
`
`
`|J+1,..., NTC DOWNLOAD QUEUE
`
`
`
`
`
`Y TO. RENDERER
`|
`"
`-
`
`124
`\t08
`
`
`
`
`
`
`STORE BLOCK Y
`IN CACHE MEMORY
`
`
`
`
`
`
`
`
`ALL TCP
`NO ouicong
`
`
`
`IN USE?
`
`
`
`
`
`
`
`VES
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`DISCARD AN OUT
`
`
`
`OF RANGE BLOCK
`
`128
`
`
`
`
`
`112
`
`
`
`
`
`[K=LOWEST LEVEL OF
`
`
`BLOCK IN QUEUE
`
`
`
`
`ALL
`
`
`SURROUNDING
`
`
`BLOCKS IN
`
`CACHE?
`
`i NO
`
`
`
`
`
`
`
`
`
`
`
`
`
`K=LOWEST LEVEL FOR WHICH NOT ALL
`
`
`
`
`SURROUNDING BLOCKS ARE IN CACHE
`
`
`
`
`
`114|BLOCK X = LAST ENTERED
`a
`LEVEL-K BLOCK
`—
`
`
`
`
`
`
`To
`
`
`
`
`SEND DOWNLOAD ORDER FOR
`NO A LEVEL~K BLOCK NOT IN CACHE
`Ne BLOC
`
`
`
`
`
`
`
`
`
`
`X WITHIN
`RANGE?
`
`
`
`
`
`
`
`118
`SEND DOWNLOAD
`
`
`
`
`“|ORDER FOR BLOCK X
`
`
`
`
`
`
`
`
`
`
`
`
`
`120
`
`
`
`
`REMOVE ORDERED
`
`
`BLOCK FROM QUEUE
`
`
`
`Page 9 of 20
`
`Unified Patents Exhibit 1028
`
`Page 9 of 20
`
`Unified Patents Exhibit 1028
`
`

`

`U.S. Patent
`
`
`
`
`Dec. 17, 2002
`
`
`
`
`
`Sheet 9 of 9
`
`
`US 6,496,189 B1
`
`
`
`
`IN
`
`
`
`ORDER BLOCKS OF
`
`
`
`LEVELS J+1 TON
`
`154
`
`
`
`192
`
`
`
`LEVEL J
`
`
`LEVEL J-+1
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`FIG. 9
`
`Page 10 of 20
`
`Unified Patents Exhibit 1028
`
`Page 10 of 20
`
`Unified Patents Exhibit 1028
`
`

`

`
`
`US 6,496,189 B1
`
`
`
`
`
`
`
`
`1
`REMOTE LANDSCAPE DISPLAY AND
`
`
`
`PILOT TRAINING
`
`
`CROSS-REFERENCE TO RELATED CASE
`
`
`
`
`
`
`
`
`This is a continuation-in-part of U.S. patent application
`
`
`
`
`
`
`
`
`
`
`Ser. No. 08/939,948,filed on Sep. 29, 1997 now USS. Pat.
`
`
`No. 6,111,583.
`FIELD OF THE INVENTION
`
`
`
`
`
`
`
`
`The present invention relates generally to terrain displays,
`
`
`
`
`
`
`and specifically to computerized displaying of real-life
`
`
`
`three-dimensional images ofterrain.
`BACKGROUND OF THE INVENTION
`
`
`
`
`
`
`
`
`
`
`
`Pilots frequently wish to plan their flight route ahead of
`
`
`
`
`
`
`
`
`
`time and familiarize themselves with the points they plan to
`
`
`
`
`
`
`
`
`
`
`pass and approach. Mapsand flight charts are used to plan
`
`
`
`
`
`
`
`
`
`routes before actually flying. However, not all pilots can
`
`
`
`
`
`
`
`
`
`easily appreciate all the features and difficulties of a route
`
`
`
`
`
`
`
`from a map. Furthermore, some information may not appear
`
`
`
`
`
`
`
`
`
`on the map in sufficient detail. For this reason, Jeppesen
`
`
`
`
`
`
`
`Sanderson Inc., of Englewood, Colorado, provides pilots
`
`
`
`
`
`
`with actual photographs of runway environments together
`
`
`
`
`
`
`
`with graphical presentations of terrain and other obstacles,
`
`
`
`
`
`
`
`as well as other pertinent local traffic information.
`
`
`
`
`
`
`
`
`Flight simulators allow pilots to practice flying without
`
`
`
`
`
`
`
`
`
`leaving the ground. The simulator shows the view seen by
`
`
`
`
`
`
`
`
`the pilot at every point of the flight. However, most existing
`
`
`
`
`
`
`
`
`
`simulators do not show real images, but rather animated
`
`
`
`
`
`
`
`
`views, and they cannot provide full acquaintance with
`real-life terrain.
`
`
`
`
`
`
`
`
`
`
`In addition, there exist Internet sites which display still
`
`
`
`
`
`
`
`images and/or video streamsofdifferent locations, for those
`
`
`
`
`
`
`
`
`whowish to see the location before visiting there. Although
`
`
`
`
`
`
`
`streaming of video imagesoverthe Internet is knownin the
`
`
`
`
`
`
`
`art, Internet video streamsare limited in the information they
`
`
`
`
`
`
`
`
`provide and would notallow the pilotto interactively probe
`
`
`
`
`
`
`the terrain over which he is goingtofly.
`
`
`
`
`
`Computer rendering of three-dimensional terrain images
`
`
`
`
`
`
`
`
`
`is known in the art. U.S. Pat. No. 4,940,972, which is
`
`
`
`
`
`incorporated herein by reference, suggests displaying to a
`
`
`
`
`
`
`
`
`pilot of an aircraft a synthetic image of the groundterrain
`
`
`
`
`
`
`
`
`
`
`over whichthe pilot is flying. U.S. Pat. No. 5,566,073 which
`
`
`
`
`
`
`
`is incorporated herein by reference, describes a method for
`
`
`
`
`
`
`
`allowing a pilot to preview a route either in flight or on the
`
`
`
`
`
`
`
`
`
`ground. The ’073 patent also suggests allowing the pilot to
`
`
`
`
`
`
`
`
`
`take over and try out different flight strategies. However, the
`
`
`
`
`
`
`
`data volume required to display flight routes in accordance
`
`
`
`
`
`
`
`
`with the above-mentioned patents is very large. The °073
`
`
`
`
`
`
`
`patent suggests representing the terrain as polygonsin order
`
`
`
`
`
`
`
`
`
`
`to save computer storage space, but even so, the amountof
`
`
`
`
`
`
`
`
`storage on most home computers allows only a limited area
`
`
`
`
`
`
`
`
`
`and/or resolution level to be displayed. The °073 patent
`
`
`
`
`
`
`
`suggests using a CD-ROM to store the required data.
`
`
`
`
`
`
`
`
`However,
`the delivery of the CD-ROM to home users
`
`
`
`
`
`
`
`
`
`requires time and prevents pilots from preparing for last
`
`
`
`
`
`
`minute flight scheduling. Furthermore, changes in the
`
`
`
`
`
`
`
`terrain, such as seasonal changes, require frequent updates
`of the data on the CD-ROM.
`
`
`
`
`
`SUMMARYOF THE INVENTION
`
`
`
`
`
`
`
`
`
`
`It is an object of some aspects of the present invention to
`
`
`
`
`
`
`
`provide methods and apparatus for displaying on a remote
`
`
`
`
`
`
`
`computer actual imagesof an area as seen from a viewpoint
`
`
`
`which is chosen interactively.
`
`
`2
`
`
`
`
`
`
`
`
`It is another object of some aspects of the present inven-
`
`
`
`
`
`
`
`
`tion to provide methods and apparatusfor training a pilot to
`
`
`
`
`
`
`
`
`
`fly a preplanned flight course while allowingthe pilot to see
`
`
`
`
`
`
`
`
`
`
`
`the view seen at any point along the flight course at
`
`
`
`
`substantially any desired angle.
`
`
`
`
`
`
`
`
`
`It is still another object of some aspects of the present
`
`
`
`
`
`
`
`invention to provide methods and apparatus for displaying
`
`
`
`
`
`
`
`on a client computer images of ground terrain stored in a
`
`
`
`
`
`
`
`
`remote server, which are conveyed to the client via a
`
`
`
`
`network, preferably the Internet.
`
`
`
`
`
`
`
`
`It is still another object of some aspects of the present
`
`
`
`
`
`
`invention to provide methods and apparatus for streaming
`
`
`
`
`
`
`data required for rendering three-dimensionalterrain images
`
`
`
`on a remote computer.
`
`
`
`
`
`
`invention, a
`In preferred embodiments of the present
`
`
`
`
`
`
`
`processor simulates flight of a virtual airplane along a
`
`
`
`
`
`
`
`
`selected route. At substantially any viewpoint along the
`
`
`
`
`
`
`
`
`
`
`route, the processor displays the view seen from the view-
`
`
`
`
`
`
`in three-dimensional real-life images. A user may
`point
`
`
`
`
`
`
`
`
`
`select at substantially each point along the route the direc-
`
`
`
`
`
`
`
`
`
`tion of view and may change the direction dynamically.
`
`
`
`
`
`
`
`Preferably, the user controls the speed of progress along
`
`
`
`
`
`
`
`
`
`the route and may stop the progress and/or reverse direction
`
`
`
`along the course.
`
`
`
`
`
`
`
`Preferably, the user views the three-dimensional images
`
`
`
`
`
`
`
`without having to store a large database of terrain images on
`
`
`
`
`
`
`
`
`
`the user’s processor, and without requiring that the processor
`
`
`
`
`
`
`
`
`have an unusually large memory capacity. Rather, the user
`
`
`
`
`
`
`
`
`connects to a pilot
`training server, which stores all the
`
`
`
`
`
`
`
`
`
`required data, and the user’s processor downloadsthe data
`
`
`
`
`
`
`
`dynamically according to the data required to display each
`
`
`
`
`
`
`
`specific scene. Preferably,
`the processor connects to the
`
`
`
`
`
`
`server via a communication link, preferably a public
`
`
`
`
`
`
`
`
`network, such as the Internet. Preferably, the data is con-
`
`
`
`
`
`
`
`veyed by a standard modem at sufficient speed forrelatively
`
`
`
`
`
`smooth display of the images.
`
`
`
`
`
`
`Alternatively or additionally, the required data is down-
`
`
`
`
`
`
`
`
`
`loaded prior to the displaying of the scene, or the data is
`
`
`
`
`
`
`retrieved from a CD or other memory apparatus associated
`
`
`
`with the processor.
`
`
`
`
`
`
`In some preferred embodiments of the present invention,
`
`
`
`
`
`
`
`the user may change the parameters of the movementof the
`
`
`
`
`
`
`
`
`virtual airplane, including the speed, height and angle of the
`
`
`
`
`
`
`
`
`airplane, and even deviate from the preplanned route.
`
`
`
`
`
`
`In some preferred embodiments of the present invention,
`
`
`
`
`
`
`
`the route includes access to an airport according to the
`
`
`
`
`
`
`access rules of the airport. Alternatively or additionally, the
`
`
`
`
`
`
`route may include military maneuvers for bombing or access
`
`
`
`
`
`
`to enemylocations. Further alternatively or additionally, the
`
`
`
`
`
`
`
`route may be selected from routes of access to canyons,
`
`
`
`
`
`
`
`mountain areas or any other hard-to-access points,
`for
`
`
`
`
`
`
`example, in order to train rescue helicopter pilots.
`
`
`
`
`
`
`
`In some preferred embodiments of the present invention,
`
`
`
`
`
`
`
`
`
`
`
`an operator of the server and/or the user may addto the data
`
`
`
`
`
`
`
`
`which describes the terrain annotations which describe spe-
`
`
`
`
`
`
`
`
`cific points in the scene, such as runways or other destina-
`
`
`
`
`
`
`
`
`tions. Alternatively or additionally, the operator may add
`
`
`
`
`
`
`three-dimensional objects, such as planned buildings,
`
`
`
`
`
`
`
`vehicles, etc. In a preferred embodiment of the present
`
`
`
`
`
`
`
`invention, a group of vehicles are tracked according to their
`
`
`
`
`
`
`
`
`position, and they are constantly superimposed on the land-
`
`
`scape images.
`
`
`
`
`
`
`
`U.S. patent application Ser. No. 08/939,948, which is
`
`
`
`
`
`
`
`
`assigned to the assignee of the present application and is
`
`
`
`
`
`
`incorporated herein by reference, describes a method of
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`10
`
`15
`
`
`
`20
`
`25
`
`
`
`35
`
`
`
`40
`
`
`
`45
`
`
`
`50
`
`
`
`55
`
`
`
`60
`
`
`
`65
`
`
`
`
`
`Page 11 of 20
`
`Unified Patents Exhibit 1028
`
`Page 11 of 20
`
`Unified Patents Exhibit 1028
`
`

`

`
`
`US 6,496,189 B1
`
`
`3
`
`
`
`
`
`
`terrain images. The method
`rendering three-dimensional
`
`
`
`
`
`
`
`allows fast rendering of images by comparison with other
`
`
`
`
`
`
`
`
`methods known in the art. The method of U.S. patent
`
`
`
`
`
`
`
`application Ser. No. 08/939,948 uses a hierarchical database
`
`
`
`
`
`
`
`in which substantially each terrain area is described in a
`
`
`
`
`
`
`
`
`plurality of blocks at different resolution levels. The blocks
`
`
`
`
`
`
`
`
`
`
`at lower resolution levels include less detail per unit area,
`
`
`
`
`
`
`
`
`while the blocks of higher resolution levels include more
`
`
`
`
`
`
`
`
`
`detail per unit area. The additional storage space required in
`
`
`
`
`
`
`
`
`
`order to store the additional data required due to the hier-
`
`
`
`
`
`
`
`archical structure is “paid back” in improved time perfor-
`
`
`
`mance of the rendering.
`
`
`
`
`
`
`
`In some preferred embodiments of the present invention,
`the data is stored at the remote server in accordance with the
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`hierarchical structure described in the *948 application.
`
`
`
`
`
`
`
`Whendata describing a specific area is needed in order to
`
`
`
`
`
`
`
`
`render the current view,
`the processor first downloads a
`
`
`
`
`
`
`
`
`
`block with a low level of resolution, which requires less data
`
`
`
`
`
`
`
`
`
`
`
`volume per area unit, and renders the view using the lower
`
`
`
`
`
`
`resolution block. Afterwards, if available bandwidth on the
`
`
`
`
`
`
`
`
`communication line permits, blocks which coverthe specific
`
`
`
`
`
`
`
`
`
`area from higher resolution levels are downloaded, and the
`
`
`
`
`
`
`
`
`processor uses these blocks to improve the rendered view.
`
`
`
`
`
`
`
`In some preferred embodiments of the present invention,
`
`
`
`
`
`
`
`
`the processor manages a local cache memory in which the
`
`
`
`
`
`
`
`
`
`processor stores blocks which cover terrain areas in the
`
`
`
`
`
`
`
`vicinity of the current viewpoint. Preferably, the processor
`
`
`
`
`
`
`
`
`stores in the cache memoryall blocks downloaded from the
`
`
`
`
`
`
`
`
`server. Preferably, when the communication link is not
`
`
`
`
`
`
`
`needed to download blocks required for currently rendered
`
`
`
`
`
`
`
`
`images, the processor downloadsblocksin the vicinity of the
`
`
`
`
`
`
`
`
`viewpoint. Preferably,
`the processor stores in the cache
`
`
`
`
`
`
`
`memory an equal number of blocks from each resolution
`
`
`
`
`
`
`
`
`level. Further preferably, the number of blocks in the cache
`
`
`
`
`
`
`
`
`
`memory is such that the cache memoryhasall the required
`
`
`
`
`
`
`
`
`
`blocks to render the view from the current viewpoint in any
`
`
`
`
`
`
`
`view direction. Preferably, when downloading blocks, the
`
`
`
`
`
`
`
`processor first downloads blocks from lower resolution
`levels.
`
`
`
`
`
`
`
`Preferably, when the processor requires a number of
`
`
`
`
`
`
`
`
`
`
`blocks, the first block sent is the block of the lowest level.
`
`
`
`
`
`
`
`
`
`
`
`If two blocks of the same level are required, the one which
`
`
`
`
`
`
`
`
`
`
`is requested last is sent first. Thus, when the viewpoint
`
`
`
`
`
`
`
`
`
`
`
`changes,the blockssentfirst are for the new viewpoint, and
`
`
`
`
`
`
`
`
`
`only afterwards are blocks sent for the old viewpoint.
`
`
`
`
`
`
`
`Preferably, if a block requested earlier is relatively far from
`
`
`
`
`
`
`
`
`
`the viewpoint, it is not sent, since it is obviously not needed
`anymore.
`
`
`
`
`
`
`
`Preferably, when the processor needs to render a new
`
`
`
`
`
`
`
`
`
`image, the processorfirst uses the data blocks stored in the
`
`
`
`
`
`
`
`cache memory and concurrently sends download orders for
`
`
`
`
`higher resolution level blocks.
`
`
`
`
`
`
`
`In some preferred embodiments of the present invention,
`
`
`
`
`
`
`
`
`the processor runs a rendering program which displays the
`
`
`
`
`
`
`
`three dimensional images based on the viewpoint, the size of
`
`
`
`
`
`
`
`
`
`the displayed image and the blocks received from the server.
`
`
`
`
`
`
`
`
`The rendering program orders the blocks it needs using a
`
`
`
`
`
`
`cache manager, which is preferably a software routine
`
`
`
`
`
`
`
`
`
`
`running on the processor. If the cache manager has the
`
`
`
`
`
`
`
`ordered block,
`it provides it
`to the rendering program.
`
`
`
`
`
`
`
`
`However,if the block is not carried by the cache manager,
`
`
`
`
`
`
`
`
`
`
`it is ordered from the server, and a replacement block from
`
`
`
`
`
`
`
`
`a lowerresolution level is passed to the rendering program.
`
`
`
`
`
`
`Whenthe rendering program requires a block including a
`
`
`
`
`
`
`
`
`
`
`new point or area for display,
`the cache manager first
`
`
`
`
`
`
`
`
`
`requests the block of the lowest resolution level which
`
`
`
`
`
`10
`
`15
`
`
`
`20
`
`25
`
`
`
`30
`
`
`
`40
`
`
`
`
`
`50
`
`
`
`55
`
`
`
`60
`
`
`
`65
`
`
`
`
`4
`
`
`
`
`
`
`
`
`
`
`covers the area with the least detail and then requests
`
`
`
`
`
`
`
`subsequent blocks with successively increasing detail, until
`
`
`
`
`
`
`
`
`the block with the level of detail required by the rendering
`
`
`
`
`
`
`
`
`program is sent. The rendering program renders the three-
`
`
`
`
`
`
`
`
`dimensional image using the blocks it has on hand. Each
`
`
`
`
`
`
`
`
`time another blockis received, the image is rendered again.
`
`
`
`
`
`
`
`
`
`Thus, the user sees an imageat substantially all times and is
`
`
`
`
`
`
`
`not prevented from moving the viewpoint while additional
`
`
`
`
`
`
`data is being sent from the server.
`
`
`
`
`
`
`There is therefore provided in accordance with a preferred
`
`
`
`
`
`
`embodimentof the present invention, a method of providing
`
`
`
`
`
`
`data blocks describing three-dimensional
`terrain to a
`
`
`
`
`
`
`
`renderer, the data blocks belonging to a hierarchical struc-
`
`
`
`
`
`
`
`
`ture which includes blocks at a plurality of different reso-
`
`
`
`
`
`
`
`
`
`lution levels, the method including receiving from the ren-
`
`
`
`
`
`
`
`
`derer one or more coordinates in the terrain along with
`
`
`
`
`
`
`
`indication of a respective resolution level, providing the
`renderer with a first data block which includes data corre-
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`sponding to the one or more coordinates, from a local
`
`
`
`
`
`
`
`
`memory, and downloading from a remote server one or more
`
`
`
`
`
`
`
`additional data blocks which include data corresponding to
`
`
`
`
`
`
`
`
`
`the one or more coordinates if the provided block from the
`
`
`
`
`
`
`
`local memoryis not at the indicated resolution level.
`
`
`
`
`
`
`
`
`Preferably, providing the first data block includes provid-
`
`
`
`
`
`
`
`
`
`
`ing the data block from the highest resolution level which
`
`
`
`
`
`
`
`includes data corresponding to the one or more coordinates.
`
`
`
`
`
`
`
`Preferably, downloading the one or more additional data
`
`
`
`
`
`
`blocks includes downloading a block at a resolution level
`
`
`
`
`
`
`
`
`higher than the resolution level of the first block.
`
`
`
`
`
`
`
`Further preferably, downloading the one or more addi-
`
`
`
`
`
`
`
`
`tional data blocks includes downloading the blocks from a
`
`
`
`
`
`
`
`succession of resolution levels, from the level immediately
`
`
`
`
`
`
`
`
`
`
`higher than the resolution level of the first block up to the
`maximalexistent resolution level on the server not above the
`
`
`
`
`
`
`
`
`indicated resolution level.
`
`
`
`
`
`
`
`
`
`
`Preferably, receiving from the renderer the one or more
`
`
`
`
`
`coordinates includes receiving a plurality of coordinates
`
`
`
`
`
`
`included in a plurality of respective distinct blocks, and
`
`
`
`
`
`
`downloading the one or more blocks includes downloading
`
`
`
`
`
`
`blocks including data correspondingto at least some of the
`
`
`
`plurality of coordinates.
`
`
`
`
`Preferably, downloading the blocks includes downloading
`
`
`
`
`
`
`
`the blocks in an order determined according to their reso-
`lution levels.
`
`
`
`
`
`
`
`Further preferably, downloading the blocks includes
`
`
`
`
`
`
`downloading blocks of lower resolution levels before blocks
`
`
`
`
`of higher resolution levels.
`
`
`
`
`Preferably, downloading the blocks includes downloading
`
`
`
`
`
`
`
`
`
`first the block for which the coordinates were provided last
`
`
`
`
`
`amongblocks at a commonresolution level.
`
`
`
`
`Preferably, downloading the blocks includes downloading
`
`
`
`
`
`
`
`the blocks according to the order in which the coordinates
`
`
`were provided.
`
`
`
`
`
`Preferably, downloading the blocks includes downloading
`
`
`
`
`
`
`
`
`
`
`first the block for which the coordinates were providedlast.
`
`
`
`
`
`
`Preferably,
`the method includes downloading excess
`
`
`
`
`
`
`
`
`
`blocks not currently needed by the rendererto fill up the
`
`
`
`
`
`
`local memory when not downloading blocks required by the
`renderer.
`
`
`
`
`
`
`
`Preferably, the renderer renders a view from a current
`
`
`
`
`
`
`viewpoint, and downloading the excess blocks includes
`
`
`
`
`
`
`
`
`
`filling the local memory with substantially all of the blocks
`
`
`
`
`
`
`
`surrounding a point in the terrain seen from the current
`
`
`
`
`
`viewpoint within a predetermined distance range.
`
`
`
`
`
`
`Preferably, downloading excess blocks includesfilling the
`
`
`
`
`
`
`
`local memory with substantially the same numberof blocks
`from each different resolution level.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Page 12 of 20
`
`Unified Patents Exhibit 1028
`
`Page 12 of 20
`
`Unified Patents Exhibit 1028
`
`

`

`
`
`US 6,496,189 B1
`
`
`
`
`
`
`10
`
`
`
`
`
`15
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`6
`5
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`resolution level from the renderer, provides the renderer
`Preferably, filling the local memory includes filling the
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`memory with substantially all the blocks within the range withafirst data block which includes data corresponding to
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`from a lowerresolution level before downloading blocks of
`the one or more specified coordinates from the local
`
`
`
`
`
`
`
`
`
`
`
`higher resolution levels.
`memory, and downloadsover the communication link one or
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`more additional data blocks which include data correspond-
`Preferably, downloading the data blocks includes down-
`
`
`
`
`
`
`
`
`
`ing to the one or more coordinates if the first block is not
`
`
`
`
`
`
`loading the blocks via the Internet.
`from the indicated level.
`
`
`
`
`
`
`
`
`
`There is further provided in accordance with a preferred
`
`
`
`
`
`
`
`
`Preferably,
`the processor provides the first data block
`
`
`
`
`
`embodimentof the present invention, a method of display-
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`from the highest resolution level which includes the one or
`ing three dimensional images, including establishing a com-
`
`
`
`
`
`
`
`more coordinates currently available in the local memory.
`
`
`
`
`
`
`munication link between a local processor and a server,
`
`
`
`
`
`
`
`
`
`
`
`
`
`transferring data blocks describing terrain over the commu-
`Preferably, the processor downloads a block of a resolu-
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`nication link from the server to the local processor; and
`tion level higher than the resolution level of the first block.
`
`
`
`
`
`rendering a three-dimensional
`terrain image at
`the local
`
`
`
`
`
`
`
`Preferably,
`the processor downloads blocks from the
`
`
`
`
`
`processor responsive to the data blocks.
`
`
`
`
`
`
`
`
`resolution level immediately higher than the resolution level
`
`
`
`
`
`
`
`
`
`
`
`
`
`Preferably, establishing the communication link includes
`of the first block up to a maximal resolution level of blocks
`stored on the serverthat is not above the indicated resolution
`
`
`
`
`
`
`
`
`
`
`
`
`establishing a low-speed communication link.
`level.
`
`
`
`
`
`
`
`Preferably, transferring the data blocks includestransfer-
`
`
`
`
`
`
`
`
`
`
`
`
`
`ring the blocks via the Internet.
`Preferably,
`the processor receives from the renderer a
`
`
`
`
`
`plurality of coordinates included in a plurality of respective
`
`
`
`
`
`
`Further preferably, transferring the data blocks includes
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`distinct blocks and downloadsblocks includingat least some
`transferring the blocks responsive to a list of coordinates
`
`
`
`
`
`
`
`of the plurality of coordinates.
`generated by the processor.
`
`
`
`
`
`
`
`
`
`
`
`Preferably, the processor downloadsthe blocks in an order
`Preferably, the list of coordinates is prepared responsive
`
`
`
`
`
`
`
`
`
`
`
`
`determined according to their resolution levels.
`to a viewpoint from which the image is rendered.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Preferably,
`the processor downloads blocks of lower
`Preferably, the viewpoint changes over time following a
`
`
`
`
`
`
`
`
`
`resolution levels before blocks of higher resolution levels.
`predetermined course.
`
`
`
`
`
`
`Preferably, the processor downloads in first precedence
`
`
`
`
`
`
`Preferably, the predetermined course is received from the
`server.
`
`
`
`
`
`
`
`
`
`the block for which the coordinates were provided last
`
`
`
`
`
`
`
`among blocks from a commonresolution level.
`
`
`
`
`
`Preferably,
`the predetermined course describes a sug-
`
`
`
`
`
`
`
`
`
`
`
`Preferably, the processor downloadsthe blocks according
`gested course for landing in an airport.
`
`
`
`
`
`
`
`
`to the order in which the coordinates were provided.
`
`
`
`
`
`
`
`
`Preferably, a user of the processor changes the view
`
`
`
`
`
`
`
`
`
`
`
`
`
`Preferably, the processor downloads in first precedence
`direction from the viewpoint without removing the view-
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`the block for which the coordinates were providedlast.
`point from the predetermined course.
`
`
`
`
`
`
`
`
`
`
`
`
`Preferably, the processor downloads excess blocks not
`Preferably, the viewpoint is controlled by a user of the
`
`
`
`
`
`
`
`processor.
`currently needed by the rendererto fill up the local memory
`
`
`
`
`
`
`
`
`when not downloading blocks required by the renderer.
`
`
`
`
`
`
`Preferably, transferring the data blocks includestransfer-
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Preferably, the renderer renders a view from a current
`ring blocks which include altitude data of the terrain.
`
`
`
`
`
`
`
`
`
`viewpoint and the processor fills the local memory with
`
`
`
`
`
`
`
`Preferably, transferring the data blocks includestransfer-
`
`
`
`
`
`
`
`
`substantially all the blocks surrounding a pointin the terrain
`
`
`
`
`
`
`
`ring blocks which include optional objects to be overlaid on
`
`
`
`
`
`
`
`the terrain.
`seen from the current viewpoint in a predetermined range.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Preferably,
`the processor fills the local memory with
`Preferably, rendering the images includes rendering the
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`substantially the same number of blocks from each resolu-
`images with at least some of the optional objects according
`tion level.
`
`
`
`
`
`
`
`
`
`to settings of the user of the local processor.
`
`
`
`
`
`
`
`
`
`
`
`
`
`Preferably,
`the processor fills the local memory with
`There is further provided in accordance with a preferred
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`substantially all the blocks from a lower level before down-
`embodiment of the present invention, a method of pilot
`
`
`
`
`
`
`
`
`
`
`
`
`loading blocks of higher resolution levels.
`training, including loading a course of a flight vehicle into
`
`
`
`
`
`
`
`
`
`
`
`a local processor, establishing a communicat