Efficient triangular shaped meshes

The present invention relates generally to graphics, and in particular to a triangular mesh rendered from a triangular graphics graphic element.

In computer graphics, various graphical shapes are created and rendered by using the underlying graphic building blocks known as graphics graphic elements. One widely used graphics graphic element is a triangular graphics graphic element. Triangular graphic elements can be aggregated into a triangular strip. A triangular strip consists of a row of triangular graphic elements assembled together in alternating top orientations, both upward and downward. A triangular strip represents a rectangular grid consisting of a single triangle (ie, a "three-vertex" triangle strip), a single quadrilateral (ie, a "four-vertex" triangle strip), or multiple vertically assembled triangular strips. It is generally a flexible unit for computer graphic operations because it can. A rectangular grid is generally defined as a rectangular two-dimensional set of multiple rows of triangular strips, where internal vertices are delivered in duplicate during delivery.

The use of triangular strips can significantly improve data utilization efficiency for sending and rendering large sets of triangular graphic elements to create a single column. This is because in a triangular strip, the number of vertices per graphical triangular shape graphic element approaches a one-to-one ratio, which is the minimum number to render (ie, graphically recreate and display) the triangular strip. This is because it requires sending the vertices of.

<p> However, using triangular strips to render a rectangular grid is inefficient. In general, the inefficiency is that the vertices of each column inside the rectangular grid must be sent out in duplicate. For example, a rectangular grid of 24 isosceles triangles (8 triangles per row in 3 columns) actually requires 30 strip vertices to be rendered.</p><p> Subdivision planes, i.e., a graphical method of dividing a given shape into subordinate shapes of components, are becoming more widely used in graphics. However, subdivision is significantly inefficient with respect to data transfer overhead, especially when triangular strip data occurs. This is because, in general, similar to the rectangular grid, the internal column vertices are sent in duplicate. At the limit (ie, where the subdivision level approaches infinity), the efficiency approaches 50%.</p><p> Another method for graphical design is to directly support the underlying graphical graphic elements so that the inner column vertices do not need to be sent in duplicate. This method creates a mesh, such as a rectangular mesh. A rectangular mesh is generally defined as a rectangular set of graphics graphic elements, which does not result from a two-dimensional set of multiple triangular strips.</p><p> In one known way to create a rectangular mesh, the renderer caches the vertices of both previous columns of a set of triangular or quadrilateral graphic elements in a given column. Then, instead of receiving the vertices of both columns for the next column of aggregated triangular or quadrilateral shape elements, the renderer will then use the next column of aggregated triangular or quadrilateral shape shapes. It only receives the vertices of the top row for the element, thereby reducing the sending information needed to draw the rectangular mesh and increasing efficiency. Rendering a rectangular mesh is more efficient than rendering a rectangular grid created by a collection of graphic element strips.</p><p> However, while processor performance is superior to memory and bus performance, the use of subdivided surfaces has increased the demand for higher throughput. Therefore, it is necessary to use graphics graphic elements to render subdivided triangles that overcome the shortcomings of current methods.</p>

<p> The present invention uses video information related to triangular meshes. The present invention obtains a plurality of adjacent triangular graphic elements in the first column. Each triangular graphic element is defined as having both at least one lower vertex and at least one upper vertex. At least one lower vertex and at least one upper vertex of the selected triangular shape element in the first column are cached. At least one bottom vertex of the selected triangle shape element is overwritten by at least one top vertex of the selected triangle shape element. One or more new top vertices of the selected triangular shape element in the next column are cached, thereby producing a triangular mesh.</p>

In the following description, many specific explanations have been made in order to fully understand the present invention. However, those skilled in the art will recognize that the present invention can be practiced without such specific description. In other examples, well-known elements are shown in the form of conceptual or block diagrams so that unnecessary explanations do not obscure the invention. Moreover, for the most part, explanations for network communications, telecommunications, electrical-magnetic signal technology, etc. are not considered necessary to obtain a complete understanding of the present invention and will be understood by those skilled in the art. Omitted because it is considered to be within range.

It is further noted that all functions described herein can be performed by either hardware or software, or a combination thereof, unless otherwise indicated. In a preferred embodiment, however, unless otherwise indicated, the function follows the code, eg, computer program code, software and / or integrated circuits coded to perform such a function. , Performed by a processor, such as a computer or electronic data processor. In a more preferred embodiment, the computer program is incorporated into or within a computer program product, such as a floppy (registered trademark) disk or compact disk, or other storage device.

Referring to FIG. 1A, an exemplary three-dimensional octahedron 100 subdivided into triangular shapes 105 is shown, the triangular shape being one triangular base of the octahedron 100. The octahedron 100 is further subdivided into triangular mesh 150. The triangular mesh 150 is subdivided into triangular graphic elements 155. Therefore, the triangular shape 105 is also composed of the triangular mesh 150. The vertex elements of one unique set of defined vertices are shared with the other triangular graphic elements 155, but each triangular graphic element 155 has its own unique set of defined vertices.

In general, the subdivision of triangle shape 105 allows more effectively the creation or generation of a given shape, eg, triangle shape (ie, numerical calculation) and more accurate depiction (ie, final display). One useful subdivision unit is a triangular graphic element. In other words, a given shape, such as the triangular shape 105, is finally subdivided into constituent elements, such as the triangular graphic element 155. The final subdivision of the triangular shape 105 into the triangular graphic element 155 is one extremely useful method in a graphic system.

In FIG. 1A, the triangular graphic elements 155 of the triangular shape 105 are defined in relation to each other to form the triangular mesh 150. Generally, in FIG. 1A, each triangular mesh 150 results from both a subdivision of the triangular shape 105 and further subdivision into the triangular graphic element 155 of this subdivision. Therefore, since the triangular shape 105 is composed of the triangular graphic element 155 and the triangular mesh 150, the triangular shape 105 is also one triangular mesh.

The triangular shape 105, which has its constituent unique vertices of various triangular graphic elements 155, is commonly generated by a microchip or some other graphics computing device. Any unique vertices are then sent to the video display device for rendering. The unique vertices of the triangular graphic element 155 are generally defined as the vertices obtained to render the graphical graphic element, but these vertices are not duplicated on delivery. The unique vertices are received by the video display device and used to render the Triangular Mesh 150.

In one embodiment, the rendering of the Triangle Mesh 150 on the display device is performed by sending the vertices in the bottom row of the triangle strips, then the vertices in the top row. Triangular entity elements are not rendered until the top vertices are received. In another embodiment, rendering of the Triangle Mesh 150 is typically done by sending out both the top and bottom vertices of the first column of the triangle graphics graphic element 155. These transmissions are made from a graphics computer or processor and then store vertices in a local storage center, such as a video device vertex cache. The video device renders the first column of adjacent triangular graphic elements 155. The video buffer then overwrites the cached unique lower vertices in the first column of the graphical graphic element 155 with the cached unique upper vertices in the first column of the graphical graphic element 155. This creates a new unique set of bottom vertices that can be used to render the next column of graphical entity elements 155. The use of overrides eliminates the need for substantial overlap of vertex transmissions that is common between columns between the graphics calculator and the display device.

The graphics calculator then sends the unique vertices at the top of the next column of triangular graphic elements 155 of the triangular mesh 150 to the video device. The video display device renders a new column. The process continues until it reaches the top of the triangle, and this last unique vertex is sent for the top triangle graphic element 155. The calculation is done taking into account reducing the number of unique vertices for each higher column.

Therefore, the rendered triangle shape 105 is composed of the triangle mesh 150. In general, the rendered shape is not constructed by a triangular grid. The triangular grid is usually defined as a two-dimensional set of triangles in a multi-column triangle strip, and the internal vertices are sent in duplicate at the time of sending. The triangular mesh 150 is created and rendered by sending and using unique vertices rather than by a collection of triangular strips, thereby significantly reducing the inefficiency of sending data.

FIG. 1B shows a triangular mesh 150, which is further subdivided and composed of triangular graphic elements 155. In the embodiment described, the triangular mesh 150 is composed of 16 triangular graphic elements 155. Triangular graphics graphic elements are numbered from 1 to 16 and are arranged in four columns. The first column is composed of triangular graphic elements 1-7. The second column is composed of triangular graphic elements 8-12. The third column is composed of triangular graphic elements 13-15. Finally, the fourth column is composed of the triangular graphic elements 16. Although shown as composed of four columns, those skilled in the art will appreciate that, in yet another embodiment, the triangular mesh 150 can be composed of triangular graphic elements 155 in columns larger than four columns.

Within each column, the bottom of the first and last triangular graphic elements 155 in the selected column is oriented towards the bottom of the triangular mesh 150. The remaining triangular graphic elements alternate in direction. In other words, the triangular graphic element "1" whose top is oriented toward the top of the triangular mesh 150 and whose top is directed toward the bottom of the triangular mesh 150 "2". , And so on. This alternation continues column by column until the last triangular graphic element is reached, where the top of the last triangular graphic element is oriented towards the top of the triangular mesh 150.

The triangular graphic elements "1" to "7" in column 1 have vertices associated with them. The triangular graphic element "1" in column 1 is defined by the lower vertices "1" and "2" and the upper vertex "6". The triangular graphic element "2" in column 1 is defined by the lower vertices "2" and the upper vertices "6" and "7". The triangular graphic element "3" in column 1 is defined by the lower vertices "2" and "3" and the upper vertex "7", and so on.

In the triangle mesh 150, the upper vertices of the triangular graphics graphic elements in column 1 are defined as the lower vertices of the triangular graphic elements in column 2. For example, the vertex "6" which is the upper vertex of the triangular graphic element "1" in column 1 and the vertex "7" which is the upper vertex of the triangular graphic element "3" in column 1 are the triangular graphic element "8" in column 2. It is defined as the lower apex of. The vertex "7" which is the upper vertex of the triangular graphic element "3" in column 1 and the vertex "8" which is the upper vertex of the triangular graphic element "5" in column 1 are the lower part of the triangular graphic element "10" in column 2. Determined as the apex. The vertex "7", which is the upper vertex of the triangular graphic element "3" in column 1, is also defined as the lower vertex of the triangular graphic element "9" in column 2. Redefining the top vertices of the previous column as the bottom vertices of the next column continues until the top vertices of the triangular graphic elements in the last column are defined. In the example shown, this is the triangular figure element "16".

Within the triangle mesh 150, the lower vertices of each triangular graphic element in the upper column (eg, column 3) are defined as a function of the upper vertices of the upper vertices of the triangular graphic element in the lower column (eg, column 2). Therefore, the triangular mesh 150 can be rendered by sending only unique vertices. The use of only unique vertices to construct a triangular mesh is less than the number of vertices required to assemble a triangular grid of the same shape and size from a vertical set of multiple triangular strips. Requires sending.

Rendering a triangular grid assembled from multiple triangular strips requires non-unique vertices. This is because each row of aggregated triangular strips that creates the triangular grid is defined independently of the continuous triangular strips of the triangular grid, and therefore more to define independently of the triangular mesh. Need a vertex.

A comparison of the efficiencies of the triangular mesh 150 and the triangular grid is shown in the following table. Levels are generally defined as the number of halves performed. That is, level "0" is one triangle, level "1" is a bisector triangle, and level "2" is a bisector triangle in which each bisector is further bisected. The same applies hereinafter. The alternative level is generally defined as a triangle subdivided into the same number of subdivisions as a given number. In other words, an alternative level of 0 represents one triangle, an alternative level of 1 represents a subdivided bisector triangle, and an alternative level of 2 represents a subdivided bisector triangle. The same applies hereinafter. In other words, the alternative level involves subdividing a triangle into n-parts (n-sections), such as bisectors, trisections, and so on.

Unique mesh vertices are generally defined as the number of vertices required to assemble a subdivided triangular mesh, and triangular strip vertices are required to assemble a subdivided triangular grid from triangular strips. Generally defined as the number of vertices. "Efficiency" is a comparison of the efficiency of using triangular strip vertices to assemble a triangular shape, as opposed to using the unique vertices of a triangular mesh to create a triangular shape.

<tables num="1"><img file="JP4009235B2_D0001.tif" /></tables>

Therefore, rendering a triangular shape with unique vertices that create a triangular mesh is generally more efficient than rendering with strip vertices that create a triangular grid.

Figure 2 shows a method 200 for creating and rendering a triangular mesh 150. In general, method 200 calculates the vertices of a graphics graphic element that represents the subdivision of triangle shape 105. In method 200, the subdivision is composed of triangular graphic elements. Method 200 then sends out vertices that are unique to the video device. The video device renders the triangular graphics graphic elements as a triangular mesh.

In step 210, the graphics processor calculates and obtains the unique vertex coordinates of the subdivided triangular region 105. The triangular area 105 is then subdivided into triangular graphics graphic elements to create a triangular mesh. In one embodiment, subdividing involves halving. As will be appreciated by those skilled in the art, methods of subdividing into other subdivided portions are within the scope of the present invention.

In step 220, the graphics processor sends a plurality of unique vertices for the selected column to the video display. If the unique vertices sent include the bottom vertices of the bottom column, then both the top and bottom vertices of the first column are sent. There, first all the lower vertices are sent, then all the upper vertices are sent. If the vertices sent do not include the bottom vertices of the bottom column, then only the top vertices of that column are sent.

In step 230, the video device caches the values of the vertices of the triangular graphic elements acquired in step 210 and sent out in step 220. There, first all the lower vertices are sent, then all the upper vertices are sent. If the vertices sent include the bottom vertices of the bottom row, both top and bottom vertices are cached in step 230. If the received vertices do not contain the bottom vertices of the bottom column, then only the top vertices of that column are sent in step 220, received in step 230, and cached.

In step 240, the video device renders one or more triangular graphic elements 155. In one embodiment, the rendering process performed by the video device further includes lighting, shading, and texture / displacement mapping of the triangular graphic element 155.

In step 250, if the graphical object to be rendered is finished, that is, if the top vertices of the top triangle graphic element are received, then stop step 275 is performed. In other words, the triangle mesh 150 is rendered. If the top vertices of the top triangle graphic element are still not received, step 260 is performed.

In step 260, the video display overwrites the value of the lower vertex of the previously submitted column with the value of the upper vertex of the previously submitted column. Therefore, the top vertex of the previous column becomes the bottom vertex of the next column. In step 270, the next column to be sent is incremented (for example, from column 2 to column 3). In step 220, the graphics processor sends out the top vertices of this new column, and so on.

Figure 3 discloses the C pseudo-code subroutine drawTriangualarMesh () for rendering the triangle mesh 150 with a video device. In general, the MAX_MESH_WIDTH variable is equal to the maximum value of the vertices in the bottom column of a subdivided triangle, eg, Triangle Mesh 150. In Figure 3, MAX_MESH_WIDTH is the maximum permissible "width" parameter.

In general, renderTriangle () is called to render a 0,1 or 2 triangle shape element for each received vertex. Zero triangle graphic elements are rendered with respect to the vertices of the first (width) column. One triangular shape element is rendered for the first vertex of each column. The two triangular graphic elements are rendered for each subsequent vertex. The subroutine renderTriangle () also renders the top row of triangular entity elements. This continues to the top column, which consists of a single triangular graphic element. Those skilled in the art will understand the use and application of "C" pseudocode. Therefore, the "C" pseudocode is not described in detail.

It is understood that the present invention can take many forms and examples. Therefore, various modifications can be made to the above-mentioned ones without departing from the spirit or scope of the present invention.

As the present invention has thus been described with reference to some of its preferred embodiments, the disclosed embodiments are examples rather than substantially limiting, with a wide range of modifications, modifications, modifications and replacements. However, it is noted that, as intended in the disclosure described above, in some examples some features of the invention can be used without the corresponding use of other features.

In summary, the following matters will be disclosed with respect to the constitution of the present invention. (1) A method that uses video information related to a triangular mesh, including the step of retrieving multiple adjacent triangular shaped graphic elements in the first column, where each triangular shaped graphic element has at least one lower vertex. And selected as having both at least one top vertex and including a step to cache both at least one bottom vertex and at least one top vertex of the selected triangular graphic element in the first column. Includes the step of overwriting at least one bottom vertex of the selected triangle shape element with at least one top vertex of the selected triangle shape element. A method that includes a step in the next column that caches one or more new top vertices of the selected triangular shape element, thereby generating a triangular mesh. (2) The method according to (1) above, further comprising the step of rendering the triangular mesh. (3) The method according to (1) above, wherein the acquisition step further includes a step of subdividing the triangular shape into triangular graphic elements. (4) The method according to (3) above, wherein the subdivision step comprises creating substantially equal bisectors. (5) The method according to (3) above, wherein the subdivision step includes creating approximately equal n equal parts. (6) A method of transmitting display information, including the step of subdividing a triangular shape into triangular graphic elements. A method that includes steps to render a triangular mesh from multiple triangular shape elements. (7) The method according to (6) above, wherein the subdivision step includes repeatedly executing substantially equal halves. (8) The method according to (6) above, wherein the subdivision step comprises creating approximately equal n equal parts. (9) The method according to (6) above, wherein the subdivision step further divides the subdivided portion into further subdivided portions and does not exceed the maximum capacity of the vertex cache. (10) A device that sends out and renders a triangular mesh composed of a plurality of graphics triangle graphic elements having at least one lower vertex and at least one upper vertex, and is a device for transmitting and rendering a plurality of adjacent graphics triangle graphic elements. With a graphics processor that you can use to get It can be used to cache both at least one bottom vertex and at least one top vertex for each triangle shape element, with at least one bottom vertex for each graphics triangle shape element and at least one top vertex for each triangle shape element. A device with a display device that can be further used to overwrite with and can be further used to cache at least one new top vertex of the next top column of triangular graphic elements. (11) The device according to (10) above, wherein the graphics processor can be used to subdivide a triangular shape into triangular graphic elements and thereby create a triangular mesh. (12) The apparatus according to (11) above, wherein subdividing involves creating substantially equal halves. (13) The apparatus according to (11) above, wherein subdividing involves creating substantially equal n equal parts. (14) A method of using a triangular mesh sending and rendering protocol that includes a first step of rendering a single triangular graphic element upon receiving the top vertices of a column, the top vertices of the column being said. Not the last vertex of the column A method that includes a second step of rendering two triangular shape elements when the last top vertex of a column is received, and a step of reducing the mesh width after receiving the column of vertices. (15) The method according to (14) above, wherein the first step of rendering is to use a triangular graphic element that can be extended to create a triangular mesh. (16) The method according to (14) above, wherein the subdivision step divides one shape to be sent and rendered into subdivision portions. (17) The method according to (16) above, wherein the subdivision step comprises creating substantially equal bisectors. (18) The method according to (16) above, wherein the subdivision step comprises creating approximately equal n equal parts. (19) A computer-readable recording medium that records a computer program that uses video information related to a triangular mesh, said computer program acquiring multiple adjacent triangular graphic elements in the first column. Functional, each triangular graphic element is defined as having both at least one lower vertex and at least one upper vertex. The ability to cache both at least one bottom vertex and at least one top vertex of the selected triangle shape element in the first column, and at least one bottom vertex of the selected triangle shape element for the selected triangle. Computers have the ability to overwrite at least one top vertex of a shape element and the ability to cache one or more new top vertices of the selected triangle shape element in the next column, thereby generating a triangle mesh. A recording medium to be realized. (20) A processor that includes a computer program and uses video information related to a triangular mesh, said computer program that obtains computer code for obtaining multiple adjacent triangular shape graphic elements in the first column. Each triangle-shaped graphic element is defined as having both at least one lower vertex and at least one upper vertex, and is defined as having at least one lower vertex and at least one of the selected triangular graphic elements in the first column. With computer code that caches both the top vertices One or more of the selected triangle shape elements in the next column, with computer code that overwrites at least one bottom vertex of the selected triangle shape element with at least one top vertex of the selected triangle shape element. A processor that uses video information related to a triangle mesh, with computer code that caches the new top vertices of the triangle mesh.

<figref num="1A">It is a figure which shows the 3D shape which has the triangular mesh which is further subdivided into the triangular graphics graphic element.</figref><figref num="1B">Triangular Graphics It is a diagram showing a more detailed triangular mesh further subdivided into graphic elements.</figref><figref num="2">It is a figure which shows the method of rendering using the display information associated with a triangular mesh.</figref><figref num="3">It is a figure which shows the "C" pseudo code subroutine drawTriangualarMesh () which can be used for rendering a triangular mesh by a video apparatus.</figref>

Code description

100 Octahedron 105 Triangle Shape 150 Triangle Mesh 155 Triangle Shape Element