64110-2425
`
`VMreeberdoosMeeslMeeeeelolobeebestobelsbectetel
`ALL FOR AGC 64240
`
`0269
`
`ST
`MO
`
`Microsoft Corp. Exhibit 1010
`
`

`

`ieIEEE
`
`G
`
`ae”
`AND|APPLICATIONS
`
`IEEE Computer Society
`10662 Los Vaqueros Circle, PO Box 3014
`Los Alamitos, CA 90720
`http://computer.org/cga
`
`Editor in Chief
`James J, Thomas
`Pacific Northwest National Laboratory
`902 Battelle Boulevard
`Richland, WA 99352
`Jim.Thomas@pnl.gov
`
`Submissions:Please submit seven copiesofall articles to
`Alkenia Winston, magazine assistant, IEEE ComputerSociety,
`10662 Los VaquerosCircle, Los Alamitos, CA 90720, Submit
`proposals forspecialissues to Michael Rhodes,
`mrhodes@odsus.jnj.com, All submissions are subject to editing
`for style, clarity, and space considerations. An author's guideis
`available from the Web,publicationsoffice, or by e-mail from
`awinston@computer.org.
`
`Associate Editors in Chief
`Michael L. Rhodes
`Ortho Diagnostic Systems
`Turner Whitted
`Microsoft
`
`Editorial Board
`
`Frank W.Bliss
`John C, Dill
`Rae A. Earnshaw
`José L, Encarnagdo
`Andrew Glassner
`Markus Gross
`Bertram Herzog
`Tosiyasu L. Kunii
`Carl Machover
`Gregory M, Nielson
`Michael J. Potel
`Theresa-Marie Rhyne
`Lawrence J, Rosenblum
`Maureen Stone
`
`EDS/GM Corp.
`SimonFraser University
`University of Bradford
`Technical University of Darmstadt
`Microsoft
`ETH, Zurich
`University of Michigan
`Hosei University
`MachoverAssociates
`Arizona State University
`Wilderest Associates
`Lockheed Martin
`Naval Research Laboratory
`StoneSoup Consulting
`
`Managing Editor Nancy Hays
`Assistant Editor Robin Baldwin
`Editorial Assistant Kristine Kelly
`Magazine Assistant Alkenia Winston
`Art Direction Joe Daigle
`
`Publisher Matt Loeb
`Advertising ManagerPatricia Garvey
`Advertising Supervisor Marian Anderson
`Advertising Coordinator Debbie Sims
`Member/Cire. Promo Mgr. Georgann Carter
`
`Publications Board
`
`Benjamin Wah(Vice President),
`Gul Agha (MOCchair), Jon Butler (TOC chair),
`Ron Williams (IEEE Pubs Representative),
`Jake Aggarwal, Alberto del Bimbo, Mike Liu, Zhiwei Xu
`
`Magazine Operations Committee
`
`Carl Chang (chair), William Everett (vice chair),
`James H. Aylor, Jean Bacon, Wushow Chou, George Cybenko,
`William |. Grosky, Steve McConnell, Daniel E. O'Leary,
`Ken Sakamura, MunindarP, Singh, James J. Thomas,
`Yervant Zorian
`
`Editorial: [EEE Computer Graphics and Applications serves both
`users and designers of graphies hardware, software, and systems.
`Its readers work in industry, business, the arts, and universities.
`Articles are peer-reviewed; departments are refereed. Unless
`otherwise stated, bylined articles and departments, as well as
`descriptions of products and services, reflect the author's orfirm's
`opinion; inclusion in this publication does not necessarily
`constitute endorsementby the [EEE 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 carry a code at the bottom ofthe first page,
`provided the per-copyfee indicated in the codeis paid throughthe
`Copyright 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 republication permission, write to Copyrights and
`Permissions Department, [EEE Publications Administration, 445
`Hoes Lane, P.O, Box 1331, Piscataway, NJ 08855-1331. All rights
`reserved, Copyright © 1999 by the Institute of Electrical and
`Electronics Engineers,Inc.
`
`Circulation: [EEE Computer Graphics andApplications (ISSN 0272-
`1716) is published bimonthly by the IEEE Computer Society.
`IEEE
`Headquarters: Three Park Ave., 17th Floor, New York, NY 10016-
`5997. IEEE Computer Society Headquarters: 1730 Massachusetts
`Ave., Washington, DC 20036-1903. IEEE ComputerSociety
`Publications Office: 10662 Los VaquerosCircle, PO Box 3014, Los
`Alamitos, CA 90720; (714) 821-8380, Annual subscription: $34 in
`addition to any IEEE group orsociety dues. Members of other
`technical organizations: $90. Nonmember subscription rates are
`available on request. Back issues: members, $10; nonmembers, $20.
`This journalis also available in microfiche form and on the Web.
`
`Postmaster: Send address changes and undelivered copies to
`IEEE Computer Graphics and Applications, IEEE Computer Society,
`10662 Los Vaqueros Circle, PO Box 3014, Los Alamitos, CA 90720,
`Periodicals postage is paid at New York, NY, and at additional
`mailing offices. Canadian GST #125634188. Canada Post
`International Publications Mail Product (Canadian Distribution)
`Sales Agreement #0487848, Printedin USA.
`
`State/Country
`
`Moving?
`
`PLEASE NOTIFY Mail to
`US 4 WEEKS
`IEEE Computer Society
`IN ADVANCE
`10662 Los Vaqueros Circle
`PO Box 3014
`Los Alamitos, CA 90720
`* This notice of address change will apply to all IEEE publications to
`which you subscribe,
`* List your new address below.
`*
`If you have a question about your subscription, place your address
`label here and clip this form to yourletter.
`ATTACH
`LABEL
`HERE
`
`Name(please print)
`
`New address
`
`City
`
`Microsoft Corp. Exhibit 1010
`
`Microsoft Corp. Exhibit 1010
`
`

`

`EEE
`
`mputerGraphics
`
`_—
`
`AND APPLICATIONS
`
`Articles
`
`March/April 1999
`Volume 19 Number 2
`Published by the IEEE ComputerSociety
`
`VRML
`1 7 Guest Editor’s Introduction:
`Virtual Reality Modeling Language
`MaureenStone
`
`with VRML
`David R. Nadeau
`
`1 8 Tutorial: Building Virtual Worlds
`VRML makesit easy to create virtual worlds, This
`tutorial reviews VRMLs syntax and features as well
`as its world construction and animation abilities.
`
`3
`
`TerraVisionII: Visualizing Massive
`Terrain Databases in VRML
`Martin Reddy, YvanLeclerc, Lee Iverson,
`and Nat Bletter
`To disseminate 3D maps and spatial data over the
`Web, the authors designed massive terrain data sets
`accessible througheither aVRML browser orthe cus-
`
`tomized TerraVision II browser,
`
`3 9 Large-Scale Mine Visualization
`Using VRML
`Keith Russ and Andrew Wetherelt
`Traditionally, mine plans and sections in 2D stored
`3D information. This article showsthat using VRML
`to modelthis information leads to new, interactive
`
`methods ofdata visualization.
`45 “Bottom, Thou Art Translated":
`The Making of VRML Dream
`Stephen N. Matsuba and Bernie Roehl
`Bringing virtual theater to the Web requires 3D
`graphics, efficient networking, and strong content.
`Pt
`The authors discuss the VRML DreamProject, a real-
`time Internet performance.
`
`International Standard
`
`5 2? Developing the VRML 97
`George5. Carson, RichardF. Puk, and
`Rikk Carey
`VRML97arose from a cooperative effort between the
`standards and VRML communities. The methodology
`
`future standards.
`
`employed applies equallywell to developmentof
`59 VRMLTesting: Making VRML Worlds
`Look the Same Everywhere
`Mary Brady, Alden Dima, Len Gebase,
`Michael Kass, Carmelo Montanez-Rivera,
`
`andLynneRosenthal
`NISTtools 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.
`és
`A Framework for Streaming Geometry
`
`in VRML
`André Guéziec, Gabriel Taubin, Bill Horn,
`
`and Francis Lazarus
`The authorsintroduce a framework for streaming
`geometry in VRML thateliminates the need to
`perform complete downloads of geometric models
`before starting to display them.
`
`Stephen Chenney, Jeffrey Ichnowski, and
`
`79 Dynamics Modeling and Culling
`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.
`a
`WBA
`rt
`fa? >
`
`-FEp 24 tar(250
`
`http://computer.org/ega/
`
`ISSN 0272-1716
`
`SRany
`
`Microsoft Corp. Exhibit 1010
`
`Microsoft Corp. Exhibit 1010
`
`

`

`4 About the Cover
`Advancing 3D through VRML
`on the Web
`
`6 Projects in VR
`Public Speaking in Virtual
`Reality: Facing an Audience
`of Avatars
`
`10 Applications
`VizSim Technology Helps
`Find Oil Faster
`
`88 Andrew Glassner‘s
`Notebook
`String Crossings
`
`96 New Products
`
`100 Advertiser/Product
`Index
`
`ComputerSociety Information, C3
`Changeof Address form, p.
`1
`
`
`
`
`
`Microsoft Corp. Exhibit 1010
`
`Microsoft Corp. Exhibit 1010
`
`

`

`VRML
`
`
`
`This material may be protected by Copyright law (Title 17 U.S. Code)
`
`|
`
`TerraVision Il:
`Visualizing Massive
`Terrain Databases
`in VRML
`
`Martin Reddy, Yvan Leclerc, Lee Iverson,
`and NatBletter
`SRI International
`
`domains,' and VRMLoffers cartographers and geogra-
`phers the potential to disseminate 3D maps andspatial
`data over the World Wide Web, However, to date we have
`not seenuseful large-scale VRMLgeographic databases.
`We aimto enable visualization of near photorealistic
`3D models of terrain that can be on the order of hun-
`dreds of gigabytes. This mightinclude differenttypes of
`terrain imagery for particular regions, as well as site
`models and auxiliary information for groundfeatures.
`The following scenario indicates the capabilities
`required. Say a user wantsto find a particularbuilding
`inaparticularcity. Her journey begins with a 3D model
`of the earth viewed fromspace. This model is texture-
`mapped withsatellite imagery of 100 kilometers reso-
`lution—thatis, each pixel in the texture map represents
`a region onthe planet's surface covering 100 km*. To
`findthe city, the userfirst rotates the earth to view the
`
`—
`
`Roo have in-
`
`
`
`To disseminate 3D maps and
`
`spatial data over the Web,
`
`we designed massive terrain
`
`data sets accessible through
`
`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, VRMLis drawing more
`serious interest from researchers
`across the spectrum, including geo-
`graphers, cartographers, geologists,
`and computerscientists, as the side-
`bar “Related Work" describes. As
`Theresa-Marie Rhyne noted, geo-
`sraphic information system (GIS) and scientific visual-
`ization tools have begun to expand into each other's
`
`either a VRML browser or
`
`the customized TerraVision
`
`ll browser.
`
`
`
`Related Work
`Michael Abernathy and Sam Shaw described
`Currently, interesting and significant work
`their work using VRML to visualize the course for a
`addresses the problem of representing geographic
`197-mile relay race through the San Francisco Bay
`data in VRML. In the earth sciences, Kate Moore
`Area.’ They did this using standard US Geological
`described the work of the Virtual Field Course
`Survey (USGS) 7.5 are min digital elevation
`(VFC) project,' which is developing software tools
`models (DEMs) for the terrain geometry with geo-
`to familiarize students with fieldwork locations and
`Ji
`referenced satellite imagery draped over the
`aid data collection and analysis. The VFC project
`
`uses VRML and java to provide interactive 2D and_terrain. Their systern also used GlobalPositioning tt
`3D views of geo-referenced data to enhance
`System (GPS) input to create a line segment
`ai
`students‘ cognition of the real environment.
`showing the race's course over the VRMLterrain.
`The US Naval Postgraduate School is currently
`
`working on a project to develop a 3D modelof 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 ofthe bay.
`Their representation uses multiresolution
`techniquesto deliver these large data amounts
`over a 28K modem connection.
`
`|
`4
`il
`References
`1. K. Moore, “Interactive Virtual Environments for Field:
`work,” British Cartographic Society Annual Symp., 1997;
`h
`available at htta://www.geog.le.ac.uk/mek/VirtEnv.htm.
`2. M. Abernathy and S. Shaw, “Integrating Geographic ‘Hf]
`
`Information in VRML Models,” Proc. Third Symp.
`VRML, ACM New York, 1998, pp. 107-114.
`
`30
`
`March/April 1999
`
`Microsoft Corp. Exhibit 1010
`0272-1716/99/510.00 © 1999 WEEE
`
`Microsoft Corp. Exhibit 1010
`
`

`

`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`03
`
`1
`
`Microsoft Corp. Exhibit 101
`IEEE Computer Graphics and Applications
`
` ~
`
`(arget region in more detail. As she zooms into the
`region, higherresolution data, suchas elevation and
`imagery, are progressively downloaded anddisplayed
`until she is “flying” over mountains with imagery down
`to one-meterresolution. Overcertain parts of the ter-
`rain, alternative imageries are available, such as aerial
`photographs; the user can select any image to view on
`top of the terrain geometry. As she approachesabuilt-
`up area, 3D models of buildings come into view. When
`the userclicks on a building, information about it js dis-
`played in a separate frame on the browser. Using this
`method, the userlocates the target building. Through-
`out the navigation, the user's location is displayed via
`an active map interface that provides a context for the
`landscape being viewed.
`In setting out to achieve such capabilities, we identi-
`fied four principal design criteria:
`
`the sidebar “The tsmApiLibrary” andis available along
`withother materials and several example VRML datasets
`at http://www.ai.sri.com/TerraVision,
`
`Multiresolution terrain techniques
`Terrain models are typically massive, For example, the
`US Geological Survey producesdigital elevation models
`(DEMS) that contain a regulargrid of 1,201 x 1,201 ele-
`vation values for a 1-degree area ofthe earth's surface,
`Producing a simple polygonal representation ofa single
`DEM creates a model with more than1.4 million poly-
`gons. The time required to download and render sucha
`model would prohibit any real-timeinteraction using the
`current generation of VRML browsers. [t therefore
`becomesessential to managelevelof detail (LOD).
`LOD techniques change a model's complexity based
`on someselection criteria, such as distance from the
`viewpointorprojected screensize, The basic premise
`forthese criteria is that anydistant detail that projects
`to less thanasingle pixel on the screenwill not generally
`be visible, To implementthis, we need a mechanism to
`simplify a data set’s geometry and imagery.
`Several polygonsimplification algorithms work well
`for terrain. However, manyofthese are view-indepen-
`dent techniquesthat force the same degree of simplifi-
`cation across
`the entire terrain?” These
`are
`
`
`
`® Scalability. Our design must scale to very large data
`sets. Commonly, a geographic data set consists of
`many millions of polygons and many gigabytes of
`imagery.
`@ Composability. Our data representation must allow
`the introduction of multiple types of geo-referenced
`data, including additional imagery,site models, cul-
`tural features, and annotations. It also must let the
`user switch between these on demand.
`B Efficiency. Users must be able to navigate the VRML,
`structures easily and efficiently using a standard
`VRMLbrowseror a customized browserthat further
`The tsmApi Library
`increases browsing efficiency.
`The Tile Set Manager Application Program
`® Datainterchange, We mustdevelop generic data rep-
`Interface (tsmApi)is a freely availableClibrary
`resentations for geo-referenced data in VRML. This
`from SRI International. Thelibrary offers
`will let other geographic data providers produce data
`functions for reading, writing, and generating
`using the same representation.
`terrain data used by TerraVisionIl, including
`functions for generating VRML versions of the
`terrain data using the representations we
`describein thearticle.
`Using the tsmApilibrary, users can create their
`own VRML 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 SRI’s fully re-entrant VRML 97 parser,
`which can be used to parse VRML 97files
`efficiently into memory and to write these
`structures back out toa VRML 97 file. Other
`functions perform transformations between
`various geographic coordinate systems, such as
`Univeral Transverse Mercator (UTM), geodetic
`(latitude/longitude), and earth-fixed geocentric,
`based on code from the US National Imagery
`and Mapping Agency's Nimamuse product.
`Precompiled tsmApidistributions are available
`for Irix, Solaris, Linux, and other platforms.In
`addition, the full C source codeis available from
`the tsmApi home page, which also includesfull
`API documentation, tutorials, format
`specifications, and example source code, The
`tsmApi Webpageis at http://www.ai.sri.com/
`tsmApi.
`
`Guidedby these requirements, we implementedthis
`functionality in a standard VRMLbrowserfor down-
`loading data over the World Wide Web, Wealso devel-
`oped a customterrain visualization package called
`TerraVisionII that can browse these VRMLdata struc-
`tures, Although not required to view the content,
`TerraVisionI] lets the user perform specialized browser.
`level optimizationsthatofferincreasedefficiency and
`seamless interaction with the terraindata.
`Wedesignedour frameworkto simplify terrain data
`maintenance andto let users dynamically select particu-
`lar sets ofgeo-referenceddata, Our implementationtses
`Javascripting to extend VRML’s base functionality and
`the External AuthoringInterfaceto offer application-spe-
`cific managementofthe virtual geographic environment,
`To help develop standard techniquesfor solving geo-
`graphical representation problems in VRML, coauthor
`Lee Iverson formedandcurrently chairs the GeoVRML
`group, an official Working Group ofthe Web3D Consor-
`tum (http://www.ai.sri.com/geovrml). As a service to
`the VRML community and the GeoVRMLeffort, we have
`madefreely available both the TerraVision Il browser and
`allof the tools we developedfor generating VRML terrain
`data sets. This includes the source codetoall ofour cus-
`tom VRMLnodesand the tsmApilibrary that weuse to
`generate the VRMLdata sets. Thelibrary is describedin
`
`Microsoft Corp. Exhibit 1010
`
`

`

`VRML
`
`1 An example
`image pyramid
`showing
`(a) four differ-
`ent resolutions
`
`of an original
`image, where
`each levelis
`
`segmentedinto
`128 x 128 pixel
`tiles, and
`(b) how this
`structure can be
`used to alter the
`
`imageresolu-
`tion in different
`regions.
`
`
`
`Microsoft Corp. Exhibit 1010
`
`erlevel; thatis, at each higherresolutionarea, the tiles
`coverhalf the geographical areaofthe previouslevel.
`Using this representation, we can recursively resolve
`certain data set regions in more detail than other
`regions. For example, Figure 1b showsthe lower-right
`cornerin high resolution with the surrounding regions
`displayed in progressively lowerresolution. Assuming
`a tile size of 128 x 128 pixels, this example requires
`downloading and rendering only 491 Kbytes(10 tiles)
`instead ofthe entire 3.1-Mbyte high-resolution image.
`Ifthe user’s locationis the bottom-right corner, then dis-
`tant imagery is renderedat lowerresolution than near
`imagery and we have achieveddistance-based LOD.
`As Figure 2 shows, our image pyramids techniques
`can be applied to elevationgrids and othertypes of ter-
`rain data. Because we use a tiled pyramid representa-
`tion for the geometry and the imagery, we can optimize
`the amount of data transferred over the network, the
`numberofpolygons in the scene, and the amount of
`memory requiredfor texture maps. Asaresult, we need
`only fetch and displaydata forthe region that the user
`is viewing, and only at a sufficient resolutionfor the
`user's viewpoint. This solutionscales well to arbitrarily
`large data sets becauseit effectively attempts to keep
`the polygon count constantfor 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-
`dependenttechnique thatlets us vary the degree ofsim-
`plification withrespect to the current viewpoint."” This
`is often done using ahierarchical data structure, such
`as a quad-tree. Further, the LOD algorithm mustnot
`require access to the entire high-resolution version of
`the dataset, as that would limit us to viewing only data
`sets that can fiton the user's local storage system. Given
`these requirements, a tiled, pyramid representation
`best suits our needs.°"
`A pyramidis a multiresolution hierarchy for a data
`set. For example, if the original image is 1024 x 1024
`pixels, then the pyramid might contain the original
`image along with down-sampled versionsat resolutions
`of 512 x 512 pixels, 256 x 256 pixels, 128 x 128 pixels,
`and so on. As Figure 1a shows, each pyramid image is
`then segmentedinto rectangulartiles, whereall tiles
`have the samepixel dimensions, A tile at a given pyra-
`midlevel will thus mapontofourtiles on the next high-
`
`
`
`geometry.
`Closer terrain is
`represented in
`higher fidelity
`(more poly-
`gons) than
`distant terrain.
`
`32
`
`March/April 1999
`
`Multiresolution data in VRML
`Weintroducefourtypes of VRMLfiles to representa
`2 Usingatiled
`large, tiled multiresolution hierarchy of the globe: ter-
`pyramid struc-
`raintilefiles, feature files, geotile files, andtreefiles.
`ture to repre-
`Figure 3 shows thesefiles andtheirrelationships. The
`sent terrain
`tree files recursively implement the LODhierarchy by
`inlining a single geotile file at one LOD andfourhigher
`resolution treefiles at the next LOD. The geotile file
`inlines all of the feature andterraintiles that cover 4
`geographical area and LOD. A terraintile file contains
`the actual elevation andimage texture datafor a given
`image, geographical area, and LOD, Feature files
`describe a geographical area’s objects, such as buildings
`and roads, Wediscuss these relationships andtheif
`advantages below.
`
`Microsoft Corp. Exhibit 1010
`
`

`

`
`
`A tree file
`
`Hierarchy of
`geatile files
`
`Twe 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
`Treefiles implementpart of the multiresolution hier-
`archyfor 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 geotile, but whenthe user
`approachesthetile, it's replaced with four higher-reso-
`lutiontree files, which in turninline the geotiles for the
`four quad-tree children, (At the bottomlevel 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 extendthe tree for higher resolutions at a
`laterjuncture. In the future, it might be possible to gen-
`erate tree files on the fly.
`Thetree files let us split the entire LOD hierarchy over
`multiple files and abstract the LOD structure fromthe
`actual terrain data. They also let us create a different
`LOD tree depthfordifferent global regions. For exam-
`ple, we could have 100-km-resolution data for the
`entire globe but recursively insert higher resolution
`data for smaller regionsofinterest, such as a one-kim-
`resolution data set for the conterminous United States
`and a one-m-resolution data set for Yosemite Valley,
`California,
`It would be possible to use the VRML Inline node
`io include the geotile files into the LOD hierarehy. How-
`ever, VRML 97 does not specify when the Universal
`Resource Locator (URL) of an Inline node should he
`loaded, making this a browser-dependentfeature. Cur-
`rently, most browsers loadall inline scenes at once. This
`makes good sense for small scenes with a handful of
`Inline nodes, However, if we have a data set of 10
`Gbytes, the VRML browserwill attempt to loadall these
`data into memory at once. This is obviously unaccept-
`able for ourapplication, so we must control wheninline
`files are loaded and unloaded. To dothis, we developed
`
`a new node, called QuadLOp, using VRML 97's
`EXTERNPROTOandscripting features. QuadLOD pro-
`vides a terrain-specific LOD capability thatefficiently
`manages the loading and unloading of higherlevels of
`detail. When the userenters a certain volume around
`the tile (determined by a ProximitySensor) Quad-
`LOD loads only atile’s four higher resolution children.
`The node also uses a tile-caching mechanismso thattiles
`aren't needlessly reloaded. Whenthe userapproaches a
`regionofterrain, moredetailis progressively loaded and
`displayed in a coarse-to-fine fashion, Most VRML
`browsers perform nonblocking network reads so that
`the userean still interact with the scene while higher
`resolution imagery and elevation loads.
`
`Geotile files
`Geotile files contain links to all data within asingle
`tile, The most basic geotile includes a single terrain tile
`file for the region. However,it’s possible fora geotile to
`store links to multiple alternative terraintiles, such as
`tiles referring to satellite, aerial, and map imagery, as
`well as feature files for objects that exist on the terrain,
`such as buildings, roads, and annotations.
`By adding this extra layer to ourglobal structure, we
`simplify the task of maintaining and adding new data
`sets. For example, when we want to add a new image
`pyramid, we can generate the terraintiles in isolation
`andsimplylink themto appropriate geotiles. (Ifthe new
`data set requires higher resolution thanthe regionpre-
`viously required, we also must generate new treefiles.)
`In addition, because each data setis stored indepen-
`dently and referencedonly via the geotiles, we can selec-
`tively display any combinationofdata sets, A node we
`created, GeoTile, permits this selectivity by organiz-
`ing the terrain tile and feature file links into sets of
`Switch nodes.
`
`Microsoft Corp.
`IEEE Computer Graphics and Applications
`
`Exhibit 1010
`33
`
`Microsoft Corp. Exhibit 1010
`
`

`

`VRML
`
`
`
`4 A tiled terrain
`model showing
`geo-referenced
`3D geometry
`overlaid for
`
`roads (orange)
`and buildings
`(yellow).
`
`Terraintile files
`Terrain tiles contain the actual terrain data fora sin-
`ele dataset tile at a particulardetail level, This includes
`the elevation geometry and the texture map imagery for
`the specific terraintile. The VRML97 specification pro-
`vides us with two potential primitives for representing
`terrain geometry: the IndexedFaceSet
`andthe
`ElevationGrid. Thelatter nodelets the user specify
`a grid of height values above the x-z plane, whereas the
`more general IndexedFaceset
`nodelets the user
`define arbitrary polygons in 3D space. VRML97’s Ele~
`vationGrid wasintroducedspecifically to represent
`terrain models and offers a compact mechanism to
`describe simple heightfield data,However,it has serious
`limitations that prevent us fromusingit, including that
`it assumesthat the heights are relative to a flat plane—
`an obvious problem whendealing with curved planets.
`EBlevationGrids are thus useful only for modeling
`local areas, where the earth’s curvatureis insignificant.
`Because we want to support globaldata sets, we use the
`IndexedFaceSat to build terrain geometry.
`
`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 andlines of communi-
`cation; weather simulations, such as clearair turbulence
`isosurfaces and wind vectors; and other 3D data, such
`as terrain annotations.
`Integrating terrain features proves difficult because
`features can extend beyondtile boundaries. For exam-
`ple, a road might cover multipletiles, ora large building
`might sit on the boundary between twotiles. One way
`to deal with this problemis to dissect the geometry for
`all groundfeatures along tile boundaries, forcing the
`conditionthat all features inatile are contained entire-
`
`ee tet
`ly within thattile. Anothersolutionis to simply include
`.
`oe ; —s
`lite
`Eb bet Veer fis “Cownascaier
`alink to the same featurein all relevant geotiles. We
`sab" Bockmete
`jw pe
`selectedthe latter approach becauseit does not con-
`Fort Benning In VEAL
`SE
`strain the cultural features to the same resolution range
`(iinet|(sit|nae|(Mai) Fratneshl](FesteesOF|
`as the terrain, andit requires no modificationto the fea-
`ture’s geometry. However, one problemis that the
`browser would normally load, store, and render dupli-
`cate copies of each feature for every loaded geotile in
`whichit occurs. To avoid this, we have designed our
`GeoTile nodeso thatit keepstrack of each request for
`a featurefile’s URL. We do this using static class struc-
`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 showsthe fusionof terrain data
`andcultural features that results.
`Geographic coordinate systems
`VRMLdefines a Cartesian coordinate systemfor mad-
`eling objects in a 3D volume, In geographicterms, this
`gives us a geocentric representation: a coordinate (x, y,
`z) is assumed to be a 3D offset (in meters) from the
`earth’s center. However, most elevation data are pro-
`vided in some geodetic orprojective coordinate system,
`A geodetic coordinate systemis related to the ellipsoid
`used to model the earth (such as thelatitude-longitude
`system). A projective coordinate system projects the
`ellipsoid onto somesimple surface, suchas a cone ora
`cylinder. Examples include the Lambert Conformal
`Conicor the Universal Transverse Mercatorprojections.
`Such coordinate systems were designedfor different
`applications andofferparticular advantages andrestric-
`tions. Forexample,someprojections can represent only |
`small-scale regions; others are conformal, offering the
`samescale in every direction; and others can be equal
`area—the projected area corresponds to the earth’s
`physical area overthe entire projection, To use datain |
`these different coordinate systems, we must convert
`coordinates in these systems into the VRML geocentric
`coordinate system. Descriptions for performing many —
`of these transformations ate available elsewhere.’ The
`
`|
`
`—
`
`|
`|
`|
`
`|
`
`sidebar “What ShapeIs the Earth?” discusses related |
`
`representation challenges.
`
`Floating-point precision issues
`The VRML 97 specificationdefines the SFFloat and
`MFloat fields to represent floating-point numbers. How-
`ever, these are only single-precision values; the dynamic
`range ofa single-precision floating-point numberisn't
`sufficient to store accurate geocentric coordinates. For
`example, the IEEE single-precision formatdefines a 23-
`bit mantissa. This providesa resolution of approximate-
`ly six digits (2°? = 8.39 x 10°). The earth's diameter is
`roughly 12,700,000m, and thus we can modelterrain to
`anaccuracy ofonly tens or hundredsof meters. This accu-
`racy can't even representtheresults froma civilian-grade
`Global Positioning System (GPS),let alonefaithfully rep-
`resent groundfeatures suchas buildings or roads.
`Most VRMLbrowsersuse only single-precision arith
`metic for modeling and matrix operations, and most
`moderngraphics hardware usesonly single precision.
`We must therefore implement accurate geocentric coor
`
`34
`
`March/April 1999
`
`Microsoft Corp. Exhibit 1010
`
`Microsoft Corp. Exhibit 1010
`
`

`

`
`
`What ShapeIs the Earth?
`In a computer graphics system,the simplest
`way to represent the earth is to produce a sphere
`and then apply toit a texture map. This method is
`adequatefor a coarse representation. However,if
`wewant to modelthe planet down to submeter
`accuracy, we must better understand the earth’s
`shape and the coordinate systemsthat describe
`it.
`
`Ellipsoids
`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-minoraxis (b), and
`the inverse flattening (1/f = a@/ (a—b)). Overthe
`past 200 years, many different referenceellipsoids
`have been formulated, each defining slightly
`different values for these variables. The current US
`Departmentof Defensestandard is defined by the
`World Geodetic System 1984 (WGS84), such that
`a= 6378137.0m and b= 6356752.3142m.
`
`Geoids
`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
`gravitationalfield. This complex, undulating
`surface varies marginally from the ellipsoid overa
`range of roughly 100m. Once again, there are
`several slightly different geoid standards, such as
`GEOID90, OSU89B, and WGS84,
`
`Datums
`A datum specifies a local or global reference
`coordinate system for defining points on the
`earth; these are called the horizontal datum and
`the vertical datum.
`The horizontal datum specifies the coordinate
`system used to localize points on the earth’s
`surface,It’s typically specified by a reference point
`on the planet, the azimuth of a line from that
`point, and a referenceellipsoid. Thereare literally
`hundreds of horizontal datums in common usage.
`Practically all of these are local in their extent, such
`as the Ordnance Survey GreatBritain 1936 datum
`or the Australian Geodetic 1984 datum. However,
`the WGS8é4defines a global datum thatis
`generally accepted as the most accurate definition
`