System and method for point pushing to render polygons in environments with changing levels of detail

A system and method are described for pushing child vertices to predetermined parent vertices to remove detail from an array of polygons. In one embodiment, a graphics engine identifies an LOD boundary that divides the array of polygons into low LOD and high LOD areas. The graphics engine identifies each child vertex that resides on the low LOD side of the LOD boundary as well as the parent vertices of that child vertex. Using a point pushing technique rule, the graphics engine determines which, if any, of the identified child vertices migrates to a parent vertex. The graphics engine identifies a predetermined parent vertex to which the graphics engine moves each migrating child vertex. The graphics engine pushes each migrating child vertex to its respective predetermined parent vertex. The graphics engine reverses this process to add detail to an array of polygons.

BACKGROUND OF THE INVENTION

1. Field of the Invention

This invention relates generally to computer graphics and more specifically to a system and method for using a point pushing technique to render polygons in environments with changing levels of detail.

2. Description of the Background Art

The resolution of a rendered object generally relates to the number of polygons used to generate that object. A rendered object that contains a greater number of polygons over a given area typically has a higher resolution than an object that contains fewer polygons over the same area.

Graphics engines or graphics software typically implement a technique known as “stripping” when rendering objects. Stripping is a method of generating polygons that enables processors, usually central processing units and graphics processing units, to generate large numbers of polygons while using relatively little processing power. Stripping thereby allows graphics engines or graphics software to render higher resolution objects more quickly and inexpensively. For this reason, producing high resolution graphics for video games and other computer programs and applications that utilize stripping algorithms is simpler and less expensive than producing high resolution graphics for games, programs and applications that do not utilize stripping algorithms.

Stripping generally entails linking polygons in a strip such that a graphics engine or graphics software can generate an additional polygon simply by creating new vertices off one end of the strip and connecting those new vertices to the vertices of the last polygon on that end the strip. The additional polygon and the polygon that was last in the strip share the vertices to which the graphics engine or graphics software connected the new vertices. A triangle is the most commonly used polygon in stripping algorithms because a graphics engine or graphics software can render an additional triangle in a strip by creating only one new vertex and connecting that vertex to each of two vertices of the last triangle in the strip.

When rendering objects, graphics engines or graphics software also typically divide an image screen into different arrays of polygons, sometimes referred to as “meshes.” At any given time, a particular mesh has one or more levels of resolution or levels of detail (LOD) that correspond to the different levels of resolution of the parts of the rendered object(s) represented in the mesh. A higher LOD area of a mesh contains both smaller polygons and a greater number of polygons than a lower LOD area of the mesh contains. The boundary between a higher LOD area of a mesh and a lower LOD area of a mesh is referred to as an “LOD boundary.”

When an LOD boundary intersects one of the polygons in a mesh, the graphics engine or graphics software generates additional polygons on the higher LOD side of the LOD boundary to add detail to that part of the mesh. The area of intersection between the LOD boundary and a side of one of the additional polygons is referred to as a “T-junction.” The result is that only part of the original polygon resides on the lower LOD side of the T-junction (referred to as the “low resolution patch”) and several smaller polygons reside on the higher LOD side of the T-junction (referred to as the “high resolution patch”). Frequently, the low resolution patch and the high resolution patch do not align properly, causing a “crack” in the screen image. A crack is where part of a background image appears in a higher resolution part of a rendered object. This same phenomenon also can occur when a graphics engine or graphics software removes detail from part of a mesh located on a lower LOD side of an LOD boundary.

Several schemes exist that address the T-junction problem described above. These prior art solutions, however, tend to compromise the ability of the graphics engine or graphics software to perform stripping. The consequence is that systems designed to address the T-junction problem lose the efficiencies of stripping and therefore produce lower resolution graphics, and systems that preserve stripping frequently produce graphics that show cracks.

SUMMARY OF THE INVENTION

One embodiment of a system and method for pushing child vertices to predetermined parent vertices to remove detail from an array of polygons starts with a graphics engine identifying an LOD boundary that divides the array of polygons into a low LOD area and a high LOD area. The graphics engine then identifies every child vertex in the array of polygons that resides on the low LOD side of the LOD boundary. The graphics engine also identifies the parent vertices of each such child vertex. Next, the graphics engine determines which, if any, of the child vertices residing on the low LOD side of the LOD boundary migrates to a parent vertex. The graphics engine uses a point pushing technique rule to make this determination. According to one embodiment of the rule, a child vertex migrates to one of its parent vertices if both parent vertices reside on the low LOD side of the LOD boundary. A child vertex does not migrate, however, if either of its parent vertices resides on the high LOD side of the LOD boundary. For each child vertex that migrates, the graphics engine identifies the parent vertex to which the graphics engine moves that child vertex. Each of these parent vertices is referred to as a “predetermined parent vertex.” Lastly, the graphics engine pushes each migrating child vertex to its respective predetermined parent vertex. When the child vertices complete their migrations, the low LOD area of the array of polygons has less detail than the high LOD area.

According to another embodiment of the system and method, the graphics engine adds detail to an array of polygons by essentially reversing the processes described above. The graphics engine first identifies an LOD boundary that divides the array of polygons into a high LOD area and a low LOD area. The graphics engine then identifies every predetermined parent vertex on the high LOD side of the LOD boundary. In addition, the graphics engine identifies each child vertex having the same position as any of the identified predetermined parent vertices as well as the other parent vertex of each such child vertex. Next, the graphics engine determines which, if any, of these child vertices migrates. The graphics engine again uses a point pushing technique rule to make this determination. In one embodiment, the point pushing technique rule dictates that a child vertex migrates if both of its parent vertices reside on the high LOD side of the LOD boundary. A child vertex does not migrate, however, if either of its parent vertices resides on the low LOD side of the LOD boundary. Lastly, the graphics engine pushes each migrating child vertex to a predetermined location. When the child vertices complete their respective migrations, the high LOD area of the array of polygons has more detail than the low LOD area.

One advantage of the embodiments of the system and method described above is that the strips of polygons in the array retain their integrity as the graphics engine either removes detail from a low LOD area of the array of polygons or adds detail to a high LOD area. Another advantage is that the graphics engine removes or adds the detail without causing cracks to appear between the low LOD area of the array of polygons and the high LOD area.

DETAILED DESCRIPTION OF THE INVENTION

FIG. 1is a block diagram of one embodiment of an electronic entertainment system100, according to the invention. System100includes, but is not limited to, a main memory110, a central processing unit (CPU)112, vector processing units VU0111and VU1113, a graphics processing unit (GPU)114, an input/output processor (IOP)116, an IOP memory118, a controller interface120, a memory card122, a Universal Serial Bus (USB) interface124and an IEEE 1394 interface126. System100also includes an operating system read-only memory (OS ROM)128, a sound processing unit (SPU)132, an optical disc control unit134and a hard disc drive (HDD)136, which are connected via a bus146to IOP116. System100is preferably an electronic gaming console; however, system100may also be implemented as any type of general-purpose computer, set-top box or hand-held gaming device.

CPU112, VU0111, VU1113, GPU114and IOP116communicate via a system bus144. CPU112communicates with main memory110via a dedicated bus142. VU1113and GPU114may also communicate via a dedicated bus140. CPU112executes programs stored in OS ROM128and main memory110. Main memory110may contain prestored programs and may also contain programs transferred via IOP116from a CD-ROM, DVD-ROM or other optical disc (not shown) using optical disc control unit134. IOP116controls data exchanges between CPU112, VU0111, VU1113, GPU114and other devices of system100, such as controller interface120.

GPU114executes drawing instructions from CPU112and VU0111to produce images for display on a display device (not shown). VU1113transforms objects from three-dimensional coordinates to two-dimensional coordinates, and sends the two-dimensional coordinates to GPU114. SPU132executes instructions to produce sound signals that are output on an audio device (not shown). In one embodiment of the invention, GPU114, CPU112and certain graphics software in main memory110operate in conjunction as a “graphics engine.”

A user of system100provides instructions via controller interface120to CPU112. For example, the user may instruct CPU112to store certain game information on memory card122or may instruct a character in a game to perform some specified action. Other devices may be connected to system100via USB interface124and IEEE 1394 interface126.

FIG. 2is a diagram illustrating the relationship between parent vertices and child vertices of a rendered polygon210, according to one embodiment of the invention. As shown, polygon210is a triangle, but in other embodiments polygon210can be any type of polygon. Polygon210has three parent vertices212,214and216, each of which is a vertex of polygon210. In addition, polygon210has three child vertices218,220and222, each of which is a point located on one of the sides of polygon210such that each set of two parent vertices has one child vertex. For example, child vertex218is the child of parent vertices212and216, child vertex220is the child of parent vertices212and214and child vertex222is the child of parent vertices214and216. The arrows shown inFIG. 2point to the parent vertices of each of child vertices218,220and222. In one embodiment of the invention, a child vertex is the midpoint between its two parent vertices.

Generally speaking, the graphics engine can use parent vertices and child vertices to add detail to or to remove detail from a rendered object (or part of a rendered object). For example, when adding detail, the graphics engine first generates a child vertex for each set of parent vertices of each polygon in the rendered object. The graphics engine then pushes or moves each child vertex to a predetermined location within the anticipated contours of the rendered object (such child vertex movement is referred to as “migration”). The graphics engine also generates additional polygons within the contours of the rendered object by connecting the child vertices to each other as well as to the parent vertices. The graphics engine can use a stripping algorithm or some other method to generate the additional polygons. Each child vertex becomes a vertex of one or more of the additional polygons and, therefore, a parent vertex of each such additional polygon. The result is that the rendered object is comprised of both smaller polygons and a greater number of polygons than it was comprised of originally, thereby giving the rendered object a higher level of detail than it had originally.

When adding yet more detail to the rendered object, the graphics engine repeats the process described above. The only difference is that the rendered object now contains more polygons. The graphics engine first generates a child vertex for each set of parent vertices of each polygon in the rendered object. The graphics engine then causes each child vertex to migrate to a predetermined location within the anticipated contours of the rendered object. The graphics engine again generates additional polygons within the contours of the rendered object by connecting the child vertices to each other as well as to the parent vertices. Again, each child vertex becomes a parent vertex of one or more of the additional polygons. The result is that the rendered object is comprised of both smaller polygons and a greater number of polygons than it was comprised of after adding the first level of detail, thereby giving the rendered object a higher level of detail than it had after adding the first level of detail.

FIGS. 3A and 3Bare diagrams illustrating how the graphics engine uses parent vertices and child vertices to add detail to a rendered object310as described in conjunction withFIG. 2. More specifically,FIG. 3Aillustrates the graphics engine's adding detail as rendered object310moves from a low LOD area of an image screen to an intermediate LOD area. As shown, rendered object310appears as a square in the low LOD area. For simplicity of illustration, assume that one can model rendered object310as a single polygon having four parent vertices312,314,316and318.

As rendered object310moves in the image screen from the low LOD area to the intermediate LOD area, the graphics engine adds detail to rendered object310. As discussed in conjunction withFIG. 2, to add the necessary detail, the graphics engine first generates child vertices320,322,324and326such that each set of parent vertices of rendered object310has a child vertex. For example, child vertex320is the child of parent vertices312and314, child vertex322is the child of parent vertices314and316, child vertex324is the child of parent vertices316and318and child vertex326is the child of parent vertices312and318.

The graphics engine then moves each child vertex to a predetermined location within the anticipated contours of rendered object328. Migration paths330,332,334and336show the paths over which the graphics engine moves each of child vertices320,322,324and326, respectively.

The graphics engine also generates additional polygons within the contours of rendered object310to provide rendered object310with the requisite amount of additional detail. For simplicity of illustration,FIG. 3Ashows only the sides of the additional polygons that constitute connections between child vertices320,322,324and326and parent vertices312,314,316and318. The result is a rendered object328, an octagon, that has more detail than rendered object310, a square.

FIG. 3Billustrates the graphics engine's adding detail as rendered object328moves from the intermediate LOD area of the image screen to a high LOD area. As shown, rendered object328appears as an octagon in the intermediate LOD area. Again, for simplicity of illustration, assume that one can model rendered object328as a single polygon having eight parent vertices312,314,316,318,320,322,324and326.

As rendered object328moves in the image screen from the intermediate LOD area to the high LOD area, the graphics engine adds detail to rendered object328. Again, to add the necessary detail, the graphics engine first generates child vertices338,340,342,344,346,348,350and352such that each set of parent vertices of rendered object328has a child vertex. For example, child vertex338is the child of parent vertices312and320, child vertex340is the child of parent vertices314and320, child vertex342is the child of parent vertices314and322, child vertex344is the child of parent vertices316and322, child vertex346is the child of parent vertices316and324, child vertex348is the child of parent vertices318and324, child vertex350is the child of parent vertices318and326and child vertex352is the child of parent vertices312and326.

The graphics engine then moves each child vertex to a predetermined location within the anticipated contours of rendered object354. Migration paths356,358,360,362,364,366,368and370show the paths over which the graphics engine moves each of child vertices338,340,342,344,346,348,350and352, respectively.

Again, the graphics engine also generates additional polygons within the contours of rendered object328to provide rendered object328with the requisite amount of additional detail. For simplicity of illustration,FIG. 3Bshows only the sides of the additional polygons that constitute connections between child vertices338,340,342,344,346,348,350and352and parent vertices312,314,316,318,320,322,324and326. The result is a rendered object354, a sixteen-sided polygon, that has more detail than rendered object328, an octagon.

The graphics engine can remove detail from either rendered object354or rendered object328by simply reversing the steps described above. For example, if rendered object354moves from the high LOD area of the image screen to the intermediate LOD area, the graphics engine can reverse the steps set forth in conjunction withFIG. 3Bto remove detail from rendered object354and transform rendered object354into rendered object328. Likewise, if rendered object328moves from the intermediate LOD area of the image screen to the low LOD area, the graphics engine can reverse the steps set forth in conjunction withFIG. 3Ato remove detail from rendered object328and transform rendered object328into rendered object310.

The examples set forth in conjunction withFIGS. 3A and 3Bparallel a situation where a circular object, such as a car tire, is a rendered object in an image screen, and the car tire moves among different LOD areas of the image screen. When the car tire is in the background of the overall image, the car tire resides in the low LOD area of the image screen. The image system shows the car tire as a square because the car tire is so small relative to the rest of the image that an image system user is unable to distinguish between a square and a circle. The square car tire therefore appears circular to the user.

As the car tire moves more into the foreground of the overall image, the car tire resides in the intermediate LOD area of the image screen. Here, the image system has to present the car tire with more detail because the car tire is larger relative to the rest of the image, enabling the image system user to see the car tire more clearly. For this reason, the image system presents the car tire as an octagon with more detail than the square version of the car tire.

As the car tire continues to move farther into the foreground of the overall image, the car tire resides in the high LOD area of the image screen. Here, the image system has to present the car tire with even more detail than the octagon version of the car tire because the car tire is larger and more clearly seen by the image system user than the octagon version. The image system therefore presents the car tire as a sixteen-sided polygon with more detail than the octagon version of the car tire. As the car tire moves closer and closer to the image system user, the graphics engine represents the car tire as a polygon with an increasing number of sides and amount of detail. In the limit, the shape of the car tire approaches that of an actual circle.

FIG. 4is diagram illustrating a point pushing technique rule, according to one embodiment of the invention. As shown, three polygons410,430and450are displayed in an image screen400. Polygon410has three parent vertices418,420and422and three child vertices412,414and416. Polygon430has three parent vertices438,440and442and three child vertices432,434and436. Polygon450has three parent vertices458,460and462and three child vertices452,454and456. An LOD boundary405divides image screen400into a low LOD area and a high LOD area.

The point pushing technique rule, according to one embodiment of the invention, is as follows. If both parent vertices of a child vertex reside on the low LOD side of the LOD boundary, the graphics engine pushes or moves that child vertex to one of its parent vertices. The system implementing the rule predetermines the parent vertex to which the graphics engine pushes the child vertex (referred to as the “predetermined parent vertex”). If, however, either of the parent vertices of a child vertex resides on the high LOD side of the LOD boundary, the graphics engine does not push or move that child vertex—rather, that child vertex remains in its original position.

The point pushing technique rule applies to polygon410as follows. The parents of child vertex412, parent vertices418and422, both reside on the low LOD side of LOD boundary405. According to the rule, the graphics engine pushes child vertex412to predetermined parent vertex418, as the arrow inFIG. 4depicts. The parents of child vertex414, parent vertices418and420, both reside on the low LOD side of LOD boundary405. According to the rule, the graphics engine pushes child vertex414to predetermined parent vertex418, as the arrow inFIG. 4depicts. The parents of child vertex416, parent vertices420and422, both reside on the low LOD side of LOD boundary405. Again, according to the rule, the graphics engine pushes child vertex416to predetermined parent vertex420, as the arrow inFIG. 4depicts.

The point pushing technique rule applies to polygon430as follows. The parents of child vertex434, parent vertices438and440, both reside on the low LOD side of LOD boundary405. According to the rule, the graphics engine pushes child vertex434to predetermined parent vertex440, as the arrow inFIG. 4depicts. The parents of child vertex436, parent vertices440and442, reside on opposite sides of LOD boundary405. According to the rule, child vertex436does not move, remaining in its original position. Similarly, the parents of child vertex432, parent vertices438and442, reside on opposite sides of LOD boundary405. According to the rule, child vertex432also does not move, remaining in its original position.

The point pushing technique rule applies to polygon450as follows. The parents of child vertex452, parent vertices458and462, both reside on the high LOD side of LOD boundary405. According to the rule, child vertex452does not move, remaining in its original position. The parents of child vertex454, parent vertices458and460, both reside on the high LOD side of LOD boundary405. According to the rule, child vertex454does not move, remaining in its original position. The parent vertices of child vertex456, parent vertices460and462, both reside on the high LOD side of LOD boundary405. Again, according to the rule, child vertex456also does not move, remaining in its original position.

As discussed in conjunction withFIGS. 3A and 3B, when a rendered object moves from a high LOD to a low LOD area in the image screen, the graphics engine removes detail from the rendered object. The graphics engine accomplishes this objective by removing polygons from the rendered object until the rendered object has an amount of detail commensurate with the low LOD.

Related to the foregoing, when a rendered object moves in an image screen, differing types of LOD boundaries intersect the arrays of polygons or meshes into which the graphics engine has divided the image screen. In a situation where a particular mesh initially resides in a high LOD area of the image screen, and then a rendered object moves, causing an LOD boundary to divide the mesh into a low LOD area and a high LOD area, the graphics engine has to remove detail from the low LOD area of the mesh. Similar to removing detail from a rendered object, the graphics engine removes detail from the low LOD area of the mesh by removing polygons in that area until that part of the mesh has an amount of detail commensurate with the low LOD.

The discussion set forth below in conjunction withFIGS. 5A,5B,6and7discloses how the graphics engine uses the point pushing method of the present invention to remove detail from any area of an array of polygons while (i) avoiding the T-junction problem described above in conjunction with the prior art and (ii) preserving the graphics engine's ability to generate polygons through stripping.

FIG. 5Ais a diagram illustrating one embodiment of a mesh500located in a low LOD area of an image screen, according to the invention. Mesh500is one embodiment of an array of polygons arranged in horizontal and vertical strips. As shown, mesh500contains three horizontal strips of polygons502,504and506and four vertical strips of polygons508,510,512and514. Parent vertices of the various polygons also are shown. For example, parent vertices516,518and522are the vertices of one polygon, parent vertices518,520and522are the vertices of one polygon, parent vertices524,526and530are the vertices of one polygon, parent vertices526,528and530are the vertices of one polygon, parent vertices532,534and538are the vertices of one polygon and parent vertices534,536and538are the vertices of yet another polygon.

FIG. 5Bis a diagram illustrating mesh500ofFIG. 5Awhen located in a high LOD area of an image screen as well as the graphics engine's application of the point pushing technique rule to remove detail from a low LOD area of mesh500, according to one embodiment of the invention. As shown, mesh500contains six horizontal strips of polygons539,540,541,542,543and544and eight vertical strips of polygons545,546,547,548,549,550,551and552when located in the high LOD area of the image screen. As seen by comparingFIGS. 5A and 5B, mesh500contains both smaller polygons and a greater number of polygons when located in the high LOD area of the image screen as compared to when located in the low LOD area. For this reason, mesh500shows more detail when located in the high LOD area of the image screen than when located in the low LOD area of the image screen.

More specifically,FIG. 5Bshows that mesh500contains four times as many polygons when located in the high LOD area of the image screen than when located in the low LOD area. The graphics engine generates the polygons such that, in the high LOD area, mesh500effectively contains four polygons for every one of the polygons depicted inFIG. 5A(each referred to as an “original polygon”). For example, the graphics engine effectively has replaced the original polygon defined by vertices516,518and522(as seen inFIG. 5A) with the polygon defined by vertices516,554and562, the polygon defined by vertices554,518and560, the polygon defined by vertices554,560and562and the polygon defined by vertices562,560and522. Likewise, the graphics engine effectively has replaced the original polygon defined by vertices526,528and530(as seen inFIG. 5A) with the polygon defined by vertices526,566and570, the polygon defined by vertices570,566and568, the polygon defined by vertices570,568and530and the polygon defined by vertices566,528and568.

FIG. 5Balso shows the child vertex of each set of parent vertices of each of the original polygons. For example, child vertex554is the child of parent vertices516and518, child vertex556is the child of parent vertices518and520, child vertex558is the child of parent vertices520and522, child vertex560is the child of parent vertices518and522and child vertex562is the child of parent vertices516and522. Similarly, child vertex564is the child of parent vertices524and526, child vertex566is the child of parent vertices526and528, child vertex578is the child of536and538, child vertex580is the child of parent vertices534and538and child vertex582is the child of parent vertices532and538.

Also shown inFIG. 5Bis an LOD boundary553that intersects mesh500to create a low LOD area on one side of LOD boundary553and a high LOD area on the other side of LOD boundary553. As discussed in more detail in conjunction withFIGS. 6 and 7, the graphics engine uses the point pushing method of the present invention to remove detail from the low LOD area of mesh500. The arrows depicted inFIG. 5Bindicate the predetermined parent vertex to which the graphics engine pushes each child vertex according to one embodiment of the point pushing technique rule. For example, according to the rule, the graphics engine pushes child vertex554to predetermined parent vertex518because both parent vertices516and518reside on the low LOD side of LOD boundary553. Similarly, according to the rule, the graphics engine pushes child vertex574to predetermined parent vertex534because both parent vertices532and534reside on the low LOD side of LOD boundary553. By contrast, according to the rule, child vertex570remains in its original position because parent vertex526resides on the low LOD side of LOD boundary553and parent vertex530resides on the high LOD side of LOD boundary553. Similarly, according to the rule, child vertex578remains in its original position because both parent vertices536and538reside on the high LOD side of LOD boundary553.

FIG. 6is a diagram illustrating the migration of the child vertices ofFIG. 5Bto the predetermined parent vertices ofFIG. 5B. As shown, the graphics engine has pushed certain child vertices located in the low LOD area of mesh500partly towards their respective predetermined parent vertices as dictated by the point pushing technique rule applied to mesh500as shown inFIG. 5B. For example, as both indicated inFIG. 5Band shown inFIG. 6, the graphics engine has pushed child vertex562towards predetermined parent vertex516, child vertices554,556and560towards predetermined parent vertex518, child vertex558towards predetermined parent vertex520, child vertex564towards predetermined parent vertex526and child vertex574towards predetermined parent vertex534. As also indicated inFIG. 5Band shown inFIG. 6, child vertices566,568,570and572as well as child vertices576,578,580and582remain in their original positions because either one (or both) of the parent vertices of each of these child vertices resides on the high LOD side of LOD boundary553.

As seen inFIG. 6, as certain child vertices in the low LOD area of mesh500migrate towards their respective predetermined parent vertices, portions of strips539,541,546,548,550and552become narrower as many of the polygons in these strips begin to collapse. By contrast, portions of strips540,542,545,547,549and551simultaneously become wider. The result is that the polygons located at the intersections of strips540and545, strips542and545, strips540and547, strips542and547, strips540and549, strips542and549and strips540and551increase in size as these polygons fill the space relinquished by the collapsing polygons. The consequence of this phenomenon is that larger and fewer polygons begin to dominate the low LOD area of mesh500, which decreases the amount of detail in that area of mesh500.

Importantly,FIG. 6shows that the graphics engine preserves the integrity of each strip in mesh500as the various child vertices migrate towards their respective predetermined parent vertices. Although several of the polygons in the strips have not retained their original shapes as right triangles, each strip nonetheless keeps its shape from one end of mesh500to the other.

Further, the point pushing method of the present invention enables the graphics engine to collapse polygons in the low LOD area of mesh500without creating or using T-junctions at the LOD boundary.FIG. 6shows that point pushing causes several transition polygons to form along LOD boundary553. Polygons610,612,614,616,618,620,622,624,626,628,630and632are examples of transition polygons. These transition polygons straddle LOD boundary553to create a small and effective transition area between the polygons in the low LOD area of mesh500and the polygons in the high LOD area. No cracks appear in the image screen because the transition polygons completely fill the transition area, thereby eliminating T-junctions at the boundary between the high resolution patch and the low resolution patch where the patches share vertices. By using the point pushing technique, the graphics engine avoids having to align a high resolution patch and a low resolution patch, the misalignment of which is a frequent source of cracks.

FIG. 7is a diagram illustrating the further migration of the child vertices ofFIG. 5Bto the predetermined parent vertices ofFIG. 5B. As shown, the graphics engine has pushed certain child vertices located in the low LOD area of mesh500much closer to their respective predetermined parent vertices as dictated by the point pushing technique rule. For example, as seen inFIG. 7, the graphics engine has pushed child vertex562closer to predetermined parent vertex516, child vertices554,556and560closer to predetermined parent vertex518, child vertex558closer to predetermined parent vertex520, child vertex564closer to predetermined parent vertex526and child vertex574closer to predetermined parent vertex534. Again, as also shown inFIG. 6, child vertices566,568,570and572as well as child vertices576,578,580and582continue to remain in their original positions because either one (or both) of the parent vertices of each of these child vertices resides on the high LOD side of LOD boundary553.

As seen inFIG. 7, as certain child vertices in the low LOD area of mesh500migrate further towards their respective predetermined parent vertices, strips539,541,546,548,550and552become even narrower as many of the polygons in those strips collapse even further. Again, by contrast, strips540,542,545,547,549and551simultaneously become even wider. The polygons located at the intersections of strips540and545, strips542and545, strips540and547, strips542and547, strips540and549, strips542and549and strips540and551continue to increase in size as these polygons continue to fill the space relinquished by the collapsing polygons. The continued consequence of this phenomenon is that a few large polygons dominate the low LOD area of mesh500, which decreases even further the amount of detail in that area of mesh500.

One can see fromFIG. 7that the graphics engine continues to preserve the integrity of each strip as the migration of the child vertices towards their respective predetermined parent vertices continues. One also can see that when the various child vertices complete their migrations, many of the polygons in strips539,541,546,548,550and552will collapse fully and disappear. The result is that the low LOD area of mesh500will look substantially similar to mesh500as depicted inFIG. 5A(when all of mesh500is located in the low LOD area of the image screen). Further, the high LOD area of mesh500will look substantially similar to mesh500as depicted inFIG. 5B(when all of mesh500is located in the high LOD area of the image screen). Lastly, as discussed above in conjunction withFIG. 6, once the child vertices complete their migrations, transition polygons will reside between the polygons in the low LOD area of mesh500and the polygons in the high LOD area, creating a continuous transition area without cracks. The consequence is that no T-junctions will exist at the boundary between the high resolution patch and the low resolution patch where the patches share vertices.

FIG. 8is a flowchart of method steps for pushing child vertices to predetermined parent vertices to remove detail from a low LOD area of an array of polygons, according to one embodiment of the invention. Although the method steps are described in the context of the graphics engine, which is a subsystem of system100illustrated inFIG. 1, any type of system, engine, processor, combination of processors or software configured to perform the method steps is within the scope of the invention.

As shown inFIG. 8, in step810, the graphics engine identifies an LOD boundary that divides an array of polygons into a low LOD area and a high LOD area. As discussed above in conjunction withFIGS. 2 through 5B, these different levels of detail are measured relative to one another. In step812, the graphics engine identifies every child vertex in the array of polygons that resides on the low LOD side of the LOD boundary. In step814, the graphics engine identifies the parent vertices of each such child vertex.

Next, in step816, the graphics engine determines which, if any, of the child vertices residing on the low LOD side of the LOD boundary migrates to a parent vertex. The graphics engine uses a point pushing technique rule to make this determination. According to one embodiment of the rule, a child vertex migrates to one of its parent vertices if both parent vertices reside on the low LOD side of the LOD boundary. A child vertex does not migrate, however, if either of its parent vertices resides on the high LOD side of the LOD boundary.

In step818, for each child vertex that migrates, the graphics engine identifies the parent vertex of the child to which the graphics engine moves that child vertex. As discussed above in conjunction withFIG. 4, each of these parent vertices is referred to as a “predetermined parent vertex.” Lastly, in step820, the graphics engine pushes or moves each migrating child vertex to its respective predetermined parent vertex.

As described above in conjunction withFIGS. 6 and 7, when the child vertices complete their migrations to their respective predetermined parent vertices, the low LOD area of the array of polygons has less detail than the high LOD area. Further, the strips of polygons in the array of polygons retain their integrity, and no cracks appear between the low LOD area of the array of polygons and the high LOD area.

To add detail to an array of polygons located in a low LOD area of an image screen, according to another embodiment of the invention, the graphics engine essentially reverses the processes described above in conjunction withFIGS. 5A through 8. The graphics engine first identifies an LOD boundary that divides the array of polygons into a high LOD area and a low LOD area. The graphics engine then identifies every predetermined parent vertex on the high LOD side of the LOD boundary. The graphics engine also identifies each child vertex having the same position as any of the identified parent vertices and the other parent vertex of each such child vertex (note that the predetermined parent vertex is one of the parents of the child vertex at the same position).

Next, the graphics engine determines which, if any, of these child vertices migrates. The graphics engine again uses a point pushing technique rule to make this determination. In one embodiment, the point pushing technique rule dictates that a child vertex migrates if both of its parent vertices reside on the high LOD side of the LOD boundary. A child vertex does not migrate, however, if either of its parent vertices resides on the low LOD side of the LOD boundary.

Lastly, the graphics engine pushes each child vertex that migrates to a predetermined location. When these child vertices complete their migrations to their respective predetermined locations, the large polygons that initially resided in the high LOD area of the array of polygons will have decreased in size. Further, the graphics engine will have generated additional polygons in the high LOD area of the array of polygons by connecting the migrating child vertices to each other and to the parent vertices residing in the high LOD area. The result is that the high LOD area of the array of polygons will have both smaller polygons and a greater number of polygons than the low LOD area, which increases the amount of detail in the high LOD area.

Similar to when removing detail from an array of polygons, the graphics engine preserves the integrity of the strips of polygons in the array of polygons when adding detail to the high LOD area of the array. Further, the graphics engine generates transition polygons on either side of the LOD boundary, which prevents cracks from appearing between the low LOD area of the array of polygons and the high LOD area.

The invention has been described above with reference to specific embodiments. Persons skilled in the art, however, will understand that various modifications and changes may be made thereto without departing from the broader spirit and scope of the invention as set forth in the appended claims. For example, for simplicity of illustration, the embodiments of the invention referenced in the discussion and examples set forth above include arrays of polygons containing small numbers of polygons with simple geometries (i.e., triangles). Other embodiments of the invention, though, can include arrays of polygons containing any number of polygons with any type of shape, whether simple or complex. The foregoing description and drawings are, accordingly, to be regarded in an illustrative rather than a restrictive sense.