Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Reexamination Certificate
1999-12-27
2003-04-08
Razavi, Michael (Department: 2672)
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
Reexamination Certificate
active
06545679
ABSTRACT:
FIELD OF THE INVENTION
The present invention is related to a computer graphics system. More specifically, the present invention is related to view volume clip-check by a computer graphics system.
BACKGROUND OF THE INVENTION
Clipping and Clip-checking
In a computer graphics system, the final two dimensional images being displayed are generated from raw three dimensional data through a sequence of processing steps. These three dimensional data include locations and geometry information about graphics objects and a hypothetical viewer. Typically, these three dimensional data are first stored in object coordinates of an object space, wherein graphics objects are represented independent of the viewer. Then, graphics objects and the viewer are transformed into a different space (with different coordinates) in order to relate these graphics objects to the viewer. In so doing, these graphics objects will be displayed as if seen through the eyes of the viewer. Next, graphics objects are clipped to fit the viewing volume of the viewer because what the viewer will see is finite in scope. Finally, the remaining three dimensional data undergo further processing steps to become two dimensional images stored in a frame buffer right before these two dimensional images are displayed.
In particular, the process of clipping geometry of graphics objects to fit the viewing volume actually involves at least three steps: transformation of the object space, clip-checking and clipping. The first step involved is called model view projection (MVP). Typically, clip-checking is not done in the object space even though three dimensional data are initially represented in object coordinates within the object space. Various transformations collectively called MVP is performed on the object space to create what is called a clip space. In so doing, the mathematical operations of clip-checking are reduced to simplified forms, thus facilitating the efficiency of clip-checking.
The second step involved is called clip-checking. In the clip-checking step, geometry of graphics objects is compared with the viewing volume of the viewer. Or more specifically, geometry of graphics object is compared with the frustum of the viewing volume. The motivation here is that the viewer sees only what is inside of the frustum: anything outside of the frustum will not be needed to generate the final two dimensional images. Thus, anything outside of the frustum is excluded (culled away) from undergoing further unnecessary processing. Also during clip-checking, if a certain portion of the geometry of graphics objects protrudes outside of the frustum, that certain portion will be designated as “to be clipped away.” The designated protruding portion will then be clipped away during the third step: the clipping step. Accordingly, this clipping step is performed within the clip space.
Prior Art Implementations of Clip-checking and Clipping
In a computer graphics system, the processing steps are allocated between the CPU (central processing unit) and the graphics pipeline. Specifically, the graphics pipeline is implemented to perform processing steps that are particularly well suited in a forward flow manner. In so doing, the graphics pipeline offsets the CPU's graphic processing load. As a result, the processing steps can be efficiently performed, thus improving the overall throughput of the computer graphics system.
In one prior art approach, clipping is incorporated as a part of a graphics pipeline. Unfortunately, clipping is “expensive” to perform within the graphics pipeline because clipping involves algorithms with branching behaviors. These branching behaviors from clipping algorithms clash against forward flow characteristics of any pipeline architecture. Moreover, clipping requires continual fetching and updating three dimensional data such as vertices of graphics objects represented within the object space. As such, if clipping is designed as a part of the graphics pipeline, the bus coupling the CPU and the graphics pipeline will be burdened with fetching and updating three dimensional data between the CPU and the graphics pipeline. In fact, bus bandwidth could be severely decreased by data communication between the CPU and the graphics pipeline, thus making bus congestion likely.
In another prior art approach, clipping is moved from the graphics pipeline to the CPU. By relying on the CPU to perform clipping, this approach solves the above problem of using a graphics pipeline's forward flow method to perform algorithms with branching behaviors. This approach also solves the above problem of congesting the bus. However, this prior art approach in turn introduces new problems of its own.
One new problem is over-burdening the CPU of the computer graphics system. Importantly, the CPU is not only over-burdened simply because it performs the extra processing of clipping that used to be performed by the graphics pipeline. The CPU is over-burdened at least for two additional reasons. First, in order to clip geometry of graphics objects to fit within the frustum, clip-checking is performed prior to clipping. But because clipping is performed by the CPU, and because clip-checking is performed prior to clipping, clip-checking is also performed by the CPU and not performed by the graphics pipeline. Second, in order to clip-check graphics objects, graphics objects in object coordinates are first transformed by a MVP matrix into graphics objects in clip coordinates within a clip space. Specifically, performing clip-checking within the clip space simplifies the mathematical operations of clip-checking geometry. As such, the CPU also performs MVP matrix multiplications in addition to clip-checking and clipping. Accordingly, in this prior art approach, the CPU not only is performing clipping, but also MVP matrix multiplication and clip-checking prior to clipping. Thus, the CPU is over-burdened. And, throughput of the computer graphics system is decreased.
Furthermore, another problem with this prior art approach is under-utilization (or waste) of the graphics pipeline's processing capability and strength. Specifically, as mentioned above, MVP matrix multiplication is now also designed to be performed by the CPU instead of the graphics pipeline. However, matrix multiplication is particular well suited for forward flow processing modal of the graphics pipeline. As such, performing matrix multiplication by the CPU does not take advantage of the graphics pipeline's efficiency in performing matrix multiplication. Thus, the graphics pipeline's processing capability is under-utilized. And again, throughput of the computer graphics system is decreased.
Thus, a need exists for a computer graphics system to perform clipping without disrupting the graphics pipeline by branching behavior of the clipping algorithms. A need also exists for a computer graphics system to perform clipping without decreasing the bus bandwidth between the CPU and the graphics pipeline. A further need exists for a computer graphics system to perform clipping without over-burdening the CPU. Yet still a need exists for a computer graphics system to perform clipping without under-utilizing the processing capability of the graphics pipeline.
Fortunately, as will be explained in the following pages, the present invention successfully answers all of the needs stated above with a new approach to clip-checking.
SUMMARY
The present invention is drawn to a method and a system for performing view volume clip-check. Until the present invention, view volume clip-check by a computer graphics system had been performed within the context of a clip space with its clip coordinates. However, the present invention performs view volume clip-check within an object space with its object coordinates. In so doing, the present invention overcomes the problems of the prior art approaches in clipping. In particular, the present invention performs clipping without disrupting forward flow of the graphic pipeline. Moreover, the present invention performs clipping without wasting bus ba
Hussain Zahid
Tommasi Gianpaolo
Cunningham G. F.
Microsoft Corporation
Razavi Michael
Woodcock & Washburn LLP
LandOfFree
View volume clip-check in object space does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with View volume clip-check in object space, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and View volume clip-check in object space will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3105424