Tessellation engine and applications thereof

Disclosed herein methods, apparatuses, and systems for performing graphics processing. In this regard, a processing unit includes a tessellation module and a connectivity module. The tessellation module is configured to sequentially tessellate portions of a geometric shape to provide a series of tessellation points for the geometric shape. The connectivity module is configured to connect one or more groups of the tessellation points into one or more primitives in an order in which the series of tessellation points is provided.

BACKGROUND

1. Field of the Invention

The present invention is generally directed to computing operations performed in computing systems. More particularly, the present invention is directed to a processing unit (such as, for example, a graphics processing unit (GPU)) that performs computing operations and applications thereof.

2. Background Art

A GPU is a complex integrated circuit that is specially designed to perform data-parallel computing tasks, such as graphics-processing tasks. A GPU may, for example, execute graphics-processing tasks required by an end-user application, such as a video-game application.

FIG. 1illustrates that several layers of software may exist between an end-user application102and a GPU108. End-user application102communicates with an application-programming interface (API)104. API104allows end-user application102to output graphics data and commands in a standardized format, rather than in a format that is dependent on GPU108. API104communicates with a driver106. Driver106translates standard code received from API104into a native format of instructions understood by GPU108. Driver106is typically written by the manufacturer of GPU108. GPU108then executes the instructions received from the driver.

Several APIs are commercially available. A relatively large segment of end-user applications are compatible with DirectX® developed by Microsoft Corporation of Redmond, Wash. To reach this relatively large segment of end-user applications, a GPU should be compatible with DirectX®.

A recent version of DirectX is known as DirectX 11 (“DX11”). DX11 uses a unified shader model in which a GPU implements a sequence of shaders. For example,FIG. 2illustrates an example sequence of shaders200specified by DX11. As illustrated inFIG. 2, the GPU executes a vertex shader202, then a hull shader204, then a tessellation shader206, and then one or more additional shaders208to provide results data. In the unified shader model, intermediate results provided by previously executed shaders (such as, hull shader204) may be used by the GPU to execute subsequent shaders (such as, tessellation shader206). Unfortunately, DX11 includes schemes that are not optimal from a GPU hardware perspective.

What is needed, therefore, are systems, apparatuses, and methods that are not only compatible with DX11, but also operate efficiently from a GPU hardware perspective.

SUMMARY OF EMBODIMENTS OF THE INVENTION

Embodiments of the present invention meet the above-described needs. For example, an embodiment of the present invention provides a graphics-processing method implemented in a processing unit. This graphics-processing method includes sequentially tessellating portions of a geometric shape to provide a series of tessellation points for the geometric shape. This graphics-processing method further includes connecting one or more groups of the tessellation points into one or more primitives in an order in which the series of tessellation points is provided.

Another embodiment of the present invention provides a processing unit that includes a tessellation module and a connectivity module. The tessellation module is configured to sequentially tessellate portions of a geometric shape to provide a series of tessellation points for the geometric shape. The connectivity module is configured to connect one or more groups of the tessellation points into one or more primitives in an order in which the series of tessellation points is provided.

A further embodiment of the present invention provides a computing system that includes a system memory, a processing unit, and a bus coupled to the system memory and the processing unit. The processing unit includes a tessellation module and a connectivity module. The tessellation module is configured to sequentially tessellate portions of a geometric shape to provide a series of tessellation points for the geometric shape. The connectivity module is configured to connect one or more groups of the tessellation points into one or more primitives in an order in which the series of tessellation points is provided.

BRIEF DESCRIPTION OF THE DRAWINGS/FIGURES

The accompanying drawings, which are incorporated herein and form part of the specification, illustrate the present invention and, together with the description, further serve to explain the principles of the invention and to enable a person skilled in the relevant art(s) to make and use the invention.

FIG. 1is a block diagram illustrating an example work flow for processing graphics.

FIG. 2illustrates example shaders included in a graphics pipeline of an example three-dimensional graphics API.

FIG. 3is a block diagram of an example computing system in accordance with an embodiment of the present invention.

FIG. 4illustrates additional components included in an example computing system according to an embodiment of the present invention.

FIG. 5is a block diagram of an example GPU in accordance with an embodiment of the present invention.

FIG. 6is a block diagram of additional details of the GPU ofFIG. 5.

FIG. 7illustrates example functional blocks of a processing unit for executing a tessellation shader in accordance with an embodiment of the present invention.

FIG. 8illustrates an example method for generating tessellation points, implemented by a tessellation module ofFIG. 7, in accordance with an embodiment of the present invention.

FIGS. 9A-Cillustrates example sequences for generating tessellation points of a patch in accordance with embodiments of the present invention.

FIG. 10illustrates an example method for connecting tessellation points into primitives, implemented by a connectivity module ofFIG. 7, in accordance with an embodiment of the present invention.

FIG. 11illustrates example lookup tables (LUTs) used for determining connectivity in accordance with an embodiment of the present invention.

FIG. 12illustrates an example method for re-using vertices of primitives, implemented by a connectivity module ofFIG. 7, in accordance with an embodiment of the present invention.

FIG. 13illustrates how tessellation points ofFIG. 9Amay be connected into primitives in accordance with an embodiment of the present invention.

DETAILED DESCRIPTION

As mentioned above with respect toFIG. 2, a typical graphics pipeline includes a plurality of shaders, including a tessellation shader206. The input to the tessellation shader206includes a patch—i.e., a geometric shape (such as, a rectangle, a triangle, or a line). One purpose of the tessellation shader206is to tessellate the patch into a plurality of points. During subsequent stages of the graphics pipeline, the points may be subjected to further processing. For example, the points may be connected into primitives (e.g., triangles). A processing unit according to an embodiment of the present invention includes a tessellation engine configured to efficiently execute tessellation shader206from a hardware perspective, thereby providing better performance (e.g., faster processing) with a reduced area footprint compared to conventional processing units.

For illustrative purposes only, and not limitation, embodiments of the present invention will be described herein in terms of a GPU. A person skill in the relevant art(s) will appreciate, however, that the present invention may be applied to other types of processing units—such as central processing units and coprocessors—that execute a tessellation shader. These other types of processors are contemplated within the spirit and scope of the present invention.

According to an embodiment of the present invention, a GPU dynamically uses an off-chip memory and an on-chip memory for execution of the tessellation shader, and applications thereof. The off-chip memory is referred to as an off-chip local data share (LDS), and the on-chip memory is referred to as an on-chip LDS. If tessellation is low (e.g., fewer than 100 vertices are involved), then the on-chip LDS is used. If tessellation is high (e.g., greater than 100 vertices are involved), then the off-chip LDS is used. The GPU driver indicates through a register write (e.g., one bit) whether the on-chip or off-chip LDS is used. The decision whether to use the on-chip or off-chip LDS for tessellation output is made dynamically.

Another embodiment of the present invention is directed to a tessellation engine that enables a GPU to generate points for tessellation in a manner that is compatible with a scheme specified by DX11, but that is more efficient from a hardware perspective than the scheme specified by DX11. As mentioned above, tessellation is performed on a patch, i.e., a geometric shape (such as, a rectangle, a triangle, or a line). The tessellation engine of the GPU is configured to tessellate the patch to provide tessellation points in an order in which a connectivity engine is configured to connect the tessellation points. In contrast, the DX11 algorithm generates all the tessellation points and stores the tessellation points in memory, and then retrieves these tessellation points from memory during connectivity processing. Unlike the DX11 algorithm, the tessellation engine of an embodiment of the present invention does not need to store the tessellation points in memory, because the tessellation engine are generated in the order in which they are processed in the connectivity engine.

In an embodiment, the tessellation engine includes two math units to generate the tessellation points. A first math unit is configured to generate points for an outside edge of a patch, and a second math unit is configured to generate points for an inside edge of the patch. Each math unit includes an output FIFO and an input FIFO. The output FIFOs have two read ports, enabling two points to be read per clock cycle. As a result, the two math units of the tessellation engine can generate points of a primitive (e.g., a triangle) in a single clock cycle. After several clock cycles, the tessellation engine generates all the points of the patch by following a serpentine path. In this way, the points of the patch are generated on the fly in a manner that is appropriate for subsequent connectivity processing, but that does not require a memory to store all points of the patch as specified by DX11.

A further embodiment of the invention is directed to a GPU, and applications thereof, that provides only unique tessellated-point data, thereby saving processing resources. In an embodiment, the GPU includes a tessellation module and a connectivity module. The tessellation module provides tessellated-point data to the connectivity module. The connectivity module creates primitives based on the topology (e.g., point, line, or triangle) of the tessellated-point data. The connectivity module sends out the data in strip form and sends relative indices for the primitives.

A still further embodiment of the present invention is directed to a tessellation engine, and applications thereof, that selects a lookup table (LUT) from a plurality of LUTs to determine whether tessellation points of a patch are connected. By selecting the one LUT from the plurality of LUTs, the tessellation engine of an embodiment of the present invention can provide one primitive per clock cycle. In contrast, using a single LUT as specified by DX11 may require up to 32 clock cycles to provide a primitive.

Further details of an example tessellation engine in accordance with an embodiment of the present invention are described below. Before providing these details, however, it is helpful to describe an example system in which such a tessellation engine may be implemented.

II. An Example System

FIG. 3is a block diagram of a computing system300according to an embodiment. Computing system300includes a CPU302, a GPU310, and may optionally include a coprocessor312. In the embodiment illustrated inFIG. 3, CPU302and GPU310are included on separate integrated circuits (ICs) or packages. In other embodiments, however, CPU302and GPU310, or the collective functionality thereof, may be included in a single IC or package.

In addition, computing system300also includes a system memory304that may be accessed by CPU302, GPU310, and coprocessor312. In embodiments, computing system300may comprise a supercomputer, a desktop computer, a laptop computer, a video-game console, an embedded device, a handheld device (e.g., a mobile telephone, smart phone, MP3 player, a camera, a GPS device, or the like), or some other device that includes or is configured to include a GPU. Although not specifically illustrated inFIG. 3, computing system300may also include a display device (e.g., cathode-ray tube, liquid crystal display, plasma display, etc.) for displaying content (e.g., graphics, video, etc.) of computing system300. The display device is used to display content to a user (such as, when computing system300comprises a computer, video-game console, or handheld device).

GPU310assists CPU302by performing certain special functions (such as, graphics-processing tasks and data-parallel, general-compute tasks), usually faster than CPU302could perform them in software. In embodiments, GPU310may be integrated into a chipset and/or CPU or other processors. Additional details of GPU310are provided below.

Coprocessor312also assists CPU302. Coprocessor312may comprise, but is not limited to, a floating point coprocessor, a GPU, a video processing unit (VPU), a networking coprocessor, and other types of coprocessors and processors as would be apparent to a person skilled in the relevant art(s).

GPU310and coprocessor312communicate with CPU302and the system memory over a bus314. Bus314may be any type of bus used in computer systems, including a peripheral component interface (PCI) bus, an accelerated graphics port (AGP) bus, a PCI Express (PCIE) bus, or another type of bus whether presently available or developed in the future.

In addition to system memory304, computing system300further includes local memory306and local memory308. Local memory306is coupled to GPU310and may also be coupled to bus314. Local memory308is coupled to coprocessor312and may also be coupled to bus314. Local memories306and308are available to GPU310and coprocessor312respectively in order to provide faster access to certain data (such as data that is frequently used) than would be possible if the data were stored in system memory304.

In an embodiment, GPU310and coprocessor312decode instructions in parallel with CPU302and execute only those instructions intended for them. In another embodiment, CPU302sends instructions intended for GPU310and coprocessor312to respective command buffers.

Although not specifically illustrated inFIG. 3, computing system300may also include or be coupled to a display device (e.g., cathode-ray tube, liquid crystal display, plasma display, or the like). The display device is used to display content to a user (such as, when computing system300comprises a computer, video-game console, or handheld device).

III. Additional Details of an Example Computing System

As set forth above,FIG. 3illustrates an example computing system300of an embodiment of the present invention.FIG. 4illustrates additional components that may be included in an example computing system400in accordance with an embodiment of the present invention.

Computing system400includes one or more processing units404. Processing unit(s)404may be a general-purpose processing unit (such as, CPU302ofFIG. 3) or a special-purpose processing unit (such as, GPU310ofFIG. 3). Processing unit(s)404is (are) connected to a communication infrastructure406(e.g., a communications bus (such as bus314ofFIG. 3), a cross-over bar, or a network).

Computing system400also includes a display interface402that forwards graphics, text, and other data from communication infrastructure406(or from a frame buffer not shown) for display on display unit430(such as, a liquid crystal display).

Computing system400also includes a main memory408, preferably random access memory (RAM), such as system memory304ofFIG. 3. In addition, computing system400may also include a secondary memory410. The secondary memory410may include, for example, a hard disk drive412and/or a removable storage drive414, representing a floppy disk drive, a magnetic tape drive, an optical disk drive, etc. The removable storage drive414reads from and/or writes to a removable storage unit418in a well-known manner. Removable storage unit418represents a floppy disk, magnetic tape, optical disk, etc. which is read by and written to by removable storage drive414. As will be appreciated, the removable storage unit418includes a computer-readable storage medium having stored therein computer software and/or data.

In alternative embodiments, secondary memory410may include other similar devices for allowing computer programs or other instructions to be loaded into computing system400. Such devices may include, for example, a removable storage unit422and an interface420. Examples of such may include a program cartridge and cartridge interface (such as that found in video game devices), a removable memory chip (such as an erasable programmable read only memory (EPROM), or programmable read only memory (PROM)) and associated socket, and other removable storage units422and interfaces420, which allow software and data to be transferred from the removable storage unit422to computing system400.

Computing system400may also include a communications interface424. Communications interface424allows software and data to be transferred between computing system400and external devices. Examples of communications interface424may include a modem, a network interface (such as an Ethernet card), a communications port, a Personal Computer Memory Card International Association (PCMCIA) slot and card, etc. Software and data transferred via communications interface424are in the form of signals428which may be electronic, electromagnetic, optical or other signals capable of being received by communications interface424. These signals428are provided to communications interface424via a communications path (e.g., channel)426. This channel426carries signals428and may be implemented using wire or cable, fiber optics, a telephone line, a cellular link, an radio frequency (RF) link and other communications channels.

In this document, the term “computer-readable storage medium” is used to generally refer to media such as removable storage drive414and a hard disk installed in hard disk drive412. These computer program products provide software to computing system400.

Computer programs (also referred to as computer control logic or instructions) are stored in main memory408and/or secondary memory410. Computer programs may be loaded into computing system400using removable storage drive414, hard drive412, or communications interface424. Such computer programs, when executed, enable the computing system400to perform features of embodiments of the present invention, as discussed herein. For example, the computer programs, when executed, enable at least one of processing unit404to execute a tessellation shader in accordance with an embodiment of the present invention. An example of the execution of such a tessellation shader is described below.

IV. An Example GPU

FIG. 5is a block diagram of an example GPU310that executes a tessellation shader in accordance with an embodiment of the present invention. As shown in the embodiment ofFIG. 5, GPU310is coupled to a command buffer502and includes input logic504, a execution unit506, and a cache508.

Input logic504performs pre-processing on the graphics-processing tasks and general-compute tasks. Input logic504identifies all the shader programs associated with a graphics-processing and/or general-compute task, and schedules when each shader program can be launched in execution unit506based on input and output data that will be available. For example, a particular graphics-processing task may require the execution of a first shader program and a second shader program, wherein the second shader program is dependent on data generated by the first shader program. In accordance with this example, input logic504identifies the first and second shader programs and schedules the first shader program to be executed before the second shader program, so that the data for the second shader program will be available when the second shader program is launched. After pre-processing the graphics-processing and general-compute tasks, input logic504issues these tasks to execution unit506.

Execution unit506includes a plurality of compute resources (e.g., single-instruction, multiple-data (SIMD) devices). The tasks to be executed by execution unit506may be broke up into a plurality of work loads, wherein work loads may be issued to different compute resources (e.g., SIMDs) in parallel. Input logic504keeps track of which workloads are processed by the different compute resources (e.g., SIMDs) within execution unit506, enabling a plurality of threads to execute in parallel. In an embodiment, for example, more than 30,000 threads may execute in execution unit506at any one time. The results of the operations of execution unit506are sent to an output buffer (such as, for example, a frame buffer). The output buffer may be included on the same chip as GPU310or may be included in an off-chip memory.

Cache508stores data that is frequently used by execution unit506. When data is needed by execution unit506to execute a shader program, first a request is made to cache508. If there is a cache hit in cache508(i.e., the requested data is in cache508), the data is forwarded to execution unit506. If there is a cache miss in cache508(i.e., the requested data is not in cache508), the request data is retrieved from off-chip memory. In an embodiment, cache508comprises one or more level 1 (L1) caches and one or more level 2 (L2) caches, wherein the L1 caches have less storage capacity but provide faster data access than the L2 caches.

In a unified shader model, a GPU executes a sequence of shaders. To execute the shaders, the GPU includes a plurality of SIMDs. Each SIMD is associated with its own local data store (LDS). Each LDS has limited memory (e.g., 32 kilobytes). The specific sequence of shaders that the GPU executes is dictated by an API to which the GPU is coupled. In a typical sequence, the GPU executes a vertex shader, a hull shader, and then a tessellation shader. During execution of the vertex shader and the hull shader, a SIMD may receive a plurality of vertices to process and will write its results into its associated LDS.

One problem is that, for a given set of vertices, the tessellation shader should be implemented by the same SIMD that performs the vertex shader and the hull shader because the data used to execute the tessellation shader is in the LDS of the SIMD that performed the vertex shader and the hull shader. Even though the GPU may have other available compute resources (e.g., other SIMDs) that could enable the GPU to more-quickly execute the tessellation shader, the other available compute resources cannot be used because they do not have access to the necessary data.

To address this problem, a GPU310in accordance with an embodiment of the present invention dynamically uses an off-chip LDS622(of an off-chip memory620) or an on-chip LDS (of GPU310) for the tessellation shader, as illustrated inFIG. 6. Referring toFIG. 6, there is a mirrored off-chip LDS622for each SIMD610of GPU310. Input logic504includes a command processor602(which receives graphics-processing and general-compute tasks to be executed by GPU310) and a vertex analyzer604(which schedules when each shader program can be launched in execution unit506). Execution unit506of GPU310includes a plurality of SIMDs610A-610N. Each SIMD is associated with one of the plurality of on-chip LDSs612A-612N. For patches in the hull shader (HS) threadgroup, the HS data can be written to either an on-chip LDS612associated with a SIMD610(if the tessellation level is low, e.g., involves fewer than 100 vertices) or an off-chip LDS622(if the tessellation level is high, e.g., involved greater than 100 vertices). A code at the end of HS decides whether HS data is written to an on-chip LDS612or an off-chip LDS622. In an embodiment, each off-chip LDS622is quad-buffered, thereby allowing the same SIMD to operate on four times as many threadgroups.

In an embodiment, GPU310includes a tessellation engine. The tessellation engine tessellates patches based on a tessellation factor for each edge of the patch. There can be two, four, or six tessellation factors per patch. Based on these factors, the tessellation engine breaks up the patch into numerous points, lines, or triangles based on the tessellation topology.

For example,FIGS. 9A-Cillustrate example patches. In the example ofFIGS. 9A-C, the patches are illustrated as rectangles, but they could also be triangles, lines or another geometric shape. For the patch ofFIG. 9A, the tessellation factor along the v direction is 6, resulting in 6 line segments between point (0,0) and point (0,1). For the patch ofFIG. 9B, the tessellation factor along the v direction is 5, resulting in 5 line segments between point (0,0) and point (0,1). For the patch ofFIG. 9C, the tessellation factor along the v direction is 4, resulting in 4 line segments between point (0,0) and point (0,1). In a similar manner, for the patches in each ofFIGS. 9A-C, the tessellation factor along the u direction is 6, resulting in 6 line segments between point (0,0) and point (1,0).

The tessellation engine receives work in the form of threadgroups. Each threadgroup defines a number of patches, a starting address into the tessellation factor memories used to fetch tessellation factors, and other state information. The tessellation engine processes each patch from an input threadgroup, requests the number of tessellation factors it needs for each patch, and tessellates the patch based on various state data (partition, topology, axis, etc.). The tessellation engine outputs vertex data and primitive data. The vertex data out of the tessellation engine comprises u,v values.

FIG. 7illustrates functional blocks of a tessellation engine in accordance with an embodiment of the present invention. Referring toFIG. 7, the tessellation engine includes a thread-to-patch module702, a pre-processing module704, a tessellation module706, and a connectivity module708. Each of these functional blocks is described in more detail below.

Thread-to-patch module702converts a threadgroup to a patch. Each threadgroup is received as input from the hull shader (such as, hull shader204ofFIG. 2). This conversion includes a determination of (i) how many tessellation factors each patch needs, (ii) the address into the tessellation factor memory for each factor for the patch, and (ii) requests tessellation factors from a vertex cache (VC). The requested tessellation factors are buffered together per patch. All of the tessellation factors for the patch and state information are sent to pre-processing module704for each patch in the threadgroup. Thread-to-patch module702also sends a flag to mark the end of a threadgroup and the end of a packet.

The tessellation factors are received by the tessellation engine in IEEE floating point format. However, the math operations used to tessellate are processed in fixed point. So, to make the hardware efficient, there is only one float-to-fixed converter and the values are converted as they arrive one at a time from the VC. The unit also performs clamping of the tessellation factors to a value between 0.0 and 64.0.

Pre-processing module704receives one patch at a time and pre-calculates values used to tessellate that patch. That is, in an embodiment, for a given patch, tessellation module706repeatedly uses several numbers to compute the parametric positions of tessellation points for that patch. These numbers are based on the tessellation factor for a given edge of the patch. Since the set of tessellation factors will be the same per patch, pre-processing module can compute the numbers that are repeatedly used and provide them to tessellation module706.

Included below is pseudo-code that may be implemented by pre-processing module704. It is to be appreciated, however, that this pseudo-code is included for illustrative purposes only, and not limitation. In the pseudo-code that follows, factors that are bolded are those that are pre-calculated by pre-processing module704and then provided to tessellation module706.

Tessellation module706receives patch information from pre-processing module704and creates all of the tessellated points of the patch. Unlike tessellation module706, the DX11 algorithm calculates every point in the patch and stores it in memory to be used during the connectivity pass. However, a single patch can have up to 4,225 points so this is not efficient for the hardware. To address this problem, tessellation module706sequentially tessellates portions of the patch to generate a series of tessellation points that are provided to connectivity module708in the order in which it is determined whether the tessellation points are connected into primitives. In this way, unlike the DX11 algorithm, the tessellation points from tessellation module706do not need to be stored in memory prior to being provided to connectivity module708.

In an embodiment, tessellation module706includes two math unit that process edges of a patch in parallel to generate tessellation points. For example,FIG. 8illustrates a pipeline of functions implemented by tessellation module706. The functions illustrated inFIG. 8are described below with reference to the example patches ofFIGS. 9A-9C.

Referring toFIG. 8, tessellation module706receives patch data in a stage802. As mentioned above, tessellation module706creates the tessellation points for an outside edge and an inside edge in parallel so that connectivity module708can create output primitives in the proper order. In this regard, an outer edge control block808identifies an outside edge of the received patch, and an inner edge control block804identifies an inside edge of the received patch. For example, the patch inFIG. 9Aincludes an outside edge901and an inside edge902. Tessellation module706starts with the outside left edge901and the inside left edge902and create points from bottom to top. For example, after staging the data in stages810and812, outer point calculation block820calculates tessellation points along outer edge901; and inner point calculation block814calculates tessellation points along inner edge902. The tessellation points for outer edge901are then temporarily staged in824, and the tessellation points of inner edge902are temporarily staged in822. Outer point adjust block828and inner point adjust block826adjust for skewing of the tessellation points of outer edge901and inner edge902, respectively. Skewing occurs when points on an inside edge and points on an outside edge are not aligned at the same v coordinate (if the edges are vertical) or the same u coordinate (if the edges are horizontal). The tessellation points are then respectively stored in outer point FIFO832and inner point FIFO830. Connectivity module708then retrieves the tessellation points from these FIFOs, as explained in more detail in the next subsection.

After calculating the tessellation points along the two edges on the left side of the patch, tessellation module706calculates tessellation points on the two top edges followed by the right side and finally the bottom edges of the ring, as illustrated by a path904. Once the outer ring is complete, the process repeats for the next inside ring. Ring control block806controls the process of transitioning to the next inside ring.

Referring toFIG. 9A, for the next inside ring, edge902is the outside edge, and edge903is the inside edge. Inner point perpendicular block816calculates the perpendicular value, i.e., the value that remains the same across the entire edge. For example, along edge902, the v value changes, whereas the u value does not change. Thus, along edge902, the v values are regular values, and the u values are perpendicular values. In contrast, along the top outside edge of the patch inFIG. 9A, the u value changes, whereas the v value does not change. Thus, along the top outside edge, the u values are regular values, and the v values are perpendicular values. Accordingly, along edge902, for example, inner point calculation block814provides v values (from bottom to top) of 0.833, 0.666, 0.5, 0.333 and 0.167, while inner point perpendicular calculation block816provides one u value of 0.167 for the entire edge (because the u value along edge902remains constant).

During processing of a next ring, regular point values (i.e., values that change along an edge) are recalculated, and not stored. This does not cause any performance issue and decreases hardware area by removing a storage unit. On ther other hand, perpendicular values (i.e., values that remain constant along an edge) are temporarily stored in perpendicular value FIFO818from the inner edge and used on the outer edge. During processing of the next inside ring (i.e., when edge902is the outside edge), outer point calculation block820re-calculates regular point values for the tessellation points along edge902, and perpendicular point values are retrieved from perpendicular value FIFO818.

The calculation of all the tessellation points of the patch is complete when all rings within the patch have been processed. This process of point generation forms a snake or serpentine pattern, as illustrated inFIG. 9A, and does not require any point storage because points are created in the order they are connected, as described in more detail below with respect to connectivity module708. Each piece of point data is indexed as a u,v coordinate used by execution unit506to create the new vertex data. Each new primitive created is also tagged with the patch ID.

There are two special cases where the points are generated in a different fashion, which are illustrated inFIGS. 9B and 9C. Both these special cases occur during the last ring of the patch. Referring toFIG. 9B, the first special case occurs when the patch ends as a polygon. This means that the last ring has no inside edges. In this case, tessellation module706processes the top and right edges in the outside edge math unit (e.g., functional blocks808,812,820,824, and828ofFIG. 8) and processes the left and bottom edges in the inside math unit (e.g., functional blocks804,810,814,822, and826ofFIG. 8). This creates a stream of points that then can be connected as a group of triangles in the middle of the patch.

Referring toFIG. 9C, the other special case occurs when a patch ends with a line in the middle. In this case, the points in the middle are processed by the inside edge math unit (e.g., functional blocks804,810,814,822, and826ofFIG. 8). It processes the line from left to right and then turns around and regenerates the points from right to left (excluding the rightmost point), as illustrated inFIG. 9C. This is done because there will be triangles above the line and below the line that reuse the same points of the line. In an embodiment, if the line is less than 14 points long, a reuse buffer in connectivity module708ensures that the repeated points are only sent to execution unit506once.

Both of the special cases described above can also occur with the v dimension being greater than the u dimension. This means that the polygon or line will be vertical instead of horizontal. This causes different edges to be processed in the math units.

Connectivity module708receives tessellated point data from tessellation module706and creates primitives based on the topology (point, line, or triangle). Connectivity module708sends out the vertex data in strip form and sends relative indices for the primitives. Importantly, connectivity module708determines which tessellation points of a patch are to be connected in the order in which tessellation module706generates the tessellation points, which (as mentioned above) circumvents the need to store the tessellation points in memory as in the DX11 algorithm.

For example,FIG. 13illustrates an example order in which connectivity module708determines the connectivity of the tessellation points for the patch ofFIG. 9A. That is, connectivity module708processes tessellation points from bottom to top along the two outside edges. Referring toFIG. 13, in an embodiment connectivity module708starts from the vertex labeled (0,1) and progresses toward the vertex labeled (0,0). For example, connectivity module708may identify vertex (0,1), vertex1302, and vertex1304as being associated with a first primitive (e.g., triangle), labeled with a “1” inFIG. 13. Similarly, connectivity module708may next identify vertices1302,1304, and1306as being associated with a second primitive (e.g., triangle), labeled with a “2” inFIG. 13. In other words, connectivity module708determines whether tessellation points are connected into primitives in the same order that tessellation module706provides the tessellation points for a patch.

Connectivity module708determines the connectivity of the output vertices (i.e., tessellation points) by a set of lookup tables which are accessed based on tessellation factor information. For example,FIG. 11illustrates a set of 32 lookup tables that connectivity module708selects from to determine whether vertices are connected. Referring toFIG. 11, the left-hand column includes the number of the LUT, and the right-hand column includes the LUT.

Unlike connectivity module708, the DX11 algorithm uses only one 32-entry LUT, which is illustrated inFIG. 11as the LUT labeled 31. According to the DX11 algorithm, this one LUT is looped through to determine when a triangle can be created. Using only one table, as in DX11, means that it could take up to 32 clocks to create one primitive. This is very inefficient for the hardware because performance requirements are to produce one primitive per clock. In accordance with an embodiment of the present invention, the one LUT is broken into 32 separate tables, as illustrated inFIG. 11. By selecting one of the 32 tables, the selected table can be looped through and a primitive can be created in a single clock cycle.

FIG. 10illustrates an example method1000implemented by connectivity module708to determine whether vertices are connected. Referring toFIG. 10, method1000begins at a step1002in which a lookup table is selected from a plurality of lookup tables. In an embodiment, the lookup table is selected based on a tessellation factor provided by hull shader204. In particular, the tessellation factor is divided by two, resulting in a number called the “half tess factor,” and the half tess factor is used to select the LUT. For example, if the tessellation factor is 10, then the half tess factor would be 5, and the LUT ofFIG. 11labeled 5 (which includes entries {4,2,5,1,6,3}) would be selected.

Referring again to method1000ofFIG. 10, in a step1004tessellation points are connected into primitives based on the selected lookup table. As mentioned above,FIG. 13illustrates how vertices may be connected into primitives.

Connectivity module708also includes reuse logic that provides tessellation-point data in an efficient manner. Unlike the reuse logic of the tessellation engine, DX11 handles reuse based on an index to the coordinates of the patch (i.e., (u, v) values stored in memory). The index in memory that DX11 uses may be degenerate, meaning that DX11 may send tessellation-point data more than once because the points of a patch are not uniquely indexed in the memory. Specifically, with some values of tessellation factors, DX11's algorithm produces the same patch coordinates (i.e., (u, v) values) for multiple points on an edge. However, DX11 considers these points as unique and sends all of them as output.

In contrast, the tessellation engine of an embodiment of the present invention handles reuse based on the actual coordinates of the patch (i.e., the actual (u, v) values), rather than an index in memory. Using the actual coordinates, as specified by an embodiment of the present invention, helps in cases where degenerate triangles are formed due to DX11's algorithm.

According to an embodiment of the present invention, the tessellation engine sends a first point and determines whether any subsequent points have the same coordinates (i.e., (u, v) value) as the first point. The tessellation engine makes this determination by comparing the coordinate of the first point to coordinates of points in an index buffer (e.g., “Parameter Cache”). In an embodiment, the index buffer stores up to 14 points. If a subsequent point has the same coordinates (i.e., (u, v) value) as the first point, the tessellation engine does not send the subsequent point. This saves shader processing.

For example,FIG. 12illustrates an example method1200, implemented by connectivity module708, for re-using vertices in accordance with an embodiment of the present invention. Method1200begins at a step1202in which vertices of primitives are indexed according to their respective positions—which are specified by (u,v) values within a patch.

Before sending a vertex for subsequent processing within a graphics pipeline, it is first determined whether the index associated with that vertex is in a buffer, as indicated in step1204. In an embodiment, the buffer is 14 elements wide. If the index is in the buffer, then as indicated in step1206the vertex is not sent for subsequent processing in the graphics pipeline, because the vertex has already be sent to the graphics pipeline.

If, on the other hand, it is determined in step1204that the index is not in the buffer, then the vertex is sent for subsequent processing in the graphics pipeline, as indicated in a step1208. In a step1210, the index for the vertex is placed in the buffer, and the oldest index is flushed from the buffer in a first-in, first-out fashion.

VI. Example Software Implementations

In addition to hardware implementations of processing units of embodiments of the present invention (e.g., CPU302and GPU310), such processing units may also be embodied in software disposed, for example, in a computer-readable medium configured to store the software (e.g., a computer-readable program code). The program code causes the enablement of embodiments of the present invention, including the following embodiments: (i) the functions of the systems and techniques disclosed herein (such as, the functions illustrated inFIGS. 7,8,10, and12); (ii) the fabrication of the systems and techniques disclosed herein (such as, the fabrication of CPU302and/or GPU310); or (iii) a combination of the functions and fabrication of the systems and techniques disclosed herein.

This can be accomplished, for example, through the use of general-programming languages (such as C or C++), hardware-description languages (HDL) including Verilog HDL, VHDL, Altera HDL (AHDL) and so on, or other available programming and/or schematic-capture tools (such as circuit-capture tools). The program code can be disposed in any known computer-readable medium including semiconductor, magnetic disk, or optical disk (such as CD-ROM, DVD-ROM). As such, the code can be transmitted over communication networks including the Internet and internets. It is understood that the functions accomplished and/or structure provided by the systems and techniques described above can be represented in a core (such as a CPU core and/or a GPU core) that is embodied in program code and may be transformed to hardware as part of the production of integrated circuits.