UNITED STATES PATENT AND TRADEMARK OFFICE
`
`
`
`
`
`
`
`
`
`
`
`BEFORE THE PATENT TRIAL AND APPEAL BOARD
`
`
`
`
`
`
`
`
`
`
`
`DECLARATION OF DR. PETER LINDSTROM
`REGARDING 1997 ARTICLE ENTITLED “AN INTEGRATED GLOBAL
`GIS AND VISUAL SIMULATION SYSTEM”
`
`
`
`Microsoft Corp. Exhibit 1012
`
`

`
`DECLARATION OF DR. PETER LINDSTROM
`REGARDING 1997 ARTICLE ENTITLED “AN INTEGRATED GLOBAL GIS AND VISUAL SIMULATION
`SYSTEM”
`
`
`I, Peter Lindstrom, make the following declaration based on my personal
`
`knowledge:
`
`1. My name is Peter G. Lindstrom. I am a computer scientist and project
`
`leader in the Center for Applied Scientific Computing at Lawrence Livermore
`
`5
`
`National Laboratory, Livermore, California. I studied and conducted research in a
`
`doctoral program at Georgia Institute of Technology (“Georgia Tech”) from 1994
`
`to 2000 and earned my Ph.D. in Computer Science from Georgia Tech in 2000.
`
`2.
`
`As part of my study and research at the Graphics, Visualization, and
`
`Usability Center (GVU) at Georgia Tech, I worked on a project related to a visual
`
`10
`
`simulation system called Virtual Geographic Information System (“VGIS”)
`
`between 1994 and 1997.
`
`3.
`
`During this project, I conducted research on various technical issues
`
`in an integrated visual simulation system supporting visualization of global
`
`multiresolution terrain elevation and imagery data, static and dynamic 3D objects
`
`15
`
`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. My research covered the requirements of real-time rendering,
`
`very large datasets, and heterogeneous detail management and their strong impact
`
`to the structure of the system. I was the lead author of a research paper relating to
`
`20
`
`VGIS titled “An Integrated Global GIS and Visual Simulation System,” along with
`
`1
`
`Microsoft Corp. Exhibit 1012
`
`

`
`DECLARATION OF DR. PETER LINDSTROM
`REGARDING 1997 ARTICLE ENTITLED “AN INTEGRATED GLOBAL GIS AND VISUAL SIMULATION
`SYSTEM”
`
`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.
`
`4.
`
`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 in 1997 because I was
`
`responsible for finalizing the paper for online publication. The Lindstrom
`
`Publication was published online as a GVU Technical Report in 1997 and was
`
`10
`
`available to the public for free through the Georgia Tech website and File Transfer
`
`Protocol (FTP) site. The Lindstrom publication could be 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 Lindstrom publication through an
`
`Internet or web search engine. I checked the GVU FTP site at least once in 1997
`
`15
`
`after the Lindstrom Publication was published and observed that the Lindstrom
`
`Publication was, in fact, available for download in a location accessible to the
`
`public.
`
`5.
`
`Attached to this declaration as Exhibit A is a true and correct copy of
`
`the Lindstrom Publication that was published and made publicly accessible in
`
`
`
`2
`
`Microsoft Corp. Exhibit 1012
`
`

`
`DECLARATION OF DR. PETER LINDSTROM
`REGARDING 1997 ARTICLE ENTITLED “AN INTEGRATED GLOBAL GIS AND VISUAL SIMULATION
`SYSTEM”
`
`1997. I recognize Exhibit A as a true and correct copy of the Lindstrom
`
`Publication from my own recollection.
`
`6.
`
`At the time the Lindstrom Publication was published, it was made
`
`available to the public at the GVU FTP site located at ftp://ftp.gvu.gatech.edu.
`
`5
`
`Subsequent to the publication of the Lindstrom Publication, the ftp site was
`
`changed to a different address at ftp://ftp.cc.gatech.edu. While the address has
`
`changed, the current address still directs users to the same Georgia Tech FTP
`
`directory to which the Lindstrom Publication was uploaded in 1997. The
`
`Lindstrom Publication is currently available
`
`10
`
`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. I have
`
`examined these online copies of the Lindstrom Publication and they are the same
`
`documents which I recall being published in 1997, and are identical to Exhibit A
`
`15
`
`with the addition of color in the color plates.
`
`7.
`
`I worked with two people at Georgia Tech on the logistics for the
`
`publication of the Lindstrom Publication at online GVU Technical Reports. I
`
`originally sent the manuscript of the Lindstrom Publication to Ms. Elaine Swobe,
`
`who was the GVU Center’s technical report coordinator. Mr. Randy Carpenter,
`
`20
`
`who was a research scientist at GVU and the manager of the GVU lab in 1997, also
`
`
`
`3
`
`Microsoft Corp. Exhibit 1012
`
`

`
`DECLARATION OF DR. PETER LINDSTROM
`REGARDING 1997 ARTICLE ENTITLED “AN INTEGRATED GLOBAL GIS AND VISUAL SIMULATION
`SYSTEM”
`
`communicated and worked with me in publishing the Lindstrom Publication. Mr.
`
`Carpenter oversaw the publication of certain reports originating out of the GVU
`
`lab and was the person who ultimately posted the Lindstrom Publication online.
`
`8.
`
`Attached to this declaration are two email communications, which I
`
`5
`
`recognize as emails that I received in 1997 relating to 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.
`
`9.
`
`The first email, dated April 3, 1997, is attached to this declaration as
`
`10
`
`Exhibit B. This email is a message from Ms. Swobe to me, copying Mr.
`
`Carpenter, indicating that the Lindstrom Publication had been assigned a Tech
`
`Report number, meaning that it had been selected for online publication.
`
`10. The second email, dated May 13, 1997, is attached as Exhibit C. This
`
`email is a message from Mrs. Swobe to the GVU Advisory Board, faculty, and
`
`15
`
`graduate students (including me) 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 graduate student email list,
`
`gvu-grad@cc.gatech.edu, which appears on the carbon copy (CC) line of Exhibit
`
`C.
`
`
`
`4
`
`Microsoft Corp. Exhibit 1012
`
`

`
`DECLARATION OF DR. PETER LINDSTROM
`REGARDING 1997 ARTICLE ENTITLED “AN INTEGRATED GLOBAL GIS AND VISUAL SIMULATION
`SYSTEM”
`
`
`11. Therefore, Exhibit A to this declaration is a true and correct copy of a
`
`journal article that was publicly available electronically in 1997. I personally
`
`drafted the manuscript of, and worked on the publication of, the Lindstrom
`
`Publication for online publication on the Georgia Tech website as a GVU
`
`5
`
`Technical Report in 1997.
`
`12.
`
`I hereby declare that all statements made herein of my own
`
`knowledge are true and that all statements made on information and belief are
`
`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
`
`10
`
`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.
`
`I declare under penalty of perjury that the foregoing is true and correct.
`Executed on this 9th day of June, 2015 in Livermore, California.
`
`15
`
`/Peter Lindstrom/
`Peter Lindstrom, Ph.D.
`
`
`
`
`
`
`
`
`
`5
`
`Microsoft Corp. Exhibit 1012
`
`

`
`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 1012
`
`

`
`(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 1012
`
`

`
`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 1012
`
`

`
`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 specialized modules
`is maintained which can be supplemented to handle near arbitrary
`data types, both by the pre-processor and the run-time system. The
`dataset building process is entirely automated, making it very easy
`to insert and remove data. This is important for facilitating real-
`time acquisition and integration of data such as up-to-date satellite
`imagery.
`
`4.2 Run-Time System
`
`The run-time part of VGIS has been designed to support highly in-
`teractive frame rates. As such, it relies heavily on a multithreaded,
`fine-grained task distribution. Since the display update rate is of-
`ten of higher importance than the scene update rate, including level
`of detail selection and animation, more resources are allocated to-
`wards satisfying a minimum frame rate. In [20], we propose a ter-
`rain geometry level of detail algorithm that generates “continuous”
`levels of detail on-the-fly. While being highly efficient in select-
`ing the vertices and triangles that make up the terrain surface for
`a given view, the recursive traversal of the terrain data structures
`for triangle stripping is a bottleneck that limits the rendering rate to
`approximately 10 frames per second for pixel-accurate full-screen
`views. As a lot of frame-to-frame coherence is evident in the re-
`sulting triangle strips, it is often satisfactory to perform the LOD
`management less frequently, say 1–5 times per second, and trade
`the scene update rate for higher display rates. We accomplish this
`by decoupling the two tasks and separate them into two different,
`asynchronous threads. This scheme allows the scene to be redis-
`played (with potential changes to the view between frames) un-
`til new parts of the scene have been generated and submitted by
`a scene manager. In addition, we further segregate different data
`types, recognizing that different data products may re