Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Reexamination Certificate
2000-07-06
2003-01-14
Vo, Cliff N. (Department: 2671)
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
Reexamination Certificate
active
06507341
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 back-face culling of data representing an object.
2. Description of Related Art
Data processing systems, such as personal computers and workstations, 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. Many of these applications may involve the display of three dimensional objects in which an object is rendered or drawn as it actually appears.
The visualization of surfaces is an important application of three-dimensional computer graphics. This technology offers accurate shaded images of surfaces along with the ability to quickly render new shaded images from any viewpoint.
Most three-dimensional computer graphics systems are optimized to render polygons, not surfaces. For this reason surfaces are usually approximated with polygons to enhance graphical performance. This creates a trade-off between the accuracy of a surface's image and the time required to produce it. For instance, a sphere may be approximated with a cube, which consists of only six polygons. The graphical performance on most three-dimensional computer graphics systems will be good in this case, but the accuracy to a sphere will be poor. As the number of polygons used in the approximation is increased the graphical performance suffers.
In many situations, one or more surfaces are used to represent the boundary of a solid. These surfaces each have a direction associated with them which identify the inside versus the outside of the solid. By approximating each surface with a mesh of polygons, surface directions may be substituted with polygonal directions, or normal vectors.
Normal vectors can be exploited during the rendering process to enhance graphical performance. By identifying whether a given normal vector points towards or away from the viewpoint, the corresponding polygon can be interpreted as being front-facing (visible) or back-facing (not visible). A technique called “back-face culling” allows improvements in graphical performance by identifying and rendering only those polygons that are front-facing.
Conventional back-face culling is typically performed using the vector dot product. Given two three-dimensional vectors: a polygon normal vector, N, and an “eye” vector, E, denoting the image plane normal vector pointing out of the screen, the dot product of these vectors determines the visibility of the polygon.
Let N and E be three-dimensional vectors (n
i
, n
j
, n
k
) and (e
i
, e
j
, e
k
), respectively. The vector dot product is defined as
DOT
(N, E)=n
i
*e
i
+n
j
*e
j
+n
k
*e
k
.
If the dot product is positive, then the polygon's front side is facing the image plane—the polygon is front-facing and should be rendered. If the dot product is negative, then the polygon's back side is facing the image plane—the polygon is back-facing and should not be rendered. If the dot product is zero, then the polygon is perpendicular to the image plane—the polygon is neither front nor back-facing and may or may not be rendered.
Although conventional back-face culling is a useful technique for improving graphical performance, it still requires three multiplications and two additions to be performed for each polygon. Therefore, it would be advantageous to have an improved method and apparatus for performing back-face culling without requiring as many operations to be performed for each polygon.
SUMMARY OF THE INVENTION
The present invention provides a method and apparatus in a data processing system for generating a two dimensional display of a three dimensional object. Data is received representing the three dimensional object. Back-face culling is performed using a data structure, wherein the data structure includes a set of predetermined visibility data derived from the results of dot products of normal vectors with eye vectors. The two dimensional display of the three dimensional object is generated using results of the back-face culling.
REFERENCES:
patent: 5898437 (1999-04-01), DEolaliker
Gross Lee Michael
Taylor Andrew Kent
Carwell Robert M.
International Business Machines - Corporation
Vo Cliff N.
Yee Duke W.
LandOfFree
Method and apparatus in a data processing system for... 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 in a data processing system for..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus in a data processing system for... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3059214