Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Reexamination Certificate
2000-09-14
2003-08-26
Zimmerman, Mark (Department: 2671)
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
Reexamination Certificate
active
06611263
ABSTRACT:
BACKGROUND OF THE INVENTION
A. Field of the Invention
The present invention relates to a culling method and module applied in a 3D graphics system, and more particularly to a culling method and module to speed up culling using a comparison circuit and a culling decision circuit or tables.
B. Description of the Related Art
Generally, there are at least four procedures in the 3D graphics system as shown in FIG.
1
. The TnL (Transform and Lighting) Engine
11
receives the 3D-Coordinate Vertex Stream and then transforms it into 2D-Coordinate Vertex Stream. The Culling module
12
receives the 2D-Coordinate Vertex Stream inputs for eliminating the polygons that cannot be seen from a view point. The Setup Engine
13
prepares the 2D-Coordinate Vertex Stream after culling for the Render Engine
14
to load the 3D graphics.
Culling or backface elimination is an operation that compares the orientation of complete polygons with the view point or center of projection and removes those polygons that cannot be seen. If a polygon can not be seen by a viewer from a point of view, then the polygon does not have to be rendered. Thus, the performance of the render engine
14
can be improved by early removing or culling away the invisible portions with respect to a particular viewpoint because the loading of further graphics process has been substantially reduced.
On average, half of the polygons in a polyhedron are back-facing, that is, invisible. To simplify the operational analysis, a triangle is usually used. The test for visibility is straightforward and is carried out in screen space. We calculate the outward normal for a polygon and examine the sign of this vector in z-axis component. If a culling test is performed on a triangle, the sign of the determinant for the triangle must be examined. Thus,
visibility
:=
{
D
>
0
,
if
vertices
'
order
is
counterclockwise
D
<
0
,
if
vertices
'
order
is
clockwise
;
D
=
&LeftBracketingBar;
x
1
y
1
x
2
y
2
x
3
y
3
&RightBracketingBar;
=
(
x
1
-
x
2
)
(
y
2
-
y
3
)
-
(
x
2
-
x
3
)
(
y
1
-
y
3
)
;
where D is the determinant of the triangle; and Vertices's coodinates are (x
1
, y
1
), (x
2
, y
2
) and (x
3
, y
3
).
In most cases, the culling test is to calculate the outward normal of a triangle and examine the sign of the determinant for the vertices coordinates of a triangle to differentiate the visible and invisible surface from a viewpoint of a viewer. Thus, when the value of the determinant N is positive and the coordinate orientation is counterclockwise or when the value of the determinant N is negative and coordinate orientation is clockwise, the triangle is visible. Otherwise, the triangle is invisible. Accordingly, the vertices coordinates are (x
1
,y
1
),(x
2
, y
2
) and (x
3
,y
3
). The determinant N after operation is equal to (x
1
−x
3
)(y
2
−y
3
)−(x
2
−x
3
)(y
1
−y
3
) respectively. According to the determinant N, it needs two multiplication operations and five subtraction operations to complete the analysis of one triangle. For a cost-effective design of culling module, it is desirable to provide a culling module without using multipliers.
SUMMARY OF THE INVENTION
Accordingly, the object of the present invention is to provide a fast and cost-effective culling method and module, which does not need any multiplication or subtraction operations for finding the vertices coordinates of a triangle. The method of the invention includes the following steps: first, divide the screen space into nine grids according to the positions of the first vertex V
1
and the second vertex V
2
, of a triangle. Continuously, perform a fast culling test for the triangle by examining which grid the third vertex V
3
of a triangle is falling on. According to the relative positions of V
1
, V
2
and the grid where the V
3
is falling in, a SIGN vector and a corresponding culling decision is obtained by looking up a culling decision table. The culling decision table records all the possible combinations of SIGN vectors, corresponding culling decisions and associated coordinate orientations. Culling a triangle may be quickly determined according to the SIGN vector and the corresponding culling decision of a culling decision table. Furthermore, the advantage of the present invention is that it is simple and easy to be implemented by using only a simple comparison circuit and a culling decision table for the culling test. Since the invention does not use multipliers, so the cost can be further reduced. Moreover, since the culling decision table is small, so the speed of table looking up is obviously faster than the computation speed of the conventional culling test.
REFERENCES:
patent: 5757321 (1998-05-01), Billyard
Huang Ta-Lun
Lu Chung-Yen
Birch & Stewart Kolasch & Birch, LLP
Sealey Lance W.
Silicon Integrated Systems Corp.
Zimmerman Mark
LandOfFree
Culling method and module for 3D graphics does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Culling method and module for 3D graphics, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Culling method and module for 3D graphics will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3112240