`Bradium Technologies LLC - patent owner
`Microsoft Corporation - petitioner
`IPR2016-00448
`
`1
`
`
`
`Independent claims 1, 7, 12 and 16 are reproduced hereinbelow with part annotations a,
`
`b, c, d, e. . .added, for ease of referencing to the various components:
`
`Claim 1 relates to a client system for dynamic visualization ofimage data provided
`
`through a network communications channel, said client system comprising:
`
`Q11 a parcel request subsystem, including a parcel request queue, operative to request
`
`discrete image data parcels in a priority order and to store received image data parcels
`
`in a parcel data store, saidparcel request subsystem being responsive to an image parcel
`
`request ofassignedpriority to place said image parcel request in saidparcel request
`
`queue ordered in correspondence with said assignedpriority; and
`
`(131 an parcel rendering subsystem coupled to saidparcel data store to selectively retrieve
`
`and render received image data parcels to a display memory, saidparcel rendering
`
`system providing saidparcel request subsystem with said image parcel request ofsaid
`
`assigned priority.
`
`Applicant affirms that the parcel request subsystem and the parcel rendering subsystem
`
`were reduced to practice by 24 January 2000.
`
`A copy of archived source code, substantially identical to that of the version of January
`
`2000 is appended herewith. This source code shows how the invention was reduced to
`
`practice by being programmed into a working system implementation and is proof of
`
`Reduction To Practice in that it demonstrates that the claimed invention was programmed
`
`and worked. Applicants affirm that the code is substantially that of the version of
`
`December 1999.
`
`Specifically, the “Parcel Request Subsystem” (a) consists of multiple consumers, and a
`
`single producer. The function “DLDownloaderThread” is executed from four threads
`
`running in parallel to the main program (See “DLStartDownloaderThreads” and
`
`“DLStopDownloaderThreads”). Each of those threads acts as a consumer of the “Parcel
`
`Request Queue”. The priority queue is implemented over a stack of sorted items named
`
`“DTL”. The consumers extract items fi'om the top of the stack. The main program acts as
`
`2/ll0
`
`2
`
`
`
`a producer of parcel requests. The function to consume requests from the queue is named
`
`DLGetNext.
`
`The fimction “RenderQuads”, in addition to rendering the visible images parcels on the
`
`display, also creates requests for parcels that are needed, and evaluates the priority of
`
`each request as described in the patent, using function DLAdd. The fimction DLManager
`
`places these requests inside an array, sorts it by priority and replaces the previous stack
`
`(Parcel request queue) with the contents of the sorted array.
`
`The priority computation in function DLAdd is performed according to the priority
`
`evaluation method explained in the patent application, see paragraphs 59-69 thereof.
`
`The fimction GenerateTileOffset computes the offset of each requested parcel inside the
`
`“Parcel data store” described by the patent. There is an explicit assumption of 2KB per
`
`compressed parcel in the data store, possible through use of a fixed-rate compression,
`
`which makes the implementation very simple.
`
`The producer side of the Parcel Request Subsystem (explained earlier) in effect shows
`
`implementation ofparcel rendering subsystem (b).
`
`This is also supported by the following routines and functions: DLAdd, DLReset,
`GenerateOffsetTable, GenerateTileOffset
`, Polygonsurface, Distort, Httpl 1Request ,TileManagerRender RecalcTilePlane
`
`DrawTileMap, Texe|Density, TileGetDrawlevel, Fast_WithinFrustrum, QuadMake,
`
`RenderQuads, FrustrumClipper,
`
`All functions in modules Raster.cppand Tex.cpp
`
`Claim 7 relates to a portable display client system supporting dynamic visualization of
`
`image data provided through a wireless network communications channel, said client
`
`system comprising:
`
`Q) a display ofdefined resolution suitablefor visual presentation ofa graphical image,
`
`said display including video memoryfor storing image data representative ofsaid
`
`graphical image;
`
`(Li) a network interface coupleable to a wireless network through which
`
`3/110
`
`3
`
`
`
`to request and receive image data parcels;
`
`[_e1 an image parcel data store providingfor the storage of image data
`
`parcels;
`
`(fl navigation controls providing input information defining a point of
`
`view location relative to said graphical image; and
`
`Q1 a processor coupled to said video memory, network interface, image
`
`parcel data store, and navigational controls, saidprocessor operative to
`
`selectively request image data parcels ofdetermined resolution through said
`
`network interface in a priority order computed relative to the defined resolution
`
`ofsaid display.
`
`Applicant asserts that the invention of claim 7 was reduced to practice in December 1999.
`
`All components related to in claim 7 were implemented in the software prior to January
`
`2000. Fragments of source code given herewithin show this implementation.
`
`The display of defined resolution suitable for visual presentation of a graphical image (c)
`
`is supported by the FlipWindow function.
`
`The Network interface (d) is utilized by the function Httpl1Request, which is used to
`
`retrieve image parcels through the HTTP/1.1 protocol.
`
`The function “Dynamic_Camera” implements various navigation commands which
`
`respond to various keystrokes. This supports (0 the navigation controls providing input
`
`information defining a point ofview location relative to said graphical image.
`
`The hardware specified in (c), (e), (g) by virtue of being hardware, cannot be directly
`
`shown in any source code of course. Nevertheless, evidence that these components were
`
`available in January 2000 is given through inference and via the OS API and runtime
`
`library calls. As evidenced by calls to functions such as GetAsyncKeyState, BitBlt and
`
`socket, the program interacted with these hardware elements, available in January 2000
`
`and described in the provisional patent specification filed in December of that year.
`
`4/110
`
`4
`
`
`
`Claim 12 relates to a client system providingfor the three-dimensional viewing ofan
`
`image relative to a dynamic viewpoint, said client system comprising:
`
`Q1 display memory corresponding to a two—dimensional display of
`
`defined resolution;
`
`(Q a network interface through which image data parcels ofrespective
`
`image parcel resolution can be requested and received;
`
`[[1 navigational controls providingfor the definition ofan image
`
`viewpoint; and
`
`$1 a processor operative to progressively render image data parcels into
`
`said display memory and to progressively request image data parcels through
`
`said network interface in a priority order determined with respect to the defined
`
`resolution ofsaid two dimensional display and the location ofsaid image
`
`viewpoint.
`
`Applicant asserts that the invention of claim 12 was similarly reduced to practice by
`
`December 1999.
`
`(h) is evidenced by InitDevice and FlipWindow
`
`Further evidence that these components were available in January 2000 is given through
`
`inference and via the OS API and runtime library calls. As evidenced by calls to
`
`functions such as GetAsyncKeyState, BitBlt and socket, the program interacted with
`
`these hardware elements, available in January 2000 and described in the provisional
`
`patent specification filed in December of that year.
`
`The Network interface (i) is utilized by the function Http1lRequest, which is used to
`
`retrieve image parcels through the H l
`
`I P/1.1 protocol.
`
`The navigation controls providing input information defining a point ofview location
`
`relative to said graphical image (j) are supported by the fimction “Dynamic_Camera”
`
`which implements various navigation commands in response to various keystrokes.
`
`5/110
`
`5
`
`
`
`The hardware specified in (k), by virtue of being hardware, cannot be directly shown in
`
`any source code.
`
`We afinn that all components related to in claim 12 were implemented in the sofiware by
`
`24 June 2000. The fragments of source code given hereabove support this afirmation.
`
`Claim 16 relates to a method ofsupporting dynamic visualization of image data
`
`transferred through a communications channel, said method comprising the steps of
`
`[Q determining, in response to user navigational commands, a
`
`viewpoint orientation with respect to an image displayed within a three-
`
`dimensional space;
`
`in) requesting, in a priority order, image parcels renderable as
`
`corresponding regions ofsaid image, each said image parcel having an
`
`associated resolution, wherein saidpriority order is determined to provide a
`
`progressive regional resolution enhancement ofsaid image as each said
`
`image parcel is rendered;
`
`Q2) receiving a plurality of image parcels through said communications
`
`channel; and
`
`(g)_rendering saidplurality ofimage parcels to provide said image.
`
`(1) is supported by the function “Dynamic_Camera” which implements various
`
`navigation commands which respond to various keystrokes,
`
`(m) is implemented in the producer side of the Parcel Request Subsystem, by fimctions
`
`including:
`
`DLAdd, DLReset, GenerateOffsetTab]e, GenerateTileOffset, , Polygonsurface, Distort,
`
`Httpl 1 Request
`
`6/110
`
`6
`
`
`
`(n) is implemented in the function Httpl lRequest, which is used to retrieve image parcels
`
`through the HTTP/ l .1 protocol
`
`See also DLReceive which processes the output from the Parcel Request Subsytem,
`
`creating a 64 by 64 texture map by applying the image decoder on the received data
`
`block, using the function DecodeFxtl . The FXTI texture compression format has a fixed
`
`rate compression of 4 bits per pixel, yielding 2KB of data per each compressed 64 by 64
`
`image parcel. This matches the compression rate for parcels specified in the patent
`
`application.
`
`(0) is implemented by the functions “TileManagerRender” and its subroutines
`
`(“DrawTileMap”, “QuadMake” “RenderQuads”, “Fast_WithinFrustrum”,
`
`“SpliceVertex”, “FrustrumClipper” among others) which render the image data to the
`
`system display. See alsoTileRecalcPlane, TexelDensity, TileGetDrawlevel, All functions
`
`in modules Raster.cpp and Tex.cpp
`
`Applicant asserts that all components related to in claims 1, 7, 12, 16 were implemented
`
`in the sofiware in December 1999, prior to publishing of the Website Presentation on the
`
`Internet as shown by Exhibit B.
`
`As evidenced by Exhibit C, GA Central Executive Summary (appended herewithin as
`
`Exhibit Ci) was written up by 20 March 2000 and Power Point Presentation GA
`
`Central2.ppt (Exhibit Cii) was written up by 13 May 2000. These documents provide
`
`further proof that the working system, including code appended hereto, were in
`
`applicant’s position prior to the filing date of US 6,671,424 to Skoll, which was filed in
`
`July 2000.
`
`Exhibit D is a screen shot extracted from Exhibit Cii, which, as evidenced by Exhibit C,
`
`was written on or before 13 May 2000. Applicant affirms that the screen shot shown in
`
`Exhibit C was obtained by running the program that embodies the invention as claimed in
`
`claims 1, 7, 12 and 16, back in December 1999. This supports Applicant’s claim that the
`
`invention as shown in source code appended herewith was in their posession in
`
`December 1999 which is six months prior to the filing date of US 6,671,424 to Skoll,
`
`which was filed in July 2000.
`
`7/110
`
`7
`
`
`
`Exhibit E and G are screen captures from December 1999 that shows that the program
`
`whose source code is appended herewith was indeed up and running at that time.
`
`It will be noted that although the code appended may have been minorly revised during
`
`maintenance, and may not perfectly match the initial implementation however it shows
`
`that the present invention as claimed was indeed reduced to practice.
`
`Applicant has thus demonstrated that the invention as claimed in claims 1, 7, 12 and 16
`
`was reduced to practice prior to July 2000 and respectfully submits that US 6,671,424
`
`Skoll, which was filed in July 2000, is not prior art to these claims.
`
`If claims 1, 7, 12 and 16 are inventive, then dependent claims 2-6, 8 to 11 and 17 to 20
`
`are inventive as well. We respectfully submit that claims 1 to 11 and 16 to 20 are thus
`
`allowable, and request that Examiner withdraws his objections of March 17 2006 and
`
`allows the claim set of USSN 10/035,981 as filed.
`
`3. The evidence submitted is sufficient to establish a reduction to practice of the
`
`invention in the US or a NAFTA or WTO member country prior to the effective date of
`
`the Robotham reference.
`
`4. We hereby declare that all statements made herein are of our own knowledge and are
`
`true. All statements made on information and belief are believed to be true. All
`
`statements are made with knowledge that willful false statements and the like so made are
`
`punishable by fine or imprisonment or both, under Section 1001 of Title 18 of the Unites
`
`States Code and that such willful statements may jeopardize the validity of the
`
`application or any patent issued thereon.
`
`» ea»:
`
`Isaac Levanon
`
`Dated: June 13, 2006
`
`
`
`8/110
`
`8
`
`
`
`EXHIBITS
`
`EXHIBIT A
`
`wms3,333
`- Stepping Sign:-e!
`
`9/110
`
`9
`
`
`
`Exhibit B
`
`Locate obstacles
`around the airfield
`
`Business to Business
`E-Commerce
`Marketplace
`
`Information, AirNav,
`FAA, etc.
`
`,-
`
`—
`
`Instant Messaging,
`_
`Chat Room
`Aircraftfi Pilot 1
`Network.
`FY31’
`
`llisual approach 1 —-—.., ‘E
`procedures
`
`- ‘Aviation Ground
`’
`services info
`
`Proprietary Flyover
`"2 3D Airfield Image
`
`Communication &
`Navigation Data
`
`Moving orientation
`maps (VFR chart, area
`road map, etc.)
`
`1
`
`7..., r;mp.z.:.{
`.- X
`..
`..,— For .‘.....
`sausauszos P:?'atIo;‘-
`
`
`
`
`
`
`
`
`j :1; 55; M
`x
`91"‘ A‘:-Tlflfliliofl
`
`:u§.1:{ a-51;
`'—-- _ ' ""'T.'."'
`
`’
`
`I177‘
`-‘W--"-"‘
`
`.
`
`. Passengers’ services
`& accommodation
`A
`
`National and Iocfl
`-
`-
`advertising
`
`E-commerce
`_-
`Marketplace - selected
`option
`
`10
`
`10/110
`
`10
`
`
`
`
`
`2-
`
`‘ -.
`
`‘7’
`
`‘
`
`"‘1'I
`
`ugf‘ .;.;,;..
`
`“‘““*:.“
`
`*".......... ..
`
`M‘.
`
`;.....m‘“*"'”’“....nT“
`
`e M
`
`-
`
`'
`
`=;,.<..,.,j.:
`
`GA Central - Executive Microsofi Word
`
`Summary.doc
`
`Document
`
`odified 2
`3/20/2000 6:02 PM 1,689,600
`
`GA Central2.ppt
`
`Microsofi PowerPoint
`Presentation
`
`5/13/2000 12:20
`AM
`
`83 6,096
`
`11
`
`11/110
`
`11
`
`
`
`7
`
`_.__.
`
`__7
`
`
`
`" 1?
`
`
`
` V
`
`
` J%%A3Dvg
`
`E;.-“.11;.-PAfO'p;[;i_§taJ?y73.. .
`
`' léhigheresiolution
`ima%geL (s atel,|ite‘ {oi .
`
`.%
`
`’
`
`F I!nternét‘Lat% af*bou‘t4%%V
`iwith
` F
`
`‘
`
`%
`
`_
`
`L
`
`:
`
`‘_:.:)t_,.
`
`I
`
`
`
`.. J
`xx”
`
`.
`
`-
`
`‘
`
`a
`
`12/110
`
`12
`
`
`
`Exhibit E
`
`Compression
`Proprietary scheme
`Selectable 1:2 - 1:14
`
`
`
`
`
`
`Resolution Tiling
`
`13/110
`
`13
`
`
`
`Exhibit F
`
`
`
`NETWORK IMAGE
`DELIVERY WITH DYNAMIC
`
`"A
`I
`3'
`flue
`Irflféb
`
`aeriafi/..i3a1'eIIire
`
`.r‘ed:3fic’ maneuve“' I (5
`
`fiyokA‘ ‘ is based-jinn exrnamdy erficiem
`easy to r.5e.5afi'wan_= ‘tools fbr
`aiguridrrn,
`wry Iarge area of
`.resalt:1‘ian'calariir)a'ye;'
`H
`'
`I
`
`‘A
`
`'
`
`‘A
`
`
`
`Proprietary ’3D-engine Streaming high-
`._
`_. resolution image (satellite or aerial
`_<phot’ogr_aph) ov_er_the |nterne't_at;_about 4klse%.".“_fi _|MB
`
`- withslx degrees of freedom
`“flamed pixels.
`
`19% ‘
`
`'
`
`Streaming over
`Internet and (future)
`
`Phones
`
`
`
` NETWORK IMAGE
`
`DELIVERY WITH
`
`DYNAMIC
`
`VIEWING
`
`FRUSTUM
`OPTIIVIIZED
`
`FOR
`
`NARROWBAND
`
`COMMUNICATION
`(‘In mural s
`
`
`
`14/110
`
`14
`
`
`
`Exhibit G
`
`
`Incremental
`streaming
`.
`
`
`
`Rebuild
`tiles and
`
`resolutions
`
`'IIIIIIfl'lI§‘I(Dl’IlfBI'll!’
`
`I
`/7__:5’E.H ‘
` £7LE’£3B ~
`,9-lrrzaaauacup.-.—....-an -'
`3VI/I/IIIJIIUIIFIIIIIJEll’V "
`
`
`
`'n"snfl1aia"ri:-€hjas_ed‘real-_-time s'rn’aIt.'s1ream'””_ing‘?a"g"erIt’t‘ig'I"rt'!7y_:E
`"Extremv elf‘
`enuplefl-tn. effisiierns-3!)-eAn_q_ine.T flesederv-and re_al-"tune
`
`of multi-Resolutions
`
`Request multi-tiles
`
`Real-time filters
`
`
`
`15/110
`
`15
`
`
`
`Exhibit H
`
`16
`
`16/110
`
`16
`
`
`
`Exhibit H continued
`
`17
`
`17/110
`
`17
`
`
`
`Source code listing
`
`APPENDIX (I)
`
`Module: MapTiles.cpp
`
`
`// Download recieve: {His i§"E§iIEE"B§"EEE'bowni3§3E§““"'"'"
`threads when they finish downloading
`// one of the map tiles. It decodes the FXTl
`generates a texture which is
`// inserted to the texture cache.
`
`image and
`
`void DLRecieve(MapTile *MT, byte *pBuf)
`{
`
`Image *Img = new Image;
`
`DecodeFxt1(pBuf,
`
`Img);
`
`if (!Img—>pData)
`{
`
`printf("*** ARPA ALARMS: Failed to D/L texture
`from map server\n");
`A
`return;
`
`} i
`
`{
`
`f ((Img—>xRes> g_TM.TileSize)I|
`(Img—>yRes > g_TM.TileSize))
`
`printf("*** ARPA ALARMS: Downloaded image is too
`large (incorrect TM setup?)\n");
`//return;
`
`} i
`
`{
`
`}
`
`f ((Img->xRes< g_TM.TileSize)|l
`(Img—>yRes < g_TM.TileSize))
`
`ImagePadding(Img);
`
`# i fnde f _FLY___OVER_WIN_CE
`__MAPPER__Tile4(Img); // ??? if i want to use the ref-
`resterizer put this line remark. and hit R
`#endif
`
`// before removing eya1+gilad memory trick
`
`word *w = new word[64*64*5];
`//memcpy(w
`,Img—
`>pData,sizeof(word)*64*64);
`
`/*
`
`18/110
`
`18
`
`18
`
`
`
`memcpy(w+64*64*4,Img-
`>pData,si2eof(word)*64*64);
`DWORD I;
`for(I=0;I<64;I++)
`memcpy(w+256*I,Img—
`>pData+64*I,sizeof(word)*64);
`
`delete Ing—>pData;
`
`Img—>pData=w;
`// Texture -> 256x64
`
`//__MAPPER_ImagePadding(Img);
`//__MAPPER_Align64(Img);
`
`Img—>pData += 64*64*4;
`__MAPPER__Tile4(Im9):
`Img—>pData —= 64*64*4;*/
`
`// end - before removing eyal+gilad memory trick
`
`// tiling shit
`TTexStorage_Add(MT,Img—>pData);
`delete Img;
`//Insert2TCache(MT,Img—>pData);
`//delete Img—>pData;
`//MT—>Texture = Img;
`use a non—padded texture
`/*
`if (MT->Flags & MT_JIT)
`{
`
`//SYNCED! so engine wont try to
`
`int wtf = 1;
`
`}*/
`
`//MT—>Flags &= ~MT_Downloading;
`
`} /
`
`/ Resets the download request list
`static void DLReset()
`{
`
`dword i;
`
`for(i=0;i<g_TM.DLNumRequests;++i)
`{
`
`g_TM.DLRequests[i].MT—>DR = NULL;
`
`} g
`
`_TM.DLNumRequests = 0;
`
`19
`
`19/110
`
`19
`
`
`
`// Garage Operation.
`master index file)
`static void GenerateOffsetTable()
`{
`
`(Calculates offsets inside map tile
`
`// BASE OFFSET: 1K
`
`const dword BASE_OFFS = 1024;
`// IMAGE CELL SIZE (TSxTSx16bit using FXTl): 4bit *
`
`TS“2
`
`const dword BASE_HEADER = 16;
`g_TM.IMAGE_CELL_SIZE =
`((g_TM.TileSize*g_TM.TileSize)>>l)+BASE_HEADER;
`
`dword I,OFFS = BASE_OFFS;
`
`for(I=O;I<g_TM.MaxLevel;I++)
`{
`
`// LEVEL OFFSET: #Tiles(T|Lvl(T)=L)
`IMAGECELLSIZE
`
`*
`
`dword S = g_TM.TSize[I];
`dword X = (g_TM.XSize+Sr1)/S;
`dword Y = (g_TM.YSize+S-1)/S;
`g_TM.XTiles[I] = X;
`g_TM.Offs[I] = OFFS;
`
`//divide + round up
`//divide + round up
`
`OFFS += X*Y*g_TM.IMAGE_CELL_SIZE;
`
`} /
`
`/ calculates offset inside map tile master index file,
`given the Texture's level and
`// (X,Y)
`in that level's tile grid.
`static dword GenerateTileOffset(dword Level,dword X,dword
`Y)
`{
`
`return g_TM.Offs[Level] + (X + Y *
`g_TM.XTiles[Level])*g_TM.IMAGE_CELL_SIZE;
`
`} /
`
`/ Distorts coordinates to create the fisheye effect needed
`for prioritizing
`'
`// cells at the view's center (focus) over peripheral
`regions
`// dfactor: distortion factor [0,1]. dfactor=1 has no
`distortion effect
`
`static inline float Distort(float x,float dfactor = 0.35)
`{
`
`if (x>0)
`
`20/110
`
`20
`
`
`
`1
`
`return (float)pow(x,dfactor);
`} else {
`
`return —(float)pow(—x,dfactor);
`
`} r
`
`eturn 0.0;
`
`} /
`
`/ Computes the surface of the polygon currently stored in
`the frustrum clipper
`// can work either pre or post clipping
`static float PolygonSurface()
`{
`
`long i;
`float s = 0.0f;
`Vertex *A,*C;
`
`A = C_Prim[0];
`
`float ax = Distort(A—>PX /
`l.Of),
`
`(float)(g_xRes*O.5f)
`
`-
`
`.
`
`ay = Distort(A—>PY /
`
`(float)(g_yRes*0.5f) -
`
`l.Of);
`
`C = C_Prim[i];
`float cx = Distort(C—>PX /
`1.0f),
`
`cy
`
`Distort(C—>PY /
`
`(float)(g_xRes*0.5f)
`‘
`(float)(g_yRes*O.5f) -
`
`-
`
`l.Of);
`float bx,by;
`
`for(i=2;i<C_NumVtx;++i)
`{
`
`bx
`
`by
`
`cx;
`
`cy;
`
`C = C_Prim[i];
`cx = Distort(C—>PX / (float)(g_xRes*0.5f) -
`ll
`
`cy
`
`Distort(C—>PY /
`
`(float)(g_yRes*0.5f) —
`
`’1.0f);
`
`l.Of);
`
`s += (ax * by - bx * ay) +
`(cx * ay — ax * cy) +
`(bx * cy - cx * by);
`
`} r
`
`eturn (float)fabs(s);
`
`} /
`
`/ Add maptile to the list of requested downloads.
`// DLev (Draw level) is used to determine the priority of
`the request.
`
`21/110
`
`21
`
`21
`
`
`
`// Draw level should be the texture detail level in which
`the map tile would have
`// been drawn if all the textures were available
`(mipmapping limit)
`static void DLAdd(Quad *Q,MapTile *MT)
`{
`
`/*
`
`long DLev = Q—>drawlev;
`if (!MT)
`{
`
`int gagaga=1;
`
`}*/
`if (MT—>F1ags&MT_Downloading) return; //I know all
`about the Zerg, Gerard.
`
`dword I;
`if (MT—>DR)
`
`{
`
`I = MT—>DR — g_TM.DLRequests;
`} else {
`
`if (g_TM.DLNumRequests==g_TM.DLMaxRequests)
`{
`M
`
`.
`
`g_TM.DLMaxRequests+=DLMaxInitialRequests;
`g_TM.DLRequests = (DownloadRequest
`*)realloc(g_TM.DLRequests,g_TM.DLMaxRequests*sizeof(Downloa
`dRequest));
`
`} I
`
`= g_TM.DLNumRequests++;
`g_TM.DLRequests[I].MT = MT;
`g_TM.DLRequests[I].FOffset =
`GenerateTi1eOffset(MT->Level,MT—>TX,MT->TY);
`
`g_TM.DLRequests[I].Priority = 0;
`MT—>DR = g_TM.DLRequests+I;
`
`} /
`
`/GenerateTileFilename(g_TM.DLRequests[I].Name,MT-
`>Level,MT—>TX,MT—>TY);
`/*
`if (MT->Level==4)
`{
`
`int debug_me_now
`
`1;
`
`}*/
`
`//g_TM.DLRequests[I].Priority = 128+MT—>Level*2—DLev;
`g_TM.DLRequests[I].Priority += PolygonSurface(); // *
`(1<<((DLev—MT—>Level) << 1));
`}
`
`-
`
`22/110
`
`22
`
`22
`
`
`
`// Creates child nodes for parameter maptile.
`called whenever the tile
`
`This is
`
`// has a draw level greater than its own level.
`own texture is available]
`
`[and its
`
`static dword MapTileExpand(MapTile *MT)
`{
`
`if
`
`expanded
`if
`
`(MT—>Flags&MT_Expanded)
`
`return 1;
`
`//already
`
`(!MT->Texture) return 0:
`
`// no texture recieved yet
`
`MT—>Flagsl=MT_Expanded;
`dword Level = MT—>Level+1;
`
`if (Level==g_TM.MaxLevel) return 1;
`
`dword xE = MT—>X+g_TM.TSize[Level];
`dword yE = MT—>Y+g_TM.TSize[Level];
`dword xOK = xE<g_TM.XSize;
`dword yOK = yE<g_TM.YSize;
`
`MT->M00 = new MapTile;
`memset(MT—>M00,0,sizeof(MapTile));
`MT->M00—>Level = Level;
`MT->M00->X = MT—>X;
`MT->M0O->Y = MT—>Y;
`MT->M00->TX
`MT—>TX<<l;
`MT->MO0->TY
`MT->TY<<l;
`MT->M0O—>Parent = MT;
`
`(XOK)
`
`if
`
`{
`
`MT->MO1 = new MapTile;
`memset(MT—>M0l,0,sizeof(MapTile));
`MT—>M01—>Level = Level;
`MT—>MO1—>X = XE;
`MT->MOl->Y = MT->Y;
`MT->MO1->TX = (MT—>TX<<l)+1;
`MT—>MO1->TY = MT->TY<<l;
`MT—>M01->Parent = MT;
`
`} i
`
`{
`
`f
`
`(YOK)
`
`MT->Ml0 = new MapTile;
`memset(MT->M10,0,sizeof(MapTile));
`MT—>Ml0~>Level = Level;
`
`23
`
`23/110
`
`23
`
`
`
`MT->Ml0—>X
`
`MT->X;
`
`yE;
`MT—>M10->Y
`MT->M10->TX = MT->TX<<1;
`MT—>Ml0->TY = (MT->TY<<1)+l;
`MT—>M10—>Parent = MT;
`
`} i
`
`{
`
`}
`
`f (xOK&&yOK)
`
`MT->M11 = new MapTile;
`memset(MT—>M11,0,sizeof(MapTile));
`MT—>Ml1—>Level = Level;
`MT—>Mll—>X = XE;
`
`MT—>M11—>Y = yE;
`MT->Ml1->TX = (MT->TX<<1)+l;
`MT—>Ml1—>TY = (MT—>TY<<l)+1;
`MT—>M1l—>Parent = MT;
`
`..
`
`return 1;
`
`.
`
`_
`
`. _.
`
`} /
`
`/ should be called for each frame. determines the plane
`equation
`transformed to camera space.
`// of the map,
`void TileRecalcPlane()
`{
`
`in world coordinates,
`// fundamental information:
`// Origin is always at (0,0,0),
`the normal is always
`(0,110)
`// XAxis is (1,0,0) and YAxis is (0,0,1).
`
`Image is inverted on the Y Axis, so Origin is
`// Note!
`shifted and axis is flipped
`
`Vector3 U;
`
`float *VM = g_TM.Cm—>VM;
`// calculate new origin
`
`Vectorscale(&g_TM.Cm—>Position,—1.0f,&U);
`MatrixXVector(VM,&U,&g_TM.Origin);
`
`// calcuate new axes
`VectorMake(&g_TM.XAxis,VM[0],VM[3],VM[6]); // VM *
`(1/0:0)
`VectorMake(&g_TM.Norm ,VM[1],VM[4],VM[7]); // VM *
`(01110)
`
`24/110
`
`24
`
`24
`
`
`
`VectorMake(&g_TM.YAxis,—VM[2],-VM[5],-VM[8]): // VM *
`(0,011)
`
`Vectorselfscale(&g_TM.XAxis,g_TM.TexelSize);
`Vectorselfscale(&g_TM.YAxis,g_TM.TexelSize);
`Vectorscale(&g_TM.YAxis,-
`(float)g_TM.YSize,&U);//g_TM.TSize[0]
`VectorSelfAdd(&g_TM.Origin,&U);
`
`g_TM.PO =-VectorDot(&g_TM.Norm,&g_TM.Origin);
`
`} /
`
`/ Determines the size one map texel at location (x1,yl) on
`the map has on the display after projection
`float TexelDensity(float x1,float yl)
`{
`
`Vector3 V:
`
`VectorMake(&V,g_TM.Origin.x +.xl * g_TM.XAxis.x + yl
`g_TM.YAxis.x,
`
`*
`
`g_TM.Origin.y + x1 * g_TM.XAxis.y +
`
`yl
`
`* g_TM.YAxis.y,
`
`yl * g_TM.YAxis.z);
`
`g_TM.Origin.z + x1 * g_TM.XAxis.z +
`
`float z = V.z*g_TM.Tilesize/g_TM.TSize[0];
`float z2 = z*z;
`VectorNorm(&V);
`
`float ca = —VectorDot(&g_TM.Norm,&V);
`
`return g_TM.Cm—>VP->Mipfactor * ca / 22;
`
`} /
`
`/ efficient Log2 operation on 32bit float (single
`precision) type
`long Log2(float x)
`{
`
`long dwrep = *(long *)(&x);
`long exponent = (dwrep>>23)—l27;
`
`return exponent;
`
`} /
`
`/ returns highest mipmapping level on a transformed
`Quadritheral,
`// Sucks. should be based on pix/tex Area ratio computation
`void TileGetDrawlevel(MapTile *MT,dword *h)
`{
`
`25/110
`
`25
`
`25
`
`
`
`// calculate camera [x,y] on tile plane coordinate
`float ratio =-1.0f/(g_TM.TexelSize*g_TM.Texelsize);
`long ox =
`(long)(ratio*VectorDot(&g_TM.Origin,&g_TM.XAxis));
`long cy =
`(long)(ratio*VectorDot(&g_TM.Origin,&g_TM.YAxis));
`
`long x1 = MT—>X;
`long yl = MT—>Y;
`
`long x2 = MT—>X+g_TM.TSize[MT->Level];
`long y2 = MT->Y+g_TM.TSize[MT->Level];
`
`if (cx<x1) cx = x1;
`else if (cx>x2) cx = x2;
`
`if (cy<y1) cy = yl;
`else if (cy>y2) cy = y2;
`
`(x2,y2)
`(x1,y1) Furthest
`// Nearest
`long lvl = Log2(TexelDensity((float)cx,(float)cy))>>l;
`// log4(dens)
`long s1 = lvl>=(long)g_TM.MaxLevel ? g_TM.MaxLevel-1 :
`
`lvl;
`
`*h
`
`sl>0 ? sl
`
`: O;
`
`} /
`
`/ This is a recoursive function which builds up the
`Rendering information.
`// Either it recourses or calls QuadMake,
`the entire visible
`
`thus rendering
`
`// portion of the map.
`void DrawTileMap(MapTile *MT,Vector3 *A,Vector3 *B,Vector3
`*C,Vector3 *D)
`{
`
`dword high;
`TileGetDrawlevel(MT,&high);
`// LA-Z-Eval: if high>MT->Level, maptileexpand will be
`called,
`// and if failed, entire quad will be drawn without
`expanding
`if (high<=MT—>Leve1l|(!MapTileExpand(MT)))
`{
`
`//if (high>MT—>Level) high=MT—>Level;
`// draw Tile as a Quad
`
`float xFrac = 1.0f,yFrac = l.Of;
`if (MT->X+g_TM.TSize[MT—>Level]>g_TM.XSize)
`
`26/110
`
`26
`
`26
`
`
`
`xFrac =
`
`(float)(9\TM.XSize-MT-
`>X)/(float)g_TM.TSize[MT—>Level];
`if (MT—>Y+g_TM.TSize[MT—>Level]>g_TM.YSize)
`yFrac =
`(float)(g_TM.YSize—MT-
`>Y)/(float)g_TM.TSize[MT—>Level];
`
`QuadMake(high,MT,A,B,C,D,xFrac,yFrac);
`return;
`
`}
`
`Vector3 AB,BC,CD,DA,ABCD;
`VectorAvg(A,B,&AB);
`VectorAvg(B,C,&BC);
`VectorAvg(C,D,&CD);
`VectorAvg(D,A,&DA);
`VectorAvg(&AB,&CD,&ABCD);
`if
`(MT->M00)
`DrawTileMap(MT->M00,A,&AB,&ABCD,&DA);
`if
`(MT—>M01)
`DrawTileMap(MT—>M01,&AB,B,&BC,&ABCD);
`if
`(MT—>M11)
`DrawTileMap(MT—>Mll,&ABCD,&BC,C,&CD);
`if (MT->M10)
`DrawTileMap(MT->M10,&DA,&ABCD,&CD,D);
`
`} /
`
`/ stores the ngon visible from frustrum on map
`
`struct WF_Visible_NGon
`{
`
`Vector2 VA[12];
`dword Numvtx;
`
`};
`
`WF_Visible_NGon FWF_;
`
`// initializes the fast within—frustrum test routine
`
`void Fast_WithinFrustrum_Init(viewport *VP,Vector3 **V)
`{
`
`// intersect entire region with viewport
`// by calling f—clipper on a generated poly
`// somehow remove the call to drawer
`// XFORM v
`Vertex VA[4];
`long i;
`for(i=0;i<4;i++)
`{
`
`>X ‘O
`
`VA[i].TPos.x
`
`g_VP.CX * V[i]->z + g_VP.K * V[i]-
`
`VA[i].TPos.y
`
`g_VP.CY * V[i]->z — g_VP.K * V[i]-
`
`H
`
`VA[i].TPos.z
`
`V[i]->z;
`
`27/110
`
`27
`
`27
`
`
`
`M
`
`1.0f/VA[i].TPos.z;
`VA[i].RZ
`VA[i].PX VA[i].TPos.x * VA[i].RZ;
`VA[i].PY = VA[i].TPos.y * VA[i].RZ;
`VertexFlags(VA+i);
`C_Buf[i] = VA+i;
`
`} C
`
`_NumVtx = 4;
`
`C_Flags =
`Vtx_Visibility&(VA[0].Flags|VA[1].Flags|VA[2].Flags|VA[3].F
`lags);
`
`FrustrumClipper(NULL);
`
`// copy to FWF_
`FWF_.NumVtx = C_NumVtx;
`float rK = 1.0f/g_VP.K;
`for(dword I=0;I<C_NumVtx;I++)
`{
`
`// memcpy(FWF_.VA+I,C_Prim[I],sizeof(Vertex));
`// Inverse—Transform perspective and 3d—>map
`
`coordinate
`
`Vector3 V;
`
`V.z = 1.0f/C_Prim[I]—>RZ;
`float z = rK*V.z;
`
`V.x = (C_Prim[I]->PX-g_VP.CX)*2;
`V.y = (g_VP.CY—C_Prim[I]->PY)*z;
`//now V is a position in 3d[camera-space]
`
`(i
`
`hope)
`
`VectorSelfSub(&V,&g_TM.Origin);
`FWF_.VA[I].x =
`VectorDot(&V,&g_TM.XAxis)*g_TM.rTexelSize;
`FWF_.VA[I].y =
`VectorDot(&V,&g_TM.YAxis)*g_TM.rTexelSize;
`//IFontWrite(IFNT_STD, 10, 50+20*I, "Delimiter
`NGON (%f,%f)",FWF_.VA[I].x,FWF_.VA[I].y);
`
`} /
`
`/ complete cycle
`FWF_.VA[C_NumVtx].x = FWF_.VA[0].x;
`H
`FWF_.VA[C_NumVtx].y
`FWF_.VA[0].y;
`
`} d
`
`{
`
`word Within_NGon(Vector2 *U)
`
`dword I,J=0;
`
`28/110
`
`28
`
`28
`
`
`
`Vector? n,d;
`for(I=0;I<FWF_.NumVtx;I++)
`{
`H
`H
`
`].y — FWF_.VA[I+1].y;
`FWF_.VA[I
`FWF_.VA[I+1].x - FWF_.VA[I
`].x;
`= U—>x-FWF_.VA[I].x;
`= U->y-FWF_.VA[I].y;
`(n.x*d.x+n.y*d.y<0.0f) J+=1<<I;
`
`KNQIN
`
`f
`
`} r
`
`eturn J;
`
`} d
`
`{
`
`word Fast_WithinFrustrum(MapTile *MT)
`
`// square:
`//MT—>X,MT—>Y : MT—>X+g_TM.TSize[MT—>Level],...
`// NGON is supposed to be CCW,so, at least one
`// of the points is supposed to be inside ngon
`// WRONG! this _has_ to clip the square vs the ngon
`// (arg) or reject squares that are all on the
`negative
`// side of one of the edges of the ngon
`dword 1 = MT->Level;
`Vector2 U,V;
`
`V.x = (float)MT—>X*g_TM.TexelSize;
`V.y = (float)MT—>Y*g_TM.TexelSize;
`float edgelen = g_TM.TSize[l]
`* g_TM.Texe1Size;
`dword f1,f2,f3,f4; // clipping flags
`if (!(f1=Within_NGon(&V))) return 1;
`U.x = V.x+edgelen;
`U.y = V.y;
`if (!(f2=Within_NGon(&U)))
`U.y += edgelen;
`if (!(f3=Within_NGon(&U))) return 1;
`U.x = V.x;
`
`return 1;
`
`if (!(f4=Within_NGon(&U))) return 1;
`return (!(f1&f2&f3&f4));
`
`} /
`
`/ Generates a Quadritheral for rendering. xFrac and yFrac
`are used to build partial tiles.
`inline void QuadMake(dword drawleve1,MapTile *MT,Vector3
`*A,Vector3 *B,Vector3 *C,Vector3 *D,float xFrac,float
`yFrac)
`{
`
`// Verify the Quadritheral is within the viewing
`frustrum.
`
`29/110
`
`29
`
`
`
`if (!Fast_WithinFrustrum(MT)) return;
`
`Quad *Q = QuadGet();
`Q—>MT = MT;
`
`long texlevel = (drawlevel>MT—>Level)
`drawlevel;
`
`? MT—>Level
`
`:
`
`long leveldiff = MT—>Level — texlevel;
`long levelpenalty;
`long i,j;
`
`MapTile *PMT = MT; // Parent Maptile
`
`for(i=0;i<leveldiff;++i) PMT = PMT—>Parent;
`
`// Quad should use PMT's texture.
`// if it does not exist, we keep going up the tree
`until we find a maptile with
`// a texture (root should always have a texture)
`while ((!PMT—>Texture)||(PMT—>Flags & MT_Downloading))
`{
`
`if (PMT—>Parent)
`{
`
`PMT=PMT—>Parent;
`++leveldiff;
`——texleve1;
`} else {
`// Fatal Error: no texture available
`—-NumQuads;
`return;
`
`} /
`
`/ Calculate mapping coordinates
`float rdtex = 1.0f/g_TM.TSize[texlevel];
`
`float t1 = 1.0f/((float)(l<<leveldiff));
`float u = (MT—>X — PMT->X)*rdtex;
`float v = (MT—>Y — PMT—>Y)*rdtex;
`
`VeCtOr3 POS[4]; // Position vectors, scaled using
`xFrac and yFrac
`,A);
`VectorCopy(Pos
`VectorCopy(Pos+1,B);
`VectorCopy(Pos+2,C);
`VectorCopy(Pos+3,D);
`
`30/110
`
`30
`
`30
`
`
`
`VectorLERP(Pos+1,Pos
`,1.0f-xFrac);
`VectorLERP(Pos+2,Pos+3,1.0f-xFrac);
`VectorLERP(Pos+3,Pos
`,l.0f—yFrac);
`VectorLERP(Pos+2,Pos+1,1.0f-yFrac);
`
`Vertex *VA[4]
`Vertex *Vtx;
`Vector3 *V =
`
`= {&Q->A,&Q->B,&Q->C,&Q->D};
`
`Pos;
`
`// set up mapping coordinates
`xFrac * tl *(LEFTU/64.0f);
`float utl_ =
`yFrac * t1 *(LEFTU/64.0f);
`float vtl_ =
`float utl =
`xFrac * tl *
`(RIGHTU/64.0f);
`float vtl =
`(RIGHTU/64.0f);
`
`yFrac * tl *
`
`#ifdef HYPERBOLIC_MAPPING
`VA[0]->U = u+utl_+PMT—>TX;
`VA[0]—>V = v+Vtl_+PMT->TY;
`VA[l]—>U = u+utl +PMT->TX;
`
`VA[1]—>V = v+vtl_+PMT—>TY;
`VA[2]->U = u+utl +PMT—>TX;
`VA[2]->V = v+vtl +PMT->TY;
`
`VA[3]->U = u+utl_+PMT—>TX;
`VA[3]->V = v+vtl +PMT->TY;
`
`#else
`
`vA[o]+>U = u+utl_;
`VA[O]->V = v+vtl_;
`VA[1]->U = u+utl
`;
`
`VA[1]—>V = v+vtl_;
`VA[2]—>U = u+utl
`5
`VA[2]—>V = v+vtl
`;
`
`VA[3]—>U = u+utl_;
`VA[3]->V = v+vtl
`;
`#endif
`// Transform Vertices and calculate clipping flags
`for(i=O;i<4;i++,V++)
`{
`
`Vtx = VA[i];
`Vtx—>TPos.x
`
`g_VP.CX * V->z + g_VP.K * V->x;
`Vtx—>TPos.y
`g_VP.CY * V->2 - g_VP.K * V->y;
`Vtx—>TPos.z - V—>z;
`Vtx—>RZ
`H l.Of/Vtx—>TPos.z;
`Vtx—>PX
`Vtx—>TPos.x * Vtx->RZ;
`Vtx—>PY
`Vtx—>UZ
`Vtx—>VZ
`
`Vtx—>TPos.y * Vtx—>RZ;
`Vtx->U*Vtx->RZ;
`Vtx—>V*Vtx->RZ;
`
`VertexFlags(Vtx);
`
`31fl10
`
`31
`
`31
`
`
`
`// Set up texturing parameters
`Q—>Tex = PMT—>Texture->Tex;
`Q—>drawlev = drawlevel;
`II
`Q->avai1lev
`PMT~>Level;//Q->MT—>Level;//Parent-
`>Level;
`
`// Update data integrity
`g_TM.DataIntegrityNorm += pow2fast(-2*(MT->Level + Q-
`>drawlev));
`
`g_TM.DataIntegrity += pow2fast(—2*(MT—>Level + Q-
`>drawlev—Q—>availlev ));
`
`g_TM.DataIntegrityMax += pow2fast(-2*MT—>Level);
`
`// Rasterize Q on Expansion map
`long qlvl = Q->MT—>Leve1;
`+ 2;
`long qscanline = (1 << (g_TM.MaxLevel—1))
`long qlength = 1 << ((g_TM.MaxLevel—1)
`— qlvl);
`long qposx = qlength * Q->MT—>TX + 1;
`long qposy = qlength * Q->MT—>TY + 1;
`byte * qptr = g_TM.ExpansionMap + qposx + qposy *
`qscanline;
`for(j=0;j<qlength;j++,qptr += qscanline)
`memset(qptr, qlvl, qlength);
`
`} /
`
`/ Renders all of the generated Quadritherals.
`void SpliceVertex(Vertex *A,Vertex *B,float t,Vertex *V)
`{
`
`float s=l.0f—t;
`V->TPos.x = A->TPos.x * s + B—>TPos.x * t;
`
`V—>TPos.y
`V—>TPos.z
`
`ll
`
`A—>TPos.y * s + B~>TPos.y * t;
`A->TPos.z * s + B->TPos.z * t;
`
`V->U
`V->V
`
`A->U *
`A->V
`*
`
`1.0f/V~>TPos.z;
`V—>RZ
`V->PX = V->TPos.x * V—>RZ;
`
`V->PY = V->TPos.y * V—>RZ;
`
`V->UZ = V->U * V—>RZ;
`V—>VZ = V—>V * V—>RZ;
`
`32/110
`
`32
`
`32
`
`
`
`// kickass
`I B—>Flags)
`if (A—>Flags
`VertexFlags(V);
`
`else
`
`V->F1ags = 0;
`
`void RenderQuads()
`
`Quad *Q.*QE;
`MapTile *MT;
`
`if (!NumQuads) return;
`
`long i,j;
`
`dufactor= Quads—>availlev;
`
`static Vertex SVBuffer[48];
`static Vertex *VA[3];
`
`Texture Tx;
`
`Tx._l2xRes = 6;
`Tx._l2yRes = 6;
`Tx._stateFlags = 0;
`Tx._PF = PF_R5G6B5;
`#ifndef _FLY_OVER_WIN_CE
`// Set to Eyal's Texture mapper.
`RR_SetTextureMapper(TMapper_Interface);
`Tx._stateFlags |= TSF_BLOCKTILED;
`
`#else
`
`// Set to Refraster with std.
`
`inner
`
`RR_SetTextureMapper(TMapper_Standard);
`RR_SetTextureInner(TInner_Standard);