System for processing vertices from a graphics request stream

An apparatus for processing a graphics request stream begins processing subsequent vertex data while processing previous vertex data. To that end, the apparatus has a vertex assembler having an input for receiving graphics requests, and a processor (coupled to the vertex assembler) for processing received graphics requests. The processor provides a headstart signal to the vertex assembler to indicate that the processor is processing a new graphics request. Upon receipt of the headstart signal, the vertex assembler causes the processor to restart processing of the new graphics request if the new request is determined to have not been properly assembled.

FIELD OF THE INVENTION
 The invention generally relates to computer systems and, more particularly,
 the invention relates to processing graphics request data for display on a
 computer display device.
 BACKGROUND OF THE INVENTION
 Three dimensional graphics request data commonly is processed in a computer
 system as a plurality of polygons having vertices. Each of the vertices
 have associated attribute data (e.g., color, transparency, depth, etc . .
 .) that is utilized to rasterize pixels on a computer display device. The
 well known OPENGL.TM. application program interface (available from
 Silicon Graphics Inc. of Mountain View, Calif.) is a commonly used three
 dimensional graphics library that may be used for processing three
 dimensional graphics request data in this manner.
 Many computer systems utilizing the OPENGL.TM. graphics library process
 vertex data sequentially and, for various reasons noted below, postpone
 processing of subsequent vertices until a previous vertex is completely
 processed. For example, a second vertex typically is not processed until
 an immediately preceding first vertex is completely processed. Among other
 reasons, this postponement ensures that the received second vertex data is
 properly assembled and thus, ready for processing. Premature processing of
 a successive vertex (e.g., processing the second vertex prior to
 completion of the first vertex) may cause an error condition if such
 successive vertex is not completely and properly assembled.
 It is not uncommon, however, for a successive vertex to be completely
 assembled prior to completion of processing of a previous vertex. In
 systems with many processing resources, postponing processing of a
 completely assembled vertex thus unnecessarily lengthens the time required
 to process a graphics request stream.
 SUMMARY OF THE INVENTION
 In accordance with one aspect of the invention, an apparatus for processing
 a graphics request stream begins processing subsequent vertex data while
 processing previous vertex data. To that end, the apparatus preferably
 includes a vertex assembler having an input for receiving graphics
 requests, and a processor (coupled to the vertex assembler) for processing
 received graphics requests. The processor provides a headstart signal to
 the vertex assembler to indicate that the processor is processing a new
 graphics request. Upon receipt of the headstart signal, the vertex
 assembler causes the processor to restart processing of the new graphics
 request if the new request is determined to have not been properly
 assembled.
 In accordance with another aspect of the invention, the apparatus for
 processing a graphics request stream provides the headstart signal to the
 vertex assembler to indicate that the processor is processing a new
 graphics request while it is processing a previous graphics request. After
 receipt of the headstart signal and completion of processing of the
 previous graphics request, the vertex assembler causes the processor to
 restart processing of the new graphics request if the new request is
 determined to have not been properly assembled.
 In preferred embodiments, after receipt of the headstart signal and
 completion of processing the previous graphics request, the vertex
 assembler causes the processor to continue processing the new graphics
 request without restarting if the new request is determined to have been
 properly assembled.
 In accordance with yet another aspect of the invention, an apparatus for
 processing a graphics request stream having first vertex data followed by
 second vertex data includes a vertex assembler having an input for
 successively receiving the first vertex data and the second vertex data,
 and a processor (coupled to the vertex assembler) for processing the first
 vertex data and the second vertex data. The vertex assembler assembles the
 first vertex data prior to assembling the second vertex data. The
 processor begins processing the second vertex data after beginning but
 prior to completing the processing of the first vertex data. The vertex
 assembler directs a message to the processor (after completing processing
 of the first vertex data) indicating whether the processor must restart
 processing of the second vertex data.
 In preferred embodiments, the message indicates whether the processor may
 continue processing the second vertex data without restarting. The vertex
 assembler may include a determiner for determining if the second vertex
 data was properly assembled when the processor began processing the second
 vertex data. The message thus may indicate that the processor must restart
 processing the second vertex data if it is determined that the second
 vertex data was not properly assembled when the processor began processing
 the second vertex data. In yet other embodiments of the invention, the
 apparatus may include a flag indicating that the processor has begun
 processing the second vertex data.
 In still other embodiments of the invention, first vertex data and second
 data may be processed by processing the assembled first vertex data, and
 then beginning to process second vertex data prior to completing the
 processing of the first vertex data. The second vertex data preferably is
 processed in accordance with a preselected process having a start portion.
 It then may be determined, after completing the processing of the first
 vertex data, if the second vertex data was properly assembled when
 processing of the second vertex data began. If it is determined that the
 second vertex data was not properly assembled when processing of the
 second vertex data began, then the second vertex data is reprocessed from
 the start portion of the preselected process

DESCRIPTION OF PREFERRED EMBODIMENTS
 FIG. 1 shows a portion of an exemplary computer system 100 on which
 preferred embodiments of the invention may be implemented. More
 particularly, the computer system 100 includes a host processor 104 (i.e.,
 a central processing unit) for executing application level programs and
 system functions, volatile host memory 102 for short term data storage
 (i.e., random access memory), a graphics accelerator 106 for processing
 graphics request code in accord with preferred embodiments of the
 invention, and a bus 110 coupling all of the prior noted elements of the
 system 100. In addition, the system 100 further includes a display device
 108, coupled to the graphics accelerator 106, for displaying the graphics
 request code processed by the accelerator 106. The graphics accelerator
 106 preferably utilizes any well known graphics processing application
 program interface such as, for example, the OPENGL.TM. application program
 interface (available from Silicon Graphics, Inc. of Mountain View, Calif.)
 for processing three dimensional ("3D") and two dimensional ("2D")
 graphical request code. In preferred embodiments, the host processor 104
 executes a graphical drawing application program such as, for example, the
 PLANT DESIGN SYSTEM.TM., available from Intergraph Corporation of
 Huntsville, Ala.
 FIG. 2 shows several elements of the graphics accelerator 106. In preferred
 embodiments, the graphics accelerator 106 includes a double buffered frame
 buffer 200 (i.e., having a back buffer and a front buffer) for storing the
 processed graphics request code in accord with the OPENGL.TM. interface.
 Among other things, the graphics accelerator 106 also preferably includes
 a geometry accelerator 202 for performing geometry operations that
 commonly are executed in graphics processing, a rasterizer 204 for
 rasterizing pixels on the display device 108, and a resolver 206 for
 storing data in the frame buffer 200 and transmitting data from the frame
 buffer 200 to the display device 108. As noted above, the graphics
 accelerator 106 preferably is adapted to process both 2D and 3D graphical
 data. For more information relating to preferred embodiments of the
 graphics accelerator 106, see, for example, copending patent application
 entitled "Wide Instruction Word Graphics Processor", filed on even date
 herewith and naming Vernon Brethour, Gary Shelton, William Lazenby, and
 Dale Kirkland as inventors, the disclosure of which is incorporated
 herein, in its entirety, by reference.
 FIG. 3 schematically shows one embodiment of the geometry accelerator 202
 that may be utilized in accord with preferred embodiments of the
 invention. Among other elements, the geometry accelerator 202 includes an
 input buffer 300 (e.g., a first-in, first-out buffer) for receiving
 graphics request code having data representing successive vertices of a
 primitive, and a vertex assembler 302 for assembling the input graphics
 request code (see below) received from the input buffer 300. The graphics
 request code may be generated by executing a graphics application program
 by the host processor 104.
 In accord with preferred embodiments, the vertex assembler 302 retrieves
 data for each successive vertex from the input buffer 300, and assembles
 each retrieved vertex into a proper form for transmission onto a geometry
 bus 304 via an output port 306. The vertex assembler 302 may assemble the
 received vertex data in accordance with conventional processes. More
 particularly, the vertex assembler 302 may construct complete and properly
 formatted vertex input data from partial vertex data. For example, in many
 graphical computer systems, vertex data may be represented by forty-four
 different numbers. Fewer than the full forty-four numbers, however, may be
 properly produced by the host processor 104 (e.g., six numbers), however,
 to represent a vertex when successive vertices have common attributes. Use
 of fewer numbers to represent a vertex necessarily reduces bandwidth
 requirements by compressing data, thus increasing system performance.
 The vertex assembler 302 also includes a flag 303 indicating that a
 "headstart" signal has been received from other portions of the geometry
 accelerator 202. Details of the flag 303 and headstart signal are
 discussed below with reference to FIG. 4.
 In addition to the input buffer 300, vertex assembler 302, and geometry bus
 304, the geometry accelerator 202 also includes a vertex processor 308 for
 performing intensive math calculations on the assembled vertex data, and
 an output buffer 310 for temporarily storing the processed vertex data
 from the vertex processor 308. Among other things, the math calculations
 may include multiplication operations, reciprocal operations, and addition
 operations. Once stored in the output buffer 310, the processed vertex
 data may be transmitted to the rasterizer 204 in accord with conventional
 processes.
 FIG. 4 shows a preferred process of processing graphics request code having
 successive vertex data. The successive vertex data preferably includes
 data for a plurality of vertices that may be considered to form a polygon
 strip (e.g., a triangle strip, which is a plurality of contiguous
 triangles). Each of the vertices are sequentially identified by a sequence
 number for sequential processing by the processor 308. As discussed below,
 the process controls the vertex processor 308 to begin processing a
 subsequent vertex while it is processing a prior vertex. Prior to the
 beginning of the process before point 400, a current vertex variable and
 subsequent variable are respectively set to be the first and second
 vertices in the graphics request stream.
 The process begins at step 402 in which the current vertex is processed by
 the vertex processor 308. To that end, the vertex processor 308 retrieves
 the assembled current vertex data from the vertex assembler 302. The
 vertex processor proceeds by performing pre-processing instructions and
 some mathematical instructions on the vertex data. In preferred
 embodiments, the vertex processor 308 includes a wide array of plural
 processing elements for processing the graphics request stream. The
 processing elements preferably are arranged in parallel to facilitate
 parallel processing.
 After pre-processing of the current vertex has finished, the processor
 begins mathematically intensive instructions at step 406. At a
 predetermined point during the mathematically intensive processing, a
 signal is sent to the vertex assembler 302 to start assembling the
 subsequent vertex in step 412. When a predetermined point in the
 instructions is reached, the vertex processor 308 retrieves the subsequent
 vertex data from the vertex assembler 302. The processor 308 retrieves
 vertex data from the vertex assembler 302 output port 306 which at this
 point is treated as the assembled vertex data of the subsequent vertex. In
 preferred embodiments, this predetermined line of instructions is reached
 after the mathematically intensive processing has occurred for the current
 vertex in step 406. In the next instruction line after the predetermined
 point, code exists for processing both the current vertex and the
 subsequent vertex. Pre-processing on the subsequent vertex occurs in step
 408 at the same time that post-processing occurs on the current vertex in
 step 410. Since the instruction set for post-processing does not require
 the use of mathematically intensive hardware such as, a multiplier or a
 reciprocal unit, for example, and the instruction set for pre-processing
 only minimally requires the use of mathematically intensive hardware, the
 pre-processing of the subsequent vertex and the post-processing of the
 current vertex may occur at the same time. Thus, both the current vertex
 and subsequent vertex are being simultaneously processed by the vertex
 processor 308. Additionally, after the predetermined point in the
 instructions is reached, a headstart signal is sent to the vertex
 assembler in step 411. When the bit of flag 303 is set, the vertex
 assembler 302 determines if the vertex data for the subsequent vertex was
 properly assembled when it was retrieved from its output port 306.
 The vertex assembler keeps track of all vertices that are assembled based
 upon the sequence number in step 416. If the subsequent vertex was not
 assembled when the headstart signal is received, a latch is set in step
 420. If the subsequent vertex is assembled, a separate latch is set in
 step 422. Keeping track of whether a vertex has been assembled or not may
 be performed in multiple ways, which should be apparent to one skilled in
 the art. For example, the vertex assembler 302 may store the sequence
 number for a vertex along with data indicative of the status of assembly.
 When the current vertex has finished the post processing, the vertex
 processor 308 sends a signal to the vertex assembler 302 in step 414. This
 notification causes the vertex assembler 302 in step 418 to check the
 state of the latches which were set in steps 420 and 422. If the
 subsequent vertex data was assembled properly, the processor continues to
 point 404 and continues to process the subsequent vertex, which is now the
 current vertex, by performing postprocessing in step 410. If, however, the
 vertex assembler 302 indicates that the subsequent vertex was not
 assembled when a request for the subsequent vertex was made from the
 vertex processor 308, the vertex assembler checks to see if the subsequent
 vertex is finished being assembled in step 424. If the subsequent vertex
 is not assembled, then the vertex assembler 302 causes the processor to
 idle while the subsequent vertex is assembled before returning to point
 400.
 The vertex assembler stores an instruction line number in a register,
 referred to hereinafter as a jump register, that the processor utilizes to
 determine which line of the instructions (referred to above) that the
 processor should process. The vertex assembler 302 updates the jump
 register at point 400 and at step 418. For example, the jump register may
 contain the setting for a zero at point 400. The processor accesses the
 jump register and reads a zero which indicates to the processor that the
 processor should sit at idle and wait for the vertex assembler 302 to set
 the jump register to an instruction line number. When the vertex assembler
 302 has assembled a vertex, the jump register is set to a predetermined
 address, such as one, for example, indicating that the first instruction
 line should be executed.
 At step 418, the vertex assembler 302 indicates whether the subsequent
 vertex was assembled and sets the jump register. Accordingly, if the
 subsequent vertex was not ready at the time of receipt of the headstart
 signal, the jump register will be set to a value which indicates that the
 first instruction should be executed on the subsequent vertex data at
 point 400. If the subsequent vertex was ready upon receipt by the vertex
 assembler 302 of the headstart signal, the vertex assembler 302 sets the
 jump register to the instruction line which is indicative of step 404 so
 that the mathematically intensive processing is begun on the subsequent
 vertex, since preprocessing has already been done.
 In an alternative embodiment, the disclosed apparatus and method for
 processing vertices from a graphics request stream may be implemented as a
 computer program product for use with a computer system. Such
 implementation may include a series of computer instructions fixed either
 on a tangible medium, such as a computer readable medium (e.g., a
 diskette, CD-ROM, ROM, or fixed disk) or transmittable to a computer
 system, via a modem or other interface device, such as a communications
 adapter connected to a network over a medium. The medium may be either a
 tangible medium (e.g., optical or analog communications lines) or a medium
 implemented with wireless techniques (e.g., microwave, infrared or other
 transmission techniques). The series of computer instructions embodies all
 or part of the functionality previously described herein with respect to
 the system. Those skilled in the art should appreciate that such computer
 instructions can be written in a number of programming languages for use
 with many computer architectures or operating systems. Furthermore, such
 instructions may be stored in any memory device, such as semiconductor,
 magnetic, optical or other memory devices, and may be transmitted using
 any communications technology, such as optical, infrared, microwave, or
 other transmission technologies. It is expected that such a computer
 program product may be distributed as a removable medium with accompanying
 printed or electronic documentation (e.g., shrink wrapped software),
 preloaded with a computer system (e.g., on system ROM or fixed disk), or
 distributed from a server or electronic bulletin board over the network
 (e.g., the Internet or World Wide Web). Of course, some embodiments of the
 invention may be implemented as a combination of both software (e.g., a
 computer program product) and hardware. Still other embodiments of the
 invention are implemented as entirely hardware, or entirely software
 (e.g., a computer program product).
 Although various exemplary embodiments of the invention have been
 disclosed, it should be apparent to those skilled in the art that various
 changes and modifications can be made which will achieve some of the
 advantages of the invention without departing from the true scope of the
 invention. These and other obvious modifications are intended to be
 covered by the appended claims.