Hierarchical Bounding of Displaced Parametric Surfaces

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.

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.