SYSTEM AND METHOD FOR MESH LEVEL OF DETAIL GENERATION

A system method for applying hierarchical mesh partitioning and reduction to provide efficient run-time rendering includes bounding a mesh to define a mesh volume, recursively subdividing the mesh volume a number of times, and reducing the mesh the number of times the mesh volume was subdivided to generate a plurality of level of detail meshes. The plurality of level of detail meshes is equal to the number of times the mesh volume was subdivided. Each level of detail mesh is then partitioned based on the number of times the mesh volume was subdivided.

TECHNICAL FIELD

The present invention generally relates to rendering, processing, and management issues associated with relatively complex high density meshes, and more particularly relates to a system and method for mesh level of detail generation to allow relatively simple run-time management and rendering of relatively complex high density meshes.

BACKGROUND

In computer graphics, objects may be modeled as tessellated polygonal approximations or meshes. These polygons may be even further converted to triangles by triangulation. During run-time, it is desirable to render objects by transforming the mesh into a visual display using various levels of detail (LOD). For example, when objects are close to a viewer, a detailed mesh is used; however, as objects recede further and further from a viewer, less detailed meshes are used. As may be appreciated, run-time processing, management, and rendering such modeled objects quickly and efficiently can be processor intensive.

During the rendering process, it may be necessary to switch between the different LOD that were generated. This can, however, create “holes” or discontinuities due, for example, to artifacts generated by the reduction algorithm. Ideally, one would prefer to generate relatively continuous LOD to eliminate, or at least significantly reduce, such discontinuities, while at the same time providing an acceptable level of performance and visual quality. Various reduction algorithms have been developed to generate the different LOD associated with a mesh. However, presently known reduction algorithms that eliminate, or at least significantly reduce, discontinuities require significant amounts of computational overhead during the rendering process.

Hence, there is a need for a system and method for mesh LOD generation that allows relatively simple run-time management and rendering of relatively complex high density meshes, while eliminating or at least significantly reducing, discontinuities of the rendered mesh. The present invention addresses at least this need.

BRIEF SUMMARY

In one embodiment, a method for applying hierarchical mesh partitioning and reduction to provide efficient run-time rendering. The method is implemented in a processor and includes bounding a mesh to define a mesh volume, recursively subdividing the mesh volume a number of times, and reducing the mesh the number of times the mesh volume was subdivided to generate a plurality of level of detail meshes. The plurality of level of detail meshes is equal to the number of times the mesh volume was subdivided. Each level of detail mesh is then partitioned based on the number of times the mesh volume was subdivided.

In another embodiment, a hierarchical mesh partitioning and reduction system includes a display device and a processor. The display device is coupled to receive image rendering display commands and is configured, upon receipt thereof, to render images. The processor is in operable communication with the display device and is configured to bound a mesh to define a mesh volume, recursively subdivide the mesh volume a number of times, reduce the mesh the number of times the mesh volume was subdivided to generate a plurality of level of detail meshes, where the plurality of level of detail meshes equal to the number of times the mesh volume was subdivided, partition each level of detail mesh based on the number of times the mesh volume was subdivided, and command the display device to render segments from a single level of detail.

In yet another embodiment, a method for applying hierarchical mesh partitioning and reduction to provide efficient run-time rendering is implemented in a processor and includes bounding a mesh to define a mesh volume, recursively subdividing the mesh volume a number of times, and reducing the mesh the number of times the mesh volume was subdivided to generate a plurality of level of detail meshes. The plurality of level of detail meshes is equal to the number of times the mesh volume was subdivided. Each level of detail mesh is partitioned based on the number of times the mesh volume was subdivided, and segments from a single level of detail are rendered on a display device. The number of times that the mesh volume is subdivided is determined by calculating a metric for portions of the mesh inside each subdivision.

Furthermore, other desirable features and characteristics of the hierarchical mesh partitioning and reduction system and method will become apparent from the subsequent detailed description and the appended claims, taken in conjunction with the accompanying drawings and the preceding background.

DETAILED DESCRIPTION

Referring toFIG. 1, a functional block diagram of one embodiment of a system100is depicted. The depicted system100may be used to, among other functions, render various types of graphics and includes at least a processor102and a display device104. The processor102is coupled to receive and/or retrieve a tessellated model106, or “mesh,” from one or more non-illustrated data sources. The processor102is configured to process the received or retrieved mesh106for rendering on the display device104. In this regard, the processor102is also configured to supply image rendering display commands to the display device104that cause the display device104to render graphical representations of all or portions of the received mesh106. The specific processing of the received mesh106that the processor102implements will be described in more detail further below.

The display device104is in operable communication with the processor102and is configured, upon receipt of the image rendering display commands supplied by the processor102, to render graphical representations of all or portions of the mesh106. The display device104is configured to implement any one of numerous types of 2D or 3D displays that are suitable for rendering textual, graphic, and/or iconic information in a format viewable by a non-illustrated observer. Non-limiting examples of such display devices include various cathode ray tube (CRT) displays, various flat panel displays, such as various types of LCD (liquid crystal display) and TFT (thin film transistor) displays, and a 3D light field display. The display device104may additionally be implemented as a panel mounted display, a HUD (head-up display) projection, or any one of numerous other known technologies.

The processor102, as previously noted, processes the received or retrieved mesh106for rendering on the display device104. More specifically, the processor102is configured to implement a process that applies hierarchical mesh partitioning and reduction to the mesh106, and does so in a manner that allows efficient run-time rendering on the display device104without introducing “holes” or other artifacts into the rendered mesh. This process200is depicted in flowchart form inFIG. 2, and will now be described. Before doing so, however, it should be noted that the process200may be applied to various types of multi-dimensional (e.g., 2D or 3D) meshes, including various types of triangle meshes, and various types of grid meshes, just to name a few. For ease of description and illustration, the process200will be described as being implemented on a 2D mesh. It should also be noted that the parenthetical references in the following description refer to like-numbered flowchart blocks inFIG. 2.

With reference now toFIG. 2, the depicted process200begins upon receipt or retrieval of the mesh106. Upon its receipt or retrieval, and as illustrated inFIG. 3, the mesh106is bounded to define a mesh volume302(202). More specifically, the processor102draws an imaginary boundary304around the mesh106. Thereafter, as illustrated inFIG. 4, the mesh volume302is recursively subdivided a number of times (204). AsFIG. 4also illustrates, the processor102may also generate a mesh tree402having a tree depth that is equal to the number of times the mesh volume was subdivided. It should be noted that at this point the mesh106is not partitioned, it is only subdivided. It will be appreciated that the mesh volume302may be recursively subdivided using any one of numerous known mesh subdivision processes including, for example, oct-tree, or quad-tree, just to name a few.

In the simplified example depicted inFIG. 4, the mesh volume302is subdivided three times, and the resulting mesh tree402, which represents the various volumetric partitions, has a depth of three. Generally speaking, however, the number of times that the mesh volume302is subdivided is determined by calculating a metric for the portions of the mesh106inside each of the subdivisions. The particular metric may vary, but in one particular embodiment the metric is a number that is less than a predetermined number of vertices per subdivision. In other words, the mesh volume302is recursively subdivided until the number of vertices (or triangles) in each subdivision is less than the predetermined number. Thus, while the processor102is recursively subdividing the mesh volume302, it is also counting the number of vertices within each subdivision and comparing the number of vertices to the predetermined number. It will be appreciated that the predetermined number may vary, and is preferably selected based upon the performance characteristics of the system100.

Referring once again toFIG. 2, but this time in combination withFIG. 5, it is seen that after the mesh volume302is recursively subdivided, the mesh106(not the mesh volume) is reduced to generate a plurality of level of detail (LOD) meshes502(206). In particular, the entire mesh106, which is the highest LOD, is reduced the same number of times that the mesh volume302was subdivided. Thus, the plurality of LOD meshes502(e.g.,502-1,502-2,502-3. . .502-N) is equal to the number of times that the mesh volume302was subdivided. It will be appreciated that the mesh106may be reduced using any one of numerous mesh reduction processes. It will additionally be appreciated that the target number of vertices in each reduced mesh502is preferably, though not necessarily, based on the overall number of vertices expected its corresponding level in the mesh tree302. Preferably, the reduction process that is selected will reduce the vertex/triangle count while maintaining a reasonable approximation of mesh106appearance, and allow a target number of vertices/triangles for each LOD mesh502to be specified.

Having generated the plurality of LOD meshes502, the processor102then partitions each LOD mesh502based on the number of times the mesh volume302was subdivided (208). As illustrated more clearly inFIG. 6, the lowest LOD mesh502, which in the depicted example is502-3, is not partitioned, and is the root of a corresponding mesh tree602that the processor102generates. The mesh tree602is balanced, all of the leaves are segments from the original mesh106, and all of the segments at a given depth (or LOD) are partitioned from the same LOD mesh502. As with the partitioning of the mesh volume302, each LOD mesh502may be partitioned using any one of numerous known mesh subdivision processes including, for example, oct-tree, or quad-tree, just to name a few. Preferably, the partitioning process that is used will allow the mesh106to be clipped to a specified volume, while handling any necessary triangle creation along the edges, appropriately handling vertex attributes, and, except for the clipping, maintaining the shape of the mesh106.

After the processor102has processed the received or received mesh106according to the above-described process200, it may then command the display device104to render all, or portions, of the mesh106. In doing so, the processor102will command the display device to use only segments from a single LOD. This is made possible because each LOD covers the entire original mesh106.

The process200depicted inFIG. 2and described above is relatively simple, exhibits low runtime complexity, and allows rendering of the mesh106with no holes or various other discontinuities that other LOD processes exhibit due to LOD mismatches between adjacent segments. This relatively simple process200can, however, exhibit its own issues when the original mesh106density is irregular. For example, due to its balanced tree partitioning, some segments at higher LOD may contain relatively few vertices. As may be appreciated, unnecessarily loading and/or rendering a lot of relatively small segments increases processing overhead. Another issue that may be exhibited is associated with the fact that the process controls for the average number of vertices per segment, but does not tightly bound the number of vertices in each individual segment. As may be appreciated, the process200depicted inFIG. 2and described above may be slightly modified, if needed or desired, to address these issue. The particular modifications associated with each issue will now be described.

The first issue may be addressed by slightly modifying the step of the process200in which each LOD mesh502is partitioned. Specifically, this step (208) is implemented by first partitioning each LOD mesh502in LOD order, from the lowest level of detail to the highest level of detail, and counting the vertices within each partitioned LOD mesh502for the next lower LOD. When the vertices within a partitioned LOD mesh502is less than a predetermined number, a boundary of the next lower LOD is used. AsFIG. 7depicts, this creates a node702in the mesh tree602that has only a single child node704. It does not, however, change the properties of resulting mesh tree602. That is, all of the leaves are the same distance from the root, and all of the segments at given depth are from the same LOD mesh502. As may be readily appreciated by the skilled person, for irregular density meshes106, this modification combines small segments at higher LOD into larger segments covering larger volumes, which reduces processing overhead.

The second issue described above may be addressed by slightly modifying both the step of the process200in which the mesh volume302is recursively subdivided, and step of the process200in which the mesh106is reduced. Specifically, and as may be appreciated, when the processor102recursively subdivides the mesh volume302, it generates a plurality of mesh sub-volumes. AsFIG. 8more clearly depicts, this step (204) of the process200is modified such that each mesh sub-volume802is bounded with a sub-volume boundary804. The step of reducing the mesh106(206) is modified so that each mesh sub-volume802is reduced, and then its associated sub-volume boundary804is removed. These modifications to the process200allow tighter control of the number vertices per segment by specifying the vertex count target for each sub-volume802plus its associated bounding box804, rather than entire mesh106, which may decrease the runtime of there duce process.