UNITED STATES PATENT AND TRADEMARK OFFICE
`
`
`
`
`
`
`
`
`
`
`
`BEFORE THE PATENT TRIAL AND APPEAL BOARD
`
`
`
`
`
`
`
`
`
`
`
`DECLARATION OF CHARLES RANDALL CARPENTER
`REGARDING 1997 ARTICLE ENTITLED “AN INTEGRATED GLOBAL
`GIS AND VISUAL SIMULATION SYSTEM”
`
`
`
`
`Microsoft Corp. Exhibit 1013
`
`

`
`DECLARATION OF CHARLES RANDALL CARPENTER
`REGARDING 1997 ARTICLE ENTITLED “AN INTEGRATED GLOBAL GIS AND VISUAL SIMULATION
`SYSTEM”
`
`
`I, Charles Randall (“Randy”) Carpenter, make the following declaration
`
`under penalty of perjury:
`
`1. My name is Charles Randall Carpenter. I am a retired research
`
`faculty member from the Georgia Institute of Technology (“Georgia Tech”)
`
`5
`
`College of Computing.
`
`2.
`
`I have a B.S. in Mathematics and an M.S. in Computer Science from
`
`Georgia State University.
`
`3.
`
`I worked at Georgia Tech from 1998 to 2014 and held various
`
`positions. Between 1994 and 1998, I was a research scientist in Georgia Tech’s
`
`10
`
`Graphics, Visualization, and Usability (GVU) Center, where I was the Manager of
`
`the GVU Lab. As part of my duties as the Manager of the GVU Lab, I oversaw
`
`publication of certain publications originating out of the GVU Lab. Some papers
`
`based on research originating out of the GVU Lab were published online as GVU
`
`Technical Reports, which would be made accessible to the public via File Transfer
`
`15
`
`Protocol and could be located and accessed from the Georgia Tech library website.
`
`4.
`
`In the mid-1990s, a group of researchers including Dr. Peter
`
`Lindstrom worked on a project related to a visual simulation system called Virtual
`
`Geographic Information System, or VGIS.
`
`5.
`
`The VGIS system was partially described in a research paper titled
`
`20
`
`“An Integrated Global GIS and Visual Simulation System,” written by Peter
`
`1
`
`Microsoft Corp. Exhibit 1013
`
`

`
`DECLARATION OF CHARLES RANDALL CARPENTER
`REGARDING 1997 ARTICLE ENTITLED “AN INTEGRATED GLOBAL GIS AND VISUAL SIMULATION
`SYSTEM”
`
`Lindstrom, David Koller, William Ribarsky, Larry F. Hodges, Augusto Op den
`
`Bosch, and Nick Faust. I will refer to this publication simply as “the Lindstrom
`
`Publication” for purposes of this declaration.
`
`6.
`
`The Lindstrom Publication was published online on the Georgia Tech
`
`5
`
`website as a GVU Technical Report in 1997. I specifically recall the publication of
`
`the Lindstrom Publication online in 1997 and I am confident based on my own
`
`recollection that the Lindstrom Publication was published that year because I
`
`worked with Dr. Lindstrom in handling the publication of the Lindstrom
`
`Publication.
`
`10
`
`7.
`
`The Lindstrom Publication was published online as a GVU Technical
`
`Report in 1997 and was available to the public for free through the Georgia Tech
`
`website and File Transfer Protocol (FTP) site. The Lindstrom Publication could
`
`have been located by the general public through a search of the online Georgia
`
`Tech catalog. The general public could also locate and obtain a copy of the
`
`15
`
`Lindstrom publication through a regular Internet search engine. I checked the
`
`GVU FTP site in 1997 after the Lindstrom Publication was published online and
`
`observed that the Lindstrom Publication was, in fact, available for download in a
`
`location accessible to the public.
`
`8.
`
`I was responsible for handling the online publication of the Lindstrom
`
`20
`
`Publication via the GVU website and FTP site in 1997. I received a copy of the
`
`
`
`2
`
`Microsoft Corp. Exhibit 1013
`
`

`
`DECLARATION OF CHARLES RANDALL CARPENTER
`REGARDING 1997 ARTICLE ENTITLED “AN INTEGRATED GLOBAL GIS AND VISUAL SIMULATION
`SYSTEM”
`
`Lindstrom Publication in approximately April 1997 from Elaine Swobe, the GVU
`
`Center’s technical report coordinator. Under our normal procedures, Ms. Swobe
`
`would accept submissions for publications and then send them for me to post on
`
`the GVU web site.
`
`5
`
`9.
`
`At the time the Lindstrom Publication was published in 1997, it was
`
`made available to the public at the GVU FTP site located at
`
`ftp://ftp.gvu.gatech.edu. Subsequent to the online publication of the Lindstrom
`
`Publication, the ftp site was changed to a different address at
`
`ftp://ftp.cc.gatech.edu. While the address changed, the current address still directs
`
`10
`
`users to the same Georgia Tech FTP directory to which I uploaded the Lindstrom
`
`Publication in 1997. The Lindstrom Publication is currently available at
`
`ftp://ftp.cc.gatech.edu//pub/groups/gvu/tr/1997/97-07.pdf, while the color plates
`
`that were published as part of this figure are available at
`
`ftp://ftp.cc.gatech.edu//pub/groups/gvu/tr/1997/97-07.figures.pdf.
`
`15
`
`10. Attached to this declaration as Exhibit A is a true and correct copy of
`
`the Lindstrom Publication that was made publicly accessible in 1997. I recognize
`
`Exhibit A as a true and correct copy of the Lindstrom Publication from my own
`
`recollection and because I retrieved this document from the publicly available
`
`GVU server. The document on the GVU server contains a time stamp showing the
`
`20
`
`dates when the Lindstrom Publication was uploaded to the GVU server.
`
`
`
`3
`
`Microsoft Corp. Exhibit 1013
`
`

`
`DECLARATION OF CHARLES RANDALL CARPENTER
`REGARDING 1997 ARTICLE ENTITLED “AN INTEGRATED GLOBAL GIS AND VISUAL SIMULATION
`SYSTEM”
`
`
`11. At the request of Microsoft’s counsel, I took a screen shot on my
`
`computer of the relevant portions of the directory of 1997 GVU Technical Reports
`
`showing the time stamps when the Lindstrom Publication and its associated figures
`
`were uploaded to the GVU server. A copy of that screen shot is attached below:
`
`5
`
`
`
`12. The above screen shot shows that the Lindstrom Publication and
`
`accompanying figures were uploaded to the directory as PostScript files on May 8,
`
`
`
`4
`
`Microsoft Corp. Exhibit 1013
`
`

`
`DECLARATION OF CHARLES RANDALL CARPENTER
`REGARDING 1997 ARTICLE ENTITLED “AN INTEGRATED GLOBAL GIS AND VISUAL SIMULATION
`SYSTEM”
`
`1997 (97-07.ps.Z and 97-07.figures.ps.Z) and as Adobe .pdf files on February 13,
`
`1998 (97-07.pdf and 97-07.figures.pdf).
`
`13.
`
`I have also located a reference from the Internet Archive showing that
`
`the Lindstrom Publication was publicly available at least as of June of 1998. To
`
`5
`
`the best of my knowledge, the Internet Archive or “Wayback Machine” is a
`
`website located at www.archive.org that uses automated programs to search web
`
`pages and store archived copies of those web pages at specific points in time.
`
`Attached as Exhibit D to this declaration is a printout of an Internet Archive
`
`capture of the GVU Technical Reports website
`
`10
`
`(http://www.gvu.gatech.edu/gvu/reports/1997/) as of June 28, 1998, also available
`
`online at
`
`https://web.archive.org/web/19980628211631/http://www.gvu.gatech.edu/gvu/repo
`
`rts/1997/.
`
`14.
`
`I designed the GVU Technical Reports website, and Exhibit D is
`
`15
`
`consistent with my recollection of how the website would have appeared to a
`
`member of the general public accessing the site as of 1998. Based on my own
`
`recollection of the GVU website, Exhibit D appears to be a true and accurate
`
`reproduction (other than the Internet Archive header) of how the GVU Technical
`
`Reports website would have appeared in mid-1998. Exhibit D shows that the
`
`
`
`5
`
`Microsoft Corp. Exhibit 1013
`
`

`
`DECLARATION OF CHARLES RANDALL CARPENTER
`REGARDING 1997 ARTICLE ENTITLED “AN INTEGRATED GLOBAL GIS AND VISUAL SIMULATION
`SYSTEM”
`
`Lindstrom Publication and its accompanying figures were available for download
`
`from the GVU Technical Reports website in mid-1998.
`
`15.
`
`I have also examined my email archive and located two email
`
`communications between myself and Ms. Swobe (whose email address at the time
`
`5
`
`was Elaine@cc.gatech.edu) regarding the publication of the Lindstrom Publication.
`
`These emails and the date stamp on the electronic publication are consistent with
`
`my recollection that the Lindstrom Publication was published in the spring of
`
`1997.
`
`16. The first email, dated April 3, 1997, is attached as Exhibit B. This
`
`10
`
`email is a message from Ms. Swobe to Mr. Lindstrom, copying me
`
`(randy@cc.gatech.edu), indicating that the Lindstrom Publication had been
`
`assigned a Tech Report number, meaning that it had been selected for online
`
`publication.
`
`17. The second email, dated May 13, 1997, is attached as Exhibit C. This
`
`15
`
`email is a message from Mrs. Swobe to the GVU Advisory Board, faculty, and
`
`graduate students announcing the release and public availability of GVU Technical
`
`reports in March and April of 1997, including the Lindstrom Publication. I
`
`received this email through the GVU faculty email list (gvu-fac@cc.gatech.edu),
`
`which is shown in the CC line.
`
`
`
`6
`
`Microsoft Corp. Exhibit 1013
`
`

`
`DECLARATION OF CHARLES RANDALL CARPENTER
`REGARDING 1997 ARTICLE ENTITLED “AN INTEGRATED GLOBAL GIS AND VISUAL SIMULATION
`SYSTEM”
`
`
`18. Therefore, I confirm that Exhibit A to this declaration is a true and
`
`correct copy of a journal article that was publicly available electronically in 1997.
`
`19.
`
`I hereby declare that all statements made herein of my own
`
`knowledge are true and that all statements made on information and belief are
`
`5
`
`believed to be true; and further that these statements were made with the
`
`knowledge that willful false statements and the like so made are punishable by fine
`
`or imprisonment, or both, under 18 U.S.C. 1001 and that such willful false
`
`statements may jeopardize the validity of the application or any patent issued
`
`thereon.
`
`10
`
`I declare under penalty of perjury that the foregoing is true and correct.
`Executed on this 11th day of June, 2015 in Atlanta, Georgia.
`
`/Charles Randall Carpenter/
`Charles Randall Carpenter
`
`
`
`
`
`
`
`7
`
`Microsoft Corp. Exhibit 1013
`
`

`
`An Integrated Global GIS and Visual Simulation System
`
`Peter Lindstrom David Koller William Ribarsky
`Larry F. Hodges
`Augusto Op den Bosch
`Nick Faust
`
`Graphics, Visualization, & Usability Center
`Georgia Institute of Technology
`
`Abstract
`
`This paper reports on an integrated visual simulation system sup-
`porting visualization of global multiresolution terrain elevation and
`imagery data, static and dynamic 3D objects with multiple levels of
`detail, non-protrusive features such as roads and rivers, distributed
`simulation and real-time sensor input, and an embedded geographic
`information system. The requirements of real-time rendering, very
`large datasets, and heterogeneous detail management strongly af-
`fect the structure of this system. Use of hierarchical spatial data
`structures and multiple coordinate systems allow for visualization
`and manipulation of huge terrain datasets spanning the entire sur-
`face of the Earth at resolutions well below one meter. The multi-
`threaded nature of the system supports multiple windows with in-
`dependent, stereoscopic views. The system is portable, built on
`OpenGL, POSIX threads, and X11/Motif windowed interface. It
`has been tested and evaluated in the field with a variety of ter-
`rain data, updates due to real-time sensor input, and display of net-
`worked DIS simulations.
`
`1 INTRODUCTION
`
`This paper reports on significant progress in our efforts to design
`and construct a real-time visual simulation and geographic informa-
`tion visualization system, named VGIS (Virtual Geographic Infor-
`mation System) [17, 30]. VGIS supports the accurate depiction of
`terrain elevation and imagery, in addition to features such as ground
`cover and trees, moving vehicles, buildings and other static objects,
`roads, and atmospheric effects. Thus an entire environment com-
`posed of heterogeneous parts must be simulated and integrated at
`rendering time. The system must be set up to efficiently manage this
`integration and, ultimately, to manage dynamically the complexity
`of each part with respect to the others in order to both conform to
`a strict time budget and to present the most telling details. Inte-
`gration of all this with a GIS database is important because many
`applications require access to geographically located information
`(e.g. building names, contents, and even floor plans). The GIS
`data can also be handled by the VGIS data managers and threaded
`through the real-time renderer for visualization in the 3D display
`environment.
`The visual simulation system described above implies very large,
`even huge amounts of data. Automatic paging and caching tech-
`niques handling heterogeneous data from the different parts of the
`system must be in place. If, for example, the system is to visualize
`urban scenes, it must manage hundreds to thousands of buildings,
`plus their textures, and also street layouts. For flexibility the terrain
`visualization sub-system should handle terrain from any part of the
`world and integrate these terrains into a common coordinate sys-
`tem without seams or gaps (e.g. between levels of detail or due to
`multiple coordinate systems). All this should be in a hierarchical
`organization structure so that the terrain detail can be continuously
`
`adapted based on user viewpoint and scene content. Yet the hierar-
`chy must be flexible so that detail can be added or deleted as needed.
`Such flexibility is quite important due to database size as the global
`datasets used with VGIS often require ten or more gigabytes.
`In this paper we describe a visual simulation system that pro-
`vides a structure supporting all the parts described above. We also
`discuss in detail our implementations for some of these parts, con-
`centrating especially on global terrain visualization. The structure
`is in a multithreaded form to facilitate balanced and separable man-
`agement of the system parts. It is also quite portable, due to stan-
`dard libraries such as Pthreads and OpenGL, and has been ported
`to multiple workstation environments, including SGI and Sun plat-
`forms. We are now working on a PC version using Windows NT.
`The system has wide applicability, having been used for battlefield
`visualizations, tactical planning, and complex urban visualizations.
`
`2 RELATED WORK
`
`VGIS takes advantage of advances in a number of areas to create
`an integrated global geographic information visualization system.
`A large body of previous work has addressed issues in modeling,
`representing, and manipulating spatial data for geographic infor-
`mation systems. Applying 3D visualization techniques to global
`and spatial data has recently enjoyed increasing attention [12, 22].
`VGIS manages its huge, complex terrain and GIS datasets in an
`efficient manner by using hierarchical spatial data structures. A
`number of such data structures have been adopted in GIS systems
`and other spatial databases. Samet [25] describes the quadtree, a
`fundamental data structure in the VGIS system. Representing spa-
`tial datasets that span the entire globe requires special data struc-
`tures which take into account the curvature of the Earth and al-
`low for efficient searching and rendering operations on the large
`amounts of data. Fekete [8] describes sphere quadtrees, a spa-
`tial data structure applicable to global representations of the Earth.
`Other researchers have proposed similar hierarchical spatial data
`structures which have been demonstrated to be useful for global
`geographic information systems [13].
`VGIS also relies on multiresolution techniques to allow truly in-
`teractive visualization with its geometrically complex terrains. A
`large number of researchers have developed multiresolution rep-
`resentations and rendering techniques for large, complex terrains
`and height fields using polygonal meshes, as VGIS does. These
`algorithms attempt to represent surfaces within a given number of
`vertices, or within a given geometric error metric, or in a manner
`that preserves application specific critical features of the surface.
`Uniform grid methods or irregular triangulations are employed to
`represent the surfaces, and techniques including hierarchical subdi-
`visions and decimations of the mesh are used for simplification and
`creation of multiresolution representations.
`Much of the previous work on polygonalization of terrain-
`like surfaces has concentrated on triangulated irregular networks
`
`EXHIBIT A
`
`Microsoft Corp. Exhibit 1013
`
`

`
`(TINs). A number of different approaches have been developed to
`create TINs from height fields using Delaunay and other triangu-
`lations [10, 11, 27], and hierarchical triangulation representations
`have been proposed that lend themselves to usage in multiresolution
`level of detail algorithms [4, 5, 26]. Regular grid surface polygonal-
`izations have also been implemented as terrain and general surface
`approximations [3]. Such a gridded terrain surface representation is
`used in VGIS and is described in [20]. Other surface approximation
`representations include techniques such as wavelet transforms [14]
`and methods that meet application specific criteria, such as preserv-
`ing important terrain features [6, 10, 28].
`VGIS uses an approach which treats the terrain as a single con-
`nected surface for rendering, using “continuous” level of detail rep-
`resentations for the terrain geometry. Similar methods for such
`“continuous” or “view-dependent” level of detail rendering for ter-
`rains and other surfaces are described in [3, 9, 20, 31, 32].
`A number of visualization systems have been implemented
`which integrate 3D visualization techniques with large spatial geo-
`graphic information and terrain data. Some systems stress accurate
`rendering of global images, or accurate modeling of environmen-
`tal processes, often sacrificing interactivity of the system [21, 24].
`Other systems emphasize tight integration of the 3D visualization
`with the powerful spatial analysis capabilities of GIS [7].
`Systems such as VGIS place a high priority on real-time, highly
`interactive 3D visualizations of the spatial data. Maintaining truly
`real-time update rates in the face of large, complex datasets re-
`quires special techniques and time-critical visualization system de-
`signs. Bryson and Johan [1] discuss some issues particular to such
`time-critical computations in visualization environments. Software
`toolkits such as IRIS Performer [23] provide an architectural frame-
`work similar to that of VGIS which provides support for efficient
`rendering and simulation operations on high-end computer graphics
`workstations.
`Interactive 3D visualization systems for visual simulation and
`training address many of the same technical problems as VGIS, in-
`cluding real-time rendering of large terrain databases. Flight sim-
`ulator systems first implemented sophisticated image generation
`techniques to allow efficient rendering and visualization of complex
`spatial databases [33]. Recent developments have made interac-
`tive 3D graphics rendering of such databases possible using off-the-
`shelf graphics workstations. NASA's Virtual Planetary Exploration
`project [16] supported virtual exploration of planetary terrains such
`as Mars at interactive frame rates. SRI's TerraVision system also
`allows interactive viewing of 3D landscapes, using similar terrain
`level of detail and paging techniques as VGIS to allow very large,
`high-resolution geo-specific terrain datasets to be visualized. The
`T Vision research project [15] provides a distributed virtual globe
`as a multimedia interface for visualizing geographic data. Other
`3D terrain visualization systems use parallel architectures to render
`complex datasets while maintaining interactive performance for vi-
`sual simulation and planetary visualization applications [2, 19].
`
`3 SYSTEM DESIGN AND
`REQUIREMENTS
`
`The rationale behind many of the design decisions made in the de-
`velopment of VGIS was driven by both hardware constraints and
`user requirements. Typical hardware constraints include available
`main memory, available texture memory, available precision in geo-
`metric calculations, rendering speed, disk transfer speed, etc., while
`the user requirements include interactivity, off-line processing time,
`display accuracy, data registration, as well as flexibility, extensibil-
`ity, and portability from both the end user's and developer's per-
`spectives.
`Due to the large datasets that VGIS typically works with, most
`
`of the data must be put in secondary storage, and a paging scheme
`is used to bring in and cache the appropriate data for display. Level
`of detail techniques are applied to both geometry and imagery to
`further limit the amount of data stored in main memory and tex-
`ture memory. These techniques are based on image quality metrics
`whose parameters can be manipulated interactively by the user to
`obtain a desirable balance between rendering speed and scene fi-
`delity.
`The user is given the ability to visualize the scene through multi-
`ple views which map onto separate windows. Each such view may
`display the scene from a different viewpoint, e.g. as a 3D immer-
`sive view or a 2D overview map, or may display different aspects
`of the same scene, e.g. as phototextured terrain or as a contour map
`with surface features such as roads and rivers turned on. In order
`to conserve memory, view-independent data is shared among the
`views and is accessed from a single primary cache.
`To further obtain a high degree of interactivity, the system is bro-
`ken down into a number of asynchronous threads that are prioritized
`according to their relevance to the final display update rate, which
`is one of the most important constraints in the system. For exam-
`ple, a dedicated render thread is used whose single task it is to up-
`date one or more views at the highest possible rate; level of detail
`(LOD) management is distributed over several threads according to
`the data they operate on, which generally update the scenes at a
`rate lower than the rendering rate; while a number of server threads
`execute only when data requests are made. This fine-grained subdi-
`vision of tasks ensures a high degree of CPU utilization and elim-
`inates the bottlenecks often associated with blocking system calls
`(e.g. disk I/O, input device polling) in the real-time components of
`the system.
`To accommodate data paging, level of detail management, and
`view culling, a quadtree data structure [25] is used to spatially sub-
`divide and organize the terrain raster data. The globe is subdivided
`into a small number of pre-determined areas, each corresponding to
`a separate quadtree. The tiles associated with the quadtree nodes,
`or quadnodes, are stored in a file format that closely matches the
`internal representation, which allows for good paging performance.
`Rather than using a single global coordinate system, a large num-
`ber of local coordinate systems is used. This is necessary as the
`precision afforded by current graphics hardware is insufficient for
`representing detailed geometry distributed over a large volume in a
`single coordinate system. Different branches within the quadtrees
`are assigned to different local coordinate systems, which are cen-
`tered such that precision is maximized, and oriented to locally pre-
`serve natural directions such as “up”, which can be exploited by the
`terrain geometry level of detail algorithm.
`VGIS has been designed to be portable across a spectrum of dif-
`ferent platforms, but is primarily targeted towards high end graph-
`ics architectures such as Silicon Graphics workstations. Certain
`platform specific extensions are optionally incorporated at compile
`time to maximize the system performance. The system is layered on
`top of portable standardized libraries such as OpenGL and POSIX
`threads, and provides a level of indirection for interfacing with the
`windowing subsystem, e.g. X11/Motif for Unix platforms.
`
`4 SYSTEM OVERVIEW
`
`The VGIS system consists of a dataset pre-processing component,
`as well as the actual run-time visualization display system. Option-
`ally, external processes may provide real-time or remote data input.
`Due to the vast volumes of data that make up the global terrain
`database, the data is prepared off-line and structured in a form that
`closely matches the internal representation so that it can be paged
`into main memory efficiently. This form of pre-processing includes
`data format conversion, reprojection, resampling, data analysis, and
`data synthesis.
`In order to maximize the run-time performance,
`
`2
`
`EXHIBIT A
`
`Microsoft Corp. Exhibit 1013
`
`

`
`non-interactive processes such as simulation, real-time data acquisi-
`tion, and remote queries can be separated from the run-time system
`and be executed as remote processes. A number of server threads
`run in the back end of the run-time system that communicate with
`the external processes and fetch data from local disk. In addition,
`these threads perform intermediate tasks such as data transforma-
`tions (e.g. conversion of height field data to Cartesian coordinates),
`data synthesis and initialization (e.g. generation of LOD param-
`eters, synthesis of different image types), and repackaging of the
`data into the internal representation whenever necessary (e.g. pars-
`ing of DIS packets and GIS queries). Such processing is sometimes
`necessary to limit the amount of data stored on disk, and also allows
`VGIS to interface with external modules such as ARC/INFO GIS
`servers and ModSAF DIS simulators.
`The servers are broken down by data type (e.g. terrain, symbol-
`ogy, GIS) and are run as independent threads. Each server handles
`requests from a number of clients that manage the corresponding
`data type. As mentioned in the previous section, VGIS supports
`the concept of multiple, independent views, each corresponding to
`a window on the screen. For example, one view could display the
`user riding a moving vehicle in three dimensions, another may be
`a “God's eye view” looking down upon the vehicle, while a third
`view could be a 2D overview map of a larger area. For each view,
`there is a view module that contains data managers for each data
`type. For example, there is a terrain manager that makes data re-
`quests to the terrain server and handles level of detail management,
`surface queries, terrain rendering, etc. Similarly, there is an ob-
`ject manager that manages animation and display of 3D symbology
`and protrusive features. The actual on-screen rendering is done by
`a single dedicated render thread. This thread runs asynchronously
`from all other threads to provide maximum rendering performance
`and interactivity. Within each view module, the scenes that are to
`be rendered are prepared and buffered in data structures similar to
`OpenGL display lists. These display lists are then sent to the ren-
`der thread for display. The display lists are typically updated less
`frequently than the scenes are rendered, thus allowing the renderer
`to reuse a display list over several frames.
`To minimize the response time, the renderer fetches copies of
`the most recent view parameters (i.e. position, orientation, field of
`view, etc.) for each view at the beginning of each frame. The view
`parameters are updated by a single user interface (UI) thread, which
`also acts as an overall manager of the system. Whenever a UI event
`is generated, e.g. from an input device or from remote commands,
`the corresponding view parameters are updated for that view.
`An overview of the VGIS architecture is given by Figure 1. The
`following sections describe each of the system components in more
`detail.
`
`4.1 Pre-Processing
`
`Data processing in the VGIS system comes in three forms: off-line
`pre-processing, which is done once per dataset; intermediate, on-
`line processing, which is performed during the data paging stage;
`and real-time, on-line processing, which is typically done once per
`frame. The purpose of the pre-processor, or dataset builder, is to
`gather the different types of data and transform them into a format
`that is readable by and quickly accessible to the run-time system.
`These tasks are inherently compute intensive and cannot be per-
`formed by the run-time system at high enough rates. Additionally,
`the pre-processing only has to be done once for a given dataset, so
`it makes sense to pay the penalty of assembling a dataset up front.
`While the pre-processor may handle a large variety of different
`data types, we will limit this discussion to the processing of static
`terrain data. Some of the basic data types within this domain in-
`clude terrain geometry (e.g. “raw” elevation, elevation corrected
`for non-protrusive surface features such as roads and rivers, as well
`
`Window #1
`
`Window #2
`
`Display Lists
`
`Display Lists
`
`Render
`Thread
`
`UI,
`Master
`
`Shared
`Cache
`
`View #2
`
`Terrain
`LOD
`
`Object
`LOD
`
`View #1
`
`Terrain
`LOD
`
`Object
`LOD
`
`Terrain Manager
`
`Object Manager
`
`Terrain Manager
`
`Object Manager
`
`Terrain
`Client
`
`Object
`Client
`
`Terrain
`Client
`
`Object
`Client
`
`Private
`Cache
`
`Private
`Cache
`
`Terrain
`Server
`
`GIS
`Server
`
`Object
`Server
`
`Disk
`Cache
`
`Real−
`Time
`
`Dataset
`Builder
`
`Remote
`Control
`
`Figure 1: Overview of the VGIS system architecture. This figure
`illustrates two independent views but can be generalized to an ar-
`bitrary number. Modules are represented by rounded boxes, pro-
`cesses and threads by circles, data structures by rectangular boxes,
`and data flow and communication by arrows.
`
`as the surface features themselves), imagery (e.g. phototexture,
`Arc Digitized Raster Graphics—or ADRG, pre-shaded relief maps,
`contour maps, etc.), and surface properties (e.g.
`surface rough-
`ness parameters, bounding volumes). The source data may come
`in a variety of file formats, which the pre-processor must translate
`to a single common format.
`In addition, for each data type, the
`source data may consist of multiple, variable resolution, possibly
`overlapping/nested datasets. The pre-processor has the ability to
`layer these and composite them into a single dataset if so desired.
`As mentioned above, VGIS utilizes a quadtree structure for orga-
`nizing multi-resolution terrain data in a hierarchical manner. Each
`node in a quadtree identifies a fixed, square area (in geodetic lat/lon
`coordinates) at a given discrete resolution. Additional constraints
`force the dimensions of the raster tiles associated with the nodes
`to be powers of two,1 and the post spacing is successively doubled
`on each consecutive level up the tree. To facilitate the use of this
`data structure, each terrain dataset must be resampled to one of the
`discrete pre-determined resolutions. To accommodate fast paging,
`the data is also resampled and generated for all the internal nodes
`of each quadtree, resulting in what is commonly referred to as a
`pyramid structure.
`The pre-processing of the data is done entirely in geodetic co-
`ordinates, assuming a pre-determined geodetic datum.2 This en-
`sures good registration between different source datasets and avoids
`the discontinuity problems often associated with flat-projected data.
`Both the height field and imagery are represented as regular grids.
`Hence, we do not require additional compute time to triangulate the
`height field—the different discrete levels of detail of the geometry
`are rather represented by the pyramidal regular grid structure, and
`further refinement is employed on-the-fly by the run-time system.
`See [20] for a detailed discussion of the height field level of de-
`tail algorithm. To further improve dataset registration, alpha chan-
`
`1The elevation height field nodes have raster dimensions 2n + 1 as their
`boundary rows and columns overlap.
`2In the current implementation, the WGS-84 datum is used.
`
`3
`
`EXHIBIT A
`
`Microsoft Corp. Exhibit 1013
`
`

`
`nels can be added to the source data (both imagery and elevation)
`to allow blending/smoothing across dataset boundaries as well as
`masking of the data, e.g. for irregularly (non-rectangular) shaped
`datasets or for regions where data is missing.
`The dataset builder has been designed to be very flexible and ex-
`tensible in terms of incorporating many different data types, and is
`structured in a modularized manner to allow for fine-grained par-
`allel execution. The different data types are declared by the user
`using a class hierarchy language. For each class, a number of meth-
`ods/modules are defined that are used for reading, writing, and pro-
`cessing the data, with bindings to implementations of the methods.
`Class inheritance can be exploited to avoid redundant methods and
`class members. The modules are then connected in a data flow
`network similar to the structure provided by visualization systems
`such as AVS and Data Explorer, that is the output of one module
`is piped to the input of another set of modules. A set of operators
`are provided for expressing which modules are allowed to run in
`parallel, and which parts must execute in series. The output data
`must be classified into a few number of meta-types, such as geome-
`try and imagery, that the run-time system understands how to man-
`age and display. A repository of generic and specia