ompuferGrid hICS
`
`64110—2435
`
`Hlml: HHIHHHIIIIIIIlrluluiiltlllrlhll'
`5'5 FILL. FDF-I. HDE‘. 6-1340
`
`.3“
`
`MD
`
`Page 1 of 13
`
`Unified Patents Exhibit 1010
`
`

`

`olEEE
`
`fl 6
`
`'1'.
`
`AN!) APl—‘titf‘n Nun's
`
`IEEE Computer Society
`10662 Los Vaqueros Circle, PO Box 3014
`Los Alamitos, CA 90720
`http:/‘fcomputermrg/cga
`
`Editor in Chief
`James J. Thomas
`Pacific Northwest National Laboratory
`902 Battelle Boulevard
`Richland, WA 99352
`Jint.Thornas@pnl.gov
`
`Submissions: Please submit seven copies of all articles to
`Aiken-tin WinSton, magazine assistant, lElZli. Computer society,
`10662 Los Vaqueros Circle. Los Alatuitos, Cit 90720. Submit
`proposals for special issues to Michael Rhodes,
`mrhodes@odsus.jnj.corn. All submissions are subject to editing
`for Style. clarity, and space considerations, mt author‘s guide is
`available from the Web, publications office, or by c-mail from
`awinston@contputor.org.
`
`Associate Editors in Chief
`Michael L. Rhodes
`Ortha Diagnostic Systems
`'l‘umer Whittcd
`Microsoft
`
`Editorial Board
`
`Frank W. Bliss
`John C. Dill
`Rae A. Earnshaw
`José L, EnCa rnactio
`Andrew Glassnet'
`Markus Gross
`Bertram Herzog
`Tosiyasu L. Kunii
`Carl Mscltover
`Gregory M. Nielson
`Michael J. Potel
`Theresa-Marie Rhyne
`Lawrence J. Rosenblum
`Maureen Stone
`
`EDS/CM Corp.
`Simon Fraser University
`University of Bradford
`'l‘cchnical University of IJat'mstadt
`Microsoft
`li'l'l l, Zurich
`University of Michigan
`llosci University
`Macbover Associates
`Arizona State University
`Wildcrest Associates
`Lockheed Martin
`Naval Research Laboratory
`StoncScttp Consulting
`
`Managing Editor Nancy l—lays
`Assistant Editor Robin Baldwin
`Editorial Assistant Kristine Kelly
`Magazine Assistant Alkcuia Winston
`Art Direction Joe Daigle
`
`Publisher Matt Loch
`Advertising Manager Patricia Garvey
`Advertising Supervisor Marian Anderson
`Advertising Coordinator Debbie Sims
`Member/Ciro. Promo Mgr. Georgann Carter
`
`Publications Board
`
`Benjamin Walt (Vice President).
`Go] Agha {MCC chair), Jon Butler {TOC chair).
`Ron Williams [IEEE Pubs Representative),
`Jake Aggarwal. Alberto del Bimbo, Mike Liu, thiwei Xu
`
`Magazine Opt-rations Committee
`
`Carl Chang (Chair). William Everett (vice chair],
`James H. Aylor, Jean Bacon, thshnw Chou, George Cybenko,
`William 1. Grottky, Steve McConnell, Daniel E. O‘l.eaty.
`Ken Sakarnura, Munindar P. Singh, James J. Thomas,
`Ycrvant Zorian
`
`Editorial: IEEE Computer Graphics and Applications serves both
`users and designers of graphics hardware, software, and systems.
`its readers work in industry, business, the arts, and universities.
`Articles are peer-reviewed; departments are reiereed. Unless
`otherwise stated, bylined articles and departments. as Well as
`descriptions of products and services, reflect the author's or firm's
`opinion: inclttsion in this publication does not necessarily
`constitute endorsement by the IEEE or the Computer Society,
`
`Copyright and reprint permission: Abstracting is permitted
`with credit to the source. Libraries are permitted to photocOpy
`beyond the limits of US copyright law for private use of patrons
`those articles that entry a code at the bottom of the first page,
`provided the per-copy fee indicated in the code is paid through the
`Cupyright Clearance Center. 29 Congress St., Salem, MA 01970.
`instructors are permitted to photocopy isolated articles for
`noncommercial classroom use without fee. For other copying,
`reprint, or rcpublication permission, write to Copyrights and
`Permissions Department, IEEE Publications Administration, 445
`Hoes Lane, PD. Box 1331, Piscataway, NJ 08055-1331. All rights
`reserved. Copyright C) 1999 by the Institute of Electrical and
`Electronics Engineers, Inc.
`
`Circulation: iEEE Computer Graphics aud/lpplican‘ons (lSSN 0272.
`1716] is published bimonthly by the IEEE Computer Society.
`Il-‘.i.-‘.I.-'.
`Headquarters: Three Park Ave, 17th Floor, New York, NY 10016-
`5997. IEEE Computer Society Headquarters: 1730 Massachusetts
`AWL. Washington, DC 20036-i903. llil'll-i Computer Society
`Publications Office: 10662 Los Vattucros Circle. PO Box 3014, Les
`Alumitos, CA 90720: {7714) 321-8380. Annual subscription: $34 in
`addition to any IEEE group or society dues. Members of other
`technical organizations: $90. Nonmember sleSL'ript'ion rates are
`available on request. Back issues: tnctnbets, 5'10; nonmembers. $20.
`This journal is also available in microfiche form and on the Web.
`
`Postmaster: Send address Changes and undelivered copies to
`iEEE Computer Graphict and Applications. “IEEE Computer Society,
`10662 Los Vaqueros Circle, PO Box 3014. Los Alantitos, CA 90720.
`Periodicals postage is paid at New York, NY, and at additional
`mailing offices. Canadian CST #125634188. Canada Post
`International Publications Mail Product [Canadian Disti‘il‘mliun]
`Sales Agreement #0487848. Printer] in USA.
`
`Moving?
`PLEASE. NOTIFY Mall to
`
`US 4 WEEKS
`lN ADVANCE
`
`IEEE Computer Society
`10662 Los Vaqueros Circle
`PO Box 3014
`Los Alamltos, CA 90720
`0 This notice oi address change will apply to all IEEE publications to
`whlch you subscribe.
`1' List your new address below,
`'
`if you have a question about your subscription, place your address
`label here and clip this form to your letter.
`ATTACH
`LABEL
`HERE
`
`StatelCountry
`
`Name (please print)
`
`New addres:
`
`City
`
`Page 2 of 13
`
`Unified Patents Exhibit 1010
`
`Page 2 of 13
`
`Unified Patents Exhibit 1010
`
`

`

`Cgln uferGra hitss
`
`AND APPLICATIONS
`
`Articles
`
`VRML
`1 7 Guest Editor’s Introduction:
`Virtual Reality Modeling Language
`Maureen Stone
`
`1 8 Tutorial: Building Virtual Worlds
`with VRML
`David R. Nadeau
`VRML makes it easy to create virtual worlds. This
`tutorial reviews VRML‘s syntax and features as well
`as its world construction and animation abilities.
`
`3
`
`March/April 1999
`Volume 19 Number 2
`Published by the IEEE Computer Society
`
`5 2 Developing the VRML 97
`International Standard
`George S. Carson, Richard F. Puk, and
`Riki: Carey
`VRML 97 arose from a cooperative effort between the
`standards and VRML communities. The methodology
`employed applies equallywell to development of
`future standards.
`
`5
`
`VRML Testing: Making VRML Worlds
`Look the Same Everywhere
`Mary Brady. Alden Dime, Len Gebase,
`Michael Kass, Carmelo Mommies-Rivera.
`andLynneRascal-ital
`NIST tools address problems posed by testing 3D
`graphics. This article explains the test development
`strategy and design issues in developing and deliver-
`ing these testing tools.
`
`TerraVision ll: Visualizing Massive
`Terrain Databases in VRML
`Martin Raddy, Wan Leclerc, Lee lverson,
`and NarBietter
`To disseminate 3D maps and spatial data over the
`Web, the authors designed massive terrain data sets
`accessible through either aVRML browser or the cus- 6 A Framework for Streaming Geometry
`tomized TerraVision 1] browser.
`in VRML
`André Gue'ziec, Gabriel 'i'aabr'n, Bill Horn,
`and Francis Lazarus
`The authors introduce a framework for streaming
`geometry in VRML that eliminates the need to
`perform complete downloads ofgeometric models
`before starting to display them.
`
`3 9 Large-Scale Mine Vlsuallzatlon
`Uslng VRML
`Keith Russ and Andrew Wetlierelt
`Traditionally, mine plans and sections in 2D stored
`3D information. This article shows that using VRML
`to model this information leads to new, interactive
`methods ofdata visualization.
`45 ”Bottom, Thou Art Translated":
`The Making of VRML Dream
`Stephen N. Matsaba and Bernie Reelil
`Bringing virtual theater to the Web requires 3i)
`graphics, efficient networking, and strong content.
`The authors discuss the VRML Dream Project, a real-
`time Internet performance.
`
`http://L‘Dmpurer-Org/Egflf
`
`Page 3 of 13
`
`79 Dynamics Modeling and Culling
`Stephen Circuitry. Jeffrey iclinawski, and
`David Forsyth
`The tools described permit including large numbers
`of complex dynamic models in a VRML world easily
`«__
`and efficiently while maintaining high frame rates.
`
`
`
`[SEN 0272-1716
`
`Unifie tress Exhibit 1010
`
`Page 3 of 13
`
`Unified Patents Exhibit 1010
`
`

`

`4 About the Cover
`
`Advancing 3]) through VRMI.
`rm the. Web
`
`6 Projects in VR
`Public Speaking in Virtual
`Reality: Facing :ln Audience
`nf'Avutnrs
`
`10 Applications
`VizSim chhnolugy Helps
`I‘ind Oil Famtcr
`
`88 Andrew Glassner's
`Notebook
`
`String Crossings
`
`96 New Products
`
`100 Advertiserf Product
`Index
`
`(.IOI‘Iiputtn' Sncit‘ly lnfornmliun, (73
`Change qucldruss form. 1).
`l
`
`
`
`
`
`Page 4 of 13
`
`Unified Patents Exhibit 1010
`
`
`
`Page 4 of 13
`
`Unified Patents Exhibit 1010
`
`

`

`VRML
`
`This material may be protected by Copyright law (Title 17 U.S. Code)
`
`i
`
`TerraVision ll:
`
`Visualizing Massive
`Terrain Databases
`
`in VRML
`
`
`
`Martin Roddy, Yvan Leclerc, Lee iverson,
`and Nat Bietter
`SRI International
`
`To disseminate 3D maps and
`
`spatial data over the Web,
`
`we designed massive terrain
`
`Researchers hav'e in-
`creasingly turned to
`Virtual Reality Modeling Language
`(VRML)
`to represent geographic
`information. In VRMl..'s early days,
`the result was a few toy examples
`that did not scale well, such as
`coarse, single-resolution elevation
`grids. Today, VRML is drawing more
`serious interest from researchers
`across the spectrum, including geo-
`graphers, cartographers, geologists.
`and computer scientists, as the side-
`bar “Related Worlt" describes. As
`Theresa-Marie Rhyne noted, geo-
`graphic information system (613] and scientific visual-
`isation tools have begun to expand into each other's
`
`data sets accessible through
`
`either a VRML browser or
`
`the customized TerraVision
`
`ll browser.
`
`clomains,' anti VRML offers cartographers and geogra-
`phers the potential to disseminate 3i) maps and spatial
`data over the World WideWeb. However, to date we have
`not seen useful large-scale VRML gcographictlaliibflses.
`We aim to enable visualization of near plintnrealistic
`3D models oft-errain that can be on the order ofhun—
`dreds of gigabytes. This might incl tide different types of
`terrain imagery For particular regions. as well as site
`models and auxiliary information for ground leatures.
`The following scenario indicates the capabilities ‘
`required. Say a user wants to find a particular building il
`in a particular city. 1' lerjotlrneyi'legilis With a 3D model
`|
`oi" the earth viewed From space. This model is texture-
`‘
`mapped with satellite imagery of 100 kilometers reso-
`i
`lurion—that is, each pixel in the texture map represents
`a region on the planet‘s surl’ace covering 100 land. To |
`find the city, the user first rotates the earth to view the i
`
`-
`
`l
`
`
`
`Related Work
`Currently, interesting and significant work
`addresses the problem of representing geographic
`data in VRML. In the earth sciences, Kate Moore
`described the work of the Virtual Field Course
`(VFC) project,‘ which is developing software tools
`to familiarize students with fieldwork locations and
`aid data collection and analysis. The VFC project
`uses VRML and java to provide interactive 2D and
`3D views of geo~reierenced data to enhance
`students‘ cognition oi the real environment.
`The US Naval Postgraduate School ls currently
`working on a prefect to develop a 3D model of the
`Monterey Bay National Marine Sanctuary. They
`aim to create a VRML representation of the
`sanctuary based on raw bathymetry (below sea
`level) data for a 2.5 x 2.5 degree region of the bay.
`Their representation uses multiresolution
`techniques to deliver these large data amounts
`over a 28K modem connection.
`
`Michael Abernathy and Sam Shaw described
`their work using VRML to visualize the course fora
`197-mile relay race through the San Francisco Bay
`Area.2 They did this using standard US Geological
`Survey (USGS) 7.5 are min digital elevation
`models (DEMs) for the terrain geometry with geo-
`referenced satellite imagery draped over the
`terrain. Their system also used Global Positioning
`System (GPS) input to create a line segment
`showing the raee's course Over the VRML terrain.
`
`
`References
`1. K. Moore, "Interactive Virtual EnVlronments for field
`work," British Cartographic Society Annual Syrup, 1 997:
`available at http:/Mkugeog.le.ac.ult/mek/VirtEnv.htru.
`2. M. Abernathy and 5. Shaw, ”Integrating Geographic
`Information in VRivlL Models," Proc. Third Symp.
`VRML, ACM New York, 1998, pp. 107-114.
`
`11
`Ill
`
`lli‘
`iii
`,J1
`l’l'
`{'31'
`
`t!
`1i
`h
`.
`J“
`fa
`0‘
`
`3!)
`
`Page 5 of 13
`March/April 1999
`
`Unified Patents Exhibit 1010
`92??!- 'I IflLiNGIEIClDD 3) WHO IEEE
`
`
`
`Page 5 of 13
`
`Unified Patents Exhibit 1010
`
`

`

`target region in more detail. As she zooms into the
`region, higher resolution data, such as elevat ion and
`unagery, are progressively downloaded and displayed
`until she is "flying” ovcrntottntains with imagery clown
`to one~meter resoltttion. Over certain parts of the ter-
`rain. alternative imageries are available, suclt as aerial
`photographs; the user can select atty intage to view on
`top of the terrain geometry. As she approaches a built-
`up area, 3D models of buildings come into view. When
`the user clicks on a bit ilding, information abottt ii is dis—
`played In a separate frame on the browser. Using tltis
`method. the user locates the target building. Through.-
`ottt the navigation, the user’s location is displayed via
`an act ive map interface that provides a context for the
`landscape being viewed.
`In setting ottt to achieve such capabilities, we identi-
`fied four principal design criteria:
`
`I iirriirtitiiity. Our design mttst scale to very large data
`sets. Commonly, a geographic data set consists of
`many millions of polygons and many gigabytes of
`imagery.
`
`l ('fotttposabiiity. Our data representation must allow
`the introduction of multiple types of gee-referenced
`data, including additiottal imagery, site models. cul-
`tural features. and annotatioas. it also must let the
`user switch between these on demand.
`
`I Efficiency. Users must be able to navigate the V'RML.
`structures easily and efficiently using a standard
`VliMi. browser or a customized browser that further
`increases browsing efficiency.
`I Dotti interchange. We must develop generic data rep—
`resentations for gee-referenced data itt VHML. This
`will let other geographic data providers produce data
`using the same representation.
`
`Guided by these requirements, WE implemented this
`functionality in a standard Vith. browser for dowa-
`loutllng data over the World Wide Web. We also devel-
`oped a custom terrain visualization package called
`'iirrraVision ii that can browse these VRMi. data strucv
`titres. Although not required to view the cotttent,
`Tet raVision ll let's the User perfoi'tlt specia liaed broWser-
`level optimizations that offer increased efficiency and
`seamless interaction wit It the terrain data.
`
`We designed our framework to simplify terrain data
`maintenance and to let users dynamically select partictn
`lar sets ofgeo-relerenced data. Our implementation ttses
`Java scripting to extend VRML’s base functionality and
`the [ExternalAuthoring interface to offer applicationrspe
`tiitc management of the virtual geographic environment.
`to help develop standard techniques for solving geo-
`graphical representation problems in VRM1., coauthor
`Lee lverson formed and currently chairs the Geon’tMi.
`group. an official Working Group ofrhe Web3D Consor-
`titttu (http://'www.ai.sricom/geovrtnl). As a service to
`the VitMl. comtnunityand the GeoVitMLeifort, we have
`made freelyavaiiable both tite‘l‘erruVision ll browser and
`all nt‘rite tools we developed for generating VRMI. terrain
`{litter sets. This includes the source code to all ofour cus-
`tom VRML nodes arid the tsmApi library that we use to
`generate the ‘v’RML data sets. The library is desetibed in
`
` L
`
`Page 6 of 13
`
`Unified Patents Exhibit 1010
`
`IEEE Computer Graphics and Applications
`
`31
`
`the sidebar “The tsmApi Library" and is available along
`with other materials and several example VItML data sets
`at http://Www.ai.st'i.comfl'ei't’a‘t’isiott.
`
`Multiresolution terrain techniques
`Terrain models are typically massive. For example, the
`US Geological Survey produces digital elevation models
`(DEMs) that contain a regular grid of 1,201 x 1,20] ele-
`vation values for a 1-degree area of the earth's surface.
`Producing a simple polygonal representation of a single
`DEM creates a model with more than 1.4 million poly—
`gons. The time required to download and render such a
`model would prohibitany real-time interaction using the
`current generation of VRML browsers. It therefore
`becotttes essential to manage level of detail (LCD).
`LCD techniques change a model's complexity based
`on some selection criteria, such as distance front the
`viewpoint or projected screen sire. The basic premise
`for these criteria is that any distant detail that projects
`to less titan a single pixel on the screen will not generally
`be visible. To implement: this. we need a mechanism to
`simplify a data set‘s gcomet ry and imagery.
`Several polygon simplification algorithms work well
`for terrain. However, many ofthese are viewrindepen-
`dent techniques that force the same degree of simplifi-
`cation across
`the entire terrain?“ These
`are
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`The tsmApl Library
`The “file Set Manager Application Program
`Interface (tsmApi) is a freely available C library
`from SRI International. The library offers
`functions for reading, writing, and generating
`terrain data used by TerraVision ll, including
`functions for generating VRML versions of the
`terrain data using the representations we
`describe in the article.
`
`Using the tsmApi library, users can create their
`own VRleL geographic data sets from several
`supported input formats such as raw imagery,
`Portable Bitmap (PBM) images, and Land
`Analysis System (LAS) bitmaps. The library also
`includes SRl's folly re-entrant VRML 9? parser,
`which can be used to parse VRMI. 97 files
`efficiently into memory and to write these
`structures back out to a VRML 97 file. Other
`functions-perfonn transformations between
`various geographic coordinate systems, such as
`Unlveral Transverse Mercator (UTM), geodetic
`(latitude/longitude), and earthuiixed geocentric,
`based on code from the US National Imagery
`and Mapping Agency's Nimamuse product.
`Precompiled tsmApi distributions are available
`for lrix, Solaris, Linux, and other platforms. In
`addition, the full C source code is available from
`the tsmApi home page, which also includes full
`API documentatioa, tutorials, format
`Specifications, and example source code. The
`umApi Web page is at http:!/www.ai.sri.comf
`tsmApl.
`
`
`
`
`
`Page 6 of 13
`
`Unified Patents Exhibit 1010
`
`

`

`VRML
`
`1 An example
`image pyramid
`showing
`(a) four differ-
`ent resolutions
`
`of an original
`image, where
`Each level is
`
`segmented into
`128 x128 pixel
`tiles, and
`(hi) how this
`structure can be
`used to alter the
`
`image resolu-
`tlon In different
`regions.
`
`
`
`or level; that is, at each higher resolution area, the tiles
`cover half the geographical area ofllte previous level.
`Using this representation, we can recursively resolve
`certain data set regions in more detail titan other
`regions. For example, Figure 1b shows the lower-right
`corner in high resolution with the surrounding regions
`displayed in progressively lower resolution. Assuming
`a tile size of 128 x 128 pixels, this example requires
`downloading and rendering only 49] Khytes (it) tiles)
`instead of the entire 3.1-Mhyte high-resolution image.
`if the user‘s location is the bottom-right corner, then dis-
`tant imagery is rendered at lower resolution than near
`imagery and we have achieved distance-based LOD.
`As Figure 2 shows, our image pyramids techniques
`can be applied to elevation grids and other types ofter—
`rain data. Because we use a tiled pyramid representa-
`lion For the geometry and the imagery, we can optimize
`the amount ofclala transferred over the network, the
`number of polygons in the Scene, and the amount of
`memory required for texture maps. As a result, we need
`onlyr fetch and display data for the region that the user
`is viewing, and only at a sufficient resolution for the
`user's viewpoint. This solution scales well to arbitrarily
`large data sets because it effectively attempts to keep
`the polygon count constant for any viewpoint.
`
`inappropriate for our application because switching to
`the highest resolutionstill involves loading every point
`of the original data set. Instead, we require a view-
`dependent technique that lets us vary the degree ofsim—
`plification with respect to the current viewpoint.“ This
`is often done trsing a hierarchical data structure, such
`as a quad-tree. Further, the LCD algorithm must not
`require access to the entire high-resolution version of
`the data set, as that would limit us to viewing only data
`sets that can fit on the user’s local storage system. Given
`these requirements, a tiled. pyramid representation
`best suits our needs."u
`
`A pyramid is a multiresolution hierarchy for a data
`set. For example, ifthe original image is 1024 x 1024
`pixels, then the pyramid might contain the original
`image along with down-so mpled versions at resolutions
`ol'512 x 512 pixels, 2.56 x 256 pixels, 128 x128 pixels,
`and so on. As Figure 1a shows, each pyramid image is
`then segmented into rectangular tiles. where all tiles
`have the some pixel dimensions A tile at a given pyra—
`mid level will thus map onto four tiles on the next high-
`
`2 Using a tiled
`pyramid struc-
`ture to repre-
`sent terrain
`
`geometry.
`Closer terrain is
`
`represented in
`higher fidelity
`(more polyu
`gens) than
`distant terrain.
`
`
`
`
`
`Multlresolutlon data in VRMI.
`We introduce four types OFVRML files to represent a
`large, tiled rnuiriresolution hierarchy of the globe: rer-
`rain tile files, feature files, geoiile files. and tree files.
`Figure 3 shows these files and their relationships The
`tree files recursively implement the LCD hierarchy by
`il‘rlining a single gentile file at one LOD and four higher
`resolution tree files at the next L01). 'l‘he gentile file
`inlincs all of the feature and terrain tiles that covert!
`
`geographical area and LCD. A terrain tile file contains
`the neural elevation and in‘tagc texture data fora given
`image, geographical area. and LOD. Feature files
`describe a geographical area’s objects, such as buildings r
`and roads. We discuss these relationships and their
`advantages below.
`
`32
`
`Page 7 of 13
`MarchMpril 1999
`
`Unified Patents Exhibit 1010
`
`
`
`Page 7 of 13
`
`Unified Patents Exhibit 1010
`
`

`

`
`
`A tree tile
`
`Hierarchy of
`gentile files
`
`Two terrain tile
`pyramids
`
`A feature file
`
`3 The relationship between tree,
`geotile. terrain tile, and feature
`files. Unidirectional arcs represent
`inline links to files over the network.
`Bold rectangles delineate file
`boundaries.
`
`Tree files
`
`Tree files implement part of the mttlti tit-Solution hier-
`archy for the entire globe. in effect. these files are the
`glue that holds the geotiles in the quad-tree structure. A
`tree file initially loads a single gentile, but when the User
`approaches the tile, it‘s replaced with four higher—reso-
`iution tree files, which in turn inline the geotiles for the
`fourquad-tree children. (At the bottom level of the tree
`hierarchy, the four geotiles are inlined directly.) The
`hierarchy of tree files must be generated only once and
`won’t generally need to be modified further—except
`perhaps to extend the tree for higher resoltttions at a
`later j tincture. In the future. it mightbe possible to gen
`crate tree files on the fly.
`The tree files let us split the entire LOD hierarchy over
`multiple files and abetted the LCD structure from the
`actual terrain data. They also let us create a different
`LOD tree depth for different global regions. For exam
`ple, we could have loo-km-resolution data for the
`entire globe but recursively insert higher resolution
`data for smaller regions of interest. such as a one-lun-
`tcsolution data set for the contetntinous United States
`
`and a one-m-resolution data set for Yosemite Valley,
`California.
`
`it would be possible to ttsc the VRMI. Inl ine node
`to include the gentile files into the LCD hierarchy. How—
`ever, VRML 97 does not specify when the Universal
`Resource Locator (URL) ofan Inl ine notle should be
`loaded, making thisa browser—dependent feature. Cur—
`rently, most browsers load all inline scenes at once. This
`makes good sense for small scenes with a handful of
`Inline nodes. l-lowevet‘, ii We have a data set' of 10
`U bytes, the VTtML browser will attempt to load all these
`data into memory at once. This is obviously unaccept.
`able for our application, so wc must control when inline
`files are loaded and unloaded. To do this, we. developed
`
`a new node. called Quadnou, using VRML 97's
`EXTERNPROTO and scripting features. QuadLOD pro-
`vides a terrain-specific LOD capability that efficiently
`manages the loading and unloading of higher levels of
`detail. When the user enters a certain Volume around
`the tile (determined by a Proximi tysensor) Quad—
`LOD loads only a tile‘s four higher resolution children.
`The nodealso uses a tile-caching mechanism so that tiles
`aren't needlessly reloaded. When the user approaches a
`region ofterrain. more detail is progressively loaded and
`displayed in a coarse-to—finc fashion. Most VRME.
`browsers perform noublocking network reads so that
`the user can still interact with the scene while higher
`resolution imagery and elevation loads.
`
`Gentile files
`
`Gcotilc files contain links to all data within a single
`tile. The most basic geotile includes a single terrain tile
`file for the region However, it's possible fora gentile to
`store linits to multiple alternative terrain tiles, such as
`tiles referring to satellite, aerial. anti map imagery, as
`well as feature files for objects that exist on I he terrain,
`such as buildings, roads. and annotations.
`By adding this extra layer to our global structure1 we.
`Simplify the task of maintaining and adding new data
`sets. For example, when we want It] add a new image
`pyramid, we can generate the terrain tiles in isolation
`anti simply link them to appropriate geotiles. [if the new
`data set requires higher resolution than the region pre-
`viously required, we also mllsl‘ generate new tree files.)
`In addition, becttu5e each data set is stored indepen—
`dently and referenced only via the geotiles, We can selec-
`tively display any combination of data sets. A node we
`created, GeoTi 1e, permits this selectivity by organia
`ing the terrain tile and feature file links into sets of
`Switch nodes.
`
`Page 8 of 13
`
`Unified Patents Exhibit 1010
`
`IEEE Computer Graphics and Applications
`
`33
`
`
`
`Page 8 of 13
`
`Unified Patents Exhibit 1010
`
`

`

`VRML
`
`‘-' IN Hun-h- ll'l' Nun-nu-
`
`.
`
`'#_.., ._
`
`For: BHIMIJ!‘ in \‘Ils‘ltll
`t “it
`,s.,_ If
`I
`
`'
`
`aim—u
`'
`
`H
`
`4 A tiled terrain
`model showing
`geo~referenced
`3D geometry
`overlaid for
`
`roads (orange)
`and buildings
`(yellow).
`
`Terrain rife files
`Terrain tiles contain the actual terrain data for a sin-
`
`gle data set tile at a particular detail level. This includes
`the elevation geometry and the texture map imagery for
`the specific terrain tile. The VRML 97‘ specification pro-
`vides us with two potential primitives for representing
`terrain geometry: the IndexedFaeeSet
`and the
`E1 evationGr id. The latter node lets the usor specify
`a grid of height values above the x-s plane. whereas the
`more general IndexedFaoeSet node lets the user
`define arbitrary polygons in 3D space. VRML 97"s Ele-
`vationGrid was introduced specifically to represent
`terrain models and offers a compact mechanism to
`describe simple height field data. However, it has serious
`limitations that prevent us from using it, including that
`it assumes that the heights are relative to a flat plane—
`an obvious problem when dealing with curved planets.
`ElevetionGric‘la are thus useful only for modeling
`local areas, where the earth’s curvature is insignificant.
`Because we want to support global data sets, we use the
`IndoxechaceSet to build terrain geot‘i‘tett'y.
`
`Feature files
`Feature files contain VRML models for objects relat—
`ed to a region of terrain. Examples include a region's
`cultural features, such as roads anti lines of communi-
`cation; weather simulations, such as clear air turbulence
`isosttrfaces and wind vectors; and other 3D data, such
`as terrain annotations.
`
`integrating terrain features proves difficult because
`features cart extend beyond tile boundaries. For exam-
`ple, a road might cover multiple tiles, or a large building
`might sit on the boundary between two tiles. One way
`to deal with this problem is to dissect the geometry for
`all ground features along tile boundaries, forcing the
`condition that all features in a tile are contained entire-
`
`ly within that tile. Another-solution is to simply include
`a link to the same feature in all relevant geotilcs. We
`selected the latter approach because it does not con-
`strain tht‘: cultural features to the same resolution range
`as the terrain, and it requires no modification to the fea-
`ture's geometry. However. one probiem is that the
`browsor Would normally load, store, and render dupli-
`cate copies of each feature for every loaded gentile in
`which it occurs. To avoid this, we have designed our
`GeoTile node so that it lteeps track ofeach request for
`a feature file‘s URL. We do this using static class store
`tures in a Java script. We load feature files only on first
`invocation, incrementing their reference count, and
`unload a feature file only when its reference count
`returns to zero. Figure 4 shows the fusion of terrain data
`anti cultural features that results.
`Geographic coordinate Systems
`VRML defines a Cartesian coordinate system for mod-
`eling objects in a 3D volume. In geographic terms, this
`gives us a geocentric representation: a coordinate (any,
`z) is assumed to be a 3D offset [in meters] from the
`earth’s center. However, most elevation data are pro—
`
`i
`
`,
`
`i
`‘
`i
`
`l
`
`i
`
`vided in some geodetic or projective coordinate system.
`A geodetic coordinate system is related to the ellipsoid
`used to model the earth {such as the latitude-longitude
`system). A projective coordinate system projects the
`ellipsoid onto some simple surface, such as a cone or a
`cylinder. Examples include the I..ambert Conformal
`Conic or the Universal Transverse Mercator projections.
`Such coordinate systems were designed for different
`applications and offer particular advantages and restric-
`tions. For example, some projections can represent only i
`small-scale regions; others are conformal, offering the
`same scale in every direction; and others can be equal
`area—the projected area corresponds to the earth’s
`physical area over the entire projection. 'i'o use data in
`these different coordinate systems, we must convert
`coordinates in these systems into the VRML geocenttic
`coordinate system. Descriptions for performing many
`of these transformations are available elsewhere.” The
`
`l
`
`sidebar “What Shape Is the Earth?" discusses related I
`
`representation challenges.
`
`Floating-point precision Issues
`The VRML 9'? specification defines the. SFFloat and
`Mi-‘loat fields to represent floating-point numbers How.
`ever. these are only sin tile-precision values; the dynamic
`range of a single-precision floating-point number isn‘t
`sufficient to store accurate gcoeentric coordinates For
`example, the lEEE single-precision format defines a 23-
`hit ntant issa. This provides a resolution of approximate
`1y six digits (2'23 = 8.39 x 10“). The earth’s diameter is
`roughly 12,700,000111, and thus we can model terrain to
`an accuracy ofonly tens or hundreds ofmeters. This accu-
`racy can‘t even represent the results front a civilian-grade
`Global Positioning System (GPS), let alone fail hfully rep-
`resent ground i'ea-tturcs such as buildings or roads.
`MostVl’cML browsers use only single-precision arith-
`metic for modeling and matrix operations, and 11105!
`modern graphics hardware uses only single precision.
`We must therefore implement accurate geoccntric coor-
`
`34
`
`Page 9 of 13
`March/April 1999
`
`Unified Patents Exhibit 1010
`
`
`
`Page 9 of 13
`
`Unified Patents Exhibit 1010
`
`

`

`
`
`What Shape Is the Earth?
`in a computer graphics system, the simplest
`way to represent the earth is to prodUCe a sphere
`and then apply to it a texture map. This method is
`adequate for a coarse representation. However, if
`we want to model the planet down to submeter
`accuracy, We must better Understand the earth's
`shape and the coordinate systems that describe
`[L16
`
`Ellipsolds
`The earth can best be modeled geometrically
`using an ellipsoid of rotation. Such an ellipsoid is
`traditionally specified by two of three variables: the
`semi-major axis (a), the semi-minor axis (is), and
`the inverse flattening (11f: a! (a — in). Over the
`past 200 years, many different reference ellipsoids
`have been formulated, each defining slightly
`different values for these variables. The current US
`Department of Defense standard is defined by the
`World Geodetic System 1934 M6584), such that
`o = 6378137.0m and b = 6356752.3142m.
`
`Geolds
`
`The ellipsoid describes an ideal surface, but
`most elevation data are given relative to the
`geoid, not the ellipsoid. The geoid is the
`physically measurable surface Corresponding to
`mean sea level and is related to the earth's
`
`gravitational