Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Reexamination Certificate
2001-01-19
2003-04-01
Zimmerman, Mark (Department: 2671)
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
Reexamination Certificate
active
06542152
ABSTRACT:
BACKGROUND OF THE INVENTION
A. Field of the Invention
This invention relates generally to a method and an apparatus for culling and, more particularly, to a method and an apparatus for accelerating culling tests in computer graphics systems.
B. Description of the Related Art
A computer graphics system is commonly used to display three-dimensional representations of an object on a two-dimensional display screen. In a typical computer graphics system, an object to be rendered is divided into a plurality of graphics primitives. The graphics primitives are basic components of a graphics picture and may be defined by geometries of a point, line, vector, or polygon, such as a triangle. The graphics primitives are fed through a graphics pipeline where various types of processing occur and are then rendered on a display.
Culling, also called backface elimination, is an operation that compares the orientation of polygons in a polyhedron with the viewpoint or center of projection, and removes those polygons that cannot be seen. On average, half of the polygons in a polyhedron are backfacing and the advantage of this process is by using a simple test to remove these polygons. The test for visibility is straightforward and is best carried out in view space. We calculate the outward normal of a polygon and examine the sign of the dot product of this normal vector and the vector from the center of projection, as illustrated in FIG.
1
.
As shown in
FIG. 1
are the outward normal vector of a polygon N
p
, and the ‘line of sight’ vector N from the center of the face to the viewpoint. Based on these two vectors, the visibility of a polygon is defined as:
Visibility=
N
p
·N
>0
Where:
N
p
is the polygon normal
N is the ‘line of sight’ vector
In order to determine whether a polygon is visible on a two-dimensional flat screen, select three points V
1
, V
2
, and V
3
from the polygon where the V
1
is the center point, V
2
and V
3
are any points on the surface which satisfy the condition that V
1
, V
2
, and V
3
are not on the same line, and (V
1
, V
2
, V
3
) is distributed counterclockwise.
From the visibility test:
Visibility=
N
p
·N
[(
V
2
−V
1
)×(
V
3
−V
1
)]·(
V
1
−V
0
)>0
Where:
V
0
is the viewpoint (0, 0, 0), and
V
1
, V
2
, and V
3
are the selected vertices (x
1
, y
1
, z
1
), (x
2
, y
2
, z
2
), and (x
3
, y
3
, z
3
) for a triangle.
The calculation for the visibility test is:
Visibility
=
|
x
1
y
1
z
1
x
2
y
2
z
2
x
3
y
3
z
3
|
>
0
Although the equation for the culling test may seem to be relatively simple and straightforward, it takes twelve multiplication processes and five addition/subtraction processes to complete the whole calculation to test the visibility for one triangle. For two triangles, hence, it takes 24 multiplications and 10 addition/subtractions. Not only is the calculation process unwieldy but also time-consuming.
SUMMARY OF THE INVENTION
In view of these problems, the object of the present invention is to provide a method and an apparatus for use in computer graphics system which can render and display graphics primitives faster.
In one aspect of the present invention, a method is provided for determining, at the same time, whether two adjacent polygons of a polyhedron are visible on a 2-dimensional visual display unit. The test can be done more easily and rapidly. It lends itself to rapid real-time culling and eliminates surfaces certain to be not visible at the observer's viewpoint.
Another aspect of the present invention is to provide an apparatus to execute the culling test described above. The culling apparatus comprises one multiplier, three multiplexers, two registers, one adder/subtractor, and a computer program with a set of commands controlling the flow and process of data. The instruction commands may be installed in ROM to be used in the computer graphic systems in order to compute and control all data inputs and outputs of culling test.
The benefits of this invention will become evident as the present invention is described more fully below.
REFERENCES:
patent: 5319447 (1994-06-01), Garino et al.
patent: 5784047 (1998-07-01), Cahill et al.
patent: 6377265 (2002-04-01), Bong
Santiago Enrique L
Silicon Integrated Systems Corp.
Zimmerman Mark
LandOfFree
Method and apparatus for culling does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for culling, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for culling will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3007793