Surface detail rendering using leap textures

The present surface detail rendering technique provides an efficient technique for applying a mesostructure to a macrostructure for an object that minimizes the amount of memory required for pre-computed data. A leap texture is pre-computed for a mesostructure by classifying each voxel in the mesostructure geometry and assigning a value in the leap texture based upon the classification. The value in the leap texture represents a distance to jump along a ray cast in any view direction when a model is decorated with the mesostructure geometry.

BACKGROUND

Computer graphics and image processing techniques continually attempt to create photorealistic images. In many applications, these photorealistic images need to be rendered in real time. For example, animated characters in video games need to be rendered in real time. In order to achieve photorealistic images, mesostructures are applied to create the appearance of real-world materials and objects. Mesostructures are fine scale surface geometries. For example, different mesostructures may simulate wood, brick, or the like. Thus, when images are rendered with mesostructures applied, the objects obtain realistic surface details.

In overview, each object in an image may be represented as a set of polygonal or parameterized surfaces. This geometric model of the objects is commonly referred to as a macrostructure level. The mesostructure level is used to model details that are too small to be modeled efficiently by polygons. Several techniques have been developed over the past several years for real-time rendering of mesostructures. Each of these techniques faces the difficult tradeoff between the number of geometric primitives and the storage of pre-computed data.

For example, remeshing and slicing create a large amount of additional primitives over the original mesh (i.e., the macrostructure) in order to represent the detailed geometry (i.e., the mesostructure). These additional primitives add processing workload in a vertex engine and thus, hurt performance. Other techniques, such as bi-directional texture functions (BTF), view-dependent displacement mappings (VDM), and generalized displacement maps (GDM) use pre-computed high dimensional data calculated using a mesostructure sample. Because the data is pre-computed, the vertex engine does not suffer from additional processing workload and the rendering of the detailed geometry is accelerated in comparison to remeshing or slicing. However, the drawback of using pre-computed data is that the data consumes a significant amount of memory. Therefore, rendering techniques that use pre-computed data have difficulty in industrial applications where there is limited memory, such as for games and movies.

Thus, even with all the advances, there is a continual need to improve upon the surface detail rendering techniques for use in real-time applications.

SUMMARY

The present surface detail rendering technique provides an efficient technique for applying a mesostructure to a macrostructure for an object that minimizes the amount of memory required for pre-computed data. A leap texture is pre-computed for a mesostructure by classifying each voxel in the mesostructure geometry and assigning a value in the leap texture based upon the classification. The value in the leap texture represents a distance to jump along a ray cast in any view direction when a model is decorated with the mesostructure geometry.

DETAILED DESCRIPTION

The following description is directed at a surface detail rendering technique for applying a mesostructure over a macrostructure of an object. In contrast with prior techniques that pre-compute data for each of several viewing directions, the present surface detail rendering technique pre-computes a leap texture that may be used for applying the mesostructure in multiple viewing directions. Thus, by using the present technique, the amount of pre-computed data is minimized while still achieving photorealistic images. These and other aspects of the present surface detail rendering technique are now described in detail.

FIG. 1is an illustrative system that may be used to implement the surface detail rendering technique described herein. The system includes a computing device, such as computing device100. Computing device100represents any type of computing device such as a personal computer, a laptop, a server, a game console, a handheld or mobile device (e.g., a cellular phone, digital assistant), and the like. In a very basic configuration, computing device100typically includes at least one processing unit102and system memory104. Depending on the exact configuration and type of computing device, system memory104may be volatile (such as RAM), non-volatile (such as ROM, flash memory, etc.) or some combination of the two. System memory104typically includes an operating system106, one or more program modules108, and may include program data110. For the present surface detail rendering technique, the program modules108may include one or more components140for implementing the surface detail rendering technique. In addition, program modules108may include a graphics application142that utilizes the surface detail rendering technique implemented within components140. Alternatively, the operating system106may include one or more components for implementing the surface detail rendering technique. Program data110may include leap texture data150and other graphic modeling data152, such as a triangle mesh. This basic configuration is illustrated inFIG. 1by those components within dashed line112.

Computing device100may have additional features or functionality. For example, computing device100may also include additional data storage devices (removable and/or non-removable) such as, for example, magnetic disks, optical disks, or tape. Such additional storage is illustrated inFIG. 1by removable storage120and non-removable storage122. Computer storage media may include volatile and nonvolatile, removable and non-removable media implemented in any method or technology for storage of information, such as computer readable instructions, data structures, program modules, or other data. System memory104, removable storage120and non-removable storage122are all examples of computer storage media. Thus, computer storage media includes, but is not limited to, RAM, ROM, EEPROM, flash memory or other memory technology, CD-ROM, digital versatile disks (DVD) or other optical storage, magnetic cassettes, magnetic tape, magnetic disk storage or other magnetic storage devices, or any other medium which can be used to store the desired information and which can be accessed by computing device100. Any such computer storage media may be part of device100.

Computing device100may also have input device(s)124such as keyboard, mouse, pen, voice input device, touch input device, etc. For example, computing device100may include a data capture device as an input device. The data capture device may be a digital/electronic still camera, a video camera, a film/photographic scanner, or the like. The data capture device may be configured to capture a single or a sequence of images. In addition, there may be multiple data capture devices of various types connected in order to capture multiple views of an image simultaneously or sequentially, to capture three-dimensional or depth images, and/or to capture panoramic images of a scene. The images captured by the data capture device may then be stored as image data within computing device100via an appropriate interface, such as USB, IEEE 1394, BLUETOOTH, or the like. Output device(s)126such as a display, speakers, printer, etc. may also be included. These devices are well known in the art and are not discussed at length here.

Computing device100may also contain communication connections128that allow the device to communicate with other computing devices130, such as over a network. Communication connection(s)128is one example of communication media. Communication media may typically be embodied by computer readable instructions, data structures, program modules, or other data in a modulated data signal, such as a carrier wave or other transport mechanism, and includes any information delivery media. The term “modulated data signal” means a signal that has one or more of its characteristics set or changed in such a manner as to encode information in the signal. By way of example, and not limitation, communication media includes wired media such as a wired network or direct-wired connection, and wireless media such as acoustic, RF, infrared and other wireless media. Computer readable media can be any available media that can be accessed by a computer. By way of example, and not limitation, computer readable media may comprise “computer storage media” and “communications media.”

Various modules and techniques may be described herein in the general context of computer-executable instructions, such as program modules, executed by one or more computers or other devices. Generally, program modules include routines, programs, objects, components, data structures, etc. for performing particular tasks or implement particular abstract data types. These program modules and the like may be executed as native code or may be downloaded and executed, such as in a virtual machine or other just-in-time compilation execution environment. Typically, the functionality of the program modules may be combined or distributed as desired in various embodiments. An implementation of these modules and techniques may be stored on or transmitted across some form of computer readable media.

FIG. 2is a block diagram illustrating exemplary program modules and program data for implementing the present surface detail rendering technique within the computing device shown inFIG. 1. The block diagram is divided into a top portion and a bottom portion separated by a dashed line. The top portion represents program modules and program data used for pre-computed data processing200. The bottom portion represents program modules and program data used for real-time processing210.

For pre-computed data processing200, a leap texture computation module204inputs a mesostructure geometry202and outputs a leap texture206in accordance with the present surface detail rendering technique. Mesostructure geometry202may be one type of program data152illustrated inFIG. 1. As described above, mesostructure geometry202represents fine scale surface geometries. The mesostructure geometry may be any conventional type of mesostructure, such as tileable mesostructure samples, synthesized mesostructures, or the like. Briefly, leap texture computation module204, illustrated inFIG. 3and described in conjunction therewith, determines a value for each voxel of a volumetric texture (i.e., the mesostructure geometry), where a voxel is a volume element in three-dimensional space. Thus, a voxel is comparable to a pixel in two-dimensional space, but is in three-dimensional space.

For real-time processing210, a mesostructure rendering module214has access to the leap texture206that was pre-computed and has access to an object model212. The object model212is any conventional object model of arbitrary geometry that is represented by a triangle mesh that models an object. Briefly, mesostructure rendering module214, illustrated inFIG. 7and described in conjunction therewith, uses the leap texture206to iteratively jump step by step by a distance specified in the leap texture. As will be described below, the distance specified in the leap texture for a specified voxel is applicable for all view directions. In contrast, the pre-computed offset value stored in a five-dimensional generalized displacement mapping table stores an offset value for each voxel for each viewing direction. Thus, as will be described below, because the present surface detail rendering technique minimizes the amount of pre-computed data while still achieving photo-realistic images in real-time, the technique may be used in industrial applications with limited memory.

FIG. 3is a flow diagram illustrating an exemplary leap texture computation process suitable for use in the leap texture computation module shown inFIG. 2. As shown inFIG. 2, the leap texture computation module has access to a mesostructure geometry. At block302, a voxel of the mesostructure geometry is classified into one of three different types: 1) a boundary voxel; 2) an empty voxel; or 3) an inside voxel. As the names imply, a boundary voxel is a voxel on the boundary of the mesostructure, an empty voxel is a voxel outside the mesostructure, and an inside voxel is a voxel within the mesostructure. Each of these three types of categories will be illustrated later in conjunction withFIGS. 4 and 5. The actual classification for all the voxels may be performed before any processing within blocks310-344, in parallel with processing within blocks310-344once a voxel is classified, in sequence with processing within blocks310-344as a voxel is classified, or in various combinations of parallel and sequential order without departing from the present surface detail rendering technique. If a voxel is classified as a boundary voxel, processing continues at block310for that voxel. If a voxel is classified as an empty voxel, processing continues at block320for that voxel. If a voxel is classified as an inside voxel, processing continues at block330for that voxel. The processing for each type of voxel is now individually described.

At block310, the leap texture computation process obtains a color and normal property for the boundary voxel. The color and normal properties are applied during rendering of the image.

At block320, two distance measurements are determined for the empty voxel over all view directions. In block322, an entrance distance is determined. The entrance distance is a measurement from the empty voxel to a boundary voxel along a ray cast from the empty voxel in a desired view direction. The boundary voxel is on the boundary of the mesostructure. In block324, an exit distance is determined. The exit distance is a measurement from the empty voxel to another boundary voxel along the ray cast from the empty voxel in the desired direction. The other boundary voxel represents where the ray exits the mesostructure. These two distance measurements are determined for all view directions. The determination of these two distance measurements are illustrated and described later in conjunction withFIG. 4. Once block320is completed, processing for the empty voxel continues at block340.

At block330, a distance measurement is determined for the inside voxel over all view directions. In block332, an inside distance for the inside voxel is determined. The inside distance is a measurement from the inside voxel to a boundary voxel along a ray cast from the inside voxel towards the view direction. The determination of this distance measurement is illustrated and described later in conjunction withFIG. 5. Once block330is complete, processing for the inside voxel also continues at block340.

At block340, a representative distance value is determined over all the view directions for both empty voxels and inside voxels. For example, the representative distance value may be an average of the distances calculated in blocks320and330for the empty voxel and inside voxel respectively. In another embodiment, shown inFIG. 5, the representative distance value may be a minimum distance determined over all the view directions. For an empty voxel, two representative distance values are determined. For an inside voxel, one representative distance value is determined. Processing continues at block342.

At block342, a leap texture for all the voxels is determined. Briefly, illustrated inFIG. 6and described later in conjunction therewith, the leap texture stores one value for each voxel. That value is used during rendering to decorate the object with the mesostructure. The value is used for all viewing directions. Thus, the amount of pre-computed data is substantially decreased from techniques which store pre-computed data for each viewing direction. Blocks320-344are now described in further detail with reference toFIGS. 4-6.

FIG. 4is a set of graphic depictions400and410of measurements for determining a leap texture for an empty voxel in accordance with the surface detail rendering technique described herein. In graphic depiction400, an empty voxel Peis shown outside of mesostructure402. Mesostructure402is graphically illustrated as a shaded area under mesostructure boundary line404. A ray406sent from empty voxel Pealong view direction {right arrow over (V)}1intersects with a boundary voxel P1after a distance dn. The distance from Peto P1represents the entrance distance for view direction {right arrow over (V)}1. The ray406may then continue in the view direction {right arrow over (V)}1until exiting the mesostructure at another boundary voxel P2. The distance dffrom Peto P2represents the exit distance for view direction {right arrow over (V)}1. Values for these two distance measurements are then determined for all view directions {right arrow over (V)}=(θ, φ) expressed in spherical angles, where the polar angle θ ranges from 0 to π and the azimuth angle φ ranges from 0 to 2π. For either or both of these two distance measurements, if an intersection does not occur, the distance measurement is set to a pre-determined value that indicates no intersection. A conventional ray-casting technique is applied to compute the distances.

Graphic depiction410illustrates the minimum distances for empty voxel Peover all the view directions. Distance dNis defined as the minimum entrance distance dnover all the view directions: dN={mindn|∀V}. Distance dFis defined as the minimum exit distance dfover all the view directions: dF={mindf|∀V}. As one can see, in the illustrated example, view direction {right arrow over (V)}1ultimately yields the minimum entrance distance dN, whereas another view direction {right arrow over (V)}2yields the minimum exit distance dF. Thus, the leap texture may be based on distances from different view directions for any voxel.

FIG. 5is a set of graphic depictions510and510of measurements for determining a leap texture for an inside voxel in accordance with the surface detail rendering technique described herein. In graphic depiction500, an inside voxel Piis shown inside mesostructure402. Again, mesostructure402is graphically illustrated as a shaded area under mesostructure boundary line404. A ray506sent from inside voxel Pialong view direction {right arrow over (V)}3intersects with a boundary voxel P3after a distance di. The distance from Pito P3represents the inside distance. A value for this distance measurement is then determined for all view directions {right arrow over (V)}=(θ, φ) expressed in spherical angles, where the polar angle θ ranges from 0 to π and the azimuth angle φ ranges from 0 to 2π. Again, if an intersection does not occur, the distance measurement is set to a pre-determined value that indicates no intersection. Graphic depiction510illustrates the minimum inside distance for voxel Pi. Distance d1is defined as the minimum inside distance diover all the view directions: d1={mindi|∀V}. As one can see, view direction {right arrow over (V)}4ultimately yielded the minimum inside distance dI.

The leap texture d(x,y,z) is a scalar field in the space of the volumetric texture. In other words, given a starting voxel and a viewing direction, the leap texture hints at a jumping step for a ray starting from the starting voxel which will allow the ray to reach a boundary voxel as quickly as possible. In addition, the leap texture ensures that the first intersection with a boundary voxel is the first intersection. In one embodiment, the value stored in the leap texture for an empty voxel is a positive value and the value stored in the leap texture for an inside voxel is a negative value. As one can appreciate upon viewingFIG. 4, dNis a conservative approximation for a jump step and dFis an aggressive approximation for the jump step. Thus, in one embodiment, the present technique introduces a variable α for approximating the jump step for an empty voxel. By using variable α, the value represents a suitable jump step that minimizes the number of jumps. Variable α depends on the mesostructure and can be chosen via experimentation. A value of 0.25 has been used to obtain successful results.

FIG. 6illustrates an exemplary definition600for the leap texture of each voxel based on the measurements depicted inFIGS. 4 and 5. Thus, the value for any boundary voxel is zero, the value for any inside voxel is the negative of the minimum distance dI, and the value for any empty voxel is defined as: a·dN+(1−α)·dF. Once this leap texture is defined for each voxel, the leap texture can be used to apply the mesostructure in real-time to an object in order to render a photo-realistic image.

FIG. 7is a flow diagram illustrating an exemplary mesostructure rendering process suitable for use in the mesostructure rendering module shown inFIG. 2. The present surface detail rendering technique does not trace rays through mesostructures synthesized onto a surface, nor does it involve formation of numerous volume texture slices. Instead, in overview, the technique rapidly processes ray segments in each extruded prism using the leap texture. As shown inFIG. 2, the mesostructure rendering module accesses input from an object model and from the leap texture. Processing begins at block702.

At block702, the object model, represented as a triangle mesh, has each of its triangles extruded along the vertex normal direction of each surface triangle. Thus, each surface triangle becomes a 3-dimensional triangular prism. Thus, the mesostructure for each prism in the object space is given by a corresponding volume in the texture space. The bilinear prism fins are each approximated by two mesh triangles. Each fin (i.e., side face of the prism) is shared by two prisms, and its normal directions are defined outwards with respect to the prism being processed. Processing continues at block704.

At block704, the faces of the triangular prism are rasterized into fragments for processing in a pixel pipeline. In one embodiment, the faces may include the fin, top, and bottom faces. While rasterization utilizes conventional procedures known to those skilled in the art, one should note that in accordance with the present rendering technique each fragment is individually processed. Processing continues at block706.

At block706, a ray is generated from a desired view direction through each voxel of each triangular prism. Briefly, referring toFIG. 9, the ray904enters the triangular prism at Pinand exits the triangular prism at Poutto form a segment908within the triangular prism. Processing continues at block708.

At block708, because the mesostructure geometry is not explicitly represented in object space, each segment908in a prism is mapped to a corresponding segment918in texture space to determine intersections with the mesostructure geometry. Again, referring toFIG. 9, ray914of the texture volume912enters the texture volume at Tinand exits the texture volume at Tout. In general, the corresponding segment in texture-space is approximated as a straight-line segment between the ray entrance and exit points of the volumetric texture. The mesostructure intersection point of its cast ray, as well as the texture value, needs to be computed in order to later render each pixel. The intersections points may be calculated using the technique used for the five-dimensional generalized displacement map. Processing continues at block710.

At block710, the ray in the viewing direction in the texture space jumps iteratively step by step based on the values in the leap texture. This is in contrast with the generalized displacement mapping technique where the ray jumps directly to a boundary voxel in one step using the pre-computed offset value stored in the five-dimensional generalized displacement mapping table. For the present technique, each iterative jump along the view direction V is determined based on the following equation: Pn=Pn-1+V·d(Pn-1), where Pn-1is obtained from the leap texture.FIG. 8, described later, explains how the leap texture is used to iteratively jump step by step. Because computing the ray path in object space accounts for variations in surface curvature and texture warping, the joint use of object and texture space for determining ray intersections using the leap texture is efficient and reduces texture distortion.

After each iteration (block710), termination conditions may be considered. While there may be any number of termination conditions, process700illustrates three possible termination conditions: decision blocks720,722,724.

At decision block720, a determination is made whether a boundary voxel has been reached. If a boundary voxel has been reached, mesostructure rendering for that fragment proceeds to block726. If the boundary voxel has not been reached, processing continues to decision block722.

At decision block722, a determination is made whether a pre-determined number of iterations (e.g., ten) has been reached. For example, a developer may set a maximum number of iterations for jumping during the fragment program loop for each fragment. If the maximum iterations have been reached, processing for that fragment proceeds to block726. If the maximum iterations have not been reached, processing continues to decision block724.

At decision block724, a determination is made whether the sum of all the jump distances is larger that a penetrate distance. The penetrate distance refers to the boundary of the current prism. In one embodiment, the penetrate distance dtis calculated as the absolute difference between the distance to an entry boundary voxel and an exit boundary voxel. If the sum is less than the penetrate distance, processing continues back to block706for another iteration. However, if the sum is greater than the penetrate distance, processing ends for that fragment. In that case, the shading computation performed in block726is skipped for that fragment.

Block726is now described. At block726, the shading of the fragment is computed. Any conventional shading technique may be implemented. In one embodiment, Phong shading is used to compute the color for the fragment. If block726is entered from decision block720(i.e., a boundary voxel was reached), the color and normal of the boundary voxel is propagated to all the voxels inside the volumetric sample using a standard four conjunction propagation method known to those skilled in the art of image processing. If block726is entered from decision block722(i.e., the maximum number of iterations has been reached), the color and normal at the last position of the ray is used for the shading computation. Once the shading computation is complete, processing for this fragment ends. Processing for other fragments continue independently.

FIG. 8is a graphic depiction800of the surface detail rendering technique using the leap texture as described herein. In graphic depiction800, a starting voxel PSis shown outside mesostructure402. Again, mesostructure402is graphically illustrated as a shaded area under mesostructure boundary line404. A ray sent from starting voxel PSalong view direction {right arrow over (V)}8jumps to voxel Pj1after the first iteration. The distance dSfrom starting voxel PSand voxel Pj1is the value stored in the leap texture for starting voxel PS. On the second iteration, the jump distance is the value stored in the leap texture for voxel Pj1resulting in jumping to voxel Pj2. On the third iteration, the jump distance is the value stored in the leap texture for voxel Pj2resulting in jumping to inside voxel Pj3. Thus, the offset distance equals the three values from the leap texture which were all positive values. On the fourth iteration, the jump distance is the value stored in the leap texture for inside voxel Pj3resulting in jumping to boundary voxel Pj4. Thus, in the example shown, the desired boundary voxel was obtained after four iterations using the leap texture.

As described, the present surface detail rendering technique using leap textures may be used in place of five-dimensional general displacement map techniques when rendering real-time images with mesostructures. Thus, a mesostructure renderer using a pre-computed multi-dimensional “generalized displacement map” may instead use a leap texture as described herein. The render can than provide real-time rendering of highly detailed non-height-field mesostructures for rendering the mesostructure textures onto open or closed surfaces of arbitrary geometry. As one skilled in the art will appreciate, height-field mesostructures may be represented as a non-height-field mesostructure. Thus, the present technique can describe a range of surface geometries that include weave patterns and slanted protrusions. In rendering the mesostructures, the pre-computed leap texture facilitates texture coordinate computation of viewing rays whose piece-wise linear trajectory in texture space is determined in object space according to the shape of a base mesh upon which the mesostructure texture is to be rendered. Thus, the present surface detail rendering technique computes mesostructure visibility jointly in object space and texture space which enables both control of texture distortion and efficient computation of texture coordinates and shadowing. Local and global illumination can be computed for the present technique using the illumination techniques for the five-dimensional generalized displacement map.

While example embodiments and applications have been illustrated and described, it is to be understood that the invention is not limited to the precise configurations and resources described above. Various modifications, changes, and variations apparent to those skilled in the art may be made in the arrangement, operation, and details of the disclosed embodiments herein without departing from the scope of the claimed invention.