(12) United States Patent
`Levanon et al.
`
`(10) Patent No.:
`(45) Date of Patent:
`
`US 7,561,156 B2
`Jul. 14, 2009
`
`US007561156B2
`
`(54) ADAPTIVE QUADTREE-BASED SCALABLE
`SURFACE RENDERING
`
`e
`
`-
`
`-
`
`-
`
`- ... -
`
`52--> <- 3
`
`OTIl . . .
`
`- - -
`
`-
`(*) Notice:
`
`-
`(21) Appl. No.: 11/275,996
`(22) Filed:
`Feb. 8, 2006
`
`-
`
`:};
`
`3/1999 Johnson ...................... 345/419
`5,883,629 A
`1/2000 Castelli ..
`... 345/419
`6,014,671 A
`6/2000 Shu ........
`... 345/419
`6,075,538 A
`(75) Inventors: Isaac Levanon, Rannana (IL); Yonatan § º jº º - - - -
`- - - *::::::
`Lavi, Rannana (IL)
`6,373,489 B1
`4/2002 Lu .........
`... 345/428
`*
`*
`6,587,103 B1
`7/2003 Tucker ..........
`... 345/421
`(73) Assignee: INovo Limited, Anguilla, British West
`6,910,001 B2
`6/2005 Hammersley ..
`... 345/420
`Indies
`6,917,369 B2
`7/2005 Perry .....
`... 345/420
`-
`6,982,715 B2 * 1/2006 Isenburg ...........
`... 345/428
`-
`- -
`-
`Subject to any disclaimer, the term of this
`7,095,423 B2 * 8/2006 Cosman et al. ............. 345/629
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 246 days.
`OTHER PUBLICATIONS
`Lee et al., Navigating through Triangle Meshes Implemented as
`Linear Quadtrees, ACM Transactions on Graphics, vol. 10, No. 2,
`Apr. 2000, pp. 79-121.
`* cited by examiner
`Primary Examiner—Phu K Nguyen
`(74) Attorney, Agent, or Firm—DLA Piper LLP (US)
`(57)
`ABSTRACT
`
`(65)
`
`Prior Publication Data
`US 2007/0182734A1
`Aug. 9, 2007
`(51) Int. Cl.
`(2006.01)
`G06T I5/06)
`(52) U.S. Cl. ........................ 345/428; 345/423; 345/419
`(58) Field of Classification Search ................. 345/428,
`345/426–427, 419–420, 423
`See application file for complete search history.
`References Cited
`
`(56)
`
`|U.S. PATENT DOCUMENTS
`
`9/1987 Meagher ..................... 345/421
`4,694.404 A
`7/1990 Imao .......................... 382/240
`4,944,023 A
`9/1994 Finnigan ..................... 345/420
`5,345,490 A
`5,461,712 A 10/1995 Chelstowski ................ 345/543
`5,615,321 A
`3/1997 Corn .......................... 345/619
`
`A 3D scalable surface renderer allows efficient real-time 3D
`rendering of high-detail smooth surfaces. The renderer is
`exceptionally effective with software rendering and low-end
`weaker graphics accelerators, and provides excellent visible
`quality per the amount of polygons used, while retaining low
`CPU processing overhead and high efficiency on graphics
`hardware. The 3D scalable surface renderer provides real
`time rendering of extremely detailed smooth surfaces with
`view-dependent tessellation using an improved level of detail
`approach
`-
`
`18 Claims, 9 Drawing Sheets
`
`
`
`
`
`Server /
`Permanent
`Storage
`
`Streaming Module
`
`Fragment
`Request
`Production
`Module
`
`
`
`
`
`Client system
`
`Fragment Management Module
`
`Fragment Cache Cr?
`
`Surface Renderer
`
`-
`3D Rendering API Calls
`
`Graphics Display
`
`Native 3D Renderer
`
`Microsoft Corp. Exhibit 1025
`
`

`

`U.S. Patent
`
`Jul. 14, 2009
`
`Sheet 1 of 9
`
`US 7,561,156 B2
`
`D(N.Child[2])
`
`D(N.Child[3])
`
`D(N.Child[0])
`
`D(N.Child[1])
`
`D(N)
`
`FIGURE 1
`
`Section
`3
`
`Section
`0
`
`D(N)
`
`Section
`2
`
`Section
`1
`
`FIGURE 2
`
`y
`
`
`
`Microsoft Corp. Exhibit 1025
`
`

`

`U.S. Patent
`
`Jul. 14, 2009
`
`Sheet 2 of 9
`
`US 7,561,156 B2
`
`FIGURE 3a
`
`Microsoft Corp. Exhibit 1025
`
`

`

`U.S. Patent
`
`Jul. 14, 2009
`
`Sheet 3 of 9
`
`US 7,561,156 B2
`
`
`
`FIGURE 3b
`
`2
`s 2
`
`Z -
`
`Microsoft Corp. Exhibit 1025
`
`

`

`U.S. Patent
`
`Jul. 14, 2009
`
`Sheet 4 of 9
`
`US 7,561,156 B2
`
`
`
`Section 1
`
`FIGURE 4
`
`Microsoft Corp. Exhibit 1025
`
`

`

`U.S. Patent
`
`Jul. 14, 2009
`
`Sheet 5 of 9
`
`US 7,561,156 B2
`
`Child ()
`
`Child 1
`
`- - -
`
`
`
`Section 3
`
`- - -
`
`Displacement:
`(0, 1)
`
`Child 3
`
`- - -
`
`Child 1
`
`cºl
`Displacement:
`CO
`c
`(1, 0
`©
`3. Y 4– — "i. 3
`E
`3
`Displacement:
`c (-1 2 0)
`C/D
`
`Child 2
`
`- - -
`
`Child ()
`
`Displacement:
`(0, - 1)
`
`Section 1
`
`Child 2
`
`|
`
`Child 3
`
`FIGURE 5
`
`Microsoft Corp. Exhibit 1025
`
`

`

`U.S. Patent
`
`Jul. 14, 2009
`
`Sheet 6 of 9
`
`US 7,561,156 B2
`
`
`
`Iterator
`progress
`Vector
`
`Section 2
`
`Section 0
`
`------------------------------------------------------------------------------
`
`Fragment B
`
`Fragment A
`
`FIGURE 6
`
`Microsoft Corp. Exhibit 1025
`
`

`

`U.S. Patent
`
`Jul. 14, 2009
`
`Sheet 7 of 9
`
`US 7,561,156 B2
`
`ROOT NODE
`
`C
`
`PRI OR ART
`
`NOTE
`
`L
`
`º
`
`º
`
`I
`A fi
`
`º
`º
`
`[...]
`B i?
`
`-
`
`º
`A E
`
`II.
`C. A.W. C. C.
`
`LEAF
`
`I.
`
`º
`
`º
`
`AB A B A A/Acc B C D B B B E BMM BM
`
`º
`
`?º
`
`£ D D D
`
`A B A. A
`
`A A. A C
`
`B E B E B B E E
`
`FIGURE 7
`
`Microsoft Corp. Exhibit 1025
`
`

`

`U.S. Patent
`
`Jul. 14, 2009
`
`Sheet 8 of 9
`
`US 7,561,156 B2
`
`
`
`FIGURE 8
`
`Microsoft Corp. Exhibit 1025
`
`

`

`U.S. Patent
`
`Jul. 14, 2009
`
`Sheet 9 of 9
`
`US 7,561,156 B2
`
`
`
`
`
`Surface
`function
`Gs
`
`FIGURE 9a
`
`
`
`
`
`
`
`Server /
`Permanent
`Storage
`
`Fragment
`Request
`Production
`Module
`
`
`
`
`
`View
`Settings
`
`
`
`
`
`
`
`Surface
`Preprocessor
`
`Source
`quad-tree
`
`Server/
`Permanent
`Storage
`
`Streaming Module
`
`Streaming
`Requests
`
`Fragment Management Module
`
`Fragment Cache CFT
`
`Fragments
`
`Surface Rcndcrer
`
`
`
`
`
`3D Rendering API Calls
`
`
`
`
`
`-
`
`-
`
`Native 3D Rend
`
`FIGURE 9b
`
`Microsoft Corp. Exhibit 1025
`
`

`

`1
`ADAPTIVE QUADTREE-BASED SCALABLE
`SURFACE RENDERING
`
`2
`the data structure. In the four-branch tree structure, three
`nodes and a leaf branch out from a root node. The node is
`
`US 7,561,156 B2
`
`BACKGROUND OF THE INVENTION
`
`1. Field of the Invention
`
`The present invention relates to computer graphics. In par-
`ticular the invention relates to real
`time rendering of
`extremely detailed smooth surfaces with view-dependent tes-
`sellation using an improved level of detail approach. The
`invention utilizes a quad-tree map and geometric boundaries
`consisting of manifold non-self-intersecting surfaces.
`2. Description of the Related Art
`Swift advances in hardware, in particular faster, larger, and
`cheaper memories, have been transforming revolutionary
`approaches in computer graphics into reality. One typical
`example is the revolution of raster graphics that took place in
`the seventies, when hardware innovations enabled the transi-
`tion from vector graphics to raster graphics. Another example
`which has a similar potential is currently shaping up in the
`field of surface rendering of volumetric bodies. This trend is
`rooted in the extensive research and development effort in
`visual graphics in general and in applications using real-time
`surface visualization, such as video games, terrain imaged
`interactive road maps and topographical maps for the aero-
`space industry.
`Iso-surfacing algorithms can be classified as either view-
`dependent
`or
`view-independent.
`View-independent
`approaches in general generate geometry near the iso-surface.
`Most methods use triangles to approximate an iso-surface.
`The use of interval trees and the span space domain decom-
`position can greatly decrease the amount ofwork necessary to
`identify cells intersected by an iso-surface (also called active-
`cells), a major bottleneck in the extraction process. One
`advantage of generating geometry is that extraction need not
`be performed for each view. However, storing geometry
`becomes a burden as data resolution increases. View-depen-
`dent approaches focus on the resulting image and therefore
`attempt to perform computation mainly in regions that con-
`tribute substantially to the final
`image. View-dependent
`approaches are attractive in general as no intermediate form
`of the iso-surface needs to be stored explicitly, which greatly
`decreases storage requirements. One drawback of view-de-
`pendent approaches is that each time a new view is specified;
`the iso-surface extraction process must be repeated. For inter-
`active applications, where viewing parameters are being
`changed frequently, such methods perform a relatively large
`number of computations. View-dependent approaches often
`offer excellent image quality, but frequently no geometric
`representation of the iso-surface is generated, making them
`undesirable for use in geometric modeling applications, for
`example. Dual contouring methods were introduced to pre-
`serve sharp features and to alleviate storage requirements by
`reducing triangle count.
`Conventionally, a hierarchical data structure for describing
`an image, which is made up of a plurality of kinds of regions
`A, B, C, D and E, consists of a four or eight branch tree
`structure (so-called quad-trees and oct-trees). According to
`this system, the image is equally divided (decomposed) into
`four regions, and each region is recursively and equally sub-
`divided (decomposed) into four sub regions until each sub
`region is made up solely of a single kind ofregion. The image
`data storage efficiency of this method is satisfactory, and the
`method enables basic image processing in the data structure.
`In addition, the image can be described in levels of rough
`steps to fine steps. However, there is a problem in that the
`number of nodes increases especially at boundary portions of
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`indicated by a circular mark and corresponds to the region or
`sub region made up of two or more kinds of regions. On the
`other hand, the leaf is indicated by a black circular mark and
`corresponds to the region or sub region made up solely of a
`single kind of region.
`Frequently, objects (such as, for example, characters in a
`video game or terrain in a virtual roadmap) are generated
`using a so-called “base mesh” composed of a minimum num-
`ber of large polygons, and so provides a minimum level of
`rendering detail. The polygons forming the base mesh are
`normally referred to as “primitives”. These primitives are
`normally selected to enable the position and orientation ofthe
`object within a scene to be rapidly (and unambiguously)
`defined, and thereby facilitate appropriate scaling and anima-
`tion of the object.
`The process of defining polygons within a primitive is
`referred to as “tessellation”, and the number of polygons
`defined within a primitive is given by the “tessellation rate”.
`Formally, the tessellation rate is the number of segments into
`which an edge ofthe primitive is divided by the vertices ofthe
`polygons defined within the primitive. Thus, for example, a
`primitive has (by definition) a tessellation rate of 1. If one or
`more polygons are then defined within the primitive so one
`new vertex lies on each edge of the primitive (thereby divid-
`ing each edge into two segments), then the tessellation rate
`will become 2. Similarly, If other polygons are then defined
`within the primitive such that two vertices lie on each edge of
`the primitive (thereby dividing each edge into three seg-
`ments), then the tessellation rate will be 3. As may be appre-
`ciated, since the tessellation rate (or value) is based on the
`number of segments into which an edge of the primitive is
`divided, the tessellation rate can be defined on a “per-edge”
`basis. In principle, this means that different edges of a primi-
`tive may have the same, or different, tessellation values.
`In cases where a higher level of detail is required, addi-
`tional polygons can be defined within each primitive, as
`needed.
`
`There are a variety of existing methods that aim at reducing
`the amount of geometric primitives that are processed by the
`rendering pipeline proper. One general technique, called
`occlusion culling, operates by eliminating sections of the
`geometry that are invisible from the current view port (or
`from any of its immediate surrounding area or volume).
`Another technique uses several refinement levels for the
`geometry. Then the system renders only the crudest represen-
`tation of geometry that will result in less than a certain accept-
`able level of visible error when compared against an image
`rendered from the exact geometry. This approach is known as
`a “level-of-detail scheme” in the art. The present invention
`improves on this category, in particular utilizing the quad-
`tree-based subdivision approach. The present invention has
`considerably less requirements on the structure of the geom-
`etry than state-of-the-art methods based on this approach, yet
`still benefiting from its simplicity and efficiency. These
`weaker requirements allow the herein inventive method to use
`geometric representations that have significantly less geo-
`metric primitives than is typical. This means the system will
`have to render considerably less primitives in real time than is
`used by methods known in the art to achieve the same level of
`fidelity. The present
`invention advantages are especially
`prevalent when rendering such level of fidelity on limited
`computing devices in terms ofprocessing power and memory
`
`Microsoft Corp. Exhibit 1025
`
`Microsoft Corp. Exhibit 1025
`
`

`

`3
`allocation as well as when streaming the geometric primitives
`over limited bandwidth communication.
`
`US 7,561,156 B2
`
`SUMMARY OF THE INVENTION
`
`5
`
`10
`
`15
`
`20
`
`It is therefore an object of this invention to allow efficient
`real-time 3D rendering of high-detail smooth surfaces. Prop
`erly implemented, it is exceptionally effective with software
`renderers and low-end weaker graphics accelerators, and pro
`vides excellent visible quality per the amount of polygons
`used allowing high efficiency with graphics hardware, while
`retaining low CPU processing overhead. Additionally, it can
`be used under very restrictive memory requirements. This is
`useful for implementation on embedded devices such as, but
`not limited to, car navigation systems, personal digital assis
`tance devices, email communicators, mobile handsets, cellu
`lar, Volp. WiFi and WiMAX phones, and topographical GPS
`mapping for the aerospace industry as those are often very
`limited in available system RAM.
`The geometry the present invention renders consists of
`manifold, non-self-intersecting, surfaces. Each surface S
`must be the image of a piecewise smooth mapping Gs:D->R*,
`where D denotes the unit square in R*. The present invention
`renders the surfaces one at a time and there is not much
`interdependency between them, so hereafter the description
`25
`will focus mostly on the rendering of a single surface. Note
`that the underlying assumption is that the complexity of the
`dataset is in the mapping of G, themselves, and not that there
`are many different surfaces to be rendered.
`The method does not use the mappings Gs directly. Instead,
`30
`it uses a pre-computed data structure called a quadtree, com
`puted from Gs. The quadtree is a kind of tree data structure in
`which each node has up to four children nodes. Each node N
`has a domain in R* that will be denoted by D(N). The domain
`of the root node of the tree is the unit square. The domain of
`35
`the child nodes of an internal node N, as shown in FIG. 1, is
`given by dividing the domain of N (a square) into four equal
`squares, taking each of the four quadrants of the domain for
`each of the node’s four children.
`Each node N contains a polygonal approximation G(N) to
`the surface fragment Gs(D(N)). The invention is indifferent to
`the geometric error method used to determine the distance
`between G(N) and Gs(D(N)) and the logic used to decide the
`error tolerance or the complexity of the polygonal approxi
`mations. The complexity of G(N) is less than the complexity
`of the aggregate geometry of all of its children
`G(N.child[0 . . . 3]), so that it takes less computational effort
`to render G(N) rather than render the geometry of all of its
`children nodes. Hereafter the polygonal approximations
`G(N) are referred to as the geometry of the node N. Nodes N1,
`N., are called adjacent if the boundary of D(N1) and D(N2)
`intersect.
`The rendering algorithm renders the surface S by travers
`ing some portion of the quadtree and rendering only the
`geometry of terminal nodes of the traversal (i.e. leaf nodes, or
`such nodes that were traversed, but whose children nodes
`were not). The traversal either terminates at a node or enters
`all of its children nodes, meaning the aggregate domain of all
`terminal nodes covers the entire unit square without any over
`laps. The traversed portion is determined by several factors,
`such as visibility, and the visible error of the rendered geom
`etry G(N) compared to Gs(D(N)), taking into account the
`camera and display settings (camera position and orientation,
`view port, and display resolution).
`The geometry of each node must be a manifold mesh that is
`composed of triangles. Manifold meshes have exactly two
`faces connected to each interior edge. Each vertex v has a
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`4
`corresponding location v.loc in the domain, though its posi
`tion in 3D is not necessarily determined by Gs(v.loc.). It is also
`required that all boundary edges form a single closed loop, so
`that the topology of the mesh is disc-like, where only vertices
`located on the boundary of the domain connect to any bound
`ary edges, and the areas of all triangles in the domain are
`non-overlapping, meaning that for any location L in N(D)
`there is exactly one vertex, or one edge interior, or one triangle
`interior that contains L. Additionally, each triangle must have
`at most one boundary edge, and the boundary is divided to
`four sections that correspond to the four edges of the node’s
`domain. There must be at least one triangle connecting to each
`boundary section, so there are at least 4 triangles per node.
`The sections are indexed between 0 and 3 according to the
`order of enumeration as shown by FIG. 2. The geometry
`contained in adjacent nodes of equal depth needs to connect
`properly along the boundary (meaning, the meshes must have
`identical edges along their shared boundary, so that the union
`of the two meshes remains a manifold). However, if the
`depths of the nodes differ, it is required that the deeper node’s
`geometry will connect to all of the vertices that exist in the
`other node’s geometry on their shared boundary section. The
`algorithm produces modified versions of the shallower tile’s
`boundary geometry, so proper connectivity is retained in all
`cases. These requirements are illustrated in FIG. 3a and FIG.
`3b. If the geometry in each node satisfies all of the above
`requirements, it is declared fragment-compatible.
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`FIG. 1 shows the state of the art of a quad-tree division of
`a domain node into four equal child nodes
`FIG. 2 shows the domain node with adjacent numbered
`sections where a triangle attaches to each domain node
`FIG. 3a shows the results of the algorithm producing a
`modified version of shallower tiles boundary geometry
`FIG. 3b shows the results of the algorithm producing a
`modified version of shallower tiles boundary geometry
`FIG. 4 shows the first pass producing section adjacency
`trees for all fragments N and sections j so that Z(N.j) contains
`the set of all fragments that are adjacent to N along section j
`FIG. 5 shows the assignment of the displacement vector
`constants and the ordering of the adjacent child nodes to a
`particular section of a domain
`FIG. 6 shows how the vertices of each boundary section are
`imputed on the adjacent section so that each contains all of the
`vertices of the next deeper section
`FIG. 7 shows a quad-tree data structure with nodes and
`leafs
`FIG. 8 shows the subdivision of a node on a quad-tree
`data-structure
`FIG. 9a shows an overview of the preprocessing steps
`which produces the database used by the real time rendering
`system as input
`FIG. 9b shows an overview of the components of the real
`time rendering system
`DETAILED DESCRIPTION OF THE INVENTION
`
`The present invention renders surfaces one at a time and
`there is not much interdependency between them, so hereafter
`the description will focus mostly on the rendering of a single
`surface. As shown in FIG. 9a, the complexity of the dataset
`appears to be in the mapping of G, of the surface, however, the
`method does not use the mappings G, directly. Instead it uses
`a surface preprocessor and quad-tree structure to create a
`database from the input surface geometry. This can be stored
`for later use in any nonvolatile storage.
`
`Microsoft Corp. Exhibit 1025
`
`

`

`US 7,561,156 B2
`
`10
`
`15
`
`20
`
`5
`FIG. 9b depicts the run time component of the system
`where the real time rendering occurs. This is divided into a
`server side, and a client side. The server side of the system is
`only required to provide random access output from the data
`base created in the preprocessing step of FIG. 9a. The client
`side of the run time system of FIG. 9b takes view settings as
`input. These settings may come from any known input source
`including a user, a program, hardware and/or a database. The
`client side of the run time system then produces a sequence of
`3D rendering operations that, when applied by the 3D ren
`dering subsystem of the client side, displays an approxima
`tion to the appearance of the original surface geometry as seen
`based on the specified view settings.
`During the preprocessing of the surfacefunction G, a quad
`tree data structure is used. A quad-tree is a tree data structure
`in which each internal node has up to four children see FIG. 7.
`Quad-trees are most often used to partition a two dimensional
`space by recursively subdividing it into four quadrants, see
`FIG. 8. Some common uses of quad-trees are image repre
`sentation, spatial indexing, efficient collision detection in two
`dimensions, view frustum culling of terrain data, and storing
`sparse data, such as formatting information for a spreadsheet.
`Quad-trees are the two-dimensional analog of octrees. As
`shown in FIG. 7, a point region (PR) quad-tree is a type of
`quad-tree where each node (open circle) must have exactly
`four children, or leaf (darkened circles), having no children.
`The PR quad-tree represents a collection of data points in two
`dimensions by decomposing the region containing the data
`points into four equal quadrants, sub-quadrants, and so on
`until no leaf node contains more than a single point.
`Each node N has a domain in R* that will be denoted by
`D(N) as shown in FIG. 2. The domain of the root node of the
`tree is the unit square. The domain of the child nodes of an
`internal node N, as shown in FIG. 1, is given by dividing the
`domain of N (a square) into four equal squares, taking each of
`35
`the four quadrants of the domain for each of the node’s four
`children.
`Given a node N in a quadtree, its children nodes are iden
`tified by numerical indices between 0 and 3, using the nota
`tion N.child[x] to refer to the index x child of the node N.
`N.parent refers to N’s parent node in the tree and N.depth is
`defined as zero for the root node, and as N.parent.depth-1 for
`any other node. N.xo, N.yo are defined as zero for the root
`node, and recursively by:
`
`6
`threshold size Mºr, any newly created fragment produced
`replaces the least-recently-used leaf in the tree, which is
`detached from the quadtree and deleted from memory.
`Each source node N contains the following information:
`1. A set of vertices N.Vo, N.V1, ..., N.V. 1, also denoted by
`N.verts[0 . . . k-1]. Each vertex contains two components:
`The location of the vertex v inside the node’s domain ((x, y)
`within the unit square), termed v.loc, and its position in 3D
`world-space (termed v.pos), which usually corresponds to
`Gs(v.loc.). The local index of any vertex N.V. is defined as k.
`2. Five lists of triangles, one for all triangles connecting
`only to interior edges (termed N.T.int), and one list for each of
`the four boundary sections, each list containing all triangles
`that connect to the corresponding section (termed N.T.bd/x|,
`wherex is the index of the section). Note that only N.T.int can
`be empty, so there are at least 4 triangles in total. Typically,
`triangles are represented as triplets of local indices, so that
`each triplet (a, b, c) represents the triangle connecting (N.V.,.
`N.V., N.V.). For any such triangle list T we define TN to be
`the node containing T.
`3. A real number N.e equal to (or an upper bound of) the
`maximal value of |GMX)—Gs(x)|for all x in D(N), where
`GMX) is produced using linear interpolation between the
`values of v.pos for the vertices of the vertex, edge interior or
`triangle interior whose domain location contains x. Note that
`Gy is well-defined, continuous and piecewise linear. Frag
`ment geometry G(N) is usually, but not necessarily con
`structed with the goal of minimizing N.e and/or the number of
`triangles used.
`All cached fragments keep all of the information loaded
`from their corresponding source nodes in system memory,
`and additional information computed by the rendering sys
`tem. Fragments also store the values N.xo, N.yo and N.depth,
`as defined above. For convenience, we shall use the same
`mathematical symbol for fragments and their corresponding
`source nodes.
`The real time surface renderer (denoted by SR) is given
`information about camera positioning, orientation, field-of
`view angles, frustrum clipping settings and other related vari
`ables, collectively referred to as the current view settings,
`denoted by SR.V.S. Also, it has a visibility testing component
`annotated as SR.Vis. This is a predicate that takes as argu
`ments view settings (such as SR.VS) and a fragment to test,
`and must return FALSE only if the fragment’s geometry is
`entirely invisible from the given view settings, and TRUE
`otherwise. Note that false positives are allowed: it is accept
`able that in some cases this test will return TRUE even for
`fragments that are in fact invisible. The renderer does not
`depend upon this component for Hidden Surface Removal.
`SR.Vis(VS, N) can return FALSE if G(N) is entirely outside
`the field of view (also known as the viewing frustrum).
`Because false positives are allowed, the system can test a
`simpler 3D object whose volume contains G(N), such as a
`box, instead of G(N) itself, against the viewing frustrum,
`which reduces the computational cost of the test significantly.
`Also, additional visibility testing can be made using occlu
`sion culling algorithms that take geometry of other fragments
`(or other, unrelated objects that are rendered in addition to the
`surfaces handled by SR) as occluders. In some cases the
`aggregate occlusion of all such objects that appear before
`G(N) is sufficient to determine N as completely invisible. The
`present invention does not depend on the logic used in SR.Vis
`and considers it a black box mechanism.
`To render a surface, it traverses its fragment tree and pro
`duces a set of fragments SR.FS={N1, ..., N,) that are to be
`rendered in the current frame. All of these fragments are
`terminal nodes of the traversal, though they are not necessar
`
`25
`
`30
`
`40
`
`45
`
`50
`
`The real-time system has access to a quad-tree data struc
`ture, termed the source quadtree. It contains all data needed to
`represent the surface, and its nodes are termed source nodes.
`Note that this structure may be placed in secondary local
`55
`storage or a remote server, serialized and possibly com
`pressed in some way, arranged so that it is possible to effi
`ciently retrieve only the data belonging to any particular
`source node. The present invention is agnostic to the encoding
`of the data and compression methods used. Such data is
`streamed to memory based on current and predicted demand
`by the system. The system produces a memory-resident quad
`tree structure, termed the fragment tree, whose nodes are
`named fragments and are constructed using streamed data
`from the corresponding source nodes. To adhere to memory
`limitations, the fragments may be placed in a cache denoted
`by Crºz. As soon as the amount of cache entries reaches a
`
`65
`
`60
`
`Microsoft Corp. Exhibit 1025
`
`

`

`US 7,561,156 B2
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`7
`ily leaves in the fragment tree, and all fragments determined
`to be entirely invisible from the current view (by the compo
`ment SR.Vis) are not inserted to the set. The traversal is done
`recursively using a function SR.Scan that takes an argument
`fragment. Initially, it is invoked with the quadtree’s root frag
`ment, and SR.FS is assigned the empty set. SR.Scan termi
`nates at any given fragment Nunless the following conditions
`are met:
`1. N is not determined to be certainly invisible from the
`current view, that is, SR.Vis(SR.VS, N) returns TRUE.
`2. All of N’s four children fragments are valid and are
`connected to the quadtree structure. This condition is met as
`soon as the production of these fragments from source node
`data completes, and will cease to hold as soon as any such
`child is removed from the fragment cache Cºr.
`3. At least one of the following conditions is met:
`a. The visible error of the fragment’s geometry G(N) in
`respect to Gs(D(N)) from the current view is greater than the
`global constant SR.maxGE. The visible error N.ve is usually
`measured as the maximal distance ||P(W(Gy?z)))—P(W(Gs
`(x)))|for all x in D(N), where W maps positions in the 3D
`environment (world coordinates) to viewer-local coordinates
`(view coordinates) and P is the projection transform used to
`map view coordinates to the plane upon which the geometry
`is logically rendered. Coordinates on this plane correspond to
`position on the display surface linearly. N.ve is difficult to
`measure precisely and is usually approximated or bounded.
`One such possible approximation for N.ve is max(|P(N.e, 0.
`zºº)|, |P(0, N.e., zºº.)|), where zºº, is a lower bound on the
`value of W(GMX)).z for all x in D(N). Zºº, can be further
`approximated using min W(v).z for all v in the vertex set of a
`bounding box B whose volume contains GNOx). The present
`invention does not dependin particular upon these methods of
`approximation for N.ve or zº,.
`b. [Applies for texture-mapped surfaces only]: the mini
`mum mipmapping level across G(N) is negative. This value,
`denoted by L(N), typically corresponds to min log, JCP(W
`(x))/T(x))|.T(x) maps x from the domain D(N) to a coordinate
`in texture space of the texture used to draw the fragment N. T
`40
`is also scaled so that the coordinates of its image correspond
`to pixels on the texture being mapped. P(W(x)) is the position
`on the drawing plane, also scaled so that it the coordinates of
`its image correspond to pixels in the rendering target surface.
`Texture sampling filters (such as anisotropic filtering) and
`other global settings may have an effect on how L(N) should
`be evaluated. It is usually too computationally expensive to
`compute L(N) exactly and a lower bound on L(N) is used
`instead. The present invention does not depend upon the exact
`details of the computation or approximation of L(N).
`If the conditions are met, SR.ScanGN) calls itself recur
`sively on all of N’s children nodes.
`If SR.ScanGN) terminates for any reason other than (1), N
`is added to SR.F.S.
`55
`When the traversal completes, the set SR.FS has been
`determined.
`All members SR.FS are inserted to a queue called the
`geometry pool SR.G.P. Fragments that already queued are
`moved to the back of the queue. The vertices and triangle lists
`of the newly inserted fragments are loaded into the Vertex
`Array (denoted by SR.VA) and Source Index Array (denoted
`by SR.SIA). These global objects contain vertices and indices
`loaded from all currently queued fragments. The object
`SR.VA should preferably be a vertex array structure native to
`the 3D rendering subsystem. The present invention uses the
`following functions:
`
`50
`
`45
`
`60
`
`65
`
`8
`1. Function GetGlobal Index(fragment N, Integer localin
`dex) returns Integer: This function returns the global index of
`any vertex of a fragment N given its local index, assuming it
`is loaded to SR.S.I.A.
`2. Procedure InsertFragment(fragment N): places the
`world-space position of all of N’s vertices in the Vertex Array.
`The vertices may be placed in any order. Loads all triangle
`lists of N (N.T.int and N.T.bd/O .
`. . 3]) into SR.SIA. The
`system uses the GetGlobalindex function to translate the local
`indices given in any triangle list T of N into indices referring
`to the corresponding positions in the vertex array, so that
`triangles are given by triplets of indices into SR.VA. The
`result of this translation is called the global index list of T.
`denoted by T.GIL. The total amount of indices in T.GIL is
`denoted by T.GIL.Size.
`3. Function AddVertex(fragment N, vertex v) returns Inte
`ger: loads a new vertex, that does not appear in N.Vo . . . . .
`into SR.VA. New vertices are assigned local indices, starting
`from k, separately by each fragment. Additionally, they are
`immediately placed in the vertex array SR.VA and thus given
`a global index. They can only be removed fr