}2-B4J-er
`
`fl | Ploy
`
`IN THE UNITED STATES PATENT AND TRADEMARK OFFICE
`REQUEST FOR FILING A PROVISIONAL APPLICATION FOR PATENT
`UNDER 37 CFR §1.53 (c)
`
`we
`
`wa
`wt
`
`
`
`oLad‘s'n
`
`
`
`Levanon
`
`| Lavi
`
`2g6°F INVENTOR(S]
`
`| 3 NachalBesorSt., Ramat Hasharn,Israel
`21 Bar Ilan St., Raanana, Israel
`
`TITLE OF THE INVENTION
`
`OPTIMIZATION OF RENDERING MEMORY USAGE IN FAST QUALITY
`BUILD-UP TARGET IMAGE TRANSFER OVER LIMITED AND
`NARROWBAND COMMUNICATION NETWORKS
`
`X[oe ot covezondenc e GonNoor 248 Mr
`
`Gerald B. Rosenberg, Esq.
`NewTechLaw
`|} 285 Hamilton Avenue,Suite 520
`Palo Alto, California 94301
`
`(Reg No.: 30,320)
`
`Telephone:
`Facsimile:
`
`650.325.2100
`650.325.2107
`
`23488
`PATENT TEADEMARK OFFICE
`
`ENCLOSED APPLICATION PARTS (checkall that apply)
`
`Specification
`
`No. of pages:
`
`i
`
`Small Entity Statement
`
`Drawings
`
`Declaration
`
`No. of sheets:
`
`Power of Attorney
`
`____ Assignment and Cover Sheet
`
`Other: Return-Receipt Post Card.
`
`METHOD OF PAYMENTOF FILING FEES FOR THIS PROVISIONAL APPLICATION FOR PATENT
`
`Provisional Basic Filing Fee: $ 150.00 (Small Entity: $75.00)
`
`Filing Fee Amount: $ 150.00
`
`A check is enclosed to cover the Filing Fees.
`
`The Commissioneris hereby authorized charge Filing Fees or credit any
`overpayment to: Deposit Account Number: 50-0890.
`
`This invention was not made by or under contract with a US Government agency.
`
`US Government agency and Contract:
`
`Gerald B. Rosenberg
`Reg. No.: 30,320
`
`Date: December 26, 2000
`
`Application Docket No:
`
`FLVT3004
`
`Express Mail Label No.:
`
`EL 661 534 291 US
`
`| Address To:
`
`Box Provisional Application, Assistant Commissioner for Patents, Washington, DC 20231
`
`gbr/flvv3004,002 prov xmittal wpd
`
`1 of 17
`
`Microsoft Corp. Exhibit 1067
`
`1 of 17
`
`Microsoft Corp. Exhibit 1067
`
`

`

`OPTIMIZATION OF RENDERING MEMORY USAGE IN
`FAST QUALITY BUILD-UP TARGET IMAGE TRANSFER
`OVER LIMITED AND NARROWBAND
`COMMUNICATION NETWORKS
`
`Inventors:
`Isaac Levanon
`Yoni Lavi
`
`Background of the Invention
`
`The present invention is generally related to the delivery of high-resolution
`
`highly featured graphic images overlimited and narrowband communications
`channels.
`
`Summary of the Invention
`
`The objective is to display a two-dimensional pixel map, a1 6-Bit RGB color
`
`imagein the preferred embodiments, of very large dimensions and permitting the
`
`viewing of the image from a dynamic three-dimensional viewpoint. Multiple such
`images are remotely hosted for on-demandselection and transfer to a client
`
`system for viewing.
`
`Attorney Docket No.: FLVT3004
`gbr/flvt/3004.000. provisional.wpd
`
`12/26/2000
`
`]
`2
`3
`4
`
`5 6 7 8 9
`
`10
`11
`12
`13
`14
`15
`
`16
`
`17
`18
`
`19
`
`20
`
`2]
`
`22
`
`23
`24
`
`25
`
`
`
`=
`
`2 of 17
`
`Microsoft Corp. Exhibit 1067
`
`2 of 17
`
`Microsoft Corp. Exhibit 1067
`
`

`

`-2-
`
`Images, as stored by the server, may individually range from gigabytes to
`
`multiple terabyte in total size. A correspondingly large server storage and
`
`processing system is contemplated. Conversely, client systems are contemplated
`to be conventional personal computersystems and,in particular, mobile,cellular,
`
`embedded, and handheld computer systems, such as personal digital assistants
`
`(PDAs) and internet-capable digital phones, with relatively limited to highly
`constrained network communications capabilities. For most wireless applications,
`conventional narrowband communications links have a bandwidth of less than
`
`approximately three kilobytes of data per second. Consequently, transmittal of
`
`entire images fo a client system in reasonable timeis infeasible as a practical
`
`matter.
`
`Overview:
`
`Description of the Invention
`
`For purposes of the present invention, each image (Figure 1) is at least
`logically defined in terms of multiple grids of image parcels with variouslevels of
`
`___
`
`resolutions (Figure 2) that are created through composition of information from
`all level of resolutions, and stored by the server to provide an imagefor transfer
`to a client system (Figure 3). Composed and separate static and dynamically
`created layers are transferred to client system in parcels in a program selectable
`orderto optimize for fast quality build-up of the image presented to a user of the
`client system, particularly when the parcels are streamed over a narrowband
`communicationlink.
`The multiple layers of an image allow the selectivity to incorporate
`
`]
`
`2 3 4 5
`
`6 7
`
`8
`
`10
`
`1]
`
`12
`
`13°
`
` 9
`
`14
`
`15
`16
`
`17
`18
`19
`20
`21
`22
`23
`24
`
`25
`
`topographical, geographical, orientational, and other terrain and mapping
`
`Attorney Docket No.: FLVT3004
`gbr/fivt/3004.000.provisional.wpd
`
`12/26/2000
`
`3 of 17
`
`Microsoft Corp. Exhibit 1067
`
`3 of 17
`
`Microsoft Corp. Exhibit 1067
`
`

`

`3.
`
`related information into the image delivered. Other layers, such as geographic
`grids, graphical text overlays, and hyperlink selection areas, separately provided
`or composed, aid in the useful presentation and navigation of the image as
`presented by the client system and viewed bythe user.
`Compositing of layers on the server enables the data transfer burden to be
`reduced, particularly in analysis of the requirements and capabilities of the client
`system and the connecting communicationslink. Separate transferof layers to the
`client system allowsthe client system selectivity in managing and presentation of
`the datato the user.
`The system and methods of the present invention are designed to, on
`demand, select, process and immediately transfer data parcels to the client
`system, which immediately processes and displays a low-detail representation of
`the image requested by the client system. The system and methods immediately
`continueto select, process and sequentially transfer data parcels that, in turn, are
`processed and displayed bythe client system to augmentthe presented image
`and thereby provide a continuously improving imageto the user.
`Selection of the sequentially transferred datais, in part, dependenton the
`progressive translation of the three-dimensional viewpoint as dynamically
`modified on the client system during the transfer process. This achieves the
`above-stated objective while concurrently achieving a goodrendering quality for
`continuousfly-overof the image asfast as possible,yet continuously building the
`image quality to the highest resolution of the image as stored by the server.
`To optimize image quality build-up over
`limited and narrowband
`communication links, the target image, as requested by the client system,
`is
`represented by multiple grids of 64x64 imagepixels (Figure 4) with each grid
`
`Attorney Docket No.: FLVT3004
`gbr/flvt/3004.000.provisional.wed
`
`12/26/2000
`
`]
`
`2 3 4 5
`
`
`
`
`6
`7
`8
`9
`10
`11
`12
`13
`14
`S 15
`16
`17
`= 18
`19
`20
`21
`22
`23
`24
`25
`
`4 of 17
`
`Microsoft Corp. Exhibit 1067
`
`4 of 17
`
`Microsoft Corp. Exhibit 1067
`
`

`

`
`
`]
`2
`3
`A
`5
`6
`7
`8
`9
`10
`11
`12
`13
`. 14
`£
`15
`
`
`=
`16
`5
`17
`
`18
`19
`20
`21
`22
`23
`24
`25
`
`4.
`
`having some correspondinglevel of detail. That is, each grid is treated as a
`sparse data arraythat can be progressively revised to increase the resolution of
`the grid and thereby the level of detail presented by the grid. The reason for
`choosing the 64x64 pixel dimension is that, using current image compression
`algorithms, a 16-bit 64x64 pixel array image can be presented as a 2KByte data
`parcel.
`In turn, this 2KByte parcel is the optimal size, subject to conventional
`protocol and overhead requirements, to be transmitted through a 3KByte per
`second narrowbandtransmission channel. Using a smaller image array, such as
`32x32, would create a 0.5KByte parcel, hence causing inefficiencies due to packet
`transmission overhead, given the nature of current wireless communications
`protocols.
`Imagearray dimensionsare preferably powers of two so that they can be
`used in texture mappingefficiently. Each parcel, as received by the client system,
`is preferably immediately processed and incorporated into the presented image.
`To do so efficiently, according to the present invention, each data parcel
`is
`independently processable by the client system, which is enabled by the selection
`and server-side processing used to prepare a parcelfortransmission.In addition,
`each data parcelis sized appropriatetofit within the level-1 cache,or equivalent,
`of the client system processor, thereby enable the data processing intensive
`operations needed to process the data parcel to be performed without extended
`memory access delays.
`In the preferred embodimentof the present invention,
`data parcels are also processed for texture mapping and other image features,
`such as topographical detailing.
`Currently, with regard to conventionalclient systems, a larger imagearray,
`such as 128x128,is too large to befully placed within the level-1 cache of many
`
`Attorney Docket No.: FLVT3004
`gbr/flvt/3004.000.provisional.wpd
`
`12/26/2000
`
`5 of 17
`
`Microsoft Corp. Exhibit 1067
`
`5 of 17
`
`Microsoft Corp. Exhibit 1067
`
`

`

`-5-
`
`OoODOONOOOF&FWHNY—
` 17
`
`of the smaller conventional current processors, such as used by personal digital
`assistants (PDAs) and cellular phones.
`Since access to cache memory is
`substantially faster than to RAM this will likely result in lower framerate.
`Different and larger data parcel sizes may be optimal as transmission
`protocols and micro-architectures of the client computers change. For purposes
`above, the data content was a pixel array representing image data. Where the
`data parcel contentis vector, text or other data that may subjectto differentclient
`system design factors, other parcel sizes may be used.
`In the process implementedby the presentinvention, data parcels maybe
`selected for sequential transmission based onaprioritization of the importance
`1]
`of the data contained. Thecriteria of importance maybe defined as suitable for
`12
`particular applications and may directly relate to the presentation of image
`13
`quality, provision of a textual overlay of a low-quality image to quickly provide a
`14
`navigationalorientation, or the addition of topography information at a rate or
`15
`timing different from the rate of image quality improvement. Thus, image data
`16
`layers reflecting navigational cues,
`text overlays, and topography can be
`composedinto data packets for transmission subjectto prioritizations set by the
`server alone, based on the nature andtype ofthe client system, and interactively
`influenced by the actions and commandsprovided bythe useroftheclient system
`(Figure 5).
`|
`Progressive transmission of image parcels is performed in aniterative
`process involving selection of an image data grid within the target imageof the
`client system, whichis a portion of a potentially multi-layered source image stored
`by the server. The selection parameters are preferably dependenton the client
`navigation viewpoint, effective velocity, and height, and the effective level of detail
`
`18
`19
`20
`21
`22
`23
`24
`25
`
`Attorney Docket No.: FLVT3004
`gbr/flvt/3004.000.provisional.wpd
`
`12/26/2000
`
`6 of 17
`
`Microsoft Corp. Exhibit 1067
`
`6 of 17
`
`Microsoft Corp. Exhibit 1067
`
`

`

`—
`
`1]
`12
`
`13
`
`oOObONOOOOFFWDH
` 17
`
`14
`15
`16
`
`18
`19
`20
`21
`22
`23
`24
`25
`
`-6-
`
`currently presented in each grid. Once a grid is selected, the server selects the
`source data to be logically composed into the selected grid to complement the
`effective resolution of that grid, processing the grid data to produce the optimally
`sized size grid data parcels, and sequentially transmitting the parcels to the client
`system. Preferably, the detail of a grid array is sequentially enhanced bydivision
`of the grid into sub-grids related by a powerof two (Figure 6). Thus, a given grid
`is preferably updated using four data parcels having twice the data resolution of
`the existing grid. Whatever numberof parcels are used, each data parcel is
`rendered by the client system into the target image. Additional client system
`image data processing to provide texturing and three-dimensional representation
`of the data may beperformedas part of the parcel rendering and integration into
`the target image.
`
`Image Parcel Download Sequence:
`The server of the present invention supports the download of parcel data
`to a client system by providing data parcels in response to network requests
`originated by client systems. Each requested data parcelis identified within a grid
`coordinate system relative to an image stored by the server.
`A client system implementing the process of the present invention is
`responsible foridentifying and requesting parcel data, then rendering the parcel
`data into the target image at the correct location. The client system is also
`responsible for managing navigational and other interaction with the user.
`In
`identifying the parcel data to be requested, the client system operates to select
`grids within the coordinate system, corresponding to portions of the target image,
`for which to request a corresponding data parcel. The requests are issued over
`
`Attorney Docket No.: FLVT3004
`gbr/flvt/3004.000.provisional.wed
`
`12/26/2000
`
`7 of 17
`
`Microsoft Corp. Exhibit 1067
`
`7 of 17
`
`Microsoft Corp. Exhibit 1067
`
`

`

`-7-
`
`the network to the server and rendering performed asynchronously as data
`
`parcels are received. The orderof data parcel requests is defined as a sequence
`
`that will provide for the optimal build-up of the target image as presented to the
`
`user. The rate of optimal build up of the target image is dependent on the nature
`
`of the target image requested, such as the supported parcel size and depth of the
`
`target image that can be rendered bythe client system.
`
`The client identifies and requests the download of data parcels in the
`
`process as follows. Denote the target imageas|, and its size in pixels as (X, Y).
`
`Let N be the smallest power of 2 that is equal or greater than max {X,Y}.
`Construct the grid of 64x64 pixel grid-images |,;, that together compose the
`target image |. The rectangle [641,641 + 64] x [64j,64 | + 64] of |, is mapped
`to Ip;;-
`
`In order to view a large portion of the image, the target image, without
`downloading the substantial bulk of the target image, mip-mapsofI, are created,
`representing a collection of images to be used as surface textures when rendering
`
`a two-dimensional representation of a three-dimensional scene, and which are
`defined recursively as:
`
`Lear (ii) = avg(l, (21,2)), (21 + 1,2)), |,(2i,2) + 1), 1,(2i + 1,2) + 1))
`
`Such mip-maps are created up to |,,,M = log, (N) - 6. At this point, ly is
`a 64x64 image containing the entire area of the original image, hence no further
`mip-mappingis required.
`
`The methods of the present invention then proceed by constructing the
`respective grids orcells (I,;;) for each mip-map. Each nonempty imagecell |,;,
`
`Attorney Docket No.: FLVT3004
`gbr/flvt/3004.000.provisional.wpd
`
`12/26/2000
`
`8 of 17
`
`Microsoft Corp. Exhibit 1067
`
`]
`
`2 3 4 5
`
`6
`
`7
`
`8
`
`9
`10
`11
`12
`13
`14
`
`cs
`
`
`
` 15
`
`16
`17
`2
`“48
`
`19
`20
`
`2]
`22
`23
`
`24
`25
`
`8 of 17
`
`Microsoft Corp. Exhibit 1067
`
`

`

`CONOOMBRBWHDY—
`
`
`
`
`9
`10
`1
`12
`13
`14
`= 15
`16
`17
`18
`19
`20
`21
`22
`23
`24
`25
`
`-8-
`
`now may be downloaded. Larger values of k cover morearea within the original
`image but provide lower detail on that area. The task at hand is now to
`determine, given the viewing frustum andthelist of previously downloaded image
`cells I,;;, downloading which grids will improve the quality of the display as fast
`as possible, considering the download rate as fixed. The scheme used to
`implemented the downloading sequence ofthesecells is by constructing a tree,
`starting from ly.6o,0 and expanding a quadtree towards the lower mip-map levels.
`(Quadirees are data structures in which each node can have upto four child
`nodes. As each 64x64 pixel imagein the grid 1, has exactly four matching 64x64
`pixel images on the grid 1,, covering the same area, the data structure is built
`accordingly.)
`For every framethatis rendered , begin with the cell that covers the area
`of the entire original image, I\.¢9,- For each cell under consideration, compute
`the principle mip-map level that should be used to draw it.
`If it is lower than the
`mip-map level of the cell, subdivide the cell
`to four smaller cells and use
`recursion.
`If this operation attempts to draw over areas that do not yet have
`imagecells at a low enough mip-map levelto use with them, the recursion stops.
`If the principle mip-map level is equal or higher than thelevelof the cell,
`thenthecell is rendered usingthecell of the principle mip-maplevel, whichis the
`parent of thatcell in the Quad-tree, at the appropriate level. Then download the
`cells in which the difference betweenthe principle mip-map level to the mip-map
`level of the imagecell actually usedis the highest. Downloading is asynchronous;
`the renderer maintains a priority queue of download requests, and separate
`threads are downloading images. Whenever a download is complete, another
`downloadisinitiated immediately, based on the currently highest-priority request.
`
`Attorney Docket No.: FLVT3004
`gbr/flvt/3004.000.provisional.wpd
`
`12/26/2000
`
`9 of 17
`
`Microsoft Corp. Exhibit 1067.
`
`9 of 17
`
`Microsoft Corp. Exhibit 1067
`
`

`

`Whenrenderingacell of the grid I,
`
`
`
`
`
`9.
`
`Theprinciple mip-map level of an imagecell is determined by the screen
`resolution, FOV(field of view) angle, the angle formed betweenthe image's plane
`normal andthe line connecting between the camera andtheposition within the
`cell that is closest to the camera, and a few other factors. The equation, which
`uses the above information, approximates the general mip-mapping level
`equation:
`
`| = max(0, log, (T/S))
`
`in whichS is the surface of the cell as displayed on the screen during rendering
`(in pixels), and T is the surface of the cell within the texture being mapped (in
`pixels).
`
`T=N’2*
`
`and
`
`S = xycos(a)ctg?(0.5FOV)#? T / 2”
`
`wherex is the display's x-resolution,y is the display’s y-resolution, FOVis the field-
`of-view angle, a is the angle between the image's plane normal and the line
`connecting the viewpoint and the pointin thecell of shortest distancetoit, t is the
`length of the square each pixelin the original imageis assignedto in 3D, and z
`is the height of the camera over the image's plane.
`This arrives at the equation:
`| = log, (z? /(xycos(a)ctg?(0.5FOV)I2))
`
`Attorney Docket No.: FLVT3004
`gbr/flvt/3004.000.provisional.wpd
`
`12/26/2000
`
`10 of 17
`
`Microsoft Corp. Exhibit 1067
`
`10 of 17
`
`Microsoft Corp. Exhibit 1067
`
`

`

`-10-
`
`| = max(0, min(l, M))
`
`For example, using a 64x64target grid display to render the image from a view
`of height N with FOV angle of 90 degrees, with the length of each pixel in space
`being one, the entire target image can befitted precisely to the display as
`demonstrated by:
`
`| = log, (N*/(647 *1 *1 °17))=M
`
`Rendering Memory GarbageCollection Process:
`The memory amountused by the above image parcel data selection and
`rendering process can be,
`in general, extremely large. An efficient form of
`garbage collection is
`required to prevent out-of-memory conditions while
`minimally impacting the performance requirements of the client system.
`Particularly on low performance and memory constrainedclient systems, such as
`PDAsandcellphone, the garbagecollection process needs to beefficient both in
`terms of the processor overhead as well as in the memory requirements of the
`garbagecollection control structures.
`In the present invention, a texture cache is used as the basis for garbage
`collection. The texture cache includes a buffer with a pre-determinedsize thatis
`sufficient to store a defined numberof image data parcels. Every rendering of a
`cell places the resulting image data and the image data ofallofits parentcells
`in a quad-tree structure stored sequentially upward inthe buffer. Each time a new
`imageis to be inserted into the texture cache buffer andthereis insufficient free
`space, the image data for the quad-tree structure logically positioned at the
`
`Attorney Docket No.: FLVT3004
`gbr/flvt/3004.000.provisional.wpd
`
`12/26/2000
`
`11 of 17
`
`Microsoft Corp. Exhibit 1067
`
`]
`
`2 3
`
`4
`5
`6
`
`7 8
`
`9
`
`
`
`10
`
`11
`12
`13
`14
`
`15
`~
`16
`S 17
`=
`18
`19
`20
`21
`22
`23
`24
`25
`
`11 of 17
`
`Microsoft Corp. Exhibit 1067
`
`

`

`-11-
`
`]
`2
`3
`4
`
`bottom of the buffer is removed and the corresponding buffer memory reclaimed
`as free buffer memory. The optimal size of the texture cache may not be
`determinable analytically, but is easily subject to empirical analysis to identify an
`optimal size.
`
`
`
`Attorney Docket No.: FLVT3004
`gbr/flvt/3004.000.provisional.wpd
`
`12/26/2000
`
`12 of 17
`
`Microsoft Corp. Exhibit 1067
`
`12 of 17
`
`Microsoft Corp. Exhibit 1067
`
`

`

`
`
`
`
`1X9}JO,JaAe]peo1UdeIs
`
`sjuswajaGepueqz
`
`‘Sigs
`hasBs
`
`i/s
`
`
`
`sjaxidpaywijuy
`
`GINPewuyup)
`
` ”OSplia@aoe
`
`o1udeiboasy
`
`sjeuuue|SIIQOIWUldz
`
`SOie
`
`aAlpedsiad
`
`XISUJIMQE
`
`josaaiBap
`
`wopsal
`
`13 of 17
`
`Microsoft Corp. Exhibit 1067
`
`13 of 17
`
`Microsoft Corp. Exhibit 1067
`
`
`
`

`

`
`
`FIG.2
`
`14 0f 17
`
`Microsoft Corp. Exhibit 1067
`
`14 of 17
`
`Microsoft Corp. Exhibit 1067
`
`

`

`3/8
`
`64
`
`64
`
`64
`
`64
`
`
`
`
`
`64
`
`64
`
`64
`
`64
`
`FIG. 4
`
`15 of 17
`
`Microsoft Corp. Exhibit 1067
`
`15 of 17
`
`Microsoft Corp. Exhibit 1067
`
`

`

`ds
`
`
`
`
`FIG.5
`
`16 of 17
`
`Microsoft Corp. Exhibit 1067
`
`16 of 17
`
`Microsoft Corp. Exhibit 1067
`
`

`

`S/S
`
`Q
`
`\O
`
`O o
`
`y
`
`64
`
`64
`
`64
`
`
`
`17 of 17
`
`Microsoft Corp. Exhibit 1067
`
`17 of 17
`
`Microsoft Corp. Exhibit 1067
`
`