throbber
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

This document is available on Docket Alarm but you must sign up to view it.


Or .

Accessing this document will incur an additional charge of $.

After purchase, you can access this document again without charge.

Accept $ Charge
throbber

Still Working On It

This document is taking longer than usual to download. This can happen if we need to contact the court directly to obtain the document and their servers are running slowly.

Give it another minute or two to complete, and then try the refresh button.

throbber

A few More Minutes ... Still Working

It can take up to 5 minutes for us to download a document if the court servers are running slowly.

Thank you for your continued patience.

This document could not be displayed.

We could not find this document within its docket. Please go back to the docket page and check the link. If that does not work, go back to the docket and refresh it to pull the newest information.

Your account does not support viewing this document.

You need a Paid Account to view this document. Click here to change your account type.

Your account does not support viewing this document.

Set your membership status to view this document.

With a Docket Alarm membership, you'll get a whole lot more, including:

  • Up-to-date information for this case.
  • Email alerts whenever there is an update.
  • Full text search for other cases.
  • Get email alerts whenever a new case matches your search.

Become a Member

One Moment Please

The filing “” is large (MB) and is being downloaded.

Please refresh this page in a few minutes to see if the filing has been downloaded. The filing will also be emailed to you when the download completes.

Your document is on its way!

If you do not receive the document in five minutes, contact support at support@docketalarm.com.

Sealed Document

We are unable to display this document, it may be under a court ordered seal.

If you have proper credentials to access the file, you may proceed directly to the court's system using your government issued username and password.


Access Government Site

We are redirecting you
to a mobile optimized page.





Document Unreadable or Corrupt

Refresh this Document
Go to the Docket

We are unable to display this document.

Refresh this Document
Go to the Docket