US20120154399A1

US20120154399A1 - Hierarchical Bounding of Displaced Parametric Surfaces

Info

Publication number: US20120154399A1
Application number: US13/400,911
Authority: US
Inventors: Jacob Munkberg; Jon Hasselgren; Robert Toth; Tomas Akenine-Möller
Original assignee: Individual
Current assignee: Individual
Priority date: 2010-04-07
Filing date: 2012-02-21
Publication date: 2012-06-21
Also published as: JP2011238213A; US20110248997A1; GB2479461A; US8144147B2; TWI443602B; GB201105960D0; CN102214369B; JP5111638B2; GB2479461B; TW201205500A; DE102011016347A1; CN102214369A

Abstract

Hierarchical bounding of displaced parametric surfaces may be a very common use case for tessellation in interactive and real-time rendering. An efficient normal bounding technique may be used, together with min-max mipmap hierarchies and oriented bounding boxes. This provides substantially faster convergence for the bounding volumes of the displaced surface, without tessellating and displacing the surface in some embodiments. This bounding technique can be used for different types of culling, ray tracing, and to sort higher order primitives in tiling architectures.

Description

CROSS-REFERENCE TO RELATED APPLICATIONS

This application is a continuation of U.S. patent application Ser. No. 12/755,506, filed on Apr. 7, 2010.

BACKGROUND

This relates generally to graphics processing and, particularly, to tessellation in rendering systems, such as interactive, real time, and off-line/film rendering.
Modern graphics processors contain dedicated hardware for tessellating surfaces into many small triangles. The DirectX 11 application programming interface (“DX11”) (API) adds three new stages to the graphics pipeline to support tessellation: the hull shader, the fixed-function tessellator and the domain shader. The hull shader is executed once per patch and once per control point, typically to compute tessellation factors and change control point bases. The fixed-function tessellator takes tessellation factors as inputs and generates a large set of vertex positions in the domain of the input primitive and connectivity information between vertices. The connectivity information forms many small triangles. The domain shader is executed once per generated vertex position from the tessellator. A typical domain shader usage is evaluating the position and normal of a parametric surface, using, for example, a set of control points, barycentric coordinates, and a detailed texture as inputs. The output is a displaced vertex defined by a set of attributes. One attribute is the position, but the shader also can compute the normal/tangent/bi-tangent/texture coordinate/color/transparency or other attribute of the displaced vertex.

BRIEF DESCRIPTION OF THE DRAWINGS

FIG. 1 is a graph showing the corner control points and the vectors b and t; by forming vectors between the corners of the patch, the OBB axes can be derived;

FIG. 2 shows an example of the resulting bounds after 25 steps of bounding a cubic polynomial with two discrete displacement peaks on the upper row, the images on the left using AABBs and the images on the right using OBBs, whose axes are determined by control points of the Bézier curve, while the lower row adds Perlin noise to the displacement shader;

FIG. 3 is a three-dimensional example of AABB versus OBB bounding with the same number of subdivisions;

FIG. 4 shows the normal bounding technique for the normal patch with the leftmost figure showing the normal patch before normalization, the middle image showing each control point as normalized so that they map to the unit sphere, and, finally, the rightmost image shows the projections being bounded by a cone which is a conservative bound of the normalized normal for the patch;

FIG. 5 shows that given bounding cones for the two parametric derivatives denoted by T and B, a cone that bounds the cross product of any vector inside T and any vector inside B can be derived and is denoted here as N;

FIG. 6 shows an example of two different views using a screen space bounding box size as the sorting criteria with 16 steps of subdivision being performed, and the resulting difference in subdivision density;

FIG. 7 is a flow chart for bounding of a displaced Bézier surface patch and bounding algorithm in accordance with one embodiment of the present invention;

FIG. 8 is a flow chart for a more detailed flow for computing bounds of a displaced patch by finding an OBB for a displaced Bézier patch in accordance with one embodiment;

FIG. 9 is a flow chart for one embodiment for defining the OBB for a base patch using control points;

FIG. 10 is a flow chart for one embodiment for finding the normalized normal;

FIG. 11 is a flow chart for another embodiment of finding the normalized normal; and

FIG. 12 is a hardware depiction for one embodiment of the present invention.

DETAILED DESCRIPTION

Reducing the number of domain shader evaluations reduces the computational resources needed for that stage of a graphics pipeline. This can be done by culling patches which do not contribute to the final image. To make this culling efficient, an algorithm for computing hierarchical bounds of displaced surfaces may be used.
Furthermore, in tile-based rendering architectures, bounds for input primitives are needed to efficiently sort the input primitives into tiles. A “bounding volume” is a volumetric object, such as a box or sphere, that encloses another object. Since the domain shader is programmable, it is hard to give conservative and tight bounds of the output positions, which may give rise to a need to sort the generated small triangles individually into tiles. This increases the memory requirements on the tile queues, increases bandwidth usage, and reduces the efficiency of occlusion culling on a patch primitive level.
These bounds may, instead, be computed on the fly (block 12) based on the domain shader only without any need for a user specified parameter, as indicated in FIG. 7. The bounds may then be adaptively refined as the primitive is split into smaller sub-patches to create a hierarchy. In one embodiment, an algorithm enables conservative and tight bounding of dynamic displaced parametric surfaces, such as Bézier patches, using efficient normal bounding, oriented bounding boxes and min-max mipmap hierarchies of the displacement texture. The patch may be culled (block 16). If not, then the primitive may be subjected to tessellation and domain shading (block 18).
Since the patch does not have to be sent to the tessellator, both domain shader and tessellator tasks may be reduced for the patch in some embodiments. If the input patch is culled, then no tessellation and domain shading may be done in some embodiments. Similarly, if a sub-patch is culled, no further processing of that sub-patch may be done in some embodiments. Otherwise, the sub-patch is tessellated and domain shaded.
Collections of bi-cubic Bézier patches are popular rendering primitives for smooth surfaces. Known algorithms may be used for translating Catmull-Clark subdivision surfaces to collections of such parametric patches, while faithfully approximating the limit surface of the recursive subdivision process. It is common to add displacements from high resolution textures in the direction of the normal vector of the patch in order to increase the detail of the final surface.
The Bézier patch with displacement may be used in a domain shader in the rendering API. The Bézier patch is compactly represented by its control points, and this parametric surface representation can be efficiently evaluated in parallel (unlike recursive subdivision surfaces).
A Bézier patch, p(u,v), is a parametric surface, that is, a surface defined over two parametric coordinates, u and v. The term “base patch” denotes the Bézier patch which has not yet been displaced, to distinguish it from the final displaced surface. A domain shader that evaluates a displaced Bézier patch at a parametric coordinate, (u,v), computes the base patch position, p(u,v), the base patch's normalized normal {circumflex over (n)}(u,v) and a displacement value (usually) taken from a texture, t(u,v). If the displacement acts in the base patch's normal direction, the domain shader (before multiplication with the model-view-projection matrix) is then:
d(u,v)=p(u,v)+{circumflex over (n)}(u,v)t(u,v) (1)
Multiplying d(u,v) by the model view projection matrix, M, the clip space position, q, in homogeneous coordinates is obtained:
q(u,v)=Md(u,v)=M(p(u,v)+{circumflex over (n)}(u,v)t(u,v)) (2)
The normalized device coordinates are given by s_x=q_x/q_wand s_y=g_y/q_w.
A conservative bounds of q(u,v) over a parametric domain, where a<=u<=b and c<=v<=d can be found.
Next, we describe how we bound p(u,v). Bézier patches have the convex hull property and they can be easily bounded by their control points. Finding an axis-aligned bounding box (AABB) for a Bézier patch accounts for 3 min and 3 max operations per control point.
By repeatedly applying Bézier subdivision, the control point cages of the subdivided patches converge quickly towards the underlying base patch. Furthermore, if the original patch is recursively split in two pieces, p_Aand p_B, in each step, the de Casteljau steps needed to generate p_Awill generate the control points for p_Bas a side product. This allows for an efficient implementation.
We can derive axes for an oriented bounding box (OBB) from the control points of the base patch defined axes. This box encloses the base patch more tightly than an AABB. For each of the two subdivided patches in the same iteration both the base patch, the normal patch, and the displacement texture and lookup is refined. Referring to FIG. 8 which shows steps which are used to compute the bounds of the displaced surface indicated in block 12 in FIG. 7, the base patch is subdivided along one axis using Bézier subdivision. The base patch bounding, indicated in block 14, involves finding the OBB axes from control points and projecting all control points on these axes. Then the minimum and maximum along each axis is located to derive an OBB that contains all of the control points, and the convex hull property of Bézier patches means that the surface is contained in this OBB.
Next, as indicated in block 15, the displacement minimum and maximums are looked up in a min/max texture hierarchy. Thereafter, in diamond 19, a check determines whether the displacement is zero. If so, the model view projection is applied to the eight corners of the patch's bounding box (block 20) and the bounds are returned (block 23). If the displacement is not zero, normal bounding is done in block 21 using one of the techniques to be described hereinafter called TPATCH and NPATCH, before doing the model view projection transform (block 20) and returning the bounds (block 23). Finally, in block 23, the model view projection transform is applied.
For Bézier patches, the vectors between the corner control points (FIG. 1) are summed to get two axes (FIG. 9, block 24). Given a patch with (m+1)x(n+1) control points, we denote the four corner control points C_0,0, c_m,0, c_0,nand c_m,n, and form the two vectors:
t=c _m,0 −c _0,0 +c _m,n −c _0,n (3)
b=c _0,n −c _0,0 +c _m,n −c _m,0 (4)
t and b can be seen as approximate average gradients in the u and v parametric directions respectively. They do not have to be orthogonal. Their cross product (FIG. 9, block 26) gives a third axis: n=t cross product of b. To form an orthonormal coordinate system, we set x=t, y=n cross product of t, and z=n and normalize each vector (FIG. 9, block 28). The final coordinate system is: ({circumflex over (x)},ŷ,{circumflex over (z)}). This significantly reduces the size of the bounding boxes compared to using AABBs in most cases. More elaborate OBB fitting schemes based on the control point cage could be derived, but in practice, the simple approach above produces axes for OBBs that bound the surface tightly. The difference in quality between bounding with AABBs and OBBs is highlighted in FIG. 2 for curves and in FIG. 3 for a Bézier patch. For degenerate cases, we simply use an AABB. As we will show below, the OBB axes are also very useful in the normal bounding algorithms.
Bounding the patch normal, {circumflex over (n)}(u,v), over a domain is considerably more difficult than bounding the base position, p(u,v). The normal direction is computed as the cross product of two parametric derivatives of the base patch, p(u,v).
Following standard notation for tensor product Bézier surfaces, a Bézier patch P(u,v): R²?R³is defined by:
$\begin{matrix} p^{m, n} (u, v) = \sum_{i = 0}^{m} \sum_{j = 0}^{n} c_{i, j} B_{i}^{m} (u) B_{j}^{n} (v) & (5) \end{matrix}$
where c_i,jare the control points, m and n are the degrees of the patch in the parametric coordinates, u an v, respectively. B_i(u) and B_j(v) are Bernstein polynomials.
The partial derivatives can be written as
$\begin{matrix} \frac{\partial p}{\partial u} (u, v) = \sum_{j = 0}^{n} \sum_{i = 0}^{m - 1} a_{i, j} B_{i}^{m - 1} (u) B_{j}^{n} (v) & (6) \\ \frac{\partial p}{\partial v} (u, v) = \sum_{i = 0}^{m} \sum_{j = 0}^{n - 1} b_{i, j} B_{j}^{n - 1} (v) B_{j}^{m} (u) where & (7) \\ a_{i, j} = m (c_{i + 1, j} - c_{i, j}), & (8) \\ b_{i, j} = n (c_{i, j + 1} - c_{i, j}) . & (9) \end{matrix}$
Note that a_i,jand b_i,jare (scaled) differences of the control points of the base patch, and therefore vectors. The surface normal (before normalization) is defined by:
$\begin{matrix} n (u, v) = (n_{x}, n_{y}, n_{z}) = \frac{\partial p}{\partial u} (u, v) \times \frac{\partial p}{\partial v} (u, v) . & (10) \end{matrix}$
The normalized normal is given by:
$\begin{matrix} \hat{n} (u, v) = \frac{n}{\sqrt{n_{x}^{2} + n_{y}^{2} + n_{z}^{2}}} & (11) \end{matrix}$
If the bi-degree of p(u,v) is (m,n) in the parametric coordinates (u,v), then the first order parametric derivatives have degrees (m−1,n) and (m,n−1). As we will see below, the bi-degree of the patch after taking the cross product of the patches is then (m+n−1, m+n−1). A patch representing the normal direction of a bi-cubic Bézier patch thus needs bi-degree (5,5) to be represented exactly.
To apply displacement, we need the normalized normal. The normalization operation (Equation 11) needs bi-degree 2(m+n−1, m+n−1) for an exact representation of the subexpressions: n_x ²,n_y ², and n_z ². For a bi-cubic Bézier patch, these terms can be represented exactly as a bi-degree (10,10) Bézier patch. In many cases, this is prohibitively expensive (11·11=121 control points). Finally, the reciprocal square root cannot be represented exactly with Bernstein polynomials. In addition, the operand to the reciprocal square root should always be larger than or equal to zero, since the operand is the squared length of the normal. If this is not true, inf or NaN may result. Therefore the bounded representation of n_x ²+n_y ²+n_z ²should be strictly greater than zero. This seems trivial at a first glance, as the square root of a sum of three squared (real) terms should be greater than or equal to zero. However, this can be difficult in practice as we use the bounding box of the control point cage for bounding, and there is no guarantee that all control points will be positive.
Here, we describe a normal bounding algorithm, which avoids most of the problems discussed above. In summary, a normal vector Bézier patch is derived from the parametric derivatives (FIG. 10, block 32), then its control points are projected on the unit sphere (FIG. 10, block 34) and their solid angle on the unit sphere is bounded in an OBB coordinate frame (FIG. 10, block 36), which gives a conservative bound of the normalized normal. We denote this normal bounding approach NPATCH.
Recall that the normal is defined by:
$\begin{matrix} \begin{matrix} n (u, v) = \frac{\partial p}{\partial u} (u, v) \times \frac{\partial p}{\partial v} (u, v) \\ \sum_{j = 0}^{n} \sum_{i = 0}^{m - 1} a_{i, j} B_{i}^{m - 1} (u) B_{j}^{n} (v) \times \\ \sum_{k = 0}^{m} \sum_{l = 0}^{n - 1} b_{k, l} B_{k}^{m} (u) B_{l}^{n - 1} (v) . \end{matrix} & (12) \end{matrix}$
Using the formula for products of Bernstein polynomials:
$\begin{matrix} B_{i}^{m} (u) B_{j}^{n} (u) = \frac{(\begin{matrix} m \\ i \end{matrix}) (\begin{matrix} n \\ j \end{matrix})}{(\begin{matrix} m + n \\ i + j \end{matrix})} B_{i + j}^{m + n} (u) & (13) \end{matrix}$
Equation 12 is written as:
$\begin{matrix} \sum_{i, j, k, l}^{} a_{i, j} \times b_{k, l} \frac{(\begin{matrix} m - 1 \\ i \end{matrix}) (\begin{matrix} m \\ k \end{matrix}) (\begin{matrix} n \\ j \end{matrix}) (\begin{matrix} n - 1 \\ l \end{matrix})}{(\begin{matrix} m + n - 1 \\ i + k \end{matrix}) (\begin{matrix} m + n - 1 \\ j + 1 \end{matrix})} B_{i + k}^{m + n - 1} (u) B_{j + 1}^{m + n - 1} (v) . & (14) \end{matrix}$
which is a patch of bi-degree (m+n−1, m+n−1) with control vectors, v_p,q, given by:
$\begin{matrix} v_{p, q} = \sum_{\underset{j + 1 = q}{I + k = p}}^{} a_{i, j} \times b_{k, l} \frac{(\begin{matrix} m - 1 \\ i \end{matrix}) (\begin{matrix} m \\ k \end{matrix}) (\begin{matrix} n \\ j \end{matrix}) (\begin{matrix} n - 1 \\ l \end{matrix})}{(\begin{matrix} m + n - 1 \\ i + k \end{matrix}) (\begin{matrix} m + n - 1 \\ j + 1 \end{matrix})} & (15) \end{matrix}$
To conservatively bound the base patch's normal over the patch, we exploit the fact that the normal after normalization is of unit length. Therefore, we normalize the control vectors, v_p,q, so that they are represented by points on the unit sphere.
A fast way to derive these bounds is to use the {circumflex over (z)}-axis from the OBB coordinate frame, which is an approximation of the patch's normal, and simply compute the minimal scalar product between any normalized control point and the {circumflex over (z)}-axis. This gives the cosine of the half-angle of a cone enclosing the normalized directions. This is illustrated in FIG. 4.
For a bi-cubic Bézier patch, the computation of v_p,qincludes 144 cross products. The binomial coefficients can be pre-computed in a small lookup table.
Note, however, that all correlation of which direction corresponds to which parametric coordinate is lost. The tightness of the approach depends on whether the unnormalized normal can be bound reasonably well, which can be hard over large domains, but becomes easier as the subdomain shrinks.
Coarser bounds can be obtained more quickly by forming two tangent cones from the control points of the first order parametric derivative patches ∂p/∂u and ∂p/∂v (see Equations 6 and 7). The control points of the derivative patches are normalized and bounded on the unit sphere, (as shown in FIG. 4), forming two cones and T:{{circumflex over (t)},α_t} and B:{{circumflex over (b)},α_b}. A cone, T, is defined by a normalized axis {circumflex over (t)} and a half-angle α_t.
If the cones T and B do not overlap, a cone N:({circumflex over (n)},θ) that bounds all possible cross products of two vectors, one from each of T and B can be constructed. Its axis {circumflex over (n)} is in the direction t×b and its half-angle, θ, is given by:
$\begin{matrix} \sin θ = \frac{\sqrt{\sin^{2} α_{t} + 2 \sin α_{t} \sin α_{b} \cos β + \sin^{2} α_{b}}}{\sin β} & (16) \end{matrix}$
where â is the smallest of the two angles between the cone axes parallel to {circumflex over (t)} and {circumflex over (b)} respectively. The cone, N, bounds all the normalized normal over the patch. The cones T, B, and N are shown in FIG. 5.
We use the {circumflex over (t)} and {circumflex over (b)} axes derived above as axes for the cones T and B and the cone angles are found for cones T and B from the parametric derivative patches' control points (FIG. 11, block 40). The cosine of the cone angle á_t(á_b) is simply the minimum dot product of any normalized control point from the tangent patch with the {circumflex over (t)}({circumflex over (b)}) axis. A normal cone is derived by computing the cross product of cones T and B (FIG. 11, block 42). The bounds for the normalized normal expressed in the OBB coordinate frame are:
([−sin θ,sin θ],[−sin θ, sin θ],[ cos θ,1]) (17)
where θ is the cone half angle of the normal cone N. Using the equality sin²è+cos²è=1, we can derive the bounds of the normalized normal using the normal cone angle without using any trigonometric functions (FIG. 11, block 44). We denote this approach TPATCH.
Care must be taken to check that the two tangent cones do not overlap. The cones overlap if á_t+á_b>â, which given α_t<pi, α_b<pi, and β<pi can be rewritten as:
cos α_tcos α_b−sin α_tsin α_b<cos β (18)
If this condition is true, or if cos á_t<0,cos á_b<0, we return the unit box in the OBB coordinate frame. A unit box has the following two extreme vertices: (−1,−1,−1) and (+1,+1,+1). However, this will rarely happen, except for highly curved patches, since the OBB coordinate frame is computed from an approximation of the local surface tangent, bi-normal, and normal of the base patch.
Techniques for bounding texture lookups involve keeping two extra mipmap hierarchies. The first stores the maximum displacement value over each texture footprint and level and the second stores the minimum displacement value of the footprint. In general, when the parametric interval decreases, so do the texture bounds.
The final bounds of the displacement vector, o={circumflex over (n)}t, is the product (on interval arithmetic form) of the interval from the texture lookup [t_min,t_max] times the intervals of the normalized normal vector along each axis. Using the notation [a,ā] to define an interval, where, a is the lower limit and ā is the upper limit, multiplication of two intervals is defined by:
[ a , a ]
[ b , b ]=[min( ab , a b , a b , ab ), max( ab , a b , a b , ab )] (19)
Hence, the interval version of the x-component of o, is:
[o_x ,ō_x]=[t, t]
[{circumflex over (n)}{circumflex over (n_x)},{circumflex over ( n_x ] (20)
and similarly for the other components. If the texture displacement is strictly positive, then equation 20 can be further optimized.
The last step in most domain shaders is the matrix transformation to clip space, so the remaining part in obtaining bounds for q is the model view projection matrix, which does not depend on the parametric domain, and can be seen as a constant. This constant matrix is easily multiplied with the eight corners of the OBB obtained from the displaced patch d, resulting in bounds for the clip space position q. (The last step may not be needed when using hierarchical bounds for pre-tessellation sorting and ray tracing).
Given an initial coarse subdivision of the patch, a priority queue of the bounding boxes of the subdomains may be maintained in some embodiments. (For example, each sub-patch could alternatively be divided into a number of smaller sub-patches until each sub-patch is “small enough,” in terms of volume, surface area, or projected area, as examples). In each following subdivision step, we take the top element of the queue, subdivide it further, and insert the subdivided boxes back into the queue.
The exact sorting criterion is application dependent, and may contain the screen-space extents of the bounding box, the depth values, or prioritize boxes intersecting a frustum plane for view frustum culling. FIG. 6 illustrates a view-dependent subdivision criterion.
For view frustum culling, the OBB corners (in clip-space) are tested against the frustum planes. The subdivision criterion may be designed so that sub-patches straddling the camera frustum are prioritized, which efficiently culls geometry outside the clip planes. The clip test results of the patch can also be used to guarantee that the entire patch is completely inside the view frustum, so the clip tests for generated triangles from the patch can possibly be bypassed.
Given a coarse depth buffer, subpatches can be culled if their bounding box is entirely occluded by already drawn primitives. The subdivision criterion may be adopted so that sub-patches closer to the camera are processed first and sent to the rasterization stage of the pipeline, therefore increasing the likelihood of z-culling.
Backface culling is the hardest type of culling, due to the difficulty in efficiently bounding the geometric normal after displacement. However, given the tessellation rate, the normal bounds and a tight interval of the displacement, bounds for the displaced surface normal can be derived. Further, the subdivision criterion can be adapted to target patches with high normal variation, increasing the likelihood of backface-culling of subpatches.
After computing a bounded representation of the displaced Bézier patch, we can use the bounds for pre-tessellation sorting into tiles. Tile-overlap can be reduced by hierarchical subdivision of the largest screen-space bounding box.
In a ray tracing environment, the subdivision criterion is tuned to reduce the total surface area of each OBB, similar to how a surface area heuristic builds acceleration data structures. In collision detection, the subdivision criterion for reduced OBB volumes is tuned.
Hierarchical bounding volumes can be used for culling, as well as for sorting into tiles and ray tracing. Using the techniques described herein, electronic data may be transformed to a visual form for display on a display.
To efficiently support the DX-11 tessellation pipeline stages, in a tiling architecture, the bounds of the displaced surfaces are needed before tessellation and domain shading occurs. These bounds can be used to bin (i.e. sort primitives into tile-specific queues) the displaced Bézier patches without doing any tessellation. The tessellation and domain shading would then occur when and if needed. The use of hierarchical bounds may be useful for binning, view frustum culling, occlusion culling, and backface culling.
The graphics processing techniques described herein may be implemented in various hardware architectures. For example, graphics functionality may be integrated within a chipset. Alternatively, a discrete graphics processor may be used. As still another embodiment, the graphics functions may be implemented by a general purpose processor, including a multicore processor.
The computer system 130, shown in FIG. 12, may include a hard drive 134 and a removable medium 136, coupled by a bus 104 to a chipset core logic 110. A keyboard and mouse 120, or other conventional components, may be coupled to the chipset core logic via bus 108. The core logic may couple to the graphics processor 112, via a bus 105, and the main or host processor 100 in one embodiment. The graphics processor 112 may also be coupled by a bus 106 to a frame buffer 114. The frame buffer 114 may be coupled by a bus 107 to a display screen 118. In one embodiment, a graphics processor 112 may be a multi-threaded, multi-core parallel processor using single instruction multiple data (SIMD) architecture.
In the case of a software implementation, the pertinent code may be stored in any suitable semiconductor, magnetic, or optical memory, including the main memory 132 or any available memory within the graphics processor. Thus, in one embodiment, the code to perform the sequences of FIGS. 7-11 may be stored in a machine or computer readable medium, such as the memory 132 or the graphics processor 112, and may be executed by the processor 100 or the graphics processor 112 in one embodiment.
FIGS. 8-12 are flow charts. In some embodiments, the sequences depicted in these flow charts may be implemented in hardware, software, or firmware. In a software embodiment, a computer readable medium, such as a semiconductor memory, a magnetic memory, or an optical memory may be used to store instructions and may be executed by a processor to implement the sequences shown in one or more of the flow charts depicted in FIGS. 8-13.
References throughout this specification to “one embodiment” or “an embodiment” mean that a particular feature, structure, or characteristic described in connection with the embodiment is included in at least one implementation encompassed within the present invention. Thus, appearances of the phrase “one embodiment” or “in an embodiment” are not necessarily referring to the same embodiment. Furthermore, the particular features, structures, or characteristics may be instituted in other suitable forms other than the particular embodiment illustrated and all such forms may be encompassed within the claims of the present application.
While the present invention has been described with respect to a limited number of embodiments, those skilled in the art will appreciate numerous modifications and variations therefrom. It is intended that the appended claims cover all such modifications and variations as fall within the true spirit and scope of this present invention.

Claims

1. A method comprising:

using a computer processor to bound an undisplaced Bézier patch representing a surface to be tessellated using object oriented bounding boxes.

2. The method of claim 1 further comprising:

bounding a parametric surface using a coordinate frame derived from the parametric surface; and

bounding a displacement vector in the same coordinate frame.

3. The method of claim 2 including computing hierarchical bounds of the displaced parametric surface.

4. The method of claim 3 including adaptively refining bounds as the parametric surface is split into smaller sub-patches by an application-defined priority metric.

5. The method of claim 4 wherein bounding includes refining position, normal and texture bounds.

6. The method of claim 5 including repeatedly applying Bézier subdivision until an application-defined threshold is met.

7. The method of claim 2 including averaging vectors between corner control points to get two axes, taking the cross product of the two axes, and normalizing each vector to form an object-oriented bounding box coordinate frame.

8. The method of claim 7 including deriving a normal vector Bézier patch from parametric derivatives, projecting control points on a unit sphere, and bounding a solid angle on a unit sphere in an object oriented bounding box coordinate frame to give a bound of the base patch's normalized normal over the patch.

9. The method of claim 7 including using cones for deriving bounds of normalized normals of a base patch.

10. The method of claim 7 including forming a first cone from a derivative in one parametric direction, forming a second cone from a derivative in a different parametric direction, and forming a third cone by computing a cross product of the first and second cones in the coordinate frame.

11. The method of claim 2 including culling sub-patches, tessellation, and domain shading.

12. The method of claim 2 including using the obtained bounds to sort higher order primitives into screen-space tiles.

13. The method of claim 2 including building a hierarchy of bounding volumes for ray tracing.

14. The method of claim 2 including transforming said surface to a visual form displayed on a computer display.

15. A computer readable medium storing instructions executed by a computer to:

use a computer processor to bound an undisplaced Bézier patch representing a surface to be tessellated using object oriented bounding boxes.

16. The medium of claim 15 further storing instructions executed by a computer to:

bound a parametric surface using a parametric frame derived from the parametric surface; and

bound a displacement vector in the same coordinate frame.

17. The medium of claim 16 further storing instructions to compute hierarchical bounds of the displaced parametric surface.

18. The medium of claim 17 further storing instructions to adaptive refine bounds as the parametric surface is split into smaller sub-patches.

19. The medium of claim 18 further storing instructions to refine the position, normal and texture bounds during bounding.

20. The medium of claim 19 further storing instructions to repeatedly apply Bézier subdivision until application defined threshold is met.

21. The medium of claim 16 further storing instructions to average vectors between corner control points to get two axes, take the cross product of the two axes, and normalize each vector to form an object oriented bounding box coordinate frame.

22. The medium of claim 21 further storing instructions to derive a normal vector Bézier patch from parametric derivatives, project control points on a unit sphere, and bound the solid angle of the unit's sphere in an object oriented bounding box coordinate frame to give a bound of the base patch's normalized normal over the patch.

23. The medium of claim 20 further storing instructions to form a first cone from a derivative in one parametric direction, form a second cone from a derivative in a different parametric direction, and form a third cone by computing a cross product of the first and second cones in the coordinate frame.

24. The medium of claim 16 further storing instructions to cull sub-patches, tessellation and domain shading.

25. The medium of claim 16 further storing instructions to build a hierarchy of bounding volumes for ray tracing.

26. An apparatus comprising:

a processor to bound an undisplaced Bézier patch representing a surface to be tessellated using object oriented bounding boxes; and

a storage coupled to said processor.

27. The apparatus of claim 26, said processor to bound a parametric surface using a coordinate frame derived from the parametric surface and to bound a displacement vector in the same coordinate frame.

28. The apparatus of claim 27 including a display to display an image resulting from the bounding of the displaced parametric surface.

29. The apparatus of claim 27, said storage to store instructions to compute hierarchical bounds of the displaced parametric surface.

30. The apparatus of claim 29, said storage to store instructions to adaptively refine bounds as the parametric surface is split into smaller sub-patches by an application-defined priority metric.

31. The apparatus of claim 29, said storage storing instructions to refine positive, normal and texture bounds.

32. The apparatus of claim 31, said storage storing instructions to repeatedly apply Bézier subdivision until an application-defined threshold is met.

33. The apparatus of claim 27, said storage storing instructions to average vectors between corner control points to get two axes, take the cross product of the two axes, and normalize each vector to form an object-oriented bounding box coordinate frame.