Microsoft et al. Exhibit 1010
`
`

`
`AN!)
`
`.1tPl-‘Ut‘c.rl JrtJ~.~‘.
`
`IEEE Computer Society
`10662 Los Vaqueros Circle, PO Box 3014
`Los Alamitos, CA 90720
`llttp:/'/eomputenorg/cga
`
`Editor in Chief
`Jatrtes J, Tltornns
`Pacific Northwest National Lttlmratory
`902 Battelle Boulevard
`Richlartcl, WA 99352
`Jin1.Ti10rnas@pI1I.gov
`
`Bllllnlissinnst Please Submit seven copies of all articles to
`Alkenln Winston, magazine assistant, IEEIE. C-C.Impu_lc|' society,
`10662 L05 Vaqueros Circle. Los Alamitos, CA 90720. Submit
`proposals for special issues to Michael Rhodes,
`|nl'l10dE5@ndSlIS-jnj.com. All submissions are stlhject to editing
`for style, clarity, and space consideration,-:. mt authm-‘s guide it.-
`available from the Web. publications office, or by e-mail from
`awinston@comput'ct'.org.
`
`Associate Editors in Chief
`Michael L. Rhodes
`Ortho lliagnostic Systems
`Tumer Whittetl
`Microsoft
`
`Editorial Board
`
`Frank W. Bliss
`John C. Dill
`Rae A. fiarnshaw
`José l... Erica rnacfio
`Andrew Glassnor
`Markus Gross
`Bertram Herzog
`Tosiyasu L. Kunii
`Carl Macltover
`Gregory M. Nielson
`Michael J. Potel
`Theresa-Marie Rhyne
`Lawrence J. Roserthlunt
`Maureen Stone
`
`[-LD5/GM Corp.
`Simon l'-'raser University
`University of Bradford
`‘Technical Uttivcr.-my of lJarmstatlt
`Microsoft
`l’.'|'l I. Zurich
`Uttiversity of Michigan
`llosei University
`lv1acl1oveI'J\ssocizues
`Arizetta State University
`Wiltlcresl Associates
`Locltlteed Martin
`Naval Research I.al)ot'atot"y
`Stcmesoup Consulting
`
`Managing Editor Nancy i-lays
`Assistant Editor Robin l3-altlwiu
`Editorial Assistant Kristine Kelly
`Magazine Assistant Alkeuia Winston
`Art Direction Joe Dalglc
`
`Publisher Matt Loch
`Advertising Manager Patricia Garvey
`Advertising Supervisor Marian Attdersun
`Advertising Coordinator Debbie Sluts
`Mernber/Circ. Promo Mgr. Georgaun Carter
`
`Publications Board
`
`Benjamin Walt (Vice President‘).
`GI-ll Rain! {MOC chair), Jon Butler {TOC t:hair).
`Ron Williams [IEEE Pttlzts Representative),
`Jake A-ggarwal. Alberto tlci Bimbo, Mike Lia, Zltiwei Xu
`
`Magazine Operations Cornmittee
`
`CI-1!'lCl1Em3 (chair). William Everett (vice chair],
`James H. Ayior, Jean Bacon, Wushnw Chou, George Cybettlto,
`William I. Grosl<y, Steve McConnell, Daniel E. O‘l.eaty.
`Ken Sakamttra, Mttnindar P. Singh, James J. 'l“homas,
`Yervant Zuriart
`
`Editorial: IEEE Compttl't.'l' Gl'tTllfift'$ and Applications selves bollt
`users and designers of graphics ltardwate, snE'tware, and ,-:y,«;ten15,
`its readers work in industry, business, the arts, anti ttnivctsitiesl
`Articles are peer-reviewed; departments are refer-ced, Unless
`otherwise stated, bylined articles and cleparttrtcnts. as well as
`i-l95fi'iPli0n$ Di Products and Services. reflect the atttltor's or firnfs
`Opinion: inclusion in this publication docs ttot necessarily
`constitute endorsement by the IEEE or the Computer Society,
`
`Copyright and reprint permission: Abstracting is permitted
`with credit to the source. Libraries are peI'rnitted to photocopy
`beyond the limits of US copyright law for private use of patrotts
`those articles that cat1'y a code at the bottom of the first page,
`proviclecl the per-copy fee indicated in the code is paid through the
`Cnplnisht Clearance Center. 29 Congress St., Salem, MA 0197-‘O.
`instructors are permitted to photocopy isolated articles for
`noncommercial classroom use without fee. For other copying,
`reprint, or republication pcrutission, write to Copyrights and
`Permissions Department, IEEE Publications Administ-ration, 445
`Hoes Lane, P.0. Box 1331, Piscataway, NJ 08355-1331. All riglus
`reserved. Copyright CD 1999 by the Institute of Electrical and
`Electronics Engineers, Inc
`
`Cirtnllaliont FEEE CUn1putcI' Gt'ttpht't's amiApplt'ctttt'ons (ISSN 0272-
`1716] is published bimonthly by the IEEE Cotttputer Society.
`Il?.l_-‘,|_-',
`Headquarters: Three Parl-t Avc., 17th Floor, New York, NY 100] 6-
`5997. IEEE Computer Society HuadqLIttrtet‘s: 1730 Massacltttselts
`Ave., Washington, DC 20036-1903. ll7.l'-Ci,-', (‘.on1pul'c|' Society
`l‘-‘ulialications Office: 10662 Lot»: Vaqttcrns Circle. PO Box 3014, Les
`Alalnitns. CA 90720: (T14) S21-B380. Annual subscription: $34 in
`addition to any IEEE group or society dues. Members of other
`technical organi:=.at'ions: $90. Noutttetnber sttbscript-inn rates are
`available on request. Back issues: mcnthets, S10; nonmt.-mbct's. $20.
`This journal is also available in I‘t'lic1‘Dfir_'hefut‘mttnrl on the web.
`
`Postmaster: Send address changes and undelivered copies to
`IEEE Conlp1Jtet‘G'fItpitirs and /1,-Iplltratiotts. IEIEE 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 #125(:34138, Canada Post
`International Publications Mail Prtatluct [Canacli:m Dls[|'il_',-|,ll_iun]
`Sales Agreement #0487848. Printed in USA.
`
`Moving?
`PLEASE. NOTIFY Mail to
`US 4 WEEKS
`IEEE Computer Society
`IN ADVANCE
`10662 Los Vaqueros Circle
`PO Box 3014
`Los Alamltos, CA 90720
`I This notice oi address change will apply to all IEEE pulztlitalions to
`which you subscribe.
`0 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
`
`Name (please print)
`
`New address
`
`City
`
`Statefcountry
`
`Microsoft et a1. Exhibit 1010
`
`Microsoft et al. Exhibit 1010
`
`

`
`Céifin uferGra hiE':s
`
`AND APPLICATIONS
`
`Articles
`
`VRM L
`
`1 7
`
`Guest Edltor’s Introduction:
`
`Virtual Reality Modeling Language
`Maureen Stone
`
`Tutorial: Building Virtual Worlds
`1 8 with VRML
`David R. Nodenn
`
`VRML makes it easy to create virtual worlds. This
`tutot'ial reviews VRML‘s syntax and features as well
`as its world construction and animation abilities.
`
`3
`
`Terravision ll: Visualizing Massive
`Terrain Databases in VRML
`Martin Rcdtly, Yvttn Lcclerc, Lee lverson,
`and Nat Bletter
`
`To disseminate 3D maps and spatial data over the
`Web, the authors designed massive terrain data sets
`accessible through either a VRML browser or the cus
`tomized Terravision 1] browser.
`
`Large-Scale Mine Visualization
`Using VRML
`Keith Russ Cil'1t'iAn(lJ'l3W Wetltereli
`
`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 of data visualization.
`
`“Bottom, Thou Art Translated":
`45 The Making ofVRML Dream
`Stephen N. Mfltsttbn and Bernie Roclll
`Bringing virtual theater to the Web requires 3D
`graphics, efficient networking, and strong content.
`The authors discuss the VRML Dream Project, a real-
`time Internet performance.
`
`March/April 1999
`Volume 19 Number 2
`
`Published by the IEEE Computer Society
`
`Developing the VRML 97
`International Standard
`
`George S. C.'tn'son, Ricl'itn‘d F. Pttlt, and
`Rilck C.'t1i'c_y
`VRML 97 arose from a cooperative effort between the
`standards and VRML. cornmunities. The methodology
`employed applies equally well to development of
`future standards.
`
`5
`
`VRML Testing: Making VRMLWor|ds
`Look the Same Everywhere
`Mary Brady. Alden Dime, Len Gcbase,
`Michael Kass, Carnviela Montancs-Rivet't1.
`and Lynne Rosentltcti
`NIST tools address problems posed by testing 3D
`graphics. This article explains the test development
`strategy and design issues in developing and deliver-
`ing l2i'li3SE testing tools.
`
`6 A Framework for Streaming Geometry
`in VRML
`Andre Guéziec, Gabriel '?'aubin, Bill Horn,
`and Fraitcis Lazctrus‘
`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.
`
`79
`
`Dynamics Modeling and Culling
`Stephen Cltenney. Jeffreyicltnowski, and
`David Forsyth
`The tools described permit including large nu nilrners
`of complex dynamic models in a VRML world easily
`
`littp://computemrg/cgaf
`
`ISSN 0272-1716
`
`Microsoft et al. Exhibit 1010
`
`Microsoft et al. Exhibit 1010
`
`

`
`Microsoft et al. 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 Reddy, Yvan Leclere, Lee lversun,
`and Nat Blett-er
`SR1 Irate:-nrttitmei
`
`t'loniains,' and VRML oi'l'ei‘s cai't0gi‘n[)liei'.s and geogra-
`phers the potential to disseminate 31) maps and spatial
`data over ihe World Wideweh. l-iowever, to date we have
`not seen useful large-scale VRML gilogi'iipl]l|J(ltilt'll3E1SE5.
`We aim to enable vistialiaatioii of item‘ plioi'rireali.siic
`3D models oftei'i'niii that can be on the order ofhun—
`drcds of gigaiiytes. This might incl tide different types of
`terrain il'nagcry For particular regions, as well as site
`models and auxiliar_v ini'oi'inatioI1forgrouncl l3EiElli'ES.
`The following scenario indicates the capabilities M
`required. Say it user wants to Find a piu'ticular building r
`in a pa1'l'iCi.1l:-ii‘ city. l' le1'_ioti1'ncyl'1egll1Swith fl 3D model
`|
`oi’ the eilI'l'li viewed ilroni space. This model is texlure-
`’
`mapped with satellite imagery of 100 l{ilUn1€i't“.i'fi
`reso-
`i
`iution—that is, each pixel in the tcxttire map repicselits
`2] region on the pl.’-inel's surface L'0Vl.3l'liig 100 ltin”. To l
`hail the city. the user lirsi rotates ihe earth to view the if‘I
`
`'
`
`i i
`
`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.‘ They did this using standard US Geological
`Survey (USGS) 7.5 arc 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 races course over the VRML terrain.
`
`
`ll
`'3
`7
`
`References
`
`1. K. Moore, "Interactive Virtual Environments for Field-
`work," Brihsh Cartographic Society Annual Symp., 1997:
`available at http:/fwwvitgeog.le.ac.uI</mek/\firiEnv.him.
`2. M. Abernathy and 5. Shaw, "Integrating Geographic
`Information in VRML Models," Proc. Third Syrnp.
`VRML, ACM New York, 1998, pp. 107-114.
`
`Microsoft et a1.
`
`Exhibit 10 10
`tl,'-!?2- i Il'lLi,“}9r'ilCl.OD 3) iii!-1'! IEEE
`
`To disseminate 3D maps and
`
`spatial data over the Web,
`
`we designed massive terrain
`
`Researc]iei‘s have in-
`creasingly ttnnecl
`to
`Virtual Reality Modeling Language
`(VltMi..]
`to 1'epi‘eSelil geographic
`information. In VRMi..'s early da_v5_.
`the rcstlll; was i-1 few toy exaniples
`that
`tlid not scale well, such as
`eoai'se. single-iesolutioii elevation
`grids. Today, VRML is drawing more
`serioiis intei'e.'_it from rcscarcl1ei‘s
`across the S1.'I@CIl'|.l!n, including geo-
`gtaplieizs, Cartogi‘ap1ie1's, geologists.
`and computer scientists, as the side-
`bar “Related Worlt" describes. As
`’l"hei'esa-Marie Rliyne noted, geo-
`gtapiiie information system (G13) and scientific visi.ial-
`iention tools have begun to expand into each oiher's
`
`data sets accessible through
`
`either a VRML browser or
`
`the customized Terravision
`
`ll browser.
`
`
`
`Related Work
`Currently, interesting and significant work
`addresses the problem of representing geographic
`data in VRML. In the earth sciences, Kate Moore
`described the worit of the Virtual Field Course
`(vrc) 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 gee-referenced data to enhance
`students‘ cognition of the real environment.
`The US Naval Postgraduate School is currently
`working on a project to develop a 3D model of the
`Monterrey 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.
`
`30
`
`Marchi'Apri| ‘I999
`
`
`
`Microsoft et al. Exhibit 1010
`
`

`
`t.-it-get region in there detail. As she zooms into the
`region. higher resolution data, such as elevation and
`imagery, are progressively downloaded anti displayed
`uliril she is "liyittg" over mountains with imagery down
`to one-meter resolution. Over certain parts of the ter-
`rain. alternative itnageries are available, such as aerial
`photographs; the user cart select any image to view on
`top of the terrain geometry. As she approaches a built-
`up area, 3D models of buildings come into view. Wlten
`the ttser clicks on at bu ilding, information abottt it is dis-
`played in a separate l'rame on the browser. Using this
`method, the user locates the target building. Through.-
`out the navigation, the user’s location is clisplayed via
`an active map interface that provides a context for the
`la nclscape being viewed.
`In setting ottt to achieve such capabilities, we identi-
`fied four principal design criteria:
`
`I .*it‘ttlt'titiiiiy. Our design must scale to very large data
`sets. Clottttnottly, a geographic data set consists of
`many millions of polygons anti many gigabytes of
`it1‘taget'y.
`
`I Cotttposnbiiity. Our data representation tnttst allow
`the introduction of Imlltlple types of gee-referenced
`data. inclutling additional itnagery_. site models. cul-
`tural features. and annotations. it also must let the
`ttser switch between these on demand.
`
`I i-.f[l’t't‘ictrt:_v. Users must be able to nttvigate the VRML
`structures easily and efficiently using a standard
`\-'l1Mi. browser or a custoniizecl browser that i'urtltet.'
`ittcreases lJI'owsing efl1cit2Iit.‘y.
`I Dotti itttettliaitge. We mttst tlevelop gt'.'I1t-.‘l'ic data 1'ep—
`reseutations for geo-rei'crenced tla ta in Viilvli.. 'i‘his
`will let other geographic data providers produce data
`using the same represetttation.
`
`Guided by these requirements. we iinplententetl this
`functionality in a stantlartl VRML browser for down-
`loading data over the World Wide Web. We also devel-
`oped a custom terrain visualization package called
`'l‘er'raVision ii that can browse these VRML data struc-
`titres. Althouglt not required to view the content.
`Tet ravision it lets the user perform specia lized browser-
`level optimizations that offer increasetl efficiottcy anti
`seamless interaction wit It the terrain data.
`
`We deslgttetl our l1'am£!w0l‘lt to simplify terrain data
`maintenance and to let users dyttan-tically select particu-
`liii sets ofgeo-t'elle1'encet| data. Our irttplcmettlaiiott uses
`Java scripting to etttetttl VRML’s base functionality and
`the i£xLerttalAuthoring interface to otTer application-spa
`triitc maitagetneut oi‘ the virtual geographic environment.
`to help develop standard techniques For solving geo-
`graphical representation problems in VRML. coauthor
`Lee lverson i'ormetl and currently chairs the GeoVRMi.
`group. an oiTicial Working Group oftlte Web3D Consor-
`titttn (http://www.ai.sri.eom/geovrrnl). As a service to
`the VRMI. COll'lii‘illl'lli.'_\t'E1liCl the Ge-o'v'li'MLell“ot'l, we have
`In.-ttle frceiyavailable both the'l‘erruVision ll browser and
`all oithe tools we developed For generating VRMI. terrain
`rlata sets. This includes the source code to all of our cus-
`iont VRML nodes and the t'sntApi library that we use to
`8Eltt:|'at'e the VRML data sets. The library is describecl in
`
`the sidebar “'i'i-re tsn1Api Library" and is available along
`with other niaterials and several example VRML data sets
`at http://Www.ai.5I'i.com/'1et't't1Visiort.
`
`Multlresolutlon terrain techniques
`'i‘c-train 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.
`i-"reducing a simple polygonal representation of a single
`DEM creates a model with more than 1.4 million poly-
`gons. The titne required to download and render such a
`model would prohibitany real-o‘tne interaction using the
`current generation of VRML browsers.
`it therefore
`becomes essential to tnanage level of detail (LCD).
`LCD leL‘l'Init1LtES change a model's complexity brtsecl
`on some selection criteria, such as distance from the
`viewpoint or projected screen size. 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 ntechanistn to
`simplify a data set‘s gcotnet ty and imagery.
`Several polygon simplification algorithms work well
`for terrain. However. litany ofthese a re view-intlepen-
`rlent techniques that force the so the degree of simplifi-
`cation across
`the entire terrnitt.“‘*‘
`']'hese
`are
`
`The tsnmpl Library
`The ‘File Set Manager Application Program
`interface (tsmfitpi) 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 tsmfitpi library, 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 SR|'s fully re-entrant VRML 9? parser,
`which can be used to parse VRML 97 files
`efficiently into memory and to write these
`Structures back out to a VRML 97 file. Other
`functions-perform transformations between
`various geographic coordinate systems, such as
`Unlveral Transverse Mercator (UTMJ, geodetic
`(latitude/longitude), and earth-fixed geocentric.
`based on code from the US National Imagery
`and Mapping Agency's Nimamuse product.
`Precompiled tsmApi distributions are available
`for Iris, Solaris. Linux, and other platforms. In
`addition, the full C source code is available from
`the tsrnfitpi home page. which also includes full
`API documentation, tutorials, format
`specifications. and example source code. The
`t.tl'nApi Web page is at l1l:ip:!fwvvw.ai.sri.com/
`tsmApi.
`
`IEEE Computer Graphics and Applications
`
`Microsoft et a1. Exhibit 1010
`31
`
`Microsoft et al. 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 nr. 128 pixel
`tiles, and
`(in) how this
`structure can be
`used to alter the
`
`image resolu-
`tion In different
`regions.
`
`
`
`inappropriate for our app] ieat ion because swittzhing to
`the highest resolution still involves loading every point
`of the original data set. instead, we require a view-
`dependent tet'.‘.l'ilil('|LlE that lets us vary the degree ol'sim-
`pllfication with respect to the c.'urrent viewpt':ittt.'”' This
`is often done using a hierarchical data str'ucntre, such
`as a t]t1ad-tree. Furtlter, the LOD algorltlnn Inttst not
`t'et]ui1'e access to the entire high-resolution version of
`the tiara set, as that would iitnit us to viewing only tiata
`sets that can fit on the tt:-:cI"s local storage system. Given
`tliese t‘et]ttircments, a tiled, pyramitl t'ept'eserttation
`best stilts our neetls.“'”
`
`A pyramid is at ittultiresolutioit hierarchy for a tlatfl
`set. For exanipie, ifthe original image is "1024 >< 1024
`pixels, then the pyrantitl might contain the original
`image along with tlown-sa tnpled versions at resolutions
`0l"5l2 X 512 pixels, 256 X 256 pixels, 128 X128 pixels,
`and so on. As Figure la shows, each pyrarnirl image is
`then segmented into rectangular tiles. where all tiles
`have the same pixel tiirnenslons. A tile at a given pyra-
`mitl level will thus map ortto 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 poly-
`gons) than
`tlistant terrain.
`
`
`
`32
`
`March./April 1999
`
`or level; that is, at each higher resolution area, the tiles
`cover half the geo3l'op]'tlcal area oflhe previous level.
`Using this t'epI'esel‘ttatloit, we can rcr_'t1rsively resolve
`certain tiara set regions in tnore tlctail than other
`regions. For example, Figure lb shows the lower-right
`corner in high resoltttion with the snrrtrtutding regions
`displayed in progressively lower resolution. Asstrinitrg
`a tile size of 128 x 128 pixels, this example requires
`ciownloatling and rendering only 491 Kliytes (it) tiles)
`instead oi’ the entire 3.1-iVihyl'e higlt-resolution image.
`if the user's location is the bottom-right corner, then dis-
`tant imagery is renclerecl at lower resolution than near
`itnagcry and we have achieve-tl tlistancc-bttsetl LOD,
`As Figure 2 shows, our image pyramids tecitniqucs
`can be applied to elevation grids and other types oF ter-
`rain data. Bccattse we use a tiled pyramid representa-
`lion for the geometry and the irnagery, we can optitnize
`the amount ofclala transferrecl over the networlt, the
`number oi’ polygons in the scene, and the amount of
`mentory t‘et'|ttlt'ecl lo1'textLtre maps. As a 1‘est1lt, we need
`only Fetch and display tiara for the region that the user
`is viewing, anti only at a sufficient resolution i'or the
`user's viewpoint. This solution scales well to arbitrarily
`large tiara sets because it eflet‘i'ively attempts to keep
`the polygon count constant for any viewpoint.
`
`Multlresolutlon data in VRMI.
`We introclttce four types oF‘JItMi.. files to represent It
`large, tiled ntultiresolution iiierarciiy of the globe: ter-
`rain tile files, feature Files, geotile Tiles, and tree files.
`Figure 3 shows these files and their relatiohsltlps. The
`tree files recursively ittiplement the LOD l1iet'arcl1y by
`llilining a single geolile file at one LOD anti Four higher
`resolution tree files at the next L01). The geotile file
`lnlines all of the lizature anti tt3l't'airt tiles that t'.ovet‘a
`
`geogt‘apl1ical area and LOD. A terrain tile file contains
`the actual elevation anti iittttge texture tiala for El given
`image, geograpitical area. and LCD. 1'«'eature files
`tlescribc a geogi'a]'il1lcal arctfs objects, such as buildings ‘
`and roatls. We discuss these t'el:-ttionsltips anti their
`atlvttntages below.
`
`Microsoft et al. Exhibit 1010
`
`
`
`Microsoft et al. Exhibit 1010
`
`

`
`
`
`A tree lilo
`
`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
`lnllne links to files over the network.
`Bold rectangles delineate file
`boundaries.
`
`Tree files
`
`nee files implement part of the rnttlti resolution hier-
`archy for the entire globe. in effect. these files are the
`glue that holds the geotiles in the quad-tree strttetttre. A
`tree file initially loads a single geotile, but when the user
`approaelres the tile, it‘s replaced with four liiglrer—1'eso-
`ltrtion tree files, which in turn inline the geotiles for tire
`torrrquad-tr'ee children. (At the bottom level of the tree
`bierarclty, the four geotiles are inlined directly.) The
`lrierarehy of tree files must be generated only once and
`won’t generally need to be modified further—ei-zeept
`|‘tC't'l1flp5 1'0 errtentl the tree For higher‘ resolutions at a
`later j uncrure. In the futtu-e, it mightbe possible to gen~
`erate tree files on the Fly.
`The tree files let trs split the entire LOD lrier'arehy over
`rtrrrltiple files and abstract the [DD strtrcttrre from the
`actual terrain data. They also let us create tr dil't'erer1t
`l..ClD tree depth Fo1‘tlilTer'e1tt global r'egions. For t.E2|r'.£-lll‘l'
`ple, we could have 100-km-resolution data for the
`entire globe but recursively insert higher resolution
`data for smaller regions of interest, such as a one-lun-
`resolution data set for the center-ruinous United States
`
`and a one-m-resolution data set for Yosemite Valley,
`Cjrrlifornia.
`
`It would be possible to use the VRMI, Inl ine node
`to irrelttdc the geolile files into the Lot) hierarel1_v. How-
`ever, VRML 97 does not specify when the Universal
`Resortrce Lorsator (URL) ofan Inl ine node slroultl be
`loaded, riinkirtg thisa br‘owse1'-depencl.er'rt Feattrr'e. Cut’-
`rentl_v. most browsers load all inline scenes at once. This
`makes good sense for‘st'nttll5eer1es with a handful of
`Inline nodes. However, if we have :1 data Set‘ of 10
`U bytes, the VRML browser will trttentpt to load all these
`data into memor_v at once. This is oliviotrsly unaccept-
`able f'ot'ot1r' application, so we turret rgmttrol when inline
`files are loaded and ti nloatled. To do this, we developed
`
`rising VRML 97's
`a new node. called Quadmo,
`EXTERNPROTO aI‘rt'l 3t'r'iptirrg l'eattIr'es. Quadhob pro-
`vides :1 terrain-speciiir.‘ LOD ctrrirahility that efiicierttly
`manages the loading and unloading of higher levels oi’
`detail. When the user enters a certain volume around
`the tile (deter'ntined by a Proximi tyoensor) Quad-
`LOD loads only a tile’s liotrr higher resoltrrlort children.
`The nodealso uses :1 tile-caching mechanism so that tiles
`aren't needlessly reloaded. When the user approaeltes :1
`region ot'ter'1'airr. more detail is progressively loaded and
`displayed in a coarse-to-t'ine fasltion. Most VRME.
`browsers perform nonblot-king network reads so that
`the user can still interact with the scene while higher
`resolution imagery and elevation loads.
`
`Gentile flies
`
`Geotile files contain links to all data within a single
`tile. The most basic gentile includes a single terrain tile
`File for the region. However, it's possible fora gentile to
`store litil-is to mtrltiple alternative ler‘r'air1 tiles, strclr as
`tiles r'efer'rir1g to satellite. aerial. and map imagery, as
`well as feattl I13 files for objects that exist on the terrain,
`Such as btrildings, roads. and annotations.
`By adding this extra layer to t)tr1'glol:Ial strtrcture, we
`simplify the task ot'n1aint'air1ing and adding new data
`sets. For example, when we want to add :1 new image
`pyramid, we can generate the terrain tiles in isolation
`anti simply link them to appropriate georiles. tlftlte new
`data set 1'Qt|tlil't'.‘5 higher resoltrlzion than the region pre-
`viously required, we also mrrslt generate new tree files.)
`In aclclition, beerruse eaclr data set is stored indepen-
`dently and r'efe1'erreec'l only via the geotiles, we can selec-
`tively display any eornbinarion ol' data sets. A node we
`created, GeoTi la, permits this selectivity by ot'ganlz~
`ing the terrain tile and feature file links into sets of
`switch nodes.
`
`Microsoft et al.
`
`Exhibit 1010
`33
`
`IEEE Cornprrter Graphics and Applications
`
`
`
`Microsoft et al. Exhibit 1010
`
`

`
`VRMI.
`
`‘-' rm H-at-iv Irv rwt.-i-.-.-
`
`4 A tiled terrain
`model showing
`geoweferenced
`3D geometry
`overlaid for
`
`roads (orange)
`and buildings
`(yellow).
`
`Terrain tile files
`Terrain tiles contain the actual terrain data for a sin-
`
`gle data set tile at a particttlar detail level. This includes
`the elevation geometry and the texture map irnagery for
`the specific terrain tile. The VRML 97‘ specification pro-
`vides us with two potential primitives for representing
`terrain geometry: the Int'1axot':lFo.ooSeit:
`and the
`E1 evationtsr id. The latter node lets the user specify
`a grid of height values above rhex-s plane, whereas the
`more general IndexedFaeeSe:t: node lets the user
`define ai'biti‘aI‘y polygons in 3D space. VRML 9"/"s Ele-
`vat:ionGrid was introdticetl specifically to represent
`terrain motiels and offers a compact mecitanistn to
`describe Simple height field tiara. However, it has serious
`limitations that prevent us from using it, including that
`it assumes that the lteiglits are relative to a flat planc—
`an obvious problem when deali ng with cu1'ved planets.
`Elevoti onorida 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
`Inn:1oxec1FaceSet to build terrain geometry.
`
`Feature files
`Feature files contain vntv1t.modeIs for objects relat-
`ed to a region of terrain. F.-‘ocanipies include a t'egion's
`cultural feartt res, such as roads and lines 0fC01i1l11tli1i-
`cation; weather Simulations, such as clear air turbulence
`isosttrfaces and wind vectors; and other 3D tiara, such
`as terrain annotations.
`
`iy within that tile. Aiiotiienztiltltion is to simply inclttde
`t‘-1 linl-t to the same featttrc in all relevant geolilesr We
`selected the latter approach because it does not con-
`strain the cI.ill'ural i'catLires to the Slime l'C‘5l'Jll.il.'ltJll range
`as the te1't'ain, and it requires no modification to the fea-
`t'tire's geometry. However. one problem is that the
`browser would normally load, store, and render dupli-
`cate copies of each feature for every loaded gentile in
`whicli it occurs. To avoid this, we have designed our
`Geo'1‘i1e node so that it lteeps tracl-t ofeach request for
`a feature file'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 t'efet'ence cottnt
`returns to zero. Figure 4 shows the ftision of terrain data
`and cultural features that results.
`
`Geographic coordinate systems
`VRML defines a Cartesian coottlitiate system for motl-
`cling objects in a 3D volume. In geographic terms, this
`gives us a geoccnttic representation: a coordinate [.\‘,_V,
`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 or projective coordinate system.
`A geodetic coordinate system is related to the ellipsoid
`used to model the earth (such as the iatittttie-longitude
`system). A projective coordinate system projects the
`ellipsoid onto sortie simple StlI'fElC'E, such as a cone or a
`cylinder‘. Examples include the I..an1hert Conformal
`Conic or the UniversalTransverse Mercatorprojections.
`Such coordinate systems were designed for diiterent
`applications and offer particular advantages anti restric-
`tions. For eitatnplc, some projections can represent only
`small-scale regions; others are conformal, offering the
`same scale in every direction; and others can be equal
`area—the projected at‘ea corresponds to the earth‘s
`physical area over the entire projection. in use data in
`these different coordinate systems, we must convert
`coordinates in these systems into the VRML geocet'itI‘iC
`coordinate system. Descriptions for performing many
`of these transi'ormations are available elsewhere.” The
`sidebar “What Shape is the Eat'tl1?"tli5L‘ttsfte£i related
`represent'at'ioi't Cliallenges.
`
`F|oating—point precision Issues
`The VRML 9'? specification defines the St-‘Float and
`Mi-‘ioat fields to represent floating-point nmnhers. Howv
`over, these are only single-p1'ccision values; the dynamic
`range of ti single-precision fiozit'i1'tg-point 11tn11|Jerisn't
`sufficient to sto1'e accurate gcocentric coordinates. For
`example, the IEEE single-precision format defines a 23-
`bit n1antissa.'l‘i1is provides a rcsoitition of approximate-
`ly six digits (213 = 3.39 x 10"). The earth’s diameter is
`roughly 12,7tlt)_.t)tltJm, and thus we can model terrain to
`an accu racy ollonly tens or ituntlretis ofrncters. This at'Ctl-
`racy can't even represent the results from a civiliatt-gi'ade
`Global Positioning System (GPS), let alone fail hfully rcp~
`resent ground features such as buildings or roads.
`it/lostVR.Ml. browsers use only single-precision arith-
`metic for modeling and ntatriit operations, and most
`modern graphics hardware uses only single precision.
`We must therefore implement accurate geocentric coor-
`
`Microsoft et a1. Exhibit 1010
`
`
`
`integrating terrain features proves tlifficult because
`features can eittencl beyond tile bottntlaries. For exam-
`plc, a road might cover multiple tiles, or a large building
`might sit on the boundary between two tiles. One way
`to deal with this prolJieI'n is to dissect the geometry for
`all ground features along tile boundaries, forcing the
`condition that all feattires in a tile are contained entire-
`
`March/April 1999
`
`Microsoft et al. 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
`sh1a_3pe and the coordinate systems that describe
`it.
`
`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 (ca), the semi-minor axis (is), and
`the inverse flattening (1/f= of (a — b)). 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 (WGS84), such that
`o = 63781 37.0rn and D = 6356752.3142m.
`
`Genlds
`
`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 relat