throbber
(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

This document is available on Docket Alarm but you must sign up to view it.


Or .

Accessing this document will incur an additional charge of $.

After purchase, you can access this document again without charge.

Accept $ Charge
throbber

Still Working On It

This document is taking longer than usual to download. This can happen if we need to contact the court directly to obtain the document and their servers are running slowly.

Give it another minute or two to complete, and then try the refresh button.

throbber

A few More Minutes ... Still Working

It can take up to 5 minutes for us to download a document if the court servers are running slowly.

Thank you for your continued patience.

This document could not be displayed.

We could not find this document within its docket. Please go back to the docket page and check the link. If that does not work, go back to the docket and refresh it to pull the newest information.

Your account does not support viewing this document.

You need a Paid Account to view this document. Click here to change your account type.

Your account does not support viewing this document.

Set your membership status to view this document.

With a Docket Alarm membership, you'll get a whole lot more, including:

  • Up-to-date information for this case.
  • Email alerts whenever there is an update.
  • Full text search for other cases.
  • Get email alerts whenever a new case matches your search.

Become a Member

One Moment Please

The filing “” is large (MB) and is being downloaded.

Please refresh this page in a few minutes to see if the filing has been downloaded. The filing will also be emailed to you when the download completes.

Your document is on its way!

If you do not receive the document in five minutes, contact support at support@docketalarm.com.

Sealed Document

We are unable to display this document, it may be under a court ordered seal.

If you have proper credentials to access the file, you may proceed directly to the court's system using your government issued username and password.


Access Government Site

We are redirecting you
to a mobile optimized page.





Document Unreadable or Corrupt

Refresh this Document
Go to the Docket

We are unable to display this document.

Refresh this Document
Go to the Docket