United States Patent
`Woods et al.
`
`[19]
`
`US005956039A
`[11] Patent Number:
`[45] Date of Patent:
`
`5,956,039
`Sep. 21, 1999
`
`[54] SYSTEM AND METHOD FOR INCREASING
`PERFORMANCE BY EFFICIENT USE OF
`LIMITED RESOURCES VIA INCREMENTAL
`FETCHING, LOADING AND UNLOADING
`OF DATA ASSETS OF THREE
`DIMENSIONAL WORLDS BASED ON
`TRANSIENT ASSET PRIORITIES
`
`[75] Inventors: Daniel J. Woods, Sunnyvale;
`Christopher F. Marrin, Fremont;
`Glenn C. Shute, Sunnyvale; David C.
`Mott, Mountain View, all of Calif.
`[73] Assignee: PLATINUM technology IP, Inc.,
`Oakbrook Terrace, Ill.
`
`James Kent, Silicon Graphics, Inc., VRML and WebSpace
`3D Navigation Interfaces for the World Wide Web, date
`unknown.
`John Rohlf and James Helman, “IRIS Performer: A High
`Performance Multiprocessing Toolkit for Real-Time 3D
`Graphics,” Computer Graphics Proceedings, Annual Con
`ference Series, 1994, pp. 381–394.
`Primary Examiner—Mark K. Zimmerman
`Assistant Examiner—Motilewa Good-Johnson
`Attorney, Agent, or Firm—Fish & Richardson P.C.
`[57]
`ABSTRACT
`A system and method for increasing the performance asso
`ciated with creating simulated 3D worlds from a network.
`The system and method provides a means for increasing the
`[21] Appl. No.: 08/900,471
`performance by fetching objects in the order of their impor
`tance. A priority scheme is used to determine the fetching,
`[22] Filed:
`Jul. 25, 1997
`pre-fetching, and caching of URLs. The operations of
`assigning priorities, making prefetch requests and cache
`[51] Int. Cl." … G06F 15/00
`management is driven by data in an asset database table. The
`[52] U.S. Cl. ............................................. 345/419; 345/421
`database contains information pertaining to each asset
`[58] Field of Search ...................................... 345/419, 421
`within the current scene such as the priority, status, region,
`type bounds, and retrieval time. The asset database table is
`[56]
`References Cited
`updated based on fetching activities, camera position, and
`the positions of moving assets. A world scene is subdivided
`into appropriately sized regions when a scene is first down
`loaded. Asset type origins are defined and moved, based on
`the position, orientation, and velocity of the camera.
`Regions are assigned priorities based on their distance from
`the asset origin. Assets within particular regions are assigned
`priorities based on the region priorities and the asset type.
`
`PUBLICATIONS
`Jean—Francis Balaguer and Enrico Gobbetti, Center for
`Advanced Studies, Research and Development in Sardinia,
`isd:A High-Speed 3D Web Browser (1995), 15 pages.
`Thomas A. Funkhouser and Carlo H. Séquin, “Adaptive
`Display Algorithm for Interactive Frame Rates During Visu
`alization of Complex Virtual Environments,” Computer
`Graphics Proceedings, Annual Conference Series, 1993, pp.
`247–254.
`
`33 Claims, 8 Drawing Sheets
`
`502
`
`
`
`1,3
`1,4
`Regions with
`priority = 3
`3
`Regions With priority 2
`
`Microsoft Corp. Exhibit 1003
`
`

`

`U.S. Patent
`
`Sep. 21, 1999
`
`Sheet 1 of 8
`
`5,956,039
`
`
`
`Click to explore 2-304
`eº
`2–305
`
`FIG. 3
`
`Microsoft Corp. Exhibit 1003
`
`

`

`U.S. Patent
`
`Sep. 21, 1999
`
`Sheet 2 of 8
`
`5,956,039
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`#VRML V2.0
`Group { Children |
`Inline {
`.
`
`bbOXSize 222
`bbOXCenter 000
`
`
`
`url "earth. Wrl"
`
`Anchor {
`Url"http://WWW.globe.com"
`deSCription "Globe home Dade"
`children I
`Transform {
`tranSlation 0 1.250
`Scale 0.025 0.025 0.025
`Children I
`Shape
`appearance Appearance {
`material Material {
`diffuseCO/Or 100
`
`}
`geometry
`Text {
`fontStyle FontStyle {
`Size 10
`justify "MIDDLE"
`
`}
`String "Click to explore"
`}
`
`}
`
`FIG. 2
`
`202
`204
`206
`208
`210
`212
`214
`216
`218
`220
`222
`224
`226
`228
`230
`232
`234
`236
`238
`240
`242
`244
`246
`248
`250
`252
`254
`256
`258
`260
`262
`264
`266
`268
`270
`272
`
`Microsoft Corp. Exhibit 1003
`
`

`

`U.S. Patent
`
`Sep. 21, 1999
`
`Sheet 3 of 8
`
`5,956,039
`
`401
`Building 1
`
`Building 2
`
`400
`
`403
`Building 3
`
`404
`
`405
`
`Inline
`B1. Wrl
`
`OutSide
`Texture
`
`408
`
`409
`
`Inline
`B2. Wrl
`
`OutSide
`Texture
`
`412
`
`413
`
`Inline
`B3. Wrl
`
`OutSide
`Texture
`
`406
`1St Floor
`Texture
`
`410
`1St Floor
`Texture
`
`414
`1St Floor
`Texture
`
`407
`
`411
`
`415
`
`2nd
`Floor
`Texture
`
`2nd
`FIOOr
`Texture
`
`2nd
`Floor
`Texture
`
`
`
`FIG. 4
`
`Microsoft Corp. Exhibit 1003
`
`

`

`U.S. Patent
`
`Sep. 21, 1999
`
`Sheet 4 of 8
`
`5,956,039
`
`502
`
`1,4:
`1,3
`Regions with
`priority = 3
`
`
`
`FIG. 5A
`
`1,4:
`1.3
`1.2:
`Regions with priority = 3
`
`Microsoft Corp. Exhibit 1003
`
`

`

`U.S. Patent
`
`Sep. 21, 1999
`
`Sheet 5 of 8
`
`5,956,039
`
`
`
`Regions with priority = 3
`
`... 3,4
`.
`Priority =
`
`edionS With priority =
`
`Microsoft Corp. Exhibit 1003
`
`

`

`U.S. Patent
`
`Sep. 21, 1999
`
`Sheet 6 of 8
`
`5,956,039
`
`602
`
`Determine the amens; of the World bounding
`OX
`
`604
`Create a grid of uniformally sized 3D regions
`COVering the World bounding box
`
`Determine initial location Of the Camera
`
`606
`
`608
`
`ASSign Priorities to regions for each asset type
`
`LOCate BaCh known asset and initialize aSSet
`database table
`
`610
`
`612
`Order (prioritize) assets for fetching based on types
`Of aSSets and regional priorities
`
`End
`
`FIG. 6
`
`Microsoft Corp. Exhibit 1003
`
`

`

`U.S. Patent
`
`Sep. 21, 1999
`
`Sheet 7 of 8
`
`5,956,039
`
`702
`
`
`
`Cro
`CC)
`
`3 .S.
`
`c
`
`s
`§
`
`701
`
`O O O O O O O O O
`O
`O
`O
`O
`O
`O
`o ProCeSSOr|o
`O
`O
`O
`O O O O O O O O O
`
`706
`
`(T) wºnºmoy
`
`Secondary Memory 708
`
`
`
`
`
`
`
`Hard Disk Drive
`
`º 710
`714
`712
`Removable
`Storage
`Removable Storage –
`Unit
`drive
`720
`1 Removable
`Storage
`Unit
`722
`
`Interface
`
`724
`Communication
`Interface
`
`726
`
`728
`
`FIG. 7
`
`Microsoft Corp. Exhibit 1003
`
`

`

`U.S. Patent
`
`Sep. 21, 1999
`
`Sheet 8 of 8
`
`5,956,039
`
`802
`Determine 5 assets with highest
`priority and load 4 active and
`1 Waiting request queues
`
`Begin fetching 4 assets from
`active queue
`simultaneously
`
`
`
`
`
`
`
`Any Active fetch
`g
`COmplete
`
`808
`Move queue element from Waiting
`queue to Active queue and begin
`fetching new asset
`
`Locate next asset with highest
`priority and put in
`Waiting queue
`
`812
`
`More aSSets
`2
`
`FIG. 8
`
`
`
`
`
`
`
`
`
`
`
`
`
`Microsoft Corp. Exhibit 1003
`
`

`

`5,956,039
`
`10
`
`15
`
`20
`
`25
`
`1
`SYSTEM AND METHOD FOR INCREASING
`PERFORMANCE BY EFFICIENT USE OF
`LIMITED RESOURCES VIA INCREMENTAL
`FETCHING, LOADING AND UNLOADING
`OF DATA ASSETS OF THREE
`DIMENSIONAL WORLDS BASED ON
`TRANSIENT ASSET PRIORITIES
`BACKGROUND OF THE INVENTION
`1. Field of the Invention
`The present invention relates generally to 3D modeling
`systems and more specifically to an intelligent system and
`method for increasing performance by the efficient use of
`limited resources via incremental fetching, loading and
`unloading of data assets of three-dimensional worlds based
`on transient asset priorities.
`2. Related Art
`In just a few short years since its emergence on the
`Internet, the worldwide web (WWW) has revolutionized the
`way many people communicate with each other and interact
`with commercial, governmental and educational entities.
`Before the emergence of the world wide web, the Internet
`was predominantly used by governmental, scientific and
`academic communities. Since the introduction of the world
`wide web however, the Internet has experienced unprec
`edented growth and has become a cultural phenomenon that
`is used on a regular basis by mainstream populations
`throughout the world.
`The Internet has been transformed from a cryptic com
`mand line, text-based environment into a user-friendly,
`30
`easily navigable ‘cyber space’ filled with colorful graphical
`images, high quality sounds and full motion video. Anyone
`can navigate through the world wide web by simply pointing
`and clicking with a mouse or other pointing device, such as
`a trackball, touchpad, touch screen or electronic pen. This
`transformation has lead to an abundance of new Internet
`subscribers and Internet providers.
`The transformation of the Internet has been accomplished
`for the most part through the use of a standard markup
`language used by Internet sites known as the hypertext
`markup language (HTML). HTML provides a unified inter
`face to text and multimedia data. HTML provides a means
`for anyone with a text editor to create colorful ‘web pages’
`which can be viewed by Internet subscribers around the
`world. HTML sites are viewed through the use of a tool
`known as a browser which enables one to explore the
`contents of databases located throughout the world without
`needing to be concerned about the details of the data format.
`Browsers download and interpret the HTML provided by
`each Web site and display them as ‘pages’ on a local display
`50
`device, such as a computer monitor or the like. Each HTML
`page can contain text, graphics and hypertext links to other
`HTML pages. Each page has a unique Internet address
`which is referred to as a Uniform Resource Locator (URL).
`Thus, when a user clicks on a hypertext link a new URL
`55
`is fetched by the browser and downloaded to the user’s
`workstation. Typically, the previous web page is replaced by
`a new web page that is defined by the HTML provided by
`the new URL. Generally hypertext links are depicted as
`underlined or highlighted words, depending on the brows
`er’s implementation of displaying of HTML. Hypertext
`links can also appear as buttons or other graphical images.
`In addition, in most browsers, the shape of the cursor
`changes when the pointer passes over a hypertext linked
`screen object. For example, a cursor having the shape of an
`arrow may change into the shape of a hand when passing
`over a hypertext link.
`
`2
`Each HTML page can have an arbitrary length. For
`example, consider a WWW site that provides a selection of
`Shakespeare’s plays. The first page of the website may
`comprise a list of all available plays. Each element in the list
`comprises a URL link to one of Shakespeare’s plays. The list
`may be scrolled vertically or horizontally by the user,
`depending on the implementation of the HTML as provided
`by the web page author. When a user selects a play by
`clicking the mouse button on a list item, a new HTML page
`is downloaded from the URL and the list is replaced with a
`representation of the selected play.
`The selected play may be represented in a variety of ways
`by the web page author. For example, the entire play can be
`represented by a single URL as one long scrollable web
`page. Alternatively, each page of the play can be represented
`by a different URL, in which case a different set of HTML
`links will be included at the bottom of each page providing
`a link to the next or previous pages, for example. In other
`implementations, a web page author may choose to repre
`sent each scene or act in the play as a single URL or web
`page.
`Each time a new web page is loaded, a new HTML
`document must be downloaded or fetched by the browser.
`The amount of time it takes to fetch each new web page
`depends on the size of the new web page and the complexity
`of the content contained therein.
`A new description language which promises to further
`revolutionize the WWW has recently appeared on the Inter
`net. This new language is called virtual reality modeling
`language (VRML). VRML documents are used to create
`three dimensional (3D) infinitely scalable, virtual worlds on
`the Web. The goal of these worlds is to provide a convincing
`illusion of a 3D environment that visitors may explore.
`Similar to the way HTML operates, VRML documents are
`downloaded from VRML web sites into local host computer
`systems by VRML browsers. The VRML browsers interpret
`the scene (also referred to herein as a ‘world’ or ‘model’)
`that is described by the VRML file and renders the resulting
`images on the local display device. 3D rendering is per
`formed from the viewpoint of a virtual camera that has the
`ability to move and tilt in any direction in response to user
`input, via a mouse, keyboard or other input device. In
`addition, objects within the 3D world can be examined and
`manipulated by a user. Further, like HTML, VRML docu
`ments can provide links to other VRML worlds and/or
`HTML Web pages through the use of URL links.
`The use of VRML enables Internet users to navigate
`through three dimensional worlds in real-time. 3D environ
`ments are being used to augment the information gathering
`experience of Internet users. For example, a user can navi
`gate through the streets of a city and hyper link to a
`particular company’s home web page by clicking on the
`company’s building site. Other examples include on-line
`virtual shopping, museum browsing, entertainment and cor
`porate briefing centers. VRML also allows users to experi
`ence worlds that have no physical counterpart and are not
`constrained by physical restrictions due to size, location,
`time, or safety. Such worlds need not even obey the laws of
`physics that govern our everyday lives.
`Although the use of VRML represents a major break
`through on several levels, many problems are still to be
`overcome. Many of the problems that are encountered are
`related to the requirement of real-time performance. Fetch
`ing and rendering 3D data is very time consuming due to the
`volume of data that needs to be downloaded into the local
`computer system, and the computational power required to
`
`35
`
`40
`
`45
`
`60
`
`65
`
`Microsoft Corp. Exhibit 1003
`
`

`

`25
`
`3
`render the 3D images. Thus, performance problems are
`primarily due to two limiting factors, namely the bandwidth
`of the Internet connection and the limited resources and
`processing power of the local computer system.
`For example, limited resources of the local computer
`system include general purpose random access memory,
`video card memory, sound card memory and disk caches.
`The network itself can also be considered a limited resource.
`Each limited resource has a particular access time associated
`with it. The access time is the amount of time it takes to
`retrieve the data from the limited resource and send it to the
`appropriate place to be presented to the user.
`In general, access times for sound and video card memory
`are very low. This is followed by general purpose memory,
`which is followed by disk cache memory. Typically the
`network itself is the source of the greatest access time.
`Today, most Internet connections are accomplished via
`analog telephone lines using commercial-off-the-shelf
`modems. Such modems typically operate at speeds of up to
`28,000 bits per second. This limited bandwidth makes it
`difficult to download the vast amount of information needed
`to render 3D worlds in a real-time fashion. Even the fastest
`Internet connections, such as those implemented using
`ISDN lines, which provide Internet connection speeds of up
`to 144,000 bits per second, are generally not fast enough to
`alleviate the bottleneck problems due to limited bandwidth.
`Using conventional methods, a clever VRML author may
`attempt to organize the VRML document so that certain
`objects that are considered more important are downloaded
`30
`before other objects. Conventionally, URLs within VRML
`documents are processed in the order in which they are
`written. That is, URLs that are located at the top of the
`VRML file are downloaded before URLs that are located at
`the bottom.
`Thus, a VRML author may attempt to increase the per
`formance of the 3D world by optimally arranging the order
`of URLs contained in the VRML file. However, due to the
`nature of 3D worlds, this task is almost impossible. Prob
`lems arise because it is very difficult to predict the way users
`will interact with the 3D world. Users are free to move in
`any direction, change viewing angles and movement speeds.
`Further, users are free to click on close or distant objects in
`an arbitrary fashion. Thus, because so many variables are
`possible, the conventional method does not provide a means
`to optimally pre-order the URLs to affect the fetching to
`increase the performance of the 3D world.
`SUMMARY OF THE INVENTION
`Accordingly, the present invention is directed toward a
`system and method for increasing performance by the effi
`cient use of limited resources via incremental fetching,
`loading and unloading of data assets of three-dimensional
`worlds based on transient asset priorities. The present inven
`tion increases the performance by fetching objects in the
`order of their importance. A priority scheme is used to
`determine the fetching, pre-fetching, and caching of data
`assets. The operations of assigning priorities, making
`prefetch requests and cache management are driven by data
`in an asset table. Preferably the asset table is implemented
`with a database. The database contains information pertain
`ing to each asset within the current scene such as the priority,
`status, region, type bounds, and retrieval time. Asset types
`include sound, inlines, movies, images, anchors, behavior,
`background, images and scripts.
`The asset table is updated based on fetching activities,
`camera position, and the positions of moving assets. A
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`5,956,039
`
`10
`
`15
`
`20
`
`4
`current scene is subdivided into appropriately sized regions
`when a scene is downloaded by an implementation of the
`present invention. An asset origin is defined for each asset
`type. An asset is assigned a priority based the region
`priorities and the value of an asset type offset. The asset table
`is updated based on changes to the camera's position. In
`addition, preferably, the asset table is updated when a fetch
`request is complete, or an asset leaves or enters a region.
`Information contained in the asset table is used to assign
`and update fetching priorities. In addition to the position of
`assets, asset bounds are considered when determining pri
`ority. For example, if a sound has a range that extends into
`every region in the world, then the sound asset will likely
`have a high priority.
`One advantage of the present invention is that it provides
`increased performance associated with creating 3D worlds
`from a network by fetching objects that are most important
`to the user as quickly as possible.
`Another advantage of the present invention is that the
`unloading of low priority assets enables the browsing of an
`infinitely large world by effective use of finite resources.
`
`BRIEF DESCRIPTION OF THE FIGURES
`The present invention will be described with reference to
`the accompanying drawings, wherein:
`FIG. 1 is a block diagram depicting an operational envi
`ronment according to a preferred embodiment of the present
`invention;
`FIG. 2 is a block diagram of a VRML file that can be used
`with an implementation of the present invention;
`FIG. 3 is a diagram depicting the rendering of the VRML
`of FIG. 2 as would be displayed on a computer terminal;
`FIG. 4 is a block diagram useful for describing the
`prioritizing principles according to the present invention;
`FIGS. 5A-5D represents a two dimensional example
`useful for describing the 3D process of prioritizing assets
`according to the present invention;
`FIG. 6 and FIG. 8 are flowcharts depicting processes
`according to two embodiments of the present invention; and
`FIG. 7 is a block diagram of a computer system that can
`be used to implement the present invention.
`In the drawings, like reference numbers generally indicate
`identical, functionally similar, and/or structurally similar
`elements. The drawing in which an element first appears is
`indicated by the leftmost digit(s) in the reference number.
`DETAILED DESCRIPTION OF THE
`PREFERRED EMBODIMENTS
`The present invention is directed towards a system and
`method increasing the performance associated with creating
`simulated 3D worlds from a network, such as the Internet.
`The present invention provides at least two major enhance
`ments to conventional fetching methods. First, the present
`invention determines a priority for data, so that the most
`important data is fetched first (i.e. that data which is most
`likely perceived). Second, the present invention provides the
`ability to unload data from memory or other cache storage
`levels, when such data is not longer perceivable.
`In order to fully describe the features of the present
`invention, a discussion of the standardized VRML language
`is presented below. For the purposes of this disclosure, a
`discussion of VRML 1.0 is presented. However, it should be
`apparent to those skilled in the relevant arts, that the
`principles of the present invention can be applied to all
`
`Microsoft Corp. Exhibit 1003
`
`

`

`5,956,039
`
`10
`
`15
`
`20
`
`30
`
`35
`
`25
`
`5
`current and future versions of VRML and other graphic
`modeling languages. As such, the examples used herein
`should not be construed to limit the scope and breadth of the
`present invention.
`VRML is based on Silicon Graphics’ Open Inventor
`ASCII file format and provides a means for describing 3D
`worlds using plain text. Typically however, VRML worlds
`are created with graphical content creation tools, which
`isolates VRML authors from having to learn the syntax and
`format of the VRML language. However, in order to better
`understand the optimization techniques provided by the
`present invention, a brief discussion of VRML in terms of its
`syntax, and the interaction between the server and client is
`presented below.
`As used in this example, the term server refers to the host
`computer system that provides 3D world descriptions in the
`form of VRML data files. The term client refers to a user’s
`local computer system that is running a web browser which
`downloads and interprets the VRML data files from the host
`computer system over a computer network, such as the
`Internet. As stated, other modeling languages can be used
`with the present invention and VRML is used herein only for
`exemplary purposes. The 3D worlds are rendered by the
`client on a local display device. An example of a web server
`and client is depicted in FIG. 1.
`FIG. 1 depicts an Internet web server and client in a
`typical environment according to an embodiment of the
`present invention. The server 102 is connected to a network,
`such as the Internet 110, via the transmission line 108, such
`as a T1 transmission link, or other communication medium.
`In this example, the client 116 is connected to the Internet
`110 via a standard telephone line 114, which is coupled with
`a modem 120. The modem 120 is coupled with the client
`computer system via the serial cable 122. Typically, the data
`transfer capacity of the client is lower than the data transfer
`capacity of the server. For example, a typical Internet
`connection is accomplished with the use of a modem that
`transfers data at a rate of 28,800 bits per second.
`Descriptions of 3D worlds are provided by the server 102
`via VRML data files, such as the data file 104. The VRML
`40
`data file 104 is fetched, or downloaded from the server 102
`to the client 116, as depicted by the arrows 106 and 112
`respectively. The client 116 then interprets the VRML data
`file using a browser program which renders the 3D world
`118 on the video screen 124 of the client computer system
`116. The VRML data file 104 may, in turn, refer to additional
`data stored on the server 102, or any other device (not
`shown) coupled to the network 110.
`VRML models are defined as a collection of nodes that
`are arranged in a hierarchical tree structure called a scene
`graph. Attributes of the model, such as geometry and color
`are described by property nodes. For example, the Sphere
`node denotes a spherical object, and the Transform node can
`cause objects that appear after it to be translated, rotated,
`and/or scaled by a specific amount. Detailed descriptions of
`the VRML 1.0 specification and the concepts upon which it
`is based can be found in the following publications: M.
`Pesce, G. Bell, and A. Parisi, VRML 1.0 specification,
`http://vrml.wired.com/vrml.tech/vrml103.html, 1995; M.
`Pesce, VRML Browsing and Building Cyberspace, New
`Riders Publishing, Indianapolis, 1995; and J. Wernecke, The
`Inventor Mentor, Addison-Wesley, Reading, Mass. 1994.
`Detailed descriptions of the VRML 2.0 specification can be
`found in Carey, Rikk, Chris Marrin and Gavin Bell, The
`Virtual Reality Modeling Language Specification: Version
`2.0, ISO/IEC CD 14472, Aug. 4, 1996, also available as
`http://vrml.sgi.com/moving-worlds/spec/index.html.
`
`45
`
`50
`
`55
`
`60
`
`65
`
`6
`Nodes may inherit properties from other nodes that appear
`above them in the scene graph. Such ordering is important
`because nodes defined earlier in a scene can affect nodes that
`appear later in the scene. For example, a Transform or
`Material node can affect the nodes that appear after it.
`VRML uses a Cartesian, right-handed, 3-dimensional
`coordinate system. By default, objects are projected onto a
`2-dimensional device by projecting them in the direction of
`the positive Z axis, with the positive X axis to the right and
`the positive Y axis up. A camera or modeling transformation
`may be used to alter this default projection. The standard
`unit for lengths and distances specified is meters and the
`standard unit for angles is radians. By default, the camera,
`which determines the viewpoint of the user, is located at
`(0,0,10) and looks along the negative z-axis.
`The present invention provides optimization techniques
`for fetching and caching assets. Such assets may be defined
`for example, in an Inline node. Inline nodes typically contain
`references to other scene graphs that are referred to as the
`children of the Inline node. An Inline node can read its
`children from anywhere in the world wide web. Further, the
`children of a Inline node often contain additional children.
`A node called a level of detail (LOD) node also uses the
`child-parent hierarchy. This group node is used to allow
`applications to switch between various representations of
`objects automatically. The children of LOD nodes typically
`represent the same object or objects at varying levels of
`detail, from highest detail to lowest. Thus, when the camera
`is far away from an object, there is no need to render the
`object with the highest level of detail. However as the
`observer moves closer to the object, the next level of detail
`is rendered to represent the object. The VRML author
`specifies, in a ranges array, the distances from the object
`which corresponds to each particular level of detail.
`The Anchor group node loads a new scene into a VRML
`browser when one of its children is selected by the user. The
`method used to select a child of an Anchor depends on the
`implementation of the VRML browser. However, this is
`typically accomplished by clicking on one of its children
`with the mouse. This will result in the new scene replacing
`the current scene.
`Various types of Texture nodes are provided by VRML.
`Each of these property nodes defines a texture map and
`parameters for that map. This map is used to apply texture
`to geometric shapes after they are rendered. A Pixel Texture
`node contains the texture data within its definition and the
`other texture nodes refer to URLs form which textures can
`be obtained.
`An example of a scene graph that depicts some of the
`concepts described above is shown in FIG. 2. In this
`example, a VRML 2.0 file is depicted that defines a 3D
`model of the earth with the words “Click to explore” above
`it. FIG. 3 shows an example of how this 3D model may look
`when rendered on a local display device, such as the display
`device 116.
`Referring to FIG. 2, the first line 202 identifies this file as
`a VRML 2.0 data file. Line 206 is the beginning of a Inline
`node that ends with the curly brace in line 214. The Lines
`210 and 212 define a boxed shape boundary that defines the
`bounding box within the current world in which the child
`scene graph is confined. This boundary is depicted by the
`dotted line 305 shown in FIG. 3. Note that the dotted line
`305 is not visible, but forms the boundary for the objects
`defined by the child scene graph. Line 208 contains a URL
`which is identifies the child scene graph as “earth.wrl”.
`Thus, the file “earth.wrl” is another VRML file (not shown)
`
`Microsoft Corp. Exhibit 1003
`
`

`

`15
`
`7
`that describes and models the picture of the earth 302, as
`shown in FIG. 3.
`The remaining lines of the VRML file 102, serve to
`complete the world scene as shown in FIG. 3. For example,
`line 216 contains an Anchor node. Anchor nodes are used to
`create links between objects in the scene and other world
`wide web content. Such other content can be other VRML
`scenes, HTML web pages etc. In this example, the words
`“Click to explore” are linked to the ‘globes’ HTML web
`page. Thus, clicking on any of the letters in the text will
`10
`cause this page to be fetched and displayed in an HTML
`browser window.
`FIG. 4 is a block diagram useful for describing the
`prioritizing principles according to the present invention. In
`this example, assume that a simple 3D world consists of 3
`two-story buildings 401, 402, and 403. Each of the 3
`buildings are modeled using four assets located in four
`separate files, each identified by unique URLs. For example,
`building 1 is modeled using an Inline asset 404 representing
`the building’s geometry, and three texture assets. The texture
`assets 405, 406 and 407 represent the outside, first floor and
`second floor textures, respectively. The other two buildings
`402 and 404 are modeled in a similar fashion. That is,
`building 2 is modeled using an Inline asset 408 and three
`texture assets 409, 410 and 411. Similarly, building 3 is
`modeled using an Inline asset 412 and three texture assets
`413, 414 and 415.
`Using traditional methods, assets in the VRML file 400
`are fetched in the order in which they are encountered. In
`this example, it is assumed that the VRML file 400 is
`organized such that a description for building 1 is followed
`by a description for building 2, which is followed by a
`description for building 3. Thus, using traditional methods,
`URLs are fetched in the order shown in table 414. That is,
`the URLs are fetched in the following order: 404, 405, 406,
`407, 408, 409, 410, 411, 412, 413, 414, and 415.
`Hence, using traditional methods, all of the assets that
`represent building 1 are fetched before the assets represent
`ing buildings 2 or 3. Generally this will cause building 1 to
`be displayed before buildings 2 and 3. Further, valuable time
`is spent fetching images which are not immediately rendered
`because they are not visible to the user. In this example, the
`textures within the interior space of building 1, such as the
`first and second floor textures 406 and 407, are not visible
`while the camera is located outside of the buildings. Thus,
`fetching such textures before they are needed is wasteful and
`causes a decreased perception of performance.
`Accordingly, using the example above, it would be pref
`erable to fetch the outside geometries 404, 408 and 412 of
`the buildings 1, 2 and 3, before fetching any of the texture
`assets. This is because, a user will be able to interact with the
`geometries of all three buildings very quickly. For example,
`even before the outside building textures are rendered, a user
`can move around the buildings, or move closer or further
`away from a particular building.
`After the geometries are fetched, it would be preferable to
`fetch the outside textures of the buildings 1, 2, and 3, before
`fetching any of the inside textures. This is so, because the
`inside textures are not visible to the user from the outside of
`the buildings. Finally, because a user must generally enter a
`building from the first floor, it would be preferable to fetch
`the textures for the first floors 406, 410, and 414, before
`fetching the textures for the second floors 407,411,415. The
`table 416 in FIG. 4, shows an ordered list of the assets that
`are prioritized according to the principles described above.
`It is important to note that priority list 416 depends on the
`position of the camera. In this case, it is assumed that the
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`5,956,039
`
`20
`
`25
`
`30
`
`35
`
`8
`camera is located outside of the three buildings. If a user
`moves the camera, the ordered list 416 may no longer be
`optimal. For example, if the user moves the camera inside of
`building 1401, suddenly the first and second floor textures
`406–407 of building 1 become more important than any of
`the remaining unfetched assets. Accordingly, as described
`below, the present invention prioritizes assets based on the
`p