Apparatus to detect setting of bits in a data structure

Details Apparatus to detect setting of bits in a data structure Apparatus to detect setting of bits in a data structure

2000-05-18

2003-12-16

Chauhan, Ulka J. (Department: 2676)

Computer graphics processing and selective visual display system

Computer graphic processing system

Plural graphics processors

C345S522000, C708S203000, C708S212000

Reexamination Certificate

active

06664967

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Technical Field
The present invention relates generally to an improved data processing system and in particular to a method and apparatus for processing graphics data. Still more particularly, the present invention relates to a method and apparatus for identifying receipt of a complete graphics data stream.
2. Description of Related Art
Data processing systems, such as personal computers and work stations, are commonly utilized to run computer-aided design (CAD) applications, computer-aided manufacturing (CAM) applications, and computer-aided software engineering (CASE) tools. Engineers, scientists, technicians, and others employ these applications daily. These applications involve complex calculations, such as finite element analysis, to model stress in structures. Other applications include chemical or molecular modeling applications. CAD/CAM/CASE applications are normally graphics intensive in terms of the information relayed to the user. Data processing system users may employ other graphics intensive applications, such as desktop publishing applications. Generally, users of these applications require and demand that the data processing systems be able to provide extremely fast graphics information.
The processing of a graphics data stream to provide a graphical display on a video display terminal requires an extremely fast graphics system to provide a display with a rapid response. In these types of graphics systems, primitives are received for processing and display. A primitive is a graphics element that is used as a building block for creating images, such as, for example, a point, a line, an arc, a cone, or a sphere. A primitive is defined by a group of one or more vertices. A vertex defines a point, an end point of an edge, or a corner of a polygon where two edges meet. Data also is associated with a vertex in which the data includes information, such as positional coordinates, colors, normals, and texture coordinates. Commands are sent to the graphics system to define how the primitives and other data should be processed for display.
Within these graphics systems, a graphics pipeline is used to process this graphics data. With a pipeline, the graphics data processing is partitioned into stages of processing elements in which processing data may be executed sequentially by separate processing elements. The first stage in the graphics pipeline is typically a vertex packer, which is used to accumulate data for a vertex prior to sending the vertex to the other stages for processing. A data stream is received by the vertex packer for processing. The amount of data that may be received in a data stream for a vertex is variable in many cases. The data stream begins with a command containing two 32 bit words. The first word contains the opcode and a count of a number of vertices to follow. The second word in the command contains a set of 32 enable bits. These enable bits identify the number of words containing vertex data. Following the command is a number of words containing the vertex data.
It is necessary to know when the variable length data stream is complete for a single vertex. When up to 32 words are to be received for a vertex, the use of a 32 bit counter to count the enable bits impedes performance because a 32 bit counter function cannot be performed in a single clock cycle. Currently, identification of whether additional words are to be received is performed by counting the number of bits set equal to a logic one in the 32 bit word and decrementing the count each time a new data word is received. This current process requires a large and slow circuit containing a counter, which is unable to perform the function in a single clock cycle.
Therefore, it would be advantageous to have an improved method and apparatus for identifying when all of the data for a vertex has been received.
SUMMARY OF THE INVENTION
The present invention provides a method and apparatus for detecting bits set in a data structure. A first level encoding stage receives bits for the data structure, groups the bits into a set of bit groups, and encodes the set of bit groups to form a set of output bits. A set of intermediate level encoding stages is connected to the first level encoding stage. Each level intermediate encoding stage receives output bits from a previous stage, groups the output bits into a plurality of bit groups, and encodes the plurality of bit groups to generate a plurality of output bits. A final level encoding stage is connected to a last intermediate level encoding stage within the set of intermediate level encoding stages, wherein the final level encoding receives final output bits from a last intermediate level encoding stage within the plurality of intermediate level encoding stages and encodes the final output bits to generate an indication of bits set in the data structure.


REFERENCES:
patent: 5420809 (1995-05-01), Read et al.
patent: 5541865 (1996-07-01), Ashkenazi
patent: 5717616 (1998-02-01), Morris
patent: 6018353 (2000-01-01), Deering et al.
patent: 6307557 (2001-10-01), Deering
patent: 6314205 (2001-11-01), Masuda et al.
patent: 6337689 (2002-01-01), Hochmuth et al.
The OpenGL Graphics System: A Specification (Version 1.2); Segal et al.; Mar. 23, 1998.

Affiliated with

Also associated with

Rating

Apparatus to detect setting of bits in a data structure does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Apparatus to detect setting of bits in a data structure, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Apparatus to detect setting of bits in a data structure will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3152465